1 | /* Operations with long integers. |
---|---|

2 | Copyright (C) 2006-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 |

7 | under the terms of the GNU General Public License as published by the |

8 | Free Software Foundation; either version 3, or (at your option) any |

9 | later version. |

10 | |

11 | GCC is distributed in the hope that it will be useful, but WITHOUT |

12 | ANY 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 | #include "config.h" |

21 | #include "system.h" |

22 | #include "coretypes.h" |

23 | #include "tm.h" /* For BITS_PER_UNIT and *_BIG_ENDIAN. */ |

24 | #include "tree.h" |

25 | |

26 | static int add_double_with_sign (unsigned HOST_WIDE_INT, HOST_WIDE_INT, |

27 | unsigned HOST_WIDE_INT, HOST_WIDE_INT, |

28 | unsigned HOST_WIDE_INT *, HOST_WIDE_INT *, |

29 | bool); |

30 | |

31 | #define add_double(l1,h1,l2,h2,lv,hv) \ |

32 | add_double_with_sign (l1, h1, l2, h2, lv, hv, false) |

33 | |

34 | static int neg_double (unsigned HOST_WIDE_INT, HOST_WIDE_INT, |

35 | unsigned HOST_WIDE_INT *, HOST_WIDE_INT *); |

36 | |

37 | static int mul_double_wide_with_sign (unsigned HOST_WIDE_INT, HOST_WIDE_INT, |

38 | unsigned HOST_WIDE_INT, HOST_WIDE_INT, |

39 | unsigned HOST_WIDE_INT *, HOST_WIDE_INT *, |

40 | unsigned HOST_WIDE_INT *, HOST_WIDE_INT *, |

41 | bool); |

42 | |

43 | #define mul_double(l1,h1,l2,h2,lv,hv) \ |

44 | mul_double_wide_with_sign (l1, h1, l2, h2, lv, hv, NULL, NULL, false) |

45 | |

46 | static int div_and_round_double (unsigned, int, unsigned HOST_WIDE_INT, |

47 | HOST_WIDE_INT, unsigned HOST_WIDE_INT, |

48 | HOST_WIDE_INT, unsigned HOST_WIDE_INT *, |

49 | HOST_WIDE_INT *, unsigned HOST_WIDE_INT *, |

50 | HOST_WIDE_INT *); |

51 | |

52 | /* We know that A1 + B1 = SUM1, using 2's complement arithmetic and ignoring |

53 | overflow. Suppose A, B and SUM have the same respective signs as A1, B1, |

54 | and SUM1. Then this yields nonzero if overflow occurred during the |

55 | addition. |

56 | |

57 | Overflow occurs if A and B have the same sign, but A and SUM differ in |

58 | sign. Use `^' to test whether signs differ, and `< 0' to isolate the |

59 | sign. */ |

60 | #define OVERFLOW_SUM_SIGN(a, b, sum) ((~((a) ^ (b)) & ((a) ^ (sum))) < 0) |

61 | |

62 | /* To do constant folding on INTEGER_CST nodes requires two-word arithmetic. |

63 | We do that by representing the two-word integer in 4 words, with only |

64 | HOST_BITS_PER_WIDE_INT / 2 bits stored in each word, as a positive |

65 | number. The value of the word is LOWPART + HIGHPART * BASE. */ |

66 | |

67 | #define LOWPART(x) \ |

68 | ((x) & ((HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT / 2)) - 1)) |

69 | #define HIGHPART(x) \ |

70 | ((unsigned HOST_WIDE_INT) (x) >> HOST_BITS_PER_WIDE_INT / 2) |

71 | #define BASE (HOST_WIDE_INT_1U << HOST_BITS_PER_WIDE_INT / 2) |

72 | |

73 | /* Unpack a two-word integer into 4 words. |

74 | LOW and HI are the integer, as two `HOST_WIDE_INT' pieces. |

75 | WORDS points to the array of HOST_WIDE_INTs. */ |

76 | |

77 | static void |

78 | encode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT low, HOST_WIDE_INT hi) |

79 | { |

80 | words[0] = LOWPART (low); |

81 | words[1] = HIGHPART (low); |

82 | words[2] = LOWPART (hi); |

83 | words[3] = HIGHPART (hi); |

84 | } |

85 | |

86 | /* Pack an array of 4 words into a two-word integer. |

87 | WORDS points to the array of words. |

88 | The integer is stored into *LOW and *HI as two `HOST_WIDE_INT' pieces. */ |

89 | |

90 | static void |

91 | decode (HOST_WIDE_INT *words, unsigned HOST_WIDE_INT *low, |

92 | HOST_WIDE_INT *hi) |

93 | { |

94 | *low = words[0] + words[1] * BASE; |

95 | *hi = words[2] + words[3] * BASE; |

96 | } |

97 | |

98 | /* Add two doubleword integers with doubleword result. |

99 | Return nonzero if the operation overflows according to UNSIGNED_P. |

100 | Each argument is given as two `HOST_WIDE_INT' pieces. |

101 | One argument is L1 and H1; the other, L2 and H2. |

102 | The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */ |

103 | |

104 | static int |

105 | add_double_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, |

106 | unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2, |

107 | unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, |

108 | bool unsigned_p) |

109 | { |

110 | unsigned HOST_WIDE_INT l; |

111 | HOST_WIDE_INT h; |

112 | |

113 | l = l1 + l2; |

114 | h = (HOST_WIDE_INT) ((unsigned HOST_WIDE_INT) h1 |

115 | + (unsigned HOST_WIDE_INT) h2 |

116 | + (l < l1)); |

117 | |

118 | *lv = l; |

119 | *hv = h; |

120 | |

121 | if (unsigned_p) |

122 | return ((unsigned HOST_WIDE_INT) h < (unsigned HOST_WIDE_INT) h1 |

123 | || (h == h1 |

124 | && l < l1)); |

125 | else |

126 | return OVERFLOW_SUM_SIGN (h1, h2, h); |

127 | } |

128 | |

129 | /* Negate a doubleword integer with doubleword result. |

130 | Return nonzero if the operation overflows, assuming it's signed. |

131 | The argument is given as two `HOST_WIDE_INT' pieces in L1 and H1. |

132 | The value is stored as two `HOST_WIDE_INT' pieces in *LV and *HV. */ |

133 | |

134 | static int |

135 | neg_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, |

136 | unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv) |

137 | { |

138 | if (l1 == 0) |

139 | { |

140 | *lv = 0; |

141 | *hv = - (unsigned HOST_WIDE_INT) h1; |

142 | return (*hv & h1) < 0; |

143 | } |

144 | else |

145 | { |

146 | *lv = -l1; |

147 | *hv = ~h1; |

148 | return 0; |

149 | } |

150 | } |

151 | |

152 | /* Multiply two doubleword integers with quadword result. |

153 | Return nonzero if the operation overflows according to UNSIGNED_P. |

154 | Each argument is given as two `HOST_WIDE_INT' pieces. |

155 | One argument is L1 and H1; the other, L2 and H2. |

156 | The value is stored as four `HOST_WIDE_INT' pieces in *LV and *HV, |

157 | *LW and *HW. |

158 | If lw is NULL then only the low part and no overflow is computed. */ |

159 | |

160 | static int |

161 | mul_double_wide_with_sign (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, |

162 | unsigned HOST_WIDE_INT l2, HOST_WIDE_INT h2, |

163 | unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, |

164 | unsigned HOST_WIDE_INT *lw, HOST_WIDE_INT *hw, |

165 | bool unsigned_p) |

