1 | /* Operations with affine combinations of trees. |
---|---|

2 | Copyright (C) 2005-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 "backend.h" |

24 | #include "rtl.h" |

25 | #include "tree.h" |

26 | #include "gimple.h" |

27 | #include "ssa.h" |

28 | #include "tree-pretty-print.h" |

29 | #include "fold-const.h" |

30 | #include "tree-affine.h" |

31 | #include "gimplify.h" |

32 | #include "dumpfile.h" |

33 | #include "cfgexpand.h" |

34 | |

35 | /* Extends CST as appropriate for the affine combinations COMB. */ |

36 | |

37 | widest_int |

38 | wide_int_ext_for_comb (const widest_int &cst, tree type) |

39 | { |

40 | return wi::sext (cst, TYPE_PRECISION (type)); |

41 | } |

42 | |

43 | /* Initializes affine combination COMB so that its value is zero in TYPE. */ |

44 | |

45 | static void |

46 | aff_combination_zero (aff_tree *comb, tree type) |

47 | { |

48 | int i; |

49 | comb->type = type; |

50 | comb->offset = 0; |

51 | comb->n = 0; |

52 | for (i = 0; i < MAX_AFF_ELTS; i++) |

53 | comb->elts[i].coef = 0; |

54 | comb->rest = NULL_TREE; |

55 | } |

56 | |

57 | /* Sets COMB to CST. */ |

58 | |

59 | void |

60 | aff_combination_const (aff_tree *comb, tree type, const widest_int &cst) |

61 | { |

62 | aff_combination_zero (comb, type); |

63 | comb->offset = wide_int_ext_for_comb (cst, comb->type);; |

64 | } |

65 | |

66 | /* Sets COMB to single element ELT. */ |

67 | |

68 | void |

69 | aff_combination_elt (aff_tree *comb, tree type, tree elt) |

70 | { |

71 | aff_combination_zero (comb, type); |

72 | |

73 | comb->n = 1; |

74 | comb->elts[0].val = elt; |

75 | comb->elts[0].coef = 1; |

76 | } |

77 | |

78 | /* Scales COMB by SCALE. */ |

79 | |

80 | void |

81 | aff_combination_scale (aff_tree *comb, const widest_int &scale_in) |

82 | { |

83 | unsigned i, j; |

84 | |

85 | widest_int scale = wide_int_ext_for_comb (scale_in, comb->type); |

86 | if (scale == 1) |

87 | return; |

88 | |

89 | if (scale == 0) |

90 | { |

91 | aff_combination_zero (comb, comb->type); |

92 | return; |

93 | } |

94 | |

95 | comb->offset = wide_int_ext_for_comb (scale * comb->offset, comb->type); |

96 | for (i = 0, j = 0; i < comb->n; i++) |

97 | { |

98 | widest_int new_coef |

99 | = wide_int_ext_for_comb (scale * comb->elts[i].coef, comb->type); |

100 | /* A coefficient may become zero due to overflow. Remove the zero |

101 | elements. */ |

102 | if (new_coef == 0) |

103 | continue; |

104 | comb->elts[j].coef = new_coef; |

105 | comb->elts[j].val = comb->elts[i].val; |

106 | j++; |

107 | } |

108 | comb->n = j; |

109 | |

110 | if (comb->rest) |

111 | { |

112 | tree type = comb->type; |

113 | if (POINTER_TYPE_P (type)) |

114 | type = sizetype; |

115 | if (comb->n < MAX_AFF_ELTS) |

116 | { |

117 | comb->elts[comb->n].coef = scale; |

118 | comb->elts[comb->n].val = comb->rest; |

119 | comb->rest = NULL_TREE; |

120 | comb->n++; |

121 | } |

122 | else |

123 | comb->rest = fold_build2 (MULT_EXPR, type, comb->rest, |

124 | wide_int_to_tree (type, scale)); |

125 | } |

126 | } |

127 | |

128 | /* Adds ELT * SCALE to COMB. */ |

129 | |

130 | void |

131 | aff_combination_add_elt (aff_tree *comb, tree elt, const widest_int &scale_in) |

