re PR testsuite/40567 (Revision 149002 caused many failures)
[official-gcc.git] / gcc / expmed.c
bloba579c7c4829c86a586548cffb47b682e95ca7628
1 /* Medium-level subroutines: convert bit-field store and extract
2 and shifts, multiplies and divides to rtl instructions.
3 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998,
4 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
5 Free Software Foundation, Inc.
7 This file is part of GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 3, or (at your option) any later
12 version.
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 for more details.
19 You should have received a copy of the GNU General Public License
20 along with GCC; see the file COPYING3. If not see
21 <http://www.gnu.org/licenses/>. */
24 #include "config.h"
25 #include "system.h"
26 #include "coretypes.h"
27 #include "tm.h"
28 #include "toplev.h"
29 #include "rtl.h"
30 #include "tree.h"
31 #include "tm_p.h"
32 #include "flags.h"
33 #include "insn-config.h"
34 #include "expr.h"
35 #include "optabs.h"
36 #include "real.h"
37 #include "recog.h"
38 #include "langhooks.h"
39 #include "df.h"
40 #include "target.h"
42 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
43 unsigned HOST_WIDE_INT,
44 unsigned HOST_WIDE_INT, rtx);
45 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
46 unsigned HOST_WIDE_INT, rtx);
47 static rtx extract_fixed_bit_field (enum machine_mode, rtx,
48 unsigned HOST_WIDE_INT,
49 unsigned HOST_WIDE_INT,
50 unsigned HOST_WIDE_INT, rtx, int);
51 static rtx mask_rtx (enum machine_mode, int, int, int);
52 static rtx lshift_value (enum machine_mode, rtx, int, int);
53 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
54 unsigned HOST_WIDE_INT, int);
55 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx);
56 static rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
57 static rtx expand_sdiv_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
59 /* Test whether a value is zero of a power of two. */
60 #define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0)
62 /* Nonzero means divides or modulus operations are relatively cheap for
63 powers of two, so don't use branches; emit the operation instead.
64 Usually, this will mean that the MD file will emit non-branch
65 sequences. */
67 static bool sdiv_pow2_cheap[2][NUM_MACHINE_MODES];
68 static bool smod_pow2_cheap[2][NUM_MACHINE_MODES];
70 #ifndef SLOW_UNALIGNED_ACCESS
71 #define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT
72 #endif
74 /* For compilers that support multiple targets with different word sizes,
75 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example
76 is the H8/300(H) compiler. */
78 #ifndef MAX_BITS_PER_WORD
79 #define MAX_BITS_PER_WORD BITS_PER_WORD
80 #endif
82 /* Reduce conditional compilation elsewhere. */
83 #ifndef HAVE_insv
84 #define HAVE_insv 0
85 #define CODE_FOR_insv CODE_FOR_nothing
86 #define gen_insv(a,b,c,d) NULL_RTX
87 #endif
88 #ifndef HAVE_extv
89 #define HAVE_extv 0
90 #define CODE_FOR_extv CODE_FOR_nothing
91 #define gen_extv(a,b,c,d) NULL_RTX
92 #endif
93 #ifndef HAVE_extzv
94 #define HAVE_extzv 0
95 #define CODE_FOR_extzv CODE_FOR_nothing
96 #define gen_extzv(a,b,c,d) NULL_RTX
97 #endif
99 /* Cost of various pieces of RTL. Note that some of these are indexed by
100 shift count and some by mode. */
101 static int zero_cost[2];
102 static int add_cost[2][NUM_MACHINE_MODES];
103 static int neg_cost[2][NUM_MACHINE_MODES];
104 static int shift_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
105 static int shiftadd_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
106 static int shiftsub0_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
107 static int shiftsub1_cost[2][NUM_MACHINE_MODES][MAX_BITS_PER_WORD];
108 static int mul_cost[2][NUM_MACHINE_MODES];
109 static int sdiv_cost[2][NUM_MACHINE_MODES];
110 static int udiv_cost[2][NUM_MACHINE_MODES];
111 static int mul_widen_cost[2][NUM_MACHINE_MODES];
112 static int mul_highpart_cost[2][NUM_MACHINE_MODES];
114 void
115 init_expmed (void)
117 struct
119 struct rtx_def reg; rtunion reg_fld[2];
120 struct rtx_def plus; rtunion plus_fld1;
121 struct rtx_def neg;
122 struct rtx_def mult; rtunion mult_fld1;
123 struct rtx_def sdiv; rtunion sdiv_fld1;
124 struct rtx_def udiv; rtunion udiv_fld1;
125 struct rtx_def zext;
126 struct rtx_def sdiv_32; rtunion sdiv_32_fld1;
127 struct rtx_def smod_32; rtunion smod_32_fld1;
128 struct rtx_def wide_mult; rtunion wide_mult_fld1;
129 struct rtx_def wide_lshr; rtunion wide_lshr_fld1;
130 struct rtx_def wide_trunc;
131 struct rtx_def shift; rtunion shift_fld1;
132 struct rtx_def shift_mult; rtunion shift_mult_fld1;
133 struct rtx_def shift_add; rtunion shift_add_fld1;
134 struct rtx_def shift_sub0; rtunion shift_sub0_fld1;
135 struct rtx_def shift_sub1; rtunion shift_sub1_fld1;
136 } all;
138 rtx pow2[MAX_BITS_PER_WORD];
139 rtx cint[MAX_BITS_PER_WORD];
140 int m, n;
141 enum machine_mode mode, wider_mode;
142 int speed;
145 for (m = 1; m < MAX_BITS_PER_WORD; m++)
147 pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
148 cint[m] = GEN_INT (m);
150 memset (&all, 0, sizeof all);
152 PUT_CODE (&all.reg, REG);
153 /* Avoid using hard regs in ways which may be unsupported. */
154 SET_REGNO (&all.reg, LAST_VIRTUAL_REGISTER + 1);
156 PUT_CODE (&all.plus, PLUS);
157 XEXP (&all.plus, 0) = &all.reg;
158 XEXP (&all.plus, 1) = &all.reg;
160 PUT_CODE (&all.neg, NEG);
161 XEXP (&all.neg, 0) = &all.reg;
163 PUT_CODE (&all.mult, MULT);
164 XEXP (&all.mult, 0) = &all.reg;
165 XEXP (&all.mult, 1) = &all.reg;
167 PUT_CODE (&all.sdiv, DIV);
168 XEXP (&all.sdiv, 0) = &all.reg;
169 XEXP (&all.sdiv, 1) = &all.reg;
171 PUT_CODE (&all.udiv, UDIV);
172 XEXP (&all.udiv, 0) = &all.reg;
173 XEXP (&all.udiv, 1) = &all.reg;
175 PUT_CODE (&all.sdiv_32, DIV);
176 XEXP (&all.sdiv_32, 0) = &all.reg;
177 XEXP (&all.sdiv_32, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32);
179 PUT_CODE (&all.smod_32, MOD);
180 XEXP (&all.smod_32, 0) = &all.reg;
181 XEXP (&all.smod_32, 1) = XEXP (&all.sdiv_32, 1);
183 PUT_CODE (&all.zext, ZERO_EXTEND);
184 XEXP (&all.zext, 0) = &all.reg;
186 PUT_CODE (&all.wide_mult, MULT);
187 XEXP (&all.wide_mult, 0) = &all.zext;
188 XEXP (&all.wide_mult, 1) = &all.zext;
190 PUT_CODE (&all.wide_lshr, LSHIFTRT);
191 XEXP (&all.wide_lshr, 0) = &all.wide_mult;
193 PUT_CODE (&all.wide_trunc, TRUNCATE);
194 XEXP (&all.wide_trunc, 0) = &all.wide_lshr;
196 PUT_CODE (&all.shift, ASHIFT);
197 XEXP (&all.shift, 0) = &all.reg;
199 PUT_CODE (&all.shift_mult, MULT);
200 XEXP (&all.shift_mult, 0) = &all.reg;
202 PUT_CODE (&all.shift_add, PLUS);
203 XEXP (&all.shift_add, 0) = &all.shift_mult;
204 XEXP (&all.shift_add, 1) = &all.reg;
206 PUT_CODE (&all.shift_sub0, MINUS);
207 XEXP (&all.shift_sub0, 0) = &all.shift_mult;
208 XEXP (&all.shift_sub0, 1) = &all.reg;
210 PUT_CODE (&all.shift_sub1, MINUS);
211 XEXP (&all.shift_sub1, 0) = &all.reg;
212 XEXP (&all.shift_sub1, 1) = &all.shift_mult;
214 for (speed = 0; speed < 2; speed++)
216 crtl->maybe_hot_insn_p = speed;
217 zero_cost[speed] = rtx_cost (const0_rtx, SET, speed);
219 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT);
220 mode != VOIDmode;
221 mode = GET_MODE_WIDER_MODE (mode))
223 PUT_MODE (&all.reg, mode);
224 PUT_MODE (&all.plus, mode);
225 PUT_MODE (&all.neg, mode);
226 PUT_MODE (&all.mult, mode);
227 PUT_MODE (&all.sdiv, mode);
228 PUT_MODE (&all.udiv, mode);
229 PUT_MODE (&all.sdiv_32, mode);
230 PUT_MODE (&all.smod_32, mode);
231 PUT_MODE (&all.wide_trunc, mode);
232 PUT_MODE (&all.shift, mode);
233 PUT_MODE (&all.shift_mult, mode);
234 PUT_MODE (&all.shift_add, mode);
235 PUT_MODE (&all.shift_sub0, mode);
236 PUT_MODE (&all.shift_sub1, mode);
238 add_cost[speed][mode] = rtx_cost (&all.plus, SET, speed);
239 neg_cost[speed][mode] = rtx_cost (&all.neg, SET, speed);
240 mul_cost[speed][mode] = rtx_cost (&all.mult, SET, speed);
241 sdiv_cost[speed][mode] = rtx_cost (&all.sdiv, SET, speed);
242 udiv_cost[speed][mode] = rtx_cost (&all.udiv, SET, speed);
244 sdiv_pow2_cheap[speed][mode] = (rtx_cost (&all.sdiv_32, SET, speed)
245 <= 2 * add_cost[speed][mode]);
246 smod_pow2_cheap[speed][mode] = (rtx_cost (&all.smod_32, SET, speed)
247 <= 4 * add_cost[speed][mode]);
249 wider_mode = GET_MODE_WIDER_MODE (mode);
250 if (wider_mode != VOIDmode)
252 PUT_MODE (&all.zext, wider_mode);
253 PUT_MODE (&all.wide_mult, wider_mode);
254 PUT_MODE (&all.wide_lshr, wider_mode);
255 XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode));
257 mul_widen_cost[speed][wider_mode]
258 = rtx_cost (&all.wide_mult, SET, speed);
259 mul_highpart_cost[speed][mode]
260 = rtx_cost (&all.wide_trunc, SET, speed);
263 shift_cost[speed][mode][0] = 0;
264 shiftadd_cost[speed][mode][0] = shiftsub0_cost[speed][mode][0]
265 = shiftsub1_cost[speed][mode][0] = add_cost[speed][mode];
267 n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode));
268 for (m = 1; m < n; m++)
270 XEXP (&all.shift, 1) = cint[m];
271 XEXP (&all.shift_mult, 1) = pow2[m];
273 shift_cost[speed][mode][m] = rtx_cost (&all.shift, SET, speed);
274 shiftadd_cost[speed][mode][m] = rtx_cost (&all.shift_add, SET, speed);
275 shiftsub0_cost[speed][mode][m] = rtx_cost (&all.shift_sub0, SET, speed);
276 shiftsub1_cost[speed][mode][m] = rtx_cost (&all.shift_sub1, SET, speed);
280 default_rtl_profile ();
283 /* Return an rtx representing minus the value of X.
284 MODE is the intended mode of the result,
285 useful if X is a CONST_INT. */
288 negate_rtx (enum machine_mode mode, rtx x)
290 rtx result = simplify_unary_operation (NEG, mode, x, mode);
292 if (result == 0)
293 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
295 return result;
298 /* Report on the availability of insv/extv/extzv and the desired mode
299 of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo
300 is false; else the mode of the specified operand. If OPNO is -1,
301 all the caller cares about is whether the insn is available. */
302 enum machine_mode
303 mode_for_extraction (enum extraction_pattern pattern, int opno)
305 const struct insn_data *data;
307 switch (pattern)
309 case EP_insv:
310 if (HAVE_insv)
312 data = &insn_data[CODE_FOR_insv];
313 break;
315 return MAX_MACHINE_MODE;
317 case EP_extv:
318 if (HAVE_extv)
320 data = &insn_data[CODE_FOR_extv];
321 break;
323 return MAX_MACHINE_MODE;
325 case EP_extzv:
326 if (HAVE_extzv)
328 data = &insn_data[CODE_FOR_extzv];
329 break;
331 return MAX_MACHINE_MODE;
333 default:
334 gcc_unreachable ();
337 if (opno == -1)
338 return VOIDmode;
340 /* Everyone who uses this function used to follow it with
341 if (result == VOIDmode) result = word_mode; */
342 if (data->operand[opno].mode == VOIDmode)
343 return word_mode;
344 return data->operand[opno].mode;
347 /* Return true if X, of mode MODE, matches the predicate for operand
348 OPNO of instruction ICODE. Allow volatile memories, regardless of
349 the ambient volatile_ok setting. */
351 static bool
352 check_predicate_volatile_ok (enum insn_code icode, int opno,
353 rtx x, enum machine_mode mode)
355 bool save_volatile_ok, result;
357 save_volatile_ok = volatile_ok;
358 result = insn_data[(int) icode].operand[opno].predicate (x, mode);
359 volatile_ok = save_volatile_ok;
360 return result;
363 /* A subroutine of store_bit_field, with the same arguments. Return true
364 if the operation could be implemented.
366 If FALLBACK_P is true, fall back to store_fixed_bit_field if we have
367 no other way of implementing the operation. If FALLBACK_P is false,
368 return false instead. */
370 static bool
371 store_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
372 unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode,
373 rtx value, bool fallback_p)
375 unsigned int unit
376 = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
377 unsigned HOST_WIDE_INT offset, bitpos;
378 rtx op0 = str_rtx;
379 int byte_offset;
380 rtx orig_value;
382 enum machine_mode op_mode = mode_for_extraction (EP_insv, 3);
384 while (GET_CODE (op0) == SUBREG)
386 /* The following line once was done only if WORDS_BIG_ENDIAN,
387 but I think that is a mistake. WORDS_BIG_ENDIAN is
388 meaningful at a much higher level; when structures are copied
389 between memory and regs, the higher-numbered regs
390 always get higher addresses. */
391 int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)));
392 int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0));
394 byte_offset = 0;
396 /* Paradoxical subregs need special handling on big endian machines. */
397 if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size)
399 int difference = inner_mode_size - outer_mode_size;
401 if (WORDS_BIG_ENDIAN)
402 byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
403 if (BYTES_BIG_ENDIAN)
404 byte_offset += difference % UNITS_PER_WORD;
406 else
407 byte_offset = SUBREG_BYTE (op0);
409 bitnum += byte_offset * BITS_PER_UNIT;
410 op0 = SUBREG_REG (op0);
413 /* No action is needed if the target is a register and if the field
414 lies completely outside that register. This can occur if the source
415 code contains an out-of-bounds access to a small array. */
416 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
417 return true;
419 /* Use vec_set patterns for inserting parts of vectors whenever
420 available. */
421 if (VECTOR_MODE_P (GET_MODE (op0))
422 && !MEM_P (op0)
423 && (optab_handler (vec_set_optab, GET_MODE (op0))->insn_code
424 != CODE_FOR_nothing)
425 && fieldmode == GET_MODE_INNER (GET_MODE (op0))
426 && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
427 && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
429 enum machine_mode outermode = GET_MODE (op0);
430 enum machine_mode innermode = GET_MODE_INNER (outermode);
431 int icode = (int) optab_handler (vec_set_optab, outermode)->insn_code;
432 int pos = bitnum / GET_MODE_BITSIZE (innermode);
433 rtx rtxpos = GEN_INT (pos);
434 rtx src = value;
435 rtx dest = op0;
436 rtx pat, seq;
437 enum machine_mode mode0 = insn_data[icode].operand[0].mode;
438 enum machine_mode mode1 = insn_data[icode].operand[1].mode;
439 enum machine_mode mode2 = insn_data[icode].operand[2].mode;
441 start_sequence ();
443 if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
444 src = copy_to_mode_reg (mode1, src);
446 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
447 rtxpos = copy_to_mode_reg (mode1, rtxpos);
449 /* We could handle this, but we should always be called with a pseudo
450 for our targets and all insns should take them as outputs. */
451 gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0)
452 && (*insn_data[icode].operand[1].predicate) (src, mode1)
453 && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2));
454 pat = GEN_FCN (icode) (dest, src, rtxpos);
455 seq = get_insns ();
456 end_sequence ();
457 if (pat)
459 emit_insn (seq);
460 emit_insn (pat);
461 return true;
465 /* If the target is a register, overwriting the entire object, or storing
466 a full-word or multi-word field can be done with just a SUBREG.
468 If the target is memory, storing any naturally aligned field can be
469 done with a simple store. For targets that support fast unaligned
470 memory, any naturally sized, unit aligned field can be done directly. */
472 offset = bitnum / unit;
473 bitpos = bitnum % unit;
474 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
475 + (offset * UNITS_PER_WORD);
477 if (bitpos == 0
478 && bitsize == GET_MODE_BITSIZE (fieldmode)
479 && (!MEM_P (op0)
480 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD
481 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode))
482 && byte_offset % GET_MODE_SIZE (fieldmode) == 0)
483 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0))
484 || (offset * BITS_PER_UNIT % bitsize == 0
485 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0))))
487 if (MEM_P (op0))
488 op0 = adjust_address (op0, fieldmode, offset);
489 else if (GET_MODE (op0) != fieldmode)
490 op0 = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0),
491 byte_offset);
492 emit_move_insn (op0, value);
493 return true;
496 /* Make sure we are playing with integral modes. Pun with subregs
497 if we aren't. This must come after the entire register case above,
498 since that case is valid for any mode. The following cases are only
499 valid for integral modes. */
501 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
502 if (imode != GET_MODE (op0))
504 if (MEM_P (op0))
505 op0 = adjust_address (op0, imode, 0);
506 else
508 gcc_assert (imode != BLKmode);
509 op0 = gen_lowpart (imode, op0);
514 /* We may be accessing data outside the field, which means
515 we can alias adjacent data. */
516 if (MEM_P (op0))
518 op0 = shallow_copy_rtx (op0);
519 set_mem_alias_set (op0, 0);
520 set_mem_expr (op0, 0);
523 /* If OP0 is a register, BITPOS must count within a word.
524 But as we have it, it counts within whatever size OP0 now has.
525 On a bigendian machine, these are not the same, so convert. */
526 if (BYTES_BIG_ENDIAN
527 && !MEM_P (op0)
528 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
529 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
531 /* Storing an lsb-aligned field in a register
532 can be done with a movestrict instruction. */
534 if (!MEM_P (op0)
535 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0)
536 && bitsize == GET_MODE_BITSIZE (fieldmode)
537 && (optab_handler (movstrict_optab, fieldmode)->insn_code
538 != CODE_FOR_nothing))
540 int icode = optab_handler (movstrict_optab, fieldmode)->insn_code;
541 rtx insn;
542 rtx start = get_last_insn ();
543 rtx arg0 = op0;
545 /* Get appropriate low part of the value being stored. */
546 if (CONST_INT_P (value) || REG_P (value))
547 value = gen_lowpart (fieldmode, value);
548 else if (!(GET_CODE (value) == SYMBOL_REF
549 || GET_CODE (value) == LABEL_REF
550 || GET_CODE (value) == CONST))
551 value = convert_to_mode (fieldmode, value, 0);
553 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode))
554 value = copy_to_mode_reg (fieldmode, value);
556 if (GET_CODE (op0) == SUBREG)
558 /* Else we've got some float mode source being extracted into
559 a different float mode destination -- this combination of
560 subregs results in Severe Tire Damage. */
561 gcc_assert (GET_MODE (SUBREG_REG (op0)) == fieldmode
562 || GET_MODE_CLASS (fieldmode) == MODE_INT
563 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT);
564 arg0 = SUBREG_REG (op0);
567 insn = (GEN_FCN (icode)
568 (gen_rtx_SUBREG (fieldmode, arg0,
569 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT
570 + (offset * UNITS_PER_WORD)),
571 value));
572 if (insn)
574 emit_insn (insn);
575 return true;
577 delete_insns_since (start);
580 /* Handle fields bigger than a word. */
582 if (bitsize > BITS_PER_WORD)
584 /* Here we transfer the words of the field
585 in the order least significant first.
586 This is because the most significant word is the one which may
587 be less than full.
588 However, only do that if the value is not BLKmode. */
590 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
591 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
592 unsigned int i;
593 rtx last;
595 /* This is the mode we must force value to, so that there will be enough
596 subwords to extract. Note that fieldmode will often (always?) be
597 VOIDmode, because that is what store_field uses to indicate that this
598 is a bit field, but passing VOIDmode to operand_subword_force
599 is not allowed. */
600 fieldmode = GET_MODE (value);
601 if (fieldmode == VOIDmode)
602 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
604 last = get_last_insn ();
605 for (i = 0; i < nwords; i++)
607 /* If I is 0, use the low-order word in both field and target;
608 if I is 1, use the next to lowest word; and so on. */
609 unsigned int wordnum = (backwards ? nwords - i - 1 : i);
610 unsigned int bit_offset = (backwards
611 ? MAX ((int) bitsize - ((int) i + 1)
612 * BITS_PER_WORD,
614 : (int) i * BITS_PER_WORD);
615 rtx value_word = operand_subword_force (value, wordnum, fieldmode);
617 if (!store_bit_field_1 (op0, MIN (BITS_PER_WORD,
618 bitsize - i * BITS_PER_WORD),
619 bitnum + bit_offset, word_mode,
620 value_word, fallback_p))
622 delete_insns_since (last);
623 return false;
626 return true;
629 /* From here on we can assume that the field to be stored in is
630 a full-word (whatever type that is), since it is shorter than a word. */
632 /* OFFSET is the number of words or bytes (UNIT says which)
633 from STR_RTX to the first word or byte containing part of the field. */
635 if (!MEM_P (op0))
637 if (offset != 0
638 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
640 if (!REG_P (op0))
642 /* Since this is a destination (lvalue), we can't copy
643 it to a pseudo. We can remove a SUBREG that does not
644 change the size of the operand. Such a SUBREG may
645 have been added above. */
646 gcc_assert (GET_CODE (op0) == SUBREG
647 && (GET_MODE_SIZE (GET_MODE (op0))
648 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)))));
649 op0 = SUBREG_REG (op0);
651 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
652 op0, (offset * UNITS_PER_WORD));
654 offset = 0;
657 /* If VALUE has a floating-point or complex mode, access it as an
658 integer of the corresponding size. This can occur on a machine
659 with 64 bit registers that uses SFmode for float. It can also
660 occur for unaligned float or complex fields. */
661 orig_value = value;
662 if (GET_MODE (value) != VOIDmode
663 && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
664 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
666 value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value)));
667 emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value);
670 /* Now OFFSET is nonzero only if OP0 is memory
671 and is therefore always measured in bytes. */
673 if (HAVE_insv
674 && GET_MODE (value) != BLKmode
675 && bitsize > 0
676 && GET_MODE_BITSIZE (op_mode) >= bitsize
677 && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG)
678 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode)))
679 && insn_data[CODE_FOR_insv].operand[1].predicate (GEN_INT (bitsize),
680 VOIDmode)
681 && check_predicate_volatile_ok (CODE_FOR_insv, 0, op0, VOIDmode))
683 int xbitpos = bitpos;
684 rtx value1;
685 rtx xop0 = op0;
686 rtx last = get_last_insn ();
687 rtx pat;
689 /* Add OFFSET into OP0's address. */
690 if (MEM_P (xop0))
691 xop0 = adjust_address (xop0, byte_mode, offset);
693 /* If xop0 is a register, we need it in OP_MODE
694 to make it acceptable to the format of insv. */
695 if (GET_CODE (xop0) == SUBREG)
696 /* We can't just change the mode, because this might clobber op0,
697 and we will need the original value of op0 if insv fails. */
698 xop0 = gen_rtx_SUBREG (op_mode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
699 if (REG_P (xop0) && GET_MODE (xop0) != op_mode)
700 xop0 = gen_rtx_SUBREG (op_mode, xop0, 0);
702 /* On big-endian machines, we count bits from the most significant.
703 If the bit field insn does not, we must invert. */
705 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
706 xbitpos = unit - bitsize - xbitpos;
708 /* We have been counting XBITPOS within UNIT.
709 Count instead within the size of the register. */
710 if (BITS_BIG_ENDIAN && !MEM_P (xop0))
711 xbitpos += GET_MODE_BITSIZE (op_mode) - unit;
713 unit = GET_MODE_BITSIZE (op_mode);
715 /* Convert VALUE to op_mode (which insv insn wants) in VALUE1. */
716 value1 = value;
717 if (GET_MODE (value) != op_mode)
719 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
721 /* Optimization: Don't bother really extending VALUE
722 if it has all the bits we will actually use. However,
723 if we must narrow it, be sure we do it correctly. */
725 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (op_mode))
727 rtx tmp;
729 tmp = simplify_subreg (op_mode, value1, GET_MODE (value), 0);
730 if (! tmp)
731 tmp = simplify_gen_subreg (op_mode,
732 force_reg (GET_MODE (value),
733 value1),
734 GET_MODE (value), 0);
735 value1 = tmp;
737 else
738 value1 = gen_lowpart (op_mode, value1);
740 else if (CONST_INT_P (value))
741 value1 = gen_int_mode (INTVAL (value), op_mode);
742 else
743 /* Parse phase is supposed to make VALUE's data type
744 match that of the component reference, which is a type
745 at least as wide as the field; so VALUE should have
746 a mode that corresponds to that type. */
747 gcc_assert (CONSTANT_P (value));
750 /* If this machine's insv insists on a register,
751 get VALUE1 into a register. */
752 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate)
753 (value1, op_mode)))
754 value1 = force_reg (op_mode, value1);
756 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1);
757 if (pat)
759 emit_insn (pat);
761 /* If the mode of the insertion is wider than the mode of the
762 target register we created a paradoxical subreg for the
763 target. Truncate the paradoxical subreg of the target to
764 itself properly. */
765 if (!TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (op0)),
766 GET_MODE_BITSIZE (op_mode))
767 && (REG_P (xop0)
768 || GET_CODE (xop0) == SUBREG))
769 convert_move (op0, xop0, true);
770 return true;
772 delete_insns_since (last);
775 /* If OP0 is a memory, try copying it to a register and seeing if a
776 cheap register alternative is available. */
777 if (HAVE_insv && MEM_P (op0))
779 enum machine_mode bestmode;
781 /* Get the mode to use for inserting into this field. If OP0 is
782 BLKmode, get the smallest mode consistent with the alignment. If
783 OP0 is a non-BLKmode object that is no wider than OP_MODE, use its
784 mode. Otherwise, use the smallest mode containing the field. */
786 if (GET_MODE (op0) == BLKmode
787 || (op_mode != MAX_MACHINE_MODE
788 && GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (op_mode)))
789 bestmode = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0),
790 (op_mode == MAX_MACHINE_MODE
791 ? VOIDmode : op_mode),
792 MEM_VOLATILE_P (op0));
793 else
794 bestmode = GET_MODE (op0);
796 if (bestmode != VOIDmode
797 && GET_MODE_SIZE (bestmode) >= GET_MODE_SIZE (fieldmode)
798 && !(SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
799 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
801 rtx last, tempreg, xop0;
802 unsigned HOST_WIDE_INT xoffset, xbitpos;
804 last = get_last_insn ();
806 /* Adjust address to point to the containing unit of
807 that mode. Compute the offset as a multiple of this unit,
808 counting in bytes. */
809 unit = GET_MODE_BITSIZE (bestmode);
810 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
811 xbitpos = bitnum % unit;
812 xop0 = adjust_address (op0, bestmode, xoffset);
814 /* Fetch that unit, store the bitfield in it, then store
815 the unit. */
816 tempreg = copy_to_reg (xop0);
817 if (store_bit_field_1 (tempreg, bitsize, xbitpos,
818 fieldmode, orig_value, false))
820 emit_move_insn (xop0, tempreg);
821 return true;
823 delete_insns_since (last);
827 if (!fallback_p)
828 return false;
830 store_fixed_bit_field (op0, offset, bitsize, bitpos, value);
831 return true;
834 /* Generate code to store value from rtx VALUE
835 into a bit-field within structure STR_RTX
836 containing BITSIZE bits starting at bit BITNUM.
837 FIELDMODE is the machine-mode of the FIELD_DECL node for this field. */
839 void
840 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
841 unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode,
842 rtx value)
844 if (!store_bit_field_1 (str_rtx, bitsize, bitnum, fieldmode, value, true))
845 gcc_unreachable ();
848 /* Use shifts and boolean operations to store VALUE
849 into a bit field of width BITSIZE
850 in a memory location specified by OP0 except offset by OFFSET bytes.
851 (OFFSET must be 0 if OP0 is a register.)
852 The field starts at position BITPOS within the byte.
853 (If OP0 is a register, it may be a full word or a narrower mode,
854 but BITPOS still counts within a full word,
855 which is significant on bigendian machines.) */
857 static void
858 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset,
859 unsigned HOST_WIDE_INT bitsize,
860 unsigned HOST_WIDE_INT bitpos, rtx value)
862 enum machine_mode mode;
863 unsigned int total_bits = BITS_PER_WORD;
864 rtx temp;
865 int all_zero = 0;
866 int all_one = 0;
868 /* There is a case not handled here:
869 a structure with a known alignment of just a halfword
870 and a field split across two aligned halfwords within the structure.
871 Or likewise a structure with a known alignment of just a byte
872 and a field split across two bytes.
873 Such cases are not supposed to be able to occur. */
875 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
877 gcc_assert (!offset);
878 /* Special treatment for a bit field split across two registers. */
879 if (bitsize + bitpos > BITS_PER_WORD)
881 store_split_bit_field (op0, bitsize, bitpos, value);
882 return;
885 else
887 /* Get the proper mode to use for this field. We want a mode that
888 includes the entire field. If such a mode would be larger than
889 a word, we won't be doing the extraction the normal way.
890 We don't want a mode bigger than the destination. */
892 mode = GET_MODE (op0);
893 if (GET_MODE_BITSIZE (mode) == 0
894 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
895 mode = word_mode;
896 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
897 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
899 if (mode == VOIDmode)
901 /* The only way this should occur is if the field spans word
902 boundaries. */
903 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT,
904 value);
905 return;
908 total_bits = GET_MODE_BITSIZE (mode);
910 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
911 be in the range 0 to total_bits-1, and put any excess bytes in
912 OFFSET. */
913 if (bitpos >= total_bits)
915 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
916 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
917 * BITS_PER_UNIT);
920 /* Get ref to an aligned byte, halfword, or word containing the field.
921 Adjust BITPOS to be position within a word,
922 and OFFSET to be the offset of that word.
923 Then alter OP0 to refer to that word. */
924 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
925 offset -= (offset % (total_bits / BITS_PER_UNIT));
926 op0 = adjust_address (op0, mode, offset);
929 mode = GET_MODE (op0);
931 /* Now MODE is either some integral mode for a MEM as OP0,
932 or is a full-word for a REG as OP0. TOTAL_BITS corresponds.
933 The bit field is contained entirely within OP0.
934 BITPOS is the starting bit number within OP0.
935 (OP0's mode may actually be narrower than MODE.) */
937 if (BYTES_BIG_ENDIAN)
938 /* BITPOS is the distance between our msb
939 and that of the containing datum.
940 Convert it to the distance from the lsb. */
941 bitpos = total_bits - bitsize - bitpos;
943 /* Now BITPOS is always the distance between our lsb
944 and that of OP0. */
946 /* Shift VALUE left by BITPOS bits. If VALUE is not constant,
947 we must first convert its mode to MODE. */
949 if (CONST_INT_P (value))
951 HOST_WIDE_INT v = INTVAL (value);
953 if (bitsize < HOST_BITS_PER_WIDE_INT)
954 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
956 if (v == 0)
957 all_zero = 1;
958 else if ((bitsize < HOST_BITS_PER_WIDE_INT
959 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
960 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
961 all_one = 1;
963 value = lshift_value (mode, value, bitpos, bitsize);
965 else
967 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
968 && bitpos + bitsize != GET_MODE_BITSIZE (mode));
970 if (GET_MODE (value) != mode)
971 value = convert_to_mode (mode, value, 1);
973 if (must_and)
974 value = expand_binop (mode, and_optab, value,
975 mask_rtx (mode, 0, bitsize, 0),
976 NULL_RTX, 1, OPTAB_LIB_WIDEN);
977 if (bitpos > 0)
978 value = expand_shift (LSHIFT_EXPR, mode, value,
979 build_int_cst (NULL_TREE, bitpos), NULL_RTX, 1);
982 /* Now clear the chosen bits in OP0,
983 except that if VALUE is -1 we need not bother. */
984 /* We keep the intermediates in registers to allow CSE to combine
985 consecutive bitfield assignments. */
987 temp = force_reg (mode, op0);
989 if (! all_one)
991 temp = expand_binop (mode, and_optab, temp,
992 mask_rtx (mode, bitpos, bitsize, 1),
993 NULL_RTX, 1, OPTAB_LIB_WIDEN);
994 temp = force_reg (mode, temp);
997 /* Now logical-or VALUE into OP0, unless it is zero. */
999 if (! all_zero)
1001 temp = expand_binop (mode, ior_optab, temp, value,
1002 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1003 temp = force_reg (mode, temp);
1006 if (op0 != temp)
1008 op0 = copy_rtx (op0);
1009 emit_move_insn (op0, temp);
1013 /* Store a bit field that is split across multiple accessible memory objects.
1015 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
1016 BITSIZE is the field width; BITPOS the position of its first bit
1017 (within the word).
1018 VALUE is the value to store.
1020 This does not yet handle fields wider than BITS_PER_WORD. */
1022 static void
1023 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1024 unsigned HOST_WIDE_INT bitpos, rtx value)
1026 unsigned int unit;
1027 unsigned int bitsdone = 0;
1029 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1030 much at a time. */
1031 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1032 unit = BITS_PER_WORD;
1033 else
1034 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1036 /* If VALUE is a constant other than a CONST_INT, get it into a register in
1037 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
1038 that VALUE might be a floating-point constant. */
1039 if (CONSTANT_P (value) && !CONST_INT_P (value))
1041 rtx word = gen_lowpart_common (word_mode, value);
1043 if (word && (value != word))
1044 value = word;
1045 else
1046 value = gen_lowpart_common (word_mode,
1047 force_reg (GET_MODE (value) != VOIDmode
1048 ? GET_MODE (value)
1049 : word_mode, value));
1052 while (bitsdone < bitsize)
1054 unsigned HOST_WIDE_INT thissize;
1055 rtx part, word;
1056 unsigned HOST_WIDE_INT thispos;
1057 unsigned HOST_WIDE_INT offset;
1059 offset = (bitpos + bitsdone) / unit;
1060 thispos = (bitpos + bitsdone) % unit;
1062 /* THISSIZE must not overrun a word boundary. Otherwise,
1063 store_fixed_bit_field will call us again, and we will mutually
1064 recurse forever. */
1065 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1066 thissize = MIN (thissize, unit - thispos);
1068 if (BYTES_BIG_ENDIAN)
1070 int total_bits;
1072 /* We must do an endian conversion exactly the same way as it is
1073 done in extract_bit_field, so that the two calls to
1074 extract_fixed_bit_field will have comparable arguments. */
1075 if (!MEM_P (value) || GET_MODE (value) == BLKmode)
1076 total_bits = BITS_PER_WORD;
1077 else
1078 total_bits = GET_MODE_BITSIZE (GET_MODE (value));
1080 /* Fetch successively less significant portions. */
1081 if (CONST_INT_P (value))
1082 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1083 >> (bitsize - bitsdone - thissize))
1084 & (((HOST_WIDE_INT) 1 << thissize) - 1));
1085 else
1086 /* The args are chosen so that the last part includes the
1087 lsb. Give extract_bit_field the value it needs (with
1088 endianness compensation) to fetch the piece we want. */
1089 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1090 total_bits - bitsize + bitsdone,
1091 NULL_RTX, 1);
1093 else
1095 /* Fetch successively more significant portions. */
1096 if (CONST_INT_P (value))
1097 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1098 >> bitsdone)
1099 & (((HOST_WIDE_INT) 1 << thissize) - 1));
1100 else
1101 part = extract_fixed_bit_field (word_mode, value, 0, thissize,
1102 bitsdone, NULL_RTX, 1);
1105 /* If OP0 is a register, then handle OFFSET here.
1107 When handling multiword bitfields, extract_bit_field may pass
1108 down a word_mode SUBREG of a larger REG for a bitfield that actually
1109 crosses a word boundary. Thus, for a SUBREG, we must find
1110 the current word starting from the base register. */
1111 if (GET_CODE (op0) == SUBREG)
1113 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1114 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1115 GET_MODE (SUBREG_REG (op0)));
1116 offset = 0;
1118 else if (REG_P (op0))
1120 word = operand_subword_force (op0, offset, GET_MODE (op0));
1121 offset = 0;
1123 else
1124 word = op0;
1126 /* OFFSET is in UNITs, and UNIT is in bits.
1127 store_fixed_bit_field wants offset in bytes. */
1128 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize,
1129 thispos, part);
1130 bitsdone += thissize;
1134 /* A subroutine of extract_bit_field_1 that converts return value X
1135 to either MODE or TMODE. MODE, TMODE and UNSIGNEDP are arguments
1136 to extract_bit_field. */
1138 static rtx
1139 convert_extracted_bit_field (rtx x, enum machine_mode mode,
1140 enum machine_mode tmode, bool unsignedp)
1142 if (GET_MODE (x) == tmode || GET_MODE (x) == mode)
1143 return x;
1145 /* If the x mode is not a scalar integral, first convert to the
1146 integer mode of that size and then access it as a floating-point
1147 value via a SUBREG. */
1148 if (!SCALAR_INT_MODE_P (tmode))
1150 enum machine_mode smode;
1152 smode = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0);
1153 x = convert_to_mode (smode, x, unsignedp);
1154 x = force_reg (smode, x);
1155 return gen_lowpart (tmode, x);
1158 return convert_to_mode (tmode, x, unsignedp);
1161 /* A subroutine of extract_bit_field, with the same arguments.
1162 If FALLBACK_P is true, fall back to extract_fixed_bit_field
1163 if we can find no other means of implementing the operation.
1164 if FALLBACK_P is false, return NULL instead. */
1166 static rtx
1167 extract_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1168 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1169 enum machine_mode mode, enum machine_mode tmode,
1170 bool fallback_p)
1172 unsigned int unit
1173 = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD;
1174 unsigned HOST_WIDE_INT offset, bitpos;
1175 rtx op0 = str_rtx;
1176 enum machine_mode int_mode;
1177 enum machine_mode ext_mode;
1178 enum machine_mode mode1;
1179 enum insn_code icode;
1180 int byte_offset;
1182 if (tmode == VOIDmode)
1183 tmode = mode;
1185 while (GET_CODE (op0) == SUBREG)
1187 bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1188 op0 = SUBREG_REG (op0);
1191 /* If we have an out-of-bounds access to a register, just return an
1192 uninitialized register of the required mode. This can occur if the
1193 source code contains an out-of-bounds access to a small array. */
1194 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
1195 return gen_reg_rtx (tmode);
1197 if (REG_P (op0)
1198 && mode == GET_MODE (op0)
1199 && bitnum == 0
1200 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1202 /* We're trying to extract a full register from itself. */
1203 return op0;
1206 /* See if we can get a better vector mode before extracting. */
1207 if (VECTOR_MODE_P (GET_MODE (op0))
1208 && !MEM_P (op0)
1209 && GET_MODE_INNER (GET_MODE (op0)) != tmode)
1211 enum machine_mode new_mode;
1212 int nunits = GET_MODE_NUNITS (GET_MODE (op0));
1214 if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1215 new_mode = MIN_MODE_VECTOR_FLOAT;
1216 else if (GET_MODE_CLASS (tmode) == MODE_FRACT)
1217 new_mode = MIN_MODE_VECTOR_FRACT;
1218 else if (GET_MODE_CLASS (tmode) == MODE_UFRACT)
1219 new_mode = MIN_MODE_VECTOR_UFRACT;
1220 else if (GET_MODE_CLASS (tmode) == MODE_ACCUM)
1221 new_mode = MIN_MODE_VECTOR_ACCUM;
1222 else if (GET_MODE_CLASS (tmode) == MODE_UACCUM)
1223 new_mode = MIN_MODE_VECTOR_UACCUM;
1224 else
1225 new_mode = MIN_MODE_VECTOR_INT;
1227 for (; new_mode != VOIDmode ; new_mode = GET_MODE_WIDER_MODE (new_mode))
1228 if (GET_MODE_NUNITS (new_mode) == nunits
1229 && GET_MODE_SIZE (new_mode) == GET_MODE_SIZE (GET_MODE (op0))
1230 && targetm.vector_mode_supported_p (new_mode))
1231 break;
1232 if (new_mode != VOIDmode)
1233 op0 = gen_lowpart (new_mode, op0);
1236 /* Use vec_extract patterns for extracting parts of vectors whenever
1237 available. */
1238 if (VECTOR_MODE_P (GET_MODE (op0))
1239 && !MEM_P (op0)
1240 && (optab_handler (vec_extract_optab, GET_MODE (op0))->insn_code
1241 != CODE_FOR_nothing)
1242 && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1243 == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1245 enum machine_mode outermode = GET_MODE (op0);
1246 enum machine_mode innermode = GET_MODE_INNER (outermode);
1247 int icode = (int) optab_handler (vec_extract_optab, outermode)->insn_code;
1248 unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode);
1249 rtx rtxpos = GEN_INT (pos);
1250 rtx src = op0;
1251 rtx dest = NULL, pat, seq;
1252 enum machine_mode mode0 = insn_data[icode].operand[0].mode;
1253 enum machine_mode mode1 = insn_data[icode].operand[1].mode;
1254 enum machine_mode mode2 = insn_data[icode].operand[2].mode;
1256 if (innermode == tmode || innermode == mode)
1257 dest = target;
1259 if (!dest)
1260 dest = gen_reg_rtx (innermode);
1262 start_sequence ();
1264 if (! (*insn_data[icode].operand[0].predicate) (dest, mode0))
1265 dest = copy_to_mode_reg (mode0, dest);
1267 if (! (*insn_data[icode].operand[1].predicate) (src, mode1))
1268 src = copy_to_mode_reg (mode1, src);
1270 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2))
1271 rtxpos = copy_to_mode_reg (mode1, rtxpos);
1273 /* We could handle this, but we should always be called with a pseudo
1274 for our targets and all insns should take them as outputs. */
1275 gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0)
1276 && (*insn_data[icode].operand[1].predicate) (src, mode1)
1277 && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2));
1279 pat = GEN_FCN (icode) (dest, src, rtxpos);
1280 seq = get_insns ();
1281 end_sequence ();
1282 if (pat)
1284 emit_insn (seq);
1285 emit_insn (pat);
1286 if (mode0 != mode)
1287 return gen_lowpart (tmode, dest);
1288 return dest;
1292 /* Make sure we are playing with integral modes. Pun with subregs
1293 if we aren't. */
1295 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1296 if (imode != GET_MODE (op0))
1298 if (MEM_P (op0))
1299 op0 = adjust_address (op0, imode, 0);
1300 else if (imode != BLKmode)
1302 op0 = gen_lowpart (imode, op0);
1304 /* If we got a SUBREG, force it into a register since we
1305 aren't going to be able to do another SUBREG on it. */
1306 if (GET_CODE (op0) == SUBREG)
1307 op0 = force_reg (imode, op0);
1309 else if (REG_P (op0))
1311 rtx reg, subreg;
1312 imode = smallest_mode_for_size (GET_MODE_BITSIZE (GET_MODE (op0)),
1313 MODE_INT);
1314 reg = gen_reg_rtx (imode);
1315 subreg = gen_lowpart_SUBREG (GET_MODE (op0), reg);
1316 emit_move_insn (subreg, op0);
1317 op0 = reg;
1318 bitnum += SUBREG_BYTE (subreg) * BITS_PER_UNIT;
1320 else
1322 rtx mem = assign_stack_temp (GET_MODE (op0),
1323 GET_MODE_SIZE (GET_MODE (op0)), 0);
1324 emit_move_insn (mem, op0);
1325 op0 = adjust_address (mem, BLKmode, 0);
1330 /* We may be accessing data outside the field, which means
1331 we can alias adjacent data. */
1332 if (MEM_P (op0))
1334 op0 = shallow_copy_rtx (op0);
1335 set_mem_alias_set (op0, 0);
1336 set_mem_expr (op0, 0);
1339 /* Extraction of a full-word or multi-word value from a structure
1340 in a register or aligned memory can be done with just a SUBREG.
1341 A subword value in the least significant part of a register
1342 can also be extracted with a SUBREG. For this, we need the
1343 byte offset of the value in op0. */
1345 bitpos = bitnum % unit;
1346 offset = bitnum / unit;
1347 byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD;
1349 /* If OP0 is a register, BITPOS must count within a word.
1350 But as we have it, it counts within whatever size OP0 now has.
1351 On a bigendian machine, these are not the same, so convert. */
1352 if (BYTES_BIG_ENDIAN
1353 && !MEM_P (op0)
1354 && unit > GET_MODE_BITSIZE (GET_MODE (op0)))
1355 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1357 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1358 If that's wrong, the solution is to test for it and set TARGET to 0
1359 if needed. */
1361 /* Only scalar integer modes can be converted via subregs. There is an
1362 additional problem for FP modes here in that they can have a precision
1363 which is different from the size. mode_for_size uses precision, but
1364 we want a mode based on the size, so we must avoid calling it for FP
1365 modes. */
1366 mode1 = (SCALAR_INT_MODE_P (tmode)
1367 ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0)
1368 : mode);
1370 if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode)
1371 && bitpos % BITS_PER_WORD == 0)
1372 || (mode1 != BLKmode
1373 /* ??? The big endian test here is wrong. This is correct
1374 if the value is in a register, and if mode_for_size is not
1375 the same mode as op0. This causes us to get unnecessarily
1376 inefficient code from the Thumb port when -mbig-endian. */
1377 && (BYTES_BIG_ENDIAN
1378 ? bitpos + bitsize == BITS_PER_WORD
1379 : bitpos == 0)))
1380 && ((!MEM_P (op0)
1381 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode1),
1382 GET_MODE_BITSIZE (GET_MODE (op0)))
1383 && GET_MODE_SIZE (mode1) != 0
1384 && byte_offset % GET_MODE_SIZE (mode1) == 0)
1385 || (MEM_P (op0)
1386 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
1387 || (offset * BITS_PER_UNIT % bitsize == 0
1388 && MEM_ALIGN (op0) % bitsize == 0)))))
1390 if (MEM_P (op0))
1391 op0 = adjust_address (op0, mode1, offset);
1392 else if (mode1 != GET_MODE (op0))
1394 rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0),
1395 byte_offset);
1396 if (sub == NULL)
1397 goto no_subreg_mode_swap;
1398 op0 = sub;
1400 if (mode1 != mode)
1401 return convert_to_mode (tmode, op0, unsignedp);
1402 return op0;
1404 no_subreg_mode_swap:
1406 /* Handle fields bigger than a word. */
1408 if (bitsize > BITS_PER_WORD)
1410 /* Here we transfer the words of the field
1411 in the order least significant first.
1412 This is because the most significant word is the one which may
1413 be less than full. */
1415 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1416 unsigned int i;
1418 if (target == 0 || !REG_P (target))
1419 target = gen_reg_rtx (mode);
1421 /* Indicate for flow that the entire target reg is being set. */
1422 emit_clobber (target);
1424 for (i = 0; i < nwords; i++)
1426 /* If I is 0, use the low-order word in both field and target;
1427 if I is 1, use the next to lowest word; and so on. */
1428 /* Word number in TARGET to use. */
1429 unsigned int wordnum
1430 = (WORDS_BIG_ENDIAN
1431 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1432 : i);
1433 /* Offset from start of field in OP0. */
1434 unsigned int bit_offset = (WORDS_BIG_ENDIAN
1435 ? MAX (0, ((int) bitsize - ((int) i + 1)
1436 * (int) BITS_PER_WORD))
1437 : (int) i * BITS_PER_WORD);
1438 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1439 rtx result_part
1440 = extract_bit_field (op0, MIN (BITS_PER_WORD,
1441 bitsize - i * BITS_PER_WORD),
1442 bitnum + bit_offset, 1, target_part, mode,
1443 word_mode);
1445 gcc_assert (target_part);
1447 if (result_part != target_part)
1448 emit_move_insn (target_part, result_part);
1451 if (unsignedp)
1453 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1454 need to be zero'd out. */
1455 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1457 unsigned int i, total_words;
1459 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1460 for (i = nwords; i < total_words; i++)
1461 emit_move_insn
1462 (operand_subword (target,
1463 WORDS_BIG_ENDIAN ? total_words - i - 1 : i,
1464 1, VOIDmode),
1465 const0_rtx);
1467 return target;
1470 /* Signed bit field: sign-extend with two arithmetic shifts. */
1471 target = expand_shift (LSHIFT_EXPR, mode, target,
1472 build_int_cst (NULL_TREE,
1473 GET_MODE_BITSIZE (mode) - bitsize),
1474 NULL_RTX, 0);
1475 return expand_shift (RSHIFT_EXPR, mode, target,
1476 build_int_cst (NULL_TREE,
1477 GET_MODE_BITSIZE (mode) - bitsize),
1478 NULL_RTX, 0);
1481 /* From here on we know the desired field is smaller than a word. */
1483 /* Check if there is a correspondingly-sized integer field, so we can
1484 safely extract it as one size of integer, if necessary; then
1485 truncate or extend to the size that is wanted; then use SUBREGs or
1486 convert_to_mode to get one of the modes we really wanted. */
1488 int_mode = int_mode_for_mode (tmode);
1489 if (int_mode == BLKmode)
1490 int_mode = int_mode_for_mode (mode);
1491 /* Should probably push op0 out to memory and then do a load. */
1492 gcc_assert (int_mode != BLKmode);
1494 /* OFFSET is the number of words or bytes (UNIT says which)
1495 from STR_RTX to the first word or byte containing part of the field. */
1496 if (!MEM_P (op0))
1498 if (offset != 0
1499 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1501 if (!REG_P (op0))
1502 op0 = copy_to_reg (op0);
1503 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0),
1504 op0, (offset * UNITS_PER_WORD));
1506 offset = 0;
1509 /* Now OFFSET is nonzero only for memory operands. */
1510 ext_mode = mode_for_extraction (unsignedp ? EP_extzv : EP_extv, 0);
1511 icode = unsignedp ? CODE_FOR_extzv : CODE_FOR_extv;
1512 if (ext_mode != MAX_MACHINE_MODE
1513 && bitsize > 0
1514 && GET_MODE_BITSIZE (ext_mode) >= bitsize
1515 /* If op0 is a register, we need it in EXT_MODE to make it
1516 acceptable to the format of ext(z)v. */
1517 && !(GET_CODE (op0) == SUBREG && GET_MODE (op0) != ext_mode)
1518 && !((REG_P (op0) || GET_CODE (op0) == SUBREG)
1519 && (bitsize + bitpos > GET_MODE_BITSIZE (ext_mode)))
1520 && check_predicate_volatile_ok (icode, 1, op0, GET_MODE (op0)))
1522 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset;
1523 rtx bitsize_rtx, bitpos_rtx;
1524 rtx last = get_last_insn ();
1525 rtx xop0 = op0;
1526 rtx xtarget = target;
1527 rtx xspec_target = target;
1528 rtx xspec_target_subreg = 0;
1529 rtx pat;
1531 /* If op0 is a register, we need it in EXT_MODE to make it
1532 acceptable to the format of ext(z)v. */
1533 if (REG_P (xop0) && GET_MODE (xop0) != ext_mode)
1534 xop0 = gen_rtx_SUBREG (ext_mode, xop0, 0);
1535 if (MEM_P (xop0))
1536 /* Get ref to first byte containing part of the field. */
1537 xop0 = adjust_address (xop0, byte_mode, xoffset);
1539 /* On big-endian machines, we count bits from the most significant.
1540 If the bit field insn does not, we must invert. */
1541 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1542 xbitpos = unit - bitsize - xbitpos;
1544 /* Now convert from counting within UNIT to counting in EXT_MODE. */
1545 if (BITS_BIG_ENDIAN && !MEM_P (xop0))
1546 xbitpos += GET_MODE_BITSIZE (ext_mode) - unit;
1548 unit = GET_MODE_BITSIZE (ext_mode);
1550 if (xtarget == 0)
1551 xtarget = xspec_target = gen_reg_rtx (tmode);
1553 if (GET_MODE (xtarget) != ext_mode)
1555 /* Don't use LHS paradoxical subreg if explicit truncation is needed
1556 between the mode of the extraction (word_mode) and the target
1557 mode. Instead, create a temporary and use convert_move to set
1558 the target. */
1559 if (REG_P (xtarget)
1560 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (GET_MODE (xtarget)),
1561 GET_MODE_BITSIZE (ext_mode)))
1563 xtarget = gen_lowpart (ext_mode, xtarget);
1564 if (GET_MODE_SIZE (ext_mode)
1565 > GET_MODE_SIZE (GET_MODE (xspec_target)))
1566 xspec_target_subreg = xtarget;
1568 else
1569 xtarget = gen_reg_rtx (ext_mode);
1572 /* If this machine's ext(z)v insists on a register target,
1573 make sure we have one. */
1574 if (!insn_data[(int) icode].operand[0].predicate (xtarget, ext_mode))
1575 xtarget = gen_reg_rtx (ext_mode);
1577 bitsize_rtx = GEN_INT (bitsize);
1578 bitpos_rtx = GEN_INT (xbitpos);
1580 pat = (unsignedp
1581 ? gen_extzv (xtarget, xop0, bitsize_rtx, bitpos_rtx)
1582 : gen_extv (xtarget, xop0, bitsize_rtx, bitpos_rtx));
1583 if (pat)
1585 emit_insn (pat);
1586 if (xtarget == xspec_target)
1587 return xtarget;
1588 if (xtarget == xspec_target_subreg)
1589 return xspec_target;
1590 return convert_extracted_bit_field (xtarget, mode, tmode, unsignedp);
1592 delete_insns_since (last);
1595 /* If OP0 is a memory, try copying it to a register and seeing if a
1596 cheap register alternative is available. */
1597 if (ext_mode != MAX_MACHINE_MODE && MEM_P (op0))
1599 enum machine_mode bestmode;
1601 /* Get the mode to use for inserting into this field. If
1602 OP0 is BLKmode, get the smallest mode consistent with the
1603 alignment. If OP0 is a non-BLKmode object that is no
1604 wider than EXT_MODE, use its mode. Otherwise, use the
1605 smallest mode containing the field. */
1607 if (GET_MODE (op0) == BLKmode
1608 || (ext_mode != MAX_MACHINE_MODE
1609 && GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (ext_mode)))
1610 bestmode = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0),
1611 (ext_mode == MAX_MACHINE_MODE
1612 ? VOIDmode : ext_mode),
1613 MEM_VOLATILE_P (op0));
1614 else
1615 bestmode = GET_MODE (op0);
1617 if (bestmode != VOIDmode
1618 && !(SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0))
1619 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0)))
1621 unsigned HOST_WIDE_INT xoffset, xbitpos;
1623 /* Compute the offset as a multiple of this unit,
1624 counting in bytes. */
1625 unit = GET_MODE_BITSIZE (bestmode);
1626 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode);
1627 xbitpos = bitnum % unit;
1629 /* Make sure the register is big enough for the whole field. */
1630 if (xoffset * BITS_PER_UNIT + unit
1631 >= offset * BITS_PER_UNIT + bitsize)
1633 rtx last, result, xop0;
1635 last = get_last_insn ();
1637 /* Fetch it to a register in that size. */
1638 xop0 = adjust_address (op0, bestmode, xoffset);
1639 xop0 = force_reg (bestmode, xop0);
1640 result = extract_bit_field_1 (xop0, bitsize, xbitpos,
1641 unsignedp, target,
1642 mode, tmode, false);
1643 if (result)
1644 return result;
1646 delete_insns_since (last);
1651 if (!fallback_p)
1652 return NULL;
1654 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize,
1655 bitpos, target, unsignedp);
1656 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1659 /* Generate code to extract a byte-field from STR_RTX
1660 containing BITSIZE bits, starting at BITNUM,
1661 and put it in TARGET if possible (if TARGET is nonzero).
1662 Regardless of TARGET, we return the rtx for where the value is placed.
1664 STR_RTX is the structure containing the byte (a REG or MEM).
1665 UNSIGNEDP is nonzero if this is an unsigned bit field.
1666 MODE is the natural mode of the field value once extracted.
1667 TMODE is the mode the caller would like the value to have;
1668 but the value may be returned with type MODE instead.
1670 If a TARGET is specified and we can store in it at no extra cost,
1671 we do so, and return TARGET.
1672 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1673 if they are equally easy. */
1676 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1677 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1678 enum machine_mode mode, enum machine_mode tmode)
1680 return extract_bit_field_1 (str_rtx, bitsize, bitnum, unsignedp,
1681 target, mode, tmode, true);
1684 /* Extract a bit field using shifts and boolean operations
1685 Returns an rtx to represent the value.
1686 OP0 addresses a register (word) or memory (byte).
1687 BITPOS says which bit within the word or byte the bit field starts in.
1688 OFFSET says how many bytes farther the bit field starts;
1689 it is 0 if OP0 is a register.
1690 BITSIZE says how many bits long the bit field is.
1691 (If OP0 is a register, it may be narrower than a full word,
1692 but BITPOS still counts within a full word,
1693 which is significant on bigendian machines.)
1695 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1696 If TARGET is nonzero, attempts to store the value there
1697 and return TARGET, but this is not guaranteed.
1698 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1700 static rtx
1701 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1702 unsigned HOST_WIDE_INT offset,
1703 unsigned HOST_WIDE_INT bitsize,
1704 unsigned HOST_WIDE_INT bitpos, rtx target,
1705 int unsignedp)
1707 unsigned int total_bits = BITS_PER_WORD;
1708 enum machine_mode mode;
1710 if (GET_CODE (op0) == SUBREG || REG_P (op0))
1712 /* Special treatment for a bit field split across two registers. */
1713 if (bitsize + bitpos > BITS_PER_WORD)
1714 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp);
1716 else
1718 /* Get the proper mode to use for this field. We want a mode that
1719 includes the entire field. If such a mode would be larger than
1720 a word, we won't be doing the extraction the normal way. */
1722 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT,
1723 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0));
1725 if (mode == VOIDmode)
1726 /* The only way this should occur is if the field spans word
1727 boundaries. */
1728 return extract_split_bit_field (op0, bitsize,
1729 bitpos + offset * BITS_PER_UNIT,
1730 unsignedp);
1732 total_bits = GET_MODE_BITSIZE (mode);
1734 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to
1735 be in the range 0 to total_bits-1, and put any excess bytes in
1736 OFFSET. */
1737 if (bitpos >= total_bits)
1739 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT);
1740 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT)
1741 * BITS_PER_UNIT);
1744 /* Get ref to an aligned byte, halfword, or word containing the field.
1745 Adjust BITPOS to be position within a word,
1746 and OFFSET to be the offset of that word.
1747 Then alter OP0 to refer to that word. */
1748 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT;
1749 offset -= (offset % (total_bits / BITS_PER_UNIT));
1750 op0 = adjust_address (op0, mode, offset);
1753 mode = GET_MODE (op0);
1755 if (BYTES_BIG_ENDIAN)
1756 /* BITPOS is the distance between our msb and that of OP0.
1757 Convert it to the distance from the lsb. */
1758 bitpos = total_bits - bitsize - bitpos;
1760 /* Now BITPOS is always the distance between the field's lsb and that of OP0.
1761 We have reduced the big-endian case to the little-endian case. */
1763 if (unsignedp)
1765 if (bitpos)
1767 /* If the field does not already start at the lsb,
1768 shift it so it does. */
1769 tree amount = build_int_cst (NULL_TREE, bitpos);
1770 /* Maybe propagate the target for the shift. */
1771 /* But not if we will return it--could confuse integrate.c. */
1772 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1773 if (tmode != mode) subtarget = 0;
1774 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1776 /* Convert the value to the desired mode. */
1777 if (mode != tmode)
1778 op0 = convert_to_mode (tmode, op0, 1);
1780 /* Unless the msb of the field used to be the msb when we shifted,
1781 mask out the upper bits. */
1783 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize)
1784 return expand_binop (GET_MODE (op0), and_optab, op0,
1785 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1786 target, 1, OPTAB_LIB_WIDEN);
1787 return op0;
1790 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1791 then arithmetic-shift its lsb to the lsb of the word. */
1792 op0 = force_reg (mode, op0);
1793 if (mode != tmode)
1794 target = 0;
1796 /* Find the narrowest integer mode that contains the field. */
1798 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1799 mode = GET_MODE_WIDER_MODE (mode))
1800 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos)
1802 op0 = convert_to_mode (mode, op0, 0);
1803 break;
1806 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos))
1808 tree amount
1809 = build_int_cst (NULL_TREE,
1810 GET_MODE_BITSIZE (mode) - (bitsize + bitpos));
1811 /* Maybe propagate the target for the shift. */
1812 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1813 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1816 return expand_shift (RSHIFT_EXPR, mode, op0,
1817 build_int_cst (NULL_TREE,
1818 GET_MODE_BITSIZE (mode) - bitsize),
1819 target, 0);
1822 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1823 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1824 complement of that if COMPLEMENT. The mask is truncated if
1825 necessary to the width of mode MODE. The mask is zero-extended if
1826 BITSIZE+BITPOS is too small for MODE. */
1828 static rtx
1829 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1831 HOST_WIDE_INT masklow, maskhigh;
1833 if (bitsize == 0)
1834 masklow = 0;
1835 else if (bitpos < HOST_BITS_PER_WIDE_INT)
1836 masklow = (HOST_WIDE_INT) -1 << bitpos;
1837 else
1838 masklow = 0;
1840 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT)
1841 masklow &= ((unsigned HOST_WIDE_INT) -1
1842 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1844 if (bitpos <= HOST_BITS_PER_WIDE_INT)
1845 maskhigh = -1;
1846 else
1847 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT);
1849 if (bitsize == 0)
1850 maskhigh = 0;
1851 else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT)
1852 maskhigh &= ((unsigned HOST_WIDE_INT) -1
1853 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize));
1854 else
1855 maskhigh = 0;
1857 if (complement)
1859 maskhigh = ~maskhigh;
1860 masklow = ~masklow;
1863 return immed_double_const (masklow, maskhigh, mode);
1866 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1867 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */
1869 static rtx
1870 lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize)
1872 unsigned HOST_WIDE_INT v = INTVAL (value);
1873 HOST_WIDE_INT low, high;
1875 if (bitsize < HOST_BITS_PER_WIDE_INT)
1876 v &= ~((HOST_WIDE_INT) -1 << bitsize);
1878 if (bitpos < HOST_BITS_PER_WIDE_INT)
1880 low = v << bitpos;
1881 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0);
1883 else
1885 low = 0;
1886 high = v << (bitpos - HOST_BITS_PER_WIDE_INT);
1889 return immed_double_const (low, high, mode);
1892 /* Extract a bit field that is split across two words
1893 and return an RTX for the result.
1895 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1896 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1897 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1899 static rtx
1900 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1901 unsigned HOST_WIDE_INT bitpos, int unsignedp)
1903 unsigned int unit;
1904 unsigned int bitsdone = 0;
1905 rtx result = NULL_RTX;
1906 int first = 1;
1908 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1909 much at a time. */
1910 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1911 unit = BITS_PER_WORD;
1912 else
1913 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1915 while (bitsdone < bitsize)
1917 unsigned HOST_WIDE_INT thissize;
1918 rtx part, word;
1919 unsigned HOST_WIDE_INT thispos;
1920 unsigned HOST_WIDE_INT offset;
1922 offset = (bitpos + bitsdone) / unit;
1923 thispos = (bitpos + bitsdone) % unit;
1925 /* THISSIZE must not overrun a word boundary. Otherwise,
1926 extract_fixed_bit_field will call us again, and we will mutually
1927 recurse forever. */
1928 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1929 thissize = MIN (thissize, unit - thispos);
1931 /* If OP0 is a register, then handle OFFSET here.
1933 When handling multiword bitfields, extract_bit_field may pass
1934 down a word_mode SUBREG of a larger REG for a bitfield that actually
1935 crosses a word boundary. Thus, for a SUBREG, we must find
1936 the current word starting from the base register. */
1937 if (GET_CODE (op0) == SUBREG)
1939 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1940 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1941 GET_MODE (SUBREG_REG (op0)));
1942 offset = 0;
1944 else if (REG_P (op0))
1946 word = operand_subword_force (op0, offset, GET_MODE (op0));
1947 offset = 0;
1949 else
1950 word = op0;
1952 /* Extract the parts in bit-counting order,
1953 whose meaning is determined by BYTES_PER_UNIT.
1954 OFFSET is in UNITs, and UNIT is in bits.
1955 extract_fixed_bit_field wants offset in bytes. */
1956 part = extract_fixed_bit_field (word_mode, word,
1957 offset * unit / BITS_PER_UNIT,
1958 thissize, thispos, 0, 1);
1959 bitsdone += thissize;
1961 /* Shift this part into place for the result. */
1962 if (BYTES_BIG_ENDIAN)
1964 if (bitsize != bitsdone)
1965 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1966 build_int_cst (NULL_TREE, bitsize - bitsdone),
1967 0, 1);
1969 else
1971 if (bitsdone != thissize)
1972 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1973 build_int_cst (NULL_TREE,
1974 bitsdone - thissize), 0, 1);
1977 if (first)
1978 result = part;
1979 else
1980 /* Combine the parts with bitwise or. This works
1981 because we extracted each part as an unsigned bit field. */
1982 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
1983 OPTAB_LIB_WIDEN);
1985 first = 0;
1988 /* Unsigned bit field: we are done. */
1989 if (unsignedp)
1990 return result;
1991 /* Signed bit field: sign-extend with two arithmetic shifts. */
1992 result = expand_shift (LSHIFT_EXPR, word_mode, result,
1993 build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize),
1994 NULL_RTX, 0);
1995 return expand_shift (RSHIFT_EXPR, word_mode, result,
1996 build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize),
1997 NULL_RTX, 0);
2000 /* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
2001 the bit pattern. SRC_MODE is the mode of SRC; if this is smaller than
2002 MODE, fill the upper bits with zeros. Fail if the layout of either
2003 mode is unknown (as for CC modes) or if the extraction would involve
2004 unprofitable mode punning. Return the value on success, otherwise
2005 return null.
2007 This is different from gen_lowpart* in these respects:
2009 - the returned value must always be considered an rvalue
2011 - when MODE is wider than SRC_MODE, the extraction involves
2012 a zero extension
2014 - when MODE is smaller than SRC_MODE, the extraction involves
2015 a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
2017 In other words, this routine performs a computation, whereas the
2018 gen_lowpart* routines are conceptually lvalue or rvalue subreg
2019 operations. */
2022 extract_low_bits (enum machine_mode mode, enum machine_mode src_mode, rtx src)
2024 enum machine_mode int_mode, src_int_mode;
2026 if (mode == src_mode)
2027 return src;
2029 if (CONSTANT_P (src))
2031 /* simplify_gen_subreg can't be used here, as if simplify_subreg
2032 fails, it will happily create (subreg (symbol_ref)) or similar
2033 invalid SUBREGs. */
2034 unsigned int byte = subreg_lowpart_offset (mode, src_mode);
2035 rtx ret = simplify_subreg (mode, src, src_mode, byte);
2036 if (ret)
2037 return ret;
2039 if (GET_MODE (src) == VOIDmode
2040 || !validate_subreg (mode, src_mode, src, byte))
2041 return NULL_RTX;
2043 src = force_reg (GET_MODE (src), src);
2044 return gen_rtx_SUBREG (mode, src, byte);
2047 if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
2048 return NULL_RTX;
2050 if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
2051 && MODES_TIEABLE_P (mode, src_mode))
2053 rtx x = gen_lowpart_common (mode, src);
2054 if (x)
2055 return x;
2058 src_int_mode = int_mode_for_mode (src_mode);
2059 int_mode = int_mode_for_mode (mode);
2060 if (src_int_mode == BLKmode || int_mode == BLKmode)
2061 return NULL_RTX;
2063 if (!MODES_TIEABLE_P (src_int_mode, src_mode))
2064 return NULL_RTX;
2065 if (!MODES_TIEABLE_P (int_mode, mode))
2066 return NULL_RTX;
2068 src = gen_lowpart (src_int_mode, src);
2069 src = convert_modes (int_mode, src_int_mode, src, true);
2070 src = gen_lowpart (mode, src);
2071 return src;
2074 /* Add INC into TARGET. */
2076 void
2077 expand_inc (rtx target, rtx inc)
2079 rtx value = expand_binop (GET_MODE (target), add_optab,
2080 target, inc,
2081 target, 0, OPTAB_LIB_WIDEN);
2082 if (value != target)
2083 emit_move_insn (target, value);
2086 /* Subtract DEC from TARGET. */
2088 void
2089 expand_dec (rtx target, rtx dec)
2091 rtx value = expand_binop (GET_MODE (target), sub_optab,
2092 target, dec,
2093 target, 0, OPTAB_LIB_WIDEN);
2094 if (value != target)
2095 emit_move_insn (target, value);
2098 /* Output a shift instruction for expression code CODE,
2099 with SHIFTED being the rtx for the value to shift,
2100 and AMOUNT the tree for the amount to shift by.
2101 Store the result in the rtx TARGET, if that is convenient.
2102 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2103 Return the rtx for where the value is. */
2106 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
2107 tree amount, rtx target, int unsignedp)
2109 rtx op1, temp = 0;
2110 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2111 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2112 optab lshift_optab = ashl_optab;
2113 optab rshift_arith_optab = ashr_optab;
2114 optab rshift_uns_optab = lshr_optab;
2115 optab lrotate_optab = rotl_optab;
2116 optab rrotate_optab = rotr_optab;
2117 enum machine_mode op1_mode;
2118 int attempt;
2119 bool speed = optimize_insn_for_speed_p ();
2121 op1 = expand_normal (amount);
2122 op1_mode = GET_MODE (op1);
2124 /* Determine whether the shift/rotate amount is a vector, or scalar. If the
2125 shift amount is a vector, use the vector/vector shift patterns. */
2126 if (VECTOR_MODE_P (mode) && VECTOR_MODE_P (op1_mode))
2128 lshift_optab = vashl_optab;
2129 rshift_arith_optab = vashr_optab;
2130 rshift_uns_optab = vlshr_optab;
2131 lrotate_optab = vrotl_optab;
2132 rrotate_optab = vrotr_optab;
2135 /* Previously detected shift-counts computed by NEGATE_EXPR
2136 and shifted in the other direction; but that does not work
2137 on all machines. */
2139 if (SHIFT_COUNT_TRUNCATED)
2141 if (CONST_INT_P (op1)
2142 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2143 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
2144 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2145 % GET_MODE_BITSIZE (mode));
2146 else if (GET_CODE (op1) == SUBREG
2147 && subreg_lowpart_p (op1)
2148 && INTEGRAL_MODE_P (GET_MODE (SUBREG_REG (op1))))
2149 op1 = SUBREG_REG (op1);
2152 if (op1 == const0_rtx)
2153 return shifted;
2155 /* Check whether its cheaper to implement a left shift by a constant
2156 bit count by a sequence of additions. */
2157 if (code == LSHIFT_EXPR
2158 && CONST_INT_P (op1)
2159 && INTVAL (op1) > 0
2160 && INTVAL (op1) < GET_MODE_BITSIZE (mode)
2161 && INTVAL (op1) < MAX_BITS_PER_WORD
2162 && shift_cost[speed][mode][INTVAL (op1)] > INTVAL (op1) * add_cost[speed][mode]
2163 && shift_cost[speed][mode][INTVAL (op1)] != MAX_COST)
2165 int i;
2166 for (i = 0; i < INTVAL (op1); i++)
2168 temp = force_reg (mode, shifted);
2169 shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2170 unsignedp, OPTAB_LIB_WIDEN);
2172 return shifted;
2175 for (attempt = 0; temp == 0 && attempt < 3; attempt++)
2177 enum optab_methods methods;
2179 if (attempt == 0)
2180 methods = OPTAB_DIRECT;
2181 else if (attempt == 1)
2182 methods = OPTAB_WIDEN;
2183 else
2184 methods = OPTAB_LIB_WIDEN;
2186 if (rotate)
2188 /* Widening does not work for rotation. */
2189 if (methods == OPTAB_WIDEN)
2190 continue;
2191 else if (methods == OPTAB_LIB_WIDEN)
2193 /* If we have been unable to open-code this by a rotation,
2194 do it as the IOR of two shifts. I.e., to rotate A
2195 by N bits, compute (A << N) | ((unsigned) A >> (C - N))
2196 where C is the bitsize of A.
2198 It is theoretically possible that the target machine might
2199 not be able to perform either shift and hence we would
2200 be making two libcalls rather than just the one for the
2201 shift (similarly if IOR could not be done). We will allow
2202 this extremely unlikely lossage to avoid complicating the
2203 code below. */
2205 rtx subtarget = target == shifted ? 0 : target;
2206 tree new_amount, other_amount;
2207 rtx temp1;
2208 tree type = TREE_TYPE (amount);
2209 if (GET_MODE (op1) != TYPE_MODE (type)
2210 && GET_MODE (op1) != VOIDmode)
2211 op1 = convert_to_mode (TYPE_MODE (type), op1, 1);
2212 new_amount = make_tree (type, op1);
2213 other_amount
2214 = fold_build2 (MINUS_EXPR, type,
2215 build_int_cst (type, GET_MODE_BITSIZE (mode)),
2216 new_amount);
2218 shifted = force_reg (mode, shifted);
2220 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2221 mode, shifted, new_amount, 0, 1);
2222 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2223 mode, shifted, other_amount, subtarget, 1);
2224 return expand_binop (mode, ior_optab, temp, temp1, target,
2225 unsignedp, methods);
2228 temp = expand_binop (mode,
2229 left ? lrotate_optab : rrotate_optab,
2230 shifted, op1, target, unsignedp, methods);
2232 else if (unsignedp)
2233 temp = expand_binop (mode,
2234 left ? lshift_optab : rshift_uns_optab,
2235 shifted, op1, target, unsignedp, methods);
2237 /* Do arithmetic shifts.
2238 Also, if we are going to widen the operand, we can just as well
2239 use an arithmetic right-shift instead of a logical one. */
2240 if (temp == 0 && ! rotate
2241 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2243 enum optab_methods methods1 = methods;
2245 /* If trying to widen a log shift to an arithmetic shift,
2246 don't accept an arithmetic shift of the same size. */
2247 if (unsignedp)
2248 methods1 = OPTAB_MUST_WIDEN;
2250 /* Arithmetic shift */
2252 temp = expand_binop (mode,
2253 left ? lshift_optab : rshift_arith_optab,
2254 shifted, op1, target, unsignedp, methods1);
2257 /* We used to try extzv here for logical right shifts, but that was
2258 only useful for one machine, the VAX, and caused poor code
2259 generation there for lshrdi3, so the code was deleted and a
2260 define_expand for lshrsi3 was added to vax.md. */
2263 gcc_assert (temp);
2264 return temp;
2267 enum alg_code {
2268 alg_unknown,
2269 alg_zero,
2270 alg_m, alg_shift,
2271 alg_add_t_m2,
2272 alg_sub_t_m2,
2273 alg_add_factor,
2274 alg_sub_factor,
2275 alg_add_t2_m,
2276 alg_sub_t2_m,
2277 alg_impossible
2280 /* This structure holds the "cost" of a multiply sequence. The
2281 "cost" field holds the total rtx_cost of every operator in the
2282 synthetic multiplication sequence, hence cost(a op b) is defined
2283 as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero.
2284 The "latency" field holds the minimum possible latency of the
2285 synthetic multiply, on a hypothetical infinitely parallel CPU.
2286 This is the critical path, or the maximum height, of the expression
2287 tree which is the sum of rtx_costs on the most expensive path from
2288 any leaf to the root. Hence latency(a op b) is defined as zero for
2289 leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise. */
2291 struct mult_cost {
2292 short cost; /* Total rtx_cost of the multiplication sequence. */
2293 short latency; /* The latency of the multiplication sequence. */
2296 /* This macro is used to compare a pointer to a mult_cost against an
2297 single integer "rtx_cost" value. This is equivalent to the macro
2298 CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}. */
2299 #define MULT_COST_LESS(X,Y) ((X)->cost < (Y) \
2300 || ((X)->cost == (Y) && (X)->latency < (Y)))
2302 /* This macro is used to compare two pointers to mult_costs against
2303 each other. The macro returns true if X is cheaper than Y.
2304 Currently, the cheaper of two mult_costs is the one with the
2305 lower "cost". If "cost"s are tied, the lower latency is cheaper. */
2306 #define CHEAPER_MULT_COST(X,Y) ((X)->cost < (Y)->cost \
2307 || ((X)->cost == (Y)->cost \
2308 && (X)->latency < (Y)->latency))
2310 /* This structure records a sequence of operations.
2311 `ops' is the number of operations recorded.
2312 `cost' is their total cost.
2313 The operations are stored in `op' and the corresponding
2314 logarithms of the integer coefficients in `log'.
2316 These are the operations:
2317 alg_zero total := 0;
2318 alg_m total := multiplicand;
2319 alg_shift total := total * coeff
2320 alg_add_t_m2 total := total + multiplicand * coeff;
2321 alg_sub_t_m2 total := total - multiplicand * coeff;
2322 alg_add_factor total := total * coeff + total;
2323 alg_sub_factor total := total * coeff - total;
2324 alg_add_t2_m total := total * coeff + multiplicand;
2325 alg_sub_t2_m total := total * coeff - multiplicand;
2327 The first operand must be either alg_zero or alg_m. */
2329 struct algorithm
2331 struct mult_cost cost;
2332 short ops;
2333 /* The size of the OP and LOG fields are not directly related to the
2334 word size, but the worst-case algorithms will be if we have few
2335 consecutive ones or zeros, i.e., a multiplicand like 10101010101...
2336 In that case we will generate shift-by-2, add, shift-by-2, add,...,
2337 in total wordsize operations. */
2338 enum alg_code op[MAX_BITS_PER_WORD];
2339 char log[MAX_BITS_PER_WORD];
2342 /* The entry for our multiplication cache/hash table. */
2343 struct alg_hash_entry {
2344 /* The number we are multiplying by. */
2345 unsigned HOST_WIDE_INT t;
2347 /* The mode in which we are multiplying something by T. */
2348 enum machine_mode mode;
2350 /* The best multiplication algorithm for t. */
2351 enum alg_code alg;
2353 /* The cost of multiplication if ALG_CODE is not alg_impossible.
2354 Otherwise, the cost within which multiplication by T is
2355 impossible. */
2356 struct mult_cost cost;
2358 /* OPtimized for speed? */
2359 bool speed;
2362 /* The number of cache/hash entries. */
2363 #if HOST_BITS_PER_WIDE_INT == 64
2364 #define NUM_ALG_HASH_ENTRIES 1031
2365 #else
2366 #define NUM_ALG_HASH_ENTRIES 307
2367 #endif
2369 /* Each entry of ALG_HASH caches alg_code for some integer. This is
2370 actually a hash table. If we have a collision, that the older
2371 entry is kicked out. */
2372 static struct alg_hash_entry alg_hash[NUM_ALG_HASH_ENTRIES];
2374 /* Indicates the type of fixup needed after a constant multiplication.
2375 BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2376 the result should be negated, and ADD_VARIANT means that the
2377 multiplicand should be added to the result. */
2378 enum mult_variant {basic_variant, negate_variant, add_variant};
2380 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2381 const struct mult_cost *, enum machine_mode mode);
2382 static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT,
2383 struct algorithm *, enum mult_variant *, int);
2384 static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx,
2385 const struct algorithm *, enum mult_variant);
2386 static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int,
2387 int, rtx *, int *, int *);
2388 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2389 static rtx extract_high_half (enum machine_mode, rtx);
2390 static rtx expand_mult_highpart (enum machine_mode, rtx, rtx, rtx, int, int);
2391 static rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx,
2392 int, int);
2393 /* Compute and return the best algorithm for multiplying by T.
2394 The algorithm must cost less than cost_limit
2395 If retval.cost >= COST_LIMIT, no algorithm was found and all
2396 other field of the returned struct are undefined.
2397 MODE is the machine mode of the multiplication. */
2399 static void
2400 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2401 const struct mult_cost *cost_limit, enum machine_mode mode)
2403 int m;
2404 struct algorithm *alg_in, *best_alg;
2405 struct mult_cost best_cost;
2406 struct mult_cost new_limit;
2407 int op_cost, op_latency;
2408 unsigned HOST_WIDE_INT orig_t = t;
2409 unsigned HOST_WIDE_INT q;
2410 int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode));
2411 int hash_index;
2412 bool cache_hit = false;
2413 enum alg_code cache_alg = alg_zero;
2414 bool speed = optimize_insn_for_speed_p ();
2416 /* Indicate that no algorithm is yet found. If no algorithm
2417 is found, this value will be returned and indicate failure. */
2418 alg_out->cost.cost = cost_limit->cost + 1;
2419 alg_out->cost.latency = cost_limit->latency + 1;
2421 if (cost_limit->cost < 0
2422 || (cost_limit->cost == 0 && cost_limit->latency <= 0))
2423 return;
2425 /* Restrict the bits of "t" to the multiplication's mode. */
2426 t &= GET_MODE_MASK (mode);
2428 /* t == 1 can be done in zero cost. */
2429 if (t == 1)
2431 alg_out->ops = 1;
2432 alg_out->cost.cost = 0;
2433 alg_out->cost.latency = 0;
2434 alg_out->op[0] = alg_m;
2435 return;
2438 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2439 fail now. */
2440 if (t == 0)
2442 if (MULT_COST_LESS (cost_limit, zero_cost[speed]))
2443 return;
2444 else
2446 alg_out->ops = 1;
2447 alg_out->cost.cost = zero_cost[speed];
2448 alg_out->cost.latency = zero_cost[speed];
2449 alg_out->op[0] = alg_zero;
2450 return;
2454 /* We'll be needing a couple extra algorithm structures now. */
2456 alg_in = XALLOCA (struct algorithm);
2457 best_alg = XALLOCA (struct algorithm);
2458 best_cost = *cost_limit;
2460 /* Compute the hash index. */
2461 hash_index = (t ^ (unsigned int) mode ^ (speed * 256)) % NUM_ALG_HASH_ENTRIES;
2463 /* See if we already know what to do for T. */
2464 if (alg_hash[hash_index].t == t
2465 && alg_hash[hash_index].mode == mode
2466 && alg_hash[hash_index].mode == mode
2467 && alg_hash[hash_index].speed == speed
2468 && alg_hash[hash_index].alg != alg_unknown)
2470 cache_alg = alg_hash[hash_index].alg;
2472 if (cache_alg == alg_impossible)
2474 /* The cache tells us that it's impossible to synthesize
2475 multiplication by T within alg_hash[hash_index].cost. */
2476 if (!CHEAPER_MULT_COST (&alg_hash[hash_index].cost, cost_limit))
2477 /* COST_LIMIT is at least as restrictive as the one
2478 recorded in the hash table, in which case we have no
2479 hope of synthesizing a multiplication. Just
2480 return. */
2481 return;
2483 /* If we get here, COST_LIMIT is less restrictive than the
2484 one recorded in the hash table, so we may be able to
2485 synthesize a multiplication. Proceed as if we didn't
2486 have the cache entry. */
2488 else
2490 if (CHEAPER_MULT_COST (cost_limit, &alg_hash[hash_index].cost))
2491 /* The cached algorithm shows that this multiplication
2492 requires more cost than COST_LIMIT. Just return. This
2493 way, we don't clobber this cache entry with
2494 alg_impossible but retain useful information. */
2495 return;
2497 cache_hit = true;
2499 switch (cache_alg)
2501 case alg_shift:
2502 goto do_alg_shift;
2504 case alg_add_t_m2:
2505 case alg_sub_t_m2:
2506 goto do_alg_addsub_t_m2;
2508 case alg_add_factor:
2509 case alg_sub_factor:
2510 goto do_alg_addsub_factor;
2512 case alg_add_t2_m:
2513 goto do_alg_add_t2_m;
2515 case alg_sub_t2_m:
2516 goto do_alg_sub_t2_m;
2518 default:
2519 gcc_unreachable ();
2524 /* If we have a group of zero bits at the low-order part of T, try
2525 multiplying by the remaining bits and then doing a shift. */
2527 if ((t & 1) == 0)
2529 do_alg_shift:
2530 m = floor_log2 (t & -t); /* m = number of low zero bits */
2531 if (m < maxm)
2533 q = t >> m;
2534 /* The function expand_shift will choose between a shift and
2535 a sequence of additions, so the observed cost is given as
2536 MIN (m * add_cost[speed][mode], shift_cost[speed][mode][m]). */
2537 op_cost = m * add_cost[speed][mode];
2538 if (shift_cost[speed][mode][m] < op_cost)
2539 op_cost = shift_cost[speed][mode][m];
2540 new_limit.cost = best_cost.cost - op_cost;
2541 new_limit.latency = best_cost.latency - op_cost;
2542 synth_mult (alg_in, q, &new_limit, mode);
2544 alg_in->cost.cost += op_cost;
2545 alg_in->cost.latency += op_cost;
2546 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2548 struct algorithm *x;
2549 best_cost = alg_in->cost;
2550 x = alg_in, alg_in = best_alg, best_alg = x;
2551 best_alg->log[best_alg->ops] = m;
2552 best_alg->op[best_alg->ops] = alg_shift;
2555 /* See if treating ORIG_T as a signed number yields a better
2556 sequence. Try this sequence only for a negative ORIG_T
2557 as it would be useless for a non-negative ORIG_T. */
2558 if ((HOST_WIDE_INT) orig_t < 0)
2560 /* Shift ORIG_T as follows because a right shift of a
2561 negative-valued signed type is implementation
2562 defined. */
2563 q = ~(~orig_t >> m);
2564 /* The function expand_shift will choose between a shift
2565 and a sequence of additions, so the observed cost is
2566 given as MIN (m * add_cost[speed][mode],
2567 shift_cost[speed][mode][m]). */
2568 op_cost = m * add_cost[speed][mode];
2569 if (shift_cost[speed][mode][m] < op_cost)
2570 op_cost = shift_cost[speed][mode][m];
2571 new_limit.cost = best_cost.cost - op_cost;
2572 new_limit.latency = best_cost.latency - op_cost;
2573 synth_mult (alg_in, q, &new_limit, mode);
2575 alg_in->cost.cost += op_cost;
2576 alg_in->cost.latency += op_cost;
2577 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2579 struct algorithm *x;
2580 best_cost = alg_in->cost;
2581 x = alg_in, alg_in = best_alg, best_alg = x;
2582 best_alg->log[best_alg->ops] = m;
2583 best_alg->op[best_alg->ops] = alg_shift;
2587 if (cache_hit)
2588 goto done;
2591 /* If we have an odd number, add or subtract one. */
2592 if ((t & 1) != 0)
2594 unsigned HOST_WIDE_INT w;
2596 do_alg_addsub_t_m2:
2597 for (w = 1; (w & t) != 0; w <<= 1)
2599 /* If T was -1, then W will be zero after the loop. This is another
2600 case where T ends with ...111. Handling this with (T + 1) and
2601 subtract 1 produces slightly better code and results in algorithm
2602 selection much faster than treating it like the ...0111 case
2603 below. */
2604 if (w == 0
2605 || (w > 2
2606 /* Reject the case where t is 3.
2607 Thus we prefer addition in that case. */
2608 && t != 3))
2610 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2612 op_cost = add_cost[speed][mode];
2613 new_limit.cost = best_cost.cost - op_cost;
2614 new_limit.latency = best_cost.latency - op_cost;
2615 synth_mult (alg_in, t + 1, &new_limit, mode);
2617 alg_in->cost.cost += op_cost;
2618 alg_in->cost.latency += op_cost;
2619 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2621 struct algorithm *x;
2622 best_cost = alg_in->cost;
2623 x = alg_in, alg_in = best_alg, best_alg = x;
2624 best_alg->log[best_alg->ops] = 0;
2625 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2628 else
2630 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2632 op_cost = add_cost[speed][mode];
2633 new_limit.cost = best_cost.cost - op_cost;
2634 new_limit.latency = best_cost.latency - op_cost;
2635 synth_mult (alg_in, t - 1, &new_limit, mode);
2637 alg_in->cost.cost += op_cost;
2638 alg_in->cost.latency += op_cost;
2639 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2641 struct algorithm *x;
2642 best_cost = alg_in->cost;
2643 x = alg_in, alg_in = best_alg, best_alg = x;
2644 best_alg->log[best_alg->ops] = 0;
2645 best_alg->op[best_alg->ops] = alg_add_t_m2;
2649 /* We may be able to calculate a * -7, a * -15, a * -31, etc
2650 quickly with a - a * n for some appropriate constant n. */
2651 m = exact_log2 (-orig_t + 1);
2652 if (m >= 0 && m < maxm)
2654 op_cost = shiftsub1_cost[speed][mode][m];
2655 new_limit.cost = best_cost.cost - op_cost;
2656 new_limit.latency = best_cost.latency - op_cost;
2657 synth_mult (alg_in, (unsigned HOST_WIDE_INT) (-orig_t + 1) >> m, &new_limit, mode);
2659 alg_in->cost.cost += op_cost;
2660 alg_in->cost.latency += op_cost;
2661 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2663 struct algorithm *x;
2664 best_cost = alg_in->cost;
2665 x = alg_in, alg_in = best_alg, best_alg = x;
2666 best_alg->log[best_alg->ops] = m;
2667 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2671 if (cache_hit)
2672 goto done;
2675 /* Look for factors of t of the form
2676 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2677 If we find such a factor, we can multiply by t using an algorithm that
2678 multiplies by q, shift the result by m and add/subtract it to itself.
2680 We search for large factors first and loop down, even if large factors
2681 are less probable than small; if we find a large factor we will find a
2682 good sequence quickly, and therefore be able to prune (by decreasing
2683 COST_LIMIT) the search. */
2685 do_alg_addsub_factor:
2686 for (m = floor_log2 (t - 1); m >= 2; m--)
2688 unsigned HOST_WIDE_INT d;
2690 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2691 if (t % d == 0 && t > d && m < maxm
2692 && (!cache_hit || cache_alg == alg_add_factor))
2694 /* If the target has a cheap shift-and-add instruction use
2695 that in preference to a shift insn followed by an add insn.
2696 Assume that the shift-and-add is "atomic" with a latency
2697 equal to its cost, otherwise assume that on superscalar
2698 hardware the shift may be executed concurrently with the
2699 earlier steps in the algorithm. */
2700 op_cost = add_cost[speed][mode] + shift_cost[speed][mode][m];
2701 if (shiftadd_cost[speed][mode][m] < op_cost)
2703 op_cost = shiftadd_cost[speed][mode][m];
2704 op_latency = op_cost;
2706 else
2707 op_latency = add_cost[speed][mode];
2709 new_limit.cost = best_cost.cost - op_cost;
2710 new_limit.latency = best_cost.latency - op_latency;
2711 synth_mult (alg_in, t / d, &new_limit, mode);
2713 alg_in->cost.cost += op_cost;
2714 alg_in->cost.latency += op_latency;
2715 if (alg_in->cost.latency < op_cost)
2716 alg_in->cost.latency = op_cost;
2717 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2719 struct algorithm *x;
2720 best_cost = alg_in->cost;
2721 x = alg_in, alg_in = best_alg, best_alg = x;
2722 best_alg->log[best_alg->ops] = m;
2723 best_alg->op[best_alg->ops] = alg_add_factor;
2725 /* Other factors will have been taken care of in the recursion. */
2726 break;
2729 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2730 if (t % d == 0 && t > d && m < maxm
2731 && (!cache_hit || cache_alg == alg_sub_factor))
2733 /* If the target has a cheap shift-and-subtract insn use
2734 that in preference to a shift insn followed by a sub insn.
2735 Assume that the shift-and-sub is "atomic" with a latency
2736 equal to it's cost, otherwise assume that on superscalar
2737 hardware the shift may be executed concurrently with the
2738 earlier steps in the algorithm. */
2739 op_cost = add_cost[speed][mode] + shift_cost[speed][mode][m];
2740 if (shiftsub0_cost[speed][mode][m] < op_cost)
2742 op_cost = shiftsub0_cost[speed][mode][m];
2743 op_latency = op_cost;
2745 else
2746 op_latency = add_cost[speed][mode];
2748 new_limit.cost = best_cost.cost - op_cost;
2749 new_limit.latency = best_cost.latency - op_latency;
2750 synth_mult (alg_in, t / d, &new_limit, mode);
2752 alg_in->cost.cost += op_cost;
2753 alg_in->cost.latency += op_latency;
2754 if (alg_in->cost.latency < op_cost)
2755 alg_in->cost.latency = op_cost;
2756 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2758 struct algorithm *x;
2759 best_cost = alg_in->cost;
2760 x = alg_in, alg_in = best_alg, best_alg = x;
2761 best_alg->log[best_alg->ops] = m;
2762 best_alg->op[best_alg->ops] = alg_sub_factor;
2764 break;
2767 if (cache_hit)
2768 goto done;
2770 /* Try shift-and-add (load effective address) instructions,
2771 i.e. do a*3, a*5, a*9. */
2772 if ((t & 1) != 0)
2774 do_alg_add_t2_m:
2775 q = t - 1;
2776 q = q & -q;
2777 m = exact_log2 (q);
2778 if (m >= 0 && m < maxm)
2780 op_cost = shiftadd_cost[speed][mode][m];
2781 new_limit.cost = best_cost.cost - op_cost;
2782 new_limit.latency = best_cost.latency - op_cost;
2783 synth_mult (alg_in, (t - 1) >> m, &new_limit, mode);
2785 alg_in->cost.cost += op_cost;
2786 alg_in->cost.latency += op_cost;
2787 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2789 struct algorithm *x;
2790 best_cost = alg_in->cost;
2791 x = alg_in, alg_in = best_alg, best_alg = x;
2792 best_alg->log[best_alg->ops] = m;
2793 best_alg->op[best_alg->ops] = alg_add_t2_m;
2796 if (cache_hit)
2797 goto done;
2799 do_alg_sub_t2_m:
2800 q = t + 1;
2801 q = q & -q;
2802 m = exact_log2 (q);
2803 if (m >= 0 && m < maxm)
2805 op_cost = shiftsub0_cost[speed][mode][m];
2806 new_limit.cost = best_cost.cost - op_cost;
2807 new_limit.latency = best_cost.latency - op_cost;
2808 synth_mult (alg_in, (t + 1) >> m, &new_limit, mode);
2810 alg_in->cost.cost += op_cost;
2811 alg_in->cost.latency += op_cost;
2812 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2814 struct algorithm *x;
2815 best_cost = alg_in->cost;
2816 x = alg_in, alg_in = best_alg, best_alg = x;
2817 best_alg->log[best_alg->ops] = m;
2818 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2821 if (cache_hit)
2822 goto done;
2825 done:
2826 /* If best_cost has not decreased, we have not found any algorithm. */
2827 if (!CHEAPER_MULT_COST (&best_cost, cost_limit))
2829 /* We failed to find an algorithm. Record alg_impossible for
2830 this case (that is, <T, MODE, COST_LIMIT>) so that next time
2831 we are asked to find an algorithm for T within the same or
2832 lower COST_LIMIT, we can immediately return to the
2833 caller. */
2834 alg_hash[hash_index].t = t;
2835 alg_hash[hash_index].mode = mode;
2836 alg_hash[hash_index].speed = speed;
2837 alg_hash[hash_index].alg = alg_impossible;
2838 alg_hash[hash_index].cost = *cost_limit;
2839 return;
2842 /* Cache the result. */
2843 if (!cache_hit)
2845 alg_hash[hash_index].t = t;
2846 alg_hash[hash_index].mode = mode;
2847 alg_hash[hash_index].speed = speed;
2848 alg_hash[hash_index].alg = best_alg->op[best_alg->ops];
2849 alg_hash[hash_index].cost.cost = best_cost.cost;
2850 alg_hash[hash_index].cost.latency = best_cost.latency;
2853 /* If we are getting a too long sequence for `struct algorithm'
2854 to record, make this search fail. */
2855 if (best_alg->ops == MAX_BITS_PER_WORD)
2856 return;
2858 /* Copy the algorithm from temporary space to the space at alg_out.
2859 We avoid using structure assignment because the majority of
2860 best_alg is normally undefined, and this is a critical function. */
2861 alg_out->ops = best_alg->ops + 1;
2862 alg_out->cost = best_cost;
2863 memcpy (alg_out->op, best_alg->op,
2864 alg_out->ops * sizeof *alg_out->op);
2865 memcpy (alg_out->log, best_alg->log,
2866 alg_out->ops * sizeof *alg_out->log);
2869 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2870 Try three variations:
2872 - a shift/add sequence based on VAL itself
2873 - a shift/add sequence based on -VAL, followed by a negation
2874 - a shift/add sequence based on VAL - 1, followed by an addition.
2876 Return true if the cheapest of these cost less than MULT_COST,
2877 describing the algorithm in *ALG and final fixup in *VARIANT. */
2879 static bool
2880 choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val,
2881 struct algorithm *alg, enum mult_variant *variant,
2882 int mult_cost)
2884 struct algorithm alg2;
2885 struct mult_cost limit;
2886 int op_cost;
2887 bool speed = optimize_insn_for_speed_p ();
2889 /* Fail quickly for impossible bounds. */
2890 if (mult_cost < 0)
2891 return false;
2893 /* Ensure that mult_cost provides a reasonable upper bound.
2894 Any constant multiplication can be performed with less
2895 than 2 * bits additions. */
2896 op_cost = 2 * GET_MODE_BITSIZE (mode) * add_cost[speed][mode];
2897 if (mult_cost > op_cost)
2898 mult_cost = op_cost;
2900 *variant = basic_variant;
2901 limit.cost = mult_cost;
2902 limit.latency = mult_cost;
2903 synth_mult (alg, val, &limit, mode);
2905 /* This works only if the inverted value actually fits in an
2906 `unsigned int' */
2907 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode))
2909 op_cost = neg_cost[speed][mode];
2910 if (MULT_COST_LESS (&alg->cost, mult_cost))
2912 limit.cost = alg->cost.cost - op_cost;
2913 limit.latency = alg->cost.latency - op_cost;
2915 else
2917 limit.cost = mult_cost - op_cost;
2918 limit.latency = mult_cost - op_cost;
2921 synth_mult (&alg2, -val, &limit, mode);
2922 alg2.cost.cost += op_cost;
2923 alg2.cost.latency += op_cost;
2924 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2925 *alg = alg2, *variant = negate_variant;
2928 /* This proves very useful for division-by-constant. */
2929 op_cost = add_cost[speed][mode];
2930 if (MULT_COST_LESS (&alg->cost, mult_cost))
2932 limit.cost = alg->cost.cost - op_cost;
2933 limit.latency = alg->cost.latency - op_cost;
2935 else
2937 limit.cost = mult_cost - op_cost;
2938 limit.latency = mult_cost - op_cost;
2941 synth_mult (&alg2, val - 1, &limit, mode);
2942 alg2.cost.cost += op_cost;
2943 alg2.cost.latency += op_cost;
2944 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2945 *alg = alg2, *variant = add_variant;
2947 return MULT_COST_LESS (&alg->cost, mult_cost);
2950 /* A subroutine of expand_mult, used for constant multiplications.
2951 Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2952 convenient. Use the shift/add sequence described by ALG and apply
2953 the final fixup specified by VARIANT. */
2955 static rtx
2956 expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val,
2957 rtx target, const struct algorithm *alg,
2958 enum mult_variant variant)
2960 HOST_WIDE_INT val_so_far;
2961 rtx insn, accum, tem;
2962 int opno;
2963 enum machine_mode nmode;
2965 /* Avoid referencing memory over and over and invalid sharing
2966 on SUBREGs. */
2967 op0 = force_reg (mode, op0);
2969 /* ACCUM starts out either as OP0 or as a zero, depending on
2970 the first operation. */
2972 if (alg->op[0] == alg_zero)
2974 accum = copy_to_mode_reg (mode, const0_rtx);
2975 val_so_far = 0;
2977 else if (alg->op[0] == alg_m)
2979 accum = copy_to_mode_reg (mode, op0);
2980 val_so_far = 1;
2982 else
2983 gcc_unreachable ();
2985 for (opno = 1; opno < alg->ops; opno++)
2987 int log = alg->log[opno];
2988 rtx shift_subtarget = optimize ? 0 : accum;
2989 rtx add_target
2990 = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2991 && !optimize)
2992 ? target : 0;
2993 rtx accum_target = optimize ? 0 : accum;
2995 switch (alg->op[opno])
2997 case alg_shift:
2998 accum = expand_shift (LSHIFT_EXPR, mode, accum,
2999 build_int_cst (NULL_TREE, log),
3000 NULL_RTX, 0);
3001 val_so_far <<= log;
3002 break;
3004 case alg_add_t_m2:
3005 tem = expand_shift (LSHIFT_EXPR, mode, op0,
3006 build_int_cst (NULL_TREE, log),
3007 NULL_RTX, 0);
3008 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3009 add_target ? add_target : accum_target);
3010 val_so_far += (HOST_WIDE_INT) 1 << log;
3011 break;
3013 case alg_sub_t_m2:
3014 tem = expand_shift (LSHIFT_EXPR, mode, op0,
3015 build_int_cst (NULL_TREE, log),
3016 NULL_RTX, 0);
3017 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
3018 add_target ? add_target : accum_target);
3019 val_so_far -= (HOST_WIDE_INT) 1 << log;
3020 break;
3022 case alg_add_t2_m:
3023 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3024 build_int_cst (NULL_TREE, log),
3025 shift_subtarget,
3027 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
3028 add_target ? add_target : accum_target);
3029 val_so_far = (val_so_far << log) + 1;
3030 break;
3032 case alg_sub_t2_m:
3033 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3034 build_int_cst (NULL_TREE, log),
3035 shift_subtarget, 0);
3036 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
3037 add_target ? add_target : accum_target);
3038 val_so_far = (val_so_far << log) - 1;
3039 break;
3041 case alg_add_factor:
3042 tem = expand_shift (LSHIFT_EXPR, mode, accum,
3043 build_int_cst (NULL_TREE, log),
3044 NULL_RTX, 0);
3045 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3046 add_target ? add_target : accum_target);
3047 val_so_far += val_so_far << log;
3048 break;
3050 case alg_sub_factor:
3051 tem = expand_shift (LSHIFT_EXPR, mode, accum,
3052 build_int_cst (NULL_TREE, log),
3053 NULL_RTX, 0);
3054 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
3055 (add_target
3056 ? add_target : (optimize ? 0 : tem)));
3057 val_so_far = (val_so_far << log) - val_so_far;
3058 break;
3060 default:
3061 gcc_unreachable ();
3064 /* Write a REG_EQUAL note on the last insn so that we can cse
3065 multiplication sequences. Note that if ACCUM is a SUBREG,
3066 we've set the inner register and must properly indicate
3067 that. */
3069 tem = op0, nmode = mode;
3070 if (GET_CODE (accum) == SUBREG)
3072 nmode = GET_MODE (SUBREG_REG (accum));
3073 tem = gen_lowpart (nmode, op0);
3076 insn = get_last_insn ();
3077 set_unique_reg_note (insn, REG_EQUAL,
3078 gen_rtx_MULT (nmode, tem,
3079 GEN_INT (val_so_far)));
3082 if (variant == negate_variant)
3084 val_so_far = -val_so_far;
3085 accum = expand_unop (mode, neg_optab, accum, target, 0);
3087 else if (variant == add_variant)
3089 val_so_far = val_so_far + 1;
3090 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
3093 /* Compare only the bits of val and val_so_far that are significant
3094 in the result mode, to avoid sign-/zero-extension confusion. */
3095 val &= GET_MODE_MASK (mode);
3096 val_so_far &= GET_MODE_MASK (mode);
3097 gcc_assert (val == val_so_far);
3099 return accum;
3102 /* Perform a multiplication and return an rtx for the result.
3103 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3104 TARGET is a suggestion for where to store the result (an rtx).
3106 We check specially for a constant integer as OP1.
3107 If you want this check for OP0 as well, then before calling
3108 you should swap the two operands if OP0 would be constant. */
3111 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3112 int unsignedp)
3114 enum mult_variant variant;
3115 struct algorithm algorithm;
3116 int max_cost;
3117 bool speed = optimize_insn_for_speed_p ();
3119 /* Handling const0_rtx here allows us to use zero as a rogue value for
3120 coeff below. */
3121 if (op1 == const0_rtx)
3122 return const0_rtx;
3123 if (op1 == const1_rtx)
3124 return op0;
3125 if (op1 == constm1_rtx)
3126 return expand_unop (mode,
3127 GET_MODE_CLASS (mode) == MODE_INT
3128 && !unsignedp && flag_trapv
3129 ? negv_optab : neg_optab,
3130 op0, target, 0);
3132 /* These are the operations that are potentially turned into a sequence
3133 of shifts and additions. */
3134 if (SCALAR_INT_MODE_P (mode)
3135 && (unsignedp || !flag_trapv))
3137 HOST_WIDE_INT coeff = 0;
3138 rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3140 /* synth_mult does an `unsigned int' multiply. As long as the mode is
3141 less than or equal in size to `unsigned int' this doesn't matter.
3142 If the mode is larger than `unsigned int', then synth_mult works
3143 only if the constant value exactly fits in an `unsigned int' without
3144 any truncation. This means that multiplying by negative values does
3145 not work; results are off by 2^32 on a 32 bit machine. */
3147 if (CONST_INT_P (op1))
3149 /* Attempt to handle multiplication of DImode values by negative
3150 coefficients, by performing the multiplication by a positive
3151 multiplier and then inverting the result. */
3152 if (INTVAL (op1) < 0
3153 && GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT)
3155 /* Its safe to use -INTVAL (op1) even for INT_MIN, as the
3156 result is interpreted as an unsigned coefficient.
3157 Exclude cost of op0 from max_cost to match the cost
3158 calculation of the synth_mult. */
3159 max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET, speed)
3160 - neg_cost[speed][mode];
3161 if (max_cost > 0
3162 && choose_mult_variant (mode, -INTVAL (op1), &algorithm,
3163 &variant, max_cost))
3165 rtx temp = expand_mult_const (mode, op0, -INTVAL (op1),
3166 NULL_RTX, &algorithm,
3167 variant);
3168 return expand_unop (mode, neg_optab, temp, target, 0);
3171 else coeff = INTVAL (op1);
3173 else if (GET_CODE (op1) == CONST_DOUBLE)
3175 /* If we are multiplying in DImode, it may still be a win
3176 to try to work with shifts and adds. */
3177 if (CONST_DOUBLE_HIGH (op1) == 0
3178 && CONST_DOUBLE_LOW (op1) > 0)
3179 coeff = CONST_DOUBLE_LOW (op1);
3180 else if (CONST_DOUBLE_LOW (op1) == 0
3181 && EXACT_POWER_OF_2_OR_ZERO_P (CONST_DOUBLE_HIGH (op1)))
3183 int shift = floor_log2 (CONST_DOUBLE_HIGH (op1))
3184 + HOST_BITS_PER_WIDE_INT;
3185 return expand_shift (LSHIFT_EXPR, mode, op0,
3186 build_int_cst (NULL_TREE, shift),
3187 target, unsignedp);
3191 /* We used to test optimize here, on the grounds that it's better to
3192 produce a smaller program when -O is not used. But this causes
3193 such a terrible slowdown sometimes that it seems better to always
3194 use synth_mult. */
3195 if (coeff != 0)
3197 /* Special case powers of two. */
3198 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3199 return expand_shift (LSHIFT_EXPR, mode, op0,
3200 build_int_cst (NULL_TREE, floor_log2 (coeff)),
3201 target, unsignedp);
3203 /* Exclude cost of op0 from max_cost to match the cost
3204 calculation of the synth_mult. */
3205 max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET, speed);
3206 if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3207 max_cost))
3208 return expand_mult_const (mode, op0, coeff, target,
3209 &algorithm, variant);
3213 if (GET_CODE (op0) == CONST_DOUBLE)
3215 rtx temp = op0;
3216 op0 = op1;
3217 op1 = temp;
3220 /* Expand x*2.0 as x+x. */
3221 if (GET_CODE (op1) == CONST_DOUBLE
3222 && SCALAR_FLOAT_MODE_P (mode))
3224 REAL_VALUE_TYPE d;
3225 REAL_VALUE_FROM_CONST_DOUBLE (d, op1);
3227 if (REAL_VALUES_EQUAL (d, dconst2))
3229 op0 = force_reg (GET_MODE (op0), op0);
3230 return expand_binop (mode, add_optab, op0, op0,
3231 target, unsignedp, OPTAB_LIB_WIDEN);
3235 /* This used to use umul_optab if unsigned, but for non-widening multiply
3236 there is no difference between signed and unsigned. */
3237 op0 = expand_binop (mode,
3238 ! unsignedp
3239 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT)
3240 ? smulv_optab : smul_optab,
3241 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
3242 gcc_assert (op0);
3243 return op0;
3246 /* Return the smallest n such that 2**n >= X. */
3249 ceil_log2 (unsigned HOST_WIDE_INT x)
3251 return floor_log2 (x - 1) + 1;
3254 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
3255 replace division by D, and put the least significant N bits of the result
3256 in *MULTIPLIER_PTR and return the most significant bit.
3258 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
3259 needed precision is in PRECISION (should be <= N).
3261 PRECISION should be as small as possible so this function can choose
3262 multiplier more freely.
3264 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
3265 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
3267 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
3268 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
3270 static
3271 unsigned HOST_WIDE_INT
3272 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
3273 rtx *multiplier_ptr, int *post_shift_ptr, int *lgup_ptr)
3275 HOST_WIDE_INT mhigh_hi, mlow_hi;
3276 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo;
3277 int lgup, post_shift;
3278 int pow, pow2;
3279 unsigned HOST_WIDE_INT nl, dummy1;
3280 HOST_WIDE_INT nh, dummy2;
3282 /* lgup = ceil(log2(divisor)); */
3283 lgup = ceil_log2 (d);
3285 gcc_assert (lgup <= n);
3287 pow = n + lgup;
3288 pow2 = n + lgup - precision;
3290 /* We could handle this with some effort, but this case is much
3291 better handled directly with a scc insn, so rely on caller using
3292 that. */
3293 gcc_assert (pow != 2 * HOST_BITS_PER_WIDE_INT);
3295 /* mlow = 2^(N + lgup)/d */
3296 if (pow >= HOST_BITS_PER_WIDE_INT)
3298 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT);
3299 nl = 0;
3301 else
3303 nh = 0;
3304 nl = (unsigned HOST_WIDE_INT) 1 << pow;
3306 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
3307 &mlow_lo, &mlow_hi, &dummy1, &dummy2);
3309 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */
3310 if (pow2 >= HOST_BITS_PER_WIDE_INT)
3311 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT);
3312 else
3313 nl |= (unsigned HOST_WIDE_INT) 1 << pow2;
3314 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0,
3315 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2);
3317 gcc_assert (!mhigh_hi || nh - d < d);
3318 gcc_assert (mhigh_hi <= 1 && mlow_hi <= 1);
3319 /* Assert that mlow < mhigh. */
3320 gcc_assert (mlow_hi < mhigh_hi
3321 || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo));
3323 /* If precision == N, then mlow, mhigh exceed 2^N
3324 (but they do not exceed 2^(N+1)). */
3326 /* Reduce to lowest terms. */
3327 for (post_shift = lgup; post_shift > 0; post_shift--)
3329 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1);
3330 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1);
3331 if (ml_lo >= mh_lo)
3332 break;
3334 mlow_hi = 0;
3335 mlow_lo = ml_lo;
3336 mhigh_hi = 0;
3337 mhigh_lo = mh_lo;
3340 *post_shift_ptr = post_shift;
3341 *lgup_ptr = lgup;
3342 if (n < HOST_BITS_PER_WIDE_INT)
3344 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
3345 *multiplier_ptr = GEN_INT (mhigh_lo & mask);
3346 return mhigh_lo >= mask;
3348 else
3350 *multiplier_ptr = GEN_INT (mhigh_lo);
3351 return mhigh_hi;
3355 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
3356 congruent to 1 (mod 2**N). */
3358 static unsigned HOST_WIDE_INT
3359 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
3361 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
3363 /* The algorithm notes that the choice y = x satisfies
3364 x*y == 1 mod 2^3, since x is assumed odd.
3365 Each iteration doubles the number of bits of significance in y. */
3367 unsigned HOST_WIDE_INT mask;
3368 unsigned HOST_WIDE_INT y = x;
3369 int nbit = 3;
3371 mask = (n == HOST_BITS_PER_WIDE_INT
3372 ? ~(unsigned HOST_WIDE_INT) 0
3373 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
3375 while (nbit < n)
3377 y = y * (2 - x*y) & mask; /* Modulo 2^N */
3378 nbit *= 2;
3380 return y;
3383 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
3384 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
3385 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
3386 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
3387 become signed.
3389 The result is put in TARGET if that is convenient.
3391 MODE is the mode of operation. */
3394 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
3395 rtx op1, rtx target, int unsignedp)
3397 rtx tem;
3398 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
3400 tem = expand_shift (RSHIFT_EXPR, mode, op0,
3401 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1),
3402 NULL_RTX, 0);
3403 tem = expand_and (mode, tem, op1, NULL_RTX);
3404 adj_operand
3405 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3406 adj_operand);
3408 tem = expand_shift (RSHIFT_EXPR, mode, op1,
3409 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1),
3410 NULL_RTX, 0);
3411 tem = expand_and (mode, tem, op0, NULL_RTX);
3412 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3413 target);
3415 return target;
3418 /* Subroutine of expand_mult_highpart. Return the MODE high part of OP. */
3420 static rtx
3421 extract_high_half (enum machine_mode mode, rtx op)
3423 enum machine_mode wider_mode;
3425 if (mode == word_mode)
3426 return gen_highpart (mode, op);
3428 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3430 wider_mode = GET_MODE_WIDER_MODE (mode);
3431 op = expand_shift (RSHIFT_EXPR, wider_mode, op,
3432 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode)), 0, 1);
3433 return convert_modes (mode, wider_mode, op, 0);
3436 /* Like expand_mult_highpart, but only consider using a multiplication
3437 optab. OP1 is an rtx for the constant operand. */
3439 static rtx
3440 expand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1,
3441 rtx target, int unsignedp, int max_cost)
3443 rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
3444 enum machine_mode wider_mode;
3445 optab moptab;
3446 rtx tem;
3447 int size;
3448 bool speed = optimize_insn_for_speed_p ();
3450 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3452 wider_mode = GET_MODE_WIDER_MODE (mode);
3453 size = GET_MODE_BITSIZE (mode);
3455 /* Firstly, try using a multiplication insn that only generates the needed
3456 high part of the product, and in the sign flavor of unsignedp. */
3457 if (mul_highpart_cost[speed][mode] < max_cost)
3459 moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
3460 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3461 unsignedp, OPTAB_DIRECT);
3462 if (tem)
3463 return tem;
3466 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
3467 Need to adjust the result after the multiplication. */
3468 if (size - 1 < BITS_PER_WORD
3469 && (mul_highpart_cost[speed][mode] + 2 * shift_cost[speed][mode][size-1]
3470 + 4 * add_cost[speed][mode] < max_cost))
3472 moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
3473 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3474 unsignedp, OPTAB_DIRECT);
3475 if (tem)
3476 /* We used the wrong signedness. Adjust the result. */
3477 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3478 tem, unsignedp);
3481 /* Try widening multiplication. */
3482 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
3483 if (optab_handler (moptab, wider_mode)->insn_code != CODE_FOR_nothing
3484 && mul_widen_cost[speed][wider_mode] < max_cost)
3486 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
3487 unsignedp, OPTAB_WIDEN);
3488 if (tem)
3489 return extract_high_half (mode, tem);
3492 /* Try widening the mode and perform a non-widening multiplication. */
3493 if (optab_handler (smul_optab, wider_mode)->insn_code != CODE_FOR_nothing
3494 && size - 1 < BITS_PER_WORD
3495 && mul_cost[speed][wider_mode] + shift_cost[speed][mode][size-1] < max_cost)
3497 rtx insns, wop0, wop1;
3499 /* We need to widen the operands, for example to ensure the
3500 constant multiplier is correctly sign or zero extended.
3501 Use a sequence to clean-up any instructions emitted by
3502 the conversions if things don't work out. */
3503 start_sequence ();
3504 wop0 = convert_modes (wider_mode, mode, op0, unsignedp);
3505 wop1 = convert_modes (wider_mode, mode, op1, unsignedp);
3506 tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0,
3507 unsignedp, OPTAB_WIDEN);
3508 insns = get_insns ();
3509 end_sequence ();
3511 if (tem)
3513 emit_insn (insns);
3514 return extract_high_half (mode, tem);
3518 /* Try widening multiplication of opposite signedness, and adjust. */
3519 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
3520 if (optab_handler (moptab, wider_mode)->insn_code != CODE_FOR_nothing
3521 && size - 1 < BITS_PER_WORD
3522 && (mul_widen_cost[speed][wider_mode] + 2 * shift_cost[speed][mode][size-1]
3523 + 4 * add_cost[speed][mode] < max_cost))
3525 tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3526 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3527 if (tem != 0)
3529 tem = extract_high_half (mode, tem);
3530 /* We used the wrong signedness. Adjust the result. */
3531 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3532 target, unsignedp);
3536 return 0;
3539 /* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant),
3540 putting the high half of the result in TARGET if that is convenient,
3541 and return where the result is. If the operation can not be performed,
3542 0 is returned.
3544 MODE is the mode of operation and result.
3546 UNSIGNEDP nonzero means unsigned multiply.
3548 MAX_COST is the total allowed cost for the expanded RTL. */
3550 static rtx
3551 expand_mult_highpart (enum machine_mode mode, rtx op0, rtx op1,
3552 rtx target, int unsignedp, int max_cost)
3554 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
3555 unsigned HOST_WIDE_INT cnst1;
3556 int extra_cost;
3557 bool sign_adjust = false;
3558 enum mult_variant variant;
3559 struct algorithm alg;
3560 rtx tem;
3561 bool speed = optimize_insn_for_speed_p ();
3563 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3564 /* We can't support modes wider than HOST_BITS_PER_INT. */
3565 gcc_assert (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT);
3567 cnst1 = INTVAL (op1) & GET_MODE_MASK (mode);
3569 /* We can't optimize modes wider than BITS_PER_WORD.
3570 ??? We might be able to perform double-word arithmetic if
3571 mode == word_mode, however all the cost calculations in
3572 synth_mult etc. assume single-word operations. */
3573 if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3574 return expand_mult_highpart_optab (mode, op0, op1, target,
3575 unsignedp, max_cost);
3577 extra_cost = shift_cost[speed][mode][GET_MODE_BITSIZE (mode) - 1];
3579 /* Check whether we try to multiply by a negative constant. */
3580 if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3582 sign_adjust = true;
3583 extra_cost += add_cost[speed][mode];
3586 /* See whether shift/add multiplication is cheap enough. */
3587 if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3588 max_cost - extra_cost))
3590 /* See whether the specialized multiplication optabs are
3591 cheaper than the shift/add version. */
3592 tem = expand_mult_highpart_optab (mode, op0, op1, target, unsignedp,
3593 alg.cost.cost + extra_cost);
3594 if (tem)
3595 return tem;
3597 tem = convert_to_mode (wider_mode, op0, unsignedp);
3598 tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3599 tem = extract_high_half (mode, tem);
3601 /* Adjust result for signedness. */
3602 if (sign_adjust)
3603 tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3605 return tem;
3607 return expand_mult_highpart_optab (mode, op0, op1, target,
3608 unsignedp, max_cost);
3612 /* Expand signed modulus of OP0 by a power of two D in mode MODE. */
3614 static rtx
3615 expand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3617 unsigned HOST_WIDE_INT masklow, maskhigh;
3618 rtx result, temp, shift, label;
3619 int logd;
3621 logd = floor_log2 (d);
3622 result = gen_reg_rtx (mode);
3624 /* Avoid conditional branches when they're expensive. */
3625 if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2
3626 && optimize_insn_for_speed_p ())
3628 rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3629 mode, 0, -1);
3630 if (signmask)
3632 signmask = force_reg (mode, signmask);
3633 masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3634 shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd);
3636 /* Use the rtx_cost of a LSHIFTRT instruction to determine
3637 which instruction sequence to use. If logical right shifts
3638 are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3639 use a LSHIFTRT, 1 ADD, 1 SUB and an AND. */
3641 temp = gen_rtx_LSHIFTRT (mode, result, shift);
3642 if (optab_handler (lshr_optab, mode)->insn_code == CODE_FOR_nothing
3643 || rtx_cost (temp, SET, optimize_insn_for_speed_p ()) > COSTS_N_INSNS (2))
3645 temp = expand_binop (mode, xor_optab, op0, signmask,
3646 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3647 temp = expand_binop (mode, sub_optab, temp, signmask,
3648 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3649 temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow),
3650 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3651 temp = expand_binop (mode, xor_optab, temp, signmask,
3652 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3653 temp = expand_binop (mode, sub_optab, temp, signmask,
3654 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3656 else
3658 signmask = expand_binop (mode, lshr_optab, signmask, shift,
3659 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3660 signmask = force_reg (mode, signmask);
3662 temp = expand_binop (mode, add_optab, op0, signmask,
3663 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3664 temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow),
3665 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3666 temp = expand_binop (mode, sub_optab, temp, signmask,
3667 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3669 return temp;
3673 /* Mask contains the mode's signbit and the significant bits of the
3674 modulus. By including the signbit in the operation, many targets
3675 can avoid an explicit compare operation in the following comparison
3676 against zero. */
3678 masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3679 if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
3681 masklow |= (HOST_WIDE_INT) -1 << (GET_MODE_BITSIZE (mode) - 1);
3682 maskhigh = -1;
3684 else
3685 maskhigh = (HOST_WIDE_INT) -1
3686 << (GET_MODE_BITSIZE (mode) - HOST_BITS_PER_WIDE_INT - 1);
3688 temp = expand_binop (mode, and_optab, op0,
3689 immed_double_const (masklow, maskhigh, mode),
3690 result, 1, OPTAB_LIB_WIDEN);
3691 if (temp != result)
3692 emit_move_insn (result, temp);
3694 label = gen_label_rtx ();
3695 do_cmp_and_jump (result, const0_rtx, GE, mode, label);
3697 temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
3698 0, OPTAB_LIB_WIDEN);
3699 masklow = (HOST_WIDE_INT) -1 << logd;
3700 maskhigh = -1;
3701 temp = expand_binop (mode, ior_optab, temp,
3702 immed_double_const (masklow, maskhigh, mode),
3703 result, 1, OPTAB_LIB_WIDEN);
3704 temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
3705 0, OPTAB_LIB_WIDEN);
3706 if (temp != result)
3707 emit_move_insn (result, temp);
3708 emit_label (label);
3709 return result;
3712 /* Expand signed division of OP0 by a power of two D in mode MODE.
3713 This routine is only called for positive values of D. */
3715 static rtx
3716 expand_sdiv_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3718 rtx temp, label;
3719 tree shift;
3720 int logd;
3722 logd = floor_log2 (d);
3723 shift = build_int_cst (NULL_TREE, logd);
3725 if (d == 2
3726 && BRANCH_COST (optimize_insn_for_speed_p (),
3727 false) >= 1)
3729 temp = gen_reg_rtx (mode);
3730 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1);
3731 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3732 0, OPTAB_LIB_WIDEN);
3733 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3736 #ifdef HAVE_conditional_move
3737 if (BRANCH_COST (optimize_insn_for_speed_p (), false)
3738 >= 2)
3740 rtx temp2;
3742 /* ??? emit_conditional_move forces a stack adjustment via
3743 compare_from_rtx so, if the sequence is discarded, it will
3744 be lost. Do it now instead. */
3745 do_pending_stack_adjust ();
3747 start_sequence ();
3748 temp2 = copy_to_mode_reg (mode, op0);
3749 temp = expand_binop (mode, add_optab, temp2, GEN_INT (d-1),
3750 NULL_RTX, 0, OPTAB_LIB_WIDEN);
3751 temp = force_reg (mode, temp);
3753 /* Construct "temp2 = (temp2 < 0) ? temp : temp2". */
3754 temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx,
3755 mode, temp, temp2, mode, 0);
3756 if (temp2)
3758 rtx seq = get_insns ();
3759 end_sequence ();
3760 emit_insn (seq);
3761 return expand_shift (RSHIFT_EXPR, mode, temp2, shift, NULL_RTX, 0);
3763 end_sequence ();
3765 #endif
3767 if (BRANCH_COST (optimize_insn_for_speed_p (),
3768 false) >= 2)
3770 int ushift = GET_MODE_BITSIZE (mode) - logd;
3772 temp = gen_reg_rtx (mode);
3773 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1);
3774 if (shift_cost[optimize_insn_for_speed_p ()][mode][ushift] > COSTS_N_INSNS (1))
3775 temp = expand_binop (mode, and_optab, temp, GEN_INT (d - 1),
3776 NULL_RTX, 0, OPTAB_LIB_WIDEN);
3777 else
3778 temp = expand_shift (RSHIFT_EXPR, mode, temp,
3779 build_int_cst (NULL_TREE, ushift),
3780 NULL_RTX, 1);
3781 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3782 0, OPTAB_LIB_WIDEN);
3783 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3786 label = gen_label_rtx ();
3787 temp = copy_to_mode_reg (mode, op0);
3788 do_cmp_and_jump (temp, const0_rtx, GE, mode, label);
3789 expand_inc (temp, GEN_INT (d - 1));
3790 emit_label (label);
3791 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0);
3794 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3795 if that is convenient, and returning where the result is.
3796 You may request either the quotient or the remainder as the result;
3797 specify REM_FLAG nonzero to get the remainder.
3799 CODE is the expression code for which kind of division this is;
3800 it controls how rounding is done. MODE is the machine mode to use.
3801 UNSIGNEDP nonzero means do unsigned division. */
3803 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3804 and then correct it by or'ing in missing high bits
3805 if result of ANDI is nonzero.
3806 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3807 This could optimize to a bfexts instruction.
3808 But C doesn't use these operations, so their optimizations are
3809 left for later. */
3810 /* ??? For modulo, we don't actually need the highpart of the first product,
3811 the low part will do nicely. And for small divisors, the second multiply
3812 can also be a low-part only multiply or even be completely left out.
3813 E.g. to calculate the remainder of a division by 3 with a 32 bit
3814 multiply, multiply with 0x55555556 and extract the upper two bits;
3815 the result is exact for inputs up to 0x1fffffff.
3816 The input range can be reduced by using cross-sum rules.
3817 For odd divisors >= 3, the following table gives right shift counts
3818 so that if a number is shifted by an integer multiple of the given
3819 amount, the remainder stays the same:
3820 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3821 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3822 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3823 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3824 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3826 Cross-sum rules for even numbers can be derived by leaving as many bits
3827 to the right alone as the divisor has zeros to the right.
3828 E.g. if x is an unsigned 32 bit number:
3829 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3833 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3834 rtx op0, rtx op1, rtx target, int unsignedp)
3836 enum machine_mode compute_mode;
3837 rtx tquotient;
3838 rtx quotient = 0, remainder = 0;
3839 rtx last;
3840 int size;
3841 rtx insn, set;
3842 optab optab1, optab2;
3843 int op1_is_constant, op1_is_pow2 = 0;
3844 int max_cost, extra_cost;
3845 static HOST_WIDE_INT last_div_const = 0;
3846 static HOST_WIDE_INT ext_op1;
3847 bool speed = optimize_insn_for_speed_p ();
3849 op1_is_constant = CONST_INT_P (op1);
3850 if (op1_is_constant)
3852 ext_op1 = INTVAL (op1);
3853 if (unsignedp)
3854 ext_op1 &= GET_MODE_MASK (mode);
3855 op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3856 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3860 This is the structure of expand_divmod:
3862 First comes code to fix up the operands so we can perform the operations
3863 correctly and efficiently.
3865 Second comes a switch statement with code specific for each rounding mode.
3866 For some special operands this code emits all RTL for the desired
3867 operation, for other cases, it generates only a quotient and stores it in
3868 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
3869 to indicate that it has not done anything.
3871 Last comes code that finishes the operation. If QUOTIENT is set and
3872 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
3873 QUOTIENT is not set, it is computed using trunc rounding.
3875 We try to generate special code for division and remainder when OP1 is a
3876 constant. If |OP1| = 2**n we can use shifts and some other fast
3877 operations. For other values of OP1, we compute a carefully selected
3878 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3879 by m.
3881 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3882 half of the product. Different strategies for generating the product are
3883 implemented in expand_mult_highpart.
3885 If what we actually want is the remainder, we generate that by another
3886 by-constant multiplication and a subtraction. */
3888 /* We shouldn't be called with OP1 == const1_rtx, but some of the
3889 code below will malfunction if we are, so check here and handle
3890 the special case if so. */
3891 if (op1 == const1_rtx)
3892 return rem_flag ? const0_rtx : op0;
3894 /* When dividing by -1, we could get an overflow.
3895 negv_optab can handle overflows. */
3896 if (! unsignedp && op1 == constm1_rtx)
3898 if (rem_flag)
3899 return const0_rtx;
3900 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT
3901 ? negv_optab : neg_optab, op0, target, 0);
3904 if (target
3905 /* Don't use the function value register as a target
3906 since we have to read it as well as write it,
3907 and function-inlining gets confused by this. */
3908 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3909 /* Don't clobber an operand while doing a multi-step calculation. */
3910 || ((rem_flag || op1_is_constant)
3911 && (reg_mentioned_p (target, op0)
3912 || (MEM_P (op0) && MEM_P (target))))
3913 || reg_mentioned_p (target, op1)
3914 || (MEM_P (op1) && MEM_P (target))))
3915 target = 0;
3917 /* Get the mode in which to perform this computation. Normally it will
3918 be MODE, but sometimes we can't do the desired operation in MODE.
3919 If so, pick a wider mode in which we can do the operation. Convert
3920 to that mode at the start to avoid repeated conversions.
3922 First see what operations we need. These depend on the expression
3923 we are evaluating. (We assume that divxx3 insns exist under the
3924 same conditions that modxx3 insns and that these insns don't normally
3925 fail. If these assumptions are not correct, we may generate less
3926 efficient code in some cases.)
3928 Then see if we find a mode in which we can open-code that operation
3929 (either a division, modulus, or shift). Finally, check for the smallest
3930 mode for which we can do the operation with a library call. */
3932 /* We might want to refine this now that we have division-by-constant
3933 optimization. Since expand_mult_highpart tries so many variants, it is
3934 not straightforward to generalize this. Maybe we should make an array
3935 of possible modes in init_expmed? Save this for GCC 2.7. */
3937 optab1 = ((op1_is_pow2 && op1 != const0_rtx)
3938 ? (unsignedp ? lshr_optab : ashr_optab)
3939 : (unsignedp ? udiv_optab : sdiv_optab));
3940 optab2 = ((op1_is_pow2 && op1 != const0_rtx)
3941 ? optab1
3942 : (unsignedp ? udivmod_optab : sdivmod_optab));
3944 for (compute_mode = mode; compute_mode != VOIDmode;
3945 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3946 if (optab_handler (optab1, compute_mode)->insn_code != CODE_FOR_nothing
3947 || optab_handler (optab2, compute_mode)->insn_code != CODE_FOR_nothing)
3948 break;
3950 if (compute_mode == VOIDmode)
3951 for (compute_mode = mode; compute_mode != VOIDmode;
3952 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
3953 if (optab_libfunc (optab1, compute_mode)
3954 || optab_libfunc (optab2, compute_mode))
3955 break;
3957 /* If we still couldn't find a mode, use MODE, but expand_binop will
3958 probably die. */
3959 if (compute_mode == VOIDmode)
3960 compute_mode = mode;
3962 if (target && GET_MODE (target) == compute_mode)
3963 tquotient = target;
3964 else
3965 tquotient = gen_reg_rtx (compute_mode);
3967 size = GET_MODE_BITSIZE (compute_mode);
3968 #if 0
3969 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
3970 (mode), and thereby get better code when OP1 is a constant. Do that
3971 later. It will require going over all usages of SIZE below. */
3972 size = GET_MODE_BITSIZE (mode);
3973 #endif
3975 /* Only deduct something for a REM if the last divide done was
3976 for a different constant. Then set the constant of the last
3977 divide. */
3978 max_cost = unsignedp ? udiv_cost[speed][compute_mode] : sdiv_cost[speed][compute_mode];
3979 if (rem_flag && ! (last_div_const != 0 && op1_is_constant
3980 && INTVAL (op1) == last_div_const))
3981 max_cost -= mul_cost[speed][compute_mode] + add_cost[speed][compute_mode];
3983 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
3985 /* Now convert to the best mode to use. */
3986 if (compute_mode != mode)
3988 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
3989 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
3991 /* convert_modes may have placed op1 into a register, so we
3992 must recompute the following. */
3993 op1_is_constant = CONST_INT_P (op1);
3994 op1_is_pow2 = (op1_is_constant
3995 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
3996 || (! unsignedp
3997 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ;
4000 /* If one of the operands is a volatile MEM, copy it into a register. */
4002 if (MEM_P (op0) && MEM_VOLATILE_P (op0))
4003 op0 = force_reg (compute_mode, op0);
4004 if (MEM_P (op1) && MEM_VOLATILE_P (op1))
4005 op1 = force_reg (compute_mode, op1);
4007 /* If we need the remainder or if OP1 is constant, we need to
4008 put OP0 in a register in case it has any queued subexpressions. */
4009 if (rem_flag || op1_is_constant)
4010 op0 = force_reg (compute_mode, op0);
4012 last = get_last_insn ();
4014 /* Promote floor rounding to trunc rounding for unsigned operations. */
4015 if (unsignedp)
4017 if (code == FLOOR_DIV_EXPR)
4018 code = TRUNC_DIV_EXPR;
4019 if (code == FLOOR_MOD_EXPR)
4020 code = TRUNC_MOD_EXPR;
4021 if (code == EXACT_DIV_EXPR && op1_is_pow2)
4022 code = TRUNC_DIV_EXPR;
4025 if (op1 != const0_rtx)
4026 switch (code)
4028 case TRUNC_MOD_EXPR:
4029 case TRUNC_DIV_EXPR:
4030 if (op1_is_constant)
4032 if (unsignedp)
4034 unsigned HOST_WIDE_INT mh;
4035 int pre_shift, post_shift;
4036 int dummy;
4037 rtx ml;
4038 unsigned HOST_WIDE_INT d = (INTVAL (op1)
4039 & GET_MODE_MASK (compute_mode));
4041 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4043 pre_shift = floor_log2 (d);
4044 if (rem_flag)
4046 remainder
4047 = expand_binop (compute_mode, and_optab, op0,
4048 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
4049 remainder, 1,
4050 OPTAB_LIB_WIDEN);
4051 if (remainder)
4052 return gen_lowpart (mode, remainder);
4054 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4055 build_int_cst (NULL_TREE,
4056 pre_shift),
4057 tquotient, 1);
4059 else if (size <= HOST_BITS_PER_WIDE_INT)
4061 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
4063 /* Most significant bit of divisor is set; emit an scc
4064 insn. */
4065 quotient = emit_store_flag_force (tquotient, GEU, op0, op1,
4066 compute_mode, 1, 1);
4068 else
4070 /* Find a suitable multiplier and right shift count
4071 instead of multiplying with D. */
4073 mh = choose_multiplier (d, size, size,
4074 &ml, &post_shift, &dummy);
4076 /* If the suggested multiplier is more than SIZE bits,
4077 we can do better for even divisors, using an
4078 initial right shift. */
4079 if (mh != 0 && (d & 1) == 0)
4081 pre_shift = floor_log2 (d & -d);
4082 mh = choose_multiplier (d >> pre_shift, size,
4083 size - pre_shift,
4084 &ml, &post_shift, &dummy);
4085 gcc_assert (!mh);
4087 else
4088 pre_shift = 0;
4090 if (mh != 0)
4092 rtx t1, t2, t3, t4;
4094 if (post_shift - 1 >= BITS_PER_WORD)
4095 goto fail1;
4097 extra_cost
4098 = (shift_cost[speed][compute_mode][post_shift - 1]
4099 + shift_cost[speed][compute_mode][1]
4100 + 2 * add_cost[speed][compute_mode]);
4101 t1 = expand_mult_highpart (compute_mode, op0, ml,
4102 NULL_RTX, 1,
4103 max_cost - extra_cost);
4104 if (t1 == 0)
4105 goto fail1;
4106 t2 = force_operand (gen_rtx_MINUS (compute_mode,
4107 op0, t1),
4108 NULL_RTX);
4109 t3 = expand_shift
4110 (RSHIFT_EXPR, compute_mode, t2,
4111 build_int_cst (NULL_TREE, 1),
4112 NULL_RTX,1);
4113 t4 = force_operand (gen_rtx_PLUS (compute_mode,
4114 t1, t3),
4115 NULL_RTX);
4116 quotient = expand_shift
4117 (RSHIFT_EXPR, compute_mode, t4,
4118 build_int_cst (NULL_TREE, post_shift - 1),
4119 tquotient, 1);
4121 else
4123 rtx t1, t2;
4125 if (pre_shift >= BITS_PER_WORD
4126 || post_shift >= BITS_PER_WORD)
4127 goto fail1;
4129 t1 = expand_shift
4130 (RSHIFT_EXPR, compute_mode, op0,
4131 build_int_cst (NULL_TREE, pre_shift),
4132 NULL_RTX, 1);
4133 extra_cost
4134 = (shift_cost[speed][compute_mode][pre_shift]
4135 + shift_cost[speed][compute_mode][post_shift]);
4136 t2 = expand_mult_highpart (compute_mode, t1, ml,
4137 NULL_RTX, 1,
4138 max_cost - extra_cost);
4139 if (t2 == 0)
4140 goto fail1;
4141 quotient = expand_shift
4142 (RSHIFT_EXPR, compute_mode, t2,
4143 build_int_cst (NULL_TREE, post_shift),
4144 tquotient, 1);
4148 else /* Too wide mode to use tricky code */
4149 break;
4151 insn = get_last_insn ();
4152 if (insn != last
4153 && (set = single_set (insn)) != 0
4154 && SET_DEST (set) == quotient)
4155 set_unique_reg_note (insn,
4156 REG_EQUAL,
4157 gen_rtx_UDIV (compute_mode, op0, op1));
4159 else /* TRUNC_DIV, signed */
4161 unsigned HOST_WIDE_INT ml;
4162 int lgup, post_shift;
4163 rtx mlr;
4164 HOST_WIDE_INT d = INTVAL (op1);
4165 unsigned HOST_WIDE_INT abs_d;
4167 /* Since d might be INT_MIN, we have to cast to
4168 unsigned HOST_WIDE_INT before negating to avoid
4169 undefined signed overflow. */
4170 abs_d = (d >= 0
4171 ? (unsigned HOST_WIDE_INT) d
4172 : - (unsigned HOST_WIDE_INT) d);
4174 /* n rem d = n rem -d */
4175 if (rem_flag && d < 0)
4177 d = abs_d;
4178 op1 = gen_int_mode (abs_d, compute_mode);
4181 if (d == 1)
4182 quotient = op0;
4183 else if (d == -1)
4184 quotient = expand_unop (compute_mode, neg_optab, op0,
4185 tquotient, 0);
4186 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
4188 /* This case is not handled correctly below. */
4189 quotient = emit_store_flag (tquotient, EQ, op0, op1,
4190 compute_mode, 1, 1);
4191 if (quotient == 0)
4192 goto fail1;
4194 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
4195 && (rem_flag ? smod_pow2_cheap[speed][compute_mode]
4196 : sdiv_pow2_cheap[speed][compute_mode])
4197 /* We assume that cheap metric is true if the
4198 optab has an expander for this mode. */
4199 && ((optab_handler ((rem_flag ? smod_optab
4200 : sdiv_optab),
4201 compute_mode)->insn_code
4202 != CODE_FOR_nothing)
4203 || (optab_handler(sdivmod_optab,
4204 compute_mode)
4205 ->insn_code != CODE_FOR_nothing)))
4207 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
4209 if (rem_flag)
4211 remainder = expand_smod_pow2 (compute_mode, op0, d);
4212 if (remainder)
4213 return gen_lowpart (mode, remainder);
4216 if (sdiv_pow2_cheap[speed][compute_mode]
4217 && ((optab_handler (sdiv_optab, compute_mode)->insn_code
4218 != CODE_FOR_nothing)
4219 || (optab_handler (sdivmod_optab, compute_mode)->insn_code
4220 != CODE_FOR_nothing)))
4221 quotient = expand_divmod (0, TRUNC_DIV_EXPR,
4222 compute_mode, op0,
4223 gen_int_mode (abs_d,
4224 compute_mode),
4225 NULL_RTX, 0);
4226 else
4227 quotient = expand_sdiv_pow2 (compute_mode, op0, abs_d);
4229 /* We have computed OP0 / abs(OP1). If OP1 is negative,
4230 negate the quotient. */
4231 if (d < 0)
4233 insn = get_last_insn ();
4234 if (insn != last
4235 && (set = single_set (insn)) != 0
4236 && SET_DEST (set) == quotient
4237 && abs_d < ((unsigned HOST_WIDE_INT) 1
4238 << (HOST_BITS_PER_WIDE_INT - 1)))
4239 set_unique_reg_note (insn,
4240 REG_EQUAL,
4241 gen_rtx_DIV (compute_mode,
4242 op0,
4243 GEN_INT
4244 (trunc_int_for_mode
4245 (abs_d,
4246 compute_mode))));
4248 quotient = expand_unop (compute_mode, neg_optab,
4249 quotient, quotient, 0);
4252 else if (size <= HOST_BITS_PER_WIDE_INT)
4254 choose_multiplier (abs_d, size, size - 1,
4255 &mlr, &post_shift, &lgup);
4256 ml = (unsigned HOST_WIDE_INT) INTVAL (mlr);
4257 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
4259 rtx t1, t2, t3;
4261 if (post_shift >= BITS_PER_WORD
4262 || size - 1 >= BITS_PER_WORD)
4263 goto fail1;
4265 extra_cost = (shift_cost[speed][compute_mode][post_shift]
4266 + shift_cost[speed][compute_mode][size - 1]
4267 + add_cost[speed][compute_mode]);
4268 t1 = expand_mult_highpart (compute_mode, op0, mlr,
4269 NULL_RTX, 0,
4270 max_cost - extra_cost);
4271 if (t1 == 0)
4272 goto fail1;
4273 t2 = expand_shift
4274 (RSHIFT_EXPR, compute_mode, t1,
4275 build_int_cst (NULL_TREE, post_shift),
4276 NULL_RTX, 0);
4277 t3 = expand_shift
4278 (RSHIFT_EXPR, compute_mode, op0,
4279 build_int_cst (NULL_TREE, size - 1),
4280 NULL_RTX, 0);
4281 if (d < 0)
4282 quotient
4283 = force_operand (gen_rtx_MINUS (compute_mode,
4284 t3, t2),
4285 tquotient);
4286 else
4287 quotient
4288 = force_operand (gen_rtx_MINUS (compute_mode,
4289 t2, t3),
4290 tquotient);
4292 else
4294 rtx t1, t2, t3, t4;
4296 if (post_shift >= BITS_PER_WORD
4297 || size - 1 >= BITS_PER_WORD)
4298 goto fail1;
4300 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
4301 mlr = gen_int_mode (ml, compute_mode);
4302 extra_cost = (shift_cost[speed][compute_mode][post_shift]
4303 + shift_cost[speed][compute_mode][size - 1]
4304 + 2 * add_cost[speed][compute_mode]);
4305 t1 = expand_mult_highpart (compute_mode, op0, mlr,
4306 NULL_RTX, 0,
4307 max_cost - extra_cost);
4308 if (t1 == 0)
4309 goto fail1;
4310 t2 = force_operand (gen_rtx_PLUS (compute_mode,
4311 t1, op0),
4312 NULL_RTX);
4313 t3 = expand_shift
4314 (RSHIFT_EXPR, compute_mode, t2,
4315 build_int_cst (NULL_TREE, post_shift),
4316 NULL_RTX, 0);
4317 t4 = expand_shift
4318 (RSHIFT_EXPR, compute_mode, op0,
4319 build_int_cst (NULL_TREE, size - 1),
4320 NULL_RTX, 0);
4321 if (d < 0)
4322 quotient
4323 = force_operand (gen_rtx_MINUS (compute_mode,
4324 t4, t3),
4325 tquotient);
4326 else
4327 quotient
4328 = force_operand (gen_rtx_MINUS (compute_mode,
4329 t3, t4),
4330 tquotient);
4333 else /* Too wide mode to use tricky code */
4334 break;
4336 insn = get_last_insn ();
4337 if (insn != last
4338 && (set = single_set (insn)) != 0
4339 && SET_DEST (set) == quotient)
4340 set_unique_reg_note (insn,
4341 REG_EQUAL,
4342 gen_rtx_DIV (compute_mode, op0, op1));
4344 break;
4346 fail1:
4347 delete_insns_since (last);
4348 break;
4350 case FLOOR_DIV_EXPR:
4351 case FLOOR_MOD_EXPR:
4352 /* We will come here only for signed operations. */
4353 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4355 unsigned HOST_WIDE_INT mh;
4356 int pre_shift, lgup, post_shift;
4357 HOST_WIDE_INT d = INTVAL (op1);
4358 rtx ml;
4360 if (d > 0)
4362 /* We could just as easily deal with negative constants here,
4363 but it does not seem worth the trouble for GCC 2.6. */
4364 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4366 pre_shift = floor_log2 (d);
4367 if (rem_flag)
4369 remainder = expand_binop (compute_mode, and_optab, op0,
4370 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1),
4371 remainder, 0, OPTAB_LIB_WIDEN);
4372 if (remainder)
4373 return gen_lowpart (mode, remainder);
4375 quotient = expand_shift
4376 (RSHIFT_EXPR, compute_mode, op0,
4377 build_int_cst (NULL_TREE, pre_shift),
4378 tquotient, 0);
4380 else
4382 rtx t1, t2, t3, t4;
4384 mh = choose_multiplier (d, size, size - 1,
4385 &ml, &post_shift, &lgup);
4386 gcc_assert (!mh);
4388 if (post_shift < BITS_PER_WORD
4389 && size - 1 < BITS_PER_WORD)
4391 t1 = expand_shift
4392 (RSHIFT_EXPR, compute_mode, op0,
4393 build_int_cst (NULL_TREE, size - 1),
4394 NULL_RTX, 0);
4395 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
4396 NULL_RTX, 0, OPTAB_WIDEN);
4397 extra_cost = (shift_cost[speed][compute_mode][post_shift]
4398 + shift_cost[speed][compute_mode][size - 1]
4399 + 2 * add_cost[speed][compute_mode]);
4400 t3 = expand_mult_highpart (compute_mode, t2, ml,
4401 NULL_RTX, 1,
4402 max_cost - extra_cost);
4403 if (t3 != 0)
4405 t4 = expand_shift
4406 (RSHIFT_EXPR, compute_mode, t3,
4407 build_int_cst (NULL_TREE, post_shift),
4408 NULL_RTX, 1);
4409 quotient = expand_binop (compute_mode, xor_optab,
4410 t4, t1, tquotient, 0,
4411 OPTAB_WIDEN);
4416 else
4418 rtx nsign, t1, t2, t3, t4;
4419 t1 = force_operand (gen_rtx_PLUS (compute_mode,
4420 op0, constm1_rtx), NULL_RTX);
4421 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
4422 0, OPTAB_WIDEN);
4423 nsign = expand_shift
4424 (RSHIFT_EXPR, compute_mode, t2,
4425 build_int_cst (NULL_TREE, size - 1),
4426 NULL_RTX, 0);
4427 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
4428 NULL_RTX);
4429 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
4430 NULL_RTX, 0);
4431 if (t4)
4433 rtx t5;
4434 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
4435 NULL_RTX, 0);
4436 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4437 t4, t5),
4438 tquotient);
4443 if (quotient != 0)
4444 break;
4445 delete_insns_since (last);
4447 /* Try using an instruction that produces both the quotient and
4448 remainder, using truncation. We can easily compensate the quotient
4449 or remainder to get floor rounding, once we have the remainder.
4450 Notice that we compute also the final remainder value here,
4451 and return the result right away. */
4452 if (target == 0 || GET_MODE (target) != compute_mode)
4453 target = gen_reg_rtx (compute_mode);
4455 if (rem_flag)
4457 remainder
4458 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4459 quotient = gen_reg_rtx (compute_mode);
4461 else
4463 quotient
4464 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4465 remainder = gen_reg_rtx (compute_mode);
4468 if (expand_twoval_binop (sdivmod_optab, op0, op1,
4469 quotient, remainder, 0))
4471 /* This could be computed with a branch-less sequence.
4472 Save that for later. */
4473 rtx tem;
4474 rtx label = gen_label_rtx ();
4475 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
4476 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4477 NULL_RTX, 0, OPTAB_WIDEN);
4478 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
4479 expand_dec (quotient, const1_rtx);
4480 expand_inc (remainder, op1);
4481 emit_label (label);
4482 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4485 /* No luck with division elimination or divmod. Have to do it
4486 by conditionally adjusting op0 *and* the result. */
4488 rtx label1, label2, label3, label4, label5;
4489 rtx adjusted_op0;
4490 rtx tem;
4492 quotient = gen_reg_rtx (compute_mode);
4493 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4494 label1 = gen_label_rtx ();
4495 label2 = gen_label_rtx ();
4496 label3 = gen_label_rtx ();
4497 label4 = gen_label_rtx ();
4498 label5 = gen_label_rtx ();
4499 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4500 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
4501 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4502 quotient, 0, OPTAB_LIB_WIDEN);
4503 if (tem != quotient)
4504 emit_move_insn (quotient, tem);
4505 emit_jump_insn (gen_jump (label5));
4506 emit_barrier ();
4507 emit_label (label1);
4508 expand_inc (adjusted_op0, const1_rtx);
4509 emit_jump_insn (gen_jump (label4));
4510 emit_barrier ();
4511 emit_label (label2);
4512 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
4513 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4514 quotient, 0, OPTAB_LIB_WIDEN);
4515 if (tem != quotient)
4516 emit_move_insn (quotient, tem);
4517 emit_jump_insn (gen_jump (label5));
4518 emit_barrier ();
4519 emit_label (label3);
4520 expand_dec (adjusted_op0, const1_rtx);
4521 emit_label (label4);
4522 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4523 quotient, 0, OPTAB_LIB_WIDEN);
4524 if (tem != quotient)
4525 emit_move_insn (quotient, tem);
4526 expand_dec (quotient, const1_rtx);
4527 emit_label (label5);
4529 break;
4531 case CEIL_DIV_EXPR:
4532 case CEIL_MOD_EXPR:
4533 if (unsignedp)
4535 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
4537 rtx t1, t2, t3;
4538 unsigned HOST_WIDE_INT d = INTVAL (op1);
4539 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4540 build_int_cst (NULL_TREE, floor_log2 (d)),
4541 tquotient, 1);
4542 t2 = expand_binop (compute_mode, and_optab, op0,
4543 GEN_INT (d - 1),
4544 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4545 t3 = gen_reg_rtx (compute_mode);
4546 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4547 compute_mode, 1, 1);
4548 if (t3 == 0)
4550 rtx lab;
4551 lab = gen_label_rtx ();
4552 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4553 expand_inc (t1, const1_rtx);
4554 emit_label (lab);
4555 quotient = t1;
4557 else
4558 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4559 t1, t3),
4560 tquotient);
4561 break;
4564 /* Try using an instruction that produces both the quotient and
4565 remainder, using truncation. We can easily compensate the
4566 quotient or remainder to get ceiling rounding, once we have the
4567 remainder. Notice that we compute also the final remainder
4568 value here, and return the result right away. */
4569 if (target == 0 || GET_MODE (target) != compute_mode)
4570 target = gen_reg_rtx (compute_mode);
4572 if (rem_flag)
4574 remainder = (REG_P (target)
4575 ? target : gen_reg_rtx (compute_mode));
4576 quotient = gen_reg_rtx (compute_mode);
4578 else
4580 quotient = (REG_P (target)
4581 ? target : gen_reg_rtx (compute_mode));
4582 remainder = gen_reg_rtx (compute_mode);
4585 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
4586 remainder, 1))
4588 /* This could be computed with a branch-less sequence.
4589 Save that for later. */
4590 rtx label = gen_label_rtx ();
4591 do_cmp_and_jump (remainder, const0_rtx, EQ,
4592 compute_mode, label);
4593 expand_inc (quotient, const1_rtx);
4594 expand_dec (remainder, op1);
4595 emit_label (label);
4596 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4599 /* No luck with division elimination or divmod. Have to do it
4600 by conditionally adjusting op0 *and* the result. */
4602 rtx label1, label2;
4603 rtx adjusted_op0, tem;
4605 quotient = gen_reg_rtx (compute_mode);
4606 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4607 label1 = gen_label_rtx ();
4608 label2 = gen_label_rtx ();
4609 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
4610 compute_mode, label1);
4611 emit_move_insn (quotient, const0_rtx);
4612 emit_jump_insn (gen_jump (label2));
4613 emit_barrier ();
4614 emit_label (label1);
4615 expand_dec (adjusted_op0, const1_rtx);
4616 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
4617 quotient, 1, OPTAB_LIB_WIDEN);
4618 if (tem != quotient)
4619 emit_move_insn (quotient, tem);
4620 expand_inc (quotient, const1_rtx);
4621 emit_label (label2);
4624 else /* signed */
4626 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4627 && INTVAL (op1) >= 0)
4629 /* This is extremely similar to the code for the unsigned case
4630 above. For 2.7 we should merge these variants, but for
4631 2.6.1 I don't want to touch the code for unsigned since that
4632 get used in C. The signed case will only be used by other
4633 languages (Ada). */
4635 rtx t1, t2, t3;
4636 unsigned HOST_WIDE_INT d = INTVAL (op1);
4637 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4638 build_int_cst (NULL_TREE, floor_log2 (d)),
4639 tquotient, 0);
4640 t2 = expand_binop (compute_mode, and_optab, op0,
4641 GEN_INT (d - 1),
4642 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4643 t3 = gen_reg_rtx (compute_mode);
4644 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4645 compute_mode, 1, 1);
4646 if (t3 == 0)
4648 rtx lab;
4649 lab = gen_label_rtx ();
4650 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4651 expand_inc (t1, const1_rtx);
4652 emit_label (lab);
4653 quotient = t1;
4655 else
4656 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4657 t1, t3),
4658 tquotient);
4659 break;
4662 /* Try using an instruction that produces both the quotient and
4663 remainder, using truncation. We can easily compensate the
4664 quotient or remainder to get ceiling rounding, once we have the
4665 remainder. Notice that we compute also the final remainder
4666 value here, and return the result right away. */
4667 if (target == 0 || GET_MODE (target) != compute_mode)
4668 target = gen_reg_rtx (compute_mode);
4669 if (rem_flag)
4671 remainder= (REG_P (target)
4672 ? target : gen_reg_rtx (compute_mode));
4673 quotient = gen_reg_rtx (compute_mode);
4675 else
4677 quotient = (REG_P (target)
4678 ? target : gen_reg_rtx (compute_mode));
4679 remainder = gen_reg_rtx (compute_mode);
4682 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
4683 remainder, 0))
4685 /* This could be computed with a branch-less sequence.
4686 Save that for later. */
4687 rtx tem;
4688 rtx label = gen_label_rtx ();
4689 do_cmp_and_jump (remainder, const0_rtx, EQ,
4690 compute_mode, label);
4691 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4692 NULL_RTX, 0, OPTAB_WIDEN);
4693 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
4694 expand_inc (quotient, const1_rtx);
4695 expand_dec (remainder, op1);
4696 emit_label (label);
4697 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4700 /* No luck with division elimination or divmod. Have to do it
4701 by conditionally adjusting op0 *and* the result. */
4703 rtx label1, label2, label3, label4, label5;
4704 rtx adjusted_op0;
4705 rtx tem;
4707 quotient = gen_reg_rtx (compute_mode);
4708 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4709 label1 = gen_label_rtx ();
4710 label2 = gen_label_rtx ();
4711 label3 = gen_label_rtx ();
4712 label4 = gen_label_rtx ();
4713 label5 = gen_label_rtx ();
4714 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4715 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
4716 compute_mode, label1);
4717 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4718 quotient, 0, OPTAB_LIB_WIDEN);
4719 if (tem != quotient)
4720 emit_move_insn (quotient, tem);
4721 emit_jump_insn (gen_jump (label5));
4722 emit_barrier ();
4723 emit_label (label1);
4724 expand_dec (adjusted_op0, const1_rtx);
4725 emit_jump_insn (gen_jump (label4));
4726 emit_barrier ();
4727 emit_label (label2);
4728 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
4729 compute_mode, label3);
4730 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4731 quotient, 0, OPTAB_LIB_WIDEN);
4732 if (tem != quotient)
4733 emit_move_insn (quotient, tem);
4734 emit_jump_insn (gen_jump (label5));
4735 emit_barrier ();
4736 emit_label (label3);
4737 expand_inc (adjusted_op0, const1_rtx);
4738 emit_label (label4);
4739 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4740 quotient, 0, OPTAB_LIB_WIDEN);
4741 if (tem != quotient)
4742 emit_move_insn (quotient, tem);
4743 expand_inc (quotient, const1_rtx);
4744 emit_label (label5);
4747 break;
4749 case EXACT_DIV_EXPR:
4750 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4752 HOST_WIDE_INT d = INTVAL (op1);
4753 unsigned HOST_WIDE_INT ml;
4754 int pre_shift;
4755 rtx t1;
4757 pre_shift = floor_log2 (d & -d);
4758 ml = invert_mod2n (d >> pre_shift, size);
4759 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4760 build_int_cst (NULL_TREE, pre_shift),
4761 NULL_RTX, unsignedp);
4762 quotient = expand_mult (compute_mode, t1,
4763 gen_int_mode (ml, compute_mode),
4764 NULL_RTX, 1);
4766 insn = get_last_insn ();
4767 set_unique_reg_note (insn,
4768 REG_EQUAL,
4769 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
4770 compute_mode,
4771 op0, op1));
4773 break;
4775 case ROUND_DIV_EXPR:
4776 case ROUND_MOD_EXPR:
4777 if (unsignedp)
4779 rtx tem;
4780 rtx label;
4781 label = gen_label_rtx ();
4782 quotient = gen_reg_rtx (compute_mode);
4783 remainder = gen_reg_rtx (compute_mode);
4784 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
4786 rtx tem;
4787 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
4788 quotient, 1, OPTAB_LIB_WIDEN);
4789 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
4790 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4791 remainder, 1, OPTAB_LIB_WIDEN);
4793 tem = plus_constant (op1, -1);
4794 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4795 build_int_cst (NULL_TREE, 1),
4796 NULL_RTX, 1);
4797 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
4798 expand_inc (quotient, const1_rtx);
4799 expand_dec (remainder, op1);
4800 emit_label (label);
4802 else
4804 rtx abs_rem, abs_op1, tem, mask;
4805 rtx label;
4806 label = gen_label_rtx ();
4807 quotient = gen_reg_rtx (compute_mode);
4808 remainder = gen_reg_rtx (compute_mode);
4809 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
4811 rtx tem;
4812 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
4813 quotient, 0, OPTAB_LIB_WIDEN);
4814 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
4815 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4816 remainder, 0, OPTAB_LIB_WIDEN);
4818 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
4819 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
4820 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
4821 build_int_cst (NULL_TREE, 1),
4822 NULL_RTX, 1);
4823 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
4824 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4825 NULL_RTX, 0, OPTAB_WIDEN);
4826 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4827 build_int_cst (NULL_TREE, size - 1),
4828 NULL_RTX, 0);
4829 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
4830 NULL_RTX, 0, OPTAB_WIDEN);
4831 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4832 NULL_RTX, 0, OPTAB_WIDEN);
4833 expand_inc (quotient, tem);
4834 tem = expand_binop (compute_mode, xor_optab, mask, op1,
4835 NULL_RTX, 0, OPTAB_WIDEN);
4836 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4837 NULL_RTX, 0, OPTAB_WIDEN);
4838 expand_dec (remainder, tem);
4839 emit_label (label);
4841 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4843 default:
4844 gcc_unreachable ();
4847 if (quotient == 0)
4849 if (target && GET_MODE (target) != compute_mode)
4850 target = 0;
4852 if (rem_flag)
4854 /* Try to produce the remainder without producing the quotient.
4855 If we seem to have a divmod pattern that does not require widening,
4856 don't try widening here. We should really have a WIDEN argument
4857 to expand_twoval_binop, since what we'd really like to do here is
4858 1) try a mod insn in compute_mode
4859 2) try a divmod insn in compute_mode
4860 3) try a div insn in compute_mode and multiply-subtract to get
4861 remainder
4862 4) try the same things with widening allowed. */
4863 remainder
4864 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4865 op0, op1, target,
4866 unsignedp,
4867 ((optab_handler (optab2, compute_mode)->insn_code
4868 != CODE_FOR_nothing)
4869 ? OPTAB_DIRECT : OPTAB_WIDEN));
4870 if (remainder == 0)
4872 /* No luck there. Can we do remainder and divide at once
4873 without a library call? */
4874 remainder = gen_reg_rtx (compute_mode);
4875 if (! expand_twoval_binop ((unsignedp
4876 ? udivmod_optab
4877 : sdivmod_optab),
4878 op0, op1,
4879 NULL_RTX, remainder, unsignedp))
4880 remainder = 0;
4883 if (remainder)
4884 return gen_lowpart (mode, remainder);
4887 /* Produce the quotient. Try a quotient insn, but not a library call.
4888 If we have a divmod in this mode, use it in preference to widening
4889 the div (for this test we assume it will not fail). Note that optab2
4890 is set to the one of the two optabs that the call below will use. */
4891 quotient
4892 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
4893 op0, op1, rem_flag ? NULL_RTX : target,
4894 unsignedp,
4895 ((optab_handler (optab2, compute_mode)->insn_code
4896 != CODE_FOR_nothing)
4897 ? OPTAB_DIRECT : OPTAB_WIDEN));
4899 if (quotient == 0)
4901 /* No luck there. Try a quotient-and-remainder insn,
4902 keeping the quotient alone. */
4903 quotient = gen_reg_rtx (compute_mode);
4904 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
4905 op0, op1,
4906 quotient, NULL_RTX, unsignedp))
4908 quotient = 0;
4909 if (! rem_flag)
4910 /* Still no luck. If we are not computing the remainder,
4911 use a library call for the quotient. */
4912 quotient = sign_expand_binop (compute_mode,
4913 udiv_optab, sdiv_optab,
4914 op0, op1, target,
4915 unsignedp, OPTAB_LIB_WIDEN);
4920 if (rem_flag)
4922 if (target && GET_MODE (target) != compute_mode)
4923 target = 0;
4925 if (quotient == 0)
4927 /* No divide instruction either. Use library for remainder. */
4928 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4929 op0, op1, target,
4930 unsignedp, OPTAB_LIB_WIDEN);
4931 /* No remainder function. Try a quotient-and-remainder
4932 function, keeping the remainder. */
4933 if (!remainder)
4935 remainder = gen_reg_rtx (compute_mode);
4936 if (!expand_twoval_binop_libfunc
4937 (unsignedp ? udivmod_optab : sdivmod_optab,
4938 op0, op1,
4939 NULL_RTX, remainder,
4940 unsignedp ? UMOD : MOD))
4941 remainder = NULL_RTX;
4944 else
4946 /* We divided. Now finish doing X - Y * (X / Y). */
4947 remainder = expand_mult (compute_mode, quotient, op1,
4948 NULL_RTX, unsignedp);
4949 remainder = expand_binop (compute_mode, sub_optab, op0,
4950 remainder, target, unsignedp,
4951 OPTAB_LIB_WIDEN);
4955 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4958 /* Return a tree node with data type TYPE, describing the value of X.
4959 Usually this is an VAR_DECL, if there is no obvious better choice.
4960 X may be an expression, however we only support those expressions
4961 generated by loop.c. */
4963 tree
4964 make_tree (tree type, rtx x)
4966 tree t;
4968 switch (GET_CODE (x))
4970 case CONST_INT:
4972 HOST_WIDE_INT hi = 0;
4974 if (INTVAL (x) < 0
4975 && !(TYPE_UNSIGNED (type)
4976 && (GET_MODE_BITSIZE (TYPE_MODE (type))
4977 < HOST_BITS_PER_WIDE_INT)))
4978 hi = -1;
4980 t = build_int_cst_wide (type, INTVAL (x), hi);
4982 return t;
4985 case CONST_DOUBLE:
4986 if (GET_MODE (x) == VOIDmode)
4987 t = build_int_cst_wide (type,
4988 CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
4989 else
4991 REAL_VALUE_TYPE d;
4993 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
4994 t = build_real (type, d);
4997 return t;
4999 case CONST_VECTOR:
5001 int units = CONST_VECTOR_NUNITS (x);
5002 tree itype = TREE_TYPE (type);
5003 tree t = NULL_TREE;
5004 int i;
5007 /* Build a tree with vector elements. */
5008 for (i = units - 1; i >= 0; --i)
5010 rtx elt = CONST_VECTOR_ELT (x, i);
5011 t = tree_cons (NULL_TREE, make_tree (itype, elt), t);
5014 return build_vector (type, t);
5017 case PLUS:
5018 return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5019 make_tree (type, XEXP (x, 1)));
5021 case MINUS:
5022 return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5023 make_tree (type, XEXP (x, 1)));
5025 case NEG:
5026 return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0)));
5028 case MULT:
5029 return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
5030 make_tree (type, XEXP (x, 1)));
5032 case ASHIFT:
5033 return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
5034 make_tree (type, XEXP (x, 1)));
5036 case LSHIFTRT:
5037 t = unsigned_type_for (type);
5038 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5039 make_tree (t, XEXP (x, 0)),
5040 make_tree (type, XEXP (x, 1))));
5042 case ASHIFTRT:
5043 t = signed_type_for (type);
5044 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5045 make_tree (t, XEXP (x, 0)),
5046 make_tree (type, XEXP (x, 1))));
5048 case DIV:
5049 if (TREE_CODE (type) != REAL_TYPE)
5050 t = signed_type_for (type);
5051 else
5052 t = type;
5054 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5055 make_tree (t, XEXP (x, 0)),
5056 make_tree (t, XEXP (x, 1))));
5057 case UDIV:
5058 t = unsigned_type_for (type);
5059 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5060 make_tree (t, XEXP (x, 0)),
5061 make_tree (t, XEXP (x, 1))));
5063 case SIGN_EXTEND:
5064 case ZERO_EXTEND:
5065 t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)),
5066 GET_CODE (x) == ZERO_EXTEND);
5067 return fold_convert (type, make_tree (t, XEXP (x, 0)));
5069 case CONST:
5070 return make_tree (type, XEXP (x, 0));
5072 case SYMBOL_REF:
5073 t = SYMBOL_REF_DECL (x);
5074 if (t)
5075 return fold_convert (type, build_fold_addr_expr (t));
5076 /* else fall through. */
5078 default:
5079 t = build_decl (RTL_LOCATION (x), VAR_DECL, NULL_TREE, type);
5081 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being
5082 ptr_mode. So convert. */
5083 if (POINTER_TYPE_P (type))
5084 x = convert_memory_address (TYPE_MODE (type), x);
5086 /* Note that we do *not* use SET_DECL_RTL here, because we do not
5087 want set_decl_rtl to go adjusting REG_ATTRS for this temporary. */
5088 t->decl_with_rtl.rtl = x;
5090 return t;
5094 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
5095 and returning TARGET.
5097 If TARGET is 0, a pseudo-register or constant is returned. */
5100 expand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target)
5102 rtx tem = 0;
5104 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
5105 tem = simplify_binary_operation (AND, mode, op0, op1);
5106 if (tem == 0)
5107 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
5109 if (target == 0)
5110 target = tem;
5111 else if (tem != target)
5112 emit_move_insn (target, tem);
5113 return target;
5116 /* Helper function for emit_store_flag. */
5117 static rtx
5118 emit_store_flag_1 (rtx target, rtx subtarget, enum machine_mode mode,
5119 int normalizep)
5121 rtx op0;
5122 enum machine_mode target_mode = GET_MODE (target);
5124 /* If we are converting to a wider mode, first convert to
5125 TARGET_MODE, then normalize. This produces better combining
5126 opportunities on machines that have a SIGN_EXTRACT when we are
5127 testing a single bit. This mostly benefits the 68k.
5129 If STORE_FLAG_VALUE does not have the sign bit set when
5130 interpreted in MODE, we can do this conversion as unsigned, which
5131 is usually more efficient. */
5132 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
5134 convert_move (target, subtarget,
5135 (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
5136 && 0 == (STORE_FLAG_VALUE
5137 & ((HOST_WIDE_INT) 1
5138 << (GET_MODE_BITSIZE (mode) -1))));
5139 op0 = target;
5140 mode = target_mode;
5142 else
5143 op0 = subtarget;
5145 /* If we want to keep subexpressions around, don't reuse our last
5146 target. */
5147 if (optimize)
5148 subtarget = 0;
5150 /* Now normalize to the proper value in MODE. Sometimes we don't
5151 have to do anything. */
5152 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
5154 /* STORE_FLAG_VALUE might be the most negative number, so write
5155 the comparison this way to avoid a compiler-time warning. */
5156 else if (- normalizep == STORE_FLAG_VALUE)
5157 op0 = expand_unop (mode, neg_optab, op0, subtarget, 0);
5159 /* We don't want to use STORE_FLAG_VALUE < 0 below since this makes
5160 it hard to use a value of just the sign bit due to ANSI integer
5161 constant typing rules. */
5162 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
5163 && (STORE_FLAG_VALUE
5164 & ((HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1))))
5165 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
5166 size_int (GET_MODE_BITSIZE (mode) - 1), subtarget,
5167 normalizep == 1);
5168 else
5170 gcc_assert (STORE_FLAG_VALUE & 1);
5172 op0 = expand_and (mode, op0, const1_rtx, subtarget);
5173 if (normalizep == -1)
5174 op0 = expand_unop (mode, neg_optab, op0, op0, 0);
5177 /* If we were converting to a smaller mode, do the conversion now. */
5178 if (target_mode != mode)
5180 convert_move (target, op0, 0);
5181 return target;
5183 else
5184 return op0;
5187 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
5188 and storing in TARGET. Normally return TARGET.
5189 Return 0 if that cannot be done.
5191 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
5192 it is VOIDmode, they cannot both be CONST_INT.
5194 UNSIGNEDP is for the case where we have to widen the operands
5195 to perform the operation. It says to use zero-extension.
5197 NORMALIZEP is 1 if we should convert the result to be either zero
5198 or one. Normalize is -1 if we should convert the result to be
5199 either zero or -1. If NORMALIZEP is zero, the result will be left
5200 "raw" out of the scc insn. */
5203 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
5204 enum machine_mode mode, int unsignedp, int normalizep)
5206 rtx subtarget;
5207 enum insn_code icode;
5208 enum machine_mode compare_mode;
5209 enum machine_mode target_mode = GET_MODE (target);
5210 enum mode_class mclass;
5211 rtx tem;
5212 rtx last;
5213 rtx pattern, comparison;
5215 if (unsignedp)
5216 code = unsigned_condition (code);
5218 /* If one operand is constant, make it the second one. Only do this
5219 if the other operand is not constant as well. */
5221 if (swap_commutative_operands_p (op0, op1))
5223 tem = op0;
5224 op0 = op1;
5225 op1 = tem;
5226 code = swap_condition (code);
5229 if (mode == VOIDmode)
5230 mode = GET_MODE (op0);
5232 /* For some comparisons with 1 and -1, we can convert this to
5233 comparisons with zero. This will often produce more opportunities for
5234 store-flag insns. */
5236 switch (code)
5238 case LT:
5239 if (op1 == const1_rtx)
5240 op1 = const0_rtx, code = LE;
5241 break;
5242 case LE:
5243 if (op1 == constm1_rtx)
5244 op1 = const0_rtx, code = LT;
5245 break;
5246 case GE:
5247 if (op1 == const1_rtx)
5248 op1 = const0_rtx, code = GT;
5249 break;
5250 case GT:
5251 if (op1 == constm1_rtx)
5252 op1 = const0_rtx, code = GE;
5253 break;
5254 case GEU:
5255 if (op1 == const1_rtx)
5256 op1 = const0_rtx, code = NE;
5257 break;
5258 case LTU:
5259 if (op1 == const1_rtx)
5260 op1 = const0_rtx, code = EQ;
5261 break;
5262 default:
5263 break;
5266 /* If we are comparing a double-word integer with zero or -1, we can
5267 convert the comparison into one involving a single word. */
5268 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
5269 && GET_MODE_CLASS (mode) == MODE_INT
5270 && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0)))
5272 if ((code == EQ || code == NE)
5273 && (op1 == const0_rtx || op1 == constm1_rtx))
5275 rtx op00, op01, op0both;
5277 /* Do a logical OR or AND of the two words and compare the
5278 result. */
5279 op00 = simplify_gen_subreg (word_mode, op0, mode, 0);
5280 op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD);
5281 op0both = expand_binop (word_mode,
5282 op1 == const0_rtx ? ior_optab : and_optab,
5283 op00, op01, NULL_RTX, unsignedp,
5284 OPTAB_DIRECT);
5286 if (op0both != 0)
5287 return emit_store_flag (target, code, op0both, op1, word_mode,
5288 unsignedp, normalizep);
5290 else if ((code == LT || code == GE) && op1 == const0_rtx)
5292 rtx op0h;
5294 /* If testing the sign bit, can just test on high word. */
5295 op0h = simplify_gen_subreg (word_mode, op0, mode,
5296 subreg_highpart_offset (word_mode,
5297 mode));
5298 return emit_store_flag (target, code, op0h, op1, word_mode,
5299 unsignedp, normalizep);
5303 /* If this is A < 0 or A >= 0, we can do this by taking the ones
5304 complement of A (for GE) and shifting the sign bit to the low bit. */
5305 if (op1 == const0_rtx && (code == LT || code == GE)
5306 && GET_MODE_CLASS (mode) == MODE_INT
5307 && (normalizep || STORE_FLAG_VALUE == 1
5308 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
5309 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
5310 == ((unsigned HOST_WIDE_INT) 1
5311 << (GET_MODE_BITSIZE (mode) - 1))))))
5313 subtarget = target;
5315 /* If the result is to be wider than OP0, it is best to convert it
5316 first. If it is to be narrower, it is *incorrect* to convert it
5317 first. */
5318 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
5320 op0 = convert_modes (target_mode, mode, op0, 0);
5321 mode = target_mode;
5324 if (target_mode != mode)
5325 subtarget = 0;
5327 if (code == GE)
5328 op0 = expand_unop (mode, one_cmpl_optab, op0,
5329 ((STORE_FLAG_VALUE == 1 || normalizep)
5330 ? 0 : subtarget), 0);
5332 if (STORE_FLAG_VALUE == 1 || normalizep)
5333 /* If we are supposed to produce a 0/1 value, we want to do
5334 a logical shift from the sign bit to the low-order bit; for
5335 a -1/0 value, we do an arithmetic shift. */
5336 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
5337 size_int (GET_MODE_BITSIZE (mode) - 1),
5338 subtarget, normalizep != -1);
5340 if (mode != target_mode)
5341 op0 = convert_modes (target_mode, mode, op0, 0);
5343 return op0;
5346 mclass = GET_MODE_CLASS (mode);
5347 for (compare_mode = mode; compare_mode != VOIDmode;
5348 compare_mode = GET_MODE_WIDER_MODE (compare_mode))
5350 enum machine_mode optab_mode = mclass == MODE_CC ? CCmode : compare_mode;
5351 icode = optab_handler (cstore_optab, optab_mode)->insn_code;
5352 if (icode != CODE_FOR_nothing)
5354 rtx x, y;
5355 enum machine_mode result_mode
5356 = insn_data[(int) icode].operand[0].mode;
5358 do_pending_stack_adjust ();
5359 last = get_last_insn ();
5361 x = prepare_operand (icode, op0, 2, mode, compare_mode, unsignedp);
5362 y = prepare_operand (icode, op1, 3, mode, compare_mode, unsignedp);
5363 comparison = gen_rtx_fmt_ee (code, result_mode, x, y);
5364 if (!x || !y
5365 || !insn_data[icode].operand[2].predicate
5366 (x, insn_data[icode].operand[2].mode)
5367 || !insn_data[icode].operand[3].predicate
5368 (y, insn_data[icode].operand[3].mode)
5369 || !insn_data[icode].operand[1].predicate (comparison, VOIDmode))
5371 delete_insns_since (last);
5372 continue;
5375 subtarget = target;
5376 if (optimize || !(insn_data[(int) icode].operand[0].predicate
5377 (subtarget, result_mode)))
5378 subtarget = gen_reg_rtx (result_mode);
5380 pattern = GEN_FCN (icode) (subtarget, comparison, x, y);
5382 if (pattern)
5384 emit_insn (pattern);
5385 return emit_store_flag_1 (target, subtarget, result_mode,
5386 normalizep);
5389 delete_insns_since (last);
5390 break;
5394 last = get_last_insn ();
5396 /* If optimizing, use different pseudo registers for each insn, instead
5397 of reusing the same pseudo. This leads to better CSE, but slows
5398 down the compiler, since there are more pseudos */
5399 subtarget = (!optimize
5400 && (target_mode == mode)) ? target : NULL_RTX;
5402 /* If we reached here, we can't do this with a scc insn. However, there
5403 are some comparisons that can be done directly. For example, if
5404 this is an equality comparison of integers, we can try to exclusive-or
5405 (or subtract) the two operands and use a recursive call to try the
5406 comparison with zero. Don't do any of these cases if branches are
5407 very cheap. */
5409 if (BRANCH_COST (optimize_insn_for_speed_p (),
5410 false) > 0
5411 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE)
5412 && op1 != const0_rtx)
5414 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
5415 OPTAB_WIDEN);
5417 if (tem == 0)
5418 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
5419 OPTAB_WIDEN);
5420 if (tem != 0)
5421 tem = emit_store_flag (target, code, tem, const0_rtx,
5422 mode, unsignedp, normalizep);
5423 if (tem == 0)
5424 delete_insns_since (last);
5425 return tem;
5428 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
5429 the constant zero. Reject all other comparisons at this point. Only
5430 do LE and GT if branches are expensive since they are expensive on
5431 2-operand machines. */
5433 if (BRANCH_COST (optimize_insn_for_speed_p (),
5434 false) == 0
5435 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx
5436 || (code != EQ && code != NE
5437 && (BRANCH_COST (optimize_insn_for_speed_p (),
5438 false) <= 1 || (code != LE && code != GT))))
5439 return 0;
5441 /* See what we need to return. We can only return a 1, -1, or the
5442 sign bit. */
5444 if (normalizep == 0)
5446 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
5447 normalizep = STORE_FLAG_VALUE;
5449 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT
5450 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode))
5451 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1)))
5453 else
5454 return 0;
5457 /* Try to put the result of the comparison in the sign bit. Assume we can't
5458 do the necessary operation below. */
5460 tem = 0;
5462 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
5463 the sign bit set. */
5465 if (code == LE)
5467 /* This is destructive, so SUBTARGET can't be OP0. */
5468 if (rtx_equal_p (subtarget, op0))
5469 subtarget = 0;
5471 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
5472 OPTAB_WIDEN);
5473 if (tem)
5474 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
5475 OPTAB_WIDEN);
5478 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
5479 number of bits in the mode of OP0, minus one. */
5481 if (code == GT)
5483 if (rtx_equal_p (subtarget, op0))
5484 subtarget = 0;
5486 tem = expand_shift (RSHIFT_EXPR, mode, op0,
5487 size_int (GET_MODE_BITSIZE (mode) - 1),
5488 subtarget, 0);
5489 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
5490 OPTAB_WIDEN);
5493 if (code == EQ || code == NE)
5495 /* For EQ or NE, one way to do the comparison is to apply an operation
5496 that converts the operand into a positive number if it is nonzero
5497 or zero if it was originally zero. Then, for EQ, we subtract 1 and
5498 for NE we negate. This puts the result in the sign bit. Then we
5499 normalize with a shift, if needed.
5501 Two operations that can do the above actions are ABS and FFS, so try
5502 them. If that doesn't work, and MODE is smaller than a full word,
5503 we can use zero-extension to the wider mode (an unsigned conversion)
5504 as the operation. */
5506 /* Note that ABS doesn't yield a positive number for INT_MIN, but
5507 that is compensated by the subsequent overflow when subtracting
5508 one / negating. */
5510 if (optab_handler (abs_optab, mode)->insn_code != CODE_FOR_nothing)
5511 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
5512 else if (optab_handler (ffs_optab, mode)->insn_code != CODE_FOR_nothing)
5513 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
5514 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5516 tem = convert_modes (word_mode, mode, op0, 1);
5517 mode = word_mode;
5520 if (tem != 0)
5522 if (code == EQ)
5523 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
5524 0, OPTAB_WIDEN);
5525 else
5526 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
5529 /* If we couldn't do it that way, for NE we can "or" the two's complement
5530 of the value with itself. For EQ, we take the one's complement of
5531 that "or", which is an extra insn, so we only handle EQ if branches
5532 are expensive. */
5534 if (tem == 0
5535 && (code == NE
5536 || BRANCH_COST (optimize_insn_for_speed_p (),
5537 false) > 1))
5539 if (rtx_equal_p (subtarget, op0))
5540 subtarget = 0;
5542 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
5543 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
5544 OPTAB_WIDEN);
5546 if (tem && code == EQ)
5547 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
5551 if (tem && normalizep)
5552 tem = expand_shift (RSHIFT_EXPR, mode, tem,
5553 size_int (GET_MODE_BITSIZE (mode) - 1),
5554 subtarget, normalizep == 1);
5556 if (tem)
5558 if (GET_MODE (tem) != target_mode)
5560 convert_move (target, tem, 0);
5561 tem = target;
5563 else if (!subtarget)
5565 emit_move_insn (target, tem);
5566 tem = target;
5569 else
5570 delete_insns_since (last);
5572 return tem;
5575 /* Like emit_store_flag, but always succeeds. */
5578 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
5579 enum machine_mode mode, int unsignedp, int normalizep)
5581 rtx tem, label;
5583 /* First see if emit_store_flag can do the job. */
5584 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
5585 if (tem != 0)
5586 return tem;
5588 if (normalizep == 0)
5589 normalizep = 1;
5591 /* If this failed, we have to do this with set/compare/jump/set code. */
5593 if (!REG_P (target)
5594 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
5595 target = gen_reg_rtx (GET_MODE (target));
5597 emit_move_insn (target, const1_rtx);
5598 label = gen_label_rtx ();
5599 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
5600 NULL_RTX, label);
5602 emit_move_insn (target, const0_rtx);
5603 emit_label (label);
5605 return target;
5608 /* Perform possibly multi-word comparison and conditional jump to LABEL
5609 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE. This is
5610 now a thin wrapper around do_compare_rtx_and_jump. */
5612 static void
5613 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
5614 rtx label)
5616 int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU);
5617 do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode,
5618 NULL_RTX, NULL_RTX, label);