166 | { |

167 | HOST_WIDE_INT arg1[4]; |

168 | HOST_WIDE_INT arg2[4]; |

169 | HOST_WIDE_INT prod[4 * 2]; |

170 | unsigned HOST_WIDE_INT carry; |

171 | int i, j, k; |

172 | unsigned HOST_WIDE_INT neglow; |

173 | HOST_WIDE_INT neghigh; |

174 | |

175 | encode (arg1, l1, h1); |

176 | encode (arg2, l2, h2); |

177 | |

178 | memset (prod, 0, sizeof prod); |

179 | |

180 | for (i = 0; i < 4; i++) |

181 | { |

182 | carry = 0; |

183 | for (j = 0; j < 4; j++) |

184 | { |

185 | k = i + j; |

186 | /* This product is <= 0xFFFE0001, the sum <= 0xFFFF0000. */ |

187 | carry += (unsigned HOST_WIDE_INT) arg1[i] * arg2[j]; |

188 | /* Since prod[p] < 0xFFFF, this sum <= 0xFFFFFFFF. */ |

189 | carry += prod[k]; |

190 | prod[k] = LOWPART (carry); |

191 | carry = HIGHPART (carry); |

192 | } |

193 | prod[i + 4] = carry; |

194 | } |

195 | |

196 | decode (prod, lv, hv); |

197 | |

198 | /* We are not interested in the wide part nor in overflow. */ |

199 | if (lw == NULL) |

200 | return 0; |

201 | |

202 | decode (prod + 4, lw, hw); |

203 | |

204 | /* Unsigned overflow is immediate. */ |

205 | if (unsigned_p) |

206 | return (*lw | *hw) != 0; |

207 | |

208 | /* Check for signed overflow by calculating the signed representation of the |

209 | top half of the result; it should agree with the low half's sign bit. */ |

210 | if (h1 < 0) |

211 | { |

212 | neg_double (l2, h2, &neglow, &neghigh); |

213 | add_double (neglow, neghigh, *lw, *hw, lw, hw); |

214 | } |

215 | if (h2 < 0) |

216 | { |

217 | neg_double (l1, h1, &neglow, &neghigh); |

218 | add_double (neglow, neghigh, *lw, *hw, lw, hw); |

219 | } |

220 | return (*hv < 0 ? ~(*lw & *hw) : *lw | *hw) != 0; |

221 | } |

222 | |

223 | /* Shift the doubleword integer in L1, H1 right by COUNT places |

224 | keeping only PREC bits of result. ARITH nonzero specifies |

225 | arithmetic shifting; otherwise use logical shift. |

226 | Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */ |

227 | |

228 | static void |

229 | rshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, |

230 | unsigned HOST_WIDE_INT count, unsigned int prec, |

231 | unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv, |

232 | bool arith) |

233 | { |

234 | unsigned HOST_WIDE_INT signmask; |

235 | |

236 | signmask = (arith |

237 | ? -((unsigned HOST_WIDE_INT) h1 >> (HOST_BITS_PER_WIDE_INT - 1)) |

238 | : 0); |

239 | |

240 | if (count >= HOST_BITS_PER_DOUBLE_INT) |

241 | { |

242 | /* Shifting by the host word size is undefined according to the |

243 | ANSI standard, so we must handle this as a special case. */ |

244 | *hv = 0; |

245 | *lv = 0; |

246 | } |

247 | else if (count >= HOST_BITS_PER_WIDE_INT) |

248 | { |

249 | *hv = 0; |

250 | *lv = (unsigned HOST_WIDE_INT) h1 >> (count - HOST_BITS_PER_WIDE_INT); |

251 | } |

252 | else |

253 | { |

254 | *hv = (unsigned HOST_WIDE_INT) h1 >> count; |

255 | *lv = ((l1 >> count) |

256 | | ((unsigned HOST_WIDE_INT) h1 |

257 | << (HOST_BITS_PER_WIDE_INT - count - 1) << 1)); |

258 | } |

259 | |

260 | /* Zero / sign extend all bits that are beyond the precision. */ |

261 | |

262 | if (count >= prec) |

263 | { |

264 | *hv = signmask; |

265 | *lv = signmask; |

266 | } |

267 | else if ((prec - count) >= HOST_BITS_PER_DOUBLE_INT) |

268 | ; |

269 | else if ((prec - count) >= HOST_BITS_PER_WIDE_INT) |

270 | { |

271 | *hv &= ~(HOST_WIDE_INT_M1U << (prec - count - HOST_BITS_PER_WIDE_INT)); |

272 | *hv |= signmask << (prec - count - HOST_BITS_PER_WIDE_INT); |

273 | } |

274 | else |

275 | { |

276 | *hv = signmask; |

277 | *lv &= ~(HOST_WIDE_INT_M1U << (prec - count)); |

278 | *lv |= signmask << (prec - count); |

279 | } |

280 | } |

281 | |

282 | /* Shift the doubleword integer in L1, H1 left by COUNT places |

283 | keeping only PREC bits of result. |

284 | Shift right if COUNT is negative. |

285 | ARITH nonzero specifies arithmetic shifting; otherwise use logical shift. |

286 | Store the value as two `HOST_WIDE_INT' pieces in *LV and *HV. */ |

287 | |

288 | static void |

289 | lshift_double (unsigned HOST_WIDE_INT l1, HOST_WIDE_INT h1, |

290 | unsigned HOST_WIDE_INT count, unsigned int prec, |

291 | unsigned HOST_WIDE_INT *lv, HOST_WIDE_INT *hv) |

292 | { |

293 | unsigned HOST_WIDE_INT signmask; |

294 | |

295 | if (count >= HOST_BITS_PER_DOUBLE_INT) |

296 | { |

297 | /* Shifting by the host word size is undefined according to the |

298 | ANSI standard, so we must handle this as a special case. */ |

299 | *hv = 0; |

300 | *lv = 0; |

301 | } |

302 | else if (count >= HOST_BITS_PER_WIDE_INT) |

303 | { |

304 | *hv = l1 << (count - HOST_BITS_PER_WIDE_INT); |

305 | *lv = 0; |

306 | } |

307 | else |

308 | { |

309 | *hv = (((unsigned HOST_WIDE_INT) h1 << count) |

310 | | (l1 >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1)); |

311 | *lv = l1 << count; |

312 | } |

313 | |

314 | /* Sign extend all bits that are beyond the precision. */ |

315 | |

316 | signmask = -((prec > HOST_BITS_PER_WIDE_INT |

317 | ? ((unsigned HOST_WIDE_INT) *hv |

318 | >> (prec - HOST_BITS_PER_WIDE_INT - 1)) |

319 | : (*lv >> (prec - 1))) & 1); |

320 | |

321 | if (prec >= HOST_BITS_PER_DOUBLE_INT) |

322 | ; |

323 | else if (prec >= HOST_BITS_PER_WIDE_INT) |

324 | { |

325 | *hv &= ~(HOST_WIDE_INT_M1U << (prec - HOST_BITS_PER_WIDE_INT)); |

326 | *hv |= signmask << (prec - HOST_BITS_PER_WIDE_INT); |

327 | } |

328 | else |

329 | { |

330 | *hv = signmask; |

331 | *lv &= ~(HOST_WIDE_INT_M1U << prec); |

332 | *lv |= signmask << prec; |

333 | } |

334 | } |

335 | |

336 | /* Divide doubleword integer LNUM, HNUM by doubleword integer LDEN, HDEN |

337 | for a quotient (stored in *LQUO, *HQUO) and remainder (in *LREM, *HREM). |

338 | CODE is a tree code for a kind of division, one of |

339 | TRUNC_DIV_EXPR, FLOOR_DIV_EXPR, CEIL_DIV_EXPR, ROUND_DIV_EXPR |

340 | or EXACT_DIV_EXPR |

341 | It controls how the quotient is rounded to an integer. |

342 | Return nonzero if the operation overflows. |

343 | UNS nonzero says do unsigned division. */ |

