1 /* Straight-line strength reduction.
2 Copyright (C) 2012 Free Software Foundation, Inc.
3 Contributed by Bill Schmidt, IBM <wschmidt@linux.ibm.com>
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 /* There are many algorithms for performing strength reduction on
22 loops. This is not one of them. IVOPTS handles strength reduction
23 of induction variables just fine. This pass is intended to pick
24 up the crumbs it leaves behind, by considering opportunities for
25 strength reduction along dominator paths.
27 Strength reduction will be implemented in four stages, gradually
28 adding more complex candidates:
30 1) Explicit multiplies, known constant multipliers, no
31 conditional increments. (complete)
32 2) Explicit multiplies, unknown constant multipliers,
33 no conditional increments. (data gathering complete,
35 3) Implicit multiplies in addressing expressions. (pending)
36 4) Explicit multiplies, conditional increments. (pending)
38 It would also be possible to apply strength reduction to divisions
39 and modulos, but such opportunities are relatively uncommon.
41 Strength reduction is also currently restricted to integer operations.
42 If desired, it could be extended to floating-point operations under
43 control of something like -funsafe-math-optimizations. */
47 #include "coretypes.h"
50 #include "basic-block.h"
51 #include "tree-pass.h"
53 #include "gimple-pretty-print.h"
54 #include "tree-flow.h"
56 #include "pointer-set.h"
58 /* Information about a strength reduction candidate. Each statement
59 in the candidate table represents an expression of one of the
60 following forms (the special case of CAND_REF will be described
63 (CAND_MULT) S1: X = (B + i) * S
64 (CAND_ADD) S1: X = B + (i * S)
66 Here X and B are SSA names, i is an integer constant, and S is
67 either an SSA name or a constant. We call B the "base," i the
68 "index", and S the "stride."
70 Any statement S0 that dominates S1 and is of the form:
72 (CAND_MULT) S0: Y = (B + i') * S
73 (CAND_ADD) S0: Y = B + (i' * S)
75 is called a "basis" for S1. In both cases, S1 may be replaced by
77 S1': X = Y + (i - i') * S,
79 where (i - i') * S is folded to the extent possible.
81 All gimple statements are visited in dominator order, and each
82 statement that may contribute to one of the forms of S1 above is
83 given at least one entry in the candidate table. Such statements
84 include addition, pointer addition, subtraction, multiplication,
85 negation, copies, and nontrivial type casts. If a statement may
86 represent more than one expression of the forms of S1 above,
87 multiple "interpretations" are stored in the table and chained
90 * An add of two SSA names may treat either operand as the base.
91 * A multiply of two SSA names, likewise.
92 * A copy or cast may be thought of as either a CAND_MULT with
93 i = 0 and S = 1, or as a CAND_ADD with i = 0 or S = 0.
95 Candidate records are allocated from an obstack. They are addressed
96 both from a hash table keyed on S1, and from a vector of candidate
97 pointers arranged in predominator order.
101 Currently we don't recognize:
106 as a strength reduction opportunity, even though this S1 would
107 also be replaceable by the S1' above. This can be added if it
108 comes up in practice. */
111 /* Index into the candidate vector, offset by 1. VECs are zero-based,
112 while cand_idx's are one-based, with zero indicating null. */
113 typedef unsigned cand_idx
;
115 /* The kind of candidate. */
124 /* The candidate statement S1. */
127 /* The base SSA name B. */
133 /* The index constant i. */
136 /* The type of the candidate. This is normally the type of base_name,
137 but casts may have occurred when combining feeding instructions.
138 A candidate can only be a basis for candidates of the same final type. */
141 /* The kind of candidate (CAND_MULT, etc.). */
144 /* Index of this candidate in the candidate vector. */
147 /* Index of the next candidate record for the same statement.
148 A statement may be useful in more than one way (e.g., due to
149 commutativity). So we can have multiple "interpretations"
151 cand_idx next_interp
;
153 /* Index of the basis statement S0, if any, in the candidate vector. */
156 /* First candidate for which this candidate is a basis, if one exists. */
159 /* Next candidate having the same basis as this one. */
162 /* If this is a conditional candidate, the defining PHI statement
163 for the base SSA name B. For future use; always NULL for now. */
166 /* Savings that can be expected from eliminating dead code if this
167 candidate is replaced. */
171 typedef struct slsr_cand_d slsr_cand
, *slsr_cand_t
;
172 typedef const struct slsr_cand_d
*const_slsr_cand_t
;
174 /* Pointers to candidates are chained together as part of a mapping
175 from SSA names to the candidates that use them as a base name. */
179 /* SSA name that serves as a base name for the chain of candidates. */
182 /* Pointer to a candidate. */
186 struct cand_chain_d
*next
;
190 typedef struct cand_chain_d cand_chain
, *cand_chain_t
;
191 typedef const struct cand_chain_d
*const_cand_chain_t
;
193 /* Candidates are maintained in a vector. If candidate X dominates
194 candidate Y, then X appears before Y in the vector; but the
195 converse does not necessarily hold. */
196 DEF_VEC_P (slsr_cand_t
);
197 DEF_VEC_ALLOC_P (slsr_cand_t
, heap
);
198 static VEC (slsr_cand_t
, heap
) *cand_vec
;
206 /* Pointer map embodying a mapping from statements to candidates. */
207 static struct pointer_map_t
*stmt_cand_map
;
209 /* Obstack for candidates. */
210 static struct obstack cand_obstack
;
212 /* Array mapping from base SSA names to chains of candidates. */
213 static cand_chain_t
*base_cand_map
;
215 /* Obstack for candidate chains. */
216 static struct obstack chain_obstack
;
218 /* Produce a pointer to the IDX'th candidate in the candidate vector. */
221 lookup_cand (cand_idx idx
)
223 return VEC_index (slsr_cand_t
, cand_vec
, idx
- 1);
226 /* Use the base name from candidate C to look for possible candidates
227 that can serve as a basis for C. Each potential basis must also
228 appear in a block that dominates the candidate statement and have
229 the same stride and type. If more than one possible basis exists,
230 the one with highest index in the vector is chosen; this will be
231 the most immediately dominating basis. */
234 find_basis_for_candidate (slsr_cand_t c
)
237 slsr_cand_t basis
= NULL
;
239 gcc_assert (TREE_CODE (c
->base_name
) == SSA_NAME
);
240 chain
= base_cand_map
[SSA_NAME_VERSION (c
->base_name
)];
242 for (; chain
; chain
= chain
->next
)
244 slsr_cand_t one_basis
= chain
->cand
;
246 if (one_basis
->kind
!= c
->kind
247 || !operand_equal_p (one_basis
->stride
, c
->stride
, 0)
248 || !types_compatible_p (one_basis
->cand_type
, c
->cand_type
)
249 || !dominated_by_p (CDI_DOMINATORS
,
250 gimple_bb (c
->cand_stmt
),
251 gimple_bb (one_basis
->cand_stmt
)))
254 if (!basis
|| basis
->cand_num
< one_basis
->cand_num
)
260 c
->sibling
= basis
->dependent
;
261 basis
->dependent
= c
->cand_num
;
262 return basis
->cand_num
;
268 /* Record a mapping from the base name of C to C itself, indicating that
269 C may potentially serve as a basis using that base name. */
272 record_potential_basis (slsr_cand_t c
)
274 cand_chain_t node
, head
;
277 node
= (cand_chain_t
) obstack_alloc (&chain_obstack
, sizeof (cand_chain
));
278 node
->base_name
= c
->base_name
;
281 index
= SSA_NAME_VERSION (c
->base_name
);
282 head
= base_cand_map
[index
];
286 node
->next
= head
->next
;
290 base_cand_map
[index
] = node
;
293 /* Allocate storage for a new candidate and initialize its fields.
294 Attempt to find a basis for the candidate. */
297 alloc_cand_and_find_basis (enum cand_kind kind
, gimple gs
, tree base
,
298 double_int index
, tree stride
, tree ctype
,
301 slsr_cand_t c
= (slsr_cand_t
) obstack_alloc (&cand_obstack
,
307 c
->cand_type
= ctype
;
309 c
->cand_num
= VEC_length (slsr_cand_t
, cand_vec
) + 1;
314 c
->dead_savings
= savings
;
316 VEC_safe_push (slsr_cand_t
, heap
, cand_vec
, c
);
317 c
->basis
= find_basis_for_candidate (c
);
318 record_potential_basis (c
);
323 /* Determine the target cost of statement GS when compiling according
327 stmt_cost (gimple gs
, bool speed
)
329 tree lhs
, rhs1
, rhs2
;
330 enum machine_mode lhs_mode
;
332 gcc_assert (is_gimple_assign (gs
));
333 lhs
= gimple_assign_lhs (gs
);
334 rhs1
= gimple_assign_rhs1 (gs
);
335 lhs_mode
= TYPE_MODE (TREE_TYPE (lhs
));
337 switch (gimple_assign_rhs_code (gs
))
340 rhs2
= gimple_assign_rhs2 (gs
);
342 if (host_integerp (rhs2
, 0))
343 return multiply_by_const_cost (TREE_INT_CST_LOW (rhs2
), lhs_mode
,
346 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
347 return multiply_regs_cost (TYPE_MODE (TREE_TYPE (lhs
)), speed
);
350 case POINTER_PLUS_EXPR
:
352 rhs2
= gimple_assign_rhs2 (gs
);
354 if (host_integerp (rhs2
, 0))
355 return add_const_cost (TYPE_MODE (TREE_TYPE (rhs1
)), speed
);
357 gcc_assert (TREE_CODE (rhs1
) != INTEGER_CST
);
358 return add_regs_cost (lhs_mode
, speed
);
361 return negate_reg_cost (lhs_mode
, speed
);
364 return extend_or_trunc_reg_cost (TREE_TYPE (lhs
), TREE_TYPE (rhs1
),
367 /* Note that we don't assign costs to copies that in most cases
377 /* Look up the defining statement for BASE_IN and return a pointer
378 to its candidate in the candidate table, if any; otherwise NULL.
379 Only CAND_ADD and CAND_MULT candidates are returned. */
382 base_cand_from_table (tree base_in
)
386 gimple def
= SSA_NAME_DEF_STMT (base_in
);
388 return (slsr_cand_t
) NULL
;
390 result
= (slsr_cand_t
*) pointer_map_contains (stmt_cand_map
, def
);
392 return (slsr_cand_t
) NULL
;
397 /* Add an entry to the statement-to-candidate mapping. */
400 add_cand_for_stmt (gimple gs
, slsr_cand_t c
)
402 void **slot
= pointer_map_insert (stmt_cand_map
, gs
);
407 /* Create a candidate entry for a statement GS, where GS multiplies
408 two SSA names BASE_IN and STRIDE_IN. Propagate any known information
409 about the two SSA names into the new candidate. Return the new
413 create_mul_ssa_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
415 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
417 unsigned savings
= 0;
419 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
421 /* Look at all interpretations of the base candidate, if necessary,
422 to find information to propagate into this candidate. */
423 while (base_cand
&& !base
)
426 if (base_cand
->kind
== CAND_MULT
427 && operand_equal_p (base_cand
->stride
, integer_one_node
, 0))
433 base
= base_cand
->base_name
;
434 index
= base_cand
->index
;
436 ctype
= base_cand
->cand_type
;
437 if (has_single_use (base_in
))
438 savings
= (base_cand
->dead_savings
439 + stmt_cost (base_cand
->cand_stmt
, speed
));
441 else if (base_cand
->kind
== CAND_ADD
442 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
444 /* Y = B + (i' * S), S constant
446 ============================
447 X = B + ((i' * S) * Z) */
448 base
= base_cand
->base_name
;
449 index
= double_int_mul (base_cand
->index
,
450 tree_to_double_int (base_cand
->stride
));
452 ctype
= base_cand
->cand_type
;
453 if (has_single_use (base_in
))
454 savings
= (base_cand
->dead_savings
455 + stmt_cost (base_cand
->cand_stmt
, speed
));
458 if (base_cand
->next_interp
)
459 base_cand
= lookup_cand (base_cand
->next_interp
);
466 /* No interpretations had anything useful to propagate, so
467 produce X = (Y + 0) * Z. */
469 index
= double_int_zero
;
471 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
474 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
479 /* Create a candidate entry for a statement GS, where GS multiplies
480 SSA name BASE_IN by constant STRIDE_IN. Propagate any known
481 information about BASE_IN into the new candidate. Return the new
485 create_mul_imm_cand (gimple gs
, tree base_in
, tree stride_in
, bool speed
)
487 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
488 double_int index
, temp
;
489 unsigned savings
= 0;
491 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
493 /* Look at all interpretations of the base candidate, if necessary,
494 to find information to propagate into this candidate. */
495 while (base_cand
&& !base
)
497 if (base_cand
->kind
== CAND_MULT
498 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
500 /* Y = (B + i') * S, S constant
502 ============================
503 X = (B + i') * (S * c) */
504 base
= base_cand
->base_name
;
505 index
= base_cand
->index
;
506 temp
= double_int_mul (tree_to_double_int (base_cand
->stride
),
507 tree_to_double_int (stride_in
));
508 stride
= double_int_to_tree (TREE_TYPE (stride_in
), temp
);
509 ctype
= base_cand
->cand_type
;
510 if (has_single_use (base_in
))
511 savings
= (base_cand
->dead_savings
512 + stmt_cost (base_cand
->cand_stmt
, speed
));
514 else if (base_cand
->kind
== CAND_ADD
515 && operand_equal_p (base_cand
->stride
, integer_one_node
, 0))
519 ===========================
521 base
= base_cand
->base_name
;
522 index
= base_cand
->index
;
524 ctype
= base_cand
->cand_type
;
525 if (has_single_use (base_in
))
526 savings
= (base_cand
->dead_savings
527 + stmt_cost (base_cand
->cand_stmt
, speed
));
529 else if (base_cand
->kind
== CAND_ADD
530 && double_int_one_p (base_cand
->index
)
531 && TREE_CODE (base_cand
->stride
) == INTEGER_CST
)
533 /* Y = B + (1 * S), S constant
535 ===========================
537 base
= base_cand
->base_name
;
538 index
= tree_to_double_int (base_cand
->stride
);
540 ctype
= base_cand
->cand_type
;
541 if (has_single_use (base_in
))
542 savings
= (base_cand
->dead_savings
543 + stmt_cost (base_cand
->cand_stmt
, speed
));
546 if (base_cand
->next_interp
)
547 base_cand
= lookup_cand (base_cand
->next_interp
);
554 /* No interpretations had anything useful to propagate, so
555 produce X = (Y + 0) * c. */
557 index
= double_int_zero
;
559 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
562 c
= alloc_cand_and_find_basis (CAND_MULT
, gs
, base
, index
, stride
,
567 /* Given GS which is a multiply of scalar integers, make an appropriate
568 entry in the candidate table. If this is a multiply of two SSA names,
569 create two CAND_MULT interpretations and attempt to find a basis for
570 each of them. Otherwise, create a single CAND_MULT and attempt to
574 slsr_process_mul (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
578 /* If this is a multiply of an SSA name with itself, it is highly
579 unlikely that we will get a strength reduction opportunity, so
580 don't record it as a candidate. This simplifies the logic for
581 finding a basis, so if this is removed that must be considered. */
585 if (TREE_CODE (rhs2
) == SSA_NAME
)
587 /* Record an interpretation of this statement in the candidate table
588 assuming RHS1 is the base name and RHS2 is the stride. */
589 c
= create_mul_ssa_cand (gs
, rhs1
, rhs2
, speed
);
591 /* Add the first interpretation to the statement-candidate mapping. */
592 add_cand_for_stmt (gs
, c
);
594 /* Record another interpretation of this statement assuming RHS1
595 is the stride and RHS2 is the base name. */
596 c2
= create_mul_ssa_cand (gs
, rhs2
, rhs1
, speed
);
597 c
->next_interp
= c2
->cand_num
;
601 /* Record an interpretation for the multiply-immediate. */
602 c
= create_mul_imm_cand (gs
, rhs1
, rhs2
, speed
);
604 /* Add the interpretation to the statement-candidate mapping. */
605 add_cand_for_stmt (gs
, c
);
609 /* Create a candidate entry for a statement GS, where GS adds two
610 SSA names BASE_IN and ADDEND_IN if SUBTRACT_P is false, and
611 subtracts ADDEND_IN from BASE_IN otherwise. Propagate any known
612 information about the two SSA names into the new candidate.
613 Return the new candidate. */
616 create_add_ssa_cand (gimple gs
, tree base_in
, tree addend_in
,
617 bool subtract_p
, bool speed
)
619 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL
;
621 unsigned savings
= 0;
623 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
624 slsr_cand_t addend_cand
= base_cand_from_table (addend_in
);
626 /* The most useful transformation is a multiply-immediate feeding
627 an add or subtract. Look for that first. */
628 while (addend_cand
&& !base
)
630 if (addend_cand
->kind
== CAND_MULT
631 && double_int_zero_p (addend_cand
->index
)
632 && TREE_CODE (addend_cand
->stride
) == INTEGER_CST
)
634 /* Z = (B + 0) * S, S constant
636 ===========================
637 X = Y + ((+/-1 * S) * B) */
639 index
= tree_to_double_int (addend_cand
->stride
);
641 index
= double_int_neg (index
);
642 stride
= addend_cand
->base_name
;
643 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
644 if (has_single_use (addend_in
))
645 savings
= (addend_cand
->dead_savings
646 + stmt_cost (addend_cand
->cand_stmt
, speed
));
649 if (addend_cand
->next_interp
)
650 addend_cand
= lookup_cand (addend_cand
->next_interp
);
655 while (base_cand
&& !base
)
657 if (base_cand
->kind
== CAND_ADD
658 && (double_int_zero_p (base_cand
->index
)
659 || operand_equal_p (base_cand
->stride
,
660 integer_zero_node
, 0)))
662 /* Y = B + (i' * S), i' * S = 0
664 ============================
665 X = B + (+/-1 * Z) */
666 base
= base_cand
->base_name
;
667 index
= subtract_p
? double_int_minus_one
: double_int_one
;
669 ctype
= base_cand
->cand_type
;
670 if (has_single_use (base_in
))
671 savings
= (base_cand
->dead_savings
672 + stmt_cost (base_cand
->cand_stmt
, speed
));
676 slsr_cand_t subtrahend_cand
= base_cand_from_table (addend_in
);
678 while (subtrahend_cand
&& !base
)
680 if (subtrahend_cand
->kind
== CAND_MULT
681 && double_int_zero_p (subtrahend_cand
->index
)
682 && TREE_CODE (subtrahend_cand
->stride
) == INTEGER_CST
)
684 /* Z = (B + 0) * S, S constant
686 ===========================
687 Value: X = Y + ((-1 * S) * B) */
689 index
= tree_to_double_int (subtrahend_cand
->stride
);
690 index
= double_int_neg (index
);
691 stride
= subtrahend_cand
->base_name
;
692 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
693 if (has_single_use (addend_in
))
694 savings
= (subtrahend_cand
->dead_savings
695 + stmt_cost (subtrahend_cand
->cand_stmt
, speed
));
698 if (subtrahend_cand
->next_interp
)
699 subtrahend_cand
= lookup_cand (subtrahend_cand
->next_interp
);
701 subtrahend_cand
= NULL
;
705 if (base_cand
->next_interp
)
706 base_cand
= lookup_cand (base_cand
->next_interp
);
713 /* No interpretations had anything useful to propagate, so
714 produce X = Y + (1 * Z). */
716 index
= subtract_p
? double_int_minus_one
: double_int_one
;
718 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
721 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, base
, index
, stride
,
726 /* Create a candidate entry for a statement GS, where GS adds SSA
727 name BASE_IN to constant INDEX_IN. Propagate any known information
728 about BASE_IN into the new candidate. Return the new candidate. */
731 create_add_imm_cand (gimple gs
, tree base_in
, double_int index_in
, bool speed
)
733 enum cand_kind kind
= CAND_ADD
;
734 tree base
= NULL_TREE
, stride
= NULL_TREE
, ctype
= NULL_TREE
;
735 double_int index
, multiple
;
736 unsigned savings
= 0;
738 slsr_cand_t base_cand
= base_cand_from_table (base_in
);
740 while (base_cand
&& !base
)
742 bool unsigned_p
= TYPE_UNSIGNED (TREE_TYPE (base_cand
->stride
));
744 if (TREE_CODE (base_cand
->stride
) == INTEGER_CST
745 && double_int_multiple_of (index_in
,
746 tree_to_double_int (base_cand
->stride
),
750 /* Y = (B + i') * S, S constant, c = kS for some integer k
752 ============================
753 X = (B + (i'+ k)) * S
755 Y = B + (i' * S), S constant, c = kS for some integer k
757 ============================
758 X = (B + (i'+ k)) * S */
759 kind
= base_cand
->kind
;
760 base
= base_cand
->base_name
;
761 index
= double_int_add (base_cand
->index
, multiple
);
762 stride
= base_cand
->stride
;
763 ctype
= base_cand
->cand_type
;
764 if (has_single_use (base_in
))
765 savings
= (base_cand
->dead_savings
766 + stmt_cost (base_cand
->cand_stmt
, speed
));
769 if (base_cand
->next_interp
)
770 base_cand
= lookup_cand (base_cand
->next_interp
);
777 /* No interpretations had anything useful to propagate, so
778 produce X = Y + (c * 1). */
782 stride
= integer_one_node
;
783 ctype
= TREE_TYPE (SSA_NAME_VAR (base_in
));
786 c
= alloc_cand_and_find_basis (kind
, gs
, base
, index
, stride
,
791 /* Given GS which is an add or subtract of scalar integers or pointers,
792 make at least one appropriate entry in the candidate table. */
795 slsr_process_add (gimple gs
, tree rhs1
, tree rhs2
, bool speed
)
797 bool subtract_p
= gimple_assign_rhs_code (gs
) == MINUS_EXPR
;
798 slsr_cand_t c
= NULL
, c2
;
800 if (TREE_CODE (rhs2
) == SSA_NAME
)
802 /* First record an interpretation assuming RHS1 is the base name
803 and RHS2 is the stride. But it doesn't make sense for the
804 stride to be a pointer, so don't record a candidate in that case. */
805 if (!POINTER_TYPE_P (TREE_TYPE (SSA_NAME_VAR (rhs2
))))
807 c
= create_add_ssa_cand (gs
, rhs1
, rhs2
, subtract_p
, speed
);
809 /* Add the first interpretation to the statement-candidate
811 add_cand_for_stmt (gs
, c
);
814 /* If the two RHS operands are identical, or this is a subtract,
816 if (operand_equal_p (rhs1
, rhs2
, 0) || subtract_p
)
819 /* Otherwise, record another interpretation assuming RHS2 is the
820 base name and RHS1 is the stride, again provided that the
821 stride is not a pointer. */
822 if (!POINTER_TYPE_P (TREE_TYPE (SSA_NAME_VAR (rhs1
))))
824 c2
= create_add_ssa_cand (gs
, rhs2
, rhs1
, false, speed
);
826 c
->next_interp
= c2
->cand_num
;
828 add_cand_for_stmt (gs
, c2
);
835 /* Record an interpretation for the add-immediate. */
836 index
= tree_to_double_int (rhs2
);
838 index
= double_int_neg (index
);
840 c
= create_add_imm_cand (gs
, rhs1
, index
, speed
);
842 /* Add the interpretation to the statement-candidate mapping. */
843 add_cand_for_stmt (gs
, c
);
847 /* Given GS which is a negate of a scalar integer, make an appropriate
848 entry in the candidate table. A negate is equivalent to a multiply
852 slsr_process_neg (gimple gs
, tree rhs1
, bool speed
)
854 /* Record a CAND_MULT interpretation for the multiply by -1. */
855 slsr_cand_t c
= create_mul_imm_cand (gs
, rhs1
, integer_minus_one_node
, speed
);
857 /* Add the interpretation to the statement-candidate mapping. */
858 add_cand_for_stmt (gs
, c
);
861 /* Return TRUE if GS is a statement that defines an SSA name from
862 a conversion and is legal for us to combine with an add and multiply
863 in the candidate table. For example, suppose we have:
869 Without the type-cast, we would create a CAND_MULT for D with base B,
870 index i, and stride S. We want to record this candidate only if it
871 is equivalent to apply the type cast following the multiply:
877 We will record the type with the candidate for D. This allows us
878 to use a similar previous candidate as a basis. If we have earlier seen
884 we can replace D with
886 D = D' + (i - i') * S;
888 But if moving the type-cast would change semantics, we mustn't do this.
890 This is legitimate for casts from a non-wrapping integral type to
891 any integral type of the same or larger size. It is not legitimate
892 to convert a wrapping type to a non-wrapping type, or to a wrapping
893 type of a different size. I.e., with a wrapping type, we must
894 assume that the addition B + i could wrap, in which case performing
895 the multiply before or after one of the "illegal" type casts will
896 have different semantics. */
899 legal_cast_p (gimple gs
, tree rhs
)
901 tree lhs
, lhs_type
, rhs_type
;
902 unsigned lhs_size
, rhs_size
;
903 bool lhs_wraps
, rhs_wraps
;
905 if (!is_gimple_assign (gs
)
906 || !CONVERT_EXPR_CODE_P (gimple_assign_rhs_code (gs
)))
909 lhs
= gimple_assign_lhs (gs
);
910 lhs_type
= TREE_TYPE (lhs
);
911 rhs_type
= TREE_TYPE (rhs
);
912 lhs_size
= TYPE_PRECISION (lhs_type
);
913 rhs_size
= TYPE_PRECISION (rhs_type
);
914 lhs_wraps
= TYPE_OVERFLOW_WRAPS (lhs_type
);
915 rhs_wraps
= TYPE_OVERFLOW_WRAPS (rhs_type
);
917 if (lhs_size
< rhs_size
918 || (rhs_wraps
&& !lhs_wraps
)
919 || (rhs_wraps
&& lhs_wraps
&& rhs_size
!= lhs_size
))
925 /* Given GS which is a cast to a scalar integer type, determine whether
926 the cast is legal for strength reduction. If so, make at least one
927 appropriate entry in the candidate table. */
930 slsr_process_cast (gimple gs
, tree rhs1
, bool speed
)
933 slsr_cand_t base_cand
, c
, c2
;
934 unsigned savings
= 0;
936 if (!legal_cast_p (gs
, rhs1
))
939 lhs
= gimple_assign_lhs (gs
);
940 base_cand
= base_cand_from_table (rhs1
);
941 ctype
= TREE_TYPE (lhs
);
947 /* Propagate all data from the base candidate except the type,
948 which comes from the cast, and the base candidate's cast,
949 which is no longer applicable. */
950 if (has_single_use (rhs1
))
951 savings
= (base_cand
->dead_savings
952 + stmt_cost (base_cand
->cand_stmt
, speed
));
954 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
955 base_cand
->base_name
,
956 base_cand
->index
, base_cand
->stride
,
958 if (base_cand
->next_interp
)
959 base_cand
= lookup_cand (base_cand
->next_interp
);
966 /* If nothing is known about the RHS, create fresh CAND_ADD and
967 CAND_MULT interpretations:
972 The first of these is somewhat arbitrary, but the choice of
973 1 for the stride simplifies the logic for propagating casts
975 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
976 integer_one_node
, ctype
, 0);
977 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
978 integer_one_node
, ctype
, 0);
979 c
->next_interp
= c2
->cand_num
;
982 /* Add the first (or only) interpretation to the statement-candidate
984 add_cand_for_stmt (gs
, c
);
987 /* Given GS which is a copy of a scalar integer type, make at least one
988 appropriate entry in the candidate table.
990 This interface is included for completeness, but is unnecessary
991 if this pass immediately follows a pass that performs copy
992 propagation, such as DOM. */
995 slsr_process_copy (gimple gs
, tree rhs1
, bool speed
)
997 slsr_cand_t base_cand
, c
, c2
;
998 unsigned savings
= 0;
1000 base_cand
= base_cand_from_table (rhs1
);
1006 /* Propagate all data from the base candidate. */
1007 if (has_single_use (rhs1
))
1008 savings
= (base_cand
->dead_savings
1009 + stmt_cost (base_cand
->cand_stmt
, speed
));
1011 c
= alloc_cand_and_find_basis (base_cand
->kind
, gs
,
1012 base_cand
->base_name
,
1013 base_cand
->index
, base_cand
->stride
,
1014 base_cand
->cand_type
, savings
);
1015 if (base_cand
->next_interp
)
1016 base_cand
= lookup_cand (base_cand
->next_interp
);
1023 /* If nothing is known about the RHS, create fresh CAND_ADD and
1024 CAND_MULT interpretations:
1029 The first of these is somewhat arbitrary, but the choice of
1030 1 for the stride simplifies the logic for propagating casts
1032 c
= alloc_cand_and_find_basis (CAND_ADD
, gs
, rhs1
, double_int_zero
,
1033 integer_one_node
, TREE_TYPE (rhs1
), 0);
1034 c2
= alloc_cand_and_find_basis (CAND_MULT
, gs
, rhs1
, double_int_zero
,
1035 integer_one_node
, TREE_TYPE (rhs1
), 0);
1036 c
->next_interp
= c2
->cand_num
;
1039 /* Add the first (or only) interpretation to the statement-candidate
1041 add_cand_for_stmt (gs
, c
);
1044 /* Find strength-reduction candidates in block BB. */
1047 find_candidates_in_block (struct dom_walk_data
*walk_data ATTRIBUTE_UNUSED
,
1050 bool speed
= optimize_bb_for_speed_p (bb
);
1051 gimple_stmt_iterator gsi
;
1053 for (gsi
= gsi_start_bb (bb
); !gsi_end_p (gsi
); gsi_next (&gsi
))
1055 gimple gs
= gsi_stmt (gsi
);
1057 if (is_gimple_assign (gs
)
1058 && SCALAR_INT_MODE_P (TYPE_MODE (TREE_TYPE (gimple_assign_lhs (gs
)))))
1060 tree rhs1
= NULL_TREE
, rhs2
= NULL_TREE
;
1062 switch (gimple_assign_rhs_code (gs
))
1066 rhs1
= gimple_assign_rhs1 (gs
);
1067 rhs2
= gimple_assign_rhs2 (gs
);
1068 /* Should never happen, but currently some buggy situations
1069 in earlier phases put constants in rhs1. */
1070 if (TREE_CODE (rhs1
) != SSA_NAME
)
1074 /* Possible future opportunity: rhs1 of a ptr+ can be
1076 case POINTER_PLUS_EXPR
:
1078 rhs2
= gimple_assign_rhs2 (gs
);
1084 rhs1
= gimple_assign_rhs1 (gs
);
1085 if (TREE_CODE (rhs1
) != SSA_NAME
)
1093 switch (gimple_assign_rhs_code (gs
))
1096 slsr_process_mul (gs
, rhs1
, rhs2
, speed
);
1100 case POINTER_PLUS_EXPR
:
1102 slsr_process_add (gs
, rhs1
, rhs2
, speed
);
1106 slsr_process_neg (gs
, rhs1
, speed
);
1110 slsr_process_cast (gs
, rhs1
, speed
);
1114 slsr_process_copy (gs
, rhs1
, speed
);
1124 /* Dump a candidate for debug. */
1127 dump_candidate (slsr_cand_t c
)
1129 fprintf (dump_file
, "%3d [%d] ", c
->cand_num
,
1130 gimple_bb (c
->cand_stmt
)->index
);
1131 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1135 fputs (" MULT : (", dump_file
);
1136 print_generic_expr (dump_file
, c
->base_name
, 0);
1137 fputs (" + ", dump_file
);
1138 dump_double_int (dump_file
, c
->index
, false);
1139 fputs (") * ", dump_file
);
1140 print_generic_expr (dump_file
, c
->stride
, 0);
1141 fputs (" : ", dump_file
);
1144 fputs (" ADD : ", dump_file
);
1145 print_generic_expr (dump_file
, c
->base_name
, 0);
1146 fputs (" + (", dump_file
);
1147 dump_double_int (dump_file
, c
->index
, false);
1148 fputs (" * ", dump_file
);
1149 print_generic_expr (dump_file
, c
->stride
, 0);
1150 fputs (") : ", dump_file
);
1155 print_generic_expr (dump_file
, c
->cand_type
, 0);
1156 fprintf (dump_file
, "\n basis: %d dependent: %d sibling: %d\n",
1157 c
->basis
, c
->dependent
, c
->sibling
);
1158 fprintf (dump_file
, " next-interp: %d dead-savings: %d\n",
1159 c
->next_interp
, c
->dead_savings
);
1162 fputs (" phi: ", dump_file
);
1163 print_gimple_stmt (dump_file
, c
->def_phi
, 0, 0);
1165 fputs ("\n", dump_file
);
1168 /* Dump the candidate vector for debug. */
1171 dump_cand_vec (void)
1176 fprintf (dump_file
, "\nStrength reduction candidate vector:\n\n");
1178 FOR_EACH_VEC_ELT (slsr_cand_t
, cand_vec
, i
, c
)
1182 /* Dump the candidate chains. */
1185 dump_cand_chains (void)
1189 fprintf (dump_file
, "\nStrength reduction candidate chains:\n\n");
1191 for (i
= 0; i
< num_ssa_names
; i
++)
1193 const_cand_chain_t chain
= base_cand_map
[i
];
1199 print_generic_expr (dump_file
, chain
->base_name
, 0);
1200 fprintf (dump_file
, " -> %d", chain
->cand
->cand_num
);
1202 for (p
= chain
->next
; p
; p
= p
->next
)
1203 fprintf (dump_file
, " -> %d", p
->cand
->cand_num
);
1205 fputs ("\n", dump_file
);
1209 fputs ("\n", dump_file
);
1213 /* Recursive helper for unconditional_cands_with_known_stride_p.
1214 Returns TRUE iff C, its siblings, and its dependents are all
1215 unconditional candidates. */
1218 unconditional_cands (slsr_cand_t c
)
1223 if (c
->sibling
&& !unconditional_cands (lookup_cand (c
->sibling
)))
1226 if (c
->dependent
&& !unconditional_cands (lookup_cand (c
->dependent
)))
1232 /* Determine whether or not the tree of candidates rooted at
1233 ROOT consists entirely of unconditional increments with
1234 an INTEGER_CST stride. */
1237 unconditional_cands_with_known_stride_p (slsr_cand_t root
)
1239 /* The stride is identical for all related candidates, so
1241 if (TREE_CODE (root
->stride
) != INTEGER_CST
)
1244 return unconditional_cands (lookup_cand (root
->dependent
));
1247 /* Calculate the increment required for candidate C relative to
1251 cand_increment (slsr_cand_t c
)
1255 /* If the candidate doesn't have a basis, just return its own
1256 index. This is useful in record_increments to help us find
1257 an existing initializer. */
1261 basis
= lookup_cand (c
->basis
);
1262 gcc_assert (operand_equal_p (c
->base_name
, basis
->base_name
, 0));
1263 return double_int_sub (c
->index
, basis
->index
);
1266 /* Return TRUE iff candidate C has already been replaced under
1267 another interpretation. */
1270 cand_already_replaced (slsr_cand_t c
)
1272 return (gimple_bb (c
->cand_stmt
) == 0);
1275 /* Helper routine for replace_dependents, doing the work for a
1276 single candidate C. */
1279 replace_dependent (slsr_cand_t c
, enum tree_code cand_code
)
1281 double_int stride
= tree_to_double_int (c
->stride
);
1282 double_int bump
= double_int_mul (cand_increment (c
), stride
);
1283 gimple stmt_to_print
= NULL
;
1285 tree basis_name
, incr_type
, bump_tree
;
1286 enum tree_code code
;
1288 /* It is highly unlikely, but possible, that the resulting
1289 bump doesn't fit in a HWI. Abandon the replacement
1290 in this case. Restriction to signed HWI is conservative
1291 for unsigned types but allows for safe negation without
1293 if (!double_int_fits_in_shwi_p (bump
))
1296 basis
= lookup_cand (c
->basis
);
1297 basis_name
= gimple_assign_lhs (basis
->cand_stmt
);
1298 incr_type
= TREE_TYPE (gimple_assign_rhs1 (c
->cand_stmt
));
1301 if (double_int_negative_p (bump
))
1304 bump
= double_int_neg (bump
);
1307 bump_tree
= double_int_to_tree (incr_type
, bump
);
1309 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1311 fputs ("Replacing: ", dump_file
);
1312 print_gimple_stmt (dump_file
, c
->cand_stmt
, 0, 0);
1315 if (double_int_zero_p (bump
))
1317 tree lhs
= gimple_assign_lhs (c
->cand_stmt
);
1318 gimple copy_stmt
= gimple_build_assign (lhs
, basis_name
);
1319 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1320 gimple_set_location (copy_stmt
, gimple_location (c
->cand_stmt
));
1321 gsi_replace (&gsi
, copy_stmt
, false);
1322 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1323 stmt_to_print
= copy_stmt
;
1327 tree rhs1
= gimple_assign_rhs1 (c
->cand_stmt
);
1328 tree rhs2
= gimple_assign_rhs2 (c
->cand_stmt
);
1329 if (cand_code
!= NEGATE_EXPR
1330 && ((operand_equal_p (rhs1
, basis_name
, 0)
1331 && operand_equal_p (rhs2
, bump_tree
, 0))
1332 || (operand_equal_p (rhs1
, bump_tree
, 0)
1333 && operand_equal_p (rhs2
, basis_name
, 0))))
1335 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1337 fputs ("(duplicate, not actually replacing)", dump_file
);
1338 stmt_to_print
= c
->cand_stmt
;
1343 gimple_stmt_iterator gsi
= gsi_for_stmt (c
->cand_stmt
);
1344 gimple_assign_set_rhs_with_ops (&gsi
, code
, basis_name
, bump_tree
);
1345 update_stmt (gsi_stmt (gsi
));
1346 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1347 stmt_to_print
= gsi_stmt (gsi
);
1351 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1353 fputs ("With: ", dump_file
);
1354 print_gimple_stmt (dump_file
, stmt_to_print
, 0, 0);
1355 fputs ("\n", dump_file
);
1359 /* Replace candidate C, each sibling of candidate C, and each
1360 dependent of candidate C with an add or subtract. Note that we
1361 only operate on CAND_MULTs with known strides, so we will never
1362 generate a POINTER_PLUS_EXPR. Each candidate X = (B + i) * S is
1363 replaced by X = Y + ((i - i') * S), as described in the module
1364 commentary. The folded value ((i - i') * S) is referred to here
1368 replace_dependents (slsr_cand_t c
)
1370 enum tree_code cand_code
= gimple_assign_rhs_code (c
->cand_stmt
);
1372 /* It is not useful to replace casts, copies, or adds of an SSA name
1373 and a constant. Also skip candidates that have already been
1374 replaced under another interpretation. */
1375 if (cand_code
!= MODIFY_EXPR
1376 && cand_code
!= NOP_EXPR
1377 && c
->kind
== CAND_MULT
1378 && !cand_already_replaced (c
))
1379 replace_dependent (c
, cand_code
);
1382 replace_dependents (lookup_cand (c
->sibling
));
1385 replace_dependents (lookup_cand (c
->dependent
));
1388 /* Analyze costs of related candidates in the candidate vector,
1389 and make beneficial replacements. */
1392 analyze_candidates_and_replace (void)
1397 /* Each candidate that has a null basis and a non-null
1398 dependent is the root of a tree of related statements.
1399 Analyze each tree to determine a subset of those
1400 statements that can be replaced with maximum benefit. */
1401 FOR_EACH_VEC_ELT (slsr_cand_t
, cand_vec
, i
, c
)
1403 slsr_cand_t first_dep
;
1405 if (c
->basis
!= 0 || c
->dependent
== 0)
1408 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1409 fprintf (dump_file
, "\nProcessing dependency tree rooted at %d.\n",
1412 first_dep
= lookup_cand (c
->dependent
);
1414 /* If the common stride of all related candidates is a
1415 known constant, and none of these has a phi-dependence,
1416 then all replacements are considered profitable.
1417 Each replaces a multiply by a single add, with the
1418 possibility that a feeding add also goes dead as a
1420 if (unconditional_cands_with_known_stride_p (c
))
1421 replace_dependents (first_dep
);
1423 /* TODO: When the stride is an SSA name, it may still be
1424 profitable to replace some or all of the dependent
1425 candidates, depending on whether the introduced increments
1426 can be reused, or are less expensive to calculate than
1427 the replaced statements. */
1429 /* TODO: Strength-reduce data references with implicit
1430 multiplication in their addressing expressions. */
1432 /* TODO: When conditional increments occur so that a
1433 candidate is dependent upon a phi-basis, the cost of
1434 introducing a temporary must be accounted for. */
1439 execute_strength_reduction (void)
1441 struct dom_walk_data walk_data
;
1443 /* Create the obstack where candidates will reside. */
1444 gcc_obstack_init (&cand_obstack
);
1446 /* Allocate the candidate vector. */
1447 cand_vec
= VEC_alloc (slsr_cand_t
, heap
, 128);
1449 /* Allocate the mapping from statements to candidate indices. */
1450 stmt_cand_map
= pointer_map_create ();
1452 /* Create the obstack where candidate chains will reside. */
1453 gcc_obstack_init (&chain_obstack
);
1455 /* Allocate the mapping from base names to candidate chains. */
1456 base_cand_map
= XNEWVEC (cand_chain_t
, num_ssa_names
);
1457 memset (base_cand_map
, 0, num_ssa_names
* sizeof (cand_chain_t
));
1459 /* Initialize the loop optimizer. We need to detect flow across
1460 back edges, and this gives us dominator information as well. */
1461 loop_optimizer_init (AVOID_CFG_MODIFICATIONS
);
1463 /* Initialize costs tables in IVOPTS. */
1464 initialize_costs ();
1466 /* Set up callbacks for the generic dominator tree walker. */
1467 walk_data
.dom_direction
= CDI_DOMINATORS
;
1468 walk_data
.initialize_block_local_data
= NULL
;
1469 walk_data
.before_dom_children
= find_candidates_in_block
;
1470 walk_data
.after_dom_children
= NULL
;
1471 walk_data
.global_data
= NULL
;
1472 walk_data
.block_local_data_size
= 0;
1473 init_walk_dominator_tree (&walk_data
);
1475 /* Walk the CFG in predominator order looking for strength reduction
1477 walk_dominator_tree (&walk_data
, ENTRY_BLOCK_PTR
);
1479 if (dump_file
&& (dump_flags
& TDF_DETAILS
))
1482 dump_cand_chains ();
1485 /* Analyze costs and make appropriate replacements. */
1486 analyze_candidates_and_replace ();
1488 /* Free resources. */
1489 fini_walk_dominator_tree (&walk_data
);
1490 loop_optimizer_finalize ();
1491 free (base_cand_map
);
1492 obstack_free (&chain_obstack
, NULL
);
1493 pointer_map_destroy (stmt_cand_map
);
1494 VEC_free (slsr_cand_t
, heap
, cand_vec
);
1495 obstack_free (&cand_obstack
, NULL
);
1502 gate_strength_reduction (void)
1504 return flag_tree_slsr
;
1507 struct gimple_opt_pass pass_strength_reduction
=
1512 gate_strength_reduction
, /* gate */
1513 execute_strength_reduction
, /* execute */
1516 0, /* static_pass_number */
1517 TV_GIMPLE_SLSR
, /* tv_id */
1518 PROP_cfg
| PROP_ssa
, /* properties_required */
1519 0, /* properties_provided */
1520 0, /* properties_destroyed */
1521 0, /* todo_flags_start */
1522 TODO_verify_ssa
/* todo_flags_finish */