132 | { |

133 | unsigned i; |

134 | tree type; |

135 | |

136 | widest_int scale = wide_int_ext_for_comb (scale_in, comb->type); |

137 | if (scale == 0) |

138 | return; |

139 | |

140 | for (i = 0; i < comb->n; i++) |

141 | if (operand_equal_p (comb->elts[i].val, elt, 0)) |

142 | { |

143 | widest_int new_coef |

144 | = wide_int_ext_for_comb (comb->elts[i].coef + scale, comb->type); |

145 | if (new_coef != 0) |

146 | { |

147 | comb->elts[i].coef = new_coef; |

148 | return; |

149 | } |

150 | |

151 | comb->n--; |

152 | comb->elts[i] = comb->elts[comb->n]; |

153 | |

154 | if (comb->rest) |

155 | { |

156 | gcc_assert (comb->n == MAX_AFF_ELTS - 1); |

157 | comb->elts[comb->n].coef = 1; |

158 | comb->elts[comb->n].val = comb->rest; |

159 | comb->rest = NULL_TREE; |

160 | comb->n++; |

161 | } |

162 | return; |

163 | } |

164 | if (comb->n < MAX_AFF_ELTS) |

165 | { |

166 | comb->elts[comb->n].coef = scale; |

167 | comb->elts[comb->n].val = elt; |

168 | comb->n++; |

169 | return; |

170 | } |

171 | |

172 | type = comb->type; |

173 | if (POINTER_TYPE_P (type)) |

174 | type = sizetype; |

175 | |

176 | if (scale == 1) |

177 | elt = fold_convert (type, elt); |

178 | else |

179 | elt = fold_build2 (MULT_EXPR, type, |

180 | fold_convert (type, elt), |

181 | wide_int_to_tree (type, scale)); |

182 | |

183 | if (comb->rest) |

184 | comb->rest = fold_build2 (PLUS_EXPR, type, comb->rest, |

185 | elt); |

186 | else |

187 | comb->rest = elt; |

188 | } |

189 | |

190 | /* Adds CST to C. */ |

191 | |

192 | static void |

193 | aff_combination_add_cst (aff_tree *c, const widest_int &cst) |

194 | { |

195 | c->offset = wide_int_ext_for_comb (c->offset + cst, c->type); |

196 | } |

197 | |

198 | /* Adds COMB2 to COMB1. */ |

199 | |

200 | void |

201 | aff_combination_add (aff_tree *comb1, aff_tree *comb2) |

202 | { |

203 | unsigned i; |

204 | |

205 | aff_combination_add_cst (comb1, comb2->offset); |

206 | for (i = 0; i < comb2->n; i++) |

207 | aff_combination_add_elt (comb1, comb2->elts[i].val, comb2->elts[i].coef); |

208 | if (comb2->rest) |

209 | aff_combination_add_elt (comb1, comb2->rest, 1); |

210 | } |

211 | |

212 | /* Converts affine combination COMB to TYPE. */ |

213 | |

214 | void |

215 | aff_combination_convert (aff_tree *comb, tree type) |

216 | { |

217 | unsigned i, j; |

218 | tree comb_type = comb->type; |

219 | |

220 | if (TYPE_PRECISION (type) > TYPE_PRECISION (comb_type)) |

221 | { |

222 | tree val = fold_convert (type, aff_combination_to_tree (comb)); |

223 | tree_to_aff_combination (val, type, comb); |

224 | return; |

225 | } |

226 | |

227 | comb->type = type; |

228 | if (comb->rest && !POINTER_TYPE_P (type)) |

229 | comb->rest = fold_convert (type, comb->rest); |

230 | |

231 | if (TYPE_PRECISION (type) == TYPE_PRECISION (comb_type)) |

232 | return; |

233 | |

234 | comb->offset = wide_int_ext_for_comb (comb->offset, comb->type); |

235 | for (i = j = 0; i < comb->n; i++) |

236 | { |

237 | if (comb->elts[i].coef == 0) |

238 | continue; |

239 | comb->elts[j].coef = comb->elts[i].coef; |

240 | comb->elts[j].val = fold_convert (type, comb->elts[i].val); |

241 | j++; |

242 | } |

243 | |

244 | comb->n = j; |

245 | if (comb->n < MAX_AFF_ELTS && comb->rest) |

246 | { |

247 | comb->elts[comb->n].coef = 1; |

248 | comb->elts[comb->n].val = comb->rest; |

249 | comb->rest = NULL_TREE; |

250 | comb->n++; |

251 | } |

252 | } |

253 | |

254 | /* Splits EXPR into an affine combination of parts. */ |

255 | |

256 | void |

257 | tree_to_aff_combination (tree expr, tree type, aff_tree *comb) |

