Branch data Line data Source code
1 : : /* Simple data type for real numbers for the GNU compiler.
2 : : Copyright (C) 2002-2024 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 : 398689365 : sreal::shift_right (int s)
91 : : {
92 : 398689365 : gcc_checking_assert (s > 0);
93 : 398689365 : 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 : 398689365 : gcc_checking_assert (m_exp + s <= SREAL_MAX_EXP);
98 : :
99 : 398689365 : m_exp += s;
100 : :
101 : 398689365 : m_sig += (int64_t) 1 << (s - 1);
102 : 398689365 : m_sig >>= s;
103 : 398689365 : }
104 : :
105 : : /* Return integer value of *this. */
106 : :
107 : : int64_t
108 : 19893437 : sreal::to_int () const
109 : : {
110 : 19893437 : int64_t sign = SREAL_SIGN (m_sig);
111 : :
112 : 19893437 : if (m_exp <= -SREAL_BITS)
113 : : return 0;
114 : 17564938 : if (m_exp >= SREAL_PART_BITS)
115 : 64 : return sign * INTTYPE_MAXIMUM (int64_t);
116 : 17564874 : if (m_exp > 0)
117 : 158 : return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
118 : 17564716 : if (m_exp < 0)
119 : 17564695 : return sign * (SREAL_ABS ((int64_t)m_sig) >> -m_exp);
120 : 21 : return m_sig;
121 : : }
122 : :
123 : : /* Return nearest integer value of *this. */
124 : :
125 : : int64_t
126 : 26834659 : sreal::to_nearest_int () const
127 : : {
128 : 26834659 : int64_t sign = SREAL_SIGN (m_sig);
129 : :
130 : 26834659 : if (m_exp <= -SREAL_BITS)
131 : : return 0;
132 : 23253644 : if (m_exp >= SREAL_PART_BITS)
133 : 2145 : return sign * INTTYPE_MAXIMUM (int64_t);
134 : 23251499 : if (m_exp > 0)
135 : 7005213 : return sign * (SREAL_ABS ((int64_t)m_sig) << m_exp);
136 : 16246286 : if (m_exp < 0)
137 : 14349281 : return sign * ((SREAL_ABS ((int64_t)m_sig) >> -m_exp)
138 : 14349281 : + ((SREAL_ABS (m_sig) >> (-m_exp - 1)) & 1));
139 : 1897005 : 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 : 10276640 : sreal::to_double () const
147 : : {
148 : 10276640 : double val = m_sig;
149 : 10276640 : if (m_exp)
150 : 10276636 : val = ldexp (val, m_exp);
151 : 10276640 : return val;
152 : : }
153 : :
154 : : /* Return *this + other. */
155 : :
156 : : sreal
157 : 584409217 : sreal::operator+ (const sreal &other) const
158 : : {
159 : 584409217 : int dexp;
160 : 584409217 : sreal tmp;
161 : 584409217 : int64_t r_sig, r_exp;
162 : :
163 : 584409217 : const sreal *a_p = this, *b_p = &other, *bb;
164 : :
165 : 584409217 : if (a_p->m_exp < b_p->m_exp)
166 : 96579217 : std::swap (a_p, b_p);
167 : :
168 : 584409217 : dexp = a_p->m_exp - b_p->m_exp;
169 : 584409217 : r_exp = a_p->m_exp;
170 : 584409217 : if (dexp > SREAL_BITS)
171 : : {
172 : 127415935 : r_sig = a_p->m_sig;
173 : :
174 : 127415935 : sreal r;
175 : 127415935 : r.m_sig = r_sig;
176 : 127415935 : r.m_exp = r_exp;
177 : 127415935 : return r;
178 : : }
179 : :
180 : 456993282 : if (dexp == 0)
181 : : bb = b_p;
182 : : else
183 : : {
184 : 385413134 : tmp = *b_p;
185 : 385413134 : tmp.shift_right (dexp);
186 : 385413134 : bb = &tmp;
187 : : }
188 : :
189 : 456993282 : r_sig = a_p->m_sig + (int64_t)bb->m_sig;
190 : 456993282 : sreal r (r_sig, r_exp);
191 : 456993282 : return r;
192 : : }
193 : :
194 : :
195 : : /* Return *this - other. */
196 : :
197 : : sreal
198 : 55281921 : sreal::operator- (const sreal &other) const
199 : : {
200 : 55281921 : int dexp;
201 : 55281921 : sreal tmp;
202 : 55281921 : int64_t r_sig, r_exp;
203 : 55281921 : const sreal *bb;
204 : 55281921 : const sreal *a_p = this, *b_p = &other;
205 : :
206 : 55281921 : int64_t sign = 1;
207 : 55281921 : if (a_p->m_exp < b_p->m_exp)
208 : : {
209 : 4289472 : sign = -1;
210 : 4289472 : std::swap (a_p, b_p);
211 : : }
212 : :
213 : 55281921 : dexp = a_p->m_exp - b_p->m_exp;
214 : 55281921 : r_exp = a_p->m_exp;
215 : 55281921 : if (dexp > SREAL_BITS)
216 : : {
217 : 962652 : r_sig = sign * a_p->m_sig;
218 : :
219 : 962652 : sreal r;
220 : 962652 : r.m_sig = r_sig;
221 : 962652 : r.m_exp = r_exp;
222 : 962652 : return r;
223 : : }
224 : 54319269 : if (dexp == 0)
225 : : bb = b_p;
226 : : else
227 : : {
228 : 13276231 : tmp = *b_p;
229 : 13276231 : tmp.shift_right (dexp);
230 : 13276231 : bb = &tmp;
231 : : }
232 : :
233 : 54319269 : r_sig = sign * ((int64_t) a_p->m_sig - (int64_t)bb->m_sig);
234 : 54319269 : sreal r (r_sig, r_exp);
235 : 54319269 : return r;
236 : : }
237 : :
238 : : /* Return *this * other. */
239 : :
240 : : sreal
241 : 535929040 : sreal::operator* (const sreal &other) const
242 : : {
243 : 535929040 : sreal r;
244 : 535929040 : if (absu_hwi (m_sig) < SREAL_MIN_SIG
245 : 1030783844 : || absu_hwi (other.m_sig) < SREAL_MIN_SIG)
246 : : {
247 : 100303261 : r.m_sig = 0;
248 : 100303261 : r.m_exp = -SREAL_MAX_EXP;
249 : : }
250 : : else
251 : 435625779 : r.normalize (m_sig * (int64_t) other.m_sig, m_exp + other.m_exp);
252 : :
253 : 535929040 : return r;
254 : : }
255 : :
256 : : /* Return *this / other. */
257 : :
258 : : sreal
259 : 308065875 : sreal::operator/ (const sreal &other) const
260 : : {
261 : 308065875 : gcc_checking_assert (other.m_sig != 0);
262 : 308065875 : sreal r (SREAL_SIGN (m_sig)
263 : 308065875 : * ((int64_t)SREAL_ABS (m_sig) << SREAL_PART_BITS) / other.m_sig,
264 : 602733304 : m_exp - other.m_exp - SREAL_PART_BITS);
265 : 308065875 : return r;
266 : : }
267 : :
268 : : /* Stream sreal value to OB. */
269 : :
270 : : void
271 : 374276 : sreal::stream_out (struct output_block *ob)
272 : : {
273 : 374276 : streamer_write_hwi (ob, m_sig);
274 : 374276 : streamer_write_hwi (ob, m_exp);
275 : 374276 : }
276 : :
277 : : /* Read sreal value from IB. */
278 : :
279 : : sreal
280 : 311818 : sreal::stream_in (class lto_input_block *ib)
281 : : {
282 : 311818 : sreal val;
283 : 311818 : val.m_sig = streamer_read_hwi (ib);
284 : 311818 : val.m_exp = streamer_read_hwi (ib);
285 : 311818 : 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 */
|
