1 | /* Simple data type for real numbers for the GNU compiler. |
---|---|

2 | Copyright (C) 2002-2017 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 */ |

387 |