344 | |

345 | static int |

346 | div_and_round_double (unsigned code, int uns, |

347 | /* num == numerator == dividend */ |

348 | unsigned HOST_WIDE_INT lnum_orig, |

349 | HOST_WIDE_INT hnum_orig, |

350 | /* den == denominator == divisor */ |

351 | unsigned HOST_WIDE_INT lden_orig, |

352 | HOST_WIDE_INT hden_orig, |

353 | unsigned HOST_WIDE_INT *lquo, |

354 | HOST_WIDE_INT *hquo, unsigned HOST_WIDE_INT *lrem, |

355 | HOST_WIDE_INT *hrem) |

356 | { |

357 | int quo_neg = 0; |

358 | HOST_WIDE_INT num[4 + 1]; /* extra element for scaling. */ |

359 | HOST_WIDE_INT den[4], quo[4]; |

360 | int i, j; |

361 | unsigned HOST_WIDE_INT work; |

362 | unsigned HOST_WIDE_INT carry = 0; |

363 | unsigned HOST_WIDE_INT lnum = lnum_orig; |

364 | HOST_WIDE_INT hnum = hnum_orig; |

365 | unsigned HOST_WIDE_INT lden = lden_orig; |

366 | HOST_WIDE_INT hden = hden_orig; |

367 | int overflow = 0; |

368 | |

369 | if (hden == 0 && lden == 0) |

370 | overflow = 1, lden = 1; |

371 | |

372 | /* Calculate quotient sign and convert operands to unsigned. */ |

373 | if (!uns) |

374 | { |

375 | if (hnum < 0) |

376 | { |

377 | quo_neg = ~ quo_neg; |

378 | /* (minimum integer) / (-1) is the only overflow case. */ |

379 | if (neg_double (lnum, hnum, &lnum, &hnum) |

380 | && ((HOST_WIDE_INT) lden & hden) == -1) |

381 | overflow = 1; |

382 | } |

383 | if (hden < 0) |

384 | { |

385 | quo_neg = ~ quo_neg; |

386 | neg_double (lden, hden, &lden, &hden); |

387 | } |

388 | } |

389 | |

390 | if (hnum == 0 && hden == 0) |

391 | { /* single precision */ |

392 | *hquo = *hrem = 0; |

393 | /* This unsigned division rounds toward zero. */ |

394 | *lquo = lnum / lden; |

395 | goto finish_up; |

396 | } |

397 | |

398 | if (hnum == 0) |

399 | { /* trivial case: dividend < divisor */ |

400 | /* hden != 0 already checked. */ |

401 | *hquo = *lquo = 0; |

402 | *hrem = hnum; |

403 | *lrem = lnum; |

404 | goto finish_up; |

405 | } |

406 | |

407 | memset (quo, 0, sizeof quo); |

408 | |

409 | memset (num, 0, sizeof num); /* to zero 9th element */ |

410 | memset (den, 0, sizeof den); |

411 | |

412 | encode (num, lnum, hnum); |

413 | encode (den, lden, hden); |

414 | |

415 | /* Special code for when the divisor < BASE. */ |

416 | if (hden == 0 && lden < (unsigned HOST_WIDE_INT) BASE) |

417 | { |

418 | /* hnum != 0 already checked. */ |

419 | for (i = 4 - 1; i >= 0; i--) |

420 | { |

421 | work = num[i] + carry * BASE; |

422 | quo[i] = work / lden; |

423 | carry = work % lden; |

424 | } |

425 | } |

426 | else |

427 | { |

428 | /* Full double precision division, |

429 | with thanks to Don Knuth's "Seminumerical Algorithms". */ |

430 | int num_hi_sig, den_hi_sig; |

431 | unsigned HOST_WIDE_INT quo_est, scale; |

432 | |

433 | /* Find the highest nonzero divisor digit. */ |

434 | for (i = 4 - 1;; i--) |

435 | if (den[i] != 0) |

436 | { |

437 | den_hi_sig = i; |

438 | break; |

439 | } |

440 | |

441 | /* Insure that the first digit of the divisor is at least BASE/2. |

442 | This is required by the quotient digit estimation algorithm. */ |

443 | |

444 | scale = BASE / (den[den_hi_sig] + 1); |

445 | if (scale > 1) |

446 | { /* scale divisor and dividend */ |

447 | carry = 0; |

448 | for (i = 0; i <= 4 - 1; i++) |

449 | { |

450 | work = (num[i] * scale) + carry; |

451 | num[i] = LOWPART (work); |

452 | carry = HIGHPART (work); |

453 | } |

454 | |

455 | num[4] = carry; |

456 | carry = 0; |

457 | for (i = 0; i <= 4 - 1; i++) |

458 | { |

459 | work = (den[i] * scale) + carry; |

460 | den[i] = LOWPART (work); |

461 | carry = HIGHPART (work); |

462 | if (den[i] != 0) den_hi_sig = i; |

463 | } |

464 | } |

465 | |

466 | num_hi_sig = 4; |

467 | |

468 | /* Main loop */ |

469 | for (i = num_hi_sig - den_hi_sig - 1; i >= 0; i--) |

470 | { |

471 | /* Guess the next quotient digit, quo_est, by dividing the first |

472 | two remaining dividend digits by the high order quotient digit. |

473 | quo_est is never low and is at most 2 high. */ |

474 | unsigned HOST_WIDE_INT tmp; |

475 | |

476 | num_hi_sig = i + den_hi_sig + 1; |

477 | work = num[num_hi_sig] * BASE + num[num_hi_sig - 1]; |

478 | if (num[num_hi_sig] != den[den_hi_sig]) |

479 | quo_est = work / den[den_hi_sig]; |

480 | else |

481 | quo_est = BASE - 1; |

482 | |

483 | /* Refine quo_est so it's usually correct, and at most one high. */ |

484 | tmp = work - quo_est * den[den_hi_sig]; |

485 | if (tmp < BASE |

486 | && (den[den_hi_sig - 1] * quo_est |

487 | > (tmp * BASE + num[num_hi_sig - 2]))) |

488 | quo_est--; |

489 | |

490 | /* Try QUO_EST as the quotient digit, by multiplying the |

491 | divisor by QUO_EST and subtracting from the remaining dividend. |

492 | Keep in mind that QUO_EST is the I - 1st digit. */ |

493 | |

494 | carry = 0; |

495 | for (j = 0; j <= den_hi_sig; j++) |

496 | { |

497 | work = quo_est * den[j] + carry; |

498 | carry = HIGHPART (work); |

499 | work = num[i + j] - LOWPART (work); |

500 | num[i + j] = LOWPART (work); |

501 | carry += HIGHPART (work) != 0; |

502 | } |

503 | |

504 | /* If quo_est was high by one, then num[i] went negative and |

505 | we need to correct things. */ |

506 | if (num[num_hi_sig] < (HOST_WIDE_INT) carry) |

507 | { |

508 | quo_est--; |

509 | carry = 0; /* add divisor back in */ |

510 | for (j = 0; j <= den_hi_sig; j++) |

511 | { |

512 | work = num[i + j] + den[j] + carry; |

513 | carry = HIGHPART (work); |

514 | num[i + j] = LOWPART (work); |

515 | } |

516 | |

517 | num [num_hi_sig] += carry; |

518 | } |

519 | |

520 | /* Store the quotient digit. */ |

521 | quo[i] = quo_est; |

522 | } |

523 | } |

524 | |

525 | decode (quo, lquo, hquo); |

526 | |

527 | finish_up: |

528 | /* If result is negative, make it so. */ |

529 | if (quo_neg) |

530 | neg_double (*lquo, *hquo, lquo, hquo); |

531 | |

532 | /* Compute trial remainder: rem = num - (quo * den) */ |

533 | mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem); |

