X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Floop-iv.c;h=00c82943642e7238268d319d989a1349813bab38;hb=238ac4b8fddfe2eccaf0feada01beebc8746a3c8;hp=55faf4a7097fd3e2d04c3ef3c3fc27b6fc25ab05;hpb=ea091dfdfe023dacb0c7c2af37bdd75e23c530f4;p=pf3gnuchains%2Fgcc-fork.git diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c index 55faf4a7097..00c82943642 100644 --- a/gcc/loop-iv.c +++ b/gcc/loop-iv.c @@ -15,37 +15,38 @@ for more details. You should have received a copy of the GNU General Public License along with GCC; see the file COPYING. If not, write to the Free -Software Foundation, 59 Temple Place - Suite 330, Boston, MA -02111-1307, USA. */ - -/* This is just a very simplistic analysis of induction variables of the loop. - The major use is for determining the number of iterations of a loop for - loop unrolling, doloop optimization and branch prediction. For this we - are only interested in bivs and a fairly limited set of givs that are - needed in the exit condition. We also only compute the iv information on - demand. - - The interesting registers are determined. A register is interesting if - - -- it is set only in the blocks that dominate the latch of the current loop - -- all its sets are simple -- i.e. in the form we understand - - We also number the insns sequentially in each basic block. For a use of the - interesting reg, it is now easy to find a reaching definition (there may be - only one). - - Induction variable is then simply analyzed by walking the use-def - chains. - - Usage: - - iv_analysis_loop_init (loop); - insn = iv_get_reaching_def (where, reg); - if (iv_analyze (insn, reg, &iv)) - { - ... - } - iv_analysis_done (); */ +Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA +02110-1301, USA. */ + +/* This is a simple analysis of induction variables of the loop. The major use + is for determining the number of iterations of a loop for loop unrolling, + doloop optimization and branch prediction. The iv information is computed + on demand. + + Induction variable is analyzed by walking the use-def chains. When a biv + is found, it is cached in the bivs hash table. When register is proved + to be a giv, its description is stored to DF_REF_DATA of the def reference. + + The analysis works always with one loop -- you must call + iv_analysis_loop_init (loop) for it. All the other functions then work with + this loop. When you need to work with another loop, just call + iv_analysis_loop_init for it. When you no longer need iv analysis, call + iv_analysis_done () to clean up the memory. + + 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_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 + corresponding to expression EXPR evaluated at INSN. All registers used bu + EXPR must also be used in INSN. + iv_current_loop_df (): Returns the dataflow object for the current loop used + by iv analysis. */ #include "config.h" #include "system.h" @@ -57,41 +58,64 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA #include "basic-block.h" #include "cfgloop.h" #include "expr.h" +#include "intl.h" #include "output.h" +#include "toplev.h" +#include "df.h" +#include "hashtab.h" -/* The insn information. */ +/* Possible return values of iv_get_reaching_def. */ -struct insn_info +enum iv_grd_result { - /* Id of the insn. */ - unsigned luid; + /* More than one reaching def, or reaching def that does not + dominate the use. */ + GRD_INVALID, - /* The previous definition of the register defined by the single - set in the insn. */ - rtx prev_def; + /* The use is trivial invariant of the loop, i.e. is not changed + inside the loop. */ + GRD_INVARIANT, - /* The description of the iv. */ - struct rtx_iv iv; + /* The use is reached by initial value and a value from the + previous iteration. */ + GRD_MAYBE_BIV, + + /* The use has single dominating def. */ + GRD_SINGLE_DOM }; -static struct insn_info *insn_info; +/* Information about a biv. */ -/* The last definition of register. */ +struct biv_entry +{ + unsigned regno; /* The register of the biv. */ + struct rtx_iv iv; /* Value of the biv. */ +}; + +/* Induction variable stored at the reference. */ +#define DF_REF_IV(REF) ((struct rtx_iv *) DF_REF_DATA (REF)) +#define DF_REF_IV_SET(REF, IV) DF_REF_DATA (REF) = (IV) + +/* The current loop. */ -static rtx *last_def; +static struct loop *current_loop; -/* The bivs. */ +/* Dataflow information for the current loop. */ -static struct rtx_iv *bivs; +static struct df *df = NULL; -/* Maximal insn number for that there is place in insn_info array. */ +/* Bivs of the current loop. */ -static unsigned max_insn_no; +static htab_t bivs; -/* Maximal register number for that there is place in bivs and last_def - arrays. */ +/* Return the dataflow object for the current loop. */ +struct df * +iv_current_loop_df (void) +{ + return df; +} -static unsigned max_reg_no; +static bool iv_analyze_op (rtx, rtx, struct rtx_iv *); /* Dumps information about IV to FILE. */ @@ -137,23 +161,6 @@ dump_iv_info (FILE *file, struct rtx_iv *iv) fprintf (file, " (first special)"); } -/* Assigns luids to insns in basic block BB. */ - -static void -assign_luids (basic_block bb) -{ - unsigned i = 0, uid; - rtx insn; - - FOR_BB_INSNS (bb, insn) - { - uid = INSN_UID (insn); - insn_info[uid].luid = i++; - insn_info[uid].prev_def = NULL_RTX; - insn_info[uid].iv.analysed = false; - } -} - /* Generates a subreg to get the least significant part of EXPR (in mode INNER_MODE) to OUTER_MODE. */ @@ -189,131 +196,45 @@ simple_reg_p (rtx reg) if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT) return false; - if (last_def[r] == const0_rtx) - return false; - return true; } -/* Checks whether assignment LHS = RHS is simple enough for us to process. */ +/* Clears the information about ivs stored in df. */ -static bool -simple_set_p (rtx lhs, rtx rhs) +static void +clear_iv_info (void) { - rtx op0, op1; + unsigned i, n_defs = DF_DEFS_SIZE (df); + struct rtx_iv *iv; + struct df_ref *def; - if (!REG_P (lhs) - || !simple_reg_p (lhs)) - return false; - - if (CONSTANT_P (rhs)) - return true; - - switch (GET_CODE (rhs)) + for (i = 0; i < n_defs; i++) { - case SUBREG: - case REG: - return simple_reg_p (rhs); - - case SIGN_EXTEND: - case ZERO_EXTEND: - case NEG: - return simple_reg_p (XEXP (rhs, 0)); - - case PLUS: - case MINUS: - case MULT: - case ASHIFT: - op0 = XEXP (rhs, 0); - op1 = XEXP (rhs, 1); - - if (!simple_reg_p (op0) - && !CONSTANT_P (op0)) - return false; - - if (!simple_reg_p (op1) - && !CONSTANT_P (op1)) - return false; - - if (GET_CODE (rhs) == MULT - && !CONSTANT_P (op0) - && !CONSTANT_P (op1)) - return false; - - if (GET_CODE (rhs) == ASHIFT - && CONSTANT_P (op0)) - return false; - - return true; - - default: - return false; + def = DF_DEFS_GET (df, i); + iv = DF_REF_IV (def); + if (!iv) + continue; + free (iv); + DF_REF_IV_SET (def, NULL); } -} - -/* Mark single SET in INSN. */ - -static rtx -mark_single_set (rtx insn, rtx set) -{ - rtx def = SET_DEST (set), src; - unsigned regno, uid; - - src = find_reg_equal_equiv_note (insn); - if (src) - src = XEXP (src, 0); - else - src = SET_SRC (set); - - if (!simple_set_p (SET_DEST (set), src)) - return NULL_RTX; - - regno = REGNO (def); - uid = INSN_UID (insn); - bivs[regno].analysed = false; - insn_info[uid].prev_def = last_def[regno]; - last_def[regno] = insn; - - return def; + htab_empty (bivs); } -/* Invalidate register REG unless it is equal to EXCEPT. */ +/* Returns hash value for biv B. */ -static void -kill_sets (rtx reg, rtx by ATTRIBUTE_UNUSED, void *except) +static hashval_t +biv_hash (const void *b) { - if (GET_CODE (reg) == SUBREG) - reg = SUBREG_REG (reg); - if (!REG_P (reg)) - return; - if (reg == except) - return; - - last_def[REGNO (reg)] = const0_rtx; + return ((const struct biv_entry *) b)->regno; } -/* Marks sets in basic block BB. If DOM is true, BB dominates the loop - latch. */ +/* Compares biv B and register R. */ -static void -mark_sets (basic_block bb, bool dom) +static int +biv_eq (const void *b, const void *r) { - rtx insn, set, def; - - FOR_BB_INSNS (bb, insn) - { - if (!INSN_P (insn)) - continue; - - if (dom - && (set = single_set (insn))) - def = mark_single_set (insn, set); - else - def = NULL_RTX; - - note_stores (PATTERN (insn), kill_sets, def); - } + return ((const struct biv_entry *) b)->regno == REGNO ((rtx) r); } /* Prepare the data for an induction variable analysis of a LOOP. */ @@ -321,97 +242,116 @@ mark_sets (basic_block bb, bool dom) void iv_analysis_loop_init (struct loop *loop) { - basic_block *body = get_loop_body_in_dom_order (loop); - unsigned b; + basic_block *body = get_loop_body_in_dom_order (loop), bb; + bitmap blocks = BITMAP_ALLOC (NULL); + unsigned i; + bool first_time = (df == NULL); - if ((unsigned) get_max_uid () >= max_insn_no) - { - /* Add some reserve for insns and registers produced in optimizations. */ - max_insn_no = get_max_uid () + 100; - if (insn_info) - free (insn_info); - insn_info = xmalloc (max_insn_no * sizeof (struct insn_info)); - } + current_loop = loop; - if ((unsigned) max_reg_num () >= max_reg_no) + /* Clear the information from the analysis of the previous loop. */ + if (first_time) { - max_reg_no = max_reg_num () + 100; - if (last_def) - free (last_def); - last_def = xmalloc (max_reg_no * sizeof (rtx)); - if (bivs) - free (bivs); - bivs = xmalloc (max_reg_no * sizeof (struct rtx_iv)); + df = df_init (DF_HARD_REGS | DF_EQUIV_NOTES); + df_chain_add_problem (df, DF_UD_CHAIN); + bivs = htab_create (10, biv_hash, biv_eq, free); } + else + clear_iv_info (); - memset (last_def, 0, max_reg_num () * sizeof (rtx)); - - for (b = 0; b < loop->num_nodes; b++) + for (i = 0; i < loop->num_nodes; i++) { - assign_luids (body[b]); - mark_sets (body[b], just_once_each_iteration_p (loop, body[b])); + bb = body[i]; + bitmap_set_bit (blocks, bb->index); } - + df_set_blocks (df, blocks); + df_analyze (df); + BITMAP_FREE (blocks); free (body); } -/* Gets definition of REG reaching the INSN. If REG is not simple, const0_rtx - is returned. If INSN is before the first def in the loop, NULL_RTX is - returned. */ +/* Finds the definition of REG that dominates loop latch and stores + it to DEF. Returns false if there is not a single definition + dominating the latch. If REG has no definition in loop, DEF + is set to NULL and true is returned. */ -rtx -iv_get_reaching_def (rtx insn, rtx reg) +static bool +latch_dominating_def (rtx reg, struct df_ref **def) { - unsigned regno, luid, auid; - rtx ainsn; - basic_block bb, abb; + struct df_ref *single_rd = NULL, *adef; + unsigned regno = REGNO (reg); + struct df_reg_info *reg_info = DF_REG_DEF_GET (df, regno); + struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (df, current_loop->latch); - if (GET_CODE (reg) == SUBREG) + for (adef = reg_info->reg_chain; adef; adef = adef->next_reg) { - if (!subreg_lowpart_p (reg)) - return const0_rtx; - reg = SUBREG_REG (reg); + if (!bitmap_bit_p (bb_info->out, DF_REF_ID (adef))) + continue; + + /* More than one reaching definition. */ + if (single_rd) + return false; + + if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef))) + return false; + + single_rd = adef; } - if (!REG_P (reg)) - return NULL_RTX; - regno = REGNO (reg); - if (!last_def[regno] - || last_def[regno] == const0_rtx) - return last_def[regno]; + *def = single_rd; + return true; +} - bb = BLOCK_FOR_INSN (insn); - luid = insn_info[INSN_UID (insn)].luid; +/* Gets definition of REG reaching its use in INSN and stores it to DEF. */ - ainsn = last_def[regno]; - while (1) - { - abb = BLOCK_FOR_INSN (ainsn); +static enum iv_grd_result +iv_get_reaching_def (rtx insn, rtx reg, struct df_ref **def) +{ + struct df_ref *use, *adef; + basic_block def_bb, use_bb; + rtx def_insn; + bool dom_p; + + *def = NULL; + if (!simple_reg_p (reg)) + return GRD_INVALID; + if (GET_CODE (reg) == SUBREG) + reg = SUBREG_REG (reg); + gcc_assert (REG_P (reg)); - if (dominated_by_p (CDI_DOMINATORS, bb, abb)) - break; + use = df_find_use (df, insn, reg); + gcc_assert (use != NULL); - auid = INSN_UID (ainsn); - ainsn = insn_info[auid].prev_def; + if (!DF_REF_CHAIN (use)) + return GRD_INVARIANT; - if (!ainsn) - return NULL_RTX; - } + /* More than one reaching def. */ + if (DF_REF_CHAIN (use)->next) + return GRD_INVALID; - while (1) - { - abb = BLOCK_FOR_INSN (ainsn); - if (abb != bb) - return ainsn; + adef = DF_REF_CHAIN (use)->ref; + def_insn = DF_REF_INSN (adef); + def_bb = DF_REF_BB (adef); + use_bb = BLOCK_FOR_INSN (insn); - auid = INSN_UID (ainsn); - if (luid > insn_info[auid].luid) - return ainsn; + if (use_bb == def_bb) + dom_p = (DF_INSN_LUID (df, def_insn) < DF_INSN_LUID (df, insn)); + else + dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb); - ainsn = insn_info[auid].prev_def; - if (!ainsn) - return NULL_RTX; + if (dom_p) + { + *def = adef; + return GRD_SINGLE_DOM; } + + /* The definition does not dominate the use. This is still OK if + this may be a use of a biv, i.e. if the def_bb dominates loop + latch. */ + if (just_once_each_iteration_p (current_loop, def_bb)) + return GRD_MAYBE_BIV; + + return GRD_INVALID; } /* Sets IV to invariant CST in MODE. Always returns true (just for @@ -423,7 +363,6 @@ iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode) if (mode == VOIDmode) mode = GET_MODE (cst); - iv->analysed = true; iv->mode = mode; iv->base = cst; iv->step = const0_rtx; @@ -651,20 +590,26 @@ iv_shift (struct rtx_iv *iv, rtx mby) } /* The recursive part of get_biv_step. Gets the value of the single value - defined in INSN wrto initial value of REG inside loop, in shape described + defined by DEF wrto initial value of REG inside loop, in shape described at get_biv_step. */ static bool -get_biv_step_1 (rtx insn, rtx reg, +get_biv_step_1 (struct df_ref *def, rtx reg, rtx *inner_step, enum machine_mode *inner_mode, enum rtx_code *extend, enum machine_mode outer_mode, rtx *outer_step) { rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX; - rtx next, nextr, def_insn, tmp; + rtx next, nextr, tmp; enum rtx_code code; + rtx insn = DF_REF_INSN (def); + struct df_ref *next_def; + enum iv_grd_result res; set = single_set (insn); + if (!set) + return false; + rhs = find_reg_equal_equiv_note (insn); if (rhs) rhs = XEXP (rhs, 0); @@ -740,11 +685,12 @@ get_biv_step_1 (rtx insn, rtx reg, else nextr = next; - def_insn = iv_get_reaching_def (insn, nextr); - if (def_insn == const0_rtx) + res = iv_get_reaching_def (insn, nextr, &next_def); + + if (res == GRD_INVALID || res == GRD_INVARIANT) return false; - if (!def_insn) + if (res == GRD_MAYBE_BIV) { if (!rtx_equal_p (nextr, reg)) return false; @@ -754,7 +700,7 @@ get_biv_step_1 (rtx insn, rtx reg, *inner_mode = outer_mode; *outer_step = const0_rtx; } - else if (!get_biv_step_1 (def_insn, reg, + else if (!get_biv_step_1 (next_def, reg, inner_step, inner_mode, extend, outer_mode, outer_step)) return false; @@ -793,16 +739,15 @@ get_biv_step_1 (rtx insn, rtx reg, case SIGN_EXTEND: case ZERO_EXTEND: - if (GET_MODE (op0) != *inner_mode - || *extend != UNKNOWN - || *outer_step != const0_rtx) - abort (); + gcc_assert (GET_MODE (op0) == *inner_mode + && *extend == UNKNOWN + && *outer_step == const0_rtx); *extend = code; break; default: - abort (); + return false; } return true; @@ -812,49 +757,79 @@ get_biv_step_1 (rtx insn, rtx reg, OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP)) - If the operation cannot be described in this shape, return false. */ + If the operation cannot be described in this shape, return false. + LAST_DEF is the definition of REG that dominates loop latch. */ static bool -get_biv_step (rtx reg, rtx *inner_step, enum machine_mode *inner_mode, - enum rtx_code *extend, enum machine_mode *outer_mode, - rtx *outer_step) +get_biv_step (struct df_ref *last_def, rtx reg, rtx *inner_step, + enum machine_mode *inner_mode, enum rtx_code *extend, + enum machine_mode *outer_mode, rtx *outer_step) { *outer_mode = GET_MODE (reg); - if (!get_biv_step_1 (last_def[REGNO (reg)], reg, + if (!get_biv_step_1 (last_def, reg, inner_step, inner_mode, extend, *outer_mode, outer_step)) return false; - if (*inner_mode != *outer_mode - && *extend == UNKNOWN) - abort (); + gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN)); + gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx); + + return true; +} + +/* Records information that DEF is induction variable IV. */ + +static void +record_iv (struct df_ref *def, struct rtx_iv *iv) +{ + struct rtx_iv *recorded_iv = XNEW (struct rtx_iv); + + *recorded_iv = *iv; + DF_REF_IV_SET (def, recorded_iv); +} + +/* If DEF was already analyzed for bivness, store the description of the biv to + IV and return true. Otherwise return false. */ - if (*inner_mode == *outer_mode - && *extend != UNKNOWN) - abort (); +static bool +analyzed_for_bivness_p (rtx def, struct rtx_iv *iv) +{ + struct biv_entry *biv = htab_find_with_hash (bivs, def, REGNO (def)); - if (*inner_mode == *outer_mode - && *outer_step != const0_rtx) - abort (); + if (!biv) + return false; + *iv = biv->iv; return true; } +static void +record_biv (rtx def, struct rtx_iv *iv) +{ + struct biv_entry *biv = XNEW (struct biv_entry); + void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT); + + biv->regno = REGNO (def); + biv->iv = *iv; + gcc_assert (!*slot); + *slot = biv; +} + /* Determines whether DEF is a biv and if so, stores its description to *IV. */ static bool iv_analyze_biv (rtx def, struct rtx_iv *iv) { - unsigned regno; rtx inner_step, outer_step; enum machine_mode inner_mode, outer_mode; enum rtx_code extend; + struct df_ref *last_def; if (dump_file) { - fprintf (dump_file, "Analysing "); + fprintf (dump_file, "Analyzing "); print_rtl (dump_file, def); fprintf (dump_file, " for bivness.\n"); } @@ -867,31 +842,24 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) return iv_constant (iv, def, VOIDmode); } - regno = REGNO (def); - if (last_def[regno] == const0_rtx) + if (!latch_dominating_def (def, &last_def)) { if (dump_file) fprintf (dump_file, " not simple.\n"); return false; } - if (last_def[regno] && bivs[regno].analysed) + if (!last_def) + return iv_constant (iv, def, VOIDmode); + + if (analyzed_for_bivness_p (def, iv)) { if (dump_file) fprintf (dump_file, " already analysed.\n"); - - *iv = bivs[regno]; return iv->base != NULL_RTX; } - if (!last_def[regno]) - { - iv_constant (iv, def, VOIDmode); - goto end; - } - - iv->analysed = true; - if (!get_biv_step (def, &inner_step, &inner_mode, &extend, + if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend, &outer_mode, &outer_step)) { iv->base = NULL_RTX; @@ -921,119 +889,154 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv) fprintf (dump_file, "\n"); } - bivs[regno] = *iv; - + record_biv (def, iv); return iv->base != NULL_RTX; } -/* Analyzes operand OP of INSN and stores the result to *IV. */ +/* Analyzes expression RHS used at INSN and stores the result to *IV. + The mode of the induction variable is MODE. */ -static bool -iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) +bool +iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv) { - rtx def_insn; - unsigned regno; - bool inv = CONSTANT_P (op); - - if (dump_file) - { - fprintf (dump_file, "Analysing operand "); - print_rtl (dump_file, op); - fprintf (dump_file, " of insn "); - print_rtl_single (dump_file, insn); - } - - if (GET_CODE (op) == SUBREG) - { - if (!subreg_lowpart_p (op)) - return false; + rtx mby = NULL_RTX, tmp; + rtx op0 = NULL_RTX, op1 = NULL_RTX; + struct rtx_iv iv0, iv1; + enum rtx_code code = GET_CODE (rhs); + enum machine_mode omode = mode; - if (!iv_analyze_op (insn, SUBREG_REG (op), iv)) - return false; + iv->mode = VOIDmode; + iv->base = NULL_RTX; + iv->step = NULL_RTX; - return iv_subreg (iv, GET_MODE (op)); - } + gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode); - if (!inv) + if (CONSTANT_P (rhs) + || REG_P (rhs) + || code == SUBREG) { - regno = REGNO (op); - if (!last_def[regno]) - inv = true; - else if (last_def[regno] == const0_rtx) + if (!iv_analyze_op (insn, rhs, iv)) + return false; + + if (iv->mode == VOIDmode) { - if (dump_file) - fprintf (dump_file, " not simple.\n"); - return false; + iv->mode = mode; + iv->extend_mode = mode; } + + return true; } - if (inv) + switch (code) { - iv_constant (iv, op, VOIDmode); + case REG: + op0 = rhs; + break; - if (dump_file) + case SIGN_EXTEND: + case ZERO_EXTEND: + case NEG: + op0 = XEXP (rhs, 0); + omode = GET_MODE (op0); + break; + + case PLUS: + case MINUS: + op0 = XEXP (rhs, 0); + op1 = XEXP (rhs, 1); + break; + + case MULT: + op0 = XEXP (rhs, 0); + mby = XEXP (rhs, 1); + if (!CONSTANT_P (mby)) { - fprintf (dump_file, " "); - dump_iv_info (dump_file, iv); - fprintf (dump_file, "\n"); + tmp = op0; + op0 = mby; + mby = tmp; } - return true; - } + if (!CONSTANT_P (mby)) + return false; + break; - def_insn = iv_get_reaching_def (insn, op); - if (def_insn == const0_rtx) - { - if (dump_file) - fprintf (dump_file, " not simple.\n"); + case ASHIFT: + op0 = XEXP (rhs, 0); + mby = XEXP (rhs, 1); + if (!CONSTANT_P (mby)) + return false; + break; + + default: return false; } - return iv_analyze (def_insn, op, iv); -} - -/* Analyzes iv DEF defined in INSN and stores the result to *IV. */ - -bool -iv_analyze (rtx insn, rtx def, struct rtx_iv *iv) -{ - unsigned uid; - rtx set, rhs, mby = NULL_RTX, tmp; - rtx op0 = NULL_RTX, op1 = NULL_RTX; - struct rtx_iv iv0, iv1; - enum machine_mode amode; - enum rtx_code code; + if (op0 + && !iv_analyze_expr (insn, op0, omode, &iv0)) + return false; - if (insn == const0_rtx) + if (op1 + && !iv_analyze_expr (insn, op1, omode, &iv1)) return false; - if (GET_CODE (def) == SUBREG) + switch (code) { - if (!subreg_lowpart_p (def)) + case SIGN_EXTEND: + case ZERO_EXTEND: + if (!iv_extend (&iv0, code, mode)) + return false; + break; + + case NEG: + if (!iv_neg (&iv0)) + return false; + break; + + case PLUS: + case MINUS: + if (!iv_add (&iv0, &iv1, code)) + return false; + break; + + case MULT: + if (!iv_mult (&iv0, mby)) return false; + break; - if (!iv_analyze (insn, SUBREG_REG (def), iv)) + case ASHIFT: + if (!iv_shift (&iv0, mby)) return false; + break; - return iv_subreg (iv, GET_MODE (def)); + default: + break; } - if (!insn) - return iv_analyze_biv (def, iv); + *iv = iv0; + return iv->base != NULL_RTX; +} + +/* Analyzes iv DEF and stores the result to *IV. */ + +static bool +iv_analyze_def (struct df_ref *def, struct rtx_iv *iv) +{ + rtx insn = DF_REF_INSN (def); + rtx reg = DF_REF_REG (def); + rtx set, rhs; if (dump_file) { fprintf (dump_file, "Analysing def of "); - print_rtl (dump_file, def); + print_rtl (dump_file, reg); fprintf (dump_file, " in insn "); print_rtl_single (dump_file, insn); } - uid = INSN_UID (insn); - if (insn_info[uid].iv.analysed) + if (DF_REF_IV (def)) { if (dump_file) fprintf (dump_file, " already analysed.\n"); - *iv = insn_info[uid].iv; + *iv = *DF_REF_IV (def); return iv->base != NULL_RTX; } @@ -1042,148 +1045,129 @@ iv_analyze (rtx insn, rtx def, struct rtx_iv *iv) iv->step = NULL_RTX; set = single_set (insn); + if (!set || SET_DEST (set) != reg) + return false; + rhs = find_reg_equal_equiv_note (insn); if (rhs) rhs = XEXP (rhs, 0); else rhs = SET_SRC (set); - code = GET_CODE (rhs); - if (CONSTANT_P (rhs)) + iv_analyze_expr (insn, rhs, GET_MODE (reg), iv); + record_iv (def, iv); + + if (dump_file) { - op0 = rhs; - amode = GET_MODE (def); + print_rtl (dump_file, reg); + fprintf (dump_file, " in insn "); + print_rtl_single (dump_file, insn); + fprintf (dump_file, " is "); + dump_iv_info (dump_file, iv); + fprintf (dump_file, "\n"); } - else - { - switch (code) - { - case SUBREG: - if (!subreg_lowpart_p (rhs)) - goto end; - op0 = rhs; - break; - - case REG: - op0 = rhs; - break; - case SIGN_EXTEND: - case ZERO_EXTEND: - case NEG: - op0 = XEXP (rhs, 0); - break; - - case PLUS: - case MINUS: - op0 = XEXP (rhs, 0); - op1 = XEXP (rhs, 1); - break; - - case MULT: - op0 = XEXP (rhs, 0); - mby = XEXP (rhs, 1); - if (!CONSTANT_P (mby)) - { - if (!CONSTANT_P (op0)) - abort (); - tmp = op0; - op0 = mby; - mby = tmp; - } - break; + return iv->base != NULL_RTX; +} - case ASHIFT: - if (CONSTANT_P (XEXP (rhs, 0))) - abort (); - op0 = XEXP (rhs, 0); - mby = XEXP (rhs, 1); - break; +/* Analyzes operand OP of INSN and stores the result to *IV. */ - default: - abort (); - } +static bool +iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv) +{ + struct df_ref *def = NULL; + enum iv_grd_result res; - amode = GET_MODE (rhs); + if (dump_file) + { + fprintf (dump_file, "Analysing operand "); + print_rtl (dump_file, op); + fprintf (dump_file, " of insn "); + print_rtl_single (dump_file, insn); } - if (op0) + if (CONSTANT_P (op)) + res = GRD_INVARIANT; + else if (GET_CODE (op) == SUBREG) { - if (!iv_analyze_op (insn, op0, &iv0)) - goto end; - - if (iv0.mode == VOIDmode) + if (!subreg_lowpart_p (op)) + return false; + + if (!iv_analyze_op (insn, SUBREG_REG (op), iv)) + return false; + + return iv_subreg (iv, GET_MODE (op)); + } + else + { + res = iv_get_reaching_def (insn, op, &def); + if (res == GRD_INVALID) { - iv0.mode = amode; - iv0.extend_mode = amode; + if (dump_file) + fprintf (dump_file, " not simple.\n"); + return false; } } - if (op1) + if (res == GRD_INVARIANT) { - if (!iv_analyze_op (insn, op1, &iv1)) - goto end; + iv_constant (iv, op, VOIDmode); - if (iv1.mode == VOIDmode) + if (dump_file) { - iv1.mode = amode; - iv1.extend_mode = amode; + fprintf (dump_file, " "); + dump_iv_info (dump_file, iv); + fprintf (dump_file, "\n"); } + return true; } - switch (code) - { - case SIGN_EXTEND: - case ZERO_EXTEND: - if (!iv_extend (&iv0, code, amode)) - goto end; - break; + if (res == GRD_MAYBE_BIV) + return iv_analyze_biv (op, iv); - case NEG: - if (!iv_neg (&iv0)) - goto end; - break; + return iv_analyze_def (def, iv); +} - case PLUS: - case MINUS: - if (!iv_add (&iv0, &iv1, code)) - goto end; - break; +/* Analyzes value VAL at INSN and stores the result to *IV. */ - case MULT: - if (!iv_mult (&iv0, mby)) - goto end; - break; +bool +iv_analyze (rtx insn, rtx val, struct rtx_iv *iv) +{ + rtx reg; - case ASHIFT: - if (!iv_shift (&iv0, mby)) - goto end; - break; + /* We must find the insn in that val is used, so that we get to UD chains. + Since the function is sometimes called on result of get_condition, + this does not necessarily have to be directly INSN; scan also the + following insns. */ + if (simple_reg_p (val)) + { + if (GET_CODE (val) == SUBREG) + reg = SUBREG_REG (val); + else + reg = val; - default: - break; + while (!df_find_use (df, insn, reg)) + insn = NEXT_INSN (insn); } - *iv = iv0; + return iv_analyze_op (insn, val, iv); +} - end: - iv->analysed = true; - insn_info[uid].iv = *iv; +/* Analyzes definition of DEF in INSN and stores the result to IV. */ - if (dump_file) - { - print_rtl (dump_file, def); - fprintf (dump_file, " in insn "); - print_rtl_single (dump_file, insn); - fprintf (dump_file, " is "); - dump_iv_info (dump_file, iv); - fprintf (dump_file, "\n"); - } +bool +iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv) +{ + struct df_ref *adef; - return iv->base != NULL_RTX; + adef = df_find_def (df, insn, def); + if (!adef) + return false; + + return iv_analyze_def (adef, iv); } -/* Checks whether definition of register REG in INSN a basic induction +/* Checks whether definition of register REG in INSN is a basic induction variable. IV analysis must have been initialized (via a call to iv_analysis_loop_init) for this function to produce a result. */ @@ -1191,14 +1175,22 @@ bool biv_p (rtx insn, rtx reg) { struct rtx_iv iv; + struct df_ref *def, *last_def; - if (!REG_P (reg)) + if (!simple_reg_p (reg)) return false; - if (last_def[REGNO (reg)] != insn) + def = df_find_def (df, insn, reg); + gcc_assert (def != NULL); + if (!latch_dominating_def (reg, &last_def)) + return false; + if (last_def != def) + return false; + + if (!iv_analyze_biv (reg, &iv)) return false; - return iv_analyze_biv (reg, &iv); + return iv.step != const0_rtx; } /* Calculates value of IV at ITERATION-th iteration. */ @@ -1210,8 +1202,7 @@ get_iv_value (struct rtx_iv *iv, rtx iteration) /* We would need to generate some if_then_else patterns, and so far it is not needed anywhere. */ - if (iv->first_special) - abort (); + gcc_assert (!iv->first_special); if (iv->step != const0_rtx && iteration != const0_rtx) val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base, @@ -1241,21 +1232,12 @@ get_iv_value (struct rtx_iv *iv, rtx iteration) void iv_analysis_done (void) { - max_insn_no = 0; - max_reg_no = 0; - if (insn_info) + if (df) { - free (insn_info); - insn_info = NULL; - } - if (last_def) - { - free (last_def); - last_def = NULL; - } - if (bivs) - { - free (bivs); + clear_iv_info (); + df_finish (df); + df = NULL; + htab_delete (bivs); bivs = NULL; } } @@ -1279,71 +1261,6 @@ inverse (unsigned HOST_WIDEST_INT x, int mod) return rslt; } -/* Tries to estimate the maximum number of iterations. */ - -static unsigned HOST_WIDEST_INT -determine_max_iter (struct niter_desc *desc) -{ - rtx niter = desc->niter_expr; - rtx mmin, mmax, left, right; - unsigned HOST_WIDEST_INT nmax, inc; - - if (GET_CODE (niter) == AND - && GET_CODE (XEXP (niter, 0)) == CONST_INT) - { - nmax = INTVAL (XEXP (niter, 0)); - if (!(nmax & (nmax + 1))) - { - desc->niter_max = nmax; - return nmax; - } - } - - get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); - nmax = INTVAL (mmax) - INTVAL (mmin); - - if (GET_CODE (niter) == UDIV) - { - if (GET_CODE (XEXP (niter, 1)) != CONST_INT) - { - desc->niter_max = nmax; - return nmax; - } - inc = INTVAL (XEXP (niter, 1)); - niter = XEXP (niter, 0); - } - else - inc = 1; - - if (GET_CODE (niter) == PLUS) - { - left = XEXP (niter, 0); - right = XEXP (niter, 0); - - if (GET_CODE (right) == CONST_INT) - right = GEN_INT (-INTVAL (right)); - } - else if (GET_CODE (niter) == MINUS) - { - left = XEXP (niter, 0); - right = XEXP (niter, 0); - } - else - { - left = niter; - right = mmin; - } - - if (GET_CODE (left) == CONST_INT) - mmax = left; - if (GET_CODE (right) == CONST_INT) - mmin = right; - nmax = INTVAL (mmax) - INTVAL (mmin); - - desc->niter_max = nmax / inc; - return nmax / inc; -} - /* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */ static int @@ -1475,14 +1392,34 @@ implies_p (rtx a, rtx b) } } + if (b == const_true_rtx) + return true; + + if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE + && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE) + || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE + && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE)) + return false; + + op0 = XEXP (a, 0); + op1 = XEXP (a, 1); + opb0 = XEXP (b, 0); + opb1 = XEXP (b, 1); + + mode = GET_MODE (op0); + if (mode != GET_MODE (opb0)) + mode = VOIDmode; + else if (mode == VOIDmode) + { + mode = GET_MODE (op1); + if (mode != GET_MODE (opb1)) + mode = VOIDmode; + } + /* A < B implies A + 1 <= B. */ if ((GET_CODE (a) == GT || GET_CODE (a) == LT) && (GET_CODE (b) == GE || GET_CODE (b) == LE)) { - op0 = XEXP (a, 0); - op1 = XEXP (a, 1); - opb0 = XEXP (b, 0); - opb1 = XEXP (b, 1); if (GET_CODE (a) == GT) { @@ -1498,22 +1435,82 @@ implies_p (rtx a, rtx b) opb1 = r; } - mode = GET_MODE (op0); - if (mode != GET_MODE (opb0)) - mode = VOIDmode; - else if (mode == VOIDmode) - { - mode = GET_MODE (op1); - if (mode != GET_MODE (opb1)) - mode = VOIDmode; - } - - if (mode != VOIDmode + if (SCALAR_INT_MODE_P (mode) && rtx_equal_p (op1, opb1) && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx) return true; + return false; + } + + /* A < B or A > B imply A != B. TODO: Likewise + A + n < B implies A != B + n if neither wraps. */ + if (GET_CODE (b) == NE + && (GET_CODE (a) == GT || GET_CODE (a) == GTU + || GET_CODE (a) == LT || GET_CODE (a) == LTU)) + { + if (rtx_equal_p (op0, opb0) + && rtx_equal_p (op1, opb1)) + return true; } + /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */ + if (GET_CODE (a) == NE + && op1 == const0_rtx) + { + if ((GET_CODE (b) == GTU + && opb1 == const0_rtx) + || (GET_CODE (b) == GEU + && opb1 == const1_rtx)) + return rtx_equal_p (op0, opb0); + } + + /* A != N is equivalent to A - (N + 1) 0. */ + if (GET_CODE (a) == NE + && GET_CODE (op1) == CONST_INT) + { + if (GET_CODE (b) == GTU + && GET_CODE (opb0) == PLUS + && opb1 == const0_rtx + && GET_CODE (XEXP (opb0, 1)) == CONST_INT + /* Avoid overflows. */ + && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) + != ((unsigned HOST_WIDE_INT) 1 << (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 + && GET_CODE (opb0) == PLUS + && opb1 == const1_rtx + && GET_CODE (XEXP (opb0, 1)) == CONST_INT + /* Avoid overflows. */ + && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1)) + != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1))) + && rtx_equal_p (XEXP (opb0, 0), op0)) + return INTVAL (op1) == -INTVAL (XEXP (opb0, 1)); + } + + /* A >s X, where X is positive, implies A = 0) + && GET_CODE (b) == LTU + && GET_CODE (opb1) == CONST_INT) + return INTVAL (opb1) < 0; + return false; } @@ -1547,8 +1544,7 @@ canon_condition (rtx cond) mode = GET_MODE (op0); if (mode == VOIDmode) mode = GET_MODE (op1); - if (mode == VOIDmode) - abort (); + gcc_assert (mode != VOIDmode); if (GET_CODE (op1) == CONST_INT && GET_MODE_CLASS (mode) != MODE_CC @@ -1677,20 +1673,23 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered) static void eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b) { - if (op == AND) + switch (op) { + case AND: /* If A implies *B, we may replace *B by true. */ if (implies_p (a, *b)) *b = const_true_rtx; - } - else if (op == IOR) - { + break; + + case IOR: /* If *B implies A, we may replace *B by false. */ if (implies_p (*b, a)) *b = const0_rtx; + break; + + default: + gcc_unreachable (); } - else - abort (); } /* Eliminates the conditions in TAIL that are implied by HEAD. OP is the @@ -1731,19 +1730,22 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) eliminate_implied_conditions (op, &head, tail); - if (op == AND) + switch (op) { + case AND: neutral = const_true_rtx; aggr = const0_rtx; - } - else if (op == IOR) - { + break; + + case IOR: neutral = const0_rtx; aggr = const_true_rtx; - } - else - abort (); + break; + default: + gcc_unreachable (); + } + simplify_using_initial_values (loop, UNKNOWN, &head); if (head == aggr) { @@ -1770,8 +1772,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) return; } - if (op != UNKNOWN) - abort (); + gcc_assert (op == UNKNOWN); e = loop_preheader_edge (loop); if (e->src == ENTRY_BLOCK_PTR) @@ -1810,6 +1811,11 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr) FREE_REG_SET (altered); return; } + if (for_each_rtx (expr, altered_reg_used, altered)) + { + FREE_REG_SET (altered); + return; + } } if (!single_pred_p (e->src) @@ -1873,7 +1879,7 @@ shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode, break; default: - abort (); + gcc_unreachable (); } iv->mode = mode; @@ -1931,7 +1937,7 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, break; default: - abort (); + gcc_unreachable (); } /* Values of both variables should be computed in the same mode. These @@ -1995,6 +2001,57 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1, return true; } +/* Tries to estimate the maximum number of iterations. */ + +static unsigned HOST_WIDEST_INT +determine_max_iter (struct loop *loop, struct niter_desc *desc) +{ + rtx niter = desc->niter_expr; + rtx mmin, mmax, cmp; + unsigned HOST_WIDEST_INT nmax, inc; + + if (GET_CODE (niter) == AND + && GET_CODE (XEXP (niter, 0)) == CONST_INT) + { + nmax = INTVAL (XEXP (niter, 0)); + if (!(nmax & (nmax + 1))) + { + desc->niter_max = nmax; + return nmax; + } + } + + get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax); + nmax = INTVAL (mmax) - INTVAL (mmin); + + if (GET_CODE (niter) == UDIV) + { + if (GET_CODE (XEXP (niter, 1)) != CONST_INT) + { + desc->niter_max = nmax; + return nmax; + } + inc = INTVAL (XEXP (niter, 1)); + niter = XEXP (niter, 0); + } + else + inc = 1; + + /* We could use a binary search here, but for now improving the upper + bound by just one eliminates one important corner case. */ + cmp = gen_rtx_fmt_ee (desc->signed_p ? LT : LTU, VOIDmode, niter, mmax); + simplify_using_initial_values (loop, UNKNOWN, &cmp); + if (cmp == const_true_rtx) + { + nmax--; + + if (dump_file) + fprintf (dump_file, ";; improved upper bound by one.\n"); + } + desc->niter_max = nmax / inc; + return nmax / inc; +} + /* Computes number of iterations of the CONDITION in INSN in LOOP and stores the result into DESC. Very similar to determine_number_of_iterations (basically its rtl version), complicated by things like subregs. */ @@ -2003,7 +2060,7 @@ static void iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, struct niter_desc *desc) { - rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1; + rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1; struct rtx_iv iv0, iv1, tmp_iv; rtx assumption, may_not_xform; enum rtx_code cond; @@ -2031,15 +2088,13 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, desc->niter_max = 0; cond = GET_CODE (condition); - if (!COMPARISON_P (condition)) - abort (); + gcc_assert (COMPARISON_P (condition)); mode = GET_MODE (XEXP (condition, 0)); if (mode == VOIDmode) mode = GET_MODE (XEXP (condition, 1)); /* The constant comparisons should be folded. */ - if (mode == VOIDmode) - abort (); + gcc_assert (mode != VOIDmode); /* We only handle integers or pointers. */ if (GET_MODE_CLASS (mode) != MODE_INT @@ -2047,15 +2102,13 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, goto fail; op0 = XEXP (condition, 0); - def_insn = iv_get_reaching_def (insn, op0); - if (!iv_analyze (def_insn, op0, &iv0)) + if (!iv_analyze (insn, op0, &iv0)) goto fail; if (iv0.extend_mode == VOIDmode) iv0.mode = iv0.extend_mode = mode; op1 = XEXP (condition, 1); - def_insn = iv_get_reaching_def (insn, op1); - if (!iv_analyze (def_insn, op1, &iv1)) + if (!iv_analyze (insn, op1, &iv1)) goto fail; if (iv1.extend_mode == VOIDmode) iv1.mode = iv1.extend_mode = mode; @@ -2159,7 +2212,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mode_mmax); if (assumption == const_true_rtx) - goto zero_iter; + goto zero_iter_simplify; iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, const1_rtx); } @@ -2169,7 +2222,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, assumption = simplify_gen_relational (EQ, SImode, mode, tmp, mode_mmin); if (assumption == const_true_rtx) - goto zero_iter; + goto zero_iter_simplify; iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, constm1_rtx); } @@ -2196,7 +2249,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, { desc->infinite = alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); - return; + /* Fill in the remaining fields somehow. */ + goto zero_iter_simplify; } } else @@ -2206,7 +2260,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, { desc->infinite = alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX); - return; + /* Fill in the remaining fields somehow. */ + goto zero_iter_simplify; } } } @@ -2317,7 +2372,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, assumption = simplify_gen_relational (reverse_condition (cond), SImode, mode, tmp0, tmp1); if (assumption == const_true_rtx) - goto zero_iter; + goto zero_iter_simplify; else if (assumption != const0_rtx) desc->noloop_assumptions = alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); @@ -2424,7 +2479,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, tmp0 = lowpart_subreg (mode, iv0.base, comp_mode); tmp1 = lowpart_subreg (mode, iv1.base, comp_mode); - bound = simplify_gen_binary (MINUS, mode, mode_mmin, + bound = simplify_gen_binary (PLUS, mode, mode_mmin, lowpart_subreg (mode, step, comp_mode)); if (step_is_pow2) { @@ -2460,7 +2515,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, delta = simplify_gen_binary (MINUS, mode, tmp1, delta); } if (assumption == const_true_rtx) - goto zero_iter; + goto zero_iter_simplify; else if (assumption != const0_rtx) desc->noloop_assumptions = alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions); @@ -2515,7 +2570,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, else { if (!desc->niter_max) - desc->niter_max = determine_max_iter (desc); + desc->niter_max = determine_max_iter (loop, desc); /* simplify_using_initial_values does a copy propagation on the registers in the expression for the number of iterations. This prolongs life @@ -2528,16 +2583,26 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition, return; -fail: - desc->simple_p = false; - return; +zero_iter_simplify: + /* Simplify the assumptions. */ + simplify_using_initial_values (loop, AND, &desc->assumptions); + if (desc->assumptions + && XEXP (desc->assumptions, 0) == const0_rtx) + goto fail; + simplify_using_initial_values (loop, IOR, &desc->infinite); + /* Fallthru. */ zero_iter: desc->const_iter = true; desc->niter = 0; desc->niter_max = 0; + desc->noloop_assumptions = NULL_RTX; desc->niter_expr = const0_rtx; return; + +fail: + desc->simple_p = false; + return; } /* Checks whether E is a simple exit from LOOP and stores its description @@ -2614,12 +2679,21 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc) if (!act.simple_p) continue; - /* Prefer constant iterations; the less the better. */ if (!any) any = true; - else if (!act.const_iter - || (desc->const_iter && act.niter >= desc->niter)) - continue; + else + { + /* Prefer constant iterations; the less the better. */ + if (!act.const_iter + || (desc->const_iter && act.niter >= desc->niter)) + continue; + + /* Also if the actual exit may be infinite, while the old one + not, prefer the old one. */ + if (act.infinite && !desc->infinite) + continue; + } + *desc = act; } } @@ -2677,11 +2751,46 @@ get_simple_loop_desc (struct loop *loop) if (desc) return desc; - desc = xmalloc (sizeof (struct niter_desc)); + desc = XNEW (struct niter_desc); iv_analysis_loop_init (loop); find_simple_exit (loop, desc); loop->aux = 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; }