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
dump(FILE * file)65 sreal::dump (FILE *file) const
66 {
67 fprintf (file, "(%" PRIi64 " * 2^%d)", m_sig, m_exp);
68 }
69
70 DEBUG_FUNCTION void
debug(const sreal & ref)71 debug (const sreal &ref)
72 {
73 ref.dump (stderr);
74 }
75
76 DEBUG_FUNCTION void
debug(const sreal * ptr)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
shift_right(int s)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
to_int()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
to_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
stream_out(struct output_block * ob)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
stream_in(struct lto_input_block * ib)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
sreal_verify_basics(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
verify_aritmetics(int64_t a,int64_t b)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
sreal_verify_arithmetics(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
verify_shifting(int64_t a)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
sreal_verify_shifting(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
sreal_verify_negative_division(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
sreal_c_tests()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 */
387