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"
41 #include "basic-block.h"
42 #include "tree-pass.h"
44 #include "gimple-pretty-print.h"
47 #include "pointer-set.h"
50 #include "hash-table.h"
51 #include "wide-int-print.h"
54 /* Information about a strength reduction candidate. Each statement
55 in the candidate table represents an expression of one of the
56 following forms (the special case of CAND_REF will be described
59 (CAND_MULT) S1: X = (B + i) * S
60 (CAND_ADD) S1: X = B + (i * S)
62 Here X and B are SSA names, i is an integer constant, and S is
63 either an SSA name or a constant. We call B the "base," i the
64 "index", and S the "stride."
66 Any statement S0 that dominates S1 and is of the form:
68 (CAND_MULT) S0: Y = (B + i') * S
69 (CAND_ADD) S0: Y = B + (i' * S)
71 is called a "basis" for S1. In both cases, S1 may be replaced by
73 S1': X = Y + (i - i') * S,
75 where (i - i') * S is folded to the extent possible.
77 All gimple statements are visited in dominator order, and each
78 statement that may contribute to one of the forms of S1 above is
79 given at least one entry in the candidate table. Such statements
80 include addition, pointer addition, subtraction, multiplication,
81 negation, copies, and nontrivial type casts. If a statement may
82 represent more than one expression of the forms of S1 above,
83 multiple "interpretations" are stored in the table and chained
86 * An add of two SSA names may treat either operand as the base.
87 * A multiply of two SSA names, likewise.
88 * A copy or cast may be thought of as either a CAND_MULT with
89 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
91 Candidate records are allocated from an obstack. They are addressed
92 both from a hash table keyed on S1, and from a vector of candidate
93 pointers arranged in predominator order.
97 Currently we don't recognize:
102 as a strength reduction opportunity, even though this S1 would
103 also be replaceable by the S1' above. This can be added if it
104 comes up in practice.
106 Strength reduction in addressing
107 --------------------------------
108 There is another kind of candidate known as CAND_REF. A CAND_REF
109 describes a statement containing a memory reference having
110 complex addressing that might benefit from strength reduction.
111 Specifically, we are interested in references for which
112 get_inner_reference returns a base address, offset, and bitpos as
115 base: MEM_REF (T1, C1)
116 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
117 bitpos: C4 * BITS_PER_UNIT
119 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
120 arbitrary integer constants. Note that C2 may be zero, in which
121 case the offset will be MULT_EXPR (T2, C3).
123 When this pattern is recognized, the original memory reference
124 can be replaced with:
126 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
129 which distributes the multiply to allow constant folding. When
130 two or more addressing expressions can be represented by MEM_REFs
131 of this form, differing only in the constants C1, C2, and C4,
132 making this substitution produces more efficient addressing during
133 the RTL phases. When there are not at least two expressions with
134 the same values of T1, T2, and C3, there is nothing to be gained
137 Strength reduction of CAND_REFs uses the same infrastructure as
138 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
139 field, MULT_EXPR (T2, C3) in the stride (S) field, and
140 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
141 is thus another CAND_REF with the same B and S values. When at
142 least two CAND_REFs are chained together using the basis relation,
143 each of them is replaced as above, resulting in improved code
144 generation for addressing.
146 Conditional candidates
147 ======================
149 Conditional candidates are best illustrated with an example.
150 Consider the code sequence:
153 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
155 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
156 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
157 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
158 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
160 Here strength reduction is complicated by the uncertain value of x_2.
161 A legitimate transformation is:
170 (4) [x_2 = PHI <x_0, x_1>;]
171 (4a) t_2 = PHI <a_0, t_1>;
175 where the bracketed instructions may go dead.
177 To recognize this opportunity, we have to observe that statement (6)
178 has a "hidden basis" (2). The hidden basis is unlike a normal basis
179 in that the statement and the hidden basis have different base SSA
180 names (x_2 and x_0, respectively). The relationship is established
181 when a statement's base name (x_2) is defined by a phi statement (4),
182 each argument of which (x_0, x_1) has an identical "derived base name."
183 If the argument is defined by a candidate (as x_1 is by (3)) that is a
184 CAND_ADD having a stride of 1, the derived base name of the argument is
185 the base name of the candidate (x_0). Otherwise, the argument itself
186 is its derived base name (as is the case with argument x_0).
188 The hidden basis for statement (6) is the nearest dominating candidate
189 whose base name is the derived base name (x_0) of the feeding phi (4),
190 and whose stride is identical to that of the statement. We can then
191 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
192 allowing the final replacement of (6) by the strength-reduced (6r).
194 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
195 A CAND_PHI is not a candidate for replacement, but is maintained in the
196 candidate table to ease discovery of hidden bases. Any phi statement
197 whose arguments share a common derived base name is entered into the
198 table with the derived base name, an (arbitrary) index of zero, and a
199 stride of 1. A statement with a hidden basis can then be detected by
200 simply looking up its feeding phi definition in the candidate table,
201 extracting the derived base name, and searching for a basis in the
202 usual manner after substituting the derived base name.
204 Note that the transformation is only valid when the original phi and
205 the statements that define the phi's arguments are all at the same
206 position in the loop hierarchy. */
209 /* Index into the candidate vector, offset by 1. VECs are zero-based,
210 while cand_idx's are one-based, with zero indicating null. */
211 typedef unsigned cand_idx
;
213 /* The kind of candidate. */
224 /* The candidate statement S1. */
227 /* The base expression B: often an SSA name, but not always. */
233 /* The index constant i. */
236 /* The type of the candidate. This is normally the type of base_expr,
237 but casts may have occurred when combining feeding instructions.
238 A candidate can only be a basis for candidates of the same final type.
239 (For CAND_REFs, this is the type to be used for operand 1 of the
240 replacement MEM_REF.) */
243 /* The kind of candidate (CAND_MULT, etc.). */
246 /* Index of this candidate in the candidate vector. */
249 /* Index of the next candidate record for the same statement.
250 A statement may be useful in more than one way (e.g., due to
251 commutativity). So we can have multiple "interpretations"
253 cand_idx next_interp
;
255 /* Index of the basis statement S0, if any, in the candidate vector. */
258 /* First candidate for which this candidate is a basis, if one exists. */
261 /* Next candidate having the same basis as this one. */
264 /* If this is a conditional candidate, the CAND_PHI candidate
265 that defines the base SSA name B. */
268 /* Savings that can be expected from eliminating dead code if this
269 candidate is replaced. */
273 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
274 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
276 /* Pointers to candidates are chained together as part of a mapping
277 from base expressions to the candidates that use them. */
281 /* Base expression for the chain of candidates: often, but not
282 always, an SSA name. */
285 /* Pointer to a candidate. */
289 struct cand_chain_d
*next
;
293 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
294 typedef const struct cand_chain_d
*const_cand_chain_t
;
296 /* Information about a unique "increment" associated with candidates
297 having an SSA name for a stride. An increment is the difference
298 between the index of the candidate and the index of its basis,
299 i.e., (i - i') as discussed in the module commentary.
301 When we are not going to generate address arithmetic we treat
302 increments that differ only in sign as the same, allowing sharing
303 of the cost of initializers. The absolute value of the increment
304 is stored in the incr_info. */
308 /* The increment that relates a candidate to its basis. */
311 /* How many times the increment occurs in the candidate tree. */
314 /* Cost of replacing candidates using this increment. Negative and
315 zero costs indicate replacement should be performed. */
318 /* If this increment is profitable but is not -1, 0, or 1, it requires
319 an initializer T_0 = stride * incr to be found or introduced in the
320 nearest common dominator of all candidates. This field holds T_0
321 for subsequent use. */
324 /* If the initializer was found to already exist, this is the block
325 where it was found. */
329 typedef struct incr_info_d incr_info
, *incr_info_t
;
331 /* Candidates are maintained in a vector. If candidate X dominates
332 candidate Y, then X appears before Y in the vector; but the
333 converse does not necessarily hold. */
334 static vec
<slsr_cand_t
> cand_vec
;
348 enum phi_adjust_status
354 enum count_phis_status
360 /* Pointer map embodying a mapping from statements to candidates. */
361 static struct pointer_map_t
*stmt_cand_map
;
363 /* Obstack for candidates. */
364 static struct obstack cand_obstack
;
366 /* Obstack for candidate chains. */
367 static struct obstack chain_obstack
;
369 /* An array INCR_VEC of incr_infos is used during analysis of related
370 candidates having an SSA name for a stride. INCR_VEC_LEN describes
371 its current length. MAX_INCR_VEC_LEN is used to avoid costly
372 pathological cases. */
373 static incr_info_t incr_vec
;
374 static unsigned incr_vec_len
;
375 const int MAX_INCR_VEC_LEN
= 16;
377 /* For a chain of candidates with unknown stride, indicates whether or not
378 we must generate pointer arithmetic when replacing statements. */
379 static bool address_arithmetic_p
;
381 /* Forward function declarations. */
382 static slsr_cand_t
base_cand_from_table (tree
);
383 static tree
introduce_cast_before_cand (slsr_cand_t
, tree
, tree
);
385 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
388 lookup_cand (cand_idx idx
)
390 return cand_vec
[idx
- 1];
393 /* Helper for hashing a candidate chain header. */
395 struct cand_chain_hasher
: typed_noop_remove
<cand_chain
>
397 typedef cand_chain value_type
;
398 typedef cand_chain compare_type
;
399 static inline hashval_t
hash (const value_type
*);
400 static inline bool equal (const value_type
*, const compare_type
*);
404 cand_chain_hasher::hash (const value_type
*p
)
406 tree base_expr
= p
->base_expr
;
407 return iterative_hash_expr (base_expr
, 0);
411 cand_chain_hasher::equal (const value_type
*chain1
, const compare_type
*chain2
)
413 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
416 /* Hash table embodying a mapping from base exprs to chains of candidates. */
417 static hash_table
<cand_chain_hasher
> base_cand_map
;
419 /* Look in the candidate table for a CAND_PHI that defines BASE and
420 return it if found; otherwise return NULL. */
423 find_phi_def (tree base
)
427 if (TREE_CODE (base
) != SSA_NAME
)
430 c
= base_cand_from_table (base
);
432 if (!c
|| c
->kind
!= CAND_PHI
)
438 /* Helper routine for find_basis_for_candidate. May be called twice:
439 once for the candidate's base expr, and optionally again for the
440 candidate's phi definition. */
443 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
445 cand_chain mapping_key
;
447 slsr_cand_t basis
= NULL
;
449 // Limit potential of N^2 behavior for long candidate chains.
451 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
453 mapping_key
.base_expr
= base_expr
;
454 chain
= base_cand_map
.find (&mapping_key
);
456 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
458 slsr_cand_t one_basis
= chain
->cand
;
460 if (one_basis
->kind
!= c
->kind
461 || one_basis
->cand_stmt
== c
->cand_stmt
462 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
463 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
464 || !dominated_by_p (CDI_DOMINATORS
,
465 gimple_bb (c
->cand_stmt
),
466 gimple_bb (one_basis
->cand_stmt
)))
469 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
476 /* Use the base expr from candidate C to look for possible candidates
477 that can serve as a basis for C. Each potential basis must also
478 appear in a block that dominates the candidate statement and have
479 the same stride and type. If more than one possible basis exists,
480 the one with highest index in the vector is chosen; this will be
481 the most immediately dominating basis. */
484 find_basis_for_candidate (slsr_cand_t c
)
486 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
488 /* If a candidate doesn't have a basis using its base expression,
489 it may have a basis hidden by one or more intervening phis. */
490 if (!basis
&& c
->def_phi
)
492 basic_block basis_bb
, phi_bb
;
493 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
494 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
498 /* A hidden basis must dominate the phi-definition of the
499 candidate's base name. */
500 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
501 basis_bb
= gimple_bb (basis
->cand_stmt
);
503 if (phi_bb
== basis_bb
504 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
510 /* If we found a hidden basis, estimate additional dead-code
511 savings if the phi and its feeding statements can be removed. */
512 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
513 c
->dead_savings
+= phi_cand
->dead_savings
;
519 c
->sibling
= basis
->dependent
;
520 basis
->dependent
= c
->cand_num
;
521 return basis
->cand_num
;
527 /* Record a mapping from the base expression of C to C itself, indicating that
528 C may potentially serve as a basis using that base expression. */
531 record_potential_basis (slsr_cand_t c
)
536 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
537 node
->base_expr
= c
->base_expr
;
540 slot
= base_cand_map
.find_slot (node
, INSERT
);
544 cand_chain_t head
= (cand_chain_t
) (*slot
);
545 node
->next
= head
->next
;
552 /* Allocate storage for a new candidate and initialize its fields.
553 Attempt to find a basis for the candidate. */
556 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
557 const max_wide_int
&index
, tree stride
, tree ctype
,
560 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
566 c
->cand_type
= ctype
;
568 c
->cand_num
= cand_vec
.length () + 1;
572 c
->def_phi
= kind
== CAND_MULT
? find_phi_def (base
) : 0;
573 c
->dead_savings
= savings
;
575 cand_vec
.safe_push (c
);
577 if (kind
== CAND_PHI
)
580 c
->basis
= find_basis_for_candidate (c
);
582 record_potential_basis (c
);
587 /* Determine the target cost of statement GS when compiling according
591 stmt_cost (gimple gs
, bool speed
)
593 tree lhs
, rhs1
, rhs2
;
594 enum machine_mode lhs_mode
;
596 gcc_assert (is_gimple_assign (gs
));
597 lhs
= gimple_assign_lhs (gs
);
598 rhs1
= gimple_assign_rhs1 (gs
);
599 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
601 switch (gimple_assign_rhs_code (gs
))
604 rhs2
= gimple_assign_rhs2 (gs
);
606 if (tree_fits_shwi_p (rhs2
))
607 return mult_by_coeff_cost (tree_to_shwi (rhs2
), lhs_mode
, speed
);
609 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
610 return mul_cost (speed
, lhs_mode
);
613 case POINTER_PLUS_EXPR
:
615 return add_cost (speed
, lhs_mode
);
618 return neg_cost (speed
, lhs_mode
);
621 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
623 /* Note that we don't assign costs to copies that in most cases
633 /* Look up the defining statement for BASE_IN and return a pointer
634 to its candidate in the candidate table, if any; otherwise NULL.
635 Only CAND_ADD and CAND_MULT candidates are returned. */
638 base_cand_from_table (tree base_in
)
642 gimple def
= SSA_NAME_DEF_STMT (base_in
);
644 return (slsr_cand_t
) NULL
;
646 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
648 if (result
&& (*result
)->kind
!= CAND_REF
)
651 return (slsr_cand_t
) NULL
;
654 /* Add an entry to the statement-to-candidate mapping. */
657 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
659 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
664 /* Given PHI which contains a phi statement, determine whether it
665 satisfies all the requirements of a phi candidate. If so, create
666 a candidate. Note that a CAND_PHI never has a basis itself, but
667 is used to help find a basis for subsequent candidates. */
670 slsr_process_phi (gimple phi
, bool speed
)
673 tree arg0_base
= NULL_TREE
, base_type
;
675 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
676 unsigned savings
= 0;
678 /* A CAND_PHI requires each of its arguments to have the same
679 derived base name. (See the module header commentary for a
680 definition of derived base names.) Furthermore, all feeding
681 definitions must be in the same position in the loop hierarchy
684 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
686 slsr_cand_t arg_cand
;
687 tree arg
= gimple_phi_arg_def (phi
, i
);
688 tree derived_base_name
= NULL_TREE
;
689 gimple arg_stmt
= NULL
;
690 basic_block arg_bb
= NULL
;
692 if (TREE_CODE (arg
) != SSA_NAME
)
695 arg_cand
= base_cand_from_table (arg
);
699 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
701 if (!arg_cand
->next_interp
)
704 arg_cand
= lookup_cand (arg_cand
->next_interp
);
707 if (!integer_onep (arg_cand
->stride
))
710 derived_base_name
= arg_cand
->base_expr
;
711 arg_stmt
= arg_cand
->cand_stmt
;
712 arg_bb
= gimple_bb (arg_stmt
);
714 /* Gather potential dead code savings if the phi statement
715 can be removed later on. */
716 if (has_single_use (arg
))
718 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
719 savings
+= arg_cand
->dead_savings
;
721 savings
+= stmt_cost (arg_stmt
, speed
);
726 derived_base_name
= arg
;
728 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
729 arg_bb
= single_succ (ENTRY_BLOCK_PTR
);
731 gimple_bb (SSA_NAME_DEF_STMT (arg
));
734 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
738 arg0_base
= derived_base_name
;
739 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
743 /* Create the candidate. "alloc_cand_and_find_basis" is named
744 misleadingly for this case, as no basis will be sought for a
746 base_type
= TREE_TYPE (arg0_base
);
748 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
,
749 0, integer_one_node
, base_type
, savings
);
751 /* Add the candidate to the statement-candidate mapping. */
752 add_cand_for_stmt (phi
, c
);
755 /* Given PBASE which is a pointer to tree, look up the defining
756 statement for it and check whether the candidate is in the
759 X = B + (1 * S), S is integer constant
760 X = B + (i * S), S is integer one
762 If so, set PBASE to the candidate's base_expr and return double
764 Otherwise, just return double int zero. */
767 backtrace_base_for_ref (tree
*pbase
)
769 tree base_in
= *pbase
;
770 slsr_cand_t base_cand
;
772 STRIP_NOPS (base_in
);
773 if (TREE_CODE (base_in
) != SSA_NAME
)
774 return tree_to_double_int (integer_zero_node
);
776 base_cand
= base_cand_from_table (base_in
);
778 while (base_cand
&& base_cand
->kind
!= CAND_PHI
)
780 if (base_cand
->kind
== CAND_ADD
781 && base_cand
->index
.is_one ()
782 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
784 /* X = B + (1 * S), S is integer constant. */
785 *pbase
= base_cand
->base_expr
;
786 return tree_to_double_int (base_cand
->stride
);
788 else if (base_cand
->kind
== CAND_ADD
789 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
790 && integer_onep (base_cand
->stride
))
792 /* X = B + (i * S), S is integer one. */
793 *pbase
= base_cand
->base_expr
;
794 return base_cand
->index
;
797 if (base_cand
->next_interp
)
798 base_cand
= lookup_cand (base_cand
->next_interp
);
803 return tree_to_double_int (integer_zero_node
);
806 /* Look for the following pattern:
808 *PBASE: MEM_REF (T1, C1)
810 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
812 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
814 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
816 *PINDEX: C4 * BITS_PER_UNIT
818 If not present, leave the input values unchanged and return FALSE.
819 Otherwise, modify the input values as follows and return TRUE:
822 *POFFSET: MULT_EXPR (T2, C3)
823 *PINDEX: C1 + (C2 * C3) + C4
825 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
826 will be further restructured to:
829 *POFFSET: MULT_EXPR (T2', C3)
830 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
833 restructure_reference (tree
*pbase
, tree
*poffset
, max_wide_int
*pindex
,
836 tree base
= *pbase
, offset
= *poffset
;
837 max_wide_int index
= *pindex
;
838 tree mult_op0
, t1
, t2
, type
;
839 max_wide_int c1
, c2
, c3
, c4
, c5
;
843 || TREE_CODE (base
) != MEM_REF
844 || TREE_CODE (offset
) != MULT_EXPR
845 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
846 || wi::umod_floor (index
, BITS_PER_UNIT
) != 0)
849 t1
= TREE_OPERAND (base
, 0);
850 c1
= max_wide_int::from (mem_ref_offset (base
), SIGNED
);
851 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
853 mult_op0
= TREE_OPERAND (offset
, 0);
854 c3
= TREE_OPERAND (offset
, 1);
856 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
858 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
860 t2
= TREE_OPERAND (mult_op0
, 0);
861 c2
= TREE_OPERAND (mult_op0
, 1);
866 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
868 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
870 t2
= TREE_OPERAND (mult_op0
, 0);
871 c2
= -(max_wide_int
)TREE_OPERAND (mult_op0
, 1);
882 c4
= wi::udiv_floor (index
, BITS_PER_UNIT
);
883 c5
= backtrace_base_for_ref (&t2
);
886 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, fold_convert (sizetype
, t2
),
887 wide_int_to_tree (sizetype
, c3
));
888 *pindex
= c1
+ c2
* c3
+ c4
+ c5
* c3
;
894 /* Given GS which contains a data reference, create a CAND_REF entry in
895 the candidate table and attempt to find a basis. */
898 slsr_process_ref (gimple gs
)
900 tree ref_expr
, base
, offset
, type
;
901 HOST_WIDE_INT bitsize
, bitpos
;
902 enum machine_mode mode
;
903 int unsignedp
, volatilep
;
907 if (gimple_vdef (gs
))
908 ref_expr
= gimple_assign_lhs (gs
);
910 ref_expr
= gimple_assign_rhs1 (gs
);
912 if (!handled_component_p (ref_expr
)
913 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
914 || (TREE_CODE (ref_expr
) == COMPONENT_REF
915 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
918 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
919 &unsignedp
, &volatilep
, false);
922 if (!restructure_reference (&base
, &offset
, &index
, &type
))
925 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
928 /* Add the candidate to the statement-candidate mapping. */
929 add_cand_for_stmt (gs
, c
);
932 /* Create a candidate entry for a statement GS, where GS multiplies
933 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
934 about the two SSA names into the new candidate. Return the new
938 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
940 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
942 unsigned savings
= 0;
944 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
946 /* Look at all interpretations of the base candidate, if necessary,
947 to find information to propagate into this candidate. */
948 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
951 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
957 base
= base_cand
->base_expr
;
958 index
= base_cand
->index
;
960 ctype
= base_cand
->cand_type
;
961 if (has_single_use (base_in
))
962 savings
= (base_cand
->dead_savings
963 + stmt_cost (base_cand
->cand_stmt
, speed
));
965 else if (base_cand
->kind
== CAND_ADD
966 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
968 /* Y = B + (i' * S), S constant
970 ============================
971 X = B + ((i' * S) * Z) */
972 base
= base_cand
->base_expr
;
973 index
= base_cand
->index
* base_cand
->stride
;
975 ctype
= base_cand
->cand_type
;
976 if (has_single_use (base_in
))
977 savings
= (base_cand
->dead_savings
978 + stmt_cost (base_cand
->cand_stmt
, speed
));
981 if (base_cand
->next_interp
)
982 base_cand
= lookup_cand (base_cand
->next_interp
);
989 /* No interpretations had anything useful to propagate, so
990 produce X = (Y + 0) * Z. */
994 ctype
= TREE_TYPE (base_in
);
997 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1002 /* Create a candidate entry for a statement GS, where GS multiplies
1003 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1004 information about BASE_IN into the new candidate. Return the new
1008 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1010 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1011 max_wide_int index
, temp
;
1012 unsigned savings
= 0;
1014 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1016 /* Look at all interpretations of the base candidate, if necessary,
1017 to find information to propagate into this candidate. */
1018 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1020 if (base_cand
->kind
== CAND_MULT
1021 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1023 /* Y = (B + i') * S, S constant
1025 ============================
1026 X = (B + i') * (S * c) */
1027 base
= base_cand
->base_expr
;
1028 index
= base_cand
->index
;
1029 temp
= wi::mul (base_cand
->stride
, stride_in
);
1030 stride
= wide_int_to_tree (TREE_TYPE (stride_in
), temp
);
1031 ctype
= base_cand
->cand_type
;
1032 if (has_single_use (base_in
))
1033 savings
= (base_cand
->dead_savings
1034 + stmt_cost (base_cand
->cand_stmt
, speed
));
1036 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
1040 ===========================
1042 base
= base_cand
->base_expr
;
1043 index
= base_cand
->index
;
1045 ctype
= base_cand
->cand_type
;
1046 if (has_single_use (base_in
))
1047 savings
= (base_cand
->dead_savings
1048 + stmt_cost (base_cand
->cand_stmt
, speed
));
1050 else if (base_cand
->kind
== CAND_ADD
1051 && base_cand
->index
== 1
1052 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1054 /* Y = B + (1 * S), S constant
1056 ===========================
1058 base
= base_cand
->base_expr
;
1059 index
= base_cand
->stride
;
1061 ctype
= base_cand
->cand_type
;
1062 if (has_single_use (base_in
))
1063 savings
= (base_cand
->dead_savings
1064 + stmt_cost (base_cand
->cand_stmt
, speed
));
1067 if (base_cand
->next_interp
)
1068 base_cand
= lookup_cand (base_cand
->next_interp
);
1075 /* No interpretations had anything useful to propagate, so
1076 produce X = (Y + 0) * c. */
1080 ctype
= TREE_TYPE (base_in
);
1083 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1088 /* Given GS which is a multiply of scalar integers, make an appropriate
1089 entry in the candidate table. If this is a multiply of two SSA names,
1090 create two CAND_MULT interpretations and attempt to find a basis for
1091 each of them. Otherwise, create a single CAND_MULT and attempt to
1095 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1099 /* If this is a multiply of an SSA name with itself, it is highly
1100 unlikely that we will get a strength reduction opportunity, so
1101 don't record it as a candidate. This simplifies the logic for
1102 finding a basis, so if this is removed that must be considered. */
1106 if (TREE_CODE (rhs2
) == SSA_NAME
)
1108 /* Record an interpretation of this statement in the candidate table
1109 assuming RHS1 is the base expression and RHS2 is the stride. */
1110 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1112 /* Add the first interpretation to the statement-candidate mapping. */
1113 add_cand_for_stmt (gs
, c
);
1115 /* Record another interpretation of this statement assuming RHS1
1116 is the stride and RHS2 is the base expression. */
1117 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1118 c
->next_interp
= c2
->cand_num
;
1122 /* Record an interpretation for the multiply-immediate. */
1123 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1125 /* Add the interpretation to the statement-candidate mapping. */
1126 add_cand_for_stmt (gs
, c
);
1130 /* Create a candidate entry for a statement GS, where GS adds two
1131 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1132 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1133 information about the two SSA names into the new candidate.
1134 Return the new candidate. */
1137 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1138 bool subtract_p
, bool speed
)
1140 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1142 unsigned savings
= 0;
1144 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1145 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1147 /* The most useful transformation is a multiply-immediate feeding
1148 an add or subtract. Look for that first. */
1149 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1151 if (addend_cand
->kind
== CAND_MULT
1152 && addend_cand
->index
== 0
1153 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1155 /* Z = (B + 0) * S, S constant
1157 ===========================
1158 X = Y + ((+/-1 * S) * B) */
1160 index
= addend_cand
->stride
;
1163 stride
= addend_cand
->base_expr
;
1164 ctype
= TREE_TYPE (base_in
);
1165 if (has_single_use (addend_in
))
1166 savings
= (addend_cand
->dead_savings
1167 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1170 if (addend_cand
->next_interp
)
1171 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1176 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1178 if (base_cand
->kind
== CAND_ADD
1179 && (base_cand
->index
== 0
1180 || operand_equal_p (base_cand
->stride
,
1181 integer_zero_node
, 0)))
1183 /* Y = B + (i' * S), i' * S = 0
1185 ============================
1186 X = B + (+/-1 * Z) */
1187 base
= base_cand
->base_expr
;
1188 index
= subtract_p
? -1 : 1;
1190 ctype
= base_cand
->cand_type
;
1191 if (has_single_use (base_in
))
1192 savings
= (base_cand
->dead_savings
1193 + stmt_cost (base_cand
->cand_stmt
, speed
));
1195 else if (subtract_p
)
1197 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1199 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1201 if (subtrahend_cand
->kind
== CAND_MULT
1202 && subtrahend_cand
->index
== 0
1203 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1205 /* Z = (B + 0) * S, S constant
1207 ===========================
1208 Value: X = Y + ((-1 * S) * B) */
1210 index
= subtrahend_cand
->stride
;
1212 stride
= subtrahend_cand
->base_expr
;
1213 ctype
= TREE_TYPE (base_in
);
1214 if (has_single_use (addend_in
))
1215 savings
= (subtrahend_cand
->dead_savings
1216 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1219 if (subtrahend_cand
->next_interp
)
1220 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1222 subtrahend_cand
= NULL
;
1226 if (base_cand
->next_interp
)
1227 base_cand
= lookup_cand (base_cand
->next_interp
);
1234 /* No interpretations had anything useful to propagate, so
1235 produce X = Y + (1 * Z). */
1237 index
= subtract_p
? -1 : 1;
1239 ctype
= TREE_TYPE (base_in
);
1242 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1247 /* Create a candidate entry for a statement GS, where GS adds SSA
1248 name BASE_IN to constant INDEX_IN. Propagate any known information
1249 about BASE_IN into the new candidate. Return the new candidate. */
1252 create_add_imm_cand (gimple gs
, tree base_in
, max_wide_int index_in
, bool speed
)
1254 enum cand_kind kind
= CAND_ADD
;
1255 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1256 max_wide_int index
, multiple
;
1257 unsigned savings
= 0;
1259 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1261 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1263 signop sign
= TYPE_SIGN (TREE_TYPE (base_cand
->stride
));
1265 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1266 && wi::multiple_of_p (index_in
, base_cand
->stride
, sign
, &multiple
))
1268 /* Y = (B + i') * S, S constant, c = kS for some integer k
1270 ============================
1271 X = (B + (i'+ k)) * S
1273 Y = B + (i' * S), S constant, c = kS for some integer k
1275 ============================
1276 X = (B + (i'+ k)) * S */
1277 kind
= base_cand
->kind
;
1278 base
= base_cand
->base_expr
;
1279 index
= base_cand
->index
+ multiple
;
1280 stride
= base_cand
->stride
;
1281 ctype
= base_cand
->cand_type
;
1282 if (has_single_use (base_in
))
1283 savings
= (base_cand
->dead_savings
1284 + stmt_cost (base_cand
->cand_stmt
, speed
));
1287 if (base_cand
->next_interp
)
1288 base_cand
= lookup_cand (base_cand
->next_interp
);
1295 /* No interpretations had anything useful to propagate, so
1296 produce X = Y + (c * 1). */
1300 stride
= integer_one_node
;
1301 ctype
= TREE_TYPE (base_in
);
1304 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1309 /* Given GS which is an add or subtract of scalar integers or pointers,
1310 make at least one appropriate entry in the candidate table. */
1313 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1315 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1316 slsr_cand_t c
= NULL
, c2
;
1318 if (TREE_CODE (rhs2
) == SSA_NAME
)
1320 /* First record an interpretation assuming RHS1 is the base expression
1321 and RHS2 is the stride. But it doesn't make sense for the
1322 stride to be a pointer, so don't record a candidate in that case. */
1323 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1325 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1327 /* Add the first interpretation to the statement-candidate
1329 add_cand_for_stmt (gs
, c
);
1332 /* If the two RHS operands are identical, or this is a subtract,
1334 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1337 /* Otherwise, record another interpretation assuming RHS2 is the
1338 base expression and RHS1 is the stride, again provided that the
1339 stride is not a pointer. */
1340 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1342 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1344 c
->next_interp
= c2
->cand_num
;
1346 add_cand_for_stmt (gs
, c2
);
1353 /* Record an interpretation for the add-immediate. */
1358 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1360 /* Add the interpretation to the statement-candidate mapping. */
1361 add_cand_for_stmt (gs
, c
);
1365 /* Given GS which is a negate of a scalar integer, make an appropriate
1366 entry in the candidate table. A negate is equivalent to a multiply
1370 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1372 /* Record a CAND_MULT interpretation for the multiply by -1. */
1373 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1375 /* Add the interpretation to the statement-candidate mapping. */
1376 add_cand_for_stmt (gs
, c
);
1379 /* Help function for legal_cast_p, operating on two trees. Checks
1380 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1381 for more details. */
1384 legal_cast_p_1 (tree lhs
, tree rhs
)
1386 tree lhs_type
, rhs_type
;
1387 unsigned lhs_size
, rhs_size
;
1388 bool lhs_wraps
, rhs_wraps
;
1390 lhs_type
= TREE_TYPE (lhs
);
1391 rhs_type
= TREE_TYPE (rhs
);
1392 lhs_size
= TYPE_PRECISION (lhs_type
);
1393 rhs_size
= TYPE_PRECISION (rhs_type
);
1394 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1395 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1397 if (lhs_size
< rhs_size
1398 || (rhs_wraps
&& !lhs_wraps
)
1399 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1405 /* Return TRUE if GS is a statement that defines an SSA name from
1406 a conversion and is legal for us to combine with an add and multiply
1407 in the candidate table. For example, suppose we have:
1413 Without the type-cast, we would create a CAND_MULT for D with base B,
1414 index i, and stride S. We want to record this candidate only if it
1415 is equivalent to apply the type cast following the multiply:
1421 We will record the type with the candidate for D. This allows us
1422 to use a similar previous candidate as a basis. If we have earlier seen
1428 we can replace D with
1430 D = D' + (i - i') * S;
1432 But if moving the type-cast would change semantics, we mustn't do this.
1434 This is legitimate for casts from a non-wrapping integral type to
1435 any integral type of the same or larger size. It is not legitimate
1436 to convert a wrapping type to a non-wrapping type, or to a wrapping
1437 type of a different size. I.e., with a wrapping type, we must
1438 assume that the addition B + i could wrap, in which case performing
1439 the multiply before or after one of the "illegal" type casts will
1440 have different semantics. */
1443 legal_cast_p (gimple gs
, tree rhs
)
1445 if (!is_gimple_assign (gs
)
1446 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1449 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1452 /* Given GS which is a cast to a scalar integer type, determine whether
1453 the cast is legal for strength reduction. If so, make at least one
1454 appropriate entry in the candidate table. */
1457 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1460 slsr_cand_t base_cand
, c
, c2
;
1461 unsigned savings
= 0;
1463 if (!legal_cast_p (gs
, rhs1
))
1466 lhs
= gimple_assign_lhs (gs
);
1467 base_cand
= base_cand_from_table (rhs1
);
1468 ctype
= TREE_TYPE (lhs
);
1470 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1474 /* Propagate all data from the base candidate except the type,
1475 which comes from the cast, and the base candidate's cast,
1476 which is no longer applicable. */
1477 if (has_single_use (rhs1
))
1478 savings
= (base_cand
->dead_savings
1479 + stmt_cost (base_cand
->cand_stmt
, speed
));
1481 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1482 base_cand
->base_expr
,
1483 base_cand
->index
, base_cand
->stride
,
1485 if (base_cand
->next_interp
)
1486 base_cand
= lookup_cand (base_cand
->next_interp
);
1493 /* If nothing is known about the RHS, create fresh CAND_ADD and
1494 CAND_MULT interpretations:
1499 The first of these is somewhat arbitrary, but the choice of
1500 1 for the stride simplifies the logic for propagating casts
1502 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
,
1503 0, integer_one_node
, ctype
, 0);
1504 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
,
1505 0, integer_one_node
, ctype
, 0);
1506 c
->next_interp
= c2
->cand_num
;
1509 /* Add the first (or only) interpretation to the statement-candidate
1511 add_cand_for_stmt (gs
, c
);
1514 /* Given GS which is a copy of a scalar integer type, make at least one
1515 appropriate entry in the candidate table.
1517 This interface is included for completeness, but is unnecessary
1518 if this pass immediately follows a pass that performs copy
1519 propagation, such as DOM. */
1522 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1524 slsr_cand_t base_cand
, c
, c2
;
1525 unsigned savings
= 0;
1527 base_cand
= base_cand_from_table (rhs1
);
1529 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1533 /* Propagate all data from the base candidate. */
1534 if (has_single_use (rhs1
))
1535 savings
= (base_cand
->dead_savings
1536 + stmt_cost (base_cand
->cand_stmt
, speed
));
1538 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1539 base_cand
->base_expr
,
1540 base_cand
->index
, base_cand
->stride
,
1541 base_cand
->cand_type
, savings
);
1542 if (base_cand
->next_interp
)
1543 base_cand
= lookup_cand (base_cand
->next_interp
);
1550 /* If nothing is known about the RHS, create fresh CAND_ADD and
1551 CAND_MULT interpretations:
1556 The first of these is somewhat arbitrary, but the choice of
1557 1 for the stride simplifies the logic for propagating casts
1559 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
,
1560 0, integer_one_node
, TREE_TYPE (rhs1
), 0);
1561 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
,
1562 0, integer_one_node
, TREE_TYPE (rhs1
), 0);
1563 c
->next_interp
= c2
->cand_num
;
1566 /* Add the first (or only) interpretation to the statement-candidate
1568 add_cand_for_stmt (gs
, c
);
1571 class find_candidates_dom_walker
: public dom_walker
1574 find_candidates_dom_walker (cdi_direction direction
)
1575 : dom_walker (direction
) {}
1576 virtual void before_dom_children (basic_block
);
1579 /* Find strength-reduction candidates in block BB. */
1582 find_candidates_dom_walker::before_dom_children (basic_block bb
)
1584 bool speed
= optimize_bb_for_speed_p (bb
);
1585 gimple_stmt_iterator gsi
;
1587 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1588 slsr_process_phi (gsi_stmt (gsi
), speed
);
1590 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1592 gimple gs
= gsi_stmt (gsi
);
1594 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1595 slsr_process_ref (gs
);
1597 else if (is_gimple_assign (gs
)
1598 && SCALAR_INT_MODE_P
1599 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1601 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1603 switch (gimple_assign_rhs_code (gs
))
1607 rhs1
= gimple_assign_rhs1 (gs
);
1608 rhs2
= gimple_assign_rhs2 (gs
);
1609 /* Should never happen, but currently some buggy situations
1610 in earlier phases put constants in rhs1. */
1611 if (TREE_CODE (rhs1
) != SSA_NAME
)
1615 /* Possible future opportunity: rhs1 of a ptr+ can be
1617 case POINTER_PLUS_EXPR
:
1619 rhs2
= gimple_assign_rhs2 (gs
);
1625 rhs1
= gimple_assign_rhs1 (gs
);
1626 if (TREE_CODE (rhs1
) != SSA_NAME
)
1634 switch (gimple_assign_rhs_code (gs
))
1637 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1641 case POINTER_PLUS_EXPR
:
1643 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1647 slsr_process_neg (gs
, rhs1
, speed
);
1651 slsr_process_cast (gs
, rhs1
, speed
);
1655 slsr_process_copy (gs
, rhs1
, speed
);
1665 /* Dump a candidate for debug. */
1668 dump_candidate (slsr_cand_t c
)
1670 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1671 gimple_bb (c
->cand_stmt
)->index
);
1672 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1676 fputs (" MULT : (", dump_file
);
1677 print_generic_expr (dump_file
, c
->base_expr
, 0);
1678 fputs (" + ", dump_file
);
1679 print_decs (c
->index
, dump_file
);
1680 fputs (") * ", dump_file
);
1681 print_generic_expr (dump_file
, c
->stride
, 0);
1682 fputs (" : ", dump_file
);
1685 fputs (" ADD : ", dump_file
);
1686 print_generic_expr (dump_file
, c
->base_expr
, 0);
1687 fputs (" + (", dump_file
);
1688 print_decs (c
->index
, dump_file
);
1689 fputs (" * ", dump_file
);
1690 print_generic_expr (dump_file
, c
->stride
, 0);
1691 fputs (") : ", dump_file
);
1694 fputs (" REF : ", dump_file
);
1695 print_generic_expr (dump_file
, c
->base_expr
, 0);
1696 fputs (" + (", dump_file
);
1697 print_generic_expr (dump_file
, c
->stride
, 0);
1698 fputs (") + ", dump_file
);
1699 print_decs (c
->index
, dump_file
);
1700 fputs (" : ", dump_file
);
1703 fputs (" PHI : ", dump_file
);
1704 print_generic_expr (dump_file
, c
->base_expr
, 0);
1705 fputs (" + (unknown * ", dump_file
);
1706 print_generic_expr (dump_file
, c
->stride
, 0);
1707 fputs (") : ", dump_file
);
1712 print_generic_expr (dump_file
, c
->cand_type
, 0);
1713 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1714 c
->basis
, c
->dependent
, c
->sibling
);
1715 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1716 c
->next_interp
, c
->dead_savings
);
1718 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1719 fputs ("\n", dump_file
);
1722 /* Dump the candidate vector for debug. */
1725 dump_cand_vec (void)
1730 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1732 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1736 /* Callback used to dump the candidate chains hash table. */
1739 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1741 const_cand_chain_t chain
= *slot
;
1744 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1745 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1747 for (p
= chain
->next
; p
; p
= p
->next
)
1748 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1750 fputs ("\n", dump_file
);
1754 /* Dump the candidate chains. */
1757 dump_cand_chains (void)
1759 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1760 base_cand_map
.traverse_noresize
<void *, ssa_base_cand_dump_callback
> (NULL
);
1761 fputs ("\n", dump_file
);
1764 /* Dump the increment vector for debug. */
1767 dump_incr_vec (void)
1769 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1773 fprintf (dump_file
, "\nIncrement vector:\n\n");
1775 for (i
= 0; i
< incr_vec_len
; i
++)
1777 fprintf (dump_file
, "%3d increment: ", i
);
1778 print_decs (incr_vec
[i
].incr
, dump_file
);
1779 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1780 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1781 fputs ("\n initializer: ", dump_file
);
1782 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1783 fputs ("\n\n", dump_file
);
1788 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1792 replace_ref (tree
*expr
, slsr_cand_t c
)
1794 tree add_expr
, mem_ref
, acc_type
= TREE_TYPE (*expr
);
1795 unsigned HOST_WIDE_INT misalign
;
1798 /* Ensure the memory reference carries the minimum alignment
1799 requirement for the data type. See PR58041. */
1800 get_object_alignment_1 (*expr
, &align
, &misalign
);
1802 align
= (misalign
& -misalign
);
1803 if (align
< TYPE_ALIGN (acc_type
))
1804 acc_type
= build_aligned_type (acc_type
, align
);
1806 add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1807 c
->base_expr
, c
->stride
);
1808 mem_ref
= fold_build2 (MEM_REF
, acc_type
, add_expr
,
1809 wide_int_to_tree (c
->cand_type
, c
->index
));
1811 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1812 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1813 TREE_OPERAND (mem_ref
, 0)
1814 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1815 /*simple_p=*/true, NULL
,
1816 /*before=*/true, GSI_SAME_STMT
);
1817 copy_ref_info (mem_ref
, *expr
);
1819 update_stmt (c
->cand_stmt
);
1822 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1823 dependent of candidate C with an equivalent strength-reduced data
1827 replace_refs (slsr_cand_t c
)
1829 if (gimple_vdef (c
->cand_stmt
))
1831 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1832 replace_ref (lhs
, c
);
1836 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1837 replace_ref (rhs
, c
);
1841 replace_refs (lookup_cand (c
->sibling
));
1844 replace_refs (lookup_cand (c
->dependent
));
1847 /* Return TRUE if candidate C is dependent upon a PHI. */
1850 phi_dependent_cand_p (slsr_cand_t c
)
1852 /* A candidate is not necessarily dependent upon a PHI just because
1853 it has a phi definition for its base name. It may have a basis
1854 that relies upon the same phi definition, in which case the PHI
1855 is irrelevant to this candidate. */
1858 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1861 /* Calculate the increment required for candidate C relative to
1865 cand_increment (slsr_cand_t c
)
1869 /* If the candidate doesn't have a basis, just return its own
1870 index. This is useful in record_increments to help us find
1871 an existing initializer. Also, if the candidate's basis is
1872 hidden by a phi, then its own index will be the increment
1873 from the newly introduced phi basis. */
1874 if (!c
->basis
|| phi_dependent_cand_p (c
))
1877 basis
= lookup_cand (c
->basis
);
1878 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1879 return c
->index
- basis
->index
;
1882 /* Calculate the increment required for candidate C relative to
1883 its basis. If we aren't going to generate pointer arithmetic
1884 for this candidate, return the absolute value of that increment
1887 static inline max_wide_int
1888 cand_abs_increment (slsr_cand_t c
)
1890 max_wide_int increment
= cand_increment (c
);
1892 if (!address_arithmetic_p
&& wi::neg_p (increment
))
1893 increment
= -increment
;
1898 /* Return TRUE iff candidate C has already been replaced under
1899 another interpretation. */
1902 cand_already_replaced (slsr_cand_t c
)
1904 return (gimple_bb (c
->cand_stmt
) == 0);
1907 /* Common logic used by replace_unconditional_candidate and
1908 replace_conditional_candidate. */
1911 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, const max_wide_int
&bump_in
)
1913 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
1914 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1915 max_wide_int bump
= bump_in
;
1917 /* It is highly unlikely, but possible, that the resulting
1918 bump doesn't fit in a HWI. Abandon the replacement
1919 in this case. This does not affect siblings or dependents
1920 of C. Restriction to signed HWI is conservative for unsigned
1921 types but allows for safe negation without twisted logic. */
1922 if (wi::fits_shwi_p (bump
)
1923 && bump
.to_shwi () != HOST_WIDE_INT_MIN
1924 /* It is not useful to replace casts, copies, or adds of
1925 an SSA name and a constant. */
1926 && cand_code
!= MODIFY_EXPR
1927 && cand_code
!= NOP_EXPR
1928 && cand_code
!= PLUS_EXPR
1929 && cand_code
!= POINTER_PLUS_EXPR
1930 && cand_code
!= MINUS_EXPR
)
1932 enum tree_code code
= PLUS_EXPR
;
1934 gimple stmt_to_print
= NULL
;
1936 /* If the basis name and the candidate's LHS have incompatible
1937 types, introduce a cast. */
1938 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
1939 basis_name
= introduce_cast_before_cand (c
, target_type
, basis_name
);
1940 if (wi::neg_p (bump
))
1946 bump_tree
= wide_int_to_tree (target_type
, bump
);
1948 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1950 fputs ("Replacing: ", dump_file
);
1951 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1956 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1957 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1958 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1959 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1960 gsi_replace (&gsi
, copy_stmt
, false);
1961 c
->cand_stmt
= copy_stmt
;
1962 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1963 stmt_to_print
= copy_stmt
;
1968 if (cand_code
!= NEGATE_EXPR
) {
1969 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1970 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1972 if (cand_code
!= NEGATE_EXPR
1973 && ((operand_equal_p (rhs1
, basis_name
, 0)
1974 && operand_equal_p (rhs2
, bump_tree
, 0))
1975 || (operand_equal_p (rhs1
, bump_tree
, 0)
1976 && operand_equal_p (rhs2
, basis_name
, 0))))
1978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1980 fputs ("(duplicate, not actually replacing)", dump_file
);
1981 stmt_to_print
= c
->cand_stmt
;
1986 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1987 gimple_assign_set_rhs_with_ops (&gsi
, code
,
1988 basis_name
, bump_tree
);
1989 update_stmt (gsi_stmt (gsi
));
1990 c
->cand_stmt
= gsi_stmt (gsi
);
1991 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1992 stmt_to_print
= gsi_stmt (gsi
);
1996 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1998 fputs ("With: ", dump_file
);
1999 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
2000 fputs ("\n", dump_file
);
2005 /* Replace candidate C with an add or subtract. Note that we only
2006 operate on CAND_MULTs with known strides, so we will never generate
2007 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2008 X = Y + ((i - i') * S), as described in the module commentary. The
2009 folded value ((i - i') * S) is referred to here as the "bump." */
2012 replace_unconditional_candidate (slsr_cand_t c
)
2017 if (cand_already_replaced (c
))
2020 basis
= lookup_cand (c
->basis
);
2021 bump
= cand_increment (c
) * c
->stride
;
2023 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
);
2026 /* Return the index in the increment vector of the given INCREMENT,
2027 or -1 if not found. The latter can occur if more than
2028 MAX_INCR_VEC_LEN increments have been found. */
2031 incr_vec_index (max_wide_int increment
)
2035 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
2038 if (i
< incr_vec_len
)
2044 /* Create a new statement along edge E to add BASIS_NAME to the product
2045 of INCREMENT and the stride of candidate C. Create and return a new
2046 SSA name from *VAR to be used as the LHS of the new statement.
2047 KNOWN_STRIDE is true iff C's stride is a constant. */
2050 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
2051 max_wide_int increment
, edge e
, location_t loc
,
2054 basic_block insert_bb
;
2055 gimple_stmt_iterator gsi
;
2056 tree lhs
, basis_type
;
2059 /* If the add candidate along this incoming edge has the same
2060 index as C's hidden basis, the hidden basis represents this
2065 basis_type
= TREE_TYPE (basis_name
);
2066 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2071 enum tree_code code
= PLUS_EXPR
;
2072 max_wide_int bump
= increment
* c
->stride
;
2073 if (wi::neg_p (bump
))
2079 bump_tree
= wide_int_to_tree (basis_type
, bump
);
2080 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2086 bool negate_incr
= (!address_arithmetic_p
&& wi::neg_p (increment
));
2087 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2088 gcc_assert (i
>= 0);
2090 if (incr_vec
[i
].initializer
)
2092 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2093 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2094 incr_vec
[i
].initializer
);
2096 else if (increment
== 1)
2097 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, lhs
, basis_name
,
2099 else if (increment
== -1)
2100 new_stmt
= gimple_build_assign_with_ops (MINUS_EXPR
, lhs
, basis_name
,
2106 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2107 gsi
= gsi_last_bb (insert_bb
);
2109 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2110 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2112 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2114 gimple_set_location (new_stmt
, loc
);
2116 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2118 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2119 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2125 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2126 is hidden by the phi node FROM_PHI, create a new phi node in the same
2127 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2128 with its phi arguments representing conditional adjustments to the
2129 hidden basis along conditional incoming paths. Those adjustments are
2130 made by creating add statements (and sometimes recursively creating
2131 phis) along those incoming paths. LOC is the location to attach to
2132 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2136 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2137 location_t loc
, bool known_stride
)
2143 slsr_cand_t basis
= lookup_cand (c
->basis
);
2144 int nargs
= gimple_phi_num_args (from_phi
);
2145 basic_block phi_bb
= gimple_bb (from_phi
);
2146 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2147 phi_args
.create (nargs
);
2149 /* Process each argument of the existing phi that represents
2150 conditionally-executed add candidates. */
2151 for (i
= 0; i
< nargs
; i
++)
2153 edge e
= (*phi_bb
->preds
)[i
];
2154 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2157 /* If the phi argument is the base name of the CAND_PHI, then
2158 this incoming arc should use the hidden basis. */
2159 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2160 if (basis
->index
== 0)
2161 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2164 max_wide_int incr
= -basis
->index
;
2165 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2166 e
, loc
, known_stride
);
2170 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2172 /* If there is another phi along this incoming edge, we must
2173 process it in the same fashion to ensure that all basis
2174 adjustments are made along its incoming edges. */
2175 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2176 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2180 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2181 max_wide_int diff
= arg_cand
->index
- basis
->index
;
2182 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2183 e
, loc
, known_stride
);
2187 /* Because of recursion, we need to save the arguments in a vector
2188 so we can create the PHI statement all at once. Otherwise the
2189 storage for the half-created PHI can be reclaimed. */
2190 phi_args
.safe_push (feeding_def
);
2193 /* Create the new phi basis. */
2194 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2195 phi
= create_phi_node (name
, phi_bb
);
2196 SSA_NAME_DEF_STMT (name
) = phi
;
2198 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2200 edge e
= (*phi_bb
->preds
)[i
];
2201 add_phi_arg (phi
, phi_arg
, e
, loc
);
2206 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2208 fputs ("Introducing new phi basis: ", dump_file
);
2209 print_gimple_stmt (dump_file
, phi
, 0, 0);
2215 /* Given a candidate C whose basis is hidden by at least one intervening
2216 phi, introduce a matching number of new phis to represent its basis
2217 adjusted by conditional increments along possible incoming paths. Then
2218 replace C as though it were an unconditional candidate, using the new
2222 replace_conditional_candidate (slsr_cand_t c
)
2224 tree basis_name
, name
;
2229 /* Look up the LHS SSA name from C's basis. This will be the
2230 RHS1 of the adds we will introduce to create new phi arguments. */
2231 basis
= lookup_cand (c
->basis
);
2232 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2234 /* Create a new phi statement which will represent C's true basis
2235 after the transformation is complete. */
2236 loc
= gimple_location (c
->cand_stmt
);
2237 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2238 basis_name
, loc
, KNOWN_STRIDE
);
2239 /* Replace C with an add of the new basis phi and a constant. */
2240 bump
= c
->index
* c
->stride
;
2242 replace_mult_candidate (c
, name
, bump
);
2245 /* Compute the expected costs of inserting basis adjustments for
2246 candidate C with phi-definition PHI. The cost of inserting
2247 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2248 which are themselves phi results, recursively calculate costs
2249 for those phis as well. */
2252 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2256 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2258 /* If we work our way back to a phi that isn't dominated by the hidden
2259 basis, this isn't a candidate for replacement. Indicate this by
2260 returning an unreasonably high cost. It's not easy to detect
2261 these situations when determining the basis, so we defer the
2262 decision until now. */
2263 basic_block phi_bb
= gimple_bb (phi
);
2264 slsr_cand_t basis
= lookup_cand (c
->basis
);
2265 basic_block basis_bb
= gimple_bb (basis
->cand_stmt
);
2267 if (phi_bb
== basis_bb
|| !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
2268 return COST_INFINITE
;
2270 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2272 tree arg
= gimple_phi_arg_def (phi
, i
);
2274 if (arg
!= phi_cand
->base_expr
)
2276 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2278 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2279 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2282 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2284 if (arg_cand
->index
!= c
->index
)
2285 cost
+= one_add_cost
;
2293 /* For candidate C, each sibling of candidate C, and each dependent of
2294 candidate C, determine whether the candidate is dependent upon a
2295 phi that hides its basis. If not, replace the candidate unconditionally.
2296 Otherwise, determine whether the cost of introducing compensation code
2297 for the candidate is offset by the gains from strength reduction. If
2298 so, replace the candidate and introduce the compensation code. */
2301 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2303 if (phi_dependent_cand_p (c
))
2305 if (c
->kind
== CAND_MULT
)
2307 /* A candidate dependent upon a phi will replace a multiply by
2308 a constant with an add, and will insert at most one add for
2309 each phi argument. Add these costs with the potential dead-code
2310 savings to determine profitability. */
2311 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2312 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2313 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2314 tree phi_result
= gimple_phi_result (phi
);
2315 int one_add_cost
= add_cost (speed
,
2316 TYPE_MODE (TREE_TYPE (phi_result
)));
2317 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2318 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2320 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2322 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2323 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2324 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2325 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2326 fprintf (dump_file
, " cost = %d\n", cost
);
2327 if (cost
<= COST_NEUTRAL
)
2328 fputs (" Replacing...\n", dump_file
);
2330 fputs (" Not replaced.\n", dump_file
);
2333 if (cost
<= COST_NEUTRAL
)
2334 replace_conditional_candidate (c
);
2338 replace_unconditional_candidate (c
);
2341 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2344 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2347 /* Count the number of candidates in the tree rooted at C that have
2348 not already been replaced under other interpretations. */
2351 count_candidates (slsr_cand_t c
)
2353 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2356 count
+= count_candidates (lookup_cand (c
->sibling
));
2359 count
+= count_candidates (lookup_cand (c
->dependent
));
2364 /* Increase the count of INCREMENT by one in the increment vector.
2365 INCREMENT is associated with candidate C. If INCREMENT is to be
2366 conditionally executed as part of a conditional candidate replacement,
2367 IS_PHI_ADJUST is true, otherwise false. If an initializer
2368 T_0 = stride * I is provided by a candidate that dominates all
2369 candidates with the same increment, also record T_0 for subsequent use. */
2372 record_increment (slsr_cand_t c
, const max_wide_int
&increment_in
, bool is_phi_adjust
)
2376 max_wide_int increment
= increment_in
;
2378 /* Treat increments that differ only in sign as identical so as to
2379 share initializers, unless we are generating pointer arithmetic. */
2380 if (!address_arithmetic_p
&& wi::neg_p (increment
))
2381 increment
= -increment
;
2383 for (i
= 0; i
< incr_vec_len
; i
++)
2385 if (incr_vec
[i
].incr
== increment
)
2387 incr_vec
[i
].count
++;
2390 /* If we previously recorded an initializer that doesn't
2391 dominate this candidate, it's not going to be useful to
2393 if (incr_vec
[i
].initializer
2394 && !dominated_by_p (CDI_DOMINATORS
,
2395 gimple_bb (c
->cand_stmt
),
2396 incr_vec
[i
].init_bb
))
2398 incr_vec
[i
].initializer
= NULL_TREE
;
2399 incr_vec
[i
].init_bb
= NULL
;
2406 if (!found
&& incr_vec_len
< MAX_INCR_VEC_LEN
- 1)
2408 /* The first time we see an increment, create the entry for it.
2409 If this is the root candidate which doesn't have a basis, set
2410 the count to zero. We're only processing it so it can possibly
2411 provide an initializer for other candidates. */
2412 incr_vec
[incr_vec_len
].incr
= increment
;
2413 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2414 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2416 /* Optimistically record the first occurrence of this increment
2417 as providing an initializer (if it does); we will revise this
2418 opinion later if it doesn't dominate all other occurrences.
2419 Exception: increments of -1, 0, 1 never need initializers;
2420 and phi adjustments don't ever provide initializers. */
2421 if (c
->kind
== CAND_ADD
2423 && c
->index
== increment
2424 && (wi::gts_p (increment
, 1)
2425 || wi::lts_p (increment
, -1))
2426 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2427 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2429 tree t0
= NULL_TREE
;
2430 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2431 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2432 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2434 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2437 && SSA_NAME_DEF_STMT (t0
)
2438 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2440 incr_vec
[incr_vec_len
].initializer
= t0
;
2441 incr_vec
[incr_vec_len
++].init_bb
2442 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2446 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2447 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2452 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2453 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2458 /* Given phi statement PHI that hides a candidate from its BASIS, find
2459 the increments along each incoming arc (recursively handling additional
2460 phis that may be present) and record them. These increments are the
2461 difference in index between the index-adjusting statements and the
2462 index of the basis. */
2465 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2468 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2470 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2472 tree arg
= gimple_phi_arg_def (phi
, i
);
2474 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2476 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2478 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2479 record_phi_increments (basis
, arg_def
);
2482 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2483 max_wide_int diff
= arg_cand
->index
- basis
->index
;
2484 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2490 /* Determine how many times each unique increment occurs in the set
2491 of candidates rooted at C's parent, recording the data in the
2492 increment vector. For each unique increment I, if an initializer
2493 T_0 = stride * I is provided by a candidate that dominates all
2494 candidates with the same increment, also record T_0 for subsequent
2498 record_increments (slsr_cand_t c
)
2500 if (!cand_already_replaced (c
))
2502 if (!phi_dependent_cand_p (c
))
2503 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2506 /* A candidate with a basis hidden by a phi will have one
2507 increment for its relationship to the index represented by
2508 the phi, and potentially additional increments along each
2509 incoming edge. For the root of the dependency tree (which
2510 has no basis), process just the initial index in case it has
2511 an initializer that can be used by subsequent candidates. */
2512 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2515 record_phi_increments (lookup_cand (c
->basis
),
2516 lookup_cand (c
->def_phi
)->cand_stmt
);
2521 record_increments (lookup_cand (c
->sibling
));
2524 record_increments (lookup_cand (c
->dependent
));
2527 /* Add up and return the costs of introducing add statements that
2528 require the increment INCR on behalf of candidate C and phi
2529 statement PHI. Accumulate into *SAVINGS the potential savings
2530 from removing existing statements that feed PHI and have no other
2534 phi_incr_cost (slsr_cand_t c
, const max_wide_int
&incr
, gimple phi
, int *savings
)
2538 slsr_cand_t basis
= lookup_cand (c
->basis
);
2539 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2541 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2543 tree arg
= gimple_phi_arg_def (phi
, i
);
2545 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2547 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2549 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2551 int feeding_savings
= 0;
2552 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2553 if (has_single_use (gimple_phi_result (arg_def
)))
2554 *savings
+= feeding_savings
;
2558 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2559 max_wide_int diff
= arg_cand
->index
- basis
->index
;
2563 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2564 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2565 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2566 if (has_single_use (lhs
))
2567 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2576 /* Return the first candidate in the tree rooted at C that has not
2577 already been replaced, favoring siblings over dependents. */
2580 unreplaced_cand_in_tree (slsr_cand_t c
)
2582 if (!cand_already_replaced (c
))
2587 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2594 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2602 /* Return TRUE if the candidates in the tree rooted at C should be
2603 optimized for speed, else FALSE. We estimate this based on the block
2604 containing the most dominant candidate in the tree that has not yet
2608 optimize_cands_for_speed_p (slsr_cand_t c
)
2610 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2612 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2615 /* Add COST_IN to the lowest cost of any dependent path starting at
2616 candidate C or any of its siblings, counting only candidates along
2617 such paths with increment INCR. Assume that replacing a candidate
2618 reduces cost by REPL_SAVINGS. Also account for savings from any
2619 statements that would go dead. If COUNT_PHIS is true, include
2620 costs of introducing feeding statements for conditional candidates. */
2623 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2624 const max_wide_int
&incr
, bool count_phis
)
2626 int local_cost
, sib_cost
, savings
= 0;
2627 max_wide_int cand_incr
= cand_abs_increment (c
);
2629 if (cand_already_replaced (c
))
2630 local_cost
= cost_in
;
2631 else if (incr
== cand_incr
)
2632 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2634 local_cost
= cost_in
- c
->dead_savings
;
2637 && phi_dependent_cand_p (c
)
2638 && !cand_already_replaced (c
))
2640 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2641 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2643 if (has_single_use (gimple_phi_result (phi
)))
2644 local_cost
-= savings
;
2648 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2649 lookup_cand (c
->dependent
), incr
,
2654 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2655 lookup_cand (c
->sibling
), incr
,
2657 local_cost
= MIN (local_cost
, sib_cost
);
2663 /* Compute the total savings that would accrue from all replacements
2664 in the candidate tree rooted at C, counting only candidates with
2665 increment INCR. Assume that replacing a candidate reduces cost
2666 by REPL_SAVINGS. Also account for savings from statements that
2670 total_savings (int repl_savings
, slsr_cand_t c
, const max_wide_int
&incr
,
2674 max_wide_int cand_incr
= cand_abs_increment (c
);
2676 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2677 savings
+= repl_savings
+ c
->dead_savings
;
2680 && phi_dependent_cand_p (c
)
2681 && !cand_already_replaced (c
))
2683 int phi_savings
= 0;
2684 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2685 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2687 if (has_single_use (gimple_phi_result (phi
)))
2688 savings
+= phi_savings
;
2692 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2696 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2702 /* Use target-specific costs to determine and record which increments
2703 in the current candidate tree are profitable to replace, assuming
2704 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2707 One slight limitation here is that we don't account for the possible
2708 introduction of casts in some cases. See replace_one_candidate for
2709 the cases where these are introduced. This should probably be cleaned
2713 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
2717 for (i
= 0; i
< incr_vec_len
; i
++)
2719 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2721 /* If somehow this increment is bigger than a HWI, we won't
2722 be optimizing candidates that use it. And if the increment
2723 has a count of zero, nothing will be done with it. */
2724 if (!wi::fits_shwi_p (incr_vec
[i
].incr
) || !incr_vec
[i
].count
)
2725 incr_vec
[i
].cost
= COST_INFINITE
;
2727 /* Increments of 0, 1, and -1 are always profitable to replace,
2728 because they always replace a multiply or add with an add or
2729 copy, and may cause one or more existing instructions to go
2730 dead. Exception: -1 can't be assumed to be profitable for
2731 pointer addition. */
2735 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2736 != POINTER_PLUS_EXPR
)))
2737 incr_vec
[i
].cost
= COST_NEUTRAL
;
2739 /* FORNOW: If we need to add an initializer, give up if a cast from
2740 the candidate's type to its stride's type can lose precision.
2741 This could eventually be handled better by expressly retaining the
2742 result of a cast to a wider type in the stride. Example:
2747 _4 = x + _3; ADD: x + (10 * _1) : int
2749 _6 = x + _3; ADD: x + (15 * _1) : int
2751 Right now replacing _6 would cause insertion of an initializer
2752 of the form "short int T = _1 * 5;" followed by a cast to
2753 int, which could overflow incorrectly. Had we recorded _2 or
2754 (int)_1 as the stride, this wouldn't happen. However, doing
2755 this breaks other opportunities, so this will require some
2757 else if (!incr_vec
[i
].initializer
2758 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2759 && !legal_cast_p_1 (first_dep
->stride
,
2760 gimple_assign_lhs (first_dep
->cand_stmt
)))
2762 incr_vec
[i
].cost
= COST_INFINITE
;
2764 /* If we need to add an initializer, make sure we don't introduce
2765 a multiply by a pointer type, which can happen in certain cast
2766 scenarios. FIXME: When cleaning up these cast issues, we can
2767 afford to introduce the multiply provided we cast out to an
2768 unsigned int of appropriate size. */
2769 else if (!incr_vec
[i
].initializer
2770 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2771 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2773 incr_vec
[i
].cost
= COST_INFINITE
;
2775 /* For any other increment, if this is a multiply candidate, we
2776 must introduce a temporary T and initialize it with
2777 T_0 = stride * increment. When optimizing for speed, walk the
2778 candidate tree to calculate the best cost reduction along any
2779 path; if it offsets the fixed cost of inserting the initializer,
2780 replacing the increment is profitable. When optimizing for
2781 size, instead calculate the total cost reduction from replacing
2782 all candidates with this increment. */
2783 else if (first_dep
->kind
== CAND_MULT
)
2785 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2786 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2788 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2789 incr_vec
[i
].incr
, COUNT_PHIS
);
2791 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2794 incr_vec
[i
].cost
= cost
;
2797 /* If this is an add candidate, the initializer may already
2798 exist, so only calculate the cost of the initializer if it
2799 doesn't. We are replacing one add with another here, so the
2800 known replacement savings is zero. We will account for removal
2801 of dead instructions in lowest_cost_path or total_savings. */
2805 if (!incr_vec
[i
].initializer
)
2806 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2809 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2812 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2815 incr_vec
[i
].cost
= cost
;
2820 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2821 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2822 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2823 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2824 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2827 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2828 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2844 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2846 /* If both candidates are in the same block, the earlier
2848 if (bb1
== ncd
&& bb2
== ncd
)
2850 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2856 /* Otherwise, if one of them produced a candidate in the
2857 dominator, that one wins. */
2858 else if (bb1
== ncd
)
2861 else if (bb2
== ncd
)
2864 /* If neither matches the dominator, neither wins. */
2871 /* Consider all candidates that feed PHI. Find the nearest common
2872 dominator of those candidates requiring the given increment INCR.
2873 Further find and return the nearest common dominator of this result
2874 with block NCD. If the returned block contains one or more of the
2875 candidates, return the earliest candidate in the block in *WHERE. */
2878 ncd_with_phi (slsr_cand_t c
, const max_wide_int
&incr
, gimple phi
,
2879 basic_block ncd
, slsr_cand_t
*where
)
2882 slsr_cand_t basis
= lookup_cand (c
->basis
);
2883 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2885 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2887 tree arg
= gimple_phi_arg_def (phi
, i
);
2889 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2891 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2893 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2894 ncd
= ncd_with_phi (c
, incr
, arg_def
, ncd
, where
);
2897 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2898 max_wide_int diff
= arg_cand
->index
- basis
->index
;
2900 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
2901 ncd
= ncd_for_two_cands (ncd
, gimple_bb (arg_cand
->cand_stmt
),
2902 *where
, arg_cand
, where
);
2910 /* Consider the candidate C together with any candidates that feed
2911 C's phi dependence (if any). Find and return the nearest common
2912 dominator of those candidates requiring the given increment INCR.
2913 If the returned block contains one or more of the candidates,
2914 return the earliest candidate in the block in *WHERE. */
2917 ncd_of_cand_and_phis (slsr_cand_t c
, const max_wide_int
&incr
, slsr_cand_t
*where
)
2919 basic_block ncd
= NULL
;
2921 if (cand_abs_increment (c
) == incr
)
2923 ncd
= gimple_bb (c
->cand_stmt
);
2927 if (phi_dependent_cand_p (c
))
2928 ncd
= ncd_with_phi (c
, incr
, lookup_cand (c
->def_phi
)->cand_stmt
,
2934 /* Consider all candidates in the tree rooted at C for which INCR
2935 represents the required increment of C relative to its basis.
2936 Find and return the basic block that most nearly dominates all
2937 such candidates. If the returned block contains one or more of
2938 the candidates, return the earliest candidate in the block in
2942 nearest_common_dominator_for_cands (slsr_cand_t c
, const max_wide_int
&incr
,
2945 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
2946 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
2948 /* First find the NCD of all siblings and dependents. */
2950 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
2953 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
2955 if (!sib_ncd
&& !dep_ncd
)
2960 else if (sib_ncd
&& !dep_ncd
)
2962 new_where
= sib_where
;
2965 else if (dep_ncd
&& !sib_ncd
)
2967 new_where
= dep_where
;
2971 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
2972 dep_where
, &new_where
);
2974 /* If the candidate's increment doesn't match the one we're interested
2975 in (and nor do any increments for feeding defs of a phi-dependence),
2976 then the result depends only on siblings and dependents. */
2977 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
2979 if (!this_ncd
|| cand_already_replaced (c
))
2985 /* Otherwise, compare this candidate with the result from all siblings
2987 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
2992 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
2995 profitable_increment_p (unsigned index
)
2997 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
3000 /* For each profitable increment in the increment vector not equal to
3001 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3002 dominator of all statements in the candidate chain rooted at C
3003 that require that increment, and insert an initializer
3004 T_0 = stride * increment at that location. Record T_0 with the
3005 increment record. */
3008 insert_initializers (slsr_cand_t c
)
3012 for (i
= 0; i
< incr_vec_len
; i
++)
3015 slsr_cand_t where
= NULL
;
3017 tree stride_type
, new_name
, incr_tree
;
3018 max_wide_int incr
= incr_vec
[i
].incr
;
3020 if (!profitable_increment_p (i
)
3023 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
3027 /* We may have already identified an existing initializer that
3029 if (incr_vec
[i
].initializer
)
3031 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3033 fputs ("Using existing initializer: ", dump_file
);
3034 print_gimple_stmt (dump_file
,
3035 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
3041 /* Find the block that most closely dominates all candidates
3042 with this increment. If there is at least one candidate in
3043 that block, the earliest one will be returned in WHERE. */
3044 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
3046 /* Create a new SSA name to hold the initializer's value. */
3047 stride_type
= TREE_TYPE (c
->stride
);
3048 new_name
= make_temp_ssa_name (stride_type
, NULL
, "slsr");
3049 incr_vec
[i
].initializer
= new_name
;
3051 /* Create the initializer and insert it in the latest possible
3052 dominating position. */
3053 incr_tree
= wide_int_to_tree (stride_type
, incr
);
3054 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
3055 c
->stride
, incr_tree
);
3058 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
3059 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3060 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
3064 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
3065 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
3067 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
3068 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3070 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
3072 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
3075 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3077 fputs ("Inserting initializer: ", dump_file
);
3078 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3083 /* Return TRUE iff all required increments for candidates feeding PHI
3084 are profitable to replace on behalf of candidate C. */
3087 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3090 slsr_cand_t basis
= lookup_cand (c
->basis
);
3091 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3093 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3095 tree arg
= gimple_phi_arg_def (phi
, i
);
3097 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3099 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3101 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3103 if (!all_phi_incrs_profitable (c
, arg_def
))
3109 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3110 max_wide_int increment
= arg_cand
->index
- basis
->index
;
3112 if (!address_arithmetic_p
&& wi::neg_p (increment
))
3113 increment
= -increment
;
3115 j
= incr_vec_index (increment
);
3117 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3119 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3121 print_gimple_stmt (dump_file
, phi
, 0, 0);
3122 fputs (" increment: ", dump_file
);
3123 print_decs (increment
, dump_file
);
3126 "\n Not replaced; incr_vec overflow.\n");
3128 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3129 if (profitable_increment_p (j
))
3130 fputs (" Replacing...\n", dump_file
);
3132 fputs (" Not replaced.\n", dump_file
);
3136 if (j
< 0 || !profitable_increment_p (j
))
3145 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3146 type TO_TYPE, and insert it in front of the statement represented
3147 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3148 the new SSA name. */
3151 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
, tree from_expr
)
3155 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3157 cast_lhs
= make_temp_ssa_name (to_type
, NULL
, "slsr");
3158 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
3159 from_expr
, NULL_TREE
);
3160 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3161 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3163 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3165 fputs (" Inserting: ", dump_file
);
3166 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3172 /* Replace the RHS of the statement represented by candidate C with
3173 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3174 leave C unchanged or just interchange its operands. The original
3175 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3176 If the replacement was made and we are doing a details dump,
3177 return the revised statement, else NULL. */
3180 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3181 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3184 if (new_code
!= old_code
3185 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3186 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3187 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3188 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3190 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3191 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3192 update_stmt (gsi_stmt (gsi
));
3193 c
->cand_stmt
= gsi_stmt (gsi
);
3195 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3196 return gsi_stmt (gsi
);
3199 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3200 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3205 /* Strength-reduce the statement represented by candidate C by replacing
3206 it with an equivalent addition or subtraction. I is the index into
3207 the increment vector identifying C's increment. NEW_VAR is used to
3208 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3209 is the rhs1 to use in creating the add/subtract. */
3212 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree basis_name
)
3214 gimple stmt_to_print
= NULL
;
3215 tree orig_rhs1
, orig_rhs2
;
3217 enum tree_code orig_code
, repl_code
;
3218 max_wide_int cand_incr
;
3220 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3221 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3222 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3223 cand_incr
= cand_increment (c
);
3225 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3227 fputs ("Replacing: ", dump_file
);
3228 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3229 stmt_to_print
= c
->cand_stmt
;
3232 if (address_arithmetic_p
)
3233 repl_code
= POINTER_PLUS_EXPR
;
3235 repl_code
= PLUS_EXPR
;
3237 /* If the increment has an initializer T_0, replace the candidate
3238 statement with an add of the basis name and the initializer. */
3239 if (incr_vec
[i
].initializer
)
3241 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3242 tree orig_type
= TREE_TYPE (orig_rhs2
);
3244 if (types_compatible_p (orig_type
, init_type
))
3245 rhs2
= incr_vec
[i
].initializer
;
3247 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3248 incr_vec
[i
].initializer
);
3250 if (incr_vec
[i
].incr
!= cand_incr
)
3252 gcc_assert (repl_code
== PLUS_EXPR
);
3253 repl_code
= MINUS_EXPR
;
3256 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3257 orig_code
, orig_rhs1
, orig_rhs2
,
3261 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3262 with a subtract of the stride from the basis name, a copy
3263 from the basis name, or an add of the stride to the basis
3264 name, respectively. It may be necessary to introduce a
3265 cast (or reuse an existing cast). */
3266 else if (cand_incr
== 1)
3268 tree stride_type
= TREE_TYPE (c
->stride
);
3269 tree orig_type
= TREE_TYPE (orig_rhs2
);
3271 if (types_compatible_p (orig_type
, stride_type
))
3274 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3276 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3277 orig_code
, orig_rhs1
, orig_rhs2
,
3281 else if (cand_incr
== -1)
3283 tree stride_type
= TREE_TYPE (c
->stride
);
3284 tree orig_type
= TREE_TYPE (orig_rhs2
);
3285 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3287 if (types_compatible_p (orig_type
, stride_type
))
3290 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3292 if (orig_code
!= MINUS_EXPR
3293 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3294 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3296 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3297 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3298 update_stmt (gsi_stmt (gsi
));
3299 c
->cand_stmt
= gsi_stmt (gsi
);
3301 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3302 stmt_to_print
= gsi_stmt (gsi
);
3304 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3305 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3308 else if (cand_incr
== 0)
3310 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3311 tree lhs_type
= TREE_TYPE (lhs
);
3312 tree basis_type
= TREE_TYPE (basis_name
);
3314 if (types_compatible_p (lhs_type
, basis_type
))
3316 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3317 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3318 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3319 gsi_replace (&gsi
, copy_stmt
, false);
3320 c
->cand_stmt
= copy_stmt
;
3322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3323 stmt_to_print
= copy_stmt
;
3327 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3328 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
3331 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3332 gsi_replace (&gsi
, cast_stmt
, false);
3333 c
->cand_stmt
= cast_stmt
;
3335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3336 stmt_to_print
= cast_stmt
;
3342 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3344 fputs ("With: ", dump_file
);
3345 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3346 fputs ("\n", dump_file
);
3350 /* For each candidate in the tree rooted at C, replace it with
3351 an increment if such has been shown to be profitable. */
3354 replace_profitable_candidates (slsr_cand_t c
)
3356 if (!cand_already_replaced (c
))
3358 max_wide_int increment
= cand_abs_increment (c
);
3359 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3362 i
= incr_vec_index (increment
);
3364 /* Only process profitable increments. Nothing useful can be done
3365 to a cast or copy. */
3367 && profitable_increment_p (i
)
3368 && orig_code
!= MODIFY_EXPR
3369 && orig_code
!= NOP_EXPR
)
3371 if (phi_dependent_cand_p (c
))
3373 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3375 if (all_phi_incrs_profitable (c
, phi
))
3377 /* Look up the LHS SSA name from C's basis. This will be
3378 the RHS1 of the adds we will introduce to create new
3380 slsr_cand_t basis
= lookup_cand (c
->basis
);
3381 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3383 /* Create a new phi statement that will represent C's true
3384 basis after the transformation is complete. */
3385 location_t loc
= gimple_location (c
->cand_stmt
);
3386 tree name
= create_phi_basis (c
, phi
, basis_name
,
3387 loc
, UNKNOWN_STRIDE
);
3389 /* Replace C with an add of the new basis phi and the
3391 replace_one_candidate (c
, i
, name
);
3396 slsr_cand_t basis
= lookup_cand (c
->basis
);
3397 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3398 replace_one_candidate (c
, i
, basis_name
);
3404 replace_profitable_candidates (lookup_cand (c
->sibling
));
3407 replace_profitable_candidates (lookup_cand (c
->dependent
));
3410 /* Analyze costs of related candidates in the candidate vector,
3411 and make beneficial replacements. */
3414 analyze_candidates_and_replace (void)
3419 /* Each candidate that has a null basis and a non-null
3420 dependent is the root of a tree of related statements.
3421 Analyze each tree to determine a subset of those
3422 statements that can be replaced with maximum benefit. */
3423 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3425 slsr_cand_t first_dep
;
3427 if (c
->basis
!= 0 || c
->dependent
== 0)
3430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3431 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3434 first_dep
= lookup_cand (c
->dependent
);
3436 /* If this is a chain of CAND_REFs, unconditionally replace
3437 each of them with a strength-reduced data reference. */
3438 if (c
->kind
== CAND_REF
)
3441 /* If the common stride of all related candidates is a known
3442 constant, each candidate without a phi-dependence can be
3443 profitably replaced. Each replaces a multiply by a single
3444 add, with the possibility that a feeding add also goes dead.
3445 A candidate with a phi-dependence is replaced only if the
3446 compensation code it requires is offset by the strength
3447 reduction savings. */
3448 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3449 replace_uncond_cands_and_profitable_phis (first_dep
);
3451 /* When the stride is an SSA name, it may still be profitable
3452 to replace some or all of the dependent candidates, depending
3453 on whether the introduced increments can be reused, or are
3454 less expensive to calculate than the replaced statements. */
3457 enum machine_mode mode
;
3460 /* Determine whether we'll be generating pointer arithmetic
3461 when replacing candidates. */
3462 address_arithmetic_p
= (c
->kind
== CAND_ADD
3463 && POINTER_TYPE_P (c
->cand_type
));
3465 /* If all candidates have already been replaced under other
3466 interpretations, nothing remains to be done. */
3467 if (!count_candidates (c
))
3470 /* Construct an array of increments for this candidate chain. */
3471 incr_vec
= XNEWVEC (incr_info
, MAX_INCR_VEC_LEN
);
3473 record_increments (c
);
3475 /* Determine which increments are profitable to replace. */
3476 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3477 speed
= optimize_cands_for_speed_p (c
);
3478 analyze_increments (first_dep
, mode
, speed
);
3480 /* Insert initializers of the form T_0 = stride * increment
3481 for use in profitable replacements. */
3482 insert_initializers (first_dep
);
3485 /* Perform the replacements. */
3486 replace_profitable_candidates (first_dep
);
3493 execute_strength_reduction (void)
3495 /* Create the obstack where candidates will reside. */
3496 gcc_obstack_init (&cand_obstack
);
3498 /* Allocate the candidate vector. */
3499 cand_vec
.create (128);
3501 /* Allocate the mapping from statements to candidate indices. */
3502 stmt_cand_map
= pointer_map_create ();
3504 /* Create the obstack where candidate chains will reside. */
3505 gcc_obstack_init (&chain_obstack
);
3507 /* Allocate the mapping from base expressions to candidate chains. */
3508 base_cand_map
.create (500);
3510 /* Initialize the loop optimizer. We need to detect flow across
3511 back edges, and this gives us dominator information as well. */
3512 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3514 /* Walk the CFG in predominator order looking for strength reduction
3516 find_candidates_dom_walker (CDI_DOMINATORS
)
3517 .walk (cfun
->cfg
->x_entry_block_ptr
);
3519 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3522 dump_cand_chains ();
3525 /* Analyze costs and make appropriate replacements. */
3526 analyze_candidates_and_replace ();
3528 loop_optimizer_finalize ();
3529 base_cand_map
.dispose ();
3530 obstack_free (&chain_obstack
, NULL
);
3531 pointer_map_destroy (stmt_cand_map
);
3532 cand_vec
.release ();
3533 obstack_free (&cand_obstack
, NULL
);
3539 gate_strength_reduction (void)
3541 return flag_tree_slsr
;
3546 const pass_data pass_data_strength_reduction
=
3548 GIMPLE_PASS
, /* type */
3550 OPTGROUP_NONE
, /* optinfo_flags */
3551 true, /* has_gate */
3552 true, /* has_execute */
3553 TV_GIMPLE_SLSR
, /* tv_id */
3554 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3555 0, /* properties_provided */
3556 0, /* properties_destroyed */
3557 0, /* todo_flags_start */
3558 TODO_verify_ssa
, /* todo_flags_finish */
3561 class pass_strength_reduction
: public gimple_opt_pass
3564 pass_strength_reduction(gcc::context
*ctxt
)
3565 : gimple_opt_pass(pass_data_strength_reduction
, ctxt
)
3568 /* opt_pass methods: */
3569 bool gate () { return gate_strength_reduction (); }
3570 unsigned int execute () { return execute_strength_reduction (); }
3572 }; // class pass_strength_reduction
3577 make_pass_strength_reduction (gcc::context
*ctxt
)
3579 return new pass_strength_reduction (ctxt
);