## Mercurial > hg > CbC > GCC_original

### annotate gcc/gimple-ssa-strength-reduction.c @ 16:04ced10e8804

Find changesets by keywords (author, files, the commit message), revision
number or hash, or revset expression.

gcc 7

author | kono |
---|---|

date | Fri, 27 Oct 2017 22:46:09 +0900 |

parents | |

children | 84e7813d76e9 |

rev | line source |
---|---|

16 | 1 /* Straight-line strength reduction. |

2 Copyright (C) 2012-2017 Free Software Foundation, Inc. | |

3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com> | |

4 | |

5 This file is part of GCC. | |

6 | |

7 GCC is free software; you can redistribute it and/or modify it under | |

8 the terms of the GNU General Public License as published by the Free | |

9 Software Foundation; either version 3, or (at your option) any later | |

10 version. | |

11 | |

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

13 WARRANTY; without even the implied warranty of MERCHANTABILITY or | |

14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |

15 for more details. | |

16 | |

17 You should have received a copy of the GNU General Public License | |

18 along with GCC; see the file COPYING3. If not see | |

19 <http://www.gnu.org/licenses/>. */ | |

20 | |

21 /* There are many algorithms for performing strength reduction on | |

22 loops. This is not one of them. IVOPTS handles strength reduction | |

23 of induction variables just fine. This pass is intended to pick | |

24 up the crumbs it leaves behind, by considering opportunities for | |

25 strength reduction along dominator paths. | |

26 | |

27 Strength reduction addresses explicit multiplies, and certain | |

28 multiplies implicit in addressing expressions. It would also be | |

29 possible to apply strength reduction to divisions and modulos, | |

30 but such opportunities are relatively uncommon. | |

31 | |

32 Strength reduction is also currently restricted to integer operations. | |

33 If desired, it could be extended to floating-point operations under | |

34 control of something like -funsafe-math-optimizations. */ | |

35 | |

36 #include "config.h" | |

37 #include "system.h" | |

38 #include "coretypes.h" | |

39 #include "backend.h" | |

40 #include "rtl.h" | |

41 #include "tree.h" | |

42 #include "gimple.h" | |

43 #include "cfghooks.h" | |

44 #include "tree-pass.h" | |

45 #include "ssa.h" | |

46 #include "expmed.h" | |

47 #include "gimple-pretty-print.h" | |

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

49 #include "gimple-iterator.h" | |

50 #include "gimplify-me.h" | |

51 #include "stor-layout.h" | |

52 #include "cfgloop.h" | |

53 #include "tree-cfg.h" | |

54 #include "domwalk.h" | |

55 #include "params.h" | |

56 #include "tree-ssa-address.h" | |

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

58 #include "builtins.h" | |

59 | |

60 /* Information about a strength reduction candidate. Each statement | |

61 in the candidate table represents an expression of one of the | |

62 following forms (the special case of CAND_REF will be described | |

63 later): | |

64 | |

65 (CAND_MULT) S1: X = (B + i) * S | |

66 (CAND_ADD) S1: X = B + (i * S) | |

67 | |

68 Here X and B are SSA names, i is an integer constant, and S is | |

69 either an SSA name or a constant. We call B the "base," i the | |

70 "index", and S the "stride." | |

71 | |

72 Any statement S0 that dominates S1 and is of the form: | |

73 | |

74 (CAND_MULT) S0: Y = (B + i') * S | |

75 (CAND_ADD) S0: Y = B + (i' * S) | |

76 | |

77 is called a "basis" for S1. In both cases, S1 may be replaced by | |

78 | |

79 S1': X = Y + (i - i') * S, | |

80 | |

81 where (i - i') * S is folded to the extent possible. | |

82 | |

83 All gimple statements are visited in dominator order, and each | |

84 statement that may contribute to one of the forms of S1 above is | |

85 given at least one entry in the candidate table. Such statements | |

86 include addition, pointer addition, subtraction, multiplication, | |

87 negation, copies, and nontrivial type casts. If a statement may | |

88 represent more than one expression of the forms of S1 above, | |

89 multiple "interpretations" are stored in the table and chained | |

90 together. Examples: | |

91 | |

92 * An add of two SSA names may treat either operand as the base. | |

93 * A multiply of two SSA names, likewise. | |

94 * A copy or cast may be thought of as either a CAND_MULT with | |

95 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0. | |

96 | |

97 Candidate records are allocated from an obstack. They are addressed | |

98 both from a hash table keyed on S1, and from a vector of candidate | |

99 pointers arranged in predominator order. | |

100 | |

101 Opportunity note | |

102 ---------------- | |

103 Currently we don't recognize: | |

104 | |

105 S0: Y = (S * i') - B | |

106 S1: X = (S * i) - B | |

107 | |

108 as a strength reduction opportunity, even though this S1 would | |

109 also be replaceable by the S1' above. This can be added if it | |

110 comes up in practice. | |

111 | |

112 Strength reduction in addressing | |

113 -------------------------------- | |

114 There is another kind of candidate known as CAND_REF. A CAND_REF | |

115 describes a statement containing a memory reference having | |

116 complex addressing that might benefit from strength reduction. | |

117 Specifically, we are interested in references for which | |

118 get_inner_reference returns a base address, offset, and bitpos as | |

119 follows: | |

120 | |

121 base: MEM_REF (T1, C1) | |

122 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3) | |

123 bitpos: C4 * BITS_PER_UNIT | |

124 | |

125 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are | |

126 arbitrary integer constants. Note that C2 may be zero, in which | |

127 case the offset will be MULT_EXPR (T2, C3). | |

128 | |

129 When this pattern is recognized, the original memory reference | |

130 can be replaced with: | |

131 | |

132 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)), | |

133 C1 + (C2 * C3) + C4) | |

134 | |

135 which distributes the multiply to allow constant folding. When | |

136 two or more addressing expressions can be represented by MEM_REFs | |

137 of this form, differing only in the constants C1, C2, and C4, | |

138 making this substitution produces more efficient addressing during | |

139 the RTL phases. When there are not at least two expressions with | |

140 the same values of T1, T2, and C3, there is nothing to be gained | |

141 by the replacement. | |

142 | |

143 Strength reduction of CAND_REFs uses the same infrastructure as | |

144 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B) | |

145 field, MULT_EXPR (T2, C3) in the stride (S) field, and | |

146 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF | |

147 is thus another CAND_REF with the same B and S values. When at | |

148 least two CAND_REFs are chained together using the basis relation, | |

149 each of them is replaced as above, resulting in improved code | |

150 generation for addressing. | |

151 | |

152 Conditional candidates | |

153 ====================== | |

154 | |

155 Conditional candidates are best illustrated with an example. | |

156 Consider the code sequence: | |

157 | |

158 (1) x_0 = ...; | |

159 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5) | |

160 if (...) | |

161 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1) | |

162 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1) | |

163 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1) | |

164 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5) | |

165 | |

166 Here strength reduction is complicated by the uncertain value of x_2. | |

167 A legitimate transformation is: | |

168 | |

169 (1) x_0 = ...; | |

170 (2) a_0 = x_0 * 5; | |

171 if (...) | |

172 { | |

173 (3) [x_1 = x_0 + 1;] | |

174 (3a) t_1 = a_0 + 5; | |

175 } | |

176 (4) [x_2 = PHI <x_0, x_1>;] | |

177 (4a) t_2 = PHI <a_0, t_1>; | |

178 (5) [x_3 = x_2 + 1;] | |

179 (6r) a_1 = t_2 + 5; | |

180 | |

181 where the bracketed instructions may go dead. | |

182 | |

183 To recognize this opportunity, we have to observe that statement (6) | |

184 has a "hidden basis" (2). The hidden basis is unlike a normal basis | |

185 in that the statement and the hidden basis have different base SSA | |

186 names (x_2 and x_0, respectively). The relationship is established | |

187 when a statement's base name (x_2) is defined by a phi statement (4), | |

188 each argument of which (x_0, x_1) has an identical "derived base name." | |

189 If the argument is defined by a candidate (as x_1 is by (3)) that is a | |

190 CAND_ADD having a stride of 1, the derived base name of the argument is | |

191 the base name of the candidate (x_0). Otherwise, the argument itself | |

192 is its derived base name (as is the case with argument x_0). | |

193 | |

194 The hidden basis for statement (6) is the nearest dominating candidate | |

195 whose base name is the derived base name (x_0) of the feeding phi (4), | |

196 and whose stride is identical to that of the statement. We can then | |

197 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a), | |

198 allowing the final replacement of (6) by the strength-reduced (6r). | |

199 | |

200 To facilitate this, a new kind of candidate (CAND_PHI) is introduced. | |

201 A CAND_PHI is not a candidate for replacement, but is maintained in the | |

202 candidate table to ease discovery of hidden bases. Any phi statement | |

203 whose arguments share a common derived base name is entered into the | |

204 table with the derived base name, an (arbitrary) index of zero, and a | |

205 stride of 1. A statement with a hidden basis can then be detected by | |

206 simply looking up its feeding phi definition in the candidate table, | |

207 extracting the derived base name, and searching for a basis in the | |

208 usual manner after substituting the derived base name. | |

209 | |

210 Note that the transformation is only valid when the original phi and | |

211 the statements that define the phi's arguments are all at the same | |

212 position in the loop hierarchy. */ | |

