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"
36 #include "langhooks.h"
38 static void store_fixed_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
39 unsigned HOST_WIDE_INT,
40 unsigned HOST_WIDE_INT, rtx));
41 static void store_split_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
42 unsigned HOST_WIDE_INT, rtx));
43 static rtx extract_fixed_bit_field PARAMS ((enum machine_mode, rtx,
44 unsigned HOST_WIDE_INT,
45 unsigned HOST_WIDE_INT,
46 unsigned HOST_WIDE_INT,
48 static rtx mask_rtx PARAMS ((enum machine_mode, int,
50 static rtx lshift_value PARAMS ((enum machine_mode, rtx,
52 static rtx extract_split_bit_field PARAMS ((rtx, unsigned HOST_WIDE_INT,
53 unsigned HOST_WIDE_INT, int));
54 static void do_cmp_and_jump PARAMS ((rtx, rtx, enum rtx_code,
55 enum machine_mode, rtx));
57 /* Nonzero means divides or modulus operations are relatively cheap for
58 powers of two, so don't use branches; emit the operation instead.
59 Usually, this will mean that the MD file will emit non-branch
62 static int sdiv_pow2_cheap, smod_pow2_cheap;
64 #ifndef SLOW_UNALIGNED_ACCESS
65 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
68 /* For compilers that support multiple targets with different word sizes,
69 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example
70 is the H8/300(H) compiler. */
72 #ifndef MAX_BITS_PER_WORD
73 #define MAX_BITS_PER_WORD BITS_PER_WORD
76 /* Reduce conditional compilation elsewhere. */
79 #define CODE_FOR_insv CODE_FOR_nothing
80 #define gen_insv(a,b,c,d) NULL_RTX
84 #define CODE_FOR_extv CODE_FOR_nothing
85 #define gen_extv(a,b,c,d) NULL_RTX
89 #define CODE_FOR_extzv CODE_FOR_nothing
90 #define gen_extzv(a,b,c,d) NULL_RTX
93 /* Cost of various pieces of RTL. Note that some of these are indexed by
94 shift count and some by mode. */
95 static int add_cost, negate_cost, zero_cost;
96 static int shift_cost[MAX_BITS_PER_WORD];
97 static int shiftadd_cost[MAX_BITS_PER_WORD];
98 static int shiftsub_cost[MAX_BITS_PER_WORD];
99 static int mul_cost[NUM_MACHINE_MODES];
100 static int div_cost[NUM_MACHINE_MODES];
101 static int mul_widen_cost[NUM_MACHINE_MODES];
102 static int mul_highpart_cost[NUM_MACHINE_MODES];
107 rtx reg, shift_insn, shiftadd_insn, shiftsub_insn;
110 enum machine_mode mode, wider_mode;
114 /* This is "some random pseudo register" for purposes of calling recog
115 to see what insns exist. */
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 rtx c_int = GEN_INT ((HOST_WIDE_INT) 1 << m);
147 shift_cost[m] = shiftadd_cost[m] = shiftsub_cost[m] = 32000;
149 XEXP (SET_SRC (PATTERN (shift_insn)), 1) = GEN_INT (m);
150 if (recog (PATTERN (shift_insn), shift_insn, &dummy) >= 0)
151 shift_cost[m] = rtx_cost (SET_SRC (PATTERN (shift_insn)), SET);
153 XEXP (XEXP (SET_SRC (PATTERN (shiftadd_insn)), 0), 1) = c_int;
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) = c_int;
158 if (recog (PATTERN (shiftsub_insn), shiftsub_insn, &dummy) >= 0)
159 shiftsub_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftsub_insn)), SET);
162 negate_cost = rtx_cost (gen_rtx_NEG (word_mode, reg), SET);
165 = (rtx_cost (gen_rtx_DIV (word_mode, reg, GEN_INT (32)), SET)
168 = (rtx_cost (gen_rtx_MOD (word_mode, reg, GEN_INT (32)), SET)
171 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
173 mode = GET_MODE_WIDER_MODE (mode))
175 reg = gen_rtx_REG (mode, 10000);
176 div_cost[(int) mode] = rtx_cost (gen_rtx_UDIV (mode, reg, reg), SET);
177 mul_cost[(int) mode] = rtx_cost (gen_rtx_MULT (mode, reg, reg), SET);
178 wider_mode = GET_MODE_WIDER_MODE (mode);
179 if (wider_mode != VOIDmode)
181 mul_widen_cost[(int) wider_mode]
182 = rtx_cost (gen_rtx_MULT (wider_mode,
183 gen_rtx_ZERO_EXTEND (wider_mode, reg),
184 gen_rtx_ZERO_EXTEND (wider_mode, reg)),
186 mul_highpart_cost[(int) mode]
187 = rtx_cost (gen_rtx_TRUNCATE
189 gen_rtx_LSHIFTRT (wider_mode,
190 gen_rtx_MULT (wider_mode,
195 GEN_INT (GET_MODE_BITSIZE (mode)))),
203 /* Return an rtx representing minus the value of X.
204 MODE is the intended mode of the result,
205 useful if X is a CONST_INT. */
209 enum machine_mode mode;
212 rtx result = simplify_unary_operation (NEG, mode, x, mode);
215 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
220 /* Report on the availability of insv/extv/extzv and the desired mode
221 of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo
222 is false; else the mode of the specified operand. If OPNO is -1,
223 all the caller cares about is whether the insn is available. */
225 mode_for_extraction (pattern, opno)
226 enum extraction_pattern pattern;
229 const struct insn_data *data;
236 data = &insn_data[CODE_FOR_insv];
239 return MAX_MACHINE_MODE;
244 data = &insn_data[CODE_FOR_extv];
247 return MAX_MACHINE_MODE;
252 data = &insn_data[CODE_FOR_extzv];
255 return MAX_MACHINE_MODE;
264 /* Everyone who uses this function used to follow it with
265 if (result == VOIDmode) result = word_mode; */
266 if (data->operand[opno].mode == VOIDmode)
268 return data->operand[opno].mode;
272 /* Generate code to store value from rtx VALUE
273 into a bit-field within structure STR_RTX
274 containing BITSIZE bits starting at bit BITNUM.
275 FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
276 ALIGN is the alignment that STR_RTX is known to have.
277 TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */
279 /* ??? Note that there are two different ideas here for how
280 to determine the size to count bits within, for a register.
281 One is BITS_PER_WORD, and the other is the size of operand 3
284 If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD
285 else, we use the mode of operand 3. */
288 store_bit_field (str_rtx, bitsize, bitnum, fieldmode, value, total_size)
290 unsigned HOST_WIDE_INT bitsize;
291 unsigned HOST_WIDE_INT bitnum;
292 enum machine_mode fieldmode;
294 HOST_WIDE_INT total_size;
297 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
298 unsigned HOST_WIDE_INT offset = bitnum / unit;
299 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
303 enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
305 /* Discount the part of the structure before the desired byte.
306 We need to know how many bytes are safe to reference after it. */
308 total_size -= (bitpos / BIGGEST_ALIGNMENT
309 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
311 while (GET_CODE (op0) == SUBREG)
313 /* The following line once was done only if WORDS_BIG_ENDIAN,
314 but I think that is a mistake. WORDS_BIG_ENDIAN is
315 meaningful at a much higher level; when structures are copied
316 between memory and regs, the higher-numbered regs
317 always get higher addresses. */
318 offset += (SUBREG_BYTE (op0) / UNITS_PER_WORD);
319 /* We used to adjust BITPOS here, but now we do the whole adjustment
320 right after the loop. */
321 op0 = SUBREG_REG (op0);
324 value = protect_from_queue (value, 0);
328 int old_generating_concat_p = generating_concat_p;
329 generating_concat_p = 0;
330 value = force_not_mem (value);
331 generating_concat_p = old_generating_concat_p;
334 /* If the target is a register, overwriting the entire object, or storing
335 a full-word or multi-word field can be done with just a SUBREG.
337 If the target is memory, storing any naturally aligned field can be
338 done with a simple store. For targets that support fast unaligned
339 memory, any naturally sized, unit aligned field can be done directly. */
341 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
342 + (offset * UNITS_PER_WORD);
345 && bitsize == GET_MODE_BITSIZE (fieldmode)
346 && (GET_CODE (op0) != MEM
347 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
348 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
349 && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
350 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
351 || (offset * BITS_PER_UNIT % bitsize == 0
352 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
354 if (GET_MODE (op0) != fieldmode)
356 if (GET_CODE (op0) == SUBREG)
358 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
359 || GET_MODE_CLASS (fieldmode) == MODE_INT
360 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
361 op0 = SUBREG_REG (op0);
363 /* Else we've got some float mode source being extracted into
364 a different float mode destination -- this combination of
365 subregs results in Severe Tire Damage. */
368 if (GET_CODE (op0) == REG)
369 op0 = gen_rtx_SUBREG (fieldmode, op0, byte_offset);
371 op0 = adjust_address (op0, fieldmode, offset);
373 emit_move_insn (op0, value);
377 /* Make sure we are playing with integral modes. Pun with subregs
378 if we aren't. This must come after the entire register case above,
379 since that case is valid for any mode. The following cases are only
380 valid for integral modes. */
382 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
383 if (imode != GET_MODE (op0))
385 if (GET_CODE (op0) == MEM)
386 op0 = adjust_address (op0, imode, 0);
387 else if (imode != BLKmode)
388 op0 = gen_lowpart (imode, op0);
394 /* We may be accessing data outside the field, which means
395 we can alias adjacent data. */
396 if (GET_CODE (op0) == MEM)
398 op0 = shallow_copy_rtx (op0);
399 set_mem_alias_set (op0, 0);
400 set_mem_expr (op0, 0);
403 /* If OP0 is a register, BITPOS must count within a word.
404 But as we have it, it counts within whatever size OP0 now has.
405 On a bigendian machine, these are not the same, so convert. */
407 && !FUNCTION_ARG_REG_LITTLE_ENDIAN
408 && GET_CODE (op0) != MEM
409 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
410 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
412 /* Storing an lsb-aligned field in a register
413 can be done with a movestrict instruction. */
415 if (GET_CODE (op0) != MEM
416 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
417 && bitsize == GET_MODE_BITSIZE (fieldmode)
418 && (movstrict_optab->handlers[(int) fieldmode].insn_code
419 != CODE_FOR_nothing))
421 int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
423 /* Get appropriate low part of the value being stored. */
424 if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
425 value = gen_lowpart (fieldmode, value);
426 else if (!(GET_CODE (value) == SYMBOL_REF
427 || GET_CODE (value) == LABEL_REF
428 || GET_CODE (value) == CONST))
429 value = convert_to_mode (fieldmode, value, 0);
431 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
432 value = copy_to_mode_reg (fieldmode, value);
434 if (GET_CODE (op0) == SUBREG)
436 if (GET_MODE (SUBREG_REG (op0)) == fieldmode
437 || GET_MODE_CLASS (fieldmode) == MODE_INT
438 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT)
439 op0 = SUBREG_REG (op0);
441 /* Else we've got some float mode source being extracted into
442 a different float mode destination -- this combination of
443 subregs results in Severe Tire Damage. */
447 emit_insn (GEN_FCN (icode)
448 (gen_rtx_SUBREG (fieldmode, op0,
449 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
450 + (offset * UNITS_PER_WORD)),
456 /* Handle fields bigger than a word. */
458 if (bitsize > BITS_PER_WORD)
460 /* Here we transfer the words of the field
461 in the order least significant first.
462 This is because the most significant word is the one which may
464 However, only do that if the value is not BLKmode. */
466 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
467 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
470 /* This is the mode we must force value to, so that there will be enough
471 subwords to extract. Note that fieldmode will often (always?) be
472 VOIDmode, because that is what store_field uses to indicate that this
473 is a bit field, but passing VOIDmode to operand_subword_force will
474 result in an abort. */
475 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
477 for (i = 0; i < nwords; i++)
479 /* If I is 0, use the low-order word in both field and target;
480 if I is 1, use the next to lowest word; and so on. */
481 unsigned int wordnum = (backwards ? nwords - i - 1 : i);
482 unsigned int bit_offset = (backwards
483 ? MAX ((int) bitsize - ((int) i + 1)
486 : (int) i * BITS_PER_WORD);
488 store_bit_field (op0, MIN (BITS_PER_WORD,
489 bitsize - i * BITS_PER_WORD),
490 bitnum + bit_offset, word_mode,
491 operand_subword_force (value, wordnum,
492 (GET_MODE (value) == VOIDmode
494 : GET_MODE (value))),
500 /* From here on we can assume that the field to be stored in is
501 a full-word (whatever type that is), since it is shorter than a word. */
503 /* OFFSET is the number of words or bytes (UNIT says which)
504 from STR_RTX to the first word or byte containing part of the field. */
506 if (GET_CODE (op0) != MEM)
509 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
511 if (GET_CODE (op0) != REG)
513 /* Since this is a destination (lvalue), we can't copy it to a
514 pseudo. We can trivially remove a SUBREG that does not
515 change the size of the operand. Such a SUBREG may have been
516 added above. Otherwise, abort. */
517 if (GET_CODE (op0) == SUBREG
518 && (GET_MODE_SIZE (GET_MODE (op0))
519 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))))
520 op0 = SUBREG_REG (op0);
524 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
525 op0, (offset * UNITS_PER_WORD));
530 op0 = protect_from_queue (op0, 1);
532 /* If VALUE is a floating-point mode, access it as an integer of the
533 corresponding size. This can occur on a machine with 64 bit registers
534 that uses SFmode for float. This can also occur for unaligned float
536 if (GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
537 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
538 value = gen_lowpart ((GET_MODE (value) == VOIDmode
539 ? word_mode : int_mode_for_mode (GET_MODE (value))),
542 /* Now OFFSET is nonzero only if OP0 is memory
543 and is therefore always measured in bytes. */
546 && GET_MODE (value) != BLKmode
547 && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
548 /* Ensure insv's size is wide enough for this field. */
549 && (GET_MODE_BITSIZE (op_mode) >= bitsize)
550 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
551 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))))
553 int xbitpos = bitpos;
556 rtx last = get_last_insn ();
558 enum machine_mode maxmode = mode_for_extraction (EP_insv, 3);
559 int save_volatile_ok = volatile_ok;
563 /* If this machine's insv can only insert into a register, copy OP0
564 into a register and save it back later. */
565 /* This used to check flag_force_mem, but that was a serious
566 de-optimization now that flag_force_mem is enabled by -O2. */
567 if (GET_CODE (op0) == MEM
568 && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate)
572 enum machine_mode bestmode;
574 /* Get the mode to use for inserting into this field. If OP0 is
575 BLKmode, get the smallest mode consistent with the alignment. If
576 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
577 mode. Otherwise, use the smallest mode containing the field. */
579 if (GET_MODE (op0) == BLKmode
580 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
582 = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode,
583 MEM_VOLATILE_P (op0));
585 bestmode = GET_MODE (op0);
587 if (bestmode == VOIDmode
588 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
589 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
592 /* Adjust address to point to the containing unit of that mode.
593 Compute offset as multiple of this unit, counting in bytes. */
594 unit = GET_MODE_BITSIZE (bestmode);
595 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
596 bitpos = bitnum % unit;
597 op0 = adjust_address (op0, bestmode, offset);
599 /* Fetch that unit, store the bitfield in it, then store
601 tempreg = copy_to_reg (op0);
602 store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
604 emit_move_insn (op0, tempreg);
607 volatile_ok = save_volatile_ok;
609 /* Add OFFSET into OP0's address. */
610 if (GET_CODE (xop0) == MEM)
611 xop0 = adjust_address (xop0, byte_mode, offset);
613 /* If xop0 is a register, we need it in MAXMODE
614 to make it acceptable to the format of insv. */
615 if (GET_CODE (xop0) == SUBREG)
616 /* We can't just change the mode, because this might clobber op0,
617 and we will need the original value of op0 if insv fails. */
618 xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
619 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
620 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
622 /* On big-endian machines, we count bits from the most significant.
623 If the bit field insn does not, we must invert. */
625 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
626 xbitpos = unit - bitsize - xbitpos;
628 /* We have been counting XBITPOS within UNIT.
629 Count instead within the size of the register. */
630 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
631 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
633 unit = GET_MODE_BITSIZE (maxmode);
635 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */
637 if (GET_MODE (value) != maxmode)
639 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
641 /* Optimization: Don't bother really extending VALUE
642 if it has all the bits we will actually use. However,
643 if we must narrow it, be sure we do it correctly. */
645 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
649 tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0);
651 tmp = simplify_gen_subreg (maxmode,
652 force_reg (GET_MODE (value),
654 GET_MODE (value), 0);
658 value1 = gen_lowpart (maxmode, value1);
660 else if (GET_CODE (value) == CONST_INT)
661 value1 = gen_int_mode (INTVAL (value), maxmode);
662 else if (!CONSTANT_P (value))
663 /* Parse phase is supposed to make VALUE's data type
664 match that of the component reference, which is a type
665 at least as wide as the field; so VALUE should have
666 a mode that corresponds to that type. */
670 /* If this machine's insv insists on a register,
671 get VALUE1 into a register. */
672 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
674 value1 = force_reg (maxmode, value1);
676 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
681 delete_insns_since (last);
682 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
687 /* Insv is not available; store using shifts and boolean ops. */
688 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
692 /* Use shifts and boolean operations to store VALUE
693 into a bit field of width BITSIZE
694 in a memory location specified by OP0 except offset by OFFSET bytes.
695 (OFFSET must be 0 if OP0 is a register.)
696 The field starts at position BITPOS within the byte.
697 (If OP0 is a register, it may be a full word or a narrower mode,
698 but BITPOS still counts within a full word,
699 which is significant on bigendian machines.)
701 Note that protect_from_queue has already been done on OP0 and VALUE. */
704 store_fixed_bit_field (op0, offset, bitsize, bitpos, value)
706 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
709 enum machine_mode mode;
710 unsigned int total_bits = BITS_PER_WORD;
715 /* There is a case not handled here:
716 a structure with a known alignment of just a halfword
717 and a field split across two aligned halfwords within the structure.
718 Or likewise a structure with a known alignment of just a byte
719 and a field split across two bytes.
720 Such cases are not supposed to be able to occur. */
722 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
726 /* Special treatment for a bit field split across two registers. */
727 if (bitsize + bitpos > BITS_PER_WORD)
729 store_split_bit_field (op0, bitsize, bitpos, value);
735 /* Get the proper mode to use for this field. We want a mode that
736 includes the entire field. If such a mode would be larger than
737 a word, we won't be doing the extraction the normal way.
738 We don't want a mode bigger than the destination. */
740 mode = GET_MODE (op0);
741 if (GET_MODE_BITSIZE (mode) == 0
742 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
744 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
745 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
747 if (mode == VOIDmode)
749 /* The only way this should occur is if the field spans word
751 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
756 total_bits = GET_MODE_BITSIZE (mode);
758 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
759 be in the range 0 to total_bits-1, and put any excess bytes in
761 if (bitpos >= total_bits)
763 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
764 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
768 /* Get ref to an aligned byte, halfword, or word containing the field.
769 Adjust BITPOS to be position within a word,
770 and OFFSET to be the offset of that word.
771 Then alter OP0 to refer to that word. */
772 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
773 offset -= (offset % (total_bits / BITS_PER_UNIT));
774 op0 = adjust_address (op0, mode, offset);
777 mode = GET_MODE (op0);
779 /* Now MODE is either some integral mode for a MEM as OP0,
780 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
781 The bit field is contained entirely within OP0.
782 BITPOS is the starting bit number within OP0.
783 (OP0's mode may actually be narrower than MODE.) */
785 if (BYTES_BIG_ENDIAN)
786 /* BITPOS is the distance between our msb
787 and that of the containing datum.
788 Convert it to the distance from the lsb. */
789 bitpos = total_bits - bitsize - bitpos;
791 /* Now BITPOS is always the distance between our lsb
794 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
795 we must first convert its mode to MODE. */
797 if (GET_CODE (value) == CONST_INT)
799 HOST_WIDE_INT v = INTVAL (value);
801 if (bitsize < HOST_BITS_PER_WIDE_INT)
802 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
806 else if ((bitsize < HOST_BITS_PER_WIDE_INT
807 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
808 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
811 value = lshift_value (mode, value, bitpos, bitsize);
815 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
816 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
818 if (GET_MODE (value) != mode)
820 if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
821 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
822 value = gen_lowpart (mode, value);
824 value = convert_to_mode (mode, value, 1);
828 value = expand_binop (mode, and_optab, value,
829 mask_rtx (mode, 0, bitsize, 0),
830 NULL_RTX, 1, OPTAB_LIB_WIDEN);
832 value = expand_shift (LSHIFT_EXPR, mode, value,
833 build_int_2 (bitpos, 0), NULL_RTX, 1);
836 /* Now clear the chosen bits in OP0,
837 except that if VALUE is -1 we need not bother. */
839 subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
843 temp = expand_binop (mode, and_optab, op0,
844 mask_rtx (mode, bitpos, bitsize, 1),
845 subtarget, 1, OPTAB_LIB_WIDEN);
851 /* Now logical-or VALUE into OP0, unless it is zero. */
854 temp = expand_binop (mode, ior_optab, temp, value,
855 subtarget, 1, OPTAB_LIB_WIDEN);
857 emit_move_insn (op0, temp);
860 /* Store a bit field that is split across multiple accessible memory objects.
862 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
863 BITSIZE is the field width; BITPOS the position of its first bit
865 VALUE is the value to store.
867 This does not yet handle fields wider than BITS_PER_WORD. */
870 store_split_bit_field (op0, bitsize, bitpos, value)
872 unsigned HOST_WIDE_INT bitsize, bitpos;
876 unsigned int bitsdone = 0;
878 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
880 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
881 unit = BITS_PER_WORD;
883 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
885 /* If VALUE is a constant other than a CONST_INT, get it into a register in
886 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
887 that VALUE might be a floating-point constant. */
888 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
890 rtx word = gen_lowpart_common (word_mode, value);
892 if (word && (value != word))
895 value = gen_lowpart_common (word_mode,
896 force_reg (GET_MODE (value) != VOIDmode
898 : word_mode, value));
900 else if (GET_CODE (value) == ADDRESSOF)
901 value = copy_to_reg (value);
903 while (bitsdone < bitsize)
905 unsigned HOST_WIDE_INT thissize;
907 unsigned HOST_WIDE_INT thispos;
908 unsigned HOST_WIDE_INT offset;
910 offset = (bitpos + bitsdone) / unit;
911 thispos = (bitpos + bitsdone) % unit;
913 /* THISSIZE must not overrun a word boundary. Otherwise,
914 store_fixed_bit_field will call us again, and we will mutually
916 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
917 thissize = MIN (thissize, unit - thispos);
919 if (BYTES_BIG_ENDIAN)
923 /* We must do an endian conversion exactly the same way as it is
924 done in extract_bit_field, so that the two calls to
925 extract_fixed_bit_field will have comparable arguments. */
926 if (GET_CODE (value) != MEM || GET_MODE (value) == BLKmode)
927 total_bits = BITS_PER_WORD;
929 total_bits = GET_MODE_BITSIZE (GET_MODE (value));
931 /* Fetch successively less significant portions. */
932 if (GET_CODE (value) == CONST_INT)
933 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
934 >> (bitsize - bitsdone - thissize))
935 & (((HOST_WIDE_INT) 1 << thissize) - 1));
937 /* The args are chosen so that the last part includes the
938 lsb. Give extract_bit_field the value it needs (with
939 endianness compensation) to fetch the piece we want. */
940 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
941 total_bits - bitsize + bitsdone,
946 /* Fetch successively more significant portions. */
947 if (GET_CODE (value) == CONST_INT)
948 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
950 & (((HOST_WIDE_INT) 1 << thissize) - 1));
952 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
953 bitsdone, NULL_RTX, 1);
956 /* If OP0 is a register, then handle OFFSET here.
958 When handling multiword bitfields, extract_bit_field may pass
959 down a word_mode SUBREG of a larger REG for a bitfield that actually
960 crosses a word boundary. Thus, for a SUBREG, we must find
961 the current word starting from the base register. */
962 if (GET_CODE (op0) == SUBREG)
964 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
965 word = operand_subword_force (SUBREG_REG (op0), word_offset,
966 GET_MODE (SUBREG_REG (op0)));
969 else if (GET_CODE (op0) == REG)
971 word = operand_subword_force (op0, offset, GET_MODE (op0));
977 /* OFFSET is in UNITs, and UNIT is in bits.
978 store_fixed_bit_field wants offset in bytes. */
979 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
981 bitsdone += thissize;
985 /* Generate code to extract a byte-field from STR_RTX
986 containing BITSIZE bits, starting at BITNUM,
987 and put it in TARGET if possible (if TARGET is nonzero).
988 Regardless of TARGET, we return the rtx for where the value is placed.
991 STR_RTX is the structure containing the byte (a REG or MEM).
992 UNSIGNEDP is nonzero if this is an unsigned bit field.
993 MODE is the natural mode of the field value once extracted.
994 TMODE is the mode the caller would like the value to have;
995 but the value may be returned with type MODE instead.
997 TOTAL_SIZE is the size in bytes of the containing structure,
1000 If a TARGET is specified and we can store in it at no extra cost,
1001 we do so, and return TARGET.
1002 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1003 if they are equally easy. */
1006 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
1007 target, mode, tmode, total_size)
1009 unsigned HOST_WIDE_INT bitsize;
1010 unsigned HOST_WIDE_INT bitnum;
1013 enum machine_mode mode, tmode;
1014 HOST_WIDE_INT total_size;
1017 = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
1018 unsigned HOST_WIDE_INT offset = bitnum / unit;
1019 unsigned HOST_WIDE_INT bitpos = bitnum % unit;
1021 rtx spec_target = target;
1022 rtx spec_target_subreg = 0;
1023 enum machine_mode int_mode;
1024 enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0);
1025 enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0);
1026 enum machine_mode mode1;
1029 /* Discount the part of the structure before the desired byte.
1030 We need to know how many bytes are safe to reference after it. */
1031 if (total_size >= 0)
1032 total_size -= (bitpos / BIGGEST_ALIGNMENT
1033 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
1035 if (tmode == VOIDmode)
1038 while (GET_CODE (op0) == SUBREG)
1040 bitpos += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1043 offset += (bitpos / unit);
1046 op0 = SUBREG_REG (op0);
1049 if (GET_CODE (op0) == REG
1050 && mode == GET_MODE (op0)
1052 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1054 /* We're trying to extract a full register from itself. */
1058 /* Make sure we are playing with integral modes. Pun with subregs
1061 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1062 if (imode != GET_MODE (op0))
1064 if (GET_CODE (op0) == MEM)
1065 op0 = adjust_address (op0, imode, 0);
1066 else if (imode != BLKmode)
1067 op0 = gen_lowpart (imode, op0);
1073 /* We may be accessing data outside the field, which means
1074 we can alias adjacent data. */
1075 if (GET_CODE (op0) == MEM)
1077 op0 = shallow_copy_rtx (op0);
1078 set_mem_alias_set (op0, 0);
1079 set_mem_expr (op0, 0);
1082 /* Extraction of a full-word or multi-word value from a structure
1083 in a register or aligned memory can be done with just a SUBREG.
1084 A subword value in the least significant part of a register
1085 can also be extracted with a SUBREG. For this, we need the
1086 byte offset of the value in op0. */
1088 byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1090 /* If OP0 is a register, BITPOS must count within a word.
1091 But as we have it, it counts within whatever size OP0 now has.
1092 On a bigendian machine, these are not the same, so convert. */
1093 if (BYTES_BIG_ENDIAN
1094 && GET_CODE (op0) != MEM
1095 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1096 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1098 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1099 If that's wrong, the solution is to test for it and set TARGET to 0
1102 mode1 = (VECTOR_MODE_P (tmode)
1104 : mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0));
1106 if (((GET_CODE (op0) != MEM
1107 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode),
1108 GET_MODE_BITSIZE (GET_MODE (op0)))
1109 && GET_MODE_SIZE (mode1) != 0
1110 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1111 || (GET_CODE (op0) == MEM
1112 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1113 || (offset * BITS_PER_UNIT % bitsize == 0
1114 && MEM_ALIGN (op0) % bitsize == 0))))
1115 && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1116 && bitpos % BITS_PER_WORD == 0)
1117 || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
1118 /* ??? The big endian test here is wrong. This is correct
1119 if the value is in a register, and if mode_for_size is not
1120 the same mode as op0. This causes us to get unnecessarily
1121 inefficient code from the Thumb port when -mbig-endian. */
1122 && (BYTES_BIG_ENDIAN
1123 ? bitpos + bitsize == BITS_PER_WORD
1126 if (mode1 != GET_MODE (op0))
1128 if (GET_CODE (op0) == SUBREG)
1130 if (GET_MODE (SUBREG_REG (op0)) == mode1
1131 || GET_MODE_CLASS (mode1) == MODE_INT
1132 || GET_MODE_CLASS (mode1) == MODE_PARTIAL_INT)
1133 op0 = SUBREG_REG (op0);
1135 /* Else we've got some float mode source being extracted into
1136 a different float mode destination -- this combination of
1137 subregs results in Severe Tire Damage. */
1138 goto no_subreg_mode_swap;
1140 if (GET_CODE (op0) == REG)
1141 op0 = gen_rtx_SUBREG (mode1, op0, byte_offset);
1143 op0 = adjust_address (op0, mode1, offset);
1146 return convert_to_mode (tmode, op0, unsignedp);
1149 no_subreg_mode_swap:
1151 /* Handle fields bigger than a word. */
1153 if (bitsize > BITS_PER_WORD)
1155 /* Here we transfer the words of the field
1156 in the order least significant first.
1157 This is because the most significant word is the one which may
1158 be less than full. */
1160 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1163 if (target == 0 || GET_CODE (target) != REG)
1164 target = gen_reg_rtx (mode);
1166 /* Indicate for flow that the entire target reg is being set. */
1167 emit_insn (gen_rtx_CLOBBER (VOIDmode, target));
1169 for (i = 0; i < nwords; i++)
1171 /* If I is 0, use the low-order word in both field and target;
1172 if I is 1, use the next to lowest word; and so on. */
1173 /* Word number in TARGET to use. */
1174 unsigned int wordnum
1176 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1178 /* Offset from start of field in OP0. */
1179 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1180 ? MAX (0, ((int) bitsize - ((int) i + 1)
1181 * (int) BITS_PER_WORD))
1182 : (int) i * BITS_PER_WORD);
1183 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1185 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1186 bitsize - i * BITS_PER_WORD),
1187 bitnum + bit_offset, 1, target_part, mode,
1188 word_mode, total_size);
1190 if (target_part == 0)
1193 if (result_part != target_part)
1194 emit_move_insn (target_part, result_part);
1199 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1200 need to be zero'd out. */
1201 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1203 unsigned int i, total_words;
1205 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1206 for (i = nwords; i < total_words; i++)
1208 (operand_subword (target,
1209 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1216 /* Signed bit field: sign-extend with two arithmetic shifts. */
1217 target = expand_shift (LSHIFT_EXPR, mode, target,
1218 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1220 return expand_shift (RSHIFT_EXPR, mode, target,
1221 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1225 /* From here on we know the desired field is smaller than a word. */
1227 /* Check if there is a correspondingly-sized integer field, so we can
1228 safely extract it as one size of integer, if necessary; then
1229 truncate or extend to the size that is wanted; then use SUBREGs or
1230 convert_to_mode to get one of the modes we really wanted. */
1232 int_mode = int_mode_for_mode (tmode);
1233 if (int_mode == BLKmode)
1234 int_mode = int_mode_for_mode (mode);
1235 if (int_mode == BLKmode)
1236 abort (); /* Should probably push op0 out to memory and then
1239 /* OFFSET is the number of words or bytes (UNIT says which)
1240 from STR_RTX to the first word or byte containing part of the field. */
1242 if (GET_CODE (op0) != MEM)
1245 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1247 if (GET_CODE (op0) != REG)
1248 op0 = copy_to_reg (op0);
1249 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1250 op0, (offset * UNITS_PER_WORD));
1255 op0 = protect_from_queue (str_rtx, 1);
1257 /* Now OFFSET is nonzero only for memory operands. */
1262 && (GET_MODE_BITSIZE (extzv_mode) >= bitsize)
1263 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1264 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode))))
1266 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1267 rtx bitsize_rtx, bitpos_rtx;
1268 rtx last = get_last_insn ();
1270 rtx xtarget = target;
1271 rtx xspec_target = spec_target;
1272 rtx xspec_target_subreg = spec_target_subreg;
1274 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0);
1276 if (GET_CODE (xop0) == MEM)
1278 int save_volatile_ok = volatile_ok;
1281 /* Is the memory operand acceptable? */
1282 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate)
1283 (xop0, GET_MODE (xop0))))
1285 /* No, load into a reg and extract from there. */
1286 enum machine_mode bestmode;
1288 /* Get the mode to use for inserting into this field. If
1289 OP0 is BLKmode, get the smallest mode consistent with the
1290 alignment. If OP0 is a non-BLKmode object that is no
1291 wider than MAXMODE, use its mode. Otherwise, use the
1292 smallest mode containing the field. */
1294 if (GET_MODE (xop0) == BLKmode
1295 || (GET_MODE_SIZE (GET_MODE (op0))
1296 > GET_MODE_SIZE (maxmode)))
1297 bestmode = get_best_mode (bitsize, bitnum,
1298 MEM_ALIGN (xop0), maxmode,
1299 MEM_VOLATILE_P (xop0));
1301 bestmode = GET_MODE (xop0);
1303 if (bestmode == VOIDmode
1304 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1305 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1308 /* Compute offset as multiple of this unit,
1309 counting in bytes. */
1310 unit = GET_MODE_BITSIZE (bestmode);
1311 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1312 xbitpos = bitnum % unit;
1313 xop0 = adjust_address (xop0, bestmode, xoffset);
1315 /* Fetch it to a register in that size. */
1316 xop0 = force_reg (bestmode, xop0);
1318 /* XBITPOS counts within UNIT, which is what is expected. */
1321 /* Get ref to first byte containing part of the field. */
1322 xop0 = adjust_address (xop0, byte_mode, xoffset);
1324 volatile_ok = save_volatile_ok;
1327 /* If op0 is a register, we need it in MAXMODE (which is usually
1328 SImode). to make it acceptable to the format of extzv. */
1329 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1331 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1332 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1334 /* On big-endian machines, we count bits from the most significant.
1335 If the bit field insn does not, we must invert. */
1336 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1337 xbitpos = unit - bitsize - xbitpos;
1339 /* Now convert from counting within UNIT to counting in MAXMODE. */
1340 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1341 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1343 unit = GET_MODE_BITSIZE (maxmode);
1346 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1347 xtarget = xspec_target = gen_reg_rtx (tmode);
1349 if (GET_MODE (xtarget) != maxmode)
1351 if (GET_CODE (xtarget) == REG)
1353 int wider = (GET_MODE_SIZE (maxmode)
1354 > GET_MODE_SIZE (GET_MODE (xtarget)));
1355 xtarget = gen_lowpart (maxmode, xtarget);
1357 xspec_target_subreg = xtarget;
1360 xtarget = gen_reg_rtx (maxmode);
1363 /* If this machine's extzv insists on a register target,
1364 make sure we have one. */
1365 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate)
1366 (xtarget, maxmode)))
1367 xtarget = gen_reg_rtx (maxmode);
1369 bitsize_rtx = GEN_INT (bitsize);
1370 bitpos_rtx = GEN_INT (xbitpos);
1372 pat = gen_extzv (protect_from_queue (xtarget, 1),
1373 xop0, bitsize_rtx, bitpos_rtx);
1378 spec_target = xspec_target;
1379 spec_target_subreg = xspec_target_subreg;
1383 delete_insns_since (last);
1384 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1390 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1396 && (GET_MODE_BITSIZE (extv_mode) >= bitsize)
1397 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1398 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode))))
1400 int xbitpos = bitpos, xoffset = offset;
1401 rtx bitsize_rtx, bitpos_rtx;
1402 rtx last = get_last_insn ();
1403 rtx xop0 = op0, xtarget = target;
1404 rtx xspec_target = spec_target;
1405 rtx xspec_target_subreg = spec_target_subreg;
1407 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0);
1409 if (GET_CODE (xop0) == MEM)
1411 /* Is the memory operand acceptable? */
1412 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate)
1413 (xop0, GET_MODE (xop0))))
1415 /* No, load into a reg and extract from there. */
1416 enum machine_mode bestmode;
1418 /* Get the mode to use for inserting into this field. If
1419 OP0 is BLKmode, get the smallest mode consistent with the
1420 alignment. If OP0 is a non-BLKmode object that is no
1421 wider than MAXMODE, use its mode. Otherwise, use the
1422 smallest mode containing the field. */
1424 if (GET_MODE (xop0) == BLKmode
1425 || (GET_MODE_SIZE (GET_MODE (op0))
1426 > GET_MODE_SIZE (maxmode)))
1427 bestmode = get_best_mode (bitsize, bitnum,
1428 MEM_ALIGN (xop0), maxmode,
1429 MEM_VOLATILE_P (xop0));
1431 bestmode = GET_MODE (xop0);
1433 if (bestmode == VOIDmode
1434 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0))
1435 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0)))
1438 /* Compute offset as multiple of this unit,
1439 counting in bytes. */
1440 unit = GET_MODE_BITSIZE (bestmode);
1441 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1442 xbitpos = bitnum % unit;
1443 xop0 = adjust_address (xop0, bestmode, xoffset);
1445 /* Fetch it to a register in that size. */
1446 xop0 = force_reg (bestmode, xop0);
1448 /* XBITPOS counts within UNIT, which is what is expected. */
1451 /* Get ref to first byte containing part of the field. */
1452 xop0 = adjust_address (xop0, byte_mode, xoffset);
1455 /* If op0 is a register, we need it in MAXMODE (which is usually
1456 SImode) to make it acceptable to the format of extv. */
1457 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1459 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1460 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0);
1462 /* On big-endian machines, we count bits from the most significant.
1463 If the bit field insn does not, we must invert. */
1464 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1465 xbitpos = unit - bitsize - xbitpos;
1467 /* XBITPOS counts within a size of UNIT.
1468 Adjust to count within a size of MAXMODE. */
1469 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1470 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1472 unit = GET_MODE_BITSIZE (maxmode);
1475 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1476 xtarget = xspec_target = gen_reg_rtx (tmode);
1478 if (GET_MODE (xtarget) != maxmode)
1480 if (GET_CODE (xtarget) == REG)
1482 int wider = (GET_MODE_SIZE (maxmode)
1483 > GET_MODE_SIZE (GET_MODE (xtarget)));
1484 xtarget = gen_lowpart (maxmode, xtarget);
1486 xspec_target_subreg = xtarget;
1489 xtarget = gen_reg_rtx (maxmode);
1492 /* If this machine's extv insists on a register target,
1493 make sure we have one. */
1494 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate)
1495 (xtarget, maxmode)))
1496 xtarget = gen_reg_rtx (maxmode);
1498 bitsize_rtx = GEN_INT (bitsize);
1499 bitpos_rtx = GEN_INT (xbitpos);
1501 pat = gen_extv (protect_from_queue (xtarget, 1),
1502 xop0, bitsize_rtx, bitpos_rtx);
1507 spec_target = xspec_target;
1508 spec_target_subreg = xspec_target_subreg;
1512 delete_insns_since (last);
1513 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1519 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1522 if (target == spec_target)
1524 if (target == spec_target_subreg)
1526 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1528 /* If the target mode is floating-point, first convert to the
1529 integer mode of that size and then access it as a floating-point
1530 value via a SUBREG. */
1531 if (GET_MODE_CLASS (tmode) != MODE_INT
1532 && GET_MODE_CLASS (tmode) != MODE_PARTIAL_INT)
1534 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1537 return gen_lowpart (tmode, target);
1540 return convert_to_mode (tmode, target, unsignedp);
1545 /* Extract a bit field using shifts and boolean operations
1546 Returns an rtx to represent the value.
1547 OP0 addresses a register (word) or memory (byte).
1548 BITPOS says which bit within the word or byte the bit field starts in.
1549 OFFSET says how many bytes farther the bit field starts;
1550 it is 0 if OP0 is a register.
1551 BITSIZE says how many bits long the bit field is.
1552 (If OP0 is a register, it may be narrower than a full word,
1553 but BITPOS still counts within a full word,
1554 which is significant on bigendian machines.)
1556 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1557 If TARGET is nonzero, attempts to store the value there
1558 and return TARGET, but this is not guaranteed.
1559 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1562 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1564 enum machine_mode tmode;
1566 unsigned HOST_WIDE_INT offset, bitsize, bitpos;
1569 unsigned int total_bits = BITS_PER_WORD;
1570 enum machine_mode mode;
1572 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1574 /* Special treatment for a bit field split across two registers. */
1575 if (bitsize + bitpos > BITS_PER_WORD)
1576 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1580 /* Get the proper mode to use for this field. We want a mode that
1581 includes the entire field. If such a mode would be larger than
1582 a word, we won't be doing the extraction the normal way. */
1584 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1585 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1587 if (mode == VOIDmode)
1588 /* The only way this should occur is if the field spans word
1590 return extract_split_bit_field (op0, bitsize,
1591 bitpos + offset * BITS_PER_UNIT,
1594 total_bits = GET_MODE_BITSIZE (mode);
1596 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1597 be in the range 0 to total_bits-1, and put any excess bytes in
1599 if (bitpos >= total_bits)
1601 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1602 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1606 /* Get ref to an aligned byte, halfword, or word containing the field.
1607 Adjust BITPOS to be position within a word,
1608 and OFFSET to be the offset of that word.
1609 Then alter OP0 to refer to that word. */
1610 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1611 offset -= (offset % (total_bits / BITS_PER_UNIT));
1612 op0 = adjust_address (op0, mode, offset);
1615 mode = GET_MODE (op0);
1617 if (BYTES_BIG_ENDIAN)
1618 /* BITPOS is the distance between our msb and that of OP0.
1619 Convert it to the distance from the lsb. */
1620 bitpos = total_bits - bitsize - bitpos;
1622 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1623 We have reduced the big-endian case to the little-endian case. */
1629 /* If the field does not already start at the lsb,
1630 shift it so it does. */
1631 tree amount = build_int_2 (bitpos, 0);
1632 /* Maybe propagate the target for the shift. */
1633 /* But not if we will return it--could confuse integrate.c. */
1634 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1635 && !REG_FUNCTION_VALUE_P (target)
1637 if (tmode != mode) subtarget = 0;
1638 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1640 /* Convert the value to the desired mode. */
1642 op0 = convert_to_mode (tmode, op0, 1);
1644 /* Unless the msb of the field used to be the msb when we shifted,
1645 mask out the upper bits. */
1647 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1648 return expand_binop (GET_MODE (op0), and_optab, op0,
1649 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1650 target, 1, OPTAB_LIB_WIDEN);
1654 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1655 then arithmetic-shift its lsb to the lsb of the word. */
1656 op0 = force_reg (mode, op0);
1660 /* Find the narrowest integer mode that contains the field. */
1662 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1663 mode = GET_MODE_WIDER_MODE (mode))
1664 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1666 op0 = convert_to_mode (mode, op0, 0);
1670 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1673 = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1674 /* Maybe propagate the target for the shift. */
1675 /* But not if we will return the result--could confuse integrate.c. */
1676 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1677 && ! REG_FUNCTION_VALUE_P (target)
1679 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1682 return expand_shift (RSHIFT_EXPR, mode, op0,
1683 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1687 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1688 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1689 complement of that if COMPLEMENT. The mask is truncated if
1690 necessary to the width of mode MODE. The mask is zero-extended if
1691 BITSIZE+BITPOS is too small for MODE. */
1694 mask_rtx (mode, bitpos, bitsize, complement)
1695 enum machine_mode mode;
1696 int bitpos, bitsize, complement;
1698 HOST_WIDE_INT masklow, maskhigh;
1700 if (bitpos < HOST_BITS_PER_WIDE_INT)
1701 masklow = (HOST_WIDE_INT) -1 << bitpos;
1705 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1706 masklow &= ((unsigned HOST_WIDE_INT) -1
1707 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1709 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1712 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1714 if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1715 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1716 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1722 maskhigh = ~maskhigh;
1726 return immed_double_const (masklow, maskhigh, mode);
1729 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1730 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1733 lshift_value (mode, value, bitpos, bitsize)
1734 enum machine_mode mode;
1736 int bitpos, bitsize;
1738 unsigned HOST_WIDE_INT v = INTVAL (value);
1739 HOST_WIDE_INT low, high;
1741 if (bitsize < HOST_BITS_PER_WIDE_INT)
1742 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1744 if (bitpos < HOST_BITS_PER_WIDE_INT)
1747 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1752 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1755 return immed_double_const (low, high, mode);
1758 /* Extract a bit field that is split across two words
1759 and return an RTX for the result.
1761 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1762 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1763 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1766 extract_split_bit_field (op0, bitsize, bitpos, unsignedp)
1768 unsigned HOST_WIDE_INT bitsize, bitpos;
1772 unsigned int bitsdone = 0;
1773 rtx result = NULL_RTX;
1776 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1778 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1779 unit = BITS_PER_WORD;
1781 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1783 while (bitsdone < bitsize)
1785 unsigned HOST_WIDE_INT thissize;
1787 unsigned HOST_WIDE_INT thispos;
1788 unsigned HOST_WIDE_INT offset;
1790 offset = (bitpos + bitsdone) / unit;
1791 thispos = (bitpos + bitsdone) % unit;
1793 /* THISSIZE must not overrun a word boundary. Otherwise,
1794 extract_fixed_bit_field will call us again, and we will mutually
1796 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1797 thissize = MIN (thissize, unit - thispos);
1799 /* If OP0 is a register, then handle OFFSET here.
1801 When handling multiword bitfields, extract_bit_field may pass
1802 down a word_mode SUBREG of a larger REG for a bitfield that actually
1803 crosses a word boundary. Thus, for a SUBREG, we must find
1804 the current word starting from the base register. */
1805 if (GET_CODE (op0) == SUBREG)
1807 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1808 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1809 GET_MODE (SUBREG_REG (op0)));
1812 else if (GET_CODE (op0) == REG)
1814 word = operand_subword_force (op0, offset, GET_MODE (op0));
1820 /* Extract the parts in bit-counting order,
1821 whose meaning is determined by BYTES_PER_UNIT.
1822 OFFSET is in UNITs, and UNIT is in bits.
1823 extract_fixed_bit_field wants offset in bytes. */
1824 part = extract_fixed_bit_field (word_mode, word,
1825 offset * unit / BITS_PER_UNIT,
1826 thissize, thispos, 0, 1);
1827 bitsdone += thissize;
1829 /* Shift this part into place for the result. */
1830 if (BYTES_BIG_ENDIAN)
1832 if (bitsize != bitsdone)
1833 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1834 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1838 if (bitsdone != thissize)
1839 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1840 build_int_2 (bitsdone - thissize, 0), 0, 1);
1846 /* Combine the parts with bitwise or. This works
1847 because we extracted each part as an unsigned bit field. */
1848 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1854 /* Unsigned bit field: we are done. */
1857 /* Signed bit field: sign-extend with two arithmetic shifts. */
1858 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1859 build_int_2 (BITS_PER_WORD - bitsize, 0),
1861 return expand_shift (RSHIFT_EXPR, word_mode, result,
1862 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1865 /* Add INC into TARGET. */
1868 expand_inc (target, inc)
1871 rtx value = expand_binop (GET_MODE (target), add_optab,
1873 target, 0, OPTAB_LIB_WIDEN);
1874 if (value != target)
1875 emit_move_insn (target, value);
1878 /* Subtract DEC from TARGET. */
1881 expand_dec (target, dec)
1884 rtx value = expand_binop (GET_MODE (target), sub_optab,
1886 target, 0, OPTAB_LIB_WIDEN);
1887 if (value != target)
1888 emit_move_insn (target, value);
1891 /* Output a shift instruction for expression code CODE,
1892 with SHIFTED being the rtx for the value to shift,
1893 and AMOUNT the tree for the amount to shift by.
1894 Store the result in the rtx TARGET, if that is convenient.
1895 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1896 Return the rtx for where the value is. */
1899 expand_shift (code, mode, shifted, amount, target, unsignedp)
1900 enum tree_code code;
1901 enum machine_mode mode;
1908 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1909 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1912 /* Previously detected shift-counts computed by NEGATE_EXPR
1913 and shifted in the other direction; but that does not work
1916 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1918 #ifdef SHIFT_COUNT_TRUNCATED
1919 if (SHIFT_COUNT_TRUNCATED)
1921 if (GET_CODE (op1) == CONST_INT
1922 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
1923 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
1924 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
1925 % GET_MODE_BITSIZE (mode));
1926 else if (GET_CODE (op1) == SUBREG
1927 && subreg_lowpart_p (op1))
1928 op1 = SUBREG_REG (op1);
1932 if (op1 == const0_rtx)
1935 for (try = 0; temp == 0 && try < 3; try++)
1937 enum optab_methods methods;
1940 methods = OPTAB_DIRECT;
1942 methods = OPTAB_WIDEN;
1944 methods = OPTAB_LIB_WIDEN;
1948 /* Widening does not work for rotation. */
1949 if (methods == OPTAB_WIDEN)
1951 else if (methods == OPTAB_LIB_WIDEN)
1953 /* If we have been unable to open-code this by a rotation,
1954 do it as the IOR of two shifts. I.e., to rotate A
1955 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
1956 where C is the bitsize of A.
1958 It is theoretically possible that the target machine might
1959 not be able to perform either shift and hence we would
1960 be making two libcalls rather than just the one for the
1961 shift (similarly if IOR could not be done). We will allow
1962 this extremely unlikely lossage to avoid complicating the
1965 rtx subtarget = target == shifted ? 0 : target;
1967 tree type = TREE_TYPE (amount);
1968 tree new_amount = make_tree (type, op1);
1970 = fold (build (MINUS_EXPR, type,
1972 build_int_2 (GET_MODE_BITSIZE (mode),
1976 shifted = force_reg (mode, shifted);
1978 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
1979 mode, shifted, new_amount, subtarget, 1);
1980 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
1981 mode, shifted, other_amount, 0, 1);
1982 return expand_binop (mode, ior_optab, temp, temp1, target,
1983 unsignedp, methods);
1986 temp = expand_binop (mode,
1987 left ? rotl_optab : rotr_optab,
1988 shifted, op1, target, unsignedp, methods);
1990 /* If we don't have the rotate, but we are rotating by a constant
1991 that is in range, try a rotate in the opposite direction. */
1993 if (temp == 0 && GET_CODE (op1) == CONST_INT
1995 && (unsigned int) INTVAL (op1) < GET_MODE_BITSIZE (mode))
1996 temp = expand_binop (mode,
1997 left ? rotr_optab : rotl_optab,
1999 GEN_INT (GET_MODE_BITSIZE (mode)
2001 target, unsignedp, methods);
2004 temp = expand_binop (mode,
2005 left ? ashl_optab : lshr_optab,
2006 shifted, op1, target, unsignedp, methods);
2008 /* Do arithmetic shifts.
2009 Also, if we are going to widen the operand, we can just as well
2010 use an arithmetic right-shift instead of a logical one. */
2011 if (temp == 0 && ! rotate
2012 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2014 enum optab_methods methods1 = methods;
2016 /* If trying to widen a log shift to an arithmetic shift,
2017 don't accept an arithmetic shift of the same size. */
2019 methods1 = OPTAB_MUST_WIDEN;
2021 /* Arithmetic shift */
2023 temp = expand_binop (mode,
2024 left ? ashl_optab : ashr_optab,
2025 shifted, op1, target, unsignedp, methods1);
2028 /* We used to try extzv here for logical right shifts, but that was
2029 only useful for one machine, the VAX, and caused poor code
2030 generation there for lshrdi3, so the code was deleted and a
2031 define_expand for lshrsi3 was added to vax.md. */
2039 enum alg_code { alg_zero, alg_m, alg_shift,
2040 alg_add_t_m2, alg_sub_t_m2,
2041 alg_add_factor, alg_sub_factor,
2042 alg_add_t2_m, alg_sub_t2_m,
2043 alg_add, alg_subtract, alg_factor, alg_shiftop };
2045 /* This structure records a sequence of operations.
2046 `ops' is the number of operations recorded.
2047 `cost' is their total cost.
2048 The operations are stored in `op' and the corresponding
2049 logarithms of the integer coefficients in `log'.
2051 These are the operations:
2052 alg_zero total := 0;
2053 alg_m total := multiplicand;
2054 alg_shift total := total * coeff
2055 alg_add_t_m2 total := total + multiplicand * coeff;
2056 alg_sub_t_m2 total := total - multiplicand * coeff;
2057 alg_add_factor total := total * coeff + total;
2058 alg_sub_factor total := total * coeff - total;
2059 alg_add_t2_m total := total * coeff + multiplicand;
2060 alg_sub_t2_m total := total * coeff - multiplicand;
2062 The first operand must be either alg_zero or alg_m. */
2068 /* The size of the OP and LOG fields are not directly related to the
2069 word size, but the worst-case algorithms will be if we have few
2070 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2071 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2072 in total wordsize operations. */
2073 enum alg_code op[MAX_BITS_PER_WORD];
2074 char log[MAX_BITS_PER_WORD];
2077 static void synth_mult PARAMS ((struct algorithm *,
2078 unsigned HOST_WIDE_INT,
2080 static unsigned HOST_WIDE_INT choose_multiplier PARAMS ((unsigned HOST_WIDE_INT,
2082 unsigned HOST_WIDE_INT *,
2084 static unsigned HOST_WIDE_INT invert_mod2n PARAMS ((unsigned HOST_WIDE_INT,
2086 /* Compute and return the best algorithm for multiplying by T.
2087 The algorithm must cost less than cost_limit
2088 If retval.cost >= COST_LIMIT, no algorithm was found and all
2089 other field of the returned struct are undefined. */
2092 synth_mult (alg_out, t, cost_limit)
2093 struct algorithm *alg_out;
2094 unsigned HOST_WIDE_INT t;
2098 struct algorithm *alg_in, *best_alg;
2100 unsigned HOST_WIDE_INT q;
2102 /* Indicate that no algorithm is yet found. If no algorithm
2103 is found, this value will be returned and indicate failure. */
2104 alg_out->cost = cost_limit;
2106 if (cost_limit <= 0)
2109 /* t == 1 can be done in zero cost. */
2114 alg_out->op[0] = alg_m;
2118 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2122 if (zero_cost >= cost_limit)
2127 alg_out->cost = zero_cost;
2128 alg_out->op[0] = alg_zero;
2133 /* We'll be needing a couple extra algorithm structures now. */
2135 alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
2136 best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
2138 /* If we have a group of zero bits at the low-order part of T, try
2139 multiplying by the remaining bits and then doing a shift. */
2143 m = floor_log2 (t & -t); /* m = number of low zero bits */
2144 if (m < BITS_PER_WORD)
2147 cost = shift_cost[m];
2148 synth_mult (alg_in, q, cost_limit - cost);
2150 cost += alg_in->cost;
2151 if (cost < cost_limit)
2153 struct algorithm *x;
2154 x = alg_in, alg_in = best_alg, best_alg = x;
2155 best_alg->log[best_alg->ops] = m;
2156 best_alg->op[best_alg->ops] = alg_shift;
2162 /* If we have an odd number, add or subtract one. */
2165 unsigned HOST_WIDE_INT w;
2167 for (w = 1; (w & t) != 0; w <<= 1)
2169 /* If T was -1, then W will be zero after the loop. This is another
2170 case where T ends with ...111. Handling this with (T + 1) and
2171 subtract 1 produces slightly better code and results in algorithm
2172 selection much faster than treating it like the ...0111 case
2176 /* Reject the case where t is 3.
2177 Thus we prefer addition in that case. */
2180 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2183 synth_mult (alg_in, t + 1, cost_limit - cost);
2185 cost += alg_in->cost;
2186 if (cost < cost_limit)
2188 struct algorithm *x;
2189 x = alg_in, alg_in = best_alg, best_alg = x;
2190 best_alg->log[best_alg->ops] = 0;
2191 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2197 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2200 synth_mult (alg_in, t - 1, cost_limit - cost);
2202 cost += alg_in->cost;
2203 if (cost < cost_limit)
2205 struct algorithm *x;
2206 x = alg_in, alg_in = best_alg, best_alg = x;
2207 best_alg->log[best_alg->ops] = 0;
2208 best_alg->op[best_alg->ops] = alg_add_t_m2;
2214 /* Look for factors of t of the form
2215 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2216 If we find such a factor, we can multiply by t using an algorithm that
2217 multiplies by q, shift the result by m and add/subtract it to itself.
2219 We search for large factors first and loop down, even if large factors
2220 are less probable than small; if we find a large factor we will find a
2221 good sequence quickly, and therefore be able to prune (by decreasing
2222 COST_LIMIT) the search. */
2224 for (m = floor_log2 (t - 1); m >= 2; m--)
2226 unsigned HOST_WIDE_INT d;
2228 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2229 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2231 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2232 synth_mult (alg_in, t / d, cost_limit - cost);
2234 cost += alg_in->cost;
2235 if (cost < cost_limit)
2237 struct algorithm *x;
2238 x = alg_in, alg_in = best_alg, best_alg = x;
2239 best_alg->log[best_alg->ops] = m;
2240 best_alg->op[best_alg->ops] = alg_add_factor;
2243 /* Other factors will have been taken care of in the recursion. */
2247 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2248 if (t % d == 0 && t > d && m < BITS_PER_WORD)
2250 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2251 synth_mult (alg_in, t / d, cost_limit - cost);
2253 cost += alg_in->cost;
2254 if (cost < cost_limit)
2256 struct algorithm *x;
2257 x = alg_in, alg_in = best_alg, best_alg = x;
2258 best_alg->log[best_alg->ops] = m;
2259 best_alg->op[best_alg->ops] = alg_sub_factor;
2266 /* Try shift-and-add (load effective address) instructions,
2267 i.e. do a*3, a*5, a*9. */
2273 if (m >= 0 && m < BITS_PER_WORD)
2275 cost = shiftadd_cost[m];
2276 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2278 cost += alg_in->cost;
2279 if (cost < cost_limit)
2281 struct algorithm *x;
2282 x = alg_in, alg_in = best_alg, best_alg = x;
2283 best_alg->log[best_alg->ops] = m;
2284 best_alg->op[best_alg->ops] = alg_add_t2_m;
2292 if (m >= 0 && m < BITS_PER_WORD)
2294 cost = shiftsub_cost[m];
2295 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2297 cost += alg_in->cost;
2298 if (cost < cost_limit)
2300 struct algorithm *x;
2301 x = alg_in, alg_in = best_alg, best_alg = x;
2302 best_alg->log[best_alg->ops] = m;
2303 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2309 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2310 we have not found any algorithm. */
2311 if (cost_limit == alg_out->cost)
2314 /* If we are getting a too long sequence for `struct algorithm'
2315 to record, make this search fail. */
2316 if (best_alg->ops == MAX_BITS_PER_WORD)
2319 /* Copy the algorithm from temporary space to the space at alg_out.
2320 We avoid using structure assignment because the majority of
2321 best_alg is normally undefined, and this is a critical function. */
2322 alg_out->ops = best_alg->ops + 1;
2323 alg_out->cost = cost_limit;
2324 memcpy (alg_out->op, best_alg->op,
2325 alg_out->ops * sizeof *alg_out->op);
2326 memcpy (alg_out->log, best_alg->log,
2327 alg_out->ops * sizeof *alg_out->log);
2330 /* Perform a multiplication and return an rtx for the result.
2331 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2332 TARGET is a suggestion for where to store the result (an rtx).
2334 We check specially for a constant integer as OP1.
2335 If you want this check for OP0 as well, then before calling
2336 you should swap the two operands if OP0 would be constant. */
2339 expand_mult (mode, op0, op1, target, unsignedp)
2340 enum machine_mode mode;
2341 rtx op0, op1, target;
2344 rtx const_op1 = op1;
2346 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2347 less than or equal in size to `unsigned int' this doesn't matter.
2348 If the mode is larger than `unsigned int', then synth_mult works only
2349 if the constant value exactly fits in an `unsigned int' without any
2350 truncation. This means that multiplying by negative values does
2351 not work; results are off by 2^32 on a 32 bit machine. */
2353 /* If we are multiplying in DImode, it may still be a win
2354 to try to work with shifts and adds. */
2355 if (GET_CODE (op1) == CONST_DOUBLE
2356 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2357 && HOST_BITS_PER_INT >= BITS_PER_WORD
2358 && CONST_DOUBLE_HIGH (op1) == 0)
2359 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2360 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2361 && GET_CODE (op1) == CONST_INT
2362 && INTVAL (op1) < 0)
2365 /* We used to test optimize here, on the grounds that it's better to
2366 produce a smaller program when -O is not used.
2367 But this causes such a terrible slowdown sometimes
2368 that it seems better to use synth_mult always. */
2370 if (const_op1 && GET_CODE (const_op1) == CONST_INT
2371 && (unsignedp || ! flag_trapv))
2373 struct algorithm alg;
2374 struct algorithm alg2;
2375 HOST_WIDE_INT val = INTVAL (op1);
2376 HOST_WIDE_INT val_so_far;
2379 enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2381 /* op0 must be register to make mult_cost match the precomputed
2382 shiftadd_cost array. */
2383 op0 = force_reg (mode, op0);
2385 /* Try to do the computation three ways: multiply by the negative of OP1
2386 and then negate, do the multiplication directly, or do multiplication
2389 mult_cost = rtx_cost (gen_rtx_MULT (mode, op0, op1), SET);
2390 mult_cost = MIN (12 * add_cost, mult_cost);
2392 synth_mult (&alg, val, mult_cost);
2394 /* This works only if the inverted value actually fits in an
2396 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2398 synth_mult (&alg2, - val,
2399 (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2400 if (alg2.cost + negate_cost < alg.cost)
2401 alg = alg2, variant = negate_variant;
2404 /* This proves very useful for division-by-constant. */
2405 synth_mult (&alg2, val - 1,
2406 (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2407 if (alg2.cost + add_cost < alg.cost)
2408 alg = alg2, variant = add_variant;
2410 if (alg.cost < mult_cost)
2412 /* We found something cheaper than a multiply insn. */
2415 enum machine_mode nmode;
2417 op0 = protect_from_queue (op0, 0);
2419 /* Avoid referencing memory over and over.
2420 For speed, but also for correctness when mem is volatile. */
2421 if (GET_CODE (op0) == MEM)
2422 op0 = force_reg (mode, op0);
2424 /* ACCUM starts out either as OP0 or as a zero, depending on
2425 the first operation. */
2427 if (alg.op[0] == alg_zero)
2429 accum = copy_to_mode_reg (mode, const0_rtx);
2432 else if (alg.op[0] == alg_m)
2434 accum = copy_to_mode_reg (mode, op0);
2440 for (opno = 1; opno < alg.ops; opno++)
2442 int log = alg.log[opno];
2443 int preserve = preserve_subexpressions_p ();
2444 rtx shift_subtarget = preserve ? 0 : accum;
2446 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2449 rtx accum_target = preserve ? 0 : accum;
2451 switch (alg.op[opno])
2454 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2455 build_int_2 (log, 0), NULL_RTX, 0);
2460 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2461 build_int_2 (log, 0), NULL_RTX, 0);
2462 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2464 ? add_target : accum_target);
2465 val_so_far += (HOST_WIDE_INT) 1 << log;
2469 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2470 build_int_2 (log, 0), NULL_RTX, 0);
2471 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2473 ? add_target : accum_target);
2474 val_so_far -= (HOST_WIDE_INT) 1 << log;
2478 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2479 build_int_2 (log, 0), shift_subtarget,
2481 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
2483 ? add_target : accum_target);
2484 val_so_far = (val_so_far << log) + 1;
2488 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2489 build_int_2 (log, 0), shift_subtarget,
2491 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
2493 ? add_target : accum_target);
2494 val_so_far = (val_so_far << log) - 1;
2497 case alg_add_factor:
2498 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2499 build_int_2 (log, 0), NULL_RTX, 0);
2500 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2502 ? add_target : accum_target);
2503 val_so_far += val_so_far << log;
2506 case alg_sub_factor:
2507 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2508 build_int_2 (log, 0), NULL_RTX, 0);
2509 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
2510 (add_target ? add_target
2511 : preserve ? 0 : tem));
2512 val_so_far = (val_so_far << log) - val_so_far;
2519 /* Write a REG_EQUAL note on the last insn so that we can cse
2520 multiplication sequences. Note that if ACCUM is a SUBREG,
2521 we've set the inner register and must properly indicate
2524 tem = op0, nmode = mode;
2525 if (GET_CODE (accum) == SUBREG)
2527 nmode = GET_MODE (SUBREG_REG (accum));
2528 tem = gen_lowpart (nmode, op0);
2531 insn = get_last_insn ();
2532 set_unique_reg_note (insn,
2534 gen_rtx_MULT (nmode, tem,
2535 GEN_INT (val_so_far)));
2538 if (variant == negate_variant)
2540 val_so_far = - val_so_far;
2541 accum = expand_unop (mode, neg_optab, accum, target, 0);
2543 else if (variant == add_variant)
2545 val_so_far = val_so_far + 1;
2546 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
2549 if (val != val_so_far)
2556 /* This used to use umul_optab if unsigned, but for non-widening multiply
2557 there is no difference between signed and unsigned. */
2558 op0 = expand_binop (mode,
2560 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
2561 ? smulv_optab : smul_optab,
2562 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2568 /* Return the smallest n such that 2**n >= X. */
2572 unsigned HOST_WIDE_INT x;
2574 return floor_log2 (x - 1) + 1;
2577 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2578 replace division by D, and put the least significant N bits of the result
2579 in *MULTIPLIER_PTR and return the most significant bit.
2581 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2582 needed precision is in PRECISION (should be <= N).
2584 PRECISION should be as small as possible so this function can choose
2585 multiplier more freely.
2587 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2588 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2590 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2591 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2594 unsigned HOST_WIDE_INT
2595 choose_multiplier (d, n, precision, multiplier_ptr, post_shift_ptr, lgup_ptr)
2596 unsigned HOST_WIDE_INT d;
2599 unsigned HOST_WIDE_INT *multiplier_ptr;
2600 int *post_shift_ptr;
2603 HOST_WIDE_INT mhigh_hi, mlow_hi;
2604 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
2605 int lgup, post_shift;
2607 unsigned HOST_WIDE_INT nl, dummy1;
2608 HOST_WIDE_INT nh, dummy2;
2610 /* lgup = ceil(log2(divisor)); */
2611 lgup = ceil_log2 (d);
2617 pow2 = n + lgup - precision;
2619 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2621 /* We could handle this with some effort, but this case is much better
2622 handled directly with a scc insn, so rely on caller using that. */
2626 /* mlow = 2^(N + lgup)/d */
2627 if (pow >= HOST_BITS_PER_WIDE_INT)
2629 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2635 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2637 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2638 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2640 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2641 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2642 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2644 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2645 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2646 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2648 if (mhigh_hi && nh - d >= d)
2650 if (mhigh_hi > 1 || mlow_hi > 1)
2652 /* assert that mlow < mhigh. */
2653 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2656 /* If precision == N, then mlow, mhigh exceed 2^N
2657 (but they do not exceed 2^(N+1)). */
2659 /* Reduce to lowest terms */
2660 for (post_shift = lgup; post_shift > 0; post_shift--)
2662 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2663 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2673 *post_shift_ptr = post_shift;
2675 if (n < HOST_BITS_PER_WIDE_INT)
2677 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2678 *multiplier_ptr = mhigh_lo & mask;
2679 return mhigh_lo >= mask;
2683 *multiplier_ptr = mhigh_lo;
2688 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2689 congruent to 1 (mod 2**N). */
2691 static unsigned HOST_WIDE_INT
2693 unsigned HOST_WIDE_INT x;
2696 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2698 /* The algorithm notes that the choice y = x satisfies
2699 x*y == 1 mod 2^3, since x is assumed odd.
2700 Each iteration doubles the number of bits of significance in y. */
2702 unsigned HOST_WIDE_INT mask;
2703 unsigned HOST_WIDE_INT y = x;
2706 mask = (n == HOST_BITS_PER_WIDE_INT
2707 ? ~(unsigned HOST_WIDE_INT) 0
2708 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2712 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2718 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2719 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2720 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2721 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2724 The result is put in TARGET if that is convenient.
2726 MODE is the mode of operation. */
2729 expand_mult_highpart_adjust (mode, adj_operand, op0, op1, target, unsignedp)
2730 enum machine_mode mode;
2731 rtx adj_operand, op0, op1, target;
2735 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2737 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2738 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2740 tem = expand_and (mode, tem, op1, NULL_RTX);
2742 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2745 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2746 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2748 tem = expand_and (mode, tem, op0, NULL_RTX);
2749 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
2755 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2756 in TARGET if that is convenient, and return where the result is. If the
2757 operation can not be performed, 0 is returned.
2759 MODE is the mode of operation and result.
2761 UNSIGNEDP nonzero means unsigned multiply.
2763 MAX_COST is the total allowed cost for the expanded RTL. */
2766 expand_mult_highpart (mode, op0, cnst1, target, unsignedp, max_cost)
2767 enum machine_mode mode;
2769 unsigned HOST_WIDE_INT cnst1;
2773 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2774 optab mul_highpart_optab;
2777 int size = GET_MODE_BITSIZE (mode);
2780 /* We can't support modes wider than HOST_BITS_PER_INT. */
2781 if (size > HOST_BITS_PER_WIDE_INT)
2784 op1 = gen_int_mode (cnst1, mode);
2787 = immed_double_const (cnst1,
2790 : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2793 /* expand_mult handles constant multiplication of word_mode
2794 or narrower. It does a poor job for large modes. */
2795 if (size < BITS_PER_WORD
2796 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2798 /* We have to do this, since expand_binop doesn't do conversion for
2799 multiply. Maybe change expand_binop to handle widening multiply? */
2800 op0 = convert_to_mode (wider_mode, op0, unsignedp);
2802 /* We know that this can't have signed overflow, so pretend this is
2803 an unsigned multiply. */
2804 tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, 0);
2805 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2806 build_int_2 (size, 0), NULL_RTX, 1);
2807 return convert_modes (mode, wider_mode, tem, unsignedp);
2811 target = gen_reg_rtx (mode);
2813 /* Firstly, try using a multiplication insn that only generates the needed
2814 high part of the product, and in the sign flavor of unsignedp. */
2815 if (mul_highpart_cost[(int) mode] < max_cost)
2817 mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2818 target = expand_binop (mode, mul_highpart_optab,
2819 op0, op1, target, unsignedp, OPTAB_DIRECT);
2824 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2825 Need to adjust the result after the multiplication. */
2826 if (size - 1 < BITS_PER_WORD
2827 && (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost
2830 mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2831 target = expand_binop (mode, mul_highpart_optab,
2832 op0, op1, target, unsignedp, OPTAB_DIRECT);
2834 /* We used the wrong signedness. Adjust the result. */
2835 return expand_mult_highpart_adjust (mode, target, op0,
2836 op1, target, unsignedp);
2839 /* Try widening multiplication. */
2840 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2841 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2842 && mul_widen_cost[(int) wider_mode] < max_cost)
2844 op1 = force_reg (mode, op1);
2848 /* Try widening the mode and perform a non-widening multiplication. */
2849 moptab = smul_optab;
2850 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2851 && size - 1 < BITS_PER_WORD
2852 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2858 /* Try widening multiplication of opposite signedness, and adjust. */
2859 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2860 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2861 && size - 1 < BITS_PER_WORD
2862 && (mul_widen_cost[(int) wider_mode]
2863 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2865 rtx regop1 = force_reg (mode, op1);
2866 tem = expand_binop (wider_mode, moptab, op0, regop1,
2867 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2870 /* Extract the high half of the just generated product. */
2871 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2872 build_int_2 (size, 0), NULL_RTX, 1);
2873 tem = convert_modes (mode, wider_mode, tem, unsignedp);
2874 /* We used the wrong signedness. Adjust the result. */
2875 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2883 /* Pass NULL_RTX as target since TARGET has wrong mode. */
2884 tem = expand_binop (wider_mode, moptab, op0, op1,
2885 NULL_RTX, unsignedp, OPTAB_WIDEN);
2889 /* Extract the high half of the just generated product. */
2890 if (mode == word_mode)
2892 return gen_highpart (mode, tem);
2896 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2897 build_int_2 (size, 0), NULL_RTX, 1);
2898 return convert_modes (mode, wider_mode, tem, unsignedp);
2902 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2903 if that is convenient, and returning where the result is.
2904 You may request either the quotient or the remainder as the result;
2905 specify REM_FLAG nonzero to get the remainder.
2907 CODE is the expression code for which kind of division this is;
2908 it controls how rounding is done. MODE is the machine mode to use.
2909 UNSIGNEDP nonzero means do unsigned division. */
2911 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2912 and then correct it by or'ing in missing high bits
2913 if result of ANDI is nonzero.
2914 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2915 This could optimize to a bfexts instruction.
2916 But C doesn't use these operations, so their optimizations are
2918 /* ??? For modulo, we don't actually need the highpart of the first product,
2919 the low part will do nicely. And for small divisors, the second multiply
2920 can also be a low-part only multiply or even be completely left out.
2921 E.g. to calculate the remainder of a division by 3 with a 32 bit
2922 multiply, multiply with 0x55555556 and extract the upper two bits;
2923 the result is exact for inputs up to 0x1fffffff.
2924 The input range can be reduced by using cross-sum rules.
2925 For odd divisors >= 3, the following table gives right shift counts
2926 so that if an number is shifted by an integer multiple of the given
2927 amount, the remainder stays the same:
2928 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
2929 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
2930 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
2931 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
2932 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
2934 Cross-sum rules for even numbers can be derived by leaving as many bits
2935 to the right alone as the divisor has zeros to the right.
2936 E.g. if x is an unsigned 32 bit number:
2937 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
2940 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
2943 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2945 enum tree_code code;
2946 enum machine_mode mode;
2947 rtx op0, op1, target;
2950 enum machine_mode compute_mode;
2952 rtx quotient = 0, remainder = 0;
2956 optab optab1, optab2;
2957 int op1_is_constant, op1_is_pow2;
2958 int max_cost, extra_cost;
2959 static HOST_WIDE_INT last_div_const = 0;
2961 op1_is_constant = GET_CODE (op1) == CONST_INT;
2962 op1_is_pow2 = (op1_is_constant
2963 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
2964 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1))))));
2967 This is the structure of expand_divmod:
2969 First comes code to fix up the operands so we can perform the operations
2970 correctly and efficiently.
2972 Second comes a switch statement with code specific for each rounding mode.
2973 For some special operands this code emits all RTL for the desired
2974 operation, for other cases, it generates only a quotient and stores it in
2975 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
2976 to indicate that it has not done anything.
2978 Last comes code that finishes the operation. If QUOTIENT is set and
2979 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
2980 QUOTIENT is not set, it is computed using trunc rounding.
2982 We try to generate special code for division and remainder when OP1 is a
2983 constant. If |OP1| = 2**n we can use shifts and some other fast
2984 operations. For other values of OP1, we compute a carefully selected
2985 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
2988 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
2989 half of the product. Different strategies for generating the product are
2990 implemented in expand_mult_highpart.
2992 If what we actually want is the remainder, we generate that by another
2993 by-constant multiplication and a subtraction. */
2995 /* We shouldn't be called with OP1 == const1_rtx, but some of the
2996 code below will malfunction if we are, so check here and handle
2997 the special case if so. */
2998 if (op1 == const1_rtx)
2999 return rem_flag ? const0_rtx : op0;
3001 /* When dividing by -1, we could get an overflow.
3002 negv_optab can handle overflows. */
3003 if (! unsignedp && op1 == constm1_rtx)
3007 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3008 ? negv_optab : neg_optab, op0, target, 0);
3012 /* Don't use the function value register as a target
3013 since we have to read it as well as write it,
3014 and function-inlining gets confused by this. */
3015 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3016 /* Don't clobber an operand while doing a multi-step calculation. */
3017 || ((rem_flag || op1_is_constant)
3018 && (reg_mentioned_p (target, op0)
3019 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
3020 || reg_mentioned_p (target, op1)
3021 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
3024 /* Get the mode in which to perform this computation. Normally it will
3025 be MODE, but sometimes we can't do the desired operation in MODE.
3026 If so, pick a wider mode in which we can do the operation. Convert
3027 to that mode at the start to avoid repeated conversions.
3029 First see what operations we need. These depend on the expression
3030 we are evaluating. (We assume that divxx3 insns exist under the
3031 same conditions that modxx3 insns and that these insns don't normally
3032 fail. If these assumptions are not correct, we may generate less
3033 efficient code in some cases.)
3035 Then see if we find a mode in which we can open-code that operation
3036 (either a division, modulus, or shift). Finally, check for the smallest
3037 mode for which we can do the operation with a library call. */
3039 /* We might want to refine this now that we have division-by-constant
3040 optimization. Since expand_mult_highpart tries so many variants, it is
3041 not straightforward to generalize this. Maybe we should make an array
3042 of possible modes in init_expmed? Save this for GCC 2.7. */
3044 optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3045 ? (unsignedp ? lshr_optab : ashr_optab)
3046 : (unsignedp ? udiv_optab : sdiv_optab));
3047 optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3049 : (unsignedp ? udivmod_optab : sdivmod_optab));
3051 for (compute_mode = mode; compute_mode != VOIDmode;
3052 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3053 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
3054 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
3057 if (compute_mode == VOIDmode)
3058 for (compute_mode = mode; compute_mode != VOIDmode;
3059 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3060 if (optab1->handlers[(int) compute_mode].libfunc
3061 || optab2->handlers[(int) compute_mode].libfunc)
3064 /* If we still couldn't find a mode, use MODE, but we'll probably abort
3066 if (compute_mode == VOIDmode)
3067 compute_mode = mode;
3069 if (target && GET_MODE (target) == compute_mode)
3072 tquotient = gen_reg_rtx (compute_mode);
3074 size = GET_MODE_BITSIZE (compute_mode);
3076 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3077 (mode), and thereby get better code when OP1 is a constant. Do that
3078 later. It will require going over all usages of SIZE below. */
3079 size = GET_MODE_BITSIZE (mode);
3082 /* Only deduct something for a REM if the last divide done was
3083 for a different constant. Then set the constant of the last
3085 max_cost = div_cost[(int) compute_mode]
3086 - (rem_flag && ! (last_div_const != 0 && op1_is_constant
3087 && INTVAL (op1) == last_div_const)
3088 ? mul_cost[(int) compute_mode] + add_cost : 0);
3090 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3092 /* Now convert to the best mode to use. */
3093 if (compute_mode != mode)
3095 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3096 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3098 /* convert_modes may have placed op1 into a register, so we
3099 must recompute the following. */
3100 op1_is_constant = GET_CODE (op1) == CONST_INT;
3101 op1_is_pow2 = (op1_is_constant
3102 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3104 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
3107 /* If one of the operands is a volatile MEM, copy it into a register. */
3109 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
3110 op0 = force_reg (compute_mode, op0);
3111 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
3112 op1 = force_reg (compute_mode, op1);
3114 /* If we need the remainder or if OP1 is constant, we need to
3115 put OP0 in a register in case it has any queued subexpressions. */
3116 if (rem_flag || op1_is_constant)
3117 op0 = force_reg (compute_mode, op0);
3119 last = get_last_insn ();
3121 /* Promote floor rounding to trunc rounding for unsigned operations. */
3124 if (code == FLOOR_DIV_EXPR)
3125 code = TRUNC_DIV_EXPR;
3126 if (code == FLOOR_MOD_EXPR)
3127 code = TRUNC_MOD_EXPR;
3128 if (code == EXACT_DIV_EXPR && op1_is_pow2)
3129 code = TRUNC_DIV_EXPR;
3132 if (op1 != const0_rtx)
3135 case TRUNC_MOD_EXPR:
3136 case TRUNC_DIV_EXPR:
3137 if (op1_is_constant)
3141 unsigned HOST_WIDE_INT mh, ml;
3142 int pre_shift, post_shift;
3144 unsigned HOST_WIDE_INT d = INTVAL (op1);
3146 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3148 pre_shift = floor_log2 (d);
3152 = expand_binop (compute_mode, and_optab, op0,
3153 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3157 return gen_lowpart (mode, remainder);
3159 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3160 build_int_2 (pre_shift, 0),
3163 else if (size <= HOST_BITS_PER_WIDE_INT)
3165 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
3167 /* Most significant bit of divisor is set; emit an scc
3169 quotient = emit_store_flag (tquotient, GEU, op0, op1,
3170 compute_mode, 1, 1);
3176 /* Find a suitable multiplier and right shift count
3177 instead of multiplying with D. */
3179 mh = choose_multiplier (d, size, size,
3180 &ml, &post_shift, &dummy);
3182 /* If the suggested multiplier is more than SIZE bits,
3183 we can do better for even divisors, using an
3184 initial right shift. */
3185 if (mh != 0 && (d & 1) == 0)
3187 pre_shift = floor_log2 (d & -d);
3188 mh = choose_multiplier (d >> pre_shift, size,
3190 &ml, &post_shift, &dummy);
3201 if (post_shift - 1 >= BITS_PER_WORD)
3204 extra_cost = (shift_cost[post_shift - 1]
3205 + shift_cost[1] + 2 * add_cost);
3206 t1 = expand_mult_highpart (compute_mode, op0, ml,
3208 max_cost - extra_cost);
3211 t2 = force_operand (gen_rtx_MINUS (compute_mode,
3214 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3215 build_int_2 (1, 0), NULL_RTX,1);
3216 t4 = force_operand (gen_rtx_PLUS (compute_mode,
3220 = expand_shift (RSHIFT_EXPR, compute_mode, t4,
3221 build_int_2 (post_shift - 1, 0),
3228 if (pre_shift >= BITS_PER_WORD
3229 || post_shift >= BITS_PER_WORD)
3232 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3233 build_int_2 (pre_shift, 0),
3235 extra_cost = (shift_cost[pre_shift]
3236 + shift_cost[post_shift]);
3237 t2 = expand_mult_highpart (compute_mode, t1, ml,
3239 max_cost - extra_cost);
3243 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3244 build_int_2 (post_shift, 0),
3249 else /* Too wide mode to use tricky code */
3252 insn = get_last_insn ();
3254 && (set = single_set (insn)) != 0
3255 && SET_DEST (set) == quotient)
3256 set_unique_reg_note (insn,
3258 gen_rtx_UDIV (compute_mode, op0, op1));
3260 else /* TRUNC_DIV, signed */
3262 unsigned HOST_WIDE_INT ml;
3263 int lgup, post_shift;
3264 HOST_WIDE_INT d = INTVAL (op1);
3265 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
3267 /* n rem d = n rem -d */
3268 if (rem_flag && d < 0)
3271 op1 = gen_int_mode (abs_d, compute_mode);
3277 quotient = expand_unop (compute_mode, neg_optab, op0,
3279 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
3281 /* This case is not handled correctly below. */
3282 quotient = emit_store_flag (tquotient, EQ, op0, op1,
3283 compute_mode, 1, 1);
3287 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
3288 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap)
3289 /* ??? The cheap metric is computed only for
3290 word_mode. If this operation is wider, this may
3291 not be so. Assume true if the optab has an
3292 expander for this mode. */
3293 && (((rem_flag ? smod_optab : sdiv_optab)
3294 ->handlers[(int) compute_mode].insn_code
3295 != CODE_FOR_nothing)
3296 || (sdivmod_optab->handlers[(int) compute_mode]
3297 .insn_code != CODE_FOR_nothing)))
3299 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
3301 lgup = floor_log2 (abs_d);
3302 if (BRANCH_COST < 1 || (abs_d != 2 && BRANCH_COST < 3))
3304 rtx label = gen_label_rtx ();
3307 t1 = copy_to_mode_reg (compute_mode, op0);
3308 do_cmp_and_jump (t1, const0_rtx, GE,
3309 compute_mode, label);
3310 expand_inc (t1, gen_int_mode (abs_d - 1,
3313 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3314 build_int_2 (lgup, 0),
3320 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3321 build_int_2 (size - 1, 0),
3323 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3324 build_int_2 (size - lgup, 0),
3326 t3 = force_operand (gen_rtx_PLUS (compute_mode,
3329 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3330 build_int_2 (lgup, 0),
3334 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
3338 insn = get_last_insn ();
3340 && (set = single_set (insn)) != 0
3341 && SET_DEST (set) == quotient
3342 && abs_d < ((unsigned HOST_WIDE_INT) 1
3343 << (HOST_BITS_PER_WIDE_INT - 1)))
3344 set_unique_reg_note (insn,
3346 gen_rtx_DIV (compute_mode,
3353 quotient = expand_unop (compute_mode, neg_optab,
3354 quotient, quotient, 0);
3357 else if (size <= HOST_BITS_PER_WIDE_INT)
3359 choose_multiplier (abs_d, size, size - 1,
3360 &ml, &post_shift, &lgup);
3361 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3365 if (post_shift >= BITS_PER_WORD
3366 || size - 1 >= BITS_PER_WORD)
3369 extra_cost = (shift_cost[post_shift]
3370 + shift_cost[size - 1] + add_cost);
3371 t1 = expand_mult_highpart (compute_mode, op0, ml,
3373 max_cost - extra_cost);
3376 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3377 build_int_2 (post_shift, 0), NULL_RTX, 0);
3378 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3379 build_int_2 (size - 1, 0), NULL_RTX, 0);
3382 = force_operand (gen_rtx_MINUS (compute_mode,
3387 = force_operand (gen_rtx_MINUS (compute_mode,
3395 if (post_shift >= BITS_PER_WORD
3396 || size - 1 >= BITS_PER_WORD)
3399 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3400 extra_cost = (shift_cost[post_shift]
3401 + shift_cost[size - 1] + 2 * add_cost);
3402 t1 = expand_mult_highpart (compute_mode, op0, ml,
3404 max_cost - extra_cost);
3407 t2 = force_operand (gen_rtx_PLUS (compute_mode,
3410 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3411 build_int_2 (post_shift, 0),
3413 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3414 build_int_2 (size - 1, 0),
3418 = force_operand (gen_rtx_MINUS (compute_mode,
3423 = force_operand (gen_rtx_MINUS (compute_mode,
3428 else /* Too wide mode to use tricky code */
3431 insn = get_last_insn ();
3433 && (set = single_set (insn)) != 0
3434 && SET_DEST (set) == quotient)
3435 set_unique_reg_note (insn,
3437 gen_rtx_DIV (compute_mode, op0, op1));
3442 delete_insns_since (last);
3445 case FLOOR_DIV_EXPR:
3446 case FLOOR_MOD_EXPR:
3447 /* We will come here only for signed operations. */
3448 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3450 unsigned HOST_WIDE_INT mh, ml;
3451 int pre_shift, lgup, post_shift;
3452 HOST_WIDE_INT d = INTVAL (op1);
3456 /* We could just as easily deal with negative constants here,
3457 but it does not seem worth the trouble for GCC 2.6. */
3458 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3460 pre_shift = floor_log2 (d);
3463 remainder = expand_binop (compute_mode, and_optab, op0,
3464 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3465 remainder, 0, OPTAB_LIB_WIDEN);
3467 return gen_lowpart (mode, remainder);
3469 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3470 build_int_2 (pre_shift, 0),
3477 mh = choose_multiplier (d, size, size - 1,
3478 &ml, &post_shift, &lgup);
3482 if (post_shift < BITS_PER_WORD
3483 && size - 1 < BITS_PER_WORD)
3485 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3486 build_int_2 (size - 1, 0),
3488 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3489 NULL_RTX, 0, OPTAB_WIDEN);
3490 extra_cost = (shift_cost[post_shift]
3491 + shift_cost[size - 1] + 2 * add_cost);
3492 t3 = expand_mult_highpart (compute_mode, t2, ml,
3494 max_cost - extra_cost);
3497 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3498 build_int_2 (post_shift, 0),
3500 quotient = expand_binop (compute_mode, xor_optab,
3501 t4, t1, tquotient, 0,
3509 rtx nsign, t1, t2, t3, t4;
3510 t1 = force_operand (gen_rtx_PLUS (compute_mode,
3511 op0, constm1_rtx), NULL_RTX);
3512 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3514 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3515 build_int_2 (size - 1, 0), NULL_RTX, 0);
3516 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
3518 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3523 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3525 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3534 delete_insns_since (last);
3536 /* Try using an instruction that produces both the quotient and
3537 remainder, using truncation. We can easily compensate the quotient
3538 or remainder to get floor rounding, once we have the remainder.
3539 Notice that we compute also the final remainder value here,
3540 and return the result right away. */
3541 if (target == 0 || GET_MODE (target) != compute_mode)
3542 target = gen_reg_rtx (compute_mode);
3547 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3548 quotient = gen_reg_rtx (compute_mode);
3553 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3554 remainder = gen_reg_rtx (compute_mode);
3557 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3558 quotient, remainder, 0))
3560 /* This could be computed with a branch-less sequence.
3561 Save that for later. */
3563 rtx label = gen_label_rtx ();
3564 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
3565 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3566 NULL_RTX, 0, OPTAB_WIDEN);
3567 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
3568 expand_dec (quotient, const1_rtx);
3569 expand_inc (remainder, op1);
3571 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3574 /* No luck with division elimination or divmod. Have to do it
3575 by conditionally adjusting op0 *and* the result. */
3577 rtx label1, label2, label3, label4, label5;
3581 quotient = gen_reg_rtx (compute_mode);
3582 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3583 label1 = gen_label_rtx ();
3584 label2 = gen_label_rtx ();
3585 label3 = gen_label_rtx ();
3586 label4 = gen_label_rtx ();
3587 label5 = gen_label_rtx ();
3588 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3589 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
3590 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3591 quotient, 0, OPTAB_LIB_WIDEN);
3592 if (tem != quotient)
3593 emit_move_insn (quotient, tem);
3594 emit_jump_insn (gen_jump (label5));
3596 emit_label (label1);
3597 expand_inc (adjusted_op0, const1_rtx);
3598 emit_jump_insn (gen_jump (label4));
3600 emit_label (label2);
3601 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
3602 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3603 quotient, 0, OPTAB_LIB_WIDEN);
3604 if (tem != quotient)
3605 emit_move_insn (quotient, tem);
3606 emit_jump_insn (gen_jump (label5));
3608 emit_label (label3);
3609 expand_dec (adjusted_op0, const1_rtx);
3610 emit_label (label4);
3611 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3612 quotient, 0, OPTAB_LIB_WIDEN);
3613 if (tem != quotient)
3614 emit_move_insn (quotient, tem);
3615 expand_dec (quotient, const1_rtx);
3616 emit_label (label5);
3624 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3627 unsigned HOST_WIDE_INT d = INTVAL (op1);
3628 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3629 build_int_2 (floor_log2 (d), 0),
3631 t2 = expand_binop (compute_mode, and_optab, op0,
3633 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3634 t3 = gen_reg_rtx (compute_mode);
3635 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3636 compute_mode, 1, 1);
3640 lab = gen_label_rtx ();
3641 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3642 expand_inc (t1, const1_rtx);
3647 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3653 /* Try using an instruction that produces both the quotient and
3654 remainder, using truncation. We can easily compensate the
3655 quotient or remainder to get ceiling rounding, once we have the
3656 remainder. Notice that we compute also the final remainder
3657 value here, and return the result right away. */
3658 if (target == 0 || GET_MODE (target) != compute_mode)
3659 target = gen_reg_rtx (compute_mode);
3663 remainder = (GET_CODE (target) == REG
3664 ? target : gen_reg_rtx (compute_mode));
3665 quotient = gen_reg_rtx (compute_mode);
3669 quotient = (GET_CODE (target) == REG
3670 ? target : gen_reg_rtx (compute_mode));
3671 remainder = gen_reg_rtx (compute_mode);
3674 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3677 /* This could be computed with a branch-less sequence.
3678 Save that for later. */
3679 rtx label = gen_label_rtx ();
3680 do_cmp_and_jump (remainder, const0_rtx, EQ,
3681 compute_mode, label);
3682 expand_inc (quotient, const1_rtx);
3683 expand_dec (remainder, op1);
3685 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3688 /* No luck with division elimination or divmod. Have to do it
3689 by conditionally adjusting op0 *and* the result. */
3692 rtx adjusted_op0, tem;
3694 quotient = gen_reg_rtx (compute_mode);
3695 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3696 label1 = gen_label_rtx ();
3697 label2 = gen_label_rtx ();
3698 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
3699 compute_mode, label1);
3700 emit_move_insn (quotient, const0_rtx);
3701 emit_jump_insn (gen_jump (label2));
3703 emit_label (label1);
3704 expand_dec (adjusted_op0, const1_rtx);
3705 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3706 quotient, 1, OPTAB_LIB_WIDEN);
3707 if (tem != quotient)
3708 emit_move_insn (quotient, tem);
3709 expand_inc (quotient, const1_rtx);
3710 emit_label (label2);
3715 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3716 && INTVAL (op1) >= 0)
3718 /* This is extremely similar to the code for the unsigned case
3719 above. For 2.7 we should merge these variants, but for
3720 2.6.1 I don't want to touch the code for unsigned since that
3721 get used in C. The signed case will only be used by other
3725 unsigned HOST_WIDE_INT d = INTVAL (op1);
3726 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3727 build_int_2 (floor_log2 (d), 0),
3729 t2 = expand_binop (compute_mode, and_optab, op0,
3731 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3732 t3 = gen_reg_rtx (compute_mode);
3733 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3734 compute_mode, 1, 1);
3738 lab = gen_label_rtx ();
3739 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
3740 expand_inc (t1, const1_rtx);
3745 quotient = force_operand (gen_rtx_PLUS (compute_mode,
3751 /* Try using an instruction that produces both the quotient and
3752 remainder, using truncation. We can easily compensate the
3753 quotient or remainder to get ceiling rounding, once we have the
3754 remainder. Notice that we compute also the final remainder
3755 value here, and return the result right away. */
3756 if (target == 0 || GET_MODE (target) != compute_mode)
3757 target = gen_reg_rtx (compute_mode);
3760 remainder= (GET_CODE (target) == REG
3761 ? target : gen_reg_rtx (compute_mode));
3762 quotient = gen_reg_rtx (compute_mode);
3766 quotient = (GET_CODE (target) == REG
3767 ? target : gen_reg_rtx (compute_mode));
3768 remainder = gen_reg_rtx (compute_mode);
3771 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3774 /* This could be computed with a branch-less sequence.
3775 Save that for later. */
3777 rtx label = gen_label_rtx ();
3778 do_cmp_and_jump (remainder, const0_rtx, EQ,
3779 compute_mode, label);
3780 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3781 NULL_RTX, 0, OPTAB_WIDEN);
3782 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
3783 expand_inc (quotient, const1_rtx);
3784 expand_dec (remainder, op1);
3786 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3789 /* No luck with division elimination or divmod. Have to do it
3790 by conditionally adjusting op0 *and* the result. */
3792 rtx label1, label2, label3, label4, label5;
3796 quotient = gen_reg_rtx (compute_mode);
3797 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3798 label1 = gen_label_rtx ();
3799 label2 = gen_label_rtx ();
3800 label3 = gen_label_rtx ();
3801 label4 = gen_label_rtx ();
3802 label5 = gen_label_rtx ();
3803 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
3804 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
3805 compute_mode, label1);
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 (label1);
3813 expand_dec (adjusted_op0, const1_rtx);
3814 emit_jump_insn (gen_jump (label4));
3816 emit_label (label2);
3817 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
3818 compute_mode, label3);
3819 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3820 quotient, 0, OPTAB_LIB_WIDEN);
3821 if (tem != quotient)
3822 emit_move_insn (quotient, tem);
3823 emit_jump_insn (gen_jump (label5));
3825 emit_label (label3);
3826 expand_inc (adjusted_op0, const1_rtx);
3827 emit_label (label4);
3828 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3829 quotient, 0, OPTAB_LIB_WIDEN);
3830 if (tem != quotient)
3831 emit_move_insn (quotient, tem);
3832 expand_inc (quotient, const1_rtx);
3833 emit_label (label5);
3838 case EXACT_DIV_EXPR:
3839 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3841 HOST_WIDE_INT d = INTVAL (op1);
3842 unsigned HOST_WIDE_INT ml;
3846 pre_shift = floor_log2 (d & -d);
3847 ml = invert_mod2n (d >> pre_shift, size);
3848 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3849 build_int_2 (pre_shift, 0), NULL_RTX, unsignedp);
3850 quotient = expand_mult (compute_mode, t1,
3851 gen_int_mode (ml, compute_mode),
3854 insn = get_last_insn ();
3855 set_unique_reg_note (insn,
3857 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
3863 case ROUND_DIV_EXPR:
3864 case ROUND_MOD_EXPR:
3869 label = gen_label_rtx ();
3870 quotient = gen_reg_rtx (compute_mode);
3871 remainder = gen_reg_rtx (compute_mode);
3872 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3875 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3876 quotient, 1, OPTAB_LIB_WIDEN);
3877 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3878 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3879 remainder, 1, OPTAB_LIB_WIDEN);
3881 tem = plus_constant (op1, -1);
3882 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3883 build_int_2 (1, 0), NULL_RTX, 1);
3884 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
3885 expand_inc (quotient, const1_rtx);
3886 expand_dec (remainder, op1);
3891 rtx abs_rem, abs_op1, tem, mask;
3893 label = gen_label_rtx ();
3894 quotient = gen_reg_rtx (compute_mode);
3895 remainder = gen_reg_rtx (compute_mode);
3896 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3899 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3900 quotient, 0, OPTAB_LIB_WIDEN);
3901 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3902 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3903 remainder, 0, OPTAB_LIB_WIDEN);
3905 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
3906 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
3907 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3908 build_int_2 (1, 0), NULL_RTX, 1);
3909 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
3910 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3911 NULL_RTX, 0, OPTAB_WIDEN);
3912 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3913 build_int_2 (size - 1, 0), NULL_RTX, 0);
3914 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3915 NULL_RTX, 0, OPTAB_WIDEN);
3916 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3917 NULL_RTX, 0, OPTAB_WIDEN);
3918 expand_inc (quotient, tem);
3919 tem = expand_binop (compute_mode, xor_optab, mask, op1,
3920 NULL_RTX, 0, OPTAB_WIDEN);
3921 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3922 NULL_RTX, 0, OPTAB_WIDEN);
3923 expand_dec (remainder, tem);
3926 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3934 if (target && GET_MODE (target) != compute_mode)
3939 /* Try to produce the remainder without producing the quotient.
3940 If we seem to have a divmod pattern that does not require widening,
3941 don't try widening here. We should really have an WIDEN argument
3942 to expand_twoval_binop, since what we'd really like to do here is
3943 1) try a mod insn in compute_mode
3944 2) try a divmod insn in compute_mode
3945 3) try a div insn in compute_mode and multiply-subtract to get
3947 4) try the same things with widening allowed. */
3949 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3952 ((optab2->handlers[(int) compute_mode].insn_code
3953 != CODE_FOR_nothing)
3954 ? OPTAB_DIRECT : OPTAB_WIDEN));
3957 /* No luck there. Can we do remainder and divide at once
3958 without a library call? */
3959 remainder = gen_reg_rtx (compute_mode);
3960 if (! expand_twoval_binop ((unsignedp
3964 NULL_RTX, remainder, unsignedp))
3969 return gen_lowpart (mode, remainder);
3972 /* Produce the quotient. Try a quotient insn, but not a library call.
3973 If we have a divmod in this mode, use it in preference to widening
3974 the div (for this test we assume it will not fail). Note that optab2
3975 is set to the one of the two optabs that the call below will use. */
3977 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
3978 op0, op1, rem_flag ? NULL_RTX : target,
3980 ((optab2->handlers[(int) compute_mode].insn_code
3981 != CODE_FOR_nothing)
3982 ? OPTAB_DIRECT : OPTAB_WIDEN));
3986 /* No luck there. Try a quotient-and-remainder insn,
3987 keeping the quotient alone. */
3988 quotient = gen_reg_rtx (compute_mode);
3989 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
3991 quotient, NULL_RTX, unsignedp))
3995 /* Still no luck. If we are not computing the remainder,
3996 use a library call for the quotient. */
3997 quotient = sign_expand_binop (compute_mode,
3998 udiv_optab, sdiv_optab,
4000 unsignedp, OPTAB_LIB_WIDEN);
4007 if (target && GET_MODE (target) != compute_mode)
4011 /* No divide instruction either. Use library for remainder. */
4012 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4014 unsignedp, OPTAB_LIB_WIDEN);
4017 /* We divided. Now finish doing X - Y * (X / Y). */
4018 remainder = expand_mult (compute_mode, quotient, op1,
4019 NULL_RTX, unsignedp);
4020 remainder = expand_binop (compute_mode, sub_optab, op0,
4021 remainder, target, unsignedp,
4026 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4029 /* Return a tree node with data type TYPE, describing the value of X.
4030 Usually this is an RTL_EXPR, if there is no obvious better choice.
4031 X may be an expression, however we only support those expressions
4032 generated by loop.c. */
4041 switch (GET_CODE (x))
4044 t = build_int_2 (INTVAL (x),
4045 (TREE_UNSIGNED (type)
4046 && (GET_MODE_BITSIZE (TYPE_MODE (type)) < HOST_BITS_PER_WIDE_INT))
4047 || INTVAL (x) >= 0 ? 0 : -1);
4048 TREE_TYPE (t) = type;
4052 if (GET_MODE (x) == VOIDmode)
4054 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4055 TREE_TYPE (t) = type;
4061 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4062 t = build_real (type, d);
4073 units = CONST_VECTOR_NUNITS (x);
4075 /* Build a tree with vector elements. */
4076 for (i = units - 1; i >= 0; --i)
4078 elt = CONST_VECTOR_ELT (x, i);
4079 t = tree_cons (NULL_TREE, make_tree (type, elt), t);
4082 return build_vector (type, t);
4086 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4087 make_tree (type, XEXP (x, 1))));
4090 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
4091 make_tree (type, XEXP (x, 1))));
4094 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
4097 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
4098 make_tree (type, XEXP (x, 1))));
4101 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
4102 make_tree (type, XEXP (x, 1))));
4105 t = (*lang_hooks.types.unsigned_type) (type);
4106 return fold (convert (type,
4107 build (RSHIFT_EXPR, t,
4108 make_tree (t, XEXP (x, 0)),
4109 make_tree (type, XEXP (x, 1)))));
4112 t = (*lang_hooks.types.signed_type) (type);
4113 return fold (convert (type,
4114 build (RSHIFT_EXPR, t,
4115 make_tree (t, XEXP (x, 0)),
4116 make_tree (type, XEXP (x, 1)))));
4119 if (TREE_CODE (type) != REAL_TYPE)
4120 t = (*lang_hooks.types.signed_type) (type);
4124 return fold (convert (type,
4125 build (TRUNC_DIV_EXPR, t,
4126 make_tree (t, XEXP (x, 0)),
4127 make_tree (t, XEXP (x, 1)))));
4129 t = (*lang_hooks.types.unsigned_type) (type);
4130 return fold (convert (type,
4131 build (TRUNC_DIV_EXPR, t,
4132 make_tree (t, XEXP (x, 0)),
4133 make_tree (t, XEXP (x, 1)))));
4137 t = (*lang_hooks.types.type_for_mode) (GET_MODE (XEXP (x, 0)),
4138 GET_CODE (x) == ZERO_EXTEND);
4139 return fold (convert (type, make_tree (t, XEXP (x, 0))));
4142 t = make_node (RTL_EXPR);
4143 TREE_TYPE (t) = type;
4145 #ifdef POINTERS_EXTEND_UNSIGNED
4146 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
4147 ptr_mode. So convert. */
4148 if (POINTER_TYPE_P (type) && GET_MODE (x) != TYPE_MODE (type))
4149 x = convert_memory_address (TYPE_MODE (type), x);
4152 RTL_EXPR_RTL (t) = x;
4153 /* There are no insns to be output
4154 when this rtl_expr is used. */
4155 RTL_EXPR_SEQUENCE (t) = 0;
4160 /* Check whether the multiplication X * MULT + ADD overflows.
4161 X, MULT and ADD must be CONST_*.
4162 MODE is the machine mode for the computation.
4163 X and MULT must have mode MODE. ADD may have a different mode.
4164 So can X (defaults to same as MODE).
4165 UNSIGNEDP is nonzero to do unsigned multiplication. */
4168 const_mult_add_overflow_p (x, mult, add, mode, unsignedp)
4170 enum machine_mode mode;
4173 tree type, mult_type, add_type, result;
4175 type = (*lang_hooks.types.type_for_mode) (mode, unsignedp);
4177 /* In order to get a proper overflow indication from an unsigned
4178 type, we have to pretend that it's a sizetype. */
4182 mult_type = copy_node (type);
4183 TYPE_IS_SIZETYPE (mult_type) = 1;
4186 add_type = (GET_MODE (add) == VOIDmode ? mult_type
4187 : (*lang_hooks.types.type_for_mode) (GET_MODE (add), unsignedp));
4189 result = fold (build (PLUS_EXPR, mult_type,
4190 fold (build (MULT_EXPR, mult_type,
4191 make_tree (mult_type, x),
4192 make_tree (mult_type, mult))),
4193 make_tree (add_type, add)));
4195 return TREE_CONSTANT_OVERFLOW (result);
4198 /* Return an rtx representing the value of X * MULT + ADD.
4199 TARGET is a suggestion for where to store the result (an rtx).
4200 MODE is the machine mode for the computation.
4201 X and MULT must have mode MODE. ADD may have a different mode.
4202 So can X (defaults to same as MODE).
4203 UNSIGNEDP is nonzero to do unsigned multiplication.
4204 This may emit insns. */
4207 expand_mult_add (x, target, mult, add, mode, unsignedp)
4208 rtx x, target, mult, add;
4209 enum machine_mode mode;
4212 tree type = (*lang_hooks.types.type_for_mode) (mode, unsignedp);
4213 tree add_type = (GET_MODE (add) == VOIDmode
4214 ? type: (*lang_hooks.types.type_for_mode) (GET_MODE (add),
4216 tree result = fold (build (PLUS_EXPR, type,
4217 fold (build (MULT_EXPR, type,
4218 make_tree (type, x),
4219 make_tree (type, mult))),
4220 make_tree (add_type, add)));
4222 return expand_expr (result, target, VOIDmode, 0);
4225 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
4226 and returning TARGET.
4228 If TARGET is 0, a pseudo-register or constant is returned. */
4231 expand_and (mode, op0, op1, target)
4232 enum machine_mode mode;
4233 rtx op0, op1, target;
4237 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
4238 tem = simplify_binary_operation (AND, mode, op0, op1);
4240 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
4244 else if (tem != target)
4245 emit_move_insn (target, tem);
4249 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
4250 and storing in TARGET. Normally return TARGET.
4251 Return 0 if that cannot be done.
4253 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
4254 it is VOIDmode, they cannot both be CONST_INT.
4256 UNSIGNEDP is for the case where we have to widen the operands
4257 to perform the operation. It says to use zero-extension.
4259 NORMALIZEP is 1 if we should convert the result to be either zero
4260 or one. Normalize is -1 if we should convert the result to be
4261 either zero or -1. If NORMALIZEP is zero, the result will be left
4262 "raw" out of the scc insn. */
4265 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
4269 enum machine_mode mode;
4274 enum insn_code icode;
4275 enum machine_mode compare_mode;
4276 enum machine_mode target_mode = GET_MODE (target);
4278 rtx last = get_last_insn ();
4279 rtx pattern, comparison;
4281 /* ??? Ok to do this and then fail? */
4282 op0 = protect_from_queue (op0, 0);
4283 op1 = protect_from_queue (op1, 0);
4286 code = unsigned_condition (code);
4288 /* If one operand is constant, make it the second one. Only do this
4289 if the other operand is not constant as well. */
4291 if (swap_commutative_operands_p (op0, op1))
4296 code = swap_condition (code);
4299 if (mode == VOIDmode)
4300 mode = GET_MODE (op0);
4302 /* For some comparisons with 1 and -1, we can convert this to
4303 comparisons with zero. This will often produce more opportunities for
4304 store-flag insns. */
4309 if (op1 == const1_rtx)
4310 op1 = const0_rtx, code = LE;
4313 if (op1 == constm1_rtx)
4314 op1 = const0_rtx, code = LT;
4317 if (op1 == const1_rtx)
4318 op1 = const0_rtx, code = GT;
4321 if (op1 == constm1_rtx)
4322 op1 = const0_rtx, code = GE;
4325 if (op1 == const1_rtx)
4326 op1 = const0_rtx, code = NE;
4329 if (op1 == const1_rtx)
4330 op1 = const0_rtx, code = EQ;
4336 /* If we are comparing a double-word integer with zero, we can convert
4337 the comparison into one involving a single word. */
4338 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
4339 && GET_MODE_CLASS (mode) == MODE_INT
4340 && op1 == const0_rtx
4341 && (GET_CODE (op0) != MEM || ! MEM_VOLATILE_P (op0)))
4343 if (code == EQ || code == NE)
4345 /* Do a logical OR of the two words and compare the result. */
4346 rtx op0h = gen_highpart (word_mode, op0);
4347 rtx op0l = gen_lowpart (word_mode, op0);
4348 rtx op0both = expand_binop (word_mode, ior_optab, op0h, op0l,
4349 NULL_RTX, unsignedp, OPTAB_DIRECT);
4351 return emit_store_flag (target, code, op0both, op1, word_mode,
4352 unsignedp, normalizep);
4354 else if (code == LT || code == GE)
4355 /* If testing the sign bit, can just test on high word. */
4356 return emit_store_flag (target, code, gen_highpart (word_mode, op0),
4357 op1, word_mode, unsignedp, normalizep);
4360 /* From now on, we won't change CODE, so set ICODE now. */
4361 icode = setcc_gen_code[(int) code];
4363 /* If this is A < 0 or A >= 0, we can do this by taking the ones
4364 complement of A (for GE) and shifting the sign bit to the low bit. */
4365 if (op1 == const0_rtx && (code == LT || code == GE)
4366 && GET_MODE_CLASS (mode) == MODE_INT
4367 && (normalizep || STORE_FLAG_VALUE == 1
4368 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4369 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4370 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
4374 /* If the result is to be wider than OP0, it is best to convert it
4375 first. If it is to be narrower, it is *incorrect* to convert it
4377 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
4379 op0 = protect_from_queue (op0, 0);
4380 op0 = convert_modes (target_mode, mode, op0, 0);
4384 if (target_mode != mode)
4388 op0 = expand_unop (mode, one_cmpl_optab, op0,
4389 ((STORE_FLAG_VALUE == 1 || normalizep)
4390 ? 0 : subtarget), 0);
4392 if (STORE_FLAG_VALUE == 1 || normalizep)
4393 /* If we are supposed to produce a 0/1 value, we want to do
4394 a logical shift from the sign bit to the low-order bit; for
4395 a -1/0 value, we do an arithmetic shift. */
4396 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
4397 size_int (GET_MODE_BITSIZE (mode) - 1),
4398 subtarget, normalizep != -1);
4400 if (mode != target_mode)
4401 op0 = convert_modes (target_mode, mode, op0, 0);
4406 if (icode != CODE_FOR_nothing)
4408 insn_operand_predicate_fn pred;
4410 /* We think we may be able to do this with a scc insn. Emit the
4411 comparison and then the scc insn.
4413 compare_from_rtx may call emit_queue, which would be deleted below
4414 if the scc insn fails. So call it ourselves before setting LAST.
4415 Likewise for do_pending_stack_adjust. */
4418 do_pending_stack_adjust ();
4419 last = get_last_insn ();
4422 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX);
4423 if (GET_CODE (comparison) == CONST_INT)
4424 return (comparison == const0_rtx ? const0_rtx
4425 : normalizep == 1 ? const1_rtx
4426 : normalizep == -1 ? constm1_rtx
4429 /* The code of COMPARISON may not match CODE if compare_from_rtx
4430 decided to swap its operands and reverse the original code.
4432 We know that compare_from_rtx returns either a CONST_INT or
4433 a new comparison code, so it is safe to just extract the
4434 code from COMPARISON. */
4435 code = GET_CODE (comparison);
4437 /* Get a reference to the target in the proper mode for this insn. */
4438 compare_mode = insn_data[(int) icode].operand[0].mode;
4440 pred = insn_data[(int) icode].operand[0].predicate;
4441 if (preserve_subexpressions_p ()
4442 || ! (*pred) (subtarget, compare_mode))
4443 subtarget = gen_reg_rtx (compare_mode);
4445 pattern = GEN_FCN (icode) (subtarget);
4448 emit_insn (pattern);
4450 /* If we are converting to a wider mode, first convert to
4451 TARGET_MODE, then normalize. This produces better combining
4452 opportunities on machines that have a SIGN_EXTRACT when we are
4453 testing a single bit. This mostly benefits the 68k.
4455 If STORE_FLAG_VALUE does not have the sign bit set when
4456 interpreted in COMPARE_MODE, we can do this conversion as
4457 unsigned, which is usually more efficient. */
4458 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
4460 convert_move (target, subtarget,
4461 (GET_MODE_BITSIZE (compare_mode)
4462 <= HOST_BITS_PER_WIDE_INT)
4463 && 0 == (STORE_FLAG_VALUE
4464 & ((HOST_WIDE_INT) 1
4465 << (GET_MODE_BITSIZE (compare_mode) -1))));
4467 compare_mode = target_mode;
4472 /* If we want to keep subexpressions around, don't reuse our
4475 if (preserve_subexpressions_p ())
4478 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
4479 we don't have to do anything. */
4480 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
4482 /* STORE_FLAG_VALUE might be the most negative number, so write
4483 the comparison this way to avoid a compiler-time warning. */
4484 else if (- normalizep == STORE_FLAG_VALUE)
4485 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
4487 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
4488 makes it hard to use a value of just the sign bit due to
4489 ANSI integer constant typing rules. */
4490 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
4491 && (STORE_FLAG_VALUE
4492 & ((HOST_WIDE_INT) 1
4493 << (GET_MODE_BITSIZE (compare_mode) - 1))))
4494 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
4495 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4496 subtarget, normalizep == 1);
4497 else if (STORE_FLAG_VALUE & 1)
4499 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget);
4500 if (normalizep == -1)
4501 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4506 /* If we were converting to a smaller mode, do the
4508 if (target_mode != compare_mode)
4510 convert_move (target, op0, 0);
4518 delete_insns_since (last);
4520 /* If expensive optimizations, use different pseudo registers for each
4521 insn, instead of reusing the same pseudo. This leads to better CSE,
4522 but slows down the compiler, since there are more pseudos */
4523 subtarget = (!flag_expensive_optimizations
4524 && (target_mode == mode)) ? target : NULL_RTX;
4526 /* If we reached here, we can't do this with a scc insn. However, there
4527 are some comparisons that can be done directly. For example, if
4528 this is an equality comparison of integers, we can try to exclusive-or
4529 (or subtract) the two operands and use a recursive call to try the
4530 comparison with zero. Don't do any of these cases if branches are
4534 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4535 && op1 != const0_rtx)
4537 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4541 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4544 tem = emit_store_flag (target, code, tem, const0_rtx,
4545 mode, unsignedp, normalizep);
4547 delete_insns_since (last);
4551 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4552 the constant zero. Reject all other comparisons at this point. Only
4553 do LE and GT if branches are expensive since they are expensive on
4554 2-operand machines. */
4556 if (BRANCH_COST == 0
4557 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4558 || (code != EQ && code != NE
4559 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4562 /* See what we need to return. We can only return a 1, -1, or the
4565 if (normalizep == 0)
4567 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4568 normalizep = STORE_FLAG_VALUE;
4570 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4571 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
4572 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4578 /* Try to put the result of the comparison in the sign bit. Assume we can't
4579 do the necessary operation below. */
4583 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4584 the sign bit set. */
4588 /* This is destructive, so SUBTARGET can't be OP0. */
4589 if (rtx_equal_p (subtarget, op0))
4592 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4595 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4599 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4600 number of bits in the mode of OP0, minus one. */
4604 if (rtx_equal_p (subtarget, op0))
4607 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4608 size_int (GET_MODE_BITSIZE (mode) - 1),
4610 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4614 if (code == EQ || code == NE)
4616 /* For EQ or NE, one way to do the comparison is to apply an operation
4617 that converts the operand into a positive number if it is nonzero
4618 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4619 for NE we negate. This puts the result in the sign bit. Then we
4620 normalize with a shift, if needed.
4622 Two operations that can do the above actions are ABS and FFS, so try
4623 them. If that doesn't work, and MODE is smaller than a full word,
4624 we can use zero-extension to the wider mode (an unsigned conversion)
4625 as the operation. */
4627 /* Note that ABS doesn't yield a positive number for INT_MIN, but
4628 that is compensated by the subsequent overflow when subtracting
4631 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4632 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4633 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4634 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4635 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4637 op0 = protect_from_queue (op0, 0);
4638 tem = convert_modes (word_mode, mode, op0, 1);
4645 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4648 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4651 /* If we couldn't do it that way, for NE we can "or" the two's complement
4652 of the value with itself. For EQ, we take the one's complement of
4653 that "or", which is an extra insn, so we only handle EQ if branches
4656 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4658 if (rtx_equal_p (subtarget, op0))
4661 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4662 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4665 if (tem && code == EQ)
4666 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4670 if (tem && normalizep)
4671 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4672 size_int (GET_MODE_BITSIZE (mode) - 1),
4673 subtarget, normalizep == 1);
4677 if (GET_MODE (tem) != target_mode)
4679 convert_move (target, tem, 0);
4682 else if (!subtarget)
4684 emit_move_insn (target, tem);
4689 delete_insns_since (last);
4694 /* Like emit_store_flag, but always succeeds. */
4697 emit_store_flag_force (target, code, op0, op1, mode, unsignedp, normalizep)
4701 enum machine_mode mode;
4707 /* First see if emit_store_flag can do the job. */
4708 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
4712 if (normalizep == 0)
4715 /* If this failed, we have to do this with set/compare/jump/set code. */
4717 if (GET_CODE (target) != REG
4718 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
4719 target = gen_reg_rtx (GET_MODE (target));
4721 emit_move_insn (target, const1_rtx);
4722 label = gen_label_rtx ();
4723 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
4726 emit_move_insn (target, const0_rtx);
4732 /* Perform possibly multi-word comparison and conditional jump to LABEL
4733 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE
4735 The algorithm is based on the code in expr.c:do_jump.
4737 Note that this does not perform a general comparison. Only variants
4738 generated within expmed.c are correctly handled, others abort (but could
4739 be handled if needed). */
4742 do_cmp_and_jump (arg1, arg2, op, mode, label)
4743 rtx arg1, arg2, label;
4745 enum machine_mode mode;
4747 /* If this mode is an integer too wide to compare properly,
4748 compare word by word. Rely on cse to optimize constant cases. */
4750 if (GET_MODE_CLASS (mode) == MODE_INT
4751 && ! can_compare_p (op, mode, ccp_jump))
4753 rtx label2 = gen_label_rtx ();
4758 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label);
4762 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2);
4766 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label);
4770 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label);
4774 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2);
4777 /* do_jump_by_parts_equality_rtx compares with zero. Luckily
4778 that's the only equality operations we do */
4780 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4782 do_jump_by_parts_equality_rtx (arg1, label2, label);
4786 if (arg2 != const0_rtx || mode != GET_MODE(arg1))
4788 do_jump_by_parts_equality_rtx (arg1, label, label2);
4795 emit_label (label2);
4798 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label);