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 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
31 #include "insn-config.h"
37 static void store_fixed_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
38 unsigned HOST_WIDE_INT,
39 unsigned HOST_WIDE_INT, rtx));
40 static void store_split_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
41 unsigned HOST_WIDE_INT, rtx));
42 static rtx extract_fixed_bit_field PARAMS ((enum machine_mode, rtx,
43 unsigned HOST_WIDE_INT,
44 unsigned HOST_WIDE_INT,
45 unsigned HOST_WIDE_INT,
47 static rtx mask_rtx PARAMS ((enum machine_mode, int,
49 static rtx lshift_value PARAMS ((enum machine_mode, rtx,
51 static rtx extract_split_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
52 unsigned HOST_WIDE_INT, int));
53 static void do_cmp_and_jump PARAMS ((rtx, rtx, enum rtx_code,
54 enum machine_mode, rtx));
56 /* Non-zero means divides or modulus operations are relatively cheap for
57 powers of two, so don't use branches; emit the operation instead.
58 Usually, this will mean that the MD file will emit non-branch
61 static int sdiv_pow2_cheap, smod_pow2_cheap;
63 #ifndef SLOW_UNALIGNED_ACCESS
64 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
67 /* For compilers that support multiple targets with different word sizes,
68 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example
69 is the H8/300(H) compiler. */
71 #ifndef MAX_BITS_PER_WORD
72 #define MAX_BITS_PER_WORD BITS_PER_WORD
75 /* Reduce conditional compilation elsewhere. */
78 #define CODE_FOR_insv CODE_FOR_nothing
79 #define gen_insv(a,b,c,d) NULL_RTX
83 #define CODE_FOR_extv CODE_FOR_nothing
84 #define gen_extv(a,b,c,d) NULL_RTX
88 #define CODE_FOR_extzv CODE_FOR_nothing
89 #define gen_extzv(a,b,c,d) NULL_RTX
92 /* Cost of various pieces of RTL. Note that some of these are indexed by
93 shift count and some by mode. */
94 static int add_cost, negate_cost, zero_cost;
95 static int shift_cost[MAX_BITS_PER_WORD];
96 static int shiftadd_cost[MAX_BITS_PER_WORD];
97 static int shiftsub_cost[MAX_BITS_PER_WORD];
98 static int mul_cost[NUM_MACHINE_MODES];
99 static int div_cost[NUM_MACHINE_MODES];
100 static int mul_widen_cost[NUM_MACHINE_MODES];
101 static int mul_highpart_cost[NUM_MACHINE_MODES];
106 /* This is "some random pseudo register" for purposes of calling recog
107 to see what insns exist. */
108 rtx reg = gen_rtx_REG (word_mode, 10000);
109 rtx shift_insn, shiftadd_insn, shiftsub_insn;
112 enum machine_mode mode, wider_mode;
116 reg = gen_rtx_REG (word_mode, 10000);
118 zero_cost = rtx_cost (const0_rtx, 0);
119 add_cost = rtx_cost (gen_rtx_PLUS (word_mode, reg, reg), SET);
121 shift_insn = emit_insn (gen_rtx_SET (VOIDmode, reg,
122 gen_rtx_ASHIFT (word_mode, reg,
126 = emit_insn (gen_rtx_SET (VOIDmode, reg,
127 gen_rtx_PLUS (word_mode,
128 gen_rtx_MULT (word_mode,
133 = emit_insn (gen_rtx_SET (VOIDmode, reg,
134 gen_rtx_MINUS (word_mode,
135 gen_rtx_MULT (word_mode,
142 shiftadd_cost[0] = shiftsub_cost[0] = add_cost;
144 for (m = 1; m < MAX_BITS_PER_WORD; m++)
146 shift_cost[m] = shiftadd_cost[m] = shiftsub_cost[m] = 32000;
148 XEXP (SET_SRC (PATTERN (shift_insn)), 1) = GEN_INT (m);
149 if (recog (PATTERN (shift_insn), shift_insn, &dummy) >= 0)
150 shift_cost[m] = rtx_cost (SET_SRC (PATTERN (shift_insn)), SET);
152 XEXP (XEXP (SET_SRC (PATTERN (shiftadd_insn)), 0), 1)
153 = GEN_INT ((HOST_WIDE_INT) 1 << m);
154 if (recog (PATTERN (shiftadd_insn), shiftadd_insn, &dummy) >= 0)
155 shiftadd_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftadd_insn)), SET);
157 XEXP (XEXP (SET_SRC (PATTERN (shiftsub_insn)), 0), 1)
158 = GEN_INT ((HOST_WIDE_INT) 1 << m);
159 if (recog (PATTERN (shiftsub_insn), shiftsub_insn, &dummy) >= 0)
160 shiftsub_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftsub_insn)), SET);
163 negate_cost = rtx_cost (gen_rtx_NEG (word_mode, reg), SET);
166 = (rtx_cost (gen_rtx_DIV (word_mode, reg, GEN_INT (32)), SET)
169 = (rtx_cost (gen_rtx_MOD (word_mode, reg, GEN_INT (32)), SET)
172 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
174 mode = GET_MODE_WIDER_MODE (mode))
176 reg = gen_rtx_REG (mode, 10000);
177 div_cost[(int) mode] = rtx_cost (gen_rtx_UDIV (mode, reg, reg), SET);
178 mul_cost[(int) mode] = rtx_cost (gen_rtx_MULT (mode, reg, reg), SET);
179 wider_mode = GET_MODE_WIDER_MODE (mode);
180 if (wider_mode != VOIDmode)
182 mul_widen_cost[(int) wider_mode]
183 = rtx_cost (gen_rtx_MULT (wider_mode,
184 gen_rtx_ZERO_EXTEND (wider_mode, reg),
185 gen_rtx_ZERO_EXTEND (wider_mode, reg)),
187 mul_highpart_cost[(int) mode]
188 = rtx_cost (gen_rtx_TRUNCATE
190 gen_rtx_LSHIFTRT (wider_mode,
191 gen_rtx_MULT (wider_mode,
196 GEN_INT (GET_MODE_BITSIZE (mode)))),
204 /* Return an rtx representing minus the value of X.
205 MODE is the intended mode of the result,
206 useful if X is a CONST_INT. */
210 enum machine_mode mode;
213 rtx result = simplify_unary_operation (NEG, mode, x, mode);
216 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
221 /* Report on the availability of insv/extv/extzv and the desired mode
222 of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo
223 is false; else the mode of the specified operand. If OPNO is -1,
224 all the caller cares about is whether the insn is available. */
226 mode_for_extraction (pattern, opno)
227 enum extraction_pattern pattern;
230 const struct insn_data *data;
237 data = &insn_data[CODE_FOR_insv];
240 return MAX_MACHINE_MODE;
245 data = &insn_data[CODE_FOR_extv];
248 return MAX_MACHINE_MODE;
253 data = &insn_data[CODE_FOR_extzv];
256 return MAX_MACHINE_MODE;
265 /* Everyone who uses this function used to follow it with
266 if (result == VOIDmode) result = word_mode; */
267 if (data->operand[opno].mode == VOIDmode)
269 return data->operand[opno].mode;
273 /* Generate code to store value from rtx VALUE
274 into a bit-field within structure STR_RTX
275 containing BITSIZE bits starting at bit BITNUM.
276 FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
277 ALIGN is the alignment that STR_RTX is known to have.
278 TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */
280 /* ??? Note that there are two different ideas here for how
281 to determine the size to count bits within, for a register.
282 One is BITS_PER_WORD, and the other is the size of operand 3
285 If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
286 else, we use the mode of operand 3. */
289 store_bit_field (str_rtx, bitsize, bitnum, fieldmode, value, total_size)
291 unsigned HOST_WIDE_INT bitsize;
292 unsigned HOST_WIDE_INT bitnum;
293 enum machine_mode fieldmode;
295 HOST_WIDE_INT total_size;
298 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
299 unsigned HOST_WIDE_INT offset = bitnum / unit;
300 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
304 enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
306 /* Discount the part of the structure before the desired byte.
307 We need to know how many bytes are safe to reference after it. */
309 total_size -= (bitpos / BIGGEST_ALIGNMENT
310 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
312 while (GET_CODE (op0) == SUBREG)
314 /* The following line once was done only if WORDS_BIG_ENDIAN,
315 but I think that is a mistake. WORDS_BIG_ENDIAN is
316 meaningful at a much higher level; when structures are copied
317 between memory and regs, the higher-numbered regs
318 always get higher addresses. */
319 offset += (SUBREG_BYTE (op0) / UNITS_PER_WORD);
320 /* We used to adjust BITPOS here, but now we do the whole adjustment
321 right after the loop. */
322 op0 = SUBREG_REG (op0);
325 value = protect_from_queue (value, 0);
328 value = force_not_mem (value);
330 /* If the target is a register, overwriting the entire object, or storing
331 a full-word or multi-word field can be done with just a SUBREG.
333 If the target is memory, storing any naturally aligned field can be
334 done with a simple store. For targets that support fast unaligned
335 memory, any naturally sized, unit aligned field can be done directly. */
337 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
338 + (offset * UNITS_PER_WORD);
341 && bitsize == GET_MODE_BITSIZE (fieldmode)
342 && (GET_CODE (op0) != MEM
343 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
344 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
345 && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
346 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
347 || (offset * BITS_PER_UNIT % bitsize == 0
348 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
350 if (GET_MODE (op0) != fieldmode)
352 if (GET_CODE (op0) == SUBREG)
354 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
355 || GET_MODE_CLASS (fieldmode) == MODE_INT
356 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
357 op0 = SUBREG_REG (op0);
359 /* Else we've got some float mode source being extracted into
360 a different float mode destination -- this combination of
361 subregs results in Severe Tire Damage. */
364 if (GET_CODE (op0) == REG)
365 op0 = gen_rtx_SUBREG (fieldmode, op0, byte_offset);
367 op0 = adjust_address (op0, fieldmode, offset);
369 emit_move_insn (op0, value);
373 /* Make sure we are playing with integral modes. Pun with subregs
374 if we aren't. This must come after the entire register case above,
375 since that case is valid for any mode. The following cases are only
376 valid for integral modes. */
378 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
379 if (imode != GET_MODE (op0))
381 if (GET_CODE (op0) == MEM)
382 op0 = adjust_address (op0, imode, 0);
383 else if (imode != BLKmode)
384 op0 = gen_lowpart (imode, op0);
390 /* If OP0 is a register, BITPOS must count within a word.
391 But as we have it, it counts within whatever size OP0 now has.
392 On a bigendian machine, these are not the same, so convert. */
394 && GET_CODE (op0) != MEM
395 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
396 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
398 /* Storing an lsb-aligned field in a register
399 can be done with a movestrict instruction. */
401 if (GET_CODE (op0) != MEM
402 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
403 && bitsize == GET_MODE_BITSIZE (fieldmode)
404 && (movstrict_optab->handlers[(int) fieldmode].insn_code
405 != CODE_FOR_nothing))
407 int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
409 /* Get appropriate low part of the value being stored. */
410 if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
411 value = gen_lowpart (fieldmode, value);
412 else if (!(GET_CODE (value) == SYMBOL_REF
413 || GET_CODE (value) == LABEL_REF
414 || GET_CODE (value) == CONST))
415 value = convert_to_mode (fieldmode, value, 0);
417 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
418 value = copy_to_mode_reg (fieldmode, value);
420 if (GET_CODE (op0) == SUBREG)
422 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
423 || GET_MODE_CLASS (fieldmode) == MODE_INT
424 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
425 op0 = SUBREG_REG (op0);
427 /* Else we've got some float mode source being extracted into
428 a different float mode destination -- this combination of
429 subregs results in Severe Tire Damage. */
433 emit_insn (GEN_FCN (icode)
434 (gen_rtx_SUBREG (fieldmode, op0,
435 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
436 + (offset * UNITS_PER_WORD)),
442 /* Handle fields bigger than a word. */
444 if (bitsize > BITS_PER_WORD)
446 /* Here we transfer the words of the field
447 in the order least significant first.
448 This is because the most significant word is the one which may
450 However, only do that if the value is not BLKmode. */
452 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
453 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
456 /* This is the mode we must force value to, so that there will be enough
457 subwords to extract. Note that fieldmode will often (always?) be
458 VOIDmode, because that is what store_field uses to indicate that this
459 is a bit field, but passing VOIDmode to operand_subword_force will
460 result in an abort. */
461 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
463 for (i = 0; i < nwords; i++)
465 /* If I is 0, use the low-order word in both field and target;
466 if I is 1, use the next to lowest word; and so on. */
467 unsigned int wordnum = (backwards ? nwords - i - 1 : i);
468 unsigned int bit_offset = (backwards
469 ? MAX ((int) bitsize - ((int) i + 1)
472 : (int) i * BITS_PER_WORD);
474 store_bit_field (op0, MIN (BITS_PER_WORD,
475 bitsize - i * BITS_PER_WORD),
476 bitnum + bit_offset, word_mode,
477 operand_subword_force (value, wordnum,
478 (GET_MODE (value) == VOIDmode
480 : GET_MODE (value))),
486 /* From here on we can assume that the field to be stored in is
487 a full-word (whatever type that is), since it is shorter than a word. */
489 /* OFFSET is the number of words or bytes (UNIT says which)
490 from STR_RTX to the first word or byte containing part of the field. */
492 if (GET_CODE (op0) != MEM)
495 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
497 if (GET_CODE (op0) != REG)
499 /* Since this is a destination (lvalue), we can't copy it to a
500 pseudo. We can trivially remove a SUBREG that does not
501 change the size of the operand. Such a SUBREG may have been
502 added above. Otherwise, abort. */
503 if (GET_CODE (op0) == SUBREG
504 && (GET_MODE_SIZE (GET_MODE (op0))
505 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
506 op0 = SUBREG_REG (op0);
510 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
511 op0, (offset * UNITS_PER_WORD));
516 op0 = protect_from_queue (op0, 1);
518 /* If VALUE is a floating-point mode, access it as an integer of the
519 corresponding size. This can occur on a machine with 64 bit registers
520 that uses SFmode for float. This can also occur for unaligned float
522 if (GET_MODE_CLASS (GET_MODE (value)) == MODE_FLOAT)
524 if (GET_CODE (value) != REG)
525 value = copy_to_reg (value);
526 value = gen_rtx_SUBREG (word_mode, value, 0);
529 /* Now OFFSET is nonzero only if OP0 is memory
530 and is therefore always measured in bytes. */
533 && GET_MODE (value) != BLKmode
534 && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
535 /* Ensure insv's size is wide enough for this field. */
536 && (GET_MODE_BITSIZE (op_mode) >= bitsize)
537 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
538 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))))
540 int xbitpos = bitpos;
543 rtx last = get_last_insn ();
545 enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
546 int save_volatile_ok = volatile_ok;
550 /* If this machine's insv can only insert into a register, copy OP0
551 into a register and save it back later. */
552 /* This used to check flag_force_mem, but that was a serious
553 de-optimization now that flag_force_mem is enabled by -O2. */
554 if (GET_CODE (op0) == MEM
555 && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
559 enum machine_mode bestmode;
561 /* Get the mode to use for inserting into this field. If OP0 is
562 BLKmode, get the smallest mode consistent with the alignment. If
563 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
564 mode. Otherwise, use the smallest mode containing the field. */
566 if (GET_MODE (op0) == BLKmode
567 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
569 = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
570 MEM_VOLATILE_P (op0));
572 bestmode = GET_MODE (op0);
574 if (bestmode == VOIDmode
575 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
576 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
579 /* Adjust address to point to the containing unit of that mode.
580 Compute offset as multiple of this unit, counting in bytes. */
581 unit = GET_MODE_BITSIZE (bestmode);
582 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
583 bitpos = bitnum % unit;
584 op0 = adjust_address (op0, bestmode, offset);
586 /* Fetch that unit, store the bitfield in it, then store
588 tempreg = copy_to_reg (op0);
589 store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
591 emit_move_insn (op0, tempreg);
594 volatile_ok = save_volatile_ok;
596 /* Add OFFSET into OP0's address. */
597 if (GET_CODE (xop0) == MEM)
598 xop0 = adjust_address (xop0, byte_mode, offset);
600 /* If xop0 is a register, we need it in MAXMODE
601 to make it acceptable to the format of insv. */
602 if (GET_CODE (xop0) == SUBREG)
603 /* We can't just change the mode, because this might clobber op0,
604 and we will need the original value of op0 if insv fails. */
605 xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
606 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
607 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
609 /* On big-endian machines, we count bits from the most significant.
610 If the bit field insn does not, we must invert. */
612 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
613 xbitpos = unit - bitsize - xbitpos;
615 /* We have been counting XBITPOS within UNIT.
616 Count instead within the size of the register. */
617 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
618 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
620 unit = GET_MODE_BITSIZE (maxmode);
622 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */
624 if (GET_MODE (value) != maxmode)
626 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
628 /* Optimization: Don't bother really extending VALUE
629 if it has all the bits we will actually use. However,
630 if we must narrow it, be sure we do it correctly. */
632 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
633 value1 = simplify_gen_subreg (maxmode, value1,
634 GET_MODE (value1), 0);
636 value1 = gen_lowpart (maxmode, value1);
638 else if (GET_CODE (value) == CONST_INT)
639 value1 = GEN_INT (trunc_int_for_mode (INTVAL (value), maxmode));
640 else if (!CONSTANT_P (value))
641 /* Parse phase is supposed to make VALUE's data type
642 match that of the component reference, which is a type
643 at least as wide as the field; so VALUE should have
644 a mode that corresponds to that type. */
648 /* If this machine's insv insists on a register,
649 get VALUE1 into a register. */
650 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
652 value1 = force_reg (maxmode, value1);
654 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
659 delete_insns_since (last);
660 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
665 /* Insv is not available; store using shifts and boolean ops. */
666 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
670 /* Use shifts and boolean operations to store VALUE
671 into a bit field of width BITSIZE
672 in a memory location specified by OP0 except offset by OFFSET bytes.
673 (OFFSET must be 0 if OP0 is a register.)
674 The field starts at position BITPOS within the byte.
675 (If OP0 is a register, it may be a full word or a narrower mode,
676 but BITPOS still counts within a full word,
677 which is significant on bigendian machines.)
679 Note that protect_from_queue has already been done on OP0 and VALUE. */
682 store_fixed_bit_field (op0, offset, bitsize, bitpos, value)
684 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
687 enum machine_mode mode;
688 unsigned int total_bits = BITS_PER_WORD;
693 /* There is a case not handled here:
694 a structure with a known alignment of just a halfword
695 and a field split across two aligned halfwords within the structure.
696 Or likewise a structure with a known alignment of just a byte
697 and a field split across two bytes.
698 Such cases are not supposed to be able to occur. */
700 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
704 /* Special treatment for a bit field split across two registers. */
705 if (bitsize + bitpos > BITS_PER_WORD)
707 store_split_bit_field (op0, bitsize, bitpos, value);
713 /* Get the proper mode to use for this field. We want a mode that
714 includes the entire field. If such a mode would be larger than
715 a word, we won't be doing the extraction the normal way.
716 We don't want a mode bigger than the destination. */
718 mode = GET_MODE (op0);
719 if (GET_MODE_BITSIZE (mode) == 0
720 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
722 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
723 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
725 if (mode == VOIDmode)
727 /* The only way this should occur is if the field spans word
729 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
734 total_bits = GET_MODE_BITSIZE (mode);
736 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
737 be in the range 0 to total_bits-1, and put any excess bytes in
739 if (bitpos >= total_bits)
741 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
742 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
746 /* Get ref to an aligned byte, halfword, or word containing the field.
747 Adjust BITPOS to be position within a word,
748 and OFFSET to be the offset of that word.
749 Then alter OP0 to refer to that word. */
750 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
751 offset -= (offset % (total_bits / BITS_PER_UNIT));
752 op0 = adjust_address (op0, mode, offset);
755 mode = GET_MODE (op0);
757 /* Now MODE is either some integral mode for a MEM as OP0,
758 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
759 The bit field is contained entirely within OP0.
760 BITPOS is the starting bit number within OP0.
761 (OP0's mode may actually be narrower than MODE.) */
763 if (BYTES_BIG_ENDIAN)
764 /* BITPOS is the distance between our msb
765 and that of the containing datum.
766 Convert it to the distance from the lsb. */
767 bitpos = total_bits - bitsize - bitpos;
769 /* Now BITPOS is always the distance between our lsb
772 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
773 we must first convert its mode to MODE. */
775 if (GET_CODE (value) == CONST_INT)
777 HOST_WIDE_INT v = INTVAL (value);
779 if (bitsize < HOST_BITS_PER_WIDE_INT)
780 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
784 else if ((bitsize < HOST_BITS_PER_WIDE_INT
785 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
786 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
789 value = lshift_value (mode, value, bitpos, bitsize);
793 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
794 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
796 if (GET_MODE (value) != mode)
798 if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
799 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
800 value = gen_lowpart (mode, value);
802 value = convert_to_mode (mode, value, 1);
806 value = expand_binop (mode, and_optab, value,
807 mask_rtx (mode, 0, bitsize, 0),
808 NULL_RTX, 1, OPTAB_LIB_WIDEN);
810 value = expand_shift (LSHIFT_EXPR, mode, value,
811 build_int_2 (bitpos, 0), NULL_RTX, 1);
814 /* Now clear the chosen bits in OP0,
815 except that if VALUE is -1 we need not bother. */
817 subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
821 temp = expand_binop (mode, and_optab, op0,
822 mask_rtx (mode, bitpos, bitsize, 1),
823 subtarget, 1, OPTAB_LIB_WIDEN);
829 /* Now logical-or VALUE into OP0, unless it is zero. */
832 temp = expand_binop (mode, ior_optab, temp, value,
833 subtarget, 1, OPTAB_LIB_WIDEN);
835 emit_move_insn (op0, temp);
838 /* Store a bit field that is split across multiple accessible memory objects.
840 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
841 BITSIZE is the field width; BITPOS the position of its first bit
843 VALUE is the value to store.
845 This does not yet handle fields wider than BITS_PER_WORD. */
848 store_split_bit_field (op0, bitsize, bitpos, value)
850 unsigned HOST_WIDE_INT bitsize, bitpos;
854 unsigned int bitsdone = 0;
856 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
858 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
859 unit = BITS_PER_WORD;
861 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
863 /* If VALUE is a constant other than a CONST_INT, get it into a register in
864 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
865 that VALUE might be a floating-point constant. */
866 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
868 rtx word = gen_lowpart_common (word_mode, value);
870 if (word && (value != word))
873 value = gen_lowpart_common (word_mode,
874 force_reg (GET_MODE (value) != VOIDmode
876 : word_mode, value));
878 else if (GET_CODE (value) == ADDRESSOF)
879 value = copy_to_reg (value);
881 while (bitsdone < bitsize)
883 unsigned HOST_WIDE_INT thissize;
885 unsigned HOST_WIDE_INT thispos;
886 unsigned HOST_WIDE_INT offset;
888 offset = (bitpos + bitsdone) / unit;
889 thispos = (bitpos + bitsdone) % unit;
891 /* THISSIZE must not overrun a word boundary. Otherwise,
892 store_fixed_bit_field will call us again, and we will mutually
894 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
895 thissize = MIN (thissize, unit - thispos);
897 if (BYTES_BIG_ENDIAN)
901 /* We must do an endian conversion exactly the same way as it is
902 done in extract_bit_field, so that the two calls to
903 extract_fixed_bit_field will have comparable arguments. */
904 if (GET_CODE (value) != MEM || GET_MODE (value) == BLKmode)
905 total_bits = BITS_PER_WORD;
907 total_bits = GET_MODE_BITSIZE (GET_MODE (value));
909 /* Fetch successively less significant portions. */
910 if (GET_CODE (value) == CONST_INT)
911 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
912 >> (bitsize - bitsdone - thissize))
913 & (((HOST_WIDE_INT) 1 << thissize) - 1));
915 /* The args are chosen so that the last part includes the
916 lsb. Give extract_bit_field the value it needs (with
917 endianness compensation) to fetch the piece we want. */
918 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
919 total_bits - bitsize + bitsdone,
924 /* Fetch successively more significant portions. */
925 if (GET_CODE (value) == CONST_INT)
926 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
928 & (((HOST_WIDE_INT) 1 << thissize) - 1));
930 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
931 bitsdone, NULL_RTX, 1);
934 /* If OP0 is a register, then handle OFFSET here.
936 When handling multiword bitfields, extract_bit_field may pass
937 down a word_mode SUBREG of a larger REG for a bitfield that actually
938 crosses a word boundary. Thus, for a SUBREG, we must find
939 the current word starting from the base register. */
940 if (GET_CODE (op0) == SUBREG)
942 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
943 word = operand_subword_force (SUBREG_REG (op0), word_offset,
944 GET_MODE (SUBREG_REG (op0)));
947 else if (GET_CODE (op0) == REG)
949 word = operand_subword_force (op0, offset, GET_MODE (op0));
955 /* OFFSET is in UNITs, and UNIT is in bits.
956 store_fixed_bit_field wants offset in bytes. */
957 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
959 bitsdone += thissize;
963 /* Generate code to extract a byte-field from STR_RTX
964 containing BITSIZE bits, starting at BITNUM,
965 and put it in TARGET if possible (if TARGET is nonzero).
966 Regardless of TARGET, we return the rtx for where the value is placed.
969 STR_RTX is the structure containing the byte (a REG or MEM).
970 UNSIGNEDP is nonzero if this is an unsigned bit field.
971 MODE is the natural mode of the field value once extracted.
972 TMODE is the mode the caller would like the value to have;
973 but the value may be returned with type MODE instead.
975 TOTAL_SIZE is the size in bytes of the containing structure,
978 If a TARGET is specified and we can store in it at no extra cost,
979 we do so, and return TARGET.
980 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
981 if they are equally easy. */
984 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
985 target, mode, tmode, total_size)
987 unsigned HOST_WIDE_INT bitsize;
988 unsigned HOST_WIDE_INT bitnum;
991 enum machine_mode mode, tmode;
992 HOST_WIDE_INT total_size;
995 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
996 unsigned HOST_WIDE_INT offset = bitnum / unit;
997 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
999 rtx spec_target = target;
1000 rtx spec_target_subreg = 0;
1001 enum machine_mode int_mode;
1002 enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1003 enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1004 enum machine_mode mode1;
1007 /* Discount the part of the structure before the desired byte.
1008 We need to know how many bytes are safe to reference after it. */
1009 if (total_size >= 0)
1010 total_size -= (bitpos / BIGGEST_ALIGNMENT
1011 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
1013 if (tmode == VOIDmode)
1015 while (GET_CODE (op0) == SUBREG)
1017 int outer_size = GET_MODE_BITSIZE (GET_MODE (op0));
1018 int inner_size = GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (op0)));
1020 offset += SUBREG_BYTE (op0) / UNITS_PER_WORD;
1022 inner_size = MIN (inner_size, BITS_PER_WORD);
1024 if (BYTES_BIG_ENDIAN && (outer_size < inner_size))
1026 bitpos += inner_size - outer_size;
1029 offset += (bitpos / unit);
1034 op0 = SUBREG_REG (op0);
1037 if (GET_CODE (op0) == REG
1038 && mode == GET_MODE (op0)
1040 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1042 /* We're trying to extract a full register from itself. */
1046 /* Make sure we are playing with integral modes. Pun with subregs
1049 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1050 if (imode != GET_MODE (op0))
1052 if (GET_CODE (op0) == MEM)
1053 op0 = adjust_address (op0, imode, 0);
1054 else if (imode != BLKmode)
1055 op0 = gen_lowpart (imode, op0);
1061 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1062 If that's wrong, the solution is to test for it and set TARGET to 0
1065 /* If OP0 is a register, BITPOS must count within a word.
1066 But as we have it, it counts within whatever size OP0 now has.
1067 On a bigendian machine, these are not the same, so convert. */
1068 if (BYTES_BIG_ENDIAN
1069 && GET_CODE (op0) != MEM
1070 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1071 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1073 /* Extracting a full-word or multi-word value
1074 from a structure in a register or aligned memory.
1075 This can be done with just SUBREG.
1076 So too extracting a subword value in
1077 the least significant part of the register. */
1079 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
1080 + (offset * UNITS_PER_WORD);
1082 mode1 = (VECTOR_MODE_P (tmode)
1084 : mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0));
1086 if (((GET_CODE (op0) != MEM
1087 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1088 GET_MODE_BITSIZE (GET_MODE (op0)))
1089 && GET_MODE_SIZE (mode1) != 0
1090 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1091 || (GET_CODE (op0) == MEM
1092 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1093 || (offset * BITS_PER_UNIT % bitsize == 0
1094 && MEM_ALIGN (op0) % bitsize == 0))))
1095 && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1096 && bitpos % BITS_PER_WORD == 0)
1097 || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
1098 /* ??? The big endian test here is wrong. This is correct
1099 if the value is in a register, and if mode_for_size is not
1100 the same mode as op0. This causes us to get unnecessarily
1101 inefficient code from the Thumb port when -mbig-endian. */
1102 && (BYTES_BIG_ENDIAN
1103 ? bitpos + bitsize == BITS_PER_WORD
1106 if (mode1 != GET_MODE (op0))
1108 if (GET_CODE (op0) == SUBREG)
1110 if (GET_MODE (SUBREG_REG (op0)) == mode1
1111 || GET_MODE_CLASS (mode1) == MODE_INT
1112 || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1113 op0 = SUBREG_REG (op0);
1115 /* Else we've got some float mode source being extracted into
1116 a different float mode destination -- this combination of
1117 subregs results in Severe Tire Damage. */
1120 if (GET_CODE (op0) == REG)
1121 op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1123 op0 = adjust_address (op0, mode1, offset);
1126 return convert_to_mode (tmode, op0, unsignedp);
1130 /* Handle fields bigger than a word. */
1132 if (bitsize > BITS_PER_WORD)
1134 /* Here we transfer the words of the field
1135 in the order least significant first.
1136 This is because the most significant word is the one which may
1137 be less than full. */
1139 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1142 if (target == 0 || GET_CODE (target) != REG)
1143 target = gen_reg_rtx (mode);
1145 /* Indicate for flow that the entire target reg is being set. */
1146 emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1148 for (i = 0; i < nwords; i++)
1150 /* If I is 0, use the low-order word in both field and target;
1151 if I is 1, use the next to lowest word; and so on. */
1152 /* Word number in TARGET to use. */
1153 unsigned int wordnum
1155 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1157 /* Offset from start of field in OP0. */
1158 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1159 ? MAX (0, ((int) bitsize - ((int) i + 1)
1160 * (int) BITS_PER_WORD))
1161 : (int) i * BITS_PER_WORD);
1162 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1164 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1165 bitsize - i * BITS_PER_WORD),
1166 bitnum + bit_offset, 1, target_part, mode,
1167 word_mode, total_size);
1169 if (target_part == 0)
1172 if (result_part != target_part)
1173 emit_move_insn (target_part, result_part);
1178 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1179 need to be zero'd out. */
1180 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1182 unsigned int i, total_words;
1184 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1185 for (i = nwords; i < total_words; i++)
1187 (operand_subword (target,
1188 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1195 /* Signed bit field: sign-extend with two arithmetic shifts. */
1196 target = expand_shift (LSHIFT_EXPR, mode, target,
1197 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1199 return expand_shift (RSHIFT_EXPR, mode, target,
1200 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1204 /* From here on we know the desired field is smaller than a word. */
1206 /* Check if there is a correspondingly-sized integer field, so we can
1207 safely extract it as one size of integer, if necessary; then
1208 truncate or extend to the size that is wanted; then use SUBREGs or
1209 convert_to_mode to get one of the modes we really wanted. */
1211 int_mode = int_mode_for_mode (tmode);
1212 if (int_mode == BLKmode)
1213 int_mode = int_mode_for_mode (mode);
1214 if (int_mode == BLKmode)
1215 abort (); /* Should probably push op0 out to memory and then
1218 /* OFFSET is the number of words or bytes (UNIT says which)
1219 from STR_RTX to the first word or byte containing part of the field. */
1221 if (GET_CODE (op0) != MEM)
1224 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1226 if (GET_CODE (op0) != REG)
1227 op0 = copy_to_reg (op0);
1228 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1229 op0, (offset * UNITS_PER_WORD));
1234 op0 = protect_from_queue (str_rtx, 1);
1236 /* Now OFFSET is nonzero only for memory operands. */
1241 && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1242 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1243 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1245 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1246 rtx bitsize_rtx, bitpos_rtx;
1247 rtx last = get_last_insn ();
1249 rtx xtarget = target;
1250 rtx xspec_target = spec_target;
1251 rtx xspec_target_subreg = spec_target_subreg;
1253 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1255 if (GET_CODE (xop0) == MEM)
1257 int save_volatile_ok = volatile_ok;
1260 /* Is the memory operand acceptable? */
1261 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1262 (xop0, GET_MODE (xop0))))
1264 /* No, load into a reg and extract from there. */
1265 enum machine_mode bestmode;
1267 /* Get the mode to use for inserting into this field. If
1268 OP0 is BLKmode, get the smallest mode consistent with the
1269 alignment. If OP0 is a non-BLKmode object that is no
1270 wider than MAXMODE, use its mode. Otherwise, use the
1271 smallest mode containing the field. */
1273 if (GET_MODE (xop0) == BLKmode
1274 || (GET_MODE_SIZE (GET_MODE (op0))
1275 > GET_MODE_SIZE (maxmode)))
1276 bestmode = get_best_mode (bitsize, bitnum,
1277 MEM_ALIGN (xop0), maxmode,
1278 MEM_VOLATILE_P (xop0));
1280 bestmode = GET_MODE (xop0);
1282 if (bestmode == VOIDmode
1283 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1284 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1287 /* Compute offset as multiple of this unit,
1288 counting in bytes. */
1289 unit = GET_MODE_BITSIZE (bestmode);
1290 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1291 xbitpos = bitnum % unit;
1292 xop0 = adjust_address (xop0, bestmode, xoffset);
1294 /* Fetch it to a register in that size. */
1295 xop0 = force_reg (bestmode, xop0);
1297 /* XBITPOS counts within UNIT, which is what is expected. */
1300 /* Get ref to first byte containing part of the field. */
1301 xop0 = adjust_address (xop0, byte_mode, xoffset);
1303 volatile_ok = save_volatile_ok;
1306 /* If op0 is a register, we need it in MAXMODE (which is usually
1307 SImode). to make it acceptable to the format of extzv. */
1308 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1310 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1311 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1313 /* On big-endian machines, we count bits from the most significant.
1314 If the bit field insn does not, we must invert. */
1315 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1316 xbitpos = unit - bitsize - xbitpos;
1318 /* Now convert from counting within UNIT to counting in MAXMODE. */
1319 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1320 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1322 unit = GET_MODE_BITSIZE (maxmode);
1325 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1326 xtarget = xspec_target = gen_reg_rtx (tmode);
1328 if (GET_MODE (xtarget) != maxmode)
1330 if (GET_CODE (xtarget) == REG)
1332 int wider = (GET_MODE_SIZE (maxmode)
1333 > GET_MODE_SIZE (GET_MODE (xtarget)));
1334 xtarget = gen_lowpart (maxmode, xtarget);
1336 xspec_target_subreg = xtarget;
1339 xtarget = gen_reg_rtx (maxmode);
1342 /* If this machine's extzv insists on a register target,
1343 make sure we have one. */
1344 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1345 (xtarget, maxmode)))
1346 xtarget = gen_reg_rtx (maxmode);
1348 bitsize_rtx = GEN_INT (bitsize);
1349 bitpos_rtx = GEN_INT (xbitpos);
1351 pat = gen_extzv (protect_from_queue (xtarget, 1),
1352 xop0, bitsize_rtx, bitpos_rtx);
1357 spec_target = xspec_target;
1358 spec_target_subreg = xspec_target_subreg;
1362 delete_insns_since (last);
1363 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1369 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1375 && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1376 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1377 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1379 int xbitpos = bitpos, xoffset = offset;
1380 rtx bitsize_rtx, bitpos_rtx;
1381 rtx last = get_last_insn ();
1382 rtx xop0 = op0, xtarget = target;
1383 rtx xspec_target = spec_target;
1384 rtx xspec_target_subreg = spec_target_subreg;
1386 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1388 if (GET_CODE (xop0) == MEM)
1390 /* Is the memory operand acceptable? */
1391 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1392 (xop0, GET_MODE (xop0))))
1394 /* No, load into a reg and extract from there. */
1395 enum machine_mode bestmode;
1397 /* Get the mode to use for inserting into this field. If
1398 OP0 is BLKmode, get the smallest mode consistent with the
1399 alignment. If OP0 is a non-BLKmode object that is no
1400 wider than MAXMODE, use its mode. Otherwise, use the
1401 smallest mode containing the field. */
1403 if (GET_MODE (xop0) == BLKmode
1404 || (GET_MODE_SIZE (GET_MODE (op0))
1405 > GET_MODE_SIZE (maxmode)))
1406 bestmode = get_best_mode (bitsize, bitnum,
1407 MEM_ALIGN (xop0), maxmode,
1408 MEM_VOLATILE_P (xop0));
1410 bestmode = GET_MODE (xop0);
1412 if (bestmode == VOIDmode
1413 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1414 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1417 /* Compute offset as multiple of this unit,
1418 counting in bytes. */
1419 unit = GET_MODE_BITSIZE (bestmode);
1420 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1421 xbitpos = bitnum % unit;
1422 xop0 = adjust_address (xop0, bestmode, xoffset);
1424 /* Fetch it to a register in that size. */
1425 xop0 = force_reg (bestmode, xop0);
1427 /* XBITPOS counts within UNIT, which is what is expected. */
1430 /* Get ref to first byte containing part of the field. */
1431 xop0 = adjust_address (xop0, byte_mode, xoffset);
1434 /* If op0 is a register, we need it in MAXMODE (which is usually
1435 SImode) to make it acceptable to the format of extv. */
1436 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1438 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1439 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1441 /* On big-endian machines, we count bits from the most significant.
1442 If the bit field insn does not, we must invert. */
1443 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1444 xbitpos = unit - bitsize - xbitpos;
1446 /* XBITPOS counts within a size of UNIT.
1447 Adjust to count within a size of MAXMODE. */
1448 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1449 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1451 unit = GET_MODE_BITSIZE (maxmode);
1454 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1455 xtarget = xspec_target = gen_reg_rtx (tmode);
1457 if (GET_MODE (xtarget) != maxmode)
1459 if (GET_CODE (xtarget) == REG)
1461 int wider = (GET_MODE_SIZE (maxmode)
1462 > GET_MODE_SIZE (GET_MODE (xtarget)));
1463 xtarget = gen_lowpart (maxmode, xtarget);
1465 xspec_target_subreg = xtarget;
1468 xtarget = gen_reg_rtx (maxmode);
1471 /* If this machine's extv insists on a register target,
1472 make sure we have one. */
1473 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1474 (xtarget, maxmode)))
1475 xtarget = gen_reg_rtx (maxmode);
1477 bitsize_rtx = GEN_INT (bitsize);
1478 bitpos_rtx = GEN_INT (xbitpos);
1480 pat = gen_extv (protect_from_queue (xtarget, 1),
1481 xop0, bitsize_rtx, bitpos_rtx);
1486 spec_target = xspec_target;
1487 spec_target_subreg = xspec_target_subreg;
1491 delete_insns_since (last);
1492 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1498 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1501 if (target == spec_target)
1503 if (target == spec_target_subreg)
1505 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1507 /* If the target mode is floating-point, first convert to the
1508 integer mode of that size and then access it as a floating-point
1509 value via a SUBREG. */
1510 if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1512 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1515 if (GET_CODE (target) != REG)
1516 target = copy_to_reg (target);
1517 return gen_rtx_SUBREG (tmode, target, 0);
1520 return convert_to_mode (tmode, target, unsignedp);
1525 /* Extract a bit field using shifts and boolean operations
1526 Returns an rtx to represent the value.
1527 OP0 addresses a register (word) or memory (byte).
1528 BITPOS says which bit within the word or byte the bit field starts in.
1529 OFFSET says how many bytes farther the bit field starts;
1530 it is 0 if OP0 is a register.
1531 BITSIZE says how many bits long the bit field is.
1532 (If OP0 is a register, it may be narrower than a full word,
1533 but BITPOS still counts within a full word,
1534 which is significant on bigendian machines.)
1536 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1537 If TARGET is nonzero, attempts to store the value there
1538 and return TARGET, but this is not guaranteed.
1539 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1542 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1544 enum machine_mode tmode;
1546 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
1549 unsigned int total_bits = BITS_PER_WORD;
1550 enum machine_mode mode;
1552 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1554 /* Special treatment for a bit field split across two registers. */
1555 if (bitsize + bitpos > BITS_PER_WORD)
1556 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1560 /* Get the proper mode to use for this field. We want a mode that
1561 includes the entire field. If such a mode would be larger than
1562 a word, we won't be doing the extraction the normal way. */
1564 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1565 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1567 if (mode == VOIDmode)
1568 /* The only way this should occur is if the field spans word
1570 return extract_split_bit_field (op0, bitsize,
1571 bitpos + offset * BITS_PER_UNIT,
1574 total_bits = GET_MODE_BITSIZE (mode);
1576 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1577 be in the range 0 to total_bits-1, and put any excess bytes in
1579 if (bitpos >= total_bits)
1581 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1582 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1586 /* Get ref to an aligned byte, halfword, or word containing the field.
1587 Adjust BITPOS to be position within a word,
1588 and OFFSET to be the offset of that word.
1589 Then alter OP0 to refer to that word. */
1590 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1591 offset -= (offset % (total_bits / BITS_PER_UNIT));
1592 op0 = adjust_address (op0, mode, offset);
1595 mode = GET_MODE (op0);
1597 if (BYTES_BIG_ENDIAN)
1598 /* BITPOS is the distance between our msb and that of OP0.
1599 Convert it to the distance from the lsb. */
1600 bitpos = total_bits - bitsize - bitpos;
1602 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1603 We have reduced the big-endian case to the little-endian case. */
1609 /* If the field does not already start at the lsb,
1610 shift it so it does. */
1611 tree amount = build_int_2 (bitpos, 0);
1612 /* Maybe propagate the target for the shift. */
1613 /* But not if we will return it--could confuse integrate.c. */
1614 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1615 && !REG_FUNCTION_VALUE_P (target)
1617 if (tmode != mode) subtarget = 0;
1618 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1620 /* Convert the value to the desired mode. */
1622 op0 = convert_to_mode (tmode, op0, 1);
1624 /* Unless the msb of the field used to be the msb when we shifted,
1625 mask out the upper bits. */
1627 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1628 return expand_binop (GET_MODE (op0), and_optab, op0,
1629 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1630 target, 1, OPTAB_LIB_WIDEN);
1634 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1635 then arithmetic-shift its lsb to the lsb of the word. */
1636 op0 = force_reg (mode, op0);
1640 /* Find the narrowest integer mode that contains the field. */
1642 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1643 mode = GET_MODE_WIDER_MODE (mode))
1644 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1646 op0 = convert_to_mode (mode, op0, 0);
1650 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1653 = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1654 /* Maybe propagate the target for the shift. */
1655 /* But not if we will return the result--could confuse integrate.c. */
1656 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1657 && ! REG_FUNCTION_VALUE_P (target)
1659 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1662 return expand_shift (RSHIFT_EXPR, mode, op0,
1663 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1667 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1668 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1669 complement of that if COMPLEMENT. The mask is truncated if
1670 necessary to the width of mode MODE. The mask is zero-extended if
1671 BITSIZE+BITPOS is too small for MODE. */
1674 mask_rtx (mode, bitpos, bitsize, complement)
1675 enum machine_mode mode;
1676 int bitpos, bitsize, complement;
1678 HOST_WIDE_INT masklow, maskhigh;
1680 if (bitpos < HOST_BITS_PER_WIDE_INT)
1681 masklow = (HOST_WIDE_INT) -1 << bitpos;
1685 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1686 masklow &= ((unsigned HOST_WIDE_INT) -1
1687 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1689 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1692 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1694 if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1695 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1696 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1702 maskhigh = ~maskhigh;
1706 return immed_double_const (masklow, maskhigh, mode);
1709 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1710 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1713 lshift_value (mode, value, bitpos, bitsize)
1714 enum machine_mode mode;
1716 int bitpos, bitsize;
1718 unsigned HOST_WIDE_INT v = INTVAL (value);
1719 HOST_WIDE_INT low, high;
1721 if (bitsize < HOST_BITS_PER_WIDE_INT)
1722 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1724 if (bitpos < HOST_BITS_PER_WIDE_INT)
1727 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1732 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1735 return immed_double_const (low, high, mode);
1738 /* Extract a bit field that is split across two words
1739 and return an RTX for the result.
1741 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1742 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1743 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1746 extract_split_bit_field (op0, bitsize, bitpos, unsignedp)
1748 unsigned HOST_WIDE_INT bitsize, bitpos;
1752 unsigned int bitsdone = 0;
1753 rtx result = NULL_RTX;
1756 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1758 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1759 unit = BITS_PER_WORD;
1761 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1763 while (bitsdone < bitsize)
1765 unsigned HOST_WIDE_INT thissize;
1767 unsigned HOST_WIDE_INT thispos;
1768 unsigned HOST_WIDE_INT offset;
1770 offset = (bitpos + bitsdone) / unit;
1771 thispos = (bitpos + bitsdone) % unit;
1773 /* THISSIZE must not overrun a word boundary. Otherwise,
1774 extract_fixed_bit_field will call us again, and we will mutually
1776 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1777 thissize = MIN (thissize, unit - thispos);
1779 /* If OP0 is a register, then handle OFFSET here.
1781 When handling multiword bitfields, extract_bit_field may pass
1782 down a word_mode SUBREG of a larger REG for a bitfield that actually
1783 crosses a word boundary. Thus, for a SUBREG, we must find
1784 the current word starting from the base register. */
1785 if (GET_CODE (op0) == SUBREG)
1787 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1788 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1789 GET_MODE (SUBREG_REG (op0)));
1792 else if (GET_CODE (op0) == REG)
1794 word = operand_subword_force (op0, offset, GET_MODE (op0));
1800 /* Extract the parts in bit-counting order,
1801 whose meaning is determined by BYTES_PER_UNIT.
1802 OFFSET is in UNITs, and UNIT is in bits.
1803 extract_fixed_bit_field wants offset in bytes. */
1804 part = extract_fixed_bit_field (word_mode, word,
1805 offset * unit / BITS_PER_UNIT,
1806 thissize, thispos, 0, 1);
1807 bitsdone += thissize;
1809 /* Shift this part into place for the result. */
1810 if (BYTES_BIG_ENDIAN)
1812 if (bitsize != bitsdone)
1813 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1814 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1818 if (bitsdone != thissize)
1819 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1820 build_int_2 (bitsdone - thissize, 0), 0, 1);
1826 /* Combine the parts with bitwise or. This works
1827 because we extracted each part as an unsigned bit field. */
1828 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1834 /* Unsigned bit field: we are done. */
1837 /* Signed bit field: sign-extend with two arithmetic shifts. */
1838 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1839 build_int_2 (BITS_PER_WORD - bitsize, 0),
1841 return expand_shift (RSHIFT_EXPR, word_mode, result,
1842 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1845 /* Add INC into TARGET. */
1848 expand_inc (target, inc)
1851 rtx value = expand_binop (GET_MODE (target), add_optab,
1853 target, 0, OPTAB_LIB_WIDEN);
1854 if (value != target)
1855 emit_move_insn (target, value);
1858 /* Subtract DEC from TARGET. */
1861 expand_dec (target, dec)
1864 rtx value = expand_binop (GET_MODE (target), sub_optab,
1866 target, 0, OPTAB_LIB_WIDEN);
1867 if (value != target)
1868 emit_move_insn (target, value);
1871 /* Output a shift instruction for expression code CODE,
1872 with SHIFTED being the rtx for the value to shift,
1873 and AMOUNT the tree for the amount to shift by.
1874 Store the result in the rtx TARGET, if that is convenient.
1875 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1876 Return the rtx for where the value is. */
1879 expand_shift (code, mode, shifted, amount, target, unsignedp)
1880 enum tree_code code;
1881 enum machine_mode mode;
1888 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1889 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1892 /* Previously detected shift-counts computed by NEGATE_EXPR
1893 and shifted in the other direction; but that does not work
1896 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1898 #ifdef SHIFT_COUNT_TRUNCATED
1899 if (SHIFT_COUNT_TRUNCATED)
1901 if (GET_CODE (op1) == CONST_INT
1902 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
1903 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
1904 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
1905 % GET_MODE_BITSIZE (mode));
1906 else if (GET_CODE (op1) == SUBREG
1907 && SUBREG_BYTE (op1) == 0)
1908 op1 = SUBREG_REG (op1);
1912 if (op1 == const0_rtx)
1915 for (try = 0; temp == 0 && try < 3; try++)
1917 enum optab_methods methods;
1920 methods = OPTAB_DIRECT;
1922 methods = OPTAB_WIDEN;
1924 methods = OPTAB_LIB_WIDEN;
1928 /* Widening does not work for rotation. */
1929 if (methods == OPTAB_WIDEN)
1931 else if (methods == OPTAB_LIB_WIDEN)
1933 /* If we have been unable to open-code this by a rotation,
1934 do it as the IOR of two shifts. I.e., to rotate A
1935 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
1936 where C is the bitsize of A.
1938 It is theoretically possible that the target machine might
1939 not be able to perform either shift and hence we would
1940 be making two libcalls rather than just the one for the
1941 shift (similarly if IOR could not be done). We will allow
1942 this extremely unlikely lossage to avoid complicating the
1945 rtx subtarget = target == shifted ? 0 : target;
1947 tree type = TREE_TYPE (amount);
1948 tree new_amount = make_tree (type, op1);
1950 = fold (build (MINUS_EXPR, type,
1952 build_int_2 (GET_MODE_BITSIZE (mode),
1956 shifted = force_reg (mode, shifted);
1958 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
1959 mode, shifted, new_amount, subtarget, 1);
1960 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
1961 mode, shifted, other_amount, 0, 1);
1962 return expand_binop (mode, ior_optab, temp, temp1, target,
1963 unsignedp, methods);
1966 temp = expand_binop (mode,
1967 left ? rotl_optab : rotr_optab,
1968 shifted, op1, target, unsignedp, methods);
1970 /* If we don't have the rotate, but we are rotating by a constant
1971 that is in range, try a rotate in the opposite direction. */
1973 if (temp == 0 && GET_CODE (op1) == CONST_INT
1975 && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
1976 temp = expand_binop (mode,
1977 left ? rotr_optab : rotl_optab,
1979 GEN_INT (GET_MODE_BITSIZE (mode)
1981 target, unsignedp, methods);
1984 temp = expand_binop (mode,
1985 left ? ashl_optab : lshr_optab,
1986 shifted, op1, target, unsignedp, methods);
1988 /* Do arithmetic shifts.
1989 Also, if we are going to widen the operand, we can just as well
1990 use an arithmetic right-shift instead of a logical one. */
1991 if (temp == 0 && ! rotate
1992 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
1994 enum optab_methods methods1 = methods;
1996 /* If trying to widen a log shift to an arithmetic shift,
1997 don't accept an arithmetic shift of the same size. */
1999 methods1 = OPTAB_MUST_WIDEN;
2001 /* Arithmetic shift */
2003 temp = expand_binop (mode,
2004 left ? ashl_optab : ashr_optab,
2005 shifted, op1, target, unsignedp, methods1);
2008 /* We used to try extzv here for logical right shifts, but that was
2009 only useful for one machine, the VAX, and caused poor code
2010 generation there for lshrdi3, so the code was deleted and a
2011 define_expand for lshrsi3 was added to vax.md. */
2019 enum alg_code { alg_zero, alg_m, alg_shift,
2020 alg_add_t_m2, alg_sub_t_m2,
2021 alg_add_factor, alg_sub_factor,
2022 alg_add_t2_m, alg_sub_t2_m,
2023 alg_add, alg_subtract, alg_factor, alg_shiftop };
2025 /* This structure records a sequence of operations.
2026 `ops' is the number of operations recorded.
2027 `cost' is their total cost.
2028 The operations are stored in `op' and the corresponding
2029 logarithms of the integer coefficients in `log'.
2031 These are the operations:
2032 alg_zero total := 0;
2033 alg_m total := multiplicand;
2034 alg_shift total := total * coeff
2035 alg_add_t_m2 total := total + multiplicand * coeff;
2036 alg_sub_t_m2 total := total - multiplicand * coeff;
2037 alg_add_factor total := total * coeff + total;
2038 alg_sub_factor total := total * coeff - total;
2039 alg_add_t2_m total := total * coeff + multiplicand;
2040 alg_sub_t2_m total := total * coeff - multiplicand;
2042 The first operand must be either alg_zero or alg_m. */
2048 /* The size of the OP and LOG fields are not directly related to the
2049 word size, but the worst-case algorithms will be if we have few
2050 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2051 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2052 in total wordsize operations. */
2053 enum alg_code op[MAX_BITS_PER_WORD];
2054 char log[MAX_BITS_PER_WORD];
2057 static void synth_mult PARAMS ((struct algorithm *,
2058 unsigned HOST_WIDE_INT,
2060 static unsigned HOST_WIDE_INT choose_multiplier PARAMS ((unsigned HOST_WIDE_INT,
2062 unsigned HOST_WIDE_INT *,
2064 static unsigned HOST_WIDE_INT invert_mod2n PARAMS ((unsigned HOST_WIDE_INT,
2066 /* Compute and return the best algorithm for multiplying by T.
2067 The algorithm must cost less than cost_limit
2068 If retval.cost >= COST_LIMIT, no algorithm was found and all
2069 other field of the returned struct are undefined. */
2072 synth_mult (alg_out, t, cost_limit)
2073 struct algorithm *alg_out;
2074 unsigned HOST_WIDE_INT t;
2078 struct algorithm *alg_in, *best_alg;
2080 unsigned HOST_WIDE_INT q;
2082 /* Indicate that no algorithm is yet found. If no algorithm
2083 is found, this value will be returned and indicate failure. */
2084 alg_out->cost = cost_limit;
2086 if (cost_limit <= 0)
2089 /* t == 1 can be done in zero cost. */
2094 alg_out->op[0] = alg_m;
2098 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2102 if (zero_cost >= cost_limit)
2107 alg_out->cost = zero_cost;
2108 alg_out->op[0] = alg_zero;
2113 /* We'll be needing a couple extra algorithm structures now. */
2115 alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
2116 best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
2118 /* If we have a group of zero bits at the low-order part of T, try
2119 multiplying by the remaining bits and then doing a shift. */
2123 m = floor_log2 (t & -t); /* m = number of low zero bits */
2124 if (m < BITS_PER_WORD)
2127 cost = shift_cost[m];
2128 synth_mult (alg_in, q, cost_limit - cost);
2130 cost += alg_in->cost;
2131 if (cost < cost_limit)
2133 struct algorithm *x;
2134 x = alg_in, alg_in = best_alg, best_alg = x;
2135 best_alg->log[best_alg->ops] = m;
2136 best_alg->op[best_alg->ops] = alg_shift;
2142 /* If we have an odd number, add or subtract one. */
2145 unsigned HOST_WIDE_INT w;
2147 for (w = 1; (w & t) != 0; w <<= 1)
2149 /* If T was -1, then W will be zero after the loop. This is another
2150 case where T ends with ...111. Handling this with (T + 1) and
2151 subtract 1 produces slightly better code and results in algorithm
2152 selection much faster than treating it like the ...0111 case
2156 /* Reject the case where t is 3.
2157 Thus we prefer addition in that case. */
2160 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2163 synth_mult (alg_in, t + 1, cost_limit - cost);
2165 cost += alg_in->cost;
2166 if (cost < cost_limit)
2168 struct algorithm *x;
2169 x = alg_in, alg_in = best_alg, best_alg = x;
2170 best_alg->log[best_alg->ops] = 0;
2171 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2177 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2180 synth_mult (alg_in, t - 1, cost_limit - cost);
2182 cost += alg_in->cost;
2183 if (cost < cost_limit)
2185 struct algorithm *x;
2186 x = alg_in, alg_in = best_alg, best_alg = x;
2187 best_alg->log[best_alg->ops] = 0;
2188 best_alg->op[best_alg->ops] = alg_add_t_m2;
2194 /* Look for factors of t of the form
2195 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2196 If we find such a factor, we can multiply by t using an algorithm that
2197 multiplies by q, shift the result by m and add/subtract it to itself.
2199 We search for large factors first and loop down, even if large factors
2200 are less probable than small; if we find a large factor we will find a
2201 good sequence quickly, and therefore be able to prune (by decreasing
2202 COST_LIMIT) the search. */
2204 for (m = floor_log2 (t - 1); m >= 2; m--)
2206 unsigned HOST_WIDE_INT d;
2208 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2209 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2211 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2212 synth_mult (alg_in, t / d, cost_limit - cost);
2214 cost += alg_in->cost;
2215 if (cost < cost_limit)
2217 struct algorithm *x;
2218 x = alg_in, alg_in = best_alg, best_alg = x;
2219 best_alg->log[best_alg->ops] = m;
2220 best_alg->op[best_alg->ops] = alg_add_factor;
2223 /* Other factors will have been taken care of in the recursion. */
2227 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2228 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2230 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2231 synth_mult (alg_in, t / d, cost_limit - cost);
2233 cost += alg_in->cost;
2234 if (cost < cost_limit)
2236 struct algorithm *x;
2237 x = alg_in, alg_in = best_alg, best_alg = x;
2238 best_alg->log[best_alg->ops] = m;
2239 best_alg->op[best_alg->ops] = alg_sub_factor;
2246 /* Try shift-and-add (load effective address) instructions,
2247 i.e. do a*3, a*5, a*9. */
2253 if (m >= 0 && m < BITS_PER_WORD)
2255 cost = shiftadd_cost[m];
2256 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2258 cost += alg_in->cost;
2259 if (cost < cost_limit)
2261 struct algorithm *x;
2262 x = alg_in, alg_in = best_alg, best_alg = x;
2263 best_alg->log[best_alg->ops] = m;
2264 best_alg->op[best_alg->ops] = alg_add_t2_m;
2272 if (m >= 0 && m < BITS_PER_WORD)
2274 cost = shiftsub_cost[m];
2275 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2277 cost += alg_in->cost;
2278 if (cost < cost_limit)
2280 struct algorithm *x;
2281 x = alg_in, alg_in = best_alg, best_alg = x;
2282 best_alg->log[best_alg->ops] = m;
2283 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2289 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2290 we have not found any algorithm. */
2291 if (cost_limit == alg_out->cost)
2294 /* If we are getting a too long sequence for `struct algorithm'
2295 to record, make this search fail. */
2296 if (best_alg->ops == MAX_BITS_PER_WORD)
2299 /* Copy the algorithm from temporary space to the space at alg_out.
2300 We avoid using structure assignment because the majority of
2301 best_alg is normally undefined, and this is a critical function. */
2302 alg_out->ops = best_alg->ops + 1;
2303 alg_out->cost = cost_limit;
2304 memcpy (alg_out->op, best_alg->op,
2305 alg_out->ops * sizeof *alg_out->op);
2306 memcpy (alg_out->log, best_alg->log,
2307 alg_out->ops * sizeof *alg_out->log);
2310 /* Perform a multiplication and return an rtx for the result.
2311 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2312 TARGET is a suggestion for where to store the result (an rtx).
2314 We check specially for a constant integer as OP1.
2315 If you want this check for OP0 as well, then before calling
2316 you should swap the two operands if OP0 would be constant. */
2319 expand_mult (mode, op0, op1, target, unsignedp)
2320 enum machine_mode mode;
2321 rtx op0, op1, target;
2324 rtx const_op1 = op1;
2326 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2327 less than or equal in size to `unsigned int' this doesn't matter.
2328 If the mode is larger than `unsigned int', then synth_mult works only
2329 if the constant value exactly fits in an `unsigned int' without any
2330 truncation. This means that multiplying by negative values does
2331 not work; results are off by 2^32 on a 32 bit machine. */
2333 /* If we are multiplying in DImode, it may still be a win
2334 to try to work with shifts and adds. */
2335 if (GET_CODE (op1) == CONST_DOUBLE
2336 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2337 && HOST_BITS_PER_INT >= BITS_PER_WORD
2338 && CONST_DOUBLE_HIGH (op1) == 0)
2339 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2340 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2341 && GET_CODE (op1) == CONST_INT
2342 && INTVAL (op1) < 0)
2345 /* We used to test optimize here, on the grounds that it's better to
2346 produce a smaller program when -O is not used.
2347 But this causes such a terrible slowdown sometimes
2348 that it seems better to use synth_mult always. */
2350 if (const_op1 && GET_CODE (const_op1) == CONST_INT
2351 && (unsignedp || ! flag_trapv))
2353 struct algorithm alg;
2354 struct algorithm alg2;
2355 HOST_WIDE_INT val = INTVAL (op1);
2356 HOST_WIDE_INT val_so_far;
2359 enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2361 /* op0 must be register to make mult_cost match the precomputed
2362 shiftadd_cost array. */
2363 op0 = force_reg (mode, op0);
2365 /* Try to do the computation three ways: multiply by the negative of OP1
2366 and then negate, do the multiplication directly, or do multiplication
2369 mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2370 mult_cost = MIN (12 * add_cost, mult_cost);
2372 synth_mult (&alg, val, mult_cost);
2374 /* This works only if the inverted value actually fits in an
2376 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2378 synth_mult (&alg2, - val,
2379 (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2380 if (alg2.cost + negate_cost < alg.cost)
2381 alg = alg2, variant = negate_variant;
2384 /* This proves very useful for division-by-constant. */
2385 synth_mult (&alg2, val - 1,
2386 (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2387 if (alg2.cost + add_cost < alg.cost)
2388 alg = alg2, variant = add_variant;
2390 if (alg.cost < mult_cost)
2392 /* We found something cheaper than a multiply insn. */
2395 enum machine_mode nmode;
2397 op0 = protect_from_queue (op0, 0);
2399 /* Avoid referencing memory over and over.
2400 For speed, but also for correctness when mem is volatile. */
2401 if (GET_CODE (op0) == MEM)
2402 op0 = force_reg (mode, op0);
2404 /* ACCUM starts out either as OP0 or as a zero, depending on
2405 the first operation. */
2407 if (alg.op[0] == alg_zero)
2409 accum = copy_to_mode_reg (mode, const0_rtx);
2412 else if (alg.op[0] == alg_m)
2414 accum = copy_to_mode_reg (mode, op0);
2420 for (opno = 1; opno < alg.ops; opno++)
2422 int log = alg.log[opno];
2423 int preserve = preserve_subexpressions_p ();
2424 rtx shift_subtarget = preserve ? 0 : accum;
2426 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2429 rtx accum_target = preserve ? 0 : accum;
2431 switch (alg.op[opno])
2434 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2435 build_int_2 (log, 0), NULL_RTX, 0);
2440 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2441 build_int_2 (log, 0), NULL_RTX, 0);
2442 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2444 ? add_target : accum_target);
2445 val_so_far += (HOST_WIDE_INT) 1 << log;
2449 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2450 build_int_2 (log, 0), NULL_RTX, 0);
2451 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2453 ? add_target : accum_target);
2454 val_so_far -= (HOST_WIDE_INT) 1 << log;
2458 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2459 build_int_2 (log, 0), shift_subtarget,
2461 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2463 ? add_target : accum_target);
2464 val_so_far = (val_so_far << log) + 1;
2468 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2469 build_int_2 (log, 0), shift_subtarget,
2471 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2473 ? add_target : accum_target);
2474 val_so_far = (val_so_far << log) - 1;
2477 case alg_add_factor:
2478 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2479 build_int_2 (log, 0), NULL_RTX, 0);
2480 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2482 ? add_target : accum_target);
2483 val_so_far += val_so_far << log;
2486 case alg_sub_factor:
2487 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2488 build_int_2 (log, 0), NULL_RTX, 0);
2489 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2490 (add_target ? add_target
2491 : preserve ? 0 : tem));
2492 val_so_far = (val_so_far << log) - val_so_far;
2499 /* Write a REG_EQUAL note on the last insn so that we can cse
2500 multiplication sequences. Note that if ACCUM is a SUBREG,
2501 we've set the inner register and must properly indicate
2504 tem = op0, nmode = mode;
2505 if (GET_CODE (accum) == SUBREG)
2507 nmode = GET_MODE (SUBREG_REG (accum));
2508 tem = gen_lowpart (nmode, op0);
2511 insn = get_last_insn ();
2512 set_unique_reg_note (insn,
2514 gen_rtx_MULT (nmode, tem,
2515 GEN_INT (val_so_far)));
2518 if (variant == negate_variant)
2520 val_so_far = - val_so_far;
2521 accum = expand_unop (mode, neg_optab, accum, target, 0);
2523 else if (variant == add_variant)
2525 val_so_far = val_so_far + 1;
2526 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2529 if (val != val_so_far)
2536 /* This used to use umul_optab if unsigned, but for non-widening multiply
2537 there is no difference between signed and unsigned. */
2538 op0 = expand_binop (mode,
2540 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2541 ? smulv_optab : smul_optab,
2542 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2548 /* Return the smallest n such that 2**n >= X. */
2552 unsigned HOST_WIDE_INT x;
2554 return floor_log2 (x - 1) + 1;
2557 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2558 replace division by D, and put the least significant N bits of the result
2559 in *MULTIPLIER_PTR and return the most significant bit.
2561 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2562 needed precision is in PRECISION (should be <= N).
2564 PRECISION should be as small as possible so this function can choose
2565 multiplier more freely.
2567 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2568 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2570 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2571 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2574 unsigned HOST_WIDE_INT
2575 choose_multiplier (d, n, precision, multiplier_ptr, post_shift_ptr, lgup_ptr)
2576 unsigned HOST_WIDE_INT d;
2579 unsigned HOST_WIDE_INT *multiplier_ptr;
2580 int *post_shift_ptr;
2583 HOST_WIDE_INT mhigh_hi, mlow_hi;
2584 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2585 int lgup, post_shift;
2587 unsigned HOST_WIDE_INT nl, dummy1;
2588 HOST_WIDE_INT nh, dummy2;
2590 /* lgup = ceil(log2(divisor)); */
2591 lgup = ceil_log2 (d);
2597 pow2 = n + lgup - precision;
2599 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2601 /* We could handle this with some effort, but this case is much better
2602 handled directly with a scc insn, so rely on caller using that. */
2606 /* mlow = 2^(N + lgup)/d */
2607 if (pow >= HOST_BITS_PER_WIDE_INT)
2609 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2615 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2617 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2618 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2620 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2621 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2622 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2624 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2625 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2626 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2628 if (mhigh_hi && nh - d >= d)
2630 if (mhigh_hi > 1 || mlow_hi > 1)
2632 /* assert that mlow < mhigh. */
2633 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2636 /* If precision == N, then mlow, mhigh exceed 2^N
2637 (but they do not exceed 2^(N+1)). */
2639 /* Reduce to lowest terms */
2640 for (post_shift = lgup; post_shift > 0; post_shift--)
2642 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2643 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2653 *post_shift_ptr = post_shift;
2655 if (n < HOST_BITS_PER_WIDE_INT)
2657 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2658 *multiplier_ptr = mhigh_lo & mask;
2659 return mhigh_lo >= mask;
2663 *multiplier_ptr = mhigh_lo;
2668 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2669 congruent to 1 (mod 2**N). */
2671 static unsigned HOST_WIDE_INT
2673 unsigned HOST_WIDE_INT x;
2676 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2678 /* The algorithm notes that the choice y = x satisfies
2679 x*y == 1 mod 2^3, since x is assumed odd.
2680 Each iteration doubles the number of bits of significance in y. */
2682 unsigned HOST_WIDE_INT mask;
2683 unsigned HOST_WIDE_INT y = x;
2686 mask = (n == HOST_BITS_PER_WIDE_INT
2687 ? ~(unsigned HOST_WIDE_INT) 0
2688 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2692 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2698 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2699 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2700 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2701 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2704 The result is put in TARGET if that is convenient.
2706 MODE is the mode of operation. */
2709 expand_mult_highpart_adjust (mode, adj_operand, op0, op1, target, unsignedp)
2710 enum machine_mode mode;
2711 rtx adj_operand, op0, op1, target;
2715 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2717 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2718 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2720 tem = expand_and (mode, tem, op1, NULL_RTX);
2722 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2725 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2726 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2728 tem = expand_and (mode, tem, op0, NULL_RTX);
2729 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2735 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2736 in TARGET if that is convenient, and return where the result is. If the
2737 operation can not be performed, 0 is returned.
2739 MODE is the mode of operation and result.
2741 UNSIGNEDP nonzero means unsigned multiply.
2743 MAX_COST is the total allowed cost for the expanded RTL. */
2746 expand_mult_highpart (mode, op0, cnst1, target, unsignedp, max_cost)
2747 enum machine_mode mode;
2749 unsigned HOST_WIDE_INT cnst1;
2753 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2754 optab mul_highpart_optab;
2757 int size = GET_MODE_BITSIZE (mode);
2760 /* We can't support modes wider than HOST_BITS_PER_INT. */
2761 if (size > HOST_BITS_PER_WIDE_INT)
2764 op1 = GEN_INT (trunc_int_for_mode (cnst1, mode));
2767 = immed_double_const (cnst1,
2770 : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2773 /* expand_mult handles constant multiplication of word_mode
2774 or narrower. It does a poor job for large modes. */
2775 if (size < BITS_PER_WORD
2776 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2778 /* We have to do this, since expand_binop doesn't do conversion for
2779 multiply. Maybe change expand_binop to handle widening multiply? */
2780 op0 = convert_to_mode (wider_mode, op0, unsignedp);
2782 /* We know that this can't have signed overflow, so pretend this is
2783 an unsigned multiply. */
2784 tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, 0);
2785 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2786 build_int_2 (size, 0), NULL_RTX, 1);
2787 return convert_modes (mode, wider_mode, tem, unsignedp);
2791 target = gen_reg_rtx (mode);
2793 /* Firstly, try using a multiplication insn that only generates the needed
2794 high part of the product, and in the sign flavor of unsignedp. */
2795 if (mul_highpart_cost[(int) mode] < max_cost)
2797 mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2798 target = expand_binop (mode, mul_highpart_optab,
2799 op0, op1, target, unsignedp, OPTAB_DIRECT);
2804 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2805 Need to adjust the result after the multiplication. */
2806 if (size - 1 < BITS_PER_WORD
2807 && (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost
2810 mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2811 target = expand_binop (mode, mul_highpart_optab,
2812 op0, op1, target, unsignedp, OPTAB_DIRECT);
2814 /* We used the wrong signedness. Adjust the result. */
2815 return expand_mult_highpart_adjust (mode, target, op0,
2816 op1, target, unsignedp);
2819 /* Try widening multiplication. */
2820 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2821 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2822 && mul_widen_cost[(int) wider_mode] < max_cost)
2824 op1 = force_reg (mode, op1);
2828 /* Try widening the mode and perform a non-widening multiplication. */
2829 moptab = smul_optab;
2830 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2831 && size - 1 < BITS_PER_WORD
2832 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2838 /* Try widening multiplication of opposite signedness, and adjust. */
2839 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2840 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2841 && size - 1 < BITS_PER_WORD
2842 && (mul_widen_cost[(int) wider_mode]
2843 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2845 rtx regop1 = force_reg (mode, op1);
2846 tem = expand_binop (wider_mode, moptab, op0, regop1,
2847 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2850 /* Extract the high half of the just generated product. */
2851 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2852 build_int_2 (size, 0), NULL_RTX, 1);
2853 tem = convert_modes (mode, wider_mode, tem, unsignedp);
2854 /* We used the wrong signedness. Adjust the result. */
2855 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2863 /* Pass NULL_RTX as target since TARGET has wrong mode. */
2864 tem = expand_binop (wider_mode, moptab, op0, op1,
2865 NULL_RTX, unsignedp, OPTAB_WIDEN);
2869 /* Extract the high half of the just generated product. */
2870 if (mode == word_mode)
2872 return gen_highpart (mode, tem);
2876 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2877 build_int_2 (size, 0), NULL_RTX, 1);
2878 return convert_modes (mode, wider_mode, tem, unsignedp);
2882 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2883 if that is convenient, and returning where the result is.
2884 You may request either the quotient or the remainder as the result;
2885 specify REM_FLAG nonzero to get the remainder.
2887 CODE is the expression code for which kind of division this is;
2888 it controls how rounding is done. MODE is the machine mode to use.
2889 UNSIGNEDP nonzero means do unsigned division. */
2891 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2892 and then correct it by or'ing in missing high bits
2893 if result of ANDI is nonzero.
2894 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2895 This could optimize to a bfexts instruction.
2896 But C doesn't use these operations, so their optimizations are
2898 /* ??? For modulo, we don't actually need the highpart of the first product,
2899 the low part will do nicely. And for small divisors, the second multiply
2900 can also be a low-part only multiply or even be completely left out.
2901 E.g. to calculate the remainder of a division by 3 with a 32 bit
2902 multiply, multiply with 0x55555556 and extract the upper two bits;
2903 the result is exact for inputs up to 0x1fffffff.
2904 The input range can be reduced by using cross-sum rules.
2905 For odd divisors >= 3, the following table gives right shift counts
2906 so that if an number is shifted by an integer multiple of the given
2907 amount, the remainder stays the same:
2908 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
2909 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
2910 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
2911 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
2912 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
2914 Cross-sum rules for even numbers can be derived by leaving as many bits
2915 to the right alone as the divisor has zeros to the right.
2916 E.g. if x is an unsigned 32 bit number:
2917 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
2920 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
2923 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2925 enum tree_code code;
2926 enum machine_mode mode;
2927 rtx op0, op1, target;
2930 enum machine_mode compute_mode;
2932 rtx quotient = 0, remainder = 0;
2936 optab optab1, optab2;
2937 int op1_is_constant, op1_is_pow2;
2938 int max_cost, extra_cost;
2939 static HOST_WIDE_INT last_div_const = 0;
2941 op1_is_constant = GET_CODE (op1) == CONST_INT;
2942 op1_is_pow2 = (op1_is_constant
2943 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
2944 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1))))));
2947 This is the structure of expand_divmod:
2949 First comes code to fix up the operands so we can perform the operations
2950 correctly and efficiently.
2952 Second comes a switch statement with code specific for each rounding mode.
2953 For some special operands this code emits all RTL for the desired
2954 operation, for other cases, it generates only a quotient and stores it in
2955 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
2956 to indicate that it has not done anything.
2958 Last comes code that finishes the operation. If QUOTIENT is set and
2959 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
2960 QUOTIENT is not set, it is computed using trunc rounding.
2962 We try to generate special code for division and remainder when OP1 is a
2963 constant. If |OP1| = 2**n we can use shifts and some other fast
2964 operations. For other values of OP1, we compute a carefully selected
2965 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
2968 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
2969 half of the product. Different strategies for generating the product are
2970 implemented in expand_mult_highpart.
2972 If what we actually want is the remainder, we generate that by another
2973 by-constant multiplication and a subtraction. */
2975 /* We shouldn't be called with OP1 == const1_rtx, but some of the
2976 code below will malfunction if we are, so check here and handle
2977 the special case if so. */
2978 if (op1 == const1_rtx)
2979 return rem_flag ? const0_rtx : op0;
2981 /* When dividing by -1, we could get an overflow.
2982 negv_optab can handle overflows. */
2983 if (! unsignedp && op1 == constm1_rtx)
2987 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
2988 ? negv_optab : neg_optab, op0, target, 0);
2992 /* Don't use the function value register as a target
2993 since we have to read it as well as write it,
2994 and function-inlining gets confused by this. */
2995 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
2996 /* Don't clobber an operand while doing a multi-step calculation. */
2997 || ((rem_flag || op1_is_constant)
2998 && (reg_mentioned_p (target, op0)
2999 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
3000 || reg_mentioned_p (target, op1)
3001 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
3004 /* Get the mode in which to perform this computation. Normally it will
3005 be MODE, but sometimes we can't do the desired operation in MODE.
3006 If so, pick a wider mode in which we can do the operation. Convert
3007 to that mode at the start to avoid repeated conversions.
3009 First see what operations we need. These depend on the expression
3010 we are evaluating. (We assume that divxx3 insns exist under the
3011 same conditions that modxx3 insns and that these insns don't normally
3012 fail. If these assumptions are not correct, we may generate less
3013 efficient code in some cases.)
3015 Then see if we find a mode in which we can open-code that operation
3016 (either a division, modulus, or shift). Finally, check for the smallest
3017 mode for which we can do the operation with a library call. */
3019 /* We might want to refine this now that we have division-by-constant
3020 optimization. Since expand_mult_highpart tries so many variants, it is
3021 not straightforward to generalize this. Maybe we should make an array
3022 of possible modes in init_expmed? Save this for GCC 2.7. */
3024 optab1 = (op1_is_pow2 ? (unsignedp ? lshr_optab : ashr_optab)
3025 : (unsignedp ? udiv_optab : sdiv_optab));
3026 optab2 = (op1_is_pow2 ? optab1 : (unsignedp ? udivmod_optab : sdivmod_optab));
3028 for (compute_mode = mode; compute_mode != VOIDmode;
3029 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3030 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
3031 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
3034 if (compute_mode == VOIDmode)
3035 for (compute_mode = mode; compute_mode != VOIDmode;
3036 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3037 if (optab1->handlers[(int) compute_mode].libfunc
3038 || optab2->handlers[(int) compute_mode].libfunc)
3041 /* If we still couldn't find a mode, use MODE, but we'll probably abort
3043 if (compute_mode == VOIDmode)
3044 compute_mode = mode;
3046 if (target && GET_MODE (target) == compute_mode)
3049 tquotient = gen_reg_rtx (compute_mode);
3051 size = GET_MODE_BITSIZE (compute_mode);
3053 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3054 (mode), and thereby get better code when OP1 is a constant. Do that
3055 later. It will require going over all usages of SIZE below. */
3056 size = GET_MODE_BITSIZE (mode);
3059 /* Only deduct something for a REM if the last divide done was
3060 for a different constant. Then set the constant of the last
3062 max_cost = div_cost[(int) compute_mode]
3063 - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3064 && INTVAL (op1) == last_div_const)
3065 ? mul_cost[(int) compute_mode] + add_cost : 0);
3067 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3069 /* Now convert to the best mode to use. */
3070 if (compute_mode != mode)
3072 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3073 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3075 /* convert_modes may have placed op1 into a register, so we
3076 must recompute the following. */
3077 op1_is_constant = GET_CODE (op1) == CONST_INT;
3078 op1_is_pow2 = (op1_is_constant
3079 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3081 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3084 /* If one of the operands is a volatile MEM, copy it into a register. */
3086 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3087 op0 = force_reg (compute_mode, op0);
3088 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3089 op1 = force_reg (compute_mode, op1);
3091 /* If we need the remainder or if OP1 is constant, we need to
3092 put OP0 in a register in case it has any queued subexpressions. */
3093 if (rem_flag || op1_is_constant)
3094 op0 = force_reg (compute_mode, op0);
3096 last = get_last_insn ();
3098 /* Promote floor rounding to trunc rounding for unsigned operations. */
3101 if (code == FLOOR_DIV_EXPR)
3102 code = TRUNC_DIV_EXPR;
3103 if (code == FLOOR_MOD_EXPR)
3104 code = TRUNC_MOD_EXPR;
3105 if (code == EXACT_DIV_EXPR && op1_is_pow2)
3106 code = TRUNC_DIV_EXPR;
3109 if (op1 != const0_rtx)
3112 case TRUNC_MOD_EXPR:
3113 case TRUNC_DIV_EXPR:
3114 if (op1_is_constant)
3118 unsigned HOST_WIDE_INT mh, ml;
3119 int pre_shift, post_shift;
3121 unsigned HOST_WIDE_INT d = INTVAL (op1);
3123 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3125 pre_shift = floor_log2 (d);
3129 = expand_binop (compute_mode, and_optab, op0,
3130 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3134 return gen_lowpart (mode, remainder);
3136 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3137 build_int_2 (pre_shift, 0),
3140 else if (size <= HOST_BITS_PER_WIDE_INT)
3142 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3144 /* Most significant bit of divisor is set; emit an scc
3146 quotient = emit_store_flag (tquotient, GEU, op0, op1,
3147 compute_mode, 1, 1);
3153 /* Find a suitable multiplier and right shift count
3154 instead of multiplying with D. */
3156 mh = choose_multiplier (d, size, size,
3157 &ml, &post_shift, &dummy);
3159 /* If the suggested multiplier is more than SIZE bits,
3160 we can do better for even divisors, using an
3161 initial right shift. */
3162 if (mh != 0 && (d & 1) == 0)
3164 pre_shift = floor_log2 (d & -d);
3165 mh = choose_multiplier (d >> pre_shift, size,
3167 &ml, &post_shift, &dummy);
3178 if (post_shift - 1 >= BITS_PER_WORD)
3181 extra_cost = (shift_cost[post_shift - 1]
3182 + shift_cost[1] + 2 * add_cost);
3183 t1 = expand_mult_highpart (compute_mode, op0, ml,
3185 max_cost - extra_cost);
3188 t2 = force_operand (gen_rtx_MINUS (compute_mode,
3191 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3192 build_int_2 (1, 0), NULL_RTX,1);
3193 t4 = force_operand (gen_rtx_PLUS (compute_mode,
3197 = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3198 build_int_2 (post_shift - 1, 0),
3205 if (pre_shift >= BITS_PER_WORD
3206 || post_shift >= BITS_PER_WORD)
3209 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3210 build_int_2 (pre_shift, 0),
3212 extra_cost = (shift_cost[pre_shift]
3213 + shift_cost[post_shift]);
3214 t2 = expand_mult_highpart (compute_mode, t1, ml,
3216 max_cost - extra_cost);
3220 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3221 build_int_2 (post_shift, 0),
3226 else /* Too wide mode to use tricky code */
3229 insn = get_last_insn ();
3231 && (set = single_set (insn)) != 0
3232 && SET_DEST (set) == quotient)
3233 set_unique_reg_note (insn,
3235 gen_rtx_UDIV (compute_mode, op0, op1));
3237 else /* TRUNC_DIV, signed */
3239 unsigned HOST_WIDE_INT ml;
3240 int lgup, post_shift;
3241 HOST_WIDE_INT d = INTVAL (op1);
3242 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3244 /* n rem d = n rem -d */
3245 if (rem_flag && d < 0)
3248 op1 = GEN_INT (trunc_int_for_mode (abs_d, compute_mode));
3254 quotient = expand_unop (compute_mode, neg_optab, op0,
3256 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3258 /* This case is not handled correctly below. */
3259 quotient = emit_store_flag (tquotient, EQ, op0, op1,
3260 compute_mode, 1, 1);
3264 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3265 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap)
3266 /* ??? The cheap metric is computed only for
3267 word_mode. If this operation is wider, this may
3268 not be so. Assume true if the optab has an
3269 expander for this mode. */
3270 && (((rem_flag ? smod_optab : sdiv_optab)
3271 ->handlers[(int) compute_mode].insn_code
3272 != CODE_FOR_nothing)
3273 || (sdivmod_optab->handlers[(int) compute_mode]
3274 .insn_code != CODE_FOR_nothing)))
3276 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3278 lgup = floor_log2 (abs_d);
3279 if (BRANCH_COST < 1 || (abs_d != 2 && BRANCH_COST < 3))
3281 rtx label = gen_label_rtx ();
3284 t1 = copy_to_mode_reg (compute_mode, op0);
3285 do_cmp_and_jump (t1, const0_rtx, GE,
3286 compute_mode, label);
3287 expand_inc (t1, GEN_INT (trunc_int_for_mode
3288 (abs_d - 1, compute_mode)));
3290 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3291 build_int_2 (lgup, 0),
3297 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3298 build_int_2 (size - 1, 0),
3300 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3301 build_int_2 (size - lgup, 0),
3303 t3 = force_operand (gen_rtx_PLUS (compute_mode,
3306 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3307 build_int_2 (lgup, 0),
3311 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
3315 insn = get_last_insn ();
3317 && (set = single_set (insn)) != 0
3318 && SET_DEST (set) == quotient
3319 && abs_d < ((unsigned HOST_WIDE_INT) 1
3320 << (HOST_BITS_PER_WIDE_INT - 1)))
3321 set_unique_reg_note (insn,
3323 gen_rtx_DIV (compute_mode,
3330 quotient = expand_unop (compute_mode, neg_optab,
3331 quotient, quotient, 0);
3334 else if (size <= HOST_BITS_PER_WIDE_INT)
3336 choose_multiplier (abs_d, size, size - 1,
3337 &ml, &post_shift, &lgup);
3338 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3342 if (post_shift >= BITS_PER_WORD
3343 || size - 1 >= BITS_PER_WORD)
3346 extra_cost = (shift_cost[post_shift]
3347 + shift_cost[size - 1] + add_cost);
3348 t1 = expand_mult_highpart (compute_mode, op0, ml,
3350 max_cost - extra_cost);
3353 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3354 build_int_2 (post_shift, 0), NULL_RTX, 0);
3355 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3356 build_int_2 (size - 1, 0), NULL_RTX, 0);
3359 = force_operand (gen_rtx_MINUS (compute_mode,
3364 = force_operand (gen_rtx_MINUS (compute_mode,
3372 if (post_shift >= BITS_PER_WORD
3373 || size - 1 >= BITS_PER_WORD)
3376 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3377 extra_cost = (shift_cost[post_shift]
3378 + shift_cost[size - 1] + 2 * add_cost);
3379 t1 = expand_mult_highpart (compute_mode, op0, ml,
3381 max_cost - extra_cost);
3384 t2 = force_operand (gen_rtx_PLUS (compute_mode,
3387 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3388 build_int_2 (post_shift, 0),
3390 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3391 build_int_2 (size - 1, 0),
3395 = force_operand (gen_rtx_MINUS (compute_mode,
3400 = force_operand (gen_rtx_MINUS (compute_mode,
3405 else /* Too wide mode to use tricky code */
3408 insn = get_last_insn ();
3410 && (set = single_set (insn)) != 0
3411 && SET_DEST (set) == quotient)
3412 set_unique_reg_note (insn,
3414 gen_rtx_DIV (compute_mode, op0, op1));
3419 delete_insns_since (last);
3422 case FLOOR_DIV_EXPR:
3423 case FLOOR_MOD_EXPR:
3424 /* We will come here only for signed operations. */
3425 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3427 unsigned HOST_WIDE_INT mh, ml;
3428 int pre_shift, lgup, post_shift;
3429 HOST_WIDE_INT d = INTVAL (op1);
3433 /* We could just as easily deal with negative constants here,
3434 but it does not seem worth the trouble for GCC 2.6. */
3435 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3437 pre_shift = floor_log2 (d);
3440 remainder = expand_binop (compute_mode, and_optab, op0,
3441 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3442 remainder, 0, OPTAB_LIB_WIDEN);
3444 return gen_lowpart (mode, remainder);
3446 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3447 build_int_2 (pre_shift, 0),
3454 mh = choose_multiplier (d, size, size - 1,
3455 &ml, &post_shift, &lgup);
3459 if (post_shift < BITS_PER_WORD
3460 && size - 1 < BITS_PER_WORD)
3462 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3463 build_int_2 (size - 1, 0),
3465 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3466 NULL_RTX, 0, OPTAB_WIDEN);
3467 extra_cost = (shift_cost[post_shift]
3468 + shift_cost[size - 1] + 2 * add_cost);
3469 t3 = expand_mult_highpart (compute_mode, t2, ml,
3471 max_cost - extra_cost);
3474 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3475 build_int_2 (post_shift, 0),
3477 quotient = expand_binop (compute_mode, xor_optab,
3478 t4, t1, tquotient, 0,
3486 rtx nsign, t1, t2, t3, t4;
3487 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3488 op0, constm1_rtx), NULL_RTX);
3489 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3491 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3492 build_int_2 (size - 1, 0), NULL_RTX, 0);
3493 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3495 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3500 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3502 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3511 delete_insns_since (last);
3513 /* Try using an instruction that produces both the quotient and
3514 remainder, using truncation. We can easily compensate the quotient
3515 or remainder to get floor rounding, once we have the remainder.
3516 Notice that we compute also the final remainder value here,
3517 and return the result right away. */
3518 if (target == 0 || GET_MODE (target) != compute_mode)
3519 target = gen_reg_rtx (compute_mode);
3524 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3525 quotient = gen_reg_rtx (compute_mode);
3530 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3531 remainder = gen_reg_rtx (compute_mode);
3534 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3535 quotient, remainder, 0))
3537 /* This could be computed with a branch-less sequence.
3538 Save that for later. */
3540 rtx label = gen_label_rtx ();
3541 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3542 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3543 NULL_RTX, 0, OPTAB_WIDEN);
3544 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3545 expand_dec (quotient, const1_rtx);
3546 expand_inc (remainder, op1);
3548 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3551 /* No luck with division elimination or divmod. Have to do it
3552 by conditionally adjusting op0 *and* the result. */
3554 rtx label1, label2, label3, label4, label5;
3558 quotient = gen_reg_rtx (compute_mode);
3559 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3560 label1 = gen_label_rtx ();
3561 label2 = gen_label_rtx ();
3562 label3 = gen_label_rtx ();
3563 label4 = gen_label_rtx ();
3564 label5 = gen_label_rtx ();
3565 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3566 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3567 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3568 quotient, 0, OPTAB_LIB_WIDEN);
3569 if (tem != quotient)
3570 emit_move_insn (quotient, tem);
3571 emit_jump_insn (gen_jump (label5));
3573 emit_label (label1);
3574 expand_inc (adjusted_op0, const1_rtx);
3575 emit_jump_insn (gen_jump (label4));
3577 emit_label (label2);
3578 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3579 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3580 quotient, 0, OPTAB_LIB_WIDEN);
3581 if (tem != quotient)
3582 emit_move_insn (quotient, tem);
3583 emit_jump_insn (gen_jump (label5));
3585 emit_label (label3);
3586 expand_dec (adjusted_op0, const1_rtx);
3587 emit_label (label4);
3588 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3589 quotient, 0, OPTAB_LIB_WIDEN);
3590 if (tem != quotient)
3591 emit_move_insn (quotient, tem);
3592 expand_dec (quotient, const1_rtx);
3593 emit_label (label5);
3601 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3604 unsigned HOST_WIDE_INT d = INTVAL (op1);
3605 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3606 build_int_2 (floor_log2 (d), 0),
3608 t2 = expand_binop (compute_mode, and_optab, op0,
3610 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3611 t3 = gen_reg_rtx (compute_mode);
3612 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3613 compute_mode, 1, 1);
3617 lab = gen_label_rtx ();
3618 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3619 expand_inc (t1, const1_rtx);
3624 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3630 /* Try using an instruction that produces both the quotient and
3631 remainder, using truncation. We can easily compensate the
3632 quotient or remainder to get ceiling rounding, once we have the
3633 remainder. Notice that we compute also the final remainder
3634 value here, and return the result right away. */
3635 if (target == 0 || GET_MODE (target) != compute_mode)
3636 target = gen_reg_rtx (compute_mode);
3640 remainder = (GET_CODE (target) == REG
3641 ? target : gen_reg_rtx (compute_mode));
3642 quotient = gen_reg_rtx (compute_mode);
3646 quotient = (GET_CODE (target) == REG
3647 ? target : gen_reg_rtx (compute_mode));
3648 remainder = gen_reg_rtx (compute_mode);
3651 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3654 /* This could be computed with a branch-less sequence.
3655 Save that for later. */
3656 rtx label = gen_label_rtx ();
3657 do_cmp_and_jump (remainder, const0_rtx, EQ,
3658 compute_mode, label);
3659 expand_inc (quotient, const1_rtx);
3660 expand_dec (remainder, op1);
3662 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3665 /* No luck with division elimination or divmod. Have to do it
3666 by conditionally adjusting op0 *and* the result. */
3669 rtx adjusted_op0, tem;
3671 quotient = gen_reg_rtx (compute_mode);
3672 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3673 label1 = gen_label_rtx ();
3674 label2 = gen_label_rtx ();
3675 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3676 compute_mode, label1);
3677 emit_move_insn (quotient, const0_rtx);
3678 emit_jump_insn (gen_jump (label2));
3680 emit_label (label1);
3681 expand_dec (adjusted_op0, const1_rtx);
3682 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3683 quotient, 1, OPTAB_LIB_WIDEN);
3684 if (tem != quotient)
3685 emit_move_insn (quotient, tem);
3686 expand_inc (quotient, const1_rtx);
3687 emit_label (label2);
3692 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3693 && INTVAL (op1) >= 0)
3695 /* This is extremely similar to the code for the unsigned case
3696 above. For 2.7 we should merge these variants, but for
3697 2.6.1 I don't want to touch the code for unsigned since that
3698 get used in C. The signed case will only be used by other
3702 unsigned HOST_WIDE_INT d = INTVAL (op1);
3703 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3704 build_int_2 (floor_log2 (d), 0),
3706 t2 = expand_binop (compute_mode, and_optab, op0,
3708 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3709 t3 = gen_reg_rtx (compute_mode);
3710 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3711 compute_mode, 1, 1);
3715 lab = gen_label_rtx ();
3716 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3717 expand_inc (t1, const1_rtx);
3722 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3728 /* Try using an instruction that produces both the quotient and
3729 remainder, using truncation. We can easily compensate the
3730 quotient or remainder to get ceiling rounding, once we have the
3731 remainder. Notice that we compute also the final remainder
3732 value here, and return the result right away. */
3733 if (target == 0 || GET_MODE (target) != compute_mode)
3734 target = gen_reg_rtx (compute_mode);
3737 remainder= (GET_CODE (target) == REG
3738 ? target : gen_reg_rtx (compute_mode));
3739 quotient = gen_reg_rtx (compute_mode);
3743 quotient = (GET_CODE (target) == REG
3744 ? target : gen_reg_rtx (compute_mode));
3745 remainder = gen_reg_rtx (compute_mode);
3748 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3751 /* This could be computed with a branch-less sequence.
3752 Save that for later. */
3754 rtx label = gen_label_rtx ();
3755 do_cmp_and_jump (remainder, const0_rtx, EQ,
3756 compute_mode, label);
3757 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3758 NULL_RTX, 0, OPTAB_WIDEN);
3759 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3760 expand_inc (quotient, const1_rtx);
3761 expand_dec (remainder, op1);
3763 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3766 /* No luck with division elimination or divmod. Have to do it
3767 by conditionally adjusting op0 *and* the result. */
3769 rtx label1, label2, label3, label4, label5;
3773 quotient = gen_reg_rtx (compute_mode);
3774 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3775 label1 = gen_label_rtx ();
3776 label2 = gen_label_rtx ();
3777 label3 = gen_label_rtx ();
3778 label4 = gen_label_rtx ();
3779 label5 = gen_label_rtx ();
3780 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3781 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3782 compute_mode, label1);
3783 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3784 quotient, 0, OPTAB_LIB_WIDEN);
3785 if (tem != quotient)
3786 emit_move_insn (quotient, tem);
3787 emit_jump_insn (gen_jump (label5));
3789 emit_label (label1);
3790 expand_dec (adjusted_op0, const1_rtx);
3791 emit_jump_insn (gen_jump (label4));
3793 emit_label (label2);
3794 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3795 compute_mode, label3);
3796 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3797 quotient, 0, OPTAB_LIB_WIDEN);
3798 if (tem != quotient)
3799 emit_move_insn (quotient, tem);
3800 emit_jump_insn (gen_jump (label5));
3802 emit_label (label3);
3803 expand_inc (adjusted_op0, const1_rtx);
3804 emit_label (label4);
3805 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3806 quotient, 0, OPTAB_LIB_WIDEN);
3807 if (tem != quotient)
3808 emit_move_insn (quotient, tem);
3809 expand_inc (quotient, const1_rtx);
3810 emit_label (label5);
3815 case EXACT_DIV_EXPR:
3816 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3818 HOST_WIDE_INT d = INTVAL (op1);
3819 unsigned HOST_WIDE_INT ml;
3823 pre_shift = floor_log2 (d & -d);
3824 ml = invert_mod2n (d >> pre_shift, size);
3825 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3826 build_int_2 (pre_shift, 0), NULL_RTX, unsignedp);
3827 quotient = expand_mult (compute_mode, t1,
3828 GEN_INT (trunc_int_for_mode
3829 (ml, compute_mode)),
3832 insn = get_last_insn ();
3833 set_unique_reg_note (insn,
3835 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
3841 case ROUND_DIV_EXPR:
3842 case ROUND_MOD_EXPR:
3847 label = gen_label_rtx ();
3848 quotient = gen_reg_rtx (compute_mode);
3849 remainder = gen_reg_rtx (compute_mode);
3850 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3853 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3854 quotient, 1, OPTAB_LIB_WIDEN);
3855 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3856 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3857 remainder, 1, OPTAB_LIB_WIDEN);
3859 tem = plus_constant (op1, -1);
3860 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3861 build_int_2 (1, 0), NULL_RTX, 1);
3862 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
3863 expand_inc (quotient, const1_rtx);
3864 expand_dec (remainder, op1);
3869 rtx abs_rem, abs_op1, tem, mask;
3871 label = gen_label_rtx ();
3872 quotient = gen_reg_rtx (compute_mode);
3873 remainder = gen_reg_rtx (compute_mode);
3874 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3877 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3878 quotient, 0, OPTAB_LIB_WIDEN);
3879 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3880 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3881 remainder, 0, OPTAB_LIB_WIDEN);
3883 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
3884 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
3885 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3886 build_int_2 (1, 0), NULL_RTX, 1);
3887 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
3888 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3889 NULL_RTX, 0, OPTAB_WIDEN);
3890 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3891 build_int_2 (size - 1, 0), NULL_RTX, 0);
3892 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3893 NULL_RTX, 0, OPTAB_WIDEN);
3894 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3895 NULL_RTX, 0, OPTAB_WIDEN);
3896 expand_inc (quotient, tem);
3897 tem = expand_binop (compute_mode, xor_optab, mask, op1,
3898 NULL_RTX, 0, OPTAB_WIDEN);
3899 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3900 NULL_RTX, 0, OPTAB_WIDEN);
3901 expand_dec (remainder, tem);
3904 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3912 if (target && GET_MODE (target) != compute_mode)
3917 /* Try to produce the remainder without producing the quotient.
3918 If we seem to have a divmod pattern that does not require widening,
3919 don't try widening here. We should really have an WIDEN argument
3920 to expand_twoval_binop, since what we'd really like to do here is
3921 1) try a mod insn in compute_mode
3922 2) try a divmod insn in compute_mode
3923 3) try a div insn in compute_mode and multiply-subtract to get
3925 4) try the same things with widening allowed. */
3927 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3930 ((optab2->handlers[(int) compute_mode].insn_code
3931 != CODE_FOR_nothing)
3932 ? OPTAB_DIRECT : OPTAB_WIDEN));
3935 /* No luck there. Can we do remainder and divide at once
3936 without a library call? */
3937 remainder = gen_reg_rtx (compute_mode);
3938 if (! expand_twoval_binop ((unsignedp
3942 NULL_RTX, remainder, unsignedp))
3947 return gen_lowpart (mode, remainder);
3950 /* Produce the quotient. Try a quotient insn, but not a library call.
3951 If we have a divmod in this mode, use it in preference to widening
3952 the div (for this test we assume it will not fail). Note that optab2
3953 is set to the one of the two optabs that the call below will use. */
3955 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
3956 op0, op1, rem_flag ? NULL_RTX : target,
3958 ((optab2->handlers[(int) compute_mode].insn_code
3959 != CODE_FOR_nothing)
3960 ? OPTAB_DIRECT : OPTAB_WIDEN));
3964 /* No luck there. Try a quotient-and-remainder insn,
3965 keeping the quotient alone. */
3966 quotient = gen_reg_rtx (compute_mode);
3967 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
3969 quotient, NULL_RTX, unsignedp))
3973 /* Still no luck. If we are not computing the remainder,
3974 use a library call for the quotient. */
3975 quotient = sign_expand_binop (compute_mode,
3976 udiv_optab, sdiv_optab,
3978 unsignedp, OPTAB_LIB_WIDEN);
3985 if (target && GET_MODE (target) != compute_mode)
3989 /* No divide instruction either. Use library for remainder. */
3990 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3992 unsignedp, OPTAB_LIB_WIDEN);
3995 /* We divided. Now finish doing X - Y * (X / Y). */
3996 remainder = expand_mult (compute_mode, quotient, op1,
3997 NULL_RTX, unsignedp);
3998 remainder = expand_binop (compute_mode, sub_optab, op0,
3999 remainder, target, unsignedp,
4004 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4007 /* Return a tree node with data type TYPE, describing the value of X.
4008 Usually this is an RTL_EXPR, if there is no obvious better choice.
4009 X may be an expression, however we only support those expressions
4010 generated by loop.c. */
4019 switch (GET_CODE (x))
4022 t = build_int_2 (INTVAL (x),
4023 (TREE_UNSIGNED (type)
4024 && (GET_MODE_BITSIZE (TYPE_MODE (type)) < HOST_BITS_PER_WIDE_INT))
4025 || INTVAL (x) >= 0 ? 0 : -1);
4026 TREE_TYPE (t) = type;
4030 if (GET_MODE (x) == VOIDmode)
4032 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4033 TREE_TYPE (t) = type;
4039 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4040 t = build_real (type, d);
4051 units = CONST_VECTOR_NUNITS (x);
4053 /* Build a tree with vector elements. */
4054 for (i = units - 1; i >= 0; --i)
4056 elt = CONST_VECTOR_ELT (x, i);
4057 t = tree_cons (NULL_TREE, make_tree (type, elt), t);
4060 return build_vector (type, t);
4064 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4065 make_tree (type, XEXP (x, 1))));
4068 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4069 make_tree (type, XEXP (x, 1))));
4072 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
4075 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
4076 make_tree (type, XEXP (x, 1))));
4079 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
4080 make_tree (type, XEXP (x, 1))));
4083 return fold (convert (type,
4084 build (RSHIFT_EXPR, unsigned_type (type),
4085 make_tree (unsigned_type (type),
4087 make_tree (type, XEXP (x, 1)))));
4090 return fold (convert (type,
4091 build (RSHIFT_EXPR, signed_type (type),
4092 make_tree (signed_type (type), XEXP (x, 0)),
4093 make_tree (type, XEXP (x, 1)))));
4096 if (TREE_CODE (type) != REAL_TYPE)
4097 t = signed_type (type);
4101 return fold (convert (type,
4102 build (TRUNC_DIV_EXPR, t,
4103 make_tree (t, XEXP (x, 0)),
4104 make_tree (t, XEXP (x, 1)))));
4106 t = unsigned_type (type);
4107 return fold (convert (type,
4108 build (TRUNC_DIV_EXPR, t,
4109 make_tree (t, XEXP (x, 0)),
4110 make_tree (t, XEXP (x, 1)))));
4112 t = make_node (RTL_EXPR);
4113 TREE_TYPE (t) = type;
4115 #ifdef POINTERS_EXTEND_UNSIGNED
4116 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
4117 ptr_mode. So convert. */
4118 if (POINTER_TYPE_P (type) && GET_MODE (x) != TYPE_MODE (type))
4119 x = convert_memory_address (TYPE_MODE (type), x);
4122 RTL_EXPR_RTL (t) = x;
4123 /* There are no insns to be output
4124 when this rtl_expr is used. */
4125 RTL_EXPR_SEQUENCE (t) = 0;
4130 /* Return an rtx representing the value of X * MULT + ADD.
4131 TARGET is a suggestion for where to store the result (an rtx).
4132 MODE is the machine mode for the computation.
4133 X and MULT must have mode MODE. ADD may have a different mode.
4134 So can X (defaults to same as MODE).
4135 UNSIGNEDP is non-zero to do unsigned multiplication.
4136 This may emit insns. */
4139 expand_mult_add (x, target, mult, add, mode, unsignedp)
4140 rtx x, target, mult, add;
4141 enum machine_mode mode;
4144 tree type = type_for_mode (mode, unsignedp);
4145 tree add_type = (GET_MODE (add) == VOIDmode
4146 ? type : type_for_mode (GET_MODE (add), unsignedp));
4147 tree result = fold (build (PLUS_EXPR, type,
4148 fold (build (MULT_EXPR, type,
4149 make_tree (type, x),
4150 make_tree (type, mult))),
4151 make_tree (add_type, add)));
4153 return expand_expr (result, target, VOIDmode, 0);
4156 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4157 and returning TARGET.
4159 If TARGET is 0, a pseudo-register or constant is returned. */
4162 expand_and (mode, op0, op1, target)
4163 enum machine_mode mode;
4164 rtx op0, op1, target;
4168 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
4169 tem = simplify_binary_operation (AND, mode, op0, op1);
4171 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4175 else if (tem != target)
4176 emit_move_insn (target, tem);
4180 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4181 and storing in TARGET. Normally return TARGET.
4182 Return 0 if that cannot be done.
4184 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
4185 it is VOIDmode, they cannot both be CONST_INT.
4187 UNSIGNEDP is for the case where we have to widen the operands
4188 to perform the operation. It says to use zero-extension.
4190 NORMALIZEP is 1 if we should convert the result to be either zero
4191 or one. Normalize is -1 if we should convert the result to be
4192 either zero or -1. If NORMALIZEP is zero, the result will be left
4193 "raw" out of the scc insn. */
4196 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
4200 enum machine_mode mode;
4205 enum insn_code icode;
4206 enum machine_mode compare_mode;
4207 enum machine_mode target_mode = GET_MODE (target);
4209 rtx last = get_last_insn ();
4210 rtx pattern, comparison;
4212 /* ??? Ok to do this and then fail? */
4213 op0 = protect_from_queue (op0, 0);
4214 op1 = protect_from_queue (op1, 0);
4217 code = unsigned_condition (code);
4219 /* If one operand is constant, make it the second one. Only do this
4220 if the other operand is not constant as well. */
4222 if (swap_commutative_operands_p (op0, op1))
4227 code = swap_condition (code);
4230 if (mode == VOIDmode)
4231 mode = GET_MODE (op0);
4233 /* For some comparisons with 1 and -1, we can convert this to
4234 comparisons with zero. This will often produce more opportunities for
4235 store-flag insns. */
4240 if (op1 == const1_rtx)
4241 op1 = const0_rtx, code = LE;
4244 if (op1 == constm1_rtx)
4245 op1 = const0_rtx, code = LT;
4248 if (op1 == const1_rtx)
4249 op1 = const0_rtx, code = GT;
4252 if (op1 == constm1_rtx)
4253 op1 = const0_rtx, code = GE;
4256 if (op1 == const1_rtx)
4257 op1 = const0_rtx, code = NE;
4260 if (op1 == const1_rtx)
4261 op1 = const0_rtx, code = EQ;
4267 /* If we are comparing a double-word integer with zero, we can convert
4268 the comparison into one involving a single word. */
4269 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
4270 && GET_MODE_CLASS (mode) == MODE_INT
4271 && op1 == const0_rtx)
4273 if (code == EQ || code == NE)
4275 /* Do a logical OR of the two words and compare the result. */
4276 rtx op0h = gen_highpart (word_mode, op0);
4277 rtx op0l = gen_lowpart (word_mode, op0);
4278 rtx op0both = expand_binop (word_mode, ior_optab, op0h, op0l,
4279 NULL_RTX, unsignedp, OPTAB_DIRECT);
4281 return emit_store_flag (target, code, op0both, op1, word_mode,
4282 unsignedp, normalizep);
4284 else if (code == LT || code == GE)
4285 /* If testing the sign bit, can just test on high word. */
4286 return emit_store_flag (target, code, gen_highpart (word_mode, op0),
4287 op1, word_mode, unsignedp, normalizep);
4290 /* From now on, we won't change CODE, so set ICODE now. */
4291 icode = setcc_gen_code[(int) code];
4293 /* If this is A < 0 or A >= 0, we can do this by taking the ones
4294 complement of A (for GE) and shifting the sign bit to the low bit. */
4295 if (op1 == const0_rtx && (code == LT || code == GE)
4296 && GET_MODE_CLASS (mode) == MODE_INT
4297 && (normalizep || STORE_FLAG_VALUE == 1
4298 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4299 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4300 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4304 /* If the result is to be wider than OP0, it is best to convert it
4305 first. If it is to be narrower, it is *incorrect* to convert it
4307 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4309 op0 = protect_from_queue (op0, 0);
4310 op0 = convert_modes (target_mode, mode, op0, 0);
4314 if (target_mode != mode)
4318 op0 = expand_unop (mode, one_cmpl_optab, op0,
4319 ((STORE_FLAG_VALUE == 1 || normalizep)
4320 ? 0 : subtarget), 0);
4322 if (STORE_FLAG_VALUE == 1 || normalizep)
4323 /* If we are supposed to produce a 0/1 value, we want to do
4324 a logical shift from the sign bit to the low-order bit; for
4325 a -1/0 value, we do an arithmetic shift. */
4326 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4327 size_int (GET_MODE_BITSIZE (mode) - 1),
4328 subtarget, normalizep != -1);
4330 if (mode != target_mode)
4331 op0 = convert_modes (target_mode, mode, op0, 0);
4336 if (icode != CODE_FOR_nothing)
4338 insn_operand_predicate_fn pred;
4340 /* We think we may be able to do this with a scc insn. Emit the
4341 comparison and then the scc insn.
4343 compare_from_rtx may call emit_queue, which would be deleted below
4344 if the scc insn fails. So call it ourselves before setting LAST.
4345 Likewise for do_pending_stack_adjust. */
4348 do_pending_stack_adjust ();
4349 last = get_last_insn ();
4352 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX);
4353 if (GET_CODE (comparison) == CONST_INT)
4354 return (comparison == const0_rtx ? const0_rtx
4355 : normalizep == 1 ? const1_rtx
4356 : normalizep == -1 ? constm1_rtx
4359 /* The code of COMPARISON may not match CODE if compare_from_rtx
4360 decided to swap its operands and reverse the original code.
4362 We know that compare_from_rtx returns either a CONST_INT or
4363 a new comparison code, so it is safe to just extract the
4364 code from COMPARISON. */
4365 code = GET_CODE (comparison);
4367 /* Get a reference to the target in the proper mode for this insn. */
4368 compare_mode = insn_data[(int) icode].operand[0].mode;
4370 pred = insn_data[(int) icode].operand[0].predicate;
4371 if (preserve_subexpressions_p ()
4372 || ! (*pred) (subtarget, compare_mode))
4373 subtarget = gen_reg_rtx (compare_mode);
4375 pattern = GEN_FCN (icode) (subtarget);
4378 emit_insn (pattern);
4380 /* If we are converting to a wider mode, first convert to
4381 TARGET_MODE, then normalize. This produces better combining
4382 opportunities on machines that have a SIGN_EXTRACT when we are
4383 testing a single bit. This mostly benefits the 68k.
4385 If STORE_FLAG_VALUE does not have the sign bit set when
4386 interpreted in COMPARE_MODE, we can do this conversion as
4387 unsigned, which is usually more efficient. */
4388 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4390 convert_move (target, subtarget,
4391 (GET_MODE_BITSIZE (compare_mode)
4392 <= HOST_BITS_PER_WIDE_INT)
4393 && 0 == (STORE_FLAG_VALUE
4394 & ((HOST_WIDE_INT) 1
4395 << (GET_MODE_BITSIZE (compare_mode) -1))));
4397 compare_mode = target_mode;
4402 /* If we want to keep subexpressions around, don't reuse our
4405 if (preserve_subexpressions_p ())
4408 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
4409 we don't have to do anything. */
4410 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4412 /* STORE_FLAG_VALUE might be the most negative number, so write
4413 the comparison this way to avoid a compiler-time warning. */
4414 else if (- normalizep == STORE_FLAG_VALUE)
4415 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4417 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4418 makes it hard to use a value of just the sign bit due to
4419 ANSI integer constant typing rules. */
4420 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4421 && (STORE_FLAG_VALUE
4422 & ((HOST_WIDE_INT) 1
4423 << (GET_MODE_BITSIZE (compare_mode) - 1))))
4424 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4425 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4426 subtarget, normalizep == 1);
4427 else if (STORE_FLAG_VALUE & 1)
4429 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget);
4430 if (normalizep == -1)
4431 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4436 /* If we were converting to a smaller mode, do the
4438 if (target_mode != compare_mode)
4440 convert_move (target, op0, 0);
4448 delete_insns_since (last);
4450 /* If expensive optimizations, use different pseudo registers for each
4451 insn, instead of reusing the same pseudo. This leads to better CSE,
4452 but slows down the compiler, since there are more pseudos */
4453 subtarget = (!flag_expensive_optimizations
4454 && (target_mode == mode)) ? target : NULL_RTX;
4456 /* If we reached here, we can't do this with a scc insn. However, there
4457 are some comparisons that can be done directly. For example, if
4458 this is an equality comparison of integers, we can try to exclusive-or
4459 (or subtract) the two operands and use a recursive call to try the
4460 comparison with zero. Don't do any of these cases if branches are
4464 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4465 && op1 != const0_rtx)
4467 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4471 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4474 tem = emit_store_flag (target, code, tem, const0_rtx,
4475 mode, unsignedp, normalizep);
4477 delete_insns_since (last);
4481 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4482 the constant zero. Reject all other comparisons at this point. Only
4483 do LE and GT if branches are expensive since they are expensive on
4484 2-operand machines. */
4486 if (BRANCH_COST == 0
4487 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4488 || (code != EQ && code != NE
4489 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4492 /* See what we need to return. We can only return a 1, -1, or the
4495 if (normalizep == 0)
4497 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4498 normalizep = STORE_FLAG_VALUE;
4500 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4501 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4502 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4508 /* Try to put the result of the comparison in the sign bit. Assume we can't
4509 do the necessary operation below. */
4513 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4514 the sign bit set. */
4518 /* This is destructive, so SUBTARGET can't be OP0. */
4519 if (rtx_equal_p (subtarget, op0))
4522 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4525 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4529 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4530 number of bits in the mode of OP0, minus one. */
4534 if (rtx_equal_p (subtarget, op0))
4537 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4538 size_int (GET_MODE_BITSIZE (mode) - 1),
4540 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4544 if (code == EQ || code == NE)
4546 /* For EQ or NE, one way to do the comparison is to apply an operation
4547 that converts the operand into a positive number if it is non-zero
4548 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4549 for NE we negate. This puts the result in the sign bit. Then we
4550 normalize with a shift, if needed.
4552 Two operations that can do the above actions are ABS and FFS, so try
4553 them. If that doesn't work, and MODE is smaller than a full word,
4554 we can use zero-extension to the wider mode (an unsigned conversion)
4555 as the operation. */
4557 /* Note that ABS doesn't yield a positive number for INT_MIN, but
4558 that is compensated by the subsequent overflow when subtracting
4561 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4562 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4563 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4564 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4565 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4567 op0 = protect_from_queue (op0, 0);
4568 tem = convert_modes (word_mode, mode, op0, 1);
4575 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4578 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4581 /* If we couldn't do it that way, for NE we can "or" the two's complement
4582 of the value with itself. For EQ, we take the one's complement of
4583 that "or", which is an extra insn, so we only handle EQ if branches
4586 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4588 if (rtx_equal_p (subtarget, op0))
4591 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4592 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4595 if (tem && code == EQ)
4596 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4600 if (tem && normalizep)
4601 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4602 size_int (GET_MODE_BITSIZE (mode) - 1),
4603 subtarget, normalizep == 1);
4607 if (GET_MODE (tem) != target_mode)
4609 convert_move (target, tem, 0);
4612 else if (!subtarget)
4614 emit_move_insn (target, tem);
4619 delete_insns_since (last);
4624 /* Like emit_store_flag, but always succeeds. */
4627 emit_store_flag_force (target, code, op0, op1, mode, unsignedp, normalizep)
4631 enum machine_mode mode;
4637 /* First see if emit_store_flag can do the job. */
4638 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4642 if (normalizep == 0)
4645 /* If this failed, we have to do this with set/compare/jump/set code. */
4647 if (GET_CODE (target) != REG
4648 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4649 target = gen_reg_rtx (GET_MODE (target));
4651 emit_move_insn (target, const1_rtx);
4652 label = gen_label_rtx ();
4653 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
4656 emit_move_insn (target, const0_rtx);
4662 /* Perform possibly multi-word comparison and conditional jump to LABEL
4663 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4665 The algorithm is based on the code in expr.c:do_jump.
4667 Note that this does not perform a general comparison. Only variants
4668 generated within expmed.c are correctly handled, others abort (but could
4669 be handled if needed). */
4672 do_cmp_and_jump (arg1, arg2, op, mode, label)
4673 rtx arg1, arg2, label;
4675 enum machine_mode mode;
4677 /* If this mode is an integer too wide to compare properly,
4678 compare word by word. Rely on cse to optimize constant cases. */
4680 if (GET_MODE_CLASS (mode) == MODE_INT
4681 && ! can_compare_p (op, mode, ccp_jump))
4683 rtx label2 = gen_label_rtx ();
4688 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4692 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4696 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4700 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4704 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4707 /* do_jump_by_parts_equality_rtx compares with zero. Luckily
4708 that's the only equality operations we do */
4710 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4712 do_jump_by_parts_equality_rtx (arg1, label2, label);
4716 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4718 do_jump_by_parts_equality_rtx (arg1, label, label2);
4725 emit_label (label2);
4728 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);