213 | |

214 | |

215 /* Index into the candidate vector, offset by 1. VECs are zero-based, | |

216 while cand_idx's are one-based, with zero indicating null. */ | |

217 typedef unsigned cand_idx; | |

218 | |

219 /* The kind of candidate. */ | |

220 enum cand_kind | |

221 { | |

222 CAND_MULT, | |

223 CAND_ADD, | |

224 CAND_REF, | |

225 CAND_PHI | |

226 }; | |

227 | |

228 struct slsr_cand_d | |

229 { | |

230 /* The candidate statement S1. */ | |

231 gimple *cand_stmt; | |

232 | |

233 /* The base expression B: often an SSA name, but not always. */ | |

234 tree base_expr; | |

235 | |

236 /* The stride S. */ | |

237 tree stride; | |

238 | |

239 /* The index constant i. */ | |

240 widest_int index; | |

241 | |

242 /* The type of the candidate. This is normally the type of base_expr, | |

243 but casts may have occurred when combining feeding instructions. | |

244 A candidate can only be a basis for candidates of the same final type. | |

245 (For CAND_REFs, this is the type to be used for operand 1 of the | |

246 replacement MEM_REF.) */ | |

247 tree cand_type; | |

248 | |

249 /* The type to be used to interpret the stride field when the stride | |

250 is not a constant. Normally the same as the type of the recorded | |

251 stride, but when the stride has been cast we need to maintain that | |

252 knowledge in order to make legal substitutions without losing | |

253 precision. When the stride is a constant, this will be sizetype. */ | |

254 tree stride_type; | |

255 | |

256 /* The kind of candidate (CAND_MULT, etc.). */ | |

257 enum cand_kind kind; | |

258 | |

259 /* Index of this candidate in the candidate vector. */ | |

260 cand_idx cand_num; | |

261 | |

262 /* Index of the next candidate record for the same statement. | |

263 A statement may be useful in more than one way (e.g., due to | |

264 commutativity). So we can have multiple "interpretations" | |

265 of a statement. */ | |

266 cand_idx next_interp; | |

267 | |

268 /* Index of the basis statement S0, if any, in the candidate vector. */ | |

269 cand_idx basis; | |

270 | |

271 /* First candidate for which this candidate is a basis, if one exists. */ | |

272 cand_idx dependent; | |

273 | |

274 /* Next candidate having the same basis as this one. */ | |

275 cand_idx sibling; | |

276 | |

277 /* If this is a conditional candidate, the CAND_PHI candidate | |

278 that defines the base SSA name B. */ | |

279 cand_idx def_phi; | |

280 | |

281 /* Savings that can be expected from eliminating dead code if this | |

282 candidate is replaced. */ | |

283 int dead_savings; | |

284 | |

285 /* For PHI candidates, use a visited flag to keep from processing the | |

286 same PHI twice from multiple paths. */ | |

287 int visited; | |

288 | |

289 /* We sometimes have to cache a phi basis with a phi candidate to | |

290 avoid processing it twice. Valid only if visited==1. */ | |

291 tree cached_basis; | |

292 }; | |

293 | |

294 typedef struct slsr_cand_d slsr_cand, *slsr_cand_t; | |

295 typedef const struct slsr_cand_d *const_slsr_cand_t; | |

296 | |

297 /* Pointers to candidates are chained together as part of a mapping | |

298 from base expressions to the candidates that use them. */ | |

299 | |

300 struct cand_chain_d | |

301 { | |

302 /* Base expression for the chain of candidates: often, but not | |

303 always, an SSA name. */ | |

304 tree base_expr; | |

305 | |

306 /* Pointer to a candidate. */ | |

307 slsr_cand_t cand; | |

308 | |

309 /* Chain pointer. */ | |

310 struct cand_chain_d *next; | |

311 | |

312 }; | |

313 | |

314 typedef struct cand_chain_d cand_chain, *cand_chain_t; | |

315 typedef const struct cand_chain_d *const_cand_chain_t; | |

316 | |

317 /* Information about a unique "increment" associated with candidates | |

318 having an SSA name for a stride. An increment is the difference | |

319 between the index of the candidate and the index of its basis, | |

320 i.e., (i - i') as discussed in the module commentary. | |

321 | |

322 When we are not going to generate address arithmetic we treat | |

323 increments that differ only in sign as the same, allowing sharing | |

324 of the cost of initializers. The absolute value of the increment | |

325 is stored in the incr_info. */ | |

326 | |

327 struct incr_info_d | |

328 { | |

329 /* The increment that relates a candidate to its basis. */ | |

330 widest_int incr; | |

331 | |

332 /* How many times the increment occurs in the candidate tree. */ | |

333 unsigned count; | |

334 | |

335 /* Cost of replacing candidates using this increment. Negative and | |

336 zero costs indicate replacement should be performed. */ | |

337 int cost; | |

338 | |

339 /* If this increment is profitable but is not -1, 0, or 1, it requires | |

340 an initializer T_0 = stride * incr to be found or introduced in the | |

341 nearest common dominator of all candidates. This field holds T_0 | |

342 for subsequent use. */ | |

343 tree initializer; | |

344 | |

345 /* If the initializer was found to already exist, this is the block | |

346 where it was found. */ | |

347 basic_block init_bb; | |

348 }; | |

349 | |

350 typedef struct incr_info_d incr_info, *incr_info_t; | |

351 | |

352 /* Candidates are maintained in a vector. If candidate X dominates | |

353 candidate Y, then X appears before Y in the vector; but the | |

354 converse does not necessarily hold. */ | |

355 static vec<slsr_cand_t> cand_vec; | |

356 | |

357 enum cost_consts | |

358 { | |

359 COST_NEUTRAL = 0, | |

360 COST_INFINITE = 1000 | |

361 }; | |

362 | |

363 enum stride_status | |

364 { | |

365 UNKNOWN_STRIDE = 0, | |

366 KNOWN_STRIDE = 1 | |

367 }; | |

368 | |

369 enum phi_adjust_status | |

370 { | |

371 NOT_PHI_ADJUST = 0, | |

372 PHI_ADJUST = 1 | |

373 }; | |

374 | |

375 enum count_phis_status | |

376 { | |

377 DONT_COUNT_PHIS = 0, | |

378 COUNT_PHIS = 1 | |

379 }; | |

380 | |

381 /* Constrain how many PHI nodes we will visit for a conditional | |

382 candidate (depth and breadth). */ | |

383 const int MAX_SPREAD = 16; | |

384 | |

385 /* Pointer map embodying a mapping from statements to candidates. */ | |

386 static hash_map<gimple *, slsr_cand_t> *stmt_cand_map; | |

387 | |

388 /* Obstack for candidates. */ | |

389 static struct obstack cand_obstack; | |

390 | |

391 /* Obstack for candidate chains. */ | |

392 static struct obstack chain_obstack; | |

393 | |

394 /* An array INCR_VEC of incr_infos is used during analysis of related | |

395 candidates having an SSA name for a stride. INCR_VEC_LEN describes | |

396 its current length. MAX_INCR_VEC_LEN is used to avoid costly | |

397 pathological cases. */ | |

398 static incr_info_t incr_vec; | |

399 static unsigned incr_vec_len; | |

400 const int MAX_INCR_VEC_LEN = 16; | |

401 | |

402 /* For a chain of candidates with unknown stride, indicates whether or not | |

403 we must generate pointer arithmetic when replacing statements. */ | |

404 static bool address_arithmetic_p; | |

405 | |

406 /* Forward function declarations. */ | |

407 static slsr_cand_t base_cand_from_table (tree); | |

408 static tree introduce_cast_before_cand (slsr_cand_t, tree, tree); | |

409 static bool legal_cast_p_1 (tree, tree); | |

410 | |

411 /* Produce a pointer to the IDX'th candidate in the candidate vector. */ | |

412 | |

413 static slsr_cand_t | |

414 lookup_cand (cand_idx idx) | |

415 { | |

416 return cand_vec[idx - 1]; | |

417 } | |

418 | |

419 /* Helper for hashing a candidate chain header. */ | |

420 | |

421 struct cand_chain_hasher : nofree_ptr_hash <cand_chain> | |

422 { | |

423 static inline hashval_t hash (const cand_chain *); | |

424 static inline bool equal (const cand_chain *, const cand_chain *); | |

425 }; | |

426 | |

427 inline hashval_t | |

428 cand_chain_hasher::hash (const cand_chain *p) | |

429 { | |

430 tree base_expr = p->base_expr; | |

431 return iterative_hash_expr (base_expr, 0); | |

432 } | |

433 | |

434 inline bool | |

435 cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2) | |

436 { | |

437 return operand_equal_p (chain1->base_expr, chain2->base_expr, 0); | |

438 } | |

439 | |

440 /* Hash table embodying a mapping from base exprs to chains of candidates. */ | |

441 static hash_table<cand_chain_hasher> *base_cand_map; | |

442 | |

443 /* Pointer map used by tree_to_aff_combination_expand. */ | |

444 static hash_map<tree, name_expansion *> *name_expansions; | |

445 /* Pointer map embodying a mapping from bases to alternative bases. */ | |