258 | { |

259 | aff_tree tmp; |

260 | enum tree_code code; |

261 | tree cst, core, toffset; |

262 | HOST_WIDE_INT bitpos, bitsize; |

263 | machine_mode mode; |

264 | int unsignedp, reversep, volatilep; |

265 | |

266 | STRIP_NOPS (expr); |

267 | |

268 | code = TREE_CODE (expr); |

269 | switch (code) |

270 | { |

271 | case INTEGER_CST: |

272 | aff_combination_const (comb, type, wi::to_widest (expr)); |

273 | return; |

274 | |

275 | case POINTER_PLUS_EXPR: |

276 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

277 | tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); |

278 | aff_combination_add (comb, &tmp); |

279 | return; |

280 | |

281 | case PLUS_EXPR: |

282 | case MINUS_EXPR: |

283 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

284 | tree_to_aff_combination (TREE_OPERAND (expr, 1), type, &tmp); |

285 | if (code == MINUS_EXPR) |

286 | aff_combination_scale (&tmp, -1); |

287 | aff_combination_add (comb, &tmp); |

288 | return; |

289 | |

290 | case MULT_EXPR: |

291 | cst = TREE_OPERAND (expr, 1); |

292 | if (TREE_CODE (cst) != INTEGER_CST) |

293 | break; |

294 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

295 | aff_combination_scale (comb, wi::to_widest (cst)); |

296 | return; |

297 | |

298 | case NEGATE_EXPR: |

299 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

300 | aff_combination_scale (comb, -1); |

301 | return; |

302 | |

303 | case BIT_NOT_EXPR: |

304 | /* ~x = -x - 1 */ |

305 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

306 | aff_combination_scale (comb, -1); |

307 | aff_combination_add_cst (comb, -1); |

308 | return; |

309 | |

310 | case ADDR_EXPR: |

311 | /* Handle &MEM[ptr + CST] which is equivalent to POINTER_PLUS_EXPR. */ |

312 | if (TREE_CODE (TREE_OPERAND (expr, 0)) == MEM_REF) |

313 | { |

314 | expr = TREE_OPERAND (expr, 0); |

315 | tree_to_aff_combination (TREE_OPERAND (expr, 0), type, comb); |

316 | tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); |

317 | aff_combination_add (comb, &tmp); |

318 | return; |

319 | } |

320 | core = get_inner_reference (TREE_OPERAND (expr, 0), &bitsize, &bitpos, |

321 | &toffset, &mode, &unsignedp, &reversep, |

322 | &volatilep); |

323 | if (bitpos % BITS_PER_UNIT != 0) |

324 | break; |

325 | aff_combination_const (comb, type, bitpos / BITS_PER_UNIT); |

326 | if (TREE_CODE (core) == MEM_REF) |

327 | { |

328 | aff_combination_add_cst (comb, wi::to_widest (TREE_OPERAND (core, 1))); |

329 | core = TREE_OPERAND (core, 0); |

330 | } |

331 | else |

332 | core = build_fold_addr_expr (core); |

333 | |

334 | if (TREE_CODE (core) == ADDR_EXPR) |

335 | aff_combination_add_elt (comb, core, 1); |

336 | else |

337 | { |

338 | tree_to_aff_combination (core, type, &tmp); |

339 | aff_combination_add (comb, &tmp); |

340 | } |

341 | if (toffset) |

342 | { |

343 | tree_to_aff_combination (toffset, type, &tmp); |

344 | aff_combination_add (comb, &tmp); |

345 | } |

346 | return; |

347 | |

348 | case MEM_REF: |

349 | if (TREE_CODE (TREE_OPERAND (expr, 0)) == ADDR_EXPR) |

350 | tree_to_aff_combination (TREE_OPERAND (TREE_OPERAND (expr, 0), 0), |

351 | type, comb); |

352 | else if (integer_zerop (TREE_OPERAND (expr, 1))) |

353 | { |

354 | aff_combination_elt (comb, type, expr); |

355 | return; |

356 | } |

357 | else |

358 | aff_combination_elt (comb, type, |

359 | build2 (MEM_REF, TREE_TYPE (expr), |

360 | TREE_OPERAND (expr, 0), |

361 | build_int_cst |

362 | (TREE_TYPE (TREE_OPERAND (expr, 1)), 0))); |

363 | tree_to_aff_combination (TREE_OPERAND (expr, 1), sizetype, &tmp); |

364 | aff_combination_add (comb, &tmp); |

365 | return; |

366 | |

367 | CASE_CONVERT: |

