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 "gimple-ssa.h"
47 #include "tree-phinodes.h"
48 #include "ssa-iterators.h"
49 #include "tree-ssanames.h"
51 #include "pointer-set.h"
54 #include "hash-table.h"
55 #include "tree-ssa-address.h"
57 /* Information about a strength reduction candidate. Each statement
58 in the candidate table represents an expression of one of the
59 following forms (the special case of CAND_REF will be described
62 (CAND_MULT) S1: X = (B + i) * S
63 (CAND_ADD) S1: X = B + (i * S)
65 Here X and B are SSA names, i is an integer constant, and S is
66 either an SSA name or a constant. We call B the "base," i the
67 "index", and S the "stride."
69 Any statement S0 that dominates S1 and is of the form:
71 (CAND_MULT) S0: Y = (B + i') * S
72 (CAND_ADD) S0: Y = B + (i' * S)
74 is called a "basis" for S1. In both cases, S1 may be replaced by
76 S1': X = Y + (i - i') * S,
78 where (i - i') * S is folded to the extent possible.
80 All gimple statements are visited in dominator order, and each
81 statement that may contribute to one of the forms of S1 above is
82 given at least one entry in the candidate table. Such statements
83 include addition, pointer addition, subtraction, multiplication,
84 negation, copies, and nontrivial type casts. If a statement may
85 represent more than one expression of the forms of S1 above,
86 multiple "interpretations" are stored in the table and chained
89 * An add of two SSA names may treat either operand as the base.
90 * A multiply of two SSA names, likewise.
91 * A copy or cast may be thought of as either a CAND_MULT with
92 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
94 Candidate records are allocated from an obstack. They are addressed
95 both from a hash table keyed on S1, and from a vector of candidate
96 pointers arranged in predominator order.
100 Currently we don't recognize:
105 as a strength reduction opportunity, even though this S1 would
106 also be replaceable by the S1' above. This can be added if it
107 comes up in practice.
109 Strength reduction in addressing
110 --------------------------------
111 There is another kind of candidate known as CAND_REF. A CAND_REF
112 describes a statement containing a memory reference having
113 complex addressing that might benefit from strength reduction.
114 Specifically, we are interested in references for which
115 get_inner_reference returns a base address, offset, and bitpos as
118 base: MEM_REF (T1, C1)
119 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
120 bitpos: C4 * BITS_PER_UNIT
122 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
123 arbitrary integer constants. Note that C2 may be zero, in which
124 case the offset will be MULT_EXPR (T2, C3).
126 When this pattern is recognized, the original memory reference
127 can be replaced with:
129 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
132 which distributes the multiply to allow constant folding. When
133 two or more addressing expressions can be represented by MEM_REFs
134 of this form, differing only in the constants C1, C2, and C4,
135 making this substitution produces more efficient addressing during
136 the RTL phases. When there are not at least two expressions with
137 the same values of T1, T2, and C3, there is nothing to be gained
140 Strength reduction of CAND_REFs uses the same infrastructure as
141 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
142 field, MULT_EXPR (T2, C3) in the stride (S) field, and
143 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
144 is thus another CAND_REF with the same B and S values. When at
145 least two CAND_REFs are chained together using the basis relation,
146 each of them is replaced as above, resulting in improved code
147 generation for addressing.
149 Conditional candidates
150 ======================
152 Conditional candidates are best illustrated with an example.
153 Consider the code sequence:
156 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
158 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
159 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
160 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
161 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
163 Here strength reduction is complicated by the uncertain value of x_2.
164 A legitimate transformation is:
173 (4) [x_2 = PHI <x_0, x_1>;]
174 (4a) t_2 = PHI <a_0, t_1>;
178 where the bracketed instructions may go dead.
180 To recognize this opportunity, we have to observe that statement (6)
181 has a "hidden basis" (2). The hidden basis is unlike a normal basis
182 in that the statement and the hidden basis have different base SSA
183 names (x_2 and x_0, respectively). The relationship is established
184 when a statement's base name (x_2) is defined by a phi statement (4),
185 each argument of which (x_0, x_1) has an identical "derived base name."
186 If the argument is defined by a candidate (as x_1 is by (3)) that is a
187 CAND_ADD having a stride of 1, the derived base name of the argument is
188 the base name of the candidate (x_0). Otherwise, the argument itself
189 is its derived base name (as is the case with argument x_0).
191 The hidden basis for statement (6) is the nearest dominating candidate
192 whose base name is the derived base name (x_0) of the feeding phi (4),
193 and whose stride is identical to that of the statement. We can then
194 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
195 allowing the final replacement of (6) by the strength-reduced (6r).
197 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
198 A CAND_PHI is not a candidate for replacement, but is maintained in the
199 candidate table to ease discovery of hidden bases. Any phi statement
200 whose arguments share a common derived base name is entered into the
201 table with the derived base name, an (arbitrary) index of zero, and a
202 stride of 1. A statement with a hidden basis can then be detected by
203 simply looking up its feeding phi definition in the candidate table,
204 extracting the derived base name, and searching for a basis in the
205 usual manner after substituting the derived base name.
207 Note that the transformation is only valid when the original phi and
208 the statements that define the phi's arguments are all at the same
209 position in the loop hierarchy. */
212 /* Index into the candidate vector, offset by 1. VECs are zero-based,
213 while cand_idx's are one-based, with zero indicating null. */
214 typedef unsigned cand_idx
;
216 /* The kind of candidate. */
227 /* The candidate statement S1. */
230 /* The base expression B: often an SSA name, but not always. */
236 /* The index constant i. */
239 /* The type of the candidate. This is normally the type of base_expr,
240 but casts may have occurred when combining feeding instructions.
241 A candidate can only be a basis for candidates of the same final type.
242 (For CAND_REFs, this is the type to be used for operand 1 of the
243 replacement MEM_REF.) */
246 /* The kind of candidate (CAND_MULT, etc.). */
249 /* Index of this candidate in the candidate vector. */
252 /* Index of the next candidate record for the same statement.
253 A statement may be useful in more than one way (e.g., due to
254 commutativity). So we can have multiple "interpretations"
256 cand_idx next_interp
;
258 /* Index of the basis statement S0, if any, in the candidate vector. */
261 /* First candidate for which this candidate is a basis, if one exists. */
264 /* Next candidate having the same basis as this one. */
267 /* If this is a conditional candidate, the CAND_PHI candidate
268 that defines the base SSA name B. */
271 /* Savings that can be expected from eliminating dead code if this
272 candidate is replaced. */
276 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
277 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
279 /* Pointers to candidates are chained together as part of a mapping
280 from base expressions to the candidates that use them. */
284 /* Base expression for the chain of candidates: often, but not
285 always, an SSA name. */
288 /* Pointer to a candidate. */
292 struct cand_chain_d
*next
;
296 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
297 typedef const struct cand_chain_d
*const_cand_chain_t
;
299 /* Information about a unique "increment" associated with candidates
300 having an SSA name for a stride. An increment is the difference
301 between the index of the candidate and the index of its basis,
302 i.e., (i - i') as discussed in the module commentary.
304 When we are not going to generate address arithmetic we treat
305 increments that differ only in sign as the same, allowing sharing
306 of the cost of initializers. The absolute value of the increment
307 is stored in the incr_info. */
311 /* The increment that relates a candidate to its basis. */
314 /* How many times the increment occurs in the candidate tree. */
317 /* Cost of replacing candidates using this increment. Negative and
318 zero costs indicate replacement should be performed. */
321 /* If this increment is profitable but is not -1, 0, or 1, it requires
322 an initializer T_0 = stride * incr to be found or introduced in the
323 nearest common dominator of all candidates. This field holds T_0
324 for subsequent use. */
327 /* If the initializer was found to already exist, this is the block
328 where it was found. */
332 typedef struct incr_info_d incr_info
, *incr_info_t
;
334 /* Candidates are maintained in a vector. If candidate X dominates
335 candidate Y, then X appears before Y in the vector; but the
336 converse does not necessarily hold. */
337 static vec
<slsr_cand_t
> cand_vec
;
351 enum phi_adjust_status
357 enum count_phis_status
363 /* Pointer map embodying a mapping from statements to candidates. */
364 static struct pointer_map_t
*stmt_cand_map
;
366 /* Obstack for candidates. */
367 static struct obstack cand_obstack
;
369 /* Obstack for candidate chains. */
370 static struct obstack chain_obstack
;
372 /* An array INCR_VEC of incr_infos is used during analysis of related
373 candidates having an SSA name for a stride. INCR_VEC_LEN describes
374 its current length. MAX_INCR_VEC_LEN is used to avoid costly
375 pathological cases. */
376 static incr_info_t incr_vec
;
377 static unsigned incr_vec_len
;
378 const int MAX_INCR_VEC_LEN
= 16;
380 /* For a chain of candidates with unknown stride, indicates whether or not
381 we must generate pointer arithmetic when replacing statements. */
382 static bool address_arithmetic_p
;
384 /* Forward function declarations. */
385 static slsr_cand_t
base_cand_from_table (tree
);
386 static tree
introduce_cast_before_cand (slsr_cand_t
, tree
, tree
);
387 static bool legal_cast_p_1 (tree
, tree
);
389 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
392 lookup_cand (cand_idx idx
)
394 return cand_vec
[idx
- 1];
397 /* Helper for hashing a candidate chain header. */
399 struct cand_chain_hasher
: typed_noop_remove
<cand_chain
>
401 typedef cand_chain value_type
;
402 typedef cand_chain compare_type
;
403 static inline hashval_t
hash (const value_type
*);
404 static inline bool equal (const value_type
*, const compare_type
*);
408 cand_chain_hasher::hash (const value_type
*p
)
410 tree base_expr
= p
->base_expr
;
411 return iterative_hash_expr (base_expr
, 0);
415 cand_chain_hasher::equal (const value_type
*chain1
, const compare_type
*chain2
)
417 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
420 /* Hash table embodying a mapping from base exprs to chains of candidates. */
421 static hash_table
<cand_chain_hasher
> base_cand_map
;
423 /* Look in the candidate table for a CAND_PHI that defines BASE and
424 return it if found; otherwise return NULL. */
427 find_phi_def (tree base
)
431 if (TREE_CODE (base
) != SSA_NAME
)
434 c
= base_cand_from_table (base
);
436 if (!c
|| c
->kind
!= CAND_PHI
)
442 /* Helper routine for find_basis_for_candidate. May be called twice:
443 once for the candidate's base expr, and optionally again for the
444 candidate's phi definition. */
447 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
449 cand_chain mapping_key
;
451 slsr_cand_t basis
= NULL
;
453 // Limit potential of N^2 behavior for long candidate chains.
455 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
457 mapping_key
.base_expr
= base_expr
;
458 chain
= base_cand_map
.find (&mapping_key
);
460 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
462 slsr_cand_t one_basis
= chain
->cand
;
464 if (one_basis
->kind
!= c
->kind
465 || one_basis
->cand_stmt
== c
->cand_stmt
466 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
467 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
468 || !dominated_by_p (CDI_DOMINATORS
,
469 gimple_bb (c
->cand_stmt
),
470 gimple_bb (one_basis
->cand_stmt
)))
473 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
480 /* Use the base expr from candidate C to look for possible candidates
481 that can serve as a basis for C. Each potential basis must also
482 appear in a block that dominates the candidate statement and have
483 the same stride and type. If more than one possible basis exists,
484 the one with highest index in the vector is chosen; this will be
485 the most immediately dominating basis. */
488 find_basis_for_candidate (slsr_cand_t c
)
490 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
492 /* If a candidate doesn't have a basis using its base expression,
493 it may have a basis hidden by one or more intervening phis. */
494 if (!basis
&& c
->def_phi
)
496 basic_block basis_bb
, phi_bb
;
497 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
498 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
502 /* A hidden basis must dominate the phi-definition of the
503 candidate's base name. */
504 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
505 basis_bb
= gimple_bb (basis
->cand_stmt
);
507 if (phi_bb
== basis_bb
508 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
514 /* If we found a hidden basis, estimate additional dead-code
515 savings if the phi and its feeding statements can be removed. */
516 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
517 c
->dead_savings
+= phi_cand
->dead_savings
;
523 c
->sibling
= basis
->dependent
;
524 basis
->dependent
= c
->cand_num
;
525 return basis
->cand_num
;
531 /* Record a mapping from the base expression of C to C itself, indicating that
532 C may potentially serve as a basis using that base expression. */
535 record_potential_basis (slsr_cand_t c
)
540 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
541 node
->base_expr
= c
->base_expr
;
544 slot
= base_cand_map
.find_slot (node
, INSERT
);
548 cand_chain_t head
= (cand_chain_t
) (*slot
);
549 node
->next
= head
->next
;
556 /* Allocate storage for a new candidate and initialize its fields.
557 Attempt to find a basis for the candidate. */
560 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
561 double_int index
, tree stride
, tree ctype
,
564 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
570 c
->cand_type
= ctype
;
572 c
->cand_num
= cand_vec
.length () + 1;
576 c
->def_phi
= kind
== CAND_MULT
? find_phi_def (base
) : 0;
577 c
->dead_savings
= savings
;
579 cand_vec
.safe_push (c
);
581 if (kind
== CAND_PHI
)
584 c
->basis
= find_basis_for_candidate (c
);
586 record_potential_basis (c
);
591 /* Determine the target cost of statement GS when compiling according
595 stmt_cost (gimple gs
, bool speed
)
597 tree lhs
, rhs1
, rhs2
;
598 enum machine_mode lhs_mode
;
600 gcc_assert (is_gimple_assign (gs
));
601 lhs
= gimple_assign_lhs (gs
);
602 rhs1
= gimple_assign_rhs1 (gs
);
603 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
605 switch (gimple_assign_rhs_code (gs
))
608 rhs2
= gimple_assign_rhs2 (gs
);
610 if (host_integerp (rhs2
, 0))
611 return mult_by_coeff_cost (TREE_INT_CST_LOW (rhs2
), lhs_mode
, speed
);
613 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
614 return mul_cost (speed
, lhs_mode
);
617 case POINTER_PLUS_EXPR
:
619 return add_cost (speed
, lhs_mode
);
622 return neg_cost (speed
, lhs_mode
);
625 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
627 /* Note that we don't assign costs to copies that in most cases
637 /* Look up the defining statement for BASE_IN and return a pointer
638 to its candidate in the candidate table, if any; otherwise NULL.
639 Only CAND_ADD and CAND_MULT candidates are returned. */
642 base_cand_from_table (tree base_in
)
646 gimple def
= SSA_NAME_DEF_STMT (base_in
);
648 return (slsr_cand_t
) NULL
;
650 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
652 if (result
&& (*result
)->kind
!= CAND_REF
)
655 return (slsr_cand_t
) NULL
;
658 /* Add an entry to the statement-to-candidate mapping. */
661 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
663 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
668 /* Given PHI which contains a phi statement, determine whether it
669 satisfies all the requirements of a phi candidate. If so, create
670 a candidate. Note that a CAND_PHI never has a basis itself, but
671 is used to help find a basis for subsequent candidates. */
674 slsr_process_phi (gimple phi
, bool speed
)
677 tree arg0_base
= NULL_TREE
, base_type
;
679 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
680 unsigned savings
= 0;
682 /* A CAND_PHI requires each of its arguments to have the same
683 derived base name. (See the module header commentary for a
684 definition of derived base names.) Furthermore, all feeding
685 definitions must be in the same position in the loop hierarchy
688 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
690 slsr_cand_t arg_cand
;
691 tree arg
= gimple_phi_arg_def (phi
, i
);
692 tree derived_base_name
= NULL_TREE
;
693 gimple arg_stmt
= NULL
;
694 basic_block arg_bb
= NULL
;
696 if (TREE_CODE (arg
) != SSA_NAME
)
699 arg_cand
= base_cand_from_table (arg
);
703 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
705 if (!arg_cand
->next_interp
)
708 arg_cand
= lookup_cand (arg_cand
->next_interp
);
711 if (!integer_onep (arg_cand
->stride
))
714 derived_base_name
= arg_cand
->base_expr
;
715 arg_stmt
= arg_cand
->cand_stmt
;
716 arg_bb
= gimple_bb (arg_stmt
);
718 /* Gather potential dead code savings if the phi statement
719 can be removed later on. */
720 if (has_single_use (arg
))
722 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
723 savings
+= arg_cand
->dead_savings
;
725 savings
+= stmt_cost (arg_stmt
, speed
);
730 derived_base_name
= arg
;
732 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
733 arg_bb
= single_succ (ENTRY_BLOCK_PTR
);
735 gimple_bb (SSA_NAME_DEF_STMT (arg
));
738 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
742 arg0_base
= derived_base_name
;
743 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
747 /* Create the candidate. "alloc_cand_and_find_basis" is named
748 misleadingly for this case, as no basis will be sought for a
750 base_type
= TREE_TYPE (arg0_base
);
752 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
, double_int_zero
,
753 integer_one_node
, base_type
, savings
);
755 /* Add the candidate to the statement-candidate mapping. */
756 add_cand_for_stmt (phi
, c
);
759 /* Given PBASE which is a pointer to tree, look up the defining
760 statement for it and check whether the candidate is in the
763 X = B + (1 * S), S is integer constant
764 X = B + (i * S), S is integer one
766 If so, set PBASE to the candidate's base_expr and return double
768 Otherwise, just return double int zero. */
771 backtrace_base_for_ref (tree
*pbase
)
773 tree base_in
= *pbase
;
774 slsr_cand_t base_cand
;
776 STRIP_NOPS (base_in
);
778 /* Strip off widening conversion(s) to handle cases where
779 e.g. 'B' is widened from an 'int' in order to calculate
781 if (CONVERT_EXPR_P (base_in
)
782 && legal_cast_p_1 (base_in
, TREE_OPERAND (base_in
, 0)))
783 base_in
= get_unwidened (base_in
, NULL_TREE
);
785 if (TREE_CODE (base_in
) != SSA_NAME
)
786 return tree_to_double_int (integer_zero_node
);
788 base_cand
= base_cand_from_table (base_in
);
790 while (base_cand
&& base_cand
->kind
!= CAND_PHI
)
792 if (base_cand
->kind
== CAND_ADD
793 && base_cand
->index
.is_one ()
794 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
796 /* X = B + (1 * S), S is integer constant. */
797 *pbase
= base_cand
->base_expr
;
798 return tree_to_double_int (base_cand
->stride
);
800 else if (base_cand
->kind
== CAND_ADD
801 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
802 && integer_onep (base_cand
->stride
))
804 /* X = B + (i * S), S is integer one. */
805 *pbase
= base_cand
->base_expr
;
806 return base_cand
->index
;
809 if (base_cand
->next_interp
)
810 base_cand
= lookup_cand (base_cand
->next_interp
);
815 return tree_to_double_int (integer_zero_node
);
818 /* Look for the following pattern:
820 *PBASE: MEM_REF (T1, C1)
822 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
824 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
826 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
828 *PINDEX: C4 * BITS_PER_UNIT
830 If not present, leave the input values unchanged and return FALSE.
831 Otherwise, modify the input values as follows and return TRUE:
834 *POFFSET: MULT_EXPR (T2, C3)
835 *PINDEX: C1 + (C2 * C3) + C4
837 When T2 is recorded by a CAND_ADD in the form of (T2' + C5), it
838 will be further restructured to:
841 *POFFSET: MULT_EXPR (T2', C3)
842 *PINDEX: C1 + (C2 * C3) + C4 + (C5 * C3) */
845 restructure_reference (tree
*pbase
, tree
*poffset
, double_int
*pindex
,
848 tree base
= *pbase
, offset
= *poffset
;
849 double_int index
= *pindex
;
850 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
851 tree mult_op0
, mult_op1
, t1
, t2
, type
;
852 double_int c1
, c2
, c3
, c4
, c5
;
856 || TREE_CODE (base
) != MEM_REF
857 || TREE_CODE (offset
) != MULT_EXPR
858 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
859 || !index
.umod (bpu
, FLOOR_MOD_EXPR
).is_zero ())
862 t1
= TREE_OPERAND (base
, 0);
863 c1
= mem_ref_offset (base
);
864 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
866 mult_op0
= TREE_OPERAND (offset
, 0);
867 mult_op1
= TREE_OPERAND (offset
, 1);
869 c3
= tree_to_double_int (mult_op1
);
871 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
873 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
875 t2
= TREE_OPERAND (mult_op0
, 0);
876 c2
= tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
881 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
883 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
885 t2
= TREE_OPERAND (mult_op0
, 0);
886 c2
= -tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
894 c2
= double_int_zero
;
897 c4
= index
.udiv (bpu
, FLOOR_DIV_EXPR
);
898 c5
= backtrace_base_for_ref (&t2
);
901 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, fold_convert (sizetype
, t2
),
902 double_int_to_tree (sizetype
, c3
));
903 *pindex
= c1
+ c2
* c3
+ c4
+ c5
* c3
;
909 /* Given GS which contains a data reference, create a CAND_REF entry in
910 the candidate table and attempt to find a basis. */
913 slsr_process_ref (gimple gs
)
915 tree ref_expr
, base
, offset
, type
;
916 HOST_WIDE_INT bitsize
, bitpos
;
917 enum machine_mode mode
;
918 int unsignedp
, volatilep
;
922 if (gimple_vdef (gs
))
923 ref_expr
= gimple_assign_lhs (gs
);
925 ref_expr
= gimple_assign_rhs1 (gs
);
927 if (!handled_component_p (ref_expr
)
928 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
929 || (TREE_CODE (ref_expr
) == COMPONENT_REF
930 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
933 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
934 &unsignedp
, &volatilep
, false);
935 index
= double_int::from_uhwi (bitpos
);
937 if (!restructure_reference (&base
, &offset
, &index
, &type
))
940 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
943 /* Add the candidate to the statement-candidate mapping. */
944 add_cand_for_stmt (gs
, c
);
947 /* Create a candidate entry for a statement GS, where GS multiplies
948 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
949 about the two SSA names into the new candidate. Return the new
953 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
955 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
957 unsigned savings
= 0;
959 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
961 /* Look at all interpretations of the base candidate, if necessary,
962 to find information to propagate into this candidate. */
963 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
966 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
972 base
= base_cand
->base_expr
;
973 index
= base_cand
->index
;
975 ctype
= base_cand
->cand_type
;
976 if (has_single_use (base_in
))
977 savings
= (base_cand
->dead_savings
978 + stmt_cost (base_cand
->cand_stmt
, speed
));
980 else if (base_cand
->kind
== CAND_ADD
981 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
983 /* Y = B + (i' * S), S constant
985 ============================
986 X = B + ((i' * S) * Z) */
987 base
= base_cand
->base_expr
;
988 index
= base_cand
->index
* tree_to_double_int (base_cand
->stride
);
990 ctype
= base_cand
->cand_type
;
991 if (has_single_use (base_in
))
992 savings
= (base_cand
->dead_savings
993 + stmt_cost (base_cand
->cand_stmt
, speed
));
996 if (base_cand
->next_interp
)
997 base_cand
= lookup_cand (base_cand
->next_interp
);
1004 /* No interpretations had anything useful to propagate, so
1005 produce X = (Y + 0) * Z. */
1007 index
= double_int_zero
;
1009 ctype
= TREE_TYPE (base_in
);
1012 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1017 /* Create a candidate entry for a statement GS, where GS multiplies
1018 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
1019 information about BASE_IN into the new candidate. Return the new
1023 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
1025 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1026 double_int index
, temp
;
1027 unsigned savings
= 0;
1029 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1031 /* Look at all interpretations of the base candidate, if necessary,
1032 to find information to propagate into this candidate. */
1033 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1035 if (base_cand
->kind
== CAND_MULT
1036 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1038 /* Y = (B + i') * S, S constant
1040 ============================
1041 X = (B + i') * (S * c) */
1042 base
= base_cand
->base_expr
;
1043 index
= base_cand
->index
;
1044 temp
= tree_to_double_int (base_cand
->stride
)
1045 * tree_to_double_int (stride_in
);
1046 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
1047 ctype
= base_cand
->cand_type
;
1048 if (has_single_use (base_in
))
1049 savings
= (base_cand
->dead_savings
1050 + stmt_cost (base_cand
->cand_stmt
, speed
));
1052 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
1056 ===========================
1058 base
= base_cand
->base_expr
;
1059 index
= base_cand
->index
;
1061 ctype
= base_cand
->cand_type
;
1062 if (has_single_use (base_in
))
1063 savings
= (base_cand
->dead_savings
1064 + stmt_cost (base_cand
->cand_stmt
, speed
));
1066 else if (base_cand
->kind
== CAND_ADD
1067 && base_cand
->index
.is_one ()
1068 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
1070 /* Y = B + (1 * S), S constant
1072 ===========================
1074 base
= base_cand
->base_expr
;
1075 index
= tree_to_double_int (base_cand
->stride
);
1077 ctype
= base_cand
->cand_type
;
1078 if (has_single_use (base_in
))
1079 savings
= (base_cand
->dead_savings
1080 + stmt_cost (base_cand
->cand_stmt
, speed
));
1083 if (base_cand
->next_interp
)
1084 base_cand
= lookup_cand (base_cand
->next_interp
);
1091 /* No interpretations had anything useful to propagate, so
1092 produce X = (Y + 0) * c. */
1094 index
= double_int_zero
;
1096 ctype
= TREE_TYPE (base_in
);
1099 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1104 /* Given GS which is a multiply of scalar integers, make an appropriate
1105 entry in the candidate table. If this is a multiply of two SSA names,
1106 create two CAND_MULT interpretations and attempt to find a basis for
1107 each of them. Otherwise, create a single CAND_MULT and attempt to
1111 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1115 /* If this is a multiply of an SSA name with itself, it is highly
1116 unlikely that we will get a strength reduction opportunity, so
1117 don't record it as a candidate. This simplifies the logic for
1118 finding a basis, so if this is removed that must be considered. */
1122 if (TREE_CODE (rhs2
) == SSA_NAME
)
1124 /* Record an interpretation of this statement in the candidate table
1125 assuming RHS1 is the base expression and RHS2 is the stride. */
1126 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1128 /* Add the first interpretation to the statement-candidate mapping. */
1129 add_cand_for_stmt (gs
, c
);
1131 /* Record another interpretation of this statement assuming RHS1
1132 is the stride and RHS2 is the base expression. */
1133 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1134 c
->next_interp
= c2
->cand_num
;
1138 /* Record an interpretation for the multiply-immediate. */
1139 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1141 /* Add the interpretation to the statement-candidate mapping. */
1142 add_cand_for_stmt (gs
, c
);
1146 /* Create a candidate entry for a statement GS, where GS adds two
1147 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1148 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1149 information about the two SSA names into the new candidate.
1150 Return the new candidate. */
1153 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1154 bool subtract_p
, bool speed
)
1156 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1158 unsigned savings
= 0;
1160 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1161 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1163 /* The most useful transformation is a multiply-immediate feeding
1164 an add or subtract. Look for that first. */
1165 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1167 if (addend_cand
->kind
== CAND_MULT
1168 && addend_cand
->index
.is_zero ()
1169 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1171 /* Z = (B + 0) * S, S constant
1173 ===========================
1174 X = Y + ((+/-1 * S) * B) */
1176 index
= tree_to_double_int (addend_cand
->stride
);
1179 stride
= addend_cand
->base_expr
;
1180 ctype
= TREE_TYPE (base_in
);
1181 if (has_single_use (addend_in
))
1182 savings
= (addend_cand
->dead_savings
1183 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1186 if (addend_cand
->next_interp
)
1187 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1192 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1194 if (base_cand
->kind
== CAND_ADD
1195 && (base_cand
->index
.is_zero ()
1196 || operand_equal_p (base_cand
->stride
,
1197 integer_zero_node
, 0)))
1199 /* Y = B + (i' * S), i' * S = 0
1201 ============================
1202 X = B + (+/-1 * Z) */
1203 base
= base_cand
->base_expr
;
1204 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1206 ctype
= base_cand
->cand_type
;
1207 if (has_single_use (base_in
))
1208 savings
= (base_cand
->dead_savings
1209 + stmt_cost (base_cand
->cand_stmt
, speed
));
1211 else if (subtract_p
)
1213 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1215 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1217 if (subtrahend_cand
->kind
== CAND_MULT
1218 && subtrahend_cand
->index
.is_zero ()
1219 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1221 /* Z = (B + 0) * S, S constant
1223 ===========================
1224 Value: X = Y + ((-1 * S) * B) */
1226 index
= tree_to_double_int (subtrahend_cand
->stride
);
1228 stride
= subtrahend_cand
->base_expr
;
1229 ctype
= TREE_TYPE (base_in
);
1230 if (has_single_use (addend_in
))
1231 savings
= (subtrahend_cand
->dead_savings
1232 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1235 if (subtrahend_cand
->next_interp
)
1236 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1238 subtrahend_cand
= NULL
;
1242 if (base_cand
->next_interp
)
1243 base_cand
= lookup_cand (base_cand
->next_interp
);
1250 /* No interpretations had anything useful to propagate, so
1251 produce X = Y + (1 * Z). */
1253 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1255 ctype
= TREE_TYPE (base_in
);
1258 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1263 /* Create a candidate entry for a statement GS, where GS adds SSA
1264 name BASE_IN to constant INDEX_IN. Propagate any known information
1265 about BASE_IN into the new candidate. Return the new candidate. */
1268 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
1270 enum cand_kind kind
= CAND_ADD
;
1271 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1272 double_int index
, multiple
;
1273 unsigned savings
= 0;
1275 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1277 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1279 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
1281 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1282 && index_in
.multiple_of (tree_to_double_int (base_cand
->stride
),
1283 unsigned_p
, &multiple
))
1285 /* Y = (B + i') * S, S constant, c = kS for some integer k
1287 ============================
1288 X = (B + (i'+ k)) * S
1290 Y = B + (i' * S), S constant, c = kS for some integer k
1292 ============================
1293 X = (B + (i'+ k)) * S */
1294 kind
= base_cand
->kind
;
1295 base
= base_cand
->base_expr
;
1296 index
= base_cand
->index
+ multiple
;
1297 stride
= base_cand
->stride
;
1298 ctype
= base_cand
->cand_type
;
1299 if (has_single_use (base_in
))
1300 savings
= (base_cand
->dead_savings
1301 + stmt_cost (base_cand
->cand_stmt
, speed
));
1304 if (base_cand
->next_interp
)
1305 base_cand
= lookup_cand (base_cand
->next_interp
);
1312 /* No interpretations had anything useful to propagate, so
1313 produce X = Y + (c * 1). */
1317 stride
= integer_one_node
;
1318 ctype
= TREE_TYPE (base_in
);
1321 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1326 /* Given GS which is an add or subtract of scalar integers or pointers,
1327 make at least one appropriate entry in the candidate table. */
1330 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1332 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1333 slsr_cand_t c
= NULL
, c2
;
1335 if (TREE_CODE (rhs2
) == SSA_NAME
)
1337 /* First record an interpretation assuming RHS1 is the base expression
1338 and RHS2 is the stride. But it doesn't make sense for the
1339 stride to be a pointer, so don't record a candidate in that case. */
1340 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1342 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1344 /* Add the first interpretation to the statement-candidate
1346 add_cand_for_stmt (gs
, c
);
1349 /* If the two RHS operands are identical, or this is a subtract,
1351 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1354 /* Otherwise, record another interpretation assuming RHS2 is the
1355 base expression and RHS1 is the stride, again provided that the
1356 stride is not a pointer. */
1357 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1359 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1361 c
->next_interp
= c2
->cand_num
;
1363 add_cand_for_stmt (gs
, c2
);
1370 /* Record an interpretation for the add-immediate. */
1371 index
= tree_to_double_int (rhs2
);
1375 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1377 /* Add the interpretation to the statement-candidate mapping. */
1378 add_cand_for_stmt (gs
, c
);
1382 /* Given GS which is a negate of a scalar integer, make an appropriate
1383 entry in the candidate table. A negate is equivalent to a multiply
1387 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1389 /* Record a CAND_MULT interpretation for the multiply by -1. */
1390 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1392 /* Add the interpretation to the statement-candidate mapping. */
1393 add_cand_for_stmt (gs
, c
);
1396 /* Help function for legal_cast_p, operating on two trees. Checks
1397 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1398 for more details. */
1401 legal_cast_p_1 (tree lhs
, tree rhs
)
1403 tree lhs_type
, rhs_type
;
1404 unsigned lhs_size
, rhs_size
;
1405 bool lhs_wraps
, rhs_wraps
;
1407 lhs_type
= TREE_TYPE (lhs
);
1408 rhs_type
= TREE_TYPE (rhs
);
1409 lhs_size
= TYPE_PRECISION (lhs_type
);
1410 rhs_size
= TYPE_PRECISION (rhs_type
);
1411 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1412 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1414 if (lhs_size
< rhs_size
1415 || (rhs_wraps
&& !lhs_wraps
)
1416 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1422 /* Return TRUE if GS is a statement that defines an SSA name from
1423 a conversion and is legal for us to combine with an add and multiply
1424 in the candidate table. For example, suppose we have:
1430 Without the type-cast, we would create a CAND_MULT for D with base B,
1431 index i, and stride S. We want to record this candidate only if it
1432 is equivalent to apply the type cast following the multiply:
1438 We will record the type with the candidate for D. This allows us
1439 to use a similar previous candidate as a basis. If we have earlier seen
1445 we can replace D with
1447 D = D' + (i - i') * S;
1449 But if moving the type-cast would change semantics, we mustn't do this.
1451 This is legitimate for casts from a non-wrapping integral type to
1452 any integral type of the same or larger size. It is not legitimate
1453 to convert a wrapping type to a non-wrapping type, or to a wrapping
1454 type of a different size. I.e., with a wrapping type, we must
1455 assume that the addition B + i could wrap, in which case performing
1456 the multiply before or after one of the "illegal" type casts will
1457 have different semantics. */
1460 legal_cast_p (gimple gs
, tree rhs
)
1462 if (!is_gimple_assign (gs
)
1463 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1466 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1469 /* Given GS which is a cast to a scalar integer type, determine whether
1470 the cast is legal for strength reduction. If so, make at least one
1471 appropriate entry in the candidate table. */
1474 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1477 slsr_cand_t base_cand
, c
, c2
;
1478 unsigned savings
= 0;
1480 if (!legal_cast_p (gs
, rhs1
))
1483 lhs
= gimple_assign_lhs (gs
);
1484 base_cand
= base_cand_from_table (rhs1
);
1485 ctype
= TREE_TYPE (lhs
);
1487 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1491 /* Propagate all data from the base candidate except the type,
1492 which comes from the cast, and the base candidate's cast,
1493 which is no longer applicable. */
1494 if (has_single_use (rhs1
))
1495 savings
= (base_cand
->dead_savings
1496 + stmt_cost (base_cand
->cand_stmt
, speed
));
1498 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1499 base_cand
->base_expr
,
1500 base_cand
->index
, base_cand
->stride
,
1502 if (base_cand
->next_interp
)
1503 base_cand
= lookup_cand (base_cand
->next_interp
);
1510 /* If nothing is known about the RHS, create fresh CAND_ADD and
1511 CAND_MULT interpretations:
1516 The first of these is somewhat arbitrary, but the choice of
1517 1 for the stride simplifies the logic for propagating casts
1519 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1520 integer_one_node
, ctype
, 0);
1521 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1522 integer_one_node
, ctype
, 0);
1523 c
->next_interp
= c2
->cand_num
;
1526 /* Add the first (or only) interpretation to the statement-candidate
1528 add_cand_for_stmt (gs
, c
);
1531 /* Given GS which is a copy of a scalar integer type, make at least one
1532 appropriate entry in the candidate table.
1534 This interface is included for completeness, but is unnecessary
1535 if this pass immediately follows a pass that performs copy
1536 propagation, such as DOM. */
1539 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1541 slsr_cand_t base_cand
, c
, c2
;
1542 unsigned savings
= 0;
1544 base_cand
= base_cand_from_table (rhs1
);
1546 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1550 /* Propagate all data from the base candidate. */
1551 if (has_single_use (rhs1
))
1552 savings
= (base_cand
->dead_savings
1553 + stmt_cost (base_cand
->cand_stmt
, speed
));
1555 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1556 base_cand
->base_expr
,
1557 base_cand
->index
, base_cand
->stride
,
1558 base_cand
->cand_type
, savings
);
1559 if (base_cand
->next_interp
)
1560 base_cand
= lookup_cand (base_cand
->next_interp
);
1567 /* If nothing is known about the RHS, create fresh CAND_ADD and
1568 CAND_MULT interpretations:
1573 The first of these is somewhat arbitrary, but the choice of
1574 1 for the stride simplifies the logic for propagating casts
1576 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1577 integer_one_node
, TREE_TYPE (rhs1
), 0);
1578 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1579 integer_one_node
, TREE_TYPE (rhs1
), 0);
1580 c
->next_interp
= c2
->cand_num
;
1583 /* Add the first (or only) interpretation to the statement-candidate
1585 add_cand_for_stmt (gs
, c
);
1588 class find_candidates_dom_walker
: public dom_walker
1591 find_candidates_dom_walker (cdi_direction direction
)
1592 : dom_walker (direction
) {}
1593 virtual void before_dom_children (basic_block
);
1596 /* Find strength-reduction candidates in block BB. */
1599 find_candidates_dom_walker::before_dom_children (basic_block bb
)
1601 bool speed
= optimize_bb_for_speed_p (bb
);
1602 gimple_stmt_iterator gsi
;
1604 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1605 slsr_process_phi (gsi_stmt (gsi
), speed
);
1607 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1609 gimple gs
= gsi_stmt (gsi
);
1611 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1612 slsr_process_ref (gs
);
1614 else if (is_gimple_assign (gs
)
1615 && SCALAR_INT_MODE_P
1616 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1618 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1620 switch (gimple_assign_rhs_code (gs
))
1624 rhs1
= gimple_assign_rhs1 (gs
);
1625 rhs2
= gimple_assign_rhs2 (gs
);
1626 /* Should never happen, but currently some buggy situations
1627 in earlier phases put constants in rhs1. */
1628 if (TREE_CODE (rhs1
) != SSA_NAME
)
1632 /* Possible future opportunity: rhs1 of a ptr+ can be
1634 case POINTER_PLUS_EXPR
:
1636 rhs2
= gimple_assign_rhs2 (gs
);
1642 rhs1
= gimple_assign_rhs1 (gs
);
1643 if (TREE_CODE (rhs1
) != SSA_NAME
)
1651 switch (gimple_assign_rhs_code (gs
))
1654 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1658 case POINTER_PLUS_EXPR
:
1660 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1664 slsr_process_neg (gs
, rhs1
, speed
);
1668 slsr_process_cast (gs
, rhs1
, speed
);
1672 slsr_process_copy (gs
, rhs1
, speed
);
1682 /* Dump a candidate for debug. */
1685 dump_candidate (slsr_cand_t c
)
1687 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1688 gimple_bb (c
->cand_stmt
)->index
);
1689 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1693 fputs (" MULT : (", dump_file
);
1694 print_generic_expr (dump_file
, c
->base_expr
, 0);
1695 fputs (" + ", dump_file
);
1696 dump_double_int (dump_file
, c
->index
, false);
1697 fputs (") * ", dump_file
);
1698 print_generic_expr (dump_file
, c
->stride
, 0);
1699 fputs (" : ", dump_file
);
1702 fputs (" ADD : ", dump_file
);
1703 print_generic_expr (dump_file
, c
->base_expr
, 0);
1704 fputs (" + (", dump_file
);
1705 dump_double_int (dump_file
, c
->index
, false);
1706 fputs (" * ", dump_file
);
1707 print_generic_expr (dump_file
, c
->stride
, 0);
1708 fputs (") : ", dump_file
);
1711 fputs (" REF : ", dump_file
);
1712 print_generic_expr (dump_file
, c
->base_expr
, 0);
1713 fputs (" + (", dump_file
);
1714 print_generic_expr (dump_file
, c
->stride
, 0);
1715 fputs (") + ", dump_file
);
1716 dump_double_int (dump_file
, c
->index
, false);
1717 fputs (" : ", dump_file
);
1720 fputs (" PHI : ", dump_file
);
1721 print_generic_expr (dump_file
, c
->base_expr
, 0);
1722 fputs (" + (unknown * ", dump_file
);
1723 print_generic_expr (dump_file
, c
->stride
, 0);
1724 fputs (") : ", dump_file
);
1729 print_generic_expr (dump_file
, c
->cand_type
, 0);
1730 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1731 c
->basis
, c
->dependent
, c
->sibling
);
1732 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1733 c
->next_interp
, c
->dead_savings
);
1735 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1736 fputs ("\n", dump_file
);
1739 /* Dump the candidate vector for debug. */
1742 dump_cand_vec (void)
1747 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1749 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1753 /* Callback used to dump the candidate chains hash table. */
1756 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1758 const_cand_chain_t chain
= *slot
;
1761 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1762 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1764 for (p
= chain
->next
; p
; p
= p
->next
)
1765 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1767 fputs ("\n", dump_file
);
1771 /* Dump the candidate chains. */
1774 dump_cand_chains (void)
1776 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1777 base_cand_map
.traverse_noresize
<void *, ssa_base_cand_dump_callback
> (NULL
);
1778 fputs ("\n", dump_file
);
1781 /* Dump the increment vector for debug. */
1784 dump_incr_vec (void)
1786 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1790 fprintf (dump_file
, "\nIncrement vector:\n\n");
1792 for (i
= 0; i
< incr_vec_len
; i
++)
1794 fprintf (dump_file
, "%3d increment: ", i
);
1795 dump_double_int (dump_file
, incr_vec
[i
].incr
, false);
1796 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1797 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1798 fputs ("\n initializer: ", dump_file
);
1799 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1800 fputs ("\n\n", dump_file
);
1805 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1809 replace_ref (tree
*expr
, slsr_cand_t c
)
1811 tree add_expr
, mem_ref
, acc_type
= TREE_TYPE (*expr
);
1812 unsigned HOST_WIDE_INT misalign
;
1815 /* Ensure the memory reference carries the minimum alignment
1816 requirement for the data type. See PR58041. */
1817 get_object_alignment_1 (*expr
, &align
, &misalign
);
1819 align
= (misalign
& -misalign
);
1820 if (align
< TYPE_ALIGN (acc_type
))
1821 acc_type
= build_aligned_type (acc_type
, align
);
1823 add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1824 c
->base_expr
, c
->stride
);
1825 mem_ref
= fold_build2 (MEM_REF
, acc_type
, add_expr
,
1826 double_int_to_tree (c
->cand_type
, c
->index
));
1828 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1829 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1830 TREE_OPERAND (mem_ref
, 0)
1831 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1832 /*simple_p=*/true, NULL
,
1833 /*before=*/true, GSI_SAME_STMT
);
1834 copy_ref_info (mem_ref
, *expr
);
1836 update_stmt (c
->cand_stmt
);
1839 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1840 dependent of candidate C with an equivalent strength-reduced data
1844 replace_refs (slsr_cand_t c
)
1846 if (gimple_vdef (c
->cand_stmt
))
1848 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1849 replace_ref (lhs
, c
);
1853 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1854 replace_ref (rhs
, c
);
1858 replace_refs (lookup_cand (c
->sibling
));
1861 replace_refs (lookup_cand (c
->dependent
));
1864 /* Return TRUE if candidate C is dependent upon a PHI. */
1867 phi_dependent_cand_p (slsr_cand_t c
)
1869 /* A candidate is not necessarily dependent upon a PHI just because
1870 it has a phi definition for its base name. It may have a basis
1871 that relies upon the same phi definition, in which case the PHI
1872 is irrelevant to this candidate. */
1875 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1878 /* Calculate the increment required for candidate C relative to
1882 cand_increment (slsr_cand_t c
)
1886 /* If the candidate doesn't have a basis, just return its own
1887 index. This is useful in record_increments to help us find
1888 an existing initializer. Also, if the candidate's basis is
1889 hidden by a phi, then its own index will be the increment
1890 from the newly introduced phi basis. */
1891 if (!c
->basis
|| phi_dependent_cand_p (c
))
1894 basis
= lookup_cand (c
->basis
);
1895 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1896 return c
->index
- basis
->index
;
1899 /* Calculate the increment required for candidate C relative to
1900 its basis. If we aren't going to generate pointer arithmetic
1901 for this candidate, return the absolute value of that increment
1904 static inline double_int
1905 cand_abs_increment (slsr_cand_t c
)
1907 double_int increment
= cand_increment (c
);
1909 if (!address_arithmetic_p
&& increment
.is_negative ())
1910 increment
= -increment
;
1915 /* Return TRUE iff candidate C has already been replaced under
1916 another interpretation. */
1919 cand_already_replaced (slsr_cand_t c
)
1921 return (gimple_bb (c
->cand_stmt
) == 0);
1924 /* Common logic used by replace_unconditional_candidate and
1925 replace_conditional_candidate. */
1928 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, double_int bump
)
1930 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
1931 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1933 /* It is highly unlikely, but possible, that the resulting
1934 bump doesn't fit in a HWI. Abandon the replacement
1935 in this case. This does not affect siblings or dependents
1936 of C. Restriction to signed HWI is conservative for unsigned
1937 types but allows for safe negation without twisted logic. */
1938 if (bump
.fits_shwi ()
1939 && bump
.to_shwi () != HOST_WIDE_INT_MIN
1940 /* It is not useful to replace casts, copies, or adds of
1941 an SSA name and a constant. */
1942 && cand_code
!= MODIFY_EXPR
1943 && cand_code
!= NOP_EXPR
1944 && cand_code
!= PLUS_EXPR
1945 && cand_code
!= POINTER_PLUS_EXPR
1946 && cand_code
!= MINUS_EXPR
)
1948 enum tree_code code
= PLUS_EXPR
;
1950 gimple stmt_to_print
= NULL
;
1952 /* If the basis name and the candidate's LHS have incompatible
1953 types, introduce a cast. */
1954 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
1955 basis_name
= introduce_cast_before_cand (c
, target_type
, basis_name
);
1956 if (bump
.is_negative ())
1962 bump_tree
= double_int_to_tree (target_type
, bump
);
1964 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1966 fputs ("Replacing: ", dump_file
);
1967 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1970 if (bump
.is_zero ())
1972 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1973 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1974 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1975 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1976 gsi_replace (&gsi
, copy_stmt
, false);
1977 c
->cand_stmt
= copy_stmt
;
1978 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1979 stmt_to_print
= copy_stmt
;
1984 if (cand_code
!= NEGATE_EXPR
) {
1985 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1986 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1988 if (cand_code
!= NEGATE_EXPR
1989 && ((operand_equal_p (rhs1
, basis_name
, 0)
1990 && operand_equal_p (rhs2
, bump_tree
, 0))
1991 || (operand_equal_p (rhs1
, bump_tree
, 0)
1992 && operand_equal_p (rhs2
, basis_name
, 0))))
1994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1996 fputs ("(duplicate, not actually replacing)", dump_file
);
1997 stmt_to_print
= c
->cand_stmt
;
2002 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
2003 gimple_assign_set_rhs_with_ops (&gsi
, code
,
2004 basis_name
, bump_tree
);
2005 update_stmt (gsi_stmt (gsi
));
2006 c
->cand_stmt
= gsi_stmt (gsi
);
2007 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2008 stmt_to_print
= gsi_stmt (gsi
);
2012 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2014 fputs ("With: ", dump_file
);
2015 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
2016 fputs ("\n", dump_file
);
2021 /* Replace candidate C with an add or subtract. Note that we only
2022 operate on CAND_MULTs with known strides, so we will never generate
2023 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
2024 X = Y + ((i - i') * S), as described in the module commentary. The
2025 folded value ((i - i') * S) is referred to here as the "bump." */
2028 replace_unconditional_candidate (slsr_cand_t c
)
2031 double_int stride
, bump
;
2033 if (cand_already_replaced (c
))
2036 basis
= lookup_cand (c
->basis
);
2037 stride
= tree_to_double_int (c
->stride
);
2038 bump
= cand_increment (c
) * stride
;
2040 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
);
2043 /* Return the index in the increment vector of the given INCREMENT,
2044 or -1 if not found. The latter can occur if more than
2045 MAX_INCR_VEC_LEN increments have been found. */
2048 incr_vec_index (double_int increment
)
2052 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
2055 if (i
< incr_vec_len
)
2061 /* Create a new statement along edge E to add BASIS_NAME to the product
2062 of INCREMENT and the stride of candidate C. Create and return a new
2063 SSA name from *VAR to be used as the LHS of the new statement.
2064 KNOWN_STRIDE is true iff C's stride is a constant. */
2067 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
2068 double_int increment
, edge e
, location_t loc
,
2071 basic_block insert_bb
;
2072 gimple_stmt_iterator gsi
;
2073 tree lhs
, basis_type
;
2076 /* If the add candidate along this incoming edge has the same
2077 index as C's hidden basis, the hidden basis represents this
2079 if (increment
.is_zero ())
2082 basis_type
= TREE_TYPE (basis_name
);
2083 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2088 enum tree_code code
= PLUS_EXPR
;
2089 double_int bump
= increment
* tree_to_double_int (c
->stride
);
2090 if (bump
.is_negative ())
2096 bump_tree
= double_int_to_tree (basis_type
, bump
);
2097 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2103 bool negate_incr
= (!address_arithmetic_p
&& increment
.is_negative ());
2104 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2105 gcc_assert (i
>= 0);
2107 if (incr_vec
[i
].initializer
)
2109 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2110 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2111 incr_vec
[i
].initializer
);
2113 else if (increment
.is_one ())
2114 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, lhs
, basis_name
,
2116 else if (increment
.is_minus_one ())
2117 new_stmt
= gimple_build_assign_with_ops (MINUS_EXPR
, lhs
, basis_name
,
2123 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2124 gsi
= gsi_last_bb (insert_bb
);
2126 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2127 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2129 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2131 gimple_set_location (new_stmt
, loc
);
2133 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2135 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2136 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2142 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2143 is hidden by the phi node FROM_PHI, create a new phi node in the same
2144 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2145 with its phi arguments representing conditional adjustments to the
2146 hidden basis along conditional incoming paths. Those adjustments are
2147 made by creating add statements (and sometimes recursively creating
2148 phis) along those incoming paths. LOC is the location to attach to
2149 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2153 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2154 location_t loc
, bool known_stride
)
2160 slsr_cand_t basis
= lookup_cand (c
->basis
);
2161 int nargs
= gimple_phi_num_args (from_phi
);
2162 basic_block phi_bb
= gimple_bb (from_phi
);
2163 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2164 phi_args
.create (nargs
);
2166 /* Process each argument of the existing phi that represents
2167 conditionally-executed add candidates. */
2168 for (i
= 0; i
< nargs
; i
++)
2170 edge e
= (*phi_bb
->preds
)[i
];
2171 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2174 /* If the phi argument is the base name of the CAND_PHI, then
2175 this incoming arc should use the hidden basis. */
2176 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2177 if (basis
->index
.is_zero ())
2178 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2181 double_int incr
= -basis
->index
;
2182 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2183 e
, loc
, known_stride
);
2187 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2189 /* If there is another phi along this incoming edge, we must
2190 process it in the same fashion to ensure that all basis
2191 adjustments are made along its incoming edges. */
2192 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2193 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2197 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2198 double_int diff
= arg_cand
->index
- basis
->index
;
2199 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2200 e
, loc
, known_stride
);
2204 /* Because of recursion, we need to save the arguments in a vector
2205 so we can create the PHI statement all at once. Otherwise the
2206 storage for the half-created PHI can be reclaimed. */
2207 phi_args
.safe_push (feeding_def
);
2210 /* Create the new phi basis. */
2211 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2212 phi
= create_phi_node (name
, phi_bb
);
2213 SSA_NAME_DEF_STMT (name
) = phi
;
2215 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2217 edge e
= (*phi_bb
->preds
)[i
];
2218 add_phi_arg (phi
, phi_arg
, e
, loc
);
2223 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2225 fputs ("Introducing new phi basis: ", dump_file
);
2226 print_gimple_stmt (dump_file
, phi
, 0, 0);
2232 /* Given a candidate C whose basis is hidden by at least one intervening
2233 phi, introduce a matching number of new phis to represent its basis
2234 adjusted by conditional increments along possible incoming paths. Then
2235 replace C as though it were an unconditional candidate, using the new
2239 replace_conditional_candidate (slsr_cand_t c
)
2241 tree basis_name
, name
;
2244 double_int stride
, bump
;
2246 /* Look up the LHS SSA name from C's basis. This will be the
2247 RHS1 of the adds we will introduce to create new phi arguments. */
2248 basis
= lookup_cand (c
->basis
);
2249 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2251 /* Create a new phi statement which will represent C's true basis
2252 after the transformation is complete. */
2253 loc
= gimple_location (c
->cand_stmt
);
2254 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2255 basis_name
, loc
, KNOWN_STRIDE
);
2256 /* Replace C with an add of the new basis phi and a constant. */
2257 stride
= tree_to_double_int (c
->stride
);
2258 bump
= c
->index
* stride
;
2260 replace_mult_candidate (c
, name
, bump
);
2263 /* Compute the expected costs of inserting basis adjustments for
2264 candidate C with phi-definition PHI. The cost of inserting
2265 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2266 which are themselves phi results, recursively calculate costs
2267 for those phis as well. */
2270 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2274 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2276 /* If we work our way back to a phi that isn't dominated by the hidden
2277 basis, this isn't a candidate for replacement. Indicate this by
2278 returning an unreasonably high cost. It's not easy to detect
2279 these situations when determining the basis, so we defer the
2280 decision until now. */
2281 basic_block phi_bb
= gimple_bb (phi
);
2282 slsr_cand_t basis
= lookup_cand (c
->basis
);
2283 basic_block basis_bb
= gimple_bb (basis
->cand_stmt
);
2285 if (phi_bb
== basis_bb
|| !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
2286 return COST_INFINITE
;
2288 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2290 tree arg
= gimple_phi_arg_def (phi
, i
);
2292 if (arg
!= phi_cand
->base_expr
)
2294 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2296 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2297 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2300 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2302 if (arg_cand
->index
!= c
->index
)
2303 cost
+= one_add_cost
;
2311 /* For candidate C, each sibling of candidate C, and each dependent of
2312 candidate C, determine whether the candidate is dependent upon a
2313 phi that hides its basis. If not, replace the candidate unconditionally.
2314 Otherwise, determine whether the cost of introducing compensation code
2315 for the candidate is offset by the gains from strength reduction. If
2316 so, replace the candidate and introduce the compensation code. */
2319 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2321 if (phi_dependent_cand_p (c
))
2323 if (c
->kind
== CAND_MULT
)
2325 /* A candidate dependent upon a phi will replace a multiply by
2326 a constant with an add, and will insert at most one add for
2327 each phi argument. Add these costs with the potential dead-code
2328 savings to determine profitability. */
2329 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2330 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2331 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2332 tree phi_result
= gimple_phi_result (phi
);
2333 int one_add_cost
= add_cost (speed
,
2334 TYPE_MODE (TREE_TYPE (phi_result
)));
2335 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2336 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2338 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2340 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2341 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2342 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2343 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2344 fprintf (dump_file
, " cost = %d\n", cost
);
2345 if (cost
<= COST_NEUTRAL
)
2346 fputs (" Replacing...\n", dump_file
);
2348 fputs (" Not replaced.\n", dump_file
);
2351 if (cost
<= COST_NEUTRAL
)
2352 replace_conditional_candidate (c
);
2356 replace_unconditional_candidate (c
);
2359 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2362 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2365 /* Count the number of candidates in the tree rooted at C that have
2366 not already been replaced under other interpretations. */
2369 count_candidates (slsr_cand_t c
)
2371 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2374 count
+= count_candidates (lookup_cand (c
->sibling
));
2377 count
+= count_candidates (lookup_cand (c
->dependent
));
2382 /* Increase the count of INCREMENT by one in the increment vector.
2383 INCREMENT is associated with candidate C. If INCREMENT is to be
2384 conditionally executed as part of a conditional candidate replacement,
2385 IS_PHI_ADJUST is true, otherwise false. If an initializer
2386 T_0 = stride * I is provided by a candidate that dominates all
2387 candidates with the same increment, also record T_0 for subsequent use. */
2390 record_increment (slsr_cand_t c
, double_int increment
, bool is_phi_adjust
)
2395 /* Treat increments that differ only in sign as identical so as to
2396 share initializers, unless we are generating pointer arithmetic. */
2397 if (!address_arithmetic_p
&& increment
.is_negative ())
2398 increment
= -increment
;
2400 for (i
= 0; i
< incr_vec_len
; i
++)
2402 if (incr_vec
[i
].incr
== increment
)
2404 incr_vec
[i
].count
++;
2407 /* If we previously recorded an initializer that doesn't
2408 dominate this candidate, it's not going to be useful to
2410 if (incr_vec
[i
].initializer
2411 && !dominated_by_p (CDI_DOMINATORS
,
2412 gimple_bb (c
->cand_stmt
),
2413 incr_vec
[i
].init_bb
))
2415 incr_vec
[i
].initializer
= NULL_TREE
;
2416 incr_vec
[i
].init_bb
= NULL
;
2423 if (!found
&& incr_vec_len
< MAX_INCR_VEC_LEN
- 1)
2425 /* The first time we see an increment, create the entry for it.
2426 If this is the root candidate which doesn't have a basis, set
2427 the count to zero. We're only processing it so it can possibly
2428 provide an initializer for other candidates. */
2429 incr_vec
[incr_vec_len
].incr
= increment
;
2430 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2431 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2433 /* Optimistically record the first occurrence of this increment
2434 as providing an initializer (if it does); we will revise this
2435 opinion later if it doesn't dominate all other occurrences.
2436 Exception: increments of -1, 0, 1 never need initializers;
2437 and phi adjustments don't ever provide initializers. */
2438 if (c
->kind
== CAND_ADD
2440 && c
->index
== increment
2441 && (increment
.sgt (double_int_one
)
2442 || increment
.slt (double_int_minus_one
))
2443 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2444 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2446 tree t0
= NULL_TREE
;
2447 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2448 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2449 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2451 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2454 && SSA_NAME_DEF_STMT (t0
)
2455 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2457 incr_vec
[incr_vec_len
].initializer
= t0
;
2458 incr_vec
[incr_vec_len
++].init_bb
2459 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2463 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2464 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2469 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2470 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2475 /* Given phi statement PHI that hides a candidate from its BASIS, find
2476 the increments along each incoming arc (recursively handling additional
2477 phis that may be present) and record them. These increments are the
2478 difference in index between the index-adjusting statements and the
2479 index of the basis. */
2482 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2485 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2487 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2489 tree arg
= gimple_phi_arg_def (phi
, i
);
2491 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2493 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2495 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2496 record_phi_increments (basis
, arg_def
);
2499 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2500 double_int diff
= arg_cand
->index
- basis
->index
;
2501 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2507 /* Determine how many times each unique increment occurs in the set
2508 of candidates rooted at C's parent, recording the data in the
2509 increment vector. For each unique increment I, if an initializer
2510 T_0 = stride * I is provided by a candidate that dominates all
2511 candidates with the same increment, also record T_0 for subsequent
2515 record_increments (slsr_cand_t c
)
2517 if (!cand_already_replaced (c
))
2519 if (!phi_dependent_cand_p (c
))
2520 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2523 /* A candidate with a basis hidden by a phi will have one
2524 increment for its relationship to the index represented by
2525 the phi, and potentially additional increments along each
2526 incoming edge. For the root of the dependency tree (which
2527 has no basis), process just the initial index in case it has
2528 an initializer that can be used by subsequent candidates. */
2529 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2532 record_phi_increments (lookup_cand (c
->basis
),
2533 lookup_cand (c
->def_phi
)->cand_stmt
);
2538 record_increments (lookup_cand (c
->sibling
));
2541 record_increments (lookup_cand (c
->dependent
));
2544 /* Add up and return the costs of introducing add statements that
2545 require the increment INCR on behalf of candidate C and phi
2546 statement PHI. Accumulate into *SAVINGS the potential savings
2547 from removing existing statements that feed PHI and have no other
2551 phi_incr_cost (slsr_cand_t c
, double_int incr
, gimple phi
, int *savings
)
2555 slsr_cand_t basis
= lookup_cand (c
->basis
);
2556 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2558 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2560 tree arg
= gimple_phi_arg_def (phi
, i
);
2562 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2564 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2566 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2568 int feeding_savings
= 0;
2569 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2570 if (has_single_use (gimple_phi_result (arg_def
)))
2571 *savings
+= feeding_savings
;
2575 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2576 double_int diff
= arg_cand
->index
- basis
->index
;
2580 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2581 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2582 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2583 if (has_single_use (lhs
))
2584 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2593 /* Return the first candidate in the tree rooted at C that has not
2594 already been replaced, favoring siblings over dependents. */
2597 unreplaced_cand_in_tree (slsr_cand_t c
)
2599 if (!cand_already_replaced (c
))
2604 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2611 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2619 /* Return TRUE if the candidates in the tree rooted at C should be
2620 optimized for speed, else FALSE. We estimate this based on the block
2621 containing the most dominant candidate in the tree that has not yet
2625 optimize_cands_for_speed_p (slsr_cand_t c
)
2627 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2629 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2632 /* Add COST_IN to the lowest cost of any dependent path starting at
2633 candidate C or any of its siblings, counting only candidates along
2634 such paths with increment INCR. Assume that replacing a candidate
2635 reduces cost by REPL_SAVINGS. Also account for savings from any
2636 statements that would go dead. If COUNT_PHIS is true, include
2637 costs of introducing feeding statements for conditional candidates. */
2640 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2641 double_int incr
, bool count_phis
)
2643 int local_cost
, sib_cost
, savings
= 0;
2644 double_int cand_incr
= cand_abs_increment (c
);
2646 if (cand_already_replaced (c
))
2647 local_cost
= cost_in
;
2648 else if (incr
== cand_incr
)
2649 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2651 local_cost
= cost_in
- c
->dead_savings
;
2654 && phi_dependent_cand_p (c
)
2655 && !cand_already_replaced (c
))
2657 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2658 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2660 if (has_single_use (gimple_phi_result (phi
)))
2661 local_cost
-= savings
;
2665 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2666 lookup_cand (c
->dependent
), incr
,
2671 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2672 lookup_cand (c
->sibling
), incr
,
2674 local_cost
= MIN (local_cost
, sib_cost
);
2680 /* Compute the total savings that would accrue from all replacements
2681 in the candidate tree rooted at C, counting only candidates with
2682 increment INCR. Assume that replacing a candidate reduces cost
2683 by REPL_SAVINGS. Also account for savings from statements that
2687 total_savings (int repl_savings
, slsr_cand_t c
, double_int incr
,
2691 double_int cand_incr
= cand_abs_increment (c
);
2693 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2694 savings
+= repl_savings
+ c
->dead_savings
;
2697 && phi_dependent_cand_p (c
)
2698 && !cand_already_replaced (c
))
2700 int phi_savings
= 0;
2701 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2702 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2704 if (has_single_use (gimple_phi_result (phi
)))
2705 savings
+= phi_savings
;
2709 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2713 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2719 /* Use target-specific costs to determine and record which increments
2720 in the current candidate tree are profitable to replace, assuming
2721 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2724 One slight limitation here is that we don't account for the possible
2725 introduction of casts in some cases. See replace_one_candidate for
2726 the cases where these are introduced. This should probably be cleaned
2730 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
2734 for (i
= 0; i
< incr_vec_len
; i
++)
2736 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2738 /* If somehow this increment is bigger than a HWI, we won't
2739 be optimizing candidates that use it. And if the increment
2740 has a count of zero, nothing will be done with it. */
2741 if (!incr_vec
[i
].incr
.fits_shwi () || !incr_vec
[i
].count
)
2742 incr_vec
[i
].cost
= COST_INFINITE
;
2744 /* Increments of 0, 1, and -1 are always profitable to replace,
2745 because they always replace a multiply or add with an add or
2746 copy, and may cause one or more existing instructions to go
2747 dead. Exception: -1 can't be assumed to be profitable for
2748 pointer addition. */
2752 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2753 != POINTER_PLUS_EXPR
)))
2754 incr_vec
[i
].cost
= COST_NEUTRAL
;
2756 /* FORNOW: If we need to add an initializer, give up if a cast from
2757 the candidate's type to its stride's type can lose precision.
2758 This could eventually be handled better by expressly retaining the
2759 result of a cast to a wider type in the stride. Example:
2764 _4 = x + _3; ADD: x + (10 * _1) : int
2766 _6 = x + _3; ADD: x + (15 * _1) : int
2768 Right now replacing _6 would cause insertion of an initializer
2769 of the form "short int T = _1 * 5;" followed by a cast to
2770 int, which could overflow incorrectly. Had we recorded _2 or
2771 (int)_1 as the stride, this wouldn't happen. However, doing
2772 this breaks other opportunities, so this will require some
2774 else if (!incr_vec
[i
].initializer
2775 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2776 && !legal_cast_p_1 (first_dep
->stride
,
2777 gimple_assign_lhs (first_dep
->cand_stmt
)))
2779 incr_vec
[i
].cost
= COST_INFINITE
;
2781 /* If we need to add an initializer, make sure we don't introduce
2782 a multiply by a pointer type, which can happen in certain cast
2783 scenarios. FIXME: When cleaning up these cast issues, we can
2784 afford to introduce the multiply provided we cast out to an
2785 unsigned int of appropriate size. */
2786 else if (!incr_vec
[i
].initializer
2787 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2788 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2790 incr_vec
[i
].cost
= COST_INFINITE
;
2792 /* For any other increment, if this is a multiply candidate, we
2793 must introduce a temporary T and initialize it with
2794 T_0 = stride * increment. When optimizing for speed, walk the
2795 candidate tree to calculate the best cost reduction along any
2796 path; if it offsets the fixed cost of inserting the initializer,
2797 replacing the increment is profitable. When optimizing for
2798 size, instead calculate the total cost reduction from replacing
2799 all candidates with this increment. */
2800 else if (first_dep
->kind
== CAND_MULT
)
2802 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2803 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2805 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2806 incr_vec
[i
].incr
, COUNT_PHIS
);
2808 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2811 incr_vec
[i
].cost
= cost
;
2814 /* If this is an add candidate, the initializer may already
2815 exist, so only calculate the cost of the initializer if it
2816 doesn't. We are replacing one add with another here, so the
2817 known replacement savings is zero. We will account for removal
2818 of dead instructions in lowest_cost_path or total_savings. */
2822 if (!incr_vec
[i
].initializer
)
2823 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2826 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2829 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2832 incr_vec
[i
].cost
= cost
;
2837 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2838 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2839 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2840 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2841 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2844 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2845 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2861 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2863 /* If both candidates are in the same block, the earlier
2865 if (bb1
== ncd
&& bb2
== ncd
)
2867 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2873 /* Otherwise, if one of them produced a candidate in the
2874 dominator, that one wins. */
2875 else if (bb1
== ncd
)
2878 else if (bb2
== ncd
)
2881 /* If neither matches the dominator, neither wins. */
2888 /* Consider all candidates that feed PHI. Find the nearest common
2889 dominator of those candidates requiring the given increment INCR.
2890 Further find and return the nearest common dominator of this result
2891 with block NCD. If the returned block contains one or more of the
2892 candidates, return the earliest candidate in the block in *WHERE. */
2895 ncd_with_phi (slsr_cand_t c
, double_int incr
, gimple phi
,
2896 basic_block ncd
, slsr_cand_t
*where
)
2899 slsr_cand_t basis
= lookup_cand (c
->basis
);
2900 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2902 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2904 tree arg
= gimple_phi_arg_def (phi
, i
);
2906 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2908 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2910 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2911 ncd
= ncd_with_phi (c
, incr
, arg_def
, ncd
, where
);
2914 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2915 double_int diff
= arg_cand
->index
- basis
->index
;
2917 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
2918 ncd
= ncd_for_two_cands (ncd
, gimple_bb (arg_cand
->cand_stmt
),
2919 *where
, arg_cand
, where
);
2927 /* Consider the candidate C together with any candidates that feed
2928 C's phi dependence (if any). Find and return the nearest common
2929 dominator of those candidates requiring the given increment INCR.
2930 If the returned block contains one or more of the candidates,
2931 return the earliest candidate in the block in *WHERE. */
2934 ncd_of_cand_and_phis (slsr_cand_t c
, double_int incr
, slsr_cand_t
*where
)
2936 basic_block ncd
= NULL
;
2938 if (cand_abs_increment (c
) == incr
)
2940 ncd
= gimple_bb (c
->cand_stmt
);
2944 if (phi_dependent_cand_p (c
))
2945 ncd
= ncd_with_phi (c
, incr
, lookup_cand (c
->def_phi
)->cand_stmt
,
2951 /* Consider all candidates in the tree rooted at C for which INCR
2952 represents the required increment of C relative to its basis.
2953 Find and return the basic block that most nearly dominates all
2954 such candidates. If the returned block contains one or more of
2955 the candidates, return the earliest candidate in the block in
2959 nearest_common_dominator_for_cands (slsr_cand_t c
, double_int incr
,
2962 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
2963 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
2965 /* First find the NCD of all siblings and dependents. */
2967 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
2970 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
2972 if (!sib_ncd
&& !dep_ncd
)
2977 else if (sib_ncd
&& !dep_ncd
)
2979 new_where
= sib_where
;
2982 else if (dep_ncd
&& !sib_ncd
)
2984 new_where
= dep_where
;
2988 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
2989 dep_where
, &new_where
);
2991 /* If the candidate's increment doesn't match the one we're interested
2992 in (and nor do any increments for feeding defs of a phi-dependence),
2993 then the result depends only on siblings and dependents. */
2994 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
2996 if (!this_ncd
|| cand_already_replaced (c
))
3002 /* Otherwise, compare this candidate with the result from all siblings
3004 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
3009 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
3012 profitable_increment_p (unsigned index
)
3014 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
3017 /* For each profitable increment in the increment vector not equal to
3018 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
3019 dominator of all statements in the candidate chain rooted at C
3020 that require that increment, and insert an initializer
3021 T_0 = stride * increment at that location. Record T_0 with the
3022 increment record. */
3025 insert_initializers (slsr_cand_t c
)
3029 for (i
= 0; i
< incr_vec_len
; i
++)
3032 slsr_cand_t where
= NULL
;
3034 tree stride_type
, new_name
, incr_tree
;
3035 double_int incr
= incr_vec
[i
].incr
;
3037 if (!profitable_increment_p (i
)
3039 || (incr
.is_minus_one ()
3040 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
3044 /* We may have already identified an existing initializer that
3046 if (incr_vec
[i
].initializer
)
3048 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3050 fputs ("Using existing initializer: ", dump_file
);
3051 print_gimple_stmt (dump_file
,
3052 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
3058 /* Find the block that most closely dominates all candidates
3059 with this increment. If there is at least one candidate in
3060 that block, the earliest one will be returned in WHERE. */
3061 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
3063 /* Create a new SSA name to hold the initializer's value. */
3064 stride_type
= TREE_TYPE (c
->stride
);
3065 new_name
= make_temp_ssa_name (stride_type
, NULL
, "slsr");
3066 incr_vec
[i
].initializer
= new_name
;
3068 /* Create the initializer and insert it in the latest possible
3069 dominating position. */
3070 incr_tree
= double_int_to_tree (stride_type
, incr
);
3071 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
3072 c
->stride
, incr_tree
);
3075 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
3076 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3077 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
3081 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
3082 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
3084 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
3085 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
3087 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
3089 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
3092 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3094 fputs ("Inserting initializer: ", dump_file
);
3095 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3100 /* Return TRUE iff all required increments for candidates feeding PHI
3101 are profitable to replace on behalf of candidate C. */
3104 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3107 slsr_cand_t basis
= lookup_cand (c
->basis
);
3108 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3110 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3112 tree arg
= gimple_phi_arg_def (phi
, i
);
3114 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3116 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3118 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3120 if (!all_phi_incrs_profitable (c
, arg_def
))
3126 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3127 double_int increment
= arg_cand
->index
- basis
->index
;
3129 if (!address_arithmetic_p
&& increment
.is_negative ())
3130 increment
= -increment
;
3132 j
= incr_vec_index (increment
);
3134 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3136 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3138 print_gimple_stmt (dump_file
, phi
, 0, 0);
3139 fputs (" increment: ", dump_file
);
3140 dump_double_int (dump_file
, increment
, false);
3143 "\n Not replaced; incr_vec overflow.\n");
3145 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3146 if (profitable_increment_p (j
))
3147 fputs (" Replacing...\n", dump_file
);
3149 fputs (" Not replaced.\n", dump_file
);
3153 if (j
< 0 || !profitable_increment_p (j
))
3162 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3163 type TO_TYPE, and insert it in front of the statement represented
3164 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3165 the new SSA name. */
3168 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
, tree from_expr
)
3172 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3174 cast_lhs
= make_temp_ssa_name (to_type
, NULL
, "slsr");
3175 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
3176 from_expr
, NULL_TREE
);
3177 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3178 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3180 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3182 fputs (" Inserting: ", dump_file
);
3183 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3189 /* Replace the RHS of the statement represented by candidate C with
3190 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3191 leave C unchanged or just interchange its operands. The original
3192 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3193 If the replacement was made and we are doing a details dump,
3194 return the revised statement, else NULL. */
3197 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3198 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3201 if (new_code
!= old_code
3202 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3203 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3204 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3205 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3207 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3208 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3209 update_stmt (gsi_stmt (gsi
));
3210 c
->cand_stmt
= gsi_stmt (gsi
);
3212 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3213 return gsi_stmt (gsi
);
3216 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3217 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3222 /* Strength-reduce the statement represented by candidate C by replacing
3223 it with an equivalent addition or subtraction. I is the index into
3224 the increment vector identifying C's increment. NEW_VAR is used to
3225 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3226 is the rhs1 to use in creating the add/subtract. */
3229 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree basis_name
)
3231 gimple stmt_to_print
= NULL
;
3232 tree orig_rhs1
, orig_rhs2
;
3234 enum tree_code orig_code
, repl_code
;
3235 double_int cand_incr
;
3237 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3238 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3239 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3240 cand_incr
= cand_increment (c
);
3242 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3244 fputs ("Replacing: ", dump_file
);
3245 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3246 stmt_to_print
= c
->cand_stmt
;
3249 if (address_arithmetic_p
)
3250 repl_code
= POINTER_PLUS_EXPR
;
3252 repl_code
= PLUS_EXPR
;
3254 /* If the increment has an initializer T_0, replace the candidate
3255 statement with an add of the basis name and the initializer. */
3256 if (incr_vec
[i
].initializer
)
3258 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3259 tree orig_type
= TREE_TYPE (orig_rhs2
);
3261 if (types_compatible_p (orig_type
, init_type
))
3262 rhs2
= incr_vec
[i
].initializer
;
3264 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3265 incr_vec
[i
].initializer
);
3267 if (incr_vec
[i
].incr
!= cand_incr
)
3269 gcc_assert (repl_code
== PLUS_EXPR
);
3270 repl_code
= MINUS_EXPR
;
3273 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3274 orig_code
, orig_rhs1
, orig_rhs2
,
3278 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3279 with a subtract of the stride from the basis name, a copy
3280 from the basis name, or an add of the stride to the basis
3281 name, respectively. It may be necessary to introduce a
3282 cast (or reuse an existing cast). */
3283 else if (cand_incr
.is_one ())
3285 tree stride_type
= TREE_TYPE (c
->stride
);
3286 tree orig_type
= TREE_TYPE (orig_rhs2
);
3288 if (types_compatible_p (orig_type
, stride_type
))
3291 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3293 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3294 orig_code
, orig_rhs1
, orig_rhs2
,
3298 else if (cand_incr
.is_minus_one ())
3300 tree stride_type
= TREE_TYPE (c
->stride
);
3301 tree orig_type
= TREE_TYPE (orig_rhs2
);
3302 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3304 if (types_compatible_p (orig_type
, stride_type
))
3307 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
);
3309 if (orig_code
!= MINUS_EXPR
3310 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3311 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3313 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3314 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3315 update_stmt (gsi_stmt (gsi
));
3316 c
->cand_stmt
= gsi_stmt (gsi
);
3318 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3319 stmt_to_print
= gsi_stmt (gsi
);
3321 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3322 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3325 else if (cand_incr
.is_zero ())
3327 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3328 tree lhs_type
= TREE_TYPE (lhs
);
3329 tree basis_type
= TREE_TYPE (basis_name
);
3331 if (types_compatible_p (lhs_type
, basis_type
))
3333 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3334 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3335 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3336 gsi_replace (&gsi
, copy_stmt
, false);
3337 c
->cand_stmt
= copy_stmt
;
3339 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3340 stmt_to_print
= copy_stmt
;
3344 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3345 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
3348 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3349 gsi_replace (&gsi
, cast_stmt
, false);
3350 c
->cand_stmt
= cast_stmt
;
3352 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3353 stmt_to_print
= cast_stmt
;
3359 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3361 fputs ("With: ", dump_file
);
3362 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3363 fputs ("\n", dump_file
);
3367 /* For each candidate in the tree rooted at C, replace it with
3368 an increment if such has been shown to be profitable. */
3371 replace_profitable_candidates (slsr_cand_t c
)
3373 if (!cand_already_replaced (c
))
3375 double_int increment
= cand_abs_increment (c
);
3376 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3379 i
= incr_vec_index (increment
);
3381 /* Only process profitable increments. Nothing useful can be done
3382 to a cast or copy. */
3384 && profitable_increment_p (i
)
3385 && orig_code
!= MODIFY_EXPR
3386 && orig_code
!= NOP_EXPR
)
3388 if (phi_dependent_cand_p (c
))
3390 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3392 if (all_phi_incrs_profitable (c
, phi
))
3394 /* Look up the LHS SSA name from C's basis. This will be
3395 the RHS1 of the adds we will introduce to create new
3397 slsr_cand_t basis
= lookup_cand (c
->basis
);
3398 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3400 /* Create a new phi statement that will represent C's true
3401 basis after the transformation is complete. */
3402 location_t loc
= gimple_location (c
->cand_stmt
);
3403 tree name
= create_phi_basis (c
, phi
, basis_name
,
3404 loc
, UNKNOWN_STRIDE
);
3406 /* Replace C with an add of the new basis phi and the
3408 replace_one_candidate (c
, i
, name
);
3413 slsr_cand_t basis
= lookup_cand (c
->basis
);
3414 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3415 replace_one_candidate (c
, i
, basis_name
);
3421 replace_profitable_candidates (lookup_cand (c
->sibling
));
3424 replace_profitable_candidates (lookup_cand (c
->dependent
));
3427 /* Analyze costs of related candidates in the candidate vector,
3428 and make beneficial replacements. */
3431 analyze_candidates_and_replace (void)
3436 /* Each candidate that has a null basis and a non-null
3437 dependent is the root of a tree of related statements.
3438 Analyze each tree to determine a subset of those
3439 statements that can be replaced with maximum benefit. */
3440 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3442 slsr_cand_t first_dep
;
3444 if (c
->basis
!= 0 || c
->dependent
== 0)
3447 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3448 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3451 first_dep
= lookup_cand (c
->dependent
);
3453 /* If this is a chain of CAND_REFs, unconditionally replace
3454 each of them with a strength-reduced data reference. */
3455 if (c
->kind
== CAND_REF
)
3458 /* If the common stride of all related candidates is a known
3459 constant, each candidate without a phi-dependence can be
3460 profitably replaced. Each replaces a multiply by a single
3461 add, with the possibility that a feeding add also goes dead.
3462 A candidate with a phi-dependence is replaced only if the
3463 compensation code it requires is offset by the strength
3464 reduction savings. */
3465 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3466 replace_uncond_cands_and_profitable_phis (first_dep
);
3468 /* When the stride is an SSA name, it may still be profitable
3469 to replace some or all of the dependent candidates, depending
3470 on whether the introduced increments can be reused, or are
3471 less expensive to calculate than the replaced statements. */
3474 enum machine_mode mode
;
3477 /* Determine whether we'll be generating pointer arithmetic
3478 when replacing candidates. */
3479 address_arithmetic_p
= (c
->kind
== CAND_ADD
3480 && POINTER_TYPE_P (c
->cand_type
));
3482 /* If all candidates have already been replaced under other
3483 interpretations, nothing remains to be done. */
3484 if (!count_candidates (c
))
3487 /* Construct an array of increments for this candidate chain. */
3488 incr_vec
= XNEWVEC (incr_info
, MAX_INCR_VEC_LEN
);
3490 record_increments (c
);
3492 /* Determine which increments are profitable to replace. */
3493 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3494 speed
= optimize_cands_for_speed_p (c
);
3495 analyze_increments (first_dep
, mode
, speed
);
3497 /* Insert initializers of the form T_0 = stride * increment
3498 for use in profitable replacements. */
3499 insert_initializers (first_dep
);
3502 /* Perform the replacements. */
3503 replace_profitable_candidates (first_dep
);
3510 execute_strength_reduction (void)
3512 /* Create the obstack where candidates will reside. */
3513 gcc_obstack_init (&cand_obstack
);
3515 /* Allocate the candidate vector. */
3516 cand_vec
.create (128);
3518 /* Allocate the mapping from statements to candidate indices. */
3519 stmt_cand_map
= pointer_map_create ();
3521 /* Create the obstack where candidate chains will reside. */
3522 gcc_obstack_init (&chain_obstack
);
3524 /* Allocate the mapping from base expressions to candidate chains. */
3525 base_cand_map
.create (500);
3527 /* Initialize the loop optimizer. We need to detect flow across
3528 back edges, and this gives us dominator information as well. */
3529 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3531 /* Walk the CFG in predominator order looking for strength reduction
3533 find_candidates_dom_walker (CDI_DOMINATORS
)
3534 .walk (cfun
->cfg
->x_entry_block_ptr
);
3536 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3539 dump_cand_chains ();
3542 /* Analyze costs and make appropriate replacements. */
3543 analyze_candidates_and_replace ();
3545 loop_optimizer_finalize ();
3546 base_cand_map
.dispose ();
3547 obstack_free (&chain_obstack
, NULL
);
3548 pointer_map_destroy (stmt_cand_map
);
3549 cand_vec
.release ();
3550 obstack_free (&cand_obstack
, NULL
);
3556 gate_strength_reduction (void)
3558 return flag_tree_slsr
;
3563 const pass_data pass_data_strength_reduction
=
3565 GIMPLE_PASS
, /* type */
3567 OPTGROUP_NONE
, /* optinfo_flags */
3568 true, /* has_gate */
3569 true, /* has_execute */
3570 TV_GIMPLE_SLSR
, /* tv_id */
3571 ( PROP_cfg
| PROP_ssa
), /* properties_required */
3572 0, /* properties_provided */
3573 0, /* properties_destroyed */
3574 0, /* todo_flags_start */
3575 TODO_verify_ssa
, /* todo_flags_finish */
3578 class pass_strength_reduction
: public gimple_opt_pass
3581 pass_strength_reduction (gcc::context
*ctxt
)
3582 : gimple_opt_pass (pass_data_strength_reduction
, ctxt
)
3585 /* opt_pass methods: */
3586 bool gate () { return gate_strength_reduction (); }
3587 unsigned int execute () { return execute_strength_reduction (); }
3589 }; // class pass_strength_reduction
3594 make_pass_strength_reduction (gcc::context
*ctxt
)
3596 return new pass_strength_reduction (ctxt
);