446 static hash_map<tree, tree> *alt_base_map; | |

447 | |

448 /* Given BASE, use the tree affine combiniation facilities to | |

449 find the underlying tree expression for BASE, with any | |

450 immediate offset excluded. | |

451 | |

452 N.B. we should eliminate this backtracking with better forward | |

453 analysis in a future release. */ | |

454 | |

455 static tree | |

456 get_alternative_base (tree base) | |

457 { | |

458 tree *result = alt_base_map->get (base); | |

459 | |

460 if (result == NULL) | |

461 { | |

462 tree expr; | |

463 aff_tree aff; | |

464 | |

465 tree_to_aff_combination_expand (base, TREE_TYPE (base), | |

466 &aff, &name_expansions); | |

467 aff.offset = 0; | |

468 expr = aff_combination_to_tree (&aff); | |

469 | |

470 gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr)); | |

471 | |

472 return expr == base ? NULL : expr; | |

473 } | |

474 | |

475 return *result; | |

476 } | |

477 | |

478 /* Look in the candidate table for a CAND_PHI that defines BASE and | |

479 return it if found; otherwise return NULL. */ | |

480 | |

481 static cand_idx | |

482 find_phi_def (tree base) | |

483 { | |

484 slsr_cand_t c; | |

485 | |

486 if (TREE_CODE (base) != SSA_NAME) | |

487 return 0; | |

488 | |

489 c = base_cand_from_table (base); | |

490 | |

491 if (!c || c->kind != CAND_PHI | |

492 || SSA_NAME_OCCURS_IN_ABNORMAL_PHI (gimple_phi_result (c->cand_stmt))) | |

493 return 0; | |

494 | |

495 return c->cand_num; | |

496 } | |

497 | |

498 /* Determine whether all uses of NAME are directly or indirectly | |

499 used by STMT. That is, we want to know whether if STMT goes | |

500 dead, the definition of NAME also goes dead. */ | |

501 static bool | |

502 uses_consumed_by_stmt (tree name, gimple *stmt, unsigned recurse = 0) | |

503 { | |

504 gimple *use_stmt; | |

505 imm_use_iterator iter; | |

506 bool retval = true; | |

507 | |

508 FOR_EACH_IMM_USE_STMT (use_stmt, iter, name) | |

509 { | |

510 if (use_stmt == stmt || is_gimple_debug (use_stmt)) | |

511 continue; | |

512 | |

513 if (!is_gimple_assign (use_stmt) | |

514 || !gimple_get_lhs (use_stmt) | |

515 || !is_gimple_reg (gimple_get_lhs (use_stmt)) | |

516 || recurse >= 10 | |

517 || !uses_consumed_by_stmt (gimple_get_lhs (use_stmt), stmt, | |

518 recurse + 1)) | |

519 { | |

520 retval = false; | |

521 BREAK_FROM_IMM_USE_STMT (iter); | |

522 } | |

523 } | |

524 | |

525 return retval; | |

526 } | |

527 | |

528 /* Helper routine for find_basis_for_candidate. May be called twice: | |

529 once for the candidate's base expr, and optionally again either for | |

530 the candidate's phi definition or for a CAND_REF's alternative base | |

531 expression. */ | |

532 | |

533 static slsr_cand_t | |

534 find_basis_for_base_expr (slsr_cand_t c, tree base_expr) | |

535 { | |

536 cand_chain mapping_key; | |

537 cand_chain_t chain; | |

538 slsr_cand_t basis = NULL; | |

539 | |

540 // Limit potential of N^2 behavior for long candidate chains. | |

541 int iters = 0; | |

542 int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN); | |

543 | |

544 mapping_key.base_expr = base_expr; | |

545 chain = base_cand_map->find (&mapping_key); | |

546 | |

547 for (; chain && iters < max_iters; chain = chain->next, ++iters) | |

548 { | |

549 slsr_cand_t one_basis = chain->cand; | |

550 | |

551 if (one_basis->kind != c->kind | |

552 || one_basis->cand_stmt == c->cand_stmt | |

553 || !operand_equal_p (one_basis->stride, c->stride, 0) | |

554 || !types_compatible_p (one_basis->cand_type, c->cand_type) | |

555 || !types_compatible_p (one_basis->stride_type, c->stride_type) | |

556 || !dominated_by_p (CDI_DOMINATORS, | |

557 gimple_bb (c->cand_stmt), | |

558 gimple_bb (one_basis->cand_stmt))) | |

559 continue; | |

560 | |

561 tree lhs = gimple_assign_lhs (one_basis->cand_stmt); | |

562 if (lhs && TREE_CODE (lhs) == SSA_NAME | |

563 && SSA_NAME_OCCURS_IN_ABNORMAL_PHI (lhs)) | |

564 continue; | |

565 | |

566 if (!basis || basis->cand_num < one_basis->cand_num) | |

567 basis = one_basis; | |

568 } | |

569 | |

570 return basis; | |

571 } | |

572 | |

573 /* Use the base expr from candidate C to look for possible candidates | |

574 that can serve as a basis for C. Each potential basis must also | |

575 appear in a block that dominates the candidate statement and have | |

576 the same stride and type. If more than one possible basis exists, | |

577 the one with highest index in the vector is chosen; this will be | |

578 the most immediately dominating basis. */ | |

579 | |

580 static int | |

581 find_basis_for_candidate (slsr_cand_t c) | |

582 { | |

583 slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr); | |

584 | |

585 /* If a candidate doesn't have a basis using its base expression, | |

586 it may have a basis hidden by one or more intervening phis. */ | |

587 if (!basis && c->def_phi) | |

588 { | |

589 basic_block basis_bb, phi_bb; | |

590 slsr_cand_t phi_cand = lookup_cand (c->def_phi); | |

591 basis = find_basis_for_base_expr (c, phi_cand->base_expr); | |

592 | |

593 if (basis) | |

594 { | |

595 /* A hidden basis must dominate the phi-definition of the | |

596 candidate's base name. */ | |

597 phi_bb = gimple_bb (phi_cand->cand_stmt); | |

598 basis_bb = gimple_bb (basis->cand_stmt); | |

599 | |

600 if (phi_bb == basis_bb | |

601 || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb)) | |

602 { | |

603 basis = NULL; | |

604 c->basis = 0; | |

605 } | |

606 | |

607 /* If we found a hidden basis, estimate additional dead-code | |

608 savings if the phi and its feeding statements can be removed. */ | |

609 tree feeding_var = gimple_phi_result (phi_cand->cand_stmt); | |

610 if (basis && uses_consumed_by_stmt (feeding_var, c->cand_stmt)) | |

611 c->dead_savings += phi_cand->dead_savings; | |

612 } | |

613 } | |

614 | |

615 if (flag_expensive_optimizations && !basis && c->kind == CAND_REF) | |

616 { | |

617 tree alt_base_expr = get_alternative_base (c->base_expr); | |

618 if (alt_base_expr) | |

619 basis = find_basis_for_base_expr (c, alt_base_expr); | |

620 } | |

621 | |

622 if (basis) | |

623 { | |

624 c->sibling = basis->dependent; | |

625 basis->dependent = c->cand_num; | |

626 return basis->cand_num; | |

627 } | |

628 | |

629 return 0; | |

630 } | |

631 | |

632 /* Record a mapping from BASE to C, indicating that C may potentially serve | |

633 as a basis using that base expression. BASE may be the same as | |

634 C->BASE_EXPR; alternatively BASE can be a different tree that share the | |

635 underlining expression of C->BASE_EXPR. */ | |

636 | |

637 static void | |

638 record_potential_basis (slsr_cand_t c, tree base) | |

639 { | |

640 cand_chain_t node; | |

641 cand_chain **slot; | |

642 | |

643 gcc_assert (base); | |

644 | |

645 node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain)); | |

646 node->base_expr = base; | |

647 node->cand = c; | |

648 node->next = NULL; | |

649 slot = base_cand_map->find_slot (node, INSERT); | |

650 | |

651 if (*slot) | |

652 { | |

653 cand_chain_t head = (cand_chain_t) (*slot); | |

654 node->next = head->next; | |

655 head->next = node; | |

656 } | |

657 else | |

658 *slot = node; | |

659 } | |

660 | |

661 /* Allocate storage for a new candidate and initialize its fields. | |

662 Attempt to find a basis for the candidate. | |

663 | |

664 For CAND_REF, an alternative base may also be recorded and used | |

665 to find a basis. This helps cases where the expression hidden | |

666 behind BASE (which is usually an SSA_NAME) has immediate offset, | |

667 e.g. | |

668 | |

669 a2[i][j] = 1; | |

670 a2[i + 20][j] = 2; */ | |

671 | |

672 static slsr_cand_t | |

673 alloc_cand_and_find_basis (enum cand_kind kind, gimple *gs, tree base, | |

674 const widest_int &index, tree stride, tree ctype, | |

675 tree stype, unsigned savings) | |

676 { | |

677 slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack, | |

678 sizeof (slsr_cand)); | |

679 c->cand_stmt = gs; | |

680 c->base_expr = base; | |

681 c->stride = stride; | |

682 c->index = index; | |

683 c->cand_type = ctype; | |

