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);
329 int old_generating_concat_p = generating_concat_p;
330 generating_concat_p = 0;
331 value = force_not_mem (value);
332 generating_concat_p = old_generating_concat_p;
335 /* If the target is a register, overwriting the entire object, or storing
336 a full-word or multi-word field can be done with just a SUBREG.
338 If the target is memory, storing any naturally aligned field can be
339 done with a simple store. For targets that support fast unaligned
340 memory, any naturally sized, unit aligned field can be done directly. */
342 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
343 + (offset * UNITS_PER_WORD);
346 && bitsize == GET_MODE_BITSIZE (fieldmode)
347 && (GET_CODE (op0) != MEM
348 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
349 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
350 && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
351 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
352 || (offset * BITS_PER_UNIT % bitsize == 0
353 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
355 if (GET_MODE (op0) != fieldmode)
357 if (GET_CODE (op0) == SUBREG)
359 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
360 || GET_MODE_CLASS (fieldmode) == MODE_INT
361 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
362 op0 = SUBREG_REG (op0);
364 /* Else we've got some float mode source being extracted into
365 a different float mode destination -- this combination of
366 subregs results in Severe Tire Damage. */
369 if (GET_CODE (op0) == REG)
370 op0 = gen_rtx_SUBREG (fieldmode, op0, byte_offset);
372 op0 = adjust_address (op0, fieldmode, offset);
374 emit_move_insn (op0, value);
378 /* Make sure we are playing with integral modes. Pun with subregs
379 if we aren't. This must come after the entire register case above,
380 since that case is valid for any mode. The following cases are only
381 valid for integral modes. */
383 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
384 if (imode != GET_MODE (op0))
386 if (GET_CODE (op0) == MEM)
387 op0 = adjust_address (op0, imode, 0);
388 else if (imode != BLKmode)
389 op0 = gen_lowpart (imode, op0);
395 /* If OP0 is a register, BITPOS must count within a word.
396 But as we have it, it counts within whatever size OP0 now has.
397 On a bigendian machine, these are not the same, so convert. */
399 && GET_CODE (op0) != MEM
400 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
401 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
403 /* Storing an lsb-aligned field in a register
404 can be done with a movestrict instruction. */
406 if (GET_CODE (op0) != MEM
407 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
408 && bitsize == GET_MODE_BITSIZE (fieldmode)
409 && (movstrict_optab->handlers[(int) fieldmode].insn_code
410 != CODE_FOR_nothing))
412 int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
414 /* Get appropriate low part of the value being stored. */
415 if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
416 value = gen_lowpart (fieldmode, value);
417 else if (!(GET_CODE (value) == SYMBOL_REF
418 || GET_CODE (value) == LABEL_REF
419 || GET_CODE (value) == CONST))
420 value = convert_to_mode (fieldmode, value, 0);
422 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
423 value = copy_to_mode_reg (fieldmode, value);
425 if (GET_CODE (op0) == SUBREG)
427 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
428 || GET_MODE_CLASS (fieldmode) == MODE_INT
429 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
430 op0 = SUBREG_REG (op0);
432 /* Else we've got some float mode source being extracted into
433 a different float mode destination -- this combination of
434 subregs results in Severe Tire Damage. */
438 emit_insn (GEN_FCN (icode)
439 (gen_rtx_SUBREG (fieldmode, op0,
440 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
441 + (offset * UNITS_PER_WORD)),
447 /* Handle fields bigger than a word. */
449 if (bitsize > BITS_PER_WORD)
451 /* Here we transfer the words of the field
452 in the order least significant first.
453 This is because the most significant word is the one which may
455 However, only do that if the value is not BLKmode. */
457 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
458 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
461 /* This is the mode we must force value to, so that there will be enough
462 subwords to extract. Note that fieldmode will often (always?) be
463 VOIDmode, because that is what store_field uses to indicate that this
464 is a bit field, but passing VOIDmode to operand_subword_force will
465 result in an abort. */
466 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
468 for (i = 0; i < nwords; i++)
470 /* If I is 0, use the low-order word in both field and target;
471 if I is 1, use the next to lowest word; and so on. */
472 unsigned int wordnum = (backwards ? nwords - i - 1 : i);
473 unsigned int bit_offset = (backwards
474 ? MAX ((int) bitsize - ((int) i + 1)
477 : (int) i * BITS_PER_WORD);
479 store_bit_field (op0, MIN (BITS_PER_WORD,
480 bitsize - i * BITS_PER_WORD),
481 bitnum + bit_offset, word_mode,
482 operand_subword_force (value, wordnum,
483 (GET_MODE (value) == VOIDmode
485 : GET_MODE (value))),
491 /* From here on we can assume that the field to be stored in is
492 a full-word (whatever type that is), since it is shorter than a word. */
494 /* OFFSET is the number of words or bytes (UNIT says which)
495 from STR_RTX to the first word or byte containing part of the field. */
497 if (GET_CODE (op0) != MEM)
500 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
502 if (GET_CODE (op0) != REG)
504 /* Since this is a destination (lvalue), we can't copy it to a
505 pseudo. We can trivially remove a SUBREG that does not
506 change the size of the operand. Such a SUBREG may have been
507 added above. Otherwise, abort. */
508 if (GET_CODE (op0) == SUBREG
509 && (GET_MODE_SIZE (GET_MODE (op0))
510 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
511 op0 = SUBREG_REG (op0);
515 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
516 op0, (offset * UNITS_PER_WORD));
521 op0 = protect_from_queue (op0, 1);
523 /* If VALUE is a floating-point mode, access it as an integer of the
524 corresponding size. This can occur on a machine with 64 bit registers
525 that uses SFmode for float. This can also occur for unaligned float
527 if (GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
528 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
529 value = gen_lowpart (word_mode, value);
531 /* Now OFFSET is nonzero only if OP0 is memory
532 and is therefore always measured in bytes. */
535 && GET_MODE (value) != BLKmode
536 && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
537 /* Ensure insv's size is wide enough for this field. */
538 && (GET_MODE_BITSIZE (op_mode) >= bitsize)
539 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
540 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))))
542 int xbitpos = bitpos;
545 rtx last = get_last_insn ();
547 enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
548 int save_volatile_ok = volatile_ok;
552 /* If this machine's insv can only insert into a register, copy OP0
553 into a register and save it back later. */
554 /* This used to check flag_force_mem, but that was a serious
555 de-optimization now that flag_force_mem is enabled by -O2. */
556 if (GET_CODE (op0) == MEM
557 && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
561 enum machine_mode bestmode;
563 /* Get the mode to use for inserting into this field. If OP0 is
564 BLKmode, get the smallest mode consistent with the alignment. If
565 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
566 mode. Otherwise, use the smallest mode containing the field. */
568 if (GET_MODE (op0) == BLKmode
569 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
571 = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
572 MEM_VOLATILE_P (op0));
574 bestmode = GET_MODE (op0);
576 if (bestmode == VOIDmode
577 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
578 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
581 /* Adjust address to point to the containing unit of that mode.
582 Compute offset as multiple of this unit, counting in bytes. */
583 unit = GET_MODE_BITSIZE (bestmode);
584 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
585 bitpos = bitnum % unit;
586 op0 = adjust_address (op0, bestmode, offset);
588 /* Fetch that unit, store the bitfield in it, then store
590 tempreg = copy_to_reg (op0);
591 store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
593 emit_move_insn (op0, tempreg);
596 volatile_ok = save_volatile_ok;
598 /* Add OFFSET into OP0's address. */
599 if (GET_CODE (xop0) == MEM)
600 xop0 = adjust_address (xop0, byte_mode, offset);
602 /* If xop0 is a register, we need it in MAXMODE
603 to make it acceptable to the format of insv. */
604 if (GET_CODE (xop0) == SUBREG)
605 /* We can't just change the mode, because this might clobber op0,
606 and we will need the original value of op0 if insv fails. */
607 xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
608 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
609 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
611 /* On big-endian machines, we count bits from the most significant.
612 If the bit field insn does not, we must invert. */
614 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
615 xbitpos = unit - bitsize - xbitpos;
617 /* We have been counting XBITPOS within UNIT.
618 Count instead within the size of the register. */
619 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
620 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
622 unit = GET_MODE_BITSIZE (maxmode);
624 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */
626 if (GET_MODE (value) != maxmode)
628 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
630 /* Optimization: Don't bother really extending VALUE
631 if it has all the bits we will actually use. However,
632 if we must narrow it, be sure we do it correctly. */
634 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
638 tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0);
640 tmp = simplify_gen_subreg (maxmode,
641 force_reg (GET_MODE (value),
643 GET_MODE (value), 0);
647 value1 = gen_lowpart (maxmode, value1);
649 else if (GET_CODE (value) == CONST_INT)
650 value1 = GEN_INT (trunc_int_for_mode (INTVAL (value), maxmode));
651 else if (!CONSTANT_P (value))
652 /* Parse phase is supposed to make VALUE's data type
653 match that of the component reference, which is a type
654 at least as wide as the field; so VALUE should have
655 a mode that corresponds to that type. */
659 /* If this machine's insv insists on a register,
660 get VALUE1 into a register. */
661 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
663 value1 = force_reg (maxmode, value1);
665 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
670 delete_insns_since (last);
671 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
676 /* Insv is not available; store using shifts and boolean ops. */
677 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
681 /* Use shifts and boolean operations to store VALUE
682 into a bit field of width BITSIZE
683 in a memory location specified by OP0 except offset by OFFSET bytes.
684 (OFFSET must be 0 if OP0 is a register.)
685 The field starts at position BITPOS within the byte.
686 (If OP0 is a register, it may be a full word or a narrower mode,
687 but BITPOS still counts within a full word,
688 which is significant on bigendian machines.)
690 Note that protect_from_queue has already been done on OP0 and VALUE. */
693 store_fixed_bit_field (op0, offset, bitsize, bitpos, value)
695 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
698 enum machine_mode mode;
699 unsigned int total_bits = BITS_PER_WORD;
704 /* There is a case not handled here:
705 a structure with a known alignment of just a halfword
706 and a field split across two aligned halfwords within the structure.
707 Or likewise a structure with a known alignment of just a byte
708 and a field split across two bytes.
709 Such cases are not supposed to be able to occur. */
711 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
715 /* Special treatment for a bit field split across two registers. */
716 if (bitsize + bitpos > BITS_PER_WORD)
718 store_split_bit_field (op0, bitsize, bitpos, value);
724 /* Get the proper mode to use for this field. We want a mode that
725 includes the entire field. If such a mode would be larger than
726 a word, we won't be doing the extraction the normal way.
727 We don't want a mode bigger than the destination. */
729 mode = GET_MODE (op0);
730 if (GET_MODE_BITSIZE (mode) == 0
731 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
733 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
734 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
736 if (mode == VOIDmode)
738 /* The only way this should occur is if the field spans word
740 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
745 total_bits = GET_MODE_BITSIZE (mode);
747 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
748 be in the range 0 to total_bits-1, and put any excess bytes in
750 if (bitpos >= total_bits)
752 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
753 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
757 /* Get ref to an aligned byte, halfword, or word containing the field.
758 Adjust BITPOS to be position within a word,
759 and OFFSET to be the offset of that word.
760 Then alter OP0 to refer to that word. */
761 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
762 offset -= (offset % (total_bits / BITS_PER_UNIT));
763 op0 = adjust_address (op0, mode, offset);
766 mode = GET_MODE (op0);
768 /* Now MODE is either some integral mode for a MEM as OP0,
769 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
770 The bit field is contained entirely within OP0.
771 BITPOS is the starting bit number within OP0.
772 (OP0's mode may actually be narrower than MODE.) */
774 if (BYTES_BIG_ENDIAN)
775 /* BITPOS is the distance between our msb
776 and that of the containing datum.
777 Convert it to the distance from the lsb. */
778 bitpos = total_bits - bitsize - bitpos;
780 /* Now BITPOS is always the distance between our lsb
783 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
784 we must first convert its mode to MODE. */
786 if (GET_CODE (value) == CONST_INT)
788 HOST_WIDE_INT v = INTVAL (value);
790 if (bitsize < HOST_BITS_PER_WIDE_INT)
791 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
795 else if ((bitsize < HOST_BITS_PER_WIDE_INT
796 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
797 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
800 value = lshift_value (mode, value, bitpos, bitsize);
804 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
805 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
807 if (GET_MODE (value) != mode)
809 if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
810 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
811 value = gen_lowpart (mode, value);
813 value = convert_to_mode (mode, value, 1);
817 value = expand_binop (mode, and_optab, value,
818 mask_rtx (mode, 0, bitsize, 0),
819 NULL_RTX, 1, OPTAB_LIB_WIDEN);
821 value = expand_shift (LSHIFT_EXPR, mode, value,
822 build_int_2 (bitpos, 0), NULL_RTX, 1);
825 /* Now clear the chosen bits in OP0,
826 except that if VALUE is -1 we need not bother. */
828 subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
832 temp = expand_binop (mode, and_optab, op0,
833 mask_rtx (mode, bitpos, bitsize, 1),
834 subtarget, 1, OPTAB_LIB_WIDEN);
840 /* Now logical-or VALUE into OP0, unless it is zero. */
843 temp = expand_binop (mode, ior_optab, temp, value,
844 subtarget, 1, OPTAB_LIB_WIDEN);
846 emit_move_insn (op0, temp);
849 /* Store a bit field that is split across multiple accessible memory objects.
851 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
852 BITSIZE is the field width; BITPOS the position of its first bit
854 VALUE is the value to store.
856 This does not yet handle fields wider than BITS_PER_WORD. */
859 store_split_bit_field (op0, bitsize, bitpos, value)
861 unsigned HOST_WIDE_INT bitsize, bitpos;
865 unsigned int bitsdone = 0;
867 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
869 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
870 unit = BITS_PER_WORD;
872 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
874 /* If VALUE is a constant other than a CONST_INT, get it into a register in
875 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
876 that VALUE might be a floating-point constant. */
877 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
879 rtx word = gen_lowpart_common (word_mode, value);
881 if (word && (value != word))
884 value = gen_lowpart_common (word_mode,
885 force_reg (GET_MODE (value) != VOIDmode
887 : word_mode, value));
889 else if (GET_CODE (value) == ADDRESSOF)
890 value = copy_to_reg (value);
892 while (bitsdone < bitsize)
894 unsigned HOST_WIDE_INT thissize;
896 unsigned HOST_WIDE_INT thispos;
897 unsigned HOST_WIDE_INT offset;
899 offset = (bitpos + bitsdone) / unit;
900 thispos = (bitpos + bitsdone) % unit;
902 /* THISSIZE must not overrun a word boundary. Otherwise,
903 store_fixed_bit_field will call us again, and we will mutually
905 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
906 thissize = MIN (thissize, unit - thispos);
908 if (BYTES_BIG_ENDIAN)
912 /* We must do an endian conversion exactly the same way as it is
913 done in extract_bit_field, so that the two calls to
914 extract_fixed_bit_field will have comparable arguments. */
915 if (GET_CODE (value) != MEM || GET_MODE (value) == BLKmode)
916 total_bits = BITS_PER_WORD;
918 total_bits = GET_MODE_BITSIZE (GET_MODE (value));
920 /* Fetch successively less significant portions. */
921 if (GET_CODE (value) == CONST_INT)
922 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
923 >> (bitsize - bitsdone - thissize))
924 & (((HOST_WIDE_INT) 1 << thissize) - 1));
926 /* The args are chosen so that the last part includes the
927 lsb. Give extract_bit_field the value it needs (with
928 endianness compensation) to fetch the piece we want. */
929 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
930 total_bits - bitsize + bitsdone,
935 /* Fetch successively more significant portions. */
936 if (GET_CODE (value) == CONST_INT)
937 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
939 & (((HOST_WIDE_INT) 1 << thissize) - 1));
941 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
942 bitsdone, NULL_RTX, 1);
945 /* If OP0 is a register, then handle OFFSET here.
947 When handling multiword bitfields, extract_bit_field may pass
948 down a word_mode SUBREG of a larger REG for a bitfield that actually
949 crosses a word boundary. Thus, for a SUBREG, we must find
950 the current word starting from the base register. */
951 if (GET_CODE (op0) == SUBREG)
953 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
954 word = operand_subword_force (SUBREG_REG (op0), word_offset,
955 GET_MODE (SUBREG_REG (op0)));
958 else if (GET_CODE (op0) == REG)
960 word = operand_subword_force (op0, offset, GET_MODE (op0));
966 /* OFFSET is in UNITs, and UNIT is in bits.
967 store_fixed_bit_field wants offset in bytes. */
968 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
970 bitsdone += thissize;
974 /* Generate code to extract a byte-field from STR_RTX
975 containing BITSIZE bits, starting at BITNUM,
976 and put it in TARGET if possible (if TARGET is nonzero).
977 Regardless of TARGET, we return the rtx for where the value is placed.
980 STR_RTX is the structure containing the byte (a REG or MEM).
981 UNSIGNEDP is nonzero if this is an unsigned bit field.
982 MODE is the natural mode of the field value once extracted.
983 TMODE is the mode the caller would like the value to have;
984 but the value may be returned with type MODE instead.
986 TOTAL_SIZE is the size in bytes of the containing structure,
989 If a TARGET is specified and we can store in it at no extra cost,
990 we do so, and return TARGET.
991 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
992 if they are equally easy. */
995 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
996 target, mode, tmode, total_size)
998 unsigned HOST_WIDE_INT bitsize;
999 unsigned HOST_WIDE_INT bitnum;
1002 enum machine_mode mode, tmode;
1003 HOST_WIDE_INT total_size;
1006 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
1007 unsigned HOST_WIDE_INT offset = bitnum / unit;
1008 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
1010 rtx spec_target = target;
1011 rtx spec_target_subreg = 0;
1012 enum machine_mode int_mode;
1013 enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1014 enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1015 enum machine_mode mode1;
1018 /* Discount the part of the structure before the desired byte.
1019 We need to know how many bytes are safe to reference after it. */
1020 if (total_size >= 0)
1021 total_size -= (bitpos / BIGGEST_ALIGNMENT
1022 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
1024 if (tmode == VOIDmode)
1026 while (GET_CODE (op0) == SUBREG)
1028 int outer_size = GET_MODE_BITSIZE (GET_MODE (op0));
1029 int inner_size = GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (op0)));
1031 offset += SUBREG_BYTE (op0) / UNITS_PER_WORD;
1033 inner_size = MIN (inner_size, BITS_PER_WORD);
1035 if (BYTES_BIG_ENDIAN && (outer_size < inner_size))
1037 bitpos += inner_size - outer_size;
1040 offset += (bitpos / unit);
1045 op0 = SUBREG_REG (op0);
1048 if (GET_CODE (op0) == REG
1049 && mode == GET_MODE (op0)
1051 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1053 /* We're trying to extract a full register from itself. */
1057 /* Make sure we are playing with integral modes. Pun with subregs
1060 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1061 if (imode != GET_MODE (op0))
1063 if (GET_CODE (op0) == MEM)
1064 op0 = adjust_address (op0, imode, 0);
1065 else if (imode != BLKmode)
1066 op0 = gen_lowpart (imode, op0);
1072 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1073 If that's wrong, the solution is to test for it and set TARGET to 0
1076 /* If OP0 is a register, BITPOS must count within a word.
1077 But as we have it, it counts within whatever size OP0 now has.
1078 On a bigendian machine, these are not the same, so convert. */
1079 if (BYTES_BIG_ENDIAN
1080 && GET_CODE (op0) != MEM
1081 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1082 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1084 /* Extracting a full-word or multi-word value
1085 from a structure in a register or aligned memory.
1086 This can be done with just SUBREG.
1087 So too extracting a subword value in
1088 the least significant part of the register. */
1090 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
1091 + (offset * UNITS_PER_WORD);
1093 mode1 = (VECTOR_MODE_P (tmode)
1095 : mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0));
1097 if (((GET_CODE (op0) != MEM
1098 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1099 GET_MODE_BITSIZE (GET_MODE (op0)))
1100 && GET_MODE_SIZE (mode1) != 0
1101 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1102 || (GET_CODE (op0) == MEM
1103 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1104 || (offset * BITS_PER_UNIT % bitsize == 0
1105 && MEM_ALIGN (op0) % bitsize == 0))))
1106 && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1107 && bitpos % BITS_PER_WORD == 0)
1108 || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
1109 /* ??? The big endian test here is wrong. This is correct
1110 if the value is in a register, and if mode_for_size is not
1111 the same mode as op0. This causes us to get unnecessarily
1112 inefficient code from the Thumb port when -mbig-endian. */
1113 && (BYTES_BIG_ENDIAN
1114 ? bitpos + bitsize == BITS_PER_WORD
1117 if (mode1 != GET_MODE (op0))
1119 if (GET_CODE (op0) == SUBREG)
1121 if (GET_MODE (SUBREG_REG (op0)) == mode1
1122 || GET_MODE_CLASS (mode1) == MODE_INT
1123 || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1124 op0 = SUBREG_REG (op0);
1126 /* Else we've got some float mode source being extracted into
1127 a different float mode destination -- this combination of
1128 subregs results in Severe Tire Damage. */
1131 if (GET_CODE (op0) == REG)
1132 op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1134 op0 = adjust_address (op0, mode1, offset);
1137 return convert_to_mode (tmode, op0, unsignedp);
1141 /* Handle fields bigger than a word. */
1143 if (bitsize > BITS_PER_WORD)
1145 /* Here we transfer the words of the field
1146 in the order least significant first.
1147 This is because the most significant word is the one which may
1148 be less than full. */
1150 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1153 if (target == 0 || GET_CODE (target) != REG)
1154 target = gen_reg_rtx (mode);
1156 /* Indicate for flow that the entire target reg is being set. */
1157 emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1159 for (i = 0; i < nwords; i++)
1161 /* If I is 0, use the low-order word in both field and target;
1162 if I is 1, use the next to lowest word; and so on. */
1163 /* Word number in TARGET to use. */
1164 unsigned int wordnum
1166 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1168 /* Offset from start of field in OP0. */
1169 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1170 ? MAX (0, ((int) bitsize - ((int) i + 1)
1171 * (int) BITS_PER_WORD))
1172 : (int) i * BITS_PER_WORD);
1173 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1175 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1176 bitsize - i * BITS_PER_WORD),
1177 bitnum + bit_offset, 1, target_part, mode,
1178 word_mode, total_size);
1180 if (target_part == 0)
1183 if (result_part != target_part)
1184 emit_move_insn (target_part, result_part);
1189 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1190 need to be zero'd out. */
1191 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1193 unsigned int i, total_words;
1195 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1196 for (i = nwords; i < total_words; i++)
1198 (operand_subword (target,
1199 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1206 /* Signed bit field: sign-extend with two arithmetic shifts. */
1207 target = expand_shift (LSHIFT_EXPR, mode, target,
1208 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1210 return expand_shift (RSHIFT_EXPR, mode, target,
1211 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1215 /* From here on we know the desired field is smaller than a word. */
1217 /* Check if there is a correspondingly-sized integer field, so we can
1218 safely extract it as one size of integer, if necessary; then
1219 truncate or extend to the size that is wanted; then use SUBREGs or
1220 convert_to_mode to get one of the modes we really wanted. */
1222 int_mode = int_mode_for_mode (tmode);
1223 if (int_mode == BLKmode)
1224 int_mode = int_mode_for_mode (mode);
1225 if (int_mode == BLKmode)
1226 abort (); /* Should probably push op0 out to memory and then
1229 /* OFFSET is the number of words or bytes (UNIT says which)
1230 from STR_RTX to the first word or byte containing part of the field. */
1232 if (GET_CODE (op0) != MEM)
1235 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1237 if (GET_CODE (op0) != REG)
1238 op0 = copy_to_reg (op0);
1239 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1240 op0, (offset * UNITS_PER_WORD));
1245 op0 = protect_from_queue (str_rtx, 1);
1247 /* Now OFFSET is nonzero only for memory operands. */
1252 && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1253 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1254 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1256 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1257 rtx bitsize_rtx, bitpos_rtx;
1258 rtx last = get_last_insn ();
1260 rtx xtarget = target;
1261 rtx xspec_target = spec_target;
1262 rtx xspec_target_subreg = spec_target_subreg;
1264 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1266 if (GET_CODE (xop0) == MEM)
1268 int save_volatile_ok = volatile_ok;
1271 /* Is the memory operand acceptable? */
1272 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1273 (xop0, GET_MODE (xop0))))
1275 /* No, load into a reg and extract from there. */
1276 enum machine_mode bestmode;
1278 /* Get the mode to use for inserting into this field. If
1279 OP0 is BLKmode, get the smallest mode consistent with the
1280 alignment. If OP0 is a non-BLKmode object that is no
1281 wider than MAXMODE, use its mode. Otherwise, use the
1282 smallest mode containing the field. */
1284 if (GET_MODE (xop0) == BLKmode
1285 || (GET_MODE_SIZE (GET_MODE (op0))
1286 > GET_MODE_SIZE (maxmode)))
1287 bestmode = get_best_mode (bitsize, bitnum,
1288 MEM_ALIGN (xop0), maxmode,
1289 MEM_VOLATILE_P (xop0));
1291 bestmode = GET_MODE (xop0);
1293 if (bestmode == VOIDmode
1294 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1295 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1298 /* Compute offset as multiple of this unit,
1299 counting in bytes. */
1300 unit = GET_MODE_BITSIZE (bestmode);
1301 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1302 xbitpos = bitnum % unit;
1303 xop0 = adjust_address (xop0, bestmode, xoffset);
1305 /* Fetch it to a register in that size. */
1306 xop0 = force_reg (bestmode, xop0);
1308 /* XBITPOS counts within UNIT, which is what is expected. */
1311 /* Get ref to first byte containing part of the field. */
1312 xop0 = adjust_address (xop0, byte_mode, xoffset);
1314 volatile_ok = save_volatile_ok;
1317 /* If op0 is a register, we need it in MAXMODE (which is usually
1318 SImode). to make it acceptable to the format of extzv. */
1319 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1321 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1322 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1324 /* On big-endian machines, we count bits from the most significant.
1325 If the bit field insn does not, we must invert. */
1326 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1327 xbitpos = unit - bitsize - xbitpos;
1329 /* Now convert from counting within UNIT to counting in MAXMODE. */
1330 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1331 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1333 unit = GET_MODE_BITSIZE (maxmode);
1336 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1337 xtarget = xspec_target = gen_reg_rtx (tmode);
1339 if (GET_MODE (xtarget) != maxmode)
1341 if (GET_CODE (xtarget) == REG)
1343 int wider = (GET_MODE_SIZE (maxmode)
1344 > GET_MODE_SIZE (GET_MODE (xtarget)));
1345 xtarget = gen_lowpart (maxmode, xtarget);
1347 xspec_target_subreg = xtarget;
1350 xtarget = gen_reg_rtx (maxmode);
1353 /* If this machine's extzv insists on a register target,
1354 make sure we have one. */
1355 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1356 (xtarget, maxmode)))
1357 xtarget = gen_reg_rtx (maxmode);
1359 bitsize_rtx = GEN_INT (bitsize);
1360 bitpos_rtx = GEN_INT (xbitpos);
1362 pat = gen_extzv (protect_from_queue (xtarget, 1),
1363 xop0, bitsize_rtx, bitpos_rtx);
1368 spec_target = xspec_target;
1369 spec_target_subreg = xspec_target_subreg;
1373 delete_insns_since (last);
1374 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1380 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1386 && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1387 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1388 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1390 int xbitpos = bitpos, xoffset = offset;
1391 rtx bitsize_rtx, bitpos_rtx;
1392 rtx last = get_last_insn ();
1393 rtx xop0 = op0, xtarget = target;
1394 rtx xspec_target = spec_target;
1395 rtx xspec_target_subreg = spec_target_subreg;
1397 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1399 if (GET_CODE (xop0) == MEM)
1401 /* Is the memory operand acceptable? */
1402 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1403 (xop0, GET_MODE (xop0))))
1405 /* No, load into a reg and extract from there. */
1406 enum machine_mode bestmode;
1408 /* Get the mode to use for inserting into this field. If
1409 OP0 is BLKmode, get the smallest mode consistent with the
1410 alignment. If OP0 is a non-BLKmode object that is no
1411 wider than MAXMODE, use its mode. Otherwise, use the
1412 smallest mode containing the field. */
1414 if (GET_MODE (xop0) == BLKmode
1415 || (GET_MODE_SIZE (GET_MODE (op0))
1416 > GET_MODE_SIZE (maxmode)))
1417 bestmode = get_best_mode (bitsize, bitnum,
1418 MEM_ALIGN (xop0), maxmode,
1419 MEM_VOLATILE_P (xop0));
1421 bestmode = GET_MODE (xop0);
1423 if (bestmode == VOIDmode
1424 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1425 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1428 /* Compute offset as multiple of this unit,
1429 counting in bytes. */
1430 unit = GET_MODE_BITSIZE (bestmode);
1431 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1432 xbitpos = bitnum % unit;
1433 xop0 = adjust_address (xop0, bestmode, xoffset);
1435 /* Fetch it to a register in that size. */
1436 xop0 = force_reg (bestmode, xop0);
1438 /* XBITPOS counts within UNIT, which is what is expected. */
1441 /* Get ref to first byte containing part of the field. */
1442 xop0 = adjust_address (xop0, byte_mode, xoffset);
1445 /* If op0 is a register, we need it in MAXMODE (which is usually
1446 SImode) to make it acceptable to the format of extv. */
1447 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1449 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1450 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1452 /* On big-endian machines, we count bits from the most significant.
1453 If the bit field insn does not, we must invert. */
1454 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1455 xbitpos = unit - bitsize - xbitpos;
1457 /* XBITPOS counts within a size of UNIT.
1458 Adjust to count within a size of MAXMODE. */
1459 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1460 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1462 unit = GET_MODE_BITSIZE (maxmode);
1465 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1466 xtarget = xspec_target = gen_reg_rtx (tmode);
1468 if (GET_MODE (xtarget) != maxmode)
1470 if (GET_CODE (xtarget) == REG)
1472 int wider = (GET_MODE_SIZE (maxmode)
1473 > GET_MODE_SIZE (GET_MODE (xtarget)));
1474 xtarget = gen_lowpart (maxmode, xtarget);
1476 xspec_target_subreg = xtarget;
1479 xtarget = gen_reg_rtx (maxmode);
1482 /* If this machine's extv insists on a register target,
1483 make sure we have one. */
1484 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1485 (xtarget, maxmode)))
1486 xtarget = gen_reg_rtx (maxmode);
1488 bitsize_rtx = GEN_INT (bitsize);
1489 bitpos_rtx = GEN_INT (xbitpos);
1491 pat = gen_extv (protect_from_queue (xtarget, 1),
1492 xop0, bitsize_rtx, bitpos_rtx);
1497 spec_target = xspec_target;
1498 spec_target_subreg = xspec_target_subreg;
1502 delete_insns_since (last);
1503 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1509 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1512 if (target == spec_target)
1514 if (target == spec_target_subreg)
1516 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1518 /* If the target mode is floating-point, first convert to the
1519 integer mode of that size and then access it as a floating-point
1520 value via a SUBREG. */
1521 if (GET_MODE_CLASS (tmode) != MODE_INT
1522 && GET_MODE_CLASS (tmode) != MODE_PARTIAL_INT)
1524 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1527 return gen_lowpart (tmode, target);
1530 return convert_to_mode (tmode, target, unsignedp);
1535 /* Extract a bit field using shifts and boolean operations
1536 Returns an rtx to represent the value.
1537 OP0 addresses a register (word) or memory (byte).
1538 BITPOS says which bit within the word or byte the bit field starts in.
1539 OFFSET says how many bytes farther the bit field starts;
1540 it is 0 if OP0 is a register.
1541 BITSIZE says how many bits long the bit field is.
1542 (If OP0 is a register, it may be narrower than a full word,
1543 but BITPOS still counts within a full word,
1544 which is significant on bigendian machines.)
1546 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1547 If TARGET is nonzero, attempts to store the value there
1548 and return TARGET, but this is not guaranteed.
1549 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1552 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1554 enum machine_mode tmode;
1556 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
1559 unsigned int total_bits = BITS_PER_WORD;
1560 enum machine_mode mode;
1562 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1564 /* Special treatment for a bit field split across two registers. */
1565 if (bitsize + bitpos > BITS_PER_WORD)
1566 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1570 /* Get the proper mode to use for this field. We want a mode that
1571 includes the entire field. If such a mode would be larger than
1572 a word, we won't be doing the extraction the normal way. */
1574 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1575 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1577 if (mode == VOIDmode)
1578 /* The only way this should occur is if the field spans word
1580 return extract_split_bit_field (op0, bitsize,
1581 bitpos + offset * BITS_PER_UNIT,
1584 total_bits = GET_MODE_BITSIZE (mode);
1586 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1587 be in the range 0 to total_bits-1, and put any excess bytes in
1589 if (bitpos >= total_bits)
1591 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1592 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1596 /* Get ref to an aligned byte, halfword, or word containing the field.
1597 Adjust BITPOS to be position within a word,
1598 and OFFSET to be the offset of that word.
1599 Then alter OP0 to refer to that word. */
1600 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1601 offset -= (offset % (total_bits / BITS_PER_UNIT));
1602 op0 = adjust_address (op0, mode, offset);
1605 mode = GET_MODE (op0);
1607 if (BYTES_BIG_ENDIAN)
1608 /* BITPOS is the distance between our msb and that of OP0.
1609 Convert it to the distance from the lsb. */
1610 bitpos = total_bits - bitsize - bitpos;
1612 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1613 We have reduced the big-endian case to the little-endian case. */
1619 /* If the field does not already start at the lsb,
1620 shift it so it does. */
1621 tree amount = build_int_2 (bitpos, 0);
1622 /* Maybe propagate the target for the shift. */
1623 /* But not if we will return it--could confuse integrate.c. */
1624 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1625 && !REG_FUNCTION_VALUE_P (target)
1627 if (tmode != mode) subtarget = 0;
1628 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1630 /* Convert the value to the desired mode. */
1632 op0 = convert_to_mode (tmode, op0, 1);
1634 /* Unless the msb of the field used to be the msb when we shifted,
1635 mask out the upper bits. */
1637 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1638 return expand_binop (GET_MODE (op0), and_optab, op0,
1639 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1640 target, 1, OPTAB_LIB_WIDEN);
1644 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1645 then arithmetic-shift its lsb to the lsb of the word. */
1646 op0 = force_reg (mode, op0);
1650 /* Find the narrowest integer mode that contains the field. */
1652 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1653 mode = GET_MODE_WIDER_MODE (mode))
1654 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1656 op0 = convert_to_mode (mode, op0, 0);
1660 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1663 = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1664 /* Maybe propagate the target for the shift. */
1665 /* But not if we will return the result--could confuse integrate.c. */
1666 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1667 && ! REG_FUNCTION_VALUE_P (target)
1669 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1672 return expand_shift (RSHIFT_EXPR, mode, op0,
1673 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1677 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1678 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1679 complement of that if COMPLEMENT. The mask is truncated if
1680 necessary to the width of mode MODE. The mask is zero-extended if
1681 BITSIZE+BITPOS is too small for MODE. */
1684 mask_rtx (mode, bitpos, bitsize, complement)
1685 enum machine_mode mode;
1686 int bitpos, bitsize, complement;
1688 HOST_WIDE_INT masklow, maskhigh;
1690 if (bitpos < HOST_BITS_PER_WIDE_INT)
1691 masklow = (HOST_WIDE_INT) -1 << bitpos;
1695 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1696 masklow &= ((unsigned HOST_WIDE_INT) -1
1697 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1699 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1702 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1704 if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1705 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1706 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1712 maskhigh = ~maskhigh;
1716 return immed_double_const (masklow, maskhigh, mode);
1719 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1720 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1723 lshift_value (mode, value, bitpos, bitsize)
1724 enum machine_mode mode;
1726 int bitpos, bitsize;
1728 unsigned HOST_WIDE_INT v = INTVAL (value);
1729 HOST_WIDE_INT low, high;
1731 if (bitsize < HOST_BITS_PER_WIDE_INT)
1732 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1734 if (bitpos < HOST_BITS_PER_WIDE_INT)
1737 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1742 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1745 return immed_double_const (low, high, mode);
1748 /* Extract a bit field that is split across two words
1749 and return an RTX for the result.
1751 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1752 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1753 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1756 extract_split_bit_field (op0, bitsize, bitpos, unsignedp)
1758 unsigned HOST_WIDE_INT bitsize, bitpos;
1762 unsigned int bitsdone = 0;
1763 rtx result = NULL_RTX;
1766 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1768 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1769 unit = BITS_PER_WORD;
1771 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1773 while (bitsdone < bitsize)
1775 unsigned HOST_WIDE_INT thissize;
1777 unsigned HOST_WIDE_INT thispos;
1778 unsigned HOST_WIDE_INT offset;
1780 offset = (bitpos + bitsdone) / unit;
1781 thispos = (bitpos + bitsdone) % unit;
1783 /* THISSIZE must not overrun a word boundary. Otherwise,
1784 extract_fixed_bit_field will call us again, and we will mutually
1786 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1787 thissize = MIN (thissize, unit - thispos);
1789 /* If OP0 is a register, then handle OFFSET here.
1791 When handling multiword bitfields, extract_bit_field may pass
1792 down a word_mode SUBREG of a larger REG for a bitfield that actually
1793 crosses a word boundary. Thus, for a SUBREG, we must find
1794 the current word starting from the base register. */
1795 if (GET_CODE (op0) == SUBREG)
1797 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1798 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1799 GET_MODE (SUBREG_REG (op0)));
1802 else if (GET_CODE (op0) == REG)
1804 word = operand_subword_force (op0, offset, GET_MODE (op0));
1810 /* Extract the parts in bit-counting order,
1811 whose meaning is determined by BYTES_PER_UNIT.
1812 OFFSET is in UNITs, and UNIT is in bits.
1813 extract_fixed_bit_field wants offset in bytes. */
1814 part = extract_fixed_bit_field (word_mode, word,
1815 offset * unit / BITS_PER_UNIT,
1816 thissize, thispos, 0, 1);
1817 bitsdone += thissize;
1819 /* Shift this part into place for the result. */
1820 if (BYTES_BIG_ENDIAN)
1822 if (bitsize != bitsdone)
1823 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1824 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1828 if (bitsdone != thissize)
1829 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1830 build_int_2 (bitsdone - thissize, 0), 0, 1);
1836 /* Combine the parts with bitwise or. This works
1837 because we extracted each part as an unsigned bit field. */
1838 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1844 /* Unsigned bit field: we are done. */
1847 /* Signed bit field: sign-extend with two arithmetic shifts. */
1848 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1849 build_int_2 (BITS_PER_WORD - bitsize, 0),
1851 return expand_shift (RSHIFT_EXPR, word_mode, result,
1852 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1855 /* Add INC into TARGET. */
1858 expand_inc (target, inc)
1861 rtx value = expand_binop (GET_MODE (target), add_optab,
1863 target, 0, OPTAB_LIB_WIDEN);
1864 if (value != target)
1865 emit_move_insn (target, value);
1868 /* Subtract DEC from TARGET. */
1871 expand_dec (target, dec)
1874 rtx value = expand_binop (GET_MODE (target), sub_optab,
1876 target, 0, OPTAB_LIB_WIDEN);
1877 if (value != target)
1878 emit_move_insn (target, value);
1881 /* Output a shift instruction for expression code CODE,
1882 with SHIFTED being the rtx for the value to shift,
1883 and AMOUNT the tree for the amount to shift by.
1884 Store the result in the rtx TARGET, if that is convenient.
1885 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1886 Return the rtx for where the value is. */
1889 expand_shift (code, mode, shifted, amount, target, unsignedp)
1890 enum tree_code code;
1891 enum machine_mode mode;
1898 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1899 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1902 /* Previously detected shift-counts computed by NEGATE_EXPR
1903 and shifted in the other direction; but that does not work
1906 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1908 #ifdef SHIFT_COUNT_TRUNCATED
1909 if (SHIFT_COUNT_TRUNCATED)
1911 if (GET_CODE (op1) == CONST_INT
1912 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
1913 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
1914 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
1915 % GET_MODE_BITSIZE (mode));
1916 else if (GET_CODE (op1) == SUBREG
1917 && subreg_lowpart_p (op1))
1918 op1 = SUBREG_REG (op1);
1922 if (op1 == const0_rtx)
1925 for (try = 0; temp == 0 && try < 3; try++)
1927 enum optab_methods methods;
1930 methods = OPTAB_DIRECT;
1932 methods = OPTAB_WIDEN;
1934 methods = OPTAB_LIB_WIDEN;
1938 /* Widening does not work for rotation. */
1939 if (methods == OPTAB_WIDEN)
1941 else if (methods == OPTAB_LIB_WIDEN)
1943 /* If we have been unable to open-code this by a rotation,
1944 do it as the IOR of two shifts. I.e., to rotate A
1945 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
1946 where C is the bitsize of A.
1948 It is theoretically possible that the target machine might
1949 not be able to perform either shift and hence we would
1950 be making two libcalls rather than just the one for the
1951 shift (similarly if IOR could not be done). We will allow
1952 this extremely unlikely lossage to avoid complicating the
1955 rtx subtarget = target == shifted ? 0 : target;
1957 tree type = TREE_TYPE (amount);
1958 tree new_amount = make_tree (type, op1);
1960 = fold (build (MINUS_EXPR, type,
1962 build_int_2 (GET_MODE_BITSIZE (mode),
1966 shifted = force_reg (mode, shifted);
1968 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
1969 mode, shifted, new_amount, subtarget, 1);
1970 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
1971 mode, shifted, other_amount, 0, 1);
1972 return expand_binop (mode, ior_optab, temp, temp1, target,
1973 unsignedp, methods);
1976 temp = expand_binop (mode,
1977 left ? rotl_optab : rotr_optab,
1978 shifted, op1, target, unsignedp, methods);
1980 /* If we don't have the rotate, but we are rotating by a constant
1981 that is in range, try a rotate in the opposite direction. */
1983 if (temp == 0 && GET_CODE (op1) == CONST_INT
1985 && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
1986 temp = expand_binop (mode,
1987 left ? rotr_optab : rotl_optab,
1989 GEN_INT (GET_MODE_BITSIZE (mode)
1991 target, unsignedp, methods);
1994 temp = expand_binop (mode,
1995 left ? ashl_optab : lshr_optab,
1996 shifted, op1, target, unsignedp, methods);
1998 /* Do arithmetic shifts.
1999 Also, if we are going to widen the operand, we can just as well
2000 use an arithmetic right-shift instead of a logical one. */
2001 if (temp == 0 && ! rotate
2002 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2004 enum optab_methods methods1 = methods;
2006 /* If trying to widen a log shift to an arithmetic shift,
2007 don't accept an arithmetic shift of the same size. */
2009 methods1 = OPTAB_MUST_WIDEN;
2011 /* Arithmetic shift */
2013 temp = expand_binop (mode,
2014 left ? ashl_optab : ashr_optab,
2015 shifted, op1, target, unsignedp, methods1);
2018 /* We used to try extzv here for logical right shifts, but that was
2019 only useful for one machine, the VAX, and caused poor code
2020 generation there for lshrdi3, so the code was deleted and a
2021 define_expand for lshrsi3 was added to vax.md. */
2029 enum alg_code { alg_zero, alg_m, alg_shift,
2030 alg_add_t_m2, alg_sub_t_m2,
2031 alg_add_factor, alg_sub_factor,
2032 alg_add_t2_m, alg_sub_t2_m,
2033 alg_add, alg_subtract, alg_factor, alg_shiftop };
2035 /* This structure records a sequence of operations.
2036 `ops' is the number of operations recorded.
2037 `cost' is their total cost.
2038 The operations are stored in `op' and the corresponding
2039 logarithms of the integer coefficients in `log'.
2041 These are the operations:
2042 alg_zero total := 0;
2043 alg_m total := multiplicand;
2044 alg_shift total := total * coeff
2045 alg_add_t_m2 total := total + multiplicand * coeff;
2046 alg_sub_t_m2 total := total - multiplicand * coeff;
2047 alg_add_factor total := total * coeff + total;
2048 alg_sub_factor total := total * coeff - total;
2049 alg_add_t2_m total := total * coeff + multiplicand;
2050 alg_sub_t2_m total := total * coeff - multiplicand;
2052 The first operand must be either alg_zero or alg_m. */
2058 /* The size of the OP and LOG fields are not directly related to the
2059 word size, but the worst-case algorithms will be if we have few
2060 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2061 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2062 in total wordsize operations. */
2063 enum alg_code op[MAX_BITS_PER_WORD];
2064 char log[MAX_BITS_PER_WORD];
2067 static void synth_mult PARAMS ((struct algorithm *,
2068 unsigned HOST_WIDE_INT,
2070 static unsigned HOST_WIDE_INT choose_multiplier PARAMS ((unsigned HOST_WIDE_INT,
2072 unsigned HOST_WIDE_INT *,
2074 static unsigned HOST_WIDE_INT invert_mod2n PARAMS ((unsigned HOST_WIDE_INT,
2076 /* Compute and return the best algorithm for multiplying by T.
2077 The algorithm must cost less than cost_limit
2078 If retval.cost >= COST_LIMIT, no algorithm was found and all
2079 other field of the returned struct are undefined. */
2082 synth_mult (alg_out, t, cost_limit)
2083 struct algorithm *alg_out;
2084 unsigned HOST_WIDE_INT t;
2088 struct algorithm *alg_in, *best_alg;
2090 unsigned HOST_WIDE_INT q;
2092 /* Indicate that no algorithm is yet found. If no algorithm
2093 is found, this value will be returned and indicate failure. */
2094 alg_out->cost = cost_limit;
2096 if (cost_limit <= 0)
2099 /* t == 1 can be done in zero cost. */
2104 alg_out->op[0] = alg_m;
2108 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2112 if (zero_cost >= cost_limit)
2117 alg_out->cost = zero_cost;
2118 alg_out->op[0] = alg_zero;
2123 /* We'll be needing a couple extra algorithm structures now. */
2125 alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
2126 best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
2128 /* If we have a group of zero bits at the low-order part of T, try
2129 multiplying by the remaining bits and then doing a shift. */
2133 m = floor_log2 (t & -t); /* m = number of low zero bits */
2134 if (m < BITS_PER_WORD)
2137 cost = shift_cost[m];
2138 synth_mult (alg_in, q, cost_limit - cost);
2140 cost += alg_in->cost;
2141 if (cost < cost_limit)
2143 struct algorithm *x;
2144 x = alg_in, alg_in = best_alg, best_alg = x;
2145 best_alg->log[best_alg->ops] = m;
2146 best_alg->op[best_alg->ops] = alg_shift;
2152 /* If we have an odd number, add or subtract one. */
2155 unsigned HOST_WIDE_INT w;
2157 for (w = 1; (w & t) != 0; w <<= 1)
2159 /* If T was -1, then W will be zero after the loop. This is another
2160 case where T ends with ...111. Handling this with (T + 1) and
2161 subtract 1 produces slightly better code and results in algorithm
2162 selection much faster than treating it like the ...0111 case
2166 /* Reject the case where t is 3.
2167 Thus we prefer addition in that case. */
2170 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2173 synth_mult (alg_in, t + 1, cost_limit - cost);
2175 cost += alg_in->cost;
2176 if (cost < cost_limit)
2178 struct algorithm *x;
2179 x = alg_in, alg_in = best_alg, best_alg = x;
2180 best_alg->log[best_alg->ops] = 0;
2181 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2187 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2190 synth_mult (alg_in, t - 1, cost_limit - cost);
2192 cost += alg_in->cost;
2193 if (cost < cost_limit)
2195 struct algorithm *x;
2196 x = alg_in, alg_in = best_alg, best_alg = x;
2197 best_alg->log[best_alg->ops] = 0;
2198 best_alg->op[best_alg->ops] = alg_add_t_m2;
2204 /* Look for factors of t of the form
2205 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2206 If we find such a factor, we can multiply by t using an algorithm that
2207 multiplies by q, shift the result by m and add/subtract it to itself.
2209 We search for large factors first and loop down, even if large factors
2210 are less probable than small; if we find a large factor we will find a
2211 good sequence quickly, and therefore be able to prune (by decreasing
2212 COST_LIMIT) the search. */
2214 for (m = floor_log2 (t - 1); m >= 2; m--)
2216 unsigned HOST_WIDE_INT d;
2218 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2219 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2221 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2222 synth_mult (alg_in, t / d, cost_limit - cost);
2224 cost += alg_in->cost;
2225 if (cost < cost_limit)
2227 struct algorithm *x;
2228 x = alg_in, alg_in = best_alg, best_alg = x;
2229 best_alg->log[best_alg->ops] = m;
2230 best_alg->op[best_alg->ops] = alg_add_factor;
2233 /* Other factors will have been taken care of in the recursion. */
2237 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2238 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2240 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2241 synth_mult (alg_in, t / d, cost_limit - cost);
2243 cost += alg_in->cost;
2244 if (cost < cost_limit)
2246 struct algorithm *x;
2247 x = alg_in, alg_in = best_alg, best_alg = x;
2248 best_alg->log[best_alg->ops] = m;
2249 best_alg->op[best_alg->ops] = alg_sub_factor;
2256 /* Try shift-and-add (load effective address) instructions,
2257 i.e. do a*3, a*5, a*9. */
2263 if (m >= 0 && m < BITS_PER_WORD)
2265 cost = shiftadd_cost[m];
2266 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2268 cost += alg_in->cost;
2269 if (cost < cost_limit)
2271 struct algorithm *x;
2272 x = alg_in, alg_in = best_alg, best_alg = x;
2273 best_alg->log[best_alg->ops] = m;
2274 best_alg->op[best_alg->ops] = alg_add_t2_m;
2282 if (m >= 0 && m < BITS_PER_WORD)
2284 cost = shiftsub_cost[m];
2285 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2287 cost += alg_in->cost;
2288 if (cost < cost_limit)
2290 struct algorithm *x;
2291 x = alg_in, alg_in = best_alg, best_alg = x;
2292 best_alg->log[best_alg->ops] = m;
2293 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2299 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2300 we have not found any algorithm. */
2301 if (cost_limit == alg_out->cost)
2304 /* If we are getting a too long sequence for `struct algorithm'
2305 to record, make this search fail. */
2306 if (best_alg->ops == MAX_BITS_PER_WORD)
2309 /* Copy the algorithm from temporary space to the space at alg_out.
2310 We avoid using structure assignment because the majority of
2311 best_alg is normally undefined, and this is a critical function. */
2312 alg_out->ops = best_alg->ops + 1;
2313 alg_out->cost = cost_limit;
2314 memcpy (alg_out->op, best_alg->op,
2315 alg_out->ops * sizeof *alg_out->op);
2316 memcpy (alg_out->log, best_alg->log,
2317 alg_out->ops * sizeof *alg_out->log);
2320 /* Perform a multiplication and return an rtx for the result.
2321 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2322 TARGET is a suggestion for where to store the result (an rtx).
2324 We check specially for a constant integer as OP1.
2325 If you want this check for OP0 as well, then before calling
2326 you should swap the two operands if OP0 would be constant. */
2329 expand_mult (mode, op0, op1, target, unsignedp)
2330 enum machine_mode mode;
2331 rtx op0, op1, target;
2334 rtx const_op1 = op1;
2336 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2337 less than or equal in size to `unsigned int' this doesn't matter.
2338 If the mode is larger than `unsigned int', then synth_mult works only
2339 if the constant value exactly fits in an `unsigned int' without any
2340 truncation. This means that multiplying by negative values does
2341 not work; results are off by 2^32 on a 32 bit machine. */
2343 /* If we are multiplying in DImode, it may still be a win
2344 to try to work with shifts and adds. */
2345 if (GET_CODE (op1) == CONST_DOUBLE
2346 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2347 && HOST_BITS_PER_INT >= BITS_PER_WORD
2348 && CONST_DOUBLE_HIGH (op1) == 0)
2349 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2350 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2351 && GET_CODE (op1) == CONST_INT
2352 && INTVAL (op1) < 0)
2355 /* We used to test optimize here, on the grounds that it's better to
2356 produce a smaller program when -O is not used.
2357 But this causes such a terrible slowdown sometimes
2358 that it seems better to use synth_mult always. */
2360 if (const_op1 && GET_CODE (const_op1) == CONST_INT
2361 && (unsignedp || ! flag_trapv))
2363 struct algorithm alg;
2364 struct algorithm alg2;
2365 HOST_WIDE_INT val = INTVAL (op1);
2366 HOST_WIDE_INT val_so_far;
2369 enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2371 /* op0 must be register to make mult_cost match the precomputed
2372 shiftadd_cost array. */
2373 op0 = force_reg (mode, op0);
2375 /* Try to do the computation three ways: multiply by the negative of OP1
2376 and then negate, do the multiplication directly, or do multiplication
2379 mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2380 mult_cost = MIN (12 * add_cost, mult_cost);
2382 synth_mult (&alg, val, mult_cost);
2384 /* This works only if the inverted value actually fits in an
2386 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2388 synth_mult (&alg2, - val,
2389 (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2390 if (alg2.cost + negate_cost < alg.cost)
2391 alg = alg2, variant = negate_variant;
2394 /* This proves very useful for division-by-constant. */
2395 synth_mult (&alg2, val - 1,
2396 (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2397 if (alg2.cost + add_cost < alg.cost)
2398 alg = alg2, variant = add_variant;
2400 if (alg.cost < mult_cost)
2402 /* We found something cheaper than a multiply insn. */
2405 enum machine_mode nmode;
2407 op0 = protect_from_queue (op0, 0);
2409 /* Avoid referencing memory over and over.
2410 For speed, but also for correctness when mem is volatile. */
2411 if (GET_CODE (op0) == MEM)
2412 op0 = force_reg (mode, op0);
2414 /* ACCUM starts out either as OP0 or as a zero, depending on
2415 the first operation. */
2417 if (alg.op[0] == alg_zero)
2419 accum = copy_to_mode_reg (mode, const0_rtx);
2422 else if (alg.op[0] == alg_m)
2424 accum = copy_to_mode_reg (mode, op0);
2430 for (opno = 1; opno < alg.ops; opno++)
2432 int log = alg.log[opno];
2433 int preserve = preserve_subexpressions_p ();
2434 rtx shift_subtarget = preserve ? 0 : accum;
2436 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2439 rtx accum_target = preserve ? 0 : accum;
2441 switch (alg.op[opno])
2444 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2445 build_int_2 (log, 0), NULL_RTX, 0);
2450 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2451 build_int_2 (log, 0), NULL_RTX, 0);
2452 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2454 ? add_target : accum_target);
2455 val_so_far += (HOST_WIDE_INT) 1 << log;
2459 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2460 build_int_2 (log, 0), NULL_RTX, 0);
2461 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2463 ? add_target : accum_target);
2464 val_so_far -= (HOST_WIDE_INT) 1 << log;
2468 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2469 build_int_2 (log, 0), shift_subtarget,
2471 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2473 ? add_target : accum_target);
2474 val_so_far = (val_so_far << log) + 1;
2478 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2479 build_int_2 (log, 0), shift_subtarget,
2481 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2483 ? add_target : accum_target);
2484 val_so_far = (val_so_far << log) - 1;
2487 case alg_add_factor:
2488 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2489 build_int_2 (log, 0), NULL_RTX, 0);
2490 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2492 ? add_target : accum_target);
2493 val_so_far += val_so_far << log;
2496 case alg_sub_factor:
2497 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2498 build_int_2 (log, 0), NULL_RTX, 0);
2499 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2500 (add_target ? add_target
2501 : preserve ? 0 : tem));
2502 val_so_far = (val_so_far << log) - val_so_far;
2509 /* Write a REG_EQUAL note on the last insn so that we can cse
2510 multiplication sequences. Note that if ACCUM is a SUBREG,
2511 we've set the inner register and must properly indicate
2514 tem = op0, nmode = mode;
2515 if (GET_CODE (accum) == SUBREG)
2517 nmode = GET_MODE (SUBREG_REG (accum));
2518 tem = gen_lowpart (nmode, op0);
2521 insn = get_last_insn ();
2522 set_unique_reg_note (insn,
2524 gen_rtx_MULT (nmode, tem,
2525 GEN_INT (val_so_far)));
2528 if (variant == negate_variant)
2530 val_so_far = - val_so_far;
2531 accum = expand_unop (mode, neg_optab, accum, target, 0);
2533 else if (variant == add_variant)
2535 val_so_far = val_so_far + 1;
2536 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2539 if (val != val_so_far)
2546 /* This used to use umul_optab if unsigned, but for non-widening multiply
2547 there is no difference between signed and unsigned. */
2548 op0 = expand_binop (mode,
2550 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2551 ? smulv_optab : smul_optab,
2552 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2558 /* Return the smallest n such that 2**n >= X. */
2562 unsigned HOST_WIDE_INT x;
2564 return floor_log2 (x - 1) + 1;
2567 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2568 replace division by D, and put the least significant N bits of the result
2569 in *MULTIPLIER_PTR and return the most significant bit.
2571 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2572 needed precision is in PRECISION (should be <= N).
2574 PRECISION should be as small as possible so this function can choose
2575 multiplier more freely.
2577 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2578 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2580 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2581 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2584 unsigned HOST_WIDE_INT
2585 choose_multiplier (d, n, precision, multiplier_ptr, post_shift_ptr, lgup_ptr)
2586 unsigned HOST_WIDE_INT d;
2589 unsigned HOST_WIDE_INT *multiplier_ptr;
2590 int *post_shift_ptr;
2593 HOST_WIDE_INT mhigh_hi, mlow_hi;
2594 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2595 int lgup, post_shift;
2597 unsigned HOST_WIDE_INT nl, dummy1;
2598 HOST_WIDE_INT nh, dummy2;
2600 /* lgup = ceil(log2(divisor)); */
2601 lgup = ceil_log2 (d);
2607 pow2 = n + lgup - precision;
2609 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2611 /* We could handle this with some effort, but this case is much better
2612 handled directly with a scc insn, so rely on caller using that. */
2616 /* mlow = 2^(N + lgup)/d */
2617 if (pow >= HOST_BITS_PER_WIDE_INT)
2619 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2625 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2627 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2628 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2630 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2631 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2632 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2634 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2635 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2636 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2638 if (mhigh_hi && nh - d >= d)
2640 if (mhigh_hi > 1 || mlow_hi > 1)
2642 /* assert that mlow < mhigh. */
2643 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2646 /* If precision == N, then mlow, mhigh exceed 2^N
2647 (but they do not exceed 2^(N+1)). */
2649 /* Reduce to lowest terms */
2650 for (post_shift = lgup; post_shift > 0; post_shift--)
2652 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2653 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2663 *post_shift_ptr = post_shift;
2665 if (n < HOST_BITS_PER_WIDE_INT)
2667 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2668 *multiplier_ptr = mhigh_lo & mask;
2669 return mhigh_lo >= mask;
2673 *multiplier_ptr = mhigh_lo;
2678 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2679 congruent to 1 (mod 2**N). */
2681 static unsigned HOST_WIDE_INT
2683 unsigned HOST_WIDE_INT x;
2686 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2688 /* The algorithm notes that the choice y = x satisfies
2689 x*y == 1 mod 2^3, since x is assumed odd.
2690 Each iteration doubles the number of bits of significance in y. */
2692 unsigned HOST_WIDE_INT mask;
2693 unsigned HOST_WIDE_INT y = x;
2696 mask = (n == HOST_BITS_PER_WIDE_INT
2697 ? ~(unsigned HOST_WIDE_INT) 0
2698 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2702 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2708 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2709 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2710 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2711 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2714 The result is put in TARGET if that is convenient.
2716 MODE is the mode of operation. */
2719 expand_mult_highpart_adjust (mode, adj_operand, op0, op1, target, unsignedp)
2720 enum machine_mode mode;
2721 rtx adj_operand, op0, op1, target;
2725 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2727 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2728 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2730 tem = expand_and (mode, tem, op1, NULL_RTX);
2732 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2735 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2736 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2738 tem = expand_and (mode, tem, op0, NULL_RTX);
2739 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2745 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2746 in TARGET if that is convenient, and return where the result is. If the
2747 operation can not be performed, 0 is returned.
2749 MODE is the mode of operation and result.
2751 UNSIGNEDP nonzero means unsigned multiply.
2753 MAX_COST is the total allowed cost for the expanded RTL. */
2756 expand_mult_highpart (mode, op0, cnst1, target, unsignedp, max_cost)
2757 enum machine_mode mode;
2759 unsigned HOST_WIDE_INT cnst1;
2763 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2764 optab mul_highpart_optab;
2767 int size = GET_MODE_BITSIZE (mode);
2770 /* We can't support modes wider than HOST_BITS_PER_INT. */
2771 if (size > HOST_BITS_PER_WIDE_INT)
2774 op1 = GEN_INT (trunc_int_for_mode (cnst1, mode));
2777 = immed_double_const (cnst1,
2780 : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2783 /* expand_mult handles constant multiplication of word_mode
2784 or narrower. It does a poor job for large modes. */
2785 if (size < BITS_PER_WORD
2786 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2788 /* We have to do this, since expand_binop doesn't do conversion for
2789 multiply. Maybe change expand_binop to handle widening multiply? */
2790 op0 = convert_to_mode (wider_mode, op0, unsignedp);
2792 /* We know that this can't have signed overflow, so pretend this is
2793 an unsigned multiply. */
2794 tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, 0);
2795 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2796 build_int_2 (size, 0), NULL_RTX, 1);
2797 return convert_modes (mode, wider_mode, tem, unsignedp);
2801 target = gen_reg_rtx (mode);
2803 /* Firstly, try using a multiplication insn that only generates the needed
2804 high part of the product, and in the sign flavor of unsignedp. */
2805 if (mul_highpart_cost[(int) mode] < max_cost)
2807 mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2808 target = expand_binop (mode, mul_highpart_optab,
2809 op0, op1, target, unsignedp, OPTAB_DIRECT);
2814 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2815 Need to adjust the result after the multiplication. */
2816 if (size - 1 < BITS_PER_WORD
2817 && (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost
2820 mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2821 target = expand_binop (mode, mul_highpart_optab,
2822 op0, op1, target, unsignedp, OPTAB_DIRECT);
2824 /* We used the wrong signedness. Adjust the result. */
2825 return expand_mult_highpart_adjust (mode, target, op0,
2826 op1, target, unsignedp);
2829 /* Try widening multiplication. */
2830 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2831 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2832 && mul_widen_cost[(int) wider_mode] < max_cost)
2834 op1 = force_reg (mode, op1);
2838 /* Try widening the mode and perform a non-widening multiplication. */
2839 moptab = smul_optab;
2840 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2841 && size - 1 < BITS_PER_WORD
2842 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2848 /* Try widening multiplication of opposite signedness, and adjust. */
2849 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2850 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2851 && size - 1 < BITS_PER_WORD
2852 && (mul_widen_cost[(int) wider_mode]
2853 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2855 rtx regop1 = force_reg (mode, op1);
2856 tem = expand_binop (wider_mode, moptab, op0, regop1,
2857 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2860 /* Extract the high half of the just generated product. */
2861 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2862 build_int_2 (size, 0), NULL_RTX, 1);
2863 tem = convert_modes (mode, wider_mode, tem, unsignedp);
2864 /* We used the wrong signedness. Adjust the result. */
2865 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2873 /* Pass NULL_RTX as target since TARGET has wrong mode. */
2874 tem = expand_binop (wider_mode, moptab, op0, op1,
2875 NULL_RTX, unsignedp, OPTAB_WIDEN);
2879 /* Extract the high half of the just generated product. */
2880 if (mode == word_mode)
2882 return gen_highpart (mode, tem);
2886 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2887 build_int_2 (size, 0), NULL_RTX, 1);
2888 return convert_modes (mode, wider_mode, tem, unsignedp);
2892 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2893 if that is convenient, and returning where the result is.
2894 You may request either the quotient or the remainder as the result;
2895 specify REM_FLAG nonzero to get the remainder.
2897 CODE is the expression code for which kind of division this is;
2898 it controls how rounding is done. MODE is the machine mode to use.
2899 UNSIGNEDP nonzero means do unsigned division. */
2901 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2902 and then correct it by or'ing in missing high bits
2903 if result of ANDI is nonzero.
2904 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2905 This could optimize to a bfexts instruction.
2906 But C doesn't use these operations, so their optimizations are
2908 /* ??? For modulo, we don't actually need the highpart of the first product,
2909 the low part will do nicely. And for small divisors, the second multiply
2910 can also be a low-part only multiply or even be completely left out.
2911 E.g. to calculate the remainder of a division by 3 with a 32 bit
2912 multiply, multiply with 0x55555556 and extract the upper two bits;
2913 the result is exact for inputs up to 0x1fffffff.
2914 The input range can be reduced by using cross-sum rules.
2915 For odd divisors >= 3, the following table gives right shift counts
2916 so that if an number is shifted by an integer multiple of the given
2917 amount, the remainder stays the same:
2918 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
2919 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
2920 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
2921 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
2922 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
2924 Cross-sum rules for even numbers can be derived by leaving as many bits
2925 to the right alone as the divisor has zeros to the right.
2926 E.g. if x is an unsigned 32 bit number:
2927 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
2930 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
2933 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2935 enum tree_code code;
2936 enum machine_mode mode;
2937 rtx op0, op1, target;
2940 enum machine_mode compute_mode;
2942 rtx quotient = 0, remainder = 0;
2946 optab optab1, optab2;
2947 int op1_is_constant, op1_is_pow2;
2948 int max_cost, extra_cost;
2949 static HOST_WIDE_INT last_div_const = 0;
2951 op1_is_constant = GET_CODE (op1) == CONST_INT;
2952 op1_is_pow2 = (op1_is_constant
2953 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
2954 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1))))));
2957 This is the structure of expand_divmod:
2959 First comes code to fix up the operands so we can perform the operations
2960 correctly and efficiently.
2962 Second comes a switch statement with code specific for each rounding mode.
2963 For some special operands this code emits all RTL for the desired
2964 operation, for other cases, it generates only a quotient and stores it in
2965 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
2966 to indicate that it has not done anything.
2968 Last comes code that finishes the operation. If QUOTIENT is set and
2969 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
2970 QUOTIENT is not set, it is computed using trunc rounding.
2972 We try to generate special code for division and remainder when OP1 is a
2973 constant. If |OP1| = 2**n we can use shifts and some other fast
2974 operations. For other values of OP1, we compute a carefully selected
2975 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
2978 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
2979 half of the product. Different strategies for generating the product are
2980 implemented in expand_mult_highpart.
2982 If what we actually want is the remainder, we generate that by another
2983 by-constant multiplication and a subtraction. */
2985 /* We shouldn't be called with OP1 == const1_rtx, but some of the
2986 code below will malfunction if we are, so check here and handle
2987 the special case if so. */
2988 if (op1 == const1_rtx)
2989 return rem_flag ? const0_rtx : op0;
2991 /* When dividing by -1, we could get an overflow.
2992 negv_optab can handle overflows. */
2993 if (! unsignedp && op1 == constm1_rtx)
2997 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
2998 ? negv_optab : neg_optab, op0, target, 0);
3002 /* Don't use the function value register as a target
3003 since we have to read it as well as write it,
3004 and function-inlining gets confused by this. */
3005 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3006 /* Don't clobber an operand while doing a multi-step calculation. */
3007 || ((rem_flag || op1_is_constant)
3008 && (reg_mentioned_p (target, op0)
3009 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
3010 || reg_mentioned_p (target, op1)
3011 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
3014 /* Get the mode in which to perform this computation. Normally it will
3015 be MODE, but sometimes we can't do the desired operation in MODE.
3016 If so, pick a wider mode in which we can do the operation. Convert
3017 to that mode at the start to avoid repeated conversions.
3019 First see what operations we need. These depend on the expression
3020 we are evaluating. (We assume that divxx3 insns exist under the
3021 same conditions that modxx3 insns and that these insns don't normally
3022 fail. If these assumptions are not correct, we may generate less
3023 efficient code in some cases.)
3025 Then see if we find a mode in which we can open-code that operation
3026 (either a division, modulus, or shift). Finally, check for the smallest
3027 mode for which we can do the operation with a library call. */
3029 /* We might want to refine this now that we have division-by-constant
3030 optimization. Since expand_mult_highpart tries so many variants, it is
3031 not straightforward to generalize this. Maybe we should make an array
3032 of possible modes in init_expmed? Save this for GCC 2.7. */
3034 optab1 = (op1_is_pow2 ? (unsignedp ? lshr_optab : ashr_optab)
3035 : (unsignedp ? udiv_optab : sdiv_optab));
3036 optab2 = (op1_is_pow2 ? optab1 : (unsignedp ? udivmod_optab : sdivmod_optab));
3038 for (compute_mode = mode; compute_mode != VOIDmode;
3039 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3040 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
3041 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
3044 if (compute_mode == VOIDmode)
3045 for (compute_mode = mode; compute_mode != VOIDmode;
3046 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3047 if (optab1->handlers[(int) compute_mode].libfunc
3048 || optab2->handlers[(int) compute_mode].libfunc)
3051 /* If we still couldn't find a mode, use MODE, but we'll probably abort
3053 if (compute_mode == VOIDmode)
3054 compute_mode = mode;
3056 if (target && GET_MODE (target) == compute_mode)
3059 tquotient = gen_reg_rtx (compute_mode);
3061 size = GET_MODE_BITSIZE (compute_mode);
3063 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3064 (mode), and thereby get better code when OP1 is a constant. Do that
3065 later. It will require going over all usages of SIZE below. */
3066 size = GET_MODE_BITSIZE (mode);
3069 /* Only deduct something for a REM if the last divide done was
3070 for a different constant. Then set the constant of the last
3072 max_cost = div_cost[(int) compute_mode]
3073 - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3074 && INTVAL (op1) == last_div_const)
3075 ? mul_cost[(int) compute_mode] + add_cost : 0);
3077 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3079 /* Now convert to the best mode to use. */
3080 if (compute_mode != mode)
3082 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3083 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3085 /* convert_modes may have placed op1 into a register, so we
3086 must recompute the following. */
3087 op1_is_constant = GET_CODE (op1) == CONST_INT;
3088 op1_is_pow2 = (op1_is_constant
3089 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3091 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3094 /* If one of the operands is a volatile MEM, copy it into a register. */
3096 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3097 op0 = force_reg (compute_mode, op0);
3098 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3099 op1 = force_reg (compute_mode, op1);
3101 /* If we need the remainder or if OP1 is constant, we need to
3102 put OP0 in a register in case it has any queued subexpressions. */
3103 if (rem_flag || op1_is_constant)
3104 op0 = force_reg (compute_mode, op0);
3106 last = get_last_insn ();
3108 /* Promote floor rounding to trunc rounding for unsigned operations. */
3111 if (code == FLOOR_DIV_EXPR)
3112 code = TRUNC_DIV_EXPR;
3113 if (code == FLOOR_MOD_EXPR)
3114 code = TRUNC_MOD_EXPR;
3115 if (code == EXACT_DIV_EXPR && op1_is_pow2)
3116 code = TRUNC_DIV_EXPR;
3119 if (op1 != const0_rtx)
3122 case TRUNC_MOD_EXPR:
3123 case TRUNC_DIV_EXPR:
3124 if (op1_is_constant)
3128 unsigned HOST_WIDE_INT mh, ml;
3129 int pre_shift, post_shift;
3131 unsigned HOST_WIDE_INT d = INTVAL (op1);
3133 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3135 pre_shift = floor_log2 (d);
3139 = expand_binop (compute_mode, and_optab, op0,
3140 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3144 return gen_lowpart (mode, remainder);
3146 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3147 build_int_2 (pre_shift, 0),
3150 else if (size <= HOST_BITS_PER_WIDE_INT)
3152 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3154 /* Most significant bit of divisor is set; emit an scc
3156 quotient = emit_store_flag (tquotient, GEU, op0, op1,
3157 compute_mode, 1, 1);
3163 /* Find a suitable multiplier and right shift count
3164 instead of multiplying with D. */
3166 mh = choose_multiplier (d, size, size,
3167 &ml, &post_shift, &dummy);
3169 /* If the suggested multiplier is more than SIZE bits,
3170 we can do better for even divisors, using an
3171 initial right shift. */
3172 if (mh != 0 && (d & 1) == 0)
3174 pre_shift = floor_log2 (d & -d);
3175 mh = choose_multiplier (d >> pre_shift, size,
3177 &ml, &post_shift, &dummy);
3188 if (post_shift - 1 >= BITS_PER_WORD)
3191 extra_cost = (shift_cost[post_shift - 1]
3192 + shift_cost[1] + 2 * add_cost);
3193 t1 = expand_mult_highpart (compute_mode, op0, ml,
3195 max_cost - extra_cost);
3198 t2 = force_operand (gen_rtx_MINUS (compute_mode,
3201 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3202 build_int_2 (1, 0), NULL_RTX,1);
3203 t4 = force_operand (gen_rtx_PLUS (compute_mode,
3207 = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3208 build_int_2 (post_shift - 1, 0),
3215 if (pre_shift >= BITS_PER_WORD
3216 || post_shift >= BITS_PER_WORD)
3219 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3220 build_int_2 (pre_shift, 0),
3222 extra_cost = (shift_cost[pre_shift]
3223 + shift_cost[post_shift]);
3224 t2 = expand_mult_highpart (compute_mode, t1, ml,
3226 max_cost - extra_cost);
3230 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3231 build_int_2 (post_shift, 0),
3236 else /* Too wide mode to use tricky code */
3239 insn = get_last_insn ();
3241 && (set = single_set (insn)) != 0
3242 && SET_DEST (set) == quotient)
3243 set_unique_reg_note (insn,
3245 gen_rtx_UDIV (compute_mode, op0, op1));
3247 else /* TRUNC_DIV, signed */
3249 unsigned HOST_WIDE_INT ml;
3250 int lgup, post_shift;
3251 HOST_WIDE_INT d = INTVAL (op1);
3252 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3254 /* n rem d = n rem -d */
3255 if (rem_flag && d < 0)
3258 op1 = GEN_INT (trunc_int_for_mode (abs_d, compute_mode));
3264 quotient = expand_unop (compute_mode, neg_optab, op0,
3266 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3268 /* This case is not handled correctly below. */
3269 quotient = emit_store_flag (tquotient, EQ, op0, op1,
3270 compute_mode, 1, 1);
3274 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3275 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap)
3276 /* ??? The cheap metric is computed only for
3277 word_mode. If this operation is wider, this may
3278 not be so. Assume true if the optab has an
3279 expander for this mode. */
3280 && (((rem_flag ? smod_optab : sdiv_optab)
3281 ->handlers[(int) compute_mode].insn_code
3282 != CODE_FOR_nothing)
3283 || (sdivmod_optab->handlers[(int) compute_mode]
3284 .insn_code != CODE_FOR_nothing)))
3286 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3288 lgup = floor_log2 (abs_d);
3289 if (BRANCH_COST < 1 || (abs_d != 2 && BRANCH_COST < 3))
3291 rtx label = gen_label_rtx ();
3294 t1 = copy_to_mode_reg (compute_mode, op0);
3295 do_cmp_and_jump (t1, const0_rtx, GE,
3296 compute_mode, label);
3297 expand_inc (t1, GEN_INT (trunc_int_for_mode
3298 (abs_d - 1, compute_mode)));
3300 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3301 build_int_2 (lgup, 0),
3307 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3308 build_int_2 (size - 1, 0),
3310 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3311 build_int_2 (size - lgup, 0),
3313 t3 = force_operand (gen_rtx_PLUS (compute_mode,
3316 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3317 build_int_2 (lgup, 0),
3321 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
3325 insn = get_last_insn ();
3327 && (set = single_set (insn)) != 0
3328 && SET_DEST (set) == quotient
3329 && abs_d < ((unsigned HOST_WIDE_INT) 1
3330 << (HOST_BITS_PER_WIDE_INT - 1)))
3331 set_unique_reg_note (insn,
3333 gen_rtx_DIV (compute_mode,
3340 quotient = expand_unop (compute_mode, neg_optab,
3341 quotient, quotient, 0);
3344 else if (size <= HOST_BITS_PER_WIDE_INT)
3346 choose_multiplier (abs_d, size, size - 1,
3347 &ml, &post_shift, &lgup);
3348 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3352 if (post_shift >= BITS_PER_WORD
3353 || size - 1 >= BITS_PER_WORD)
3356 extra_cost = (shift_cost[post_shift]
3357 + shift_cost[size - 1] + add_cost);
3358 t1 = expand_mult_highpart (compute_mode, op0, ml,
3360 max_cost - extra_cost);
3363 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3364 build_int_2 (post_shift, 0), NULL_RTX, 0);
3365 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3366 build_int_2 (size - 1, 0), NULL_RTX, 0);
3369 = force_operand (gen_rtx_MINUS (compute_mode,
3374 = force_operand (gen_rtx_MINUS (compute_mode,
3382 if (post_shift >= BITS_PER_WORD
3383 || size - 1 >= BITS_PER_WORD)
3386 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3387 extra_cost = (shift_cost[post_shift]
3388 + shift_cost[size - 1] + 2 * add_cost);
3389 t1 = expand_mult_highpart (compute_mode, op0, ml,
3391 max_cost - extra_cost);
3394 t2 = force_operand (gen_rtx_PLUS (compute_mode,
3397 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3398 build_int_2 (post_shift, 0),
3400 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3401 build_int_2 (size - 1, 0),
3405 = force_operand (gen_rtx_MINUS (compute_mode,
3410 = force_operand (gen_rtx_MINUS (compute_mode,
3415 else /* Too wide mode to use tricky code */
3418 insn = get_last_insn ();
3420 && (set = single_set (insn)) != 0
3421 && SET_DEST (set) == quotient)
3422 set_unique_reg_note (insn,
3424 gen_rtx_DIV (compute_mode, op0, op1));
3429 delete_insns_since (last);
3432 case FLOOR_DIV_EXPR:
3433 case FLOOR_MOD_EXPR:
3434 /* We will come here only for signed operations. */
3435 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3437 unsigned HOST_WIDE_INT mh, ml;
3438 int pre_shift, lgup, post_shift;
3439 HOST_WIDE_INT d = INTVAL (op1);
3443 /* We could just as easily deal with negative constants here,
3444 but it does not seem worth the trouble for GCC 2.6. */
3445 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3447 pre_shift = floor_log2 (d);
3450 remainder = expand_binop (compute_mode, and_optab, op0,
3451 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3452 remainder, 0, OPTAB_LIB_WIDEN);
3454 return gen_lowpart (mode, remainder);
3456 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3457 build_int_2 (pre_shift, 0),
3464 mh = choose_multiplier (d, size, size - 1,
3465 &ml, &post_shift, &lgup);
3469 if (post_shift < BITS_PER_WORD
3470 && size - 1 < BITS_PER_WORD)
3472 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3473 build_int_2 (size - 1, 0),
3475 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3476 NULL_RTX, 0, OPTAB_WIDEN);
3477 extra_cost = (shift_cost[post_shift]
3478 + shift_cost[size - 1] + 2 * add_cost);
3479 t3 = expand_mult_highpart (compute_mode, t2, ml,
3481 max_cost - extra_cost);
3484 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3485 build_int_2 (post_shift, 0),
3487 quotient = expand_binop (compute_mode, xor_optab,
3488 t4, t1, tquotient, 0,
3496 rtx nsign, t1, t2, t3, t4;
3497 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3498 op0, constm1_rtx), NULL_RTX);
3499 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3501 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3502 build_int_2 (size - 1, 0), NULL_RTX, 0);
3503 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3505 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3510 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3512 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3521 delete_insns_since (last);
3523 /* Try using an instruction that produces both the quotient and
3524 remainder, using truncation. We can easily compensate the quotient
3525 or remainder to get floor rounding, once we have the remainder.
3526 Notice that we compute also the final remainder value here,
3527 and return the result right away. */
3528 if (target == 0 || GET_MODE (target) != compute_mode)
3529 target = gen_reg_rtx (compute_mode);
3534 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3535 quotient = gen_reg_rtx (compute_mode);
3540 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3541 remainder = gen_reg_rtx (compute_mode);
3544 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3545 quotient, remainder, 0))
3547 /* This could be computed with a branch-less sequence.
3548 Save that for later. */
3550 rtx label = gen_label_rtx ();
3551 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3552 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3553 NULL_RTX, 0, OPTAB_WIDEN);
3554 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3555 expand_dec (quotient, const1_rtx);
3556 expand_inc (remainder, op1);
3558 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3561 /* No luck with division elimination or divmod. Have to do it
3562 by conditionally adjusting op0 *and* the result. */
3564 rtx label1, label2, label3, label4, label5;
3568 quotient = gen_reg_rtx (compute_mode);
3569 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3570 label1 = gen_label_rtx ();
3571 label2 = gen_label_rtx ();
3572 label3 = gen_label_rtx ();
3573 label4 = gen_label_rtx ();
3574 label5 = gen_label_rtx ();
3575 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3576 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3577 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3578 quotient, 0, OPTAB_LIB_WIDEN);
3579 if (tem != quotient)
3580 emit_move_insn (quotient, tem);
3581 emit_jump_insn (gen_jump (label5));
3583 emit_label (label1);
3584 expand_inc (adjusted_op0, const1_rtx);
3585 emit_jump_insn (gen_jump (label4));
3587 emit_label (label2);
3588 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3589 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3590 quotient, 0, OPTAB_LIB_WIDEN);
3591 if (tem != quotient)
3592 emit_move_insn (quotient, tem);
3593 emit_jump_insn (gen_jump (label5));
3595 emit_label (label3);
3596 expand_dec (adjusted_op0, const1_rtx);
3597 emit_label (label4);
3598 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3599 quotient, 0, OPTAB_LIB_WIDEN);
3600 if (tem != quotient)
3601 emit_move_insn (quotient, tem);
3602 expand_dec (quotient, const1_rtx);
3603 emit_label (label5);
3611 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3614 unsigned HOST_WIDE_INT d = INTVAL (op1);
3615 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3616 build_int_2 (floor_log2 (d), 0),
3618 t2 = expand_binop (compute_mode, and_optab, op0,
3620 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3621 t3 = gen_reg_rtx (compute_mode);
3622 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3623 compute_mode, 1, 1);
3627 lab = gen_label_rtx ();
3628 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3629 expand_inc (t1, const1_rtx);
3634 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3640 /* Try using an instruction that produces both the quotient and
3641 remainder, using truncation. We can easily compensate the
3642 quotient or remainder to get ceiling rounding, once we have the
3643 remainder. Notice that we compute also the final remainder
3644 value here, and return the result right away. */
3645 if (target == 0 || GET_MODE (target) != compute_mode)
3646 target = gen_reg_rtx (compute_mode);
3650 remainder = (GET_CODE (target) == REG
3651 ? target : gen_reg_rtx (compute_mode));
3652 quotient = gen_reg_rtx (compute_mode);
3656 quotient = (GET_CODE (target) == REG
3657 ? target : gen_reg_rtx (compute_mode));
3658 remainder = gen_reg_rtx (compute_mode);
3661 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3664 /* This could be computed with a branch-less sequence.
3665 Save that for later. */
3666 rtx label = gen_label_rtx ();
3667 do_cmp_and_jump (remainder, const0_rtx, EQ,
3668 compute_mode, label);
3669 expand_inc (quotient, const1_rtx);
3670 expand_dec (remainder, op1);
3672 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3675 /* No luck with division elimination or divmod. Have to do it
3676 by conditionally adjusting op0 *and* the result. */
3679 rtx adjusted_op0, tem;
3681 quotient = gen_reg_rtx (compute_mode);
3682 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3683 label1 = gen_label_rtx ();
3684 label2 = gen_label_rtx ();
3685 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3686 compute_mode, label1);
3687 emit_move_insn (quotient, const0_rtx);
3688 emit_jump_insn (gen_jump (label2));
3690 emit_label (label1);
3691 expand_dec (adjusted_op0, const1_rtx);
3692 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3693 quotient, 1, OPTAB_LIB_WIDEN);
3694 if (tem != quotient)
3695 emit_move_insn (quotient, tem);
3696 expand_inc (quotient, const1_rtx);
3697 emit_label (label2);
3702 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3703 && INTVAL (op1) >= 0)
3705 /* This is extremely similar to the code for the unsigned case
3706 above. For 2.7 we should merge these variants, but for
3707 2.6.1 I don't want to touch the code for unsigned since that
3708 get used in C. The signed case will only be used by other
3712 unsigned HOST_WIDE_INT d = INTVAL (op1);
3713 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3714 build_int_2 (floor_log2 (d), 0),
3716 t2 = expand_binop (compute_mode, and_optab, op0,
3718 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3719 t3 = gen_reg_rtx (compute_mode);
3720 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3721 compute_mode, 1, 1);
3725 lab = gen_label_rtx ();
3726 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3727 expand_inc (t1, const1_rtx);
3732 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3738 /* Try using an instruction that produces both the quotient and
3739 remainder, using truncation. We can easily compensate the
3740 quotient or remainder to get ceiling rounding, once we have the
3741 remainder. Notice that we compute also the final remainder
3742 value here, and return the result right away. */
3743 if (target == 0 || GET_MODE (target) != compute_mode)
3744 target = gen_reg_rtx (compute_mode);
3747 remainder= (GET_CODE (target) == REG
3748 ? target : gen_reg_rtx (compute_mode));
3749 quotient = gen_reg_rtx (compute_mode);
3753 quotient = (GET_CODE (target) == REG
3754 ? target : gen_reg_rtx (compute_mode));
3755 remainder = gen_reg_rtx (compute_mode);
3758 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3761 /* This could be computed with a branch-less sequence.
3762 Save that for later. */
3764 rtx label = gen_label_rtx ();
3765 do_cmp_and_jump (remainder, const0_rtx, EQ,
3766 compute_mode, label);
3767 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3768 NULL_RTX, 0, OPTAB_WIDEN);
3769 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3770 expand_inc (quotient, const1_rtx);
3771 expand_dec (remainder, op1);
3773 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3776 /* No luck with division elimination or divmod. Have to do it
3777 by conditionally adjusting op0 *and* the result. */
3779 rtx label1, label2, label3, label4, label5;
3783 quotient = gen_reg_rtx (compute_mode);
3784 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3785 label1 = gen_label_rtx ();
3786 label2 = gen_label_rtx ();
3787 label3 = gen_label_rtx ();
3788 label4 = gen_label_rtx ();
3789 label5 = gen_label_rtx ();
3790 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3791 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3792 compute_mode, label1);
3793 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3794 quotient, 0, OPTAB_LIB_WIDEN);
3795 if (tem != quotient)
3796 emit_move_insn (quotient, tem);
3797 emit_jump_insn (gen_jump (label5));
3799 emit_label (label1);
3800 expand_dec (adjusted_op0, const1_rtx);
3801 emit_jump_insn (gen_jump (label4));
3803 emit_label (label2);
3804 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3805 compute_mode, label3);
3806 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3807 quotient, 0, OPTAB_LIB_WIDEN);
3808 if (tem != quotient)
3809 emit_move_insn (quotient, tem);
3810 emit_jump_insn (gen_jump (label5));
3812 emit_label (label3);
3813 expand_inc (adjusted_op0, const1_rtx);
3814 emit_label (label4);
3815 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3816 quotient, 0, OPTAB_LIB_WIDEN);
3817 if (tem != quotient)
3818 emit_move_insn (quotient, tem);
3819 expand_inc (quotient, const1_rtx);
3820 emit_label (label5);
3825 case EXACT_DIV_EXPR:
3826 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3828 HOST_WIDE_INT d = INTVAL (op1);
3829 unsigned HOST_WIDE_INT ml;
3833 pre_shift = floor_log2 (d & -d);
3834 ml = invert_mod2n (d >> pre_shift, size);
3835 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3836 build_int_2 (pre_shift, 0), NULL_RTX, unsignedp);
3837 quotient = expand_mult (compute_mode, t1,
3838 GEN_INT (trunc_int_for_mode
3839 (ml, compute_mode)),
3842 insn = get_last_insn ();
3843 set_unique_reg_note (insn,
3845 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
3851 case ROUND_DIV_EXPR:
3852 case ROUND_MOD_EXPR:
3857 label = gen_label_rtx ();
3858 quotient = gen_reg_rtx (compute_mode);
3859 remainder = gen_reg_rtx (compute_mode);
3860 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3863 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3864 quotient, 1, OPTAB_LIB_WIDEN);
3865 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3866 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3867 remainder, 1, OPTAB_LIB_WIDEN);
3869 tem = plus_constant (op1, -1);
3870 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3871 build_int_2 (1, 0), NULL_RTX, 1);
3872 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
3873 expand_inc (quotient, const1_rtx);
3874 expand_dec (remainder, op1);
3879 rtx abs_rem, abs_op1, tem, mask;
3881 label = gen_label_rtx ();
3882 quotient = gen_reg_rtx (compute_mode);
3883 remainder = gen_reg_rtx (compute_mode);
3884 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3887 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3888 quotient, 0, OPTAB_LIB_WIDEN);
3889 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3890 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3891 remainder, 0, OPTAB_LIB_WIDEN);
3893 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
3894 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
3895 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3896 build_int_2 (1, 0), NULL_RTX, 1);
3897 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
3898 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3899 NULL_RTX, 0, OPTAB_WIDEN);
3900 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3901 build_int_2 (size - 1, 0), NULL_RTX, 0);
3902 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3903 NULL_RTX, 0, OPTAB_WIDEN);
3904 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3905 NULL_RTX, 0, OPTAB_WIDEN);
3906 expand_inc (quotient, tem);
3907 tem = expand_binop (compute_mode, xor_optab, mask, op1,
3908 NULL_RTX, 0, OPTAB_WIDEN);
3909 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3910 NULL_RTX, 0, OPTAB_WIDEN);
3911 expand_dec (remainder, tem);
3914 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3922 if (target && GET_MODE (target) != compute_mode)
3927 /* Try to produce the remainder without producing the quotient.
3928 If we seem to have a divmod pattern that does not require widening,
3929 don't try widening here. We should really have an WIDEN argument
3930 to expand_twoval_binop, since what we'd really like to do here is
3931 1) try a mod insn in compute_mode
3932 2) try a divmod insn in compute_mode
3933 3) try a div insn in compute_mode and multiply-subtract to get
3935 4) try the same things with widening allowed. */
3937 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3940 ((optab2->handlers[(int) compute_mode].insn_code
3941 != CODE_FOR_nothing)
3942 ? OPTAB_DIRECT : OPTAB_WIDEN));
3945 /* No luck there. Can we do remainder and divide at once
3946 without a library call? */
3947 remainder = gen_reg_rtx (compute_mode);
3948 if (! expand_twoval_binop ((unsignedp
3952 NULL_RTX, remainder, unsignedp))
3957 return gen_lowpart (mode, remainder);
3960 /* Produce the quotient. Try a quotient insn, but not a library call.
3961 If we have a divmod in this mode, use it in preference to widening
3962 the div (for this test we assume it will not fail). Note that optab2
3963 is set to the one of the two optabs that the call below will use. */
3965 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
3966 op0, op1, rem_flag ? NULL_RTX : target,
3968 ((optab2->handlers[(int) compute_mode].insn_code
3969 != CODE_FOR_nothing)
3970 ? OPTAB_DIRECT : OPTAB_WIDEN));
3974 /* No luck there. Try a quotient-and-remainder insn,
3975 keeping the quotient alone. */
3976 quotient = gen_reg_rtx (compute_mode);
3977 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
3979 quotient, NULL_RTX, unsignedp))
3983 /* Still no luck. If we are not computing the remainder,
3984 use a library call for the quotient. */
3985 quotient = sign_expand_binop (compute_mode,
3986 udiv_optab, sdiv_optab,
3988 unsignedp, OPTAB_LIB_WIDEN);
3995 if (target && GET_MODE (target) != compute_mode)
3999 /* No divide instruction either. Use library for remainder. */
4000 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4002 unsignedp, OPTAB_LIB_WIDEN);
4005 /* We divided. Now finish doing X - Y * (X / Y). */
4006 remainder = expand_mult (compute_mode, quotient, op1,
4007 NULL_RTX, unsignedp);
4008 remainder = expand_binop (compute_mode, sub_optab, op0,
4009 remainder, target, unsignedp,
4014 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4017 /* Return a tree node with data type TYPE, describing the value of X.
4018 Usually this is an RTL_EXPR, if there is no obvious better choice.
4019 X may be an expression, however we only support those expressions
4020 generated by loop.c. */
4029 switch (GET_CODE (x))
4032 t = build_int_2 (INTVAL (x),
4033 (TREE_UNSIGNED (type)
4034 && (GET_MODE_BITSIZE (TYPE_MODE (type)) < HOST_BITS_PER_WIDE_INT))
4035 || INTVAL (x) >= 0 ? 0 : -1);
4036 TREE_TYPE (t) = type;
4040 if (GET_MODE (x) == VOIDmode)
4042 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4043 TREE_TYPE (t) = type;
4049 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4050 t = build_real (type, d);
4061 units = CONST_VECTOR_NUNITS (x);
4063 /* Build a tree with vector elements. */
4064 for (i = units - 1; i >= 0; --i)
4066 elt = CONST_VECTOR_ELT (x, i);
4067 t = tree_cons (NULL_TREE, make_tree (type, elt), t);
4070 return build_vector (type, t);
4074 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4075 make_tree (type, XEXP (x, 1))));
4078 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4079 make_tree (type, XEXP (x, 1))));
4082 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
4085 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
4086 make_tree (type, XEXP (x, 1))));
4089 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
4090 make_tree (type, XEXP (x, 1))));
4093 return fold (convert (type,
4094 build (RSHIFT_EXPR, unsigned_type (type),
4095 make_tree (unsigned_type (type),
4097 make_tree (type, XEXP (x, 1)))));
4100 return fold (convert (type,
4101 build (RSHIFT_EXPR, signed_type (type),
4102 make_tree (signed_type (type), XEXP (x, 0)),
4103 make_tree (type, XEXP (x, 1)))));
4106 if (TREE_CODE (type) != REAL_TYPE)
4107 t = signed_type (type);
4111 return fold (convert (type,
4112 build (TRUNC_DIV_EXPR, t,
4113 make_tree (t, XEXP (x, 0)),
4114 make_tree (t, XEXP (x, 1)))));
4116 t = unsigned_type (type);
4117 return fold (convert (type,
4118 build (TRUNC_DIV_EXPR, t,
4119 make_tree (t, XEXP (x, 0)),
4120 make_tree (t, XEXP (x, 1)))));
4122 t = make_node (RTL_EXPR);
4123 TREE_TYPE (t) = type;
4125 #ifdef POINTERS_EXTEND_UNSIGNED
4126 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
4127 ptr_mode. So convert. */
4128 if (POINTER_TYPE_P (type) && GET_MODE (x) != TYPE_MODE (type))
4129 x = convert_memory_address (TYPE_MODE (type), x);
4132 RTL_EXPR_RTL (t) = x;
4133 /* There are no insns to be output
4134 when this rtl_expr is used. */
4135 RTL_EXPR_SEQUENCE (t) = 0;
4140 /* Return an rtx representing the value of X * MULT + ADD.
4141 TARGET is a suggestion for where to store the result (an rtx).
4142 MODE is the machine mode for the computation.
4143 X and MULT must have mode MODE. ADD may have a different mode.
4144 So can X (defaults to same as MODE).
4145 UNSIGNEDP is non-zero to do unsigned multiplication.
4146 This may emit insns. */
4149 expand_mult_add (x, target, mult, add, mode, unsignedp)
4150 rtx x, target, mult, add;
4151 enum machine_mode mode;
4154 tree type = type_for_mode (mode, unsignedp);
4155 tree add_type = (GET_MODE (add) == VOIDmode
4156 ? type : type_for_mode (GET_MODE (add), unsignedp));
4157 tree result = fold (build (PLUS_EXPR, type,
4158 fold (build (MULT_EXPR, type,
4159 make_tree (type, x),
4160 make_tree (type, mult))),
4161 make_tree (add_type, add)));
4163 return expand_expr (result, target, VOIDmode, 0);
4166 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4167 and returning TARGET.
4169 If TARGET is 0, a pseudo-register or constant is returned. */
4172 expand_and (mode, op0, op1, target)
4173 enum machine_mode mode;
4174 rtx op0, op1, target;
4178 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
4179 tem = simplify_binary_operation (AND, mode, op0, op1);
4181 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4185 else if (tem != target)
4186 emit_move_insn (target, tem);
4190 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4191 and storing in TARGET. Normally return TARGET.
4192 Return 0 if that cannot be done.
4194 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
4195 it is VOIDmode, they cannot both be CONST_INT.
4197 UNSIGNEDP is for the case where we have to widen the operands
4198 to perform the operation. It says to use zero-extension.
4200 NORMALIZEP is 1 if we should convert the result to be either zero
4201 or one. Normalize is -1 if we should convert the result to be
4202 either zero or -1. If NORMALIZEP is zero, the result will be left
4203 "raw" out of the scc insn. */
4206 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
4210 enum machine_mode mode;
4215 enum insn_code icode;
4216 enum machine_mode compare_mode;
4217 enum machine_mode target_mode = GET_MODE (target);
4219 rtx last = get_last_insn ();
4220 rtx pattern, comparison;
4222 /* ??? Ok to do this and then fail? */
4223 op0 = protect_from_queue (op0, 0);
4224 op1 = protect_from_queue (op1, 0);
4227 code = unsigned_condition (code);
4229 /* If one operand is constant, make it the second one. Only do this
4230 if the other operand is not constant as well. */
4232 if (swap_commutative_operands_p (op0, op1))
4237 code = swap_condition (code);
4240 if (mode == VOIDmode)
4241 mode = GET_MODE (op0);
4243 /* For some comparisons with 1 and -1, we can convert this to
4244 comparisons with zero. This will often produce more opportunities for
4245 store-flag insns. */
4250 if (op1 == const1_rtx)
4251 op1 = const0_rtx, code = LE;
4254 if (op1 == constm1_rtx)
4255 op1 = const0_rtx, code = LT;
4258 if (op1 == const1_rtx)
4259 op1 = const0_rtx, code = GT;
4262 if (op1 == constm1_rtx)
4263 op1 = const0_rtx, code = GE;
4266 if (op1 == const1_rtx)
4267 op1 = const0_rtx, code = NE;
4270 if (op1 == const1_rtx)
4271 op1 = const0_rtx, code = EQ;
4277 /* If we are comparing a double-word integer with zero, we can convert
4278 the comparison into one involving a single word. */
4279 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
4280 && GET_MODE_CLASS (mode) == MODE_INT
4281 && op1 == const0_rtx)
4283 if (code == EQ || code == NE)
4285 /* Do a logical OR of the two words and compare the result. */
4286 rtx op0h = gen_highpart (word_mode, op0);
4287 rtx op0l = gen_lowpart (word_mode, op0);
4288 rtx op0both = expand_binop (word_mode, ior_optab, op0h, op0l,
4289 NULL_RTX, unsignedp, OPTAB_DIRECT);
4291 return emit_store_flag (target, code, op0both, op1, word_mode,
4292 unsignedp, normalizep);
4294 else if (code == LT || code == GE)
4295 /* If testing the sign bit, can just test on high word. */
4296 return emit_store_flag (target, code, gen_highpart (word_mode, op0),
4297 op1, word_mode, unsignedp, normalizep);
4300 /* From now on, we won't change CODE, so set ICODE now. */
4301 icode = setcc_gen_code[(int) code];
4303 /* If this is A < 0 or A >= 0, we can do this by taking the ones
4304 complement of A (for GE) and shifting the sign bit to the low bit. */
4305 if (op1 == const0_rtx && (code == LT || code == GE)
4306 && GET_MODE_CLASS (mode) == MODE_INT
4307 && (normalizep || STORE_FLAG_VALUE == 1
4308 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4309 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4310 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4314 /* If the result is to be wider than OP0, it is best to convert it
4315 first. If it is to be narrower, it is *incorrect* to convert it
4317 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4319 op0 = protect_from_queue (op0, 0);
4320 op0 = convert_modes (target_mode, mode, op0, 0);
4324 if (target_mode != mode)
4328 op0 = expand_unop (mode, one_cmpl_optab, op0,
4329 ((STORE_FLAG_VALUE == 1 || normalizep)
4330 ? 0 : subtarget), 0);
4332 if (STORE_FLAG_VALUE == 1 || normalizep)
4333 /* If we are supposed to produce a 0/1 value, we want to do
4334 a logical shift from the sign bit to the low-order bit; for
4335 a -1/0 value, we do an arithmetic shift. */
4336 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4337 size_int (GET_MODE_BITSIZE (mode) - 1),
4338 subtarget, normalizep != -1);
4340 if (mode != target_mode)
4341 op0 = convert_modes (target_mode, mode, op0, 0);
4346 if (icode != CODE_FOR_nothing)
4348 insn_operand_predicate_fn pred;
4350 /* We think we may be able to do this with a scc insn. Emit the
4351 comparison and then the scc insn.
4353 compare_from_rtx may call emit_queue, which would be deleted below
4354 if the scc insn fails. So call it ourselves before setting LAST.
4355 Likewise for do_pending_stack_adjust. */
4358 do_pending_stack_adjust ();
4359 last = get_last_insn ();
4362 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX);
4363 if (GET_CODE (comparison) == CONST_INT)
4364 return (comparison == const0_rtx ? const0_rtx
4365 : normalizep == 1 ? const1_rtx
4366 : normalizep == -1 ? constm1_rtx
4369 /* The code of COMPARISON may not match CODE if compare_from_rtx
4370 decided to swap its operands and reverse the original code.
4372 We know that compare_from_rtx returns either a CONST_INT or
4373 a new comparison code, so it is safe to just extract the
4374 code from COMPARISON. */
4375 code = GET_CODE (comparison);
4377 /* Get a reference to the target in the proper mode for this insn. */
4378 compare_mode = insn_data[(int) icode].operand[0].mode;
4380 pred = insn_data[(int) icode].operand[0].predicate;
4381 if (preserve_subexpressions_p ()
4382 || ! (*pred) (subtarget, compare_mode))
4383 subtarget = gen_reg_rtx (compare_mode);
4385 pattern = GEN_FCN (icode) (subtarget);
4388 emit_insn (pattern);
4390 /* If we are converting to a wider mode, first convert to
4391 TARGET_MODE, then normalize. This produces better combining
4392 opportunities on machines that have a SIGN_EXTRACT when we are
4393 testing a single bit. This mostly benefits the 68k.
4395 If STORE_FLAG_VALUE does not have the sign bit set when
4396 interpreted in COMPARE_MODE, we can do this conversion as
4397 unsigned, which is usually more efficient. */
4398 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4400 convert_move (target, subtarget,
4401 (GET_MODE_BITSIZE (compare_mode)
4402 <= HOST_BITS_PER_WIDE_INT)
4403 && 0 == (STORE_FLAG_VALUE
4404 & ((HOST_WIDE_INT) 1
4405 << (GET_MODE_BITSIZE (compare_mode) -1))));
4407 compare_mode = target_mode;
4412 /* If we want to keep subexpressions around, don't reuse our
4415 if (preserve_subexpressions_p ())
4418 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
4419 we don't have to do anything. */
4420 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4422 /* STORE_FLAG_VALUE might be the most negative number, so write
4423 the comparison this way to avoid a compiler-time warning. */
4424 else if (- normalizep == STORE_FLAG_VALUE)
4425 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4427 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4428 makes it hard to use a value of just the sign bit due to
4429 ANSI integer constant typing rules. */
4430 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4431 && (STORE_FLAG_VALUE
4432 & ((HOST_WIDE_INT) 1
4433 << (GET_MODE_BITSIZE (compare_mode) - 1))))
4434 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4435 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4436 subtarget, normalizep == 1);
4437 else if (STORE_FLAG_VALUE & 1)
4439 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget);
4440 if (normalizep == -1)
4441 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4446 /* If we were converting to a smaller mode, do the
4448 if (target_mode != compare_mode)
4450 convert_move (target, op0, 0);
4458 delete_insns_since (last);
4460 /* If expensive optimizations, use different pseudo registers for each
4461 insn, instead of reusing the same pseudo. This leads to better CSE,
4462 but slows down the compiler, since there are more pseudos */
4463 subtarget = (!flag_expensive_optimizations
4464 && (target_mode == mode)) ? target : NULL_RTX;
4466 /* If we reached here, we can't do this with a scc insn. However, there
4467 are some comparisons that can be done directly. For example, if
4468 this is an equality comparison of integers, we can try to exclusive-or
4469 (or subtract) the two operands and use a recursive call to try the
4470 comparison with zero. Don't do any of these cases if branches are
4474 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4475 && op1 != const0_rtx)
4477 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4481 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4484 tem = emit_store_flag (target, code, tem, const0_rtx,
4485 mode, unsignedp, normalizep);
4487 delete_insns_since (last);
4491 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4492 the constant zero. Reject all other comparisons at this point. Only
4493 do LE and GT if branches are expensive since they are expensive on
4494 2-operand machines. */
4496 if (BRANCH_COST == 0
4497 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4498 || (code != EQ && code != NE
4499 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4502 /* See what we need to return. We can only return a 1, -1, or the
4505 if (normalizep == 0)
4507 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4508 normalizep = STORE_FLAG_VALUE;
4510 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4511 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4512 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4518 /* Try to put the result of the comparison in the sign bit. Assume we can't
4519 do the necessary operation below. */
4523 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4524 the sign bit set. */
4528 /* This is destructive, so SUBTARGET can't be OP0. */
4529 if (rtx_equal_p (subtarget, op0))
4532 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4535 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4539 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4540 number of bits in the mode of OP0, minus one. */
4544 if (rtx_equal_p (subtarget, op0))
4547 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4548 size_int (GET_MODE_BITSIZE (mode) - 1),
4550 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4554 if (code == EQ || code == NE)
4556 /* For EQ or NE, one way to do the comparison is to apply an operation
4557 that converts the operand into a positive number if it is non-zero
4558 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4559 for NE we negate. This puts the result in the sign bit. Then we
4560 normalize with a shift, if needed.
4562 Two operations that can do the above actions are ABS and FFS, so try
4563 them. If that doesn't work, and MODE is smaller than a full word,
4564 we can use zero-extension to the wider mode (an unsigned conversion)
4565 as the operation. */
4567 /* Note that ABS doesn't yield a positive number for INT_MIN, but
4568 that is compensated by the subsequent overflow when subtracting
4571 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4572 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4573 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4574 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4575 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4577 op0 = protect_from_queue (op0, 0);
4578 tem = convert_modes (word_mode, mode, op0, 1);
4585 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4588 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4591 /* If we couldn't do it that way, for NE we can "or" the two's complement
4592 of the value with itself. For EQ, we take the one's complement of
4593 that "or", which is an extra insn, so we only handle EQ if branches
4596 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4598 if (rtx_equal_p (subtarget, op0))
4601 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4602 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4605 if (tem && code == EQ)
4606 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4610 if (tem && normalizep)
4611 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4612 size_int (GET_MODE_BITSIZE (mode) - 1),
4613 subtarget, normalizep == 1);
4617 if (GET_MODE (tem) != target_mode)
4619 convert_move (target, tem, 0);
4622 else if (!subtarget)
4624 emit_move_insn (target, tem);
4629 delete_insns_since (last);
4634 /* Like emit_store_flag, but always succeeds. */
4637 emit_store_flag_force (target, code, op0, op1, mode, unsignedp, normalizep)
4641 enum machine_mode mode;
4647 /* First see if emit_store_flag can do the job. */
4648 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4652 if (normalizep == 0)
4655 /* If this failed, we have to do this with set/compare/jump/set code. */
4657 if (GET_CODE (target) != REG
4658 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4659 target = gen_reg_rtx (GET_MODE (target));
4661 emit_move_insn (target, const1_rtx);
4662 label = gen_label_rtx ();
4663 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
4666 emit_move_insn (target, const0_rtx);
4672 /* Perform possibly multi-word comparison and conditional jump to LABEL
4673 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4675 The algorithm is based on the code in expr.c:do_jump.
4677 Note that this does not perform a general comparison. Only variants
4678 generated within expmed.c are correctly handled, others abort (but could
4679 be handled if needed). */
4682 do_cmp_and_jump (arg1, arg2, op, mode, label)
4683 rtx arg1, arg2, label;
4685 enum machine_mode mode;
4687 /* If this mode is an integer too wide to compare properly,
4688 compare word by word. Rely on cse to optimize constant cases. */
4690 if (GET_MODE_CLASS (mode) == MODE_INT
4691 && ! can_compare_p (op, mode, ccp_jump))
4693 rtx label2 = gen_label_rtx ();
4698 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4702 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4706 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4710 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4714 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4717 /* do_jump_by_parts_equality_rtx compares with zero. Luckily
4718 that's the only equality operations we do */
4720 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4722 do_jump_by_parts_equality_rtx (arg1, label2, label);
4726 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4728 do_jump_by_parts_equality_rtx (arg1, label, label2);
4735 emit_label (label2);
4738 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);