534 | neg_double (*lrem, *hrem, lrem, hrem); |

535 | add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem); |

536 | |

537 | switch (code) |

538 | { |

539 | case TRUNC_DIV_EXPR: |

540 | case TRUNC_MOD_EXPR: /* round toward zero */ |

541 | case EXACT_DIV_EXPR: /* for this one, it shouldn't matter */ |

542 | return overflow; |

543 | |

544 | case FLOOR_DIV_EXPR: |

545 | case FLOOR_MOD_EXPR: /* round toward negative infinity */ |

546 | if (quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio < 0 && rem != 0 */ |

547 | { |

548 | /* quo = quo - 1; */ |

549 | add_double (*lquo, *hquo, HOST_WIDE_INT_M1, HOST_WIDE_INT_M1, |

550 | lquo, hquo); |

551 | } |

552 | else |

553 | return overflow; |

554 | break; |

555 | |

556 | case CEIL_DIV_EXPR: |

557 | case CEIL_MOD_EXPR: /* round toward positive infinity */ |

558 | if (!quo_neg && (*lrem != 0 || *hrem != 0)) /* ratio > 0 && rem != 0 */ |

559 | { |

560 | add_double (*lquo, *hquo, HOST_WIDE_INT_1, HOST_WIDE_INT_0, |

561 | lquo, hquo); |

562 | } |

563 | else |

564 | return overflow; |

565 | break; |

566 | |

567 | case ROUND_DIV_EXPR: |

568 | case ROUND_MOD_EXPR: /* round to closest integer */ |

569 | { |

570 | unsigned HOST_WIDE_INT labs_rem = *lrem; |

571 | HOST_WIDE_INT habs_rem = *hrem; |

572 | unsigned HOST_WIDE_INT labs_den = lden, lnegabs_rem, ldiff; |

573 | HOST_WIDE_INT habs_den = hden, hnegabs_rem, hdiff; |

574 | |

575 | /* Get absolute values. */ |

576 | if (!uns && *hrem < 0) |

577 | neg_double (*lrem, *hrem, &labs_rem, &habs_rem); |

578 | if (!uns && hden < 0) |

579 | neg_double (lden, hden, &labs_den, &habs_den); |

580 | |

581 | /* If abs(rem) >= abs(den) - abs(rem), adjust the quotient. */ |

582 | neg_double (labs_rem, habs_rem, &lnegabs_rem, &hnegabs_rem); |

583 | add_double (labs_den, habs_den, lnegabs_rem, hnegabs_rem, |

584 | &ldiff, &hdiff); |

585 | |

586 | if (((unsigned HOST_WIDE_INT) habs_rem |

587 | > (unsigned HOST_WIDE_INT) hdiff) |

588 | || (habs_rem == hdiff && labs_rem >= ldiff)) |

589 | { |

590 | if (quo_neg) |

591 | /* quo = quo - 1; */ |

592 | add_double (*lquo, *hquo, |

593 | HOST_WIDE_INT_M1, HOST_WIDE_INT_M1, lquo, hquo); |

594 | else |

595 | /* quo = quo + 1; */ |

596 | add_double (*lquo, *hquo, HOST_WIDE_INT_1, HOST_WIDE_INT_0, |

597 | lquo, hquo); |

598 | } |

599 | else |

600 | return overflow; |

601 | } |

602 | break; |

603 | |

604 | default: |

605 | gcc_unreachable (); |

606 | } |

607 | |

608 | /* Compute true remainder: rem = num - (quo * den) */ |

609 | mul_double (*lquo, *hquo, lden_orig, hden_orig, lrem, hrem); |

610 | neg_double (*lrem, *hrem, lrem, hrem); |

611 | add_double (lnum_orig, hnum_orig, *lrem, *hrem, lrem, hrem); |

612 | return overflow; |

613 | } |

614 | |

615 | |

616 | /* Construct from a buffer of length LEN. BUFFER will be read according |

617 | to byte endianness and word endianness. Only the lower LEN bytes |

618 | of the result are set; the remaining high bytes are cleared. */ |

619 | |

620 | double_int |

621 | double_int::from_buffer (const unsigned char *buffer, int len) |

622 | { |

623 | double_int result = double_int_zero; |

624 | int words = len / UNITS_PER_WORD; |

625 | |

626 | gcc_assert (len * BITS_PER_UNIT <= HOST_BITS_PER_DOUBLE_INT); |

627 | |

628 | for (int byte = 0; byte < len; byte++) |

629 | { |

630 | int offset; |

631 | int bitpos = byte * BITS_PER_UNIT; |

632 | unsigned HOST_WIDE_INT value; |

633 | |

634 | if (len > UNITS_PER_WORD) |

635 | { |

636 | int word = byte / UNITS_PER_WORD; |

637 | |

638 | if (WORDS_BIG_ENDIAN) |

639 | word = (words - 1) - word; |

640 | |

641 | offset = word * UNITS_PER_WORD; |

642 | |

643 | if (BYTES_BIG_ENDIAN) |

644 | offset += (UNITS_PER_WORD - 1) - (byte % UNITS_PER_WORD); |

645 | else |

646 | offset += byte % UNITS_PER_WORD; |

647 | } |

648 | else |

649 | offset = BYTES_BIG_ENDIAN ? (len - 1) - byte : byte; |

650 | |

651 | value = (unsigned HOST_WIDE_INT) buffer[offset]; |

652 | |

653 | if (bitpos < HOST_BITS_PER_WIDE_INT) |

654 | result.low |= value << bitpos; |

655 | else |

656 | result.high |= value << (bitpos - HOST_BITS_PER_WIDE_INT); |

657 | } |

658 | |

659 | return result; |

660 | } |

661 | |

662 | |

663 | /* Returns mask for PREC bits. */ |

664 | |

665 | double_int |

666 | double_int::mask (unsigned prec) |

667 | { |

668 | unsigned HOST_WIDE_INT m; |

669 | double_int mask; |

670 | |

671 | if (prec > HOST_BITS_PER_WIDE_INT) |

672 | { |

673 | prec -= HOST_BITS_PER_WIDE_INT; |

674 | m = ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1; |

675 | mask.high = (HOST_WIDE_INT) m; |

676 | mask.low = ALL_ONES; |

677 | } |

678 | else |

679 | { |

680 | mask.high = 0; |

681 | mask.low = prec ? ((unsigned HOST_WIDE_INT) 2 << (prec - 1)) - 1 : 0; |

682 | } |

683 | |

684 | return mask; |

685 | } |

686 | |

687 | /* Returns a maximum value for signed or unsigned integer |

688 | of precision PREC. */ |

689 | |

690 | double_int |

691 | double_int::max_value (unsigned int prec, bool uns) |

692 | { |

693 | return double_int::mask (prec - (uns ? 0 : 1)); |

694 | } |

695 | |

696 | /* Returns a minimum value for signed or unsigned integer |

697 | of precision PREC. */ |

698 | |

699 | double_int |

700 | double_int::min_value (unsigned int prec, bool uns) |

701 | { |

702 | if (uns) |

703 | return double_int_zero; |

704 | return double_int_one.lshift (prec - 1, prec, false); |

705 | } |

706 | |

707 | /* Clears the bits of CST over the precision PREC. If UNS is false, the bits |

708 | outside of the precision are set to the sign bit (i.e., the PREC-th one), |

709 | otherwise they are set to zero. |

710 | |

711 | This corresponds to returning the value represented by PREC lowermost bits |

712 | of CST, with the given signedness. */ |

713 | |

714 | double_int |

715 | double_int::ext (unsigned prec, bool uns) const |

716 | { |

717 | if (uns) |

718 | return this->zext (prec); |

719 | else |

720 | return this->sext (prec); |

721 | } |