684 c->stride_type = stype; | |

685 c->kind = kind; | |

686 c->cand_num = cand_vec.length () + 1; | |

687 c->next_interp = 0; | |

688 c->dependent = 0; | |

689 c->sibling = 0; | |

690 c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0; | |

691 c->dead_savings = savings; | |

692 c->visited = 0; | |

693 c->cached_basis = NULL_TREE; | |

694 | |

695 cand_vec.safe_push (c); | |

696 | |

697 if (kind == CAND_PHI) | |

698 c->basis = 0; | |

699 else | |

700 c->basis = find_basis_for_candidate (c); | |

701 | |

702 record_potential_basis (c, base); | |

703 if (flag_expensive_optimizations && kind == CAND_REF) | |

704 { | |

705 tree alt_base = get_alternative_base (base); | |

706 if (alt_base) | |

707 record_potential_basis (c, alt_base); | |

708 } | |

709 | |

710 return c; | |

711 } | |

712 | |

713 /* Determine the target cost of statement GS when compiling according | |

714 to SPEED. */ | |

715 | |

716 static int | |

717 stmt_cost (gimple *gs, bool speed) | |

718 { | |

719 tree lhs, rhs1, rhs2; | |

720 machine_mode lhs_mode; | |

721 | |

722 gcc_assert (is_gimple_assign (gs)); | |

723 lhs = gimple_assign_lhs (gs); | |

724 rhs1 = gimple_assign_rhs1 (gs); | |

725 lhs_mode = TYPE_MODE (TREE_TYPE (lhs)); | |

726 | |

727 switch (gimple_assign_rhs_code (gs)) | |

728 { | |

729 case MULT_EXPR: | |

730 rhs2 = gimple_assign_rhs2 (gs); | |

731 | |

732 if (tree_fits_shwi_p (rhs2)) | |

733 return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed); | |

734 | |

735 gcc_assert (TREE_CODE (rhs1) != INTEGER_CST); | |

736 return mul_cost (speed, lhs_mode); | |

737 | |

738 case PLUS_EXPR: | |

739 case POINTER_PLUS_EXPR: | |

740 case MINUS_EXPR: | |

741 return add_cost (speed, lhs_mode); | |

742 | |

743 case NEGATE_EXPR: | |

744 return neg_cost (speed, lhs_mode); | |

745 | |

746 CASE_CONVERT: | |

747 return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed); | |

748 | |

749 /* Note that we don't assign costs to copies that in most cases | |

750 will go away. */ | |

751 case SSA_NAME: | |

752 return 0; | |

753 | |

754 default: | |

755 ; | |

756 } | |

757 | |

758 gcc_unreachable (); | |

759 return 0; | |

760 } | |

761 | |

762 /* Look up the defining statement for BASE_IN and return a pointer | |

763 to its candidate in the candidate table, if any; otherwise NULL. | |

764 Only CAND_ADD and CAND_MULT candidates are returned. */ | |

765 | |

766 static slsr_cand_t | |

767 base_cand_from_table (tree base_in) | |

768 { | |

769 slsr_cand_t *result; | |

770 | |

771 gimple *def = SSA_NAME_DEF_STMT (base_in); | |

772 if (!def) | |

773 return (slsr_cand_t) NULL; | |

774 | |

775 result = stmt_cand_map->get (def); | |

776 | |

777 if (result && (*result)->kind != CAND_REF) | |

778 return *result; | |

779 | |

780 return (slsr_cand_t) NULL; | |

781 } | |

782 | |

783 /* Add an entry to the statement-to-candidate mapping. */ | |

784 | |

785 static void | |

786 add_cand_for_stmt (gimple *gs, slsr_cand_t c) | |

787 { | |

788 gcc_assert (!stmt_cand_map->put (gs, c)); | |

789 } | |

790 | |

791 /* Given PHI which contains a phi statement, determine whether it | |

792 satisfies all the requirements of a phi candidate. If so, create | |

793 a candidate. Note that a CAND_PHI never has a basis itself, but | |

794 is used to help find a basis for subsequent candidates. */ | |

795 | |

796 static void | |

797 slsr_process_phi (gphi *phi, bool speed) | |

798 { | |

799 unsigned i; | |

800 tree arg0_base = NULL_TREE, base_type; | |

801 slsr_cand_t c; | |

802 struct loop *cand_loop = gimple_bb (phi)->loop_father; | |

803 unsigned savings = 0; | |

804 | |

805 /* A CAND_PHI requires each of its arguments to have the same | |

806 derived base name. (See the module header commentary for a | |

807 definition of derived base names.) Furthermore, all feeding | |

808 definitions must be in the same position in the loop hierarchy | |

809 as PHI. */ | |

810 | |

811 for (i = 0; i < gimple_phi_num_args (phi); i++) | |

812 { | |

813 slsr_cand_t arg_cand; | |

814 tree arg = gimple_phi_arg_def (phi, i); | |

815 tree derived_base_name = NULL_TREE; | |

816 gimple *arg_stmt = NULL; | |

817 basic_block arg_bb = NULL; | |

818 | |

819 if (TREE_CODE (arg) != SSA_NAME) | |

820 return; | |

821 | |

822 arg_cand = base_cand_from_table (arg); | |

823 | |

824 if (arg_cand) | |

825 { | |

826 while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI) | |

827 { | |

828 if (!arg_cand->next_interp) | |

829 return; | |

830 | |

831 arg_cand = lookup_cand (arg_cand->next_interp); | |

832 } | |

833 | |

834 if (!integer_onep (arg_cand->stride)) | |

835 return; | |

836 | |

837 derived_base_name = arg_cand->base_expr; | |

838 arg_stmt = arg_cand->cand_stmt; | |

839 arg_bb = gimple_bb (arg_stmt); | |

840 | |

841 /* Gather potential dead code savings if the phi statement | |

842 can be removed later on. */ | |

843 if (uses_consumed_by_stmt (arg, phi)) | |

844 { | |

845 if (gimple_code (arg_stmt) == GIMPLE_PHI) | |

846 savings += arg_cand->dead_savings; | |

847 else | |

848 savings += stmt_cost (arg_stmt, speed); | |

849 } | |

850 } | |

851 else if (SSA_NAME_IS_DEFAULT_DEF (arg)) | |

852 { | |

853 derived_base_name = arg; | |

854 arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun)); | |

855 } | |

856 | |

857 if (!arg_bb || arg_bb->loop_father != cand_loop) | |

858 return; | |

859 | |

860 if (i == 0) | |

861 arg0_base = derived_base_name; | |

862 else if (!operand_equal_p (derived_base_name, arg0_base, 0)) | |

863 return; | |

864 } | |

865 | |

866 /* Create the candidate. "alloc_cand_and_find_basis" is named | |

867 misleadingly for this case, as no basis will be sought for a | |

868 CAND_PHI. */ | |

869 base_type = TREE_TYPE (arg0_base); | |

870 | |

871 c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base, | |

872 0, integer_one_node, base_type, | |

873 sizetype, savings); | |

874 | |

875 /* Add the candidate to the statement-candidate mapping. */ | |

876 add_cand_for_stmt (phi, c); | |

877 } | |

878 | |

879 /* Given PBASE which is a pointer to tree, look up the defining | |

880 statement for it and check whether the candidate is in the | |

881 form of: | |

882 | |

883 X = B + (1 * S), S is integer constant | |

884 X = B + (i * S), S is integer one | |

885 | |

886 If so, set PBASE to the candidate's base_expr and return double | |

887 int (i * S). | |

888 Otherwise, just return double int zero. */ | |

889 | |

890 static widest_int | |

891 backtrace_base_for_ref (tree *pbase) | |

892 { | |

893 tree base_in = *pbase; | |

894 slsr_cand_t base_cand; | |

895 | |

896 STRIP_NOPS (base_in); | |

897 | |

898 /* Strip off widening conversion(s) to handle cases where | |

899 e.g. 'B' is widened from an 'int' in order to calculate | |

900 a 64-bit address. */ | |

901 if (CONVERT_EXPR_P (base_in) | |

902 && legal_cast_p_1 (TREE_TYPE (base_in), | |

903 TREE_TYPE (TREE_OPERAND (base_in, 0)))) | |

904 base_in = get_unwidened (base_in, NULL_TREE); | |

905 | |

906 if (TREE_CODE (base_in) != SSA_NAME) | |

907 return 0; | |

908 | |

909 base_cand = base_cand_from_table (base_in); | |

910 | |

911 while (base_cand && base_cand->kind != CAND_PHI) | |

912 { | |

913 if (base_cand->kind == CAND_ADD | |

914 && base_cand->index == 1 | |

915 && TREE_CODE (base_cand->stride) == INTEGER_CST) | |

916 { | |

917 /* X = B + (1 * S), S is integer constant. */ | |

918 *pbase = base_cand->base_expr; | |

919 return wi::to_widest (base_cand->stride); | |

920 } | |

921 else if (base_cand->kind == CAND_ADD | |

922 && TREE_CODE (base_cand->stride) == INTEGER_CST | |

923 && integer_onep (base_cand->stride)) | |

924 { | |

925 /* X = B + (i * S), S is integer one. */ | |

926 *pbase = base_cand->base_expr; | |

927 return base_cand->index; | |

928 } | |

929 | |

930 if (base_cand->next_interp) | |

931 base_cand = lookup_cand (base_cand->next_interp); | |

932 else | |

933 base_cand = NULL; | |

934 } | |

935 | |

936 return 0; | |

937 } | |

