1 /* Target-dependent costs for expmed.c.
2 Copyright (C) 1987-2015 Free Software Foundation, Inc.
4 This file is part of GCC.
6 GCC is free software; you can redistribute it and/or modify it under
7 the terms of the GNU General Public License as published by the Free
8 Software Foundation; either version 3, or (at your option; any later
11 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12 WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
16 You should have received a copy of the GNU General Public License
17 along with GCC; see the file COPYING3. If not see
18 <http://www.gnu.org/licenses/>. */
23 #include "insn-codes.h"
38 /* This structure holds the "cost" of a multiply sequence. The
39 "cost" field holds the total rtx_cost of every operator in the
40 synthetic multiplication sequence, hence cost(a op b) is defined
41 as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero.
42 The "latency" field holds the minimum possible latency of the
43 synthetic multiply, on a hypothetical infinitely parallel CPU.
44 This is the critical path, or the maximum height, of the expression
45 tree which is the sum of rtx_costs on the most expensive path from
46 any leaf to the root. Hence latency(a op b) is defined as zero for
47 leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise. */
50 short cost
; /* Total rtx_cost of the multiplication sequence. */
51 short latency
; /* The latency of the multiplication sequence. */
54 /* This macro is used to compare a pointer to a mult_cost against an
55 single integer "rtx_cost" value. This is equivalent to the macro
56 CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}. */
57 #define MULT_COST_LESS(X,Y) ((X)->cost < (Y) \
58 || ((X)->cost == (Y) && (X)->latency < (Y)))
60 /* This macro is used to compare two pointers to mult_costs against
61 each other. The macro returns true if X is cheaper than Y.
62 Currently, the cheaper of two mult_costs is the one with the
63 lower "cost". If "cost"s are tied, the lower latency is cheaper. */
64 #define CHEAPER_MULT_COST(X,Y) ((X)->cost < (Y)->cost \
65 || ((X)->cost == (Y)->cost \
66 && (X)->latency < (Y)->latency))
68 /* This structure records a sequence of operations.
69 `ops' is the number of operations recorded.
70 `cost' is their total cost.
71 The operations are stored in `op' and the corresponding
72 logarithms of the integer coefficients in `log'.
74 These are the operations:
76 alg_m total := multiplicand;
77 alg_shift total := total * coeff
78 alg_add_t_m2 total := total + multiplicand * coeff;
79 alg_sub_t_m2 total := total - multiplicand * coeff;
80 alg_add_factor total := total * coeff + total;
81 alg_sub_factor total := total * coeff - total;
82 alg_add_t2_m total := total * coeff + multiplicand;
83 alg_sub_t2_m total := total * coeff - multiplicand;
85 The first operand must be either alg_zero or alg_m. */
89 struct mult_cost cost
;
91 /* The size of the OP and LOG fields are not directly related to the
92 word size, but the worst-case algorithms will be if we have few
93 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
94 In that case we will generate shift-by-2, add, shift-by-2, add,...,
95 in total wordsize operations. */
96 enum alg_code op
[MAX_BITS_PER_WORD
];
97 char log
[MAX_BITS_PER_WORD
];
100 /* The entry for our multiplication cache/hash table. */
101 struct alg_hash_entry
{
102 /* The number we are multiplying by. */
103 unsigned HOST_WIDE_INT t
;
105 /* The mode in which we are multiplying something by T. */
108 /* The best multiplication algorithm for t. */
111 /* The cost of multiplication if ALG_CODE is not alg_impossible.
112 Otherwise, the cost within which multiplication by T is
114 struct mult_cost cost
;
116 /* Optimized for speed? */
120 /* The number of cache/hash entries. */
121 #if HOST_BITS_PER_WIDE_INT == 64
122 #define NUM_ALG_HASH_ENTRIES 1031
124 #define NUM_ALG_HASH_ENTRIES 307
127 #define NUM_MODE_INT \
128 (MAX_MODE_INT - MIN_MODE_INT + 1)
129 #define NUM_MODE_PARTIAL_INT \
130 (MIN_MODE_PARTIAL_INT == VOIDmode ? 0 \
131 : MAX_MODE_PARTIAL_INT - MIN_MODE_PARTIAL_INT + 1)
132 #define NUM_MODE_VECTOR_INT \
133 (MIN_MODE_VECTOR_INT == VOIDmode ? 0 \
134 : MAX_MODE_VECTOR_INT - MIN_MODE_VECTOR_INT + 1)
136 #define NUM_MODE_IP_INT (NUM_MODE_INT + NUM_MODE_PARTIAL_INT)
137 #define NUM_MODE_IPV_INT (NUM_MODE_IP_INT + NUM_MODE_VECTOR_INT)
139 struct expmed_op_cheap
{
140 bool cheap
[2][NUM_MODE_IPV_INT
];
143 struct expmed_op_costs
{
144 int cost
[2][NUM_MODE_IPV_INT
];
147 /* Target-dependent globals. */
148 struct target_expmed
{
149 /* Each entry of ALG_HASH caches alg_code for some integer. This is
150 actually a hash table. If we have a collision, that the older
151 entry is kicked out. */
152 struct alg_hash_entry x_alg_hash
[NUM_ALG_HASH_ENTRIES
];
154 /* True if x_alg_hash might already have been used. */
155 bool x_alg_hash_used_p
;
157 /* Nonzero means divides or modulus operations are relatively cheap for
158 powers of two, so don't use branches; emit the operation instead.
159 Usually, this will mean that the MD file will emit non-branch
161 struct expmed_op_cheap x_sdiv_pow2_cheap
;
162 struct expmed_op_cheap x_smod_pow2_cheap
;
164 /* Cost of various pieces of RTL. Note that some of these are indexed by
165 shift count and some by mode. */
167 struct expmed_op_costs x_add_cost
;
168 struct expmed_op_costs x_neg_cost
;
169 struct expmed_op_costs x_shift_cost
[MAX_BITS_PER_WORD
];
170 struct expmed_op_costs x_shiftadd_cost
[MAX_BITS_PER_WORD
];
171 struct expmed_op_costs x_shiftsub0_cost
[MAX_BITS_PER_WORD
];
172 struct expmed_op_costs x_shiftsub1_cost
[MAX_BITS_PER_WORD
];
173 struct expmed_op_costs x_mul_cost
;
174 struct expmed_op_costs x_sdiv_cost
;
175 struct expmed_op_costs x_udiv_cost
;
176 int x_mul_widen_cost
[2][NUM_MODE_INT
];
177 int x_mul_highpart_cost
[2][NUM_MODE_INT
];
179 /* Conversion costs are only defined between two scalar integer modes
180 of different sizes. The first machine mode is the destination mode,
181 and the second is the source mode. */
182 int x_convert_cost
[2][NUM_MODE_IP_INT
][NUM_MODE_IP_INT
];
185 extern struct target_expmed default_target_expmed
;
186 #if SWITCHABLE_TARGET
187 extern struct target_expmed
*this_target_expmed
;
189 #define this_target_expmed (&default_target_expmed)
192 /* Return a pointer to the alg_hash_entry at IDX. */
194 static inline struct alg_hash_entry
*
195 alg_hash_entry_ptr (int idx
)
197 return &this_target_expmed
->x_alg_hash
[idx
];
200 /* Return true if the x_alg_hash field might have been used. */
203 alg_hash_used_p (void)
205 return this_target_expmed
->x_alg_hash_used_p
;
208 /* Set whether the x_alg_hash field might have been used. */
211 set_alg_hash_used_p (bool usedp
)
213 this_target_expmed
->x_alg_hash_used_p
= usedp
;
216 /* Compute an index into the cost arrays by mode class. */
219 expmed_mode_index (machine_mode mode
)
221 switch (GET_MODE_CLASS (mode
))
224 return mode
- MIN_MODE_INT
;
225 case MODE_PARTIAL_INT
:
226 /* If there are no partial integer modes, help the compiler
227 to figure out this will never happen. See PR59934. */
228 if (MIN_MODE_PARTIAL_INT
!= VOIDmode
)
229 return mode
- MIN_MODE_PARTIAL_INT
+ NUM_MODE_INT
;
231 case MODE_VECTOR_INT
:
232 /* If there are no vector integer modes, help the compiler
233 to figure out this will never happen. See PR59934. */
234 if (MIN_MODE_VECTOR_INT
!= VOIDmode
)
235 return mode
- MIN_MODE_VECTOR_INT
+ NUM_MODE_IP_INT
;
243 /* Return a pointer to a boolean contained in EOC indicating whether
244 a particular operation performed in MODE is cheap when optimizing
248 expmed_op_cheap_ptr (struct expmed_op_cheap
*eoc
, bool speed
,
251 int idx
= expmed_mode_index (mode
);
252 return &eoc
->cheap
[speed
][idx
];
255 /* Return a pointer to a cost contained in COSTS when a particular
256 operation is performed in MODE when optimizing for SPEED. */
259 expmed_op_cost_ptr (struct expmed_op_costs
*costs
, bool speed
,
262 int idx
= expmed_mode_index (mode
);
263 return &costs
->cost
[speed
][idx
];
266 /* Subroutine of {set_,}sdiv_pow2_cheap. Not to be used otherwise. */
269 sdiv_pow2_cheap_ptr (bool speed
, machine_mode mode
)
271 return expmed_op_cheap_ptr (&this_target_expmed
->x_sdiv_pow2_cheap
,
275 /* Set whether a signed division by a power of 2 is cheap in MODE
276 when optimizing for SPEED. */
279 set_sdiv_pow2_cheap (bool speed
, machine_mode mode
, bool cheap_p
)
281 *sdiv_pow2_cheap_ptr (speed
, mode
) = cheap_p
;
284 /* Return whether a signed division by a power of 2 is cheap in MODE
285 when optimizing for SPEED. */
288 sdiv_pow2_cheap (bool speed
, machine_mode mode
)
290 return *sdiv_pow2_cheap_ptr (speed
, mode
);
293 /* Subroutine of {set_,}smod_pow2_cheap. Not to be used otherwise. */
296 smod_pow2_cheap_ptr (bool speed
, machine_mode mode
)
298 return expmed_op_cheap_ptr (&this_target_expmed
->x_smod_pow2_cheap
,
302 /* Set whether a signed modulo by a power of 2 is CHEAP in MODE when
303 optimizing for SPEED. */
306 set_smod_pow2_cheap (bool speed
, machine_mode mode
, bool cheap
)
308 *smod_pow2_cheap_ptr (speed
, mode
) = cheap
;
311 /* Return whether a signed modulo by a power of 2 is cheap in MODE
312 when optimizing for SPEED. */
315 smod_pow2_cheap (bool speed
, machine_mode mode
)
317 return *smod_pow2_cheap_ptr (speed
, mode
);
320 /* Subroutine of {set_,}zero_cost. Not to be used otherwise. */
323 zero_cost_ptr (bool speed
)
325 return &this_target_expmed
->x_zero_cost
[speed
];
328 /* Set the COST of loading zero when optimizing for SPEED. */
331 set_zero_cost (bool speed
, int cost
)
333 *zero_cost_ptr (speed
) = cost
;
336 /* Return the COST of loading zero when optimizing for SPEED. */
339 zero_cost (bool speed
)
341 return *zero_cost_ptr (speed
);
344 /* Subroutine of {set_,}add_cost. Not to be used otherwise. */
347 add_cost_ptr (bool speed
, machine_mode mode
)
349 return expmed_op_cost_ptr (&this_target_expmed
->x_add_cost
, speed
, mode
);
352 /* Set the COST of computing an add in MODE when optimizing for SPEED. */
355 set_add_cost (bool speed
, machine_mode mode
, int cost
)
357 *add_cost_ptr (speed
, mode
) = cost
;
360 /* Return the cost of computing an add in MODE when optimizing for SPEED. */
363 add_cost (bool speed
, machine_mode mode
)
365 return *add_cost_ptr (speed
, mode
);
368 /* Subroutine of {set_,}neg_cost. Not to be used otherwise. */
371 neg_cost_ptr (bool speed
, machine_mode mode
)
373 return expmed_op_cost_ptr (&this_target_expmed
->x_neg_cost
, speed
, mode
);
376 /* Set the COST of computing a negation in MODE when optimizing for SPEED. */
379 set_neg_cost (bool speed
, machine_mode mode
, int cost
)
381 *neg_cost_ptr (speed
, mode
) = cost
;
384 /* Return the cost of computing a negation in MODE when optimizing for
388 neg_cost (bool speed
, machine_mode mode
)
390 return *neg_cost_ptr (speed
, mode
);
393 /* Subroutine of {set_,}shift_cost. Not to be used otherwise. */
396 shift_cost_ptr (bool speed
, machine_mode mode
, int bits
)
398 return expmed_op_cost_ptr (&this_target_expmed
->x_shift_cost
[bits
],
402 /* Set the COST of doing a shift in MODE by BITS when optimizing for SPEED. */
405 set_shift_cost (bool speed
, machine_mode mode
, int bits
, int cost
)
407 *shift_cost_ptr (speed
, mode
, bits
) = cost
;
410 /* Return the cost of doing a shift in MODE by BITS when optimizing for
414 shift_cost (bool speed
, machine_mode mode
, int bits
)
416 return *shift_cost_ptr (speed
, mode
, bits
);
419 /* Subroutine of {set_,}shiftadd_cost. Not to be used otherwise. */
422 shiftadd_cost_ptr (bool speed
, machine_mode mode
, int bits
)
424 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftadd_cost
[bits
],
428 /* Set the COST of doing a shift in MODE by BITS followed by an add when
429 optimizing for SPEED. */
432 set_shiftadd_cost (bool speed
, machine_mode mode
, int bits
, int cost
)
434 *shiftadd_cost_ptr (speed
, mode
, bits
) = cost
;
437 /* Return the cost of doing a shift in MODE by BITS followed by an add
438 when optimizing for SPEED. */
441 shiftadd_cost (bool speed
, machine_mode mode
, int bits
)
443 return *shiftadd_cost_ptr (speed
, mode
, bits
);
446 /* Subroutine of {set_,}shiftsub0_cost. Not to be used otherwise. */
449 shiftsub0_cost_ptr (bool speed
, machine_mode mode
, int bits
)
451 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftsub0_cost
[bits
],
455 /* Set the COST of doing a shift in MODE by BITS and then subtracting a
456 value when optimizing for SPEED. */
459 set_shiftsub0_cost (bool speed
, machine_mode mode
, int bits
, int cost
)
461 *shiftsub0_cost_ptr (speed
, mode
, bits
) = cost
;
464 /* Return the cost of doing a shift in MODE by BITS and then subtracting
465 a value when optimizing for SPEED. */
468 shiftsub0_cost (bool speed
, machine_mode mode
, int bits
)
470 return *shiftsub0_cost_ptr (speed
, mode
, bits
);
473 /* Subroutine of {set_,}shiftsub1_cost. Not to be used otherwise. */
476 shiftsub1_cost_ptr (bool speed
, machine_mode mode
, int bits
)
478 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftsub1_cost
[bits
],
482 /* Set the COST of subtracting a shift in MODE by BITS from a value when
483 optimizing for SPEED. */
486 set_shiftsub1_cost (bool speed
, machine_mode mode
, int bits
, int cost
)
488 *shiftsub1_cost_ptr (speed
, mode
, bits
) = cost
;
491 /* Return the cost of subtracting a shift in MODE by BITS from a value
492 when optimizing for SPEED. */
495 shiftsub1_cost (bool speed
, machine_mode mode
, int bits
)
497 return *shiftsub1_cost_ptr (speed
, mode
, bits
);
500 /* Subroutine of {set_,}mul_cost. Not to be used otherwise. */
503 mul_cost_ptr (bool speed
, machine_mode mode
)
505 return expmed_op_cost_ptr (&this_target_expmed
->x_mul_cost
, speed
, mode
);
508 /* Set the COST of doing a multiplication in MODE when optimizing for
512 set_mul_cost (bool speed
, machine_mode mode
, int cost
)
514 *mul_cost_ptr (speed
, mode
) = cost
;
517 /* Return the cost of doing a multiplication in MODE when optimizing
521 mul_cost (bool speed
, machine_mode mode
)
523 return *mul_cost_ptr (speed
, mode
);
526 /* Subroutine of {set_,}sdiv_cost. Not to be used otherwise. */
529 sdiv_cost_ptr (bool speed
, machine_mode mode
)
531 return expmed_op_cost_ptr (&this_target_expmed
->x_sdiv_cost
, speed
, mode
);
534 /* Set the COST of doing a signed division in MODE when optimizing
538 set_sdiv_cost (bool speed
, machine_mode mode
, int cost
)
540 *sdiv_cost_ptr (speed
, mode
) = cost
;
543 /* Return the cost of doing a signed division in MODE when optimizing
547 sdiv_cost (bool speed
, machine_mode mode
)
549 return *sdiv_cost_ptr (speed
, mode
);
552 /* Subroutine of {set_,}udiv_cost. Not to be used otherwise. */
555 udiv_cost_ptr (bool speed
, machine_mode mode
)
557 return expmed_op_cost_ptr (&this_target_expmed
->x_udiv_cost
, speed
, mode
);
560 /* Set the COST of doing an unsigned division in MODE when optimizing
564 set_udiv_cost (bool speed
, machine_mode mode
, int cost
)
566 *udiv_cost_ptr (speed
, mode
) = cost
;
569 /* Return the cost of doing an unsigned division in MODE when
570 optimizing for SPEED. */
573 udiv_cost (bool speed
, machine_mode mode
)
575 return *udiv_cost_ptr (speed
, mode
);
578 /* Subroutine of {set_,}mul_widen_cost. Not to be used otherwise. */
581 mul_widen_cost_ptr (bool speed
, machine_mode mode
)
583 gcc_assert (GET_MODE_CLASS (mode
) == MODE_INT
);
585 return &this_target_expmed
->x_mul_widen_cost
[speed
][mode
- MIN_MODE_INT
];
588 /* Set the COST for computing a widening multiplication in MODE when
589 optimizing for SPEED. */
592 set_mul_widen_cost (bool speed
, machine_mode mode
, int cost
)
594 *mul_widen_cost_ptr (speed
, mode
) = cost
;
597 /* Return the cost for computing a widening multiplication in MODE when
598 optimizing for SPEED. */
601 mul_widen_cost (bool speed
, machine_mode mode
)
603 return *mul_widen_cost_ptr (speed
, mode
);
606 /* Subroutine of {set_,}mul_highpart_cost. Not to be used otherwise. */
609 mul_highpart_cost_ptr (bool speed
, machine_mode mode
)
611 gcc_assert (GET_MODE_CLASS (mode
) == MODE_INT
);
613 return &this_target_expmed
->x_mul_highpart_cost
[speed
][mode
- MIN_MODE_INT
];
616 /* Set the COST for computing the high part of a multiplication in MODE
617 when optimizing for SPEED. */
620 set_mul_highpart_cost (bool speed
, machine_mode mode
, int cost
)
622 *mul_highpart_cost_ptr (speed
, mode
) = cost
;
625 /* Return the cost for computing the high part of a multiplication in MODE
626 when optimizing for SPEED. */
629 mul_highpart_cost (bool speed
, machine_mode mode
)
631 return *mul_highpart_cost_ptr (speed
, mode
);
634 /* Subroutine of {set_,}convert_cost. Not to be used otherwise. */
637 convert_cost_ptr (machine_mode to_mode
, machine_mode from_mode
,
640 int to_idx
= expmed_mode_index (to_mode
);
641 int from_idx
= expmed_mode_index (from_mode
);
643 gcc_assert (IN_RANGE (to_idx
, 0, NUM_MODE_IP_INT
- 1));
644 gcc_assert (IN_RANGE (from_idx
, 0, NUM_MODE_IP_INT
- 1));
646 return &this_target_expmed
->x_convert_cost
[speed
][to_idx
][from_idx
];
649 /* Set the COST for converting from FROM_MODE to TO_MODE when optimizing
653 set_convert_cost (machine_mode to_mode
, machine_mode from_mode
,
654 bool speed
, int cost
)
656 *convert_cost_ptr (to_mode
, from_mode
, speed
) = cost
;
659 /* Return the cost for converting from FROM_MODE to TO_MODE when optimizing
663 convert_cost (machine_mode to_mode
, machine_mode from_mode
,
666 return *convert_cost_ptr (to_mode
, from_mode
, speed
);
669 extern int mult_by_coeff_cost (HOST_WIDE_INT
, machine_mode
, bool);
670 extern rtx
emit_cstore (rtx target
, enum insn_code icode
, enum rtx_code code
,
671 enum machine_mode mode
, enum machine_mode compare_mode
,
672 int unsignedp
, rtx x
, rtx y
, int normalizep
,
673 enum machine_mode target_mode
);
675 /* Arguments MODE, RTX: return an rtx for the negation of that value.
677 extern rtx
negate_rtx (machine_mode
, rtx
);
679 /* Expand a logical AND operation. */
680 extern rtx
expand_and (machine_mode
, rtx
, rtx
, rtx
);
682 /* Emit a store-flag operation. */
683 extern rtx
emit_store_flag (rtx
, enum rtx_code
, rtx
, rtx
, machine_mode
,
686 /* Like emit_store_flag, but always succeeds. */
687 extern rtx
emit_store_flag_force (rtx
, enum rtx_code
, rtx
, rtx
,
688 machine_mode
, int, int);
690 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
691 replace division by D, and put the least significant N bits of the result
692 in *MULTIPLIER_PTR and return the most significant bit. */
693 extern unsigned HOST_WIDE_INT
choose_multiplier (unsigned HOST_WIDE_INT
, int,
694 int, unsigned HOST_WIDE_INT
*,
698 extern rtx
expand_variable_shift (enum tree_code
, machine_mode
,
699 rtx
, tree
, rtx
, int);
700 extern rtx
expand_shift (enum tree_code
, machine_mode
, rtx
, int, rtx
,
702 extern rtx
expand_divmod (int, enum tree_code
, machine_mode
, rtx
, rtx
,
706 extern void store_bit_field (rtx
, unsigned HOST_WIDE_INT
,
707 unsigned HOST_WIDE_INT
,
708 unsigned HOST_WIDE_INT
,
709 unsigned HOST_WIDE_INT
,
711 extern rtx
extract_bit_field (rtx
, unsigned HOST_WIDE_INT
,
712 unsigned HOST_WIDE_INT
, int, rtx
,
713 machine_mode
, machine_mode
);
714 extern rtx
extract_low_bits (machine_mode
, machine_mode
, rtx
);
715 extern rtx
expand_mult (machine_mode
, rtx
, rtx
, rtx
, int);
716 extern rtx
expand_mult_highpart_adjust (machine_mode
, rtx
, rtx
, rtx
, rtx
, int);