1 /* Straight-line strength reduction.
2 Copyright (C) 2012 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 will be implemented in four stages, gradually
28 adding more complex candidates:
30 1) Explicit multiplies, known constant multipliers, no
31 conditional increments. (complete)
32 2) Explicit multiplies, unknown constant multipliers,
33 no conditional increments. (complete)
34 3) Implicit multiplies in addressing expressions. (complete)
35 4) Explicit multiplies, conditional increments. (pending)
37 It would also be possible to apply strength reduction to divisions
38 and modulos, but such opportunities are relatively uncommon.
40 Strength reduction is also currently restricted to integer operations.
41 If desired, it could be extended to floating-point operations under
42 control of something like -funsafe-math-optimizations. */
46 #include "coretypes.h"
49 #include "basic-block.h"
50 #include "tree-pass.h"
52 #include "gimple-pretty-print.h"
53 #include "tree-flow.h"
55 #include "pointer-set.h"
58 /* Information about a strength reduction candidate. Each statement
59 in the candidate table represents an expression of one of the
60 following forms (the special case of CAND_REF will be described
63 (CAND_MULT) S1: X = (B + i) * S
64 (CAND_ADD) S1: X = B + (i * S)
66 Here X and B are SSA names, i is an integer constant, and S is
67 either an SSA name or a constant. We call B the "base," i the
68 "index", and S the "stride."
70 Any statement S0 that dominates S1 and is of the form:
72 (CAND_MULT) S0: Y = (B + i') * S
73 (CAND_ADD) S0: Y = B + (i' * S)
75 is called a "basis" for S1. In both cases, S1 may be replaced by
77 S1': X = Y + (i - i') * S,
79 where (i - i') * S is folded to the extent possible.
81 All gimple statements are visited in dominator order, and each
82 statement that may contribute to one of the forms of S1 above is
83 given at least one entry in the candidate table. Such statements
84 include addition, pointer addition, subtraction, multiplication,
85 negation, copies, and nontrivial type casts. If a statement may
86 represent more than one expression of the forms of S1 above,
87 multiple "interpretations" are stored in the table and chained
90 * An add of two SSA names may treat either operand as the base.
91 * A multiply of two SSA names, likewise.
92 * A copy or cast may be thought of as either a CAND_MULT with
93 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
95 Candidate records are allocated from an obstack. They are addressed
96 both from a hash table keyed on S1, and from a vector of candidate
97 pointers arranged in predominator order.
101 Currently we don't recognize:
106 as a strength reduction opportunity, even though this S1 would
107 also be replaceable by the S1' above. This can be added if it
108 comes up in practice.
110 Strength reduction in addressing
111 --------------------------------
112 There is another kind of candidate known as CAND_REF. A CAND_REF
113 describes a statement containing a memory reference having
114 complex addressing that might benefit from strength reduction.
115 Specifically, we are interested in references for which
116 get_inner_reference returns a base address, offset, and bitpos as
119 base: MEM_REF (T1, C1)
120 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
121 bitpos: C4 * BITS_PER_UNIT
123 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
124 arbitrary integer constants. Note that C2 may be zero, in which
125 case the offset will be MULT_EXPR (T2, C3).
127 When this pattern is recognized, the original memory reference
128 can be replaced with:
130 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
133 which distributes the multiply to allow constant folding. When
134 two or more addressing expressions can be represented by MEM_REFs
135 of this form, differing only in the constants C1, C2, and C4,
136 making this substitution produces more efficient addressing during
137 the RTL phases. When there are not at least two expressions with
138 the same values of T1, T2, and C3, there is nothing to be gained
141 Strength reduction of CAND_REFs uses the same infrastructure as
142 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
143 field, MULT_EXPR (T2, C3) in the stride (S) field, and
144 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
145 is thus another CAND_REF with the same B and S values. When at
146 least two CAND_REFs are chained together using the basis relation,
147 each of them is replaced as above, resulting in improved code
148 generation for addressing. */
151 /* Index into the candidate vector, offset by 1. VECs are zero-based,
152 while cand_idx's are one-based, with zero indicating null. */
153 typedef unsigned cand_idx
;
155 /* The kind of candidate. */
165 /* The candidate statement S1. */
168 /* The base expression B: often an SSA name, but not always. */
174 /* The index constant i. */
177 /* The type of the candidate. This is normally the type of base_expr,
178 but casts may have occurred when combining feeding instructions.
179 A candidate can only be a basis for candidates of the same final type.
180 (For CAND_REFs, this is the type to be used for operand 1 of the
181 replacement MEM_REF.) */
184 /* The kind of candidate (CAND_MULT, etc.). */
187 /* Index of this candidate in the candidate vector. */
190 /* Index of the next candidate record for the same statement.
191 A statement may be useful in more than one way (e.g., due to
192 commutativity). So we can have multiple "interpretations"
194 cand_idx next_interp
;
196 /* Index of the basis statement S0, if any, in the candidate vector. */
199 /* First candidate for which this candidate is a basis, if one exists. */
202 /* Next candidate having the same basis as this one. */
205 /* If this is a conditional candidate, the defining PHI statement
206 for the base SSA name B. For future use; always NULL for now. */
209 /* Savings that can be expected from eliminating dead code if this
210 candidate is replaced. */
214 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
215 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
217 /* Pointers to candidates are chained together as part of a mapping
218 from base expressions to the candidates that use them. */
222 /* Base expression for the chain of candidates: often, but not
223 always, an SSA name. */
226 /* Pointer to a candidate. */
230 struct cand_chain_d
*next
;
234 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
235 typedef const struct cand_chain_d
*const_cand_chain_t
;
237 /* Information about a unique "increment" associated with candidates
238 having an SSA name for a stride. An increment is the difference
239 between the index of the candidate and the index of its basis,
240 i.e., (i - i') as discussed in the module commentary.
242 When we are not going to generate address arithmetic we treat
243 increments that differ only in sign as the same, allowing sharing
244 of the cost of initializers. The absolute value of the increment
245 is stored in the incr_info. */
249 /* The increment that relates a candidate to its basis. */
252 /* How many times the increment occurs in the candidate tree. */
255 /* Cost of replacing candidates using this increment. Negative and
256 zero costs indicate replacement should be performed. */
259 /* If this increment is profitable but is not -1, 0, or 1, it requires
260 an initializer T_0 = stride * incr to be found or introduced in the
261 nearest common dominator of all candidates. This field holds T_0
262 for subsequent use. */
265 /* If the initializer was found to already exist, this is the block
266 where it was found. */
270 typedef struct incr_info_d incr_info
, *incr_info_t
;
272 /* Candidates are maintained in a vector. If candidate X dominates
273 candidate Y, then X appears before Y in the vector; but the
274 converse does not necessarily hold. */
275 DEF_VEC_P (slsr_cand_t
);
276 DEF_VEC_ALLOC_P (slsr_cand_t
, heap
);
277 static VEC (slsr_cand_t
, heap
) *cand_vec
;
285 /* Pointer map embodying a mapping from statements to candidates. */
286 static struct pointer_map_t
*stmt_cand_map
;
288 /* Obstack for candidates. */
289 static struct obstack cand_obstack
;
291 /* Hash table embodying a mapping from base exprs to chains of candidates. */
292 static htab_t base_cand_map
;
294 /* Obstack for candidate chains. */
295 static struct obstack chain_obstack
;
297 /* An array INCR_VEC of incr_infos is used during analysis of related
298 candidates having an SSA name for a stride. INCR_VEC_LEN describes
299 its current length. */
300 static incr_info_t incr_vec
;
301 static unsigned incr_vec_len
;
303 /* For a chain of candidates with unknown stride, indicates whether or not
304 we must generate pointer arithmetic when replacing statements. */
305 static bool address_arithmetic_p
;
307 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
310 lookup_cand (cand_idx idx
)
312 return VEC_index (slsr_cand_t
, cand_vec
, idx
- 1);
315 /* Callback to produce a hash value for a candidate chain header. */
318 base_cand_hash (const void *p
)
320 tree base_expr
= ((const_cand_chain_t
) p
)->base_expr
;
321 return iterative_hash_expr (base_expr
, 0);
324 /* Callback when an element is removed from the hash table.
325 We never remove entries until the entire table is released. */
328 base_cand_free (void *p ATTRIBUTE_UNUSED
)
332 /* Callback to return true if two candidate chain headers are equal. */
335 base_cand_eq (const void *p1
, const void *p2
)
337 const_cand_chain_t
const chain1
= (const_cand_chain_t
) p1
;
338 const_cand_chain_t
const chain2
= (const_cand_chain_t
) p2
;
339 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
342 /* Use the base expr from candidate C to look for possible candidates
343 that can serve as a basis for C. Each potential basis must also
344 appear in a block that dominates the candidate statement and have
345 the same stride and type. If more than one possible basis exists,
346 the one with highest index in the vector is chosen; this will be
347 the most immediately dominating basis. */
350 find_basis_for_candidate (slsr_cand_t c
)
352 cand_chain mapping_key
;
354 slsr_cand_t basis
= NULL
;
356 mapping_key
.base_expr
= c
->base_expr
;
357 chain
= (cand_chain_t
) htab_find (base_cand_map
, &mapping_key
);
359 for (; chain
; chain
= chain
->next
)
361 slsr_cand_t one_basis
= chain
->cand
;
363 if (one_basis
->kind
!= c
->kind
364 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
365 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
366 || !dominated_by_p (CDI_DOMINATORS
,
367 gimple_bb (c
->cand_stmt
),
368 gimple_bb (one_basis
->cand_stmt
)))
371 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
377 c
->sibling
= basis
->dependent
;
378 basis
->dependent
= c
->cand_num
;
379 return basis
->cand_num
;
385 /* Record a mapping from the base expression of C to C itself, indicating that
386 C may potentially serve as a basis using that base expression. */
389 record_potential_basis (slsr_cand_t c
)
394 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
395 node
->base_expr
= c
->base_expr
;
398 slot
= htab_find_slot (base_cand_map
, node
, INSERT
);
402 cand_chain_t head
= (cand_chain_t
) (*slot
);
403 node
->next
= head
->next
;
410 /* Allocate storage for a new candidate and initialize its fields.
411 Attempt to find a basis for the candidate. */
414 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
415 double_int index
, tree stride
, tree ctype
,
418 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
424 c
->cand_type
= ctype
;
426 c
->cand_num
= VEC_length (slsr_cand_t
, cand_vec
) + 1;
431 c
->dead_savings
= savings
;
433 VEC_safe_push (slsr_cand_t
, heap
, cand_vec
, c
);
434 c
->basis
= find_basis_for_candidate (c
);
435 record_potential_basis (c
);
440 /* Determine the target cost of statement GS when compiling according
444 stmt_cost (gimple gs
, bool speed
)
446 tree lhs
, rhs1
, rhs2
;
447 enum machine_mode lhs_mode
;
449 gcc_assert (is_gimple_assign (gs
));
450 lhs
= gimple_assign_lhs (gs
);
451 rhs1
= gimple_assign_rhs1 (gs
);
452 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
454 switch (gimple_assign_rhs_code (gs
))
457 rhs2
= gimple_assign_rhs2 (gs
);
459 if (host_integerp (rhs2
, 0))
460 return mult_by_coeff_cost (TREE_INT_CST_LOW (rhs2
), lhs_mode
, speed
);
462 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
463 return mul_cost (speed
, lhs_mode
);
466 case POINTER_PLUS_EXPR
:
468 return add_cost (speed
, lhs_mode
);
471 return neg_cost (speed
, lhs_mode
);
474 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
476 /* Note that we don't assign costs to copies that in most cases
486 /* Look up the defining statement for BASE_IN and return a pointer
487 to its candidate in the candidate table, if any; otherwise NULL.
488 Only CAND_ADD and CAND_MULT candidates are returned. */
491 base_cand_from_table (tree base_in
)
495 gimple def
= SSA_NAME_DEF_STMT (base_in
);
497 return (slsr_cand_t
) NULL
;
499 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
501 if (result
&& (*result
)->kind
!= CAND_REF
)
504 return (slsr_cand_t
) NULL
;
507 /* Add an entry to the statement-to-candidate mapping. */
510 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
512 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
517 /* Look for the following pattern:
519 *PBASE: MEM_REF (T1, C1)
521 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
523 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
525 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
527 *PINDEX: C4 * BITS_PER_UNIT
529 If not present, leave the input values unchanged and return FALSE.
530 Otherwise, modify the input values as follows and return TRUE:
533 *POFFSET: MULT_EXPR (T2, C3)
534 *PINDEX: C1 + (C2 * C3) + C4 */
537 restructure_reference (tree
*pbase
, tree
*poffset
, double_int
*pindex
,
540 tree base
= *pbase
, offset
= *poffset
;
541 double_int index
= *pindex
;
542 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
543 tree mult_op0
, mult_op1
, t1
, t2
, type
;
544 double_int c1
, c2
, c3
, c4
;
548 || TREE_CODE (base
) != MEM_REF
549 || TREE_CODE (offset
) != MULT_EXPR
550 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
551 || !index
.umod (bpu
, FLOOR_MOD_EXPR
).is_zero ())
554 t1
= TREE_OPERAND (base
, 0);
555 c1
= mem_ref_offset (base
);
556 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
558 mult_op0
= TREE_OPERAND (offset
, 0);
559 mult_op1
= TREE_OPERAND (offset
, 1);
561 c3
= tree_to_double_int (mult_op1
);
563 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
565 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
567 t2
= TREE_OPERAND (mult_op0
, 0);
568 c2
= tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
573 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
575 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
577 t2
= TREE_OPERAND (mult_op0
, 0);
578 c2
= -tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
586 c2
= double_int_zero
;
589 c4
= index
.udiv (bpu
, FLOOR_DIV_EXPR
);
592 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, t2
,
593 double_int_to_tree (sizetype
, c3
));
594 *pindex
= c1
+ c2
* c3
+ c4
;
600 /* Given GS which contains a data reference, create a CAND_REF entry in
601 the candidate table and attempt to find a basis. */
604 slsr_process_ref (gimple gs
)
606 tree ref_expr
, base
, offset
, type
;
607 HOST_WIDE_INT bitsize
, bitpos
;
608 enum machine_mode mode
;
609 int unsignedp
, volatilep
;
613 if (gimple_vdef (gs
))
614 ref_expr
= gimple_assign_lhs (gs
);
616 ref_expr
= gimple_assign_rhs1 (gs
);
618 if (!handled_component_p (ref_expr
)
619 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
620 || (TREE_CODE (ref_expr
) == COMPONENT_REF
621 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
624 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
625 &unsignedp
, &volatilep
, false);
626 index
= double_int::from_uhwi (bitpos
);
628 if (!restructure_reference (&base
, &offset
, &index
, &type
))
631 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
634 /* Add the candidate to the statement-candidate mapping. */
635 add_cand_for_stmt (gs
, c
);
638 /* Create a candidate entry for a statement GS, where GS multiplies
639 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
640 about the two SSA names into the new candidate. Return the new
644 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
646 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
648 unsigned savings
= 0;
650 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
652 /* Look at all interpretations of the base candidate, if necessary,
653 to find information to propagate into this candidate. */
654 while (base_cand
&& !base
)
657 if (base_cand
->kind
== CAND_MULT
658 && operand_equal_p (base_cand
->stride
, integer_one_node
, 0))
664 base
= base_cand
->base_expr
;
665 index
= base_cand
->index
;
667 ctype
= base_cand
->cand_type
;
668 if (has_single_use (base_in
))
669 savings
= (base_cand
->dead_savings
670 + stmt_cost (base_cand
->cand_stmt
, speed
));
672 else if (base_cand
->kind
== CAND_ADD
673 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
675 /* Y = B + (i' * S), S constant
677 ============================
678 X = B + ((i' * S) * Z) */
679 base
= base_cand
->base_expr
;
680 index
= base_cand
->index
* tree_to_double_int (base_cand
->stride
);
682 ctype
= base_cand
->cand_type
;
683 if (has_single_use (base_in
))
684 savings
= (base_cand
->dead_savings
685 + stmt_cost (base_cand
->cand_stmt
, speed
));
688 if (base_cand
->next_interp
)
689 base_cand
= lookup_cand (base_cand
->next_interp
);
696 /* No interpretations had anything useful to propagate, so
697 produce X = (Y + 0) * Z. */
699 index
= double_int_zero
;
701 ctype
= TREE_TYPE (base_in
);
704 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
709 /* Create a candidate entry for a statement GS, where GS multiplies
710 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
711 information about BASE_IN into the new candidate. Return the new
715 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
717 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
718 double_int index
, temp
;
719 unsigned savings
= 0;
721 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
723 /* Look at all interpretations of the base candidate, if necessary,
724 to find information to propagate into this candidate. */
725 while (base_cand
&& !base
)
727 if (base_cand
->kind
== CAND_MULT
728 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
730 /* Y = (B + i') * S, S constant
732 ============================
733 X = (B + i') * (S * c) */
734 base
= base_cand
->base_expr
;
735 index
= base_cand
->index
;
736 temp
= tree_to_double_int (base_cand
->stride
)
737 * tree_to_double_int (stride_in
);
738 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
739 ctype
= base_cand
->cand_type
;
740 if (has_single_use (base_in
))
741 savings
= (base_cand
->dead_savings
742 + stmt_cost (base_cand
->cand_stmt
, speed
));
744 else if (base_cand
->kind
== CAND_ADD
745 && operand_equal_p (base_cand
->stride
, integer_one_node
, 0))
749 ===========================
751 base
= base_cand
->base_expr
;
752 index
= base_cand
->index
;
754 ctype
= base_cand
->cand_type
;
755 if (has_single_use (base_in
))
756 savings
= (base_cand
->dead_savings
757 + stmt_cost (base_cand
->cand_stmt
, speed
));
759 else if (base_cand
->kind
== CAND_ADD
760 && base_cand
->index
.is_one ()
761 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
763 /* Y = B + (1 * S), S constant
765 ===========================
767 base
= base_cand
->base_expr
;
768 index
= tree_to_double_int (base_cand
->stride
);
770 ctype
= base_cand
->cand_type
;
771 if (has_single_use (base_in
))
772 savings
= (base_cand
->dead_savings
773 + stmt_cost (base_cand
->cand_stmt
, speed
));
776 if (base_cand
->next_interp
)
777 base_cand
= lookup_cand (base_cand
->next_interp
);
784 /* No interpretations had anything useful to propagate, so
785 produce X = (Y + 0) * c. */
787 index
= double_int_zero
;
789 ctype
= TREE_TYPE (base_in
);
792 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
797 /* Given GS which is a multiply of scalar integers, make an appropriate
798 entry in the candidate table. If this is a multiply of two SSA names,
799 create two CAND_MULT interpretations and attempt to find a basis for
800 each of them. Otherwise, create a single CAND_MULT and attempt to
804 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
808 /* If this is a multiply of an SSA name with itself, it is highly
809 unlikely that we will get a strength reduction opportunity, so
810 don't record it as a candidate. This simplifies the logic for
811 finding a basis, so if this is removed that must be considered. */
815 if (TREE_CODE (rhs2
) == SSA_NAME
)
817 /* Record an interpretation of this statement in the candidate table
818 assuming RHS1 is the base expression and RHS2 is the stride. */
819 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
821 /* Add the first interpretation to the statement-candidate mapping. */
822 add_cand_for_stmt (gs
, c
);
824 /* Record another interpretation of this statement assuming RHS1
825 is the stride and RHS2 is the base expression. */
826 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
827 c
->next_interp
= c2
->cand_num
;
831 /* Record an interpretation for the multiply-immediate. */
832 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
834 /* Add the interpretation to the statement-candidate mapping. */
835 add_cand_for_stmt (gs
, c
);
839 /* Create a candidate entry for a statement GS, where GS adds two
840 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
841 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
842 information about the two SSA names into the new candidate.
843 Return the new candidate. */
846 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
847 bool subtract_p
, bool speed
)
849 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
851 unsigned savings
= 0;
853 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
854 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
856 /* The most useful transformation is a multiply-immediate feeding
857 an add or subtract. Look for that first. */
858 while (addend_cand
&& !base
)
860 if (addend_cand
->kind
== CAND_MULT
861 && addend_cand
->index
.is_zero ()
862 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
864 /* Z = (B + 0) * S, S constant
866 ===========================
867 X = Y + ((+/-1 * S) * B) */
869 index
= tree_to_double_int (addend_cand
->stride
);
872 stride
= addend_cand
->base_expr
;
873 ctype
= TREE_TYPE (base_in
);
874 if (has_single_use (addend_in
))
875 savings
= (addend_cand
->dead_savings
876 + stmt_cost (addend_cand
->cand_stmt
, speed
));
879 if (addend_cand
->next_interp
)
880 addend_cand
= lookup_cand (addend_cand
->next_interp
);
885 while (base_cand
&& !base
)
887 if (base_cand
->kind
== CAND_ADD
888 && (base_cand
->index
.is_zero ()
889 || operand_equal_p (base_cand
->stride
,
890 integer_zero_node
, 0)))
892 /* Y = B + (i' * S), i' * S = 0
894 ============================
895 X = B + (+/-1 * Z) */
896 base
= base_cand
->base_expr
;
897 index
= subtract_p
? double_int_minus_one
: double_int_one
;
899 ctype
= base_cand
->cand_type
;
900 if (has_single_use (base_in
))
901 savings
= (base_cand
->dead_savings
902 + stmt_cost (base_cand
->cand_stmt
, speed
));
906 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
908 while (subtrahend_cand
&& !base
)
910 if (subtrahend_cand
->kind
== CAND_MULT
911 && subtrahend_cand
->index
.is_zero ()
912 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
914 /* Z = (B + 0) * S, S constant
916 ===========================
917 Value: X = Y + ((-1 * S) * B) */
919 index
= tree_to_double_int (subtrahend_cand
->stride
);
921 stride
= subtrahend_cand
->base_expr
;
922 ctype
= TREE_TYPE (base_in
);
923 if (has_single_use (addend_in
))
924 savings
= (subtrahend_cand
->dead_savings
925 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
928 if (subtrahend_cand
->next_interp
)
929 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
931 subtrahend_cand
= NULL
;
935 if (base_cand
->next_interp
)
936 base_cand
= lookup_cand (base_cand
->next_interp
);
943 /* No interpretations had anything useful to propagate, so
944 produce X = Y + (1 * Z). */
946 index
= subtract_p
? double_int_minus_one
: double_int_one
;
948 ctype
= TREE_TYPE (base_in
);
951 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
956 /* Create a candidate entry for a statement GS, where GS adds SSA
957 name BASE_IN to constant INDEX_IN. Propagate any known information
958 about BASE_IN into the new candidate. Return the new candidate. */
961 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
963 enum cand_kind kind
= CAND_ADD
;
964 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
965 double_int index
, multiple
;
966 unsigned savings
= 0;
968 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
970 while (base_cand
&& !base
)
972 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
974 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
975 && index_in
.multiple_of (tree_to_double_int (base_cand
->stride
),
976 unsigned_p
, &multiple
))
978 /* Y = (B + i') * S, S constant, c = kS for some integer k
980 ============================
981 X = (B + (i'+ k)) * S
983 Y = B + (i' * S), S constant, c = kS for some integer k
985 ============================
986 X = (B + (i'+ k)) * S */
987 kind
= base_cand
->kind
;
988 base
= base_cand
->base_expr
;
989 index
= base_cand
->index
+ multiple
;
990 stride
= base_cand
->stride
;
991 ctype
= base_cand
->cand_type
;
992 if (has_single_use (base_in
))
993 savings
= (base_cand
->dead_savings
994 + stmt_cost (base_cand
->cand_stmt
, speed
));
997 if (base_cand
->next_interp
)
998 base_cand
= lookup_cand (base_cand
->next_interp
);
1005 /* No interpretations had anything useful to propagate, so
1006 produce X = Y + (c * 1). */
1010 stride
= integer_one_node
;
1011 ctype
= TREE_TYPE (base_in
);
1014 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1019 /* Given GS which is an add or subtract of scalar integers or pointers,
1020 make at least one appropriate entry in the candidate table. */
1023 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1025 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1026 slsr_cand_t c
= NULL
, c2
;
1028 if (TREE_CODE (rhs2
) == SSA_NAME
)
1030 /* First record an interpretation assuming RHS1 is the base expression
1031 and RHS2 is the stride. But it doesn't make sense for the
1032 stride to be a pointer, so don't record a candidate in that case. */
1033 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1035 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1037 /* Add the first interpretation to the statement-candidate
1039 add_cand_for_stmt (gs
, c
);
1042 /* If the two RHS operands are identical, or this is a subtract,
1044 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1047 /* Otherwise, record another interpretation assuming RHS2 is the
1048 base expression and RHS1 is the stride, again provided that the
1049 stride is not a pointer. */
1050 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1052 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1054 c
->next_interp
= c2
->cand_num
;
1056 add_cand_for_stmt (gs
, c2
);
1063 /* Record an interpretation for the add-immediate. */
1064 index
= tree_to_double_int (rhs2
);
1068 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1070 /* Add the interpretation to the statement-candidate mapping. */
1071 add_cand_for_stmt (gs
, c
);
1075 /* Given GS which is a negate of a scalar integer, make an appropriate
1076 entry in the candidate table. A negate is equivalent to a multiply
1080 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1082 /* Record a CAND_MULT interpretation for the multiply by -1. */
1083 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1085 /* Add the interpretation to the statement-candidate mapping. */
1086 add_cand_for_stmt (gs
, c
);
1089 /* Help function for legal_cast_p, operating on two trees. Checks
1090 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1091 for more details. */
1094 legal_cast_p_1 (tree lhs
, tree rhs
)
1096 tree lhs_type
, rhs_type
;
1097 unsigned lhs_size
, rhs_size
;
1098 bool lhs_wraps
, rhs_wraps
;
1100 lhs_type
= TREE_TYPE (lhs
);
1101 rhs_type
= TREE_TYPE (rhs
);
1102 lhs_size
= TYPE_PRECISION (lhs_type
);
1103 rhs_size
= TYPE_PRECISION (rhs_type
);
1104 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1105 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1107 if (lhs_size
< rhs_size
1108 || (rhs_wraps
&& !lhs_wraps
)
1109 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1115 /* Return TRUE if GS is a statement that defines an SSA name from
1116 a conversion and is legal for us to combine with an add and multiply
1117 in the candidate table. For example, suppose we have:
1123 Without the type-cast, we would create a CAND_MULT for D with base B,
1124 index i, and stride S. We want to record this candidate only if it
1125 is equivalent to apply the type cast following the multiply:
1131 We will record the type with the candidate for D. This allows us
1132 to use a similar previous candidate as a basis. If we have earlier seen
1138 we can replace D with
1140 D = D' + (i - i') * S;
1142 But if moving the type-cast would change semantics, we mustn't do this.
1144 This is legitimate for casts from a non-wrapping integral type to
1145 any integral type of the same or larger size. It is not legitimate
1146 to convert a wrapping type to a non-wrapping type, or to a wrapping
1147 type of a different size. I.e., with a wrapping type, we must
1148 assume that the addition B + i could wrap, in which case performing
1149 the multiply before or after one of the "illegal" type casts will
1150 have different semantics. */
1153 legal_cast_p (gimple gs
, tree rhs
)
1155 if (!is_gimple_assign (gs
)
1156 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1159 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1162 /* Given GS which is a cast to a scalar integer type, determine whether
1163 the cast is legal for strength reduction. If so, make at least one
1164 appropriate entry in the candidate table. */
1167 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1170 slsr_cand_t base_cand
, c
, c2
;
1171 unsigned savings
= 0;
1173 if (!legal_cast_p (gs
, rhs1
))
1176 lhs
= gimple_assign_lhs (gs
);
1177 base_cand
= base_cand_from_table (rhs1
);
1178 ctype
= TREE_TYPE (lhs
);
1184 /* Propagate all data from the base candidate except the type,
1185 which comes from the cast, and the base candidate's cast,
1186 which is no longer applicable. */
1187 if (has_single_use (rhs1
))
1188 savings
= (base_cand
->dead_savings
1189 + stmt_cost (base_cand
->cand_stmt
, speed
));
1191 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1192 base_cand
->base_expr
,
1193 base_cand
->index
, base_cand
->stride
,
1195 if (base_cand
->next_interp
)
1196 base_cand
= lookup_cand (base_cand
->next_interp
);
1203 /* If nothing is known about the RHS, create fresh CAND_ADD and
1204 CAND_MULT interpretations:
1209 The first of these is somewhat arbitrary, but the choice of
1210 1 for the stride simplifies the logic for propagating casts
1212 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1213 integer_one_node
, ctype
, 0);
1214 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1215 integer_one_node
, ctype
, 0);
1216 c
->next_interp
= c2
->cand_num
;
1219 /* Add the first (or only) interpretation to the statement-candidate
1221 add_cand_for_stmt (gs
, c
);
1224 /* Given GS which is a copy of a scalar integer type, make at least one
1225 appropriate entry in the candidate table.
1227 This interface is included for completeness, but is unnecessary
1228 if this pass immediately follows a pass that performs copy
1229 propagation, such as DOM. */
1232 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1234 slsr_cand_t base_cand
, c
, c2
;
1235 unsigned savings
= 0;
1237 base_cand
= base_cand_from_table (rhs1
);
1243 /* Propagate all data from the base candidate. */
1244 if (has_single_use (rhs1
))
1245 savings
= (base_cand
->dead_savings
1246 + stmt_cost (base_cand
->cand_stmt
, speed
));
1248 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1249 base_cand
->base_expr
,
1250 base_cand
->index
, base_cand
->stride
,
1251 base_cand
->cand_type
, savings
);
1252 if (base_cand
->next_interp
)
1253 base_cand
= lookup_cand (base_cand
->next_interp
);
1260 /* If nothing is known about the RHS, create fresh CAND_ADD and
1261 CAND_MULT interpretations:
1266 The first of these is somewhat arbitrary, but the choice of
1267 1 for the stride simplifies the logic for propagating casts
1269 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1270 integer_one_node
, TREE_TYPE (rhs1
), 0);
1271 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1272 integer_one_node
, TREE_TYPE (rhs1
), 0);
1273 c
->next_interp
= c2
->cand_num
;
1276 /* Add the first (or only) interpretation to the statement-candidate
1278 add_cand_for_stmt (gs
, c
);
1281 /* Find strength-reduction candidates in block BB. */
1284 find_candidates_in_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1287 bool speed
= optimize_bb_for_speed_p (bb
);
1288 gimple_stmt_iterator gsi
;
1290 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1292 gimple gs
= gsi_stmt (gsi
);
1294 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1295 slsr_process_ref (gs
);
1297 else if (is_gimple_assign (gs
)
1298 && SCALAR_INT_MODE_P
1299 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1301 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1303 switch (gimple_assign_rhs_code (gs
))
1307 rhs1
= gimple_assign_rhs1 (gs
);
1308 rhs2
= gimple_assign_rhs2 (gs
);
1309 /* Should never happen, but currently some buggy situations
1310 in earlier phases put constants in rhs1. */
1311 if (TREE_CODE (rhs1
) != SSA_NAME
)
1315 /* Possible future opportunity: rhs1 of a ptr+ can be
1317 case POINTER_PLUS_EXPR
:
1319 rhs2
= gimple_assign_rhs2 (gs
);
1325 rhs1
= gimple_assign_rhs1 (gs
);
1326 if (TREE_CODE (rhs1
) != SSA_NAME
)
1334 switch (gimple_assign_rhs_code (gs
))
1337 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1341 case POINTER_PLUS_EXPR
:
1343 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1347 slsr_process_neg (gs
, rhs1
, speed
);
1351 slsr_process_cast (gs
, rhs1
, speed
);
1355 slsr_process_copy (gs
, rhs1
, speed
);
1365 /* Dump a candidate for debug. */
1368 dump_candidate (slsr_cand_t c
)
1370 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1371 gimple_bb (c
->cand_stmt
)->index
);
1372 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1376 fputs (" MULT : (", dump_file
);
1377 print_generic_expr (dump_file
, c
->base_expr
, 0);
1378 fputs (" + ", dump_file
);
1379 dump_double_int (dump_file
, c
->index
, false);
1380 fputs (") * ", dump_file
);
1381 print_generic_expr (dump_file
, c
->stride
, 0);
1382 fputs (" : ", dump_file
);
1385 fputs (" ADD : ", dump_file
);
1386 print_generic_expr (dump_file
, c
->base_expr
, 0);
1387 fputs (" + (", dump_file
);
1388 dump_double_int (dump_file
, c
->index
, false);
1389 fputs (" * ", dump_file
);
1390 print_generic_expr (dump_file
, c
->stride
, 0);
1391 fputs (") : ", dump_file
);
1394 fputs (" REF : ", dump_file
);
1395 print_generic_expr (dump_file
, c
->base_expr
, 0);
1396 fputs (" + (", dump_file
);
1397 print_generic_expr (dump_file
, c
->stride
, 0);
1398 fputs (") + ", dump_file
);
1399 dump_double_int (dump_file
, c
->index
, false);
1400 fputs (" : ", dump_file
);
1405 print_generic_expr (dump_file
, c
->cand_type
, 0);
1406 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1407 c
->basis
, c
->dependent
, c
->sibling
);
1408 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1409 c
->next_interp
, c
->dead_savings
);
1412 fputs (" phi: ", dump_file
);
1413 print_gimple_stmt (dump_file
, c
->def_phi
, 0, 0);
1415 fputs ("\n", dump_file
);
1418 /* Dump the candidate vector for debug. */
1421 dump_cand_vec (void)
1426 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1428 FOR_EACH_VEC_ELT (slsr_cand_t
, cand_vec
, i
, c
)
1432 /* Callback used to dump the candidate chains hash table. */
1435 base_cand_dump_callback (void **slot
, void *ignored ATTRIBUTE_UNUSED
)
1437 const_cand_chain_t chain
= *((const_cand_chain_t
*) slot
);
1440 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1441 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1443 for (p
= chain
->next
; p
; p
= p
->next
)
1444 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1446 fputs ("\n", dump_file
);
1450 /* Dump the candidate chains. */
1453 dump_cand_chains (void)
1455 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1456 htab_traverse_noresize (base_cand_map
, base_cand_dump_callback
, NULL
);
1457 fputs ("\n", dump_file
);
1460 /* Dump the increment vector for debug. */
1463 dump_incr_vec (void)
1465 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1469 fprintf (dump_file
, "\nIncrement vector:\n\n");
1471 for (i
= 0; i
< incr_vec_len
; i
++)
1473 fprintf (dump_file
, "%3d increment: ", i
);
1474 dump_double_int (dump_file
, incr_vec
[i
].incr
, false);
1475 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1476 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1477 fputs ("\n initializer: ", dump_file
);
1478 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1479 fputs ("\n\n", dump_file
);
1484 /* Recursive helper for unconditional_cands_with_known_stride_p.
1485 Returns TRUE iff C, its siblings, and its dependents are all
1486 unconditional candidates. */
1489 unconditional_cands (slsr_cand_t c
)
1494 if (c
->sibling
&& !unconditional_cands (lookup_cand (c
->sibling
)))
1497 if (c
->dependent
&& !unconditional_cands (lookup_cand (c
->dependent
)))
1503 /* Determine whether or not the tree of candidates rooted at
1504 ROOT consists entirely of unconditional increments with
1505 an INTEGER_CST stride. */
1508 unconditional_cands_with_known_stride_p (slsr_cand_t root
)
1510 /* The stride is identical for all related candidates, so
1512 if (TREE_CODE (root
->stride
) != INTEGER_CST
)
1515 return unconditional_cands (lookup_cand (root
->dependent
));
1518 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1522 replace_ref (tree
*expr
, slsr_cand_t c
)
1524 tree add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1525 c
->base_expr
, c
->stride
);
1526 tree mem_ref
= fold_build2 (MEM_REF
, TREE_TYPE (*expr
), add_expr
,
1527 double_int_to_tree (c
->cand_type
, c
->index
));
1529 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1530 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1531 TREE_OPERAND (mem_ref
, 0)
1532 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1533 /*simple_p=*/true, NULL
,
1534 /*before=*/true, GSI_SAME_STMT
);
1535 copy_ref_info (mem_ref
, *expr
);
1537 update_stmt (c
->cand_stmt
);
1540 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1541 dependent of candidate C with an equivalent strength-reduced data
1545 replace_refs (slsr_cand_t c
)
1547 if (gimple_vdef (c
->cand_stmt
))
1549 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1550 replace_ref (lhs
, c
);
1554 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1555 replace_ref (rhs
, c
);
1559 replace_refs (lookup_cand (c
->sibling
));
1562 replace_refs (lookup_cand (c
->dependent
));
1565 /* Calculate the increment required for candidate C relative to
1569 cand_increment (slsr_cand_t c
)
1573 /* If the candidate doesn't have a basis, just return its own
1574 index. This is useful in record_increments to help us find
1575 an existing initializer. */
1579 basis
= lookup_cand (c
->basis
);
1580 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1581 return c
->index
- basis
->index
;
1584 /* Calculate the increment required for candidate C relative to
1585 its basis. If we aren't going to generate pointer arithmetic
1586 for this candidate, return the absolute value of that increment
1589 static inline double_int
1590 cand_abs_increment (slsr_cand_t c
)
1592 double_int increment
= cand_increment (c
);
1594 if (!address_arithmetic_p
&& increment
.is_negative ())
1595 increment
= -increment
;
1600 /* If *VAR is NULL or is not of a compatible type with TYPE, create a
1601 new temporary reg of type TYPE and store it in *VAR. */
1604 lazy_create_slsr_reg (tree
*var
, tree type
)
1606 if (!*var
|| !types_compatible_p (TREE_TYPE (*var
), type
))
1607 *var
= create_tmp_reg (type
, "slsr");
1610 /* Return TRUE iff candidate C has already been replaced under
1611 another interpretation. */
1614 cand_already_replaced (slsr_cand_t c
)
1616 return (gimple_bb (c
->cand_stmt
) == 0);
1619 /* Helper routine for replace_dependents, doing the work for a
1620 single candidate C. */
1623 replace_dependent (slsr_cand_t c
, enum tree_code cand_code
)
1625 double_int stride
= tree_to_double_int (c
->stride
);
1626 double_int bump
= cand_increment (c
) * stride
;
1627 gimple stmt_to_print
= NULL
;
1629 tree basis_name
, incr_type
, bump_tree
;
1630 enum tree_code code
;
1632 /* It is highly unlikely, but possible, that the resulting
1633 bump doesn't fit in a HWI. Abandon the replacement
1634 in this case. Restriction to signed HWI is conservative
1635 for unsigned types but allows for safe negation without
1637 if (!bump
.fits_shwi ())
1640 basis
= lookup_cand (c
->basis
);
1641 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
1642 incr_type
= TREE_TYPE (gimple_assign_rhs1 (c
->cand_stmt
));
1645 if (bump
.is_negative ())
1651 bump_tree
= double_int_to_tree (incr_type
, bump
);
1653 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1655 fputs ("Replacing: ", dump_file
);
1656 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1659 if (bump
.is_zero ())
1661 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1662 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1663 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1664 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1665 gsi_replace (&gsi
, copy_stmt
, false);
1666 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1667 stmt_to_print
= copy_stmt
;
1671 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1672 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1673 if (cand_code
!= NEGATE_EXPR
1674 && ((operand_equal_p (rhs1
, basis_name
, 0)
1675 && operand_equal_p (rhs2
, bump_tree
, 0))
1676 || (operand_equal_p (rhs1
, bump_tree
, 0)
1677 && operand_equal_p (rhs2
, basis_name
, 0))))
1679 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1681 fputs ("(duplicate, not actually replacing)", dump_file
);
1682 stmt_to_print
= c
->cand_stmt
;
1687 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1688 gimple_assign_set_rhs_with_ops (&gsi
, code
, basis_name
, bump_tree
);
1689 update_stmt (gsi_stmt (gsi
));
1690 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1691 stmt_to_print
= gsi_stmt (gsi
);
1695 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1697 fputs ("With: ", dump_file
);
1698 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
1699 fputs ("\n", dump_file
);
1703 /* Replace candidate C, each sibling of candidate C, and each
1704 dependent of candidate C with an add or subtract. Note that we
1705 only operate on CAND_MULTs with known strides, so we will never
1706 generate a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is
1707 replaced by X = Y + ((i - i') * S), as described in the module
1708 commentary. The folded value ((i - i') * S) is referred to here
1712 replace_dependents (slsr_cand_t c
)
1714 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1716 /* It is not useful to replace casts, copies, or adds of an SSA name
1717 and a constant. Also skip candidates that have already been
1718 replaced under another interpretation. */
1719 if (cand_code
!= MODIFY_EXPR
1720 && cand_code
!= NOP_EXPR
1721 && c
->kind
== CAND_MULT
1722 && !cand_already_replaced (c
))
1723 replace_dependent (c
, cand_code
);
1726 replace_dependents (lookup_cand (c
->sibling
));
1729 replace_dependents (lookup_cand (c
->dependent
));
1732 /* Return the index in the increment vector of the given INCREMENT. */
1734 static inline unsigned
1735 incr_vec_index (double_int increment
)
1739 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
1742 gcc_assert (i
< incr_vec_len
);
1746 /* Count the number of candidates in the tree rooted at C that have
1747 not already been replaced under other interpretations. */
1750 count_candidates (slsr_cand_t c
)
1752 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
1755 count
+= count_candidates (lookup_cand (c
->sibling
));
1758 count
+= count_candidates (lookup_cand (c
->dependent
));
1763 /* Increase the count of INCREMENT by one in the increment vector.
1764 INCREMENT is associated with candidate C. If an initializer
1765 T_0 = stride * I is provided by a candidate that dominates all
1766 candidates with the same increment, also record T_0 for subsequent use. */
1769 record_increment (slsr_cand_t c
, double_int increment
)
1774 /* Treat increments that differ only in sign as identical so as to
1775 share initializers, unless we are generating pointer arithmetic. */
1776 if (!address_arithmetic_p
&& increment
.is_negative ())
1777 increment
= -increment
;
1779 for (i
= 0; i
< incr_vec_len
; i
++)
1781 if (incr_vec
[i
].incr
== increment
)
1783 incr_vec
[i
].count
++;
1786 /* If we previously recorded an initializer that doesn't
1787 dominate this candidate, it's not going to be useful to
1789 if (incr_vec
[i
].initializer
1790 && !dominated_by_p (CDI_DOMINATORS
,
1791 gimple_bb (c
->cand_stmt
),
1792 incr_vec
[i
].init_bb
))
1794 incr_vec
[i
].initializer
= NULL_TREE
;
1795 incr_vec
[i
].init_bb
= NULL
;
1804 /* The first time we see an increment, create the entry for it.
1805 If this is the root candidate which doesn't have a basis, set
1806 the count to zero. We're only processing it so it can possibly
1807 provide an initializer for other candidates. */
1808 incr_vec
[incr_vec_len
].incr
= increment
;
1809 incr_vec
[incr_vec_len
].count
= c
->basis
? 1 : 0;
1810 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
1812 /* Optimistically record the first occurrence of this increment
1813 as providing an initializer (if it does); we will revise this
1814 opinion later if it doesn't dominate all other occurrences.
1815 Exception: increments of -1, 0, 1 never need initializers. */
1816 if (c
->kind
== CAND_ADD
1817 && c
->index
== increment
1818 && (increment
.sgt (double_int_one
)
1819 || increment
.slt (double_int_minus_one
)))
1822 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1823 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1824 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
1828 if (SSA_NAME_DEF_STMT (t0
) && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
1830 incr_vec
[incr_vec_len
].initializer
= t0
;
1831 incr_vec
[incr_vec_len
++].init_bb
1832 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
1836 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
1837 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
1842 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
1843 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
1848 /* Determine how many times each unique increment occurs in the set
1849 of candidates rooted at C's parent, recording the data in the
1850 increment vector. For each unique increment I, if an initializer
1851 T_0 = stride * I is provided by a candidate that dominates all
1852 candidates with the same increment, also record T_0 for subsequent
1856 record_increments (slsr_cand_t c
)
1858 if (!cand_already_replaced (c
))
1859 record_increment (c
, cand_increment (c
));
1862 record_increments (lookup_cand (c
->sibling
));
1865 record_increments (lookup_cand (c
->dependent
));
1868 /* Return the first candidate in the tree rooted at C that has not
1869 already been replaced, favoring siblings over dependents. */
1872 unreplaced_cand_in_tree (slsr_cand_t c
)
1874 if (!cand_already_replaced (c
))
1879 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
1886 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
1894 /* Return TRUE if the candidates in the tree rooted at C should be
1895 optimized for speed, else FALSE. We estimate this based on the block
1896 containing the most dominant candidate in the tree that has not yet
1900 optimize_cands_for_speed_p (slsr_cand_t c
)
1902 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
1904 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
1907 /* Add COST_IN to the lowest cost of any dependent path starting at
1908 candidate C or any of its siblings, counting only candidates along
1909 such paths with increment INCR. Assume that replacing a candidate
1910 reduces cost by REPL_SAVINGS. Also account for savings from any
1911 statements that would go dead. */
1914 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
, double_int incr
)
1916 int local_cost
, sib_cost
;
1917 double_int cand_incr
= cand_abs_increment (c
);
1919 if (cand_already_replaced (c
))
1920 local_cost
= cost_in
;
1921 else if (incr
== cand_incr
)
1922 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
1924 local_cost
= cost_in
- c
->dead_savings
;
1927 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
1928 lookup_cand (c
->dependent
), incr
);
1932 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
1933 lookup_cand (c
->sibling
), incr
);
1934 local_cost
= MIN (local_cost
, sib_cost
);
1940 /* Compute the total savings that would accrue from all replacements
1941 in the candidate tree rooted at C, counting only candidates with
1942 increment INCR. Assume that replacing a candidate reduces cost
1943 by REPL_SAVINGS. Also account for savings from statements that
1947 total_savings (int repl_savings
, slsr_cand_t c
, double_int incr
)
1950 double_int cand_incr
= cand_abs_increment (c
);
1952 if (incr
== cand_incr
&& !cand_already_replaced (c
))
1953 savings
+= repl_savings
+ c
->dead_savings
;
1956 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
);
1959 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
);
1964 /* Use target-specific costs to determine and record which increments
1965 in the current candidate tree are profitable to replace, assuming
1966 MODE and SPEED. FIRST_DEP is the first dependent of the root of
1969 One slight limitation here is that we don't account for the possible
1970 introduction of casts in some cases. See replace_one_candidate for
1971 the cases where these are introduced. This should probably be cleaned
1975 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
1979 for (i
= 0; i
< incr_vec_len
; i
++)
1981 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
1983 /* If somehow this increment is bigger than a HWI, we won't
1984 be optimizing candidates that use it. And if the increment
1985 has a count of zero, nothing will be done with it. */
1986 if (!incr_vec
[i
].incr
.fits_shwi () || !incr_vec
[i
].count
)
1987 incr_vec
[i
].cost
= COST_INFINITE
;
1989 /* Increments of 0, 1, and -1 are always profitable to replace,
1990 because they always replace a multiply or add with an add or
1991 copy, and may cause one or more existing instructions to go
1992 dead. Exception: -1 can't be assumed to be profitable for
1993 pointer addition. */
1997 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
1998 != POINTER_PLUS_EXPR
)))
1999 incr_vec
[i
].cost
= COST_NEUTRAL
;
2001 /* FORNOW: If we need to add an initializer, give up if a cast from
2002 the candidate's type to its stride's type can lose precision.
2003 This could eventually be handled better by expressly retaining the
2004 result of a cast to a wider type in the stride. Example:
2009 _4 = x + _3; ADD: x + (10 * _1) : int
2011 _6 = x + _3; ADD: x + (15 * _1) : int
2013 Right now replacing _6 would cause insertion of an initializer
2014 of the form "short int T = _1 * 5;" followed by a cast to
2015 int, which could overflow incorrectly. Had we recorded _2 or
2016 (int)_1 as the stride, this wouldn't happen. However, doing
2017 this breaks other opportunities, so this will require some
2019 else if (!incr_vec
[i
].initializer
2020 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2021 && !legal_cast_p_1 (first_dep
->stride
,
2022 gimple_assign_lhs (first_dep
->cand_stmt
)))
2024 incr_vec
[i
].cost
= COST_INFINITE
;
2026 /* For any other increment, if this is a multiply candidate, we
2027 must introduce a temporary T and initialize it with
2028 T_0 = stride * increment. When optimizing for speed, walk the
2029 candidate tree to calculate the best cost reduction along any
2030 path; if it offsets the fixed cost of inserting the initializer,
2031 replacing the increment is profitable. When optimizing for
2032 size, instead calculate the total cost reduction from replacing
2033 all candidates with this increment. */
2034 else if (first_dep
->kind
== CAND_MULT
)
2036 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2037 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2039 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2042 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
);
2044 incr_vec
[i
].cost
= cost
;
2047 /* If this is an add candidate, the initializer may already
2048 exist, so only calculate the cost of the initializer if it
2049 doesn't. We are replacing one add with another here, so the
2050 known replacement savings is zero. We will account for removal
2051 of dead instructions in lowest_cost_path or total_savings. */
2055 if (!incr_vec
[i
].initializer
)
2056 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2059 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
);
2061 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
);
2063 incr_vec
[i
].cost
= cost
;
2068 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2069 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2070 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2071 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2072 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2075 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2076 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2092 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2094 /* If both candidates are in the same block, the earlier
2096 if (bb1
== ncd
&& bb2
== ncd
)
2098 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2104 /* Otherwise, if one of them produced a candidate in the
2105 dominator, that one wins. */
2106 else if (bb1
== ncd
)
2109 else if (bb2
== ncd
)
2112 /* If neither matches the dominator, neither wins. */
2119 /* Consider all candidates in the tree rooted at C for which INCR
2120 represents the required increment of C relative to its basis.
2121 Find and return the basic block that most nearly dominates all
2122 such candidates. If the returned block contains one or more of
2123 the candidates, return the earliest candidate in the block in
2127 nearest_common_dominator_for_cands (slsr_cand_t c
, double_int incr
,
2130 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
2131 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
2132 double_int cand_incr
;
2134 /* First find the NCD of all siblings and dependents. */
2136 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
2139 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
2141 if (!sib_ncd
&& !dep_ncd
)
2146 else if (sib_ncd
&& !dep_ncd
)
2148 new_where
= sib_where
;
2151 else if (dep_ncd
&& !sib_ncd
)
2153 new_where
= dep_where
;
2157 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
2158 dep_where
, &new_where
);
2160 /* If the candidate's increment doesn't match the one we're interested
2161 in, then the result depends only on siblings and dependents. */
2162 cand_incr
= cand_abs_increment (c
);
2164 if (cand_incr
!= incr
|| cand_already_replaced (c
))
2170 /* Otherwise, compare this candidate with the result from all siblings
2173 this_ncd
= gimple_bb (c
->cand_stmt
);
2174 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
2179 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
2182 profitable_increment_p (unsigned index
)
2184 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
2187 /* For each profitable increment in the increment vector not equal to
2188 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
2189 dominator of all statements in the candidate chain rooted at C
2190 that require that increment, and insert an initializer
2191 T_0 = stride * increment at that location. Record T_0 with the
2192 increment record. */
2195 insert_initializers (slsr_cand_t c
)
2198 tree new_var
= NULL_TREE
;
2200 for (i
= 0; i
< incr_vec_len
; i
++)
2203 slsr_cand_t where
= NULL
;
2205 tree stride_type
, new_name
, incr_tree
;
2206 double_int incr
= incr_vec
[i
].incr
;
2208 if (!profitable_increment_p (i
)
2210 || (incr
.is_minus_one ()
2211 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
2215 /* We may have already identified an existing initializer that
2217 if (incr_vec
[i
].initializer
)
2219 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2221 fputs ("Using existing initializer: ", dump_file
);
2222 print_gimple_stmt (dump_file
,
2223 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
2229 /* Find the block that most closely dominates all candidates
2230 with this increment. If there is at least one candidate in
2231 that block, the earliest one will be returned in WHERE. */
2232 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
2234 /* Create a new SSA name to hold the initializer's value. */
2235 stride_type
= TREE_TYPE (c
->stride
);
2236 lazy_create_slsr_reg (&new_var
, stride_type
);
2237 new_name
= make_ssa_name (new_var
, NULL
);
2238 incr_vec
[i
].initializer
= new_name
;
2240 /* Create the initializer and insert it in the latest possible
2241 dominating position. */
2242 incr_tree
= double_int_to_tree (stride_type
, incr
);
2243 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
2244 c
->stride
, incr_tree
);
2247 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
2248 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2249 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
2253 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2254 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
2256 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2257 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2259 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
2261 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
2264 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2266 fputs ("Inserting initializer: ", dump_file
);
2267 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
2272 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
2273 type TO_TYPE, and insert it in front of the statement represented
2274 by candidate C. Use *NEW_VAR to create the new SSA name. Return
2275 the new SSA name. */
2278 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
,
2279 tree from_expr
, tree
*new_var
)
2283 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2285 lazy_create_slsr_reg (new_var
, to_type
);
2286 cast_lhs
= make_ssa_name (*new_var
, NULL
);
2287 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
2288 from_expr
, NULL_TREE
);
2289 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
2290 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
2292 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2294 fputs (" Inserting: ", dump_file
);
2295 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
2301 /* Replace the RHS of the statement represented by candidate C with
2302 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
2303 leave C unchanged or just interchange its operands. The original
2304 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
2305 If the replacement was made and we are doing a details dump,
2306 return the revised statement, else NULL. */
2309 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
2310 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
2313 if (new_code
!= old_code
2314 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
2315 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
2316 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
2317 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
2319 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2320 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
2321 update_stmt (gsi_stmt (gsi
));
2323 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2324 return gsi_stmt (gsi
);
2327 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2328 fputs (" (duplicate, not actually replacing)\n", dump_file
);
2333 /* Strength-reduce the statement represented by candidate C by replacing
2334 it with an equivalent addition or subtraction. I is the index into
2335 the increment vector identifying C's increment. NEW_VAR is used to
2336 create a new SSA name if a cast needs to be introduced. BASIS_NAME
2337 is the rhs1 to use in creating the add/subtract. */
2340 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree
*new_var
,
2343 gimple stmt_to_print
= NULL
;
2344 tree orig_rhs1
, orig_rhs2
;
2346 enum tree_code orig_code
, repl_code
;
2347 double_int cand_incr
;
2349 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
2350 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2351 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2352 cand_incr
= cand_increment (c
);
2354 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2356 fputs ("Replacing: ", dump_file
);
2357 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
2358 stmt_to_print
= c
->cand_stmt
;
2361 if (address_arithmetic_p
)
2362 repl_code
= POINTER_PLUS_EXPR
;
2364 repl_code
= PLUS_EXPR
;
2366 /* If the increment has an initializer T_0, replace the candidate
2367 statement with an add of the basis name and the initializer. */
2368 if (incr_vec
[i
].initializer
)
2370 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
2371 tree orig_type
= TREE_TYPE (orig_rhs2
);
2373 if (types_compatible_p (orig_type
, init_type
))
2374 rhs2
= incr_vec
[i
].initializer
;
2376 rhs2
= introduce_cast_before_cand (c
, orig_type
,
2377 incr_vec
[i
].initializer
,
2380 if (incr_vec
[i
].incr
!= cand_incr
)
2382 gcc_assert (repl_code
== PLUS_EXPR
);
2383 repl_code
= MINUS_EXPR
;
2386 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
2387 orig_code
, orig_rhs1
, orig_rhs2
,
2391 /* Otherwise, the increment is one of -1, 0, and 1. Replace
2392 with a subtract of the stride from the basis name, a copy
2393 from the basis name, or an add of the stride to the basis
2394 name, respectively. It may be necessary to introduce a
2395 cast (or reuse an existing cast). */
2396 else if (cand_incr
.is_one ())
2398 tree stride_type
= TREE_TYPE (c
->stride
);
2399 tree orig_type
= TREE_TYPE (orig_rhs2
);
2401 if (types_compatible_p (orig_type
, stride_type
))
2404 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
, new_var
);
2406 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
2407 orig_code
, orig_rhs1
, orig_rhs2
,
2411 else if (cand_incr
.is_minus_one ())
2413 tree stride_type
= TREE_TYPE (c
->stride
);
2414 tree orig_type
= TREE_TYPE (orig_rhs2
);
2415 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
2417 if (types_compatible_p (orig_type
, stride_type
))
2420 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
, new_var
);
2422 if (orig_code
!= MINUS_EXPR
2423 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
2424 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
2426 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2427 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
2428 update_stmt (gsi_stmt (gsi
));
2430 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2431 stmt_to_print
= gsi_stmt (gsi
);
2433 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2434 fputs (" (duplicate, not actually replacing)\n", dump_file
);
2437 else if (cand_incr
.is_zero ())
2439 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
2440 tree lhs_type
= TREE_TYPE (lhs
);
2441 tree basis_type
= TREE_TYPE (basis_name
);
2443 if (types_compatible_p (lhs_type
, basis_type
))
2445 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
2446 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2447 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
2448 gsi_replace (&gsi
, copy_stmt
, false);
2450 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2451 stmt_to_print
= copy_stmt
;
2455 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2456 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
2459 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
2460 gsi_replace (&gsi
, cast_stmt
, false);
2462 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2463 stmt_to_print
= cast_stmt
;
2469 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
2471 fputs ("With: ", dump_file
);
2472 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
2473 fputs ("\n", dump_file
);
2477 /* For each candidate in the tree rooted at C, replace it with
2478 an increment if such has been shown to be profitable. */
2481 replace_profitable_candidates (slsr_cand_t c
)
2483 if (!cand_already_replaced (c
))
2485 double_int increment
= cand_abs_increment (c
);
2486 tree new_var
= NULL
;
2487 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
2490 i
= incr_vec_index (increment
);
2492 /* Only process profitable increments. Nothing useful can be done
2493 to a cast or copy. */
2494 if (profitable_increment_p (i
)
2495 && orig_code
!= MODIFY_EXPR
2496 && orig_code
!= NOP_EXPR
)
2498 slsr_cand_t basis
= lookup_cand (c
->basis
);
2499 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2500 replace_one_candidate (c
, i
, &new_var
, basis_name
);
2505 replace_profitable_candidates (lookup_cand (c
->sibling
));
2508 replace_profitable_candidates (lookup_cand (c
->dependent
));
2511 /* Analyze costs of related candidates in the candidate vector,
2512 and make beneficial replacements. */
2515 analyze_candidates_and_replace (void)
2520 /* Each candidate that has a null basis and a non-null
2521 dependent is the root of a tree of related statements.
2522 Analyze each tree to determine a subset of those
2523 statements that can be replaced with maximum benefit. */
2524 FOR_EACH_VEC_ELT (slsr_cand_t
, cand_vec
, i
, c
)
2526 slsr_cand_t first_dep
;
2528 if (c
->basis
!= 0 || c
->dependent
== 0)
2531 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2532 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
2535 first_dep
= lookup_cand (c
->dependent
);
2537 /* If this is a chain of CAND_REFs, unconditionally replace
2538 each of them with a strength-reduced data reference. */
2539 if (c
->kind
== CAND_REF
)
2542 /* If the common stride of all related candidates is a
2543 known constant, and none of these has a phi-dependence,
2544 then all replacements are considered profitable.
2545 Each replaces a multiply by a single add, with the
2546 possibility that a feeding add also goes dead as a
2548 else if (unconditional_cands_with_known_stride_p (c
))
2549 replace_dependents (first_dep
);
2551 /* When the stride is an SSA name, it may still be profitable
2552 to replace some or all of the dependent candidates, depending
2553 on whether the introduced increments can be reused, or are
2554 less expensive to calculate than the replaced statements. */
2558 enum machine_mode mode
;
2561 /* Determine whether we'll be generating pointer arithmetic
2562 when replacing candidates. */
2563 address_arithmetic_p
= (c
->kind
== CAND_ADD
2564 && POINTER_TYPE_P (c
->cand_type
));
2566 /* If all candidates have already been replaced under other
2567 interpretations, nothing remains to be done. */
2568 length
= count_candidates (c
);
2572 /* Construct an array of increments for this candidate chain. */
2573 incr_vec
= XNEWVEC (incr_info
, length
);
2575 record_increments (c
);
2577 /* Determine which increments are profitable to replace. */
2578 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
2579 speed
= optimize_cands_for_speed_p (c
);
2580 analyze_increments (first_dep
, mode
, speed
);
2582 /* Insert initializers of the form T_0 = stride * increment
2583 for use in profitable replacements. */
2584 insert_initializers (first_dep
);
2587 /* Perform the replacements. */
2588 replace_profitable_candidates (first_dep
);
2592 /* TODO: When conditional increments occur so that a
2593 candidate is dependent upon a phi-basis, the cost of
2594 introducing a temporary must be accounted for. */
2599 execute_strength_reduction (void)
2601 struct dom_walk_data walk_data
;
2603 /* Create the obstack where candidates will reside. */
2604 gcc_obstack_init (&cand_obstack
);
2606 /* Allocate the candidate vector. */
2607 cand_vec
= VEC_alloc (slsr_cand_t
, heap
, 128);
2609 /* Allocate the mapping from statements to candidate indices. */
2610 stmt_cand_map
= pointer_map_create ();
2612 /* Create the obstack where candidate chains will reside. */
2613 gcc_obstack_init (&chain_obstack
);
2615 /* Allocate the mapping from base expressions to candidate chains. */
2616 base_cand_map
= htab_create (500, base_cand_hash
,
2617 base_cand_eq
, base_cand_free
);
2619 /* Initialize the loop optimizer. We need to detect flow across
2620 back edges, and this gives us dominator information as well. */
2621 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
2623 /* Set up callbacks for the generic dominator tree walker. */
2624 walk_data
.dom_direction
= CDI_DOMINATORS
;
2625 walk_data
.initialize_block_local_data
= NULL
;
2626 walk_data
.before_dom_children
= find_candidates_in_block
;
2627 walk_data
.after_dom_children
= NULL
;
2628 walk_data
.global_data
= NULL
;
2629 walk_data
.block_local_data_size
= 0;
2630 init_walk_dominator_tree (&walk_data
);
2632 /* Walk the CFG in predominator order looking for strength reduction
2634 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
2636 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2639 dump_cand_chains ();
2642 /* Analyze costs and make appropriate replacements. */
2643 analyze_candidates_and_replace ();
2645 /* Free resources. */
2646 fini_walk_dominator_tree (&walk_data
);
2647 loop_optimizer_finalize ();
2648 htab_delete (base_cand_map
);
2649 obstack_free (&chain_obstack
, NULL
);
2650 pointer_map_destroy (stmt_cand_map
);
2651 VEC_free (slsr_cand_t
, heap
, cand_vec
);
2652 obstack_free (&cand_obstack
, NULL
);
2658 gate_strength_reduction (void)
2660 return flag_tree_slsr
;
2663 struct gimple_opt_pass pass_strength_reduction
=
2668 gate_strength_reduction
, /* gate */
2669 execute_strength_reduction
, /* execute */
2672 0, /* static_pass_number */
2673 TV_GIMPLE_SLSR
, /* tv_id */
2674 PROP_cfg
| PROP_ssa
, /* properties_required */
2675 0, /* properties_provided */
2676 0, /* properties_destroyed */
2677 0, /* todo_flags_start */
2678 TODO_verify_ssa
/* todo_flags_finish */