938 | |

939 /* Look for the following pattern: | |

940 | |

941 *PBASE: MEM_REF (T1, C1) | |

942 | |

943 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero] | |

944 or | |

945 MULT_EXPR (PLUS_EXPR (T2, C2), C3) | |

946 or | |

947 MULT_EXPR (MINUS_EXPR (T2, -C2), C3) | |

948 | |

949 *PINDEX: C4 * BITS_PER_UNIT | |

950 | |

951 If not present, leave the input values unchanged and return FALSE. | |

952 Otherwise, modify the input values as follows and return TRUE: | |

953 | |

954 *PBASE: T1 | |

955 *POFFSET: MULT_EXPR (T2, C3) | |

956 *PINDEX: C1 + (C2 * C3) + C4 | |

957 | |

958 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it | |

959 will be further restructured to: | |

960 | |

961 *PBASE: T1 | |

962 *POFFSET: MULT_EXPR (T2', C3) | |

963 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */ | |

964 | |

965 static bool | |

966 restructure_reference (tree *pbase, tree *poffset, widest_int *pindex, | |

967 tree *ptype) | |

968 { | |

969 tree base = *pbase, offset = *poffset; | |

970 widest_int index = *pindex; | |

971 tree mult_op0, t1, t2, type; | |

972 widest_int c1, c2, c3, c4, c5; | |

973 | |

974 if (!base | |

975 || !offset | |

976 || TREE_CODE (base) != MEM_REF | |

977 || TREE_CODE (offset) != MULT_EXPR | |

978 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST | |

979 || wi::umod_floor (index, BITS_PER_UNIT) != 0) | |

980 return false; | |

981 | |

982 t1 = TREE_OPERAND (base, 0); | |

983 c1 = widest_int::from (mem_ref_offset (base), SIGNED); | |

984 type = TREE_TYPE (TREE_OPERAND (base, 1)); | |

985 | |

986 mult_op0 = TREE_OPERAND (offset, 0); | |

987 c3 = wi::to_widest (TREE_OPERAND (offset, 1)); | |

988 | |

989 if (TREE_CODE (mult_op0) == PLUS_EXPR) | |

990 | |

991 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST) | |

992 { | |

993 t2 = TREE_OPERAND (mult_op0, 0); | |

994 c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1)); | |

995 } | |

996 else | |

997 return false; | |

998 | |

999 else if (TREE_CODE (mult_op0) == MINUS_EXPR) | |

1000 | |

1001 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST) | |

1002 { | |

1003 t2 = TREE_OPERAND (mult_op0, 0); | |

1004 c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1)); | |

1005 } | |

1006 else | |

1007 return false; | |

1008 | |

1009 else | |

1010 { | |

1011 t2 = mult_op0; | |

1012 c2 = 0; | |

1013 } | |

1014 | |

1015 c4 = index >> LOG2_BITS_PER_UNIT; | |

1016 c5 = backtrace_base_for_ref (&t2); | |

1017 | |

1018 *pbase = t1; | |

1019 *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2), | |

1020 wide_int_to_tree (sizetype, c3)); | |

1021 *pindex = c1 + c2 * c3 + c4 + c5 * c3; | |

1022 *ptype = type; | |

1023 | |

1024 return true; | |

1025 } | |

1026 | |

1027 /* Given GS which contains a data reference, create a CAND_REF entry in | |

1028 the candidate table and attempt to find a basis. */ | |

1029 | |

1030 static void | |

1031 slsr_process_ref (gimple *gs) | |

1032 { | |

1033 tree ref_expr, base, offset, type; | |

1034 HOST_WIDE_INT bitsize, bitpos; | |

1035 machine_mode mode; | |

1036 int unsignedp, reversep, volatilep; | |

1037 slsr_cand_t c; | |

1038 | |

1039 if (gimple_vdef (gs)) | |

1040 ref_expr = gimple_assign_lhs (gs); | |

1041 else | |

1042 ref_expr = gimple_assign_rhs1 (gs); | |

1043 | |

1044 if (!handled_component_p (ref_expr) | |

1045 || TREE_CODE (ref_expr) == BIT_FIELD_REF | |

1046 || (TREE_CODE (ref_expr) == COMPONENT_REF | |

1047 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1)))) | |

1048 return; | |

1049 | |

1050 base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode, | |

1051 &unsignedp, &reversep, &volatilep); | |

1052 if (reversep) | |

1053 return; | |

1054 widest_int index = bitpos; | |

1055 | |

1056 if (!restructure_reference (&base, &offset, &index, &type)) | |

1057 return; | |

1058 | |

1059 c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset, | |

1060 type, sizetype, 0); | |

1061 | |

1062 /* Add the candidate to the statement-candidate mapping. */ | |

1063 add_cand_for_stmt (gs, c); | |

1064 } | |

1065 | |

1066 /* Create a candidate entry for a statement GS, where GS multiplies | |

1067 two SSA names BASE_IN and STRIDE_IN. Propagate any known information | |

1068 about the two SSA names into the new candidate. Return the new | |

1069 candidate. */ | |

1070 | |

1071 static slsr_cand_t | |

1072 create_mul_ssa_cand (gimple *gs, tree base_in, tree stride_in, bool speed) | |

1073 { | |

1074 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; | |

1075 tree stype = NULL_TREE; | |

1076 widest_int index; | |

1077 unsigned savings = 0; | |

1078 slsr_cand_t c; | |

1079 slsr_cand_t base_cand = base_cand_from_table (base_in); | |

1080 | |

1081 /* Look at all interpretations of the base candidate, if necessary, | |

1082 to find information to propagate into this candidate. */ | |

1083 while (base_cand && !base && base_cand->kind != CAND_PHI) | |

1084 { | |

1085 | |

1086 if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride)) | |

1087 { | |

1088 /* Y = (B + i') * 1 | |

1089 X = Y * Z | |

1090 ================ | |

1091 X = (B + i') * Z */ | |

1092 base = base_cand->base_expr; | |

1093 index = base_cand->index; | |

1094 stride = stride_in; | |

1095 ctype = base_cand->cand_type; | |

1096 stype = TREE_TYPE (stride_in); | |

1097 if (has_single_use (base_in)) | |

1098 savings = (base_cand->dead_savings | |

1099 + stmt_cost (base_cand->cand_stmt, speed)); | |

1100 } | |

1101 else if (base_cand->kind == CAND_ADD | |

1102 && TREE_CODE (base_cand->stride) == INTEGER_CST) | |

1103 { | |

1104 /* Y = B + (i' * S), S constant | |

1105 X = Y * Z | |

1106 ============================ | |

1107 X = B + ((i' * S) * Z) */ | |

1108 base = base_cand->base_expr; | |

1109 index = base_cand->index * wi::to_widest (base_cand->stride); | |

1110 stride = stride_in; | |

1111 ctype = base_cand->cand_type; | |

1112 stype = TREE_TYPE (stride_in); | |

1113 if (has_single_use (base_in)) | |

1114 savings = (base_cand->dead_savings | |

1115 + stmt_cost (base_cand->cand_stmt, speed)); | |

1116 } | |

1117 | |

1118 if (base_cand->next_interp) | |

1119 base_cand = lookup_cand (base_cand->next_interp); | |

1120 else | |

1121 base_cand = NULL; | |

1122 } | |

1123 | |

1124 if (!base) | |

1125 { | |

1126 /* No interpretations had anything useful to propagate, so | |

1127 produce X = (Y + 0) * Z. */ | |

1128 base = base_in; | |

1129 index = 0; | |

1130 stride = stride_in; | |

1131 ctype = TREE_TYPE (base_in); | |

1132 stype = TREE_TYPE (stride_in); | |

1133 } | |

1134 | |

1135 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, | |

1136 ctype, stype, savings); | |

1137 return c; | |

1138 } | |

1139 | |

1140 /* Create a candidate entry for a statement GS, where GS multiplies | |

1141 SSA name BASE_IN by constant STRIDE_IN. Propagate any known | |

1142 information about BASE_IN into the new candidate. Return the new | |

1143 candidate. */ | |

1144 | |

1145 static slsr_cand_t | |

1146 create_mul_imm_cand (gimple *gs, tree base_in, tree stride_in, bool speed) | |

1147 { | |

1148 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; | |

1149 widest_int index, temp; | |

1150 unsigned savings = 0; | |

1151 slsr_cand_t c; | |

1152 slsr_cand_t base_cand = base_cand_from_table (base_in); | |

1153 | |

1154 /* Look at all interpretations of the base candidate, if necessary, | |

1155 to find information to propagate into this candidate. */ | |

1156 while (base_cand && !base && base_cand->kind != CAND_PHI) | |

1157 { | |

1158 if (base_cand->kind == CAND_MULT | |

1159 && TREE_CODE (base_cand->stride) == INTEGER_CST) | |

1160 { | |

1161 /* Y = (B + i') * S, S constant | |

1162 X = Y * c | |

1163 ============================ | |

1164 X = (B + i') * (S * c) */ | |

1165 temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in); | |

1166 if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in))) | |

