2014-02-21 Janus Weil <janus@gcc.gnu.org>
[official-gcc.git] / gcc / expmed.c
blob7c1c979f7741bf9a280855c1cc51796b805f11de
1 /* Medium-level subroutines: convert bit-field store and extract
2 and shifts, multiplies and divides to rtl instructions.
3 Copyright (C) 1987-2014 Free Software Foundation, Inc.
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
10 version.
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15 for more details.
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "diagnostic-core.h"
27 #include "rtl.h"
28 #include "tree.h"
29 #include "stor-layout.h"
30 #include "tm_p.h"
31 #include "flags.h"
32 #include "insn-config.h"
33 #include "expr.h"
34 #include "optabs.h"
35 #include "recog.h"
36 #include "langhooks.h"
37 #include "df.h"
38 #include "target.h"
39 #include "expmed.h"
41 struct target_expmed default_target_expmed;
42 #if SWITCHABLE_TARGET
43 struct target_expmed *this_target_expmed = &default_target_expmed;
44 #endif
46 static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT,
47 unsigned HOST_WIDE_INT,
48 unsigned HOST_WIDE_INT,
49 unsigned HOST_WIDE_INT,
50 rtx);
51 static void store_fixed_bit_field_1 (rtx, unsigned HOST_WIDE_INT,
52 unsigned HOST_WIDE_INT,
53 rtx);
54 static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT,
55 unsigned HOST_WIDE_INT,
56 unsigned HOST_WIDE_INT,
57 unsigned HOST_WIDE_INT,
58 rtx);
59 static rtx extract_fixed_bit_field (enum machine_mode, rtx,
60 unsigned HOST_WIDE_INT,
61 unsigned HOST_WIDE_INT, rtx, int);
62 static rtx extract_fixed_bit_field_1 (enum machine_mode, rtx,
63 unsigned HOST_WIDE_INT,
64 unsigned HOST_WIDE_INT, rtx, int);
65 static rtx mask_rtx (enum machine_mode, int, int, int);
66 static rtx lshift_value (enum machine_mode, unsigned HOST_WIDE_INT, int);
67 static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT,
68 unsigned HOST_WIDE_INT, int);
69 static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx);
70 static rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
71 static rtx expand_sdiv_pow2 (enum machine_mode, rtx, HOST_WIDE_INT);
73 /* Test whether a value is zero of a power of two. */
74 #define EXACT_POWER_OF_2_OR_ZERO_P(x) \
75 (((x) & ((x) - (unsigned HOST_WIDE_INT) 1)) == 0)
77 struct init_expmed_rtl
79 struct rtx_def reg;
80 struct rtx_def plus;
81 struct rtx_def neg;
82 struct rtx_def mult;
83 struct rtx_def sdiv;
84 struct rtx_def udiv;
85 struct rtx_def sdiv_32;
86 struct rtx_def smod_32;
87 struct rtx_def wide_mult;
88 struct rtx_def wide_lshr;
89 struct rtx_def wide_trunc;
90 struct rtx_def shift;
91 struct rtx_def shift_mult;
92 struct rtx_def shift_add;
93 struct rtx_def shift_sub0;
94 struct rtx_def shift_sub1;
95 struct rtx_def zext;
96 struct rtx_def trunc;
98 rtx pow2[MAX_BITS_PER_WORD];
99 rtx cint[MAX_BITS_PER_WORD];
102 static void
103 init_expmed_one_conv (struct init_expmed_rtl *all, enum machine_mode to_mode,
104 enum machine_mode from_mode, bool speed)
106 int to_size, from_size;
107 rtx which;
109 /* We're given no information about the true size of a partial integer,
110 only the size of the "full" integer it requires for storage. For
111 comparison purposes here, reduce the bit size by one in that case. */
112 to_size = (GET_MODE_BITSIZE (to_mode)
113 - (GET_MODE_CLASS (to_mode) == MODE_PARTIAL_INT));
114 from_size = (GET_MODE_BITSIZE (from_mode)
115 - (GET_MODE_CLASS (from_mode) == MODE_PARTIAL_INT));
117 /* Assume cost of zero-extend and sign-extend is the same. */
118 which = (to_size < from_size ? &all->trunc : &all->zext);
120 PUT_MODE (&all->reg, from_mode);
121 set_convert_cost (to_mode, from_mode, speed, set_src_cost (which, speed));
124 static void
125 init_expmed_one_mode (struct init_expmed_rtl *all,
126 enum machine_mode mode, int speed)
128 int m, n, mode_bitsize;
129 enum machine_mode mode_from;
131 mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
133 PUT_MODE (&all->reg, mode);
134 PUT_MODE (&all->plus, mode);
135 PUT_MODE (&all->neg, mode);
136 PUT_MODE (&all->mult, mode);
137 PUT_MODE (&all->sdiv, mode);
138 PUT_MODE (&all->udiv, mode);
139 PUT_MODE (&all->sdiv_32, mode);
140 PUT_MODE (&all->smod_32, mode);
141 PUT_MODE (&all->wide_trunc, mode);
142 PUT_MODE (&all->shift, mode);
143 PUT_MODE (&all->shift_mult, mode);
144 PUT_MODE (&all->shift_add, mode);
145 PUT_MODE (&all->shift_sub0, mode);
146 PUT_MODE (&all->shift_sub1, mode);
147 PUT_MODE (&all->zext, mode);
148 PUT_MODE (&all->trunc, mode);
150 set_add_cost (speed, mode, set_src_cost (&all->plus, speed));
151 set_neg_cost (speed, mode, set_src_cost (&all->neg, speed));
152 set_mul_cost (speed, mode, set_src_cost (&all->mult, speed));
153 set_sdiv_cost (speed, mode, set_src_cost (&all->sdiv, speed));
154 set_udiv_cost (speed, mode, set_src_cost (&all->udiv, speed));
156 set_sdiv_pow2_cheap (speed, mode, (set_src_cost (&all->sdiv_32, speed)
157 <= 2 * add_cost (speed, mode)));
158 set_smod_pow2_cheap (speed, mode, (set_src_cost (&all->smod_32, speed)
159 <= 4 * add_cost (speed, mode)));
161 set_shift_cost (speed, mode, 0, 0);
163 int cost = add_cost (speed, mode);
164 set_shiftadd_cost (speed, mode, 0, cost);
165 set_shiftsub0_cost (speed, mode, 0, cost);
166 set_shiftsub1_cost (speed, mode, 0, cost);
169 n = MIN (MAX_BITS_PER_WORD, mode_bitsize);
170 for (m = 1; m < n; m++)
172 XEXP (&all->shift, 1) = all->cint[m];
173 XEXP (&all->shift_mult, 1) = all->pow2[m];
175 set_shift_cost (speed, mode, m, set_src_cost (&all->shift, speed));
176 set_shiftadd_cost (speed, mode, m, set_src_cost (&all->shift_add, speed));
177 set_shiftsub0_cost (speed, mode, m, set_src_cost (&all->shift_sub0, speed));
178 set_shiftsub1_cost (speed, mode, m, set_src_cost (&all->shift_sub1, speed));
181 if (SCALAR_INT_MODE_P (mode))
183 for (mode_from = MIN_MODE_INT; mode_from <= MAX_MODE_INT;
184 mode_from = (enum machine_mode)(mode_from + 1))
185 init_expmed_one_conv (all, mode, mode_from, speed);
187 if (GET_MODE_CLASS (mode) == MODE_INT)
189 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
190 if (wider_mode != VOIDmode)
192 PUT_MODE (&all->zext, wider_mode);
193 PUT_MODE (&all->wide_mult, wider_mode);
194 PUT_MODE (&all->wide_lshr, wider_mode);
195 XEXP (&all->wide_lshr, 1) = GEN_INT (mode_bitsize);
197 set_mul_widen_cost (speed, wider_mode,
198 set_src_cost (&all->wide_mult, speed));
199 set_mul_highpart_cost (speed, mode,
200 set_src_cost (&all->wide_trunc, speed));
205 void
206 init_expmed (void)
208 struct init_expmed_rtl all;
209 enum machine_mode mode;
210 int m, speed;
212 memset (&all, 0, sizeof all);
213 for (m = 1; m < MAX_BITS_PER_WORD; m++)
215 all.pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m);
216 all.cint[m] = GEN_INT (m);
219 PUT_CODE (&all.reg, REG);
220 /* Avoid using hard regs in ways which may be unsupported. */
221 SET_REGNO (&all.reg, LAST_VIRTUAL_REGISTER + 1);
223 PUT_CODE (&all.plus, PLUS);
224 XEXP (&all.plus, 0) = &all.reg;
225 XEXP (&all.plus, 1) = &all.reg;
227 PUT_CODE (&all.neg, NEG);
228 XEXP (&all.neg, 0) = &all.reg;
230 PUT_CODE (&all.mult, MULT);
231 XEXP (&all.mult, 0) = &all.reg;
232 XEXP (&all.mult, 1) = &all.reg;
234 PUT_CODE (&all.sdiv, DIV);
235 XEXP (&all.sdiv, 0) = &all.reg;
236 XEXP (&all.sdiv, 1) = &all.reg;
238 PUT_CODE (&all.udiv, UDIV);
239 XEXP (&all.udiv, 0) = &all.reg;
240 XEXP (&all.udiv, 1) = &all.reg;
242 PUT_CODE (&all.sdiv_32, DIV);
243 XEXP (&all.sdiv_32, 0) = &all.reg;
244 XEXP (&all.sdiv_32, 1) = 32 < MAX_BITS_PER_WORD ? all.cint[32] : GEN_INT (32);
246 PUT_CODE (&all.smod_32, MOD);
247 XEXP (&all.smod_32, 0) = &all.reg;
248 XEXP (&all.smod_32, 1) = XEXP (&all.sdiv_32, 1);
250 PUT_CODE (&all.zext, ZERO_EXTEND);
251 XEXP (&all.zext, 0) = &all.reg;
253 PUT_CODE (&all.wide_mult, MULT);
254 XEXP (&all.wide_mult, 0) = &all.zext;
255 XEXP (&all.wide_mult, 1) = &all.zext;
257 PUT_CODE (&all.wide_lshr, LSHIFTRT);
258 XEXP (&all.wide_lshr, 0) = &all.wide_mult;
260 PUT_CODE (&all.wide_trunc, TRUNCATE);
261 XEXP (&all.wide_trunc, 0) = &all.wide_lshr;
263 PUT_CODE (&all.shift, ASHIFT);
264 XEXP (&all.shift, 0) = &all.reg;
266 PUT_CODE (&all.shift_mult, MULT);
267 XEXP (&all.shift_mult, 0) = &all.reg;
269 PUT_CODE (&all.shift_add, PLUS);
270 XEXP (&all.shift_add, 0) = &all.shift_mult;
271 XEXP (&all.shift_add, 1) = &all.reg;
273 PUT_CODE (&all.shift_sub0, MINUS);
274 XEXP (&all.shift_sub0, 0) = &all.shift_mult;
275 XEXP (&all.shift_sub0, 1) = &all.reg;
277 PUT_CODE (&all.shift_sub1, MINUS);
278 XEXP (&all.shift_sub1, 0) = &all.reg;
279 XEXP (&all.shift_sub1, 1) = &all.shift_mult;
281 PUT_CODE (&all.trunc, TRUNCATE);
282 XEXP (&all.trunc, 0) = &all.reg;
284 for (speed = 0; speed < 2; speed++)
286 crtl->maybe_hot_insn_p = speed;
287 set_zero_cost (speed, set_src_cost (const0_rtx, speed));
289 for (mode = MIN_MODE_INT; mode <= MAX_MODE_INT;
290 mode = (enum machine_mode)(mode + 1))
291 init_expmed_one_mode (&all, mode, speed);
293 if (MIN_MODE_PARTIAL_INT != VOIDmode)
294 for (mode = MIN_MODE_PARTIAL_INT; mode <= MAX_MODE_PARTIAL_INT;
295 mode = (enum machine_mode)(mode + 1))
296 init_expmed_one_mode (&all, mode, speed);
298 if (MIN_MODE_VECTOR_INT != VOIDmode)
299 for (mode = MIN_MODE_VECTOR_INT; mode <= MAX_MODE_VECTOR_INT;
300 mode = (enum machine_mode)(mode + 1))
301 init_expmed_one_mode (&all, mode, speed);
304 if (alg_hash_used_p ())
306 struct alg_hash_entry *p = alg_hash_entry_ptr (0);
307 memset (p, 0, sizeof (*p) * NUM_ALG_HASH_ENTRIES);
309 else
310 set_alg_hash_used_p (true);
311 default_rtl_profile ();
314 /* Return an rtx representing minus the value of X.
315 MODE is the intended mode of the result,
316 useful if X is a CONST_INT. */
319 negate_rtx (enum machine_mode mode, rtx x)
321 rtx result = simplify_unary_operation (NEG, mode, x, mode);
323 if (result == 0)
324 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0);
326 return result;
329 /* Adjust bitfield memory MEM so that it points to the first unit of mode
330 MODE that contains a bitfield of size BITSIZE at bit position BITNUM.
331 If MODE is BLKmode, return a reference to every byte in the bitfield.
332 Set *NEW_BITNUM to the bit position of the field within the new memory. */
334 static rtx
335 narrow_bit_field_mem (rtx mem, enum machine_mode mode,
336 unsigned HOST_WIDE_INT bitsize,
337 unsigned HOST_WIDE_INT bitnum,
338 unsigned HOST_WIDE_INT *new_bitnum)
340 if (mode == BLKmode)
342 *new_bitnum = bitnum % BITS_PER_UNIT;
343 HOST_WIDE_INT offset = bitnum / BITS_PER_UNIT;
344 HOST_WIDE_INT size = ((*new_bitnum + bitsize + BITS_PER_UNIT - 1)
345 / BITS_PER_UNIT);
346 return adjust_bitfield_address_size (mem, mode, offset, size);
348 else
350 unsigned int unit = GET_MODE_BITSIZE (mode);
351 *new_bitnum = bitnum % unit;
352 HOST_WIDE_INT offset = (bitnum - *new_bitnum) / BITS_PER_UNIT;
353 return adjust_bitfield_address (mem, mode, offset);
357 /* The caller wants to perform insertion or extraction PATTERN on a
358 bitfield of size BITSIZE at BITNUM bits into memory operand OP0.
359 BITREGION_START and BITREGION_END are as for store_bit_field
360 and FIELDMODE is the natural mode of the field.
362 Search for a mode that is compatible with the memory access
363 restrictions and (where applicable) with a register insertion or
364 extraction. Return the new memory on success, storing the adjusted
365 bit position in *NEW_BITNUM. Return null otherwise. */
367 static rtx
368 adjust_bit_field_mem_for_reg (enum extraction_pattern pattern,
369 rtx op0, HOST_WIDE_INT bitsize,
370 HOST_WIDE_INT bitnum,
371 unsigned HOST_WIDE_INT bitregion_start,
372 unsigned HOST_WIDE_INT bitregion_end,
373 enum machine_mode fieldmode,
374 unsigned HOST_WIDE_INT *new_bitnum)
376 bit_field_mode_iterator iter (bitsize, bitnum, bitregion_start,
377 bitregion_end, MEM_ALIGN (op0),
378 MEM_VOLATILE_P (op0));
379 enum machine_mode best_mode;
380 if (iter.next_mode (&best_mode))
382 /* We can use a memory in BEST_MODE. See whether this is true for
383 any wider modes. All other things being equal, we prefer to
384 use the widest mode possible because it tends to expose more
385 CSE opportunities. */
386 if (!iter.prefer_smaller_modes ())
388 /* Limit the search to the mode required by the corresponding
389 register insertion or extraction instruction, if any. */
390 enum machine_mode limit_mode = word_mode;
391 extraction_insn insn;
392 if (get_best_reg_extraction_insn (&insn, pattern,
393 GET_MODE_BITSIZE (best_mode),
394 fieldmode))
395 limit_mode = insn.field_mode;
397 enum machine_mode wider_mode;
398 while (iter.next_mode (&wider_mode)
399 && GET_MODE_SIZE (wider_mode) <= GET_MODE_SIZE (limit_mode))
400 best_mode = wider_mode;
402 return narrow_bit_field_mem (op0, best_mode, bitsize, bitnum,
403 new_bitnum);
405 return NULL_RTX;
408 /* Return true if a bitfield of size BITSIZE at bit number BITNUM within
409 a structure of mode STRUCT_MODE represents a lowpart subreg. The subreg
410 offset is then BITNUM / BITS_PER_UNIT. */
412 static bool
413 lowpart_bit_field_p (unsigned HOST_WIDE_INT bitnum,
414 unsigned HOST_WIDE_INT bitsize,
415 enum machine_mode struct_mode)
417 if (BYTES_BIG_ENDIAN)
418 return (bitnum % BITS_PER_UNIT == 0
419 && (bitnum + bitsize == GET_MODE_BITSIZE (struct_mode)
420 || (bitnum + bitsize) % BITS_PER_WORD == 0));
421 else
422 return bitnum % BITS_PER_WORD == 0;
425 /* Return true if -fstrict-volatile-bitfields applies to an access of OP0
426 containing BITSIZE bits starting at BITNUM, with field mode FIELDMODE.
427 Return false if the access would touch memory outside the range
428 BITREGION_START to BITREGION_END for conformance to the C++ memory
429 model. */
431 static bool
432 strict_volatile_bitfield_p (rtx op0, unsigned HOST_WIDE_INT bitsize,
433 unsigned HOST_WIDE_INT bitnum,
434 enum machine_mode fieldmode,
435 unsigned HOST_WIDE_INT bitregion_start,
436 unsigned HOST_WIDE_INT bitregion_end)
438 unsigned HOST_WIDE_INT modesize = GET_MODE_BITSIZE (fieldmode);
440 /* -fstrict-volatile-bitfields must be enabled and we must have a
441 volatile MEM. */
442 if (!MEM_P (op0)
443 || !MEM_VOLATILE_P (op0)
444 || flag_strict_volatile_bitfields <= 0)
445 return false;
447 /* Non-integral modes likely only happen with packed structures.
448 Punt. */
449 if (!SCALAR_INT_MODE_P (fieldmode))
450 return false;
452 /* The bit size must not be larger than the field mode, and
453 the field mode must not be larger than a word. */
454 if (bitsize > modesize || modesize > BITS_PER_WORD)
455 return false;
457 /* Check for cases of unaligned fields that must be split. */
458 if (bitnum % BITS_PER_UNIT + bitsize > modesize
459 || (STRICT_ALIGNMENT
460 && bitnum % GET_MODE_ALIGNMENT (fieldmode) + bitsize > modesize))
461 return false;
463 /* Check for cases where the C++ memory model applies. */
464 if (bitregion_end != 0
465 && (bitnum - bitnum % modesize < bitregion_start
466 || bitnum - bitnum % modesize + modesize > bitregion_end))
467 return false;
469 return true;
472 /* Return true if OP is a memory and if a bitfield of size BITSIZE at
473 bit number BITNUM can be treated as a simple value of mode MODE. */
475 static bool
476 simple_mem_bitfield_p (rtx op0, unsigned HOST_WIDE_INT bitsize,
477 unsigned HOST_WIDE_INT bitnum, enum machine_mode mode)
479 return (MEM_P (op0)
480 && bitnum % BITS_PER_UNIT == 0
481 && bitsize == GET_MODE_BITSIZE (mode)
482 && (!SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0))
483 || (bitnum % GET_MODE_ALIGNMENT (mode) == 0
484 && MEM_ALIGN (op0) >= GET_MODE_ALIGNMENT (mode))));
487 /* Try to use instruction INSV to store VALUE into a field of OP0.
488 BITSIZE and BITNUM are as for store_bit_field. */
490 static bool
491 store_bit_field_using_insv (const extraction_insn *insv, rtx op0,
492 unsigned HOST_WIDE_INT bitsize,
493 unsigned HOST_WIDE_INT bitnum,
494 rtx value)
496 struct expand_operand ops[4];
497 rtx value1;
498 rtx xop0 = op0;
499 rtx last = get_last_insn ();
500 bool copy_back = false;
502 enum machine_mode op_mode = insv->field_mode;
503 unsigned int unit = GET_MODE_BITSIZE (op_mode);
504 if (bitsize == 0 || bitsize > unit)
505 return false;
507 if (MEM_P (xop0))
508 /* Get a reference to the first byte of the field. */
509 xop0 = narrow_bit_field_mem (xop0, insv->struct_mode, bitsize, bitnum,
510 &bitnum);
511 else
513 /* Convert from counting within OP0 to counting in OP_MODE. */
514 if (BYTES_BIG_ENDIAN)
515 bitnum += unit - GET_MODE_BITSIZE (GET_MODE (op0));
517 /* If xop0 is a register, we need it in OP_MODE
518 to make it acceptable to the format of insv. */
519 if (GET_CODE (xop0) == SUBREG)
520 /* We can't just change the mode, because this might clobber op0,
521 and we will need the original value of op0 if insv fails. */
522 xop0 = gen_rtx_SUBREG (op_mode, SUBREG_REG (xop0), SUBREG_BYTE (xop0));
523 if (REG_P (xop0) && GET_MODE (xop0) != op_mode)
524 xop0 = gen_lowpart_SUBREG (op_mode, xop0);
527 /* If the destination is a paradoxical subreg such that we need a
528 truncate to the inner mode, perform the insertion on a temporary and
529 truncate the result to the original destination. Note that we can't
530 just truncate the paradoxical subreg as (truncate:N (subreg:W (reg:N
531 X) 0)) is (reg:N X). */
532 if (GET_CODE (xop0) == SUBREG
533 && REG_P (SUBREG_REG (xop0))
534 && !TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (SUBREG_REG (xop0)),
535 op_mode))
537 rtx tem = gen_reg_rtx (op_mode);
538 emit_move_insn (tem, xop0);
539 xop0 = tem;
540 copy_back = true;
543 /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
544 "backwards" from the size of the unit we are inserting into.
545 Otherwise, we count bits from the most significant on a
546 BYTES/BITS_BIG_ENDIAN machine. */
548 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
549 bitnum = unit - bitsize - bitnum;
551 /* Convert VALUE to op_mode (which insv insn wants) in VALUE1. */
552 value1 = value;
553 if (GET_MODE (value) != op_mode)
555 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize)
557 /* Optimization: Don't bother really extending VALUE
558 if it has all the bits we will actually use. However,
559 if we must narrow it, be sure we do it correctly. */
561 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (op_mode))
563 rtx tmp;
565 tmp = simplify_subreg (op_mode, value1, GET_MODE (value), 0);
566 if (! tmp)
567 tmp = simplify_gen_subreg (op_mode,
568 force_reg (GET_MODE (value),
569 value1),
570 GET_MODE (value), 0);
571 value1 = tmp;
573 else
574 value1 = gen_lowpart (op_mode, value1);
576 else if (CONST_INT_P (value))
577 value1 = gen_int_mode (INTVAL (value), op_mode);
578 else
579 /* Parse phase is supposed to make VALUE's data type
580 match that of the component reference, which is a type
581 at least as wide as the field; so VALUE should have
582 a mode that corresponds to that type. */
583 gcc_assert (CONSTANT_P (value));
586 create_fixed_operand (&ops[0], xop0);
587 create_integer_operand (&ops[1], bitsize);
588 create_integer_operand (&ops[2], bitnum);
589 create_input_operand (&ops[3], value1, op_mode);
590 if (maybe_expand_insn (insv->icode, 4, ops))
592 if (copy_back)
593 convert_move (op0, xop0, true);
594 return true;
596 delete_insns_since (last);
597 return false;
600 /* A subroutine of store_bit_field, with the same arguments. Return true
601 if the operation could be implemented.
603 If FALLBACK_P is true, fall back to store_fixed_bit_field if we have
604 no other way of implementing the operation. If FALLBACK_P is false,
605 return false instead. */
607 static bool
608 store_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
609 unsigned HOST_WIDE_INT bitnum,
610 unsigned HOST_WIDE_INT bitregion_start,
611 unsigned HOST_WIDE_INT bitregion_end,
612 enum machine_mode fieldmode,
613 rtx value, bool fallback_p)
615 rtx op0 = str_rtx;
616 rtx orig_value;
618 while (GET_CODE (op0) == SUBREG)
620 /* The following line once was done only if WORDS_BIG_ENDIAN,
621 but I think that is a mistake. WORDS_BIG_ENDIAN is
622 meaningful at a much higher level; when structures are copied
623 between memory and regs, the higher-numbered regs
624 always get higher addresses. */
625 int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0)));
626 int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0));
627 int byte_offset = 0;
629 /* Paradoxical subregs need special handling on big endian machines. */
630 if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size)
632 int difference = inner_mode_size - outer_mode_size;
634 if (WORDS_BIG_ENDIAN)
635 byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD;
636 if (BYTES_BIG_ENDIAN)
637 byte_offset += difference % UNITS_PER_WORD;
639 else
640 byte_offset = SUBREG_BYTE (op0);
642 bitnum += byte_offset * BITS_PER_UNIT;
643 op0 = SUBREG_REG (op0);
646 /* No action is needed if the target is a register and if the field
647 lies completely outside that register. This can occur if the source
648 code contains an out-of-bounds access to a small array. */
649 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
650 return true;
652 /* Use vec_set patterns for inserting parts of vectors whenever
653 available. */
654 if (VECTOR_MODE_P (GET_MODE (op0))
655 && !MEM_P (op0)
656 && optab_handler (vec_set_optab, GET_MODE (op0)) != CODE_FOR_nothing
657 && fieldmode == GET_MODE_INNER (GET_MODE (op0))
658 && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
659 && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
661 struct expand_operand ops[3];
662 enum machine_mode outermode = GET_MODE (op0);
663 enum machine_mode innermode = GET_MODE_INNER (outermode);
664 enum insn_code icode = optab_handler (vec_set_optab, outermode);
665 int pos = bitnum / GET_MODE_BITSIZE (innermode);
667 create_fixed_operand (&ops[0], op0);
668 create_input_operand (&ops[1], value, innermode);
669 create_integer_operand (&ops[2], pos);
670 if (maybe_expand_insn (icode, 3, ops))
671 return true;
674 /* If the target is a register, overwriting the entire object, or storing
675 a full-word or multi-word field can be done with just a SUBREG. */
676 if (!MEM_P (op0)
677 && bitsize == GET_MODE_BITSIZE (fieldmode)
678 && ((bitsize == GET_MODE_BITSIZE (GET_MODE (op0)) && bitnum == 0)
679 || (bitsize % BITS_PER_WORD == 0 && bitnum % BITS_PER_WORD == 0)))
681 /* Use the subreg machinery either to narrow OP0 to the required
682 words or to cope with mode punning between equal-sized modes.
683 In the latter case, use subreg on the rhs side, not lhs. */
684 rtx sub;
686 if (bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
688 sub = simplify_gen_subreg (GET_MODE (op0), value, fieldmode, 0);
689 if (sub)
691 emit_move_insn (op0, sub);
692 return true;
695 else
697 sub = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0),
698 bitnum / BITS_PER_UNIT);
699 if (sub)
701 emit_move_insn (sub, value);
702 return true;
707 /* If the target is memory, storing any naturally aligned field can be
708 done with a simple store. For targets that support fast unaligned
709 memory, any naturally sized, unit aligned field can be done directly. */
710 if (simple_mem_bitfield_p (op0, bitsize, bitnum, fieldmode))
712 op0 = adjust_bitfield_address (op0, fieldmode, bitnum / BITS_PER_UNIT);
713 emit_move_insn (op0, value);
714 return true;
717 /* Make sure we are playing with integral modes. Pun with subregs
718 if we aren't. This must come after the entire register case above,
719 since that case is valid for any mode. The following cases are only
720 valid for integral modes. */
722 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
723 if (imode != GET_MODE (op0))
725 if (MEM_P (op0))
726 op0 = adjust_bitfield_address_size (op0, imode, 0, MEM_SIZE (op0));
727 else
729 gcc_assert (imode != BLKmode);
730 op0 = gen_lowpart (imode, op0);
735 /* Storing an lsb-aligned field in a register
736 can be done with a movstrict instruction. */
738 if (!MEM_P (op0)
739 && lowpart_bit_field_p (bitnum, bitsize, GET_MODE (op0))
740 && bitsize == GET_MODE_BITSIZE (fieldmode)
741 && optab_handler (movstrict_optab, fieldmode) != CODE_FOR_nothing)
743 struct expand_operand ops[2];
744 enum insn_code icode = optab_handler (movstrict_optab, fieldmode);
745 rtx arg0 = op0;
746 unsigned HOST_WIDE_INT subreg_off;
748 if (GET_CODE (arg0) == SUBREG)
750 /* Else we've got some float mode source being extracted into
751 a different float mode destination -- this combination of
752 subregs results in Severe Tire Damage. */
753 gcc_assert (GET_MODE (SUBREG_REG (arg0)) == fieldmode
754 || GET_MODE_CLASS (fieldmode) == MODE_INT
755 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT);
756 arg0 = SUBREG_REG (arg0);
759 subreg_off = bitnum / BITS_PER_UNIT;
760 if (validate_subreg (fieldmode, GET_MODE (arg0), arg0, subreg_off))
762 arg0 = gen_rtx_SUBREG (fieldmode, arg0, subreg_off);
764 create_fixed_operand (&ops[0], arg0);
765 /* Shrink the source operand to FIELDMODE. */
766 create_convert_operand_to (&ops[1], value, fieldmode, false);
767 if (maybe_expand_insn (icode, 2, ops))
768 return true;
772 /* Handle fields bigger than a word. */
774 if (bitsize > BITS_PER_WORD)
776 /* Here we transfer the words of the field
777 in the order least significant first.
778 This is because the most significant word is the one which may
779 be less than full.
780 However, only do that if the value is not BLKmode. */
782 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode;
783 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
784 unsigned int i;
785 rtx last;
787 /* This is the mode we must force value to, so that there will be enough
788 subwords to extract. Note that fieldmode will often (always?) be
789 VOIDmode, because that is what store_field uses to indicate that this
790 is a bit field, but passing VOIDmode to operand_subword_force
791 is not allowed. */
792 fieldmode = GET_MODE (value);
793 if (fieldmode == VOIDmode)
794 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT);
796 last = get_last_insn ();
797 for (i = 0; i < nwords; i++)
799 /* If I is 0, use the low-order word in both field and target;
800 if I is 1, use the next to lowest word; and so on. */
801 unsigned int wordnum = (backwards
802 ? GET_MODE_SIZE (fieldmode) / UNITS_PER_WORD
803 - i - 1
804 : i);
805 unsigned int bit_offset = (backwards
806 ? MAX ((int) bitsize - ((int) i + 1)
807 * BITS_PER_WORD,
809 : (int) i * BITS_PER_WORD);
810 rtx value_word = operand_subword_force (value, wordnum, fieldmode);
811 unsigned HOST_WIDE_INT new_bitsize =
812 MIN (BITS_PER_WORD, bitsize - i * BITS_PER_WORD);
814 /* If the remaining chunk doesn't have full wordsize we have
815 to make sure that for big endian machines the higher order
816 bits are used. */
817 if (new_bitsize < BITS_PER_WORD && BYTES_BIG_ENDIAN && !backwards)
818 value_word = simplify_expand_binop (word_mode, lshr_optab,
819 value_word,
820 GEN_INT (BITS_PER_WORD
821 - new_bitsize),
822 NULL_RTX, true,
823 OPTAB_LIB_WIDEN);
825 if (!store_bit_field_1 (op0, new_bitsize,
826 bitnum + bit_offset,
827 bitregion_start, bitregion_end,
828 word_mode,
829 value_word, fallback_p))
831 delete_insns_since (last);
832 return false;
835 return true;
838 /* If VALUE has a floating-point or complex mode, access it as an
839 integer of the corresponding size. This can occur on a machine
840 with 64 bit registers that uses SFmode for float. It can also
841 occur for unaligned float or complex fields. */
842 orig_value = value;
843 if (GET_MODE (value) != VOIDmode
844 && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT
845 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT)
847 value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value)));
848 emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value);
851 /* If OP0 is a multi-word register, narrow it to the affected word.
852 If the region spans two words, defer to store_split_bit_field. */
853 if (!MEM_P (op0) && GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
855 op0 = simplify_gen_subreg (word_mode, op0, GET_MODE (op0),
856 bitnum / BITS_PER_WORD * UNITS_PER_WORD);
857 gcc_assert (op0);
858 bitnum %= BITS_PER_WORD;
859 if (bitnum + bitsize > BITS_PER_WORD)
861 if (!fallback_p)
862 return false;
864 store_split_bit_field (op0, bitsize, bitnum, bitregion_start,
865 bitregion_end, value);
866 return true;
870 /* From here on we can assume that the field to be stored in fits
871 within a word. If the destination is a register, it too fits
872 in a word. */
874 extraction_insn insv;
875 if (!MEM_P (op0)
876 && get_best_reg_extraction_insn (&insv, EP_insv,
877 GET_MODE_BITSIZE (GET_MODE (op0)),
878 fieldmode)
879 && store_bit_field_using_insv (&insv, op0, bitsize, bitnum, value))
880 return true;
882 /* If OP0 is a memory, try copying it to a register and seeing if a
883 cheap register alternative is available. */
884 if (MEM_P (op0))
886 if (get_best_mem_extraction_insn (&insv, EP_insv, bitsize, bitnum,
887 fieldmode)
888 && store_bit_field_using_insv (&insv, op0, bitsize, bitnum, value))
889 return true;
891 rtx last = get_last_insn ();
893 /* Try loading part of OP0 into a register, inserting the bitfield
894 into that, and then copying the result back to OP0. */
895 unsigned HOST_WIDE_INT bitpos;
896 rtx xop0 = adjust_bit_field_mem_for_reg (EP_insv, op0, bitsize, bitnum,
897 bitregion_start, bitregion_end,
898 fieldmode, &bitpos);
899 if (xop0)
901 rtx tempreg = copy_to_reg (xop0);
902 if (store_bit_field_1 (tempreg, bitsize, bitpos,
903 bitregion_start, bitregion_end,
904 fieldmode, orig_value, false))
906 emit_move_insn (xop0, tempreg);
907 return true;
909 delete_insns_since (last);
913 if (!fallback_p)
914 return false;
916 store_fixed_bit_field (op0, bitsize, bitnum, bitregion_start,
917 bitregion_end, value);
918 return true;
921 /* Generate code to store value from rtx VALUE
922 into a bit-field within structure STR_RTX
923 containing BITSIZE bits starting at bit BITNUM.
925 BITREGION_START is bitpos of the first bitfield in this region.
926 BITREGION_END is the bitpos of the ending bitfield in this region.
927 These two fields are 0, if the C++ memory model does not apply,
928 or we are not interested in keeping track of bitfield regions.
930 FIELDMODE is the machine-mode of the FIELD_DECL node for this field. */
932 void
933 store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
934 unsigned HOST_WIDE_INT bitnum,
935 unsigned HOST_WIDE_INT bitregion_start,
936 unsigned HOST_WIDE_INT bitregion_end,
937 enum machine_mode fieldmode,
938 rtx value)
940 /* Handle -fstrict-volatile-bitfields in the cases where it applies. */
941 if (strict_volatile_bitfield_p (str_rtx, bitsize, bitnum, fieldmode,
942 bitregion_start, bitregion_end))
944 /* Storing any naturally aligned field can be done with a simple
945 store. For targets that support fast unaligned memory, any
946 naturally sized, unit aligned field can be done directly. */
947 if (simple_mem_bitfield_p (str_rtx, bitsize, bitnum, fieldmode))
949 str_rtx = adjust_bitfield_address (str_rtx, fieldmode,
950 bitnum / BITS_PER_UNIT);
951 emit_move_insn (str_rtx, value);
953 else
955 str_rtx = narrow_bit_field_mem (str_rtx, fieldmode, bitsize, bitnum,
956 &bitnum);
957 /* Explicitly override the C/C++ memory model; ignore the
958 bit range so that we can do the access in the mode mandated
959 by -fstrict-volatile-bitfields instead. */
960 store_fixed_bit_field_1 (str_rtx, bitsize, bitnum, value);
963 return;
966 /* Under the C++0x memory model, we must not touch bits outside the
967 bit region. Adjust the address to start at the beginning of the
968 bit region. */
969 if (MEM_P (str_rtx) && bitregion_start > 0)
971 enum machine_mode bestmode;
972 HOST_WIDE_INT offset, size;
974 gcc_assert ((bitregion_start % BITS_PER_UNIT) == 0);
976 offset = bitregion_start / BITS_PER_UNIT;
977 bitnum -= bitregion_start;
978 size = (bitnum + bitsize + BITS_PER_UNIT - 1) / BITS_PER_UNIT;
979 bitregion_end -= bitregion_start;
980 bitregion_start = 0;
981 bestmode = get_best_mode (bitsize, bitnum,
982 bitregion_start, bitregion_end,
983 MEM_ALIGN (str_rtx), VOIDmode,
984 MEM_VOLATILE_P (str_rtx));
985 str_rtx = adjust_bitfield_address_size (str_rtx, bestmode, offset, size);
988 if (!store_bit_field_1 (str_rtx, bitsize, bitnum,
989 bitregion_start, bitregion_end,
990 fieldmode, value, true))
991 gcc_unreachable ();
994 /* Use shifts and boolean operations to store VALUE into a bit field of
995 width BITSIZE in OP0, starting at bit BITNUM. */
997 static void
998 store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
999 unsigned HOST_WIDE_INT bitnum,
1000 unsigned HOST_WIDE_INT bitregion_start,
1001 unsigned HOST_WIDE_INT bitregion_end,
1002 rtx value)
1004 /* There is a case not handled here:
1005 a structure with a known alignment of just a halfword
1006 and a field split across two aligned halfwords within the structure.
1007 Or likewise a structure with a known alignment of just a byte
1008 and a field split across two bytes.
1009 Such cases are not supposed to be able to occur. */
1011 if (MEM_P (op0))
1013 enum machine_mode mode = GET_MODE (op0);
1014 if (GET_MODE_BITSIZE (mode) == 0
1015 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode))
1016 mode = word_mode;
1017 mode = get_best_mode (bitsize, bitnum, bitregion_start, bitregion_end,
1018 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0));
1020 if (mode == VOIDmode)
1022 /* The only way this should occur is if the field spans word
1023 boundaries. */
1024 store_split_bit_field (op0, bitsize, bitnum, bitregion_start,
1025 bitregion_end, value);
1026 return;
1029 op0 = narrow_bit_field_mem (op0, mode, bitsize, bitnum, &bitnum);
1032 store_fixed_bit_field_1 (op0, bitsize, bitnum, value);
1035 /* Helper function for store_fixed_bit_field, stores
1036 the bit field always using the MODE of OP0. */
1038 static void
1039 store_fixed_bit_field_1 (rtx op0, unsigned HOST_WIDE_INT bitsize,
1040 unsigned HOST_WIDE_INT bitnum,
1041 rtx value)
1043 enum machine_mode mode;
1044 rtx temp;
1045 int all_zero = 0;
1046 int all_one = 0;
1048 mode = GET_MODE (op0);
1049 gcc_assert (SCALAR_INT_MODE_P (mode));
1051 /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
1052 for invalid input, such as f5 from gcc.dg/pr48335-2.c. */
1054 if (BYTES_BIG_ENDIAN)
1055 /* BITNUM is the distance between our msb
1056 and that of the containing datum.
1057 Convert it to the distance from the lsb. */
1058 bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
1060 /* Now BITNUM is always the distance between our lsb
1061 and that of OP0. */
1063 /* Shift VALUE left by BITNUM bits. If VALUE is not constant,
1064 we must first convert its mode to MODE. */
1066 if (CONST_INT_P (value))
1068 HOST_WIDE_INT v = INTVAL (value);
1070 if (bitsize < HOST_BITS_PER_WIDE_INT)
1071 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1;
1073 if (v == 0)
1074 all_zero = 1;
1075 else if ((bitsize < HOST_BITS_PER_WIDE_INT
1076 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1)
1077 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1))
1078 all_one = 1;
1080 value = lshift_value (mode, v, bitnum);
1082 else
1084 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize
1085 && bitnum + bitsize != GET_MODE_BITSIZE (mode));
1087 if (GET_MODE (value) != mode)
1088 value = convert_to_mode (mode, value, 1);
1090 if (must_and)
1091 value = expand_binop (mode, and_optab, value,
1092 mask_rtx (mode, 0, bitsize, 0),
1093 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1094 if (bitnum > 0)
1095 value = expand_shift (LSHIFT_EXPR, mode, value,
1096 bitnum, NULL_RTX, 1);
1099 /* Now clear the chosen bits in OP0,
1100 except that if VALUE is -1 we need not bother. */
1101 /* We keep the intermediates in registers to allow CSE to combine
1102 consecutive bitfield assignments. */
1104 temp = force_reg (mode, op0);
1106 if (! all_one)
1108 temp = expand_binop (mode, and_optab, temp,
1109 mask_rtx (mode, bitnum, bitsize, 1),
1110 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1111 temp = force_reg (mode, temp);
1114 /* Now logical-or VALUE into OP0, unless it is zero. */
1116 if (! all_zero)
1118 temp = expand_binop (mode, ior_optab, temp, value,
1119 NULL_RTX, 1, OPTAB_LIB_WIDEN);
1120 temp = force_reg (mode, temp);
1123 if (op0 != temp)
1125 op0 = copy_rtx (op0);
1126 emit_move_insn (op0, temp);
1130 /* Store a bit field that is split across multiple accessible memory objects.
1132 OP0 is the REG, SUBREG or MEM rtx for the first of the objects.
1133 BITSIZE is the field width; BITPOS the position of its first bit
1134 (within the word).
1135 VALUE is the value to store.
1137 This does not yet handle fields wider than BITS_PER_WORD. */
1139 static void
1140 store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1141 unsigned HOST_WIDE_INT bitpos,
1142 unsigned HOST_WIDE_INT bitregion_start,
1143 unsigned HOST_WIDE_INT bitregion_end,
1144 rtx value)
1146 unsigned int unit;
1147 unsigned int bitsdone = 0;
1149 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1150 much at a time. */
1151 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1152 unit = BITS_PER_WORD;
1153 else
1154 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1156 /* If OP0 is a memory with a mode, then UNIT must not be larger than
1157 OP0's mode as well. Otherwise, store_fixed_bit_field will call us
1158 again, and we will mutually recurse forever. */
1159 if (MEM_P (op0) && GET_MODE_BITSIZE (GET_MODE (op0)) > 0)
1160 unit = MIN (unit, GET_MODE_BITSIZE (GET_MODE (op0)));
1162 /* If VALUE is a constant other than a CONST_INT, get it into a register in
1163 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note
1164 that VALUE might be a floating-point constant. */
1165 if (CONSTANT_P (value) && !CONST_INT_P (value))
1167 rtx word = gen_lowpart_common (word_mode, value);
1169 if (word && (value != word))
1170 value = word;
1171 else
1172 value = gen_lowpart_common (word_mode,
1173 force_reg (GET_MODE (value) != VOIDmode
1174 ? GET_MODE (value)
1175 : word_mode, value));
1178 while (bitsdone < bitsize)
1180 unsigned HOST_WIDE_INT thissize;
1181 rtx part, word;
1182 unsigned HOST_WIDE_INT thispos;
1183 unsigned HOST_WIDE_INT offset;
1185 offset = (bitpos + bitsdone) / unit;
1186 thispos = (bitpos + bitsdone) % unit;
1188 /* When region of bytes we can touch is restricted, decrease
1189 UNIT close to the end of the region as needed. If op0 is a REG
1190 or SUBREG of REG, don't do this, as there can't be data races
1191 on a register and we can expand shorter code in some cases. */
1192 if (bitregion_end
1193 && unit > BITS_PER_UNIT
1194 && bitpos + bitsdone - thispos + unit > bitregion_end + 1
1195 && !REG_P (op0)
1196 && (GET_CODE (op0) != SUBREG || !REG_P (SUBREG_REG (op0))))
1198 unit = unit / 2;
1199 continue;
1202 /* THISSIZE must not overrun a word boundary. Otherwise,
1203 store_fixed_bit_field will call us again, and we will mutually
1204 recurse forever. */
1205 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1206 thissize = MIN (thissize, unit - thispos);
1208 if (BYTES_BIG_ENDIAN)
1210 /* Fetch successively less significant portions. */
1211 if (CONST_INT_P (value))
1212 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1213 >> (bitsize - bitsdone - thissize))
1214 & (((HOST_WIDE_INT) 1 << thissize) - 1));
1215 else
1217 int total_bits = GET_MODE_BITSIZE (GET_MODE (value));
1218 /* The args are chosen so that the last part includes the
1219 lsb. Give extract_bit_field the value it needs (with
1220 endianness compensation) to fetch the piece we want. */
1221 part = extract_fixed_bit_field (word_mode, value, thissize,
1222 total_bits - bitsize + bitsdone,
1223 NULL_RTX, 1);
1226 else
1228 /* Fetch successively more significant portions. */
1229 if (CONST_INT_P (value))
1230 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value))
1231 >> bitsdone)
1232 & (((HOST_WIDE_INT) 1 << thissize) - 1));
1233 else
1234 part = extract_fixed_bit_field (word_mode, value, thissize,
1235 bitsdone, NULL_RTX, 1);
1238 /* If OP0 is a register, then handle OFFSET here.
1240 When handling multiword bitfields, extract_bit_field may pass
1241 down a word_mode SUBREG of a larger REG for a bitfield that actually
1242 crosses a word boundary. Thus, for a SUBREG, we must find
1243 the current word starting from the base register. */
1244 if (GET_CODE (op0) == SUBREG)
1246 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD)
1247 + (offset * unit / BITS_PER_WORD);
1248 enum machine_mode sub_mode = GET_MODE (SUBREG_REG (op0));
1249 if (sub_mode != BLKmode && GET_MODE_SIZE (sub_mode) < UNITS_PER_WORD)
1250 word = word_offset ? const0_rtx : op0;
1251 else
1252 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1253 GET_MODE (SUBREG_REG (op0)));
1254 offset &= BITS_PER_WORD / unit - 1;
1256 else if (REG_P (op0))
1258 enum machine_mode op0_mode = GET_MODE (op0);
1259 if (op0_mode != BLKmode && GET_MODE_SIZE (op0_mode) < UNITS_PER_WORD)
1260 word = offset ? const0_rtx : op0;
1261 else
1262 word = operand_subword_force (op0, offset * unit / BITS_PER_WORD,
1263 GET_MODE (op0));
1264 offset &= BITS_PER_WORD / unit - 1;
1266 else
1267 word = op0;
1269 /* OFFSET is in UNITs, and UNIT is in bits. If WORD is const0_rtx,
1270 it is just an out-of-bounds access. Ignore it. */
1271 if (word != const0_rtx)
1272 store_fixed_bit_field (word, thissize, offset * unit + thispos,
1273 bitregion_start, bitregion_end, part);
1274 bitsdone += thissize;
1278 /* A subroutine of extract_bit_field_1 that converts return value X
1279 to either MODE or TMODE. MODE, TMODE and UNSIGNEDP are arguments
1280 to extract_bit_field. */
1282 static rtx
1283 convert_extracted_bit_field (rtx x, enum machine_mode mode,
1284 enum machine_mode tmode, bool unsignedp)
1286 if (GET_MODE (x) == tmode || GET_MODE (x) == mode)
1287 return x;
1289 /* If the x mode is not a scalar integral, first convert to the
1290 integer mode of that size and then access it as a floating-point
1291 value via a SUBREG. */
1292 if (!SCALAR_INT_MODE_P (tmode))
1294 enum machine_mode smode;
1296 smode = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0);
1297 x = convert_to_mode (smode, x, unsignedp);
1298 x = force_reg (smode, x);
1299 return gen_lowpart (tmode, x);
1302 return convert_to_mode (tmode, x, unsignedp);
1305 /* Try to use an ext(z)v pattern to extract a field from OP0.
1306 Return the extracted value on success, otherwise return null.
1307 EXT_MODE is the mode of the extraction and the other arguments
1308 are as for extract_bit_field. */
1310 static rtx
1311 extract_bit_field_using_extv (const extraction_insn *extv, rtx op0,
1312 unsigned HOST_WIDE_INT bitsize,
1313 unsigned HOST_WIDE_INT bitnum,
1314 int unsignedp, rtx target,
1315 enum machine_mode mode, enum machine_mode tmode)
1317 struct expand_operand ops[4];
1318 rtx spec_target = target;
1319 rtx spec_target_subreg = 0;
1320 enum machine_mode ext_mode = extv->field_mode;
1321 unsigned unit = GET_MODE_BITSIZE (ext_mode);
1323 if (bitsize == 0 || unit < bitsize)
1324 return NULL_RTX;
1326 if (MEM_P (op0))
1327 /* Get a reference to the first byte of the field. */
1328 op0 = narrow_bit_field_mem (op0, extv->struct_mode, bitsize, bitnum,
1329 &bitnum);
1330 else
1332 /* Convert from counting within OP0 to counting in EXT_MODE. */
1333 if (BYTES_BIG_ENDIAN)
1334 bitnum += unit - GET_MODE_BITSIZE (GET_MODE (op0));
1336 /* If op0 is a register, we need it in EXT_MODE to make it
1337 acceptable to the format of ext(z)v. */
1338 if (GET_CODE (op0) == SUBREG && GET_MODE (op0) != ext_mode)
1339 return NULL_RTX;
1340 if (REG_P (op0) && GET_MODE (op0) != ext_mode)
1341 op0 = gen_lowpart_SUBREG (ext_mode, op0);
1344 /* If BITS_BIG_ENDIAN is zero on a BYTES_BIG_ENDIAN machine, we count
1345 "backwards" from the size of the unit we are extracting from.
1346 Otherwise, we count bits from the most significant on a
1347 BYTES/BITS_BIG_ENDIAN machine. */
1349 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN)
1350 bitnum = unit - bitsize - bitnum;
1352 if (target == 0)
1353 target = spec_target = gen_reg_rtx (tmode);
1355 if (GET_MODE (target) != ext_mode)
1357 /* Don't use LHS paradoxical subreg if explicit truncation is needed
1358 between the mode of the extraction (word_mode) and the target
1359 mode. Instead, create a temporary and use convert_move to set
1360 the target. */
1361 if (REG_P (target)
1362 && TRULY_NOOP_TRUNCATION_MODES_P (GET_MODE (target), ext_mode))
1364 target = gen_lowpart (ext_mode, target);
1365 if (GET_MODE_PRECISION (ext_mode)
1366 > GET_MODE_PRECISION (GET_MODE (spec_target)))
1367 spec_target_subreg = target;
1369 else
1370 target = gen_reg_rtx (ext_mode);
1373 create_output_operand (&ops[0], target, ext_mode);
1374 create_fixed_operand (&ops[1], op0);
1375 create_integer_operand (&ops[2], bitsize);
1376 create_integer_operand (&ops[3], bitnum);
1377 if (maybe_expand_insn (extv->icode, 4, ops))
1379 target = ops[0].value;
1380 if (target == spec_target)
1381 return target;
1382 if (target == spec_target_subreg)
1383 return spec_target;
1384 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1386 return NULL_RTX;
1389 /* A subroutine of extract_bit_field, with the same arguments.
1390 If FALLBACK_P is true, fall back to extract_fixed_bit_field
1391 if we can find no other means of implementing the operation.
1392 if FALLBACK_P is false, return NULL instead. */
1394 static rtx
1395 extract_bit_field_1 (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1396 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1397 enum machine_mode mode, enum machine_mode tmode,
1398 bool fallback_p)
1400 rtx op0 = str_rtx;
1401 enum machine_mode int_mode;
1402 enum machine_mode mode1;
1404 if (tmode == VOIDmode)
1405 tmode = mode;
1407 while (GET_CODE (op0) == SUBREG)
1409 bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT;
1410 op0 = SUBREG_REG (op0);
1413 /* If we have an out-of-bounds access to a register, just return an
1414 uninitialized register of the required mode. This can occur if the
1415 source code contains an out-of-bounds access to a small array. */
1416 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0)))
1417 return gen_reg_rtx (tmode);
1419 if (REG_P (op0)
1420 && mode == GET_MODE (op0)
1421 && bitnum == 0
1422 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0)))
1424 /* We're trying to extract a full register from itself. */
1425 return op0;
1428 /* See if we can get a better vector mode before extracting. */
1429 if (VECTOR_MODE_P (GET_MODE (op0))
1430 && !MEM_P (op0)
1431 && GET_MODE_INNER (GET_MODE (op0)) != tmode)
1433 enum machine_mode new_mode;
1435 if (GET_MODE_CLASS (tmode) == MODE_FLOAT)
1436 new_mode = MIN_MODE_VECTOR_FLOAT;
1437 else if (GET_MODE_CLASS (tmode) == MODE_FRACT)
1438 new_mode = MIN_MODE_VECTOR_FRACT;
1439 else if (GET_MODE_CLASS (tmode) == MODE_UFRACT)
1440 new_mode = MIN_MODE_VECTOR_UFRACT;
1441 else if (GET_MODE_CLASS (tmode) == MODE_ACCUM)
1442 new_mode = MIN_MODE_VECTOR_ACCUM;
1443 else if (GET_MODE_CLASS (tmode) == MODE_UACCUM)
1444 new_mode = MIN_MODE_VECTOR_UACCUM;
1445 else
1446 new_mode = MIN_MODE_VECTOR_INT;
1448 for (; new_mode != VOIDmode ; new_mode = GET_MODE_WIDER_MODE (new_mode))
1449 if (GET_MODE_SIZE (new_mode) == GET_MODE_SIZE (GET_MODE (op0))
1450 && targetm.vector_mode_supported_p (new_mode))
1451 break;
1452 if (new_mode != VOIDmode)
1453 op0 = gen_lowpart (new_mode, op0);
1456 /* Use vec_extract patterns for extracting parts of vectors whenever
1457 available. */
1458 if (VECTOR_MODE_P (GET_MODE (op0))
1459 && !MEM_P (op0)
1460 && optab_handler (vec_extract_optab, GET_MODE (op0)) != CODE_FOR_nothing
1461 && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))
1462 == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0)))))
1464 struct expand_operand ops[3];
1465 enum machine_mode outermode = GET_MODE (op0);
1466 enum machine_mode innermode = GET_MODE_INNER (outermode);
1467 enum insn_code icode = optab_handler (vec_extract_optab, outermode);
1468 unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode);
1470 create_output_operand (&ops[0], target, innermode);
1471 create_input_operand (&ops[1], op0, outermode);
1472 create_integer_operand (&ops[2], pos);
1473 if (maybe_expand_insn (icode, 3, ops))
1475 target = ops[0].value;
1476 if (GET_MODE (target) != mode)
1477 return gen_lowpart (tmode, target);
1478 return target;
1482 /* Make sure we are playing with integral modes. Pun with subregs
1483 if we aren't. */
1485 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0));
1486 if (imode != GET_MODE (op0))
1488 if (MEM_P (op0))
1489 op0 = adjust_bitfield_address_size (op0, imode, 0, MEM_SIZE (op0));
1490 else if (imode != BLKmode)
1492 op0 = gen_lowpart (imode, op0);
1494 /* If we got a SUBREG, force it into a register since we
1495 aren't going to be able to do another SUBREG on it. */
1496 if (GET_CODE (op0) == SUBREG)
1497 op0 = force_reg (imode, op0);
1499 else if (REG_P (op0))
1501 rtx reg, subreg;
1502 imode = smallest_mode_for_size (GET_MODE_BITSIZE (GET_MODE (op0)),
1503 MODE_INT);
1504 reg = gen_reg_rtx (imode);
1505 subreg = gen_lowpart_SUBREG (GET_MODE (op0), reg);
1506 emit_move_insn (subreg, op0);
1507 op0 = reg;
1508 bitnum += SUBREG_BYTE (subreg) * BITS_PER_UNIT;
1510 else
1512 HOST_WIDE_INT size = GET_MODE_SIZE (GET_MODE (op0));
1513 rtx mem = assign_stack_temp (GET_MODE (op0), size);
1514 emit_move_insn (mem, op0);
1515 op0 = adjust_bitfield_address_size (mem, BLKmode, 0, size);
1520 /* ??? We currently assume TARGET is at least as big as BITSIZE.
1521 If that's wrong, the solution is to test for it and set TARGET to 0
1522 if needed. */
1524 /* Get the mode of the field to use for atomic access or subreg
1525 conversion. */
1526 mode1 = mode;
1527 if (SCALAR_INT_MODE_P (tmode))
1529 enum machine_mode try_mode = mode_for_size (bitsize,
1530 GET_MODE_CLASS (tmode), 0);
1531 if (try_mode != BLKmode)
1532 mode1 = try_mode;
1534 gcc_assert (mode1 != BLKmode);
1536 /* Extraction of a full MODE1 value can be done with a subreg as long
1537 as the least significant bit of the value is the least significant
1538 bit of either OP0 or a word of OP0. */
1539 if (!MEM_P (op0)
1540 && lowpart_bit_field_p (bitnum, bitsize, GET_MODE (op0))
1541 && bitsize == GET_MODE_BITSIZE (mode1)
1542 && TRULY_NOOP_TRUNCATION_MODES_P (mode1, GET_MODE (op0)))
1544 rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0),
1545 bitnum / BITS_PER_UNIT);
1546 if (sub)
1547 return convert_extracted_bit_field (sub, mode, tmode, unsignedp);
1550 /* Extraction of a full MODE1 value can be done with a load as long as
1551 the field is on a byte boundary and is sufficiently aligned. */
1552 if (simple_mem_bitfield_p (op0, bitsize, bitnum, mode1))
1554 op0 = adjust_bitfield_address (op0, mode1, bitnum / BITS_PER_UNIT);
1555 return convert_extracted_bit_field (op0, mode, tmode, unsignedp);
1558 /* Handle fields bigger than a word. */
1560 if (bitsize > BITS_PER_WORD)
1562 /* Here we transfer the words of the field
1563 in the order least significant first.
1564 This is because the most significant word is the one which may
1565 be less than full. */
1567 unsigned int backwards = WORDS_BIG_ENDIAN;
1568 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD;
1569 unsigned int i;
1570 rtx last;
1572 if (target == 0 || !REG_P (target) || !valid_multiword_target_p (target))
1573 target = gen_reg_rtx (mode);
1575 /* Indicate for flow that the entire target reg is being set. */
1576 emit_clobber (target);
1578 last = get_last_insn ();
1579 for (i = 0; i < nwords; i++)
1581 /* If I is 0, use the low-order word in both field and target;
1582 if I is 1, use the next to lowest word; and so on. */
1583 /* Word number in TARGET to use. */
1584 unsigned int wordnum
1585 = (backwards
1586 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1
1587 : i);
1588 /* Offset from start of field in OP0. */
1589 unsigned int bit_offset = (backwards
1590 ? MAX ((int) bitsize - ((int) i + 1)
1591 * BITS_PER_WORD,
1593 : (int) i * BITS_PER_WORD);
1594 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode);
1595 rtx result_part
1596 = extract_bit_field_1 (op0, MIN (BITS_PER_WORD,
1597 bitsize - i * BITS_PER_WORD),
1598 bitnum + bit_offset, 1, target_part,
1599 mode, word_mode, fallback_p);
1601 gcc_assert (target_part);
1602 if (!result_part)
1604 delete_insns_since (last);
1605 return NULL;
1608 if (result_part != target_part)
1609 emit_move_insn (target_part, result_part);
1612 if (unsignedp)
1614 /* Unless we've filled TARGET, the upper regs in a multi-reg value
1615 need to be zero'd out. */
1616 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD)
1618 unsigned int i, total_words;
1620 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD;
1621 for (i = nwords; i < total_words; i++)
1622 emit_move_insn
1623 (operand_subword (target,
1624 backwards ? total_words - i - 1 : i,
1625 1, VOIDmode),
1626 const0_rtx);
1628 return target;
1631 /* Signed bit field: sign-extend with two arithmetic shifts. */
1632 target = expand_shift (LSHIFT_EXPR, mode, target,
1633 GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1634 return expand_shift (RSHIFT_EXPR, mode, target,
1635 GET_MODE_BITSIZE (mode) - bitsize, NULL_RTX, 0);
1638 /* If OP0 is a multi-word register, narrow it to the affected word.
1639 If the region spans two words, defer to extract_split_bit_field. */
1640 if (!MEM_P (op0) && GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD)
1642 op0 = simplify_gen_subreg (word_mode, op0, GET_MODE (op0),
1643 bitnum / BITS_PER_WORD * UNITS_PER_WORD);
1644 bitnum %= BITS_PER_WORD;
1645 if (bitnum + bitsize > BITS_PER_WORD)
1647 if (!fallback_p)
1648 return NULL_RTX;
1649 target = extract_split_bit_field (op0, bitsize, bitnum, unsignedp);
1650 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1654 /* From here on we know the desired field is smaller than a word.
1655 If OP0 is a register, it too fits within a word. */
1656 enum extraction_pattern pattern = unsignedp ? EP_extzv : EP_extv;
1657 extraction_insn extv;
1658 if (!MEM_P (op0)
1659 /* ??? We could limit the structure size to the part of OP0 that
1660 contains the field, with appropriate checks for endianness
1661 and TRULY_NOOP_TRUNCATION. */
1662 && get_best_reg_extraction_insn (&extv, pattern,
1663 GET_MODE_BITSIZE (GET_MODE (op0)),
1664 tmode))
1666 rtx result = extract_bit_field_using_extv (&extv, op0, bitsize, bitnum,
1667 unsignedp, target, mode,
1668 tmode);
1669 if (result)
1670 return result;
1673 /* If OP0 is a memory, try copying it to a register and seeing if a
1674 cheap register alternative is available. */
1675 if (MEM_P (op0))
1677 if (get_best_mem_extraction_insn (&extv, pattern, bitsize, bitnum,
1678 tmode))
1680 rtx result = extract_bit_field_using_extv (&extv, op0, bitsize,
1681 bitnum, unsignedp,
1682 target, mode,
1683 tmode);
1684 if (result)
1685 return result;
1688 rtx last = get_last_insn ();
1690 /* Try loading part of OP0 into a register and extracting the
1691 bitfield from that. */
1692 unsigned HOST_WIDE_INT bitpos;
1693 rtx xop0 = adjust_bit_field_mem_for_reg (pattern, op0, bitsize, bitnum,
1694 0, 0, tmode, &bitpos);
1695 if (xop0)
1697 xop0 = copy_to_reg (xop0);
1698 rtx result = extract_bit_field_1 (xop0, bitsize, bitpos,
1699 unsignedp, target,
1700 mode, tmode, false);
1701 if (result)
1702 return result;
1703 delete_insns_since (last);
1707 if (!fallback_p)
1708 return NULL;
1710 /* Find a correspondingly-sized integer field, so we can apply
1711 shifts and masks to it. */
1712 int_mode = int_mode_for_mode (tmode);
1713 if (int_mode == BLKmode)
1714 int_mode = int_mode_for_mode (mode);
1715 /* Should probably push op0 out to memory and then do a load. */
1716 gcc_assert (int_mode != BLKmode);
1718 target = extract_fixed_bit_field (int_mode, op0, bitsize, bitnum,
1719 target, unsignedp);
1720 return convert_extracted_bit_field (target, mode, tmode, unsignedp);
1723 /* Generate code to extract a byte-field from STR_RTX
1724 containing BITSIZE bits, starting at BITNUM,
1725 and put it in TARGET if possible (if TARGET is nonzero).
1726 Regardless of TARGET, we return the rtx for where the value is placed.
1728 STR_RTX is the structure containing the byte (a REG or MEM).
1729 UNSIGNEDP is nonzero if this is an unsigned bit field.
1730 MODE is the natural mode of the field value once extracted.
1731 TMODE is the mode the caller would like the value to have;
1732 but the value may be returned with type MODE instead.
1734 If a TARGET is specified and we can store in it at no extra cost,
1735 we do so, and return TARGET.
1736 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred
1737 if they are equally easy. */
1740 extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize,
1741 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target,
1742 enum machine_mode mode, enum machine_mode tmode)
1744 enum machine_mode mode1;
1746 /* Handle -fstrict-volatile-bitfields in the cases where it applies. */
1747 if (GET_MODE_BITSIZE (GET_MODE (str_rtx)) > 0)
1748 mode1 = GET_MODE (str_rtx);
1749 else if (target && GET_MODE_BITSIZE (GET_MODE (target)) > 0)
1750 mode1 = GET_MODE (target);
1751 else
1752 mode1 = tmode;
1754 if (strict_volatile_bitfield_p (str_rtx, bitsize, bitnum, mode1, 0, 0))
1756 rtx result;
1758 /* Extraction of a full MODE1 value can be done with a load as long as
1759 the field is on a byte boundary and is sufficiently aligned. */
1760 if (simple_mem_bitfield_p (str_rtx, bitsize, bitnum, mode1))
1761 result = adjust_bitfield_address (str_rtx, mode1,
1762 bitnum / BITS_PER_UNIT);
1763 else
1765 str_rtx = narrow_bit_field_mem (str_rtx, mode1, bitsize, bitnum,
1766 &bitnum);
1767 result = extract_fixed_bit_field_1 (mode, str_rtx, bitsize, bitnum,
1768 target, unsignedp);
1771 return convert_extracted_bit_field (result, mode, tmode, unsignedp);
1774 return extract_bit_field_1 (str_rtx, bitsize, bitnum, unsignedp,
1775 target, mode, tmode, true);
1778 /* Use shifts and boolean operations to extract a field of BITSIZE bits
1779 from bit BITNUM of OP0.
1781 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value).
1782 If TARGET is nonzero, attempts to store the value there
1783 and return TARGET, but this is not guaranteed.
1784 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */
1786 static rtx
1787 extract_fixed_bit_field (enum machine_mode tmode, rtx op0,
1788 unsigned HOST_WIDE_INT bitsize,
1789 unsigned HOST_WIDE_INT bitnum, rtx target,
1790 int unsignedp)
1792 if (MEM_P (op0))
1794 enum machine_mode mode
1795 = get_best_mode (bitsize, bitnum, 0, 0, MEM_ALIGN (op0), word_mode,
1796 MEM_VOLATILE_P (op0));
1798 if (mode == VOIDmode)
1799 /* The only way this should occur is if the field spans word
1800 boundaries. */
1801 return extract_split_bit_field (op0, bitsize, bitnum, unsignedp);
1803 op0 = narrow_bit_field_mem (op0, mode, bitsize, bitnum, &bitnum);
1806 return extract_fixed_bit_field_1 (tmode, op0, bitsize, bitnum,
1807 target, unsignedp);
1810 /* Helper function for extract_fixed_bit_field, extracts
1811 the bit field always using the MODE of OP0. */
1813 static rtx
1814 extract_fixed_bit_field_1 (enum machine_mode tmode, rtx op0,
1815 unsigned HOST_WIDE_INT bitsize,
1816 unsigned HOST_WIDE_INT bitnum, rtx target,
1817 int unsignedp)
1819 enum machine_mode mode = GET_MODE (op0);
1820 gcc_assert (SCALAR_INT_MODE_P (mode));
1822 /* Note that bitsize + bitnum can be greater than GET_MODE_BITSIZE (mode)
1823 for invalid input, such as extract equivalent of f5 from
1824 gcc.dg/pr48335-2.c. */
1826 if (BYTES_BIG_ENDIAN)
1827 /* BITNUM is the distance between our msb and that of OP0.
1828 Convert it to the distance from the lsb. */
1829 bitnum = GET_MODE_BITSIZE (mode) - bitsize - bitnum;
1831 /* Now BITNUM is always the distance between the field's lsb and that of OP0.
1832 We have reduced the big-endian case to the little-endian case. */
1834 if (unsignedp)
1836 if (bitnum)
1838 /* If the field does not already start at the lsb,
1839 shift it so it does. */
1840 /* Maybe propagate the target for the shift. */
1841 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1842 if (tmode != mode)
1843 subtarget = 0;
1844 op0 = expand_shift (RSHIFT_EXPR, mode, op0, bitnum, subtarget, 1);
1846 /* Convert the value to the desired mode. */
1847 if (mode != tmode)
1848 op0 = convert_to_mode (tmode, op0, 1);
1850 /* Unless the msb of the field used to be the msb when we shifted,
1851 mask out the upper bits. */
1853 if (GET_MODE_BITSIZE (mode) != bitnum + bitsize)
1854 return expand_binop (GET_MODE (op0), and_optab, op0,
1855 mask_rtx (GET_MODE (op0), 0, bitsize, 0),
1856 target, 1, OPTAB_LIB_WIDEN);
1857 return op0;
1860 /* To extract a signed bit-field, first shift its msb to the msb of the word,
1861 then arithmetic-shift its lsb to the lsb of the word. */
1862 op0 = force_reg (mode, op0);
1864 /* Find the narrowest integer mode that contains the field. */
1866 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode;
1867 mode = GET_MODE_WIDER_MODE (mode))
1868 if (GET_MODE_BITSIZE (mode) >= bitsize + bitnum)
1870 op0 = convert_to_mode (mode, op0, 0);
1871 break;
1874 if (mode != tmode)
1875 target = 0;
1877 if (GET_MODE_BITSIZE (mode) != (bitsize + bitnum))
1879 int amount = GET_MODE_BITSIZE (mode) - (bitsize + bitnum);
1880 /* Maybe propagate the target for the shift. */
1881 rtx subtarget = (target != 0 && REG_P (target) ? target : 0);
1882 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1);
1885 return expand_shift (RSHIFT_EXPR, mode, op0,
1886 GET_MODE_BITSIZE (mode) - bitsize, target, 0);
1889 /* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value
1890 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the
1891 complement of that if COMPLEMENT. The mask is truncated if
1892 necessary to the width of mode MODE. The mask is zero-extended if
1893 BITSIZE+BITPOS is too small for MODE. */
1895 static rtx
1896 mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement)
1898 double_int mask;
1900 mask = double_int::mask (bitsize);
1901 mask = mask.llshift (bitpos, HOST_BITS_PER_DOUBLE_INT);
1903 if (complement)
1904 mask = ~mask;
1906 return immed_double_int_const (mask, mode);
1909 /* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value
1910 VALUE << BITPOS. */
1912 static rtx
1913 lshift_value (enum machine_mode mode, unsigned HOST_WIDE_INT value,
1914 int bitpos)
1916 double_int val;
1918 val = double_int::from_uhwi (value);
1919 val = val.llshift (bitpos, HOST_BITS_PER_DOUBLE_INT);
1921 return immed_double_int_const (val, mode);
1924 /* Extract a bit field that is split across two words
1925 and return an RTX for the result.
1927 OP0 is the REG, SUBREG or MEM rtx for the first of the two words.
1928 BITSIZE is the field width; BITPOS, position of its first bit, in the word.
1929 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */
1931 static rtx
1932 extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize,
1933 unsigned HOST_WIDE_INT bitpos, int unsignedp)
1935 unsigned int unit;
1936 unsigned int bitsdone = 0;
1937 rtx result = NULL_RTX;
1938 int first = 1;
1940 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that
1941 much at a time. */
1942 if (REG_P (op0) || GET_CODE (op0) == SUBREG)
1943 unit = BITS_PER_WORD;
1944 else
1945 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD);
1947 while (bitsdone < bitsize)
1949 unsigned HOST_WIDE_INT thissize;
1950 rtx part, word;
1951 unsigned HOST_WIDE_INT thispos;
1952 unsigned HOST_WIDE_INT offset;
1954 offset = (bitpos + bitsdone) / unit;
1955 thispos = (bitpos + bitsdone) % unit;
1957 /* THISSIZE must not overrun a word boundary. Otherwise,
1958 extract_fixed_bit_field will call us again, and we will mutually
1959 recurse forever. */
1960 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD);
1961 thissize = MIN (thissize, unit - thispos);
1963 /* If OP0 is a register, then handle OFFSET here.
1965 When handling multiword bitfields, extract_bit_field may pass
1966 down a word_mode SUBREG of a larger REG for a bitfield that actually
1967 crosses a word boundary. Thus, for a SUBREG, we must find
1968 the current word starting from the base register. */
1969 if (GET_CODE (op0) == SUBREG)
1971 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset;
1972 word = operand_subword_force (SUBREG_REG (op0), word_offset,
1973 GET_MODE (SUBREG_REG (op0)));
1974 offset = 0;
1976 else if (REG_P (op0))
1978 word = operand_subword_force (op0, offset, GET_MODE (op0));
1979 offset = 0;
1981 else
1982 word = op0;
1984 /* Extract the parts in bit-counting order,
1985 whose meaning is determined by BYTES_PER_UNIT.
1986 OFFSET is in UNITs, and UNIT is in bits. */
1987 part = extract_fixed_bit_field (word_mode, word, thissize,
1988 offset * unit + thispos, 0, 1);
1989 bitsdone += thissize;
1991 /* Shift this part into place for the result. */
1992 if (BYTES_BIG_ENDIAN)
1994 if (bitsize != bitsdone)
1995 part = expand_shift (LSHIFT_EXPR, word_mode, part,
1996 bitsize - bitsdone, 0, 1);
1998 else
2000 if (bitsdone != thissize)
2001 part = expand_shift (LSHIFT_EXPR, word_mode, part,
2002 bitsdone - thissize, 0, 1);
2005 if (first)
2006 result = part;
2007 else
2008 /* Combine the parts with bitwise or. This works
2009 because we extracted each part as an unsigned bit field. */
2010 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1,
2011 OPTAB_LIB_WIDEN);
2013 first = 0;
2016 /* Unsigned bit field: we are done. */
2017 if (unsignedp)
2018 return result;
2019 /* Signed bit field: sign-extend with two arithmetic shifts. */
2020 result = expand_shift (LSHIFT_EXPR, word_mode, result,
2021 BITS_PER_WORD - bitsize, NULL_RTX, 0);
2022 return expand_shift (RSHIFT_EXPR, word_mode, result,
2023 BITS_PER_WORD - bitsize, NULL_RTX, 0);
2026 /* Try to read the low bits of SRC as an rvalue of mode MODE, preserving
2027 the bit pattern. SRC_MODE is the mode of SRC; if this is smaller than
2028 MODE, fill the upper bits with zeros. Fail if the layout of either
2029 mode is unknown (as for CC modes) or if the extraction would involve
2030 unprofitable mode punning. Return the value on success, otherwise
2031 return null.
2033 This is different from gen_lowpart* in these respects:
2035 - the returned value must always be considered an rvalue
2037 - when MODE is wider than SRC_MODE, the extraction involves
2038 a zero extension
2040 - when MODE is smaller than SRC_MODE, the extraction involves
2041 a truncation (and is thus subject to TRULY_NOOP_TRUNCATION).
2043 In other words, this routine performs a computation, whereas the
2044 gen_lowpart* routines are conceptually lvalue or rvalue subreg
2045 operations. */
2048 extract_low_bits (enum machine_mode mode, enum machine_mode src_mode, rtx src)
2050 enum machine_mode int_mode, src_int_mode;
2052 if (mode == src_mode)
2053 return src;
2055 if (CONSTANT_P (src))
2057 /* simplify_gen_subreg can't be used here, as if simplify_subreg
2058 fails, it will happily create (subreg (symbol_ref)) or similar
2059 invalid SUBREGs. */
2060 unsigned int byte = subreg_lowpart_offset (mode, src_mode);
2061 rtx ret = simplify_subreg (mode, src, src_mode, byte);
2062 if (ret)
2063 return ret;
2065 if (GET_MODE (src) == VOIDmode
2066 || !validate_subreg (mode, src_mode, src, byte))
2067 return NULL_RTX;
2069 src = force_reg (GET_MODE (src), src);
2070 return gen_rtx_SUBREG (mode, src, byte);
2073 if (GET_MODE_CLASS (mode) == MODE_CC || GET_MODE_CLASS (src_mode) == MODE_CC)
2074 return NULL_RTX;
2076 if (GET_MODE_BITSIZE (mode) == GET_MODE_BITSIZE (src_mode)
2077 && MODES_TIEABLE_P (mode, src_mode))
2079 rtx x = gen_lowpart_common (mode, src);
2080 if (x)
2081 return x;
2084 src_int_mode = int_mode_for_mode (src_mode);
2085 int_mode = int_mode_for_mode (mode);
2086 if (src_int_mode == BLKmode || int_mode == BLKmode)
2087 return NULL_RTX;
2089 if (!MODES_TIEABLE_P (src_int_mode, src_mode))
2090 return NULL_RTX;
2091 if (!MODES_TIEABLE_P (int_mode, mode))
2092 return NULL_RTX;
2094 src = gen_lowpart (src_int_mode, src);
2095 src = convert_modes (int_mode, src_int_mode, src, true);
2096 src = gen_lowpart (mode, src);
2097 return src;
2100 /* Add INC into TARGET. */
2102 void
2103 expand_inc (rtx target, rtx inc)
2105 rtx value = expand_binop (GET_MODE (target), add_optab,
2106 target, inc,
2107 target, 0, OPTAB_LIB_WIDEN);
2108 if (value != target)
2109 emit_move_insn (target, value);
2112 /* Subtract DEC from TARGET. */
2114 void
2115 expand_dec (rtx target, rtx dec)
2117 rtx value = expand_binop (GET_MODE (target), sub_optab,
2118 target, dec,
2119 target, 0, OPTAB_LIB_WIDEN);
2120 if (value != target)
2121 emit_move_insn (target, value);
2124 /* Output a shift instruction for expression code CODE,
2125 with SHIFTED being the rtx for the value to shift,
2126 and AMOUNT the rtx for the amount to shift by.
2127 Store the result in the rtx TARGET, if that is convenient.
2128 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2129 Return the rtx for where the value is. */
2131 static rtx
2132 expand_shift_1 (enum tree_code code, enum machine_mode mode, rtx shifted,
2133 rtx amount, rtx target, int unsignedp)
2135 rtx op1, temp = 0;
2136 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR);
2137 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR);
2138 optab lshift_optab = ashl_optab;
2139 optab rshift_arith_optab = ashr_optab;
2140 optab rshift_uns_optab = lshr_optab;
2141 optab lrotate_optab = rotl_optab;
2142 optab rrotate_optab = rotr_optab;
2143 enum machine_mode op1_mode;
2144 int attempt;
2145 bool speed = optimize_insn_for_speed_p ();
2147 op1 = amount;
2148 op1_mode = GET_MODE (op1);
2150 /* Determine whether the shift/rotate amount is a vector, or scalar. If the
2151 shift amount is a vector, use the vector/vector shift patterns. */
2152 if (VECTOR_MODE_P (mode) && VECTOR_MODE_P (op1_mode))
2154 lshift_optab = vashl_optab;
2155 rshift_arith_optab = vashr_optab;
2156 rshift_uns_optab = vlshr_optab;
2157 lrotate_optab = vrotl_optab;
2158 rrotate_optab = vrotr_optab;
2161 /* Previously detected shift-counts computed by NEGATE_EXPR
2162 and shifted in the other direction; but that does not work
2163 on all machines. */
2165 if (SHIFT_COUNT_TRUNCATED)
2167 if (CONST_INT_P (op1)
2168 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >=
2169 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode)))
2170 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1)
2171 % GET_MODE_BITSIZE (mode));
2172 else if (GET_CODE (op1) == SUBREG
2173 && subreg_lowpart_p (op1)
2174 && SCALAR_INT_MODE_P (GET_MODE (SUBREG_REG (op1)))
2175 && SCALAR_INT_MODE_P (GET_MODE (op1)))
2176 op1 = SUBREG_REG (op1);
2179 /* Canonicalize rotates by constant amount. If op1 is bitsize / 2,
2180 prefer left rotation, if op1 is from bitsize / 2 + 1 to
2181 bitsize - 1, use other direction of rotate with 1 .. bitsize / 2 - 1
2182 amount instead. */
2183 if (rotate
2184 && CONST_INT_P (op1)
2185 && IN_RANGE (INTVAL (op1), GET_MODE_BITSIZE (mode) / 2 + left,
2186 GET_MODE_BITSIZE (mode) - 1))
2188 op1 = GEN_INT (GET_MODE_BITSIZE (mode) - INTVAL (op1));
2189 left = !left;
2190 code = left ? LROTATE_EXPR : RROTATE_EXPR;
2193 if (op1 == const0_rtx)
2194 return shifted;
2196 /* Check whether its cheaper to implement a left shift by a constant
2197 bit count by a sequence of additions. */
2198 if (code == LSHIFT_EXPR
2199 && CONST_INT_P (op1)
2200 && INTVAL (op1) > 0
2201 && INTVAL (op1) < GET_MODE_PRECISION (mode)
2202 && INTVAL (op1) < MAX_BITS_PER_WORD
2203 && (shift_cost (speed, mode, INTVAL (op1))
2204 > INTVAL (op1) * add_cost (speed, mode))
2205 && shift_cost (speed, mode, INTVAL (op1)) != MAX_COST)
2207 int i;
2208 for (i = 0; i < INTVAL (op1); i++)
2210 temp = force_reg (mode, shifted);
2211 shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX,
2212 unsignedp, OPTAB_LIB_WIDEN);
2214 return shifted;
2217 for (attempt = 0; temp == 0 && attempt < 3; attempt++)
2219 enum optab_methods methods;
2221 if (attempt == 0)
2222 methods = OPTAB_DIRECT;
2223 else if (attempt == 1)
2224 methods = OPTAB_WIDEN;
2225 else
2226 methods = OPTAB_LIB_WIDEN;
2228 if (rotate)
2230 /* Widening does not work for rotation. */
2231 if (methods == OPTAB_WIDEN)
2232 continue;
2233 else if (methods == OPTAB_LIB_WIDEN)
2235 /* If we have been unable to open-code this by a rotation,
2236 do it as the IOR of two shifts. I.e., to rotate A
2237 by N bits, compute
2238 (A << N) | ((unsigned) A >> ((-N) & (C - 1)))
2239 where C is the bitsize of A.
2241 It is theoretically possible that the target machine might
2242 not be able to perform either shift and hence we would
2243 be making two libcalls rather than just the one for the
2244 shift (similarly if IOR could not be done). We will allow
2245 this extremely unlikely lossage to avoid complicating the
2246 code below. */
2248 rtx subtarget = target == shifted ? 0 : target;
2249 rtx new_amount, other_amount;
2250 rtx temp1;
2252 new_amount = op1;
2253 if (op1 == const0_rtx)
2254 return shifted;
2255 else if (CONST_INT_P (op1))
2256 other_amount = GEN_INT (GET_MODE_BITSIZE (mode)
2257 - INTVAL (op1));
2258 else
2260 other_amount
2261 = simplify_gen_unary (NEG, GET_MODE (op1),
2262 op1, GET_MODE (op1));
2263 HOST_WIDE_INT mask = GET_MODE_PRECISION (mode) - 1;
2264 other_amount
2265 = simplify_gen_binary (AND, GET_MODE (op1), other_amount,
2266 gen_int_mode (mask, GET_MODE (op1)));
2269 shifted = force_reg (mode, shifted);
2271 temp = expand_shift_1 (left ? LSHIFT_EXPR : RSHIFT_EXPR,
2272 mode, shifted, new_amount, 0, 1);
2273 temp1 = expand_shift_1 (left ? RSHIFT_EXPR : LSHIFT_EXPR,
2274 mode, shifted, other_amount,
2275 subtarget, 1);
2276 return expand_binop (mode, ior_optab, temp, temp1, target,
2277 unsignedp, methods);
2280 temp = expand_binop (mode,
2281 left ? lrotate_optab : rrotate_optab,
2282 shifted, op1, target, unsignedp, methods);
2284 else if (unsignedp)
2285 temp = expand_binop (mode,
2286 left ? lshift_optab : rshift_uns_optab,
2287 shifted, op1, target, unsignedp, methods);
2289 /* Do arithmetic shifts.
2290 Also, if we are going to widen the operand, we can just as well
2291 use an arithmetic right-shift instead of a logical one. */
2292 if (temp == 0 && ! rotate
2293 && (! unsignedp || (! left && methods == OPTAB_WIDEN)))
2295 enum optab_methods methods1 = methods;
2297 /* If trying to widen a log shift to an arithmetic shift,
2298 don't accept an arithmetic shift of the same size. */
2299 if (unsignedp)
2300 methods1 = OPTAB_MUST_WIDEN;
2302 /* Arithmetic shift */
2304 temp = expand_binop (mode,
2305 left ? lshift_optab : rshift_arith_optab,
2306 shifted, op1, target, unsignedp, methods1);
2309 /* We used to try extzv here for logical right shifts, but that was
2310 only useful for one machine, the VAX, and caused poor code
2311 generation there for lshrdi3, so the code was deleted and a
2312 define_expand for lshrsi3 was added to vax.md. */
2315 gcc_assert (temp);
2316 return temp;
2319 /* Output a shift instruction for expression code CODE,
2320 with SHIFTED being the rtx for the value to shift,
2321 and AMOUNT the amount to shift by.
2322 Store the result in the rtx TARGET, if that is convenient.
2323 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2324 Return the rtx for where the value is. */
2327 expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
2328 int amount, rtx target, int unsignedp)
2330 return expand_shift_1 (code, mode,
2331 shifted, GEN_INT (amount), target, unsignedp);
2334 /* Output a shift instruction for expression code CODE,
2335 with SHIFTED being the rtx for the value to shift,
2336 and AMOUNT the tree for the amount to shift by.
2337 Store the result in the rtx TARGET, if that is convenient.
2338 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic.
2339 Return the rtx for where the value is. */
2342 expand_variable_shift (enum tree_code code, enum machine_mode mode, rtx shifted,
2343 tree amount, rtx target, int unsignedp)
2345 return expand_shift_1 (code, mode,
2346 shifted, expand_normal (amount), target, unsignedp);
2350 /* Indicates the type of fixup needed after a constant multiplication.
2351 BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that
2352 the result should be negated, and ADD_VARIANT means that the
2353 multiplicand should be added to the result. */
2354 enum mult_variant {basic_variant, negate_variant, add_variant};
2356 static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT,
2357 const struct mult_cost *, enum machine_mode mode);
2358 static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT,
2359 struct algorithm *, enum mult_variant *, int);
2360 static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx,
2361 const struct algorithm *, enum mult_variant);
2362 static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int);
2363 static rtx extract_high_half (enum machine_mode, rtx);
2364 static rtx expmed_mult_highpart (enum machine_mode, rtx, rtx, rtx, int, int);
2365 static rtx expmed_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx,
2366 int, int);
2367 /* Compute and return the best algorithm for multiplying by T.
2368 The algorithm must cost less than cost_limit
2369 If retval.cost >= COST_LIMIT, no algorithm was found and all
2370 other field of the returned struct are undefined.
2371 MODE is the machine mode of the multiplication. */
2373 static void
2374 synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t,
2375 const struct mult_cost *cost_limit, enum machine_mode mode)
2377 int m;
2378 struct algorithm *alg_in, *best_alg;
2379 struct mult_cost best_cost;
2380 struct mult_cost new_limit;
2381 int op_cost, op_latency;
2382 unsigned HOST_WIDE_INT orig_t = t;
2383 unsigned HOST_WIDE_INT q;
2384 int maxm, hash_index;
2385 bool cache_hit = false;
2386 enum alg_code cache_alg = alg_zero;
2387 bool speed = optimize_insn_for_speed_p ();
2388 enum machine_mode imode;
2389 struct alg_hash_entry *entry_ptr;
2391 /* Indicate that no algorithm is yet found. If no algorithm
2392 is found, this value will be returned and indicate failure. */
2393 alg_out->cost.cost = cost_limit->cost + 1;
2394 alg_out->cost.latency = cost_limit->latency + 1;
2396 if (cost_limit->cost < 0
2397 || (cost_limit->cost == 0 && cost_limit->latency <= 0))
2398 return;
2400 /* Be prepared for vector modes. */
2401 imode = GET_MODE_INNER (mode);
2402 if (imode == VOIDmode)
2403 imode = mode;
2405 maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (imode));
2407 /* Restrict the bits of "t" to the multiplication's mode. */
2408 t &= GET_MODE_MASK (imode);
2410 /* t == 1 can be done in zero cost. */
2411 if (t == 1)
2413 alg_out->ops = 1;
2414 alg_out->cost.cost = 0;
2415 alg_out->cost.latency = 0;
2416 alg_out->op[0] = alg_m;
2417 return;
2420 /* t == 0 sometimes has a cost. If it does and it exceeds our limit,
2421 fail now. */
2422 if (t == 0)
2424 if (MULT_COST_LESS (cost_limit, zero_cost (speed)))
2425 return;
2426 else
2428 alg_out->ops = 1;
2429 alg_out->cost.cost = zero_cost (speed);
2430 alg_out->cost.latency = zero_cost (speed);
2431 alg_out->op[0] = alg_zero;
2432 return;
2436 /* We'll be needing a couple extra algorithm structures now. */
2438 alg_in = XALLOCA (struct algorithm);
2439 best_alg = XALLOCA (struct algorithm);
2440 best_cost = *cost_limit;
2442 /* Compute the hash index. */
2443 hash_index = (t ^ (unsigned int) mode ^ (speed * 256)) % NUM_ALG_HASH_ENTRIES;
2445 /* See if we already know what to do for T. */
2446 entry_ptr = alg_hash_entry_ptr (hash_index);
2447 if (entry_ptr->t == t
2448 && entry_ptr->mode == mode
2449 && entry_ptr->mode == mode
2450 && entry_ptr->speed == speed
2451 && entry_ptr->alg != alg_unknown)
2453 cache_alg = entry_ptr->alg;
2455 if (cache_alg == alg_impossible)
2457 /* The cache tells us that it's impossible to synthesize
2458 multiplication by T within entry_ptr->cost. */
2459 if (!CHEAPER_MULT_COST (&entry_ptr->cost, cost_limit))
2460 /* COST_LIMIT is at least as restrictive as the one
2461 recorded in the hash table, in which case we have no
2462 hope of synthesizing a multiplication. Just
2463 return. */
2464 return;
2466 /* If we get here, COST_LIMIT is less restrictive than the
2467 one recorded in the hash table, so we may be able to
2468 synthesize a multiplication. Proceed as if we didn't
2469 have the cache entry. */
2471 else
2473 if (CHEAPER_MULT_COST (cost_limit, &entry_ptr->cost))
2474 /* The cached algorithm shows that this multiplication
2475 requires more cost than COST_LIMIT. Just return. This
2476 way, we don't clobber this cache entry with
2477 alg_impossible but retain useful information. */
2478 return;
2480 cache_hit = true;
2482 switch (cache_alg)
2484 case alg_shift:
2485 goto do_alg_shift;
2487 case alg_add_t_m2:
2488 case alg_sub_t_m2:
2489 goto do_alg_addsub_t_m2;
2491 case alg_add_factor:
2492 case alg_sub_factor:
2493 goto do_alg_addsub_factor;
2495 case alg_add_t2_m:
2496 goto do_alg_add_t2_m;
2498 case alg_sub_t2_m:
2499 goto do_alg_sub_t2_m;
2501 default:
2502 gcc_unreachable ();
2507 /* If we have a group of zero bits at the low-order part of T, try
2508 multiplying by the remaining bits and then doing a shift. */
2510 if ((t & 1) == 0)
2512 do_alg_shift:
2513 m = floor_log2 (t & -t); /* m = number of low zero bits */
2514 if (m < maxm)
2516 q = t >> m;
2517 /* The function expand_shift will choose between a shift and
2518 a sequence of additions, so the observed cost is given as
2519 MIN (m * add_cost(speed, mode), shift_cost(speed, mode, m)). */
2520 op_cost = m * add_cost (speed, mode);
2521 if (shift_cost (speed, mode, m) < op_cost)
2522 op_cost = shift_cost (speed, mode, m);
2523 new_limit.cost = best_cost.cost - op_cost;
2524 new_limit.latency = best_cost.latency - op_cost;
2525 synth_mult (alg_in, q, &new_limit, mode);
2527 alg_in->cost.cost += op_cost;
2528 alg_in->cost.latency += op_cost;
2529 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2531 struct algorithm *x;
2532 best_cost = alg_in->cost;
2533 x = alg_in, alg_in = best_alg, best_alg = x;
2534 best_alg->log[best_alg->ops] = m;
2535 best_alg->op[best_alg->ops] = alg_shift;
2538 /* See if treating ORIG_T as a signed number yields a better
2539 sequence. Try this sequence only for a negative ORIG_T
2540 as it would be useless for a non-negative ORIG_T. */
2541 if ((HOST_WIDE_INT) orig_t < 0)
2543 /* Shift ORIG_T as follows because a right shift of a
2544 negative-valued signed type is implementation
2545 defined. */
2546 q = ~(~orig_t >> m);
2547 /* The function expand_shift will choose between a shift
2548 and a sequence of additions, so the observed cost is
2549 given as MIN (m * add_cost(speed, mode),
2550 shift_cost(speed, mode, m)). */
2551 op_cost = m * add_cost (speed, mode);
2552 if (shift_cost (speed, mode, m) < op_cost)
2553 op_cost = shift_cost (speed, mode, m);
2554 new_limit.cost = best_cost.cost - op_cost;
2555 new_limit.latency = best_cost.latency - op_cost;
2556 synth_mult (alg_in, q, &new_limit, mode);
2558 alg_in->cost.cost += op_cost;
2559 alg_in->cost.latency += op_cost;
2560 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2562 struct algorithm *x;
2563 best_cost = alg_in->cost;
2564 x = alg_in, alg_in = best_alg, best_alg = x;
2565 best_alg->log[best_alg->ops] = m;
2566 best_alg->op[best_alg->ops] = alg_shift;
2570 if (cache_hit)
2571 goto done;
2574 /* If we have an odd number, add or subtract one. */
2575 if ((t & 1) != 0)
2577 unsigned HOST_WIDE_INT w;
2579 do_alg_addsub_t_m2:
2580 for (w = 1; (w & t) != 0; w <<= 1)
2582 /* If T was -1, then W will be zero after the loop. This is another
2583 case where T ends with ...111. Handling this with (T + 1) and
2584 subtract 1 produces slightly better code and results in algorithm
2585 selection much faster than treating it like the ...0111 case
2586 below. */
2587 if (w == 0
2588 || (w > 2
2589 /* Reject the case where t is 3.
2590 Thus we prefer addition in that case. */
2591 && t != 3))
2593 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */
2595 op_cost = add_cost (speed, mode);
2596 new_limit.cost = best_cost.cost - op_cost;
2597 new_limit.latency = best_cost.latency - op_cost;
2598 synth_mult (alg_in, t + 1, &new_limit, mode);
2600 alg_in->cost.cost += op_cost;
2601 alg_in->cost.latency += op_cost;
2602 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2604 struct algorithm *x;
2605 best_cost = alg_in->cost;
2606 x = alg_in, alg_in = best_alg, best_alg = x;
2607 best_alg->log[best_alg->ops] = 0;
2608 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2611 else
2613 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */
2615 op_cost = add_cost (speed, mode);
2616 new_limit.cost = best_cost.cost - op_cost;
2617 new_limit.latency = best_cost.latency - op_cost;
2618 synth_mult (alg_in, t - 1, &new_limit, mode);
2620 alg_in->cost.cost += op_cost;
2621 alg_in->cost.latency += op_cost;
2622 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2624 struct algorithm *x;
2625 best_cost = alg_in->cost;
2626 x = alg_in, alg_in = best_alg, best_alg = x;
2627 best_alg->log[best_alg->ops] = 0;
2628 best_alg->op[best_alg->ops] = alg_add_t_m2;
2632 /* We may be able to calculate a * -7, a * -15, a * -31, etc
2633 quickly with a - a * n for some appropriate constant n. */
2634 m = exact_log2 (-orig_t + 1);
2635 if (m >= 0 && m < maxm)
2637 op_cost = shiftsub1_cost (speed, mode, m);
2638 new_limit.cost = best_cost.cost - op_cost;
2639 new_limit.latency = best_cost.latency - op_cost;
2640 synth_mult (alg_in, (unsigned HOST_WIDE_INT) (-orig_t + 1) >> m,
2641 &new_limit, mode);
2643 alg_in->cost.cost += op_cost;
2644 alg_in->cost.latency += op_cost;
2645 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2647 struct algorithm *x;
2648 best_cost = alg_in->cost;
2649 x = alg_in, alg_in = best_alg, best_alg = x;
2650 best_alg->log[best_alg->ops] = m;
2651 best_alg->op[best_alg->ops] = alg_sub_t_m2;
2655 if (cache_hit)
2656 goto done;
2659 /* Look for factors of t of the form
2660 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)).
2661 If we find such a factor, we can multiply by t using an algorithm that
2662 multiplies by q, shift the result by m and add/subtract it to itself.
2664 We search for large factors first and loop down, even if large factors
2665 are less probable than small; if we find a large factor we will find a
2666 good sequence quickly, and therefore be able to prune (by decreasing
2667 COST_LIMIT) the search. */
2669 do_alg_addsub_factor:
2670 for (m = floor_log2 (t - 1); m >= 2; m--)
2672 unsigned HOST_WIDE_INT d;
2674 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1;
2675 if (t % d == 0 && t > d && m < maxm
2676 && (!cache_hit || cache_alg == alg_add_factor))
2678 /* If the target has a cheap shift-and-add instruction use
2679 that in preference to a shift insn followed by an add insn.
2680 Assume that the shift-and-add is "atomic" with a latency
2681 equal to its cost, otherwise assume that on superscalar
2682 hardware the shift may be executed concurrently with the
2683 earlier steps in the algorithm. */
2684 op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2685 if (shiftadd_cost (speed, mode, m) < op_cost)
2687 op_cost = shiftadd_cost (speed, mode, m);
2688 op_latency = op_cost;
2690 else
2691 op_latency = add_cost (speed, mode);
2693 new_limit.cost = best_cost.cost - op_cost;
2694 new_limit.latency = best_cost.latency - op_latency;
2695 synth_mult (alg_in, t / d, &new_limit, mode);
2697 alg_in->cost.cost += op_cost;
2698 alg_in->cost.latency += op_latency;
2699 if (alg_in->cost.latency < op_cost)
2700 alg_in->cost.latency = op_cost;
2701 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2703 struct algorithm *x;
2704 best_cost = alg_in->cost;
2705 x = alg_in, alg_in = best_alg, best_alg = x;
2706 best_alg->log[best_alg->ops] = m;
2707 best_alg->op[best_alg->ops] = alg_add_factor;
2709 /* Other factors will have been taken care of in the recursion. */
2710 break;
2713 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1;
2714 if (t % d == 0 && t > d && m < maxm
2715 && (!cache_hit || cache_alg == alg_sub_factor))
2717 /* If the target has a cheap shift-and-subtract insn use
2718 that in preference to a shift insn followed by a sub insn.
2719 Assume that the shift-and-sub is "atomic" with a latency
2720 equal to it's cost, otherwise assume that on superscalar
2721 hardware the shift may be executed concurrently with the
2722 earlier steps in the algorithm. */
2723 op_cost = add_cost (speed, mode) + shift_cost (speed, mode, m);
2724 if (shiftsub0_cost (speed, mode, m) < op_cost)
2726 op_cost = shiftsub0_cost (speed, mode, m);
2727 op_latency = op_cost;
2729 else
2730 op_latency = add_cost (speed, mode);
2732 new_limit.cost = best_cost.cost - op_cost;
2733 new_limit.latency = best_cost.latency - op_latency;
2734 synth_mult (alg_in, t / d, &new_limit, mode);
2736 alg_in->cost.cost += op_cost;
2737 alg_in->cost.latency += op_latency;
2738 if (alg_in->cost.latency < op_cost)
2739 alg_in->cost.latency = op_cost;
2740 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2742 struct algorithm *x;
2743 best_cost = alg_in->cost;
2744 x = alg_in, alg_in = best_alg, best_alg = x;
2745 best_alg->log[best_alg->ops] = m;
2746 best_alg->op[best_alg->ops] = alg_sub_factor;
2748 break;
2751 if (cache_hit)
2752 goto done;
2754 /* Try shift-and-add (load effective address) instructions,
2755 i.e. do a*3, a*5, a*9. */
2756 if ((t & 1) != 0)
2758 do_alg_add_t2_m:
2759 q = t - 1;
2760 q = q & -q;
2761 m = exact_log2 (q);
2762 if (m >= 0 && m < maxm)
2764 op_cost = shiftadd_cost (speed, mode, m);
2765 new_limit.cost = best_cost.cost - op_cost;
2766 new_limit.latency = best_cost.latency - op_cost;
2767 synth_mult (alg_in, (t - 1) >> m, &new_limit, mode);
2769 alg_in->cost.cost += op_cost;
2770 alg_in->cost.latency += op_cost;
2771 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2773 struct algorithm *x;
2774 best_cost = alg_in->cost;
2775 x = alg_in, alg_in = best_alg, best_alg = x;
2776 best_alg->log[best_alg->ops] = m;
2777 best_alg->op[best_alg->ops] = alg_add_t2_m;
2780 if (cache_hit)
2781 goto done;
2783 do_alg_sub_t2_m:
2784 q = t + 1;
2785 q = q & -q;
2786 m = exact_log2 (q);
2787 if (m >= 0 && m < maxm)
2789 op_cost = shiftsub0_cost (speed, mode, m);
2790 new_limit.cost = best_cost.cost - op_cost;
2791 new_limit.latency = best_cost.latency - op_cost;
2792 synth_mult (alg_in, (t + 1) >> m, &new_limit, mode);
2794 alg_in->cost.cost += op_cost;
2795 alg_in->cost.latency += op_cost;
2796 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost))
2798 struct algorithm *x;
2799 best_cost = alg_in->cost;
2800 x = alg_in, alg_in = best_alg, best_alg = x;
2801 best_alg->log[best_alg->ops] = m;
2802 best_alg->op[best_alg->ops] = alg_sub_t2_m;
2805 if (cache_hit)
2806 goto done;
2809 done:
2810 /* If best_cost has not decreased, we have not found any algorithm. */
2811 if (!CHEAPER_MULT_COST (&best_cost, cost_limit))
2813 /* We failed to find an algorithm. Record alg_impossible for
2814 this case (that is, <T, MODE, COST_LIMIT>) so that next time
2815 we are asked to find an algorithm for T within the same or
2816 lower COST_LIMIT, we can immediately return to the
2817 caller. */
2818 entry_ptr->t = t;
2819 entry_ptr->mode = mode;
2820 entry_ptr->speed = speed;
2821 entry_ptr->alg = alg_impossible;
2822 entry_ptr->cost = *cost_limit;
2823 return;
2826 /* Cache the result. */
2827 if (!cache_hit)
2829 entry_ptr->t = t;
2830 entry_ptr->mode = mode;
2831 entry_ptr->speed = speed;
2832 entry_ptr->alg = best_alg->op[best_alg->ops];
2833 entry_ptr->cost.cost = best_cost.cost;
2834 entry_ptr->cost.latency = best_cost.latency;
2837 /* If we are getting a too long sequence for `struct algorithm'
2838 to record, make this search fail. */
2839 if (best_alg->ops == MAX_BITS_PER_WORD)
2840 return;
2842 /* Copy the algorithm from temporary space to the space at alg_out.
2843 We avoid using structure assignment because the majority of
2844 best_alg is normally undefined, and this is a critical function. */
2845 alg_out->ops = best_alg->ops + 1;
2846 alg_out->cost = best_cost;
2847 memcpy (alg_out->op, best_alg->op,
2848 alg_out->ops * sizeof *alg_out->op);
2849 memcpy (alg_out->log, best_alg->log,
2850 alg_out->ops * sizeof *alg_out->log);
2853 /* Find the cheapest way of multiplying a value of mode MODE by VAL.
2854 Try three variations:
2856 - a shift/add sequence based on VAL itself
2857 - a shift/add sequence based on -VAL, followed by a negation
2858 - a shift/add sequence based on VAL - 1, followed by an addition.
2860 Return true if the cheapest of these cost less than MULT_COST,
2861 describing the algorithm in *ALG and final fixup in *VARIANT. */
2863 static bool
2864 choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val,
2865 struct algorithm *alg, enum mult_variant *variant,
2866 int mult_cost)
2868 struct algorithm alg2;
2869 struct mult_cost limit;
2870 int op_cost;
2871 bool speed = optimize_insn_for_speed_p ();
2873 /* Fail quickly for impossible bounds. */
2874 if (mult_cost < 0)
2875 return false;
2877 /* Ensure that mult_cost provides a reasonable upper bound.
2878 Any constant multiplication can be performed with less
2879 than 2 * bits additions. */
2880 op_cost = 2 * GET_MODE_UNIT_BITSIZE (mode) * add_cost (speed, mode);
2881 if (mult_cost > op_cost)
2882 mult_cost = op_cost;
2884 *variant = basic_variant;
2885 limit.cost = mult_cost;
2886 limit.latency = mult_cost;
2887 synth_mult (alg, val, &limit, mode);
2889 /* This works only if the inverted value actually fits in an
2890 `unsigned int' */
2891 if (HOST_BITS_PER_INT >= GET_MODE_UNIT_BITSIZE (mode))
2893 op_cost = neg_cost (speed, mode);
2894 if (MULT_COST_LESS (&alg->cost, mult_cost))
2896 limit.cost = alg->cost.cost - op_cost;
2897 limit.latency = alg->cost.latency - op_cost;
2899 else
2901 limit.cost = mult_cost - op_cost;
2902 limit.latency = mult_cost - op_cost;
2905 synth_mult (&alg2, -val, &limit, mode);
2906 alg2.cost.cost += op_cost;
2907 alg2.cost.latency += op_cost;
2908 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2909 *alg = alg2, *variant = negate_variant;
2912 /* This proves very useful for division-by-constant. */
2913 op_cost = add_cost (speed, mode);
2914 if (MULT_COST_LESS (&alg->cost, mult_cost))
2916 limit.cost = alg->cost.cost - op_cost;
2917 limit.latency = alg->cost.latency - op_cost;
2919 else
2921 limit.cost = mult_cost - op_cost;
2922 limit.latency = mult_cost - op_cost;
2925 synth_mult (&alg2, val - 1, &limit, mode);
2926 alg2.cost.cost += op_cost;
2927 alg2.cost.latency += op_cost;
2928 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost))
2929 *alg = alg2, *variant = add_variant;
2931 return MULT_COST_LESS (&alg->cost, mult_cost);
2934 /* A subroutine of expand_mult, used for constant multiplications.
2935 Multiply OP0 by VAL in mode MODE, storing the result in TARGET if
2936 convenient. Use the shift/add sequence described by ALG and apply
2937 the final fixup specified by VARIANT. */
2939 static rtx
2940 expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val,
2941 rtx target, const struct algorithm *alg,
2942 enum mult_variant variant)
2944 HOST_WIDE_INT val_so_far;
2945 rtx insn, accum, tem;
2946 int opno;
2947 enum machine_mode nmode;
2949 /* Avoid referencing memory over and over and invalid sharing
2950 on SUBREGs. */
2951 op0 = force_reg (mode, op0);
2953 /* ACCUM starts out either as OP0 or as a zero, depending on
2954 the first operation. */
2956 if (alg->op[0] == alg_zero)
2958 accum = copy_to_mode_reg (mode, CONST0_RTX (mode));
2959 val_so_far = 0;
2961 else if (alg->op[0] == alg_m)
2963 accum = copy_to_mode_reg (mode, op0);
2964 val_so_far = 1;
2966 else
2967 gcc_unreachable ();
2969 for (opno = 1; opno < alg->ops; opno++)
2971 int log = alg->log[opno];
2972 rtx shift_subtarget = optimize ? 0 : accum;
2973 rtx add_target
2974 = (opno == alg->ops - 1 && target != 0 && variant != add_variant
2975 && !optimize)
2976 ? target : 0;
2977 rtx accum_target = optimize ? 0 : accum;
2978 rtx accum_inner;
2980 switch (alg->op[opno])
2982 case alg_shift:
2983 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
2984 /* REG_EQUAL note will be attached to the following insn. */
2985 emit_move_insn (accum, tem);
2986 val_so_far <<= log;
2987 break;
2989 case alg_add_t_m2:
2990 tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
2991 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
2992 add_target ? add_target : accum_target);
2993 val_so_far += (HOST_WIDE_INT) 1 << log;
2994 break;
2996 case alg_sub_t_m2:
2997 tem = expand_shift (LSHIFT_EXPR, mode, op0, log, NULL_RTX, 0);
2998 accum = force_operand (gen_rtx_MINUS (mode, accum, tem),
2999 add_target ? add_target : accum_target);
3000 val_so_far -= (HOST_WIDE_INT) 1 << log;
3001 break;
3003 case alg_add_t2_m:
3004 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3005 log, shift_subtarget, 0);
3006 accum = force_operand (gen_rtx_PLUS (mode, accum, op0),
3007 add_target ? add_target : accum_target);
3008 val_so_far = (val_so_far << log) + 1;
3009 break;
3011 case alg_sub_t2_m:
3012 accum = expand_shift (LSHIFT_EXPR, mode, accum,
3013 log, shift_subtarget, 0);
3014 accum = force_operand (gen_rtx_MINUS (mode, accum, op0),
3015 add_target ? add_target : accum_target);
3016 val_so_far = (val_so_far << log) - 1;
3017 break;
3019 case alg_add_factor:
3020 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3021 accum = force_operand (gen_rtx_PLUS (mode, accum, tem),
3022 add_target ? add_target : accum_target);
3023 val_so_far += val_so_far << log;
3024 break;
3026 case alg_sub_factor:
3027 tem = expand_shift (LSHIFT_EXPR, mode, accum, log, NULL_RTX, 0);
3028 accum = force_operand (gen_rtx_MINUS (mode, tem, accum),
3029 (add_target
3030 ? add_target : (optimize ? 0 : tem)));
3031 val_so_far = (val_so_far << log) - val_so_far;
3032 break;
3034 default:
3035 gcc_unreachable ();
3038 if (SCALAR_INT_MODE_P (mode))
3040 /* Write a REG_EQUAL note on the last insn so that we can cse
3041 multiplication sequences. Note that if ACCUM is a SUBREG,
3042 we've set the inner register and must properly indicate that. */
3043 tem = op0, nmode = mode;
3044 accum_inner = accum;
3045 if (GET_CODE (accum) == SUBREG)
3047 accum_inner = SUBREG_REG (accum);
3048 nmode = GET_MODE (accum_inner);
3049 tem = gen_lowpart (nmode, op0);
3052 insn = get_last_insn ();
3053 set_dst_reg_note (insn, REG_EQUAL,
3054 gen_rtx_MULT (nmode, tem,
3055 gen_int_mode (val_so_far, nmode)),
3056 accum_inner);
3060 if (variant == negate_variant)
3062 val_so_far = -val_so_far;
3063 accum = expand_unop (mode, neg_optab, accum, target, 0);
3065 else if (variant == add_variant)
3067 val_so_far = val_so_far + 1;
3068 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target);
3071 /* Compare only the bits of val and val_so_far that are significant
3072 in the result mode, to avoid sign-/zero-extension confusion. */
3073 nmode = GET_MODE_INNER (mode);
3074 if (nmode == VOIDmode)
3075 nmode = mode;
3076 val &= GET_MODE_MASK (nmode);
3077 val_so_far &= GET_MODE_MASK (nmode);
3078 gcc_assert (val == val_so_far);
3080 return accum;
3083 /* Perform a multiplication and return an rtx for the result.
3084 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3085 TARGET is a suggestion for where to store the result (an rtx).
3087 We check specially for a constant integer as OP1.
3088 If you want this check for OP0 as well, then before calling
3089 you should swap the two operands if OP0 would be constant. */
3092 expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3093 int unsignedp)
3095 enum mult_variant variant;
3096 struct algorithm algorithm;
3097 rtx scalar_op1;
3098 int max_cost;
3099 bool speed = optimize_insn_for_speed_p ();
3100 bool do_trapv = flag_trapv && SCALAR_INT_MODE_P (mode) && !unsignedp;
3102 if (CONSTANT_P (op0))
3104 rtx temp = op0;
3105 op0 = op1;
3106 op1 = temp;
3109 /* For vectors, there are several simplifications that can be made if
3110 all elements of the vector constant are identical. */
3111 scalar_op1 = op1;
3112 if (GET_CODE (op1) == CONST_VECTOR)
3114 int i, n = CONST_VECTOR_NUNITS (op1);
3115 scalar_op1 = CONST_VECTOR_ELT (op1, 0);
3116 for (i = 1; i < n; ++i)
3117 if (!rtx_equal_p (scalar_op1, CONST_VECTOR_ELT (op1, i)))
3118 goto skip_scalar;
3121 if (INTEGRAL_MODE_P (mode))
3123 rtx fake_reg;
3124 HOST_WIDE_INT coeff;
3125 bool is_neg;
3126 int mode_bitsize;
3128 if (op1 == CONST0_RTX (mode))
3129 return op1;
3130 if (op1 == CONST1_RTX (mode))
3131 return op0;
3132 if (op1 == CONSTM1_RTX (mode))
3133 return expand_unop (mode, do_trapv ? negv_optab : neg_optab,
3134 op0, target, 0);
3136 if (do_trapv)
3137 goto skip_synth;
3139 /* If mode is integer vector mode, check if the backend supports
3140 vector lshift (by scalar or vector) at all. If not, we can't use
3141 synthetized multiply. */
3142 if (GET_MODE_CLASS (mode) == MODE_VECTOR_INT
3143 && optab_handler (vashl_optab, mode) == CODE_FOR_nothing
3144 && optab_handler (ashl_optab, mode) == CODE_FOR_nothing)
3145 goto skip_synth;
3147 /* These are the operations that are potentially turned into
3148 a sequence of shifts and additions. */
3149 mode_bitsize = GET_MODE_UNIT_BITSIZE (mode);
3151 /* synth_mult does an `unsigned int' multiply. As long as the mode is
3152 less than or equal in size to `unsigned int' this doesn't matter.
3153 If the mode is larger than `unsigned int', then synth_mult works
3154 only if the constant value exactly fits in an `unsigned int' without
3155 any truncation. This means that multiplying by negative values does
3156 not work; results are off by 2^32 on a 32 bit machine. */
3158 if (CONST_INT_P (scalar_op1))
3160 coeff = INTVAL (scalar_op1);
3161 is_neg = coeff < 0;
3163 else if (CONST_DOUBLE_AS_INT_P (scalar_op1))
3165 /* If we are multiplying in DImode, it may still be a win
3166 to try to work with shifts and adds. */
3167 if (CONST_DOUBLE_HIGH (scalar_op1) == 0
3168 && (CONST_DOUBLE_LOW (scalar_op1) > 0
3169 || (CONST_DOUBLE_LOW (scalar_op1) < 0
3170 && EXACT_POWER_OF_2_OR_ZERO_P
3171 (CONST_DOUBLE_LOW (scalar_op1)))))
3173 coeff = CONST_DOUBLE_LOW (scalar_op1);
3174 is_neg = false;
3176 else if (CONST_DOUBLE_LOW (scalar_op1) == 0)
3178 coeff = CONST_DOUBLE_HIGH (scalar_op1);
3179 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3181 int shift = floor_log2 (coeff) + HOST_BITS_PER_WIDE_INT;
3182 if (shift < HOST_BITS_PER_DOUBLE_INT - 1
3183 || mode_bitsize <= HOST_BITS_PER_DOUBLE_INT)
3184 return expand_shift (LSHIFT_EXPR, mode, op0,
3185 shift, target, unsignedp);
3187 goto skip_synth;
3189 else
3190 goto skip_synth;
3192 else
3193 goto skip_synth;
3195 /* We used to test optimize here, on the grounds that it's better to
3196 produce a smaller program when -O is not used. But this causes
3197 such a terrible slowdown sometimes that it seems better to always
3198 use synth_mult. */
3200 /* Special case powers of two. */
3201 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff)
3202 && !(is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT))
3203 return expand_shift (LSHIFT_EXPR, mode, op0,
3204 floor_log2 (coeff), target, unsignedp);
3206 fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3208 /* Attempt to handle multiplication of DImode values by negative
3209 coefficients, by performing the multiplication by a positive
3210 multiplier and then inverting the result. */
3211 if (is_neg && mode_bitsize > HOST_BITS_PER_WIDE_INT)
3213 /* Its safe to use -coeff even for INT_MIN, as the
3214 result is interpreted as an unsigned coefficient.
3215 Exclude cost of op0 from max_cost to match the cost
3216 calculation of the synth_mult. */
3217 coeff = -(unsigned HOST_WIDE_INT) coeff;
3218 max_cost = (set_src_cost (gen_rtx_MULT (mode, fake_reg, op1), speed)
3219 - neg_cost (speed, mode));
3220 if (max_cost <= 0)
3221 goto skip_synth;
3223 /* Special case powers of two. */
3224 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3226 rtx temp = expand_shift (LSHIFT_EXPR, mode, op0,
3227 floor_log2 (coeff), target, unsignedp);
3228 return expand_unop (mode, neg_optab, temp, target, 0);
3231 if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3232 max_cost))
3234 rtx temp = expand_mult_const (mode, op0, coeff, NULL_RTX,
3235 &algorithm, variant);
3236 return expand_unop (mode, neg_optab, temp, target, 0);
3238 goto skip_synth;
3241 /* Exclude cost of op0 from max_cost to match the cost
3242 calculation of the synth_mult. */
3243 max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, op1), speed);
3244 if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3245 return expand_mult_const (mode, op0, coeff, target,
3246 &algorithm, variant);
3248 skip_synth:
3250 /* Expand x*2.0 as x+x. */
3251 if (CONST_DOUBLE_AS_FLOAT_P (scalar_op1))
3253 REAL_VALUE_TYPE d;
3254 REAL_VALUE_FROM_CONST_DOUBLE (d, scalar_op1);
3256 if (REAL_VALUES_EQUAL (d, dconst2))
3258 op0 = force_reg (GET_MODE (op0), op0);
3259 return expand_binop (mode, add_optab, op0, op0,
3260 target, unsignedp, OPTAB_LIB_WIDEN);
3263 skip_scalar:
3265 /* This used to use umul_optab if unsigned, but for non-widening multiply
3266 there is no difference between signed and unsigned. */
3267 op0 = expand_binop (mode, do_trapv ? smulv_optab : smul_optab,
3268 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN);
3269 gcc_assert (op0);
3270 return op0;
3273 /* Return a cost estimate for multiplying a register by the given
3274 COEFFicient in the given MODE and SPEED. */
3277 mult_by_coeff_cost (HOST_WIDE_INT coeff, enum machine_mode mode, bool speed)
3279 int max_cost;
3280 struct algorithm algorithm;
3281 enum mult_variant variant;
3283 rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1);
3284 max_cost = set_src_cost (gen_rtx_MULT (mode, fake_reg, fake_reg), speed);
3285 if (choose_mult_variant (mode, coeff, &algorithm, &variant, max_cost))
3286 return algorithm.cost.cost;
3287 else
3288 return max_cost;
3291 /* Perform a widening multiplication and return an rtx for the result.
3292 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's);
3293 TARGET is a suggestion for where to store the result (an rtx).
3294 THIS_OPTAB is the optab we should use, it must be either umul_widen_optab
3295 or smul_widen_optab.
3297 We check specially for a constant integer as OP1, comparing the
3298 cost of a widening multiply against the cost of a sequence of shifts
3299 and adds. */
3302 expand_widening_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target,
3303 int unsignedp, optab this_optab)
3305 bool speed = optimize_insn_for_speed_p ();
3306 rtx cop1;
3308 if (CONST_INT_P (op1)
3309 && GET_MODE (op0) != VOIDmode
3310 && (cop1 = convert_modes (mode, GET_MODE (op0), op1,
3311 this_optab == umul_widen_optab))
3312 && CONST_INT_P (cop1)
3313 && (INTVAL (cop1) >= 0
3314 || HWI_COMPUTABLE_MODE_P (mode)))
3316 HOST_WIDE_INT coeff = INTVAL (cop1);
3317 int max_cost;
3318 enum mult_variant variant;
3319 struct algorithm algorithm;
3321 /* Special case powers of two. */
3322 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff))
3324 op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3325 return expand_shift (LSHIFT_EXPR, mode, op0,
3326 floor_log2 (coeff), target, unsignedp);
3329 /* Exclude cost of op0 from max_cost to match the cost
3330 calculation of the synth_mult. */
3331 max_cost = mul_widen_cost (speed, mode);
3332 if (choose_mult_variant (mode, coeff, &algorithm, &variant,
3333 max_cost))
3335 op0 = convert_to_mode (mode, op0, this_optab == umul_widen_optab);
3336 return expand_mult_const (mode, op0, coeff, target,
3337 &algorithm, variant);
3340 return expand_binop (mode, this_optab, op0, op1, target,
3341 unsignedp, OPTAB_LIB_WIDEN);
3344 /* Choose a minimal N + 1 bit approximation to 1/D that can be used to
3345 replace division by D, and put the least significant N bits of the result
3346 in *MULTIPLIER_PTR and return the most significant bit.
3348 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the
3349 needed precision is in PRECISION (should be <= N).
3351 PRECISION should be as small as possible so this function can choose
3352 multiplier more freely.
3354 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that
3355 is to be used for a final right shift is placed in *POST_SHIFT_PTR.
3357 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR),
3358 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */
3360 unsigned HOST_WIDE_INT
3361 choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision,
3362 unsigned HOST_WIDE_INT *multiplier_ptr,
3363 int *post_shift_ptr, int *lgup_ptr)
3365 double_int mhigh, mlow;
3366 int lgup, post_shift;
3367 int pow, pow2;
3369 /* lgup = ceil(log2(divisor)); */
3370 lgup = ceil_log2 (d);
3372 gcc_assert (lgup <= n);
3374 pow = n + lgup;
3375 pow2 = n + lgup - precision;
3377 /* We could handle this with some effort, but this case is much
3378 better handled directly with a scc insn, so rely on caller using
3379 that. */
3380 gcc_assert (pow != HOST_BITS_PER_DOUBLE_INT);
3382 /* mlow = 2^(N + lgup)/d */
3383 double_int val = double_int_zero.set_bit (pow);
3384 mlow = val.div (double_int::from_uhwi (d), true, TRUNC_DIV_EXPR);
3386 /* mhigh = (2^(N + lgup) + 2^(N + lgup - precision))/d */
3387 val |= double_int_zero.set_bit (pow2);
3388 mhigh = val.div (double_int::from_uhwi (d), true, TRUNC_DIV_EXPR);
3390 gcc_assert (!mhigh.high || val.high - d < d);
3391 gcc_assert (mhigh.high <= 1 && mlow.high <= 1);
3392 /* Assert that mlow < mhigh. */
3393 gcc_assert (mlow.ult (mhigh));
3395 /* If precision == N, then mlow, mhigh exceed 2^N
3396 (but they do not exceed 2^(N+1)). */
3398 /* Reduce to lowest terms. */
3399 for (post_shift = lgup; post_shift > 0; post_shift--)
3401 int shft = HOST_BITS_PER_WIDE_INT - 1;
3402 unsigned HOST_WIDE_INT ml_lo = (mlow.high << shft) | (mlow.low >> 1);
3403 unsigned HOST_WIDE_INT mh_lo = (mhigh.high << shft) | (mhigh.low >> 1);
3404 if (ml_lo >= mh_lo)
3405 break;
3407 mlow = double_int::from_uhwi (ml_lo);
3408 mhigh = double_int::from_uhwi (mh_lo);
3411 *post_shift_ptr = post_shift;
3412 *lgup_ptr = lgup;
3413 if (n < HOST_BITS_PER_WIDE_INT)
3415 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1;
3416 *multiplier_ptr = mhigh.low & mask;
3417 return mhigh.low >= mask;
3419 else
3421 *multiplier_ptr = mhigh.low;
3422 return mhigh.high;
3426 /* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is
3427 congruent to 1 (mod 2**N). */
3429 static unsigned HOST_WIDE_INT
3430 invert_mod2n (unsigned HOST_WIDE_INT x, int n)
3432 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */
3434 /* The algorithm notes that the choice y = x satisfies
3435 x*y == 1 mod 2^3, since x is assumed odd.
3436 Each iteration doubles the number of bits of significance in y. */
3438 unsigned HOST_WIDE_INT mask;
3439 unsigned HOST_WIDE_INT y = x;
3440 int nbit = 3;
3442 mask = (n == HOST_BITS_PER_WIDE_INT
3443 ? ~(unsigned HOST_WIDE_INT) 0
3444 : ((unsigned HOST_WIDE_INT) 1 << n) - 1);
3446 while (nbit < n)
3448 y = y * (2 - x*y) & mask; /* Modulo 2^N */
3449 nbit *= 2;
3451 return y;
3454 /* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness
3455 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the
3456 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product
3457 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to
3458 become signed.
3460 The result is put in TARGET if that is convenient.
3462 MODE is the mode of operation. */
3465 expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0,
3466 rtx op1, rtx target, int unsignedp)
3468 rtx tem;
3469 enum rtx_code adj_code = unsignedp ? PLUS : MINUS;
3471 tem = expand_shift (RSHIFT_EXPR, mode, op0,
3472 GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3473 tem = expand_and (mode, tem, op1, NULL_RTX);
3474 adj_operand
3475 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3476 adj_operand);
3478 tem = expand_shift (RSHIFT_EXPR, mode, op1,
3479 GET_MODE_BITSIZE (mode) - 1, NULL_RTX, 0);
3480 tem = expand_and (mode, tem, op0, NULL_RTX);
3481 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem),
3482 target);
3484 return target;
3487 /* Subroutine of expmed_mult_highpart. Return the MODE high part of OP. */
3489 static rtx
3490 extract_high_half (enum machine_mode mode, rtx op)
3492 enum machine_mode wider_mode;
3494 if (mode == word_mode)
3495 return gen_highpart (mode, op);
3497 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3499 wider_mode = GET_MODE_WIDER_MODE (mode);
3500 op = expand_shift (RSHIFT_EXPR, wider_mode, op,
3501 GET_MODE_BITSIZE (mode), 0, 1);
3502 return convert_modes (mode, wider_mode, op, 0);
3505 /* Like expmed_mult_highpart, but only consider using a multiplication
3506 optab. OP1 is an rtx for the constant operand. */
3508 static rtx
3509 expmed_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1,
3510 rtx target, int unsignedp, int max_cost)
3512 rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode);
3513 enum machine_mode wider_mode;
3514 optab moptab;
3515 rtx tem;
3516 int size;
3517 bool speed = optimize_insn_for_speed_p ();
3519 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3521 wider_mode = GET_MODE_WIDER_MODE (mode);
3522 size = GET_MODE_BITSIZE (mode);
3524 /* Firstly, try using a multiplication insn that only generates the needed
3525 high part of the product, and in the sign flavor of unsignedp. */
3526 if (mul_highpart_cost (speed, mode) < max_cost)
3528 moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab;
3529 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3530 unsignedp, OPTAB_DIRECT);
3531 if (tem)
3532 return tem;
3535 /* Secondly, same as above, but use sign flavor opposite of unsignedp.
3536 Need to adjust the result after the multiplication. */
3537 if (size - 1 < BITS_PER_WORD
3538 && (mul_highpart_cost (speed, mode)
3539 + 2 * shift_cost (speed, mode, size-1)
3540 + 4 * add_cost (speed, mode) < max_cost))
3542 moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab;
3543 tem = expand_binop (mode, moptab, op0, narrow_op1, target,
3544 unsignedp, OPTAB_DIRECT);
3545 if (tem)
3546 /* We used the wrong signedness. Adjust the result. */
3547 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3548 tem, unsignedp);
3551 /* Try widening multiplication. */
3552 moptab = unsignedp ? umul_widen_optab : smul_widen_optab;
3553 if (widening_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3554 && mul_widen_cost (speed, wider_mode) < max_cost)
3556 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0,
3557 unsignedp, OPTAB_WIDEN);
3558 if (tem)
3559 return extract_high_half (mode, tem);
3562 /* Try widening the mode and perform a non-widening multiplication. */
3563 if (optab_handler (smul_optab, wider_mode) != CODE_FOR_nothing
3564 && size - 1 < BITS_PER_WORD
3565 && (mul_cost (speed, wider_mode) + shift_cost (speed, mode, size-1)
3566 < max_cost))
3568 rtx insns, wop0, wop1;
3570 /* We need to widen the operands, for example to ensure the
3571 constant multiplier is correctly sign or zero extended.
3572 Use a sequence to clean-up any instructions emitted by
3573 the conversions if things don't work out. */
3574 start_sequence ();
3575 wop0 = convert_modes (wider_mode, mode, op0, unsignedp);
3576 wop1 = convert_modes (wider_mode, mode, op1, unsignedp);
3577 tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0,
3578 unsignedp, OPTAB_WIDEN);
3579 insns = get_insns ();
3580 end_sequence ();
3582 if (tem)
3584 emit_insn (insns);
3585 return extract_high_half (mode, tem);
3589 /* Try widening multiplication of opposite signedness, and adjust. */
3590 moptab = unsignedp ? smul_widen_optab : umul_widen_optab;
3591 if (widening_optab_handler (moptab, wider_mode, mode) != CODE_FOR_nothing
3592 && size - 1 < BITS_PER_WORD
3593 && (mul_widen_cost (speed, wider_mode)
3594 + 2 * shift_cost (speed, mode, size-1)
3595 + 4 * add_cost (speed, mode) < max_cost))
3597 tem = expand_binop (wider_mode, moptab, op0, narrow_op1,
3598 NULL_RTX, ! unsignedp, OPTAB_WIDEN);
3599 if (tem != 0)
3601 tem = extract_high_half (mode, tem);
3602 /* We used the wrong signedness. Adjust the result. */
3603 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1,
3604 target, unsignedp);
3608 return 0;
3611 /* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant),
3612 putting the high half of the result in TARGET if that is convenient,
3613 and return where the result is. If the operation can not be performed,
3614 0 is returned.
3616 MODE is the mode of operation and result.
3618 UNSIGNEDP nonzero means unsigned multiply.
3620 MAX_COST is the total allowed cost for the expanded RTL. */
3622 static rtx
3623 expmed_mult_highpart (enum machine_mode mode, rtx op0, rtx op1,
3624 rtx target, int unsignedp, int max_cost)
3626 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode);
3627 unsigned HOST_WIDE_INT cnst1;
3628 int extra_cost;
3629 bool sign_adjust = false;
3630 enum mult_variant variant;
3631 struct algorithm alg;
3632 rtx tem;
3633 bool speed = optimize_insn_for_speed_p ();
3635 gcc_assert (!SCALAR_FLOAT_MODE_P (mode));
3636 /* We can't support modes wider than HOST_BITS_PER_INT. */
3637 gcc_assert (HWI_COMPUTABLE_MODE_P (mode));
3639 cnst1 = INTVAL (op1) & GET_MODE_MASK (mode);
3641 /* We can't optimize modes wider than BITS_PER_WORD.
3642 ??? We might be able to perform double-word arithmetic if
3643 mode == word_mode, however all the cost calculations in
3644 synth_mult etc. assume single-word operations. */
3645 if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD)
3646 return expmed_mult_highpart_optab (mode, op0, op1, target,
3647 unsignedp, max_cost);
3649 extra_cost = shift_cost (speed, mode, GET_MODE_BITSIZE (mode) - 1);
3651 /* Check whether we try to multiply by a negative constant. */
3652 if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1))
3654 sign_adjust = true;
3655 extra_cost += add_cost (speed, mode);
3658 /* See whether shift/add multiplication is cheap enough. */
3659 if (choose_mult_variant (wider_mode, cnst1, &alg, &variant,
3660 max_cost - extra_cost))
3662 /* See whether the specialized multiplication optabs are
3663 cheaper than the shift/add version. */
3664 tem = expmed_mult_highpart_optab (mode, op0, op1, target, unsignedp,
3665 alg.cost.cost + extra_cost);
3666 if (tem)
3667 return tem;
3669 tem = convert_to_mode (wider_mode, op0, unsignedp);
3670 tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant);
3671 tem = extract_high_half (mode, tem);
3673 /* Adjust result for signedness. */
3674 if (sign_adjust)
3675 tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem);
3677 return tem;
3679 return expmed_mult_highpart_optab (mode, op0, op1, target,
3680 unsignedp, max_cost);
3684 /* Expand signed modulus of OP0 by a power of two D in mode MODE. */
3686 static rtx
3687 expand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3689 unsigned HOST_WIDE_INT masklow, maskhigh;
3690 rtx result, temp, shift, label;
3691 int logd;
3693 logd = floor_log2 (d);
3694 result = gen_reg_rtx (mode);
3696 /* Avoid conditional branches when they're expensive. */
3697 if (BRANCH_COST (optimize_insn_for_speed_p (), false) >= 2
3698 && optimize_insn_for_speed_p ())
3700 rtx signmask = emit_store_flag (result, LT, op0, const0_rtx,
3701 mode, 0, -1);
3702 if (signmask)
3704 signmask = force_reg (mode, signmask);
3705 masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3706 shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd);
3708 /* Use the rtx_cost of a LSHIFTRT instruction to determine
3709 which instruction sequence to use. If logical right shifts
3710 are expensive the use 2 XORs, 2 SUBs and an AND, otherwise
3711 use a LSHIFTRT, 1 ADD, 1 SUB and an AND. */
3713 temp = gen_rtx_LSHIFTRT (mode, result, shift);
3714 if (optab_handler (lshr_optab, mode) == CODE_FOR_nothing
3715 || (set_src_cost (temp, optimize_insn_for_speed_p ())
3716 > COSTS_N_INSNS (2)))
3718 temp = expand_binop (mode, xor_optab, op0, signmask,
3719 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3720 temp = expand_binop (mode, sub_optab, temp, signmask,
3721 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3722 temp = expand_binop (mode, and_optab, temp,
3723 gen_int_mode (masklow, mode),
3724 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3725 temp = expand_binop (mode, xor_optab, temp, signmask,
3726 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3727 temp = expand_binop (mode, sub_optab, temp, signmask,
3728 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3730 else
3732 signmask = expand_binop (mode, lshr_optab, signmask, shift,
3733 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3734 signmask = force_reg (mode, signmask);
3736 temp = expand_binop (mode, add_optab, op0, signmask,
3737 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3738 temp = expand_binop (mode, and_optab, temp,
3739 gen_int_mode (masklow, mode),
3740 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3741 temp = expand_binop (mode, sub_optab, temp, signmask,
3742 NULL_RTX, 1, OPTAB_LIB_WIDEN);
3744 return temp;
3748 /* Mask contains the mode's signbit and the significant bits of the
3749 modulus. By including the signbit in the operation, many targets
3750 can avoid an explicit compare operation in the following comparison
3751 against zero. */
3753 masklow = ((HOST_WIDE_INT) 1 << logd) - 1;
3754 if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
3756 masklow |= HOST_WIDE_INT_M1U << (GET_MODE_BITSIZE (mode) - 1);
3757 maskhigh = -1;
3759 else
3760 maskhigh = HOST_WIDE_INT_M1U
3761 << (GET_MODE_BITSIZE (mode) - HOST_BITS_PER_WIDE_INT - 1);
3763 temp = expand_binop (mode, and_optab, op0,
3764 immed_double_const (masklow, maskhigh, mode),
3765 result, 1, OPTAB_LIB_WIDEN);
3766 if (temp != result)
3767 emit_move_insn (result, temp);
3769 label = gen_label_rtx ();
3770 do_cmp_and_jump (result, const0_rtx, GE, mode, label);
3772 temp = expand_binop (mode, sub_optab, result, const1_rtx, result,
3773 0, OPTAB_LIB_WIDEN);
3774 masklow = HOST_WIDE_INT_M1U << logd;
3775 maskhigh = -1;
3776 temp = expand_binop (mode, ior_optab, temp,
3777 immed_double_const (masklow, maskhigh, mode),
3778 result, 1, OPTAB_LIB_WIDEN);
3779 temp = expand_binop (mode, add_optab, temp, const1_rtx, result,
3780 0, OPTAB_LIB_WIDEN);
3781 if (temp != result)
3782 emit_move_insn (result, temp);
3783 emit_label (label);
3784 return result;
3787 /* Expand signed division of OP0 by a power of two D in mode MODE.
3788 This routine is only called for positive values of D. */
3790 static rtx
3791 expand_sdiv_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d)
3793 rtx temp, label;
3794 int logd;
3796 logd = floor_log2 (d);
3798 if (d == 2
3799 && BRANCH_COST (optimize_insn_for_speed_p (),
3800 false) >= 1)
3802 temp = gen_reg_rtx (mode);
3803 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1);
3804 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3805 0, OPTAB_LIB_WIDEN);
3806 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3809 #ifdef HAVE_conditional_move
3810 if (BRANCH_COST (optimize_insn_for_speed_p (), false)
3811 >= 2)
3813 rtx temp2;
3815 start_sequence ();
3816 temp2 = copy_to_mode_reg (mode, op0);
3817 temp = expand_binop (mode, add_optab, temp2, gen_int_mode (d - 1, mode),
3818 NULL_RTX, 0, OPTAB_LIB_WIDEN);
3819 temp = force_reg (mode, temp);
3821 /* Construct "temp2 = (temp2 < 0) ? temp : temp2". */
3822 temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx,
3823 mode, temp, temp2, mode, 0);
3824 if (temp2)
3826 rtx seq = get_insns ();
3827 end_sequence ();
3828 emit_insn (seq);
3829 return expand_shift (RSHIFT_EXPR, mode, temp2, logd, NULL_RTX, 0);
3831 end_sequence ();
3833 #endif
3835 if (BRANCH_COST (optimize_insn_for_speed_p (),
3836 false) >= 2)
3838 int ushift = GET_MODE_BITSIZE (mode) - logd;
3840 temp = gen_reg_rtx (mode);
3841 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1);
3842 if (shift_cost (optimize_insn_for_speed_p (), mode, ushift)
3843 > COSTS_N_INSNS (1))
3844 temp = expand_binop (mode, and_optab, temp, gen_int_mode (d - 1, mode),
3845 NULL_RTX, 0, OPTAB_LIB_WIDEN);
3846 else
3847 temp = expand_shift (RSHIFT_EXPR, mode, temp,
3848 ushift, NULL_RTX, 1);
3849 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX,
3850 0, OPTAB_LIB_WIDEN);
3851 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3854 label = gen_label_rtx ();
3855 temp = copy_to_mode_reg (mode, op0);
3856 do_cmp_and_jump (temp, const0_rtx, GE, mode, label);
3857 expand_inc (temp, gen_int_mode (d - 1, mode));
3858 emit_label (label);
3859 return expand_shift (RSHIFT_EXPR, mode, temp, logd, NULL_RTX, 0);
3862 /* Emit the code to divide OP0 by OP1, putting the result in TARGET
3863 if that is convenient, and returning where the result is.
3864 You may request either the quotient or the remainder as the result;
3865 specify REM_FLAG nonzero to get the remainder.
3867 CODE is the expression code for which kind of division this is;
3868 it controls how rounding is done. MODE is the machine mode to use.
3869 UNSIGNEDP nonzero means do unsigned division. */
3871 /* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI
3872 and then correct it by or'ing in missing high bits
3873 if result of ANDI is nonzero.
3874 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result.
3875 This could optimize to a bfexts instruction.
3876 But C doesn't use these operations, so their optimizations are
3877 left for later. */
3878 /* ??? For modulo, we don't actually need the highpart of the first product,
3879 the low part will do nicely. And for small divisors, the second multiply
3880 can also be a low-part only multiply or even be completely left out.
3881 E.g. to calculate the remainder of a division by 3 with a 32 bit
3882 multiply, multiply with 0x55555556 and extract the upper two bits;
3883 the result is exact for inputs up to 0x1fffffff.
3884 The input range can be reduced by using cross-sum rules.
3885 For odd divisors >= 3, the following table gives right shift counts
3886 so that if a number is shifted by an integer multiple of the given
3887 amount, the remainder stays the same:
3888 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20,
3889 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0,
3890 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0,
3891 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33,
3892 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12
3894 Cross-sum rules for even numbers can be derived by leaving as many bits
3895 to the right alone as the divisor has zeros to the right.
3896 E.g. if x is an unsigned 32 bit number:
3897 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28
3901 expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode,
3902 rtx op0, rtx op1, rtx target, int unsignedp)
3904 enum machine_mode compute_mode;
3905 rtx tquotient;
3906 rtx quotient = 0, remainder = 0;
3907 rtx last;
3908 int size;
3909 rtx insn;
3910 optab optab1, optab2;
3911 int op1_is_constant, op1_is_pow2 = 0;
3912 int max_cost, extra_cost;
3913 static HOST_WIDE_INT last_div_const = 0;
3914 bool speed = optimize_insn_for_speed_p ();
3916 op1_is_constant = CONST_INT_P (op1);
3917 if (op1_is_constant)
3919 unsigned HOST_WIDE_INT ext_op1 = UINTVAL (op1);
3920 if (unsignedp)
3921 ext_op1 &= GET_MODE_MASK (mode);
3922 op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1)
3923 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1))));
3927 This is the structure of expand_divmod:
3929 First comes code to fix up the operands so we can perform the operations
3930 correctly and efficiently.
3932 Second comes a switch statement with code specific for each rounding mode.
3933 For some special operands this code emits all RTL for the desired
3934 operation, for other cases, it generates only a quotient and stores it in
3935 QUOTIENT. The case for trunc division/remainder might leave quotient = 0,
3936 to indicate that it has not done anything.
3938 Last comes code that finishes the operation. If QUOTIENT is set and
3939 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If
3940 QUOTIENT is not set, it is computed using trunc rounding.
3942 We try to generate special code for division and remainder when OP1 is a
3943 constant. If |OP1| = 2**n we can use shifts and some other fast
3944 operations. For other values of OP1, we compute a carefully selected
3945 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0
3946 by m.
3948 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper
3949 half of the product. Different strategies for generating the product are
3950 implemented in expmed_mult_highpart.
3952 If what we actually want is the remainder, we generate that by another
3953 by-constant multiplication and a subtraction. */
3955 /* We shouldn't be called with OP1 == const1_rtx, but some of the
3956 code below will malfunction if we are, so check here and handle
3957 the special case if so. */
3958 if (op1 == const1_rtx)
3959 return rem_flag ? const0_rtx : op0;
3961 /* When dividing by -1, we could get an overflow.
3962 negv_optab can handle overflows. */
3963 if (! unsignedp && op1 == constm1_rtx)
3965 if (rem_flag)
3966 return const0_rtx;
3967 return expand_unop (mode, flag_trapv && GET_MODE_CLASS (mode) == MODE_INT
3968 ? negv_optab : neg_optab, op0, target, 0);
3971 if (target
3972 /* Don't use the function value register as a target
3973 since we have to read it as well as write it,
3974 and function-inlining gets confused by this. */
3975 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target))
3976 /* Don't clobber an operand while doing a multi-step calculation. */
3977 || ((rem_flag || op1_is_constant)
3978 && (reg_mentioned_p (target, op0)
3979 || (MEM_P (op0) && MEM_P (target))))
3980 || reg_mentioned_p (target, op1)
3981 || (MEM_P (op1) && MEM_P (target))))
3982 target = 0;
3984 /* Get the mode in which to perform this computation. Normally it will
3985 be MODE, but sometimes we can't do the desired operation in MODE.
3986 If so, pick a wider mode in which we can do the operation. Convert
3987 to that mode at the start to avoid repeated conversions.
3989 First see what operations we need. These depend on the expression
3990 we are evaluating. (We assume that divxx3 insns exist under the
3991 same conditions that modxx3 insns and that these insns don't normally
3992 fail. If these assumptions are not correct, we may generate less
3993 efficient code in some cases.)
3995 Then see if we find a mode in which we can open-code that operation
3996 (either a division, modulus, or shift). Finally, check for the smallest
3997 mode for which we can do the operation with a library call. */
3999 /* We might want to refine this now that we have division-by-constant
4000 optimization. Since expmed_mult_highpart tries so many variants, it is
4001 not straightforward to generalize this. Maybe we should make an array
4002 of possible modes in init_expmed? Save this for GCC 2.7. */
4004 optab1 = ((op1_is_pow2 && op1 != const0_rtx)
4005 ? (unsignedp ? lshr_optab : ashr_optab)
4006 : (unsignedp ? udiv_optab : sdiv_optab));
4007 optab2 = ((op1_is_pow2 && op1 != const0_rtx)
4008 ? optab1
4009 : (unsignedp ? udivmod_optab : sdivmod_optab));
4011 for (compute_mode = mode; compute_mode != VOIDmode;
4012 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
4013 if (optab_handler (optab1, compute_mode) != CODE_FOR_nothing
4014 || optab_handler (optab2, compute_mode) != CODE_FOR_nothing)
4015 break;
4017 if (compute_mode == VOIDmode)
4018 for (compute_mode = mode; compute_mode != VOIDmode;
4019 compute_mode = GET_MODE_WIDER_MODE (compute_mode))
4020 if (optab_libfunc (optab1, compute_mode)
4021 || optab_libfunc (optab2, compute_mode))
4022 break;
4024 /* If we still couldn't find a mode, use MODE, but expand_binop will
4025 probably die. */
4026 if (compute_mode == VOIDmode)
4027 compute_mode = mode;
4029 if (target && GET_MODE (target) == compute_mode)
4030 tquotient = target;
4031 else
4032 tquotient = gen_reg_rtx (compute_mode);
4034 size = GET_MODE_BITSIZE (compute_mode);
4035 #if 0
4036 /* It should be possible to restrict the precision to GET_MODE_BITSIZE
4037 (mode), and thereby get better code when OP1 is a constant. Do that
4038 later. It will require going over all usages of SIZE below. */
4039 size = GET_MODE_BITSIZE (mode);
4040 #endif
4042 /* Only deduct something for a REM if the last divide done was
4043 for a different constant. Then set the constant of the last
4044 divide. */
4045 max_cost = (unsignedp
4046 ? udiv_cost (speed, compute_mode)
4047 : sdiv_cost (speed, compute_mode));
4048 if (rem_flag && ! (last_div_const != 0 && op1_is_constant
4049 && INTVAL (op1) == last_div_const))
4050 max_cost -= (mul_cost (speed, compute_mode)
4051 + add_cost (speed, compute_mode));
4053 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0;
4055 /* Now convert to the best mode to use. */
4056 if (compute_mode != mode)
4058 op0 = convert_modes (compute_mode, mode, op0, unsignedp);
4059 op1 = convert_modes (compute_mode, mode, op1, unsignedp);
4061 /* convert_modes may have placed op1 into a register, so we
4062 must recompute the following. */
4063 op1_is_constant = CONST_INT_P (op1);
4064 op1_is_pow2 = (op1_is_constant
4065 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4066 || (! unsignedp
4067 && EXACT_POWER_OF_2_OR_ZERO_P (-UINTVAL (op1))))));
4070 /* If one of the operands is a volatile MEM, copy it into a register. */
4072 if (MEM_P (op0) && MEM_VOLATILE_P (op0))
4073 op0 = force_reg (compute_mode, op0);
4074 if (MEM_P (op1) && MEM_VOLATILE_P (op1))
4075 op1 = force_reg (compute_mode, op1);
4077 /* If we need the remainder or if OP1 is constant, we need to
4078 put OP0 in a register in case it has any queued subexpressions. */
4079 if (rem_flag || op1_is_constant)
4080 op0 = force_reg (compute_mode, op0);
4082 last = get_last_insn ();
4084 /* Promote floor rounding to trunc rounding for unsigned operations. */
4085 if (unsignedp)
4087 if (code == FLOOR_DIV_EXPR)
4088 code = TRUNC_DIV_EXPR;
4089 if (code == FLOOR_MOD_EXPR)
4090 code = TRUNC_MOD_EXPR;
4091 if (code == EXACT_DIV_EXPR && op1_is_pow2)
4092 code = TRUNC_DIV_EXPR;
4095 if (op1 != const0_rtx)
4096 switch (code)
4098 case TRUNC_MOD_EXPR:
4099 case TRUNC_DIV_EXPR:
4100 if (op1_is_constant)
4102 if (unsignedp)
4104 unsigned HOST_WIDE_INT mh, ml;
4105 int pre_shift, post_shift;
4106 int dummy;
4107 unsigned HOST_WIDE_INT d = (INTVAL (op1)
4108 & GET_MODE_MASK (compute_mode));
4110 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4112 pre_shift = floor_log2 (d);
4113 if (rem_flag)
4115 unsigned HOST_WIDE_INT mask
4116 = ((unsigned HOST_WIDE_INT) 1 << pre_shift) - 1;
4117 remainder
4118 = expand_binop (compute_mode, and_optab, op0,
4119 gen_int_mode (mask, compute_mode),
4120 remainder, 1,
4121 OPTAB_LIB_WIDEN);
4122 if (remainder)
4123 return gen_lowpart (mode, remainder);
4125 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4126 pre_shift, tquotient, 1);
4128 else if (size <= HOST_BITS_PER_WIDE_INT)
4130 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1)))
4132 /* Most significant bit of divisor is set; emit an scc
4133 insn. */
4134 quotient = emit_store_flag_force (tquotient, GEU, op0, op1,
4135 compute_mode, 1, 1);
4137 else
4139 /* Find a suitable multiplier and right shift count
4140 instead of multiplying with D. */
4142 mh = choose_multiplier (d, size, size,
4143 &ml, &post_shift, &dummy);
4145 /* If the suggested multiplier is more than SIZE bits,
4146 we can do better for even divisors, using an
4147 initial right shift. */
4148 if (mh != 0 && (d & 1) == 0)
4150 pre_shift = floor_log2 (d & -d);
4151 mh = choose_multiplier (d >> pre_shift, size,
4152 size - pre_shift,
4153 &ml, &post_shift, &dummy);
4154 gcc_assert (!mh);
4156 else
4157 pre_shift = 0;
4159 if (mh != 0)
4161 rtx t1, t2, t3, t4;
4163 if (post_shift - 1 >= BITS_PER_WORD)
4164 goto fail1;
4166 extra_cost
4167 = (shift_cost (speed, compute_mode, post_shift - 1)
4168 + shift_cost (speed, compute_mode, 1)
4169 + 2 * add_cost (speed, compute_mode));
4170 t1 = expmed_mult_highpart
4171 (compute_mode, op0,
4172 gen_int_mode (ml, compute_mode),
4173 NULL_RTX, 1, max_cost - extra_cost);
4174 if (t1 == 0)
4175 goto fail1;
4176 t2 = force_operand (gen_rtx_MINUS (compute_mode,
4177 op0, t1),
4178 NULL_RTX);
4179 t3 = expand_shift (RSHIFT_EXPR, compute_mode,
4180 t2, 1, NULL_RTX, 1);
4181 t4 = force_operand (gen_rtx_PLUS (compute_mode,
4182 t1, t3),
4183 NULL_RTX);
4184 quotient = expand_shift
4185 (RSHIFT_EXPR, compute_mode, t4,
4186 post_shift - 1, tquotient, 1);
4188 else
4190 rtx t1, t2;
4192 if (pre_shift >= BITS_PER_WORD
4193 || post_shift >= BITS_PER_WORD)
4194 goto fail1;
4196 t1 = expand_shift
4197 (RSHIFT_EXPR, compute_mode, op0,
4198 pre_shift, NULL_RTX, 1);
4199 extra_cost
4200 = (shift_cost (speed, compute_mode, pre_shift)
4201 + shift_cost (speed, compute_mode, post_shift));
4202 t2 = expmed_mult_highpart
4203 (compute_mode, t1,
4204 gen_int_mode (ml, compute_mode),
4205 NULL_RTX, 1, max_cost - extra_cost);
4206 if (t2 == 0)
4207 goto fail1;
4208 quotient = expand_shift
4209 (RSHIFT_EXPR, compute_mode, t2,
4210 post_shift, tquotient, 1);
4214 else /* Too wide mode to use tricky code */
4215 break;
4217 insn = get_last_insn ();
4218 if (insn != last)
4219 set_dst_reg_note (insn, REG_EQUAL,
4220 gen_rtx_UDIV (compute_mode, op0, op1),
4221 quotient);
4223 else /* TRUNC_DIV, signed */
4225 unsigned HOST_WIDE_INT ml;
4226 int lgup, post_shift;
4227 rtx mlr;
4228 HOST_WIDE_INT d = INTVAL (op1);
4229 unsigned HOST_WIDE_INT abs_d;
4231 /* Since d might be INT_MIN, we have to cast to
4232 unsigned HOST_WIDE_INT before negating to avoid
4233 undefined signed overflow. */
4234 abs_d = (d >= 0
4235 ? (unsigned HOST_WIDE_INT) d
4236 : - (unsigned HOST_WIDE_INT) d);
4238 /* n rem d = n rem -d */
4239 if (rem_flag && d < 0)
4241 d = abs_d;
4242 op1 = gen_int_mode (abs_d, compute_mode);
4245 if (d == 1)
4246 quotient = op0;
4247 else if (d == -1)
4248 quotient = expand_unop (compute_mode, neg_optab, op0,
4249 tquotient, 0);
4250 else if (HOST_BITS_PER_WIDE_INT >= size
4251 && abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1))
4253 /* This case is not handled correctly below. */
4254 quotient = emit_store_flag (tquotient, EQ, op0, op1,
4255 compute_mode, 1, 1);
4256 if (quotient == 0)
4257 goto fail1;
4259 else if (EXACT_POWER_OF_2_OR_ZERO_P (d)
4260 && (rem_flag
4261 ? smod_pow2_cheap (speed, compute_mode)
4262 : sdiv_pow2_cheap (speed, compute_mode))
4263 /* We assume that cheap metric is true if the
4264 optab has an expander for this mode. */
4265 && ((optab_handler ((rem_flag ? smod_optab
4266 : sdiv_optab),
4267 compute_mode)
4268 != CODE_FOR_nothing)
4269 || (optab_handler (sdivmod_optab,
4270 compute_mode)
4271 != CODE_FOR_nothing)))
4273 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d))
4275 if (rem_flag)
4277 remainder = expand_smod_pow2 (compute_mode, op0, d);
4278 if (remainder)
4279 return gen_lowpart (mode, remainder);
4282 if (sdiv_pow2_cheap (speed, compute_mode)
4283 && ((optab_handler (sdiv_optab, compute_mode)
4284 != CODE_FOR_nothing)
4285 || (optab_handler (sdivmod_optab, compute_mode)
4286 != CODE_FOR_nothing)))
4287 quotient = expand_divmod (0, TRUNC_DIV_EXPR,
4288 compute_mode, op0,
4289 gen_int_mode (abs_d,
4290 compute_mode),
4291 NULL_RTX, 0);
4292 else
4293 quotient = expand_sdiv_pow2 (compute_mode, op0, abs_d);
4295 /* We have computed OP0 / abs(OP1). If OP1 is negative,
4296 negate the quotient. */
4297 if (d < 0)
4299 insn = get_last_insn ();
4300 if (insn != last
4301 && abs_d < ((unsigned HOST_WIDE_INT) 1
4302 << (HOST_BITS_PER_WIDE_INT - 1)))
4303 set_dst_reg_note (insn, REG_EQUAL,
4304 gen_rtx_DIV (compute_mode, op0,
4305 gen_int_mode
4306 (abs_d,
4307 compute_mode)),
4308 quotient);
4310 quotient = expand_unop (compute_mode, neg_optab,
4311 quotient, quotient, 0);
4314 else if (size <= HOST_BITS_PER_WIDE_INT)
4316 choose_multiplier (abs_d, size, size - 1,
4317 &ml, &post_shift, &lgup);
4318 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1))
4320 rtx t1, t2, t3;
4322 if (post_shift >= BITS_PER_WORD
4323 || size - 1 >= BITS_PER_WORD)
4324 goto fail1;
4326 extra_cost = (shift_cost (speed, compute_mode, post_shift)
4327 + shift_cost (speed, compute_mode, size - 1)
4328 + add_cost (speed, compute_mode));
4329 t1 = expmed_mult_highpart
4330 (compute_mode, op0, gen_int_mode (ml, compute_mode),
4331 NULL_RTX, 0, max_cost - extra_cost);
4332 if (t1 == 0)
4333 goto fail1;
4334 t2 = expand_shift
4335 (RSHIFT_EXPR, compute_mode, t1,
4336 post_shift, NULL_RTX, 0);
4337 t3 = expand_shift
4338 (RSHIFT_EXPR, compute_mode, op0,
4339 size - 1, NULL_RTX, 0);
4340 if (d < 0)
4341 quotient
4342 = force_operand (gen_rtx_MINUS (compute_mode,
4343 t3, t2),
4344 tquotient);
4345 else
4346 quotient
4347 = force_operand (gen_rtx_MINUS (compute_mode,
4348 t2, t3),
4349 tquotient);
4351 else
4353 rtx t1, t2, t3, t4;
4355 if (post_shift >= BITS_PER_WORD
4356 || size - 1 >= BITS_PER_WORD)
4357 goto fail1;
4359 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1);
4360 mlr = gen_int_mode (ml, compute_mode);
4361 extra_cost = (shift_cost (speed, compute_mode, post_shift)
4362 + shift_cost (speed, compute_mode, size - 1)
4363 + 2 * add_cost (speed, compute_mode));
4364 t1 = expmed_mult_highpart (compute_mode, op0, mlr,
4365 NULL_RTX, 0,
4366 max_cost - extra_cost);
4367 if (t1 == 0)
4368 goto fail1;
4369 t2 = force_operand (gen_rtx_PLUS (compute_mode,
4370 t1, op0),
4371 NULL_RTX);
4372 t3 = expand_shift
4373 (RSHIFT_EXPR, compute_mode, t2,
4374 post_shift, NULL_RTX, 0);
4375 t4 = expand_shift
4376 (RSHIFT_EXPR, compute_mode, op0,
4377 size - 1, NULL_RTX, 0);
4378 if (d < 0)
4379 quotient
4380 = force_operand (gen_rtx_MINUS (compute_mode,
4381 t4, t3),
4382 tquotient);
4383 else
4384 quotient
4385 = force_operand (gen_rtx_MINUS (compute_mode,
4386 t3, t4),
4387 tquotient);
4390 else /* Too wide mode to use tricky code */
4391 break;
4393 insn = get_last_insn ();
4394 if (insn != last)
4395 set_dst_reg_note (insn, REG_EQUAL,
4396 gen_rtx_DIV (compute_mode, op0, op1),
4397 quotient);
4399 break;
4401 fail1:
4402 delete_insns_since (last);
4403 break;
4405 case FLOOR_DIV_EXPR:
4406 case FLOOR_MOD_EXPR:
4407 /* We will come here only for signed operations. */
4408 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4410 unsigned HOST_WIDE_INT mh, ml;
4411 int pre_shift, lgup, post_shift;
4412 HOST_WIDE_INT d = INTVAL (op1);
4414 if (d > 0)
4416 /* We could just as easily deal with negative constants here,
4417 but it does not seem worth the trouble for GCC 2.6. */
4418 if (EXACT_POWER_OF_2_OR_ZERO_P (d))
4420 pre_shift = floor_log2 (d);
4421 if (rem_flag)
4423 unsigned HOST_WIDE_INT mask
4424 = ((unsigned HOST_WIDE_INT) 1 << pre_shift) - 1;
4425 remainder = expand_binop
4426 (compute_mode, and_optab, op0,
4427 gen_int_mode (mask, compute_mode),
4428 remainder, 0, OPTAB_LIB_WIDEN);
4429 if (remainder)
4430 return gen_lowpart (mode, remainder);
4432 quotient = expand_shift
4433 (RSHIFT_EXPR, compute_mode, op0,
4434 pre_shift, tquotient, 0);
4436 else
4438 rtx t1, t2, t3, t4;
4440 mh = choose_multiplier (d, size, size - 1,
4441 &ml, &post_shift, &lgup);
4442 gcc_assert (!mh);
4444 if (post_shift < BITS_PER_WORD
4445 && size - 1 < BITS_PER_WORD)
4447 t1 = expand_shift
4448 (RSHIFT_EXPR, compute_mode, op0,
4449 size - 1, NULL_RTX, 0);
4450 t2 = expand_binop (compute_mode, xor_optab, op0, t1,
4451 NULL_RTX, 0, OPTAB_WIDEN);
4452 extra_cost = (shift_cost (speed, compute_mode, post_shift)
4453 + shift_cost (speed, compute_mode, size - 1)
4454 + 2 * add_cost (speed, compute_mode));
4455 t3 = expmed_mult_highpart
4456 (compute_mode, t2, gen_int_mode (ml, compute_mode),
4457 NULL_RTX, 1, max_cost - extra_cost);
4458 if (t3 != 0)
4460 t4 = expand_shift
4461 (RSHIFT_EXPR, compute_mode, t3,
4462 post_shift, NULL_RTX, 1);
4463 quotient = expand_binop (compute_mode, xor_optab,
4464 t4, t1, tquotient, 0,
4465 OPTAB_WIDEN);
4470 else
4472 rtx nsign, t1, t2, t3, t4;
4473 t1 = force_operand (gen_rtx_PLUS (compute_mode,
4474 op0, constm1_rtx), NULL_RTX);
4475 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX,
4476 0, OPTAB_WIDEN);
4477 nsign = expand_shift
4478 (RSHIFT_EXPR, compute_mode, t2,
4479 size - 1, NULL_RTX, 0);
4480 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign),
4481 NULL_RTX);
4482 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1,
4483 NULL_RTX, 0);
4484 if (t4)
4486 rtx t5;
4487 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign,
4488 NULL_RTX, 0);
4489 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4490 t4, t5),
4491 tquotient);
4496 if (quotient != 0)
4497 break;
4498 delete_insns_since (last);
4500 /* Try using an instruction that produces both the quotient and
4501 remainder, using truncation. We can easily compensate the quotient
4502 or remainder to get floor rounding, once we have the remainder.
4503 Notice that we compute also the final remainder value here,
4504 and return the result right away. */
4505 if (target == 0 || GET_MODE (target) != compute_mode)
4506 target = gen_reg_rtx (compute_mode);
4508 if (rem_flag)
4510 remainder
4511 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4512 quotient = gen_reg_rtx (compute_mode);
4514 else
4516 quotient
4517 = REG_P (target) ? target : gen_reg_rtx (compute_mode);
4518 remainder = gen_reg_rtx (compute_mode);
4521 if (expand_twoval_binop (sdivmod_optab, op0, op1,
4522 quotient, remainder, 0))
4524 /* This could be computed with a branch-less sequence.
4525 Save that for later. */
4526 rtx tem;
4527 rtx label = gen_label_rtx ();
4528 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label);
4529 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4530 NULL_RTX, 0, OPTAB_WIDEN);
4531 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label);
4532 expand_dec (quotient, const1_rtx);
4533 expand_inc (remainder, op1);
4534 emit_label (label);
4535 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4538 /* No luck with division elimination or divmod. Have to do it
4539 by conditionally adjusting op0 *and* the result. */
4541 rtx label1, label2, label3, label4, label5;
4542 rtx adjusted_op0;
4543 rtx tem;
4545 quotient = gen_reg_rtx (compute_mode);
4546 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4547 label1 = gen_label_rtx ();
4548 label2 = gen_label_rtx ();
4549 label3 = gen_label_rtx ();
4550 label4 = gen_label_rtx ();
4551 label5 = gen_label_rtx ();
4552 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4553 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1);
4554 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4555 quotient, 0, OPTAB_LIB_WIDEN);
4556 if (tem != quotient)
4557 emit_move_insn (quotient, tem);
4558 emit_jump_insn (gen_jump (label5));
4559 emit_barrier ();
4560 emit_label (label1);
4561 expand_inc (adjusted_op0, const1_rtx);
4562 emit_jump_insn (gen_jump (label4));
4563 emit_barrier ();
4564 emit_label (label2);
4565 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3);
4566 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4567 quotient, 0, OPTAB_LIB_WIDEN);
4568 if (tem != quotient)
4569 emit_move_insn (quotient, tem);
4570 emit_jump_insn (gen_jump (label5));
4571 emit_barrier ();
4572 emit_label (label3);
4573 expand_dec (adjusted_op0, const1_rtx);
4574 emit_label (label4);
4575 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4576 quotient, 0, OPTAB_LIB_WIDEN);
4577 if (tem != quotient)
4578 emit_move_insn (quotient, tem);
4579 expand_dec (quotient, const1_rtx);
4580 emit_label (label5);
4582 break;
4584 case CEIL_DIV_EXPR:
4585 case CEIL_MOD_EXPR:
4586 if (unsignedp)
4588 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)))
4590 rtx t1, t2, t3;
4591 unsigned HOST_WIDE_INT d = INTVAL (op1);
4592 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4593 floor_log2 (d), tquotient, 1);
4594 t2 = expand_binop (compute_mode, and_optab, op0,
4595 gen_int_mode (d - 1, compute_mode),
4596 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4597 t3 = gen_reg_rtx (compute_mode);
4598 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4599 compute_mode, 1, 1);
4600 if (t3 == 0)
4602 rtx lab;
4603 lab = gen_label_rtx ();
4604 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4605 expand_inc (t1, const1_rtx);
4606 emit_label (lab);
4607 quotient = t1;
4609 else
4610 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4611 t1, t3),
4612 tquotient);
4613 break;
4616 /* Try using an instruction that produces both the quotient and
4617 remainder, using truncation. We can easily compensate the
4618 quotient or remainder to get ceiling rounding, once we have the
4619 remainder. Notice that we compute also the final remainder
4620 value here, and return the result right away. */
4621 if (target == 0 || GET_MODE (target) != compute_mode)
4622 target = gen_reg_rtx (compute_mode);
4624 if (rem_flag)
4626 remainder = (REG_P (target)
4627 ? target : gen_reg_rtx (compute_mode));
4628 quotient = gen_reg_rtx (compute_mode);
4630 else
4632 quotient = (REG_P (target)
4633 ? target : gen_reg_rtx (compute_mode));
4634 remainder = gen_reg_rtx (compute_mode);
4637 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient,
4638 remainder, 1))
4640 /* This could be computed with a branch-less sequence.
4641 Save that for later. */
4642 rtx label = gen_label_rtx ();
4643 do_cmp_and_jump (remainder, const0_rtx, EQ,
4644 compute_mode, label);
4645 expand_inc (quotient, const1_rtx);
4646 expand_dec (remainder, op1);
4647 emit_label (label);
4648 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4651 /* No luck with division elimination or divmod. Have to do it
4652 by conditionally adjusting op0 *and* the result. */
4654 rtx label1, label2;
4655 rtx adjusted_op0, tem;
4657 quotient = gen_reg_rtx (compute_mode);
4658 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4659 label1 = gen_label_rtx ();
4660 label2 = gen_label_rtx ();
4661 do_cmp_and_jump (adjusted_op0, const0_rtx, NE,
4662 compute_mode, label1);
4663 emit_move_insn (quotient, const0_rtx);
4664 emit_jump_insn (gen_jump (label2));
4665 emit_barrier ();
4666 emit_label (label1);
4667 expand_dec (adjusted_op0, const1_rtx);
4668 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1,
4669 quotient, 1, OPTAB_LIB_WIDEN);
4670 if (tem != quotient)
4671 emit_move_insn (quotient, tem);
4672 expand_inc (quotient, const1_rtx);
4673 emit_label (label2);
4676 else /* signed */
4678 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))
4679 && INTVAL (op1) >= 0)
4681 /* This is extremely similar to the code for the unsigned case
4682 above. For 2.7 we should merge these variants, but for
4683 2.6.1 I don't want to touch the code for unsigned since that
4684 get used in C. The signed case will only be used by other
4685 languages (Ada). */
4687 rtx t1, t2, t3;
4688 unsigned HOST_WIDE_INT d = INTVAL (op1);
4689 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4690 floor_log2 (d), tquotient, 0);
4691 t2 = expand_binop (compute_mode, and_optab, op0,
4692 gen_int_mode (d - 1, compute_mode),
4693 NULL_RTX, 1, OPTAB_LIB_WIDEN);
4694 t3 = gen_reg_rtx (compute_mode);
4695 t3 = emit_store_flag (t3, NE, t2, const0_rtx,
4696 compute_mode, 1, 1);
4697 if (t3 == 0)
4699 rtx lab;
4700 lab = gen_label_rtx ();
4701 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab);
4702 expand_inc (t1, const1_rtx);
4703 emit_label (lab);
4704 quotient = t1;
4706 else
4707 quotient = force_operand (gen_rtx_PLUS (compute_mode,
4708 t1, t3),
4709 tquotient);
4710 break;
4713 /* Try using an instruction that produces both the quotient and
4714 remainder, using truncation. We can easily compensate the
4715 quotient or remainder to get ceiling rounding, once we have the
4716 remainder. Notice that we compute also the final remainder
4717 value here, and return the result right away. */
4718 if (target == 0 || GET_MODE (target) != compute_mode)
4719 target = gen_reg_rtx (compute_mode);
4720 if (rem_flag)
4722 remainder= (REG_P (target)
4723 ? target : gen_reg_rtx (compute_mode));
4724 quotient = gen_reg_rtx (compute_mode);
4726 else
4728 quotient = (REG_P (target)
4729 ? target : gen_reg_rtx (compute_mode));
4730 remainder = gen_reg_rtx (compute_mode);
4733 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient,
4734 remainder, 0))
4736 /* This could be computed with a branch-less sequence.
4737 Save that for later. */
4738 rtx tem;
4739 rtx label = gen_label_rtx ();
4740 do_cmp_and_jump (remainder, const0_rtx, EQ,
4741 compute_mode, label);
4742 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4743 NULL_RTX, 0, OPTAB_WIDEN);
4744 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label);
4745 expand_inc (quotient, const1_rtx);
4746 expand_dec (remainder, op1);
4747 emit_label (label);
4748 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4751 /* No luck with division elimination or divmod. Have to do it
4752 by conditionally adjusting op0 *and* the result. */
4754 rtx label1, label2, label3, label4, label5;
4755 rtx adjusted_op0;
4756 rtx tem;
4758 quotient = gen_reg_rtx (compute_mode);
4759 adjusted_op0 = copy_to_mode_reg (compute_mode, op0);
4760 label1 = gen_label_rtx ();
4761 label2 = gen_label_rtx ();
4762 label3 = gen_label_rtx ();
4763 label4 = gen_label_rtx ();
4764 label5 = gen_label_rtx ();
4765 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2);
4766 do_cmp_and_jump (adjusted_op0, const0_rtx, GT,
4767 compute_mode, label1);
4768 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4769 quotient, 0, OPTAB_LIB_WIDEN);
4770 if (tem != quotient)
4771 emit_move_insn (quotient, tem);
4772 emit_jump_insn (gen_jump (label5));
4773 emit_barrier ();
4774 emit_label (label1);
4775 expand_dec (adjusted_op0, const1_rtx);
4776 emit_jump_insn (gen_jump (label4));
4777 emit_barrier ();
4778 emit_label (label2);
4779 do_cmp_and_jump (adjusted_op0, const0_rtx, LT,
4780 compute_mode, label3);
4781 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4782 quotient, 0, OPTAB_LIB_WIDEN);
4783 if (tem != quotient)
4784 emit_move_insn (quotient, tem);
4785 emit_jump_insn (gen_jump (label5));
4786 emit_barrier ();
4787 emit_label (label3);
4788 expand_inc (adjusted_op0, const1_rtx);
4789 emit_label (label4);
4790 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1,
4791 quotient, 0, OPTAB_LIB_WIDEN);
4792 if (tem != quotient)
4793 emit_move_insn (quotient, tem);
4794 expand_inc (quotient, const1_rtx);
4795 emit_label (label5);
4798 break;
4800 case EXACT_DIV_EXPR:
4801 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size)
4803 HOST_WIDE_INT d = INTVAL (op1);
4804 unsigned HOST_WIDE_INT ml;
4805 int pre_shift;
4806 rtx t1;
4808 pre_shift = floor_log2 (d & -d);
4809 ml = invert_mod2n (d >> pre_shift, size);
4810 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0,
4811 pre_shift, NULL_RTX, unsignedp);
4812 quotient = expand_mult (compute_mode, t1,
4813 gen_int_mode (ml, compute_mode),
4814 NULL_RTX, 1);
4816 insn = get_last_insn ();
4817 set_dst_reg_note (insn, REG_EQUAL,
4818 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV,
4819 compute_mode, op0, op1),
4820 quotient);
4822 break;
4824 case ROUND_DIV_EXPR:
4825 case ROUND_MOD_EXPR:
4826 if (unsignedp)
4828 rtx tem;
4829 rtx label;
4830 label = gen_label_rtx ();
4831 quotient = gen_reg_rtx (compute_mode);
4832 remainder = gen_reg_rtx (compute_mode);
4833 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0)
4835 rtx tem;
4836 quotient = expand_binop (compute_mode, udiv_optab, op0, op1,
4837 quotient, 1, OPTAB_LIB_WIDEN);
4838 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1);
4839 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4840 remainder, 1, OPTAB_LIB_WIDEN);
4842 tem = plus_constant (compute_mode, op1, -1);
4843 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem, 1, NULL_RTX, 1);
4844 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label);
4845 expand_inc (quotient, const1_rtx);
4846 expand_dec (remainder, op1);
4847 emit_label (label);
4849 else
4851 rtx abs_rem, abs_op1, tem, mask;
4852 rtx label;
4853 label = gen_label_rtx ();
4854 quotient = gen_reg_rtx (compute_mode);
4855 remainder = gen_reg_rtx (compute_mode);
4856 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0)
4858 rtx tem;
4859 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1,
4860 quotient, 0, OPTAB_LIB_WIDEN);
4861 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0);
4862 remainder = expand_binop (compute_mode, sub_optab, op0, tem,
4863 remainder, 0, OPTAB_LIB_WIDEN);
4865 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0);
4866 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0);
4867 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem,
4868 1, NULL_RTX, 1);
4869 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label);
4870 tem = expand_binop (compute_mode, xor_optab, op0, op1,
4871 NULL_RTX, 0, OPTAB_WIDEN);
4872 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem,
4873 size - 1, NULL_RTX, 0);
4874 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx,
4875 NULL_RTX, 0, OPTAB_WIDEN);
4876 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4877 NULL_RTX, 0, OPTAB_WIDEN);
4878 expand_inc (quotient, tem);
4879 tem = expand_binop (compute_mode, xor_optab, mask, op1,
4880 NULL_RTX, 0, OPTAB_WIDEN);
4881 tem = expand_binop (compute_mode, sub_optab, tem, mask,
4882 NULL_RTX, 0, OPTAB_WIDEN);
4883 expand_dec (remainder, tem);
4884 emit_label (label);
4886 return gen_lowpart (mode, rem_flag ? remainder : quotient);
4888 default:
4889 gcc_unreachable ();
4892 if (quotient == 0)
4894 if (target && GET_MODE (target) != compute_mode)
4895 target = 0;
4897 if (rem_flag)
4899 /* Try to produce the remainder without producing the quotient.
4900 If we seem to have a divmod pattern that does not require widening,
4901 don't try widening here. We should really have a WIDEN argument
4902 to expand_twoval_binop, since what we'd really like to do here is
4903 1) try a mod insn in compute_mode
4904 2) try a divmod insn in compute_mode
4905 3) try a div insn in compute_mode and multiply-subtract to get
4906 remainder
4907 4) try the same things with widening allowed. */
4908 remainder
4909 = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4910 op0, op1, target,
4911 unsignedp,
4912 ((optab_handler (optab2, compute_mode)
4913 != CODE_FOR_nothing)
4914 ? OPTAB_DIRECT : OPTAB_WIDEN));
4915 if (remainder == 0)
4917 /* No luck there. Can we do remainder and divide at once
4918 without a library call? */
4919 remainder = gen_reg_rtx (compute_mode);
4920 if (! expand_twoval_binop ((unsignedp
4921 ? udivmod_optab
4922 : sdivmod_optab),
4923 op0, op1,
4924 NULL_RTX, remainder, unsignedp))
4925 remainder = 0;
4928 if (remainder)
4929 return gen_lowpart (mode, remainder);
4932 /* Produce the quotient. Try a quotient insn, but not a library call.
4933 If we have a divmod in this mode, use it in preference to widening
4934 the div (for this test we assume it will not fail). Note that optab2
4935 is set to the one of the two optabs that the call below will use. */
4936 quotient
4937 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab,
4938 op0, op1, rem_flag ? NULL_RTX : target,
4939 unsignedp,
4940 ((optab_handler (optab2, compute_mode)
4941 != CODE_FOR_nothing)
4942 ? OPTAB_DIRECT : OPTAB_WIDEN));
4944 if (quotient == 0)
4946 /* No luck there. Try a quotient-and-remainder insn,
4947 keeping the quotient alone. */
4948 quotient = gen_reg_rtx (compute_mode);
4949 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab,
4950 op0, op1,
4951 quotient, NULL_RTX, unsignedp))
4953 quotient = 0;
4954 if (! rem_flag)
4955 /* Still no luck. If we are not computing the remainder,
4956 use a library call for the quotient. */
4957 quotient = sign_expand_binop (compute_mode,
4958 udiv_optab, sdiv_optab,
4959 op0, op1, target,
4960 unsignedp, OPTAB_LIB_WIDEN);
4965 if (rem_flag)
4967 if (target && GET_MODE (target) != compute_mode)
4968 target = 0;
4970 if (quotient == 0)
4972 /* No divide instruction either. Use library for remainder. */
4973 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab,
4974 op0, op1, target,
4975 unsignedp, OPTAB_LIB_WIDEN);
4976 /* No remainder function. Try a quotient-and-remainder
4977 function, keeping the remainder. */
4978 if (!remainder)
4980 remainder = gen_reg_rtx (compute_mode);
4981 if (!expand_twoval_binop_libfunc
4982 (unsignedp ? udivmod_optab : sdivmod_optab,
4983 op0, op1,
4984 NULL_RTX, remainder,
4985 unsignedp ? UMOD : MOD))
4986 remainder = NULL_RTX;
4989 else
4991 /* We divided. Now finish doing X - Y * (X / Y). */
4992 remainder = expand_mult (compute_mode, quotient, op1,
4993 NULL_RTX, unsignedp);
4994 remainder = expand_binop (compute_mode, sub_optab, op0,
4995 remainder, target, unsignedp,
4996 OPTAB_LIB_WIDEN);
5000 return gen_lowpart (mode, rem_flag ? remainder : quotient);
5003 /* Return a tree node with data type TYPE, describing the value of X.
5004 Usually this is an VAR_DECL, if there is no obvious better choice.
5005 X may be an expression, however we only support those expressions
5006 generated by loop.c. */
5008 tree
5009 make_tree (tree type, rtx x)
5011 tree t;
5013 switch (GET_CODE (x))
5015 case CONST_INT:
5017 HOST_WIDE_INT hi = 0;
5019 if (INTVAL (x) < 0
5020 && !(TYPE_UNSIGNED (type)
5021 && (GET_MODE_BITSIZE (TYPE_MODE (type))
5022 < HOST_BITS_PER_WIDE_INT)))
5023 hi = -1;
5025 t = build_int_cst_wide (type, INTVAL (x), hi);
5027 return t;
5030 case CONST_DOUBLE:
5031 if (GET_MODE (x) == VOIDmode)
5032 t = build_int_cst_wide (type,
5033 CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x));
5034 else
5036 REAL_VALUE_TYPE d;
5038 REAL_VALUE_FROM_CONST_DOUBLE (d, x);
5039 t = build_real (type, d);
5042 return t;
5044 case CONST_VECTOR:
5046 int units = CONST_VECTOR_NUNITS (x);
5047 tree itype = TREE_TYPE (type);
5048 tree *elts;
5049 int i;
5051 /* Build a tree with vector elements. */
5052 elts = XALLOCAVEC (tree, units);
5053 for (i = units - 1; i >= 0; --i)
5055 rtx elt = CONST_VECTOR_ELT (x, i);
5056 elts[i] = make_tree (itype, elt);
5059 return build_vector (type, elts);
5062 case PLUS:
5063 return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5064 make_tree (type, XEXP (x, 1)));
5066 case MINUS:
5067 return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)),
5068 make_tree (type, XEXP (x, 1)));
5070 case NEG:
5071 return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0)));
5073 case MULT:
5074 return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)),
5075 make_tree (type, XEXP (x, 1)));
5077 case ASHIFT:
5078 return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)),
5079 make_tree (type, XEXP (x, 1)));
5081 case LSHIFTRT:
5082 t = unsigned_type_for (type);
5083 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5084 make_tree (t, XEXP (x, 0)),
5085 make_tree (type, XEXP (x, 1))));
5087 case ASHIFTRT:
5088 t = signed_type_for (type);
5089 return fold_convert (type, build2 (RSHIFT_EXPR, t,
5090 make_tree (t, XEXP (x, 0)),
5091 make_tree (type, XEXP (x, 1))));
5093 case DIV:
5094 if (TREE_CODE (type) != REAL_TYPE)
5095 t = signed_type_for (type);
5096 else
5097 t = type;
5099 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5100 make_tree (t, XEXP (x, 0)),
5101 make_tree (t, XEXP (x, 1))));
5102 case UDIV:
5103 t = unsigned_type_for (type);
5104 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t,
5105 make_tree (t, XEXP (x, 0)),
5106 make_tree (t, XEXP (x, 1))));
5108 case SIGN_EXTEND:
5109 case ZERO_EXTEND:
5110 t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)),
5111 GET_CODE (x) == ZERO_EXTEND);
5112 return fold_convert (type, make_tree (t, XEXP (x, 0)));
5114 case CONST:
5115 return make_tree (type, XEXP (x, 0));
5117 case SYMBOL_REF:
5118 t = SYMBOL_REF_DECL (x);
5119 if (t)
5120 return fold_convert (type, build_fold_addr_expr (t));
5121 /* else fall through. */
5123 default:
5124 t = build_decl (RTL_LOCATION (x), VAR_DECL, NULL_TREE, type);
5126 /* If TYPE is a POINTER_TYPE, we might need to convert X from
5127 address mode to pointer mode. */
5128 if (POINTER_TYPE_P (type))
5129 x = convert_memory_address_addr_space
5130 (TYPE_MODE (type), x, TYPE_ADDR_SPACE (TREE_TYPE (type)));
5132 /* Note that we do *not* use SET_DECL_RTL here, because we do not
5133 want set_decl_rtl to go adjusting REG_ATTRS for this temporary. */
5134 t->decl_with_rtl.rtl = x;
5136 return t;
5140 /* Compute the logical-and of OP0 and OP1, storing it in TARGET
5141 and returning TARGET.
5143 If TARGET is 0, a pseudo-register or constant is returned. */
5146 expand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target)
5148 rtx tem = 0;
5150 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode)
5151 tem = simplify_binary_operation (AND, mode, op0, op1);
5152 if (tem == 0)
5153 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN);
5155 if (target == 0)
5156 target = tem;
5157 else if (tem != target)
5158 emit_move_insn (target, tem);
5159 return target;
5162 /* Helper function for emit_store_flag. */
5163 static rtx
5164 emit_cstore (rtx target, enum insn_code icode, enum rtx_code code,
5165 enum machine_mode mode, enum machine_mode compare_mode,
5166 int unsignedp, rtx x, rtx y, int normalizep,
5167 enum machine_mode target_mode)
5169 struct expand_operand ops[4];
5170 rtx op0, last, comparison, subtarget;
5171 enum machine_mode result_mode = targetm.cstore_mode (icode);
5173 last = get_last_insn ();
5174 x = prepare_operand (icode, x, 2, mode, compare_mode, unsignedp);
5175 y = prepare_operand (icode, y, 3, mode, compare_mode, unsignedp);
5176 if (!x || !y)
5178 delete_insns_since (last);
5179 return NULL_RTX;
5182 if (target_mode == VOIDmode)
5183 target_mode = result_mode;
5184 if (!target)
5185 target = gen_reg_rtx (target_mode);
5187 comparison = gen_rtx_fmt_ee (code, result_mode, x, y);
5189 create_output_operand (&ops[0], optimize ? NULL_RTX : target, result_mode);
5190 create_fixed_operand (&ops[1], comparison);
5191 create_fixed_operand (&ops[2], x);
5192 create_fixed_operand (&ops[3], y);
5193 if (!maybe_expand_insn (icode, 4, ops))
5195 delete_insns_since (last);
5196 return NULL_RTX;
5198 subtarget = ops[0].value;
5200 /* If we are converting to a wider mode, first convert to
5201 TARGET_MODE, then normalize. This produces better combining
5202 opportunities on machines that have a SIGN_EXTRACT when we are
5203 testing a single bit. This mostly benefits the 68k.
5205 If STORE_FLAG_VALUE does not have the sign bit set when
5206 interpreted in MODE, we can do this conversion as unsigned, which
5207 is usually more efficient. */
5208 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (result_mode))
5210 convert_move (target, subtarget,
5211 val_signbit_known_clear_p (result_mode,
5212 STORE_FLAG_VALUE));
5213 op0 = target;
5214 result_mode = target_mode;
5216 else
5217 op0 = subtarget;
5219 /* If we want to keep subexpressions around, don't reuse our last
5220 target. */
5221 if (optimize)
5222 subtarget = 0;
5224 /* Now normalize to the proper value in MODE. Sometimes we don't
5225 have to do anything. */
5226 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE)
5228 /* STORE_FLAG_VALUE might be the most negative number, so write
5229 the comparison this way to avoid a compiler-time warning. */
5230 else if (- normalizep == STORE_FLAG_VALUE)
5231 op0 = expand_unop (result_mode, neg_optab, op0, subtarget, 0);
5233 /* We don't want to use STORE_FLAG_VALUE < 0 below since this makes
5234 it hard to use a value of just the sign bit due to ANSI integer
5235 constant typing rules. */
5236 else if (val_signbit_known_set_p (result_mode, STORE_FLAG_VALUE))
5237 op0 = expand_shift (RSHIFT_EXPR, result_mode, op0,
5238 GET_MODE_BITSIZE (result_mode) - 1, subtarget,
5239 normalizep == 1);
5240 else
5242 gcc_assert (STORE_FLAG_VALUE & 1);
5244 op0 = expand_and (result_mode, op0, const1_rtx, subtarget);
5245 if (normalizep == -1)
5246 op0 = expand_unop (result_mode, neg_optab, op0, op0, 0);
5249 /* If we were converting to a smaller mode, do the conversion now. */
5250 if (target_mode != result_mode)
5252 convert_move (target, op0, 0);
5253 return target;
5255 else
5256 return op0;
5260 /* A subroutine of emit_store_flag only including "tricks" that do not
5261 need a recursive call. These are kept separate to avoid infinite
5262 loops. */
5264 static rtx
5265 emit_store_flag_1 (rtx target, enum rtx_code code, rtx op0, rtx op1,
5266 enum machine_mode mode, int unsignedp, int normalizep,
5267 enum machine_mode target_mode)
5269 rtx subtarget;
5270 enum insn_code icode;
5271 enum machine_mode compare_mode;
5272 enum mode_class mclass;
5273 enum rtx_code scode;
5274 rtx tem;
5276 if (unsignedp)
5277 code = unsigned_condition (code);
5278 scode = swap_condition (code);
5280 /* If one operand is constant, make it the second one. Only do this
5281 if the other operand is not constant as well. */
5283 if (swap_commutative_operands_p (op0, op1))
5285 tem = op0;
5286 op0 = op1;
5287 op1 = tem;
5288 code = swap_condition (code);
5291 if (mode == VOIDmode)
5292 mode = GET_MODE (op0);
5294 /* For some comparisons with 1 and -1, we can convert this to
5295 comparisons with zero. This will often produce more opportunities for
5296 store-flag insns. */
5298 switch (code)
5300 case LT:
5301 if (op1 == const1_rtx)
5302 op1 = const0_rtx, code = LE;
5303 break;
5304 case LE:
5305 if (op1 == constm1_rtx)
5306 op1 = const0_rtx, code = LT;
5307 break;
5308 case GE:
5309 if (op1 == const1_rtx)
5310 op1 = const0_rtx, code = GT;
5311 break;
5312 case GT:
5313 if (op1 == constm1_rtx)
5314 op1 = const0_rtx, code = GE;
5315 break;
5316 case GEU:
5317 if (op1 == const1_rtx)
5318 op1 = const0_rtx, code = NE;
5319 break;
5320 case LTU:
5321 if (op1 == const1_rtx)
5322 op1 = const0_rtx, code = EQ;
5323 break;
5324 default:
5325 break;
5328 /* If we are comparing a double-word integer with zero or -1, we can
5329 convert the comparison into one involving a single word. */
5330 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2
5331 && GET_MODE_CLASS (mode) == MODE_INT
5332 && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0)))
5334 if ((code == EQ || code == NE)
5335 && (op1 == const0_rtx || op1 == constm1_rtx))
5337 rtx op00, op01;
5339 /* Do a logical OR or AND of the two words and compare the
5340 result. */
5341 op00 = simplify_gen_subreg (word_mode, op0, mode, 0);
5342 op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD);
5343 tem = expand_binop (word_mode,
5344 op1 == const0_rtx ? ior_optab : and_optab,
5345 op00, op01, NULL_RTX, unsignedp,
5346 OPTAB_DIRECT);
5348 if (tem != 0)
5349 tem = emit_store_flag (NULL_RTX, code, tem, op1, word_mode,
5350 unsignedp, normalizep);
5352 else if ((code == LT || code == GE) && op1 == const0_rtx)
5354 rtx op0h;
5356 /* If testing the sign bit, can just test on high word. */
5357 op0h = simplify_gen_subreg (word_mode, op0, mode,
5358 subreg_highpart_offset (word_mode,
5359 mode));
5360 tem = emit_store_flag (NULL_RTX, code, op0h, op1, word_mode,
5361 unsignedp, normalizep);
5363 else
5364 tem = NULL_RTX;
5366 if (tem)
5368 if (target_mode == VOIDmode || GET_MODE (tem) == target_mode)
5369 return tem;
5370 if (!target)
5371 target = gen_reg_rtx (target_mode);
5373 convert_move (target, tem,
5374 !val_signbit_known_set_p (word_mode,
5375 (normalizep ? normalizep
5376 : STORE_FLAG_VALUE)));
5377 return target;
5381 /* If this is A < 0 or A >= 0, we can do this by taking the ones
5382 complement of A (for GE) and shifting the sign bit to the low bit. */
5383 if (op1 == const0_rtx && (code == LT || code == GE)
5384 && GET_MODE_CLASS (mode) == MODE_INT
5385 && (normalizep || STORE_FLAG_VALUE == 1
5386 || val_signbit_p (mode, STORE_FLAG_VALUE)))
5388 subtarget = target;
5390 if (!target)
5391 target_mode = mode;
5393 /* If the result is to be wider than OP0, it is best to convert it
5394 first. If it is to be narrower, it is *incorrect* to convert it
5395 first. */
5396 else if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode))
5398 op0 = convert_modes (target_mode, mode, op0, 0);
5399 mode = target_mode;
5402 if (target_mode != mode)
5403 subtarget = 0;
5405 if (code == GE)
5406 op0 = expand_unop (mode, one_cmpl_optab, op0,
5407 ((STORE_FLAG_VALUE == 1 || normalizep)
5408 ? 0 : subtarget), 0);
5410 if (STORE_FLAG_VALUE == 1 || normalizep)
5411 /* If we are supposed to produce a 0/1 value, we want to do
5412 a logical shift from the sign bit to the low-order bit; for
5413 a -1/0 value, we do an arithmetic shift. */
5414 op0 = expand_shift (RSHIFT_EXPR, mode, op0,
5415 GET_MODE_BITSIZE (mode) - 1,
5416 subtarget, normalizep != -1);
5418 if (mode != target_mode)
5419 op0 = convert_modes (target_mode, mode, op0, 0);
5421 return op0;
5424 mclass = GET_MODE_CLASS (mode);
5425 for (compare_mode = mode; compare_mode != VOIDmode;
5426 compare_mode = GET_MODE_WIDER_MODE (compare_mode))
5428 enum machine_mode optab_mode = mclass == MODE_CC ? CCmode : compare_mode;
5429 icode = optab_handler (cstore_optab, optab_mode);
5430 if (icode != CODE_FOR_nothing)
5432 do_pending_stack_adjust ();
5433 tem = emit_cstore (target, icode, code, mode, compare_mode,
5434 unsignedp, op0, op1, normalizep, target_mode);
5435 if (tem)
5436 return tem;
5438 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5440 tem = emit_cstore (target, icode, scode, mode, compare_mode,
5441 unsignedp, op1, op0, normalizep, target_mode);
5442 if (tem)
5443 return tem;
5445 break;
5449 return 0;
5452 /* Emit a store-flags instruction for comparison CODE on OP0 and OP1
5453 and storing in TARGET. Normally return TARGET.
5454 Return 0 if that cannot be done.
5456 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If
5457 it is VOIDmode, they cannot both be CONST_INT.
5459 UNSIGNEDP is for the case where we have to widen the operands
5460 to perform the operation. It says to use zero-extension.
5462 NORMALIZEP is 1 if we should convert the result to be either zero
5463 or one. Normalize is -1 if we should convert the result to be
5464 either zero or -1. If NORMALIZEP is zero, the result will be left
5465 "raw" out of the scc insn. */
5468 emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1,
5469 enum machine_mode mode, int unsignedp, int normalizep)
5471 enum machine_mode target_mode = target ? GET_MODE (target) : VOIDmode;
5472 enum rtx_code rcode;
5473 rtx subtarget;
5474 rtx tem, last, trueval;
5476 /* If we compare constants, we shouldn't use a store-flag operation,
5477 but a constant load. We can get there via the vanilla route that
5478 usually generates a compare-branch sequence, but will in this case
5479 fold the comparison to a constant, and thus elide the branch. */
5480 if (CONSTANT_P (op0) && CONSTANT_P (op1))
5481 return NULL_RTX;
5483 tem = emit_store_flag_1 (target, code, op0, op1, mode, unsignedp, normalizep,
5484 target_mode);
5485 if (tem)
5486 return tem;
5488 /* If we reached here, we can't do this with a scc insn, however there
5489 are some comparisons that can be done in other ways. Don't do any
5490 of these cases if branches are very cheap. */
5491 if (BRANCH_COST (optimize_insn_for_speed_p (), false) == 0)
5492 return 0;
5494 /* See what we need to return. We can only return a 1, -1, or the
5495 sign bit. */
5497 if (normalizep == 0)
5499 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1)
5500 normalizep = STORE_FLAG_VALUE;
5502 else if (val_signbit_p (mode, STORE_FLAG_VALUE))
5504 else
5505 return 0;
5508 last = get_last_insn ();
5510 /* If optimizing, use different pseudo registers for each insn, instead
5511 of reusing the same pseudo. This leads to better CSE, but slows
5512 down the compiler, since there are more pseudos */
5513 subtarget = (!optimize
5514 && (target_mode == mode)) ? target : NULL_RTX;
5515 trueval = GEN_INT (normalizep ? normalizep : STORE_FLAG_VALUE);
5517 /* For floating-point comparisons, try the reverse comparison or try
5518 changing the "orderedness" of the comparison. */
5519 if (GET_MODE_CLASS (mode) == MODE_FLOAT)
5521 enum rtx_code first_code;
5522 bool and_them;
5524 rcode = reverse_condition_maybe_unordered (code);
5525 if (can_compare_p (rcode, mode, ccp_store_flag)
5526 && (code == ORDERED || code == UNORDERED
5527 || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
5528 || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
5530 int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
5531 || (STORE_FLAG_VALUE == -1 && normalizep == 1));
5533 /* For the reverse comparison, use either an addition or a XOR. */
5534 if (want_add
5535 && rtx_cost (GEN_INT (normalizep), PLUS, 1,
5536 optimize_insn_for_speed_p ()) == 0)
5538 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5539 STORE_FLAG_VALUE, target_mode);
5540 if (tem)
5541 return expand_binop (target_mode, add_optab, tem,
5542 gen_int_mode (normalizep, target_mode),
5543 target, 0, OPTAB_WIDEN);
5545 else if (!want_add
5546 && rtx_cost (trueval, XOR, 1,
5547 optimize_insn_for_speed_p ()) == 0)
5549 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5550 normalizep, target_mode);
5551 if (tem)
5552 return expand_binop (target_mode, xor_optab, tem, trueval,
5553 target, INTVAL (trueval) >= 0, OPTAB_WIDEN);
5557 delete_insns_since (last);
5559 /* Cannot split ORDERED and UNORDERED, only try the above trick. */
5560 if (code == ORDERED || code == UNORDERED)
5561 return 0;
5563 and_them = split_comparison (code, mode, &first_code, &code);
5565 /* If there are no NaNs, the first comparison should always fall through.
5566 Effectively change the comparison to the other one. */
5567 if (!HONOR_NANS (mode))
5569 gcc_assert (first_code == (and_them ? ORDERED : UNORDERED));
5570 return emit_store_flag_1 (target, code, op0, op1, mode, 0, normalizep,
5571 target_mode);
5574 #ifdef HAVE_conditional_move
5575 /* Try using a setcc instruction for ORDERED/UNORDERED, followed by a
5576 conditional move. */
5577 tem = emit_store_flag_1 (subtarget, first_code, op0, op1, mode, 0,
5578 normalizep, target_mode);
5579 if (tem == 0)
5580 return 0;
5582 if (and_them)
5583 tem = emit_conditional_move (target, code, op0, op1, mode,
5584 tem, const0_rtx, GET_MODE (tem), 0);
5585 else
5586 tem = emit_conditional_move (target, code, op0, op1, mode,
5587 trueval, tem, GET_MODE (tem), 0);
5589 if (tem == 0)
5590 delete_insns_since (last);
5591 return tem;
5592 #else
5593 return 0;
5594 #endif
5597 /* The remaining tricks only apply to integer comparisons. */
5599 if (GET_MODE_CLASS (mode) != MODE_INT)
5600 return 0;
5602 /* If this is an equality comparison of integers, we can try to exclusive-or
5603 (or subtract) the two operands and use a recursive call to try the
5604 comparison with zero. Don't do any of these cases if branches are
5605 very cheap. */
5607 if ((code == EQ || code == NE) && op1 != const0_rtx)
5609 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1,
5610 OPTAB_WIDEN);
5612 if (tem == 0)
5613 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1,
5614 OPTAB_WIDEN);
5615 if (tem != 0)
5616 tem = emit_store_flag (target, code, tem, const0_rtx,
5617 mode, unsignedp, normalizep);
5618 if (tem != 0)
5619 return tem;
5621 delete_insns_since (last);
5624 /* For integer comparisons, try the reverse comparison. However, for
5625 small X and if we'd have anyway to extend, implementing "X != 0"
5626 as "-(int)X >> 31" is still cheaper than inverting "(int)X == 0". */
5627 rcode = reverse_condition (code);
5628 if (can_compare_p (rcode, mode, ccp_store_flag)
5629 && ! (optab_handler (cstore_optab, mode) == CODE_FOR_nothing
5630 && code == NE
5631 && GET_MODE_SIZE (mode) < UNITS_PER_WORD
5632 && op1 == const0_rtx))
5634 int want_add = ((STORE_FLAG_VALUE == 1 && normalizep == -1)
5635 || (STORE_FLAG_VALUE == -1 && normalizep == 1));
5637 /* Again, for the reverse comparison, use either an addition or a XOR. */
5638 if (want_add
5639 && rtx_cost (GEN_INT (normalizep), PLUS, 1,
5640 optimize_insn_for_speed_p ()) == 0)
5642 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5643 STORE_FLAG_VALUE, target_mode);
5644 if (tem != 0)
5645 tem = expand_binop (target_mode, add_optab, tem,
5646 gen_int_mode (normalizep, target_mode),
5647 target, 0, OPTAB_WIDEN);
5649 else if (!want_add
5650 && rtx_cost (trueval, XOR, 1,
5651 optimize_insn_for_speed_p ()) == 0)
5653 tem = emit_store_flag_1 (subtarget, rcode, op0, op1, mode, 0,
5654 normalizep, target_mode);
5655 if (tem != 0)
5656 tem = expand_binop (target_mode, xor_optab, tem, trueval, target,
5657 INTVAL (trueval) >= 0, OPTAB_WIDEN);
5660 if (tem != 0)
5661 return tem;
5662 delete_insns_since (last);
5665 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with
5666 the constant zero. Reject all other comparisons at this point. Only
5667 do LE and GT if branches are expensive since they are expensive on
5668 2-operand machines. */
5670 if (op1 != const0_rtx
5671 || (code != EQ && code != NE
5672 && (BRANCH_COST (optimize_insn_for_speed_p (),
5673 false) <= 1 || (code != LE && code != GT))))
5674 return 0;
5676 /* Try to put the result of the comparison in the sign bit. Assume we can't
5677 do the necessary operation below. */
5679 tem = 0;
5681 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has
5682 the sign bit set. */
5684 if (code == LE)
5686 /* This is destructive, so SUBTARGET can't be OP0. */
5687 if (rtx_equal_p (subtarget, op0))
5688 subtarget = 0;
5690 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0,
5691 OPTAB_WIDEN);
5692 if (tem)
5693 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0,
5694 OPTAB_WIDEN);
5697 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the
5698 number of bits in the mode of OP0, minus one. */
5700 if (code == GT)
5702 if (rtx_equal_p (subtarget, op0))
5703 subtarget = 0;
5705 tem = expand_shift (RSHIFT_EXPR, mode, op0,
5706 GET_MODE_BITSIZE (mode) - 1,
5707 subtarget, 0);
5708 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0,
5709 OPTAB_WIDEN);
5712 if (code == EQ || code == NE)
5714 /* For EQ or NE, one way to do the comparison is to apply an operation
5715 that converts the operand into a positive number if it is nonzero
5716 or zero if it was originally zero. Then, for EQ, we subtract 1 and
5717 for NE we negate. This puts the result in the sign bit. Then we
5718 normalize with a shift, if needed.
5720 Two operations that can do the above actions are ABS and FFS, so try
5721 them. If that doesn't work, and MODE is smaller than a full word,
5722 we can use zero-extension to the wider mode (an unsigned conversion)
5723 as the operation. */
5725 /* Note that ABS doesn't yield a positive number for INT_MIN, but
5726 that is compensated by the subsequent overflow when subtracting
5727 one / negating. */
5729 if (optab_handler (abs_optab, mode) != CODE_FOR_nothing)
5730 tem = expand_unop (mode, abs_optab, op0, subtarget, 1);
5731 else if (optab_handler (ffs_optab, mode) != CODE_FOR_nothing)
5732 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1);
5733 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD)
5735 tem = convert_modes (word_mode, mode, op0, 1);
5736 mode = word_mode;
5739 if (tem != 0)
5741 if (code == EQ)
5742 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget,
5743 0, OPTAB_WIDEN);
5744 else
5745 tem = expand_unop (mode, neg_optab, tem, subtarget, 0);
5748 /* If we couldn't do it that way, for NE we can "or" the two's complement
5749 of the value with itself. For EQ, we take the one's complement of
5750 that "or", which is an extra insn, so we only handle EQ if branches
5751 are expensive. */
5753 if (tem == 0
5754 && (code == NE
5755 || BRANCH_COST (optimize_insn_for_speed_p (),
5756 false) > 1))
5758 if (rtx_equal_p (subtarget, op0))
5759 subtarget = 0;
5761 tem = expand_unop (mode, neg_optab, op0, subtarget, 0);
5762 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0,
5763 OPTAB_WIDEN);
5765 if (tem && code == EQ)
5766 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0);
5770 if (tem && normalizep)
5771 tem = expand_shift (RSHIFT_EXPR, mode, tem,
5772 GET_MODE_BITSIZE (mode) - 1,
5773 subtarget, normalizep == 1);
5775 if (tem)
5777 if (!target)
5779 else if (GET_MODE (tem) != target_mode)
5781 convert_move (target, tem, 0);
5782 tem = target;
5784 else if (!subtarget)
5786 emit_move_insn (target, tem);
5787 tem = target;
5790 else
5791 delete_insns_since (last);
5793 return tem;
5796 /* Like emit_store_flag, but always succeeds. */
5799 emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1,
5800 enum machine_mode mode, int unsignedp, int normalizep)
5802 rtx tem, label;
5803 rtx trueval, falseval;
5805 /* First see if emit_store_flag can do the job. */
5806 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep);
5807 if (tem != 0)
5808 return tem;
5810 if (!target)
5811 target = gen_reg_rtx (word_mode);
5813 /* If this failed, we have to do this with set/compare/jump/set code.
5814 For foo != 0, if foo is in OP0, just replace it with 1 if nonzero. */
5815 trueval = normalizep ? GEN_INT (normalizep) : const1_rtx;
5816 if (code == NE
5817 && GET_MODE_CLASS (mode) == MODE_INT
5818 && REG_P (target)
5819 && op0 == target
5820 && op1 == const0_rtx)
5822 label = gen_label_rtx ();
5823 do_compare_rtx_and_jump (target, const0_rtx, EQ, unsignedp,
5824 mode, NULL_RTX, NULL_RTX, label, -1);
5825 emit_move_insn (target, trueval);
5826 emit_label (label);
5827 return target;
5830 if (!REG_P (target)
5831 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1))
5832 target = gen_reg_rtx (GET_MODE (target));
5834 /* Jump in the right direction if the target cannot implement CODE
5835 but can jump on its reverse condition. */
5836 falseval = const0_rtx;
5837 if (! can_compare_p (code, mode, ccp_jump)
5838 && (! FLOAT_MODE_P (mode)
5839 || code == ORDERED || code == UNORDERED
5840 || (! HONOR_NANS (mode) && (code == LTGT || code == UNEQ))
5841 || (! HONOR_SNANS (mode) && (code == EQ || code == NE))))
5843 enum rtx_code rcode;
5844 if (FLOAT_MODE_P (mode))
5845 rcode = reverse_condition_maybe_unordered (code);
5846 else
5847 rcode = reverse_condition (code);
5849 /* Canonicalize to UNORDERED for the libcall. */
5850 if (can_compare_p (rcode, mode, ccp_jump)
5851 || (code == ORDERED && ! can_compare_p (ORDERED, mode, ccp_jump)))
5853 falseval = trueval;
5854 trueval = const0_rtx;
5855 code = rcode;
5859 emit_move_insn (target, trueval);
5860 label = gen_label_rtx ();
5861 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX,
5862 NULL_RTX, label, -1);
5864 emit_move_insn (target, falseval);
5865 emit_label (label);
5867 return target;
5870 /* Perform possibly multi-word comparison and conditional jump to LABEL
5871 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE. This is
5872 now a thin wrapper around do_compare_rtx_and_jump. */
5874 static void
5875 do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode,
5876 rtx label)
5878 int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU);
5879 do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode,
5880 NULL_RTX, NULL_RTX, label, -1);