1 /* Target-dependent costs for expmed.c.
2 Copyright (C) 1987-2014 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/>. */
36 /* This structure holds the "cost" of a multiply sequence. The
37 "cost" field holds the total rtx_cost of every operator in the
38 synthetic multiplication sequence, hence cost(a op b) is defined
39 as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero.
40 The "latency" field holds the minimum possible latency of the
41 synthetic multiply, on a hypothetical infinitely parallel CPU.
42 This is the critical path, or the maximum height, of the expression
43 tree which is the sum of rtx_costs on the most expensive path from
44 any leaf to the root. Hence latency(a op b) is defined as zero for
45 leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise. */
48 short cost
; /* Total rtx_cost of the multiplication sequence. */
49 short latency
; /* The latency of the multiplication sequence. */
52 /* This macro is used to compare a pointer to a mult_cost against an
53 single integer "rtx_cost" value. This is equivalent to the macro
54 CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}. */
55 #define MULT_COST_LESS(X,Y) ((X)->cost < (Y) \
56 || ((X)->cost == (Y) && (X)->latency < (Y)))
58 /* This macro is used to compare two pointers to mult_costs against
59 each other. The macro returns true if X is cheaper than Y.
60 Currently, the cheaper of two mult_costs is the one with the
61 lower "cost". If "cost"s are tied, the lower latency is cheaper. */
62 #define CHEAPER_MULT_COST(X,Y) ((X)->cost < (Y)->cost \
63 || ((X)->cost == (Y)->cost \
64 && (X)->latency < (Y)->latency))
66 /* This structure records a sequence of operations.
67 `ops' is the number of operations recorded.
68 `cost' is their total cost.
69 The operations are stored in `op' and the corresponding
70 logarithms of the integer coefficients in `log'.
72 These are the operations:
74 alg_m total := multiplicand;
75 alg_shift total := total * coeff
76 alg_add_t_m2 total := total + multiplicand * coeff;
77 alg_sub_t_m2 total := total - multiplicand * coeff;
78 alg_add_factor total := total * coeff + total;
79 alg_sub_factor total := total * coeff - total;
80 alg_add_t2_m total := total * coeff + multiplicand;
81 alg_sub_t2_m total := total * coeff - multiplicand;
83 The first operand must be either alg_zero or alg_m. */
87 struct mult_cost cost
;
89 /* The size of the OP and LOG fields are not directly related to the
90 word size, but the worst-case algorithms will be if we have few
91 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
92 In that case we will generate shift-by-2, add, shift-by-2, add,...,
93 in total wordsize operations. */
94 enum alg_code op
[MAX_BITS_PER_WORD
];
95 char log
[MAX_BITS_PER_WORD
];
98 /* The entry for our multiplication cache/hash table. */
99 struct alg_hash_entry
{
100 /* The number we are multiplying by. */
101 unsigned HOST_WIDE_INT t
;
103 /* The mode in which we are multiplying something by T. */
104 enum machine_mode mode
;
106 /* The best multiplication algorithm for t. */
109 /* The cost of multiplication if ALG_CODE is not alg_impossible.
110 Otherwise, the cost within which multiplication by T is
112 struct mult_cost cost
;
114 /* Optimized for speed? */
118 /* The number of cache/hash entries. */
119 #if HOST_BITS_PER_WIDE_INT == 64
120 #define NUM_ALG_HASH_ENTRIES 1031
122 #define NUM_ALG_HASH_ENTRIES 307
125 #define NUM_MODE_INT \
126 (MAX_MODE_INT - MIN_MODE_INT + 1)
127 #define NUM_MODE_PARTIAL_INT \
128 (MIN_MODE_PARTIAL_INT == VOIDmode ? 0 \
129 : MAX_MODE_PARTIAL_INT - MIN_MODE_PARTIAL_INT + 1)
130 #define NUM_MODE_VECTOR_INT \
131 (MIN_MODE_VECTOR_INT == VOIDmode ? 0 \
132 : MAX_MODE_VECTOR_INT - MIN_MODE_VECTOR_INT + 1)
134 #define NUM_MODE_IP_INT (NUM_MODE_INT + NUM_MODE_PARTIAL_INT)
135 #define NUM_MODE_IPV_INT (NUM_MODE_IP_INT + NUM_MODE_VECTOR_INT)
137 struct expmed_op_cheap
{
138 bool cheap
[2][NUM_MODE_IPV_INT
];
141 struct expmed_op_costs
{
142 int cost
[2][NUM_MODE_IPV_INT
];
145 /* Target-dependent globals. */
146 struct target_expmed
{
147 /* Each entry of ALG_HASH caches alg_code for some integer. This is
148 actually a hash table. If we have a collision, that the older
149 entry is kicked out. */
150 struct alg_hash_entry x_alg_hash
[NUM_ALG_HASH_ENTRIES
];
152 /* True if x_alg_hash might already have been used. */
153 bool x_alg_hash_used_p
;
155 /* Nonzero means divides or modulus operations are relatively cheap for
156 powers of two, so don't use branches; emit the operation instead.
157 Usually, this will mean that the MD file will emit non-branch
159 struct expmed_op_cheap x_sdiv_pow2_cheap
;
160 struct expmed_op_cheap x_smod_pow2_cheap
;
162 /* Cost of various pieces of RTL. Note that some of these are indexed by
163 shift count and some by mode. */
165 struct expmed_op_costs x_add_cost
;
166 struct expmed_op_costs x_neg_cost
;
167 struct expmed_op_costs x_shift_cost
[MAX_BITS_PER_WORD
];
168 struct expmed_op_costs x_shiftadd_cost
[MAX_BITS_PER_WORD
];
169 struct expmed_op_costs x_shiftsub0_cost
[MAX_BITS_PER_WORD
];
170 struct expmed_op_costs x_shiftsub1_cost
[MAX_BITS_PER_WORD
];
171 struct expmed_op_costs x_mul_cost
;
172 struct expmed_op_costs x_sdiv_cost
;
173 struct expmed_op_costs x_udiv_cost
;
174 int x_mul_widen_cost
[2][NUM_MODE_INT
];
175 int x_mul_highpart_cost
[2][NUM_MODE_INT
];
177 /* Conversion costs are only defined between two scalar integer modes
178 of different sizes. The first machine mode is the destination mode,
179 and the second is the source mode. */
180 int x_convert_cost
[2][NUM_MODE_IP_INT
][NUM_MODE_IP_INT
];
183 extern struct target_expmed default_target_expmed
;
184 #if SWITCHABLE_TARGET
185 extern struct target_expmed
*this_target_expmed
;
187 #define this_target_expmed (&default_target_expmed)
190 /* Return a pointer to the alg_hash_entry at IDX. */
192 static inline struct alg_hash_entry
*
193 alg_hash_entry_ptr (int idx
)
195 return &this_target_expmed
->x_alg_hash
[idx
];
198 /* Return true if the x_alg_hash field might have been used. */
201 alg_hash_used_p (void)
203 return this_target_expmed
->x_alg_hash_used_p
;
206 /* Set whether the x_alg_hash field might have been used. */
209 set_alg_hash_used_p (bool usedp
)
211 this_target_expmed
->x_alg_hash_used_p
= usedp
;
214 /* Compute an index into the cost arrays by mode class. */
217 expmed_mode_index (enum machine_mode mode
)
219 switch (GET_MODE_CLASS (mode
))
222 return mode
- MIN_MODE_INT
;
223 case MODE_PARTIAL_INT
:
224 /* If there are no partial integer modes, help the compiler
225 to figure out this will never happen. See PR59934. */
226 if (MIN_MODE_PARTIAL_INT
!= VOIDmode
)
227 return mode
- MIN_MODE_PARTIAL_INT
+ NUM_MODE_INT
;
229 case MODE_VECTOR_INT
:
230 /* If there are no vector integer modes, help the compiler
231 to figure out this will never happen. See PR59934. */
232 if (MIN_MODE_VECTOR_INT
!= VOIDmode
)
233 return mode
- MIN_MODE_VECTOR_INT
+ NUM_MODE_IP_INT
;
241 /* Return a pointer to a boolean contained in EOC indicating whether
242 a particular operation performed in MODE is cheap when optimizing
246 expmed_op_cheap_ptr (struct expmed_op_cheap
*eoc
, bool speed
,
247 enum machine_mode mode
)
249 int idx
= expmed_mode_index (mode
);
250 return &eoc
->cheap
[speed
][idx
];
253 /* Return a pointer to a cost contained in COSTS when a particular
254 operation is performed in MODE when optimizing for SPEED. */
257 expmed_op_cost_ptr (struct expmed_op_costs
*costs
, bool speed
,
258 enum machine_mode mode
)
260 int idx
= expmed_mode_index (mode
);
261 return &costs
->cost
[speed
][idx
];
264 /* Subroutine of {set_,}sdiv_pow2_cheap. Not to be used otherwise. */
267 sdiv_pow2_cheap_ptr (bool speed
, enum machine_mode mode
)
269 return expmed_op_cheap_ptr (&this_target_expmed
->x_sdiv_pow2_cheap
,
273 /* Set whether a signed division by a power of 2 is cheap in MODE
274 when optimizing for SPEED. */
277 set_sdiv_pow2_cheap (bool speed
, enum machine_mode mode
, bool cheap_p
)
279 *sdiv_pow2_cheap_ptr (speed
, mode
) = cheap_p
;
282 /* Return whether a signed division by a power of 2 is cheap in MODE
283 when optimizing for SPEED. */
286 sdiv_pow2_cheap (bool speed
, enum machine_mode mode
)
288 return *sdiv_pow2_cheap_ptr (speed
, mode
);
291 /* Subroutine of {set_,}smod_pow2_cheap. Not to be used otherwise. */
294 smod_pow2_cheap_ptr (bool speed
, enum machine_mode mode
)
296 return expmed_op_cheap_ptr (&this_target_expmed
->x_smod_pow2_cheap
,
300 /* Set whether a signed modulo by a power of 2 is CHEAP in MODE when
301 optimizing for SPEED. */
304 set_smod_pow2_cheap (bool speed
, enum machine_mode mode
, bool cheap
)
306 *smod_pow2_cheap_ptr (speed
, mode
) = cheap
;
309 /* Return whether a signed modulo by a power of 2 is cheap in MODE
310 when optimizing for SPEED. */
313 smod_pow2_cheap (bool speed
, enum machine_mode mode
)
315 return *smod_pow2_cheap_ptr (speed
, mode
);
318 /* Subroutine of {set_,}zero_cost. Not to be used otherwise. */
321 zero_cost_ptr (bool speed
)
323 return &this_target_expmed
->x_zero_cost
[speed
];
326 /* Set the COST of loading zero when optimizing for SPEED. */
329 set_zero_cost (bool speed
, int cost
)
331 *zero_cost_ptr (speed
) = cost
;
334 /* Return the COST of loading zero when optimizing for SPEED. */
337 zero_cost (bool speed
)
339 return *zero_cost_ptr (speed
);
342 /* Subroutine of {set_,}add_cost. Not to be used otherwise. */
345 add_cost_ptr (bool speed
, enum machine_mode mode
)
347 return expmed_op_cost_ptr (&this_target_expmed
->x_add_cost
, speed
, mode
);
350 /* Set the COST of computing an add in MODE when optimizing for SPEED. */
353 set_add_cost (bool speed
, enum machine_mode mode
, int cost
)
355 *add_cost_ptr (speed
, mode
) = cost
;
358 /* Return the cost of computing an add in MODE when optimizing for SPEED. */
361 add_cost (bool speed
, enum machine_mode mode
)
363 return *add_cost_ptr (speed
, mode
);
366 /* Subroutine of {set_,}neg_cost. Not to be used otherwise. */
369 neg_cost_ptr (bool speed
, enum machine_mode mode
)
371 return expmed_op_cost_ptr (&this_target_expmed
->x_neg_cost
, speed
, mode
);
374 /* Set the COST of computing a negation in MODE when optimizing for SPEED. */
377 set_neg_cost (bool speed
, enum machine_mode mode
, int cost
)
379 *neg_cost_ptr (speed
, mode
) = cost
;
382 /* Return the cost of computing a negation in MODE when optimizing for
386 neg_cost (bool speed
, enum machine_mode mode
)
388 return *neg_cost_ptr (speed
, mode
);
391 /* Subroutine of {set_,}shift_cost. Not to be used otherwise. */
394 shift_cost_ptr (bool speed
, enum machine_mode mode
, int bits
)
396 return expmed_op_cost_ptr (&this_target_expmed
->x_shift_cost
[bits
],
400 /* Set the COST of doing a shift in MODE by BITS when optimizing for SPEED. */
403 set_shift_cost (bool speed
, enum machine_mode mode
, int bits
, int cost
)
405 *shift_cost_ptr (speed
, mode
, bits
) = cost
;
408 /* Return the cost of doing a shift in MODE by BITS when optimizing for
412 shift_cost (bool speed
, enum machine_mode mode
, int bits
)
414 return *shift_cost_ptr (speed
, mode
, bits
);
417 /* Subroutine of {set_,}shiftadd_cost. Not to be used otherwise. */
420 shiftadd_cost_ptr (bool speed
, enum machine_mode mode
, int bits
)
422 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftadd_cost
[bits
],
426 /* Set the COST of doing a shift in MODE by BITS followed by an add when
427 optimizing for SPEED. */
430 set_shiftadd_cost (bool speed
, enum machine_mode mode
, int bits
, int cost
)
432 *shiftadd_cost_ptr (speed
, mode
, bits
) = cost
;
435 /* Return the cost of doing a shift in MODE by BITS followed by an add
436 when optimizing for SPEED. */
439 shiftadd_cost (bool speed
, enum machine_mode mode
, int bits
)
441 return *shiftadd_cost_ptr (speed
, mode
, bits
);
444 /* Subroutine of {set_,}shiftsub0_cost. Not to be used otherwise. */
447 shiftsub0_cost_ptr (bool speed
, enum machine_mode mode
, int bits
)
449 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftsub0_cost
[bits
],
453 /* Set the COST of doing a shift in MODE by BITS and then subtracting a
454 value when optimizing for SPEED. */
457 set_shiftsub0_cost (bool speed
, enum machine_mode mode
, int bits
, int cost
)
459 *shiftsub0_cost_ptr (speed
, mode
, bits
) = cost
;
462 /* Return the cost of doing a shift in MODE by BITS and then subtracting
463 a value when optimizing for SPEED. */
466 shiftsub0_cost (bool speed
, enum machine_mode mode
, int bits
)
468 return *shiftsub0_cost_ptr (speed
, mode
, bits
);
471 /* Subroutine of {set_,}shiftsub1_cost. Not to be used otherwise. */
474 shiftsub1_cost_ptr (bool speed
, enum machine_mode mode
, int bits
)
476 return expmed_op_cost_ptr (&this_target_expmed
->x_shiftsub1_cost
[bits
],
480 /* Set the COST of subtracting a shift in MODE by BITS from a value when
481 optimizing for SPEED. */
484 set_shiftsub1_cost (bool speed
, enum machine_mode mode
, int bits
, int cost
)
486 *shiftsub1_cost_ptr (speed
, mode
, bits
) = cost
;
489 /* Return the cost of subtracting a shift in MODE by BITS from a value
490 when optimizing for SPEED. */
493 shiftsub1_cost (bool speed
, enum machine_mode mode
, int bits
)
495 return *shiftsub1_cost_ptr (speed
, mode
, bits
);
498 /* Subroutine of {set_,}mul_cost. Not to be used otherwise. */
501 mul_cost_ptr (bool speed
, enum machine_mode mode
)
503 return expmed_op_cost_ptr (&this_target_expmed
->x_mul_cost
, speed
, mode
);
506 /* Set the COST of doing a multiplication in MODE when optimizing for
510 set_mul_cost (bool speed
, enum machine_mode mode
, int cost
)
512 *mul_cost_ptr (speed
, mode
) = cost
;
515 /* Return the cost of doing a multiplication in MODE when optimizing
519 mul_cost (bool speed
, enum machine_mode mode
)
521 return *mul_cost_ptr (speed
, mode
);
524 /* Subroutine of {set_,}sdiv_cost. Not to be used otherwise. */
527 sdiv_cost_ptr (bool speed
, enum machine_mode mode
)
529 return expmed_op_cost_ptr (&this_target_expmed
->x_sdiv_cost
, speed
, mode
);
532 /* Set the COST of doing a signed division in MODE when optimizing
536 set_sdiv_cost (bool speed
, enum machine_mode mode
, int cost
)
538 *sdiv_cost_ptr (speed
, mode
) = cost
;
541 /* Return the cost of doing a signed division in MODE when optimizing
545 sdiv_cost (bool speed
, enum machine_mode mode
)
547 return *sdiv_cost_ptr (speed
, mode
);
550 /* Subroutine of {set_,}udiv_cost. Not to be used otherwise. */
553 udiv_cost_ptr (bool speed
, enum machine_mode mode
)
555 return expmed_op_cost_ptr (&this_target_expmed
->x_udiv_cost
, speed
, mode
);
558 /* Set the COST of doing an unsigned division in MODE when optimizing
562 set_udiv_cost (bool speed
, enum machine_mode mode
, int cost
)
564 *udiv_cost_ptr (speed
, mode
) = cost
;
567 /* Return the cost of doing an unsigned division in MODE when
568 optimizing for SPEED. */
571 udiv_cost (bool speed
, enum machine_mode mode
)
573 return *udiv_cost_ptr (speed
, mode
);
576 /* Subroutine of {set_,}mul_widen_cost. Not to be used otherwise. */
579 mul_widen_cost_ptr (bool speed
, enum machine_mode mode
)
581 gcc_assert (GET_MODE_CLASS (mode
) == MODE_INT
);
583 return &this_target_expmed
->x_mul_widen_cost
[speed
][mode
- MIN_MODE_INT
];
586 /* Set the COST for computing a widening multiplication in MODE when
587 optimizing for SPEED. */
590 set_mul_widen_cost (bool speed
, enum machine_mode mode
, int cost
)
592 *mul_widen_cost_ptr (speed
, mode
) = cost
;
595 /* Return the cost for computing a widening multiplication in MODE when
596 optimizing for SPEED. */
599 mul_widen_cost (bool speed
, enum machine_mode mode
)
601 return *mul_widen_cost_ptr (speed
, mode
);
604 /* Subroutine of {set_,}mul_highpart_cost. Not to be used otherwise. */
607 mul_highpart_cost_ptr (bool speed
, enum machine_mode mode
)
609 gcc_assert (GET_MODE_CLASS (mode
) == MODE_INT
);
611 return &this_target_expmed
->x_mul_highpart_cost
[speed
][mode
- MIN_MODE_INT
];
614 /* Set the COST for computing the high part of a multiplication in MODE
615 when optimizing for SPEED. */
618 set_mul_highpart_cost (bool speed
, enum machine_mode mode
, int cost
)
620 *mul_highpart_cost_ptr (speed
, mode
) = cost
;
623 /* Return the cost for computing the high part of a multiplication in MODE
624 when optimizing for SPEED. */
627 mul_highpart_cost (bool speed
, enum machine_mode mode
)
629 return *mul_highpart_cost_ptr (speed
, mode
);
632 /* Subroutine of {set_,}convert_cost. Not to be used otherwise. */
635 convert_cost_ptr (enum machine_mode to_mode
, enum machine_mode from_mode
,
638 int to_idx
= expmed_mode_index (to_mode
);
639 int from_idx
= expmed_mode_index (from_mode
);
641 gcc_assert (IN_RANGE (to_idx
, 0, NUM_MODE_IP_INT
- 1));
642 gcc_assert (IN_RANGE (from_idx
, 0, NUM_MODE_IP_INT
- 1));
644 return &this_target_expmed
->x_convert_cost
[speed
][to_idx
][from_idx
];
647 /* Set the COST for converting from FROM_MODE to TO_MODE when optimizing
651 set_convert_cost (enum machine_mode to_mode
, enum machine_mode from_mode
,
652 bool speed
, int cost
)
654 *convert_cost_ptr (to_mode
, from_mode
, speed
) = cost
;
657 /* Return the cost for converting from FROM_MODE to TO_MODE when optimizing
661 convert_cost (enum machine_mode to_mode
, enum machine_mode from_mode
,
664 return *convert_cost_ptr (to_mode
, from_mode
, speed
);
667 extern int mult_by_coeff_cost (HOST_WIDE_INT
, enum machine_mode
, bool);