X-Git-Url: http://git.sourceforge.jp/view?p=pf3gnuchains%2Fgcc-fork.git;a=blobdiff_plain;f=gcc%2Frtlanal.c;h=da9774e488befcad3885d7c6e8d8c5c80e1c828e;hp=6d391eaf374b55773a09686c3f2a1e50a28faaba;hb=efb9d9ee8e1478917ccbfa1e47447d8dfb63953c;hpb=0a8176f36ec372a4571f006c8262b5aa8a29b65c diff --git a/gcc/rtlanal.c b/gcc/rtlanal.c index 6d391eaf374..da9774e488b 100644 --- a/gcc/rtlanal.c +++ b/gcc/rtlanal.c @@ -1,6 +1,6 @@ /* Analyze RTL for C-Compiler Copyright (C) 1987, 1988, 1992, 1993, 1994, 1995, 1996, 1997, 1998, - 1999, 2000, 2001, 2002 Free Software Foundation, Inc. + 1999, 2000, 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. This file is part of GCC. @@ -22,24 +22,45 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "config.h" #include "system.h" +#include "coretypes.h" +#include "tm.h" #include "toplev.h" #include "rtl.h" #include "hard-reg-set.h" #include "insn-config.h" #include "recog.h" +#include "target.h" +#include "output.h" #include "tm_p.h" #include "flags.h" -#include "basic-block.h" #include "real.h" +#include "regs.h" +#include "function.h" /* Forward declarations */ -static int global_reg_mentioned_p_1 PARAMS ((rtx *, void *)); -static void set_of_1 PARAMS ((rtx, rtx, void *)); -static void insn_dependent_p_1 PARAMS ((rtx, rtx, void *)); -static int computed_jump_p_1 PARAMS ((rtx)); -static void parms_set PARAMS ((rtx, rtx, void *)); -static bool hoist_test_store PARAMS ((rtx, rtx, regset)); -static void hoist_update_store PARAMS ((rtx, rtx *, rtx, rtx)); +static int global_reg_mentioned_p_1 (rtx *, void *); +static void set_of_1 (rtx, rtx, void *); +static bool covers_regno_p (rtx, unsigned int); +static bool covers_regno_no_parallel_p (rtx, unsigned int); +static int rtx_referenced_p_1 (rtx *, void *); +static int computed_jump_p_1 (rtx); +static void parms_set (rtx, rtx, void *); + +static unsigned HOST_WIDE_INT cached_nonzero_bits (rtx, enum machine_mode, + rtx, enum machine_mode, + unsigned HOST_WIDE_INT); +static unsigned HOST_WIDE_INT nonzero_bits1 (rtx, enum machine_mode, rtx, + enum machine_mode, + unsigned HOST_WIDE_INT); +static unsigned int cached_num_sign_bit_copies (rtx, enum machine_mode, rtx, + enum machine_mode, + unsigned int); +static unsigned int num_sign_bit_copies1 (rtx, enum machine_mode, rtx, + enum machine_mode, unsigned int); + +/* Offset of the first 'e', 'E' or 'V' operand for each rtx code, or + -1 if a code has no such operand. */ +static int non_rtx_starting_operands[NUM_RTX_CODE]; /* Bit flags that specify the machine subtype we are compiling for. Bits are tested using macros TARGET_... defined in the tm.h file @@ -53,8 +74,7 @@ int target_flags; (within one function) and so is anything marked `unchanging'. */ int -rtx_unstable_p (x) - rtx x; +rtx_unstable_p (rtx x) { RTX_CODE code = GET_CODE (x); int i; @@ -63,12 +83,8 @@ rtx_unstable_p (x) switch (code) { case MEM: - return ! RTX_UNCHANGING_P (x) || rtx_unstable_p (XEXP (x, 0)); + return !MEM_READONLY_P (x) || rtx_unstable_p (XEXP (x, 0)); - case QUEUED: - return 1; - - case ADDRESSOF: case CONST: case CONST_INT: case CONST_DOUBLE: @@ -81,8 +97,7 @@ rtx_unstable_p (x) /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */ if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx /* The arg pointer varies if it is not a fixed register. */ - || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM]) - || RTX_UNCHANGING_P (x)) + || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])) return 0; #ifndef PIC_OFFSET_TABLE_REG_CALL_CLOBBERED /* ??? When call-clobbered, the value is stable modulo the restore @@ -97,7 +112,7 @@ rtx_unstable_p (x) if (MEM_VOLATILE_P (x)) return 1; - /* FALLTHROUGH */ + /* Fall through. */ default: break; @@ -129,21 +144,20 @@ rtx_unstable_p (x) The frame pointer and the arg pointer are considered constant. */ int -rtx_varies_p (x, for_alias) - rtx x; - int for_alias; +rtx_varies_p (rtx x, int for_alias) { - RTX_CODE code = GET_CODE (x); + RTX_CODE code; int i; const char *fmt; + if (!x) + return 0; + + code = GET_CODE (x); switch (code) { case MEM: - return ! RTX_UNCHANGING_P (x) || rtx_varies_p (XEXP (x, 0), for_alias); - - case QUEUED: - return 1; + return !MEM_READONLY_P (x) || rtx_varies_p (XEXP (x, 0), for_alias); case CONST: case CONST_INT: @@ -185,7 +199,7 @@ rtx_varies_p (x, for_alias) if (MEM_VOLATILE_P (x)) return 1; - /* FALLTHROUGH */ + /* Fall through. */ default: break; @@ -212,8 +226,7 @@ rtx_varies_p (x, for_alias) /* Return 0 if the use of X as an address in a MEM can cause a trap. */ int -rtx_addr_can_trap_p (x) - rtx x; +rtx_addr_can_trap_p (rtx x) { enum rtx_code code = GET_CODE (x); @@ -269,6 +282,85 @@ rtx_addr_can_trap_p (x) return 1; } +/* Return true if X is an address that is known to not be zero. */ + +bool +nonzero_address_p (rtx x) +{ + enum rtx_code code = GET_CODE (x); + + switch (code) + { + case SYMBOL_REF: + return !SYMBOL_REF_WEAK (x); + + case LABEL_REF: + return true; + + case REG: + /* As in rtx_varies_p, we have to use the actual rtx, not reg number. */ + if (x == frame_pointer_rtx || x == hard_frame_pointer_rtx + || x == stack_pointer_rtx + || (x == arg_pointer_rtx && fixed_regs[ARG_POINTER_REGNUM])) + return true; + /* All of the virtual frame registers are stack references. */ + if (REGNO (x) >= FIRST_VIRTUAL_REGISTER + && REGNO (x) <= LAST_VIRTUAL_REGISTER) + return true; + return false; + + case CONST: + return nonzero_address_p (XEXP (x, 0)); + + case PLUS: + if (GET_CODE (XEXP (x, 1)) == CONST_INT) + { + /* Pointers aren't allowed to wrap. If we've got a register + that is known to be a pointer, and a positive offset, then + the composite can't be zero. */ + if (INTVAL (XEXP (x, 1)) > 0 + && REG_P (XEXP (x, 0)) + && REG_POINTER (XEXP (x, 0))) + return true; + + return nonzero_address_p (XEXP (x, 0)); + } + /* Handle PIC references. */ + else if (XEXP (x, 0) == pic_offset_table_rtx + && CONSTANT_P (XEXP (x, 1))) + return true; + return false; + + case PRE_MODIFY: + /* Similar to the above; allow positive offsets. Further, since + auto-inc is only allowed in memories, the register must be a + pointer. */ + if (GET_CODE (XEXP (x, 1)) == CONST_INT + && INTVAL (XEXP (x, 1)) > 0) + return true; + return nonzero_address_p (XEXP (x, 0)); + + case PRE_INC: + /* Similarly. Further, the offset is always positive. */ + return true; + + case PRE_DEC: + case POST_DEC: + case POST_INC: + case POST_MODIFY: + return nonzero_address_p (XEXP (x, 0)); + + case LO_SUM: + return nonzero_address_p (XEXP (x, 1)); + + default: + break; + } + + /* If it isn't one of the case above, might be zero. */ + return false; +} + /* Return 1 if X refers to a memory location whose address cannot be compared reliably with constant addresses, or if X refers to a BLKmode memory object. @@ -276,9 +368,7 @@ rtx_addr_can_trap_p (x) zero, we are slightly more conservative. */ int -rtx_addr_varies_p (x, for_alias) - rtx x; - int for_alias; +rtx_addr_varies_p (rtx x, int for_alias) { enum rtx_code code; int i; @@ -314,8 +404,7 @@ rtx_addr_varies_p (x, for_alias) This is used in cse.c with the `related_value' field. */ HOST_WIDE_INT -get_integer_term (x) - rtx x; +get_integer_term (rtx x) { if (GET_CODE (x) == CONST) x = XEXP (x, 0); @@ -334,8 +423,7 @@ get_integer_term (x) Only obvious integer terms are detected. */ rtx -get_related_value (x) - rtx x; +get_related_value (rtx x) { if (GET_CODE (x) != CONST) return 0; @@ -349,153 +437,11 @@ get_related_value (x) return 0; } -/* Given a tablejump insn INSN, return the RTL expression for the offset - into the jump table. If the offset cannot be determined, then return - NULL_RTX. - - If EARLIEST is non-zero, it is a pointer to a place where the earliest - insn used in locating the offset was found. */ - -rtx -get_jump_table_offset (insn, earliest) - rtx insn; - rtx *earliest; -{ - rtx label; - rtx table; - rtx set; - rtx old_insn; - rtx x; - rtx old_x; - rtx y; - rtx old_y; - int i; - - if (GET_CODE (insn) != JUMP_INSN - || ! (label = JUMP_LABEL (insn)) - || ! (table = NEXT_INSN (label)) - || GET_CODE (table) != JUMP_INSN - || (GET_CODE (PATTERN (table)) != ADDR_VEC - && GET_CODE (PATTERN (table)) != ADDR_DIFF_VEC) - || ! (set = single_set (insn))) - return NULL_RTX; - - x = SET_SRC (set); - - /* Some targets (eg, ARM) emit a tablejump that also - contains the out-of-range target. */ - if (GET_CODE (x) == IF_THEN_ELSE - && GET_CODE (XEXP (x, 2)) == LABEL_REF) - x = XEXP (x, 1); - - /* Search backwards and locate the expression stored in X. */ - for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x; - old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0)) - ; - - /* If X is an expression using a relative address then strip - off the addition / subtraction of PC, PIC_OFFSET_TABLE_REGNUM, - or the jump table label. */ - if (GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC - && (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS)) - { - for (i = 0; i < 2; i++) - { - old_insn = insn; - y = XEXP (x, i); - - if (y == pc_rtx || y == pic_offset_table_rtx) - break; - - for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y; - old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0)) - ; - - if ((GET_CODE (y) == LABEL_REF && XEXP (y, 0) == label)) - break; - } - - if (i >= 2) - return NULL_RTX; - - x = XEXP (x, 1 - i); - - for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x; - old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0)) - ; - } - - /* Strip off any sign or zero extension. */ - if (GET_CODE (x) == SIGN_EXTEND || GET_CODE (x) == ZERO_EXTEND) - { - x = XEXP (x, 0); - - for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x; - old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0)) - ; - } - - /* If X isn't a MEM then this isn't a tablejump we understand. */ - if (GET_CODE (x) != MEM) - return NULL_RTX; - - /* Strip off the MEM. */ - x = XEXP (x, 0); - - for (old_x = NULL_RTX; GET_CODE (x) == REG && x != old_x; - old_x = x, x = find_last_value (x, &insn, NULL_RTX, 0)) - ; - - /* If X isn't a PLUS than this isn't a tablejump we understand. */ - if (GET_CODE (x) != PLUS) - return NULL_RTX; - - /* At this point we should have an expression representing the jump table - plus an offset. Examine each operand in order to determine which one - represents the jump table. Knowing that tells us that the other operand - must represent the offset. */ - for (i = 0; i < 2; i++) - { - old_insn = insn; - y = XEXP (x, i); - - for (old_y = NULL_RTX; GET_CODE (y) == REG && y != old_y; - old_y = y, y = find_last_value (y, &old_insn, NULL_RTX, 0)) - ; - - if ((GET_CODE (y) == CONST || GET_CODE (y) == LABEL_REF) - && reg_mentioned_p (label, y)) - break; - } - - if (i >= 2) - return NULL_RTX; - - x = XEXP (x, 1 - i); - - /* Strip off the addition / subtraction of PIC_OFFSET_TABLE_REGNUM. */ - if (GET_CODE (x) == PLUS || GET_CODE (x) == MINUS) - for (i = 0; i < 2; i++) - if (XEXP (x, i) == pic_offset_table_rtx) - { - x = XEXP (x, 1 - i); - break; - } - - if (earliest) - *earliest = insn; - - /* Return the RTL expression representing the offset. */ - return x; -} - /* A subroutine of global_reg_mentioned_p, returns 1 if *LOC mentions a global register. */ static int -global_reg_mentioned_p_1 (loc, data) - rtx *loc; - void *data ATTRIBUTE_UNUSED; +global_reg_mentioned_p_1 (rtx *loc, void *data ATTRIBUTE_UNUSED) { int regno; rtx x = *loc; @@ -506,7 +452,7 @@ global_reg_mentioned_p_1 (loc, data) switch (GET_CODE (x)) { case SUBREG: - if (GET_CODE (SUBREG_REG (x)) == REG) + if (REG_P (SUBREG_REG (x))) { if (REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER && global_regs[subreg_regno (x)]) @@ -541,16 +487,14 @@ global_reg_mentioned_p_1 (loc, data) return 0; } -/* Returns non-zero if X mentions a global register. */ +/* Returns nonzero if X mentions a global register. */ int -global_reg_mentioned_p (x) - rtx x; +global_reg_mentioned_p (rtx x) { - if (INSN_P (x)) { - if (GET_CODE (x) == CALL_INSN) + if (CALL_P (x)) { if (! CONST_OR_PURE_CALL_P (x)) return 1; @@ -569,9 +513,7 @@ global_reg_mentioned_p (x) zero, we do not count occurrences inside the destination of a SET. */ int -count_occurrences (x, find, count_dest) - rtx x, find; - int count_dest; +count_occurrences (rtx x, rtx find, int count_dest) { int i, j; enum rtx_code code; @@ -596,7 +538,7 @@ count_occurrences (x, find, count_dest) return 0; case MEM: - if (GET_CODE (find) == MEM && rtx_equal_p (x, find)) + if (MEM_P (find) && rtx_equal_p (x, find)) return 1; break; @@ -634,8 +576,7 @@ count_occurrences (x, find, count_dest) for a subexpression of IN that is Lisp "equal" to REG. */ int -reg_mentioned_p (reg, in) - rtx reg, in; +reg_mentioned_p (rtx reg, rtx in) { const char *fmt; int i; @@ -656,7 +597,7 @@ reg_mentioned_p (reg, in) { /* Compare registers by number. */ case REG: - return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg); + return REG_P (reg) && REGNO (in) == REGNO (reg); /* These codes have no constituent expressions and are unique. */ @@ -666,8 +607,6 @@ reg_mentioned_p (reg, in) return 0; case CONST_INT: - return GET_CODE (reg) == CONST_INT && INTVAL (in) == INTVAL (reg); - case CONST_VECTOR: case CONST_DOUBLE: /* These are kept unique for a given value. */ @@ -702,28 +641,13 @@ reg_mentioned_p (reg, in) no CODE_LABEL insn. */ int -no_labels_between_p (beg, end) - rtx beg, end; +no_labels_between_p (rtx beg, rtx end) { rtx p; if (beg == end) return 0; for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p)) - if (GET_CODE (p) == CODE_LABEL) - return 0; - return 1; -} - -/* Return 1 if in between BEG and END, exclusive of BEG and END, there is - no JUMP_INSN insn. */ - -int -no_jumps_between_p (beg, end) - rtx beg, end; -{ - rtx p; - for (p = NEXT_INSN (beg); p != end; p = NEXT_INSN (p)) - if (GET_CODE (p) == JUMP_INSN) + if (LABEL_P (p)) return 0; return 1; } @@ -732,8 +656,7 @@ no_jumps_between_p (beg, end) FROM_INSN and TO_INSN (exclusive of those two). */ int -reg_used_between_p (reg, from_insn, to_insn) - rtx reg, from_insn, to_insn; +reg_used_between_p (rtx reg, rtx from_insn, rtx to_insn) { rtx insn; @@ -743,7 +666,7 @@ reg_used_between_p (reg, from_insn, to_insn) for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn)) if (INSN_P (insn) && (reg_overlap_mentioned_p (reg, PATTERN (insn)) - || (GET_CODE (insn) == CALL_INSN + || (CALL_P (insn) && (find_reg_fusage (insn, USE, reg) || find_reg_fusage (insn, CLOBBER, reg))))) return 1; @@ -755,9 +678,7 @@ reg_used_between_p (reg, from_insn, to_insn) we do not consider it a reference. */ int -reg_referenced_p (x, body) - rtx x; - rtx body; +reg_referenced_p (rtx x, rtx body) { int i; @@ -772,9 +693,9 @@ reg_referenced_p (x, body) it is mentioned in the destination. */ if (GET_CODE (SET_DEST (body)) != CC0 && GET_CODE (SET_DEST (body)) != PC - && GET_CODE (SET_DEST (body)) != REG + && !REG_P (SET_DEST (body)) && ! (GET_CODE (SET_DEST (body)) == SUBREG - && GET_CODE (SUBREG_REG (SET_DEST (body))) == REG + && REG_P (SUBREG_REG (SET_DEST (body))) && (((GET_MODE_SIZE (GET_MODE (SUBREG_REG (SET_DEST (body)))) + (UNITS_PER_WORD - 1)) / UNITS_PER_WORD) == ((GET_MODE_SIZE (GET_MODE (SET_DEST (body))) @@ -814,7 +735,7 @@ reg_referenced_p (x, body) return 0; case CLOBBER: - if (GET_CODE (XEXP (body, 0)) == MEM) + if (MEM_P (XEXP (body, 0))) if (reg_overlap_mentioned_p (x, XEXP (XEXP (body, 0), 0))) return 1; return 0; @@ -828,35 +749,12 @@ reg_referenced_p (x, body) return 0; } } - -/* Nonzero if register REG is referenced in an insn between - FROM_INSN and TO_INSN (exclusive of those two). Sets of REG do - not count. */ - -int -reg_referenced_between_p (reg, from_insn, to_insn) - rtx reg, from_insn, to_insn; -{ - rtx insn; - - if (from_insn == to_insn) - return 0; - - for (insn = NEXT_INSN (from_insn); insn != to_insn; insn = NEXT_INSN (insn)) - if (INSN_P (insn) - && (reg_referenced_p (reg, PATTERN (insn)) - || (GET_CODE (insn) == CALL_INSN - && find_reg_fusage (insn, USE, reg)))) - return 1; - return 0; -} /* Nonzero if register REG is set or clobbered in an insn between FROM_INSN and TO_INSN (exclusive of those two). */ int -reg_set_between_p (reg, from_insn, to_insn) - rtx reg, from_insn, to_insn; +reg_set_between_p (rtx reg, rtx from_insn, rtx to_insn) { rtx insn; @@ -871,94 +769,38 @@ reg_set_between_p (reg, from_insn, to_insn) /* Internals of reg_set_between_p. */ int -reg_set_p (reg, insn) - rtx reg, insn; +reg_set_p (rtx reg, rtx insn) { - rtx body = insn; - /* We can be passed an insn or part of one. If we are passed an insn, check if a side-effect of the insn clobbers REG. */ - if (INSN_P (insn)) - { - if (FIND_REG_INC_NOTE (insn, reg) - || (GET_CODE (insn) == CALL_INSN - /* We'd like to test call_used_regs here, but rtlanal.c can't - reference that variable due to its use in genattrtab. So - we'll just be more conservative. - - ??? Unless we could ensure that the CALL_INSN_FUNCTION_USAGE - information holds all clobbered registers. */ - && ((GET_CODE (reg) == REG - && REGNO (reg) < FIRST_PSEUDO_REGISTER) - || GET_CODE (reg) == MEM - || find_reg_fusage (insn, CLOBBER, reg)))) - return 1; - - body = PATTERN (insn); - } + if (INSN_P (insn) + && (FIND_REG_INC_NOTE (insn, reg) + || (CALL_P (insn) + && ((REG_P (reg) + && REGNO (reg) < FIRST_PSEUDO_REGISTER + && TEST_HARD_REG_BIT (regs_invalidated_by_call, + REGNO (reg))) + || MEM_P (reg) + || find_reg_fusage (insn, CLOBBER, reg))))) + return 1; return set_of (reg, insn) != NULL_RTX; } /* Similar to reg_set_between_p, but check all registers in X. Return 0 - only if none of them are modified between START and END. Do not - consider non-registers one way or the other. */ - -int -regs_set_between_p (x, start, end) - rtx x; - rtx start, end; -{ - enum rtx_code code = GET_CODE (x); - const char *fmt; - int i, j; - - switch (code) - { - case CONST_INT: - case CONST_DOUBLE: - case CONST_VECTOR: - case CONST: - case SYMBOL_REF: - case LABEL_REF: - case PC: - case CC0: - return 0; - - case REG: - return reg_set_between_p (x, start, end); - - default: - break; - } - - fmt = GET_RTX_FORMAT (code); - for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) - { - if (fmt[i] == 'e' && regs_set_between_p (XEXP (x, i), start, end)) - return 1; - - else if (fmt[i] == 'E') - for (j = XVECLEN (x, i) - 1; j >= 0; j--) - if (regs_set_between_p (XVECEXP (x, i, j), start, end)) - return 1; - } - - return 0; -} - -/* Similar to reg_set_between_p, but check all registers in X. Return 0 only if none of them are modified between START and END. Return 1 if - X contains a MEM; this routine does not perform any memory aliasing. */ + X contains a MEM; this routine does usememory aliasing. */ int -modified_between_p (x, start, end) - rtx x; - rtx start, end; +modified_between_p (rtx x, rtx start, rtx end) { enum rtx_code code = GET_CODE (x); const char *fmt; int i, j; + rtx insn; + + if (start == end) + return 0; switch (code) { @@ -975,10 +817,14 @@ modified_between_p (x, start, end) return 1; case MEM: - /* If the memory is not constant, assume it is modified. If it is - constant, we still have to check the address. */ - if (! RTX_UNCHANGING_P (x)) + if (modified_between_p (XEXP (x, 0), start, end)) return 1; + if (MEM_READONLY_P (x)) + return 0; + for (insn = NEXT_INSN (start); insn != end; insn = NEXT_INSN (insn)) + if (memory_modified_in_insn_p (x, insn)) + return 1; + return 0; break; case REG: @@ -1005,12 +851,10 @@ modified_between_p (x, start, end) /* Similar to reg_set_p, but check all registers in X. Return 0 only if none of them are modified in INSN. Return 1 if X contains a MEM; this routine - does not perform any memory aliasing. */ + does use memory aliasing. */ int -modified_in_p (x, insn) - rtx x; - rtx insn; +modified_in_p (rtx x, rtx insn) { enum rtx_code code = GET_CODE (x); const char *fmt; @@ -1031,10 +875,13 @@ modified_in_p (x, insn) return 1; case MEM: - /* If the memory is not constant, assume it is modified. If it is - constant, we still have to check the address. */ - if (! RTX_UNCHANGING_P (x)) + if (modified_in_p (XEXP (x, 0), insn)) + return 1; + if (MEM_READONLY_P (x)) + return 0; + if (memory_modified_in_insn_p (x, insn)) return 1; + return 0; break; case REG: @@ -1058,45 +905,6 @@ modified_in_p (x, insn) return 0; } - -/* Return true if anything in insn X is (anti,output,true) dependent on - anything in insn Y. */ - -int -insn_dependent_p (x, y) - rtx x, y; -{ - rtx tmp; - - if (! INSN_P (x) || ! INSN_P (y)) - abort (); - - tmp = PATTERN (y); - note_stores (PATTERN (x), insn_dependent_p_1, &tmp); - if (tmp == NULL_RTX) - return 1; - - tmp = PATTERN (x); - note_stores (PATTERN (y), insn_dependent_p_1, &tmp); - if (tmp == NULL_RTX) - return 1; - - return 0; -} - -/* A helper routine for insn_dependent_p called through note_stores. */ - -static void -insn_dependent_p_1 (x, pat, data) - rtx x; - rtx pat ATTRIBUTE_UNUSED; - void *data; -{ - rtx * pinsn = (rtx *) data; - - if (*pinsn && reg_mentioned_p (x, *pinsn)) - *pinsn = NULL_RTX; -} /* Helper function for set_of. */ struct set_of_data @@ -1106,22 +914,18 @@ struct set_of_data }; static void -set_of_1 (x, pat, data1) - rtx x; - rtx pat; - void *data1; +set_of_1 (rtx x, rtx pat, void *data1) { struct set_of_data *data = (struct set_of_data *) (data1); if (rtx_equal_p (x, data->pat) - || (GET_CODE (x) != MEM && reg_overlap_mentioned_p (data->pat, x))) + || (!MEM_P (x) && reg_overlap_mentioned_p (data->pat, x))) data->found = pat; } /* Give an INSN, return a SET or CLOBBER expression that does modify PAT (either directly or via STRICT_LOW_PART and similar modifiers). */ rtx -set_of (pat, insn) - rtx pat, insn; +set_of (rtx pat, rtx insn) { struct set_of_data data; data.found = NULL_RTX; @@ -1135,8 +939,7 @@ set_of (pat, insn) will not be used, which we ignore. */ rtx -single_set_2 (insn, pat) - rtx insn, pat; +single_set_2 (rtx insn, rtx pat) { rtx set = NULL; int set_verified = 1; @@ -1189,8 +992,7 @@ single_set_2 (insn, pat) zero. */ int -multiple_sets (insn) - rtx insn; +multiple_sets (rtx insn) { int found; int i; @@ -1221,25 +1023,21 @@ multiple_sets (insn) and there are no side effects. */ int -set_noop_p (set) - rtx set; +set_noop_p (rtx set) { rtx src = SET_SRC (set); rtx dst = SET_DEST (set); - if (side_effects_p (src) || side_effects_p (dst)) - return 0; - - if (GET_CODE (dst) == MEM && GET_CODE (src) == MEM) - return rtx_equal_p (dst, src); - if (dst == pc_rtx && src == pc_rtx) return 1; - if (GET_CODE (dst) == SIGN_EXTRACT - || GET_CODE (dst) == ZERO_EXTRACT) + if (MEM_P (dst) && MEM_P (src)) + return rtx_equal_p (dst, src) && !side_effects_p (dst); + + if (GET_CODE (dst) == ZERO_EXTRACT) return rtx_equal_p (XEXP (dst, 0), src) - && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx; + && ! BYTES_BIG_ENDIAN && XEXP (dst, 2) == const0_rtx + && !side_effects_p (src); if (GET_CODE (dst) == STRICT_LOW_PART) dst = XEXP (dst, 0); @@ -1252,7 +1050,7 @@ set_noop_p (set) dst = SUBREG_REG (dst); } - return (GET_CODE (src) == REG && GET_CODE (dst) == REG + return (REG_P (src) && REG_P (dst) && REGNO (src) == REGNO (dst)); } @@ -1260,8 +1058,7 @@ set_noop_p (set) value to itself. */ int -noop_move_p (insn) - rtx insn; +noop_move_p (rtx insn) { rtx pat = PATTERN (insn); @@ -1311,15 +1108,11 @@ noop_move_p (insn) be the src. */ rtx -find_last_value (x, pinsn, valid_to, allow_hwreg) - rtx x; - rtx *pinsn; - rtx valid_to; - int allow_hwreg; +find_last_value (rtx x, rtx *pinsn, rtx valid_to, int allow_hwreg) { rtx p; - for (p = PREV_INSN (*pinsn); p && GET_CODE (p) != CODE_LABEL; + for (p = PREV_INSN (*pinsn); p && !LABEL_P (p); p = PREV_INSN (p)) if (INSN_P (p)) { @@ -1337,7 +1130,7 @@ find_last_value (x, pinsn, valid_to, allow_hwreg) || ! modified_between_p (src, PREV_INSN (p), valid_to)) /* Reject hard registers because we don't usually want to use them; we'd rather use a pseudo. */ - && (! (GET_CODE (src) == REG + && (! (REG_P (src) && REGNO (src) < FIRST_PSEUDO_REGISTER) || allow_hwreg)) { *pinsn = p; @@ -1361,10 +1154,8 @@ find_last_value (x, pinsn, valid_to, allow_hwreg) LOC may be zero, meaning don't ignore anything. */ int -refers_to_regno_p (regno, endregno, x, loc) - unsigned int regno, endregno; - rtx x; - rtx *loc; +refers_to_regno_p (unsigned int regno, unsigned int endregno, rtx x, + rtx *loc) { int i; unsigned int x_regno; @@ -1397,19 +1188,19 @@ refers_to_regno_p (regno, endregno, x, loc) return (endregno > x_regno && regno < x_regno + (x_regno < FIRST_PSEUDO_REGISTER - ? HARD_REGNO_NREGS (x_regno, GET_MODE (x)) + ? hard_regno_nregs[x_regno][GET_MODE (x)] : 1)); case SUBREG: /* If this is a SUBREG of a hard reg, we can see exactly which registers are being modified. Otherwise, handle normally. */ - if (GET_CODE (SUBREG_REG (x)) == REG + if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < FIRST_PSEUDO_REGISTER) { unsigned int inner_regno = subreg_regno (x); unsigned int inner_endregno = inner_regno + (inner_regno < FIRST_PSEUDO_REGISTER - ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1); + ? hard_regno_nregs[inner_regno][GET_MODE (x)] : 1); return endregno > inner_regno && regno < inner_endregno; } @@ -1423,11 +1214,11 @@ refers_to_regno_p (regno, endregno, x, loc) treat each word individually. */ && ((GET_CODE (SET_DEST (x)) == SUBREG && loc != &SUBREG_REG (SET_DEST (x)) - && GET_CODE (SUBREG_REG (SET_DEST (x))) == REG + && REG_P (SUBREG_REG (SET_DEST (x))) && REGNO (SUBREG_REG (SET_DEST (x))) >= FIRST_PSEUDO_REGISTER && refers_to_regno_p (regno, endregno, SUBREG_REG (SET_DEST (x)), loc)) - || (GET_CODE (SET_DEST (x)) != REG + || (!REG_P (SET_DEST (x)) && refers_to_regno_p (regno, endregno, SET_DEST (x), loc)))) return 1; @@ -1459,7 +1250,7 @@ refers_to_regno_p (regno, endregno, x, loc) else if (fmt[i] == 'E') { int j; - for (j = XVECLEN (x, i) - 1; j >=0; j--) + for (j = XVECLEN (x, i) - 1; j >= 0; j--) if (loc != &XVECEXP (x, i, j) && refers_to_regno_p (regno, endregno, XVECEXP (x, i, j), loc)) return 1; @@ -1475,21 +1266,26 @@ refers_to_regno_p (regno, endregno, x, loc) conflict because we expect this to be a rare case. */ int -reg_overlap_mentioned_p (x, in) - rtx x, in; +reg_overlap_mentioned_p (rtx x, rtx in) { unsigned int regno, endregno; - /* Overly conservative. */ - if (GET_CODE (x) == STRICT_LOW_PART) - x = XEXP (x, 0); - - /* If either argument is a constant, then modifying X can not affect IN. */ - if (CONSTANT_P (x) || CONSTANT_P (in)) + /* If either argument is a constant, then modifying X can not + affect IN. Here we look at IN, we can profitably combine + CONSTANT_P (x) with the switch statement below. */ + if (CONSTANT_P (in)) return 0; + recurse: switch (GET_CODE (x)) { + case STRICT_LOW_PART: + case ZERO_EXTRACT: + case SIGN_EXTRACT: + /* Overly conservative. */ + x = XEXP (x, 0); + goto recurse; + case SUBREG: regno = REGNO (SUBREG_REG (x)); if (regno < FIRST_PSEUDO_REGISTER) @@ -1500,7 +1296,7 @@ reg_overlap_mentioned_p (x, in) regno = REGNO (x); do_reg: endregno = regno + (regno < FIRST_PSEUDO_REGISTER - ? HARD_REGNO_NREGS (regno, GET_MODE (x)) : 1); + ? hard_regno_nregs[regno][GET_MODE (x)] : 1); return refers_to_regno_p (regno, endregno, in, (rtx*) 0); case MEM: @@ -1508,7 +1304,7 @@ reg_overlap_mentioned_p (x, in) const char *fmt; int i; - if (GET_CODE (in) == MEM) + if (MEM_P (in)) return 1; fmt = GET_RTX_FORMAT (GET_CODE (in)); @@ -1532,65 +1328,14 @@ reg_overlap_mentioned_p (x, in) for (i = XVECLEN (x, 0) - 1; i >= 0; i--) if (XEXP (XVECEXP (x, 0, i), 0) != 0 && reg_overlap_mentioned_p (XEXP (XVECEXP (x, 0, i), 0), in)) - return 1; + return 1; return 0; } default: - break; + gcc_assert (CONSTANT_P (x)); + return 0; } - - abort (); -} - -/* Return the last value to which REG was set prior to INSN. If we can't - find it easily, return 0. - - We only return a REG, SUBREG, or constant because it is too hard to - check if a MEM remains unchanged. */ - -rtx -reg_set_last (x, insn) - rtx x; - rtx insn; -{ - rtx orig_insn = insn; - - /* Scan backwards until reg_set_last_1 changed one of the above flags. - Stop when we reach a label or X is a hard reg and we reach a - CALL_INSN (if reg_set_last_last_regno is a hard reg). - - If we find a set of X, ensure that its SET_SRC remains unchanged. */ - - /* We compare with <= here, because reg_set_last_last_regno - is actually the number of the first reg *not* in X. */ - for (; - insn && GET_CODE (insn) != CODE_LABEL - && ! (GET_CODE (insn) == CALL_INSN - && REGNO (x) <= FIRST_PSEUDO_REGISTER); - insn = PREV_INSN (insn)) - if (INSN_P (insn)) - { - rtx set = set_of (x, insn); - /* OK, this function modify our register. See if we understand it. */ - if (set) - { - rtx last_value; - if (GET_CODE (set) != SET || SET_DEST (set) != x) - return 0; - last_value = SET_SRC (x); - if (CONSTANT_P (last_value) - || ((GET_CODE (last_value) == REG - || GET_CODE (last_value) == SUBREG) - && ! reg_set_between_p (last_value, - insn, orig_insn))) - return last_value; - else - return 0; - } - } - - return 0; } /* Call FUN on each register or MEM that is stored into or clobbered by X. @@ -1603,10 +1348,7 @@ reg_set_last (x, insn) the SUBREG will be passed. */ void -note_stores (x, fun, data) - rtx x; - void (*fun) PARAMS ((rtx, rtx, void *)); - void *data; +note_stores (rtx x, void (*fun) (rtx, rtx, void *), void *data) { int i; @@ -1618,10 +1360,9 @@ note_stores (x, fun, data) rtx dest = SET_DEST (x); while ((GET_CODE (dest) == SUBREG - && (GET_CODE (SUBREG_REG (dest)) != REG + && (!REG_P (SUBREG_REG (dest)) || REGNO (SUBREG_REG (dest)) >= FIRST_PSEUDO_REGISTER)) || GET_CODE (dest) == ZERO_EXTRACT - || GET_CODE (dest) == SIGN_EXTRACT || GET_CODE (dest) == STRICT_LOW_PART) dest = XEXP (dest, 0); @@ -1652,10 +1393,7 @@ note_stores (x, fun, data) partially set, while we do not. */ void -note_uses (pbody, fun, data) - rtx *pbody; - void (*fun) PARAMS ((rtx *, void *)); - void *data; +note_uses (rtx *pbody, void (*fun) (rtx *, void *), void *data) { rtx body = *pbody; int i; @@ -1696,7 +1434,7 @@ note_uses (pbody, fun, data) return; case CLOBBER: - if (GET_CODE (XEXP (body, 0)) == MEM) + if (MEM_P (XEXP (body, 0))) (*fun) (&XEXP (XEXP (body, 0), 0), data); return; @@ -1717,7 +1455,7 @@ note_uses (pbody, fun, data) while (GET_CODE (dest) == SUBREG || GET_CODE (dest) == STRICT_LOW_PART) dest = XEXP (dest, 0); - if (GET_CODE (dest) == MEM) + if (MEM_P (dest)) (*fun) (&XEXP (dest, 0), data); } return; @@ -1733,8 +1471,8 @@ note_uses (pbody, fun, data) This will be true if X is (cc0) or if X is a register and X dies in INSN or because INSN entirely sets X. - "Entirely set" means set directly and not through a SUBREG, - ZERO_EXTRACT or SIGN_EXTRACT, so no trace of the old contents remains. + "Entirely set" means set directly and not through a SUBREG, or + ZERO_EXTRACT, so no trace of the old contents remains. Likewise, REG_INC does not count. REG may be a hard or pseudo reg. Renumbering is not taken into account, @@ -1747,9 +1485,7 @@ note_uses (pbody, fun, data) by INSN. */ int -dead_or_set_p (insn, x) - rtx insn; - rtx x; +dead_or_set_p (rtx insn, rtx x) { unsigned int regno, last_regno; unsigned int i; @@ -1758,12 +1494,11 @@ dead_or_set_p (insn, x) if (GET_CODE (x) == CC0) return 1; - if (GET_CODE (x) != REG) - abort (); + gcc_assert (REG_P (x)); regno = REGNO (x); last_regno = (regno >= FIRST_PSEUDO_REGISTER ? regno - : regno + HARD_REGNO_NREGS (regno, GET_MODE (x)) - 1); + : regno + hard_regno_nregs[regno][GET_MODE (x)] - 1); for (i = regno; i <= last_regno; i++) if (! dead_or_set_regno_p (insn, i)) @@ -1772,53 +1507,81 @@ dead_or_set_p (insn, x) return 1; } -/* Utility function for dead_or_set_p to check an individual register. Also - called from flow.c. */ +/* Return TRUE iff DEST is a register or subreg of a register and + doesn't change the number of words of the inner register, and any + part of the register is TEST_REGNO. */ -int -dead_or_set_regno_p (insn, test_regno) - rtx insn; - unsigned int test_regno; +static bool +covers_regno_no_parallel_p (rtx dest, unsigned int test_regno) { unsigned int regno, endregno; - rtx pattern; - /* See if there is a death note for something that includes TEST_REGNO. */ - if (find_regno_note (insn, REG_DEAD, test_regno)) - return 1; + if (GET_CODE (dest) == SUBREG + && (((GET_MODE_SIZE (GET_MODE (dest)) + + UNITS_PER_WORD - 1) / UNITS_PER_WORD) + == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) + + UNITS_PER_WORD - 1) / UNITS_PER_WORD))) + dest = SUBREG_REG (dest); - if (GET_CODE (insn) == CALL_INSN - && find_regno_fusage (insn, CLOBBER, test_regno)) - return 1; + if (!REG_P (dest)) + return false; - pattern = PATTERN (insn); + regno = REGNO (dest); + endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1 + : regno + hard_regno_nregs[regno][GET_MODE (dest)]); + return (test_regno >= regno && test_regno < endregno); +} - if (GET_CODE (pattern) == COND_EXEC) - pattern = COND_EXEC_CODE (pattern); +/* Like covers_regno_no_parallel_p, but also handles PARALLELs where + any member matches the covers_regno_no_parallel_p criteria. */ - if (GET_CODE (pattern) == SET) +static bool +covers_regno_p (rtx dest, unsigned int test_regno) +{ + if (GET_CODE (dest) == PARALLEL) { - rtx dest = SET_DEST (PATTERN (insn)); + /* Some targets place small structures in registers for return + values of functions, and those registers are wrapped in + PARALLELs that we may see as the destination of a SET. */ + int i; - /* A value is totally replaced if it is the destination or the - destination is a SUBREG of REGNO that does not change the number of - words in it. */ - if (GET_CODE (dest) == SUBREG - && (((GET_MODE_SIZE (GET_MODE (dest)) - + UNITS_PER_WORD - 1) / UNITS_PER_WORD) - == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - + UNITS_PER_WORD - 1) / UNITS_PER_WORD))) - dest = SUBREG_REG (dest); + for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) + { + rtx inner = XEXP (XVECEXP (dest, 0, i), 0); + if (inner != NULL_RTX + && covers_regno_no_parallel_p (inner, test_regno)) + return true; + } - if (GET_CODE (dest) != REG) - return 0; + return false; + } + else + return covers_regno_no_parallel_p (dest, test_regno); +} - regno = REGNO (dest); - endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1 - : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest))); +/* Utility function for dead_or_set_p to check an individual register. Also + called from flow.c. */ - return (test_regno >= regno && test_regno < endregno); - } +int +dead_or_set_regno_p (rtx insn, unsigned int test_regno) +{ + rtx pattern; + + /* See if there is a death note for something that includes TEST_REGNO. */ + if (find_regno_note (insn, REG_DEAD, test_regno)) + return 1; + + if (CALL_P (insn) + && find_regno_fusage (insn, CLOBBER, test_regno)) + return 1; + + pattern = PATTERN (insn); + + if (GET_CODE (pattern) == COND_EXEC) + pattern = COND_EXEC_CODE (pattern); + + if (GET_CODE (pattern) == SET) + return covers_regno_p (SET_DEST (pattern), test_regno); else if (GET_CODE (pattern) == PARALLEL) { int i; @@ -1830,27 +1593,9 @@ dead_or_set_regno_p (insn, test_regno) if (GET_CODE (body) == COND_EXEC) body = COND_EXEC_CODE (body); - if (GET_CODE (body) == SET || GET_CODE (body) == CLOBBER) - { - rtx dest = SET_DEST (body); - - if (GET_CODE (dest) == SUBREG - && (((GET_MODE_SIZE (GET_MODE (dest)) - + UNITS_PER_WORD - 1) / UNITS_PER_WORD) - == ((GET_MODE_SIZE (GET_MODE (SUBREG_REG (dest))) - + UNITS_PER_WORD - 1) / UNITS_PER_WORD))) - dest = SUBREG_REG (dest); - - if (GET_CODE (dest) != REG) - continue; - - regno = REGNO (dest); - endregno = (regno >= FIRST_PSEUDO_REGISTER ? regno + 1 - : regno + HARD_REGNO_NREGS (regno, GET_MODE (dest))); - - if (test_regno >= regno && test_regno < endregno) - return 1; - } + if ((GET_CODE (body) == SET || GET_CODE (body) == CLOBBER) + && covers_regno_p (SET_DEST (body), test_regno)) + return 1; } } @@ -1861,20 +1606,23 @@ dead_or_set_regno_p (insn, test_regno) If DATUM is nonzero, look for one whose datum is DATUM. */ rtx -find_reg_note (insn, kind, datum) - rtx insn; - enum reg_note kind; - rtx datum; +find_reg_note (rtx insn, enum reg_note kind, rtx datum) { rtx link; /* Ignore anything that is not an INSN, JUMP_INSN or CALL_INSN. */ if (! INSN_P (insn)) return 0; + if (datum == 0) + { + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == kind) + return link; + return 0; + } for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) - if (REG_NOTE_KIND (link) == kind - && (datum == 0 || datum == XEXP (link, 0))) + if (REG_NOTE_KIND (link) == kind && datum == XEXP (link, 0)) return link; return 0; } @@ -1885,10 +1633,7 @@ find_reg_note (insn, kind, datum) it might be the case that the note overlaps REGNO. */ rtx -find_regno_note (insn, kind, regno) - rtx insn; - enum reg_note kind; - unsigned int regno; +find_regno_note (rtx insn, enum reg_note kind, unsigned int regno) { rtx link; @@ -1900,12 +1645,12 @@ find_regno_note (insn, kind, regno) if (REG_NOTE_KIND (link) == kind /* Verify that it is a register, so that scratch and MEM won't cause a problem here. */ - && GET_CODE (XEXP (link, 0)) == REG + && REG_P (XEXP (link, 0)) && REGNO (XEXP (link, 0)) <= regno && ((REGNO (XEXP (link, 0)) + (REGNO (XEXP (link, 0)) >= FIRST_PSEUDO_REGISTER ? 1 - : HARD_REGNO_NREGS (REGNO (XEXP (link, 0)), - GET_MODE (XEXP (link, 0))))) + : hard_regno_nregs[REGNO (XEXP (link, 0))] + [GET_MODE (XEXP (link, 0))])) > regno)) return link; return 0; @@ -1915,37 +1660,37 @@ find_regno_note (insn, kind, regno) has such a note. */ rtx -find_reg_equal_equiv_note (insn) - rtx insn; +find_reg_equal_equiv_note (rtx insn) { - rtx note; + rtx link; - if (single_set (insn) == 0) + if (!INSN_P (insn)) return 0; - else if ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX)) != 0) - return note; - else - return find_reg_note (insn, REG_EQUAL, NULL_RTX); + for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) + if (REG_NOTE_KIND (link) == REG_EQUAL + || REG_NOTE_KIND (link) == REG_EQUIV) + { + if (single_set (insn) == 0) + return 0; + return link; + } + return NULL; } /* Return true if DATUM, or any overlap of DATUM, of kind CODE is found in the CALL_INSN_FUNCTION_USAGE information of INSN. */ int -find_reg_fusage (insn, code, datum) - rtx insn; - enum rtx_code code; - rtx datum; +find_reg_fusage (rtx insn, enum rtx_code code, rtx datum) { /* If it's not a CALL_INSN, it can't possibly have a CALL_INSN_FUNCTION_USAGE field, so don't bother checking. */ - if (GET_CODE (insn) != CALL_INSN) + if (!CALL_P (insn)) return 0; - if (! datum) - abort (); + gcc_assert (datum); - if (GET_CODE (datum) != REG) + if (!REG_P (datum)) { rtx link; @@ -1966,7 +1711,7 @@ find_reg_fusage (insn, code, datum) if (regno < FIRST_PSEUDO_REGISTER) { unsigned int end_regno - = regno + HARD_REGNO_NREGS (regno, GET_MODE (datum)); + = regno + hard_regno_nregs[regno][GET_MODE (datum)]; unsigned int i; for (i = regno; i < end_regno; i++) @@ -1982,10 +1727,7 @@ find_reg_fusage (insn, code, datum) in the CALL_INSN_FUNCTION_USAGE information of INSN. */ int -find_regno_fusage (insn, code, regno) - rtx insn; - enum rtx_code code; - unsigned int regno; +find_regno_fusage (rtx insn, enum rtx_code code, unsigned int regno) { rtx link; @@ -1993,7 +1735,7 @@ find_regno_fusage (insn, code, regno) to pseudo registers, so don't bother checking. */ if (regno >= FIRST_PSEUDO_REGISTER - || GET_CODE (insn) != CALL_INSN ) + || !CALL_P (insn) ) return 0; for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) @@ -2002,9 +1744,9 @@ find_regno_fusage (insn, code, regno) rtx op, reg; if (GET_CODE (op = XEXP (link, 0)) == code - && GET_CODE (reg = XEXP (op, 0)) == REG + && REG_P (reg = XEXP (op, 0)) && (regnote = REGNO (reg)) <= regno - && regnote + HARD_REGNO_NREGS (regnote, GET_MODE (reg)) > regno) + && regnote + hard_regno_nregs[regnote][GET_MODE (reg)] > regno) return 1; } @@ -2014,12 +1756,11 @@ find_regno_fusage (insn, code, regno) /* Return true if INSN is a call to a pure function. */ int -pure_call_p (insn) - rtx insn; +pure_call_p (rtx insn) { rtx link; - if (GET_CODE (insn) != CALL_INSN || ! CONST_OR_PURE_CALL_P (insn)) + if (!CALL_P (insn) || ! CONST_OR_PURE_CALL_P (insn)) return 0; /* Look for the note that differentiates const and pure functions. */ @@ -2028,7 +1769,7 @@ pure_call_p (insn) rtx u, m; if (GET_CODE (u = XEXP (link, 0)) == USE - && GET_CODE (m = XEXP (u, 0)) == MEM && GET_MODE (m) == BLKmode + && MEM_P (m = XEXP (u, 0)) && GET_MODE (m) == BLKmode && GET_CODE (XEXP (m, 0)) == SCRATCH) return 1; } @@ -2039,9 +1780,7 @@ pure_call_p (insn) /* Remove register note NOTE from the REG_NOTES of INSN. */ void -remove_note (insn, note) - rtx insn; - rtx note; +remove_note (rtx insn, rtx note) { rtx link; @@ -2061,7 +1800,7 @@ remove_note (insn, note) return; } - abort (); + gcc_unreachable (); } /* Search LISTP (an EXPR_LIST) for an entry whose first operand is NODE and @@ -2069,9 +1808,7 @@ remove_note (insn, note) NODE matches. */ int -in_expr_list_p (listp, node) - rtx listp; - rtx node; +in_expr_list_p (rtx listp, rtx node) { rtx x; @@ -2088,9 +1825,7 @@ in_expr_list_p (listp, node) A simple equality test is used to determine if NODE matches. */ void -remove_node_from_expr_list (node, listp) - rtx node; - rtx *listp; +remove_node_from_expr_list (rtx node, rtx *listp) { rtx temp = *listp; rtx prev = NULL_RTX; @@ -2119,8 +1854,7 @@ remove_node_from_expr_list (node, listp) only volatile asms and UNSPEC_VOLATILE instructions. */ int -volatile_insn_p (x) - rtx x; +volatile_insn_p (rtx x) { RTX_CODE code; @@ -2138,7 +1872,6 @@ volatile_insn_p (x) case REG: case SCRATCH: case CLOBBER: - case ASM_INPUT: case ADDR_VEC: case ADDR_DIFF_VEC: case CALL: @@ -2149,6 +1882,7 @@ volatile_insn_p (x) /* case TRAP_IF: This isn't clear yet. */ return 1; + case ASM_INPUT: case ASM_OPERANDS: if (MEM_VOLATILE_P (x)) return 1; @@ -2186,8 +1920,7 @@ volatile_insn_p (x) UNSPEC_VOLATILE operations or volatile ASM_OPERANDS expressions. */ int -volatile_refs_p (x) - rtx x; +volatile_refs_p (rtx x) { RTX_CODE code; @@ -2205,7 +1938,6 @@ volatile_refs_p (x) case REG: case SCRATCH: case CLOBBER: - case ASM_INPUT: case ADDR_VEC: case ADDR_DIFF_VEC: return 0; @@ -2214,6 +1946,7 @@ volatile_refs_p (x) return 1; case MEM: + case ASM_INPUT: case ASM_OPERANDS: if (MEM_VOLATILE_P (x)) return 1; @@ -2251,8 +1984,7 @@ volatile_refs_p (x) incrementing. */ int -side_effects_p (x) - rtx x; +side_effects_p (rtx x) { RTX_CODE code; @@ -2269,7 +2001,6 @@ side_effects_p (x) case PC: case REG: case SCRATCH: - case ASM_INPUT: case ADDR_VEC: case ADDR_DIFF_VEC: return 0; @@ -2292,6 +2023,7 @@ side_effects_p (x) return 1; case MEM: + case ASM_INPUT: case ASM_OPERANDS: if (MEM_VOLATILE_P (x)) return 1; @@ -2328,8 +2060,7 @@ side_effects_p (x) /* Return nonzero if evaluating rtx X might cause a trap. */ int -may_trap_p (x) - rtx x; +may_trap_p (rtx x) { int i; enum rtx_code code; @@ -2363,6 +2094,8 @@ may_trap_p (x) /* Memory ref can trap unless it's a static var or a stack slot. */ case MEM: + if (MEM_NOTRAP_P (x)) + return 0; return rtx_addr_can_trap_p (XEXP (x, 0)); /* Division by a non-constant might trap. */ @@ -2372,13 +2105,9 @@ may_trap_p (x) case UMOD: if (HONOR_SNANS (GET_MODE (x))) return 1; - if (! CONSTANT_P (XEXP (x, 1)) - || (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT - && flag_trapping_math)) - return 1; - /* This was const0_rtx, but by not using that, - we can link this file into other programs. */ - if (GET_CODE (XEXP (x, 1)) == CONST_INT && INTVAL (XEXP (x, 1)) == 0) + if (GET_MODE_CLASS (GET_MODE (x)) == MODE_FLOAT) + return flag_trapping_math; + if (!CONSTANT_P (XEXP (x, 1)) || (XEXP (x, 1) == const0_rtx)) return 1; break; @@ -2391,6 +2120,7 @@ may_trap_p (x) case GT: case LE: case LT: + case LTGT: case COMPARE: /* Some floating point comparisons may trap. */ if (!flag_trapping_math) @@ -2418,6 +2148,12 @@ may_trap_p (x) return 1; break; + case FIX: + /* Conversion of floating point might trap. */ + if (flag_trapping_math && HONOR_NANS (GET_MODE (XEXP (x, 0)))) + return 1; + break; + case NEG: case ABS: /* These operations don't trap even with floating point. */ @@ -2453,8 +2189,7 @@ may_trap_p (x) i.e., an inequality. */ int -inequality_comparisons_p (x) - rtx x; +inequality_comparisons_p (rtx x) { const char *fmt; int len, i; @@ -2517,8 +2252,7 @@ inequality_comparisons_p (x) are to be modified. */ rtx -replace_rtx (x, from, to) - rtx x, from, to; +replace_rtx (rtx x, rtx from, rtx to) { int i, j; const char *fmt; @@ -2544,8 +2278,7 @@ replace_rtx (x, from, to) x = simplify_subreg (GET_MODE (x), new, GET_MODE (SUBREG_REG (x)), SUBREG_BYTE (x)); - if (! x) - abort (); + gcc_assert (x); } else SUBREG_REG (x) = new; @@ -2560,8 +2293,7 @@ replace_rtx (x, from, to) { x = simplify_unary_operation (ZERO_EXTEND, GET_MODE (x), new, GET_MODE (XEXP (x, 0))); - if (! x) - abort (); + gcc_assert (x); } else XEXP (x, 0) = new; @@ -2595,11 +2327,7 @@ replace_rtx (x, from, to) otherwise, only sources are replaced. */ rtx -replace_regs (x, reg_map, nregs, replace_dest) - rtx x; - rtx *reg_map; - unsigned int nregs; - int replace_dest; +replace_regs (rtx x, rtx *reg_map, unsigned int nregs, int replace_dest) { enum rtx_code code; int i; @@ -2637,7 +2365,7 @@ replace_regs (x, reg_map, nregs, replace_dest) case SUBREG: /* Prevent making nested SUBREGs. */ - if (GET_CODE (SUBREG_REG (x)) == REG && REGNO (SUBREG_REG (x)) < nregs + if (REG_P (SUBREG_REG (x)) && REGNO (SUBREG_REG (x)) < nregs && reg_map[REGNO (SUBREG_REG (x))] != 0 && GET_CODE (reg_map[REGNO (SUBREG_REG (x))]) == SUBREG) { @@ -2652,7 +2380,7 @@ replace_regs (x, reg_map, nregs, replace_dest) if (replace_dest) SET_DEST (x) = replace_regs (SET_DEST (x), reg_map, nregs, 0); - else if (GET_CODE (SET_DEST (x)) == MEM + else if (MEM_P (SET_DEST (x)) || GET_CODE (SET_DEST (x)) == STRICT_LOW_PART) /* Even if we are not to replace destinations, replace register if it is CONTAINED in destination (destination is memory or @@ -2686,13 +2414,130 @@ replace_regs (x, reg_map, nregs, replace_dest) return x; } +/* Replace occurrences of the old label in *X with the new one. + DATA is a REPLACE_LABEL_DATA containing the old and new labels. */ + +int +replace_label (rtx *x, void *data) +{ + rtx l = *x; + rtx old_label = ((replace_label_data *) data)->r1; + rtx new_label = ((replace_label_data *) data)->r2; + bool update_label_nuses = ((replace_label_data *) data)->update_label_nuses; + + if (l == NULL_RTX) + return 0; + + if (GET_CODE (l) == SYMBOL_REF + && CONSTANT_POOL_ADDRESS_P (l)) + { + rtx c = get_pool_constant (l); + if (rtx_referenced_p (old_label, c)) + { + rtx new_c, new_l; + replace_label_data *d = (replace_label_data *) data; + + /* Create a copy of constant C; replace the label inside + but do not update LABEL_NUSES because uses in constant pool + are not counted. */ + new_c = copy_rtx (c); + d->update_label_nuses = false; + for_each_rtx (&new_c, replace_label, data); + d->update_label_nuses = update_label_nuses; + + /* Add the new constant NEW_C to constant pool and replace + the old reference to constant by new reference. */ + new_l = XEXP (force_const_mem (get_pool_mode (l), new_c), 0); + *x = replace_rtx (l, l, new_l); + } + return 0; + } + + /* If this is a JUMP_INSN, then we also need to fix the JUMP_LABEL + field. This is not handled by for_each_rtx because it doesn't + handle unprinted ('0') fields. */ + if (JUMP_P (l) && JUMP_LABEL (l) == old_label) + JUMP_LABEL (l) = new_label; + + if ((GET_CODE (l) == LABEL_REF + || GET_CODE (l) == INSN_LIST) + && XEXP (l, 0) == old_label) + { + XEXP (l, 0) = new_label; + if (update_label_nuses) + { + ++LABEL_NUSES (new_label); + --LABEL_NUSES (old_label); + } + return 0; + } + + return 0; +} + +/* When *BODY is equal to X or X is directly referenced by *BODY + return nonzero, thus FOR_EACH_RTX stops traversing and returns nonzero + too, otherwise FOR_EACH_RTX continues traversing *BODY. */ + +static int +rtx_referenced_p_1 (rtx *body, void *x) +{ + rtx y = (rtx) x; + + if (*body == NULL_RTX) + return y == NULL_RTX; + + /* Return true if a label_ref *BODY refers to label Y. */ + if (GET_CODE (*body) == LABEL_REF && LABEL_P (y)) + return XEXP (*body, 0) == y; + + /* If *BODY is a reference to pool constant traverse the constant. */ + if (GET_CODE (*body) == SYMBOL_REF + && CONSTANT_POOL_ADDRESS_P (*body)) + return rtx_referenced_p (y, get_pool_constant (*body)); + + /* By default, compare the RTL expressions. */ + return rtx_equal_p (*body, y); +} + +/* Return true if X is referenced in BODY. */ + +int +rtx_referenced_p (rtx x, rtx body) +{ + return for_each_rtx (&body, rtx_referenced_p_1, x); +} + +/* If INSN is a tablejump return true and store the label (before jump table) to + *LABELP and the jump table to *TABLEP. LABELP and TABLEP may be NULL. */ + +bool +tablejump_p (rtx insn, rtx *labelp, rtx *tablep) +{ + rtx label, table; + + if (JUMP_P (insn) + && (label = JUMP_LABEL (insn)) != NULL_RTX + && (table = next_active_insn (label)) != NULL_RTX + && JUMP_P (table) + && (GET_CODE (PATTERN (table)) == ADDR_VEC + || GET_CODE (PATTERN (table)) == ADDR_DIFF_VEC)) + { + if (labelp) + *labelp = label; + if (tablep) + *tablep = table; + return true; + } + return false; +} + /* A subroutine of computed_jump_p, return 1 if X contains a REG or MEM or constant that is not in the constant pool and not in the condition of an IF_THEN_ELSE. */ static int -computed_jump_p_1 (x) - rtx x; +computed_jump_p_1 (rtx x) { enum rtx_code code = GET_CODE (x); int i, j; @@ -2746,11 +2591,10 @@ computed_jump_p_1 (x) we can recognize them by a (use (label_ref)). */ int -computed_jump_p (insn) - rtx insn; +computed_jump_p (rtx insn) { int i; - if (GET_CODE (insn) == JUMP_INSN) + if (JUMP_P (insn)) { rtx pat = PATTERN (insn); @@ -2782,11 +2626,87 @@ computed_jump_p (insn) return 0; } +/* Optimized loop of for_each_rtx, trying to avoid useless recursive + calls. Processes the subexpressions of EXP and passes them to F. */ +static int +for_each_rtx_1 (rtx exp, int n, rtx_function f, void *data) +{ + int result, i, j; + const char *format = GET_RTX_FORMAT (GET_CODE (exp)); + rtx *x; + + for (; format[n] != '\0'; n++) + { + switch (format[n]) + { + case 'e': + /* Call F on X. */ + x = &XEXP (exp, n); + result = (*f) (x, data); + if (result == -1) + /* Do not traverse sub-expressions. */ + continue; + else if (result != 0) + /* Stop the traversal. */ + return result; + + if (*x == NULL_RTX) + /* There are no sub-expressions. */ + continue; + + i = non_rtx_starting_operands[GET_CODE (*x)]; + if (i >= 0) + { + result = for_each_rtx_1 (*x, i, f, data); + if (result != 0) + return result; + } + break; + + case 'V': + case 'E': + if (XVEC (exp, n) == 0) + continue; + for (j = 0; j < XVECLEN (exp, n); ++j) + { + /* Call F on X. */ + x = &XVECEXP (exp, n, j); + result = (*f) (x, data); + if (result == -1) + /* Do not traverse sub-expressions. */ + continue; + else if (result != 0) + /* Stop the traversal. */ + return result; + + if (*x == NULL_RTX) + /* There are no sub-expressions. */ + continue; + + i = non_rtx_starting_operands[GET_CODE (*x)]; + if (i >= 0) + { + result = for_each_rtx_1 (*x, i, f, data); + if (result != 0) + return result; + } + } + break; + + default: + /* Nothing to do. */ + break; + } + } + + return 0; +} + /* Traverse X via depth-first search, calling F for each sub-expression (including X itself). F is also passed the DATA. If F returns -1, do not traverse sub-expressions, but continue traversing the rest of the tree. If F ever returns any other - non-zero value, stop the traversal, and return the value returned + nonzero value, stop the traversal, and return the value returned by F. Otherwise, return 0. This function does not traverse inside tree structure that contains RTX_EXPRs, or into sub-expressions whose format code is `0' since it is not known whether or not those @@ -2796,14 +2716,9 @@ computed_jump_p (insn) implement many of the other routines in this file. */ int -for_each_rtx (x, f, data) - rtx *x; - rtx_function f; - void *data; +for_each_rtx (rtx *x, rtx_function f, void *data) { int result; - int length; - const char *format; int i; /* Call F on X. */ @@ -2819,56 +2734,25 @@ for_each_rtx (x, f, data) /* There are no sub-expressions. */ return 0; - length = GET_RTX_LENGTH (GET_CODE (*x)); - format = GET_RTX_FORMAT (GET_CODE (*x)); - - for (i = 0; i < length; ++i) - { - switch (format[i]) - { - case 'e': - result = for_each_rtx (&XEXP (*x, i), f, data); - if (result != 0) - return result; - break; - - case 'V': - case 'E': - if (XVEC (*x, i) != 0) - { - int j; - for (j = 0; j < XVECLEN (*x, i); ++j) - { - result = for_each_rtx (&XVECEXP (*x, i, j), f, data); - if (result != 0) - return result; - } - } - break; - - default: - /* Nothing to do. */ - break; - } - - } + i = non_rtx_starting_operands[GET_CODE (*x)]; + if (i < 0) + return 0; - return 0; + return for_each_rtx_1 (*x, i, f, data); } + /* Searches X for any reference to REGNO, returning the rtx of the reference found if any. Otherwise, returns NULL_RTX. */ rtx -regno_use_in (regno, x) - unsigned int regno; - rtx x; +regno_use_in (unsigned int regno, rtx x) { const char *fmt; int i, j; rtx tem; - if (GET_CODE (x) == REG && REGNO (x) == regno) + if (REG_P (x) && REGNO (x) == regno) return x; fmt = GET_RTX_FORMAT (GET_CODE (x)); @@ -2895,43 +2779,70 @@ regno_use_in (regno, x) and positive values for the second operand. */ int -commutative_operand_precedence (op) - rtx op; +commutative_operand_precedence (rtx op) { + enum rtx_code code = GET_CODE (op); + /* Constants always come the second operand. Prefer "nice" constants. */ - if (GET_CODE (op) == CONST_INT) - return -5; - if (GET_CODE (op) == CONST_DOUBLE) - return -4; - if (CONSTANT_P (op)) - return -3; - - /* SUBREGs of objects should come second. */ - if (GET_CODE (op) == SUBREG - && GET_RTX_CLASS (GET_CODE (SUBREG_REG (op))) == 'o') - return -2; - - /* If only one operand is a `neg', `not', - `mult', `plus', or `minus' expression, it will be the first - operand. */ - if (GET_CODE (op) == NEG || GET_CODE (op) == NOT - || GET_CODE (op) == MULT || GET_CODE (op) == PLUS - || GET_CODE (op) == MINUS) - return 2; - - /* Complex expressions should be the first, so decrease priority - of objects. */ - if (GET_RTX_CLASS (GET_CODE (op)) == 'o') - return -1; - return 0; + if (code == CONST_INT) + return -7; + if (code == CONST_DOUBLE) + return -6; + op = avoid_constant_pool_reference (op); + code = GET_CODE (op); + + switch (GET_RTX_CLASS (code)) + { + case RTX_CONST_OBJ: + if (code == CONST_INT) + return -5; + if (code == CONST_DOUBLE) + return -4; + return -3; + + case RTX_EXTRA: + /* SUBREGs of objects should come second. */ + if (code == SUBREG && OBJECT_P (SUBREG_REG (op))) + return -2; + + if (!CONSTANT_P (op)) + return 0; + else + /* As for RTX_CONST_OBJ. */ + return -3; + + case RTX_OBJ: + /* Complex expressions should be the first, so decrease priority + of objects. */ + return -1; + + case RTX_COMM_ARITH: + /* Prefer operands that are themselves commutative to be first. + This helps to make things linear. In particular, + (and (and (reg) (reg)) (not (reg))) is canonical. */ + return 4; + + case RTX_BIN_ARITH: + /* If only one operand is a binary expression, it will be the first + operand. In particular, (plus (minus (reg) (reg)) (neg (reg))) + is canonical, although it will usually be further simplified. */ + return 2; + + case RTX_UNARY: + /* Then prefer NEG and NOT. */ + if (code == NEG || code == NOT) + return 1; + + default: + return 0; + } } /* Return 1 iff it is necessary to swap operands of commutative operation in order to canonicalize expression. */ int -swap_commutative_operands_p (x, y) - rtx x, y; +swap_commutative_operands_p (rtx x, rtx y) { return (commutative_operand_precedence (x) < commutative_operand_precedence (y)); @@ -2940,8 +2851,7 @@ swap_commutative_operands_p (x, y) /* Return 1 if X is an autoincrement side effect and the register is not the stack pointer. */ int -auto_inc_p (x) - rtx x; +auto_inc_p (rtx x) { switch (GET_CODE (x)) { @@ -2971,10 +2881,7 @@ auto_inc_p (x) conditions as well. */ int -insns_safe_to_move_p (from, to, new_to) - rtx from; - rtx to; - rtx *new_to; +insns_safe_to_move_p (rtx from, rtx to, rtx *new_to) { int eh_region_count = 0; int past_to_p = 0; @@ -2987,7 +2894,7 @@ insns_safe_to_move_p (from, to, new_to) while (r) { - if (GET_CODE (r) == NOTE) + if (NOTE_P (r)) { switch (NOTE_LINE_NUMBER (r)) { @@ -3039,10 +2946,9 @@ insns_safe_to_move_p (from, to, new_to) return 0; } -/* Return non-zero if IN contains a piece of rtl that has the address LOC */ +/* Return nonzero if IN contains a piece of rtl that has the address LOC. */ int -loc_mentioned_in_p (loc, in) - rtx *loc, in; +loc_mentioned_in_p (rtx *loc, rtx in) { enum rtx_code code = GET_CODE (in); const char *fmt = GET_RTX_FORMAT (code); @@ -3050,7 +2956,7 @@ loc_mentioned_in_p (loc, in) for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) { - if (loc == &in->fld[i].rtx) + if (loc == &in->u.fld[i].rt_rtx) return 1; if (fmt[i] == 'e') { @@ -3065,49 +2971,58 @@ loc_mentioned_in_p (loc, in) return 0; } -/* Given a subreg X, return the bit offset where the subreg begins - (counting from the least significant bit of the reg). */ +/* Helper function for subreg_lsb. Given a subreg's OUTER_MODE, INNER_MODE, + and SUBREG_BYTE, return the bit offset where the subreg begins + (counting from the least significant bit of the operand). */ unsigned int -subreg_lsb (x) - rtx x; +subreg_lsb_1 (enum machine_mode outer_mode, + enum machine_mode inner_mode, + unsigned int subreg_byte) { - enum machine_mode inner_mode = GET_MODE (SUBREG_REG (x)); - enum machine_mode mode = GET_MODE (x); unsigned int bitpos; unsigned int byte; unsigned int word; /* A paradoxical subreg begins at bit position 0. */ - if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (inner_mode)) + if (GET_MODE_BITSIZE (outer_mode) > GET_MODE_BITSIZE (inner_mode)) return 0; if (WORDS_BIG_ENDIAN != BYTES_BIG_ENDIAN) /* If the subreg crosses a word boundary ensure that it also begins and ends on a word boundary. */ - if ((SUBREG_BYTE (x) % UNITS_PER_WORD - + GET_MODE_SIZE (mode)) > UNITS_PER_WORD - && (SUBREG_BYTE (x) % UNITS_PER_WORD - || GET_MODE_SIZE (mode) % UNITS_PER_WORD)) - abort (); + gcc_assert (!((subreg_byte % UNITS_PER_WORD + + GET_MODE_SIZE (outer_mode)) > UNITS_PER_WORD + && (subreg_byte % UNITS_PER_WORD + || GET_MODE_SIZE (outer_mode) % UNITS_PER_WORD))); if (WORDS_BIG_ENDIAN) word = (GET_MODE_SIZE (inner_mode) - - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) / UNITS_PER_WORD; + - (subreg_byte + GET_MODE_SIZE (outer_mode))) / UNITS_PER_WORD; else - word = SUBREG_BYTE (x) / UNITS_PER_WORD; + word = subreg_byte / UNITS_PER_WORD; bitpos = word * BITS_PER_WORD; if (BYTES_BIG_ENDIAN) byte = (GET_MODE_SIZE (inner_mode) - - (SUBREG_BYTE (x) + GET_MODE_SIZE (mode))) % UNITS_PER_WORD; + - (subreg_byte + GET_MODE_SIZE (outer_mode))) % UNITS_PER_WORD; else - byte = SUBREG_BYTE (x) % UNITS_PER_WORD; + byte = subreg_byte % UNITS_PER_WORD; bitpos += byte * BITS_PER_UNIT; return bitpos; } +/* Given a subreg X, return the bit offset where the subreg begins + (counting from the least significant bit of the reg). */ + +unsigned int +subreg_lsb (rtx x) +{ + return subreg_lsb_1 (GET_MODE (x), GET_MODE (SUBREG_REG (x)), + SUBREG_BYTE (x)); +} + /* This function returns the regno offset of a subreg expression. xregno - A regno of an inner hard subreg_reg (or what will become one). xmode - The mode of xregno. @@ -3115,21 +3030,17 @@ subreg_lsb (x) ymode - The mode of a top level SUBREG (or what may become one). RETURN - The regno offset which would be used. */ unsigned int -subreg_regno_offset (xregno, xmode, offset, ymode) - unsigned int xregno; - enum machine_mode xmode; - unsigned int offset; - enum machine_mode ymode; +subreg_regno_offset (unsigned int xregno, enum machine_mode xmode, + unsigned int offset, enum machine_mode ymode) { int nregs_xmode, nregs_ymode; int mode_multiple, nregs_multiple; int y_offset; - if (xregno >= FIRST_PSEUDO_REGISTER) - abort (); + gcc_assert (xregno < FIRST_PSEUDO_REGISTER); - nregs_xmode = HARD_REGNO_NREGS (xregno, xmode); - nregs_ymode = HARD_REGNO_NREGS (xregno, ymode); + nregs_xmode = hard_regno_nregs[xregno][xmode]; + nregs_ymode = hard_regno_nregs[xregno][ymode]; /* If this is a big endian paradoxical subreg, which uses more actual hard registers than the original register, we must return a negative @@ -3145,18 +3056,75 @@ subreg_regno_offset (xregno, xmode, offset, ymode) /* size of ymode must not be greater than the size of xmode. */ mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode); - if (mode_multiple == 0) - abort (); + gcc_assert (mode_multiple != 0); y_offset = offset / GET_MODE_SIZE (ymode); nregs_multiple = nregs_xmode / nregs_ymode; return (y_offset / (mode_multiple / nregs_multiple)) * nregs_ymode; } +/* This function returns true when the offset is representable via + subreg_offset in the given regno. + xregno - A regno of an inner hard subreg_reg (or what will become one). + xmode - The mode of xregno. + offset - The byte offset. + ymode - The mode of a top level SUBREG (or what may become one). + RETURN - The regno offset which would be used. */ +bool +subreg_offset_representable_p (unsigned int xregno, enum machine_mode xmode, + unsigned int offset, enum machine_mode ymode) +{ + int nregs_xmode, nregs_ymode; + int mode_multiple, nregs_multiple; + int y_offset; + + gcc_assert (xregno < FIRST_PSEUDO_REGISTER); + + nregs_xmode = hard_regno_nregs[xregno][xmode]; + nregs_ymode = hard_regno_nregs[xregno][ymode]; + + /* Paradoxical subregs are always valid. */ + if (offset == 0 + && nregs_ymode > nregs_xmode + && (GET_MODE_SIZE (ymode) > UNITS_PER_WORD + ? WORDS_BIG_ENDIAN : BYTES_BIG_ENDIAN)) + return true; + + /* Lowpart subregs are always valid. */ + if (offset == subreg_lowpart_offset (ymode, xmode)) + return true; + + /* This should always pass, otherwise we don't know how to verify the + constraint. These conditions may be relaxed but subreg_offset would + need to be redesigned. */ + gcc_assert ((GET_MODE_SIZE (xmode) % GET_MODE_SIZE (ymode)) == 0); + gcc_assert ((GET_MODE_SIZE (ymode) % nregs_ymode) == 0); + gcc_assert ((nregs_xmode % nregs_ymode) == 0); + + /* The XMODE value can be seen as a vector of NREGS_XMODE + values. The subreg must represent a lowpart of given field. + Compute what field it is. */ + offset -= subreg_lowpart_offset (ymode, + mode_for_size (GET_MODE_BITSIZE (xmode) + / nregs_xmode, + MODE_INT, 0)); + + /* size of ymode must not be greater than the size of xmode. */ + mode_multiple = GET_MODE_SIZE (xmode) / GET_MODE_SIZE (ymode); + gcc_assert (mode_multiple != 0); + + y_offset = offset / GET_MODE_SIZE (ymode); + nregs_multiple = nregs_xmode / nregs_ymode; + + gcc_assert ((offset % GET_MODE_SIZE (ymode)) == 0); + gcc_assert ((mode_multiple % nregs_multiple) == 0); + + return (!(y_offset % (mode_multiple / nregs_multiple))); +} + /* Return the final regno that a subreg expression refers to. */ unsigned int -subreg_regno (x) - rtx x; +subreg_regno (rtx x) { unsigned int ret; rtx subreg = SUBREG_REG (x); @@ -3177,9 +3145,7 @@ struct parms_set_data /* Helper function for noticing stores to parameter registers. */ static void -parms_set (x, pat, data) - rtx x, pat ATTRIBUTE_UNUSED; - void *data; +parms_set (rtx x, rtx pat ATTRIBUTE_UNUSED, void *data) { struct parms_set_data *d = data; if (REG_P (x) && REGNO (x) < FIRST_PSEUDO_REGISTER @@ -3191,13 +3157,15 @@ parms_set (x, pat, data) } /* Look backward for first parameter to be loaded. + Note that loads of all parameters will not necessarily be + found if CSE has eliminated some of them (e.g., an argument + to the outer function is passed down as a parameter). Do not skip BOUNDARY. */ rtx -find_first_parameter_load (call_insn, boundary) - rtx call_insn, boundary; +find_first_parameter_load (rtx call_insn, rtx boundary) { struct parms_set_data parm; - rtx p, before; + rtx p, before, first_set; /* Since different machines initialize their parameter registers in different orders, assume nothing. Collect the set of all @@ -3206,10 +3174,9 @@ find_first_parameter_load (call_insn, boundary) parm.nregs = 0; for (p = CALL_INSN_FUNCTION_USAGE (call_insn); p; p = XEXP (p, 1)) if (GET_CODE (XEXP (p, 0)) == USE - && GET_CODE (XEXP (XEXP (p, 0), 0)) == REG) + && REG_P (XEXP (XEXP (p, 0), 0))) { - if (REGNO (XEXP (XEXP (p, 0), 0)) >= FIRST_PSEUDO_REGISTER) - abort (); + gcc_assert (REGNO (XEXP (XEXP (p, 0), 0)) < FIRST_PSEUDO_REGISTER); /* We only care about registers which can hold function arguments. */ @@ -3220,6 +3187,7 @@ find_first_parameter_load (call_insn, boundary) parm.nregs++; } before = call_insn; + first_set = call_insn; /* Search backward for the first set of a register in this set. */ while (parm.nregs && before != boundary) @@ -3228,45 +3196,54 @@ find_first_parameter_load (call_insn, boundary) /* It is possible that some loads got CSEed from one call to another. Stop in that case. */ - if (GET_CODE (before) == CALL_INSN) + if (CALL_P (before)) break; /* Our caller needs either ensure that we will find all sets (in case code has not been optimized yet), or take care for possible labels in a way by setting boundary to preceding CODE_LABEL. */ - if (GET_CODE (before) == CODE_LABEL) + if (LABEL_P (before)) { - if (before != boundary) - abort (); + gcc_assert (before == boundary); break; } if (INSN_P (before)) - note_stores (PATTERN (before), parms_set, &parm); + { + int nregs_old = parm.nregs; + note_stores (PATTERN (before), parms_set, &parm); + /* If we found something that did not set a parameter reg, + we're done. Do not keep going, as that might result + in hoisting an insn before the setting of a pseudo + that is used by the hoisted insn. */ + if (nregs_old != parm.nregs) + first_set = before; + else + break; + } } - return before; + return first_set; } -/* Return true if we should avoid inserting code between INSN and preceeding +/* Return true if we should avoid inserting code between INSN and preceding call instruction. */ bool -keep_with_call_p (insn) - rtx insn; +keep_with_call_p (rtx insn) { rtx set; if (INSN_P (insn) && (set = single_set (insn)) != NULL) { - if (GET_CODE (SET_DEST (set)) == REG + if (REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) < FIRST_PSEUDO_REGISTER && fixed_regs[REGNO (SET_DEST (set))] && general_operand (SET_SRC (set), VOIDmode)) return true; - if (GET_CODE (SET_SRC (set)) == REG + if (REG_P (SET_SRC (set)) && FUNCTION_VALUE_REGNO_P (REGNO (SET_SRC (set))) - && GET_CODE (SET_DEST (set)) == REG + && REG_P (SET_DEST (set)) && REGNO (SET_DEST (set)) >= FIRST_PSEUDO_REGISTER) return true; /* There may be a stack pop just after the call and before the store @@ -3282,265 +3259,1432 @@ keep_with_call_p (insn) return false; } -/* Return true when store to register X can be hoisted to the place - with LIVE registers (can be NULL). Value VAL contains destination - whose value will be used. */ +/* Return true if LABEL is a target of JUMP_INSN. This applies only + to non-complex jumps. That is, direct unconditional, conditional, + and tablejumps, but not computed jumps or returns. It also does + not apply to the fallthru case of a conditional jump. */ -static bool -hoist_test_store (x, val, live) - rtx x, val; - regset live; +bool +label_is_jump_target_p (rtx label, rtx jump_insn) { - if (GET_CODE (x) == SCRATCH) - return true; + rtx tmp = JUMP_LABEL (jump_insn); - if (rtx_equal_p (x, val)) + if (label == tmp) return true; - /* Allow subreg of X in case it is not writting just part of multireg pseudo. - Then we would need to update all users to care hoisting the store too. - Caller may represent that by specifying whole subreg as val. */ - - if (GET_CODE (x) == SUBREG && rtx_equal_p (SUBREG_REG (x), val)) - { - if (GET_MODE_SIZE (GET_MODE (SUBREG_REG (x))) > UNITS_PER_WORD - && GET_MODE_BITSIZE (GET_MODE (x)) < - GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))) - return false; - return true; - } - if (GET_CODE (x) == SUBREG) - x = SUBREG_REG (x); - - /* Anything except register store is not hoistable. This includes the - partial stores to registers. */ - - if (!REG_P (x)) - return false; - - /* Pseudo registers can be allways replaced by another pseudo to avoid - the side effect, for hard register we must ensure that they are dead. - Eventually we may want to add code to try turn pseudos to hards, but it - is unlikely usefull. */ - - if (REGNO (x) < FIRST_PSEUDO_REGISTER) + if (tablejump_p (jump_insn, NULL, &tmp)) { - int regno = REGNO (x); - int n = HARD_REGNO_NREGS (regno, GET_MODE (x)); + rtvec vec = XVEC (PATTERN (tmp), + GET_CODE (PATTERN (tmp)) == ADDR_DIFF_VEC); + int i, veclen = GET_NUM_ELEM (vec); - if (!live) - return false; - if (REGNO_REG_SET_P (live, regno)) - return false; - while (--n > 0) - if (REGNO_REG_SET_P (live, regno + n)) - return false; + for (i = 0; i < veclen; ++i) + if (XEXP (RTVEC_ELT (vec, i), 0) == label) + return true; } - return true; -} + return false; +} -/* Return true if INSN can be hoisted to place with LIVE hard registers - (LIVE can be NULL when unknown). VAL is expected to be stored by the insn - and used by the hoisting pass. */ + +/* Return an estimate of the cost of computing rtx X. + One use is in cse, to decide which expression to keep in the hash table. + Another is in rtl generation, to pick the cheapest way to multiply. + Other uses like the latter are expected in the future. */ -bool -can_hoist_insn_p (insn, val, live) - rtx insn, val; - regset live; +int +rtx_cost (rtx x, enum rtx_code outer_code ATTRIBUTE_UNUSED) { - rtx pat = PATTERN (insn); - int i; + int i, j; + enum rtx_code code; + const char *fmt; + int total; - /* It probably does not worth the complexity to handle multiple - set stores. */ - if (!single_set (insn)) - return false; - /* We can move CALL_INSN, but we need to check that all caller clobbered - regs are dead. */ - if (GET_CODE (insn) == CALL_INSN) - return false; - /* In future we will handle hoisting of libcall sequences, but - give up for now. */ - if (find_reg_note (insn, REG_RETVAL, NULL_RTX)) - return false; - switch (GET_CODE (pat)) + if (x == 0) + return 0; + + /* Compute the default costs of certain things. + Note that targetm.rtx_costs can override the defaults. */ + + code = GET_CODE (x); + switch (code) { - case SET: - if (!hoist_test_store (SET_DEST (pat), val, live)) - return false; + case MULT: + total = COSTS_N_INSNS (5); + break; + case DIV: + case UDIV: + case MOD: + case UMOD: + total = COSTS_N_INSNS (7); break; case USE: - /* USES do have sick semantics, so do not move them. */ - return false; + /* Used in loop.c and combine.c as a marker. */ + total = 0; break; - case CLOBBER: - if (!hoist_test_store (XEXP (pat, 0), val, live)) - return false; + default: + total = COSTS_N_INSNS (1); + } + + switch (code) + { + case REG: + return 0; + + case SUBREG: + total = 0; + /* If we can't tie these modes, make this expensive. The larger + the mode, the more expensive it is. */ + if (! MODES_TIEABLE_P (GET_MODE (x), GET_MODE (SUBREG_REG (x)))) + return COSTS_N_INSNS (2 + + GET_MODE_SIZE (GET_MODE (x)) / UNITS_PER_WORD); break; - case PARALLEL: - for (i = 0; i < XVECLEN (pat, 0); i++) + + default: + if (targetm.rtx_costs (x, code, outer_code, &total)) + return total; + break; + } + + /* Sum the costs of the sub-rtx's, plus cost of this operation, + which is already in total. */ + + fmt = GET_RTX_FORMAT (code); + for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) + if (fmt[i] == 'e') + total += rtx_cost (XEXP (x, i), code); + else if (fmt[i] == 'E') + for (j = 0; j < XVECLEN (x, i); j++) + total += rtx_cost (XVECEXP (x, i, j), code); + + return total; +} + +/* Return cost of address expression X. + Expect that X is properly formed address reference. */ + +int +address_cost (rtx x, enum machine_mode mode) +{ + /* We may be asked for cost of various unusual addresses, such as operands + of push instruction. It is not worthwhile to complicate writing + of the target hook by such cases. */ + + if (!memory_address_p (mode, x)) + return 1000; + + return targetm.address_cost (x); +} + +/* If the target doesn't override, compute the cost as with arithmetic. */ + +int +default_address_cost (rtx x) +{ + return rtx_cost (x, MEM); +} + + +unsigned HOST_WIDE_INT +nonzero_bits (rtx x, enum machine_mode mode) +{ + return cached_nonzero_bits (x, mode, NULL_RTX, VOIDmode, 0); +} + +unsigned int +num_sign_bit_copies (rtx x, enum machine_mode mode) +{ + return cached_num_sign_bit_copies (x, mode, NULL_RTX, VOIDmode, 0); +} + +/* The function cached_nonzero_bits is a wrapper around nonzero_bits1. + It avoids exponential behavior in nonzero_bits1 when X has + identical subexpressions on the first or the second level. */ + +static unsigned HOST_WIDE_INT +cached_nonzero_bits (rtx x, enum machine_mode mode, rtx known_x, + enum machine_mode known_mode, + unsigned HOST_WIDE_INT known_ret) +{ + if (x == known_x && mode == known_mode) + return known_ret; + + /* Try to find identical subexpressions. If found call + nonzero_bits1 on X with the subexpressions as KNOWN_X and the + precomputed value for the subexpression as KNOWN_RET. */ + + if (ARITHMETIC_P (x)) + { + rtx x0 = XEXP (x, 0); + rtx x1 = XEXP (x, 1); + + /* Check the first level. */ + if (x0 == x1) + return nonzero_bits1 (x, mode, x0, mode, + cached_nonzero_bits (x0, mode, known_x, + known_mode, known_ret)); + + /* Check the second level. */ + if (ARITHMETIC_P (x0) + && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1))) + return nonzero_bits1 (x, mode, x1, mode, + cached_nonzero_bits (x1, mode, known_x, + known_mode, known_ret)); + + if (ARITHMETIC_P (x1) + && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1))) + return nonzero_bits1 (x, mode, x0, mode, + cached_nonzero_bits (x0, mode, known_x, + known_mode, known_ret)); + } + + return nonzero_bits1 (x, mode, known_x, known_mode, known_ret); +} + +/* We let num_sign_bit_copies recur into nonzero_bits as that is useful. + We don't let nonzero_bits recur into num_sign_bit_copies, because that + is less useful. We can't allow both, because that results in exponential + run time recursion. There is a nullstone testcase that triggered + this. This macro avoids accidental uses of num_sign_bit_copies. */ +#define cached_num_sign_bit_copies sorry_i_am_preventing_exponential_behavior + +/* Given an expression, X, compute which bits in X can be nonzero. + We don't care about bits outside of those defined in MODE. + + For most X this is simply GET_MODE_MASK (GET_MODE (MODE)), but if X is + an arithmetic operation, we can do better. */ + +static unsigned HOST_WIDE_INT +nonzero_bits1 (rtx x, enum machine_mode mode, rtx known_x, + enum machine_mode known_mode, + unsigned HOST_WIDE_INT known_ret) +{ + unsigned HOST_WIDE_INT nonzero = GET_MODE_MASK (mode); + unsigned HOST_WIDE_INT inner_nz; + enum rtx_code code; + unsigned int mode_width = GET_MODE_BITSIZE (mode); + + /* For floating-point values, assume all bits are needed. */ + if (FLOAT_MODE_P (GET_MODE (x)) || FLOAT_MODE_P (mode)) + return nonzero; + + /* If X is wider than MODE, use its mode instead. */ + if (GET_MODE_BITSIZE (GET_MODE (x)) > mode_width) + { + mode = GET_MODE (x); + nonzero = GET_MODE_MASK (mode); + mode_width = GET_MODE_BITSIZE (mode); + } + + if (mode_width > HOST_BITS_PER_WIDE_INT) + /* Our only callers in this case look for single bit values. So + just return the mode mask. Those tests will then be false. */ + return nonzero; + +#ifndef WORD_REGISTER_OPERATIONS + /* If MODE is wider than X, but both are a single word for both the host + and target machines, we can compute this from which bits of the + object might be nonzero in its own mode, taking into account the fact + that on many CISC machines, accessing an object in a wider mode + causes the high-order bits to become undefined. So they are + not known to be zero. */ + + if (GET_MODE (x) != VOIDmode && GET_MODE (x) != mode + && GET_MODE_BITSIZE (GET_MODE (x)) <= BITS_PER_WORD + && GET_MODE_BITSIZE (GET_MODE (x)) <= HOST_BITS_PER_WIDE_INT + && GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (GET_MODE (x))) + { + nonzero &= cached_nonzero_bits (x, GET_MODE (x), + known_x, known_mode, known_ret); + nonzero |= GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x)); + return nonzero; + } +#endif + + code = GET_CODE (x); + switch (code) + { + case REG: +#if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend) + /* If pointers extend unsigned and this is a pointer in Pmode, say that + all the bits above ptr_mode are known to be zero. */ + if (POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode + && REG_POINTER (x)) + nonzero &= GET_MODE_MASK (ptr_mode); +#endif + + /* Include declared information about alignment of pointers. */ + /* ??? We don't properly preserve REG_POINTER changes across + pointer-to-integer casts, so we can't trust it except for + things that we know must be pointers. See execute/960116-1.c. */ + if ((x == stack_pointer_rtx + || x == frame_pointer_rtx + || x == arg_pointer_rtx) + && REGNO_POINTER_ALIGN (REGNO (x))) { - rtx x = XVECEXP (pat, 0, i); - switch (GET_CODE (x)) - { - case SET: - if (!hoist_test_store (SET_DEST (x), val, live)) - return false; + unsigned HOST_WIDE_INT alignment + = REGNO_POINTER_ALIGN (REGNO (x)) / BITS_PER_UNIT; + +#ifdef PUSH_ROUNDING + /* If PUSH_ROUNDING is defined, it is possible for the + stack to be momentarily aligned only to that amount, + so we pick the least alignment. */ + if (x == stack_pointer_rtx && PUSH_ARGS) + alignment = MIN ((unsigned HOST_WIDE_INT) PUSH_ROUNDING (1), + alignment); +#endif + + nonzero &= ~(alignment - 1); + } + + { + unsigned HOST_WIDE_INT nonzero_for_hook = nonzero; + rtx new = rtl_hooks.reg_nonzero_bits (x, mode, known_x, + known_mode, known_ret, + &nonzero_for_hook); + + if (new) + nonzero_for_hook &= cached_nonzero_bits (new, mode, known_x, + known_mode, known_ret); + + return nonzero_for_hook; + } + + case CONST_INT: +#ifdef SHORT_IMMEDIATES_SIGN_EXTEND + /* If X is negative in MODE, sign-extend the value. */ + if (INTVAL (x) > 0 && mode_width < BITS_PER_WORD + && 0 != (INTVAL (x) & ((HOST_WIDE_INT) 1 << (mode_width - 1)))) + return (INTVAL (x) | ((HOST_WIDE_INT) (-1) << mode_width)); +#endif + + return INTVAL (x); + + case MEM: +#ifdef LOAD_EXTEND_OP + /* In many, if not most, RISC machines, reading a byte from memory + zeros the rest of the register. Noticing that fact saves a lot + of extra zero-extends. */ + if (LOAD_EXTEND_OP (GET_MODE (x)) == ZERO_EXTEND) + nonzero &= GET_MODE_MASK (GET_MODE (x)); +#endif + break; + + case EQ: case NE: + case UNEQ: case LTGT: + case GT: case GTU: case UNGT: + case LT: case LTU: case UNLT: + case GE: case GEU: case UNGE: + case LE: case LEU: case UNLE: + case UNORDERED: case ORDERED: + + /* If this produces an integer result, we know which bits are set. + Code here used to clear bits outside the mode of X, but that is + now done above. */ + + if (GET_MODE_CLASS (mode) == MODE_INT + && mode_width <= HOST_BITS_PER_WIDE_INT) + nonzero = STORE_FLAG_VALUE; + break; + + case NEG: +#if 0 + /* Disabled to avoid exponential mutual recursion between nonzero_bits + and num_sign_bit_copies. */ + if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x)) + == GET_MODE_BITSIZE (GET_MODE (x))) + nonzero = 1; +#endif + + if (GET_MODE_SIZE (GET_MODE (x)) < mode_width) + nonzero |= (GET_MODE_MASK (mode) & ~GET_MODE_MASK (GET_MODE (x))); + break; + + case ABS: +#if 0 + /* Disabled to avoid exponential mutual recursion between nonzero_bits + and num_sign_bit_copies. */ + if (num_sign_bit_copies (XEXP (x, 0), GET_MODE (x)) + == GET_MODE_BITSIZE (GET_MODE (x))) + nonzero = 1; +#endif + break; + + case TRUNCATE: + nonzero &= (cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret) + & GET_MODE_MASK (mode)); + break; + + case ZERO_EXTEND: + nonzero &= cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + if (GET_MODE (XEXP (x, 0)) != VOIDmode) + nonzero &= GET_MODE_MASK (GET_MODE (XEXP (x, 0))); + break; + + case SIGN_EXTEND: + /* If the sign bit is known clear, this is the same as ZERO_EXTEND. + Otherwise, show all the bits in the outer mode but not the inner + may be nonzero. */ + inner_nz = cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + if (GET_MODE (XEXP (x, 0)) != VOIDmode) + { + inner_nz &= GET_MODE_MASK (GET_MODE (XEXP (x, 0))); + if (inner_nz + & (((HOST_WIDE_INT) 1 + << (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) - 1)))) + inner_nz |= (GET_MODE_MASK (mode) + & ~GET_MODE_MASK (GET_MODE (XEXP (x, 0)))); + } + + nonzero &= inner_nz; + break; + + case AND: + nonzero &= cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret) + & cached_nonzero_bits (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + break; + + case XOR: case IOR: + case UMIN: case UMAX: case SMIN: case SMAX: + { + unsigned HOST_WIDE_INT nonzero0 = + cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + + /* Don't call nonzero_bits for the second time if it cannot change + anything. */ + if ((nonzero & nonzero0) != nonzero) + nonzero &= nonzero0 + | cached_nonzero_bits (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + } + break; + + case PLUS: case MINUS: + case MULT: + case DIV: case UDIV: + case MOD: case UMOD: + /* We can apply the rules of arithmetic to compute the number of + high- and low-order zero bits of these operations. We start by + computing the width (position of the highest-order nonzero bit) + and the number of low-order zero bits for each value. */ + { + unsigned HOST_WIDE_INT nz0 = + cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + unsigned HOST_WIDE_INT nz1 = + cached_nonzero_bits (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + int sign_index = GET_MODE_BITSIZE (GET_MODE (x)) - 1; + int width0 = floor_log2 (nz0) + 1; + int width1 = floor_log2 (nz1) + 1; + int low0 = floor_log2 (nz0 & -nz0); + int low1 = floor_log2 (nz1 & -nz1); + HOST_WIDE_INT op0_maybe_minusp + = (nz0 & ((HOST_WIDE_INT) 1 << sign_index)); + HOST_WIDE_INT op1_maybe_minusp + = (nz1 & ((HOST_WIDE_INT) 1 << sign_index)); + unsigned int result_width = mode_width; + int result_low = 0; + + switch (code) + { + case PLUS: + result_width = MAX (width0, width1) + 1; + result_low = MIN (low0, low1); + break; + case MINUS: + result_low = MIN (low0, low1); + break; + case MULT: + result_width = width0 + width1; + result_low = low0 + low1; + break; + case DIV: + if (width1 == 0) break; - case USE: - /* We need to fix callers to really ensure availability - of all values inisn uses, but for now it is safe to prohibit - hoisting of any insn having such a hiden uses. */ - return false; + if (! op0_maybe_minusp && ! op1_maybe_minusp) + result_width = width0; + break; + case UDIV: + if (width1 == 0) break; - case CLOBBER: - if (!hoist_test_store (SET_DEST (x), val, live)) - return false; + result_width = width0; + break; + case MOD: + if (width1 == 0) break; - default: + if (! op0_maybe_minusp && ! op1_maybe_minusp) + result_width = MIN (width0, width1); + result_low = MIN (low0, low1); + break; + case UMOD: + if (width1 == 0) break; + result_width = MIN (width0, width1); + result_low = MIN (low0, low1); + break; + default: + gcc_unreachable (); + } + + if (result_width < mode_width) + nonzero &= ((HOST_WIDE_INT) 1 << result_width) - 1; + + if (result_low > 0) + nonzero &= ~(((HOST_WIDE_INT) 1 << result_low) - 1); + +#ifdef POINTERS_EXTEND_UNSIGNED + /* If pointers extend unsigned and this is an addition or subtraction + to a pointer in Pmode, all the bits above ptr_mode are known to be + zero. */ + if (POINTERS_EXTEND_UNSIGNED > 0 && GET_MODE (x) == Pmode + && (code == PLUS || code == MINUS) + && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0))) + nonzero &= GET_MODE_MASK (ptr_mode); +#endif + } + break; + + case ZERO_EXTRACT: + if (GET_CODE (XEXP (x, 1)) == CONST_INT + && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT) + nonzero &= ((HOST_WIDE_INT) 1 << INTVAL (XEXP (x, 1))) - 1; + break; + + case SUBREG: + /* If this is a SUBREG formed for a promoted variable that has + been zero-extended, we know that at least the high-order bits + are zero, though others might be too. */ + + if (SUBREG_PROMOTED_VAR_P (x) && SUBREG_PROMOTED_UNSIGNED_P (x) > 0) + nonzero = GET_MODE_MASK (GET_MODE (x)) + & cached_nonzero_bits (SUBREG_REG (x), GET_MODE (x), + known_x, known_mode, known_ret); + + /* If the inner mode is a single word for both the host and target + machines, we can compute this from which bits of the inner + object might be nonzero. */ + if (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) <= BITS_PER_WORD + && (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) + <= HOST_BITS_PER_WIDE_INT)) + { + nonzero &= cached_nonzero_bits (SUBREG_REG (x), mode, + known_x, known_mode, known_ret); + +#if defined (WORD_REGISTER_OPERATIONS) && defined (LOAD_EXTEND_OP) + /* If this is a typical RISC machine, we only have to worry + about the way loads are extended. */ + if ((LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND + ? (((nonzero + & (((unsigned HOST_WIDE_INT) 1 + << (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) - 1)))) + != 0)) + : LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) != ZERO_EXTEND) + || !MEM_P (SUBREG_REG (x))) +#endif + { + /* On many CISC machines, accessing an object in a wider mode + causes the high-order bits to become undefined. So they are + not known to be zero. */ + if (GET_MODE_SIZE (GET_MODE (x)) + > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) + nonzero |= (GET_MODE_MASK (GET_MODE (x)) + & ~GET_MODE_MASK (GET_MODE (SUBREG_REG (x)))); + } + } + break; + + case ASHIFTRT: + case LSHIFTRT: + case ASHIFT: + case ROTATE: + /* The nonzero bits are in two classes: any bits within MODE + that aren't in GET_MODE (x) are always significant. The rest of the + nonzero bits are those that are significant in the operand of + the shift when shifted the appropriate number of bits. This + shows that high-order bits are cleared by the right shift and + low-order bits by left shifts. */ + if (GET_CODE (XEXP (x, 1)) == CONST_INT + && INTVAL (XEXP (x, 1)) >= 0 + && INTVAL (XEXP (x, 1)) < HOST_BITS_PER_WIDE_INT) + { + enum machine_mode inner_mode = GET_MODE (x); + unsigned int width = GET_MODE_BITSIZE (inner_mode); + int count = INTVAL (XEXP (x, 1)); + unsigned HOST_WIDE_INT mode_mask = GET_MODE_MASK (inner_mode); + unsigned HOST_WIDE_INT op_nonzero = + cached_nonzero_bits (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + unsigned HOST_WIDE_INT inner = op_nonzero & mode_mask; + unsigned HOST_WIDE_INT outer = 0; + + if (mode_width > width) + outer = (op_nonzero & nonzero & ~mode_mask); + + if (code == LSHIFTRT) + inner >>= count; + else if (code == ASHIFTRT) + { + inner >>= count; + + /* If the sign bit may have been nonzero before the shift, we + need to mark all the places it could have been copied to + by the shift as possibly nonzero. */ + if (inner & ((HOST_WIDE_INT) 1 << (width - 1 - count))) + inner |= (((HOST_WIDE_INT) 1 << count) - 1) << (width - count); } + else if (code == ASHIFT) + inner <<= count; + else + inner = ((inner << (count % width) + | (inner >> (width - (count % width)))) & mode_mask); + + nonzero &= (outer | inner); } break; + + case FFS: + case POPCOUNT: + /* This is at most the number of bits in the mode. */ + nonzero = ((HOST_WIDE_INT) 2 << (floor_log2 (mode_width))) - 1; + break; + + case CLZ: + /* If CLZ has a known value at zero, then the nonzero bits are + that value, plus the number of bits in the mode minus one. */ + if (CLZ_DEFINED_VALUE_AT_ZERO (mode, nonzero)) + nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1; + else + nonzero = -1; + break; + + case CTZ: + /* If CTZ has a known value at zero, then the nonzero bits are + that value, plus the number of bits in the mode minus one. */ + if (CTZ_DEFINED_VALUE_AT_ZERO (mode, nonzero)) + nonzero |= ((HOST_WIDE_INT) 1 << (floor_log2 (mode_width))) - 1; + else + nonzero = -1; + break; + + case PARITY: + nonzero = 1; + break; + + case IF_THEN_ELSE: + { + unsigned HOST_WIDE_INT nonzero_true = + cached_nonzero_bits (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + + /* Don't call nonzero_bits for the second time if it cannot change + anything. */ + if ((nonzero & nonzero_true) != nonzero) + nonzero &= nonzero_true + | cached_nonzero_bits (XEXP (x, 2), mode, + known_x, known_mode, known_ret); + } + break; + default: - abort (); + break; } - return true; + + return nonzero; } -/* Update store after hoisting - replace all stores to pseudo registers - by new ones to avoid clobbering of values except for store to VAL that will - be updated to NEW. */ +/* See the macro definition above. */ +#undef cached_num_sign_bit_copies -static void -hoist_update_store (insn, xp, val, new) - rtx insn, *xp, val, new; + +/* The function cached_num_sign_bit_copies is a wrapper around + num_sign_bit_copies1. It avoids exponential behavior in + num_sign_bit_copies1 when X has identical subexpressions on the + first or the second level. */ + +static unsigned int +cached_num_sign_bit_copies (rtx x, enum machine_mode mode, rtx known_x, + enum machine_mode known_mode, + unsigned int known_ret) { - rtx x = *xp; + if (x == known_x && mode == known_mode) + return known_ret; - if (GET_CODE (x) == SCRATCH) - return; + /* Try to find identical subexpressions. If found call + num_sign_bit_copies1 on X with the subexpressions as KNOWN_X and + the precomputed value for the subexpression as KNOWN_RET. */ - if (GET_CODE (x) == SUBREG && SUBREG_REG (x) == val) - validate_change (insn, xp, - simplify_gen_subreg (GET_MODE (x), new, GET_MODE (new), - SUBREG_BYTE (x)), 1); - if (rtx_equal_p (x, val)) - { - validate_change (insn, xp, new, 1); - return; - } - if (GET_CODE (x) == SUBREG) + if (ARITHMETIC_P (x)) { - xp = &SUBREG_REG (x); - x = *xp; + rtx x0 = XEXP (x, 0); + rtx x1 = XEXP (x, 1); + + /* Check the first level. */ + if (x0 == x1) + return + num_sign_bit_copies1 (x, mode, x0, mode, + cached_num_sign_bit_copies (x0, mode, known_x, + known_mode, + known_ret)); + + /* Check the second level. */ + if (ARITHMETIC_P (x0) + && (x1 == XEXP (x0, 0) || x1 == XEXP (x0, 1))) + return + num_sign_bit_copies1 (x, mode, x1, mode, + cached_num_sign_bit_copies (x1, mode, known_x, + known_mode, + known_ret)); + + if (ARITHMETIC_P (x1) + && (x0 == XEXP (x1, 0) || x0 == XEXP (x1, 1))) + return + num_sign_bit_copies1 (x, mode, x0, mode, + cached_num_sign_bit_copies (x0, mode, known_x, + known_mode, + known_ret)); } - if (!REG_P (x)) - abort (); - - /* We've verified that hard registers are dead, so we may keep the side - effect. Otherwise replace it by new pseudo. */ - if (REGNO (x) >= FIRST_PSEUDO_REGISTER) - validate_change (insn, xp, gen_reg_rtx (GET_MODE (x)), 1); - REG_NOTES (insn) - = alloc_EXPR_LIST (REG_UNUSED, *xp, REG_NOTES (insn)); + return num_sign_bit_copies1 (x, mode, known_x, known_mode, known_ret); } -/* Create a copy of INSN after AFTER replacing store of VAL to NEW - and each other side effect to pseudo register by new pseudo register. */ +/* Return the number of bits at the high-order end of X that are known to + be equal to the sign bit. X will be used in mode MODE; if MODE is + VOIDmode, X will be used in its own mode. The returned value will always + be between 1 and the number of bits in MODE. */ -rtx -hoist_insn_after (insn, after, val, new) - rtx insn, after, val, new; +static unsigned int +num_sign_bit_copies1 (rtx x, enum machine_mode mode, rtx known_x, + enum machine_mode known_mode, + unsigned int known_ret) { - rtx pat; - int i; - rtx note; + enum rtx_code code = GET_CODE (x); + unsigned int bitwidth = GET_MODE_BITSIZE (mode); + int num0, num1, result; + unsigned HOST_WIDE_INT nonzero; - insn = emit_copy_of_insn_after (insn, after); - pat = PATTERN (insn); + /* If we weren't given a mode, use the mode of X. If the mode is still + VOIDmode, we don't know anything. Likewise if one of the modes is + floating-point. */ - /* Remove REG_UNUSED notes as we will re-emit them. */ - while ((note = find_reg_note (insn, REG_UNUSED, NULL_RTX))) - remove_note (insn, note); + if (mode == VOIDmode) + mode = GET_MODE (x); - /* To get this working callers must ensure to move everything referenced - by REG_EQUAL/REG_EQUIV notes too. Lets remove them, it is probably - easier. */ - while ((note = find_reg_note (insn, REG_EQUAL, NULL_RTX))) - remove_note (insn, note); - while ((note = find_reg_note (insn, REG_EQUIV, NULL_RTX))) - remove_note (insn, note); + if (mode == VOIDmode || FLOAT_MODE_P (mode) || FLOAT_MODE_P (GET_MODE (x))) + return 1; - /* Remove REG_DEAD notes as they might not be valid anymore in case - we create redundancy. */ - while ((note = find_reg_note (insn, REG_DEAD, NULL_RTX))) - remove_note (insn, note); - switch (GET_CODE (pat)) + /* For a smaller object, just ignore the high bits. */ + if (bitwidth < GET_MODE_BITSIZE (GET_MODE (x))) { - case SET: - hoist_update_store (insn, &SET_DEST (pat), val, new); + num0 = cached_num_sign_bit_copies (x, GET_MODE (x), + known_x, known_mode, known_ret); + return MAX (1, + num0 - (int) (GET_MODE_BITSIZE (GET_MODE (x)) - bitwidth)); + } + + if (GET_MODE (x) != VOIDmode && bitwidth > GET_MODE_BITSIZE (GET_MODE (x))) + { +#ifndef WORD_REGISTER_OPERATIONS + /* If this machine does not do all register operations on the entire + register and MODE is wider than the mode of X, we can say nothing + at all about the high-order bits. */ + return 1; +#else + /* Likewise on machines that do, if the mode of the object is smaller + than a word and loads of that size don't sign extend, we can say + nothing about the high order bits. */ + if (GET_MODE_BITSIZE (GET_MODE (x)) < BITS_PER_WORD +#ifdef LOAD_EXTEND_OP + && LOAD_EXTEND_OP (GET_MODE (x)) != SIGN_EXTEND +#endif + ) + return 1; +#endif + } + + switch (code) + { + case REG: + +#if defined(POINTERS_EXTEND_UNSIGNED) && !defined(HAVE_ptr_extend) + /* If pointers extend signed and this is a pointer in Pmode, say that + all the bits above ptr_mode are known to be sign bit copies. */ + if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode && mode == Pmode + && REG_POINTER (x)) + return GET_MODE_BITSIZE (Pmode) - GET_MODE_BITSIZE (ptr_mode) + 1; +#endif + + { + unsigned int copies_for_hook = 1, copies = 1; + rtx new = rtl_hooks.reg_num_sign_bit_copies (x, mode, known_x, + known_mode, known_ret, + &copies_for_hook); + + if (new) + copies = cached_num_sign_bit_copies (new, mode, known_x, + known_mode, known_ret); + + if (copies > 1 || copies_for_hook > 1) + return MAX (copies, copies_for_hook); + + /* Else, use nonzero_bits to guess num_sign_bit_copies (see below). */ + } break; - case USE: + + case MEM: +#ifdef LOAD_EXTEND_OP + /* Some RISC machines sign-extend all loads of smaller than a word. */ + if (LOAD_EXTEND_OP (GET_MODE (x)) == SIGN_EXTEND) + return MAX (1, ((int) bitwidth + - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1)); +#endif break; - case CLOBBER: - hoist_update_store (insn, &XEXP (pat, 0), val, new); + + case CONST_INT: + /* If the constant is negative, take its 1's complement and remask. + Then see how many zero bits we have. */ + nonzero = INTVAL (x) & GET_MODE_MASK (mode); + if (bitwidth <= HOST_BITS_PER_WIDE_INT + && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0) + nonzero = (~nonzero) & GET_MODE_MASK (mode); + + return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1); + + case SUBREG: + /* If this is a SUBREG for a promoted object that is sign-extended + and we are looking at it in a wider mode, we know that at least the + high-order bits are known to be sign bit copies. */ + + if (SUBREG_PROMOTED_VAR_P (x) && ! SUBREG_PROMOTED_UNSIGNED_P (x)) + { + num0 = cached_num_sign_bit_copies (SUBREG_REG (x), mode, + known_x, known_mode, known_ret); + return MAX ((int) bitwidth + - (int) GET_MODE_BITSIZE (GET_MODE (x)) + 1, + num0); + } + + /* For a smaller object, just ignore the high bits. */ + if (bitwidth <= GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x)))) + { + num0 = cached_num_sign_bit_copies (SUBREG_REG (x), VOIDmode, + known_x, known_mode, known_ret); + return MAX (1, (num0 + - (int) (GET_MODE_BITSIZE (GET_MODE (SUBREG_REG (x))) + - bitwidth))); + } + +#ifdef WORD_REGISTER_OPERATIONS +#ifdef LOAD_EXTEND_OP + /* For paradoxical SUBREGs on machines where all register operations + affect the entire register, just look inside. Note that we are + passing MODE to the recursive call, so the number of sign bit copies + will remain relative to that mode, not the inner mode. */ + + /* This works only if loads sign extend. Otherwise, if we get a + reload for the inner part, it may be loaded from the stack, and + then we lose all sign bit copies that existed before the store + to the stack. */ + + if ((GET_MODE_SIZE (GET_MODE (x)) + > GET_MODE_SIZE (GET_MODE (SUBREG_REG (x)))) + && LOAD_EXTEND_OP (GET_MODE (SUBREG_REG (x))) == SIGN_EXTEND + && MEM_P (SUBREG_REG (x))) + return cached_num_sign_bit_copies (SUBREG_REG (x), mode, + known_x, known_mode, known_ret); +#endif +#endif break; - case PARALLEL: + + case SIGN_EXTRACT: + if (GET_CODE (XEXP (x, 1)) == CONST_INT) + return MAX (1, (int) bitwidth - INTVAL (XEXP (x, 1))); + break; + + case SIGN_EXTEND: + return (bitwidth - GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) + + cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode, + known_x, known_mode, known_ret)); + + case TRUNCATE: + /* For a smaller object, just ignore the high bits. */ + num0 = cached_num_sign_bit_copies (XEXP (x, 0), VOIDmode, + known_x, known_mode, known_ret); + return MAX (1, (num0 - (int) (GET_MODE_BITSIZE (GET_MODE (XEXP (x, 0))) + - bitwidth))); + + case NOT: + return cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + + case ROTATE: case ROTATERT: + /* If we are rotating left by a number of bits less than the number + of sign bit copies, we can just subtract that amount from the + number. */ + if (GET_CODE (XEXP (x, 1)) == CONST_INT + && INTVAL (XEXP (x, 1)) >= 0 + && INTVAL (XEXP (x, 1)) < (int) bitwidth) + { + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + return MAX (1, num0 - (code == ROTATE ? INTVAL (XEXP (x, 1)) + : (int) bitwidth - INTVAL (XEXP (x, 1)))); + } + break; + + case NEG: + /* In general, this subtracts one sign bit copy. But if the value + is known to be positive, the number of sign bit copies is the + same as that of the input. Finally, if the input has just one bit + that might be nonzero, all the bits are copies of the sign bit. */ + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + if (bitwidth > HOST_BITS_PER_WIDE_INT) + return num0 > 1 ? num0 - 1 : 1; + + nonzero = nonzero_bits (XEXP (x, 0), mode); + if (nonzero == 1) + return bitwidth; + + if (num0 > 1 + && (((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero)) + num0--; + + return num0; + + case IOR: case AND: case XOR: + case SMIN: case SMAX: case UMIN: case UMAX: + /* Logical operations will preserve the number of sign-bit copies. + MIN and MAX operations always return one of the operands. */ + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + return MIN (num0, num1); + + case PLUS: case MINUS: + /* For addition and subtraction, we can have a 1-bit carry. However, + if we are subtracting 1 from a positive number, there will not + be such a carry. Furthermore, if the positive number is known to + be 0 or 1, we know the result is either -1 or 0. */ + + if (code == PLUS && XEXP (x, 1) == constm1_rtx + && bitwidth <= HOST_BITS_PER_WIDE_INT) + { + nonzero = nonzero_bits (XEXP (x, 0), mode); + if ((((HOST_WIDE_INT) 1 << (bitwidth - 1)) & nonzero) == 0) + return (nonzero == 1 || nonzero == 0 ? bitwidth + : bitwidth - floor_log2 (nonzero) - 1); + } + + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + result = MAX (1, MIN (num0, num1) - 1); + +#ifdef POINTERS_EXTEND_UNSIGNED + /* If pointers extend signed and this is an addition or subtraction + to a pointer in Pmode, all the bits above ptr_mode are known to be + sign bit copies. */ + if (! POINTERS_EXTEND_UNSIGNED && GET_MODE (x) == Pmode + && (code == PLUS || code == MINUS) + && REG_P (XEXP (x, 0)) && REG_POINTER (XEXP (x, 0))) + result = MAX ((int) (GET_MODE_BITSIZE (Pmode) + - GET_MODE_BITSIZE (ptr_mode) + 1), + result); +#endif + return result; + + case MULT: + /* The number of bits of the product is the sum of the number of + bits of both terms. However, unless one of the terms if known + to be positive, we must allow for an additional bit since negating + a negative number can remove one sign bit copy. */ + + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + num1 = cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + + result = bitwidth - (bitwidth - num0) - (bitwidth - num1); + if (result > 0 + && (bitwidth > HOST_BITS_PER_WIDE_INT + || (((nonzero_bits (XEXP (x, 0), mode) + & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0) + && ((nonzero_bits (XEXP (x, 1), mode) + & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)))) + result--; + + return MAX (1, result); + + case UDIV: + /* The result must be <= the first operand. If the first operand + has the high bit set, we know nothing about the number of sign + bit copies. */ + if (bitwidth > HOST_BITS_PER_WIDE_INT) + return 1; + else if ((nonzero_bits (XEXP (x, 0), mode) + & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0) + return 1; + else + return cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + + case UMOD: + /* The result must be <= the second operand. */ + return cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + + case DIV: + /* Similar to unsigned division, except that we have to worry about + the case where the divisor is negative, in which case we have + to add 1. */ + result = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + if (result > 1 + && (bitwidth > HOST_BITS_PER_WIDE_INT + || (nonzero_bits (XEXP (x, 1), mode) + & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)) + result--; + + return result; + + case MOD: + result = cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + if (result > 1 + && (bitwidth > HOST_BITS_PER_WIDE_INT + || (nonzero_bits (XEXP (x, 1), mode) + & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0)) + result--; + + return result; + + case ASHIFTRT: + /* Shifts by a constant add to the number of bits equal to the + sign bit. */ + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + if (GET_CODE (XEXP (x, 1)) == CONST_INT + && INTVAL (XEXP (x, 1)) > 0) + num0 = MIN ((int) bitwidth, num0 + INTVAL (XEXP (x, 1))); + + return num0; + + case ASHIFT: + /* Left shifts destroy copies. */ + if (GET_CODE (XEXP (x, 1)) != CONST_INT + || INTVAL (XEXP (x, 1)) < 0 + || INTVAL (XEXP (x, 1)) >= (int) bitwidth) + return 1; + + num0 = cached_num_sign_bit_copies (XEXP (x, 0), mode, + known_x, known_mode, known_ret); + return MAX (1, num0 - INTVAL (XEXP (x, 1))); + + case IF_THEN_ELSE: + num0 = cached_num_sign_bit_copies (XEXP (x, 1), mode, + known_x, known_mode, known_ret); + num1 = cached_num_sign_bit_copies (XEXP (x, 2), mode, + known_x, known_mode, known_ret); + return MIN (num0, num1); + + case EQ: case NE: case GE: case GT: case LE: case LT: + case UNEQ: case LTGT: case UNGE: case UNGT: case UNLE: case UNLT: + case GEU: case GTU: case LEU: case LTU: + case UNORDERED: case ORDERED: + /* If the constant is negative, take its 1's complement and remask. + Then see how many zero bits we have. */ + nonzero = STORE_FLAG_VALUE; + if (bitwidth <= HOST_BITS_PER_WIDE_INT + && (nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1))) != 0) + nonzero = (~nonzero) & GET_MODE_MASK (mode); + + return (nonzero == 0 ? bitwidth : bitwidth - floor_log2 (nonzero) - 1); + + default: + break; + } + + /* If we haven't been able to figure it out by one of the above rules, + see if some of the high-order bits are known to be zero. If so, + count those bits and return one less than that amount. If we can't + safely compute the mask for this mode, always return BITWIDTH. */ + + bitwidth = GET_MODE_BITSIZE (mode); + if (bitwidth > HOST_BITS_PER_WIDE_INT) + return 1; + + nonzero = nonzero_bits (x, mode); + return nonzero & ((HOST_WIDE_INT) 1 << (bitwidth - 1)) + ? 1 : bitwidth - floor_log2 (nonzero) - 1; +} + +/* Calculate the rtx_cost of a single instruction. A return value of + zero indicates an instruction pattern without a known cost. */ + +int +insn_rtx_cost (rtx pat) +{ + int i, cost; + rtx set; + + /* Extract the single set rtx from the instruction pattern. + We can't use single_set since we only have the pattern. */ + if (GET_CODE (pat) == SET) + set = pat; + else if (GET_CODE (pat) == PARALLEL) + { + set = NULL_RTX; for (i = 0; i < XVECLEN (pat, 0); i++) { rtx x = XVECEXP (pat, 0, i); - switch (GET_CODE (x)) + if (GET_CODE (x) == SET) { - case SET: - hoist_update_store (insn, &SET_DEST (x), val, new); - break; - case USE: - break; - case CLOBBER: - hoist_update_store (insn, &SET_DEST (x), val, new); - break; - default: - break; + if (set) + return 0; + set = x; } } - break; - default: - abort (); + if (!set) + return 0; } - if (!apply_change_group ()) - abort (); + else + return 0; - return insn; + cost = rtx_cost (SET_SRC (set), SET); + return cost > 0 ? cost : COSTS_N_INSNS (1); } +/* Given an insn INSN and condition COND, return the condition in a + canonical form to simplify testing by callers. Specifically: + + (1) The code will always be a comparison operation (EQ, NE, GT, etc.). + (2) Both operands will be machine operands; (cc0) will have been replaced. + (3) If an operand is a constant, it will be the second operand. + (4) (LE x const) will be replaced with (LT x ) and similarly + for GE, GEU, and LEU. + + If the condition cannot be understood, or is an inequality floating-point + comparison which needs to be reversed, 0 will be returned. + + If REVERSE is nonzero, then reverse the condition prior to canonizing it. + + If EARLIEST is nonzero, it is a pointer to a place where the earliest + insn used in locating the condition was found. If a replacement test + of the condition is desired, it should be placed in front of that + insn and we will be sure that the inputs are still valid. + + If WANT_REG is nonzero, we wish the condition to be relative to that + register, if possible. Therefore, do not canonicalize the condition + further. If ALLOW_CC_MODE is nonzero, allow the condition returned + to be a compare to a CC mode register. + + If VALID_AT_INSN_P, the condition must be valid at both *EARLIEST + and at INSN. */ + rtx -hoist_insn_to_edge (insn, e, val, new) - rtx insn, val, new; - edge e; +canonicalize_condition (rtx insn, rtx cond, int reverse, rtx *earliest, + rtx want_reg, int allow_cc_mode, int valid_at_insn_p) { - rtx new_insn; + enum rtx_code code; + rtx prev = insn; + rtx set; + rtx tem; + rtx op0, op1; + int reverse_code = 0; + enum machine_mode mode; + + code = GET_CODE (cond); + mode = GET_MODE (cond); + op0 = XEXP (cond, 0); + op1 = XEXP (cond, 1); + + if (reverse) + code = reversed_comparison_code (cond, insn); + if (code == UNKNOWN) + return 0; + + if (earliest) + *earliest = insn; - /* We cannot insert instructions on an abnormal critical edge. - It will be easier to find the culprit if we die now. */ - if ((e->flags & EDGE_ABNORMAL) && EDGE_CRITICAL_P (e)) - abort (); + /* If we are comparing a register with zero, see if the register is set + in the previous insn to a COMPARE or a comparison operation. Perform + the same tests as a function of STORE_FLAG_VALUE as find_comparison_args + in cse.c */ - /* Do not use emit_insn_on_edge as we want to preserve notes and similar - stuff. We also emit CALL_INSNS and firends. */ - if (e->insns == NULL_RTX) + while ((GET_RTX_CLASS (code) == RTX_COMPARE + || GET_RTX_CLASS (code) == RTX_COMM_COMPARE) + && op1 == CONST0_RTX (GET_MODE (op0)) + && op0 != want_reg) { - start_sequence (); - emit_note (NULL, NOTE_INSN_DELETED); + /* Set nonzero when we find something of interest. */ + rtx x = 0; + +#ifdef HAVE_cc0 + /* If comparison with cc0, import actual comparison from compare + insn. */ + if (op0 == cc0_rtx) + { + if ((prev = prev_nonnote_insn (prev)) == 0 + || !NONJUMP_INSN_P (prev) + || (set = single_set (prev)) == 0 + || SET_DEST (set) != cc0_rtx) + return 0; + + op0 = SET_SRC (set); + op1 = CONST0_RTX (GET_MODE (op0)); + if (earliest) + *earliest = prev; + } +#endif + + /* If this is a COMPARE, pick up the two things being compared. */ + if (GET_CODE (op0) == COMPARE) + { + op1 = XEXP (op0, 1); + op0 = XEXP (op0, 0); + continue; + } + else if (!REG_P (op0)) + break; + + /* Go back to the previous insn. Stop if it is not an INSN. We also + stop if it isn't a single set or if it has a REG_INC note because + we don't want to bother dealing with it. */ + + if ((prev = prev_nonnote_insn (prev)) == 0 + || !NONJUMP_INSN_P (prev) + || FIND_REG_INC_NOTE (prev, NULL_RTX)) + break; + + set = set_of (op0, prev); + + if (set + && (GET_CODE (set) != SET + || !rtx_equal_p (SET_DEST (set), op0))) + break; + + /* If this is setting OP0, get what it sets it to if it looks + relevant. */ + if (set) + { + enum machine_mode inner_mode = GET_MODE (SET_DEST (set)); +#ifdef FLOAT_STORE_FLAG_VALUE + REAL_VALUE_TYPE fsfv; +#endif + + /* ??? We may not combine comparisons done in a CCmode with + comparisons not done in a CCmode. This is to aid targets + like Alpha that have an IEEE compliant EQ instruction, and + a non-IEEE compliant BEQ instruction. The use of CCmode is + actually artificial, simply to prevent the combination, but + should not affect other platforms. + + However, we must allow VOIDmode comparisons to match either + CCmode or non-CCmode comparison, because some ports have + modeless comparisons inside branch patterns. + + ??? This mode check should perhaps look more like the mode check + in simplify_comparison in combine. */ + + if ((GET_CODE (SET_SRC (set)) == COMPARE + || (((code == NE + || (code == LT + && GET_MODE_CLASS (inner_mode) == MODE_INT + && (GET_MODE_BITSIZE (inner_mode) + <= HOST_BITS_PER_WIDE_INT) + && (STORE_FLAG_VALUE + & ((HOST_WIDE_INT) 1 + << (GET_MODE_BITSIZE (inner_mode) - 1)))) +#ifdef FLOAT_STORE_FLAG_VALUE + || (code == LT + && GET_MODE_CLASS (inner_mode) == MODE_FLOAT + && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode), + REAL_VALUE_NEGATIVE (fsfv))) +#endif + )) + && COMPARISON_P (SET_SRC (set)))) + && (((GET_MODE_CLASS (mode) == MODE_CC) + == (GET_MODE_CLASS (inner_mode) == MODE_CC)) + || mode == VOIDmode || inner_mode == VOIDmode)) + x = SET_SRC (set); + else if (((code == EQ + || (code == GE + && (GET_MODE_BITSIZE (inner_mode) + <= HOST_BITS_PER_WIDE_INT) + && GET_MODE_CLASS (inner_mode) == MODE_INT + && (STORE_FLAG_VALUE + & ((HOST_WIDE_INT) 1 + << (GET_MODE_BITSIZE (inner_mode) - 1)))) +#ifdef FLOAT_STORE_FLAG_VALUE + || (code == GE + && GET_MODE_CLASS (inner_mode) == MODE_FLOAT + && (fsfv = FLOAT_STORE_FLAG_VALUE (inner_mode), + REAL_VALUE_NEGATIVE (fsfv))) +#endif + )) + && COMPARISON_P (SET_SRC (set)) + && (((GET_MODE_CLASS (mode) == MODE_CC) + == (GET_MODE_CLASS (inner_mode) == MODE_CC)) + || mode == VOIDmode || inner_mode == VOIDmode)) + + { + reverse_code = 1; + x = SET_SRC (set); + } + else + break; + } + + else if (reg_set_p (op0, prev)) + /* If this sets OP0, but not directly, we have to give up. */ + break; + + if (x) + { + /* If the caller is expecting the condition to be valid at INSN, + make sure X doesn't change before INSN. */ + if (valid_at_insn_p) + if (modified_in_p (x, prev) || modified_between_p (x, prev, insn)) + break; + if (COMPARISON_P (x)) + code = GET_CODE (x); + if (reverse_code) + { + code = reversed_comparison_code (x, prev); + if (code == UNKNOWN) + return 0; + reverse_code = 0; + } + + op0 = XEXP (x, 0), op1 = XEXP (x, 1); + if (earliest) + *earliest = prev; + } } - else - push_to_sequence (e->insns); - new_insn = hoist_insn_after (insn, get_last_insn (), val, new); + /* If constant is first, put it last. */ + if (CONSTANT_P (op0)) + code = swap_condition (code), tem = op0, op0 = op1, op1 = tem; + + /* If OP0 is the result of a comparison, we weren't able to find what + was really being compared, so fail. */ + if (!allow_cc_mode + && GET_MODE_CLASS (GET_MODE (op0)) == MODE_CC) + return 0; + + /* Canonicalize any ordered comparison with integers involving equality + if we can do computations in the relevant mode and we do not + overflow. */ + + if (GET_MODE_CLASS (GET_MODE (op0)) != MODE_CC + && GET_CODE (op1) == CONST_INT + && GET_MODE (op0) != VOIDmode + && GET_MODE_BITSIZE (GET_MODE (op0)) <= HOST_BITS_PER_WIDE_INT) + { + HOST_WIDE_INT const_val = INTVAL (op1); + unsigned HOST_WIDE_INT uconst_val = const_val; + unsigned HOST_WIDE_INT max_val + = (unsigned HOST_WIDE_INT) GET_MODE_MASK (GET_MODE (op0)); + + switch (code) + { + case LE: + if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1) + code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0)); + break; + + /* When cross-compiling, const_val might be sign-extended from + BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */ + case GE: + if ((HOST_WIDE_INT) (const_val & max_val) + != (((HOST_WIDE_INT) 1 + << (GET_MODE_BITSIZE (GET_MODE (op0)) - 1)))) + code = GT, op1 = gen_int_mode (const_val - 1, GET_MODE (op0)); + break; + + case LEU: + if (uconst_val < max_val) + code = LTU, op1 = gen_int_mode (uconst_val + 1, GET_MODE (op0)); + break; + + case GEU: + if (uconst_val != 0) + code = GTU, op1 = gen_int_mode (uconst_val - 1, GET_MODE (op0)); + break; + + default: + break; + } + } - e->insns = get_insns (); - end_sequence (); - return new_insn; + /* Never return CC0; return zero instead. */ + if (CC0_P (op0)) + return 0; + + return gen_rtx_fmt_ee (code, VOIDmode, op0, op1); +} + +/* Given a jump insn JUMP, return the condition that will cause it to branch + to its JUMP_LABEL. If the condition cannot be understood, or is an + inequality floating-point comparison which needs to be reversed, 0 will + be returned. + + If EARLIEST is nonzero, it is a pointer to a place where the earliest + insn used in locating the condition was found. If a replacement test + of the condition is desired, it should be placed in front of that + insn and we will be sure that the inputs are still valid. If EARLIEST + is null, the returned condition will be valid at INSN. + + If ALLOW_CC_MODE is nonzero, allow the condition returned to be a + compare CC mode register. + + VALID_AT_INSN_P is the same as for canonicalize_condition. */ + +rtx +get_condition (rtx jump, rtx *earliest, int allow_cc_mode, int valid_at_insn_p) +{ + rtx cond; + int reverse; + rtx set; + + /* If this is not a standard conditional jump, we can't parse it. */ + if (!JUMP_P (jump) + || ! any_condjump_p (jump)) + return 0; + set = pc_set (jump); + + cond = XEXP (SET_SRC (set), 0); + + /* If this branches to JUMP_LABEL when the condition is false, reverse + the condition. */ + reverse + = GET_CODE (XEXP (SET_SRC (set), 2)) == LABEL_REF + && XEXP (XEXP (SET_SRC (set), 2), 0) == JUMP_LABEL (jump); + + return canonicalize_condition (jump, cond, reverse, earliest, NULL_RTX, + allow_cc_mode, valid_at_insn_p); +} + + +/* Initialize non_rtx_starting_operands, which is used to speed up + for_each_rtx. */ +void +init_rtlanal (void) +{ + int i; + for (i = 0; i < NUM_RTX_CODE; i++) + { + const char *format = GET_RTX_FORMAT (i); + const char *first = strpbrk (format, "eEV"); + non_rtx_starting_operands[i] = first ? first - format : -1; + } }