1 /* Medium-level subroutines: convert bit-field store and extract
2 and shifts, multiplies and divides to rtl instructions.
3 Copyright (C) 1987, 88, 89, 92, 93, 94, 1995 Free Software Foundation, Inc.
5 This file is part of GNU CC.
7 GNU CC is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GNU CC is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GNU CC; see the file COPYING. If not, write to
19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
26 #include "insn-flags.h"
27 #include "insn-codes.h"
28 #include "insn-config.h"
33 static void store_fixed_bit_field PROTO((rtx, int, int, int, rtx, int));
34 static void store_split_bit_field PROTO((rtx, int, int, rtx, int));
35 static rtx extract_fixed_bit_field PROTO((enum machine_mode, rtx, int,
36 int, int, rtx, int, int));
37 static rtx mask_rtx PROTO((enum machine_mode, int,
39 static rtx lshift_value PROTO((enum machine_mode, rtx,
41 static rtx extract_split_bit_field PROTO((rtx, int, int, int, int));
43 #define CEIL(x,y) (((x) + (y) - 1) / (y))
45 /* Non-zero means divides or modulus operations are relatively cheap for
46 powers of two, so don't use branches; emit the operation instead.
47 Usually, this will mean that the MD file will emit non-branch
50 static int sdiv_pow2_cheap, smod_pow2_cheap;
52 #ifndef SLOW_UNALIGNED_ACCESS
53 #define SLOW_UNALIGNED_ACCESS STRICT_ALIGNMENT
56 /* For compilers that support multiple targets with different word sizes,
57 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example
58 is the H8/300(H) compiler. */
60 #ifndef MAX_BITS_PER_WORD
61 #define MAX_BITS_PER_WORD BITS_PER_WORD
64 /* Cost of various pieces of RTL. Note that some of these are indexed by shift count,
66 static int add_cost, negate_cost, zero_cost;
67 static int shift_cost[MAX_BITS_PER_WORD];
68 static int shiftadd_cost[MAX_BITS_PER_WORD];
69 static int shiftsub_cost[MAX_BITS_PER_WORD];
70 static int mul_cost[NUM_MACHINE_MODES];
71 static int div_cost[NUM_MACHINE_MODES];
72 static int mul_widen_cost[NUM_MACHINE_MODES];
73 static int mul_highpart_cost[NUM_MACHINE_MODES];
79 /* This is "some random pseudo register" for purposes of calling recog
80 to see what insns exist. */
81 rtx reg = gen_rtx (REG, word_mode, 10000);
82 rtx shift_insn, shiftadd_insn, shiftsub_insn;
85 enum machine_mode mode, wider_mode;
89 /* Since we are on the permanent obstack, we must be sure we save this
90 spot AFTER we call start_sequence, since it will reuse the rtl it
93 free_point = (char *) oballoc (0);
95 zero_cost = rtx_cost (const0_rtx, 0);
96 add_cost = rtx_cost (gen_rtx (PLUS, word_mode, reg, reg), SET);
98 shift_insn = emit_insn (gen_rtx (SET, VOIDmode, reg,
99 gen_rtx (ASHIFT, word_mode, reg,
102 shiftadd_insn = emit_insn (gen_rtx (SET, VOIDmode, reg,
103 gen_rtx (PLUS, word_mode,
104 gen_rtx (MULT, word_mode,
108 shiftsub_insn = emit_insn (gen_rtx (SET, VOIDmode, reg,
109 gen_rtx (MINUS, word_mode,
110 gen_rtx (MULT, word_mode,
117 shiftadd_cost[0] = shiftsub_cost[0] = add_cost;
119 for (m = 1; m < BITS_PER_WORD; m++)
121 shift_cost[m] = shiftadd_cost[m] = shiftsub_cost[m] = 32000;
123 XEXP (SET_SRC (PATTERN (shift_insn)), 1) = GEN_INT (m);
124 if (recog (PATTERN (shift_insn), shift_insn, &dummy) >= 0)
125 shift_cost[m] = rtx_cost (SET_SRC (PATTERN (shift_insn)), SET);
127 XEXP (XEXP (SET_SRC (PATTERN (shiftadd_insn)), 0), 1)
128 = GEN_INT ((HOST_WIDE_INT) 1 << m);
129 if (recog (PATTERN (shiftadd_insn), shiftadd_insn, &dummy) >= 0)
130 shiftadd_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftadd_insn)), SET);
132 XEXP (XEXP (SET_SRC (PATTERN (shiftsub_insn)), 0), 1)
133 = GEN_INT ((HOST_WIDE_INT) 1 << m);
134 if (recog (PATTERN (shiftsub_insn), shiftsub_insn, &dummy) >= 0)
135 shiftsub_cost[m] = rtx_cost (SET_SRC (PATTERN (shiftsub_insn)), SET);
138 negate_cost = rtx_cost (gen_rtx (NEG, word_mode, reg), SET);
141 = (rtx_cost (gen_rtx (DIV, word_mode, reg, GEN_INT (32)), SET)
144 = (rtx_cost (gen_rtx (MOD, word_mode, reg, GEN_INT (32)), SET)
147 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
149 mode = GET_MODE_WIDER_MODE (mode))
151 reg = gen_rtx (REG, mode, 10000);
152 div_cost[(int) mode] = rtx_cost (gen_rtx (UDIV, mode, reg, reg), SET);
153 mul_cost[(int) mode] = rtx_cost (gen_rtx (MULT, mode, reg, reg), SET);
154 wider_mode = GET_MODE_WIDER_MODE (mode);
155 if (wider_mode != VOIDmode)
157 mul_widen_cost[(int) wider_mode]
158 = rtx_cost (gen_rtx (MULT, wider_mode,
159 gen_rtx (ZERO_EXTEND, wider_mode, reg),
160 gen_rtx (ZERO_EXTEND, wider_mode, reg)),
162 mul_highpart_cost[(int) mode]
163 = rtx_cost (gen_rtx (TRUNCATE, mode,
164 gen_rtx (LSHIFTRT, wider_mode,
165 gen_rtx (MULT, wider_mode,
166 gen_rtx (ZERO_EXTEND, wider_mode, reg),
167 gen_rtx (ZERO_EXTEND, wider_mode, reg)),
168 GEN_INT (GET_MODE_BITSIZE (mode)))),
173 /* Free the objects we just allocated. */
178 /* Return an rtx representing minus the value of X.
179 MODE is the intended mode of the result,
180 useful if X is a CONST_INT. */
184 enum machine_mode mode;
187 if (GET_CODE (x) == CONST_INT)
189 HOST_WIDE_INT val = - INTVAL (x);
190 if (GET_MODE_BITSIZE (mode) < HOST_BITS_PER_WIDE_INT)
192 /* Sign extend the value from the bits that are significant. */
193 if (val & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
194 val |= (HOST_WIDE_INT) (-1) << GET_MODE_BITSIZE (mode);
196 val &= ((HOST_WIDE_INT) 1 << GET_MODE_BITSIZE (mode)) - 1;
198 return GEN_INT (val);
201 return expand_unop (GET_MODE (x), neg_optab, x, NULL_RTX, 0);
204 /* Generate code to store value from rtx VALUE
205 into a bit-field within structure STR_RTX
206 containing BITSIZE bits starting at bit BITNUM.
207 FIELDMODE is the machine-mode of the FIELD_DECL node for this field.
208 ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
209 TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */
211 /* ??? Note that there are two different ideas here for how
212 to determine the size to count bits within, for a register.
213 One is BITS_PER_WORD, and the other is the size of operand 3
214 of the insv pattern. (The latter assumes that an n-bit machine
215 will be able to insert bit fields up to n bits wide.)
216 It isn't certain that either of these is right.
217 extract_bit_field has the same quandary. */
220 store_bit_field (str_rtx, bitsize, bitnum, fieldmode, value, align, total_size)
222 register int bitsize;
224 enum machine_mode fieldmode;
229 int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
230 register int offset = bitnum / unit;
231 register int bitpos = bitnum % unit;
232 register rtx op0 = str_rtx;
234 if (GET_CODE (str_rtx) == MEM && ! MEM_IN_STRUCT_P (str_rtx))
237 /* Discount the part of the structure before the desired byte.
238 We need to know how many bytes are safe to reference after it. */
240 total_size -= (bitpos / BIGGEST_ALIGNMENT
241 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
243 while (GET_CODE (op0) == SUBREG)
245 /* The following line once was done only if WORDS_BIG_ENDIAN,
246 but I think that is a mistake. WORDS_BIG_ENDIAN is
247 meaningful at a much higher level; when structures are copied
248 between memory and regs, the higher-numbered regs
249 always get higher addresses. */
250 offset += SUBREG_WORD (op0);
251 /* We used to adjust BITPOS here, but now we do the whole adjustment
252 right after the loop. */
253 op0 = SUBREG_REG (op0);
256 /* If OP0 is a register, BITPOS must count within a word.
257 But as we have it, it counts within whatever size OP0 now has.
258 On a bigendian machine, these are not the same, so convert. */
260 && GET_CODE (op0) != MEM
261 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
262 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
264 value = protect_from_queue (value, 0);
267 value = force_not_mem (value);
269 /* Note that the adjustment of BITPOS above has no effect on whether
270 BITPOS is 0 in a REG bigger than a word. */
271 if (GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
272 && (GET_CODE (op0) != MEM
273 || ! SLOW_UNALIGNED_ACCESS
274 || (offset * BITS_PER_UNIT % bitsize == 0
275 && align % GET_MODE_SIZE (fieldmode) == 0))
276 && bitpos == 0 && bitsize == GET_MODE_BITSIZE (fieldmode))
278 /* Storing in a full-word or multi-word field in a register
279 can be done with just SUBREG. */
280 if (GET_MODE (op0) != fieldmode)
282 if (GET_CODE (op0) == REG)
283 op0 = gen_rtx (SUBREG, fieldmode, op0, offset);
285 op0 = change_address (op0, fieldmode,
286 plus_constant (XEXP (op0, 0), offset));
288 emit_move_insn (op0, value);
292 /* Storing an lsb-aligned field in a register
293 can be done with a movestrict instruction. */
295 if (GET_CODE (op0) != MEM
296 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
297 && bitsize == GET_MODE_BITSIZE (fieldmode)
298 && (GET_MODE (op0) == fieldmode
299 || (movstrict_optab->handlers[(int) fieldmode].insn_code
300 != CODE_FOR_nothing)))
302 /* Get appropriate low part of the value being stored. */
303 if (GET_CODE (value) == CONST_INT || GET_CODE (value) == REG)
304 value = gen_lowpart (fieldmode, value);
305 else if (!(GET_CODE (value) == SYMBOL_REF
306 || GET_CODE (value) == LABEL_REF
307 || GET_CODE (value) == CONST))
308 value = convert_to_mode (fieldmode, value, 0);
310 if (GET_MODE (op0) == fieldmode)
311 emit_move_insn (op0, value);
314 int icode = movstrict_optab->handlers[(int) fieldmode].insn_code;
315 if(! (*insn_operand_predicate[icode][1]) (value, fieldmode))
316 value = copy_to_mode_reg (fieldmode, value);
317 emit_insn (GEN_FCN (icode)
318 (gen_rtx (SUBREG, fieldmode, op0, offset), value));
323 /* Handle fields bigger than a word. */
325 if (bitsize > BITS_PER_WORD)
327 /* Here we transfer the words of the field
328 in the order least significant first.
329 This is because the most significant word is the one which may
331 However, only do that if the value is not BLKmode. */
333 int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
335 int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
338 /* This is the mode we must force value to, so that there will be enough
339 subwords to extract. Note that fieldmode will often (always?) be
340 VOIDmode, because that is what store_field uses to indicate that this
341 is a bit field, but passing VOIDmode to operand_subword_force will
342 result in an abort. */
343 fieldmode = mode_for_size (nwords * BITS_PER_WORD, MODE_INT, 0);
345 for (i = 0; i < nwords; i++)
347 /* If I is 0, use the low-order word in both field and target;
348 if I is 1, use the next to lowest word; and so on. */
349 int wordnum = (backwards ? nwords - i - 1 : i);
350 int bit_offset = (backwards
351 ? MAX (bitsize - (i + 1) * BITS_PER_WORD, 0)
352 : i * BITS_PER_WORD);
353 store_bit_field (op0, MIN (BITS_PER_WORD,
354 bitsize - i * BITS_PER_WORD),
355 bitnum + bit_offset, word_mode,
356 operand_subword_force (value, wordnum,
357 (GET_MODE (value) == VOIDmode
359 : GET_MODE (value))),
365 /* From here on we can assume that the field to be stored in is
366 a full-word (whatever type that is), since it is shorter than a word. */
368 /* OFFSET is the number of words or bytes (UNIT says which)
369 from STR_RTX to the first word or byte containing part of the field. */
371 if (GET_CODE (op0) == REG)
374 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
375 op0 = gen_rtx (SUBREG, TYPE_MODE (type_for_size (BITS_PER_WORD, 0)),
381 op0 = protect_from_queue (op0, 1);
384 /* If VALUE is a floating-point mode, access it as an integer of the
385 corresponding size. This can occur on a machine with 64 bit registers
386 that uses SFmode for float. This can also occur for unaligned float
388 if (GET_MODE_CLASS (GET_MODE (value)) == MODE_FLOAT)
390 if (GET_CODE (value) != REG)
391 value = copy_to_reg (value);
392 value = gen_rtx (SUBREG, word_mode, value, 0);
395 /* Now OFFSET is nonzero only if OP0 is memory
396 and is therefore always measured in bytes. */
400 && !(bitsize == 1 && GET_CODE (value) == CONST_INT)
401 /* Ensure insv's size is wide enough for this field. */
402 && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_insv][3])
404 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
406 > GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_insv][3]))))
408 int xbitpos = bitpos;
411 rtx last = get_last_insn ();
413 enum machine_mode maxmode
414 = insn_operand_mode[(int) CODE_FOR_insv][3];
416 int save_volatile_ok = volatile_ok;
419 /* If this machine's insv can only insert into a register, or if we
420 are to force MEMs into a register, copy OP0 into a register and
421 save it back later. */
422 if (GET_CODE (op0) == MEM
424 || ! ((*insn_operand_predicate[(int) CODE_FOR_insv][0])
428 enum machine_mode bestmode;
430 /* Get the mode to use for inserting into this field. If OP0 is
431 BLKmode, get the smallest mode consistent with the alignment. If
432 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its
433 mode. Otherwise, use the smallest mode containing the field. */
435 if (GET_MODE (op0) == BLKmode
436 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode))
438 = get_best_mode (bitsize, bitnum, align * BITS_PER_UNIT, maxmode,
439 MEM_VOLATILE_P (op0));
441 bestmode = GET_MODE (op0);
443 if (bestmode == VOIDmode
444 || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
447 /* Adjust address to point to the containing unit of that mode. */
448 unit = GET_MODE_BITSIZE (bestmode);
449 /* Compute offset as multiple of this unit, counting in bytes. */
450 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
451 bitpos = bitnum % unit;
452 op0 = change_address (op0, bestmode,
453 plus_constant (XEXP (op0, 0), offset));
455 /* Fetch that unit, store the bitfield in it, then store the unit. */
456 tempreg = copy_to_reg (op0);
457 store_bit_field (tempreg, bitsize, bitpos, fieldmode, value,
459 emit_move_insn (op0, tempreg);
462 volatile_ok = save_volatile_ok;
464 /* Add OFFSET into OP0's address. */
465 if (GET_CODE (xop0) == MEM)
466 xop0 = change_address (xop0, byte_mode,
467 plus_constant (XEXP (xop0, 0), offset));
469 /* If xop0 is a register, we need it in MAXMODE
470 to make it acceptable to the format of insv. */
471 if (GET_CODE (xop0) == SUBREG)
472 /* We can't just change the mode, because this might clobber op0,
473 and we will need the original value of op0 if insv fails. */
474 xop0 = gen_rtx (SUBREG, maxmode, SUBREG_REG (xop0), SUBREG_WORD (xop0));
475 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
476 xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
478 /* On big-endian machines, we count bits from the most significant.
479 If the bit field insn does not, we must invert. */
481 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
482 xbitpos = unit - bitsize - xbitpos;
484 /* We have been counting XBITPOS within UNIT.
485 Count instead within the size of the register. */
486 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
487 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
489 unit = GET_MODE_BITSIZE (maxmode);
491 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */
493 if (GET_MODE (value) != maxmode)
495 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
497 /* Optimization: Don't bother really extending VALUE
498 if it has all the bits we will actually use. However,
499 if we must narrow it, be sure we do it correctly. */
501 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode))
503 /* Avoid making subreg of a subreg, or of a mem. */
504 if (GET_CODE (value1) != REG)
505 value1 = copy_to_reg (value1);
506 value1 = gen_rtx (SUBREG, maxmode, value1, 0);
509 value1 = gen_lowpart (maxmode, value1);
511 else if (!CONSTANT_P (value))
512 /* Parse phase is supposed to make VALUE's data type
513 match that of the component reference, which is a type
514 at least as wide as the field; so VALUE should have
515 a mode that corresponds to that type. */
519 /* If this machine's insv insists on a register,
520 get VALUE1 into a register. */
521 if (! ((*insn_operand_predicate[(int) CODE_FOR_insv][3])
523 value1 = force_reg (maxmode, value1);
525 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
530 delete_insns_since (last);
531 store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
537 /* Insv is not available; store using shifts and boolean ops. */
538 store_fixed_bit_field (op0, offset, bitsize, bitpos, value, align);
542 /* Use shifts and boolean operations to store VALUE
543 into a bit field of width BITSIZE
544 in a memory location specified by OP0 except offset by OFFSET bytes.
545 (OFFSET must be 0 if OP0 is a register.)
546 The field starts at position BITPOS within the byte.
547 (If OP0 is a register, it may be a full word or a narrower mode,
548 but BITPOS still counts within a full word,
549 which is significant on bigendian machines.)
550 STRUCT_ALIGN is the alignment the structure is known to have (in bytes).
552 Note that protect_from_queue has already been done on OP0 and VALUE. */
555 store_fixed_bit_field (op0, offset, bitsize, bitpos, value, struct_align)
557 register int offset, bitsize, bitpos;
561 register enum machine_mode mode;
562 int total_bits = BITS_PER_WORD;
567 /* There is a case not handled here:
568 a structure with a known alignment of just a halfword
569 and a field split across two aligned halfwords within the structure.
570 Or likewise a structure with a known alignment of just a byte
571 and a field split across two bytes.
572 Such cases are not supposed to be able to occur. */
574 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
578 /* Special treatment for a bit field split across two registers. */
579 if (bitsize + bitpos > BITS_PER_WORD)
581 store_split_bit_field (op0, bitsize, bitpos,
582 value, BITS_PER_WORD);
588 /* Get the proper mode to use for this field. We want a mode that
589 includes the entire field. If such a mode would be larger than
590 a word, we won't be doing the extraction the normal way. */
592 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
593 struct_align * BITS_PER_UNIT, word_mode,
594 GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
596 if (mode == VOIDmode)
598 /* The only way this should occur is if the field spans word
600 store_split_bit_field (op0,
601 bitsize, bitpos + offset * BITS_PER_UNIT,
602 value, struct_align);
606 total_bits = GET_MODE_BITSIZE (mode);
608 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
609 be be in the range 0 to total_bits-1, and put any excess bytes in
611 if (bitpos >= total_bits)
613 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
614 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
618 /* Get ref to an aligned byte, halfword, or word containing the field.
619 Adjust BITPOS to be position within a word,
620 and OFFSET to be the offset of that word.
621 Then alter OP0 to refer to that word. */
622 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
623 offset -= (offset % (total_bits / BITS_PER_UNIT));
624 op0 = change_address (op0, mode,
625 plus_constant (XEXP (op0, 0), offset));
628 mode = GET_MODE (op0);
630 /* Now MODE is either some integral mode for a MEM as OP0,
631 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
632 The bit field is contained entirely within OP0.
633 BITPOS is the starting bit number within OP0.
634 (OP0's mode may actually be narrower than MODE.) */
636 if (BYTES_BIG_ENDIAN)
637 /* BITPOS is the distance between our msb
638 and that of the containing datum.
639 Convert it to the distance from the lsb. */
640 bitpos = total_bits - bitsize - bitpos;
642 /* Now BITPOS is always the distance between our lsb
645 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
646 we must first convert its mode to MODE. */
648 if (GET_CODE (value) == CONST_INT)
650 register HOST_WIDE_INT v = INTVAL (value);
652 if (bitsize < HOST_BITS_PER_WIDE_INT)
653 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
657 else if ((bitsize < HOST_BITS_PER_WIDE_INT
658 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
659 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
662 value = lshift_value (mode, value, bitpos, bitsize);
666 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
667 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
669 if (GET_MODE (value) != mode)
671 if ((GET_CODE (value) == REG || GET_CODE (value) == SUBREG)
672 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value)))
673 value = gen_lowpart (mode, value);
675 value = convert_to_mode (mode, value, 1);
679 value = expand_binop (mode, and_optab, value,
680 mask_rtx (mode, 0, bitsize, 0),
681 NULL_RTX, 1, OPTAB_LIB_WIDEN);
683 value = expand_shift (LSHIFT_EXPR, mode, value,
684 build_int_2 (bitpos, 0), NULL_RTX, 1);
687 /* Now clear the chosen bits in OP0,
688 except that if VALUE is -1 we need not bother. */
690 subtarget = (GET_CODE (op0) == REG || ! flag_force_mem) ? op0 : 0;
694 temp = expand_binop (mode, and_optab, op0,
695 mask_rtx (mode, bitpos, bitsize, 1),
696 subtarget, 1, OPTAB_LIB_WIDEN);
702 /* Now logical-or VALUE into OP0, unless it is zero. */
705 temp = expand_binop (mode, ior_optab, temp, value,
706 subtarget, 1, OPTAB_LIB_WIDEN);
708 emit_move_insn (op0, temp);
711 /* Store a bit field that is split across multiple accessible memory objects.
713 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
714 BITSIZE is the field width; BITPOS the position of its first bit
716 VALUE is the value to store.
717 ALIGN is the known alignment of OP0, measured in bytes.
718 This is also the size of the memory objects to be used.
720 This does not yet handle fields wider than BITS_PER_WORD. */
723 store_split_bit_field (op0, bitsize, bitpos, value, align)
732 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
734 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
735 unit = BITS_PER_WORD;
737 unit = MIN (align * BITS_PER_UNIT, BITS_PER_WORD);
739 /* If VALUE is a constant other than a CONST_INT, get it into a register in
740 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
741 that VALUE might be a floating-point constant. */
742 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT)
744 rtx word = gen_lowpart_common (word_mode, value);
746 if (word && (value != word))
749 value = gen_lowpart_common (word_mode,
750 force_reg (GET_MODE (value), value));
753 while (bitsdone < bitsize)
760 offset = (bitpos + bitsdone) / unit;
761 thispos = (bitpos + bitsdone) % unit;
763 /* THISSIZE must not overrun a word boundary. Otherwise,
764 store_fixed_bit_field will call us again, and we will mutually
766 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
767 thissize = MIN (thissize, unit - thispos);
769 if (BYTES_BIG_ENDIAN)
771 /* Fetch successively less significant portions. */
772 if (GET_CODE (value) == CONST_INT)
773 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
774 >> (bitsize - bitsdone - thissize))
775 & (((HOST_WIDE_INT) 1 << thissize) - 1));
777 /* The args are chosen so that the last part includes the
778 lsb. Give extract_bit_field the value it needs (with
779 endianness compensation) to fetch the piece we want. */
780 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
781 GET_MODE_BITSIZE (GET_MODE (value))
782 - bitsize + bitsdone,
787 /* Fetch successively more significant portions. */
788 if (GET_CODE (value) == CONST_INT)
789 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
791 & (((HOST_WIDE_INT) 1 << thissize) - 1));
793 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
794 bitsdone, NULL_RTX, 1, align);
797 /* If OP0 is a register, then handle OFFSET here.
799 When handling multiword bitfields, extract_bit_field may pass
800 down a word_mode SUBREG of a larger REG for a bitfield that actually
801 crosses a word boundary. Thus, for a SUBREG, we must find
802 the current word starting from the base register. */
803 if (GET_CODE (op0) == SUBREG)
805 word = operand_subword_force (SUBREG_REG (op0),
806 SUBREG_WORD (op0) + offset,
807 GET_MODE (SUBREG_REG (op0)));
810 else if (GET_CODE (op0) == REG)
812 word = operand_subword_force (op0, offset, GET_MODE (op0));
818 /* OFFSET is in UNITs, and UNIT is in bits.
819 store_fixed_bit_field wants offset in bytes. */
820 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT,
821 thissize, thispos, part, align);
822 bitsdone += thissize;
826 /* Generate code to extract a byte-field from STR_RTX
827 containing BITSIZE bits, starting at BITNUM,
828 and put it in TARGET if possible (if TARGET is nonzero).
829 Regardless of TARGET, we return the rtx for where the value is placed.
832 STR_RTX is the structure containing the byte (a REG or MEM).
833 UNSIGNEDP is nonzero if this is an unsigned bit field.
834 MODE is the natural mode of the field value once extracted.
835 TMODE is the mode the caller would like the value to have;
836 but the value may be returned with type MODE instead.
838 ALIGN is the alignment that STR_RTX is known to have, measured in bytes.
839 TOTAL_SIZE is the size in bytes of the containing structure,
842 If a TARGET is specified and we can store in it at no extra cost,
843 we do so, and return TARGET.
844 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
845 if they are equally easy. */
848 extract_bit_field (str_rtx, bitsize, bitnum, unsignedp,
849 target, mode, tmode, align, total_size)
851 register int bitsize;
855 enum machine_mode mode, tmode;
859 int unit = (GET_CODE (str_rtx) == MEM) ? BITS_PER_UNIT : BITS_PER_WORD;
860 register int offset = bitnum / unit;
861 register int bitpos = bitnum % unit;
862 register rtx op0 = str_rtx;
863 rtx spec_target = target;
864 rtx spec_target_subreg = 0;
866 if (GET_CODE (str_rtx) == MEM && ! MEM_IN_STRUCT_P (str_rtx))
869 /* Discount the part of the structure before the desired byte.
870 We need to know how many bytes are safe to reference after it. */
872 total_size -= (bitpos / BIGGEST_ALIGNMENT
873 * (BIGGEST_ALIGNMENT / BITS_PER_UNIT));
875 if (tmode == VOIDmode)
877 while (GET_CODE (op0) == SUBREG)
879 offset += SUBREG_WORD (op0);
880 op0 = SUBREG_REG (op0);
883 /* ??? We currently assume TARGET is at least as big as BITSIZE.
884 If that's wrong, the solution is to test for it and set TARGET to 0
887 /* If OP0 is a register, BITPOS must count within a word.
888 But as we have it, it counts within whatever size OP0 now has.
889 On a bigendian machine, these are not the same, so convert. */
890 if (BYTES_BIG_ENDIAN &&
891 GET_CODE (op0) != MEM
892 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
893 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
895 /* Extracting a full-word or multi-word value
896 from a structure in a register or aligned memory.
897 This can be done with just SUBREG.
898 So too extracting a subword value in
899 the least significant part of the register. */
901 if ((GET_CODE (op0) == REG
902 || (GET_CODE (op0) == MEM
903 && (! SLOW_UNALIGNED_ACCESS
904 || (offset * BITS_PER_UNIT % bitsize == 0
905 && align * BITS_PER_UNIT % bitsize == 0))))
906 && ((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
907 && bitpos % BITS_PER_WORD == 0)
908 || (mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) != BLKmode
910 ? bitpos + bitsize == BITS_PER_WORD
913 enum machine_mode mode1
914 = mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0);
916 if (mode1 != GET_MODE (op0))
918 if (GET_CODE (op0) == REG)
919 op0 = gen_rtx (SUBREG, mode1, op0, offset);
921 op0 = change_address (op0, mode1,
922 plus_constant (XEXP (op0, 0), offset));
925 return convert_to_mode (tmode, op0, unsignedp);
929 /* Handle fields bigger than a word. */
931 if (bitsize > BITS_PER_WORD)
933 /* Here we transfer the words of the field
934 in the order least significant first.
935 This is because the most significant word is the one which may
936 be less than full. */
938 int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
941 if (target == 0 || GET_CODE (target) != REG)
942 target = gen_reg_rtx (mode);
944 for (i = 0; i < nwords; i++)
946 /* If I is 0, use the low-order word in both field and target;
947 if I is 1, use the next to lowest word; and so on. */
948 /* Word number in TARGET to use. */
949 int wordnum = (WORDS_BIG_ENDIAN
950 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
952 /* Offset from start of field in OP0. */
953 int bit_offset = (WORDS_BIG_ENDIAN
954 ? MAX (0, bitsize - (i + 1) * BITS_PER_WORD)
955 : i * BITS_PER_WORD);
956 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
958 = extract_bit_field (op0, MIN (BITS_PER_WORD,
959 bitsize - i * BITS_PER_WORD),
961 1, target_part, mode, word_mode,
964 if (target_part == 0)
967 if (result_part != target_part)
968 emit_move_insn (target_part, result_part);
973 /* Unless we've filled TARGET, the upper regs in a multi-reg value
974 need to be zero'd out. */
975 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
979 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
980 for (i = nwords; i < total_words; i++)
982 int wordnum = WORDS_BIG_ENDIAN ? total_words - i - 1 : i;
983 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
984 emit_move_insn (target_part, const0_rtx);
990 /* Signed bit field: sign-extend with two arithmetic shifts. */
991 target = expand_shift (LSHIFT_EXPR, mode, target,
992 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
994 return expand_shift (RSHIFT_EXPR, mode, target,
995 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
999 /* From here on we know the desired field is smaller than a word
1000 so we can assume it is an integer. So we can safely extract it as one
1001 size of integer, if necessary, and then truncate or extend
1002 to the size that is wanted. */
1004 /* OFFSET is the number of words or bytes (UNIT says which)
1005 from STR_RTX to the first word or byte containing part of the field. */
1007 if (GET_CODE (op0) == REG)
1010 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1011 op0 = gen_rtx (SUBREG, TYPE_MODE (type_for_size (BITS_PER_WORD, 0)),
1017 op0 = protect_from_queue (str_rtx, 1);
1020 /* Now OFFSET is nonzero only for memory operands. */
1026 && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extzv][0])
1028 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1029 && (bitsize + bitpos
1030 > GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extzv][0]))))
1032 int xbitpos = bitpos, xoffset = offset;
1033 rtx bitsize_rtx, bitpos_rtx;
1034 rtx last = get_last_insn();
1036 rtx xtarget = target;
1037 rtx xspec_target = spec_target;
1038 rtx xspec_target_subreg = spec_target_subreg;
1040 enum machine_mode maxmode
1041 = insn_operand_mode[(int) CODE_FOR_extzv][0];
1043 if (GET_CODE (xop0) == MEM)
1045 int save_volatile_ok = volatile_ok;
1048 /* Is the memory operand acceptable? */
1050 || ! ((*insn_operand_predicate[(int) CODE_FOR_extzv][1])
1051 (xop0, GET_MODE (xop0))))
1053 /* No, load into a reg and extract from there. */
1054 enum machine_mode bestmode;
1056 /* Get the mode to use for inserting into this field. If
1057 OP0 is BLKmode, get the smallest mode consistent with the
1058 alignment. If OP0 is a non-BLKmode object that is no
1059 wider than MAXMODE, use its mode. Otherwise, use the
1060 smallest mode containing the field. */
1062 if (GET_MODE (xop0) == BLKmode
1063 || (GET_MODE_SIZE (GET_MODE (op0))
1064 > GET_MODE_SIZE (maxmode)))
1065 bestmode = get_best_mode (bitsize, bitnum,
1066 align * BITS_PER_UNIT, maxmode,
1067 MEM_VOLATILE_P (xop0));
1069 bestmode = GET_MODE (xop0);
1071 if (bestmode == VOIDmode
1072 || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
1075 /* Compute offset as multiple of this unit,
1076 counting in bytes. */
1077 unit = GET_MODE_BITSIZE (bestmode);
1078 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1079 xbitpos = bitnum % unit;
1080 xop0 = change_address (xop0, bestmode,
1081 plus_constant (XEXP (xop0, 0),
1083 /* Fetch it to a register in that size. */
1084 xop0 = force_reg (bestmode, xop0);
1086 /* XBITPOS counts within UNIT, which is what is expected. */
1089 /* Get ref to first byte containing part of the field. */
1090 xop0 = change_address (xop0, byte_mode,
1091 plus_constant (XEXP (xop0, 0), xoffset));
1093 volatile_ok = save_volatile_ok;
1096 /* If op0 is a register, we need it in MAXMODE (which is usually
1097 SImode). to make it acceptable to the format of extzv. */
1098 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1100 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1101 xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
1103 /* On big-endian machines, we count bits from the most significant.
1104 If the bit field insn does not, we must invert. */
1105 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1106 xbitpos = unit - bitsize - xbitpos;
1108 /* Now convert from counting within UNIT to counting in MAXMODE. */
1109 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1110 xbitpos += GET_MODE_BITSIZE (maxmode) - unit;
1112 unit = GET_MODE_BITSIZE (maxmode);
1115 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1116 xtarget = xspec_target = gen_reg_rtx (tmode);
1118 if (GET_MODE (xtarget) != maxmode)
1120 if (GET_CODE (xtarget) == REG)
1122 int wider = (GET_MODE_SIZE (maxmode)
1123 > GET_MODE_SIZE (GET_MODE (xtarget)));
1124 xtarget = gen_lowpart (maxmode, xtarget);
1126 xspec_target_subreg = xtarget;
1129 xtarget = gen_reg_rtx (maxmode);
1132 /* If this machine's extzv insists on a register target,
1133 make sure we have one. */
1134 if (! ((*insn_operand_predicate[(int) CODE_FOR_extzv][0])
1135 (xtarget, maxmode)))
1136 xtarget = gen_reg_rtx (maxmode);
1138 bitsize_rtx = GEN_INT (bitsize);
1139 bitpos_rtx = GEN_INT (xbitpos);
1141 pat = gen_extzv (protect_from_queue (xtarget, 1),
1142 xop0, bitsize_rtx, bitpos_rtx);
1147 spec_target = xspec_target;
1148 spec_target_subreg = xspec_target_subreg;
1152 delete_insns_since (last);
1153 target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
1154 bitpos, target, 1, align);
1160 target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1167 && (GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extv][0])
1169 && ! ((GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1170 && (bitsize + bitpos
1171 > GET_MODE_BITSIZE (insn_operand_mode[(int) CODE_FOR_extv][0]))))
1173 int xbitpos = bitpos, xoffset = offset;
1174 rtx bitsize_rtx, bitpos_rtx;
1175 rtx last = get_last_insn();
1176 rtx xop0 = op0, xtarget = target;
1177 rtx xspec_target = spec_target;
1178 rtx xspec_target_subreg = spec_target_subreg;
1180 enum machine_mode maxmode
1181 = insn_operand_mode[(int) CODE_FOR_extv][0];
1183 if (GET_CODE (xop0) == MEM)
1185 /* Is the memory operand acceptable? */
1186 if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][1])
1187 (xop0, GET_MODE (xop0))))
1189 /* No, load into a reg and extract from there. */
1190 enum machine_mode bestmode;
1192 /* Get the mode to use for inserting into this field. If
1193 OP0 is BLKmode, get the smallest mode consistent with the
1194 alignment. If OP0 is a non-BLKmode object that is no
1195 wider than MAXMODE, use its mode. Otherwise, use the
1196 smallest mode containing the field. */
1198 if (GET_MODE (xop0) == BLKmode
1199 || (GET_MODE_SIZE (GET_MODE (op0))
1200 > GET_MODE_SIZE (maxmode)))
1201 bestmode = get_best_mode (bitsize, bitnum,
1202 align * BITS_PER_UNIT, maxmode,
1203 MEM_VOLATILE_P (xop0));
1205 bestmode = GET_MODE (xop0);
1207 if (bestmode == VOIDmode
1208 || (SLOW_UNALIGNED_ACCESS && GET_MODE_SIZE (bestmode) > align))
1211 /* Compute offset as multiple of this unit,
1212 counting in bytes. */
1213 unit = GET_MODE_BITSIZE (bestmode);
1214 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1215 xbitpos = bitnum % unit;
1216 xop0 = change_address (xop0, bestmode,
1217 plus_constant (XEXP (xop0, 0),
1219 /* Fetch it to a register in that size. */
1220 xop0 = force_reg (bestmode, xop0);
1222 /* XBITPOS counts within UNIT, which is what is expected. */
1225 /* Get ref to first byte containing part of the field. */
1226 xop0 = change_address (xop0, byte_mode,
1227 plus_constant (XEXP (xop0, 0), xoffset));
1230 /* If op0 is a register, we need it in MAXMODE (which is usually
1231 SImode) to make it acceptable to the format of extv. */
1232 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode)
1234 if (GET_CODE (xop0) == REG && GET_MODE (xop0) != maxmode)
1235 xop0 = gen_rtx (SUBREG, maxmode, xop0, 0);
1237 /* On big-endian machines, we count bits from the most significant.
1238 If the bit field insn does not, we must invert. */
1239 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1240 xbitpos = unit - bitsize - xbitpos;
1242 /* XBITPOS counts within a size of UNIT.
1243 Adjust to count within a size of MAXMODE. */
1244 if (BITS_BIG_ENDIAN && GET_CODE (xop0) != MEM)
1245 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit);
1247 unit = GET_MODE_BITSIZE (maxmode);
1250 || (flag_force_mem && GET_CODE (xtarget) == MEM))
1251 xtarget = xspec_target = gen_reg_rtx (tmode);
1253 if (GET_MODE (xtarget) != maxmode)
1255 if (GET_CODE (xtarget) == REG)
1257 int wider = (GET_MODE_SIZE (maxmode)
1258 > GET_MODE_SIZE (GET_MODE (xtarget)));
1259 xtarget = gen_lowpart (maxmode, xtarget);
1261 xspec_target_subreg = xtarget;
1264 xtarget = gen_reg_rtx (maxmode);
1267 /* If this machine's extv insists on a register target,
1268 make sure we have one. */
1269 if (! ((*insn_operand_predicate[(int) CODE_FOR_extv][0])
1270 (xtarget, maxmode)))
1271 xtarget = gen_reg_rtx (maxmode);
1273 bitsize_rtx = GEN_INT (bitsize);
1274 bitpos_rtx = GEN_INT (xbitpos);
1276 pat = gen_extv (protect_from_queue (xtarget, 1),
1277 xop0, bitsize_rtx, bitpos_rtx);
1282 spec_target = xspec_target;
1283 spec_target_subreg = xspec_target_subreg;
1287 delete_insns_since (last);
1288 target = extract_fixed_bit_field (tmode, op0, offset, bitsize,
1289 bitpos, target, 0, align);
1295 target = extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1298 if (target == spec_target)
1300 if (target == spec_target_subreg)
1302 if (GET_MODE (target) != tmode && GET_MODE (target) != mode)
1304 /* If the target mode is floating-point, first convert to the
1305 integer mode of that size and then access it as a floating-point
1306 value via a SUBREG. */
1307 if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1309 target = convert_to_mode (mode_for_size (GET_MODE_BITSIZE (tmode),
1312 if (GET_CODE (target) != REG)
1313 target = copy_to_reg (target);
1314 return gen_rtx (SUBREG, tmode, target, 0);
1317 return convert_to_mode (tmode, target, unsignedp);
1322 /* Extract a bit field using shifts and boolean operations
1323 Returns an rtx to represent the value.
1324 OP0 addresses a register (word) or memory (byte).
1325 BITPOS says which bit within the word or byte the bit field starts in.
1326 OFFSET says how many bytes farther the bit field starts;
1327 it is 0 if OP0 is a register.
1328 BITSIZE says how many bits long the bit field is.
1329 (If OP0 is a register, it may be narrower than a full word,
1330 but BITPOS still counts within a full word,
1331 which is significant on bigendian machines.)
1333 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1334 If TARGET is nonzero, attempts to store the value there
1335 and return TARGET, but this is not guaranteed.
1336 If TARGET is not used, create a pseudo-reg of mode TMODE for the value.
1338 ALIGN is the alignment that STR_RTX is known to have, measured in bytes. */
1341 extract_fixed_bit_field (tmode, op0, offset, bitsize, bitpos,
1342 target, unsignedp, align)
1343 enum machine_mode tmode;
1344 register rtx op0, target;
1345 register int offset, bitsize, bitpos;
1349 int total_bits = BITS_PER_WORD;
1350 enum machine_mode mode;
1352 if (GET_CODE (op0) == SUBREG || GET_CODE (op0) == REG)
1354 /* Special treatment for a bit field split across two registers. */
1355 if (bitsize + bitpos > BITS_PER_WORD)
1356 return extract_split_bit_field (op0, bitsize, bitpos,
1361 /* Get the proper mode to use for this field. We want a mode that
1362 includes the entire field. If such a mode would be larger than
1363 a word, we won't be doing the extraction the normal way. */
1365 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1366 align * BITS_PER_UNIT, word_mode,
1367 GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0));
1369 if (mode == VOIDmode)
1370 /* The only way this should occur is if the field spans word
1372 return extract_split_bit_field (op0, bitsize,
1373 bitpos + offset * BITS_PER_UNIT,
1376 total_bits = GET_MODE_BITSIZE (mode);
1378 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1379 be be in the range 0 to total_bits-1, and put any excess bytes in
1381 if (bitpos >= total_bits)
1383 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1384 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1388 /* Get ref to an aligned byte, halfword, or word containing the field.
1389 Adjust BITPOS to be position within a word,
1390 and OFFSET to be the offset of that word.
1391 Then alter OP0 to refer to that word. */
1392 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1393 offset -= (offset % (total_bits / BITS_PER_UNIT));
1394 op0 = change_address (op0, mode,
1395 plus_constant (XEXP (op0, 0), offset));
1398 mode = GET_MODE (op0);
1400 if (BYTES_BIG_ENDIAN)
1402 /* BITPOS is the distance between our msb and that of OP0.
1403 Convert it to the distance from the lsb. */
1405 bitpos = total_bits - bitsize - bitpos;
1408 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1409 We have reduced the big-endian case to the little-endian case. */
1415 /* If the field does not already start at the lsb,
1416 shift it so it does. */
1417 tree amount = build_int_2 (bitpos, 0);
1418 /* Maybe propagate the target for the shift. */
1419 /* But not if we will return it--could confuse integrate.c. */
1420 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1421 && !REG_FUNCTION_VALUE_P (target)
1423 if (tmode != mode) subtarget = 0;
1424 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1426 /* Convert the value to the desired mode. */
1428 op0 = convert_to_mode (tmode, op0, 1);
1430 /* Unless the msb of the field used to be the msb when we shifted,
1431 mask out the upper bits. */
1433 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize
1435 #ifdef SLOW_ZERO_EXTEND
1436 /* Always generate an `and' if
1437 we just zero-extended op0 and SLOW_ZERO_EXTEND, since it
1438 will combine fruitfully with the zero-extend. */
1443 return expand_binop (GET_MODE (op0), and_optab, op0,
1444 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1445 target, 1, OPTAB_LIB_WIDEN);
1449 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1450 then arithmetic-shift its lsb to the lsb of the word. */
1451 op0 = force_reg (mode, op0);
1455 /* Find the narrowest integer mode that contains the field. */
1457 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1458 mode = GET_MODE_WIDER_MODE (mode))
1459 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1461 op0 = convert_to_mode (mode, op0, 0);
1465 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1467 tree amount = build_int_2 (GET_MODE_BITSIZE (mode) - (bitsize + bitpos), 0);
1468 /* Maybe propagate the target for the shift. */
1469 /* But not if we will return the result--could confuse integrate.c. */
1470 rtx subtarget = (target != 0 && GET_CODE (target) == REG
1471 && ! REG_FUNCTION_VALUE_P (target)
1473 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1476 return expand_shift (RSHIFT_EXPR, mode, op0,
1477 build_int_2 (GET_MODE_BITSIZE (mode) - bitsize, 0),
1481 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1482 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1483 complement of that if COMPLEMENT. The mask is truncated if
1484 necessary to the width of mode MODE. The mask is zero-extended if
1485 BITSIZE+BITPOS is too small for MODE. */
1488 mask_rtx (mode, bitpos, bitsize, complement)
1489 enum machine_mode mode;
1490 int bitpos, bitsize, complement;
1492 HOST_WIDE_INT masklow, maskhigh;
1494 if (bitpos < HOST_BITS_PER_WIDE_INT)
1495 masklow = (HOST_WIDE_INT) -1 << bitpos;
1499 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1500 masklow &= ((unsigned HOST_WIDE_INT) -1
1501 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1503 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1506 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1508 if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1509 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1510 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1516 maskhigh = ~maskhigh;
1520 return immed_double_const (masklow, maskhigh, mode);
1523 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1524 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1527 lshift_value (mode, value, bitpos, bitsize)
1528 enum machine_mode mode;
1530 int bitpos, bitsize;
1532 unsigned HOST_WIDE_INT v = INTVAL (value);
1533 HOST_WIDE_INT low, high;
1535 if (bitsize < HOST_BITS_PER_WIDE_INT)
1536 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1538 if (bitpos < HOST_BITS_PER_WIDE_INT)
1541 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1546 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1549 return immed_double_const (low, high, mode);
1552 /* Extract a bit field that is split across two words
1553 and return an RTX for the result.
1555 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1556 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1557 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend.
1559 ALIGN is the known alignment of OP0, measured in bytes.
1560 This is also the size of the memory objects to be used. */
1563 extract_split_bit_field (op0, bitsize, bitpos, unsignedp, align)
1565 int bitsize, bitpos, unsignedp, align;
1572 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1574 if (GET_CODE (op0) == REG || GET_CODE (op0) == SUBREG)
1575 unit = BITS_PER_WORD;
1577 unit = MIN (align * BITS_PER_UNIT, BITS_PER_WORD);
1579 while (bitsdone < bitsize)
1586 offset = (bitpos + bitsdone) / unit;
1587 thispos = (bitpos + bitsdone) % unit;
1589 /* THISSIZE must not overrun a word boundary. Otherwise,
1590 extract_fixed_bit_field will call us again, and we will mutually
1592 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1593 thissize = MIN (thissize, unit - thispos);
1595 /* If OP0 is a register, then handle OFFSET here.
1597 When handling multiword bitfields, extract_bit_field may pass
1598 down a word_mode SUBREG of a larger REG for a bitfield that actually
1599 crosses a word boundary. Thus, for a SUBREG, we must find
1600 the current word starting from the base register. */
1601 if (GET_CODE (op0) == SUBREG)
1603 word = operand_subword_force (SUBREG_REG (op0),
1604 SUBREG_WORD (op0) + offset,
1605 GET_MODE (SUBREG_REG (op0)));
1608 else if (GET_CODE (op0) == REG)
1610 word = operand_subword_force (op0, offset, GET_MODE (op0));
1616 /* Extract the parts in bit-counting order,
1617 whose meaning is determined by BYTES_PER_UNIT.
1618 OFFSET is in UNITs, and UNIT is in bits.
1619 extract_fixed_bit_field wants offset in bytes. */
1620 part = extract_fixed_bit_field (word_mode, word,
1621 offset * unit / BITS_PER_UNIT,
1622 thissize, thispos, 0, 1, align);
1623 bitsdone += thissize;
1625 /* Shift this part into place for the result. */
1626 if (BYTES_BIG_ENDIAN)
1628 if (bitsize != bitsdone)
1629 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1630 build_int_2 (bitsize - bitsdone, 0), 0, 1);
1634 if (bitsdone != thissize)
1635 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1636 build_int_2 (bitsdone - thissize, 0), 0, 1);
1642 /* Combine the parts with bitwise or. This works
1643 because we extracted each part as an unsigned bit field. */
1644 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1650 /* Unsigned bit field: we are done. */
1653 /* Signed bit field: sign-extend with two arithmetic shifts. */
1654 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1655 build_int_2 (BITS_PER_WORD - bitsize, 0),
1657 return expand_shift (RSHIFT_EXPR, word_mode, result,
1658 build_int_2 (BITS_PER_WORD - bitsize, 0), NULL_RTX, 0);
1661 /* Add INC into TARGET. */
1664 expand_inc (target, inc)
1667 rtx value = expand_binop (GET_MODE (target), add_optab,
1669 target, 0, OPTAB_LIB_WIDEN);
1670 if (value != target)
1671 emit_move_insn (target, value);
1674 /* Subtract DEC from TARGET. */
1677 expand_dec (target, dec)
1680 rtx value = expand_binop (GET_MODE (target), sub_optab,
1682 target, 0, OPTAB_LIB_WIDEN);
1683 if (value != target)
1684 emit_move_insn (target, value);
1687 /* Output a shift instruction for expression code CODE,
1688 with SHIFTED being the rtx for the value to shift,
1689 and AMOUNT the tree for the amount to shift by.
1690 Store the result in the rtx TARGET, if that is convenient.
1691 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
1692 Return the rtx for where the value is. */
1695 expand_shift (code, mode, shifted, amount, target, unsignedp)
1696 enum tree_code code;
1697 register enum machine_mode mode;
1700 register rtx target;
1703 register rtx op1, temp = 0;
1704 register int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
1705 register int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
1708 /* Previously detected shift-counts computed by NEGATE_EXPR
1709 and shifted in the other direction; but that does not work
1712 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0);
1714 #if SHIFT_COUNT_TRUNCATED
1715 if (SHIFT_COUNT_TRUNCATED
1716 && GET_CODE (op1) == CONST_INT
1717 && (unsigned HOST_WIDE_INT) INTVAL (op1) >= GET_MODE_BITSIZE (mode))
1718 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
1719 % GET_MODE_BITSIZE (mode));
1722 if (op1 == const0_rtx)
1725 for (try = 0; temp == 0 && try < 3; try++)
1727 enum optab_methods methods;
1730 methods = OPTAB_DIRECT;
1732 methods = OPTAB_WIDEN;
1734 methods = OPTAB_LIB_WIDEN;
1738 /* Widening does not work for rotation. */
1739 if (methods == OPTAB_WIDEN)
1741 else if (methods == OPTAB_LIB_WIDEN)
1743 /* If we have been unable to open-code this by a rotation,
1744 do it as the IOR of two shifts. I.e., to rotate A
1745 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
1746 where C is the bitsize of A.
1748 It is theoretically possible that the target machine might
1749 not be able to perform either shift and hence we would
1750 be making two libcalls rather than just the one for the
1751 shift (similarly if IOR could not be done). We will allow
1752 this extremely unlikely lossage to avoid complicating the
1755 rtx subtarget = target == shifted ? 0 : target;
1757 tree type = TREE_TYPE (amount);
1758 tree new_amount = make_tree (type, op1);
1760 = fold (build (MINUS_EXPR, type,
1762 build_int_2 (GET_MODE_BITSIZE (mode),
1766 shifted = force_reg (mode, shifted);
1768 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
1769 mode, shifted, new_amount, subtarget, 1);
1770 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
1771 mode, shifted, other_amount, 0, 1);
1772 return expand_binop (mode, ior_optab, temp, temp1, target,
1773 unsignedp, methods);
1776 temp = expand_binop (mode,
1777 left ? rotl_optab : rotr_optab,
1778 shifted, op1, target, unsignedp, methods);
1780 /* If we don't have the rotate, but we are rotating by a constant
1781 that is in range, try a rotate in the opposite direction. */
1783 if (temp == 0 && GET_CODE (op1) == CONST_INT
1784 && INTVAL (op1) > 0 && INTVAL (op1) < GET_MODE_BITSIZE (mode))
1785 temp = expand_binop (mode,
1786 left ? rotr_optab : rotl_optab,
1788 GEN_INT (GET_MODE_BITSIZE (mode)
1790 target, unsignedp, methods);
1793 temp = expand_binop (mode,
1794 left ? ashl_optab : lshr_optab,
1795 shifted, op1, target, unsignedp, methods);
1797 /* Do arithmetic shifts.
1798 Also, if we are going to widen the operand, we can just as well
1799 use an arithmetic right-shift instead of a logical one. */
1800 if (temp == 0 && ! rotate
1801 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
1803 enum optab_methods methods1 = methods;
1805 /* If trying to widen a log shift to an arithmetic shift,
1806 don't accept an arithmetic shift of the same size. */
1808 methods1 = OPTAB_MUST_WIDEN;
1810 /* Arithmetic shift */
1812 temp = expand_binop (mode,
1813 left ? ashl_optab : ashr_optab,
1814 shifted, op1, target, unsignedp, methods1);
1817 /* We used to try extzv here for logical right shifts, but that was
1818 only useful for one machine, the VAX, and caused poor code
1819 generation there for lshrdi3, so the code was deleted and a
1820 define_expand for lshrsi3 was added to vax.md. */
1828 enum alg_code { alg_zero, alg_m, alg_shift,
1829 alg_add_t_m2, alg_sub_t_m2,
1830 alg_add_factor, alg_sub_factor,
1831 alg_add_t2_m, alg_sub_t2_m,
1832 alg_add, alg_subtract, alg_factor, alg_shiftop };
1834 /* This structure records a sequence of operations.
1835 `ops' is the number of operations recorded.
1836 `cost' is their total cost.
1837 The operations are stored in `op' and the corresponding
1838 logarithms of the integer coefficients in `log'.
1840 These are the operations:
1841 alg_zero total := 0;
1842 alg_m total := multiplicand;
1843 alg_shift total := total * coeff
1844 alg_add_t_m2 total := total + multiplicand * coeff;
1845 alg_sub_t_m2 total := total - multiplicand * coeff;
1846 alg_add_factor total := total * coeff + total;
1847 alg_sub_factor total := total * coeff - total;
1848 alg_add_t2_m total := total * coeff + multiplicand;
1849 alg_sub_t2_m total := total * coeff - multiplicand;
1851 The first operand must be either alg_zero or alg_m. */
1857 /* The size of the OP and LOG fields are not directly related to the
1858 word size, but the worst-case algorithms will be if we have few
1859 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
1860 In that case we will generate shift-by-2, add, shift-by-2, add,...,
1861 in total wordsize operations. */
1862 enum alg_code op[MAX_BITS_PER_WORD];
1863 char log[MAX_BITS_PER_WORD];
1866 /* Compute and return the best algorithm for multiplying by T.
1867 The algorithm must cost less than cost_limit
1868 If retval.cost >= COST_LIMIT, no algorithm was found and all
1869 other field of the returned struct are undefined. */
1872 synth_mult (alg_out, t, cost_limit)
1873 struct algorithm *alg_out;
1874 unsigned HOST_WIDE_INT t;
1878 struct algorithm *alg_in, *best_alg;
1880 unsigned HOST_WIDE_INT q;
1882 /* Indicate that no algorithm is yet found. If no algorithm
1883 is found, this value will be returned and indicate failure. */
1884 alg_out->cost = cost_limit;
1886 if (cost_limit <= 0)
1889 /* t == 1 can be done in zero cost. */
1894 alg_out->op[0] = alg_m;
1898 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
1902 if (zero_cost >= cost_limit)
1907 alg_out->cost = zero_cost;
1908 alg_out->op[0] = alg_zero;
1913 /* We'll be needing a couple extra algorithm structures now. */
1915 alg_in = (struct algorithm *)alloca (sizeof (struct algorithm));
1916 best_alg = (struct algorithm *)alloca (sizeof (struct algorithm));
1918 /* If we have a group of zero bits at the low-order part of T, try
1919 multiplying by the remaining bits and then doing a shift. */
1923 m = floor_log2 (t & -t); /* m = number of low zero bits */
1925 cost = shift_cost[m];
1926 synth_mult (alg_in, q, cost_limit - cost);
1928 cost += alg_in->cost;
1929 if (cost < cost_limit)
1931 struct algorithm *x;
1932 x = alg_in, alg_in = best_alg, best_alg = x;
1933 best_alg->log[best_alg->ops] = m;
1934 best_alg->op[best_alg->ops] = alg_shift;
1939 /* If we have an odd number, add or subtract one. */
1942 unsigned HOST_WIDE_INT w;
1944 for (w = 1; (w & t) != 0; w <<= 1)
1947 /* Reject the case where t is 3.
1948 Thus we prefer addition in that case. */
1951 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
1954 synth_mult (alg_in, t + 1, cost_limit - cost);
1956 cost += alg_in->cost;
1957 if (cost < cost_limit)
1959 struct algorithm *x;
1960 x = alg_in, alg_in = best_alg, best_alg = x;
1961 best_alg->log[best_alg->ops] = 0;
1962 best_alg->op[best_alg->ops] = alg_sub_t_m2;
1968 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
1971 synth_mult (alg_in, t - 1, cost_limit - cost);
1973 cost += alg_in->cost;
1974 if (cost < cost_limit)
1976 struct algorithm *x;
1977 x = alg_in, alg_in = best_alg, best_alg = x;
1978 best_alg->log[best_alg->ops] = 0;
1979 best_alg->op[best_alg->ops] = alg_add_t_m2;
1985 /* Look for factors of t of the form
1986 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
1987 If we find such a factor, we can multiply by t using an algorithm that
1988 multiplies by q, shift the result by m and add/subtract it to itself.
1990 We search for large factors first and loop down, even if large factors
1991 are less probable than small; if we find a large factor we will find a
1992 good sequence quickly, and therefore be able to prune (by decreasing
1993 COST_LIMIT) the search. */
1995 for (m = floor_log2 (t - 1); m >= 2; m--)
1997 unsigned HOST_WIDE_INT d;
1999 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2000 if (t % d == 0 && t > d)
2002 cost = MIN (shiftadd_cost[m], add_cost + shift_cost[m]);
2003 synth_mult (alg_in, t / d, cost_limit - cost);
2005 cost += alg_in->cost;
2006 if (cost < cost_limit)
2008 struct algorithm *x;
2009 x = alg_in, alg_in = best_alg, best_alg = x;
2010 best_alg->log[best_alg->ops] = m;
2011 best_alg->op[best_alg->ops] = alg_add_factor;
2014 /* Other factors will have been taken care of in the recursion. */
2018 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2019 if (t % d == 0 && t > d)
2021 cost = MIN (shiftsub_cost[m], add_cost + shift_cost[m]);
2022 synth_mult (alg_in, t / d, cost_limit - cost);
2024 cost += alg_in->cost;
2025 if (cost < cost_limit)
2027 struct algorithm *x;
2028 x = alg_in, alg_in = best_alg, best_alg = x;
2029 best_alg->log[best_alg->ops] = m;
2030 best_alg->op[best_alg->ops] = alg_sub_factor;
2037 /* Try shift-and-add (load effective address) instructions,
2038 i.e. do a*3, a*5, a*9. */
2046 cost = shiftadd_cost[m];
2047 synth_mult (alg_in, (t - 1) >> m, cost_limit - cost);
2049 cost += alg_in->cost;
2050 if (cost < cost_limit)
2052 struct algorithm *x;
2053 x = alg_in, alg_in = best_alg, best_alg = x;
2054 best_alg->log[best_alg->ops] = m;
2055 best_alg->op[best_alg->ops] = alg_add_t2_m;
2065 cost = shiftsub_cost[m];
2066 synth_mult (alg_in, (t + 1) >> m, cost_limit - cost);
2068 cost += alg_in->cost;
2069 if (cost < cost_limit)
2071 struct algorithm *x;
2072 x = alg_in, alg_in = best_alg, best_alg = x;
2073 best_alg->log[best_alg->ops] = m;
2074 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2080 /* If cost_limit has not decreased since we stored it in alg_out->cost,
2081 we have not found any algorithm. */
2082 if (cost_limit == alg_out->cost)
2085 /* If we are getting a too long sequence for `struct algorithm'
2086 to record, make this search fail. */
2087 if (best_alg->ops == MAX_BITS_PER_WORD)
2090 /* Copy the algorithm from temporary space to the space at alg_out.
2091 We avoid using structure assignment because the majority of
2092 best_alg is normally undefined, and this is a critical function. */
2093 alg_out->ops = best_alg->ops + 1;
2094 alg_out->cost = cost_limit;
2095 bcopy ((char *) best_alg->op, (char *) alg_out->op,
2096 alg_out->ops * sizeof *alg_out->op);
2097 bcopy ((char *) best_alg->log, (char *) alg_out->log,
2098 alg_out->ops * sizeof *alg_out->log);
2101 /* Perform a multiplication and return an rtx for the result.
2102 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
2103 TARGET is a suggestion for where to store the result (an rtx).
2105 We check specially for a constant integer as OP1.
2106 If you want this check for OP0 as well, then before calling
2107 you should swap the two operands if OP0 would be constant. */
2110 expand_mult (mode, op0, op1, target, unsignedp)
2111 enum machine_mode mode;
2112 register rtx op0, op1, target;
2115 rtx const_op1 = op1;
2117 /* synth_mult does an `unsigned int' multiply. As long as the mode is
2118 less than or equal in size to `unsigned int' this doesn't matter.
2119 If the mode is larger than `unsigned int', then synth_mult works only
2120 if the constant value exactly fits in an `unsigned int' without any
2121 truncation. This means that multiplying by negative values does
2122 not work; results are off by 2^32 on a 32 bit machine. */
2124 /* If we are multiplying in DImode, it may still be a win
2125 to try to work with shifts and adds. */
2126 if (GET_CODE (op1) == CONST_DOUBLE
2127 && GET_MODE_CLASS (GET_MODE (op1)) == MODE_INT
2128 && HOST_BITS_PER_INT >= BITS_PER_WORD
2129 && CONST_DOUBLE_HIGH (op1) == 0)
2130 const_op1 = GEN_INT (CONST_DOUBLE_LOW (op1));
2131 else if (HOST_BITS_PER_INT < GET_MODE_BITSIZE (mode)
2132 && GET_CODE (op1) == CONST_INT
2133 && INTVAL (op1) < 0)
2136 /* We used to test optimize here, on the grounds that it's better to
2137 produce a smaller program when -O is not used.
2138 But this causes such a terrible slowdown sometimes
2139 that it seems better to use synth_mult always. */
2141 if (const_op1 && GET_CODE (const_op1) == CONST_INT)
2143 struct algorithm alg;
2144 struct algorithm alg2;
2145 HOST_WIDE_INT val = INTVAL (op1);
2146 HOST_WIDE_INT val_so_far;
2149 enum {basic_variant, negate_variant, add_variant} variant = basic_variant;
2151 /* Try to do the computation three ways: multiply by the negative of OP1
2152 and then negate, do the multiplication directly, or do multiplication
2155 mult_cost = rtx_cost (gen_rtx (MULT, mode, op0, op1), SET);
2156 mult_cost = MIN (12 * add_cost, mult_cost);
2158 synth_mult (&alg, val, mult_cost);
2160 /* This works only if the inverted value actually fits in an
2162 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2164 synth_mult (&alg2, - val,
2165 (alg.cost < mult_cost ? alg.cost : mult_cost) - negate_cost);
2166 if (alg2.cost + negate_cost < alg.cost)
2167 alg = alg2, variant = negate_variant;
2170 /* This proves very useful for division-by-constant. */
2171 synth_mult (&alg2, val - 1,
2172 (alg.cost < mult_cost ? alg.cost : mult_cost) - add_cost);
2173 if (alg2.cost + add_cost < alg.cost)
2174 alg = alg2, variant = add_variant;
2176 if (alg.cost < mult_cost)
2178 /* We found something cheaper than a multiply insn. */
2182 op0 = protect_from_queue (op0, 0);
2184 /* Avoid referencing memory over and over.
2185 For speed, but also for correctness when mem is volatile. */
2186 if (GET_CODE (op0) == MEM)
2187 op0 = force_reg (mode, op0);
2189 /* ACCUM starts out either as OP0 or as a zero, depending on
2190 the first operation. */
2192 if (alg.op[0] == alg_zero)
2194 accum = copy_to_mode_reg (mode, const0_rtx);
2197 else if (alg.op[0] == alg_m)
2199 accum = copy_to_mode_reg (mode, op0);
2205 for (opno = 1; opno < alg.ops; opno++)
2207 int log = alg.log[opno];
2208 int preserve = preserve_subexpressions_p ();
2209 rtx shift_subtarget = preserve ? 0 : accum;
2211 = (opno == alg.ops - 1 && target != 0 && variant != add_variant
2213 rtx accum_target = preserve ? 0 : accum;
2215 switch (alg.op[opno])
2218 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2219 build_int_2 (log, 0), NULL_RTX, 0);
2224 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2225 build_int_2 (log, 0), NULL_RTX, 0);
2226 accum = force_operand (gen_rtx (PLUS, mode, accum, tem),
2227 add_target ? add_target : accum_target);
2228 val_so_far += (HOST_WIDE_INT) 1 << log;
2232 tem = expand_shift (LSHIFT_EXPR, mode, op0,
2233 build_int_2 (log, 0), NULL_RTX, 0);
2234 accum = force_operand (gen_rtx (MINUS, mode, accum, tem),
2235 add_target ? add_target : accum_target);
2236 val_so_far -= (HOST_WIDE_INT) 1 << log;
2240 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2241 build_int_2 (log, 0), shift_subtarget,
2243 accum = force_operand (gen_rtx (PLUS, mode, accum, op0),
2244 add_target ? add_target : accum_target);
2245 val_so_far = (val_so_far << log) + 1;
2249 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2250 build_int_2 (log, 0), shift_subtarget,
2252 accum = force_operand (gen_rtx (MINUS, mode, accum, op0),
2253 add_target ? add_target : accum_target);
2254 val_so_far = (val_so_far << log) - 1;
2257 case alg_add_factor:
2258 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2259 build_int_2 (log, 0), NULL_RTX, 0);
2260 accum = force_operand (gen_rtx (PLUS, mode, accum, tem),
2261 add_target ? add_target : accum_target);
2262 val_so_far += val_so_far << log;
2265 case alg_sub_factor:
2266 tem = expand_shift (LSHIFT_EXPR, mode, accum,
2267 build_int_2 (log, 0), NULL_RTX, 0);
2268 accum = force_operand (gen_rtx (MINUS, mode, tem, accum),
2269 (add_target ? add_target
2270 : preserve ? 0 : tem));
2271 val_so_far = (val_so_far << log) - val_so_far;
2278 /* Write a REG_EQUAL note on the last insn so that we can cse
2279 multiplication sequences. */
2281 insn = get_last_insn ();
2283 = gen_rtx (EXPR_LIST, REG_EQUAL,
2284 gen_rtx (MULT, mode, op0, GEN_INT (val_so_far)),
2288 if (variant == negate_variant)
2290 val_so_far = - val_so_far;
2291 accum = expand_unop (mode, neg_optab, accum, target, 0);
2293 else if (variant == add_variant)
2295 val_so_far = val_so_far + 1;
2296 accum = force_operand (gen_rtx (PLUS, mode, accum, op0), target);
2299 if (val != val_so_far)
2306 /* This used to use umul_optab if unsigned, but for non-widening multiply
2307 there is no difference between signed and unsigned. */
2308 op0 = expand_binop (mode, smul_optab,
2309 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
2315 /* Return the smallest n such that 2**n >= X. */
2319 unsigned HOST_WIDE_INT x;
2321 return floor_log2 (x - 1) + 1;
2324 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
2325 replace division by D, and put the least significant N bits of the result
2326 in *MULTIPLIER_PTR and return the most significant bit.
2328 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
2329 needed precision is in PRECISION (should be <= N).
2331 PRECISION should be as small as possible so this function can choose
2332 multiplier more freely.
2334 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
2335 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
2337 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
2338 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
2341 unsigned HOST_WIDE_INT
2342 choose_multiplier (d, n, precision, multiplier_ptr, post_shift_ptr, lgup_ptr)
2343 unsigned HOST_WIDE_INT d;
2346 unsigned HOST_WIDE_INT *multiplier_ptr;
2347 int *post_shift_ptr;
2350 unsigned HOST_WIDE_INT mhigh_hi, mhigh_lo;
2351 unsigned HOST_WIDE_INT mlow_hi, mlow_lo;
2352 int lgup, post_shift;
2354 unsigned HOST_WIDE_INT nh, nl, dummy1, dummy2;
2356 /* lgup = ceil(log2(divisor)); */
2357 lgup = ceil_log2 (d);
2363 pow2 = n + lgup - precision;
2365 if (pow == 2 * HOST_BITS_PER_WIDE_INT)
2367 /* We could handle this with some effort, but this case is much better
2368 handled directly with a scc insn, so rely on caller using that. */
2372 /* mlow = 2^(N + lgup)/d */
2373 if (pow >= HOST_BITS_PER_WIDE_INT)
2375 nh = (unsigned HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
2381 nl = (unsigned HOST_WIDE_INT) 1 << pow;
2383 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2384 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
2386 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
2387 if (pow2 >= HOST_BITS_PER_WIDE_INT)
2388 nh |= (unsigned HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
2390 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
2391 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
2392 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
2394 if (mhigh_hi && nh - d >= d)
2396 if (mhigh_hi > 1 || mlow_hi > 1)
2398 /* assert that mlow < mhigh. */
2399 if (! (mlow_hi < mhigh_hi || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)))
2402 /* If precision == N, then mlow, mhigh exceed 2^N
2403 (but they do not exceed 2^(N+1)). */
2405 /* Reduce to lowest terms */
2406 for (post_shift = lgup; post_shift > 0; post_shift--)
2408 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
2409 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
2419 *post_shift_ptr = post_shift;
2421 if (n < HOST_BITS_PER_WIDE_INT)
2423 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
2424 *multiplier_ptr = mhigh_lo & mask;
2425 return mhigh_lo >= mask;
2429 *multiplier_ptr = mhigh_lo;
2434 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
2435 congruent to 1 (mod 2**N). */
2437 static unsigned HOST_WIDE_INT
2439 unsigned HOST_WIDE_INT x;
2442 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
2444 /* The algorithm notes that the choice y = x satisfies
2445 x*y == 1 mod 2^3, since x is assumed odd.
2446 Each iteration doubles the number of bits of significance in y. */
2448 unsigned HOST_WIDE_INT mask;
2449 unsigned HOST_WIDE_INT y = x;
2452 mask = (n == HOST_BITS_PER_WIDE_INT
2453 ? ~(unsigned HOST_WIDE_INT) 0
2454 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
2458 y = y * (2 - x*y) & mask; /* Modulo 2^N */
2464 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
2465 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
2466 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
2467 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
2470 The result is put in TARGET if that is convenient.
2472 MODE is the mode of operation. */
2475 expand_mult_highpart_adjust (mode, adj_operand, op0, op1, target, unsignedp)
2476 enum machine_mode mode;
2477 register rtx adj_operand, op0, op1, target;
2481 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
2483 tem = expand_shift (RSHIFT_EXPR, mode, op0,
2484 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2486 tem = expand_and (tem, op1, NULL_RTX);
2487 adj_operand = force_operand (gen_rtx (adj_code, mode, adj_operand, tem),
2490 tem = expand_shift (RSHIFT_EXPR, mode, op1,
2491 build_int_2 (GET_MODE_BITSIZE (mode) - 1, 0),
2493 tem = expand_and (tem, op0, NULL_RTX);
2494 target = force_operand (gen_rtx (adj_code, mode, adj_operand, tem), target);
2499 /* Emit code to multiply OP0 and CNST1, putting the high half of the result
2500 in TARGET if that is convenient, and return where the result is. If the
2501 operation can not be performed, 0 is returned.
2503 MODE is the mode of operation and result.
2505 UNSIGNEDP nonzero means unsigned multiply.
2507 MAX_COST is the total allowed cost for the expanded RTL. */
2510 expand_mult_highpart (mode, op0, cnst1, target, unsignedp, max_cost)
2511 enum machine_mode mode;
2512 register rtx op0, target;
2513 unsigned HOST_WIDE_INT cnst1;
2517 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
2518 optab mul_highpart_optab;
2521 int size = GET_MODE_BITSIZE (mode);
2524 /* We can't support modes wider than HOST_BITS_PER_INT. */
2525 if (size > HOST_BITS_PER_WIDE_INT)
2528 op1 = GEN_INT (cnst1);
2530 if (GET_MODE_BITSIZE (wider_mode) <= HOST_BITS_PER_INT)
2534 = immed_double_const (cnst1,
2537 : -(cnst1 >> (HOST_BITS_PER_WIDE_INT - 1))),
2540 /* expand_mult handles constant multiplication of word_mode
2541 or narrower. It does a poor job for large modes. */
2542 if (size < BITS_PER_WORD
2543 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2545 /* We have to do this, since expand_binop doesn't do conversion for
2546 multiply. Maybe change expand_binop to handle widening multiply? */
2547 op0 = convert_to_mode (wider_mode, op0, unsignedp);
2549 tem = expand_mult (wider_mode, op0, wide_op1, NULL_RTX, unsignedp);
2550 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2551 build_int_2 (size, 0), NULL_RTX, 1);
2552 return convert_modes (mode, wider_mode, tem, unsignedp);
2556 target = gen_reg_rtx (mode);
2558 /* Firstly, try using a multiplication insn that only generates the needed
2559 high part of the product, and in the sign flavor of unsignedp. */
2560 if (mul_highpart_cost[(int) mode] < max_cost)
2562 mul_highpart_optab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
2563 target = expand_binop (mode, mul_highpart_optab,
2564 op0, op1, target, unsignedp, OPTAB_DIRECT);
2569 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
2570 Need to adjust the result after the multiplication. */
2571 if (mul_highpart_cost[(int) mode] + 2 * shift_cost[size-1] + 4 * add_cost < max_cost)
2573 mul_highpart_optab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
2574 target = expand_binop (mode, mul_highpart_optab,
2575 op0, op1, target, unsignedp, OPTAB_DIRECT);
2577 /* We used the wrong signedness. Adjust the result. */
2578 return expand_mult_highpart_adjust (mode, target, op0,
2579 op1, target, unsignedp);
2582 /* Try widening multiplication. */
2583 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
2584 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2585 && mul_widen_cost[(int) wider_mode] < max_cost)
2588 /* Try widening the mode and perform a non-widening multiplication. */
2589 moptab = smul_optab;
2590 if (smul_optab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2591 && mul_cost[(int) wider_mode] + shift_cost[size-1] < max_cost)
2594 /* Try widening multiplication of opposite signedness, and adjust. */
2595 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
2596 if (moptab->handlers[(int) wider_mode].insn_code != CODE_FOR_nothing
2597 && (mul_widen_cost[(int) wider_mode]
2598 + 2 * shift_cost[size-1] + 4 * add_cost < max_cost))
2600 tem = expand_binop (wider_mode, moptab, op0, wide_op1,
2601 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
2604 /* Extract the high half of the just generated product. */
2605 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2606 build_int_2 (size, 0), NULL_RTX, 1);
2607 tem = convert_modes (mode, wider_mode, tem, unsignedp);
2608 /* We used the wrong signedness. Adjust the result. */
2609 return expand_mult_highpart_adjust (mode, tem, op0, op1,
2617 /* Pass NULL_RTX as target since TARGET has wrong mode. */
2618 tem = expand_binop (wider_mode, moptab, op0, wide_op1,
2619 NULL_RTX, unsignedp, OPTAB_WIDEN);
2623 /* Extract the high half of the just generated product. */
2624 tem = expand_shift (RSHIFT_EXPR, wider_mode, tem,
2625 build_int_2 (size, 0), NULL_RTX, 1);
2626 return convert_modes (mode, wider_mode, tem, unsignedp);
2629 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
2630 if that is convenient, and returning where the result is.
2631 You may request either the quotient or the remainder as the result;
2632 specify REM_FLAG nonzero to get the remainder.
2634 CODE is the expression code for which kind of division this is;
2635 it controls how rounding is done. MODE is the machine mode to use.
2636 UNSIGNEDP nonzero means do unsigned division. */
2638 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
2639 and then correct it by or'ing in missing high bits
2640 if result of ANDI is nonzero.
2641 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
2642 This could optimize to a bfexts instruction.
2643 But C doesn't use these operations, so their optimizations are
2646 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
2649 expand_divmod (rem_flag, code, mode, op0, op1, target, unsignedp)
2651 enum tree_code code;
2652 enum machine_mode mode;
2653 register rtx op0, op1, target;
2656 enum machine_mode compute_mode;
2657 register rtx tquotient;
2658 rtx quotient = 0, remainder = 0;
2662 optab optab1, optab2;
2663 int op1_is_constant, op1_is_pow2;
2664 int max_cost, extra_cost;
2666 op1_is_constant = GET_CODE (op1) == CONST_INT;
2667 op1_is_pow2 = (op1_is_constant
2668 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
2669 || EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))));
2672 This is the structure of expand_divmod:
2674 First comes code to fix up the operands so we can perform the operations
2675 correctly and efficiently.
2677 Second comes a switch statement with code specific for each rounding mode.
2678 For some special operands this code emits all RTL for the desired
2679 operation, for other cases, it generates only a quotient and stores it in
2680 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
2681 to indicate that it has not done anything.
2683 Last comes code that finishes the operation. If QUOTIENT is set and
2684 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
2685 QUOTIENT is not set, it is computed using trunc rounding.
2687 We try to generate special code for division and remainder when OP1 is a
2688 constant. If |OP1| = 2**n we can use shifts and some other fast
2689 operations. For other values of OP1, we compute a carefully selected
2690 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
2693 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
2694 half of the product. Different strategies for generating the product are
2695 implemented in expand_mult_highpart.
2697 If what we actually want is the remainder, we generate that by another
2698 by-constant multiplication and a subtraction. */
2700 /* We shouldn't be called with OP1 == const1_rtx, but some of the
2701 code below will malfunction if we are, so check here and handle
2702 the special case if so. */
2703 if (op1 == const1_rtx)
2704 return rem_flag ? const0_rtx : op0;
2707 /* Don't use the function value register as a target
2708 since we have to read it as well as write it,
2709 and function-inlining gets confused by this. */
2710 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
2711 /* Don't clobber an operand while doing a multi-step calculation. */
2712 || ((rem_flag || op1_is_constant)
2713 && (reg_mentioned_p (target, op0)
2714 || (GET_CODE (op0) == MEM && GET_CODE (target) == MEM)))
2715 || reg_mentioned_p (target, op1)
2716 || (GET_CODE (op1) == MEM && GET_CODE (target) == MEM)))
2719 /* Get the mode in which to perform this computation. Normally it will
2720 be MODE, but sometimes we can't do the desired operation in MODE.
2721 If so, pick a wider mode in which we can do the operation. Convert
2722 to that mode at the start to avoid repeated conversions.
2724 First see what operations we need. These depend on the expression
2725 we are evaluating. (We assume that divxx3 insns exist under the
2726 same conditions that modxx3 insns and that these insns don't normally
2727 fail. If these assumptions are not correct, we may generate less
2728 efficient code in some cases.)
2730 Then see if we find a mode in which we can open-code that operation
2731 (either a division, modulus, or shift). Finally, check for the smallest
2732 mode for which we can do the operation with a library call. */
2734 /* We might want to refine this now that we have division-by-constant
2735 optimization. Since expand_mult_highpart tries so many variants, it is
2736 not straightforward to generalize this. Maybe we should make an array
2737 of possible modes in init_expmed? Save this for GCC 2.7. */
2739 optab1 = (op1_is_pow2 ? (unsignedp ? lshr_optab : ashr_optab)
2740 : (unsignedp ? udiv_optab : sdiv_optab));
2741 optab2 = (op1_is_pow2 ? optab1 : (unsignedp ? udivmod_optab : sdivmod_optab));
2743 for (compute_mode = mode; compute_mode != VOIDmode;
2744 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2745 if (optab1->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing
2746 || optab2->handlers[(int) compute_mode].insn_code != CODE_FOR_nothing)
2749 if (compute_mode == VOIDmode)
2750 for (compute_mode = mode; compute_mode != VOIDmode;
2751 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
2752 if (optab1->handlers[(int) compute_mode].libfunc
2753 || optab2->handlers[(int) compute_mode].libfunc)
2756 /* If we still couldn't find a mode, use MODE, but we'll probably abort
2758 if (compute_mode == VOIDmode)
2759 compute_mode = mode;
2761 if (target && GET_MODE (target) == compute_mode)
2764 tquotient = gen_reg_rtx (compute_mode);
2766 size = GET_MODE_BITSIZE (compute_mode);
2768 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
2769 (mode), and thereby get better code when OP1 is a constant. Do that
2770 later. It will require going over all usages of SIZE below. */
2771 size = GET_MODE_BITSIZE (mode);
2774 max_cost = div_cost[(int) compute_mode]
2775 - (rem_flag ? mul_cost[(int) compute_mode] + add_cost : 0);
2777 /* Now convert to the best mode to use. */
2778 if (compute_mode != mode)
2780 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
2781 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
2784 /* If one of the operands is a volatile MEM, copy it into a register. */
2786 if (GET_CODE (op0) == MEM && MEM_VOLATILE_P (op0))
2787 op0 = force_reg (compute_mode, op0);
2788 if (GET_CODE (op1) == MEM && MEM_VOLATILE_P (op1))
2789 op1 = force_reg (compute_mode, op1);
2791 /* If we need the remainder or if OP1 is constant, we need to
2792 put OP0 in a register in case it has any queued subexpressions. */
2793 if (rem_flag || op1_is_constant)
2794 op0 = force_reg (compute_mode, op0);
2796 last = get_last_insn ();
2798 /* Promote floor rouding to trunc rounding for unsigned operations. */
2801 if (code == FLOOR_DIV_EXPR)
2802 code = TRUNC_DIV_EXPR;
2803 if (code == FLOOR_MOD_EXPR)
2804 code = TRUNC_MOD_EXPR;
2807 if (op1 != const0_rtx)
2810 case TRUNC_MOD_EXPR:
2811 case TRUNC_DIV_EXPR:
2812 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
2816 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (compute_mode) - 1)))
2818 unsigned HOST_WIDE_INT mh, ml;
2819 int pre_shift, post_shift;
2821 unsigned HOST_WIDE_INT d = INTVAL (op1);
2823 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
2825 pre_shift = floor_log2 (d);
2828 remainder = expand_binop (compute_mode, and_optab, op0,
2829 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
2833 return gen_lowpart (mode, remainder);
2835 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
2836 build_int_2 (pre_shift, 0),
2839 else if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
2841 /* Most significant bit of divisor is set, emit a scc insn.
2842 emit_store_flag needs to be passed a place for the
2844 quotient = emit_store_flag (tquotient, GEU, op0, op1,
2845 compute_mode, 1, 1);
2846 /* Can emit_store_flag have failed? */
2852 /* Find a suitable multiplier and right shift count instead
2853 of multiplying with D. */
2855 mh = choose_multiplier (d, size, size,
2856 &ml, &post_shift, &dummy);
2858 /* If the suggested multiplier is more than SIZE bits, we
2859 can do better for even divisors, using an initial right
2861 if (mh != 0 && (d & 1) == 0)
2863 pre_shift = floor_log2 (d & -d);
2864 mh = choose_multiplier (d >> pre_shift, size,
2866 &ml, &post_shift, &dummy);
2877 extra_cost = (shift_cost[post_shift - 1]
2878 + shift_cost[1] + 2 * add_cost);
2879 t1 = expand_mult_highpart (compute_mode, op0, ml,
2881 max_cost - extra_cost);
2884 t2 = force_operand (gen_rtx (MINUS, compute_mode,
2887 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
2888 build_int_2 (1, 0), NULL_RTX, 1);
2889 t4 = force_operand (gen_rtx (PLUS, compute_mode,
2892 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t4,
2893 build_int_2 (post_shift - 1,
2901 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
2902 build_int_2 (pre_shift, 0),
2904 extra_cost = (shift_cost[pre_shift]
2905 + shift_cost[post_shift]);
2906 t2 = expand_mult_highpart (compute_mode, t1, ml,
2908 max_cost - extra_cost);
2911 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t2,
2912 build_int_2 (post_shift, 0),
2917 insn = get_last_insn ();
2919 && (set = single_set (insn)) != 0
2920 && SET_DEST (set) == quotient)
2922 = gen_rtx (EXPR_LIST, REG_EQUAL,
2923 gen_rtx (UDIV, compute_mode, op0, op1),
2926 else /* TRUNC_DIV, signed */
2928 unsigned HOST_WIDE_INT ml;
2929 int lgup, post_shift;
2930 HOST_WIDE_INT d = INTVAL (op1);
2931 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d;
2933 /* n rem d = n rem -d */
2934 if (rem_flag && d < 0)
2937 op1 = GEN_INT (abs_d);
2943 quotient = expand_unop (compute_mode, neg_optab, op0,
2945 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
2946 && (rem_flag ? smod_pow2_cheap : sdiv_pow2_cheap))
2948 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
2950 lgup = floor_log2 (abs_d);
2951 if (abs_d != 2 && BRANCH_COST < 3)
2953 rtx label = gen_label_rtx ();
2956 t1 = copy_to_mode_reg (compute_mode, op0);
2957 emit_cmp_insn (t1, const0_rtx, GE,
2958 NULL_RTX, compute_mode, 0, 0);
2959 emit_jump_insn (gen_bge (label));
2960 expand_inc (t1, GEN_INT (abs_d - 1));
2962 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
2963 build_int_2 (lgup, 0),
2969 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
2970 build_int_2 (size - 1, 0),
2972 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
2973 build_int_2 (size - lgup, 0),
2975 t3 = force_operand (gen_rtx (PLUS, compute_mode,
2978 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t3,
2979 build_int_2 (lgup, 0),
2983 /* We have computed OP0 / abs(OP1). If OP1 is negative, negate
2987 insn = get_last_insn ();
2989 && (set = single_set (insn)) != 0
2990 && SET_DEST (set) == quotient)
2992 = gen_rtx (EXPR_LIST, REG_EQUAL,
2993 gen_rtx (DIV, compute_mode, op0,
2997 quotient = expand_unop (compute_mode, neg_optab,
2998 quotient, quotient, 0);
3003 choose_multiplier (abs_d, size, size - 1,
3004 &ml, &post_shift, &lgup);
3005 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
3009 extra_cost = (shift_cost[post_shift]
3010 + shift_cost[size - 1] + add_cost);
3011 t1 = expand_mult_highpart (compute_mode, op0, ml,
3013 max_cost - extra_cost);
3016 t2 = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3017 build_int_2 (post_shift, 0), NULL_RTX, 0);
3018 t3 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3019 build_int_2 (size - 1, 0), NULL_RTX, 0);
3021 quotient = force_operand (gen_rtx (MINUS, compute_mode, t3, t2),
3024 quotient = force_operand (gen_rtx (MINUS, compute_mode, t2, t3),
3031 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
3032 extra_cost = (shift_cost[post_shift]
3033 + shift_cost[size - 1] + 2 * add_cost);
3034 t1 = expand_mult_highpart (compute_mode, op0, ml,
3036 max_cost - extra_cost);
3039 t2 = force_operand (gen_rtx (PLUS, compute_mode, t1, op0),
3041 t3 = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3042 build_int_2 (post_shift, 0), NULL_RTX, 0);
3043 t4 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3044 build_int_2 (size - 1, 0), NULL_RTX, 0);
3046 quotient = force_operand (gen_rtx (MINUS, compute_mode, t4, t3),
3049 quotient = force_operand (gen_rtx (MINUS, compute_mode, t3, t4),
3054 insn = get_last_insn ();
3056 && (set = single_set (insn)) != 0
3057 && SET_DEST (set) == quotient)
3059 = gen_rtx (EXPR_LIST, REG_EQUAL,
3060 gen_rtx (DIV, compute_mode, op0, op1),
3066 delete_insns_since (last);
3069 case FLOOR_DIV_EXPR:
3070 case FLOOR_MOD_EXPR:
3071 /* We will come here only for signed operations. */
3072 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3074 unsigned HOST_WIDE_INT mh, ml;
3075 int pre_shift, lgup, post_shift;
3076 HOST_WIDE_INT d = INTVAL (op1);
3080 /* We could just as easily deal with negative constants here,
3081 but it does not seem worth the trouble for GCC 2.6. */
3082 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
3084 pre_shift = floor_log2 (d);
3087 remainder = expand_binop (compute_mode, and_optab, op0,
3088 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
3089 remainder, 0, OPTAB_LIB_WIDEN);
3091 return gen_lowpart (mode, remainder);
3093 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3094 build_int_2 (pre_shift, 0),
3101 mh = choose_multiplier (d, size, size - 1,
3102 &ml, &post_shift, &lgup);
3106 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3107 build_int_2 (size - 1, 0), NULL_RTX, 0);
3108 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
3109 NULL_RTX, 0, OPTAB_WIDEN);
3110 extra_cost = (shift_cost[post_shift]
3111 + shift_cost[size - 1] + 2 * add_cost);
3112 t3 = expand_mult_highpart (compute_mode, t2, ml,
3114 max_cost - extra_cost);
3117 t4 = expand_shift (RSHIFT_EXPR, compute_mode, t3,
3118 build_int_2 (post_shift, 0),
3120 quotient = expand_binop (compute_mode, xor_optab,
3121 t4, t1, tquotient, 0,
3128 rtx nsign, t1, t2, t3, t4;
3129 t1 = force_operand (gen_rtx (PLUS, compute_mode,
3130 op0, constm1_rtx), NULL_RTX);
3131 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
3133 nsign = expand_shift (RSHIFT_EXPR, compute_mode, t2,
3134 build_int_2 (size - 1, 0), NULL_RTX, 0);
3135 t3 = force_operand (gen_rtx (MINUS, compute_mode, t1, nsign),
3137 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
3142 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
3144 quotient = force_operand (gen_rtx (PLUS, compute_mode,
3153 delete_insns_since (last);
3155 /* Try using an instruction that produces both the quotient and
3156 remainder, using truncation. We can easily compensate the quotient
3157 or remainder to get floor rounding, once we have the remainder.
3158 Notice that we compute also the final remainder value here,
3159 and return the result right away. */
3161 target = gen_reg_rtx (compute_mode);
3166 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3167 quotient = gen_reg_rtx (compute_mode);
3172 = GET_CODE (target) == REG ? target : gen_reg_rtx (compute_mode);
3173 remainder = gen_reg_rtx (compute_mode);
3176 if (expand_twoval_binop (sdivmod_optab, op0, op1,
3177 quotient, remainder, 0))
3179 /* This could be computed with a branch-less sequence.
3180 Save that for later. */
3182 rtx label = gen_label_rtx ();
3183 emit_cmp_insn (remainder, const0_rtx, EQ, NULL_RTX,
3184 compute_mode, 0, 0);
3185 emit_jump_insn (gen_beq (label));
3186 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3187 NULL_RTX, 0, OPTAB_WIDEN);
3188 emit_cmp_insn (tem, const0_rtx, GE, NULL_RTX, compute_mode, 0, 0);
3189 emit_jump_insn (gen_bge (label));
3190 expand_dec (quotient, const1_rtx);
3191 expand_inc (remainder, op1);
3193 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3196 /* No luck with division elimination or divmod. Have to do it
3197 by conditionally adjusting op0 *and* the result. */
3199 rtx label1, label2, label3, label4, label5;
3203 quotient = gen_reg_rtx (compute_mode);
3204 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3205 label1 = gen_label_rtx ();
3206 label2 = gen_label_rtx ();
3207 label3 = gen_label_rtx ();
3208 label4 = gen_label_rtx ();
3209 label5 = gen_label_rtx ();
3210 emit_cmp_insn (op1, const0_rtx, LT, NULL_RTX, compute_mode, 0, 0);
3211 emit_jump_insn (gen_blt (label2));
3212 emit_cmp_insn (adjusted_op0, const0_rtx, LT, NULL_RTX,
3213 compute_mode, 0, 0);
3214 emit_jump_insn (gen_blt (label1));
3215 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3216 quotient, 0, OPTAB_LIB_WIDEN);
3217 if (tem != quotient)
3218 emit_move_insn (quotient, tem);
3219 emit_jump_insn (gen_jump (label5));
3221 emit_label (label1);
3222 expand_inc (adjusted_op0, const1_rtx);
3223 emit_jump_insn (gen_jump (label4));
3225 emit_label (label2);
3226 emit_cmp_insn (adjusted_op0, const0_rtx, GT, NULL_RTX,
3227 compute_mode, 0, 0);
3228 emit_jump_insn (gen_bgt (label3));
3229 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3230 quotient, 0, OPTAB_LIB_WIDEN);
3231 if (tem != quotient)
3232 emit_move_insn (quotient, tem);
3233 emit_jump_insn (gen_jump (label5));
3235 emit_label (label3);
3236 expand_dec (adjusted_op0, const1_rtx);
3237 emit_label (label4);
3238 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3239 quotient, 0, OPTAB_LIB_WIDEN);
3240 if (tem != quotient)
3241 emit_move_insn (quotient, tem);
3242 expand_dec (quotient, const1_rtx);
3243 emit_label (label5);
3251 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
3254 unsigned HOST_WIDE_INT d = INTVAL (op1);
3255 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3256 build_int_2 (floor_log2 (d), 0),
3258 t2 = expand_binop (compute_mode, and_optab, op0,
3260 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3261 t3 = gen_reg_rtx (compute_mode);
3262 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3263 compute_mode, 1, 1);
3267 lab = gen_label_rtx ();
3268 emit_cmp_insn (t2, const0_rtx, EQ, NULL_RTX,
3269 compute_mode, 0, 0);
3270 emit_jump_insn (gen_beq (lab));
3271 expand_inc (t1, const1_rtx);
3276 quotient = force_operand (gen_rtx (PLUS, compute_mode,
3282 /* Try using an instruction that produces both the quotient and
3283 remainder, using truncation. We can easily compensate the
3284 quotient or remainder to get ceiling rounding, once we have the
3285 remainder. Notice that we compute also the final remainder
3286 value here, and return the result right away. */
3288 target = gen_reg_rtx (compute_mode);
3292 remainder = (GET_CODE (target) == REG
3293 ? target : gen_reg_rtx (compute_mode));
3294 quotient = gen_reg_rtx (compute_mode);
3298 quotient = (GET_CODE (target) == REG
3299 ? target : gen_reg_rtx (compute_mode));
3300 remainder = gen_reg_rtx (compute_mode);
3303 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
3306 /* This could be computed with a branch-less sequence.
3307 Save that for later. */
3308 rtx label = gen_label_rtx ();
3309 emit_cmp_insn (remainder, const0_rtx, EQ, NULL_RTX,
3310 compute_mode, 0, 0);
3311 emit_jump_insn (gen_beq (label));
3312 expand_inc (quotient, const1_rtx);
3313 expand_dec (remainder, op1);
3315 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3318 /* No luck with division elimination or divmod. Have to do it
3319 by conditionally adjusting op0 *and* the result. */
3322 rtx adjusted_op0, tem;
3324 quotient = gen_reg_rtx (compute_mode);
3325 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3326 label1 = gen_label_rtx ();
3327 label2 = gen_label_rtx ();
3328 emit_cmp_insn (adjusted_op0, const0_rtx, NE, NULL_RTX,
3329 compute_mode, 0, 0);
3330 emit_jump_insn (gen_bne (label1));
3331 emit_move_insn (quotient, const0_rtx);
3332 emit_jump_insn (gen_jump (label2));
3334 emit_label (label1);
3335 expand_dec (adjusted_op0, const1_rtx);
3336 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
3337 quotient, 1, OPTAB_LIB_WIDEN);
3338 if (tem != quotient)
3339 emit_move_insn (quotient, tem);
3340 expand_inc (quotient, const1_rtx);
3341 emit_label (label2);
3346 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3347 && INTVAL (op1) >= 0)
3349 /* This is extremely similar to the code for the unsigned case
3350 above. For 2.7 we should merge these variants, but for
3351 2.6.1 I don't want to touch the code for unsigned since that
3352 get used in C. The signed case will only be used by other
3356 unsigned HOST_WIDE_INT d = INTVAL (op1);
3357 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
3358 build_int_2 (floor_log2 (d), 0),
3360 t2 = expand_binop (compute_mode, and_optab, op0,
3362 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3363 t3 = gen_reg_rtx (compute_mode);
3364 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
3365 compute_mode, 1, 1);
3369 lab = gen_label_rtx ();
3370 emit_cmp_insn (t2, const0_rtx, EQ, NULL_RTX,
3371 compute_mode, 0, 0);
3372 emit_jump_insn (gen_beq (lab));
3373 expand_inc (t1, const1_rtx);
3378 quotient = force_operand (gen_rtx (PLUS, compute_mode,
3384 /* Try using an instruction that produces both the quotient and
3385 remainder, using truncation. We can easily compensate the
3386 quotient or remainder to get ceiling rounding, once we have the
3387 remainder. Notice that we compute also the final remainder
3388 value here, and return the result right away. */
3390 target = gen_reg_rtx (compute_mode);
3393 remainder= (GET_CODE (target) == REG
3394 ? target : gen_reg_rtx (compute_mode));
3395 quotient = gen_reg_rtx (compute_mode);
3399 quotient = (GET_CODE (target) == REG
3400 ? target : gen_reg_rtx (compute_mode));
3401 remainder = gen_reg_rtx (compute_mode);
3404 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
3407 /* This could be computed with a branch-less sequence.
3408 Save that for later. */
3410 rtx label = gen_label_rtx ();
3411 emit_cmp_insn (remainder, const0_rtx, EQ, NULL_RTX,
3412 compute_mode, 0, 0);
3413 emit_jump_insn (gen_beq (label));
3414 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3415 NULL_RTX, 0, OPTAB_WIDEN);
3416 emit_cmp_insn (tem, const0_rtx, LT, NULL_RTX,
3417 compute_mode, 0, 0);
3418 emit_jump_insn (gen_blt (label));
3419 expand_inc (quotient, const1_rtx);
3420 expand_dec (remainder, op1);
3422 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3425 /* No luck with division elimination or divmod. Have to do it
3426 by conditionally adjusting op0 *and* the result. */
3428 rtx label1, label2, label3, label4, label5;
3432 quotient = gen_reg_rtx (compute_mode);
3433 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
3434 label1 = gen_label_rtx ();
3435 label2 = gen_label_rtx ();
3436 label3 = gen_label_rtx ();
3437 label4 = gen_label_rtx ();
3438 label5 = gen_label_rtx ();
3439 emit_cmp_insn (op1, const0_rtx, LT, NULL_RTX,
3440 compute_mode, 0, 0);
3441 emit_jump_insn (gen_blt (label2));
3442 emit_cmp_insn (adjusted_op0, const0_rtx, GT, NULL_RTX,
3443 compute_mode, 0, 0);
3444 emit_jump_insn (gen_bgt (label1));
3445 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3446 quotient, 0, OPTAB_LIB_WIDEN);
3447 if (tem != quotient)
3448 emit_move_insn (quotient, tem);
3449 emit_jump_insn (gen_jump (label5));
3451 emit_label (label1);
3452 expand_dec (adjusted_op0, const1_rtx);
3453 emit_jump_insn (gen_jump (label4));
3455 emit_label (label2);
3456 emit_cmp_insn (adjusted_op0, const0_rtx, LT, NULL_RTX,
3457 compute_mode, 0, 0);
3458 emit_jump_insn (gen_blt (label3));
3459 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3460 quotient, 0, OPTAB_LIB_WIDEN);
3461 if (tem != quotient)
3462 emit_move_insn (quotient, tem);
3463 emit_jump_insn (gen_jump (label5));
3465 emit_label (label3);
3466 expand_inc (adjusted_op0, const1_rtx);
3467 emit_label (label4);
3468 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
3469 quotient, 0, OPTAB_LIB_WIDEN);
3470 if (tem != quotient)
3471 emit_move_insn (quotient, tem);
3472 expand_inc (quotient, const1_rtx);
3473 emit_label (label5);
3478 case EXACT_DIV_EXPR:
3479 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
3481 HOST_WIDE_INT d = INTVAL (op1);
3482 unsigned HOST_WIDE_INT ml;
3486 post_shift = floor_log2 (d & -d);
3487 ml = invert_mod2n (d >> post_shift, size);
3488 t1 = expand_mult (compute_mode, op0, GEN_INT (ml), NULL_RTX,
3490 quotient = expand_shift (RSHIFT_EXPR, compute_mode, t1,
3491 build_int_2 (post_shift, 0),
3492 NULL_RTX, unsignedp);
3494 insn = get_last_insn ();
3496 = gen_rtx (EXPR_LIST, REG_EQUAL,
3497 gen_rtx (unsignedp ? UDIV : DIV, compute_mode,
3503 case ROUND_DIV_EXPR:
3504 case ROUND_MOD_EXPR:
3509 label = gen_label_rtx ();
3510 quotient = gen_reg_rtx (compute_mode);
3511 remainder = gen_reg_rtx (compute_mode);
3512 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
3515 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
3516 quotient, 1, OPTAB_LIB_WIDEN);
3517 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
3518 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3519 remainder, 1, OPTAB_LIB_WIDEN);
3521 tem = plus_constant (op1, -1);
3522 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3523 build_int_2 (1, 0), NULL_RTX, 1);
3524 emit_cmp_insn (remainder, tem, LEU, NULL_RTX, compute_mode, 0, 0);
3525 emit_jump_insn (gen_bleu (label));
3526 expand_inc (quotient, const1_rtx);
3527 expand_dec (remainder, op1);
3532 rtx abs_rem, abs_op1, tem, mask;
3534 label = gen_label_rtx ();
3535 quotient = gen_reg_rtx (compute_mode);
3536 remainder = gen_reg_rtx (compute_mode);
3537 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
3540 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
3541 quotient, 0, OPTAB_LIB_WIDEN);
3542 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
3543 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
3544 remainder, 0, OPTAB_LIB_WIDEN);
3546 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 0, 0);
3547 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 0, 0);
3548 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
3549 build_int_2 (1, 0), NULL_RTX, 1);
3550 emit_cmp_insn (tem, abs_op1, LTU, NULL_RTX, compute_mode, 0, 0);
3551 emit_jump_insn (gen_bltu (label));
3552 tem = expand_binop (compute_mode, xor_optab, op0, op1,
3553 NULL_RTX, 0, OPTAB_WIDEN);
3554 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
3555 build_int_2 (size - 1, 0), NULL_RTX, 0);
3556 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
3557 NULL_RTX, 0, OPTAB_WIDEN);
3558 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3559 NULL_RTX, 0, OPTAB_WIDEN);
3560 expand_inc (quotient, tem);
3561 tem = expand_binop (compute_mode, xor_optab, mask, op1,
3562 NULL_RTX, 0, OPTAB_WIDEN);
3563 tem = expand_binop (compute_mode, sub_optab, tem, mask,
3564 NULL_RTX, 0, OPTAB_WIDEN);
3565 expand_dec (remainder, tem);
3568 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3575 /* Try to produce the remainder directly without a library call. */
3576 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3578 unsignedp, OPTAB_WIDEN);
3581 /* No luck there. Can we do remainder and divide at once
3582 without a library call? */
3583 remainder = gen_reg_rtx (compute_mode);
3584 if (! expand_twoval_binop ((unsignedp
3588 NULL_RTX, remainder, unsignedp))
3593 return gen_lowpart (mode, remainder);
3596 /* Produce the quotient. */
3597 /* Try a quotient insn, but not a library call. */
3598 quotient = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
3599 op0, op1, rem_flag ? NULL_RTX : target,
3600 unsignedp, OPTAB_WIDEN);
3603 /* No luck there. Try a quotient-and-remainder insn,
3604 keeping the quotient alone. */
3605 quotient = gen_reg_rtx (compute_mode);
3606 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
3608 quotient, NULL_RTX, unsignedp))
3612 /* Still no luck. If we are not computing the remainder,
3613 use a library call for the quotient. */
3614 quotient = sign_expand_binop (compute_mode,
3615 udiv_optab, sdiv_optab,
3617 unsignedp, OPTAB_LIB_WIDEN);
3625 /* No divide instruction either. Use library for remainder. */
3626 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
3628 unsignedp, OPTAB_LIB_WIDEN);
3631 /* We divided. Now finish doing X - Y * (X / Y). */
3632 remainder = expand_mult (compute_mode, quotient, op1,
3633 NULL_RTX, unsignedp);
3634 remainder = expand_binop (compute_mode, sub_optab, op0,
3635 remainder, target, unsignedp,
3640 return gen_lowpart (mode, rem_flag ? remainder : quotient);
3643 /* Return a tree node with data type TYPE, describing the value of X.
3644 Usually this is an RTL_EXPR, if there is no obvious better choice.
3645 X may be an expression, however we only support those expressions
3646 generated by loop.c. */
3655 switch (GET_CODE (x))
3658 t = build_int_2 (INTVAL (x),
3659 TREE_UNSIGNED (type) || INTVAL (x) >= 0 ? 0 : -1);
3660 TREE_TYPE (t) = type;
3664 if (GET_MODE (x) == VOIDmode)
3666 t = build_int_2 (CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
3667 TREE_TYPE (t) = type;
3673 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
3674 t = build_real (type, d);
3680 return fold (build (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
3681 make_tree (type, XEXP (x, 1))));
3684 return fold (build (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
3685 make_tree (type, XEXP (x, 1))));
3688 return fold (build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))));
3691 return fold (build (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
3692 make_tree (type, XEXP (x, 1))));
3695 return fold (build (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
3696 make_tree (type, XEXP (x, 1))));
3699 return fold (convert (type,
3700 build (RSHIFT_EXPR, unsigned_type (type),
3701 make_tree (unsigned_type (type),
3703 make_tree (type, XEXP (x, 1)))));
3706 return fold (convert (type,
3707 build (RSHIFT_EXPR, signed_type (type),
3708 make_tree (signed_type (type), XEXP (x, 0)),
3709 make_tree (type, XEXP (x, 1)))));
3712 if (TREE_CODE (type) != REAL_TYPE)
3713 t = signed_type (type);
3717 return fold (convert (type,
3718 build (TRUNC_DIV_EXPR, t,
3719 make_tree (t, XEXP (x, 0)),
3720 make_tree (t, XEXP (x, 1)))));
3722 t = unsigned_type (type);
3723 return fold (convert (type,
3724 build (TRUNC_DIV_EXPR, t,
3725 make_tree (t, XEXP (x, 0)),
3726 make_tree (t, XEXP (x, 1)))));
3728 t = make_node (RTL_EXPR);
3729 TREE_TYPE (t) = type;
3730 RTL_EXPR_RTL (t) = x;
3731 /* There are no insns to be output
3732 when this rtl_expr is used. */
3733 RTL_EXPR_SEQUENCE (t) = 0;
3738 /* Return an rtx representing the value of X * MULT + ADD.
3739 TARGET is a suggestion for where to store the result (an rtx).
3740 MODE is the machine mode for the computation.
3741 X and MULT must have mode MODE. ADD may have a different mode.
3742 So can X (defaults to same as MODE).
3743 UNSIGNEDP is non-zero to do unsigned multiplication.
3744 This may emit insns. */
3747 expand_mult_add (x, target, mult, add, mode, unsignedp)
3748 rtx x, target, mult, add;
3749 enum machine_mode mode;
3752 tree type = type_for_mode (mode, unsignedp);
3753 tree add_type = (GET_MODE (add) == VOIDmode
3754 ? type : type_for_mode (GET_MODE (add), unsignedp));
3755 tree result = fold (build (PLUS_EXPR, type,
3756 fold (build (MULT_EXPR, type,
3757 make_tree (type, x),
3758 make_tree (type, mult))),
3759 make_tree (add_type, add)));
3761 return expand_expr (result, target, VOIDmode, 0);
3764 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
3765 and returning TARGET.
3767 If TARGET is 0, a pseudo-register or constant is returned. */
3770 expand_and (op0, op1, target)
3771 rtx op0, op1, target;
3773 enum machine_mode mode = VOIDmode;
3776 if (GET_MODE (op0) != VOIDmode)
3777 mode = GET_MODE (op0);
3778 else if (GET_MODE (op1) != VOIDmode)
3779 mode = GET_MODE (op1);
3781 if (mode != VOIDmode)
3782 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
3783 else if (GET_CODE (op0) == CONST_INT && GET_CODE (op1) == CONST_INT)
3784 tem = GEN_INT (INTVAL (op0) & INTVAL (op1));
3790 else if (tem != target)
3791 emit_move_insn (target, tem);
3795 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
3796 and storing in TARGET. Normally return TARGET.
3797 Return 0 if that cannot be done.
3799 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
3800 it is VOIDmode, they cannot both be CONST_INT.
3802 UNSIGNEDP is for the case where we have to widen the operands
3803 to perform the operation. It says to use zero-extension.
3805 NORMALIZEP is 1 if we should convert the result to be either zero
3806 or one one. Normalize is -1 if we should convert the result to be
3807 either zero or -1. If NORMALIZEP is zero, the result will be left
3808 "raw" out of the scc insn. */
3811 emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep)
3815 enum machine_mode mode;
3820 enum insn_code icode;
3821 enum machine_mode compare_mode;
3822 enum machine_mode target_mode = GET_MODE (target);
3825 rtx pattern, comparison;
3827 /* If one operand is constant, make it the second one. Only do this
3828 if the other operand is not constant as well. */
3830 if ((CONSTANT_P (op0) && ! CONSTANT_P (op1))
3831 || (GET_CODE (op0) == CONST_INT && GET_CODE (op1) != CONST_INT))
3836 code = swap_condition (code);
3839 if (mode == VOIDmode)
3840 mode = GET_MODE (op0);
3842 /* For some comparisons with 1 and -1, we can convert this to
3843 comparisons with zero. This will often produce more opportunities for
3844 store-flag insns. */
3849 if (op1 == const1_rtx)
3850 op1 = const0_rtx, code = LE;
3853 if (op1 == constm1_rtx)
3854 op1 = const0_rtx, code = LT;
3857 if (op1 == const1_rtx)
3858 op1 = const0_rtx, code = GT;
3861 if (op1 == constm1_rtx)
3862 op1 = const0_rtx, code = GE;
3865 if (op1 == const1_rtx)
3866 op1 = const0_rtx, code = NE;
3869 if (op1 == const1_rtx)
3870 op1 = const0_rtx, code = EQ;
3874 /* From now on, we won't change CODE, so set ICODE now. */
3875 icode = setcc_gen_code[(int) code];
3877 /* If this is A < 0 or A >= 0, we can do this by taking the ones
3878 complement of A (for GE) and shifting the sign bit to the low bit. */
3879 if (op1 == const0_rtx && (code == LT || code == GE)
3880 && GET_MODE_CLASS (mode) == MODE_INT
3881 && (normalizep || STORE_FLAG_VALUE == 1
3882 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
3883 && (STORE_FLAG_VALUE
3884 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))))
3888 /* If the result is to be wider than OP0, it is best to convert it
3889 first. If it is to be narrower, it is *incorrect* to convert it
3891 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
3893 op0 = protect_from_queue (op0, 0);
3894 op0 = convert_modes (target_mode, mode, op0, 0);
3898 if (target_mode != mode)
3902 op0 = expand_unop (mode, one_cmpl_optab, op0, subtarget, 0);
3904 if (normalizep || STORE_FLAG_VALUE == 1)
3905 /* If we are supposed to produce a 0/1 value, we want to do
3906 a logical shift from the sign bit to the low-order bit; for
3907 a -1/0 value, we do an arithmetic shift. */
3908 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
3909 size_int (GET_MODE_BITSIZE (mode) - 1),
3910 subtarget, normalizep != -1);
3912 if (mode != target_mode)
3913 op0 = convert_modes (target_mode, mode, op0, 0);
3918 if (icode != CODE_FOR_nothing)
3920 /* We think we may be able to do this with a scc insn. Emit the
3921 comparison and then the scc insn.
3923 compare_from_rtx may call emit_queue, which would be deleted below
3924 if the scc insn fails. So call it ourselves before setting LAST. */
3927 last = get_last_insn ();
3930 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX, 0);
3931 if (GET_CODE (comparison) == CONST_INT)
3932 return (comparison == const0_rtx ? const0_rtx
3933 : normalizep == 1 ? const1_rtx
3934 : normalizep == -1 ? constm1_rtx
3937 /* If the code of COMPARISON doesn't match CODE, something is
3938 wrong; we can no longer be sure that we have the operation.
3939 We could handle this case, but it should not happen. */
3941 if (GET_CODE (comparison) != code)
3944 /* Get a reference to the target in the proper mode for this insn. */
3945 compare_mode = insn_operand_mode[(int) icode][0];
3947 if (preserve_subexpressions_p ()
3948 || ! (*insn_operand_predicate[(int) icode][0]) (subtarget, compare_mode))
3949 subtarget = gen_reg_rtx (compare_mode);
3951 pattern = GEN_FCN (icode) (subtarget);
3954 emit_insn (pattern);
3956 /* If we are converting to a wider mode, first convert to
3957 TARGET_MODE, then normalize. This produces better combining
3958 opportunities on machines that have a SIGN_EXTRACT when we are
3959 testing a single bit. This mostly benefits the 68k.
3961 If STORE_FLAG_VALUE does not have the sign bit set when
3962 interpreted in COMPARE_MODE, we can do this conversion as
3963 unsigned, which is usually more efficient. */
3964 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode))
3966 convert_move (target, subtarget,
3967 (GET_MODE_BITSIZE (compare_mode)
3968 <= HOST_BITS_PER_WIDE_INT)
3969 && 0 == (STORE_FLAG_VALUE
3970 & ((HOST_WIDE_INT) 1
3971 << (GET_MODE_BITSIZE (compare_mode) -1))));
3973 compare_mode = target_mode;
3978 /* If we want to keep subexpressions around, don't reuse our
3981 if (preserve_subexpressions_p ())
3984 /* Now normalize to the proper value in COMPARE_MODE. Sometimes
3985 we don't have to do anything. */
3986 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
3988 else if (normalizep == - STORE_FLAG_VALUE)
3989 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0);
3991 /* We don't want to use STORE_FLAG_VALUE < 0 below since this
3992 makes it hard to use a value of just the sign bit due to
3993 ANSI integer constant typing rules. */
3994 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT
3995 && (STORE_FLAG_VALUE
3996 & ((HOST_WIDE_INT) 1
3997 << (GET_MODE_BITSIZE (compare_mode) - 1))))
3998 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0,
3999 size_int (GET_MODE_BITSIZE (compare_mode) - 1),
4000 subtarget, normalizep == 1);
4001 else if (STORE_FLAG_VALUE & 1)
4003 op0 = expand_and (op0, const1_rtx, subtarget);
4004 if (normalizep == -1)
4005 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0);
4010 /* If we were converting to a smaller mode, do the
4012 if (target_mode != compare_mode)
4014 convert_move (target, op0, 0);
4023 delete_insns_since (last);
4025 subtarget = target_mode == mode ? target : 0;
4027 /* If we reached here, we can't do this with a scc insn. However, there
4028 are some comparisons that can be done directly. For example, if
4029 this is an equality comparison of integers, we can try to exclusive-or
4030 (or subtract) the two operands and use a recursive call to try the
4031 comparison with zero. Don't do any of these cases if branches are
4035 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
4036 && op1 != const0_rtx)
4038 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
4042 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
4045 tem = emit_store_flag (target, code, tem, const0_rtx,
4046 mode, unsignedp, normalizep);
4048 delete_insns_since (last);
4052 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
4053 the constant zero. Reject all other comparisons at this point. Only
4054 do LE and GT if branches are expensive since they are expensive on
4055 2-operand machines. */
4057 if (BRANCH_COST == 0
4058 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
4059 || (code != EQ && code != NE
4060 && (BRANCH_COST <= 1 || (code != LE && code != GT))))
4063 /* See what we need to return. We can only return a 1, -1, or the
4066 if (normalizep == 0)
4068 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
4069 normalizep = STORE_FLAG_VALUE;
4071 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
4072 && (STORE_FLAG_VALUE
4073 == (HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
4079 /* Try to put the result of the comparison in the sign bit. Assume we can't
4080 do the necessary operation below. */
4084 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
4085 the sign bit set. */
4089 /* This is destructive, so SUBTARGET can't be OP0. */
4090 if (rtx_equal_p (subtarget, op0))
4093 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
4096 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
4100 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
4101 number of bits in the mode of OP0, minus one. */
4105 if (rtx_equal_p (subtarget, op0))
4108 tem = expand_shift (RSHIFT_EXPR, mode, op0,
4109 size_int (GET_MODE_BITSIZE (mode) - 1),
4111 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
4115 if (code == EQ || code == NE)
4117 /* For EQ or NE, one way to do the comparison is to apply an operation
4118 that converts the operand into a positive number if it is non-zero
4119 or zero if it was originally zero. Then, for EQ, we subtract 1 and
4120 for NE we negate. This puts the result in the sign bit. Then we
4121 normalize with a shift, if needed.
4123 Two operations that can do the above actions are ABS and FFS, so try
4124 them. If that doesn't work, and MODE is smaller than a full word,
4125 we can use zero-extension to the wider mode (an unsigned conversion)
4126 as the operation. */
4128 if (abs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4129 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
4130 else if (ffs_optab->handlers[(int) mode].insn_code != CODE_FOR_nothing)
4131 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
4132 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
4134 op0 = protect_from_queue (op0, 0);
4135 tem = convert_modes (word_mode, mode, op0, 1);
4142 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
4145 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
4148 /* If we couldn't do it that way, for NE we can "or" the two's complement
4149 of the value with itself. For EQ, we take the one's complement of
4150 that "or", which is an extra insn, so we only handle EQ if branches
4153 if (tem == 0 && (code == NE || BRANCH_COST > 1))
4155 if (rtx_equal_p (subtarget, op0))
4158 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
4159 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
4162 if (tem && code == EQ)
4163 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
4167 if (tem && normalizep)
4168 tem = expand_shift (RSHIFT_EXPR, mode, tem,
4169 size_int (GET_MODE_BITSIZE (mode) - 1),
4170 tem, normalizep == 1);
4172 if (tem && GET_MODE (tem) != target_mode)
4174 convert_move (target, tem, 0);
4179 delete_insns_since (last);
4183 emit_jump_insn ((*bcc_gen_fctn[(int) code]) (label));
4184 emit_move_insn (target, const1_rtx);