X-Git-Url: http://git.sourceforge.jp/view?a=blobdiff_plain;f=gcc%2Floop-iv.c;h=16e9a52697dafbd76784ff9fa706edefc8ac01f9;hb=3e5482040c58423a2a6e5fdb321d630adcea200c;hp=7c7a5de0a556eedd74cbf566c23bf79f9d738ece;hpb=7e3cc6817ae6be36340eb0c1978c1b3210cab69e;p=pf3gnuchains%2Fgcc-fork.git
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 7c7a5de0a55..16e9a52697d 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -1,51 +1,52 @@
/* Rtl-level induction variable analysis.
- Copyright (C) 2004, 2005 Free Software Foundation, Inc.
-
+ Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+ Free Software Foundation, Inc.
+
This file is part of GCC.
-
+
GCC is free software; you can redistribute it and/or modify it
under the terms of the GNU General Public License as published by the
-Free Software Foundation; either version 2, or (at your option) any
+Free Software Foundation; either version 3, or (at your option) any
later version.
-
+
GCC is distributed in the hope that it will be useful, but WITHOUT
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
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, 51 Franklin Street, Fifth Floor, Boston, MA
-02110-1301, 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 (); */
+along with GCC; see the file COPYING3. If not see
+. */
+
+/* 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 variables are analyzed by walking the use-def chains. When
+ a basic induction variable (biv) is found, it is cached in the bivs
+ hash table. When register is proved to be a biv, 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.
+*/
#include "config.h"
#include "system.h"
@@ -60,40 +61,57 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
#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. */
+};
+
+static bool clean_slate = true;
-static rtx *last_def;
+static unsigned int iv_ref_table_size = 0;
-/* The bivs. */
+/* Table of rtx_ivs indexed by the df_ref uid field. */
+static struct rtx_iv ** iv_ref_table;
-static struct rtx_iv *bivs;
+/* Induction variable stored at the reference. */
+#define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
+#define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
-/* Maximal insn number for that there is place in insn_info array. */
+/* The current loop. */
-static unsigned max_insn_no;
+static struct loop *current_loop;
-/* Maximal register number for that there is place in bivs and last_def
- arrays. */
+/* Bivs of the current loop. */
-static unsigned max_reg_no;
+static htab_t bivs;
+
+static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
/* Dumps information about IV to FILE. */
@@ -139,23 +157,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. */
@@ -167,6 +168,20 @@ lowpart_subreg (enum machine_mode outer_mode, rtx expr,
subreg_lowpart_offset (outer_mode, inner_mode));
}
+static void
+check_iv_ref_table_size (void)
+{
+ if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
+ {
+ unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
+ iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
+ memset (&iv_ref_table[iv_ref_table_size], 0,
+ (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
+ iv_ref_table_size = new_size;
+ }
+}
+
+
/* Checks whether REG is a well-behaved register. */
static bool
@@ -191,229 +206,176 @@ 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;
-
- if (!REG_P (lhs)
- || !simple_reg_p (lhs))
- return false;
-
- if (CONSTANT_P (rhs))
- return true;
+ unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
+ struct rtx_iv *iv;
- switch (GET_CODE (rhs))
+ check_iv_ref_table_size ();
+ 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;
+ iv = iv_ref_table[i];
+ if (iv)
+ {
+ free (iv);
+ iv_ref_table[i] = NULL;
+ }
}
+
+ htab_empty (bivs);
}
-/* Mark single SET in INSN. */
+/* Returns hash value for biv B. */
-static rtx
-mark_single_set (rtx insn, rtx set)
+static hashval_t
+biv_hash (const void *b)
{
- 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;
+ return ((const struct biv_entry *) b)->regno;
}
-/* Invalidate register REG unless it is equal to EXCEPT. */
+/* Compares biv B and register R. */
-static void
-kill_sets (rtx reg, rtx by ATTRIBUTE_UNUSED, void *except)
+static int
+biv_eq (const void *b, const void *r)
{
- 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 == REGNO ((const_rtx) r);
}
-/* Marks sets in basic block BB. If DOM is true, BB dominates the loop
- latch. */
+/* Prepare the data for an induction variable analysis of a LOOP. */
-static void
-mark_sets (basic_block bb, bool dom)
+void
+iv_analysis_loop_init (struct loop *loop)
{
- rtx insn, set, def;
+ basic_block *body = get_loop_body_in_dom_order (loop), bb;
+ bitmap blocks = BITMAP_ALLOC (NULL);
+ unsigned i;
+
+ current_loop = loop;
- FOR_BB_INSNS (bb, insn)
+ /* Clear the information from the analysis of the previous loop. */
+ if (clean_slate)
{
- if (!INSN_P (insn))
- continue;
+ df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
+ bivs = htab_create (10, biv_hash, biv_eq, free);
+ clean_slate = false;
+ }
+ else
+ clear_iv_info ();
- if (dom
- && (set = single_set (insn)))
- def = mark_single_set (insn, set);
- else
- def = NULL_RTX;
+ 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);
+ df_process_deferred_rescans ();
+ df_chain_add_problem (DF_UD_CHAIN);
+ df_note_add_problem ();
+ df_set_blocks (blocks);
+ df_analyze ();
+ if (dump_file)
+ df_dump_region (dump_file);
- note_stores (PATTERN (insn), kill_sets, def);
- }
+ check_iv_ref_table_size ();
+ BITMAP_FREE (blocks);
+ free (body);
}
-/* Prepare the data for an induction variable analysis of a LOOP. */
+/* 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. */
-void
-iv_analysis_loop_init (struct loop *loop)
+static bool
+latch_dominating_def (rtx reg, df_ref *def)
{
- basic_block *body = get_loop_body_in_dom_order (loop);
- unsigned b;
+ df_ref single_rd = NULL, adef;
+ unsigned regno = REGNO (reg);
+ struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
- if ((unsigned) get_max_uid () >= max_insn_no)
+ for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
{
- /* 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));
- }
+ if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
+ || !bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
+ continue;
- if ((unsigned) max_reg_num () >= max_reg_no)
- {
- 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));
- }
+ /* More than one reaching definition. */
+ if (single_rd)
+ return false;
- memset (last_def, 0, max_reg_num () * sizeof (rtx));
+ if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
+ return false;
- for (b = 0; b < loop->num_nodes; b++)
- {
- assign_luids (body[b]);
- mark_sets (body[b], just_once_each_iteration_p (loop, body[b]));
+ single_rd = adef;
}
- free (body);
+ *def = single_rd;
+ return true;
}
-/* 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. */
+/* Gets definition of REG reaching its use in INSN and stores it to DEF. */
-rtx
-iv_get_reaching_def (rtx insn, rtx reg)
+static enum iv_grd_result
+iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
{
- unsigned regno, luid, auid;
- rtx ainsn;
- basic_block bb, abb;
+ 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)
- {
- if (!subreg_lowpart_p (reg))
- return const0_rtx;
- reg = SUBREG_REG (reg);
- }
- if (!REG_P (reg))
- return NULL_RTX;
+ reg = SUBREG_REG (reg);
+ gcc_assert (REG_P (reg));
- regno = REGNO (reg);
- if (!last_def[regno]
- || last_def[regno] == const0_rtx)
- return last_def[regno];
+ use = df_find_use (insn, reg);
+ gcc_assert (use != NULL);
- bb = BLOCK_FOR_INSN (insn);
- luid = insn_info[INSN_UID (insn)].luid;
+ if (!DF_REF_CHAIN (use))
+ return GRD_INVARIANT;
- ainsn = last_def[regno];
- while (1)
- {
- abb = BLOCK_FOR_INSN (ainsn);
+ /* More than one reaching def. */
+ if (DF_REF_CHAIN (use)->next)
+ return GRD_INVALID;
- if (dominated_by_p (CDI_DOMINATORS, bb, abb))
- break;
+ adef = DF_REF_CHAIN (use)->ref;
- auid = INSN_UID (ainsn);
- ainsn = insn_info[auid].prev_def;
+ /* We do not handle setting only part of the register. */
+ if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
+ return GRD_INVALID;
- if (!ainsn)
- return NULL_RTX;
- }
+ def_insn = DF_REF_INSN (adef);
+ def_bb = DF_REF_BB (adef);
+ use_bb = BLOCK_FOR_INSN (insn);
- while (1)
+ if (use_bb == def_bb)
+ dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
+ else
+ dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
+
+ if (dom_p)
{
- abb = BLOCK_FOR_INSN (ainsn);
- if (abb != bb)
- return ainsn;
+ *def = adef;
+ return GRD_SINGLE_DOM;
+ }
- auid = INSN_UID (ainsn);
- if (luid > insn_info[auid].luid)
- return ainsn;
+ /* 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;
- ainsn = insn_info[auid].prev_def;
- if (!ainsn)
- return NULL_RTX;
- }
+ return GRD_INVALID;
}
/* Sets IV to invariant CST in MODE. Always returns true (just for
@@ -425,7 +387,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;
@@ -653,20 +614,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 (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);
+ 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);
@@ -742,11 +709,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;
@@ -756,7 +724,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;
@@ -803,7 +771,7 @@ get_biv_step_1 (rtx insn, rtx reg,
break;
default:
- gcc_unreachable ();
+ return false;
}
return true;
@@ -813,16 +781,17 @@ 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 (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;
@@ -833,16 +802,56 @@ get_biv_step (rtx reg, rtx *inner_step, enum machine_mode *inner_mode,
return true;
}
+/* Records information that DEF is induction variable IV. */
+
+static void
+record_iv (df_ref def, struct rtx_iv *iv)
+{
+ struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
+
+ *recorded_iv = *iv;
+ check_iv_ref_table_size ();
+ 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. */
+
+static bool
+analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
+{
+ struct biv_entry *biv =
+ (struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));
+
+ 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;
+ df_ref last_def;
if (dump_file)
{
@@ -850,7 +859,7 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
print_rtl (dump_file, def);
fprintf (dump_file, " for bivness.\n");
}
-
+
if (!REG_P (def))
{
if (!CONSTANT_P (def))
@@ -859,31 +868,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;
@@ -913,119 +915,155 @@ 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);
+ 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 (dump_file)
- {
- fprintf (dump_file, "Analyzing operand ");
- print_rtl (dump_file, op);
- fprintf (dump_file, " of insn ");
- print_rtl_single (dump_file, insn);
- }
+ iv->mode = VOIDmode;
+ iv->base = NULL_RTX;
+ iv->step = NULL_RTX;
- if (GET_CODE (op) == SUBREG)
- {
- if (!subreg_lowpart_p (op))
- return false;
+ gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
- if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
+ if (CONSTANT_P (rhs)
+ || REG_P (rhs)
+ || code == SUBREG)
+ {
+ if (!iv_analyze_op (insn, rhs, iv))
return false;
- return iv_subreg (iv, GET_MODE (op));
- }
-
- if (!inv)
- {
- regno = REGNO (op);
- if (!last_def[regno])
- inv = true;
- else if (last_def[regno] == const0_rtx)
+ 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;
- if (!iv_analyze (insn, SUBREG_REG (def), iv))
+ case MULT:
+ if (!iv_mult (&iv0, mby))
return false;
+ break;
- return iv_subreg (iv, GET_MODE (def));
+ case ASHIFT:
+ if (!iv_shift (&iv0, mby))
+ return false;
+ break;
+
+ 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 (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, "Analyzing 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)
+ check_iv_ref_table_size ();
+ 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;
}
@@ -1033,147 +1071,137 @@ iv_analyze (rtx insn, rtx def, struct rtx_iv *iv)
iv->base = NULL_RTX;
iv->step = NULL_RTX;
+ if (!REG_P (reg))
+ return false;
+
set = single_set (insn);
+ if (!set)
+ return false;
+
+ if (!REG_P (SET_DEST (set)))
+ return false;
+
+ gcc_assert (SET_DEST (set) == reg);
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;
+ return iv->base != NULL_RTX;
+}
- case PLUS:
- case MINUS:
- op0 = XEXP (rhs, 0);
- op1 = XEXP (rhs, 1);
- break;
+/* Analyzes operand OP of INSN and stores the result to *IV. */
- case MULT:
- op0 = XEXP (rhs, 0);
- mby = XEXP (rhs, 1);
- if (!CONSTANT_P (mby))
- {
- gcc_assert (CONSTANT_P (op0));
- tmp = op0;
- op0 = mby;
- mby = tmp;
- }
- break;
+static bool
+iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
+{
+ df_ref def = NULL;
+ enum iv_grd_result res;
- case ASHIFT:
- gcc_assert (!CONSTANT_P (XEXP (rhs, 0)));
- op0 = XEXP (rhs, 0);
- mby = XEXP (rhs, 1);
- break;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Analyzing operand ");
+ print_rtl (dump_file, op);
+ fprintf (dump_file, " of insn ");
+ print_rtl_single (dump_file, insn);
+ }
- default:
- gcc_unreachable ();
- }
+ if (function_invariant_p (op))
+ res = GRD_INVARIANT;
+ else if (GET_CODE (op) == SUBREG)
+ {
+ if (!subreg_lowpart_p (op))
+ return false;
- amode = GET_MODE (rhs);
- }
+ if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
+ return false;
- if (op0)
+ return iv_subreg (iv, GET_MODE (op));
+ }
+ else
{
- if (!iv_analyze_op (insn, op0, &iv0))
- goto end;
-
- if (iv0.mode == VOIDmode)
+ 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 (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)
+{
+ df_ref adef;
- return iv->base != NULL_RTX;
+ adef = df_find_def (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. */
@@ -1181,14 +1209,22 @@ bool
biv_p (rtx insn, rtx reg)
{
struct rtx_iv iv;
+ df_ref def, last_def;
- if (!REG_P (reg))
+ if (!simple_reg_p (reg))
+ return false;
+
+ def = df_find_def (insn, reg);
+ gcc_assert (def != NULL);
+ if (!latch_dominating_def (reg, &last_def))
+ return false;
+ if (last_def != def)
return false;
- if (last_def[REGNO (reg)] != insn)
+ 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. */
@@ -1230,21 +1266,15 @@ 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)
- {
- free (insn_info);
- insn_info = NULL;
- }
- if (last_def)
- {
- free (last_def);
- last_def = NULL;
- }
- if (bivs)
- {
- free (bivs);
+ if (!clean_slate)
+ {
+ clear_iv_info ();
+ clean_slate = true;
+ df_finish_pass (true);
+ htab_delete (bivs);
+ free (iv_ref_table);
+ iv_ref_table = NULL;
+ iv_ref_table_size = 0;
bivs = NULL;
}
}
@@ -1268,71 +1298,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
@@ -1341,20 +1306,20 @@ altered_reg_used (rtx *reg, void *alt)
if (!REG_P (*reg))
return 0;
- return REGNO_REG_SET_P (alt, REGNO (*reg));
+ return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
}
/* Marks registers altered by EXPR in set ALT. */
static void
-mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
+mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
{
if (GET_CODE (expr) == SUBREG)
expr = SUBREG_REG (expr);
if (!REG_P (expr))
return;
- SET_REGNO_REG_SET (alt, REGNO (expr));
+ SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
}
/* Checks whether RHS is simple enough to process. */
@@ -1364,62 +1329,114 @@ simple_rhs_p (rtx rhs)
{
rtx op0, op1;
- if (CONSTANT_P (rhs)
- || REG_P (rhs))
+ if (function_invariant_p (rhs)
+ || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
return true;
switch (GET_CODE (rhs))
{
case PLUS:
case MINUS:
+ case AND:
op0 = XEXP (rhs, 0);
op1 = XEXP (rhs, 1);
- /* Allow reg + const sets only. */
- if (REG_P (op0) && CONSTANT_P (op1))
- return true;
- if (REG_P (op1) && CONSTANT_P (op0))
- return true;
+ /* Allow reg OP const and reg OP reg. */
+ if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
+ && !function_invariant_p (op0))
+ return false;
+ if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
+ && !function_invariant_p (op1))
+ return false;
- return false;
+ return true;
+
+ case ASHIFT:
+ case ASHIFTRT:
+ case LSHIFTRT:
+ case MULT:
+ op0 = XEXP (rhs, 0);
+ op1 = XEXP (rhs, 1);
+ /* Allow reg OP const. */
+ if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
+ return false;
+ if (!function_invariant_p (op1))
+ return false;
+
+ return true;
default:
return false;
}
}
-/* Simplifies *EXPR using assignment in INSN. ALTERED is the set of registers
- altered so far. */
+/* If REG has a single definition, replace it with its known value in EXPR.
+ Callback for for_each_rtx. */
-static void
-simplify_using_assignment (rtx insn, rtx *expr, regset altered)
+static int
+replace_single_def_regs (rtx *reg, void *expr1)
{
- rtx set = single_set (insn);
- rtx lhs = NULL_RTX, rhs;
- bool ret = false;
+ unsigned regno;
+ df_ref adef;
+ rtx set, src;
+ rtx *expr = (rtx *)expr1;
- if (set)
- {
- lhs = SET_DEST (set);
- if (!REG_P (lhs)
- || altered_reg_used (&lhs, altered))
- ret = true;
- }
- else
- ret = true;
+ if (!REG_P (*reg))
+ return 0;
- note_stores (PATTERN (insn), mark_altered, altered);
- if (CALL_P (insn))
+ regno = REGNO (*reg);
+ for (;;)
{
- int i;
+ rtx note;
+ adef = DF_REG_DEF_CHAIN (regno);
+ if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
+ || DF_REF_IS_ARTIFICIAL (adef))
+ return -1;
+
+ set = single_set (DF_REF_INSN (adef));
+ if (set == NULL || !REG_P (SET_DEST (set))
+ || REGNO (SET_DEST (set)) != regno)
+ return -1;
- /* Kill all call clobbered registers. */
- for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
- if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
- SET_REGNO_REG_SET (altered, i);
+ note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
+
+ if (note && function_invariant_p (XEXP (note, 0)))
+ {
+ src = XEXP (note, 0);
+ break;
+ }
+ src = SET_SRC (set);
+
+ if (REG_P (src))
+ {
+ regno = REGNO (src);
+ continue;
+ }
+ break;
}
+ if (!function_invariant_p (src))
+ return -1;
- if (ret)
- return;
+ *expr = simplify_replace_rtx (*expr, *reg, src);
+ return 1;
+}
+
+/* A subroutine of simplify_using_initial_values, this function examines INSN
+ to see if it contains a suitable set that we can use to make a replacement.
+ If it is suitable, return true and set DEST and SRC to the lhs and rhs of
+ the set; return false otherwise. */
+
+static bool
+suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
+{
+ rtx set = single_set (insn);
+ rtx lhs = NULL_RTX, rhs;
+
+ if (!set)
+ return false;
+
+ lhs = SET_DEST (set);
+ if (!REG_P (lhs))
+ return false;
rhs = find_reg_equal_equiv_note (insn);
if (rhs)
@@ -1428,12 +1445,25 @@ simplify_using_assignment (rtx insn, rtx *expr, regset altered)
rhs = SET_SRC (set);
if (!simple_rhs_p (rhs))
- return;
+ return false;
- if (for_each_rtx (&rhs, altered_reg_used, altered))
- return;
+ *dest = lhs;
+ *src = rhs;
+ return true;
+}
- *expr = simplify_replace_rtx (*expr, lhs, rhs);
+/* Using the data returned by suitable_set_for_replacement, replace DEST
+ with SRC in *EXPR and return the new expression. Also call
+ replace_single_def_regs if the replacement changed something. */
+static void
+replace_in_expr (rtx *expr, rtx dest, rtx src)
+{
+ rtx old = *expr;
+ *expr = simplify_replace_rtx (*expr, dest, src);
+ if (old == *expr)
+ return;
+ while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
+ continue;
}
/* Checks whether A implies B. */
@@ -1464,14 +1494,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)
{
@@ -1487,22 +1537,83 @@ 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
+ && CONST_INT_P (op1))
+ {
+ if (GET_CODE (b) == GTU
+ && GET_CODE (opb0) == PLUS
+ && opb1 == const0_rtx
+ && 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)))
+ && 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
+ && 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)))
+ && 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
+ && CONST_INT_P (opb1)
+ && rtx_equal_p (op0, opb0))
+ return INTVAL (opb1) < 0;
+
return false;
}
@@ -1538,7 +1649,7 @@ canon_condition (rtx cond)
mode = GET_MODE (op1);
gcc_assert (mode != VOIDmode);
- if (GET_CODE (op1) == CONST_INT
+ if (CONST_INT_P (op1)
&& GET_MODE_CLASS (mode) != MODE_CC
&& GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
{
@@ -1595,15 +1706,22 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
{
rtx rev, reve, exp = *expr;
- if (!COMPARISON_P (exp))
- return;
-
/* 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))
return;
+ if (GET_CODE (cond) == EQ
+ && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
+ {
+ *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
+ return;
+ }
+
+ if (!COMPARISON_P (exp))
+ return;
+
rev = reversed_condition (cond);
reve = reversed_condition (exp);
@@ -1620,7 +1738,6 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
return;
}
-
if (rev && rtx_equal_p (exp, rev))
{
*expr = const0_rtx;
@@ -1632,7 +1749,7 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
*expr = const_true_rtx;
return;
}
-
+
if (reve && implies_p (cond, reve))
{
*expr = const0_rtx;
@@ -1704,9 +1821,10 @@ eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
static void
simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
{
- rtx head, tail, insn;
+ bool expression_valid;
+ rtx head, tail, insn, cond_list, last_valid_expr;
rtx neutral, aggr;
- regset altered;
+ regset altered, this_altered;
edge e;
if (!*expr)
@@ -1737,7 +1855,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
default:
gcc_unreachable ();
}
-
+
simplify_using_initial_values (loop, UNKNOWN, &head);
if (head == aggr)
{
@@ -1758,7 +1876,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
*expr = tail;
return;
}
-
+
XEXP (*expr, 0) = head;
XEXP (*expr, 1) = tail;
return;
@@ -1766,43 +1884,122 @@ 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;
+ if (CONSTANT_P (*expr))
+ return;
+
e = loop_preheader_edge (loop);
if (e->src == ENTRY_BLOCK_PTR)
return;
altered = ALLOC_REG_SET (®_obstack);
+ this_altered = ALLOC_REG_SET (®_obstack);
+ expression_valid = true;
+ last_valid_expr = *expr;
+ cond_list = NULL_RTX;
while (1)
{
insn = BB_END (e->src);
if (any_condjump_p (insn))
{
rtx cond = get_condition (BB_END (e->src), NULL, false, true);
-
+
if (cond && (e->flags & EDGE_FALLTHRU))
cond = reversed_condition (cond);
if (cond)
{
+ rtx old = *expr;
simplify_using_condition (cond, expr, altered);
- if (CONSTANT_P (*expr))
+ if (old != *expr)
{
- FREE_REG_SET (altered);
- return;
+ rtx note;
+ if (CONSTANT_P (*expr))
+ goto out;
+ for (note = cond_list; note; note = XEXP (note, 1))
+ {
+ simplify_using_condition (XEXP (note, 0), expr, altered);
+ if (CONSTANT_P (*expr))
+ goto out;
+ }
}
+ cond_list = alloc_EXPR_LIST (0, cond, cond_list);
}
}
FOR_BB_INSNS_REVERSE (e->src, insn)
{
+ rtx src, dest;
+ rtx old = *expr;
+
if (!INSN_P (insn))
continue;
-
- simplify_using_assignment (insn, expr, altered);
- if (CONSTANT_P (*expr))
+
+ CLEAR_REG_SET (this_altered);
+ note_stores (PATTERN (insn), mark_altered, this_altered);
+ if (CALL_P (insn))
+ {
+ int i;
+
+ /* Kill all call clobbered registers. */
+ for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+ if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
+ SET_REGNO_REG_SET (this_altered, i);
+ }
+
+ if (suitable_set_for_replacement (insn, &dest, &src))
{
- FREE_REG_SET (altered);
- return;
+ rtx *pnote, *pnote_next;
+
+ replace_in_expr (expr, dest, src);
+ if (CONSTANT_P (*expr))
+ goto out;
+
+ for (pnote = &cond_list; *pnote; pnote = pnote_next)
+ {
+ rtx note = *pnote;
+ rtx old_cond = XEXP (note, 0);
+
+ pnote_next = &XEXP (note, 1);
+ replace_in_expr (&XEXP (note, 0), dest, src);
+
+ /* We can no longer use a condition that has been simplified
+ to a constant, and simplify_using_condition will abort if
+ we try. */
+ if (CONSTANT_P (XEXP (note, 0)))
+ {
+ *pnote = *pnote_next;
+ pnote_next = pnote;
+ free_EXPR_LIST_node (note);
+ }
+ /* Retry simplifications with this condition if either the
+ expression or the condition changed. */
+ else if (old_cond != XEXP (note, 0) || old != *expr)
+ simplify_using_condition (XEXP (note, 0), expr, altered);
+ }
}
+ else
+ /* 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))
+ goto out;
+
+ if (CONSTANT_P (*expr))
+ goto out;
+
+ IOR_REG_SET (altered, this_altered);
+
+ /* If the expression now contains regs that have been altered, we
+ 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))
+ expression_valid = false;
+ if (expression_valid)
+ last_valid_expr = *expr;
}
if (!single_pred_p (e->src)
@@ -1811,7 +2008,12 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
e = single_pred_edge (e->src);
}
+ out:
+ free_EXPR_LIST_list (&cond_list);
+ if (!CONSTANT_P (*expr))
+ *expr = last_valid_expr;
FREE_REG_SET (altered);
+ FREE_REG_SET (this_altered);
}
/* Transforms invariant IV into MODE. Adds assumptions based on the fact
@@ -1935,7 +2137,7 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
and iv0 and iv1 are both ivs iterating in SI mode, but calculated
in different modes. This does not seem impossible to handle, but
it hardly ever occurs in practice.
-
+
The only exception is the case when one of operands is invariant.
For example pentium 3 generates comparisons like
(lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
@@ -1988,6 +2190,61 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
return true;
}
+/* Tries to estimate the maximum number of iterations in LOOP, and store the
+ result in DESC. This function is called from iv_number_of_iterations with
+ 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
+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;
+
+ if (GET_CODE (niter) == AND
+ && CONST_INT_P (XEXP (niter, 0)))
+ {
+ 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 (!CONST_INT_P (XEXP (niter, 1)))
+ {
+ 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 = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
+ desc->mode, old_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. */
@@ -1996,7 +2253,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;
@@ -2038,15 +2295,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;
@@ -2091,7 +2346,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
- if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
+ if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
goto fail;
/* We can take care of the case of two induction variables chasing each other
@@ -2222,7 +2477,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
may_xform = const0_rtx;
may_not_xform = const_true_rtx;
- if (GET_CODE (delta) == CONST_INT)
+ if (CONST_INT_P (delta))
{
if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
{
@@ -2285,11 +2540,11 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
number of iterations in this step, so record the information
here. */
inc = INTVAL (iv0.step) - INTVAL (iv1.step);
- if (GET_CODE (iv1.base) == CONST_INT)
+ if (CONST_INT_P (iv1.base))
up = INTVAL (iv1.base);
else
up = INTVAL (mode_mmax) - inc;
- down = INTVAL (GET_CODE (iv0.base) == CONST_INT
+ down = INTVAL (CONST_INT_P (iv0.base)
? iv0.base
: mode_mmin);
desc->niter_max = (up - down) / inc + 1;
@@ -2417,7 +2672,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)
{
@@ -2498,7 +2753,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
&& XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
goto zero_iter;
- if (GET_CODE (desc->niter_expr) == CONST_INT)
+ if (CONST_INT_P (desc->niter_expr))
{
unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
@@ -2508,7 +2763,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, old_niter);
/* simplify_using_initial_values does a copy propagation on the registers
in the expression for the number of iterations. This prolongs life
@@ -2612,7 +2867,7 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
{
if (flow_bb_inside_loop_p (loop, e->dest))
continue;
-
+
check_simple_exit (loop, e, &act);
if (!act.simple_p)
continue;
@@ -2631,7 +2886,7 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
if (act.infinite && !desc->infinite)
continue;
}
-
+
*desc = act;
}
}
@@ -2689,22 +2944,24 @@ get_simple_loop_desc (struct loop *loop)
if (desc)
return desc;
- desc = xmalloc (sizeof (struct niter_desc));
+ /* At least desc->infinite is not always initialized by
+ find_simple_loop_exit. */
+ desc = XCNEW (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;
+ const char *wording;
- /* Assume that no overflow happens and that the loop is finite.
+ /* 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 =
+ wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop is not infinite")
: N_("cannot optimize possibly infinite loops");
@@ -2713,7 +2970,7 @@ get_simple_loop_desc (struct loop *loop)
}
if (desc->assumptions)
{
- wording =
+ wording =
flag_unsafe_loop_optimizations
? N_("assuming that the loop counter does not overflow")
: N_("cannot optimize loop, the loop counter may overflow");