Fix ICE in lto_symtab_merge_symbols_1 (PR lto/88004).
[official-gcc.git] / gcc / expmed.c
blob444d6a82f983c316cd287d03f48db4aab02a8cbb
1 /* Medium-level subroutines: convert bit-field store and extract
2 and shifts, multiplies and divides to rtl instructions.
3 Copyright (C) 1987-2018 Free Software Foundation, Inc.
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
10 version.
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
15 for more details.
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/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "backend.h"
26 #include "target.h"
27 #include "rtl.h"
28 #include "tree.h"
29 #include "predict.h"
30 #include "memmodel.h"
31 #include "tm_p.h"
32 #include "expmed.h"
33 #include "optabs.h"
34 #include "regs.h"
35 #include "emit-rtl.h"
36 #include "diagnostic-core.h"
37 #include "fold-const.h"
38 #include "stor-layout.h"
39 #include "dojump.h"
40 #include "explow.h"
41 #include "expr.h"
42 #include "langhooks.h"
43 #include "tree-vector-builder.h"
45 struct target_expmed default_target_expmed;
46 #if SWITCHABLE_TARGET
47 struct target_expmed *this_target_expmed = &default_target_expmed;
48 #endif
50 static bool store_integral_bit_field (rtx, opt_scalar_int_mode,
51 unsigned HOST_WIDE_INT,
52 unsigned HOST_WIDE_INT,
53 poly_uint64, poly_uint64,
54 machine_mode, rtx, bool, bool);
55 static void store_fixed_bit_field (rtx, opt_scalar_int_mode,
56 unsigned HOST_WIDE_INT,
57 unsigned HOST_WIDE_INT,
58 poly_uint64, poly_uint64,
59 rtx, scalar_int_mode, bool);
60 static void store_fixed_bit_field_1 (rtx, scalar_int_mode,
61 unsigned HOST_WIDE_INT,
62 unsigned HOST_WIDE_INT,
63 rtx, scalar_int_mode, bool);
64 static void store_split_bit_field (rtx, opt_scalar_int_mode,
65 unsigned HOST_WIDE_INT,
66 unsigned HOST_WIDE_INT,
67 poly_uint64, poly_uint64,
68 rtx, scalar_int_mode, bool);
69 static rtx extract_integral_bit_field (rtx, opt_scalar_int_mode,
70 unsigned HOST_WIDE_INT,
71 unsigned HOST_WIDE_INT, int, rtx,
72 machine_mode, machine_mode, bool, bool);
73 static rtx extract_fixed_bit_field (machine_mode, rtx, opt_scalar_int_mode,
74 unsigned HOST_WIDE_INT,
75 unsigned HOST_WIDE_INT, rtx, int, bool);
76 static rtx extract_fixed_bit_field_1 (machine_mode, rtx, scalar_int_mode,
77 unsigned HOST_WIDE_INT,
78 unsigned HOST_WIDE_INT, rtx, int, bool);
79 static rtx lshift_value (machine_mode, unsigned HOST_WIDE_INT, int);
80 static rtx extract_split_bit_field (rtx, opt_scalar_int_mode,
81 unsigned HOST_WIDE_INT,
82 unsigned HOST_WIDE_INT, int, bool);
83 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, machine_mode, rtx_code_label *);
84 static rtx expand_smod_pow2 (scalar_int_mode, rtx, HOST_WIDE_INT);
85 static rtx expand_sdiv_pow2 (scalar_int_mode, rtx, HOST_WIDE_INT);
87 /* Return a constant integer mask value of mode MODE with BITSIZE ones
88 followed by BITPOS zeros, or the complement of that if COMPLEMENT.
89 The mask is truncated if necessary to the width of mode MODE. The
90 mask is zero-extended if BITSIZE+BITPOS is too small for MODE. */
92 static inline rtx
93 mask_rtx (scalar_int_mode mode, int bitpos, int bitsize, bool complement)
95 return immed_wide_int_const
96 (wi::shifted_mask (bitpos, bitsize, complement,
97 GET_MODE_PRECISION (mode)), mode);
100 /* Test whether a value is zero of a power of two. */
101 #define EXACT_POWER_OF_2_OR_ZERO_P(x) \
102 (((x) & ((x) - HOST_WIDE_INT_1U)) == 0)
104 struct init_expmed_rtl
106 rtx reg;
107 rtx plus;
108 rtx neg;
109 rtx mult;
110 rtx sdiv;
111 rtx udiv;
112 rtx sdiv_32;
113 rtx smod_32;
114 rtx wide_mult;
115 rtx wide_lshr;
116 rtx wide_trunc;
117 rtx shift;
118 rtx shift_mult;
119 rtx shift_add;
120 rtx shift_sub0;
121 rtx shift_sub1;
122 rtx zext;
123 rtx trunc;
125 rtx pow2[MAX_BITS_PER_WORD];
126 rtx cint[MAX_BITS_PER_WORD];
129 static void
130 init_expmed_one_conv (struct init_expmed_rtl *all, scalar_int_mode to_mode,
131 scalar_int_mode from_mode, bool speed)
133 int to_size, from_size;
134 rtx which;
136 to_size = GET_MODE_PRECISION (to_mode);
137 from_size = GET_MODE_PRECISION (from_mode);
139 /* Most partial integers have a precision less than the "full"
140 integer it requires for storage. In case one doesn't, for
141 comparison purposes here, reduce the bit size by one in that
142 case. */
143 if (GET_MODE_CLASS (to_mode) == MODE_PARTIAL_INT
144 && pow2p_hwi (to_size))
145 to_size --;
146 if (GET_MODE_CLASS (from_mode) == MODE_PARTIAL_INT
147 && pow2p_hwi (from_size))
148 from_size --;
150 /* Assume cost of zero-extend and sign-extend is the same. */
151 which = (to_size < from_size ? all->trunc : all->zext);
153 PUT_MODE (all->reg, from_mode);
154 set_convert_cost (to_mode, from_mode, speed,
155 set_src_cost (which, to_mode, speed));
158 static void
159 init_expmed_one_mode (struct init_expmed_rtl *all,
160 machine_mode mode, int speed)
162 int m, n, mode_bitsize;
163 machine_mode mode_from;
165 mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
167 PUT_MODE (all->reg, mode);
168 PUT_MODE (all->plus, mode);
169 PUT_MODE (all->neg, mode);
170 PUT_MODE (all->mult, mode);
171 PUT_MODE (all->sdiv, mode);
172 PUT_MODE (all->udiv, mode);
173 PUT_MODE (all->sdiv_32, mode);
174 PUT_MODE (all->smod_32, mode);
175 PUT_MODE (all->wide_trunc, mode);
176 PUT_MODE (all->shift, mode);
177 PUT_MODE (all->shift_mult, mode);
178 PUT_MODE (all->shift_add, mode);
179 PUT_MODE (all->shift_sub0, mode);
180 PUT_MODE (all->shift_sub1, mode);
181 PUT_MODE (all->zext, mode);
182 PUT_MODE (all->trunc, mode);
184 set_add_cost (speed, mode, set_src_cost (all->plus, mode, speed));
185 set_neg_cost (speed, mode, set_src_cost (all->neg, mode, speed));
186 set_mul_cost (speed, mode, set_src_cost (all->mult, mode, speed));
187 set_sdiv_cost (speed, mode, set_src_cost (all->sdiv, mode, speed));
188 set_udiv_cost (speed, mode, set_src_cost (all->udiv, mode, speed));
190 set_sdiv_pow2_cheap (speed, mode, (set_src_cost (all->sdiv_32, mode, speed)
191 <= 2 * add_cost (speed, mode)));
192 set_smod_pow2_cheap (speed, mode, (set_src_cost (all->smod_32, mode, speed)
193 <= 4 * add_cost (speed, mode)));
195 set_shift_cost (speed, mode, 0, 0);
197 int cost = add_cost (speed, mode);
198 set_shiftadd_cost (speed, mode, 0, cost);
199 set_shiftsub0_cost (speed, mode, 0, cost);
200 set_shiftsub1_cost (speed, mode, 0, cost);
203 n = MIN (MAX_BITS_PER_WORD, mode_bitsize);
204 for (m = 1; m < n; m++)
206 XEXP (all->shift, 1) = all->cint[m];
207 XEXP (all->shift_mult, 1) = all->pow2[m];
209 set_shift_cost (speed, mode, m, set_src_cost (all->shift, mode, speed));
210 set_shiftadd_cost (speed, mode, m, set_src_cost (all->shift_add, mode,
211 speed));
212 set_shiftsub0_cost (speed, mode, m, set_src_cost (all->shift_sub0, mode,
213 speed));
214 set_shiftsub1_cost (speed, mode, m, set_src_cost (all->shift_sub1, mode,
215 speed));
218 scalar_int_mode int_mode_to;
219 if (is_a <scalar_int_mode> (mode, &int_mode_to))
221 for (mode_from = MIN_MODE_INT; mode_from <= MAX_MODE_INT;
222 mode_from = (machine_mode)(mode_from + 1))
223 init_expmed_one_conv (all, int_mode_to,
224 as_a <scalar_int_mode> (mode_from), speed);
226 scalar_int_mode wider_mode;
227 if (GET_MODE_CLASS (int_mode_to) == MODE_INT
228 && GET_MODE_WIDER_MODE (int_mode_to).exists (&wider_mode))
230 PUT_MODE (all->zext, wider_mode);
231 PUT_MODE (all->wide_mult, wider_mode);
232 PUT_MODE (all->wide_lshr, wider_mode);
233 XEXP (all->wide_lshr, 1)
234 = gen_int_shift_amount (wider_mode, mode_bitsize);
236 set_mul_widen_cost (speed, wider_mode,
237 set_src_cost (all->wide_mult, wider_mode, speed));
238 set_mul_highpart_cost (speed, int_mode_to,
239 set_src_cost (all->wide_trunc,
240 int_mode_to, speed));
245 void
246 init_expmed (void)
248 struct init_expmed_rtl all;
249 machine_mode mode = QImode;
250 int m, speed;
252 memset (&all, 0, sizeof all);
253 for (m = 1; m < MAX_BITS_PER_WORD; m++)
255 all.pow2[m] = GEN_INT (HOST_WIDE_INT_1 << m);
256 all.cint[m] = GEN_INT (m);
259 /* Avoid using hard regs in ways which may be unsupported. */
260 all.reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
261 all.plus = gen_rtx_PLUS (mode, all.reg, all.reg);
262 all.neg = gen_rtx_NEG (mode, all.reg);
263 all.mult = gen_rtx_MULT (mode, all.reg, all.reg);
264 all.sdiv = gen_rtx_DIV (mode, all.reg, all.reg);
265 all.udiv = gen_rtx_UDIV (mode, all.reg, all.reg);
266 all.sdiv_32 = gen_rtx_DIV (mode, all.reg, all.pow2[5]);
267 all.smod_32 = gen_rtx_MOD (mode, all.reg, all.pow2[5]);
268 all.zext = gen_rtx_ZERO_EXTEND (mode, all.reg);
269 all.wide_mult = gen_rtx_MULT (mode, all.zext, all.zext);
270 all.wide_lshr = gen_rtx_LSHIFTRT (mode, all.wide_mult, all.reg);
271 all.wide_trunc = gen_rtx_TRUNCATE (mode, all.wide_lshr);
272 all.shift = gen_rtx_ASHIFT (mode, all.reg, all.reg);
273 all.shift_mult = gen_rtx_MULT (mode, all.reg, all.reg);
274 all.shift_add = gen_rtx_PLUS (mode, all.shift_mult, all.reg);
275 all.shift_sub0 = gen_rtx_MINUS (mode, all.shift_mult, all.reg);
276 all.shift_sub1 = gen_rtx_MINUS (mode, all.reg, all.shift_mult);
277 all.trunc = gen_rtx_TRUNCATE (mode, all.reg);
279 for (speed = 0; speed < 2; speed++)
281 crtl->maybe_hot_insn_p = speed;
282 set_zero_cost (speed, set_src_cost (const0_rtx, mode, speed));
284 for (mode = MIN_MODE_INT; mode <= MAX_MODE_INT;
285 mode = (machine_mode)(mode + 1))
286 init_expmed_one_mode (&all, mode, speed);
288 if (MIN_MODE_PARTIAL_INT != VOIDmode)
289 for (mode = MIN_MODE_PARTIAL_INT; mode <= MAX_MODE_PARTIAL_INT;
290 mode = (machine_mode)(mode + 1))
291 init_expmed_one_mode (&all, mode, speed);
293 if (MIN_MODE_VECTOR_INT != VOIDmode)
294 for (mode = MIN_MODE_VECTOR_INT; mode <= MAX_MODE_VECTOR_INT;
295 mode = (machine_mode)(mode + 1))
296 init_expmed_one_mode (&all, mode, speed);
299 if (alg_hash_used_p ())
301 struct alg_hash_entry *p = alg_hash_entry_ptr (0);
302 memset (p, 0, sizeof (*p) * NUM_ALG_HASH_ENTRIES);
304 else
305 set_alg_hash_used_p (true);
306 default_rtl_profile ();
308 ggc_free (all.trunc);
309 ggc_free (all.shift_sub1);
310 ggc_free (all.shift_sub0);
311 ggc_free (all.shift_add);
312 ggc_free (all.shift_mult);
313 ggc_free (all.shift);
314 ggc_free (all.wide_trunc);
315 ggc_free (all.wide_lshr);
316 ggc_free (all.wide_mult);
317 ggc_free (all.zext);
318 ggc_free (all.smod_32);
319 ggc_free (all.sdiv_32);
320 ggc_free (all.udiv);
321 ggc_free (all.sdiv);
322 ggc_free (all.mult);
323 ggc_free (all.neg);
324 ggc_free (all.plus);
325 ggc_free (all.reg);
328 /* Return an rtx representing minus the value of X.
329 MODE is the intended mode of the result,
330 useful if X is a CONST_INT. */
333 negate_rtx (machine_mode mode, rtx x)
335 rtx result = simplify_unary_operation (NEG, mode, x, mode);
337 if (result == 0)
338 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
340 return result;
343 /* Whether reverse storage order is supported on the target. */
344 static int reverse_storage_order_supported = -1;
346 /* Check whether reverse storage order is supported on the target. */
348 static void
349 check_reverse_storage_order_support (void)
351 if (BYTES_BIG_ENDIAN != WORDS_BIG_ENDIAN)
353 reverse_storage_order_supported = 0;
354 sorry ("reverse scalar storage order");
356 else
357 reverse_storage_order_supported = 1;
360 /* Whether reverse FP storage order is supported on the target. */
361 static int reverse_float_storage_order_supported = -1;
363 /* Check whether reverse FP storage order is supported on the target. */
365 static void
366 check_reverse_float_storage_order_support (void)
368 if (FLOAT_WORDS_BIG_ENDIAN != WORDS_BIG_ENDIAN)
370 reverse_float_storage_order_supported = 0;
371 sorry ("reverse floating-point scalar storage order");
373 else
374 reverse_float_storage_order_supported = 1;
377 /* Return an rtx representing value of X with reverse storage order.
378 MODE is the intended mode of the result,
379 useful if X is a CONST_INT. */
382 flip_storage_order (machine_mode mode, rtx x)
384 scalar_int_mode int_mode;
385 rtx result;
387 if (mode == QImode)
388 return x;
390 if (COMPLEX_MODE_P (mode))
392 rtx real = read_complex_part (x, false);
393 rtx imag = read_complex_part (x, true);
395 real = flip_storage_order (GET_MODE_INNER (mode), real);
396 imag = flip_storage_order (GET_MODE_INNER (mode), imag);
398 return gen_rtx_CONCAT (mode, real, imag);
401 if (__builtin_expect (reverse_storage_order_supported < 0, 0))
402 check_reverse_storage_order_support ();
404 if (!is_a <scalar_int_mode> (mode, &int_mode))
406 if (FLOAT_MODE_P (mode)
407 && __builtin_expect (reverse_float_storage_order_supported < 0, 0))
408 check_reverse_float_storage_order_support ();
410 if (!int_mode_for_size (GET_MODE_PRECISION (mode), 0).exists (&int_mode))
412 sorry ("reverse storage order for %smode", GET_MODE_NAME (mode));
413 return x;
415 x = gen_lowpart (int_mode, x);
418 result = simplify_unary_operation (BSWAP, int_mode, x, int_mode);
419 if (result == 0)
420 result = expand_unop (int_mode, bswap_optab, x, NULL_RTX, 1);
422 if (int_mode != mode)
423 result = gen_lowpart (mode, result);
425 return result;
428 /* If MODE is set, adjust bitfield memory MEM so that it points to the
429 first unit of mode MODE that contains a bitfield of size BITSIZE at
430 bit position BITNUM. If MODE is not set, return a BLKmode reference
431 to every byte in the bitfield. Set *NEW_BITNUM to the bit position
432 of the field within the new memory. */
434 static rtx
435 narrow_bit_field_mem (rtx mem, opt_scalar_int_mode mode,
436 unsigned HOST_WIDE_INT bitsize,
437 unsigned HOST_WIDE_INT bitnum,
438 unsigned HOST_WIDE_INT *new_bitnum)
440 scalar_int_mode imode;
441 if (mode.exists (&imode))
443 unsigned int unit = GET_MODE_BITSIZE (imode);
444 *new_bitnum = bitnum % unit;
445 HOST_WIDE_INT offset = (bitnum - *new_bitnum) / BITS_PER_UNIT;
446 return adjust_bitfield_address (mem, imode, offset);
448 else
450 *new_bitnum = bitnum % BITS_PER_UNIT;
451 HOST_WIDE_INT offset = bitnum / BITS_PER_UNIT;
452 HOST_WIDE_INT size = ((*new_bitnum + bitsize + BITS_PER_UNIT - 1)
453 / BITS_PER_UNIT);
454 return adjust_bitfield_address_size (mem, BLKmode, offset, size);
458 /* The caller wants to perform insertion or extraction PATTERN on a
459 bitfield of size BITSIZE at BITNUM bits into memory operand OP0.
460 BITREGION_START and BITREGION_END are as for store_bit_field
461 and FIELDMODE is the natural mode of the field.
463 Search for a mode that is compatible with the memory access
464 restrictions and (where applicable) with a register insertion or
465 extraction. Return the new memory on success, storing the adjusted
466 bit position in *NEW_BITNUM. Return null otherwise. */
468 static rtx
469 adjust_bit_field_mem_for_reg (enum extraction_pattern pattern,
470 rtx op0, HOST_WIDE_INT bitsize,
471 HOST_WIDE_INT bitnum,
472 poly_uint64 bitregion_start,
473 poly_uint64 bitregion_end,
474 machine_mode fieldmode,
475 unsigned HOST_WIDE_INT *new_bitnum)
477 bit_field_mode_iterator iter (bitsize, bitnum, bitregion_start,
478 bitregion_end, MEM_ALIGN (op0),
479 MEM_VOLATILE_P (op0));
480 scalar_int_mode best_mode;
481 if (iter.next_mode (&best_mode))
483 /* We can use a memory in BEST_MODE. See whether this is true for
484 any wider modes. All other things being equal, we prefer to
485 use the widest mode possible because it tends to expose more
486 CSE opportunities. */
487 if (!iter.prefer_smaller_modes ())
489 /* Limit the search to the mode required by the corresponding
490 register insertion or extraction instruction, if any. */
491 scalar_int_mode limit_mode = word_mode;
492 extraction_insn insn;
493 if (get_best_reg_extraction_insn (&insn, pattern,
494 GET_MODE_BITSIZE (best_mode),
495 fieldmode))
496 limit_mode = insn.field_mode;
498 scalar_int_mode wider_mode;
499 while (iter.next_mode (&wider_mode)
500 && GET_MODE_SIZE (wider_mode) <= GET_MODE_SIZE (limit_mode))
501 best_mode = wider_mode;
503 return narrow_bit_field_mem (op0, best_mode, bitsize, bitnum,
504 new_bitnum);
506 return NULL_RTX;
509 /* Return true if a bitfield of size BITSIZE at bit number BITNUM within
510 a structure of mode STRUCT_MODE represents a lowpart subreg. The subreg
511 offset is then BITNUM / BITS_PER_UNIT. */
513 static bool
514 lowpart_bit_field_p (poly_uint64 bitnum, poly_uint64 bitsize,
515 machine_mode struct_mode)
517 poly_uint64 regsize = REGMODE_NATURAL_SIZE (struct_mode);
518 if (BYTES_BIG_ENDIAN)
519 return (multiple_p (bitnum, BITS_PER_UNIT)
520 && (known_eq (bitnum + bitsize, GET_MODE_BITSIZE (struct_mode))
521 || multiple_p (bitnum + bitsize,
522 regsize * BITS_PER_UNIT)));
523 else
524 return multiple_p (bitnum, regsize * BITS_PER_UNIT);
527 /* Return true if -fstrict-volatile-bitfields applies to an access of OP0
528 containing BITSIZE bits starting at BITNUM, with field mode FIELDMODE.
529 Return false if the access would touch memory outside the range
530 BITREGION_START to BITREGION_END for conformance to the C++ memory
531 model. */
533 static bool
534 strict_volatile_bitfield_p (rtx op0, unsigned HOST_WIDE_INT bitsize,
535 unsigned HOST_WIDE_INT bitnum,
536 scalar_int_mode fieldmode,
537 poly_uint64 bitregion_start,
538 poly_uint64 bitregion_end)
540 unsigned HOST_WIDE_INT modesize = GET_MODE_BITSIZE (fieldmode);
542 /* -fstrict-volatile-bitfields must be enabled and we must have a
543 volatile MEM. */
544 if (!MEM_P (op0)
545 || !MEM_VOLATILE_P (op0)
546 || flag_strict_volatile_bitfields <= 0)
547 return false;
549 /* The bit size must not be larger than the field mode, and
550 the field mode must not be larger than a word. */
551 if (bitsize > modesize || modesize > BITS_PER_WORD)
552 return false;
554 /* Check for cases of unaligned fields that must be split. */
555 if (bitnum % modesize + bitsize > modesize)
556 return false;
558 /* The memory must be sufficiently aligned for a MODESIZE access.
559 This condition guarantees, that the memory access will not
560 touch anything after the end of the structure. */
561 if (MEM_ALIGN (op0) < modesize)
562 return false;
564 /* Check for cases where the C++ memory model applies. */
565 if (maybe_ne (bitregion_end, 0U)
566 && (maybe_lt (bitnum - bitnum % modesize, bitregion_start)
567 || maybe_gt (bitnum - bitnum % modesize + modesize - 1,
568 bitregion_end)))
569 return false;
571 return true;
574 /* Return true if OP is a memory and if a bitfield of size BITSIZE at
575 bit number BITNUM can be treated as a simple value of mode MODE.
576 Store the byte offset in *BYTENUM if so. */
578 static bool
579 simple_mem_bitfield_p (rtx op0, poly_uint64 bitsize, poly_uint64 bitnum,
580 machine_mode mode, poly_uint64 *bytenum)
582 return (MEM_P (op0)
583 && multiple_p (bitnum, BITS_PER_UNIT, bytenum)
584 && known_eq (bitsize, GET_MODE_BITSIZE (mode))
585 && (!targetm.slow_unaligned_access (mode, MEM_ALIGN (op0))
586 || (multiple_p (bitnum, GET_MODE_ALIGNMENT (mode))
587 && MEM_ALIGN (op0) >= GET_MODE_ALIGNMENT (mode))));
590 /* Try to use instruction INSV to store VALUE into a field of OP0.
591 If OP0_MODE is defined, it is the mode of OP0, otherwise OP0 is a
592 BLKmode MEM. VALUE_MODE is the mode of VALUE. BITSIZE and BITNUM
593 are as for store_bit_field. */
595 static bool
596 store_bit_field_using_insv (const extraction_insn *insv, rtx op0,
597 opt_scalar_int_mode op0_mode,
598 unsigned HOST_WIDE_INT bitsize,
599 unsigned HOST_WIDE_INT bitnum,
600 rtx value, scalar_int_mode value_mode)
602 struct expand_operand ops[4];
603 rtx value1;
604 rtx xop0 = op0;
605 rtx_insn *last = get_last_insn ();
606 bool copy_back = false;
608 scalar_int_mode op_mode = insv->field_mode;
609 unsigned int unit = GET_MODE_BITSIZE (op_mode);
610 if (bitsize == 0 || bitsize > unit)
611 return false;
613 if (MEM_P (xop0))
614 /* Get a reference to the first byte of the field. */
615 xop0 = narrow_bit_field_mem (xop0, insv->struct_mode, bitsize, bitnum,
616 &bitnum);
617 else
619 /* Convert from counting within OP0 to counting in OP_MODE. */
620 if (BYTES_BIG_ENDIAN)
621 bitnum += unit - GET_MODE_BITSIZE (op0_mode.require ());
623 /* If xop0 is a register, we need it in OP_MODE
624 to make it acceptable to the format of insv. */
625 if (GET_CODE (xop0) == SUBREG)
626 /* We can't just change the mode, because this might clobber op0,
627 and we will need the original value of op0 if insv fails. */
628 xop0 = gen_rtx_SUBREG (op_mode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
629 if (REG_P (xop0) && GET_MODE (xop0) != op_mode)
630 xop0 = gen_lowpart_SUBREG (op_mode, xop0);
633 /* If the destination is a paradoxical subreg such that we need a
634 truncate to the inner mode, perform the insertion on a temporary and
635 truncate the result to the original destination. Note that we can't
636 just truncate the paradoxical subreg as (truncate:N (subreg:W (reg:N
637 X) 0)) is (reg:N X). */
638 if (GET_CODE (xop0) == SUBREG
639 && REG_P (SUBREG_REG (xop0))
640 && !TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (SUBREG_REG (xop0)),
641 op_mode))
643 rtx tem = gen_reg_rtx (op_mode);
644 emit_move_insn (tem, xop0);
645 xop0 = tem;
646 copy_back = true;
649 /* There are similar overflow check at the start of store_bit_field_1,
650 but that only check the situation where the field lies completely
651 outside the register, while there do have situation where the field
652 lies partialy in the register, we need to adjust bitsize for this
653 partial overflow situation. Without this fix, pr48335-2.c on big-endian
654 will broken on those arch support bit insert instruction, like arm, aarch64
655 etc. */
656 if (bitsize + bitnum > unit && bitnum < unit)
658 warning (OPT_Wextra, "write of %wu-bit data outside the bound of "
659 "destination object, data truncated into %wu-bit",
660 bitsize, unit - bitnum);
661 bitsize = unit - bitnum;
664 /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
665 "backwards" from the size of the unit we are inserting into.
666 Otherwise, we count bits from the most significant on a
667 BYTES/BITS_BIG_ENDIAN machine. */
669 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
670 bitnum = unit - bitsize - bitnum;
672 /* Convert VALUE to op_mode (which insv insn wants) in VALUE1. */
673 value1 = value;
674 if (value_mode != op_mode)
676 if (GET_MODE_BITSIZE (value_mode) >= bitsize)
678 rtx tmp;
679 /* Optimization: Don't bother really extending VALUE
680 if it has all the bits we will actually use. However,
681 if we must narrow it, be sure we do it correctly. */
683 if (GET_MODE_SIZE (value_mode) < GET_MODE_SIZE (op_mode))
685 tmp = simplify_subreg (op_mode, value1, value_mode, 0);
686 if (! tmp)
687 tmp = simplify_gen_subreg (op_mode,
688 force_reg (value_mode, value1),
689 value_mode, 0);
691 else
693 tmp = gen_lowpart_if_possible (op_mode, value1);
694 if (! tmp)
695 tmp = gen_lowpart (op_mode, force_reg (value_mode, value1));
697 value1 = tmp;
699 else if (CONST_INT_P (value))
700 value1 = gen_int_mode (INTVAL (value), op_mode);
701 else
702 /* Parse phase is supposed to make VALUE's data type
703 match that of the component reference, which is a type
704 at least as wide as the field; so VALUE should have
705 a mode that corresponds to that type. */
706 gcc_assert (CONSTANT_P (value));
709 create_fixed_operand (&ops[0], xop0);
710 create_integer_operand (&ops[1], bitsize);
711 create_integer_operand (&ops[2], bitnum);
712 create_input_operand (&ops[3], value1, op_mode);
713 if (maybe_expand_insn (insv->icode, 4, ops))
715 if (copy_back)
716 convert_move (op0, xop0, true);
717 return true;
719 delete_insns_since (last);
720 return false;
723 /* A subroutine of store_bit_field, with the same arguments. Return true
724 if the operation could be implemented.
726 If FALLBACK_P is true, fall back to store_fixed_bit_field if we have
727 no other way of implementing the operation. If FALLBACK_P is false,
728 return false instead. */
730 static bool
731 store_bit_field_1 (rtx str_rtx, poly_uint64 bitsize, poly_uint64 bitnum,
732 poly_uint64 bitregion_start, poly_uint64 bitregion_end,
733 machine_mode fieldmode,
734 rtx value, bool reverse, bool fallback_p)
736 rtx op0 = str_rtx;
738 while (GET_CODE (op0) == SUBREG)
740 bitnum += subreg_memory_offset (op0) * BITS_PER_UNIT;
741 op0 = SUBREG_REG (op0);
744 /* No action is needed if the target is a register and if the field
745 lies completely outside that register. This can occur if the source
746 code contains an out-of-bounds access to a small array. */
747 if (REG_P (op0) && known_ge (bitnum, GET_MODE_BITSIZE (GET_MODE (op0))))
748 return true;
750 /* Use vec_set patterns for inserting parts of vectors whenever
751 available. */
752 machine_mode outermode = GET_MODE (op0);
753 scalar_mode innermode = GET_MODE_INNER (outermode);
754 poly_uint64 pos;
755 if (VECTOR_MODE_P (outermode)
756 && !MEM_P (op0)
757 && optab_handler (vec_set_optab, outermode) != CODE_FOR_nothing
758 && fieldmode == innermode
759 && known_eq (bitsize, GET_MODE_BITSIZE (innermode))
760 && multiple_p (bitnum, GET_MODE_BITSIZE (innermode), &pos))
762 struct expand_operand ops[3];
763 enum insn_code icode = optab_handler (vec_set_optab, outermode);
765 create_fixed_operand (&ops[0], op0);
766 create_input_operand (&ops[1], value, innermode);
767 create_integer_operand (&ops[2], pos);
768 if (maybe_expand_insn (icode, 3, ops))
769 return true;
772 /* If the target is a register, overwriting the entire object, or storing
773 a full-word or multi-word field can be done with just a SUBREG. */
774 if (!MEM_P (op0)
775 && known_eq (bitsize, GET_MODE_BITSIZE (fieldmode)))
777 /* Use the subreg machinery either to narrow OP0 to the required
778 words or to cope with mode punning between equal-sized modes.
779 In the latter case, use subreg on the rhs side, not lhs. */
780 rtx sub;
781 HOST_WIDE_INT regnum;
782 poly_uint64 regsize = REGMODE_NATURAL_SIZE (GET_MODE (op0));
783 if (known_eq (bitnum, 0U)
784 && known_eq (bitsize, GET_MODE_BITSIZE (GET_MODE (op0))))
786 sub = simplify_gen_subreg (GET_MODE (op0), value, fieldmode, 0);
787 if (sub)
789 if (reverse)
790 sub = flip_storage_order (GET_MODE (op0), sub);
791 emit_move_insn (op0, sub);
792 return true;
795 else if (constant_multiple_p (bitnum, regsize * BITS_PER_UNIT, &regnum)
796 && multiple_p (bitsize, regsize * BITS_PER_UNIT))
798 sub = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0),
799 regnum * regsize);
800 if (sub)
802 if (reverse)
803 value = flip_storage_order (fieldmode, value);
804 emit_move_insn (sub, value);
805 return true;
810 /* If the target is memory, storing any naturally aligned field can be
811 done with a simple store. For targets that support fast unaligned
812 memory, any naturally sized, unit aligned field can be done directly. */
813 poly_uint64 bytenum;
814 if (simple_mem_bitfield_p (op0, bitsize, bitnum, fieldmode, &bytenum))
816 op0 = adjust_bitfield_address (op0, fieldmode, bytenum);
817 if (reverse)
818 value = flip_storage_order (fieldmode, value);
819 emit_move_insn (op0, value);
820 return true;
823 /* It's possible we'll need to handle other cases here for
824 polynomial bitnum and bitsize. */
826 /* From here on we need to be looking at a fixed-size insertion. */
827 unsigned HOST_WIDE_INT ibitsize = bitsize.to_constant ();
828 unsigned HOST_WIDE_INT ibitnum = bitnum.to_constant ();
830 /* Make sure we are playing with integral modes. Pun with subregs
831 if we aren't. This must come after the entire register case above,
832 since that case is valid for any mode. The following cases are only
833 valid for integral modes. */
834 opt_scalar_int_mode op0_mode = int_mode_for_mode (GET_MODE (op0));
835 scalar_int_mode imode;
836 if (!op0_mode.exists (&imode) || imode != GET_MODE (op0))
838 if (MEM_P (op0))
839 op0 = adjust_bitfield_address_size (op0, op0_mode.else_blk (),
840 0, MEM_SIZE (op0));
841 else
842 op0 = gen_lowpart (op0_mode.require (), op0);
845 return store_integral_bit_field (op0, op0_mode, ibitsize, ibitnum,
846 bitregion_start, bitregion_end,
847 fieldmode, value, reverse, fallback_p);
850 /* Subroutine of store_bit_field_1, with the same arguments, except
851 that BITSIZE and BITNUM are constant. Handle cases specific to
852 integral modes. If OP0_MODE is defined, it is the mode of OP0,
853 otherwise OP0 is a BLKmode MEM. */
855 static bool
856 store_integral_bit_field (rtx op0, opt_scalar_int_mode op0_mode,
857 unsigned HOST_WIDE_INT bitsize,
858 unsigned HOST_WIDE_INT bitnum,
859 poly_uint64 bitregion_start,
860 poly_uint64 bitregion_end,
861 machine_mode fieldmode,
862 rtx value, bool reverse, bool fallback_p)
864 /* Storing an lsb-aligned field in a register
865 can be done with a movstrict instruction. */
867 if (!MEM_P (op0)
868 && !reverse
869 && lowpart_bit_field_p (bitnum, bitsize, op0_mode.require ())
870 && known_eq (bitsize, GET_MODE_BITSIZE (fieldmode))
871 && optab_handler (movstrict_optab, fieldmode) != CODE_FOR_nothing)
873 struct expand_operand ops[2];
874 enum insn_code icode = optab_handler (movstrict_optab, fieldmode);
875 rtx arg0 = op0;
876 unsigned HOST_WIDE_INT subreg_off;
878 if (GET_CODE (arg0) == SUBREG)
880 /* Else we've got some float mode source being extracted into
881 a different float mode destination -- this combination of
882 subregs results in Severe Tire Damage. */
883 gcc_assert (GET_MODE (SUBREG_REG (arg0)) == fieldmode
884 || GET_MODE_CLASS (fieldmode) == MODE_INT
885 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT);
886 arg0 = SUBREG_REG (arg0);
889 subreg_off = bitnum / BITS_PER_UNIT;
890 if (validate_subreg (fieldmode, GET_MODE (arg0), arg0, subreg_off))
892 arg0 = gen_rtx_SUBREG (fieldmode, arg0, subreg_off);
894 create_fixed_operand (&ops[0], arg0);
895 /* Shrink the source operand to FIELDMODE. */
896 create_convert_operand_to (&ops[1], value, fieldmode, false);
897 if (maybe_expand_insn (icode, 2, ops))
898 return true;
902 /* Handle fields bigger than a word. */
904 if (bitsize > BITS_PER_WORD)
906 /* Here we transfer the words of the field
907 in the order least significant first.
908 This is because the most significant word is the one which may
909 be less than full.
910 However, only do that if the value is not BLKmode. */
912 const bool backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
913 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
914 unsigned int i;
915 rtx_insn *last;
917 /* This is the mode we must force value to, so that there will be enough
918 subwords to extract. Note that fieldmode will often (always?) be
919 VOIDmode, because that is what store_field uses to indicate that this
920 is a bit field, but passing VOIDmode to operand_subword_force
921 is not allowed.
923 The mode must be fixed-size, since insertions into variable-sized
924 objects are meant to be handled before calling this function. */
925 fixed_size_mode value_mode = as_a <fixed_size_mode> (GET_MODE (value));
926 if (value_mode == VOIDmode)
927 value_mode = smallest_int_mode_for_size (nwords * BITS_PER_WORD);
929 last = get_last_insn ();
930 for (i = 0; i < nwords; i++)
932 /* If I is 0, use the low-order word in both field and target;
933 if I is 1, use the next to lowest word; and so on. */
934 unsigned int wordnum = (backwards
935 ? GET_MODE_SIZE (value_mode) / UNITS_PER_WORD
936 - i - 1
937 : i);
938 unsigned int bit_offset = (backwards ^ reverse
939 ? MAX ((int) bitsize - ((int) i + 1)
940 * BITS_PER_WORD,
942 : (int) i * BITS_PER_WORD);
943 rtx value_word = operand_subword_force (value, wordnum, value_mode);
944 unsigned HOST_WIDE_INT new_bitsize =
945 MIN (BITS_PER_WORD, bitsize - i * BITS_PER_WORD);
947 /* If the remaining chunk doesn't have full wordsize we have
948 to make sure that for big-endian machines the higher order
949 bits are used. */
950 if (new_bitsize < BITS_PER_WORD && BYTES_BIG_ENDIAN && !backwards)
952 int shift = BITS_PER_WORD - new_bitsize;
953 rtx shift_rtx = gen_int_shift_amount (word_mode, shift);
954 value_word = simplify_expand_binop (word_mode, lshr_optab,
955 value_word, shift_rtx,
956 NULL_RTX, true,
957 OPTAB_LIB_WIDEN);
960 if (!store_bit_field_1 (op0, new_bitsize,
961 bitnum + bit_offset,
962 bitregion_start, bitregion_end,
963 word_mode,
964 value_word, reverse, fallback_p))
966 delete_insns_since (last);
967 return false;
970 return true;
973 /* If VALUE has a floating-point or complex mode, access it as an
974 integer of the corresponding size. This can occur on a machine
975 with 64 bit registers that uses SFmode for float. It can also
976 occur for unaligned float or complex fields. */
977 rtx orig_value = value;
978 scalar_int_mode value_mode;
979 if (GET_MODE (value) == VOIDmode)
980 /* By this point we've dealt with values that are bigger than a word,
981 so word_mode is a conservatively correct choice. */
982 value_mode = word_mode;
983 else if (!is_a <scalar_int_mode> (GET_MODE (value), &value_mode))
985 value_mode = int_mode_for_mode (GET_MODE (value)).require ();
986 value = gen_reg_rtx (value_mode);
987 emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value);
990 /* If OP0 is a multi-word register, narrow it to the affected word.
991 If the region spans two words, defer to store_split_bit_field.
992 Don't do this if op0 is a single hard register wider than word
993 such as a float or vector register. */
994 if (!MEM_P (op0)
995 && GET_MODE_SIZE (op0_mode.require ()) > UNITS_PER_WORD
996 && (!REG_P (op0)
997 || !HARD_REGISTER_P (op0)
998 || hard_regno_nregs (REGNO (op0), op0_mode.require ()) != 1))
1000 if (bitnum % BITS_PER_WORD + bitsize > BITS_PER_WORD)
1002 if (!fallback_p)
1003 return false;
1005 store_split_bit_field (op0, op0_mode, bitsize, bitnum,
1006 bitregion_start, bitregion_end,
1007 value, value_mode, reverse);
1008 return true;
1010 op0 = simplify_gen_subreg (word_mode, op0, op0_mode.require (),
1011 bitnum / BITS_PER_WORD * UNITS_PER_WORD);
1012 gcc_assert (op0);
1013 op0_mode = word_mode;
1014 bitnum %= BITS_PER_WORD;
1017 /* From here on we can assume that the field to be stored in fits
1018 within a word. If the destination is a register, it too fits
1019 in a word. */
1021 extraction_insn insv;
1022 if (!MEM_P (op0)
1023 && !reverse
1024 && get_best_reg_extraction_insn (&insv, EP_insv,
1025 GET_MODE_BITSIZE (op0_mode.require ()),
1026 fieldmode)
1027 && store_bit_field_using_insv (&insv, op0, op0_mode,
1028 bitsize, bitnum, value, value_mode))
1029 return true;
1031 /* If OP0 is a memory, try copying it to a register and seeing if a
1032 cheap register alternative is available. */
1033 if (MEM_P (op0) && !reverse)
1035 if (get_best_mem_extraction_insn (&insv, EP_insv, bitsize, bitnum,
1036 fieldmode)
1037 && store_bit_field_using_insv (&insv, op0, op0_mode,
1038 bitsize, bitnum, value, value_mode))
1039 return true;
1041 rtx_insn *last = get_last_insn ();
1043 /* Try loading part of OP0 into a register, inserting the bitfield
1044 into that, and then copying the result back to OP0. */
1045 unsigned HOST_WIDE_INT bitpos;
1046 rtx xop0 = adjust_bit_field_mem_for_reg (EP_insv, op0, bitsize, bitnum,
1047 bitregion_start, bitregion_end,
1048 fieldmode, &bitpos);
1049 if (xop0)
1051 rtx tempreg = copy_to_reg (xop0);
1052 if (store_bit_field_1 (tempreg, bitsize, bitpos,
1053 bitregion_start, bitregion_end,
1054 fieldmode, orig_value, reverse, false))
1056 emit_move_insn (xop0, tempreg);
1057 return true;
1059 delete_insns_since (last);
1063 if (!fallback_p)
1064 return false;
1066 store_fixed_bit_field (op0, op0_mode, bitsize, bitnum, bitregion_start,
1067 bitregion_end, value, value_mode, reverse);
1068 return true;
1071 /* Generate code to store value from rtx VALUE
1072 into a bit-field within structure STR_RTX
1073 containing BITSIZE bits starting at bit BITNUM.
1075 BITREGION_START is bitpos of the first bitfield in this region.
1076 BITREGION_END is the bitpos of the ending bitfield in this region.
1077 These two fields are 0, if the C++ memory model does not apply,
1078 or we are not interested in keeping track of bitfield regions.
1080 FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
1082 If REVERSE is true, the store is to be done in reverse order. */
1084 void
1085 store_bit_field (rtx str_rtx, poly_uint64 bitsize, poly_uint64 bitnum,
1086 poly_uint64 bitregion_start, poly_uint64 bitregion_end,
1087 machine_mode fieldmode,
1088 rtx value, bool reverse)
1090 /* Handle -fstrict-volatile-bitfields in the cases where it applies. */
1091 unsigned HOST_WIDE_INT ibitsize = 0, ibitnum = 0;
1092 scalar_int_mode int_mode;
1093 if (bitsize.is_constant (&ibitsize)
1094 && bitnum.is_constant (&ibitnum)
1095 && is_a <scalar_int_mode> (fieldmode, &int_mode)
1096 && strict_volatile_bitfield_p (str_rtx, ibitsize, ibitnum, int_mode,
1097 bitregion_start, bitregion_end))
1099 /* Storing of a full word can be done with a simple store.
1100 We know here that the field can be accessed with one single
1101 instruction. For targets that support unaligned memory,
1102 an unaligned access may be necessary. */
1103 if (ibitsize == GET_MODE_BITSIZE (int_mode))
1105 str_rtx = adjust_bitfield_address (str_rtx, int_mode,
1106 ibitnum / BITS_PER_UNIT);
1107 if (reverse)
1108 value = flip_storage_order (int_mode, value);
1109 gcc_assert (ibitnum % BITS_PER_UNIT == 0);
1110 emit_move_insn (str_rtx, value);
1112 else
1114 rtx temp;
1116 str_rtx = narrow_bit_field_mem (str_rtx, int_mode, ibitsize,
1117 ibitnum, &ibitnum);
1118 gcc_assert (ibitnum + ibitsize <= GET_MODE_BITSIZE (int_mode));
1119 temp = copy_to_reg (str_rtx);
1120 if (!store_bit_field_1 (temp, ibitsize, ibitnum, 0, 0,
1121 int_mode, value, reverse, true))
1122 gcc_unreachable ();
1124 emit_move_insn (str_rtx, temp);
1127 return;
1130 /* Under the C++0x memory model, we must not touch bits outside the
1131 bit region. Adjust the address to start at the beginning of the
1132 bit region. */
1133 if (MEM_P (str_rtx) && maybe_ne (bitregion_start, 0U))
1135 scalar_int_mode best_mode;
1136 machine_mode addr_mode = VOIDmode;
1138 poly_uint64 offset = exact_div (bitregion_start, BITS_PER_UNIT);
1139 bitnum -= bitregion_start;
1140 poly_int64 size = bits_to_bytes_round_up (bitnum + bitsize);
1141 bitregion_end -= bitregion_start;
1142 bitregion_start = 0;
1143 if (bitsize.is_constant (&ibitsize)
1144 && bitnum.is_constant (&ibitnum)
1145 && get_best_mode (ibitsize, ibitnum,
1146 bitregion_start, bitregion_end,
1147 MEM_ALIGN (str_rtx), INT_MAX,
1148 MEM_VOLATILE_P (str_rtx), &best_mode))
1149 addr_mode = best_mode;
1150 str_rtx = adjust_bitfield_address_size (str_rtx, addr_mode,
1151 offset, size);
1154 if (!store_bit_field_1 (str_rtx, bitsize, bitnum,
1155 bitregion_start, bitregion_end,
1156 fieldmode, value, reverse, true))
1157 gcc_unreachable ();
1160 /* Use shifts and boolean operations to store VALUE into a bit field of
1161 width BITSIZE in OP0, starting at bit BITNUM. If OP0_MODE is defined,
1162 it is the mode of OP0, otherwise OP0 is a BLKmode MEM. VALUE_MODE is
1163 the mode of VALUE.
1165 If REVERSE is true, the store is to be done in reverse order. */
1167 static void
1168 store_fixed_bit_field (rtx op0, opt_scalar_int_mode op0_mode,
1169 unsigned HOST_WIDE_INT bitsize,
1170 unsigned HOST_WIDE_INT bitnum,
1171 poly_uint64 bitregion_start, poly_uint64 bitregion_end,
1172 rtx value, scalar_int_mode value_mode, bool reverse)
1174 /* There is a case not handled here:
1175 a structure with a known alignment of just a halfword
1176 and a field split across two aligned halfwords within the structure.
1177 Or likewise a structure with a known alignment of just a byte
1178 and a field split across two bytes.
1179 Such cases are not supposed to be able to occur. */
1181 scalar_int_mode best_mode;
1182 if (MEM_P (op0))
1184 unsigned int max_bitsize = BITS_PER_WORD;
1185 scalar_int_mode imode;
1186 if (op0_mode.exists (&imode) && GET_MODE_BITSIZE (imode) < max_bitsize)
1187 max_bitsize = GET_MODE_BITSIZE (imode);
1189 if (!get_best_mode (bitsize, bitnum, bitregion_start, bitregion_end,
1190 MEM_ALIGN (op0), max_bitsize, MEM_VOLATILE_P (op0),
1191 &best_mode))
1193 /* The only way this should occur is if the field spans word
1194 boundaries. */
1195 store_split_bit_field (op0, op0_mode, bitsize, bitnum,
1196 bitregion_start, bitregion_end,
1197 value, value_mode, reverse);
1198 return;
1201 op0 = narrow_bit_field_mem (op0, best_mode, bitsize, bitnum, &bitnum);
1203 else
1204 best_mode = op0_mode.require ();
1206 store_fixed_bit_field_1 (op0, best_mode, bitsize, bitnum,
1207 value, value_mode, reverse);
1210 /* Helper function for store_fixed_bit_field, stores
1211 the bit field always using MODE, which is the mode of OP0. The other
1212 arguments are as for store_fixed_bit_field. */
1214 static void
1215 store_fixed_bit_field_1 (rtx op0, scalar_int_mode mode,
1216 unsigned HOST_WIDE_INT bitsize,
1217 unsigned HOST_WIDE_INT bitnum,
1218 rtx value, scalar_int_mode value_mode, bool reverse)
1220 rtx temp;
1221 int all_zero = 0;
1222 int all_one = 0;
1224 /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
1225 for invalid input, such as f5 from gcc.dg/pr48335-2.c. */
1227 if (reverse ? !BYTES_BIG_ENDIAN : BYTES_BIG_ENDIAN)
1228 /* BITNUM is the distance between our msb
1229 and that of the containing datum.
1230 Convert it to the distance from the lsb. */
1231 bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
1233 /* Now BITNUM is always the distance between our lsb
1234 and that of OP0. */
1236 /* Shift VALUE left by BITNUM bits. If VALUE is not constant,
1237 we must first convert its mode to MODE. */
1239 if (CONST_INT_P (value))
1241 unsigned HOST_WIDE_INT v = UINTVAL (value);
1243 if (bitsize < HOST_BITS_PER_WIDE_INT)
1244 v &= (HOST_WIDE_INT_1U << bitsize) - 1;
1246 if (v == 0)
1247 all_zero = 1;
1248 else if ((bitsize < HOST_BITS_PER_WIDE_INT
1249 && v == (HOST_WIDE_INT_1U << bitsize) - 1)
1250 || (bitsize == HOST_BITS_PER_WIDE_INT
1251 && v == HOST_WIDE_INT_M1U))
1252 all_one = 1;
1254 value = lshift_value (mode, v, bitnum);
1256 else
1258 int must_and = (GET_MODE_BITSIZE (value_mode) != bitsize
1259 && bitnum + bitsize != GET_MODE_BITSIZE (mode));
1261 if (value_mode != mode)
1262 value = convert_to_mode (mode, value, 1);
1264 if (must_and)
1265 value = expand_binop (mode, and_optab, value,
1266 mask_rtx (mode, 0, bitsize, 0),
1267 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1268 if (bitnum > 0)
1269 value = expand_shift (LSHIFT_EXPR, mode, value,
1270 bitnum, NULL_RTX, 1);
1273 if (reverse)
1274 value = flip_storage_order (mode, value);
1276 /* Now clear the chosen bits in OP0,
1277 except that if VALUE is -1 we need not bother. */
1278 /* We keep the intermediates in registers to allow CSE to combine
1279 consecutive bitfield assignments. */
1281 temp = force_reg (mode, op0);
1283 if (! all_one)
1285 rtx mask = mask_rtx (mode, bitnum, bitsize, 1);
1286 if (reverse)
1287 mask = flip_storage_order (mode, mask);
1288 temp = expand_binop (mode, and_optab, temp, mask,
1289 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1290 temp = force_reg (mode, temp);
1293 /* Now logical-or VALUE into OP0, unless it is zero. */
1295 if (! all_zero)
1297 temp = expand_binop (mode, ior_optab, temp, value,
1298 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1299 temp = force_reg (mode, temp);
1302 if (op0 != temp)
1304 op0 = copy_rtx (op0);
1305 emit_move_insn (op0, temp);
1309 /* Store a bit field that is split across multiple accessible memory objects.
1311 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
1312 BITSIZE is the field width; BITPOS the position of its first bit
1313 (within the word).
1314 VALUE is the value to store, which has mode VALUE_MODE.
1315 If OP0_MODE is defined, it is the mode of OP0, otherwise OP0 is
1316 a BLKmode MEM.
1318 If REVERSE is true, the store is to be done in reverse order.
1320 This does not yet handle fields wider than BITS_PER_WORD. */
1322 static void
1323 store_split_bit_field (rtx op0, opt_scalar_int_mode op0_mode,
1324 unsigned HOST_WIDE_INT bitsize,
1325 unsigned HOST_WIDE_INT bitpos,
1326 poly_uint64 bitregion_start, poly_uint64 bitregion_end,
1327 rtx value, scalar_int_mode value_mode, bool reverse)
1329 unsigned int unit, total_bits, bitsdone = 0;
1331 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1332 much at a time. */
1333 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1334 unit = BITS_PER_WORD;
1335 else
1336 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1338 /* If OP0 is a memory with a mode, then UNIT must not be larger than
1339 OP0's mode as well. Otherwise, store_fixed_bit_field will call us
1340 again, and we will mutually recurse forever. */
1341 if (MEM_P (op0) && op0_mode.exists ())
1342 unit = MIN (unit, GET_MODE_BITSIZE (op0_mode.require ()));
1344 /* If VALUE is a constant other than a CONST_INT, get it into a register in
1345 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
1346 that VALUE might be a floating-point constant. */
1347 if (CONSTANT_P (value) && !CONST_INT_P (value))
1349 rtx word = gen_lowpart_common (word_mode, value);
1351 if (word && (value != word))
1352 value = word;
1353 else
1354 value = gen_lowpart_common (word_mode, force_reg (value_mode, value));
1355 value_mode = word_mode;
1358 total_bits = GET_MODE_BITSIZE (value_mode);
1360 while (bitsdone < bitsize)
1362 unsigned HOST_WIDE_INT thissize;
1363 unsigned HOST_WIDE_INT thispos;
1364 unsigned HOST_WIDE_INT offset;
1365 rtx part;
1367 offset = (bitpos + bitsdone) / unit;
1368 thispos = (bitpos + bitsdone) % unit;
1370 /* When region of bytes we can touch is restricted, decrease
1371 UNIT close to the end of the region as needed. If op0 is a REG
1372 or SUBREG of REG, don't do this, as there can't be data races
1373 on a register and we can expand shorter code in some cases. */
1374 if (maybe_ne (bitregion_end, 0U)
1375 && unit > BITS_PER_UNIT
1376 && maybe_gt (bitpos + bitsdone - thispos + unit, bitregion_end + 1)
1377 && !REG_P (op0)
1378 && (GET_CODE (op0) != SUBREG || !REG_P (SUBREG_REG (op0))))
1380 unit = unit / 2;
1381 continue;
1384 /* THISSIZE must not overrun a word boundary. Otherwise,
1385 store_fixed_bit_field will call us again, and we will mutually
1386 recurse forever. */
1387 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1388 thissize = MIN (thissize, unit - thispos);
1390 if (reverse ? !BYTES_BIG_ENDIAN : BYTES_BIG_ENDIAN)
1392 /* Fetch successively less significant portions. */
1393 if (CONST_INT_P (value))
1394 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1395 >> (bitsize - bitsdone - thissize))
1396 & ((HOST_WIDE_INT_1 << thissize) - 1));
1397 /* Likewise, but the source is little-endian. */
1398 else if (reverse)
1399 part = extract_fixed_bit_field (word_mode, value, value_mode,
1400 thissize,
1401 bitsize - bitsdone - thissize,
1402 NULL_RTX, 1, false);
1403 else
1404 /* The args are chosen so that the last part includes the
1405 lsb. Give extract_bit_field the value it needs (with
1406 endianness compensation) to fetch the piece we want. */
1407 part = extract_fixed_bit_field (word_mode, value, value_mode,
1408 thissize,
1409 total_bits - bitsize + bitsdone,
1410 NULL_RTX, 1, false);
1412 else
1414 /* Fetch successively more significant portions. */
1415 if (CONST_INT_P (value))
1416 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1417 >> bitsdone)
1418 & ((HOST_WIDE_INT_1 << thissize) - 1));
1419 /* Likewise, but the source is big-endian. */
1420 else if (reverse)
1421 part = extract_fixed_bit_field (word_mode, value, value_mode,
1422 thissize,
1423 total_bits - bitsdone - thissize,
1424 NULL_RTX, 1, false);
1425 else
1426 part = extract_fixed_bit_field (word_mode, value, value_mode,
1427 thissize, bitsdone, NULL_RTX,
1428 1, false);
1431 /* If OP0 is a register, then handle OFFSET here. */
1432 rtx op0_piece = op0;
1433 opt_scalar_int_mode op0_piece_mode = op0_mode;
1434 if (SUBREG_P (op0) || REG_P (op0))
1436 scalar_int_mode imode;
1437 if (op0_mode.exists (&imode)
1438 && GET_MODE_SIZE (imode) < UNITS_PER_WORD)
1440 if (offset)
1441 op0_piece = const0_rtx;
1443 else
1445 op0_piece = operand_subword_force (op0,
1446 offset * unit / BITS_PER_WORD,
1447 GET_MODE (op0));
1448 op0_piece_mode = word_mode;
1450 offset &= BITS_PER_WORD / unit - 1;
1453 /* OFFSET is in UNITs, and UNIT is in bits. If WORD is const0_rtx,
1454 it is just an out-of-bounds access. Ignore it. */
1455 if (op0_piece != const0_rtx)
1456 store_fixed_bit_field (op0_piece, op0_piece_mode, thissize,
1457 offset * unit + thispos, bitregion_start,
1458 bitregion_end, part, word_mode, reverse);
1459 bitsdone += thissize;
1463 /* A subroutine of extract_bit_field_1 that converts return value X
1464 to either MODE or TMODE. MODE, TMODE and UNSIGNEDP are arguments
1465 to extract_bit_field. */
1467 static rtx
1468 convert_extracted_bit_field (rtx x, machine_mode mode,
1469 machine_mode tmode, bool unsignedp)
1471 if (GET_MODE (x) == tmode || GET_MODE (x) == mode)
1472 return x;
1474 /* If the x mode is not a scalar integral, first convert to the
1475 integer mode of that size and then access it as a floating-point
1476 value via a SUBREG. */
1477 if (!SCALAR_INT_MODE_P (tmode))
1479 scalar_int_mode int_mode = int_mode_for_mode (tmode).require ();
1480 x = convert_to_mode (int_mode, x, unsignedp);
1481 x = force_reg (int_mode, x);
1482 return gen_lowpart (tmode, x);
1485 return convert_to_mode (tmode, x, unsignedp);
1488 /* Try to use an ext(z)v pattern to extract a field from OP0.
1489 Return the extracted value on success, otherwise return null.
1490 EXTV describes the extraction instruction to use. If OP0_MODE
1491 is defined, it is the mode of OP0, otherwise OP0 is a BLKmode MEM.
1492 The other arguments are as for extract_bit_field. */
1494 static rtx
1495 extract_bit_field_using_extv (const extraction_insn *extv, rtx op0,
1496 opt_scalar_int_mode op0_mode,
1497 unsigned HOST_WIDE_INT bitsize,
1498 unsigned HOST_WIDE_INT bitnum,
1499 int unsignedp, rtx target,
1500 machine_mode mode, machine_mode tmode)
1502 struct expand_operand ops[4];
1503 rtx spec_target = target;
1504 rtx spec_target_subreg = 0;
1505 scalar_int_mode ext_mode = extv->field_mode;
1506 unsigned unit = GET_MODE_BITSIZE (ext_mode);
1508 if (bitsize == 0 || unit < bitsize)
1509 return NULL_RTX;
1511 if (MEM_P (op0))
1512 /* Get a reference to the first byte of the field. */
1513 op0 = narrow_bit_field_mem (op0, extv->struct_mode, bitsize, bitnum,
1514 &bitnum);
1515 else
1517 /* Convert from counting within OP0 to counting in EXT_MODE. */
1518 if (BYTES_BIG_ENDIAN)
1519 bitnum += unit - GET_MODE_BITSIZE (op0_mode.require ());
1521 /* If op0 is a register, we need it in EXT_MODE to make it
1522 acceptable to the format of ext(z)v. */
1523 if (GET_CODE (op0) == SUBREG && op0_mode.require () != ext_mode)
1524 return NULL_RTX;
1525 if (REG_P (op0) && op0_mode.require () != ext_mode)
1526 op0 = gen_lowpart_SUBREG (ext_mode, op0);
1529 /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
1530 "backwards" from the size of the unit we are extracting from.
1531 Otherwise, we count bits from the most significant on a
1532 BYTES/BITS_BIG_ENDIAN machine. */
1534 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1535 bitnum = unit - bitsize - bitnum;
1537 if (target == 0)
1538 target = spec_target = gen_reg_rtx (tmode);
1540 if (GET_MODE (target) != ext_mode)
1542 /* Don't use LHS paradoxical subreg if explicit truncation is needed
1543 between the mode of the extraction (word_mode) and the target
1544 mode. Instead, create a temporary and use convert_move to set
1545 the target. */
1546 if (REG_P (target)
1547 && TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (target), ext_mode))
1549 target = gen_lowpart (ext_mode, target);
1550 if (partial_subreg_p (GET_MODE (spec_target), ext_mode))
1551 spec_target_subreg = target;
1553 else
1554 target = gen_reg_rtx (ext_mode);
1557 create_output_operand (&ops[0], target, ext_mode);
1558 create_fixed_operand (&ops[1], op0);
1559 create_integer_operand (&ops[2], bitsize);
1560 create_integer_operand (&ops[3], bitnum);
1561 if (maybe_expand_insn (extv->icode, 4, ops))
1563 target = ops[0].value;
1564 if (target == spec_target)
1565 return target;
1566 if (target == spec_target_subreg)
1567 return spec_target;
1568 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1570 return NULL_RTX;
1573 /* See whether it would be valid to extract the part of OP0 described
1574 by BITNUM and BITSIZE into a value of mode MODE using a subreg
1575 operation. Return the subreg if so, otherwise return null. */
1577 static rtx
1578 extract_bit_field_as_subreg (machine_mode mode, rtx op0,
1579 poly_uint64 bitsize, poly_uint64 bitnum)
1581 poly_uint64 bytenum;
1582 if (multiple_p (bitnum, BITS_PER_UNIT, &bytenum)
1583 && known_eq (bitsize, GET_MODE_BITSIZE (mode))
1584 && lowpart_bit_field_p (bitnum, bitsize, GET_MODE (op0))
1585 && TRULY_NOOP_TRUNCATION_MODES_P (mode, GET_MODE (op0)))
1586 return simplify_gen_subreg (mode, op0, GET_MODE (op0), bytenum);
1587 return NULL_RTX;
1590 /* A subroutine of extract_bit_field, with the same arguments.
1591 If FALLBACK_P is true, fall back to extract_fixed_bit_field
1592 if we can find no other means of implementing the operation.
1593 if FALLBACK_P is false, return NULL instead. */
1595 static rtx
1596 extract_bit_field_1 (rtx str_rtx, poly_uint64 bitsize, poly_uint64 bitnum,
1597 int unsignedp, rtx target, machine_mode mode,
1598 machine_mode tmode, bool reverse, bool fallback_p,
1599 rtx *alt_rtl)
1601 rtx op0 = str_rtx;
1602 machine_mode mode1;
1604 if (tmode == VOIDmode)
1605 tmode = mode;
1607 while (GET_CODE (op0) == SUBREG)
1609 bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1610 op0 = SUBREG_REG (op0);
1613 /* If we have an out-of-bounds access to a register, just return an
1614 uninitialized register of the required mode. This can occur if the
1615 source code contains an out-of-bounds access to a small array. */
1616 if (REG_P (op0) && known_ge (bitnum, GET_MODE_BITSIZE (GET_MODE (op0))))
1617 return gen_reg_rtx (tmode);
1619 if (REG_P (op0)
1620 && mode == GET_MODE (op0)
1621 && known_eq (bitnum, 0U)
1622 && known_eq (bitsize, GET_MODE_BITSIZE (GET_MODE (op0))))
1624 if (reverse)
1625 op0 = flip_storage_order (mode, op0);
1626 /* We're trying to extract a full register from itself. */
1627 return op0;
1630 /* First try to check for vector from vector extractions. */
1631 if (VECTOR_MODE_P (GET_MODE (op0))
1632 && !MEM_P (op0)
1633 && VECTOR_MODE_P (tmode)
1634 && known_eq (bitsize, GET_MODE_BITSIZE (tmode))
1635 && maybe_gt (GET_MODE_SIZE (GET_MODE (op0)), GET_MODE_SIZE (tmode)))
1637 machine_mode new_mode = GET_MODE (op0);
1638 if (GET_MODE_INNER (new_mode) != GET_MODE_INNER (tmode))
1640 scalar_mode inner_mode = GET_MODE_INNER (tmode);
1641 poly_uint64 nunits;
1642 if (!multiple_p (GET_MODE_BITSIZE (GET_MODE (op0)),
1643 GET_MODE_UNIT_BITSIZE (tmode), &nunits)
1644 || !mode_for_vector (inner_mode, nunits).exists (&new_mode)
1645 || !VECTOR_MODE_P (new_mode)
1646 || maybe_ne (GET_MODE_SIZE (new_mode),
1647 GET_MODE_SIZE (GET_MODE (op0)))
1648 || GET_MODE_INNER (new_mode) != GET_MODE_INNER (tmode)
1649 || !targetm.vector_mode_supported_p (new_mode))
1650 new_mode = VOIDmode;
1652 poly_uint64 pos;
1653 if (new_mode != VOIDmode
1654 && (convert_optab_handler (vec_extract_optab, new_mode, tmode)
1655 != CODE_FOR_nothing)
1656 && multiple_p (bitnum, GET_MODE_BITSIZE (tmode), &pos))
1658 struct expand_operand ops[3];
1659 machine_mode outermode = new_mode;
1660 machine_mode innermode = tmode;
1661 enum insn_code icode
1662 = convert_optab_handler (vec_extract_optab, outermode, innermode);
1664 if (new_mode != GET_MODE (op0))
1665 op0 = gen_lowpart (new_mode, op0);
1666 create_output_operand (&ops[0], target, innermode);
1667 ops[0].target = 1;
1668 create_input_operand (&ops[1], op0, outermode);
1669 create_integer_operand (&ops[2], pos);
1670 if (maybe_expand_insn (icode, 3, ops))
1672 if (alt_rtl && ops[0].target)
1673 *alt_rtl = target;
1674 target = ops[0].value;
1675 if (GET_MODE (target) != mode)
1676 return gen_lowpart (tmode, target);
1677 return target;
1682 /* See if we can get a better vector mode before extracting. */
1683 if (VECTOR_MODE_P (GET_MODE (op0))
1684 && !MEM_P (op0)
1685 && GET_MODE_INNER (GET_MODE (op0)) != tmode)
1687 machine_mode new_mode;
1689 if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1690 new_mode = MIN_MODE_VECTOR_FLOAT;
1691 else if (GET_MODE_CLASS (tmode) == MODE_FRACT)
1692 new_mode = MIN_MODE_VECTOR_FRACT;
1693 else if (GET_MODE_CLASS (tmode) == MODE_UFRACT)
1694 new_mode = MIN_MODE_VECTOR_UFRACT;
1695 else if (GET_MODE_CLASS (tmode) == MODE_ACCUM)
1696 new_mode = MIN_MODE_VECTOR_ACCUM;
1697 else if (GET_MODE_CLASS (tmode) == MODE_UACCUM)
1698 new_mode = MIN_MODE_VECTOR_UACCUM;
1699 else
1700 new_mode = MIN_MODE_VECTOR_INT;
1702 FOR_EACH_MODE_FROM (new_mode, new_mode)
1703 if (known_eq (GET_MODE_SIZE (new_mode), GET_MODE_SIZE (GET_MODE (op0)))
1704 && known_eq (GET_MODE_UNIT_SIZE (new_mode), GET_MODE_SIZE (tmode))
1705 && targetm.vector_mode_supported_p (new_mode))
1706 break;
1707 if (new_mode != VOIDmode)
1708 op0 = gen_lowpart (new_mode, op0);
1711 /* Use vec_extract patterns for extracting parts of vectors whenever
1712 available. If that fails, see whether the current modes and bitregion
1713 give a natural subreg. */
1714 machine_mode outermode = GET_MODE (op0);
1715 if (VECTOR_MODE_P (outermode) && !MEM_P (op0))
1717 scalar_mode innermode = GET_MODE_INNER (outermode);
1718 enum insn_code icode
1719 = convert_optab_handler (vec_extract_optab, outermode, innermode);
1720 poly_uint64 pos;
1721 if (icode != CODE_FOR_nothing
1722 && known_eq (bitsize, GET_MODE_BITSIZE (innermode))
1723 && multiple_p (bitnum, GET_MODE_BITSIZE (innermode), &pos))
1725 struct expand_operand ops[3];
1727 create_output_operand (&ops[0], target, innermode);
1728 ops[0].target = 1;
1729 create_input_operand (&ops[1], op0, outermode);
1730 create_integer_operand (&ops[2], pos);
1731 if (maybe_expand_insn (icode, 3, ops))
1733 if (alt_rtl && ops[0].target)
1734 *alt_rtl = target;
1735 target = ops[0].value;
1736 if (GET_MODE (target) != mode)
1737 return gen_lowpart (tmode, target);
1738 return target;
1741 /* Using subregs is useful if we're extracting one register vector
1742 from a multi-register vector. extract_bit_field_as_subreg checks
1743 for valid bitsize and bitnum, so we don't need to do that here. */
1744 if (VECTOR_MODE_P (mode))
1746 rtx sub = extract_bit_field_as_subreg (mode, op0, bitsize, bitnum);
1747 if (sub)
1748 return sub;
1752 /* Make sure we are playing with integral modes. Pun with subregs
1753 if we aren't. */
1754 opt_scalar_int_mode op0_mode = int_mode_for_mode (GET_MODE (op0));
1755 scalar_int_mode imode;
1756 if (!op0_mode.exists (&imode) || imode != GET_MODE (op0))
1758 if (MEM_P (op0))
1759 op0 = adjust_bitfield_address_size (op0, op0_mode.else_blk (),
1760 0, MEM_SIZE (op0));
1761 else if (op0_mode.exists (&imode))
1763 op0 = gen_lowpart (imode, op0);
1765 /* If we got a SUBREG, force it into a register since we
1766 aren't going to be able to do another SUBREG on it. */
1767 if (GET_CODE (op0) == SUBREG)
1768 op0 = force_reg (imode, op0);
1770 else
1772 poly_int64 size = GET_MODE_SIZE (GET_MODE (op0));
1773 rtx mem = assign_stack_temp (GET_MODE (op0), size);
1774 emit_move_insn (mem, op0);
1775 op0 = adjust_bitfield_address_size (mem, BLKmode, 0, size);
1779 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1780 If that's wrong, the solution is to test for it and set TARGET to 0
1781 if needed. */
1783 /* Get the mode of the field to use for atomic access or subreg
1784 conversion. */
1785 if (!SCALAR_INT_MODE_P (tmode)
1786 || !mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0).exists (&mode1))
1787 mode1 = mode;
1788 gcc_assert (mode1 != BLKmode);
1790 /* Extraction of a full MODE1 value can be done with a subreg as long
1791 as the least significant bit of the value is the least significant
1792 bit of either OP0 or a word of OP0. */
1793 if (!MEM_P (op0) && !reverse)
1795 rtx sub = extract_bit_field_as_subreg (mode1, op0, bitsize, bitnum);
1796 if (sub)
1797 return convert_extracted_bit_field (sub, mode, tmode, unsignedp);
1800 /* Extraction of a full MODE1 value can be done with a load as long as
1801 the field is on a byte boundary and is sufficiently aligned. */
1802 poly_uint64 bytenum;
1803 if (simple_mem_bitfield_p (op0, bitsize, bitnum, mode1, &bytenum))
1805 op0 = adjust_bitfield_address (op0, mode1, bytenum);
1806 if (reverse)
1807 op0 = flip_storage_order (mode1, op0);
1808 return convert_extracted_bit_field (op0, mode, tmode, unsignedp);
1811 /* If we have a memory source and a non-constant bit offset, restrict
1812 the memory to the referenced bytes. This is a worst-case fallback
1813 but is useful for things like vector booleans. */
1814 if (MEM_P (op0) && !bitnum.is_constant ())
1816 bytenum = bits_to_bytes_round_down (bitnum);
1817 bitnum = num_trailing_bits (bitnum);
1818 poly_uint64 bytesize = bits_to_bytes_round_up (bitnum + bitsize);
1819 op0 = adjust_bitfield_address_size (op0, BLKmode, bytenum, bytesize);
1820 op0_mode = opt_scalar_int_mode ();
1823 /* It's possible we'll need to handle other cases here for
1824 polynomial bitnum and bitsize. */
1826 /* From here on we need to be looking at a fixed-size insertion. */
1827 return extract_integral_bit_field (op0, op0_mode, bitsize.to_constant (),
1828 bitnum.to_constant (), unsignedp,
1829 target, mode, tmode, reverse, fallback_p);
1832 /* Subroutine of extract_bit_field_1, with the same arguments, except
1833 that BITSIZE and BITNUM are constant. Handle cases specific to
1834 integral modes. If OP0_MODE is defined, it is the mode of OP0,
1835 otherwise OP0 is a BLKmode MEM. */
1837 static rtx
1838 extract_integral_bit_field (rtx op0, opt_scalar_int_mode op0_mode,
1839 unsigned HOST_WIDE_INT bitsize,
1840 unsigned HOST_WIDE_INT bitnum, int unsignedp,
1841 rtx target, machine_mode mode, machine_mode tmode,
1842 bool reverse, bool fallback_p)
1844 /* Handle fields bigger than a word. */
1846 if (bitsize > BITS_PER_WORD)
1848 /* Here we transfer the words of the field
1849 in the order least significant first.
1850 This is because the most significant word is the one which may
1851 be less than full. */
1853 const bool backwards = WORDS_BIG_ENDIAN;
1854 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1855 unsigned int i;
1856 rtx_insn *last;
1858 if (target == 0 || !REG_P (target) || !valid_multiword_target_p (target))
1859 target = gen_reg_rtx (mode);
1861 /* In case we're about to clobber a base register or something
1862 (see gcc.c-torture/execute/20040625-1.c). */
1863 if (reg_mentioned_p (target, op0))
1864 target = gen_reg_rtx (mode);
1866 /* Indicate for flow that the entire target reg is being set. */
1867 emit_clobber (target);
1869 /* The mode must be fixed-size, since extract_bit_field_1 handles
1870 extractions from variable-sized objects before calling this
1871 function. */
1872 unsigned int target_size
1873 = GET_MODE_SIZE (GET_MODE (target)).to_constant ();
1874 last = get_last_insn ();
1875 for (i = 0; i < nwords; i++)
1877 /* If I is 0, use the low-order word in both field and target;
1878 if I is 1, use the next to lowest word; and so on. */
1879 /* Word number in TARGET to use. */
1880 unsigned int wordnum
1881 = (backwards ? target_size / UNITS_PER_WORD - i - 1 : i);
1882 /* Offset from start of field in OP0. */
1883 unsigned int bit_offset = (backwards ^ reverse
1884 ? MAX ((int) bitsize - ((int) i + 1)
1885 * BITS_PER_WORD,
1887 : (int) i * BITS_PER_WORD);
1888 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1889 rtx result_part
1890 = extract_bit_field_1 (op0, MIN (BITS_PER_WORD,
1891 bitsize - i * BITS_PER_WORD),
1892 bitnum + bit_offset, 1, target_part,
1893 mode, word_mode, reverse, fallback_p, NULL);
1895 gcc_assert (target_part);
1896 if (!result_part)
1898 delete_insns_since (last);
1899 return NULL;
1902 if (result_part != target_part)
1903 emit_move_insn (target_part, result_part);
1906 if (unsignedp)
1908 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1909 need to be zero'd out. */
1910 if (target_size > nwords * UNITS_PER_WORD)
1912 unsigned int i, total_words;
1914 total_words = target_size / UNITS_PER_WORD;
1915 for (i = nwords; i < total_words; i++)
1916 emit_move_insn
1917 (operand_subword (target,
1918 backwards ? total_words - i - 1 : i,
1919 1, VOIDmode),
1920 const0_rtx);
1922 return target;
1925 /* Signed bit field: sign-extend with two arithmetic shifts. */
1926 target = expand_shift (LSHIFT_EXPR, mode, target,
1927 GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1928 return expand_shift (RSHIFT_EXPR, mode, target,
1929 GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1932 /* If OP0 is a multi-word register, narrow it to the affected word.
1933 If the region spans two words, defer to extract_split_bit_field. */
1934 if (!MEM_P (op0) && GET_MODE_SIZE (op0_mode.require ()) > UNITS_PER_WORD)
1936 if (bitnum % BITS_PER_WORD + bitsize > BITS_PER_WORD)
1938 if (!fallback_p)
1939 return NULL_RTX;
1940 target = extract_split_bit_field (op0, op0_mode, bitsize, bitnum,
1941 unsignedp, reverse);
1942 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1944 op0 = simplify_gen_subreg (word_mode, op0, op0_mode.require (),
1945 bitnum / BITS_PER_WORD * UNITS_PER_WORD);
1946 op0_mode = word_mode;
1947 bitnum %= BITS_PER_WORD;
1950 /* From here on we know the desired field is smaller than a word.
1951 If OP0 is a register, it too fits within a word. */
1952 enum extraction_pattern pattern = unsignedp ? EP_extzv : EP_extv;
1953 extraction_insn extv;
1954 if (!MEM_P (op0)
1955 && !reverse
1956 /* ??? We could limit the structure size to the part of OP0 that
1957 contains the field, with appropriate checks for endianness
1958 and TARGET_TRULY_NOOP_TRUNCATION. */
1959 && get_best_reg_extraction_insn (&extv, pattern,
1960 GET_MODE_BITSIZE (op0_mode.require ()),
1961 tmode))
1963 rtx result = extract_bit_field_using_extv (&extv, op0, op0_mode,
1964 bitsize, bitnum,
1965 unsignedp, target, mode,
1966 tmode);
1967 if (result)
1968 return result;
1971 /* If OP0 is a memory, try copying it to a register and seeing if a
1972 cheap register alternative is available. */
1973 if (MEM_P (op0) & !reverse)
1975 if (get_best_mem_extraction_insn (&extv, pattern, bitsize, bitnum,
1976 tmode))
1978 rtx result = extract_bit_field_using_extv (&extv, op0, op0_mode,
1979 bitsize, bitnum,
1980 unsignedp, target, mode,
1981 tmode);
1982 if (result)
1983 return result;
1986 rtx_insn *last = get_last_insn ();
1988 /* Try loading part of OP0 into a register and extracting the
1989 bitfield from that. */
1990 unsigned HOST_WIDE_INT bitpos;
1991 rtx xop0 = adjust_bit_field_mem_for_reg (pattern, op0, bitsize, bitnum,
1992 0, 0, tmode, &bitpos);
1993 if (xop0)
1995 xop0 = copy_to_reg (xop0);
1996 rtx result = extract_bit_field_1 (xop0, bitsize, bitpos,
1997 unsignedp, target,
1998 mode, tmode, reverse, false, NULL);
1999 if (result)
2000 return result;
2001 delete_insns_since (last);
2005 if (!fallback_p)
2006 return NULL;
2008 /* Find a correspondingly-sized integer field, so we can apply
2009 shifts and masks to it. */
2010 scalar_int_mode int_mode;
2011 if (!int_mode_for_mode (tmode).exists (&int_mode))
2012 /* If this fails, we should probably push op0 out to memory and then
2013 do a load. */
2014 int_mode = int_mode_for_mode (mode).require ();
2016 target = extract_fixed_bit_field (int_mode, op0, op0_mode, bitsize,
2017 bitnum, target, unsignedp, reverse);
2019 /* Complex values must be reversed piecewise, so we need to undo the global
2020 reversal, convert to the complex mode and reverse again. */
2021 if (reverse && COMPLEX_MODE_P (tmode))
2023 target = flip_storage_order (int_mode, target);
2024 target = convert_extracted_bit_field (target, mode, tmode, unsignedp);
2025 target = flip_storage_order (tmode, target);
2027 else
2028 target = convert_extracted_bit_field (target, mode, tmode, unsignedp);
2030 return target;
2033 /* Generate code to extract a byte-field from STR_RTX
2034 containing BITSIZE bits, starting at BITNUM,
2035 and put it in TARGET if possible (if TARGET is nonzero).
2036 Regardless of TARGET, we return the rtx for where the value is placed.
2038 STR_RTX is the structure containing the byte (a REG or MEM).
2039 UNSIGNEDP is nonzero if this is an unsigned bit field.
2040 MODE is the natural mode of the field value once extracted.
2041 TMODE is the mode the caller would like the value to have;
2042 but the value may be returned with type MODE instead.
2044 If REVERSE is true, the extraction is to be done in reverse order.
2046 If a TARGET is specified and we can store in it at no extra cost,
2047 we do so, and return TARGET.
2048 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
2049 if they are equally easy. */
2052 extract_bit_field (rtx str_rtx, poly_uint64 bitsize, poly_uint64 bitnum,
2053 int unsignedp, rtx target, machine_mode mode,
2054 machine_mode tmode, bool reverse, rtx *alt_rtl)
2056 machine_mode mode1;
2058 /* Handle -fstrict-volatile-bitfields in the cases where it applies. */
2059 if (maybe_ne (GET_MODE_BITSIZE (GET_MODE (str_rtx)), 0))
2060 mode1 = GET_MODE (str_rtx);
2061 else if (target && maybe_ne (GET_MODE_BITSIZE (GET_MODE (target)), 0))
2062 mode1 = GET_MODE (target);
2063 else
2064 mode1 = tmode;
2066 unsigned HOST_WIDE_INT ibitsize, ibitnum;
2067 scalar_int_mode int_mode;
2068 if (bitsize.is_constant (&ibitsize)
2069 && bitnum.is_constant (&ibitnum)
2070 && is_a <scalar_int_mode> (mode1, &int_mode)
2071 && strict_volatile_bitfield_p (str_rtx, ibitsize, ibitnum,
2072 int_mode, 0, 0))
2074 /* Extraction of a full INT_MODE value can be done with a simple load.
2075 We know here that the field can be accessed with one single
2076 instruction. For targets that support unaligned memory,
2077 an unaligned access may be necessary. */
2078 if (ibitsize == GET_MODE_BITSIZE (int_mode))
2080 rtx result = adjust_bitfield_address (str_rtx, int_mode,
2081 ibitnum / BITS_PER_UNIT);
2082 if (reverse)
2083 result = flip_storage_order (int_mode, result);
2084 gcc_assert (ibitnum % BITS_PER_UNIT == 0);
2085 return convert_extracted_bit_field (result, mode, tmode, unsignedp);
2088 str_rtx = narrow_bit_field_mem (str_rtx, int_mode, ibitsize, ibitnum,
2089 &ibitnum);
2090 gcc_assert (ibitnum + ibitsize <= GET_MODE_BITSIZE (int_mode));
2091 str_rtx = copy_to_reg (str_rtx);
2092 return extract_bit_field_1 (str_rtx, ibitsize, ibitnum, unsignedp,
2093 target, mode, tmode, reverse, true, alt_rtl);
2096 return extract_bit_field_1 (str_rtx, bitsize, bitnum, unsignedp,
2097 target, mode, tmode, reverse, true, alt_rtl);
2100 /* Use shifts and boolean operations to extract a field of BITSIZE bits
2101 from bit BITNUM of OP0. If OP0_MODE is defined, it is the mode of OP0,
2102 otherwise OP0 is a BLKmode MEM.
2104 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
2105 If REVERSE is true, the extraction is to be done in reverse order.
2107 If TARGET is nonzero, attempts to store the value there
2108 and return TARGET, but this is not guaranteed.
2109 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
2111 static rtx
2112 extract_fixed_bit_field (machine_mode tmode, rtx op0,
2113 opt_scalar_int_mode op0_mode,
2114 unsigned HOST_WIDE_INT bitsize,
2115 unsigned HOST_WIDE_INT bitnum, rtx target,
2116 int unsignedp, bool reverse)
2118 scalar_int_mode mode;
2119 if (MEM_P (op0))
2121 if (!get_best_mode (bitsize, bitnum, 0, 0, MEM_ALIGN (op0),
2122 BITS_PER_WORD, MEM_VOLATILE_P (op0), &mode))
2123 /* The only way this should occur is if the field spans word
2124 boundaries. */
2125 return extract_split_bit_field (op0, op0_mode, bitsize, bitnum,
2126 unsignedp, reverse);
2128 op0 = narrow_bit_field_mem (op0, mode, bitsize, bitnum, &bitnum);
2130 else
2131 mode = op0_mode.require ();
2133 return extract_fixed_bit_field_1 (tmode, op0, mode, bitsize, bitnum,
2134 target, unsignedp, reverse);
2137 /* Helper function for extract_fixed_bit_field, extracts
2138 the bit field always using MODE, which is the mode of OP0.
2139 The other arguments are as for extract_fixed_bit_field. */
2141 static rtx
2142 extract_fixed_bit_field_1 (machine_mode tmode, rtx op0, scalar_int_mode mode,
2143 unsigned HOST_WIDE_INT bitsize,
2144 unsigned HOST_WIDE_INT bitnum, rtx target,
2145 int unsignedp, bool reverse)
2147 /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
2148 for invalid input, such as extract equivalent of f5 from
2149 gcc.dg/pr48335-2.c. */
2151 if (reverse ? !BYTES_BIG_ENDIAN : BYTES_BIG_ENDIAN)
2152 /* BITNUM is the distance between our msb and that of OP0.
2153 Convert it to the distance from the lsb. */
2154 bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
2156 /* Now BITNUM is always the distance between the field's lsb and that of OP0.
2157 We have reduced the big-endian case to the little-endian case. */
2158 if (reverse)
2159 op0 = flip_storage_order (mode, op0);
2161 if (unsignedp)
2163 if (bitnum)
2165 /* If the field does not already start at the lsb,
2166 shift it so it does. */
2167 /* Maybe propagate the target for the shift. */
2168 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
2169 if (tmode != mode)
2170 subtarget = 0;
2171 op0 = expand_shift (RSHIFT_EXPR, mode, op0, bitnum, subtarget, 1);
2173 /* Convert the value to the desired mode. TMODE must also be a
2174 scalar integer for this conversion to make sense, since we
2175 shouldn't reinterpret the bits. */
2176 scalar_int_mode new_mode = as_a <scalar_int_mode> (tmode);
2177 if (mode != new_mode)
2178 op0 = convert_to_mode (new_mode, op0, 1);
2180 /* Unless the msb of the field used to be the msb when we shifted,
2181 mask out the upper bits. */
2183 if (GET_MODE_BITSIZE (mode) != bitnum + bitsize)
2184 return expand_binop (new_mode, and_optab, op0,
2185 mask_rtx (new_mode, 0, bitsize, 0),
2186 target, 1, OPTAB_LIB_WIDEN);
2187 return op0;
2190 /* To extract a signed bit-field, first shift its msb to the msb of the word,
2191 then arithmetic-shift its lsb to the lsb of the word. */
2192 op0 = force_reg (mode, op0);
2194 /* Find the narrowest integer mode that contains the field. */
2196 opt_scalar_int_mode mode_iter;
2197 FOR_EACH_MODE_IN_CLASS (mode_iter, MODE_INT)
2198 if (GET_MODE_BITSIZE (mode_iter.require ()) >= bitsize + bitnum)
2199 break;
2201 mode = mode_iter.require ();
2202 op0 = convert_to_mode (mode, op0, 0);
2204 if (mode != tmode)
2205 target = 0;
2207 if (GET_MODE_BITSIZE (mode) != (bitsize + bitnum))
2209 int amount = GET_MODE_BITSIZE (mode) - (bitsize + bitnum);
2210 /* Maybe propagate the target for the shift. */
2211 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
2212 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
2215 return expand_shift (RSHIFT_EXPR, mode, op0,
2216 GET_MODE_BITSIZE (mode) - bitsize, target, 0);
2219 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
2220 VALUE << BITPOS. */
2222 static rtx
2223 lshift_value (machine_mode mode, unsigned HOST_WIDE_INT value,
2224 int bitpos)
2226 return immed_wide_int_const (wi::lshift (value, bitpos), mode);
2229 /* Extract a bit field that is split across two words
2230 and return an RTX for the result.
2232 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
2233 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
2234 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.
2235 If OP0_MODE is defined, it is the mode of OP0, otherwise OP0 is
2236 a BLKmode MEM.
2238 If REVERSE is true, the extraction is to be done in reverse order. */
2240 static rtx
2241 extract_split_bit_field (rtx op0, opt_scalar_int_mode op0_mode,
2242 unsigned HOST_WIDE_INT bitsize,
2243 unsigned HOST_WIDE_INT bitpos, int unsignedp,
2244 bool reverse)
2246 unsigned int unit;
2247 unsigned int bitsdone = 0;
2248 rtx result = NULL_RTX;
2249 int first = 1;
2251 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
2252 much at a time. */
2253 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
2254 unit = BITS_PER_WORD;
2255 else
2256 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
2258 while (bitsdone < bitsize)
2260 unsigned HOST_WIDE_INT thissize;
2261 rtx part;
2262 unsigned HOST_WIDE_INT thispos;
2263 unsigned HOST_WIDE_INT offset;
2265 offset = (bitpos + bitsdone) / unit;
2266 thispos = (bitpos + bitsdone) % unit;
2268 /* THISSIZE must not overrun a word boundary. Otherwise,
2269 extract_fixed_bit_field will call us again, and we will mutually
2270 recurse forever. */
2271 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
2272 thissize = MIN (thissize, unit - thispos);
2274 /* If OP0 is a register, then handle OFFSET here. */
2275 rtx op0_piece = op0;
2276 opt_scalar_int_mode op0_piece_mode = op0_mode;
2277 if (SUBREG_P (op0) || REG_P (op0))
2279 op0_piece = operand_subword_force (op0, offset, op0_mode.require ());
2280 op0_piece_mode = word_mode;
2281 offset = 0;
2284 /* Extract the parts in bit-counting order,
2285 whose meaning is determined by BYTES_PER_UNIT.
2286 OFFSET is in UNITs, and UNIT is in bits. */
2287 part = extract_fixed_bit_field (word_mode, op0_piece, op0_piece_mode,
2288 thissize, offset * unit + thispos,
2289 0, 1, reverse);
2290 bitsdone += thissize;
2292 /* Shift this part into place for the result. */
2293 if (reverse ? !BYTES_BIG_ENDIAN : BYTES_BIG_ENDIAN)
2295 if (bitsize != bitsdone)
2296 part = expand_shift (LSHIFT_EXPR, word_mode, part,
2297 bitsize - bitsdone, 0, 1);
2299 else
2301 if (bitsdone != thissize)
2302 part = expand_shift (LSHIFT_EXPR, word_mode, part,
2303 bitsdone - thissize, 0, 1);
2306 if (first)
2307 result = part;
2308 else
2309 /* Combine the parts with bitwise or. This works
2310 because we extracted each part as an unsigned bit field. */
2311 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
2312 OPTAB_LIB_WIDEN);
2314 first = 0;
2317 /* Unsigned bit field: we are done. */
2318 if (unsignedp)
2319 return result;
2320 /* Signed bit field: sign-extend with two arithmetic shifts. */
2321 result = expand_shift (LSHIFT_EXPR, word_mode, result,
2322 BITS_PER_WORD - bitsize, NULL_RTX, 0);
2323 return expand_shift (RSHIFT_EXPR, word_mode, result,
2324 BITS_PER_WORD - bitsize, NULL_RTX, 0);
2327 /* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
2328 the bit pattern. SRC_MODE is the mode of SRC; if this is smaller than
2329 MODE, fill the upper bits with zeros. Fail if the layout of either
2330 mode is unknown (as for CC modes) or if the extraction would involve
2331 unprofitable mode punning. Return the value on success, otherwise
2332 return null.
2334 This is different from gen_lowpart* in these respects:
2336 - the returned value must always be considered an rvalue
2338 - when MODE is wider than SRC_MODE, the extraction involves
2339 a zero extension
2341 - when MODE is smaller than SRC_MODE, the extraction involves
2342 a truncation (and is thus subject to TARGET_TRULY_NOOP_TRUNCATION).
2344 In other words, this routine performs a computation, whereas the
2345 gen_lowpart* routines are conceptually lvalue or rvalue subreg
2346 operations. */
2349 extract_low_bits (machine_mode mode, machine_mode src_mode, rtx src)
2351 scalar_int_mode int_mode, src_int_mode;
2353 if (mode == src_mode)
2354 return src;
2356 if (CONSTANT_P (src))
2358 /* simplify_gen_subreg can't be used here, as if simplify_subreg
2359 fails, it will happily create (subreg (symbol_ref)) or similar
2360 invalid SUBREGs. */
2361 poly_uint64 byte = subreg_lowpart_offset (mode, src_mode);
2362 rtx ret = simplify_subreg (mode, src, src_mode, byte);
2363 if (ret)
2364 return ret;
2366 if (GET_MODE (src) == VOIDmode
2367 || !validate_subreg (mode, src_mode, src, byte))
2368 return NULL_RTX;
2370 src = force_reg (GET_MODE (src), src);
2371 return gen_rtx_SUBREG (mode, src, byte);
2374 if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
2375 return NULL_RTX;
2377 if (known_eq (GET_MODE_BITSIZE (mode), GET_MODE_BITSIZE (src_mode))
2378 && targetm.modes_tieable_p (mode, src_mode))
2380 rtx x = gen_lowpart_common (mode, src);
2381 if (x)
2382 return x;
2385 if (!int_mode_for_mode (src_mode).exists (&src_int_mode)
2386 || !int_mode_for_mode (mode).exists (&int_mode))
2387 return NULL_RTX;
2389 if (!targetm.modes_tieable_p (src_int_mode, src_mode))
2390 return NULL_RTX;
2391 if (!targetm.modes_tieable_p (int_mode, mode))
2392 return NULL_RTX;
2394 src = gen_lowpart (src_int_mode, src);
2395 if (!validate_subreg (int_mode, src_int_mode, src,
2396 subreg_lowpart_offset (int_mode, src_int_mode)))
2397 return NULL_RTX;
2399 src = convert_modes (int_mode, src_int_mode, src, true);
2400 src = gen_lowpart (mode, src);
2401 return src;
2404 /* Add INC into TARGET. */
2406 void
2407 expand_inc (rtx target, rtx inc)
2409 rtx value = expand_binop (GET_MODE (target), add_optab,
2410 target, inc,
2411 target, 0, OPTAB_LIB_WIDEN);
2412 if (value != target)
2413 emit_move_insn (target, value);
2416 /* Subtract DEC from TARGET. */
2418 void
2419 expand_dec (rtx target, rtx dec)
2421 rtx value = expand_binop (GET_MODE (target), sub_optab,
2422 target, dec,
2423 target, 0, OPTAB_LIB_WIDEN);
2424 if (value != target)
2425 emit_move_insn (target, value);
2428 /* Output a shift instruction for expression code CODE,
2429 with SHIFTED being the rtx for the value to shift,
2430 and AMOUNT the rtx for the amount to shift by.
2431 Store the result in the rtx TARGET, if that is convenient.
2432 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2433 Return the rtx for where the value is.
2434 If that cannot be done, abort the compilation unless MAY_FAIL is true,
2435 in which case 0 is returned. */
2437 static rtx
2438 expand_shift_1 (enum tree_code code, machine_mode mode, rtx shifted,
2439 rtx amount, rtx target, int unsignedp, bool may_fail = false)
2441 rtx op1, temp = 0;
2442 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2443 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2444 optab lshift_optab = ashl_optab;
2445 optab rshift_arith_optab = ashr_optab;
2446 optab rshift_uns_optab = lshr_optab;
2447 optab lrotate_optab = rotl_optab;
2448 optab rrotate_optab = rotr_optab;
2449 machine_mode op1_mode;
2450 scalar_mode scalar_mode = GET_MODE_INNER (mode);
2451 int attempt;
2452 bool speed = optimize_insn_for_speed_p ();
2454 op1 = amount;
2455 op1_mode = GET_MODE (op1);
2457 /* Determine whether the shift/rotate amount is a vector, or scalar. If the
2458 shift amount is a vector, use the vector/vector shift patterns. */
2459 if (VECTOR_MODE_P (mode) && VECTOR_MODE_P (op1_mode))
2461 lshift_optab = vashl_optab;
2462 rshift_arith_optab = vashr_optab;
2463 rshift_uns_optab = vlshr_optab;
2464 lrotate_optab = vrotl_optab;
2465 rrotate_optab = vrotr_optab;
2468 /* Previously detected shift-counts computed by NEGATE_EXPR
2469 and shifted in the other direction; but that does not work
2470 on all machines. */
2472 if (SHIFT_COUNT_TRUNCATED)
2474 if (CONST_INT_P (op1)
2475 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2476 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (scalar_mode)))
2477 op1 = gen_int_shift_amount (mode,
2478 (unsigned HOST_WIDE_INT) INTVAL (op1)
2479 % GET_MODE_BITSIZE (scalar_mode));
2480 else if (GET_CODE (op1) == SUBREG
2481 && subreg_lowpart_p (op1)
2482 && SCALAR_INT_MODE_P (GET_MODE (SUBREG_REG (op1)))
2483 && SCALAR_INT_MODE_P (GET_MODE (op1)))
2484 op1 = SUBREG_REG (op1);
2487 /* Canonicalize rotates by constant amount. If op1 is bitsize / 2,
2488 prefer left rotation, if op1 is from bitsize / 2 + 1 to
2489 bitsize - 1, use other direction of rotate with 1 .. bitsize / 2 - 1
2490 amount instead. */
2491 if (rotate
2492 && CONST_INT_P (op1)
2493 && IN_RANGE (INTVAL (op1), GET_MODE_BITSIZE (scalar_mode) / 2 + left,
2494 GET_MODE_BITSIZE (scalar_mode) - 1))
2496 op1 = gen_int_shift_amount (mode, (GET_MODE_BITSIZE (scalar_mode)
2497 - INTVAL (op1)));
2498 left = !left;
2499 code = left ? LROTATE_EXPR : RROTATE_EXPR;
2502 /* Rotation of 16bit values by 8 bits is effectively equivalent to a bswaphi.
2503 Note that this is not the case for bigger values. For instance a rotation
2504 of 0x01020304 by 16 bits gives 0x03040102 which is different from
2505 0x04030201 (bswapsi). */
2506 if (rotate
2507 && CONST_INT_P (op1)
2508 && INTVAL (op1) == BITS_PER_UNIT
2509 && GET_MODE_SIZE (scalar_mode) == 2
2510 && optab_handler (bswap_optab, mode) != CODE_FOR_nothing)
2511 return expand_unop (mode, bswap_optab, shifted, NULL_RTX, unsignedp);
2513 if (op1 == const0_rtx)
2514 return shifted;
2516 /* Check whether its cheaper to implement a left shift by a constant
2517 bit count by a sequence of additions. */
2518 if (code == LSHIFT_EXPR
2519 && CONST_INT_P (op1)
2520 && INTVAL (op1) > 0
2521 && INTVAL (op1) < GET_MODE_PRECISION (scalar_mode)
2522 && INTVAL (op1) < MAX_BITS_PER_WORD
2523 && (shift_cost (speed, mode, INTVAL (op1))
2524 > INTVAL (op1) * add_cost (speed, mode))
2525 && shift_cost (speed, mode, INTVAL (op1)) != MAX_COST)
2527 int i;
2528 for (i = 0; i < INTVAL (op1); i++)
2530 temp = force_reg (mode, shifted);
2531 shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2532 unsignedp, OPTAB_LIB_WIDEN);
2534 return shifted;
2537 for (attempt = 0; temp == 0 && attempt < 3; attempt++)
2539 enum optab_methods methods;
2541 if (attempt == 0)
2542 methods = OPTAB_DIRECT;
2543 else if (attempt == 1)
2544 methods = OPTAB_WIDEN;
2545 else
2546 methods = OPTAB_LIB_WIDEN;
2548 if (rotate)
2550 /* Widening does not work for rotation. */
2551 if (methods == OPTAB_WIDEN)
2552 continue;
2553 else if (methods == OPTAB_LIB_WIDEN)
2555 /* If we have been unable to open-code this by a rotation,
2556 do it as the IOR of two shifts. I.e., to rotate A
2557 by N bits, compute
2558 (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
2559 where C is the bitsize of A.
2561 It is theoretically possible that the target machine might
2562 not be able to perform either shift and hence we would
2563 be making two libcalls rather than just the one for the
2564 shift (similarly if IOR could not be done). We will allow
2565 this extremely unlikely lossage to avoid complicating the
2566 code below. */
2568 rtx subtarget = target == shifted ? 0 : target;
2569 rtx new_amount, other_amount;
2570 rtx temp1;
2572 new_amount = op1;
2573 if (op1 == const0_rtx)
2574 return shifted;
2575 else if (CONST_INT_P (op1))
2576 other_amount = gen_int_shift_amount
2577 (mode, GET_MODE_BITSIZE (scalar_mode) - INTVAL (op1));
2578 else
2580 other_amount
2581 = simplify_gen_unary (NEG, GET_MODE (op1),
2582 op1, GET_MODE (op1));
2583 HOST_WIDE_INT mask = GET_MODE_PRECISION (scalar_mode) - 1;
2584 other_amount
2585 = simplify_gen_binary (AND, GET_MODE (op1), other_amount,
2586 gen_int_mode (mask, GET_MODE (op1)));
2589 shifted = force_reg (mode, shifted);
2591 temp = expand_shift_1 (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2592 mode, shifted, new_amount, 0, 1);
2593 temp1 = expand_shift_1 (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2594 mode, shifted, other_amount,
2595 subtarget, 1);
2596 return expand_binop (mode, ior_optab, temp, temp1, target,
2597 unsignedp, methods);
2600 temp = expand_binop (mode,
2601 left ? lrotate_optab : rrotate_optab,
2602 shifted, op1, target, unsignedp, methods);
2604 else if (unsignedp)
2605 temp = expand_binop (mode,
2606 left ? lshift_optab : rshift_uns_optab,
2607 shifted, op1, target, unsignedp, methods);
2609 /* Do arithmetic shifts.
2610 Also, if we are going to widen the operand, we can just as well
2611 use an arithmetic right-shift instead of a logical one. */
2612 if (temp == 0 && ! rotate
2613 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2615 enum optab_methods methods1 = methods;
2617 /* If trying to widen a log shift to an arithmetic shift,
2618 don't accept an arithmetic shift of the same size. */
2619 if (unsignedp)
2620 methods1 = OPTAB_MUST_WIDEN;
2622 /* Arithmetic shift */
2624 temp = expand_binop (mode,
2625 left ? lshift_optab : rshift_arith_optab,
2626 shifted, op1, target, unsignedp, methods1);
2629 /* We used to try extzv here for logical right shifts, but that was
2630 only useful for one machine, the VAX, and caused poor code
2631 generation there for lshrdi3, so the code was deleted and a
2632 define_expand for lshrsi3 was added to vax.md. */
2635 gcc_assert (temp != NULL_RTX || may_fail);
2636 return temp;
2639 /* Output a shift instruction for expression code CODE,
2640 with SHIFTED being the rtx for the value to shift,
2641 and AMOUNT the amount to shift by.
2642 Store the result in the rtx TARGET, if that is convenient.
2643 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2644 Return the rtx for where the value is. */
2647 expand_shift (enum tree_code code, machine_mode mode, rtx shifted,
2648 poly_int64 amount, rtx target, int unsignedp)
2650 return expand_shift_1 (code, mode, shifted,
2651 gen_int_shift_amount (mode, amount),
2652 target, unsignedp);
2655 /* Likewise, but return 0 if that cannot be done. */
2657 static rtx
2658 maybe_expand_shift (enum tree_code code, machine_mode mode, rtx shifted,
2659 int amount, rtx target, int unsignedp)
2661 return expand_shift_1 (code, mode,
2662 shifted, GEN_INT (amount), target, unsignedp, true);
2665 /* Output a shift instruction for expression code CODE,
2666 with SHIFTED being the rtx for the value to shift,
2667 and AMOUNT the tree for the amount to shift by.
2668 Store the result in the rtx TARGET, if that is convenient.
2669 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2670 Return the rtx for where the value is. */
2673 expand_variable_shift (enum tree_code code, machine_mode mode, rtx shifted,
2674 tree amount, rtx target, int unsignedp)
2676 return expand_shift_1 (code, mode,
2677 shifted, expand_normal (amount), target, unsignedp);
2681 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2682 const struct mult_cost *, machine_mode mode);
2683 static rtx expand_mult_const (machine_mode, rtx, HOST_WIDE_INT, rtx,
2684 const struct algorithm *, enum mult_variant);
2685 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2686 static rtx extract_high_half (scalar_int_mode, rtx);
2687 static rtx expmed_mult_highpart (scalar_int_mode, rtx, rtx, rtx, int, int);
2688 static rtx expmed_mult_highpart_optab (scalar_int_mode, rtx, rtx, rtx,
2689 int, int);
2690 /* Compute and return the best algorithm for multiplying by T.
2691 The algorithm must cost less than cost_limit
2692 If retval.cost >= COST_LIMIT, no algorithm was found and all
2693 other field of the returned struct are undefined.
2694 MODE is the machine mode of the multiplication. */
2696 static void
2697 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2698 const struct mult_cost *cost_limit, machine_mode mode)
2700 int m;
2701 struct algorithm *alg_in, *best_alg;
2702 struct mult_cost best_cost;
2703 struct mult_cost new_limit;
2704 int op_cost, op_latency;
2705 unsigned HOST_WIDE_INT orig_t = t;
2706 unsigned HOST_WIDE_INT q;
2707 int maxm, hash_index;
2708 bool cache_hit = false;
2709 enum alg_code cache_alg = alg_zero;
2710 bool speed = optimize_insn_for_speed_p ();
2711 scalar_int_mode imode;
2712 struct alg_hash_entry *entry_ptr;
2714 /* Indicate that no algorithm is yet found. If no algorithm
2715 is found, this value will be returned and indicate failure. */
2716 alg_out->cost.cost = cost_limit->cost + 1;
2717 alg_out->cost.latency = cost_limit->latency + 1;
2719 if (cost_limit->cost < 0
2720 || (cost_limit->cost == 0 && cost_limit->latency <= 0))
2721 return;
2723 /* Be prepared for vector modes. */
2724 imode = as_a <scalar_int_mode> (GET_MODE_INNER (mode));
2726 maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (imode));
2728 /* Restrict the bits of "t" to the multiplication's mode. */
2729 t &= GET_MODE_MASK (imode);
2731 /* t == 1 can be done in zero cost. */
2732 if (t == 1)
2734 alg_out->ops = 1;
2735 alg_out->cost.cost = 0;
2736 alg_out->cost.latency = 0;
2737 alg_out->op[0] = alg_m;
2738 return;
2741 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2742 fail now. */
2743 if (t == 0)
2745 if (MULT_COST_LESS (cost_limit, zero_cost (speed)))
2746 return;
2747 else
2749 alg_out->ops = 1;
2750 alg_out->cost.cost = zero_cost (speed);
2751 alg_out->cost.latency = zero_cost (speed);
2752 alg_out->op[0] = alg_zero;
2753 return;
2757 /* We'll be needing a couple extra algorithm structures now. */
2759 alg_in = XALLOCA (struct algorithm);
2760 best_alg = XALLOCA (struct algorithm);
2761 best_cost = *cost_limit;
2763 /* Compute the hash index. */
2764 hash_index = (t ^ (unsigned int) mode ^ (speed * 256)) % NUM_ALG_HASH_ENTRIES;
2766 /* See if we already know what to do for T. */
2767 entry_ptr = alg_hash_entry_ptr (hash_index);
2768 if (entry_ptr->t == t
2769 && entry_ptr->mode == mode
2770 && entry_ptr->speed == speed
2771 && entry_ptr->alg != alg_unknown)
2773 cache_alg = entry_ptr->alg;
2775 if (cache_alg == alg_impossible)
2777 /* The cache tells us that it's impossible to synthesize
2778 multiplication by T within entry_ptr->cost. */
2779 if (!CHEAPER_MULT_COST (&entry_ptr->cost, cost_limit))
2780 /* COST_LIMIT is at least as restrictive as the one
2781 recorded in the hash table, in which case we have no
2782 hope of synthesizing a multiplication. Just
2783 return. */
2784 return;
2786 /* If we get here, COST_LIMIT is less restrictive than the
2787 one recorded in the hash table, so we may be able to
2788 synthesize a multiplication. Proceed as if we didn't
2789 have the cache entry. */
2791 else
2793 if (CHEAPER_MULT_COST (cost_limit, &entry_ptr->cost))
2794 /* The cached algorithm shows that this multiplication
2795 requires more cost than COST_LIMIT. Just return. This
2796 way, we don't clobber this cache entry with
2797 alg_impossible but retain useful information. */
2798 return;
2800 cache_hit = true;
2802 switch (cache_alg)
2804 case alg_shift:
2805 goto do_alg_shift;
2807 case alg_add_t_m2:
2808 case alg_sub_t_m2:
2809 goto do_alg_addsub_t_m2;
2811 case alg_add_factor:
2812 case alg_sub_factor:
2813 goto do_alg_addsub_factor;
2815 case alg_add_t2_m:
2816 goto do_alg_add_t2_m;
2818 case alg_sub_t2_m:
2819 goto do_alg_sub_t2_m;
2821 default:
2822 gcc_unreachable ();
2827 /* If we have a group of zero bits at the low-order part of T, try
2828 multiplying by the remaining bits and then doing a shift. */
2830 if ((t & 1) == 0)
2832 do_alg_shift:
2833 m = ctz_or_zero (t); /* m = number of low zero bits */
2834 if (m < maxm)
2836 q = t >> m;
2837 /* The function expand_shift will choose between a shift and
2838 a sequence of additions, so the observed cost is given as
2839 MIN (m * add_cost(speed, mode), shift_cost(speed, mode, m)). */
2840 op_cost = m * add_cost (speed, mode);
2841 if (shift_cost (speed, mode, m) < op_cost)
2842 op_cost = shift_cost (speed, mode, m);
2843 new_limit.cost = best_cost.cost - op_cost;
2844 new_limit.latency = best_cost.latency - op_cost;
2845 synth_mult (alg_in, q, &new_limit, mode);
2847 alg_in->cost.cost += op_cost;
2848 alg_in->cost.latency += op_cost;
2849 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2851 best_cost = alg_in->cost;
2852 std::swap (alg_in, best_alg);
2853 best_alg->log[best_alg->ops] = m;
2854 best_alg->op[best_alg->ops] = alg_shift;
2857 /* See if treating ORIG_T as a signed number yields a better
2858 sequence. Try this sequence only for a negative ORIG_T
2859 as it would be useless for a non-negative ORIG_T. */
2860 if ((HOST_WIDE_INT) orig_t < 0)
2862 /* Shift ORIG_T as follows because a right shift of a
2863 negative-valued signed type is implementation
2864 defined. */
2865 q = ~(~orig_t >> m);
2866 /* The function expand_shift will choose between a shift
2867 and a sequence of additions, so the observed cost is
2868 given as MIN (m * add_cost(speed, mode),
2869 shift_cost(speed, mode, m)). */
2870 op_cost = m * add_cost (speed, mode);
2871 if (shift_cost (speed, mode, m) < op_cost)
2872 op_cost = shift_cost (speed, mode, m);
2873 new_limit.cost = best_cost.cost - op_cost;
2874 new_limit.latency = best_cost.latency - op_cost;
2875 synth_mult (alg_in, q, &new_limit, mode);
2877 alg_in->cost.cost += op_cost;
2878 alg_in->cost.latency += op_cost;
2879 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2881 best_cost = alg_in->cost;
2882 std::swap (alg_in, best_alg);
2883 best_alg->log[best_alg->ops] = m;
2884 best_alg->op[best_alg->ops] = alg_shift;
2888 if (cache_hit)
2889 goto done;
2892 /* If we have an odd number, add or subtract one. */
2893 if ((t & 1) != 0)
2895 unsigned HOST_WIDE_INT w;
2897 do_alg_addsub_t_m2:
2898 for (w = 1; (w & t) != 0; w <<= 1)
2900 /* If T was -1, then W will be zero after the loop. This is another
2901 case where T ends with ...111. Handling this with (T + 1) and
2902 subtract 1 produces slightly better code and results in algorithm
2903 selection much faster than treating it like the ...0111 case
2904 below. */
2905 if (w == 0
2906 || (w > 2
2907 /* Reject the case where t is 3.
2908 Thus we prefer addition in that case. */
2909 && t != 3))
2911 /* T ends with ...111. Multiply by (T + 1) and subtract T. */
2913 op_cost = add_cost (speed, mode);
2914 new_limit.cost = best_cost.cost - op_cost;
2915 new_limit.latency = best_cost.latency - op_cost;
2916 synth_mult (alg_in, t + 1, &new_limit, mode);
2918 alg_in->cost.cost += op_cost;
2919 alg_in->cost.latency += op_cost;
2920 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2922 best_cost = alg_in->cost;
2923 std::swap (alg_in, best_alg);
2924 best_alg->log[best_alg->ops] = 0;
2925 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2928 else
2930 /* T ends with ...01 or ...011. Multiply by (T - 1) and add T. */
2932 op_cost = add_cost (speed, mode);
2933 new_limit.cost = best_cost.cost - op_cost;
2934 new_limit.latency = best_cost.latency - op_cost;
2935 synth_mult (alg_in, t - 1, &new_limit, mode);
2937 alg_in->cost.cost += op_cost;
2938 alg_in->cost.latency += op_cost;
2939 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2941 best_cost = alg_in->cost;
2942 std::swap (alg_in, best_alg);
2943 best_alg->log[best_alg->ops] = 0;
2944 best_alg->op[best_alg->ops] = alg_add_t_m2;
2948 /* We may be able to calculate a * -7, a * -15, a * -31, etc
2949 quickly with a - a * n for some appropriate constant n. */
2950 m = exact_log2 (-orig_t + 1);
2951 if (m >= 0 && m < maxm)
2953 op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2954 /* If the target has a cheap shift-and-subtract insn use
2955 that in preference to a shift insn followed by a sub insn.
2956 Assume that the shift-and-sub is "atomic" with a latency
2957 equal to it's cost, otherwise assume that on superscalar
2958 hardware the shift may be executed concurrently with the
2959 earlier steps in the algorithm. */
2960 if (shiftsub1_cost (speed, mode, m) <= op_cost)
2962 op_cost = shiftsub1_cost (speed, mode, m);
2963 op_latency = op_cost;
2965 else
2966 op_latency = add_cost (speed, mode);
2968 new_limit.cost = best_cost.cost - op_cost;
2969 new_limit.latency = best_cost.latency - op_latency;
2970 synth_mult (alg_in, (unsigned HOST_WIDE_INT) (-orig_t + 1) >> m,
2971 &new_limit, mode);
2973 alg_in->cost.cost += op_cost;
2974 alg_in->cost.latency += op_latency;
2975 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2977 best_cost = alg_in->cost;
2978 std::swap (alg_in, best_alg);
2979 best_alg->log[best_alg->ops] = m;
2980 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2984 if (cache_hit)
2985 goto done;
2988 /* Look for factors of t of the form
2989 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2990 If we find such a factor, we can multiply by t using an algorithm that
2991 multiplies by q, shift the result by m and add/subtract it to itself.
2993 We search for large factors first and loop down, even if large factors
2994 are less probable than small; if we find a large factor we will find a
2995 good sequence quickly, and therefore be able to prune (by decreasing
2996 COST_LIMIT) the search. */
2998 do_alg_addsub_factor:
2999 for (m = floor_log2 (t - 1); m >= 2; m--)
3001 unsigned HOST_WIDE_INT d;
3003 d = (HOST_WIDE_INT_1U << m) + 1;
3004 if (t % d == 0 && t > d && m < maxm
3005 && (!cache_hit || cache_alg == alg_add_factor))
3007 op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
3008 if (shiftadd_cost (speed, mode, m) <= op_cost)
3009 op_cost = shiftadd_cost (speed, mode, m);
3011 op_latency = op_cost;
3014 new_limit.cost = best_cost.cost - op_cost;
3015 new_limit.latency = best_cost.latency - op_latency;
3016 synth_mult (alg_in, t / d, &new_limit, mode);
3018 alg_in->cost.cost += op_cost;
3019 alg_in->cost.latency += op_latency;
3020 if (alg_in->cost.latency < op_cost)
3021 alg_in->cost.latency = op_cost;
3022 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
3024 best_cost = alg_in->cost;
3025 std::swap (alg_in, best_alg);
3026 best_alg->log[best_alg->ops] = m;
3027 best_alg->op[best_alg->ops] = alg_add_factor;
3029 /* Other factors will have been taken care of in the recursion. */
3030 break;
3033 d = (HOST_WIDE_INT_1U << m) - 1;
3034 if (t % d == 0 && t > d && m < maxm
3035 && (!cache_hit || cache_alg == alg_sub_factor))
3037 op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
3038 if (shiftsub0_cost (speed, mode, m) <= op_cost)
3039 op_cost = shiftsub0_cost (speed, mode, m);
3041 op_latency = op_cost;
3043 new_limit.cost = best_cost.cost - op_cost;
3044 new_limit.latency = best_cost.latency - op_latency;
3045 synth_mult (alg_in, t / d, &new_limit, mode);
3047 alg_in->cost.cost += op_cost;
3048 alg_in->cost.latency += op_latency;
3049 if (alg_in->cost.latency < op_cost)
3050 alg_in->cost.latency = op_cost;
3051 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
3053 best_cost = alg_in->cost;
3054 std::swap (alg_in, best_alg);
3055 best_alg->log[best_alg->ops] = m;
3056 best_alg->op[best_alg->ops] = alg_sub_factor;
3058 break;
3061 if (cache_hit)
3062 goto done;
3064 /* Try shift-and-add (load effective address) instructions,
3065 i.e. do a*3, a*5, a*9. */
3066 if ((t & 1) != 0)
3068 do_alg_add_t2_m:
3069 q = t - 1;
3070 m = ctz_hwi (q);
3071 if (q && m < maxm)
3073 op_cost = shiftadd_cost (speed, mode, m);
3074 new_limit.cost = best_cost.cost - op_cost;
3075 new_limit.latency = best_cost.latency - op_cost;
3076 synth_mult (alg_in, (t - 1) >> m, &new_limit, mode);
3078 alg_in->cost.cost += op_cost;
3079 alg_in->cost.latency += op_cost;
3080 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
3082 best_cost = alg_in->cost;
3083 std::swap (alg_in, best_alg);
3084 best_alg->log[best_alg->ops] = m;
3085 best_alg->op[best_alg->ops] = alg_add_t2_m;
3088 if (cache_hit)
3089 goto done;
3091 do_alg_sub_t2_m:
3092 q = t + 1;
3093 m = ctz_hwi (q);
3094 if (q && m < maxm)
3096 op_cost = shiftsub0_cost (speed, mode, m);
3097 new_limit.cost = best_cost.cost - op_cost;
3098 new_limit.latency = best_cost.latency - op_cost;
3099 synth_mult (alg_in, (t + 1) >> m, &new_limit, mode);
3101 alg_in->cost.cost += op_cost;
3102 alg_in->cost.latency += op_cost;
3103 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
3105 best_cost = alg_in->cost;
3106 std::swap (alg_in, best_alg);
3107 best_alg->log[best_alg->ops] = m;
3108 best_alg->op[best_alg->ops] = alg_sub_t2_m;
3111 if (cache_hit)
3112 goto done;
3115 done:
3116 /* If best_cost has not decreased, we have not found any algorithm. */
3117 if (!CHEAPER_MULT_COST (&best_cost, cost_limit))
3119 /* We failed to find an algorithm. Record alg_impossible for
3120 this case (that is, <T, MODE, COST_LIMIT>) so that next time
3121 we are asked to find an algorithm for T within the same or
3122 lower COST_LIMIT, we can immediately return to the
3123 caller. */
3124 entry_ptr->t = t;
3125 entry_ptr->mode = mode;
3126 entry_ptr->speed = speed;
3127 entry_ptr->alg = alg_impossible;
3128 entry_ptr->cost = *cost_limit;
3129 return;
3132 /* Cache the result. */
3133 if (!cache_hit)
3135 entry_ptr->t = t;
3136 entry_ptr->mode = mode;
3137 entry_ptr->speed = speed;
3138 entry_ptr->alg = best_alg->op[best_alg->ops];
3139 entry_ptr->cost.cost = best_cost.cost;
3140 entry_ptr->cost.latency = best_cost.latency;
3143 /* If we are getting a too long sequence for `struct algorithm'
3144 to record, make this search fail. */
3145 if (best_alg->ops == MAX_BITS_PER_WORD)
3146 return;
3148 /* Copy the algorithm from temporary space to the space at alg_out.
3149 We avoid using structure assignment because the majority of
3150 best_alg is normally undefined, and this is a critical function. */
3151 alg_out->ops = best_alg->ops + 1;
3152 alg_out->cost = best_cost;
3153 memcpy (alg_out->op, best_alg->op,
3154 alg_out->ops * sizeof *alg_out->op);
3155 memcpy (alg_out->log, best_alg->log,
3156 alg_out->ops * sizeof *alg_out->log);
3159 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
3160 Try three variations:
3162 - a shift/add sequence based on VAL itself
3163 - a shift/add sequence based on -VAL, followed by a negation
3164 - a shift/add sequence based on VAL - 1, followed by an addition.
3166 Return true if the cheapest of these cost less than MULT_COST,
3167 describing the algorithm in *ALG and final fixup in *VARIANT. */
3169 bool
3170 choose_mult_variant (machine_mode mode, HOST_WIDE_INT val,
3171 struct algorithm *alg, enum mult_variant *variant,
3172 int mult_cost)
3174 struct algorithm alg2;
3175 struct mult_cost limit;
3176 int op_cost;
3177 bool speed = optimize_insn_for_speed_p ();
3179 /* Fail quickly for impossible bounds. */
3180 if (mult_cost < 0)
3181 return false;
3183 /* Ensure that mult_cost provides a reasonable upper bound.
3184 Any constant multiplication can be performed with less
3185 than 2 * bits additions. */
3186 op_cost = 2 * GET_MODE_UNIT_BITSIZE (mode) * add_cost (speed, mode);
3187 if (mult_cost > op_cost)
3188 mult_cost = op_cost;
3190 *variant = basic_variant;
3191 limit.cost = mult_cost;
3192 limit.latency = mult_cost;
3193 synth_mult (alg, val, &limit, mode);
3195 /* This works only if the inverted value actually fits in an
3196 `unsigned int' */
3197 if (HOST_BITS_PER_INT >= GET_MODE_UNIT_BITSIZE (mode))
3199 op_cost = neg_cost (speed, mode);
3200 if (MULT_COST_LESS (&alg->cost, mult_cost))
3202 limit.cost = alg->cost.cost - op_cost;
3203 limit.latency = alg->cost.latency - op_cost;
3205 else
3207 limit.cost = mult_cost - op_cost;
3208 limit.latency = mult_cost - op_cost;
3211 synth_mult (&alg2, -val, &limit, mode);
3212 alg2.cost.cost += op_cost;
3213 alg2.cost.latency += op_cost;
3214 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
3215 *alg = alg2, *variant = negate_variant;
3218 /* This proves very useful for division-by-constant. */
3219 op_cost = add_cost (speed, mode);
3220 if (MULT_COST_LESS (&alg->cost, mult_cost))
3222 limit.cost = alg->cost.cost - op_cost;
3223 limit.latency = alg->cost.latency - op_cost;
3225 else
3227 limit.cost = mult_cost - op_cost;
3228 limit.latency = mult_cost - op_cost;
3231 synth_mult (&alg2, val - 1, &limit, mode);
3232 alg2.cost.cost += op_cost;
3233 alg2.cost.latency += op_cost;
3234 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
3235 *alg = alg2, *variant = add_variant;
3237 return MULT_COST_LESS (&alg->cost, mult_cost);
3240 /* A subroutine of expand_mult, used for constant multiplications.
3241 Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
3242 convenient. Use the shift/add sequence described by ALG and apply
3243 the final fixup specified by VARIANT. */
3245 static rtx
3246 expand_mult_const (machine_mode mode, rtx op0, HOST_WIDE_INT val,
3247 rtx target, const struct algorithm *alg,
3248 enum mult_variant variant)
3250 unsigned HOST_WIDE_INT val_so_far;
3251 rtx_insn *insn;
3252 rtx accum, tem;
3253 int opno;
3254 machine_mode nmode;
3256 /* Avoid referencing memory over and over and invalid sharing
3257 on SUBREGs. */
3258 op0 = force_reg (mode, op0);
3260 /* ACCUM starts out either as OP0 or as a zero, depending on
3261 the first operation. */
3263 if (alg->op[0] == alg_zero)
3265 accum = copy_to_mode_reg (mode, CONST0_RTX (mode));
3266 val_so_far = 0;
3268 else if (alg->op[0] == alg_m)
3270 accum = copy_to_mode_reg (mode, op0);
3271 val_so_far = 1;
3273 else
3274 gcc_unreachable ();
3276 for (opno = 1; opno < alg->ops; opno++)
3278 int log = alg->log[opno];
3279 rtx shift_subtarget = optimize ? 0 : accum;
3280 rtx add_target
3281 = (opno == alg->ops - 1 && target != 0 && variant != add_variant
3282 && !optimize)
3283 ? target : 0;
3284 rtx accum_target = optimize ? 0 : accum;
3285 rtx accum_inner;
3287 switch (alg->op[opno])
3289 case alg_shift:
3290 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3291 /* REG_EQUAL note will be attached to the following insn. */
3292 emit_move_insn (accum, tem);
3293 val_so_far <<= log;
3294 break;
3296 case alg_add_t_m2:
3297 tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
3298 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3299 add_target ? add_target : accum_target);
3300 val_so_far += HOST_WIDE_INT_1U << log;
3301 break;
3303 case alg_sub_t_m2:
3304 tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
3305 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
3306 add_target ? add_target : accum_target);
3307 val_so_far -= HOST_WIDE_INT_1U << log;
3308 break;
3310 case alg_add_t2_m:
3311 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3312 log, shift_subtarget, 0);
3313 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
3314 add_target ? add_target : accum_target);
3315 val_so_far = (val_so_far << log) + 1;
3316 break;
3318 case alg_sub_t2_m:
3319 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3320 log, shift_subtarget, 0);
3321 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
3322 add_target ? add_target : accum_target);
3323 val_so_far = (val_so_far << log) - 1;
3324 break;
3326 case alg_add_factor:
3327 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3328 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3329 add_target ? add_target : accum_target);
3330 val_so_far += val_so_far << log;
3331 break;
3333 case alg_sub_factor:
3334 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3335 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
3336 (add_target
3337 ? add_target : (optimize ? 0 : tem)));
3338 val_so_far = (val_so_far << log) - val_so_far;
3339 break;
3341 default:
3342 gcc_unreachable ();
3345 if (SCALAR_INT_MODE_P (mode))
3347 /* Write a REG_EQUAL note on the last insn so that we can cse
3348 multiplication sequences. Note that if ACCUM is a SUBREG,
3349 we've set the inner register and must properly indicate that. */
3350 tem = op0, nmode = mode;
3351 accum_inner = accum;
3352 if (GET_CODE (accum) == SUBREG)
3354 accum_inner = SUBREG_REG (accum);
3355 nmode = GET_MODE (accum_inner);
3356 tem = gen_lowpart (nmode, op0);
3359 insn = get_last_insn ();
3360 wide_int wval_so_far
3361 = wi::uhwi (val_so_far,
3362 GET_MODE_PRECISION (as_a <scalar_mode> (nmode)));
3363 rtx c = immed_wide_int_const (wval_so_far, nmode);
3364 set_dst_reg_note (insn, REG_EQUAL, gen_rtx_MULT (nmode, tem, c),
3365 accum_inner);
3369 if (variant == negate_variant)
3371 val_so_far = -val_so_far;
3372 accum = expand_unop (mode, neg_optab, accum, target, 0);
3374 else if (variant == add_variant)
3376 val_so_far = val_so_far + 1;
3377 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
3380 /* Compare only the bits of val and val_so_far that are significant
3381 in the result mode, to avoid sign-/zero-extension confusion. */
3382 nmode = GET_MODE_INNER (mode);
3383 val &= GET_MODE_MASK (nmode);
3384 val_so_far &= GET_MODE_MASK (nmode);
3385 gcc_assert (val == (HOST_WIDE_INT) val_so_far);
3387 return accum;
3390 /* Perform a multiplication and return an rtx for the result.
3391 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3392 TARGET is a suggestion for where to store the result (an rtx).
3394 We check specially for a constant integer as OP1.
3395 If you want this check for OP0 as well, then before calling
3396 you should swap the two operands if OP0 would be constant. */
3399 expand_mult (machine_mode mode, rtx op0, rtx op1, rtx target,
3400 int unsignedp, bool no_libcall)
3402 enum mult_variant variant;
3403 struct algorithm algorithm;
3404 rtx scalar_op1;
3405 int max_cost;
3406 bool speed = optimize_insn_for_speed_p ();
3407 bool do_trapv = flag_trapv && SCALAR_INT_MODE_P (mode) && !unsignedp;
3409 if (CONSTANT_P (op0))
3410 std::swap (op0, op1);
3412 /* For vectors, there are several simplifications that can be made if
3413 all elements of the vector constant are identical. */
3414 scalar_op1 = unwrap_const_vec_duplicate (op1);
3416 if (INTEGRAL_MODE_P (mode))
3418 rtx fake_reg;
3419 HOST_WIDE_INT coeff;
3420 bool is_neg;
3421 int mode_bitsize;
3423 if (op1 == CONST0_RTX (mode))
3424 return op1;
3425 if (op1 == CONST1_RTX (mode))
3426 return op0;
3427 if (op1 == CONSTM1_RTX (mode))
3428 return expand_unop (mode, do_trapv ? negv_optab : neg_optab,
3429 op0, target, 0);
3431 if (do_trapv)
3432 goto skip_synth;
3434 /* If mode is integer vector mode, check if the backend supports
3435 vector lshift (by scalar or vector) at all. If not, we can't use
3436 synthetized multiply. */
3437 if (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
3438 && optab_handler (vashl_optab, mode) == CODE_FOR_nothing
3439 && optab_handler (ashl_optab, mode) == CODE_FOR_nothing)
3440 goto skip_synth;
3442 /* These are the operations that are potentially turned into
3443 a sequence of shifts and additions. */
3444 mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
3446 /* synth_mult does an `unsigned int' multiply. As long as the mode is
3447 less than or equal in size to `unsigned int' this doesn't matter.
3448 If the mode is larger than `unsigned int', then synth_mult works
3449 only if the constant value exactly fits in an `unsigned int' without
3450 any truncation. This means that multiplying by negative values does
3451 not work; results are off by 2^32 on a 32 bit machine. */
3452 if (CONST_INT_P (scalar_op1))
3454 coeff = INTVAL (scalar_op1);
3455 is_neg = coeff < 0;
3457 #if TARGET_SUPPORTS_WIDE_INT
3458 else if (CONST_WIDE_INT_P (scalar_op1))
3459 #else
3460 else if (CONST_DOUBLE_AS_INT_P (scalar_op1))
3461 #endif
3463 int shift = wi::exact_log2 (rtx_mode_t (scalar_op1, mode));
3464 /* Perfect power of 2 (other than 1, which is handled above). */
3465 if (shift > 0)
3466 return expand_shift (LSHIFT_EXPR, mode, op0,
3467 shift, target, unsignedp);
3468 else
3469 goto skip_synth;
3471 else
3472 goto skip_synth;
3474 /* We used to test optimize here, on the grounds that it's better to
3475 produce a smaller program when -O is not used. But this causes
3476 such a terrible slowdown sometimes that it seems better to always
3477 use synth_mult. */
3479 /* Special case powers of two. */
3480 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff)
3481 && !(is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT))
3482 return expand_shift (LSHIFT_EXPR, mode, op0,
3483 floor_log2 (coeff), target, unsignedp);
3485 fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3487 /* Attempt to handle multiplication of DImode values by negative
3488 coefficients, by performing the multiplication by a positive
3489 multiplier and then inverting the result. */
3490 if (is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT)
3492 /* Its safe to use -coeff even for INT_MIN, as the
3493 result is interpreted as an unsigned coefficient.
3494 Exclude cost of op0 from max_cost to match the cost
3495 calculation of the synth_mult. */
3496 coeff = -(unsigned HOST_WIDE_INT) coeff;
3497 max_cost = (set_src_cost (gen_rtx_MULT (mode, fake_reg, op1),
3498 mode, speed)
3499 - neg_cost (speed, mode));
3500 if (max_cost <= 0)
3501 goto skip_synth;
3503 /* Special case powers of two. */
3504 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3506 rtx temp = expand_shift (LSHIFT_EXPR, mode, op0,
3507 floor_log2 (coeff), target, unsignedp);
3508 return expand_unop (mode, neg_optab, temp, target, 0);
3511 if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3512 max_cost))
3514 rtx temp = expand_mult_const (mode, op0, coeff, NULL_RTX,
3515 &algorithm, variant);
3516 return expand_unop (mode, neg_optab, temp, target, 0);
3518 goto skip_synth;
3521 /* Exclude cost of op0 from max_cost to match the cost
3522 calculation of the synth_mult. */
3523 max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, op1), mode, speed);
3524 if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3525 return expand_mult_const (mode, op0, coeff, target,
3526 &algorithm, variant);
3528 skip_synth:
3530 /* Expand x*2.0 as x+x. */
3531 if (CONST_DOUBLE_AS_FLOAT_P (scalar_op1)
3532 && real_equal (CONST_DOUBLE_REAL_VALUE (scalar_op1), &dconst2))
3534 op0 = force_reg (GET_MODE (op0), op0);
3535 return expand_binop (mode, add_optab, op0, op0,
3536 target, unsignedp,
3537 no_libcall ? OPTAB_WIDEN : OPTAB_LIB_WIDEN);
3540 /* This used to use umul_optab if unsigned, but for non-widening multiply
3541 there is no difference between signed and unsigned. */
3542 op0 = expand_binop (mode, do_trapv ? smulv_optab : smul_optab,
3543 op0, op1, target, unsignedp,
3544 no_libcall ? OPTAB_WIDEN : OPTAB_LIB_WIDEN);
3545 gcc_assert (op0 || no_libcall);
3546 return op0;
3549 /* Return a cost estimate for multiplying a register by the given
3550 COEFFicient in the given MODE and SPEED. */
3553 mult_by_coeff_cost (HOST_WIDE_INT coeff, machine_mode mode, bool speed)
3555 int max_cost;
3556 struct algorithm algorithm;
3557 enum mult_variant variant;
3559 rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3560 max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, fake_reg),
3561 mode, speed);
3562 if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3563 return algorithm.cost.cost;
3564 else
3565 return max_cost;
3568 /* Perform a widening multiplication and return an rtx for the result.
3569 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3570 TARGET is a suggestion for where to store the result (an rtx).
3571 THIS_OPTAB is the optab we should use, it must be either umul_widen_optab
3572 or smul_widen_optab.
3574 We check specially for a constant integer as OP1, comparing the
3575 cost of a widening multiply against the cost of a sequence of shifts
3576 and adds. */
3579 expand_widening_mult (machine_mode mode, rtx op0, rtx op1, rtx target,
3580 int unsignedp, optab this_optab)
3582 bool speed = optimize_insn_for_speed_p ();
3583 rtx cop1;
3585 if (CONST_INT_P (op1)
3586 && GET_MODE (op0) != VOIDmode
3587 && (cop1 = convert_modes (mode, GET_MODE (op0), op1,
3588 this_optab == umul_widen_optab))
3589 && CONST_INT_P (cop1)
3590 && (INTVAL (cop1) >= 0
3591 || HWI_COMPUTABLE_MODE_P (mode)))
3593 HOST_WIDE_INT coeff = INTVAL (cop1);
3594 int max_cost;
3595 enum mult_variant variant;
3596 struct algorithm algorithm;
3598 if (coeff == 0)
3599 return CONST0_RTX (mode);
3601 /* Special case powers of two. */
3602 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3604 op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3605 return expand_shift (LSHIFT_EXPR, mode, op0,
3606 floor_log2 (coeff), target, unsignedp);
3609 /* Exclude cost of op0 from max_cost to match the cost
3610 calculation of the synth_mult. */
3611 max_cost = mul_widen_cost (speed, mode);
3612 if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3613 max_cost))
3615 op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3616 return expand_mult_const (mode, op0, coeff, target,
3617 &algorithm, variant);
3620 return expand_binop (mode, this_optab, op0, op1, target,
3621 unsignedp, OPTAB_LIB_WIDEN);
3624 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
3625 replace division by D, and put the least significant N bits of the result
3626 in *MULTIPLIER_PTR and return the most significant bit.
3628 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
3629 needed precision is in PRECISION (should be <= N).
3631 PRECISION should be as small as possible so this function can choose
3632 multiplier more freely.
3634 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
3635 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
3637 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
3638 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
3640 unsigned HOST_WIDE_INT
3641 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
3642 unsigned HOST_WIDE_INT *multiplier_ptr,
3643 int *post_shift_ptr, int *lgup_ptr)
3645 int lgup, post_shift;
3646 int pow, pow2;
3648 /* lgup = ceil(log2(divisor)); */
3649 lgup = ceil_log2 (d);
3651 gcc_assert (lgup <= n);
3653 pow = n + lgup;
3654 pow2 = n + lgup - precision;
3656 /* mlow = 2^(N + lgup)/d */
3657 wide_int val = wi::set_bit_in_zero (pow, HOST_BITS_PER_DOUBLE_INT);
3658 wide_int mlow = wi::udiv_trunc (val, d);
3660 /* mhigh = (2^(N + lgup) + 2^(N + lgup - precision))/d */
3661 val |= wi::set_bit_in_zero (pow2, HOST_BITS_PER_DOUBLE_INT);
3662 wide_int mhigh = wi::udiv_trunc (val, d);
3664 /* If precision == N, then mlow, mhigh exceed 2^N
3665 (but they do not exceed 2^(N+1)). */
3667 /* Reduce to lowest terms. */
3668 for (post_shift = lgup; post_shift > 0; post_shift--)
3670 unsigned HOST_WIDE_INT ml_lo = wi::extract_uhwi (mlow, 1,
3671 HOST_BITS_PER_WIDE_INT);
3672 unsigned HOST_WIDE_INT mh_lo = wi::extract_uhwi (mhigh, 1,
3673 HOST_BITS_PER_WIDE_INT);
3674 if (ml_lo >= mh_lo)
3675 break;
3677 mlow = wi::uhwi (ml_lo, HOST_BITS_PER_DOUBLE_INT);
3678 mhigh = wi::uhwi (mh_lo, HOST_BITS_PER_DOUBLE_INT);
3681 *post_shift_ptr = post_shift;
3682 *lgup_ptr = lgup;
3683 if (n < HOST_BITS_PER_WIDE_INT)
3685 unsigned HOST_WIDE_INT mask = (HOST_WIDE_INT_1U << n) - 1;
3686 *multiplier_ptr = mhigh.to_uhwi () & mask;
3687 return mhigh.to_uhwi () > mask;
3689 else
3691 *multiplier_ptr = mhigh.to_uhwi ();
3692 return wi::extract_uhwi (mhigh, HOST_BITS_PER_WIDE_INT, 1);
3696 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
3697 congruent to 1 (mod 2**N). */
3699 static unsigned HOST_WIDE_INT
3700 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
3702 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
3704 /* The algorithm notes that the choice y = x satisfies
3705 x*y == 1 mod 2^3, since x is assumed odd.
3706 Each iteration doubles the number of bits of significance in y. */
3708 unsigned HOST_WIDE_INT mask;
3709 unsigned HOST_WIDE_INT y = x;
3710 int nbit = 3;
3712 mask = (n == HOST_BITS_PER_WIDE_INT
3713 ? HOST_WIDE_INT_M1U
3714 : (HOST_WIDE_INT_1U << n) - 1);
3716 while (nbit < n)
3718 y = y * (2 - x*y) & mask; /* Modulo 2^N */
3719 nbit *= 2;
3721 return y;
3724 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
3725 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
3726 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
3727 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
3728 become signed.
3730 The result is put in TARGET if that is convenient.
3732 MODE is the mode of operation. */
3735 expand_mult_highpart_adjust (scalar_int_mode mode, rtx adj_operand, rtx op0,
3736 rtx op1, rtx target, int unsignedp)
3738 rtx tem;
3739 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
3741 tem = expand_shift (RSHIFT_EXPR, mode, op0,
3742 GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3743 tem = expand_and (mode, tem, op1, NULL_RTX);
3744 adj_operand
3745 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3746 adj_operand);
3748 tem = expand_shift (RSHIFT_EXPR, mode, op1,
3749 GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3750 tem = expand_and (mode, tem, op0, NULL_RTX);
3751 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3752 target);
3754 return target;
3757 /* Subroutine of expmed_mult_highpart. Return the MODE high part of OP. */
3759 static rtx
3760 extract_high_half (scalar_int_mode mode, rtx op)
3762 if (mode == word_mode)
3763 return gen_highpart (mode, op);
3765 scalar_int_mode wider_mode = GET_MODE_WIDER_MODE (mode).require ();
3767 op = expand_shift (RSHIFT_EXPR, wider_mode, op,
3768 GET_MODE_BITSIZE (mode), 0, 1);
3769 return convert_modes (mode, wider_mode, op, 0);
3772 /* Like expmed_mult_highpart, but only consider using a multiplication
3773 optab. OP1 is an rtx for the constant operand. */
3775 static rtx
3776 expmed_mult_highpart_optab (scalar_int_mode mode, rtx op0, rtx op1,
3777 rtx target, int unsignedp, int max_cost)
3779 rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
3780 optab moptab;
3781 rtx tem;
3782 int size;
3783 bool speed = optimize_insn_for_speed_p ();
3785 scalar_int_mode wider_mode = GET_MODE_WIDER_MODE (mode).require ();
3787 size = GET_MODE_BITSIZE (mode);
3789 /* Firstly, try using a multiplication insn that only generates the needed
3790 high part of the product, and in the sign flavor of unsignedp. */
3791 if (mul_highpart_cost (speed, mode) < max_cost)
3793 moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
3794 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3795 unsignedp, OPTAB_DIRECT);
3796 if (tem)
3797 return tem;
3800 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
3801 Need to adjust the result after the multiplication. */
3802 if (size - 1 < BITS_PER_WORD
3803 && (mul_highpart_cost (speed, mode)
3804 + 2 * shift_cost (speed, mode, size-1)
3805 + 4 * add_cost (speed, mode) < max_cost))
3807 moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
3808 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3809 unsignedp, OPTAB_DIRECT);
3810 if (tem)
3811 /* We used the wrong signedness. Adjust the result. */
3812 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3813 tem, unsignedp);
3816 /* Try widening multiplication. */
3817 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
3818 if (convert_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3819 && mul_widen_cost (speed, wider_mode) < max_cost)
3821 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
3822 unsignedp, OPTAB_WIDEN);
3823 if (tem)
3824 return extract_high_half (mode, tem);
3827 /* Try widening the mode and perform a non-widening multiplication. */
3828 if (optab_handler (smul_optab, wider_mode) != CODE_FOR_nothing
3829 && size - 1 < BITS_PER_WORD
3830 && (mul_cost (speed, wider_mode) + shift_cost (speed, mode, size-1)
3831 < max_cost))
3833 rtx_insn *insns;
3834 rtx wop0, wop1;
3836 /* We need to widen the operands, for example to ensure the
3837 constant multiplier is correctly sign or zero extended.
3838 Use a sequence to clean-up any instructions emitted by
3839 the conversions if things don't work out. */
3840 start_sequence ();
3841 wop0 = convert_modes (wider_mode, mode, op0, unsignedp);
3842 wop1 = convert_modes (wider_mode, mode, op1, unsignedp);
3843 tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0,
3844 unsignedp, OPTAB_WIDEN);
3845 insns = get_insns ();
3846 end_sequence ();
3848 if (tem)
3850 emit_insn (insns);
3851 return extract_high_half (mode, tem);
3855 /* Try widening multiplication of opposite signedness, and adjust. */
3856 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
3857 if (convert_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3858 && size - 1 < BITS_PER_WORD
3859 && (mul_widen_cost (speed, wider_mode)
3860 + 2 * shift_cost (speed, mode, size-1)
3861 + 4 * add_cost (speed, mode) < max_cost))
3863 tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3864 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3865 if (tem != 0)
3867 tem = extract_high_half (mode, tem);
3868 /* We used the wrong signedness. Adjust the result. */
3869 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3870 target, unsignedp);
3874 return 0;
3877 /* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant),
3878 putting the high half of the result in TARGET if that is convenient,
3879 and return where the result is. If the operation can not be performed,
3880 0 is returned.
3882 MODE is the mode of operation and result.
3884 UNSIGNEDP nonzero means unsigned multiply.
3886 MAX_COST is the total allowed cost for the expanded RTL. */
3888 static rtx
3889 expmed_mult_highpart (scalar_int_mode mode, rtx op0, rtx op1,
3890 rtx target, int unsignedp, int max_cost)
3892 unsigned HOST_WIDE_INT cnst1;
3893 int extra_cost;
3894 bool sign_adjust = false;
3895 enum mult_variant variant;
3896 struct algorithm alg;
3897 rtx tem;
3898 bool speed = optimize_insn_for_speed_p ();
3900 /* We can't support modes wider than HOST_BITS_PER_INT. */
3901 gcc_assert (HWI_COMPUTABLE_MODE_P (mode));
3903 cnst1 = INTVAL (op1) & GET_MODE_MASK (mode);
3905 /* We can't optimize modes wider than BITS_PER_WORD.
3906 ??? We might be able to perform double-word arithmetic if
3907 mode == word_mode, however all the cost calculations in
3908 synth_mult etc. assume single-word operations. */
3909 scalar_int_mode wider_mode = GET_MODE_WIDER_MODE (mode).require ();
3910 if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3911 return expmed_mult_highpart_optab (mode, op0, op1, target,
3912 unsignedp, max_cost);
3914 extra_cost = shift_cost (speed, mode, GET_MODE_BITSIZE (mode) - 1);
3916 /* Check whether we try to multiply by a negative constant. */
3917 if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3919 sign_adjust = true;
3920 extra_cost += add_cost (speed, mode);
3923 /* See whether shift/add multiplication is cheap enough. */
3924 if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3925 max_cost - extra_cost))
3927 /* See whether the specialized multiplication optabs are
3928 cheaper than the shift/add version. */
3929 tem = expmed_mult_highpart_optab (mode, op0, op1, target, unsignedp,
3930 alg.cost.cost + extra_cost);
3931 if (tem)
3932 return tem;
3934 tem = convert_to_mode (wider_mode, op0, unsignedp);
3935 tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3936 tem = extract_high_half (mode, tem);
3938 /* Adjust result for signedness. */
3939 if (sign_adjust)
3940 tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3942 return tem;
3944 return expmed_mult_highpart_optab (mode, op0, op1, target,
3945 unsignedp, max_cost);
3949 /* Expand signed modulus of OP0 by a power of two D in mode MODE. */
3951 static rtx
3952 expand_smod_pow2 (scalar_int_mode mode, rtx op0, HOST_WIDE_INT d)
3954 rtx result, temp, shift;
3955 rtx_code_label *label;
3956 int logd;
3957 int prec = GET_MODE_PRECISION (mode);
3959 logd = floor_log2 (d);
3960 result = gen_reg_rtx (mode);
3962 /* Avoid conditional branches when they're expensive. */
3963 if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2
3964 && optimize_insn_for_speed_p ())
3966 rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3967 mode, 0, -1);
3968 if (signmask)
3970 HOST_WIDE_INT masklow = (HOST_WIDE_INT_1 << logd) - 1;
3971 signmask = force_reg (mode, signmask);
3972 shift = gen_int_shift_amount (mode, GET_MODE_BITSIZE (mode) - logd);
3974 /* Use the rtx_cost of a LSHIFTRT instruction to determine
3975 which instruction sequence to use. If logical right shifts
3976 are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3977 use a LSHIFTRT, 1 ADD, 1 SUB and an AND. */
3979 temp = gen_rtx_LSHIFTRT (mode, result, shift);
3980 if (optab_handler (lshr_optab, mode) == CODE_FOR_nothing
3981 || (set_src_cost (temp, mode, optimize_insn_for_speed_p ())
3982 > COSTS_N_INSNS (2)))
3984 temp = expand_binop (mode, xor_optab, op0, signmask,
3985 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3986 temp = expand_binop (mode, sub_optab, temp, signmask,
3987 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3988 temp = expand_binop (mode, and_optab, temp,
3989 gen_int_mode (masklow, mode),
3990 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3991 temp = expand_binop (mode, xor_optab, temp, signmask,
3992 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3993 temp = expand_binop (mode, sub_optab, temp, signmask,
3994 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3996 else
3998 signmask = expand_binop (mode, lshr_optab, signmask, shift,
3999 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4000 signmask = force_reg (mode, signmask);
4002 temp = expand_binop (mode, add_optab, op0, signmask,
4003 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4004 temp = expand_binop (mode, and_optab, temp,
4005 gen_int_mode (masklow, mode),
4006 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4007 temp = expand_binop (mode, sub_optab, temp, signmask,
4008 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4010 return temp;
4014 /* Mask contains the mode's signbit and the significant bits of the
4015 modulus. By including the signbit in the operation, many targets
4016 can avoid an explicit compare operation in the following comparison
4017 against zero. */
4018 wide_int mask = wi::mask (logd, false, prec);
4019 mask = wi::set_bit (mask, prec - 1);
4021 temp = expand_binop (mode, and_optab, op0,
4022 immed_wide_int_const (mask, mode),
4023 result, 1, OPTAB_LIB_WIDEN);
4024 if (temp != result)
4025 emit_move_insn (result, temp);
4027 label = gen_label_rtx ();
4028 do_cmp_and_jump (result, const0_rtx, GE, mode, label);
4030 temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
4031 0, OPTAB_LIB_WIDEN);
4033 mask = wi::mask (logd, true, prec);
4034 temp = expand_binop (mode, ior_optab, temp,
4035 immed_wide_int_const (mask, mode),
4036 result, 1, OPTAB_LIB_WIDEN);
4037 temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
4038 0, OPTAB_LIB_WIDEN);
4039 if (temp != result)
4040 emit_move_insn (result, temp);
4041 emit_label (label);
4042 return result;
4045 /* Expand signed division of OP0 by a power of two D in mode MODE.
4046 This routine is only called for positive values of D. */
4048 static rtx
4049 expand_sdiv_pow2 (scalar_int_mode mode, rtx op0, HOST_WIDE_INT d)
4051 rtx temp;
4052 rtx_code_label *label;
4053 int logd;
4055 logd = floor_log2 (d);
4057 if (d == 2
4058 && BRANCH_COST (optimize_insn_for_speed_p (),
4059 false) >= 1)
4061 temp = gen_reg_rtx (mode);
4062 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1);
4063 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
4064 0, OPTAB_LIB_WIDEN);
4065 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
4068 if (HAVE_conditional_move
4069 && BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2)
4071 rtx temp2;
4073 start_sequence ();
4074 temp2 = copy_to_mode_reg (mode, op0);
4075 temp = expand_binop (mode, add_optab, temp2, gen_int_mode (d - 1, mode),
4076 NULL_RTX, 0, OPTAB_LIB_WIDEN);
4077 temp = force_reg (mode, temp);
4079 /* Construct "temp2 = (temp2 < 0) ? temp : temp2". */
4080 temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx,
4081 mode, temp, temp2, mode, 0);
4082 if (temp2)
4084 rtx_insn *seq = get_insns ();
4085 end_sequence ();
4086 emit_insn (seq);
4087 return expand_shift (RSHIFT_EXPR, mode, temp2, logd, NULL_RTX, 0);
4089 end_sequence ();
4092 if (BRANCH_COST (optimize_insn_for_speed_p (),
4093 false) >= 2)
4095 int ushift = GET_MODE_BITSIZE (mode) - logd;
4097 temp = gen_reg_rtx (mode);
4098 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1);
4099 if (GET_MODE_BITSIZE (mode) >= BITS_PER_WORD
4100 || shift_cost (optimize_insn_for_speed_p (), mode, ushift)
4101 > COSTS_N_INSNS (1))
4102 temp = expand_binop (mode, and_optab, temp, gen_int_mode (d - 1, mode),
4103 NULL_RTX, 0, OPTAB_LIB_WIDEN);
4104 else
4105 temp = expand_shift (RSHIFT_EXPR, mode, temp,
4106 ushift, NULL_RTX, 1);
4107 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
4108 0, OPTAB_LIB_WIDEN);
4109 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
4112 label = gen_label_rtx ();
4113 temp = copy_to_mode_reg (mode, op0);
4114 do_cmp_and_jump (temp, const0_rtx, GE, mode, label);
4115 expand_inc (temp, gen_int_mode (d - 1, mode));
4116 emit_label (label);
4117 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
4120 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
4121 if that is convenient, and returning where the result is.
4122 You may request either the quotient or the remainder as the result;
4123 specify REM_FLAG nonzero to get the remainder.
4125 CODE is the expression code for which kind of division this is;
4126 it controls how rounding is done. MODE is the machine mode to use.
4127 UNSIGNEDP nonzero means do unsigned division. */
4129 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
4130 and then correct it by or'ing in missing high bits
4131 if result of ANDI is nonzero.
4132 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
4133 This could optimize to a bfexts instruction.
4134 But C doesn't use these operations, so their optimizations are
4135 left for later. */
4136 /* ??? For modulo, we don't actually need the highpart of the first product,
4137 the low part will do nicely. And for small divisors, the second multiply
4138 can also be a low-part only multiply or even be completely left out.
4139 E.g. to calculate the remainder of a division by 3 with a 32 bit
4140 multiply, multiply with 0x55555556 and extract the upper two bits;
4141 the result is exact for inputs up to 0x1fffffff.
4142 The input range can be reduced by using cross-sum rules.
4143 For odd divisors >= 3, the following table gives right shift counts
4144 so that if a number is shifted by an integer multiple of the given
4145 amount, the remainder stays the same:
4146 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
4147 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
4148 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
4149 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
4150 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
4152 Cross-sum rules for even numbers can be derived by leaving as many bits
4153 to the right alone as the divisor has zeros to the right.
4154 E.g. if x is an unsigned 32 bit number:
4155 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
4159 expand_divmod (int rem_flag, enum tree_code code, machine_mode mode,
4160 rtx op0, rtx op1, rtx target, int unsignedp)
4162 machine_mode compute_mode;
4163 rtx tquotient;
4164 rtx quotient = 0, remainder = 0;
4165 rtx_insn *last;
4166 rtx_insn *insn;
4167 optab optab1, optab2;
4168 int op1_is_constant, op1_is_pow2 = 0;
4169 int max_cost, extra_cost;
4170 static HOST_WIDE_INT last_div_const = 0;
4171 bool speed = optimize_insn_for_speed_p ();
4173 op1_is_constant = CONST_INT_P (op1);
4174 if (op1_is_constant)
4176 wide_int ext_op1 = rtx_mode_t (op1, mode);
4177 op1_is_pow2 = (wi::popcount (ext_op1) == 1
4178 || (! unsignedp
4179 && wi::popcount (wi::neg (ext_op1)) == 1));
4183 This is the structure of expand_divmod:
4185 First comes code to fix up the operands so we can perform the operations
4186 correctly and efficiently.
4188 Second comes a switch statement with code specific for each rounding mode.
4189 For some special operands this code emits all RTL for the desired
4190 operation, for other cases, it generates only a quotient and stores it in
4191 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
4192 to indicate that it has not done anything.
4194 Last comes code that finishes the operation. If QUOTIENT is set and
4195 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
4196 QUOTIENT is not set, it is computed using trunc rounding.
4198 We try to generate special code for division and remainder when OP1 is a
4199 constant. If |OP1| = 2**n we can use shifts and some other fast
4200 operations. For other values of OP1, we compute a carefully selected
4201 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
4202 by m.
4204 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
4205 half of the product. Different strategies for generating the product are
4206 implemented in expmed_mult_highpart.
4208 If what we actually want is the remainder, we generate that by another
4209 by-constant multiplication and a subtraction. */
4211 /* We shouldn't be called with OP1 == const1_rtx, but some of the
4212 code below will malfunction if we are, so check here and handle
4213 the special case if so. */
4214 if (op1 == const1_rtx)
4215 return rem_flag ? const0_rtx : op0;
4217 /* When dividing by -1, we could get an overflow.
4218 negv_optab can handle overflows. */
4219 if (! unsignedp && op1 == constm1_rtx)
4221 if (rem_flag)
4222 return const0_rtx;
4223 return expand_unop (mode, flag_trapv && GET_MODE_CLASS (mode) == MODE_INT
4224 ? negv_optab : neg_optab, op0, target, 0);
4227 if (target
4228 /* Don't use the function value register as a target
4229 since we have to read it as well as write it,
4230 and function-inlining gets confused by this. */
4231 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
4232 /* Don't clobber an operand while doing a multi-step calculation. */
4233 || ((rem_flag || op1_is_constant)
4234 && (reg_mentioned_p (target, op0)
4235 || (MEM_P (op0) && MEM_P (target))))
4236 || reg_mentioned_p (target, op1)
4237 || (MEM_P (op1) && MEM_P (target))))
4238 target = 0;
4240 /* Get the mode in which to perform this computation. Normally it will
4241 be MODE, but sometimes we can't do the desired operation in MODE.
4242 If so, pick a wider mode in which we can do the operation. Convert
4243 to that mode at the start to avoid repeated conversions.
4245 First see what operations we need. These depend on the expression
4246 we are evaluating. (We assume that divxx3 insns exist under the
4247 same conditions that modxx3 insns and that these insns don't normally
4248 fail. If these assumptions are not correct, we may generate less
4249 efficient code in some cases.)
4251 Then see if we find a mode in which we can open-code that operation
4252 (either a division, modulus, or shift). Finally, check for the smallest
4253 mode for which we can do the operation with a library call. */
4255 /* We might want to refine this now that we have division-by-constant
4256 optimization. Since expmed_mult_highpart tries so many variants, it is
4257 not straightforward to generalize this. Maybe we should make an array
4258 of possible modes in init_expmed? Save this for GCC 2.7. */
4260 optab1 = (op1_is_pow2
4261 ? (unsignedp ? lshr_optab : ashr_optab)
4262 : (unsignedp ? udiv_optab : sdiv_optab));
4263 optab2 = (op1_is_pow2 ? optab1
4264 : (unsignedp ? udivmod_optab : sdivmod_optab));
4266 FOR_EACH_MODE_FROM (compute_mode, mode)
4267 if (optab_handler (optab1, compute_mode) != CODE_FOR_nothing
4268 || optab_handler (optab2, compute_mode) != CODE_FOR_nothing)
4269 break;
4271 if (compute_mode == VOIDmode)
4272 FOR_EACH_MODE_FROM (compute_mode, mode)
4273 if (optab_libfunc (optab1, compute_mode)
4274 || optab_libfunc (optab2, compute_mode))
4275 break;
4277 /* If we still couldn't find a mode, use MODE, but expand_binop will
4278 probably die. */
4279 if (compute_mode == VOIDmode)
4280 compute_mode = mode;
4282 if (target && GET_MODE (target) == compute_mode)
4283 tquotient = target;
4284 else
4285 tquotient = gen_reg_rtx (compute_mode);
4287 #if 0
4288 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
4289 (mode), and thereby get better code when OP1 is a constant. Do that
4290 later. It will require going over all usages of SIZE below. */
4291 size = GET_MODE_BITSIZE (mode);
4292 #endif
4294 /* Only deduct something for a REM if the last divide done was
4295 for a different constant. Then set the constant of the last
4296 divide. */
4297 max_cost = (unsignedp
4298 ? udiv_cost (speed, compute_mode)
4299 : sdiv_cost (speed, compute_mode));
4300 if (rem_flag && ! (last_div_const != 0 && op1_is_constant
4301 && INTVAL (op1) == last_div_const))
4302 max_cost -= (mul_cost (speed, compute_mode)
4303 + add_cost (speed, compute_mode));
4305 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
4307 /* Now convert to the best mode to use. */
4308 if (compute_mode != mode)
4310 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
4311 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
4313 /* convert_modes may have placed op1 into a register, so we
4314 must recompute the following. */
4315 op1_is_constant = CONST_INT_P (op1);
4316 if (op1_is_constant)
4318 wide_int ext_op1 = rtx_mode_t (op1, compute_mode);
4319 op1_is_pow2 = (wi::popcount (ext_op1) == 1
4320 || (! unsignedp
4321 && wi::popcount (wi::neg (ext_op1)) == 1));
4323 else
4324 op1_is_pow2 = 0;
4327 /* If one of the operands is a volatile MEM, copy it into a register. */
4329 if (MEM_P (op0) && MEM_VOLATILE_P (op0))
4330 op0 = force_reg (compute_mode, op0);
4331 if (MEM_P (op1) && MEM_VOLATILE_P (op1))
4332 op1 = force_reg (compute_mode, op1);
4334 /* If we need the remainder or if OP1 is constant, we need to
4335 put OP0 in a register in case it has any queued subexpressions. */
4336 if (rem_flag || op1_is_constant)
4337 op0 = force_reg (compute_mode, op0);
4339 last = get_last_insn ();
4341 /* Promote floor rounding to trunc rounding for unsigned operations. */
4342 if (unsignedp)
4344 if (code == FLOOR_DIV_EXPR)
4345 code = TRUNC_DIV_EXPR;
4346 if (code == FLOOR_MOD_EXPR)
4347 code = TRUNC_MOD_EXPR;
4348 if (code == EXACT_DIV_EXPR && op1_is_pow2)
4349 code = TRUNC_DIV_EXPR;
4352 if (op1 != const0_rtx)
4353 switch (code)
4355 case TRUNC_MOD_EXPR:
4356 case TRUNC_DIV_EXPR:
4357 if (op1_is_constant)
4359 scalar_int_mode int_mode = as_a <scalar_int_mode> (compute_mode);
4360 int size = GET_MODE_BITSIZE (int_mode);
4361 if (unsignedp)
4363 unsigned HOST_WIDE_INT mh, ml;
4364 int pre_shift, post_shift;
4365 int dummy;
4366 wide_int wd = rtx_mode_t (op1, int_mode);
4367 unsigned HOST_WIDE_INT d = wd.to_uhwi ();
4369 if (wi::popcount (wd) == 1)
4371 pre_shift = floor_log2 (d);
4372 if (rem_flag)
4374 unsigned HOST_WIDE_INT mask
4375 = (HOST_WIDE_INT_1U << pre_shift) - 1;
4376 remainder
4377 = expand_binop (int_mode, and_optab, op0,
4378 gen_int_mode (mask, int_mode),
4379 remainder, 1,
4380 OPTAB_LIB_WIDEN);
4381 if (remainder)
4382 return gen_lowpart (mode, remainder);
4384 quotient = expand_shift (RSHIFT_EXPR, int_mode, op0,
4385 pre_shift, tquotient, 1);
4387 else if (size <= HOST_BITS_PER_WIDE_INT)
4389 if (d >= (HOST_WIDE_INT_1U << (size - 1)))
4391 /* Most significant bit of divisor is set; emit an scc
4392 insn. */
4393 quotient = emit_store_flag_force (tquotient, GEU, op0, op1,
4394 int_mode, 1, 1);
4396 else
4398 /* Find a suitable multiplier and right shift count
4399 instead of multiplying with D. */
4401 mh = choose_multiplier (d, size, size,
4402 &ml, &post_shift, &dummy);
4404 /* If the suggested multiplier is more than SIZE bits,
4405 we can do better for even divisors, using an
4406 initial right shift. */
4407 if (mh != 0 && (d & 1) == 0)
4409 pre_shift = ctz_or_zero (d);
4410 mh = choose_multiplier (d >> pre_shift, size,
4411 size - pre_shift,
4412 &ml, &post_shift, &dummy);
4413 gcc_assert (!mh);
4415 else
4416 pre_shift = 0;
4418 if (mh != 0)
4420 rtx t1, t2, t3, t4;
4422 if (post_shift - 1 >= BITS_PER_WORD)
4423 goto fail1;
4425 extra_cost
4426 = (shift_cost (speed, int_mode, post_shift - 1)
4427 + shift_cost (speed, int_mode, 1)
4428 + 2 * add_cost (speed, int_mode));
4429 t1 = expmed_mult_highpart
4430 (int_mode, op0, gen_int_mode (ml, int_mode),
4431 NULL_RTX, 1, max_cost - extra_cost);
4432 if (t1 == 0)
4433 goto fail1;
4434 t2 = force_operand (gen_rtx_MINUS (int_mode,
4435 op0, t1),
4436 NULL_RTX);
4437 t3 = expand_shift (RSHIFT_EXPR, int_mode,
4438 t2, 1, NULL_RTX, 1);
4439 t4 = force_operand (gen_rtx_PLUS (int_mode,
4440 t1, t3),
4441 NULL_RTX);
4442 quotient = expand_shift
4443 (RSHIFT_EXPR, int_mode, t4,
4444 post_shift - 1, tquotient, 1);
4446 else
4448 rtx t1, t2;
4450 if (pre_shift >= BITS_PER_WORD
4451 || post_shift >= BITS_PER_WORD)
4452 goto fail1;
4454 t1 = expand_shift
4455 (RSHIFT_EXPR, int_mode, op0,
4456 pre_shift, NULL_RTX, 1);
4457 extra_cost
4458 = (shift_cost (speed, int_mode, pre_shift)
4459 + shift_cost (speed, int_mode, post_shift));
4460 t2 = expmed_mult_highpart
4461 (int_mode, t1,
4462 gen_int_mode (ml, int_mode),
4463 NULL_RTX, 1, max_cost - extra_cost);
4464 if (t2 == 0)
4465 goto fail1;
4466 quotient = expand_shift
4467 (RSHIFT_EXPR, int_mode, t2,
4468 post_shift, tquotient, 1);
4472 else /* Too wide mode to use tricky code */
4473 break;
4475 insn = get_last_insn ();
4476 if (insn != last)
4477 set_dst_reg_note (insn, REG_EQUAL,
4478 gen_rtx_UDIV (int_mode, op0, op1),
4479 quotient);
4481 else /* TRUNC_DIV, signed */
4483 unsigned HOST_WIDE_INT ml;
4484 int lgup, post_shift;
4485 rtx mlr;
4486 HOST_WIDE_INT d = INTVAL (op1);
4487 unsigned HOST_WIDE_INT abs_d;
4489 /* Not prepared to handle division/remainder by
4490 0xffffffffffffffff8000000000000000 etc. */
4491 if (d == HOST_WIDE_INT_MIN && size > HOST_BITS_PER_WIDE_INT)
4492 break;
4494 /* Since d might be INT_MIN, we have to cast to
4495 unsigned HOST_WIDE_INT before negating to avoid
4496 undefined signed overflow. */
4497 abs_d = (d >= 0
4498 ? (unsigned HOST_WIDE_INT) d
4499 : - (unsigned HOST_WIDE_INT) d);
4501 /* n rem d = n rem -d */
4502 if (rem_flag && d < 0)
4504 d = abs_d;
4505 op1 = gen_int_mode (abs_d, int_mode);
4508 if (d == 1)
4509 quotient = op0;
4510 else if (d == -1)
4511 quotient = expand_unop (int_mode, neg_optab, op0,
4512 tquotient, 0);
4513 else if (size <= HOST_BITS_PER_WIDE_INT
4514 && abs_d == HOST_WIDE_INT_1U << (size - 1))
4516 /* This case is not handled correctly below. */
4517 quotient = emit_store_flag (tquotient, EQ, op0, op1,
4518 int_mode, 1, 1);
4519 if (quotient == 0)
4520 goto fail1;
4522 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
4523 && (size <= HOST_BITS_PER_WIDE_INT || d >= 0)
4524 && (rem_flag
4525 ? smod_pow2_cheap (speed, int_mode)
4526 : sdiv_pow2_cheap (speed, int_mode))
4527 /* We assume that cheap metric is true if the
4528 optab has an expander for this mode. */
4529 && ((optab_handler ((rem_flag ? smod_optab
4530 : sdiv_optab),
4531 int_mode)
4532 != CODE_FOR_nothing)
4533 || (optab_handler (sdivmod_optab, int_mode)
4534 != CODE_FOR_nothing)))
4536 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
4538 if (rem_flag)
4540 remainder = expand_smod_pow2 (int_mode, op0, d);
4541 if (remainder)
4542 return gen_lowpart (mode, remainder);
4545 if (sdiv_pow2_cheap (speed, int_mode)
4546 && ((optab_handler (sdiv_optab, int_mode)
4547 != CODE_FOR_nothing)
4548 || (optab_handler (sdivmod_optab, int_mode)
4549 != CODE_FOR_nothing)))
4550 quotient = expand_divmod (0, TRUNC_DIV_EXPR,
4551 int_mode, op0,
4552 gen_int_mode (abs_d,
4553 int_mode),
4554 NULL_RTX, 0);
4555 else
4556 quotient = expand_sdiv_pow2 (int_mode, op0, abs_d);
4558 /* We have computed OP0 / abs(OP1). If OP1 is negative,
4559 negate the quotient. */
4560 if (d < 0)
4562 insn = get_last_insn ();
4563 if (insn != last
4564 && abs_d < (HOST_WIDE_INT_1U
4565 << (HOST_BITS_PER_WIDE_INT - 1)))
4566 set_dst_reg_note (insn, REG_EQUAL,
4567 gen_rtx_DIV (int_mode, op0,
4568 gen_int_mode
4569 (abs_d,
4570 int_mode)),
4571 quotient);
4573 quotient = expand_unop (int_mode, neg_optab,
4574 quotient, quotient, 0);
4577 else if (size <= HOST_BITS_PER_WIDE_INT)
4579 choose_multiplier (abs_d, size, size - 1,
4580 &ml, &post_shift, &lgup);
4581 if (ml < HOST_WIDE_INT_1U << (size - 1))
4583 rtx t1, t2, t3;
4585 if (post_shift >= BITS_PER_WORD
4586 || size - 1 >= BITS_PER_WORD)
4587 goto fail1;
4589 extra_cost = (shift_cost (speed, int_mode, post_shift)
4590 + shift_cost (speed, int_mode, size - 1)
4591 + add_cost (speed, int_mode));
4592 t1 = expmed_mult_highpart
4593 (int_mode, op0, gen_int_mode (ml, int_mode),
4594 NULL_RTX, 0, max_cost - extra_cost);
4595 if (t1 == 0)
4596 goto fail1;
4597 t2 = expand_shift
4598 (RSHIFT_EXPR, int_mode, t1,
4599 post_shift, NULL_RTX, 0);
4600 t3 = expand_shift
4601 (RSHIFT_EXPR, int_mode, op0,
4602 size - 1, NULL_RTX, 0);
4603 if (d < 0)
4604 quotient
4605 = force_operand (gen_rtx_MINUS (int_mode, t3, t2),
4606 tquotient);
4607 else
4608 quotient
4609 = force_operand (gen_rtx_MINUS (int_mode, t2, t3),
4610 tquotient);
4612 else
4614 rtx t1, t2, t3, t4;
4616 if (post_shift >= BITS_PER_WORD
4617 || size - 1 >= BITS_PER_WORD)
4618 goto fail1;
4620 ml |= HOST_WIDE_INT_M1U << (size - 1);
4621 mlr = gen_int_mode (ml, int_mode);
4622 extra_cost = (shift_cost (speed, int_mode, post_shift)
4623 + shift_cost (speed, int_mode, size - 1)
4624 + 2 * add_cost (speed, int_mode));
4625 t1 = expmed_mult_highpart (int_mode, op0, mlr,
4626 NULL_RTX, 0,
4627 max_cost - extra_cost);
4628 if (t1 == 0)
4629 goto fail1;
4630 t2 = force_operand (gen_rtx_PLUS (int_mode, t1, op0),
4631 NULL_RTX);
4632 t3 = expand_shift
4633 (RSHIFT_EXPR, int_mode, t2,
4634 post_shift, NULL_RTX, 0);
4635 t4 = expand_shift
4636 (RSHIFT_EXPR, int_mode, op0,
4637 size - 1, NULL_RTX, 0);
4638 if (d < 0)
4639 quotient
4640 = force_operand (gen_rtx_MINUS (int_mode, t4, t3),
4641 tquotient);
4642 else
4643 quotient
4644 = force_operand (gen_rtx_MINUS (int_mode, t3, t4),
4645 tquotient);
4648 else /* Too wide mode to use tricky code */
4649 break;
4651 insn = get_last_insn ();
4652 if (insn != last)
4653 set_dst_reg_note (insn, REG_EQUAL,
4654 gen_rtx_DIV (int_mode, op0, op1),
4655 quotient);
4657 break;
4659 fail1:
4660 delete_insns_since (last);
4661 break;
4663 case FLOOR_DIV_EXPR:
4664 case FLOOR_MOD_EXPR:
4665 /* We will come here only for signed operations. */
4666 if (op1_is_constant && HWI_COMPUTABLE_MODE_P (compute_mode))
4668 scalar_int_mode int_mode = as_a <scalar_int_mode> (compute_mode);
4669 int size = GET_MODE_BITSIZE (int_mode);
4670 unsigned HOST_WIDE_INT mh, ml;
4671 int pre_shift, lgup, post_shift;
4672 HOST_WIDE_INT d = INTVAL (op1);
4674 if (d > 0)
4676 /* We could just as easily deal with negative constants here,
4677 but it does not seem worth the trouble for GCC 2.6. */
4678 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4680 pre_shift = floor_log2 (d);
4681 if (rem_flag)
4683 unsigned HOST_WIDE_INT mask
4684 = (HOST_WIDE_INT_1U << pre_shift) - 1;
4685 remainder = expand_binop
4686 (int_mode, and_optab, op0,
4687 gen_int_mode (mask, int_mode),
4688 remainder, 0, OPTAB_LIB_WIDEN);
4689 if (remainder)
4690 return gen_lowpart (mode, remainder);
4692 quotient = expand_shift
4693 (RSHIFT_EXPR, int_mode, op0,
4694 pre_shift, tquotient, 0);
4696 else
4698 rtx t1, t2, t3, t4;
4700 mh = choose_multiplier (d, size, size - 1,
4701 &ml, &post_shift, &lgup);
4702 gcc_assert (!mh);
4704 if (post_shift < BITS_PER_WORD
4705 && size - 1 < BITS_PER_WORD)
4707 t1 = expand_shift
4708 (RSHIFT_EXPR, int_mode, op0,
4709 size - 1, NULL_RTX, 0);
4710 t2 = expand_binop (int_mode, xor_optab, op0, t1,
4711 NULL_RTX, 0, OPTAB_WIDEN);
4712 extra_cost = (shift_cost (speed, int_mode, post_shift)
4713 + shift_cost (speed, int_mode, size - 1)
4714 + 2 * add_cost (speed, int_mode));
4715 t3 = expmed_mult_highpart
4716 (int_mode, t2, gen_int_mode (ml, int_mode),
4717 NULL_RTX, 1, max_cost - extra_cost);
4718 if (t3 != 0)
4720 t4 = expand_shift
4721 (RSHIFT_EXPR, int_mode, t3,
4722 post_shift, NULL_RTX, 1);
4723 quotient = expand_binop (int_mode, xor_optab,
4724 t4, t1, tquotient, 0,
4725 OPTAB_WIDEN);
4730 else
4732 rtx nsign, t1, t2, t3, t4;
4733 t1 = force_operand (gen_rtx_PLUS (int_mode,
4734 op0, constm1_rtx), NULL_RTX);
4735 t2 = expand_binop (int_mode, ior_optab, op0, t1, NULL_RTX,
4736 0, OPTAB_WIDEN);
4737 nsign = expand_shift (RSHIFT_EXPR, int_mode, t2,
4738 size - 1, NULL_RTX, 0);
4739 t3 = force_operand (gen_rtx_MINUS (int_mode, t1, nsign),
4740 NULL_RTX);
4741 t4 = expand_divmod (0, TRUNC_DIV_EXPR, int_mode, t3, op1,
4742 NULL_RTX, 0);
4743 if (t4)
4745 rtx t5;
4746 t5 = expand_unop (int_mode, one_cmpl_optab, nsign,
4747 NULL_RTX, 0);
4748 quotient = force_operand (gen_rtx_PLUS (int_mode, t4, t5),
4749 tquotient);
4754 if (quotient != 0)
4755 break;
4756 delete_insns_since (last);
4758 /* Try using an instruction that produces both the quotient and
4759 remainder, using truncation. We can easily compensate the quotient
4760 or remainder to get floor rounding, once we have the remainder.
4761 Notice that we compute also the final remainder value here,
4762 and return the result right away. */
4763 if (target == 0 || GET_MODE (target) != compute_mode)
4764 target = gen_reg_rtx (compute_mode);
4766 if (rem_flag)
4768 remainder
4769 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4770 quotient = gen_reg_rtx (compute_mode);
4772 else
4774 quotient
4775 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4776 remainder = gen_reg_rtx (compute_mode);
4779 if (expand_twoval_binop (sdivmod_optab, op0, op1,
4780 quotient, remainder, 0))
4782 /* This could be computed with a branch-less sequence.
4783 Save that for later. */
4784 rtx tem;
4785 rtx_code_label *label = gen_label_rtx ();
4786 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
4787 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4788 NULL_RTX, 0, OPTAB_WIDEN);
4789 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
4790 expand_dec (quotient, const1_rtx);
4791 expand_inc (remainder, op1);
4792 emit_label (label);
4793 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4796 /* No luck with division elimination or divmod. Have to do it
4797 by conditionally adjusting op0 *and* the result. */
4799 rtx_code_label *label1, *label2, *label3, *label4, *label5;
4800 rtx adjusted_op0;
4801 rtx tem;
4803 quotient = gen_reg_rtx (compute_mode);
4804 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4805 label1 = gen_label_rtx ();
4806 label2 = gen_label_rtx ();
4807 label3 = gen_label_rtx ();
4808 label4 = gen_label_rtx ();
4809 label5 = gen_label_rtx ();
4810 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4811 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
4812 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4813 quotient, 0, OPTAB_LIB_WIDEN);
4814 if (tem != quotient)
4815 emit_move_insn (quotient, tem);
4816 emit_jump_insn (targetm.gen_jump (label5));
4817 emit_barrier ();
4818 emit_label (label1);
4819 expand_inc (adjusted_op0, const1_rtx);
4820 emit_jump_insn (targetm.gen_jump (label4));
4821 emit_barrier ();
4822 emit_label (label2);
4823 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
4824 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4825 quotient, 0, OPTAB_LIB_WIDEN);
4826 if (tem != quotient)
4827 emit_move_insn (quotient, tem);
4828 emit_jump_insn (targetm.gen_jump (label5));
4829 emit_barrier ();
4830 emit_label (label3);
4831 expand_dec (adjusted_op0, const1_rtx);
4832 emit_label (label4);
4833 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4834 quotient, 0, OPTAB_LIB_WIDEN);
4835 if (tem != quotient)
4836 emit_move_insn (quotient, tem);
4837 expand_dec (quotient, const1_rtx);
4838 emit_label (label5);
4840 break;
4842 case CEIL_DIV_EXPR:
4843 case CEIL_MOD_EXPR:
4844 if (unsignedp)
4846 if (op1_is_constant
4847 && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4848 && (HWI_COMPUTABLE_MODE_P (compute_mode)
4849 || INTVAL (op1) >= 0))
4851 scalar_int_mode int_mode
4852 = as_a <scalar_int_mode> (compute_mode);
4853 rtx t1, t2, t3;
4854 unsigned HOST_WIDE_INT d = INTVAL (op1);
4855 t1 = expand_shift (RSHIFT_EXPR, int_mode, op0,
4856 floor_log2 (d), tquotient, 1);
4857 t2 = expand_binop (int_mode, and_optab, op0,
4858 gen_int_mode (d - 1, int_mode),
4859 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4860 t3 = gen_reg_rtx (int_mode);
4861 t3 = emit_store_flag (t3, NE, t2, const0_rtx, int_mode, 1, 1);
4862 if (t3 == 0)
4864 rtx_code_label *lab;
4865 lab = gen_label_rtx ();
4866 do_cmp_and_jump (t2, const0_rtx, EQ, int_mode, lab);
4867 expand_inc (t1, const1_rtx);
4868 emit_label (lab);
4869 quotient = t1;
4871 else
4872 quotient = force_operand (gen_rtx_PLUS (int_mode, t1, t3),
4873 tquotient);
4874 break;
4877 /* Try using an instruction that produces both the quotient and
4878 remainder, using truncation. We can easily compensate the
4879 quotient or remainder to get ceiling rounding, once we have the
4880 remainder. Notice that we compute also the final remainder
4881 value here, and return the result right away. */
4882 if (target == 0 || GET_MODE (target) != compute_mode)
4883 target = gen_reg_rtx (compute_mode);
4885 if (rem_flag)
4887 remainder = (REG_P (target)
4888 ? target : gen_reg_rtx (compute_mode));
4889 quotient = gen_reg_rtx (compute_mode);
4891 else
4893 quotient = (REG_P (target)
4894 ? target : gen_reg_rtx (compute_mode));
4895 remainder = gen_reg_rtx (compute_mode);
4898 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
4899 remainder, 1))
4901 /* This could be computed with a branch-less sequence.
4902 Save that for later. */
4903 rtx_code_label *label = gen_label_rtx ();
4904 do_cmp_and_jump (remainder, const0_rtx, EQ,
4905 compute_mode, label);
4906 expand_inc (quotient, const1_rtx);
4907 expand_dec (remainder, op1);
4908 emit_label (label);
4909 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4912 /* No luck with division elimination or divmod. Have to do it
4913 by conditionally adjusting op0 *and* the result. */
4915 rtx_code_label *label1, *label2;
4916 rtx adjusted_op0, tem;
4918 quotient = gen_reg_rtx (compute_mode);
4919 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4920 label1 = gen_label_rtx ();
4921 label2 = gen_label_rtx ();
4922 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
4923 compute_mode, label1);
4924 emit_move_insn (quotient, const0_rtx);
4925 emit_jump_insn (targetm.gen_jump (label2));
4926 emit_barrier ();
4927 emit_label (label1);
4928 expand_dec (adjusted_op0, const1_rtx);
4929 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
4930 quotient, 1, OPTAB_LIB_WIDEN);
4931 if (tem != quotient)
4932 emit_move_insn (quotient, tem);
4933 expand_inc (quotient, const1_rtx);
4934 emit_label (label2);
4937 else /* signed */
4939 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4940 && INTVAL (op1) >= 0)
4942 /* This is extremely similar to the code for the unsigned case
4943 above. For 2.7 we should merge these variants, but for
4944 2.6.1 I don't want to touch the code for unsigned since that
4945 get used in C. The signed case will only be used by other
4946 languages (Ada). */
4948 rtx t1, t2, t3;
4949 unsigned HOST_WIDE_INT d = INTVAL (op1);
4950 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4951 floor_log2 (d), tquotient, 0);
4952 t2 = expand_binop (compute_mode, and_optab, op0,
4953 gen_int_mode (d - 1, compute_mode),
4954 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4955 t3 = gen_reg_rtx (compute_mode);
4956 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4957 compute_mode, 1, 1);
4958 if (t3 == 0)
4960 rtx_code_label *lab;
4961 lab = gen_label_rtx ();
4962 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4963 expand_inc (t1, const1_rtx);
4964 emit_label (lab);
4965 quotient = t1;
4967 else
4968 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4969 t1, t3),
4970 tquotient);
4971 break;
4974 /* Try using an instruction that produces both the quotient and
4975 remainder, using truncation. We can easily compensate the
4976 quotient or remainder to get ceiling rounding, once we have the
4977 remainder. Notice that we compute also the final remainder
4978 value here, and return the result right away. */
4979 if (target == 0 || GET_MODE (target) != compute_mode)
4980 target = gen_reg_rtx (compute_mode);
4981 if (rem_flag)
4983 remainder= (REG_P (target)
4984 ? target : gen_reg_rtx (compute_mode));
4985 quotient = gen_reg_rtx (compute_mode);
4987 else
4989 quotient = (REG_P (target)
4990 ? target : gen_reg_rtx (compute_mode));
4991 remainder = gen_reg_rtx (compute_mode);
4994 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
4995 remainder, 0))
4997 /* This could be computed with a branch-less sequence.
4998 Save that for later. */
4999 rtx tem;
5000 rtx_code_label *label = gen_label_rtx ();
5001 do_cmp_and_jump (remainder, const0_rtx, EQ,
5002 compute_mode, label);
5003 tem = expand_binop (compute_mode, xor_optab, op0, op1,
5004 NULL_RTX, 0, OPTAB_WIDEN);
5005 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
5006 expand_inc (quotient, const1_rtx);
5007 expand_dec (remainder, op1);
5008 emit_label (label);
5009 return gen_lowpart (mode, rem_flag ? remainder : quotient);
5012 /* No luck with division elimination or divmod. Have to do it
5013 by conditionally adjusting op0 *and* the result. */
5015 rtx_code_label *label1, *label2, *label3, *label4, *label5;
5016 rtx adjusted_op0;
5017 rtx tem;
5019 quotient = gen_reg_rtx (compute_mode);
5020 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
5021 label1 = gen_label_rtx ();
5022 label2 = gen_label_rtx ();
5023 label3 = gen_label_rtx ();
5024 label4 = gen_label_rtx ();
5025 label5 = gen_label_rtx ();
5026 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
5027 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
5028 compute_mode, label1);
5029 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
5030 quotient, 0, OPTAB_LIB_WIDEN);
5031 if (tem != quotient)
5032 emit_move_insn (quotient, tem);
5033 emit_jump_insn (targetm.gen_jump (label5));
5034 emit_barrier ();
5035 emit_label (label1);
5036 expand_dec (adjusted_op0, const1_rtx);
5037 emit_jump_insn (targetm.gen_jump (label4));
5038 emit_barrier ();
5039 emit_label (label2);
5040 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
5041 compute_mode, label3);
5042 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
5043 quotient, 0, OPTAB_LIB_WIDEN);
5044 if (tem != quotient)
5045 emit_move_insn (quotient, tem);
5046 emit_jump_insn (targetm.gen_jump (label5));
5047 emit_barrier ();
5048 emit_label (label3);
5049 expand_inc (adjusted_op0, const1_rtx);
5050 emit_label (label4);
5051 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
5052 quotient, 0, OPTAB_LIB_WIDEN);
5053 if (tem != quotient)
5054 emit_move_insn (quotient, tem);
5055 expand_inc (quotient, const1_rtx);
5056 emit_label (label5);
5059 break;
5061 case EXACT_DIV_EXPR:
5062 if (op1_is_constant && HWI_COMPUTABLE_MODE_P (compute_mode))
5064 scalar_int_mode int_mode = as_a <scalar_int_mode> (compute_mode);
5065 int size = GET_MODE_BITSIZE (int_mode);
5066 HOST_WIDE_INT d = INTVAL (op1);
5067 unsigned HOST_WIDE_INT ml;
5068 int pre_shift;
5069 rtx t1;
5071 pre_shift = ctz_or_zero (d);
5072 ml = invert_mod2n (d >> pre_shift, size);
5073 t1 = expand_shift (RSHIFT_EXPR, int_mode, op0,
5074 pre_shift, NULL_RTX, unsignedp);
5075 quotient = expand_mult (int_mode, t1, gen_int_mode (ml, int_mode),
5076 NULL_RTX, 1);
5078 insn = get_last_insn ();
5079 set_dst_reg_note (insn, REG_EQUAL,
5080 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
5081 int_mode, op0, op1),
5082 quotient);
5084 break;
5086 case ROUND_DIV_EXPR:
5087 case ROUND_MOD_EXPR:
5088 if (unsignedp)
5090 scalar_int_mode int_mode = as_a <scalar_int_mode> (compute_mode);
5091 rtx tem;
5092 rtx_code_label *label;
5093 label = gen_label_rtx ();
5094 quotient = gen_reg_rtx (int_mode);
5095 remainder = gen_reg_rtx (int_mode);
5096 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
5098 rtx tem;
5099 quotient = expand_binop (int_mode, udiv_optab, op0, op1,
5100 quotient, 1, OPTAB_LIB_WIDEN);
5101 tem = expand_mult (int_mode, quotient, op1, NULL_RTX, 1);
5102 remainder = expand_binop (int_mode, sub_optab, op0, tem,
5103 remainder, 1, OPTAB_LIB_WIDEN);
5105 tem = plus_constant (int_mode, op1, -1);
5106 tem = expand_shift (RSHIFT_EXPR, int_mode, tem, 1, NULL_RTX, 1);
5107 do_cmp_and_jump (remainder, tem, LEU, int_mode, label);
5108 expand_inc (quotient, const1_rtx);
5109 expand_dec (remainder, op1);
5110 emit_label (label);
5112 else
5114 scalar_int_mode int_mode = as_a <scalar_int_mode> (compute_mode);
5115 int size = GET_MODE_BITSIZE (int_mode);
5116 rtx abs_rem, abs_op1, tem, mask;
5117 rtx_code_label *label;
5118 label = gen_label_rtx ();
5119 quotient = gen_reg_rtx (int_mode);
5120 remainder = gen_reg_rtx (int_mode);
5121 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
5123 rtx tem;
5124 quotient = expand_binop (int_mode, sdiv_optab, op0, op1,
5125 quotient, 0, OPTAB_LIB_WIDEN);
5126 tem = expand_mult (int_mode, quotient, op1, NULL_RTX, 0);
5127 remainder = expand_binop (int_mode, sub_optab, op0, tem,
5128 remainder, 0, OPTAB_LIB_WIDEN);
5130 abs_rem = expand_abs (int_mode, remainder, NULL_RTX, 1, 0);
5131 abs_op1 = expand_abs (int_mode, op1, NULL_RTX, 1, 0);
5132 tem = expand_shift (LSHIFT_EXPR, int_mode, abs_rem,
5133 1, NULL_RTX, 1);
5134 do_cmp_and_jump (tem, abs_op1, LTU, int_mode, label);
5135 tem = expand_binop (int_mode, xor_optab, op0, op1,
5136 NULL_RTX, 0, OPTAB_WIDEN);
5137 mask = expand_shift (RSHIFT_EXPR, int_mode, tem,
5138 size - 1, NULL_RTX, 0);
5139 tem = expand_binop (int_mode, xor_optab, mask, const1_rtx,
5140 NULL_RTX, 0, OPTAB_WIDEN);
5141 tem = expand_binop (int_mode, sub_optab, tem, mask,
5142 NULL_RTX, 0, OPTAB_WIDEN);
5143 expand_inc (quotient, tem);
5144 tem = expand_binop (int_mode, xor_optab, mask, op1,
5145 NULL_RTX, 0, OPTAB_WIDEN);
5146 tem = expand_binop (int_mode, sub_optab, tem, mask,
5147 NULL_RTX, 0, OPTAB_WIDEN);
5148 expand_dec (remainder, tem);
5149 emit_label (label);
5151 return gen_lowpart (mode, rem_flag ? remainder : quotient);
5153 default:
5154 gcc_unreachable ();
5157 if (quotient == 0)
5159 if (target && GET_MODE (target) != compute_mode)
5160 target = 0;
5162 if (rem_flag)
5164 /* Try to produce the remainder without producing the quotient.
5165 If we seem to have a divmod pattern that does not require widening,
5166 don't try widening here. We should really have a WIDEN argument
5167 to expand_twoval_binop, since what we'd really like to do here is
5168 1) try a mod insn in compute_mode
5169 2) try a divmod insn in compute_mode
5170 3) try a div insn in compute_mode and multiply-subtract to get
5171 remainder
5172 4) try the same things with widening allowed. */
5173 remainder
5174 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
5175 op0, op1, target,
5176 unsignedp,
5177 ((optab_handler (optab2, compute_mode)
5178 != CODE_FOR_nothing)
5179 ? OPTAB_DIRECT : OPTAB_WIDEN));
5180 if (remainder == 0)
5182 /* No luck there. Can we do remainder and divide at once
5183 without a library call? */
5184 remainder = gen_reg_rtx (compute_mode);
5185 if (! expand_twoval_binop ((unsignedp
5186 ? udivmod_optab
5187 : sdivmod_optab),
5188 op0, op1,
5189 NULL_RTX, remainder, unsignedp))
5190 remainder = 0;
5193 if (remainder)
5194 return gen_lowpart (mode, remainder);
5197 /* Produce the quotient. Try a quotient insn, but not a library call.
5198 If we have a divmod in this mode, use it in preference to widening
5199 the div (for this test we assume it will not fail). Note that optab2
5200 is set to the one of the two optabs that the call below will use. */
5201 quotient
5202 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
5203 op0, op1, rem_flag ? NULL_RTX : target,
5204 unsignedp,
5205 ((optab_handler (optab2, compute_mode)
5206 != CODE_FOR_nothing)
5207 ? OPTAB_DIRECT : OPTAB_WIDEN));
5209 if (quotient == 0)
5211 /* No luck there. Try a quotient-and-remainder insn,
5212 keeping the quotient alone. */
5213 quotient = gen_reg_rtx (compute_mode);
5214 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
5215 op0, op1,
5216 quotient, NULL_RTX, unsignedp))
5218 quotient = 0;
5219 if (! rem_flag)
5220 /* Still no luck. If we are not computing the remainder,
5221 use a library call for the quotient. */
5222 quotient = sign_expand_binop (compute_mode,
5223 udiv_optab, sdiv_optab,
5224 op0, op1, target,
5225 unsignedp, OPTAB_LIB_WIDEN);
5230 if (rem_flag)
5232 if (target && GET_MODE (target) != compute_mode)
5233 target = 0;
5235 if (quotient == 0)
5237 /* No divide instruction either. Use library for remainder. */
5238 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
5239 op0, op1, target,
5240 unsignedp, OPTAB_LIB_WIDEN);
5241 /* No remainder function. Try a quotient-and-remainder
5242 function, keeping the remainder. */
5243 if (!remainder)
5245 remainder = gen_reg_rtx (compute_mode);
5246 if (!expand_twoval_binop_libfunc
5247 (unsignedp ? udivmod_optab : sdivmod_optab,
5248 op0, op1,
5249 NULL_RTX, remainder,
5250 unsignedp ? UMOD : MOD))
5251 remainder = NULL_RTX;
5254 else
5256 /* We divided. Now finish doing X - Y * (X / Y). */
5257 remainder = expand_mult (compute_mode, quotient, op1,
5258 NULL_RTX, unsignedp);
5259 remainder = expand_binop (compute_mode, sub_optab, op0,
5260 remainder, target, unsignedp,
5261 OPTAB_LIB_WIDEN);
5265 return gen_lowpart (mode, rem_flag ? remainder : quotient);
5268 /* Return a tree node with data type TYPE, describing the value of X.
5269 Usually this is an VAR_DECL, if there is no obvious better choice.
5270 X may be an expression, however we only support those expressions
5271 generated by loop.c. */
5273 tree
5274 make_tree (tree type, rtx x)
5276 tree t;
5278 switch (GET_CODE (x))
5280 case CONST_INT:
5281 case CONST_WIDE_INT:
5282 t = wide_int_to_tree (type, rtx_mode_t (x, TYPE_MODE (type)));
5283 return t;
5285 case CONST_DOUBLE:
5286 STATIC_ASSERT (HOST_BITS_PER_WIDE_INT * 2 <= MAX_BITSIZE_MODE_ANY_INT);
5287 if (TARGET_SUPPORTS_WIDE_INT == 0 && GET_MODE (x) == VOIDmode)
5288 t = wide_int_to_tree (type,
5289 wide_int::from_array (&CONST_DOUBLE_LOW (x), 2,
5290 HOST_BITS_PER_WIDE_INT * 2));
5291 else
5292 t = build_real (type, *CONST_DOUBLE_REAL_VALUE (x));
5294 return t;
5296 case CONST_VECTOR:
5298 unsigned int npatterns = CONST_VECTOR_NPATTERNS (x);
5299 unsigned int nelts_per_pattern = CONST_VECTOR_NELTS_PER_PATTERN (x);
5300 tree itype = TREE_TYPE (type);
5302 /* Build a tree with vector elements. */
5303 tree_vector_builder elts (type, npatterns, nelts_per_pattern);
5304 unsigned int count = elts.encoded_nelts ();
5305 for (unsigned int i = 0; i < count; ++i)
5307 rtx elt = CONST_VECTOR_ELT (x, i);
5308 elts.quick_push (make_tree (itype, elt));
5311 return elts.build ();
5314 case PLUS:
5315 return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5316 make_tree (type, XEXP (x, 1)));
5318 case MINUS:
5319 return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5320 make_tree (type, XEXP (x, 1)));
5322 case NEG:
5323 return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0)));
5325 case MULT:
5326 return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
5327 make_tree (type, XEXP (x, 1)));
5329 case ASHIFT:
5330 return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
5331 make_tree (type, XEXP (x, 1)));
5333 case LSHIFTRT:
5334 t = unsigned_type_for (type);
5335 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5336 make_tree (t, XEXP (x, 0)),
5337 make_tree (type, XEXP (x, 1))));
5339 case ASHIFTRT:
5340 t = signed_type_for (type);
5341 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5342 make_tree (t, XEXP (x, 0)),
5343 make_tree (type, XEXP (x, 1))));
5345 case DIV:
5346 if (TREE_CODE (type) != REAL_TYPE)
5347 t = signed_type_for (type);
5348 else
5349 t = type;
5351 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5352 make_tree (t, XEXP (x, 0)),
5353 make_tree (t, XEXP (x, 1))));
5354 case UDIV:
5355 t = unsigned_type_for (type);
5356 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5357 make_tree (t, XEXP (x, 0)),
5358 make_tree (t, XEXP (x, 1))));
5360 case SIGN_EXTEND:
5361 case ZERO_EXTEND:
5362 t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)),
5363 GET_CODE (x) == ZERO_EXTEND);
5364 return fold_convert (type, make_tree (t, XEXP (x, 0)));
5366 case CONST:
5367 return make_tree (type, XEXP (x, 0));
5369 case SYMBOL_REF:
5370 t = SYMBOL_REF_DECL (x);
5371 if (t)
5372 return fold_convert (type, build_fold_addr_expr (t));
5373 /* fall through. */
5375 default:
5376 if (CONST_POLY_INT_P (x))
5377 return wide_int_to_tree (t, const_poly_int_value (x));
5379 t = build_decl (RTL_LOCATION (x), VAR_DECL, NULL_TREE, type);
5381 /* If TYPE is a POINTER_TYPE, we might need to convert X from
5382 address mode to pointer mode. */
5383 if (POINTER_TYPE_P (type))
5384 x = convert_memory_address_addr_space
5385 (SCALAR_INT_TYPE_MODE (type), x, TYPE_ADDR_SPACE (TREE_TYPE (type)));
5387 /* Note that we do *not* use SET_DECL_RTL here, because we do not
5388 want set_decl_rtl to go adjusting REG_ATTRS for this temporary. */
5389 t->decl_with_rtl.rtl = x;
5391 return t;
5395 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
5396 and returning TARGET.
5398 If TARGET is 0, a pseudo-register or constant is returned. */
5401 expand_and (machine_mode mode, rtx op0, rtx op1, rtx target)
5403 rtx tem = 0;
5405 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
5406 tem = simplify_binary_operation (AND, mode, op0, op1);
5407 if (tem == 0)
5408 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
5410 if (target == 0)
5411 target = tem;
5412 else if (tem != target)
5413 emit_move_insn (target, tem);
5414 return target;
5417 /* Helper function for emit_store_flag. */
5419 emit_cstore (rtx target, enum insn_code icode, enum rtx_code code,
5420 machine_mode mode, machine_mode compare_mode,
5421 int unsignedp, rtx x, rtx y, int normalizep,
5422 machine_mode target_mode)
5424 struct expand_operand ops[4];
5425 rtx op0, comparison, subtarget;
5426 rtx_insn *last;
5427 scalar_int_mode result_mode = targetm.cstore_mode (icode);
5428 scalar_int_mode int_target_mode;
5430 last = get_last_insn ();
5431 x = prepare_operand (icode, x, 2, mode, compare_mode, unsignedp);
5432 y = prepare_operand (icode, y, 3, mode, compare_mode, unsignedp);
5433 if (!x || !y)
5435 delete_insns_since (last);
5436 return NULL_RTX;
5439 if (target_mode == VOIDmode)
5440 int_target_mode = result_mode;
5441 else
5442 int_target_mode = as_a <scalar_int_mode> (target_mode);
5443 if (!target)
5444 target = gen_reg_rtx (int_target_mode);
5446 comparison = gen_rtx_fmt_ee (code, result_mode, x, y);
5448 create_output_operand (&ops[0], optimize ? NULL_RTX : target, result_mode);
5449 create_fixed_operand (&ops[1], comparison);
5450 create_fixed_operand (&ops[2], x);
5451 create_fixed_operand (&ops[3], y);
5452 if (!maybe_expand_insn (icode, 4, ops))
5454 delete_insns_since (last);
5455 return NULL_RTX;
5457 subtarget = ops[0].value;
5459 /* If we are converting to a wider mode, first convert to
5460 INT_TARGET_MODE, then normalize. This produces better combining
5461 opportunities on machines that have a SIGN_EXTRACT when we are
5462 testing a single bit. This mostly benefits the 68k.
5464 If STORE_FLAG_VALUE does not have the sign bit set when
5465 interpreted in MODE, we can do this conversion as unsigned, which
5466 is usually more efficient. */
5467 if (GET_MODE_PRECISION (int_target_mode) > GET_MODE_PRECISION (result_mode))
5469 gcc_assert (GET_MODE_PRECISION (result_mode) != 1
5470 || STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1);
5472 bool unsignedp = (STORE_FLAG_VALUE >= 0);
5473 convert_move (target, subtarget, unsignedp);
5475 op0 = target;
5476 result_mode = int_target_mode;
5478 else
5479 op0 = subtarget;
5481 /* If we want to keep subexpressions around, don't reuse our last
5482 target. */
5483 if (optimize)
5484 subtarget = 0;
5486 /* Now normalize to the proper value in MODE. Sometimes we don't
5487 have to do anything. */
5488 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
5490 /* STORE_FLAG_VALUE might be the most negative number, so write
5491 the comparison this way to avoid a compiler-time warning. */
5492 else if (- normalizep == STORE_FLAG_VALUE)
5493 op0 = expand_unop (result_mode, neg_optab, op0, subtarget, 0);
5495 /* We don't want to use STORE_FLAG_VALUE < 0 below since this makes
5496 it hard to use a value of just the sign bit due to ANSI integer
5497 constant typing rules. */
5498 else if (val_signbit_known_set_p (result_mode, STORE_FLAG_VALUE))
5499 op0 = expand_shift (RSHIFT_EXPR, result_mode, op0,
5500 GET_MODE_BITSIZE (result_mode) - 1, subtarget,
5501 normalizep == 1);
5502 else
5504 gcc_assert (STORE_FLAG_VALUE & 1);
5506 op0 = expand_and (result_mode, op0, const1_rtx, subtarget);
5507 if (normalizep == -1)
5508 op0 = expand_unop (result_mode, neg_optab, op0, op0, 0);
5511 /* If we were converting to a smaller mode, do the conversion now. */
5512 if (int_target_mode != result_mode)
5514 convert_move (target, op0, 0);
5515 return target;
5517 else
5518 return op0;
5522 /* A subroutine of emit_store_flag only including "tricks" that do not
5523 need a recursive call. These are kept separate to avoid infinite
5524 loops. */
5526 static rtx
5527 emit_store_flag_1 (rtx target, enum rtx_code code, rtx op0, rtx op1,
5528 machine_mode mode, int unsignedp, int normalizep,
5529 machine_mode target_mode)
5531 rtx subtarget;
5532 enum insn_code icode;
5533 machine_mode compare_mode;
5534 enum mode_class mclass;
5535 enum rtx_code scode;
5537 if (unsignedp)
5538 code = unsigned_condition (code);
5539 scode = swap_condition (code);
5541 /* If one operand is constant, make it the second one. Only do this
5542 if the other operand is not constant as well. */
5544 if (swap_commutative_operands_p (op0, op1))
5546 std::swap (op0, op1);
5547 code = swap_condition (code);
5550 if (mode == VOIDmode)
5551 mode = GET_MODE (op0);
5553 if (CONST_SCALAR_INT_P (op1))
5554 canonicalize_comparison (mode, &code, &op1);
5556 /* For some comparisons with 1 and -1, we can convert this to
5557 comparisons with zero. This will often produce more opportunities for
5558 store-flag insns. */
5560 switch (code)
5562 case LT:
5563 if (op1 == const1_rtx)
5564 op1 = const0_rtx, code = LE;
5565 break;
5566 case LE:
5567 if (op1 == constm1_rtx)
5568 op1 = const0_rtx, code = LT;
5569 break;
5570 case GE:
5571 if (op1 == const1_rtx)
5572 op1 = const0_rtx, code = GT;
5573 break;
5574 case GT:
5575 if (op1 == constm1_rtx)
5576 op1 = const0_rtx, code = GE;
5577 break;
5578 case GEU:
5579 if (op1 == const1_rtx)
5580 op1 = const0_rtx, code = NE;
5581 break;
5582 case LTU:
5583 if (op1 == const1_rtx)
5584 op1 = const0_rtx, code = EQ;
5585 break;
5586 default:
5587 break;
5590 /* If we are comparing a double-word integer with zero or -1, we can
5591 convert the comparison into one involving a single word. */
5592 scalar_int_mode int_mode;
5593 if (is_int_mode (mode, &int_mode)
5594 && GET_MODE_BITSIZE (int_mode) == BITS_PER_WORD * 2
5595 && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0)))
5597 rtx tem;
5598 if ((code == EQ || code == NE)
5599 && (op1 == const0_rtx || op1 == constm1_rtx))
5601 rtx op00, op01;
5603 /* Do a logical OR or AND of the two words and compare the
5604 result. */
5605 op00 = simplify_gen_subreg (word_mode, op0, int_mode, 0);
5606 op01 = simplify_gen_subreg (word_mode, op0, int_mode, UNITS_PER_WORD);
5607 tem = expand_binop (word_mode,
5608 op1 == const0_rtx ? ior_optab : and_optab,
5609 op00, op01, NULL_RTX, unsignedp,
5610 OPTAB_DIRECT);
5612 if (tem != 0)
5613 tem = emit_store_flag (NULL_RTX, code, tem, op1, word_mode,
5614 unsignedp, normalizep);
5616 else if ((code == LT || code == GE) && op1 == const0_rtx)
5618 rtx op0h;
5620 /* If testing the sign bit, can just test on high word. */
5621 op0h = simplify_gen_subreg (word_mode, op0, int_mode,
5622 subreg_highpart_offset (word_mode,
5623 int_mode));
5624 tem = emit_store_flag (NULL_RTX, code, op0h, op1, word_mode,
5625 unsignedp, normalizep);
5627 else
5628 tem = NULL_RTX;
5630 if (tem)
5632 if (target_mode == VOIDmode || GET_MODE (tem) == target_mode)
5633 return tem;
5634 if (!target)
5635 target = gen_reg_rtx (target_mode);
5637 convert_move (target, tem,
5638 !val_signbit_known_set_p (word_mode,
5639 (normalizep ? normalizep
5640 : STORE_FLAG_VALUE)));
5641 return target;
5645 /* If this is A < 0 or A >= 0, we can do this by taking the ones
5646 complement of A (for GE) and shifting the sign bit to the low bit. */
5647 if (op1 == const0_rtx && (code == LT || code == GE)
5648 && is_int_mode (mode, &int_mode)
5649 && (normalizep || STORE_FLAG_VALUE == 1
5650 || val_signbit_p (int_mode, STORE_FLAG_VALUE)))
5652 scalar_int_mode int_target_mode;
5653 subtarget = target;
5655 if (!target)
5656 int_target_mode = int_mode;
5657 else
5659 /* If the result is to be wider than OP0, it is best to convert it
5660 first. If it is to be narrower, it is *incorrect* to convert it
5661 first. */
5662 int_target_mode = as_a <scalar_int_mode> (target_mode);
5663 if (GET_MODE_SIZE (int_target_mode) > GET_MODE_SIZE (int_mode))
5665 op0 = convert_modes (int_target_mode, int_mode, op0, 0);
5666 int_mode = int_target_mode;
5670 if (int_target_mode != int_mode)
5671 subtarget = 0;
5673 if (code == GE)
5674 op0 = expand_unop (int_mode, one_cmpl_optab, op0,
5675 ((STORE_FLAG_VALUE == 1 || normalizep)
5676 ? 0 : subtarget), 0);
5678 if (STORE_FLAG_VALUE == 1 || normalizep)
5679 /* If we are supposed to produce a 0/1 value, we want to do
5680 a logical shift from the sign bit to the low-order bit; for
5681 a -1/0 value, we do an arithmetic shift. */
5682 op0 = expand_shift (RSHIFT_EXPR, int_mode, op0,
5683 GET_MODE_BITSIZE (int_mode) - 1,
5684 subtarget, normalizep != -1);
5686 if (int_mode != int_target_mode)
5687 op0 = convert_modes (int_target_mode, int_mode, op0, 0);
5689 return op0;
5692 mclass = GET_MODE_CLASS (mode);
5693 FOR_EACH_MODE_FROM (compare_mode, mode)
5695 machine_mode optab_mode = mclass == MODE_CC ? CCmode : compare_mode;
5696 icode = optab_handler (cstore_optab, optab_mode);
5697 if (icode != CODE_FOR_nothing)
5699 do_pending_stack_adjust ();
5700 rtx tem = emit_cstore (target, icode, code, mode, compare_mode,
5701 unsignedp, op0, op1, normalizep, target_mode);
5702 if (tem)
5703 return tem;
5705 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5707 tem = emit_cstore (target, icode, scode, mode, compare_mode,
5708 unsignedp, op1, op0, normalizep, target_mode);
5709 if (tem)
5710 return tem;
5712 break;
5716 return 0;
5719 /* Subroutine of emit_store_flag that handles cases in which the operands
5720 are scalar integers. SUBTARGET is the target to use for temporary
5721 operations and TRUEVAL is the value to store when the condition is
5722 true. All other arguments are as for emit_store_flag. */
5725 emit_store_flag_int (rtx target, rtx subtarget, enum rtx_code code, rtx op0,
5726 rtx op1, scalar_int_mode mode, int unsignedp,
5727 int normalizep, rtx trueval)
5729 machine_mode target_mode = target ? GET_MODE (target) : VOIDmode;
5730 rtx_insn *last = get_last_insn ();
5732 /* If this is an equality comparison of integers, we can try to exclusive-or
5733 (or subtract) the two operands and use a recursive call to try the
5734 comparison with zero. Don't do any of these cases if branches are
5735 very cheap. */
5737 if ((code == EQ || code == NE) && op1 != const0_rtx)
5739 rtx tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
5740 OPTAB_WIDEN);
5742 if (tem == 0)
5743 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
5744 OPTAB_WIDEN);
5745 if (tem != 0)
5746 tem = emit_store_flag (target, code, tem, const0_rtx,
5747 mode, unsignedp, normalizep);
5748 if (tem != 0)
5749 return tem;
5751 delete_insns_since (last);
5754 /* For integer comparisons, try the reverse comparison. However, for
5755 small X and if we'd have anyway to extend, implementing "X != 0"
5756 as "-(int)X >> 31" is still cheaper than inverting "(int)X == 0". */
5757 rtx_code rcode = reverse_condition (code);
5758 if (can_compare_p (rcode, mode, ccp_store_flag)
5759 && ! (optab_handler (cstore_optab, mode) == CODE_FOR_nothing
5760 && code == NE
5761 && GET_MODE_SIZE (mode) < UNITS_PER_WORD
5762 && op1 == const0_rtx))
5764 int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
5765 || (STORE_FLAG_VALUE == -1 && normalizep == 1));
5767 /* Again, for the reverse comparison, use either an addition or a XOR. */
5768 if (want_add
5769 && rtx_cost (GEN_INT (normalizep), mode, PLUS, 1,
5770 optimize_insn_for_speed_p ()) == 0)
5772 rtx tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5773 STORE_FLAG_VALUE, target_mode);
5774 if (tem != 0)
5775 tem = expand_binop (target_mode, add_optab, tem,
5776 gen_int_mode (normalizep, target_mode),
5777 target, 0, OPTAB_WIDEN);
5778 if (tem != 0)
5779 return tem;
5781 else if (!want_add
5782 && rtx_cost (trueval, mode, XOR, 1,
5783 optimize_insn_for_speed_p ()) == 0)
5785 rtx tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5786 normalizep, target_mode);
5787 if (tem != 0)
5788 tem = expand_binop (target_mode, xor_optab, tem, trueval, target,
5789 INTVAL (trueval) >= 0, OPTAB_WIDEN);
5790 if (tem != 0)
5791 return tem;
5794 delete_insns_since (last);
5797 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
5798 the constant zero. Reject all other comparisons at this point. Only
5799 do LE and GT if branches are expensive since they are expensive on
5800 2-operand machines. */
5802 if (op1 != const0_rtx
5803 || (code != EQ && code != NE
5804 && (BRANCH_COST (optimize_insn_for_speed_p (),
5805 false) <= 1 || (code != LE && code != GT))))
5806 return 0;
5808 /* Try to put the result of the comparison in the sign bit. Assume we can't
5809 do the necessary operation below. */
5811 rtx tem = 0;
5813 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
5814 the sign bit set. */
5816 if (code == LE)
5818 /* This is destructive, so SUBTARGET can't be OP0. */
5819 if (rtx_equal_p (subtarget, op0))
5820 subtarget = 0;
5822 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
5823 OPTAB_WIDEN);
5824 if (tem)
5825 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
5826 OPTAB_WIDEN);
5829 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
5830 number of bits in the mode of OP0, minus one. */
5832 if (code == GT)
5834 if (rtx_equal_p (subtarget, op0))
5835 subtarget = 0;
5837 tem = maybe_expand_shift (RSHIFT_EXPR, mode, op0,
5838 GET_MODE_BITSIZE (mode) - 1,
5839 subtarget, 0);
5840 if (tem)
5841 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
5842 OPTAB_WIDEN);
5845 if (code == EQ || code == NE)
5847 /* For EQ or NE, one way to do the comparison is to apply an operation
5848 that converts the operand into a positive number if it is nonzero
5849 or zero if it was originally zero. Then, for EQ, we subtract 1 and
5850 for NE we negate. This puts the result in the sign bit. Then we
5851 normalize with a shift, if needed.
5853 Two operations that can do the above actions are ABS and FFS, so try
5854 them. If that doesn't work, and MODE is smaller than a full word,
5855 we can use zero-extension to the wider mode (an unsigned conversion)
5856 as the operation. */
5858 /* Note that ABS doesn't yield a positive number for INT_MIN, but
5859 that is compensated by the subsequent overflow when subtracting
5860 one / negating. */
5862 if (optab_handler (abs_optab, mode) != CODE_FOR_nothing)
5863 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
5864 else if (optab_handler (ffs_optab, mode) != CODE_FOR_nothing)
5865 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
5866 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5868 tem = convert_modes (word_mode, mode, op0, 1);
5869 mode = word_mode;
5872 if (tem != 0)
5874 if (code == EQ)
5875 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
5876 0, OPTAB_WIDEN);
5877 else
5878 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
5881 /* If we couldn't do it that way, for NE we can "or" the two's complement
5882 of the value with itself. For EQ, we take the one's complement of
5883 that "or", which is an extra insn, so we only handle EQ if branches
5884 are expensive. */
5886 if (tem == 0
5887 && (code == NE
5888 || BRANCH_COST (optimize_insn_for_speed_p (),
5889 false) > 1))
5891 if (rtx_equal_p (subtarget, op0))
5892 subtarget = 0;
5894 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
5895 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
5896 OPTAB_WIDEN);
5898 if (tem && code == EQ)
5899 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
5903 if (tem && normalizep)
5904 tem = maybe_expand_shift (RSHIFT_EXPR, mode, tem,
5905 GET_MODE_BITSIZE (mode) - 1,
5906 subtarget, normalizep == 1);
5908 if (tem)
5910 if (!target)
5912 else if (GET_MODE (tem) != target_mode)
5914 convert_move (target, tem, 0);
5915 tem = target;
5917 else if (!subtarget)
5919 emit_move_insn (target, tem);
5920 tem = target;
5923 else
5924 delete_insns_since (last);
5926 return tem;
5929 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
5930 and storing in TARGET. Normally return TARGET.
5931 Return 0 if that cannot be done.
5933 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
5934 it is VOIDmode, they cannot both be CONST_INT.
5936 UNSIGNEDP is for the case where we have to widen the operands
5937 to perform the operation. It says to use zero-extension.
5939 NORMALIZEP is 1 if we should convert the result to be either zero
5940 or one. Normalize is -1 if we should convert the result to be
5941 either zero or -1. If NORMALIZEP is zero, the result will be left
5942 "raw" out of the scc insn. */
5945 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
5946 machine_mode mode, int unsignedp, int normalizep)
5948 machine_mode target_mode = target ? GET_MODE (target) : VOIDmode;
5949 enum rtx_code rcode;
5950 rtx subtarget;
5951 rtx tem, trueval;
5952 rtx_insn *last;
5954 /* If we compare constants, we shouldn't use a store-flag operation,
5955 but a constant load. We can get there via the vanilla route that
5956 usually generates a compare-branch sequence, but will in this case
5957 fold the comparison to a constant, and thus elide the branch. */
5958 if (CONSTANT_P (op0) && CONSTANT_P (op1))
5959 return NULL_RTX;
5961 tem = emit_store_flag_1 (target, code, op0, op1, mode, unsignedp, normalizep,
5962 target_mode);
5963 if (tem)
5964 return tem;
5966 /* If we reached here, we can't do this with a scc insn, however there
5967 are some comparisons that can be done in other ways. Don't do any
5968 of these cases if branches are very cheap. */
5969 if (BRANCH_COST (optimize_insn_for_speed_p (), false) == 0)
5970 return 0;
5972 /* See what we need to return. We can only return a 1, -1, or the
5973 sign bit. */
5975 if (normalizep == 0)
5977 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
5978 normalizep = STORE_FLAG_VALUE;
5980 else if (val_signbit_p (mode, STORE_FLAG_VALUE))
5982 else
5983 return 0;
5986 last = get_last_insn ();
5988 /* If optimizing, use different pseudo registers for each insn, instead
5989 of reusing the same pseudo. This leads to better CSE, but slows
5990 down the compiler, since there are more pseudos. */
5991 subtarget = (!optimize
5992 && (target_mode == mode)) ? target : NULL_RTX;
5993 trueval = GEN_INT (normalizep ? normalizep : STORE_FLAG_VALUE);
5995 /* For floating-point comparisons, try the reverse comparison or try
5996 changing the "orderedness" of the comparison. */
5997 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5999 enum rtx_code first_code;
6000 bool and_them;
6002 rcode = reverse_condition_maybe_unordered (code);
6003 if (can_compare_p (rcode, mode, ccp_store_flag)
6004 && (code == ORDERED || code == UNORDERED
6005 || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
6006 || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
6008 int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
6009 || (STORE_FLAG_VALUE == -1 && normalizep == 1));
6011 /* For the reverse comparison, use either an addition or a XOR. */
6012 if (want_add
6013 && rtx_cost (GEN_INT (normalizep), mode, PLUS, 1,
6014 optimize_insn_for_speed_p ()) == 0)
6016 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
6017 STORE_FLAG_VALUE, target_mode);
6018 if (tem)
6019 return expand_binop (target_mode, add_optab, tem,
6020 gen_int_mode (normalizep, target_mode),
6021 target, 0, OPTAB_WIDEN);
6023 else if (!want_add
6024 && rtx_cost (trueval, mode, XOR, 1,
6025 optimize_insn_for_speed_p ()) == 0)
6027 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
6028 normalizep, target_mode);
6029 if (tem)
6030 return expand_binop (target_mode, xor_optab, tem, trueval,
6031 target, INTVAL (trueval) >= 0,
6032 OPTAB_WIDEN);
6036 delete_insns_since (last);
6038 /* Cannot split ORDERED and UNORDERED, only try the above trick. */
6039 if (code == ORDERED || code == UNORDERED)
6040 return 0;
6042 and_them = split_comparison (code, mode, &first_code, &code);
6044 /* If there are no NaNs, the first comparison should always fall through.
6045 Effectively change the comparison to the other one. */
6046 if (!HONOR_NANS (mode))
6048 gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
6049 return emit_store_flag_1 (target, code, op0, op1, mode, 0, normalizep,
6050 target_mode);
6053 if (!HAVE_conditional_move)
6054 return 0;
6056 /* Do not turn a trapping comparison into a non-trapping one. */
6057 if ((code != EQ && code != NE && code != UNEQ && code != LTGT)
6058 && flag_trapping_math)
6059 return 0;
6061 /* Try using a setcc instruction for ORDERED/UNORDERED, followed by a
6062 conditional move. */
6063 tem = emit_store_flag_1 (subtarget, first_code, op0, op1, mode, 0,
6064 normalizep, target_mode);
6065 if (tem == 0)
6066 return 0;
6068 if (and_them)
6069 tem = emit_conditional_move (target, code, op0, op1, mode,
6070 tem, const0_rtx, GET_MODE (tem), 0);
6071 else
6072 tem = emit_conditional_move (target, code, op0, op1, mode,
6073 trueval, tem, GET_MODE (tem), 0);
6075 if (tem == 0)
6076 delete_insns_since (last);
6077 return tem;
6080 /* The remaining tricks only apply to integer comparisons. */
6082 scalar_int_mode int_mode;
6083 if (is_int_mode (mode, &int_mode))
6084 return emit_store_flag_int (target, subtarget, code, op0, op1, int_mode,
6085 unsignedp, normalizep, trueval);
6087 return 0;
6090 /* Like emit_store_flag, but always succeeds. */
6093 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
6094 machine_mode mode, int unsignedp, int normalizep)
6096 rtx tem;
6097 rtx_code_label *label;
6098 rtx trueval, falseval;
6100 /* First see if emit_store_flag can do the job. */
6101 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
6102 if (tem != 0)
6103 return tem;
6105 /* If one operand is constant, make it the second one. Only do this
6106 if the other operand is not constant as well. */
6107 if (swap_commutative_operands_p (op0, op1))
6109 std::swap (op0, op1);
6110 code = swap_condition (code);
6113 if (mode == VOIDmode)
6114 mode = GET_MODE (op0);
6116 if (!target)
6117 target = gen_reg_rtx (word_mode);
6119 /* If this failed, we have to do this with set/compare/jump/set code.
6120 For foo != 0, if foo is in OP0, just replace it with 1 if nonzero. */
6121 trueval = normalizep ? GEN_INT (normalizep) : const1_rtx;
6122 if (code == NE
6123 && GET_MODE_CLASS (mode) == MODE_INT
6124 && REG_P (target)
6125 && op0 == target
6126 && op1 == const0_rtx)
6128 label = gen_label_rtx ();
6129 do_compare_rtx_and_jump (target, const0_rtx, EQ, unsignedp, mode,
6130 NULL_RTX, NULL, label,
6131 profile_probability::uninitialized ());
6132 emit_move_insn (target, trueval);
6133 emit_label (label);
6134 return target;
6137 if (!REG_P (target)
6138 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
6139 target = gen_reg_rtx (GET_MODE (target));
6141 /* Jump in the right direction if the target cannot implement CODE
6142 but can jump on its reverse condition. */
6143 falseval = const0_rtx;
6144 if (! can_compare_p (code, mode, ccp_jump)
6145 && (! FLOAT_MODE_P (mode)
6146 || code == ORDERED || code == UNORDERED
6147 || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
6148 || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
6150 enum rtx_code rcode;
6151 if (FLOAT_MODE_P (mode))
6152 rcode = reverse_condition_maybe_unordered (code);
6153 else
6154 rcode = reverse_condition (code);
6156 /* Canonicalize to UNORDERED for the libcall. */
6157 if (can_compare_p (rcode, mode, ccp_jump)
6158 || (code == ORDERED && ! can_compare_p (ORDERED, mode, ccp_jump)))
6160 falseval = trueval;
6161 trueval = const0_rtx;
6162 code = rcode;
6166 emit_move_insn (target, trueval);
6167 label = gen_label_rtx ();
6168 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX, NULL,
6169 label, profile_probability::uninitialized ());
6171 emit_move_insn (target, falseval);
6172 emit_label (label);
6174 return target;
6177 /* Helper function for canonicalize_cmp_for_target. Swap between inclusive
6178 and exclusive ranges in order to create an equivalent comparison. See
6179 canonicalize_cmp_for_target for the possible cases. */
6181 static enum rtx_code
6182 equivalent_cmp_code (enum rtx_code code)
6184 switch (code)
6186 case GT:
6187 return GE;
6188 case GE:
6189 return GT;
6190 case LT:
6191 return LE;
6192 case LE:
6193 return LT;
6194 case GTU:
6195 return GEU;
6196 case GEU:
6197 return GTU;
6198 case LTU:
6199 return LEU;
6200 case LEU:
6201 return LTU;
6203 default:
6204 return code;
6208 /* Choose the more appropiate immediate in scalar integer comparisons. The
6209 purpose of this is to end up with an immediate which can be loaded into a
6210 register in fewer moves, if possible.
6212 For each integer comparison there exists an equivalent choice:
6213 i) a > b or a >= b + 1
6214 ii) a <= b or a < b + 1
6215 iii) a >= b or a > b - 1
6216 iv) a < b or a <= b - 1
6218 MODE is the mode of the first operand.
6219 CODE points to the comparison code.
6220 IMM points to the rtx containing the immediate. *IMM must satisfy
6221 CONST_SCALAR_INT_P on entry and continues to satisfy CONST_SCALAR_INT_P
6222 on exit. */
6224 void
6225 canonicalize_comparison (machine_mode mode, enum rtx_code *code, rtx *imm)
6227 if (!SCALAR_INT_MODE_P (mode))
6228 return;
6230 int to_add = 0;
6231 enum signop sgn = unsigned_condition_p (*code) ? UNSIGNED : SIGNED;
6233 /* Extract the immediate value from the rtx. */
6234 wide_int imm_val = rtx_mode_t (*imm, mode);
6236 if (*code == GT || *code == GTU || *code == LE || *code == LEU)
6237 to_add = 1;
6238 else if (*code == GE || *code == GEU || *code == LT || *code == LTU)
6239 to_add = -1;
6240 else
6241 return;
6243 /* Check for overflow/underflow in the case of signed values and
6244 wrapping around in the case of unsigned values. If any occur
6245 cancel the optimization. */
6246 wi::overflow_type overflow = wi::OVF_NONE;
6247 wide_int imm_modif;
6249 if (to_add == 1)
6250 imm_modif = wi::add (imm_val, 1, sgn, &overflow);
6251 else
6252 imm_modif = wi::sub (imm_val, 1, sgn, &overflow);
6254 if (overflow)
6255 return;
6257 /* The following creates a pseudo; if we cannot do that, bail out. */
6258 if (!can_create_pseudo_p ())
6259 return;
6261 rtx reg = gen_rtx_REG (mode, LAST_VIRTUAL_REGISTER + 1);
6262 rtx new_imm = immed_wide_int_const (imm_modif, mode);
6264 rtx_insn *old_rtx = gen_move_insn (reg, *imm);
6265 rtx_insn *new_rtx = gen_move_insn (reg, new_imm);
6267 /* Update the immediate and the code. */
6268 if (insn_cost (old_rtx, true) > insn_cost (new_rtx, true))
6270 *code = equivalent_cmp_code (*code);
6271 *imm = new_imm;
6277 /* Perform possibly multi-word comparison and conditional jump to LABEL
6278 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE. This is
6279 now a thin wrapper around do_compare_rtx_and_jump. */
6281 static void
6282 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, machine_mode mode,
6283 rtx_code_label *label)
6285 int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU);
6286 do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode, NULL_RTX,
6287 NULL, label, profile_probability::uninitialized ());