X-Git-Url: http://git.ipfire.org/?a=blobdiff_plain;f=gcc%2Floop-iv.c;h=82b4bdb15232a4eb16c257f36c18335cae628b68;hb=1fcf995f9521c6a958944b5f8bd94d18131d8a0a;hp=6b5f82b16b1ab0c59323d8d303e13ae64a9893ae;hpb=81c6af2dc6f960f98ef064146de297755d6b0894;p=thirdparty%2Fgcc.git diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c index 6b5f82b16b1a..82b4bdb15232 100644 --- a/gcc/loop-iv.c +++ b/gcc/loop-iv.c @@ -1,5 +1,5 @@ /* Rtl-level induction variable analysis. - Copyright (C) 2004-2013 Free Software Foundation, Inc. + Copyright (C) 2004-2019 Free Software Foundation, Inc. This file is part of GCC. @@ -35,33 +35,32 @@ along with GCC; see the file COPYING3. If not see The available functions are: - iv_analyze (insn, reg, iv): Stores the description of the induction variable - corresponding to the use of register REG in INSN to IV. Returns true if - REG is an induction variable in INSN. false otherwise. - If use of REG is not found in INSN, following insns are scanned (so that - we may call this function on insn returned by get_condition). + iv_analyze (insn, mode, reg, iv): Stores the description of the induction + variable corresponding to the use of register REG in INSN to IV, given + that REG has mode MODE. Returns true if REG is an induction variable + in INSN. false otherwise. If a use of REG is not found in INSN, + the following insns are scanned (so that we may call this function + on insns returned by get_condition). iv_analyze_result (insn, def, iv): Stores to IV the description of the iv corresponding to DEF, which is a register defined in INSN. - iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv + iv_analyze_expr (insn, mode, expr, iv): Stores to IV the description of iv corresponding to expression EXPR evaluated at INSN. All registers used bu - EXPR must also be used in INSN. + EXPR must also be used in INSN. MODE is the mode of EXPR. */ #include "config.h" #include "system.h" #include "coretypes.h" -#include "tm.h" +#include "backend.h" #include "rtl.h" -#include "hard-reg-set.h" -#include "obstack.h" -#include "basic-block.h" +#include "df.h" +#include "memmodel.h" +#include "emit-rtl.h" +#include "diagnostic-core.h" #include "cfgloop.h" -#include "expr.h" #include "intl.h" -#include "diagnostic-core.h" -#include "df.h" -#include "hash-table.h" #include "dumpfile.h" +#include "rtl-iter.h" /* Possible return values of iv_get_reaching_def. */ @@ -108,18 +107,17 @@ static struct loop *current_loop; /* Hashtable helper. */ -struct biv_entry_hasher : typed_free_remove +struct biv_entry_hasher : free_ptr_hash { - typedef biv_entry value_type; - typedef rtx_def compare_type; - static inline hashval_t hash (const value_type *); - static inline bool equal (const value_type *, const compare_type *); + typedef rtx_def *compare_type; + static inline hashval_t hash (const biv_entry *); + static inline bool equal (const biv_entry *, const rtx_def *); }; /* Returns hash value for biv B. */ inline hashval_t -biv_entry_hasher::hash (const value_type *b) +biv_entry_hasher::hash (const biv_entry *b) { return b->regno; } @@ -127,16 +125,16 @@ biv_entry_hasher::hash (const value_type *b) /* Compares biv B and register R. */ inline bool -biv_entry_hasher::equal (const value_type *b, const compare_type *r) +biv_entry_hasher::equal (const biv_entry *b, const rtx_def *r) { return b->regno == REGNO (r); } /* Bivs of the current loop. */ -static hash_table bivs; +static hash_table *bivs; -static bool iv_analyze_op (rtx, rtx, struct rtx_iv *); +static bool iv_analyze_op (rtx_insn *, scalar_int_mode, rtx, struct rtx_iv *); /* Return the RTX code corresponding to the IV extend code EXTEND. */ static inline enum rtx_code @@ -198,17 +196,6 @@ dump_iv_info (FILE *file, struct rtx_iv *iv) fprintf (file, " (first special)"); } -/* Generates a subreg to get the least significant part of EXPR (in mode - INNER_MODE) to OUTER_MODE. */ - -rtx -lowpart_subreg (enum machine_mode outer_mode, rtx expr, - enum machine_mode inner_mode) -{ - return simplify_gen_subreg (outer_mode, expr, inner_mode, - subreg_lowpart_offset (outer_mode, inner_mode)); -} - static void check_iv_ref_table_size (void) { @@ -269,7 +256,7 @@ clear_iv_info (void) } } - bivs.empty (); + bivs->empty (); } @@ -278,27 +265,18 @@ clear_iv_info (void) void iv_analysis_loop_init (struct loop *loop) { - basic_block *body = get_loop_body_in_dom_order (loop), bb; - bitmap blocks = BITMAP_ALLOC (NULL); - unsigned i; - current_loop = loop; /* Clear the information from the analysis of the previous loop. */ if (clean_slate) { df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN); - bivs.create (10); + bivs = new hash_table (10); clean_slate = false; } else clear_iv_info (); - for (i = 0; i < loop->num_nodes; i++) - { - bb = body[i]; - bitmap_set_bit (blocks, bb->index); - } /* Get rid of the ud chains before processing the rescans. Then add the problem back. */ df_remove_problem (df_chain); @@ -306,14 +284,11 @@ iv_analysis_loop_init (struct loop *loop) df_set_flags (DF_RD_PRUNE_DEAD_DEFS); df_chain_add_problem (DF_UD_CHAIN); df_note_add_problem (); - df_set_blocks (blocks); - df_analyze (); + df_analyze_loop (loop); if (dump_file) df_dump_region (dump_file); check_iv_ref_table_size (); - BITMAP_FREE (blocks); - free (body); } /* Finds the definition of REG that dominates loop latch and stores @@ -351,11 +326,11 @@ latch_dominating_def (rtx reg, df_ref *def) /* Gets definition of REG reaching its use in INSN and stores it to DEF. */ static enum iv_grd_result -iv_get_reaching_def (rtx insn, rtx reg, df_ref *def) +iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def) { df_ref use, adef; basic_block def_bb, use_bb; - rtx def_insn; + rtx_insn *def_insn; bool dom_p; *def = NULL; @@ -409,11 +384,8 @@ iv_get_reaching_def (rtx insn, rtx reg, df_ref *def) consistency with other iv manipulation functions that may fail). */ static bool -iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode) +iv_constant (struct rtx_iv *iv, scalar_int_mode mode, rtx cst) { - if (mode == VOIDmode) - mode = GET_MODE (cst); - iv->mode = mode; iv->base = cst; iv->step = const0_rtx; @@ -429,7 +401,7 @@ iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode) /* Evaluates application of subreg to MODE on IV. */ static bool -iv_subreg (struct rtx_iv *iv, enum machine_mode mode) +iv_subreg (struct rtx_iv *iv, scalar_int_mode mode) { /* If iv is invariant, just calculate the new value. */ if (iv->step == const0_rtx @@ -471,7 +443,7 @@ iv_subreg (struct rtx_iv *iv, enum machine_mode mode) /* Evaluates application of EXTEND to MODE on IV. */ static bool -iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode) +iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, scalar_int_mode mode) { /* If iv is invariant, just calculate the new value. */ if (iv->step == const0_rtx @@ -534,7 +506,7 @@ iv_neg (struct rtx_iv *iv) static bool iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op) { - enum machine_mode mode; + scalar_int_mode mode; rtx arg; /* Extend the constant to extend_mode of the other operand if necessary. */ @@ -604,7 +576,7 @@ iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op) static bool iv_mult (struct rtx_iv *iv, rtx mby) { - enum machine_mode mode = iv->extend_mode; + scalar_int_mode mode = iv->extend_mode; if (GET_MODE (mby) != VOIDmode && GET_MODE (mby) != mode) @@ -629,7 +601,7 @@ iv_mult (struct rtx_iv *iv, rtx mby) static bool iv_shift (struct rtx_iv *iv, rtx mby) { - enum machine_mode mode = iv->extend_mode; + scalar_int_mode mode = iv->extend_mode; if (GET_MODE (mby) != VOIDmode && GET_MODE (mby) != mode) @@ -654,15 +626,15 @@ iv_shift (struct rtx_iv *iv, rtx mby) at get_biv_step. */ static bool -get_biv_step_1 (df_ref def, rtx reg, - rtx *inner_step, enum machine_mode *inner_mode, - enum iv_extend_code *extend, enum machine_mode outer_mode, +get_biv_step_1 (df_ref def, scalar_int_mode outer_mode, rtx reg, + rtx *inner_step, scalar_int_mode *inner_mode, + enum iv_extend_code *extend, rtx *outer_step) { rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX; - rtx next, nextr, tmp; + rtx next, nextr; enum rtx_code code; - rtx insn = DF_REF_INSN (def); + rtx_insn *insn = DF_REF_INSN (def); df_ref next_def; enum iv_grd_result res; @@ -690,9 +662,7 @@ get_biv_step_1 (df_ref def, rtx reg, op1 = XEXP (rhs, 1); if (code == PLUS && CONSTANT_P (op0)) - { - tmp = op0; op0 = op1; op1 = tmp; - } + std::swap (op0, op1); if (!simple_reg_p (op0) || !CONSTANT_P (op1)) @@ -760,16 +730,16 @@ get_biv_step_1 (df_ref def, rtx reg, *inner_mode = outer_mode; *outer_step = const0_rtx; } - else if (!get_biv_step_1 (next_def, reg, - inner_step, inner_mode, extend, outer_mode, + else if (!get_biv_step_1 (next_def, outer_mode, reg, + inner_step, inner_mode, extend, outer_step)) return false; if (GET_CODE (next) == SUBREG) { - enum machine_mode amode = GET_MODE (next); - - if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode)) + scalar_int_mode amode; + if (!is_a (GET_MODE (next), &amode) + || GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode)) return false; *inner_mode = amode; @@ -821,19 +791,17 @@ get_biv_step_1 (df_ref def, rtx reg, LAST_DEF is the definition of REG that dominates loop latch. */ static bool -get_biv_step (df_ref last_def, rtx reg, rtx *inner_step, - enum machine_mode *inner_mode, enum iv_extend_code *extend, - enum machine_mode *outer_mode, rtx *outer_step) +get_biv_step (df_ref last_def, scalar_int_mode outer_mode, rtx reg, + rtx *inner_step, scalar_int_mode *inner_mode, + enum iv_extend_code *extend, rtx *outer_step) { - *outer_mode = GET_MODE (reg); - - if (!get_biv_step_1 (last_def, reg, - inner_step, inner_mode, extend, *outer_mode, + if (!get_biv_step_1 (last_def, outer_mode, reg, + inner_step, inner_mode, extend, outer_step)) return false; - gcc_assert ((*inner_mode == *outer_mode) != (*extend != IV_UNKNOWN_EXTEND)); - gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx); + gcc_assert ((*inner_mode == outer_mode) != (*extend != IV_UNKNOWN_EXTEND)); + gcc_assert (*inner_mode != outer_mode || *outer_step == const0_rtx); return true; } @@ -856,7 +824,7 @@ record_iv (df_ref def, struct rtx_iv *iv) static bool analyzed_for_bivness_p (rtx def, struct rtx_iv *iv) { - struct biv_entry *biv = bivs.find_with_hash (def, REGNO (def)); + struct biv_entry *biv = bivs->find_with_hash (def, REGNO (def)); if (!biv) return false; @@ -869,7 +837,7 @@ static void record_biv (rtx def, struct rtx_iv *iv) { struct biv_entry *biv = XNEW (struct biv_entry); - biv_entry **slot = bivs.find_slot_with_hash (def, REGNO (def), INSERT); + biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT); biv->regno = REGNO (def); biv->iv = *iv; @@ -878,13 +846,13 @@ record_biv (rtx def, struct rtx_iv *iv) } /* Determines whether DEF is a biv and if so, stores its description - to *IV. */ + to *IV. OUTER_MODE is the mode of DEF. */ static bool -iv_analyze_biv (rtx def, struct rtx_iv *iv) +iv_analyze_biv (scalar_int_mode outer_mode, rtx def, struct rtx_iv *iv) { rtx inner_step, outer_step; - enum machine_mode inner_mode, outer_mode; + scalar_int_mode inner_mode; enum iv_extend_code extend; df_ref last_def; @@ -900,7 +868,7 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) if (!CONSTANT_P (def)) return false; - return iv_constant (iv, def, VOIDmode); + return iv_constant (iv, outer_mode, def); } if (!latch_dominating_def (def, &last_def)) @@ -911,7 +879,7 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) } if (!last_def) - return iv_constant (iv, def, VOIDmode); + return iv_constant (iv, outer_mode, def); if (analyzed_for_bivness_p (def, iv)) { @@ -920,8 +888,8 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) return iv->base != NULL_RTX; } - if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend, - &outer_mode, &outer_step)) + if (!get_biv_step (last_def, outer_mode, def, &inner_step, &inner_mode, + &extend, &outer_step)) { iv->base = NULL_RTX; goto end; @@ -958,15 +926,15 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) The mode of the induction variable is MODE. */ bool -iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) +iv_analyze_expr (rtx_insn *insn, scalar_int_mode mode, rtx rhs, + struct rtx_iv *iv) { - rtx mby = NULL_RTX, tmp; + rtx mby = NULL_RTX; rtx op0 = NULL_RTX, op1 = NULL_RTX; struct rtx_iv iv0, iv1; enum rtx_code code = GET_CODE (rhs); - enum machine_mode omode = mode; + scalar_int_mode omode = mode; - iv->mode = VOIDmode; iv->base = NULL_RTX; iv->step = NULL_RTX; @@ -975,18 +943,7 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) if (CONSTANT_P (rhs) || REG_P (rhs) || code == SUBREG) - { - if (!iv_analyze_op (insn, rhs, iv)) - return false; - - if (iv->mode == VOIDmode) - { - iv->mode = mode; - iv->extend_mode = mode; - } - - return true; - } + return iv_analyze_op (insn, mode, rhs, iv); switch (code) { @@ -998,7 +955,9 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) case ZERO_EXTEND: case NEG: op0 = XEXP (rhs, 0); - omode = GET_MODE (op0); + /* We don't know how many bits there are in a sign-extended constant. */ + if (!is_a (GET_MODE (op0), &omode)) + return false; break; case PLUS: @@ -1011,11 +970,7 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) op0 = XEXP (rhs, 0); mby = XEXP (rhs, 1); if (!CONSTANT_P (mby)) - { - tmp = op0; - op0 = mby; - mby = tmp; - } + std::swap (op0, mby); if (!CONSTANT_P (mby)) return false; break; @@ -1032,11 +987,11 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) } if (op0 - && !iv_analyze_expr (insn, op0, omode, &iv0)) + && !iv_analyze_expr (insn, omode, op0, &iv0)) return false; if (op1 - && !iv_analyze_expr (insn, op1, omode, &iv1)) + && !iv_analyze_expr (insn, omode, op1, &iv1)) return false; switch (code) @@ -1085,7 +1040,7 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) static bool iv_analyze_def (df_ref def, struct rtx_iv *iv) { - rtx insn = DF_REF_INSN (def); + rtx_insn *insn = DF_REF_INSN (def); rtx reg = DF_REF_REG (def); rtx set, rhs; @@ -1106,11 +1061,11 @@ iv_analyze_def (df_ref def, struct rtx_iv *iv) return iv->base != NULL_RTX; } - iv->mode = VOIDmode; iv->base = NULL_RTX; iv->step = NULL_RTX; - if (!REG_P (reg)) + scalar_int_mode mode; + if (!REG_P (reg) || !is_a (GET_MODE (reg), &mode)) return false; set = single_set (insn); @@ -1127,7 +1082,7 @@ iv_analyze_def (df_ref def, struct rtx_iv *iv) else rhs = SET_SRC (set); - iv_analyze_expr (insn, rhs, GET_MODE (reg), iv); + iv_analyze_expr (insn, mode, rhs, iv); record_iv (def, iv); if (dump_file) @@ -1143,10 +1098,11 @@ iv_analyze_def (df_ref def, struct rtx_iv *iv) return iv->base != NULL_RTX; } -/* Analyzes operand OP of INSN and stores the result to *IV. */ +/* Analyzes operand OP of INSN and stores the result to *IV. MODE is the + mode of OP. */ static bool -iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) +iv_analyze_op (rtx_insn *insn, scalar_int_mode mode, rtx op, struct rtx_iv *iv) { df_ref def = NULL; enum iv_grd_result res; @@ -1163,13 +1119,15 @@ iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) res = GRD_INVARIANT; else if (GET_CODE (op) == SUBREG) { - if (!subreg_lowpart_p (op)) + scalar_int_mode inner_mode; + if (!subreg_lowpart_p (op) + || !is_a (GET_MODE (SUBREG_REG (op)), &inner_mode)) return false; - if (!iv_analyze_op (insn, SUBREG_REG (op), iv)) + if (!iv_analyze_op (insn, inner_mode, SUBREG_REG (op), iv)) return false; - return iv_subreg (iv, GET_MODE (op)); + return iv_subreg (iv, mode); } else { @@ -1184,7 +1142,7 @@ iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) if (res == GRD_INVARIANT) { - iv_constant (iv, op, VOIDmode); + iv_constant (iv, mode, op); if (dump_file) { @@ -1196,15 +1154,16 @@ iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) } if (res == GRD_MAYBE_BIV) - return iv_analyze_biv (op, iv); + return iv_analyze_biv (mode, op, iv); return iv_analyze_def (def, iv); } -/* Analyzes value VAL at INSN and stores the result to *IV. */ +/* Analyzes value VAL at INSN and stores the result to *IV. MODE is the + mode of VAL. */ bool -iv_analyze (rtx insn, rtx val, struct rtx_iv *iv) +iv_analyze (rtx_insn *insn, scalar_int_mode mode, rtx val, struct rtx_iv *iv) { rtx reg; @@ -1223,13 +1182,13 @@ iv_analyze (rtx insn, rtx val, struct rtx_iv *iv) insn = NEXT_INSN (insn); } - return iv_analyze_op (insn, val, iv); + return iv_analyze_op (insn, mode, val, iv); } /* Analyzes definition of DEF in INSN and stores the result to IV. */ bool -iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv) +iv_analyze_result (rtx_insn *insn, rtx def, struct rtx_iv *iv) { df_ref adef; @@ -1241,11 +1200,13 @@ iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv) } /* Checks whether definition of register REG in INSN is a basic induction - variable. IV analysis must have been initialized (via a call to + variable. MODE is the mode of REG. + + IV analysis must have been initialized (via a call to iv_analysis_loop_init) for this function to produce a result. */ bool -biv_p (rtx insn, rtx reg) +biv_p (rtx_insn *insn, scalar_int_mode mode, rtx reg) { struct rtx_iv iv; df_ref def, last_def; @@ -1260,7 +1221,7 @@ biv_p (rtx insn, rtx reg) if (last_def != def) return false; - if (!iv_analyze_biv (reg, &iv)) + if (!iv_analyze_biv (mode, reg, &iv)) return false; return iv.step != const0_rtx; @@ -1311,7 +1272,8 @@ iv_analysis_done (void) clear_iv_info (); clean_slate = true; df_finish_pass (true); - bivs.dispose (); + delete bivs; + bivs = NULL; free (iv_ref_table); iv_ref_table = NULL; iv_ref_table_size = 0; @@ -1320,12 +1282,12 @@ iv_analysis_done (void) /* Computes inverse to X modulo (1 << MOD). */ -static unsigned HOST_WIDEST_INT -inverse (unsigned HOST_WIDEST_INT x, int mod) +static uint64_t +inverse (uint64_t x, int mod) { - unsigned HOST_WIDEST_INT mask = - ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1; - unsigned HOST_WIDEST_INT rslt = 1; + uint64_t mask = + ((uint64_t) 1 << (mod - 1) << 1) - 1; + uint64_t rslt = 1; int i; for (i = 0; i < mod - 1; i++) @@ -1337,15 +1299,19 @@ inverse (unsigned HOST_WIDEST_INT x, int mod) return rslt; } -/* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */ +/* Checks whether any register in X is in set ALT. */ -static int -altered_reg_used (rtx *reg, void *alt) +static bool +altered_reg_used (const_rtx x, bitmap alt) { - if (!REG_P (*reg)) - return 0; - - return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg)); + subrtx_iterator::array_type array; + FOR_EACH_SUBRTX (iter, array, x, NONCONST) + { + const_rtx x = *iter; + if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x))) + return true; + } + return false; } /* Marks registers altered by EXPR in set ALT. */ @@ -1408,33 +1374,27 @@ simple_rhs_p (rtx rhs) } } -/* If REG has a single definition, replace it with its known value in EXPR. - Callback for for_each_rtx. */ +/* If REGNO has a single definition, return its known value, otherwise return + null. */ -static int -replace_single_def_regs (rtx *reg, void *expr1) +static rtx +find_single_def_src (unsigned int regno) { - unsigned regno; df_ref adef; rtx set, src; - rtx *expr = (rtx *)expr1; - - if (!REG_P (*reg)) - return 0; - regno = REGNO (*reg); for (;;) { rtx note; adef = DF_REG_DEF_CHAIN (regno); if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL - || DF_REF_IS_ARTIFICIAL (adef)) - return -1; + || DF_REF_IS_ARTIFICIAL (adef)) + return NULL_RTX; set = single_set (DF_REF_INSN (adef)); if (set == NULL || !REG_P (SET_DEST (set)) || REGNO (SET_DEST (set)) != regno) - return -1; + return NULL_RTX; note = find_reg_equal_equiv_note (DF_REF_INSN (adef)); @@ -1453,10 +1413,29 @@ replace_single_def_regs (rtx *reg, void *expr1) break; } if (!function_invariant_p (src)) - return -1; + return NULL_RTX; + + return src; +} + +/* If any registers in *EXPR that have a single definition, try to replace + them with the known-equivalent values. */ - *expr = simplify_replace_rtx (*expr, *reg, src); - return 1; +static void +replace_single_def_regs (rtx *expr) +{ + subrtx_var_iterator::array_type array; + repeat: + FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST) + { + rtx x = *iter; + if (REG_P (x)) + if (rtx new_x = find_single_def_src (REGNO (x))) + { + *expr = simplify_replace_rtx (*expr, x, new_x); + goto repeat; + } + } } /* A subroutine of simplify_using_initial_values, this function examines INSN @@ -1465,7 +1444,7 @@ replace_single_def_regs (rtx *reg, void *expr1) the set; return false otherwise. */ static bool -suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src) +suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src) { rtx set = single_set (insn); rtx lhs = NULL_RTX, rhs; @@ -1501,8 +1480,7 @@ replace_in_expr (rtx *expr, rtx dest, rtx src) *expr = simplify_replace_rtx (*expr, dest, src); if (old == *expr) return; - while (for_each_rtx (expr, replace_single_def_regs, expr) != 0) - continue; + replace_single_def_regs (expr); } /* Checks whether A implies B. */ @@ -1510,8 +1488,8 @@ replace_in_expr (rtx *expr, rtx dest, rtx src) static bool implies_p (rtx a, rtx b) { - rtx op0, op1, opb0, opb1, r; - enum machine_mode mode; + rtx op0, op1, opb0, opb1; + machine_mode mode; if (rtx_equal_p (a, b)) return true; @@ -1525,7 +1503,7 @@ implies_p (rtx a, rtx b) || (GET_CODE (op0) == SUBREG && REG_P (SUBREG_REG (op0)))) { - r = simplify_replace_rtx (b, op0, op1); + rtx r = simplify_replace_rtx (b, op0, op1); if (r == const_true_rtx) return true; } @@ -1534,7 +1512,7 @@ implies_p (rtx a, rtx b) || (GET_CODE (op1) == SUBREG && REG_P (SUBREG_REG (op1)))) { - r = simplify_replace_rtx (b, op1, op0); + rtx r = simplify_replace_rtx (b, op1, op0); if (r == const_true_rtx) return true; } @@ -1570,18 +1548,10 @@ implies_p (rtx a, rtx b) { if (GET_CODE (a) == GT) - { - r = op0; - op0 = op1; - op1 = r; - } + std::swap (op0, op1); if (GET_CODE (b) == GE) - { - r = opb0; - opb0 = opb1; - opb1 = r; - } + std::swap (opb0, opb1); if (SCALAR_INT_MODE_P (mode) && rtx_equal_p (op1, opb1) @@ -1636,7 +1606,7 @@ implies_p (rtx a, rtx b) && CONST_INT_P (XEXP (opb0, 1)) /* Avoid overflows. */ && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) - != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))) + != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1))) && rtx_equal_p (XEXP (opb0, 0), op0)) return INTVAL (op1) == -INTVAL (XEXP (opb0, 1)); if (GET_CODE (b) == GEU @@ -1645,7 +1615,7 @@ implies_p (rtx a, rtx b) && CONST_INT_P (XEXP (opb0, 1)) /* Avoid overflows. */ && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) - != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))) + != (HOST_WIDE_INT_1U << (HOST_BITS_PER_WIDE_INT - 1))) && rtx_equal_p (XEXP (opb0, 0), op0)) return INTVAL (op1) == -INTVAL (XEXP (opb0, 1)); } @@ -1673,10 +1643,9 @@ implies_p (rtx a, rtx b) rtx canon_condition (rtx cond) { - rtx tem; rtx op0, op1; enum rtx_code code; - enum machine_mode mode; + machine_mode mode; code = GET_CODE (cond); op0 = XEXP (cond, 0); @@ -1685,9 +1654,7 @@ canon_condition (rtx cond) if (swap_commutative_operands_p (op0, op1)) { code = swap_condition (code); - tem = op0; - op0 = op1; - op1 = tem; + std::swap (op0, op1); } mode = GET_MODE (op0); @@ -1695,39 +1662,42 @@ canon_condition (rtx cond) mode = GET_MODE (op1); gcc_assert (mode != VOIDmode); - if (CONST_INT_P (op1) - && GET_MODE_CLASS (mode) != MODE_CC - && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT) + if (CONST_SCALAR_INT_P (op1) && GET_MODE_CLASS (mode) != MODE_CC) { - 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 (mode); + rtx_mode_t const_val (op1, mode); 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)); + if (wi::ne_p (const_val, wi::max_value (mode, SIGNED))) + { + code = LT; + op1 = immed_wide_int_const (wi::add (const_val, 1), mode); + } 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, mode); + if (wi::ne_p (const_val, wi::min_value (mode, SIGNED))) + { + code = GT; + op1 = immed_wide_int_const (wi::sub (const_val, 1), mode); + } break; case LEU: - if (uconst_val < max_val) - code = LTU, op1 = gen_int_mode (uconst_val + 1, mode); + if (wi::ne_p (const_val, -1)) + { + code = LTU; + op1 = immed_wide_int_const (wi::add (const_val, 1), mode); + } break; case GEU: - if (uconst_val != 0) - code = GTU, op1 = gen_int_mode (uconst_val - 1, mode); + if (wi::ne_p (const_val, 0)) + { + code = GTU; + op1 = immed_wide_int_const (wi::sub (const_val, 1), mode); + } break; default: @@ -1744,6 +1714,21 @@ canon_condition (rtx cond) return cond; } +/* Reverses CONDition; returns NULL if we cannot. */ + +static rtx +reversed_condition (rtx cond) +{ + enum rtx_code reversed; + reversed = reversed_comparison_code (cond, NULL); + if (reversed == UNKNOWN) + return NULL_RTX; + else + return gen_rtx_fmt_ee (reversed, + GET_MODE (cond), XEXP (cond, 0), + XEXP (cond, 1)); +} + /* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the set of altered regs. */ @@ -1754,8 +1739,7 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered) /* If some register gets altered later, we do not really speak about its value at the time of comparison. */ - if (altered - && for_each_rtx (&cond, altered_reg_used, altered)) + if (altered && altered_reg_used (cond, altered)) return; if (GET_CODE (cond) == EQ @@ -1868,7 +1852,9 @@ static void simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) { bool expression_valid; - rtx head, tail, insn, cond_list, last_valid_expr; + rtx head, tail, last_valid_expr; + rtx_expr_list *cond_list; + rtx_insn *insn; rtx neutral, aggr; regset altered, this_altered; edge e; @@ -1930,14 +1916,12 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) gcc_assert (op == UNKNOWN); - for (;;) - if (for_each_rtx (expr, replace_single_def_regs, expr) == 0) - break; + replace_single_def_regs (expr); if (CONSTANT_P (*expr)) return; e = loop_preheader_edge (loop); - if (e->src == ENTRY_BLOCK_PTR) + if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun)) return; altered = ALLOC_REG_SET (®_obstack); @@ -1945,7 +1929,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) expression_valid = true; last_valid_expr = *expr; - cond_list = NULL_RTX; + cond_list = NULL; while (1) { insn = BB_END (e->src); @@ -1997,7 +1981,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) if (suitable_set_for_replacement (insn, &dest, &src)) { - rtx *pnote, *pnote_next; + rtx_expr_list **pnote, **pnote_next; replace_in_expr (expr, dest, src); if (CONSTANT_P (*expr)) @@ -2005,10 +1989,10 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) for (pnote = &cond_list; *pnote; pnote = pnote_next) { - rtx note = *pnote; + rtx_expr_list *note = *pnote; rtx old_cond = XEXP (note, 0); - pnote_next = &XEXP (note, 1); + pnote_next = (rtx_expr_list **)&XEXP (note, 1); replace_in_expr (&XEXP (note, 0), dest, src); /* We can no longer use a condition that has been simplified @@ -2028,22 +2012,22 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) } else { - rtx *pnote, *pnote_next; + rtx_expr_list **pnote, **pnote_next; /* If we did not use this insn to make a replacement, any overlap between stores in this insn and our expression will cause the expression to become invalid. */ - if (for_each_rtx (expr, altered_reg_used, this_altered)) + if (altered_reg_used (*expr, this_altered)) goto out; /* Likewise for the conditions. */ for (pnote = &cond_list; *pnote; pnote = pnote_next) { - rtx note = *pnote; + rtx_expr_list *note = *pnote; rtx old_cond = XEXP (note, 0); - pnote_next = &XEXP (note, 1); - if (for_each_rtx (&old_cond, altered_reg_used, this_altered)) + pnote_next = (rtx_expr_list **)&XEXP (note, 1); + if (altered_reg_used (old_cond, this_altered)) { *pnote = *pnote_next; pnote_next = pnote; @@ -2061,14 +2045,14 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) can't return it to the caller. However, it is still valid for further simplification, so keep searching to see if we can eventually turn it into a constant. */ - if (for_each_rtx (expr, altered_reg_used, altered)) + if (altered_reg_used (*expr, altered)) expression_valid = false; if (expression_valid) last_valid_expr = *expr; } if (!single_pred_p (e->src) - || single_pred (e->src) == ENTRY_BLOCK_PTR) + || single_pred (e->src) == ENTRY_BLOCK_PTR_FOR_FN (cfun)) break; e = single_pred_edge (e->src); } @@ -2086,7 +2070,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) is SIGNED_P to DESC. */ static void -shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode, +shorten_into_mode (struct rtx_iv *iv, scalar_int_mode mode, enum rtx_code cond, bool signed_p, struct niter_desc *desc) { rtx mmin, mmax, cond_over, cond_under; @@ -2148,7 +2132,7 @@ static bool canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code cond, struct niter_desc *desc) { - enum machine_mode comp_mode; + scalar_int_mode comp_mode; bool signed_p; /* If the ivs behave specially in the first iteration, or are @@ -2260,13 +2244,13 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, a number of fields in DESC already filled in. OLD_NITER is the original expression for the number of iterations, before we tried to simplify it. */ -static unsigned HOST_WIDEST_INT +static uint64_t determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter) { rtx niter = desc->niter_expr; rtx mmin, mmax, cmp; - unsigned HOST_WIDEST_INT nmax, inc; - unsigned HOST_WIDEST_INT andmax = 0; + uint64_t nmax, inc; + uint64_t andmax = 0; /* We used to look for constant operand 0 of AND, but canonicalization should always make this impossible. */ @@ -2281,7 +2265,7 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter) } get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); - nmax = INTVAL (mmax) - INTVAL (mmin); + nmax = UINTVAL (mmax) - UINTVAL (mmin); if (GET_CODE (niter) == UDIV) { @@ -2309,7 +2293,7 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter) if (andmax) nmax = MIN (nmax, andmax); if (dump_file) - fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n", + fprintf (dump_file, ";; Determined upper bound %" PRId64".\n", nmax); return nmax; } @@ -2319,17 +2303,18 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter) (basically its rtl version), complicated by things like subregs. */ static void -iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, +iv_number_of_iterations (struct loop *loop, rtx_insn *insn, rtx condition, struct niter_desc *desc) { rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1; - struct rtx_iv iv0, iv1, tmp_iv; + struct rtx_iv iv0, iv1; rtx assumption, may_not_xform; enum rtx_code cond; - enum machine_mode mode, comp_mode; + machine_mode nonvoid_mode; + scalar_int_mode comp_mode; rtx mmin, mmax, mode_mmin, mode_mmax; - unsigned HOST_WIDEST_INT s, size, d, inv, max; - HOST_WIDEST_INT up, down, inc, step_val; + uint64_t s, size, d, inv, max, up, down; + int64_t inc, step_val; int was_sharp = false; rtx old_niter; bool step_is_pow2; @@ -2351,28 +2336,24 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, cond = GET_CODE (condition); gcc_assert (COMPARISON_P (condition)); - mode = GET_MODE (XEXP (condition, 0)); - if (mode == VOIDmode) - mode = GET_MODE (XEXP (condition, 1)); + nonvoid_mode = GET_MODE (XEXP (condition, 0)); + if (nonvoid_mode == VOIDmode) + nonvoid_mode = GET_MODE (XEXP (condition, 1)); /* The constant comparisons should be folded. */ - gcc_assert (mode != VOIDmode); + gcc_assert (nonvoid_mode != VOIDmode); /* We only handle integers or pointers. */ - if (GET_MODE_CLASS (mode) != MODE_INT - && GET_MODE_CLASS (mode) != MODE_PARTIAL_INT) + scalar_int_mode mode; + if (!is_a (nonvoid_mode, &mode)) goto fail; op0 = XEXP (condition, 0); - if (!iv_analyze (insn, op0, &iv0)) + if (!iv_analyze (insn, mode, op0, &iv0)) goto fail; - if (iv0.extend_mode == VOIDmode) - iv0.mode = iv0.extend_mode = mode; op1 = XEXP (condition, 1); - if (!iv_analyze (insn, op1, &iv1)) + if (!iv_analyze (insn, mode, op1, &iv1)) goto fail; - if (iv1.extend_mode == VOIDmode) - iv1.mode = iv1.extend_mode = mode; if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT || GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT) @@ -2386,7 +2367,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, case GT: case GEU: case GTU: - tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv; + std::swap (iv0, iv1); cond = swap_condition (cond); break; case NE: @@ -2409,7 +2390,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, comp_mode = iv0.extend_mode; mode = iv0.mode; - size = GET_MODE_BITSIZE (mode); + size = GET_MODE_PRECISION (mode); get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax); mode_mmin = lowpart_subreg (mode, mmin, comp_mode); mode_mmax = lowpart_subreg (mode, mmax, comp_mode); @@ -2676,7 +2657,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, d *= 2; size--; } - bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1); + bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1); tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode)); @@ -2830,7 +2811,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, if (CONST_INT_P (desc->niter_expr)) { - unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr); + uint64_t val = INTVAL (desc->niter_expr); desc->const_iter = true; desc->niter = val & GET_MODE_MASK (desc->mode); @@ -2887,7 +2868,8 @@ static void check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc) { basic_block exit_bb; - rtx condition, at; + rtx condition; + rtx_insn *at; edge ein; exit_bb = e->src; @@ -3006,6 +2988,8 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc) fprintf (dump_file, " upper bound: %li\n", (long)get_max_loop_iterations_int (loop)); + fprintf (dump_file, " likely upper bound: %li\n", + (long)get_likely_max_loop_iterations_int (loop)); fprintf (dump_file, " realistic bound: %li\n", (long)get_estimated_loop_iterations_int (loop)); } @@ -3029,46 +3013,10 @@ get_simple_loop_desc (struct loop *loop) /* At least desc->infinite is not always initialized by find_simple_loop_exit. */ - desc = ggc_alloc_cleared_niter_desc (); + desc = ggc_cleared_alloc (); iv_analysis_loop_init (loop); find_simple_exit (loop, desc); loop->simple_loop_desc = desc; - - if (desc->simple_p && (desc->assumptions || desc->infinite)) - { - const char *wording; - - /* Assume that no overflow happens and that the loop is finite. - We already warned at the tree level if we ran optimizations there. */ - if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations) - { - if (desc->infinite) - { - wording = - flag_unsafe_loop_optimizations - ? N_("assuming that the loop is not infinite") - : N_("cannot optimize possibly infinite loops"); - warning (OPT_Wunsafe_loop_optimizations, "%s", - gettext (wording)); - } - if (desc->assumptions) - { - wording = - flag_unsafe_loop_optimizations - ? N_("assuming that the loop counter does not overflow") - : N_("cannot optimize loop, the loop counter may overflow"); - warning (OPT_Wunsafe_loop_optimizations, "%s", - gettext (wording)); - } - } - - if (flag_unsafe_loop_optimizations) - { - desc->assumptions = NULL_RTX; - desc->infinite = NULL_RTX; - } - } - return desc; }