1 /* Straight-line strength reduction.
2 Copyright (C) 2012-2015 Free Software Foundation, Inc.
3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
5 This file is part of GCC.
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
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
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/>. */
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.
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.
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. */
38 #include "coretypes.h"
43 #include "fold-const.h"
46 #include "hard-reg-set.h"
48 #include "dominance.h"
50 #include "basic-block.h"
51 #include "tree-ssa-alias.h"
52 #include "internal-fn.h"
53 #include "gimple-expr.h"
55 #include "gimple-iterator.h"
56 #include "gimplify-me.h"
57 #include "stor-layout.h"
60 #include "insn-config.h"
69 #include "tree-pass.h"
71 #include "gimple-pretty-print.h"
72 #include "gimple-ssa.h"
74 #include "tree-phinodes.h"
75 #include "ssa-iterators.h"
76 #include "stringpool.h"
77 #include "tree-ssanames.h"
80 #include "tree-ssa-address.h"
81 #include "tree-affine.h"
82 #include "wide-int-print.h"
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
90 (CAND_MULT) S1: X = (B + i) * S
91 (CAND_ADD) S1: X = B + (i * S)
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."
97 Any statement S0 that dominates S1 and is of the form:
99 (CAND_MULT) S0: Y = (B + i') * S
100 (CAND_ADD) S0: Y = B + (i' * S)
102 is called a "basis" for S1. In both cases, S1 may be replaced by
104 S1': X = Y + (i - i') * S,
106 where (i - i') * S is folded to the extent possible.
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
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.
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.
128 Currently we don't recognize:
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.
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
146 base: MEM_REF (T1, C1)
147 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
148 bitpos: C4 * BITS_PER_UNIT
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).
154 When this pattern is recognized, the original memory reference
155 can be replaced with:
157 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
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
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.
177 Conditional candidates
178 ======================
180 Conditional candidates are best illustrated with an example.
181 Consider the code sequence:
184 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
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)
191 Here strength reduction is complicated by the uncertain value of x_2.
192 A legitimate transformation is:
201 (4) [x_2 = PHI <x_0, x_1>;]
202 (4a) t_2 = PHI <a_0, t_1>;
206 where the bracketed instructions may go dead.
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).
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).
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.
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. */
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
;
244 /* The kind of candidate. */
255 /* The candidate statement S1. */
258 /* The base expression B: often an SSA name, but not always. */
264 /* The index constant i. */
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.) */
274 /* The kind of candidate (CAND_MULT, etc.). */
277 /* Index of this candidate in the candidate vector. */
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"
284 cand_idx next_interp
;
286 /* Index of the basis statement S0, if any, in the candidate vector. */
289 /* First candidate for which this candidate is a basis, if one exists. */
292 /* Next candidate having the same basis as this one. */
295 /* If this is a conditional candidate, the CAND_PHI candidate
296 that defines the base SSA name B. */
299 /* Savings that can be expected from eliminating dead code if this
300 candidate is replaced. */
304 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
305 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
307 /* Pointers to candidates are chained together as part of a mapping
308 from base expressions to the candidates that use them. */
312 /* Base expression for the chain of candidates: often, but not
313 always, an SSA name. */
316 /* Pointer to a candidate. */
320 struct cand_chain_d
*next
;
324 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
325 typedef const struct cand_chain_d
*const_cand_chain_t
;
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.
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. */
339 /* The increment that relates a candidate to its basis. */
342 /* How many times the increment occurs in the candidate tree. */
345 /* Cost of replacing candidates using this increment. Negative and
346 zero costs indicate replacement should be performed. */
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. */
355 /* If the initializer was found to already exist, this is the block
356 where it was found. */
360 typedef struct incr_info_d incr_info
, *incr_info_t
;
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
;
379 enum phi_adjust_status
385 enum count_phis_status
391 /* Pointer map embodying a mapping from statements to candidates. */
392 static hash_map
<gimple
, slsr_cand_t
> *stmt_cand_map
;
394 /* Obstack for candidates. */
395 static struct obstack cand_obstack
;
397 /* Obstack for candidate chains. */
398 static struct obstack chain_obstack
;
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;
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
;
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
);
417 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
420 lookup_cand (cand_idx idx
)
422 return cand_vec
[idx
- 1];
425 /* Helper for hashing a candidate chain header. */
427 struct cand_chain_hasher
: nofree_ptr_hash
<cand_chain
>
429 static inline hashval_t
hash (const cand_chain
*);
430 static inline bool equal (const cand_chain
*, const cand_chain
*);
434 cand_chain_hasher::hash (const cand_chain
*p
)
436 tree base_expr
= p
->base_expr
;
437 return iterative_hash_expr (base_expr
, 0);
441 cand_chain_hasher::equal (const cand_chain
*chain1
, const cand_chain
*chain2
)
443 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
446 /* Hash table embodying a mapping from base exprs to chains of candidates. */
447 static hash_table
<cand_chain_hasher
> *base_cand_map
;
449 /* Pointer map used by tree_to_aff_combination_expand. */
450 static hash_map
<tree
, name_expansion
*> *name_expansions
;
451 /* Pointer map embodying a mapping from bases to alternative bases. */
452 static hash_map
<tree
, tree
> *alt_base_map
;
454 /* Given BASE, use the tree affine combiniation facilities to
455 find the underlying tree expression for BASE, with any
456 immediate offset excluded.
458 N.B. we should eliminate this backtracking with better forward
459 analysis in a future release. */
462 get_alternative_base (tree base
)
464 tree
*result
= alt_base_map
->get (base
);
471 tree_to_aff_combination_expand (base
, TREE_TYPE (base
),
472 &aff
, &name_expansions
);
474 expr
= aff_combination_to_tree (&aff
);
476 gcc_assert (!alt_base_map
->put (base
, base
== expr
? NULL
: expr
));
478 return expr
== base
? NULL
: expr
;
484 /* Look in the candidate table for a CAND_PHI that defines BASE and
485 return it if found; otherwise return NULL. */
488 find_phi_def (tree base
)
492 if (TREE_CODE (base
) != SSA_NAME
)
495 c
= base_cand_from_table (base
);
497 if (!c
|| c
->kind
!= CAND_PHI
)
503 /* Helper routine for find_basis_for_candidate. May be called twice:
504 once for the candidate's base expr, and optionally again either for
505 the candidate's phi definition or for a CAND_REF's alternative base
509 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
511 cand_chain mapping_key
;
513 slsr_cand_t basis
= NULL
;
515 // Limit potential of N^2 behavior for long candidate chains.
517 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
519 mapping_key
.base_expr
= base_expr
;
520 chain
= base_cand_map
->find (&mapping_key
);
522 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
524 slsr_cand_t one_basis
= chain
->cand
;
526 if (one_basis
->kind
!= c
->kind
527 || one_basis
->cand_stmt
== c
->cand_stmt
528 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
529 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
530 || !dominated_by_p (CDI_DOMINATORS
,
531 gimple_bb (c
->cand_stmt
),
532 gimple_bb (one_basis
->cand_stmt
)))
535 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
542 /* Use the base expr from candidate C to look for possible candidates
543 that can serve as a basis for C. Each potential basis must also
544 appear in a block that dominates the candidate statement and have
545 the same stride and type. If more than one possible basis exists,
546 the one with highest index in the vector is chosen; this will be
547 the most immediately dominating basis. */
550 find_basis_for_candidate (slsr_cand_t c
)
552 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
554 /* If a candidate doesn't have a basis using its base expression,
555 it may have a basis hidden by one or more intervening phis. */
556 if (!basis
&& c
->def_phi
)
558 basic_block basis_bb
, phi_bb
;
559 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
560 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
564 /* A hidden basis must dominate the phi-definition of the
565 candidate's base name. */
566 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
567 basis_bb
= gimple_bb (basis
->cand_stmt
);
569 if (phi_bb
== basis_bb
570 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
576 /* If we found a hidden basis, estimate additional dead-code
577 savings if the phi and its feeding statements can be removed. */
578 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
579 c
->dead_savings
+= phi_cand
->dead_savings
;
583 if (flag_expensive_optimizations
&& !basis
&& c
->kind
== CAND_REF
)
585 tree alt_base_expr
= get_alternative_base (c
->base_expr
);
587 basis
= find_basis_for_base_expr (c
, alt_base_expr
);
592 c
->sibling
= basis
->dependent
;
593 basis
->dependent
= c
->cand_num
;
594 return basis
->cand_num
;
600 /* Record a mapping from BASE to C, indicating that C may potentially serve
601 as a basis using that base expression. BASE may be the same as
602 C->BASE_EXPR; alternatively BASE can be a different tree that share the
603 underlining expression of C->BASE_EXPR. */
606 record_potential_basis (slsr_cand_t c
, tree base
)
613 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
614 node
->base_expr
= base
;
617 slot
= base_cand_map
->find_slot (node
, INSERT
);
621 cand_chain_t head
= (cand_chain_t
) (*slot
);
622 node
->next
= head
->next
;
629 /* Allocate storage for a new candidate and initialize its fields.
630 Attempt to find a basis for the candidate.
632 For CAND_REF, an alternative base may also be recorded and used
633 to find a basis. This helps cases where the expression hidden
634 behind BASE (which is usually an SSA_NAME) has immediate offset,
638 a2[i + 20][j] = 2; */
641 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
642 const widest_int
&index
, tree stride
, tree ctype
,
645 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
651 c
->cand_type
= ctype
;
653 c
->cand_num
= cand_vec
.length () + 1;
657 c
->def_phi
= kind
== CAND_MULT
? find_phi_def (base
) : 0;
658 c
->dead_savings
= savings
;
660 cand_vec
.safe_push (c
);
662 if (kind
== CAND_PHI
)
665 c
->basis
= find_basis_for_candidate (c
);
667 record_potential_basis (c
, base
);
668 if (flag_expensive_optimizations
&& kind
== CAND_REF
)
670 tree alt_base
= get_alternative_base (base
);
672 record_potential_basis (c
, alt_base
);
678 /* Determine the target cost of statement GS when compiling according
682 stmt_cost (gimple gs
, bool speed
)
684 tree lhs
, rhs1
, rhs2
;
685 machine_mode lhs_mode
;
687 gcc_assert (is_gimple_assign (gs
));
688 lhs
= gimple_assign_lhs (gs
);
689 rhs1
= gimple_assign_rhs1 (gs
);
690 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
692 switch (gimple_assign_rhs_code (gs
))
695 rhs2
= gimple_assign_rhs2 (gs
);
697 if (tree_fits_shwi_p (rhs2
))
698 return mult_by_coeff_cost (tree_to_shwi (rhs2
), lhs_mode
, speed
);
700 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
701 return mul_cost (speed
, lhs_mode
);
704 case POINTER_PLUS_EXPR
:
706 return add_cost (speed
, lhs_mode
);
709 return neg_cost (speed
, lhs_mode
);
712 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
714 /* Note that we don't assign costs to copies that in most cases
724 /* Look up the defining statement for BASE_IN and return a pointer
725 to its candidate in the candidate table, if any; otherwise NULL.
726 Only CAND_ADD and CAND_MULT candidates are returned. */
729 base_cand_from_table (tree base_in
)
733 gimple def
= SSA_NAME_DEF_STMT (base_in
);
735 return (slsr_cand_t
) NULL
;
737 result
= stmt_cand_map
->get (def
);
739 if (result
&& (*result
)->kind
!= CAND_REF
)
742 return (slsr_cand_t
) NULL
;
745 /* Add an entry to the statement-to-candidate mapping. */
748 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
750 gcc_assert (!stmt_cand_map
->put (gs
, c
));
753 /* Given PHI which contains a phi statement, determine whether it
754 satisfies all the requirements of a phi candidate. If so, create
755 a candidate. Note that a CAND_PHI never has a basis itself, but
756 is used to help find a basis for subsequent candidates. */
759 slsr_process_phi (gphi
*phi
, bool speed
)
762 tree arg0_base
= NULL_TREE
, base_type
;
764 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
765 unsigned savings
= 0;
767 /* A CAND_PHI requires each of its arguments to have the same
768 derived base name. (See the module header commentary for a
769 definition of derived base names.) Furthermore, all feeding
770 definitions must be in the same position in the loop hierarchy
773 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
775 slsr_cand_t arg_cand
;
776 tree arg
= gimple_phi_arg_def (phi
, i
);
777 tree derived_base_name
= NULL_TREE
;
778 gimple arg_stmt
= NULL
;
779 basic_block arg_bb
= NULL
;
781 if (TREE_CODE (arg
) != SSA_NAME
)
784 arg_cand
= base_cand_from_table (arg
);
788 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
790 if (!arg_cand
->next_interp
)
793 arg_cand
= lookup_cand (arg_cand
->next_interp
);
796 if (!integer_onep (arg_cand
->stride
))
799 derived_base_name
= arg_cand
->base_expr
;
800 arg_stmt
= arg_cand
->cand_stmt
;
801 arg_bb
= gimple_bb (arg_stmt
);
803 /* Gather potential dead code savings if the phi statement
804 can be removed later on. */
805 if (has_single_use (arg
))
807 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
808 savings
+= arg_cand
->dead_savings
;
810 savings
+= stmt_cost (arg_stmt
, speed
);
815 derived_base_name
= arg
;
817 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
818 arg_bb
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
820 gimple_bb (SSA_NAME_DEF_STMT (arg
));
823 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
827 arg0_base
= derived_base_name
;
828 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
832 /* Create the candidate. "alloc_cand_and_find_basis" is named
833 misleadingly for this case, as no basis will be sought for a
835 base_type
= TREE_TYPE (arg0_base
);
837 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
,
838 0, integer_one_node
, base_type
, savings
);
840 /* Add the candidate to the statement-candidate mapping. */
841 add_cand_for_stmt (phi
, c
);
844 /* Given PBASE which is a pointer to tree, look up the defining
845 statement for it and check whether the candidate is in the
848 X = B + (1 * S), S is integer constant
849 X = B + (i * S), S is integer one
851 If so, set PBASE to the candidate's base_expr and return double
853 Otherwise, just return double int zero. */
856 backtrace_base_for_ref (tree
*pbase
)
858 tree base_in
= *pbase
;
859 slsr_cand_t base_cand
;
861 STRIP_NOPS (base_in
);
863 /* Strip off widening conversion(s) to handle cases where
864 e.g. 'B' is widened from an 'int' in order to calculate
866 if (CONVERT_EXPR_P (base_in
)
867 && legal_cast_p_1 (base_in
, TREE_OPERAND (base_in
, 0)))
868 base_in
= get_unwidened (base_in
, NULL_TREE
);
870 if (TREE_CODE (base_in
) != SSA_NAME
)
873 base_cand
= base_cand_from_table (base_in
);
875 while (base_cand
&& base_cand
->kind
!= CAND_PHI
)
877 if (base_cand
->kind
== CAND_ADD
878 && base_cand
->index
== 1
879 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
881 /* X = B + (1 * S), S is integer constant. */
882 *pbase
= base_cand
->base_expr
;
883 return wi::to_widest (base_cand
->stride
);
885 else if (base_cand
->kind
== CAND_ADD
886 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
887 && integer_onep (base_cand
->stride
))
889 /* X = B + (i * S), S is integer one. */
890 *pbase
= base_cand
->base_expr
;
891 return base_cand
->index
;
894 if (base_cand
->next_interp
)
895 base_cand
= lookup_cand (base_cand
->next_interp
);
903 /* Look for the following pattern:
905 *PBASE: MEM_REF (T1, C1)
907 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
909 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
911 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
913 *PINDEX: C4 * BITS_PER_UNIT
915 If not present, leave the input values unchanged and return FALSE.
916 Otherwise, modify the input values as follows and return TRUE:
919 *POFFSET: MULT_EXPR (T2, C3)
920 *PINDEX: C1 + (C2 * C3) + C4
922 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
923 will be further restructured to:
926 *POFFSET: MULT_EXPR (T2', C3)
927 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
930 restructure_reference (tree
*pbase
, tree
*poffset
, widest_int
*pindex
,
933 tree base
= *pbase
, offset
= *poffset
;
934 widest_int index
= *pindex
;
935 tree mult_op0
, t1
, t2
, type
;
936 widest_int c1
, c2
, c3
, c4
, c5
;
940 || TREE_CODE (base
) != MEM_REF
941 || TREE_CODE (offset
) != MULT_EXPR
942 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
943 || wi::umod_floor (index
, BITS_PER_UNIT
) != 0)
946 t1
= TREE_OPERAND (base
, 0);
947 c1
= widest_int::from (mem_ref_offset (base
), SIGNED
);
948 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
950 mult_op0
= TREE_OPERAND (offset
, 0);
951 c3
= wi::to_widest (TREE_OPERAND (offset
, 1));
953 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
955 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
957 t2
= TREE_OPERAND (mult_op0
, 0);
958 c2
= wi::to_widest (TREE_OPERAND (mult_op0
, 1));
963 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
965 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
967 t2
= TREE_OPERAND (mult_op0
, 0);
968 c2
= -wi::to_widest (TREE_OPERAND (mult_op0
, 1));
979 c4
= wi::lrshift (index
, LOG2_BITS_PER_UNIT
);
980 c5
= backtrace_base_for_ref (&t2
);
983 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, fold_convert (sizetype
, t2
),
984 wide_int_to_tree (sizetype
, c3
));
985 *pindex
= c1
+ c2
* c3
+ c4
+ c5
* c3
;
991 /* Given GS which contains a data reference, create a CAND_REF entry in
992 the candidate table and attempt to find a basis. */
995 slsr_process_ref (gimple gs
)
997 tree ref_expr
, base
, offset
, type
;
998 HOST_WIDE_INT bitsize
, bitpos
;
1000 int unsignedp
, volatilep
;
1003 if (gimple_vdef (gs
))
1004 ref_expr
= gimple_assign_lhs (gs
);
1006 ref_expr
= gimple_assign_rhs1 (gs
);
1008 if (!handled_component_p (ref_expr
)
1009 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
1010 || (TREE_CODE (ref_expr
) == COMPONENT_REF
1011 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
1014 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
1015 &unsignedp
, &volatilep
, false);
1016 widest_int index
= bitpos
;
1018 if (!restructure_reference (&base
, &offset
, &index
, &type
))
1021 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
1024 /* Add the candidate to the statement-candidate mapping. */
1025 add_cand_for_stmt (gs
, c
);
1028 /* Create a candidate entry for a statement GS, where GS multiplies
1029 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
1030 about the two SSA names into the new candidate. Return the new
1034 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1036 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1038 unsigned savings
= 0;
1040 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1042 /* Look at all interpretations of the base candidate, if necessary,
1043 to find information to propagate into this candidate. */
1044 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1047 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
1053 base
= base_cand
->base_expr
;
1054 index
= base_cand
->index
;
1056 ctype
= base_cand
->cand_type
;
1057 if (has_single_use (base_in
))
1058 savings
= (base_cand
->dead_savings
1059 + stmt_cost (base_cand
->cand_stmt
, speed
));
1061 else if (base_cand
->kind
== CAND_ADD
1062 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1064 /* Y = B + (i' * S), S constant
1066 ============================
1067 X = B + ((i' * S) * Z) */
1068 base
= base_cand
->base_expr
;
1069 index
= base_cand
->index
* wi::to_widest (base_cand
->stride
);
1071 ctype
= base_cand
->cand_type
;
1072 if (has_single_use (base_in
))
1073 savings
= (base_cand
->dead_savings
1074 + stmt_cost (base_cand
->cand_stmt
, speed
));
1077 if (base_cand
->next_interp
)
1078 base_cand
= lookup_cand (base_cand
->next_interp
);
1085 /* No interpretations had anything useful to propagate, so
1086 produce X = (Y + 0) * Z. */
1090 ctype
= TREE_TYPE (base_in
);
1093 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1098 /* Create a candidate entry for a statement GS, where GS multiplies
1099 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1100 information about BASE_IN into the new candidate. Return the new
1104 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1106 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1107 widest_int index
, temp
;
1108 unsigned savings
= 0;
1110 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1112 /* Look at all interpretations of the base candidate, if necessary,
1113 to find information to propagate into this candidate. */
1114 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1116 if (base_cand
->kind
== CAND_MULT
1117 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1119 /* Y = (B + i') * S, S constant
1121 ============================
1122 X = (B + i') * (S * c) */
1123 temp
= wi::to_widest (base_cand
->stride
) * wi::to_widest (stride_in
);
1124 if (wi::fits_to_tree_p (temp
, TREE_TYPE (stride_in
)))
1126 base
= base_cand
->base_expr
;
1127 index
= base_cand
->index
;
1128 stride
= wide_int_to_tree (TREE_TYPE (stride_in
), temp
);
1129 ctype
= base_cand
->cand_type
;
1130 if (has_single_use (base_in
))
1131 savings
= (base_cand
->dead_savings
1132 + stmt_cost (base_cand
->cand_stmt
, speed
));
1135 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
1139 ===========================
1141 base
= base_cand
->base_expr
;
1142 index
= base_cand
->index
;
1144 ctype
= base_cand
->cand_type
;
1145 if (has_single_use (base_in
))
1146 savings
= (base_cand
->dead_savings
1147 + stmt_cost (base_cand
->cand_stmt
, speed
));
1149 else if (base_cand
->kind
== CAND_ADD
1150 && base_cand
->index
== 1
1151 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1153 /* Y = B + (1 * S), S constant
1155 ===========================
1157 base
= base_cand
->base_expr
;
1158 index
= wi::to_widest (base_cand
->stride
);
1160 ctype
= base_cand
->cand_type
;
1161 if (has_single_use (base_in
))
1162 savings
= (base_cand
->dead_savings
1163 + stmt_cost (base_cand
->cand_stmt
, speed
));
1166 if (base_cand
->next_interp
)
1167 base_cand
= lookup_cand (base_cand
->next_interp
);
1174 /* No interpretations had anything useful to propagate, so
1175 produce X = (Y + 0) * c. */
1179 ctype
= TREE_TYPE (base_in
);
1182 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1187 /* Given GS which is a multiply of scalar integers, make an appropriate
1188 entry in the candidate table. If this is a multiply of two SSA names,
1189 create two CAND_MULT interpretations and attempt to find a basis for
1190 each of them. Otherwise, create a single CAND_MULT and attempt to
1194 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1198 /* If this is a multiply of an SSA name with itself, it is highly
1199 unlikely that we will get a strength reduction opportunity, so
1200 don't record it as a candidate. This simplifies the logic for
1201 finding a basis, so if this is removed that must be considered. */
1205 if (TREE_CODE (rhs2
) == SSA_NAME
)
1207 /* Record an interpretation of this statement in the candidate table
1208 assuming RHS1 is the base expression and RHS2 is the stride. */
1209 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1211 /* Add the first interpretation to the statement-candidate mapping. */
1212 add_cand_for_stmt (gs
, c
);
1214 /* Record another interpretation of this statement assuming RHS1
1215 is the stride and RHS2 is the base expression. */
1216 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1217 c
->next_interp
= c2
->cand_num
;
1221 /* Record an interpretation for the multiply-immediate. */
1222 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1224 /* Add the interpretation to the statement-candidate mapping. */
1225 add_cand_for_stmt (gs
, c
);
1229 /* Create a candidate entry for a statement GS, where GS adds two
1230 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1231 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1232 information about the two SSA names into the new candidate.
1233 Return the new candidate. */
1236 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1237 bool subtract_p
, bool speed
)
1239 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1241 unsigned savings
= 0;
1243 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1244 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1246 /* The most useful transformation is a multiply-immediate feeding
1247 an add or subtract. Look for that first. */
1248 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1250 if (addend_cand
->kind
== CAND_MULT
1251 && addend_cand
->index
== 0
1252 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1254 /* Z = (B + 0) * S, S constant
1256 ===========================
1257 X = Y + ((+/-1 * S) * B) */
1259 index
= wi::to_widest (addend_cand
->stride
);
1262 stride
= addend_cand
->base_expr
;
1263 ctype
= TREE_TYPE (base_in
);
1264 if (has_single_use (addend_in
))
1265 savings
= (addend_cand
->dead_savings
1266 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1269 if (addend_cand
->next_interp
)
1270 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1275 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1277 if (base_cand
->kind
== CAND_ADD
1278 && (base_cand
->index
== 0
1279 || operand_equal_p (base_cand
->stride
,
1280 integer_zero_node
, 0)))
1282 /* Y = B + (i' * S), i' * S = 0
1284 ============================
1285 X = B + (+/-1 * Z) */
1286 base
= base_cand
->base_expr
;
1287 index
= subtract_p
? -1 : 1;
1289 ctype
= base_cand
->cand_type
;
1290 if (has_single_use (base_in
))
1291 savings
= (base_cand
->dead_savings
1292 + stmt_cost (base_cand
->cand_stmt
, speed
));
1294 else if (subtract_p
)
1296 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1298 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1300 if (subtrahend_cand
->kind
== CAND_MULT
1301 && subtrahend_cand
->index
== 0
1302 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1304 /* Z = (B + 0) * S, S constant
1306 ===========================
1307 Value: X = Y + ((-1 * S) * B) */
1309 index
= wi::to_widest (subtrahend_cand
->stride
);
1311 stride
= subtrahend_cand
->base_expr
;
1312 ctype
= TREE_TYPE (base_in
);
1313 if (has_single_use (addend_in
))
1314 savings
= (subtrahend_cand
->dead_savings
1315 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1318 if (subtrahend_cand
->next_interp
)
1319 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1321 subtrahend_cand
= NULL
;
1325 if (base_cand
->next_interp
)
1326 base_cand
= lookup_cand (base_cand
->next_interp
);
1333 /* No interpretations had anything useful to propagate, so
1334 produce X = Y + (1 * Z). */
1336 index
= subtract_p
? -1 : 1;
1338 ctype
= TREE_TYPE (base_in
);
1341 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1346 /* Create a candidate entry for a statement GS, where GS adds SSA
1347 name BASE_IN to constant INDEX_IN. Propagate any known information
1348 about BASE_IN into the new candidate. Return the new candidate. */
1351 create_add_imm_cand (gimple gs
, tree base_in
, const widest_int
&index_in
,
1354 enum cand_kind kind
= CAND_ADD
;
1355 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1356 widest_int index
, multiple
;
1357 unsigned savings
= 0;
1359 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1361 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1363 signop sign
= TYPE_SIGN (TREE_TYPE (base_cand
->stride
));
1365 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1366 && wi::multiple_of_p (index_in
, wi::to_widest (base_cand
->stride
),
1369 /* Y = (B + i') * S, S constant, c = kS for some integer k
1371 ============================
1372 X = (B + (i'+ k)) * S
1374 Y = B + (i' * S), S constant, c = kS for some integer k
1376 ============================
1377 X = (B + (i'+ k)) * S */
1378 kind
= base_cand
->kind
;
1379 base
= base_cand
->base_expr
;
1380 index
= base_cand
->index
+ multiple
;
1381 stride
= base_cand
->stride
;
1382 ctype
= base_cand
->cand_type
;
1383 if (has_single_use (base_in
))
1384 savings
= (base_cand
->dead_savings
1385 + stmt_cost (base_cand
->cand_stmt
, speed
));
1388 if (base_cand
->next_interp
)
1389 base_cand
= lookup_cand (base_cand
->next_interp
);
1396 /* No interpretations had anything useful to propagate, so
1397 produce X = Y + (c * 1). */
1401 stride
= integer_one_node
;
1402 ctype
= TREE_TYPE (base_in
);
1405 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1410 /* Given GS which is an add or subtract of scalar integers or pointers,
1411 make at least one appropriate entry in the candidate table. */
1414 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1416 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1417 slsr_cand_t c
= NULL
, c2
;
1419 if (TREE_CODE (rhs2
) == SSA_NAME
)
1421 /* First record an interpretation assuming RHS1 is the base expression
1422 and RHS2 is the stride. But it doesn't make sense for the
1423 stride to be a pointer, so don't record a candidate in that case. */
1424 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1426 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1428 /* Add the first interpretation to the statement-candidate
1430 add_cand_for_stmt (gs
, c
);
1433 /* If the two RHS operands are identical, or this is a subtract,
1435 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1438 /* Otherwise, record another interpretation assuming RHS2 is the
1439 base expression and RHS1 is the stride, again provided that the
1440 stride is not a pointer. */
1441 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1443 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1445 c
->next_interp
= c2
->cand_num
;
1447 add_cand_for_stmt (gs
, c2
);
1452 /* Record an interpretation for the add-immediate. */
1453 widest_int index
= wi::to_widest (rhs2
);
1457 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1459 /* Add the interpretation to the statement-candidate mapping. */
1460 add_cand_for_stmt (gs
, c
);
1464 /* Given GS which is a negate of a scalar integer, make an appropriate
1465 entry in the candidate table. A negate is equivalent to a multiply
1469 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1471 /* Record a CAND_MULT interpretation for the multiply by -1. */
1472 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1474 /* Add the interpretation to the statement-candidate mapping. */
1475 add_cand_for_stmt (gs
, c
);
1478 /* Help function for legal_cast_p, operating on two trees. Checks
1479 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1480 for more details. */
1483 legal_cast_p_1 (tree lhs
, tree rhs
)
1485 tree lhs_type
, rhs_type
;
1486 unsigned lhs_size
, rhs_size
;
1487 bool lhs_wraps
, rhs_wraps
;
1489 lhs_type
= TREE_TYPE (lhs
);
1490 rhs_type
= TREE_TYPE (rhs
);
1491 lhs_size
= TYPE_PRECISION (lhs_type
);
1492 rhs_size
= TYPE_PRECISION (rhs_type
);
1493 lhs_wraps
= ANY_INTEGRAL_TYPE_P (lhs_type
) && TYPE_OVERFLOW_WRAPS (lhs_type
);
1494 rhs_wraps
= ANY_INTEGRAL_TYPE_P (rhs_type
) && TYPE_OVERFLOW_WRAPS (rhs_type
);
1496 if (lhs_size
< rhs_size
1497 || (rhs_wraps
&& !lhs_wraps
)
1498 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1504 /* Return TRUE if GS is a statement that defines an SSA name from
1505 a conversion and is legal for us to combine with an add and multiply
1506 in the candidate table. For example, suppose we have:
1512 Without the type-cast, we would create a CAND_MULT for D with base B,
1513 index i, and stride S. We want to record this candidate only if it
1514 is equivalent to apply the type cast following the multiply:
1520 We will record the type with the candidate for D. This allows us
1521 to use a similar previous candidate as a basis. If we have earlier seen
1527 we can replace D with
1529 D = D' + (i - i') * S;
1531 But if moving the type-cast would change semantics, we mustn't do this.
1533 This is legitimate for casts from a non-wrapping integral type to
1534 any integral type of the same or larger size. It is not legitimate
1535 to convert a wrapping type to a non-wrapping type, or to a wrapping
1536 type of a different size. I.e., with a wrapping type, we must
1537 assume that the addition B + i could wrap, in which case performing
1538 the multiply before or after one of the "illegal" type casts will
1539 have different semantics. */
1542 legal_cast_p (gimple gs
, tree rhs
)
1544 if (!is_gimple_assign (gs
)
1545 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1548 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1551 /* Given GS which is a cast to a scalar integer type, determine whether
1552 the cast is legal for strength reduction. If so, make at least one
1553 appropriate entry in the candidate table. */
1556 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1559 slsr_cand_t base_cand
, c
, c2
;
1560 unsigned savings
= 0;
1562 if (!legal_cast_p (gs
, rhs1
))
1565 lhs
= gimple_assign_lhs (gs
);
1566 base_cand
= base_cand_from_table (rhs1
);
1567 ctype
= TREE_TYPE (lhs
);
1569 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1573 /* Propagate all data from the base candidate except the type,
1574 which comes from the cast, and the base candidate's cast,
1575 which is no longer applicable. */
1576 if (has_single_use (rhs1
))
1577 savings
= (base_cand
->dead_savings
1578 + stmt_cost (base_cand
->cand_stmt
, speed
));
1580 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1581 base_cand
->base_expr
,
1582 base_cand
->index
, base_cand
->stride
,
1584 if (base_cand
->next_interp
)
1585 base_cand
= lookup_cand (base_cand
->next_interp
);
1592 /* If nothing is known about the RHS, create fresh CAND_ADD and
1593 CAND_MULT interpretations:
1598 The first of these is somewhat arbitrary, but the choice of
1599 1 for the stride simplifies the logic for propagating casts
1601 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
,
1602 0, integer_one_node
, ctype
, 0);
1603 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
,
1604 0, integer_one_node
, ctype
, 0);
1605 c
->next_interp
= c2
->cand_num
;
1608 /* Add the first (or only) interpretation to the statement-candidate
1610 add_cand_for_stmt (gs
, c
);
1613 /* Given GS which is a copy of a scalar integer type, make at least one
1614 appropriate entry in the candidate table.
1616 This interface is included for completeness, but is unnecessary
1617 if this pass immediately follows a pass that performs copy
1618 propagation, such as DOM. */
1621 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1623 slsr_cand_t base_cand
, c
, c2
;
1624 unsigned savings
= 0;
1626 base_cand
= base_cand_from_table (rhs1
);
1628 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1632 /* Propagate all data from the base candidate. */
1633 if (has_single_use (rhs1
))
1634 savings
= (base_cand
->dead_savings
1635 + stmt_cost (base_cand
->cand_stmt
, speed
));
1637 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1638 base_cand
->base_expr
,
1639 base_cand
->index
, base_cand
->stride
,
1640 base_cand
->cand_type
, savings
);
1641 if (base_cand
->next_interp
)
1642 base_cand
= lookup_cand (base_cand
->next_interp
);
1649 /* If nothing is known about the RHS, create fresh CAND_ADD and
1650 CAND_MULT interpretations:
1655 The first of these is somewhat arbitrary, but the choice of
1656 1 for the stride simplifies the logic for propagating casts
1658 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
,
1659 0, integer_one_node
, TREE_TYPE (rhs1
), 0);
1660 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
,
1661 0, integer_one_node
, TREE_TYPE (rhs1
), 0);
1662 c
->next_interp
= c2
->cand_num
;
1665 /* Add the first (or only) interpretation to the statement-candidate
1667 add_cand_for_stmt (gs
, c
);
1670 class find_candidates_dom_walker
: public dom_walker
1673 find_candidates_dom_walker (cdi_direction direction
)
1674 : dom_walker (direction
) {}
1675 virtual void before_dom_children (basic_block
);
1678 /* Find strength-reduction candidates in block BB. */
1681 find_candidates_dom_walker::before_dom_children (basic_block bb
)
1683 bool speed
= optimize_bb_for_speed_p (bb
);
1685 for (gphi_iterator gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
);
1687 slsr_process_phi (gsi
.phi (), speed
);
1689 for (gimple_stmt_iterator gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
);
1692 gimple gs
= gsi_stmt (gsi
);
1694 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1695 slsr_process_ref (gs
);
1697 else if (is_gimple_assign (gs
)
1698 && SCALAR_INT_MODE_P
1699 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1701 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1703 switch (gimple_assign_rhs_code (gs
))
1707 rhs1
= gimple_assign_rhs1 (gs
);
1708 rhs2
= gimple_assign_rhs2 (gs
);
1709 /* Should never happen, but currently some buggy situations
1710 in earlier phases put constants in rhs1. */
1711 if (TREE_CODE (rhs1
) != SSA_NAME
)
1715 /* Possible future opportunity: rhs1 of a ptr+ can be
1717 case POINTER_PLUS_EXPR
:
1719 rhs2
= gimple_assign_rhs2 (gs
);
1725 rhs1
= gimple_assign_rhs1 (gs
);
1726 if (TREE_CODE (rhs1
) != SSA_NAME
)
1734 switch (gimple_assign_rhs_code (gs
))
1737 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1741 case POINTER_PLUS_EXPR
:
1743 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1747 slsr_process_neg (gs
, rhs1
, speed
);
1751 slsr_process_cast (gs
, rhs1
, speed
);
1755 slsr_process_copy (gs
, rhs1
, speed
);
1765 /* Dump a candidate for debug. */
1768 dump_candidate (slsr_cand_t c
)
1770 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1771 gimple_bb (c
->cand_stmt
)->index
);
1772 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1776 fputs (" MULT : (", dump_file
);
1777 print_generic_expr (dump_file
, c
->base_expr
, 0);
1778 fputs (" + ", dump_file
);
1779 print_decs (c
->index
, dump_file
);
1780 fputs (") * ", dump_file
);
1781 print_generic_expr (dump_file
, c
->stride
, 0);
1782 fputs (" : ", dump_file
);
1785 fputs (" ADD : ", dump_file
);
1786 print_generic_expr (dump_file
, c
->base_expr
, 0);
1787 fputs (" + (", dump_file
);
1788 print_decs (c
->index
, dump_file
);
1789 fputs (" * ", dump_file
);
1790 print_generic_expr (dump_file
, c
->stride
, 0);
1791 fputs (") : ", dump_file
);
1794 fputs (" REF : ", dump_file
);
1795 print_generic_expr (dump_file
, c
->base_expr
, 0);
1796 fputs (" + (", dump_file
);
1797 print_generic_expr (dump_file
, c
->stride
, 0);
1798 fputs (") + ", dump_file
);
1799 print_decs (c
->index
, dump_file
);
1800 fputs (" : ", dump_file
);
1803 fputs (" PHI : ", dump_file
);
1804 print_generic_expr (dump_file
, c
->base_expr
, 0);
1805 fputs (" + (unknown * ", dump_file
);
1806 print_generic_expr (dump_file
, c
->stride
, 0);
1807 fputs (") : ", dump_file
);
1812 print_generic_expr (dump_file
, c
->cand_type
, 0);
1813 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1814 c
->basis
, c
->dependent
, c
->sibling
);
1815 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1816 c
->next_interp
, c
->dead_savings
);
1818 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1819 fputs ("\n", dump_file
);
1822 /* Dump the candidate vector for debug. */
1825 dump_cand_vec (void)
1830 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1832 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1836 /* Callback used to dump the candidate chains hash table. */
1839 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1841 const_cand_chain_t chain
= *slot
;
1844 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1845 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1847 for (p
= chain
->next
; p
; p
= p
->next
)
1848 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1850 fputs ("\n", dump_file
);
1854 /* Dump the candidate chains. */
1857 dump_cand_chains (void)
1859 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1860 base_cand_map
->traverse_noresize
<void *, ssa_base_cand_dump_callback
>
1862 fputs ("\n", dump_file
);
1865 /* Dump the increment vector for debug. */
1868 dump_incr_vec (void)
1870 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1874 fprintf (dump_file
, "\nIncrement vector:\n\n");
1876 for (i
= 0; i
< incr_vec_len
; i
++)
1878 fprintf (dump_file
, "%3d increment: ", i
);
1879 print_decs (incr_vec
[i
].incr
, dump_file
);
1880 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1881 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1882 fputs ("\n initializer: ", dump_file
);
1883 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1884 fputs ("\n\n", dump_file
);
1889 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1893 replace_ref (tree
*expr
, slsr_cand_t c
)
1895 tree add_expr
, mem_ref
, acc_type
= TREE_TYPE (*expr
);
1896 unsigned HOST_WIDE_INT misalign
;
1899 /* Ensure the memory reference carries the minimum alignment
1900 requirement for the data type. See PR58041. */
1901 get_object_alignment_1 (*expr
, &align
, &misalign
);
1903 align
= (misalign
& -misalign
);
1904 if (align
< TYPE_ALIGN (acc_type
))
1905 acc_type
= build_aligned_type (acc_type
, align
);
1907 add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1908 c
->base_expr
, c
->stride
);
1909 mem_ref
= fold_build2 (MEM_REF
, acc_type
, add_expr
,
1910 wide_int_to_tree (c
->cand_type
, c
->index
));
1912 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1913 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1914 TREE_OPERAND (mem_ref
, 0)
1915 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1916 /*simple_p=*/true, NULL
,
1917 /*before=*/true, GSI_SAME_STMT
);
1918 copy_ref_info (mem_ref
, *expr
);
1920 update_stmt (c
->cand_stmt
);
1923 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1924 dependent of candidate C with an equivalent strength-reduced data
1928 replace_refs (slsr_cand_t c
)
1930 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1932 fputs ("Replacing reference: ", dump_file
);
1933 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1936 if (gimple_vdef (c
->cand_stmt
))
1938 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1939 replace_ref (lhs
, c
);
1943 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1944 replace_ref (rhs
, c
);
1947 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1949 fputs ("With: ", dump_file
);
1950 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1951 fputs ("\n", dump_file
);
1955 replace_refs (lookup_cand (c
->sibling
));
1958 replace_refs (lookup_cand (c
->dependent
));
1961 /* Return TRUE if candidate C is dependent upon a PHI. */
1964 phi_dependent_cand_p (slsr_cand_t c
)
1966 /* A candidate is not necessarily dependent upon a PHI just because
1967 it has a phi definition for its base name. It may have a basis
1968 that relies upon the same phi definition, in which case the PHI
1969 is irrelevant to this candidate. */
1972 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1975 /* Calculate the increment required for candidate C relative to
1979 cand_increment (slsr_cand_t c
)
1983 /* If the candidate doesn't have a basis, just return its own
1984 index. This is useful in record_increments to help us find
1985 an existing initializer. Also, if the candidate's basis is
1986 hidden by a phi, then its own index will be the increment
1987 from the newly introduced phi basis. */
1988 if (!c
->basis
|| phi_dependent_cand_p (c
))
1991 basis
= lookup_cand (c
->basis
);
1992 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1993 return c
->index
- basis
->index
;
1996 /* Calculate the increment required for candidate C relative to
1997 its basis. If we aren't going to generate pointer arithmetic
1998 for this candidate, return the absolute value of that increment
2001 static inline widest_int
2002 cand_abs_increment (slsr_cand_t c
)
2004 widest_int increment
= cand_increment (c
);
2006 if (!address_arithmetic_p
&& wi::neg_p (increment
))
2007 increment
= -increment
;
2012 /* Return TRUE iff candidate C has already been replaced under
2013 another interpretation. */
2016 cand_already_replaced (slsr_cand_t c
)
2018 return (gimple_bb (c
->cand_stmt
) == 0);
2021 /* Common logic used by replace_unconditional_candidate and
2022 replace_conditional_candidate. */
2025 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, widest_int bump
)
2027 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
2028 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
2030 /* It is highly unlikely, but possible, that the resulting
2031 bump doesn't fit in a HWI. Abandon the replacement
2032 in this case. This does not affect siblings or dependents
2033 of C. Restriction to signed HWI is conservative for unsigned
2034 types but allows for safe negation without twisted logic. */
2035 if (wi::fits_shwi_p (bump
)
2036 && bump
.to_shwi () != HOST_WIDE_INT_MIN
2037 /* It is not useful to replace casts, copies, or adds of
2038 an SSA name and a constant. */
2039 && cand_code
!= MODIFY_EXPR
2040 && !CONVERT_EXPR_CODE_P (cand_code
)
2041 && cand_code
!= PLUS_EXPR
2042 && cand_code
!= POINTER_PLUS_EXPR
2043 && cand_code
!= MINUS_EXPR
)
2045 enum tree_code code
= PLUS_EXPR
;
2047 gimple stmt_to_print
= NULL
;
2049 /* If the basis name and the candidate's LHS have incompatible
2050 types, introduce a cast. */
2051 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
2052 basis_name
= introduce_cast_before_cand (c
, target_type
, basis_name
);
2053 if (wi::neg_p (bump
))
2059 bump_tree
= wide_int_to_tree (target_type
, bump
);
2061 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2063 fputs ("Replacing: ", dump_file
);
2064 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
2069 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
2070 gassign
*copy_stmt
= gimple_build_assign (lhs
, basis_name
);
2071 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2072 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
2073 gsi_replace (&gsi
, copy_stmt
, false);
2074 c
->cand_stmt
= copy_stmt
;
2075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2076 stmt_to_print
= copy_stmt
;
2081 if (cand_code
!= NEGATE_EXPR
) {
2082 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2083 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2085 if (cand_code
!= NEGATE_EXPR
2086 && ((operand_equal_p (rhs1
, basis_name
, 0)
2087 && operand_equal_p (rhs2
, bump_tree
, 0))
2088 || (operand_equal_p (rhs1
, bump_tree
, 0)
2089 && operand_equal_p (rhs2
, basis_name
, 0))))
2091 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2093 fputs ("(duplicate, not actually replacing)", dump_file
);
2094 stmt_to_print
= c
->cand_stmt
;
2099 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2100 gimple_assign_set_rhs_with_ops (&gsi
, code
,
2101 basis_name
, bump_tree
);
2102 update_stmt (gsi_stmt (gsi
));
2103 c
->cand_stmt
= gsi_stmt (gsi
);
2104 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2105 stmt_to_print
= gsi_stmt (gsi
);
2109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2111 fputs ("With: ", dump_file
);
2112 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
2113 fputs ("\n", dump_file
);
2118 /* Replace candidate C with an add or subtract. Note that we only
2119 operate on CAND_MULTs with known strides, so we will never generate
2120 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2121 X = Y + ((i - i') * S), as described in the module commentary. The
2122 folded value ((i - i') * S) is referred to here as the "bump." */
2125 replace_unconditional_candidate (slsr_cand_t c
)
2129 if (cand_already_replaced (c
))
2132 basis
= lookup_cand (c
->basis
);
2133 widest_int bump
= cand_increment (c
) * wi::to_widest (c
->stride
);
2135 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
);
2138 /* Return the index in the increment vector of the given INCREMENT,
2139 or -1 if not found. The latter can occur if more than
2140 MAX_INCR_VEC_LEN increments have been found. */
2143 incr_vec_index (const widest_int
&increment
)
2147 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
2150 if (i
< incr_vec_len
)
2156 /* Create a new statement along edge E to add BASIS_NAME to the product
2157 of INCREMENT and the stride of candidate C. Create and return a new
2158 SSA name from *VAR to be used as the LHS of the new statement.
2159 KNOWN_STRIDE is true iff C's stride is a constant. */
2162 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
2163 widest_int increment
, edge e
, location_t loc
,
2166 basic_block insert_bb
;
2167 gimple_stmt_iterator gsi
;
2168 tree lhs
, basis_type
;
2171 /* If the add candidate along this incoming edge has the same
2172 index as C's hidden basis, the hidden basis represents this
2177 basis_type
= TREE_TYPE (basis_name
);
2178 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2183 enum tree_code code
= PLUS_EXPR
;
2184 widest_int bump
= increment
* wi::to_widest (c
->stride
);
2185 if (wi::neg_p (bump
))
2191 bump_tree
= wide_int_to_tree (basis_type
, bump
);
2192 new_stmt
= gimple_build_assign (lhs
, code
, basis_name
, bump_tree
);
2197 bool negate_incr
= (!address_arithmetic_p
&& wi::neg_p (increment
));
2198 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2199 gcc_assert (i
>= 0);
2201 if (incr_vec
[i
].initializer
)
2203 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2204 new_stmt
= gimple_build_assign (lhs
, code
, basis_name
,
2205 incr_vec
[i
].initializer
);
2207 else if (increment
== 1)
2208 new_stmt
= gimple_build_assign (lhs
, PLUS_EXPR
, basis_name
, c
->stride
);
2209 else if (increment
== -1)
2210 new_stmt
= gimple_build_assign (lhs
, MINUS_EXPR
, basis_name
,
2216 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2217 gsi
= gsi_last_bb (insert_bb
);
2219 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2220 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2222 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2224 gimple_set_location (new_stmt
, loc
);
2226 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2228 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2229 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2235 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2236 is hidden by the phi node FROM_PHI, create a new phi node in the same
2237 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2238 with its phi arguments representing conditional adjustments to the
2239 hidden basis along conditional incoming paths. Those adjustments are
2240 made by creating add statements (and sometimes recursively creating
2241 phis) along those incoming paths. LOC is the location to attach to
2242 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2246 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2247 location_t loc
, bool known_stride
)
2253 slsr_cand_t basis
= lookup_cand (c
->basis
);
2254 int nargs
= gimple_phi_num_args (from_phi
);
2255 basic_block phi_bb
= gimple_bb (from_phi
);
2256 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2257 phi_args
.create (nargs
);
2259 /* Process each argument of the existing phi that represents
2260 conditionally-executed add candidates. */
2261 for (i
= 0; i
< nargs
; i
++)
2263 edge e
= (*phi_bb
->preds
)[i
];
2264 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2267 /* If the phi argument is the base name of the CAND_PHI, then
2268 this incoming arc should use the hidden basis. */
2269 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2270 if (basis
->index
== 0)
2271 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2274 widest_int incr
= -basis
->index
;
2275 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2276 e
, loc
, known_stride
);
2280 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2282 /* If there is another phi along this incoming edge, we must
2283 process it in the same fashion to ensure that all basis
2284 adjustments are made along its incoming edges. */
2285 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2286 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2290 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2291 widest_int diff
= arg_cand
->index
- basis
->index
;
2292 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2293 e
, loc
, known_stride
);
2297 /* Because of recursion, we need to save the arguments in a vector
2298 so we can create the PHI statement all at once. Otherwise the
2299 storage for the half-created PHI can be reclaimed. */
2300 phi_args
.safe_push (feeding_def
);
2303 /* Create the new phi basis. */
2304 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2305 phi
= create_phi_node (name
, phi_bb
);
2306 SSA_NAME_DEF_STMT (name
) = phi
;
2308 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2310 edge e
= (*phi_bb
->preds
)[i
];
2311 add_phi_arg (phi
, phi_arg
, e
, loc
);
2316 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2318 fputs ("Introducing new phi basis: ", dump_file
);
2319 print_gimple_stmt (dump_file
, phi
, 0, 0);
2325 /* Given a candidate C whose basis is hidden by at least one intervening
2326 phi, introduce a matching number of new phis to represent its basis
2327 adjusted by conditional increments along possible incoming paths. Then
2328 replace C as though it were an unconditional candidate, using the new
2332 replace_conditional_candidate (slsr_cand_t c
)
2334 tree basis_name
, name
;
2338 /* Look up the LHS SSA name from C's basis. This will be the
2339 RHS1 of the adds we will introduce to create new phi arguments. */
2340 basis
= lookup_cand (c
->basis
);
2341 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2343 /* Create a new phi statement which will represent C's true basis
2344 after the transformation is complete. */
2345 loc
= gimple_location (c
->cand_stmt
);
2346 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2347 basis_name
, loc
, KNOWN_STRIDE
);
2348 /* Replace C with an add of the new basis phi and a constant. */
2349 widest_int bump
= c
->index
* wi::to_widest (c
->stride
);
2351 replace_mult_candidate (c
, name
, bump
);
2354 /* Compute the expected costs of inserting basis adjustments for
2355 candidate C with phi-definition PHI. The cost of inserting
2356 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2357 which are themselves phi results, recursively calculate costs
2358 for those phis as well. */
2361 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2365 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2367 /* If we work our way back to a phi that isn't dominated by the hidden
2368 basis, this isn't a candidate for replacement. Indicate this by
2369 returning an unreasonably high cost. It's not easy to detect
2370 these situations when determining the basis, so we defer the
2371 decision until now. */
2372 basic_block phi_bb
= gimple_bb (phi
);
2373 slsr_cand_t basis
= lookup_cand (c
->basis
);
2374 basic_block basis_bb
= gimple_bb (basis
->cand_stmt
);
2376 if (phi_bb
== basis_bb
|| !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
2377 return COST_INFINITE
;
2379 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2381 tree arg
= gimple_phi_arg_def (phi
, i
);
2383 if (arg
!= phi_cand
->base_expr
)
2385 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2387 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2388 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2391 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2393 if (arg_cand
->index
!= c
->index
)
2394 cost
+= one_add_cost
;
2402 /* For candidate C, each sibling of candidate C, and each dependent of
2403 candidate C, determine whether the candidate is dependent upon a
2404 phi that hides its basis. If not, replace the candidate unconditionally.
2405 Otherwise, determine whether the cost of introducing compensation code
2406 for the candidate is offset by the gains from strength reduction. If
2407 so, replace the candidate and introduce the compensation code. */
2410 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2412 if (phi_dependent_cand_p (c
))
2414 if (c
->kind
== CAND_MULT
)
2416 /* A candidate dependent upon a phi will replace a multiply by
2417 a constant with an add, and will insert at most one add for
2418 each phi argument. Add these costs with the potential dead-code
2419 savings to determine profitability. */
2420 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2421 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2422 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2423 tree phi_result
= gimple_phi_result (phi
);
2424 int one_add_cost
= add_cost (speed
,
2425 TYPE_MODE (TREE_TYPE (phi_result
)));
2426 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2427 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2429 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2431 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2432 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2433 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2434 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2435 fprintf (dump_file
, " cost = %d\n", cost
);
2436 if (cost
<= COST_NEUTRAL
)
2437 fputs (" Replacing...\n", dump_file
);
2439 fputs (" Not replaced.\n", dump_file
);
2442 if (cost
<= COST_NEUTRAL
)
2443 replace_conditional_candidate (c
);
2447 replace_unconditional_candidate (c
);
2450 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2453 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2456 /* Count the number of candidates in the tree rooted at C that have
2457 not already been replaced under other interpretations. */
2460 count_candidates (slsr_cand_t c
)
2462 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2465 count
+= count_candidates (lookup_cand (c
->sibling
));
2468 count
+= count_candidates (lookup_cand (c
->dependent
));
2473 /* Increase the count of INCREMENT by one in the increment vector.
2474 INCREMENT is associated with candidate C. If INCREMENT is to be
2475 conditionally executed as part of a conditional candidate replacement,
2476 IS_PHI_ADJUST is true, otherwise false. If an initializer
2477 T_0 = stride * I is provided by a candidate that dominates all
2478 candidates with the same increment, also record T_0 for subsequent use. */
2481 record_increment (slsr_cand_t c
, widest_int increment
, bool is_phi_adjust
)
2486 /* Treat increments that differ only in sign as identical so as to
2487 share initializers, unless we are generating pointer arithmetic. */
2488 if (!address_arithmetic_p
&& wi::neg_p (increment
))
2489 increment
= -increment
;
2491 for (i
= 0; i
< incr_vec_len
; i
++)
2493 if (incr_vec
[i
].incr
== increment
)
2495 incr_vec
[i
].count
++;
2498 /* If we previously recorded an initializer that doesn't
2499 dominate this candidate, it's not going to be useful to
2501 if (incr_vec
[i
].initializer
2502 && !dominated_by_p (CDI_DOMINATORS
,
2503 gimple_bb (c
->cand_stmt
),
2504 incr_vec
[i
].init_bb
))
2506 incr_vec
[i
].initializer
= NULL_TREE
;
2507 incr_vec
[i
].init_bb
= NULL
;
2514 if (!found
&& incr_vec_len
< MAX_INCR_VEC_LEN
- 1)
2516 /* The first time we see an increment, create the entry for it.
2517 If this is the root candidate which doesn't have a basis, set
2518 the count to zero. We're only processing it so it can possibly
2519 provide an initializer for other candidates. */
2520 incr_vec
[incr_vec_len
].incr
= increment
;
2521 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2522 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2524 /* Optimistically record the first occurrence of this increment
2525 as providing an initializer (if it does); we will revise this
2526 opinion later if it doesn't dominate all other occurrences.
2527 Exception: increments of -1, 0, 1 never need initializers;
2528 and phi adjustments don't ever provide initializers. */
2529 if (c
->kind
== CAND_ADD
2531 && c
->index
== increment
2532 && (wi::gts_p (increment
, 1)
2533 || wi::lts_p (increment
, -1))
2534 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2535 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2537 tree t0
= NULL_TREE
;
2538 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2539 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2540 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2542 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2545 && SSA_NAME_DEF_STMT (t0
)
2546 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2548 incr_vec
[incr_vec_len
].initializer
= t0
;
2549 incr_vec
[incr_vec_len
++].init_bb
2550 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2554 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2555 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2560 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2561 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2566 /* Given phi statement PHI that hides a candidate from its BASIS, find
2567 the increments along each incoming arc (recursively handling additional
2568 phis that may be present) and record them. These increments are the
2569 difference in index between the index-adjusting statements and the
2570 index of the basis. */
2573 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2576 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2578 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2580 tree arg
= gimple_phi_arg_def (phi
, i
);
2582 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2584 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2586 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2587 record_phi_increments (basis
, arg_def
);
2590 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2591 widest_int diff
= arg_cand
->index
- basis
->index
;
2592 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2598 /* Determine how many times each unique increment occurs in the set
2599 of candidates rooted at C's parent, recording the data in the
2600 increment vector. For each unique increment I, if an initializer
2601 T_0 = stride * I is provided by a candidate that dominates all
2602 candidates with the same increment, also record T_0 for subsequent
2606 record_increments (slsr_cand_t c
)
2608 if (!cand_already_replaced (c
))
2610 if (!phi_dependent_cand_p (c
))
2611 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2614 /* A candidate with a basis hidden by a phi will have one
2615 increment for its relationship to the index represented by
2616 the phi, and potentially additional increments along each
2617 incoming edge. For the root of the dependency tree (which
2618 has no basis), process just the initial index in case it has
2619 an initializer that can be used by subsequent candidates. */
2620 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2623 record_phi_increments (lookup_cand (c
->basis
),
2624 lookup_cand (c
->def_phi
)->cand_stmt
);
2629 record_increments (lookup_cand (c
->sibling
));
2632 record_increments (lookup_cand (c
->dependent
));
2635 /* Add up and return the costs of introducing add statements that
2636 require the increment INCR on behalf of candidate C and phi
2637 statement PHI. Accumulate into *SAVINGS the potential savings
2638 from removing existing statements that feed PHI and have no other
2642 phi_incr_cost (slsr_cand_t c
, const widest_int
&incr
, gimple phi
, int *savings
)
2646 slsr_cand_t basis
= lookup_cand (c
->basis
);
2647 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2649 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2651 tree arg
= gimple_phi_arg_def (phi
, i
);
2653 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2655 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2657 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2659 int feeding_savings
= 0;
2660 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2661 if (has_single_use (gimple_phi_result (arg_def
)))
2662 *savings
+= feeding_savings
;
2666 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2667 widest_int diff
= arg_cand
->index
- basis
->index
;
2671 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2672 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2673 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2674 if (has_single_use (lhs
))
2675 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2684 /* Return the first candidate in the tree rooted at C that has not
2685 already been replaced, favoring siblings over dependents. */
2688 unreplaced_cand_in_tree (slsr_cand_t c
)
2690 if (!cand_already_replaced (c
))
2695 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2702 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2710 /* Return TRUE if the candidates in the tree rooted at C should be
2711 optimized for speed, else FALSE. We estimate this based on the block
2712 containing the most dominant candidate in the tree that has not yet
2716 optimize_cands_for_speed_p (slsr_cand_t c
)
2718 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2720 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2723 /* Add COST_IN to the lowest cost of any dependent path starting at
2724 candidate C or any of its siblings, counting only candidates along
2725 such paths with increment INCR. Assume that replacing a candidate
2726 reduces cost by REPL_SAVINGS. Also account for savings from any
2727 statements that would go dead. If COUNT_PHIS is true, include
2728 costs of introducing feeding statements for conditional candidates. */
2731 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2732 const widest_int
&incr
, bool count_phis
)
2734 int local_cost
, sib_cost
, savings
= 0;
2735 widest_int cand_incr
= cand_abs_increment (c
);
2737 if (cand_already_replaced (c
))
2738 local_cost
= cost_in
;
2739 else if (incr
== cand_incr
)
2740 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2742 local_cost
= cost_in
- c
->dead_savings
;
2745 && phi_dependent_cand_p (c
)
2746 && !cand_already_replaced (c
))
2748 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2749 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2751 if (has_single_use (gimple_phi_result (phi
)))
2752 local_cost
-= savings
;
2756 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2757 lookup_cand (c
->dependent
), incr
,
2762 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2763 lookup_cand (c
->sibling
), incr
,
2765 local_cost
= MIN (local_cost
, sib_cost
);
2771 /* Compute the total savings that would accrue from all replacements
2772 in the candidate tree rooted at C, counting only candidates with
2773 increment INCR. Assume that replacing a candidate reduces cost
2774 by REPL_SAVINGS. Also account for savings from statements that
2778 total_savings (int repl_savings
, slsr_cand_t c
, const widest_int
&incr
,
2782 widest_int cand_incr
= cand_abs_increment (c
);
2784 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2785 savings
+= repl_savings
+ c
->dead_savings
;
2788 && phi_dependent_cand_p (c
)
2789 && !cand_already_replaced (c
))
2791 int phi_savings
= 0;
2792 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2793 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2795 if (has_single_use (gimple_phi_result (phi
)))
2796 savings
+= phi_savings
;
2800 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2804 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2810 /* Use target-specific costs to determine and record which increments
2811 in the current candidate tree are profitable to replace, assuming
2812 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2815 One slight limitation here is that we don't account for the possible
2816 introduction of casts in some cases. See replace_one_candidate for
2817 the cases where these are introduced. This should probably be cleaned
2821 analyze_increments (slsr_cand_t first_dep
, machine_mode mode
, bool speed
)
2825 for (i
= 0; i
< incr_vec_len
; i
++)
2827 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2829 /* If somehow this increment is bigger than a HWI, we won't
2830 be optimizing candidates that use it. And if the increment
2831 has a count of zero, nothing will be done with it. */
2832 if (!wi::fits_shwi_p (incr_vec
[i
].incr
) || !incr_vec
[i
].count
)
2833 incr_vec
[i
].cost
= COST_INFINITE
;
2835 /* Increments of 0, 1, and -1 are always profitable to replace,
2836 because they always replace a multiply or add with an add or
2837 copy, and may cause one or more existing instructions to go
2838 dead. Exception: -1 can't be assumed to be profitable for
2839 pointer addition. */
2843 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2844 != POINTER_PLUS_EXPR
)))
2845 incr_vec
[i
].cost
= COST_NEUTRAL
;
2847 /* FORNOW: If we need to add an initializer, give up if a cast from
2848 the candidate's type to its stride's type can lose precision.
2849 This could eventually be handled better by expressly retaining the
2850 result of a cast to a wider type in the stride. Example:
2855 _4 = x + _3; ADD: x + (10 * _1) : int
2857 _6 = x + _3; ADD: x + (15 * _1) : int
2859 Right now replacing _6 would cause insertion of an initializer
2860 of the form "short int T = _1 * 5;" followed by a cast to
2861 int, which could overflow incorrectly. Had we recorded _2 or
2862 (int)_1 as the stride, this wouldn't happen. However, doing
2863 this breaks other opportunities, so this will require some
2865 else if (!incr_vec
[i
].initializer
2866 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2867 && !legal_cast_p_1 (first_dep
->stride
,
2868 gimple_assign_lhs (first_dep
->cand_stmt
)))
2870 incr_vec
[i
].cost
= COST_INFINITE
;
2872 /* If we need to add an initializer, make sure we don't introduce
2873 a multiply by a pointer type, which can happen in certain cast
2874 scenarios. FIXME: When cleaning up these cast issues, we can
2875 afford to introduce the multiply provided we cast out to an
2876 unsigned int of appropriate size. */
2877 else if (!incr_vec
[i
].initializer
2878 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2879 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2881 incr_vec
[i
].cost
= COST_INFINITE
;
2883 /* For any other increment, if this is a multiply candidate, we
2884 must introduce a temporary T and initialize it with
2885 T_0 = stride * increment. When optimizing for speed, walk the
2886 candidate tree to calculate the best cost reduction along any
2887 path; if it offsets the fixed cost of inserting the initializer,
2888 replacing the increment is profitable. When optimizing for
2889 size, instead calculate the total cost reduction from replacing
2890 all candidates with this increment. */
2891 else if (first_dep
->kind
== CAND_MULT
)
2893 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2894 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2896 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2897 incr_vec
[i
].incr
, COUNT_PHIS
);
2899 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2902 incr_vec
[i
].cost
= cost
;
2905 /* If this is an add candidate, the initializer may already
2906 exist, so only calculate the cost of the initializer if it
2907 doesn't. We are replacing one add with another here, so the
2908 known replacement savings is zero. We will account for removal
2909 of dead instructions in lowest_cost_path or total_savings. */
2913 if (!incr_vec
[i
].initializer
)
2914 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2917 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2920 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2923 incr_vec
[i
].cost
= cost
;
2928 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2929 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2930 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2931 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2932 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2935 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2936 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2952 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2954 /* If both candidates are in the same block, the earlier
2956 if (bb1
== ncd
&& bb2
== ncd
)
2958 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2964 /* Otherwise, if one of them produced a candidate in the
2965 dominator, that one wins. */
2966 else if (bb1
== ncd
)
2969 else if (bb2
== ncd
)
2972 /* If neither matches the dominator, neither wins. */
2979 /* Consider all candidates that feed PHI. Find the nearest common
2980 dominator of those candidates requiring the given increment INCR.
2981 Further find and return the nearest common dominator of this result
2982 with block NCD. If the returned block contains one or more of the
2983 candidates, return the earliest candidate in the block in *WHERE. */
2986 ncd_with_phi (slsr_cand_t c
, const widest_int
&incr
, gphi
*phi
,
2987 basic_block ncd
, slsr_cand_t
*where
)
2990 slsr_cand_t basis
= lookup_cand (c
->basis
);
2991 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2993 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2995 tree arg
= gimple_phi_arg_def (phi
, i
);
2997 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2999 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3001 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3002 ncd
= ncd_with_phi (c
, incr
, as_a
<gphi
*> (arg_def
), ncd
,
3006 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3007 widest_int diff
= arg_cand
->index
- basis
->index
;
3008 basic_block pred
= gimple_phi_arg_edge (phi
, i
)->src
;
3010 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
3011 ncd
= ncd_for_two_cands (ncd
, pred
, *where
, NULL
, where
);
3019 /* Consider the candidate C together with any candidates that feed
3020 C's phi dependence (if any). Find and return the nearest common
3021 dominator of those candidates requiring the given increment INCR.
3022 If the returned block contains one or more of the candidates,
3023 return the earliest candidate in the block in *WHERE. */
3026 ncd_of_cand_and_phis (slsr_cand_t c
, const widest_int
&incr
, slsr_cand_t
*where
)
3028 basic_block ncd
= NULL
;
3030 if (cand_abs_increment (c
) == incr
)
3032 ncd
= gimple_bb (c
->cand_stmt
);
3036 if (phi_dependent_cand_p (c
))
3037 ncd
= ncd_with_phi (c
, incr
,
3038 as_a
<gphi
*> (lookup_cand (c
->def_phi
)->cand_stmt
),
3044 /* Consider all candidates in the tree rooted at C for which INCR
3045 represents the required increment of C relative to its basis.
3046 Find and return the basic block that most nearly dominates all
3047 such candidates. If the returned block contains one or more of
3048 the candidates, return the earliest candidate in the block in
3052 nearest_common_dominator_for_cands (slsr_cand_t c
, const widest_int
&incr
,
3055 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
3056 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
3058 /* First find the NCD of all siblings and dependents. */
3060 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
3063 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
3065 if (!sib_ncd
&& !dep_ncd
)
3070 else if (sib_ncd
&& !dep_ncd
)
3072 new_where
= sib_where
;
3075 else if (dep_ncd
&& !sib_ncd
)
3077 new_where
= dep_where
;
3081 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
3082 dep_where
, &new_where
);
3084 /* If the candidate's increment doesn't match the one we're interested
3085 in (and nor do any increments for feeding defs of a phi-dependence),
3086 then the result depends only on siblings and dependents. */
3087 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
3089 if (!this_ncd
|| cand_already_replaced (c
))
3095 /* Otherwise, compare this candidate with the result from all siblings
3097 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
3102 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
3105 profitable_increment_p (unsigned index
)
3107 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
3110 /* For each profitable increment in the increment vector not equal to
3111 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3112 dominator of all statements in the candidate chain rooted at C
3113 that require that increment, and insert an initializer
3114 T_0 = stride * increment at that location. Record T_0 with the
3115 increment record. */
3118 insert_initializers (slsr_cand_t c
)
3122 for (i
= 0; i
< incr_vec_len
; i
++)
3125 slsr_cand_t where
= NULL
;
3127 tree stride_type
, new_name
, incr_tree
;
3128 widest_int incr
= incr_vec
[i
].incr
;
3130 if (!profitable_increment_p (i
)
3133 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
3137 /* We may have already identified an existing initializer that
3139 if (incr_vec
[i
].initializer
)
3141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3143 fputs ("Using existing initializer: ", dump_file
);
3144 print_gimple_stmt (dump_file
,
3145 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
3151 /* Find the block that most closely dominates all candidates
3152 with this increment. If there is at least one candidate in
3153 that block, the earliest one will be returned in WHERE. */
3154 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
3156 /* Create a new SSA name to hold the initializer's value. */
3157 stride_type
= TREE_TYPE (c
->stride
);
3158 new_name
= make_temp_ssa_name (stride_type
, NULL
, "slsr");
3159 incr_vec
[i
].initializer
= new_name
;
3161 /* Create the initializer and insert it in the latest possible
3162 dominating position. */
3163 incr_tree
= wide_int_to_tree (stride_type
, incr
);
3164 init_stmt
= gimple_build_assign (new_name
, MULT_EXPR
,
3165 c
->stride
, incr_tree
);
3168 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
3169 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3170 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
3174 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
3175 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
3177 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
3178 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3180 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
3182 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
3185 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3187 fputs ("Inserting initializer: ", dump_file
);
3188 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3193 /* Return TRUE iff all required increments for candidates feeding PHI
3194 are profitable to replace on behalf of candidate C. */
3197 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3200 slsr_cand_t basis
= lookup_cand (c
->basis
);
3201 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3203 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3205 tree arg
= gimple_phi_arg_def (phi
, i
);
3207 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3209 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3211 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3213 if (!all_phi_incrs_profitable (c
, arg_def
))
3219 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3220 widest_int increment
= arg_cand
->index
- basis
->index
;
3222 if (!address_arithmetic_p
&& wi::neg_p (increment
))
3223 increment
= -increment
;
3225 j
= incr_vec_index (increment
);
3227 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3229 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3231 print_gimple_stmt (dump_file
, phi
, 0, 0);
3232 fputs (" increment: ", dump_file
);
3233 print_decs (increment
, dump_file
);
3236 "\n Not replaced; incr_vec overflow.\n");
3238 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3239 if (profitable_increment_p (j
))
3240 fputs (" Replacing...\n", dump_file
);
3242 fputs (" Not replaced.\n", dump_file
);
3246 if (j
< 0 || !profitable_increment_p (j
))
3255 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3256 type TO_TYPE, and insert it in front of the statement represented
3257 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3258 the new SSA name. */
3261 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
, tree from_expr
)
3265 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3267 cast_lhs
= make_temp_ssa_name (to_type
, NULL
, "slsr");
3268 cast_stmt
= gimple_build_assign (cast_lhs
, NOP_EXPR
, from_expr
);
3269 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3270 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3272 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3274 fputs (" Inserting: ", dump_file
);
3275 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3281 /* Replace the RHS of the statement represented by candidate C with
3282 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3283 leave C unchanged or just interchange its operands. The original
3284 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3285 If the replacement was made and we are doing a details dump,
3286 return the revised statement, else NULL. */
3289 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3290 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3293 if (new_code
!= old_code
3294 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3295 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3296 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3297 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3299 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3300 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3301 update_stmt (gsi_stmt (gsi
));
3302 c
->cand_stmt
= gsi_stmt (gsi
);
3304 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3305 return gsi_stmt (gsi
);
3308 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3309 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3314 /* Strength-reduce the statement represented by candidate C by replacing
3315 it with an equivalent addition or subtraction. I is the index into
3316 the increment vector identifying C's increment. NEW_VAR is used to
3317 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3318 is the rhs1 to use in creating the add/subtract. */
3321 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree basis_name
)
3323 gimple stmt_to_print
= NULL
;
3324 tree orig_rhs1
, orig_rhs2
;
3326 enum tree_code orig_code
, repl_code
;
3327 widest_int cand_incr
;
3329 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3330 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3331 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3332 cand_incr
= cand_increment (c
);
3334 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 fputs ("Replacing: ", dump_file
);
3337 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3338 stmt_to_print
= c
->cand_stmt
;
3341 if (address_arithmetic_p
)
3342 repl_code
= POINTER_PLUS_EXPR
;
3344 repl_code
= PLUS_EXPR
;
3346 /* If the increment has an initializer T_0, replace the candidate
3347 statement with an add of the basis name and the initializer. */
3348 if (incr_vec
[i
].initializer
)
3350 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3351 tree orig_type
= TREE_TYPE (orig_rhs2
);
3353 if (types_compatible_p (orig_type
, init_type
))
3354 rhs2
= incr_vec
[i
].initializer
;
3356 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3357 incr_vec
[i
].initializer
);
3359 if (incr_vec
[i
].incr
!= cand_incr
)
3361 gcc_assert (repl_code
== PLUS_EXPR
);
3362 repl_code
= MINUS_EXPR
;
3365 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3366 orig_code
, orig_rhs1
, orig_rhs2
,
3370 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3371 with a subtract of the stride from the basis name, a copy
3372 from the basis name, or an add of the stride to the basis
3373 name, respectively. It may be necessary to introduce a
3374 cast (or reuse an existing cast). */
3375 else if (cand_incr
== 1)
3377 tree stride_type
= TREE_TYPE (c
->stride
);
3378 tree orig_type
= TREE_TYPE (orig_rhs2
);
3380 if (types_compatible_p (orig_type
, stride_type
))
3383 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3385 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3386 orig_code
, orig_rhs1
, orig_rhs2
,
3390 else if (cand_incr
== -1)
3392 tree stride_type
= TREE_TYPE (c
->stride
);
3393 tree orig_type
= TREE_TYPE (orig_rhs2
);
3394 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3396 if (types_compatible_p (orig_type
, stride_type
))
3399 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3401 if (orig_code
!= MINUS_EXPR
3402 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3403 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3405 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3406 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3407 update_stmt (gsi_stmt (gsi
));
3408 c
->cand_stmt
= gsi_stmt (gsi
);
3410 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3411 stmt_to_print
= gsi_stmt (gsi
);
3413 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3414 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3417 else if (cand_incr
== 0)
3419 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3420 tree lhs_type
= TREE_TYPE (lhs
);
3421 tree basis_type
= TREE_TYPE (basis_name
);
3423 if (types_compatible_p (lhs_type
, basis_type
))
3425 gassign
*copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3426 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3427 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3428 gsi_replace (&gsi
, copy_stmt
, false);
3429 c
->cand_stmt
= copy_stmt
;
3431 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3432 stmt_to_print
= copy_stmt
;
3436 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3437 gassign
*cast_stmt
= gimple_build_assign (lhs
, NOP_EXPR
, basis_name
);
3438 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3439 gsi_replace (&gsi
, cast_stmt
, false);
3440 c
->cand_stmt
= cast_stmt
;
3442 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3443 stmt_to_print
= cast_stmt
;
3449 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3451 fputs ("With: ", dump_file
);
3452 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3453 fputs ("\n", dump_file
);
3457 /* For each candidate in the tree rooted at C, replace it with
3458 an increment if such has been shown to be profitable. */
3461 replace_profitable_candidates (slsr_cand_t c
)
3463 if (!cand_already_replaced (c
))
3465 widest_int increment
= cand_abs_increment (c
);
3466 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3469 i
= incr_vec_index (increment
);
3471 /* Only process profitable increments. Nothing useful can be done
3472 to a cast or copy. */
3474 && profitable_increment_p (i
)
3475 && orig_code
!= MODIFY_EXPR
3476 && !CONVERT_EXPR_CODE_P (orig_code
))
3478 if (phi_dependent_cand_p (c
))
3480 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3482 if (all_phi_incrs_profitable (c
, phi
))
3484 /* Look up the LHS SSA name from C's basis. This will be
3485 the RHS1 of the adds we will introduce to create new
3487 slsr_cand_t basis
= lookup_cand (c
->basis
);
3488 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3490 /* Create a new phi statement that will represent C's true
3491 basis after the transformation is complete. */
3492 location_t loc
= gimple_location (c
->cand_stmt
);
3493 tree name
= create_phi_basis (c
, phi
, basis_name
,
3494 loc
, UNKNOWN_STRIDE
);
3496 /* Replace C with an add of the new basis phi and the
3498 replace_one_candidate (c
, i
, name
);
3503 slsr_cand_t basis
= lookup_cand (c
->basis
);
3504 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3505 replace_one_candidate (c
, i
, basis_name
);
3511 replace_profitable_candidates (lookup_cand (c
->sibling
));
3514 replace_profitable_candidates (lookup_cand (c
->dependent
));
3517 /* Analyze costs of related candidates in the candidate vector,
3518 and make beneficial replacements. */
3521 analyze_candidates_and_replace (void)
3526 /* Each candidate that has a null basis and a non-null
3527 dependent is the root of a tree of related statements.
3528 Analyze each tree to determine a subset of those
3529 statements that can be replaced with maximum benefit. */
3530 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3532 slsr_cand_t first_dep
;
3534 if (c
->basis
!= 0 || c
->dependent
== 0)
3537 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3538 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3541 first_dep
= lookup_cand (c
->dependent
);
3543 /* If this is a chain of CAND_REFs, unconditionally replace
3544 each of them with a strength-reduced data reference. */
3545 if (c
->kind
== CAND_REF
)
3548 /* If the common stride of all related candidates is a known
3549 constant, each candidate without a phi-dependence can be
3550 profitably replaced. Each replaces a multiply by a single
3551 add, with the possibility that a feeding add also goes dead.
3552 A candidate with a phi-dependence is replaced only if the
3553 compensation code it requires is offset by the strength
3554 reduction savings. */
3555 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3556 replace_uncond_cands_and_profitable_phis (first_dep
);
3558 /* When the stride is an SSA name, it may still be profitable
3559 to replace some or all of the dependent candidates, depending
3560 on whether the introduced increments can be reused, or are
3561 less expensive to calculate than the replaced statements. */
3567 /* Determine whether we'll be generating pointer arithmetic
3568 when replacing candidates. */
3569 address_arithmetic_p
= (c
->kind
== CAND_ADD
3570 && POINTER_TYPE_P (c
->cand_type
));
3572 /* If all candidates have already been replaced under other
3573 interpretations, nothing remains to be done. */
3574 if (!count_candidates (c
))
3577 /* Construct an array of increments for this candidate chain. */
3578 incr_vec
= XNEWVEC (incr_info
, MAX_INCR_VEC_LEN
);
3580 record_increments (c
);
3582 /* Determine which increments are profitable to replace. */
3583 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3584 speed
= optimize_cands_for_speed_p (c
);
3585 analyze_increments (first_dep
, mode
, speed
);
3587 /* Insert initializers of the form T_0 = stride * increment
3588 for use in profitable replacements. */
3589 insert_initializers (first_dep
);
3592 /* Perform the replacements. */
3593 replace_profitable_candidates (first_dep
);
3601 const pass_data pass_data_strength_reduction
=
3603 GIMPLE_PASS
, /* type */
3605 OPTGROUP_NONE
, /* optinfo_flags */
3606 TV_GIMPLE_SLSR
, /* tv_id */
3607 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3608 0, /* properties_provided */
3609 0, /* properties_destroyed */
3610 0, /* todo_flags_start */
3611 0, /* todo_flags_finish */
3614 class pass_strength_reduction
: public gimple_opt_pass
3617 pass_strength_reduction (gcc::context
*ctxt
)
3618 : gimple_opt_pass (pass_data_strength_reduction
, ctxt
)
3621 /* opt_pass methods: */
3622 virtual bool gate (function
*) { return flag_tree_slsr
; }
3623 virtual unsigned int execute (function
*);
3625 }; // class pass_strength_reduction
3628 pass_strength_reduction::execute (function
*fun
)
3630 /* Create the obstack where candidates will reside. */
3631 gcc_obstack_init (&cand_obstack
);
3633 /* Allocate the candidate vector. */
3634 cand_vec
.create (128);
3636 /* Allocate the mapping from statements to candidate indices. */
3637 stmt_cand_map
= new hash_map
<gimple
, slsr_cand_t
>;
3639 /* Create the obstack where candidate chains will reside. */
3640 gcc_obstack_init (&chain_obstack
);
3642 /* Allocate the mapping from base expressions to candidate chains. */
3643 base_cand_map
= new hash_table
<cand_chain_hasher
> (500);
3645 /* Allocate the mapping from bases to alternative bases. */
3646 alt_base_map
= new hash_map
<tree
, tree
>;
3648 /* Initialize the loop optimizer. We need to detect flow across
3649 back edges, and this gives us dominator information as well. */
3650 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3652 /* Walk the CFG in predominator order looking for strength reduction
3654 find_candidates_dom_walker (CDI_DOMINATORS
)
3655 .walk (fun
->cfg
->x_entry_block_ptr
);
3657 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3660 dump_cand_chains ();
3663 delete alt_base_map
;
3664 free_affine_expand_cache (&name_expansions
);
3666 /* Analyze costs and make appropriate replacements. */
3667 analyze_candidates_and_replace ();
3669 loop_optimizer_finalize ();
3670 delete base_cand_map
;
3671 base_cand_map
= NULL
;
3672 obstack_free (&chain_obstack
, NULL
);
3673 delete stmt_cand_map
;
3674 cand_vec
.release ();
3675 obstack_free (&cand_obstack
, NULL
);
3683 make_pass_strength_reduction (gcc::context
*ctxt
)
3685 return new pass_strength_reduction (ctxt
);