368 | { |

369 | tree otype = TREE_TYPE (expr); |

370 | tree inner = TREE_OPERAND (expr, 0); |

371 | tree itype = TREE_TYPE (inner); |

372 | enum tree_code icode = TREE_CODE (inner); |

373 | |

374 | /* In principle this is a valid folding, but it isn't necessarily |

375 | an optimization, so do it here and not in fold_unary. */ |

376 | if ((icode == PLUS_EXPR || icode == MINUS_EXPR || icode == MULT_EXPR) |

377 | && TREE_CODE (itype) == INTEGER_TYPE |

378 | && TREE_CODE (otype) == INTEGER_TYPE |

379 | && TYPE_PRECISION (otype) > TYPE_PRECISION (itype)) |

380 | { |

381 | tree op0 = TREE_OPERAND (inner, 0), op1 = TREE_OPERAND (inner, 1); |

382 | |

383 | /* If inner type has undefined overflow behavior, fold conversion |

384 | for below two cases: |

385 | (T1)(X *+- CST) -> (T1)X *+- (T1)CST |

386 | (T1)(X + X) -> (T1)X + (T1)X. */ |

387 | if (TYPE_OVERFLOW_UNDEFINED (itype) |

388 | && (TREE_CODE (op1) == INTEGER_CST |

389 | || (icode == PLUS_EXPR && operand_equal_p (op0, op1, 0)))) |

390 | { |

391 | op0 = fold_convert (otype, op0); |

392 | op1 = fold_convert (otype, op1); |

393 | expr = fold_build2 (icode, otype, op0, op1); |

394 | tree_to_aff_combination (expr, type, comb); |

395 | return; |

396 | } |

397 | wide_int minv, maxv; |

398 | /* If inner type has wrapping overflow behavior, fold conversion |

399 | for below case: |

400 | (T1)(X - CST) -> (T1)X - (T1)CST |

401 | if X - CST doesn't overflow by range information. Also handle |

402 | (T1)(X + CST) as (T1)(X - (-CST)). */ |

403 | if (TYPE_UNSIGNED (itype) |

404 | && TYPE_OVERFLOW_WRAPS (itype) |

405 | && TREE_CODE (op0) == SSA_NAME |

406 | && TREE_CODE (op1) == INTEGER_CST |

407 | && icode != MULT_EXPR |

408 | && get_range_info (op0, &minv, &maxv) == VR_RANGE) |

409 | { |

410 | if (icode == PLUS_EXPR) |

411 | op1 = wide_int_to_tree (itype, -wi::to_wide (op1)); |

412 | if (wi::geu_p (minv, wi::to_wide (op1))) |

413 | { |

414 | op0 = fold_convert (otype, op0); |

415 | op1 = fold_convert (otype, op1); |

416 | expr = fold_build2 (MINUS_EXPR, otype, op0, op1); |

417 | tree_to_aff_combination (expr, type, comb); |

418 | return; |

419 | } |

420 | } |

421 | } |

422 | } |

423 | break; |

424 | |

425 | default: |

426 | break; |

427 | } |

428 | |

429 | aff_combination_elt (comb, type, expr); |

430 | } |

431 | |

432 | /* Creates EXPR + ELT * SCALE in TYPE. EXPR is taken from affine |

433 | combination COMB. */ |

434 | |

435 | static tree |

436 | add_elt_to_tree (tree expr, tree type, tree elt, const widest_int &scale_in) |

437 | { |

438 | enum tree_code code; |

439 | |

440 | widest_int scale = wide_int_ext_for_comb (scale_in, type); |

441 | |

442 | elt = fold_convert (type, elt); |

443 | if (scale == 1) |

444 | { |

445 | if (!expr) |

446 | return elt; |

447 | |

448 | return fold_build2 (PLUS_EXPR, type, expr, elt); |

449 | } |

450 | |

451 | if (scale == -1) |

452 | { |

453 | if (!expr) |

454 | return fold_build1 (NEGATE_EXPR, type, elt); |

455 | |

456 | return fold_build2 (MINUS_EXPR, type, expr, elt); |

457 | } |

458 | |

459 | if (!expr) |

460 | return fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); |

461 | |

462 | if (wi::neg_p (scale)) |

463 | { |

464 | code = MINUS_EXPR; |

465 | scale = -scale; |

466 | } |

467 | else |

468 | code = PLUS_EXPR; |

469 | |

470 | elt = fold_build2 (MULT_EXPR, type, elt, wide_int_to_tree (type, scale)); |

471 | return fold_build2 (code, type, expr, elt); |

472 | } |

473 | |

474 | /* Makes tree from the affine combination COMB. */ |