1167 { | |

1168 base = base_cand->base_expr; | |

1169 index = base_cand->index; | |

1170 stride = wide_int_to_tree (TREE_TYPE (stride_in), temp); | |

1171 ctype = base_cand->cand_type; | |

1172 if (has_single_use (base_in)) | |

1173 savings = (base_cand->dead_savings | |

1174 + stmt_cost (base_cand->cand_stmt, speed)); | |

1175 } | |

1176 } | |

1177 else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride)) | |

1178 { | |

1179 /* Y = B + (i' * 1) | |

1180 X = Y * c | |

1181 =========================== | |

1182 X = (B + i') * c */ | |

1183 base = base_cand->base_expr; | |

1184 index = base_cand->index; | |

1185 stride = stride_in; | |

1186 ctype = base_cand->cand_type; | |

1187 if (has_single_use (base_in)) | |

1188 savings = (base_cand->dead_savings | |

1189 + stmt_cost (base_cand->cand_stmt, speed)); | |

1190 } | |

1191 else if (base_cand->kind == CAND_ADD | |

1192 && base_cand->index == 1 | |

1193 && TREE_CODE (base_cand->stride) == INTEGER_CST) | |

1194 { | |

1195 /* Y = B + (1 * S), S constant | |

1196 X = Y * c | |

1197 =========================== | |

1198 X = (B + S) * c */ | |

1199 base = base_cand->base_expr; | |

1200 index = wi::to_widest (base_cand->stride); | |

1201 stride = stride_in; | |

1202 ctype = base_cand->cand_type; | |

1203 if (has_single_use (base_in)) | |

1204 savings = (base_cand->dead_savings | |

1205 + stmt_cost (base_cand->cand_stmt, speed)); | |

1206 } | |

1207 | |

1208 if (base_cand->next_interp) | |

1209 base_cand = lookup_cand (base_cand->next_interp); | |

1210 else | |

1211 base_cand = NULL; | |

1212 } | |

1213 | |

1214 if (!base) | |

1215 { | |

1216 /* No interpretations had anything useful to propagate, so | |

1217 produce X = (Y + 0) * c. */ | |

1218 base = base_in; | |

1219 index = 0; | |

1220 stride = stride_in; | |

1221 ctype = TREE_TYPE (base_in); | |

1222 } | |

1223 | |

1224 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride, | |

1225 ctype, sizetype, savings); | |

1226 return c; | |

1227 } | |

1228 | |

1229 /* Given GS which is a multiply of scalar integers, make an appropriate | |

1230 entry in the candidate table. If this is a multiply of two SSA names, | |

1231 create two CAND_MULT interpretations and attempt to find a basis for | |

1232 each of them. Otherwise, create a single CAND_MULT and attempt to | |

1233 find a basis. */ | |

1234 | |

1235 static void | |

1236 slsr_process_mul (gimple *gs, tree rhs1, tree rhs2, bool speed) | |

1237 { | |

1238 slsr_cand_t c, c2; | |

1239 | |

1240 /* If this is a multiply of an SSA name with itself, it is highly | |

1241 unlikely that we will get a strength reduction opportunity, so | |

1242 don't record it as a candidate. This simplifies the logic for | |

1243 finding a basis, so if this is removed that must be considered. */ | |

1244 if (rhs1 == rhs2) | |

1245 return; | |

1246 | |

1247 if (TREE_CODE (rhs2) == SSA_NAME) | |

1248 { | |

1249 /* Record an interpretation of this statement in the candidate table | |

1250 assuming RHS1 is the base expression and RHS2 is the stride. */ | |

1251 c = create_mul_ssa_cand (gs, rhs1, rhs2, speed); | |

1252 | |

1253 /* Add the first interpretation to the statement-candidate mapping. */ | |

1254 add_cand_for_stmt (gs, c); | |

1255 | |

1256 /* Record another interpretation of this statement assuming RHS1 | |

1257 is the stride and RHS2 is the base expression. */ | |

1258 c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed); | |

1259 c->next_interp = c2->cand_num; | |

1260 } | |

1261 else | |

1262 { | |

1263 /* Record an interpretation for the multiply-immediate. */ | |

1264 c = create_mul_imm_cand (gs, rhs1, rhs2, speed); | |

1265 | |

1266 /* Add the interpretation to the statement-candidate mapping. */ | |

1267 add_cand_for_stmt (gs, c); | |

1268 } | |

1269 } | |

1270 | |

1271 /* Create a candidate entry for a statement GS, where GS adds two | |

1272 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and | |

1273 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known | |

1274 information about the two SSA names into the new candidate. | |

1275 Return the new candidate. */ | |

1276 | |

1277 static slsr_cand_t | |

1278 create_add_ssa_cand (gimple *gs, tree base_in, tree addend_in, | |

1279 bool subtract_p, bool speed) | |

1280 { | |

1281 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; | |

1282 tree stype = NULL_TREE; | |

1283 widest_int index; | |

1284 unsigned savings = 0; | |

1285 slsr_cand_t c; | |

1286 slsr_cand_t base_cand = base_cand_from_table (base_in); | |

1287 slsr_cand_t addend_cand = base_cand_from_table (addend_in); | |

1288 | |

1289 /* The most useful transformation is a multiply-immediate feeding | |

1290 an add or subtract. Look for that first. */ | |

1291 while (addend_cand && !base && addend_cand->kind != CAND_PHI) | |

1292 { | |

1293 if (addend_cand->kind == CAND_MULT | |

1294 && addend_cand->index == 0 | |

1295 && TREE_CODE (addend_cand->stride) == INTEGER_CST) | |

1296 { | |

1297 /* Z = (B + 0) * S, S constant | |

1298 X = Y +/- Z | |

1299 =========================== | |

1300 X = Y + ((+/-1 * S) * B) */ | |

1301 base = base_in; | |

1302 index = wi::to_widest (addend_cand->stride); | |

1303 if (subtract_p) | |

1304 index = -index; | |

1305 stride = addend_cand->base_expr; | |

1306 ctype = TREE_TYPE (base_in); | |

1307 stype = addend_cand->cand_type; | |

1308 if (has_single_use (addend_in)) | |

1309 savings = (addend_cand->dead_savings | |

1310 + stmt_cost (addend_cand->cand_stmt, speed)); | |

1311 } | |

1312 | |

1313 if (addend_cand->next_interp) | |

1314 addend_cand = lookup_cand (addend_cand->next_interp); | |

1315 else | |

1316 addend_cand = NULL; | |

1317 } | |

1318 | |

1319 while (base_cand && !base && base_cand->kind != CAND_PHI) | |

1320 { | |

1321 if (base_cand->kind == CAND_ADD | |

1322 && (base_cand->index == 0 | |

1323 || operand_equal_p (base_cand->stride, | |

1324 integer_zero_node, 0))) | |

1325 { | |

1326 /* Y = B + (i' * S), i' * S = 0 | |

1327 X = Y +/- Z | |

1328 ============================ | |

1329 X = B + (+/-1 * Z) */ | |

1330 base = base_cand->base_expr; | |

1331 index = subtract_p ? -1 : 1; | |

1332 stride = addend_in; | |

1333 ctype = base_cand->cand_type; | |

1334 stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype | |

1335 : TREE_TYPE (addend_in)); | |

1336 if (has_single_use (base_in)) | |

1337 savings = (base_cand->dead_savings | |

1338 + stmt_cost (base_cand->cand_stmt, speed)); | |

1339 } | |

1340 else if (subtract_p) | |

1341 { | |

1342 slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in); | |

1343 | |

1344 while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI) | |

1345 { | |

1346 if (subtrahend_cand->kind == CAND_MULT | |

1347 && subtrahend_cand->index == 0 | |

1348 && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST) | |

1349 { | |

1350 /* Z = (B + 0) * S, S constant | |

1351 X = Y - Z | |

1352 =========================== | |

1353 Value: X = Y + ((-1 * S) * B) */ | |

1354 base = base_in; | |

1355 index = wi::to_widest (subtrahend_cand->stride); | |

1356 index = -index; | |

1357 stride = subtrahend_cand->base_expr; | |

1358 ctype = TREE_TYPE (base_in); | |

1359 stype = subtrahend_cand->cand_type; | |

1360 if (has_single_use (addend_in)) | |

1361 savings = (subtrahend_cand->dead_savings | |

1362 + stmt_cost (subtrahend_cand->cand_stmt, speed)); | |

1363 } | |

1364 | |

1365 if (subtrahend_cand->next_interp) | |

1366 subtrahend_cand = lookup_cand (subtrahend_cand->next_interp); | |

1367 else | |

1368 subtrahend_cand = NULL; | |

1369 } | |

1370 } | |

1371 | |

1372 if (base_cand->next_interp) | |

1373 base_cand = lookup_cand (base_cand->next_interp); | |

1374 else | |

1375 base_cand = NULL; | |

1376 } | |

1377 | |

1378 if (!base) | |

