1 /* Straight-line strength reduction.
2 Copyright (C) 2012-2013 Free Software Foundation, Inc.
3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* There are many algorithms for performing strength reduction on
22 loops. This is not one of them. IVOPTS handles strength reduction
23 of induction variables just fine. This pass is intended to pick
24 up the crumbs it leaves behind, by considering opportunities for
25 strength reduction along dominator paths.
27 Strength reduction addresses explicit multiplies, and certain
28 multiplies implicit in addressing expressions. It would also be
29 possible to apply strength reduction to divisions and modulos,
30 but such opportunities are relatively uncommon.
32 Strength reduction is also currently restricted to integer operations.
33 If desired, it could be extended to floating-point operations under
34 control of something like -funsafe-math-optimizations. */
38 #include "coretypes.h"
41 #include "basic-block.h"
42 #include "tree-pass.h"
44 #include "gimple-pretty-print.h"
45 #include "tree-flow.h"
47 #include "pointer-set.h"
50 #include "hash-table.h"
52 /* Information about a strength reduction candidate. Each statement
53 in the candidate table represents an expression of one of the
54 following forms (the special case of CAND_REF will be described
57 (CAND_MULT) S1: X = (B + i) * S
58 (CAND_ADD) S1: X = B + (i * S)
60 Here X and B are SSA names, i is an integer constant, and S is
61 either an SSA name or a constant. We call B the "base," i the
62 "index", and S the "stride."
64 Any statement S0 that dominates S1 and is of the form:
66 (CAND_MULT) S0: Y = (B + i') * S
67 (CAND_ADD) S0: Y = B + (i' * S)
69 is called a "basis" for S1. In both cases, S1 may be replaced by
71 S1': X = Y + (i - i') * S,
73 where (i - i') * S is folded to the extent possible.
75 All gimple statements are visited in dominator order, and each
76 statement that may contribute to one of the forms of S1 above is
77 given at least one entry in the candidate table. Such statements
78 include addition, pointer addition, subtraction, multiplication,
79 negation, copies, and nontrivial type casts. If a statement may
80 represent more than one expression of the forms of S1 above,
81 multiple "interpretations" are stored in the table and chained
84 * An add of two SSA names may treat either operand as the base.
85 * A multiply of two SSA names, likewise.
86 * A copy or cast may be thought of as either a CAND_MULT with
87 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
89 Candidate records are allocated from an obstack. They are addressed
90 both from a hash table keyed on S1, and from a vector of candidate
91 pointers arranged in predominator order.
95 Currently we don't recognize:
100 as a strength reduction opportunity, even though this S1 would
101 also be replaceable by the S1' above. This can be added if it
102 comes up in practice.
104 Strength reduction in addressing
105 --------------------------------
106 There is another kind of candidate known as CAND_REF. A CAND_REF
107 describes a statement containing a memory reference having
108 complex addressing that might benefit from strength reduction.
109 Specifically, we are interested in references for which
110 get_inner_reference returns a base address, offset, and bitpos as
113 base: MEM_REF (T1, C1)
114 offset: MULT_EXPR (PLUS_EXPR (T2, C2), C3)
115 bitpos: C4 * BITS_PER_UNIT
117 Here T1 and T2 are arbitrary trees, and C1, C2, C3, C4 are
118 arbitrary integer constants. Note that C2 may be zero, in which
119 case the offset will be MULT_EXPR (T2, C3).
121 When this pattern is recognized, the original memory reference
122 can be replaced with:
124 MEM_REF (POINTER_PLUS_EXPR (T1, MULT_EXPR (T2, C3)),
127 which distributes the multiply to allow constant folding. When
128 two or more addressing expressions can be represented by MEM_REFs
129 of this form, differing only in the constants C1, C2, and C4,
130 making this substitution produces more efficient addressing during
131 the RTL phases. When there are not at least two expressions with
132 the same values of T1, T2, and C3, there is nothing to be gained
135 Strength reduction of CAND_REFs uses the same infrastructure as
136 that used by CAND_MULTs and CAND_ADDs. We record T1 in the base (B)
137 field, MULT_EXPR (T2, C3) in the stride (S) field, and
138 C1 + (C2 * C3) + C4 in the index (i) field. A basis for a CAND_REF
139 is thus another CAND_REF with the same B and S values. When at
140 least two CAND_REFs are chained together using the basis relation,
141 each of them is replaced as above, resulting in improved code
142 generation for addressing.
144 Conditional candidates
145 ======================
147 Conditional candidates are best illustrated with an example.
148 Consider the code sequence:
151 (2) a_0 = x_0 * 5; MULT (B: x_0; i: 0; S: 5)
153 (3) x_1 = x_0 + 1; ADD (B: x_0, i: 1; S: 1)
154 (4) x_2 = PHI <x_0, x_1>; PHI (B: x_0, i: 0, S: 1)
155 (5) x_3 = x_2 + 1; ADD (B: x_2, i: 1, S: 1)
156 (6) a_1 = x_3 * 5; MULT (B: x_2, i: 1; S: 5)
158 Here strength reduction is complicated by the uncertain value of x_2.
159 A legitimate transformation is:
168 (4) [x_2 = PHI <x_0, x_1>;]
169 (4a) t_2 = PHI <a_0, t_1>;
173 where the bracketed instructions may go dead.
175 To recognize this opportunity, we have to observe that statement (6)
176 has a "hidden basis" (2). The hidden basis is unlike a normal basis
177 in that the statement and the hidden basis have different base SSA
178 names (x_2 and x_0, respectively). The relationship is established
179 when a statement's base name (x_2) is defined by a phi statement (4),
180 each argument of which (x_0, x_1) has an identical "derived base name."
181 If the argument is defined by a candidate (as x_1 is by (3)) that is a
182 CAND_ADD having a stride of 1, the derived base name of the argument is
183 the base name of the candidate (x_0). Otherwise, the argument itself
184 is its derived base name (as is the case with argument x_0).
186 The hidden basis for statement (6) is the nearest dominating candidate
187 whose base name is the derived base name (x_0) of the feeding phi (4),
188 and whose stride is identical to that of the statement. We can then
189 create the new "phi basis" (4a) and feeding adds along incoming arcs (3a),
190 allowing the final replacement of (6) by the strength-reduced (6r).
192 To facilitate this, a new kind of candidate (CAND_PHI) is introduced.
193 A CAND_PHI is not a candidate for replacement, but is maintained in the
194 candidate table to ease discovery of hidden bases. Any phi statement
195 whose arguments share a common derived base name is entered into the
196 table with the derived base name, an (arbitrary) index of zero, and a
197 stride of 1. A statement with a hidden basis can then be detected by
198 simply looking up its feeding phi definition in the candidate table,
199 extracting the derived base name, and searching for a basis in the
200 usual manner after substituting the derived base name.
202 Note that the transformation is only valid when the original phi and
203 the statements that define the phi's arguments are all at the same
204 position in the loop hierarchy. */
207 /* Index into the candidate vector, offset by 1. VECs are zero-based,
208 while cand_idx's are one-based, with zero indicating null. */
209 typedef unsigned cand_idx
;
211 /* The kind of candidate. */
222 /* The candidate statement S1. */
225 /* The base expression B: often an SSA name, but not always. */
231 /* The index constant i. */
234 /* The type of the candidate. This is normally the type of base_expr,
235 but casts may have occurred when combining feeding instructions.
236 A candidate can only be a basis for candidates of the same final type.
237 (For CAND_REFs, this is the type to be used for operand 1 of the
238 replacement MEM_REF.) */
241 /* The kind of candidate (CAND_MULT, etc.). */
244 /* Index of this candidate in the candidate vector. */
247 /* Index of the next candidate record for the same statement.
248 A statement may be useful in more than one way (e.g., due to
249 commutativity). So we can have multiple "interpretations"
251 cand_idx next_interp
;
253 /* Index of the basis statement S0, if any, in the candidate vector. */
256 /* First candidate for which this candidate is a basis, if one exists. */
259 /* Next candidate having the same basis as this one. */
262 /* If this is a conditional candidate, the CAND_PHI candidate
263 that defines the base SSA name B. */
266 /* Savings that can be expected from eliminating dead code if this
267 candidate is replaced. */
271 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
272 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
274 /* Pointers to candidates are chained together as part of a mapping
275 from base expressions to the candidates that use them. */
279 /* Base expression for the chain of candidates: often, but not
280 always, an SSA name. */
283 /* Pointer to a candidate. */
287 struct cand_chain_d
*next
;
291 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
292 typedef const struct cand_chain_d
*const_cand_chain_t
;
294 /* Information about a unique "increment" associated with candidates
295 having an SSA name for a stride. An increment is the difference
296 between the index of the candidate and the index of its basis,
297 i.e., (i - i') as discussed in the module commentary.
299 When we are not going to generate address arithmetic we treat
300 increments that differ only in sign as the same, allowing sharing
301 of the cost of initializers. The absolute value of the increment
302 is stored in the incr_info. */
306 /* The increment that relates a candidate to its basis. */
309 /* How many times the increment occurs in the candidate tree. */
312 /* Cost of replacing candidates using this increment. Negative and
313 zero costs indicate replacement should be performed. */
316 /* If this increment is profitable but is not -1, 0, or 1, it requires
317 an initializer T_0 = stride * incr to be found or introduced in the
318 nearest common dominator of all candidates. This field holds T_0
319 for subsequent use. */
322 /* If the initializer was found to already exist, this is the block
323 where it was found. */
327 typedef struct incr_info_d incr_info
, *incr_info_t
;
329 /* Candidates are maintained in a vector. If candidate X dominates
330 candidate Y, then X appears before Y in the vector; but the
331 converse does not necessarily hold. */
332 static vec
<slsr_cand_t
> cand_vec
;
346 enum phi_adjust_status
352 enum count_phis_status
358 /* Pointer map embodying a mapping from statements to candidates. */
359 static struct pointer_map_t
*stmt_cand_map
;
361 /* Obstack for candidates. */
362 static struct obstack cand_obstack
;
364 /* Obstack for candidate chains. */
365 static struct obstack chain_obstack
;
367 /* An array INCR_VEC of incr_infos is used during analysis of related
368 candidates having an SSA name for a stride. INCR_VEC_LEN describes
369 its current length. */
370 static incr_info_t incr_vec
;
371 static unsigned incr_vec_len
;
373 /* For a chain of candidates with unknown stride, indicates whether or not
374 we must generate pointer arithmetic when replacing statements. */
375 static bool address_arithmetic_p
;
377 /* Forward function declarations. */
378 static slsr_cand_t
base_cand_from_table (tree
);
379 static tree
introduce_cast_before_cand (slsr_cand_t
, tree
, tree
, tree
*);
381 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
384 lookup_cand (cand_idx idx
)
386 return cand_vec
[idx
- 1];
389 /* Helper for hashing a candidate chain header. */
391 struct cand_chain_hasher
: typed_noop_remove
<cand_chain
>
393 typedef cand_chain value_type
;
394 typedef cand_chain compare_type
;
395 static inline hashval_t
hash (const value_type
*);
396 static inline bool equal (const value_type
*, const compare_type
*);
400 cand_chain_hasher::hash (const value_type
*p
)
402 tree base_expr
= p
->base_expr
;
403 return iterative_hash_expr (base_expr
, 0);
407 cand_chain_hasher::equal (const value_type
*chain1
, const compare_type
*chain2
)
409 return operand_equal_p (chain1
->base_expr
, chain2
->base_expr
, 0);
412 /* Hash table embodying a mapping from base exprs to chains of candidates. */
413 static hash_table
<cand_chain_hasher
> base_cand_map
;
415 /* Look in the candidate table for a CAND_PHI that defines BASE and
416 return it if found; otherwise return NULL. */
419 find_phi_def (tree base
)
423 if (TREE_CODE (base
) != SSA_NAME
)
426 c
= base_cand_from_table (base
);
428 if (!c
|| c
->kind
!= CAND_PHI
)
434 /* Helper routine for find_basis_for_candidate. May be called twice:
435 once for the candidate's base expr, and optionally again for the
436 candidate's phi definition. */
439 find_basis_for_base_expr (slsr_cand_t c
, tree base_expr
)
441 cand_chain mapping_key
;
443 slsr_cand_t basis
= NULL
;
445 // Limit potential of N^2 behavior for long candidate chains.
447 int max_iters
= PARAM_VALUE (PARAM_MAX_SLSR_CANDIDATE_SCAN
);
449 mapping_key
.base_expr
= base_expr
;
450 chain
= base_cand_map
.find (&mapping_key
);
452 for (; chain
&& iters
< max_iters
; chain
= chain
->next
, ++iters
)
454 slsr_cand_t one_basis
= chain
->cand
;
456 if (one_basis
->kind
!= c
->kind
457 || one_basis
->cand_stmt
== c
->cand_stmt
458 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
459 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
460 || !dominated_by_p (CDI_DOMINATORS
,
461 gimple_bb (c
->cand_stmt
),
462 gimple_bb (one_basis
->cand_stmt
)))
465 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
472 /* Use the base expr from candidate C to look for possible candidates
473 that can serve as a basis for C. Each potential basis must also
474 appear in a block that dominates the candidate statement and have
475 the same stride and type. If more than one possible basis exists,
476 the one with highest index in the vector is chosen; this will be
477 the most immediately dominating basis. */
480 find_basis_for_candidate (slsr_cand_t c
)
482 slsr_cand_t basis
= find_basis_for_base_expr (c
, c
->base_expr
);
484 /* If a candidate doesn't have a basis using its base expression,
485 it may have a basis hidden by one or more intervening phis. */
486 if (!basis
&& c
->def_phi
)
488 basic_block basis_bb
, phi_bb
;
489 slsr_cand_t phi_cand
= lookup_cand (c
->def_phi
);
490 basis
= find_basis_for_base_expr (c
, phi_cand
->base_expr
);
494 /* A hidden basis must dominate the phi-definition of the
495 candidate's base name. */
496 phi_bb
= gimple_bb (phi_cand
->cand_stmt
);
497 basis_bb
= gimple_bb (basis
->cand_stmt
);
499 if (phi_bb
== basis_bb
500 || !dominated_by_p (CDI_DOMINATORS
, phi_bb
, basis_bb
))
506 /* If we found a hidden basis, estimate additional dead-code
507 savings if the phi and its feeding statements can be removed. */
508 if (basis
&& has_single_use (gimple_phi_result (phi_cand
->cand_stmt
)))
509 c
->dead_savings
+= phi_cand
->dead_savings
;
515 c
->sibling
= basis
->dependent
;
516 basis
->dependent
= c
->cand_num
;
517 return basis
->cand_num
;
523 /* Record a mapping from the base expression of C to C itself, indicating that
524 C may potentially serve as a basis using that base expression. */
527 record_potential_basis (slsr_cand_t c
)
532 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
533 node
->base_expr
= c
->base_expr
;
536 slot
= base_cand_map
.find_slot (node
, INSERT
);
540 cand_chain_t head
= (cand_chain_t
) (*slot
);
541 node
->next
= head
->next
;
548 /* Allocate storage for a new candidate and initialize its fields.
549 Attempt to find a basis for the candidate. */
552 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
553 double_int index
, tree stride
, tree ctype
,
556 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
562 c
->cand_type
= ctype
;
564 c
->cand_num
= cand_vec
.length () + 1;
568 c
->def_phi
= find_phi_def (base
);
569 c
->dead_savings
= savings
;
571 cand_vec
.safe_push (c
);
573 if (kind
== CAND_PHI
)
576 c
->basis
= find_basis_for_candidate (c
);
578 record_potential_basis (c
);
583 /* Determine the target cost of statement GS when compiling according
587 stmt_cost (gimple gs
, bool speed
)
589 tree lhs
, rhs1
, rhs2
;
590 enum machine_mode lhs_mode
;
592 gcc_assert (is_gimple_assign (gs
));
593 lhs
= gimple_assign_lhs (gs
);
594 rhs1
= gimple_assign_rhs1 (gs
);
595 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
597 switch (gimple_assign_rhs_code (gs
))
600 rhs2
= gimple_assign_rhs2 (gs
);
602 if (host_integerp (rhs2
, 0))
603 return mult_by_coeff_cost (TREE_INT_CST_LOW (rhs2
), lhs_mode
, speed
);
605 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
606 return mul_cost (speed
, lhs_mode
);
609 case POINTER_PLUS_EXPR
:
611 return add_cost (speed
, lhs_mode
);
614 return neg_cost (speed
, lhs_mode
);
617 return convert_cost (lhs_mode
, TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
619 /* Note that we don't assign costs to copies that in most cases
629 /* Look up the defining statement for BASE_IN and return a pointer
630 to its candidate in the candidate table, if any; otherwise NULL.
631 Only CAND_ADD and CAND_MULT candidates are returned. */
634 base_cand_from_table (tree base_in
)
638 gimple def
= SSA_NAME_DEF_STMT (base_in
);
640 return (slsr_cand_t
) NULL
;
642 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
644 if (result
&& (*result
)->kind
!= CAND_REF
)
647 return (slsr_cand_t
) NULL
;
650 /* Add an entry to the statement-to-candidate mapping. */
653 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
655 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
660 /* Given PHI which contains a phi statement, determine whether it
661 satisfies all the requirements of a phi candidate. If so, create
662 a candidate. Note that a CAND_PHI never has a basis itself, but
663 is used to help find a basis for subsequent candidates. */
666 slsr_process_phi (gimple phi
, bool speed
)
669 tree arg0_base
= NULL_TREE
, base_type
;
671 struct loop
*cand_loop
= gimple_bb (phi
)->loop_father
;
672 unsigned savings
= 0;
674 /* A CAND_PHI requires each of its arguments to have the same
675 derived base name. (See the module header commentary for a
676 definition of derived base names.) Furthermore, all feeding
677 definitions must be in the same position in the loop hierarchy
680 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
682 slsr_cand_t arg_cand
;
683 tree arg
= gimple_phi_arg_def (phi
, i
);
684 tree derived_base_name
= NULL_TREE
;
685 gimple arg_stmt
= NULL
;
686 basic_block arg_bb
= NULL
;
688 if (TREE_CODE (arg
) != SSA_NAME
)
691 arg_cand
= base_cand_from_table (arg
);
695 while (arg_cand
->kind
!= CAND_ADD
&& arg_cand
->kind
!= CAND_PHI
)
697 if (!arg_cand
->next_interp
)
700 arg_cand
= lookup_cand (arg_cand
->next_interp
);
703 if (!integer_onep (arg_cand
->stride
))
706 derived_base_name
= arg_cand
->base_expr
;
707 arg_stmt
= arg_cand
->cand_stmt
;
708 arg_bb
= gimple_bb (arg_stmt
);
710 /* Gather potential dead code savings if the phi statement
711 can be removed later on. */
712 if (has_single_use (arg
))
714 if (gimple_code (arg_stmt
) == GIMPLE_PHI
)
715 savings
+= arg_cand
->dead_savings
;
717 savings
+= stmt_cost (arg_stmt
, speed
);
722 derived_base_name
= arg
;
724 if (SSA_NAME_IS_DEFAULT_DEF (arg
))
725 arg_bb
= single_succ (ENTRY_BLOCK_PTR
);
727 gimple_bb (SSA_NAME_DEF_STMT (arg
));
730 if (!arg_bb
|| arg_bb
->loop_father
!= cand_loop
)
734 arg0_base
= derived_base_name
;
735 else if (!operand_equal_p (derived_base_name
, arg0_base
, 0))
739 /* Create the candidate. "alloc_cand_and_find_basis" is named
740 misleadingly for this case, as no basis will be sought for a
742 base_type
= TREE_TYPE (arg0_base
);
744 c
= alloc_cand_and_find_basis (CAND_PHI
, phi
, arg0_base
, double_int_zero
,
745 integer_one_node
, base_type
, savings
);
747 /* Add the candidate to the statement-candidate mapping. */
748 add_cand_for_stmt (phi
, c
);
751 /* Look for the following pattern:
753 *PBASE: MEM_REF (T1, C1)
755 *POFFSET: MULT_EXPR (T2, C3) [C2 is zero]
757 MULT_EXPR (PLUS_EXPR (T2, C2), C3)
759 MULT_EXPR (MINUS_EXPR (T2, -C2), C3)
761 *PINDEX: C4 * BITS_PER_UNIT
763 If not present, leave the input values unchanged and return FALSE.
764 Otherwise, modify the input values as follows and return TRUE:
767 *POFFSET: MULT_EXPR (T2, C3)
768 *PINDEX: C1 + (C2 * C3) + C4 */
771 restructure_reference (tree
*pbase
, tree
*poffset
, double_int
*pindex
,
774 tree base
= *pbase
, offset
= *poffset
;
775 double_int index
= *pindex
;
776 double_int bpu
= double_int::from_uhwi (BITS_PER_UNIT
);
777 tree mult_op0
, mult_op1
, t1
, t2
, type
;
778 double_int c1
, c2
, c3
, c4
;
782 || TREE_CODE (base
) != MEM_REF
783 || TREE_CODE (offset
) != MULT_EXPR
784 || TREE_CODE (TREE_OPERAND (offset
, 1)) != INTEGER_CST
785 || !index
.umod (bpu
, FLOOR_MOD_EXPR
).is_zero ())
788 t1
= TREE_OPERAND (base
, 0);
789 c1
= mem_ref_offset (base
);
790 type
= TREE_TYPE (TREE_OPERAND (base
, 1));
792 mult_op0
= TREE_OPERAND (offset
, 0);
793 mult_op1
= TREE_OPERAND (offset
, 1);
795 c3
= tree_to_double_int (mult_op1
);
797 if (TREE_CODE (mult_op0
) == PLUS_EXPR
)
799 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
801 t2
= TREE_OPERAND (mult_op0
, 0);
802 c2
= tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
807 else if (TREE_CODE (mult_op0
) == MINUS_EXPR
)
809 if (TREE_CODE (TREE_OPERAND (mult_op0
, 1)) == INTEGER_CST
)
811 t2
= TREE_OPERAND (mult_op0
, 0);
812 c2
= -tree_to_double_int (TREE_OPERAND (mult_op0
, 1));
820 c2
= double_int_zero
;
823 c4
= index
.udiv (bpu
, FLOOR_DIV_EXPR
);
826 *poffset
= fold_build2 (MULT_EXPR
, sizetype
, t2
,
827 double_int_to_tree (sizetype
, c3
));
828 *pindex
= c1
+ c2
* c3
+ c4
;
834 /* Given GS which contains a data reference, create a CAND_REF entry in
835 the candidate table and attempt to find a basis. */
838 slsr_process_ref (gimple gs
)
840 tree ref_expr
, base
, offset
, type
;
841 HOST_WIDE_INT bitsize
, bitpos
;
842 enum machine_mode mode
;
843 int unsignedp
, volatilep
;
847 if (gimple_vdef (gs
))
848 ref_expr
= gimple_assign_lhs (gs
);
850 ref_expr
= gimple_assign_rhs1 (gs
);
852 if (!handled_component_p (ref_expr
)
853 || TREE_CODE (ref_expr
) == BIT_FIELD_REF
854 || (TREE_CODE (ref_expr
) == COMPONENT_REF
855 && DECL_BIT_FIELD (TREE_OPERAND (ref_expr
, 1))))
858 base
= get_inner_reference (ref_expr
, &bitsize
, &bitpos
, &offset
, &mode
,
859 &unsignedp
, &volatilep
, false);
860 index
= double_int::from_uhwi (bitpos
);
862 if (!restructure_reference (&base
, &offset
, &index
, &type
))
865 c
= alloc_cand_and_find_basis (CAND_REF
, gs
, base
, index
, offset
,
868 /* Add the candidate to the statement-candidate mapping. */
869 add_cand_for_stmt (gs
, c
);
872 /* Create a candidate entry for a statement GS, where GS multiplies
873 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
874 about the two SSA names into the new candidate. Return the new
878 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
880 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
882 unsigned savings
= 0;
884 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
886 /* Look at all interpretations of the base candidate, if necessary,
887 to find information to propagate into this candidate. */
888 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
891 if (base_cand
->kind
== CAND_MULT
&& integer_onep (base_cand
->stride
))
897 base
= base_cand
->base_expr
;
898 index
= base_cand
->index
;
900 ctype
= base_cand
->cand_type
;
901 if (has_single_use (base_in
))
902 savings
= (base_cand
->dead_savings
903 + stmt_cost (base_cand
->cand_stmt
, speed
));
905 else if (base_cand
->kind
== CAND_ADD
906 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
908 /* Y = B + (i' * S), S constant
910 ============================
911 X = B + ((i' * S) * Z) */
912 base
= base_cand
->base_expr
;
913 index
= base_cand
->index
* tree_to_double_int (base_cand
->stride
);
915 ctype
= base_cand
->cand_type
;
916 if (has_single_use (base_in
))
917 savings
= (base_cand
->dead_savings
918 + stmt_cost (base_cand
->cand_stmt
, speed
));
921 if (base_cand
->next_interp
)
922 base_cand
= lookup_cand (base_cand
->next_interp
);
929 /* No interpretations had anything useful to propagate, so
930 produce X = (Y + 0) * Z. */
932 index
= double_int_zero
;
934 ctype
= TREE_TYPE (base_in
);
937 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
942 /* Create a candidate entry for a statement GS, where GS multiplies
943 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
944 information about BASE_IN into the new candidate. Return the new
948 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
950 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
951 double_int index
, temp
;
952 unsigned savings
= 0;
954 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
956 /* Look at all interpretations of the base candidate, if necessary,
957 to find information to propagate into this candidate. */
958 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
960 if (base_cand
->kind
== CAND_MULT
961 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
963 /* Y = (B + i') * S, S constant
965 ============================
966 X = (B + i') * (S * c) */
967 base
= base_cand
->base_expr
;
968 index
= base_cand
->index
;
969 temp
= tree_to_double_int (base_cand
->stride
)
970 * tree_to_double_int (stride_in
);
971 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
972 ctype
= base_cand
->cand_type
;
973 if (has_single_use (base_in
))
974 savings
= (base_cand
->dead_savings
975 + stmt_cost (base_cand
->cand_stmt
, speed
));
977 else if (base_cand
->kind
== CAND_ADD
&& integer_onep (base_cand
->stride
))
981 ===========================
983 base
= base_cand
->base_expr
;
984 index
= base_cand
->index
;
986 ctype
= base_cand
->cand_type
;
987 if (has_single_use (base_in
))
988 savings
= (base_cand
->dead_savings
989 + stmt_cost (base_cand
->cand_stmt
, speed
));
991 else if (base_cand
->kind
== CAND_ADD
992 && base_cand
->index
.is_one ()
993 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
995 /* Y = B + (1 * S), S constant
997 ===========================
999 base
= base_cand
->base_expr
;
1000 index
= tree_to_double_int (base_cand
->stride
);
1002 ctype
= base_cand
->cand_type
;
1003 if (has_single_use (base_in
))
1004 savings
= (base_cand
->dead_savings
1005 + stmt_cost (base_cand
->cand_stmt
, speed
));
1008 if (base_cand
->next_interp
)
1009 base_cand
= lookup_cand (base_cand
->next_interp
);
1016 /* No interpretations had anything useful to propagate, so
1017 produce X = (Y + 0) * c. */
1019 index
= double_int_zero
;
1021 ctype
= TREE_TYPE (base_in
);
1024 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
1029 /* Given GS which is a multiply of scalar integers, make an appropriate
1030 entry in the candidate table. If this is a multiply of two SSA names,
1031 create two CAND_MULT interpretations and attempt to find a basis for
1032 each of them. Otherwise, create a single CAND_MULT and attempt to
1036 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1040 /* If this is a multiply of an SSA name with itself, it is highly
1041 unlikely that we will get a strength reduction opportunity, so
1042 don't record it as a candidate. This simplifies the logic for
1043 finding a basis, so if this is removed that must be considered. */
1047 if (TREE_CODE (rhs2
) == SSA_NAME
)
1049 /* Record an interpretation of this statement in the candidate table
1050 assuming RHS1 is the base expression and RHS2 is the stride. */
1051 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
1053 /* Add the first interpretation to the statement-candidate mapping. */
1054 add_cand_for_stmt (gs
, c
);
1056 /* Record another interpretation of this statement assuming RHS1
1057 is the stride and RHS2 is the base expression. */
1058 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
1059 c
->next_interp
= c2
->cand_num
;
1063 /* Record an interpretation for the multiply-immediate. */
1064 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
1066 /* Add the interpretation to the statement-candidate mapping. */
1067 add_cand_for_stmt (gs
, c
);
1071 /* Create a candidate entry for a statement GS, where GS adds two
1072 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
1073 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
1074 information about the two SSA names into the new candidate.
1075 Return the new candidate. */
1078 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
1079 bool subtract_p
, bool speed
)
1081 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
1083 unsigned savings
= 0;
1085 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1086 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
1088 /* The most useful transformation is a multiply-immediate feeding
1089 an add or subtract. Look for that first. */
1090 while (addend_cand
&& !base
&& addend_cand
->kind
!= CAND_PHI
)
1092 if (addend_cand
->kind
== CAND_MULT
1093 && addend_cand
->index
.is_zero ()
1094 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
1096 /* Z = (B + 0) * S, S constant
1098 ===========================
1099 X = Y + ((+/-1 * S) * B) */
1101 index
= tree_to_double_int (addend_cand
->stride
);
1104 stride
= addend_cand
->base_expr
;
1105 ctype
= TREE_TYPE (base_in
);
1106 if (has_single_use (addend_in
))
1107 savings
= (addend_cand
->dead_savings
1108 + stmt_cost (addend_cand
->cand_stmt
, speed
));
1111 if (addend_cand
->next_interp
)
1112 addend_cand
= lookup_cand (addend_cand
->next_interp
);
1117 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1119 if (base_cand
->kind
== CAND_ADD
1120 && (base_cand
->index
.is_zero ()
1121 || operand_equal_p (base_cand
->stride
,
1122 integer_zero_node
, 0)))
1124 /* Y = B + (i' * S), i' * S = 0
1126 ============================
1127 X = B + (+/-1 * Z) */
1128 base
= base_cand
->base_expr
;
1129 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1131 ctype
= base_cand
->cand_type
;
1132 if (has_single_use (base_in
))
1133 savings
= (base_cand
->dead_savings
1134 + stmt_cost (base_cand
->cand_stmt
, speed
));
1136 else if (subtract_p
)
1138 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
1140 while (subtrahend_cand
&& !base
&& subtrahend_cand
->kind
!= CAND_PHI
)
1142 if (subtrahend_cand
->kind
== CAND_MULT
1143 && subtrahend_cand
->index
.is_zero ()
1144 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
1146 /* Z = (B + 0) * S, S constant
1148 ===========================
1149 Value: X = Y + ((-1 * S) * B) */
1151 index
= tree_to_double_int (subtrahend_cand
->stride
);
1153 stride
= subtrahend_cand
->base_expr
;
1154 ctype
= TREE_TYPE (base_in
);
1155 if (has_single_use (addend_in
))
1156 savings
= (subtrahend_cand
->dead_savings
1157 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
1160 if (subtrahend_cand
->next_interp
)
1161 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
1163 subtrahend_cand
= NULL
;
1167 if (base_cand
->next_interp
)
1168 base_cand
= lookup_cand (base_cand
->next_interp
);
1175 /* No interpretations had anything useful to propagate, so
1176 produce X = Y + (1 * Z). */
1178 index
= subtract_p
? double_int_minus_one
: double_int_one
;
1180 ctype
= TREE_TYPE (base_in
);
1183 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
1188 /* Create a candidate entry for a statement GS, where GS adds SSA
1189 name BASE_IN to constant INDEX_IN. Propagate any known information
1190 about BASE_IN into the new candidate. Return the new candidate. */
1193 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
1195 enum cand_kind kind
= CAND_ADD
;
1196 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
1197 double_int index
, multiple
;
1198 unsigned savings
= 0;
1200 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
1202 while (base_cand
&& !base
&& base_cand
->kind
!= CAND_PHI
)
1204 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
1206 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
1207 && index_in
.multiple_of (tree_to_double_int (base_cand
->stride
),
1208 unsigned_p
, &multiple
))
1210 /* Y = (B + i') * S, S constant, c = kS for some integer k
1212 ============================
1213 X = (B + (i'+ k)) * S
1215 Y = B + (i' * S), S constant, c = kS for some integer k
1217 ============================
1218 X = (B + (i'+ k)) * S */
1219 kind
= base_cand
->kind
;
1220 base
= base_cand
->base_expr
;
1221 index
= base_cand
->index
+ multiple
;
1222 stride
= base_cand
->stride
;
1223 ctype
= base_cand
->cand_type
;
1224 if (has_single_use (base_in
))
1225 savings
= (base_cand
->dead_savings
1226 + stmt_cost (base_cand
->cand_stmt
, speed
));
1229 if (base_cand
->next_interp
)
1230 base_cand
= lookup_cand (base_cand
->next_interp
);
1237 /* No interpretations had anything useful to propagate, so
1238 produce X = Y + (c * 1). */
1242 stride
= integer_one_node
;
1243 ctype
= TREE_TYPE (base_in
);
1246 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
1251 /* Given GS which is an add or subtract of scalar integers or pointers,
1252 make at least one appropriate entry in the candidate table. */
1255 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
1257 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
1258 slsr_cand_t c
= NULL
, c2
;
1260 if (TREE_CODE (rhs2
) == SSA_NAME
)
1262 /* First record an interpretation assuming RHS1 is the base expression
1263 and RHS2 is the stride. But it doesn't make sense for the
1264 stride to be a pointer, so don't record a candidate in that case. */
1265 if (!POINTER_TYPE_P (TREE_TYPE (rhs2
)))
1267 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
1269 /* Add the first interpretation to the statement-candidate
1271 add_cand_for_stmt (gs
, c
);
1274 /* If the two RHS operands are identical, or this is a subtract,
1276 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
1279 /* Otherwise, record another interpretation assuming RHS2 is the
1280 base expression and RHS1 is the stride, again provided that the
1281 stride is not a pointer. */
1282 if (!POINTER_TYPE_P (TREE_TYPE (rhs1
)))
1284 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
1286 c
->next_interp
= c2
->cand_num
;
1288 add_cand_for_stmt (gs
, c2
);
1295 /* Record an interpretation for the add-immediate. */
1296 index
= tree_to_double_int (rhs2
);
1300 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
1302 /* Add the interpretation to the statement-candidate mapping. */
1303 add_cand_for_stmt (gs
, c
);
1307 /* Given GS which is a negate of a scalar integer, make an appropriate
1308 entry in the candidate table. A negate is equivalent to a multiply
1312 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
1314 /* Record a CAND_MULT interpretation for the multiply by -1. */
1315 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
1317 /* Add the interpretation to the statement-candidate mapping. */
1318 add_cand_for_stmt (gs
, c
);
1321 /* Help function for legal_cast_p, operating on two trees. Checks
1322 whether it's allowable to cast from RHS to LHS. See legal_cast_p
1323 for more details. */
1326 legal_cast_p_1 (tree lhs
, tree rhs
)
1328 tree lhs_type
, rhs_type
;
1329 unsigned lhs_size
, rhs_size
;
1330 bool lhs_wraps
, rhs_wraps
;
1332 lhs_type
= TREE_TYPE (lhs
);
1333 rhs_type
= TREE_TYPE (rhs
);
1334 lhs_size
= TYPE_PRECISION (lhs_type
);
1335 rhs_size
= TYPE_PRECISION (rhs_type
);
1336 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
1337 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
1339 if (lhs_size
< rhs_size
1340 || (rhs_wraps
&& !lhs_wraps
)
1341 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
1347 /* Return TRUE if GS is a statement that defines an SSA name from
1348 a conversion and is legal for us to combine with an add and multiply
1349 in the candidate table. For example, suppose we have:
1355 Without the type-cast, we would create a CAND_MULT for D with base B,
1356 index i, and stride S. We want to record this candidate only if it
1357 is equivalent to apply the type cast following the multiply:
1363 We will record the type with the candidate for D. This allows us
1364 to use a similar previous candidate as a basis. If we have earlier seen
1370 we can replace D with
1372 D = D' + (i - i') * S;
1374 But if moving the type-cast would change semantics, we mustn't do this.
1376 This is legitimate for casts from a non-wrapping integral type to
1377 any integral type of the same or larger size. It is not legitimate
1378 to convert a wrapping type to a non-wrapping type, or to a wrapping
1379 type of a different size. I.e., with a wrapping type, we must
1380 assume that the addition B + i could wrap, in which case performing
1381 the multiply before or after one of the "illegal" type casts will
1382 have different semantics. */
1385 legal_cast_p (gimple gs
, tree rhs
)
1387 if (!is_gimple_assign (gs
)
1388 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
1391 return legal_cast_p_1 (gimple_assign_lhs (gs
), rhs
);
1394 /* Given GS which is a cast to a scalar integer type, determine whether
1395 the cast is legal for strength reduction. If so, make at least one
1396 appropriate entry in the candidate table. */
1399 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
1402 slsr_cand_t base_cand
, c
, c2
;
1403 unsigned savings
= 0;
1405 if (!legal_cast_p (gs
, rhs1
))
1408 lhs
= gimple_assign_lhs (gs
);
1409 base_cand
= base_cand_from_table (rhs1
);
1410 ctype
= TREE_TYPE (lhs
);
1412 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1416 /* Propagate all data from the base candidate except the type,
1417 which comes from the cast, and the base candidate's cast,
1418 which is no longer applicable. */
1419 if (has_single_use (rhs1
))
1420 savings
= (base_cand
->dead_savings
1421 + stmt_cost (base_cand
->cand_stmt
, speed
));
1423 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1424 base_cand
->base_expr
,
1425 base_cand
->index
, base_cand
->stride
,
1427 if (base_cand
->next_interp
)
1428 base_cand
= lookup_cand (base_cand
->next_interp
);
1435 /* If nothing is known about the RHS, create fresh CAND_ADD and
1436 CAND_MULT interpretations:
1441 The first of these is somewhat arbitrary, but the choice of
1442 1 for the stride simplifies the logic for propagating casts
1444 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1445 integer_one_node
, ctype
, 0);
1446 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1447 integer_one_node
, ctype
, 0);
1448 c
->next_interp
= c2
->cand_num
;
1451 /* Add the first (or only) interpretation to the statement-candidate
1453 add_cand_for_stmt (gs
, c
);
1456 /* Given GS which is a copy of a scalar integer type, make at least one
1457 appropriate entry in the candidate table.
1459 This interface is included for completeness, but is unnecessary
1460 if this pass immediately follows a pass that performs copy
1461 propagation, such as DOM. */
1464 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
1466 slsr_cand_t base_cand
, c
, c2
;
1467 unsigned savings
= 0;
1469 base_cand
= base_cand_from_table (rhs1
);
1471 if (base_cand
&& base_cand
->kind
!= CAND_PHI
)
1475 /* Propagate all data from the base candidate. */
1476 if (has_single_use (rhs1
))
1477 savings
= (base_cand
->dead_savings
1478 + stmt_cost (base_cand
->cand_stmt
, speed
));
1480 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1481 base_cand
->base_expr
,
1482 base_cand
->index
, base_cand
->stride
,
1483 base_cand
->cand_type
, savings
);
1484 if (base_cand
->next_interp
)
1485 base_cand
= lookup_cand (base_cand
->next_interp
);
1492 /* If nothing is known about the RHS, create fresh CAND_ADD and
1493 CAND_MULT interpretations:
1498 The first of these is somewhat arbitrary, but the choice of
1499 1 for the stride simplifies the logic for propagating casts
1501 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1502 integer_one_node
, TREE_TYPE (rhs1
), 0);
1503 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1504 integer_one_node
, TREE_TYPE (rhs1
), 0);
1505 c
->next_interp
= c2
->cand_num
;
1508 /* Add the first (or only) interpretation to the statement-candidate
1510 add_cand_for_stmt (gs
, c
);
1513 /* Find strength-reduction candidates in block BB. */
1516 find_candidates_in_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1519 bool speed
= optimize_bb_for_speed_p (bb
);
1520 gimple_stmt_iterator gsi
;
1522 for (gsi
= gsi_start_phis (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1523 slsr_process_phi (gsi_stmt (gsi
), speed
);
1525 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1527 gimple gs
= gsi_stmt (gsi
);
1529 if (gimple_vuse (gs
) && gimple_assign_single_p (gs
))
1530 slsr_process_ref (gs
);
1532 else if (is_gimple_assign (gs
)
1533 && SCALAR_INT_MODE_P
1534 (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1536 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1538 switch (gimple_assign_rhs_code (gs
))
1542 rhs1
= gimple_assign_rhs1 (gs
);
1543 rhs2
= gimple_assign_rhs2 (gs
);
1544 /* Should never happen, but currently some buggy situations
1545 in earlier phases put constants in rhs1. */
1546 if (TREE_CODE (rhs1
) != SSA_NAME
)
1550 /* Possible future opportunity: rhs1 of a ptr+ can be
1552 case POINTER_PLUS_EXPR
:
1554 rhs2
= gimple_assign_rhs2 (gs
);
1560 rhs1
= gimple_assign_rhs1 (gs
);
1561 if (TREE_CODE (rhs1
) != SSA_NAME
)
1569 switch (gimple_assign_rhs_code (gs
))
1572 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1576 case POINTER_PLUS_EXPR
:
1578 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1582 slsr_process_neg (gs
, rhs1
, speed
);
1586 slsr_process_cast (gs
, rhs1
, speed
);
1590 slsr_process_copy (gs
, rhs1
, speed
);
1600 /* Dump a candidate for debug. */
1603 dump_candidate (slsr_cand_t c
)
1605 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1606 gimple_bb (c
->cand_stmt
)->index
);
1607 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1611 fputs (" MULT : (", dump_file
);
1612 print_generic_expr (dump_file
, c
->base_expr
, 0);
1613 fputs (" + ", dump_file
);
1614 dump_double_int (dump_file
, c
->index
, false);
1615 fputs (") * ", dump_file
);
1616 print_generic_expr (dump_file
, c
->stride
, 0);
1617 fputs (" : ", dump_file
);
1620 fputs (" ADD : ", dump_file
);
1621 print_generic_expr (dump_file
, c
->base_expr
, 0);
1622 fputs (" + (", dump_file
);
1623 dump_double_int (dump_file
, c
->index
, false);
1624 fputs (" * ", dump_file
);
1625 print_generic_expr (dump_file
, c
->stride
, 0);
1626 fputs (") : ", dump_file
);
1629 fputs (" REF : ", dump_file
);
1630 print_generic_expr (dump_file
, c
->base_expr
, 0);
1631 fputs (" + (", dump_file
);
1632 print_generic_expr (dump_file
, c
->stride
, 0);
1633 fputs (") + ", dump_file
);
1634 dump_double_int (dump_file
, c
->index
, false);
1635 fputs (" : ", dump_file
);
1638 fputs (" PHI : ", dump_file
);
1639 print_generic_expr (dump_file
, c
->base_expr
, 0);
1640 fputs (" + (unknown * ", dump_file
);
1641 print_generic_expr (dump_file
, c
->stride
, 0);
1642 fputs (") : ", dump_file
);
1647 print_generic_expr (dump_file
, c
->cand_type
, 0);
1648 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1649 c
->basis
, c
->dependent
, c
->sibling
);
1650 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1651 c
->next_interp
, c
->dead_savings
);
1653 fprintf (dump_file
, " phi: %d\n", c
->def_phi
);
1654 fputs ("\n", dump_file
);
1657 /* Dump the candidate vector for debug. */
1660 dump_cand_vec (void)
1665 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1667 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
1671 /* Callback used to dump the candidate chains hash table. */
1674 ssa_base_cand_dump_callback (cand_chain
**slot
, void *ignored ATTRIBUTE_UNUSED
)
1676 const_cand_chain_t chain
= *slot
;
1679 print_generic_expr (dump_file
, chain
->base_expr
, 0);
1680 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1682 for (p
= chain
->next
; p
; p
= p
->next
)
1683 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1685 fputs ("\n", dump_file
);
1689 /* Dump the candidate chains. */
1692 dump_cand_chains (void)
1694 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1695 base_cand_map
.traverse_noresize
<void *, ssa_base_cand_dump_callback
> (NULL
);
1696 fputs ("\n", dump_file
);
1699 /* Dump the increment vector for debug. */
1702 dump_incr_vec (void)
1704 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1708 fprintf (dump_file
, "\nIncrement vector:\n\n");
1710 for (i
= 0; i
< incr_vec_len
; i
++)
1712 fprintf (dump_file
, "%3d increment: ", i
);
1713 dump_double_int (dump_file
, incr_vec
[i
].incr
, false);
1714 fprintf (dump_file
, "\n count: %d", incr_vec
[i
].count
);
1715 fprintf (dump_file
, "\n cost: %d", incr_vec
[i
].cost
);
1716 fputs ("\n initializer: ", dump_file
);
1717 print_generic_expr (dump_file
, incr_vec
[i
].initializer
, 0);
1718 fputs ("\n\n", dump_file
);
1723 /* Replace *EXPR in candidate C with an equivalent strength-reduced
1727 replace_ref (tree
*expr
, slsr_cand_t c
)
1729 tree add_expr
= fold_build2 (POINTER_PLUS_EXPR
, TREE_TYPE (c
->base_expr
),
1730 c
->base_expr
, c
->stride
);
1731 tree mem_ref
= fold_build2 (MEM_REF
, TREE_TYPE (*expr
), add_expr
,
1732 double_int_to_tree (c
->cand_type
, c
->index
));
1734 /* Gimplify the base addressing expression for the new MEM_REF tree. */
1735 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1736 TREE_OPERAND (mem_ref
, 0)
1737 = force_gimple_operand_gsi (&gsi
, TREE_OPERAND (mem_ref
, 0),
1738 /*simple_p=*/true, NULL
,
1739 /*before=*/true, GSI_SAME_STMT
);
1740 copy_ref_info (mem_ref
, *expr
);
1742 update_stmt (c
->cand_stmt
);
1745 /* Replace CAND_REF candidate C, each sibling of candidate C, and each
1746 dependent of candidate C with an equivalent strength-reduced data
1750 replace_refs (slsr_cand_t c
)
1752 if (gimple_vdef (c
->cand_stmt
))
1754 tree
*lhs
= gimple_assign_lhs_ptr (c
->cand_stmt
);
1755 replace_ref (lhs
, c
);
1759 tree
*rhs
= gimple_assign_rhs1_ptr (c
->cand_stmt
);
1760 replace_ref (rhs
, c
);
1764 replace_refs (lookup_cand (c
->sibling
));
1767 replace_refs (lookup_cand (c
->dependent
));
1770 /* Return TRUE if candidate C is dependent upon a PHI. */
1773 phi_dependent_cand_p (slsr_cand_t c
)
1775 /* A candidate is not necessarily dependent upon a PHI just because
1776 it has a phi definition for its base name. It may have a basis
1777 that relies upon the same phi definition, in which case the PHI
1778 is irrelevant to this candidate. */
1781 && lookup_cand (c
->basis
)->def_phi
!= c
->def_phi
);
1784 /* Calculate the increment required for candidate C relative to
1788 cand_increment (slsr_cand_t c
)
1792 /* If the candidate doesn't have a basis, just return its own
1793 index. This is useful in record_increments to help us find
1794 an existing initializer. Also, if the candidate's basis is
1795 hidden by a phi, then its own index will be the increment
1796 from the newly introduced phi basis. */
1797 if (!c
->basis
|| phi_dependent_cand_p (c
))
1800 basis
= lookup_cand (c
->basis
);
1801 gcc_assert (operand_equal_p (c
->base_expr
, basis
->base_expr
, 0));
1802 return c
->index
- basis
->index
;
1805 /* Calculate the increment required for candidate C relative to
1806 its basis. If we aren't going to generate pointer arithmetic
1807 for this candidate, return the absolute value of that increment
1810 static inline double_int
1811 cand_abs_increment (slsr_cand_t c
)
1813 double_int increment
= cand_increment (c
);
1815 if (!address_arithmetic_p
&& increment
.is_negative ())
1816 increment
= -increment
;
1821 /* If *VAR is NULL or is not of a compatible type with TYPE, create a
1822 new temporary reg of type TYPE and store it in *VAR. */
1825 lazy_create_slsr_reg (tree
*var
, tree type
)
1827 if (!*var
|| !types_compatible_p (TREE_TYPE (*var
), type
))
1828 *var
= create_tmp_reg (type
, "slsr");
1831 /* Return TRUE iff candidate C has already been replaced under
1832 another interpretation. */
1835 cand_already_replaced (slsr_cand_t c
)
1837 return (gimple_bb (c
->cand_stmt
) == 0);
1840 /* Common logic used by replace_unconditional_candidate and
1841 replace_conditional_candidate. */
1844 replace_mult_candidate (slsr_cand_t c
, tree basis_name
, double_int bump
,
1847 tree target_type
= TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
));
1848 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1850 /* It is highly unlikely, but possible, that the resulting
1851 bump doesn't fit in a HWI. Abandon the replacement
1852 in this case. This does not affect siblings or dependents
1853 of C. Restriction to signed HWI is conservative for unsigned
1854 types but allows for safe negation without twisted logic. */
1855 if (bump
.fits_shwi ()
1856 && bump
.to_shwi () != HOST_WIDE_INT_MIN
1857 /* It is not useful to replace casts, copies, or adds of
1858 an SSA name and a constant. */
1859 && cand_code
!= MODIFY_EXPR
1860 && cand_code
!= NOP_EXPR
1861 && cand_code
!= PLUS_EXPR
1862 && cand_code
!= POINTER_PLUS_EXPR
1863 && cand_code
!= MINUS_EXPR
)
1865 enum tree_code code
= PLUS_EXPR
;
1867 gimple stmt_to_print
= NULL
;
1869 /* If the basis name and the candidate's LHS have incompatible
1870 types, introduce a cast. */
1871 if (!useless_type_conversion_p (target_type
, TREE_TYPE (basis_name
)))
1872 basis_name
= introduce_cast_before_cand (c
, target_type
,
1874 if (bump
.is_negative ())
1880 bump_tree
= double_int_to_tree (target_type
, bump
);
1882 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1884 fputs ("Replacing: ", dump_file
);
1885 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1888 if (bump
.is_zero ())
1890 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1891 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1892 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1893 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1894 gsi_replace (&gsi
, copy_stmt
, false);
1895 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1896 stmt_to_print
= copy_stmt
;
1901 if (cand_code
!= NEGATE_EXPR
) {
1902 rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1903 rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1905 if (cand_code
!= NEGATE_EXPR
1906 && ((operand_equal_p (rhs1
, basis_name
, 0)
1907 && operand_equal_p (rhs2
, bump_tree
, 0))
1908 || (operand_equal_p (rhs1
, bump_tree
, 0)
1909 && operand_equal_p (rhs2
, basis_name
, 0))))
1911 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1913 fputs ("(duplicate, not actually replacing)", dump_file
);
1914 stmt_to_print
= c
->cand_stmt
;
1919 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1920 gimple_assign_set_rhs_with_ops (&gsi
, code
,
1921 basis_name
, bump_tree
);
1922 update_stmt (gsi_stmt (gsi
));
1923 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1924 stmt_to_print
= gsi_stmt (gsi
);
1928 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1930 fputs ("With: ", dump_file
);
1931 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
1932 fputs ("\n", dump_file
);
1937 /* Replace candidate C with an add or subtract. Note that we only
1938 operate on CAND_MULTs with known strides, so we will never generate
1939 a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is replaced by
1940 X = Y + ((i - i') * S), as described in the module commentary. The
1941 folded value ((i - i') * S) is referred to here as the "bump." */
1944 replace_unconditional_candidate (slsr_cand_t c
)
1947 double_int stride
, bump
;
1950 if (cand_already_replaced (c
))
1953 basis
= lookup_cand (c
->basis
);
1954 stride
= tree_to_double_int (c
->stride
);
1955 bump
= cand_increment (c
) * stride
;
1957 replace_mult_candidate (c
, gimple_assign_lhs (basis
->cand_stmt
), bump
, &var
);
1960 /* Return the index in the increment vector of the given INCREMENT. */
1962 static inline unsigned
1963 incr_vec_index (double_int increment
)
1967 for (i
= 0; i
< incr_vec_len
&& increment
!= incr_vec
[i
].incr
; i
++)
1970 gcc_assert (i
< incr_vec_len
);
1974 /* Create a new statement along edge E to add BASIS_NAME to the product
1975 of INCREMENT and the stride of candidate C. Create and return a new
1976 SSA name from *VAR to be used as the LHS of the new statement.
1977 KNOWN_STRIDE is true iff C's stride is a constant. */
1980 create_add_on_incoming_edge (slsr_cand_t c
, tree basis_name
,
1981 double_int increment
, edge e
, location_t loc
,
1984 basic_block insert_bb
;
1985 gimple_stmt_iterator gsi
;
1986 tree lhs
, basis_type
;
1989 /* If the add candidate along this incoming edge has the same
1990 index as C's hidden basis, the hidden basis represents this
1992 if (increment
.is_zero ())
1995 basis_type
= TREE_TYPE (basis_name
);
1996 lhs
= make_temp_ssa_name (basis_type
, NULL
, "slsr");
2001 enum tree_code code
= PLUS_EXPR
;
2002 double_int bump
= increment
* tree_to_double_int (c
->stride
);
2003 if (bump
.is_negative ())
2009 bump_tree
= double_int_to_tree (basis_type
, bump
);
2010 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2016 bool negate_incr
= (!address_arithmetic_p
&& increment
.is_negative ());
2017 i
= incr_vec_index (negate_incr
? -increment
: increment
);
2019 if (incr_vec
[i
].initializer
)
2021 enum tree_code code
= negate_incr
? MINUS_EXPR
: PLUS_EXPR
;
2022 new_stmt
= gimple_build_assign_with_ops (code
, lhs
, basis_name
,
2023 incr_vec
[i
].initializer
);
2025 else if (increment
.is_one ())
2026 new_stmt
= gimple_build_assign_with_ops (PLUS_EXPR
, lhs
, basis_name
,
2028 else if (increment
.is_minus_one ())
2029 new_stmt
= gimple_build_assign_with_ops (MINUS_EXPR
, lhs
, basis_name
,
2035 insert_bb
= single_succ_p (e
->src
) ? e
->src
: split_edge (e
);
2036 gsi
= gsi_last_bb (insert_bb
);
2038 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2039 gsi_insert_before (&gsi
, new_stmt
, GSI_NEW_STMT
);
2041 gsi_insert_after (&gsi
, new_stmt
, GSI_NEW_STMT
);
2043 gimple_set_location (new_stmt
, loc
);
2045 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2047 fprintf (dump_file
, "Inserting in block %d: ", insert_bb
->index
);
2048 print_gimple_stmt (dump_file
, new_stmt
, 0, 0);
2054 /* Given a candidate C with BASIS_NAME being the LHS of C's basis which
2055 is hidden by the phi node FROM_PHI, create a new phi node in the same
2056 block as FROM_PHI. The new phi is suitable for use as a basis by C,
2057 with its phi arguments representing conditional adjustments to the
2058 hidden basis along conditional incoming paths. Those adjustments are
2059 made by creating add statements (and sometimes recursively creating
2060 phis) along those incoming paths. LOC is the location to attach to
2061 the introduced statements. KNOWN_STRIDE is true iff C's stride is a
2065 create_phi_basis (slsr_cand_t c
, gimple from_phi
, tree basis_name
,
2066 location_t loc
, bool known_stride
)
2072 slsr_cand_t basis
= lookup_cand (c
->basis
);
2073 int nargs
= gimple_phi_num_args (from_phi
);
2074 basic_block phi_bb
= gimple_bb (from_phi
);
2075 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (from_phi
));
2076 phi_args
.create (nargs
);
2078 /* Process each argument of the existing phi that represents
2079 conditionally-executed add candidates. */
2080 for (i
= 0; i
< nargs
; i
++)
2082 edge e
= (*phi_bb
->preds
)[i
];
2083 tree arg
= gimple_phi_arg_def (from_phi
, i
);
2086 /* If the phi argument is the base name of the CAND_PHI, then
2087 this incoming arc should use the hidden basis. */
2088 if (operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2089 if (basis
->index
.is_zero ())
2090 feeding_def
= gimple_assign_lhs (basis
->cand_stmt
);
2093 double_int incr
= -basis
->index
;
2094 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, incr
,
2095 e
, loc
, known_stride
);
2099 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2101 /* If there is another phi along this incoming edge, we must
2102 process it in the same fashion to ensure that all basis
2103 adjustments are made along its incoming edges. */
2104 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2105 feeding_def
= create_phi_basis (c
, arg_def
, basis_name
,
2109 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2110 double_int diff
= arg_cand
->index
- basis
->index
;
2111 feeding_def
= create_add_on_incoming_edge (c
, basis_name
, diff
,
2112 e
, loc
, known_stride
);
2116 /* Because of recursion, we need to save the arguments in a vector
2117 so we can create the PHI statement all at once. Otherwise the
2118 storage for the half-created PHI can be reclaimed. */
2119 phi_args
.safe_push (feeding_def
);
2122 /* Create the new phi basis. */
2123 name
= make_temp_ssa_name (TREE_TYPE (basis_name
), NULL
, "slsr");
2124 phi
= create_phi_node (name
, phi_bb
);
2125 SSA_NAME_DEF_STMT (name
) = phi
;
2127 FOR_EACH_VEC_ELT (phi_args
, i
, phi_arg
)
2129 edge e
= (*phi_bb
->preds
)[i
];
2130 add_phi_arg (phi
, phi_arg
, e
, loc
);
2135 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2137 fputs ("Introducing new phi basis: ", dump_file
);
2138 print_gimple_stmt (dump_file
, phi
, 0, 0);
2144 /* Given a candidate C whose basis is hidden by at least one intervening
2145 phi, introduce a matching number of new phis to represent its basis
2146 adjusted by conditional increments along possible incoming paths. Then
2147 replace C as though it were an unconditional candidate, using the new
2151 replace_conditional_candidate (slsr_cand_t c
)
2153 tree basis_name
, name
, var
= NULL
;
2156 double_int stride
, bump
;
2158 /* Look up the LHS SSA name from C's basis. This will be the
2159 RHS1 of the adds we will introduce to create new phi arguments. */
2160 basis
= lookup_cand (c
->basis
);
2161 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
2163 /* Create a new phi statement which will represent C's true basis
2164 after the transformation is complete. */
2165 loc
= gimple_location (c
->cand_stmt
);
2166 name
= create_phi_basis (c
, lookup_cand (c
->def_phi
)->cand_stmt
,
2167 basis_name
, loc
, KNOWN_STRIDE
);
2168 /* Replace C with an add of the new basis phi and a constant. */
2169 stride
= tree_to_double_int (c
->stride
);
2170 bump
= c
->index
* stride
;
2172 replace_mult_candidate (c
, name
, bump
, &var
);
2175 /* Compute the expected costs of inserting basis adjustments for
2176 candidate C with phi-definition PHI. The cost of inserting
2177 one adjustment is given by ONE_ADD_COST. If PHI has arguments
2178 which are themselves phi results, recursively calculate costs
2179 for those phis as well. */
2182 phi_add_costs (gimple phi
, slsr_cand_t c
, int one_add_cost
)
2186 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2188 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2190 tree arg
= gimple_phi_arg_def (phi
, i
);
2192 if (arg
!= phi_cand
->base_expr
)
2194 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2196 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2197 cost
+= phi_add_costs (arg_def
, c
, one_add_cost
);
2200 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2202 if (arg_cand
->index
!= c
->index
)
2203 cost
+= one_add_cost
;
2211 /* For candidate C, each sibling of candidate C, and each dependent of
2212 candidate C, determine whether the candidate is dependent upon a
2213 phi that hides its basis. If not, replace the candidate unconditionally.
2214 Otherwise, determine whether the cost of introducing compensation code
2215 for the candidate is offset by the gains from strength reduction. If
2216 so, replace the candidate and introduce the compensation code. */
2219 replace_uncond_cands_and_profitable_phis (slsr_cand_t c
)
2221 if (phi_dependent_cand_p (c
))
2223 if (c
->kind
== CAND_MULT
)
2225 /* A candidate dependent upon a phi will replace a multiply by
2226 a constant with an add, and will insert at most one add for
2227 each phi argument. Add these costs with the potential dead-code
2228 savings to determine profitability. */
2229 bool speed
= optimize_bb_for_speed_p (gimple_bb (c
->cand_stmt
));
2230 int mult_savings
= stmt_cost (c
->cand_stmt
, speed
);
2231 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2232 tree phi_result
= gimple_phi_result (phi
);
2233 int one_add_cost
= add_cost (speed
,
2234 TYPE_MODE (TREE_TYPE (phi_result
)));
2235 int add_costs
= one_add_cost
+ phi_add_costs (phi
, c
, one_add_cost
);
2236 int cost
= add_costs
- mult_savings
- c
->dead_savings
;
2238 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2240 fprintf (dump_file
, " Conditional candidate %d:\n", c
->cand_num
);
2241 fprintf (dump_file
, " add_costs = %d\n", add_costs
);
2242 fprintf (dump_file
, " mult_savings = %d\n", mult_savings
);
2243 fprintf (dump_file
, " dead_savings = %d\n", c
->dead_savings
);
2244 fprintf (dump_file
, " cost = %d\n", cost
);
2245 if (cost
<= COST_NEUTRAL
)
2246 fputs (" Replacing...\n", dump_file
);
2248 fputs (" Not replaced.\n", dump_file
);
2251 if (cost
<= COST_NEUTRAL
)
2252 replace_conditional_candidate (c
);
2256 replace_unconditional_candidate (c
);
2259 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->sibling
));
2262 replace_uncond_cands_and_profitable_phis (lookup_cand (c
->dependent
));
2265 /* Count the number of candidates in the tree rooted at C that have
2266 not already been replaced under other interpretations. */
2269 count_candidates (slsr_cand_t c
)
2271 unsigned count
= cand_already_replaced (c
) ? 0 : 1;
2274 count
+= count_candidates (lookup_cand (c
->sibling
));
2277 count
+= count_candidates (lookup_cand (c
->dependent
));
2282 /* Increase the count of INCREMENT by one in the increment vector.
2283 INCREMENT is associated with candidate C. If INCREMENT is to be
2284 conditionally executed as part of a conditional candidate replacement,
2285 IS_PHI_ADJUST is true, otherwise false. If an initializer
2286 T_0 = stride * I is provided by a candidate that dominates all
2287 candidates with the same increment, also record T_0 for subsequent use. */
2290 record_increment (slsr_cand_t c
, double_int increment
, bool is_phi_adjust
)
2295 /* Treat increments that differ only in sign as identical so as to
2296 share initializers, unless we are generating pointer arithmetic. */
2297 if (!address_arithmetic_p
&& increment
.is_negative ())
2298 increment
= -increment
;
2300 for (i
= 0; i
< incr_vec_len
; i
++)
2302 if (incr_vec
[i
].incr
== increment
)
2304 incr_vec
[i
].count
++;
2307 /* If we previously recorded an initializer that doesn't
2308 dominate this candidate, it's not going to be useful to
2310 if (incr_vec
[i
].initializer
2311 && !dominated_by_p (CDI_DOMINATORS
,
2312 gimple_bb (c
->cand_stmt
),
2313 incr_vec
[i
].init_bb
))
2315 incr_vec
[i
].initializer
= NULL_TREE
;
2316 incr_vec
[i
].init_bb
= NULL
;
2325 /* The first time we see an increment, create the entry for it.
2326 If this is the root candidate which doesn't have a basis, set
2327 the count to zero. We're only processing it so it can possibly
2328 provide an initializer for other candidates. */
2329 incr_vec
[incr_vec_len
].incr
= increment
;
2330 incr_vec
[incr_vec_len
].count
= c
->basis
|| is_phi_adjust
? 1 : 0;
2331 incr_vec
[incr_vec_len
].cost
= COST_INFINITE
;
2333 /* Optimistically record the first occurrence of this increment
2334 as providing an initializer (if it does); we will revise this
2335 opinion later if it doesn't dominate all other occurrences.
2336 Exception: increments of -1, 0, 1 never need initializers;
2337 and phi adjustments don't ever provide initializers. */
2338 if (c
->kind
== CAND_ADD
2340 && c
->index
== increment
2341 && (increment
.sgt (double_int_one
)
2342 || increment
.slt (double_int_minus_one
))
2343 && (gimple_assign_rhs_code (c
->cand_stmt
) == PLUS_EXPR
2344 || gimple_assign_rhs_code (c
->cand_stmt
) == POINTER_PLUS_EXPR
))
2346 tree t0
= NULL_TREE
;
2347 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
2348 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
2349 if (operand_equal_p (rhs1
, c
->base_expr
, 0))
2351 else if (operand_equal_p (rhs2
, c
->base_expr
, 0))
2354 && SSA_NAME_DEF_STMT (t0
)
2355 && gimple_bb (SSA_NAME_DEF_STMT (t0
)))
2357 incr_vec
[incr_vec_len
].initializer
= t0
;
2358 incr_vec
[incr_vec_len
++].init_bb
2359 = gimple_bb (SSA_NAME_DEF_STMT (t0
));
2363 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2364 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2369 incr_vec
[incr_vec_len
].initializer
= NULL_TREE
;
2370 incr_vec
[incr_vec_len
++].init_bb
= NULL
;
2375 /* Given phi statement PHI that hides a candidate from its BASIS, find
2376 the increments along each incoming arc (recursively handling additional
2377 phis that may be present) and record them. These increments are the
2378 difference in index between the index-adjusting statements and the
2379 index of the basis. */
2382 record_phi_increments (slsr_cand_t basis
, gimple phi
)
2385 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2387 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2389 tree arg
= gimple_phi_arg_def (phi
, i
);
2391 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2393 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2395 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2396 record_phi_increments (basis
, arg_def
);
2399 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2400 double_int diff
= arg_cand
->index
- basis
->index
;
2401 record_increment (arg_cand
, diff
, PHI_ADJUST
);
2407 /* Determine how many times each unique increment occurs in the set
2408 of candidates rooted at C's parent, recording the data in the
2409 increment vector. For each unique increment I, if an initializer
2410 T_0 = stride * I is provided by a candidate that dominates all
2411 candidates with the same increment, also record T_0 for subsequent
2415 record_increments (slsr_cand_t c
)
2417 if (!cand_already_replaced (c
))
2419 if (!phi_dependent_cand_p (c
))
2420 record_increment (c
, cand_increment (c
), NOT_PHI_ADJUST
);
2423 /* A candidate with a basis hidden by a phi will have one
2424 increment for its relationship to the index represented by
2425 the phi, and potentially additional increments along each
2426 incoming edge. For the root of the dependency tree (which
2427 has no basis), process just the initial index in case it has
2428 an initializer that can be used by subsequent candidates. */
2429 record_increment (c
, c
->index
, NOT_PHI_ADJUST
);
2432 record_phi_increments (lookup_cand (c
->basis
),
2433 lookup_cand (c
->def_phi
)->cand_stmt
);
2438 record_increments (lookup_cand (c
->sibling
));
2441 record_increments (lookup_cand (c
->dependent
));
2444 /* Add up and return the costs of introducing add statements that
2445 require the increment INCR on behalf of candidate C and phi
2446 statement PHI. Accumulate into *SAVINGS the potential savings
2447 from removing existing statements that feed PHI and have no other
2451 phi_incr_cost (slsr_cand_t c
, double_int incr
, gimple phi
, int *savings
)
2455 slsr_cand_t basis
= lookup_cand (c
->basis
);
2456 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2458 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2460 tree arg
= gimple_phi_arg_def (phi
, i
);
2462 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2464 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2466 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2468 int feeding_savings
= 0;
2469 cost
+= phi_incr_cost (c
, incr
, arg_def
, &feeding_savings
);
2470 if (has_single_use (gimple_phi_result (arg_def
)))
2471 *savings
+= feeding_savings
;
2475 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2476 double_int diff
= arg_cand
->index
- basis
->index
;
2480 tree basis_lhs
= gimple_assign_lhs (basis
->cand_stmt
);
2481 tree lhs
= gimple_assign_lhs (arg_cand
->cand_stmt
);
2482 cost
+= add_cost (true, TYPE_MODE (TREE_TYPE (basis_lhs
)));
2483 if (has_single_use (lhs
))
2484 *savings
+= stmt_cost (arg_cand
->cand_stmt
, true);
2493 /* Return the first candidate in the tree rooted at C that has not
2494 already been replaced, favoring siblings over dependents. */
2497 unreplaced_cand_in_tree (slsr_cand_t c
)
2499 if (!cand_already_replaced (c
))
2504 slsr_cand_t sib
= unreplaced_cand_in_tree (lookup_cand (c
->sibling
));
2511 slsr_cand_t dep
= unreplaced_cand_in_tree (lookup_cand (c
->dependent
));
2519 /* Return TRUE if the candidates in the tree rooted at C should be
2520 optimized for speed, else FALSE. We estimate this based on the block
2521 containing the most dominant candidate in the tree that has not yet
2525 optimize_cands_for_speed_p (slsr_cand_t c
)
2527 slsr_cand_t c2
= unreplaced_cand_in_tree (c
);
2529 return optimize_bb_for_speed_p (gimple_bb (c2
->cand_stmt
));
2532 /* Add COST_IN to the lowest cost of any dependent path starting at
2533 candidate C or any of its siblings, counting only candidates along
2534 such paths with increment INCR. Assume that replacing a candidate
2535 reduces cost by REPL_SAVINGS. Also account for savings from any
2536 statements that would go dead. If COUNT_PHIS is true, include
2537 costs of introducing feeding statements for conditional candidates. */
2540 lowest_cost_path (int cost_in
, int repl_savings
, slsr_cand_t c
,
2541 double_int incr
, bool count_phis
)
2543 int local_cost
, sib_cost
, savings
= 0;
2544 double_int cand_incr
= cand_abs_increment (c
);
2546 if (cand_already_replaced (c
))
2547 local_cost
= cost_in
;
2548 else if (incr
== cand_incr
)
2549 local_cost
= cost_in
- repl_savings
- c
->dead_savings
;
2551 local_cost
= cost_in
- c
->dead_savings
;
2554 && phi_dependent_cand_p (c
)
2555 && !cand_already_replaced (c
))
2557 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2558 local_cost
+= phi_incr_cost (c
, incr
, phi
, &savings
);
2560 if (has_single_use (gimple_phi_result (phi
)))
2561 local_cost
-= savings
;
2565 local_cost
= lowest_cost_path (local_cost
, repl_savings
,
2566 lookup_cand (c
->dependent
), incr
,
2571 sib_cost
= lowest_cost_path (cost_in
, repl_savings
,
2572 lookup_cand (c
->sibling
), incr
,
2574 local_cost
= MIN (local_cost
, sib_cost
);
2580 /* Compute the total savings that would accrue from all replacements
2581 in the candidate tree rooted at C, counting only candidates with
2582 increment INCR. Assume that replacing a candidate reduces cost
2583 by REPL_SAVINGS. Also account for savings from statements that
2587 total_savings (int repl_savings
, slsr_cand_t c
, double_int incr
,
2591 double_int cand_incr
= cand_abs_increment (c
);
2593 if (incr
== cand_incr
&& !cand_already_replaced (c
))
2594 savings
+= repl_savings
+ c
->dead_savings
;
2597 && phi_dependent_cand_p (c
)
2598 && !cand_already_replaced (c
))
2600 int phi_savings
= 0;
2601 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
2602 savings
-= phi_incr_cost (c
, incr
, phi
, &phi_savings
);
2604 if (has_single_use (gimple_phi_result (phi
)))
2605 savings
+= phi_savings
;
2609 savings
+= total_savings (repl_savings
, lookup_cand (c
->dependent
), incr
,
2613 savings
+= total_savings (repl_savings
, lookup_cand (c
->sibling
), incr
,
2619 /* Use target-specific costs to determine and record which increments
2620 in the current candidate tree are profitable to replace, assuming
2621 MODE and SPEED. FIRST_DEP is the first dependent of the root of
2624 One slight limitation here is that we don't account for the possible
2625 introduction of casts in some cases. See replace_one_candidate for
2626 the cases where these are introduced. This should probably be cleaned
2630 analyze_increments (slsr_cand_t first_dep
, enum machine_mode mode
, bool speed
)
2634 for (i
= 0; i
< incr_vec_len
; i
++)
2636 HOST_WIDE_INT incr
= incr_vec
[i
].incr
.to_shwi ();
2638 /* If somehow this increment is bigger than a HWI, we won't
2639 be optimizing candidates that use it. And if the increment
2640 has a count of zero, nothing will be done with it. */
2641 if (!incr_vec
[i
].incr
.fits_shwi () || !incr_vec
[i
].count
)
2642 incr_vec
[i
].cost
= COST_INFINITE
;
2644 /* Increments of 0, 1, and -1 are always profitable to replace,
2645 because they always replace a multiply or add with an add or
2646 copy, and may cause one or more existing instructions to go
2647 dead. Exception: -1 can't be assumed to be profitable for
2648 pointer addition. */
2652 && (gimple_assign_rhs_code (first_dep
->cand_stmt
)
2653 != POINTER_PLUS_EXPR
)))
2654 incr_vec
[i
].cost
= COST_NEUTRAL
;
2656 /* FORNOW: If we need to add an initializer, give up if a cast from
2657 the candidate's type to its stride's type can lose precision.
2658 This could eventually be handled better by expressly retaining the
2659 result of a cast to a wider type in the stride. Example:
2664 _4 = x + _3; ADD: x + (10 * _1) : int
2666 _6 = x + _3; ADD: x + (15 * _1) : int
2668 Right now replacing _6 would cause insertion of an initializer
2669 of the form "short int T = _1 * 5;" followed by a cast to
2670 int, which could overflow incorrectly. Had we recorded _2 or
2671 (int)_1 as the stride, this wouldn't happen. However, doing
2672 this breaks other opportunities, so this will require some
2674 else if (!incr_vec
[i
].initializer
2675 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2676 && !legal_cast_p_1 (first_dep
->stride
,
2677 gimple_assign_lhs (first_dep
->cand_stmt
)))
2679 incr_vec
[i
].cost
= COST_INFINITE
;
2681 /* If we need to add an initializer, make sure we don't introduce
2682 a multiply by a pointer type, which can happen in certain cast
2683 scenarios. FIXME: When cleaning up these cast issues, we can
2684 afford to introduce the multiply provided we cast out to an
2685 unsigned int of appropriate size. */
2686 else if (!incr_vec
[i
].initializer
2687 && TREE_CODE (first_dep
->stride
) != INTEGER_CST
2688 && POINTER_TYPE_P (TREE_TYPE (first_dep
->stride
)))
2690 incr_vec
[i
].cost
= COST_INFINITE
;
2692 /* For any other increment, if this is a multiply candidate, we
2693 must introduce a temporary T and initialize it with
2694 T_0 = stride * increment. When optimizing for speed, walk the
2695 candidate tree to calculate the best cost reduction along any
2696 path; if it offsets the fixed cost of inserting the initializer,
2697 replacing the increment is profitable. When optimizing for
2698 size, instead calculate the total cost reduction from replacing
2699 all candidates with this increment. */
2700 else if (first_dep
->kind
== CAND_MULT
)
2702 int cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2703 int repl_savings
= mul_cost (speed
, mode
) - add_cost (speed
, mode
);
2705 cost
= lowest_cost_path (cost
, repl_savings
, first_dep
,
2706 incr_vec
[i
].incr
, COUNT_PHIS
);
2708 cost
-= total_savings (repl_savings
, first_dep
, incr_vec
[i
].incr
,
2711 incr_vec
[i
].cost
= cost
;
2714 /* If this is an add candidate, the initializer may already
2715 exist, so only calculate the cost of the initializer if it
2716 doesn't. We are replacing one add with another here, so the
2717 known replacement savings is zero. We will account for removal
2718 of dead instructions in lowest_cost_path or total_savings. */
2722 if (!incr_vec
[i
].initializer
)
2723 cost
= mult_by_coeff_cost (incr
, mode
, speed
);
2726 cost
= lowest_cost_path (cost
, 0, first_dep
, incr_vec
[i
].incr
,
2729 cost
-= total_savings (0, first_dep
, incr_vec
[i
].incr
,
2732 incr_vec
[i
].cost
= cost
;
2737 /* Return the nearest common dominator of BB1 and BB2. If the blocks
2738 are identical, return the earlier of C1 and C2 in *WHERE. Otherwise,
2739 if the NCD matches BB1, return C1 in *WHERE; if the NCD matches BB2,
2740 return C2 in *WHERE; and if the NCD matches neither, return NULL in
2741 *WHERE. Note: It is possible for one of C1 and C2 to be NULL. */
2744 ncd_for_two_cands (basic_block bb1
, basic_block bb2
,
2745 slsr_cand_t c1
, slsr_cand_t c2
, slsr_cand_t
*where
)
2761 ncd
= nearest_common_dominator (CDI_DOMINATORS
, bb1
, bb2
);
2763 /* If both candidates are in the same block, the earlier
2765 if (bb1
== ncd
&& bb2
== ncd
)
2767 if (!c1
|| (c2
&& c2
->cand_num
< c1
->cand_num
))
2773 /* Otherwise, if one of them produced a candidate in the
2774 dominator, that one wins. */
2775 else if (bb1
== ncd
)
2778 else if (bb2
== ncd
)
2781 /* If neither matches the dominator, neither wins. */
2788 /* Consider all candidates that feed PHI. Find the nearest common
2789 dominator of those candidates requiring the given increment INCR.
2790 Further find and return the nearest common dominator of this result
2791 with block NCD. If the returned block contains one or more of the
2792 candidates, return the earliest candidate in the block in *WHERE. */
2795 ncd_with_phi (slsr_cand_t c
, double_int incr
, gimple phi
,
2796 basic_block ncd
, slsr_cand_t
*where
)
2799 slsr_cand_t basis
= lookup_cand (c
->basis
);
2800 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
2802 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
2804 tree arg
= gimple_phi_arg_def (phi
, i
);
2806 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
2808 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
2810 if (gimple_code (arg_def
) == GIMPLE_PHI
)
2811 ncd
= ncd_with_phi (c
, incr
, arg_def
, ncd
, where
);
2814 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
2815 double_int diff
= arg_cand
->index
- basis
->index
;
2817 if ((incr
== diff
) || (!address_arithmetic_p
&& incr
== -diff
))
2818 ncd
= ncd_for_two_cands (ncd
, gimple_bb (arg_cand
->cand_stmt
),
2819 *where
, arg_cand
, where
);
2827 /* Consider the candidate C together with any candidates that feed
2828 C's phi dependence (if any). Find and return the nearest common
2829 dominator of those candidates requiring the given increment INCR.
2830 If the returned block contains one or more of the candidates,
2831 return the earliest candidate in the block in *WHERE. */
2834 ncd_of_cand_and_phis (slsr_cand_t c
, double_int incr
, slsr_cand_t
*where
)
2836 basic_block ncd
= NULL
;
2838 if (cand_abs_increment (c
) == incr
)
2840 ncd
= gimple_bb (c
->cand_stmt
);
2844 if (phi_dependent_cand_p (c
))
2845 ncd
= ncd_with_phi (c
, incr
, lookup_cand (c
->def_phi
)->cand_stmt
,
2851 /* Consider all candidates in the tree rooted at C for which INCR
2852 represents the required increment of C relative to its basis.
2853 Find and return the basic block that most nearly dominates all
2854 such candidates. If the returned block contains one or more of
2855 the candidates, return the earliest candidate in the block in
2859 nearest_common_dominator_for_cands (slsr_cand_t c
, double_int incr
,
2862 basic_block sib_ncd
= NULL
, dep_ncd
= NULL
, this_ncd
= NULL
, ncd
;
2863 slsr_cand_t sib_where
= NULL
, dep_where
= NULL
, this_where
= NULL
, new_where
;
2865 /* First find the NCD of all siblings and dependents. */
2867 sib_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->sibling
),
2870 dep_ncd
= nearest_common_dominator_for_cands (lookup_cand (c
->dependent
),
2872 if (!sib_ncd
&& !dep_ncd
)
2877 else if (sib_ncd
&& !dep_ncd
)
2879 new_where
= sib_where
;
2882 else if (dep_ncd
&& !sib_ncd
)
2884 new_where
= dep_where
;
2888 ncd
= ncd_for_two_cands (sib_ncd
, dep_ncd
, sib_where
,
2889 dep_where
, &new_where
);
2891 /* If the candidate's increment doesn't match the one we're interested
2892 in (and nor do any increments for feeding defs of a phi-dependence),
2893 then the result depends only on siblings and dependents. */
2894 this_ncd
= ncd_of_cand_and_phis (c
, incr
, &this_where
);
2896 if (!this_ncd
|| cand_already_replaced (c
))
2902 /* Otherwise, compare this candidate with the result from all siblings
2904 ncd
= ncd_for_two_cands (ncd
, this_ncd
, new_where
, this_where
, where
);
2909 /* Return TRUE if the increment indexed by INDEX is profitable to replace. */
2912 profitable_increment_p (unsigned index
)
2914 return (incr_vec
[index
].cost
<= COST_NEUTRAL
);
2917 /* For each profitable increment in the increment vector not equal to
2918 0 or 1 (or -1, for non-pointer arithmetic), find the nearest common
2919 dominator of all statements in the candidate chain rooted at C
2920 that require that increment, and insert an initializer
2921 T_0 = stride * increment at that location. Record T_0 with the
2922 increment record. */
2925 insert_initializers (slsr_cand_t c
)
2928 tree new_var
= NULL_TREE
;
2930 for (i
= 0; i
< incr_vec_len
; i
++)
2933 slsr_cand_t where
= NULL
;
2935 tree stride_type
, new_name
, incr_tree
;
2936 double_int incr
= incr_vec
[i
].incr
;
2938 if (!profitable_increment_p (i
)
2940 || (incr
.is_minus_one ()
2941 && gimple_assign_rhs_code (c
->cand_stmt
) != POINTER_PLUS_EXPR
)
2945 /* We may have already identified an existing initializer that
2947 if (incr_vec
[i
].initializer
)
2949 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2951 fputs ("Using existing initializer: ", dump_file
);
2952 print_gimple_stmt (dump_file
,
2953 SSA_NAME_DEF_STMT (incr_vec
[i
].initializer
),
2959 /* Find the block that most closely dominates all candidates
2960 with this increment. If there is at least one candidate in
2961 that block, the earliest one will be returned in WHERE. */
2962 bb
= nearest_common_dominator_for_cands (c
, incr
, &where
);
2964 /* Create a new SSA name to hold the initializer's value. */
2965 stride_type
= TREE_TYPE (c
->stride
);
2966 lazy_create_slsr_reg (&new_var
, stride_type
);
2967 new_name
= make_ssa_name (new_var
, NULL
);
2968 incr_vec
[i
].initializer
= new_name
;
2970 /* Create the initializer and insert it in the latest possible
2971 dominating position. */
2972 incr_tree
= double_int_to_tree (stride_type
, incr
);
2973 init_stmt
= gimple_build_assign_with_ops (MULT_EXPR
, new_name
,
2974 c
->stride
, incr_tree
);
2977 gimple_stmt_iterator gsi
= gsi_for_stmt (where
->cand_stmt
);
2978 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2979 gimple_set_location (init_stmt
, gimple_location (where
->cand_stmt
));
2983 gimple_stmt_iterator gsi
= gsi_last_bb (bb
);
2984 gimple basis_stmt
= lookup_cand (c
->basis
)->cand_stmt
;
2986 if (!gsi_end_p (gsi
) && is_ctrl_stmt (gsi_stmt (gsi
)))
2987 gsi_insert_before (&gsi
, init_stmt
, GSI_SAME_STMT
);
2989 gsi_insert_after (&gsi
, init_stmt
, GSI_SAME_STMT
);
2991 gimple_set_location (init_stmt
, gimple_location (basis_stmt
));
2994 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
2996 fputs ("Inserting initializer: ", dump_file
);
2997 print_gimple_stmt (dump_file
, init_stmt
, 0, 0);
3002 /* Return TRUE iff all required increments for candidates feeding PHI
3003 are profitable to replace on behalf of candidate C. */
3006 all_phi_incrs_profitable (slsr_cand_t c
, gimple phi
)
3009 slsr_cand_t basis
= lookup_cand (c
->basis
);
3010 slsr_cand_t phi_cand
= base_cand_from_table (gimple_phi_result (phi
));
3012 for (i
= 0; i
< gimple_phi_num_args (phi
); i
++)
3014 tree arg
= gimple_phi_arg_def (phi
, i
);
3016 if (!operand_equal_p (arg
, phi_cand
->base_expr
, 0))
3018 gimple arg_def
= SSA_NAME_DEF_STMT (arg
);
3020 if (gimple_code (arg_def
) == GIMPLE_PHI
)
3022 if (!all_phi_incrs_profitable (c
, arg_def
))
3028 slsr_cand_t arg_cand
= base_cand_from_table (arg
);
3029 double_int increment
= arg_cand
->index
- basis
->index
;
3031 if (!address_arithmetic_p
&& increment
.is_negative ())
3032 increment
= -increment
;
3034 j
= incr_vec_index (increment
);
3036 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3038 fprintf (dump_file
, " Conditional candidate %d, phi: ",
3040 print_gimple_stmt (dump_file
, phi
, 0, 0);
3041 fputs (" increment: ", dump_file
);
3042 dump_double_int (dump_file
, increment
, false);
3043 fprintf (dump_file
, "\n cost: %d\n", incr_vec
[j
].cost
);
3044 if (profitable_increment_p (j
))
3045 fputs (" Replacing...\n", dump_file
);
3047 fputs (" Not replaced.\n", dump_file
);
3050 if (!profitable_increment_p (j
))
3059 /* Create a NOP_EXPR that copies FROM_EXPR into a new SSA name of
3060 type TO_TYPE, and insert it in front of the statement represented
3061 by candidate C. Use *NEW_VAR to create the new SSA name. Return
3062 the new SSA name. */
3065 introduce_cast_before_cand (slsr_cand_t c
, tree to_type
,
3066 tree from_expr
, tree
*new_var
)
3070 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3072 lazy_create_slsr_reg (new_var
, to_type
);
3073 cast_lhs
= make_ssa_name (*new_var
, NULL
);
3074 cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, cast_lhs
,
3075 from_expr
, NULL_TREE
);
3076 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3077 gsi_insert_before (&gsi
, cast_stmt
, GSI_SAME_STMT
);
3079 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3081 fputs (" Inserting: ", dump_file
);
3082 print_gimple_stmt (dump_file
, cast_stmt
, 0, 0);
3088 /* Replace the RHS of the statement represented by candidate C with
3089 NEW_CODE, NEW_RHS1, and NEW_RHS2, provided that to do so doesn't
3090 leave C unchanged or just interchange its operands. The original
3091 operation and operands are in OLD_CODE, OLD_RHS1, and OLD_RHS2.
3092 If the replacement was made and we are doing a details dump,
3093 return the revised statement, else NULL. */
3096 replace_rhs_if_not_dup (enum tree_code new_code
, tree new_rhs1
, tree new_rhs2
,
3097 enum tree_code old_code
, tree old_rhs1
, tree old_rhs2
,
3100 if (new_code
!= old_code
3101 || ((!operand_equal_p (new_rhs1
, old_rhs1
, 0)
3102 || !operand_equal_p (new_rhs2
, old_rhs2
, 0))
3103 && (!operand_equal_p (new_rhs1
, old_rhs2
, 0)
3104 || !operand_equal_p (new_rhs2
, old_rhs1
, 0))))
3106 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3107 gimple_assign_set_rhs_with_ops (&gsi
, new_code
, new_rhs1
, new_rhs2
);
3108 update_stmt (gsi_stmt (gsi
));
3110 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3111 return gsi_stmt (gsi
);
3114 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3115 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3120 /* Strength-reduce the statement represented by candidate C by replacing
3121 it with an equivalent addition or subtraction. I is the index into
3122 the increment vector identifying C's increment. NEW_VAR is used to
3123 create a new SSA name if a cast needs to be introduced. BASIS_NAME
3124 is the rhs1 to use in creating the add/subtract. */
3127 replace_one_candidate (slsr_cand_t c
, unsigned i
, tree
*new_var
,
3130 gimple stmt_to_print
= NULL
;
3131 tree orig_rhs1
, orig_rhs2
;
3133 enum tree_code orig_code
, repl_code
;
3134 double_int cand_incr
;
3136 orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3137 orig_rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
3138 orig_rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
3139 cand_incr
= cand_increment (c
);
3141 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3143 fputs ("Replacing: ", dump_file
);
3144 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
3145 stmt_to_print
= c
->cand_stmt
;
3148 if (address_arithmetic_p
)
3149 repl_code
= POINTER_PLUS_EXPR
;
3151 repl_code
= PLUS_EXPR
;
3153 /* If the increment has an initializer T_0, replace the candidate
3154 statement with an add of the basis name and the initializer. */
3155 if (incr_vec
[i
].initializer
)
3157 tree init_type
= TREE_TYPE (incr_vec
[i
].initializer
);
3158 tree orig_type
= TREE_TYPE (orig_rhs2
);
3160 if (types_compatible_p (orig_type
, init_type
))
3161 rhs2
= incr_vec
[i
].initializer
;
3163 rhs2
= introduce_cast_before_cand (c
, orig_type
,
3164 incr_vec
[i
].initializer
,
3167 if (incr_vec
[i
].incr
!= cand_incr
)
3169 gcc_assert (repl_code
== PLUS_EXPR
);
3170 repl_code
= MINUS_EXPR
;
3173 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3174 orig_code
, orig_rhs1
, orig_rhs2
,
3178 /* Otherwise, the increment is one of -1, 0, and 1. Replace
3179 with a subtract of the stride from the basis name, a copy
3180 from the basis name, or an add of the stride to the basis
3181 name, respectively. It may be necessary to introduce a
3182 cast (or reuse an existing cast). */
3183 else if (cand_incr
.is_one ())
3185 tree stride_type
= TREE_TYPE (c
->stride
);
3186 tree orig_type
= TREE_TYPE (orig_rhs2
);
3188 if (types_compatible_p (orig_type
, stride_type
))
3191 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
, new_var
);
3193 stmt_to_print
= replace_rhs_if_not_dup (repl_code
, basis_name
, rhs2
,
3194 orig_code
, orig_rhs1
, orig_rhs2
,
3198 else if (cand_incr
.is_minus_one ())
3200 tree stride_type
= TREE_TYPE (c
->stride
);
3201 tree orig_type
= TREE_TYPE (orig_rhs2
);
3202 gcc_assert (repl_code
!= POINTER_PLUS_EXPR
);
3204 if (types_compatible_p (orig_type
, stride_type
))
3207 rhs2
= introduce_cast_before_cand (c
, orig_type
, c
->stride
, new_var
);
3209 if (orig_code
!= MINUS_EXPR
3210 || !operand_equal_p (basis_name
, orig_rhs1
, 0)
3211 || !operand_equal_p (rhs2
, orig_rhs2
, 0))
3213 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3214 gimple_assign_set_rhs_with_ops (&gsi
, MINUS_EXPR
, basis_name
, rhs2
);
3215 update_stmt (gsi_stmt (gsi
));
3217 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3218 stmt_to_print
= gsi_stmt (gsi
);
3220 else if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3221 fputs (" (duplicate, not actually replacing)\n", dump_file
);
3224 else if (cand_incr
.is_zero ())
3226 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
3227 tree lhs_type
= TREE_TYPE (lhs
);
3228 tree basis_type
= TREE_TYPE (basis_name
);
3230 if (types_compatible_p (lhs_type
, basis_type
))
3232 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
3233 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3234 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
3235 gsi_replace (&gsi
, copy_stmt
, false);
3237 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3238 stmt_to_print
= copy_stmt
;
3242 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
3243 gimple cast_stmt
= gimple_build_assign_with_ops (NOP_EXPR
, lhs
,
3246 gimple_set_location (cast_stmt
, gimple_location (c
->cand_stmt
));
3247 gsi_replace (&gsi
, cast_stmt
, false);
3249 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3250 stmt_to_print
= cast_stmt
;
3256 if (dump_file
&& (dump_flags
& TDF_DETAILS
) && stmt_to_print
)
3258 fputs ("With: ", dump_file
);
3259 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
3260 fputs ("\n", dump_file
);
3264 /* For each candidate in the tree rooted at C, replace it with
3265 an increment if such has been shown to be profitable. */
3268 replace_profitable_candidates (slsr_cand_t c
)
3270 if (!cand_already_replaced (c
))
3272 double_int increment
= cand_abs_increment (c
);
3273 tree new_var
= NULL
;
3274 enum tree_code orig_code
= gimple_assign_rhs_code (c
->cand_stmt
);
3277 i
= incr_vec_index (increment
);
3279 /* Only process profitable increments. Nothing useful can be done
3280 to a cast or copy. */
3281 if (profitable_increment_p (i
)
3282 && orig_code
!= MODIFY_EXPR
3283 && orig_code
!= NOP_EXPR
)
3285 if (phi_dependent_cand_p (c
))
3287 gimple phi
= lookup_cand (c
->def_phi
)->cand_stmt
;
3289 if (all_phi_incrs_profitable (c
, phi
))
3291 /* Look up the LHS SSA name from C's basis. This will be
3292 the RHS1 of the adds we will introduce to create new
3294 slsr_cand_t basis
= lookup_cand (c
->basis
);
3295 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3297 /* Create a new phi statement that will represent C's true
3298 basis after the transformation is complete. */
3299 location_t loc
= gimple_location (c
->cand_stmt
);
3300 tree name
= create_phi_basis (c
, phi
, basis_name
,
3301 loc
, UNKNOWN_STRIDE
);
3303 /* Replace C with an add of the new basis phi and the
3305 replace_one_candidate (c
, i
, &new_var
, name
);
3310 slsr_cand_t basis
= lookup_cand (c
->basis
);
3311 tree basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
3312 replace_one_candidate (c
, i
, &new_var
, basis_name
);
3318 replace_profitable_candidates (lookup_cand (c
->sibling
));
3321 replace_profitable_candidates (lookup_cand (c
->dependent
));
3324 /* Analyze costs of related candidates in the candidate vector,
3325 and make beneficial replacements. */
3328 analyze_candidates_and_replace (void)
3333 /* Each candidate that has a null basis and a non-null
3334 dependent is the root of a tree of related statements.
3335 Analyze each tree to determine a subset of those
3336 statements that can be replaced with maximum benefit. */
3337 FOR_EACH_VEC_ELT (cand_vec
, i
, c
)
3339 slsr_cand_t first_dep
;
3341 if (c
->basis
!= 0 || c
->dependent
== 0)
3344 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3345 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
3348 first_dep
= lookup_cand (c
->dependent
);
3350 /* If this is a chain of CAND_REFs, unconditionally replace
3351 each of them with a strength-reduced data reference. */
3352 if (c
->kind
== CAND_REF
)
3355 /* If the common stride of all related candidates is a known
3356 constant, each candidate without a phi-dependence can be
3357 profitably replaced. Each replaces a multiply by a single
3358 add, with the possibility that a feeding add also goes dead.
3359 A candidate with a phi-dependence is replaced only if the
3360 compensation code it requires is offset by the strength
3361 reduction savings. */
3362 else if (TREE_CODE (c
->stride
) == INTEGER_CST
)
3363 replace_uncond_cands_and_profitable_phis (first_dep
);
3365 /* When the stride is an SSA name, it may still be profitable
3366 to replace some or all of the dependent candidates, depending
3367 on whether the introduced increments can be reused, or are
3368 less expensive to calculate than the replaced statements. */
3372 enum machine_mode mode
;
3375 /* Determine whether we'll be generating pointer arithmetic
3376 when replacing candidates. */
3377 address_arithmetic_p
= (c
->kind
== CAND_ADD
3378 && POINTER_TYPE_P (c
->cand_type
));
3380 /* If all candidates have already been replaced under other
3381 interpretations, nothing remains to be done. */
3382 length
= count_candidates (c
);
3386 /* Construct an array of increments for this candidate chain. */
3387 incr_vec
= XNEWVEC (incr_info
, length
);
3389 record_increments (c
);
3391 /* Determine which increments are profitable to replace. */
3392 mode
= TYPE_MODE (TREE_TYPE (gimple_assign_lhs (c
->cand_stmt
)));
3393 speed
= optimize_cands_for_speed_p (c
);
3394 analyze_increments (first_dep
, mode
, speed
);
3396 /* Insert initializers of the form T_0 = stride * increment
3397 for use in profitable replacements. */
3398 insert_initializers (first_dep
);
3401 /* Perform the replacements. */
3402 replace_profitable_candidates (first_dep
);
3409 execute_strength_reduction (void)
3411 struct dom_walk_data walk_data
;
3413 /* Create the obstack where candidates will reside. */
3414 gcc_obstack_init (&cand_obstack
);
3416 /* Allocate the candidate vector. */
3417 cand_vec
.create (128);
3419 /* Allocate the mapping from statements to candidate indices. */
3420 stmt_cand_map
= pointer_map_create ();
3422 /* Create the obstack where candidate chains will reside. */
3423 gcc_obstack_init (&chain_obstack
);
3425 /* Allocate the mapping from base expressions to candidate chains. */
3426 base_cand_map
.create (500);
3428 /* Initialize the loop optimizer. We need to detect flow across
3429 back edges, and this gives us dominator information as well. */
3430 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
3432 /* Set up callbacks for the generic dominator tree walker. */
3433 walk_data
.dom_direction
= CDI_DOMINATORS
;
3434 walk_data
.initialize_block_local_data
= NULL
;
3435 walk_data
.before_dom_children
= find_candidates_in_block
;
3436 walk_data
.after_dom_children
= NULL
;
3437 walk_data
.global_data
= NULL
;
3438 walk_data
.block_local_data_size
= 0;
3439 init_walk_dominator_tree (&walk_data
);
3441 /* Walk the CFG in predominator order looking for strength reduction
3443 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
3445 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
3448 dump_cand_chains ();
3451 /* Analyze costs and make appropriate replacements. */
3452 analyze_candidates_and_replace ();
3454 /* Free resources. */
3455 fini_walk_dominator_tree (&walk_data
);
3456 loop_optimizer_finalize ();
3457 base_cand_map
.dispose ();
3458 obstack_free (&chain_obstack
, NULL
);
3459 pointer_map_destroy (stmt_cand_map
);
3460 cand_vec
.release ();
3461 obstack_free (&cand_obstack
, NULL
);
3467 gate_strength_reduction (void)
3469 return flag_tree_slsr
;
3472 struct gimple_opt_pass pass_strength_reduction
=
3477 OPTGROUP_NONE
, /* optinfo_flags */
3478 gate_strength_reduction
, /* gate */
3479 execute_strength_reduction
, /* execute */
3482 0, /* static_pass_number */
3483 TV_GIMPLE_SLSR
, /* tv_id */
3484 PROP_cfg
| PROP_ssa
, /* properties_required */
3485 0, /* properties_provided */
3486 0, /* properties_destroyed */
3487 0, /* todo_flags_start */
3488 TODO_verify_ssa
/* todo_flags_finish */