/* Rtl-level induction variable analysis.
- Copyright (C) 2004 Free Software Foundation, Inc.
+ Copyright (C) 2004, 2005 Free Software Foundation, Inc.
This file is part of GCC.
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"
#include "tm.h"
#include "rtl.h"
#include "hard-reg-set.h"
+#include "obstack.h"
#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
+};
+
+/* Information about a biv. */
+
+struct biv_entry
+{
+ unsigned regno; /* The register of the biv. */
+ struct rtx_iv iv; /* Value of the biv. */
};
-static struct insn_info *insn_info;
+/* 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 last definition of register. */
+/* 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. */
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. */
-static rtx
+rtx
lowpart_subreg (enum machine_mode outer_mode, rtx expr,
enum machine_mode inner_mode)
{
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_SIZE (df);
+ struct rtx_iv *iv;
+ struct df_ref *def;
- 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. */
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
if (mode == VOIDmode)
mode = GET_MODE (cst);
- iv->analysed = true;
iv->mode = mode;
iv->base = cst;
iv->step = const0_rtx;
}
/* 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, lhs, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
- rtx next, nextr, def_insn, tmp;
+ rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
+ 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);
else
rhs = SET_SRC (set);
- lhs = SET_DEST (set);
code = GET_CODE (rhs);
switch (code)
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;
*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;
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;
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 (*inner_mode == *outer_mode
- && *extend != UNKNOWN)
- abort ();
+/* 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
- && *outer_step != const0_rtx)
- 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 (!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");
}
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;
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);
- }
+ 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 (GET_CODE (op) == SUBREG)
- {
- if (!subreg_lowpart_p (op))
- return false;
+ iv->mode = VOIDmode;
+ iv->base = NULL_RTX;
+ iv->step = NULL_RTX;
- if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
- return false;
+ gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
- return iv_subreg (iv, GET_MODE (op));
- }
-
- 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;
}
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;
+ 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))
- {
- if (!CONSTANT_P (op0))
- abort ();
- tmp = op0;
- op0 = mby;
- mby = tmp;
- }
- break;
+static bool
+iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
+{
+ struct df_ref *def = NULL;
+ enum iv_grd_result res;
- case ASHIFT:
- if (CONSTANT_P (XEXP (rhs, 0)))
- abort ();
- op0 = XEXP (rhs, 0);
- mby = XEXP (rhs, 1);
- break;
+ if (dump_file)
+ {
+ fprintf (dump_file, "Analysing operand ");
+ print_rtl (dump_file, op);
+ fprintf (dump_file, " of insn ");
+ print_rtl_single (dump_file, insn);
+ }
- default:
- abort ();
- }
+ if (CONSTANT_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 (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. */
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. */
/* 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,
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;
}
}
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
}
}
+ 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)
{
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) <u -1. */
+ if (GET_CODE (a) == NE
+ && GET_CODE (op1) == CONST_INT
+ && GET_CODE (b) == LTU
+ && opb1 == constm1_rtx
+ && GET_CODE (opb0) == PLUS
+ && 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)) - 1)
+ && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
+ return rtx_equal_p (op0, XEXP (opb0, 0));
+
+ /* Likewise, A != N implies A - N > 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 <u Y, if Y is negative. */
+ if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
+ && GET_CODE (op1) == CONST_INT
+ && ((GET_CODE (a) == GT && op1 == constm1_rtx)
+ || INTVAL (op1) >= 0)
+ && GET_CODE (b) == LTU
+ && GET_CODE (opb1) == CONST_INT)
+ return INTVAL (opb1) < 0;
+
return false;
}
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
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
rtx head, tail, insn;
rtx neutral, aggr;
regset altered;
- regset_head altered_head;
edge e;
if (!*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)
{
return;
}
- if (op != UNKNOWN)
- abort ();
+ gcc_assert (op == UNKNOWN);
e = loop_preheader_edge (loop);
if (e->src == ENTRY_BLOCK_PTR)
return;
- altered = INITIALIZE_REG_SET (altered_head);
+ altered = ALLOC_REG_SET (®_obstack);
while (1)
{
- basic_block tmp_bb;
-
insn = BB_END (e->src);
if (any_condjump_p (insn))
{
}
}
- /* This is a bit subtle. Store away e->src in tmp_bb, since we
- modify `e' and this can invalidate the subsequent count of
- e->src's predecessors by looking at the wrong block. */
- tmp_bb = e->src;
- e = EDGE_PRED (tmp_bb, 0);
- if (EDGE_COUNT (tmp_bb->preds) > 1
- || e->src == ENTRY_BLOCK_PTR)
+ if (!single_pred_p (e->src)
+ || single_pred (e->src) == ENTRY_BLOCK_PTR)
break;
+ e = single_pred_edge (e->src);
}
FREE_REG_SET (altered);
break;
default:
- abort ();
+ gcc_unreachable ();
}
iv->mode = mode;
break;
default:
- abort ();
+ gcc_unreachable ();
}
/* Values of both variables should be computed in the same mode. These
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. */
-void
+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;
enum machine_mode mode, comp_mode;
rtx mmin, mmax, mode_mmin, mode_mmax;
unsigned HOST_WIDEST_INT s, size, d, inv;
- HOST_WIDEST_INT up, down, inc;
+ HOST_WIDEST_INT up, down, inc, step_val;
int was_sharp = false;
rtx old_niter;
+ bool step_is_pow2;
/* The meaning of these assumptions is this:
if !assumptions
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
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;
if (iv0.step == const0_rtx && iv1.step == const0_rtx)
goto fail;
- /* Ignore loops of while (i-- < 10) type. */
- if (cond != NE
- && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
- goto fail;
+ if (cond != NE)
+ {
+ if (iv0.step == const0_rtx)
+ step_val = -INTVAL (iv1.step);
+ else
+ step_val = INTVAL (iv0.step);
+
+ /* Ignore loops of while (i-- < 10) type. */
+ if (step_val < 0)
+ goto fail;
+
+ step_is_pow2 = !(step_val & (step_val - 1));
+ }
+ else
+ {
+ /* We do not care about whether the step is power of two in this
+ case. */
+ step_is_pow2 = false;
+ step_val = 0;
+ }
/* Some more condition normalization. We must record some assumptions
due to overflows. */
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);
}
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);
}
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
else
{
desc->infinite =
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
- return;
+ /* Fill in the remaining fields somehow. */
+ goto zero_iter_simplify;
}
}
}
/* If the step is a power of two and the final value we have
computed overflows, the cycle is infinite. Otherwise it
is nontrivial to compute the number of iterations. */
- s = INTVAL (step);
- if ((s & (s - 1)) == 0)
+ if (step_is_pow2)
desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
desc->infinite);
else
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);
tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
inv = inverse (s, size);
- inv = trunc_int_for_mode (inv, mode);
- tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
+ tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
}
else
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
bound = simplify_gen_binary (MINUS, mode, mode_mmax,
- lowpart_subreg (mode, step, comp_mode));
- assumption = simplify_gen_relational (cond, SImode, mode,
- tmp1, bound);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ lowpart_subreg (mode, step,
+ comp_mode));
+ if (step_is_pow2)
+ {
+ rtx t0, t1;
+
+ /* If s is power of 2, we know that the loop is infinite if
+ a % s <= b % s and b + s overflows. */
+ assumption = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ tmp1, bound);
+
+ t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+ t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+ tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+ assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+ desc->infinite =
+ alloc_EXPR_LIST (0, assumption, desc->infinite);
+ }
+ else
+ {
+ assumption = simplify_gen_relational (cond, SImode, mode,
+ tmp1, bound);
+ desc->assumptions =
+ alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ }
tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
tmp = lowpart_subreg (mode, tmp, comp_mode);
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));
- assumption = simplify_gen_relational (cond, SImode, mode,
- bound, tmp0);
- desc->assumptions =
- alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ if (step_is_pow2)
+ {
+ rtx t0, t1;
+
+ /* If s is power of 2, we know that the loop is infinite if
+ a % s <= b % s and a - s overflows. */
+ assumption = simplify_gen_relational (reverse_condition (cond),
+ SImode, mode,
+ bound, tmp0);
+
+ t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+ t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+ tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+ assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+ desc->infinite =
+ alloc_EXPR_LIST (0, assumption, desc->infinite);
+ }
+ else
+ {
+ assumption = simplify_gen_relational (cond, SImode, mode,
+ bound, tmp0);
+ desc->assumptions =
+ alloc_EXPR_LIST (0, assumption, desc->assumptions);
+ }
tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
tmp = lowpart_subreg (mode, tmp, comp_mode);
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);
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
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
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;
}
}
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;
}
OSDN Git Service
