1 /* Straight-line strength reduction.
2 Copyright (C) 2012-2013 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"
40 #include "pointer-set.h"
41 #include "hash-table.h"
42 #include "basic-block.h"
43 #include "tree-ssa-alias.h"
44 #include "internal-fn.h"
45 #include "gimple-expr.h"
48 #include "gimple-iterator.h"
49 #include "gimplify-me.h"
50 #include "stor-layout.h"
52 #include "tree-pass.h"
54 #include "gimple-pretty-print.h"
55 #include "gimple-ssa.h"
57 #include "tree-phinodes.h"
58 #include "ssa-iterators.h"
59 #include "stringpool.h"
60 #include "tree-ssanames.h"
64 #include "tree-ssa-address.h"
65 #include "tree-affine.h"
67 /* Information about a strength reduction candidate. Each statement
68 in the candidate table represents an expression of one of the
69 following forms (the special case of CAND_REF will be described
72 (CAND_MULT) S1: X = (B + i) * S
73 (CAND_ADD) S1: X = B + (i * S)
75 Here X and B are SSA names, i is an integer constant, and S is
76 either an SSA name or a constant. We call B the "base," i the
77 "index", and S the "stride."
79 Any statement S0 that dominates S1 and is of the form:
81 (CAND_MULT) S0: Y = (B + i') * S
82 (CAND_ADD) S0: Y = B + (i' * S)
84 is called a "basis" for S1. In both cases, S1 may be replaced by
86 S1': X = Y + (i - i') * S,
88 where (i - i') * S is folded to the extent possible.
90 All gimple statements are visited in dominator order, and each
91 statement that may contribute to one of the forms of S1 above is
92 given at least one entry in the candidate table. Such statements
93 include addition, pointer addition, subtraction, multiplication,
94 negation, copies, and nontrivial type casts. If a statement may
95 represent more than one expression of the forms of S1 above,
96 multiple "interpretations" are stored in the table and chained
99 * An add of two SSA names may treat either operand as the base.
100 * A multiply of two SSA names, likewise.
101 * A copy or cast may be thought of as either a CAND_MULT with
102 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
104 Candidate records are allocated from an obstack. They are addressed
105 both from a hash table keyed on S1, and from a vector of candidate
106 pointers arranged in predominator order.
110 Currently we don't recognize:
115 as a strength reduction opportunity, even though this S1 would
116 also be replaceable by the S1' above. This can be added if it
117 comes up in practice.
119 Strength reduction in addressing
120 --------------------------------
121 There is another kind of candidate known as CAND_REF. A CAND_REF
122 describes a statement containing a memory reference having
123 complex addressing that might benefit from strength reduction.
124 Specifically, we are interested in references for which
125 get_inner_reference returns a base address, offset, and bitpos as
128 base: MEM_REF (T1, C1)
129 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
130 bitpos: C4 * BITS_PER_UNIT
132 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
133 arbitrary integer constants. Note that C2 may be zero, in which
134 case the offset will be MULT_EXPR (T2, C3).
136 When this pattern is recognized, the original memory reference
137 can be replaced with:
139 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
142 which distributes the multiply to allow constant folding. When
143 two or more addressing expressions can be represented by MEM_REFs
144 of this form, differing only in the constants C1, C2, and C4,
145 making this substitution produces more efficient addressing during
146 the RTL phases. When there are not at least two expressions with
147 the same values of T1, T2, and C3, there is nothing to be gained
150 Strength reduction of CAND_REFs uses the same infrastructure as
151 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
152 field, MULT_EXPR (T2, C3) in the stride (S) field, and
153 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
154 is thus another CAND_REF with the same B and S values. When at
155 least two CAND_REFs are chained together using the basis relation,
156 each of them is replaced as above, resulting in improved code
157 generation for addressing.
159 Conditional candidates
160 ======================
162 Conditional candidates are best illustrated with an example.
163 Consider the code sequence:
166 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
168 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
169 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
170 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
171 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
173 Here strength reduction is complicated by the uncertain value of x_2.
174 A legitimate transformation is:
183 (4) [x_2 = PHI <x_0, x_1>;]
184 (4a) t_2 = PHI <a_0, t_1>;
188 where the bracketed instructions may go dead.
190 To recognize this opportunity, we have to observe that statement (6)
191 has a "hidden basis" (2). The hidden basis is unlike a normal basis
192 in that the statement and the hidden basis have different base SSA
193 names (x_2 and x_0, respectively). The relationship is established
194 when a statement's base name (x_2) is defined by a phi statement (4),
195 each argument of which (x_0, x_1) has an identical "derived base name."
196 If the argument is defined by a candidate (as x_1 is by (3)) that is a
197 CAND_ADD having a stride of 1, the derived base name of the argument is
198 the base name of the candidate (x_0). Otherwise, the argument itself
199 is its derived base name (as is the case with argument x_0).
201 The hidden basis for statement (6) is the nearest dominating candidate
202 whose base name is the derived base name (x_0) of the feeding phi (4),
203 and whose stride is identical to that of the statement. We can then
204 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
205 allowing the final replacement of (6) by the strength-reduced (6r).
207 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
208 A CAND_PHI is not a candidate for replacement, but is maintained in the
209 candidate table to ease discovery of hidden bases. Any phi statement
210 whose arguments share a common derived base name is entered into the
211 table with the derived base name, an (arbitrary) index of zero, and a
212 stride of 1. A statement with a hidden basis can then be detected by
213 simply looking up its feeding phi definition in the candidate table,
214 extracting the derived base name, and searching for a basis in the
215 usual manner after substituting the derived base name.
217 Note that the transformation is only valid when the original phi and
218 the statements that define the phi's arguments are all at the same
219 position in the loop hierarchy. */
222 /* Index into the candidate vector, offset by 1. VECs are zero-based,
223 while cand_idx's are one-based, with zero indicating null. */
224 typedef unsigned cand_idx
;
226 /* The kind of candidate. */
237 /* The candidate statement S1. */
240 /* The base expression B: often an SSA name, but not always. */
246 /* The index constant i. */
249 /* The type of the candidate. This is normally the type of base_expr,
250 but casts may have occurred when combining feeding instructions.
251 A candidate can only be a basis for candidates of the same final type.
252 (For CAND_REFs, this is the type to be used for operand 1 of the
253 replacement MEM_REF.) */
256 /* The kind of candidate (CAND_MULT, etc.). */
259 /* Index of this candidate in the candidate vector. */
262 /* Index of the next candidate record for the same statement.
263 A statement may be useful in more than one way (e.g., due to
264 commutativity). So we can have multiple "interpretations"
266 cand_idx next_interp
;
268 /* Index of the basis statement S0, if any, in the candidate vector. */
271 /* First candidate for which this candidate is a basis, if one exists. */
274 /* Next candidate having the same basis as this one. */
277 /* If this is a conditional candidate, the CAND_PHI candidate
278 that defines the base SSA name B. */
281 /* Savings that can be expected from eliminating dead code if this
282 candidate is replaced. */
286 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
287 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
289 /* Pointers to candidates are chained together as part of a mapping
290 from base expressions to the candidates that use them. */
294 /* Base expression for the chain of candidates: often, but not
295 always, an SSA name. */
298 /* Pointer to a candidate. */
302 struct cand_chain_d
*next
;
306 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
307 typedef const struct cand_chain_d
*const_cand_chain_t
;
309 /* Information about a unique "increment" associated with candidates
310 having an SSA name for a stride. An increment is the difference
311 between the index of the candidate and the index of its basis,
312 i.e., (i - i') as discussed in the module commentary.
314 When we are not going to generate address arithmetic we treat
315 increments that differ only in sign as the same, allowing sharing
316 of the cost of initializers. The absolute value of the increment
317 is stored in the incr_info. */
321 /* The increment that relates a candidate to its basis. */
324 /* How many times the increment occurs in the candidate tree. */
327 /* Cost of replacing candidates using this increment. Negative and
328 zero costs indicate replacement should be performed. */
331 /* If this increment is profitable but is not -1, 0, or 1, it requires
332 an initializer T_0 = stride * incr to be found or introduced in the
333 nearest common dominator of all candidates. This field holds T_0
334 for subsequent use. */
337 /* If the initializer was found to already exist, this is the block
338 where it was found. */
342 typedef struct incr_info_d incr_info
, *incr_info_t
;
344 /* Candidates are maintained in a vector. If candidate X dominates
345 candidate Y, then X appears before Y in the vector; but the
346 converse does not necessarily hold. */
347 static vec
<slsr_cand_t
> cand_vec
;
361 enum phi_adjust_status
367 enum count_phis_status
373 /* Pointer map embodying a mapping from statements to candidates. */
374 static struct pointer_map_t
*stmt_cand_map
;
376 /* Obstack for candidates. */
377 static struct obstack cand_obstack
;
379 /* Obstack for candidate chains. */
380 static struct obstack chain_obstack
;
382 /* An array INCR_VEC of incr_infos is used during analysis of related
383 candidates having an SSA name for a stride. INCR_VEC_LEN describes
384 its current length. MAX_INCR_VEC_LEN is used to avoid costly
385 pathological cases. */
386 static incr_info_t incr_vec
;
387 static unsigned incr_vec_len
;
388 const int MAX_INCR_VEC_LEN
= 16;
390 /* For a chain of candidates with unknown stride, indicates whether or not
391 we must generate pointer arithmetic when replacing statements. */
392 static bool address_arithmetic_p
;
394 /* Forward function declarations. */
395 static slsr_cand_t
base_cand_from_table (tree
);
396 static tree
introduce_cast_before_cand (slsr_cand_t
, tree
, tree
);
397 static bool legal_cast_p_1 (tree
, tree
);
399 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
402 lookup_cand (cand_idx idx
)
404 return cand_vec
[idx
- 1];
407 /* Helper for hashing a candidate chain header. */
409 struct cand_chain_hasher
: typed_noop_remove
<cand_chain
>
411 typedef cand_chain value_type
;
412 typedef cand_chain compare_type
;
413 static inline hashval_t
hash (const value_type
*);
414 static inline bool equal (const value_type
*, const compare_type
*);
418 cand_chain_hasher::hash (const value_type
*p
)
420 tree base_expr
= p
->base_expr
;
421 return iterative_hash_expr (base_expr
, 0);
425 cand_chain_hasher::equal (const value_type
*chain1
, const compare_type
*chain2
)
427 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
430 /* Hash table embodying a mapping from base exprs to chains of candidates. */
431 static hash_table
<cand_chain_hasher
> base_cand_map
;
433 /* Pointer map used by tree_to_aff_combination_expand. */
434 static struct pointer_map_t
*name_expansions
;
435 /* Pointer map embodying a mapping from bases to alternative bases. */
436 static struct pointer_map_t
*alt_base_map
;
438 /* Given BASE, use the tree affine combiniation facilities to
439 find the underlying tree expression for BASE, with any
440 immediate offset excluded. */
443 get_alternative_base (tree base
)
445 tree
*result
= (tree
*) pointer_map_contains (alt_base_map
, base
);
452 tree_to_aff_combination_expand (base
, TREE_TYPE (base
),
453 &aff
, &name_expansions
);
454 aff
.offset
= tree_to_double_int (integer_zero_node
);
455 expr
= aff_combination_to_tree (&aff
);
457 result
= (tree
*) pointer_map_insert (alt_base_map
, base
);
458 gcc_assert (!*result
);
469 /* Look in the candidate table for a CAND_PHI that defines BASE and
470 return it if found; otherwise return NULL. */
473 find_phi_def (tree base
)
477 if (TREE_CODE (base
) != SSA_NAME
)
480 c
= base_cand_from_table (base
);
482 if (!c
|| c
->kind
!= CAND_PHI
)
488 /* Helper routine for find_basis_for_candidate. May be called twice:
489 once for the candidate's base expr, and optionally again either for
490 the candidate's phi definition or for a CAND_REF's alternative base
494 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
496 cand_chain mapping_key
;
498 slsr_cand_t basis
= NULL
;
500 // Limit potential of N^2 behavior for long candidate chains.
502 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
504 mapping_key
.base_expr
= base_expr
;
505 chain
= base_cand_map
.find (&mapping_key
);
507 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
509 slsr_cand_t one_basis
= chain
->cand
;
511 if (one_basis
->kind
!= c
->kind
512 || one_basis
->cand_stmt
== c
->cand_stmt
513 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
514 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
515 || !dominated_by_p (CDI_DOMINATORS
,
516 gimple_bb (c
->cand_stmt
),
517 gimple_bb (one_basis
->cand_stmt
)))
520 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
527 /* Use the base expr from candidate C to look for possible candidates
528 that can serve as a basis for C. Each potential basis must also
529 appear in a block that dominates the candidate statement and have
530 the same stride and type. If more than one possible basis exists,
531 the one with highest index in the vector is chosen; this will be
532 the most immediately dominating basis. */
535 find_basis_for_candidate (slsr_cand_t c
)
537 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
539 /* If a candidate doesn't have a basis using its base expression,
540 it may have a basis hidden by one or more intervening phis. */
541 if (!basis
&& c
->def_phi
)
543 basic_block basis_bb
, phi_bb
;
544 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
545 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
549 /* A hidden basis must dominate the phi-definition of the
550 candidate's base name. */
551 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
552 basis_bb
= gimple_bb (basis
->cand_stmt
);
554 if (phi_bb
== basis_bb
555 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
561 /* If we found a hidden basis, estimate additional dead-code
562 savings if the phi and its feeding statements can be removed. */
563 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
564 c
->dead_savings
+= phi_cand
->dead_savings
;
568 if (!basis
&& c
->kind
== CAND_REF
)
570 tree alt_base_expr
= get_alternative_base (c
->base_expr
);
572 basis
= find_basis_for_base_expr (c
, alt_base_expr
);
577 c
->sibling
= basis
->dependent
;
578 basis
->dependent
= c
->cand_num
;
579 return basis
->cand_num
;
585 /* Record a mapping from BASE to C, indicating that C may potentially serve
586 as a basis using that base expression. BASE may be the same as
587 C->BASE_EXPR; alternatively BASE can be a different tree that share the
588 underlining expression of C->BASE_EXPR. */
591 record_potential_basis (slsr_cand_t c
, tree base
)
598 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
599 node
->base_expr
= base
;
602 slot
= base_cand_map
.find_slot (node
, INSERT
);
606 cand_chain_t head
= (cand_chain_t
) (*slot
);
607 node
->next
= head
->next
;
614 /* Allocate storage for a new candidate and initialize its fields.
615 Attempt to find a basis for the candidate.
617 For CAND_REF, an alternative base may also be recorded and used
618 to find a basis. This helps cases where the expression hidden
619 behind BASE (which is usually an SSA_NAME) has immediate offset,
623 a2[i + 20][j] = 2; */
626 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
627 double_int index
, tree stride
, tree ctype
,
630 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
636 c
->cand_type
= ctype
;
638 c
->cand_num
= cand_vec
.length () + 1;
642 c
->def_phi
= kind
== CAND_MULT
? find_phi_def (base
) : 0;
643 c
->dead_savings
= savings
;
645 cand_vec
.safe_push (c
);
647 if (kind
== CAND_PHI
)
650 c
->basis
= find_basis_for_candidate (c
);
652 record_potential_basis (c
, base
);
653 if (kind
== CAND_REF
)
655 tree alt_base
= get_alternative_base (base
);
657 record_potential_basis (c
, alt_base
);
663 /* Determine the target cost of statement GS when compiling according
667 stmt_cost (gimple gs
, bool speed
)
669 tree lhs
, rhs1
, rhs2
;
670 enum machine_mode lhs_mode
;
672 gcc_assert (is_gimple_assign (gs
));
673 lhs
= gimple_assign_lhs (gs
);
674 rhs1
= gimple_assign_rhs1 (gs
);
675 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
677 switch (gimple_assign_rhs_code (gs
))
680 rhs2
= gimple_assign_rhs2 (gs
);
682 if (tree_fits_shwi_p (rhs2
))
683 return mult_by_coeff_cost (tree_to_shwi (rhs2
), lhs_mode
, speed
);
685 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
686 return mul_cost (speed
, lhs_mode
);
689 case POINTER_PLUS_EXPR
:
691 return add_cost (speed
, lhs_mode
);
694 return neg_cost (speed
, lhs_mode
);
697 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
699 /* Note that we don't assign costs to copies that in most cases
709 /* Look up the defining statement for BASE_IN and return a pointer
710 to its candidate in the candidate table, if any; otherwise NULL.
711 Only CAND_ADD and CAND_MULT candidates are returned. */
714 base_cand_from_table (tree base_in
)
718 gimple def
= SSA_NAME_DEF_STMT (base_in
);
720 return (slsr_cand_t
) NULL
;
722 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
724 if (result
&& (*result
)->kind
!= CAND_REF
)
727 return (slsr_cand_t
) NULL
;
730 /* Add an entry to the statement-to-candidate mapping. */
733 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
735 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
740 /* Given PHI which contains a phi statement, determine whether it
741 satisfies all the requirements of a phi candidate. If so, create
742 a candidate. Note that a CAND_PHI never has a basis itself, but
743 is used to help find a basis for subsequent candidates. */
746 slsr_process_phi (gimple phi
, bool speed
)
749 tree arg0_base
= NULL_TREE
, base_type
;
751 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
752 unsigned savings
= 0;
754 /* A CAND_PHI requires each of its arguments to have the same
755 derived base name. (See the module header commentary for a
756 definition of derived base names.) Furthermore, all feeding
757 definitions must be in the same position in the loop hierarchy
760 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
762 slsr_cand_t arg_cand
;
763 tree arg
= gimple_phi_arg_def (phi
, i
);
764 tree derived_base_name
= NULL_TREE
;
765 gimple arg_stmt
= NULL
;
766 basic_block arg_bb
= NULL
;
768 if (TREE_CODE (arg
) != SSA_NAME
)
771 arg_cand
= base_cand_from_table (arg
);
775 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
777 if (!arg_cand
->next_interp
)
780 arg_cand
= lookup_cand (arg_cand
->next_interp
);
783 if (!integer_onep (arg_cand
->stride
))
786 derived_base_name
= arg_cand
->base_expr
;
787 arg_stmt
= arg_cand
->cand_stmt
;
788 arg_bb
= gimple_bb (arg_stmt
);
790 /* Gather potential dead code savings if the phi statement
791 can be removed later on. */
792 if (has_single_use (arg
))
794 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
795 savings
+= arg_cand
->dead_savings
;
797 savings
+= stmt_cost (arg_stmt
, speed
);
802 derived_base_name
= arg
;
804 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
805 arg_bb
= single_succ (ENTRY_BLOCK_PTR_FOR_FN (cfun
));
807 gimple_bb (SSA_NAME_DEF_STMT (arg
));
810 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
814 arg0_base
= derived_base_name
;
815 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
819 /* Create the candidate. "alloc_cand_and_find_basis" is named
820 misleadingly for this case, as no basis will be sought for a
822 base_type
= TREE_TYPE (arg0_base
);
824 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
, double_int_zero
,
825 integer_one_node
, base_type
, savings
);
827 /* Add the candidate to the statement-candidate mapping. */
828 add_cand_for_stmt (phi
, c
);
831 /* Given PBASE which is a pointer to tree, look up the defining
832 statement for it and check whether the candidate is in the
835 X = B + (1 * S), S is integer constant
836 X = B + (i * S), S is integer one
838 If so, set PBASE to the candidate's base_expr and return double
840 Otherwise, just return double int zero. */
843 backtrace_base_for_ref (tree
*pbase
)
845 tree base_in
= *pbase
;
846 slsr_cand_t base_cand
;
848 STRIP_NOPS (base_in
);
850 /* Strip off widening conversion(s) to handle cases where
851 e.g. 'B' is widened from an 'int' in order to calculate
853 if (CONVERT_EXPR_P (base_in
)
854 && legal_cast_p_1 (base_in
, TREE_OPERAND (base_in
, 0)))
855 base_in
= get_unwidened (base_in
, NULL_TREE
);
857 if (TREE_CODE (base_in
) != SSA_NAME
)
858 return tree_to_double_int (integer_zero_node
);
860 base_cand
= base_cand_from_table (base_in
);
862 while (base_cand
&& base_cand
->kind
!= CAND_PHI
)
864 if (base_cand
->kind
== CAND_ADD
865 && base_cand
->index
.is_one ()
866 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
868 /* X = B + (1 * S), S is integer constant. */
869 *pbase
= base_cand
->base_expr
;
870 return tree_to_double_int (base_cand
->stride
);
872 else if (base_cand
->kind
== CAND_ADD
873 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
874 && integer_onep (base_cand
->stride
))
876 /* X = B + (i * S), S is integer one. */
877 *pbase
= base_cand
->base_expr
;
878 return base_cand
->index
;
881 if (base_cand
->next_interp
)
882 base_cand
= lookup_cand (base_cand
->next_interp
);
887 return tree_to_double_int (integer_zero_node
);
890 /* Look for the following pattern:
892 *PBASE: MEM_REF (T1, C1)
894 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
896 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
898 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
900 *PINDEX: C4 * BITS_PER_UNIT
902 If not present, leave the input values unchanged and return FALSE.
903 Otherwise, modify the input values as follows and return TRUE:
906 *POFFSET: MULT_EXPR (T2, C3)
907 *PINDEX: C1 + (C2 * C3) + C4
909 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
910 will be further restructured to:
913 *POFFSET: MULT_EXPR (T2', C3)
914 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
917 restructure_reference (tree
*pbase
, tree
*poffset
, double_int
*pindex
,
920 tree base
= *pbase
, offset
= *poffset
;
921 double_int index
= *pindex
;
922 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
923 tree mult_op0
, mult_op1
, t1
, t2
, type
;
924 double_int c1
, c2
, c3
, c4
, c5
;
928 || TREE_CODE (base
) != MEM_REF
929 || TREE_CODE (offset
) != MULT_EXPR
930 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
931 || !index
.umod (bpu
, FLOOR_MOD_EXPR
).is_zero ())
934 t1
= TREE_OPERAND (base
, 0);
935 c1
= mem_ref_offset (base
);
936 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
938 mult_op0
= TREE_OPERAND (offset
, 0);
939 mult_op1
= TREE_OPERAND (offset
, 1);
941 c3
= tree_to_double_int (mult_op1
);
943 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
945 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
947 t2
= TREE_OPERAND (mult_op0
, 0);
948 c2
= tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
953 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
955 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
957 t2
= TREE_OPERAND (mult_op0
, 0);
958 c2
= -tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
966 c2
= double_int_zero
;
969 c4
= index
.udiv (bpu
, FLOOR_DIV_EXPR
);
970 c5
= backtrace_base_for_ref (&t2
);
973 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, fold_convert (sizetype
, t2
),
974 double_int_to_tree (sizetype
, c3
));
975 *pindex
= c1
+ c2
* c3
+ c4
+ c5
* c3
;
981 /* Given GS which contains a data reference, create a CAND_REF entry in
982 the candidate table and attempt to find a basis. */
985 slsr_process_ref (gimple gs
)
987 tree ref_expr
, base
, offset
, type
;
988 HOST_WIDE_INT bitsize
, bitpos
;
989 enum machine_mode mode
;
990 int unsignedp
, volatilep
;
994 if (gimple_vdef (gs
))
995 ref_expr
= gimple_assign_lhs (gs
);
997 ref_expr
= gimple_assign_rhs1 (gs
);
999 if (!handled_component_p (ref_expr
)
1000 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
1001 || (TREE_CODE (ref_expr
) == COMPONENT_REF
1002 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
1005 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
1006 &unsignedp
, &volatilep
, false);
1007 index
= double_int::from_uhwi (bitpos
);
1009 if (!restructure_reference (&base
, &offset
, &index
, &type
))
1012 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
1015 /* Add the candidate to the statement-candidate mapping. */
1016 add_cand_for_stmt (gs
, c
);
1019 /* Create a candidate entry for a statement GS, where GS multiplies
1020 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
1021 about the two SSA names into the new candidate. Return the new
1025 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1027 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1029 unsigned savings
= 0;
1031 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1033 /* Look at all interpretations of the base candidate, if necessary,
1034 to find information to propagate into this candidate. */
1035 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1038 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
1044 base
= base_cand
->base_expr
;
1045 index
= base_cand
->index
;
1047 ctype
= base_cand
->cand_type
;
1048 if (has_single_use (base_in
))
1049 savings
= (base_cand
->dead_savings
1050 + stmt_cost (base_cand
->cand_stmt
, speed
));
1052 else if (base_cand
->kind
== CAND_ADD
1053 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1055 /* Y = B + (i' * S), S constant
1057 ============================
1058 X = B + ((i' * S) * Z) */
1059 base
= base_cand
->base_expr
;
1060 index
= base_cand
->index
* tree_to_double_int (base_cand
->stride
);
1062 ctype
= base_cand
->cand_type
;
1063 if (has_single_use (base_in
))
1064 savings
= (base_cand
->dead_savings
1065 + stmt_cost (base_cand
->cand_stmt
, speed
));
1068 if (base_cand
->next_interp
)
1069 base_cand
= lookup_cand (base_cand
->next_interp
);
1076 /* No interpretations had anything useful to propagate, so
1077 produce X = (Y + 0) * Z. */
1079 index
= double_int_zero
;
1081 ctype
= TREE_TYPE (base_in
);
1084 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1089 /* Create a candidate entry for a statement GS, where GS multiplies
1090 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1091 information about BASE_IN into the new candidate. Return the new
1095 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1097 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1098 double_int index
, temp
;
1099 unsigned savings
= 0;
1101 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1103 /* Look at all interpretations of the base candidate, if necessary,
1104 to find information to propagate into this candidate. */
1105 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1107 if (base_cand
->kind
== CAND_MULT
1108 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1110 /* Y = (B + i') * S, S constant
1112 ============================
1113 X = (B + i') * (S * c) */
1114 base
= base_cand
->base_expr
;
1115 index
= base_cand
->index
;
1116 temp
= tree_to_double_int (base_cand
->stride
)
1117 * tree_to_double_int (stride_in
);
1118 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
1119 ctype
= base_cand
->cand_type
;
1120 if (has_single_use (base_in
))
1121 savings
= (base_cand
->dead_savings
1122 + stmt_cost (base_cand
->cand_stmt
, speed
));
1124 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
1128 ===========================
1130 base
= base_cand
->base_expr
;
1131 index
= base_cand
->index
;
1133 ctype
= base_cand
->cand_type
;
1134 if (has_single_use (base_in
))
1135 savings
= (base_cand
->dead_savings
1136 + stmt_cost (base_cand
->cand_stmt
, speed
));
1138 else if (base_cand
->kind
== CAND_ADD
1139 && base_cand
->index
.is_one ()
1140 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1142 /* Y = B + (1 * S), S constant
1144 ===========================
1146 base
= base_cand
->base_expr
;
1147 index
= tree_to_double_int (base_cand
->stride
);
1149 ctype
= base_cand
->cand_type
;
1150 if (has_single_use (base_in
))
1151 savings
= (base_cand
->dead_savings
1152 + stmt_cost (base_cand
->cand_stmt
, speed
));
1155 if (base_cand
->next_interp
)
1156 base_cand
= lookup_cand (base_cand
->next_interp
);
1163 /* No interpretations had anything useful to propagate, so
1164 produce X = (Y + 0) * c. */
1166 index
= double_int_zero
;
1168 ctype
= TREE_TYPE (base_in
);
1171 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1176 /* Given GS which is a multiply of scalar integers, make an appropriate
1177 entry in the candidate table. If this is a multiply of two SSA names,
1178 create two CAND_MULT interpretations and attempt to find a basis for
1179 each of them. Otherwise, create a single CAND_MULT and attempt to
1183 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1187 /* If this is a multiply of an SSA name with itself, it is highly
1188 unlikely that we will get a strength reduction opportunity, so
1189 don't record it as a candidate. This simplifies the logic for
1190 finding a basis, so if this is removed that must be considered. */
1194 if (TREE_CODE (rhs2
) == SSA_NAME
)
1196 /* Record an interpretation of this statement in the candidate table
1197 assuming RHS1 is the base expression and RHS2 is the stride. */
1198 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1200 /* Add the first interpretation to the statement-candidate mapping. */
1201 add_cand_for_stmt (gs
, c
);
1203 /* Record another interpretation of this statement assuming RHS1
1204 is the stride and RHS2 is the base expression. */
1205 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1206 c
->next_interp
= c2
->cand_num
;
1210 /* Record an interpretation for the multiply-immediate. */
1211 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1213 /* Add the interpretation to the statement-candidate mapping. */
1214 add_cand_for_stmt (gs
, c
);
1218 /* Create a candidate entry for a statement GS, where GS adds two
1219 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1220 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1221 information about the two SSA names into the new candidate.
1222 Return the new candidate. */
1225 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1226 bool subtract_p
, bool speed
)
1228 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1230 unsigned savings
= 0;
1232 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1233 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1235 /* The most useful transformation is a multiply-immediate feeding
1236 an add or subtract. Look for that first. */
1237 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1239 if (addend_cand
->kind
== CAND_MULT
1240 && addend_cand
->index
.is_zero ()
1241 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1243 /* Z = (B + 0) * S, S constant
1245 ===========================
1246 X = Y + ((+/-1 * S) * B) */
1248 index
= tree_to_double_int (addend_cand
->stride
);
1251 stride
= addend_cand
->base_expr
;
1252 ctype
= TREE_TYPE (base_in
);
1253 if (has_single_use (addend_in
))
1254 savings
= (addend_cand
->dead_savings
1255 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1258 if (addend_cand
->next_interp
)
1259 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1264 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1266 if (base_cand
->kind
== CAND_ADD
1267 && (base_cand
->index
.is_zero ()
1268 || operand_equal_p (base_cand
->stride
,
1269 integer_zero_node
, 0)))
1271 /* Y = B + (i' * S), i' * S = 0
1273 ============================
1274 X = B + (+/-1 * Z) */
1275 base
= base_cand
->base_expr
;
1276 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1278 ctype
= base_cand
->cand_type
;
1279 if (has_single_use (base_in
))
1280 savings
= (base_cand
->dead_savings
1281 + stmt_cost (base_cand
->cand_stmt
, speed
));
1283 else if (subtract_p
)
1285 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1287 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1289 if (subtrahend_cand
->kind
== CAND_MULT
1290 && subtrahend_cand
->index
.is_zero ()
1291 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1293 /* Z = (B + 0) * S, S constant
1295 ===========================
1296 Value: X = Y + ((-1 * S) * B) */
1298 index
= tree_to_double_int (subtrahend_cand
->stride
);
1300 stride
= subtrahend_cand
->base_expr
;
1301 ctype
= TREE_TYPE (base_in
);
1302 if (has_single_use (addend_in
))
1303 savings
= (subtrahend_cand
->dead_savings
1304 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1307 if (subtrahend_cand
->next_interp
)
1308 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1310 subtrahend_cand
= NULL
;
1314 if (base_cand
->next_interp
)
1315 base_cand
= lookup_cand (base_cand
->next_interp
);
1322 /* No interpretations had anything useful to propagate, so
1323 produce X = Y + (1 * Z). */
1325 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1327 ctype
= TREE_TYPE (base_in
);
1330 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1335 /* Create a candidate entry for a statement GS, where GS adds SSA
1336 name BASE_IN to constant INDEX_IN. Propagate any known information
1337 about BASE_IN into the new candidate. Return the new candidate. */
1340 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
1342 enum cand_kind kind
= CAND_ADD
;
1343 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1344 double_int index
, multiple
;
1345 unsigned savings
= 0;
1347 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1349 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1351 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
1353 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1354 && index_in
.multiple_of (tree_to_double_int (base_cand
->stride
),
1355 unsigned_p
, &multiple
))
1357 /* Y = (B + i') * S, S constant, c = kS for some integer k
1359 ============================
1360 X = (B + (i'+ k)) * S
1362 Y = B + (i' * S), S constant, c = kS for some integer k
1364 ============================
1365 X = (B + (i'+ k)) * S */
1366 kind
= base_cand
->kind
;
1367 base
= base_cand
->base_expr
;
1368 index
= base_cand
->index
+ multiple
;
1369 stride
= base_cand
->stride
;
1370 ctype
= base_cand
->cand_type
;
1371 if (has_single_use (base_in
))
1372 savings
= (base_cand
->dead_savings
1373 + stmt_cost (base_cand
->cand_stmt
, speed
));
1376 if (base_cand
->next_interp
)
1377 base_cand
= lookup_cand (base_cand
->next_interp
);
1384 /* No interpretations had anything useful to propagate, so
1385 produce X = Y + (c * 1). */
1389 stride
= integer_one_node
;
1390 ctype
= TREE_TYPE (base_in
);
1393 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1398 /* Given GS which is an add or subtract of scalar integers or pointers,
1399 make at least one appropriate entry in the candidate table. */
1402 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1404 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1405 slsr_cand_t c
= NULL
, c2
;
1407 if (TREE_CODE (rhs2
) == SSA_NAME
)
1409 /* First record an interpretation assuming RHS1 is the base expression
1410 and RHS2 is the stride. But it doesn't make sense for the
1411 stride to be a pointer, so don't record a candidate in that case. */
1412 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1414 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1416 /* Add the first interpretation to the statement-candidate
1418 add_cand_for_stmt (gs
, c
);
1421 /* If the two RHS operands are identical, or this is a subtract,
1423 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1426 /* Otherwise, record another interpretation assuming RHS2 is the
1427 base expression and RHS1 is the stride, again provided that the
1428 stride is not a pointer. */
1429 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1431 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1433 c
->next_interp
= c2
->cand_num
;
1435 add_cand_for_stmt (gs
, c2
);
1442 /* Record an interpretation for the add-immediate. */
1443 index
= tree_to_double_int (rhs2
);
1447 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1449 /* Add the interpretation to the statement-candidate mapping. */
1450 add_cand_for_stmt (gs
, c
);
1454 /* Given GS which is a negate of a scalar integer, make an appropriate
1455 entry in the candidate table. A negate is equivalent to a multiply
1459 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1461 /* Record a CAND_MULT interpretation for the multiply by -1. */
1462 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1464 /* Add the interpretation to the statement-candidate mapping. */
1465 add_cand_for_stmt (gs
, c
);
1468 /* Help function for legal_cast_p, operating on two trees. Checks
1469 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1470 for more details. */
1473 legal_cast_p_1 (tree lhs
, tree rhs
)
1475 tree lhs_type
, rhs_type
;
1476 unsigned lhs_size
, rhs_size
;
1477 bool lhs_wraps
, rhs_wraps
;
1479 lhs_type
= TREE_TYPE (lhs
);
1480 rhs_type
= TREE_TYPE (rhs
);
1481 lhs_size
= TYPE_PRECISION (lhs_type
);
1482 rhs_size
= TYPE_PRECISION (rhs_type
);
1483 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1484 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1486 if (lhs_size
< rhs_size
1487 || (rhs_wraps
&& !lhs_wraps
)
1488 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1494 /* Return TRUE if GS is a statement that defines an SSA name from
1495 a conversion and is legal for us to combine with an add and multiply
1496 in the candidate table. For example, suppose we have:
1502 Without the type-cast, we would create a CAND_MULT for D with base B,
1503 index i, and stride S. We want to record this candidate only if it
1504 is equivalent to apply the type cast following the multiply:
1510 We will record the type with the candidate for D. This allows us
1511 to use a similar previous candidate as a basis. If we have earlier seen
1517 we can replace D with
1519 D = D' + (i - i') * S;
1521 But if moving the type-cast would change semantics, we mustn't do this.
1523 This is legitimate for casts from a non-wrapping integral type to
1524 any integral type of the same or larger size. It is not legitimate
1525 to convert a wrapping type to a non-wrapping type, or to a wrapping
1526 type of a different size. I.e., with a wrapping type, we must
1527 assume that the addition B + i could wrap, in which case performing
1528 the multiply before or after one of the "illegal" type casts will
1529 have different semantics. */
1532 legal_cast_p (gimple gs
, tree rhs
)
1534 if (!is_gimple_assign (gs
)
1535 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1538 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1541 /* Given GS which is a cast to a scalar integer type, determine whether
1542 the cast is legal for strength reduction. If so, make at least one
1543 appropriate entry in the candidate table. */
1546 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1549 slsr_cand_t base_cand
, c
, c2
;
1550 unsigned savings
= 0;
1552 if (!legal_cast_p (gs
, rhs1
))
1555 lhs
= gimple_assign_lhs (gs
);
1556 base_cand
= base_cand_from_table (rhs1
);
1557 ctype
= TREE_TYPE (lhs
);
1559 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1563 /* Propagate all data from the base candidate except the type,
1564 which comes from the cast, and the base candidate's cast,
1565 which is no longer applicable. */
1566 if (has_single_use (rhs1
))
1567 savings
= (base_cand
->dead_savings
1568 + stmt_cost (base_cand
->cand_stmt
, speed
));
1570 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1571 base_cand
->base_expr
,
1572 base_cand
->index
, base_cand
->stride
,
1574 if (base_cand
->next_interp
)
1575 base_cand
= lookup_cand (base_cand
->next_interp
);
1582 /* If nothing is known about the RHS, create fresh CAND_ADD and
1583 CAND_MULT interpretations:
1588 The first of these is somewhat arbitrary, but the choice of
1589 1 for the stride simplifies the logic for propagating casts
1591 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1592 integer_one_node
, ctype
, 0);
1593 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1594 integer_one_node
, ctype
, 0);
1595 c
->next_interp
= c2
->cand_num
;
1598 /* Add the first (or only) interpretation to the statement-candidate
1600 add_cand_for_stmt (gs
, c
);
1603 /* Given GS which is a copy of a scalar integer type, make at least one
1604 appropriate entry in the candidate table.
1606 This interface is included for completeness, but is unnecessary
1607 if this pass immediately follows a pass that performs copy
1608 propagation, such as DOM. */
1611 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1613 slsr_cand_t base_cand
, c
, c2
;
1614 unsigned savings
= 0;
1616 base_cand
= base_cand_from_table (rhs1
);
1618 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1622 /* Propagate all data from the base candidate. */
1623 if (has_single_use (rhs1
))
1624 savings
= (base_cand
->dead_savings
1625 + stmt_cost (base_cand
->cand_stmt
, speed
));
1627 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1628 base_cand
->base_expr
,
1629 base_cand
->index
, base_cand
->stride
,
1630 base_cand
->cand_type
, savings
);
1631 if (base_cand
->next_interp
)
1632 base_cand
= lookup_cand (base_cand
->next_interp
);
1639 /* If nothing is known about the RHS, create fresh CAND_ADD and
1640 CAND_MULT interpretations:
1645 The first of these is somewhat arbitrary, but the choice of
1646 1 for the stride simplifies the logic for propagating casts
1648 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1649 integer_one_node
, TREE_TYPE (rhs1
), 0);
1650 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1651 integer_one_node
, TREE_TYPE (rhs1
), 0);
1652 c
->next_interp
= c2
->cand_num
;
1655 /* Add the first (or only) interpretation to the statement-candidate
1657 add_cand_for_stmt (gs
, c
);
1660 class find_candidates_dom_walker
: public dom_walker
1663 find_candidates_dom_walker (cdi_direction direction
)
1664 : dom_walker (direction
) {}
1665 virtual void before_dom_children (basic_block
);
1668 /* Find strength-reduction candidates in block BB. */
1671 find_candidates_dom_walker::before_dom_children (basic_block bb
)
1673 bool speed
= optimize_bb_for_speed_p (bb
);
1674 gimple_stmt_iterator gsi
;
1676 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1677 slsr_process_phi (gsi_stmt (gsi
), speed
);
1679 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1681 gimple gs
= gsi_stmt (gsi
);
1683 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1684 slsr_process_ref (gs
);
1686 else if (is_gimple_assign (gs
)
1687 && SCALAR_INT_MODE_P
1688 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1690 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1692 switch (gimple_assign_rhs_code (gs
))
1696 rhs1
= gimple_assign_rhs1 (gs
);
1697 rhs2
= gimple_assign_rhs2 (gs
);
1698 /* Should never happen, but currently some buggy situations
1699 in earlier phases put constants in rhs1. */
1700 if (TREE_CODE (rhs1
) != SSA_NAME
)
1704 /* Possible future opportunity: rhs1 of a ptr+ can be
1706 case POINTER_PLUS_EXPR
:
1708 rhs2
= gimple_assign_rhs2 (gs
);
1714 rhs1
= gimple_assign_rhs1 (gs
);
1715 if (TREE_CODE (rhs1
) != SSA_NAME
)
1723 switch (gimple_assign_rhs_code (gs
))
1726 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1730 case POINTER_PLUS_EXPR
:
1732 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1736 slsr_process_neg (gs
, rhs1
, speed
);
1740 slsr_process_cast (gs
, rhs1
, speed
);
1744 slsr_process_copy (gs
, rhs1
, speed
);
1754 /* Dump a candidate for debug. */
1757 dump_candidate (slsr_cand_t c
)
1759 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1760 gimple_bb (c
->cand_stmt
)->index
);
1761 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1765 fputs (" MULT : (", dump_file
);
1766 print_generic_expr (dump_file
, c
->base_expr
, 0);
1767 fputs (" + ", dump_file
);
1768 dump_double_int (dump_file
, c
->index
, false);
1769 fputs (") * ", dump_file
);
1770 print_generic_expr (dump_file
, c
->stride
, 0);
1771 fputs (" : ", dump_file
);
1774 fputs (" ADD : ", dump_file
);
1775 print_generic_expr (dump_file
, c
->base_expr
, 0);
1776 fputs (" + (", dump_file
);
1777 dump_double_int (dump_file
, c
->index
, false);
1778 fputs (" * ", dump_file
);
1779 print_generic_expr (dump_file
, c
->stride
, 0);
1780 fputs (") : ", dump_file
);
1783 fputs (" REF : ", dump_file
);
1784 print_generic_expr (dump_file
, c
->base_expr
, 0);
1785 fputs (" + (", dump_file
);
1786 print_generic_expr (dump_file
, c
->stride
, 0);
1787 fputs (") + ", dump_file
);
1788 dump_double_int (dump_file
, c
->index
, false);
1789 fputs (" : ", dump_file
);
1792 fputs (" PHI : ", dump_file
);
1793 print_generic_expr (dump_file
, c
->base_expr
, 0);
1794 fputs (" + (unknown * ", dump_file
);
1795 print_generic_expr (dump_file
, c
->stride
, 0);
1796 fputs (") : ", dump_file
);
1801 print_generic_expr (dump_file
, c
->cand_type
, 0);
1802 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1803 c
->basis
, c
->dependent
, c
->sibling
);
1804 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1805 c
->next_interp
, c
->dead_savings
);
1807 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1808 fputs ("\n", dump_file
);
1811 /* Dump the candidate vector for debug. */
1814 dump_cand_vec (void)
1819 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1821 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1825 /* Callback used to dump the candidate chains hash table. */
1828 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1830 const_cand_chain_t chain
= *slot
;
1833 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1834 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1836 for (p
= chain
->next
; p
; p
= p
->next
)
1837 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1839 fputs ("\n", dump_file
);
1843 /* Dump the candidate chains. */
1846 dump_cand_chains (void)
1848 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1849 base_cand_map
.traverse_noresize
<void *, ssa_base_cand_dump_callback
> (NULL
);
1850 fputs ("\n", dump_file
);
1853 /* Dump the increment vector for debug. */
1856 dump_incr_vec (void)
1858 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1862 fprintf (dump_file
, "\nIncrement vector:\n\n");
1864 for (i
= 0; i
< incr_vec_len
; i
++)
1866 fprintf (dump_file
, "%3d increment: ", i
);
1867 dump_double_int (dump_file
, incr_vec
[i
].incr
, false);
1868 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1869 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1870 fputs ("\n initializer: ", dump_file
);
1871 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1872 fputs ("\n\n", dump_file
);
1877 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1881 replace_ref (tree
*expr
, slsr_cand_t c
)
1883 tree add_expr
, mem_ref
, acc_type
= TREE_TYPE (*expr
);
1884 unsigned HOST_WIDE_INT misalign
;
1887 /* Ensure the memory reference carries the minimum alignment
1888 requirement for the data type. See PR58041. */
1889 get_object_alignment_1 (*expr
, &align
, &misalign
);
1891 align
= (misalign
& -misalign
);
1892 if (align
< TYPE_ALIGN (acc_type
))
1893 acc_type
= build_aligned_type (acc_type
, align
);
1895 add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1896 c
->base_expr
, c
->stride
);
1897 mem_ref
= fold_build2 (MEM_REF
, acc_type
, add_expr
,
1898 double_int_to_tree (c
->cand_type
, c
->index
));
1900 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1901 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1902 TREE_OPERAND (mem_ref
, 0)
1903 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1904 /*simple_p=*/true, NULL
,
1905 /*before=*/true, GSI_SAME_STMT
);
1906 copy_ref_info (mem_ref
, *expr
);
1908 update_stmt (c
->cand_stmt
);
1911 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1912 dependent of candidate C with an equivalent strength-reduced data
1916 replace_refs (slsr_cand_t c
)
1918 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1920 fputs ("Replacing reference: ", dump_file
);
1921 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1924 if (gimple_vdef (c
->cand_stmt
))
1926 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1927 replace_ref (lhs
, c
);
1931 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1932 replace_ref (rhs
, c
);
1935 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1937 fputs ("With: ", dump_file
);
1938 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1939 fputs ("\n", dump_file
);
1943 replace_refs (lookup_cand (c
->sibling
));
1946 replace_refs (lookup_cand (c
->dependent
));
1949 /* Return TRUE if candidate C is dependent upon a PHI. */
1952 phi_dependent_cand_p (slsr_cand_t c
)
1954 /* A candidate is not necessarily dependent upon a PHI just because
1955 it has a phi definition for its base name. It may have a basis
1956 that relies upon the same phi definition, in which case the PHI
1957 is irrelevant to this candidate. */
1960 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1963 /* Calculate the increment required for candidate C relative to
1967 cand_increment (slsr_cand_t c
)
1971 /* If the candidate doesn't have a basis, just return its own
1972 index. This is useful in record_increments to help us find
1973 an existing initializer. Also, if the candidate's basis is
1974 hidden by a phi, then its own index will be the increment
1975 from the newly introduced phi basis. */
1976 if (!c
->basis
|| phi_dependent_cand_p (c
))
1979 basis
= lookup_cand (c
->basis
);
1980 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1981 return c
->index
- basis
->index
;
1984 /* Calculate the increment required for candidate C relative to
1985 its basis. If we aren't going to generate pointer arithmetic
1986 for this candidate, return the absolute value of that increment
1989 static inline double_int
1990 cand_abs_increment (slsr_cand_t c
)
1992 double_int increment
= cand_increment (c
);
1994 if (!address_arithmetic_p
&& increment
.is_negative ())
1995 increment
= -increment
;
2000 /* Return TRUE iff candidate C has already been replaced under
2001 another interpretation. */
2004 cand_already_replaced (slsr_cand_t c
)
2006 return (gimple_bb (c
->cand_stmt
) == 0);
2009 /* Common logic used by replace_unconditional_candidate and
2010 replace_conditional_candidate. */
2013 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, double_int bump
)
2015 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
2016 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
2018 /* It is highly unlikely, but possible, that the resulting
2019 bump doesn't fit in a HWI. Abandon the replacement
2020 in this case. This does not affect siblings or dependents
2021 of C. Restriction to signed HWI is conservative for unsigned
2022 types but allows for safe negation without twisted logic. */
2023 if (bump
.fits_shwi ()
2024 && bump
.to_shwi () != HOST_WIDE_INT_MIN
2025 /* It is not useful to replace casts, copies, or adds of
2026 an SSA name and a constant. */
2027 && cand_code
!= MODIFY_EXPR
2028 && cand_code
!= NOP_EXPR
2029 && cand_code
!= PLUS_EXPR
2030 && cand_code
!= POINTER_PLUS_EXPR
2031 && cand_code
!= MINUS_EXPR
)
2033 enum tree_code code
= PLUS_EXPR
;
2035 gimple stmt_to_print
= NULL
;
2037 /* If the basis name and the candidate's LHS have incompatible
2038 types, introduce a cast. */
2039 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
2040 basis_name
= introduce_cast_before_cand (c
, target_type
, basis_name
);
2041 if (bump
.is_negative ())
2047 bump_tree
= double_int_to_tree (target_type
, bump
);
2049 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2051 fputs ("Replacing: ", dump_file
);
2052 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
2055 if (bump
.is_zero ())
2057 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
2058 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
2059 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2060 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
2061 gsi_replace (&gsi
, copy_stmt
, false);
2062 c
->cand_stmt
= copy_stmt
;
2063 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2064 stmt_to_print
= copy_stmt
;
2069 if (cand_code
!= NEGATE_EXPR
) {
2070 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2071 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2073 if (cand_code
!= NEGATE_EXPR
2074 && ((operand_equal_p (rhs1
, basis_name
, 0)
2075 && operand_equal_p (rhs2
, bump_tree
, 0))
2076 || (operand_equal_p (rhs1
, bump_tree
, 0)
2077 && operand_equal_p (rhs2
, basis_name
, 0))))
2079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2081 fputs ("(duplicate, not actually replacing)", dump_file
);
2082 stmt_to_print
= c
->cand_stmt
;
2087 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2088 gimple_assign_set_rhs_with_ops (&gsi
, code
,
2089 basis_name
, bump_tree
);
2090 update_stmt (gsi_stmt (gsi
));
2091 c
->cand_stmt
= gsi_stmt (gsi
);
2092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2093 stmt_to_print
= gsi_stmt (gsi
);
2097 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2099 fputs ("With: ", dump_file
);
2100 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
2101 fputs ("\n", dump_file
);
2106 /* Replace candidate C with an add or subtract. Note that we only
2107 operate on CAND_MULTs with known strides, so we will never generate
2108 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2109 X = Y + ((i - i') * S), as described in the module commentary. The
2110 folded value ((i - i') * S) is referred to here as the "bump." */
2113 replace_unconditional_candidate (slsr_cand_t c
)
2116 double_int stride
, bump
;
2118 if (cand_already_replaced (c
))
2121 basis
= lookup_cand (c
->basis
);
2122 stride
= tree_to_double_int (c
->stride
);
2123 bump
= cand_increment (c
) * stride
;
2125 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
);
2128 /* Return the index in the increment vector of the given INCREMENT,
2129 or -1 if not found. The latter can occur if more than
2130 MAX_INCR_VEC_LEN increments have been found. */
2133 incr_vec_index (double_int increment
)
2137 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
2140 if (i
< incr_vec_len
)
2146 /* Create a new statement along edge E to add BASIS_NAME to the product
2147 of INCREMENT and the stride of candidate C. Create and return a new
2148 SSA name from *VAR to be used as the LHS of the new statement.
2149 KNOWN_STRIDE is true iff C's stride is a constant. */
2152 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
2153 double_int increment
, edge e
, location_t loc
,
2156 basic_block insert_bb
;
2157 gimple_stmt_iterator gsi
;
2158 tree lhs
, basis_type
;
2161 /* If the add candidate along this incoming edge has the same
2162 index as C's hidden basis, the hidden basis represents this
2164 if (increment
.is_zero ())
2167 basis_type
= TREE_TYPE (basis_name
);
2168 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2173 enum tree_code code
= PLUS_EXPR
;
2174 double_int bump
= increment
* tree_to_double_int (c
->stride
);
2175 if (bump
.is_negative ())
2181 bump_tree
= double_int_to_tree (basis_type
, bump
);
2182 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2188 bool negate_incr
= (!address_arithmetic_p
&& increment
.is_negative ());
2189 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2190 gcc_assert (i
>= 0);
2192 if (incr_vec
[i
].initializer
)
2194 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2195 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2196 incr_vec
[i
].initializer
);
2198 else if (increment
.is_one ())
2199 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, lhs
, basis_name
,
2201 else if (increment
.is_minus_one ())
2202 new_stmt
= gimple_build_assign_with_ops (MINUS_EXPR
, lhs
, basis_name
,
2208 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2209 gsi
= gsi_last_bb (insert_bb
);
2211 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2212 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2214 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2216 gimple_set_location (new_stmt
, loc
);
2218 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2220 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2221 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2227 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2228 is hidden by the phi node FROM_PHI, create a new phi node in the same
2229 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2230 with its phi arguments representing conditional adjustments to the
2231 hidden basis along conditional incoming paths. Those adjustments are
2232 made by creating add statements (and sometimes recursively creating
2233 phis) along those incoming paths. LOC is the location to attach to
2234 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2238 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2239 location_t loc
, bool known_stride
)
2245 slsr_cand_t basis
= lookup_cand (c
->basis
);
2246 int nargs
= gimple_phi_num_args (from_phi
);
2247 basic_block phi_bb
= gimple_bb (from_phi
);
2248 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2249 phi_args
.create (nargs
);
2251 /* Process each argument of the existing phi that represents
2252 conditionally-executed add candidates. */
2253 for (i
= 0; i
< nargs
; i
++)
2255 edge e
= (*phi_bb
->preds
)[i
];
2256 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2259 /* If the phi argument is the base name of the CAND_PHI, then
2260 this incoming arc should use the hidden basis. */
2261 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2262 if (basis
->index
.is_zero ())
2263 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2266 double_int incr
= -basis
->index
;
2267 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2268 e
, loc
, known_stride
);
2272 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2274 /* If there is another phi along this incoming edge, we must
2275 process it in the same fashion to ensure that all basis
2276 adjustments are made along its incoming edges. */
2277 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2278 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2282 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2283 double_int diff
= arg_cand
->index
- basis
->index
;
2284 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2285 e
, loc
, known_stride
);
2289 /* Because of recursion, we need to save the arguments in a vector
2290 so we can create the PHI statement all at once. Otherwise the
2291 storage for the half-created PHI can be reclaimed. */
2292 phi_args
.safe_push (feeding_def
);
2295 /* Create the new phi basis. */
2296 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2297 phi
= create_phi_node (name
, phi_bb
);
2298 SSA_NAME_DEF_STMT (name
) = phi
;
2300 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2302 edge e
= (*phi_bb
->preds
)[i
];
2303 add_phi_arg (phi
, phi_arg
, e
, loc
);
2308 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2310 fputs ("Introducing new phi basis: ", dump_file
);
2311 print_gimple_stmt (dump_file
, phi
, 0, 0);
2317 /* Given a candidate C whose basis is hidden by at least one intervening
2318 phi, introduce a matching number of new phis to represent its basis
2319 adjusted by conditional increments along possible incoming paths. Then
2320 replace C as though it were an unconditional candidate, using the new
2324 replace_conditional_candidate (slsr_cand_t c
)
2326 tree basis_name
, name
;
2329 double_int stride
, bump
;
2331 /* Look up the LHS SSA name from C's basis. This will be the
2332 RHS1 of the adds we will introduce to create new phi arguments. */
2333 basis
= lookup_cand (c
->basis
);
2334 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2336 /* Create a new phi statement which will represent C's true basis
2337 after the transformation is complete. */
2338 loc
= gimple_location (c
->cand_stmt
);
2339 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2340 basis_name
, loc
, KNOWN_STRIDE
);
2341 /* Replace C with an add of the new basis phi and a constant. */
2342 stride
= tree_to_double_int (c
->stride
);
2343 bump
= c
->index
* stride
;
2345 replace_mult_candidate (c
, name
, bump
);
2348 /* Compute the expected costs of inserting basis adjustments for
2349 candidate C with phi-definition PHI. The cost of inserting
2350 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2351 which are themselves phi results, recursively calculate costs
2352 for those phis as well. */
2355 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2359 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2361 /* If we work our way back to a phi that isn't dominated by the hidden
2362 basis, this isn't a candidate for replacement. Indicate this by
2363 returning an unreasonably high cost. It's not easy to detect
2364 these situations when determining the basis, so we defer the
2365 decision until now. */
2366 basic_block phi_bb
= gimple_bb (phi
);
2367 slsr_cand_t basis
= lookup_cand (c
->basis
);
2368 basic_block basis_bb
= gimple_bb (basis
->cand_stmt
);
2370 if (phi_bb
== basis_bb
|| !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
2371 return COST_INFINITE
;
2373 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2375 tree arg
= gimple_phi_arg_def (phi
, i
);
2377 if (arg
!= phi_cand
->base_expr
)
2379 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2381 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2382 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2385 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2387 if (arg_cand
->index
!= c
->index
)
2388 cost
+= one_add_cost
;
2396 /* For candidate C, each sibling of candidate C, and each dependent of
2397 candidate C, determine whether the candidate is dependent upon a
2398 phi that hides its basis. If not, replace the candidate unconditionally.
2399 Otherwise, determine whether the cost of introducing compensation code
2400 for the candidate is offset by the gains from strength reduction. If
2401 so, replace the candidate and introduce the compensation code. */
2404 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2406 if (phi_dependent_cand_p (c
))
2408 if (c
->kind
== CAND_MULT
)
2410 /* A candidate dependent upon a phi will replace a multiply by
2411 a constant with an add, and will insert at most one add for
2412 each phi argument. Add these costs with the potential dead-code
2413 savings to determine profitability. */
2414 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2415 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2416 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2417 tree phi_result
= gimple_phi_result (phi
);
2418 int one_add_cost
= add_cost (speed
,
2419 TYPE_MODE (TREE_TYPE (phi_result
)));
2420 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2421 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2423 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2425 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2426 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2427 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2428 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2429 fprintf (dump_file
, " cost = %d\n", cost
);
2430 if (cost
<= COST_NEUTRAL
)
2431 fputs (" Replacing...\n", dump_file
);
2433 fputs (" Not replaced.\n", dump_file
);
2436 if (cost
<= COST_NEUTRAL
)
2437 replace_conditional_candidate (c
);
2441 replace_unconditional_candidate (c
);
2444 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2447 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2450 /* Count the number of candidates in the tree rooted at C that have
2451 not already been replaced under other interpretations. */
2454 count_candidates (slsr_cand_t c
)
2456 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2459 count
+= count_candidates (lookup_cand (c
->sibling
));
2462 count
+= count_candidates (lookup_cand (c
->dependent
));
2467 /* Increase the count of INCREMENT by one in the increment vector.
2468 INCREMENT is associated with candidate C. If INCREMENT is to be
2469 conditionally executed as part of a conditional candidate replacement,
2470 IS_PHI_ADJUST is true, otherwise false. If an initializer
2471 T_0 = stride * I is provided by a candidate that dominates all
2472 candidates with the same increment, also record T_0 for subsequent use. */
2475 record_increment (slsr_cand_t c
, double_int increment
, bool is_phi_adjust
)
2480 /* Treat increments that differ only in sign as identical so as to
2481 share initializers, unless we are generating pointer arithmetic. */
2482 if (!address_arithmetic_p
&& increment
.is_negative ())
2483 increment
= -increment
;
2485 for (i
= 0; i
< incr_vec_len
; i
++)
2487 if (incr_vec
[i
].incr
== increment
)
2489 incr_vec
[i
].count
++;
2492 /* If we previously recorded an initializer that doesn't
2493 dominate this candidate, it's not going to be useful to
2495 if (incr_vec
[i
].initializer
2496 && !dominated_by_p (CDI_DOMINATORS
,
2497 gimple_bb (c
->cand_stmt
),
2498 incr_vec
[i
].init_bb
))
2500 incr_vec
[i
].initializer
= NULL_TREE
;
2501 incr_vec
[i
].init_bb
= NULL
;
2508 if (!found
&& incr_vec_len
< MAX_INCR_VEC_LEN
- 1)
2510 /* The first time we see an increment, create the entry for it.
2511 If this is the root candidate which doesn't have a basis, set
2512 the count to zero. We're only processing it so it can possibly
2513 provide an initializer for other candidates. */
2514 incr_vec
[incr_vec_len
].incr
= increment
;
2515 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2516 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2518 /* Optimistically record the first occurrence of this increment
2519 as providing an initializer (if it does); we will revise this
2520 opinion later if it doesn't dominate all other occurrences.
2521 Exception: increments of -1, 0, 1 never need initializers;
2522 and phi adjustments don't ever provide initializers. */
2523 if (c
->kind
== CAND_ADD
2525 && c
->index
== increment
2526 && (increment
.sgt (double_int_one
)
2527 || increment
.slt (double_int_minus_one
))
2528 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2529 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2531 tree t0
= NULL_TREE
;
2532 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2533 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2534 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2536 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2539 && SSA_NAME_DEF_STMT (t0
)
2540 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2542 incr_vec
[incr_vec_len
].initializer
= t0
;
2543 incr_vec
[incr_vec_len
++].init_bb
2544 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2548 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2549 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2554 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2555 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2560 /* Given phi statement PHI that hides a candidate from its BASIS, find
2561 the increments along each incoming arc (recursively handling additional
2562 phis that may be present) and record them. These increments are the
2563 difference in index between the index-adjusting statements and the
2564 index of the basis. */
2567 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2570 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2572 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2574 tree arg
= gimple_phi_arg_def (phi
, i
);
2576 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2578 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2580 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2581 record_phi_increments (basis
, arg_def
);
2584 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2585 double_int diff
= arg_cand
->index
- basis
->index
;
2586 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2592 /* Determine how many times each unique increment occurs in the set
2593 of candidates rooted at C's parent, recording the data in the
2594 increment vector. For each unique increment I, if an initializer
2595 T_0 = stride * I is provided by a candidate that dominates all
2596 candidates with the same increment, also record T_0 for subsequent
2600 record_increments (slsr_cand_t c
)
2602 if (!cand_already_replaced (c
))
2604 if (!phi_dependent_cand_p (c
))
2605 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2608 /* A candidate with a basis hidden by a phi will have one
2609 increment for its relationship to the index represented by
2610 the phi, and potentially additional increments along each
2611 incoming edge. For the root of the dependency tree (which
2612 has no basis), process just the initial index in case it has
2613 an initializer that can be used by subsequent candidates. */
2614 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2617 record_phi_increments (lookup_cand (c
->basis
),
2618 lookup_cand (c
->def_phi
)->cand_stmt
);
2623 record_increments (lookup_cand (c
->sibling
));
2626 record_increments (lookup_cand (c
->dependent
));
2629 /* Add up and return the costs of introducing add statements that
2630 require the increment INCR on behalf of candidate C and phi
2631 statement PHI. Accumulate into *SAVINGS the potential savings
2632 from removing existing statements that feed PHI and have no other
2636 phi_incr_cost (slsr_cand_t c
, double_int incr
, gimple phi
, int *savings
)
2640 slsr_cand_t basis
= lookup_cand (c
->basis
);
2641 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2643 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2645 tree arg
= gimple_phi_arg_def (phi
, i
);
2647 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2649 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2651 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2653 int feeding_savings
= 0;
2654 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2655 if (has_single_use (gimple_phi_result (arg_def
)))
2656 *savings
+= feeding_savings
;
2660 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2661 double_int diff
= arg_cand
->index
- basis
->index
;
2665 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2666 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2667 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2668 if (has_single_use (lhs
))
2669 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2678 /* Return the first candidate in the tree rooted at C that has not
2679 already been replaced, favoring siblings over dependents. */
2682 unreplaced_cand_in_tree (slsr_cand_t c
)
2684 if (!cand_already_replaced (c
))
2689 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2696 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2704 /* Return TRUE if the candidates in the tree rooted at C should be
2705 optimized for speed, else FALSE. We estimate this based on the block
2706 containing the most dominant candidate in the tree that has not yet
2710 optimize_cands_for_speed_p (slsr_cand_t c
)
2712 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2714 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2717 /* Add COST_IN to the lowest cost of any dependent path starting at
2718 candidate C or any of its siblings, counting only candidates along
2719 such paths with increment INCR. Assume that replacing a candidate
2720 reduces cost by REPL_SAVINGS. Also account for savings from any
2721 statements that would go dead. If COUNT_PHIS is true, include
2722 costs of introducing feeding statements for conditional candidates. */
2725 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2726 double_int incr
, bool count_phis
)
2728 int local_cost
, sib_cost
, savings
= 0;
2729 double_int cand_incr
= cand_abs_increment (c
);
2731 if (cand_already_replaced (c
))
2732 local_cost
= cost_in
;
2733 else if (incr
== cand_incr
)
2734 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2736 local_cost
= cost_in
- c
->dead_savings
;
2739 && phi_dependent_cand_p (c
)
2740 && !cand_already_replaced (c
))
2742 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2743 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2745 if (has_single_use (gimple_phi_result (phi
)))
2746 local_cost
-= savings
;
2750 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2751 lookup_cand (c
->dependent
), incr
,
2756 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2757 lookup_cand (c
->sibling
), incr
,
2759 local_cost
= MIN (local_cost
, sib_cost
);
2765 /* Compute the total savings that would accrue from all replacements
2766 in the candidate tree rooted at C, counting only candidates with
2767 increment INCR. Assume that replacing a candidate reduces cost
2768 by REPL_SAVINGS. Also account for savings from statements that
2772 total_savings (int repl_savings
, slsr_cand_t c
, double_int incr
,
2776 double_int cand_incr
= cand_abs_increment (c
);
2778 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2779 savings
+= repl_savings
+ c
->dead_savings
;
2782 && phi_dependent_cand_p (c
)
2783 && !cand_already_replaced (c
))
2785 int phi_savings
= 0;
2786 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2787 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2789 if (has_single_use (gimple_phi_result (phi
)))
2790 savings
+= phi_savings
;
2794 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2798 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2804 /* Use target-specific costs to determine and record which increments
2805 in the current candidate tree are profitable to replace, assuming
2806 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2809 One slight limitation here is that we don't account for the possible
2810 introduction of casts in some cases. See replace_one_candidate for
2811 the cases where these are introduced. This should probably be cleaned
2815 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
2819 for (i
= 0; i
< incr_vec_len
; i
++)
2821 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2823 /* If somehow this increment is bigger than a HWI, we won't
2824 be optimizing candidates that use it. And if the increment
2825 has a count of zero, nothing will be done with it. */
2826 if (!incr_vec
[i
].incr
.fits_shwi () || !incr_vec
[i
].count
)
2827 incr_vec
[i
].cost
= COST_INFINITE
;
2829 /* Increments of 0, 1, and -1 are always profitable to replace,
2830 because they always replace a multiply or add with an add or
2831 copy, and may cause one or more existing instructions to go
2832 dead. Exception: -1 can't be assumed to be profitable for
2833 pointer addition. */
2837 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2838 != POINTER_PLUS_EXPR
)))
2839 incr_vec
[i
].cost
= COST_NEUTRAL
;
2841 /* FORNOW: If we need to add an initializer, give up if a cast from
2842 the candidate's type to its stride's type can lose precision.
2843 This could eventually be handled better by expressly retaining the
2844 result of a cast to a wider type in the stride. Example:
2849 _4 = x + _3; ADD: x + (10 * _1) : int
2851 _6 = x + _3; ADD: x + (15 * _1) : int
2853 Right now replacing _6 would cause insertion of an initializer
2854 of the form "short int T = _1 * 5;" followed by a cast to
2855 int, which could overflow incorrectly. Had we recorded _2 or
2856 (int)_1 as the stride, this wouldn't happen. However, doing
2857 this breaks other opportunities, so this will require some
2859 else if (!incr_vec
[i
].initializer
2860 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2861 && !legal_cast_p_1 (first_dep
->stride
,
2862 gimple_assign_lhs (first_dep
->cand_stmt
)))
2864 incr_vec
[i
].cost
= COST_INFINITE
;
2866 /* If we need to add an initializer, make sure we don't introduce
2867 a multiply by a pointer type, which can happen in certain cast
2868 scenarios. FIXME: When cleaning up these cast issues, we can
2869 afford to introduce the multiply provided we cast out to an
2870 unsigned int of appropriate size. */
2871 else if (!incr_vec
[i
].initializer
2872 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2873 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2875 incr_vec
[i
].cost
= COST_INFINITE
;
2877 /* For any other increment, if this is a multiply candidate, we
2878 must introduce a temporary T and initialize it with
2879 T_0 = stride * increment. When optimizing for speed, walk the
2880 candidate tree to calculate the best cost reduction along any
2881 path; if it offsets the fixed cost of inserting the initializer,
2882 replacing the increment is profitable. When optimizing for
2883 size, instead calculate the total cost reduction from replacing
2884 all candidates with this increment. */
2885 else if (first_dep
->kind
== CAND_MULT
)
2887 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2888 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2890 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2891 incr_vec
[i
].incr
, COUNT_PHIS
);
2893 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2896 incr_vec
[i
].cost
= cost
;
2899 /* If this is an add candidate, the initializer may already
2900 exist, so only calculate the cost of the initializer if it
2901 doesn't. We are replacing one add with another here, so the
2902 known replacement savings is zero. We will account for removal
2903 of dead instructions in lowest_cost_path or total_savings. */
2907 if (!incr_vec
[i
].initializer
)
2908 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2911 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2914 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2917 incr_vec
[i
].cost
= cost
;
2922 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2923 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2924 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2925 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2926 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2929 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2930 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2946 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2948 /* If both candidates are in the same block, the earlier
2950 if (bb1
== ncd
&& bb2
== ncd
)
2952 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2958 /* Otherwise, if one of them produced a candidate in the
2959 dominator, that one wins. */
2960 else if (bb1
== ncd
)
2963 else if (bb2
== ncd
)
2966 /* If neither matches the dominator, neither wins. */
2973 /* Consider all candidates that feed PHI. Find the nearest common
2974 dominator of those candidates requiring the given increment INCR.
2975 Further find and return the nearest common dominator of this result
2976 with block NCD. If the returned block contains one or more of the
2977 candidates, return the earliest candidate in the block in *WHERE. */
2980 ncd_with_phi (slsr_cand_t c
, double_int incr
, gimple phi
,
2981 basic_block ncd
, slsr_cand_t
*where
)
2984 slsr_cand_t basis
= lookup_cand (c
->basis
);
2985 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2987 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2989 tree arg
= gimple_phi_arg_def (phi
, i
);
2991 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2993 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2995 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2996 ncd
= ncd_with_phi (c
, incr
, arg_def
, ncd
, where
);
2999 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3000 double_int diff
= arg_cand
->index
- basis
->index
;
3002 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
3003 ncd
= ncd_for_two_cands (ncd
, gimple_bb (arg_cand
->cand_stmt
),
3004 *where
, arg_cand
, where
);
3012 /* Consider the candidate C together with any candidates that feed
3013 C's phi dependence (if any). Find and return the nearest common
3014 dominator of those candidates requiring the given increment INCR.
3015 If the returned block contains one or more of the candidates,
3016 return the earliest candidate in the block in *WHERE. */
3019 ncd_of_cand_and_phis (slsr_cand_t c
, double_int incr
, slsr_cand_t
*where
)
3021 basic_block ncd
= NULL
;
3023 if (cand_abs_increment (c
) == incr
)
3025 ncd
= gimple_bb (c
->cand_stmt
);
3029 if (phi_dependent_cand_p (c
))
3030 ncd
= ncd_with_phi (c
, incr
, lookup_cand (c
->def_phi
)->cand_stmt
,
3036 /* Consider all candidates in the tree rooted at C for which INCR
3037 represents the required increment of C relative to its basis.
3038 Find and return the basic block that most nearly dominates all
3039 such candidates. If the returned block contains one or more of
3040 the candidates, return the earliest candidate in the block in
3044 nearest_common_dominator_for_cands (slsr_cand_t c
, double_int incr
,
3047 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
3048 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
3050 /* First find the NCD of all siblings and dependents. */
3052 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
3055 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
3057 if (!sib_ncd
&& !dep_ncd
)
3062 else if (sib_ncd
&& !dep_ncd
)
3064 new_where
= sib_where
;
3067 else if (dep_ncd
&& !sib_ncd
)
3069 new_where
= dep_where
;
3073 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
3074 dep_where
, &new_where
);
3076 /* If the candidate's increment doesn't match the one we're interested
3077 in (and nor do any increments for feeding defs of a phi-dependence),
3078 then the result depends only on siblings and dependents. */
3079 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
3081 if (!this_ncd
|| cand_already_replaced (c
))
3087 /* Otherwise, compare this candidate with the result from all siblings
3089 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
3094 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
3097 profitable_increment_p (unsigned index
)
3099 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
3102 /* For each profitable increment in the increment vector not equal to
3103 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3104 dominator of all statements in the candidate chain rooted at C
3105 that require that increment, and insert an initializer
3106 T_0 = stride * increment at that location. Record T_0 with the
3107 increment record. */
3110 insert_initializers (slsr_cand_t c
)
3114 for (i
= 0; i
< incr_vec_len
; i
++)
3117 slsr_cand_t where
= NULL
;
3119 tree stride_type
, new_name
, incr_tree
;
3120 double_int incr
= incr_vec
[i
].incr
;
3122 if (!profitable_increment_p (i
)
3124 || (incr
.is_minus_one ()
3125 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
3129 /* We may have already identified an existing initializer that
3131 if (incr_vec
[i
].initializer
)
3133 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3135 fputs ("Using existing initializer: ", dump_file
);
3136 print_gimple_stmt (dump_file
,
3137 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
3143 /* Find the block that most closely dominates all candidates
3144 with this increment. If there is at least one candidate in
3145 that block, the earliest one will be returned in WHERE. */
3146 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
3148 /* Create a new SSA name to hold the initializer's value. */
3149 stride_type
= TREE_TYPE (c
->stride
);
3150 new_name
= make_temp_ssa_name (stride_type
, NULL
, "slsr");
3151 incr_vec
[i
].initializer
= new_name
;
3153 /* Create the initializer and insert it in the latest possible
3154 dominating position. */
3155 incr_tree
= double_int_to_tree (stride_type
, incr
);
3156 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
3157 c
->stride
, incr_tree
);
3160 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
3161 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3162 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
3166 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
3167 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
3169 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
3170 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3172 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
3174 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
3177 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3179 fputs ("Inserting initializer: ", dump_file
);
3180 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3185 /* Return TRUE iff all required increments for candidates feeding PHI
3186 are profitable to replace on behalf of candidate C. */
3189 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3192 slsr_cand_t basis
= lookup_cand (c
->basis
);
3193 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3195 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3197 tree arg
= gimple_phi_arg_def (phi
, i
);
3199 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3201 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3203 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3205 if (!all_phi_incrs_profitable (c
, arg_def
))
3211 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3212 double_int increment
= arg_cand
->index
- basis
->index
;
3214 if (!address_arithmetic_p
&& increment
.is_negative ())
3215 increment
= -increment
;
3217 j
= incr_vec_index (increment
);
3219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3221 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3223 print_gimple_stmt (dump_file
, phi
, 0, 0);
3224 fputs (" increment: ", dump_file
);
3225 dump_double_int (dump_file
, increment
, false);
3228 "\n Not replaced; incr_vec overflow.\n");
3230 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3231 if (profitable_increment_p (j
))
3232 fputs (" Replacing...\n", dump_file
);
3234 fputs (" Not replaced.\n", dump_file
);
3238 if (j
< 0 || !profitable_increment_p (j
))
3247 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3248 type TO_TYPE, and insert it in front of the statement represented
3249 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3250 the new SSA name. */
3253 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
, tree from_expr
)
3257 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3259 cast_lhs
= make_temp_ssa_name (to_type
, NULL
, "slsr");
3260 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
3261 from_expr
, NULL_TREE
);
3262 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3263 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3265 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3267 fputs (" Inserting: ", dump_file
);
3268 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3274 /* Replace the RHS of the statement represented by candidate C with
3275 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3276 leave C unchanged or just interchange its operands. The original
3277 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3278 If the replacement was made and we are doing a details dump,
3279 return the revised statement, else NULL. */
3282 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3283 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3286 if (new_code
!= old_code
3287 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3288 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3289 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3290 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3292 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3293 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3294 update_stmt (gsi_stmt (gsi
));
3295 c
->cand_stmt
= gsi_stmt (gsi
);
3297 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3298 return gsi_stmt (gsi
);
3301 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3302 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3307 /* Strength-reduce the statement represented by candidate C by replacing
3308 it with an equivalent addition or subtraction. I is the index into
3309 the increment vector identifying C's increment. NEW_VAR is used to
3310 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3311 is the rhs1 to use in creating the add/subtract. */
3314 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree basis_name
)
3316 gimple stmt_to_print
= NULL
;
3317 tree orig_rhs1
, orig_rhs2
;
3319 enum tree_code orig_code
, repl_code
;
3320 double_int cand_incr
;
3322 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3323 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3324 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3325 cand_incr
= cand_increment (c
);
3327 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3329 fputs ("Replacing: ", dump_file
);
3330 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3331 stmt_to_print
= c
->cand_stmt
;
3334 if (address_arithmetic_p
)
3335 repl_code
= POINTER_PLUS_EXPR
;
3337 repl_code
= PLUS_EXPR
;
3339 /* If the increment has an initializer T_0, replace the candidate
3340 statement with an add of the basis name and the initializer. */
3341 if (incr_vec
[i
].initializer
)
3343 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3344 tree orig_type
= TREE_TYPE (orig_rhs2
);
3346 if (types_compatible_p (orig_type
, init_type
))
3347 rhs2
= incr_vec
[i
].initializer
;
3349 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3350 incr_vec
[i
].initializer
);
3352 if (incr_vec
[i
].incr
!= cand_incr
)
3354 gcc_assert (repl_code
== PLUS_EXPR
);
3355 repl_code
= MINUS_EXPR
;
3358 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3359 orig_code
, orig_rhs1
, orig_rhs2
,
3363 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3364 with a subtract of the stride from the basis name, a copy
3365 from the basis name, or an add of the stride to the basis
3366 name, respectively. It may be necessary to introduce a
3367 cast (or reuse an existing cast). */
3368 else if (cand_incr
.is_one ())
3370 tree stride_type
= TREE_TYPE (c
->stride
);
3371 tree orig_type
= TREE_TYPE (orig_rhs2
);
3373 if (types_compatible_p (orig_type
, stride_type
))
3376 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3378 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3379 orig_code
, orig_rhs1
, orig_rhs2
,
3383 else if (cand_incr
.is_minus_one ())
3385 tree stride_type
= TREE_TYPE (c
->stride
);
3386 tree orig_type
= TREE_TYPE (orig_rhs2
);
3387 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3389 if (types_compatible_p (orig_type
, stride_type
))
3392 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3394 if (orig_code
!= MINUS_EXPR
3395 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3396 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3398 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3399 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3400 update_stmt (gsi_stmt (gsi
));
3401 c
->cand_stmt
= gsi_stmt (gsi
);
3403 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3404 stmt_to_print
= gsi_stmt (gsi
);
3406 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3407 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3410 else if (cand_incr
.is_zero ())
3412 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3413 tree lhs_type
= TREE_TYPE (lhs
);
3414 tree basis_type
= TREE_TYPE (basis_name
);
3416 if (types_compatible_p (lhs_type
, basis_type
))
3418 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3419 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3420 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3421 gsi_replace (&gsi
, copy_stmt
, false);
3422 c
->cand_stmt
= copy_stmt
;
3424 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3425 stmt_to_print
= copy_stmt
;
3429 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3430 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
3433 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3434 gsi_replace (&gsi
, cast_stmt
, false);
3435 c
->cand_stmt
= cast_stmt
;
3437 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3438 stmt_to_print
= cast_stmt
;
3444 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3446 fputs ("With: ", dump_file
);
3447 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3448 fputs ("\n", dump_file
);
3452 /* For each candidate in the tree rooted at C, replace it with
3453 an increment if such has been shown to be profitable. */
3456 replace_profitable_candidates (slsr_cand_t c
)
3458 if (!cand_already_replaced (c
))
3460 double_int increment
= cand_abs_increment (c
);
3461 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3464 i
= incr_vec_index (increment
);
3466 /* Only process profitable increments. Nothing useful can be done
3467 to a cast or copy. */
3469 && profitable_increment_p (i
)
3470 && orig_code
!= MODIFY_EXPR
3471 && orig_code
!= NOP_EXPR
)
3473 if (phi_dependent_cand_p (c
))
3475 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3477 if (all_phi_incrs_profitable (c
, phi
))
3479 /* Look up the LHS SSA name from C's basis. This will be
3480 the RHS1 of the adds we will introduce to create new
3482 slsr_cand_t basis
= lookup_cand (c
->basis
);
3483 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3485 /* Create a new phi statement that will represent C's true
3486 basis after the transformation is complete. */
3487 location_t loc
= gimple_location (c
->cand_stmt
);
3488 tree name
= create_phi_basis (c
, phi
, basis_name
,
3489 loc
, UNKNOWN_STRIDE
);
3491 /* Replace C with an add of the new basis phi and the
3493 replace_one_candidate (c
, i
, name
);
3498 slsr_cand_t basis
= lookup_cand (c
->basis
);
3499 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3500 replace_one_candidate (c
, i
, basis_name
);
3506 replace_profitable_candidates (lookup_cand (c
->sibling
));
3509 replace_profitable_candidates (lookup_cand (c
->dependent
));
3512 /* Analyze costs of related candidates in the candidate vector,
3513 and make beneficial replacements. */
3516 analyze_candidates_and_replace (void)
3521 /* Each candidate that has a null basis and a non-null
3522 dependent is the root of a tree of related statements.
3523 Analyze each tree to determine a subset of those
3524 statements that can be replaced with maximum benefit. */
3525 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3527 slsr_cand_t first_dep
;
3529 if (c
->basis
!= 0 || c
->dependent
== 0)
3532 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3533 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3536 first_dep
= lookup_cand (c
->dependent
);
3538 /* If this is a chain of CAND_REFs, unconditionally replace
3539 each of them with a strength-reduced data reference. */
3540 if (c
->kind
== CAND_REF
)
3543 /* If the common stride of all related candidates is a known
3544 constant, each candidate without a phi-dependence can be
3545 profitably replaced. Each replaces a multiply by a single
3546 add, with the possibility that a feeding add also goes dead.
3547 A candidate with a phi-dependence is replaced only if the
3548 compensation code it requires is offset by the strength
3549 reduction savings. */
3550 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3551 replace_uncond_cands_and_profitable_phis (first_dep
);
3553 /* When the stride is an SSA name, it may still be profitable
3554 to replace some or all of the dependent candidates, depending
3555 on whether the introduced increments can be reused, or are
3556 less expensive to calculate than the replaced statements. */
3559 enum machine_mode mode
;
3562 /* Determine whether we'll be generating pointer arithmetic
3563 when replacing candidates. */
3564 address_arithmetic_p
= (c
->kind
== CAND_ADD
3565 && POINTER_TYPE_P (c
->cand_type
));
3567 /* If all candidates have already been replaced under other
3568 interpretations, nothing remains to be done. */
3569 if (!count_candidates (c
))
3572 /* Construct an array of increments for this candidate chain. */
3573 incr_vec
= XNEWVEC (incr_info
, MAX_INCR_VEC_LEN
);
3575 record_increments (c
);
3577 /* Determine which increments are profitable to replace. */
3578 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3579 speed
= optimize_cands_for_speed_p (c
);
3580 analyze_increments (first_dep
, mode
, speed
);
3582 /* Insert initializers of the form T_0 = stride * increment
3583 for use in profitable replacements. */
3584 insert_initializers (first_dep
);
3587 /* Perform the replacements. */
3588 replace_profitable_candidates (first_dep
);
3595 execute_strength_reduction (void)
3597 /* Create the obstack where candidates will reside. */
3598 gcc_obstack_init (&cand_obstack
);
3600 /* Allocate the candidate vector. */
3601 cand_vec
.create (128);
3603 /* Allocate the mapping from statements to candidate indices. */
3604 stmt_cand_map
= pointer_map_create ();
3606 /* Create the obstack where candidate chains will reside. */
3607 gcc_obstack_init (&chain_obstack
);
3609 /* Allocate the mapping from base expressions to candidate chains. */
3610 base_cand_map
.create (500);
3612 /* Allocate the mapping from bases to alternative bases. */
3613 alt_base_map
= pointer_map_create ();
3615 /* Initialize the loop optimizer. We need to detect flow across
3616 back edges, and this gives us dominator information as well. */
3617 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3619 /* Walk the CFG in predominator order looking for strength reduction
3621 find_candidates_dom_walker (CDI_DOMINATORS
)
3622 .walk (cfun
->cfg
->x_entry_block_ptr
);
3624 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3627 dump_cand_chains ();
3630 pointer_map_destroy (alt_base_map
);
3631 free_affine_expand_cache (&name_expansions
);
3633 /* Analyze costs and make appropriate replacements. */
3634 analyze_candidates_and_replace ();
3636 loop_optimizer_finalize ();
3637 base_cand_map
.dispose ();
3638 obstack_free (&chain_obstack
, NULL
);
3639 pointer_map_destroy (stmt_cand_map
);
3640 cand_vec
.release ();
3641 obstack_free (&cand_obstack
, NULL
);
3647 gate_strength_reduction (void)
3649 return flag_tree_slsr
;
3654 const pass_data pass_data_strength_reduction
=
3656 GIMPLE_PASS
, /* type */
3658 OPTGROUP_NONE
, /* optinfo_flags */
3659 true, /* has_gate */
3660 true, /* has_execute */
3661 TV_GIMPLE_SLSR
, /* tv_id */
3662 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3663 0, /* properties_provided */
3664 0, /* properties_destroyed */
3665 0, /* todo_flags_start */
3666 TODO_verify_ssa
, /* todo_flags_finish */
3669 class pass_strength_reduction
: public gimple_opt_pass
3672 pass_strength_reduction (gcc::context
*ctxt
)
3673 : gimple_opt_pass (pass_data_strength_reduction
, ctxt
)
3676 /* opt_pass methods: */
3677 bool gate () { return gate_strength_reduction (); }
3678 unsigned int execute () { return execute_strength_reduction (); }
3680 }; // class pass_strength_reduction
3685 make_pass_strength_reduction (gcc::context
*ctxt
)
3687 return new pass_strength_reduction (ctxt
);