decl.c (value_annotation_hasher::handle_cache_entry): Delete.
[gcc.git] / gcc / gimple-ssa-strength-reduction.c
1 /* Straight-line strength reduction.
2 Copyright (C) 2012-2015 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 "alias.h"
40 #include "symtab.h"
41 #include "options.h"
42 #include "tree.h"
43 #include "fold-const.h"
44 #include "predict.h"
45 #include "tm.h"
46 #include "hard-reg-set.h"
47 #include "function.h"
48 #include "dominance.h"
49 #include "cfg.h"
50 #include "basic-block.h"
51 #include "tree-ssa-alias.h"
52 #include "internal-fn.h"
53 #include "gimple-expr.h"
54 #include "gimple.h"
55 #include "gimple-iterator.h"
56 #include "gimplify-me.h"
57 #include "stor-layout.h"
58 #include "rtl.h"
59 #include "flags.h"
60 #include "insn-config.h"
61 #include "expmed.h"
62 #include "dojump.h"
63 #include "explow.h"
64 #include "calls.h"
65 #include "emit-rtl.h"
66 #include "varasm.h"
67 #include "stmt.h"
68 #include "expr.h"
69 #include "tree-pass.h"
70 #include "cfgloop.h"
71 #include "gimple-pretty-print.h"
72 #include "gimple-ssa.h"
73 #include "tree-cfg.h"
74 #include "tree-phinodes.h"
75 #include "ssa-iterators.h"
76 #include "stringpool.h"
77 #include "tree-ssanames.h"
78 #include "domwalk.h"
79 #include "params.h"
80 #include "tree-ssa-address.h"
81 #include "tree-affine.h"
82 #include "wide-int-print.h"
83 #include "builtins.h"
84 \f
85 /* Information about a strength reduction candidate. Each statement
86 in the candidate table represents an expression of one of the
87 following forms (the special case of CAND_REF will be described
88 later):
89
90 (CAND_MULT) S1: X = (B + i) * S
91 (CAND_ADD) S1: X = B + (i * S)
92
93 Here X and B are SSA names, i is an integer constant, and S is
94 either an SSA name or a constant. We call B the "base," i the
95 "index", and S the "stride."
96
97 Any statement S0 that dominates S1 and is of the form:
98
99 (CAND_MULT) S0: Y = (B + i') * S
100 (CAND_ADD) S0: Y = B + (i' * S)
101
102 is called a "basis" for S1. In both cases, S1 may be replaced by
103
104 S1': X = Y + (i - i') * S,
105
106 where (i - i') * S is folded to the extent possible.
107
108 All gimple statements are visited in dominator order, and each
109 statement that may contribute to one of the forms of S1 above is
110 given at least one entry in the candidate table. Such statements
111 include addition, pointer addition, subtraction, multiplication,
112 negation, copies, and nontrivial type casts. If a statement may
113 represent more than one expression of the forms of S1 above,
114 multiple "interpretations" are stored in the table and chained
115 together. Examples:
116
117 * An add of two SSA names may treat either operand as the base.
118 * A multiply of two SSA names, likewise.
119 * A copy or cast may be thought of as either a CAND_MULT with
120 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
121
122 Candidate records are allocated from an obstack. They are addressed
123 both from a hash table keyed on S1, and from a vector of candidate
124 pointers arranged in predominator order.
125
126 Opportunity note
127 ----------------
128 Currently we don't recognize:
129
130 S0: Y = (S * i') - B
131 S1: X = (S * i) - B
132
133 as a strength reduction opportunity, even though this S1 would
134 also be replaceable by the S1' above. This can be added if it
135 comes up in practice.
136
137 Strength reduction in addressing
138 --------------------------------
139 There is another kind of candidate known as CAND_REF. A CAND_REF
140 describes a statement containing a memory reference having
141 complex addressing that might benefit from strength reduction.
142 Specifically, we are interested in references for which
143 get_inner_reference returns a base address, offset, and bitpos as
144 follows:
145
146 base: MEM_REF (T1, C1)
147 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
148 bitpos: C4 * BITS_PER_UNIT
149
150 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
151 arbitrary integer constants. Note that C2 may be zero, in which
152 case the offset will be MULT_EXPR (T2, C3).
153
154 When this pattern is recognized, the original memory reference
155 can be replaced with:
156
157 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
158 C1 + (C2 * C3) + C4)
159
160 which distributes the multiply to allow constant folding. When
161 two or more addressing expressions can be represented by MEM_REFs
162 of this form, differing only in the constants C1, C2, and C4,
163 making this substitution produces more efficient addressing during
164 the RTL phases. When there are not at least two expressions with
165 the same values of T1, T2, and C3, there is nothing to be gained
166 by the replacement.
167
168 Strength reduction of CAND_REFs uses the same infrastructure as
169 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
170 field, MULT_EXPR (T2, C3) in the stride (S) field, and
171 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
172 is thus another CAND_REF with the same B and S values. When at
173 least two CAND_REFs are chained together using the basis relation,
174 each of them is replaced as above, resulting in improved code
175 generation for addressing.
176
177 Conditional candidates
178 ======================
179
180 Conditional candidates are best illustrated with an example.
181 Consider the code sequence:
182
183 (1) x_0 = ...;
184 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
185 if (...)
186 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
187 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
188 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
189 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
190
191 Here strength reduction is complicated by the uncertain value of x_2.
192 A legitimate transformation is:
193
194 (1) x_0 = ...;
195 (2) a_0 = x_0 * 5;
196 if (...)
197 {
198 (3) [x_1 = x_0 + 1;]
199 (3a) t_1 = a_0 + 5;
200 }
201 (4) [x_2 = PHI <x_0, x_1>;]
202 (4a) t_2 = PHI <a_0, t_1>;
203 (5) [x_3 = x_2 + 1;]
204 (6r) a_1 = t_2 + 5;
205
206 where the bracketed instructions may go dead.
207
208 To recognize this opportunity, we have to observe that statement (6)
209 has a "hidden basis" (2). The hidden basis is unlike a normal basis
210 in that the statement and the hidden basis have different base SSA
211 names (x_2 and x_0, respectively). The relationship is established
212 when a statement's base name (x_2) is defined by a phi statement (4),
213 each argument of which (x_0, x_1) has an identical "derived base name."
214 If the argument is defined by a candidate (as x_1 is by (3)) that is a
215 CAND_ADD having a stride of 1, the derived base name of the argument is
216 the base name of the candidate (x_0). Otherwise, the argument itself
217 is its derived base name (as is the case with argument x_0).
218
219 The hidden basis for statement (6) is the nearest dominating candidate
220 whose base name is the derived base name (x_0) of the feeding phi (4),
221 and whose stride is identical to that of the statement. We can then
222 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
223 allowing the final replacement of (6) by the strength-reduced (6r).
224
225 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
226 A CAND_PHI is not a candidate for replacement, but is maintained in the
227 candidate table to ease discovery of hidden bases. Any phi statement
228 whose arguments share a common derived base name is entered into the
229 table with the derived base name, an (arbitrary) index of zero, and a
230 stride of 1. A statement with a hidden basis can then be detected by
231 simply looking up its feeding phi definition in the candidate table,
232 extracting the derived base name, and searching for a basis in the
233 usual manner after substituting the derived base name.
234
235 Note that the transformation is only valid when the original phi and
236 the statements that define the phi's arguments are all at the same
237 position in the loop hierarchy. */
238
239
240 /* Index into the candidate vector, offset by 1. VECs are zero-based,
241 while cand_idx's are one-based, with zero indicating null. */
242 typedef unsigned cand_idx;
243
244 /* The kind of candidate. */
245 enum cand_kind
246 {
247 CAND_MULT,
248 CAND_ADD,
249 CAND_REF,
250 CAND_PHI
251 };
252
253 struct slsr_cand_d
254 {
255 /* The candidate statement S1. */
256 gimple cand_stmt;
257
258 /* The base expression B: often an SSA name, but not always. */
259 tree base_expr;
260
261 /* The stride S. */
262 tree stride;
263
264 /* The index constant i. */
265 widest_int index;
266
267 /* The type of the candidate. This is normally the type of base_expr,
268 but casts may have occurred when combining feeding instructions.
269 A candidate can only be a basis for candidates of the same final type.
270 (For CAND_REFs, this is the type to be used for operand 1 of the
271 replacement MEM_REF.) */
272 tree cand_type;
273
274 /* The kind of candidate (CAND_MULT, etc.). */
275 enum cand_kind kind;
276
277 /* Index of this candidate in the candidate vector. */
278 cand_idx cand_num;
279
280 /* Index of the next candidate record for the same statement.
281 A statement may be useful in more than one way (e.g., due to
282 commutativity). So we can have multiple "interpretations"
283 of a statement. */
284 cand_idx next_interp;
285
286 /* Index of the basis statement S0, if any, in the candidate vector. */
287 cand_idx basis;
288
289 /* First candidate for which this candidate is a basis, if one exists. */
290 cand_idx dependent;
291
292 /* Next candidate having the same basis as this one. */
293 cand_idx sibling;
294
295 /* If this is a conditional candidate, the CAND_PHI candidate
296 that defines the base SSA name B. */
297 cand_idx def_phi;
298
299 /* Savings that can be expected from eliminating dead code if this
300 candidate is replaced. */
301 int dead_savings;
302 };
303
304 typedef struct slsr_cand_d slsr_cand, *slsr_cand_t;
305 typedef const struct slsr_cand_d *const_slsr_cand_t;
306
307 /* Pointers to candidates are chained together as part of a mapping
308 from base expressions to the candidates that use them. */
309
310 struct cand_chain_d
311 {
312 /* Base expression for the chain of candidates: often, but not
313 always, an SSA name. */
314 tree base_expr;
315
316 /* Pointer to a candidate. */
317 slsr_cand_t cand;
318
319 /* Chain pointer. */
320 struct cand_chain_d *next;
321
322 };
323
324 typedef struct cand_chain_d cand_chain, *cand_chain_t;
325 typedef const struct cand_chain_d *const_cand_chain_t;
326
327 /* Information about a unique "increment" associated with candidates
328 having an SSA name for a stride. An increment is the difference
329 between the index of the candidate and the index of its basis,
330 i.e., (i - i') as discussed in the module commentary.
331
332 When we are not going to generate address arithmetic we treat
333 increments that differ only in sign as the same, allowing sharing
334 of the cost of initializers. The absolute value of the increment
335 is stored in the incr_info. */
336
337 struct incr_info_d
338 {
339 /* The increment that relates a candidate to its basis. */
340 widest_int incr;
341
342 /* How many times the increment occurs in the candidate tree. */
343 unsigned count;
344
345 /* Cost of replacing candidates using this increment. Negative and
346 zero costs indicate replacement should be performed. */
347 int cost;
348
349 /* If this increment is profitable but is not -1, 0, or 1, it requires
350 an initializer T_0 = stride * incr to be found or introduced in the
351 nearest common dominator of all candidates. This field holds T_0
352 for subsequent use. */
353 tree initializer;
354
355 /* If the initializer was found to already exist, this is the block
356 where it was found. */
357 basic_block init_bb;
358 };
359
360 typedef struct incr_info_d incr_info, *incr_info_t;
361
362 /* Candidates are maintained in a vector. If candidate X dominates
363 candidate Y, then X appears before Y in the vector; but the
364 converse does not necessarily hold. */
365 static vec<slsr_cand_t> cand_vec;
366
367 enum cost_consts
368 {
369 COST_NEUTRAL = 0,
370 COST_INFINITE = 1000
371 };
372
373 enum stride_status
374 {
375 UNKNOWN_STRIDE = 0,
376 KNOWN_STRIDE = 1
377 };
378
379 enum phi_adjust_status
380 {
381 NOT_PHI_ADJUST = 0,
382 PHI_ADJUST = 1
383 };
384
385 enum count_phis_status
386 {
387 DONT_COUNT_PHIS = 0,
388 COUNT_PHIS = 1
389 };
390
391 /* Pointer map embodying a mapping from statements to candidates. */
392 static hash_map<gimple, slsr_cand_t> *stmt_cand_map;
393
394 /* Obstack for candidates. */
395 static struct obstack cand_obstack;
396
397 /* Obstack for candidate chains. */
398 static struct obstack chain_obstack;
399
400 /* An array INCR_VEC of incr_infos is used during analysis of related
401 candidates having an SSA name for a stride. INCR_VEC_LEN describes
402 its current length. MAX_INCR_VEC_LEN is used to avoid costly
403 pathological cases. */
404 static incr_info_t incr_vec;
405 static unsigned incr_vec_len;
406 const int MAX_INCR_VEC_LEN = 16;
407
408 /* For a chain of candidates with unknown stride, indicates whether or not
409 we must generate pointer arithmetic when replacing statements. */
410 static bool address_arithmetic_p;
411
412 /* Forward function declarations. */
413 static slsr_cand_t base_cand_from_table (tree);
414 static tree introduce_cast_before_cand (slsr_cand_t, tree, tree);
415 static bool legal_cast_p_1 (tree, tree);
416 \f
417 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
418
419 static slsr_cand_t
420 lookup_cand (cand_idx idx)
421 {
422 return cand_vec[idx - 1];
423 }
424
425 /* Helper for hashing a candidate chain header. */
426
427 struct cand_chain_hasher : typed_noop_remove <cand_chain>
428 {
429 typedef cand_chain *value_type;
430 typedef cand_chain *compare_type;
431 static inline hashval_t hash (const cand_chain *);
432 static inline bool equal (const cand_chain *, const cand_chain *);
433 };
434
435 inline hashval_t
436 cand_chain_hasher::hash (const cand_chain *p)
437 {
438 tree base_expr = p->base_expr;
439 return iterative_hash_expr (base_expr, 0);
440 }
441
442 inline bool
443 cand_chain_hasher::equal (const cand_chain *chain1, const cand_chain *chain2)
444 {
445 return operand_equal_p (chain1->base_expr, chain2->base_expr, 0);
446 }
447
448 /* Hash table embodying a mapping from base exprs to chains of candidates. */
449 static hash_table<cand_chain_hasher> *base_cand_map;
450 \f
451 /* Pointer map used by tree_to_aff_combination_expand. */
452 static hash_map<tree, name_expansion *> *name_expansions;
453 /* Pointer map embodying a mapping from bases to alternative bases. */
454 static hash_map<tree, tree> *alt_base_map;
455
456 /* Given BASE, use the tree affine combiniation facilities to
457 find the underlying tree expression for BASE, with any
458 immediate offset excluded.
459
460 N.B. we should eliminate this backtracking with better forward
461 analysis in a future release. */
462
463 static tree
464 get_alternative_base (tree base)
465 {
466 tree *result = alt_base_map->get (base);
467
468 if (result == NULL)
469 {
470 tree expr;
471 aff_tree aff;
472
473 tree_to_aff_combination_expand (base, TREE_TYPE (base),
474 &aff, &name_expansions);
475 aff.offset = 0;
476 expr = aff_combination_to_tree (&aff);
477
478 gcc_assert (!alt_base_map->put (base, base == expr ? NULL : expr));
479
480 return expr == base ? NULL : expr;
481 }
482
483 return *result;
484 }
485
486 /* Look in the candidate table for a CAND_PHI that defines BASE and
487 return it if found; otherwise return NULL. */
488
489 static cand_idx
490 find_phi_def (tree base)
491 {
492 slsr_cand_t c;
493
494 if (TREE_CODE (base) != SSA_NAME)
495 return 0;
496
497 c = base_cand_from_table (base);
498
499 if (!c || c->kind != CAND_PHI)
500 return 0;
501
502 return c->cand_num;
503 }
504
505 /* Helper routine for find_basis_for_candidate. May be called twice:
506 once for the candidate's base expr, and optionally again either for
507 the candidate's phi definition or for a CAND_REF's alternative base
508 expression. */
509
510 static slsr_cand_t
511 find_basis_for_base_expr (slsr_cand_t c, tree base_expr)
512 {
513 cand_chain mapping_key;
514 cand_chain_t chain;
515 slsr_cand_t basis = NULL;
516
517 // Limit potential of N^2 behavior for long candidate chains.
518 int iters = 0;
519 int max_iters = PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN);
520
521 mapping_key.base_expr = base_expr;
522 chain = base_cand_map->find (&mapping_key);
523
524 for (; chain && iters < max_iters; chain = chain->next, ++iters)
525 {
526 slsr_cand_t one_basis = chain->cand;
527
528 if (one_basis->kind != c->kind
529 || one_basis->cand_stmt == c->cand_stmt
530 || !operand_equal_p (one_basis->stride, c->stride, 0)
531 || !types_compatible_p (one_basis->cand_type, c->cand_type)
532 || !dominated_by_p (CDI_DOMINATORS,
533 gimple_bb (c->cand_stmt),
534 gimple_bb (one_basis->cand_stmt)))
535 continue;
536
537 if (!basis || basis->cand_num < one_basis->cand_num)
538 basis = one_basis;
539 }
540
541 return basis;
542 }
543
544 /* Use the base expr from candidate C to look for possible candidates
545 that can serve as a basis for C. Each potential basis must also
546 appear in a block that dominates the candidate statement and have
547 the same stride and type. If more than one possible basis exists,
548 the one with highest index in the vector is chosen; this will be
549 the most immediately dominating basis. */
550
551 static int
552 find_basis_for_candidate (slsr_cand_t c)
553 {
554 slsr_cand_t basis = find_basis_for_base_expr (c, c->base_expr);
555
556 /* If a candidate doesn't have a basis using its base expression,
557 it may have a basis hidden by one or more intervening phis. */
558 if (!basis && c->def_phi)
559 {
560 basic_block basis_bb, phi_bb;
561 slsr_cand_t phi_cand = lookup_cand (c->def_phi);
562 basis = find_basis_for_base_expr (c, phi_cand->base_expr);
563
564 if (basis)
565 {
566 /* A hidden basis must dominate the phi-definition of the
567 candidate's base name. */
568 phi_bb = gimple_bb (phi_cand->cand_stmt);
569 basis_bb = gimple_bb (basis->cand_stmt);
570
571 if (phi_bb == basis_bb
572 || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
573 {
574 basis = NULL;
575 c->basis = 0;
576 }
577
578 /* If we found a hidden basis, estimate additional dead-code
579 savings if the phi and its feeding statements can be removed. */
580 if (basis && has_single_use (gimple_phi_result (phi_cand->cand_stmt)))
581 c->dead_savings += phi_cand->dead_savings;
582 }
583 }
584
585 if (flag_expensive_optimizations && !basis && c->kind == CAND_REF)
586 {
587 tree alt_base_expr = get_alternative_base (c->base_expr);
588 if (alt_base_expr)
589 basis = find_basis_for_base_expr (c, alt_base_expr);
590 }
591
592 if (basis)
593 {
594 c->sibling = basis->dependent;
595 basis->dependent = c->cand_num;
596 return basis->cand_num;
597 }
598
599 return 0;
600 }
601
602 /* Record a mapping from BASE to C, indicating that C may potentially serve
603 as a basis using that base expression. BASE may be the same as
604 C->BASE_EXPR; alternatively BASE can be a different tree that share the
605 underlining expression of C->BASE_EXPR. */
606
607 static void
608 record_potential_basis (slsr_cand_t c, tree base)
609 {
610 cand_chain_t node;
611 cand_chain **slot;
612
613 gcc_assert (base);
614
615 node = (cand_chain_t) obstack_alloc (&chain_obstack, sizeof (cand_chain));
616 node->base_expr = base;
617 node->cand = c;
618 node->next = NULL;
619 slot = base_cand_map->find_slot (node, INSERT);
620
621 if (*slot)
622 {
623 cand_chain_t head = (cand_chain_t) (*slot);
624 node->next = head->next;
625 head->next = node;
626 }
627 else
628 *slot = node;
629 }
630
631 /* Allocate storage for a new candidate and initialize its fields.
632 Attempt to find a basis for the candidate.
633
634 For CAND_REF, an alternative base may also be recorded and used
635 to find a basis. This helps cases where the expression hidden
636 behind BASE (which is usually an SSA_NAME) has immediate offset,
637 e.g.
638
639 a2[i][j] = 1;
640 a2[i + 20][j] = 2; */
641
642 static slsr_cand_t
643 alloc_cand_and_find_basis (enum cand_kind kind, gimple gs, tree base,
644 const widest_int &index, tree stride, tree ctype,
645 unsigned savings)
646 {
647 slsr_cand_t c = (slsr_cand_t) obstack_alloc (&cand_obstack,
648 sizeof (slsr_cand));
649 c->cand_stmt = gs;
650 c->base_expr = base;
651 c->stride = stride;
652 c->index = index;
653 c->cand_type = ctype;
654 c->kind = kind;
655 c->cand_num = cand_vec.length () + 1;
656 c->next_interp = 0;
657 c->dependent = 0;
658 c->sibling = 0;
659 c->def_phi = kind == CAND_MULT ? find_phi_def (base) : 0;
660 c->dead_savings = savings;
661
662 cand_vec.safe_push (c);
663
664 if (kind == CAND_PHI)
665 c->basis = 0;
666 else
667 c->basis = find_basis_for_candidate (c);
668
669 record_potential_basis (c, base);
670 if (flag_expensive_optimizations && kind == CAND_REF)
671 {
672 tree alt_base = get_alternative_base (base);
673 if (alt_base)
674 record_potential_basis (c, alt_base);
675 }
676
677 return c;
678 }
679
680 /* Determine the target cost of statement GS when compiling according
681 to SPEED. */
682
683 static int
684 stmt_cost (gimple gs, bool speed)
685 {
686 tree lhs, rhs1, rhs2;
687 machine_mode lhs_mode;
688
689 gcc_assert (is_gimple_assign (gs));
690 lhs = gimple_assign_lhs (gs);
691 rhs1 = gimple_assign_rhs1 (gs);
692 lhs_mode = TYPE_MODE (TREE_TYPE (lhs));
693
694 switch (gimple_assign_rhs_code (gs))
695 {
696 case MULT_EXPR:
697 rhs2 = gimple_assign_rhs2 (gs);
698
699 if (tree_fits_shwi_p (rhs2))
700 return mult_by_coeff_cost (tree_to_shwi (rhs2), lhs_mode, speed);
701
702 gcc_assert (TREE_CODE (rhs1) != INTEGER_CST);
703 return mul_cost (speed, lhs_mode);
704
705 case PLUS_EXPR:
706 case POINTER_PLUS_EXPR:
707 case MINUS_EXPR:
708 return add_cost (speed, lhs_mode);
709
710 case NEGATE_EXPR:
711 return neg_cost (speed, lhs_mode);
712
713 CASE_CONVERT:
714 return convert_cost (lhs_mode, TYPE_MODE (TREE_TYPE (rhs1)), speed);
715
716 /* Note that we don't assign costs to copies that in most cases
717 will go away. */
718 default:
719 ;
720 }
721
722 gcc_unreachable ();
723 return 0;
724 }
725
726 /* Look up the defining statement for BASE_IN and return a pointer
727 to its candidate in the candidate table, if any; otherwise NULL.
728 Only CAND_ADD and CAND_MULT candidates are returned. */
729
730 static slsr_cand_t
731 base_cand_from_table (tree base_in)
732 {
733 slsr_cand_t *result;
734
735 gimple def = SSA_NAME_DEF_STMT (base_in);
736 if (!def)
737 return (slsr_cand_t) NULL;
738
739 result = stmt_cand_map->get (def);
740
741 if (result && (*result)->kind != CAND_REF)
742 return *result;
743
744 return (slsr_cand_t) NULL;
745 }
746
747 /* Add an entry to the statement-to-candidate mapping. */
748
749 static void
750 add_cand_for_stmt (gimple gs, slsr_cand_t c)
751 {
752 gcc_assert (!stmt_cand_map->put (gs, c));
753 }
754 \f
755 /* Given PHI which contains a phi statement, determine whether it
756 satisfies all the requirements of a phi candidate. If so, create
757 a candidate. Note that a CAND_PHI never has a basis itself, but
758 is used to help find a basis for subsequent candidates. */
759
760 static void
761 slsr_process_phi (gphi *phi, bool speed)
762 {
763 unsigned i;
764 tree arg0_base = NULL_TREE, base_type;
765 slsr_cand_t c;
766 struct loop *cand_loop = gimple_bb (phi)->loop_father;
767 unsigned savings = 0;
768
769 /* A CAND_PHI requires each of its arguments to have the same
770 derived base name. (See the module header commentary for a
771 definition of derived base names.) Furthermore, all feeding
772 definitions must be in the same position in the loop hierarchy
773 as PHI. */
774
775 for (i = 0; i < gimple_phi_num_args (phi); i++)
776 {
777 slsr_cand_t arg_cand;
778 tree arg = gimple_phi_arg_def (phi, i);
779 tree derived_base_name = NULL_TREE;
780 gimple arg_stmt = NULL;
781 basic_block arg_bb = NULL;
782
783 if (TREE_CODE (arg) != SSA_NAME)
784 return;
785
786 arg_cand = base_cand_from_table (arg);
787
788 if (arg_cand)
789 {
790 while (arg_cand->kind != CAND_ADD && arg_cand->kind != CAND_PHI)
791 {
792 if (!arg_cand->next_interp)
793 return;
794
795 arg_cand = lookup_cand (arg_cand->next_interp);
796 }
797
798 if (!integer_onep (arg_cand->stride))
799 return;
800
801 derived_base_name = arg_cand->base_expr;
802 arg_stmt = arg_cand->cand_stmt;
803 arg_bb = gimple_bb (arg_stmt);
804
805 /* Gather potential dead code savings if the phi statement
806 can be removed later on. */
807 if (has_single_use (arg))
808 {
809 if (gimple_code (arg_stmt) == GIMPLE_PHI)
810 savings += arg_cand->dead_savings;
811 else
812 savings += stmt_cost (arg_stmt, speed);
813 }
814 }
815 else
816 {
817 derived_base_name = arg;
818
819 if (SSA_NAME_IS_DEFAULT_DEF (arg))
820 arg_bb = single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun));
821 else
822 gimple_bb (SSA_NAME_DEF_STMT (arg));
823 }
824
825 if (!arg_bb || arg_bb->loop_father != cand_loop)
826 return;
827
828 if (i == 0)
829 arg0_base = derived_base_name;
830 else if (!operand_equal_p (derived_base_name, arg0_base, 0))
831 return;
832 }
833
834 /* Create the candidate. "alloc_cand_and_find_basis" is named
835 misleadingly for this case, as no basis will be sought for a
836 CAND_PHI. */
837 base_type = TREE_TYPE (arg0_base);
838
839 c = alloc_cand_and_find_basis (CAND_PHI, phi, arg0_base,
840 0, integer_one_node, base_type, savings);
841
842 /* Add the candidate to the statement-candidate mapping. */
843 add_cand_for_stmt (phi, c);
844 }
845
846 /* Given PBASE which is a pointer to tree, look up the defining
847 statement for it and check whether the candidate is in the
848 form of:
849
850 X = B + (1 * S), S is integer constant
851 X = B + (i * S), S is integer one
852
853 If so, set PBASE to the candidate's base_expr and return double
854 int (i * S).
855 Otherwise, just return double int zero. */
856
857 static widest_int
858 backtrace_base_for_ref (tree *pbase)
859 {
860 tree base_in = *pbase;
861 slsr_cand_t base_cand;
862
863 STRIP_NOPS (base_in);
864
865 /* Strip off widening conversion(s) to handle cases where
866 e.g. 'B' is widened from an 'int' in order to calculate
867 a 64-bit address. */
868 if (CONVERT_EXPR_P (base_in)
869 && legal_cast_p_1 (base_in, TREE_OPERAND (base_in, 0)))
870 base_in = get_unwidened (base_in, NULL_TREE);
871
872 if (TREE_CODE (base_in) != SSA_NAME)
873 return 0;
874
875 base_cand = base_cand_from_table (base_in);
876
877 while (base_cand && base_cand->kind != CAND_PHI)
878 {
879 if (base_cand->kind == CAND_ADD
880 && base_cand->index == 1
881 && TREE_CODE (base_cand->stride) == INTEGER_CST)
882 {
883 /* X = B + (1 * S), S is integer constant. */
884 *pbase = base_cand->base_expr;
885 return wi::to_widest (base_cand->stride);
886 }
887 else if (base_cand->kind == CAND_ADD
888 && TREE_CODE (base_cand->stride) == INTEGER_CST
889 && integer_onep (base_cand->stride))
890 {
891 /* X = B + (i * S), S is integer one. */
892 *pbase = base_cand->base_expr;
893 return base_cand->index;
894 }
895
896 if (base_cand->next_interp)
897 base_cand = lookup_cand (base_cand->next_interp);
898 else
899 base_cand = NULL;
900 }
901
902 return 0;
903 }
904
905 /* Look for the following pattern:
906
907 *PBASE: MEM_REF (T1, C1)
908
909 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
910 or
911 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
912 or
913 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
914
915 *PINDEX: C4 * BITS_PER_UNIT
916
917 If not present, leave the input values unchanged and return FALSE.
918 Otherwise, modify the input values as follows and return TRUE:
919
920 *PBASE: T1
921 *POFFSET: MULT_EXPR (T2, C3)
922 *PINDEX: C1 + (C2 * C3) + C4
923
924 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
925 will be further restructured to:
926
927 *PBASE: T1
928 *POFFSET: MULT_EXPR (T2', C3)
929 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
930
931 static bool
932 restructure_reference (tree *pbase, tree *poffset, widest_int *pindex,
933 tree *ptype)
934 {
935 tree base = *pbase, offset = *poffset;
936 widest_int index = *pindex;
937 tree mult_op0, t1, t2, type;
938 widest_int c1, c2, c3, c4, c5;
939
940 if (!base
941 || !offset
942 || TREE_CODE (base) != MEM_REF
943 || TREE_CODE (offset) != MULT_EXPR
944 || TREE_CODE (TREE_OPERAND (offset, 1)) != INTEGER_CST
945 || wi::umod_floor (index, BITS_PER_UNIT) != 0)
946 return false;
947
948 t1 = TREE_OPERAND (base, 0);
949 c1 = widest_int::from (mem_ref_offset (base), SIGNED);
950 type = TREE_TYPE (TREE_OPERAND (base, 1));
951
952 mult_op0 = TREE_OPERAND (offset, 0);
953 c3 = wi::to_widest (TREE_OPERAND (offset, 1));
954
955 if (TREE_CODE (mult_op0) == PLUS_EXPR)
956
957 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
958 {
959 t2 = TREE_OPERAND (mult_op0, 0);
960 c2 = wi::to_widest (TREE_OPERAND (mult_op0, 1));
961 }
962 else
963 return false;
964
965 else if (TREE_CODE (mult_op0) == MINUS_EXPR)
966
967 if (TREE_CODE (TREE_OPERAND (mult_op0, 1)) == INTEGER_CST)
968 {
969 t2 = TREE_OPERAND (mult_op0, 0);
970 c2 = -wi::to_widest (TREE_OPERAND (mult_op0, 1));
971 }
972 else
973 return false;
974
975 else
976 {
977 t2 = mult_op0;
978 c2 = 0;
979 }
980
981 c4 = wi::lrshift (index, LOG2_BITS_PER_UNIT);
982 c5 = backtrace_base_for_ref (&t2);
983
984 *pbase = t1;
985 *poffset = fold_build2 (MULT_EXPR, sizetype, fold_convert (sizetype, t2),
986 wide_int_to_tree (sizetype, c3));
987 *pindex = c1 + c2 * c3 + c4 + c5 * c3;
988 *ptype = type;
989
990 return true;
991 }
992
993 /* Given GS which contains a data reference, create a CAND_REF entry in
994 the candidate table and attempt to find a basis. */
995
996 static void
997 slsr_process_ref (gimple gs)
998 {
999 tree ref_expr, base, offset, type;
1000 HOST_WIDE_INT bitsize, bitpos;
1001 machine_mode mode;
1002 int unsignedp, volatilep;
1003 slsr_cand_t c;
1004
1005 if (gimple_vdef (gs))
1006 ref_expr = gimple_assign_lhs (gs);
1007 else
1008 ref_expr = gimple_assign_rhs1 (gs);
1009
1010 if (!handled_component_p (ref_expr)
1011 || TREE_CODE (ref_expr) == BIT_FIELD_REF
1012 || (TREE_CODE (ref_expr) == COMPONENT_REF
1013 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr, 1))))
1014 return;
1015
1016 base = get_inner_reference (ref_expr, &bitsize, &bitpos, &offset, &mode,
1017 &unsignedp, &volatilep, false);
1018 widest_int index = bitpos;
1019
1020 if (!restructure_reference (&base, &offset, &index, &type))
1021 return;
1022
1023 c = alloc_cand_and_find_basis (CAND_REF, gs, base, index, offset,
1024 type, 0);
1025
1026 /* Add the candidate to the statement-candidate mapping. */
1027 add_cand_for_stmt (gs, c);
1028 }
1029
1030 /* Create a candidate entry for a statement GS, where GS multiplies
1031 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
1032 about the two SSA names into the new candidate. Return the new
1033 candidate. */
1034
1035 static slsr_cand_t
1036 create_mul_ssa_cand (gimple gs, tree base_in, tree stride_in, bool speed)
1037 {
1038 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1039 widest_int index;
1040 unsigned savings = 0;
1041 slsr_cand_t c;
1042 slsr_cand_t base_cand = base_cand_from_table (base_in);
1043
1044 /* Look at all interpretations of the base candidate, if necessary,
1045 to find information to propagate into this candidate. */
1046 while (base_cand && !base && base_cand->kind != CAND_PHI)
1047 {
1048
1049 if (base_cand->kind == CAND_MULT && integer_onep (base_cand->stride))
1050 {
1051 /* Y = (B + i') * 1
1052 X = Y * Z
1053 ================
1054 X = (B + i') * Z */
1055 base = base_cand->base_expr;
1056 index = base_cand->index;
1057 stride = stride_in;
1058 ctype = base_cand->cand_type;
1059 if (has_single_use (base_in))
1060 savings = (base_cand->dead_savings
1061 + stmt_cost (base_cand->cand_stmt, speed));
1062 }
1063 else if (base_cand->kind == CAND_ADD
1064 && TREE_CODE (base_cand->stride) == INTEGER_CST)
1065 {
1066 /* Y = B + (i' * S), S constant
1067 X = Y * Z
1068 ============================
1069 X = B + ((i' * S) * Z) */
1070 base = base_cand->base_expr;
1071 index = base_cand->index * wi::to_widest (base_cand->stride);
1072 stride = stride_in;
1073 ctype = base_cand->cand_type;
1074 if (has_single_use (base_in))
1075 savings = (base_cand->dead_savings
1076 + stmt_cost (base_cand->cand_stmt, speed));
1077 }
1078
1079 if (base_cand->next_interp)
1080 base_cand = lookup_cand (base_cand->next_interp);
1081 else
1082 base_cand = NULL;
1083 }
1084
1085 if (!base)
1086 {
1087 /* No interpretations had anything useful to propagate, so
1088 produce X = (Y + 0) * Z. */
1089 base = base_in;
1090 index = 0;
1091 stride = stride_in;
1092 ctype = TREE_TYPE (base_in);
1093 }
1094
1095 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
1096 ctype, savings);
1097 return c;
1098 }
1099
1100 /* Create a candidate entry for a statement GS, where GS multiplies
1101 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1102 information about BASE_IN into the new candidate. Return the new
1103 candidate. */
1104
1105 static slsr_cand_t
1106 create_mul_imm_cand (gimple gs, tree base_in, tree stride_in, bool speed)
1107 {
1108 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1109 widest_int index, temp;
1110 unsigned savings = 0;
1111 slsr_cand_t c;
1112 slsr_cand_t base_cand = base_cand_from_table (base_in);
1113
1114 /* Look at all interpretations of the base candidate, if necessary,
1115 to find information to propagate into this candidate. */
1116 while (base_cand && !base && base_cand->kind != CAND_PHI)
1117 {
1118 if (base_cand->kind == CAND_MULT
1119 && TREE_CODE (base_cand->stride) == INTEGER_CST)
1120 {
1121 /* Y = (B + i') * S, S constant
1122 X = Y * c
1123 ============================
1124 X = (B + i') * (S * c) */
1125 temp = wi::to_widest (base_cand->stride) * wi::to_widest (stride_in);
1126 if (wi::fits_to_tree_p (temp, TREE_TYPE (stride_in)))
1127 {
1128 base = base_cand->base_expr;
1129 index = base_cand->index;
1130 stride = wide_int_to_tree (TREE_TYPE (stride_in), temp);
1131 ctype = base_cand->cand_type;
1132 if (has_single_use (base_in))
1133 savings = (base_cand->dead_savings
1134 + stmt_cost (base_cand->cand_stmt, speed));
1135 }
1136 }
1137 else if (base_cand->kind == CAND_ADD && integer_onep (base_cand->stride))
1138 {
1139 /* Y = B + (i' * 1)
1140 X = Y * c
1141 ===========================
1142 X = (B + i') * c */
1143 base = base_cand->base_expr;
1144 index = base_cand->index;
1145 stride = stride_in;
1146 ctype = base_cand->cand_type;
1147 if (has_single_use (base_in))
1148 savings = (base_cand->dead_savings
1149 + stmt_cost (base_cand->cand_stmt, speed));
1150 }
1151 else if (base_cand->kind == CAND_ADD
1152 && base_cand->index == 1
1153 && TREE_CODE (base_cand->stride) == INTEGER_CST)
1154 {
1155 /* Y = B + (1 * S), S constant
1156 X = Y * c
1157 ===========================
1158 X = (B + S) * c */
1159 base = base_cand->base_expr;
1160 index = wi::to_widest (base_cand->stride);
1161 stride = stride_in;
1162 ctype = base_cand->cand_type;
1163 if (has_single_use (base_in))
1164 savings = (base_cand->dead_savings
1165 + stmt_cost (base_cand->cand_stmt, speed));
1166 }
1167
1168 if (base_cand->next_interp)
1169 base_cand = lookup_cand (base_cand->next_interp);
1170 else
1171 base_cand = NULL;
1172 }
1173
1174 if (!base)
1175 {
1176 /* No interpretations had anything useful to propagate, so
1177 produce X = (Y + 0) * c. */
1178 base = base_in;
1179 index = 0;
1180 stride = stride_in;
1181 ctype = TREE_TYPE (base_in);
1182 }
1183
1184 c = alloc_cand_and_find_basis (CAND_MULT, gs, base, index, stride,
1185 ctype, savings);
1186 return c;
1187 }
1188
1189 /* Given GS which is a multiply of scalar integers, make an appropriate
1190 entry in the candidate table. If this is a multiply of two SSA names,
1191 create two CAND_MULT interpretations and attempt to find a basis for
1192 each of them. Otherwise, create a single CAND_MULT and attempt to
1193 find a basis. */
1194
1195 static void
1196 slsr_process_mul (gimple gs, tree rhs1, tree rhs2, bool speed)
1197 {
1198 slsr_cand_t c, c2;
1199
1200 /* If this is a multiply of an SSA name with itself, it is highly
1201 unlikely that we will get a strength reduction opportunity, so
1202 don't record it as a candidate. This simplifies the logic for
1203 finding a basis, so if this is removed that must be considered. */
1204 if (rhs1 == rhs2)
1205 return;
1206
1207 if (TREE_CODE (rhs2) == SSA_NAME)
1208 {
1209 /* Record an interpretation of this statement in the candidate table
1210 assuming RHS1 is the base expression and RHS2 is the stride. */
1211 c = create_mul_ssa_cand (gs, rhs1, rhs2, speed);
1212
1213 /* Add the first interpretation to the statement-candidate mapping. */
1214 add_cand_for_stmt (gs, c);
1215
1216 /* Record another interpretation of this statement assuming RHS1
1217 is the stride and RHS2 is the base expression. */
1218 c2 = create_mul_ssa_cand (gs, rhs2, rhs1, speed);
1219 c->next_interp = c2->cand_num;
1220 }
1221 else
1222 {
1223 /* Record an interpretation for the multiply-immediate. */
1224 c = create_mul_imm_cand (gs, rhs1, rhs2, speed);
1225
1226 /* Add the interpretation to the statement-candidate mapping. */
1227 add_cand_for_stmt (gs, c);
1228 }
1229 }
1230
1231 /* Create a candidate entry for a statement GS, where GS adds two
1232 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1233 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1234 information about the two SSA names into the new candidate.
1235 Return the new candidate. */
1236
1237 static slsr_cand_t
1238 create_add_ssa_cand (gimple gs, tree base_in, tree addend_in,
1239 bool subtract_p, bool speed)
1240 {
1241 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL;
1242 widest_int index;
1243 unsigned savings = 0;
1244 slsr_cand_t c;
1245 slsr_cand_t base_cand = base_cand_from_table (base_in);
1246 slsr_cand_t addend_cand = base_cand_from_table (addend_in);
1247
1248 /* The most useful transformation is a multiply-immediate feeding
1249 an add or subtract. Look for that first. */
1250 while (addend_cand && !base && addend_cand->kind != CAND_PHI)
1251 {
1252 if (addend_cand->kind == CAND_MULT
1253 && addend_cand->index == 0
1254 && TREE_CODE (addend_cand->stride) == INTEGER_CST)
1255 {
1256 /* Z = (B + 0) * S, S constant
1257 X = Y +/- Z
1258 ===========================
1259 X = Y + ((+/-1 * S) * B) */
1260 base = base_in;
1261 index = wi::to_widest (addend_cand->stride);
1262 if (subtract_p)
1263 index = -index;
1264 stride = addend_cand->base_expr;
1265 ctype = TREE_TYPE (base_in);
1266 if (has_single_use (addend_in))
1267 savings = (addend_cand->dead_savings
1268 + stmt_cost (addend_cand->cand_stmt, speed));
1269 }
1270
1271 if (addend_cand->next_interp)
1272 addend_cand = lookup_cand (addend_cand->next_interp);
1273 else
1274 addend_cand = NULL;
1275 }
1276
1277 while (base_cand && !base && base_cand->kind != CAND_PHI)
1278 {
1279 if (base_cand->kind == CAND_ADD
1280 && (base_cand->index == 0
1281 || operand_equal_p (base_cand->stride,
1282 integer_zero_node, 0)))
1283 {
1284 /* Y = B + (i' * S), i' * S = 0
1285 X = Y +/- Z
1286 ============================
1287 X = B + (+/-1 * Z) */
1288 base = base_cand->base_expr;
1289 index = subtract_p ? -1 : 1;
1290 stride = addend_in;
1291 ctype = base_cand->cand_type;
1292 if (has_single_use (base_in))
1293 savings = (base_cand->dead_savings
1294 + stmt_cost (base_cand->cand_stmt, speed));
1295 }
1296 else if (subtract_p)
1297 {
1298 slsr_cand_t subtrahend_cand = base_cand_from_table (addend_in);
1299
1300 while (subtrahend_cand && !base && subtrahend_cand->kind != CAND_PHI)
1301 {
1302 if (subtrahend_cand->kind == CAND_MULT
1303 && subtrahend_cand->index == 0
1304 && TREE_CODE (subtrahend_cand->stride) == INTEGER_CST)
1305 {
1306 /* Z = (B + 0) * S, S constant
1307 X = Y - Z
1308 ===========================
1309 Value: X = Y + ((-1 * S) * B) */
1310 base = base_in;
1311 index = wi::to_widest (subtrahend_cand->stride);
1312 index = -index;
1313 stride = subtrahend_cand->base_expr;
1314 ctype = TREE_TYPE (base_in);
1315 if (has_single_use (addend_in))
1316 savings = (subtrahend_cand->dead_savings
1317 + stmt_cost (subtrahend_cand->cand_stmt, speed));
1318 }
1319
1320 if (subtrahend_cand->next_interp)
1321 subtrahend_cand = lookup_cand (subtrahend_cand->next_interp);
1322 else
1323 subtrahend_cand = NULL;
1324 }
1325 }
1326
1327 if (base_cand->next_interp)
1328 base_cand = lookup_cand (base_cand->next_interp);
1329 else
1330 base_cand = NULL;
1331 }
1332
1333 if (!base)
1334 {
1335 /* No interpretations had anything useful to propagate, so
1336 produce X = Y + (1 * Z). */
1337 base = base_in;
1338 index = subtract_p ? -1 : 1;
1339 stride = addend_in;
1340 ctype = TREE_TYPE (base_in);
1341 }
1342
1343 c = alloc_cand_and_find_basis (CAND_ADD, gs, base, index, stride,
1344 ctype, savings);
1345 return c;
1346 }
1347
1348 /* Create a candidate entry for a statement GS, where GS adds SSA
1349 name BASE_IN to constant INDEX_IN. Propagate any known information
1350 about BASE_IN into the new candidate. Return the new candidate. */
1351
1352 static slsr_cand_t
1353 create_add_imm_cand (gimple gs, tree base_in, const widest_int &index_in,
1354 bool speed)
1355 {
1356 enum cand_kind kind = CAND_ADD;
1357 tree base = NULL_TREE, stride = NULL_TREE, ctype = NULL_TREE;
1358 widest_int index, multiple;
1359 unsigned savings = 0;
1360 slsr_cand_t c;
1361 slsr_cand_t base_cand = base_cand_from_table (base_in);
1362
1363 while (base_cand && !base && base_cand->kind != CAND_PHI)
1364 {
1365 signop sign = TYPE_SIGN (TREE_TYPE (base_cand->stride));
1366
1367 if (TREE_CODE (base_cand->stride) == INTEGER_CST
1368 && wi::multiple_of_p (index_in, wi::to_widest (base_cand->stride),
1369 sign, &multiple))
1370 {
1371 /* Y = (B + i') * S, S constant, c = kS for some integer k
1372 X = Y + c
1373 ============================
1374 X = (B + (i'+ k)) * S
1375 OR
1376 Y = B + (i' * S), S constant, c = kS for some integer k
1377 X = Y + c
1378 ============================
1379 X = (B + (i'+ k)) * S */
1380 kind = base_cand->kind;
1381 base = base_cand->base_expr;
1382 index = base_cand->index + multiple;
1383 stride = base_cand->stride;
1384 ctype = base_cand->cand_type;
1385 if (has_single_use (base_in))
1386 savings = (base_cand->dead_savings
1387 + stmt_cost (base_cand->cand_stmt, speed));
1388 }
1389
1390 if (base_cand->next_interp)
1391 base_cand = lookup_cand (base_cand->next_interp);
1392 else
1393 base_cand = NULL;
1394 }
1395
1396 if (!base)
1397 {
1398 /* No interpretations had anything useful to propagate, so
1399 produce X = Y + (c * 1). */
1400 kind = CAND_ADD;
1401 base = base_in;
1402 index = index_in;
1403 stride = integer_one_node;
1404 ctype = TREE_TYPE (base_in);
1405 }
1406
1407 c = alloc_cand_and_find_basis (kind, gs, base, index, stride,
1408 ctype, savings);
1409 return c;
1410 }
1411
1412 /* Given GS which is an add or subtract of scalar integers or pointers,
1413 make at least one appropriate entry in the candidate table. */
1414
1415 static void
1416 slsr_process_add (gimple gs, tree rhs1, tree rhs2, bool speed)
1417 {
1418 bool subtract_p = gimple_assign_rhs_code (gs) == MINUS_EXPR;
1419 slsr_cand_t c = NULL, c2;
1420
1421 if (TREE_CODE (rhs2) == SSA_NAME)
1422 {
1423 /* First record an interpretation assuming RHS1 is the base expression
1424 and RHS2 is the stride. But it doesn't make sense for the
1425 stride to be a pointer, so don't record a candidate in that case. */
1426 if (!POINTER_TYPE_P (TREE_TYPE (rhs2)))
1427 {
1428 c = create_add_ssa_cand (gs, rhs1, rhs2, subtract_p, speed);
1429
1430 /* Add the first interpretation to the statement-candidate
1431 mapping. */
1432 add_cand_for_stmt (gs, c);
1433 }
1434
1435 /* If the two RHS operands are identical, or this is a subtract,
1436 we're done. */
1437 if (operand_equal_p (rhs1, rhs2, 0) || subtract_p)
1438 return;
1439
1440 /* Otherwise, record another interpretation assuming RHS2 is the
1441 base expression and RHS1 is the stride, again provided that the
1442 stride is not a pointer. */
1443 if (!POINTER_TYPE_P (TREE_TYPE (rhs1)))
1444 {
1445 c2 = create_add_ssa_cand (gs, rhs2, rhs1, false, speed);
1446 if (c)
1447 c->next_interp = c2->cand_num;
1448 else
1449 add_cand_for_stmt (gs, c2);
1450 }
1451 }
1452 else
1453 {
1454 /* Record an interpretation for the add-immediate. */
1455 widest_int index = wi::to_widest (rhs2);
1456 if (subtract_p)
1457 index = -index;
1458
1459 c = create_add_imm_cand (gs, rhs1, index, speed);
1460
1461 /* Add the interpretation to the statement-candidate mapping. */
1462 add_cand_for_stmt (gs, c);
1463 }
1464 }
1465
1466 /* Given GS which is a negate of a scalar integer, make an appropriate
1467 entry in the candidate table. A negate is equivalent to a multiply
1468 by -1. */
1469
1470 static void
1471 slsr_process_neg (gimple gs, tree rhs1, bool speed)
1472 {
1473 /* Record a CAND_MULT interpretation for the multiply by -1. */
1474 slsr_cand_t c = create_mul_imm_cand (gs, rhs1, integer_minus_one_node, speed);
1475
1476 /* Add the interpretation to the statement-candidate mapping. */
1477 add_cand_for_stmt (gs, c);
1478 }
1479
1480 /* Help function for legal_cast_p, operating on two trees. Checks
1481 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1482 for more details. */
1483
1484 static bool
1485 legal_cast_p_1 (tree lhs, tree rhs)
1486 {
1487 tree lhs_type, rhs_type;
1488 unsigned lhs_size, rhs_size;
1489 bool lhs_wraps, rhs_wraps;
1490
1491 lhs_type = TREE_TYPE (lhs);
1492 rhs_type = TREE_TYPE (rhs);
1493 lhs_size = TYPE_PRECISION (lhs_type);
1494 rhs_size = TYPE_PRECISION (rhs_type);
1495 lhs_wraps = ANY_INTEGRAL_TYPE_P (lhs_type) && TYPE_OVERFLOW_WRAPS (lhs_type);
1496 rhs_wraps = ANY_INTEGRAL_TYPE_P (rhs_type) && TYPE_OVERFLOW_WRAPS (rhs_type);
1497
1498 if (lhs_size < rhs_size
1499 || (rhs_wraps && !lhs_wraps)
1500 || (rhs_wraps && lhs_wraps && rhs_size != lhs_size))
1501 return false;
1502
1503 return true;
1504 }
1505
1506 /* Return TRUE if GS is a statement that defines an SSA name from
1507 a conversion and is legal for us to combine with an add and multiply
1508 in the candidate table. For example, suppose we have:
1509
1510 A = B + i;
1511 C = (type) A;
1512 D = C * S;
1513
1514 Without the type-cast, we would create a CAND_MULT for D with base B,
1515 index i, and stride S. We want to record this candidate only if it
1516 is equivalent to apply the type cast following the multiply:
1517
1518 A = B + i;
1519 E = A * S;
1520 D = (type) E;
1521
1522 We will record the type with the candidate for D. This allows us
1523 to use a similar previous candidate as a basis. If we have earlier seen
1524
1525 A' = B + i';
1526 C' = (type) A';
1527 D' = C' * S;
1528
1529 we can replace D with
1530
1531 D = D' + (i - i') * S;
1532
1533 But if moving the type-cast would change semantics, we mustn't do this.
1534
1535 This is legitimate for casts from a non-wrapping integral type to
1536 any integral type of the same or larger size. It is not legitimate
1537 to convert a wrapping type to a non-wrapping type, or to a wrapping
1538 type of a different size. I.e., with a wrapping type, we must
1539 assume that the addition B + i could wrap, in which case performing
1540 the multiply before or after one of the "illegal" type casts will
1541 have different semantics. */
1542
1543 static bool
1544 legal_cast_p (gimple gs, tree rhs)
1545 {
1546 if (!is_gimple_assign (gs)
1547 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs)))
1548 return false;
1549
1550 return legal_cast_p_1 (gimple_assign_lhs (gs), rhs);
1551 }
1552
1553 /* Given GS which is a cast to a scalar integer type, determine whether
1554 the cast is legal for strength reduction. If so, make at least one
1555 appropriate entry in the candidate table. */
1556
1557 static void
1558 slsr_process_cast (gimple gs, tree rhs1, bool speed)
1559 {
1560 tree lhs, ctype;
1561 slsr_cand_t base_cand, c, c2;
1562 unsigned savings = 0;
1563
1564 if (!legal_cast_p (gs, rhs1))
1565 return;
1566
1567 lhs = gimple_assign_lhs (gs);
1568 base_cand = base_cand_from_table (rhs1);
1569 ctype = TREE_TYPE (lhs);
1570
1571 if (base_cand && base_cand->kind != CAND_PHI)
1572 {
1573 while (base_cand)
1574 {
1575 /* Propagate all data from the base candidate except the type,
1576 which comes from the cast, and the base candidate's cast,
1577 which is no longer applicable. */
1578 if (has_single_use (rhs1))
1579 savings = (base_cand->dead_savings
1580 + stmt_cost (base_cand->cand_stmt, speed));
1581
1582 c = alloc_cand_and_find_basis (base_cand->kind, gs,
1583 base_cand->base_expr,
1584 base_cand->index, base_cand->stride,
1585 ctype, savings);
1586 if (base_cand->next_interp)
1587 base_cand = lookup_cand (base_cand->next_interp);
1588 else
1589 base_cand = NULL;
1590 }
1591 }
1592 else
1593 {
1594 /* If nothing is known about the RHS, create fresh CAND_ADD and
1595 CAND_MULT interpretations:
1596
1597 X = Y + (0 * 1)
1598 X = (Y + 0) * 1
1599
1600 The first of these is somewhat arbitrary, but the choice of
1601 1 for the stride simplifies the logic for propagating casts
1602 into their uses. */
1603 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1,
1604 0, integer_one_node, ctype, 0);
1605 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1,
1606 0, integer_one_node, ctype, 0);
1607 c->next_interp = c2->cand_num;
1608 }
1609
1610 /* Add the first (or only) interpretation to the statement-candidate
1611 mapping. */
1612 add_cand_for_stmt (gs, c);
1613 }
1614
1615 /* Given GS which is a copy of a scalar integer type, make at least one
1616 appropriate entry in the candidate table.
1617
1618 This interface is included for completeness, but is unnecessary
1619 if this pass immediately follows a pass that performs copy
1620 propagation, such as DOM. */
1621
1622 static void
1623 slsr_process_copy (gimple gs, tree rhs1, bool speed)
1624 {
1625 slsr_cand_t base_cand, c, c2;
1626 unsigned savings = 0;
1627
1628 base_cand = base_cand_from_table (rhs1);
1629
1630 if (base_cand && base_cand->kind != CAND_PHI)
1631 {
1632 while (base_cand)
1633 {
1634 /* Propagate all data from the base candidate. */
1635 if (has_single_use (rhs1))
1636 savings = (base_cand->dead_savings
1637 + stmt_cost (base_cand->cand_stmt, speed));
1638
1639 c = alloc_cand_and_find_basis (base_cand->kind, gs,
1640 base_cand->base_expr,
1641 base_cand->index, base_cand->stride,
1642 base_cand->cand_type, savings);
1643 if (base_cand->next_interp)
1644 base_cand = lookup_cand (base_cand->next_interp);
1645 else
1646 base_cand = NULL;
1647 }
1648 }
1649 else
1650 {
1651 /* If nothing is known about the RHS, create fresh CAND_ADD and
1652 CAND_MULT interpretations:
1653
1654 X = Y + (0 * 1)
1655 X = (Y + 0) * 1
1656
1657 The first of these is somewhat arbitrary, but the choice of
1658 1 for the stride simplifies the logic for propagating casts
1659 into their uses. */
1660 c = alloc_cand_and_find_basis (CAND_ADD, gs, rhs1,
1661 0, integer_one_node, TREE_TYPE (rhs1), 0);
1662 c2 = alloc_cand_and_find_basis (CAND_MULT, gs, rhs1,
1663 0, integer_one_node, TREE_TYPE (rhs1), 0);
1664 c->next_interp = c2->cand_num;
1665 }
1666
1667 /* Add the first (or only) interpretation to the statement-candidate
1668 mapping. */
1669 add_cand_for_stmt (gs, c);
1670 }
1671 \f
1672 class find_candidates_dom_walker : public dom_walker
1673 {
1674 public:
1675 find_candidates_dom_walker (cdi_direction direction)
1676 : dom_walker (direction) {}
1677 virtual void before_dom_children (basic_block);
1678 };
1679
1680 /* Find strength-reduction candidates in block BB. */
1681
1682 void
1683 find_candidates_dom_walker::before_dom_children (basic_block bb)
1684 {
1685 bool speed = optimize_bb_for_speed_p (bb);
1686
1687 for (gphi_iterator gsi = gsi_start_phis (bb); !gsi_end_p (gsi);
1688 gsi_next (&gsi))
1689 slsr_process_phi (gsi.phi (), speed);
1690
1691 for (gimple_stmt_iterator gsi = gsi_start_bb (bb); !gsi_end_p (gsi);
1692 gsi_next (&gsi))
1693 {
1694 gimple gs = gsi_stmt (gsi);
1695
1696 if (gimple_vuse (gs) && gimple_assign_single_p (gs))
1697 slsr_process_ref (gs);
1698
1699 else if (is_gimple_assign (gs)
1700 && SCALAR_INT_MODE_P
1701 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs)))))
1702 {
1703 tree rhs1 = NULL_TREE, rhs2 = NULL_TREE;
1704
1705 switch (gimple_assign_rhs_code (gs))
1706 {
1707 case MULT_EXPR:
1708 case PLUS_EXPR:
1709 rhs1 = gimple_assign_rhs1 (gs);
1710 rhs2 = gimple_assign_rhs2 (gs);
1711 /* Should never happen, but currently some buggy situations
1712 in earlier phases put constants in rhs1. */
1713 if (TREE_CODE (rhs1) != SSA_NAME)
1714 continue;
1715 break;
1716
1717 /* Possible future opportunity: rhs1 of a ptr+ can be
1718 an ADDR_EXPR. */
1719 case POINTER_PLUS_EXPR:
1720 case MINUS_EXPR:
1721 rhs2 = gimple_assign_rhs2 (gs);
1722 /* Fall-through. */
1723
1724 CASE_CONVERT:
1725 case MODIFY_EXPR:
1726 case NEGATE_EXPR:
1727 rhs1 = gimple_assign_rhs1 (gs);
1728 if (TREE_CODE (rhs1) != SSA_NAME)
1729 continue;
1730 break;
1731
1732 default:
1733 ;
1734 }
1735
1736 switch (gimple_assign_rhs_code (gs))
1737 {
1738 case MULT_EXPR:
1739 slsr_process_mul (gs, rhs1, rhs2, speed);
1740 break;
1741
1742 case PLUS_EXPR:
1743 case POINTER_PLUS_EXPR:
1744 case MINUS_EXPR:
1745 slsr_process_add (gs, rhs1, rhs2, speed);
1746 break;
1747
1748 case NEGATE_EXPR:
1749 slsr_process_neg (gs, rhs1, speed);
1750 break;
1751
1752 CASE_CONVERT:
1753 slsr_process_cast (gs, rhs1, speed);
1754 break;
1755
1756 case MODIFY_EXPR:
1757 slsr_process_copy (gs, rhs1, speed);
1758 break;
1759
1760 default:
1761 ;
1762 }
1763 }
1764 }
1765 }
1766 \f
1767 /* Dump a candidate for debug. */
1768
1769 static void
1770 dump_candidate (slsr_cand_t c)
1771 {
1772 fprintf (dump_file, "%3d [%d] ", c->cand_num,
1773 gimple_bb (c->cand_stmt)->index);
1774 print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
1775 switch (c->kind)
1776 {
1777 case CAND_MULT:
1778 fputs (" MULT : (", dump_file);
1779 print_generic_expr (dump_file, c->base_expr, 0);
1780 fputs (" + ", dump_file);
1781 print_decs (c->index, dump_file);
1782 fputs (") * ", dump_file);
1783 print_generic_expr (dump_file, c->stride, 0);
1784 fputs (" : ", dump_file);
1785 break;
1786 case CAND_ADD:
1787 fputs (" ADD : ", dump_file);
1788 print_generic_expr (dump_file, c->base_expr, 0);
1789 fputs (" + (", dump_file);
1790 print_decs (c->index, dump_file);
1791 fputs (" * ", dump_file);
1792 print_generic_expr (dump_file, c->stride, 0);
1793 fputs (") : ", dump_file);
1794 break;
1795 case CAND_REF:
1796 fputs (" REF : ", dump_file);
1797 print_generic_expr (dump_file, c->base_expr, 0);
1798 fputs (" + (", dump_file);
1799 print_generic_expr (dump_file, c->stride, 0);
1800 fputs (") + ", dump_file);
1801 print_decs (c->index, dump_file);
1802 fputs (" : ", dump_file);
1803 break;
1804 case CAND_PHI:
1805 fputs (" PHI : ", dump_file);
1806 print_generic_expr (dump_file, c->base_expr, 0);
1807 fputs (" + (unknown * ", dump_file);
1808 print_generic_expr (dump_file, c->stride, 0);
1809 fputs (") : ", dump_file);
1810 break;
1811 default:
1812 gcc_unreachable ();
1813 }
1814 print_generic_expr (dump_file, c->cand_type, 0);
1815 fprintf (dump_file, "\n basis: %d dependent: %d sibling: %d\n",
1816 c->basis, c->dependent, c->sibling);
1817 fprintf (dump_file, " next-interp: %d dead-savings: %d\n",
1818 c->next_interp, c->dead_savings);
1819 if (c->def_phi)
1820 fprintf (dump_file, " phi: %d\n", c->def_phi);
1821 fputs ("\n", dump_file);
1822 }
1823
1824 /* Dump the candidate vector for debug. */
1825
1826 static void
1827 dump_cand_vec (void)
1828 {
1829 unsigned i;
1830 slsr_cand_t c;
1831
1832 fprintf (dump_file, "\nStrength reduction candidate vector:\n\n");
1833
1834 FOR_EACH_VEC_ELT (cand_vec, i, c)
1835 dump_candidate (c);
1836 }
1837
1838 /* Callback used to dump the candidate chains hash table. */
1839
1840 int
1841 ssa_base_cand_dump_callback (cand_chain **slot, void *ignored ATTRIBUTE_UNUSED)
1842 {
1843 const_cand_chain_t chain = *slot;
1844 cand_chain_t p;
1845
1846 print_generic_expr (dump_file, chain->base_expr, 0);
1847 fprintf (dump_file, " -> %d", chain->cand->cand_num);
1848
1849 for (p = chain->next; p; p = p->next)
1850 fprintf (dump_file, " -> %d", p->cand->cand_num);
1851
1852 fputs ("\n", dump_file);
1853 return 1;
1854 }
1855
1856 /* Dump the candidate chains. */
1857
1858 static void
1859 dump_cand_chains (void)
1860 {
1861 fprintf (dump_file, "\nStrength reduction candidate chains:\n\n");
1862 base_cand_map->traverse_noresize <void *, ssa_base_cand_dump_callback>
1863 (NULL);
1864 fputs ("\n", dump_file);
1865 }
1866
1867 /* Dump the increment vector for debug. */
1868
1869 static void
1870 dump_incr_vec (void)
1871 {
1872 if (dump_file && (dump_flags & TDF_DETAILS))
1873 {
1874 unsigned i;
1875
1876 fprintf (dump_file, "\nIncrement vector:\n\n");
1877
1878 for (i = 0; i < incr_vec_len; i++)
1879 {
1880 fprintf (dump_file, "%3d increment: ", i);
1881 print_decs (incr_vec[i].incr, dump_file);
1882 fprintf (dump_file, "\n count: %d", incr_vec[i].count);
1883 fprintf (dump_file, "\n cost: %d", incr_vec[i].cost);
1884 fputs ("\n initializer: ", dump_file);
1885 print_generic_expr (dump_file, incr_vec[i].initializer, 0);
1886 fputs ("\n\n", dump_file);
1887 }
1888 }
1889 }
1890 \f
1891 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1892 data reference. */
1893
1894 static void
1895 replace_ref (tree *expr, slsr_cand_t c)
1896 {
1897 tree add_expr, mem_ref, acc_type = TREE_TYPE (*expr);
1898 unsigned HOST_WIDE_INT misalign;
1899 unsigned align;
1900
1901 /* Ensure the memory reference carries the minimum alignment
1902 requirement for the data type. See PR58041. */
1903 get_object_alignment_1 (*expr, &align, &misalign);
1904 if (misalign != 0)
1905 align = (misalign & -misalign);
1906 if (align < TYPE_ALIGN (acc_type))
1907 acc_type = build_aligned_type (acc_type, align);
1908
1909 add_expr = fold_build2 (POINTER_PLUS_EXPR, TREE_TYPE (c->base_expr),
1910 c->base_expr, c->stride);
1911 mem_ref = fold_build2 (MEM_REF, acc_type, add_expr,
1912 wide_int_to_tree (c->cand_type, c->index));
1913
1914 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1915 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
1916 TREE_OPERAND (mem_ref, 0)
1917 = force_gimple_operand_gsi (&gsi, TREE_OPERAND (mem_ref, 0),
1918 /*simple_p=*/true, NULL,
1919 /*before=*/true, GSI_SAME_STMT);
1920 copy_ref_info (mem_ref, *expr);
1921 *expr = mem_ref;
1922 update_stmt (c->cand_stmt);
1923 }
1924
1925 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1926 dependent of candidate C with an equivalent strength-reduced data
1927 reference. */
1928
1929 static void
1930 replace_refs (slsr_cand_t c)
1931 {
1932 if (dump_file && (dump_flags & TDF_DETAILS))
1933 {
1934 fputs ("Replacing reference: ", dump_file);
1935 print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
1936 }
1937
1938 if (gimple_vdef (c->cand_stmt))
1939 {
1940 tree *lhs = gimple_assign_lhs_ptr (c->cand_stmt);
1941 replace_ref (lhs, c);
1942 }
1943 else
1944 {
1945 tree *rhs = gimple_assign_rhs1_ptr (c->cand_stmt);
1946 replace_ref (rhs, c);
1947 }
1948
1949 if (dump_file && (dump_flags & TDF_DETAILS))
1950 {
1951 fputs ("With: ", dump_file);
1952 print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
1953 fputs ("\n", dump_file);
1954 }
1955
1956 if (c->sibling)
1957 replace_refs (lookup_cand (c->sibling));
1958
1959 if (c->dependent)
1960 replace_refs (lookup_cand (c->dependent));
1961 }
1962
1963 /* Return TRUE if candidate C is dependent upon a PHI. */
1964
1965 static bool
1966 phi_dependent_cand_p (slsr_cand_t c)
1967 {
1968 /* A candidate is not necessarily dependent upon a PHI just because
1969 it has a phi definition for its base name. It may have a basis
1970 that relies upon the same phi definition, in which case the PHI
1971 is irrelevant to this candidate. */
1972 return (c->def_phi
1973 && c->basis
1974 && lookup_cand (c->basis)->def_phi != c->def_phi);
1975 }
1976
1977 /* Calculate the increment required for candidate C relative to
1978 its basis. */
1979
1980 static widest_int
1981 cand_increment (slsr_cand_t c)
1982 {
1983 slsr_cand_t basis;
1984
1985 /* If the candidate doesn't have a basis, just return its own
1986 index. This is useful in record_increments to help us find
1987 an existing initializer. Also, if the candidate's basis is
1988 hidden by a phi, then its own index will be the increment
1989 from the newly introduced phi basis. */
1990 if (!c->basis || phi_dependent_cand_p (c))
1991 return c->index;
1992
1993 basis = lookup_cand (c->basis);
1994 gcc_assert (operand_equal_p (c->base_expr, basis->base_expr, 0));
1995 return c->index - basis->index;
1996 }
1997
1998 /* Calculate the increment required for candidate C relative to
1999 its basis. If we aren't going to generate pointer arithmetic
2000 for this candidate, return the absolute value of that increment
2001 instead. */
2002
2003 static inline widest_int
2004 cand_abs_increment (slsr_cand_t c)
2005 {
2006 widest_int increment = cand_increment (c);
2007
2008 if (!address_arithmetic_p && wi::neg_p (increment))
2009 increment = -increment;
2010
2011 return increment;
2012 }
2013
2014 /* Return TRUE iff candidate C has already been replaced under
2015 another interpretation. */
2016
2017 static inline bool
2018 cand_already_replaced (slsr_cand_t c)
2019 {
2020 return (gimple_bb (c->cand_stmt) == 0);
2021 }
2022
2023 /* Common logic used by replace_unconditional_candidate and
2024 replace_conditional_candidate. */
2025
2026 static void
2027 replace_mult_candidate (slsr_cand_t c, tree basis_name, widest_int bump)
2028 {
2029 tree target_type = TREE_TYPE (gimple_assign_lhs (c->cand_stmt));
2030 enum tree_code cand_code = gimple_assign_rhs_code (c->cand_stmt);
2031
2032 /* It is highly unlikely, but possible, that the resulting
2033 bump doesn't fit in a HWI. Abandon the replacement
2034 in this case. This does not affect siblings or dependents
2035 of C. Restriction to signed HWI is conservative for unsigned
2036 types but allows for safe negation without twisted logic. */
2037 if (wi::fits_shwi_p (bump)
2038 && bump.to_shwi () != HOST_WIDE_INT_MIN
2039 /* It is not useful to replace casts, copies, or adds of
2040 an SSA name and a constant. */
2041 && cand_code != MODIFY_EXPR
2042 && !CONVERT_EXPR_CODE_P (cand_code)
2043 && cand_code != PLUS_EXPR
2044 && cand_code != POINTER_PLUS_EXPR
2045 && cand_code != MINUS_EXPR)
2046 {
2047 enum tree_code code = PLUS_EXPR;
2048 tree bump_tree;
2049 gimple stmt_to_print = NULL;
2050
2051 /* If the basis name and the candidate's LHS have incompatible
2052 types, introduce a cast. */
2053 if (!useless_type_conversion_p (target_type, TREE_TYPE (basis_name)))
2054 basis_name = introduce_cast_before_cand (c, target_type, basis_name);
2055 if (wi::neg_p (bump))
2056 {
2057 code = MINUS_EXPR;
2058 bump = -bump;
2059 }
2060
2061 bump_tree = wide_int_to_tree (target_type, bump);
2062
2063 if (dump_file && (dump_flags & TDF_DETAILS))
2064 {
2065 fputs ("Replacing: ", dump_file);
2066 print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
2067 }
2068
2069 if (bump == 0)
2070 {
2071 tree lhs = gimple_assign_lhs (c->cand_stmt);
2072 gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
2073 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
2074 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
2075 gsi_replace (&gsi, copy_stmt, false);
2076 c->cand_stmt = copy_stmt;
2077 if (dump_file && (dump_flags & TDF_DETAILS))
2078 stmt_to_print = copy_stmt;
2079 }
2080 else
2081 {
2082 tree rhs1, rhs2;
2083 if (cand_code != NEGATE_EXPR) {
2084 rhs1 = gimple_assign_rhs1 (c->cand_stmt);
2085 rhs2 = gimple_assign_rhs2 (c->cand_stmt);
2086 }
2087 if (cand_code != NEGATE_EXPR
2088 && ((operand_equal_p (rhs1, basis_name, 0)
2089 && operand_equal_p (rhs2, bump_tree, 0))
2090 || (operand_equal_p (rhs1, bump_tree, 0)
2091 && operand_equal_p (rhs2, basis_name, 0))))
2092 {
2093 if (dump_file && (dump_flags & TDF_DETAILS))
2094 {
2095 fputs ("(duplicate, not actually replacing)", dump_file);
2096 stmt_to_print = c->cand_stmt;
2097 }
2098 }
2099 else
2100 {
2101 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
2102 gimple_assign_set_rhs_with_ops (&gsi, code,
2103 basis_name, bump_tree);
2104 update_stmt (gsi_stmt (gsi));
2105 c->cand_stmt = gsi_stmt (gsi);
2106 if (dump_file && (dump_flags & TDF_DETAILS))
2107 stmt_to_print = gsi_stmt (gsi);
2108 }
2109 }
2110
2111 if (dump_file && (dump_flags & TDF_DETAILS))
2112 {
2113 fputs ("With: ", dump_file);
2114 print_gimple_stmt (dump_file, stmt_to_print, 0, 0);
2115 fputs ("\n", dump_file);
2116 }
2117 }
2118 }
2119
2120 /* Replace candidate C with an add or subtract. Note that we only
2121 operate on CAND_MULTs with known strides, so we will never generate
2122 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2123 X = Y + ((i - i') * S), as described in the module commentary. The
2124 folded value ((i - i') * S) is referred to here as the "bump." */
2125
2126 static void
2127 replace_unconditional_candidate (slsr_cand_t c)
2128 {
2129 slsr_cand_t basis;
2130
2131 if (cand_already_replaced (c))
2132 return;
2133
2134 basis = lookup_cand (c->basis);
2135 widest_int bump = cand_increment (c) * wi::to_widest (c->stride);
2136
2137 replace_mult_candidate (c, gimple_assign_lhs (basis->cand_stmt), bump);
2138 }
2139 \f
2140 /* Return the index in the increment vector of the given INCREMENT,
2141 or -1 if not found. The latter can occur if more than
2142 MAX_INCR_VEC_LEN increments have been found. */
2143
2144 static inline int
2145 incr_vec_index (const widest_int &increment)
2146 {
2147 unsigned i;
2148
2149 for (i = 0; i < incr_vec_len && increment != incr_vec[i].incr; i++)
2150 ;
2151
2152 if (i < incr_vec_len)
2153 return i;
2154 else
2155 return -1;
2156 }
2157
2158 /* Create a new statement along edge E to add BASIS_NAME to the product
2159 of INCREMENT and the stride of candidate C. Create and return a new
2160 SSA name from *VAR to be used as the LHS of the new statement.
2161 KNOWN_STRIDE is true iff C's stride is a constant. */
2162
2163 static tree
2164 create_add_on_incoming_edge (slsr_cand_t c, tree basis_name,
2165 widest_int increment, edge e, location_t loc,
2166 bool known_stride)
2167 {
2168 basic_block insert_bb;
2169 gimple_stmt_iterator gsi;
2170 tree lhs, basis_type;
2171 gassign *new_stmt;
2172
2173 /* If the add candidate along this incoming edge has the same
2174 index as C's hidden basis, the hidden basis represents this
2175 edge correctly. */
2176 if (increment == 0)
2177 return basis_name;
2178
2179 basis_type = TREE_TYPE (basis_name);
2180 lhs = make_temp_ssa_name (basis_type, NULL, "slsr");
2181
2182 if (known_stride)
2183 {
2184 tree bump_tree;
2185 enum tree_code code = PLUS_EXPR;
2186 widest_int bump = increment * wi::to_widest (c->stride);
2187 if (wi::neg_p (bump))
2188 {
2189 code = MINUS_EXPR;
2190 bump = -bump;
2191 }
2192
2193 bump_tree = wide_int_to_tree (basis_type, bump);
2194 new_stmt = gimple_build_assign (lhs, code, basis_name, bump_tree);
2195 }
2196 else
2197 {
2198 int i;
2199 bool negate_incr = (!address_arithmetic_p && wi::neg_p (increment));
2200 i = incr_vec_index (negate_incr ? -increment : increment);
2201 gcc_assert (i >= 0);
2202
2203 if (incr_vec[i].initializer)
2204 {
2205 enum tree_code code = negate_incr ? MINUS_EXPR : PLUS_EXPR;
2206 new_stmt = gimple_build_assign (lhs, code, basis_name,
2207 incr_vec[i].initializer);
2208 }
2209 else if (increment == 1)
2210 new_stmt = gimple_build_assign (lhs, PLUS_EXPR, basis_name, c->stride);
2211 else if (increment == -1)
2212 new_stmt = gimple_build_assign (lhs, MINUS_EXPR, basis_name,
2213 c->stride);
2214 else
2215 gcc_unreachable ();
2216 }
2217
2218 insert_bb = single_succ_p (e->src) ? e->src : split_edge (e);
2219 gsi = gsi_last_bb (insert_bb);
2220
2221 if (!gsi_end_p (gsi) && is_ctrl_stmt (gsi_stmt (gsi)))
2222 gsi_insert_before (&gsi, new_stmt, GSI_NEW_STMT);
2223 else
2224 gsi_insert_after (&gsi, new_stmt, GSI_NEW_STMT);
2225
2226 gimple_set_location (new_stmt, loc);
2227
2228 if (dump_file && (dump_flags & TDF_DETAILS))
2229 {
2230 fprintf (dump_file, "Inserting in block %d: ", insert_bb->index);
2231 print_gimple_stmt (dump_file, new_stmt, 0, 0);
2232 }
2233
2234 return lhs;
2235 }
2236
2237 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2238 is hidden by the phi node FROM_PHI, create a new phi node in the same
2239 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2240 with its phi arguments representing conditional adjustments to the
2241 hidden basis along conditional incoming paths. Those adjustments are
2242 made by creating add statements (and sometimes recursively creating
2243 phis) along those incoming paths. LOC is the location to attach to
2244 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2245 constant. */
2246
2247 static tree
2248 create_phi_basis (slsr_cand_t c, gimple from_phi, tree basis_name,
2249 location_t loc, bool known_stride)
2250 {
2251 int i;
2252 tree name, phi_arg;
2253 gphi *phi;
2254 vec<tree> phi_args;
2255 slsr_cand_t basis = lookup_cand (c->basis);
2256 int nargs = gimple_phi_num_args (from_phi);
2257 basic_block phi_bb = gimple_bb (from_phi);
2258 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (from_phi));
2259 phi_args.create (nargs);
2260
2261 /* Process each argument of the existing phi that represents
2262 conditionally-executed add candidates. */
2263 for (i = 0; i < nargs; i++)
2264 {
2265 edge e = (*phi_bb->preds)[i];
2266 tree arg = gimple_phi_arg_def (from_phi, i);
2267 tree feeding_def;
2268
2269 /* If the phi argument is the base name of the CAND_PHI, then
2270 this incoming arc should use the hidden basis. */
2271 if (operand_equal_p (arg, phi_cand->base_expr, 0))
2272 if (basis->index == 0)
2273 feeding_def = gimple_assign_lhs (basis->cand_stmt);
2274 else
2275 {
2276 widest_int incr = -basis->index;
2277 feeding_def = create_add_on_incoming_edge (c, basis_name, incr,
2278 e, loc, known_stride);
2279 }
2280 else
2281 {
2282 gimple arg_def = SSA_NAME_DEF_STMT (arg);
2283
2284 /* If there is another phi along this incoming edge, we must
2285 process it in the same fashion to ensure that all basis
2286 adjustments are made along its incoming edges. */
2287 if (gimple_code (arg_def) == GIMPLE_PHI)
2288 feeding_def = create_phi_basis (c, arg_def, basis_name,
2289 loc, known_stride);
2290 else
2291 {
2292 slsr_cand_t arg_cand = base_cand_from_table (arg);
2293 widest_int diff = arg_cand->index - basis->index;
2294 feeding_def = create_add_on_incoming_edge (c, basis_name, diff,
2295 e, loc, known_stride);
2296 }
2297 }
2298
2299 /* Because of recursion, we need to save the arguments in a vector
2300 so we can create the PHI statement all at once. Otherwise the
2301 storage for the half-created PHI can be reclaimed. */
2302 phi_args.safe_push (feeding_def);
2303 }
2304
2305 /* Create the new phi basis. */
2306 name = make_temp_ssa_name (TREE_TYPE (basis_name), NULL, "slsr");
2307 phi = create_phi_node (name, phi_bb);
2308 SSA_NAME_DEF_STMT (name) = phi;
2309
2310 FOR_EACH_VEC_ELT (phi_args, i, phi_arg)
2311 {
2312 edge e = (*phi_bb->preds)[i];
2313 add_phi_arg (phi, phi_arg, e, loc);
2314 }
2315
2316 update_stmt (phi);
2317
2318 if (dump_file && (dump_flags & TDF_DETAILS))
2319 {
2320 fputs ("Introducing new phi basis: ", dump_file);
2321 print_gimple_stmt (dump_file, phi, 0, 0);
2322 }
2323
2324 return name;
2325 }
2326
2327 /* Given a candidate C whose basis is hidden by at least one intervening
2328 phi, introduce a matching number of new phis to represent its basis
2329 adjusted by conditional increments along possible incoming paths. Then
2330 replace C as though it were an unconditional candidate, using the new
2331 basis. */
2332
2333 static void
2334 replace_conditional_candidate (slsr_cand_t c)
2335 {
2336 tree basis_name, name;
2337 slsr_cand_t basis;
2338 location_t loc;
2339
2340 /* Look up the LHS SSA name from C's basis. This will be the
2341 RHS1 of the adds we will introduce to create new phi arguments. */
2342 basis = lookup_cand (c->basis);
2343 basis_name = gimple_assign_lhs (basis->cand_stmt);
2344
2345 /* Create a new phi statement which will represent C's true basis
2346 after the transformation is complete. */
2347 loc = gimple_location (c->cand_stmt);
2348 name = create_phi_basis (c, lookup_cand (c->def_phi)->cand_stmt,
2349 basis_name, loc, KNOWN_STRIDE);
2350 /* Replace C with an add of the new basis phi and a constant. */
2351 widest_int bump = c->index * wi::to_widest (c->stride);
2352
2353 replace_mult_candidate (c, name, bump);
2354 }
2355
2356 /* Compute the expected costs of inserting basis adjustments for
2357 candidate C with phi-definition PHI. The cost of inserting
2358 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2359 which are themselves phi results, recursively calculate costs
2360 for those phis as well. */
2361
2362 static int
2363 phi_add_costs (gimple phi, slsr_cand_t c, int one_add_cost)
2364 {
2365 unsigned i;
2366 int cost = 0;
2367 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
2368
2369 /* If we work our way back to a phi that isn't dominated by the hidden
2370 basis, this isn't a candidate for replacement. Indicate this by
2371 returning an unreasonably high cost. It's not easy to detect
2372 these situations when determining the basis, so we defer the
2373 decision until now. */
2374 basic_block phi_bb = gimple_bb (phi);
2375 slsr_cand_t basis = lookup_cand (c->basis);
2376 basic_block basis_bb = gimple_bb (basis->cand_stmt);
2377
2378 if (phi_bb == basis_bb || !dominated_by_p (CDI_DOMINATORS, phi_bb, basis_bb))
2379 return COST_INFINITE;
2380
2381 for (i = 0; i < gimple_phi_num_args (phi); i++)
2382 {
2383 tree arg = gimple_phi_arg_def (phi, i);
2384
2385 if (arg != phi_cand->base_expr)
2386 {
2387 gimple arg_def = SSA_NAME_DEF_STMT (arg);
2388
2389 if (gimple_code (arg_def) == GIMPLE_PHI)
2390 cost += phi_add_costs (arg_def, c, one_add_cost);
2391 else
2392 {
2393 slsr_cand_t arg_cand = base_cand_from_table (arg);
2394
2395 if (arg_cand->index != c->index)
2396 cost += one_add_cost;
2397 }
2398 }
2399 }
2400
2401 return cost;
2402 }
2403
2404 /* For candidate C, each sibling of candidate C, and each dependent of
2405 candidate C, determine whether the candidate is dependent upon a
2406 phi that hides its basis. If not, replace the candidate unconditionally.
2407 Otherwise, determine whether the cost of introducing compensation code
2408 for the candidate is offset by the gains from strength reduction. If
2409 so, replace the candidate and introduce the compensation code. */
2410
2411 static void
2412 replace_uncond_cands_and_profitable_phis (slsr_cand_t c)
2413 {
2414 if (phi_dependent_cand_p (c))
2415 {
2416 if (c->kind == CAND_MULT)
2417 {
2418 /* A candidate dependent upon a phi will replace a multiply by
2419 a constant with an add, and will insert at most one add for
2420 each phi argument. Add these costs with the potential dead-code
2421 savings to determine profitability. */
2422 bool speed = optimize_bb_for_speed_p (gimple_bb (c->cand_stmt));
2423 int mult_savings = stmt_cost (c->cand_stmt, speed);
2424 gimple phi = lookup_cand (c->def_phi)->cand_stmt;
2425 tree phi_result = gimple_phi_result (phi);
2426 int one_add_cost = add_cost (speed,
2427 TYPE_MODE (TREE_TYPE (phi_result)));
2428 int add_costs = one_add_cost + phi_add_costs (phi, c, one_add_cost);
2429 int cost = add_costs - mult_savings - c->dead_savings;
2430
2431 if (dump_file && (dump_flags & TDF_DETAILS))
2432 {
2433 fprintf (dump_file, " Conditional candidate %d:\n", c->cand_num);
2434 fprintf (dump_file, " add_costs = %d\n", add_costs);
2435 fprintf (dump_file, " mult_savings = %d\n", mult_savings);
2436 fprintf (dump_file, " dead_savings = %d\n", c->dead_savings);
2437 fprintf (dump_file, " cost = %d\n", cost);
2438 if (cost <= COST_NEUTRAL)
2439 fputs (" Replacing...\n", dump_file);
2440 else
2441 fputs (" Not replaced.\n", dump_file);
2442 }
2443
2444 if (cost <= COST_NEUTRAL)
2445 replace_conditional_candidate (c);
2446 }
2447 }
2448 else
2449 replace_unconditional_candidate (c);
2450
2451 if (c->sibling)
2452 replace_uncond_cands_and_profitable_phis (lookup_cand (c->sibling));
2453
2454 if (c->dependent)
2455 replace_uncond_cands_and_profitable_phis (lookup_cand (c->dependent));
2456 }
2457 \f
2458 /* Count the number of candidates in the tree rooted at C that have
2459 not already been replaced under other interpretations. */
2460
2461 static int
2462 count_candidates (slsr_cand_t c)
2463 {
2464 unsigned count = cand_already_replaced (c) ? 0 : 1;
2465
2466 if (c->sibling)
2467 count += count_candidates (lookup_cand (c->sibling));
2468
2469 if (c->dependent)
2470 count += count_candidates (lookup_cand (c->dependent));
2471
2472 return count;
2473 }
2474
2475 /* Increase the count of INCREMENT by one in the increment vector.
2476 INCREMENT is associated with candidate C. If INCREMENT is to be
2477 conditionally executed as part of a conditional candidate replacement,
2478 IS_PHI_ADJUST is true, otherwise false. If an initializer
2479 T_0 = stride * I is provided by a candidate that dominates all
2480 candidates with the same increment, also record T_0 for subsequent use. */
2481
2482 static void
2483 record_increment (slsr_cand_t c, widest_int increment, bool is_phi_adjust)
2484 {
2485 bool found = false;
2486 unsigned i;
2487
2488 /* Treat increments that differ only in sign as identical so as to
2489 share initializers, unless we are generating pointer arithmetic. */
2490 if (!address_arithmetic_p && wi::neg_p (increment))
2491 increment = -increment;
2492
2493 for (i = 0; i < incr_vec_len; i++)
2494 {
2495 if (incr_vec[i].incr == increment)
2496 {
2497 incr_vec[i].count++;
2498 found = true;
2499
2500 /* If we previously recorded an initializer that doesn't
2501 dominate this candidate, it's not going to be useful to
2502 us after all. */
2503 if (incr_vec[i].initializer
2504 && !dominated_by_p (CDI_DOMINATORS,
2505 gimple_bb (c->cand_stmt),
2506 incr_vec[i].init_bb))
2507 {
2508 incr_vec[i].initializer = NULL_TREE;
2509 incr_vec[i].init_bb = NULL;
2510 }
2511
2512 break;
2513 }
2514 }
2515
2516 if (!found && incr_vec_len < MAX_INCR_VEC_LEN - 1)
2517 {
2518 /* The first time we see an increment, create the entry for it.
2519 If this is the root candidate which doesn't have a basis, set
2520 the count to zero. We're only processing it so it can possibly
2521 provide an initializer for other candidates. */
2522 incr_vec[incr_vec_len].incr = increment;
2523 incr_vec[incr_vec_len].count = c->basis || is_phi_adjust ? 1 : 0;
2524 incr_vec[incr_vec_len].cost = COST_INFINITE;
2525
2526 /* Optimistically record the first occurrence of this increment
2527 as providing an initializer (if it does); we will revise this
2528 opinion later if it doesn't dominate all other occurrences.
2529 Exception: increments of -1, 0, 1 never need initializers;
2530 and phi adjustments don't ever provide initializers. */
2531 if (c->kind == CAND_ADD
2532 && !is_phi_adjust
2533 && c->index == increment
2534 && (wi::gts_p (increment, 1)
2535 || wi::lts_p (increment, -1))
2536 && (gimple_assign_rhs_code (c->cand_stmt) == PLUS_EXPR
2537 || gimple_assign_rhs_code (c->cand_stmt) == POINTER_PLUS_EXPR))
2538 {
2539 tree t0 = NULL_TREE;
2540 tree rhs1 = gimple_assign_rhs1 (c->cand_stmt);
2541 tree rhs2 = gimple_assign_rhs2 (c->cand_stmt);
2542 if (operand_equal_p (rhs1, c->base_expr, 0))
2543 t0 = rhs2;
2544 else if (operand_equal_p (rhs2, c->base_expr, 0))
2545 t0 = rhs1;
2546 if (t0
2547 && SSA_NAME_DEF_STMT (t0)
2548 && gimple_bb (SSA_NAME_DEF_STMT (t0)))
2549 {
2550 incr_vec[incr_vec_len].initializer = t0;
2551 incr_vec[incr_vec_len++].init_bb
2552 = gimple_bb (SSA_NAME_DEF_STMT (t0));
2553 }
2554 else
2555 {
2556 incr_vec[incr_vec_len].initializer = NULL_TREE;
2557 incr_vec[incr_vec_len++].init_bb = NULL;
2558 }
2559 }
2560 else
2561 {
2562 incr_vec[incr_vec_len].initializer = NULL_TREE;
2563 incr_vec[incr_vec_len++].init_bb = NULL;
2564 }
2565 }
2566 }
2567
2568 /* Given phi statement PHI that hides a candidate from its BASIS, find
2569 the increments along each incoming arc (recursively handling additional
2570 phis that may be present) and record them. These increments are the
2571 difference in index between the index-adjusting statements and the
2572 index of the basis. */
2573
2574 static void
2575 record_phi_increments (slsr_cand_t basis, gimple phi)
2576 {
2577 unsigned i;
2578 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
2579
2580 for (i = 0; i < gimple_phi_num_args (phi); i++)
2581 {
2582 tree arg = gimple_phi_arg_def (phi, i);
2583
2584 if (!operand_equal_p (arg, phi_cand->base_expr, 0))
2585 {
2586 gimple arg_def = SSA_NAME_DEF_STMT (arg);
2587
2588 if (gimple_code (arg_def) == GIMPLE_PHI)
2589 record_phi_increments (basis, arg_def);
2590 else
2591 {
2592 slsr_cand_t arg_cand = base_cand_from_table (arg);
2593 widest_int diff = arg_cand->index - basis->index;
2594 record_increment (arg_cand, diff, PHI_ADJUST);
2595 }
2596 }
2597 }
2598 }
2599
2600 /* Determine how many times each unique increment occurs in the set
2601 of candidates rooted at C's parent, recording the data in the
2602 increment vector. For each unique increment I, if an initializer
2603 T_0 = stride * I is provided by a candidate that dominates all
2604 candidates with the same increment, also record T_0 for subsequent
2605 use. */
2606
2607 static void
2608 record_increments (slsr_cand_t c)
2609 {
2610 if (!cand_already_replaced (c))
2611 {
2612 if (!phi_dependent_cand_p (c))
2613 record_increment (c, cand_increment (c), NOT_PHI_ADJUST);
2614 else
2615 {
2616 /* A candidate with a basis hidden by a phi will have one
2617 increment for its relationship to the index represented by
2618 the phi, and potentially additional increments along each
2619 incoming edge. For the root of the dependency tree (which
2620 has no basis), process just the initial index in case it has
2621 an initializer that can be used by subsequent candidates. */
2622 record_increment (c, c->index, NOT_PHI_ADJUST);
2623
2624 if (c->basis)
2625 record_phi_increments (lookup_cand (c->basis),
2626 lookup_cand (c->def_phi)->cand_stmt);
2627 }
2628 }
2629
2630 if (c->sibling)
2631 record_increments (lookup_cand (c->sibling));
2632
2633 if (c->dependent)
2634 record_increments (lookup_cand (c->dependent));
2635 }
2636
2637 /* Add up and return the costs of introducing add statements that
2638 require the increment INCR on behalf of candidate C and phi
2639 statement PHI. Accumulate into *SAVINGS the potential savings
2640 from removing existing statements that feed PHI and have no other
2641 uses. */
2642
2643 static int
2644 phi_incr_cost (slsr_cand_t c, const widest_int &incr, gimple phi, int *savings)
2645 {
2646 unsigned i;
2647 int cost = 0;
2648 slsr_cand_t basis = lookup_cand (c->basis);
2649 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
2650
2651 for (i = 0; i < gimple_phi_num_args (phi); i++)
2652 {
2653 tree arg = gimple_phi_arg_def (phi, i);
2654
2655 if (!operand_equal_p (arg, phi_cand->base_expr, 0))
2656 {
2657 gimple arg_def = SSA_NAME_DEF_STMT (arg);
2658
2659 if (gimple_code (arg_def) == GIMPLE_PHI)
2660 {
2661 int feeding_savings = 0;
2662 cost += phi_incr_cost (c, incr, arg_def, &feeding_savings);
2663 if (has_single_use (gimple_phi_result (arg_def)))
2664 *savings += feeding_savings;
2665 }
2666 else
2667 {
2668 slsr_cand_t arg_cand = base_cand_from_table (arg);
2669 widest_int diff = arg_cand->index - basis->index;
2670
2671 if (incr == diff)
2672 {
2673 tree basis_lhs = gimple_assign_lhs (basis->cand_stmt);
2674 tree lhs = gimple_assign_lhs (arg_cand->cand_stmt);
2675 cost += add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs)));
2676 if (has_single_use (lhs))
2677 *savings += stmt_cost (arg_cand->cand_stmt, true);
2678 }
2679 }
2680 }
2681 }
2682
2683 return cost;
2684 }
2685
2686 /* Return the first candidate in the tree rooted at C that has not
2687 already been replaced, favoring siblings over dependents. */
2688
2689 static slsr_cand_t
2690 unreplaced_cand_in_tree (slsr_cand_t c)
2691 {
2692 if (!cand_already_replaced (c))
2693 return c;
2694
2695 if (c->sibling)
2696 {
2697 slsr_cand_t sib = unreplaced_cand_in_tree (lookup_cand (c->sibling));
2698 if (sib)
2699 return sib;
2700 }
2701
2702 if (c->dependent)
2703 {
2704 slsr_cand_t dep = unreplaced_cand_in_tree (lookup_cand (c->dependent));
2705 if (dep)
2706 return dep;
2707 }
2708
2709 return NULL;
2710 }
2711
2712 /* Return TRUE if the candidates in the tree rooted at C should be
2713 optimized for speed, else FALSE. We estimate this based on the block
2714 containing the most dominant candidate in the tree that has not yet
2715 been replaced. */
2716
2717 static bool
2718 optimize_cands_for_speed_p (slsr_cand_t c)
2719 {
2720 slsr_cand_t c2 = unreplaced_cand_in_tree (c);
2721 gcc_assert (c2);
2722 return optimize_bb_for_speed_p (gimple_bb (c2->cand_stmt));
2723 }
2724
2725 /* Add COST_IN to the lowest cost of any dependent path starting at
2726 candidate C or any of its siblings, counting only candidates along
2727 such paths with increment INCR. Assume that replacing a candidate
2728 reduces cost by REPL_SAVINGS. Also account for savings from any
2729 statements that would go dead. If COUNT_PHIS is true, include
2730 costs of introducing feeding statements for conditional candidates. */
2731
2732 static int
2733 lowest_cost_path (int cost_in, int repl_savings, slsr_cand_t c,
2734 const widest_int &incr, bool count_phis)
2735 {
2736 int local_cost, sib_cost, savings = 0;
2737 widest_int cand_incr = cand_abs_increment (c);
2738
2739 if (cand_already_replaced (c))
2740 local_cost = cost_in;
2741 else if (incr == cand_incr)
2742 local_cost = cost_in - repl_savings - c->dead_savings;
2743 else
2744 local_cost = cost_in - c->dead_savings;
2745
2746 if (count_phis
2747 && phi_dependent_cand_p (c)
2748 && !cand_already_replaced (c))
2749 {
2750 gimple phi = lookup_cand (c->def_phi)->cand_stmt;
2751 local_cost += phi_incr_cost (c, incr, phi, &savings);
2752
2753 if (has_single_use (gimple_phi_result (phi)))
2754 local_cost -= savings;
2755 }
2756
2757 if (c->dependent)
2758 local_cost = lowest_cost_path (local_cost, repl_savings,
2759 lookup_cand (c->dependent), incr,
2760 count_phis);
2761
2762 if (c->sibling)
2763 {
2764 sib_cost = lowest_cost_path (cost_in, repl_savings,
2765 lookup_cand (c->sibling), incr,
2766 count_phis);
2767 local_cost = MIN (local_cost, sib_cost);
2768 }
2769
2770 return local_cost;
2771 }
2772
2773 /* Compute the total savings that would accrue from all replacements
2774 in the candidate tree rooted at C, counting only candidates with
2775 increment INCR. Assume that replacing a candidate reduces cost
2776 by REPL_SAVINGS. Also account for savings from statements that
2777 would go dead. */
2778
2779 static int
2780 total_savings (int repl_savings, slsr_cand_t c, const widest_int &incr,
2781 bool count_phis)
2782 {
2783 int savings = 0;
2784 widest_int cand_incr = cand_abs_increment (c);
2785
2786 if (incr == cand_incr && !cand_already_replaced (c))
2787 savings += repl_savings + c->dead_savings;
2788
2789 if (count_phis
2790 && phi_dependent_cand_p (c)
2791 && !cand_already_replaced (c))
2792 {
2793 int phi_savings = 0;
2794 gimple phi = lookup_cand (c->def_phi)->cand_stmt;
2795 savings -= phi_incr_cost (c, incr, phi, &phi_savings);
2796
2797 if (has_single_use (gimple_phi_result (phi)))
2798 savings += phi_savings;
2799 }
2800
2801 if (c->dependent)
2802 savings += total_savings (repl_savings, lookup_cand (c->dependent), incr,
2803 count_phis);
2804
2805 if (c->sibling)
2806 savings += total_savings (repl_savings, lookup_cand (c->sibling), incr,
2807 count_phis);
2808
2809 return savings;
2810 }
2811
2812 /* Use target-specific costs to determine and record which increments
2813 in the current candidate tree are profitable to replace, assuming
2814 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2815 the candidate tree.
2816
2817 One slight limitation here is that we don't account for the possible
2818 introduction of casts in some cases. See replace_one_candidate for
2819 the cases where these are introduced. This should probably be cleaned
2820 up sometime. */
2821
2822 static void
2823 analyze_increments (slsr_cand_t first_dep, machine_mode mode, bool speed)
2824 {
2825 unsigned i;
2826
2827 for (i = 0; i < incr_vec_len; i++)
2828 {
2829 HOST_WIDE_INT incr = incr_vec[i].incr.to_shwi ();
2830
2831 /* If somehow this increment is bigger than a HWI, we won't
2832 be optimizing candidates that use it. And if the increment
2833 has a count of zero, nothing will be done with it. */
2834 if (!wi::fits_shwi_p (incr_vec[i].incr) || !incr_vec[i].count)
2835 incr_vec[i].cost = COST_INFINITE;
2836
2837 /* Increments of 0, 1, and -1 are always profitable to replace,
2838 because they always replace a multiply or add with an add or
2839 copy, and may cause one or more existing instructions to go
2840 dead. Exception: -1 can't be assumed to be profitable for
2841 pointer addition. */
2842 else if (incr == 0
2843 || incr == 1
2844 || (incr == -1
2845 && (gimple_assign_rhs_code (first_dep->cand_stmt)
2846 != POINTER_PLUS_EXPR)))
2847 incr_vec[i].cost = COST_NEUTRAL;
2848
2849 /* FORNOW: If we need to add an initializer, give up if a cast from
2850 the candidate's type to its stride's type can lose precision.
2851 This could eventually be handled better by expressly retaining the
2852 result of a cast to a wider type in the stride. Example:
2853
2854 short int _1;
2855 _2 = (int) _1;
2856 _3 = _2 * 10;
2857 _4 = x + _3; ADD: x + (10 * _1) : int
2858 _5 = _2 * 15;
2859 _6 = x + _3; ADD: x + (15 * _1) : int
2860
2861 Right now replacing _6 would cause insertion of an initializer
2862 of the form "short int T = _1 * 5;" followed by a cast to
2863 int, which could overflow incorrectly. Had we recorded _2 or
2864 (int)_1 as the stride, this wouldn't happen. However, doing
2865 this breaks other opportunities, so this will require some
2866 care. */
2867 else if (!incr_vec[i].initializer
2868 && TREE_CODE (first_dep->stride) != INTEGER_CST
2869 && !legal_cast_p_1 (first_dep->stride,
2870 gimple_assign_lhs (first_dep->cand_stmt)))
2871
2872 incr_vec[i].cost = COST_INFINITE;
2873
2874 /* If we need to add an initializer, make sure we don't introduce
2875 a multiply by a pointer type, which can happen in certain cast
2876 scenarios. FIXME: When cleaning up these cast issues, we can
2877 afford to introduce the multiply provided we cast out to an
2878 unsigned int of appropriate size. */
2879 else if (!incr_vec[i].initializer
2880 && TREE_CODE (first_dep->stride) != INTEGER_CST
2881 && POINTER_TYPE_P (TREE_TYPE (first_dep->stride)))
2882
2883 incr_vec[i].cost = COST_INFINITE;
2884
2885 /* For any other increment, if this is a multiply candidate, we
2886 must introduce a temporary T and initialize it with
2887 T_0 = stride * increment. When optimizing for speed, walk the
2888 candidate tree to calculate the best cost reduction along any
2889 path; if it offsets the fixed cost of inserting the initializer,
2890 replacing the increment is profitable. When optimizing for
2891 size, instead calculate the total cost reduction from replacing
2892 all candidates with this increment. */
2893 else if (first_dep->kind == CAND_MULT)
2894 {
2895 int cost = mult_by_coeff_cost (incr, mode, speed);
2896 int repl_savings = mul_cost (speed, mode) - add_cost (speed, mode);
2897 if (speed)
2898 cost = lowest_cost_path (cost, repl_savings, first_dep,
2899 incr_vec[i].incr, COUNT_PHIS);
2900 else
2901 cost -= total_savings (repl_savings, first_dep, incr_vec[i].incr,
2902 COUNT_PHIS);
2903
2904 incr_vec[i].cost = cost;
2905 }
2906
2907 /* If this is an add candidate, the initializer may already
2908 exist, so only calculate the cost of the initializer if it
2909 doesn't. We are replacing one add with another here, so the
2910 known replacement savings is zero. We will account for removal
2911 of dead instructions in lowest_cost_path or total_savings. */
2912 else
2913 {
2914 int cost = 0;
2915 if (!incr_vec[i].initializer)
2916 cost = mult_by_coeff_cost (incr, mode, speed);
2917
2918 if (speed)
2919 cost = lowest_cost_path (cost, 0, first_dep, incr_vec[i].incr,
2920 DONT_COUNT_PHIS);
2921 else
2922 cost -= total_savings (0, first_dep, incr_vec[i].incr,
2923 DONT_COUNT_PHIS);
2924
2925 incr_vec[i].cost = cost;
2926 }
2927 }
2928 }
2929
2930 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2931 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2932 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2933 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2934 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2935
2936 static basic_block
2937 ncd_for_two_cands (basic_block bb1, basic_block bb2,
2938 slsr_cand_t c1, slsr_cand_t c2, slsr_cand_t *where)
2939 {
2940 basic_block ncd;
2941
2942 if (!bb1)
2943 {
2944 *where = c2;
2945 return bb2;
2946 }
2947
2948 if (!bb2)
2949 {
2950 *where = c1;
2951 return bb1;
2952 }
2953
2954 ncd = nearest_common_dominator (CDI_DOMINATORS, bb1, bb2);
2955
2956 /* If both candidates are in the same block, the earlier
2957 candidate wins. */
2958 if (bb1 == ncd && bb2 == ncd)
2959 {
2960 if (!c1 || (c2 && c2->cand_num < c1->cand_num))
2961 *where = c2;
2962 else
2963 *where = c1;
2964 }
2965
2966 /* Otherwise, if one of them produced a candidate in the
2967 dominator, that one wins. */
2968 else if (bb1 == ncd)
2969 *where = c1;
2970
2971 else if (bb2 == ncd)
2972 *where = c2;
2973
2974 /* If neither matches the dominator, neither wins. */
2975 else
2976 *where = NULL;
2977
2978 return ncd;
2979 }
2980
2981 /* Consider all candidates that feed PHI. Find the nearest common
2982 dominator of those candidates requiring the given increment INCR.
2983 Further find and return the nearest common dominator of this result
2984 with block NCD. If the returned block contains one or more of the
2985 candidates, return the earliest candidate in the block in *WHERE. */
2986
2987 static basic_block
2988 ncd_with_phi (slsr_cand_t c, const widest_int &incr, gphi *phi,
2989 basic_block ncd, slsr_cand_t *where)
2990 {
2991 unsigned i;
2992 slsr_cand_t basis = lookup_cand (c->basis);
2993 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
2994
2995 for (i = 0; i < gimple_phi_num_args (phi); i++)
2996 {
2997 tree arg = gimple_phi_arg_def (phi, i);
2998
2999 if (!operand_equal_p (arg, phi_cand->base_expr, 0))
3000 {
3001 gimple arg_def = SSA_NAME_DEF_STMT (arg);
3002
3003 if (gimple_code (arg_def) == GIMPLE_PHI)
3004 ncd = ncd_with_phi (c, incr, as_a <gphi *> (arg_def), ncd,
3005 where);
3006 else
3007 {
3008 slsr_cand_t arg_cand = base_cand_from_table (arg);
3009 widest_int diff = arg_cand->index - basis->index;
3010 basic_block pred = gimple_phi_arg_edge (phi, i)->src;
3011
3012 if ((incr == diff) || (!address_arithmetic_p && incr == -diff))
3013 ncd = ncd_for_two_cands (ncd, pred, *where, NULL, where);
3014 }
3015 }
3016 }
3017
3018 return ncd;
3019 }
3020
3021 /* Consider the candidate C together with any candidates that feed
3022 C's phi dependence (if any). Find and return the nearest common
3023 dominator of those candidates requiring the given increment INCR.
3024 If the returned block contains one or more of the candidates,
3025 return the earliest candidate in the block in *WHERE. */
3026
3027 static basic_block
3028 ncd_of_cand_and_phis (slsr_cand_t c, const widest_int &incr, slsr_cand_t *where)
3029 {
3030 basic_block ncd = NULL;
3031
3032 if (cand_abs_increment (c) == incr)
3033 {
3034 ncd = gimple_bb (c->cand_stmt);
3035 *where = c;
3036 }
3037
3038 if (phi_dependent_cand_p (c))
3039 ncd = ncd_with_phi (c, incr,
3040 as_a <gphi *> (lookup_cand (c->def_phi)->cand_stmt),
3041 ncd, where);
3042
3043 return ncd;
3044 }
3045
3046 /* Consider all candidates in the tree rooted at C for which INCR
3047 represents the required increment of C relative to its basis.
3048 Find and return the basic block that most nearly dominates all
3049 such candidates. If the returned block contains one or more of
3050 the candidates, return the earliest candidate in the block in
3051 *WHERE. */
3052
3053 static basic_block
3054 nearest_common_dominator_for_cands (slsr_cand_t c, const widest_int &incr,
3055 slsr_cand_t *where)
3056 {
3057 basic_block sib_ncd = NULL, dep_ncd = NULL, this_ncd = NULL, ncd;
3058 slsr_cand_t sib_where = NULL, dep_where = NULL, this_where = NULL, new_where;
3059
3060 /* First find the NCD of all siblings and dependents. */
3061 if (c->sibling)
3062 sib_ncd = nearest_common_dominator_for_cands (lookup_cand (c->sibling),
3063 incr, &sib_where);
3064 if (c->dependent)
3065 dep_ncd = nearest_common_dominator_for_cands (lookup_cand (c->dependent),
3066 incr, &dep_where);
3067 if (!sib_ncd && !dep_ncd)
3068 {
3069 new_where = NULL;
3070 ncd = NULL;
3071 }
3072 else if (sib_ncd && !dep_ncd)
3073 {
3074 new_where = sib_where;
3075 ncd = sib_ncd;
3076 }
3077 else if (dep_ncd && !sib_ncd)
3078 {
3079 new_where = dep_where;
3080 ncd = dep_ncd;
3081 }
3082 else
3083 ncd = ncd_for_two_cands (sib_ncd, dep_ncd, sib_where,
3084 dep_where, &new_where);
3085
3086 /* If the candidate's increment doesn't match the one we're interested
3087 in (and nor do any increments for feeding defs of a phi-dependence),
3088 then the result depends only on siblings and dependents. */
3089 this_ncd = ncd_of_cand_and_phis (c, incr, &this_where);
3090
3091 if (!this_ncd || cand_already_replaced (c))
3092 {
3093 *where = new_where;
3094 return ncd;
3095 }
3096
3097 /* Otherwise, compare this candidate with the result from all siblings
3098 and dependents. */
3099 ncd = ncd_for_two_cands (ncd, this_ncd, new_where, this_where, where);
3100
3101 return ncd;
3102 }
3103
3104 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
3105
3106 static inline bool
3107 profitable_increment_p (unsigned index)
3108 {
3109 return (incr_vec[index].cost <= COST_NEUTRAL);
3110 }
3111
3112 /* For each profitable increment in the increment vector not equal to
3113 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3114 dominator of all statements in the candidate chain rooted at C
3115 that require that increment, and insert an initializer
3116 T_0 = stride * increment at that location. Record T_0 with the
3117 increment record. */
3118
3119 static void
3120 insert_initializers (slsr_cand_t c)
3121 {
3122 unsigned i;
3123
3124 for (i = 0; i < incr_vec_len; i++)
3125 {
3126 basic_block bb;
3127 slsr_cand_t where = NULL;
3128 gassign *init_stmt;
3129 tree stride_type, new_name, incr_tree;
3130 widest_int incr = incr_vec[i].incr;
3131
3132 if (!profitable_increment_p (i)
3133 || incr == 1
3134 || (incr == -1
3135 && gimple_assign_rhs_code (c->cand_stmt) != POINTER_PLUS_EXPR)
3136 || incr == 0)
3137 continue;
3138
3139 /* We may have already identified an existing initializer that
3140 will suffice. */
3141 if (incr_vec[i].initializer)
3142 {
3143 if (dump_file && (dump_flags & TDF_DETAILS))
3144 {
3145 fputs ("Using existing initializer: ", dump_file);
3146 print_gimple_stmt (dump_file,
3147 SSA_NAME_DEF_STMT (incr_vec[i].initializer),
3148 0, 0);
3149 }
3150 continue;
3151 }
3152
3153 /* Find the block that most closely dominates all candidates
3154 with this increment. If there is at least one candidate in
3155 that block, the earliest one will be returned in WHERE. */
3156 bb = nearest_common_dominator_for_cands (c, incr, &where);
3157
3158 /* Create a new SSA name to hold the initializer's value. */
3159 stride_type = TREE_TYPE (c->stride);
3160 new_name = make_temp_ssa_name (stride_type, NULL, "slsr");
3161 incr_vec[i].initializer = new_name;
3162
3163 /* Create the initializer and insert it in the latest possible
3164 dominating position. */
3165 incr_tree = wide_int_to_tree (stride_type, incr);
3166 init_stmt = gimple_build_assign (new_name, MULT_EXPR,
3167 c->stride, incr_tree);
3168 if (where)
3169 {
3170 gimple_stmt_iterator gsi = gsi_for_stmt (where->cand_stmt);
3171 gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
3172 gimple_set_location (init_stmt, gimple_location (where->cand_stmt));
3173 }
3174 else
3175 {
3176 gimple_stmt_iterator gsi = gsi_last_bb (bb);
3177 gimple basis_stmt = lookup_cand (c->basis)->cand_stmt;
3178
3179 if (!gsi_end_p (gsi) && is_ctrl_stmt (gsi_stmt (gsi)))
3180 gsi_insert_before (&gsi, init_stmt, GSI_SAME_STMT);
3181 else
3182 gsi_insert_after (&gsi, init_stmt, GSI_SAME_STMT);
3183
3184 gimple_set_location (init_stmt, gimple_location (basis_stmt));
3185 }
3186
3187 if (dump_file && (dump_flags & TDF_DETAILS))
3188 {
3189 fputs ("Inserting initializer: ", dump_file);
3190 print_gimple_stmt (dump_file, init_stmt, 0, 0);
3191 }
3192 }
3193 }
3194
3195 /* Return TRUE iff all required increments for candidates feeding PHI
3196 are profitable to replace on behalf of candidate C. */
3197
3198 static bool
3199 all_phi_incrs_profitable (slsr_cand_t c, gimple phi)
3200 {
3201 unsigned i;
3202 slsr_cand_t basis = lookup_cand (c->basis);
3203 slsr_cand_t phi_cand = base_cand_from_table (gimple_phi_result (phi));
3204
3205 for (i = 0; i < gimple_phi_num_args (phi); i++)
3206 {
3207 tree arg = gimple_phi_arg_def (phi, i);
3208
3209 if (!operand_equal_p (arg, phi_cand->base_expr, 0))
3210 {
3211 gimple arg_def = SSA_NAME_DEF_STMT (arg);
3212
3213 if (gimple_code (arg_def) == GIMPLE_PHI)
3214 {
3215 if (!all_phi_incrs_profitable (c, arg_def))
3216 return false;
3217 }
3218 else
3219 {
3220 int j;
3221 slsr_cand_t arg_cand = base_cand_from_table (arg);
3222 widest_int increment = arg_cand->index - basis->index;
3223
3224 if (!address_arithmetic_p && wi::neg_p (increment))
3225 increment = -increment;
3226
3227 j = incr_vec_index (increment);
3228
3229 if (dump_file && (dump_flags & TDF_DETAILS))
3230 {
3231 fprintf (dump_file, " Conditional candidate %d, phi: ",
3232 c->cand_num);
3233 print_gimple_stmt (dump_file, phi, 0, 0);
3234 fputs (" increment: ", dump_file);
3235 print_decs (increment, dump_file);
3236 if (j < 0)
3237 fprintf (dump_file,
3238 "\n Not replaced; incr_vec overflow.\n");
3239 else {
3240 fprintf (dump_file, "\n cost: %d\n", incr_vec[j].cost);
3241 if (profitable_increment_p (j))
3242 fputs (" Replacing...\n", dump_file);
3243 else
3244 fputs (" Not replaced.\n", dump_file);
3245 }
3246 }
3247
3248 if (j < 0 || !profitable_increment_p (j))
3249 return false;
3250 }
3251 }
3252 }
3253
3254 return true;
3255 }
3256
3257 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3258 type TO_TYPE, and insert it in front of the statement represented
3259 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3260 the new SSA name. */
3261
3262 static tree
3263 introduce_cast_before_cand (slsr_cand_t c, tree to_type, tree from_expr)
3264 {
3265 tree cast_lhs;
3266 gassign *cast_stmt;
3267 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3268
3269 cast_lhs = make_temp_ssa_name (to_type, NULL, "slsr");
3270 cast_stmt = gimple_build_assign (cast_lhs, NOP_EXPR, from_expr);
3271 gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
3272 gsi_insert_before (&gsi, cast_stmt, GSI_SAME_STMT);
3273
3274 if (dump_file && (dump_flags & TDF_DETAILS))
3275 {
3276 fputs (" Inserting: ", dump_file);
3277 print_gimple_stmt (dump_file, cast_stmt, 0, 0);
3278 }
3279
3280 return cast_lhs;
3281 }
3282
3283 /* Replace the RHS of the statement represented by candidate C with
3284 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3285 leave C unchanged or just interchange its operands. The original
3286 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3287 If the replacement was made and we are doing a details dump,
3288 return the revised statement, else NULL. */
3289
3290 static gimple
3291 replace_rhs_if_not_dup (enum tree_code new_code, tree new_rhs1, tree new_rhs2,
3292 enum tree_code old_code, tree old_rhs1, tree old_rhs2,
3293 slsr_cand_t c)
3294 {
3295 if (new_code != old_code
3296 || ((!operand_equal_p (new_rhs1, old_rhs1, 0)
3297 || !operand_equal_p (new_rhs2, old_rhs2, 0))
3298 && (!operand_equal_p (new_rhs1, old_rhs2, 0)
3299 || !operand_equal_p (new_rhs2, old_rhs1, 0))))
3300 {
3301 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3302 gimple_assign_set_rhs_with_ops (&gsi, new_code, new_rhs1, new_rhs2);
3303 update_stmt (gsi_stmt (gsi));
3304 c->cand_stmt = gsi_stmt (gsi);
3305
3306 if (dump_file && (dump_flags & TDF_DETAILS))
3307 return gsi_stmt (gsi);
3308 }
3309
3310 else if (dump_file && (dump_flags & TDF_DETAILS))
3311 fputs (" (duplicate, not actually replacing)\n", dump_file);
3312
3313 return NULL;
3314 }
3315
3316 /* Strength-reduce the statement represented by candidate C by replacing
3317 it with an equivalent addition or subtraction. I is the index into
3318 the increment vector identifying C's increment. NEW_VAR is used to
3319 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3320 is the rhs1 to use in creating the add/subtract. */
3321
3322 static void
3323 replace_one_candidate (slsr_cand_t c, unsigned i, tree basis_name)
3324 {
3325 gimple stmt_to_print = NULL;
3326 tree orig_rhs1, orig_rhs2;
3327 tree rhs2;
3328 enum tree_code orig_code, repl_code;
3329 widest_int cand_incr;
3330
3331 orig_code = gimple_assign_rhs_code (c->cand_stmt);
3332 orig_rhs1 = gimple_assign_rhs1 (c->cand_stmt);
3333 orig_rhs2 = gimple_assign_rhs2 (c->cand_stmt);
3334 cand_incr = cand_increment (c);
3335
3336 if (dump_file && (dump_flags & TDF_DETAILS))
3337 {
3338 fputs ("Replacing: ", dump_file);
3339 print_gimple_stmt (dump_file, c->cand_stmt, 0, 0);
3340 stmt_to_print = c->cand_stmt;
3341 }
3342
3343 if (address_arithmetic_p)
3344 repl_code = POINTER_PLUS_EXPR;
3345 else
3346 repl_code = PLUS_EXPR;
3347
3348 /* If the increment has an initializer T_0, replace the candidate
3349 statement with an add of the basis name and the initializer. */
3350 if (incr_vec[i].initializer)
3351 {
3352 tree init_type = TREE_TYPE (incr_vec[i].initializer);
3353 tree orig_type = TREE_TYPE (orig_rhs2);
3354
3355 if (types_compatible_p (orig_type, init_type))
3356 rhs2 = incr_vec[i].initializer;
3357 else
3358 rhs2 = introduce_cast_before_cand (c, orig_type,
3359 incr_vec[i].initializer);
3360
3361 if (incr_vec[i].incr != cand_incr)
3362 {
3363 gcc_assert (repl_code == PLUS_EXPR);
3364 repl_code = MINUS_EXPR;
3365 }
3366
3367 stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
3368 orig_code, orig_rhs1, orig_rhs2,
3369 c);
3370 }
3371
3372 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3373 with a subtract of the stride from the basis name, a copy
3374 from the basis name, or an add of the stride to the basis
3375 name, respectively. It may be necessary to introduce a
3376 cast (or reuse an existing cast). */
3377 else if (cand_incr == 1)
3378 {
3379 tree stride_type = TREE_TYPE (c->stride);
3380 tree orig_type = TREE_TYPE (orig_rhs2);
3381
3382 if (types_compatible_p (orig_type, stride_type))
3383 rhs2 = c->stride;
3384 else
3385 rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
3386
3387 stmt_to_print = replace_rhs_if_not_dup (repl_code, basis_name, rhs2,
3388 orig_code, orig_rhs1, orig_rhs2,
3389 c);
3390 }
3391
3392 else if (cand_incr == -1)
3393 {
3394 tree stride_type = TREE_TYPE (c->stride);
3395 tree orig_type = TREE_TYPE (orig_rhs2);
3396 gcc_assert (repl_code != POINTER_PLUS_EXPR);
3397
3398 if (types_compatible_p (orig_type, stride_type))
3399 rhs2 = c->stride;
3400 else
3401 rhs2 = introduce_cast_before_cand (c, orig_type, c->stride);
3402
3403 if (orig_code != MINUS_EXPR
3404 || !operand_equal_p (basis_name, orig_rhs1, 0)
3405 || !operand_equal_p (rhs2, orig_rhs2, 0))
3406 {
3407 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3408 gimple_assign_set_rhs_with_ops (&gsi, MINUS_EXPR, basis_name, rhs2);
3409 update_stmt (gsi_stmt (gsi));
3410 c->cand_stmt = gsi_stmt (gsi);
3411
3412 if (dump_file && (dump_flags & TDF_DETAILS))
3413 stmt_to_print = gsi_stmt (gsi);
3414 }
3415 else if (dump_file && (dump_flags & TDF_DETAILS))
3416 fputs (" (duplicate, not actually replacing)\n", dump_file);
3417 }
3418
3419 else if (cand_incr == 0)
3420 {
3421 tree lhs = gimple_assign_lhs (c->cand_stmt);
3422 tree lhs_type = TREE_TYPE (lhs);
3423 tree basis_type = TREE_TYPE (basis_name);
3424
3425 if (types_compatible_p (lhs_type, basis_type))
3426 {
3427 gassign *copy_stmt = gimple_build_assign (lhs, basis_name);
3428 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3429 gimple_set_location (copy_stmt, gimple_location (c->cand_stmt));
3430 gsi_replace (&gsi, copy_stmt, false);
3431 c->cand_stmt = copy_stmt;
3432
3433 if (dump_file && (dump_flags & TDF_DETAILS))
3434 stmt_to_print = copy_stmt;
3435 }
3436 else
3437 {
3438 gimple_stmt_iterator gsi = gsi_for_stmt (c->cand_stmt);
3439 gassign *cast_stmt = gimple_build_assign (lhs, NOP_EXPR, basis_name);
3440 gimple_set_location (cast_stmt, gimple_location (c->cand_stmt));
3441 gsi_replace (&gsi, cast_stmt, false);
3442 c->cand_stmt = cast_stmt;
3443
3444 if (dump_file && (dump_flags & TDF_DETAILS))
3445 stmt_to_print = cast_stmt;
3446 }
3447 }
3448 else
3449 gcc_unreachable ();
3450
3451 if (dump_file && (dump_flags & TDF_DETAILS) && stmt_to_print)
3452 {
3453 fputs ("With: ", dump_file);
3454 print_gimple_stmt (dump_file, stmt_to_print, 0, 0);
3455 fputs ("\n", dump_file);
3456 }
3457 }
3458
3459 /* For each candidate in the tree rooted at C, replace it with
3460 an increment if such has been shown to be profitable. */
3461
3462 static void
3463 replace_profitable_candidates (slsr_cand_t c)
3464 {
3465 if (!cand_already_replaced (c))
3466 {
3467 widest_int increment = cand_abs_increment (c);
3468 enum tree_code orig_code = gimple_assign_rhs_code (c->cand_stmt);
3469 int i;
3470
3471 i = incr_vec_index (increment);
3472
3473 /* Only process profitable increments. Nothing useful can be done
3474 to a cast or copy. */
3475 if (i >= 0
3476 && profitable_increment_p (i)
3477 && orig_code != MODIFY_EXPR
3478 && !CONVERT_EXPR_CODE_P (orig_code))
3479 {
3480 if (phi_dependent_cand_p (c))
3481 {
3482 gimple phi = lookup_cand (c->def_phi)->cand_stmt;
3483
3484 if (all_phi_incrs_profitable (c, phi))
3485 {
3486 /* Look up the LHS SSA name from C's basis. This will be
3487 the RHS1 of the adds we will introduce to create new
3488 phi arguments. */
3489 slsr_cand_t basis = lookup_cand (c->basis);
3490 tree basis_name = gimple_assign_lhs (basis->cand_stmt);
3491
3492 /* Create a new phi statement that will represent C's true
3493 basis after the transformation is complete. */
3494 location_t loc = gimple_location (c->cand_stmt);
3495 tree name = create_phi_basis (c, phi, basis_name,
3496 loc, UNKNOWN_STRIDE);
3497
3498 /* Replace C with an add of the new basis phi and the
3499 increment. */
3500 replace_one_candidate (c, i, name);
3501 }
3502 }
3503 else
3504 {
3505 slsr_cand_t basis = lookup_cand (c->basis);
3506 tree basis_name = gimple_assign_lhs (basis->cand_stmt);
3507 replace_one_candidate (c, i, basis_name);
3508 }
3509 }
3510 }
3511
3512 if (c->sibling)
3513 replace_profitable_candidates (lookup_cand (c->sibling));
3514
3515 if (c->dependent)
3516 replace_profitable_candidates (lookup_cand (c->dependent));
3517 }
3518 \f
3519 /* Analyze costs of related candidates in the candidate vector,
3520 and make beneficial replacements. */
3521
3522 static void
3523 analyze_candidates_and_replace (void)
3524 {
3525 unsigned i;
3526 slsr_cand_t c;
3527
3528 /* Each candidate that has a null basis and a non-null
3529 dependent is the root of a tree of related statements.
3530 Analyze each tree to determine a subset of those
3531 statements that can be replaced with maximum benefit. */
3532 FOR_EACH_VEC_ELT (cand_vec, i, c)
3533 {
3534 slsr_cand_t first_dep;
3535
3536 if (c->basis != 0 || c->dependent == 0)
3537 continue;
3538
3539 if (dump_file && (dump_flags & TDF_DETAILS))
3540 fprintf (dump_file, "\nProcessing dependency tree rooted at %d.\n",
3541 c->cand_num);
3542
3543 first_dep = lookup_cand (c->dependent);
3544
3545 /* If this is a chain of CAND_REFs, unconditionally replace
3546 each of them with a strength-reduced data reference. */
3547 if (c->kind == CAND_REF)
3548 replace_refs (c);
3549
3550 /* If the common stride of all related candidates is a known
3551 constant, each candidate without a phi-dependence can be
3552 profitably replaced. Each replaces a multiply by a single
3553 add, with the possibility that a feeding add also goes dead.
3554 A candidate with a phi-dependence is replaced only if the
3555 compensation code it requires is offset by the strength
3556 reduction savings. */
3557 else if (TREE_CODE (c->stride) == INTEGER_CST)
3558 replace_uncond_cands_and_profitable_phis (first_dep);
3559
3560 /* When the stride is an SSA name, it may still be profitable
3561 to replace some or all of the dependent candidates, depending
3562 on whether the introduced increments can be reused, or are
3563 less expensive to calculate than the replaced statements. */
3564 else
3565 {
3566 machine_mode mode;
3567 bool speed;
3568
3569 /* Determine whether we'll be generating pointer arithmetic
3570 when replacing candidates. */
3571 address_arithmetic_p = (c->kind == CAND_ADD
3572 && POINTER_TYPE_P (c->cand_type));
3573
3574 /* If all candidates have already been replaced under other
3575 interpretations, nothing remains to be done. */
3576 if (!count_candidates (c))
3577 continue;
3578
3579 /* Construct an array of increments for this candidate chain. */
3580 incr_vec = XNEWVEC (incr_info, MAX_INCR_VEC_LEN);
3581 incr_vec_len = 0;
3582 record_increments (c);
3583
3584 /* Determine which increments are profitable to replace. */
3585 mode = TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c->cand_stmt)));
3586 speed = optimize_cands_for_speed_p (c);
3587 analyze_increments (first_dep, mode, speed);
3588
3589 /* Insert initializers of the form T_0 = stride * increment
3590 for use in profitable replacements. */
3591 insert_initializers (first_dep);
3592 dump_incr_vec ();
3593
3594 /* Perform the replacements. */
3595 replace_profitable_candidates (first_dep);
3596 free (incr_vec);
3597 }
3598 }
3599 }
3600
3601 namespace {
3602
3603 const pass_data pass_data_strength_reduction =
3604 {
3605 GIMPLE_PASS, /* type */
3606 "slsr", /* name */
3607 OPTGROUP_NONE, /* optinfo_flags */
3608 TV_GIMPLE_SLSR, /* tv_id */
3609 ( PROP_cfg | PROP_ssa ), /* properties_required */
3610 0, /* properties_provided */
3611 0, /* properties_destroyed */
3612 0, /* todo_flags_start */
3613 0, /* todo_flags_finish */
3614 };
3615
3616 class pass_strength_reduction : public gimple_opt_pass
3617 {
3618 public:
3619 pass_strength_reduction (gcc::context *ctxt)
3620 : gimple_opt_pass (pass_data_strength_reduction, ctxt)
3621 {}
3622
3623 /* opt_pass methods: */
3624 virtual bool gate (function *) { return flag_tree_slsr; }
3625 virtual unsigned int execute (function *);
3626
3627 }; // class pass_strength_reduction
3628
3629 unsigned
3630 pass_strength_reduction::execute (function *fun)
3631 {
3632 /* Create the obstack where candidates will reside. */
3633 gcc_obstack_init (&cand_obstack);
3634
3635 /* Allocate the candidate vector. */
3636 cand_vec.create (128);
3637
3638 /* Allocate the mapping from statements to candidate indices. */
3639 stmt_cand_map = new hash_map<gimple, slsr_cand_t>;
3640
3641 /* Create the obstack where candidate chains will reside. */
3642 gcc_obstack_init (&chain_obstack);
3643
3644 /* Allocate the mapping from base expressions to candidate chains. */
3645 base_cand_map = new hash_table<cand_chain_hasher> (500);
3646
3647 /* Allocate the mapping from bases to alternative bases. */
3648 alt_base_map = new hash_map<tree, tree>;
3649
3650 /* Initialize the loop optimizer. We need to detect flow across
3651 back edges, and this gives us dominator information as well. */
3652 loop_optimizer_init (AVOID_CFG_MODIFICATIONS);
3653
3654 /* Walk the CFG in predominator order looking for strength reduction
3655 candidates. */
3656 find_candidates_dom_walker (CDI_DOMINATORS)
3657 .walk (fun->cfg->x_entry_block_ptr);
3658
3659 if (dump_file && (dump_flags & TDF_DETAILS))
3660 {
3661 dump_cand_vec ();
3662 dump_cand_chains ();
3663 }
3664
3665 delete alt_base_map;
3666 free_affine_expand_cache (&name_expansions);
3667
3668 /* Analyze costs and make appropriate replacements. */
3669 analyze_candidates_and_replace ();
3670
3671 loop_optimizer_finalize ();
3672 delete base_cand_map;
3673 base_cand_map = NULL;
3674 obstack_free (&chain_obstack, NULL);
3675 delete stmt_cand_map;
3676 cand_vec.release ();
3677 obstack_free (&cand_obstack, NULL);
3678
3679 return 0;
3680 }
3681
3682 } // anon namespace
3683
3684 gimple_opt_pass *
3685 make_pass_strength_reduction (gcc::context *ctxt)
3686 {
3687 return new pass_strength_reduction (ctxt);
3688 }