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"
45 #include "tree-flow.h"
47 #include "pointer-set.h"
50 #include "hash-table.h"
52 /* Information about a strength reduction candidate. Each statement
53 in the candidate table represents an expression of one of the
54 following forms (the special case of CAND_REF will be described
57 (CAND_MULT) S1: X = (B + i) * S
58 (CAND_ADD) S1: X = B + (i * S)
60 Here X and B are SSA names, i is an integer constant, and S is
61 either an SSA name or a constant. We call B the "base," i the
62 "index", and S the "stride."
64 Any statement S0 that dominates S1 and is of the form:
66 (CAND_MULT) S0: Y = (B + i') * S
67 (CAND_ADD) S0: Y = B + (i' * S)
69 is called a "basis" for S1. In both cases, S1 may be replaced by
71 S1': X = Y + (i - i') * S,
73 where (i - i') * S is folded to the extent possible.
75 All gimple statements are visited in dominator order, and each
76 statement that may contribute to one of the forms of S1 above is
77 given at least one entry in the candidate table. Such statements
78 include addition, pointer addition, subtraction, multiplication,
79 negation, copies, and nontrivial type casts. If a statement may
80 represent more than one expression of the forms of S1 above,
81 multiple "interpretations" are stored in the table and chained
84 * An add of two SSA names may treat either operand as the base.
85 * A multiply of two SSA names, likewise.
86 * A copy or cast may be thought of as either a CAND_MULT with
87 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
89 Candidate records are allocated from an obstack. They are addressed
90 both from a hash table keyed on S1, and from a vector of candidate
91 pointers arranged in predominator order.
95 Currently we don't recognize:
100 as a strength reduction opportunity, even though this S1 would
101 also be replaceable by the S1' above. This can be added if it
102 comes up in practice.
104 Strength reduction in addressing
105 --------------------------------
106 There is another kind of candidate known as CAND_REF. A CAND_REF
107 describes a statement containing a memory reference having
108 complex addressing that might benefit from strength reduction.
109 Specifically, we are interested in references for which
110 get_inner_reference returns a base address, offset, and bitpos as
113 base: MEM_REF (T1, C1)
114 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
115 bitpos: C4 * BITS_PER_UNIT
117 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
118 arbitrary integer constants. Note that C2 may be zero, in which
119 case the offset will be MULT_EXPR (T2, C3).
121 When this pattern is recognized, the original memory reference
122 can be replaced with:
124 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
127 which distributes the multiply to allow constant folding. When
128 two or more addressing expressions can be represented by MEM_REFs
129 of this form, differing only in the constants C1, C2, and C4,
130 making this substitution produces more efficient addressing during
131 the RTL phases. When there are not at least two expressions with
132 the same values of T1, T2, and C3, there is nothing to be gained
135 Strength reduction of CAND_REFs uses the same infrastructure as
136 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
137 field, MULT_EXPR (T2, C3) in the stride (S) field, and
138 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
139 is thus another CAND_REF with the same B and S values. When at
140 least two CAND_REFs are chained together using the basis relation,
141 each of them is replaced as above, resulting in improved code
142 generation for addressing.
144 Conditional candidates
145 ======================
147 Conditional candidates are best illustrated with an example.
148 Consider the code sequence:
151 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
153 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
154 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
155 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
156 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
158 Here strength reduction is complicated by the uncertain value of x_2.
159 A legitimate transformation is:
168 (4) [x_2 = PHI <x_0, x_1>;]
169 (4a) t_2 = PHI <a_0, t_1>;
173 where the bracketed instructions may go dead.
175 To recognize this opportunity, we have to observe that statement (6)
176 has a "hidden basis" (2). The hidden basis is unlike a normal basis
177 in that the statement and the hidden basis have different base SSA
178 names (x_2 and x_0, respectively). The relationship is established
179 when a statement's base name (x_2) is defined by a phi statement (4),
180 each argument of which (x_0, x_1) has an identical "derived base name."
181 If the argument is defined by a candidate (as x_1 is by (3)) that is a
182 CAND_ADD having a stride of 1, the derived base name of the argument is
183 the base name of the candidate (x_0). Otherwise, the argument itself
184 is its derived base name (as is the case with argument x_0).
186 The hidden basis for statement (6) is the nearest dominating candidate
187 whose base name is the derived base name (x_0) of the feeding phi (4),
188 and whose stride is identical to that of the statement. We can then
189 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
190 allowing the final replacement of (6) by the strength-reduced (6r).
192 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
193 A CAND_PHI is not a candidate for replacement, but is maintained in the
194 candidate table to ease discovery of hidden bases. Any phi statement
195 whose arguments share a common derived base name is entered into the
196 table with the derived base name, an (arbitrary) index of zero, and a
197 stride of 1. A statement with a hidden basis can then be detected by
198 simply looking up its feeding phi definition in the candidate table,
199 extracting the derived base name, and searching for a basis in the
200 usual manner after substituting the derived base name.
202 Note that the transformation is only valid when the original phi and
203 the statements that define the phi's arguments are all at the same
204 position in the loop hierarchy. */
207 /* Index into the candidate vector, offset by 1. VECs are zero-based,
208 while cand_idx's are one-based, with zero indicating null. */
209 typedef unsigned cand_idx
;
211 /* The kind of candidate. */
222 /* The candidate statement S1. */
225 /* The base expression B: often an SSA name, but not always. */
231 /* The index constant i. */
234 /* The type of the candidate. This is normally the type of base_expr,
235 but casts may have occurred when combining feeding instructions.
236 A candidate can only be a basis for candidates of the same final type.
237 (For CAND_REFs, this is the type to be used for operand 1 of the
238 replacement MEM_REF.) */
241 /* The kind of candidate (CAND_MULT, etc.). */
244 /* Index of this candidate in the candidate vector. */
247 /* Index of the next candidate record for the same statement.
248 A statement may be useful in more than one way (e.g., due to
249 commutativity). So we can have multiple "interpretations"
251 cand_idx next_interp
;
253 /* Index of the basis statement S0, if any, in the candidate vector. */
256 /* First candidate for which this candidate is a basis, if one exists. */
259 /* Next candidate having the same basis as this one. */
262 /* If this is a conditional candidate, the CAND_PHI candidate
263 that defines the base SSA name B. */
266 /* Savings that can be expected from eliminating dead code if this
267 candidate is replaced. */
271 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
272 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
274 /* Pointers to candidates are chained together as part of a mapping
275 from base expressions to the candidates that use them. */
279 /* Base expression for the chain of candidates: often, but not
280 always, an SSA name. */
283 /* Pointer to a candidate. */
287 struct cand_chain_d
*next
;
291 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
292 typedef const struct cand_chain_d
*const_cand_chain_t
;
294 /* Information about a unique "increment" associated with candidates
295 having an SSA name for a stride. An increment is the difference
296 between the index of the candidate and the index of its basis,
297 i.e., (i - i') as discussed in the module commentary.
299 When we are not going to generate address arithmetic we treat
300 increments that differ only in sign as the same, allowing sharing
301 of the cost of initializers. The absolute value of the increment
302 is stored in the incr_info. */
306 /* The increment that relates a candidate to its basis. */
309 /* How many times the increment occurs in the candidate tree. */
312 /* Cost of replacing candidates using this increment. Negative and
313 zero costs indicate replacement should be performed. */
316 /* If this increment is profitable but is not -1, 0, or 1, it requires
317 an initializer T_0 = stride * incr to be found or introduced in the
318 nearest common dominator of all candidates. This field holds T_0
319 for subsequent use. */
322 /* If the initializer was found to already exist, this is the block
323 where it was found. */
327 typedef struct incr_info_d incr_info
, *incr_info_t
;
329 /* Candidates are maintained in a vector. If candidate X dominates
330 candidate Y, then X appears before Y in the vector; but the
331 converse does not necessarily hold. */
332 static vec
<slsr_cand_t
> cand_vec
;
346 enum phi_adjust_status
352 enum count_phis_status
358 /* Pointer map embodying a mapping from statements to candidates. */
359 static struct pointer_map_t
*stmt_cand_map
;
361 /* Obstack for candidates. */
362 static struct obstack cand_obstack
;
364 /* Obstack for candidate chains. */
365 static struct obstack chain_obstack
;
367 /* An array INCR_VEC of incr_infos is used during analysis of related
368 candidates having an SSA name for a stride. INCR_VEC_LEN describes
369 its current length. */
370 static incr_info_t incr_vec
;
371 static unsigned incr_vec_len
;
373 /* For a chain of candidates with unknown stride, indicates whether or not
374 we must generate pointer arithmetic when replacing statements. */
375 static bool address_arithmetic_p
;
377 /* Forward function declarations. */
378 static slsr_cand_t
base_cand_from_table (tree
);
379 static tree
introduce_cast_before_cand (slsr_cand_t
, tree
, tree
);
381 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
384 lookup_cand (cand_idx idx
)
386 return cand_vec
[idx
- 1];
389 /* Helper for hashing a candidate chain header. */
391 struct cand_chain_hasher
: typed_noop_remove
<cand_chain
>
393 typedef cand_chain value_type
;
394 typedef cand_chain compare_type
;
395 static inline hashval_t
hash (const value_type
*);
396 static inline bool equal (const value_type
*, const compare_type
*);
400 cand_chain_hasher::hash (const value_type
*p
)
402 tree base_expr
= p
->base_expr
;
403 return iterative_hash_expr (base_expr
, 0);
407 cand_chain_hasher::equal (const value_type
*chain1
, const compare_type
*chain2
)
409 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
412 /* Hash table embodying a mapping from base exprs to chains of candidates. */
413 static hash_table
<cand_chain_hasher
> base_cand_map
;
415 /* Look in the candidate table for a CAND_PHI that defines BASE and
416 return it if found; otherwise return NULL. GS is the candidate
417 statement with BASE, INDEX, and STRIDE. If GS is a CAND_ADD with
418 an index of 1 and an SSA name for STRIDE, we must be careful that
419 we haven't commuted the operands for this candidate. STRIDE must
420 correspond to the second addend of GS for the eventual transformation
421 to be legal. If not, return NULL. */
424 find_phi_def (gimple gs
, enum cand_kind kind
, tree base
,
425 double_int index
, tree stride
)
429 if (TREE_CODE (base
) != SSA_NAME
)
432 /* If we've commuted the operands (so "y + z" is represented as
433 "z + (1 * y)"), we don't have the pattern we're looking for.
434 Bail out to avoid doing a wrong replacement downstream. */
437 && TREE_CODE (stride
) == SSA_NAME
438 && gimple_assign_rhs_code (gs
) == PLUS_EXPR
439 && stride
!= gimple_assign_rhs2 (gs
))
442 c
= base_cand_from_table (base
);
444 if (!c
|| c
->kind
!= CAND_PHI
)
450 /* Helper routine for find_basis_for_candidate. May be called twice:
451 once for the candidate's base expr, and optionally again for the
452 candidate's phi definition. */
455 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
457 cand_chain mapping_key
;
459 slsr_cand_t basis
= NULL
;
461 // Limit potential of N^2 behavior for long candidate chains.
463 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
465 mapping_key
.base_expr
= base_expr
;
466 chain
= base_cand_map
.find (&mapping_key
);
468 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
470 slsr_cand_t one_basis
= chain
->cand
;
472 if (one_basis
->kind
!= c
->kind
473 || one_basis
->cand_stmt
== c
->cand_stmt
474 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
475 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
476 || !dominated_by_p (CDI_DOMINATORS
,
477 gimple_bb (c
->cand_stmt
),
478 gimple_bb (one_basis
->cand_stmt
)))
481 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
488 /* Use the base expr from candidate C to look for possible candidates
489 that can serve as a basis for C. Each potential basis must also
490 appear in a block that dominates the candidate statement and have
491 the same stride and type. If more than one possible basis exists,
492 the one with highest index in the vector is chosen; this will be
493 the most immediately dominating basis. */
496 find_basis_for_candidate (slsr_cand_t c
)
498 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
500 /* If a candidate doesn't have a basis using its base expression,
501 it may have a basis hidden by one or more intervening phis. */
502 if (!basis
&& c
->def_phi
)
504 basic_block basis_bb
, phi_bb
;
505 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
506 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
510 /* A hidden basis must dominate the phi-definition of the
511 candidate's base name. */
512 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
513 basis_bb
= gimple_bb (basis
->cand_stmt
);
515 if (phi_bb
== basis_bb
516 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
522 /* If we found a hidden basis, estimate additional dead-code
523 savings if the phi and its feeding statements can be removed. */
524 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
525 c
->dead_savings
+= phi_cand
->dead_savings
;
531 c
->sibling
= basis
->dependent
;
532 basis
->dependent
= c
->cand_num
;
533 return basis
->cand_num
;
539 /* Record a mapping from the base expression of C to C itself, indicating that
540 C may potentially serve as a basis using that base expression. */
543 record_potential_basis (slsr_cand_t c
)
548 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
549 node
->base_expr
= c
->base_expr
;
552 slot
= base_cand_map
.find_slot (node
, INSERT
);
556 cand_chain_t head
= (cand_chain_t
) (*slot
);
557 node
->next
= head
->next
;
564 /* Allocate storage for a new candidate and initialize its fields.
565 Attempt to find a basis for the candidate. */
568 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
569 double_int index
, tree stride
, tree ctype
,
572 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
578 c
->cand_type
= ctype
;
580 c
->cand_num
= cand_vec
.length () + 1;
584 c
->def_phi
= find_phi_def (gs
, kind
, base
, index
, stride
);
585 c
->dead_savings
= savings
;
587 cand_vec
.safe_push (c
);
589 if (kind
== CAND_PHI
)
592 c
->basis
= find_basis_for_candidate (c
);
594 record_potential_basis (c
);
599 /* Determine the target cost of statement GS when compiling according
603 stmt_cost (gimple gs
, bool speed
)
605 tree lhs
, rhs1
, rhs2
;
606 enum machine_mode lhs_mode
;
608 gcc_assert (is_gimple_assign (gs
));
609 lhs
= gimple_assign_lhs (gs
);
610 rhs1
= gimple_assign_rhs1 (gs
);
611 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
613 switch (gimple_assign_rhs_code (gs
))
616 rhs2
= gimple_assign_rhs2 (gs
);
618 if (host_integerp (rhs2
, 0))
619 return mult_by_coeff_cost (TREE_INT_CST_LOW (rhs2
), lhs_mode
, speed
);
621 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
622 return mul_cost (speed
, lhs_mode
);
625 case POINTER_PLUS_EXPR
:
627 return add_cost (speed
, lhs_mode
);
630 return neg_cost (speed
, lhs_mode
);
633 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
635 /* Note that we don't assign costs to copies that in most cases
645 /* Look up the defining statement for BASE_IN and return a pointer
646 to its candidate in the candidate table, if any; otherwise NULL.
647 Only CAND_ADD and CAND_MULT candidates are returned. */
650 base_cand_from_table (tree base_in
)
654 gimple def
= SSA_NAME_DEF_STMT (base_in
);
656 return (slsr_cand_t
) NULL
;
658 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
660 if (result
&& (*result
)->kind
!= CAND_REF
)
663 return (slsr_cand_t
) NULL
;
666 /* Add an entry to the statement-to-candidate mapping. */
669 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
671 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
676 /* Given PHI which contains a phi statement, determine whether it
677 satisfies all the requirements of a phi candidate. If so, create
678 a candidate. Note that a CAND_PHI never has a basis itself, but
679 is used to help find a basis for subsequent candidates. */
682 slsr_process_phi (gimple phi
, bool speed
)
685 tree arg0_base
= NULL_TREE
, base_type
;
687 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
688 unsigned savings
= 0;
690 /* A CAND_PHI requires each of its arguments to have the same
691 derived base name. (See the module header commentary for a
692 definition of derived base names.) Furthermore, all feeding
693 definitions must be in the same position in the loop hierarchy
696 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
698 slsr_cand_t arg_cand
;
699 tree arg
= gimple_phi_arg_def (phi
, i
);
700 tree derived_base_name
= NULL_TREE
;
701 gimple arg_stmt
= NULL
;
702 basic_block arg_bb
= NULL
;
704 if (TREE_CODE (arg
) != SSA_NAME
)
707 arg_cand
= base_cand_from_table (arg
);
711 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
713 if (!arg_cand
->next_interp
)
716 arg_cand
= lookup_cand (arg_cand
->next_interp
);
719 if (!integer_onep (arg_cand
->stride
))
722 derived_base_name
= arg_cand
->base_expr
;
723 arg_stmt
= arg_cand
->cand_stmt
;
724 arg_bb
= gimple_bb (arg_stmt
);
726 /* Gather potential dead code savings if the phi statement
727 can be removed later on. */
728 if (has_single_use (arg
))
730 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
731 savings
+= arg_cand
->dead_savings
;
733 savings
+= stmt_cost (arg_stmt
, speed
);
738 derived_base_name
= arg
;
740 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
741 arg_bb
= single_succ (ENTRY_BLOCK_PTR
);
743 gimple_bb (SSA_NAME_DEF_STMT (arg
));
746 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
750 arg0_base
= derived_base_name
;
751 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
755 /* Create the candidate. "alloc_cand_and_find_basis" is named
756 misleadingly for this case, as no basis will be sought for a
758 base_type
= TREE_TYPE (arg0_base
);
760 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
, double_int_zero
,
761 integer_one_node
, base_type
, savings
);
763 /* Add the candidate to the statement-candidate mapping. */
764 add_cand_for_stmt (phi
, c
);
767 /* Look for the following pattern:
769 *PBASE: MEM_REF (T1, C1)
771 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
773 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
775 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
777 *PINDEX: C4 * BITS_PER_UNIT
779 If not present, leave the input values unchanged and return FALSE.
780 Otherwise, modify the input values as follows and return TRUE:
783 *POFFSET: MULT_EXPR (T2, C3)
784 *PINDEX: C1 + (C2 * C3) + C4 */
787 restructure_reference (tree
*pbase
, tree
*poffset
, double_int
*pindex
,
790 tree base
= *pbase
, offset
= *poffset
;
791 double_int index
= *pindex
;
792 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
793 tree mult_op0
, mult_op1
, t1
, t2
, type
;
794 double_int c1
, c2
, c3
, c4
;
798 || TREE_CODE (base
) != MEM_REF
799 || TREE_CODE (offset
) != MULT_EXPR
800 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
801 || !index
.umod (bpu
, FLOOR_MOD_EXPR
).is_zero ())
804 t1
= TREE_OPERAND (base
, 0);
805 c1
= mem_ref_offset (base
);
806 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
808 mult_op0
= TREE_OPERAND (offset
, 0);
809 mult_op1
= TREE_OPERAND (offset
, 1);
811 c3
= tree_to_double_int (mult_op1
);
813 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
815 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
817 t2
= TREE_OPERAND (mult_op0
, 0);
818 c2
= tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
823 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
825 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
827 t2
= TREE_OPERAND (mult_op0
, 0);
828 c2
= -tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
836 c2
= double_int_zero
;
839 c4
= index
.udiv (bpu
, FLOOR_DIV_EXPR
);
842 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, t2
,
843 double_int_to_tree (sizetype
, c3
));
844 *pindex
= c1
+ c2
* c3
+ c4
;
850 /* Given GS which contains a data reference, create a CAND_REF entry in
851 the candidate table and attempt to find a basis. */
854 slsr_process_ref (gimple gs
)
856 tree ref_expr
, base
, offset
, type
;
857 HOST_WIDE_INT bitsize
, bitpos
;
858 enum machine_mode mode
;
859 int unsignedp
, volatilep
;
863 if (gimple_vdef (gs
))
864 ref_expr
= gimple_assign_lhs (gs
);
866 ref_expr
= gimple_assign_rhs1 (gs
);
868 if (!handled_component_p (ref_expr
)
869 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
870 || (TREE_CODE (ref_expr
) == COMPONENT_REF
871 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
874 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
875 &unsignedp
, &volatilep
, false);
876 index
= double_int::from_uhwi (bitpos
);
878 if (!restructure_reference (&base
, &offset
, &index
, &type
))
881 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
884 /* Add the candidate to the statement-candidate mapping. */
885 add_cand_for_stmt (gs
, c
);
888 /* Create a candidate entry for a statement GS, where GS multiplies
889 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
890 about the two SSA names into the new candidate. Return the new
894 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
896 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
898 unsigned savings
= 0;
900 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
902 /* Look at all interpretations of the base candidate, if necessary,
903 to find information to propagate into this candidate. */
904 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
907 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
913 base
= base_cand
->base_expr
;
914 index
= base_cand
->index
;
916 ctype
= base_cand
->cand_type
;
917 if (has_single_use (base_in
))
918 savings
= (base_cand
->dead_savings
919 + stmt_cost (base_cand
->cand_stmt
, speed
));
921 else if (base_cand
->kind
== CAND_ADD
922 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
924 /* Y = B + (i' * S), S constant
926 ============================
927 X = B + ((i' * S) * Z) */
928 base
= base_cand
->base_expr
;
929 index
= base_cand
->index
* tree_to_double_int (base_cand
->stride
);
931 ctype
= base_cand
->cand_type
;
932 if (has_single_use (base_in
))
933 savings
= (base_cand
->dead_savings
934 + stmt_cost (base_cand
->cand_stmt
, speed
));
937 if (base_cand
->next_interp
)
938 base_cand
= lookup_cand (base_cand
->next_interp
);
945 /* No interpretations had anything useful to propagate, so
946 produce X = (Y + 0) * Z. */
948 index
= double_int_zero
;
950 ctype
= TREE_TYPE (base_in
);
953 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
958 /* Create a candidate entry for a statement GS, where GS multiplies
959 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
960 information about BASE_IN into the new candidate. Return the new
964 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
966 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
967 double_int index
, temp
;
968 unsigned savings
= 0;
970 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
972 /* Look at all interpretations of the base candidate, if necessary,
973 to find information to propagate into this candidate. */
974 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
976 if (base_cand
->kind
== CAND_MULT
977 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
979 /* Y = (B + i') * S, S constant
981 ============================
982 X = (B + i') * (S * c) */
983 base
= base_cand
->base_expr
;
984 index
= base_cand
->index
;
985 temp
= tree_to_double_int (base_cand
->stride
)
986 * tree_to_double_int (stride_in
);
987 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
988 ctype
= base_cand
->cand_type
;
989 if (has_single_use (base_in
))
990 savings
= (base_cand
->dead_savings
991 + stmt_cost (base_cand
->cand_stmt
, speed
));
993 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
997 ===========================
999 base
= base_cand
->base_expr
;
1000 index
= base_cand
->index
;
1002 ctype
= base_cand
->cand_type
;
1003 if (has_single_use (base_in
))
1004 savings
= (base_cand
->dead_savings
1005 + stmt_cost (base_cand
->cand_stmt
, speed
));
1007 else if (base_cand
->kind
== CAND_ADD
1008 && base_cand
->index
.is_one ()
1009 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1011 /* Y = B + (1 * S), S constant
1013 ===========================
1015 base
= base_cand
->base_expr
;
1016 index
= tree_to_double_int (base_cand
->stride
);
1018 ctype
= base_cand
->cand_type
;
1019 if (has_single_use (base_in
))
1020 savings
= (base_cand
->dead_savings
1021 + stmt_cost (base_cand
->cand_stmt
, speed
));
1024 if (base_cand
->next_interp
)
1025 base_cand
= lookup_cand (base_cand
->next_interp
);
1032 /* No interpretations had anything useful to propagate, so
1033 produce X = (Y + 0) * c. */
1035 index
= double_int_zero
;
1037 ctype
= TREE_TYPE (base_in
);
1040 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1045 /* Given GS which is a multiply of scalar integers, make an appropriate
1046 entry in the candidate table. If this is a multiply of two SSA names,
1047 create two CAND_MULT interpretations and attempt to find a basis for
1048 each of them. Otherwise, create a single CAND_MULT and attempt to
1052 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1056 /* If this is a multiply of an SSA name with itself, it is highly
1057 unlikely that we will get a strength reduction opportunity, so
1058 don't record it as a candidate. This simplifies the logic for
1059 finding a basis, so if this is removed that must be considered. */
1063 if (TREE_CODE (rhs2
) == SSA_NAME
)
1065 /* Record an interpretation of this statement in the candidate table
1066 assuming RHS1 is the base expression and RHS2 is the stride. */
1067 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1069 /* Add the first interpretation to the statement-candidate mapping. */
1070 add_cand_for_stmt (gs
, c
);
1072 /* Record another interpretation of this statement assuming RHS1
1073 is the stride and RHS2 is the base expression. */
1074 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1075 c
->next_interp
= c2
->cand_num
;
1079 /* Record an interpretation for the multiply-immediate. */
1080 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1082 /* Add the interpretation to the statement-candidate mapping. */
1083 add_cand_for_stmt (gs
, c
);
1087 /* Create a candidate entry for a statement GS, where GS adds two
1088 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1089 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1090 information about the two SSA names into the new candidate.
1091 Return the new candidate. */
1094 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1095 bool subtract_p
, bool speed
)
1097 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1099 unsigned savings
= 0;
1101 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1102 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1104 /* The most useful transformation is a multiply-immediate feeding
1105 an add or subtract. Look for that first. */
1106 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1108 if (addend_cand
->kind
== CAND_MULT
1109 && addend_cand
->index
.is_zero ()
1110 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1112 /* Z = (B + 0) * S, S constant
1114 ===========================
1115 X = Y + ((+/-1 * S) * B) */
1117 index
= tree_to_double_int (addend_cand
->stride
);
1120 stride
= addend_cand
->base_expr
;
1121 ctype
= TREE_TYPE (base_in
);
1122 if (has_single_use (addend_in
))
1123 savings
= (addend_cand
->dead_savings
1124 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1127 if (addend_cand
->next_interp
)
1128 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1133 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1135 if (base_cand
->kind
== CAND_ADD
1136 && (base_cand
->index
.is_zero ()
1137 || operand_equal_p (base_cand
->stride
,
1138 integer_zero_node
, 0)))
1140 /* Y = B + (i' * S), i' * S = 0
1142 ============================
1143 X = B + (+/-1 * Z) */
1144 base
= base_cand
->base_expr
;
1145 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1147 ctype
= base_cand
->cand_type
;
1148 if (has_single_use (base_in
))
1149 savings
= (base_cand
->dead_savings
1150 + stmt_cost (base_cand
->cand_stmt
, speed
));
1152 else if (subtract_p
)
1154 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1156 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1158 if (subtrahend_cand
->kind
== CAND_MULT
1159 && subtrahend_cand
->index
.is_zero ()
1160 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1162 /* Z = (B + 0) * S, S constant
1164 ===========================
1165 Value: X = Y + ((-1 * S) * B) */
1167 index
= tree_to_double_int (subtrahend_cand
->stride
);
1169 stride
= subtrahend_cand
->base_expr
;
1170 ctype
= TREE_TYPE (base_in
);
1171 if (has_single_use (addend_in
))
1172 savings
= (subtrahend_cand
->dead_savings
1173 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1176 if (subtrahend_cand
->next_interp
)
1177 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1179 subtrahend_cand
= NULL
;
1183 if (base_cand
->next_interp
)
1184 base_cand
= lookup_cand (base_cand
->next_interp
);
1191 /* No interpretations had anything useful to propagate, so
1192 produce X = Y + (1 * Z). */
1194 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1196 ctype
= TREE_TYPE (base_in
);
1199 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1204 /* Create a candidate entry for a statement GS, where GS adds SSA
1205 name BASE_IN to constant INDEX_IN. Propagate any known information
1206 about BASE_IN into the new candidate. Return the new candidate. */
1209 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
1211 enum cand_kind kind
= CAND_ADD
;
1212 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1213 double_int index
, multiple
;
1214 unsigned savings
= 0;
1216 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1218 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1220 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
1222 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1223 && index_in
.multiple_of (tree_to_double_int (base_cand
->stride
),
1224 unsigned_p
, &multiple
))
1226 /* Y = (B + i') * S, S constant, c = kS for some integer k
1228 ============================
1229 X = (B + (i'+ k)) * S
1231 Y = B + (i' * S), S constant, c = kS for some integer k
1233 ============================
1234 X = (B + (i'+ k)) * S */
1235 kind
= base_cand
->kind
;
1236 base
= base_cand
->base_expr
;
1237 index
= base_cand
->index
+ multiple
;
1238 stride
= base_cand
->stride
;
1239 ctype
= base_cand
->cand_type
;
1240 if (has_single_use (base_in
))
1241 savings
= (base_cand
->dead_savings
1242 + stmt_cost (base_cand
->cand_stmt
, speed
));
1245 if (base_cand
->next_interp
)
1246 base_cand
= lookup_cand (base_cand
->next_interp
);
1253 /* No interpretations had anything useful to propagate, so
1254 produce X = Y + (c * 1). */
1258 stride
= integer_one_node
;
1259 ctype
= TREE_TYPE (base_in
);
1262 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1267 /* Given GS which is an add or subtract of scalar integers or pointers,
1268 make at least one appropriate entry in the candidate table. */
1271 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1273 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1274 slsr_cand_t c
= NULL
, c2
;
1276 if (TREE_CODE (rhs2
) == SSA_NAME
)
1278 /* First record an interpretation assuming RHS1 is the base expression
1279 and RHS2 is the stride. But it doesn't make sense for the
1280 stride to be a pointer, so don't record a candidate in that case. */
1281 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1283 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1285 /* Add the first interpretation to the statement-candidate
1287 add_cand_for_stmt (gs
, c
);
1290 /* If the two RHS operands are identical, or this is a subtract,
1292 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1295 /* Otherwise, record another interpretation assuming RHS2 is the
1296 base expression and RHS1 is the stride, again provided that the
1297 stride is not a pointer. */
1298 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1300 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1302 c
->next_interp
= c2
->cand_num
;
1304 add_cand_for_stmt (gs
, c2
);
1311 /* Record an interpretation for the add-immediate. */
1312 index
= tree_to_double_int (rhs2
);
1316 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1318 /* Add the interpretation to the statement-candidate mapping. */
1319 add_cand_for_stmt (gs
, c
);
1323 /* Given GS which is a negate of a scalar integer, make an appropriate
1324 entry in the candidate table. A negate is equivalent to a multiply
1328 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1330 /* Record a CAND_MULT interpretation for the multiply by -1. */
1331 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1333 /* Add the interpretation to the statement-candidate mapping. */
1334 add_cand_for_stmt (gs
, c
);
1337 /* Help function for legal_cast_p, operating on two trees. Checks
1338 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1339 for more details. */
1342 legal_cast_p_1 (tree lhs
, tree rhs
)
1344 tree lhs_type
, rhs_type
;
1345 unsigned lhs_size
, rhs_size
;
1346 bool lhs_wraps
, rhs_wraps
;
1348 lhs_type
= TREE_TYPE (lhs
);
1349 rhs_type
= TREE_TYPE (rhs
);
1350 lhs_size
= TYPE_PRECISION (lhs_type
);
1351 rhs_size
= TYPE_PRECISION (rhs_type
);
1352 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1353 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1355 if (lhs_size
< rhs_size
1356 || (rhs_wraps
&& !lhs_wraps
)
1357 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1363 /* Return TRUE if GS is a statement that defines an SSA name from
1364 a conversion and is legal for us to combine with an add and multiply
1365 in the candidate table. For example, suppose we have:
1371 Without the type-cast, we would create a CAND_MULT for D with base B,
1372 index i, and stride S. We want to record this candidate only if it
1373 is equivalent to apply the type cast following the multiply:
1379 We will record the type with the candidate for D. This allows us
1380 to use a similar previous candidate as a basis. If we have earlier seen
1386 we can replace D with
1388 D = D' + (i - i') * S;
1390 But if moving the type-cast would change semantics, we mustn't do this.
1392 This is legitimate for casts from a non-wrapping integral type to
1393 any integral type of the same or larger size. It is not legitimate
1394 to convert a wrapping type to a non-wrapping type, or to a wrapping
1395 type of a different size. I.e., with a wrapping type, we must
1396 assume that the addition B + i could wrap, in which case performing
1397 the multiply before or after one of the "illegal" type casts will
1398 have different semantics. */
1401 legal_cast_p (gimple gs
, tree rhs
)
1403 if (!is_gimple_assign (gs
)
1404 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1407 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1410 /* Given GS which is a cast to a scalar integer type, determine whether
1411 the cast is legal for strength reduction. If so, make at least one
1412 appropriate entry in the candidate table. */
1415 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1418 slsr_cand_t base_cand
, c
, c2
;
1419 unsigned savings
= 0;
1421 if (!legal_cast_p (gs
, rhs1
))
1424 lhs
= gimple_assign_lhs (gs
);
1425 base_cand
= base_cand_from_table (rhs1
);
1426 ctype
= TREE_TYPE (lhs
);
1428 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1432 /* Propagate all data from the base candidate except the type,
1433 which comes from the cast, and the base candidate's cast,
1434 which is no longer applicable. */
1435 if (has_single_use (rhs1
))
1436 savings
= (base_cand
->dead_savings
1437 + stmt_cost (base_cand
->cand_stmt
, speed
));
1439 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1440 base_cand
->base_expr
,
1441 base_cand
->index
, base_cand
->stride
,
1443 if (base_cand
->next_interp
)
1444 base_cand
= lookup_cand (base_cand
->next_interp
);
1451 /* If nothing is known about the RHS, create fresh CAND_ADD and
1452 CAND_MULT interpretations:
1457 The first of these is somewhat arbitrary, but the choice of
1458 1 for the stride simplifies the logic for propagating casts
1460 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1461 integer_one_node
, ctype
, 0);
1462 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1463 integer_one_node
, ctype
, 0);
1464 c
->next_interp
= c2
->cand_num
;
1467 /* Add the first (or only) interpretation to the statement-candidate
1469 add_cand_for_stmt (gs
, c
);
1472 /* Given GS which is a copy of a scalar integer type, make at least one
1473 appropriate entry in the candidate table.
1475 This interface is included for completeness, but is unnecessary
1476 if this pass immediately follows a pass that performs copy
1477 propagation, such as DOM. */
1480 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1482 slsr_cand_t base_cand
, c
, c2
;
1483 unsigned savings
= 0;
1485 base_cand
= base_cand_from_table (rhs1
);
1487 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1491 /* Propagate all data from the base candidate. */
1492 if (has_single_use (rhs1
))
1493 savings
= (base_cand
->dead_savings
1494 + stmt_cost (base_cand
->cand_stmt
, speed
));
1496 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1497 base_cand
->base_expr
,
1498 base_cand
->index
, base_cand
->stride
,
1499 base_cand
->cand_type
, savings
);
1500 if (base_cand
->next_interp
)
1501 base_cand
= lookup_cand (base_cand
->next_interp
);
1508 /* If nothing is known about the RHS, create fresh CAND_ADD and
1509 CAND_MULT interpretations:
1514 The first of these is somewhat arbitrary, but the choice of
1515 1 for the stride simplifies the logic for propagating casts
1517 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1518 integer_one_node
, TREE_TYPE (rhs1
), 0);
1519 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1520 integer_one_node
, TREE_TYPE (rhs1
), 0);
1521 c
->next_interp
= c2
->cand_num
;
1524 /* Add the first (or only) interpretation to the statement-candidate
1526 add_cand_for_stmt (gs
, c
);
1529 /* Find strength-reduction candidates in block BB. */
1532 find_candidates_in_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1535 bool speed
= optimize_bb_for_speed_p (bb
);
1536 gimple_stmt_iterator gsi
;
1538 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1539 slsr_process_phi (gsi_stmt (gsi
), speed
);
1541 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1543 gimple gs
= gsi_stmt (gsi
);
1545 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1546 slsr_process_ref (gs
);
1548 else if (is_gimple_assign (gs
)
1549 && SCALAR_INT_MODE_P
1550 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1552 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1554 switch (gimple_assign_rhs_code (gs
))
1558 rhs1
= gimple_assign_rhs1 (gs
);
1559 rhs2
= gimple_assign_rhs2 (gs
);
1560 /* Should never happen, but currently some buggy situations
1561 in earlier phases put constants in rhs1. */
1562 if (TREE_CODE (rhs1
) != SSA_NAME
)
1566 /* Possible future opportunity: rhs1 of a ptr+ can be
1568 case POINTER_PLUS_EXPR
:
1570 rhs2
= gimple_assign_rhs2 (gs
);
1576 rhs1
= gimple_assign_rhs1 (gs
);
1577 if (TREE_CODE (rhs1
) != SSA_NAME
)
1585 switch (gimple_assign_rhs_code (gs
))
1588 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1592 case POINTER_PLUS_EXPR
:
1594 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1598 slsr_process_neg (gs
, rhs1
, speed
);
1602 slsr_process_cast (gs
, rhs1
, speed
);
1606 slsr_process_copy (gs
, rhs1
, speed
);
1616 /* Dump a candidate for debug. */
1619 dump_candidate (slsr_cand_t c
)
1621 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1622 gimple_bb (c
->cand_stmt
)->index
);
1623 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1627 fputs (" MULT : (", dump_file
);
1628 print_generic_expr (dump_file
, c
->base_expr
, 0);
1629 fputs (" + ", dump_file
);
1630 dump_double_int (dump_file
, c
->index
, false);
1631 fputs (") * ", dump_file
);
1632 print_generic_expr (dump_file
, c
->stride
, 0);
1633 fputs (" : ", dump_file
);
1636 fputs (" ADD : ", dump_file
);
1637 print_generic_expr (dump_file
, c
->base_expr
, 0);
1638 fputs (" + (", dump_file
);
1639 dump_double_int (dump_file
, c
->index
, false);
1640 fputs (" * ", dump_file
);
1641 print_generic_expr (dump_file
, c
->stride
, 0);
1642 fputs (") : ", dump_file
);
1645 fputs (" REF : ", dump_file
);
1646 print_generic_expr (dump_file
, c
->base_expr
, 0);
1647 fputs (" + (", dump_file
);
1648 print_generic_expr (dump_file
, c
->stride
, 0);
1649 fputs (") + ", dump_file
);
1650 dump_double_int (dump_file
, c
->index
, false);
1651 fputs (" : ", dump_file
);
1654 fputs (" PHI : ", dump_file
);
1655 print_generic_expr (dump_file
, c
->base_expr
, 0);
1656 fputs (" + (unknown * ", dump_file
);
1657 print_generic_expr (dump_file
, c
->stride
, 0);
1658 fputs (") : ", dump_file
);
1663 print_generic_expr (dump_file
, c
->cand_type
, 0);
1664 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1665 c
->basis
, c
->dependent
, c
->sibling
);
1666 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1667 c
->next_interp
, c
->dead_savings
);
1669 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1670 fputs ("\n", dump_file
);
1673 /* Dump the candidate vector for debug. */
1676 dump_cand_vec (void)
1681 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1683 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1687 /* Callback used to dump the candidate chains hash table. */
1690 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1692 const_cand_chain_t chain
= *slot
;
1695 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1696 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1698 for (p
= chain
->next
; p
; p
= p
->next
)
1699 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1701 fputs ("\n", dump_file
);
1705 /* Dump the candidate chains. */
1708 dump_cand_chains (void)
1710 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1711 base_cand_map
.traverse_noresize
<void *, ssa_base_cand_dump_callback
> (NULL
);
1712 fputs ("\n", dump_file
);
1715 /* Dump the increment vector for debug. */
1718 dump_incr_vec (void)
1720 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1724 fprintf (dump_file
, "\nIncrement vector:\n\n");
1726 for (i
= 0; i
< incr_vec_len
; i
++)
1728 fprintf (dump_file
, "%3d increment: ", i
);
1729 dump_double_int (dump_file
, incr_vec
[i
].incr
, false);
1730 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1731 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1732 fputs ("\n initializer: ", dump_file
);
1733 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1734 fputs ("\n\n", dump_file
);
1739 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1743 replace_ref (tree
*expr
, slsr_cand_t c
)
1745 tree add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1746 c
->base_expr
, c
->stride
);
1747 tree mem_ref
= fold_build2 (MEM_REF
, TREE_TYPE (*expr
), add_expr
,
1748 double_int_to_tree (c
->cand_type
, c
->index
));
1750 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1751 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1752 TREE_OPERAND (mem_ref
, 0)
1753 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1754 /*simple_p=*/true, NULL
,
1755 /*before=*/true, GSI_SAME_STMT
);
1756 copy_ref_info (mem_ref
, *expr
);
1758 update_stmt (c
->cand_stmt
);
1761 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1762 dependent of candidate C with an equivalent strength-reduced data
1766 replace_refs (slsr_cand_t c
)
1768 if (gimple_vdef (c
->cand_stmt
))
1770 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1771 replace_ref (lhs
, c
);
1775 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1776 replace_ref (rhs
, c
);
1780 replace_refs (lookup_cand (c
->sibling
));
1783 replace_refs (lookup_cand (c
->dependent
));
1786 /* Return TRUE if candidate C is dependent upon a PHI. */
1789 phi_dependent_cand_p (slsr_cand_t c
)
1791 /* A candidate is not necessarily dependent upon a PHI just because
1792 it has a phi definition for its base name. It may have a basis
1793 that relies upon the same phi definition, in which case the PHI
1794 is irrelevant to this candidate. */
1797 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1800 /* Calculate the increment required for candidate C relative to
1804 cand_increment (slsr_cand_t c
)
1808 /* If the candidate doesn't have a basis, just return its own
1809 index. This is useful in record_increments to help us find
1810 an existing initializer. Also, if the candidate's basis is
1811 hidden by a phi, then its own index will be the increment
1812 from the newly introduced phi basis. */
1813 if (!c
->basis
|| phi_dependent_cand_p (c
))
1816 basis
= lookup_cand (c
->basis
);
1817 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1818 return c
->index
- basis
->index
;
1821 /* Calculate the increment required for candidate C relative to
1822 its basis. If we aren't going to generate pointer arithmetic
1823 for this candidate, return the absolute value of that increment
1826 static inline double_int
1827 cand_abs_increment (slsr_cand_t c
)
1829 double_int increment
= cand_increment (c
);
1831 if (!address_arithmetic_p
&& increment
.is_negative ())
1832 increment
= -increment
;
1837 /* Return TRUE iff candidate C has already been replaced under
1838 another interpretation. */
1841 cand_already_replaced (slsr_cand_t c
)
1843 return (gimple_bb (c
->cand_stmt
) == 0);
1846 /* Common logic used by replace_unconditional_candidate and
1847 replace_conditional_candidate. */
1850 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, double_int bump
)
1852 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
1853 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1855 /* It is highly unlikely, but possible, that the resulting
1856 bump doesn't fit in a HWI. Abandon the replacement
1857 in this case. This does not affect siblings or dependents
1858 of C. Restriction to signed HWI is conservative for unsigned
1859 types but allows for safe negation without twisted logic. */
1860 if (bump
.fits_shwi ()
1861 && bump
.to_shwi () != HOST_WIDE_INT_MIN
1862 /* It is not useful to replace casts, copies, or adds of
1863 an SSA name and a constant. */
1864 && cand_code
!= MODIFY_EXPR
1865 && cand_code
!= NOP_EXPR
1866 && cand_code
!= PLUS_EXPR
1867 && cand_code
!= POINTER_PLUS_EXPR
1868 && cand_code
!= MINUS_EXPR
)
1870 enum tree_code code
= PLUS_EXPR
;
1872 gimple stmt_to_print
= NULL
;
1874 /* If the basis name and the candidate's LHS have incompatible
1875 types, introduce a cast. */
1876 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
1877 basis_name
= introduce_cast_before_cand (c
, target_type
, basis_name
);
1878 if (bump
.is_negative ())
1884 bump_tree
= double_int_to_tree (target_type
, bump
);
1886 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1888 fputs ("Replacing: ", dump_file
);
1889 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1892 if (bump
.is_zero ())
1894 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1895 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1896 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1897 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1898 gsi_replace (&gsi
, copy_stmt
, false);
1899 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1900 stmt_to_print
= copy_stmt
;
1905 if (cand_code
!= NEGATE_EXPR
) {
1906 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1907 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1909 if (cand_code
!= NEGATE_EXPR
1910 && ((operand_equal_p (rhs1
, basis_name
, 0)
1911 && operand_equal_p (rhs2
, bump_tree
, 0))
1912 || (operand_equal_p (rhs1
, bump_tree
, 0)
1913 && operand_equal_p (rhs2
, basis_name
, 0))))
1915 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1917 fputs ("(duplicate, not actually replacing)", dump_file
);
1918 stmt_to_print
= c
->cand_stmt
;
1923 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1924 gimple_assign_set_rhs_with_ops (&gsi
, code
,
1925 basis_name
, bump_tree
);
1926 update_stmt (gsi_stmt (gsi
));
1927 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1928 stmt_to_print
= gsi_stmt (gsi
);
1932 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1934 fputs ("With: ", dump_file
);
1935 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
1936 fputs ("\n", dump_file
);
1941 /* Replace candidate C with an add or subtract. Note that we only
1942 operate on CAND_MULTs with known strides, so we will never generate
1943 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
1944 X = Y + ((i - i') * S), as described in the module commentary. The
1945 folded value ((i - i') * S) is referred to here as the "bump." */
1948 replace_unconditional_candidate (slsr_cand_t c
)
1951 double_int stride
, bump
;
1953 if (cand_already_replaced (c
))
1956 basis
= lookup_cand (c
->basis
);
1957 stride
= tree_to_double_int (c
->stride
);
1958 bump
= cand_increment (c
) * stride
;
1960 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
);
1963 /* Return the index in the increment vector of the given INCREMENT. */
1965 static inline unsigned
1966 incr_vec_index (double_int increment
)
1970 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
1973 gcc_assert (i
< incr_vec_len
);
1977 /* Create a new statement along edge E to add BASIS_NAME to the product
1978 of INCREMENT and the stride of candidate C. Create and return a new
1979 SSA name from *VAR to be used as the LHS of the new statement.
1980 KNOWN_STRIDE is true iff C's stride is a constant. */
1983 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
1984 double_int increment
, edge e
, location_t loc
,
1987 basic_block insert_bb
;
1988 gimple_stmt_iterator gsi
;
1989 tree lhs
, basis_type
;
1992 /* If the add candidate along this incoming edge has the same
1993 index as C's hidden basis, the hidden basis represents this
1995 if (increment
.is_zero ())
1998 basis_type
= TREE_TYPE (basis_name
);
1999 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2004 enum tree_code code
= PLUS_EXPR
;
2005 double_int bump
= increment
* tree_to_double_int (c
->stride
);
2006 if (bump
.is_negative ())
2012 bump_tree
= double_int_to_tree (basis_type
, bump
);
2013 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2019 bool negate_incr
= (!address_arithmetic_p
&& increment
.is_negative ());
2020 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2022 if (incr_vec
[i
].initializer
)
2024 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2025 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2026 incr_vec
[i
].initializer
);
2028 else if (increment
.is_one ())
2029 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, lhs
, basis_name
,
2031 else if (increment
.is_minus_one ())
2032 new_stmt
= gimple_build_assign_with_ops (MINUS_EXPR
, lhs
, basis_name
,
2038 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2039 gsi
= gsi_last_bb (insert_bb
);
2041 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2042 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2044 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2046 gimple_set_location (new_stmt
, loc
);
2048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2050 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2051 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2057 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2058 is hidden by the phi node FROM_PHI, create a new phi node in the same
2059 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2060 with its phi arguments representing conditional adjustments to the
2061 hidden basis along conditional incoming paths. Those adjustments are
2062 made by creating add statements (and sometimes recursively creating
2063 phis) along those incoming paths. LOC is the location to attach to
2064 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2068 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2069 location_t loc
, bool known_stride
)
2075 slsr_cand_t basis
= lookup_cand (c
->basis
);
2076 int nargs
= gimple_phi_num_args (from_phi
);
2077 basic_block phi_bb
= gimple_bb (from_phi
);
2078 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2079 phi_args
.create (nargs
);
2081 /* Process each argument of the existing phi that represents
2082 conditionally-executed add candidates. */
2083 for (i
= 0; i
< nargs
; i
++)
2085 edge e
= (*phi_bb
->preds
)[i
];
2086 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2089 /* If the phi argument is the base name of the CAND_PHI, then
2090 this incoming arc should use the hidden basis. */
2091 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2092 if (basis
->index
.is_zero ())
2093 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2096 double_int incr
= -basis
->index
;
2097 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2098 e
, loc
, known_stride
);
2102 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2104 /* If there is another phi along this incoming edge, we must
2105 process it in the same fashion to ensure that all basis
2106 adjustments are made along its incoming edges. */
2107 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2108 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2112 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2113 double_int diff
= arg_cand
->index
- basis
->index
;
2114 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2115 e
, loc
, known_stride
);
2119 /* Because of recursion, we need to save the arguments in a vector
2120 so we can create the PHI statement all at once. Otherwise the
2121 storage for the half-created PHI can be reclaimed. */
2122 phi_args
.safe_push (feeding_def
);
2125 /* Create the new phi basis. */
2126 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2127 phi
= create_phi_node (name
, phi_bb
);
2128 SSA_NAME_DEF_STMT (name
) = phi
;
2130 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2132 edge e
= (*phi_bb
->preds
)[i
];
2133 add_phi_arg (phi
, phi_arg
, e
, loc
);
2138 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2140 fputs ("Introducing new phi basis: ", dump_file
);
2141 print_gimple_stmt (dump_file
, phi
, 0, 0);
2147 /* Given a candidate C whose basis is hidden by at least one intervening
2148 phi, introduce a matching number of new phis to represent its basis
2149 adjusted by conditional increments along possible incoming paths. Then
2150 replace C as though it were an unconditional candidate, using the new
2154 replace_conditional_candidate (slsr_cand_t c
)
2156 tree basis_name
, name
;
2159 double_int stride
, bump
;
2161 /* Look up the LHS SSA name from C's basis. This will be the
2162 RHS1 of the adds we will introduce to create new phi arguments. */
2163 basis
= lookup_cand (c
->basis
);
2164 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2166 /* Create a new phi statement which will represent C's true basis
2167 after the transformation is complete. */
2168 loc
= gimple_location (c
->cand_stmt
);
2169 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2170 basis_name
, loc
, KNOWN_STRIDE
);
2171 /* Replace C with an add of the new basis phi and a constant. */
2172 stride
= tree_to_double_int (c
->stride
);
2173 bump
= c
->index
* stride
;
2175 replace_mult_candidate (c
, name
, bump
);
2178 /* Compute the expected costs of inserting basis adjustments for
2179 candidate C with phi-definition PHI. The cost of inserting
2180 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2181 which are themselves phi results, recursively calculate costs
2182 for those phis as well. */
2185 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2189 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2191 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2193 tree arg
= gimple_phi_arg_def (phi
, i
);
2195 if (arg
!= phi_cand
->base_expr
)
2197 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2199 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2200 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2203 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2205 if (arg_cand
->index
!= c
->index
)
2206 cost
+= one_add_cost
;
2214 /* For candidate C, each sibling of candidate C, and each dependent of
2215 candidate C, determine whether the candidate is dependent upon a
2216 phi that hides its basis. If not, replace the candidate unconditionally.
2217 Otherwise, determine whether the cost of introducing compensation code
2218 for the candidate is offset by the gains from strength reduction. If
2219 so, replace the candidate and introduce the compensation code. */
2222 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2224 if (phi_dependent_cand_p (c
))
2226 if (c
->kind
== CAND_MULT
)
2228 /* A candidate dependent upon a phi will replace a multiply by
2229 a constant with an add, and will insert at most one add for
2230 each phi argument. Add these costs with the potential dead-code
2231 savings to determine profitability. */
2232 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2233 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2234 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2235 tree phi_result
= gimple_phi_result (phi
);
2236 int one_add_cost
= add_cost (speed
,
2237 TYPE_MODE (TREE_TYPE (phi_result
)));
2238 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2239 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2241 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2243 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2244 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2245 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2246 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2247 fprintf (dump_file
, " cost = %d\n", cost
);
2248 if (cost
<= COST_NEUTRAL
)
2249 fputs (" Replacing...\n", dump_file
);
2251 fputs (" Not replaced.\n", dump_file
);
2254 if (cost
<= COST_NEUTRAL
)
2255 replace_conditional_candidate (c
);
2259 replace_unconditional_candidate (c
);
2262 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2265 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2268 /* Count the number of candidates in the tree rooted at C that have
2269 not already been replaced under other interpretations. */
2272 count_candidates (slsr_cand_t c
)
2274 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2277 count
+= count_candidates (lookup_cand (c
->sibling
));
2280 count
+= count_candidates (lookup_cand (c
->dependent
));
2285 /* Increase the count of INCREMENT by one in the increment vector.
2286 INCREMENT is associated with candidate C. If INCREMENT is to be
2287 conditionally executed as part of a conditional candidate replacement,
2288 IS_PHI_ADJUST is true, otherwise false. If an initializer
2289 T_0 = stride * I is provided by a candidate that dominates all
2290 candidates with the same increment, also record T_0 for subsequent use. */
2293 record_increment (slsr_cand_t c
, double_int increment
, bool is_phi_adjust
)
2298 /* Treat increments that differ only in sign as identical so as to
2299 share initializers, unless we are generating pointer arithmetic. */
2300 if (!address_arithmetic_p
&& increment
.is_negative ())
2301 increment
= -increment
;
2303 for (i
= 0; i
< incr_vec_len
; i
++)
2305 if (incr_vec
[i
].incr
== increment
)
2307 incr_vec
[i
].count
++;
2310 /* If we previously recorded an initializer that doesn't
2311 dominate this candidate, it's not going to be useful to
2313 if (incr_vec
[i
].initializer
2314 && !dominated_by_p (CDI_DOMINATORS
,
2315 gimple_bb (c
->cand_stmt
),
2316 incr_vec
[i
].init_bb
))
2318 incr_vec
[i
].initializer
= NULL_TREE
;
2319 incr_vec
[i
].init_bb
= NULL
;
2328 /* The first time we see an increment, create the entry for it.
2329 If this is the root candidate which doesn't have a basis, set
2330 the count to zero. We're only processing it so it can possibly
2331 provide an initializer for other candidates. */
2332 incr_vec
[incr_vec_len
].incr
= increment
;
2333 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2334 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2336 /* Optimistically record the first occurrence of this increment
2337 as providing an initializer (if it does); we will revise this
2338 opinion later if it doesn't dominate all other occurrences.
2339 Exception: increments of -1, 0, 1 never need initializers;
2340 and phi adjustments don't ever provide initializers. */
2341 if (c
->kind
== CAND_ADD
2343 && c
->index
== increment
2344 && (increment
.sgt (double_int_one
)
2345 || increment
.slt (double_int_minus_one
))
2346 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2347 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2349 tree t0
= NULL_TREE
;
2350 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2351 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2352 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2354 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2357 && SSA_NAME_DEF_STMT (t0
)
2358 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2360 incr_vec
[incr_vec_len
].initializer
= t0
;
2361 incr_vec
[incr_vec_len
++].init_bb
2362 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2366 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2367 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2372 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2373 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2378 /* Given phi statement PHI that hides a candidate from its BASIS, find
2379 the increments along each incoming arc (recursively handling additional
2380 phis that may be present) and record them. These increments are the
2381 difference in index between the index-adjusting statements and the
2382 index of the basis. */
2385 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2388 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2390 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2392 tree arg
= gimple_phi_arg_def (phi
, i
);
2394 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2396 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2398 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2399 record_phi_increments (basis
, arg_def
);
2402 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2403 double_int diff
= arg_cand
->index
- basis
->index
;
2404 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2410 /* Determine how many times each unique increment occurs in the set
2411 of candidates rooted at C's parent, recording the data in the
2412 increment vector. For each unique increment I, if an initializer
2413 T_0 = stride * I is provided by a candidate that dominates all
2414 candidates with the same increment, also record T_0 for subsequent
2418 record_increments (slsr_cand_t c
)
2420 if (!cand_already_replaced (c
))
2422 if (!phi_dependent_cand_p (c
))
2423 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2426 /* A candidate with a basis hidden by a phi will have one
2427 increment for its relationship to the index represented by
2428 the phi, and potentially additional increments along each
2429 incoming edge. For the root of the dependency tree (which
2430 has no basis), process just the initial index in case it has
2431 an initializer that can be used by subsequent candidates. */
2432 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2435 record_phi_increments (lookup_cand (c
->basis
),
2436 lookup_cand (c
->def_phi
)->cand_stmt
);
2441 record_increments (lookup_cand (c
->sibling
));
2444 record_increments (lookup_cand (c
->dependent
));
2447 /* Add up and return the costs of introducing add statements that
2448 require the increment INCR on behalf of candidate C and phi
2449 statement PHI. Accumulate into *SAVINGS the potential savings
2450 from removing existing statements that feed PHI and have no other
2454 phi_incr_cost (slsr_cand_t c
, double_int incr
, gimple phi
, int *savings
)
2458 slsr_cand_t basis
= lookup_cand (c
->basis
);
2459 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2461 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2463 tree arg
= gimple_phi_arg_def (phi
, i
);
2465 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2467 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2469 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2471 int feeding_savings
= 0;
2472 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2473 if (has_single_use (gimple_phi_result (arg_def
)))
2474 *savings
+= feeding_savings
;
2478 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2479 double_int diff
= arg_cand
->index
- basis
->index
;
2483 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2484 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2485 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2486 if (has_single_use (lhs
))
2487 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2496 /* Return the first candidate in the tree rooted at C that has not
2497 already been replaced, favoring siblings over dependents. */
2500 unreplaced_cand_in_tree (slsr_cand_t c
)
2502 if (!cand_already_replaced (c
))
2507 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2514 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2522 /* Return TRUE if the candidates in the tree rooted at C should be
2523 optimized for speed, else FALSE. We estimate this based on the block
2524 containing the most dominant candidate in the tree that has not yet
2528 optimize_cands_for_speed_p (slsr_cand_t c
)
2530 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2532 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2535 /* Add COST_IN to the lowest cost of any dependent path starting at
2536 candidate C or any of its siblings, counting only candidates along
2537 such paths with increment INCR. Assume that replacing a candidate
2538 reduces cost by REPL_SAVINGS. Also account for savings from any
2539 statements that would go dead. If COUNT_PHIS is true, include
2540 costs of introducing feeding statements for conditional candidates. */
2543 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2544 double_int incr
, bool count_phis
)
2546 int local_cost
, sib_cost
, savings
= 0;
2547 double_int cand_incr
= cand_abs_increment (c
);
2549 if (cand_already_replaced (c
))
2550 local_cost
= cost_in
;
2551 else if (incr
== cand_incr
)
2552 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2554 local_cost
= cost_in
- c
->dead_savings
;
2557 && phi_dependent_cand_p (c
)
2558 && !cand_already_replaced (c
))
2560 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2561 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2563 if (has_single_use (gimple_phi_result (phi
)))
2564 local_cost
-= savings
;
2568 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2569 lookup_cand (c
->dependent
), incr
,
2574 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2575 lookup_cand (c
->sibling
), incr
,
2577 local_cost
= MIN (local_cost
, sib_cost
);
2583 /* Compute the total savings that would accrue from all replacements
2584 in the candidate tree rooted at C, counting only candidates with
2585 increment INCR. Assume that replacing a candidate reduces cost
2586 by REPL_SAVINGS. Also account for savings from statements that
2590 total_savings (int repl_savings
, slsr_cand_t c
, double_int incr
,
2594 double_int cand_incr
= cand_abs_increment (c
);
2596 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2597 savings
+= repl_savings
+ c
->dead_savings
;
2600 && phi_dependent_cand_p (c
)
2601 && !cand_already_replaced (c
))
2603 int phi_savings
= 0;
2604 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2605 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2607 if (has_single_use (gimple_phi_result (phi
)))
2608 savings
+= phi_savings
;
2612 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2616 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2622 /* Use target-specific costs to determine and record which increments
2623 in the current candidate tree are profitable to replace, assuming
2624 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2627 One slight limitation here is that we don't account for the possible
2628 introduction of casts in some cases. See replace_one_candidate for
2629 the cases where these are introduced. This should probably be cleaned
2633 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
2637 for (i
= 0; i
< incr_vec_len
; i
++)
2639 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2641 /* If somehow this increment is bigger than a HWI, we won't
2642 be optimizing candidates that use it. And if the increment
2643 has a count of zero, nothing will be done with it. */
2644 if (!incr_vec
[i
].incr
.fits_shwi () || !incr_vec
[i
].count
)
2645 incr_vec
[i
].cost
= COST_INFINITE
;
2647 /* Increments of 0, 1, and -1 are always profitable to replace,
2648 because they always replace a multiply or add with an add or
2649 copy, and may cause one or more existing instructions to go
2650 dead. Exception: -1 can't be assumed to be profitable for
2651 pointer addition. */
2655 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2656 != POINTER_PLUS_EXPR
)))
2657 incr_vec
[i
].cost
= COST_NEUTRAL
;
2659 /* FORNOW: If we need to add an initializer, give up if a cast from
2660 the candidate's type to its stride's type can lose precision.
2661 This could eventually be handled better by expressly retaining the
2662 result of a cast to a wider type in the stride. Example:
2667 _4 = x + _3; ADD: x + (10 * _1) : int
2669 _6 = x + _3; ADD: x + (15 * _1) : int
2671 Right now replacing _6 would cause insertion of an initializer
2672 of the form "short int T = _1 * 5;" followed by a cast to
2673 int, which could overflow incorrectly. Had we recorded _2 or
2674 (int)_1 as the stride, this wouldn't happen. However, doing
2675 this breaks other opportunities, so this will require some
2677 else if (!incr_vec
[i
].initializer
2678 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2679 && !legal_cast_p_1 (first_dep
->stride
,
2680 gimple_assign_lhs (first_dep
->cand_stmt
)))
2682 incr_vec
[i
].cost
= COST_INFINITE
;
2684 /* If we need to add an initializer, make sure we don't introduce
2685 a multiply by a pointer type, which can happen in certain cast
2686 scenarios. FIXME: When cleaning up these cast issues, we can
2687 afford to introduce the multiply provided we cast out to an
2688 unsigned int of appropriate size. */
2689 else if (!incr_vec
[i
].initializer
2690 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2691 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2693 incr_vec
[i
].cost
= COST_INFINITE
;
2695 /* For any other increment, if this is a multiply candidate, we
2696 must introduce a temporary T and initialize it with
2697 T_0 = stride * increment. When optimizing for speed, walk the
2698 candidate tree to calculate the best cost reduction along any
2699 path; if it offsets the fixed cost of inserting the initializer,
2700 replacing the increment is profitable. When optimizing for
2701 size, instead calculate the total cost reduction from replacing
2702 all candidates with this increment. */
2703 else if (first_dep
->kind
== CAND_MULT
)
2705 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2706 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2708 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2709 incr_vec
[i
].incr
, COUNT_PHIS
);
2711 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2714 incr_vec
[i
].cost
= cost
;
2717 /* If this is an add candidate, the initializer may already
2718 exist, so only calculate the cost of the initializer if it
2719 doesn't. We are replacing one add with another here, so the
2720 known replacement savings is zero. We will account for removal
2721 of dead instructions in lowest_cost_path or total_savings. */
2725 if (!incr_vec
[i
].initializer
)
2726 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2729 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2732 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2735 incr_vec
[i
].cost
= cost
;
2740 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2741 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2742 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2743 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2744 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2747 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2748 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2764 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2766 /* If both candidates are in the same block, the earlier
2768 if (bb1
== ncd
&& bb2
== ncd
)
2770 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2776 /* Otherwise, if one of them produced a candidate in the
2777 dominator, that one wins. */
2778 else if (bb1
== ncd
)
2781 else if (bb2
== ncd
)
2784 /* If neither matches the dominator, neither wins. */
2791 /* Consider all candidates that feed PHI. Find the nearest common
2792 dominator of those candidates requiring the given increment INCR.
2793 Further find and return the nearest common dominator of this result
2794 with block NCD. If the returned block contains one or more of the
2795 candidates, return the earliest candidate in the block in *WHERE. */
2798 ncd_with_phi (slsr_cand_t c
, double_int incr
, gimple phi
,
2799 basic_block ncd
, slsr_cand_t
*where
)
2802 slsr_cand_t basis
= lookup_cand (c
->basis
);
2803 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2805 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2807 tree arg
= gimple_phi_arg_def (phi
, i
);
2809 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2811 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2813 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2814 ncd
= ncd_with_phi (c
, incr
, arg_def
, ncd
, where
);
2817 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2818 double_int diff
= arg_cand
->index
- basis
->index
;
2820 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
2821 ncd
= ncd_for_two_cands (ncd
, gimple_bb (arg_cand
->cand_stmt
),
2822 *where
, arg_cand
, where
);
2830 /* Consider the candidate C together with any candidates that feed
2831 C's phi dependence (if any). Find and return the nearest common
2832 dominator of those candidates requiring the given increment INCR.
2833 If the returned block contains one or more of the candidates,
2834 return the earliest candidate in the block in *WHERE. */
2837 ncd_of_cand_and_phis (slsr_cand_t c
, double_int incr
, slsr_cand_t
*where
)
2839 basic_block ncd
= NULL
;
2841 if (cand_abs_increment (c
) == incr
)
2843 ncd
= gimple_bb (c
->cand_stmt
);
2847 if (phi_dependent_cand_p (c
))
2848 ncd
= ncd_with_phi (c
, incr
, lookup_cand (c
->def_phi
)->cand_stmt
,
2854 /* Consider all candidates in the tree rooted at C for which INCR
2855 represents the required increment of C relative to its basis.
2856 Find and return the basic block that most nearly dominates all
2857 such candidates. If the returned block contains one or more of
2858 the candidates, return the earliest candidate in the block in
2862 nearest_common_dominator_for_cands (slsr_cand_t c
, double_int incr
,
2865 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
2866 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
2868 /* First find the NCD of all siblings and dependents. */
2870 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
2873 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
2875 if (!sib_ncd
&& !dep_ncd
)
2880 else if (sib_ncd
&& !dep_ncd
)
2882 new_where
= sib_where
;
2885 else if (dep_ncd
&& !sib_ncd
)
2887 new_where
= dep_where
;
2891 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
2892 dep_where
, &new_where
);
2894 /* If the candidate's increment doesn't match the one we're interested
2895 in (and nor do any increments for feeding defs of a phi-dependence),
2896 then the result depends only on siblings and dependents. */
2897 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
2899 if (!this_ncd
|| cand_already_replaced (c
))
2905 /* Otherwise, compare this candidate with the result from all siblings
2907 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
2912 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
2915 profitable_increment_p (unsigned index
)
2917 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
2920 /* For each profitable increment in the increment vector not equal to
2921 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
2922 dominator of all statements in the candidate chain rooted at C
2923 that require that increment, and insert an initializer
2924 T_0 = stride * increment at that location. Record T_0 with the
2925 increment record. */
2928 insert_initializers (slsr_cand_t c
)
2932 for (i
= 0; i
< incr_vec_len
; i
++)
2935 slsr_cand_t where
= NULL
;
2937 tree stride_type
, new_name
, incr_tree
;
2938 double_int incr
= incr_vec
[i
].incr
;
2940 if (!profitable_increment_p (i
)
2942 || (incr
.is_minus_one ()
2943 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
2947 /* We may have already identified an existing initializer that
2949 if (incr_vec
[i
].initializer
)
2951 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2953 fputs ("Using existing initializer: ", dump_file
);
2954 print_gimple_stmt (dump_file
,
2955 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
2961 /* Find the block that most closely dominates all candidates
2962 with this increment. If there is at least one candidate in
2963 that block, the earliest one will be returned in WHERE. */
2964 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
2966 /* Create a new SSA name to hold the initializer's value. */
2967 stride_type
= TREE_TYPE (c
->stride
);
2968 new_name
= make_temp_ssa_name (stride_type
, NULL
, "slsr");
2969 incr_vec
[i
].initializer
= new_name
;
2971 /* Create the initializer and insert it in the latest possible
2972 dominating position. */
2973 incr_tree
= double_int_to_tree (stride_type
, incr
);
2974 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
2975 c
->stride
, incr_tree
);
2978 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
2979 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2980 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
2984 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2985 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
2987 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2988 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2990 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
2992 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
2995 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2997 fputs ("Inserting initializer: ", dump_file
);
2998 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3003 /* Return TRUE iff all required increments for candidates feeding PHI
3004 are profitable to replace on behalf of candidate C. */
3007 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3010 slsr_cand_t basis
= lookup_cand (c
->basis
);
3011 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3013 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3015 tree arg
= gimple_phi_arg_def (phi
, i
);
3017 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3019 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3021 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3023 if (!all_phi_incrs_profitable (c
, arg_def
))
3029 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3030 double_int increment
= arg_cand
->index
- basis
->index
;
3032 if (!address_arithmetic_p
&& increment
.is_negative ())
3033 increment
= -increment
;
3035 j
= incr_vec_index (increment
);
3037 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3039 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3041 print_gimple_stmt (dump_file
, phi
, 0, 0);
3042 fputs (" increment: ", dump_file
);
3043 dump_double_int (dump_file
, increment
, false);
3044 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3045 if (profitable_increment_p (j
))
3046 fputs (" Replacing...\n", dump_file
);
3048 fputs (" Not replaced.\n", dump_file
);
3051 if (!profitable_increment_p (j
))
3060 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3061 type TO_TYPE, and insert it in front of the statement represented
3062 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3063 the new SSA name. */
3066 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
, tree from_expr
)
3070 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3072 cast_lhs
= make_temp_ssa_name (to_type
, NULL
, "slsr");
3073 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
3074 from_expr
, NULL_TREE
);
3075 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3076 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3078 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3080 fputs (" Inserting: ", dump_file
);
3081 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3087 /* Replace the RHS of the statement represented by candidate C with
3088 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3089 leave C unchanged or just interchange its operands. The original
3090 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3091 If the replacement was made and we are doing a details dump,
3092 return the revised statement, else NULL. */
3095 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3096 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3099 if (new_code
!= old_code
3100 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3101 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3102 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3103 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3105 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3106 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3107 update_stmt (gsi_stmt (gsi
));
3109 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3110 return gsi_stmt (gsi
);
3113 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3114 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3119 /* Strength-reduce the statement represented by candidate C by replacing
3120 it with an equivalent addition or subtraction. I is the index into
3121 the increment vector identifying C's increment. NEW_VAR is used to
3122 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3123 is the rhs1 to use in creating the add/subtract. */
3126 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree basis_name
)
3128 gimple stmt_to_print
= NULL
;
3129 tree orig_rhs1
, orig_rhs2
;
3131 enum tree_code orig_code
, repl_code
;
3132 double_int cand_incr
;
3134 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3135 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3136 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3137 cand_incr
= cand_increment (c
);
3139 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3141 fputs ("Replacing: ", dump_file
);
3142 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3143 stmt_to_print
= c
->cand_stmt
;
3146 if (address_arithmetic_p
)
3147 repl_code
= POINTER_PLUS_EXPR
;
3149 repl_code
= PLUS_EXPR
;
3151 /* If the increment has an initializer T_0, replace the candidate
3152 statement with an add of the basis name and the initializer. */
3153 if (incr_vec
[i
].initializer
)
3155 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3156 tree orig_type
= TREE_TYPE (orig_rhs2
);
3158 if (types_compatible_p (orig_type
, init_type
))
3159 rhs2
= incr_vec
[i
].initializer
;
3161 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3162 incr_vec
[i
].initializer
);
3164 if (incr_vec
[i
].incr
!= cand_incr
)
3166 gcc_assert (repl_code
== PLUS_EXPR
);
3167 repl_code
= MINUS_EXPR
;
3170 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3171 orig_code
, orig_rhs1
, orig_rhs2
,
3175 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3176 with a subtract of the stride from the basis name, a copy
3177 from the basis name, or an add of the stride to the basis
3178 name, respectively. It may be necessary to introduce a
3179 cast (or reuse an existing cast). */
3180 else if (cand_incr
.is_one ())
3182 tree stride_type
= TREE_TYPE (c
->stride
);
3183 tree orig_type
= TREE_TYPE (orig_rhs2
);
3185 if (types_compatible_p (orig_type
, stride_type
))
3188 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3190 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3191 orig_code
, orig_rhs1
, orig_rhs2
,
3195 else if (cand_incr
.is_minus_one ())
3197 tree stride_type
= TREE_TYPE (c
->stride
);
3198 tree orig_type
= TREE_TYPE (orig_rhs2
);
3199 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3201 if (types_compatible_p (orig_type
, stride_type
))
3204 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3206 if (orig_code
!= MINUS_EXPR
3207 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3208 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3210 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3211 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3212 update_stmt (gsi_stmt (gsi
));
3214 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3215 stmt_to_print
= gsi_stmt (gsi
);
3217 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3218 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3221 else if (cand_incr
.is_zero ())
3223 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3224 tree lhs_type
= TREE_TYPE (lhs
);
3225 tree basis_type
= TREE_TYPE (basis_name
);
3227 if (types_compatible_p (lhs_type
, basis_type
))
3229 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3230 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3231 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3232 gsi_replace (&gsi
, copy_stmt
, false);
3234 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3235 stmt_to_print
= copy_stmt
;
3239 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3240 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
3243 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3244 gsi_replace (&gsi
, cast_stmt
, false);
3246 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3247 stmt_to_print
= cast_stmt
;
3253 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3255 fputs ("With: ", dump_file
);
3256 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3257 fputs ("\n", dump_file
);
3261 /* For each candidate in the tree rooted at C, replace it with
3262 an increment if such has been shown to be profitable. */
3265 replace_profitable_candidates (slsr_cand_t c
)
3267 if (!cand_already_replaced (c
))
3269 double_int increment
= cand_abs_increment (c
);
3270 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3273 i
= incr_vec_index (increment
);
3275 /* Only process profitable increments. Nothing useful can be done
3276 to a cast or copy. */
3277 if (profitable_increment_p (i
)
3278 && orig_code
!= MODIFY_EXPR
3279 && orig_code
!= NOP_EXPR
)
3281 if (phi_dependent_cand_p (c
))
3283 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3285 if (all_phi_incrs_profitable (c
, phi
))
3287 /* Look up the LHS SSA name from C's basis. This will be
3288 the RHS1 of the adds we will introduce to create new
3290 slsr_cand_t basis
= lookup_cand (c
->basis
);
3291 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3293 /* Create a new phi statement that will represent C's true
3294 basis after the transformation is complete. */
3295 location_t loc
= gimple_location (c
->cand_stmt
);
3296 tree name
= create_phi_basis (c
, phi
, basis_name
,
3297 loc
, UNKNOWN_STRIDE
);
3299 /* Replace C with an add of the new basis phi and the
3301 replace_one_candidate (c
, i
, name
);
3306 slsr_cand_t basis
= lookup_cand (c
->basis
);
3307 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3308 replace_one_candidate (c
, i
, basis_name
);
3314 replace_profitable_candidates (lookup_cand (c
->sibling
));
3317 replace_profitable_candidates (lookup_cand (c
->dependent
));
3320 /* Analyze costs of related candidates in the candidate vector,
3321 and make beneficial replacements. */
3324 analyze_candidates_and_replace (void)
3329 /* Each candidate that has a null basis and a non-null
3330 dependent is the root of a tree of related statements.
3331 Analyze each tree to determine a subset of those
3332 statements that can be replaced with maximum benefit. */
3333 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3335 slsr_cand_t first_dep
;
3337 if (c
->basis
!= 0 || c
->dependent
== 0)
3340 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3341 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3344 first_dep
= lookup_cand (c
->dependent
);
3346 /* If this is a chain of CAND_REFs, unconditionally replace
3347 each of them with a strength-reduced data reference. */
3348 if (c
->kind
== CAND_REF
)
3351 /* If the common stride of all related candidates is a known
3352 constant, each candidate without a phi-dependence can be
3353 profitably replaced. Each replaces a multiply by a single
3354 add, with the possibility that a feeding add also goes dead.
3355 A candidate with a phi-dependence is replaced only if the
3356 compensation code it requires is offset by the strength
3357 reduction savings. */
3358 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3359 replace_uncond_cands_and_profitable_phis (first_dep
);
3361 /* When the stride is an SSA name, it may still be profitable
3362 to replace some or all of the dependent candidates, depending
3363 on whether the introduced increments can be reused, or are
3364 less expensive to calculate than the replaced statements. */
3368 enum machine_mode mode
;
3371 /* Determine whether we'll be generating pointer arithmetic
3372 when replacing candidates. */
3373 address_arithmetic_p
= (c
->kind
== CAND_ADD
3374 && POINTER_TYPE_P (c
->cand_type
));
3376 /* If all candidates have already been replaced under other
3377 interpretations, nothing remains to be done. */
3378 length
= count_candidates (c
);
3382 /* Construct an array of increments for this candidate chain. */
3383 incr_vec
= XNEWVEC (incr_info
, length
);
3385 record_increments (c
);
3387 /* Determine which increments are profitable to replace. */
3388 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3389 speed
= optimize_cands_for_speed_p (c
);
3390 analyze_increments (first_dep
, mode
, speed
);
3392 /* Insert initializers of the form T_0 = stride * increment
3393 for use in profitable replacements. */
3394 insert_initializers (first_dep
);
3397 /* Perform the replacements. */
3398 replace_profitable_candidates (first_dep
);
3405 execute_strength_reduction (void)
3407 struct dom_walk_data walk_data
;
3409 /* Create the obstack where candidates will reside. */
3410 gcc_obstack_init (&cand_obstack
);
3412 /* Allocate the candidate vector. */
3413 cand_vec
.create (128);
3415 /* Allocate the mapping from statements to candidate indices. */
3416 stmt_cand_map
= pointer_map_create ();
3418 /* Create the obstack where candidate chains will reside. */
3419 gcc_obstack_init (&chain_obstack
);
3421 /* Allocate the mapping from base expressions to candidate chains. */
3422 base_cand_map
.create (500);
3424 /* Initialize the loop optimizer. We need to detect flow across
3425 back edges, and this gives us dominator information as well. */
3426 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3428 /* Set up callbacks for the generic dominator tree walker. */
3429 walk_data
.dom_direction
= CDI_DOMINATORS
;
3430 walk_data
.initialize_block_local_data
= NULL
;
3431 walk_data
.before_dom_children
= find_candidates_in_block
;
3432 walk_data
.after_dom_children
= NULL
;
3433 walk_data
.global_data
= NULL
;
3434 walk_data
.block_local_data_size
= 0;
3435 init_walk_dominator_tree (&walk_data
);
3437 /* Walk the CFG in predominator order looking for strength reduction
3439 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
3441 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3444 dump_cand_chains ();
3447 /* Analyze costs and make appropriate replacements. */
3448 analyze_candidates_and_replace ();
3450 /* Free resources. */
3451 fini_walk_dominator_tree (&walk_data
);
3452 loop_optimizer_finalize ();
3453 base_cand_map
.dispose ();
3454 obstack_free (&chain_obstack
, NULL
);
3455 pointer_map_destroy (stmt_cand_map
);
3456 cand_vec
.release ();
3457 obstack_free (&cand_obstack
, NULL
);
3463 gate_strength_reduction (void)
3465 return flag_tree_slsr
;
3468 struct gimple_opt_pass pass_strength_reduction
=
3473 OPTGROUP_NONE
, /* optinfo_flags */
3474 gate_strength_reduction
, /* gate */
3475 execute_strength_reduction
, /* execute */
3478 0, /* static_pass_number */
3479 TV_GIMPLE_SLSR
, /* tv_id */
3480 PROP_cfg
| PROP_ssa
, /* properties_required */
3481 0, /* properties_provided */
3482 0, /* properties_destroyed */
3483 0, /* todo_flags_start */
3484 TODO_verify_ssa
/* todo_flags_finish */