118334Speter/* Medium-level subroutines: convert bit-field store and extract 218334Speter and shifts, multiplies and divides to rtl instructions. 372562Sobrien Copyright (C) 1987, 1988, 1989, 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4169689Skan 1999, 2000, 2001, 2002, 2003, 2004, 2005, 2006 5169689Skan Free Software Foundation, Inc. 618334Speter 790075SobrienThis file is part of GCC. 818334Speter 990075SobrienGCC is free software; you can redistribute it and/or modify it under 1090075Sobrienthe terms of the GNU General Public License as published by the Free 1190075SobrienSoftware Foundation; either version 2, or (at your option) any later 1290075Sobrienversion. 1318334Speter 1490075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1590075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1690075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1790075Sobrienfor more details. 1818334Speter 1918334SpeterYou should have received a copy of the GNU General Public License 2090075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 21169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 22169689Skan02110-1301, USA. */ 2318334Speter 2418334Speter 2518334Speter#include "config.h" 2650397Sobrien#include "system.h" 27132718Skan#include "coretypes.h" 28132718Skan#include "tm.h" 2952284Sobrien#include "toplev.h" 3018334Speter#include "rtl.h" 3118334Speter#include "tree.h" 3290075Sobrien#include "tm_p.h" 3318334Speter#include "flags.h" 3418334Speter#include "insn-config.h" 3518334Speter#include "expr.h" 3690075Sobrien#include "optabs.h" 3718334Speter#include "real.h" 3818334Speter#include "recog.h" 39117395Skan#include "langhooks.h" 4018334Speter 41132718Skanstatic void store_fixed_bit_field (rtx, unsigned HOST_WIDE_INT, 42132718Skan unsigned HOST_WIDE_INT, 43132718Skan unsigned HOST_WIDE_INT, rtx); 44132718Skanstatic void store_split_bit_field (rtx, unsigned HOST_WIDE_INT, 45132718Skan unsigned HOST_WIDE_INT, rtx); 46132718Skanstatic rtx extract_fixed_bit_field (enum machine_mode, rtx, 47132718Skan unsigned HOST_WIDE_INT, 48132718Skan unsigned HOST_WIDE_INT, 49132718Skan unsigned HOST_WIDE_INT, rtx, int); 50132718Skanstatic rtx mask_rtx (enum machine_mode, int, int, int); 51132718Skanstatic rtx lshift_value (enum machine_mode, rtx, int, int); 52132718Skanstatic rtx extract_split_bit_field (rtx, unsigned HOST_WIDE_INT, 53132718Skan unsigned HOST_WIDE_INT, int); 54132718Skanstatic void do_cmp_and_jump (rtx, rtx, enum rtx_code, enum machine_mode, rtx); 55169689Skanstatic rtx expand_smod_pow2 (enum machine_mode, rtx, HOST_WIDE_INT); 56169689Skanstatic rtx expand_sdiv_pow2 (enum machine_mode, rtx, HOST_WIDE_INT); 5718334Speter 58169689Skan/* Test whether a value is zero of a power of two. */ 59169689Skan#define EXACT_POWER_OF_2_OR_ZERO_P(x) (((x) & ((x) - 1)) == 0) 60169689Skan 61117395Skan/* Nonzero means divides or modulus operations are relatively cheap for 6296263Sobrien powers of two, so don't use branches; emit the operation instead. 6318334Speter Usually, this will mean that the MD file will emit non-branch 6418334Speter sequences. */ 6518334Speter 66169689Skanstatic bool sdiv_pow2_cheap[NUM_MACHINE_MODES]; 67169689Skanstatic bool smod_pow2_cheap[NUM_MACHINE_MODES]; 6818334Speter 6918334Speter#ifndef SLOW_UNALIGNED_ACCESS 7090075Sobrien#define SLOW_UNALIGNED_ACCESS(MODE, ALIGN) STRICT_ALIGNMENT 7118334Speter#endif 7218334Speter 7318334Speter/* For compilers that support multiple targets with different word sizes, 7418334Speter MAX_BITS_PER_WORD contains the biggest value of BITS_PER_WORD. An example 7518334Speter is the H8/300(H) compiler. */ 7618334Speter 7718334Speter#ifndef MAX_BITS_PER_WORD 7818334Speter#define MAX_BITS_PER_WORD BITS_PER_WORD 7918334Speter#endif 8018334Speter 8190075Sobrien/* Reduce conditional compilation elsewhere. */ 8290075Sobrien#ifndef HAVE_insv 8390075Sobrien#define HAVE_insv 0 8490075Sobrien#define CODE_FOR_insv CODE_FOR_nothing 8590075Sobrien#define gen_insv(a,b,c,d) NULL_RTX 8690075Sobrien#endif 8790075Sobrien#ifndef HAVE_extv 8890075Sobrien#define HAVE_extv 0 8990075Sobrien#define CODE_FOR_extv CODE_FOR_nothing 9090075Sobrien#define gen_extv(a,b,c,d) NULL_RTX 9190075Sobrien#endif 9290075Sobrien#ifndef HAVE_extzv 9390075Sobrien#define HAVE_extzv 0 9490075Sobrien#define CODE_FOR_extzv CODE_FOR_nothing 9590075Sobrien#define gen_extzv(a,b,c,d) NULL_RTX 9690075Sobrien#endif 9790075Sobrien 9890075Sobrien/* Cost of various pieces of RTL. Note that some of these are indexed by 9990075Sobrien shift count and some by mode. */ 100169689Skanstatic int zero_cost; 101169689Skanstatic int add_cost[NUM_MACHINE_MODES]; 102169689Skanstatic int neg_cost[NUM_MACHINE_MODES]; 103169689Skanstatic int shift_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 104169689Skanstatic int shiftadd_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 105169689Skanstatic int shiftsub_cost[NUM_MACHINE_MODES][MAX_BITS_PER_WORD]; 10618334Speterstatic int mul_cost[NUM_MACHINE_MODES]; 107169689Skanstatic int sdiv_cost[NUM_MACHINE_MODES]; 108169689Skanstatic int udiv_cost[NUM_MACHINE_MODES]; 10918334Speterstatic int mul_widen_cost[NUM_MACHINE_MODES]; 11018334Speterstatic int mul_highpart_cost[NUM_MACHINE_MODES]; 11118334Speter 11218334Spetervoid 113132718Skaninit_expmed (void) 11418334Speter{ 115169689Skan struct 116169689Skan { 117169689Skan struct rtx_def reg; rtunion reg_fld[2]; 118169689Skan struct rtx_def plus; rtunion plus_fld1; 119169689Skan struct rtx_def neg; 120169689Skan struct rtx_def mult; rtunion mult_fld1; 121169689Skan struct rtx_def sdiv; rtunion sdiv_fld1; 122169689Skan struct rtx_def udiv; rtunion udiv_fld1; 123169689Skan struct rtx_def zext; 124169689Skan struct rtx_def sdiv_32; rtunion sdiv_32_fld1; 125169689Skan struct rtx_def smod_32; rtunion smod_32_fld1; 126169689Skan struct rtx_def wide_mult; rtunion wide_mult_fld1; 127169689Skan struct rtx_def wide_lshr; rtunion wide_lshr_fld1; 128169689Skan struct rtx_def wide_trunc; 129169689Skan struct rtx_def shift; rtunion shift_fld1; 130169689Skan struct rtx_def shift_mult; rtunion shift_mult_fld1; 131169689Skan struct rtx_def shift_add; rtunion shift_add_fld1; 132169689Skan struct rtx_def shift_sub; rtunion shift_sub_fld1; 133169689Skan } all; 134169689Skan 135169689Skan rtx pow2[MAX_BITS_PER_WORD]; 136169689Skan rtx cint[MAX_BITS_PER_WORD]; 137169689Skan int m, n; 13818334Speter enum machine_mode mode, wider_mode; 13918334Speter 140169689Skan zero_cost = rtx_cost (const0_rtx, 0); 14118334Speter 142169689Skan for (m = 1; m < MAX_BITS_PER_WORD; m++) 143169689Skan { 144169689Skan pow2[m] = GEN_INT ((HOST_WIDE_INT) 1 << m); 145169689Skan cint[m] = GEN_INT (m); 146169689Skan } 14718334Speter 148169689Skan memset (&all, 0, sizeof all); 14918334Speter 150169689Skan PUT_CODE (&all.reg, REG); 151169689Skan /* Avoid using hard regs in ways which may be unsupported. */ 152169689Skan REGNO (&all.reg) = LAST_VIRTUAL_REGISTER + 1; 15318334Speter 154169689Skan PUT_CODE (&all.plus, PLUS); 155169689Skan XEXP (&all.plus, 0) = &all.reg; 156169689Skan XEXP (&all.plus, 1) = &all.reg; 15718334Speter 158169689Skan PUT_CODE (&all.neg, NEG); 159169689Skan XEXP (&all.neg, 0) = &all.reg; 16018334Speter 161169689Skan PUT_CODE (&all.mult, MULT); 162169689Skan XEXP (&all.mult, 0) = &all.reg; 163169689Skan XEXP (&all.mult, 1) = &all.reg; 16418334Speter 165169689Skan PUT_CODE (&all.sdiv, DIV); 166169689Skan XEXP (&all.sdiv, 0) = &all.reg; 167169689Skan XEXP (&all.sdiv, 1) = &all.reg; 16818334Speter 169169689Skan PUT_CODE (&all.udiv, UDIV); 170169689Skan XEXP (&all.udiv, 0) = &all.reg; 171169689Skan XEXP (&all.udiv, 1) = &all.reg; 17218334Speter 173169689Skan PUT_CODE (&all.sdiv_32, DIV); 174169689Skan XEXP (&all.sdiv_32, 0) = &all.reg; 175169689Skan XEXP (&all.sdiv_32, 1) = 32 < MAX_BITS_PER_WORD ? cint[32] : GEN_INT (32); 17618334Speter 177169689Skan PUT_CODE (&all.smod_32, MOD); 178169689Skan XEXP (&all.smod_32, 0) = &all.reg; 179169689Skan XEXP (&all.smod_32, 1) = XEXP (&all.sdiv_32, 1); 18018334Speter 181169689Skan PUT_CODE (&all.zext, ZERO_EXTEND); 182169689Skan XEXP (&all.zext, 0) = &all.reg; 18318334Speter 184169689Skan PUT_CODE (&all.wide_mult, MULT); 185169689Skan XEXP (&all.wide_mult, 0) = &all.zext; 186169689Skan XEXP (&all.wide_mult, 1) = &all.zext; 18718334Speter 188169689Skan PUT_CODE (&all.wide_lshr, LSHIFTRT); 189169689Skan XEXP (&all.wide_lshr, 0) = &all.wide_mult; 19018334Speter 191169689Skan PUT_CODE (&all.wide_trunc, TRUNCATE); 192169689Skan XEXP (&all.wide_trunc, 0) = &all.wide_lshr; 193169689Skan 194169689Skan PUT_CODE (&all.shift, ASHIFT); 195169689Skan XEXP (&all.shift, 0) = &all.reg; 196169689Skan 197169689Skan PUT_CODE (&all.shift_mult, MULT); 198169689Skan XEXP (&all.shift_mult, 0) = &all.reg; 199169689Skan 200169689Skan PUT_CODE (&all.shift_add, PLUS); 201169689Skan XEXP (&all.shift_add, 0) = &all.shift_mult; 202169689Skan XEXP (&all.shift_add, 1) = &all.reg; 203169689Skan 204169689Skan PUT_CODE (&all.shift_sub, MINUS); 205169689Skan XEXP (&all.shift_sub, 0) = &all.shift_mult; 206169689Skan XEXP (&all.shift_sub, 1) = &all.reg; 207169689Skan 20818334Speter for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); 20918334Speter mode != VOIDmode; 21018334Speter mode = GET_MODE_WIDER_MODE (mode)) 21118334Speter { 212169689Skan PUT_MODE (&all.reg, mode); 213169689Skan PUT_MODE (&all.plus, mode); 214169689Skan PUT_MODE (&all.neg, mode); 215169689Skan PUT_MODE (&all.mult, mode); 216169689Skan PUT_MODE (&all.sdiv, mode); 217169689Skan PUT_MODE (&all.udiv, mode); 218169689Skan PUT_MODE (&all.sdiv_32, mode); 219169689Skan PUT_MODE (&all.smod_32, mode); 220169689Skan PUT_MODE (&all.wide_trunc, mode); 221169689Skan PUT_MODE (&all.shift, mode); 222169689Skan PUT_MODE (&all.shift_mult, mode); 223169689Skan PUT_MODE (&all.shift_add, mode); 224169689Skan PUT_MODE (&all.shift_sub, mode); 225169689Skan 226169689Skan add_cost[mode] = rtx_cost (&all.plus, SET); 227169689Skan neg_cost[mode] = rtx_cost (&all.neg, SET); 228169689Skan mul_cost[mode] = rtx_cost (&all.mult, SET); 229169689Skan sdiv_cost[mode] = rtx_cost (&all.sdiv, SET); 230169689Skan udiv_cost[mode] = rtx_cost (&all.udiv, SET); 231169689Skan 232169689Skan sdiv_pow2_cheap[mode] = (rtx_cost (&all.sdiv_32, SET) 233169689Skan <= 2 * add_cost[mode]); 234169689Skan smod_pow2_cheap[mode] = (rtx_cost (&all.smod_32, SET) 235169689Skan <= 4 * add_cost[mode]); 236169689Skan 23718334Speter wider_mode = GET_MODE_WIDER_MODE (mode); 23818334Speter if (wider_mode != VOIDmode) 23918334Speter { 240169689Skan PUT_MODE (&all.zext, wider_mode); 241169689Skan PUT_MODE (&all.wide_mult, wider_mode); 242169689Skan PUT_MODE (&all.wide_lshr, wider_mode); 243169689Skan XEXP (&all.wide_lshr, 1) = GEN_INT (GET_MODE_BITSIZE (mode)); 244169689Skan 245169689Skan mul_widen_cost[wider_mode] = rtx_cost (&all.wide_mult, SET); 246169689Skan mul_highpart_cost[mode] = rtx_cost (&all.wide_trunc, SET); 24718334Speter } 248169689Skan 249169689Skan shift_cost[mode][0] = 0; 250169689Skan shiftadd_cost[mode][0] = shiftsub_cost[mode][0] = add_cost[mode]; 251169689Skan 252169689Skan n = MIN (MAX_BITS_PER_WORD, GET_MODE_BITSIZE (mode)); 253169689Skan for (m = 1; m < n; m++) 254169689Skan { 255169689Skan XEXP (&all.shift, 1) = cint[m]; 256169689Skan XEXP (&all.shift_mult, 1) = pow2[m]; 257169689Skan 258169689Skan shift_cost[mode][m] = rtx_cost (&all.shift, SET); 259169689Skan shiftadd_cost[mode][m] = rtx_cost (&all.shift_add, SET); 260169689Skan shiftsub_cost[mode][m] = rtx_cost (&all.shift_sub, SET); 261169689Skan } 26218334Speter } 26318334Speter} 26418334Speter 26518334Speter/* Return an rtx representing minus the value of X. 26618334Speter MODE is the intended mode of the result, 26718334Speter useful if X is a CONST_INT. */ 26818334Speter 26918334Speterrtx 270132718Skannegate_rtx (enum machine_mode mode, rtx x) 27118334Speter{ 27250397Sobrien rtx result = simplify_unary_operation (NEG, mode, x, mode); 27350397Sobrien 27450397Sobrien if (result == 0) 27550397Sobrien result = expand_unop (mode, neg_optab, x, NULL_RTX, 0); 27650397Sobrien 27750397Sobrien return result; 27818334Speter} 27990075Sobrien 28090075Sobrien/* Report on the availability of insv/extv/extzv and the desired mode 28190075Sobrien of each of their operands. Returns MAX_MACHINE_MODE if HAVE_foo 28290075Sobrien is false; else the mode of the specified operand. If OPNO is -1, 28390075Sobrien all the caller cares about is whether the insn is available. */ 28490075Sobrienenum machine_mode 285132718Skanmode_for_extraction (enum extraction_pattern pattern, int opno) 28690075Sobrien{ 28790075Sobrien const struct insn_data *data; 28890075Sobrien 28990075Sobrien switch (pattern) 29090075Sobrien { 29190075Sobrien case EP_insv: 29290075Sobrien if (HAVE_insv) 29390075Sobrien { 29490075Sobrien data = &insn_data[CODE_FOR_insv]; 29590075Sobrien break; 29690075Sobrien } 29790075Sobrien return MAX_MACHINE_MODE; 29890075Sobrien 29990075Sobrien case EP_extv: 30090075Sobrien if (HAVE_extv) 30190075Sobrien { 30290075Sobrien data = &insn_data[CODE_FOR_extv]; 30390075Sobrien break; 30490075Sobrien } 30590075Sobrien return MAX_MACHINE_MODE; 30690075Sobrien 30790075Sobrien case EP_extzv: 30890075Sobrien if (HAVE_extzv) 30990075Sobrien { 31090075Sobrien data = &insn_data[CODE_FOR_extzv]; 31190075Sobrien break; 31290075Sobrien } 31390075Sobrien return MAX_MACHINE_MODE; 31490075Sobrien 31590075Sobrien default: 316169689Skan gcc_unreachable (); 31790075Sobrien } 31890075Sobrien 31990075Sobrien if (opno == -1) 32090075Sobrien return VOIDmode; 32190075Sobrien 32290075Sobrien /* Everyone who uses this function used to follow it with 32390075Sobrien if (result == VOIDmode) result = word_mode; */ 32490075Sobrien if (data->operand[opno].mode == VOIDmode) 32590075Sobrien return word_mode; 32690075Sobrien return data->operand[opno].mode; 32790075Sobrien} 32890075Sobrien 32918334Speter 33018334Speter/* Generate code to store value from rtx VALUE 33118334Speter into a bit-field within structure STR_RTX 33218334Speter containing BITSIZE bits starting at bit BITNUM. 33318334Speter FIELDMODE is the machine-mode of the FIELD_DECL node for this field. 33490075Sobrien ALIGN is the alignment that STR_RTX is known to have. 33518334Speter TOTAL_SIZE is the size of the structure in bytes, or -1 if varying. */ 33618334Speter 33718334Speter/* ??? Note that there are two different ideas here for how 33818334Speter to determine the size to count bits within, for a register. 33918334Speter One is BITS_PER_WORD, and the other is the size of operand 3 34052284Sobrien of the insv pattern. 34118334Speter 34252284Sobrien If operand 3 of the insv pattern is VOIDmode, then we will use BITS_PER_WORD 34352284Sobrien else, we use the mode of operand 3. */ 34452284Sobrien 34518334Speterrtx 346132718Skanstore_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize, 347132718Skan unsigned HOST_WIDE_INT bitnum, enum machine_mode fieldmode, 348169689Skan rtx value) 34918334Speter{ 35090075Sobrien unsigned int unit 351169689Skan = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD; 352169689Skan unsigned HOST_WIDE_INT offset, bitpos; 35390075Sobrien rtx op0 = str_rtx; 35496263Sobrien int byte_offset; 355146895Skan rtx orig_value; 35618334Speter 35790075Sobrien enum machine_mode op_mode = mode_for_extraction (EP_insv, 3); 35852284Sobrien 35918334Speter while (GET_CODE (op0) == SUBREG) 36018334Speter { 36118334Speter /* The following line once was done only if WORDS_BIG_ENDIAN, 36218334Speter but I think that is a mistake. WORDS_BIG_ENDIAN is 36318334Speter meaningful at a much higher level; when structures are copied 36418334Speter between memory and regs, the higher-numbered regs 36518334Speter always get higher addresses. */ 366169689Skan int inner_mode_size = GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))); 367169689Skan int outer_mode_size = GET_MODE_SIZE (GET_MODE (op0)); 368169689Skan 369169689Skan byte_offset = 0; 370169689Skan 371169689Skan /* Paradoxical subregs need special handling on big endian machines. */ 372169689Skan if (SUBREG_BYTE (op0) == 0 && inner_mode_size < outer_mode_size) 373169689Skan { 374169689Skan int difference = inner_mode_size - outer_mode_size; 375169689Skan 376169689Skan if (WORDS_BIG_ENDIAN) 377169689Skan byte_offset += (difference / UNITS_PER_WORD) * UNITS_PER_WORD; 378169689Skan if (BYTES_BIG_ENDIAN) 379169689Skan byte_offset += difference % UNITS_PER_WORD; 380169689Skan } 381169689Skan else 382169689Skan byte_offset = SUBREG_BYTE (op0); 383169689Skan 384169689Skan bitnum += byte_offset * BITS_PER_UNIT; 38518334Speter op0 = SUBREG_REG (op0); 38618334Speter } 38718334Speter 388169689Skan /* No action is needed if the target is a register and if the field 389169689Skan lies completely outside that register. This can occur if the source 390169689Skan code contains an out-of-bounds access to a small array. */ 391169689Skan if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0))) 392169689Skan return value; 39318334Speter 394169689Skan /* Use vec_set patterns for inserting parts of vectors whenever 395132718Skan available. */ 396132718Skan if (VECTOR_MODE_P (GET_MODE (op0)) 397169689Skan && !MEM_P (op0) 398169689Skan && (vec_set_optab->handlers[GET_MODE (op0)].insn_code 399132718Skan != CODE_FOR_nothing) 400132718Skan && fieldmode == GET_MODE_INNER (GET_MODE (op0)) 401132718Skan && bitsize == GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))) 402132718Skan && !(bitnum % GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))))) 403132718Skan { 404132718Skan enum machine_mode outermode = GET_MODE (op0); 405132718Skan enum machine_mode innermode = GET_MODE_INNER (outermode); 406169689Skan int icode = (int) vec_set_optab->handlers[outermode].insn_code; 407132718Skan int pos = bitnum / GET_MODE_BITSIZE (innermode); 408132718Skan rtx rtxpos = GEN_INT (pos); 409132718Skan rtx src = value; 410132718Skan rtx dest = op0; 411132718Skan rtx pat, seq; 412132718Skan enum machine_mode mode0 = insn_data[icode].operand[0].mode; 413132718Skan enum machine_mode mode1 = insn_data[icode].operand[1].mode; 414132718Skan enum machine_mode mode2 = insn_data[icode].operand[2].mode; 415132718Skan 416132718Skan start_sequence (); 417132718Skan 418132718Skan if (! (*insn_data[icode].operand[1].predicate) (src, mode1)) 419132718Skan src = copy_to_mode_reg (mode1, src); 420132718Skan 421132718Skan if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)) 422132718Skan rtxpos = copy_to_mode_reg (mode1, rtxpos); 423132718Skan 424132718Skan /* We could handle this, but we should always be called with a pseudo 425132718Skan for our targets and all insns should take them as outputs. */ 426169689Skan gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0) 427169689Skan && (*insn_data[icode].operand[1].predicate) (src, mode1) 428169689Skan && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)); 429132718Skan pat = GEN_FCN (icode) (dest, src, rtxpos); 430132718Skan seq = get_insns (); 431132718Skan end_sequence (); 432132718Skan if (pat) 433132718Skan { 434132718Skan emit_insn (seq); 435132718Skan emit_insn (pat); 436132718Skan return dest; 437132718Skan } 438132718Skan } 439132718Skan 44090075Sobrien /* If the target is a register, overwriting the entire object, or storing 44190075Sobrien a full-word or multi-word field can be done with just a SUBREG. 44290075Sobrien 44390075Sobrien If the target is memory, storing any naturally aligned field can be 44490075Sobrien done with a simple store. For targets that support fast unaligned 44590075Sobrien memory, any naturally sized, unit aligned field can be done directly. */ 44696263Sobrien 447169689Skan offset = bitnum / unit; 448169689Skan bitpos = bitnum % unit; 44996263Sobrien byte_offset = (bitnum % BITS_PER_WORD) / BITS_PER_UNIT 45096263Sobrien + (offset * UNITS_PER_WORD); 45196263Sobrien 45290075Sobrien if (bitpos == 0 45390075Sobrien && bitsize == GET_MODE_BITSIZE (fieldmode) 454169689Skan && (!MEM_P (op0) 45596263Sobrien ? ((GET_MODE_SIZE (fieldmode) >= UNITS_PER_WORD 45690075Sobrien || GET_MODE_SIZE (GET_MODE (op0)) == GET_MODE_SIZE (fieldmode)) 457117395Skan && byte_offset % GET_MODE_SIZE (fieldmode) == 0) 45890075Sobrien : (! SLOW_UNALIGNED_ACCESS (fieldmode, MEM_ALIGN (op0)) 45990075Sobrien || (offset * BITS_PER_UNIT % bitsize == 0 46090075Sobrien && MEM_ALIGN (op0) % GET_MODE_BITSIZE (fieldmode) == 0)))) 46118334Speter { 462169689Skan if (MEM_P (op0)) 463161651Skan op0 = adjust_address (op0, fieldmode, offset); 464161651Skan else if (GET_MODE (op0) != fieldmode) 465161651Skan op0 = simplify_gen_subreg (fieldmode, op0, GET_MODE (op0), 466161651Skan byte_offset); 46718334Speter emit_move_insn (op0, value); 46818334Speter return value; 46918334Speter } 47018334Speter 47190075Sobrien /* Make sure we are playing with integral modes. Pun with subregs 47290075Sobrien if we aren't. This must come after the entire register case above, 47390075Sobrien since that case is valid for any mode. The following cases are only 47490075Sobrien valid for integral modes. */ 47590075Sobrien { 47690075Sobrien enum machine_mode imode = int_mode_for_mode (GET_MODE (op0)); 47790075Sobrien if (imode != GET_MODE (op0)) 47890075Sobrien { 479169689Skan if (MEM_P (op0)) 48090075Sobrien op0 = adjust_address (op0, imode, 0); 48190075Sobrien else 482169689Skan { 483169689Skan gcc_assert (imode != BLKmode); 484169689Skan op0 = gen_lowpart (imode, op0); 485169689Skan } 48690075Sobrien } 48790075Sobrien } 48890075Sobrien 48996263Sobrien /* We may be accessing data outside the field, which means 49096263Sobrien we can alias adjacent data. */ 491169689Skan if (MEM_P (op0)) 49296263Sobrien { 49396263Sobrien op0 = shallow_copy_rtx (op0); 49496263Sobrien set_mem_alias_set (op0, 0); 49596263Sobrien set_mem_expr (op0, 0); 49696263Sobrien } 49796263Sobrien 49890075Sobrien /* If OP0 is a register, BITPOS must count within a word. 49990075Sobrien But as we have it, it counts within whatever size OP0 now has. 50090075Sobrien On a bigendian machine, these are not the same, so convert. */ 50190075Sobrien if (BYTES_BIG_ENDIAN 502169689Skan && !MEM_P (op0) 50390075Sobrien && unit > GET_MODE_BITSIZE (GET_MODE (op0))) 50490075Sobrien bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0)); 50590075Sobrien 50618334Speter /* Storing an lsb-aligned field in a register 50718334Speter can be done with a movestrict instruction. */ 50818334Speter 509169689Skan if (!MEM_P (op0) 51018334Speter && (BYTES_BIG_ENDIAN ? bitpos + bitsize == unit : bitpos == 0) 51118334Speter && bitsize == GET_MODE_BITSIZE (fieldmode) 512169689Skan && (movstrict_optab->handlers[fieldmode].insn_code 51390075Sobrien != CODE_FOR_nothing)) 51418334Speter { 515169689Skan int icode = movstrict_optab->handlers[fieldmode].insn_code; 51690075Sobrien 51718334Speter /* Get appropriate low part of the value being stored. */ 518169689Skan if (GET_CODE (value) == CONST_INT || REG_P (value)) 51918334Speter value = gen_lowpart (fieldmode, value); 52018334Speter else if (!(GET_CODE (value) == SYMBOL_REF 52118334Speter || GET_CODE (value) == LABEL_REF 52218334Speter || GET_CODE (value) == CONST)) 52318334Speter value = convert_to_mode (fieldmode, value, 0); 52418334Speter 52590075Sobrien if (! (*insn_data[icode].operand[1].predicate) (value, fieldmode)) 52690075Sobrien value = copy_to_mode_reg (fieldmode, value); 52790075Sobrien 52890075Sobrien if (GET_CODE (op0) == SUBREG) 52918334Speter { 530169689Skan /* Else we've got some float mode source being extracted into 531169689Skan a different float mode destination -- this combination of 532169689Skan subregs results in Severe Tire Damage. */ 533169689Skan gcc_assert (GET_MODE (SUBREG_REG (op0)) == fieldmode 534169689Skan || GET_MODE_CLASS (fieldmode) == MODE_INT 535169689Skan || GET_MODE_CLASS (fieldmode) == MODE_PARTIAL_INT); 536169689Skan op0 = SUBREG_REG (op0); 53790075Sobrien } 53852284Sobrien 53990075Sobrien emit_insn (GEN_FCN (icode) 54090075Sobrien (gen_rtx_SUBREG (fieldmode, op0, 54190075Sobrien (bitnum % BITS_PER_WORD) / BITS_PER_UNIT 54290075Sobrien + (offset * UNITS_PER_WORD)), 54390075Sobrien value)); 54452284Sobrien 54518334Speter return value; 54618334Speter } 54718334Speter 54818334Speter /* Handle fields bigger than a word. */ 54918334Speter 55018334Speter if (bitsize > BITS_PER_WORD) 55118334Speter { 55218334Speter /* Here we transfer the words of the field 55318334Speter in the order least significant first. 55418334Speter This is because the most significant word is the one which may 55518334Speter be less than full. 55618334Speter However, only do that if the value is not BLKmode. */ 55718334Speter 55890075Sobrien unsigned int backwards = WORDS_BIG_ENDIAN && fieldmode != BLKmode; 55990075Sobrien unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD; 56090075Sobrien unsigned int i; 56118334Speter 56218334Speter /* This is the mode we must force value to, so that there will be enough 56318334Speter subwords to extract. Note that fieldmode will often (always?) be 56418334Speter VOIDmode, because that is what store_field uses to indicate that this 565169689Skan is a bit field, but passing VOIDmode to operand_subword_force 566169689Skan is not allowed. */ 567132718Skan fieldmode = GET_MODE (value); 568132718Skan if (fieldmode == VOIDmode) 569132718Skan fieldmode = smallest_mode_for_size (nwords * BITS_PER_WORD, MODE_INT); 57018334Speter 57118334Speter for (i = 0; i < nwords; i++) 57218334Speter { 57318334Speter /* If I is 0, use the low-order word in both field and target; 57418334Speter if I is 1, use the next to lowest word; and so on. */ 57590075Sobrien unsigned int wordnum = (backwards ? nwords - i - 1 : i); 57690075Sobrien unsigned int bit_offset = (backwards 57790075Sobrien ? MAX ((int) bitsize - ((int) i + 1) 57890075Sobrien * BITS_PER_WORD, 57990075Sobrien 0) 58090075Sobrien : (int) i * BITS_PER_WORD); 58190075Sobrien 58218334Speter store_bit_field (op0, MIN (BITS_PER_WORD, 58318334Speter bitsize - i * BITS_PER_WORD), 58418334Speter bitnum + bit_offset, word_mode, 585169689Skan operand_subword_force (value, wordnum, fieldmode)); 58618334Speter } 58718334Speter return value; 58818334Speter } 58918334Speter 59018334Speter /* From here on we can assume that the field to be stored in is 59118334Speter a full-word (whatever type that is), since it is shorter than a word. */ 59218334Speter 59318334Speter /* OFFSET is the number of words or bytes (UNIT says which) 59418334Speter from STR_RTX to the first word or byte containing part of the field. */ 59518334Speter 596169689Skan if (!MEM_P (op0)) 59718334Speter { 59818334Speter if (offset != 0 59918334Speter || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD) 60052284Sobrien { 601169689Skan if (!REG_P (op0)) 60252284Sobrien { 603169689Skan /* Since this is a destination (lvalue), we can't copy 604169689Skan it to a pseudo. We can remove a SUBREG that does not 605169689Skan change the size of the operand. Such a SUBREG may 606169689Skan have been added above. */ 607169689Skan gcc_assert (GET_CODE (op0) == SUBREG 608169689Skan && (GET_MODE_SIZE (GET_MODE (op0)) 609169689Skan == GET_MODE_SIZE (GET_MODE (SUBREG_REG (op0))))); 610169689Skan op0 = SUBREG_REG (op0); 61152284Sobrien } 61252284Sobrien op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0), 61390075Sobrien op0, (offset * UNITS_PER_WORD)); 61452284Sobrien } 61518334Speter offset = 0; 61618334Speter } 61718334Speter 618169689Skan /* If VALUE has a floating-point or complex mode, access it as an 619169689Skan integer of the corresponding size. This can occur on a machine 620169689Skan with 64 bit registers that uses SFmode for float. It can also 621169689Skan occur for unaligned float or complex fields. */ 622146895Skan orig_value = value; 623169689Skan if (GET_MODE (value) != VOIDmode 624169689Skan && GET_MODE_CLASS (GET_MODE (value)) != MODE_INT 62596263Sobrien && GET_MODE_CLASS (GET_MODE (value)) != MODE_PARTIAL_INT) 626169689Skan { 627169689Skan value = gen_reg_rtx (int_mode_for_mode (GET_MODE (value))); 628169689Skan emit_move_insn (gen_lowpart (GET_MODE (orig_value), value), orig_value); 629169689Skan } 63018334Speter 63118334Speter /* Now OFFSET is nonzero only if OP0 is memory 63218334Speter and is therefore always measured in bytes. */ 63318334Speter 63418334Speter if (HAVE_insv 63550397Sobrien && GET_MODE (value) != BLKmode 636169689Skan && bitsize > 0 637169689Skan && GET_MODE_BITSIZE (op_mode) >= bitsize 638169689Skan && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 639169689Skan && (bitsize + bitpos > GET_MODE_BITSIZE (op_mode))) 640169689Skan && insn_data[CODE_FOR_insv].operand[1].predicate (GEN_INT (bitsize), 641169689Skan VOIDmode)) 64218334Speter { 64318334Speter int xbitpos = bitpos; 64418334Speter rtx value1; 64518334Speter rtx xop0 = op0; 64618334Speter rtx last = get_last_insn (); 64718334Speter rtx pat; 64890075Sobrien enum machine_mode maxmode = mode_for_extraction (EP_insv, 3); 64952284Sobrien int save_volatile_ok = volatile_ok; 65018334Speter 65118334Speter volatile_ok = 1; 65218334Speter 65350397Sobrien /* If this machine's insv can only insert into a register, copy OP0 65450397Sobrien into a register and save it back later. */ 655169689Skan if (MEM_P (op0) 65690075Sobrien && ! ((*insn_data[(int) CODE_FOR_insv].operand[0].predicate) 65750397Sobrien (op0, VOIDmode))) 65818334Speter { 65918334Speter rtx tempreg; 66018334Speter enum machine_mode bestmode; 66118334Speter 66218334Speter /* Get the mode to use for inserting into this field. If OP0 is 66318334Speter BLKmode, get the smallest mode consistent with the alignment. If 66418334Speter OP0 is a non-BLKmode object that is no wider than MAXMODE, use its 66518334Speter mode. Otherwise, use the smallest mode containing the field. */ 66618334Speter 66718334Speter if (GET_MODE (op0) == BLKmode 66818334Speter || GET_MODE_SIZE (GET_MODE (op0)) > GET_MODE_SIZE (maxmode)) 66918334Speter bestmode 67090075Sobrien = get_best_mode (bitsize, bitnum, MEM_ALIGN (op0), maxmode, 67118334Speter MEM_VOLATILE_P (op0)); 67218334Speter else 67318334Speter bestmode = GET_MODE (op0); 67418334Speter 67518334Speter if (bestmode == VOIDmode 676161651Skan || GET_MODE_SIZE (bestmode) < GET_MODE_SIZE (fieldmode) 67790075Sobrien || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (op0)) 67890075Sobrien && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (op0))) 67918334Speter goto insv_loses; 68018334Speter 68196263Sobrien /* Adjust address to point to the containing unit of that mode. 68290075Sobrien Compute offset as multiple of this unit, counting in bytes. */ 68318334Speter unit = GET_MODE_BITSIZE (bestmode); 68418334Speter offset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 68518334Speter bitpos = bitnum % unit; 68690075Sobrien op0 = adjust_address (op0, bestmode, offset); 68718334Speter 68890075Sobrien /* Fetch that unit, store the bitfield in it, then store 68990075Sobrien the unit. */ 69018334Speter tempreg = copy_to_reg (op0); 691169689Skan store_bit_field (tempreg, bitsize, bitpos, fieldmode, orig_value); 69218334Speter emit_move_insn (op0, tempreg); 69318334Speter return value; 69418334Speter } 69518334Speter volatile_ok = save_volatile_ok; 69618334Speter 69718334Speter /* Add OFFSET into OP0's address. */ 698169689Skan if (MEM_P (xop0)) 69990075Sobrien xop0 = adjust_address (xop0, byte_mode, offset); 70018334Speter 70118334Speter /* If xop0 is a register, we need it in MAXMODE 70218334Speter to make it acceptable to the format of insv. */ 70318334Speter if (GET_CODE (xop0) == SUBREG) 70418334Speter /* We can't just change the mode, because this might clobber op0, 70518334Speter and we will need the original value of op0 if insv fails. */ 70690075Sobrien xop0 = gen_rtx_SUBREG (maxmode, SUBREG_REG (xop0), SUBREG_BYTE (xop0)); 707169689Skan if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 70850397Sobrien xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 70918334Speter 71018334Speter /* On big-endian machines, we count bits from the most significant. 71118334Speter If the bit field insn does not, we must invert. */ 71218334Speter 71318334Speter if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 71418334Speter xbitpos = unit - bitsize - xbitpos; 71518334Speter 71618334Speter /* We have been counting XBITPOS within UNIT. 71718334Speter Count instead within the size of the register. */ 718169689Skan if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 71918334Speter xbitpos += GET_MODE_BITSIZE (maxmode) - unit; 72018334Speter 72118334Speter unit = GET_MODE_BITSIZE (maxmode); 72218334Speter 72318334Speter /* Convert VALUE to maxmode (which insv insn wants) in VALUE1. */ 72418334Speter value1 = value; 72518334Speter if (GET_MODE (value) != maxmode) 72618334Speter { 72718334Speter if (GET_MODE_BITSIZE (GET_MODE (value)) >= bitsize) 72818334Speter { 72918334Speter /* Optimization: Don't bother really extending VALUE 73018334Speter if it has all the bits we will actually use. However, 73118334Speter if we must narrow it, be sure we do it correctly. */ 73218334Speter 73318334Speter if (GET_MODE_SIZE (GET_MODE (value)) < GET_MODE_SIZE (maxmode)) 73496263Sobrien { 73596263Sobrien rtx tmp; 73696263Sobrien 73796263Sobrien tmp = simplify_subreg (maxmode, value1, GET_MODE (value), 0); 73896263Sobrien if (! tmp) 73996263Sobrien tmp = simplify_gen_subreg (maxmode, 74096263Sobrien force_reg (GET_MODE (value), 74196263Sobrien value1), 74296263Sobrien GET_MODE (value), 0); 74396263Sobrien value1 = tmp; 74496263Sobrien } 74518334Speter else 74618334Speter value1 = gen_lowpart (maxmode, value1); 74718334Speter } 74890075Sobrien else if (GET_CODE (value) == CONST_INT) 749117395Skan value1 = gen_int_mode (INTVAL (value), maxmode); 750169689Skan else 75118334Speter /* Parse phase is supposed to make VALUE's data type 75218334Speter match that of the component reference, which is a type 75318334Speter at least as wide as the field; so VALUE should have 75418334Speter a mode that corresponds to that type. */ 755169689Skan gcc_assert (CONSTANT_P (value)); 75618334Speter } 75718334Speter 75818334Speter /* If this machine's insv insists on a register, 75918334Speter get VALUE1 into a register. */ 76090075Sobrien if (! ((*insn_data[(int) CODE_FOR_insv].operand[3].predicate) 76118334Speter (value1, maxmode))) 76218334Speter value1 = force_reg (maxmode, value1); 76318334Speter 76418334Speter pat = gen_insv (xop0, GEN_INT (bitsize), GEN_INT (xbitpos), value1); 76518334Speter if (pat) 76618334Speter emit_insn (pat); 76718334Speter else 768117395Skan { 76918334Speter delete_insns_since (last); 77090075Sobrien store_fixed_bit_field (op0, offset, bitsize, bitpos, value); 77118334Speter } 77218334Speter } 77318334Speter else 77418334Speter insv_loses: 77518334Speter /* Insv is not available; store using shifts and boolean ops. */ 77690075Sobrien store_fixed_bit_field (op0, offset, bitsize, bitpos, value); 77718334Speter return value; 77818334Speter} 77918334Speter 78018334Speter/* Use shifts and boolean operations to store VALUE 78118334Speter into a bit field of width BITSIZE 78218334Speter in a memory location specified by OP0 except offset by OFFSET bytes. 78318334Speter (OFFSET must be 0 if OP0 is a register.) 78418334Speter The field starts at position BITPOS within the byte. 78518334Speter (If OP0 is a register, it may be a full word or a narrower mode, 78618334Speter but BITPOS still counts within a full word, 787169689Skan which is significant on bigendian machines.) */ 78818334Speter 78918334Speterstatic void 790132718Skanstore_fixed_bit_field (rtx op0, unsigned HOST_WIDE_INT offset, 791132718Skan unsigned HOST_WIDE_INT bitsize, 792132718Skan unsigned HOST_WIDE_INT bitpos, rtx value) 79318334Speter{ 79490075Sobrien enum machine_mode mode; 79590075Sobrien unsigned int total_bits = BITS_PER_WORD; 796169689Skan rtx temp; 79718334Speter int all_zero = 0; 79818334Speter int all_one = 0; 79918334Speter 80018334Speter /* There is a case not handled here: 80118334Speter a structure with a known alignment of just a halfword 80218334Speter and a field split across two aligned halfwords within the structure. 80318334Speter Or likewise a structure with a known alignment of just a byte 80418334Speter and a field split across two bytes. 80518334Speter Such cases are not supposed to be able to occur. */ 80618334Speter 807169689Skan if (REG_P (op0) || GET_CODE (op0) == SUBREG) 80818334Speter { 809169689Skan gcc_assert (!offset); 81018334Speter /* Special treatment for a bit field split across two registers. */ 81118334Speter if (bitsize + bitpos > BITS_PER_WORD) 81218334Speter { 81390075Sobrien store_split_bit_field (op0, bitsize, bitpos, value); 81418334Speter return; 81518334Speter } 81618334Speter } 81718334Speter else 81818334Speter { 81918334Speter /* Get the proper mode to use for this field. We want a mode that 82018334Speter includes the entire field. If such a mode would be larger than 82196263Sobrien a word, we won't be doing the extraction the normal way. 82290075Sobrien We don't want a mode bigger than the destination. */ 82318334Speter 82490075Sobrien mode = GET_MODE (op0); 82590075Sobrien if (GET_MODE_BITSIZE (mode) == 0 826117395Skan || GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (word_mode)) 827117395Skan mode = word_mode; 82818334Speter mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT, 82990075Sobrien MEM_ALIGN (op0), mode, MEM_VOLATILE_P (op0)); 83018334Speter 83118334Speter if (mode == VOIDmode) 83218334Speter { 83318334Speter /* The only way this should occur is if the field spans word 83418334Speter boundaries. */ 83590075Sobrien store_split_bit_field (op0, bitsize, bitpos + offset * BITS_PER_UNIT, 83690075Sobrien value); 83718334Speter return; 83818334Speter } 83918334Speter 84018334Speter total_bits = GET_MODE_BITSIZE (mode); 84118334Speter 84218334Speter /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to 84350397Sobrien be in the range 0 to total_bits-1, and put any excess bytes in 84418334Speter OFFSET. */ 84518334Speter if (bitpos >= total_bits) 84618334Speter { 84718334Speter offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT); 84818334Speter bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT) 84918334Speter * BITS_PER_UNIT); 85018334Speter } 85118334Speter 85218334Speter /* Get ref to an aligned byte, halfword, or word containing the field. 85318334Speter Adjust BITPOS to be position within a word, 85418334Speter and OFFSET to be the offset of that word. 85518334Speter Then alter OP0 to refer to that word. */ 85618334Speter bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT; 85718334Speter offset -= (offset % (total_bits / BITS_PER_UNIT)); 85890075Sobrien op0 = adjust_address (op0, mode, offset); 85918334Speter } 86018334Speter 86118334Speter mode = GET_MODE (op0); 86218334Speter 86318334Speter /* Now MODE is either some integral mode for a MEM as OP0, 86418334Speter or is a full-word for a REG as OP0. TOTAL_BITS corresponds. 86518334Speter The bit field is contained entirely within OP0. 86618334Speter BITPOS is the starting bit number within OP0. 86718334Speter (OP0's mode may actually be narrower than MODE.) */ 86818334Speter 86918334Speter if (BYTES_BIG_ENDIAN) 87018334Speter /* BITPOS is the distance between our msb 87118334Speter and that of the containing datum. 87218334Speter Convert it to the distance from the lsb. */ 87318334Speter bitpos = total_bits - bitsize - bitpos; 87418334Speter 87518334Speter /* Now BITPOS is always the distance between our lsb 87618334Speter and that of OP0. */ 87718334Speter 87818334Speter /* Shift VALUE left by BITPOS bits. If VALUE is not constant, 87918334Speter we must first convert its mode to MODE. */ 88018334Speter 88118334Speter if (GET_CODE (value) == CONST_INT) 88218334Speter { 88390075Sobrien HOST_WIDE_INT v = INTVAL (value); 88418334Speter 88518334Speter if (bitsize < HOST_BITS_PER_WIDE_INT) 88618334Speter v &= ((HOST_WIDE_INT) 1 << bitsize) - 1; 88718334Speter 88818334Speter if (v == 0) 88918334Speter all_zero = 1; 89018334Speter else if ((bitsize < HOST_BITS_PER_WIDE_INT 89118334Speter && v == ((HOST_WIDE_INT) 1 << bitsize) - 1) 89218334Speter || (bitsize == HOST_BITS_PER_WIDE_INT && v == -1)) 89318334Speter all_one = 1; 89418334Speter 89518334Speter value = lshift_value (mode, value, bitpos, bitsize); 89618334Speter } 89718334Speter else 89818334Speter { 89918334Speter int must_and = (GET_MODE_BITSIZE (GET_MODE (value)) != bitsize 90018334Speter && bitpos + bitsize != GET_MODE_BITSIZE (mode)); 90118334Speter 90218334Speter if (GET_MODE (value) != mode) 90318334Speter { 904169689Skan if ((REG_P (value) || GET_CODE (value) == SUBREG) 90518334Speter && GET_MODE_SIZE (mode) < GET_MODE_SIZE (GET_MODE (value))) 90618334Speter value = gen_lowpart (mode, value); 90718334Speter else 90818334Speter value = convert_to_mode (mode, value, 1); 90918334Speter } 91018334Speter 91118334Speter if (must_and) 91218334Speter value = expand_binop (mode, and_optab, value, 91318334Speter mask_rtx (mode, 0, bitsize, 0), 91418334Speter NULL_RTX, 1, OPTAB_LIB_WIDEN); 91518334Speter if (bitpos > 0) 91618334Speter value = expand_shift (LSHIFT_EXPR, mode, value, 917169689Skan build_int_cst (NULL_TREE, bitpos), NULL_RTX, 1); 91818334Speter } 91918334Speter 92018334Speter /* Now clear the chosen bits in OP0, 92118334Speter except that if VALUE is -1 we need not bother. */ 922169689Skan /* We keep the intermediates in registers to allow CSE to combine 923169689Skan consecutive bitfield assignments. */ 92418334Speter 925169689Skan temp = force_reg (mode, op0); 92618334Speter 92718334Speter if (! all_one) 92818334Speter { 929169689Skan temp = expand_binop (mode, and_optab, temp, 93018334Speter mask_rtx (mode, bitpos, bitsize, 1), 931169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 932169689Skan temp = force_reg (mode, temp); 93318334Speter } 93418334Speter 93518334Speter /* Now logical-or VALUE into OP0, unless it is zero. */ 93618334Speter 93718334Speter if (! all_zero) 938169689Skan { 939169689Skan temp = expand_binop (mode, ior_optab, temp, value, 940169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 941169689Skan temp = force_reg (mode, temp); 942169689Skan } 943169689Skan 94418334Speter if (op0 != temp) 94518334Speter emit_move_insn (op0, temp); 94618334Speter} 94718334Speter 94818334Speter/* Store a bit field that is split across multiple accessible memory objects. 94918334Speter 95018334Speter OP0 is the REG, SUBREG or MEM rtx for the first of the objects. 95118334Speter BITSIZE is the field width; BITPOS the position of its first bit 95218334Speter (within the word). 95318334Speter VALUE is the value to store. 95418334Speter 95518334Speter This does not yet handle fields wider than BITS_PER_WORD. */ 95618334Speter 95718334Speterstatic void 958132718Skanstore_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 959132718Skan unsigned HOST_WIDE_INT bitpos, rtx value) 96018334Speter{ 96190075Sobrien unsigned int unit; 96290075Sobrien unsigned int bitsdone = 0; 96318334Speter 96418334Speter /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that 96518334Speter much at a time. */ 966169689Skan if (REG_P (op0) || GET_CODE (op0) == SUBREG) 96718334Speter unit = BITS_PER_WORD; 96818334Speter else 96990075Sobrien unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD); 97018334Speter 97118334Speter /* If VALUE is a constant other than a CONST_INT, get it into a register in 97218334Speter WORD_MODE. If we can do this using gen_lowpart_common, do so. Note 97318334Speter that VALUE might be a floating-point constant. */ 97418334Speter if (CONSTANT_P (value) && GET_CODE (value) != CONST_INT) 97518334Speter { 97618334Speter rtx word = gen_lowpart_common (word_mode, value); 97718334Speter 97818334Speter if (word && (value != word)) 97918334Speter value = word; 98018334Speter else 98118334Speter value = gen_lowpart_common (word_mode, 98218334Speter force_reg (GET_MODE (value) != VOIDmode 98318334Speter ? GET_MODE (value) 98418334Speter : word_mode, value)); 98518334Speter } 98618334Speter 98718334Speter while (bitsdone < bitsize) 98818334Speter { 98990075Sobrien unsigned HOST_WIDE_INT thissize; 99018334Speter rtx part, word; 99190075Sobrien unsigned HOST_WIDE_INT thispos; 99290075Sobrien unsigned HOST_WIDE_INT offset; 99318334Speter 99418334Speter offset = (bitpos + bitsdone) / unit; 99518334Speter thispos = (bitpos + bitsdone) % unit; 99618334Speter 99718334Speter /* THISSIZE must not overrun a word boundary. Otherwise, 99818334Speter store_fixed_bit_field will call us again, and we will mutually 99918334Speter recurse forever. */ 100018334Speter thissize = MIN (bitsize - bitsdone, BITS_PER_WORD); 100118334Speter thissize = MIN (thissize, unit - thispos); 100218334Speter 100318334Speter if (BYTES_BIG_ENDIAN) 100418334Speter { 100518334Speter int total_bits; 100618334Speter 100718334Speter /* We must do an endian conversion exactly the same way as it is 100818334Speter done in extract_bit_field, so that the two calls to 100918334Speter extract_fixed_bit_field will have comparable arguments. */ 1010169689Skan if (!MEM_P (value) || GET_MODE (value) == BLKmode) 101118334Speter total_bits = BITS_PER_WORD; 101218334Speter else 101318334Speter total_bits = GET_MODE_BITSIZE (GET_MODE (value)); 101418334Speter 101518334Speter /* Fetch successively less significant portions. */ 101618334Speter if (GET_CODE (value) == CONST_INT) 101718334Speter part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value)) 101818334Speter >> (bitsize - bitsdone - thissize)) 101918334Speter & (((HOST_WIDE_INT) 1 << thissize) - 1)); 102018334Speter else 102118334Speter /* The args are chosen so that the last part includes the 102218334Speter lsb. Give extract_bit_field the value it needs (with 102390075Sobrien endianness compensation) to fetch the piece we want. */ 102490075Sobrien part = extract_fixed_bit_field (word_mode, value, 0, thissize, 102590075Sobrien total_bits - bitsize + bitsdone, 102690075Sobrien NULL_RTX, 1); 102718334Speter } 102818334Speter else 102918334Speter { 103018334Speter /* Fetch successively more significant portions. */ 103118334Speter if (GET_CODE (value) == CONST_INT) 103218334Speter part = GEN_INT (((unsigned HOST_WIDE_INT) (INTVAL (value)) 103318334Speter >> bitsdone) 103418334Speter & (((HOST_WIDE_INT) 1 << thissize) - 1)); 103518334Speter else 103690075Sobrien part = extract_fixed_bit_field (word_mode, value, 0, thissize, 103790075Sobrien bitsdone, NULL_RTX, 1); 103818334Speter } 103918334Speter 104018334Speter /* If OP0 is a register, then handle OFFSET here. 104118334Speter 104218334Speter When handling multiword bitfields, extract_bit_field may pass 104318334Speter down a word_mode SUBREG of a larger REG for a bitfield that actually 104418334Speter crosses a word boundary. Thus, for a SUBREG, we must find 104518334Speter the current word starting from the base register. */ 104618334Speter if (GET_CODE (op0) == SUBREG) 104718334Speter { 104890075Sobrien int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset; 104990075Sobrien word = operand_subword_force (SUBREG_REG (op0), word_offset, 105018334Speter GET_MODE (SUBREG_REG (op0))); 105118334Speter offset = 0; 105218334Speter } 1053169689Skan else if (REG_P (op0)) 105418334Speter { 105518334Speter word = operand_subword_force (op0, offset, GET_MODE (op0)); 105618334Speter offset = 0; 105718334Speter } 105818334Speter else 105918334Speter word = op0; 106018334Speter 106118334Speter /* OFFSET is in UNITs, and UNIT is in bits. 106218334Speter store_fixed_bit_field wants offset in bytes. */ 106390075Sobrien store_fixed_bit_field (word, offset * unit / BITS_PER_UNIT, thissize, 106490075Sobrien thispos, part); 106518334Speter bitsdone += thissize; 106618334Speter } 106718334Speter} 106818334Speter 106918334Speter/* Generate code to extract a byte-field from STR_RTX 107018334Speter containing BITSIZE bits, starting at BITNUM, 107118334Speter and put it in TARGET if possible (if TARGET is nonzero). 107218334Speter Regardless of TARGET, we return the rtx for where the value is placed. 107318334Speter 107418334Speter STR_RTX is the structure containing the byte (a REG or MEM). 107518334Speter UNSIGNEDP is nonzero if this is an unsigned bit field. 107618334Speter MODE is the natural mode of the field value once extracted. 107718334Speter TMODE is the mode the caller would like the value to have; 107818334Speter but the value may be returned with type MODE instead. 107918334Speter 108018334Speter TOTAL_SIZE is the size in bytes of the containing structure, 108118334Speter or -1 if varying. 108218334Speter 108318334Speter If a TARGET is specified and we can store in it at no extra cost, 108418334Speter we do so, and return TARGET. 108518334Speter Otherwise, we return a REG of mode TMODE or MODE, with TMODE preferred 108618334Speter if they are equally easy. */ 108718334Speter 108818334Speterrtx 1089132718Skanextract_bit_field (rtx str_rtx, unsigned HOST_WIDE_INT bitsize, 1090132718Skan unsigned HOST_WIDE_INT bitnum, int unsignedp, rtx target, 1091169689Skan enum machine_mode mode, enum machine_mode tmode) 109218334Speter{ 109390075Sobrien unsigned int unit 1094169689Skan = (MEM_P (str_rtx)) ? BITS_PER_UNIT : BITS_PER_WORD; 1095169689Skan unsigned HOST_WIDE_INT offset, bitpos; 109690075Sobrien rtx op0 = str_rtx; 109718334Speter rtx spec_target = target; 109818334Speter rtx spec_target_subreg = 0; 109990075Sobrien enum machine_mode int_mode; 110090075Sobrien enum machine_mode extv_mode = mode_for_extraction (EP_extv, 0); 110190075Sobrien enum machine_mode extzv_mode = mode_for_extraction (EP_extzv, 0); 110290075Sobrien enum machine_mode mode1; 110390075Sobrien int byte_offset; 110418334Speter 110518334Speter if (tmode == VOIDmode) 110618334Speter tmode = mode; 1107117395Skan 110818334Speter while (GET_CODE (op0) == SUBREG) 110918334Speter { 1110169689Skan bitnum += SUBREG_BYTE (op0) * BITS_PER_UNIT; 111118334Speter op0 = SUBREG_REG (op0); 111218334Speter } 111318334Speter 1114169689Skan /* If we have an out-of-bounds access to a register, just return an 1115169689Skan uninitialized register of the required mode. This can occur if the 1116169689Skan source code contains an out-of-bounds access to a small array. */ 1117169689Skan if (REG_P (op0) && bitnum >= GET_MODE_BITSIZE (GET_MODE (op0))) 1118169689Skan return gen_reg_rtx (tmode); 1119169689Skan 1120169689Skan if (REG_P (op0) 112190075Sobrien && mode == GET_MODE (op0) 112290075Sobrien && bitnum == 0 112390075Sobrien && bitsize == GET_MODE_BITSIZE (GET_MODE (op0))) 112490075Sobrien { 112590075Sobrien /* We're trying to extract a full register from itself. */ 112690075Sobrien return op0; 112790075Sobrien } 112890075Sobrien 1129132718Skan /* Use vec_extract patterns for extracting parts of vectors whenever 1130132718Skan available. */ 1131132718Skan if (VECTOR_MODE_P (GET_MODE (op0)) 1132169689Skan && !MEM_P (op0) 1133169689Skan && (vec_extract_optab->handlers[GET_MODE (op0)].insn_code 1134132718Skan != CODE_FOR_nothing) 1135169689Skan && ((bitnum + bitsize - 1) / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))) 1136169689Skan == bitnum / GET_MODE_BITSIZE (GET_MODE_INNER (GET_MODE (op0))))) 1137132718Skan { 1138132718Skan enum machine_mode outermode = GET_MODE (op0); 1139132718Skan enum machine_mode innermode = GET_MODE_INNER (outermode); 1140169689Skan int icode = (int) vec_extract_optab->handlers[outermode].insn_code; 1141169689Skan unsigned HOST_WIDE_INT pos = bitnum / GET_MODE_BITSIZE (innermode); 1142132718Skan rtx rtxpos = GEN_INT (pos); 1143132718Skan rtx src = op0; 1144132718Skan rtx dest = NULL, pat, seq; 1145132718Skan enum machine_mode mode0 = insn_data[icode].operand[0].mode; 1146132718Skan enum machine_mode mode1 = insn_data[icode].operand[1].mode; 1147132718Skan enum machine_mode mode2 = insn_data[icode].operand[2].mode; 1148132718Skan 1149132718Skan if (innermode == tmode || innermode == mode) 1150132718Skan dest = target; 1151132718Skan 1152132718Skan if (!dest) 1153132718Skan dest = gen_reg_rtx (innermode); 1154132718Skan 1155132718Skan start_sequence (); 1156132718Skan 1157132718Skan if (! (*insn_data[icode].operand[0].predicate) (dest, mode0)) 1158132718Skan dest = copy_to_mode_reg (mode0, dest); 1159132718Skan 1160132718Skan if (! (*insn_data[icode].operand[1].predicate) (src, mode1)) 1161132718Skan src = copy_to_mode_reg (mode1, src); 1162132718Skan 1163132718Skan if (! (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)) 1164132718Skan rtxpos = copy_to_mode_reg (mode1, rtxpos); 1165132718Skan 1166132718Skan /* We could handle this, but we should always be called with a pseudo 1167132718Skan for our targets and all insns should take them as outputs. */ 1168169689Skan gcc_assert ((*insn_data[icode].operand[0].predicate) (dest, mode0) 1169169689Skan && (*insn_data[icode].operand[1].predicate) (src, mode1) 1170169689Skan && (*insn_data[icode].operand[2].predicate) (rtxpos, mode2)); 1171132718Skan 1172132718Skan pat = GEN_FCN (icode) (dest, src, rtxpos); 1173132718Skan seq = get_insns (); 1174132718Skan end_sequence (); 1175132718Skan if (pat) 1176132718Skan { 1177132718Skan emit_insn (seq); 1178132718Skan emit_insn (pat); 1179132718Skan return dest; 1180132718Skan } 1181132718Skan } 1182132718Skan 118352284Sobrien /* Make sure we are playing with integral modes. Pun with subregs 118452284Sobrien if we aren't. */ 118552284Sobrien { 118652284Sobrien enum machine_mode imode = int_mode_for_mode (GET_MODE (op0)); 118752284Sobrien if (imode != GET_MODE (op0)) 118852284Sobrien { 1189169689Skan if (MEM_P (op0)) 119090075Sobrien op0 = adjust_address (op0, imode, 0); 119152284Sobrien else 1192169689Skan { 1193169689Skan gcc_assert (imode != BLKmode); 1194169689Skan op0 = gen_lowpart (imode, op0); 1195169689Skan 1196169689Skan /* If we got a SUBREG, force it into a register since we 1197169689Skan aren't going to be able to do another SUBREG on it. */ 1198169689Skan if (GET_CODE (op0) == SUBREG) 1199169689Skan op0 = force_reg (imode, op0); 1200169689Skan } 120152284Sobrien } 120252284Sobrien } 120352284Sobrien 120496263Sobrien /* We may be accessing data outside the field, which means 120596263Sobrien we can alias adjacent data. */ 1206169689Skan if (MEM_P (op0)) 120796263Sobrien { 120896263Sobrien op0 = shallow_copy_rtx (op0); 120996263Sobrien set_mem_alias_set (op0, 0); 121096263Sobrien set_mem_expr (op0, 0); 121196263Sobrien } 121296263Sobrien 1213117395Skan /* Extraction of a full-word or multi-word value from a structure 1214117395Skan in a register or aligned memory can be done with just a SUBREG. 1215117395Skan A subword value in the least significant part of a register 1216117395Skan can also be extracted with a SUBREG. For this, we need the 1217117395Skan byte offset of the value in op0. */ 121896263Sobrien 1219169689Skan bitpos = bitnum % unit; 1220169689Skan offset = bitnum / unit; 1221117395Skan byte_offset = bitpos / BITS_PER_UNIT + offset * UNITS_PER_WORD; 1222117395Skan 122318334Speter /* If OP0 is a register, BITPOS must count within a word. 122418334Speter But as we have it, it counts within whatever size OP0 now has. 122518334Speter On a bigendian machine, these are not the same, so convert. */ 122650397Sobrien if (BYTES_BIG_ENDIAN 1227169689Skan && !MEM_P (op0) 122818334Speter && unit > GET_MODE_BITSIZE (GET_MODE (op0))) 122918334Speter bitpos += unit - GET_MODE_BITSIZE (GET_MODE (op0)); 123018334Speter 1231117395Skan /* ??? We currently assume TARGET is at least as big as BITSIZE. 1232117395Skan If that's wrong, the solution is to test for it and set TARGET to 0 1233117395Skan if needed. */ 123418334Speter 1235132718Skan /* Only scalar integer modes can be converted via subregs. There is an 1236132718Skan additional problem for FP modes here in that they can have a precision 1237132718Skan which is different from the size. mode_for_size uses precision, but 1238132718Skan we want a mode based on the size, so we must avoid calling it for FP 1239132718Skan modes. */ 1240132718Skan mode1 = (SCALAR_INT_MODE_P (tmode) 1241132718Skan ? mode_for_size (bitsize, GET_MODE_CLASS (tmode), 0) 1242132718Skan : mode); 124390075Sobrien 1244132718Skan if (((bitsize >= BITS_PER_WORD && bitsize == GET_MODE_BITSIZE (mode) 1245132718Skan && bitpos % BITS_PER_WORD == 0) 1246132718Skan || (mode1 != BLKmode 1247132718Skan /* ??? The big endian test here is wrong. This is correct 1248132718Skan if the value is in a register, and if mode_for_size is not 1249132718Skan the same mode as op0. This causes us to get unnecessarily 1250132718Skan inefficient code from the Thumb port when -mbig-endian. */ 1251132718Skan && (BYTES_BIG_ENDIAN 1252132718Skan ? bitpos + bitsize == BITS_PER_WORD 1253132718Skan : bitpos == 0))) 1254169689Skan && ((!MEM_P (op0) 1255132718Skan && TRULY_NOOP_TRUNCATION (GET_MODE_BITSIZE (mode), 1256132718Skan GET_MODE_BITSIZE (GET_MODE (op0))) 1257132718Skan && GET_MODE_SIZE (mode1) != 0 1258132718Skan && byte_offset % GET_MODE_SIZE (mode1) == 0) 1259169689Skan || (MEM_P (op0) 1260132718Skan && (! SLOW_UNALIGNED_ACCESS (mode, MEM_ALIGN (op0)) 1261132718Skan || (offset * BITS_PER_UNIT % bitsize == 0 1262132718Skan && MEM_ALIGN (op0) % bitsize == 0))))) 126318334Speter { 126418334Speter if (mode1 != GET_MODE (op0)) 126518334Speter { 1266169689Skan if (MEM_P (op0)) 1267169689Skan op0 = adjust_address (op0, mode1, offset); 1268169689Skan else 126952284Sobrien { 1270169689Skan rtx sub = simplify_gen_subreg (mode1, op0, GET_MODE (op0), 1271169689Skan byte_offset); 1272169689Skan if (sub == NULL) 1273107590Sobrien goto no_subreg_mode_swap; 1274169689Skan op0 = sub; 127552284Sobrien } 127618334Speter } 127718334Speter if (mode1 != mode) 127818334Speter return convert_to_mode (tmode, op0, unsignedp); 127918334Speter return op0; 128018334Speter } 1281107590Sobrien no_subreg_mode_swap: 128218334Speter 128318334Speter /* Handle fields bigger than a word. */ 128496263Sobrien 128518334Speter if (bitsize > BITS_PER_WORD) 128618334Speter { 128718334Speter /* Here we transfer the words of the field 128818334Speter in the order least significant first. 128918334Speter This is because the most significant word is the one which may 129018334Speter be less than full. */ 129118334Speter 129290075Sobrien unsigned int nwords = (bitsize + (BITS_PER_WORD - 1)) / BITS_PER_WORD; 129390075Sobrien unsigned int i; 129418334Speter 1295169689Skan if (target == 0 || !REG_P (target)) 129618334Speter target = gen_reg_rtx (mode); 129718334Speter 129850397Sobrien /* Indicate for flow that the entire target reg is being set. */ 129950397Sobrien emit_insn (gen_rtx_CLOBBER (VOIDmode, target)); 130050397Sobrien 130118334Speter for (i = 0; i < nwords; i++) 130218334Speter { 130318334Speter /* If I is 0, use the low-order word in both field and target; 130418334Speter if I is 1, use the next to lowest word; and so on. */ 130518334Speter /* Word number in TARGET to use. */ 130690075Sobrien unsigned int wordnum 130790075Sobrien = (WORDS_BIG_ENDIAN 130890075Sobrien ? GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD - i - 1 130990075Sobrien : i); 131018334Speter /* Offset from start of field in OP0. */ 131190075Sobrien unsigned int bit_offset = (WORDS_BIG_ENDIAN 131290075Sobrien ? MAX (0, ((int) bitsize - ((int) i + 1) 131390075Sobrien * (int) BITS_PER_WORD)) 131490075Sobrien : (int) i * BITS_PER_WORD); 131518334Speter rtx target_part = operand_subword (target, wordnum, 1, VOIDmode); 131618334Speter rtx result_part 131718334Speter = extract_bit_field (op0, MIN (BITS_PER_WORD, 131818334Speter bitsize - i * BITS_PER_WORD), 131990075Sobrien bitnum + bit_offset, 1, target_part, mode, 1320169689Skan word_mode); 132118334Speter 1322169689Skan gcc_assert (target_part); 132318334Speter 132418334Speter if (result_part != target_part) 132518334Speter emit_move_insn (target_part, result_part); 132618334Speter } 132718334Speter 132818334Speter if (unsignedp) 132918334Speter { 133018334Speter /* Unless we've filled TARGET, the upper regs in a multi-reg value 133118334Speter need to be zero'd out. */ 133218334Speter if (GET_MODE_SIZE (GET_MODE (target)) > nwords * UNITS_PER_WORD) 133318334Speter { 133490075Sobrien unsigned int i, total_words; 133518334Speter 133618334Speter total_words = GET_MODE_SIZE (GET_MODE (target)) / UNITS_PER_WORD; 133718334Speter for (i = nwords; i < total_words; i++) 133890075Sobrien emit_move_insn 133990075Sobrien (operand_subword (target, 134090075Sobrien WORDS_BIG_ENDIAN ? total_words - i - 1 : i, 134190075Sobrien 1, VOIDmode), 134290075Sobrien const0_rtx); 134318334Speter } 134418334Speter return target; 134518334Speter } 134618334Speter 134718334Speter /* Signed bit field: sign-extend with two arithmetic shifts. */ 134818334Speter target = expand_shift (LSHIFT_EXPR, mode, target, 1349169689Skan build_int_cst (NULL_TREE, 1350169689Skan GET_MODE_BITSIZE (mode) - bitsize), 135118334Speter NULL_RTX, 0); 135218334Speter return expand_shift (RSHIFT_EXPR, mode, target, 1353169689Skan build_int_cst (NULL_TREE, 1354169689Skan GET_MODE_BITSIZE (mode) - bitsize), 135518334Speter NULL_RTX, 0); 135618334Speter } 135796263Sobrien 135890075Sobrien /* From here on we know the desired field is smaller than a word. */ 135918334Speter 136090075Sobrien /* Check if there is a correspondingly-sized integer field, so we can 136190075Sobrien safely extract it as one size of integer, if necessary; then 136290075Sobrien truncate or extend to the size that is wanted; then use SUBREGs or 136390075Sobrien convert_to_mode to get one of the modes we really wanted. */ 136496263Sobrien 136590075Sobrien int_mode = int_mode_for_mode (tmode); 136690075Sobrien if (int_mode == BLKmode) 136790075Sobrien int_mode = int_mode_for_mode (mode); 1368169689Skan /* Should probably push op0 out to memory and then do a load. */ 1369169689Skan gcc_assert (int_mode != BLKmode); 137090075Sobrien 137118334Speter /* OFFSET is the number of words or bytes (UNIT says which) 137218334Speter from STR_RTX to the first word or byte containing part of the field. */ 1373169689Skan if (!MEM_P (op0)) 137418334Speter { 137518334Speter if (offset != 0 137618334Speter || GET_MODE_SIZE (GET_MODE (op0)) > UNITS_PER_WORD) 137752284Sobrien { 1378169689Skan if (!REG_P (op0)) 137952284Sobrien op0 = copy_to_reg (op0); 138052284Sobrien op0 = gen_rtx_SUBREG (mode_for_size (BITS_PER_WORD, MODE_INT, 0), 138190075Sobrien op0, (offset * UNITS_PER_WORD)); 138252284Sobrien } 138318334Speter offset = 0; 138418334Speter } 138518334Speter 138618334Speter /* Now OFFSET is nonzero only for memory operands. */ 138718334Speter 138818334Speter if (unsignedp) 138918334Speter { 139018334Speter if (HAVE_extzv 1391169689Skan && bitsize > 0 1392169689Skan && GET_MODE_BITSIZE (extzv_mode) >= bitsize 1393169689Skan && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 139490075Sobrien && (bitsize + bitpos > GET_MODE_BITSIZE (extzv_mode)))) 139518334Speter { 139690075Sobrien unsigned HOST_WIDE_INT xbitpos = bitpos, xoffset = offset; 139718334Speter rtx bitsize_rtx, bitpos_rtx; 139850397Sobrien rtx last = get_last_insn (); 139918334Speter rtx xop0 = op0; 140018334Speter rtx xtarget = target; 140118334Speter rtx xspec_target = spec_target; 140218334Speter rtx xspec_target_subreg = spec_target_subreg; 140318334Speter rtx pat; 140490075Sobrien enum machine_mode maxmode = mode_for_extraction (EP_extzv, 0); 140518334Speter 1406169689Skan if (MEM_P (xop0)) 140718334Speter { 140818334Speter int save_volatile_ok = volatile_ok; 140918334Speter volatile_ok = 1; 141018334Speter 141118334Speter /* Is the memory operand acceptable? */ 141290075Sobrien if (! ((*insn_data[(int) CODE_FOR_extzv].operand[1].predicate) 141350397Sobrien (xop0, GET_MODE (xop0)))) 141418334Speter { 141518334Speter /* No, load into a reg and extract from there. */ 141618334Speter enum machine_mode bestmode; 141718334Speter 141818334Speter /* Get the mode to use for inserting into this field. If 141918334Speter OP0 is BLKmode, get the smallest mode consistent with the 142018334Speter alignment. If OP0 is a non-BLKmode object that is no 142118334Speter wider than MAXMODE, use its mode. Otherwise, use the 142218334Speter smallest mode containing the field. */ 142318334Speter 142418334Speter if (GET_MODE (xop0) == BLKmode 142518334Speter || (GET_MODE_SIZE (GET_MODE (op0)) 142618334Speter > GET_MODE_SIZE (maxmode))) 142718334Speter bestmode = get_best_mode (bitsize, bitnum, 142890075Sobrien MEM_ALIGN (xop0), maxmode, 142918334Speter MEM_VOLATILE_P (xop0)); 143018334Speter else 143118334Speter bestmode = GET_MODE (xop0); 143218334Speter 143318334Speter if (bestmode == VOIDmode 143490075Sobrien || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0)) 143590075Sobrien && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0))) 143618334Speter goto extzv_loses; 143718334Speter 143818334Speter /* Compute offset as multiple of this unit, 143918334Speter counting in bytes. */ 144018334Speter unit = GET_MODE_BITSIZE (bestmode); 144118334Speter xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 144218334Speter xbitpos = bitnum % unit; 144390075Sobrien xop0 = adjust_address (xop0, bestmode, xoffset); 144490075Sobrien 1445161651Skan /* Make sure register is big enough for the whole field. */ 1446161651Skan if (xoffset * BITS_PER_UNIT + unit 1447161651Skan < offset * BITS_PER_UNIT + bitsize) 1448161651Skan goto extzv_loses; 1449161651Skan 145018334Speter /* Fetch it to a register in that size. */ 145118334Speter xop0 = force_reg (bestmode, xop0); 145218334Speter 145318334Speter /* XBITPOS counts within UNIT, which is what is expected. */ 145418334Speter } 145518334Speter else 145618334Speter /* Get ref to first byte containing part of the field. */ 145790075Sobrien xop0 = adjust_address (xop0, byte_mode, xoffset); 145818334Speter 145918334Speter volatile_ok = save_volatile_ok; 146018334Speter } 146118334Speter 146218334Speter /* If op0 is a register, we need it in MAXMODE (which is usually 146318334Speter SImode). to make it acceptable to the format of extzv. */ 146418334Speter if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode) 146550397Sobrien goto extzv_loses; 1466169689Skan if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 146750397Sobrien xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 146818334Speter 146918334Speter /* On big-endian machines, we count bits from the most significant. 147018334Speter If the bit field insn does not, we must invert. */ 147118334Speter if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 147218334Speter xbitpos = unit - bitsize - xbitpos; 147318334Speter 147418334Speter /* Now convert from counting within UNIT to counting in MAXMODE. */ 1475169689Skan if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 147618334Speter xbitpos += GET_MODE_BITSIZE (maxmode) - unit; 147718334Speter 147818334Speter unit = GET_MODE_BITSIZE (maxmode); 147918334Speter 1480169689Skan if (xtarget == 0) 148118334Speter xtarget = xspec_target = gen_reg_rtx (tmode); 148218334Speter 148318334Speter if (GET_MODE (xtarget) != maxmode) 148418334Speter { 1485169689Skan if (REG_P (xtarget)) 148618334Speter { 148718334Speter int wider = (GET_MODE_SIZE (maxmode) 148818334Speter > GET_MODE_SIZE (GET_MODE (xtarget))); 148918334Speter xtarget = gen_lowpart (maxmode, xtarget); 149018334Speter if (wider) 149118334Speter xspec_target_subreg = xtarget; 149218334Speter } 149318334Speter else 149418334Speter xtarget = gen_reg_rtx (maxmode); 149518334Speter } 149618334Speter 149718334Speter /* If this machine's extzv insists on a register target, 149818334Speter make sure we have one. */ 149990075Sobrien if (! ((*insn_data[(int) CODE_FOR_extzv].operand[0].predicate) 150018334Speter (xtarget, maxmode))) 150118334Speter xtarget = gen_reg_rtx (maxmode); 150218334Speter 150318334Speter bitsize_rtx = GEN_INT (bitsize); 150418334Speter bitpos_rtx = GEN_INT (xbitpos); 150518334Speter 1506169689Skan pat = gen_extzv (xtarget, xop0, bitsize_rtx, bitpos_rtx); 150718334Speter if (pat) 150818334Speter { 150918334Speter emit_insn (pat); 151018334Speter target = xtarget; 151118334Speter spec_target = xspec_target; 151218334Speter spec_target_subreg = xspec_target_subreg; 151318334Speter } 151418334Speter else 151518334Speter { 151618334Speter delete_insns_since (last); 151790075Sobrien target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 151890075Sobrien bitpos, target, 1); 151918334Speter } 152018334Speter } 152118334Speter else 152290075Sobrien extzv_loses: 152396263Sobrien target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 152490075Sobrien bitpos, target, 1); 152518334Speter } 152618334Speter else 152718334Speter { 152818334Speter if (HAVE_extv 1529169689Skan && bitsize > 0 1530169689Skan && GET_MODE_BITSIZE (extv_mode) >= bitsize 1531169689Skan && ! ((REG_P (op0) || GET_CODE (op0) == SUBREG) 153290075Sobrien && (bitsize + bitpos > GET_MODE_BITSIZE (extv_mode)))) 153318334Speter { 153418334Speter int xbitpos = bitpos, xoffset = offset; 153518334Speter rtx bitsize_rtx, bitpos_rtx; 153650397Sobrien rtx last = get_last_insn (); 153718334Speter rtx xop0 = op0, xtarget = target; 153818334Speter rtx xspec_target = spec_target; 153918334Speter rtx xspec_target_subreg = spec_target_subreg; 154018334Speter rtx pat; 154190075Sobrien enum machine_mode maxmode = mode_for_extraction (EP_extv, 0); 154218334Speter 1543169689Skan if (MEM_P (xop0)) 154418334Speter { 154518334Speter /* Is the memory operand acceptable? */ 154690075Sobrien if (! ((*insn_data[(int) CODE_FOR_extv].operand[1].predicate) 154718334Speter (xop0, GET_MODE (xop0)))) 154818334Speter { 154918334Speter /* No, load into a reg and extract from there. */ 155018334Speter enum machine_mode bestmode; 155118334Speter 155218334Speter /* Get the mode to use for inserting into this field. If 155318334Speter OP0 is BLKmode, get the smallest mode consistent with the 155418334Speter alignment. If OP0 is a non-BLKmode object that is no 155518334Speter wider than MAXMODE, use its mode. Otherwise, use the 155618334Speter smallest mode containing the field. */ 155718334Speter 155818334Speter if (GET_MODE (xop0) == BLKmode 155918334Speter || (GET_MODE_SIZE (GET_MODE (op0)) 156018334Speter > GET_MODE_SIZE (maxmode))) 156118334Speter bestmode = get_best_mode (bitsize, bitnum, 156290075Sobrien MEM_ALIGN (xop0), maxmode, 156318334Speter MEM_VOLATILE_P (xop0)); 156418334Speter else 156518334Speter bestmode = GET_MODE (xop0); 156618334Speter 156718334Speter if (bestmode == VOIDmode 156890075Sobrien || (SLOW_UNALIGNED_ACCESS (bestmode, MEM_ALIGN (xop0)) 156990075Sobrien && GET_MODE_BITSIZE (bestmode) > MEM_ALIGN (xop0))) 157018334Speter goto extv_loses; 157118334Speter 157218334Speter /* Compute offset as multiple of this unit, 157318334Speter counting in bytes. */ 157418334Speter unit = GET_MODE_BITSIZE (bestmode); 157518334Speter xoffset = (bitnum / unit) * GET_MODE_SIZE (bestmode); 157618334Speter xbitpos = bitnum % unit; 157790075Sobrien xop0 = adjust_address (xop0, bestmode, xoffset); 157890075Sobrien 1579161651Skan /* Make sure register is big enough for the whole field. */ 1580161651Skan if (xoffset * BITS_PER_UNIT + unit 1581161651Skan < offset * BITS_PER_UNIT + bitsize) 1582161651Skan goto extv_loses; 1583161651Skan 158418334Speter /* Fetch it to a register in that size. */ 158518334Speter xop0 = force_reg (bestmode, xop0); 158618334Speter 158718334Speter /* XBITPOS counts within UNIT, which is what is expected. */ 158818334Speter } 158918334Speter else 159018334Speter /* Get ref to first byte containing part of the field. */ 159190075Sobrien xop0 = adjust_address (xop0, byte_mode, xoffset); 159218334Speter } 159318334Speter 159418334Speter /* If op0 is a register, we need it in MAXMODE (which is usually 159518334Speter SImode) to make it acceptable to the format of extv. */ 159618334Speter if (GET_CODE (xop0) == SUBREG && GET_MODE (xop0) != maxmode) 159750397Sobrien goto extv_loses; 1598169689Skan if (REG_P (xop0) && GET_MODE (xop0) != maxmode) 159950397Sobrien xop0 = gen_rtx_SUBREG (maxmode, xop0, 0); 160018334Speter 160118334Speter /* On big-endian machines, we count bits from the most significant. 160218334Speter If the bit field insn does not, we must invert. */ 160318334Speter if (BITS_BIG_ENDIAN != BYTES_BIG_ENDIAN) 160418334Speter xbitpos = unit - bitsize - xbitpos; 160518334Speter 160618334Speter /* XBITPOS counts within a size of UNIT. 160718334Speter Adjust to count within a size of MAXMODE. */ 1608169689Skan if (BITS_BIG_ENDIAN && !MEM_P (xop0)) 160918334Speter xbitpos += (GET_MODE_BITSIZE (maxmode) - unit); 161018334Speter 161118334Speter unit = GET_MODE_BITSIZE (maxmode); 161218334Speter 1613169689Skan if (xtarget == 0) 161418334Speter xtarget = xspec_target = gen_reg_rtx (tmode); 161518334Speter 161618334Speter if (GET_MODE (xtarget) != maxmode) 161718334Speter { 1618169689Skan if (REG_P (xtarget)) 161918334Speter { 162018334Speter int wider = (GET_MODE_SIZE (maxmode) 162118334Speter > GET_MODE_SIZE (GET_MODE (xtarget))); 162218334Speter xtarget = gen_lowpart (maxmode, xtarget); 162318334Speter if (wider) 162418334Speter xspec_target_subreg = xtarget; 162518334Speter } 162618334Speter else 162718334Speter xtarget = gen_reg_rtx (maxmode); 162818334Speter } 162918334Speter 163018334Speter /* If this machine's extv insists on a register target, 163118334Speter make sure we have one. */ 163290075Sobrien if (! ((*insn_data[(int) CODE_FOR_extv].operand[0].predicate) 163318334Speter (xtarget, maxmode))) 163418334Speter xtarget = gen_reg_rtx (maxmode); 163518334Speter 163618334Speter bitsize_rtx = GEN_INT (bitsize); 163718334Speter bitpos_rtx = GEN_INT (xbitpos); 163818334Speter 1639169689Skan pat = gen_extv (xtarget, xop0, bitsize_rtx, bitpos_rtx); 164018334Speter if (pat) 164118334Speter { 164218334Speter emit_insn (pat); 164318334Speter target = xtarget; 164418334Speter spec_target = xspec_target; 164518334Speter spec_target_subreg = xspec_target_subreg; 164618334Speter } 164718334Speter else 164818334Speter { 164918334Speter delete_insns_since (last); 165090075Sobrien target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 165190075Sobrien bitpos, target, 0); 165218334Speter } 165396263Sobrien } 165418334Speter else 165590075Sobrien extv_loses: 165696263Sobrien target = extract_fixed_bit_field (int_mode, op0, offset, bitsize, 165790075Sobrien bitpos, target, 0); 165818334Speter } 165918334Speter if (target == spec_target) 166018334Speter return target; 166118334Speter if (target == spec_target_subreg) 166218334Speter return spec_target; 166318334Speter if (GET_MODE (target) != tmode && GET_MODE (target) != mode) 166418334Speter { 1665169689Skan /* If the target mode is not a scalar integral, first convert to the 166618334Speter integer mode of that size and then access it as a floating-point 166718334Speter value via a SUBREG. */ 1668169689Skan if (!SCALAR_INT_MODE_P (tmode)) 166918334Speter { 1670169689Skan enum machine_mode smode 1671169689Skan = mode_for_size (GET_MODE_BITSIZE (tmode), MODE_INT, 0); 1672169689Skan target = convert_to_mode (smode, target, unsignedp); 1673169689Skan target = force_reg (smode, target); 167496263Sobrien return gen_lowpart (tmode, target); 167518334Speter } 1676169689Skan 1677169689Skan return convert_to_mode (tmode, target, unsignedp); 167818334Speter } 167918334Speter return target; 168018334Speter} 168118334Speter 168218334Speter/* Extract a bit field using shifts and boolean operations 168318334Speter Returns an rtx to represent the value. 168418334Speter OP0 addresses a register (word) or memory (byte). 168518334Speter BITPOS says which bit within the word or byte the bit field starts in. 168618334Speter OFFSET says how many bytes farther the bit field starts; 168718334Speter it is 0 if OP0 is a register. 168818334Speter BITSIZE says how many bits long the bit field is. 168918334Speter (If OP0 is a register, it may be narrower than a full word, 169018334Speter but BITPOS still counts within a full word, 169118334Speter which is significant on bigendian machines.) 169218334Speter 169318334Speter UNSIGNEDP is nonzero for an unsigned bit field (don't sign-extend value). 169418334Speter If TARGET is nonzero, attempts to store the value there 169518334Speter and return TARGET, but this is not guaranteed. 169690075Sobrien If TARGET is not used, create a pseudo-reg of mode TMODE for the value. */ 169718334Speter 169818334Speterstatic rtx 1699132718Skanextract_fixed_bit_field (enum machine_mode tmode, rtx op0, 1700132718Skan unsigned HOST_WIDE_INT offset, 1701132718Skan unsigned HOST_WIDE_INT bitsize, 1702132718Skan unsigned HOST_WIDE_INT bitpos, rtx target, 1703132718Skan int unsignedp) 170418334Speter{ 170590075Sobrien unsigned int total_bits = BITS_PER_WORD; 170618334Speter enum machine_mode mode; 170718334Speter 1708169689Skan if (GET_CODE (op0) == SUBREG || REG_P (op0)) 170918334Speter { 171018334Speter /* Special treatment for a bit field split across two registers. */ 171118334Speter if (bitsize + bitpos > BITS_PER_WORD) 171290075Sobrien return extract_split_bit_field (op0, bitsize, bitpos, unsignedp); 171318334Speter } 171418334Speter else 171518334Speter { 171618334Speter /* Get the proper mode to use for this field. We want a mode that 171718334Speter includes the entire field. If such a mode would be larger than 171818334Speter a word, we won't be doing the extraction the normal way. */ 171918334Speter 172018334Speter mode = get_best_mode (bitsize, bitpos + offset * BITS_PER_UNIT, 172190075Sobrien MEM_ALIGN (op0), word_mode, MEM_VOLATILE_P (op0)); 172218334Speter 172318334Speter if (mode == VOIDmode) 172418334Speter /* The only way this should occur is if the field spans word 172518334Speter boundaries. */ 172618334Speter return extract_split_bit_field (op0, bitsize, 172718334Speter bitpos + offset * BITS_PER_UNIT, 172890075Sobrien unsignedp); 172918334Speter 173018334Speter total_bits = GET_MODE_BITSIZE (mode); 173118334Speter 173218334Speter /* Make sure bitpos is valid for the chosen mode. Adjust BITPOS to 173350397Sobrien be in the range 0 to total_bits-1, and put any excess bytes in 173418334Speter OFFSET. */ 173518334Speter if (bitpos >= total_bits) 173618334Speter { 173718334Speter offset += (bitpos / total_bits) * (total_bits / BITS_PER_UNIT); 173818334Speter bitpos -= ((bitpos / total_bits) * (total_bits / BITS_PER_UNIT) 173918334Speter * BITS_PER_UNIT); 174018334Speter } 174118334Speter 174218334Speter /* Get ref to an aligned byte, halfword, or word containing the field. 174318334Speter Adjust BITPOS to be position within a word, 174418334Speter and OFFSET to be the offset of that word. 174518334Speter Then alter OP0 to refer to that word. */ 174618334Speter bitpos += (offset % (total_bits / BITS_PER_UNIT)) * BITS_PER_UNIT; 174718334Speter offset -= (offset % (total_bits / BITS_PER_UNIT)); 174890075Sobrien op0 = adjust_address (op0, mode, offset); 174918334Speter } 175018334Speter 175118334Speter mode = GET_MODE (op0); 175218334Speter 175318334Speter if (BYTES_BIG_ENDIAN) 175490075Sobrien /* BITPOS is the distance between our msb and that of OP0. 175590075Sobrien Convert it to the distance from the lsb. */ 175690075Sobrien bitpos = total_bits - bitsize - bitpos; 175718334Speter 175818334Speter /* Now BITPOS is always the distance between the field's lsb and that of OP0. 175918334Speter We have reduced the big-endian case to the little-endian case. */ 176018334Speter 176118334Speter if (unsignedp) 176218334Speter { 176318334Speter if (bitpos) 176418334Speter { 176518334Speter /* If the field does not already start at the lsb, 176618334Speter shift it so it does. */ 1767169689Skan tree amount = build_int_cst (NULL_TREE, bitpos); 176818334Speter /* Maybe propagate the target for the shift. */ 176918334Speter /* But not if we will return it--could confuse integrate.c. */ 1770169689Skan rtx subtarget = (target != 0 && REG_P (target) ? target : 0); 177118334Speter if (tmode != mode) subtarget = 0; 177218334Speter op0 = expand_shift (RSHIFT_EXPR, mode, op0, amount, subtarget, 1); 177318334Speter } 177418334Speter /* Convert the value to the desired mode. */ 177518334Speter if (mode != tmode) 177618334Speter op0 = convert_to_mode (tmode, op0, 1); 177718334Speter 177818334Speter /* Unless the msb of the field used to be the msb when we shifted, 177918334Speter mask out the upper bits. */ 178018334Speter 178190075Sobrien if (GET_MODE_BITSIZE (mode) != bitpos + bitsize) 178218334Speter return expand_binop (GET_MODE (op0), and_optab, op0, 178318334Speter mask_rtx (GET_MODE (op0), 0, bitsize, 0), 178418334Speter target, 1, OPTAB_LIB_WIDEN); 178518334Speter return op0; 178618334Speter } 178718334Speter 178818334Speter /* To extract a signed bit-field, first shift its msb to the msb of the word, 178918334Speter then arithmetic-shift its lsb to the lsb of the word. */ 179018334Speter op0 = force_reg (mode, op0); 179118334Speter if (mode != tmode) 179218334Speter target = 0; 179318334Speter 179418334Speter /* Find the narrowest integer mode that contains the field. */ 179518334Speter 179618334Speter for (mode = GET_CLASS_NARROWEST_MODE (MODE_INT); mode != VOIDmode; 179718334Speter mode = GET_MODE_WIDER_MODE (mode)) 179818334Speter if (GET_MODE_BITSIZE (mode) >= bitsize + bitpos) 179918334Speter { 180018334Speter op0 = convert_to_mode (mode, op0, 0); 180118334Speter break; 180218334Speter } 180318334Speter 180418334Speter if (GET_MODE_BITSIZE (mode) != (bitsize + bitpos)) 180518334Speter { 180690075Sobrien tree amount 1807169689Skan = build_int_cst (NULL_TREE, 1808169689Skan GET_MODE_BITSIZE (mode) - (bitsize + bitpos)); 180918334Speter /* Maybe propagate the target for the shift. */ 1810169689Skan rtx subtarget = (target != 0 && REG_P (target) ? target : 0); 181118334Speter op0 = expand_shift (LSHIFT_EXPR, mode, op0, amount, subtarget, 1); 181218334Speter } 181318334Speter 181418334Speter return expand_shift (RSHIFT_EXPR, mode, op0, 1815169689Skan build_int_cst (NULL_TREE, 1816169689Skan GET_MODE_BITSIZE (mode) - bitsize), 181718334Speter target, 0); 181818334Speter} 181918334Speter 182018334Speter/* Return a constant integer (CONST_INT or CONST_DOUBLE) mask value 182118334Speter of mode MODE with BITSIZE ones followed by BITPOS zeros, or the 182218334Speter complement of that if COMPLEMENT. The mask is truncated if 182318334Speter necessary to the width of mode MODE. The mask is zero-extended if 182418334Speter BITSIZE+BITPOS is too small for MODE. */ 182518334Speter 182618334Speterstatic rtx 1827132718Skanmask_rtx (enum machine_mode mode, int bitpos, int bitsize, int complement) 182818334Speter{ 182918334Speter HOST_WIDE_INT masklow, maskhigh; 183018334Speter 1831132718Skan if (bitsize == 0) 1832132718Skan masklow = 0; 1833132718Skan else if (bitpos < HOST_BITS_PER_WIDE_INT) 183418334Speter masklow = (HOST_WIDE_INT) -1 << bitpos; 183518334Speter else 183618334Speter masklow = 0; 183718334Speter 183818334Speter if (bitpos + bitsize < HOST_BITS_PER_WIDE_INT) 183918334Speter masklow &= ((unsigned HOST_WIDE_INT) -1 184018334Speter >> (HOST_BITS_PER_WIDE_INT - bitpos - bitsize)); 184196263Sobrien 184218334Speter if (bitpos <= HOST_BITS_PER_WIDE_INT) 184318334Speter maskhigh = -1; 184418334Speter else 184518334Speter maskhigh = (HOST_WIDE_INT) -1 << (bitpos - HOST_BITS_PER_WIDE_INT); 184618334Speter 1847132718Skan if (bitsize == 0) 1848132718Skan maskhigh = 0; 1849132718Skan else if (bitpos + bitsize > HOST_BITS_PER_WIDE_INT) 185018334Speter maskhigh &= ((unsigned HOST_WIDE_INT) -1 185118334Speter >> (2 * HOST_BITS_PER_WIDE_INT - bitpos - bitsize)); 185218334Speter else 185318334Speter maskhigh = 0; 185418334Speter 185518334Speter if (complement) 185618334Speter { 185718334Speter maskhigh = ~maskhigh; 185818334Speter masklow = ~masklow; 185918334Speter } 186018334Speter 186118334Speter return immed_double_const (masklow, maskhigh, mode); 186218334Speter} 186318334Speter 186418334Speter/* Return a constant integer (CONST_INT or CONST_DOUBLE) rtx with the value 186518334Speter VALUE truncated to BITSIZE bits and then shifted left BITPOS bits. */ 186618334Speter 186718334Speterstatic rtx 1868132718Skanlshift_value (enum machine_mode mode, rtx value, int bitpos, int bitsize) 186918334Speter{ 187018334Speter unsigned HOST_WIDE_INT v = INTVAL (value); 187118334Speter HOST_WIDE_INT low, high; 187218334Speter 187318334Speter if (bitsize < HOST_BITS_PER_WIDE_INT) 187418334Speter v &= ~((HOST_WIDE_INT) -1 << bitsize); 187518334Speter 187618334Speter if (bitpos < HOST_BITS_PER_WIDE_INT) 187718334Speter { 187818334Speter low = v << bitpos; 187918334Speter high = (bitpos > 0 ? (v >> (HOST_BITS_PER_WIDE_INT - bitpos)) : 0); 188018334Speter } 188118334Speter else 188218334Speter { 188318334Speter low = 0; 188418334Speter high = v << (bitpos - HOST_BITS_PER_WIDE_INT); 188518334Speter } 188618334Speter 188718334Speter return immed_double_const (low, high, mode); 188818334Speter} 188918334Speter 1890169689Skan/* Extract a bit field from a memory by forcing the alignment of the 1891169689Skan memory. This efficient only if the field spans at least 4 boundaries. 1892169689Skan 1893169689Skan OP0 is the MEM. 1894169689Skan BITSIZE is the field width; BITPOS is the position of the first bit. 1895169689Skan UNSIGNEDP is true if the result should be zero-extended. */ 1896169689Skan 1897169689Skanstatic rtx 1898169689Skanextract_force_align_mem_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 1899169689Skan unsigned HOST_WIDE_INT bitpos, 1900169689Skan int unsignedp) 1901169689Skan{ 1902169689Skan enum machine_mode mode, dmode; 1903169689Skan unsigned int m_bitsize, m_size; 1904169689Skan unsigned int sign_shift_up, sign_shift_dn; 1905169689Skan rtx base, a1, a2, v1, v2, comb, shift, result, start; 1906169689Skan 1907169689Skan /* Choose a mode that will fit BITSIZE. */ 1908169689Skan mode = smallest_mode_for_size (bitsize, MODE_INT); 1909169689Skan m_size = GET_MODE_SIZE (mode); 1910169689Skan m_bitsize = GET_MODE_BITSIZE (mode); 1911169689Skan 1912169689Skan /* Choose a mode twice as wide. Fail if no such mode exists. */ 1913169689Skan dmode = mode_for_size (m_bitsize * 2, MODE_INT, false); 1914169689Skan if (dmode == BLKmode) 1915169689Skan return NULL; 1916169689Skan 1917169689Skan do_pending_stack_adjust (); 1918169689Skan start = get_last_insn (); 1919169689Skan 1920169689Skan /* At the end, we'll need an additional shift to deal with sign/zero 1921169689Skan extension. By default this will be a left+right shift of the 1922169689Skan appropriate size. But we may be able to eliminate one of them. */ 1923169689Skan sign_shift_up = sign_shift_dn = m_bitsize - bitsize; 1924169689Skan 1925169689Skan if (STRICT_ALIGNMENT) 1926169689Skan { 1927169689Skan base = plus_constant (XEXP (op0, 0), bitpos / BITS_PER_UNIT); 1928169689Skan bitpos %= BITS_PER_UNIT; 1929169689Skan 1930169689Skan /* We load two values to be concatenate. There's an edge condition 1931169689Skan that bears notice -- an aligned value at the end of a page can 1932169689Skan only load one value lest we segfault. So the two values we load 1933169689Skan are at "base & -size" and "(base + size - 1) & -size". If base 1934169689Skan is unaligned, the addresses will be aligned and sequential; if 1935169689Skan base is aligned, the addresses will both be equal to base. */ 1936169689Skan 1937169689Skan a1 = expand_simple_binop (Pmode, AND, force_operand (base, NULL), 1938169689Skan GEN_INT (-(HOST_WIDE_INT)m_size), 1939169689Skan NULL, true, OPTAB_LIB_WIDEN); 1940169689Skan mark_reg_pointer (a1, m_bitsize); 1941169689Skan v1 = gen_rtx_MEM (mode, a1); 1942169689Skan set_mem_align (v1, m_bitsize); 1943169689Skan v1 = force_reg (mode, validize_mem (v1)); 1944169689Skan 1945169689Skan a2 = plus_constant (base, GET_MODE_SIZE (mode) - 1); 1946169689Skan a2 = expand_simple_binop (Pmode, AND, force_operand (a2, NULL), 1947169689Skan GEN_INT (-(HOST_WIDE_INT)m_size), 1948169689Skan NULL, true, OPTAB_LIB_WIDEN); 1949169689Skan v2 = gen_rtx_MEM (mode, a2); 1950169689Skan set_mem_align (v2, m_bitsize); 1951169689Skan v2 = force_reg (mode, validize_mem (v2)); 1952169689Skan 1953169689Skan /* Combine these two values into a double-word value. */ 1954169689Skan if (m_bitsize == BITS_PER_WORD) 1955169689Skan { 1956169689Skan comb = gen_reg_rtx (dmode); 1957169689Skan emit_insn (gen_rtx_CLOBBER (VOIDmode, comb)); 1958169689Skan emit_move_insn (gen_rtx_SUBREG (mode, comb, 0), v1); 1959169689Skan emit_move_insn (gen_rtx_SUBREG (mode, comb, m_size), v2); 1960169689Skan } 1961169689Skan else 1962169689Skan { 1963169689Skan if (BYTES_BIG_ENDIAN) 1964169689Skan comb = v1, v1 = v2, v2 = comb; 1965169689Skan v1 = convert_modes (dmode, mode, v1, true); 1966169689Skan if (v1 == NULL) 1967169689Skan goto fail; 1968169689Skan v2 = convert_modes (dmode, mode, v2, true); 1969169689Skan v2 = expand_simple_binop (dmode, ASHIFT, v2, GEN_INT (m_bitsize), 1970169689Skan NULL, true, OPTAB_LIB_WIDEN); 1971169689Skan if (v2 == NULL) 1972169689Skan goto fail; 1973169689Skan comb = expand_simple_binop (dmode, IOR, v1, v2, NULL, 1974169689Skan true, OPTAB_LIB_WIDEN); 1975169689Skan if (comb == NULL) 1976169689Skan goto fail; 1977169689Skan } 1978169689Skan 1979169689Skan shift = expand_simple_binop (Pmode, AND, base, GEN_INT (m_size - 1), 1980169689Skan NULL, true, OPTAB_LIB_WIDEN); 1981169689Skan shift = expand_mult (Pmode, shift, GEN_INT (BITS_PER_UNIT), NULL, 1); 1982169689Skan 1983169689Skan if (bitpos != 0) 1984169689Skan { 1985169689Skan if (sign_shift_up <= bitpos) 1986169689Skan bitpos -= sign_shift_up, sign_shift_up = 0; 1987169689Skan shift = expand_simple_binop (Pmode, PLUS, shift, GEN_INT (bitpos), 1988169689Skan NULL, true, OPTAB_LIB_WIDEN); 1989169689Skan } 1990169689Skan } 1991169689Skan else 1992169689Skan { 1993169689Skan unsigned HOST_WIDE_INT offset = bitpos / BITS_PER_UNIT; 1994169689Skan bitpos %= BITS_PER_UNIT; 1995169689Skan 1996169689Skan /* When strict alignment is not required, we can just load directly 1997169689Skan from memory without masking. If the remaining BITPOS offset is 1998169689Skan small enough, we may be able to do all operations in MODE as 1999169689Skan opposed to DMODE. */ 2000169689Skan if (bitpos + bitsize <= m_bitsize) 2001169689Skan dmode = mode; 2002169689Skan comb = adjust_address (op0, dmode, offset); 2003169689Skan 2004169689Skan if (sign_shift_up <= bitpos) 2005169689Skan bitpos -= sign_shift_up, sign_shift_up = 0; 2006169689Skan shift = GEN_INT (bitpos); 2007169689Skan } 2008169689Skan 2009169689Skan /* Shift down the double-word such that the requested value is at bit 0. */ 2010169689Skan if (shift != const0_rtx) 2011169689Skan comb = expand_simple_binop (dmode, unsignedp ? LSHIFTRT : ASHIFTRT, 2012169689Skan comb, shift, NULL, unsignedp, OPTAB_LIB_WIDEN); 2013169689Skan if (comb == NULL) 2014169689Skan goto fail; 2015169689Skan 2016169689Skan /* If the field exactly matches MODE, then all we need to do is return the 2017169689Skan lowpart. Otherwise, shift to get the sign bits set properly. */ 2018169689Skan result = force_reg (mode, gen_lowpart (mode, comb)); 2019169689Skan 2020169689Skan if (sign_shift_up) 2021169689Skan result = expand_simple_binop (mode, ASHIFT, result, 2022169689Skan GEN_INT (sign_shift_up), 2023169689Skan NULL_RTX, 0, OPTAB_LIB_WIDEN); 2024169689Skan if (sign_shift_dn) 2025169689Skan result = expand_simple_binop (mode, unsignedp ? LSHIFTRT : ASHIFTRT, 2026169689Skan result, GEN_INT (sign_shift_dn), 2027169689Skan NULL_RTX, 0, OPTAB_LIB_WIDEN); 2028169689Skan 2029169689Skan return result; 2030169689Skan 2031169689Skan fail: 2032169689Skan delete_insns_since (start); 2033169689Skan return NULL; 2034169689Skan} 2035169689Skan 203618334Speter/* Extract a bit field that is split across two words 203718334Speter and return an RTX for the result. 203818334Speter 203918334Speter OP0 is the REG, SUBREG or MEM rtx for the first of the two words. 204018334Speter BITSIZE is the field width; BITPOS, position of its first bit, in the word. 204190075Sobrien UNSIGNEDP is 1 if should zero-extend the contents; else sign-extend. */ 204218334Speter 204318334Speterstatic rtx 2044132718Skanextract_split_bit_field (rtx op0, unsigned HOST_WIDE_INT bitsize, 2045132718Skan unsigned HOST_WIDE_INT bitpos, int unsignedp) 204618334Speter{ 204790075Sobrien unsigned int unit; 204890075Sobrien unsigned int bitsdone = 0; 204950397Sobrien rtx result = NULL_RTX; 205018334Speter int first = 1; 205118334Speter 205218334Speter /* Make sure UNIT isn't larger than BITS_PER_WORD, we can only handle that 205318334Speter much at a time. */ 2054169689Skan if (REG_P (op0) || GET_CODE (op0) == SUBREG) 205518334Speter unit = BITS_PER_WORD; 205618334Speter else 2057169689Skan { 2058169689Skan unit = MIN (MEM_ALIGN (op0), BITS_PER_WORD); 2059169689Skan if (0 && bitsize / unit > 2) 2060169689Skan { 2061169689Skan rtx tmp = extract_force_align_mem_bit_field (op0, bitsize, bitpos, 2062169689Skan unsignedp); 2063169689Skan if (tmp) 2064169689Skan return tmp; 2065169689Skan } 2066169689Skan } 206718334Speter 206818334Speter while (bitsdone < bitsize) 206918334Speter { 207090075Sobrien unsigned HOST_WIDE_INT thissize; 207118334Speter rtx part, word; 207290075Sobrien unsigned HOST_WIDE_INT thispos; 207390075Sobrien unsigned HOST_WIDE_INT offset; 207418334Speter 207518334Speter offset = (bitpos + bitsdone) / unit; 207618334Speter thispos = (bitpos + bitsdone) % unit; 207718334Speter 207818334Speter /* THISSIZE must not overrun a word boundary. Otherwise, 207918334Speter extract_fixed_bit_field will call us again, and we will mutually 208018334Speter recurse forever. */ 208118334Speter thissize = MIN (bitsize - bitsdone, BITS_PER_WORD); 208218334Speter thissize = MIN (thissize, unit - thispos); 208318334Speter 208418334Speter /* If OP0 is a register, then handle OFFSET here. 208518334Speter 208618334Speter When handling multiword bitfields, extract_bit_field may pass 208718334Speter down a word_mode SUBREG of a larger REG for a bitfield that actually 208818334Speter crosses a word boundary. Thus, for a SUBREG, we must find 208918334Speter the current word starting from the base register. */ 209018334Speter if (GET_CODE (op0) == SUBREG) 209118334Speter { 209290075Sobrien int word_offset = (SUBREG_BYTE (op0) / UNITS_PER_WORD) + offset; 209390075Sobrien word = operand_subword_force (SUBREG_REG (op0), word_offset, 209418334Speter GET_MODE (SUBREG_REG (op0))); 209518334Speter offset = 0; 209618334Speter } 2097169689Skan else if (REG_P (op0)) 209818334Speter { 209918334Speter word = operand_subword_force (op0, offset, GET_MODE (op0)); 210018334Speter offset = 0; 210118334Speter } 210218334Speter else 210318334Speter word = op0; 210418334Speter 210518334Speter /* Extract the parts in bit-counting order, 210618334Speter whose meaning is determined by BYTES_PER_UNIT. 210718334Speter OFFSET is in UNITs, and UNIT is in bits. 210818334Speter extract_fixed_bit_field wants offset in bytes. */ 210918334Speter part = extract_fixed_bit_field (word_mode, word, 211018334Speter offset * unit / BITS_PER_UNIT, 211190075Sobrien thissize, thispos, 0, 1); 211218334Speter bitsdone += thissize; 211318334Speter 211418334Speter /* Shift this part into place for the result. */ 211518334Speter if (BYTES_BIG_ENDIAN) 211618334Speter { 211718334Speter if (bitsize != bitsdone) 211818334Speter part = expand_shift (LSHIFT_EXPR, word_mode, part, 2119169689Skan build_int_cst (NULL_TREE, bitsize - bitsdone), 2120169689Skan 0, 1); 212118334Speter } 212218334Speter else 212318334Speter { 212418334Speter if (bitsdone != thissize) 212518334Speter part = expand_shift (LSHIFT_EXPR, word_mode, part, 2126169689Skan build_int_cst (NULL_TREE, 2127169689Skan bitsdone - thissize), 0, 1); 212818334Speter } 212918334Speter 213018334Speter if (first) 213118334Speter result = part; 213218334Speter else 213318334Speter /* Combine the parts with bitwise or. This works 213418334Speter because we extracted each part as an unsigned bit field. */ 213518334Speter result = expand_binop (word_mode, ior_optab, part, result, NULL_RTX, 1, 213618334Speter OPTAB_LIB_WIDEN); 213718334Speter 213818334Speter first = 0; 213918334Speter } 214018334Speter 214118334Speter /* Unsigned bit field: we are done. */ 214218334Speter if (unsignedp) 214318334Speter return result; 214418334Speter /* Signed bit field: sign-extend with two arithmetic shifts. */ 214518334Speter result = expand_shift (LSHIFT_EXPR, word_mode, result, 2146169689Skan build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize), 214718334Speter NULL_RTX, 0); 214818334Speter return expand_shift (RSHIFT_EXPR, word_mode, result, 2149169689Skan build_int_cst (NULL_TREE, BITS_PER_WORD - bitsize), 2150169689Skan NULL_RTX, 0); 215118334Speter} 215218334Speter 215318334Speter/* Add INC into TARGET. */ 215418334Speter 215518334Spetervoid 2156132718Skanexpand_inc (rtx target, rtx inc) 215718334Speter{ 215818334Speter rtx value = expand_binop (GET_MODE (target), add_optab, 215918334Speter target, inc, 216018334Speter target, 0, OPTAB_LIB_WIDEN); 216118334Speter if (value != target) 216218334Speter emit_move_insn (target, value); 216318334Speter} 216418334Speter 216518334Speter/* Subtract DEC from TARGET. */ 216618334Speter 216718334Spetervoid 2168132718Skanexpand_dec (rtx target, rtx dec) 216918334Speter{ 217018334Speter rtx value = expand_binop (GET_MODE (target), sub_optab, 217118334Speter target, dec, 217218334Speter target, 0, OPTAB_LIB_WIDEN); 217318334Speter if (value != target) 217418334Speter emit_move_insn (target, value); 217518334Speter} 217618334Speter 217718334Speter/* Output a shift instruction for expression code CODE, 217818334Speter with SHIFTED being the rtx for the value to shift, 217918334Speter and AMOUNT the tree for the amount to shift by. 218018334Speter Store the result in the rtx TARGET, if that is convenient. 218118334Speter If UNSIGNEDP is nonzero, do a logical shift; otherwise, arithmetic. 218218334Speter Return the rtx for where the value is. */ 218318334Speter 218418334Speterrtx 2185132718Skanexpand_shift (enum tree_code code, enum machine_mode mode, rtx shifted, 2186132718Skan tree amount, rtx target, int unsignedp) 218718334Speter{ 218890075Sobrien rtx op1, temp = 0; 218990075Sobrien int left = (code == LSHIFT_EXPR || code == LROTATE_EXPR); 219090075Sobrien int rotate = (code == LROTATE_EXPR || code == RROTATE_EXPR); 219118334Speter int try; 219218334Speter 219318334Speter /* Previously detected shift-counts computed by NEGATE_EXPR 219418334Speter and shifted in the other direction; but that does not work 219518334Speter on all machines. */ 219618334Speter 2197169689Skan op1 = expand_normal (amount); 219818334Speter 219950397Sobrien if (SHIFT_COUNT_TRUNCATED) 220050397Sobrien { 220150397Sobrien if (GET_CODE (op1) == CONST_INT 2202117395Skan && ((unsigned HOST_WIDE_INT) INTVAL (op1) >= 220352284Sobrien (unsigned HOST_WIDE_INT) GET_MODE_BITSIZE (mode))) 2204117395Skan op1 = GEN_INT ((unsigned HOST_WIDE_INT) INTVAL (op1) 220550397Sobrien % GET_MODE_BITSIZE (mode)); 220650397Sobrien else if (GET_CODE (op1) == SUBREG 2207117395Skan && subreg_lowpart_p (op1)) 220850397Sobrien op1 = SUBREG_REG (op1); 220950397Sobrien } 221018334Speter 221118334Speter if (op1 == const0_rtx) 221218334Speter return shifted; 221318334Speter 2214169689Skan /* Check whether its cheaper to implement a left shift by a constant 2215169689Skan bit count by a sequence of additions. */ 2216169689Skan if (code == LSHIFT_EXPR 2217169689Skan && GET_CODE (op1) == CONST_INT 2218169689Skan && INTVAL (op1) > 0 2219169689Skan && INTVAL (op1) < GET_MODE_BITSIZE (mode) 2220169689Skan && INTVAL (op1) < MAX_BITS_PER_WORD 2221169689Skan && shift_cost[mode][INTVAL (op1)] > INTVAL (op1) * add_cost[mode] 2222169689Skan && shift_cost[mode][INTVAL (op1)] != MAX_COST) 2223169689Skan { 2224169689Skan int i; 2225169689Skan for (i = 0; i < INTVAL (op1); i++) 2226169689Skan { 2227169689Skan temp = force_reg (mode, shifted); 2228169689Skan shifted = expand_binop (mode, add_optab, temp, temp, NULL_RTX, 2229169689Skan unsignedp, OPTAB_LIB_WIDEN); 2230169689Skan } 2231169689Skan return shifted; 2232169689Skan } 2233169689Skan 223418334Speter for (try = 0; temp == 0 && try < 3; try++) 223518334Speter { 223618334Speter enum optab_methods methods; 223718334Speter 223818334Speter if (try == 0) 223918334Speter methods = OPTAB_DIRECT; 224018334Speter else if (try == 1) 224118334Speter methods = OPTAB_WIDEN; 224218334Speter else 224318334Speter methods = OPTAB_LIB_WIDEN; 224418334Speter 224518334Speter if (rotate) 224618334Speter { 224718334Speter /* Widening does not work for rotation. */ 224818334Speter if (methods == OPTAB_WIDEN) 224918334Speter continue; 225018334Speter else if (methods == OPTAB_LIB_WIDEN) 225118334Speter { 225218334Speter /* If we have been unable to open-code this by a rotation, 225318334Speter do it as the IOR of two shifts. I.e., to rotate A 225418334Speter by N bits, compute (A << N) | ((unsigned) A >> (C - N)) 225518334Speter where C is the bitsize of A. 225618334Speter 225718334Speter It is theoretically possible that the target machine might 225818334Speter not be able to perform either shift and hence we would 225918334Speter be making two libcalls rather than just the one for the 226018334Speter shift (similarly if IOR could not be done). We will allow 226118334Speter this extremely unlikely lossage to avoid complicating the 226218334Speter code below. */ 226318334Speter 226418334Speter rtx subtarget = target == shifted ? 0 : target; 2265169689Skan tree new_amount, other_amount; 226618334Speter rtx temp1; 226718334Speter tree type = TREE_TYPE (amount); 2268169689Skan if (GET_MODE (op1) != TYPE_MODE (type) 2269169689Skan && GET_MODE (op1) != VOIDmode) 2270169689Skan op1 = convert_to_mode (TYPE_MODE (type), op1, 1); 2271169689Skan new_amount = make_tree (type, op1); 2272169689Skan other_amount 2273169689Skan = fold_build2 (MINUS_EXPR, type, 2274169689Skan build_int_cst (type, GET_MODE_BITSIZE (mode)), 2275169689Skan new_amount); 227618334Speter 227718334Speter shifted = force_reg (mode, shifted); 227818334Speter 227918334Speter temp = expand_shift (left ? LSHIFT_EXPR : RSHIFT_EXPR, 2280169689Skan mode, shifted, new_amount, 0, 1); 228118334Speter temp1 = expand_shift (left ? RSHIFT_EXPR : LSHIFT_EXPR, 2282169689Skan mode, shifted, other_amount, subtarget, 1); 228318334Speter return expand_binop (mode, ior_optab, temp, temp1, target, 228418334Speter unsignedp, methods); 228518334Speter } 228618334Speter 228718334Speter temp = expand_binop (mode, 228818334Speter left ? rotl_optab : rotr_optab, 228918334Speter shifted, op1, target, unsignedp, methods); 229018334Speter } 229118334Speter else if (unsignedp) 229218334Speter temp = expand_binop (mode, 229318334Speter left ? ashl_optab : lshr_optab, 229418334Speter shifted, op1, target, unsignedp, methods); 229518334Speter 229618334Speter /* Do arithmetic shifts. 229718334Speter Also, if we are going to widen the operand, we can just as well 229818334Speter use an arithmetic right-shift instead of a logical one. */ 229918334Speter if (temp == 0 && ! rotate 230018334Speter && (! unsignedp || (! left && methods == OPTAB_WIDEN))) 230118334Speter { 230218334Speter enum optab_methods methods1 = methods; 230318334Speter 230418334Speter /* If trying to widen a log shift to an arithmetic shift, 230518334Speter don't accept an arithmetic shift of the same size. */ 230618334Speter if (unsignedp) 230718334Speter methods1 = OPTAB_MUST_WIDEN; 230818334Speter 230918334Speter /* Arithmetic shift */ 231018334Speter 231118334Speter temp = expand_binop (mode, 231218334Speter left ? ashl_optab : ashr_optab, 231318334Speter shifted, op1, target, unsignedp, methods1); 231418334Speter } 231518334Speter 231618334Speter /* We used to try extzv here for logical right shifts, but that was 231796263Sobrien only useful for one machine, the VAX, and caused poor code 231818334Speter generation there for lshrdi3, so the code was deleted and a 231918334Speter define_expand for lshrsi3 was added to vax.md. */ 232018334Speter } 232118334Speter 2322169689Skan gcc_assert (temp); 232318334Speter return temp; 232418334Speter} 232518334Speter 2326169689Skanenum alg_code { 2327169689Skan alg_unknown, 2328169689Skan alg_zero, 2329169689Skan alg_m, alg_shift, 2330169689Skan alg_add_t_m2, 2331169689Skan alg_sub_t_m2, 2332169689Skan alg_add_factor, 2333169689Skan alg_sub_factor, 2334169689Skan alg_add_t2_m, 2335169689Skan alg_sub_t2_m, 2336169689Skan alg_impossible 2337169689Skan}; 233818334Speter 2339169689Skan/* This structure holds the "cost" of a multiply sequence. The 2340169689Skan "cost" field holds the total rtx_cost of every operator in the 2341169689Skan synthetic multiplication sequence, hence cost(a op b) is defined 2342169689Skan as rtx_cost(op) + cost(a) + cost(b), where cost(leaf) is zero. 2343169689Skan The "latency" field holds the minimum possible latency of the 2344169689Skan synthetic multiply, on a hypothetical infinitely parallel CPU. 2345169689Skan This is the critical path, or the maximum height, of the expression 2346169689Skan tree which is the sum of rtx_costs on the most expensive path from 2347169689Skan any leaf to the root. Hence latency(a op b) is defined as zero for 2348169689Skan leaves and rtx_cost(op) + max(latency(a), latency(b)) otherwise. */ 2349169689Skan 2350169689Skanstruct mult_cost { 2351169689Skan short cost; /* Total rtx_cost of the multiplication sequence. */ 2352169689Skan short latency; /* The latency of the multiplication sequence. */ 2353169689Skan}; 2354169689Skan 2355169689Skan/* This macro is used to compare a pointer to a mult_cost against an 2356169689Skan single integer "rtx_cost" value. This is equivalent to the macro 2357169689Skan CHEAPER_MULT_COST(X,Z) where Z = {Y,Y}. */ 2358169689Skan#define MULT_COST_LESS(X,Y) ((X)->cost < (Y) \ 2359169689Skan || ((X)->cost == (Y) && (X)->latency < (Y))) 2360169689Skan 2361169689Skan/* This macro is used to compare two pointers to mult_costs against 2362169689Skan each other. The macro returns true if X is cheaper than Y. 2363169689Skan Currently, the cheaper of two mult_costs is the one with the 2364169689Skan lower "cost". If "cost"s are tied, the lower latency is cheaper. */ 2365169689Skan#define CHEAPER_MULT_COST(X,Y) ((X)->cost < (Y)->cost \ 2366169689Skan || ((X)->cost == (Y)->cost \ 2367169689Skan && (X)->latency < (Y)->latency)) 2368169689Skan 236918334Speter/* This structure records a sequence of operations. 237018334Speter `ops' is the number of operations recorded. 237118334Speter `cost' is their total cost. 237218334Speter The operations are stored in `op' and the corresponding 237318334Speter logarithms of the integer coefficients in `log'. 237418334Speter 237518334Speter These are the operations: 237618334Speter alg_zero total := 0; 237718334Speter alg_m total := multiplicand; 237818334Speter alg_shift total := total * coeff 237918334Speter alg_add_t_m2 total := total + multiplicand * coeff; 238018334Speter alg_sub_t_m2 total := total - multiplicand * coeff; 238118334Speter alg_add_factor total := total * coeff + total; 238218334Speter alg_sub_factor total := total * coeff - total; 238318334Speter alg_add_t2_m total := total * coeff + multiplicand; 238418334Speter alg_sub_t2_m total := total * coeff - multiplicand; 238518334Speter 238618334Speter The first operand must be either alg_zero or alg_m. */ 238718334Speter 238818334Speterstruct algorithm 238918334Speter{ 2390169689Skan struct mult_cost cost; 239118334Speter short ops; 239218334Speter /* The size of the OP and LOG fields are not directly related to the 239318334Speter word size, but the worst-case algorithms will be if we have few 239418334Speter consecutive ones or zeros, i.e., a multiplicand like 10101010101... 239518334Speter In that case we will generate shift-by-2, add, shift-by-2, add,..., 239618334Speter in total wordsize operations. */ 239718334Speter enum alg_code op[MAX_BITS_PER_WORD]; 239818334Speter char log[MAX_BITS_PER_WORD]; 239918334Speter}; 240018334Speter 2401169689Skan/* The entry for our multiplication cache/hash table. */ 2402169689Skanstruct alg_hash_entry { 2403169689Skan /* The number we are multiplying by. */ 2404169689Skan unsigned HOST_WIDE_INT t; 2405169689Skan 2406169689Skan /* The mode in which we are multiplying something by T. */ 2407169689Skan enum machine_mode mode; 2408169689Skan 2409169689Skan /* The best multiplication algorithm for t. */ 2410169689Skan enum alg_code alg; 2411169689Skan 2412169689Skan /* The cost of multiplication if ALG_CODE is not alg_impossible. 2413169689Skan Otherwise, the cost within which multiplication by T is 2414169689Skan impossible. */ 2415169689Skan struct mult_cost cost; 2416169689Skan}; 2417169689Skan 2418169689Skan/* The number of cache/hash entries. */ 2419169689Skan#if HOST_BITS_PER_WIDE_INT == 64 2420169689Skan#define NUM_ALG_HASH_ENTRIES 1031 2421169689Skan#else 2422169689Skan#define NUM_ALG_HASH_ENTRIES 307 2423169689Skan#endif 2424169689Skan 2425169689Skan/* Each entry of ALG_HASH caches alg_code for some integer. This is 2426169689Skan actually a hash table. If we have a collision, that the older 2427169689Skan entry is kicked out. */ 2428169689Skanstatic struct alg_hash_entry alg_hash[NUM_ALG_HASH_ENTRIES]; 2429169689Skan 2430169689Skan/* Indicates the type of fixup needed after a constant multiplication. 2431169689Skan BASIC_VARIANT means no fixup is needed, NEGATE_VARIANT means that 2432169689Skan the result should be negated, and ADD_VARIANT means that the 2433169689Skan multiplicand should be added to the result. */ 2434169689Skanenum mult_variant {basic_variant, negate_variant, add_variant}; 2435169689Skan 2436169689Skanstatic void synth_mult (struct algorithm *, unsigned HOST_WIDE_INT, 2437169689Skan const struct mult_cost *, enum machine_mode mode); 2438169689Skanstatic bool choose_mult_variant (enum machine_mode, HOST_WIDE_INT, 2439169689Skan struct algorithm *, enum mult_variant *, int); 2440169689Skanstatic rtx expand_mult_const (enum machine_mode, rtx, HOST_WIDE_INT, rtx, 2441169689Skan const struct algorithm *, enum mult_variant); 2442132718Skanstatic unsigned HOST_WIDE_INT choose_multiplier (unsigned HOST_WIDE_INT, int, 2443169689Skan int, rtx *, int *, int *); 2444132718Skanstatic unsigned HOST_WIDE_INT invert_mod2n (unsigned HOST_WIDE_INT, int); 2445169689Skanstatic rtx extract_high_half (enum machine_mode, rtx); 2446169689Skanstatic rtx expand_mult_highpart (enum machine_mode, rtx, rtx, rtx, int, int); 2447169689Skanstatic rtx expand_mult_highpart_optab (enum machine_mode, rtx, rtx, rtx, 2448169689Skan int, int); 244918334Speter/* Compute and return the best algorithm for multiplying by T. 245018334Speter The algorithm must cost less than cost_limit 245118334Speter If retval.cost >= COST_LIMIT, no algorithm was found and all 2452169689Skan other field of the returned struct are undefined. 2453169689Skan MODE is the machine mode of the multiplication. */ 245418334Speter 245518334Speterstatic void 2456132718Skansynth_mult (struct algorithm *alg_out, unsigned HOST_WIDE_INT t, 2457169689Skan const struct mult_cost *cost_limit, enum machine_mode mode) 245818334Speter{ 245918334Speter int m; 246018334Speter struct algorithm *alg_in, *best_alg; 2461169689Skan struct mult_cost best_cost; 2462169689Skan struct mult_cost new_limit; 2463169689Skan int op_cost, op_latency; 246418334Speter unsigned HOST_WIDE_INT q; 2465169689Skan int maxm = MIN (BITS_PER_WORD, GET_MODE_BITSIZE (mode)); 2466169689Skan int hash_index; 2467169689Skan bool cache_hit = false; 2468169689Skan enum alg_code cache_alg = alg_zero; 246918334Speter 247018334Speter /* Indicate that no algorithm is yet found. If no algorithm 247118334Speter is found, this value will be returned and indicate failure. */ 2472169689Skan alg_out->cost.cost = cost_limit->cost + 1; 2473169689Skan alg_out->cost.latency = cost_limit->latency + 1; 247418334Speter 2475169689Skan if (cost_limit->cost < 0 2476169689Skan || (cost_limit->cost == 0 && cost_limit->latency <= 0)) 247718334Speter return; 247818334Speter 2479169689Skan /* Restrict the bits of "t" to the multiplication's mode. */ 2480169689Skan t &= GET_MODE_MASK (mode); 2481169689Skan 248218334Speter /* t == 1 can be done in zero cost. */ 248318334Speter if (t == 1) 248418334Speter { 248518334Speter alg_out->ops = 1; 2486169689Skan alg_out->cost.cost = 0; 2487169689Skan alg_out->cost.latency = 0; 248818334Speter alg_out->op[0] = alg_m; 248918334Speter return; 249018334Speter } 249118334Speter 249218334Speter /* t == 0 sometimes has a cost. If it does and it exceeds our limit, 249318334Speter fail now. */ 249418334Speter if (t == 0) 249518334Speter { 2496169689Skan if (MULT_COST_LESS (cost_limit, zero_cost)) 249718334Speter return; 249818334Speter else 249918334Speter { 250018334Speter alg_out->ops = 1; 2501169689Skan alg_out->cost.cost = zero_cost; 2502169689Skan alg_out->cost.latency = zero_cost; 250318334Speter alg_out->op[0] = alg_zero; 250418334Speter return; 250518334Speter } 250618334Speter } 250718334Speter 250818334Speter /* We'll be needing a couple extra algorithm structures now. */ 250918334Speter 2510132718Skan alg_in = alloca (sizeof (struct algorithm)); 2511132718Skan best_alg = alloca (sizeof (struct algorithm)); 2512169689Skan best_cost = *cost_limit; 251318334Speter 2514169689Skan /* Compute the hash index. */ 2515169689Skan hash_index = (t ^ (unsigned int) mode) % NUM_ALG_HASH_ENTRIES; 2516169689Skan 2517169689Skan /* See if we already know what to do for T. */ 2518169689Skan if (alg_hash[hash_index].t == t 2519169689Skan && alg_hash[hash_index].mode == mode 2520169689Skan && alg_hash[hash_index].alg != alg_unknown) 2521169689Skan { 2522169689Skan cache_alg = alg_hash[hash_index].alg; 2523169689Skan 2524169689Skan if (cache_alg == alg_impossible) 2525169689Skan { 2526169689Skan /* The cache tells us that it's impossible to synthesize 2527169689Skan multiplication by T within alg_hash[hash_index].cost. */ 2528169689Skan if (!CHEAPER_MULT_COST (&alg_hash[hash_index].cost, cost_limit)) 2529169689Skan /* COST_LIMIT is at least as restrictive as the one 2530169689Skan recorded in the hash table, in which case we have no 2531169689Skan hope of synthesizing a multiplication. Just 2532169689Skan return. */ 2533169689Skan return; 2534169689Skan 2535169689Skan /* If we get here, COST_LIMIT is less restrictive than the 2536169689Skan one recorded in the hash table, so we may be able to 2537169689Skan synthesize a multiplication. Proceed as if we didn't 2538169689Skan have the cache entry. */ 2539169689Skan } 2540169689Skan else 2541169689Skan { 2542169689Skan if (CHEAPER_MULT_COST (cost_limit, &alg_hash[hash_index].cost)) 2543169689Skan /* The cached algorithm shows that this multiplication 2544169689Skan requires more cost than COST_LIMIT. Just return. This 2545169689Skan way, we don't clobber this cache entry with 2546169689Skan alg_impossible but retain useful information. */ 2547169689Skan return; 2548169689Skan 2549169689Skan cache_hit = true; 2550169689Skan 2551169689Skan switch (cache_alg) 2552169689Skan { 2553169689Skan case alg_shift: 2554169689Skan goto do_alg_shift; 2555169689Skan 2556169689Skan case alg_add_t_m2: 2557169689Skan case alg_sub_t_m2: 2558169689Skan goto do_alg_addsub_t_m2; 2559169689Skan 2560169689Skan case alg_add_factor: 2561169689Skan case alg_sub_factor: 2562169689Skan goto do_alg_addsub_factor; 2563169689Skan 2564169689Skan case alg_add_t2_m: 2565169689Skan goto do_alg_add_t2_m; 2566169689Skan 2567169689Skan case alg_sub_t2_m: 2568169689Skan goto do_alg_sub_t2_m; 2569169689Skan 2570169689Skan default: 2571169689Skan gcc_unreachable (); 2572169689Skan } 2573169689Skan } 2574169689Skan } 2575169689Skan 257618334Speter /* If we have a group of zero bits at the low-order part of T, try 257718334Speter multiplying by the remaining bits and then doing a shift. */ 257818334Speter 257918334Speter if ((t & 1) == 0) 258018334Speter { 2581169689Skan do_alg_shift: 258218334Speter m = floor_log2 (t & -t); /* m = number of low zero bits */ 2583169689Skan if (m < maxm) 258490075Sobrien { 258590075Sobrien q = t >> m; 2586169689Skan /* The function expand_shift will choose between a shift and 2587169689Skan a sequence of additions, so the observed cost is given as 2588169689Skan MIN (m * add_cost[mode], shift_cost[mode][m]). */ 2589169689Skan op_cost = m * add_cost[mode]; 2590169689Skan if (shift_cost[mode][m] < op_cost) 2591169689Skan op_cost = shift_cost[mode][m]; 2592169689Skan new_limit.cost = best_cost.cost - op_cost; 2593169689Skan new_limit.latency = best_cost.latency - op_cost; 2594169689Skan synth_mult (alg_in, q, &new_limit, mode); 259518334Speter 2596169689Skan alg_in->cost.cost += op_cost; 2597169689Skan alg_in->cost.latency += op_cost; 2598169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 259990075Sobrien { 260090075Sobrien struct algorithm *x; 2601169689Skan best_cost = alg_in->cost; 260290075Sobrien x = alg_in, alg_in = best_alg, best_alg = x; 260390075Sobrien best_alg->log[best_alg->ops] = m; 260490075Sobrien best_alg->op[best_alg->ops] = alg_shift; 260590075Sobrien } 260618334Speter } 2607169689Skan if (cache_hit) 2608169689Skan goto done; 260918334Speter } 261018334Speter 261118334Speter /* If we have an odd number, add or subtract one. */ 261218334Speter if ((t & 1) != 0) 261318334Speter { 261418334Speter unsigned HOST_WIDE_INT w; 261518334Speter 2616169689Skan do_alg_addsub_t_m2: 261718334Speter for (w = 1; (w & t) != 0; w <<= 1) 261818334Speter ; 261950397Sobrien /* If T was -1, then W will be zero after the loop. This is another 262096263Sobrien case where T ends with ...111. Handling this with (T + 1) and 262150397Sobrien subtract 1 produces slightly better code and results in algorithm 262250397Sobrien selection much faster than treating it like the ...0111 case 262350397Sobrien below. */ 262450397Sobrien if (w == 0 262550397Sobrien || (w > 2 262650397Sobrien /* Reject the case where t is 3. 262750397Sobrien Thus we prefer addition in that case. */ 262850397Sobrien && t != 3)) 262918334Speter { 263018334Speter /* T ends with ...111. Multiply by (T + 1) and subtract 1. */ 263118334Speter 2632169689Skan op_cost = add_cost[mode]; 2633169689Skan new_limit.cost = best_cost.cost - op_cost; 2634169689Skan new_limit.latency = best_cost.latency - op_cost; 2635169689Skan synth_mult (alg_in, t + 1, &new_limit, mode); 263618334Speter 2637169689Skan alg_in->cost.cost += op_cost; 2638169689Skan alg_in->cost.latency += op_cost; 2639169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 264018334Speter { 264118334Speter struct algorithm *x; 2642169689Skan best_cost = alg_in->cost; 264318334Speter x = alg_in, alg_in = best_alg, best_alg = x; 264418334Speter best_alg->log[best_alg->ops] = 0; 264518334Speter best_alg->op[best_alg->ops] = alg_sub_t_m2; 264618334Speter } 264718334Speter } 264818334Speter else 264918334Speter { 265018334Speter /* T ends with ...01 or ...011. Multiply by (T - 1) and add 1. */ 265118334Speter 2652169689Skan op_cost = add_cost[mode]; 2653169689Skan new_limit.cost = best_cost.cost - op_cost; 2654169689Skan new_limit.latency = best_cost.latency - op_cost; 2655169689Skan synth_mult (alg_in, t - 1, &new_limit, mode); 265618334Speter 2657169689Skan alg_in->cost.cost += op_cost; 2658169689Skan alg_in->cost.latency += op_cost; 2659169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 266018334Speter { 266118334Speter struct algorithm *x; 2662169689Skan best_cost = alg_in->cost; 266318334Speter x = alg_in, alg_in = best_alg, best_alg = x; 266418334Speter best_alg->log[best_alg->ops] = 0; 266518334Speter best_alg->op[best_alg->ops] = alg_add_t_m2; 266618334Speter } 266718334Speter } 2668169689Skan if (cache_hit) 2669169689Skan goto done; 267018334Speter } 267118334Speter 267218334Speter /* Look for factors of t of the form 267318334Speter t = q(2**m +- 1), 2 <= m <= floor(log2(t - 1)). 267418334Speter If we find such a factor, we can multiply by t using an algorithm that 267518334Speter multiplies by q, shift the result by m and add/subtract it to itself. 267618334Speter 267718334Speter We search for large factors first and loop down, even if large factors 267818334Speter are less probable than small; if we find a large factor we will find a 267918334Speter good sequence quickly, and therefore be able to prune (by decreasing 268018334Speter COST_LIMIT) the search. */ 268118334Speter 2682169689Skan do_alg_addsub_factor: 268318334Speter for (m = floor_log2 (t - 1); m >= 2; m--) 268418334Speter { 268518334Speter unsigned HOST_WIDE_INT d; 268618334Speter 268718334Speter d = ((unsigned HOST_WIDE_INT) 1 << m) + 1; 2688169689Skan if (t % d == 0 && t > d && m < maxm 2689169689Skan && (!cache_hit || cache_alg == alg_add_factor)) 269018334Speter { 2691169689Skan /* If the target has a cheap shift-and-add instruction use 2692169689Skan that in preference to a shift insn followed by an add insn. 2693169689Skan Assume that the shift-and-add is "atomic" with a latency 2694169689Skan equal to its cost, otherwise assume that on superscalar 2695169689Skan hardware the shift may be executed concurrently with the 2696169689Skan earlier steps in the algorithm. */ 2697169689Skan op_cost = add_cost[mode] + shift_cost[mode][m]; 2698169689Skan if (shiftadd_cost[mode][m] < op_cost) 2699169689Skan { 2700169689Skan op_cost = shiftadd_cost[mode][m]; 2701169689Skan op_latency = op_cost; 2702169689Skan } 2703169689Skan else 2704169689Skan op_latency = add_cost[mode]; 270518334Speter 2706169689Skan new_limit.cost = best_cost.cost - op_cost; 2707169689Skan new_limit.latency = best_cost.latency - op_latency; 2708169689Skan synth_mult (alg_in, t / d, &new_limit, mode); 2709169689Skan 2710169689Skan alg_in->cost.cost += op_cost; 2711169689Skan alg_in->cost.latency += op_latency; 2712169689Skan if (alg_in->cost.latency < op_cost) 2713169689Skan alg_in->cost.latency = op_cost; 2714169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 271518334Speter { 271618334Speter struct algorithm *x; 2717169689Skan best_cost = alg_in->cost; 271818334Speter x = alg_in, alg_in = best_alg, best_alg = x; 271918334Speter best_alg->log[best_alg->ops] = m; 272018334Speter best_alg->op[best_alg->ops] = alg_add_factor; 272118334Speter } 272218334Speter /* Other factors will have been taken care of in the recursion. */ 272318334Speter break; 272418334Speter } 272518334Speter 272618334Speter d = ((unsigned HOST_WIDE_INT) 1 << m) - 1; 2727169689Skan if (t % d == 0 && t > d && m < maxm 2728169689Skan && (!cache_hit || cache_alg == alg_sub_factor)) 272918334Speter { 2730169689Skan /* If the target has a cheap shift-and-subtract insn use 2731169689Skan that in preference to a shift insn followed by a sub insn. 2732169689Skan Assume that the shift-and-sub is "atomic" with a latency 2733169689Skan equal to it's cost, otherwise assume that on superscalar 2734169689Skan hardware the shift may be executed concurrently with the 2735169689Skan earlier steps in the algorithm. */ 2736169689Skan op_cost = add_cost[mode] + shift_cost[mode][m]; 2737169689Skan if (shiftsub_cost[mode][m] < op_cost) 2738169689Skan { 2739169689Skan op_cost = shiftsub_cost[mode][m]; 2740169689Skan op_latency = op_cost; 2741169689Skan } 2742169689Skan else 2743169689Skan op_latency = add_cost[mode]; 274418334Speter 2745169689Skan new_limit.cost = best_cost.cost - op_cost; 2746169689Skan new_limit.latency = best_cost.latency - op_latency; 2747169689Skan synth_mult (alg_in, t / d, &new_limit, mode); 2748169689Skan 2749169689Skan alg_in->cost.cost += op_cost; 2750169689Skan alg_in->cost.latency += op_latency; 2751169689Skan if (alg_in->cost.latency < op_cost) 2752169689Skan alg_in->cost.latency = op_cost; 2753169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 275418334Speter { 275518334Speter struct algorithm *x; 2756169689Skan best_cost = alg_in->cost; 275718334Speter x = alg_in, alg_in = best_alg, best_alg = x; 275818334Speter best_alg->log[best_alg->ops] = m; 275918334Speter best_alg->op[best_alg->ops] = alg_sub_factor; 276018334Speter } 276118334Speter break; 276218334Speter } 276318334Speter } 2764169689Skan if (cache_hit) 2765169689Skan goto done; 276618334Speter 276718334Speter /* Try shift-and-add (load effective address) instructions, 276818334Speter i.e. do a*3, a*5, a*9. */ 276918334Speter if ((t & 1) != 0) 277018334Speter { 2771169689Skan do_alg_add_t2_m: 277218334Speter q = t - 1; 277318334Speter q = q & -q; 277418334Speter m = exact_log2 (q); 2775169689Skan if (m >= 0 && m < maxm) 277618334Speter { 2777169689Skan op_cost = shiftadd_cost[mode][m]; 2778169689Skan new_limit.cost = best_cost.cost - op_cost; 2779169689Skan new_limit.latency = best_cost.latency - op_cost; 2780169689Skan synth_mult (alg_in, (t - 1) >> m, &new_limit, mode); 278118334Speter 2782169689Skan alg_in->cost.cost += op_cost; 2783169689Skan alg_in->cost.latency += op_cost; 2784169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 278518334Speter { 278618334Speter struct algorithm *x; 2787169689Skan best_cost = alg_in->cost; 278818334Speter x = alg_in, alg_in = best_alg, best_alg = x; 278918334Speter best_alg->log[best_alg->ops] = m; 279018334Speter best_alg->op[best_alg->ops] = alg_add_t2_m; 279118334Speter } 279218334Speter } 2793169689Skan if (cache_hit) 2794169689Skan goto done; 279518334Speter 2796169689Skan do_alg_sub_t2_m: 279718334Speter q = t + 1; 279818334Speter q = q & -q; 279918334Speter m = exact_log2 (q); 2800169689Skan if (m >= 0 && m < maxm) 280118334Speter { 2802169689Skan op_cost = shiftsub_cost[mode][m]; 2803169689Skan new_limit.cost = best_cost.cost - op_cost; 2804169689Skan new_limit.latency = best_cost.latency - op_cost; 2805169689Skan synth_mult (alg_in, (t + 1) >> m, &new_limit, mode); 280618334Speter 2807169689Skan alg_in->cost.cost += op_cost; 2808169689Skan alg_in->cost.latency += op_cost; 2809169689Skan if (CHEAPER_MULT_COST (&alg_in->cost, &best_cost)) 281018334Speter { 281118334Speter struct algorithm *x; 2812169689Skan best_cost = alg_in->cost; 281318334Speter x = alg_in, alg_in = best_alg, best_alg = x; 281418334Speter best_alg->log[best_alg->ops] = m; 281518334Speter best_alg->op[best_alg->ops] = alg_sub_t2_m; 281618334Speter } 281718334Speter } 2818169689Skan if (cache_hit) 2819169689Skan goto done; 282018334Speter } 282118334Speter 2822169689Skan done: 2823169689Skan /* If best_cost has not decreased, we have not found any algorithm. */ 2824169689Skan if (!CHEAPER_MULT_COST (&best_cost, cost_limit)) 2825169689Skan { 2826169689Skan /* We failed to find an algorithm. Record alg_impossible for 2827169689Skan this case (that is, <T, MODE, COST_LIMIT>) so that next time 2828169689Skan we are asked to find an algorithm for T within the same or 2829169689Skan lower COST_LIMIT, we can immediately return to the 2830169689Skan caller. */ 2831169689Skan alg_hash[hash_index].t = t; 2832169689Skan alg_hash[hash_index].mode = mode; 2833169689Skan alg_hash[hash_index].alg = alg_impossible; 2834169689Skan alg_hash[hash_index].cost = *cost_limit; 2835169689Skan return; 2836169689Skan } 283718334Speter 2838169689Skan /* Cache the result. */ 2839169689Skan if (!cache_hit) 2840169689Skan { 2841169689Skan alg_hash[hash_index].t = t; 2842169689Skan alg_hash[hash_index].mode = mode; 2843169689Skan alg_hash[hash_index].alg = best_alg->op[best_alg->ops]; 2844169689Skan alg_hash[hash_index].cost.cost = best_cost.cost; 2845169689Skan alg_hash[hash_index].cost.latency = best_cost.latency; 2846169689Skan } 2847169689Skan 284818334Speter /* If we are getting a too long sequence for `struct algorithm' 284918334Speter to record, make this search fail. */ 285018334Speter if (best_alg->ops == MAX_BITS_PER_WORD) 285118334Speter return; 285218334Speter 285318334Speter /* Copy the algorithm from temporary space to the space at alg_out. 285418334Speter We avoid using structure assignment because the majority of 285518334Speter best_alg is normally undefined, and this is a critical function. */ 285618334Speter alg_out->ops = best_alg->ops + 1; 2857169689Skan alg_out->cost = best_cost; 285890075Sobrien memcpy (alg_out->op, best_alg->op, 285990075Sobrien alg_out->ops * sizeof *alg_out->op); 286090075Sobrien memcpy (alg_out->log, best_alg->log, 286190075Sobrien alg_out->ops * sizeof *alg_out->log); 286218334Speter} 286318334Speter 2864169689Skan/* Find the cheapest way of multiplying a value of mode MODE by VAL. 2865169689Skan Try three variations: 286618334Speter 2867169689Skan - a shift/add sequence based on VAL itself 2868169689Skan - a shift/add sequence based on -VAL, followed by a negation 2869169689Skan - a shift/add sequence based on VAL - 1, followed by an addition. 287018334Speter 2871169689Skan Return true if the cheapest of these cost less than MULT_COST, 2872169689Skan describing the algorithm in *ALG and final fixup in *VARIANT. */ 2873169689Skan 2874169689Skanstatic bool 2875169689Skanchoose_mult_variant (enum machine_mode mode, HOST_WIDE_INT val, 2876169689Skan struct algorithm *alg, enum mult_variant *variant, 2877169689Skan int mult_cost) 287818334Speter{ 2879169689Skan struct algorithm alg2; 2880169689Skan struct mult_cost limit; 2881169689Skan int op_cost; 288218334Speter 2883169689Skan /* Fail quickly for impossible bounds. */ 2884169689Skan if (mult_cost < 0) 2885169689Skan return false; 288618334Speter 2887169689Skan /* Ensure that mult_cost provides a reasonable upper bound. 2888169689Skan Any constant multiplication can be performed with less 2889169689Skan than 2 * bits additions. */ 2890169689Skan op_cost = 2 * GET_MODE_BITSIZE (mode) * add_cost[mode]; 2891169689Skan if (mult_cost > op_cost) 2892169689Skan mult_cost = op_cost; 289318334Speter 2894169689Skan *variant = basic_variant; 2895169689Skan limit.cost = mult_cost; 2896169689Skan limit.latency = mult_cost; 2897169689Skan synth_mult (alg, val, &limit, mode); 289818334Speter 2899169689Skan /* This works only if the inverted value actually fits in an 2900169689Skan `unsigned int' */ 2901169689Skan if (HOST_BITS_PER_INT >= GET_MODE_BITSIZE (mode)) 290218334Speter { 2903169689Skan op_cost = neg_cost[mode]; 2904169689Skan if (MULT_COST_LESS (&alg->cost, mult_cost)) 2905169689Skan { 2906169689Skan limit.cost = alg->cost.cost - op_cost; 2907169689Skan limit.latency = alg->cost.latency - op_cost; 2908169689Skan } 2909169689Skan else 2910169689Skan { 2911169689Skan limit.cost = mult_cost - op_cost; 2912169689Skan limit.latency = mult_cost - op_cost; 2913169689Skan } 291418334Speter 2915169689Skan synth_mult (&alg2, -val, &limit, mode); 2916169689Skan alg2.cost.cost += op_cost; 2917169689Skan alg2.cost.latency += op_cost; 2918169689Skan if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost)) 2919169689Skan *alg = alg2, *variant = negate_variant; 2920169689Skan } 292190075Sobrien 2922169689Skan /* This proves very useful for division-by-constant. */ 2923169689Skan op_cost = add_cost[mode]; 2924169689Skan if (MULT_COST_LESS (&alg->cost, mult_cost)) 2925169689Skan { 2926169689Skan limit.cost = alg->cost.cost - op_cost; 2927169689Skan limit.latency = alg->cost.latency - op_cost; 2928169689Skan } 2929169689Skan else 2930169689Skan { 2931169689Skan limit.cost = mult_cost - op_cost; 2932169689Skan limit.latency = mult_cost - op_cost; 2933169689Skan } 293418334Speter 2935169689Skan synth_mult (&alg2, val - 1, &limit, mode); 2936169689Skan alg2.cost.cost += op_cost; 2937169689Skan alg2.cost.latency += op_cost; 2938169689Skan if (CHEAPER_MULT_COST (&alg2.cost, &alg->cost)) 2939169689Skan *alg = alg2, *variant = add_variant; 294018334Speter 2941169689Skan return MULT_COST_LESS (&alg->cost, mult_cost); 2942169689Skan} 294318334Speter 2944169689Skan/* A subroutine of expand_mult, used for constant multiplications. 2945169689Skan Multiply OP0 by VAL in mode MODE, storing the result in TARGET if 2946169689Skan convenient. Use the shift/add sequence described by ALG and apply 2947169689Skan the final fixup specified by VARIANT. */ 294818334Speter 2949169689Skanstatic rtx 2950169689Skanexpand_mult_const (enum machine_mode mode, rtx op0, HOST_WIDE_INT val, 2951169689Skan rtx target, const struct algorithm *alg, 2952169689Skan enum mult_variant variant) 2953169689Skan{ 2954169689Skan HOST_WIDE_INT val_so_far; 2955169689Skan rtx insn, accum, tem; 2956169689Skan int opno; 2957169689Skan enum machine_mode nmode; 295818334Speter 2959169689Skan /* Avoid referencing memory over and over. 2960169689Skan For speed, but also for correctness when mem is volatile. */ 2961169689Skan if (MEM_P (op0)) 2962169689Skan op0 = force_reg (mode, op0); 2963169689Skan 2964169689Skan /* ACCUM starts out either as OP0 or as a zero, depending on 2965169689Skan the first operation. */ 2966169689Skan 2967169689Skan if (alg->op[0] == alg_zero) 2968169689Skan { 2969169689Skan accum = copy_to_mode_reg (mode, const0_rtx); 2970169689Skan val_so_far = 0; 2971169689Skan } 2972169689Skan else if (alg->op[0] == alg_m) 2973169689Skan { 2974169689Skan accum = copy_to_mode_reg (mode, op0); 2975169689Skan val_so_far = 1; 2976169689Skan } 2977169689Skan else 2978169689Skan gcc_unreachable (); 2979169689Skan 2980169689Skan for (opno = 1; opno < alg->ops; opno++) 2981169689Skan { 2982169689Skan int log = alg->log[opno]; 2983169689Skan rtx shift_subtarget = optimize ? 0 : accum; 2984169689Skan rtx add_target 2985169689Skan = (opno == alg->ops - 1 && target != 0 && variant != add_variant 2986169689Skan && !optimize) 2987169689Skan ? target : 0; 2988169689Skan rtx accum_target = optimize ? 0 : accum; 2989169689Skan 2990169689Skan switch (alg->op[opno]) 299118334Speter { 2992169689Skan case alg_shift: 2993169689Skan accum = expand_shift (LSHIFT_EXPR, mode, accum, 2994169689Skan build_int_cst (NULL_TREE, log), 2995169689Skan NULL_RTX, 0); 2996169689Skan val_so_far <<= log; 2997169689Skan break; 299818334Speter 2999169689Skan case alg_add_t_m2: 3000169689Skan tem = expand_shift (LSHIFT_EXPR, mode, op0, 3001169689Skan build_int_cst (NULL_TREE, log), 3002169689Skan NULL_RTX, 0); 3003169689Skan accum = force_operand (gen_rtx_PLUS (mode, accum, tem), 3004169689Skan add_target ? add_target : accum_target); 3005169689Skan val_so_far += (HOST_WIDE_INT) 1 << log; 3006169689Skan break; 300718334Speter 3008169689Skan case alg_sub_t_m2: 3009169689Skan tem = expand_shift (LSHIFT_EXPR, mode, op0, 3010169689Skan build_int_cst (NULL_TREE, log), 3011169689Skan NULL_RTX, 0); 3012169689Skan accum = force_operand (gen_rtx_MINUS (mode, accum, tem), 3013169689Skan add_target ? add_target : accum_target); 3014169689Skan val_so_far -= (HOST_WIDE_INT) 1 << log; 3015169689Skan break; 301618334Speter 3017169689Skan case alg_add_t2_m: 3018169689Skan accum = expand_shift (LSHIFT_EXPR, mode, accum, 3019169689Skan build_int_cst (NULL_TREE, log), 3020169689Skan shift_subtarget, 3021169689Skan 0); 3022169689Skan accum = force_operand (gen_rtx_PLUS (mode, accum, op0), 3023169689Skan add_target ? add_target : accum_target); 3024169689Skan val_so_far = (val_so_far << log) + 1; 3025169689Skan break; 302618334Speter 3027169689Skan case alg_sub_t2_m: 3028169689Skan accum = expand_shift (LSHIFT_EXPR, mode, accum, 3029169689Skan build_int_cst (NULL_TREE, log), 3030169689Skan shift_subtarget, 0); 3031169689Skan accum = force_operand (gen_rtx_MINUS (mode, accum, op0), 3032169689Skan add_target ? add_target : accum_target); 3033169689Skan val_so_far = (val_so_far << log) - 1; 3034169689Skan break; 303518334Speter 3036169689Skan case alg_add_factor: 3037169689Skan tem = expand_shift (LSHIFT_EXPR, mode, accum, 3038169689Skan build_int_cst (NULL_TREE, log), 3039169689Skan NULL_RTX, 0); 3040169689Skan accum = force_operand (gen_rtx_PLUS (mode, accum, tem), 3041169689Skan add_target ? add_target : accum_target); 3042169689Skan val_so_far += val_so_far << log; 3043169689Skan break; 304496263Sobrien 3045169689Skan case alg_sub_factor: 3046169689Skan tem = expand_shift (LSHIFT_EXPR, mode, accum, 3047169689Skan build_int_cst (NULL_TREE, log), 3048169689Skan NULL_RTX, 0); 3049169689Skan accum = force_operand (gen_rtx_MINUS (mode, tem, accum), 3050169689Skan (add_target 3051169689Skan ? add_target : (optimize ? 0 : tem))); 3052169689Skan val_so_far = (val_so_far << log) - val_so_far; 3053169689Skan break; 305418334Speter 3055169689Skan default: 3056169689Skan gcc_unreachable (); 3057169689Skan } 305818334Speter 3059169689Skan /* Write a REG_EQUAL note on the last insn so that we can cse 3060169689Skan multiplication sequences. Note that if ACCUM is a SUBREG, 3061169689Skan we've set the inner register and must properly indicate 3062169689Skan that. */ 306318334Speter 3064169689Skan tem = op0, nmode = mode; 3065169689Skan if (GET_CODE (accum) == SUBREG) 3066169689Skan { 3067169689Skan nmode = GET_MODE (SUBREG_REG (accum)); 3068169689Skan tem = gen_lowpart (nmode, op0); 3069169689Skan } 307018334Speter 3071169689Skan insn = get_last_insn (); 3072169689Skan set_unique_reg_note (insn, REG_EQUAL, 3073169689Skan gen_rtx_MULT (nmode, tem, GEN_INT (val_so_far))); 3074169689Skan } 307518334Speter 3076169689Skan if (variant == negate_variant) 3077169689Skan { 3078169689Skan val_so_far = -val_so_far; 3079169689Skan accum = expand_unop (mode, neg_optab, accum, target, 0); 3080169689Skan } 3081169689Skan else if (variant == add_variant) 3082169689Skan { 3083169689Skan val_so_far = val_so_far + 1; 3084169689Skan accum = force_operand (gen_rtx_PLUS (mode, accum, op0), target); 3085169689Skan } 308618334Speter 3087169689Skan /* Compare only the bits of val and val_so_far that are significant 3088169689Skan in the result mode, to avoid sign-/zero-extension confusion. */ 3089169689Skan val &= GET_MODE_MASK (mode); 3090169689Skan val_so_far &= GET_MODE_MASK (mode); 3091169689Skan gcc_assert (val == val_so_far); 309218334Speter 3093169689Skan return accum; 3094169689Skan} 309518334Speter 3096169689Skan/* Perform a multiplication and return an rtx for the result. 3097169689Skan MODE is mode of value; OP0 and OP1 are what to multiply (rtx's); 3098169689Skan TARGET is a suggestion for where to store the result (an rtx). 309918334Speter 3100169689Skan We check specially for a constant integer as OP1. 3101169689Skan If you want this check for OP0 as well, then before calling 3102169689Skan you should swap the two operands if OP0 would be constant. */ 310390075Sobrien 3104169689Skanrtx 3105169689Skanexpand_mult (enum machine_mode mode, rtx op0, rtx op1, rtx target, 3106169689Skan int unsignedp) 3107169689Skan{ 3108169689Skan enum mult_variant variant; 3109169689Skan struct algorithm algorithm; 3110169689Skan int max_cost; 311118334Speter 3112169689Skan /* Handling const0_rtx here allows us to use zero as a rogue value for 3113169689Skan coeff below. */ 3114169689Skan if (op1 == const0_rtx) 3115169689Skan return const0_rtx; 3116169689Skan if (op1 == const1_rtx) 3117169689Skan return op0; 3118169689Skan if (op1 == constm1_rtx) 3119169689Skan return expand_unop (mode, 3120169689Skan GET_MODE_CLASS (mode) == MODE_INT 3121169689Skan && !unsignedp && flag_trapv 3122169689Skan ? negv_optab : neg_optab, 3123169689Skan op0, target, 0); 3124169689Skan 3125169689Skan /* These are the operations that are potentially turned into a sequence 3126169689Skan of shifts and additions. */ 3127169689Skan if (SCALAR_INT_MODE_P (mode) 3128169689Skan && (unsignedp || !flag_trapv)) 3129169689Skan { 3130169689Skan HOST_WIDE_INT coeff = 0; 3131169689Skan rtx fake_reg = gen_raw_REG (mode, LAST_VIRTUAL_REGISTER + 1); 3132169689Skan 3133169689Skan /* synth_mult does an `unsigned int' multiply. As long as the mode is 3134169689Skan less than or equal in size to `unsigned int' this doesn't matter. 3135169689Skan If the mode is larger than `unsigned int', then synth_mult works 3136169689Skan only if the constant value exactly fits in an `unsigned int' without 3137169689Skan any truncation. This means that multiplying by negative values does 3138169689Skan not work; results are off by 2^32 on a 32 bit machine. */ 3139169689Skan 3140169689Skan if (GET_CODE (op1) == CONST_INT) 3141169689Skan { 3142169689Skan /* Attempt to handle multiplication of DImode values by negative 3143169689Skan coefficients, by performing the multiplication by a positive 3144169689Skan multiplier and then inverting the result. */ 3145169689Skan if (INTVAL (op1) < 0 3146169689Skan && GET_MODE_BITSIZE (mode) > HOST_BITS_PER_WIDE_INT) 314718334Speter { 3148169689Skan /* Its safe to use -INTVAL (op1) even for INT_MIN, as the 3149169689Skan result is interpreted as an unsigned coefficient. 3150169689Skan Exclude cost of op0 from max_cost to match the cost 3151169689Skan calculation of the synth_mult. */ 3152169689Skan max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET) 3153169689Skan - neg_cost[mode]; 3154169689Skan if (max_cost > 0 3155169689Skan && choose_mult_variant (mode, -INTVAL (op1), &algorithm, 3156169689Skan &variant, max_cost)) 3157169689Skan { 3158169689Skan rtx temp = expand_mult_const (mode, op0, -INTVAL (op1), 3159169689Skan NULL_RTX, &algorithm, 3160169689Skan variant); 3161169689Skan return expand_unop (mode, neg_optab, temp, target, 0); 3162169689Skan } 316318334Speter } 3164169689Skan else coeff = INTVAL (op1); 3165169689Skan } 3166169689Skan else if (GET_CODE (op1) == CONST_DOUBLE) 3167169689Skan { 3168169689Skan /* If we are multiplying in DImode, it may still be a win 3169169689Skan to try to work with shifts and adds. */ 3170169689Skan if (CONST_DOUBLE_HIGH (op1) == 0) 3171169689Skan coeff = CONST_DOUBLE_LOW (op1); 3172169689Skan else if (CONST_DOUBLE_LOW (op1) == 0 3173169689Skan && EXACT_POWER_OF_2_OR_ZERO_P (CONST_DOUBLE_HIGH (op1))) 317418334Speter { 3175169689Skan int shift = floor_log2 (CONST_DOUBLE_HIGH (op1)) 3176169689Skan + HOST_BITS_PER_WIDE_INT; 3177169689Skan return expand_shift (LSHIFT_EXPR, mode, op0, 3178169689Skan build_int_cst (NULL_TREE, shift), 3179169689Skan target, unsignedp); 318018334Speter } 3181169689Skan } 3182169689Skan 3183169689Skan /* We used to test optimize here, on the grounds that it's better to 3184169689Skan produce a smaller program when -O is not used. But this causes 3185169689Skan such a terrible slowdown sometimes that it seems better to always 3186169689Skan use synth_mult. */ 3187169689Skan if (coeff != 0) 3188169689Skan { 3189169689Skan /* Special case powers of two. */ 3190169689Skan if (EXACT_POWER_OF_2_OR_ZERO_P (coeff)) 3191169689Skan return expand_shift (LSHIFT_EXPR, mode, op0, 3192169689Skan build_int_cst (NULL_TREE, floor_log2 (coeff)), 3193169689Skan target, unsignedp); 319418334Speter 3195169689Skan /* Exclude cost of op0 from max_cost to match the cost 3196169689Skan calculation of the synth_mult. */ 3197169689Skan max_cost = rtx_cost (gen_rtx_MULT (mode, fake_reg, op1), SET); 3198169689Skan if (choose_mult_variant (mode, coeff, &algorithm, &variant, 3199169689Skan max_cost)) 3200169689Skan return expand_mult_const (mode, op0, coeff, target, 3201169689Skan &algorithm, variant); 320218334Speter } 320318334Speter } 320418334Speter 3205132718Skan if (GET_CODE (op0) == CONST_DOUBLE) 3206132718Skan { 3207132718Skan rtx temp = op0; 3208132718Skan op0 = op1; 3209132718Skan op1 = temp; 3210132718Skan } 3211132718Skan 3212132718Skan /* Expand x*2.0 as x+x. */ 3213132718Skan if (GET_CODE (op1) == CONST_DOUBLE 3214169689Skan && SCALAR_FLOAT_MODE_P (mode)) 3215132718Skan { 3216132718Skan REAL_VALUE_TYPE d; 3217132718Skan REAL_VALUE_FROM_CONST_DOUBLE (d, op1); 3218132718Skan 3219132718Skan if (REAL_VALUES_EQUAL (d, dconst2)) 3220132718Skan { 3221132718Skan op0 = force_reg (GET_MODE (op0), op0); 3222132718Skan return expand_binop (mode, add_optab, op0, op0, 3223132718Skan target, unsignedp, OPTAB_LIB_WIDEN); 3224132718Skan } 3225132718Skan } 3226132718Skan 322718334Speter /* This used to use umul_optab if unsigned, but for non-widening multiply 322818334Speter there is no difference between signed and unsigned. */ 322996263Sobrien op0 = expand_binop (mode, 323090075Sobrien ! unsignedp 3231117395Skan && flag_trapv && (GET_MODE_CLASS(mode) == MODE_INT) 3232117395Skan ? smulv_optab : smul_optab, 323318334Speter op0, op1, target, unsignedp, OPTAB_LIB_WIDEN); 3234169689Skan gcc_assert (op0); 323518334Speter return op0; 323618334Speter} 323718334Speter 323818334Speter/* Return the smallest n such that 2**n >= X. */ 323918334Speter 324018334Speterint 3241132718Skanceil_log2 (unsigned HOST_WIDE_INT x) 324218334Speter{ 324318334Speter return floor_log2 (x - 1) + 1; 324418334Speter} 324518334Speter 324618334Speter/* Choose a minimal N + 1 bit approximation to 1/D that can be used to 324718334Speter replace division by D, and put the least significant N bits of the result 324818334Speter in *MULTIPLIER_PTR and return the most significant bit. 324918334Speter 325018334Speter The width of operations is N (should be <= HOST_BITS_PER_WIDE_INT), the 325118334Speter needed precision is in PRECISION (should be <= N). 325218334Speter 325318334Speter PRECISION should be as small as possible so this function can choose 325418334Speter multiplier more freely. 325518334Speter 325618334Speter The rounded-up logarithm of D is placed in *lgup_ptr. A shift count that 325718334Speter is to be used for a final right shift is placed in *POST_SHIFT_PTR. 325818334Speter 325918334Speter Using this function, x/D will be equal to (x * m) >> (*POST_SHIFT_PTR), 326018334Speter where m is the full HOST_BITS_PER_WIDE_INT + 1 bit multiplier. */ 326118334Speter 326218334Speterstatic 326318334Speterunsigned HOST_WIDE_INT 3264132718Skanchoose_multiplier (unsigned HOST_WIDE_INT d, int n, int precision, 3265169689Skan rtx *multiplier_ptr, int *post_shift_ptr, int *lgup_ptr) 326618334Speter{ 326790075Sobrien HOST_WIDE_INT mhigh_hi, mlow_hi; 326890075Sobrien unsigned HOST_WIDE_INT mhigh_lo, mlow_lo; 326918334Speter int lgup, post_shift; 327018334Speter int pow, pow2; 327190075Sobrien unsigned HOST_WIDE_INT nl, dummy1; 327290075Sobrien HOST_WIDE_INT nh, dummy2; 327318334Speter 327418334Speter /* lgup = ceil(log2(divisor)); */ 327518334Speter lgup = ceil_log2 (d); 327618334Speter 3277169689Skan gcc_assert (lgup <= n); 327818334Speter 327918334Speter pow = n + lgup; 328018334Speter pow2 = n + lgup - precision; 328118334Speter 3282169689Skan /* We could handle this with some effort, but this case is much 3283169689Skan better handled directly with a scc insn, so rely on caller using 3284169689Skan that. */ 3285169689Skan gcc_assert (pow != 2 * HOST_BITS_PER_WIDE_INT); 328618334Speter 328718334Speter /* mlow = 2^(N + lgup)/d */ 328818334Speter if (pow >= HOST_BITS_PER_WIDE_INT) 328918334Speter { 329090075Sobrien nh = (HOST_WIDE_INT) 1 << (pow - HOST_BITS_PER_WIDE_INT); 329118334Speter nl = 0; 329218334Speter } 329318334Speter else 329418334Speter { 329518334Speter nh = 0; 329618334Speter nl = (unsigned HOST_WIDE_INT) 1 << pow; 329718334Speter } 329818334Speter div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0, 329918334Speter &mlow_lo, &mlow_hi, &dummy1, &dummy2); 330018334Speter 330118334Speter /* mhigh = (2^(N + lgup) + 2^N + lgup - precision)/d */ 330218334Speter if (pow2 >= HOST_BITS_PER_WIDE_INT) 330390075Sobrien nh |= (HOST_WIDE_INT) 1 << (pow2 - HOST_BITS_PER_WIDE_INT); 330418334Speter else 330518334Speter nl |= (unsigned HOST_WIDE_INT) 1 << pow2; 330618334Speter div_and_round_double (TRUNC_DIV_EXPR, 1, nl, nh, d, (HOST_WIDE_INT) 0, 330718334Speter &mhigh_lo, &mhigh_hi, &dummy1, &dummy2); 330818334Speter 3309169689Skan gcc_assert (!mhigh_hi || nh - d < d); 3310169689Skan gcc_assert (mhigh_hi <= 1 && mlow_hi <= 1); 3311132718Skan /* Assert that mlow < mhigh. */ 3312169689Skan gcc_assert (mlow_hi < mhigh_hi 3313169689Skan || (mlow_hi == mhigh_hi && mlow_lo < mhigh_lo)); 331418334Speter 331518334Speter /* If precision == N, then mlow, mhigh exceed 2^N 331618334Speter (but they do not exceed 2^(N+1)). */ 331718334Speter 3318132718Skan /* Reduce to lowest terms. */ 331918334Speter for (post_shift = lgup; post_shift > 0; post_shift--) 332018334Speter { 332118334Speter unsigned HOST_WIDE_INT ml_lo = (mlow_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mlow_lo >> 1); 332218334Speter unsigned HOST_WIDE_INT mh_lo = (mhigh_hi << (HOST_BITS_PER_WIDE_INT - 1)) | (mhigh_lo >> 1); 332318334Speter if (ml_lo >= mh_lo) 332418334Speter break; 332518334Speter 332618334Speter mlow_hi = 0; 332718334Speter mlow_lo = ml_lo; 332818334Speter mhigh_hi = 0; 332918334Speter mhigh_lo = mh_lo; 333018334Speter } 333118334Speter 333218334Speter *post_shift_ptr = post_shift; 333318334Speter *lgup_ptr = lgup; 333418334Speter if (n < HOST_BITS_PER_WIDE_INT) 333518334Speter { 333618334Speter unsigned HOST_WIDE_INT mask = ((unsigned HOST_WIDE_INT) 1 << n) - 1; 3337169689Skan *multiplier_ptr = GEN_INT (mhigh_lo & mask); 333818334Speter return mhigh_lo >= mask; 333918334Speter } 334018334Speter else 334118334Speter { 3342169689Skan *multiplier_ptr = GEN_INT (mhigh_lo); 334318334Speter return mhigh_hi; 334418334Speter } 334518334Speter} 334618334Speter 334718334Speter/* Compute the inverse of X mod 2**n, i.e., find Y such that X * Y is 334818334Speter congruent to 1 (mod 2**N). */ 334918334Speter 335018334Speterstatic unsigned HOST_WIDE_INT 3351132718Skaninvert_mod2n (unsigned HOST_WIDE_INT x, int n) 335218334Speter{ 335350397Sobrien /* Solve x*y == 1 (mod 2^n), where x is odd. Return y. */ 335418334Speter 335518334Speter /* The algorithm notes that the choice y = x satisfies 335618334Speter x*y == 1 mod 2^3, since x is assumed odd. 335718334Speter Each iteration doubles the number of bits of significance in y. */ 335818334Speter 335918334Speter unsigned HOST_WIDE_INT mask; 336018334Speter unsigned HOST_WIDE_INT y = x; 336118334Speter int nbit = 3; 336218334Speter 336318334Speter mask = (n == HOST_BITS_PER_WIDE_INT 336418334Speter ? ~(unsigned HOST_WIDE_INT) 0 336518334Speter : ((unsigned HOST_WIDE_INT) 1 << n) - 1); 336618334Speter 336718334Speter while (nbit < n) 336818334Speter { 336918334Speter y = y * (2 - x*y) & mask; /* Modulo 2^N */ 337018334Speter nbit *= 2; 337118334Speter } 337218334Speter return y; 337318334Speter} 337418334Speter 337518334Speter/* Emit code to adjust ADJ_OPERAND after multiplication of wrong signedness 337618334Speter flavor of OP0 and OP1. ADJ_OPERAND is already the high half of the 337718334Speter product OP0 x OP1. If UNSIGNEDP is nonzero, adjust the signed product 337818334Speter to become unsigned, if UNSIGNEDP is zero, adjust the unsigned product to 337918334Speter become signed. 338018334Speter 338118334Speter The result is put in TARGET if that is convenient. 338218334Speter 338318334Speter MODE is the mode of operation. */ 338418334Speter 338518334Speterrtx 3386132718Skanexpand_mult_highpart_adjust (enum machine_mode mode, rtx adj_operand, rtx op0, 3387132718Skan rtx op1, rtx target, int unsignedp) 338818334Speter{ 338918334Speter rtx tem; 339018334Speter enum rtx_code adj_code = unsignedp ? PLUS : MINUS; 339118334Speter 339218334Speter tem = expand_shift (RSHIFT_EXPR, mode, op0, 3393169689Skan build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1), 339418334Speter NULL_RTX, 0); 339596263Sobrien tem = expand_and (mode, tem, op1, NULL_RTX); 339650397Sobrien adj_operand 339750397Sobrien = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem), 339850397Sobrien adj_operand); 339918334Speter 340018334Speter tem = expand_shift (RSHIFT_EXPR, mode, op1, 3401169689Skan build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode) - 1), 340218334Speter NULL_RTX, 0); 340396263Sobrien tem = expand_and (mode, tem, op0, NULL_RTX); 340450397Sobrien target = force_operand (gen_rtx_fmt_ee (adj_code, mode, adj_operand, tem), 340550397Sobrien target); 340618334Speter 340718334Speter return target; 340818334Speter} 340918334Speter 3410169689Skan/* Subroutine of expand_mult_highpart. Return the MODE high part of OP. */ 341118334Speter 3412169689Skanstatic rtx 3413169689Skanextract_high_half (enum machine_mode mode, rtx op) 3414169689Skan{ 3415169689Skan enum machine_mode wider_mode; 341618334Speter 3417169689Skan if (mode == word_mode) 3418169689Skan return gen_highpart (mode, op); 341918334Speter 3420169689Skan gcc_assert (!SCALAR_FLOAT_MODE_P (mode)); 342118334Speter 3422169689Skan wider_mode = GET_MODE_WIDER_MODE (mode); 3423169689Skan op = expand_shift (RSHIFT_EXPR, wider_mode, op, 3424169689Skan build_int_cst (NULL_TREE, GET_MODE_BITSIZE (mode)), 0, 1); 3425169689Skan return convert_modes (mode, wider_mode, op, 0); 3426169689Skan} 3427169689Skan 3428169689Skan/* Like expand_mult_highpart, but only consider using a multiplication 3429169689Skan optab. OP1 is an rtx for the constant operand. */ 3430169689Skan 3431169689Skanstatic rtx 3432169689Skanexpand_mult_highpart_optab (enum machine_mode mode, rtx op0, rtx op1, 3433169689Skan rtx target, int unsignedp, int max_cost) 343418334Speter{ 3435169689Skan rtx narrow_op1 = gen_int_mode (INTVAL (op1), mode); 3436169689Skan enum machine_mode wider_mode; 343718334Speter optab moptab; 343818334Speter rtx tem; 3439169689Skan int size; 344018334Speter 3441169689Skan gcc_assert (!SCALAR_FLOAT_MODE_P (mode)); 344218334Speter 3443169689Skan wider_mode = GET_MODE_WIDER_MODE (mode); 3444169689Skan size = GET_MODE_BITSIZE (mode); 344518334Speter 344618334Speter /* Firstly, try using a multiplication insn that only generates the needed 344718334Speter high part of the product, and in the sign flavor of unsignedp. */ 3448169689Skan if (mul_highpart_cost[mode] < max_cost) 344918334Speter { 3450169689Skan moptab = unsignedp ? umul_highpart_optab : smul_highpart_optab; 3451169689Skan tem = expand_binop (mode, moptab, op0, narrow_op1, target, 3452169689Skan unsignedp, OPTAB_DIRECT); 3453169689Skan if (tem) 3454169689Skan return tem; 345518334Speter } 345618334Speter 345718334Speter /* Secondly, same as above, but use sign flavor opposite of unsignedp. 345818334Speter Need to adjust the result after the multiplication. */ 345990075Sobrien if (size - 1 < BITS_PER_WORD 3460169689Skan && (mul_highpart_cost[mode] + 2 * shift_cost[mode][size-1] 3461169689Skan + 4 * add_cost[mode] < max_cost)) 346218334Speter { 3463169689Skan moptab = unsignedp ? smul_highpart_optab : umul_highpart_optab; 3464169689Skan tem = expand_binop (mode, moptab, op0, narrow_op1, target, 3465169689Skan unsignedp, OPTAB_DIRECT); 3466169689Skan if (tem) 346718334Speter /* We used the wrong signedness. Adjust the result. */ 3468169689Skan return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1, 3469169689Skan tem, unsignedp); 347018334Speter } 347118334Speter 347218334Speter /* Try widening multiplication. */ 347318334Speter moptab = unsignedp ? umul_widen_optab : smul_widen_optab; 3474169689Skan if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing 3475169689Skan && mul_widen_cost[wider_mode] < max_cost) 347650397Sobrien { 3477169689Skan tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 0, 3478169689Skan unsignedp, OPTAB_WIDEN); 3479169689Skan if (tem) 3480169689Skan return extract_high_half (mode, tem); 348196263Sobrien } 348218334Speter 348318334Speter /* Try widening the mode and perform a non-widening multiplication. */ 3484169689Skan if (smul_optab->handlers[wider_mode].insn_code != CODE_FOR_nothing 348590075Sobrien && size - 1 < BITS_PER_WORD 3486169689Skan && mul_cost[wider_mode] + shift_cost[mode][size-1] < max_cost) 348750397Sobrien { 3488169689Skan rtx insns, wop0, wop1; 3489169689Skan 3490169689Skan /* We need to widen the operands, for example to ensure the 3491169689Skan constant multiplier is correctly sign or zero extended. 3492169689Skan Use a sequence to clean-up any instructions emitted by 3493169689Skan the conversions if things don't work out. */ 3494169689Skan start_sequence (); 3495169689Skan wop0 = convert_modes (wider_mode, mode, op0, unsignedp); 3496169689Skan wop1 = convert_modes (wider_mode, mode, op1, unsignedp); 3497169689Skan tem = expand_binop (wider_mode, smul_optab, wop0, wop1, 0, 3498169689Skan unsignedp, OPTAB_WIDEN); 3499169689Skan insns = get_insns (); 3500169689Skan end_sequence (); 3501169689Skan 3502169689Skan if (tem) 3503169689Skan { 3504169689Skan emit_insn (insns); 3505169689Skan return extract_high_half (mode, tem); 3506169689Skan } 350750397Sobrien } 350818334Speter 350918334Speter /* Try widening multiplication of opposite signedness, and adjust. */ 351018334Speter moptab = unsignedp ? smul_widen_optab : umul_widen_optab; 3511169689Skan if (moptab->handlers[wider_mode].insn_code != CODE_FOR_nothing 351290075Sobrien && size - 1 < BITS_PER_WORD 3513169689Skan && (mul_widen_cost[wider_mode] + 2 * shift_cost[mode][size-1] 3514169689Skan + 4 * add_cost[mode] < max_cost)) 351518334Speter { 3516169689Skan tem = expand_binop (wider_mode, moptab, op0, narrow_op1, 351718334Speter NULL_RTX, ! unsignedp, OPTAB_WIDEN); 351818334Speter if (tem != 0) 351918334Speter { 3520169689Skan tem = extract_high_half (mode, tem); 352118334Speter /* We used the wrong signedness. Adjust the result. */ 3522169689Skan return expand_mult_highpart_adjust (mode, tem, op0, narrow_op1, 352318334Speter target, unsignedp); 352418334Speter } 352518334Speter } 352618334Speter 352718334Speter return 0; 3528169689Skan} 352918334Speter 3530169689Skan/* Emit code to multiply OP0 and OP1 (where OP1 is an integer constant), 3531169689Skan putting the high half of the result in TARGET if that is convenient, 3532169689Skan and return where the result is. If the operation can not be performed, 3533169689Skan 0 is returned. 353418334Speter 3535169689Skan MODE is the mode of operation and result. 3536169689Skan 3537169689Skan UNSIGNEDP nonzero means unsigned multiply. 3538169689Skan 3539169689Skan MAX_COST is the total allowed cost for the expanded RTL. */ 3540169689Skan 3541169689Skanstatic rtx 3542169689Skanexpand_mult_highpart (enum machine_mode mode, rtx op0, rtx op1, 3543169689Skan rtx target, int unsignedp, int max_cost) 3544169689Skan{ 3545169689Skan enum machine_mode wider_mode = GET_MODE_WIDER_MODE (mode); 3546169689Skan unsigned HOST_WIDE_INT cnst1; 3547169689Skan int extra_cost; 3548169689Skan bool sign_adjust = false; 3549169689Skan enum mult_variant variant; 3550169689Skan struct algorithm alg; 3551169689Skan rtx tem; 3552169689Skan 3553169689Skan gcc_assert (!SCALAR_FLOAT_MODE_P (mode)); 3554169689Skan /* We can't support modes wider than HOST_BITS_PER_INT. */ 3555169689Skan gcc_assert (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT); 3556169689Skan 3557169689Skan cnst1 = INTVAL (op1) & GET_MODE_MASK (mode); 3558169689Skan 3559169689Skan /* We can't optimize modes wider than BITS_PER_WORD. 3560169689Skan ??? We might be able to perform double-word arithmetic if 3561169689Skan mode == word_mode, however all the cost calculations in 3562169689Skan synth_mult etc. assume single-word operations. */ 3563169689Skan if (GET_MODE_BITSIZE (wider_mode) > BITS_PER_WORD) 3564169689Skan return expand_mult_highpart_optab (mode, op0, op1, target, 3565169689Skan unsignedp, max_cost); 3566169689Skan 3567169689Skan extra_cost = shift_cost[mode][GET_MODE_BITSIZE (mode) - 1]; 3568169689Skan 3569169689Skan /* Check whether we try to multiply by a negative constant. */ 3570169689Skan if (!unsignedp && ((cnst1 >> (GET_MODE_BITSIZE (mode) - 1)) & 1)) 357150397Sobrien { 3572169689Skan sign_adjust = true; 3573169689Skan extra_cost += add_cost[mode]; 357450397Sobrien } 3575169689Skan 3576169689Skan /* See whether shift/add multiplication is cheap enough. */ 3577169689Skan if (choose_mult_variant (wider_mode, cnst1, &alg, &variant, 3578169689Skan max_cost - extra_cost)) 3579169689Skan { 3580169689Skan /* See whether the specialized multiplication optabs are 3581169689Skan cheaper than the shift/add version. */ 3582169689Skan tem = expand_mult_highpart_optab (mode, op0, op1, target, unsignedp, 3583169689Skan alg.cost.cost + extra_cost); 3584169689Skan if (tem) 3585169689Skan return tem; 3586169689Skan 3587169689Skan tem = convert_to_mode (wider_mode, op0, unsignedp); 3588169689Skan tem = expand_mult_const (wider_mode, tem, cnst1, 0, &alg, variant); 3589169689Skan tem = extract_high_half (mode, tem); 3590169689Skan 3591169689Skan /* Adjust result for signedness. */ 3592169689Skan if (sign_adjust) 3593169689Skan tem = force_operand (gen_rtx_MINUS (mode, tem, op0), tem); 3594169689Skan 3595169689Skan return tem; 3596169689Skan } 3597169689Skan return expand_mult_highpart_optab (mode, op0, op1, target, 3598169689Skan unsignedp, max_cost); 3599169689Skan} 3600169689Skan 3601169689Skan 3602169689Skan/* Expand signed modulus of OP0 by a power of two D in mode MODE. */ 3603169689Skan 3604169689Skanstatic rtx 3605169689Skanexpand_smod_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d) 3606169689Skan{ 3607169689Skan unsigned HOST_WIDE_INT masklow, maskhigh; 3608169689Skan rtx result, temp, shift, label; 3609169689Skan int logd; 3610169689Skan 3611169689Skan logd = floor_log2 (d); 3612169689Skan result = gen_reg_rtx (mode); 3613169689Skan 3614169689Skan /* Avoid conditional branches when they're expensive. */ 3615169689Skan if (BRANCH_COST >= 2 3616169689Skan && !optimize_size) 3617169689Skan { 3618169689Skan rtx signmask = emit_store_flag (result, LT, op0, const0_rtx, 3619169689Skan mode, 0, -1); 3620169689Skan if (signmask) 3621169689Skan { 3622169689Skan signmask = force_reg (mode, signmask); 3623169689Skan masklow = ((HOST_WIDE_INT) 1 << logd) - 1; 3624169689Skan shift = GEN_INT (GET_MODE_BITSIZE (mode) - logd); 3625169689Skan 3626169689Skan /* Use the rtx_cost of a LSHIFTRT instruction to determine 3627169689Skan which instruction sequence to use. If logical right shifts 3628169689Skan are expensive the use 2 XORs, 2 SUBs and an AND, otherwise 3629169689Skan use a LSHIFTRT, 1 ADD, 1 SUB and an AND. */ 3630169689Skan 3631169689Skan temp = gen_rtx_LSHIFTRT (mode, result, shift); 3632169689Skan if (lshr_optab->handlers[mode].insn_code == CODE_FOR_nothing 3633169689Skan || rtx_cost (temp, SET) > COSTS_N_INSNS (2)) 3634169689Skan { 3635169689Skan temp = expand_binop (mode, xor_optab, op0, signmask, 3636169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3637169689Skan temp = expand_binop (mode, sub_optab, temp, signmask, 3638169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3639169689Skan temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow), 3640169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3641169689Skan temp = expand_binop (mode, xor_optab, temp, signmask, 3642169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3643169689Skan temp = expand_binop (mode, sub_optab, temp, signmask, 3644169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3645169689Skan } 3646169689Skan else 3647169689Skan { 3648169689Skan signmask = expand_binop (mode, lshr_optab, signmask, shift, 3649169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3650169689Skan signmask = force_reg (mode, signmask); 3651169689Skan 3652169689Skan temp = expand_binop (mode, add_optab, op0, signmask, 3653169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3654169689Skan temp = expand_binop (mode, and_optab, temp, GEN_INT (masklow), 3655169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3656169689Skan temp = expand_binop (mode, sub_optab, temp, signmask, 3657169689Skan NULL_RTX, 1, OPTAB_LIB_WIDEN); 3658169689Skan } 3659169689Skan return temp; 3660169689Skan } 3661169689Skan } 3662169689Skan 3663169689Skan /* Mask contains the mode's signbit and the significant bits of the 3664169689Skan modulus. By including the signbit in the operation, many targets 3665169689Skan can avoid an explicit compare operation in the following comparison 3666169689Skan against zero. */ 3667169689Skan 3668169689Skan masklow = ((HOST_WIDE_INT) 1 << logd) - 1; 3669169689Skan if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT) 3670169689Skan { 3671169689Skan masklow |= (HOST_WIDE_INT) -1 << (GET_MODE_BITSIZE (mode) - 1); 3672169689Skan maskhigh = -1; 3673169689Skan } 367450397Sobrien else 3675169689Skan maskhigh = (HOST_WIDE_INT) -1 3676169689Skan << (GET_MODE_BITSIZE (mode) - HOST_BITS_PER_WIDE_INT - 1); 3677169689Skan 3678169689Skan temp = expand_binop (mode, and_optab, op0, 3679169689Skan immed_double_const (masklow, maskhigh, mode), 3680169689Skan result, 1, OPTAB_LIB_WIDEN); 3681169689Skan if (temp != result) 3682169689Skan emit_move_insn (result, temp); 3683169689Skan 3684169689Skan label = gen_label_rtx (); 3685169689Skan do_cmp_and_jump (result, const0_rtx, GE, mode, label); 3686169689Skan 3687169689Skan temp = expand_binop (mode, sub_optab, result, const1_rtx, result, 3688169689Skan 0, OPTAB_LIB_WIDEN); 3689169689Skan masklow = (HOST_WIDE_INT) -1 << logd; 3690169689Skan maskhigh = -1; 3691169689Skan temp = expand_binop (mode, ior_optab, temp, 3692169689Skan immed_double_const (masklow, maskhigh, mode), 3693169689Skan result, 1, OPTAB_LIB_WIDEN); 3694169689Skan temp = expand_binop (mode, add_optab, temp, const1_rtx, result, 3695169689Skan 0, OPTAB_LIB_WIDEN); 3696169689Skan if (temp != result) 3697169689Skan emit_move_insn (result, temp); 3698169689Skan emit_label (label); 3699169689Skan return result; 3700169689Skan} 3701169689Skan 3702169689Skan/* Expand signed division of OP0 by a power of two D in mode MODE. 3703169689Skan This routine is only called for positive values of D. */ 3704169689Skan 3705169689Skanstatic rtx 3706169689Skanexpand_sdiv_pow2 (enum machine_mode mode, rtx op0, HOST_WIDE_INT d) 3707169689Skan{ 3708169689Skan rtx temp, label; 3709169689Skan tree shift; 3710169689Skan int logd; 3711169689Skan 3712169689Skan logd = floor_log2 (d); 3713169689Skan shift = build_int_cst (NULL_TREE, logd); 3714169689Skan 3715169689Skan if (d == 2 && BRANCH_COST >= 1) 371650397Sobrien { 3717169689Skan temp = gen_reg_rtx (mode); 3718169689Skan temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, 1); 3719169689Skan temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX, 3720169689Skan 0, OPTAB_LIB_WIDEN); 3721169689Skan return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 372250397Sobrien } 3723169689Skan 3724169689Skan#ifdef HAVE_conditional_move 3725169689Skan if (BRANCH_COST >= 2) 3726169689Skan { 3727169689Skan rtx temp2; 3728169689Skan 3729169689Skan /* ??? emit_conditional_move forces a stack adjustment via 3730169689Skan compare_from_rtx so, if the sequence is discarded, it will 3731169689Skan be lost. Do it now instead. */ 3732169689Skan do_pending_stack_adjust (); 3733169689Skan 3734169689Skan start_sequence (); 3735169689Skan temp2 = copy_to_mode_reg (mode, op0); 3736169689Skan temp = expand_binop (mode, add_optab, temp2, GEN_INT (d-1), 3737169689Skan NULL_RTX, 0, OPTAB_LIB_WIDEN); 3738169689Skan temp = force_reg (mode, temp); 3739169689Skan 3740169689Skan /* Construct "temp2 = (temp2 < 0) ? temp : temp2". */ 3741169689Skan temp2 = emit_conditional_move (temp2, LT, temp2, const0_rtx, 3742169689Skan mode, temp, temp2, mode, 0); 3743169689Skan if (temp2) 3744169689Skan { 3745169689Skan rtx seq = get_insns (); 3746169689Skan end_sequence (); 3747169689Skan emit_insn (seq); 3748169689Skan return expand_shift (RSHIFT_EXPR, mode, temp2, shift, NULL_RTX, 0); 3749169689Skan } 3750169689Skan end_sequence (); 3751169689Skan } 3752169689Skan#endif 3753169689Skan 3754169689Skan if (BRANCH_COST >= 2) 3755169689Skan { 3756169689Skan int ushift = GET_MODE_BITSIZE (mode) - logd; 3757169689Skan 3758169689Skan temp = gen_reg_rtx (mode); 3759169689Skan temp = emit_store_flag (temp, LT, op0, const0_rtx, mode, 0, -1); 3760169689Skan if (shift_cost[mode][ushift] > COSTS_N_INSNS (1)) 3761169689Skan temp = expand_binop (mode, and_optab, temp, GEN_INT (d - 1), 3762169689Skan NULL_RTX, 0, OPTAB_LIB_WIDEN); 3763169689Skan else 3764169689Skan temp = expand_shift (RSHIFT_EXPR, mode, temp, 3765169689Skan build_int_cst (NULL_TREE, ushift), 3766169689Skan NULL_RTX, 1); 3767169689Skan temp = expand_binop (mode, add_optab, temp, op0, NULL_RTX, 3768169689Skan 0, OPTAB_LIB_WIDEN); 3769169689Skan return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 3770169689Skan } 3771169689Skan 3772169689Skan label = gen_label_rtx (); 3773169689Skan temp = copy_to_mode_reg (mode, op0); 3774169689Skan do_cmp_and_jump (temp, const0_rtx, GE, mode, label); 3775169689Skan expand_inc (temp, GEN_INT (d - 1)); 3776169689Skan emit_label (label); 3777169689Skan return expand_shift (RSHIFT_EXPR, mode, temp, shift, NULL_RTX, 0); 377818334Speter} 377918334Speter 378018334Speter/* Emit the code to divide OP0 by OP1, putting the result in TARGET 378118334Speter if that is convenient, and returning where the result is. 378218334Speter You may request either the quotient or the remainder as the result; 378318334Speter specify REM_FLAG nonzero to get the remainder. 378418334Speter 378518334Speter CODE is the expression code for which kind of division this is; 378618334Speter it controls how rounding is done. MODE is the machine mode to use. 378718334Speter UNSIGNEDP nonzero means do unsigned division. */ 378818334Speter 378918334Speter/* ??? For CEIL_MOD_EXPR, can compute incorrect remainder with ANDI 379018334Speter and then correct it by or'ing in missing high bits 379118334Speter if result of ANDI is nonzero. 379218334Speter For ROUND_MOD_EXPR, can use ANDI and then sign-extend the result. 379318334Speter This could optimize to a bfexts instruction. 379418334Speter But C doesn't use these operations, so their optimizations are 379518334Speter left for later. */ 379652284Sobrien/* ??? For modulo, we don't actually need the highpart of the first product, 379752284Sobrien the low part will do nicely. And for small divisors, the second multiply 379852284Sobrien can also be a low-part only multiply or even be completely left out. 379952284Sobrien E.g. to calculate the remainder of a division by 3 with a 32 bit 380052284Sobrien multiply, multiply with 0x55555556 and extract the upper two bits; 380152284Sobrien the result is exact for inputs up to 0x1fffffff. 380252284Sobrien The input range can be reduced by using cross-sum rules. 380352284Sobrien For odd divisors >= 3, the following table gives right shift counts 3804117395Skan so that if a number is shifted by an integer multiple of the given 380552284Sobrien amount, the remainder stays the same: 380652284Sobrien 2, 4, 3, 6, 10, 12, 4, 8, 18, 6, 11, 20, 18, 0, 5, 10, 12, 0, 12, 20, 380752284Sobrien 14, 12, 23, 21, 8, 0, 20, 18, 0, 0, 6, 12, 0, 22, 0, 18, 20, 30, 0, 0, 380852284Sobrien 0, 8, 0, 11, 12, 10, 36, 0, 30, 0, 0, 12, 0, 0, 0, 0, 44, 12, 24, 0, 380952284Sobrien 20, 0, 7, 14, 0, 18, 36, 0, 0, 46, 60, 0, 42, 0, 15, 24, 20, 0, 0, 33, 381052284Sobrien 0, 20, 0, 0, 18, 0, 60, 0, 0, 0, 0, 0, 40, 18, 0, 0, 12 381118334Speter 381252284Sobrien Cross-sum rules for even numbers can be derived by leaving as many bits 381352284Sobrien to the right alone as the divisor has zeros to the right. 381452284Sobrien E.g. if x is an unsigned 32 bit number: 381552284Sobrien (x mod 12) == (((x & 1023) + ((x >> 8) & ~3)) * 0x15555558 >> 2 * 3) >> 28 381652284Sobrien */ 381752284Sobrien 381818334Speterrtx 3819132718Skanexpand_divmod (int rem_flag, enum tree_code code, enum machine_mode mode, 3820132718Skan rtx op0, rtx op1, rtx target, int unsignedp) 382118334Speter{ 382218334Speter enum machine_mode compute_mode; 382390075Sobrien rtx tquotient; 382418334Speter rtx quotient = 0, remainder = 0; 382518334Speter rtx last; 382618334Speter int size; 382718334Speter rtx insn, set; 382818334Speter optab optab1, optab2; 3829132718Skan int op1_is_constant, op1_is_pow2 = 0; 383018334Speter int max_cost, extra_cost; 383150397Sobrien static HOST_WIDE_INT last_div_const = 0; 3832132718Skan static HOST_WIDE_INT ext_op1; 383318334Speter 383418334Speter op1_is_constant = GET_CODE (op1) == CONST_INT; 3835132718Skan if (op1_is_constant) 3836132718Skan { 3837132718Skan ext_op1 = INTVAL (op1); 3838132718Skan if (unsignedp) 3839132718Skan ext_op1 &= GET_MODE_MASK (mode); 3840132718Skan op1_is_pow2 = ((EXACT_POWER_OF_2_OR_ZERO_P (ext_op1) 3841132718Skan || (! unsignedp && EXACT_POWER_OF_2_OR_ZERO_P (-ext_op1)))); 3842132718Skan } 384318334Speter 384418334Speter /* 384518334Speter This is the structure of expand_divmod: 384618334Speter 384718334Speter First comes code to fix up the operands so we can perform the operations 384818334Speter correctly and efficiently. 384918334Speter 385018334Speter Second comes a switch statement with code specific for each rounding mode. 385118334Speter For some special operands this code emits all RTL for the desired 385218334Speter operation, for other cases, it generates only a quotient and stores it in 385318334Speter QUOTIENT. The case for trunc division/remainder might leave quotient = 0, 385418334Speter to indicate that it has not done anything. 385518334Speter 385618334Speter Last comes code that finishes the operation. If QUOTIENT is set and 385718334Speter REM_FLAG is set, the remainder is computed as OP0 - QUOTIENT * OP1. If 385818334Speter QUOTIENT is not set, it is computed using trunc rounding. 385918334Speter 386018334Speter We try to generate special code for division and remainder when OP1 is a 386118334Speter constant. If |OP1| = 2**n we can use shifts and some other fast 386218334Speter operations. For other values of OP1, we compute a carefully selected 386318334Speter fixed-point approximation m = 1/OP1, and generate code that multiplies OP0 386418334Speter by m. 386518334Speter 386618334Speter In all cases but EXACT_DIV_EXPR, this multiplication requires the upper 386718334Speter half of the product. Different strategies for generating the product are 386818334Speter implemented in expand_mult_highpart. 386918334Speter 387018334Speter If what we actually want is the remainder, we generate that by another 387118334Speter by-constant multiplication and a subtraction. */ 387218334Speter 387318334Speter /* We shouldn't be called with OP1 == const1_rtx, but some of the 387418334Speter code below will malfunction if we are, so check here and handle 387518334Speter the special case if so. */ 387618334Speter if (op1 == const1_rtx) 387718334Speter return rem_flag ? const0_rtx : op0; 387818334Speter 387990075Sobrien /* When dividing by -1, we could get an overflow. 388090075Sobrien negv_optab can handle overflows. */ 388190075Sobrien if (! unsignedp && op1 == constm1_rtx) 388290075Sobrien { 388390075Sobrien if (rem_flag) 3884117395Skan return const0_rtx; 388590075Sobrien return expand_unop (mode, flag_trapv && GET_MODE_CLASS(mode) == MODE_INT 3886117395Skan ? negv_optab : neg_optab, op0, target, 0); 388790075Sobrien } 388890075Sobrien 388918334Speter if (target 389018334Speter /* Don't use the function value register as a target 389118334Speter since we have to read it as well as write it, 389218334Speter and function-inlining gets confused by this. */ 389318334Speter && ((REG_P (target) && REG_FUNCTION_VALUE_P (target)) 389418334Speter /* Don't clobber an operand while doing a multi-step calculation. */ 389518334Speter || ((rem_flag || op1_is_constant) 389618334Speter && (reg_mentioned_p (target, op0) 3897169689Skan || (MEM_P (op0) && MEM_P (target)))) 389818334Speter || reg_mentioned_p (target, op1) 3899169689Skan || (MEM_P (op1) && MEM_P (target)))) 390018334Speter target = 0; 390118334Speter 390218334Speter /* Get the mode in which to perform this computation. Normally it will 390318334Speter be MODE, but sometimes we can't do the desired operation in MODE. 390418334Speter If so, pick a wider mode in which we can do the operation. Convert 390518334Speter to that mode at the start to avoid repeated conversions. 390618334Speter 390718334Speter First see what operations we need. These depend on the expression 390818334Speter we are evaluating. (We assume that divxx3 insns exist under the 390918334Speter same conditions that modxx3 insns and that these insns don't normally 391018334Speter fail. If these assumptions are not correct, we may generate less 391118334Speter efficient code in some cases.) 391218334Speter 391318334Speter Then see if we find a mode in which we can open-code that operation 391418334Speter (either a division, modulus, or shift). Finally, check for the smallest 391518334Speter mode for which we can do the operation with a library call. */ 391618334Speter 391718334Speter /* We might want to refine this now that we have division-by-constant 391818334Speter optimization. Since expand_mult_highpart tries so many variants, it is 391918334Speter not straightforward to generalize this. Maybe we should make an array 392018334Speter of possible modes in init_expmed? Save this for GCC 2.7. */ 392118334Speter 3922102780Skan optab1 = ((op1_is_pow2 && op1 != const0_rtx) 3923102780Skan ? (unsignedp ? lshr_optab : ashr_optab) 392418334Speter : (unsignedp ? udiv_optab : sdiv_optab)); 3925102780Skan optab2 = ((op1_is_pow2 && op1 != const0_rtx) 3926102780Skan ? optab1 3927102780Skan : (unsignedp ? udivmod_optab : sdivmod_optab)); 392818334Speter 392918334Speter for (compute_mode = mode; compute_mode != VOIDmode; 393018334Speter compute_mode = GET_MODE_WIDER_MODE (compute_mode)) 3931169689Skan if (optab1->handlers[compute_mode].insn_code != CODE_FOR_nothing 3932169689Skan || optab2->handlers[compute_mode].insn_code != CODE_FOR_nothing) 393318334Speter break; 393418334Speter 393518334Speter if (compute_mode == VOIDmode) 393618334Speter for (compute_mode = mode; compute_mode != VOIDmode; 393718334Speter compute_mode = GET_MODE_WIDER_MODE (compute_mode)) 3938169689Skan if (optab1->handlers[compute_mode].libfunc 3939169689Skan || optab2->handlers[compute_mode].libfunc) 394018334Speter break; 394118334Speter 3942169689Skan /* If we still couldn't find a mode, use MODE, but expand_binop will 3943169689Skan probably die. */ 394418334Speter if (compute_mode == VOIDmode) 394518334Speter compute_mode = mode; 394618334Speter 394718334Speter if (target && GET_MODE (target) == compute_mode) 394818334Speter tquotient = target; 394918334Speter else 395018334Speter tquotient = gen_reg_rtx (compute_mode); 395118334Speter 395218334Speter size = GET_MODE_BITSIZE (compute_mode); 395318334Speter#if 0 395418334Speter /* It should be possible to restrict the precision to GET_MODE_BITSIZE 395518334Speter (mode), and thereby get better code when OP1 is a constant. Do that 395618334Speter later. It will require going over all usages of SIZE below. */ 395718334Speter size = GET_MODE_BITSIZE (mode); 395818334Speter#endif 395918334Speter 396050397Sobrien /* Only deduct something for a REM if the last divide done was 396150397Sobrien for a different constant. Then set the constant of the last 396250397Sobrien divide. */ 3963169689Skan max_cost = unsignedp ? udiv_cost[compute_mode] : sdiv_cost[compute_mode]; 3964169689Skan if (rem_flag && ! (last_div_const != 0 && op1_is_constant 3965169689Skan && INTVAL (op1) == last_div_const)) 3966169689Skan max_cost -= mul_cost[compute_mode] + add_cost[compute_mode]; 396718334Speter 396850397Sobrien last_div_const = ! rem_flag && op1_is_constant ? INTVAL (op1) : 0; 396950397Sobrien 397018334Speter /* Now convert to the best mode to use. */ 397118334Speter if (compute_mode != mode) 397218334Speter { 397318334Speter op0 = convert_modes (compute_mode, mode, op0, unsignedp); 397418334Speter op1 = convert_modes (compute_mode, mode, op1, unsignedp); 397550397Sobrien 397650397Sobrien /* convert_modes may have placed op1 into a register, so we 397750397Sobrien must recompute the following. */ 397850397Sobrien op1_is_constant = GET_CODE (op1) == CONST_INT; 397950397Sobrien op1_is_pow2 = (op1_is_constant 398050397Sobrien && ((EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)) 398150397Sobrien || (! unsignedp 398250397Sobrien && EXACT_POWER_OF_2_OR_ZERO_P (-INTVAL (op1)))))) ; 398318334Speter } 398418334Speter 398518334Speter /* If one of the operands is a volatile MEM, copy it into a register. */ 398618334Speter 3987169689Skan if (MEM_P (op0) && MEM_VOLATILE_P (op0)) 398818334Speter op0 = force_reg (compute_mode, op0); 3989169689Skan if (MEM_P (op1) && MEM_VOLATILE_P (op1)) 399018334Speter op1 = force_reg (compute_mode, op1); 399118334Speter 399218334Speter /* If we need the remainder or if OP1 is constant, we need to 399318334Speter put OP0 in a register in case it has any queued subexpressions. */ 399418334Speter if (rem_flag || op1_is_constant) 399518334Speter op0 = force_reg (compute_mode, op0); 399618334Speter 399718334Speter last = get_last_insn (); 399818334Speter 399918334Speter /* Promote floor rounding to trunc rounding for unsigned operations. */ 400018334Speter if (unsignedp) 400118334Speter { 400218334Speter if (code == FLOOR_DIV_EXPR) 400318334Speter code = TRUNC_DIV_EXPR; 400418334Speter if (code == FLOOR_MOD_EXPR) 400518334Speter code = TRUNC_MOD_EXPR; 400650397Sobrien if (code == EXACT_DIV_EXPR && op1_is_pow2) 400750397Sobrien code = TRUNC_DIV_EXPR; 400818334Speter } 400918334Speter 401018334Speter if (op1 != const0_rtx) 401118334Speter switch (code) 401218334Speter { 401318334Speter case TRUNC_MOD_EXPR: 401418334Speter case TRUNC_DIV_EXPR: 401550397Sobrien if (op1_is_constant) 401618334Speter { 401718334Speter if (unsignedp) 401818334Speter { 4019169689Skan unsigned HOST_WIDE_INT mh; 402018334Speter int pre_shift, post_shift; 402118334Speter int dummy; 4022169689Skan rtx ml; 4023132718Skan unsigned HOST_WIDE_INT d = (INTVAL (op1) 4024132718Skan & GET_MODE_MASK (compute_mode)); 402518334Speter 402618334Speter if (EXACT_POWER_OF_2_OR_ZERO_P (d)) 402718334Speter { 402818334Speter pre_shift = floor_log2 (d); 402918334Speter if (rem_flag) 403018334Speter { 403150397Sobrien remainder 403250397Sobrien = expand_binop (compute_mode, and_optab, op0, 403350397Sobrien GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1), 403450397Sobrien remainder, 1, 403550397Sobrien OPTAB_LIB_WIDEN); 403618334Speter if (remainder) 403718334Speter return gen_lowpart (mode, remainder); 403818334Speter } 403918334Speter quotient = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4040169689Skan build_int_cst (NULL_TREE, 4041169689Skan pre_shift), 404218334Speter tquotient, 1); 404318334Speter } 404450397Sobrien else if (size <= HOST_BITS_PER_WIDE_INT) 404518334Speter { 404650397Sobrien if (d >= ((unsigned HOST_WIDE_INT) 1 << (size - 1))) 404718334Speter { 404850397Sobrien /* Most significant bit of divisor is set; emit an scc 404950397Sobrien insn. */ 405050397Sobrien quotient = emit_store_flag (tquotient, GEU, op0, op1, 405150397Sobrien compute_mode, 1, 1); 405250397Sobrien if (quotient == 0) 405318334Speter goto fail1; 405418334Speter } 405518334Speter else 405618334Speter { 405750397Sobrien /* Find a suitable multiplier and right shift count 405850397Sobrien instead of multiplying with D. */ 405918334Speter 406050397Sobrien mh = choose_multiplier (d, size, size, 406150397Sobrien &ml, &post_shift, &dummy); 406250397Sobrien 406350397Sobrien /* If the suggested multiplier is more than SIZE bits, 406450397Sobrien we can do better for even divisors, using an 406550397Sobrien initial right shift. */ 406650397Sobrien if (mh != 0 && (d & 1) == 0) 406750397Sobrien { 406850397Sobrien pre_shift = floor_log2 (d & -d); 406950397Sobrien mh = choose_multiplier (d >> pre_shift, size, 407050397Sobrien size - pre_shift, 407150397Sobrien &ml, &post_shift, &dummy); 4072169689Skan gcc_assert (!mh); 407350397Sobrien } 407450397Sobrien else 407550397Sobrien pre_shift = 0; 407650397Sobrien 407750397Sobrien if (mh != 0) 407850397Sobrien { 407950397Sobrien rtx t1, t2, t3, t4; 408050397Sobrien 408190075Sobrien if (post_shift - 1 >= BITS_PER_WORD) 408290075Sobrien goto fail1; 408390075Sobrien 4084169689Skan extra_cost 4085169689Skan = (shift_cost[compute_mode][post_shift - 1] 4086169689Skan + shift_cost[compute_mode][1] 4087169689Skan + 2 * add_cost[compute_mode]); 408850397Sobrien t1 = expand_mult_highpart (compute_mode, op0, ml, 408950397Sobrien NULL_RTX, 1, 409050397Sobrien max_cost - extra_cost); 409150397Sobrien if (t1 == 0) 409250397Sobrien goto fail1; 409350397Sobrien t2 = force_operand (gen_rtx_MINUS (compute_mode, 409450397Sobrien op0, t1), 409550397Sobrien NULL_RTX); 4096169689Skan t3 = expand_shift 4097169689Skan (RSHIFT_EXPR, compute_mode, t2, 4098169689Skan build_int_cst (NULL_TREE, 1), 4099169689Skan NULL_RTX,1); 410050397Sobrien t4 = force_operand (gen_rtx_PLUS (compute_mode, 410150397Sobrien t1, t3), 410250397Sobrien NULL_RTX); 4103169689Skan quotient = expand_shift 4104169689Skan (RSHIFT_EXPR, compute_mode, t4, 4105169689Skan build_int_cst (NULL_TREE, post_shift - 1), 4106169689Skan tquotient, 1); 410750397Sobrien } 410850397Sobrien else 410950397Sobrien { 411050397Sobrien rtx t1, t2; 411150397Sobrien 411290075Sobrien if (pre_shift >= BITS_PER_WORD 411390075Sobrien || post_shift >= BITS_PER_WORD) 411490075Sobrien goto fail1; 411590075Sobrien 4116169689Skan t1 = expand_shift 4117169689Skan (RSHIFT_EXPR, compute_mode, op0, 4118169689Skan build_int_cst (NULL_TREE, pre_shift), 4119169689Skan NULL_RTX, 1); 4120169689Skan extra_cost 4121169689Skan = (shift_cost[compute_mode][pre_shift] 4122169689Skan + shift_cost[compute_mode][post_shift]); 412350397Sobrien t2 = expand_mult_highpart (compute_mode, t1, ml, 412450397Sobrien NULL_RTX, 1, 412550397Sobrien max_cost - extra_cost); 412650397Sobrien if (t2 == 0) 412750397Sobrien goto fail1; 4128169689Skan quotient = expand_shift 4129169689Skan (RSHIFT_EXPR, compute_mode, t2, 4130169689Skan build_int_cst (NULL_TREE, post_shift), 4131169689Skan tquotient, 1); 413250397Sobrien } 413318334Speter } 413418334Speter } 413550397Sobrien else /* Too wide mode to use tricky code */ 413650397Sobrien break; 413718334Speter 413818334Speter insn = get_last_insn (); 413918334Speter if (insn != last 414018334Speter && (set = single_set (insn)) != 0 414118334Speter && SET_DEST (set) == quotient) 414296263Sobrien set_unique_reg_note (insn, 4143132718Skan REG_EQUAL, 414452284Sobrien gen_rtx_UDIV (compute_mode, op0, op1)); 414518334Speter } 414618334Speter else /* TRUNC_DIV, signed */ 414718334Speter { 414818334Speter unsigned HOST_WIDE_INT ml; 414918334Speter int lgup, post_shift; 4150169689Skan rtx mlr; 415118334Speter HOST_WIDE_INT d = INTVAL (op1); 415218334Speter unsigned HOST_WIDE_INT abs_d = d >= 0 ? d : -d; 415318334Speter 415418334Speter /* n rem d = n rem -d */ 415518334Speter if (rem_flag && d < 0) 415618334Speter { 415718334Speter d = abs_d; 4158117395Skan op1 = gen_int_mode (abs_d, compute_mode); 415918334Speter } 416018334Speter 416118334Speter if (d == 1) 416218334Speter quotient = op0; 416318334Speter else if (d == -1) 416418334Speter quotient = expand_unop (compute_mode, neg_optab, op0, 416518334Speter tquotient, 0); 416618334Speter else if (abs_d == (unsigned HOST_WIDE_INT) 1 << (size - 1)) 416718334Speter { 416818334Speter /* This case is not handled correctly below. */ 416918334Speter quotient = emit_store_flag (tquotient, EQ, op0, op1, 417018334Speter compute_mode, 1, 1); 417118334Speter if (quotient == 0) 417218334Speter goto fail1; 417318334Speter } 417418334Speter else if (EXACT_POWER_OF_2_OR_ZERO_P (d) 4175169689Skan && (rem_flag ? smod_pow2_cheap[compute_mode] 4176169689Skan : sdiv_pow2_cheap[compute_mode]) 4177169689Skan /* We assume that cheap metric is true if the 4178169689Skan optab has an expander for this mode. */ 417990075Sobrien && (((rem_flag ? smod_optab : sdiv_optab) 4180169689Skan ->handlers[compute_mode].insn_code 418190075Sobrien != CODE_FOR_nothing) 4182169689Skan || (sdivmod_optab->handlers[compute_mode] 418390075Sobrien .insn_code != CODE_FOR_nothing))) 418418334Speter ; 418518334Speter else if (EXACT_POWER_OF_2_OR_ZERO_P (abs_d)) 418618334Speter { 4187169689Skan if (rem_flag) 418818334Speter { 4189169689Skan remainder = expand_smod_pow2 (compute_mode, op0, d); 4190169689Skan if (remainder) 4191169689Skan return gen_lowpart (mode, remainder); 4192169689Skan } 419318334Speter 4194169689Skan if (sdiv_pow2_cheap[compute_mode] 4195169689Skan && ((sdiv_optab->handlers[compute_mode].insn_code 4196169689Skan != CODE_FOR_nothing) 4197169689Skan || (sdivmod_optab->handlers[compute_mode].insn_code 4198169689Skan != CODE_FOR_nothing))) 4199169689Skan quotient = expand_divmod (0, TRUNC_DIV_EXPR, 4200169689Skan compute_mode, op0, 4201169689Skan gen_int_mode (abs_d, 4202169689Skan compute_mode), 4203169689Skan NULL_RTX, 0); 420418334Speter else 4205169689Skan quotient = expand_sdiv_pow2 (compute_mode, op0, abs_d); 420618334Speter 4207169689Skan /* We have computed OP0 / abs(OP1). If OP1 is negative, 4208169689Skan negate the quotient. */ 420918334Speter if (d < 0) 421018334Speter { 421118334Speter insn = get_last_insn (); 421218334Speter if (insn != last 421318334Speter && (set = single_set (insn)) != 0 421452284Sobrien && SET_DEST (set) == quotient 421552284Sobrien && abs_d < ((unsigned HOST_WIDE_INT) 1 421652284Sobrien << (HOST_BITS_PER_WIDE_INT - 1))) 421796263Sobrien set_unique_reg_note (insn, 4218132718Skan REG_EQUAL, 421952284Sobrien gen_rtx_DIV (compute_mode, 422052284Sobrien op0, 422190075Sobrien GEN_INT 422290075Sobrien (trunc_int_for_mode 422390075Sobrien (abs_d, 422490075Sobrien compute_mode)))); 422518334Speter 422618334Speter quotient = expand_unop (compute_mode, neg_optab, 422718334Speter quotient, quotient, 0); 422818334Speter } 422918334Speter } 423050397Sobrien else if (size <= HOST_BITS_PER_WIDE_INT) 423118334Speter { 423218334Speter choose_multiplier (abs_d, size, size - 1, 4233169689Skan &mlr, &post_shift, &lgup); 4234169689Skan ml = (unsigned HOST_WIDE_INT) INTVAL (mlr); 423518334Speter if (ml < (unsigned HOST_WIDE_INT) 1 << (size - 1)) 423618334Speter { 423718334Speter rtx t1, t2, t3; 423818334Speter 423990075Sobrien if (post_shift >= BITS_PER_WORD 424090075Sobrien || size - 1 >= BITS_PER_WORD) 424190075Sobrien goto fail1; 424290075Sobrien 4243169689Skan extra_cost = (shift_cost[compute_mode][post_shift] 4244169689Skan + shift_cost[compute_mode][size - 1] 4245169689Skan + add_cost[compute_mode]); 4246169689Skan t1 = expand_mult_highpart (compute_mode, op0, mlr, 424718334Speter NULL_RTX, 0, 424818334Speter max_cost - extra_cost); 424918334Speter if (t1 == 0) 425018334Speter goto fail1; 4251169689Skan t2 = expand_shift 4252169689Skan (RSHIFT_EXPR, compute_mode, t1, 4253169689Skan build_int_cst (NULL_TREE, post_shift), 4254169689Skan NULL_RTX, 0); 4255169689Skan t3 = expand_shift 4256169689Skan (RSHIFT_EXPR, compute_mode, op0, 4257169689Skan build_int_cst (NULL_TREE, size - 1), 4258169689Skan NULL_RTX, 0); 425918334Speter if (d < 0) 426090075Sobrien quotient 426190075Sobrien = force_operand (gen_rtx_MINUS (compute_mode, 426290075Sobrien t3, t2), 426390075Sobrien tquotient); 426418334Speter else 426590075Sobrien quotient 426690075Sobrien = force_operand (gen_rtx_MINUS (compute_mode, 426790075Sobrien t2, t3), 426890075Sobrien tquotient); 426918334Speter } 427018334Speter else 427118334Speter { 427218334Speter rtx t1, t2, t3, t4; 427318334Speter 427490075Sobrien if (post_shift >= BITS_PER_WORD 427590075Sobrien || size - 1 >= BITS_PER_WORD) 427690075Sobrien goto fail1; 427790075Sobrien 427818334Speter ml |= (~(unsigned HOST_WIDE_INT) 0) << (size - 1); 4279169689Skan mlr = gen_int_mode (ml, compute_mode); 4280169689Skan extra_cost = (shift_cost[compute_mode][post_shift] 4281169689Skan + shift_cost[compute_mode][size - 1] 4282169689Skan + 2 * add_cost[compute_mode]); 4283169689Skan t1 = expand_mult_highpart (compute_mode, op0, mlr, 428418334Speter NULL_RTX, 0, 428518334Speter max_cost - extra_cost); 428618334Speter if (t1 == 0) 428718334Speter goto fail1; 428890075Sobrien t2 = force_operand (gen_rtx_PLUS (compute_mode, 428990075Sobrien t1, op0), 429018334Speter NULL_RTX); 4291169689Skan t3 = expand_shift 4292169689Skan (RSHIFT_EXPR, compute_mode, t2, 4293169689Skan build_int_cst (NULL_TREE, post_shift), 4294169689Skan NULL_RTX, 0); 4295169689Skan t4 = expand_shift 4296169689Skan (RSHIFT_EXPR, compute_mode, op0, 4297169689Skan build_int_cst (NULL_TREE, size - 1), 4298169689Skan NULL_RTX, 0); 429918334Speter if (d < 0) 430090075Sobrien quotient 430190075Sobrien = force_operand (gen_rtx_MINUS (compute_mode, 430290075Sobrien t4, t3), 430390075Sobrien tquotient); 430418334Speter else 430590075Sobrien quotient 430690075Sobrien = force_operand (gen_rtx_MINUS (compute_mode, 430790075Sobrien t3, t4), 430890075Sobrien tquotient); 430918334Speter } 431018334Speter } 431150397Sobrien else /* Too wide mode to use tricky code */ 431250397Sobrien break; 431318334Speter 431418334Speter insn = get_last_insn (); 431518334Speter if (insn != last 431618334Speter && (set = single_set (insn)) != 0 431718334Speter && SET_DEST (set) == quotient) 431896263Sobrien set_unique_reg_note (insn, 4319132718Skan REG_EQUAL, 432052284Sobrien gen_rtx_DIV (compute_mode, op0, op1)); 432118334Speter } 432218334Speter break; 432318334Speter } 432418334Speter fail1: 432518334Speter delete_insns_since (last); 432618334Speter break; 432718334Speter 432818334Speter case FLOOR_DIV_EXPR: 432918334Speter case FLOOR_MOD_EXPR: 433018334Speter /* We will come here only for signed operations. */ 433118334Speter if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size) 433218334Speter { 4333169689Skan unsigned HOST_WIDE_INT mh; 433418334Speter int pre_shift, lgup, post_shift; 433518334Speter HOST_WIDE_INT d = INTVAL (op1); 4336169689Skan rtx ml; 433718334Speter 433818334Speter if (d > 0) 433918334Speter { 434018334Speter /* We could just as easily deal with negative constants here, 434118334Speter but it does not seem worth the trouble for GCC 2.6. */ 434218334Speter if (EXACT_POWER_OF_2_OR_ZERO_P (d)) 434318334Speter { 434418334Speter pre_shift = floor_log2 (d); 434518334Speter if (rem_flag) 434618334Speter { 434718334Speter remainder = expand_binop (compute_mode, and_optab, op0, 434818334Speter GEN_INT (((HOST_WIDE_INT) 1 << pre_shift) - 1), 434918334Speter remainder, 0, OPTAB_LIB_WIDEN); 435018334Speter if (remainder) 435118334Speter return gen_lowpart (mode, remainder); 435218334Speter } 4353169689Skan quotient = expand_shift 4354169689Skan (RSHIFT_EXPR, compute_mode, op0, 4355169689Skan build_int_cst (NULL_TREE, pre_shift), 4356169689Skan tquotient, 0); 435718334Speter } 435818334Speter else 435918334Speter { 436018334Speter rtx t1, t2, t3, t4; 436118334Speter 436218334Speter mh = choose_multiplier (d, size, size - 1, 436318334Speter &ml, &post_shift, &lgup); 4364169689Skan gcc_assert (!mh); 436518334Speter 436690075Sobrien if (post_shift < BITS_PER_WORD 436790075Sobrien && size - 1 < BITS_PER_WORD) 436818334Speter { 4369169689Skan t1 = expand_shift 4370169689Skan (RSHIFT_EXPR, compute_mode, op0, 4371169689Skan build_int_cst (NULL_TREE, size - 1), 4372169689Skan NULL_RTX, 0); 437390075Sobrien t2 = expand_binop (compute_mode, xor_optab, op0, t1, 437490075Sobrien NULL_RTX, 0, OPTAB_WIDEN); 4375169689Skan extra_cost = (shift_cost[compute_mode][post_shift] 4376169689Skan + shift_cost[compute_mode][size - 1] 4377169689Skan + 2 * add_cost[compute_mode]); 437890075Sobrien t3 = expand_mult_highpart (compute_mode, t2, ml, 437990075Sobrien NULL_RTX, 1, 438090075Sobrien max_cost - extra_cost); 438190075Sobrien if (t3 != 0) 438290075Sobrien { 4383169689Skan t4 = expand_shift 4384169689Skan (RSHIFT_EXPR, compute_mode, t3, 4385169689Skan build_int_cst (NULL_TREE, post_shift), 4386169689Skan NULL_RTX, 1); 438790075Sobrien quotient = expand_binop (compute_mode, xor_optab, 438890075Sobrien t4, t1, tquotient, 0, 438990075Sobrien OPTAB_WIDEN); 439090075Sobrien } 439118334Speter } 439218334Speter } 439318334Speter } 439418334Speter else 439518334Speter { 439618334Speter rtx nsign, t1, t2, t3, t4; 439750397Sobrien t1 = force_operand (gen_rtx_PLUS (compute_mode, 439850397Sobrien op0, constm1_rtx), NULL_RTX); 439918334Speter t2 = expand_binop (compute_mode, ior_optab, op0, t1, NULL_RTX, 440018334Speter 0, OPTAB_WIDEN); 4401169689Skan nsign = expand_shift 4402169689Skan (RSHIFT_EXPR, compute_mode, t2, 4403169689Skan build_int_cst (NULL_TREE, size - 1), 4404169689Skan NULL_RTX, 0); 440550397Sobrien t3 = force_operand (gen_rtx_MINUS (compute_mode, t1, nsign), 440618334Speter NULL_RTX); 440718334Speter t4 = expand_divmod (0, TRUNC_DIV_EXPR, compute_mode, t3, op1, 440818334Speter NULL_RTX, 0); 440918334Speter if (t4) 441018334Speter { 441118334Speter rtx t5; 441218334Speter t5 = expand_unop (compute_mode, one_cmpl_optab, nsign, 441318334Speter NULL_RTX, 0); 441450397Sobrien quotient = force_operand (gen_rtx_PLUS (compute_mode, 441550397Sobrien t4, t5), 441618334Speter tquotient); 441718334Speter } 441818334Speter } 441918334Speter } 442018334Speter 442118334Speter if (quotient != 0) 442218334Speter break; 442318334Speter delete_insns_since (last); 442418334Speter 442518334Speter /* Try using an instruction that produces both the quotient and 442618334Speter remainder, using truncation. We can easily compensate the quotient 442718334Speter or remainder to get floor rounding, once we have the remainder. 442818334Speter Notice that we compute also the final remainder value here, 442918334Speter and return the result right away. */ 443050397Sobrien if (target == 0 || GET_MODE (target) != compute_mode) 443118334Speter target = gen_reg_rtx (compute_mode); 443218334Speter 443318334Speter if (rem_flag) 443418334Speter { 443518334Speter remainder 4436169689Skan = REG_P (target) ? target : gen_reg_rtx (compute_mode); 443718334Speter quotient = gen_reg_rtx (compute_mode); 443818334Speter } 443918334Speter else 444018334Speter { 444118334Speter quotient 4442169689Skan = REG_P (target) ? target : gen_reg_rtx (compute_mode); 444318334Speter remainder = gen_reg_rtx (compute_mode); 444418334Speter } 444518334Speter 444618334Speter if (expand_twoval_binop (sdivmod_optab, op0, op1, 444718334Speter quotient, remainder, 0)) 444818334Speter { 444918334Speter /* This could be computed with a branch-less sequence. 445018334Speter Save that for later. */ 445118334Speter rtx tem; 445218334Speter rtx label = gen_label_rtx (); 445350397Sobrien do_cmp_and_jump (remainder, const0_rtx, EQ, compute_mode, label); 445418334Speter tem = expand_binop (compute_mode, xor_optab, op0, op1, 445518334Speter NULL_RTX, 0, OPTAB_WIDEN); 445650397Sobrien do_cmp_and_jump (tem, const0_rtx, GE, compute_mode, label); 445718334Speter expand_dec (quotient, const1_rtx); 445818334Speter expand_inc (remainder, op1); 445918334Speter emit_label (label); 446018334Speter return gen_lowpart (mode, rem_flag ? remainder : quotient); 446118334Speter } 446218334Speter 446318334Speter /* No luck with division elimination or divmod. Have to do it 446418334Speter by conditionally adjusting op0 *and* the result. */ 446518334Speter { 446618334Speter rtx label1, label2, label3, label4, label5; 446718334Speter rtx adjusted_op0; 446818334Speter rtx tem; 446918334Speter 447018334Speter quotient = gen_reg_rtx (compute_mode); 447118334Speter adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 447218334Speter label1 = gen_label_rtx (); 447318334Speter label2 = gen_label_rtx (); 447418334Speter label3 = gen_label_rtx (); 447518334Speter label4 = gen_label_rtx (); 447618334Speter label5 = gen_label_rtx (); 447750397Sobrien do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2); 447850397Sobrien do_cmp_and_jump (adjusted_op0, const0_rtx, LT, compute_mode, label1); 447918334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 448018334Speter quotient, 0, OPTAB_LIB_WIDEN); 448118334Speter if (tem != quotient) 448218334Speter emit_move_insn (quotient, tem); 448318334Speter emit_jump_insn (gen_jump (label5)); 448418334Speter emit_barrier (); 448518334Speter emit_label (label1); 448618334Speter expand_inc (adjusted_op0, const1_rtx); 448718334Speter emit_jump_insn (gen_jump (label4)); 448818334Speter emit_barrier (); 448918334Speter emit_label (label2); 449050397Sobrien do_cmp_and_jump (adjusted_op0, const0_rtx, GT, compute_mode, label3); 449118334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 449218334Speter quotient, 0, OPTAB_LIB_WIDEN); 449318334Speter if (tem != quotient) 449418334Speter emit_move_insn (quotient, tem); 449518334Speter emit_jump_insn (gen_jump (label5)); 449618334Speter emit_barrier (); 449718334Speter emit_label (label3); 449818334Speter expand_dec (adjusted_op0, const1_rtx); 449918334Speter emit_label (label4); 450018334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 450118334Speter quotient, 0, OPTAB_LIB_WIDEN); 450218334Speter if (tem != quotient) 450318334Speter emit_move_insn (quotient, tem); 450418334Speter expand_dec (quotient, const1_rtx); 450518334Speter emit_label (label5); 450618334Speter } 450718334Speter break; 450818334Speter 450918334Speter case CEIL_DIV_EXPR: 451018334Speter case CEIL_MOD_EXPR: 451118334Speter if (unsignedp) 451218334Speter { 451318334Speter if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1))) 451418334Speter { 451518334Speter rtx t1, t2, t3; 451618334Speter unsigned HOST_WIDE_INT d = INTVAL (op1); 451718334Speter t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4518169689Skan build_int_cst (NULL_TREE, floor_log2 (d)), 451918334Speter tquotient, 1); 452018334Speter t2 = expand_binop (compute_mode, and_optab, op0, 452118334Speter GEN_INT (d - 1), 452218334Speter NULL_RTX, 1, OPTAB_LIB_WIDEN); 452318334Speter t3 = gen_reg_rtx (compute_mode); 452418334Speter t3 = emit_store_flag (t3, NE, t2, const0_rtx, 452518334Speter compute_mode, 1, 1); 452618334Speter if (t3 == 0) 452718334Speter { 452818334Speter rtx lab; 452918334Speter lab = gen_label_rtx (); 453050397Sobrien do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab); 453118334Speter expand_inc (t1, const1_rtx); 453218334Speter emit_label (lab); 453318334Speter quotient = t1; 453418334Speter } 453518334Speter else 453650397Sobrien quotient = force_operand (gen_rtx_PLUS (compute_mode, 453750397Sobrien t1, t3), 453818334Speter tquotient); 453918334Speter break; 454018334Speter } 454118334Speter 454218334Speter /* Try using an instruction that produces both the quotient and 454318334Speter remainder, using truncation. We can easily compensate the 454418334Speter quotient or remainder to get ceiling rounding, once we have the 454518334Speter remainder. Notice that we compute also the final remainder 454618334Speter value here, and return the result right away. */ 454750397Sobrien if (target == 0 || GET_MODE (target) != compute_mode) 454818334Speter target = gen_reg_rtx (compute_mode); 454918334Speter 455018334Speter if (rem_flag) 455118334Speter { 4552169689Skan remainder = (REG_P (target) 455318334Speter ? target : gen_reg_rtx (compute_mode)); 455418334Speter quotient = gen_reg_rtx (compute_mode); 455518334Speter } 455618334Speter else 455718334Speter { 4558169689Skan quotient = (REG_P (target) 455918334Speter ? target : gen_reg_rtx (compute_mode)); 456018334Speter remainder = gen_reg_rtx (compute_mode); 456118334Speter } 456218334Speter 456318334Speter if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, 456418334Speter remainder, 1)) 456518334Speter { 456618334Speter /* This could be computed with a branch-less sequence. 456718334Speter Save that for later. */ 456818334Speter rtx label = gen_label_rtx (); 456950397Sobrien do_cmp_and_jump (remainder, const0_rtx, EQ, 457050397Sobrien compute_mode, label); 457118334Speter expand_inc (quotient, const1_rtx); 457218334Speter expand_dec (remainder, op1); 457318334Speter emit_label (label); 457418334Speter return gen_lowpart (mode, rem_flag ? remainder : quotient); 457518334Speter } 457618334Speter 457718334Speter /* No luck with division elimination or divmod. Have to do it 457818334Speter by conditionally adjusting op0 *and* the result. */ 457918334Speter { 458018334Speter rtx label1, label2; 458118334Speter rtx adjusted_op0, tem; 458218334Speter 458318334Speter quotient = gen_reg_rtx (compute_mode); 458418334Speter adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 458518334Speter label1 = gen_label_rtx (); 458618334Speter label2 = gen_label_rtx (); 458750397Sobrien do_cmp_and_jump (adjusted_op0, const0_rtx, NE, 458850397Sobrien compute_mode, label1); 458918334Speter emit_move_insn (quotient, const0_rtx); 459018334Speter emit_jump_insn (gen_jump (label2)); 459118334Speter emit_barrier (); 459218334Speter emit_label (label1); 459318334Speter expand_dec (adjusted_op0, const1_rtx); 459418334Speter tem = expand_binop (compute_mode, udiv_optab, adjusted_op0, op1, 459518334Speter quotient, 1, OPTAB_LIB_WIDEN); 459618334Speter if (tem != quotient) 459718334Speter emit_move_insn (quotient, tem); 459818334Speter expand_inc (quotient, const1_rtx); 459918334Speter emit_label (label2); 460018334Speter } 460118334Speter } 460218334Speter else /* signed */ 460318334Speter { 460418334Speter if (op1_is_constant && EXACT_POWER_OF_2_OR_ZERO_P (INTVAL (op1)) 460518334Speter && INTVAL (op1) >= 0) 460618334Speter { 460718334Speter /* This is extremely similar to the code for the unsigned case 460818334Speter above. For 2.7 we should merge these variants, but for 460918334Speter 2.6.1 I don't want to touch the code for unsigned since that 461018334Speter get used in C. The signed case will only be used by other 461118334Speter languages (Ada). */ 461218334Speter 461318334Speter rtx t1, t2, t3; 461418334Speter unsigned HOST_WIDE_INT d = INTVAL (op1); 461518334Speter t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4616169689Skan build_int_cst (NULL_TREE, floor_log2 (d)), 461718334Speter tquotient, 0); 461818334Speter t2 = expand_binop (compute_mode, and_optab, op0, 461918334Speter GEN_INT (d - 1), 462018334Speter NULL_RTX, 1, OPTAB_LIB_WIDEN); 462118334Speter t3 = gen_reg_rtx (compute_mode); 462218334Speter t3 = emit_store_flag (t3, NE, t2, const0_rtx, 462318334Speter compute_mode, 1, 1); 462418334Speter if (t3 == 0) 462518334Speter { 462618334Speter rtx lab; 462718334Speter lab = gen_label_rtx (); 462850397Sobrien do_cmp_and_jump (t2, const0_rtx, EQ, compute_mode, lab); 462918334Speter expand_inc (t1, const1_rtx); 463018334Speter emit_label (lab); 463118334Speter quotient = t1; 463218334Speter } 463318334Speter else 463450397Sobrien quotient = force_operand (gen_rtx_PLUS (compute_mode, 463550397Sobrien t1, t3), 463618334Speter tquotient); 463718334Speter break; 463818334Speter } 463918334Speter 464018334Speter /* Try using an instruction that produces both the quotient and 464118334Speter remainder, using truncation. We can easily compensate the 464218334Speter quotient or remainder to get ceiling rounding, once we have the 464318334Speter remainder. Notice that we compute also the final remainder 464418334Speter value here, and return the result right away. */ 464550397Sobrien if (target == 0 || GET_MODE (target) != compute_mode) 464618334Speter target = gen_reg_rtx (compute_mode); 464718334Speter if (rem_flag) 464818334Speter { 4649169689Skan remainder= (REG_P (target) 465018334Speter ? target : gen_reg_rtx (compute_mode)); 465118334Speter quotient = gen_reg_rtx (compute_mode); 465218334Speter } 465318334Speter else 465418334Speter { 4655169689Skan quotient = (REG_P (target) 465618334Speter ? target : gen_reg_rtx (compute_mode)); 465718334Speter remainder = gen_reg_rtx (compute_mode); 465818334Speter } 465918334Speter 466018334Speter if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, 466118334Speter remainder, 0)) 466218334Speter { 466318334Speter /* This could be computed with a branch-less sequence. 466418334Speter Save that for later. */ 466518334Speter rtx tem; 466618334Speter rtx label = gen_label_rtx (); 466750397Sobrien do_cmp_and_jump (remainder, const0_rtx, EQ, 466850397Sobrien compute_mode, label); 466918334Speter tem = expand_binop (compute_mode, xor_optab, op0, op1, 467018334Speter NULL_RTX, 0, OPTAB_WIDEN); 467150397Sobrien do_cmp_and_jump (tem, const0_rtx, LT, compute_mode, label); 467218334Speter expand_inc (quotient, const1_rtx); 467318334Speter expand_dec (remainder, op1); 467418334Speter emit_label (label); 467518334Speter return gen_lowpart (mode, rem_flag ? remainder : quotient); 467618334Speter } 467718334Speter 467818334Speter /* No luck with division elimination or divmod. Have to do it 467918334Speter by conditionally adjusting op0 *and* the result. */ 468018334Speter { 468118334Speter rtx label1, label2, label3, label4, label5; 468218334Speter rtx adjusted_op0; 468318334Speter rtx tem; 468418334Speter 468518334Speter quotient = gen_reg_rtx (compute_mode); 468618334Speter adjusted_op0 = copy_to_mode_reg (compute_mode, op0); 468718334Speter label1 = gen_label_rtx (); 468818334Speter label2 = gen_label_rtx (); 468918334Speter label3 = gen_label_rtx (); 469018334Speter label4 = gen_label_rtx (); 469118334Speter label5 = gen_label_rtx (); 469250397Sobrien do_cmp_and_jump (op1, const0_rtx, LT, compute_mode, label2); 469350397Sobrien do_cmp_and_jump (adjusted_op0, const0_rtx, GT, 469450397Sobrien compute_mode, label1); 469518334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 469618334Speter quotient, 0, OPTAB_LIB_WIDEN); 469718334Speter if (tem != quotient) 469818334Speter emit_move_insn (quotient, tem); 469918334Speter emit_jump_insn (gen_jump (label5)); 470018334Speter emit_barrier (); 470118334Speter emit_label (label1); 470218334Speter expand_dec (adjusted_op0, const1_rtx); 470318334Speter emit_jump_insn (gen_jump (label4)); 470418334Speter emit_barrier (); 470518334Speter emit_label (label2); 470650397Sobrien do_cmp_and_jump (adjusted_op0, const0_rtx, LT, 470750397Sobrien compute_mode, label3); 470818334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 470918334Speter quotient, 0, OPTAB_LIB_WIDEN); 471018334Speter if (tem != quotient) 471118334Speter emit_move_insn (quotient, tem); 471218334Speter emit_jump_insn (gen_jump (label5)); 471318334Speter emit_barrier (); 471418334Speter emit_label (label3); 471518334Speter expand_inc (adjusted_op0, const1_rtx); 471618334Speter emit_label (label4); 471718334Speter tem = expand_binop (compute_mode, sdiv_optab, adjusted_op0, op1, 471818334Speter quotient, 0, OPTAB_LIB_WIDEN); 471918334Speter if (tem != quotient) 472018334Speter emit_move_insn (quotient, tem); 472118334Speter expand_inc (quotient, const1_rtx); 472218334Speter emit_label (label5); 472318334Speter } 472418334Speter } 472518334Speter break; 472618334Speter 472718334Speter case EXACT_DIV_EXPR: 472818334Speter if (op1_is_constant && HOST_BITS_PER_WIDE_INT >= size) 472918334Speter { 473018334Speter HOST_WIDE_INT d = INTVAL (op1); 473118334Speter unsigned HOST_WIDE_INT ml; 473290075Sobrien int pre_shift; 473318334Speter rtx t1; 473418334Speter 473590075Sobrien pre_shift = floor_log2 (d & -d); 473690075Sobrien ml = invert_mod2n (d >> pre_shift, size); 473790075Sobrien t1 = expand_shift (RSHIFT_EXPR, compute_mode, op0, 4738169689Skan build_int_cst (NULL_TREE, pre_shift), 4739169689Skan NULL_RTX, unsignedp); 474090075Sobrien quotient = expand_mult (compute_mode, t1, 4741117395Skan gen_int_mode (ml, compute_mode), 4742132718Skan NULL_RTX, 1); 474318334Speter 474418334Speter insn = get_last_insn (); 474552284Sobrien set_unique_reg_note (insn, 4746132718Skan REG_EQUAL, 474752284Sobrien gen_rtx_fmt_ee (unsignedp ? UDIV : DIV, 474852284Sobrien compute_mode, 474952284Sobrien op0, op1)); 475018334Speter } 475118334Speter break; 475218334Speter 475318334Speter case ROUND_DIV_EXPR: 475418334Speter case ROUND_MOD_EXPR: 475518334Speter if (unsignedp) 475618334Speter { 475718334Speter rtx tem; 475818334Speter rtx label; 475918334Speter label = gen_label_rtx (); 476018334Speter quotient = gen_reg_rtx (compute_mode); 476118334Speter remainder = gen_reg_rtx (compute_mode); 476218334Speter if (expand_twoval_binop (udivmod_optab, op0, op1, quotient, remainder, 1) == 0) 476318334Speter { 476418334Speter rtx tem; 476518334Speter quotient = expand_binop (compute_mode, udiv_optab, op0, op1, 476618334Speter quotient, 1, OPTAB_LIB_WIDEN); 476718334Speter tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 1); 476818334Speter remainder = expand_binop (compute_mode, sub_optab, op0, tem, 476918334Speter remainder, 1, OPTAB_LIB_WIDEN); 477018334Speter } 477118334Speter tem = plus_constant (op1, -1); 477218334Speter tem = expand_shift (RSHIFT_EXPR, compute_mode, tem, 4773169689Skan build_int_cst (NULL_TREE, 1), 4774169689Skan NULL_RTX, 1); 477550397Sobrien do_cmp_and_jump (remainder, tem, LEU, compute_mode, label); 477618334Speter expand_inc (quotient, const1_rtx); 477718334Speter expand_dec (remainder, op1); 477818334Speter emit_label (label); 477918334Speter } 478018334Speter else 478118334Speter { 478218334Speter rtx abs_rem, abs_op1, tem, mask; 478318334Speter rtx label; 478418334Speter label = gen_label_rtx (); 478518334Speter quotient = gen_reg_rtx (compute_mode); 478618334Speter remainder = gen_reg_rtx (compute_mode); 478718334Speter if (expand_twoval_binop (sdivmod_optab, op0, op1, quotient, remainder, 0) == 0) 478818334Speter { 478918334Speter rtx tem; 479018334Speter quotient = expand_binop (compute_mode, sdiv_optab, op0, op1, 479118334Speter quotient, 0, OPTAB_LIB_WIDEN); 479218334Speter tem = expand_mult (compute_mode, quotient, op1, NULL_RTX, 0); 479318334Speter remainder = expand_binop (compute_mode, sub_optab, op0, tem, 479418334Speter remainder, 0, OPTAB_LIB_WIDEN); 479518334Speter } 479690075Sobrien abs_rem = expand_abs (compute_mode, remainder, NULL_RTX, 1, 0); 479790075Sobrien abs_op1 = expand_abs (compute_mode, op1, NULL_RTX, 1, 0); 479818334Speter tem = expand_shift (LSHIFT_EXPR, compute_mode, abs_rem, 4799169689Skan build_int_cst (NULL_TREE, 1), 4800169689Skan NULL_RTX, 1); 480150397Sobrien do_cmp_and_jump (tem, abs_op1, LTU, compute_mode, label); 480218334Speter tem = expand_binop (compute_mode, xor_optab, op0, op1, 480318334Speter NULL_RTX, 0, OPTAB_WIDEN); 480418334Speter mask = expand_shift (RSHIFT_EXPR, compute_mode, tem, 4805169689Skan build_int_cst (NULL_TREE, size - 1), 4806169689Skan NULL_RTX, 0); 480718334Speter tem = expand_binop (compute_mode, xor_optab, mask, const1_rtx, 480818334Speter NULL_RTX, 0, OPTAB_WIDEN); 480918334Speter tem = expand_binop (compute_mode, sub_optab, tem, mask, 481018334Speter NULL_RTX, 0, OPTAB_WIDEN); 481118334Speter expand_inc (quotient, tem); 481218334Speter tem = expand_binop (compute_mode, xor_optab, mask, op1, 481318334Speter NULL_RTX, 0, OPTAB_WIDEN); 481418334Speter tem = expand_binop (compute_mode, sub_optab, tem, mask, 481518334Speter NULL_RTX, 0, OPTAB_WIDEN); 481618334Speter expand_dec (remainder, tem); 481718334Speter emit_label (label); 481818334Speter } 481918334Speter return gen_lowpart (mode, rem_flag ? remainder : quotient); 482096263Sobrien 482150397Sobrien default: 4822169689Skan gcc_unreachable (); 482318334Speter } 482418334Speter 482518334Speter if (quotient == 0) 482618334Speter { 482750397Sobrien if (target && GET_MODE (target) != compute_mode) 482850397Sobrien target = 0; 482950397Sobrien 483018334Speter if (rem_flag) 483118334Speter { 483252284Sobrien /* Try to produce the remainder without producing the quotient. 483390075Sobrien If we seem to have a divmod pattern that does not require widening, 4834132718Skan don't try widening here. We should really have a WIDEN argument 483552284Sobrien to expand_twoval_binop, since what we'd really like to do here is 483652284Sobrien 1) try a mod insn in compute_mode 483752284Sobrien 2) try a divmod insn in compute_mode 483852284Sobrien 3) try a div insn in compute_mode and multiply-subtract to get 483952284Sobrien remainder 484052284Sobrien 4) try the same things with widening allowed. */ 484152284Sobrien remainder 484252284Sobrien = sign_expand_binop (compute_mode, umod_optab, smod_optab, 484352284Sobrien op0, op1, target, 484452284Sobrien unsignedp, 4845169689Skan ((optab2->handlers[compute_mode].insn_code 484652284Sobrien != CODE_FOR_nothing) 484752284Sobrien ? OPTAB_DIRECT : OPTAB_WIDEN)); 484818334Speter if (remainder == 0) 484918334Speter { 485018334Speter /* No luck there. Can we do remainder and divide at once 485118334Speter without a library call? */ 485218334Speter remainder = gen_reg_rtx (compute_mode); 485318334Speter if (! expand_twoval_binop ((unsignedp 485418334Speter ? udivmod_optab 485518334Speter : sdivmod_optab), 485618334Speter op0, op1, 485718334Speter NULL_RTX, remainder, unsignedp)) 485818334Speter remainder = 0; 485918334Speter } 486018334Speter 486118334Speter if (remainder) 486218334Speter return gen_lowpart (mode, remainder); 486318334Speter } 486418334Speter 486550397Sobrien /* Produce the quotient. Try a quotient insn, but not a library call. 486650397Sobrien If we have a divmod in this mode, use it in preference to widening 486750397Sobrien the div (for this test we assume it will not fail). Note that optab2 486850397Sobrien is set to the one of the two optabs that the call below will use. */ 486950397Sobrien quotient 487050397Sobrien = sign_expand_binop (compute_mode, udiv_optab, sdiv_optab, 487150397Sobrien op0, op1, rem_flag ? NULL_RTX : target, 487250397Sobrien unsignedp, 4873169689Skan ((optab2->handlers[compute_mode].insn_code 487450397Sobrien != CODE_FOR_nothing) 487550397Sobrien ? OPTAB_DIRECT : OPTAB_WIDEN)); 487650397Sobrien 487718334Speter if (quotient == 0) 487818334Speter { 487918334Speter /* No luck there. Try a quotient-and-remainder insn, 488018334Speter keeping the quotient alone. */ 488118334Speter quotient = gen_reg_rtx (compute_mode); 488218334Speter if (! expand_twoval_binop (unsignedp ? udivmod_optab : sdivmod_optab, 488318334Speter op0, op1, 488418334Speter quotient, NULL_RTX, unsignedp)) 488518334Speter { 488618334Speter quotient = 0; 488718334Speter if (! rem_flag) 488818334Speter /* Still no luck. If we are not computing the remainder, 488918334Speter use a library call for the quotient. */ 489018334Speter quotient = sign_expand_binop (compute_mode, 489118334Speter udiv_optab, sdiv_optab, 489218334Speter op0, op1, target, 489318334Speter unsignedp, OPTAB_LIB_WIDEN); 489418334Speter } 489518334Speter } 489618334Speter } 489718334Speter 489818334Speter if (rem_flag) 489918334Speter { 490050397Sobrien if (target && GET_MODE (target) != compute_mode) 490150397Sobrien target = 0; 490250397Sobrien 490318334Speter if (quotient == 0) 4904169689Skan { 4905169689Skan /* No divide instruction either. Use library for remainder. */ 4906169689Skan remainder = sign_expand_binop (compute_mode, umod_optab, smod_optab, 4907169689Skan op0, op1, target, 4908169689Skan unsignedp, OPTAB_LIB_WIDEN); 4909169689Skan /* No remainder function. Try a quotient-and-remainder 4910169689Skan function, keeping the remainder. */ 4911169689Skan if (!remainder) 4912169689Skan { 4913169689Skan remainder = gen_reg_rtx (compute_mode); 4914169689Skan if (!expand_twoval_binop_libfunc 4915169689Skan (unsignedp ? udivmod_optab : sdivmod_optab, 4916169689Skan op0, op1, 4917169689Skan NULL_RTX, remainder, 4918169689Skan unsignedp ? UMOD : MOD)) 4919169689Skan remainder = NULL_RTX; 4920169689Skan } 4921169689Skan } 492218334Speter else 492318334Speter { 492418334Speter /* We divided. Now finish doing X - Y * (X / Y). */ 492518334Speter remainder = expand_mult (compute_mode, quotient, op1, 492618334Speter NULL_RTX, unsignedp); 492718334Speter remainder = expand_binop (compute_mode, sub_optab, op0, 492818334Speter remainder, target, unsignedp, 492918334Speter OPTAB_LIB_WIDEN); 493018334Speter } 493118334Speter } 493218334Speter 493318334Speter return gen_lowpart (mode, rem_flag ? remainder : quotient); 493418334Speter} 493518334Speter 493618334Speter/* Return a tree node with data type TYPE, describing the value of X. 4937169689Skan Usually this is an VAR_DECL, if there is no obvious better choice. 493818334Speter X may be an expression, however we only support those expressions 493990075Sobrien generated by loop.c. */ 494018334Speter 494118334Spetertree 4942132718Skanmake_tree (tree type, rtx x) 494318334Speter{ 494418334Speter tree t; 494518334Speter 494618334Speter switch (GET_CODE (x)) 494718334Speter { 494818334Speter case CONST_INT: 4949169689Skan { 4950169689Skan HOST_WIDE_INT hi = 0; 495118334Speter 4952169689Skan if (INTVAL (x) < 0 4953169689Skan && !(TYPE_UNSIGNED (type) 4954169689Skan && (GET_MODE_BITSIZE (TYPE_MODE (type)) 4955169689Skan < HOST_BITS_PER_WIDE_INT))) 4956169689Skan hi = -1; 4957169689Skan 4958169689Skan t = build_int_cst_wide (type, INTVAL (x), hi); 4959169689Skan 4960169689Skan return t; 4961169689Skan } 4962169689Skan 496318334Speter case CONST_DOUBLE: 496418334Speter if (GET_MODE (x) == VOIDmode) 4965169689Skan t = build_int_cst_wide (type, 4966169689Skan CONST_DOUBLE_LOW (x), CONST_DOUBLE_HIGH (x)); 496718334Speter else 496818334Speter { 496918334Speter REAL_VALUE_TYPE d; 497018334Speter 497118334Speter REAL_VALUE_FROM_CONST_DOUBLE (d, x); 497218334Speter t = build_real (type, d); 497318334Speter } 497418334Speter 497518334Speter return t; 497696263Sobrien 497796263Sobrien case CONST_VECTOR: 497896263Sobrien { 4979169689Skan int units = CONST_VECTOR_NUNITS (x); 4980169689Skan tree itype = TREE_TYPE (type); 498196263Sobrien tree t = NULL_TREE; 4982169689Skan int i; 498396263Sobrien 498496263Sobrien 498596263Sobrien /* Build a tree with vector elements. */ 498696263Sobrien for (i = units - 1; i >= 0; --i) 498796263Sobrien { 4988169689Skan rtx elt = CONST_VECTOR_ELT (x, i); 4989169689Skan t = tree_cons (NULL_TREE, make_tree (itype, elt), t); 499096263Sobrien } 499196263Sobrien 499296263Sobrien return build_vector (type, t); 499396263Sobrien } 499496263Sobrien 499518334Speter case PLUS: 4996169689Skan return fold_build2 (PLUS_EXPR, type, make_tree (type, XEXP (x, 0)), 4997169689Skan make_tree (type, XEXP (x, 1))); 499896263Sobrien 499918334Speter case MINUS: 5000169689Skan return fold_build2 (MINUS_EXPR, type, make_tree (type, XEXP (x, 0)), 5001169689Skan make_tree (type, XEXP (x, 1))); 500296263Sobrien 500318334Speter case NEG: 5004169689Skan return fold_build1 (NEGATE_EXPR, type, make_tree (type, XEXP (x, 0))); 500518334Speter 500618334Speter case MULT: 5007169689Skan return fold_build2 (MULT_EXPR, type, make_tree (type, XEXP (x, 0)), 5008169689Skan make_tree (type, XEXP (x, 1))); 500996263Sobrien 501018334Speter case ASHIFT: 5011169689Skan return fold_build2 (LSHIFT_EXPR, type, make_tree (type, XEXP (x, 0)), 5012169689Skan make_tree (type, XEXP (x, 1))); 501396263Sobrien 501418334Speter case LSHIFTRT: 5015169689Skan t = lang_hooks.types.unsigned_type (type); 5016169689Skan return fold_convert (type, build2 (RSHIFT_EXPR, t, 5017169689Skan make_tree (t, XEXP (x, 0)), 5018169689Skan make_tree (type, XEXP (x, 1)))); 501996263Sobrien 502018334Speter case ASHIFTRT: 5021169689Skan t = lang_hooks.types.signed_type (type); 5022169689Skan return fold_convert (type, build2 (RSHIFT_EXPR, t, 5023169689Skan make_tree (t, XEXP (x, 0)), 5024169689Skan make_tree (type, XEXP (x, 1)))); 502596263Sobrien 502618334Speter case DIV: 502718334Speter if (TREE_CODE (type) != REAL_TYPE) 5028169689Skan t = lang_hooks.types.signed_type (type); 502918334Speter else 503018334Speter t = type; 503118334Speter 5032169689Skan return fold_convert (type, build2 (TRUNC_DIV_EXPR, t, 5033169689Skan make_tree (t, XEXP (x, 0)), 5034169689Skan make_tree (t, XEXP (x, 1)))); 503518334Speter case UDIV: 5036169689Skan t = lang_hooks.types.unsigned_type (type); 5037169689Skan return fold_convert (type, build2 (TRUNC_DIV_EXPR, t, 5038169689Skan make_tree (t, XEXP (x, 0)), 5039169689Skan make_tree (t, XEXP (x, 1)))); 5040102780Skan 5041102780Skan case SIGN_EXTEND: 5042102780Skan case ZERO_EXTEND: 5043169689Skan t = lang_hooks.types.type_for_mode (GET_MODE (XEXP (x, 0)), 5044169689Skan GET_CODE (x) == ZERO_EXTEND); 5045169689Skan return fold_convert (type, make_tree (t, XEXP (x, 0))); 5046102780Skan 5047169689Skan case CONST: 5048169689Skan return make_tree (type, XEXP (x, 0)); 504990075Sobrien 5050169689Skan case SYMBOL_REF: 5051169689Skan t = SYMBOL_REF_DECL (x); 5052169689Skan if (t) 5053169689Skan return fold_convert (type, build_fold_addr_expr (t)); 5054169689Skan /* else fall through. */ 5055169689Skan 5056169689Skan default: 5057169689Skan t = build_decl (VAR_DECL, NULL_TREE, type); 5058169689Skan 505990075Sobrien /* If TYPE is a POINTER_TYPE, X might be Pmode with TYPE_MODE being 506090075Sobrien ptr_mode. So convert. */ 5061132718Skan if (POINTER_TYPE_P (type)) 506290075Sobrien x = convert_memory_address (TYPE_MODE (type), x); 506390075Sobrien 5064169689Skan /* Note that we do *not* use SET_DECL_RTL here, because we do not 5065169689Skan want set_decl_rtl to go adjusting REG_ATTRS for this temporary. */ 5066169689Skan t->decl_with_rtl.rtl = x; 5067169689Skan 506818334Speter return t; 506918334Speter } 507018334Speter} 507118334Speter 507218334Speter/* Compute the logical-and of OP0 and OP1, storing it in TARGET 507318334Speter and returning TARGET. 507418334Speter 507518334Speter If TARGET is 0, a pseudo-register or constant is returned. */ 507618334Speter 507718334Speterrtx 5078132718Skanexpand_and (enum machine_mode mode, rtx op0, rtx op1, rtx target) 507918334Speter{ 508096263Sobrien rtx tem = 0; 508118334Speter 508296263Sobrien if (GET_MODE (op0) == VOIDmode && GET_MODE (op1) == VOIDmode) 508396263Sobrien tem = simplify_binary_operation (AND, mode, op0, op1); 508496263Sobrien if (tem == 0) 508518334Speter tem = expand_binop (mode, and_optab, op0, op1, target, 0, OPTAB_LIB_WIDEN); 508618334Speter 508718334Speter if (target == 0) 508818334Speter target = tem; 508918334Speter else if (tem != target) 509018334Speter emit_move_insn (target, tem); 509118334Speter return target; 509218334Speter} 509318334Speter 509418334Speter/* Emit a store-flags instruction for comparison CODE on OP0 and OP1 509518334Speter and storing in TARGET. Normally return TARGET. 509618334Speter Return 0 if that cannot be done. 509718334Speter 509818334Speter MODE is the mode to use for OP0 and OP1 should they be CONST_INTs. If 509996263Sobrien it is VOIDmode, they cannot both be CONST_INT. 510018334Speter 510118334Speter UNSIGNEDP is for the case where we have to widen the operands 510218334Speter to perform the operation. It says to use zero-extension. 510318334Speter 510418334Speter NORMALIZEP is 1 if we should convert the result to be either zero 510550397Sobrien or one. Normalize is -1 if we should convert the result to be 510618334Speter either zero or -1. If NORMALIZEP is zero, the result will be left 510718334Speter "raw" out of the scc insn. */ 510818334Speter 510918334Speterrtx 5110132718Skanemit_store_flag (rtx target, enum rtx_code code, rtx op0, rtx op1, 5111132718Skan enum machine_mode mode, int unsignedp, int normalizep) 511218334Speter{ 511318334Speter rtx subtarget; 511418334Speter enum insn_code icode; 511518334Speter enum machine_mode compare_mode; 511618334Speter enum machine_mode target_mode = GET_MODE (target); 511718334Speter rtx tem; 511818334Speter rtx last = get_last_insn (); 511918334Speter rtx pattern, comparison; 512018334Speter 512190075Sobrien if (unsignedp) 512290075Sobrien code = unsigned_condition (code); 512390075Sobrien 512418334Speter /* If one operand is constant, make it the second one. Only do this 512518334Speter if the other operand is not constant as well. */ 512618334Speter 512790075Sobrien if (swap_commutative_operands_p (op0, op1)) 512818334Speter { 512918334Speter tem = op0; 513018334Speter op0 = op1; 513118334Speter op1 = tem; 513218334Speter code = swap_condition (code); 513318334Speter } 513418334Speter 513518334Speter if (mode == VOIDmode) 513618334Speter mode = GET_MODE (op0); 513718334Speter 513896263Sobrien /* For some comparisons with 1 and -1, we can convert this to 513918334Speter comparisons with zero. This will often produce more opportunities for 514050397Sobrien store-flag insns. */ 514118334Speter 514218334Speter switch (code) 514318334Speter { 514418334Speter case LT: 514518334Speter if (op1 == const1_rtx) 514618334Speter op1 = const0_rtx, code = LE; 514718334Speter break; 514818334Speter case LE: 514918334Speter if (op1 == constm1_rtx) 515018334Speter op1 = const0_rtx, code = LT; 515118334Speter break; 515218334Speter case GE: 515318334Speter if (op1 == const1_rtx) 515418334Speter op1 = const0_rtx, code = GT; 515518334Speter break; 515618334Speter case GT: 515718334Speter if (op1 == constm1_rtx) 515818334Speter op1 = const0_rtx, code = GE; 515918334Speter break; 516018334Speter case GEU: 516118334Speter if (op1 == const1_rtx) 516218334Speter op1 = const0_rtx, code = NE; 516318334Speter break; 516418334Speter case LTU: 516518334Speter if (op1 == const1_rtx) 516618334Speter op1 = const0_rtx, code = EQ; 516718334Speter break; 516850397Sobrien default: 516950397Sobrien break; 517018334Speter } 517118334Speter 5172169689Skan /* If we are comparing a double-word integer with zero or -1, we can 5173169689Skan convert the comparison into one involving a single word. */ 517490075Sobrien if (GET_MODE_BITSIZE (mode) == BITS_PER_WORD * 2 517590075Sobrien && GET_MODE_CLASS (mode) == MODE_INT 5176169689Skan && (!MEM_P (op0) || ! MEM_VOLATILE_P (op0))) 517790075Sobrien { 5178169689Skan if ((code == EQ || code == NE) 5179169689Skan && (op1 == const0_rtx || op1 == constm1_rtx)) 518090075Sobrien { 5181117395Skan rtx op00, op01, op0both; 5182117395Skan 5183169689Skan /* Do a logical OR or AND of the two words and compare the result. */ 5184117395Skan op00 = simplify_gen_subreg (word_mode, op0, mode, 0); 5185117395Skan op01 = simplify_gen_subreg (word_mode, op0, mode, UNITS_PER_WORD); 5186169689Skan op0both = expand_binop (word_mode, 5187169689Skan op1 == const0_rtx ? ior_optab : and_optab, 5188169689Skan op00, op01, NULL_RTX, unsignedp, OPTAB_DIRECT); 5189169689Skan 519090075Sobrien if (op0both != 0) 519190075Sobrien return emit_store_flag (target, code, op0both, op1, word_mode, 519290075Sobrien unsignedp, normalizep); 519390075Sobrien } 5194169689Skan else if ((code == LT || code == GE) && op1 == const0_rtx) 5195117395Skan { 5196117395Skan rtx op0h; 5197117395Skan 5198117395Skan /* If testing the sign bit, can just test on high word. */ 5199117395Skan op0h = simplify_gen_subreg (word_mode, op0, mode, 5200117395Skan subreg_highpart_offset (word_mode, mode)); 5201117395Skan return emit_store_flag (target, code, op0h, op1, word_mode, 5202117395Skan unsignedp, normalizep); 5203117395Skan } 520490075Sobrien } 520590075Sobrien 520618334Speter /* From now on, we won't change CODE, so set ICODE now. */ 520718334Speter icode = setcc_gen_code[(int) code]; 520818334Speter 520918334Speter /* If this is A < 0 or A >= 0, we can do this by taking the ones 521018334Speter complement of A (for GE) and shifting the sign bit to the low bit. */ 521118334Speter if (op1 == const0_rtx && (code == LT || code == GE) 521218334Speter && GET_MODE_CLASS (mode) == MODE_INT 521318334Speter && (normalizep || STORE_FLAG_VALUE == 1 521418334Speter || (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT 521550397Sobrien && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode)) 5216132718Skan == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1))))) 521718334Speter { 521818334Speter subtarget = target; 521918334Speter 522018334Speter /* If the result is to be wider than OP0, it is best to convert it 522118334Speter first. If it is to be narrower, it is *incorrect* to convert it 522218334Speter first. */ 522318334Speter if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (mode)) 522418334Speter { 522518334Speter op0 = convert_modes (target_mode, mode, op0, 0); 522618334Speter mode = target_mode; 522718334Speter } 522818334Speter 522918334Speter if (target_mode != mode) 523018334Speter subtarget = 0; 523118334Speter 523218334Speter if (code == GE) 523350397Sobrien op0 = expand_unop (mode, one_cmpl_optab, op0, 523450397Sobrien ((STORE_FLAG_VALUE == 1 || normalizep) 523550397Sobrien ? 0 : subtarget), 0); 523618334Speter 523750397Sobrien if (STORE_FLAG_VALUE == 1 || normalizep) 523818334Speter /* If we are supposed to produce a 0/1 value, we want to do 523918334Speter a logical shift from the sign bit to the low-order bit; for 524018334Speter a -1/0 value, we do an arithmetic shift. */ 524118334Speter op0 = expand_shift (RSHIFT_EXPR, mode, op0, 524218334Speter size_int (GET_MODE_BITSIZE (mode) - 1), 524318334Speter subtarget, normalizep != -1); 524418334Speter 524518334Speter if (mode != target_mode) 524618334Speter op0 = convert_modes (target_mode, mode, op0, 0); 524718334Speter 524818334Speter return op0; 524918334Speter } 525018334Speter 525118334Speter if (icode != CODE_FOR_nothing) 525218334Speter { 525390075Sobrien insn_operand_predicate_fn pred; 525490075Sobrien 525518334Speter /* We think we may be able to do this with a scc insn. Emit the 5256169689Skan comparison and then the scc insn. */ 525718334Speter 525870635Sobrien do_pending_stack_adjust (); 525918334Speter last = get_last_insn (); 526018334Speter 526118334Speter comparison 526290075Sobrien = compare_from_rtx (op0, op1, code, unsignedp, mode, NULL_RTX); 5263169689Skan if (CONSTANT_P (comparison)) 5264169689Skan { 5265169689Skan switch (GET_CODE (comparison)) 5266169689Skan { 5267169689Skan case CONST_INT: 5268169689Skan if (comparison == const0_rtx) 5269169689Skan return const0_rtx; 5270169689Skan break; 5271169689Skan 5272169689Skan#ifdef FLOAT_STORE_FLAG_VALUE 5273169689Skan case CONST_DOUBLE: 5274169689Skan if (comparison == CONST0_RTX (GET_MODE (comparison))) 5275169689Skan return const0_rtx; 5276169689Skan break; 5277169689Skan#endif 5278169689Skan default: 5279169689Skan gcc_unreachable (); 5280169689Skan } 5281169689Skan 5282169689Skan if (normalizep == 1) 5283169689Skan return const1_rtx; 5284169689Skan if (normalizep == -1) 5285169689Skan return constm1_rtx; 5286169689Skan return const_true_rtx; 5287169689Skan } 528818334Speter 528990075Sobrien /* The code of COMPARISON may not match CODE if compare_from_rtx 529090075Sobrien decided to swap its operands and reverse the original code. 529118334Speter 529290075Sobrien We know that compare_from_rtx returns either a CONST_INT or 529390075Sobrien a new comparison code, so it is safe to just extract the 529490075Sobrien code from COMPARISON. */ 529590075Sobrien code = GET_CODE (comparison); 529618334Speter 529718334Speter /* Get a reference to the target in the proper mode for this insn. */ 529890075Sobrien compare_mode = insn_data[(int) icode].operand[0].mode; 529918334Speter subtarget = target; 530090075Sobrien pred = insn_data[(int) icode].operand[0].predicate; 5301169689Skan if (optimize || ! (*pred) (subtarget, compare_mode)) 530218334Speter subtarget = gen_reg_rtx (compare_mode); 530318334Speter 530418334Speter pattern = GEN_FCN (icode) (subtarget); 530518334Speter if (pattern) 530618334Speter { 530718334Speter emit_insn (pattern); 530818334Speter 530918334Speter /* If we are converting to a wider mode, first convert to 531018334Speter TARGET_MODE, then normalize. This produces better combining 531118334Speter opportunities on machines that have a SIGN_EXTRACT when we are 531218334Speter testing a single bit. This mostly benefits the 68k. 531318334Speter 531418334Speter If STORE_FLAG_VALUE does not have the sign bit set when 531518334Speter interpreted in COMPARE_MODE, we can do this conversion as 531618334Speter unsigned, which is usually more efficient. */ 531718334Speter if (GET_MODE_SIZE (target_mode) > GET_MODE_SIZE (compare_mode)) 531818334Speter { 531918334Speter convert_move (target, subtarget, 532018334Speter (GET_MODE_BITSIZE (compare_mode) 532118334Speter <= HOST_BITS_PER_WIDE_INT) 532218334Speter && 0 == (STORE_FLAG_VALUE 532318334Speter & ((HOST_WIDE_INT) 1 532418334Speter << (GET_MODE_BITSIZE (compare_mode) -1)))); 532518334Speter op0 = target; 532618334Speter compare_mode = target_mode; 532718334Speter } 532818334Speter else 532918334Speter op0 = subtarget; 533018334Speter 533118334Speter /* If we want to keep subexpressions around, don't reuse our 533218334Speter last target. */ 533318334Speter 5334169689Skan if (optimize) 533518334Speter subtarget = 0; 533618334Speter 533718334Speter /* Now normalize to the proper value in COMPARE_MODE. Sometimes 533818334Speter we don't have to do anything. */ 533918334Speter if (normalizep == 0 || normalizep == STORE_FLAG_VALUE) 534018334Speter ; 534190075Sobrien /* STORE_FLAG_VALUE might be the most negative number, so write 534290075Sobrien the comparison this way to avoid a compiler-time warning. */ 534390075Sobrien else if (- normalizep == STORE_FLAG_VALUE) 534418334Speter op0 = expand_unop (compare_mode, neg_optab, op0, subtarget, 0); 534518334Speter 534618334Speter /* We don't want to use STORE_FLAG_VALUE < 0 below since this 534718334Speter makes it hard to use a value of just the sign bit due to 534818334Speter ANSI integer constant typing rules. */ 534918334Speter else if (GET_MODE_BITSIZE (compare_mode) <= HOST_BITS_PER_WIDE_INT 535018334Speter && (STORE_FLAG_VALUE 535118334Speter & ((HOST_WIDE_INT) 1 535218334Speter << (GET_MODE_BITSIZE (compare_mode) - 1)))) 535318334Speter op0 = expand_shift (RSHIFT_EXPR, compare_mode, op0, 535418334Speter size_int (GET_MODE_BITSIZE (compare_mode) - 1), 535518334Speter subtarget, normalizep == 1); 5356169689Skan else 535718334Speter { 5358169689Skan gcc_assert (STORE_FLAG_VALUE & 1); 5359169689Skan 536096263Sobrien op0 = expand_and (compare_mode, op0, const1_rtx, subtarget); 536118334Speter if (normalizep == -1) 536218334Speter op0 = expand_unop (compare_mode, neg_optab, op0, op0, 0); 536318334Speter } 536418334Speter 536596263Sobrien /* If we were converting to a smaller mode, do the 536618334Speter conversion now. */ 536718334Speter if (target_mode != compare_mode) 536818334Speter { 536918334Speter convert_move (target, op0, 0); 537018334Speter return target; 537118334Speter } 537218334Speter else 537318334Speter return op0; 537418334Speter } 537518334Speter } 537618334Speter 537718334Speter delete_insns_since (last); 537818334Speter 5379169689Skan /* If optimizing, use different pseudo registers for each insn, instead 5380169689Skan of reusing the same pseudo. This leads to better CSE, but slows 5381169689Skan down the compiler, since there are more pseudos */ 5382169689Skan subtarget = (!optimize 538318334Speter && (target_mode == mode)) ? target : NULL_RTX; 538418334Speter 538518334Speter /* If we reached here, we can't do this with a scc insn. However, there 538618334Speter are some comparisons that can be done directly. For example, if 538718334Speter this is an equality comparison of integers, we can try to exclusive-or 538818334Speter (or subtract) the two operands and use a recursive call to try the 538918334Speter comparison with zero. Don't do any of these cases if branches are 539018334Speter very cheap. */ 539118334Speter 539218334Speter if (BRANCH_COST > 0 539318334Speter && GET_MODE_CLASS (mode) == MODE_INT && (code == EQ || code == NE) 539418334Speter && op1 != const0_rtx) 539518334Speter { 539618334Speter tem = expand_binop (mode, xor_optab, op0, op1, subtarget, 1, 539718334Speter OPTAB_WIDEN); 539818334Speter 539918334Speter if (tem == 0) 540018334Speter tem = expand_binop (mode, sub_optab, op0, op1, subtarget, 1, 540118334Speter OPTAB_WIDEN); 540218334Speter if (tem != 0) 540318334Speter tem = emit_store_flag (target, code, tem, const0_rtx, 540418334Speter mode, unsignedp, normalizep); 540518334Speter if (tem == 0) 540618334Speter delete_insns_since (last); 540718334Speter return tem; 540818334Speter } 540918334Speter 541096263Sobrien /* Some other cases we can do are EQ, NE, LE, and GT comparisons with 541118334Speter the constant zero. Reject all other comparisons at this point. Only 541218334Speter do LE and GT if branches are expensive since they are expensive on 541318334Speter 2-operand machines. */ 541418334Speter 541518334Speter if (BRANCH_COST == 0 541618334Speter || GET_MODE_CLASS (mode) != MODE_INT || op1 != const0_rtx 541718334Speter || (code != EQ && code != NE 541818334Speter && (BRANCH_COST <= 1 || (code != LE && code != GT)))) 541918334Speter return 0; 542018334Speter 542118334Speter /* See what we need to return. We can only return a 1, -1, or the 542218334Speter sign bit. */ 542318334Speter 542418334Speter if (normalizep == 0) 542518334Speter { 542618334Speter if (STORE_FLAG_VALUE == 1 || STORE_FLAG_VALUE == -1) 542718334Speter normalizep = STORE_FLAG_VALUE; 542818334Speter 542918334Speter else if (GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT 543050397Sobrien && ((STORE_FLAG_VALUE & GET_MODE_MASK (mode)) 543152284Sobrien == (unsigned HOST_WIDE_INT) 1 << (GET_MODE_BITSIZE (mode) - 1))) 543218334Speter ; 543318334Speter else 543418334Speter return 0; 543518334Speter } 543618334Speter 543718334Speter /* Try to put the result of the comparison in the sign bit. Assume we can't 543818334Speter do the necessary operation below. */ 543918334Speter 544018334Speter tem = 0; 544118334Speter 544218334Speter /* To see if A <= 0, compute (A | (A - 1)). A <= 0 iff that result has 544318334Speter the sign bit set. */ 544418334Speter 544518334Speter if (code == LE) 544618334Speter { 544718334Speter /* This is destructive, so SUBTARGET can't be OP0. */ 544818334Speter if (rtx_equal_p (subtarget, op0)) 544918334Speter subtarget = 0; 545018334Speter 545118334Speter tem = expand_binop (mode, sub_optab, op0, const1_rtx, subtarget, 0, 545218334Speter OPTAB_WIDEN); 545318334Speter if (tem) 545418334Speter tem = expand_binop (mode, ior_optab, op0, tem, subtarget, 0, 545518334Speter OPTAB_WIDEN); 545618334Speter } 545718334Speter 545818334Speter /* To see if A > 0, compute (((signed) A) << BITS) - A, where BITS is the 545918334Speter number of bits in the mode of OP0, minus one. */ 546018334Speter 546118334Speter if (code == GT) 546218334Speter { 546318334Speter if (rtx_equal_p (subtarget, op0)) 546418334Speter subtarget = 0; 546518334Speter 546618334Speter tem = expand_shift (RSHIFT_EXPR, mode, op0, 546718334Speter size_int (GET_MODE_BITSIZE (mode) - 1), 546818334Speter subtarget, 0); 546918334Speter tem = expand_binop (mode, sub_optab, tem, op0, subtarget, 0, 547018334Speter OPTAB_WIDEN); 547118334Speter } 547296263Sobrien 547318334Speter if (code == EQ || code == NE) 547418334Speter { 547518334Speter /* For EQ or NE, one way to do the comparison is to apply an operation 5476117395Skan that converts the operand into a positive number if it is nonzero 547718334Speter or zero if it was originally zero. Then, for EQ, we subtract 1 and 547818334Speter for NE we negate. This puts the result in the sign bit. Then we 547996263Sobrien normalize with a shift, if needed. 548018334Speter 548118334Speter Two operations that can do the above actions are ABS and FFS, so try 548218334Speter them. If that doesn't work, and MODE is smaller than a full word, 548318334Speter we can use zero-extension to the wider mode (an unsigned conversion) 548418334Speter as the operation. */ 548518334Speter 548696263Sobrien /* Note that ABS doesn't yield a positive number for INT_MIN, but 548796263Sobrien that is compensated by the subsequent overflow when subtracting 548890075Sobrien one / negating. */ 548990075Sobrien 5490169689Skan if (abs_optab->handlers[mode].insn_code != CODE_FOR_nothing) 549118334Speter tem = expand_unop (mode, abs_optab, op0, subtarget, 1); 5492169689Skan else if (ffs_optab->handlers[mode].insn_code != CODE_FOR_nothing) 549318334Speter tem = expand_unop (mode, ffs_optab, op0, subtarget, 1); 549418334Speter else if (GET_MODE_SIZE (mode) < UNITS_PER_WORD) 549518334Speter { 549618334Speter tem = convert_modes (word_mode, mode, op0, 1); 549718334Speter mode = word_mode; 549818334Speter } 549918334Speter 550018334Speter if (tem != 0) 550118334Speter { 550218334Speter if (code == EQ) 550318334Speter tem = expand_binop (mode, sub_optab, tem, const1_rtx, subtarget, 550418334Speter 0, OPTAB_WIDEN); 550518334Speter else 550618334Speter tem = expand_unop (mode, neg_optab, tem, subtarget, 0); 550718334Speter } 550818334Speter 550918334Speter /* If we couldn't do it that way, for NE we can "or" the two's complement 551018334Speter of the value with itself. For EQ, we take the one's complement of 551118334Speter that "or", which is an extra insn, so we only handle EQ if branches 551218334Speter are expensive. */ 551318334Speter 551418334Speter if (tem == 0 && (code == NE || BRANCH_COST > 1)) 551518334Speter { 551618334Speter if (rtx_equal_p (subtarget, op0)) 551718334Speter subtarget = 0; 551818334Speter 551918334Speter tem = expand_unop (mode, neg_optab, op0, subtarget, 0); 552018334Speter tem = expand_binop (mode, ior_optab, tem, op0, subtarget, 0, 552118334Speter OPTAB_WIDEN); 552218334Speter 552318334Speter if (tem && code == EQ) 552418334Speter tem = expand_unop (mode, one_cmpl_optab, tem, subtarget, 0); 552518334Speter } 552618334Speter } 552718334Speter 552818334Speter if (tem && normalizep) 552918334Speter tem = expand_shift (RSHIFT_EXPR, mode, tem, 553018334Speter size_int (GET_MODE_BITSIZE (mode) - 1), 553118334Speter subtarget, normalizep == 1); 553218334Speter 553318334Speter if (tem) 553418334Speter { 553518334Speter if (GET_MODE (tem) != target_mode) 553618334Speter { 553718334Speter convert_move (target, tem, 0); 553818334Speter tem = target; 553918334Speter } 554018334Speter else if (!subtarget) 554118334Speter { 554218334Speter emit_move_insn (target, tem); 554318334Speter tem = target; 554418334Speter } 554518334Speter } 554618334Speter else 554718334Speter delete_insns_since (last); 554818334Speter 554918334Speter return tem; 555018334Speter} 555150397Sobrien 555250397Sobrien/* Like emit_store_flag, but always succeeds. */ 555350397Sobrien 555450397Sobrienrtx 5555132718Skanemit_store_flag_force (rtx target, enum rtx_code code, rtx op0, rtx op1, 5556132718Skan enum machine_mode mode, int unsignedp, int normalizep) 555750397Sobrien{ 555850397Sobrien rtx tem, label; 555950397Sobrien 556050397Sobrien /* First see if emit_store_flag can do the job. */ 556150397Sobrien tem = emit_store_flag (target, code, op0, op1, mode, unsignedp, normalizep); 556250397Sobrien if (tem != 0) 556350397Sobrien return tem; 556450397Sobrien 556550397Sobrien if (normalizep == 0) 556650397Sobrien normalizep = 1; 556750397Sobrien 556850397Sobrien /* If this failed, we have to do this with set/compare/jump/set code. */ 556950397Sobrien 5570169689Skan if (!REG_P (target) 557150397Sobrien || reg_mentioned_p (target, op0) || reg_mentioned_p (target, op1)) 557250397Sobrien target = gen_reg_rtx (GET_MODE (target)); 557350397Sobrien 557450397Sobrien emit_move_insn (target, const1_rtx); 557550397Sobrien label = gen_label_rtx (); 557690075Sobrien do_compare_rtx_and_jump (op0, op1, code, unsignedp, mode, NULL_RTX, 557790075Sobrien NULL_RTX, label); 557850397Sobrien 557950397Sobrien emit_move_insn (target, const0_rtx); 558050397Sobrien emit_label (label); 558150397Sobrien 558250397Sobrien return target; 558350397Sobrien} 558450397Sobrien 558550397Sobrien/* Perform possibly multi-word comparison and conditional jump to LABEL 5586169689Skan if ARG1 OP ARG2 true where ARG1 and ARG2 are of mode MODE. This is 5587169689Skan now a thin wrapper around do_compare_rtx_and_jump. */ 558850397Sobrien 558950397Sobrienstatic void 5590132718Skando_cmp_and_jump (rtx arg1, rtx arg2, enum rtx_code op, enum machine_mode mode, 5591132718Skan rtx label) 559250397Sobrien{ 5593169689Skan int unsignedp = (op == LTU || op == LEU || op == GTU || op == GEU); 5594169689Skan do_compare_rtx_and_jump (arg1, arg2, op, unsignedp, mode, 5595169689Skan NULL_RTX, NULL_RTX, label); 559650397Sobrien} 5597