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))
1128 pat = GEN_FCN (icode) (dest, src, rtxpos);
1135 return extract_bit_field (dest, bitsize,
1136 bitnum - pos * GET_MODE_BITSIZE (innermode),
1137 unsignedp, target, mode, tmode, total_size);
1141 /* Make sure we are playing with integral modes. Pun with subregs
1144 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1145 if (imode != GET_MODE (op0))
1147 if (GET_CODE (op0) == MEM)
1148 op0 = adjust_address (op0, imode, 0);
1149 else if (imode != BLKmode)
1150 op0 = gen_lowpart (imode, op0);
1156 /* We may be accessing data outside the field, which means
1157 we can alias adjacent data. */
1158 if (GET_CODE (op0) == MEM)
1160 op0 = shallow_copy_rtx (op0);
1161 set_mem_alias_set (op0, 0);
1162 set_mem_expr (op0, 0);
1165 /* Extraction of a full-word or multi-word value from a structure
1166 in a register or aligned memory can be done with just a SUBREG.
1167 A subword value in the least significant part of a register
1168 can also be extracted with a SUBREG. For this, we need the
1169 byte offset of the value in op0. */
1171 byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1173 /* If OP0 is a register, BITPOS must count within a word.
1174 But as we have it, it counts within whatever size OP0 now has.
1175 On a bigendian machine, these are not the same, so convert. */
1176 if (BYTES_BIG_ENDIAN
1177 && GET_CODE (op0) != MEM
1178 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1179 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1181 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1182 If that's wrong, the solution is to test for it and set TARGET to 0
1185 /* Only scalar integer modes can be converted via subregs. There is an
1186 additional problem for FP modes here in that they can have a precision
1187 which is different from the size. mode_for_size uses precision, but
1188 we want a mode based on the size, so we must avoid calling it for FP
1190 mode1 = (SCALAR_INT_MODE_P (tmode)
1191 ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0)
1194 if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1195 && bitpos % BITS_PER_WORD == 0)
1196 || (mode1 != BLKmode
1197 /* ??? The big endian test here is wrong. This is correct
1198 if the value is in a register, and if mode_for_size is not
1199 the same mode as op0. This causes us to get unnecessarily
1200 inefficient code from the Thumb port when -mbig-endian. */
1201 && (BYTES_BIG_ENDIAN
1202 ? bitpos + bitsize == BITS_PER_WORD
1204 && ((GET_CODE (op0) != MEM
1205 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1206 GET_MODE_BITSIZE (GET_MODE (op0)))
1207 && GET_MODE_SIZE (mode1) != 0
1208 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1209 || (GET_CODE (op0) == MEM
1210 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1211 || (offset * BITS_PER_UNIT % bitsize == 0
1212 && MEM_ALIGN (op0) % bitsize == 0)))))
1214 if (mode1 != GET_MODE (op0))
1216 if (GET_CODE (op0) == SUBREG)
1218 if (GET_MODE (SUBREG_REG (op0)) == mode1
1219 || GET_MODE_CLASS (mode1) == MODE_INT
1220 || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1221 op0 = SUBREG_REG (op0);
1223 /* Else we've got some float mode source being extracted into
1224 a different float mode destination -- this combination of
1225 subregs results in Severe Tire Damage. */
1226 goto no_subreg_mode_swap;
1228 if (GET_CODE (op0) == REG)
1229 op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1231 op0 = adjust_address (op0, mode1, offset);
1234 return convert_to_mode (tmode, op0, unsignedp);
1237 no_subreg_mode_swap:
1239 /* Handle fields bigger than a word. */
1241 if (bitsize > BITS_PER_WORD)
1243 /* Here we transfer the words of the field
1244 in the order least significant first.
1245 This is because the most significant word is the one which may
1246 be less than full. */
1248 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1251 if (target == 0 || GET_CODE (target) != REG)
1252 target = gen_reg_rtx (mode);
1254 /* Indicate for flow that the entire target reg is being set. */
1255 emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1257 for (i = 0; i < nwords; i++)
1259 /* If I is 0, use the low-order word in both field and target;
1260 if I is 1, use the next to lowest word; and so on. */
1261 /* Word number in TARGET to use. */
1262 unsigned int wordnum
1264 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1266 /* Offset from start of field in OP0. */
1267 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1268 ? MAX (0, ((int) bitsize - ((int) i + 1)
1269 * (int) BITS_PER_WORD))
1270 : (int) i * BITS_PER_WORD);
1271 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1273 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1274 bitsize - i * BITS_PER_WORD),
1275 bitnum + bit_offset, 1, target_part, mode,
1276 word_mode, total_size);
1278 if (target_part == 0)
1281 if (result_part != target_part)
1282 emit_move_insn (target_part, result_part);
1287 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1288 need to be zero'd out. */
1289 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1291 unsigned int i, total_words;
1293 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1294 for (i = nwords; i < total_words; i++)
1296 (operand_subword (target,
1297 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1304 /* Signed bit field: sign-extend with two arithmetic shifts. */
1305 target = expand_shift (LSHIFT_EXPR, mode, target,
1306 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1308 return expand_shift (RSHIFT_EXPR, mode, target,
1309 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1313 /* From here on we know the desired field is smaller than a word. */
1315 /* Check if there is a correspondingly-sized integer field, so we can
1316 safely extract it as one size of integer, if necessary; then
1317 truncate or extend to the size that is wanted; then use SUBREGs or
1318 convert_to_mode to get one of the modes we really wanted. */
1320 int_mode = int_mode_for_mode (tmode);
1321 if (int_mode == BLKmode)
1322 int_mode = int_mode_for_mode (mode);
1323 if (int_mode == BLKmode)
1324 abort (); /* Should probably push op0 out to memory and then
1327 /* OFFSET is the number of words or bytes (UNIT says which)
1328 from STR_RTX to the first word or byte containing part of the field. */
1330 if (GET_CODE (op0) != MEM)
1333 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1335 if (GET_CODE (op0) != REG)
1336 op0 = copy_to_reg (op0);
1337 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1338 op0, (offset * UNITS_PER_WORD));
1343 op0 = protect_from_queue (str_rtx, 1);
1345 /* Now OFFSET is nonzero only for memory operands. */
1350 && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1351 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1352 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1354 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1355 rtx bitsize_rtx, bitpos_rtx;
1356 rtx last = get_last_insn ();
1358 rtx xtarget = target;
1359 rtx xspec_target = spec_target;
1360 rtx xspec_target_subreg = spec_target_subreg;
1362 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1364 if (GET_CODE (xop0) == MEM)
1366 int save_volatile_ok = volatile_ok;
1369 /* Is the memory operand acceptable? */
1370 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1371 (xop0, GET_MODE (xop0))))
1373 /* No, load into a reg and extract from there. */
1374 enum machine_mode bestmode;
1376 /* Get the mode to use for inserting into this field. If
1377 OP0 is BLKmode, get the smallest mode consistent with the
1378 alignment. If OP0 is a non-BLKmode object that is no
1379 wider than MAXMODE, use its mode. Otherwise, use the
1380 smallest mode containing the field. */
1382 if (GET_MODE (xop0) == BLKmode
1383 || (GET_MODE_SIZE (GET_MODE (op0))
1384 > GET_MODE_SIZE (maxmode)))
1385 bestmode = get_best_mode (bitsize, bitnum,
1386 MEM_ALIGN (xop0), maxmode,
1387 MEM_VOLATILE_P (xop0));
1389 bestmode = GET_MODE (xop0);
1391 if (bestmode == VOIDmode
1392 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1393 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1396 /* Compute offset as multiple of this unit,
1397 counting in bytes. */
1398 unit = GET_MODE_BITSIZE (bestmode);
1399 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1400 xbitpos = bitnum % unit;
1401 xop0 = adjust_address (xop0, bestmode, xoffset);
1403 /* Fetch it to a register in that size. */
1404 xop0 = force_reg (bestmode, xop0);
1406 /* XBITPOS counts within UNIT, which is what is expected. */
1409 /* Get ref to first byte containing part of the field. */
1410 xop0 = adjust_address (xop0, byte_mode, xoffset);
1412 volatile_ok = save_volatile_ok;
1415 /* If op0 is a register, we need it in MAXMODE (which is usually
1416 SImode). to make it acceptable to the format of extzv. */
1417 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1419 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1420 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1422 /* On big-endian machines, we count bits from the most significant.
1423 If the bit field insn does not, we must invert. */
1424 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1425 xbitpos = unit - bitsize - xbitpos;
1427 /* Now convert from counting within UNIT to counting in MAXMODE. */
1428 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1429 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1431 unit = GET_MODE_BITSIZE (maxmode);
1434 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1435 xtarget = xspec_target = gen_reg_rtx (tmode);
1437 if (GET_MODE (xtarget) != maxmode)
1439 if (GET_CODE (xtarget) == REG)
1441 int wider = (GET_MODE_SIZE (maxmode)
1442 > GET_MODE_SIZE (GET_MODE (xtarget)));
1443 xtarget = gen_lowpart (maxmode, xtarget);
1445 xspec_target_subreg = xtarget;
1448 xtarget = gen_reg_rtx (maxmode);
1451 /* If this machine's extzv insists on a register target,
1452 make sure we have one. */
1453 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1454 (xtarget, maxmode)))
1455 xtarget = gen_reg_rtx (maxmode);
1457 bitsize_rtx = GEN_INT (bitsize);
1458 bitpos_rtx = GEN_INT (xbitpos);
1460 pat = gen_extzv (protect_from_queue (xtarget, 1),
1461 xop0, bitsize_rtx, bitpos_rtx);
1466 spec_target = xspec_target;
1467 spec_target_subreg = xspec_target_subreg;
1471 delete_insns_since (last);
1472 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1478 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1484 && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1485 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1486 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1488 int xbitpos = bitpos, xoffset = offset;
1489 rtx bitsize_rtx, bitpos_rtx;
1490 rtx last = get_last_insn ();
1491 rtx xop0 = op0, xtarget = target;
1492 rtx xspec_target = spec_target;
1493 rtx xspec_target_subreg = spec_target_subreg;
1495 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1497 if (GET_CODE (xop0) == MEM)
1499 /* Is the memory operand acceptable? */
1500 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1501 (xop0, GET_MODE (xop0))))
1503 /* No, load into a reg and extract from there. */
1504 enum machine_mode bestmode;
1506 /* Get the mode to use for inserting into this field. If
1507 OP0 is BLKmode, get the smallest mode consistent with the
1508 alignment. If OP0 is a non-BLKmode object that is no
1509 wider than MAXMODE, use its mode. Otherwise, use the
1510 smallest mode containing the field. */
1512 if (GET_MODE (xop0) == BLKmode
1513 || (GET_MODE_SIZE (GET_MODE (op0))
1514 > GET_MODE_SIZE (maxmode)))
1515 bestmode = get_best_mode (bitsize, bitnum,
1516 MEM_ALIGN (xop0), maxmode,
1517 MEM_VOLATILE_P (xop0));
1519 bestmode = GET_MODE (xop0);
1521 if (bestmode == VOIDmode
1522 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1523 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1526 /* Compute offset as multiple of this unit,
1527 counting in bytes. */
1528 unit = GET_MODE_BITSIZE (bestmode);
1529 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1530 xbitpos = bitnum % unit;
1531 xop0 = adjust_address (xop0, bestmode, xoffset);
1533 /* Fetch it to a register in that size. */
1534 xop0 = force_reg (bestmode, xop0);
1536 /* XBITPOS counts within UNIT, which is what is expected. */
1539 /* Get ref to first byte containing part of the field. */
1540 xop0 = adjust_address (xop0, byte_mode, xoffset);
1543 /* If op0 is a register, we need it in MAXMODE (which is usually
1544 SImode) to make it acceptable to the format of extv. */
1545 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1547 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1548 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1550 /* On big-endian machines, we count bits from the most significant.
1551 If the bit field insn does not, we must invert. */
1552 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1553 xbitpos = unit - bitsize - xbitpos;
1555 /* XBITPOS counts within a size of UNIT.
1556 Adjust to count within a size of MAXMODE. */
1557 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1558 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1560 unit = GET_MODE_BITSIZE (maxmode);
1563 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1564 xtarget = xspec_target = gen_reg_rtx (tmode);
1566 if (GET_MODE (xtarget) != maxmode)
1568 if (GET_CODE (xtarget) == REG)
1570 int wider = (GET_MODE_SIZE (maxmode)
1571 > GET_MODE_SIZE (GET_MODE (xtarget)));
1572 xtarget = gen_lowpart (maxmode, xtarget);
1574 xspec_target_subreg = xtarget;
1577 xtarget = gen_reg_rtx (maxmode);
1580 /* If this machine's extv insists on a register target,
1581 make sure we have one. */
1582 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1583 (xtarget, maxmode)))
1584 xtarget = gen_reg_rtx (maxmode);
1586 bitsize_rtx = GEN_INT (bitsize);
1587 bitpos_rtx = GEN_INT (xbitpos);
1589 pat = gen_extv (protect_from_queue (xtarget, 1),
1590 xop0, bitsize_rtx, bitpos_rtx);
1595 spec_target = xspec_target;
1596 spec_target_subreg = xspec_target_subreg;
1600 delete_insns_since (last);
1601 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1607 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1610 if (target == spec_target)
1612 if (target == spec_target_subreg)
1614 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1616 /* If the target mode is floating-point, first convert to the
1617 integer mode of that size and then access it as a floating-point
1618 value via a SUBREG. */
1619 if (GET_MODE_CLASS (tmode) != MODE_INT
1620 && GET_MODE_CLASS (tmode) != MODE_PARTIAL_INT)
1622 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1625 return gen_lowpart (tmode, target);
1628 return convert_to_mode (tmode, target, unsignedp);
1633 /* Extract a bit field using shifts and boolean operations
1634 Returns an rtx to represent the value.
1635 OP0 addresses a register (word) or memory (byte).
1636 BITPOS says which bit within the word or byte the bit field starts in.
1637 OFFSET says how many bytes farther the bit field starts;
1638 it is 0 if OP0 is a register.
1639 BITSIZE says how many bits long the bit field is.
1640 (If OP0 is a register, it may be narrower than a full word,
1641 but BITPOS still counts within a full word,
1642 which is significant on bigendian machines.)
1644 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1645 If TARGET is nonzero, attempts to store the value there
1646 and return TARGET, but this is not guaranteed.
1647 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1650 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1651 unsigned HOST_WIDE_INT offset,
1652 unsigned HOST_WIDE_INT bitsize,
1653 unsigned HOST_WIDE_INT bitpos, rtx target,
1656 unsigned int total_bits = BITS_PER_WORD;
1657 enum machine_mode mode;
1659 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1661 /* Special treatment for a bit field split across two registers. */
1662 if (bitsize + bitpos > BITS_PER_WORD)
1663 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1667 /* Get the proper mode to use for this field. We want a mode that
1668 includes the entire field. If such a mode would be larger than
1669 a word, we won't be doing the extraction the normal way. */
1671 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1672 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1674 if (mode == VOIDmode)
1675 /* The only way this should occur is if the field spans word
1677 return extract_split_bit_field (op0, bitsize,
1678 bitpos + offset * BITS_PER_UNIT,
1681 total_bits = GET_MODE_BITSIZE (mode);
1683 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1684 be in the range 0 to total_bits-1, and put any excess bytes in
1686 if (bitpos >= total_bits)
1688 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1689 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1693 /* Get ref to an aligned byte, halfword, or word containing the field.
1694 Adjust BITPOS to be position within a word,
1695 and OFFSET to be the offset of that word.
1696 Then alter OP0 to refer to that word. */
1697 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1698 offset -= (offset % (total_bits / BITS_PER_UNIT));
1699 op0 = adjust_address (op0, mode, offset);
1702 mode = GET_MODE (op0);
1704 if (BYTES_BIG_ENDIAN)
1705 /* BITPOS is the distance between our msb and that of OP0.
1706 Convert it to the distance from the lsb. */
1707 bitpos = total_bits - bitsize - bitpos;
1709 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1710 We have reduced the big-endian case to the little-endian case. */
1716 /* If the field does not already start at the lsb,
1717 shift it so it does. */
1718 tree amount = build_int_2 (bitpos, 0);
1719 /* Maybe propagate the target for the shift. */
1720 /* But not if we will return it--could confuse integrate.c. */
1721 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1722 && !REG_FUNCTION_VALUE_P (target)
1724 if (tmode != mode) subtarget = 0;
1725 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1727 /* Convert the value to the desired mode. */
1729 op0 = convert_to_mode (tmode, op0, 1);
1731 /* Unless the msb of the field used to be the msb when we shifted,
1732 mask out the upper bits. */
1734 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1735 return expand_binop (GET_MODE (op0), and_optab, op0,
1736 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1737 target, 1, OPTAB_LIB_WIDEN);
1741 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1742 then arithmetic-shift its lsb to the lsb of the word. */
1743 op0 = force_reg (mode, op0);
1747 /* Find the narrowest integer mode that contains the field. */
1749 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1750 mode = GET_MODE_WIDER_MODE (mode))
1751 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1753 op0 = convert_to_mode (mode, op0, 0);
1757 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1760 = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1761 /* Maybe propagate the target for the shift. */
1762 /* But not if we will return the result--could confuse integrate.c. */
1763 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1764 && ! REG_FUNCTION_VALUE_P (target)
1766 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1769 return expand_shift (RSHIFT_EXPR, mode, op0,
1770 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1774 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1775 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1776 complement of that if COMPLEMENT. The mask is truncated if
1777 necessary to the width of mode MODE. The mask is zero-extended if
1778 BITSIZE+BITPOS is too small for MODE. */
1781 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1783 HOST_WIDE_INT masklow, maskhigh;
1787 else if (bitpos < HOST_BITS_PER_WIDE_INT)
1788 masklow = (HOST_WIDE_INT) -1 << bitpos;
1792 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1793 masklow &= ((unsigned HOST_WIDE_INT) -1
1794 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1796 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1799 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1803 else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1804 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1805 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1811 maskhigh = ~maskhigh;
1815 return immed_double_const (masklow, maskhigh, mode);
1818 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1819 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1822 lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize)
1824 unsigned HOST_WIDE_INT v = INTVAL (value);
1825 HOST_WIDE_INT low, high;
1827 if (bitsize < HOST_BITS_PER_WIDE_INT)
1828 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1830 if (bitpos < HOST_BITS_PER_WIDE_INT)
1833 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1838 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1841 return immed_double_const (low, high, mode);
1844 /* Extract a bit field that is split across two words
1845 and return an RTX for the result.
1847 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1848 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1849 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1852 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1853 unsigned HOST_WIDE_INT bitpos, int unsignedp)
1856 unsigned int bitsdone = 0;
1857 rtx result = NULL_RTX;
1860 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1862 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1863 unit = BITS_PER_WORD;
1865 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1867 while (bitsdone < bitsize)
1869 unsigned HOST_WIDE_INT thissize;
1871 unsigned HOST_WIDE_INT thispos;
1872 unsigned HOST_WIDE_INT offset;
1874 offset = (bitpos + bitsdone) / unit;
1875 thispos = (bitpos + bitsdone) % unit;
1877 /* THISSIZE must not overrun a word boundary. Otherwise,
1878 extract_fixed_bit_field will call us again, and we will mutually
1880 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1881 thissize = MIN (thissize, unit - thispos);
1883 /* If OP0 is a register, then handle OFFSET here.
1885 When handling multiword bitfields, extract_bit_field may pass
1886 down a word_mode SUBREG of a larger REG for a bitfield that actually
1887 crosses a word boundary. Thus, for a SUBREG, we must find
1888 the current word starting from the base register. */
1889 if (GET_CODE (op0) == SUBREG)
1891 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1892 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1893 GET_MODE (SUBREG_REG (op0)));
1896 else if (GET_CODE (op0) == REG)
1898 word = operand_subword_force (op0, offset, GET_MODE (op0));
1904 /* Extract the parts in bit-counting order,
1905 whose meaning is determined by BYTES_PER_UNIT.
1906 OFFSET is in UNITs, and UNIT is in bits.
1907 extract_fixed_bit_field wants offset in bytes. */
1908 part = extract_fixed_bit_field (word_mode, word,
1909 offset * unit / BITS_PER_UNIT,
1910 thissize, thispos, 0, 1);
1911 bitsdone += thissize;
1913 /* Shift this part into place for the result. */
1914 if (BYTES_BIG_ENDIAN)
1916 if (bitsize != bitsdone)
1917 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1918 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1922 if (bitsdone != thissize)
1923 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1924 build_int_2 (bitsdone - thissize, 0), 0, 1);
1930 /* Combine the parts with bitwise or. This works
1931 because we extracted each part as an unsigned bit field. */
1932 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1938 /* Unsigned bit field: we are done. */
1941 /* Signed bit field: sign-extend with two arithmetic shifts. */
1942 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1943 build_int_2 (BITS_PER_WORD - bitsize, 0),
1945 return expand_shift (RSHIFT_EXPR, word_mode, result,
1946 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1949 /* Add INC into TARGET. */
1952 expand_inc (rtx target, rtx inc)
1954 rtx value = expand_binop (GET_MODE (target), add_optab,
1956 target, 0, OPTAB_LIB_WIDEN);
1957 if (value != target)
1958 emit_move_insn (target, value);
1961 /* Subtract DEC from TARGET. */
1964 expand_dec (rtx target, rtx dec)
1966 rtx value = expand_binop (GET_MODE (target), sub_optab,
1968 target, 0, OPTAB_LIB_WIDEN);
1969 if (value != target)
1970 emit_move_insn (target, value);
1973 /* Output a shift instruction for expression code CODE,
1974 with SHIFTED being the rtx for the value to shift,
1975 and AMOUNT the tree for the amount to shift by.
1976 Store the result in the rtx TARGET, if that is convenient.
1977 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1978 Return the rtx for where the value is. */
1981 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
1982 tree amount, rtx target, int unsignedp)
1985 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1986 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1989 /* Previously detected shift-counts computed by NEGATE_EXPR
1990 and shifted in the other direction; but that does not work
1993 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
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);
2007 if (op1 == const0_rtx)
2010 for (try = 0; temp == 0 && try < 3; try++)
2012 enum optab_methods methods;
2015 methods = OPTAB_DIRECT;
2017 methods = OPTAB_WIDEN;
2019 methods = OPTAB_LIB_WIDEN;
2023 /* Widening does not work for rotation. */
2024 if (methods == OPTAB_WIDEN)
2026 else if (methods == OPTAB_LIB_WIDEN)
2028 /* If we have been unable to open-code this by a rotation,
2029 do it as the IOR of two shifts. I.e., to rotate A
2030 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
2031 where C is the bitsize of A.
2033 It is theoretically possible that the target machine might
2034 not be able to perform either shift and hence we would
2035 be making two libcalls rather than just the one for the
2036 shift (similarly if IOR could not be done). We will allow
2037 this extremely unlikely lossage to avoid complicating the
2040 rtx subtarget = target == shifted ? 0 : target;
2042 tree type = TREE_TYPE (amount);
2043 tree new_amount = make_tree (type, op1);
2045 = fold (build (MINUS_EXPR, type,
2047 build_int_2 (GET_MODE_BITSIZE (mode),
2051 shifted = force_reg (mode, shifted);
2053 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2054 mode, shifted, new_amount, subtarget, 1);
2055 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2056 mode, shifted, other_amount, 0, 1);
2057 return expand_binop (mode, ior_optab, temp, temp1, target,
2058 unsignedp, methods);
2061 temp = expand_binop (mode,
2062 left ? rotl_optab : rotr_optab,
2063 shifted, op1, target, unsignedp, methods);
2065 /* If we don't have the rotate, but we are rotating by a constant
2066 that is in range, try a rotate in the opposite direction. */
2068 if (temp == 0 && GET_CODE (op1) == CONST_INT
2070 && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
2071 temp = expand_binop (mode,
2072 left ? rotr_optab : rotl_optab,
2074 GEN_INT (GET_MODE_BITSIZE (mode)
2076 target, unsignedp, methods);
2079 temp = expand_binop (mode,
2080 left ? ashl_optab : lshr_optab,
2081 shifted, op1, target, unsignedp, methods);
2083 /* Do arithmetic shifts.
2084 Also, if we are going to widen the operand, we can just as well
2085 use an arithmetic right-shift instead of a logical one. */
2086 if (temp == 0 && ! rotate
2087 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2089 enum optab_methods methods1 = methods;
2091 /* If trying to widen a log shift to an arithmetic shift,
2092 don't accept an arithmetic shift of the same size. */
2094 methods1 = OPTAB_MUST_WIDEN;
2096 /* Arithmetic shift */
2098 temp = expand_binop (mode,
2099 left ? ashl_optab : ashr_optab,
2100 shifted, op1, target, unsignedp, methods1);
2103 /* We used to try extzv here for logical right shifts, but that was
2104 only useful for one machine, the VAX, and caused poor code
2105 generation there for lshrdi3, so the code was deleted and a
2106 define_expand for lshrsi3 was added to vax.md. */
2114 enum alg_code { alg_zero, alg_m, alg_shift,
2115 alg_add_t_m2, alg_sub_t_m2,
2116 alg_add_factor, alg_sub_factor,
2117 alg_add_t2_m, alg_sub_t2_m,
2118 alg_add, alg_subtract, alg_factor, alg_shiftop };
2120 /* This structure records a sequence of operations.
2121 `ops' is the number of operations recorded.
2122 `cost' is their total cost.
2123 The operations are stored in `op' and the corresponding
2124 logarithms of the integer coefficients in `log'.
2126 These are the operations:
2127 alg_zero total := 0;
2128 alg_m total := multiplicand;
2129 alg_shift total := total * coeff
2130 alg_add_t_m2 total := total + multiplicand * coeff;
2131 alg_sub_t_m2 total := total - multiplicand * coeff;
2132 alg_add_factor total := total * coeff + total;
2133 alg_sub_factor total := total * coeff - total;
2134 alg_add_t2_m total := total * coeff + multiplicand;
2135 alg_sub_t2_m total := total * coeff - multiplicand;
2137 The first operand must be either alg_zero or alg_m. */
2143 /* The size of the OP and LOG fields are not directly related to the
2144 word size, but the worst-case algorithms will be if we have few
2145 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2146 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2147 in total wordsize operations. */
2148 enum alg_code op[MAX_BITS_PER_WORD];
2149 char log[MAX_BITS_PER_WORD];
2152 /* Indicates the type of fixup needed after a constant multiplication.
2153 BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2154 the result should be negated, and ADD_VARIANT means that the
2155 multiplicand should be added to the result. */
2156 enum mult_variant {basic_variant, negate_variant, add_variant};
2158 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT, int);
2159 static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT,
2160 struct algorithm *, enum mult_variant *, int);
2161 static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx,
2162 const struct algorithm *, enum mult_variant);
2163 static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int,
2164 int, unsigned HOST_WIDE_INT *,
2166 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2167 static rtx extract_high_half (enum machine_mode, rtx);
2168 static rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx,
2170 /* Compute and return the best algorithm for multiplying by T.
2171 The algorithm must cost less than cost_limit
2172 If retval.cost >= COST_LIMIT, no algorithm was found and all
2173 other field of the returned struct are undefined. */
2176 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2180 struct algorithm *alg_in, *best_alg;
2182 unsigned HOST_WIDE_INT q;
2184 /* Indicate that no algorithm is yet found. If no algorithm
2185 is found, this value will be returned and indicate failure. */
2186 alg_out->cost = cost_limit;
2188 if (cost_limit <= 0)
2191 /* t == 1 can be done in zero cost. */
2196 alg_out->op[0] = alg_m;
2200 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2204 if (zero_cost >= cost_limit)
2209 alg_out->cost = zero_cost;
2210 alg_out->op[0] = alg_zero;
2215 /* We'll be needing a couple extra algorithm structures now. */
2217 alg_in = alloca (sizeof (struct algorithm));
2218 best_alg = alloca (sizeof (struct algorithm));
2220 /* If we have a group of zero bits at the low-order part of T, try
2221 multiplying by the remaining bits and then doing a shift. */
2225 m = floor_log2 (t & -t); /* m = number of low zero bits */
2226 if (m < BITS_PER_WORD)
2229 cost = shift_cost[m];
2230 synth_mult (alg_in, q, cost_limit - cost);
2232 cost += alg_in->cost;
2233 if (cost < cost_limit)
2235 struct algorithm *x;
2236 x = alg_in, alg_in = best_alg, best_alg = x;
2237 best_alg->log[best_alg->ops] = m;
2238 best_alg->op[best_alg->ops] = alg_shift;
2244 /* If we have an odd number, add or subtract one. */
2247 unsigned HOST_WIDE_INT w;
2249 for (w = 1; (w & t) != 0; w <<= 1)
2251 /* If T was -1, then W will be zero after the loop. This is another
2252 case where T ends with ...111. Handling this with (T + 1) and
2253 subtract 1 produces slightly better code and results in algorithm
2254 selection much faster than treating it like the ...0111 case
2258 /* Reject the case where t is 3.
2259 Thus we prefer addition in that case. */
2262 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2265 synth_mult (alg_in, t + 1, cost_limit - cost);
2267 cost += alg_in->cost;
2268 if (cost < cost_limit)
2270 struct algorithm *x;
2271 x = alg_in, alg_in = best_alg, best_alg = x;
2272 best_alg->log[best_alg->ops] = 0;
2273 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2279 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2282 synth_mult (alg_in, t - 1, cost_limit - cost);
2284 cost += alg_in->cost;
2285 if (cost < cost_limit)
2287 struct algorithm *x;
2288 x = alg_in, alg_in = best_alg, best_alg = x;
2289 best_alg->log[best_alg->ops] = 0;
2290 best_alg->op[best_alg->ops] = alg_add_t_m2;
2296 /* Look for factors of t of the form
2297 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2298 If we find such a factor, we can multiply by t using an algorithm that
2299 multiplies by q, shift the result by m and add/subtract it to itself.
2301 We search for large factors first and loop down, even if large factors
2302 are less probable than small; if we find a large factor we will find a
2303 good sequence quickly, and therefore be able to prune (by decreasing
2304 COST_LIMIT) the search. */
2306 for (m = floor_log2 (t - 1); m >= 2; m--)
2308 unsigned HOST_WIDE_INT d;
2310 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2311 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2313 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2314 synth_mult (alg_in, t / d, cost_limit - cost);
2316 cost += alg_in->cost;
2317 if (cost < cost_limit)
2319 struct algorithm *x;
2320 x = alg_in, alg_in = best_alg, best_alg = x;
2321 best_alg->log[best_alg->ops] = m;
2322 best_alg->op[best_alg->ops] = alg_add_factor;
2325 /* Other factors will have been taken care of in the recursion. */
2329 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2330 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2332 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2333 synth_mult (alg_in, t / d, cost_limit - cost);
2335 cost += alg_in->cost;
2336 if (cost < cost_limit)
2338 struct algorithm *x;
2339 x = alg_in, alg_in = best_alg, best_alg = x;
2340 best_alg->log[best_alg->ops] = m;
2341 best_alg->op[best_alg->ops] = alg_sub_factor;
2348 /* Try shift-and-add (load effective address) instructions,
2349 i.e. do a*3, a*5, a*9. */
2355 if (m >= 0 && m < BITS_PER_WORD)
2357 cost = shiftadd_cost[m];
2358 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2360 cost += alg_in->cost;
2361 if (cost < cost_limit)
2363 struct algorithm *x;
2364 x = alg_in, alg_in = best_alg, best_alg = x;
2365 best_alg->log[best_alg->ops] = m;
2366 best_alg->op[best_alg->ops] = alg_add_t2_m;
2374 if (m >= 0 && m < BITS_PER_WORD)
2376 cost = shiftsub_cost[m];
2377 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2379 cost += alg_in->cost;
2380 if (cost < cost_limit)
2382 struct algorithm *x;
2383 x = alg_in, alg_in = best_alg, best_alg = x;
2384 best_alg->log[best_alg->ops] = m;
2385 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2391 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2392 we have not found any algorithm. */
2393 if (cost_limit == alg_out->cost)
2396 /* If we are getting a too long sequence for `struct algorithm'
2397 to record, make this search fail. */
2398 if (best_alg->ops == MAX_BITS_PER_WORD)
2401 /* Copy the algorithm from temporary space to the space at alg_out.
2402 We avoid using structure assignment because the majority of
2403 best_alg is normally undefined, and this is a critical function. */
2404 alg_out->ops = best_alg->ops + 1;
2405 alg_out->cost = cost_limit;
2406 memcpy (alg_out->op, best_alg->op,
2407 alg_out->ops * sizeof *alg_out->op);
2408 memcpy (alg_out->log, best_alg->log,
2409 alg_out->ops * sizeof *alg_out->log);
2412 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2413 Try three variations:
2415 - a shift/add sequence based on VAL itself
2416 - a shift/add sequence based on -VAL, followed by a negation
2417 - a shift/add sequence based on VAL - 1, followed by an addition.
2419 Return true if the cheapest of these cost less than MULT_COST,
2420 describing the algorithm in *ALG and final fixup in *VARIANT. */
2423 choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val,
2424 struct algorithm *alg, enum mult_variant *variant,
2427 struct algorithm alg2;
2429 *variant = basic_variant;
2430 synth_mult (alg, val, mult_cost);
2432 /* This works only if the inverted value actually fits in an
2434 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2436 synth_mult (&alg2, -val, MIN (alg->cost, mult_cost) - negate_cost);
2437 alg2.cost += negate_cost;
2438 if (alg2.cost < alg->cost)
2439 *alg = alg2, *variant = negate_variant;
2442 /* This proves very useful for division-by-constant. */
2443 synth_mult (&alg2, val - 1, MIN (alg->cost, mult_cost) - add_cost);
2444 alg2.cost += add_cost;
2445 if (alg2.cost < alg->cost)
2446 *alg = alg2, *variant = add_variant;
2448 return alg->cost < mult_cost;
2451 /* A subroutine of expand_mult, used for constant multiplications.
2452 Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2453 convenient. Use the shift/add sequence described by ALG and apply
2454 the final fixup specified by VARIANT. */
2457 expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val,
2458 rtx target, const struct algorithm *alg,
2459 enum mult_variant variant)
2461 HOST_WIDE_INT val_so_far;
2462 rtx insn, accum, tem;
2464 enum machine_mode nmode;
2466 /* op0 must be register to make mult_cost match the precomputed
2467 shiftadd_cost array. */
2468 op0 = protect_from_queue (op0, 0);
2470 /* Avoid referencing memory over and over.
2471 For speed, but also for correctness when mem is volatile. */
2472 if (GET_CODE (op0) == MEM)
2473 op0 = force_reg (mode, op0);
2475 /* ACCUM starts out either as OP0 or as a zero, depending on
2476 the first operation. */
2478 if (alg->op[0] == alg_zero)
2480 accum = copy_to_mode_reg (mode, const0_rtx);
2483 else if (alg->op[0] == alg_m)
2485 accum = copy_to_mode_reg (mode, op0);
2491 for (opno = 1; opno < alg->ops; opno++)
2493 int log = alg->log[opno];
2494 int preserve = preserve_subexpressions_p ();
2495 rtx shift_subtarget = preserve ? 0 : accum;
2497 = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2500 rtx accum_target = preserve ? 0 : accum;
2502 switch (alg->op[opno])
2505 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2506 build_int_2 (log, 0), NULL_RTX, 0);
2511 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2512 build_int_2 (log, 0), NULL_RTX, 0);
2513 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2514 add_target ? add_target : accum_target);
2515 val_so_far += (HOST_WIDE_INT) 1 << log;
2519 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2520 build_int_2 (log, 0), NULL_RTX, 0);
2521 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2522 add_target ? add_target : accum_target);
2523 val_so_far -= (HOST_WIDE_INT) 1 << log;
2527 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2528 build_int_2 (log, 0), shift_subtarget,
2530 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2531 add_target ? add_target : accum_target);
2532 val_so_far = (val_so_far << log) + 1;
2536 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2537 build_int_2 (log, 0), shift_subtarget, 0);
2538 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2539 add_target ? add_target : accum_target);
2540 val_so_far = (val_so_far << log) - 1;
2543 case alg_add_factor:
2544 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2545 build_int_2 (log, 0), NULL_RTX, 0);
2546 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2547 add_target ? add_target : accum_target);
2548 val_so_far += val_so_far << log;
2551 case alg_sub_factor:
2552 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2553 build_int_2 (log, 0), NULL_RTX, 0);
2554 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2555 (add_target ? add_target
2556 : preserve ? 0 : tem));
2557 val_so_far = (val_so_far << log) - val_so_far;
2564 /* Write a REG_EQUAL note on the last insn so that we can cse
2565 multiplication sequences. Note that if ACCUM is a SUBREG,
2566 we've set the inner register and must properly indicate
2569 tem = op0, nmode = mode;
2570 if (GET_CODE (accum) == SUBREG)
2572 nmode = GET_MODE (SUBREG_REG (accum));
2573 tem = gen_lowpart (nmode, op0);
2576 insn = get_last_insn ();
2577 set_unique_reg_note (insn, REG_EQUAL,
2578 gen_rtx_MULT (nmode, tem, GEN_INT (val_so_far)));
2581 if (variant == negate_variant)
2583 val_so_far = -val_so_far;
2584 accum = expand_unop (mode, neg_optab, accum, target, 0);
2586 else if (variant == add_variant)
2588 val_so_far = val_so_far + 1;
2589 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2592 if (val != val_so_far)
2598 /* Perform a multiplication and return an rtx for the result.
2599 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2600 TARGET is a suggestion for where to store the result (an rtx).
2602 We check specially for a constant integer as OP1.
2603 If you want this check for OP0 as well, then before calling
2604 you should swap the two operands if OP0 would be constant. */
2607 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
2610 rtx const_op1 = op1;
2611 enum mult_variant variant;
2612 struct algorithm algorithm;
2614 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2615 less than or equal in size to `unsigned int' this doesn't matter.
2616 If the mode is larger than `unsigned int', then synth_mult works only
2617 if the constant value exactly fits in an `unsigned int' without any
2618 truncation. This means that multiplying by negative values does
2619 not work; results are off by 2^32 on a 32 bit machine. */
2621 /* If we are multiplying in DImode, it may still be a win
2622 to try to work with shifts and adds. */
2623 if (GET_CODE (op1) == CONST_DOUBLE
2624 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2625 && HOST_BITS_PER_INT >= BITS_PER_WORD
2626 && CONST_DOUBLE_HIGH (op1) == 0)
2627 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2628 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2629 && GET_CODE (op1) == CONST_INT
2630 && INTVAL (op1) < 0)
2633 /* We used to test optimize here, on the grounds that it's better to
2634 produce a smaller program when -O is not used.
2635 But this causes such a terrible slowdown sometimes
2636 that it seems better to use synth_mult always. */
2638 if (const_op1 && GET_CODE (const_op1) == CONST_INT
2639 && (unsignedp || !flag_trapv))
2641 int mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2642 mult_cost = MIN (12 * add_cost, mult_cost);
2644 if (choose_mult_variant (mode, INTVAL (const_op1), &algorithm, &variant,
2646 return expand_mult_const (mode, op0, INTVAL (const_op1), target,
2647 &algorithm, variant);
2650 if (GET_CODE (op0) == CONST_DOUBLE)
2657 /* Expand x*2.0 as x+x. */
2658 if (GET_CODE (op1) == CONST_DOUBLE
2659 && GET_MODE_CLASS (mode) == MODE_FLOAT)
2662 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
2664 if (REAL_VALUES_EQUAL (d, dconst2))
2666 op0 = force_reg (GET_MODE (op0), op0);
2667 return expand_binop (mode, add_optab, op0, op0,
2668 target, unsignedp, OPTAB_LIB_WIDEN);
2672 /* This used to use umul_optab if unsigned, but for non-widening multiply
2673 there is no difference between signed and unsigned. */
2674 op0 = expand_binop (mode,
2676 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2677 ? smulv_optab : smul_optab,
2678 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2684 /* Return the smallest n such that 2**n >= X. */
2687 ceil_log2 (unsigned HOST_WIDE_INT x)
2689 return floor_log2 (x - 1) + 1;
2692 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2693 replace division by D, and put the least significant N bits of the result
2694 in *MULTIPLIER_PTR and return the most significant bit.
2696 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2697 needed precision is in PRECISION (should be <= N).
2699 PRECISION should be as small as possible so this function can choose
2700 multiplier more freely.
2702 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2703 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2705 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2706 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2709 unsigned HOST_WIDE_INT
2710 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
2711 unsigned HOST_WIDE_INT *multiplier_ptr,
2712 int *post_shift_ptr, int *lgup_ptr)
2714 HOST_WIDE_INT mhigh_hi, mlow_hi;
2715 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2716 int lgup, post_shift;
2718 unsigned HOST_WIDE_INT nl, dummy1;
2719 HOST_WIDE_INT nh, dummy2;
2721 /* lgup = ceil(log2(divisor)); */
2722 lgup = ceil_log2 (d);
2728 pow2 = n + lgup - precision;
2730 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2732 /* We could handle this with some effort, but this case is much better
2733 handled directly with a scc insn, so rely on caller using that. */
2737 /* mlow = 2^(N + lgup)/d */
2738 if (pow >= HOST_BITS_PER_WIDE_INT)
2740 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2746 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2748 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2749 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2751 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2752 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2753 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2755 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2756 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2757 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2759 if (mhigh_hi && nh - d >= d)
2761 if (mhigh_hi > 1 || mlow_hi > 1)
2763 /* Assert that mlow < mhigh. */
2764 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2767 /* If precision == N, then mlow, mhigh exceed 2^N
2768 (but they do not exceed 2^(N+1)). */
2770 /* Reduce to lowest terms. */
2771 for (post_shift = lgup; post_shift > 0; post_shift--)
2773 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2774 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2784 *post_shift_ptr = post_shift;
2786 if (n < HOST_BITS_PER_WIDE_INT)
2788 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2789 *multiplier_ptr = mhigh_lo & mask;
2790 return mhigh_lo >= mask;
2794 *multiplier_ptr = mhigh_lo;
2799 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2800 congruent to 1 (mod 2**N). */
2802 static unsigned HOST_WIDE_INT
2803 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
2805 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2807 /* The algorithm notes that the choice y = x satisfies
2808 x*y == 1 mod 2^3, since x is assumed odd.
2809 Each iteration doubles the number of bits of significance in y. */
2811 unsigned HOST_WIDE_INT mask;
2812 unsigned HOST_WIDE_INT y = x;
2815 mask = (n == HOST_BITS_PER_WIDE_INT
2816 ? ~(unsigned HOST_WIDE_INT) 0
2817 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2821 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2827 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2828 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2829 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2830 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2833 The result is put in TARGET if that is convenient.
2835 MODE is the mode of operation. */
2838 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
2839 rtx op1, rtx target, int unsignedp)
2842 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2844 op1 = gen_int_mode (INTVAL (op1), mode);
2845 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2846 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2848 tem = expand_and (mode, tem, op1, NULL_RTX);
2850 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2853 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2854 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2856 tem = expand_and (mode, tem, op0, NULL_RTX);
2857 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2863 /* Subroutine of expand_mult_highpart. Return the MODE high part of OP. */
2866 extract_high_half (enum machine_mode mode, rtx op)
2868 enum machine_mode wider_mode;
2870 if (mode == word_mode)
2871 return gen_highpart (mode, op);
2873 wider_mode = GET_MODE_WIDER_MODE (mode);
2874 op = expand_shift (RSHIFT_EXPR, wider_mode, op,
2875 build_int_2 (GET_MODE_BITSIZE (mode), 0), 0, 1);
2876 return convert_modes (mode, wider_mode, op, 0);
2879 /* Like expand_mult_highpart, but only consider using a multiplication
2880 optab. OP1 is an rtx for the constant operand. */
2883 expand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1,
2884 rtx target, int unsignedp, int max_cost)
2886 rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
2887 enum machine_mode wider_mode;
2892 wider_mode = GET_MODE_WIDER_MODE (mode);
2893 size = GET_MODE_BITSIZE (mode);
2895 /* Firstly, try using a multiplication insn that only generates the needed
2896 high part of the product, and in the sign flavor of unsignedp. */
2897 if (mul_highpart_cost[(int) mode] < max_cost)
2899 moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2900 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
2901 unsignedp, OPTAB_DIRECT);
2906 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2907 Need to adjust the result after the multiplication. */
2908 if (size - 1 < BITS_PER_WORD
2909 && (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost
2912 moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2913 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
2914 unsignedp, OPTAB_DIRECT);
2916 /* We used the wrong signedness. Adjust the result. */
2917 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2921 /* Try widening multiplication. */
2922 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2923 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2924 && mul_widen_cost[(int) wider_mode] < max_cost)
2926 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
2927 unsignedp, OPTAB_WIDEN);
2929 return extract_high_half (mode, tem);
2932 /* Try widening the mode and perform a non-widening multiplication. */
2933 moptab = smul_optab;
2934 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2935 && size - 1 < BITS_PER_WORD
2936 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2938 tem = expand_binop (wider_mode, moptab, op0, op1, 0,
2939 unsignedp, OPTAB_WIDEN);
2941 return extract_high_half (mode, tem);
2944 /* Try widening multiplication of opposite signedness, and adjust. */
2945 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2946 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2947 && size - 1 < BITS_PER_WORD
2948 && (mul_widen_cost[(int) wider_mode]
2949 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2951 tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
2952 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2955 tem = extract_high_half (mode, tem);
2956 /* We used the wrong signedness. Adjust the result. */
2957 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2965 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2966 in TARGET if that is convenient, and return where the result is. If the
2967 operation can not be performed, 0 is returned.
2969 MODE is the mode of operation and result.
2971 UNSIGNEDP nonzero means unsigned multiply.
2973 MAX_COST is the total allowed cost for the expanded RTL. */
2976 expand_mult_highpart (enum machine_mode mode, rtx op0,
2977 unsigned HOST_WIDE_INT cnst1, rtx target,
2978 int unsignedp, int max_cost)
2980 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2982 bool sign_adjust = false;
2983 enum mult_variant variant;
2984 struct algorithm alg;
2987 /* We can't support modes wider than HOST_BITS_PER_INT. */
2988 if (GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT)
2991 op1 = gen_int_mode (cnst1, wider_mode);
2992 cnst1 &= GET_MODE_MASK (mode);
2994 /* We can't optimize modes wider than BITS_PER_WORD.
2995 ??? We might be able to perform double-word arithmetic if
2996 mode == word_mode, however all the cost calculations in
2997 synth_mult etc. assume single-word operations. */
2998 if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
2999 return expand_mult_highpart_optab (mode, op0, op1, target,
3000 unsignedp, max_cost);
3002 extra_cost = shift_cost[GET_MODE_BITSIZE (mode) - 1];
3004 /* Check whether we try to multiply by a negative constant. */
3005 if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3008 extra_cost += add_cost;
3011 /* See whether shift/add multiplication is cheap enough. */
3012 if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3013 max_cost - extra_cost))
3015 /* See whether the specialized multiplication optabs are
3016 cheaper than the shift/add version. */
3017 tem = expand_mult_highpart_optab (mode, op0, op1, target,
3018 unsignedp, alg.cost + extra_cost);
3022 tem = convert_to_mode (wider_mode, op0, unsignedp);
3023 tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3024 tem = extract_high_half (mode, tem);
3026 /* Adjust result for signedness. */
3028 tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3032 return expand_mult_highpart_optab (mode, op0, op1, target,
3033 unsignedp, max_cost);
3036 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3037 if that is convenient, and returning where the result is.
3038 You may request either the quotient or the remainder as the result;
3039 specify REM_FLAG nonzero to get the remainder.
3041 CODE is the expression code for which kind of division this is;
3042 it controls how rounding is done. MODE is the machine mode to use.
3043 UNSIGNEDP nonzero means do unsigned division. */
3045 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3046 and then correct it by or'ing in missing high bits
3047 if result of ANDI is nonzero.
3048 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3049 This could optimize to a bfexts instruction.
3050 But C doesn't use these operations, so their optimizations are
3052 /* ??? For modulo, we don't actually need the highpart of the first product,
3053 the low part will do nicely. And for small divisors, the second multiply
3054 can also be a low-part only multiply or even be completely left out.
3055 E.g. to calculate the remainder of a division by 3 with a 32 bit
3056 multiply, multiply with 0x55555556 and extract the upper two bits;
3057 the result is exact for inputs up to 0x1fffffff.
3058 The input range can be reduced by using cross-sum rules.
3059 For odd divisors >= 3, the following table gives right shift counts
3060 so that if a number is shifted by an integer multiple of the given
3061 amount, the remainder stays the same:
3062 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3063 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3064 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3065 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3066 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3068 Cross-sum rules for even numbers can be derived by leaving as many bits
3069 to the right alone as the divisor has zeros to the right.
3070 E.g. if x is an unsigned 32 bit number:
3071 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3074 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
3077 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3078 rtx op0, rtx op1, rtx target, int unsignedp)
3080 enum machine_mode compute_mode;
3082 rtx quotient = 0, remainder = 0;
3086 optab optab1, optab2;
3087 int op1_is_constant, op1_is_pow2 = 0;
3088 int max_cost, extra_cost;
3089 static HOST_WIDE_INT last_div_const = 0;
3090 static HOST_WIDE_INT ext_op1;
3092 op1_is_constant = GET_CODE (op1) == CONST_INT;
3093 if (op1_is_constant)
3095 ext_op1 = INTVAL (op1);
3097 ext_op1 &= GET_MODE_MASK (mode);
3098 op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3099 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3103 This is the structure of expand_divmod:
3105 First comes code to fix up the operands so we can perform the operations
3106 correctly and efficiently.
3108 Second comes a switch statement with code specific for each rounding mode.
3109 For some special operands this code emits all RTL for the desired
3110 operation, for other cases, it generates only a quotient and stores it in
3111 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
3112 to indicate that it has not done anything.
3114 Last comes code that finishes the operation. If QUOTIENT is set and
3115 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
3116 QUOTIENT is not set, it is computed using trunc rounding.
3118 We try to generate special code for division and remainder when OP1 is a
3119 constant. If |OP1| = 2**n we can use shifts and some other fast
3120 operations. For other values of OP1, we compute a carefully selected
3121 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3124 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3125 half of the product. Different strategies for generating the product are
3126 implemented in expand_mult_highpart.
3128 If what we actually want is the remainder, we generate that by another
3129 by-constant multiplication and a subtraction. */
3131 /* We shouldn't be called with OP1 == const1_rtx, but some of the
3132 code below will malfunction if we are, so check here and handle
3133 the special case if so. */
3134 if (op1 == const1_rtx)
3135 return rem_flag ? const0_rtx : op0;
3137 /* When dividing by -1, we could get an overflow.
3138 negv_optab can handle overflows. */
3139 if (! unsignedp && op1 == constm1_rtx)
3143 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3144 ? negv_optab : neg_optab, op0, target, 0);
3148 /* Don't use the function value register as a target
3149 since we have to read it as well as write it,
3150 and function-inlining gets confused by this. */
3151 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3152 /* Don't clobber an operand while doing a multi-step calculation. */
3153 || ((rem_flag || op1_is_constant)
3154 && (reg_mentioned_p (target, op0)
3155 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
3156 || reg_mentioned_p (target, op1)
3157 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
3160 /* Get the mode in which to perform this computation. Normally it will
3161 be MODE, but sometimes we can't do the desired operation in MODE.
3162 If so, pick a wider mode in which we can do the operation. Convert
3163 to that mode at the start to avoid repeated conversions.
3165 First see what operations we need. These depend on the expression
3166 we are evaluating. (We assume that divxx3 insns exist under the
3167 same conditions that modxx3 insns and that these insns don't normally
3168 fail. If these assumptions are not correct, we may generate less
3169 efficient code in some cases.)
3171 Then see if we find a mode in which we can open-code that operation
3172 (either a division, modulus, or shift). Finally, check for the smallest
3173 mode for which we can do the operation with a library call. */
3175 /* We might want to refine this now that we have division-by-constant
3176 optimization. Since expand_mult_highpart tries so many variants, it is
3177 not straightforward to generalize this. Maybe we should make an array
3178 of possible modes in init_expmed? Save this for GCC 2.7. */
3180 optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3181 ? (unsignedp ? lshr_optab : ashr_optab)
3182 : (unsignedp ? udiv_optab : sdiv_optab));
3183 optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3185 : (unsignedp ? udivmod_optab : sdivmod_optab));
3187 for (compute_mode = mode; compute_mode != VOIDmode;
3188 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3189 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
3190 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
3193 if (compute_mode == VOIDmode)
3194 for (compute_mode = mode; compute_mode != VOIDmode;
3195 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3196 if (optab1->handlers[(int) compute_mode].libfunc
3197 || optab2->handlers[(int) compute_mode].libfunc)
3200 /* If we still couldn't find a mode, use MODE, but we'll probably abort
3202 if (compute_mode == VOIDmode)
3203 compute_mode = mode;
3205 if (target && GET_MODE (target) == compute_mode)
3208 tquotient = gen_reg_rtx (compute_mode);
3210 size = GET_MODE_BITSIZE (compute_mode);
3212 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3213 (mode), and thereby get better code when OP1 is a constant. Do that
3214 later. It will require going over all usages of SIZE below. */
3215 size = GET_MODE_BITSIZE (mode);
3218 /* Only deduct something for a REM if the last divide done was
3219 for a different constant. Then set the constant of the last
3221 max_cost = div_cost[(int) compute_mode]
3222 - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3223 && INTVAL (op1) == last_div_const)
3224 ? mul_cost[(int) compute_mode] + add_cost : 0);
3226 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3228 /* Now convert to the best mode to use. */
3229 if (compute_mode != mode)
3231 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3232 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3234 /* convert_modes may have placed op1 into a register, so we
3235 must recompute the following. */
3236 op1_is_constant = GET_CODE (op1) == CONST_INT;
3237 op1_is_pow2 = (op1_is_constant
3238 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3240 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3243 /* If one of the operands is a volatile MEM, copy it into a register. */
3245 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3246 op0 = force_reg (compute_mode, op0);
3247 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3248 op1 = force_reg (compute_mode, op1);
3250 /* If we need the remainder or if OP1 is constant, we need to
3251 put OP0 in a register in case it has any queued subexpressions. */
3252 if (rem_flag || op1_is_constant)
3253 op0 = force_reg (compute_mode, op0);
3255 last = get_last_insn ();
3257 /* Promote floor rounding to trunc rounding for unsigned operations. */
3260 if (code == FLOOR_DIV_EXPR)
3261 code = TRUNC_DIV_EXPR;
3262 if (code == FLOOR_MOD_EXPR)
3263 code = TRUNC_MOD_EXPR;
3264 if (code == EXACT_DIV_EXPR && op1_is_pow2)
3265 code = TRUNC_DIV_EXPR;
3268 if (op1 != const0_rtx)
3271 case TRUNC_MOD_EXPR:
3272 case TRUNC_DIV_EXPR:
3273 if (op1_is_constant)
3277 unsigned HOST_WIDE_INT mh, ml;
3278 int pre_shift, post_shift;
3280 unsigned HOST_WIDE_INT d = (INTVAL (op1)
3281 & GET_MODE_MASK (compute_mode));
3283 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3285 pre_shift = floor_log2 (d);
3289 = expand_binop (compute_mode, and_optab, op0,
3290 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3294 return gen_lowpart (mode, remainder);
3296 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3297 build_int_2 (pre_shift, 0),
3300 else if (size <= HOST_BITS_PER_WIDE_INT)
3302 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3304 /* Most significant bit of divisor is set; emit an scc
3306 quotient = emit_store_flag (tquotient, GEU, op0, op1,
3307 compute_mode, 1, 1);
3313 /* Find a suitable multiplier and right shift count
3314 instead of multiplying with D. */
3316 mh = choose_multiplier (d, size, size,
3317 &ml, &post_shift, &dummy);
3319 /* If the suggested multiplier is more than SIZE bits,
3320 we can do better for even divisors, using an
3321 initial right shift. */
3322 if (mh != 0 && (d & 1) == 0)
3324 pre_shift = floor_log2 (d & -d);
3325 mh = choose_multiplier (d >> pre_shift, size,
3327 &ml, &post_shift, &dummy);
3338 if (post_shift - 1 >= BITS_PER_WORD)
3341 extra_cost = (shift_cost[post_shift - 1]
3342 + shift_cost[1] + 2 * add_cost);
3343 t1 = expand_mult_highpart (compute_mode, op0, ml,
3345 max_cost - extra_cost);
3348 t2 = force_operand (gen_rtx_MINUS (compute_mode,
3351 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3352 build_int_2 (1, 0), NULL_RTX,1);
3353 t4 = force_operand (gen_rtx_PLUS (compute_mode,
3357 = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3358 build_int_2 (post_shift - 1, 0),
3365 if (pre_shift >= BITS_PER_WORD
3366 || post_shift >= BITS_PER_WORD)
3369 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3370 build_int_2 (pre_shift, 0),
3372 extra_cost = (shift_cost[pre_shift]
3373 + shift_cost[post_shift]);
3374 t2 = expand_mult_highpart (compute_mode, t1, ml,
3376 max_cost - extra_cost);
3380 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3381 build_int_2 (post_shift, 0),
3386 else /* Too wide mode to use tricky code */
3389 insn = get_last_insn ();
3391 && (set = single_set (insn)) != 0
3392 && SET_DEST (set) == quotient)
3393 set_unique_reg_note (insn,
3395 gen_rtx_UDIV (compute_mode, op0, op1));
3397 else /* TRUNC_DIV, signed */
3399 unsigned HOST_WIDE_INT ml;
3400 int lgup, post_shift;
3401 HOST_WIDE_INT d = INTVAL (op1);
3402 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3404 /* n rem d = n rem -d */
3405 if (rem_flag && d < 0)
3408 op1 = gen_int_mode (abs_d, compute_mode);
3414 quotient = expand_unop (compute_mode, neg_optab, op0,
3416 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3418 /* This case is not handled correctly below. */
3419 quotient = emit_store_flag (tquotient, EQ, op0, op1,
3420 compute_mode, 1, 1);
3424 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3425 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap)
3426 /* ??? The cheap metric is computed only for
3427 word_mode. If this operation is wider, this may
3428 not be so. Assume true if the optab has an
3429 expander for this mode. */
3430 && (((rem_flag ? smod_optab : sdiv_optab)
3431 ->handlers[(int) compute_mode].insn_code
3432 != CODE_FOR_nothing)
3433 || (sdivmod_optab->handlers[(int) compute_mode]
3434 .insn_code != CODE_FOR_nothing)))
3436 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3438 lgup = floor_log2 (abs_d);
3439 if (BRANCH_COST < 1 || (abs_d != 2 && BRANCH_COST < 3))
3441 rtx label = gen_label_rtx ();
3444 t1 = copy_to_mode_reg (compute_mode, op0);
3445 do_cmp_and_jump (t1, const0_rtx, GE,
3446 compute_mode, label);
3447 expand_inc (t1, gen_int_mode (abs_d - 1,
3450 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3451 build_int_2 (lgup, 0),
3457 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3458 build_int_2 (size - 1, 0),
3460 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3461 build_int_2 (size - lgup, 0),
3463 t3 = force_operand (gen_rtx_PLUS (compute_mode,
3466 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3467 build_int_2 (lgup, 0),
3471 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
3475 insn = get_last_insn ();
3477 && (set = single_set (insn)) != 0
3478 && SET_DEST (set) == quotient
3479 && abs_d < ((unsigned HOST_WIDE_INT) 1
3480 << (HOST_BITS_PER_WIDE_INT - 1)))
3481 set_unique_reg_note (insn,
3483 gen_rtx_DIV (compute_mode,
3490 quotient = expand_unop (compute_mode, neg_optab,
3491 quotient, quotient, 0);
3494 else if (size <= HOST_BITS_PER_WIDE_INT)
3496 choose_multiplier (abs_d, size, size - 1,
3497 &ml, &post_shift, &lgup);
3498 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3502 if (post_shift >= BITS_PER_WORD
3503 || size - 1 >= BITS_PER_WORD)
3506 extra_cost = (shift_cost[post_shift]
3507 + shift_cost[size - 1] + add_cost);
3508 t1 = expand_mult_highpart (compute_mode, op0, ml,
3510 max_cost - extra_cost);
3513 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3514 build_int_2 (post_shift, 0), NULL_RTX, 0);
3515 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3516 build_int_2 (size - 1, 0), NULL_RTX, 0);
3519 = force_operand (gen_rtx_MINUS (compute_mode,
3524 = force_operand (gen_rtx_MINUS (compute_mode,
3532 if (post_shift >= BITS_PER_WORD
3533 || size - 1 >= BITS_PER_WORD)
3536 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3537 extra_cost = (shift_cost[post_shift]
3538 + shift_cost[size - 1] + 2 * add_cost);
3539 t1 = expand_mult_highpart (compute_mode, op0, ml,
3541 max_cost - extra_cost);
3544 t2 = force_operand (gen_rtx_PLUS (compute_mode,
3547 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3548 build_int_2 (post_shift, 0),
3550 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3551 build_int_2 (size - 1, 0),
3555 = force_operand (gen_rtx_MINUS (compute_mode,
3560 = force_operand (gen_rtx_MINUS (compute_mode,
3565 else /* Too wide mode to use tricky code */
3568 insn = get_last_insn ();
3570 && (set = single_set (insn)) != 0
3571 && SET_DEST (set) == quotient)
3572 set_unique_reg_note (insn,
3574 gen_rtx_DIV (compute_mode, op0, op1));
3579 delete_insns_since (last);
3582 case FLOOR_DIV_EXPR:
3583 case FLOOR_MOD_EXPR:
3584 /* We will come here only for signed operations. */
3585 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3587 unsigned HOST_WIDE_INT mh, ml;
3588 int pre_shift, lgup, post_shift;
3589 HOST_WIDE_INT d = INTVAL (op1);
3593 /* We could just as easily deal with negative constants here,
3594 but it does not seem worth the trouble for GCC 2.6. */
3595 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3597 pre_shift = floor_log2 (d);
3600 remainder = expand_binop (compute_mode, and_optab, op0,
3601 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3602 remainder, 0, OPTAB_LIB_WIDEN);
3604 return gen_lowpart (mode, remainder);
3606 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3607 build_int_2 (pre_shift, 0),
3614 mh = choose_multiplier (d, size, size - 1,
3615 &ml, &post_shift, &lgup);
3619 if (post_shift < BITS_PER_WORD
3620 && size - 1 < BITS_PER_WORD)
3622 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3623 build_int_2 (size - 1, 0),
3625 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3626 NULL_RTX, 0, OPTAB_WIDEN);
3627 extra_cost = (shift_cost[post_shift]
3628 + shift_cost[size - 1] + 2 * add_cost);
3629 t3 = expand_mult_highpart (compute_mode, t2, ml,
3631 max_cost - extra_cost);
3634 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3635 build_int_2 (post_shift, 0),
3637 quotient = expand_binop (compute_mode, xor_optab,
3638 t4, t1, tquotient, 0,
3646 rtx nsign, t1, t2, t3, t4;
3647 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3648 op0, constm1_rtx), NULL_RTX);
3649 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3651 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3652 build_int_2 (size - 1, 0), NULL_RTX, 0);
3653 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3655 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3660 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3662 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3671 delete_insns_since (last);
3673 /* Try using an instruction that produces both the quotient and
3674 remainder, using truncation. We can easily compensate the quotient
3675 or remainder to get floor rounding, once we have the remainder.
3676 Notice that we compute also the final remainder value here,
3677 and return the result right away. */
3678 if (target == 0 || GET_MODE (target) != compute_mode)
3679 target = gen_reg_rtx (compute_mode);
3684 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3685 quotient = gen_reg_rtx (compute_mode);
3690 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3691 remainder = gen_reg_rtx (compute_mode);
3694 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3695 quotient, remainder, 0))
3697 /* This could be computed with a branch-less sequence.
3698 Save that for later. */
3700 rtx label = gen_label_rtx ();
3701 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3702 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3703 NULL_RTX, 0, OPTAB_WIDEN);
3704 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3705 expand_dec (quotient, const1_rtx);
3706 expand_inc (remainder, op1);
3708 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3711 /* No luck with division elimination or divmod. Have to do it
3712 by conditionally adjusting op0 *and* the result. */
3714 rtx label1, label2, label3, label4, label5;
3718 quotient = gen_reg_rtx (compute_mode);
3719 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3720 label1 = gen_label_rtx ();
3721 label2 = gen_label_rtx ();
3722 label3 = gen_label_rtx ();
3723 label4 = gen_label_rtx ();
3724 label5 = gen_label_rtx ();
3725 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3726 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3727 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3728 quotient, 0, OPTAB_LIB_WIDEN);
3729 if (tem != quotient)
3730 emit_move_insn (quotient, tem);
3731 emit_jump_insn (gen_jump (label5));
3733 emit_label (label1);
3734 expand_inc (adjusted_op0, const1_rtx);
3735 emit_jump_insn (gen_jump (label4));
3737 emit_label (label2);
3738 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3739 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3740 quotient, 0, OPTAB_LIB_WIDEN);
3741 if (tem != quotient)
3742 emit_move_insn (quotient, tem);
3743 emit_jump_insn (gen_jump (label5));
3745 emit_label (label3);
3746 expand_dec (adjusted_op0, const1_rtx);
3747 emit_label (label4);
3748 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3749 quotient, 0, OPTAB_LIB_WIDEN);
3750 if (tem != quotient)
3751 emit_move_insn (quotient, tem);
3752 expand_dec (quotient, const1_rtx);
3753 emit_label (label5);
3761 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3764 unsigned HOST_WIDE_INT d = INTVAL (op1);
3765 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3766 build_int_2 (floor_log2 (d), 0),
3768 t2 = expand_binop (compute_mode, and_optab, op0,
3770 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3771 t3 = gen_reg_rtx (compute_mode);
3772 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3773 compute_mode, 1, 1);
3777 lab = gen_label_rtx ();
3778 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3779 expand_inc (t1, const1_rtx);
3784 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3790 /* Try using an instruction that produces both the quotient and
3791 remainder, using truncation. We can easily compensate the
3792 quotient or remainder to get ceiling rounding, once we have the
3793 remainder. Notice that we compute also the final remainder
3794 value here, and return the result right away. */
3795 if (target == 0 || GET_MODE (target) != compute_mode)
3796 target = gen_reg_rtx (compute_mode);
3800 remainder = (GET_CODE (target) == REG
3801 ? target : gen_reg_rtx (compute_mode));
3802 quotient = gen_reg_rtx (compute_mode);
3806 quotient = (GET_CODE (target) == REG
3807 ? target : gen_reg_rtx (compute_mode));
3808 remainder = gen_reg_rtx (compute_mode);
3811 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3814 /* This could be computed with a branch-less sequence.
3815 Save that for later. */
3816 rtx label = gen_label_rtx ();
3817 do_cmp_and_jump (remainder, const0_rtx, EQ,
3818 compute_mode, label);
3819 expand_inc (quotient, const1_rtx);
3820 expand_dec (remainder, op1);
3822 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3825 /* No luck with division elimination or divmod. Have to do it
3826 by conditionally adjusting op0 *and* the result. */
3829 rtx adjusted_op0, tem;
3831 quotient = gen_reg_rtx (compute_mode);
3832 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3833 label1 = gen_label_rtx ();
3834 label2 = gen_label_rtx ();
3835 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3836 compute_mode, label1);
3837 emit_move_insn (quotient, const0_rtx);
3838 emit_jump_insn (gen_jump (label2));
3840 emit_label (label1);
3841 expand_dec (adjusted_op0, const1_rtx);
3842 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3843 quotient, 1, OPTAB_LIB_WIDEN);
3844 if (tem != quotient)
3845 emit_move_insn (quotient, tem);
3846 expand_inc (quotient, const1_rtx);
3847 emit_label (label2);
3852 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3853 && INTVAL (op1) >= 0)
3855 /* This is extremely similar to the code for the unsigned case
3856 above. For 2.7 we should merge these variants, but for
3857 2.6.1 I don't want to touch the code for unsigned since that
3858 get used in C. The signed case will only be used by other
3862 unsigned HOST_WIDE_INT d = INTVAL (op1);
3863 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3864 build_int_2 (floor_log2 (d), 0),
3866 t2 = expand_binop (compute_mode, and_optab, op0,
3868 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3869 t3 = gen_reg_rtx (compute_mode);
3870 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3871 compute_mode, 1, 1);
3875 lab = gen_label_rtx ();
3876 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3877 expand_inc (t1, const1_rtx);
3882 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3888 /* Try using an instruction that produces both the quotient and
3889 remainder, using truncation. We can easily compensate the
3890 quotient or remainder to get ceiling rounding, once we have the
3891 remainder. Notice that we compute also the final remainder
3892 value here, and return the result right away. */
3893 if (target == 0 || GET_MODE (target) != compute_mode)
3894 target = gen_reg_rtx (compute_mode);
3897 remainder= (GET_CODE (target) == REG
3898 ? target : gen_reg_rtx (compute_mode));
3899 quotient = gen_reg_rtx (compute_mode);
3903 quotient = (GET_CODE (target) == REG
3904 ? target : gen_reg_rtx (compute_mode));
3905 remainder = gen_reg_rtx (compute_mode);
3908 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3911 /* This could be computed with a branch-less sequence.
3912 Save that for later. */
3914 rtx label = gen_label_rtx ();
3915 do_cmp_and_jump (remainder, const0_rtx, EQ,
3916 compute_mode, label);
3917 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3918 NULL_RTX, 0, OPTAB_WIDEN);
3919 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3920 expand_inc (quotient, const1_rtx);
3921 expand_dec (remainder, op1);
3923 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3926 /* No luck with division elimination or divmod. Have to do it
3927 by conditionally adjusting op0 *and* the result. */
3929 rtx label1, label2, label3, label4, label5;
3933 quotient = gen_reg_rtx (compute_mode);
3934 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3935 label1 = gen_label_rtx ();
3936 label2 = gen_label_rtx ();
3937 label3 = gen_label_rtx ();
3938 label4 = gen_label_rtx ();
3939 label5 = gen_label_rtx ();
3940 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3941 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3942 compute_mode, label1);
3943 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3944 quotient, 0, OPTAB_LIB_WIDEN);
3945 if (tem != quotient)
3946 emit_move_insn (quotient, tem);
3947 emit_jump_insn (gen_jump (label5));
3949 emit_label (label1);
3950 expand_dec (adjusted_op0, const1_rtx);
3951 emit_jump_insn (gen_jump (label4));
3953 emit_label (label2);
3954 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3955 compute_mode, label3);
3956 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3957 quotient, 0, OPTAB_LIB_WIDEN);
3958 if (tem != quotient)
3959 emit_move_insn (quotient, tem);
3960 emit_jump_insn (gen_jump (label5));
3962 emit_label (label3);
3963 expand_inc (adjusted_op0, const1_rtx);
3964 emit_label (label4);
3965 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3966 quotient, 0, OPTAB_LIB_WIDEN);
3967 if (tem != quotient)
3968 emit_move_insn (quotient, tem);
3969 expand_inc (quotient, const1_rtx);
3970 emit_label (label5);
3975 case EXACT_DIV_EXPR:
3976 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3978 HOST_WIDE_INT d = INTVAL (op1);
3979 unsigned HOST_WIDE_INT ml;
3983 pre_shift = floor_log2 (d & -d);
3984 ml = invert_mod2n (d >> pre_shift, size);
3985 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3986 build_int_2 (pre_shift, 0), NULL_RTX, unsignedp);
3987 quotient = expand_mult (compute_mode, t1,
3988 gen_int_mode (ml, compute_mode),
3991 insn = get_last_insn ();
3992 set_unique_reg_note (insn,
3994 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
4000 case ROUND_DIV_EXPR:
4001 case ROUND_MOD_EXPR:
4006 label = gen_label_rtx ();
4007 quotient = gen_reg_rtx (compute_mode);
4008 remainder = gen_reg_rtx (compute_mode);
4009 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
4012 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
4013 quotient, 1, OPTAB_LIB_WIDEN);
4014 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
4015 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4016 remainder, 1, OPTAB_LIB_WIDEN);
4018 tem = plus_constant (op1, -1);
4019 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4020 build_int_2 (1, 0), NULL_RTX, 1);
4021 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
4022 expand_inc (quotient, const1_rtx);
4023 expand_dec (remainder, op1);
4028 rtx abs_rem, abs_op1, tem, mask;
4030 label = gen_label_rtx ();
4031 quotient = gen_reg_rtx (compute_mode);
4032 remainder = gen_reg_rtx (compute_mode);
4033 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
4036 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
4037 quotient, 0, OPTAB_LIB_WIDEN);
4038 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
4039 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4040 remainder, 0, OPTAB_LIB_WIDEN);
4042 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
4043 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
4044 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
4045 build_int_2 (1, 0), NULL_RTX, 1);
4046 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
4047 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4048 NULL_RTX, 0, OPTAB_WIDEN);
4049 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4050 build_int_2 (size - 1, 0), NULL_RTX, 0);
4051 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
4052 NULL_RTX, 0, OPTAB_WIDEN);
4053 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4054 NULL_RTX, 0, OPTAB_WIDEN);
4055 expand_inc (quotient, tem);
4056 tem = expand_binop (compute_mode, xor_optab, mask, op1,
4057 NULL_RTX, 0, OPTAB_WIDEN);
4058 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4059 NULL_RTX, 0, OPTAB_WIDEN);
4060 expand_dec (remainder, tem);
4063 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4071 if (target && GET_MODE (target) != compute_mode)
4076 /* Try to produce the remainder without producing the quotient.
4077 If we seem to have a divmod pattern that does not require widening,
4078 don't try widening here. We should really have a WIDEN argument
4079 to expand_twoval_binop, since what we'd really like to do here is
4080 1) try a mod insn in compute_mode
4081 2) try a divmod insn in compute_mode
4082 3) try a div insn in compute_mode and multiply-subtract to get
4084 4) try the same things with widening allowed. */
4086 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4089 ((optab2->handlers[(int) compute_mode].insn_code
4090 != CODE_FOR_nothing)
4091 ? OPTAB_DIRECT : OPTAB_WIDEN));
4094 /* No luck there. Can we do remainder and divide at once
4095 without a library call? */
4096 remainder = gen_reg_rtx (compute_mode);
4097 if (! expand_twoval_binop ((unsignedp
4101 NULL_RTX, remainder, unsignedp))
4106 return gen_lowpart (mode, remainder);
4109 /* Produce the quotient. Try a quotient insn, but not a library call.
4110 If we have a divmod in this mode, use it in preference to widening
4111 the div (for this test we assume it will not fail). Note that optab2
4112 is set to the one of the two optabs that the call below will use. */
4114 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
4115 op0, op1, rem_flag ? NULL_RTX : target,
4117 ((optab2->handlers[(int) compute_mode].insn_code
4118 != CODE_FOR_nothing)
4119 ? OPTAB_DIRECT : OPTAB_WIDEN));
4123 /* No luck there. Try a quotient-and-remainder insn,
4124 keeping the quotient alone. */
4125 quotient = gen_reg_rtx (compute_mode);
4126 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
4128 quotient, NULL_RTX, unsignedp))
4132 /* Still no luck. If we are not computing the remainder,
4133 use a library call for the quotient. */
4134 quotient = sign_expand_binop (compute_mode,
4135 udiv_optab, sdiv_optab,
4137 unsignedp, OPTAB_LIB_WIDEN);
4144 if (target && GET_MODE (target) != compute_mode)
4148 /* No divide instruction either. Use library for remainder. */
4149 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4151 unsignedp, OPTAB_LIB_WIDEN);
4154 /* We divided. Now finish doing X - Y * (X / Y). */
4155 remainder = expand_mult (compute_mode, quotient, op1,
4156 NULL_RTX, unsignedp);
4157 remainder = expand_binop (compute_mode, sub_optab, op0,
4158 remainder, target, unsignedp,
4163 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4166 /* Return a tree node with data type TYPE, describing the value of X.
4167 Usually this is an RTL_EXPR, if there is no obvious better choice.
4168 X may be an expression, however we only support those expressions
4169 generated by loop.c. */
4172 make_tree (tree type, rtx x)
4176 switch (GET_CODE (x))
4179 t = build_int_2 (INTVAL (x),
4180 (TYPE_UNSIGNED (type)
4181 && (GET_MODE_BITSIZE (TYPE_MODE (type))
4182 < HOST_BITS_PER_WIDE_INT))
4183 || INTVAL (x) >= 0 ? 0 : -1);
4184 TREE_TYPE (t) = type;
4188 if (GET_MODE (x) == VOIDmode)
4190 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4191 TREE_TYPE (t) = type;
4197 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4198 t = build_real (type, d);
4209 units = CONST_VECTOR_NUNITS (x);
4211 /* Build a tree with vector elements. */
4212 for (i = units - 1; i >= 0; --i)
4214 elt = CONST_VECTOR_ELT (x, i);
4215 t = tree_cons (NULL_TREE, make_tree (type, elt), t);
4218 return build_vector (type, t);
4222 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4223 make_tree (type, XEXP (x, 1))));
4226 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4227 make_tree (type, XEXP (x, 1))));
4230 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
4233 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
4234 make_tree (type, XEXP (x, 1))));
4237 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
4238 make_tree (type, XEXP (x, 1))));
4241 t = lang_hooks.types.unsigned_type (type);
4242 return fold (convert (type,
4243 build (RSHIFT_EXPR, t,
4244 make_tree (t, XEXP (x, 0)),
4245 make_tree (type, XEXP (x, 1)))));
4248 t = lang_hooks.types.signed_type (type);
4249 return fold (convert (type,
4250 build (RSHIFT_EXPR, t,
4251 make_tree (t, XEXP (x, 0)),
4252 make_tree (type, XEXP (x, 1)))));
4255 if (TREE_CODE (type) != REAL_TYPE)
4256 t = lang_hooks.types.signed_type (type);
4260 return fold (convert (type,
4261 build (TRUNC_DIV_EXPR, t,
4262 make_tree (t, XEXP (x, 0)),
4263 make_tree (t, XEXP (x, 1)))));
4265 t = lang_hooks.types.unsigned_type (type);
4266 return fold (convert (type,
4267 build (TRUNC_DIV_EXPR, t,
4268 make_tree (t, XEXP (x, 0)),
4269 make_tree (t, XEXP (x, 1)))));
4273 t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)),
4274 GET_CODE (x) == ZERO_EXTEND);
4275 return fold (convert (type, make_tree (t, XEXP (x, 0))));
4278 t = make_node (RTL_EXPR);
4279 TREE_TYPE (t) = type;
4281 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
4282 ptr_mode. So convert. */
4283 if (POINTER_TYPE_P (type))
4284 x = convert_memory_address (TYPE_MODE (type), x);
4286 RTL_EXPR_RTL (t) = x;
4287 /* There are no insns to be output
4288 when this rtl_expr is used. */
4289 RTL_EXPR_SEQUENCE (t) = 0;
4294 /* Check whether the multiplication X * MULT + ADD overflows.
4295 X, MULT and ADD must be CONST_*.
4296 MODE is the machine mode for the computation.
4297 X and MULT must have mode MODE. ADD may have a different mode.
4298 So can X (defaults to same as MODE).
4299 UNSIGNEDP is nonzero to do unsigned multiplication. */
4302 const_mult_add_overflow_p (rtx x, rtx mult, rtx add, enum machine_mode mode, int unsignedp)
4304 tree type, mult_type, add_type, result;
4306 type = lang_hooks.types.type_for_mode (mode, unsignedp);
4308 /* In order to get a proper overflow indication from an unsigned
4309 type, we have to pretend that it's a sizetype. */
4313 mult_type = copy_node (type);
4314 TYPE_IS_SIZETYPE (mult_type) = 1;
4317 add_type = (GET_MODE (add) == VOIDmode ? mult_type
4318 : lang_hooks.types.type_for_mode (GET_MODE (add), unsignedp));
4320 result = fold (build (PLUS_EXPR, mult_type,
4321 fold (build (MULT_EXPR, mult_type,
4322 make_tree (mult_type, x),
4323 make_tree (mult_type, mult))),
4324 make_tree (add_type, add)));
4326 return TREE_CONSTANT_OVERFLOW (result);
4329 /* Return an rtx representing the value of X * MULT + ADD.
4330 TARGET is a suggestion for where to store the result (an rtx).
4331 MODE is the machine mode for the computation.
4332 X and MULT must have mode MODE. ADD may have a different mode.
4333 So can X (defaults to same as MODE).
4334 UNSIGNEDP is nonzero to do unsigned multiplication.
4335 This may emit insns. */
4338 expand_mult_add (rtx x, rtx target, rtx mult, rtx add, enum machine_mode mode,
4341 tree type = lang_hooks.types.type_for_mode (mode, unsignedp);
4342 tree add_type = (GET_MODE (add) == VOIDmode
4343 ? type: lang_hooks.types.type_for_mode (GET_MODE (add),
4345 tree result = fold (build (PLUS_EXPR, type,
4346 fold (build (MULT_EXPR, type,
4347 make_tree (type, x),
4348 make_tree (type, mult))),
4349 make_tree (add_type, add)));
4351 return expand_expr (result, target, VOIDmode, 0);
4354 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4355 and returning TARGET.
4357 If TARGET is 0, a pseudo-register or constant is returned. */
4360 expand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target)
4364 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
4365 tem = simplify_binary_operation (AND, mode, op0, op1);
4367 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4371 else if (tem != target)
4372 emit_move_insn (target, tem);
4376 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4377 and storing in TARGET. Normally return TARGET.
4378 Return 0 if that cannot be done.
4380 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
4381 it is VOIDmode, they cannot both be CONST_INT.
4383 UNSIGNEDP is for the case where we have to widen the operands
4384 to perform the operation. It says to use zero-extension.
4386 NORMALIZEP is 1 if we should convert the result to be either zero
4387 or one. Normalize is -1 if we should convert the result to be
4388 either zero or -1. If NORMALIZEP is zero, the result will be left
4389 "raw" out of the scc insn. */
4392 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
4393 enum machine_mode mode, int unsignedp, int normalizep)
4396 enum insn_code icode;
4397 enum machine_mode compare_mode;
4398 enum machine_mode target_mode = GET_MODE (target);
4400 rtx last = get_last_insn ();
4401 rtx pattern, comparison;
4403 /* ??? Ok to do this and then fail? */
4404 op0 = protect_from_queue (op0, 0);
4405 op1 = protect_from_queue (op1, 0);
4408 code = unsigned_condition (code);
4410 /* If one operand is constant, make it the second one. Only do this
4411 if the other operand is not constant as well. */
4413 if (swap_commutative_operands_p (op0, op1))
4418 code = swap_condition (code);
4421 if (mode == VOIDmode)
4422 mode = GET_MODE (op0);
4424 /* For some comparisons with 1 and -1, we can convert this to
4425 comparisons with zero. This will often produce more opportunities for
4426 store-flag insns. */
4431 if (op1 == const1_rtx)
4432 op1 = const0_rtx, code = LE;
4435 if (op1 == constm1_rtx)
4436 op1 = const0_rtx, code = LT;
4439 if (op1 == const1_rtx)
4440 op1 = const0_rtx, code = GT;
4443 if (op1 == constm1_rtx)
4444 op1 = const0_rtx, code = GE;
4447 if (op1 == const1_rtx)
4448 op1 = const0_rtx, code = NE;
4451 if (op1 == const1_rtx)
4452 op1 = const0_rtx, code = EQ;
4458 /* If we are comparing a double-word integer with zero, we can convert
4459 the comparison into one involving a single word. */
4460 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
4461 && GET_MODE_CLASS (mode) == MODE_INT
4462 && op1 == const0_rtx
4463 && (GET_CODE (op0) != MEM || ! MEM_VOLATILE_P (op0)))
4465 if (code == EQ || code == NE)
4467 rtx op00, op01, op0both;
4469 /* Do a logical OR of the two words and compare the result. */
4470 op00 = simplify_gen_subreg (word_mode, op0, mode, 0);
4471 op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD);
4472 op0both = expand_binop (word_mode, ior_optab, op00, op01,
4473 NULL_RTX, unsignedp, OPTAB_DIRECT);
4475 return emit_store_flag (target, code, op0both, op1, word_mode,
4476 unsignedp, normalizep);
4478 else if (code == LT || code == GE)
4482 /* If testing the sign bit, can just test on high word. */
4483 op0h = simplify_gen_subreg (word_mode, op0, mode,
4484 subreg_highpart_offset (word_mode, mode));
4485 return emit_store_flag (target, code, op0h, op1, word_mode,
4486 unsignedp, normalizep);
4490 /* From now on, we won't change CODE, so set ICODE now. */
4491 icode = setcc_gen_code[(int) code];
4493 /* If this is A < 0 or A >= 0, we can do this by taking the ones
4494 complement of A (for GE) and shifting the sign bit to the low bit. */
4495 if (op1 == const0_rtx && (code == LT || code == GE)
4496 && GET_MODE_CLASS (mode) == MODE_INT
4497 && (normalizep || STORE_FLAG_VALUE == 1
4498 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4499 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4500 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4504 /* If the result is to be wider than OP0, it is best to convert it
4505 first. If it is to be narrower, it is *incorrect* to convert it
4507 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4509 op0 = protect_from_queue (op0, 0);
4510 op0 = convert_modes (target_mode, mode, op0, 0);
4514 if (target_mode != mode)
4518 op0 = expand_unop (mode, one_cmpl_optab, op0,
4519 ((STORE_FLAG_VALUE == 1 || normalizep)
4520 ? 0 : subtarget), 0);
4522 if (STORE_FLAG_VALUE == 1 || normalizep)
4523 /* If we are supposed to produce a 0/1 value, we want to do
4524 a logical shift from the sign bit to the low-order bit; for
4525 a -1/0 value, we do an arithmetic shift. */
4526 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4527 size_int (GET_MODE_BITSIZE (mode) - 1),
4528 subtarget, normalizep != -1);
4530 if (mode != target_mode)
4531 op0 = convert_modes (target_mode, mode, op0, 0);
4536 if (icode != CODE_FOR_nothing)
4538 insn_operand_predicate_fn pred;
4540 /* We think we may be able to do this with a scc insn. Emit the
4541 comparison and then the scc insn.
4543 compare_from_rtx may call emit_queue, which would be deleted below
4544 if the scc insn fails. So call it ourselves before setting LAST.
4545 Likewise for do_pending_stack_adjust. */
4548 do_pending_stack_adjust ();
4549 last = get_last_insn ();
4552 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX);
4553 if (GET_CODE (comparison) == CONST_INT)
4554 return (comparison == const0_rtx ? const0_rtx
4555 : normalizep == 1 ? const1_rtx
4556 : normalizep == -1 ? constm1_rtx
4559 /* The code of COMPARISON may not match CODE if compare_from_rtx
4560 decided to swap its operands and reverse the original code.
4562 We know that compare_from_rtx returns either a CONST_INT or
4563 a new comparison code, so it is safe to just extract the
4564 code from COMPARISON. */
4565 code = GET_CODE (comparison);
4567 /* Get a reference to the target in the proper mode for this insn. */
4568 compare_mode = insn_data[(int) icode].operand[0].mode;
4570 pred = insn_data[(int) icode].operand[0].predicate;
4571 if (preserve_subexpressions_p ()
4572 || ! (*pred) (subtarget, compare_mode))
4573 subtarget = gen_reg_rtx (compare_mode);
4575 pattern = GEN_FCN (icode) (subtarget);
4578 emit_insn (pattern);
4580 /* If we are converting to a wider mode, first convert to
4581 TARGET_MODE, then normalize. This produces better combining
4582 opportunities on machines that have a SIGN_EXTRACT when we are
4583 testing a single bit. This mostly benefits the 68k.
4585 If STORE_FLAG_VALUE does not have the sign bit set when
4586 interpreted in COMPARE_MODE, we can do this conversion as
4587 unsigned, which is usually more efficient. */
4588 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4590 convert_move (target, subtarget,
4591 (GET_MODE_BITSIZE (compare_mode)
4592 <= HOST_BITS_PER_WIDE_INT)
4593 && 0 == (STORE_FLAG_VALUE
4594 & ((HOST_WIDE_INT) 1
4595 << (GET_MODE_BITSIZE (compare_mode) -1))));
4597 compare_mode = target_mode;
4602 /* If we want to keep subexpressions around, don't reuse our
4605 if (preserve_subexpressions_p ())
4608 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
4609 we don't have to do anything. */
4610 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4612 /* STORE_FLAG_VALUE might be the most negative number, so write
4613 the comparison this way to avoid a compiler-time warning. */
4614 else if (- normalizep == STORE_FLAG_VALUE)
4615 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4617 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4618 makes it hard to use a value of just the sign bit due to
4619 ANSI integer constant typing rules. */
4620 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4621 && (STORE_FLAG_VALUE
4622 & ((HOST_WIDE_INT) 1
4623 << (GET_MODE_BITSIZE (compare_mode) - 1))))
4624 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4625 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4626 subtarget, normalizep == 1);
4627 else if (STORE_FLAG_VALUE & 1)
4629 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget);
4630 if (normalizep == -1)
4631 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4636 /* If we were converting to a smaller mode, do the
4638 if (target_mode != compare_mode)
4640 convert_move (target, op0, 0);
4648 delete_insns_since (last);
4650 /* If expensive optimizations, use different pseudo registers for each
4651 insn, instead of reusing the same pseudo. This leads to better CSE,
4652 but slows down the compiler, since there are more pseudos */
4653 subtarget = (!flag_expensive_optimizations
4654 && (target_mode == mode)) ? target : NULL_RTX;
4656 /* If we reached here, we can't do this with a scc insn. However, there
4657 are some comparisons that can be done directly. For example, if
4658 this is an equality comparison of integers, we can try to exclusive-or
4659 (or subtract) the two operands and use a recursive call to try the
4660 comparison with zero. Don't do any of these cases if branches are
4664 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4665 && op1 != const0_rtx)
4667 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4671 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4674 tem = emit_store_flag (target, code, tem, const0_rtx,
4675 mode, unsignedp, normalizep);
4677 delete_insns_since (last);
4681 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4682 the constant zero. Reject all other comparisons at this point. Only
4683 do LE and GT if branches are expensive since they are expensive on
4684 2-operand machines. */
4686 if (BRANCH_COST == 0
4687 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4688 || (code != EQ && code != NE
4689 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4692 /* See what we need to return. We can only return a 1, -1, or the
4695 if (normalizep == 0)
4697 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4698 normalizep = STORE_FLAG_VALUE;
4700 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4701 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4702 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4708 /* Try to put the result of the comparison in the sign bit. Assume we can't
4709 do the necessary operation below. */
4713 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4714 the sign bit set. */
4718 /* This is destructive, so SUBTARGET can't be OP0. */
4719 if (rtx_equal_p (subtarget, op0))
4722 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4725 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4729 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4730 number of bits in the mode of OP0, minus one. */
4734 if (rtx_equal_p (subtarget, op0))
4737 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4738 size_int (GET_MODE_BITSIZE (mode) - 1),
4740 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4744 if (code == EQ || code == NE)
4746 /* For EQ or NE, one way to do the comparison is to apply an operation
4747 that converts the operand into a positive number if it is nonzero
4748 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4749 for NE we negate. This puts the result in the sign bit. Then we
4750 normalize with a shift, if needed.
4752 Two operations that can do the above actions are ABS and FFS, so try
4753 them. If that doesn't work, and MODE is smaller than a full word,
4754 we can use zero-extension to the wider mode (an unsigned conversion)
4755 as the operation. */
4757 /* Note that ABS doesn't yield a positive number for INT_MIN, but
4758 that is compensated by the subsequent overflow when subtracting
4761 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4762 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4763 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4764 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4765 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4767 op0 = protect_from_queue (op0, 0);
4768 tem = convert_modes (word_mode, mode, op0, 1);
4775 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4778 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4781 /* If we couldn't do it that way, for NE we can "or" the two's complement
4782 of the value with itself. For EQ, we take the one's complement of
4783 that "or", which is an extra insn, so we only handle EQ if branches
4786 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4788 if (rtx_equal_p (subtarget, op0))
4791 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4792 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4795 if (tem && code == EQ)
4796 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4800 if (tem && normalizep)
4801 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4802 size_int (GET_MODE_BITSIZE (mode) - 1),
4803 subtarget, normalizep == 1);
4807 if (GET_MODE (tem) != target_mode)
4809 convert_move (target, tem, 0);
4812 else if (!subtarget)
4814 emit_move_insn (target, tem);
4819 delete_insns_since (last);
4824 /* Like emit_store_flag, but always succeeds. */
4827 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
4828 enum machine_mode mode, int unsignedp, int normalizep)
4832 /* First see if emit_store_flag can do the job. */
4833 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4837 if (normalizep == 0)
4840 /* If this failed, we have to do this with set/compare/jump/set code. */
4842 if (GET_CODE (target) != REG
4843 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4844 target = gen_reg_rtx (GET_MODE (target));
4846 emit_move_insn (target, const1_rtx);
4847 label = gen_label_rtx ();
4848 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
4851 emit_move_insn (target, const0_rtx);
4857 /* Perform possibly multi-word comparison and conditional jump to LABEL
4858 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4860 The algorithm is based on the code in expr.c:do_jump.
4862 Note that this does not perform a general comparison. Only variants
4863 generated within expmed.c are correctly handled, others abort (but could
4864 be handled if needed). */
4867 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
4870 /* If this mode is an integer too wide to compare properly,
4871 compare word by word. Rely on cse to optimize constant cases. */
4873 if (GET_MODE_CLASS (mode) == MODE_INT
4874 && ! can_compare_p (op, mode, ccp_jump))
4876 rtx label2 = gen_label_rtx ();
4881 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4885 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4889 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4893 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4897 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4900 /* do_jump_by_parts_equality_rtx compares with zero. Luckily
4901 that's the only equality operations we do */
4903 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4905 do_jump_by_parts_equality_rtx (arg1, label2, label);
4909 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4911 do_jump_by_parts_equality_rtx (arg1, label, label2);
4918 emit_label (label2);
4921 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);