475 | |

476 | tree |

477 | aff_combination_to_tree (aff_tree *comb) |

478 | { |

479 | tree type = comb->type, base = NULL_TREE, expr = NULL_TREE; |

480 | unsigned i; |

481 | widest_int off, sgn; |

482 | |

483 | gcc_assert (comb->n == MAX_AFF_ELTS || comb->rest == NULL_TREE); |

484 | |

485 | i = 0; |

486 | if (POINTER_TYPE_P (type)) |

487 | { |

488 | type = sizetype; |

489 | if (comb->n > 0 && comb->elts[0].coef == 1 |

490 | && POINTER_TYPE_P (TREE_TYPE (comb->elts[0].val))) |

491 | { |

492 | base = comb->elts[0].val; |

493 | ++i; |

494 | } |

495 | } |

496 | |

497 | for (; i < comb->n; i++) |

498 | expr = add_elt_to_tree (expr, type, comb->elts[i].val, comb->elts[i].coef); |

499 | |

500 | if (comb->rest) |

501 | expr = add_elt_to_tree (expr, type, comb->rest, 1); |

502 | |

503 | /* Ensure that we get x - 1, not x + (-1) or x + 0xff..f if x is |

504 | unsigned. */ |

505 | if (wi::neg_p (comb->offset)) |

506 | { |

507 | off = -comb->offset; |

508 | sgn = -1; |

509 | } |

510 | else |

511 | { |

512 | off = comb->offset; |

513 | sgn = 1; |

514 | } |

515 | expr = add_elt_to_tree (expr, type, wide_int_to_tree (type, off), sgn); |

516 | |

517 | if (base) |

518 | return fold_build_pointer_plus (base, expr); |

519 | else |

520 | return fold_convert (comb->type, expr); |

521 | } |

522 | |

523 | /* Copies the tree elements of COMB to ensure that they are not shared. */ |

524 | |

525 | void |

526 | unshare_aff_combination (aff_tree *comb) |

527 | { |

528 | unsigned i; |

529 | |

530 | for (i = 0; i < comb->n; i++) |

531 | comb->elts[i].val = unshare_expr (comb->elts[i].val); |

532 | if (comb->rest) |

533 | comb->rest = unshare_expr (comb->rest); |

534 | } |

535 | |

536 | /* Remove M-th element from COMB. */ |

537 | |

538 | void |

539 | aff_combination_remove_elt (aff_tree *comb, unsigned m) |

540 | { |

541 | comb->n--; |

542 | if (m <= comb->n) |

543 | comb->elts[m] = comb->elts[comb->n]; |

544 | if (comb->rest) |

545 | { |

546 | comb->elts[comb->n].coef = 1; |

547 | comb->elts[comb->n].val = comb->rest; |

548 | comb->rest = NULL_TREE; |

549 | comb->n++; |

550 | } |

551 | } |

552 | |

553 | /* Adds C * COEF * VAL to R. VAL may be NULL, in that case only |

554 | C * COEF is added to R. */ |

555 | |

556 | |

557 | static void |

558 | aff_combination_add_product (aff_tree *c, const widest_int &coef, tree val, |

559 | aff_tree *r) |

560 | { |

561 | unsigned i; |

562 | tree aval, type; |

563 | |

564 | for (i = 0; i < c->n; i++) |

565 | { |

566 | aval = c->elts[i].val; |

567 | if (val) |

568 | { |

569 | type = TREE_TYPE (aval); |

570 | aval = fold_build2 (MULT_EXPR, type, aval, |

571 | fold_convert (type, val)); |

572 | } |

573 | |

574 | aff_combination_add_elt (r, aval, coef * c->elts[i].coef); |

575 | } |

576 | |

577 | if (c->rest) |

578 | { |

579 | aval = c->rest; |

580 | if (val) |

581 | { |

582 | type = TREE_TYPE (aval); |

583 | aval = fold_build2 (MULT_EXPR, type, aval, |

584 | fold_convert (type, val)); |

585 | } |

586 | |

587 | aff_combination_add_elt (r, aval, coef); |

588 | } |

589 | |

590 | if (val) |

591 | aff_combination_add_elt (r, val, coef * c->offset); |

592 | else |

593 | aff_combination_add_cst (r, coef * c->offset); |

594 | } |

595 | |

596 | /* Multiplies C1 by C2, storing the result to R */ |

597 | |

598 | void |

599 | aff_combination_mult (aff_tree *c1, aff_tree *c2, aff_tree *r) |