1379 { | |

1380 /* No interpretations had anything useful to propagate, so | |

1381 produce X = Y + (1 * Z). */ | |

1382 base = base_in; | |

1383 index = subtract_p ? -1 : 1; | |

1384 stride = addend_in; | |

1385 ctype = TREE_TYPE (base_in); | |

1386 stype = (TREE_CODE (addend_in) == INTEGER_CST ? sizetype | |

1387 : TREE_TYPE (addend_in)); | |

1388 } | |

1389 | |

1390 c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride, | |

1391 ctype, stype, savings); | |

1392 return c; | |

1393 } | |

1394 | |

1395 /* Create a candidate entry for a statement GS, where GS adds SSA | |

1396 name BASE_IN to constant INDEX_IN. Propagate any known information | |

1397 about BASE_IN into the new candidate. Return the new candidate. */ | |

1398 | |

1399 static slsr_cand_t | |

1400 create_add_imm_cand (gimple *gs, tree base_in, const widest_int &index_in, | |

1401 bool speed) | |

1402 { | |

1403 enum cand_kind kind = CAND_ADD; | |

1404 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE; | |

1405 tree stype = NULL_TREE; | |

1406 widest_int index, multiple; | |

1407 unsigned savings = 0; | |

1408 slsr_cand_t c; | |

1409 slsr_cand_t base_cand = base_cand_from_table (base_in); | |

1410 | |

1411 while (base_cand && !base && base_cand->kind != CAND_PHI) | |

1412 { | |

1413 signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride)); | |

1414 | |

1415 if (TREE_CODE (base_cand->stride) == INTEGER_CST | |

1416 && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride), | |

1417 sign, &multiple)) | |

1418 { | |

1419 /* Y = (B + i') * S, S constant, c = kS for some integer k | |

1420 X = Y + c | |

1421 ============================ | |

1422 X = (B + (i'+ k)) * S | |

1423 OR | |

1424 Y = B + (i' * S), S constant, c = kS for some integer k | |

1425 X = Y + c | |

1426 ============================ | |

1427 X = (B + (i'+ k)) * S */ | |

1428 kind = base_cand->kind; | |

1429 base = base_cand->base_expr; | |

1430 index = base_cand->index + multiple; | |

1431 stride = base_cand->stride; | |

1432 ctype = base_cand->cand_type; | |

1433 stype = base_cand->stride_type; | |

1434 if (has_single_use (base_in)) | |

1435 savings = (base_cand->dead_savings | |

1436 + stmt_cost (base_cand->cand_stmt, speed)); | |

1437 } | |

1438 | |

1439 if (base_cand->next_interp) | |

1440 base_cand = lookup_cand (base_cand->next_interp); | |

1441 else | |

1442 base_cand = NULL; | |

1443 } | |

1444 | |

1445 if (!base) | |

1446 { | |

1447 /* No interpretations had anything useful to propagate, so | |

1448 produce X = Y + (c * 1). */ | |

1449 kind = CAND_ADD; | |

1450 base = base_in; | |

1451 index = index_in; | |

1452 stride = integer_one_node; | |

1453 ctype = TREE_TYPE (base_in); | |

1454 stype = sizetype; | |

1455 } | |

1456 | |

1457 c = alloc_cand_and_find_basis (kind, gs, base, index, stride, | |

1458 ctype, stype, savings); | |

1459 return c; | |

1460 } | |

1461 | |

1462 /* Given GS which is an add or subtract of scalar integers or pointers, | |

1463 make at least one appropriate entry in the candidate table. */ | |

1464 | |

1465 static void | |

1466 slsr_process_add (gimple *gs, tree rhs1, tree rhs2, bool speed) | |

1467 { | |

1468 bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR; | |

1469 slsr_cand_t c = NULL, c2; | |

1470 | |

1471 if (TREE_CODE (rhs2) == SSA_NAME) | |

1472 { | |

1473 /* First record an interpretation assuming RHS1 is the base expression | |

1474 and RHS2 is the stride. But it doesn't make sense for the | |

1475 stride to be a pointer, so don't record a candidate in that case. */ | |

1476 if (!POINTER_TYPE_P (TREE_TYPE (rhs2))) | |

1477 { | |

1478 c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed); | |

1479 | |

1480 /* Add the first interpretation to the statement-candidate | |

1481 mapping. */ | |

1482 add_cand_for_stmt (gs, c); | |

1483 } | |

1484 | |

1485 /* If the two RHS operands are identical, or this is a subtract, | |

1486 we're done. */ | |

1487 if (operand_equal_p (rhs1, rhs2, 0) || subtract_p) | |

1488 return; | |

1489 | |

1490 /* Otherwise, record another interpretation assuming RHS2 is the | |

1491 base expression and RHS1 is the stride, again provided that the | |

1492 stride is not a pointer. */ | |

1493 if (!POINTER_TYPE_P (TREE_TYPE (rhs1))) | |

1494 { | |

1495 c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed); | |

1496 if (c) | |

1497 c->next_interp = c2->cand_num; | |

1498 else | |

1499 add_cand_for_stmt (gs, c2); | |

1500 } | |

1501 } | |

1502 else | |

1503 { | |

1504 /* Record an interpretation for the add-immediate. */ | |

1505 widest_int index = wi::to_widest (rhs2); | |

1506 if (subtract_p) | |

1507 index = -index; | |

1508 | |

1509 c = create_add_imm_cand (gs, rhs1, index, speed); | |

1510 | |

1511 /* Add the interpretation to the statement-candidate mapping. */ | |

1512 add_cand_for_stmt (gs, c); | |

1513 } | |

1514 } | |

1515 | |

1516 /* Given GS which is a negate of a scalar integer, make an appropriate | |

1517 entry in the candidate table. A negate is equivalent to a multiply | |

1518 by -1. */ | |

1519 | |

1520 static void | |

1521 slsr_process_neg (gimple *gs, tree rhs1, bool speed) | |

1522 { | |

1523 /* Record a CAND_MULT interpretation for the multiply by -1. */ | |

1524 slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed); | |

1525 | |

1526 /* Add the interpretation to the statement-candidate mapping. */ | |

1527 add_cand_for_stmt (gs, c); | |

1528 } | |

1529 | |

1530 /* Help function for legal_cast_p, operating on two trees. Checks | |

1531 whether it's allowable to cast from RHS to LHS. See legal_cast_p | |

1532 for more details. */ | |

1533 | |

1534 static bool | |

1535 legal_cast_p_1 (tree lhs_type, tree rhs_type) | |

1536 { | |

1537 unsigned lhs_size, rhs_size; | |

1538 bool lhs_wraps, rhs_wraps; | |

1539 | |

1540 lhs_size = TYPE_PRECISION (lhs_type); | |

1541 rhs_size = TYPE_PRECISION (rhs_type); | |

1542 lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type); | |

1543 rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type); | |

1544 | |

1545 if (lhs_size < rhs_size | |

1546 || (rhs_wraps && !lhs_wraps) | |

1547 || (rhs_wraps && lhs_wraps && rhs_size != lhs_size)) | |

1548 return false; | |

1549 | |

1550 return true; | |

1551 } | |

1552 | |

1553 /* Return TRUE if GS is a statement that defines an SSA name from | |

1554 a conversion and is legal for us to combine with an add and multiply | |

1555 in the candidate table. For example, suppose we have: | |

1556 | |

1557 A = B + i; | |

1558 C = (type) A; | |

1559 D = C * S; | |

1560 | |

1561 Without the type-cast, we would create a CAND_MULT for D with base B, | |

1562 index i, and stride S. We want to record this candidate only if it | |

1563 is equivalent to apply the type cast following the multiply: | |

1564 | |

1565 A = B + i; | |

1566 E = A * S; | |

1567 D = (type) E; | |

1568 | |

1569 We will record the type with the candidate for D. This allows us | |

1570 to use a similar previous candidate as a basis. If we have earlier seen | |

1571 | |

1572 A' = B + i'; | |

1573 C' = (type) A'; | |

1574 D' = C' * S; | |

1575 | |

1576 we can replace D with | |

1577 | |

1578 D = D' + (i - i') * S; | |

1579 | |

1580 But if moving the type-cast would change semantics, we mustn't do this. | |

1581 | |

1582 This is legitimate for casts from a non-wrapping integral type to | |

1583 any integral type of the same or larger size. It is not legitimate | |

1584 to convert a wrapping type to a non-wrapping type, or to a wrapping | |

1585 type of a different size. I.e., with a wrapping type, we must | |

1586 assume that the addition B + i could wrap, in which case performing | |

1587 the multiply before or after one of the "illegal" type casts will | |

1588 have different semantics. */ | |

1589 | |

1590 static bool | |

1591 legal_cast_p (gimple *gs, tree rhs) | |

1592 { | |

1593 if (!is_gimple_assign (gs) | |

1594 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs))) | |

1595 return false; | |

1596 | |

1597 return legal_cast_p_1 (TREE_TYPE (gimple_assign_lhs (gs)), TREE_TYPE (rhs)); | |

1598 } | |

1599 | |

1600 /* Given GS which is a cast to a scalar integer type, determine whether | |

1601 the cast is legal for strength reduction. If so, make at least one | |

1602 appropriate entry in the candidate table. */ | |

1603 | |

1604 static void | |

1605 slsr_process_cast (gimple *gs, tree rhs1, bool speed) | |

