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 (stream: file, format: "(%" 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 (ref: *ptr); |
81 | else |
82 | fprintf (stderr, format: "<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 (x: val, exponent: 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&: a_p, b&: 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 (s: 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&: a_p, b&: 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 (s: 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 (x: m_sig) < SREAL_MIN_SIG |
245 | || absu_hwi (x: 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 (new_sig: m_sig * (int64_t) other.m_sig, new_exp: 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 (a: 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 */ |
445 | |