600 | { |

601 | unsigned i; |

602 | gcc_assert (TYPE_PRECISION (c1->type) == TYPE_PRECISION (c2->type)); |

603 | |

604 | aff_combination_zero (r, c1->type); |

605 | |

606 | for (i = 0; i < c2->n; i++) |

607 | aff_combination_add_product (c1, c2->elts[i].coef, c2->elts[i].val, r); |

608 | if (c2->rest) |

609 | aff_combination_add_product (c1, 1, c2->rest, r); |

610 | aff_combination_add_product (c1, c2->offset, NULL, r); |

611 | } |

612 | |

613 | /* Returns the element of COMB whose value is VAL, or NULL if no such |

614 | element exists. If IDX is not NULL, it is set to the index of VAL in |

615 | COMB. */ |

616 | |

617 | static struct aff_comb_elt * |

618 | aff_combination_find_elt (aff_tree *comb, tree val, unsigned *idx) |

619 | { |

620 | unsigned i; |

621 | |

622 | for (i = 0; i < comb->n; i++) |

623 | if (operand_equal_p (comb->elts[i].val, val, 0)) |

624 | { |

625 | if (idx) |

626 | *idx = i; |

627 | |

628 | return &comb->elts[i]; |

629 | } |

630 | |

631 | return NULL; |

632 | } |

633 | |

634 | /* Element of the cache that maps ssa name NAME to its expanded form |

635 | as an affine expression EXPANSION. */ |

636 | |

637 | struct name_expansion |

638 | { |

639 | aff_tree expansion; |

640 | |

641 | /* True if the expansion for the name is just being generated. */ |

642 | unsigned in_progress : 1; |

643 | }; |

644 | |

645 | /* Expands SSA names in COMB recursively. CACHE is used to cache the |

646 | results. */ |

647 | |

648 | void |

649 | aff_combination_expand (aff_tree *comb ATTRIBUTE_UNUSED, |

650 | hash_map<tree, name_expansion *> **cache) |

651 | { |

652 | unsigned i; |

653 | aff_tree to_add, current, curre; |

654 | tree e, rhs; |

655 | gimple *def; |

656 | widest_int scale; |

657 | struct name_expansion *exp; |

658 | |

659 | aff_combination_zero (&to_add, comb->type); |

660 | for (i = 0; i < comb->n; i++) |

661 | { |

662 | tree type, name; |

663 | enum tree_code code; |

664 | |

665 | e = comb->elts[i].val; |

666 | type = TREE_TYPE (e); |

667 | name = e; |

668 | /* Look through some conversions. */ |

669 | if (CONVERT_EXPR_P (e) |

670 | && (TYPE_PRECISION (type) |

671 | >= TYPE_PRECISION (TREE_TYPE (TREE_OPERAND (e, 0))))) |

672 | name = TREE_OPERAND (e, 0); |

673 | if (TREE_CODE (name) != SSA_NAME) |

674 | continue; |

675 | def = SSA_NAME_DEF_STMT (name); |

676 | if (!is_gimple_assign (def) || gimple_assign_lhs (def) != name) |

677 | continue; |

678 | |

679 | code = gimple_assign_rhs_code (def); |

680 | if (code != SSA_NAME |

681 | && !IS_EXPR_CODE_CLASS (TREE_CODE_CLASS (code)) |

682 | && (get_gimple_rhs_class (code) != GIMPLE_SINGLE_RHS |

683 | || !is_gimple_min_invariant (gimple_assign_rhs1 (def)))) |

684 | continue; |

685 | |

686 | /* We do not know whether the reference retains its value at the |

687 | place where the expansion is used. */ |

688 | if (TREE_CODE_CLASS (code) == tcc_reference) |

689 | continue; |

690 | |

691 | if (!*cache) |

692 | *cache = new hash_map<tree, name_expansion *>; |

693 | name_expansion **slot = &(*cache)->get_or_insert (e); |

694 | exp = *slot; |

695 | |

696 | if (!exp) |

697 | { |

698 | exp = XNEW (struct name_expansion); |

699 | exp->in_progress = 1; |

700 | *slot = exp; |

701 | rhs = gimple_assign_rhs_to_tree (def); |

702 | if (e != name) |

703 | rhs = fold_convert (type, rhs); |

704 | |

705 | tree_to_aff_combination_expand (rhs, comb->type, ¤t, cache); |

706 | exp->expansion = current; |

707 | exp->in_progress = 0; |

708 | } |

709 | else |

710 | { |

711 | /* Since we follow the definitions in the SSA form, we should not |

712 | enter a cycle unless we pass through a phi node. */ |

713 | gcc_assert (!exp->in_progress); |

714 | current = exp->expansion; |

715 | } |

716 | |

717 | /* Accumulate the new terms to TO_ADD, so that we do not modify |

718 | COMB while traversing it; include the term -coef * E, to remove |

719 | it from COMB. */ |

720 | scale = comb->elts[i].coef; |

721 | aff_combination_zero (&curre, comb->type); |

722 | aff_combination_add_elt (&curre, e, -scale); |

723 | aff_combination_scale (¤t, scale); |

724 | aff_combination_add (&to_add, ¤t); |

725 | aff_combination_add (&to_add, &curre); |

726 | } |

727 | aff_combination_add (comb, &to_add); |

728 | } |

