1/* Medium-level subroutines: convert bit-field store and extract 2 and shifts, multiplies and divides to rtl instructions. 3 Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 5 Free Software Foundation, Inc. 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 2, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24 25#include "config.h" 26#include "system.h" 27#include "coretypes.h" 28#include "tm.h" 29#include "toplev.h" 30#include "rtl.h" 31#include "tree.h" 32#include "tm_p.h" 33#include "flags.h" 34#include "insn-config.h" 35#include "expr.h" 36#include "optabs.h" 37#include "real.h" 38#include "recog.h" 39#include "langhooks.h" 40 41static void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT, 42 unsigned HOST_WIDE_INT, 43 unsigned HOST_WIDE_INT, rtx); 44static void store_split_bit_field (rtx, unsigned HOST_WIDE_INT, 45 unsigned HOST_WIDE_INT, rtx); 46static rtx extract_fixed_bit_field (enum machine_mode, rtx, 47 unsigned HOST_WIDE_INT, 48 unsigned HOST_WIDE_INT, 49 unsigned HOST_WIDE_INT, rtx, int); 50static rtx mask_rtx (enum machine_mode, int, int, int); 51static rtx lshift_value (enum machine_mode, rtx, int, int); 52static rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT, 53 unsigned HOST_WIDE_INT, int); 54static void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx); 55static rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT); 56static rtx expand_sdiv_pow2 (enum machine_mode, rtx, HOST_WIDE_INT); 57 58/* Test whether a value is zero of a power of two. */ 59#define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0) 60 61/* Nonzero means divides or modulus operations are relatively cheap for 62 powers of two, so don't use branches; emit the operation instead. 63 Usually, this will mean that the MD file will emit non-branch 64 sequences. */ 65 66static bool sdiv_pow2_cheap[NUM_MACHINE_MODES]; 67static bool smod_pow2_cheap[NUM_MACHINE_MODES]; 68 69#ifndef SLOW_UNALIGNED_ACCESS 70#define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT 71#endif 72 73/* For compilers that support multiple targets with different word sizes, 74 MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example 75 is the H8/300(H) compiler. */ 76 77#ifndef MAX_BITS_PER_WORD 78#define MAX_BITS_PER_WORD BITS_PER_WORD 79#endif 80 81/* Reduce conditional compilation elsewhere. */ 82#ifndef HAVE_insv 83#define HAVE_insv 0 84#define CODE_FOR_insv CODE_FOR_nothing 85#define gen_insv(a,b,c,d) NULL_RTX 86#endif 87#ifndef HAVE_extv 88#define HAVE_extv 0 89#define CODE_FOR_extv CODE_FOR_nothing 90#define gen_extv(a,b,c,d) NULL_RTX 91#endif 92#ifndef HAVE_extzv 93#define HAVE_extzv 0 94#define CODE_FOR_extzv CODE_FOR_nothing 95#define gen_extzv(a,b,c,d) NULL_RTX 96#endif 97 98/* Cost of various pieces of RTL. Note that some of these are indexed by 99 shift count and some by mode. */ 100static int zero_cost; 101static int add_cost[NUM_MACHINE_MODES]; 102static int neg_cost[NUM_MACHINE_MODES]; 103static int shift_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 104static int shiftadd_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 105static int shiftsub_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 106static int mul_cost[NUM_MACHINE_MODES]; 107static int div_cost[NUM_MACHINE_MODES]; 108static int mul_widen_cost[NUM_MACHINE_MODES]; 109static int mul_highpart_cost[NUM_MACHINE_MODES]; 110 111void 112init_expmed (void) 113{ 114 struct 115 { 116 struct rtx_def reg; rtunion reg_fld[2]; 117 struct rtx_def plus; rtunion plus_fld1; 118 struct rtx_def neg; 119 struct rtx_def udiv; rtunion udiv_fld1; 120 struct rtx_def mult; rtunion mult_fld1; 121 struct rtx_def div; rtunion div_fld1; 122 struct rtx_def mod; rtunion mod_fld1; 123 struct rtx_def zext; 124 struct rtx_def wide_mult; rtunion wide_mult_fld1; 125 struct rtx_def wide_lshr; rtunion wide_lshr_fld1; 126 struct rtx_def wide_trunc; 127 struct rtx_def shift; rtunion shift_fld1; 128 struct rtx_def shift_mult; rtunion shift_mult_fld1; 129 struct rtx_def shift_add; rtunion shift_add_fld1; 130 struct rtx_def shift_sub; rtunion shift_sub_fld1; 131 } all; 132 133 rtx pow2[MAX_BITS_PER_WORD]; 134 rtx cint[MAX_BITS_PER_WORD]; 135 int m, n; 136 enum machine_mode mode, wider_mode; 137 138 zero_cost = rtx_cost (const0_rtx, 0); 139 140 for (m = 1; m < MAX_BITS_PER_WORD; m++) 141 { 142 pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m); 143 cint[m] = GEN_INT (m); 144 } 145 146 memset (&all, 0, sizeof all); 147 148 PUT_CODE (&all.reg, REG); 149 /* Avoid using hard regs in ways which may be unsupported. */ 150 REGNO (&all.reg) = LAST_VIRTUAL_REGISTER + 1; 151 152 PUT_CODE (&all.plus, PLUS); 153 XEXP (&all.plus, 0) = &all.reg; 154 XEXP (&all.plus, 1) = &all.reg; 155 156 PUT_CODE (&all.neg, NEG); 157 XEXP (&all.neg, 0) = &all.reg; 158 159 PUT_CODE (&all.udiv, UDIV); 160 XEXP (&all.udiv, 0) = &all.reg; 161 XEXP (&all.udiv, 1) = &all.reg; 162 163 PUT_CODE (&all.mult, MULT); 164 XEXP (&all.mult, 0) = &all.reg; 165 XEXP (&all.mult, 1) = &all.reg; 166 167 PUT_CODE (&all.div, DIV); 168 XEXP (&all.div, 0) = &all.reg; 169 XEXP (&all.div, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32); 170 171 PUT_CODE (&all.mod, MOD); 172 XEXP (&all.mod, 0) = &all.reg; 173 XEXP (&all.mod, 1) = XEXP (&all.div, 1); 174 175 PUT_CODE (&all.zext, ZERO_EXTEND); 176 XEXP (&all.zext, 0) = &all.reg; 177 178 PUT_CODE (&all.wide_mult, MULT); 179 XEXP (&all.wide_mult, 0) = &all.zext; 180 XEXP (&all.wide_mult, 1) = &all.zext; 181 182 PUT_CODE (&all.wide_lshr, LSHIFTRT); 183 XEXP (&all.wide_lshr, 0) = &all.wide_mult; 184 185 PUT_CODE (&all.wide_trunc, TRUNCATE); 186 XEXP (&all.wide_trunc, 0) = &all.wide_lshr; 187 188 PUT_CODE (&all.shift, ASHIFT); 189 XEXP (&all.shift, 0) = &all.reg; 190 191 PUT_CODE (&all.shift_mult, MULT); 192 XEXP (&all.shift_mult, 0) = &all.reg; 193 194 PUT_CODE (&all.shift_add, PLUS); 195 XEXP (&all.shift_add, 0) = &all.shift_mult; 196 XEXP (&all.shift_add, 1) = &all.reg; 197 198 PUT_CODE (&all.shift_sub, MINUS); 199 XEXP (&all.shift_sub, 0) = &all.shift_mult; 200 XEXP (&all.shift_sub, 1) = &all.reg; 201 202 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); 203 mode != VOIDmode; 204 mode = GET_MODE_WIDER_MODE (mode)) 205 { 206 PUT_MODE (&all.reg, mode); 207 PUT_MODE (&all.plus, mode); 208 PUT_MODE (&all.neg, mode); 209 PUT_MODE (&all.udiv, mode); 210 PUT_MODE (&all.mult, mode); 211 PUT_MODE (&all.div, mode); 212 PUT_MODE (&all.mod, mode); 213 PUT_MODE (&all.wide_trunc, mode); 214 PUT_MODE (&all.shift, mode); 215 PUT_MODE (&all.shift_mult, mode); 216 PUT_MODE (&all.shift_add, mode); 217 PUT_MODE (&all.shift_sub, mode); 218 219 add_cost[mode] = rtx_cost (&all.plus, SET); 220 neg_cost[mode] = rtx_cost (&all.neg, SET); 221 div_cost[mode] = rtx_cost (&all.udiv, SET); 222 mul_cost[mode] = rtx_cost (&all.mult, SET); 223 224 sdiv_pow2_cheap[mode] = (rtx_cost (&all.div, SET) <= 2 * add_cost[mode]); 225 smod_pow2_cheap[mode] = (rtx_cost (&all.mod, SET) <= 4 * add_cost[mode]); 226 227 wider_mode = GET_MODE_WIDER_MODE (mode); 228 if (wider_mode != VOIDmode) 229 { 230 PUT_MODE (&all.zext, wider_mode); 231 PUT_MODE (&all.wide_mult, wider_mode); 232 PUT_MODE (&all.wide_lshr, wider_mode); 233 XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode)); 234 235 mul_widen_cost[wider_mode] = rtx_cost (&all.wide_mult, SET); 236 mul_highpart_cost[mode] = rtx_cost (&all.wide_trunc, SET); 237 } 238 239 shift_cost[mode][0] = 0; 240 shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode]; 241 242 n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode)); 243 for (m = 1; m < n; m++) 244 { 245 XEXP (&all.shift, 1) = cint[m]; 246 XEXP (&all.shift_mult, 1) = pow2[m]; 247 248 shift_cost[mode][m] = rtx_cost (&all.shift, SET); 249 shiftadd_cost[mode][m] = rtx_cost (&all.shift_add, SET); 250 shiftsub_cost[mode][m] = rtx_cost (&all.shift_sub, SET); 251 } 252 } 253} 254 255/* Return an rtx representing minus the value of X. 256 MODE is the intended mode of the result, 257 useful if X is a CONST_INT. */ 258 259rtx 260negate_rtx (enum machine_mode mode, rtx x) 261{ 262 rtx result = simplify_unary_operation (NEG, mode, x, mode); 263 264 if (result == 0) 265 result = expand_unop (mode, neg_optab, x, NULL_RTX, 0); 266 267 return result; 268} 269 270/* Report on the availability of insv/extv/extzv and the desired mode 271 of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo 272 is false; else the mode of the specified operand. If OPNO is -1, 273 all the caller cares about is whether the insn is available. */ 274enum machine_mode 275mode_for_extraction (enum extraction_pattern pattern, int opno) 276{ 277 const struct insn_data *data; 278 279 switch (pattern) 280 { 281 case EP_insv: 282 if (HAVE_insv) 283 { 284 data = &insn_data[CODE_FOR_insv]; 285 break; 286 } 287 return MAX_MACHINE_MODE; 288 289 case EP_extv: 290 if (HAVE_extv) 291 { 292 data = &insn_data[CODE_FOR_extv]; 293 break; 294 } 295 return MAX_MACHINE_MODE; 296 297 case EP_extzv: 298 if (HAVE_extzv) 299 { 300 data = &insn_data[CODE_FOR_extzv]; 301 break; 302 } 303 return MAX_MACHINE_MODE; 304 305 default: 306 gcc_unreachable (); 307 } 308 309 if (opno == -1) 310 return VOIDmode; 311 312 /* Everyone who uses this function used to follow it with 313 if (result == VOIDmode) result = word_mode; */ 314 if (data->operand[opno].mode == VOIDmode) 315 return word_mode; 316 return data->operand[opno].mode; 317} 318 319 320/* Generate code to store value from rtx VALUE 321 into a bit-field within structure STR_RTX 322 containing BITSIZE bits starting at bit BITNUM. 323 FIELDMODE is the machine-mode of the FIELD_DECL node for this field. 324 ALIGN is the alignment that STR_RTX is known to have. 325 TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */ 326 327/* ??? Note that there are two different ideas here for how 328 to determine the size to count bits within, for a register. 329 One is BITS_PER_WORD, and the other is the size of operand 3 330 of the insv pattern. 331 332 If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD 333 else, we use the mode of operand 3. */ 334 335rtx 336store_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize, 337 unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode, 338 rtx value) 339{ 340 unsigned int unit 341 = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD; 342 unsigned HOST_WIDE_INT offset, bitpos; 343 rtx op0 = str_rtx; 344 int byte_offset; 345 rtx orig_value; 346 347 enum machine_mode op_mode = mode_for_extraction (EP_insv, 3); 348 349 while (GET_CODE (op0) == SUBREG) 350 { 351 /* The following line once was done only if WORDS_BIG_ENDIAN, 352 but I think that is a mistake. WORDS_BIG_ENDIAN is 353 meaningful at a much higher level; when structures are copied 354 between memory and regs, the higher-numbered regs 355 always get higher addresses. */ 356 int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))); 357 int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0)); 358 359 byte_offset = 0; 360 361 /* Paradoxical subregs need special handling on big endian machines. */ 362 if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size) 363 { 364 int difference = inner_mode_size - outer_mode_size; 365 366 if (WORDS_BIG_ENDIAN) 367 byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD; 368 if (BYTES_BIG_ENDIAN) 369 byte_offset += difference % UNITS_PER_WORD; 370 } 371 else 372 byte_offset = SUBREG_BYTE (op0); 373 374 bitnum += byte_offset * BITS_PER_UNIT; 375 op0 = SUBREG_REG (op0); 376 } 377 378 /* No action is needed if the target is a register and if the field 379 lies completely outside that register. This can occur if the source 380 code contains an out-of-bounds access to a small array. */ 381 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0))) 382 return value; 383 384 /* Use vec_set patterns for inserting parts of vectors whenever 385 available. */ 386 if (VECTOR_MODE_P (GET_MODE (op0)) 387 && !MEM_P (op0) 388 && (vec_set_optab->handlers[GET_MODE (op0)].insn_code 389 != CODE_FOR_nothing) 390 && fieldmode == GET_MODE_INNER (GET_MODE (op0)) 391 && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))) 392 && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))))) 393 { 394 enum machine_mode outermode = GET_MODE (op0); 395 enum machine_mode innermode = GET_MODE_INNER (outermode); 396 int icode = (int) vec_set_optab->handlers[outermode].insn_code; 397 int pos = bitnum / GET_MODE_BITSIZE (innermode); 398 rtx rtxpos = GEN_INT (pos); 399 rtx src = value; 400 rtx dest = op0; 401 rtx pat, seq; 402 enum machine_mode mode0 = insn_data[icode].operand[0].mode; 403 enum machine_mode mode1 = insn_data[icode].operand[1].mode; 404 enum machine_mode mode2 = insn_data[icode].operand[2].mode; 405 406 start_sequence (); 407 408 if (! (*insn_data[icode].operand[1].predicate) (src, mode1)) 409 src = copy_to_mode_reg (mode1, src); 410 411 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)) 412 rtxpos = copy_to_mode_reg (mode1, rtxpos); 413 414 /* We could handle this, but we should always be called with a pseudo 415 for our targets and all insns should take them as outputs. */ 416 gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0) 417 && (*insn_data[icode].operand[1].predicate) (src, mode1) 418 && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)); 419 pat = GEN_FCN (icode) (dest, src, rtxpos); 420 seq = get_insns (); 421 end_sequence (); 422 if (pat) 423 { 424 emit_insn (seq); 425 emit_insn (pat); 426 return dest; 427 } 428 } 429 430 /* If the target is a register, overwriting the entire object, or storing 431 a full-word or multi-word field can be done with just a SUBREG. 432 433 If the target is memory, storing any naturally aligned field can be 434 done with a simple store. For targets that support fast unaligned 435 memory, any naturally sized, unit aligned field can be done directly. */ 436 437 offset = bitnum / unit; 438 bitpos = bitnum % unit; 439 byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT 440 + (offset * UNITS_PER_WORD); 441 442 if (bitpos == 0 443 && bitsize == GET_MODE_BITSIZE (fieldmode) 444 && (!MEM_P (op0) 445 ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD 446 || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode)) 447 && byte_offset % GET_MODE_SIZE (fieldmode) == 0) 448 : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0)) 449 || (offset * BITS_PER_UNIT % bitsize == 0 450 && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0)))) 451 { 452 if (MEM_P (op0)) 453 op0 = adjust_address (op0, fieldmode, offset); 454 else if (GET_MODE (op0) != fieldmode) 455 op0 = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0), 456 byte_offset); 457 emit_move_insn (op0, value); 458 return value; 459 } 460 461 /* Make sure we are playing with integral modes. Pun with subregs 462 if we aren't. This must come after the entire register case above, 463 since that case is valid for any mode. The following cases are only 464 valid for integral modes. */ 465 { 466 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0)); 467 if (imode != GET_MODE (op0)) 468 { 469 if (MEM_P (op0)) 470 op0 = adjust_address (op0, imode, 0); 471 else 472 { 473 gcc_assert (imode != BLKmode); 474 op0 = gen_lowpart (imode, op0); 475 } 476 } 477 } 478 479 /* We may be accessing data outside the field, which means 480 we can alias adjacent data. */ 481 if (MEM_P (op0)) 482 { 483 op0 = shallow_copy_rtx (op0); 484 set_mem_alias_set (op0, 0); 485 set_mem_expr (op0, 0); 486 } 487 488 /* If OP0 is a register, BITPOS must count within a word. 489 But as we have it, it counts within whatever size OP0 now has. 490 On a bigendian machine, these are not the same, so convert. */ 491 if (BYTES_BIG_ENDIAN 492 && !MEM_P (op0) 493 && unit > GET_MODE_BITSIZE (GET_MODE (op0))) 494 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0)); 495 496 /* Storing an lsb-aligned field in a register 497 can be done with a movestrict instruction. */ 498 499 if (!MEM_P (op0) 500 && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0) 501 && bitsize == GET_MODE_BITSIZE (fieldmode) 502 && (movstrict_optab->handlers[fieldmode].insn_code 503 != CODE_FOR_nothing)) 504 { 505 int icode = movstrict_optab->handlers[fieldmode].insn_code; 506 507 /* Get appropriate low part of the value being stored. */ 508 if (GET_CODE (value) == CONST_INT || REG_P (value)) 509 value = gen_lowpart (fieldmode, value); 510 else if (!(GET_CODE (value) == SYMBOL_REF 511 || GET_CODE (value) == LABEL_REF 512 || GET_CODE (value) == CONST)) 513 value = convert_to_mode (fieldmode, value, 0); 514 515 if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode)) 516 value = copy_to_mode_reg (fieldmode, value); 517 518 if (GET_CODE (op0) == SUBREG) 519 { 520 /* Else we've got some float mode source being extracted into 521 a different float mode destination -- this combination of 522 subregs results in Severe Tire Damage. */ 523 gcc_assert (GET_MODE (SUBREG_REG (op0)) == fieldmode 524 || GET_MODE_CLASS (fieldmode) == MODE_INT 525 || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT); 526 op0 = SUBREG_REG (op0); 527 } 528 529 emit_insn (GEN_FCN (icode) 530 (gen_rtx_SUBREG (fieldmode, op0, 531 (bitnum % BITS_PER_WORD) / BITS_PER_UNIT 532 + (offset * UNITS_PER_WORD)), 533 value)); 534 535 return value; 536 } 537 538 /* Handle fields bigger than a word. */ 539 540 if (bitsize > BITS_PER_WORD) 541 { 542 /* Here we transfer the words of the field 543 in the order least significant first. 544 This is because the most significant word is the one which may 545 be less than full. 546 However, only do that if the value is not BLKmode. */ 547 548 unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode; 549 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD; 550 unsigned int i; 551 552 /* This is the mode we must force value to, so that there will be enough 553 subwords to extract. Note that fieldmode will often (always?) be 554 VOIDmode, because that is what store_field uses to indicate that this 555 is a bit field, but passing VOIDmode to operand_subword_force 556 is not allowed. */ 557 fieldmode = GET_MODE (value); 558 if (fieldmode == VOIDmode) 559 fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT); 560 561 for (i = 0; i < nwords; i++) 562 { 563 /* If I is 0, use the low-order word in both field and target; 564 if I is 1, use the next to lowest word; and so on. */ 565 unsigned int wordnum = (backwards ? nwords - i - 1 : i); 566 unsigned int bit_offset = (backwards 567 ? MAX ((int) bitsize - ((int) i + 1) 568 * BITS_PER_WORD, 569 0) 570 : (int) i * BITS_PER_WORD); 571 572 store_bit_field (op0, MIN (BITS_PER_WORD, 573 bitsize - i * BITS_PER_WORD), 574 bitnum + bit_offset, word_mode, 575 operand_subword_force (value, wordnum, fieldmode)); 576 } 577 return value; 578 } 579 580 /* From here on we can assume that the field to be stored in is 581 a full-word (whatever type that is), since it is shorter than a word. */ 582 583 /* OFFSET is the number of words or bytes (UNIT says which) 584 from STR_RTX to the first word or byte containing part of the field. */ 585 586 if (!MEM_P (op0)) 587 { 588 if (offset != 0 589 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD) 590 { 591 if (!REG_P (op0)) 592 { 593 /* Since this is a destination (lvalue), we can't copy 594 it to a pseudo. We can remove a SUBREG that does not 595 change the size of the operand. Such a SUBREG may 596 have been added above. */ 597 gcc_assert (GET_CODE (op0) == SUBREG 598 && (GET_MODE_SIZE (GET_MODE (op0)) 599 == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))); 600 op0 = SUBREG_REG (op0); 601 } 602 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0), 603 op0, (offset * UNITS_PER_WORD)); 604 } 605 offset = 0; 606 } 607 608 /* If VALUE has a floating-point or complex mode, access it as an 609 integer of the corresponding size. This can occur on a machine 610 with 64 bit registers that uses SFmode for float. It can also 611 occur for unaligned float or complex fields. */ 612 orig_value = value; 613 if (GET_MODE (value) != VOIDmode 614 && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT 615 && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT) 616 { 617 value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value))); 618 emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value); 619 } 620 621 /* Now OFFSET is nonzero only if OP0 is memory 622 and is therefore always measured in bytes. */ 623 624 if (HAVE_insv 625 && GET_MODE (value) != BLKmode 626 && !(bitsize == 1 && GET_CODE (value) == CONST_INT) 627 && bitsize > 0 628 && GET_MODE_BITSIZE (op_mode) >= bitsize 629 && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 630 && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))) 631 && insn_data[CODE_FOR_insv].operand[1].predicate (GEN_INT (bitsize), 632 VOIDmode)) 633 { 634 int xbitpos = bitpos; 635 rtx value1; 636 rtx xop0 = op0; 637 rtx last = get_last_insn (); 638 rtx pat; 639 enum machine_mode maxmode = mode_for_extraction (EP_insv, 3); 640 int save_volatile_ok = volatile_ok; 641 642 volatile_ok = 1; 643 644 /* If this machine's insv can only insert into a register, copy OP0 645 into a register and save it back later. */ 646 if (MEM_P (op0) 647 && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate) 648 (op0, VOIDmode))) 649 { 650 rtx tempreg; 651 enum machine_mode bestmode; 652 653 /* Get the mode to use for inserting into this field. If OP0 is 654 BLKmode, get the smallest mode consistent with the alignment. If 655 OP0 is a non-BLKmode object that is no wider than MAXMODE, use its 656 mode. Otherwise, use the smallest mode containing the field. */ 657 658 if (GET_MODE (op0) == BLKmode 659 || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode)) 660 bestmode 661 = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode, 662 MEM_VOLATILE_P (op0)); 663 else 664 bestmode = GET_MODE (op0); 665 666 if (bestmode == VOIDmode 667 || GET_MODE_SIZE (bestmode) < GET_MODE_SIZE (fieldmode) 668 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0)) 669 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0))) 670 goto insv_loses; 671 672 /* Adjust address to point to the containing unit of that mode. 673 Compute offset as multiple of this unit, counting in bytes. */ 674 unit = GET_MODE_BITSIZE (bestmode); 675 offset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 676 bitpos = bitnum % unit; 677 op0 = adjust_address (op0, bestmode, offset); 678 679 /* Fetch that unit, store the bitfield in it, then store 680 the unit. */ 681 tempreg = copy_to_reg (op0); 682 store_bit_field (tempreg, bitsize, bitpos, fieldmode, orig_value); 683 emit_move_insn (op0, tempreg); 684 return value; 685 } 686 volatile_ok = save_volatile_ok; 687 688 /* Add OFFSET into OP0's address. */ 689 if (MEM_P (xop0)) 690 xop0 = adjust_address (xop0, byte_mode, offset); 691 692 /* If xop0 is a register, we need it in MAXMODE 693 to make it acceptable to the format of insv. */ 694 if (GET_CODE (xop0) == SUBREG) 695 /* We can't just change the mode, because this might clobber op0, 696 and we will need the original value of op0 if insv fails. */ 697 xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0)); 698 if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 699 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 700 701 /* On big-endian machines, we count bits from the most significant. 702 If the bit field insn does not, we must invert. */ 703 704 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 705 xbitpos = unit - bitsize - xbitpos; 706 707 /* We have been counting XBITPOS within UNIT. 708 Count instead within the size of the register. */ 709 if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 710 xbitpos += GET_MODE_BITSIZE (maxmode) - unit; 711 712 unit = GET_MODE_BITSIZE (maxmode); 713 714 /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */ 715 value1 = value; 716 if (GET_MODE (value) != maxmode) 717 { 718 if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize) 719 { 720 /* Optimization: Don't bother really extending VALUE 721 if it has all the bits we will actually use. However, 722 if we must narrow it, be sure we do it correctly. */ 723 724 if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode)) 725 { 726 rtx tmp; 727 728 tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0); 729 if (! tmp) 730 tmp = simplify_gen_subreg (maxmode, 731 force_reg (GET_MODE (value), 732 value1), 733 GET_MODE (value), 0); 734 value1 = tmp; 735 } 736 else 737 value1 = gen_lowpart (maxmode, value1); 738 } 739 else if (GET_CODE (value) == CONST_INT) 740 value1 = gen_int_mode (INTVAL (value), maxmode); 741 else 742 /* Parse phase is supposed to make VALUE's data type 743 match that of the component reference, which is a type 744 at least as wide as the field; so VALUE should have 745 a mode that corresponds to that type. */ 746 gcc_assert (CONSTANT_P (value)); 747 } 748 749 /* If this machine's insv insists on a register, 750 get VALUE1 into a register. */ 751 if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate) 752 (value1, maxmode))) 753 value1 = force_reg (maxmode, value1); 754 755 pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1); 756 if (pat) 757 emit_insn (pat); 758 else 759 { 760 delete_insns_since (last); 761 store_fixed_bit_field (op0, offset, bitsize, bitpos, value); 762 } 763 } 764 else 765 insv_loses: 766 /* Insv is not available; store using shifts and boolean ops. */ 767 store_fixed_bit_field (op0, offset, bitsize, bitpos, value); 768 return value; 769} 770 771/* Use shifts and boolean operations to store VALUE 772 into a bit field of width BITSIZE 773 in a memory location specified by OP0 except offset by OFFSET bytes. 774 (OFFSET must be 0 if OP0 is a register.) 775 The field starts at position BITPOS within the byte. 776 (If OP0 is a register, it may be a full word or a narrower mode, 777 but BITPOS still counts within a full word, 778 which is significant on bigendian machines.) */ 779 780static void 781store_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset, 782 unsigned HOST_WIDE_INT bitsize, 783 unsigned HOST_WIDE_INT bitpos, rtx value) 784{ 785 enum machine_mode mode; 786 unsigned int total_bits = BITS_PER_WORD; 787 rtx temp; 788 int all_zero = 0; 789 int all_one = 0; 790 791 /* There is a case not handled here: 792 a structure with a known alignment of just a halfword 793 and a field split across two aligned halfwords within the structure. 794 Or likewise a structure with a known alignment of just a byte 795 and a field split across two bytes. 796 Such cases are not supposed to be able to occur. */ 797 798 if (REG_P (op0) || GET_CODE (op0) == SUBREG) 799 { 800 gcc_assert (!offset); 801 /* Special treatment for a bit field split across two registers. */ 802 if (bitsize + bitpos > BITS_PER_WORD) 803 { 804 store_split_bit_field (op0, bitsize, bitpos, value); 805 return; 806 } 807 } 808 else 809 { 810 /* Get the proper mode to use for this field. We want a mode that 811 includes the entire field. If such a mode would be larger than 812 a word, we won't be doing the extraction the normal way. 813 We don't want a mode bigger than the destination. */ 814 815 mode = GET_MODE (op0); 816 if (GET_MODE_BITSIZE (mode) == 0 817 || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode)) 818 mode = word_mode; 819 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT, 820 MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0)); 821 822 if (mode == VOIDmode) 823 { 824 /* The only way this should occur is if the field spans word 825 boundaries. */ 826 store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT, 827 value); 828 return; 829 } 830 831 total_bits = GET_MODE_BITSIZE (mode); 832 833 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to 834 be in the range 0 to total_bits-1, and put any excess bytes in 835 OFFSET. */ 836 if (bitpos >= total_bits) 837 { 838 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT); 839 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT) 840 * BITS_PER_UNIT); 841 } 842 843 /* Get ref to an aligned byte, halfword, or word containing the field. 844 Adjust BITPOS to be position within a word, 845 and OFFSET to be the offset of that word. 846 Then alter OP0 to refer to that word. */ 847 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT; 848 offset -= (offset % (total_bits / BITS_PER_UNIT)); 849 op0 = adjust_address (op0, mode, offset); 850 } 851 852 mode = GET_MODE (op0); 853 854 /* Now MODE is either some integral mode for a MEM as OP0, 855 or is a full-word for a REG as OP0. TOTAL_BITS corresponds. 856 The bit field is contained entirely within OP0. 857 BITPOS is the starting bit number within OP0. 858 (OP0's mode may actually be narrower than MODE.) */ 859 860 if (BYTES_BIG_ENDIAN) 861 /* BITPOS is the distance between our msb 862 and that of the containing datum. 863 Convert it to the distance from the lsb. */ 864 bitpos = total_bits - bitsize - bitpos; 865 866 /* Now BITPOS is always the distance between our lsb 867 and that of OP0. */ 868 869 /* Shift VALUE left by BITPOS bits. If VALUE is not constant, 870 we must first convert its mode to MODE. */ 871 872 if (GET_CODE (value) == CONST_INT) 873 { 874 HOST_WIDE_INT v = INTVAL (value); 875 876 if (bitsize < HOST_BITS_PER_WIDE_INT) 877 v &= ((HOST_WIDE_INT) 1 << bitsize) - 1; 878 879 if (v == 0) 880 all_zero = 1; 881 else if ((bitsize < HOST_BITS_PER_WIDE_INT 882 && v == ((HOST_WIDE_INT) 1 << bitsize) - 1) 883 || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1)) 884 all_one = 1; 885 886 value = lshift_value (mode, value, bitpos, bitsize); 887 } 888 else 889 { 890 int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize 891 && bitpos + bitsize != GET_MODE_BITSIZE (mode)); 892 893 if (GET_MODE (value) != mode) 894 { 895 if ((REG_P (value) || GET_CODE (value) == SUBREG) 896 && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value))) 897 value = gen_lowpart (mode, value); 898 else 899 value = convert_to_mode (mode, value, 1); 900 } 901 902 if (must_and) 903 value = expand_binop (mode, and_optab, value, 904 mask_rtx (mode, 0, bitsize, 0), 905 NULL_RTX, 1, OPTAB_LIB_WIDEN); 906 if (bitpos > 0) 907 value = expand_shift (LSHIFT_EXPR, mode, value, 908 build_int_cst (NULL_TREE, bitpos), NULL_RTX, 1); 909 } 910 911 /* Now clear the chosen bits in OP0, 912 except that if VALUE is -1 we need not bother. */ 913 /* We keep the intermediates in registers to allow CSE to combine 914 consecutive bitfield assignments. */ 915 916 temp = force_reg (mode, op0); 917 918 if (! all_one) 919 { 920 temp = expand_binop (mode, and_optab, temp, 921 mask_rtx (mode, bitpos, bitsize, 1), 922 NULL_RTX, 1, OPTAB_LIB_WIDEN); 923 temp = force_reg (mode, temp); 924 } 925 926 /* Now logical-or VALUE into OP0, unless it is zero. */ 927 928 if (! all_zero) 929 { 930 temp = expand_binop (mode, ior_optab, temp, value, 931 NULL_RTX, 1, OPTAB_LIB_WIDEN); 932 temp = force_reg (mode, temp); 933 } 934 935 if (op0 != temp) 936 emit_move_insn (op0, temp); 937} 938 939/* Store a bit field that is split across multiple accessible memory objects. 940 941 OP0 is the REG, SUBREG or MEM rtx for the first of the objects. 942 BITSIZE is the field width; BITPOS the position of its first bit 943 (within the word). 944 VALUE is the value to store. 945 946 This does not yet handle fields wider than BITS_PER_WORD. */ 947 948static void 949store_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 950 unsigned HOST_WIDE_INT bitpos, rtx value) 951{ 952 unsigned int unit; 953 unsigned int bitsdone = 0; 954 955 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that 956 much at a time. */ 957 if (REG_P (op0) || GET_CODE (op0) == SUBREG) 958 unit = BITS_PER_WORD; 959 else 960 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD); 961 962 /* If VALUE is a constant other than a CONST_INT, get it into a register in 963 WORD_MODE. If we can do this using gen_lowpart_common, do so. Note 964 that VALUE might be a floating-point constant. */ 965 if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT) 966 { 967 rtx word = gen_lowpart_common (word_mode, value); 968 969 if (word && (value != word)) 970 value = word; 971 else 972 value = gen_lowpart_common (word_mode, 973 force_reg (GET_MODE (value) != VOIDmode 974 ? GET_MODE (value) 975 : word_mode, value)); 976 } 977 978 while (bitsdone < bitsize) 979 { 980 unsigned HOST_WIDE_INT thissize; 981 rtx part, word; 982 unsigned HOST_WIDE_INT thispos; 983 unsigned HOST_WIDE_INT offset; 984 985 offset = (bitpos + bitsdone) / unit; 986 thispos = (bitpos + bitsdone) % unit; 987 988 /* THISSIZE must not overrun a word boundary. Otherwise, 989 store_fixed_bit_field will call us again, and we will mutually 990 recurse forever. */ 991 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD); 992 thissize = MIN (thissize, unit - thispos); 993 994 if (BYTES_BIG_ENDIAN) 995 { 996 int total_bits; 997 998 /* We must do an endian conversion exactly the same way as it is 999 done in extract_bit_field, so that the two calls to 1000 extract_fixed_bit_field will have comparable arguments. */ 1001 if (!MEM_P (value) || GET_MODE (value) == BLKmode) 1002 total_bits = BITS_PER_WORD; 1003 else 1004 total_bits = GET_MODE_BITSIZE (GET_MODE (value)); 1005 1006 /* Fetch successively less significant portions. */ 1007 if (GET_CODE (value) == CONST_INT) 1008 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value)) 1009 >> (bitsize - bitsdone - thissize)) 1010 & (((HOST_WIDE_INT) 1 << thissize) - 1)); 1011 else 1012 /* The args are chosen so that the last part includes the 1013 lsb. Give extract_bit_field the value it needs (with 1014 endianness compensation) to fetch the piece we want. */ 1015 part = extract_fixed_bit_field (word_mode, value, 0, thissize, 1016 total_bits - bitsize + bitsdone, 1017 NULL_RTX, 1); 1018 } 1019 else 1020 { 1021 /* Fetch successively more significant portions. */ 1022 if (GET_CODE (value) == CONST_INT) 1023 part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value)) 1024 >> bitsdone) 1025 & (((HOST_WIDE_INT) 1 << thissize) - 1)); 1026 else 1027 part = extract_fixed_bit_field (word_mode, value, 0, thissize, 1028 bitsdone, NULL_RTX, 1); 1029 } 1030 1031 /* If OP0 is a register, then handle OFFSET here. 1032 1033 When handling multiword bitfields, extract_bit_field may pass 1034 down a word_mode SUBREG of a larger REG for a bitfield that actually 1035 crosses a word boundary. Thus, for a SUBREG, we must find 1036 the current word starting from the base register. */ 1037 if (GET_CODE (op0) == SUBREG) 1038 { 1039 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset; 1040 word = operand_subword_force (SUBREG_REG (op0), word_offset, 1041 GET_MODE (SUBREG_REG (op0))); 1042 offset = 0; 1043 } 1044 else if (REG_P (op0)) 1045 { 1046 word = operand_subword_force (op0, offset, GET_MODE (op0)); 1047 offset = 0; 1048 } 1049 else 1050 word = op0; 1051 1052 /* OFFSET is in UNITs, and UNIT is in bits. 1053 store_fixed_bit_field wants offset in bytes. */ 1054 store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize, 1055 thispos, part); 1056 bitsdone += thissize; 1057 } 1058} 1059 1060/* Generate code to extract a byte-field from STR_RTX 1061 containing BITSIZE bits, starting at BITNUM, 1062 and put it in TARGET if possible (if TARGET is nonzero). 1063 Regardless of TARGET, we return the rtx for where the value is placed. 1064 1065 STR_RTX is the structure containing the byte (a REG or MEM). 1066 UNSIGNEDP is nonzero if this is an unsigned bit field. 1067 MODE is the natural mode of the field value once extracted. 1068 TMODE is the mode the caller would like the value to have; 1069 but the value may be returned with type MODE instead. 1070 1071 TOTAL_SIZE is the size in bytes of the containing structure, 1072 or -1 if varying. 1073 1074 If a TARGET is specified and we can store in it at no extra cost, 1075 we do so, and return TARGET. 1076 Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred 1077 if they are equally easy. */ 1078 1079rtx 1080extract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize, 1081 unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target, 1082 enum machine_mode mode, enum machine_mode tmode) 1083{ 1084 unsigned int unit 1085 = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD; 1086 unsigned HOST_WIDE_INT offset, bitpos; 1087 rtx op0 = str_rtx; 1088 rtx spec_target = target; 1089 rtx spec_target_subreg = 0; 1090 enum machine_mode int_mode; 1091 enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0); 1092 enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0); 1093 enum machine_mode mode1; 1094 int byte_offset; 1095 1096 if (tmode == VOIDmode) 1097 tmode = mode; 1098 1099 while (GET_CODE (op0) == SUBREG) 1100 { 1101 bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT; 1102 op0 = SUBREG_REG (op0); 1103 } 1104 1105 /* If we have an out-of-bounds access to a register, just return an 1106 uninitialized register of the required mode. This can occur if the 1107 source code contains an out-of-bounds access to a small array. */ 1108 if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0))) 1109 return gen_reg_rtx (tmode); 1110 1111 if (REG_P (op0) 1112 && mode == GET_MODE (op0) 1113 && bitnum == 0 1114 && bitsize == GET_MODE_BITSIZE (GET_MODE (op0))) 1115 { 1116 /* We're trying to extract a full register from itself. */ 1117 return op0; 1118 } 1119 1120 /* Use vec_extract patterns for extracting parts of vectors whenever 1121 available. */ 1122 if (VECTOR_MODE_P (GET_MODE (op0)) 1123 && !MEM_P (op0) 1124 && (vec_extract_optab->handlers[GET_MODE (op0)].insn_code 1125 != CODE_FOR_nothing) 1126 && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))) 1127 == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))))) 1128 { 1129 enum machine_mode outermode = GET_MODE (op0); 1130 enum machine_mode innermode = GET_MODE_INNER (outermode); 1131 int icode = (int) vec_extract_optab->handlers[outermode].insn_code; 1132 unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode); 1133 rtx rtxpos = GEN_INT (pos); 1134 rtx src = op0; 1135 rtx dest = NULL, pat, seq; 1136 enum machine_mode mode0 = insn_data[icode].operand[0].mode; 1137 enum machine_mode mode1 = insn_data[icode].operand[1].mode; 1138 enum machine_mode mode2 = insn_data[icode].operand[2].mode; 1139 1140 if (innermode == tmode || innermode == mode) 1141 dest = target; 1142 1143 if (!dest) 1144 dest = gen_reg_rtx (innermode); 1145 1146 start_sequence (); 1147 1148 if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)) 1149 dest = copy_to_mode_reg (mode0, dest); 1150 1151 if (! (*insn_data[icode].operand[1].predicate) (src, mode1)) 1152 src = copy_to_mode_reg (mode1, src); 1153 1154 if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)) 1155 rtxpos = copy_to_mode_reg (mode1, rtxpos); 1156 1157 /* We could handle this, but we should always be called with a pseudo 1158 for our targets and all insns should take them as outputs. */ 1159 gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0) 1160 && (*insn_data[icode].operand[1].predicate) (src, mode1) 1161 && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)); 1162 1163 pat = GEN_FCN (icode) (dest, src, rtxpos); 1164 seq = get_insns (); 1165 end_sequence (); 1166 if (pat) 1167 { 1168 emit_insn (seq); 1169 emit_insn (pat); 1170 return dest; 1171 } 1172 } 1173 1174 /* Make sure we are playing with integral modes. Pun with subregs 1175 if we aren't. */ 1176 { 1177 enum machine_mode imode = int_mode_for_mode (GET_MODE (op0)); 1178 if (imode != GET_MODE (op0)) 1179 { 1180 if (MEM_P (op0)) 1181 op0 = adjust_address (op0, imode, 0); 1182 else 1183 { 1184 gcc_assert (imode != BLKmode); 1185 op0 = gen_lowpart (imode, op0); 1186 1187 /* If we got a SUBREG, force it into a register since we 1188 aren't going to be able to do another SUBREG on it. */ 1189 if (GET_CODE (op0) == SUBREG) 1190 op0 = force_reg (imode, op0); 1191 } 1192 } 1193 } 1194 1195 /* We may be accessing data outside the field, which means 1196 we can alias adjacent data. */ 1197 if (MEM_P (op0)) 1198 { 1199 op0 = shallow_copy_rtx (op0); 1200 set_mem_alias_set (op0, 0); 1201 set_mem_expr (op0, 0); 1202 } 1203 1204 /* Extraction of a full-word or multi-word value from a structure 1205 in a register or aligned memory can be done with just a SUBREG. 1206 A subword value in the least significant part of a register 1207 can also be extracted with a SUBREG. For this, we need the 1208 byte offset of the value in op0. */ 1209 1210 bitpos = bitnum % unit; 1211 offset = bitnum / unit; 1212 byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD; 1213 1214 /* If OP0 is a register, BITPOS must count within a word. 1215 But as we have it, it counts within whatever size OP0 now has. 1216 On a bigendian machine, these are not the same, so convert. */ 1217 if (BYTES_BIG_ENDIAN 1218 && !MEM_P (op0) 1219 && unit > GET_MODE_BITSIZE (GET_MODE (op0))) 1220 bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0)); 1221 1222 /* ??? We currently assume TARGET is at least as big as BITSIZE. 1223 If that's wrong, the solution is to test for it and set TARGET to 0 1224 if needed. */ 1225 1226 /* Only scalar integer modes can be converted via subregs. There is an 1227 additional problem for FP modes here in that they can have a precision 1228 which is different from the size. mode_for_size uses precision, but 1229 we want a mode based on the size, so we must avoid calling it for FP 1230 modes. */ 1231 mode1 = (SCALAR_INT_MODE_P (tmode) 1232 ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) 1233 : mode); 1234 1235 if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode) 1236 && bitpos % BITS_PER_WORD == 0) 1237 || (mode1 != BLKmode 1238 /* ??? The big endian test here is wrong. This is correct 1239 if the value is in a register, and if mode_for_size is not 1240 the same mode as op0. This causes us to get unnecessarily 1241 inefficient code from the Thumb port when -mbig-endian. */ 1242 && (BYTES_BIG_ENDIAN 1243 ? bitpos + bitsize == BITS_PER_WORD 1244 : bitpos == 0))) 1245 && ((!MEM_P (op0) 1246 && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode), 1247 GET_MODE_BITSIZE (GET_MODE (op0))) 1248 && GET_MODE_SIZE (mode1) != 0 1249 && byte_offset % GET_MODE_SIZE (mode1) == 0) 1250 || (MEM_P (op0) 1251 && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0)) 1252 || (offset * BITS_PER_UNIT % bitsize == 0 1253 && MEM_ALIGN (op0) % bitsize == 0))))) 1254 { 1255 if (mode1 != GET_MODE (op0)) 1256 { 1257 if (MEM_P (op0)) 1258 op0 = adjust_address (op0, mode1, offset); 1259 else 1260 { 1261 rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0), 1262 byte_offset); 1263 if (sub == NULL) 1264 goto no_subreg_mode_swap; 1265 op0 = sub; 1266 } 1267 } 1268 if (mode1 != mode) 1269 return convert_to_mode (tmode, op0, unsignedp); 1270 return op0; 1271 } 1272 no_subreg_mode_swap: 1273 1274 /* Handle fields bigger than a word. */ 1275 1276 if (bitsize > BITS_PER_WORD) 1277 { 1278 /* Here we transfer the words of the field 1279 in the order least significant first. 1280 This is because the most significant word is the one which may 1281 be less than full. */ 1282 1283 unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD; 1284 unsigned int i; 1285 1286 if (target == 0 || !REG_P (target)) 1287 target = gen_reg_rtx (mode); 1288 1289 /* Indicate for flow that the entire target reg is being set. */ 1290 emit_insn (gen_rtx_CLOBBER (VOIDmode, target)); 1291 1292 for (i = 0; i < nwords; i++) 1293 { 1294 /* If I is 0, use the low-order word in both field and target; 1295 if I is 1, use the next to lowest word; and so on. */ 1296 /* Word number in TARGET to use. */ 1297 unsigned int wordnum 1298 = (WORDS_BIG_ENDIAN 1299 ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1 1300 : i); 1301 /* Offset from start of field in OP0. */ 1302 unsigned int bit_offset = (WORDS_BIG_ENDIAN 1303 ? MAX (0, ((int) bitsize - ((int) i + 1) 1304 * (int) BITS_PER_WORD)) 1305 : (int) i * BITS_PER_WORD); 1306 rtx target_part = operand_subword (target, wordnum, 1, VOIDmode); 1307 rtx result_part 1308 = extract_bit_field (op0, MIN (BITS_PER_WORD, 1309 bitsize - i * BITS_PER_WORD), 1310 bitnum + bit_offset, 1, target_part, mode, 1311 word_mode); 1312 1313 gcc_assert (target_part); 1314 1315 if (result_part != target_part) 1316 emit_move_insn (target_part, result_part); 1317 } 1318 1319 if (unsignedp) 1320 { 1321 /* Unless we've filled TARGET, the upper regs in a multi-reg value 1322 need to be zero'd out. */ 1323 if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD) 1324 { 1325 unsigned int i, total_words; 1326 1327 total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD; 1328 for (i = nwords; i < total_words; i++) 1329 emit_move_insn 1330 (operand_subword (target, 1331 WORDS_BIG_ENDIAN ? total_words - i - 1 : i, 1332 1, VOIDmode), 1333 const0_rtx); 1334 } 1335 return target; 1336 } 1337 1338 /* Signed bit field: sign-extend with two arithmetic shifts. */ 1339 target = expand_shift (LSHIFT_EXPR, mode, target, 1340 build_int_cst (NULL_TREE, 1341 GET_MODE_BITSIZE (mode) - bitsize), 1342 NULL_RTX, 0); 1343 return expand_shift (RSHIFT_EXPR, mode, target, 1344 build_int_cst (NULL_TREE, 1345 GET_MODE_BITSIZE (mode) - bitsize), 1346 NULL_RTX, 0); 1347 } 1348 1349 /* From here on we know the desired field is smaller than a word. */ 1350 1351 /* Check if there is a correspondingly-sized integer field, so we can 1352 safely extract it as one size of integer, if necessary; then 1353 truncate or extend to the size that is wanted; then use SUBREGs or 1354 convert_to_mode to get one of the modes we really wanted. */ 1355 1356 int_mode = int_mode_for_mode (tmode); 1357 if (int_mode == BLKmode) 1358 int_mode = int_mode_for_mode (mode); 1359 /* Should probably push op0 out to memory and then do a load. */ 1360 gcc_assert (int_mode != BLKmode); 1361 1362 /* OFFSET is the number of words or bytes (UNIT says which) 1363 from STR_RTX to the first word or byte containing part of the field. */ 1364 if (!MEM_P (op0)) 1365 { 1366 if (offset != 0 1367 || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD) 1368 { 1369 if (!REG_P (op0)) 1370 op0 = copy_to_reg (op0); 1371 op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0), 1372 op0, (offset * UNITS_PER_WORD)); 1373 } 1374 offset = 0; 1375 } 1376 1377 /* Now OFFSET is nonzero only for memory operands. */ 1378 1379 if (unsignedp) 1380 { 1381 if (HAVE_extzv 1382 && bitsize > 0 1383 && GET_MODE_BITSIZE (extzv_mode) >= bitsize 1384 && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 1385 && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode)))) 1386 { 1387 unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset; 1388 rtx bitsize_rtx, bitpos_rtx; 1389 rtx last = get_last_insn (); 1390 rtx xop0 = op0; 1391 rtx xtarget = target; 1392 rtx xspec_target = spec_target; 1393 rtx xspec_target_subreg = spec_target_subreg; 1394 rtx pat; 1395 enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0); 1396 1397 if (MEM_P (xop0)) 1398 { 1399 int save_volatile_ok = volatile_ok; 1400 volatile_ok = 1; 1401 1402 /* Is the memory operand acceptable? */ 1403 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate) 1404 (xop0, GET_MODE (xop0)))) 1405 { 1406 /* No, load into a reg and extract from there. */ 1407 enum machine_mode bestmode; 1408 1409 /* Get the mode to use for inserting into this field. If 1410 OP0 is BLKmode, get the smallest mode consistent with the 1411 alignment. If OP0 is a non-BLKmode object that is no 1412 wider than MAXMODE, use its mode. Otherwise, use the 1413 smallest mode containing the field. */ 1414 1415 if (GET_MODE (xop0) == BLKmode 1416 || (GET_MODE_SIZE (GET_MODE (op0)) 1417 > GET_MODE_SIZE (maxmode))) 1418 bestmode = get_best_mode (bitsize, bitnum, 1419 MEM_ALIGN (xop0), maxmode, 1420 MEM_VOLATILE_P (xop0)); 1421 else 1422 bestmode = GET_MODE (xop0); 1423 1424 if (bestmode == VOIDmode 1425 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0)) 1426 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0))) 1427 goto extzv_loses; 1428 1429 /* Compute offset as multiple of this unit, 1430 counting in bytes. */ 1431 unit = GET_MODE_BITSIZE (bestmode); 1432 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 1433 xbitpos = bitnum % unit; 1434 xop0 = adjust_address (xop0, bestmode, xoffset); 1435 1436 /* Make sure register is big enough for the whole field. */ 1437 if (xoffset * BITS_PER_UNIT + unit 1438 < offset * BITS_PER_UNIT + bitsize) 1439 goto extzv_loses; 1440 1441 /* Fetch it to a register in that size. */ 1442 xop0 = force_reg (bestmode, xop0); 1443 1444 /* XBITPOS counts within UNIT, which is what is expected. */ 1445 } 1446 else 1447 /* Get ref to first byte containing part of the field. */ 1448 xop0 = adjust_address (xop0, byte_mode, xoffset); 1449 1450 volatile_ok = save_volatile_ok; 1451 } 1452 1453 /* If op0 is a register, we need it in MAXMODE (which is usually 1454 SImode). to make it acceptable to the format of extzv. */ 1455 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode) 1456 goto extzv_loses; 1457 if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 1458 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 1459 1460 /* On big-endian machines, we count bits from the most significant. 1461 If the bit field insn does not, we must invert. */ 1462 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 1463 xbitpos = unit - bitsize - xbitpos; 1464 1465 /* Now convert from counting within UNIT to counting in MAXMODE. */ 1466 if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 1467 xbitpos += GET_MODE_BITSIZE (maxmode) - unit; 1468 1469 unit = GET_MODE_BITSIZE (maxmode); 1470 1471 if (xtarget == 0) 1472 xtarget = xspec_target = gen_reg_rtx (tmode); 1473 1474 if (GET_MODE (xtarget) != maxmode) 1475 { 1476 if (REG_P (xtarget)) 1477 { 1478 int wider = (GET_MODE_SIZE (maxmode) 1479 > GET_MODE_SIZE (GET_MODE (xtarget))); 1480 xtarget = gen_lowpart (maxmode, xtarget); 1481 if (wider) 1482 xspec_target_subreg = xtarget; 1483 } 1484 else 1485 xtarget = gen_reg_rtx (maxmode); 1486 } 1487 1488 /* If this machine's extzv insists on a register target, 1489 make sure we have one. */ 1490 if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate) 1491 (xtarget, maxmode))) 1492 xtarget = gen_reg_rtx (maxmode); 1493 1494 bitsize_rtx = GEN_INT (bitsize); 1495 bitpos_rtx = GEN_INT (xbitpos); 1496 1497 pat = gen_extzv (xtarget, xop0, bitsize_rtx, bitpos_rtx); 1498 if (pat) 1499 { 1500 emit_insn (pat); 1501 target = xtarget; 1502 spec_target = xspec_target; 1503 spec_target_subreg = xspec_target_subreg; 1504 } 1505 else 1506 { 1507 delete_insns_since (last); 1508 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 1509 bitpos, target, 1); 1510 } 1511 } 1512 else 1513 extzv_loses: 1514 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 1515 bitpos, target, 1); 1516 } 1517 else 1518 { 1519 if (HAVE_extv 1520 && bitsize > 0 1521 && GET_MODE_BITSIZE (extv_mode) >= bitsize 1522 && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 1523 && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode)))) 1524 { 1525 int xbitpos = bitpos, xoffset = offset; 1526 rtx bitsize_rtx, bitpos_rtx; 1527 rtx last = get_last_insn (); 1528 rtx xop0 = op0, xtarget = target; 1529 rtx xspec_target = spec_target; 1530 rtx xspec_target_subreg = spec_target_subreg; 1531 rtx pat; 1532 enum machine_mode maxmode = mode_for_extraction (EP_extv, 0); 1533 1534 if (MEM_P (xop0)) 1535 { 1536 /* Is the memory operand acceptable? */ 1537 if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate) 1538 (xop0, GET_MODE (xop0)))) 1539 { 1540 /* No, load into a reg and extract from there. */ 1541 enum machine_mode bestmode; 1542 1543 /* Get the mode to use for inserting into this field. If 1544 OP0 is BLKmode, get the smallest mode consistent with the 1545 alignment. If OP0 is a non-BLKmode object that is no 1546 wider than MAXMODE, use its mode. Otherwise, use the 1547 smallest mode containing the field. */ 1548 1549 if (GET_MODE (xop0) == BLKmode 1550 || (GET_MODE_SIZE (GET_MODE (op0)) 1551 > GET_MODE_SIZE (maxmode))) 1552 bestmode = get_best_mode (bitsize, bitnum, 1553 MEM_ALIGN (xop0), maxmode, 1554 MEM_VOLATILE_P (xop0)); 1555 else 1556 bestmode = GET_MODE (xop0); 1557 1558 if (bestmode == VOIDmode 1559 || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0)) 1560 && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0))) 1561 goto extv_loses; 1562 1563 /* Compute offset as multiple of this unit, 1564 counting in bytes. */ 1565 unit = GET_MODE_BITSIZE (bestmode); 1566 xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 1567 xbitpos = bitnum % unit; 1568 xop0 = adjust_address (xop0, bestmode, xoffset); 1569 1570 /* Make sure register is big enough for the whole field. */ 1571 if (xoffset * BITS_PER_UNIT + unit 1572 < offset * BITS_PER_UNIT + bitsize) 1573 goto extv_loses; 1574 1575 /* Fetch it to a register in that size. */ 1576 xop0 = force_reg (bestmode, xop0); 1577 1578 /* XBITPOS counts within UNIT, which is what is expected. */ 1579 } 1580 else 1581 /* Get ref to first byte containing part of the field. */ 1582 xop0 = adjust_address (xop0, byte_mode, xoffset); 1583 } 1584 1585 /* If op0 is a register, we need it in MAXMODE (which is usually 1586 SImode) to make it acceptable to the format of extv. */ 1587 if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode) 1588 goto extv_loses; 1589 if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 1590 xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 1591 1592 /* On big-endian machines, we count bits from the most significant. 1593 If the bit field insn does not, we must invert. */ 1594 if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 1595 xbitpos = unit - bitsize - xbitpos; 1596 1597 /* XBITPOS counts within a size of UNIT. 1598 Adjust to count within a size of MAXMODE. */ 1599 if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 1600 xbitpos += (GET_MODE_BITSIZE (maxmode) - unit); 1601 1602 unit = GET_MODE_BITSIZE (maxmode); 1603 1604 if (xtarget == 0) 1605 xtarget = xspec_target = gen_reg_rtx (tmode); 1606 1607 if (GET_MODE (xtarget) != maxmode) 1608 { 1609 if (REG_P (xtarget)) 1610 { 1611 int wider = (GET_MODE_SIZE (maxmode) 1612 > GET_MODE_SIZE (GET_MODE (xtarget))); 1613 xtarget = gen_lowpart (maxmode, xtarget); 1614 if (wider) 1615 xspec_target_subreg = xtarget; 1616 } 1617 else 1618 xtarget = gen_reg_rtx (maxmode); 1619 } 1620 1621 /* If this machine's extv insists on a register target, 1622 make sure we have one. */ 1623 if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate) 1624 (xtarget, maxmode))) 1625 xtarget = gen_reg_rtx (maxmode); 1626 1627 bitsize_rtx = GEN_INT (bitsize); 1628 bitpos_rtx = GEN_INT (xbitpos); 1629 1630 pat = gen_extv (xtarget, xop0, bitsize_rtx, bitpos_rtx); 1631 if (pat) 1632 { 1633 emit_insn (pat); 1634 target = xtarget; 1635 spec_target = xspec_target; 1636 spec_target_subreg = xspec_target_subreg; 1637 } 1638 else 1639 { 1640 delete_insns_since (last); 1641 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 1642 bitpos, target, 0); 1643 } 1644 } 1645 else 1646 extv_loses: 1647 target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 1648 bitpos, target, 0); 1649 } 1650 if (target == spec_target) 1651 return target; 1652 if (target == spec_target_subreg) 1653 return spec_target; 1654 if (GET_MODE (target) != tmode && GET_MODE (target) != mode) 1655 { 1656 /* If the target mode is not a scalar integral, first convert to the 1657 integer mode of that size and then access it as a floating-point 1658 value via a SUBREG. */ 1659 if (!SCALAR_INT_MODE_P (tmode)) 1660 { 1661 enum machine_mode smode 1662 = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0); 1663 target = convert_to_mode (smode, target, unsignedp); 1664 target = force_reg (smode, target); 1665 return gen_lowpart (tmode, target); 1666 } 1667 1668 return convert_to_mode (tmode, target, unsignedp); 1669 } 1670 return target; 1671} 1672 1673/* Extract a bit field using shifts and boolean operations 1674 Returns an rtx to represent the value. 1675 OP0 addresses a register (word) or memory (byte). 1676 BITPOS says which bit within the word or byte the bit field starts in. 1677 OFFSET says how many bytes farther the bit field starts; 1678 it is 0 if OP0 is a register. 1679 BITSIZE says how many bits long the bit field is. 1680 (If OP0 is a register, it may be narrower than a full word, 1681 but BITPOS still counts within a full word, 1682 which is significant on bigendian machines.) 1683 1684 UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value). 1685 If TARGET is nonzero, attempts to store the value there 1686 and return TARGET, but this is not guaranteed. 1687 If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */ 1688 1689static rtx 1690extract_fixed_bit_field (enum machine_mode tmode, rtx op0, 1691 unsigned HOST_WIDE_INT offset, 1692 unsigned HOST_WIDE_INT bitsize, 1693 unsigned HOST_WIDE_INT bitpos, rtx target, 1694 int unsignedp) 1695{ 1696 unsigned int total_bits = BITS_PER_WORD; 1697 enum machine_mode mode; 1698 1699 if (GET_CODE (op0) == SUBREG || REG_P (op0)) 1700 { 1701 /* Special treatment for a bit field split across two registers. */ 1702 if (bitsize + bitpos > BITS_PER_WORD) 1703 return extract_split_bit_field (op0, bitsize, bitpos, unsignedp); 1704 } 1705 else 1706 { 1707 /* Get the proper mode to use for this field. We want a mode that 1708 includes the entire field. If such a mode would be larger than 1709 a word, we won't be doing the extraction the normal way. */ 1710 1711 mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT, 1712 MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0)); 1713 1714 if (mode == VOIDmode) 1715 /* The only way this should occur is if the field spans word 1716 boundaries. */ 1717 return extract_split_bit_field (op0, bitsize, 1718 bitpos + offset * BITS_PER_UNIT, 1719 unsignedp); 1720 1721 total_bits = GET_MODE_BITSIZE (mode); 1722 1723 /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to 1724 be in the range 0 to total_bits-1, and put any excess bytes in 1725 OFFSET. */ 1726 if (bitpos >= total_bits) 1727 { 1728 offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT); 1729 bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT) 1730 * BITS_PER_UNIT); 1731 } 1732 1733 /* Get ref to an aligned byte, halfword, or word containing the field. 1734 Adjust BITPOS to be position within a word, 1735 and OFFSET to be the offset of that word. 1736 Then alter OP0 to refer to that word. */ 1737 bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT; 1738 offset -= (offset % (total_bits / BITS_PER_UNIT)); 1739 op0 = adjust_address (op0, mode, offset); 1740 } 1741 1742 mode = GET_MODE (op0); 1743 1744 if (BYTES_BIG_ENDIAN) 1745 /* BITPOS is the distance between our msb and that of OP0. 1746 Convert it to the distance from the lsb. */ 1747 bitpos = total_bits - bitsize - bitpos; 1748 1749 /* Now BITPOS is always the distance between the field's lsb and that of OP0. 1750 We have reduced the big-endian case to the little-endian case. */ 1751 1752 if (unsignedp) 1753 { 1754 if (bitpos) 1755 { 1756 /* If the field does not already start at the lsb, 1757 shift it so it does. */ 1758 tree amount = build_int_cst (NULL_TREE, bitpos); 1759 /* Maybe propagate the target for the shift. */ 1760 /* But not if we will return it--could confuse integrate.c. */ 1761 rtx subtarget = (target != 0 && REG_P (target) ? target : 0); 1762 if (tmode != mode) subtarget = 0; 1763 op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1); 1764 } 1765 /* Convert the value to the desired mode. */ 1766 if (mode != tmode) 1767 op0 = convert_to_mode (tmode, op0, 1); 1768 1769 /* Unless the msb of the field used to be the msb when we shifted, 1770 mask out the upper bits. */ 1771 1772 if (GET_MODE_BITSIZE (mode) != bitpos + bitsize) 1773 return expand_binop (GET_MODE (op0), and_optab, op0, 1774 mask_rtx (GET_MODE (op0), 0, bitsize, 0), 1775 target, 1, OPTAB_LIB_WIDEN); 1776 return op0; 1777 } 1778 1779 /* To extract a signed bit-field, first shift its msb to the msb of the word, 1780 then arithmetic-shift its lsb to the lsb of the word. */ 1781 op0 = force_reg (mode, op0); 1782 if (mode != tmode) 1783 target = 0; 1784 1785 /* Find the narrowest integer mode that contains the field. */ 1786 1787 for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode; 1788 mode = GET_MODE_WIDER_MODE (mode)) 1789 if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos) 1790 { 1791 op0 = convert_to_mode (mode, op0, 0); 1792 break; 1793 } 1794 1795 if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos)) 1796 { 1797 tree amount 1798 = build_int_cst (NULL_TREE, 1799 GET_MODE_BITSIZE (mode) - (bitsize + bitpos)); 1800 /* Maybe propagate the target for the shift. */ 1801 rtx subtarget = (target != 0 && REG_P (target) ? target : 0); 1802 op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1); 1803 } 1804 1805 return expand_shift (RSHIFT_EXPR, mode, op0, 1806 build_int_cst (NULL_TREE, 1807 GET_MODE_BITSIZE (mode) - bitsize), 1808 target, 0); 1809} 1810 1811/* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value 1812 of mode MODE with BITSIZE ones followed by BITPOS zeros, or the 1813 complement of that if COMPLEMENT. The mask is truncated if 1814 necessary to the width of mode MODE. The mask is zero-extended if 1815 BITSIZE+BITPOS is too small for MODE. */ 1816 1817static rtx 1818mask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement) 1819{ 1820 HOST_WIDE_INT masklow, maskhigh; 1821 1822 if (bitsize == 0) 1823 masklow = 0; 1824 else if (bitpos < HOST_BITS_PER_WIDE_INT) 1825 masklow = (HOST_WIDE_INT) -1 << bitpos; 1826 else 1827 masklow = 0; 1828 1829 if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT) 1830 masklow &= ((unsigned HOST_WIDE_INT) -1 1831 >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize)); 1832 1833 if (bitpos <= HOST_BITS_PER_WIDE_INT) 1834 maskhigh = -1; 1835 else 1836 maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT); 1837 1838 if (bitsize == 0) 1839 maskhigh = 0; 1840 else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT) 1841 maskhigh &= ((unsigned HOST_WIDE_INT) -1 1842 >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize)); 1843 else 1844 maskhigh = 0; 1845 1846 if (complement) 1847 { 1848 maskhigh = ~maskhigh; 1849 masklow = ~masklow; 1850 } 1851 1852 return immed_double_const (masklow, maskhigh, mode); 1853} 1854 1855/* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value 1856 VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */ 1857 1858static rtx 1859lshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize) 1860{ 1861 unsigned HOST_WIDE_INT v = INTVAL (value); 1862 HOST_WIDE_INT low, high; 1863 1864 if (bitsize < HOST_BITS_PER_WIDE_INT) 1865 v &= ~((HOST_WIDE_INT) -1 << bitsize); 1866 1867 if (bitpos < HOST_BITS_PER_WIDE_INT) 1868 { 1869 low = v << bitpos; 1870 high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0); 1871 } 1872 else 1873 { 1874 low = 0; 1875 high = v << (bitpos - HOST_BITS_PER_WIDE_INT); 1876 } 1877 1878 return immed_double_const (low, high, mode); 1879} 1880 1881/* Extract a bit field from a memory by forcing the alignment of the 1882 memory. This efficient only if the field spans at least 4 boundaries. 1883 1884 OP0 is the MEM. 1885 BITSIZE is the field width; BITPOS is the position of the first bit. 1886 UNSIGNEDP is true if the result should be zero-extended. */ 1887 1888static rtx 1889extract_force_align_mem_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 1890 unsigned HOST_WIDE_INT bitpos, 1891 int unsignedp) 1892{ 1893 enum machine_mode mode, dmode; 1894 unsigned int m_bitsize, m_size; 1895 unsigned int sign_shift_up, sign_shift_dn; 1896 rtx base, a1, a2, v1, v2, comb, shift, result, start; 1897 1898 /* Choose a mode that will fit BITSIZE. */ 1899 mode = smallest_mode_for_size (bitsize, MODE_INT); 1900 m_size = GET_MODE_SIZE (mode); 1901 m_bitsize = GET_MODE_BITSIZE (mode); 1902 1903 /* Choose a mode twice as wide. Fail if no such mode exists. */ 1904 dmode = mode_for_size (m_bitsize * 2, MODE_INT, false); 1905 if (dmode == BLKmode) 1906 return NULL; 1907 1908 do_pending_stack_adjust (); 1909 start = get_last_insn (); 1910 1911 /* At the end, we'll need an additional shift to deal with sign/zero 1912 extension. By default this will be a left+right shift of the 1913 appropriate size. But we may be able to eliminate one of them. */ 1914 sign_shift_up = sign_shift_dn = m_bitsize - bitsize; 1915 1916 if (STRICT_ALIGNMENT) 1917 { 1918 base = plus_constant (XEXP (op0, 0), bitpos / BITS_PER_UNIT); 1919 bitpos %= BITS_PER_UNIT; 1920 1921 /* We load two values to be concatenate. There's an edge condition 1922 that bears notice -- an aligned value at the end of a page can 1923 only load one value lest we segfault. So the two values we load 1924 are at "base & -size" and "(base + size - 1) & -size". If base 1925 is unaligned, the addresses will be aligned and sequential; if 1926 base is aligned, the addresses will both be equal to base. */ 1927 1928 a1 = expand_simple_binop (Pmode, AND, force_operand (base, NULL), 1929 GEN_INT (-(HOST_WIDE_INT)m_size), 1930 NULL, true, OPTAB_LIB_WIDEN); 1931 mark_reg_pointer (a1, m_bitsize); 1932 v1 = gen_rtx_MEM (mode, a1); 1933 set_mem_align (v1, m_bitsize); 1934 v1 = force_reg (mode, validize_mem (v1)); 1935 1936 a2 = plus_constant (base, GET_MODE_SIZE (mode) - 1); 1937 a2 = expand_simple_binop (Pmode, AND, force_operand (a2, NULL), 1938 GEN_INT (-(HOST_WIDE_INT)m_size), 1939 NULL, true, OPTAB_LIB_WIDEN); 1940 v2 = gen_rtx_MEM (mode, a2); 1941 set_mem_align (v2, m_bitsize); 1942 v2 = force_reg (mode, validize_mem (v2)); 1943 1944 /* Combine these two values into a double-word value. */ 1945 if (m_bitsize == BITS_PER_WORD) 1946 { 1947 comb = gen_reg_rtx (dmode); 1948 emit_insn (gen_rtx_CLOBBER (VOIDmode, comb)); 1949 emit_move_insn (gen_rtx_SUBREG (mode, comb, 0), v1); 1950 emit_move_insn (gen_rtx_SUBREG (mode, comb, m_size), v2); 1951 } 1952 else 1953 { 1954 if (BYTES_BIG_ENDIAN) 1955 comb = v1, v1 = v2, v2 = comb; 1956 v1 = convert_modes (dmode, mode, v1, true); 1957 if (v1 == NULL) 1958 goto fail; 1959 v2 = convert_modes (dmode, mode, v2, true); 1960 v2 = expand_simple_binop (dmode, ASHIFT, v2, GEN_INT (m_bitsize), 1961 NULL, true, OPTAB_LIB_WIDEN); 1962 if (v2 == NULL) 1963 goto fail; 1964 comb = expand_simple_binop (dmode, IOR, v1, v2, NULL, 1965 true, OPTAB_LIB_WIDEN); 1966 if (comb == NULL) 1967 goto fail; 1968 } 1969 1970 shift = expand_simple_binop (Pmode, AND, base, GEN_INT (m_size - 1), 1971 NULL, true, OPTAB_LIB_WIDEN); 1972 shift = expand_mult (Pmode, shift, GEN_INT (BITS_PER_UNIT), NULL, 1); 1973 1974 if (bitpos != 0) 1975 { 1976 if (sign_shift_up <= bitpos) 1977 bitpos -= sign_shift_up, sign_shift_up = 0; 1978 shift = expand_simple_binop (Pmode, PLUS, shift, GEN_INT (bitpos), 1979 NULL, true, OPTAB_LIB_WIDEN); 1980 } 1981 } 1982 else 1983 { 1984 unsigned HOST_WIDE_INT offset = bitpos / BITS_PER_UNIT; 1985 bitpos %= BITS_PER_UNIT; 1986 1987 /* When strict alignment is not required, we can just load directly 1988 from memory without masking. If the remaining BITPOS offset is 1989 small enough, we may be able to do all operations in MODE as 1990 opposed to DMODE. */ 1991 if (bitpos + bitsize <= m_bitsize) 1992 dmode = mode; 1993 comb = adjust_address (op0, dmode, offset); 1994 1995 if (sign_shift_up <= bitpos) 1996 bitpos -= sign_shift_up, sign_shift_up = 0; 1997 shift = GEN_INT (bitpos); 1998 } 1999 2000 /* Shift down the double-word such that the requested value is at bit 0. */ 2001 if (shift != const0_rtx) 2002 comb = expand_simple_binop (dmode, unsignedp ? LSHIFTRT : ASHIFTRT, 2003 comb, shift, NULL, unsignedp, OPTAB_LIB_WIDEN); 2004 if (comb == NULL) 2005 goto fail; 2006 2007 /* If the field exactly matches MODE, then all we need to do is return the 2008 lowpart. Otherwise, shift to get the sign bits set properly. */ 2009 result = force_reg (mode, gen_lowpart (mode, comb)); 2010 2011 if (sign_shift_up) 2012 result = expand_simple_binop (mode, ASHIFT, result, 2013 GEN_INT (sign_shift_up), 2014 NULL_RTX, 0, OPTAB_LIB_WIDEN); 2015 if (sign_shift_dn) 2016 result = expand_simple_binop (mode, unsignedp ? LSHIFTRT : ASHIFTRT, 2017 result, GEN_INT (sign_shift_dn), 2018 NULL_RTX, 0, OPTAB_LIB_WIDEN); 2019 2020 return result; 2021 2022 fail: 2023 delete_insns_since (start); 2024 return NULL; 2025} 2026 2027/* Extract a bit field that is split across two words 2028 and return an RTX for the result. 2029 2030 OP0 is the REG, SUBREG or MEM rtx for the first of the two words. 2031 BITSIZE is the field width; BITPOS, position of its first bit, in the word. 2032 UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */ 2033 2034static rtx 2035extract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 2036 unsigned HOST_WIDE_INT bitpos, int unsignedp) 2037{ 2038 unsigned int unit; 2039 unsigned int bitsdone = 0; 2040 rtx result = NULL_RTX; 2041 int first = 1; 2042 2043 /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that 2044 much at a time. */ 2045 if (REG_P (op0) || GET_CODE (op0) == SUBREG) 2046 unit = BITS_PER_WORD; 2047 else 2048 { 2049 unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD); 2050 if (0 && bitsize / unit > 2) 2051 { 2052 rtx tmp = extract_force_align_mem_bit_field (op0, bitsize, bitpos, 2053 unsignedp); 2054 if (tmp) 2055 return tmp; 2056 } 2057 } 2058 2059 while (bitsdone < bitsize) 2060 { 2061 unsigned HOST_WIDE_INT thissize; 2062 rtx part, word; 2063 unsigned HOST_WIDE_INT thispos; 2064 unsigned HOST_WIDE_INT offset; 2065 2066 offset = (bitpos + bitsdone) / unit; 2067 thispos = (bitpos + bitsdone) % unit; 2068 2069 /* THISSIZE must not overrun a word boundary. Otherwise, 2070 extract_fixed_bit_field will call us again, and we will mutually 2071 recurse forever. */ 2072 thissize = MIN (bitsize - bitsdone, BITS_PER_WORD); 2073 thissize = MIN (thissize, unit - thispos); 2074 2075 /* If OP0 is a register, then handle OFFSET here. 2076 2077 When handling multiword bitfields, extract_bit_field may pass 2078 down a word_mode SUBREG of a larger REG for a bitfield that actually 2079 crosses a word boundary. Thus, for a SUBREG, we must find 2080 the current word starting from the base register. */ 2081 if (GET_CODE (op0) == SUBREG) 2082 { 2083 int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset; 2084 word = operand_subword_force (SUBREG_REG (op0), word_offset, 2085 GET_MODE (SUBREG_REG (op0))); 2086 offset = 0; 2087 } 2088 else if (REG_P (op0)) 2089 { 2090 word = operand_subword_force (op0, offset, GET_MODE (op0)); 2091 offset = 0; 2092 } 2093 else 2094 word = op0; 2095 2096 /* Extract the parts in bit-counting order, 2097 whose meaning is determined by BYTES_PER_UNIT. 2098 OFFSET is in UNITs, and UNIT is in bits. 2099 extract_fixed_bit_field wants offset in bytes. */ 2100 part = extract_fixed_bit_field (word_mode, word, 2101 offset * unit / BITS_PER_UNIT, 2102 thissize, thispos, 0, 1); 2103 bitsdone += thissize; 2104 2105 /* Shift this part into place for the result. */ 2106 if (BYTES_BIG_ENDIAN) 2107 { 2108 if (bitsize != bitsdone) 2109 part = expand_shift (LSHIFT_EXPR, word_mode, part, 2110 build_int_cst (NULL_TREE, bitsize - bitsdone), 2111 0, 1); 2112 } 2113 else 2114 { 2115 if (bitsdone != thissize) 2116 part = expand_shift (LSHIFT_EXPR, word_mode, part, 2117 build_int_cst (NULL_TREE, 2118 bitsdone - thissize), 0, 1); 2119 } 2120 2121 if (first) 2122 result = part; 2123 else 2124 /* Combine the parts with bitwise or. This works 2125 because we extracted each part as an unsigned bit field. */ 2126 result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1, 2127 OPTAB_LIB_WIDEN); 2128 2129 first = 0; 2130 } 2131 2132 /* Unsigned bit field: we are done. */ 2133 if (unsignedp) 2134 return result; 2135 /* Signed bit field: sign-extend with two arithmetic shifts. */ 2136 result = expand_shift (LSHIFT_EXPR, word_mode, result, 2137 build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize), 2138 NULL_RTX, 0); 2139 return expand_shift (RSHIFT_EXPR, word_mode, result, 2140 build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize), 2141 NULL_RTX, 0); 2142} 2143 2144/* Add INC into TARGET. */ 2145 2146void 2147expand_inc (rtx target, rtx inc) 2148{ 2149 rtx value = expand_binop (GET_MODE (target), add_optab, 2150 target, inc, 2151 target, 0, OPTAB_LIB_WIDEN); 2152 if (value != target) 2153 emit_move_insn (target, value); 2154} 2155 2156/* Subtract DEC from TARGET. */ 2157 2158void 2159expand_dec (rtx target, rtx dec) 2160{ 2161 rtx value = expand_binop (GET_MODE (target), sub_optab, 2162 target, dec, 2163 target, 0, OPTAB_LIB_WIDEN); 2164 if (value != target) 2165 emit_move_insn (target, value); 2166} 2167 2168/* Output a shift instruction for expression code CODE, 2169 with SHIFTED being the rtx for the value to shift, 2170 and AMOUNT the tree for the amount to shift by. 2171 Store the result in the rtx TARGET, if that is convenient. 2172 If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic. 2173 Return the rtx for where the value is. */ 2174 2175rtx 2176expand_shift (enum tree_code code, enum machine_mode mode, rtx shifted, 2177 tree amount, rtx target, int unsignedp) 2178{ 2179 rtx op1, temp = 0; 2180 int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR); 2181 int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR); 2182 int try; 2183 2184 /* Previously detected shift-counts computed by NEGATE_EXPR 2185 and shifted in the other direction; but that does not work 2186 on all machines. */ 2187 2188 op1 = expand_expr (amount, NULL_RTX, VOIDmode, 0); 2189 2190 if (SHIFT_COUNT_TRUNCATED) 2191 { 2192 if (GET_CODE (op1) == CONST_INT 2193 && ((unsigned HOST_WIDE_INT) INTVAL (op1) >= 2194 (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode))) 2195 op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1) 2196 % GET_MODE_BITSIZE (mode)); 2197 else if (GET_CODE (op1) == SUBREG 2198 && subreg_lowpart_p (op1)) 2199 op1 = SUBREG_REG (op1); 2200 } 2201 2202 if (op1 == const0_rtx) 2203 return shifted; 2204 2205 /* Check whether its cheaper to implement a left shift by a constant 2206 bit count by a sequence of additions. */ 2207 if (code == LSHIFT_EXPR 2208 && GET_CODE (op1) == CONST_INT 2209 && INTVAL (op1) > 0 2210 && INTVAL (op1) < GET_MODE_BITSIZE (mode) 2211 && INTVAL (op1) < MAX_BITS_PER_WORD 2212 && shift_cost[mode][INTVAL (op1)] > INTVAL (op1) * add_cost[mode] 2213 && shift_cost[mode][INTVAL (op1)] != MAX_COST) 2214 { 2215 int i; 2216 for (i = 0; i < INTVAL (op1); i++) 2217 { 2218 temp = force_reg (mode, shifted); 2219 shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX, 2220 unsignedp, OPTAB_LIB_WIDEN); 2221 } 2222 return shifted; 2223 } 2224 2225 for (try = 0; temp == 0 && try < 3; try++) 2226 { 2227 enum optab_methods methods; 2228 2229 if (try == 0) 2230 methods = OPTAB_DIRECT; 2231 else if (try == 1) 2232 methods = OPTAB_WIDEN; 2233 else 2234 methods = OPTAB_LIB_WIDEN; 2235 2236 if (rotate) 2237 { 2238 /* Widening does not work for rotation. */ 2239 if (methods == OPTAB_WIDEN) 2240 continue; 2241 else if (methods == OPTAB_LIB_WIDEN) 2242 { 2243 /* If we have been unable to open-code this by a rotation, 2244 do it as the IOR of two shifts. I.e., to rotate A 2245 by N bits, compute (A << N) | ((unsigned) A >> (C - N)) 2246 where C is the bitsize of A. 2247 2248 It is theoretically possible that the target machine might 2249 not be able to perform either shift and hence we would 2250 be making two libcalls rather than just the one for the 2251 shift (similarly if IOR could not be done). We will allow 2252 this extremely unlikely lossage to avoid complicating the 2253 code below. */ 2254 2255 rtx subtarget = target == shifted ? 0 : target; 2256 tree new_amount, other_amount; 2257 rtx temp1; 2258 tree type = TREE_TYPE (amount); 2259 if (GET_MODE (op1) != TYPE_MODE (type) 2260 && GET_MODE (op1) != VOIDmode) 2261 op1 = convert_to_mode (TYPE_MODE (type), op1, 1); 2262 new_amount = make_tree (type, op1); 2263 other_amount 2264 = fold_build2 (MINUS_EXPR, type, 2265 build_int_cst (type, GET_MODE_BITSIZE (mode)), 2266 new_amount); 2267 2268 shifted = force_reg (mode, shifted); 2269 2270 temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR, 2271 mode, shifted, new_amount, 0, 1); 2272 temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR, 2273 mode, shifted, other_amount, subtarget, 1); 2274 return expand_binop (mode, ior_optab, temp, temp1, target, 2275 unsignedp, methods); 2276 } 2277 2278 temp = expand_binop (mode, 2279 left ? rotl_optab : rotr_optab, 2280 shifted, op1, target, unsignedp, methods); 2281 } 2282 else if (unsignedp) 2283 temp = expand_binop (mode, 2284 left ? ashl_optab : lshr_optab, 2285 shifted, op1, target, unsignedp, methods); 2286 2287 /* Do arithmetic shifts. 2288 Also, if we are going to widen the operand, we can just as well 2289 use an arithmetic right-shift instead of a logical one. */ 2290 if (temp == 0 && ! rotate 2291 && (! unsignedp || (! left && methods == OPTAB_WIDEN))) 2292 { 2293 enum optab_methods methods1 = methods; 2294 2295 /* If trying to widen a log shift to an arithmetic shift, 2296 don't accept an arithmetic shift of the same size. */ 2297 if (unsignedp) 2298 methods1 = OPTAB_MUST_WIDEN; 2299 2300 /* Arithmetic shift */ 2301 2302 temp = expand_binop (mode, 2303 left ? ashl_optab : ashr_optab, 2304 shifted, op1, target, unsignedp, methods1); 2305 } 2306 2307 /* We used to try extzv here for logical right shifts, but that was 2308 only useful for one machine, the VAX, and caused poor code 2309 generation there for lshrdi3, so the code was deleted and a 2310 define_expand for lshrsi3 was added to vax.md. */ 2311 } 2312 2313 gcc_assert (temp); 2314 return temp; 2315} 2316 2317enum alg_code { 2318 alg_unknown, 2319 alg_zero, 2320 alg_m, alg_shift, 2321 alg_add_t_m2, 2322 alg_sub_t_m2, 2323 alg_add_factor, 2324 alg_sub_factor, 2325 alg_add_t2_m, 2326 alg_sub_t2_m, 2327 alg_impossible 2328}; 2329 2330/* This structure holds the "cost" of a multiply sequence. The 2331 "cost" field holds the total rtx_cost of every operator in the 2332 synthetic multiplication sequence, hence cost(a op b) is defined 2333 as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero. 2334 The "latency" field holds the minimum possible latency of the 2335 synthetic multiply, on a hypothetical infinitely parallel CPU. 2336 This is the critical path, or the maximum height, of the expression 2337 tree which is the sum of rtx_costs on the most expensive path from 2338 any leaf to the root. Hence latency(a op b) is defined as zero for 2339 leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise. */ 2340 2341struct mult_cost { 2342 short cost; /* Total rtx_cost of the multiplication sequence. */ 2343 short latency; /* The latency of the multiplication sequence. */ 2344}; 2345 2346/* This macro is used to compare a pointer to a mult_cost against an 2347 single integer "rtx_cost" value. This is equivalent to the macro 2348 CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}. */ 2349#define MULT_COST_LESS(X,Y) ((X)->cost < (Y) \ 2350 || ((X)->cost == (Y) && (X)->latency < (Y))) 2351 2352/* This macro is used to compare two pointers to mult_costs against 2353 each other. The macro returns true if X is cheaper than Y. 2354 Currently, the cheaper of two mult_costs is the one with the 2355 lower "cost". If "cost"s are tied, the lower latency is cheaper. */ 2356#define CHEAPER_MULT_COST(X,Y) ((X)->cost < (Y)->cost \ 2357 || ((X)->cost == (Y)->cost \ 2358 && (X)->latency < (Y)->latency)) 2359 2360/* This structure records a sequence of operations. 2361 `ops' is the number of operations recorded. 2362 `cost' is their total cost. 2363 The operations are stored in `op' and the corresponding 2364 logarithms of the integer coefficients in `log'. 2365 2366 These are the operations: 2367 alg_zero total := 0; 2368 alg_m total := multiplicand; 2369 alg_shift total := total * coeff 2370 alg_add_t_m2 total := total + multiplicand * coeff; 2371 alg_sub_t_m2 total := total - multiplicand * coeff; 2372 alg_add_factor total := total * coeff + total; 2373 alg_sub_factor total := total * coeff - total; 2374 alg_add_t2_m total := total * coeff + multiplicand; 2375 alg_sub_t2_m total := total * coeff - multiplicand; 2376 2377 The first operand must be either alg_zero or alg_m. */ 2378 2379struct algorithm 2380{ 2381 struct mult_cost cost; 2382 short ops; 2383 /* The size of the OP and LOG fields are not directly related to the 2384 word size, but the worst-case algorithms will be if we have few 2385 consecutive ones or zeros, i.e., a multiplicand like 10101010101... 2386 In that case we will generate shift-by-2, add, shift-by-2, add,..., 2387 in total wordsize operations. */ 2388 enum alg_code op[MAX_BITS_PER_WORD]; 2389 char log[MAX_BITS_PER_WORD]; 2390}; 2391 2392/* The entry for our multiplication cache/hash table. */ 2393struct alg_hash_entry { 2394 /* The number we are multiplying by. */ 2395 unsigned HOST_WIDE_INT t; 2396 2397 /* The mode in which we are multiplying something by T. */ 2398 enum machine_mode mode; 2399 2400 /* The best multiplication algorithm for t. */ 2401 enum alg_code alg; 2402 2403 /* The cost of multiplication if ALG_CODE is not alg_impossible. 2404 Otherwise, the cost within which multiplication by T is 2405 impossible. */ 2406 struct mult_cost cost; 2407}; 2408 2409/* The number of cache/hash entries. */ 2410#if HOST_BITS_PER_WIDE_INT == 64 2411#define NUM_ALG_HASH_ENTRIES 1031 2412#else 2413#define NUM_ALG_HASH_ENTRIES 307 2414#endif 2415 2416/* Each entry of ALG_HASH caches alg_code for some integer. This is 2417 actually a hash table. If we have a collision, that the older 2418 entry is kicked out. */ 2419static struct alg_hash_entry alg_hash[NUM_ALG_HASH_ENTRIES]; 2420 2421/* Indicates the type of fixup needed after a constant multiplication. 2422 BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that 2423 the result should be negated, and ADD_VARIANT means that the 2424 multiplicand should be added to the result. */ 2425enum mult_variant {basic_variant, negate_variant, add_variant}; 2426 2427static void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT, 2428 const struct mult_cost *, enum machine_mode mode); 2429static bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT, 2430 struct algorithm *, enum mult_variant *, int); 2431static rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx, 2432 const struct algorithm *, enum mult_variant); 2433static unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int, 2434 int, rtx *, int *, int *); 2435static unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int); 2436static rtx extract_high_half (enum machine_mode, rtx); 2437static rtx expand_mult_highpart (enum machine_mode, rtx, rtx, rtx, int, int); 2438static rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx, 2439 int, int); 2440/* Compute and return the best algorithm for multiplying by T. 2441 The algorithm must cost less than cost_limit 2442 If retval.cost >= COST_LIMIT, no algorithm was found and all 2443 other field of the returned struct are undefined. 2444 MODE is the machine mode of the multiplication. */ 2445 2446static void 2447synth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t, 2448 const struct mult_cost *cost_limit, enum machine_mode mode) 2449{ 2450 int m; 2451 struct algorithm *alg_in, *best_alg; 2452 struct mult_cost best_cost; 2453 struct mult_cost new_limit; 2454 int op_cost, op_latency; 2455 unsigned HOST_WIDE_INT q; 2456 int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode)); 2457 int hash_index; 2458 bool cache_hit = false; 2459 enum alg_code cache_alg = alg_zero; 2460 2461 /* Indicate that no algorithm is yet found. If no algorithm 2462 is found, this value will be returned and indicate failure. */ 2463 alg_out->cost.cost = cost_limit->cost + 1; 2464 alg_out->cost.latency = cost_limit->latency + 1; 2465 2466 if (cost_limit->cost < 0 2467 || (cost_limit->cost == 0 && cost_limit->latency <= 0)) 2468 return; 2469 2470 /* Restrict the bits of "t" to the multiplication's mode. */ 2471 t &= GET_MODE_MASK (mode); 2472 2473 /* t == 1 can be done in zero cost. */ 2474 if (t == 1) 2475 { 2476 alg_out->ops = 1; 2477 alg_out->cost.cost = 0; 2478 alg_out->cost.latency = 0; 2479 alg_out->op[0] = alg_m; 2480 return; 2481 } 2482 2483 /* t == 0 sometimes has a cost. If it does and it exceeds our limit, 2484 fail now. */ 2485 if (t == 0) 2486 { 2487 if (MULT_COST_LESS (cost_limit, zero_cost)) 2488 return; 2489 else 2490 { 2491 alg_out->ops = 1; 2492 alg_out->cost.cost = zero_cost; 2493 alg_out->cost.latency = zero_cost; 2494 alg_out->op[0] = alg_zero; 2495 return; 2496 } 2497 } 2498 2499 /* We'll be needing a couple extra algorithm structures now. */ 2500 2501 alg_in = alloca (sizeof (struct algorithm)); 2502 best_alg = alloca (sizeof (struct algorithm)); 2503 best_cost = *cost_limit; 2504 2505 /* Compute the hash index. */ 2506 hash_index = (t ^ (unsigned int) mode) % NUM_ALG_HASH_ENTRIES; 2507 2508 /* See if we already know what to do for T. */ 2509 if (alg_hash[hash_index].t == t 2510 && alg_hash[hash_index].mode == mode 2511 && alg_hash[hash_index].alg != alg_unknown) 2512 { 2513 cache_alg = alg_hash[hash_index].alg; 2514 2515 if (cache_alg == alg_impossible) 2516 { 2517 /* The cache tells us that it's impossible to synthesize 2518 multiplication by T within alg_hash[hash_index].cost. */ 2519 if (!CHEAPER_MULT_COST (&alg_hash[hash_index].cost, cost_limit)) 2520 /* COST_LIMIT is at least as restrictive as the one 2521 recorded in the hash table, in which case we have no 2522 hope of synthesizing a multiplication. Just 2523 return. */ 2524 return; 2525 2526 /* If we get here, COST_LIMIT is less restrictive than the 2527 one recorded in the hash table, so we may be able to 2528 synthesize a multiplication. Proceed as if we didn't 2529 have the cache entry. */ 2530 } 2531 else 2532 { 2533 if (CHEAPER_MULT_COST (cost_limit, &alg_hash[hash_index].cost)) 2534 /* The cached algorithm shows that this multiplication 2535 requires more cost than COST_LIMIT. Just return. This 2536 way, we don't clobber this cache entry with 2537 alg_impossible but retain useful information. */ 2538 return; 2539 2540 cache_hit = true; 2541 2542 switch (cache_alg) 2543 { 2544 case alg_shift: 2545 goto do_alg_shift; 2546 2547 case alg_add_t_m2: 2548 case alg_sub_t_m2: 2549 goto do_alg_addsub_t_m2; 2550 2551 case alg_add_factor: 2552 case alg_sub_factor: 2553 goto do_alg_addsub_factor; 2554 2555 case alg_add_t2_m: 2556 goto do_alg_add_t2_m; 2557 2558 case alg_sub_t2_m: 2559 goto do_alg_sub_t2_m; 2560 2561 default: 2562 gcc_unreachable (); 2563 } 2564 } 2565 } 2566 2567 /* If we have a group of zero bits at the low-order part of T, try 2568 multiplying by the remaining bits and then doing a shift. */ 2569 2570 if ((t & 1) == 0) 2571 { 2572 do_alg_shift: 2573 m = floor_log2 (t & -t); /* m = number of low zero bits */ 2574 if (m < maxm) 2575 { 2576 q = t >> m; 2577 /* The function expand_shift will choose between a shift and 2578 a sequence of additions, so the observed cost is given as 2579 MIN (m * add_cost[mode], shift_cost[mode][m]). */ 2580 op_cost = m * add_cost[mode]; 2581 if (shift_cost[mode][m] < op_cost) 2582 op_cost = shift_cost[mode][m]; 2583 new_limit.cost = best_cost.cost - op_cost; 2584 new_limit.latency = best_cost.latency - op_cost; 2585 synth_mult (alg_in, q, &new_limit, mode); 2586 2587 alg_in->cost.cost += op_cost; 2588 alg_in->cost.latency += op_cost; 2589 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2590 { 2591 struct algorithm *x; 2592 best_cost = alg_in->cost; 2593 x = alg_in, alg_in = best_alg, best_alg = x; 2594 best_alg->log[best_alg->ops] = m; 2595 best_alg->op[best_alg->ops] = alg_shift; 2596 } 2597 } 2598 if (cache_hit) 2599 goto done; 2600 } 2601 2602 /* If we have an odd number, add or subtract one. */ 2603 if ((t & 1) != 0) 2604 { 2605 unsigned HOST_WIDE_INT w; 2606 2607 do_alg_addsub_t_m2: 2608 for (w = 1; (w & t) != 0; w <<= 1) 2609 ; 2610 /* If T was -1, then W will be zero after the loop. This is another 2611 case where T ends with ...111. Handling this with (T + 1) and 2612 subtract 1 produces slightly better code and results in algorithm 2613 selection much faster than treating it like the ...0111 case 2614 below. */ 2615 if (w == 0 2616 || (w > 2 2617 /* Reject the case where t is 3. 2618 Thus we prefer addition in that case. */ 2619 && t != 3)) 2620 { 2621 /* T ends with ...111. Multiply by (T + 1) and subtract 1. */ 2622 2623 op_cost = add_cost[mode]; 2624 new_limit.cost = best_cost.cost - op_cost; 2625 new_limit.latency = best_cost.latency - op_cost; 2626 synth_mult (alg_in, t + 1, &new_limit, mode); 2627 2628 alg_in->cost.cost += op_cost; 2629 alg_in->cost.latency += op_cost; 2630 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2631 { 2632 struct algorithm *x; 2633 best_cost = alg_in->cost; 2634 x = alg_in, alg_in = best_alg, best_alg = x; 2635 best_alg->log[best_alg->ops] = 0; 2636 best_alg->op[best_alg->ops] = alg_sub_t_m2; 2637 } 2638 } 2639 else 2640 { 2641 /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */ 2642 2643 op_cost = add_cost[mode]; 2644 new_limit.cost = best_cost.cost - op_cost; 2645 new_limit.latency = best_cost.latency - op_cost; 2646 synth_mult (alg_in, t - 1, &new_limit, mode); 2647 2648 alg_in->cost.cost += op_cost; 2649 alg_in->cost.latency += op_cost; 2650 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2651 { 2652 struct algorithm *x; 2653 best_cost = alg_in->cost; 2654 x = alg_in, alg_in = best_alg, best_alg = x; 2655 best_alg->log[best_alg->ops] = 0; 2656 best_alg->op[best_alg->ops] = alg_add_t_m2; 2657 } 2658 } 2659 if (cache_hit) 2660 goto done; 2661 } 2662 2663 /* Look for factors of t of the form 2664 t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)). 2665 If we find such a factor, we can multiply by t using an algorithm that 2666 multiplies by q, shift the result by m and add/subtract it to itself. 2667 2668 We search for large factors first and loop down, even if large factors 2669 are less probable than small; if we find a large factor we will find a 2670 good sequence quickly, and therefore be able to prune (by decreasing 2671 COST_LIMIT) the search. */ 2672 2673 do_alg_addsub_factor: 2674 for (m = floor_log2 (t - 1); m >= 2; m--) 2675 { 2676 unsigned HOST_WIDE_INT d; 2677 2678 d = ((unsigned HOST_WIDE_INT) 1 << m) + 1; 2679 if (t % d == 0 && t > d && m < maxm 2680 && (!cache_hit || cache_alg == alg_add_factor)) 2681 { 2682 /* If the target has a cheap shift-and-add instruction use 2683 that in preference to a shift insn followed by an add insn. 2684 Assume that the shift-and-add is "atomic" with a latency 2685 equal to its cost, otherwise assume that on superscalar 2686 hardware the shift may be executed concurrently with the 2687 earlier steps in the algorithm. */ 2688 op_cost = add_cost[mode] + shift_cost[mode][m]; 2689 if (shiftadd_cost[mode][m] < op_cost) 2690 { 2691 op_cost = shiftadd_cost[mode][m]; 2692 op_latency = op_cost; 2693 } 2694 else 2695 op_latency = add_cost[mode]; 2696 2697 new_limit.cost = best_cost.cost - op_cost; 2698 new_limit.latency = best_cost.latency - op_latency; 2699 synth_mult (alg_in, t / d, &new_limit, mode); 2700 2701 alg_in->cost.cost += op_cost; 2702 alg_in->cost.latency += op_latency; 2703 if (alg_in->cost.latency < op_cost) 2704 alg_in->cost.latency = op_cost; 2705 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2706 { 2707 struct algorithm *x; 2708 best_cost = alg_in->cost; 2709 x = alg_in, alg_in = best_alg, best_alg = x; 2710 best_alg->log[best_alg->ops] = m; 2711 best_alg->op[best_alg->ops] = alg_add_factor; 2712 } 2713 /* Other factors will have been taken care of in the recursion. */ 2714 break; 2715 } 2716 2717 d = ((unsigned HOST_WIDE_INT) 1 << m) - 1; 2718 if (t % d == 0 && t > d && m < maxm 2719 && (!cache_hit || cache_alg == alg_sub_factor)) 2720 { 2721 /* If the target has a cheap shift-and-subtract insn use 2722 that in preference to a shift insn followed by a sub insn. 2723 Assume that the shift-and-sub is "atomic" with a latency 2724 equal to it's cost, otherwise assume that on superscalar 2725 hardware the shift may be executed concurrently with the 2726 earlier steps in the algorithm. */ 2727 op_cost = add_cost[mode] + shift_cost[mode][m]; 2728 if (shiftsub_cost[mode][m] < op_cost) 2729 { 2730 op_cost = shiftsub_cost[mode][m]; 2731 op_latency = op_cost; 2732 } 2733 else 2734 op_latency = add_cost[mode]; 2735 2736 new_limit.cost = best_cost.cost - op_cost; 2737 new_limit.latency = best_cost.latency - op_latency; 2738 synth_mult (alg_in, t / d, &new_limit, mode); 2739 2740 alg_in->cost.cost += op_cost; 2741 alg_in->cost.latency += op_latency; 2742 if (alg_in->cost.latency < op_cost) 2743 alg_in->cost.latency = op_cost; 2744 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2745 { 2746 struct algorithm *x; 2747 best_cost = alg_in->cost; 2748 x = alg_in, alg_in = best_alg, best_alg = x; 2749 best_alg->log[best_alg->ops] = m; 2750 best_alg->op[best_alg->ops] = alg_sub_factor; 2751 } 2752 break; 2753 } 2754 } 2755 if (cache_hit) 2756 goto done; 2757 2758 /* Try shift-and-add (load effective address) instructions, 2759 i.e. do a*3, a*5, a*9. */ 2760 if ((t & 1) != 0) 2761 { 2762 do_alg_add_t2_m: 2763 q = t - 1; 2764 q = q & -q; 2765 m = exact_log2 (q); 2766 if (m >= 0 && m < maxm) 2767 { 2768 op_cost = shiftadd_cost[mode][m]; 2769 new_limit.cost = best_cost.cost - op_cost; 2770 new_limit.latency = best_cost.latency - op_cost; 2771 synth_mult (alg_in, (t - 1) >> m, &new_limit, mode); 2772 2773 alg_in->cost.cost += op_cost; 2774 alg_in->cost.latency += op_cost; 2775 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2776 { 2777 struct algorithm *x; 2778 best_cost = alg_in->cost; 2779 x = alg_in, alg_in = best_alg, best_alg = x; 2780 best_alg->log[best_alg->ops] = m; 2781 best_alg->op[best_alg->ops] = alg_add_t2_m; 2782 } 2783 } 2784 if (cache_hit) 2785 goto done; 2786 2787 do_alg_sub_t2_m: 2788 q = t + 1; 2789 q = q & -q; 2790 m = exact_log2 (q); 2791 if (m >= 0 && m < maxm) 2792 { 2793 op_cost = shiftsub_cost[mode][m]; 2794 new_limit.cost = best_cost.cost - op_cost; 2795 new_limit.latency = best_cost.latency - op_cost; 2796 synth_mult (alg_in, (t + 1) >> m, &new_limit, mode); 2797 2798 alg_in->cost.cost += op_cost; 2799 alg_in->cost.latency += op_cost; 2800 if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 2801 { 2802 struct algorithm *x; 2803 best_cost = alg_in->cost; 2804 x = alg_in, alg_in = best_alg, best_alg = x; 2805 best_alg->log[best_alg->ops] = m; 2806 best_alg->op[best_alg->ops] = alg_sub_t2_m; 2807 } 2808 } 2809 if (cache_hit) 2810 goto done; 2811 } 2812 2813 done: 2814 /* If best_cost has not decreased, we have not found any algorithm. */ 2815 if (!CHEAPER_MULT_COST (&best_cost, cost_limit)) 2816 { 2817 /* We failed to find an algorithm. Record alg_impossible for 2818 this case (that is, <T, MODE, COST_LIMIT>) so that next time 2819 we are asked to find an algorithm for T within the same or 2820 lower COST_LIMIT, we can immediately return to the 2821 caller. */ 2822 alg_hash[hash_index].t = t; 2823 alg_hash[hash_index].mode = mode; 2824 alg_hash[hash_index].alg = alg_impossible; 2825 alg_hash[hash_index].cost = *cost_limit; 2826 return; 2827 } 2828 2829 /* Cache the result. */ 2830 if (!cache_hit) 2831 { 2832 alg_hash[hash_index].t = t; 2833 alg_hash[hash_index].mode = mode; 2834 alg_hash[hash_index].alg = best_alg->op[best_alg->ops]; 2835 alg_hash[hash_index].cost.cost = best_cost.cost; 2836 alg_hash[hash_index].cost.latency = best_cost.latency; 2837 } 2838 2839 /* If we are getting a too long sequence for `struct algorithm' 2840 to record, make this search fail. */ 2841 if (best_alg->ops == MAX_BITS_PER_WORD) 2842 return; 2843 2844 /* Copy the algorithm from temporary space to the space at alg_out. 2845 We avoid using structure assignment because the majority of 2846 best_alg is normally undefined, and this is a critical function. */ 2847 alg_out->ops = best_alg->ops + 1; 2848 alg_out->cost = best_cost; 2849 memcpy (alg_out->op, best_alg->op, 2850 alg_out->ops * sizeof *alg_out->op); 2851 memcpy (alg_out->log, best_alg->log, 2852 alg_out->ops * sizeof *alg_out->log); 2853} 2854 2855/* Find the cheapest way of multiplying a value of mode MODE by VAL. 2856 Try three variations: 2857 2858 - a shift/add sequence based on VAL itself 2859 - a shift/add sequence based on -VAL, followed by a negation 2860 - a shift/add sequence based on VAL - 1, followed by an addition. 2861 2862 Return true if the cheapest of these cost less than MULT_COST, 2863 describing the algorithm in *ALG and final fixup in *VARIANT. */ 2864 2865static bool 2866choose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val, 2867 struct algorithm *alg, enum mult_variant *variant, 2868 int mult_cost) 2869{ 2870 struct algorithm alg2; 2871 struct mult_cost limit; 2872 int op_cost; 2873 2874 /* Fail quickly for impossible bounds. */ 2875 if (mult_cost < 0) 2876 return false; 2877 2878 /* Ensure that mult_cost provides a reasonable upper bound. 2879 Any constant multiplication can be performed with less 2880 than 2 * bits additions. */ 2881 op_cost = 2 * GET_MODE_BITSIZE (mode) * add_cost[mode]; 2882 if (mult_cost > op_cost) 2883 mult_cost = op_cost; 2884 2885 *variant = basic_variant; 2886 limit.cost = mult_cost; 2887 limit.latency = mult_cost; 2888 synth_mult (alg, val, &limit, mode); 2889 2890 /* This works only if the inverted value actually fits in an 2891 `unsigned int' */ 2892 if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode)) 2893 { 2894 op_cost = neg_cost[mode]; 2895 if (MULT_COST_LESS (&alg->cost, mult_cost)) 2896 { 2897 limit.cost = alg->cost.cost - op_cost; 2898 limit.latency = alg->cost.latency - op_cost; 2899 } 2900 else 2901 { 2902 limit.cost = mult_cost - op_cost; 2903 limit.latency = mult_cost - op_cost; 2904 } 2905 2906 synth_mult (&alg2, -val, &limit, mode); 2907 alg2.cost.cost += op_cost; 2908 alg2.cost.latency += op_cost; 2909 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost)) 2910 *alg = alg2, *variant = negate_variant; 2911 } 2912 2913 /* This proves very useful for division-by-constant. */ 2914 op_cost = add_cost[mode]; 2915 if (MULT_COST_LESS (&alg->cost, mult_cost)) 2916 { 2917 limit.cost = alg->cost.cost - op_cost; 2918 limit.latency = alg->cost.latency - op_cost; 2919 } 2920 else 2921 { 2922 limit.cost = mult_cost - op_cost; 2923 limit.latency = mult_cost - op_cost; 2924 } 2925 2926 synth_mult (&alg2, val - 1, &limit, mode); 2927 alg2.cost.cost += op_cost; 2928 alg2.cost.latency += op_cost; 2929 if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost)) 2930 *alg = alg2, *variant = add_variant; 2931 2932 return MULT_COST_LESS (&alg->cost, mult_cost); 2933} 2934 2935/* A subroutine of expand_mult, used for constant multiplications. 2936 Multiply OP0 by VAL in mode MODE, storing the result in TARGET if 2937 convenient. Use the shift/add sequence described by ALG and apply 2938 the final fixup specified by VARIANT. */ 2939 2940static rtx 2941expand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val, 2942 rtx target, const struct algorithm *alg, 2943 enum mult_variant variant) 2944{ 2945 HOST_WIDE_INT val_so_far; 2946 rtx insn, accum, tem; 2947 int opno; 2948 enum machine_mode nmode; 2949 2950 /* Avoid referencing memory over and over. 2951 For speed, but also for correctness when mem is volatile. */ 2952 if (MEM_P (op0)) 2953 op0 = force_reg (mode, op0); 2954 2955 /* ACCUM starts out either as OP0 or as a zero, depending on 2956 the first operation. */ 2957 2958 if (alg->op[0] == alg_zero) 2959 { 2960 accum = copy_to_mode_reg (mode, const0_rtx); 2961 val_so_far = 0; 2962 } 2963 else if (alg->op[0] == alg_m) 2964 { 2965 accum = copy_to_mode_reg (mode, op0); 2966 val_so_far = 1; 2967 } 2968 else 2969 gcc_unreachable (); 2970 2971 for (opno = 1; opno < alg->ops; opno++) 2972 { 2973 int log = alg->log[opno]; 2974 rtx shift_subtarget = optimize ? 0 : accum; 2975 rtx add_target 2976 = (opno == alg->ops - 1 && target != 0 && variant != add_variant 2977 && !optimize) 2978 ? target : 0; 2979 rtx accum_target = optimize ? 0 : accum; 2980 2981 switch (alg->op[opno]) 2982 { 2983 case alg_shift: 2984 accum = expand_shift (LSHIFT_EXPR, mode, accum, 2985 build_int_cst (NULL_TREE, log), 2986 NULL_RTX, 0); 2987 val_so_far <<= log; 2988 break; 2989 2990 case alg_add_t_m2: 2991 tem = expand_shift (LSHIFT_EXPR, mode, op0, 2992 build_int_cst (NULL_TREE, log), 2993 NULL_RTX, 0); 2994 accum = force_operand (gen_rtx_PLUS (mode, accum, tem), 2995 add_target ? add_target : accum_target); 2996 val_so_far += (HOST_WIDE_INT) 1 << log; 2997 break; 2998 2999 case alg_sub_t_m2: 3000 tem = expand_shift (LSHIFT_EXPR, mode, op0, 3001 build_int_cst (NULL_TREE, log), 3002 NULL_RTX, 0); 3003 accum = force_operand (gen_rtx_MINUS (mode, accum, tem), 3004 add_target ? add_target : accum_target); 3005 val_so_far -= (HOST_WIDE_INT) 1 << log; 3006 break; 3007 3008 case alg_add_t2_m: 3009 accum = expand_shift (LSHIFT_EXPR, mode, accum, 3010 build_int_cst (NULL_TREE, log), 3011 shift_subtarget, 3012 0); 3013 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), 3014 add_target ? add_target : accum_target); 3015 val_so_far = (val_so_far << log) + 1; 3016 break; 3017 3018 case alg_sub_t2_m: 3019 accum = expand_shift (LSHIFT_EXPR, mode, accum, 3020 build_int_cst (NULL_TREE, log), 3021 shift_subtarget, 0); 3022 accum = force_operand (gen_rtx_MINUS (mode, accum, op0), 3023 add_target ? add_target : accum_target); 3024 val_so_far = (val_so_far << log) - 1; 3025 break; 3026 3027 case alg_add_factor: 3028 tem = expand_shift (LSHIFT_EXPR, mode, accum, 3029 build_int_cst (NULL_TREE, log), 3030 NULL_RTX, 0); 3031 accum = force_operand (gen_rtx_PLUS (mode, accum, tem), 3032 add_target ? add_target : accum_target); 3033 val_so_far += val_so_far << log; 3034 break; 3035 3036 case alg_sub_factor: 3037 tem = expand_shift (LSHIFT_EXPR, mode, accum, 3038 build_int_cst (NULL_TREE, log), 3039 NULL_RTX, 0); 3040 accum = force_operand (gen_rtx_MINUS (mode, tem, accum), 3041 (add_target 3042 ? add_target : (optimize ? 0 : tem))); 3043 val_so_far = (val_so_far << log) - val_so_far; 3044 break; 3045 3046 default: 3047 gcc_unreachable (); 3048 } 3049 3050 /* Write a REG_EQUAL note on the last insn so that we can cse 3051 multiplication sequences. Note that if ACCUM is a SUBREG, 3052 we've set the inner register and must properly indicate 3053 that. */ 3054 3055 tem = op0, nmode = mode; 3056 if (GET_CODE (accum) == SUBREG) 3057 { 3058 nmode = GET_MODE (SUBREG_REG (accum)); 3059 tem = gen_lowpart (nmode, op0); 3060 } 3061 3062 insn = get_last_insn (); 3063 set_unique_reg_note (insn, REG_EQUAL, 3064 gen_rtx_MULT (nmode, tem, GEN_INT (val_so_far))); 3065 } 3066 3067 if (variant == negate_variant) 3068 { 3069 val_so_far = -val_so_far; 3070 accum = expand_unop (mode, neg_optab, accum, target, 0); 3071 } 3072 else if (variant == add_variant) 3073 { 3074 val_so_far = val_so_far + 1; 3075 accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target); 3076 } 3077 3078 /* Compare only the bits of val and val_so_far that are significant 3079 in the result mode, to avoid sign-/zero-extension confusion. */ 3080 val &= GET_MODE_MASK (mode); 3081 val_so_far &= GET_MODE_MASK (mode); 3082 gcc_assert (val == val_so_far); 3083 3084 return accum; 3085} 3086 3087/* Perform a multiplication and return an rtx for the result. 3088 MODE is mode of value; OP0 and OP1 are what to multiply (rtx's); 3089 TARGET is a suggestion for where to store the result (an rtx). 3090 3091 We check specially for a constant integer as OP1. 3092 If you want this check for OP0 as well, then before calling 3093 you should swap the two operands if OP0 would be constant. */ 3094 3095rtx 3096expand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target, 3097 int unsignedp) 3098{ 3099 enum mult_variant variant; 3100 struct algorithm algorithm; 3101 int max_cost; 3102 3103 /* Handling const0_rtx here allows us to use zero as a rogue value for 3104 coeff below. */ 3105 if (op1 == const0_rtx) 3106 return const0_rtx; 3107 if (op1 == const1_rtx) 3108 return op0; 3109 if (op1 == constm1_rtx) 3110 return expand_unop (mode, 3111 GET_MODE_CLASS (mode) == MODE_INT 3112 && !unsignedp && flag_trapv 3113 ? negv_optab : neg_optab, 3114 op0, target, 0); 3115 3116 /* These are the operations that are potentially turned into a sequence 3117 of shifts and additions. */ 3118 if (SCALAR_INT_MODE_P (mode) 3119 && (unsignedp || !flag_trapv)) 3120 { 3121 HOST_WIDE_INT coeff = 0; 3122 rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1); 3123 3124 /* synth_mult does an `unsigned int' multiply. As long as the mode is 3125 less than or equal in size to `unsigned int' this doesn't matter. 3126 If the mode is larger than `unsigned int', then synth_mult works 3127 only if the constant value exactly fits in an `unsigned int' without 3128 any truncation. This means that multiplying by negative values does 3129 not work; results are off by 2^32 on a 32 bit machine. */ 3130 3131 if (GET_CODE (op1) == CONST_INT) 3132 { 3133 /* Attempt to handle multiplication of DImode values by negative 3134 coefficients, by performing the multiplication by a positive 3135 multiplier and then inverting the result. */ 3136 if (INTVAL (op1) < 0 3137 && GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT) 3138 { 3139 /* Its safe to use -INTVAL (op1) even for INT_MIN, as the 3140 result is interpreted as an unsigned coefficient. 3141 Exclude cost of op0 from max_cost to match the cost 3142 calculation of the synth_mult. */ 3143 max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET) 3144 - neg_cost[mode]; 3145 if (max_cost > 0 3146 && choose_mult_variant (mode, -INTVAL (op1), &algorithm, 3147 &variant, max_cost)) 3148 { 3149 rtx temp = expand_mult_const (mode, op0, -INTVAL (op1), 3150 NULL_RTX, &algorithm, 3151 variant); 3152 return expand_unop (mode, neg_optab, temp, target, 0); 3153 } 3154 } 3155 else coeff = INTVAL (op1); 3156 } 3157 else if (GET_CODE (op1) == CONST_DOUBLE) 3158 { 3159 /* If we are multiplying in DImode, it may still be a win 3160 to try to work with shifts and adds. */ 3161 if (CONST_DOUBLE_HIGH (op1) == 0) 3162 coeff = CONST_DOUBLE_LOW (op1); 3163 else if (CONST_DOUBLE_LOW (op1) == 0 3164 && EXACT_POWER_OF_2_OR_ZERO_P (CONST_DOUBLE_HIGH (op1))) 3165 { 3166 int shift = floor_log2 (CONST_DOUBLE_HIGH (op1)) 3167 + HOST_BITS_PER_WIDE_INT; 3168 return expand_shift (LSHIFT_EXPR, mode, op0, 3169 build_int_cst (NULL_TREE, shift), 3170 target, unsignedp); 3171 } 3172 } 3173 3174 /* We used to test optimize here, on the grounds that it's better to 3175 produce a smaller program when -O is not used. But this causes 3176 such a terrible slowdown sometimes that it seems better to always 3177 use synth_mult. */ 3178 if (coeff != 0) 3179 { 3180 /* Special case powers of two. */ 3181 if (EXACT_POWER_OF_2_OR_ZERO_P (coeff)) 3182 return expand_shift (LSHIFT_EXPR, mode, op0, 3183 build_int_cst (NULL_TREE, floor_log2 (coeff)), 3184 target, unsignedp); 3185 3186 /* Exclude cost of op0 from max_cost to match the cost 3187 calculation of the synth_mult. */ 3188 max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET); 3189 if (choose_mult_variant (mode, coeff, &algorithm, &variant, 3190 max_cost)) 3191 return expand_mult_const (mode, op0, coeff, target, 3192 &algorithm, variant); 3193 } 3194 } 3195 3196 if (GET_CODE (op0) == CONST_DOUBLE) 3197 { 3198 rtx temp = op0; 3199 op0 = op1; 3200 op1 = temp; 3201 } 3202 3203 /* Expand x*2.0 as x+x. */ 3204 if (GET_CODE (op1) == CONST_DOUBLE 3205 && GET_MODE_CLASS (mode) == MODE_FLOAT) 3206 { 3207 REAL_VALUE_TYPE d; 3208 REAL_VALUE_FROM_CONST_DOUBLE (d, op1); 3209 3210 if (REAL_VALUES_EQUAL (d, dconst2)) 3211 { 3212 op0 = force_reg (GET_MODE (op0), op0); 3213 return expand_binop (mode, add_optab, op0, op0, 3214 target, unsignedp, OPTAB_LIB_WIDEN); 3215 } 3216 } 3217 3218 /* This used to use umul_optab if unsigned, but for non-widening multiply 3219 there is no difference between signed and unsigned. */ 3220 op0 = expand_binop (mode, 3221 ! unsignedp 3222 && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT) 3223 ? smulv_optab : smul_optab, 3224 op0, op1, target, unsignedp, OPTAB_LIB_WIDEN); 3225 gcc_assert (op0); 3226 return op0; 3227} 3228 3229/* Return the smallest n such that 2**n >= X. */ 3230 3231int 3232ceil_log2 (unsigned HOST_WIDE_INT x) 3233{ 3234 return floor_log2 (x - 1) + 1; 3235} 3236 3237/* Choose a minimal N + 1 bit approximation to 1/D that can be used to 3238 replace division by D, and put the least significant N bits of the result 3239 in *MULTIPLIER_PTR and return the most significant bit. 3240 3241 The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the 3242 needed precision is in PRECISION (should be <= N). 3243 3244 PRECISION should be as small as possible so this function can choose 3245 multiplier more freely. 3246 3247 The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that 3248 is to be used for a final right shift is placed in *POST_SHIFT_PTR. 3249 3250 Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR), 3251 where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */ 3252 3253static 3254unsigned HOST_WIDE_INT 3255choose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision, 3256 rtx *multiplier_ptr, int *post_shift_ptr, int *lgup_ptr) 3257{ 3258 HOST_WIDE_INT mhigh_hi, mlow_hi; 3259 unsigned HOST_WIDE_INT mhigh_lo, mlow_lo; 3260 int lgup, post_shift; 3261 int pow, pow2; 3262 unsigned HOST_WIDE_INT nl, dummy1; 3263 HOST_WIDE_INT nh, dummy2; 3264 3265 /* lgup = ceil(log2(divisor)); */ 3266 lgup = ceil_log2 (d); 3267 3268 gcc_assert (lgup <= n); 3269 3270 pow = n + lgup; 3271 pow2 = n + lgup - precision; 3272 3273 /* We could handle this with some effort, but this case is much 3274 better handled directly with a scc insn, so rely on caller using 3275 that. */ 3276 gcc_assert (pow != 2 * HOST_BITS_PER_WIDE_INT); 3277 3278 /* mlow = 2^(N + lgup)/d */ 3279 if (pow >= HOST_BITS_PER_WIDE_INT) 3280 { 3281 nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT); 3282 nl = 0; 3283 } 3284 else 3285 { 3286 nh = 0; 3287 nl = (unsigned HOST_WIDE_INT) 1 << pow; 3288 } 3289 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0, 3290 &mlow_lo, &mlow_hi, &dummy1, &dummy2); 3291 3292 /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */ 3293 if (pow2 >= HOST_BITS_PER_WIDE_INT) 3294 nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT); 3295 else 3296 nl |= (unsigned HOST_WIDE_INT) 1 << pow2; 3297 div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0, 3298 &mhigh_lo, &mhigh_hi, &dummy1, &dummy2); 3299 3300 gcc_assert (!mhigh_hi || nh - d < d); 3301 gcc_assert (mhigh_hi <= 1 && mlow_hi <= 1); 3302 /* Assert that mlow < mhigh. */ 3303 gcc_assert (mlow_hi < mhigh_hi 3304 || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)); 3305 3306 /* If precision == N, then mlow, mhigh exceed 2^N 3307 (but they do not exceed 2^(N+1)). */ 3308 3309 /* Reduce to lowest terms. */ 3310 for (post_shift = lgup; post_shift > 0; post_shift--) 3311 { 3312 unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1); 3313 unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1); 3314 if (ml_lo >= mh_lo) 3315 break; 3316 3317 mlow_hi = 0; 3318 mlow_lo = ml_lo; 3319 mhigh_hi = 0; 3320 mhigh_lo = mh_lo; 3321 } 3322 3323 *post_shift_ptr = post_shift; 3324 *lgup_ptr = lgup; 3325 if (n < HOST_BITS_PER_WIDE_INT) 3326 { 3327 unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1; 3328 *multiplier_ptr = GEN_INT (mhigh_lo & mask); 3329 return mhigh_lo >= mask; 3330 } 3331 else 3332 { 3333 *multiplier_ptr = GEN_INT (mhigh_lo); 3334 return mhigh_hi; 3335 } 3336} 3337 3338/* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is 3339 congruent to 1 (mod 2**N). */ 3340 3341static unsigned HOST_WIDE_INT 3342invert_mod2n (unsigned HOST_WIDE_INT x, int n) 3343{ 3344 /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */ 3345 3346 /* The algorithm notes that the choice y = x satisfies 3347 x*y == 1 mod 2^3, since x is assumed odd. 3348 Each iteration doubles the number of bits of significance in y. */ 3349 3350 unsigned HOST_WIDE_INT mask; 3351 unsigned HOST_WIDE_INT y = x; 3352 int nbit = 3; 3353 3354 mask = (n == HOST_BITS_PER_WIDE_INT 3355 ? ~(unsigned HOST_WIDE_INT) 0 3356 : ((unsigned HOST_WIDE_INT) 1 << n) - 1); 3357 3358 while (nbit < n) 3359 { 3360 y = y * (2 - x*y) & mask; /* Modulo 2^N */ 3361 nbit *= 2; 3362 } 3363 return y; 3364} 3365 3366/* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness 3367 flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the 3368 product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product 3369 to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to 3370 become signed. 3371 3372 The result is put in TARGET if that is convenient. 3373 3374 MODE is the mode of operation. */ 3375 3376rtx 3377expand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0, 3378 rtx op1, rtx target, int unsignedp) 3379{ 3380 rtx tem; 3381 enum rtx_code adj_code = unsignedp ? PLUS : MINUS; 3382 3383 tem = expand_shift (RSHIFT_EXPR, mode, op0, 3384 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1), 3385 NULL_RTX, 0); 3386 tem = expand_and (mode, tem, op1, NULL_RTX); 3387 adj_operand 3388 = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem), 3389 adj_operand); 3390 3391 tem = expand_shift (RSHIFT_EXPR, mode, op1, 3392 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1), 3393 NULL_RTX, 0); 3394 tem = expand_and (mode, tem, op0, NULL_RTX); 3395 target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem), 3396 target); 3397 3398 return target; 3399} 3400 3401/* Subroutine of expand_mult_highpart. Return the MODE high part of OP. */ 3402 3403static rtx 3404extract_high_half (enum machine_mode mode, rtx op) 3405{ 3406 enum machine_mode wider_mode; 3407 3408 if (mode == word_mode) 3409 return gen_highpart (mode, op); 3410 3411 wider_mode = GET_MODE_WIDER_MODE (mode); 3412 op = expand_shift (RSHIFT_EXPR, wider_mode, op, 3413 build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode)), 0, 1); 3414 return convert_modes (mode, wider_mode, op, 0); 3415} 3416 3417/* Like expand_mult_highpart, but only consider using a multiplication 3418 optab. OP1 is an rtx for the constant operand. */ 3419 3420static rtx 3421expand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1, 3422 rtx target, int unsignedp, int max_cost) 3423{ 3424 rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode); 3425 enum machine_mode wider_mode; 3426 optab moptab; 3427 rtx tem; 3428 int size; 3429 3430 wider_mode = GET_MODE_WIDER_MODE (mode); 3431 size = GET_MODE_BITSIZE (mode); 3432 3433 /* Firstly, try using a multiplication insn that only generates the needed 3434 high part of the product, and in the sign flavor of unsignedp. */ 3435 if (mul_highpart_cost[mode] < max_cost) 3436 { 3437 moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab; 3438 tem = expand_binop (mode, moptab, op0, narrow_op1, target, 3439 unsignedp, OPTAB_DIRECT); 3440 if (tem) 3441 return tem; 3442 } 3443 3444 /* Secondly, same as above, but use sign flavor opposite of unsignedp. 3445 Need to adjust the result after the multiplication. */ 3446 if (size - 1 < BITS_PER_WORD 3447 && (mul_highpart_cost[mode] + 2 * shift_cost[mode][size-1] 3448 + 4 * add_cost[mode] < max_cost)) 3449 { 3450 moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab; 3451 tem = expand_binop (mode, moptab, op0, narrow_op1, target, 3452 unsignedp, OPTAB_DIRECT); 3453 if (tem) 3454 /* We used the wrong signedness. Adjust the result. */ 3455 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1, 3456 tem, unsignedp); 3457 } 3458 3459 /* Try widening multiplication. */ 3460 moptab = unsignedp ? umul_widen_optab : smul_widen_optab; 3461 if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing 3462 && mul_widen_cost[wider_mode] < max_cost) 3463 { 3464 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0, 3465 unsignedp, OPTAB_WIDEN); 3466 if (tem) 3467 return extract_high_half (mode, tem); 3468 } 3469 3470 /* Try widening the mode and perform a non-widening multiplication. */ 3471 if (smul_optab->handlers[wider_mode].insn_code != CODE_FOR_nothing 3472 && size - 1 < BITS_PER_WORD 3473 && mul_cost[wider_mode] + shift_cost[mode][size-1] < max_cost) 3474 { 3475 rtx insns, wop0, wop1; 3476 3477 /* We need to widen the operands, for example to ensure the 3478 constant multiplier is correctly sign or zero extended. 3479 Use a sequence to clean-up any instructions emitted by 3480 the conversions if things don't work out. */ 3481 start_sequence (); 3482 wop0 = convert_modes (wider_mode, mode, op0, unsignedp); 3483 wop1 = convert_modes (wider_mode, mode, op1, unsignedp); 3484 tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0, 3485 unsignedp, OPTAB_WIDEN); 3486 insns = get_insns (); 3487 end_sequence (); 3488 3489 if (tem) 3490 { 3491 emit_insn (insns); 3492 return extract_high_half (mode, tem); 3493 } 3494 } 3495 3496 /* Try widening multiplication of opposite signedness, and adjust. */ 3497 moptab = unsignedp ? smul_widen_optab : umul_widen_optab; 3498 if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing 3499 && size - 1 < BITS_PER_WORD 3500 && (mul_widen_cost[wider_mode] + 2 * shift_cost[mode][size-1] 3501 + 4 * add_cost[mode] < max_cost)) 3502 { 3503 tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 3504 NULL_RTX, ! unsignedp, OPTAB_WIDEN); 3505 if (tem != 0) 3506 { 3507 tem = extract_high_half (mode, tem); 3508 /* We used the wrong signedness. Adjust the result. */ 3509 return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1, 3510 target, unsignedp); 3511 } 3512 } 3513 3514 return 0; 3515} 3516 3517/* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant), 3518 putting the high half of the result in TARGET if that is convenient, 3519 and return where the result is. If the operation can not be performed, 3520 0 is returned. 3521 3522 MODE is the mode of operation and result. 3523 3524 UNSIGNEDP nonzero means unsigned multiply. 3525 3526 MAX_COST is the total allowed cost for the expanded RTL. */ 3527 3528static rtx 3529expand_mult_highpart (enum machine_mode mode, rtx op0, rtx op1, 3530 rtx target, int unsignedp, int max_cost) 3531{ 3532 enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode); 3533 unsigned HOST_WIDE_INT cnst1; 3534 int extra_cost; 3535 bool sign_adjust = false; 3536 enum mult_variant variant; 3537 struct algorithm alg; 3538 rtx tem; 3539 3540 /* We can't support modes wider than HOST_BITS_PER_INT. */ 3541 gcc_assert (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT); 3542 3543 cnst1 = INTVAL (op1) & GET_MODE_MASK (mode); 3544 3545 /* We can't optimize modes wider than BITS_PER_WORD. 3546 ??? We might be able to perform double-word arithmetic if 3547 mode == word_mode, however all the cost calculations in 3548 synth_mult etc. assume single-word operations. */ 3549 if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD) 3550 return expand_mult_highpart_optab (mode, op0, op1, target, 3551 unsignedp, max_cost); 3552 3553 extra_cost = shift_cost[mode][GET_MODE_BITSIZE (mode) - 1]; 3554 3555 /* Check whether we try to multiply by a negative constant. */ 3556 if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1)) 3557 { 3558 sign_adjust = true; 3559 extra_cost += add_cost[mode]; 3560 } 3561 3562 /* See whether shift/add multiplication is cheap enough. */ 3563 if (choose_mult_variant (wider_mode, cnst1, &alg, &variant, 3564 max_cost - extra_cost)) 3565 { 3566 /* See whether the specialized multiplication optabs are 3567 cheaper than the shift/add version. */ 3568 tem = expand_mult_highpart_optab (mode, op0, op1, target, unsignedp, 3569 alg.cost.cost + extra_cost); 3570 if (tem) 3571 return tem; 3572 3573 tem = convert_to_mode (wider_mode, op0, unsignedp); 3574 tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant); 3575 tem = extract_high_half (mode, tem); 3576 3577 /* Adjust result for signedness. */ 3578 if (sign_adjust) 3579 tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem); 3580 3581 return tem; 3582 } 3583 return expand_mult_highpart_optab (mode, op0, op1, target, 3584 unsignedp, max_cost); 3585} 3586 3587 3588/* Expand signed modulus of OP0 by a power of two D in mode MODE. */ 3589 3590static rtx 3591expand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d) 3592{ 3593 unsigned HOST_WIDE_INT masklow, maskhigh; 3594 rtx result, temp, shift, label; 3595 int logd; 3596 3597 logd = floor_log2 (d); 3598 result = gen_reg_rtx (mode); 3599 3600 /* Avoid conditional branches when they're expensive. */ 3601 if (BRANCH_COST >= 2 3602 && !optimize_size) 3603 { 3604 rtx signmask = emit_store_flag (result, LT, op0, const0_rtx, 3605 mode, 0, -1); 3606 if (signmask) 3607 { 3608 signmask = force_reg (mode, signmask); 3609 masklow = ((HOST_WIDE_INT) 1 << logd) - 1; 3610 shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd); 3611 3612 /* Use the rtx_cost of a LSHIFTRT instruction to determine 3613 which instruction sequence to use. If logical right shifts 3614 are expensive the use 2 XORs, 2 SUBs and an AND, otherwise 3615 use a LSHIFTRT, 1 ADD, 1 SUB and an AND. */ 3616 3617 temp = gen_rtx_LSHIFTRT (mode, result, shift); 3618 if (lshr_optab->handlers[mode].insn_code == CODE_FOR_nothing 3619 || rtx_cost (temp, SET) > COSTS_N_INSNS (2)) 3620 { 3621 temp = expand_binop (mode, xor_optab, op0, signmask, 3622 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3623 temp = expand_binop (mode, sub_optab, temp, signmask, 3624 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3625 temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow), 3626 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3627 temp = expand_binop (mode, xor_optab, temp, signmask, 3628 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3629 temp = expand_binop (mode, sub_optab, temp, signmask, 3630 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3631 } 3632 else 3633 { 3634 signmask = expand_binop (mode, lshr_optab, signmask, shift, 3635 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3636 signmask = force_reg (mode, signmask); 3637 3638 temp = expand_binop (mode, add_optab, op0, signmask, 3639 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3640 temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow), 3641 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3642 temp = expand_binop (mode, sub_optab, temp, signmask, 3643 NULL_RTX, 1, OPTAB_LIB_WIDEN); 3644 } 3645 return temp; 3646 } 3647 } 3648 3649 /* Mask contains the mode's signbit and the significant bits of the 3650 modulus. By including the signbit in the operation, many targets 3651 can avoid an explicit compare operation in the following comparison 3652 against zero. */ 3653 3654 masklow = ((HOST_WIDE_INT) 1 << logd) - 1; 3655 if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT) 3656 { 3657 masklow |= (HOST_WIDE_INT) -1 << (GET_MODE_BITSIZE (mode) - 1); 3658 maskhigh = -1; 3659 } 3660 else 3661 maskhigh = (HOST_WIDE_INT) -1 3662 << (GET_MODE_BITSIZE (mode) - HOST_BITS_PER_WIDE_INT - 1); 3663 3664 temp = expand_binop (mode, and_optab, op0, 3665 immed_double_const (masklow, maskhigh, mode), 3666 result, 1, OPTAB_LIB_WIDEN); 3667 if (temp != result) 3668 emit_move_insn (result, temp); 3669 3670 label = gen_label_rtx (); 3671 do_cmp_and_jump (result, const0_rtx, GE, mode, label); 3672 3673 temp = expand_binop (mode, sub_optab, result, const1_rtx, result, 3674 0, OPTAB_LIB_WIDEN); 3675 masklow = (HOST_WIDE_INT) -1 << logd; 3676 maskhigh = -1; 3677 temp = expand_binop (mode, ior_optab, temp, 3678 immed_double_const (masklow, maskhigh, mode), 3679 result, 1, OPTAB_LIB_WIDEN); 3680 temp = expand_binop (mode, add_optab, temp, const1_rtx, result, 3681 0, OPTAB_LIB_WIDEN); 3682 if (temp != result) 3683 emit_move_insn (result, temp); 3684 emit_label (label); 3685 return result; 3686} 3687 3688/* Expand signed division of OP0 by a power of two D in mode MODE. 3689 This routine is only called for positive values of D. */ 3690 3691static rtx 3692expand_sdiv_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d) 3693{ 3694 rtx temp, label; 3695 tree shift; 3696 int logd; 3697 3698 logd = floor_log2 (d); 3699 shift = build_int_cst (NULL_TREE, logd); 3700 3701 if (d == 2 && BRANCH_COST >= 1) 3702 { 3703 temp = gen_reg_rtx (mode); 3704 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1); 3705 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX, 3706 0, OPTAB_LIB_WIDEN); 3707 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 3708 } 3709 3710#ifdef HAVE_conditional_move 3711 if (BRANCH_COST >= 2) 3712 { 3713 rtx temp2; 3714 3715 /* ??? emit_conditional_move forces a stack adjustment via 3716 compare_from_rtx so, if the sequence is discarded, it will 3717 be lost. Do it now instead. */ 3718 do_pending_stack_adjust (); 3719 3720 start_sequence (); 3721 temp2 = copy_to_mode_reg (mode, op0); 3722 temp = expand_binop (mode, add_optab, temp2, GEN_INT (d-1), 3723 NULL_RTX, 0, OPTAB_LIB_WIDEN); 3724 temp = force_reg (mode, temp); 3725 3726 /* Construct "temp2 = (temp2 < 0) ? temp : temp2". */ 3727 temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx, 3728 mode, temp, temp2, mode, 0); 3729 if (temp2) 3730 { 3731 rtx seq = get_insns (); 3732 end_sequence (); 3733 emit_insn (seq); 3734 return expand_shift (RSHIFT_EXPR, mode, temp2, shift, NULL_RTX, 0); 3735 } 3736 end_sequence (); 3737 } 3738#endif 3739 3740 if (BRANCH_COST >= 2) 3741 { 3742 int ushift = GET_MODE_BITSIZE (mode) - logd; 3743 3744 temp = gen_reg_rtx (mode); 3745 temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1); 3746 if (shift_cost[mode][ushift] > COSTS_N_INSNS (1)) 3747 temp = expand_binop (mode, and_optab, temp, GEN_INT (d - 1), 3748 NULL_RTX, 0, OPTAB_LIB_WIDEN); 3749 else 3750 temp = expand_shift (RSHIFT_EXPR, mode, temp, 3751 build_int_cst (NULL_TREE, ushift), 3752 NULL_RTX, 1); 3753 temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX, 3754 0, OPTAB_LIB_WIDEN); 3755 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 3756 } 3757 3758 label = gen_label_rtx (); 3759 temp = copy_to_mode_reg (mode, op0); 3760 do_cmp_and_jump (temp, const0_rtx, GE, mode, label); 3761 expand_inc (temp, GEN_INT (d - 1)); 3762 emit_label (label); 3763 return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 3764} 3765 3766/* Emit the code to divide OP0 by OP1, putting the result in TARGET 3767 if that is convenient, and returning where the result is. 3768 You may request either the quotient or the remainder as the result; 3769 specify REM_FLAG nonzero to get the remainder. 3770 3771 CODE is the expression code for which kind of division this is; 3772 it controls how rounding is done. MODE is the machine mode to use. 3773 UNSIGNEDP nonzero means do unsigned division. */ 3774 3775/* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI 3776 and then correct it by or'ing in missing high bits 3777 if result of ANDI is nonzero. 3778 For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result. 3779 This could optimize to a bfexts instruction. 3780 But C doesn't use these operations, so their optimizations are 3781 left for later. */ 3782/* ??? For modulo, we don't actually need the highpart of the first product, 3783 the low part will do nicely. And for small divisors, the second multiply 3784 can also be a low-part only multiply or even be completely left out. 3785 E.g. to calculate the remainder of a division by 3 with a 32 bit 3786 multiply, multiply with 0x55555556 and extract the upper two bits; 3787 the result is exact for inputs up to 0x1fffffff. 3788 The input range can be reduced by using cross-sum rules. 3789 For odd divisors >= 3, the following table gives right shift counts 3790 so that if a number is shifted by an integer multiple of the given 3791 amount, the remainder stays the same: 3792 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20, 3793 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0, 3794 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0, 3795 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33, 3796 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12 3797 3798 Cross-sum rules for even numbers can be derived by leaving as many bits 3799 to the right alone as the divisor has zeros to the right. 3800 E.g. if x is an unsigned 32 bit number: 3801 (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28 3802 */ 3803 3804rtx 3805expand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode, 3806 rtx op0, rtx op1, rtx target, int unsignedp) 3807{ 3808 enum machine_mode compute_mode; 3809 rtx tquotient; 3810 rtx quotient = 0, remainder = 0; 3811 rtx last; 3812 int size; 3813 rtx insn, set; 3814 optab optab1, optab2; 3815 int op1_is_constant, op1_is_pow2 = 0; 3816 int max_cost, extra_cost; 3817 static HOST_WIDE_INT last_div_const = 0; 3818 static HOST_WIDE_INT ext_op1; 3819 3820 op1_is_constant = GET_CODE (op1) == CONST_INT; 3821 if (op1_is_constant) 3822 { 3823 ext_op1 = INTVAL (op1); 3824 if (unsignedp) 3825 ext_op1 &= GET_MODE_MASK (mode); 3826 op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1) 3827 || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1)))); 3828 } 3829 3830 /* 3831 This is the structure of expand_divmod: 3832 3833 First comes code to fix up the operands so we can perform the operations 3834 correctly and efficiently. 3835 3836 Second comes a switch statement with code specific for each rounding mode. 3837 For some special operands this code emits all RTL for the desired 3838 operation, for other cases, it generates only a quotient and stores it in 3839 QUOTIENT. The case for trunc division/remainder might leave quotient = 0, 3840 to indicate that it has not done anything. 3841 3842 Last comes code that finishes the operation. If QUOTIENT is set and 3843 REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If 3844 QUOTIENT is not set, it is computed using trunc rounding. 3845 3846 We try to generate special code for division and remainder when OP1 is a 3847 constant. If |OP1| = 2**n we can use shifts and some other fast 3848 operations. For other values of OP1, we compute a carefully selected 3849 fixed-point approximation m = 1/OP1, and generate code that multiplies OP0 3850 by m. 3851 3852 In all cases but EXACT_DIV_EXPR, this multiplication requires the upper 3853 half of the product. Different strategies for generating the product are 3854 implemented in expand_mult_highpart. 3855 3856 If what we actually want is the remainder, we generate that by another 3857 by-constant multiplication and a subtraction. */ 3858 3859 /* We shouldn't be called with OP1 == const1_rtx, but some of the 3860 code below will malfunction if we are, so check here and handle 3861 the special case if so. */ 3862 if (op1 == const1_rtx) 3863 return rem_flag ? const0_rtx : op0; 3864 3865 /* When dividing by -1, we could get an overflow. 3866 negv_optab can handle overflows. */ 3867 if (! unsignedp && op1 == constm1_rtx) 3868 { 3869 if (rem_flag) 3870 return const0_rtx; 3871 return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT 3872 ? negv_optab : neg_optab, op0, target, 0); 3873 } 3874 3875 if (target 3876 /* Don't use the function value register as a target 3877 since we have to read it as well as write it, 3878 and function-inlining gets confused by this. */ 3879 && ((REG_P (target) && REG_FUNCTION_VALUE_P (target)) 3880 /* Don't clobber an operand while doing a multi-step calculation. */ 3881 || ((rem_flag || op1_is_constant) 3882 && (reg_mentioned_p (target, op0) 3883 || (MEM_P (op0) && MEM_P (target)))) 3884 || reg_mentioned_p (target, op1) 3885 || (MEM_P (op1) && MEM_P (target)))) 3886 target = 0; 3887 3888 /* Get the mode in which to perform this computation. Normally it will 3889 be MODE, but sometimes we can't do the desired operation in MODE. 3890 If so, pick a wider mode in which we can do the operation. Convert 3891 to that mode at the start to avoid repeated conversions. 3892 3893 First see what operations we need. These depend on the expression 3894 we are evaluating. (We assume that divxx3 insns exist under the 3895 same conditions that modxx3 insns and that these insns don't normally 3896 fail. If these assumptions are not correct, we may generate less 3897 efficient code in some cases.) 3898 3899 Then see if we find a mode in which we can open-code that operation 3900 (either a division, modulus, or shift). Finally, check for the smallest 3901 mode for which we can do the operation with a library call. */ 3902 3903 /* We might want to refine this now that we have division-by-constant 3904 optimization. Since expand_mult_highpart tries so many variants, it is 3905 not straightforward to generalize this. Maybe we should make an array 3906 of possible modes in init_expmed? Save this for GCC 2.7. */ 3907 3908 optab1 = ((op1_is_pow2 && op1 != const0_rtx) 3909 ? (unsignedp ? lshr_optab : ashr_optab) 3910 : (unsignedp ? udiv_optab : sdiv_optab)); 3911 optab2 = ((op1_is_pow2 && op1 != const0_rtx) 3912 ? optab1 3913 : (unsignedp ? udivmod_optab : sdivmod_optab)); 3914 3915 for (compute_mode = mode; compute_mode != VOIDmode; 3916 compute_mode = GET_MODE_WIDER_MODE (compute_mode)) 3917 if (optab1->handlers[compute_mode].insn_code != CODE_FOR_nothing 3918 || optab2->handlers[compute_mode].insn_code != CODE_FOR_nothing) 3919 break; 3920 3921 if (compute_mode == VOIDmode) 3922 for (compute_mode = mode; compute_mode != VOIDmode; 3923 compute_mode = GET_MODE_WIDER_MODE (compute_mode)) 3924 if (optab1->handlers[compute_mode].libfunc 3925 || optab2->handlers[compute_mode].libfunc) 3926 break; 3927 3928 /* If we still couldn't find a mode, use MODE, but expand_binop will 3929 probably die. */ 3930 if (compute_mode == VOIDmode) 3931 compute_mode = mode; 3932 3933 if (target && GET_MODE (target) == compute_mode) 3934 tquotient = target; 3935 else 3936 tquotient = gen_reg_rtx (compute_mode); 3937 3938 size = GET_MODE_BITSIZE (compute_mode); 3939#if 0 3940 /* It should be possible to restrict the precision to GET_MODE_BITSIZE 3941 (mode), and thereby get better code when OP1 is a constant. Do that 3942 later. It will require going over all usages of SIZE below. */ 3943 size = GET_MODE_BITSIZE (mode); 3944#endif 3945 3946 /* Only deduct something for a REM if the last divide done was 3947 for a different constant. Then set the constant of the last 3948 divide. */ 3949 max_cost = div_cost[compute_mode] 3950 - (rem_flag && ! (last_div_const != 0 && op1_is_constant 3951 && INTVAL (op1) == last_div_const) 3952 ? mul_cost[compute_mode] + add_cost[compute_mode] 3953 : 0); 3954 3955 last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0; 3956 3957 /* Now convert to the best mode to use. */ 3958 if (compute_mode != mode) 3959 { 3960 op0 = convert_modes (compute_mode, mode, op0, unsignedp); 3961 op1 = convert_modes (compute_mode, mode, op1, unsignedp); 3962 3963 /* convert_modes may have placed op1 into a register, so we 3964 must recompute the following. */ 3965 op1_is_constant = GET_CODE (op1) == CONST_INT; 3966 op1_is_pow2 = (op1_is_constant 3967 && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)) 3968 || (! unsignedp 3969 && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ; 3970 } 3971 3972 /* If one of the operands is a volatile MEM, copy it into a register. */ 3973 3974 if (MEM_P (op0) && MEM_VOLATILE_P (op0)) 3975 op0 = force_reg (compute_mode, op0); 3976 if (MEM_P (op1) && MEM_VOLATILE_P (op1)) 3977 op1 = force_reg (compute_mode, op1); 3978 3979 /* If we need the remainder or if OP1 is constant, we need to 3980 put OP0 in a register in case it has any queued subexpressions. */ 3981 if (rem_flag || op1_is_constant) 3982 op0 = force_reg (compute_mode, op0); 3983 3984 last = get_last_insn (); 3985 3986 /* Promote floor rounding to trunc rounding for unsigned operations. */ 3987 if (unsignedp) 3988 { 3989 if (code == FLOOR_DIV_EXPR) 3990 code = TRUNC_DIV_EXPR; 3991 if (code == FLOOR_MOD_EXPR) 3992 code = TRUNC_MOD_EXPR; 3993 if (code == EXACT_DIV_EXPR && op1_is_pow2) 3994 code = TRUNC_DIV_EXPR; 3995 } 3996 3997 if (op1 != const0_rtx) 3998 switch (code) 3999 { 4000 case TRUNC_MOD_EXPR: 4001 case TRUNC_DIV_EXPR: 4002 if (op1_is_constant) 4003 { 4004 if (unsignedp) 4005 { 4006 unsigned HOST_WIDE_INT mh; 4007 int pre_shift, post_shift; 4008 int dummy; 4009 rtx ml; 4010 unsigned HOST_WIDE_INT d = (INTVAL (op1) 4011 & GET_MODE_MASK (compute_mode)); 4012 4013 if (EXACT_POWER_OF_2_OR_ZERO_P (d)) 4014 { 4015 pre_shift = floor_log2 (d); 4016 if (rem_flag) 4017 { 4018 remainder 4019 = expand_binop (compute_mode, and_optab, op0, 4020 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1), 4021 remainder, 1, 4022 OPTAB_LIB_WIDEN); 4023 if (remainder) 4024 return gen_lowpart (mode, remainder); 4025 } 4026 quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4027 build_int_cst (NULL_TREE, 4028 pre_shift), 4029 tquotient, 1); 4030 } 4031 else if (size <= HOST_BITS_PER_WIDE_INT) 4032 { 4033 if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1))) 4034 { 4035 /* Most significant bit of divisor is set; emit an scc 4036 insn. */ 4037 quotient = emit_store_flag (tquotient, GEU, op0, op1, 4038 compute_mode, 1, 1); 4039 if (quotient == 0) 4040 goto fail1; 4041 } 4042 else 4043 { 4044 /* Find a suitable multiplier and right shift count 4045 instead of multiplying with D. */ 4046 4047 mh = choose_multiplier (d, size, size, 4048 &ml, &post_shift, &dummy); 4049 4050 /* If the suggested multiplier is more than SIZE bits, 4051 we can do better for even divisors, using an 4052 initial right shift. */ 4053 if (mh != 0 && (d & 1) == 0) 4054 { 4055 pre_shift = floor_log2 (d & -d); 4056 mh = choose_multiplier (d >> pre_shift, size, 4057 size - pre_shift, 4058 &ml, &post_shift, &dummy); 4059 gcc_assert (!mh); 4060 } 4061 else 4062 pre_shift = 0; 4063 4064 if (mh != 0) 4065 { 4066 rtx t1, t2, t3, t4; 4067 4068 if (post_shift - 1 >= BITS_PER_WORD) 4069 goto fail1; 4070 4071 extra_cost 4072 = (shift_cost[compute_mode][post_shift - 1] 4073 + shift_cost[compute_mode][1] 4074 + 2 * add_cost[compute_mode]); 4075 t1 = expand_mult_highpart (compute_mode, op0, ml, 4076 NULL_RTX, 1, 4077 max_cost - extra_cost); 4078 if (t1 == 0) 4079 goto fail1; 4080 t2 = force_operand (gen_rtx_MINUS (compute_mode, 4081 op0, t1), 4082 NULL_RTX); 4083 t3 = expand_shift 4084 (RSHIFT_EXPR, compute_mode, t2, 4085 build_int_cst (NULL_TREE, 1), 4086 NULL_RTX,1); 4087 t4 = force_operand (gen_rtx_PLUS (compute_mode, 4088 t1, t3), 4089 NULL_RTX); 4090 quotient = expand_shift 4091 (RSHIFT_EXPR, compute_mode, t4, 4092 build_int_cst (NULL_TREE, post_shift - 1), 4093 tquotient, 1); 4094 } 4095 else 4096 { 4097 rtx t1, t2; 4098 4099 if (pre_shift >= BITS_PER_WORD 4100 || post_shift >= BITS_PER_WORD) 4101 goto fail1; 4102 4103 t1 = expand_shift 4104 (RSHIFT_EXPR, compute_mode, op0, 4105 build_int_cst (NULL_TREE, pre_shift), 4106 NULL_RTX, 1); 4107 extra_cost 4108 = (shift_cost[compute_mode][pre_shift] 4109 + shift_cost[compute_mode][post_shift]); 4110 t2 = expand_mult_highpart (compute_mode, t1, ml, 4111 NULL_RTX, 1, 4112 max_cost - extra_cost); 4113 if (t2 == 0) 4114 goto fail1; 4115 quotient = expand_shift 4116 (RSHIFT_EXPR, compute_mode, t2, 4117 build_int_cst (NULL_TREE, post_shift), 4118 tquotient, 1); 4119 } 4120 } 4121 } 4122 else /* Too wide mode to use tricky code */ 4123 break; 4124 4125 insn = get_last_insn (); 4126 if (insn != last 4127 && (set = single_set (insn)) != 0 4128 && SET_DEST (set) == quotient) 4129 set_unique_reg_note (insn, 4130 REG_EQUAL, 4131 gen_rtx_UDIV (compute_mode, op0, op1)); 4132 } 4133 else /* TRUNC_DIV, signed */ 4134 { 4135 unsigned HOST_WIDE_INT ml; 4136 int lgup, post_shift; 4137 rtx mlr; 4138 HOST_WIDE_INT d = INTVAL (op1); 4139 unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d; 4140 4141 /* n rem d = n rem -d */ 4142 if (rem_flag && d < 0) 4143 { 4144 d = abs_d; 4145 op1 = gen_int_mode (abs_d, compute_mode); 4146 } 4147 4148 if (d == 1) 4149 quotient = op0; 4150 else if (d == -1) 4151 quotient = expand_unop (compute_mode, neg_optab, op0, 4152 tquotient, 0); 4153 else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1)) 4154 { 4155 /* This case is not handled correctly below. */ 4156 quotient = emit_store_flag (tquotient, EQ, op0, op1, 4157 compute_mode, 1, 1); 4158 if (quotient == 0) 4159 goto fail1; 4160 } 4161 else if (EXACT_POWER_OF_2_OR_ZERO_P (d) 4162 && (rem_flag ? smod_pow2_cheap[compute_mode] 4163 : sdiv_pow2_cheap[compute_mode]) 4164 /* We assume that cheap metric is true if the 4165 optab has an expander for this mode. */ 4166 && (((rem_flag ? smod_optab : sdiv_optab) 4167 ->handlers[compute_mode].insn_code 4168 != CODE_FOR_nothing) 4169 || (sdivmod_optab->handlers[compute_mode] 4170 .insn_code != CODE_FOR_nothing))) 4171 ; 4172 else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d)) 4173 { 4174 if (rem_flag) 4175 { 4176 remainder = expand_smod_pow2 (compute_mode, op0, d); 4177 if (remainder) 4178 return gen_lowpart (mode, remainder); 4179 } 4180 4181 if (sdiv_pow2_cheap[compute_mode] 4182 && ((sdiv_optab->handlers[compute_mode].insn_code 4183 != CODE_FOR_nothing) 4184 || (sdivmod_optab->handlers[compute_mode].insn_code 4185 != CODE_FOR_nothing))) 4186 quotient = expand_divmod (0, TRUNC_DIV_EXPR, 4187 compute_mode, op0, 4188 gen_int_mode (abs_d, 4189 compute_mode), 4190 NULL_RTX, 0); 4191 else 4192 quotient = expand_sdiv_pow2 (compute_mode, op0, abs_d); 4193 4194 /* We have computed OP0 / abs(OP1). If OP1 is negative, 4195 negate the quotient. */ 4196 if (d < 0) 4197 { 4198 insn = get_last_insn (); 4199 if (insn != last 4200 && (set = single_set (insn)) != 0 4201 && SET_DEST (set) == quotient 4202 && abs_d < ((unsigned HOST_WIDE_INT) 1 4203 << (HOST_BITS_PER_WIDE_INT - 1))) 4204 set_unique_reg_note (insn, 4205 REG_EQUAL, 4206 gen_rtx_DIV (compute_mode, 4207 op0, 4208 GEN_INT 4209 (trunc_int_for_mode 4210 (abs_d, 4211 compute_mode)))); 4212 4213 quotient = expand_unop (compute_mode, neg_optab, 4214 quotient, quotient, 0); 4215 } 4216 } 4217 else if (size <= HOST_BITS_PER_WIDE_INT) 4218 { 4219 choose_multiplier (abs_d, size, size - 1, 4220 &mlr, &post_shift, &lgup); 4221 ml = (unsigned HOST_WIDE_INT) INTVAL (mlr); 4222 if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1)) 4223 { 4224 rtx t1, t2, t3; 4225 4226 if (post_shift >= BITS_PER_WORD 4227 || size - 1 >= BITS_PER_WORD) 4228 goto fail1; 4229 4230 extra_cost = (shift_cost[compute_mode][post_shift] 4231 + shift_cost[compute_mode][size - 1] 4232 + add_cost[compute_mode]); 4233 t1 = expand_mult_highpart (compute_mode, op0, mlr, 4234 NULL_RTX, 0, 4235 max_cost - extra_cost); 4236 if (t1 == 0) 4237 goto fail1; 4238 t2 = expand_shift 4239 (RSHIFT_EXPR, compute_mode, t1, 4240 build_int_cst (NULL_TREE, post_shift), 4241 NULL_RTX, 0); 4242 t3 = expand_shift 4243 (RSHIFT_EXPR, compute_mode, op0, 4244 build_int_cst (NULL_TREE, size - 1), 4245 NULL_RTX, 0); 4246 if (d < 0) 4247 quotient 4248 = force_operand (gen_rtx_MINUS (compute_mode, 4249 t3, t2), 4250 tquotient); 4251 else 4252 quotient 4253 = force_operand (gen_rtx_MINUS (compute_mode, 4254 t2, t3), 4255 tquotient); 4256 } 4257 else 4258 { 4259 rtx t1, t2, t3, t4; 4260 4261 if (post_shift >= BITS_PER_WORD 4262 || size - 1 >= BITS_PER_WORD) 4263 goto fail1; 4264 4265 ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1); 4266 mlr = gen_int_mode (ml, compute_mode); 4267 extra_cost = (shift_cost[compute_mode][post_shift] 4268 + shift_cost[compute_mode][size - 1] 4269 + 2 * add_cost[compute_mode]); 4270 t1 = expand_mult_highpart (compute_mode, op0, mlr, 4271 NULL_RTX, 0, 4272 max_cost - extra_cost); 4273 if (t1 == 0) 4274 goto fail1; 4275 t2 = force_operand (gen_rtx_PLUS (compute_mode, 4276 t1, op0), 4277 NULL_RTX); 4278 t3 = expand_shift 4279 (RSHIFT_EXPR, compute_mode, t2, 4280 build_int_cst (NULL_TREE, post_shift), 4281 NULL_RTX, 0); 4282 t4 = expand_shift 4283 (RSHIFT_EXPR, compute_mode, op0, 4284 build_int_cst (NULL_TREE, size - 1), 4285 NULL_RTX, 0); 4286 if (d < 0) 4287 quotient 4288 = force_operand (gen_rtx_MINUS (compute_mode, 4289 t4, t3), 4290 tquotient); 4291 else 4292 quotient 4293 = force_operand (gen_rtx_MINUS (compute_mode, 4294 t3, t4), 4295 tquotient); 4296 } 4297 } 4298 else /* Too wide mode to use tricky code */ 4299 break; 4300 4301 insn = get_last_insn (); 4302 if (insn != last 4303 && (set = single_set (insn)) != 0 4304 && SET_DEST (set) == quotient) 4305 set_unique_reg_note (insn, 4306 REG_EQUAL, 4307 gen_rtx_DIV (compute_mode, op0, op1)); 4308 } 4309 break; 4310 } 4311 fail1: 4312 delete_insns_since (last); 4313 break; 4314 4315 case FLOOR_DIV_EXPR: 4316 case FLOOR_MOD_EXPR: 4317 /* We will come here only for signed operations. */ 4318 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size) 4319 { 4320 unsigned HOST_WIDE_INT mh; 4321 int pre_shift, lgup, post_shift; 4322 HOST_WIDE_INT d = INTVAL (op1); 4323 rtx ml; 4324 4325 if (d > 0) 4326 { 4327 /* We could just as easily deal with negative constants here, 4328 but it does not seem worth the trouble for GCC 2.6. */ 4329 if (EXACT_POWER_OF_2_OR_ZERO_P (d)) 4330 { 4331 pre_shift = floor_log2 (d); 4332 if (rem_flag) 4333 { 4334 remainder = expand_binop (compute_mode, and_optab, op0, 4335 GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1), 4336 remainder, 0, OPTAB_LIB_WIDEN); 4337 if (remainder) 4338 return gen_lowpart (mode, remainder); 4339 } 4340 quotient = expand_shift 4341 (RSHIFT_EXPR, compute_mode, op0, 4342 build_int_cst (NULL_TREE, pre_shift), 4343 tquotient, 0); 4344 } 4345 else 4346 { 4347 rtx t1, t2, t3, t4; 4348 4349 mh = choose_multiplier (d, size, size - 1, 4350 &ml, &post_shift, &lgup); 4351 gcc_assert (!mh); 4352 4353 if (post_shift < BITS_PER_WORD 4354 && size - 1 < BITS_PER_WORD) 4355 { 4356 t1 = expand_shift 4357 (RSHIFT_EXPR, compute_mode, op0, 4358 build_int_cst (NULL_TREE, size - 1), 4359 NULL_RTX, 0); 4360 t2 = expand_binop (compute_mode, xor_optab, op0, t1, 4361 NULL_RTX, 0, OPTAB_WIDEN); 4362 extra_cost = (shift_cost[compute_mode][post_shift] 4363 + shift_cost[compute_mode][size - 1] 4364 + 2 * add_cost[compute_mode]); 4365 t3 = expand_mult_highpart (compute_mode, t2, ml, 4366 NULL_RTX, 1, 4367 max_cost - extra_cost); 4368 if (t3 != 0) 4369 { 4370 t4 = expand_shift 4371 (RSHIFT_EXPR, compute_mode, t3, 4372 build_int_cst (NULL_TREE, post_shift), 4373 NULL_RTX, 1); 4374 quotient = expand_binop (compute_mode, xor_optab, 4375 t4, t1, tquotient, 0, 4376 OPTAB_WIDEN); 4377 } 4378 } 4379 } 4380 } 4381 else 4382 { 4383 rtx nsign, t1, t2, t3, t4; 4384 t1 = force_operand (gen_rtx_PLUS (compute_mode, 4385 op0, constm1_rtx), NULL_RTX); 4386 t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX, 4387 0, OPTAB_WIDEN); 4388 nsign = expand_shift 4389 (RSHIFT_EXPR, compute_mode, t2, 4390 build_int_cst (NULL_TREE, size - 1), 4391 NULL_RTX, 0); 4392 t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign), 4393 NULL_RTX); 4394 t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1, 4395 NULL_RTX, 0); 4396 if (t4) 4397 { 4398 rtx t5; 4399 t5 = expand_unop (compute_mode, one_cmpl_optab, nsign, 4400 NULL_RTX, 0); 4401 quotient = force_operand (gen_rtx_PLUS (compute_mode, 4402 t4, t5), 4403 tquotient); 4404 } 4405 } 4406 } 4407 4408 if (quotient != 0) 4409 break; 4410 delete_insns_since (last); 4411 4412 /* Try using an instruction that produces both the quotient and 4413 remainder, using truncation. We can easily compensate the quotient 4414 or remainder to get floor rounding, once we have the remainder. 4415 Notice that we compute also the final remainder value here, 4416 and return the result right away. */ 4417 if (target == 0 || GET_MODE (target) != compute_mode) 4418 target = gen_reg_rtx (compute_mode); 4419 4420 if (rem_flag) 4421 { 4422 remainder 4423 = REG_P (target) ? target : gen_reg_rtx (compute_mode); 4424 quotient = gen_reg_rtx (compute_mode); 4425 } 4426 else 4427 { 4428 quotient 4429 = REG_P (target) ? target : gen_reg_rtx (compute_mode); 4430 remainder = gen_reg_rtx (compute_mode); 4431 } 4432 4433 if (expand_twoval_binop (sdivmod_optab, op0, op1, 4434 quotient, remainder, 0)) 4435 { 4436 /* This could be computed with a branch-less sequence. 4437 Save that for later. */ 4438 rtx tem; 4439 rtx label = gen_label_rtx (); 4440 do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label); 4441 tem = expand_binop (compute_mode, xor_optab, op0, op1, 4442 NULL_RTX, 0, OPTAB_WIDEN); 4443 do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label); 4444 expand_dec (quotient, const1_rtx); 4445 expand_inc (remainder, op1); 4446 emit_label (label); 4447 return gen_lowpart (mode, rem_flag ? remainder : quotient); 4448 } 4449 4450 /* No luck with division elimination or divmod. Have to do it 4451 by conditionally adjusting op0 *and* the result. */ 4452 { 4453 rtx label1, label2, label3, label4, label5; 4454 rtx adjusted_op0; 4455 rtx tem; 4456 4457 quotient = gen_reg_rtx (compute_mode); 4458 adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 4459 label1 = gen_label_rtx (); 4460 label2 = gen_label_rtx (); 4461 label3 = gen_label_rtx (); 4462 label4 = gen_label_rtx (); 4463 label5 = gen_label_rtx (); 4464 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2); 4465 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1); 4466 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4467 quotient, 0, OPTAB_LIB_WIDEN); 4468 if (tem != quotient) 4469 emit_move_insn (quotient, tem); 4470 emit_jump_insn (gen_jump (label5)); 4471 emit_barrier (); 4472 emit_label (label1); 4473 expand_inc (adjusted_op0, const1_rtx); 4474 emit_jump_insn (gen_jump (label4)); 4475 emit_barrier (); 4476 emit_label (label2); 4477 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3); 4478 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4479 quotient, 0, OPTAB_LIB_WIDEN); 4480 if (tem != quotient) 4481 emit_move_insn (quotient, tem); 4482 emit_jump_insn (gen_jump (label5)); 4483 emit_barrier (); 4484 emit_label (label3); 4485 expand_dec (adjusted_op0, const1_rtx); 4486 emit_label (label4); 4487 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4488 quotient, 0, OPTAB_LIB_WIDEN); 4489 if (tem != quotient) 4490 emit_move_insn (quotient, tem); 4491 expand_dec (quotient, const1_rtx); 4492 emit_label (label5); 4493 } 4494 break; 4495 4496 case CEIL_DIV_EXPR: 4497 case CEIL_MOD_EXPR: 4498 if (unsignedp) 4499 { 4500 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))) 4501 { 4502 rtx t1, t2, t3; 4503 unsigned HOST_WIDE_INT d = INTVAL (op1); 4504 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4505 build_int_cst (NULL_TREE, floor_log2 (d)), 4506 tquotient, 1); 4507 t2 = expand_binop (compute_mode, and_optab, op0, 4508 GEN_INT (d - 1), 4509 NULL_RTX, 1, OPTAB_LIB_WIDEN); 4510 t3 = gen_reg_rtx (compute_mode); 4511 t3 = emit_store_flag (t3, NE, t2, const0_rtx, 4512 compute_mode, 1, 1); 4513 if (t3 == 0) 4514 { 4515 rtx lab; 4516 lab = gen_label_rtx (); 4517 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab); 4518 expand_inc (t1, const1_rtx); 4519 emit_label (lab); 4520 quotient = t1; 4521 } 4522 else 4523 quotient = force_operand (gen_rtx_PLUS (compute_mode, 4524 t1, t3), 4525 tquotient); 4526 break; 4527 } 4528 4529 /* Try using an instruction that produces both the quotient and 4530 remainder, using truncation. We can easily compensate the 4531 quotient or remainder to get ceiling rounding, once we have the 4532 remainder. Notice that we compute also the final remainder 4533 value here, and return the result right away. */ 4534 if (target == 0 || GET_MODE (target) != compute_mode) 4535 target = gen_reg_rtx (compute_mode); 4536 4537 if (rem_flag) 4538 { 4539 remainder = (REG_P (target) 4540 ? target : gen_reg_rtx (compute_mode)); 4541 quotient = gen_reg_rtx (compute_mode); 4542 } 4543 else 4544 { 4545 quotient = (REG_P (target) 4546 ? target : gen_reg_rtx (compute_mode)); 4547 remainder = gen_reg_rtx (compute_mode); 4548 } 4549 4550 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, 4551 remainder, 1)) 4552 { 4553 /* This could be computed with a branch-less sequence. 4554 Save that for later. */ 4555 rtx label = gen_label_rtx (); 4556 do_cmp_and_jump (remainder, const0_rtx, EQ, 4557 compute_mode, label); 4558 expand_inc (quotient, const1_rtx); 4559 expand_dec (remainder, op1); 4560 emit_label (label); 4561 return gen_lowpart (mode, rem_flag ? remainder : quotient); 4562 } 4563 4564 /* No luck with division elimination or divmod. Have to do it 4565 by conditionally adjusting op0 *and* the result. */ 4566 { 4567 rtx label1, label2; 4568 rtx adjusted_op0, tem; 4569 4570 quotient = gen_reg_rtx (compute_mode); 4571 adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 4572 label1 = gen_label_rtx (); 4573 label2 = gen_label_rtx (); 4574 do_cmp_and_jump (adjusted_op0, const0_rtx, NE, 4575 compute_mode, label1); 4576 emit_move_insn (quotient, const0_rtx); 4577 emit_jump_insn (gen_jump (label2)); 4578 emit_barrier (); 4579 emit_label (label1); 4580 expand_dec (adjusted_op0, const1_rtx); 4581 tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1, 4582 quotient, 1, OPTAB_LIB_WIDEN); 4583 if (tem != quotient) 4584 emit_move_insn (quotient, tem); 4585 expand_inc (quotient, const1_rtx); 4586 emit_label (label2); 4587 } 4588 } 4589 else /* signed */ 4590 { 4591 if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)) 4592 && INTVAL (op1) >= 0) 4593 { 4594 /* This is extremely similar to the code for the unsigned case 4595 above. For 2.7 we should merge these variants, but for 4596 2.6.1 I don't want to touch the code for unsigned since that 4597 get used in C. The signed case will only be used by other 4598 languages (Ada). */ 4599 4600 rtx t1, t2, t3; 4601 unsigned HOST_WIDE_INT d = INTVAL (op1); 4602 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4603 build_int_cst (NULL_TREE, floor_log2 (d)), 4604 tquotient, 0); 4605 t2 = expand_binop (compute_mode, and_optab, op0, 4606 GEN_INT (d - 1), 4607 NULL_RTX, 1, OPTAB_LIB_WIDEN); 4608 t3 = gen_reg_rtx (compute_mode); 4609 t3 = emit_store_flag (t3, NE, t2, const0_rtx, 4610 compute_mode, 1, 1); 4611 if (t3 == 0) 4612 { 4613 rtx lab; 4614 lab = gen_label_rtx (); 4615 do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab); 4616 expand_inc (t1, const1_rtx); 4617 emit_label (lab); 4618 quotient = t1; 4619 } 4620 else 4621 quotient = force_operand (gen_rtx_PLUS (compute_mode, 4622 t1, t3), 4623 tquotient); 4624 break; 4625 } 4626 4627 /* Try using an instruction that produces both the quotient and 4628 remainder, using truncation. We can easily compensate the 4629 quotient or remainder to get ceiling rounding, once we have the 4630 remainder. Notice that we compute also the final remainder 4631 value here, and return the result right away. */ 4632 if (target == 0 || GET_MODE (target) != compute_mode) 4633 target = gen_reg_rtx (compute_mode); 4634 if (rem_flag) 4635 { 4636 remainder= (REG_P (target) 4637 ? target : gen_reg_rtx (compute_mode)); 4638 quotient = gen_reg_rtx (compute_mode); 4639 } 4640 else 4641 { 4642 quotient = (REG_P (target) 4643 ? target : gen_reg_rtx (compute_mode)); 4644 remainder = gen_reg_rtx (compute_mode); 4645 } 4646 4647 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, 4648 remainder, 0)) 4649 { 4650 /* This could be computed with a branch-less sequence. 4651 Save that for later. */ 4652 rtx tem; 4653 rtx label = gen_label_rtx (); 4654 do_cmp_and_jump (remainder, const0_rtx, EQ, 4655 compute_mode, label); 4656 tem = expand_binop (compute_mode, xor_optab, op0, op1, 4657 NULL_RTX, 0, OPTAB_WIDEN); 4658 do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label); 4659 expand_inc (quotient, const1_rtx); 4660 expand_dec (remainder, op1); 4661 emit_label (label); 4662 return gen_lowpart (mode, rem_flag ? remainder : quotient); 4663 } 4664 4665 /* No luck with division elimination or divmod. Have to do it 4666 by conditionally adjusting op0 *and* the result. */ 4667 { 4668 rtx label1, label2, label3, label4, label5; 4669 rtx adjusted_op0; 4670 rtx tem; 4671 4672 quotient = gen_reg_rtx (compute_mode); 4673 adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 4674 label1 = gen_label_rtx (); 4675 label2 = gen_label_rtx (); 4676 label3 = gen_label_rtx (); 4677 label4 = gen_label_rtx (); 4678 label5 = gen_label_rtx (); 4679 do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2); 4680 do_cmp_and_jump (adjusted_op0, const0_rtx, GT, 4681 compute_mode, label1); 4682 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4683 quotient, 0, OPTAB_LIB_WIDEN); 4684 if (tem != quotient) 4685 emit_move_insn (quotient, tem); 4686 emit_jump_insn (gen_jump (label5)); 4687 emit_barrier (); 4688 emit_label (label1); 4689 expand_dec (adjusted_op0, const1_rtx); 4690 emit_jump_insn (gen_jump (label4)); 4691 emit_barrier (); 4692 emit_label (label2); 4693 do_cmp_and_jump (adjusted_op0, const0_rtx, LT, 4694 compute_mode, label3); 4695 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4696 quotient, 0, OPTAB_LIB_WIDEN); 4697 if (tem != quotient) 4698 emit_move_insn (quotient, tem); 4699 emit_jump_insn (gen_jump (label5)); 4700 emit_barrier (); 4701 emit_label (label3); 4702 expand_inc (adjusted_op0, const1_rtx); 4703 emit_label (label4); 4704 tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 4705 quotient, 0, OPTAB_LIB_WIDEN); 4706 if (tem != quotient) 4707 emit_move_insn (quotient, tem); 4708 expand_inc (quotient, const1_rtx); 4709 emit_label (label5); 4710 } 4711 } 4712 break; 4713 4714 case EXACT_DIV_EXPR: 4715 if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size) 4716 { 4717 HOST_WIDE_INT d = INTVAL (op1); 4718 unsigned HOST_WIDE_INT ml; 4719 int pre_shift; 4720 rtx t1; 4721 4722 pre_shift = floor_log2 (d & -d); 4723 ml = invert_mod2n (d >> pre_shift, size); 4724 t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4725 build_int_cst (NULL_TREE, pre_shift), 4726 NULL_RTX, unsignedp); 4727 quotient = expand_mult (compute_mode, t1, 4728 gen_int_mode (ml, compute_mode), 4729 NULL_RTX, 1); 4730 4731 insn = get_last_insn (); 4732 set_unique_reg_note (insn, 4733 REG_EQUAL, 4734 gen_rtx_fmt_ee (unsignedp ? UDIV : DIV, 4735 compute_mode, 4736 op0, op1)); 4737 } 4738 break; 4739 4740 case ROUND_DIV_EXPR: 4741 case ROUND_MOD_EXPR: 4742 if (unsignedp) 4743 { 4744 rtx tem; 4745 rtx label; 4746 label = gen_label_rtx (); 4747 quotient = gen_reg_rtx (compute_mode); 4748 remainder = gen_reg_rtx (compute_mode); 4749 if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0) 4750 { 4751 rtx tem; 4752 quotient = expand_binop (compute_mode, udiv_optab, op0, op1, 4753 quotient, 1, OPTAB_LIB_WIDEN); 4754 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1); 4755 remainder = expand_binop (compute_mode, sub_optab, op0, tem, 4756 remainder, 1, OPTAB_LIB_WIDEN); 4757 } 4758 tem = plus_constant (op1, -1); 4759 tem = expand_shift (RSHIFT_EXPR, compute_mode, tem, 4760 build_int_cst (NULL_TREE, 1), 4761 NULL_RTX, 1); 4762 do_cmp_and_jump (remainder, tem, LEU, compute_mode, label); 4763 expand_inc (quotient, const1_rtx); 4764 expand_dec (remainder, op1); 4765 emit_label (label); 4766 } 4767 else 4768 { 4769 rtx abs_rem, abs_op1, tem, mask; 4770 rtx label; 4771 label = gen_label_rtx (); 4772 quotient = gen_reg_rtx (compute_mode); 4773 remainder = gen_reg_rtx (compute_mode); 4774 if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0) 4775 { 4776 rtx tem; 4777 quotient = expand_binop (compute_mode, sdiv_optab, op0, op1, 4778 quotient, 0, OPTAB_LIB_WIDEN); 4779 tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0); 4780 remainder = expand_binop (compute_mode, sub_optab, op0, tem, 4781 remainder, 0, OPTAB_LIB_WIDEN); 4782 } 4783 abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0); 4784 abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0); 4785 tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem, 4786 build_int_cst (NULL_TREE, 1), 4787 NULL_RTX, 1); 4788 do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label); 4789 tem = expand_binop (compute_mode, xor_optab, op0, op1, 4790 NULL_RTX, 0, OPTAB_WIDEN); 4791 mask = expand_shift (RSHIFT_EXPR, compute_mode, tem, 4792 build_int_cst (NULL_TREE, size - 1), 4793 NULL_RTX, 0); 4794 tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx, 4795 NULL_RTX, 0, OPTAB_WIDEN); 4796 tem = expand_binop (compute_mode, sub_optab, tem, mask, 4797 NULL_RTX, 0, OPTAB_WIDEN); 4798 expand_inc (quotient, tem); 4799 tem = expand_binop (compute_mode, xor_optab, mask, op1, 4800 NULL_RTX, 0, OPTAB_WIDEN); 4801 tem = expand_binop (compute_mode, sub_optab, tem, mask, 4802 NULL_RTX, 0, OPTAB_WIDEN); 4803 expand_dec (remainder, tem); 4804 emit_label (label); 4805 } 4806 return gen_lowpart (mode, rem_flag ? remainder : quotient); 4807 4808 default: 4809 gcc_unreachable (); 4810 } 4811 4812 if (quotient == 0) 4813 { 4814 if (target && GET_MODE (target) != compute_mode) 4815 target = 0; 4816 4817 if (rem_flag) 4818 { 4819 /* Try to produce the remainder without producing the quotient. 4820 If we seem to have a divmod pattern that does not require widening, 4821 don't try widening here. We should really have a WIDEN argument 4822 to expand_twoval_binop, since what we'd really like to do here is 4823 1) try a mod insn in compute_mode 4824 2) try a divmod insn in compute_mode 4825 3) try a div insn in compute_mode and multiply-subtract to get 4826 remainder 4827 4) try the same things with widening allowed. */ 4828 remainder 4829 = sign_expand_binop (compute_mode, umod_optab, smod_optab, 4830 op0, op1, target, 4831 unsignedp, 4832 ((optab2->handlers[compute_mode].insn_code 4833 != CODE_FOR_nothing) 4834 ? OPTAB_DIRECT : OPTAB_WIDEN)); 4835 if (remainder == 0) 4836 { 4837 /* No luck there. Can we do remainder and divide at once 4838 without a library call? */ 4839 remainder = gen_reg_rtx (compute_mode); 4840 if (! expand_twoval_binop ((unsignedp 4841 ? udivmod_optab 4842 : sdivmod_optab), 4843 op0, op1, 4844 NULL_RTX, remainder, unsignedp)) 4845 remainder = 0; 4846 } 4847 4848 if (remainder) 4849 return gen_lowpart (mode, remainder); 4850 } 4851 4852 /* Produce the quotient. Try a quotient insn, but not a library call. 4853 If we have a divmod in this mode, use it in preference to widening 4854 the div (for this test we assume it will not fail). Note that optab2 4855 is set to the one of the two optabs that the call below will use. */ 4856 quotient 4857 = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab, 4858 op0, op1, rem_flag ? NULL_RTX : target, 4859 unsignedp, 4860 ((optab2->handlers[compute_mode].insn_code 4861 != CODE_FOR_nothing) 4862 ? OPTAB_DIRECT : OPTAB_WIDEN)); 4863 4864 if (quotient == 0) 4865 { 4866 /* No luck there. Try a quotient-and-remainder insn, 4867 keeping the quotient alone. */ 4868 quotient = gen_reg_rtx (compute_mode); 4869 if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab, 4870 op0, op1, 4871 quotient, NULL_RTX, unsignedp)) 4872 { 4873 quotient = 0; 4874 if (! rem_flag) 4875 /* Still no luck. If we are not computing the remainder, 4876 use a library call for the quotient. */ 4877 quotient = sign_expand_binop (compute_mode, 4878 udiv_optab, sdiv_optab, 4879 op0, op1, target, 4880 unsignedp, OPTAB_LIB_WIDEN); 4881 } 4882 } 4883 } 4884 4885 if (rem_flag) 4886 { 4887 if (target && GET_MODE (target) != compute_mode) 4888 target = 0; 4889 4890 if (quotient == 0) 4891 { 4892 /* No divide instruction either. Use library for remainder. */ 4893 remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab, 4894 op0, op1, target, 4895 unsignedp, OPTAB_LIB_WIDEN); 4896 /* No remainder function. Try a quotient-and-remainder 4897 function, keeping the remainder. */ 4898 if (!remainder) 4899 { 4900 remainder = gen_reg_rtx (compute_mode); 4901 if (!expand_twoval_binop_libfunc 4902 (unsignedp ? udivmod_optab : sdivmod_optab, 4903 op0, op1, 4904 NULL_RTX, remainder, 4905 unsignedp ? UMOD : MOD)) 4906 remainder = NULL_RTX; 4907 } 4908 } 4909 else 4910 { 4911 /* We divided. Now finish doing X - Y * (X / Y). */ 4912 remainder = expand_mult (compute_mode, quotient, op1, 4913 NULL_RTX, unsignedp); 4914 remainder = expand_binop (compute_mode, sub_optab, op0, 4915 remainder, target, unsignedp, 4916 OPTAB_LIB_WIDEN); 4917 } 4918 } 4919 4920 return gen_lowpart (mode, rem_flag ? remainder : quotient); 4921} 4922 4923/* Return a tree node with data type TYPE, describing the value of X. 4924 Usually this is an VAR_DECL, if there is no obvious better choice. 4925 X may be an expression, however we only support those expressions 4926 generated by loop.c. */ 4927 4928tree 4929make_tree (tree type, rtx x) 4930{ 4931 tree t; 4932 4933 switch (GET_CODE (x)) 4934 { 4935 case CONST_INT: 4936 { 4937 HOST_WIDE_INT hi = 0; 4938 4939 if (INTVAL (x) < 0 4940 && !(TYPE_UNSIGNED (type) 4941 && (GET_MODE_BITSIZE (TYPE_MODE (type)) 4942 < HOST_BITS_PER_WIDE_INT))) 4943 hi = -1; 4944 4945 t = build_int_cst_wide (type, INTVAL (x), hi); 4946 4947 return t; 4948 } 4949 4950 case CONST_DOUBLE: 4951 if (GET_MODE (x) == VOIDmode) 4952 t = build_int_cst_wide (type, 4953 CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x)); 4954 else 4955 { 4956 REAL_VALUE_TYPE d; 4957 4958 REAL_VALUE_FROM_CONST_DOUBLE (d, x); 4959 t = build_real (type, d); 4960 } 4961 4962 return t; 4963 4964 case CONST_VECTOR: 4965 { 4966 int i, units; 4967 rtx elt; 4968 tree t = NULL_TREE; 4969 4970 units = CONST_VECTOR_NUNITS (x); 4971 4972 /* Build a tree with vector elements. */ 4973 for (i = units - 1; i >= 0; --i) 4974 { 4975 elt = CONST_VECTOR_ELT (x, i); 4976 t = tree_cons (NULL_TREE, make_tree (type, elt), t); 4977 } 4978 4979 return build_vector (type, t); 4980 } 4981 4982 case PLUS: 4983 return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)), 4984 make_tree (type, XEXP (x, 1))); 4985 4986 case MINUS: 4987 return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)), 4988 make_tree (type, XEXP (x, 1))); 4989 4990 case NEG: 4991 return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))); 4992 4993 case MULT: 4994 return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)), 4995 make_tree (type, XEXP (x, 1))); 4996 4997 case ASHIFT: 4998 return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)), 4999 make_tree (type, XEXP (x, 1))); 5000 5001 case LSHIFTRT: 5002 t = lang_hooks.types.unsigned_type (type); 5003 return fold_convert (type, build2 (RSHIFT_EXPR, t, 5004 make_tree (t, XEXP (x, 0)), 5005 make_tree (type, XEXP (x, 1)))); 5006 5007 case ASHIFTRT: 5008 t = lang_hooks.types.signed_type (type); 5009 return fold_convert (type, build2 (RSHIFT_EXPR, t, 5010 make_tree (t, XEXP (x, 0)), 5011 make_tree (type, XEXP (x, 1)))); 5012 5013 case DIV: 5014 if (TREE_CODE (type) != REAL_TYPE) 5015 t = lang_hooks.types.signed_type (type); 5016 else 5017 t = type; 5018 5019 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t, 5020 make_tree (t, XEXP (x, 0)), 5021 make_tree (t, XEXP (x, 1)))); 5022 case UDIV: 5023 t = lang_hooks.types.unsigned_type (type); 5024 return fold_convert (type, build2 (TRUNC_DIV_EXPR, t, 5025 make_tree (t, XEXP (x, 0)), 5026 make_tree (t, XEXP (x, 1)))); 5027 5028 case SIGN_EXTEND: 5029 case ZERO_EXTEND: 5030 t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)), 5031 GET_CODE (x) == ZERO_EXTEND); 5032 return fold_convert (type, make_tree (t, XEXP (x, 0))); 5033 5034 default: 5035 t = build_decl (VAR_DECL, NULL_TREE, type); 5036 5037 /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being 5038 ptr_mode. So convert. */ 5039 if (POINTER_TYPE_P (type)) 5040 x = convert_memory_address (TYPE_MODE (type), x); 5041 5042 /* Note that we do *not* use SET_DECL_RTL here, because we do not 5043 want set_decl_rtl to go adjusting REG_ATTRS for this temporary. */ 5044 t->decl_with_rtl.rtl = x; 5045 5046 return t; 5047 } 5048} 5049 5050/* Check whether the multiplication X * MULT + ADD overflows. 5051 X, MULT and ADD must be CONST_*. 5052 MODE is the machine mode for the computation. 5053 X and MULT must have mode MODE. ADD may have a different mode. 5054 So can X (defaults to same as MODE). 5055 UNSIGNEDP is nonzero to do unsigned multiplication. */ 5056 5057bool 5058const_mult_add_overflow_p (rtx x, rtx mult, rtx add, 5059 enum machine_mode mode, int unsignedp) 5060{ 5061 tree type, mult_type, add_type, result; 5062 5063 type = lang_hooks.types.type_for_mode (mode, unsignedp); 5064 5065 /* In order to get a proper overflow indication from an unsigned 5066 type, we have to pretend that it's a sizetype. */ 5067 mult_type = type; 5068 if (unsignedp) 5069 { 5070 /* FIXME:It would be nice if we could step directly from this 5071 type to its sizetype equivalent. */ 5072 mult_type = build_distinct_type_copy (type); 5073 TYPE_IS_SIZETYPE (mult_type) = 1; 5074 } 5075 5076 add_type = (GET_MODE (add) == VOIDmode ? mult_type 5077 : lang_hooks.types.type_for_mode (GET_MODE (add), unsignedp)); 5078 5079 result = fold_build2 (PLUS_EXPR, mult_type, 5080 fold_build2 (MULT_EXPR, mult_type, 5081 make_tree (mult_type, x), 5082 make_tree (mult_type, mult)), 5083 make_tree (add_type, add)); 5084 5085 return TREE_CONSTANT_OVERFLOW (result); 5086} 5087 5088/* Return an rtx representing the value of X * MULT + ADD. 5089 TARGET is a suggestion for where to store the result (an rtx). 5090 MODE is the machine mode for the computation. 5091 X and MULT must have mode MODE. ADD may have a different mode. 5092 So can X (defaults to same as MODE). 5093 UNSIGNEDP is nonzero to do unsigned multiplication. 5094 This may emit insns. */ 5095 5096rtx 5097expand_mult_add (rtx x, rtx target, rtx mult, rtx add, enum machine_mode mode, 5098 int unsignedp) 5099{ 5100 tree type = lang_hooks.types.type_for_mode (mode, unsignedp); 5101 tree add_type = (GET_MODE (add) == VOIDmode 5102 ? type: lang_hooks.types.type_for_mode (GET_MODE (add), 5103 unsignedp)); 5104 tree result = fold_build2 (PLUS_EXPR, type, 5105 fold_build2 (MULT_EXPR, type, 5106 make_tree (type, x), 5107 make_tree (type, mult)), 5108 make_tree (add_type, add)); 5109 5110 return expand_expr (result, target, VOIDmode, 0); 5111} 5112 5113/* Compute the logical-and of OP0 and OP1, storing it in TARGET 5114 and returning TARGET. 5115 5116 If TARGET is 0, a pseudo-register or constant is returned. */ 5117 5118rtx 5119expand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target) 5120{ 5121 rtx tem = 0; 5122 5123 if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode) 5124 tem = simplify_binary_operation (AND, mode, op0, op1); 5125 if (tem == 0) 5126 tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN); 5127 5128 if (target == 0) 5129 target = tem; 5130 else if (tem != target) 5131 emit_move_insn (target, tem); 5132 return target; 5133} 5134 5135/* Emit a store-flags instruction for comparison CODE on OP0 and OP1 5136 and storing in TARGET. Normally return TARGET. 5137 Return 0 if that cannot be done. 5138 5139 MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If 5140 it is VOIDmode, they cannot both be CONST_INT. 5141 5142 UNSIGNEDP is for the case where we have to widen the operands 5143 to perform the operation. It says to use zero-extension. 5144 5145 NORMALIZEP is 1 if we should convert the result to be either zero 5146 or one. Normalize is -1 if we should convert the result to be 5147 either zero or -1. If NORMALIZEP is zero, the result will be left 5148 "raw" out of the scc insn. */ 5149 5150rtx 5151emit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1, 5152 enum machine_mode mode, int unsignedp, int normalizep) 5153{ 5154 rtx subtarget; 5155 enum insn_code icode; 5156 enum machine_mode compare_mode; 5157 enum machine_mode target_mode = GET_MODE (target); 5158 rtx tem; 5159 rtx last = get_last_insn (); 5160 rtx pattern, comparison; 5161 5162 if (unsignedp) 5163 code = unsigned_condition (code); 5164 5165 /* If one operand is constant, make it the second one. Only do this 5166 if the other operand is not constant as well. */ 5167 5168 if (swap_commutative_operands_p (op0, op1)) 5169 { 5170 tem = op0; 5171 op0 = op1; 5172 op1 = tem; 5173 code = swap_condition (code); 5174 } 5175 5176 if (mode == VOIDmode) 5177 mode = GET_MODE (op0); 5178 5179 /* For some comparisons with 1 and -1, we can convert this to 5180 comparisons with zero. This will often produce more opportunities for 5181 store-flag insns. */ 5182 5183 switch (code) 5184 { 5185 case LT: 5186 if (op1 == const1_rtx) 5187 op1 = const0_rtx, code = LE; 5188 break; 5189 case LE: 5190 if (op1 == constm1_rtx) 5191 op1 = const0_rtx, code = LT; 5192 break; 5193 case GE: 5194 if (op1 == const1_rtx) 5195 op1 = const0_rtx, code = GT; 5196 break; 5197 case GT: 5198 if (op1 == constm1_rtx) 5199 op1 = const0_rtx, code = GE; 5200 break; 5201 case GEU: 5202 if (op1 == const1_rtx) 5203 op1 = const0_rtx, code = NE; 5204 break; 5205 case LTU: 5206 if (op1 == const1_rtx) 5207 op1 = const0_rtx, code = EQ; 5208 break; 5209 default: 5210 break; 5211 } 5212 5213 /* If we are comparing a double-word integer with zero or -1, we can 5214 convert the comparison into one involving a single word. */ 5215 if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2 5216 && GET_MODE_CLASS (mode) == MODE_INT 5217 && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0))) 5218 { 5219 if ((code == EQ || code == NE) 5220 && (op1 == const0_rtx || op1 == constm1_rtx)) 5221 { 5222 rtx op00, op01, op0both; 5223 5224 /* Do a logical OR or AND of the two words and compare the result. */ 5225 op00 = simplify_gen_subreg (word_mode, op0, mode, 0); 5226 op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD); 5227 op0both = expand_binop (word_mode, 5228 op1 == const0_rtx ? ior_optab : and_optab, 5229 op00, op01, NULL_RTX, unsignedp, OPTAB_DIRECT); 5230 5231 if (op0both != 0) 5232 return emit_store_flag (target, code, op0both, op1, word_mode, 5233 unsignedp, normalizep); 5234 } 5235 else if ((code == LT || code == GE) && op1 == const0_rtx) 5236 { 5237 rtx op0h; 5238 5239 /* If testing the sign bit, can just test on high word. */ 5240 op0h = simplify_gen_subreg (word_mode, op0, mode, 5241 subreg_highpart_offset (word_mode, mode)); 5242 return emit_store_flag (target, code, op0h, op1, word_mode, 5243 unsignedp, normalizep); 5244 } 5245 } 5246 5247 /* From now on, we won't change CODE, so set ICODE now. */ 5248 icode = setcc_gen_code[(int) code]; 5249 5250 /* If this is A < 0 or A >= 0, we can do this by taking the ones 5251 complement of A (for GE) and shifting the sign bit to the low bit. */ 5252 if (op1 == const0_rtx && (code == LT || code == GE) 5253 && GET_MODE_CLASS (mode) == MODE_INT 5254 && (normalizep || STORE_FLAG_VALUE == 1 5255 || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT 5256 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode)) 5257 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1))))) 5258 { 5259 subtarget = target; 5260 5261 /* If the result is to be wider than OP0, it is best to convert it 5262 first. If it is to be narrower, it is *incorrect* to convert it 5263 first. */ 5264 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode)) 5265 { 5266 op0 = convert_modes (target_mode, mode, op0, 0); 5267 mode = target_mode; 5268 } 5269 5270 if (target_mode != mode) 5271 subtarget = 0; 5272 5273 if (code == GE) 5274 op0 = expand_unop (mode, one_cmpl_optab, op0, 5275 ((STORE_FLAG_VALUE == 1 || normalizep) 5276 ? 0 : subtarget), 0); 5277 5278 if (STORE_FLAG_VALUE == 1 || normalizep) 5279 /* If we are supposed to produce a 0/1 value, we want to do 5280 a logical shift from the sign bit to the low-order bit; for 5281 a -1/0 value, we do an arithmetic shift. */ 5282 op0 = expand_shift (RSHIFT_EXPR, mode, op0, 5283 size_int (GET_MODE_BITSIZE (mode) - 1), 5284 subtarget, normalizep != -1); 5285 5286 if (mode != target_mode) 5287 op0 = convert_modes (target_mode, mode, op0, 0); 5288 5289 return op0; 5290 } 5291 5292 if (icode != CODE_FOR_nothing) 5293 { 5294 insn_operand_predicate_fn pred; 5295 5296 /* We think we may be able to do this with a scc insn. Emit the 5297 comparison and then the scc insn. */ 5298 5299 do_pending_stack_adjust (); 5300 last = get_last_insn (); 5301 5302 comparison 5303 = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX); 5304 if (CONSTANT_P (comparison)) 5305 { 5306 switch (GET_CODE (comparison)) 5307 { 5308 case CONST_INT: 5309 if (comparison == const0_rtx) 5310 return const0_rtx; 5311 break; 5312 5313#ifdef FLOAT_STORE_FLAG_VALUE 5314 case CONST_DOUBLE: 5315 if (comparison == CONST0_RTX (GET_MODE (comparison))) 5316 return const0_rtx; 5317 break; 5318#endif 5319 default: 5320 gcc_unreachable (); 5321 } 5322 5323 if (normalizep == 1) 5324 return const1_rtx; 5325 if (normalizep == -1) 5326 return constm1_rtx; 5327 return const_true_rtx; 5328 } 5329 5330 /* The code of COMPARISON may not match CODE if compare_from_rtx 5331 decided to swap its operands and reverse the original code. 5332 5333 We know that compare_from_rtx returns either a CONST_INT or 5334 a new comparison code, so it is safe to just extract the 5335 code from COMPARISON. */ 5336 code = GET_CODE (comparison); 5337 5338 /* Get a reference to the target in the proper mode for this insn. */ 5339 compare_mode = insn_data[(int) icode].operand[0].mode; 5340 subtarget = target; 5341 pred = insn_data[(int) icode].operand[0].predicate; 5342 if (optimize || ! (*pred) (subtarget, compare_mode)) 5343 subtarget = gen_reg_rtx (compare_mode); 5344 5345 pattern = GEN_FCN (icode) (subtarget); 5346 if (pattern) 5347 { 5348 emit_insn (pattern); 5349 5350 /* If we are converting to a wider mode, first convert to 5351 TARGET_MODE, then normalize. This produces better combining 5352 opportunities on machines that have a SIGN_EXTRACT when we are 5353 testing a single bit. This mostly benefits the 68k. 5354 5355 If STORE_FLAG_VALUE does not have the sign bit set when 5356 interpreted in COMPARE_MODE, we can do this conversion as 5357 unsigned, which is usually more efficient. */ 5358 if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode)) 5359 { 5360 convert_move (target, subtarget, 5361 (GET_MODE_BITSIZE (compare_mode) 5362 <= HOST_BITS_PER_WIDE_INT) 5363 && 0 == (STORE_FLAG_VALUE 5364 & ((HOST_WIDE_INT) 1 5365 << (GET_MODE_BITSIZE (compare_mode) -1)))); 5366 op0 = target; 5367 compare_mode = target_mode; 5368 } 5369 else 5370 op0 = subtarget; 5371 5372 /* If we want to keep subexpressions around, don't reuse our 5373 last target. */ 5374 5375 if (optimize) 5376 subtarget = 0; 5377 5378 /* Now normalize to the proper value in COMPARE_MODE. Sometimes 5379 we don't have to do anything. */ 5380 if (normalizep == 0 || normalizep == STORE_FLAG_VALUE) 5381 ; 5382 /* STORE_FLAG_VALUE might be the most negative number, so write 5383 the comparison this way to avoid a compiler-time warning. */ 5384 else if (- normalizep == STORE_FLAG_VALUE) 5385 op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0); 5386 5387 /* We don't want to use STORE_FLAG_VALUE < 0 below since this 5388 makes it hard to use a value of just the sign bit due to 5389 ANSI integer constant typing rules. */ 5390 else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT 5391 && (STORE_FLAG_VALUE 5392 & ((HOST_WIDE_INT) 1 5393 << (GET_MODE_BITSIZE (compare_mode) - 1)))) 5394 op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0, 5395 size_int (GET_MODE_BITSIZE (compare_mode) - 1), 5396 subtarget, normalizep == 1); 5397 else 5398 { 5399 gcc_assert (STORE_FLAG_VALUE & 1); 5400 5401 op0 = expand_and (compare_mode, op0, const1_rtx, subtarget); 5402 if (normalizep == -1) 5403 op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0); 5404 } 5405 5406 /* If we were converting to a smaller mode, do the 5407 conversion now. */ 5408 if (target_mode != compare_mode) 5409 { 5410 convert_move (target, op0, 0); 5411 return target; 5412 } 5413 else 5414 return op0; 5415 } 5416 } 5417 5418 delete_insns_since (last); 5419 5420 /* If optimizing, use different pseudo registers for each insn, instead 5421 of reusing the same pseudo. This leads to better CSE, but slows 5422 down the compiler, since there are more pseudos */ 5423 subtarget = (!optimize 5424 && (target_mode == mode)) ? target : NULL_RTX; 5425 5426 /* If we reached here, we can't do this with a scc insn. However, there 5427 are some comparisons that can be done directly. For example, if 5428 this is an equality comparison of integers, we can try to exclusive-or 5429 (or subtract) the two operands and use a recursive call to try the 5430 comparison with zero. Don't do any of these cases if branches are 5431 very cheap. */ 5432 5433 if (BRANCH_COST > 0 5434 && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE) 5435 && op1 != const0_rtx) 5436 { 5437 tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1, 5438 OPTAB_WIDEN); 5439 5440 if (tem == 0) 5441 tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1, 5442 OPTAB_WIDEN); 5443 if (tem != 0) 5444 tem = emit_store_flag (target, code, tem, const0_rtx, 5445 mode, unsignedp, normalizep); 5446 if (tem == 0) 5447 delete_insns_since (last); 5448 return tem; 5449 } 5450 5451 /* Some other cases we can do are EQ, NE, LE, and GT comparisons with 5452 the constant zero. Reject all other comparisons at this point. Only 5453 do LE and GT if branches are expensive since they are expensive on 5454 2-operand machines. */ 5455 5456 if (BRANCH_COST == 0 5457 || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx 5458 || (code != EQ && code != NE 5459 && (BRANCH_COST <= 1 || (code != LE && code != GT)))) 5460 return 0; 5461 5462 /* See what we need to return. We can only return a 1, -1, or the 5463 sign bit. */ 5464 5465 if (normalizep == 0) 5466 { 5467 if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1) 5468 normalizep = STORE_FLAG_VALUE; 5469 5470 else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT 5471 && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode)) 5472 == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1))) 5473 ; 5474 else 5475 return 0; 5476 } 5477 5478 /* Try to put the result of the comparison in the sign bit. Assume we can't 5479 do the necessary operation below. */ 5480 5481 tem = 0; 5482 5483 /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has 5484 the sign bit set. */ 5485 5486 if (code == LE) 5487 { 5488 /* This is destructive, so SUBTARGET can't be OP0. */ 5489 if (rtx_equal_p (subtarget, op0)) 5490 subtarget = 0; 5491 5492 tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0, 5493 OPTAB_WIDEN); 5494 if (tem) 5495 tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0, 5496 OPTAB_WIDEN); 5497 } 5498 5499 /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the 5500 number of bits in the mode of OP0, minus one. */ 5501 5502 if (code == GT) 5503 { 5504 if (rtx_equal_p (subtarget, op0)) 5505 subtarget = 0; 5506 5507 tem = expand_shift (RSHIFT_EXPR, mode, op0, 5508 size_int (GET_MODE_BITSIZE (mode) - 1), 5509 subtarget, 0); 5510 tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0, 5511 OPTAB_WIDEN); 5512 } 5513 5514 if (code == EQ || code == NE) 5515 { 5516 /* For EQ or NE, one way to do the comparison is to apply an operation 5517 that converts the operand into a positive number if it is nonzero 5518 or zero if it was originally zero. Then, for EQ, we subtract 1 and 5519 for NE we negate. This puts the result in the sign bit. Then we 5520 normalize with a shift, if needed. 5521 5522 Two operations that can do the above actions are ABS and FFS, so try 5523 them. If that doesn't work, and MODE is smaller than a full word, 5524 we can use zero-extension to the wider mode (an unsigned conversion) 5525 as the operation. */ 5526 5527 /* Note that ABS doesn't yield a positive number for INT_MIN, but 5528 that is compensated by the subsequent overflow when subtracting 5529 one / negating. */ 5530 5531 if (abs_optab->handlers[mode].insn_code != CODE_FOR_nothing) 5532 tem = expand_unop (mode, abs_optab, op0, subtarget, 1); 5533 else if (ffs_optab->handlers[mode].insn_code != CODE_FOR_nothing) 5534 tem = expand_unop (mode, ffs_optab, op0, subtarget, 1); 5535 else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD) 5536 { 5537 tem = convert_modes (word_mode, mode, op0, 1); 5538 mode = word_mode; 5539 } 5540 5541 if (tem != 0) 5542 { 5543 if (code == EQ) 5544 tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget, 5545 0, OPTAB_WIDEN); 5546 else 5547 tem = expand_unop (mode, neg_optab, tem, subtarget, 0); 5548 } 5549 5550 /* If we couldn't do it that way, for NE we can "or" the two's complement 5551 of the value with itself. For EQ, we take the one's complement of 5552 that "or", which is an extra insn, so we only handle EQ if branches 5553 are expensive. */ 5554 5555 if (tem == 0 && (code == NE || BRANCH_COST > 1)) 5556 { 5557 if (rtx_equal_p (subtarget, op0)) 5558 subtarget = 0; 5559 5560 tem = expand_unop (mode, neg_optab, op0, subtarget, 0); 5561 tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0, 5562 OPTAB_WIDEN); 5563 5564 if (tem && code == EQ) 5565 tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0); 5566 } 5567 } 5568 5569 if (tem && normalizep) 5570 tem = expand_shift (RSHIFT_EXPR, mode, tem, 5571 size_int (GET_MODE_BITSIZE (mode) - 1), 5572 subtarget, normalizep == 1); 5573 5574 if (tem) 5575 { 5576 if (GET_MODE (tem) != target_mode) 5577 { 5578 convert_move (target, tem, 0); 5579 tem = target; 5580 } 5581 else if (!subtarget) 5582 { 5583 emit_move_insn (target, tem); 5584 tem = target; 5585 } 5586 } 5587 else 5588 delete_insns_since (last); 5589 5590 return tem; 5591} 5592 5593/* Like emit_store_flag, but always succeeds. */ 5594 5595rtx 5596emit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1, 5597 enum machine_mode mode, int unsignedp, int normalizep) 5598{ 5599 rtx tem, label; 5600 5601 /* First see if emit_store_flag can do the job. */ 5602 tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep); 5603 if (tem != 0) 5604 return tem; 5605 5606 if (normalizep == 0) 5607 normalizep = 1; 5608 5609 /* If this failed, we have to do this with set/compare/jump/set code. */ 5610 5611 if (!REG_P (target) 5612 || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1)) 5613 target = gen_reg_rtx (GET_MODE (target)); 5614 5615 emit_move_insn (target, const1_rtx); 5616 label = gen_label_rtx (); 5617 do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX, 5618 NULL_RTX, label); 5619 5620 emit_move_insn (target, const0_rtx); 5621 emit_label (label); 5622 5623 return target; 5624} 5625 5626/* Perform possibly multi-word comparison and conditional jump to LABEL 5627 if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE 5628 5629 The algorithm is based on the code in expr.c:do_jump. 5630 5631 Note that this does not perform a general comparison. Only 5632 variants generated within expmed.c are correctly handled, others 5633 could be handled if needed. */ 5634 5635static void 5636do_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode, 5637 rtx label) 5638{ 5639 /* If this mode is an integer too wide to compare properly, 5640 compare word by word. Rely on cse to optimize constant cases. */ 5641 5642 if (GET_MODE_CLASS (mode) == MODE_INT 5643 && ! can_compare_p (op, mode, ccp_jump)) 5644 { 5645 rtx label2 = gen_label_rtx (); 5646 5647 switch (op) 5648 { 5649 case LTU: 5650 do_jump_by_parts_greater_rtx (mode, 1, arg2, arg1, label2, label); 5651 break; 5652 5653 case LEU: 5654 do_jump_by_parts_greater_rtx (mode, 1, arg1, arg2, label, label2); 5655 break; 5656 5657 case LT: 5658 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label2, label); 5659 break; 5660 5661 case GT: 5662 do_jump_by_parts_greater_rtx (mode, 0, arg1, arg2, label2, label); 5663 break; 5664 5665 case GE: 5666 do_jump_by_parts_greater_rtx (mode, 0, arg2, arg1, label, label2); 5667 break; 5668 5669 /* do_jump_by_parts_equality_rtx compares with zero. Luckily 5670 that's the only equality operations we do */ 5671 case EQ: 5672 gcc_assert (arg2 == const0_rtx && mode == GET_MODE(arg1)); 5673 do_jump_by_parts_equality_rtx (arg1, label2, label); 5674 break; 5675 5676 case NE: 5677 gcc_assert (arg2 == const0_rtx && mode == GET_MODE(arg1)); 5678 do_jump_by_parts_equality_rtx (arg1, label, label2); 5679 break; 5680 5681 default: 5682 gcc_unreachable (); 5683 } 5684 5685 emit_label (label2); 5686 } 5687 else 5688 emit_cmp_and_jump_insns (arg1, arg2, op, NULL_RTX, mode, 0, label); 5689} 5690