722 | |

723 | /* The same as double_int::ext with UNS = true. */ |

724 | |

725 | double_int |

726 | double_int::zext (unsigned prec) const |

727 | { |

728 | const double_int &cst = *this; |

729 | double_int mask = double_int::mask (prec); |

730 | double_int r; |

731 | |

732 | r.low = cst.low & mask.low; |

733 | r.high = cst.high & mask.high; |

734 | |

735 | return r; |

736 | } |

737 | |

738 | /* The same as double_int::ext with UNS = false. */ |

739 | |

740 | double_int |

741 | double_int::sext (unsigned prec) const |

742 | { |

743 | const double_int &cst = *this; |

744 | double_int mask = double_int::mask (prec); |

745 | double_int r; |

746 | unsigned HOST_WIDE_INT snum; |

747 | |

748 | if (prec <= HOST_BITS_PER_WIDE_INT) |

749 | snum = cst.low; |

750 | else |

751 | { |

752 | prec -= HOST_BITS_PER_WIDE_INT; |

753 | snum = (unsigned HOST_WIDE_INT) cst.high; |

754 | } |

755 | if (((snum >> (prec - 1)) & 1) == 1) |

756 | { |

757 | r.low = cst.low | ~mask.low; |

758 | r.high = cst.high | ~mask.high; |

759 | } |

760 | else |

761 | { |

762 | r.low = cst.low & mask.low; |

763 | r.high = cst.high & mask.high; |

764 | } |

765 | |

766 | return r; |

767 | } |

768 | |

769 | /* Returns true if CST fits in signed HOST_WIDE_INT. */ |

770 | |

771 | bool |

772 | double_int::fits_shwi () const |

773 | { |

774 | const double_int &cst = *this; |

775 | if (cst.high == 0) |

776 | return (HOST_WIDE_INT) cst.low >= 0; |

777 | else if (cst.high == -1) |

778 | return (HOST_WIDE_INT) cst.low < 0; |

779 | else |

780 | return false; |

781 | } |

782 | |

783 | /* Returns true if CST fits in HOST_WIDE_INT if UNS is false, or in |

784 | unsigned HOST_WIDE_INT if UNS is true. */ |

785 | |

786 | bool |

787 | double_int::fits_hwi (bool uns) const |

788 | { |

789 | if (uns) |

790 | return this->fits_uhwi (); |

791 | else |

792 | return this->fits_shwi (); |

793 | } |

794 | |

795 | /* Returns A * B. */ |

796 | |

797 | double_int |

798 | double_int::operator * (double_int b) const |

799 | { |

800 | const double_int &a = *this; |

801 | double_int ret; |

802 | mul_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high); |

803 | return ret; |

804 | } |

805 | |

806 | /* Multiplies *this with B and returns a reference to *this. */ |

807 | |

808 | double_int & |

809 | double_int::operator *= (double_int b) |

810 | { |

811 | mul_double (low, high, b.low, b.high, &low, &high); |

812 | return *this; |

813 | } |

814 | |

815 | /* Returns A * B. If the operation overflows according to UNSIGNED_P, |

816 | *OVERFLOW is set to nonzero. */ |

817 | |

818 | double_int |

819 | double_int::mul_with_sign (double_int b, bool unsigned_p, bool *overflow) const |

820 | { |

821 | const double_int &a = *this; |

822 | double_int ret, tem; |

823 | *overflow = mul_double_wide_with_sign (a.low, a.high, b.low, b.high, |

824 | &ret.low, &ret.high, |

825 | &tem.low, &tem.high, unsigned_p); |

826 | return ret; |

827 | } |

828 | |

829 | double_int |

830 | double_int::wide_mul_with_sign (double_int b, bool unsigned_p, |

831 | double_int *higher, bool *overflow) const |

832 | |

833 | { |

834 | double_int lower; |

835 | *overflow = mul_double_wide_with_sign (low, high, b.low, b.high, |

836 | &lower.low, &lower.high, |

837 | &higher->low, &higher->high, |

838 | unsigned_p); |

839 | return lower; |

840 | } |

841 | |

842 | /* Returns A + B. */ |

843 | |

844 | double_int |

845 | double_int::operator + (double_int b) const |

846 | { |

847 | const double_int &a = *this; |

848 | double_int ret; |

849 | add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high); |

850 | return ret; |

851 | } |

852 | |

853 | /* Adds B to *this and returns a reference to *this. */ |

854 | |

855 | double_int & |

856 | double_int::operator += (double_int b) |

857 | { |

858 | add_double (low, high, b.low, b.high, &low, &high); |

859 | return *this; |

860 | } |

861 | |

862 | |

863 | /* Returns A + B. If the operation overflows according to UNSIGNED_P, |

864 | *OVERFLOW is set to nonzero. */ |

865 | |

866 | double_int |

867 | double_int::add_with_sign (double_int b, bool unsigned_p, bool *overflow) const |

868 | { |

869 | const double_int &a = *this; |

870 | double_int ret; |

871 | *overflow = add_double_with_sign (a.low, a.high, b.low, b.high, |

872 | &ret.low, &ret.high, unsigned_p); |

873 | return ret; |

874 | } |

875 | |

876 | /* Returns A - B. */ |

877 | |

878 | double_int |

879 | double_int::operator - (double_int b) const |

880 | { |

881 | const double_int &a = *this; |

882 | double_int ret; |

883 | neg_double (b.low, b.high, &b.low, &b.high); |

884 | add_double (a.low, a.high, b.low, b.high, &ret.low, &ret.high); |

885 | return ret; |

886 | } |

887 | |

888 | /* Subtracts B from *this and returns a reference to *this. */ |

889 | |

890 | double_int & |

891 | double_int::operator -= (double_int b) |

892 | { |

893 | neg_double (b.low, b.high, &b.low, &b.high); |

894 | add_double (low, high, b.low, b.high, &low, &high); |

895 | return *this; |

896 | } |

897 | |

898 | |

899 | /* Returns A - B. If the operation overflows via inconsistent sign bits, |

900 | *OVERFLOW is set to nonzero. */ |

901 | |

902 | double_int |

903 | double_int::sub_with_overflow (double_int b, bool *overflow) const |

904 | { |

905 | double_int ret; |

906 | neg_double (b.low, b.high, &ret.low, &ret.high); |

907 | add_double (low, high, ret.low, ret.high, &ret.low, &ret.high); |

908 | *overflow = OVERFLOW_SUM_SIGN (ret.high, b.high, high); |

909 | return ret; |

910 | } |

911 | |

912 | /* Returns -A. */ |

913 | |

914 | double_int |

915 | double_int::operator - () const |

916 | { |

917 | const double_int &a = *this; |

918 | double_int ret; |

919 | neg_double (a.low, a.high, &ret.low, &ret.high); |

920 | return ret; |

921 | } |

922 | |

923 | double_int |

924 | double_int::neg_with_overflow (bool *overflow) const |

925 | { |

926 | double_int ret; |

927 | *overflow = neg_double (low, high, &ret.low, &ret.high); |

928 | return ret; |

929 | } |

930 | |

931 | /* Returns A / B (computed as unsigned depending on UNS, and rounded as |

932 | specified by CODE). CODE is enum tree_code in fact, but double_int.h |

933 | must be included before tree.h. The remainder after the division is |

934 | stored to MOD. */ |

935 | |

936 | double_int |

937 | double_int::divmod_with_overflow (double_int b, bool uns, unsigned code, |

938 | double_int *mod, bool *overflow) const |

939 | { |

940 | const double_int &a = *this; |

941 | double_int ret; |

942 | |

943 | *overflow = div_and_round_double (code, uns, a.low, a.high, |

944 | b.low, b.high, &ret.low, &ret.high, |

945 | &mod->low, &mod->high); |

946 | return ret; |

947 | } |

