1 /* Medium-level subroutines: convert bit-field store and extract
2 and shifts, multiplies and divides to rtl instructions.
3 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 2, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING. If not, write to the Free
20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
26 #include "coretypes.h"
33 #include "insn-config.h"
38 #include "langhooks.h"
40 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
41 unsigned HOST_WIDE_INT,
42 unsigned HOST_WIDE_INT, rtx);
43 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
44 unsigned HOST_WIDE_INT, rtx);
45 static rtx extract_fixed_bit_field (enum machine_mode, rtx,
46 unsigned HOST_WIDE_INT,
47 unsigned HOST_WIDE_INT,
48 unsigned HOST_WIDE_INT, rtx, int);
49 static rtx mask_rtx (enum machine_mode, int, int, int);
50 static rtx lshift_value (enum machine_mode, rtx, int, int);
51 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
52 unsigned HOST_WIDE_INT, int);
53 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx);
55 /* Nonzero means divides or modulus operations are relatively cheap for
56 powers of two, so don't use branches; emit the operation instead.
57 Usually, this will mean that the MD file will emit non-branch
60 static int sdiv_pow2_cheap, smod_pow2_cheap;
62 #ifndef SLOW_UNALIGNED_ACCESS
63 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
66 /* For compilers that support multiple targets with different word sizes,
67 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example
68 is the H8/300(H) compiler. */
70 #ifndef MAX_BITS_PER_WORD
71 #define MAX_BITS_PER_WORD BITS_PER_WORD
74 /* Reduce conditional compilation elsewhere. */
77 #define CODE_FOR_insv CODE_FOR_nothing
78 #define gen_insv(a,b,c,d) NULL_RTX
82 #define CODE_FOR_extv CODE_FOR_nothing
83 #define gen_extv(a,b,c,d) NULL_RTX
87 #define CODE_FOR_extzv CODE_FOR_nothing
88 #define gen_extzv(a,b,c,d) NULL_RTX
91 /* Cost of various pieces of RTL. Note that some of these are indexed by
92 shift count and some by mode. */
93 static int add_cost, negate_cost, zero_cost;
94 static int shift_cost[MAX_BITS_PER_WORD];
95 static int shiftadd_cost[MAX_BITS_PER_WORD];
96 static int shiftsub_cost[MAX_BITS_PER_WORD];
97 static int mul_cost[NUM_MACHINE_MODES];
98 static int div_cost[NUM_MACHINE_MODES];
99 static int mul_widen_cost[NUM_MACHINE_MODES];
100 static int mul_highpart_cost[NUM_MACHINE_MODES];
105 rtx reg, shift_insn, shiftadd_insn, shiftsub_insn;
108 enum machine_mode mode, wider_mode;
112 /* This is "some random pseudo register" for purposes of calling recog
113 to see what insns exist. */
114 reg = gen_rtx_REG (word_mode, 10000);
116 zero_cost = rtx_cost (const0_rtx, 0);
117 add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
119 shift_insn = emit_insn (gen_rtx_SET (VOIDmode, reg,
120 gen_rtx_ASHIFT (word_mode, reg,
124 = emit_insn (gen_rtx_SET (VOIDmode, reg,
125 gen_rtx_PLUS (word_mode,
126 gen_rtx_MULT (word_mode,
131 = emit_insn (gen_rtx_SET (VOIDmode, reg,
132 gen_rtx_MINUS (word_mode,
133 gen_rtx_MULT (word_mode,
140 shiftadd_cost[0] = shiftsub_cost[0] = add_cost;
142 for (m = 1; m < MAX_BITS_PER_WORD; m++)
144 rtx c_int = GEN_INT ((HOST_WIDE_INT) 1 << m);
145 shift_cost[m] = shiftadd_cost[m] = shiftsub_cost[m] = 32000;
147 XEXP (SET_SRC (PATTERN (shift_insn)), 1) = GEN_INT (m);
148 if (recog (PATTERN (shift_insn), shift_insn, &dummy) >= 0)
149 shift_cost[m] = rtx_cost (SET_SRC (PATTERN (shift_insn)), SET);
151 XEXP (XEXP (SET_SRC (PATTERN (shiftadd_insn)), 0), 1) = c_int;
152 if (recog (PATTERN (shiftadd_insn), shiftadd_insn, &dummy) >= 0)
153 shiftadd_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftadd_insn)), SET);
155 XEXP (XEXP (SET_SRC (PATTERN (shiftsub_insn)), 0), 1) = c_int;
156 if (recog (PATTERN (shiftsub_insn), shiftsub_insn, &dummy) >= 0)
157 shiftsub_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftsub_insn)), SET);
160 negate_cost = rtx_cost (gen_rtx_NEG (word_mode, reg), SET);
163 = (rtx_cost (gen_rtx_DIV (word_mode, reg, GEN_INT (32)), SET)
166 = (rtx_cost (gen_rtx_MOD (word_mode, reg, GEN_INT (32)), SET)
169 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
171 mode = GET_MODE_WIDER_MODE (mode))
173 reg = gen_rtx_REG (mode, 10000);
174 div_cost[(int) mode] = rtx_cost (gen_rtx_UDIV (mode, reg, reg), SET);
175 mul_cost[(int) mode] = rtx_cost (gen_rtx_MULT (mode, reg, reg), SET);
176 wider_mode = GET_MODE_WIDER_MODE (mode);
177 if (wider_mode != VOIDmode)
179 mul_widen_cost[(int) wider_mode]
180 = rtx_cost (gen_rtx_MULT (wider_mode,
181 gen_rtx_ZERO_EXTEND (wider_mode, reg),
182 gen_rtx_ZERO_EXTEND (wider_mode, reg)),
184 mul_highpart_cost[(int) mode]
185 = rtx_cost (gen_rtx_TRUNCATE
187 gen_rtx_LSHIFTRT (wider_mode,
188 gen_rtx_MULT (wider_mode,
193 GEN_INT (GET_MODE_BITSIZE (mode)))),
201 /* Return an rtx representing minus the value of X.
202 MODE is the intended mode of the result,
203 useful if X is a CONST_INT. */
206 negate_rtx (enum machine_mode mode, rtx x)
208 rtx result = simplify_unary_operation (NEG, mode, x, mode);
211 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
216 /* Report on the availability of insv/extv/extzv and the desired mode
217 of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo
218 is false; else the mode of the specified operand. If OPNO is -1,
219 all the caller cares about is whether the insn is available. */
221 mode_for_extraction (enum extraction_pattern pattern, int opno)
223 const struct insn_data *data;
230 data = &insn_data[CODE_FOR_insv];
233 return MAX_MACHINE_MODE;
238 data = &insn_data[CODE_FOR_extv];
241 return MAX_MACHINE_MODE;
246 data = &insn_data[CODE_FOR_extzv];
249 return MAX_MACHINE_MODE;
258 /* Everyone who uses this function used to follow it with
259 if (result == VOIDmode) result = word_mode; */
260 if (data->operand[opno].mode == VOIDmode)
262 return data->operand[opno].mode;
266 /* Generate code to store value from rtx VALUE
267 into a bit-field within structure STR_RTX
268 containing BITSIZE bits starting at bit BITNUM.
269 FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
270 ALIGN is the alignment that STR_RTX is known to have.
271 TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */
273 /* ??? Note that there are two different ideas here for how
274 to determine the size to count bits within, for a register.
275 One is BITS_PER_WORD, and the other is the size of operand 3
278 If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
279 else, we use the mode of operand 3. */
282 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
283 unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode,
284 rtx value, HOST_WIDE_INT total_size)
287 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
288 unsigned HOST_WIDE_INT offset = bitnum / unit;
289 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
293 enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
295 /* Discount the part of the structure before the desired byte.
296 We need to know how many bytes are safe to reference after it. */
298 total_size -= (bitpos / BIGGEST_ALIGNMENT
299 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
301 while (GET_CODE (op0) == SUBREG)
303 /* The following line once was done only if WORDS_BIG_ENDIAN,
304 but I think that is a mistake. WORDS_BIG_ENDIAN is
305 meaningful at a much higher level; when structures are copied
306 between memory and regs, the higher-numbered regs
307 always get higher addresses. */
308 offset += (SUBREG_BYTE (op0) / UNITS_PER_WORD);
309 /* We used to adjust BITPOS here, but now we do the whole adjustment
310 right after the loop. */
311 op0 = SUBREG_REG (op0);
314 value = protect_from_queue (value, 0);
316 /* Use vec_extract patterns for extracting parts of vectors whenever
318 if (VECTOR_MODE_P (GET_MODE (op0))
319 && GET_CODE (op0) != MEM
320 && (vec_set_optab->handlers[(int)GET_MODE (op0)].insn_code
322 && fieldmode == GET_MODE_INNER (GET_MODE (op0))
323 && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
324 && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
326 enum machine_mode outermode = GET_MODE (op0);
327 enum machine_mode innermode = GET_MODE_INNER (outermode);
328 int icode = (int) vec_set_optab->handlers[(int) outermode].insn_code;
329 int pos = bitnum / GET_MODE_BITSIZE (innermode);
330 rtx rtxpos = GEN_INT (pos);
334 enum machine_mode mode0 = insn_data[icode].operand[0].mode;
335 enum machine_mode mode1 = insn_data[icode].operand[1].mode;
336 enum machine_mode mode2 = insn_data[icode].operand[2].mode;
340 if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
341 src = copy_to_mode_reg (mode1, src);
343 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
344 rtxpos = copy_to_mode_reg (mode1, rtxpos);
346 /* We could handle this, but we should always be called with a pseudo
347 for our targets and all insns should take them as outputs. */
348 if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)
349 || ! (*insn_data[icode].operand[1].predicate) (src, mode1)
350 || ! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
352 pat = GEN_FCN (icode) (dest, src, rtxpos);
365 int old_generating_concat_p = generating_concat_p;
366 generating_concat_p = 0;
367 value = force_not_mem (value);
368 generating_concat_p = old_generating_concat_p;
371 /* If the target is a register, overwriting the entire object, or storing
372 a full-word or multi-word field can be done with just a SUBREG.
374 If the target is memory, storing any naturally aligned field can be
375 done with a simple store. For targets that support fast unaligned
376 memory, any naturally sized, unit aligned field can be done directly. */
378 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
379 + (offset * UNITS_PER_WORD);
382 && bitsize == GET_MODE_BITSIZE (fieldmode)
383 && (GET_CODE (op0) != MEM
384 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
385 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
386 && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
387 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
388 || (offset * BITS_PER_UNIT % bitsize == 0
389 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
391 if (GET_MODE (op0) != fieldmode)
393 if (GET_CODE (op0) == SUBREG)
395 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
396 || GET_MODE_CLASS (fieldmode) == MODE_INT
397 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
398 op0 = SUBREG_REG (op0);
400 /* Else we've got some float mode source being extracted into
401 a different float mode destination -- this combination of
402 subregs results in Severe Tire Damage. */
405 if (GET_CODE (op0) == REG)
406 op0 = gen_rtx_SUBREG (fieldmode, op0, byte_offset);
408 op0 = adjust_address (op0, fieldmode, offset);
410 emit_move_insn (op0, value);
414 /* Make sure we are playing with integral modes. Pun with subregs
415 if we aren't. This must come after the entire register case above,
416 since that case is valid for any mode. The following cases are only
417 valid for integral modes. */
419 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
420 if (imode != GET_MODE (op0))
422 if (GET_CODE (op0) == MEM)
423 op0 = adjust_address (op0, imode, 0);
424 else if (imode != BLKmode)
425 op0 = gen_lowpart (imode, op0);
431 /* We may be accessing data outside the field, which means
432 we can alias adjacent data. */
433 if (GET_CODE (op0) == MEM)
435 op0 = shallow_copy_rtx (op0);
436 set_mem_alias_set (op0, 0);
437 set_mem_expr (op0, 0);
440 /* If OP0 is a register, BITPOS must count within a word.
441 But as we have it, it counts within whatever size OP0 now has.
442 On a bigendian machine, these are not the same, so convert. */
444 && GET_CODE (op0) != MEM
445 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
446 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
448 /* Storing an lsb-aligned field in a register
449 can be done with a movestrict instruction. */
451 if (GET_CODE (op0) != MEM
452 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
453 && bitsize == GET_MODE_BITSIZE (fieldmode)
454 && (movstrict_optab->handlers[(int) fieldmode].insn_code
455 != CODE_FOR_nothing))
457 int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
459 /* Get appropriate low part of the value being stored. */
460 if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
461 value = gen_lowpart (fieldmode, value);
462 else if (!(GET_CODE (value) == SYMBOL_REF
463 || GET_CODE (value) == LABEL_REF
464 || GET_CODE (value) == CONST))
465 value = convert_to_mode (fieldmode, value, 0);
467 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
468 value = copy_to_mode_reg (fieldmode, value);
470 if (GET_CODE (op0) == SUBREG)
472 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
473 || GET_MODE_CLASS (fieldmode) == MODE_INT
474 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
475 op0 = SUBREG_REG (op0);
477 /* Else we've got some float mode source being extracted into
478 a different float mode destination -- this combination of
479 subregs results in Severe Tire Damage. */
483 emit_insn (GEN_FCN (icode)
484 (gen_rtx_SUBREG (fieldmode, op0,
485 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
486 + (offset * UNITS_PER_WORD)),
492 /* Handle fields bigger than a word. */
494 if (bitsize > BITS_PER_WORD)
496 /* Here we transfer the words of the field
497 in the order least significant first.
498 This is because the most significant word is the one which may
500 However, only do that if the value is not BLKmode. */
502 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
503 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
506 /* This is the mode we must force value to, so that there will be enough
507 subwords to extract. Note that fieldmode will often (always?) be
508 VOIDmode, because that is what store_field uses to indicate that this
509 is a bit field, but passing VOIDmode to operand_subword_force will
510 result in an abort. */
511 fieldmode = GET_MODE (value);
512 if (fieldmode == VOIDmode)
513 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
515 for (i = 0; i < nwords; i++)
517 /* If I is 0, use the low-order word in both field and target;
518 if I is 1, use the next to lowest word; and so on. */
519 unsigned int wordnum = (backwards ? nwords - i - 1 : i);
520 unsigned int bit_offset = (backwards
521 ? MAX ((int) bitsize - ((int) i + 1)
524 : (int) i * BITS_PER_WORD);
526 store_bit_field (op0, MIN (BITS_PER_WORD,
527 bitsize - i * BITS_PER_WORD),
528 bitnum + bit_offset, word_mode,
529 operand_subword_force (value, wordnum, fieldmode),
535 /* From here on we can assume that the field to be stored in is
536 a full-word (whatever type that is), since it is shorter than a word. */
538 /* OFFSET is the number of words or bytes (UNIT says which)
539 from STR_RTX to the first word or byte containing part of the field. */
541 if (GET_CODE (op0) != MEM)
544 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
546 if (GET_CODE (op0) != REG)
548 /* Since this is a destination (lvalue), we can't copy it to a
549 pseudo. We can trivially remove a SUBREG that does not
550 change the size of the operand. Such a SUBREG may have been
551 added above. Otherwise, abort. */
552 if (GET_CODE (op0) == SUBREG
553 && (GET_MODE_SIZE (GET_MODE (op0))
554 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
555 op0 = SUBREG_REG (op0);
559 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
560 op0, (offset * UNITS_PER_WORD));
565 op0 = protect_from_queue (op0, 1);
567 /* If VALUE is a floating-point mode, access it as an integer of the
568 corresponding size. This can occur on a machine with 64 bit registers
569 that uses SFmode for float. This can also occur for unaligned float
571 if (GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
572 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
573 value = gen_lowpart ((GET_MODE (value) == VOIDmode
574 ? word_mode : int_mode_for_mode (GET_MODE (value))),
577 /* Now OFFSET is nonzero only if OP0 is memory
578 and is therefore always measured in bytes. */
581 && GET_MODE (value) != BLKmode
582 && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
583 /* Ensure insv's size is wide enough for this field. */
584 && (GET_MODE_BITSIZE (op_mode) >= bitsize)
585 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
586 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))))
588 int xbitpos = bitpos;
591 rtx last = get_last_insn ();
593 enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
594 int save_volatile_ok = volatile_ok;
598 /* If this machine's insv can only insert into a register, copy OP0
599 into a register and save it back later. */
600 /* This used to check flag_force_mem, but that was a serious
601 de-optimization now that flag_force_mem is enabled by -O2. */
602 if (GET_CODE (op0) == MEM
603 && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
607 enum machine_mode bestmode;
609 /* Get the mode to use for inserting into this field. If OP0 is
610 BLKmode, get the smallest mode consistent with the alignment. If
611 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
612 mode. Otherwise, use the smallest mode containing the field. */
614 if (GET_MODE (op0) == BLKmode
615 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
617 = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
618 MEM_VOLATILE_P (op0));
620 bestmode = GET_MODE (op0);
622 if (bestmode == VOIDmode
623 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
624 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
627 /* Adjust address to point to the containing unit of that mode.
628 Compute offset as multiple of this unit, counting in bytes. */
629 unit = GET_MODE_BITSIZE (bestmode);
630 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
631 bitpos = bitnum % unit;
632 op0 = adjust_address (op0, bestmode, offset);
634 /* Fetch that unit, store the bitfield in it, then store
636 tempreg = copy_to_reg (op0);
637 store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
639 emit_move_insn (op0, tempreg);
642 volatile_ok = save_volatile_ok;
644 /* Add OFFSET into OP0's address. */
645 if (GET_CODE (xop0) == MEM)
646 xop0 = adjust_address (xop0, byte_mode, offset);
648 /* If xop0 is a register, we need it in MAXMODE
649 to make it acceptable to the format of insv. */
650 if (GET_CODE (xop0) == SUBREG)
651 /* We can't just change the mode, because this might clobber op0,
652 and we will need the original value of op0 if insv fails. */
653 xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
654 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
655 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
657 /* On big-endian machines, we count bits from the most significant.
658 If the bit field insn does not, we must invert. */
660 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
661 xbitpos = unit - bitsize - xbitpos;
663 /* We have been counting XBITPOS within UNIT.
664 Count instead within the size of the register. */
665 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
666 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
668 unit = GET_MODE_BITSIZE (maxmode);
670 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */
672 if (GET_MODE (value) != maxmode)
674 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
676 /* Optimization: Don't bother really extending VALUE
677 if it has all the bits we will actually use. However,
678 if we must narrow it, be sure we do it correctly. */
680 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
684 tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0);
686 tmp = simplify_gen_subreg (maxmode,
687 force_reg (GET_MODE (value),
689 GET_MODE (value), 0);
693 value1 = gen_lowpart (maxmode, value1);
695 else if (GET_CODE (value) == CONST_INT)
696 value1 = gen_int_mode (INTVAL (value), maxmode);
697 else if (!CONSTANT_P (value))
698 /* Parse phase is supposed to make VALUE's data type
699 match that of the component reference, which is a type
700 at least as wide as the field; so VALUE should have
701 a mode that corresponds to that type. */
705 /* If this machine's insv insists on a register,
706 get VALUE1 into a register. */
707 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
709 value1 = force_reg (maxmode, value1);
711 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
716 delete_insns_since (last);
717 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
722 /* Insv is not available; store using shifts and boolean ops. */
723 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
727 /* Use shifts and boolean operations to store VALUE
728 into a bit field of width BITSIZE
729 in a memory location specified by OP0 except offset by OFFSET bytes.
730 (OFFSET must be 0 if OP0 is a register.)
731 The field starts at position BITPOS within the byte.
732 (If OP0 is a register, it may be a full word or a narrower mode,
733 but BITPOS still counts within a full word,
734 which is significant on bigendian machines.)
736 Note that protect_from_queue has already been done on OP0 and VALUE. */
739 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset,
740 unsigned HOST_WIDE_INT bitsize,
741 unsigned HOST_WIDE_INT bitpos, rtx value)
743 enum machine_mode mode;
744 unsigned int total_bits = BITS_PER_WORD;
749 /* There is a case not handled here:
750 a structure with a known alignment of just a halfword
751 and a field split across two aligned halfwords within the structure.
752 Or likewise a structure with a known alignment of just a byte
753 and a field split across two bytes.
754 Such cases are not supposed to be able to occur. */
756 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
760 /* Special treatment for a bit field split across two registers. */
761 if (bitsize + bitpos > BITS_PER_WORD)
763 store_split_bit_field (op0, bitsize, bitpos, value);
769 /* Get the proper mode to use for this field. We want a mode that
770 includes the entire field. If such a mode would be larger than
771 a word, we won't be doing the extraction the normal way.
772 We don't want a mode bigger than the destination. */
774 mode = GET_MODE (op0);
775 if (GET_MODE_BITSIZE (mode) == 0
776 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
778 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
779 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
781 if (mode == VOIDmode)
783 /* The only way this should occur is if the field spans word
785 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
790 total_bits = GET_MODE_BITSIZE (mode);
792 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
793 be in the range 0 to total_bits-1, and put any excess bytes in
795 if (bitpos >= total_bits)
797 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
798 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
802 /* Get ref to an aligned byte, halfword, or word containing the field.
803 Adjust BITPOS to be position within a word,
804 and OFFSET to be the offset of that word.
805 Then alter OP0 to refer to that word. */
806 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
807 offset -= (offset % (total_bits / BITS_PER_UNIT));
808 op0 = adjust_address (op0, mode, offset);
811 mode = GET_MODE (op0);
813 /* Now MODE is either some integral mode for a MEM as OP0,
814 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
815 The bit field is contained entirely within OP0.
816 BITPOS is the starting bit number within OP0.
817 (OP0's mode may actually be narrower than MODE.) */
819 if (BYTES_BIG_ENDIAN)
820 /* BITPOS is the distance between our msb
821 and that of the containing datum.
822 Convert it to the distance from the lsb. */
823 bitpos = total_bits - bitsize - bitpos;
825 /* Now BITPOS is always the distance between our lsb
828 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
829 we must first convert its mode to MODE. */
831 if (GET_CODE (value) == CONST_INT)
833 HOST_WIDE_INT v = INTVAL (value);
835 if (bitsize < HOST_BITS_PER_WIDE_INT)
836 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
840 else if ((bitsize < HOST_BITS_PER_WIDE_INT
841 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
842 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
845 value = lshift_value (mode, value, bitpos, bitsize);
849 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
850 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
852 if (GET_MODE (value) != mode)
854 if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
855 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
856 value = gen_lowpart (mode, value);
858 value = convert_to_mode (mode, value, 1);
862 value = expand_binop (mode, and_optab, value,
863 mask_rtx (mode, 0, bitsize, 0),
864 NULL_RTX, 1, OPTAB_LIB_WIDEN);
866 value = expand_shift (LSHIFT_EXPR, mode, value,
867 build_int_2 (bitpos, 0), NULL_RTX, 1);
870 /* Now clear the chosen bits in OP0,
871 except that if VALUE is -1 we need not bother. */
873 subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
877 temp = expand_binop (mode, and_optab, op0,
878 mask_rtx (mode, bitpos, bitsize, 1),
879 subtarget, 1, OPTAB_LIB_WIDEN);
885 /* Now logical-or VALUE into OP0, unless it is zero. */
888 temp = expand_binop (mode, ior_optab, temp, value,
889 subtarget, 1, OPTAB_LIB_WIDEN);
891 emit_move_insn (op0, temp);
894 /* Store a bit field that is split across multiple accessible memory objects.
896 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
897 BITSIZE is the field width; BITPOS the position of its first bit
899 VALUE is the value to store.
901 This does not yet handle fields wider than BITS_PER_WORD. */
904 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
905 unsigned HOST_WIDE_INT bitpos, rtx value)
908 unsigned int bitsdone = 0;
910 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
912 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
913 unit = BITS_PER_WORD;
915 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
917 /* If VALUE is a constant other than a CONST_INT, get it into a register in
918 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
919 that VALUE might be a floating-point constant. */
920 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
922 rtx word = gen_lowpart_common (word_mode, value);
924 if (word && (value != word))
927 value = gen_lowpart_common (word_mode,
928 force_reg (GET_MODE (value) != VOIDmode
930 : word_mode, value));
932 else if (GET_CODE (value) == ADDRESSOF)
933 value = copy_to_reg (value);
935 while (bitsdone < bitsize)
937 unsigned HOST_WIDE_INT thissize;
939 unsigned HOST_WIDE_INT thispos;
940 unsigned HOST_WIDE_INT offset;
942 offset = (bitpos + bitsdone) / unit;
943 thispos = (bitpos + bitsdone) % unit;
945 /* THISSIZE must not overrun a word boundary. Otherwise,
946 store_fixed_bit_field will call us again, and we will mutually
948 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
949 thissize = MIN (thissize, unit - thispos);
951 if (BYTES_BIG_ENDIAN)
955 /* We must do an endian conversion exactly the same way as it is
956 done in extract_bit_field, so that the two calls to
957 extract_fixed_bit_field will have comparable arguments. */
958 if (GET_CODE (value) != MEM || GET_MODE (value) == BLKmode)
959 total_bits = BITS_PER_WORD;
961 total_bits = GET_MODE_BITSIZE (GET_MODE (value));
963 /* Fetch successively less significant portions. */
964 if (GET_CODE (value) == CONST_INT)
965 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
966 >> (bitsize - bitsdone - thissize))
967 & (((HOST_WIDE_INT) 1 << thissize) - 1));
969 /* The args are chosen so that the last part includes the
970 lsb. Give extract_bit_field the value it needs (with
971 endianness compensation) to fetch the piece we want. */
972 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
973 total_bits - bitsize + bitsdone,
978 /* Fetch successively more significant portions. */
979 if (GET_CODE (value) == CONST_INT)
980 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
982 & (((HOST_WIDE_INT) 1 << thissize) - 1));
984 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
985 bitsdone, NULL_RTX, 1);
988 /* If OP0 is a register, then handle OFFSET here.
990 When handling multiword bitfields, extract_bit_field may pass
991 down a word_mode SUBREG of a larger REG for a bitfield that actually
992 crosses a word boundary. Thus, for a SUBREG, we must find
993 the current word starting from the base register. */
994 if (GET_CODE (op0) == SUBREG)
996 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
997 word = operand_subword_force (SUBREG_REG (op0), word_offset,
998 GET_MODE (SUBREG_REG (op0)));
1001 else if (GET_CODE (op0) == REG)
1003 word = operand_subword_force (op0, offset, GET_MODE (op0));
1009 /* OFFSET is in UNITs, and UNIT is in bits.
1010 store_fixed_bit_field wants offset in bytes. */
1011 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
1013 bitsdone += thissize;
1017 /* Generate code to extract a byte-field from STR_RTX
1018 containing BITSIZE bits, starting at BITNUM,
1019 and put it in TARGET if possible (if TARGET is nonzero).
1020 Regardless of TARGET, we return the rtx for where the value is placed.
1023 STR_RTX is the structure containing the byte (a REG or MEM).
1024 UNSIGNEDP is nonzero if this is an unsigned bit field.
1025 MODE is the natural mode of the field value once extracted.
1026 TMODE is the mode the caller would like the value to have;
1027 but the value may be returned with type MODE instead.
1029 TOTAL_SIZE is the size in bytes of the containing structure,
1032 If a TARGET is specified and we can store in it at no extra cost,
1033 we do so, and return TARGET.
1034 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1035 if they are equally easy. */
1038 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1039 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1040 enum machine_mode mode, enum machine_mode tmode,
1041 HOST_WIDE_INT total_size)
1044 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
1045 unsigned HOST_WIDE_INT offset = bitnum / unit;
1046 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
1048 rtx spec_target = target;
1049 rtx spec_target_subreg = 0;
1050 enum machine_mode int_mode;
1051 enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1052 enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1053 enum machine_mode mode1;
1056 /* Discount the part of the structure before the desired byte.
1057 We need to know how many bytes are safe to reference after it. */
1058 if (total_size >= 0)
1059 total_size -= (bitpos / BIGGEST_ALIGNMENT
1060 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
1062 if (tmode == VOIDmode)
1065 while (GET_CODE (op0) == SUBREG)
1067 bitpos += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1070 offset += (bitpos / unit);
1073 op0 = SUBREG_REG (op0);
1076 if (GET_CODE (op0) == REG
1077 && mode == GET_MODE (op0)
1079 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1081 /* We're trying to extract a full register from itself. */
1085 /* Use vec_extract patterns for extracting parts of vectors whenever
1087 if (VECTOR_MODE_P (GET_MODE (op0))
1088 && GET_CODE (op0) != MEM
1089 && (vec_extract_optab->handlers[(int)GET_MODE (op0)].insn_code
1090 != CODE_FOR_nothing)
1091 && ((bitsize + bitnum) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1092 == bitsize / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1094 enum machine_mode outermode = GET_MODE (op0);
1095 enum machine_mode innermode = GET_MODE_INNER (outermode);
1096 int icode = (int) vec_extract_optab->handlers[(int) outermode].insn_code;
1097 int pos = bitnum / GET_MODE_BITSIZE (innermode);
1098 rtx rtxpos = GEN_INT (pos);
1100 rtx dest = NULL, pat, seq;
1101 enum machine_mode mode0 = insn_data[icode].operand[0].mode;
1102 enum machine_mode mode1 = insn_data[icode].operand[1].mode;
1103 enum machine_mode mode2 = insn_data[icode].operand[2].mode;
1105 if (innermode == tmode || innermode == mode)
1109 dest = gen_reg_rtx (innermode);
1113 if (! (*insn_data[icode].operand[0].predicate) (dest, mode0))
1114 dest = copy_to_mode_reg (mode0, dest);
1116 if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
1117 src = copy_to_mode_reg (mode1, src);
1119 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1120 rtxpos = copy_to_mode_reg (mode1, rtxpos);
1122 /* We could handle this, but we should always be called with a pseudo
1123 for our targets and all insns should take them as outputs. */
1124 if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)
1125 || ! (*insn_data[icode].operand[1].predicate) (src, mode1)
1126 || ! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1129 pat = GEN_FCN (icode) (dest, src, rtxpos);
1140 /* Make sure we are playing with integral modes. Pun with subregs
1143 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1144 if (imode != GET_MODE (op0))
1146 if (GET_CODE (op0) == MEM)
1147 op0 = adjust_address (op0, imode, 0);
1148 else if (imode != BLKmode)
1149 op0 = gen_lowpart (imode, op0);
1155 /* We may be accessing data outside the field, which means
1156 we can alias adjacent data. */
1157 if (GET_CODE (op0) == MEM)
1159 op0 = shallow_copy_rtx (op0);
1160 set_mem_alias_set (op0, 0);
1161 set_mem_expr (op0, 0);
1164 /* Extraction of a full-word or multi-word value from a structure
1165 in a register or aligned memory can be done with just a SUBREG.
1166 A subword value in the least significant part of a register
1167 can also be extracted with a SUBREG. For this, we need the
1168 byte offset of the value in op0. */
1170 byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1172 /* If OP0 is a register, BITPOS must count within a word.
1173 But as we have it, it counts within whatever size OP0 now has.
1174 On a bigendian machine, these are not the same, so convert. */
1175 if (BYTES_BIG_ENDIAN
1176 && GET_CODE (op0) != MEM
1177 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1178 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1180 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1181 If that's wrong, the solution is to test for it and set TARGET to 0
1184 /* Only scalar integer modes can be converted via subregs. There is an
1185 additional problem for FP modes here in that they can have a precision
1186 which is different from the size. mode_for_size uses precision, but
1187 we want a mode based on the size, so we must avoid calling it for FP
1189 mode1 = (SCALAR_INT_MODE_P (tmode)
1190 ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0)
1193 if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1194 && bitpos % BITS_PER_WORD == 0)
1195 || (mode1 != BLKmode
1196 /* ??? The big endian test here is wrong. This is correct
1197 if the value is in a register, and if mode_for_size is not
1198 the same mode as op0. This causes us to get unnecessarily
1199 inefficient code from the Thumb port when -mbig-endian. */
1200 && (BYTES_BIG_ENDIAN
1201 ? bitpos + bitsize == BITS_PER_WORD
1203 && ((GET_CODE (op0) != MEM
1204 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1205 GET_MODE_BITSIZE (GET_MODE (op0)))
1206 && GET_MODE_SIZE (mode1) != 0
1207 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1208 || (GET_CODE (op0) == MEM
1209 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1210 || (offset * BITS_PER_UNIT % bitsize == 0
1211 && MEM_ALIGN (op0) % bitsize == 0)))))
1213 if (mode1 != GET_MODE (op0))
1215 if (GET_CODE (op0) == SUBREG)
1217 if (GET_MODE (SUBREG_REG (op0)) == mode1
1218 || GET_MODE_CLASS (mode1) == MODE_INT
1219 || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1220 op0 = SUBREG_REG (op0);
1222 /* Else we've got some float mode source being extracted into
1223 a different float mode destination -- this combination of
1224 subregs results in Severe Tire Damage. */
1225 goto no_subreg_mode_swap;
1227 if (GET_CODE (op0) == REG)
1228 op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1230 op0 = adjust_address (op0, mode1, offset);
1233 return convert_to_mode (tmode, op0, unsignedp);
1236 no_subreg_mode_swap:
1238 /* Handle fields bigger than a word. */
1240 if (bitsize > BITS_PER_WORD)
1242 /* Here we transfer the words of the field
1243 in the order least significant first.
1244 This is because the most significant word is the one which may
1245 be less than full. */
1247 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1250 if (target == 0 || GET_CODE (target) != REG)
1251 target = gen_reg_rtx (mode);
1253 /* Indicate for flow that the entire target reg is being set. */
1254 emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1256 for (i = 0; i < nwords; i++)
1258 /* If I is 0, use the low-order word in both field and target;
1259 if I is 1, use the next to lowest word; and so on. */
1260 /* Word number in TARGET to use. */
1261 unsigned int wordnum
1263 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1265 /* Offset from start of field in OP0. */
1266 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1267 ? MAX (0, ((int) bitsize - ((int) i + 1)
1268 * (int) BITS_PER_WORD))
1269 : (int) i * BITS_PER_WORD);
1270 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1272 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1273 bitsize - i * BITS_PER_WORD),
1274 bitnum + bit_offset, 1, target_part, mode,
1275 word_mode, total_size);
1277 if (target_part == 0)
1280 if (result_part != target_part)
1281 emit_move_insn (target_part, result_part);
1286 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1287 need to be zero'd out. */
1288 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1290 unsigned int i, total_words;
1292 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1293 for (i = nwords; i < total_words; i++)
1295 (operand_subword (target,
1296 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1303 /* Signed bit field: sign-extend with two arithmetic shifts. */
1304 target = expand_shift (LSHIFT_EXPR, mode, target,
1305 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1307 return expand_shift (RSHIFT_EXPR, mode, target,
1308 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1312 /* From here on we know the desired field is smaller than a word. */
1314 /* Check if there is a correspondingly-sized integer field, so we can
1315 safely extract it as one size of integer, if necessary; then
1316 truncate or extend to the size that is wanted; then use SUBREGs or
1317 convert_to_mode to get one of the modes we really wanted. */
1319 int_mode = int_mode_for_mode (tmode);
1320 if (int_mode == BLKmode)
1321 int_mode = int_mode_for_mode (mode);
1322 if (int_mode == BLKmode)
1323 abort (); /* Should probably push op0 out to memory and then
1326 /* OFFSET is the number of words or bytes (UNIT says which)
1327 from STR_RTX to the first word or byte containing part of the field. */
1329 if (GET_CODE (op0) != MEM)
1332 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1334 if (GET_CODE (op0) != REG)
1335 op0 = copy_to_reg (op0);
1336 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1337 op0, (offset * UNITS_PER_WORD));
1342 op0 = protect_from_queue (str_rtx, 1);
1344 /* Now OFFSET is nonzero only for memory operands. */
1349 && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1350 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1351 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1353 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1354 rtx bitsize_rtx, bitpos_rtx;
1355 rtx last = get_last_insn ();
1357 rtx xtarget = target;
1358 rtx xspec_target = spec_target;
1359 rtx xspec_target_subreg = spec_target_subreg;
1361 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1363 if (GET_CODE (xop0) == MEM)
1365 int save_volatile_ok = volatile_ok;
1368 /* Is the memory operand acceptable? */
1369 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1370 (xop0, GET_MODE (xop0))))
1372 /* No, load into a reg and extract from there. */
1373 enum machine_mode bestmode;
1375 /* Get the mode to use for inserting into this field. If
1376 OP0 is BLKmode, get the smallest mode consistent with the
1377 alignment. If OP0 is a non-BLKmode object that is no
1378 wider than MAXMODE, use its mode. Otherwise, use the
1379 smallest mode containing the field. */
1381 if (GET_MODE (xop0) == BLKmode
1382 || (GET_MODE_SIZE (GET_MODE (op0))
1383 > GET_MODE_SIZE (maxmode)))
1384 bestmode = get_best_mode (bitsize, bitnum,
1385 MEM_ALIGN (xop0), maxmode,
1386 MEM_VOLATILE_P (xop0));
1388 bestmode = GET_MODE (xop0);
1390 if (bestmode == VOIDmode
1391 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1392 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1395 /* Compute offset as multiple of this unit,
1396 counting in bytes. */
1397 unit = GET_MODE_BITSIZE (bestmode);
1398 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1399 xbitpos = bitnum % unit;
1400 xop0 = adjust_address (xop0, bestmode, xoffset);
1402 /* Fetch it to a register in that size. */
1403 xop0 = force_reg (bestmode, xop0);
1405 /* XBITPOS counts within UNIT, which is what is expected. */
1408 /* Get ref to first byte containing part of the field. */
1409 xop0 = adjust_address (xop0, byte_mode, xoffset);
1411 volatile_ok = save_volatile_ok;
1414 /* If op0 is a register, we need it in MAXMODE (which is usually
1415 SImode). to make it acceptable to the format of extzv. */
1416 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1418 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1419 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1421 /* On big-endian machines, we count bits from the most significant.
1422 If the bit field insn does not, we must invert. */
1423 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1424 xbitpos = unit - bitsize - xbitpos;
1426 /* Now convert from counting within UNIT to counting in MAXMODE. */
1427 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1428 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1430 unit = GET_MODE_BITSIZE (maxmode);
1433 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1434 xtarget = xspec_target = gen_reg_rtx (tmode);
1436 if (GET_MODE (xtarget) != maxmode)
1438 if (GET_CODE (xtarget) == REG)
1440 int wider = (GET_MODE_SIZE (maxmode)
1441 > GET_MODE_SIZE (GET_MODE (xtarget)));
1442 xtarget = gen_lowpart (maxmode, xtarget);
1444 xspec_target_subreg = xtarget;
1447 xtarget = gen_reg_rtx (maxmode);
1450 /* If this machine's extzv insists on a register target,
1451 make sure we have one. */
1452 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1453 (xtarget, maxmode)))
1454 xtarget = gen_reg_rtx (maxmode);
1456 bitsize_rtx = GEN_INT (bitsize);
1457 bitpos_rtx = GEN_INT (xbitpos);
1459 pat = gen_extzv (protect_from_queue (xtarget, 1),
1460 xop0, bitsize_rtx, bitpos_rtx);
1465 spec_target = xspec_target;
1466 spec_target_subreg = xspec_target_subreg;
1470 delete_insns_since (last);
1471 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1477 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1483 && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1484 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1485 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1487 int xbitpos = bitpos, xoffset = offset;
1488 rtx bitsize_rtx, bitpos_rtx;
1489 rtx last = get_last_insn ();
1490 rtx xop0 = op0, xtarget = target;
1491 rtx xspec_target = spec_target;
1492 rtx xspec_target_subreg = spec_target_subreg;
1494 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1496 if (GET_CODE (xop0) == MEM)
1498 /* Is the memory operand acceptable? */
1499 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1500 (xop0, GET_MODE (xop0))))
1502 /* No, load into a reg and extract from there. */
1503 enum machine_mode bestmode;
1505 /* Get the mode to use for inserting into this field. If
1506 OP0 is BLKmode, get the smallest mode consistent with the
1507 alignment. If OP0 is a non-BLKmode object that is no
1508 wider than MAXMODE, use its mode. Otherwise, use the
1509 smallest mode containing the field. */
1511 if (GET_MODE (xop0) == BLKmode
1512 || (GET_MODE_SIZE (GET_MODE (op0))
1513 > GET_MODE_SIZE (maxmode)))
1514 bestmode = get_best_mode (bitsize, bitnum,
1515 MEM_ALIGN (xop0), maxmode,
1516 MEM_VOLATILE_P (xop0));
1518 bestmode = GET_MODE (xop0);
1520 if (bestmode == VOIDmode
1521 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1522 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1525 /* Compute offset as multiple of this unit,
1526 counting in bytes. */
1527 unit = GET_MODE_BITSIZE (bestmode);
1528 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1529 xbitpos = bitnum % unit;
1530 xop0 = adjust_address (xop0, bestmode, xoffset);
1532 /* Fetch it to a register in that size. */
1533 xop0 = force_reg (bestmode, xop0);
1535 /* XBITPOS counts within UNIT, which is what is expected. */
1538 /* Get ref to first byte containing part of the field. */
1539 xop0 = adjust_address (xop0, byte_mode, xoffset);
1542 /* If op0 is a register, we need it in MAXMODE (which is usually
1543 SImode) to make it acceptable to the format of extv. */
1544 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1546 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1547 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1549 /* On big-endian machines, we count bits from the most significant.
1550 If the bit field insn does not, we must invert. */
1551 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1552 xbitpos = unit - bitsize - xbitpos;
1554 /* XBITPOS counts within a size of UNIT.
1555 Adjust to count within a size of MAXMODE. */
1556 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1557 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1559 unit = GET_MODE_BITSIZE (maxmode);
1562 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1563 xtarget = xspec_target = gen_reg_rtx (tmode);
1565 if (GET_MODE (xtarget) != maxmode)
1567 if (GET_CODE (xtarget) == REG)
1569 int wider = (GET_MODE_SIZE (maxmode)
1570 > GET_MODE_SIZE (GET_MODE (xtarget)));
1571 xtarget = gen_lowpart (maxmode, xtarget);
1573 xspec_target_subreg = xtarget;
1576 xtarget = gen_reg_rtx (maxmode);
1579 /* If this machine's extv insists on a register target,
1580 make sure we have one. */
1581 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1582 (xtarget, maxmode)))
1583 xtarget = gen_reg_rtx (maxmode);
1585 bitsize_rtx = GEN_INT (bitsize);
1586 bitpos_rtx = GEN_INT (xbitpos);
1588 pat = gen_extv (protect_from_queue (xtarget, 1),
1589 xop0, bitsize_rtx, bitpos_rtx);
1594 spec_target = xspec_target;
1595 spec_target_subreg = xspec_target_subreg;
1599 delete_insns_since (last);
1600 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1606 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1609 if (target == spec_target)
1611 if (target == spec_target_subreg)
1613 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1615 /* If the target mode is floating-point, first convert to the
1616 integer mode of that size and then access it as a floating-point
1617 value via a SUBREG. */
1618 if (GET_MODE_CLASS (tmode) != MODE_INT
1619 && GET_MODE_CLASS (tmode) != MODE_PARTIAL_INT)
1621 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1624 return gen_lowpart (tmode, target);
1627 return convert_to_mode (tmode, target, unsignedp);
1632 /* Extract a bit field using shifts and boolean operations
1633 Returns an rtx to represent the value.
1634 OP0 addresses a register (word) or memory (byte).
1635 BITPOS says which bit within the word or byte the bit field starts in.
1636 OFFSET says how many bytes farther the bit field starts;
1637 it is 0 if OP0 is a register.
1638 BITSIZE says how many bits long the bit field is.
1639 (If OP0 is a register, it may be narrower than a full word,
1640 but BITPOS still counts within a full word,
1641 which is significant on bigendian machines.)
1643 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1644 If TARGET is nonzero, attempts to store the value there
1645 and return TARGET, but this is not guaranteed.
1646 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1649 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1650 unsigned HOST_WIDE_INT offset,
1651 unsigned HOST_WIDE_INT bitsize,
1652 unsigned HOST_WIDE_INT bitpos, rtx target,
1655 unsigned int total_bits = BITS_PER_WORD;
1656 enum machine_mode mode;
1658 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1660 /* Special treatment for a bit field split across two registers. */
1661 if (bitsize + bitpos > BITS_PER_WORD)
1662 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1666 /* Get the proper mode to use for this field. We want a mode that
1667 includes the entire field. If such a mode would be larger than
1668 a word, we won't be doing the extraction the normal way. */
1670 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1671 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1673 if (mode == VOIDmode)
1674 /* The only way this should occur is if the field spans word
1676 return extract_split_bit_field (op0, bitsize,
1677 bitpos + offset * BITS_PER_UNIT,
1680 total_bits = GET_MODE_BITSIZE (mode);
1682 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1683 be in the range 0 to total_bits-1, and put any excess bytes in
1685 if (bitpos >= total_bits)
1687 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1688 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1692 /* Get ref to an aligned byte, halfword, or word containing the field.
1693 Adjust BITPOS to be position within a word,
1694 and OFFSET to be the offset of that word.
1695 Then alter OP0 to refer to that word. */
1696 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1697 offset -= (offset % (total_bits / BITS_PER_UNIT));
1698 op0 = adjust_address (op0, mode, offset);
1701 mode = GET_MODE (op0);
1703 if (BYTES_BIG_ENDIAN)
1704 /* BITPOS is the distance between our msb and that of OP0.
1705 Convert it to the distance from the lsb. */
1706 bitpos = total_bits - bitsize - bitpos;
1708 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1709 We have reduced the big-endian case to the little-endian case. */
1715 /* If the field does not already start at the lsb,
1716 shift it so it does. */
1717 tree amount = build_int_2 (bitpos, 0);
1718 /* Maybe propagate the target for the shift. */
1719 /* But not if we will return it--could confuse integrate.c. */
1720 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1721 && !REG_FUNCTION_VALUE_P (target)
1723 if (tmode != mode) subtarget = 0;
1724 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1726 /* Convert the value to the desired mode. */
1728 op0 = convert_to_mode (tmode, op0, 1);
1730 /* Unless the msb of the field used to be the msb when we shifted,
1731 mask out the upper bits. */
1733 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1734 return expand_binop (GET_MODE (op0), and_optab, op0,
1735 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1736 target, 1, OPTAB_LIB_WIDEN);
1740 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1741 then arithmetic-shift its lsb to the lsb of the word. */
1742 op0 = force_reg (mode, op0);
1746 /* Find the narrowest integer mode that contains the field. */
1748 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1749 mode = GET_MODE_WIDER_MODE (mode))
1750 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1752 op0 = convert_to_mode (mode, op0, 0);
1756 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1759 = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1760 /* Maybe propagate the target for the shift. */
1761 /* But not if we will return the result--could confuse integrate.c. */
1762 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1763 && ! REG_FUNCTION_VALUE_P (target)
1765 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1768 return expand_shift (RSHIFT_EXPR, mode, op0,
1769 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1773 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1774 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1775 complement of that if COMPLEMENT. The mask is truncated if
1776 necessary to the width of mode MODE. The mask is zero-extended if
1777 BITSIZE+BITPOS is too small for MODE. */
1780 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1782 HOST_WIDE_INT masklow, maskhigh;
1786 else if (bitpos < HOST_BITS_PER_WIDE_INT)
1787 masklow = (HOST_WIDE_INT) -1 << bitpos;
1791 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1792 masklow &= ((unsigned HOST_WIDE_INT) -1
1793 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1795 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1798 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1802 else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1803 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1804 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1810 maskhigh = ~maskhigh;
1814 return immed_double_const (masklow, maskhigh, mode);
1817 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1818 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1821 lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize)
1823 unsigned HOST_WIDE_INT v = INTVAL (value);
1824 HOST_WIDE_INT low, high;
1826 if (bitsize < HOST_BITS_PER_WIDE_INT)
1827 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1829 if (bitpos < HOST_BITS_PER_WIDE_INT)
1832 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1837 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1840 return immed_double_const (low, high, mode);
1843 /* Extract a bit field that is split across two words
1844 and return an RTX for the result.
1846 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1847 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1848 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1851 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1852 unsigned HOST_WIDE_INT bitpos, int unsignedp)
1855 unsigned int bitsdone = 0;
1856 rtx result = NULL_RTX;
1859 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1861 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1862 unit = BITS_PER_WORD;
1864 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1866 while (bitsdone < bitsize)
1868 unsigned HOST_WIDE_INT thissize;
1870 unsigned HOST_WIDE_INT thispos;
1871 unsigned HOST_WIDE_INT offset;
1873 offset = (bitpos + bitsdone) / unit;
1874 thispos = (bitpos + bitsdone) % unit;
1876 /* THISSIZE must not overrun a word boundary. Otherwise,
1877 extract_fixed_bit_field will call us again, and we will mutually
1879 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1880 thissize = MIN (thissize, unit - thispos);
1882 /* If OP0 is a register, then handle OFFSET here.
1884 When handling multiword bitfields, extract_bit_field may pass
1885 down a word_mode SUBREG of a larger REG for a bitfield that actually
1886 crosses a word boundary. Thus, for a SUBREG, we must find
1887 the current word starting from the base register. */
1888 if (GET_CODE (op0) == SUBREG)
1890 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1891 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1892 GET_MODE (SUBREG_REG (op0)));
1895 else if (GET_CODE (op0) == REG)
1897 word = operand_subword_force (op0, offset, GET_MODE (op0));
1903 /* Extract the parts in bit-counting order,
1904 whose meaning is determined by BYTES_PER_UNIT.
1905 OFFSET is in UNITs, and UNIT is in bits.
1906 extract_fixed_bit_field wants offset in bytes. */
1907 part = extract_fixed_bit_field (word_mode, word,
1908 offset * unit / BITS_PER_UNIT,
1909 thissize, thispos, 0, 1);
1910 bitsdone += thissize;
1912 /* Shift this part into place for the result. */
1913 if (BYTES_BIG_ENDIAN)
1915 if (bitsize != bitsdone)
1916 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1917 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1921 if (bitsdone != thissize)
1922 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1923 build_int_2 (bitsdone - thissize, 0), 0, 1);
1929 /* Combine the parts with bitwise or. This works
1930 because we extracted each part as an unsigned bit field. */
1931 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1937 /* Unsigned bit field: we are done. */
1940 /* Signed bit field: sign-extend with two arithmetic shifts. */
1941 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1942 build_int_2 (BITS_PER_WORD - bitsize, 0),
1944 return expand_shift (RSHIFT_EXPR, word_mode, result,
1945 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1948 /* Add INC into TARGET. */
1951 expand_inc (rtx target, rtx inc)
1953 rtx value = expand_binop (GET_MODE (target), add_optab,
1955 target, 0, OPTAB_LIB_WIDEN);
1956 if (value != target)
1957 emit_move_insn (target, value);
1960 /* Subtract DEC from TARGET. */
1963 expand_dec (rtx target, rtx dec)
1965 rtx value = expand_binop (GET_MODE (target), sub_optab,
1967 target, 0, OPTAB_LIB_WIDEN);
1968 if (value != target)
1969 emit_move_insn (target, value);
1972 /* Output a shift instruction for expression code CODE,
1973 with SHIFTED being the rtx for the value to shift,
1974 and AMOUNT the tree for the amount to shift by.
1975 Store the result in the rtx TARGET, if that is convenient.
1976 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1977 Return the rtx for where the value is. */
1980 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
1981 tree amount, rtx target, int unsignedp)
1984 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1985 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1988 /* Previously detected shift-counts computed by NEGATE_EXPR
1989 and shifted in the other direction; but that does not work
1992 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1994 #ifdef SHIFT_COUNT_TRUNCATED
1995 if (SHIFT_COUNT_TRUNCATED)
1997 if (GET_CODE (op1) == CONST_INT
1998 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
1999 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
2000 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2001 % GET_MODE_BITSIZE (mode));
2002 else if (GET_CODE (op1) == SUBREG
2003 && subreg_lowpart_p (op1))
2004 op1 = SUBREG_REG (op1);
2008 if (op1 == const0_rtx)
2011 for (try = 0; temp == 0 && try < 3; try++)
2013 enum optab_methods methods;
2016 methods = OPTAB_DIRECT;
2018 methods = OPTAB_WIDEN;
2020 methods = OPTAB_LIB_WIDEN;
2024 /* Widening does not work for rotation. */
2025 if (methods == OPTAB_WIDEN)
2027 else if (methods == OPTAB_LIB_WIDEN)
2029 /* If we have been unable to open-code this by a rotation,
2030 do it as the IOR of two shifts. I.e., to rotate A
2031 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
2032 where C is the bitsize of A.
2034 It is theoretically possible that the target machine might
2035 not be able to perform either shift and hence we would
2036 be making two libcalls rather than just the one for the
2037 shift (similarly if IOR could not be done). We will allow
2038 this extremely unlikely lossage to avoid complicating the
2041 rtx subtarget = target == shifted ? 0 : target;
2043 tree type = TREE_TYPE (amount);
2044 tree new_amount = make_tree (type, op1);
2046 = fold (build (MINUS_EXPR, type,
2048 build_int_2 (GET_MODE_BITSIZE (mode),
2052 shifted = force_reg (mode, shifted);
2054 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2055 mode, shifted, new_amount, subtarget, 1);
2056 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2057 mode, shifted, other_amount, 0, 1);
2058 return expand_binop (mode, ior_optab, temp, temp1, target,
2059 unsignedp, methods);
2062 temp = expand_binop (mode,
2063 left ? rotl_optab : rotr_optab,
2064 shifted, op1, target, unsignedp, methods);
2066 /* If we don't have the rotate, but we are rotating by a constant
2067 that is in range, try a rotate in the opposite direction. */
2069 if (temp == 0 && GET_CODE (op1) == CONST_INT
2071 && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
2072 temp = expand_binop (mode,
2073 left ? rotr_optab : rotl_optab,
2075 GEN_INT (GET_MODE_BITSIZE (mode)
2077 target, unsignedp, methods);
2080 temp = expand_binop (mode,
2081 left ? ashl_optab : lshr_optab,
2082 shifted, op1, target, unsignedp, methods);
2084 /* Do arithmetic shifts.
2085 Also, if we are going to widen the operand, we can just as well
2086 use an arithmetic right-shift instead of a logical one. */
2087 if (temp == 0 && ! rotate
2088 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2090 enum optab_methods methods1 = methods;
2092 /* If trying to widen a log shift to an arithmetic shift,
2093 don't accept an arithmetic shift of the same size. */
2095 methods1 = OPTAB_MUST_WIDEN;
2097 /* Arithmetic shift */
2099 temp = expand_binop (mode,
2100 left ? ashl_optab : ashr_optab,
2101 shifted, op1, target, unsignedp, methods1);
2104 /* We used to try extzv here for logical right shifts, but that was
2105 only useful for one machine, the VAX, and caused poor code
2106 generation there for lshrdi3, so the code was deleted and a
2107 define_expand for lshrsi3 was added to vax.md. */
2115 enum alg_code { alg_zero, alg_m, alg_shift,
2116 alg_add_t_m2, alg_sub_t_m2,
2117 alg_add_factor, alg_sub_factor,
2118 alg_add_t2_m, alg_sub_t2_m,
2119 alg_add, alg_subtract, alg_factor, alg_shiftop };
2121 /* This structure records a sequence of operations.
2122 `ops' is the number of operations recorded.
2123 `cost' is their total cost.
2124 The operations are stored in `op' and the corresponding
2125 logarithms of the integer coefficients in `log'.
2127 These are the operations:
2128 alg_zero total := 0;
2129 alg_m total := multiplicand;
2130 alg_shift total := total * coeff
2131 alg_add_t_m2 total := total + multiplicand * coeff;
2132 alg_sub_t_m2 total := total - multiplicand * coeff;
2133 alg_add_factor total := total * coeff + total;
2134 alg_sub_factor total := total * coeff - total;
2135 alg_add_t2_m total := total * coeff + multiplicand;
2136 alg_sub_t2_m total := total * coeff - multiplicand;
2138 The first operand must be either alg_zero or alg_m. */
2144 /* The size of the OP and LOG fields are not directly related to the
2145 word size, but the worst-case algorithms will be if we have few
2146 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2147 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2148 in total wordsize operations. */
2149 enum alg_code op[MAX_BITS_PER_WORD];
2150 char log[MAX_BITS_PER_WORD];
2153 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT, int);
2154 static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int,
2155 int, unsigned HOST_WIDE_INT *,
2157 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2158 /* Compute and return the best algorithm for multiplying by T.
2159 The algorithm must cost less than cost_limit
2160 If retval.cost >= COST_LIMIT, no algorithm was found and all
2161 other field of the returned struct are undefined. */
2164 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2168 struct algorithm *alg_in, *best_alg;
2170 unsigned HOST_WIDE_INT q;
2172 /* Indicate that no algorithm is yet found. If no algorithm
2173 is found, this value will be returned and indicate failure. */
2174 alg_out->cost = cost_limit;
2176 if (cost_limit <= 0)
2179 /* t == 1 can be done in zero cost. */
2184 alg_out->op[0] = alg_m;
2188 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2192 if (zero_cost >= cost_limit)
2197 alg_out->cost = zero_cost;
2198 alg_out->op[0] = alg_zero;
2203 /* We'll be needing a couple extra algorithm structures now. */
2205 alg_in = alloca (sizeof (struct algorithm));
2206 best_alg = alloca (sizeof (struct algorithm));
2208 /* If we have a group of zero bits at the low-order part of T, try
2209 multiplying by the remaining bits and then doing a shift. */
2213 m = floor_log2 (t & -t); /* m = number of low zero bits */
2214 if (m < BITS_PER_WORD)
2217 cost = shift_cost[m];
2218 synth_mult (alg_in, q, cost_limit - cost);
2220 cost += alg_in->cost;
2221 if (cost < cost_limit)
2223 struct algorithm *x;
2224 x = alg_in, alg_in = best_alg, best_alg = x;
2225 best_alg->log[best_alg->ops] = m;
2226 best_alg->op[best_alg->ops] = alg_shift;
2232 /* If we have an odd number, add or subtract one. */
2235 unsigned HOST_WIDE_INT w;
2237 for (w = 1; (w & t) != 0; w <<= 1)
2239 /* If T was -1, then W will be zero after the loop. This is another
2240 case where T ends with ...111. Handling this with (T + 1) and
2241 subtract 1 produces slightly better code and results in algorithm
2242 selection much faster than treating it like the ...0111 case
2246 /* Reject the case where t is 3.
2247 Thus we prefer addition in that case. */
2250 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2253 synth_mult (alg_in, t + 1, cost_limit - cost);
2255 cost += alg_in->cost;
2256 if (cost < cost_limit)
2258 struct algorithm *x;
2259 x = alg_in, alg_in = best_alg, best_alg = x;
2260 best_alg->log[best_alg->ops] = 0;
2261 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2267 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2270 synth_mult (alg_in, t - 1, cost_limit - cost);
2272 cost += alg_in->cost;
2273 if (cost < cost_limit)
2275 struct algorithm *x;
2276 x = alg_in, alg_in = best_alg, best_alg = x;
2277 best_alg->log[best_alg->ops] = 0;
2278 best_alg->op[best_alg->ops] = alg_add_t_m2;
2284 /* Look for factors of t of the form
2285 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2286 If we find such a factor, we can multiply by t using an algorithm that
2287 multiplies by q, shift the result by m and add/subtract it to itself.
2289 We search for large factors first and loop down, even if large factors
2290 are less probable than small; if we find a large factor we will find a
2291 good sequence quickly, and therefore be able to prune (by decreasing
2292 COST_LIMIT) the search. */
2294 for (m = floor_log2 (t - 1); m >= 2; m--)
2296 unsigned HOST_WIDE_INT d;
2298 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2299 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2301 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2302 synth_mult (alg_in, t / d, cost_limit - cost);
2304 cost += alg_in->cost;
2305 if (cost < cost_limit)
2307 struct algorithm *x;
2308 x = alg_in, alg_in = best_alg, best_alg = x;
2309 best_alg->log[best_alg->ops] = m;
2310 best_alg->op[best_alg->ops] = alg_add_factor;
2313 /* Other factors will have been taken care of in the recursion. */
2317 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2318 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2320 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2321 synth_mult (alg_in, t / d, cost_limit - cost);
2323 cost += alg_in->cost;
2324 if (cost < cost_limit)
2326 struct algorithm *x;
2327 x = alg_in, alg_in = best_alg, best_alg = x;
2328 best_alg->log[best_alg->ops] = m;
2329 best_alg->op[best_alg->ops] = alg_sub_factor;
2336 /* Try shift-and-add (load effective address) instructions,
2337 i.e. do a*3, a*5, a*9. */
2343 if (m >= 0 && m < BITS_PER_WORD)
2345 cost = shiftadd_cost[m];
2346 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2348 cost += alg_in->cost;
2349 if (cost < cost_limit)
2351 struct algorithm *x;
2352 x = alg_in, alg_in = best_alg, best_alg = x;
2353 best_alg->log[best_alg->ops] = m;
2354 best_alg->op[best_alg->ops] = alg_add_t2_m;
2362 if (m >= 0 && m < BITS_PER_WORD)
2364 cost = shiftsub_cost[m];
2365 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2367 cost += alg_in->cost;
2368 if (cost < cost_limit)
2370 struct algorithm *x;
2371 x = alg_in, alg_in = best_alg, best_alg = x;
2372 best_alg->log[best_alg->ops] = m;
2373 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2379 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2380 we have not found any algorithm. */
2381 if (cost_limit == alg_out->cost)
2384 /* If we are getting a too long sequence for `struct algorithm'
2385 to record, make this search fail. */
2386 if (best_alg->ops == MAX_BITS_PER_WORD)
2389 /* Copy the algorithm from temporary space to the space at alg_out.
2390 We avoid using structure assignment because the majority of
2391 best_alg is normally undefined, and this is a critical function. */
2392 alg_out->ops = best_alg->ops + 1;
2393 alg_out->cost = cost_limit;
2394 memcpy (alg_out->op, best_alg->op,
2395 alg_out->ops * sizeof *alg_out->op);
2396 memcpy (alg_out->log, best_alg->log,
2397 alg_out->ops * sizeof *alg_out->log);
2400 /* Perform a multiplication and return an rtx for the result.
2401 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2402 TARGET is a suggestion for where to store the result (an rtx).
2404 We check specially for a constant integer as OP1.
2405 If you want this check for OP0 as well, then before calling
2406 you should swap the two operands if OP0 would be constant. */
2409 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
2412 rtx const_op1 = op1;
2414 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2415 less than or equal in size to `unsigned int' this doesn't matter.
2416 If the mode is larger than `unsigned int', then synth_mult works only
2417 if the constant value exactly fits in an `unsigned int' without any
2418 truncation. This means that multiplying by negative values does
2419 not work; results are off by 2^32 on a 32 bit machine. */
2421 /* If we are multiplying in DImode, it may still be a win
2422 to try to work with shifts and adds. */
2423 if (GET_CODE (op1) == CONST_DOUBLE
2424 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2425 && HOST_BITS_PER_INT >= BITS_PER_WORD
2426 && CONST_DOUBLE_HIGH (op1) == 0)
2427 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2428 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2429 && GET_CODE (op1) == CONST_INT
2430 && INTVAL (op1) < 0)
2433 /* We used to test optimize here, on the grounds that it's better to
2434 produce a smaller program when -O is not used.
2435 But this causes such a terrible slowdown sometimes
2436 that it seems better to use synth_mult always. */
2438 if (const_op1 && GET_CODE (const_op1) == CONST_INT
2439 && (unsignedp || ! flag_trapv))
2441 struct algorithm alg;
2442 struct algorithm alg2;
2443 HOST_WIDE_INT val = INTVAL (op1);
2444 HOST_WIDE_INT val_so_far;
2447 enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2449 /* op0 must be register to make mult_cost match the precomputed
2450 shiftadd_cost array. */
2451 op0 = force_reg (mode, op0);
2453 /* Try to do the computation three ways: multiply by the negative of OP1
2454 and then negate, do the multiplication directly, or do multiplication
2457 mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2458 mult_cost = MIN (12 * add_cost, mult_cost);
2460 synth_mult (&alg, val, mult_cost);
2462 /* This works only if the inverted value actually fits in an
2464 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2466 synth_mult (&alg2, - val,
2467 (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2468 if (alg2.cost + negate_cost < alg.cost)
2469 alg = alg2, variant = negate_variant;
2472 /* This proves very useful for division-by-constant. */
2473 synth_mult (&alg2, val - 1,
2474 (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2475 if (alg2.cost + add_cost < alg.cost)
2476 alg = alg2, variant = add_variant;
2478 if (alg.cost < mult_cost)
2480 /* We found something cheaper than a multiply insn. */
2483 enum machine_mode nmode;
2485 op0 = protect_from_queue (op0, 0);
2487 /* Avoid referencing memory over and over.
2488 For speed, but also for correctness when mem is volatile. */
2489 if (GET_CODE (op0) == MEM)
2490 op0 = force_reg (mode, op0);
2492 /* ACCUM starts out either as OP0 or as a zero, depending on
2493 the first operation. */
2495 if (alg.op[0] == alg_zero)
2497 accum = copy_to_mode_reg (mode, const0_rtx);
2500 else if (alg.op[0] == alg_m)
2502 accum = copy_to_mode_reg (mode, op0);
2508 for (opno = 1; opno < alg.ops; opno++)
2510 int log = alg.log[opno];
2511 int preserve = preserve_subexpressions_p ();
2512 rtx shift_subtarget = preserve ? 0 : accum;
2514 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2517 rtx accum_target = preserve ? 0 : accum;
2519 switch (alg.op[opno])
2522 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2523 build_int_2 (log, 0), NULL_RTX, 0);
2528 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2529 build_int_2 (log, 0), NULL_RTX, 0);
2530 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2532 ? add_target : accum_target);
2533 val_so_far += (HOST_WIDE_INT) 1 << log;
2537 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2538 build_int_2 (log, 0), NULL_RTX, 0);
2539 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2541 ? add_target : accum_target);
2542 val_so_far -= (HOST_WIDE_INT) 1 << log;
2546 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2547 build_int_2 (log, 0), shift_subtarget,
2549 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2551 ? add_target : accum_target);
2552 val_so_far = (val_so_far << log) + 1;
2556 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2557 build_int_2 (log, 0), shift_subtarget,
2559 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2561 ? add_target : accum_target);
2562 val_so_far = (val_so_far << log) - 1;
2565 case alg_add_factor:
2566 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2567 build_int_2 (log, 0), NULL_RTX, 0);
2568 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2570 ? add_target : accum_target);
2571 val_so_far += val_so_far << log;
2574 case alg_sub_factor:
2575 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2576 build_int_2 (log, 0), NULL_RTX, 0);
2577 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2578 (add_target ? add_target
2579 : preserve ? 0 : tem));
2580 val_so_far = (val_so_far << log) - val_so_far;
2587 /* Write a REG_EQUAL note on the last insn so that we can cse
2588 multiplication sequences. Note that if ACCUM is a SUBREG,
2589 we've set the inner register and must properly indicate
2592 tem = op0, nmode = mode;
2593 if (GET_CODE (accum) == SUBREG)
2595 nmode = GET_MODE (SUBREG_REG (accum));
2596 tem = gen_lowpart (nmode, op0);
2599 insn = get_last_insn ();
2600 set_unique_reg_note (insn,
2602 gen_rtx_MULT (nmode, tem,
2603 GEN_INT (val_so_far)));
2606 if (variant == negate_variant)
2608 val_so_far = - val_so_far;
2609 accum = expand_unop (mode, neg_optab, accum, target, 0);
2611 else if (variant == add_variant)
2613 val_so_far = val_so_far + 1;
2614 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2617 if (val != val_so_far)
2624 if (GET_CODE (op0) == CONST_DOUBLE)
2631 /* Expand x*2.0 as x+x. */
2632 if (GET_CODE (op1) == CONST_DOUBLE
2633 && GET_MODE_CLASS (mode) == MODE_FLOAT)
2636 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
2638 if (REAL_VALUES_EQUAL (d, dconst2))
2640 op0 = force_reg (GET_MODE (op0), op0);
2641 return expand_binop (mode, add_optab, op0, op0,
2642 target, unsignedp, OPTAB_LIB_WIDEN);
2646 /* This used to use umul_optab if unsigned, but for non-widening multiply
2647 there is no difference between signed and unsigned. */
2648 op0 = expand_binop (mode,
2650 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2651 ? smulv_optab : smul_optab,
2652 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2658 /* Return the smallest n such that 2**n >= X. */
2661 ceil_log2 (unsigned HOST_WIDE_INT x)
2663 return floor_log2 (x - 1) + 1;
2666 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2667 replace division by D, and put the least significant N bits of the result
2668 in *MULTIPLIER_PTR and return the most significant bit.
2670 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2671 needed precision is in PRECISION (should be <= N).
2673 PRECISION should be as small as possible so this function can choose
2674 multiplier more freely.
2676 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2677 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2679 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2680 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2683 unsigned HOST_WIDE_INT
2684 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
2685 unsigned HOST_WIDE_INT *multiplier_ptr,
2686 int *post_shift_ptr, int *lgup_ptr)
2688 HOST_WIDE_INT mhigh_hi, mlow_hi;
2689 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2690 int lgup, post_shift;
2692 unsigned HOST_WIDE_INT nl, dummy1;
2693 HOST_WIDE_INT nh, dummy2;
2695 /* lgup = ceil(log2(divisor)); */
2696 lgup = ceil_log2 (d);
2702 pow2 = n + lgup - precision;
2704 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2706 /* We could handle this with some effort, but this case is much better
2707 handled directly with a scc insn, so rely on caller using that. */
2711 /* mlow = 2^(N + lgup)/d */
2712 if (pow >= HOST_BITS_PER_WIDE_INT)
2714 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2720 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2722 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2723 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2725 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2726 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2727 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2729 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2730 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2731 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2733 if (mhigh_hi && nh - d >= d)
2735 if (mhigh_hi > 1 || mlow_hi > 1)
2737 /* Assert that mlow < mhigh. */
2738 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2741 /* If precision == N, then mlow, mhigh exceed 2^N
2742 (but they do not exceed 2^(N+1)). */
2744 /* Reduce to lowest terms. */
2745 for (post_shift = lgup; post_shift > 0; post_shift--)
2747 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2748 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2758 *post_shift_ptr = post_shift;
2760 if (n < HOST_BITS_PER_WIDE_INT)
2762 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2763 *multiplier_ptr = mhigh_lo & mask;
2764 return mhigh_lo >= mask;
2768 *multiplier_ptr = mhigh_lo;
2773 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2774 congruent to 1 (mod 2**N). */
2776 static unsigned HOST_WIDE_INT
2777 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
2779 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2781 /* The algorithm notes that the choice y = x satisfies
2782 x*y == 1 mod 2^3, since x is assumed odd.
2783 Each iteration doubles the number of bits of significance in y. */
2785 unsigned HOST_WIDE_INT mask;
2786 unsigned HOST_WIDE_INT y = x;
2789 mask = (n == HOST_BITS_PER_WIDE_INT
2790 ? ~(unsigned HOST_WIDE_INT) 0
2791 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2795 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2801 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2802 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2803 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2804 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2807 The result is put in TARGET if that is convenient.
2809 MODE is the mode of operation. */
2812 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
2813 rtx op1, rtx target, int unsignedp)
2816 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2818 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2819 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2821 tem = expand_and (mode, tem, op1, NULL_RTX);
2823 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2826 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2827 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2829 tem = expand_and (mode, tem, op0, NULL_RTX);
2830 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2836 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2837 in TARGET if that is convenient, and return where the result is. If the
2838 operation can not be performed, 0 is returned.
2840 MODE is the mode of operation and result.
2842 UNSIGNEDP nonzero means unsigned multiply.
2844 MAX_COST is the total allowed cost for the expanded RTL. */
2847 expand_mult_highpart (enum machine_mode mode, rtx op0,
2848 unsigned HOST_WIDE_INT cnst1, rtx target,
2849 int unsignedp, int max_cost)
2851 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2852 optab mul_highpart_optab;
2855 int size = GET_MODE_BITSIZE (mode);
2858 /* We can't support modes wider than HOST_BITS_PER_INT. */
2859 if (size > HOST_BITS_PER_WIDE_INT)
2862 op1 = gen_int_mode (cnst1, mode);
2865 = immed_double_const (cnst1,
2868 : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2871 /* expand_mult handles constant multiplication of word_mode
2872 or narrower. It does a poor job for large modes. */
2873 if (size < BITS_PER_WORD
2874 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2876 /* We have to do this, since expand_binop doesn't do conversion for
2877 multiply. Maybe change expand_binop to handle widening multiply? */
2878 op0 = convert_to_mode (wider_mode, op0, unsignedp);
2880 /* We know that this can't have signed overflow, so pretend this is
2881 an unsigned multiply. */
2882 tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, 0);
2883 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2884 build_int_2 (size, 0), NULL_RTX, 1);
2885 return convert_modes (mode, wider_mode, tem, unsignedp);
2889 target = gen_reg_rtx (mode);
2891 /* Firstly, try using a multiplication insn that only generates the needed
2892 high part of the product, and in the sign flavor of unsignedp. */
2893 if (mul_highpart_cost[(int) mode] < max_cost)
2895 mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2896 target = expand_binop (mode, mul_highpart_optab,
2897 op0, op1, target, unsignedp, OPTAB_DIRECT);
2902 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2903 Need to adjust the result after the multiplication. */
2904 if (size - 1 < BITS_PER_WORD
2905 && (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost
2908 mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2909 target = expand_binop (mode, mul_highpart_optab,
2910 op0, op1, target, unsignedp, OPTAB_DIRECT);
2912 /* We used the wrong signedness. Adjust the result. */
2913 return expand_mult_highpart_adjust (mode, target, op0,
2914 op1, target, unsignedp);
2917 /* Try widening multiplication. */
2918 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2919 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2920 && mul_widen_cost[(int) wider_mode] < max_cost)
2922 op1 = force_reg (mode, op1);
2926 /* Try widening the mode and perform a non-widening multiplication. */
2927 moptab = smul_optab;
2928 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2929 && size - 1 < BITS_PER_WORD
2930 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2936 /* Try widening multiplication of opposite signedness, and adjust. */
2937 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2938 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2939 && size - 1 < BITS_PER_WORD
2940 && (mul_widen_cost[(int) wider_mode]
2941 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2943 rtx regop1 = force_reg (mode, op1);
2944 tem = expand_binop (wider_mode, moptab, op0, regop1,
2945 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2948 /* Extract the high half of the just generated product. */
2949 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2950 build_int_2 (size, 0), NULL_RTX, 1);
2951 tem = convert_modes (mode, wider_mode, tem, unsignedp);
2952 /* We used the wrong signedness. Adjust the result. */
2953 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2961 /* Pass NULL_RTX as target since TARGET has wrong mode. */
2962 tem = expand_binop (wider_mode, moptab, op0, op1,
2963 NULL_RTX, unsignedp, OPTAB_WIDEN);
2967 /* Extract the high half of the just generated product. */
2968 if (mode == word_mode)
2970 return gen_highpart (mode, tem);
2974 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2975 build_int_2 (size, 0), NULL_RTX, 1);
2976 return convert_modes (mode, wider_mode, tem, unsignedp);
2980 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2981 if that is convenient, and returning where the result is.
2982 You may request either the quotient or the remainder as the result;
2983 specify REM_FLAG nonzero to get the remainder.
2985 CODE is the expression code for which kind of division this is;
2986 it controls how rounding is done. MODE is the machine mode to use.
2987 UNSIGNEDP nonzero means do unsigned division. */
2989 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2990 and then correct it by or'ing in missing high bits
2991 if result of ANDI is nonzero.
2992 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2993 This could optimize to a bfexts instruction.
2994 But C doesn't use these operations, so their optimizations are
2996 /* ??? For modulo, we don't actually need the highpart of the first product,
2997 the low part will do nicely. And for small divisors, the second multiply
2998 can also be a low-part only multiply or even be completely left out.
2999 E.g. to calculate the remainder of a division by 3 with a 32 bit
3000 multiply, multiply with 0x55555556 and extract the upper two bits;
3001 the result is exact for inputs up to 0x1fffffff.
3002 The input range can be reduced by using cross-sum rules.
3003 For odd divisors >= 3, the following table gives right shift counts
3004 so that if a number is shifted by an integer multiple of the given
3005 amount, the remainder stays the same:
3006 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3007 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3008 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3009 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3010 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3012 Cross-sum rules for even numbers can be derived by leaving as many bits
3013 to the right alone as the divisor has zeros to the right.
3014 E.g. if x is an unsigned 32 bit number:
3015 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3018 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
3021 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3022 rtx op0, rtx op1, rtx target, int unsignedp)
3024 enum machine_mode compute_mode;
3026 rtx quotient = 0, remainder = 0;
3030 optab optab1, optab2;
3031 int op1_is_constant, op1_is_pow2 = 0;
3032 int max_cost, extra_cost;
3033 static HOST_WIDE_INT last_div_const = 0;
3034 static HOST_WIDE_INT ext_op1;
3036 op1_is_constant = GET_CODE (op1) == CONST_INT;
3037 if (op1_is_constant)
3039 ext_op1 = INTVAL (op1);
3041 ext_op1 &= GET_MODE_MASK (mode);
3042 op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3043 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3047 This is the structure of expand_divmod:
3049 First comes code to fix up the operands so we can perform the operations
3050 correctly and efficiently.
3052 Second comes a switch statement with code specific for each rounding mode.
3053 For some special operands this code emits all RTL for the desired
3054 operation, for other cases, it generates only a quotient and stores it in
3055 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
3056 to indicate that it has not done anything.
3058 Last comes code that finishes the operation. If QUOTIENT is set and
3059 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
3060 QUOTIENT is not set, it is computed using trunc rounding.
3062 We try to generate special code for division and remainder when OP1 is a
3063 constant. If |OP1| = 2**n we can use shifts and some other fast
3064 operations. For other values of OP1, we compute a carefully selected
3065 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3068 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3069 half of the product. Different strategies for generating the product are
3070 implemented in expand_mult_highpart.
3072 If what we actually want is the remainder, we generate that by another
3073 by-constant multiplication and a subtraction. */
3075 /* We shouldn't be called with OP1 == const1_rtx, but some of the
3076 code below will malfunction if we are, so check here and handle
3077 the special case if so. */
3078 if (op1 == const1_rtx)
3079 return rem_flag ? const0_rtx : op0;
3081 /* When dividing by -1, we could get an overflow.
3082 negv_optab can handle overflows. */
3083 if (! unsignedp && op1 == constm1_rtx)
3087 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3088 ? negv_optab : neg_optab, op0, target, 0);
3092 /* Don't use the function value register as a target
3093 since we have to read it as well as write it,
3094 and function-inlining gets confused by this. */
3095 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3096 /* Don't clobber an operand while doing a multi-step calculation. */
3097 || ((rem_flag || op1_is_constant)
3098 && (reg_mentioned_p (target, op0)
3099 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
3100 || reg_mentioned_p (target, op1)
3101 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
3104 /* Get the mode in which to perform this computation. Normally it will
3105 be MODE, but sometimes we can't do the desired operation in MODE.
3106 If so, pick a wider mode in which we can do the operation. Convert
3107 to that mode at the start to avoid repeated conversions.
3109 First see what operations we need. These depend on the expression
3110 we are evaluating. (We assume that divxx3 insns exist under the
3111 same conditions that modxx3 insns and that these insns don't normally
3112 fail. If these assumptions are not correct, we may generate less
3113 efficient code in some cases.)
3115 Then see if we find a mode in which we can open-code that operation
3116 (either a division, modulus, or shift). Finally, check for the smallest
3117 mode for which we can do the operation with a library call. */
3119 /* We might want to refine this now that we have division-by-constant
3120 optimization. Since expand_mult_highpart tries so many variants, it is
3121 not straightforward to generalize this. Maybe we should make an array
3122 of possible modes in init_expmed? Save this for GCC 2.7. */
3124 optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3125 ? (unsignedp ? lshr_optab : ashr_optab)
3126 : (unsignedp ? udiv_optab : sdiv_optab));
3127 optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3129 : (unsignedp ? udivmod_optab : sdivmod_optab));
3131 for (compute_mode = mode; compute_mode != VOIDmode;
3132 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3133 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
3134 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
3137 if (compute_mode == VOIDmode)
3138 for (compute_mode = mode; compute_mode != VOIDmode;
3139 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3140 if (optab1->handlers[(int) compute_mode].libfunc
3141 || optab2->handlers[(int) compute_mode].libfunc)
3144 /* If we still couldn't find a mode, use MODE, but we'll probably abort
3146 if (compute_mode == VOIDmode)
3147 compute_mode = mode;
3149 if (target && GET_MODE (target) == compute_mode)
3152 tquotient = gen_reg_rtx (compute_mode);
3154 size = GET_MODE_BITSIZE (compute_mode);
3156 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3157 (mode), and thereby get better code when OP1 is a constant. Do that
3158 later. It will require going over all usages of SIZE below. */
3159 size = GET_MODE_BITSIZE (mode);
3162 /* Only deduct something for a REM if the last divide done was
3163 for a different constant. Then set the constant of the last
3165 max_cost = div_cost[(int) compute_mode]
3166 - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3167 && INTVAL (op1) == last_div_const)
3168 ? mul_cost[(int) compute_mode] + add_cost : 0);
3170 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3172 /* Now convert to the best mode to use. */
3173 if (compute_mode != mode)
3175 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3176 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3178 /* convert_modes may have placed op1 into a register, so we
3179 must recompute the following. */
3180 op1_is_constant = GET_CODE (op1) == CONST_INT;
3181 op1_is_pow2 = (op1_is_constant
3182 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3184 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3187 /* If one of the operands is a volatile MEM, copy it into a register. */
3189 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3190 op0 = force_reg (compute_mode, op0);
3191 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3192 op1 = force_reg (compute_mode, op1);
3194 /* If we need the remainder or if OP1 is constant, we need to
3195 put OP0 in a register in case it has any queued subexpressions. */
3196 if (rem_flag || op1_is_constant)
3197 op0 = force_reg (compute_mode, op0);
3199 last = get_last_insn ();
3201 /* Promote floor rounding to trunc rounding for unsigned operations. */
3204 if (code == FLOOR_DIV_EXPR)
3205 code = TRUNC_DIV_EXPR;
3206 if (code == FLOOR_MOD_EXPR)
3207 code = TRUNC_MOD_EXPR;
3208 if (code == EXACT_DIV_EXPR && op1_is_pow2)
3209 code = TRUNC_DIV_EXPR;
3212 if (op1 != const0_rtx)
3215 case TRUNC_MOD_EXPR:
3216 case TRUNC_DIV_EXPR:
3217 if (op1_is_constant)
3221 unsigned HOST_WIDE_INT mh, ml;
3222 int pre_shift, post_shift;
3224 unsigned HOST_WIDE_INT d = (INTVAL (op1)
3225 & GET_MODE_MASK (compute_mode));
3227 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3229 pre_shift = floor_log2 (d);
3233 = expand_binop (compute_mode, and_optab, op0,
3234 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3238 return gen_lowpart (mode, remainder);
3240 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3241 build_int_2 (pre_shift, 0),
3244 else if (size <= HOST_BITS_PER_WIDE_INT)
3246 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3248 /* Most significant bit of divisor is set; emit an scc
3250 quotient = emit_store_flag (tquotient, GEU, op0, op1,
3251 compute_mode, 1, 1);
3257 /* Find a suitable multiplier and right shift count
3258 instead of multiplying with D. */
3260 mh = choose_multiplier (d, size, size,
3261 &ml, &post_shift, &dummy);
3263 /* If the suggested multiplier is more than SIZE bits,
3264 we can do better for even divisors, using an
3265 initial right shift. */
3266 if (mh != 0 && (d & 1) == 0)
3268 pre_shift = floor_log2 (d & -d);
3269 mh = choose_multiplier (d >> pre_shift, size,
3271 &ml, &post_shift, &dummy);
3282 if (post_shift - 1 >= BITS_PER_WORD)
3285 extra_cost = (shift_cost[post_shift - 1]
3286 + shift_cost[1] + 2 * add_cost);
3287 t1 = expand_mult_highpart (compute_mode, op0, ml,
3289 max_cost - extra_cost);
3292 t2 = force_operand (gen_rtx_MINUS (compute_mode,
3295 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3296 build_int_2 (1, 0), NULL_RTX,1);
3297 t4 = force_operand (gen_rtx_PLUS (compute_mode,
3301 = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3302 build_int_2 (post_shift - 1, 0),
3309 if (pre_shift >= BITS_PER_WORD
3310 || post_shift >= BITS_PER_WORD)
3313 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3314 build_int_2 (pre_shift, 0),
3316 extra_cost = (shift_cost[pre_shift]
3317 + shift_cost[post_shift]);
3318 t2 = expand_mult_highpart (compute_mode, t1, ml,
3320 max_cost - extra_cost);
3324 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3325 build_int_2 (post_shift, 0),
3330 else /* Too wide mode to use tricky code */
3333 insn = get_last_insn ();
3335 && (set = single_set (insn)) != 0
3336 && SET_DEST (set) == quotient)
3337 set_unique_reg_note (insn,
3339 gen_rtx_UDIV (compute_mode, op0, op1));
3341 else /* TRUNC_DIV, signed */
3343 unsigned HOST_WIDE_INT ml;
3344 int lgup, post_shift;
3345 HOST_WIDE_INT d = INTVAL (op1);
3346 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3348 /* n rem d = n rem -d */
3349 if (rem_flag && d < 0)
3352 op1 = gen_int_mode (abs_d, compute_mode);
3358 quotient = expand_unop (compute_mode, neg_optab, op0,
3360 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3362 /* This case is not handled correctly below. */
3363 quotient = emit_store_flag (tquotient, EQ, op0, op1,
3364 compute_mode, 1, 1);
3368 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3369 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap)
3370 /* ??? The cheap metric is computed only for
3371 word_mode. If this operation is wider, this may
3372 not be so. Assume true if the optab has an
3373 expander for this mode. */
3374 && (((rem_flag ? smod_optab : sdiv_optab)
3375 ->handlers[(int) compute_mode].insn_code
3376 != CODE_FOR_nothing)
3377 || (sdivmod_optab->handlers[(int) compute_mode]
3378 .insn_code != CODE_FOR_nothing)))
3380 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3382 lgup = floor_log2 (abs_d);
3383 if (BRANCH_COST < 1 || (abs_d != 2 && BRANCH_COST < 3))
3385 rtx label = gen_label_rtx ();
3388 t1 = copy_to_mode_reg (compute_mode, op0);
3389 do_cmp_and_jump (t1, const0_rtx, GE,
3390 compute_mode, label);
3391 expand_inc (t1, gen_int_mode (abs_d - 1,
3394 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3395 build_int_2 (lgup, 0),
3401 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3402 build_int_2 (size - 1, 0),
3404 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3405 build_int_2 (size - lgup, 0),
3407 t3 = force_operand (gen_rtx_PLUS (compute_mode,
3410 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3411 build_int_2 (lgup, 0),
3415 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
3419 insn = get_last_insn ();
3421 && (set = single_set (insn)) != 0
3422 && SET_DEST (set) == quotient
3423 && abs_d < ((unsigned HOST_WIDE_INT) 1
3424 << (HOST_BITS_PER_WIDE_INT - 1)))
3425 set_unique_reg_note (insn,
3427 gen_rtx_DIV (compute_mode,
3434 quotient = expand_unop (compute_mode, neg_optab,
3435 quotient, quotient, 0);
3438 else if (size <= HOST_BITS_PER_WIDE_INT)
3440 choose_multiplier (abs_d, size, size - 1,
3441 &ml, &post_shift, &lgup);
3442 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3446 if (post_shift >= BITS_PER_WORD
3447 || size - 1 >= BITS_PER_WORD)
3450 extra_cost = (shift_cost[post_shift]
3451 + shift_cost[size - 1] + add_cost);
3452 t1 = expand_mult_highpart (compute_mode, op0, ml,
3454 max_cost - extra_cost);
3457 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3458 build_int_2 (post_shift, 0), NULL_RTX, 0);
3459 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3460 build_int_2 (size - 1, 0), NULL_RTX, 0);
3463 = force_operand (gen_rtx_MINUS (compute_mode,
3468 = force_operand (gen_rtx_MINUS (compute_mode,
3476 if (post_shift >= BITS_PER_WORD
3477 || size - 1 >= BITS_PER_WORD)
3480 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3481 extra_cost = (shift_cost[post_shift]
3482 + shift_cost[size - 1] + 2 * add_cost);
3483 t1 = expand_mult_highpart (compute_mode, op0, ml,
3485 max_cost - extra_cost);
3488 t2 = force_operand (gen_rtx_PLUS (compute_mode,
3491 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3492 build_int_2 (post_shift, 0),
3494 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3495 build_int_2 (size - 1, 0),
3499 = force_operand (gen_rtx_MINUS (compute_mode,
3504 = force_operand (gen_rtx_MINUS (compute_mode,
3509 else /* Too wide mode to use tricky code */
3512 insn = get_last_insn ();
3514 && (set = single_set (insn)) != 0
3515 && SET_DEST (set) == quotient)
3516 set_unique_reg_note (insn,
3518 gen_rtx_DIV (compute_mode, op0, op1));
3523 delete_insns_since (last);
3526 case FLOOR_DIV_EXPR:
3527 case FLOOR_MOD_EXPR:
3528 /* We will come here only for signed operations. */
3529 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3531 unsigned HOST_WIDE_INT mh, ml;
3532 int pre_shift, lgup, post_shift;
3533 HOST_WIDE_INT d = INTVAL (op1);
3537 /* We could just as easily deal with negative constants here,
3538 but it does not seem worth the trouble for GCC 2.6. */
3539 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3541 pre_shift = floor_log2 (d);
3544 remainder = expand_binop (compute_mode, and_optab, op0,
3545 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3546 remainder, 0, OPTAB_LIB_WIDEN);
3548 return gen_lowpart (mode, remainder);
3550 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3551 build_int_2 (pre_shift, 0),
3558 mh = choose_multiplier (d, size, size - 1,
3559 &ml, &post_shift, &lgup);
3563 if (post_shift < BITS_PER_WORD
3564 && size - 1 < BITS_PER_WORD)
3566 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3567 build_int_2 (size - 1, 0),
3569 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3570 NULL_RTX, 0, OPTAB_WIDEN);
3571 extra_cost = (shift_cost[post_shift]
3572 + shift_cost[size - 1] + 2 * add_cost);
3573 t3 = expand_mult_highpart (compute_mode, t2, ml,
3575 max_cost - extra_cost);
3578 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3579 build_int_2 (post_shift, 0),
3581 quotient = expand_binop (compute_mode, xor_optab,
3582 t4, t1, tquotient, 0,
3590 rtx nsign, t1, t2, t3, t4;
3591 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3592 op0, constm1_rtx), NULL_RTX);
3593 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3595 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3596 build_int_2 (size - 1, 0), NULL_RTX, 0);
3597 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3599 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3604 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3606 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3615 delete_insns_since (last);
3617 /* Try using an instruction that produces both the quotient and
3618 remainder, using truncation. We can easily compensate the quotient
3619 or remainder to get floor rounding, once we have the remainder.
3620 Notice that we compute also the final remainder value here,
3621 and return the result right away. */
3622 if (target == 0 || GET_MODE (target) != compute_mode)
3623 target = gen_reg_rtx (compute_mode);
3628 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3629 quotient = gen_reg_rtx (compute_mode);
3634 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3635 remainder = gen_reg_rtx (compute_mode);
3638 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3639 quotient, remainder, 0))
3641 /* This could be computed with a branch-less sequence.
3642 Save that for later. */
3644 rtx label = gen_label_rtx ();
3645 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3646 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3647 NULL_RTX, 0, OPTAB_WIDEN);
3648 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3649 expand_dec (quotient, const1_rtx);
3650 expand_inc (remainder, op1);
3652 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3655 /* No luck with division elimination or divmod. Have to do it
3656 by conditionally adjusting op0 *and* the result. */
3658 rtx label1, label2, label3, label4, label5;
3662 quotient = gen_reg_rtx (compute_mode);
3663 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3664 label1 = gen_label_rtx ();
3665 label2 = gen_label_rtx ();
3666 label3 = gen_label_rtx ();
3667 label4 = gen_label_rtx ();
3668 label5 = gen_label_rtx ();
3669 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3670 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3671 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3672 quotient, 0, OPTAB_LIB_WIDEN);
3673 if (tem != quotient)
3674 emit_move_insn (quotient, tem);
3675 emit_jump_insn (gen_jump (label5));
3677 emit_label (label1);
3678 expand_inc (adjusted_op0, const1_rtx);
3679 emit_jump_insn (gen_jump (label4));
3681 emit_label (label2);
3682 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3683 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3684 quotient, 0, OPTAB_LIB_WIDEN);
3685 if (tem != quotient)
3686 emit_move_insn (quotient, tem);
3687 emit_jump_insn (gen_jump (label5));
3689 emit_label (label3);
3690 expand_dec (adjusted_op0, const1_rtx);
3691 emit_label (label4);
3692 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3693 quotient, 0, OPTAB_LIB_WIDEN);
3694 if (tem != quotient)
3695 emit_move_insn (quotient, tem);
3696 expand_dec (quotient, const1_rtx);
3697 emit_label (label5);
3705 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3708 unsigned HOST_WIDE_INT d = INTVAL (op1);
3709 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3710 build_int_2 (floor_log2 (d), 0),
3712 t2 = expand_binop (compute_mode, and_optab, op0,
3714 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3715 t3 = gen_reg_rtx (compute_mode);
3716 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3717 compute_mode, 1, 1);
3721 lab = gen_label_rtx ();
3722 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3723 expand_inc (t1, const1_rtx);
3728 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3734 /* Try using an instruction that produces both the quotient and
3735 remainder, using truncation. We can easily compensate the
3736 quotient or remainder to get ceiling rounding, once we have the
3737 remainder. Notice that we compute also the final remainder
3738 value here, and return the result right away. */
3739 if (target == 0 || GET_MODE (target) != compute_mode)
3740 target = gen_reg_rtx (compute_mode);
3744 remainder = (GET_CODE (target) == REG
3745 ? target : gen_reg_rtx (compute_mode));
3746 quotient = gen_reg_rtx (compute_mode);
3750 quotient = (GET_CODE (target) == REG
3751 ? target : gen_reg_rtx (compute_mode));
3752 remainder = gen_reg_rtx (compute_mode);
3755 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3758 /* This could be computed with a branch-less sequence.
3759 Save that for later. */
3760 rtx label = gen_label_rtx ();
3761 do_cmp_and_jump (remainder, const0_rtx, EQ,
3762 compute_mode, label);
3763 expand_inc (quotient, const1_rtx);
3764 expand_dec (remainder, op1);
3766 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3769 /* No luck with division elimination or divmod. Have to do it
3770 by conditionally adjusting op0 *and* the result. */
3773 rtx adjusted_op0, tem;
3775 quotient = gen_reg_rtx (compute_mode);
3776 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3777 label1 = gen_label_rtx ();
3778 label2 = gen_label_rtx ();
3779 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3780 compute_mode, label1);
3781 emit_move_insn (quotient, const0_rtx);
3782 emit_jump_insn (gen_jump (label2));
3784 emit_label (label1);
3785 expand_dec (adjusted_op0, const1_rtx);
3786 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3787 quotient, 1, OPTAB_LIB_WIDEN);
3788 if (tem != quotient)
3789 emit_move_insn (quotient, tem);
3790 expand_inc (quotient, const1_rtx);
3791 emit_label (label2);
3796 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3797 && INTVAL (op1) >= 0)
3799 /* This is extremely similar to the code for the unsigned case
3800 above. For 2.7 we should merge these variants, but for
3801 2.6.1 I don't want to touch the code for unsigned since that
3802 get used in C. The signed case will only be used by other
3806 unsigned HOST_WIDE_INT d = INTVAL (op1);
3807 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3808 build_int_2 (floor_log2 (d), 0),
3810 t2 = expand_binop (compute_mode, and_optab, op0,
3812 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3813 t3 = gen_reg_rtx (compute_mode);
3814 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3815 compute_mode, 1, 1);
3819 lab = gen_label_rtx ();
3820 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3821 expand_inc (t1, const1_rtx);
3826 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3832 /* Try using an instruction that produces both the quotient and
3833 remainder, using truncation. We can easily compensate the
3834 quotient or remainder to get ceiling rounding, once we have the
3835 remainder. Notice that we compute also the final remainder
3836 value here, and return the result right away. */
3837 if (target == 0 || GET_MODE (target) != compute_mode)
3838 target = gen_reg_rtx (compute_mode);
3841 remainder= (GET_CODE (target) == REG
3842 ? target : gen_reg_rtx (compute_mode));
3843 quotient = gen_reg_rtx (compute_mode);
3847 quotient = (GET_CODE (target) == REG
3848 ? target : gen_reg_rtx (compute_mode));
3849 remainder = gen_reg_rtx (compute_mode);
3852 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3855 /* This could be computed with a branch-less sequence.
3856 Save that for later. */
3858 rtx label = gen_label_rtx ();
3859 do_cmp_and_jump (remainder, const0_rtx, EQ,
3860 compute_mode, label);
3861 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3862 NULL_RTX, 0, OPTAB_WIDEN);
3863 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3864 expand_inc (quotient, const1_rtx);
3865 expand_dec (remainder, op1);
3867 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3870 /* No luck with division elimination or divmod. Have to do it
3871 by conditionally adjusting op0 *and* the result. */
3873 rtx label1, label2, label3, label4, label5;
3877 quotient = gen_reg_rtx (compute_mode);
3878 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3879 label1 = gen_label_rtx ();
3880 label2 = gen_label_rtx ();
3881 label3 = gen_label_rtx ();
3882 label4 = gen_label_rtx ();
3883 label5 = gen_label_rtx ();
3884 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3885 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3886 compute_mode, label1);
3887 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3888 quotient, 0, OPTAB_LIB_WIDEN);
3889 if (tem != quotient)
3890 emit_move_insn (quotient, tem);
3891 emit_jump_insn (gen_jump (label5));
3893 emit_label (label1);
3894 expand_dec (adjusted_op0, const1_rtx);
3895 emit_jump_insn (gen_jump (label4));
3897 emit_label (label2);
3898 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3899 compute_mode, label3);
3900 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3901 quotient, 0, OPTAB_LIB_WIDEN);
3902 if (tem != quotient)
3903 emit_move_insn (quotient, tem);
3904 emit_jump_insn (gen_jump (label5));
3906 emit_label (label3);
3907 expand_inc (adjusted_op0, const1_rtx);
3908 emit_label (label4);
3909 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3910 quotient, 0, OPTAB_LIB_WIDEN);
3911 if (tem != quotient)
3912 emit_move_insn (quotient, tem);
3913 expand_inc (quotient, const1_rtx);
3914 emit_label (label5);
3919 case EXACT_DIV_EXPR:
3920 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3922 HOST_WIDE_INT d = INTVAL (op1);
3923 unsigned HOST_WIDE_INT ml;
3927 pre_shift = floor_log2 (d & -d);
3928 ml = invert_mod2n (d >> pre_shift, size);
3929 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3930 build_int_2 (pre_shift, 0), NULL_RTX, unsignedp);
3931 quotient = expand_mult (compute_mode, t1,
3932 gen_int_mode (ml, compute_mode),
3935 insn = get_last_insn ();
3936 set_unique_reg_note (insn,
3938 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
3944 case ROUND_DIV_EXPR:
3945 case ROUND_MOD_EXPR:
3950 label = gen_label_rtx ();
3951 quotient = gen_reg_rtx (compute_mode);
3952 remainder = gen_reg_rtx (compute_mode);
3953 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3956 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3957 quotient, 1, OPTAB_LIB_WIDEN);
3958 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3959 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3960 remainder, 1, OPTAB_LIB_WIDEN);
3962 tem = plus_constant (op1, -1);
3963 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3964 build_int_2 (1, 0), NULL_RTX, 1);
3965 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
3966 expand_inc (quotient, const1_rtx);
3967 expand_dec (remainder, op1);
3972 rtx abs_rem, abs_op1, tem, mask;
3974 label = gen_label_rtx ();
3975 quotient = gen_reg_rtx (compute_mode);
3976 remainder = gen_reg_rtx (compute_mode);
3977 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3980 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3981 quotient, 0, OPTAB_LIB_WIDEN);
3982 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3983 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3984 remainder, 0, OPTAB_LIB_WIDEN);
3986 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
3987 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
3988 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3989 build_int_2 (1, 0), NULL_RTX, 1);
3990 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
3991 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3992 NULL_RTX, 0, OPTAB_WIDEN);
3993 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3994 build_int_2 (size - 1, 0), NULL_RTX, 0);
3995 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3996 NULL_RTX, 0, OPTAB_WIDEN);
3997 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3998 NULL_RTX, 0, OPTAB_WIDEN);
3999 expand_inc (quotient, tem);
4000 tem = expand_binop (compute_mode, xor_optab, mask, op1,
4001 NULL_RTX, 0, OPTAB_WIDEN);
4002 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4003 NULL_RTX, 0, OPTAB_WIDEN);
4004 expand_dec (remainder, tem);
4007 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4015 if (target && GET_MODE (target) != compute_mode)
4020 /* Try to produce the remainder without producing the quotient.
4021 If we seem to have a divmod pattern that does not require widening,
4022 don't try widening here. We should really have a WIDEN argument
4023 to expand_twoval_binop, since what we'd really like to do here is
4024 1) try a mod insn in compute_mode
4025 2) try a divmod insn in compute_mode
4026 3) try a div insn in compute_mode and multiply-subtract to get
4028 4) try the same things with widening allowed. */
4030 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4033 ((optab2->handlers[(int) compute_mode].insn_code
4034 != CODE_FOR_nothing)
4035 ? OPTAB_DIRECT : OPTAB_WIDEN));
4038 /* No luck there. Can we do remainder and divide at once
4039 without a library call? */
4040 remainder = gen_reg_rtx (compute_mode);
4041 if (! expand_twoval_binop ((unsignedp
4045 NULL_RTX, remainder, unsignedp))
4050 return gen_lowpart (mode, remainder);
4053 /* Produce the quotient. Try a quotient insn, but not a library call.
4054 If we have a divmod in this mode, use it in preference to widening
4055 the div (for this test we assume it will not fail). Note that optab2
4056 is set to the one of the two optabs that the call below will use. */
4058 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
4059 op0, op1, rem_flag ? NULL_RTX : target,
4061 ((optab2->handlers[(int) compute_mode].insn_code
4062 != CODE_FOR_nothing)
4063 ? OPTAB_DIRECT : OPTAB_WIDEN));
4067 /* No luck there. Try a quotient-and-remainder insn,
4068 keeping the quotient alone. */
4069 quotient = gen_reg_rtx (compute_mode);
4070 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
4072 quotient, NULL_RTX, unsignedp))
4076 /* Still no luck. If we are not computing the remainder,
4077 use a library call for the quotient. */
4078 quotient = sign_expand_binop (compute_mode,
4079 udiv_optab, sdiv_optab,
4081 unsignedp, OPTAB_LIB_WIDEN);
4088 if (target && GET_MODE (target) != compute_mode)
4092 /* No divide instruction either. Use library for remainder. */
4093 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4095 unsignedp, OPTAB_LIB_WIDEN);
4098 /* We divided. Now finish doing X - Y * (X / Y). */
4099 remainder = expand_mult (compute_mode, quotient, op1,
4100 NULL_RTX, unsignedp);
4101 remainder = expand_binop (compute_mode, sub_optab, op0,
4102 remainder, target, unsignedp,
4107 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4110 /* Return a tree node with data type TYPE, describing the value of X.
4111 Usually this is an RTL_EXPR, if there is no obvious better choice.
4112 X may be an expression, however we only support those expressions
4113 generated by loop.c. */
4116 make_tree (tree type, rtx x)
4120 switch (GET_CODE (x))
4123 t = build_int_2 (INTVAL (x),
4124 (TREE_UNSIGNED (type)
4125 && (GET_MODE_BITSIZE (TYPE_MODE (type)) < HOST_BITS_PER_WIDE_INT))
4126 || INTVAL (x) >= 0 ? 0 : -1);
4127 TREE_TYPE (t) = type;
4131 if (GET_MODE (x) == VOIDmode)
4133 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4134 TREE_TYPE (t) = type;
4140 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4141 t = build_real (type, d);
4152 units = CONST_VECTOR_NUNITS (x);
4154 /* Build a tree with vector elements. */
4155 for (i = units - 1; i >= 0; --i)
4157 elt = CONST_VECTOR_ELT (x, i);
4158 t = tree_cons (NULL_TREE, make_tree (type, elt), t);
4161 return build_vector (type, t);
4165 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4166 make_tree (type, XEXP (x, 1))));
4169 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4170 make_tree (type, XEXP (x, 1))));
4173 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
4176 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
4177 make_tree (type, XEXP (x, 1))));
4180 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
4181 make_tree (type, XEXP (x, 1))));
4184 t = (*lang_hooks.types.unsigned_type) (type);
4185 return fold (convert (type,
4186 build (RSHIFT_EXPR, t,
4187 make_tree (t, XEXP (x, 0)),
4188 make_tree (type, XEXP (x, 1)))));
4191 t = (*lang_hooks.types.signed_type) (type);
4192 return fold (convert (type,
4193 build (RSHIFT_EXPR, t,
4194 make_tree (t, XEXP (x, 0)),
4195 make_tree (type, XEXP (x, 1)))));
4198 if (TREE_CODE (type) != REAL_TYPE)
4199 t = (*lang_hooks.types.signed_type) (type);
4203 return fold (convert (type,
4204 build (TRUNC_DIV_EXPR, t,
4205 make_tree (t, XEXP (x, 0)),
4206 make_tree (t, XEXP (x, 1)))));
4208 t = (*lang_hooks.types.unsigned_type) (type);
4209 return fold (convert (type,
4210 build (TRUNC_DIV_EXPR, t,
4211 make_tree (t, XEXP (x, 0)),
4212 make_tree (t, XEXP (x, 1)))));
4216 t = (*lang_hooks.types.type_for_mode) (GET_MODE (XEXP (x, 0)),
4217 GET_CODE (x) == ZERO_EXTEND);
4218 return fold (convert (type, make_tree (t, XEXP (x, 0))));
4221 t = make_node (RTL_EXPR);
4222 TREE_TYPE (t) = type;
4224 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
4225 ptr_mode. So convert. */
4226 if (POINTER_TYPE_P (type))
4227 x = convert_memory_address (TYPE_MODE (type), x);
4229 RTL_EXPR_RTL (t) = x;
4230 /* There are no insns to be output
4231 when this rtl_expr is used. */
4232 RTL_EXPR_SEQUENCE (t) = 0;
4237 /* Check whether the multiplication X * MULT + ADD overflows.
4238 X, MULT and ADD must be CONST_*.
4239 MODE is the machine mode for the computation.
4240 X and MULT must have mode MODE. ADD may have a different mode.
4241 So can X (defaults to same as MODE).
4242 UNSIGNEDP is nonzero to do unsigned multiplication. */
4245 const_mult_add_overflow_p (rtx x, rtx mult, rtx add, enum machine_mode mode, int unsignedp)
4247 tree type, mult_type, add_type, result;
4249 type = (*lang_hooks.types.type_for_mode) (mode, unsignedp);
4251 /* In order to get a proper overflow indication from an unsigned
4252 type, we have to pretend that it's a sizetype. */
4256 mult_type = copy_node (type);
4257 TYPE_IS_SIZETYPE (mult_type) = 1;
4260 add_type = (GET_MODE (add) == VOIDmode ? mult_type
4261 : (*lang_hooks.types.type_for_mode) (GET_MODE (add), unsignedp));
4263 result = fold (build (PLUS_EXPR, mult_type,
4264 fold (build (MULT_EXPR, mult_type,
4265 make_tree (mult_type, x),
4266 make_tree (mult_type, mult))),
4267 make_tree (add_type, add)));
4269 return TREE_CONSTANT_OVERFLOW (result);
4272 /* Return an rtx representing the value of X * MULT + ADD.
4273 TARGET is a suggestion for where to store the result (an rtx).
4274 MODE is the machine mode for the computation.
4275 X and MULT must have mode MODE. ADD may have a different mode.
4276 So can X (defaults to same as MODE).
4277 UNSIGNEDP is nonzero to do unsigned multiplication.
4278 This may emit insns. */
4281 expand_mult_add (rtx x, rtx target, rtx mult, rtx add, enum machine_mode mode,
4284 tree type = (*lang_hooks.types.type_for_mode) (mode, unsignedp);
4285 tree add_type = (GET_MODE (add) == VOIDmode
4286 ? type: (*lang_hooks.types.type_for_mode) (GET_MODE (add),
4288 tree result = fold (build (PLUS_EXPR, type,
4289 fold (build (MULT_EXPR, type,
4290 make_tree (type, x),
4291 make_tree (type, mult))),
4292 make_tree (add_type, add)));
4294 return expand_expr (result, target, VOIDmode, 0);
4297 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4298 and returning TARGET.
4300 If TARGET is 0, a pseudo-register or constant is returned. */
4303 expand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target)
4307 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
4308 tem = simplify_binary_operation (AND, mode, op0, op1);
4310 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4314 else if (tem != target)
4315 emit_move_insn (target, tem);
4319 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4320 and storing in TARGET. Normally return TARGET.
4321 Return 0 if that cannot be done.
4323 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
4324 it is VOIDmode, they cannot both be CONST_INT.
4326 UNSIGNEDP is for the case where we have to widen the operands
4327 to perform the operation. It says to use zero-extension.
4329 NORMALIZEP is 1 if we should convert the result to be either zero
4330 or one. Normalize is -1 if we should convert the result to be
4331 either zero or -1. If NORMALIZEP is zero, the result will be left
4332 "raw" out of the scc insn. */
4335 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
4336 enum machine_mode mode, int unsignedp, int normalizep)
4339 enum insn_code icode;
4340 enum machine_mode compare_mode;
4341 enum machine_mode target_mode = GET_MODE (target);
4343 rtx last = get_last_insn ();
4344 rtx pattern, comparison;
4346 /* ??? Ok to do this and then fail? */
4347 op0 = protect_from_queue (op0, 0);
4348 op1 = protect_from_queue (op1, 0);
4351 code = unsigned_condition (code);
4353 /* If one operand is constant, make it the second one. Only do this
4354 if the other operand is not constant as well. */
4356 if (swap_commutative_operands_p (op0, op1))
4361 code = swap_condition (code);
4364 if (mode == VOIDmode)
4365 mode = GET_MODE (op0);
4367 /* For some comparisons with 1 and -1, we can convert this to
4368 comparisons with zero. This will often produce more opportunities for
4369 store-flag insns. */
4374 if (op1 == const1_rtx)
4375 op1 = const0_rtx, code = LE;
4378 if (op1 == constm1_rtx)
4379 op1 = const0_rtx, code = LT;
4382 if (op1 == const1_rtx)
4383 op1 = const0_rtx, code = GT;
4386 if (op1 == constm1_rtx)
4387 op1 = const0_rtx, code = GE;
4390 if (op1 == const1_rtx)
4391 op1 = const0_rtx, code = NE;
4394 if (op1 == const1_rtx)
4395 op1 = const0_rtx, code = EQ;
4401 /* If we are comparing a double-word integer with zero, we can convert
4402 the comparison into one involving a single word. */
4403 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
4404 && GET_MODE_CLASS (mode) == MODE_INT
4405 && op1 == const0_rtx
4406 && (GET_CODE (op0) != MEM || ! MEM_VOLATILE_P (op0)))
4408 if (code == EQ || code == NE)
4410 rtx op00, op01, op0both;
4412 /* Do a logical OR of the two words and compare the result. */
4413 op00 = simplify_gen_subreg (word_mode, op0, mode, 0);
4414 op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD);
4415 op0both = expand_binop (word_mode, ior_optab, op00, op01,
4416 NULL_RTX, unsignedp, OPTAB_DIRECT);
4418 return emit_store_flag (target, code, op0both, op1, word_mode,
4419 unsignedp, normalizep);
4421 else if (code == LT || code == GE)
4425 /* If testing the sign bit, can just test on high word. */
4426 op0h = simplify_gen_subreg (word_mode, op0, mode,
4427 subreg_highpart_offset (word_mode, mode));
4428 return emit_store_flag (target, code, op0h, op1, word_mode,
4429 unsignedp, normalizep);
4433 /* From now on, we won't change CODE, so set ICODE now. */
4434 icode = setcc_gen_code[(int) code];
4436 /* If this is A < 0 or A >= 0, we can do this by taking the ones
4437 complement of A (for GE) and shifting the sign bit to the low bit. */
4438 if (op1 == const0_rtx && (code == LT || code == GE)
4439 && GET_MODE_CLASS (mode) == MODE_INT
4440 && (normalizep || STORE_FLAG_VALUE == 1
4441 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4442 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4443 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4447 /* If the result is to be wider than OP0, it is best to convert it
4448 first. If it is to be narrower, it is *incorrect* to convert it
4450 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4452 op0 = protect_from_queue (op0, 0);
4453 op0 = convert_modes (target_mode, mode, op0, 0);
4457 if (target_mode != mode)
4461 op0 = expand_unop (mode, one_cmpl_optab, op0,
4462 ((STORE_FLAG_VALUE == 1 || normalizep)
4463 ? 0 : subtarget), 0);
4465 if (STORE_FLAG_VALUE == 1 || normalizep)
4466 /* If we are supposed to produce a 0/1 value, we want to do
4467 a logical shift from the sign bit to the low-order bit; for
4468 a -1/0 value, we do an arithmetic shift. */
4469 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4470 size_int (GET_MODE_BITSIZE (mode) - 1),
4471 subtarget, normalizep != -1);
4473 if (mode != target_mode)
4474 op0 = convert_modes (target_mode, mode, op0, 0);
4479 if (icode != CODE_FOR_nothing)
4481 insn_operand_predicate_fn pred;
4483 /* We think we may be able to do this with a scc insn. Emit the
4484 comparison and then the scc insn.
4486 compare_from_rtx may call emit_queue, which would be deleted below
4487 if the scc insn fails. So call it ourselves before setting LAST.
4488 Likewise for do_pending_stack_adjust. */
4491 do_pending_stack_adjust ();
4492 last = get_last_insn ();
4495 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX);
4496 if (GET_CODE (comparison) == CONST_INT)
4497 return (comparison == const0_rtx ? const0_rtx
4498 : normalizep == 1 ? const1_rtx
4499 : normalizep == -1 ? constm1_rtx
4502 /* The code of COMPARISON may not match CODE if compare_from_rtx
4503 decided to swap its operands and reverse the original code.
4505 We know that compare_from_rtx returns either a CONST_INT or
4506 a new comparison code, so it is safe to just extract the
4507 code from COMPARISON. */
4508 code = GET_CODE (comparison);
4510 /* Get a reference to the target in the proper mode for this insn. */
4511 compare_mode = insn_data[(int) icode].operand[0].mode;
4513 pred = insn_data[(int) icode].operand[0].predicate;
4514 if (preserve_subexpressions_p ()
4515 || ! (*pred) (subtarget, compare_mode))
4516 subtarget = gen_reg_rtx (compare_mode);
4518 pattern = GEN_FCN (icode) (subtarget);
4521 emit_insn (pattern);
4523 /* If we are converting to a wider mode, first convert to
4524 TARGET_MODE, then normalize. This produces better combining
4525 opportunities on machines that have a SIGN_EXTRACT when we are
4526 testing a single bit. This mostly benefits the 68k.
4528 If STORE_FLAG_VALUE does not have the sign bit set when
4529 interpreted in COMPARE_MODE, we can do this conversion as
4530 unsigned, which is usually more efficient. */
4531 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4533 convert_move (target, subtarget,
4534 (GET_MODE_BITSIZE (compare_mode)
4535 <= HOST_BITS_PER_WIDE_INT)
4536 && 0 == (STORE_FLAG_VALUE
4537 & ((HOST_WIDE_INT) 1
4538 << (GET_MODE_BITSIZE (compare_mode) -1))));
4540 compare_mode = target_mode;
4545 /* If we want to keep subexpressions around, don't reuse our
4548 if (preserve_subexpressions_p ())
4551 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
4552 we don't have to do anything. */
4553 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4555 /* STORE_FLAG_VALUE might be the most negative number, so write
4556 the comparison this way to avoid a compiler-time warning. */
4557 else if (- normalizep == STORE_FLAG_VALUE)
4558 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4560 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4561 makes it hard to use a value of just the sign bit due to
4562 ANSI integer constant typing rules. */
4563 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4564 && (STORE_FLAG_VALUE
4565 & ((HOST_WIDE_INT) 1
4566 << (GET_MODE_BITSIZE (compare_mode) - 1))))
4567 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4568 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4569 subtarget, normalizep == 1);
4570 else if (STORE_FLAG_VALUE & 1)
4572 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget);
4573 if (normalizep == -1)
4574 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4579 /* If we were converting to a smaller mode, do the
4581 if (target_mode != compare_mode)
4583 convert_move (target, op0, 0);
4591 delete_insns_since (last);
4593 /* If expensive optimizations, use different pseudo registers for each
4594 insn, instead of reusing the same pseudo. This leads to better CSE,
4595 but slows down the compiler, since there are more pseudos */
4596 subtarget = (!flag_expensive_optimizations
4597 && (target_mode == mode)) ? target : NULL_RTX;
4599 /* If we reached here, we can't do this with a scc insn. However, there
4600 are some comparisons that can be done directly. For example, if
4601 this is an equality comparison of integers, we can try to exclusive-or
4602 (or subtract) the two operands and use a recursive call to try the
4603 comparison with zero. Don't do any of these cases if branches are
4607 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4608 && op1 != const0_rtx)
4610 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4614 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4617 tem = emit_store_flag (target, code, tem, const0_rtx,
4618 mode, unsignedp, normalizep);
4620 delete_insns_since (last);
4624 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4625 the constant zero. Reject all other comparisons at this point. Only
4626 do LE and GT if branches are expensive since they are expensive on
4627 2-operand machines. */
4629 if (BRANCH_COST == 0
4630 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4631 || (code != EQ && code != NE
4632 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4635 /* See what we need to return. We can only return a 1, -1, or the
4638 if (normalizep == 0)
4640 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4641 normalizep = STORE_FLAG_VALUE;
4643 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4644 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4645 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4651 /* Try to put the result of the comparison in the sign bit. Assume we can't
4652 do the necessary operation below. */
4656 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4657 the sign bit set. */
4661 /* This is destructive, so SUBTARGET can't be OP0. */
4662 if (rtx_equal_p (subtarget, op0))
4665 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4668 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4672 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4673 number of bits in the mode of OP0, minus one. */
4677 if (rtx_equal_p (subtarget, op0))
4680 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4681 size_int (GET_MODE_BITSIZE (mode) - 1),
4683 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4687 if (code == EQ || code == NE)
4689 /* For EQ or NE, one way to do the comparison is to apply an operation
4690 that converts the operand into a positive number if it is nonzero
4691 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4692 for NE we negate. This puts the result in the sign bit. Then we
4693 normalize with a shift, if needed.
4695 Two operations that can do the above actions are ABS and FFS, so try
4696 them. If that doesn't work, and MODE is smaller than a full word,
4697 we can use zero-extension to the wider mode (an unsigned conversion)
4698 as the operation. */
4700 /* Note that ABS doesn't yield a positive number for INT_MIN, but
4701 that is compensated by the subsequent overflow when subtracting
4704 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4705 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4706 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4707 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4708 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4710 op0 = protect_from_queue (op0, 0);
4711 tem = convert_modes (word_mode, mode, op0, 1);
4718 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4721 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4724 /* If we couldn't do it that way, for NE we can "or" the two's complement
4725 of the value with itself. For EQ, we take the one's complement of
4726 that "or", which is an extra insn, so we only handle EQ if branches
4729 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4731 if (rtx_equal_p (subtarget, op0))
4734 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4735 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4738 if (tem && code == EQ)
4739 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4743 if (tem && normalizep)
4744 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4745 size_int (GET_MODE_BITSIZE (mode) - 1),
4746 subtarget, normalizep == 1);
4750 if (GET_MODE (tem) != target_mode)
4752 convert_move (target, tem, 0);
4755 else if (!subtarget)
4757 emit_move_insn (target, tem);
4762 delete_insns_since (last);
4767 /* Like emit_store_flag, but always succeeds. */
4770 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
4771 enum machine_mode mode, int unsignedp, int normalizep)
4775 /* First see if emit_store_flag can do the job. */
4776 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4780 if (normalizep == 0)
4783 /* If this failed, we have to do this with set/compare/jump/set code. */
4785 if (GET_CODE (target) != REG
4786 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4787 target = gen_reg_rtx (GET_MODE (target));
4789 emit_move_insn (target, const1_rtx);
4790 label = gen_label_rtx ();
4791 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
4794 emit_move_insn (target, const0_rtx);
4800 /* Perform possibly multi-word comparison and conditional jump to LABEL
4801 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4803 The algorithm is based on the code in expr.c:do_jump.
4805 Note that this does not perform a general comparison. Only variants
4806 generated within expmed.c are correctly handled, others abort (but could
4807 be handled if needed). */
4810 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
4813 /* If this mode is an integer too wide to compare properly,
4814 compare word by word. Rely on cse to optimize constant cases. */
4816 if (GET_MODE_CLASS (mode) == MODE_INT
4817 && ! can_compare_p (op, mode, ccp_jump))
4819 rtx label2 = gen_label_rtx ();
4824 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4828 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4832 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4836 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4840 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4843 /* do_jump_by_parts_equality_rtx compares with zero. Luckily
4844 that's the only equality operations we do */
4846 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4848 do_jump_by_parts_equality_rtx (arg1, label2, label);
4852 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4854 do_jump_by_parts_equality_rtx (arg1, label, label2);
4861 emit_label (label2);
4864 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);