729 | |

730 | /* Similar to tree_to_aff_combination, but follows SSA name definitions |

731 | and expands them recursively. CACHE is used to cache the expansions |

732 | of the ssa names, to avoid exponential time complexity for cases |

733 | like |

734 | |

735 | a1 = a0 + a0; |

736 | a2 = a1 + a1; |

737 | a3 = a2 + a2; |

738 | ... */ |

739 | |

740 | void |

741 | tree_to_aff_combination_expand (tree expr, tree type, aff_tree *comb, |

742 | hash_map<tree, name_expansion *> **cache) |

743 | { |

744 | tree_to_aff_combination (expr, type, comb); |

745 | aff_combination_expand (comb, cache); |

746 | } |

747 | |

748 | /* Frees memory occupied by struct name_expansion in *VALUE. Callback for |

749 | hash_map::traverse. */ |

750 | |

751 | bool |

752 | free_name_expansion (tree const &, name_expansion **value, void *) |

753 | { |

754 | free (*value); |

755 | return true; |

756 | } |

757 | |

758 | /* Frees memory allocated for the CACHE used by |

759 | tree_to_aff_combination_expand. */ |

760 | |

761 | void |

762 | free_affine_expand_cache (hash_map<tree, name_expansion *> **cache) |

763 | { |

764 | if (!*cache) |

765 | return; |

766 | |

767 | (*cache)->traverse<void *, free_name_expansion> (NULL); |

768 | delete (*cache); |

769 | *cache = NULL; |

770 | } |

771 | |

772 | /* If VAL != CST * DIV for any constant CST, returns false. |

773 | Otherwise, if *MULT_SET is true, additionally compares CST and MULT, |

774 | and if they are different, returns false. Finally, if neither of these |

775 | two cases occur, true is returned, and CST is stored to MULT and MULT_SET |

776 | is set to true. */ |

777 | |

778 | static bool |

779 | wide_int_constant_multiple_p (const widest_int &val, const widest_int &div, |

780 | bool *mult_set, widest_int *mult) |

781 | { |

782 | widest_int rem, cst; |

783 | |

784 | if (val == 0) |

785 | { |

786 | if (*mult_set && *mult != 0) |

787 | return false; |

788 | *mult_set = true; |

789 | *mult = 0; |

790 | return true; |

791 | } |

792 | |

793 | if (div == 0) |

794 | return false; |

795 | |

796 | if (!wi::multiple_of_p (val, div, SIGNED, &cst)) |

797 | return false; |

798 | |

799 | if (*mult_set && *mult != cst) |

800 | return false; |

801 | |

802 | *mult_set = true; |

803 | *mult = cst; |

804 | return true; |

805 | } |

806 | |

807 | /* Returns true if VAL = X * DIV for some constant X. If this is the case, |

808 | X is stored to MULT. */ |

809 | |

810 | bool |

811 | aff_combination_constant_multiple_p (aff_tree *val, aff_tree *div, |

812 | widest_int *mult) |

813 | { |

814 | bool mult_set = false; |

815 | unsigned i; |

816 | |

817 | if (val->n == 0 && val->offset == 0) |

818 | { |

819 | *mult = 0; |

820 | return true; |

821 | } |

822 | if (val->n != div->n) |

823 | return false; |

824 | |

825 | if (val->rest || div->rest) |

826 | return false; |

827 | |

828 | if (!wide_int_constant_multiple_p (val->offset, div->offset, |

829 | &mult_set, mult)) |

830 | return false; |

831 | |

832 | for (i = 0; i < div->n; i++) |

833 | { |

834 | struct aff_comb_elt *elt |

835 | = aff_combination_find_elt (val, div->elts[i].val, NULL); |

836 | if (!elt) |

837 | return false; |

838 | if (!wide_int_constant_multiple_p (elt->coef, div->elts[i].coef, |

839 | &mult_set, mult)) |

840 | return false; |

841 | } |

842 | |

843 | gcc_assert (mult_set); |

844 | return true; |

845 | } |