948 | |

949 | double_int |

950 | double_int::divmod (double_int b, bool uns, unsigned code, |

951 | double_int *mod) const |

952 | { |

953 | const double_int &a = *this; |

954 | double_int ret; |

955 | |

956 | div_and_round_double (code, uns, a.low, a.high, |

957 | b.low, b.high, &ret.low, &ret.high, |

958 | &mod->low, &mod->high); |

959 | return ret; |

960 | } |

961 | |

962 | /* The same as double_int::divmod with UNS = false. */ |

963 | |

964 | double_int |

965 | double_int::sdivmod (double_int b, unsigned code, double_int *mod) const |

966 | { |

967 | return this->divmod (b, false, code, mod); |

968 | } |

969 | |

970 | /* The same as double_int::divmod with UNS = true. */ |

971 | |

972 | double_int |

973 | double_int::udivmod (double_int b, unsigned code, double_int *mod) const |

974 | { |

975 | return this->divmod (b, true, code, mod); |

976 | } |

977 | |

978 | /* Returns A / B (computed as unsigned depending on UNS, and rounded as |

979 | specified by CODE). CODE is enum tree_code in fact, but double_int.h |

980 | must be included before tree.h. */ |

981 | |

982 | double_int |

983 | double_int::div (double_int b, bool uns, unsigned code) const |

984 | { |

985 | double_int mod; |

986 | |

987 | return this->divmod (b, uns, code, &mod); |

988 | } |

989 | |

990 | /* The same as double_int::div with UNS = false. */ |

991 | |

992 | double_int |

993 | double_int::sdiv (double_int b, unsigned code) const |

994 | { |

995 | return this->div (b, false, code); |

996 | } |

997 | |

998 | /* The same as double_int::div with UNS = true. */ |

999 | |

1000 | double_int |

1001 | double_int::udiv (double_int b, unsigned code) const |

1002 | { |

1003 | return this->div (b, true, code); |

1004 | } |

1005 | |

1006 | /* Returns A % B (computed as unsigned depending on UNS, and rounded as |

1007 | specified by CODE). CODE is enum tree_code in fact, but double_int.h |

1008 | must be included before tree.h. */ |

1009 | |

1010 | double_int |

1011 | double_int::mod (double_int b, bool uns, unsigned code) const |

1012 | { |

1013 | double_int mod; |

1014 | |

1015 | this->divmod (b, uns, code, &mod); |

1016 | return mod; |

1017 | } |

1018 | |

1019 | /* The same as double_int::mod with UNS = false. */ |

1020 | |

1021 | double_int |

1022 | double_int::smod (double_int b, unsigned code) const |

1023 | { |

1024 | return this->mod (b, false, code); |

1025 | } |

1026 | |

1027 | /* The same as double_int::mod with UNS = true. */ |

1028 | |

1029 | double_int |

1030 | double_int::umod (double_int b, unsigned code) const |

1031 | { |

1032 | return this->mod (b, true, code); |

1033 | } |

1034 | |

1035 | /* Return TRUE iff PRODUCT is an integral multiple of FACTOR, and return |

1036 | the multiple in *MULTIPLE. Otherwise return FALSE and leave *MULTIPLE |

1037 | unchanged. */ |

1038 | |

1039 | bool |

1040 | double_int::multiple_of (double_int factor, |

1041 | bool unsigned_p, double_int *multiple) const |

1042 | { |

1043 | double_int remainder; |

1044 | double_int quotient = this->divmod (factor, unsigned_p, |

1045 | TRUNC_DIV_EXPR, &remainder); |

1046 | if (remainder.is_zero ()) |

1047 | { |

1048 | *multiple = quotient; |

1049 | return true; |

1050 | } |

1051 | |

1052 | return false; |

1053 | } |

1054 | |

1055 | /* Set BITPOS bit in A. */ |

1056 | double_int |

1057 | double_int::set_bit (unsigned bitpos) const |

1058 | { |

1059 | double_int a = *this; |

1060 | if (bitpos < HOST_BITS_PER_WIDE_INT) |

1061 | a.low |= HOST_WIDE_INT_1U << bitpos; |

1062 | else |

1063 | a.high |= HOST_WIDE_INT_1 << (bitpos - HOST_BITS_PER_WIDE_INT); |

1064 | |

1065 | return a; |

1066 | } |

1067 | |

1068 | /* Count trailing zeros in A. */ |

1069 | int |

1070 | double_int::trailing_zeros () const |

1071 | { |

1072 | const double_int &a = *this; |

1073 | unsigned HOST_WIDE_INT w = a.low ? a.low : (unsigned HOST_WIDE_INT) a.high; |

1074 | unsigned bits = a.low ? 0 : HOST_BITS_PER_WIDE_INT; |

1075 | if (!w) |

1076 | return HOST_BITS_PER_DOUBLE_INT; |

1077 | bits += ctz_hwi (w); |

1078 | return bits; |

1079 | } |

1080 | |

1081 | /* Shift A left by COUNT places. */ |

1082 | |

1083 | double_int |

1084 | double_int::lshift (HOST_WIDE_INT count) const |

1085 | { |

1086 | double_int ret; |

1087 | |

1088 | gcc_checking_assert (count >= 0); |

1089 | |

1090 | if (count >= HOST_BITS_PER_DOUBLE_INT) |

1091 | { |

1092 | /* Shifting by the host word size is undefined according to the |

1093 | ANSI standard, so we must handle this as a special case. */ |

1094 | ret.high = 0; |

1095 | ret.low = 0; |

1096 | } |

1097 | else if (count >= HOST_BITS_PER_WIDE_INT) |

1098 | { |

1099 | ret.high = low << (count - HOST_BITS_PER_WIDE_INT); |

1100 | ret.low = 0; |

1101 | } |

1102 | else |

1103 | { |

1104 | ret.high = (((unsigned HOST_WIDE_INT) high << count) |

1105 | | (low >> (HOST_BITS_PER_WIDE_INT - count - 1) >> 1)); |

1106 | ret.low = low << count; |

1107 | } |

1108 | |

1109 | return ret; |

1110 | } |

1111 | |

1112 | /* Shift A right by COUNT places. */ |

1113 | |

1114 | double_int |

1115 | double_int::rshift (HOST_WIDE_INT count) const |

1116 | { |

1117 | double_int ret; |

1118 | |

1119 | gcc_checking_assert (count >= 0); |

1120 | |

1121 | if (count >= HOST_BITS_PER_DOUBLE_INT) |

1122 | { |

1123 | /* Shifting by the host word size is undefined according to the |

1124 | ANSI standard, so we must handle this as a special case. */ |

1125 | ret.high = 0; |

1126 | ret.low = 0; |

1127 | } |

1128 | else if (count >= HOST_BITS_PER_WIDE_INT) |

1129 | { |

1130 | ret.high = 0; |

1131 | ret.low |

1132 | = (unsigned HOST_WIDE_INT) (high >> (count - HOST_BITS_PER_WIDE_INT)); |

1133 | } |

1134 | else |

1135 | { |

1136 | ret.high = high >> count; |

1137 | ret.low = ((low >> count) |

1138 | | ((unsigned HOST_WIDE_INT) high |

1139 | << (HOST_BITS_PER_WIDE_INT - count - 1) << 1)); |

1140 | } |

1141 | |

1142 | return ret; |

1143 | } |

1144 | |

1145 | /* Shift A left by COUNT places keeping only PREC bits of result. Shift |

1146 | right if COUNT is negative. ARITH true specifies arithmetic shifting; |

1147 | otherwise use logical shift. */ |

1148 | |

1149 | double_int |

1150 | double_int::lshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const |