1606 { | |

1607 tree lhs, ctype; | |

1608 slsr_cand_t base_cand, c = NULL, c2; | |

1609 unsigned savings = 0; | |

1610 | |

1611 if (!legal_cast_p (gs, rhs1)) | |

1612 return; | |

1613 | |

1614 lhs = gimple_assign_lhs (gs); | |

1615 base_cand = base_cand_from_table (rhs1); | |

1616 ctype = TREE_TYPE (lhs); | |

1617 | |

1618 if (base_cand && base_cand->kind != CAND_PHI) | |

1619 { | |

1620 while (base_cand) | |

1621 { | |

1622 /* Propagate all data from the base candidate except the type, | |

1623 which comes from the cast, and the base candidate's cast, | |

1624 which is no longer applicable. */ | |

1625 if (has_single_use (rhs1)) | |

1626 savings = (base_cand->dead_savings | |

1627 + stmt_cost (base_cand->cand_stmt, speed)); | |

1628 | |

1629 c = alloc_cand_and_find_basis (base_cand->kind, gs, | |

1630 base_cand->base_expr, | |

1631 base_cand->index, base_cand->stride, | |

1632 ctype, base_cand->stride_type, | |

1633 savings); | |

1634 if (base_cand->next_interp) | |

1635 base_cand = lookup_cand (base_cand->next_interp); | |

1636 else | |

1637 base_cand = NULL; | |

1638 } | |

1639 } | |

1640 else | |

1641 { | |

1642 /* If nothing is known about the RHS, create fresh CAND_ADD and | |

1643 CAND_MULT interpretations: | |

1644 | |

1645 X = Y + (0 * 1) | |

1646 X = (Y + 0) * 1 | |

1647 | |

1648 The first of these is somewhat arbitrary, but the choice of | |

1649 1 for the stride simplifies the logic for propagating casts | |

1650 into their uses. */ | |

1651 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, | |

1652 integer_one_node, ctype, sizetype, 0); | |

1653 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, | |

1654 integer_one_node, ctype, sizetype, 0); | |

1655 c->next_interp = c2->cand_num; | |

1656 } | |

1657 | |

1658 /* Add the first (or only) interpretation to the statement-candidate | |

1659 mapping. */ | |

1660 add_cand_for_stmt (gs, c); | |

1661 } | |

1662 | |

1663 /* Given GS which is a copy of a scalar integer type, make at least one | |

1664 appropriate entry in the candidate table. | |

1665 | |

1666 This interface is included for completeness, but is unnecessary | |

1667 if this pass immediately follows a pass that performs copy | |

1668 propagation, such as DOM. */ | |

1669 | |

1670 static void | |

1671 slsr_process_copy (gimple *gs, tree rhs1, bool speed) | |

1672 { | |

1673 slsr_cand_t base_cand, c = NULL, c2; | |

1674 unsigned savings = 0; | |

1675 | |

1676 base_cand = base_cand_from_table (rhs1); | |

1677 | |

1678 if (base_cand && base_cand->kind != CAND_PHI) | |

1679 { | |

1680 while (base_cand) | |

1681 { | |

1682 /* Propagate all data from the base candidate. */ | |

1683 if (has_single_use (rhs1)) | |

1684 savings = (base_cand->dead_savings | |

1685 + stmt_cost (base_cand->cand_stmt, speed)); | |

1686 | |

1687 c = alloc_cand_and_find_basis (base_cand->kind, gs, | |

1688 base_cand->base_expr, | |

1689 base_cand->index, base_cand->stride, | |

1690 base_cand->cand_type, | |

1691 base_cand->stride_type, savings); | |

1692 if (base_cand->next_interp) | |

1693 base_cand = lookup_cand (base_cand->next_interp); | |

1694 else | |

1695 base_cand = NULL; | |

1696 } | |

1697 } | |

1698 else | |

1699 { | |

1700 /* If nothing is known about the RHS, create fresh CAND_ADD and | |

1701 CAND_MULT interpretations: | |

1702 | |

1703 X = Y + (0 * 1) | |

1704 X = (Y + 0) * 1 | |

1705 | |

1706 The first of these is somewhat arbitrary, but the choice of | |

1707 1 for the stride simplifies the logic for propagating casts | |

1708 into their uses. */ | |

1709 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1, 0, | |

1710 integer_one_node, TREE_TYPE (rhs1), | |

1711 sizetype, 0); | |

1712 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1, 0, | |

1713 integer_one_node, TREE_TYPE (rhs1), | |

1714 sizetype, 0); | |

1715 c->next_interp = c2->cand_num; | |

1716 } | |

1717 | |

1718 /* Add the first (or only) interpretation to the statement-candidate | |

1719 mapping. */ | |

1720 add_cand_for_stmt (gs, c); | |

1721 } | |

1722 | |

1723 class find_candidates_dom_walker : public dom_walker | |

1724 { | |

1725 public: | |

1726 find_candidates_dom_walker (cdi_direction direction) | |

1727 : dom_walker (direction) {} | |

1728 virtual edge before_dom_children (basic_block); | |

1729 }; | |

1730 | |

1731 /* Find strength-reduction candidates in block BB. */ | |

1732 | |

1733 edge | |

1734 find_candidates_dom_walker::before_dom_children (basic_block bb) | |

1735 { | |

1736 bool speed = optimize_bb_for_speed_p (bb); | |

1737 | |

1738 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi); | |

1739 gsi_next (&gsi)) | |

1740 slsr_process_phi (gsi.phi (), speed); | |

1741 | |

1742 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi); | |

1743 gsi_next (&gsi)) | |

1744 { | |

1745 gimple *gs = gsi_stmt (gsi); | |

1746 | |

1747 if (gimple_vuse (gs) && gimple_assign_single_p (gs)) | |

1748 slsr_process_ref (gs); | |

1749 | |

1750 else if (is_gimple_assign (gs) | |

1751 && (INTEGRAL_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs))) | |

1752 || POINTER_TYPE_P (TREE_TYPE (gimple_assign_lhs (gs))))) | |

1753 { | |

1754 tree rhs1 = NULL_TREE, rhs2 = NULL_TREE; | |

1755 | |

1756 switch (gimple_assign_rhs_code (gs)) | |

1757 { | |

1758 case MULT_EXPR: | |

1759 case PLUS_EXPR: | |

1760 rhs1 = gimple_assign_rhs1 (gs); | |

1761 rhs2 = gimple_assign_rhs2 (gs); | |

1762 /* Should never happen, but currently some buggy situations | |

1763 in earlier phases put constants in rhs1. */ | |

1764 if (TREE_CODE (rhs1) != SSA_NAME) | |

1765 continue; | |

1766 break; | |

1767 | |

1768 /* Possible future opportunity: rhs1 of a ptr+ can be | |

1769 an ADDR_EXPR. */ | |

1770 case POINTER_PLUS_EXPR: | |

1771 case MINUS_EXPR: | |

1772 rhs2 = gimple_assign_rhs2 (gs); | |

1773 gcc_fallthrough (); | |

1774 | |

1775 CASE_CONVERT: | |

1776 case SSA_NAME: | |

1777 case NEGATE_EXPR: | |

1778 rhs1 = gimple_assign_rhs1 (gs); | |

1779 if (TREE_CODE (rhs1) != SSA_NAME) | |

1780 continue; | |

1781 break; | |

1782 | |

1783 default: | |

1784 ; | |

1785 } | |

1786 | |

1787 switch (gimple_assign_rhs_code (gs)) | |

1788 { | |

1789 case MULT_EXPR: | |

1790 slsr_process_mul (gs, rhs1, rhs2, speed); | |

1791 break; | |

1792 | |

1793 case PLUS_EXPR: | |

1794 case POINTER_PLUS_EXPR: | |

1795 case MINUS_EXPR: | |

1796 slsr_process_add (gs, rhs1, rhs2, speed); | |

1797 break; | |

1798 | |

1799 case NEGATE_EXPR: | |

1800 slsr_process_neg (gs, rhs1, speed); | |

1801 break; | |

1802 | |

1803 CASE_CONVERT: | |

1804 slsr_process_cast (gs, rhs1, speed); | |

1805 break; | |

1806 | |

1807 case SSA_NAME: | |

1808 slsr_process_copy (gs, rhs1, speed); | |

1809 break; | |

1810 | |

1811 default: | |

1812 ; | |

1813 } | |

1814 } | |

1815 } | |

1816 return NULL; | |

1817 } | |

1818 | |

1819 /* Dump a candidate for debug. */ | |

1820 | |

1821 static void | |

1822 dump_candidate (slsr_cand_t c) | |

1823 { | |

1824 fprintf (dump_file, "%3d [%d] ", c->cand_num, | |

1825 gimple_bb (c->cand_stmt)->index); | |

1826 print_gimple_stmt (dump_file, c->cand_stmt, 0); | |

1827 switch (c->kind) | |

1828 { | |

1829 case CAND_MULT: | |

1830 fputs (" MULT : (", dump_file); | |

1831 print_generic_expr (dump_file, c->base_expr); | |

1832 fputs (" + ", dump_file); | |

1833 print_decs (c->index, dump_file); | |

1834 fputs (") * ", dump_file); | |

1835 if (TREE_CO |