846 | |

847 | /* Prints the affine VAL to the FILE. */ |

848 | |

849 | static void |

850 | print_aff (FILE *file, aff_tree *val) |

851 | { |

852 | unsigned i; |

853 | signop sgn = TYPE_SIGN (val->type); |

854 | if (POINTER_TYPE_P (val->type)) |

855 | sgn = SIGNED; |

856 | fprintf (file, "{\n type = "); |

857 | print_generic_expr (file, val->type, TDF_VOPS|TDF_MEMSYMS); |

858 | fprintf (file, "\n offset = "); |

859 | print_dec (val->offset, file, sgn); |

860 | if (val->n > 0) |

861 | { |

862 | fprintf (file, "\n elements = {\n"); |

863 | for (i = 0; i < val->n; i++) |

864 | { |

865 | fprintf (file, " [%d] = ", i); |

866 | print_generic_expr (file, val->elts[i].val, TDF_VOPS|TDF_MEMSYMS); |

867 | |

868 | fprintf (file, " * "); |

869 | print_dec (val->elts[i].coef, file, sgn); |

870 | if (i != val->n - 1) |

871 | fprintf (file, ", \n"); |

872 | } |

873 | fprintf (file, "\n }"); |

874 | } |

875 | if (val->rest) |

876 | { |

877 | fprintf (file, "\n rest = "); |

878 | print_generic_expr (file, val->rest, TDF_VOPS|TDF_MEMSYMS); |

879 | } |

880 | fprintf (file, "\n}"); |

881 | } |

882 | |

883 | /* Prints the affine VAL to the standard error, used for debugging. */ |

884 | |

885 | DEBUG_FUNCTION void |

886 | debug_aff (aff_tree *val) |

887 | { |

888 | print_aff (stderr, val); |

889 | fprintf (stderr, "\n"); |

890 | } |

891 | |

892 | /* Computes address of the reference REF in ADDR. The size of the accessed |

893 | location is stored to SIZE. Returns the ultimate containing object to |

894 | which REF refers. */ |

895 | |

896 | tree |

897 | get_inner_reference_aff (tree ref, aff_tree *addr, widest_int *size) |

898 | { |

899 | HOST_WIDE_INT bitsize, bitpos; |

900 | tree toff; |

901 | machine_mode mode; |

902 | int uns, rev, vol; |

903 | aff_tree tmp; |

904 | tree base = get_inner_reference (ref, &bitsize, &bitpos, &toff, &mode, |

905 | &uns, &rev, &vol); |

906 | tree base_addr = build_fold_addr_expr (base); |

907 | |

908 | /* ADDR = &BASE + TOFF + BITPOS / BITS_PER_UNIT. */ |

909 | |

910 | tree_to_aff_combination (base_addr, sizetype, addr); |

911 | |

912 | if (toff) |

913 | { |

914 | tree_to_aff_combination (toff, sizetype, &tmp); |

915 | aff_combination_add (addr, &tmp); |

916 | } |

917 | |

918 | aff_combination_const (&tmp, sizetype, bitpos / BITS_PER_UNIT); |

919 | aff_combination_add (addr, &tmp); |

920 | |

921 | *size = (bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT; |

922 | |

923 | return base; |

924 | } |

925 | |

926 | /* Returns true if a region of size SIZE1 at position 0 and a region of |

927 | size SIZE2 at position DIFF cannot overlap. */ |

928 | |

929 | bool |

930 | aff_comb_cannot_overlap_p (aff_tree *diff, const widest_int &size1, |

931 | const widest_int &size2) |

932 | { |

933 | /* Unless the difference is a constant, we fail. */ |

934 | if (diff->n != 0) |

935 | return false; |

936 | |

937 | if (wi::neg_p (diff->offset)) |

938 | { |

939 | /* The second object is before the first one, we succeed if the last |

940 | element of the second object is before the start of the first one. */ |

941 | return wi::neg_p (diff->offset + size2 - 1); |

942 | } |

943 | else |

944 | { |

945 | /* We succeed if the second object starts after the first one ends. */ |

946 | return size1 <= diff->offset; |

947 | } |

948 | } |

949 | |

950 |