1151 | { |

1152 | double_int ret; |

1153 | if (count > 0) |

1154 | lshift_double (low, high, count, prec, &ret.low, &ret.high); |

1155 | else |

1156 | rshift_double (low, high, absu_hwi (count), prec, &ret.low, &ret.high, arith); |

1157 | return ret; |

1158 | } |

1159 | |

1160 | /* Shift A right by COUNT places keeping only PREC bits of result. Shift |

1161 | left if COUNT is negative. ARITH true specifies arithmetic shifting; |

1162 | otherwise use logical shift. */ |

1163 | |

1164 | double_int |

1165 | double_int::rshift (HOST_WIDE_INT count, unsigned int prec, bool arith) const |

1166 | { |

1167 | double_int ret; |

1168 | if (count > 0) |

1169 | rshift_double (low, high, count, prec, &ret.low, &ret.high, arith); |

1170 | else |

1171 | lshift_double (low, high, absu_hwi (count), prec, &ret.low, &ret.high); |

1172 | return ret; |

1173 | } |

1174 | |

1175 | /* Arithmetic shift A left by COUNT places keeping only PREC bits of result. |

1176 | Shift right if COUNT is negative. */ |

1177 | |

1178 | double_int |

1179 | double_int::alshift (HOST_WIDE_INT count, unsigned int prec) const |

1180 | { |

1181 | double_int r; |

1182 | if (count > 0) |

1183 | lshift_double (low, high, count, prec, &r.low, &r.high); |

1184 | else |

1185 | rshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high, true); |

1186 | return r; |

1187 | } |

1188 | |

1189 | /* Arithmetic shift A right by COUNT places keeping only PREC bits of result. |

1190 | Shift left if COUNT is negative. */ |

1191 | |

1192 | double_int |

1193 | double_int::arshift (HOST_WIDE_INT count, unsigned int prec) const |

1194 | { |

1195 | double_int r; |

1196 | if (count > 0) |

1197 | rshift_double (low, high, count, prec, &r.low, &r.high, true); |

1198 | else |

1199 | lshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high); |

1200 | return r; |

1201 | } |

1202 | |

1203 | /* Logical shift A left by COUNT places keeping only PREC bits of result. |

1204 | Shift right if COUNT is negative. */ |

1205 | |

1206 | double_int |

1207 | double_int::llshift (HOST_WIDE_INT count, unsigned int prec) const |

1208 | { |

1209 | double_int r; |

1210 | if (count > 0) |

1211 | lshift_double (low, high, count, prec, &r.low, &r.high); |

1212 | else |

1213 | rshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high, false); |

1214 | return r; |

1215 | } |

1216 | |

1217 | /* Logical shift A right by COUNT places keeping only PREC bits of result. |

1218 | Shift left if COUNT is negative. */ |

1219 | |

1220 | double_int |

1221 | double_int::lrshift (HOST_WIDE_INT count, unsigned int prec) const |

1222 | { |

1223 | double_int r; |

1224 | if (count > 0) |

1225 | rshift_double (low, high, count, prec, &r.low, &r.high, false); |

1226 | else |

1227 | lshift_double (low, high, absu_hwi (count), prec, &r.low, &r.high); |

1228 | return r; |

1229 | } |

1230 | |

1231 | /* Rotate A left by COUNT places keeping only PREC bits of result. |

1232 | Rotate right if COUNT is negative. */ |

1233 | |

1234 | double_int |

1235 | double_int::lrotate (HOST_WIDE_INT count, unsigned int prec) const |

1236 | { |

1237 | double_int t1, t2; |

1238 | |

1239 | count %= prec; |

1240 | if (count < 0) |

1241 | count += prec; |

1242 | |

1243 | t1 = this->llshift (count, prec); |

1244 | t2 = this->lrshift (prec - count, prec); |

1245 | |

1246 | return t1 | t2; |

1247 | } |

1248 | |

1249 | /* Rotate A rigth by COUNT places keeping only PREC bits of result. |

1250 | Rotate right if COUNT is negative. */ |

1251 | |

1252 | double_int |

1253 | double_int::rrotate (HOST_WIDE_INT count, unsigned int prec) const |

1254 | { |

1255 | double_int t1, t2; |

1256 | |

1257 | count %= prec; |

1258 | if (count < 0) |

1259 | count += prec; |

1260 | |

1261 | t1 = this->lrshift (count, prec); |

1262 | t2 = this->llshift (prec - count, prec); |

1263 | |

1264 | return t1 | t2; |

1265 | } |

1266 | |

1267 | /* Returns -1 if A < B, 0 if A == B and 1 if A > B. Signedness of the |

1268 | comparison is given by UNS. */ |

1269 | |

1270 | int |

1271 | double_int::cmp (double_int b, bool uns) const |

1272 | { |

1273 | if (uns) |

1274 | return this->ucmp (b); |

1275 | else |

1276 | return this->scmp (b); |

1277 | } |

1278 | |

1279 | /* Compares two unsigned values A and B. Returns -1 if A < B, 0 if A == B, |

1280 | and 1 if A > B. */ |

1281 | |

1282 | int |

1283 | double_int::ucmp (double_int b) const |

1284 | { |

1285 | const double_int &a = *this; |

1286 | if ((unsigned HOST_WIDE_INT) a.high < (unsigned HOST_WIDE_INT) b.high) |

1287 | return -1; |

1288 | if ((unsigned HOST_WIDE_INT) a.high > (unsigned HOST_WIDE_INT) b.high) |

1289 | return 1; |

1290 | if (a.low < b.low) |

1291 | return -1; |

1292 | if (a.low > b.low) |

1293 | return 1; |

1294 | |

1295 | return 0; |

1296 | } |

1297 | |

1298 | /* Compares two signed values A and B. Returns -1 if A < B, 0 if A == B, |

1299 | and 1 if A > B. */ |

1300 | |

1301 | int |

1302 | double_int::scmp (double_int b) const |

1303 | { |

1304 | const double_int &a = *this; |

1305 | if (a.high < b.high) |

1306 | return -1; |

1307 | if (a.high > b.high) |

1308 | return 1; |

1309 | if (a.low < b.low) |

1310 | return -1; |

1311 | if (a.low > b.low) |

1312 | return 1; |

1313 | |

1314 | return 0; |

1315 | } |

1316 | |

1317 | /* Compares two unsigned values A and B for less-than. */ |

1318 | |

1319 | bool |

1320 | double_int::ult (double_int b) const |

1321 | { |

1322 | if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high) |

1323 | return true; |

1324 | if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high) |

1325 | return false; |

1326 | if (low < b.low) |

1327 | return true; |

1328 | return false; |

1329 | } |

1330 | |

1331 | /* Compares two unsigned values A and B for less-than or equal-to. */ |

1332 | |

1333 | bool |

1334 | double_int::ule (double_int b) const |

1335 | { |

1336 | if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high) |

1337 | return true; |

1338 | if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high) |

1339 | return false; |

1340 | if (low <= b.low) |

1341 | return true; |

1342 | return false; |

1343 | } |

1344 | |

1345 | /* Compares two unsigned values A and B for greater-than. */ |

1346 | |

1347 | bool |

1348 | double_int::ugt (double_int b) const |

1349 | { |

1350 | if ((unsigned HOST_WIDE_INT) high > (unsigned HOST_WIDE_INT) b.high) |

1351 | return true; |

1352 | if ((unsigned HOST_WIDE_INT) high < (unsigned HOST_WIDE_INT) b.high) |

1353 | return false; |

1354 | if (low > b.low) |

1355 | return true; |

1356 | return false; |

1357 | } |

1358 | |

1359 | /* Compares two signed values A and B for less-than. */ |

1360 | |

1361 | bool |

1362 | double_int::slt (double_int b) const |

1363 | { |

1364 | if (high < b.high) |

1365 | return true; |

1366 | if (high > b.high) |

1367 | return false; |

1368 | if (low < b.low) |

1369 | return true; |

1370 | return false; |

1371 | } |

1372 | |

1373 | /* Compares two signed values A and B for less-than or equal-to. */ |

1374 | |

1375 | bool |

1376 | double_int::sle (double_int b) const |

1377 | { |

1378 | if (high < b.high) |

1379 | return true; |

1380 | if (high > b.high) |

1381 | return false; |

1382 | if (low <= b.low) |

1383 | return true; |

1384 | return false; |

1385 | } |

1386 | |

1387 | /* Compares two signed values A and B for greater-than. */ |

1388 | |

1389 | bool |

1390 | double_int::sgt (double_int b) const |

1391 | { |

1392 | if (high > b.high) |

1393 | return true; |

1394 | if (high < b.high) |

1395 | return false; |

1396 | if (low > b.low) |

1397 | return true; |

1398 | return false; |

1399 | } |

1400 | |

1401 | |

1402 | /* Compares two values A and B. Returns max value. Signedness of the |

1403 | comparison is given by UNS. */ |

1404 | |

1405 | double_int |

1406 | double_int::max (double_int b, bool uns) |

1407 | { |

1408 | return (this->cmp (b, uns) == 1) ? *this : b; |

1409 | } |

1410 | |

1411 | /* Compares two signed values A and B. Returns max value. */ |

1412 | |

1413 | double_int |

1414 | double_int::smax (double_int b) |

1415 | { |

1416 | return (this->scmp (b) == 1) ? *this : b; |

1417 | } |

1418 | |

1419 | /* Compares two unsigned values A and B. Returns max value. */ |

1420 | |

1421 | double_int |

1422 | double_int::umax (double_int b) |

1423 | { |

1424 | return (this->ucmp (b) == 1) ? *this : b; |

1425 | } |

1426 | |

1427 | /* Compares two values A and B. Returns mix value. Signedness of the |

1428 | comparison is given by UNS. */ |

1429 | |

1430 | double_int |

1431 | double_int::min (double_int b, bool uns) |

1432 | { |

1433 | return (this->cmp (b, uns) == -1) ? *this : b; |

1434 | } |

1435 | |

1436 | /* Compares two signed values A and B. Returns min value. */ |

1437 | |

1438 | double_int |

1439 | double_int::smin (double_int b) |

1440 | { |

1441 | return (this->scmp (b) == -1) ? *this : b; |

1442 | } |

1443 | |

1444 | /* Compares two unsigned values A and B. Returns min value. */ |

1445 | |

1446 | double_int |

1447 | double_int::umin (double_int b) |

1448 | { |

1449 | return (this->ucmp (b) == -1) ? *this : b; |

1450 | } |

1451 | |

1452 | /* Splits last digit of *CST (taken as unsigned) in BASE and returns it. */ |

1453 | |

1454 | static unsigned |

1455 | double_int_split_digit (double_int *cst, unsigned base) |

1456 | { |

1457 | unsigned HOST_WIDE_INT resl, reml; |

1458 | HOST_WIDE_INT resh, remh; |

1459 | |

1460 | div_and_round_double (FLOOR_DIV_EXPR, true, cst->low, cst->high, base, 0, |

1461 | &resl, &resh, &reml, &remh); |

1462 | cst->high = resh; |

1463 | cst->low = resl; |

1464 | |

1465 | return reml; |

1466 | } |

1467 | |

1468 | /* Dumps CST to FILE. If UNS is true, CST is considered to be unsigned, |

1469 | otherwise it is signed. */ |

1470 | |

1471 | void |

1472 | dump_double_int (FILE *file, double_int cst, bool uns) |

1473 | { |

1474 | unsigned digits[100], n; |

1475 | int i; |

1476 | |

1477 | if (cst.is_zero ()) |

1478 | { |

1479 | fprintf (file, "0"); |

1480 | return; |

1481 | } |

1482 | |

1483 | if (!uns && cst.is_negative ()) |

1484 | { |

1485 | fprintf (file, "-"); |

1486 | cst = -cst; |

1487 | } |

1488 | |

1489 | for (n = 0; !cst.is_zero (); n++) |

1490 | digits[n] = double_int_split_digit (&cst, 10); |

1491 | for (i = n - 1; i >= 0; i--) |

1492 | fprintf (file, "%u", digits[i]); |

1493 | } |

1494 | |

1495 | |

1496 | /* Sets RESULT to VAL, taken unsigned if UNS is true and as signed |

1497 | otherwise. */ |

1498 | |

1499 | void |

1500 | mpz_set_double_int (mpz_t result, double_int val, bool uns) |

1501 | { |

1502 | bool negate = false; |

1503 | unsigned HOST_WIDE_INT vp[2]; |

1504 | |

1505 | if (!uns && val.is_negative ()) |

1506 | { |

1507 | negate = true; |

1508 | val = -val; |

1509 | } |

1510 | |

1511 | vp[0] = val.low; |

1512 | vp[1] = (unsigned HOST_WIDE_INT) val.high; |

1513 | mpz_import (result, 2, -1, sizeof (HOST_WIDE_INT), 0, 0, vp); |

1514 | |

1515 | if (negate) |

1516 | mpz_neg (result, result); |

1517 | } |

1518 | |

1519 | /* Returns VAL converted to TYPE. If WRAP is true, then out-of-range |

1520 | values of VAL will be wrapped; otherwise, they will be set to the |

1521 | appropriate minimum or maximum TYPE bound. */ |

1522 | |

1523 | double_int |

1524 | mpz_get_double_int (const_tree type, mpz_t val, bool wrap) |

1525 | { |

1526 | unsigned HOST_WIDE_INT *vp; |

1527 | size_t count, numb; |

1528 | double_int res; |

1529 | |

1530 | if (!wrap) |

1531 | { |

1532 | mpz_t min, max; |

1533 | |

1534 | mpz_init (min); |

1535 | mpz_init (max); |

1536 | get_type_static_bounds (type, min, max); |

1537 | |

1538 | if (mpz_cmp (val, min) < 0) |

1539 | mpz_set (val, min); |

1540 | else if (mpz_cmp (val, max) > 0) |

1541 | mpz_set (val, max); |

1542 | |

1543 | mpz_clear (min); |

1544 | mpz_clear (max); |

1545 | } |

1546 | |

1547 | /* Determine the number of unsigned HOST_WIDE_INT that are required |

1548 | for representing the value. The code to calculate count is |

1549 | extracted from the GMP manual, section "Integer Import and Export": |

1550 | http://gmplib.org/manual/Integer-Import-and-Export.html */ |

1551 | numb = 8 * sizeof (HOST_WIDE_INT); |

1552 | count = (mpz_sizeinbase (val, 2) + numb-1) / numb; |

1553 | if (count < 2) |

1554 | count = 2; |

1555 | vp = (unsigned HOST_WIDE_INT *) alloca (count * sizeof (HOST_WIDE_INT)); |

1556 | |

1557 | vp[0] = 0; |

1558 | vp[1] = 0; |

1559 | mpz_export (vp, &count, -1, sizeof (HOST_WIDE_INT), 0, 0, val); |

1560 | |

1561 | gcc_assert (wrap || count <= 2); |

1562 | |

1563 | res.low = vp[0]; |

1564 | res.high = (HOST_WIDE_INT) vp[1]; |

1565 | |

1566 | res = res.ext (TYPE_PRECISION (type), TYPE_UNSIGNED (type)); |

1567 | if (mpz_sgn (val) < 0) |

1568 | res = -res; |

1569 | |

1570 | return res; |

1571 | } |

1572 |