summaryrefslogtreecommitdiff
path: root/gcc/loop-iv.c
diff options
context:
space:
mode:
authorbstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4>2015-01-21 22:01:24 +0000
committerbstarynk <bstarynk@138bc75d-0d04-0410-961f-82ee72b054a4>2015-01-21 22:01:24 +0000
commitffde65b31066f17eef243be882bb89a6e19370aa (patch)
treeea876d041c0a63eefccdac5416a8678e75da4cfc /gcc/loop-iv.c
parenta8c7acc4db08ce7c8ac3ddcb943f9219e2893792 (diff)
downloadgcc-ffde65b31066f17eef243be882bb89a6e19370aa.tar.gz
[.]
2015-01-21 Basile Starynkevitch <basile@starynkevitch.net> {{merged with trunk -i.e. GCC5.0 in stage4- using svn merge -r209216:219879 svn+ssh://bstarynk@gcc.gnu.org/svn/gcc/trunk but should probably have used svn merge -r209216:219879 ^/trunk we don't use svnmerge.py anymore since our svn is version 1.8.10 }} VERY UNSTABLE 2015-01-20 Basile Starynkevitch <basile@starynkevitch.net> Move previous topdir ChangeLog.MELT to ChangeLog.MELT.2008-2014 [contrib/] 2015-01-21 Basile Starynkevitch <basile@starynkevitch.net> * MELT-Plugin-Makefile: Able to make upgrade-melt as a plugin. Works for GCC 5.0. Remove GCC 4.7 old stuff. Move previous contrib/ChangeLog.MELT to ChangeLog.MELT.2008-2014 [gcc/] 2015-01-21 Basile Starynkevitch <basile@starynkevitch.net> {{merged with trunk -i.e. GCC5.0 in stage4- using svn merge -r209216:219879 svn+ssh://bstarynk@gcc.gnu.org/svn/gcc/trunk but should probably have used svn merge -r209216:219879 ^/trunk **@@@ UNSTABLE since libmelt-ana-gimple.melt not compiling, but translator painfully bootstrapping!!@@@@ }} * toplev.c: Merged manually by keeping MELT extra stuff. * toplev.h: Likewise. * gengtype.c: Add "melt-runtime.h" in list, but merged with trunk. * melt-runtime.h (MELT_VERSION_STRING): Bump to "1.2-pre-merged". (meltgc_walk_gimple_seq): Remove. (gt_ggc_mx_gimple_statement_d): Same for GCC 4.9 & 5.0 * melt-runtime.cc: Update copyright year. (ggc_alloc_cleared_melt_valuevector_st, melt_resize_scangcvect): Call ggc_internal_cleared_alloc. (melt_val2passflag): Skip TODO_verify_ssa, TODO_verify_flow, TODO_verify_stmts, TODO_verify_rtl_sharing for GCC 5.0. (meltgc_walkstmt_cb, meltgc_walktree_cb) (melt_tree_walk_frame_size, meltgc_walk_gimple_seq): Remove. (melt_gt_ggc_mx_gimple_seq_d): Call gt_ggc_mx_gimple_statement_base. * melt-build-script.tpl: Update copyright year. Don't symlink meltrunsup.h anymore. * melt-build-script.sh: Regenerate. * melt/warmelt-base.melt: Update copyright year. (valdesc_object, valdesc_mapobjects, valdesc_mapstrings) (valdesc_multiple, valdesc_closure, valdesc_routine, valdesc_hook) (valdesc_bucketlongs, valdesc_jsonobject, valdesc_string) (valdesc_strbuf, valdesc_pair, valdesc_list, valdesc_int) (valdesc_double, valdesc_mixint, valdesc_mixloc) (valdesc_mixbigint, valdesc_real, valdesc_special_data): Use ggc_internal_alloc & ggc_internal_cleared_alloc for GCC 5.0. (json_canonical_name): Use ISUPPER, ISALPHA, TOUPPER instead of their standard <ctype.h> lowercase macros. * melt/warmelt-modes.melt: Update copyright year. (generate_runtypesupport_forwcopy_fun): Emit both GCC 4.9 & 5.0 compatible code. * melt/libmelt-ana-base.melt: Update copyright year. * melt/libmelt-ana-gimple.melt: TO BE IMPROVED * melt/generated/*: Painfully regenerated several times thru GCC 4.9 MELT plugin. git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/branches/melt-branch@219975 138bc75d-0d04-0410-961f-82ee72b054a4
Diffstat (limited to 'gcc/loop-iv.c')
-rw-r--r--gcc/loop-iv.c396
1 files changed, 275 insertions, 121 deletions
diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index 9091220642c..7b2116c61a2 100644
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -1,5 +1,5 @@
/* Rtl-level induction variable analysis.
- Copyright (C) 2004-2014 Free Software Foundation, Inc.
+ Copyright (C) 2004-2015 Free Software Foundation, Inc.
This file is part of GCC.
@@ -54,14 +54,42 @@ along with GCC; see the file COPYING3. If not see
#include "rtl.h"
#include "hard-reg-set.h"
#include "obstack.h"
+#include "predict.h"
+#include "vec.h"
+#include "hashtab.h"
+#include "hash-set.h"
+#include "machmode.h"
+#include "input.h"
+#include "function.h"
+#include "dominance.h"
+#include "cfg.h"
#include "basic-block.h"
#include "cfgloop.h"
+#include "symtab.h"
+#include "flags.h"
+#include "statistics.h"
+#include "double-int.h"
+#include "real.h"
+#include "fixed-value.h"
+#include "alias.h"
+#include "wide-int.h"
+#include "inchash.h"
+#include "tree.h"
+#include "insn-config.h"
+#include "expmed.h"
+#include "dojump.h"
+#include "explow.h"
+#include "calls.h"
+#include "emit-rtl.h"
+#include "varasm.h"
+#include "stmt.h"
#include "expr.h"
#include "intl.h"
#include "diagnostic-core.h"
#include "df.h"
#include "hash-table.h"
#include "dumpfile.h"
+#include "rtl-iter.h"
/* Possible return values of iv_get_reaching_def. */
@@ -134,9 +162,9 @@ biv_entry_hasher::equal (const value_type *b, const compare_type *r)
/* Bivs of the current loop. */
-static hash_table <biv_entry_hasher> bivs;
+static hash_table<biv_entry_hasher> *bivs;
-static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
+static bool iv_analyze_op (rtx_insn *, rtx, struct rtx_iv *);
/* Return the RTX code corresponding to the IV extend code EXTEND. */
static inline enum rtx_code
@@ -202,8 +230,8 @@ dump_iv_info (FILE *file, struct rtx_iv *iv)
INNER_MODE) to OUTER_MODE. */
rtx
-lowpart_subreg (enum machine_mode outer_mode, rtx expr,
- enum machine_mode inner_mode)
+lowpart_subreg (machine_mode outer_mode, rtx expr,
+ machine_mode inner_mode)
{
return simplify_gen_subreg (outer_mode, expr, inner_mode,
subreg_lowpart_offset (outer_mode, inner_mode));
@@ -269,7 +297,7 @@ clear_iv_info (void)
}
}
- bivs.empty ();
+ bivs->empty ();
}
@@ -284,7 +312,7 @@ iv_analysis_loop_init (struct loop *loop)
if (clean_slate)
{
df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
- bivs.create (10);
+ bivs = new hash_table<biv_entry_hasher> (10);
clean_slate = false;
}
else
@@ -304,34 +332,72 @@ iv_analysis_loop_init (struct loop *loop)
check_iv_ref_table_size ();
}
+/* Return true if D_REF is defined in an immediate predecessor of the
+ current loop's latch block. Otherwise return false. */
+
+static bool
+def_pred_latch_p (df_ref d_ref)
+{
+ basic_block bb = DF_REF_BB (d_ref);
+ edge_iterator ei;
+ edge e;
+
+ FOR_EACH_EDGE (e, ei, current_loop->latch->preds)
+ {
+ if (e->src == bb)
+ return true;
+ }
+ return false;
+}
+
/* 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
+ dominating the latch or all defs are same and they are on different
+ predecessors of loop latch. If REG has no definition in loop, DEF
is set to NULL and true is returned. */
static bool
latch_dominating_def (rtx reg, df_ref *def)
{
df_ref single_rd = NULL, adef;
- unsigned regno = REGNO (reg);
+ unsigned regno = REGNO (reg), def_num = 0;
struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
{
+ /* Initialize this to true for the very first iteration when
+ SINGLE_RD is NULL. */
+ bool def_pred_latch = true;
+
if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
|| !bitmap_bit_p (&bb_info->out, DF_REF_ID (adef)))
continue;
- /* More than one reaching definition. */
+ /* More than one reaching definition is ok in case definitions are
+ in predecessors of latch block and those definitions are the same.
+ Probably this could be relaxed and check for sub-dominance instead
+ predecessor. */
+ def_num++;
if (single_rd)
- return false;
-
- if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
- return false;
+ {
+ if (!(def_pred_latch = def_pred_latch_p (adef))
+ || !rtx_equal_p (PATTERN (DF_REF_INSN (single_rd)),
+ PATTERN (DF_REF_INSN (adef))))
+ return false;
+ }
single_rd = adef;
}
+ /* If we have single definition it has to be executed on each iteration. */
+ if ((def_num == 1) && single_rd
+ && !just_once_each_iteration_p (current_loop, DF_REF_BB (single_rd)))
+ return false;
+
+ /* Make sure all preds contain definitions. */
+ if (def_num != EDGE_COUNT (current_loop->latch->preds))
+ return false;
+
*def = single_rd;
return true;
}
@@ -339,12 +405,12 @@ latch_dominating_def (rtx reg, df_ref *def)
/* Gets definition of REG reaching its use in INSN and stores it to DEF. */
static enum iv_grd_result
-iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
+iv_get_reaching_def (rtx_insn *insn, rtx reg, df_ref *def)
{
- df_ref use, adef;
+ df_ref use, adef = NULL;
basic_block def_bb, use_bb;
- rtx def_insn;
- bool dom_p;
+ rtx_insn *def_insn;
+ bool dom_p, dom_latch_p = false;
*def = NULL;
if (!simple_reg_p (reg))
@@ -359,11 +425,26 @@ iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
if (!DF_REF_CHAIN (use))
return GRD_INVARIANT;
- /* More than one reaching def. */
+ adef = DF_REF_CHAIN (use)->ref;
+ /* Having more than one reaching def is ok once all defs are in blocks which
+ are latch's predecessors. */
if (DF_REF_CHAIN (use)->next)
- return GRD_INVALID;
+ {
+ df_link* defs;
+ unsigned int def_num = 0;
- adef = DF_REF_CHAIN (use)->ref;
+ for (defs = DF_REF_CHAIN (use); defs; defs = defs->next)
+ {
+ if (!def_pred_latch_p (defs->ref))
+ return GRD_INVALID;
+ def_num++;
+ }
+ /* Make sure all preds contain definitions. */
+ if (def_num != EDGE_COUNT (current_loop->latch->preds))
+ return GRD_INVALID;
+
+ dom_latch_p = true;
+ }
/* We do not handle setting only part of the register. */
if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
@@ -386,8 +467,8 @@ iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
/* 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))
+ latch or all defs are in latch's predecessors. */
+ if (dom_latch_p || just_once_each_iteration_p (current_loop, def_bb))
return GRD_MAYBE_BIV;
return GRD_INVALID;
@@ -397,7 +478,7 @@ iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
consistency with other iv manipulation functions that may fail). */
static bool
-iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
+iv_constant (struct rtx_iv *iv, rtx cst, machine_mode mode)
{
if (mode == VOIDmode)
mode = GET_MODE (cst);
@@ -417,7 +498,7 @@ iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
/* Evaluates application of subreg to MODE on IV. */
static bool
-iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
+iv_subreg (struct rtx_iv *iv, machine_mode mode)
{
/* If iv is invariant, just calculate the new value. */
if (iv->step == const0_rtx
@@ -459,7 +540,7 @@ iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
/* Evaluates application of EXTEND to MODE on IV. */
static bool
-iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, enum machine_mode mode)
+iv_extend (struct rtx_iv *iv, enum iv_extend_code extend, machine_mode mode)
{
/* If iv is invariant, just calculate the new value. */
if (iv->step == const0_rtx
@@ -522,7 +603,7 @@ iv_neg (struct rtx_iv *iv)
static bool
iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
{
- enum machine_mode mode;
+ machine_mode mode;
rtx arg;
/* Extend the constant to extend_mode of the other operand if necessary. */
@@ -592,7 +673,7 @@ iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
static bool
iv_mult (struct rtx_iv *iv, rtx mby)
{
- enum machine_mode mode = iv->extend_mode;
+ machine_mode mode = iv->extend_mode;
if (GET_MODE (mby) != VOIDmode
&& GET_MODE (mby) != mode)
@@ -617,7 +698,7 @@ iv_mult (struct rtx_iv *iv, rtx mby)
static bool
iv_shift (struct rtx_iv *iv, rtx mby)
{
- enum machine_mode mode = iv->extend_mode;
+ machine_mode mode = iv->extend_mode;
if (GET_MODE (mby) != VOIDmode
&& GET_MODE (mby) != mode)
@@ -643,14 +724,14 @@ iv_shift (struct rtx_iv *iv, rtx mby)
static bool
get_biv_step_1 (df_ref def, rtx reg,
- rtx *inner_step, enum machine_mode *inner_mode,
- enum iv_extend_code *extend, enum machine_mode outer_mode,
+ rtx *inner_step, machine_mode *inner_mode,
+ enum iv_extend_code *extend, machine_mode outer_mode,
rtx *outer_step)
{
rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
rtx next, nextr, tmp;
enum rtx_code code;
- rtx insn = DF_REF_INSN (def);
+ rtx_insn *insn = DF_REF_INSN (def);
df_ref next_def;
enum iv_grd_result res;
@@ -755,7 +836,7 @@ get_biv_step_1 (df_ref def, rtx reg,
if (GET_CODE (next) == SUBREG)
{
- enum machine_mode amode = GET_MODE (next);
+ machine_mode amode = GET_MODE (next);
if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
return false;
@@ -810,8 +891,8 @@ get_biv_step_1 (df_ref def, rtx reg,
static bool
get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
- enum machine_mode *inner_mode, enum iv_extend_code *extend,
- enum machine_mode *outer_mode, rtx *outer_step)
+ machine_mode *inner_mode, enum iv_extend_code *extend,
+ machine_mode *outer_mode, rtx *outer_step)
{
*outer_mode = GET_MODE (reg);
@@ -844,7 +925,7 @@ record_iv (df_ref def, struct rtx_iv *iv)
static bool
analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
{
- struct biv_entry *biv = bivs.find_with_hash (def, REGNO (def));
+ struct biv_entry *biv = bivs->find_with_hash (def, REGNO (def));
if (!biv)
return false;
@@ -857,7 +938,7 @@ static void
record_biv (rtx def, struct rtx_iv *iv)
{
struct biv_entry *biv = XNEW (struct biv_entry);
- biv_entry **slot = bivs.find_slot_with_hash (def, REGNO (def), INSERT);
+ biv_entry **slot = bivs->find_slot_with_hash (def, REGNO (def), INSERT);
biv->regno = REGNO (def);
biv->iv = *iv;
@@ -872,7 +953,7 @@ static bool
iv_analyze_biv (rtx def, struct rtx_iv *iv)
{
rtx inner_step, outer_step;
- enum machine_mode inner_mode, outer_mode;
+ machine_mode inner_mode, outer_mode;
enum iv_extend_code extend;
df_ref last_def;
@@ -946,13 +1027,14 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
The mode of the induction variable is MODE. */
bool
-iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
+iv_analyze_expr (rtx_insn *insn, rtx rhs, machine_mode mode,
+ struct rtx_iv *iv)
{
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;
+ machine_mode omode = mode;
iv->mode = VOIDmode;
iv->base = NULL_RTX;
@@ -1073,7 +1155,7 @@ iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
static bool
iv_analyze_def (df_ref def, struct rtx_iv *iv)
{
- rtx insn = DF_REF_INSN (def);
+ rtx_insn *insn = DF_REF_INSN (def);
rtx reg = DF_REF_REG (def);
rtx set, rhs;
@@ -1134,7 +1216,7 @@ iv_analyze_def (df_ref def, struct rtx_iv *iv)
/* Analyzes operand OP of INSN and stores the result to *IV. */
static bool
-iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
+iv_analyze_op (rtx_insn *insn, rtx op, struct rtx_iv *iv)
{
df_ref def = NULL;
enum iv_grd_result res;
@@ -1192,7 +1274,7 @@ iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
/* Analyzes value VAL at INSN and stores the result to *IV. */
bool
-iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
+iv_analyze (rtx_insn *insn, rtx val, struct rtx_iv *iv)
{
rtx reg;
@@ -1217,7 +1299,7 @@ iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
/* Analyzes definition of DEF in INSN and stores the result to IV. */
bool
-iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
+iv_analyze_result (rtx_insn *insn, rtx def, struct rtx_iv *iv)
{
df_ref adef;
@@ -1233,7 +1315,7 @@ iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
iv_analysis_loop_init) for this function to produce a result. */
bool
-biv_p (rtx insn, rtx reg)
+biv_p (rtx_insn *insn, rtx reg)
{
struct rtx_iv iv;
df_ref def, last_def;
@@ -1299,7 +1381,8 @@ iv_analysis_done (void)
clear_iv_info ();
clean_slate = true;
df_finish_pass (true);
- bivs.dispose ();
+ delete bivs;
+ bivs = NULL;
free (iv_ref_table);
iv_ref_table = NULL;
iv_ref_table_size = 0;
@@ -1308,12 +1391,12 @@ iv_analysis_done (void)
/* Computes inverse to X modulo (1 << MOD). */
-static unsigned HOST_WIDEST_INT
-inverse (unsigned HOST_WIDEST_INT x, int mod)
+static uint64_t
+inverse (uint64_t x, int mod)
{
- unsigned HOST_WIDEST_INT mask =
- ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
- unsigned HOST_WIDEST_INT rslt = 1;
+ uint64_t mask =
+ ((uint64_t) 1 << (mod - 1) << 1) - 1;
+ uint64_t rslt = 1;
int i;
for (i = 0; i < mod - 1; i++)
@@ -1325,15 +1408,19 @@ inverse (unsigned HOST_WIDEST_INT x, int mod)
return rslt;
}
-/* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
+/* Checks whether any register in X is in set ALT. */
-static int
-altered_reg_used (rtx *reg, void *alt)
+static bool
+altered_reg_used (const_rtx x, bitmap alt)
{
- if (!REG_P (*reg))
- return 0;
-
- return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
+ subrtx_iterator::array_type array;
+ FOR_EACH_SUBRTX (iter, array, x, NONCONST)
+ {
+ const_rtx x = *iter;
+ if (REG_P (x) && REGNO_REG_SET_P (alt, REGNO (x)))
+ return true;
+ }
+ return false;
}
/* Marks registers altered by EXPR in set ALT. */
@@ -1396,33 +1483,27 @@ simple_rhs_p (rtx rhs)
}
}
-/* If REG has a single definition, replace it with its known value in EXPR.
- Callback for for_each_rtx. */
+/* If REGNO has a single definition, return its known value, otherwise return
+ null. */
-static int
-replace_single_def_regs (rtx *reg, void *expr1)
+static rtx
+find_single_def_src (unsigned int regno)
{
- unsigned regno;
df_ref adef;
rtx set, src;
- rtx *expr = (rtx *)expr1;
- if (!REG_P (*reg))
- return 0;
-
- regno = REGNO (*reg);
for (;;)
{
rtx note;
adef = DF_REG_DEF_CHAIN (regno);
if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
- || DF_REF_IS_ARTIFICIAL (adef))
- return -1;
+ || DF_REF_IS_ARTIFICIAL (adef))
+ return NULL_RTX;
set = single_set (DF_REF_INSN (adef));
if (set == NULL || !REG_P (SET_DEST (set))
|| REGNO (SET_DEST (set)) != regno)
- return -1;
+ return NULL_RTX;
note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
@@ -1441,10 +1522,29 @@ replace_single_def_regs (rtx *reg, void *expr1)
break;
}
if (!function_invariant_p (src))
- return -1;
+ return NULL_RTX;
+
+ return src;
+}
+
+/* If any registers in *EXPR that have a single definition, try to replace
+ them with the known-equivalent values. */
- *expr = simplify_replace_rtx (*expr, *reg, src);
- return 1;
+static void
+replace_single_def_regs (rtx *expr)
+{
+ subrtx_var_iterator::array_type array;
+ repeat:
+ FOR_EACH_SUBRTX_VAR (iter, array, *expr, NONCONST)
+ {
+ rtx x = *iter;
+ if (REG_P (x))
+ if (rtx new_x = find_single_def_src (REGNO (x)))
+ {
+ *expr = simplify_replace_rtx (*expr, x, new_x);
+ goto repeat;
+ }
+ }
}
/* A subroutine of simplify_using_initial_values, this function examines INSN
@@ -1453,7 +1553,7 @@ replace_single_def_regs (rtx *reg, void *expr1)
the set; return false otherwise. */
static bool
-suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
+suitable_set_for_replacement (rtx_insn *insn, rtx *dest, rtx *src)
{
rtx set = single_set (insn);
rtx lhs = NULL_RTX, rhs;
@@ -1489,8 +1589,7 @@ replace_in_expr (rtx *expr, rtx dest, rtx src)
*expr = simplify_replace_rtx (*expr, dest, src);
if (old == *expr)
return;
- while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
- continue;
+ replace_single_def_regs (expr);
}
/* Checks whether A implies B. */
@@ -1499,7 +1598,7 @@ static bool
implies_p (rtx a, rtx b)
{
rtx op0, op1, opb0, opb1, r;
- enum machine_mode mode;
+ machine_mode mode;
if (rtx_equal_p (a, b))
return true;
@@ -1664,7 +1763,7 @@ canon_condition (rtx cond)
rtx tem;
rtx op0, op1;
enum rtx_code code;
- enum machine_mode mode;
+ machine_mode mode;
code = GET_CODE (cond);
op0 = XEXP (cond, 0);
@@ -1732,6 +1831,21 @@ canon_condition (rtx cond)
return cond;
}
+/* Reverses CONDition; returns NULL if we cannot. */
+
+static rtx
+reversed_condition (rtx cond)
+{
+ enum rtx_code reversed;
+ reversed = reversed_comparison_code (cond, NULL);
+ if (reversed == UNKNOWN)
+ return NULL_RTX;
+ else
+ return gen_rtx_fmt_ee (reversed,
+ GET_MODE (cond), XEXP (cond, 0),
+ XEXP (cond, 1));
+}
+
/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
set of altered regs. */
@@ -1742,8 +1856,7 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
/* If some register gets altered later, we do not really speak about its
value at the time of comparison. */
- if (altered
- && for_each_rtx (&cond, altered_reg_used, altered))
+ if (altered && altered_reg_used (cond, altered))
return;
if (GET_CODE (cond) == EQ
@@ -1856,7 +1969,9 @@ static void
simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
{
bool expression_valid;
- rtx head, tail, insn, cond_list, last_valid_expr;
+ rtx head, tail, last_valid_expr;
+ rtx_expr_list *cond_list;
+ rtx_insn *insn;
rtx neutral, aggr;
regset altered, this_altered;
edge e;
@@ -1918,9 +2033,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
gcc_assert (op == UNKNOWN);
- for (;;)
- if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
- break;
+ replace_single_def_regs (expr);
if (CONSTANT_P (*expr))
return;
@@ -1933,7 +2046,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
expression_valid = true;
last_valid_expr = *expr;
- cond_list = NULL_RTX;
+ cond_list = NULL;
while (1)
{
insn = BB_END (e->src);
@@ -1985,7 +2098,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
if (suitable_set_for_replacement (insn, &dest, &src))
{
- rtx *pnote, *pnote_next;
+ rtx_expr_list **pnote, **pnote_next;
replace_in_expr (expr, dest, src);
if (CONSTANT_P (*expr))
@@ -1996,7 +2109,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
rtx note = *pnote;
rtx old_cond = XEXP (note, 0);
- pnote_next = &XEXP (note, 1);
+ pnote_next = (rtx_expr_list **)&XEXP (note, 1);
replace_in_expr (&XEXP (note, 0), dest, src);
/* We can no longer use a condition that has been simplified
@@ -2016,12 +2129,12 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
}
else
{
- rtx *pnote, *pnote_next;
+ rtx_expr_list **pnote, **pnote_next;
/* If we did not use this insn to make a replacement, any overlap
between stores in this insn and our expression will cause the
expression to become invalid. */
- if (for_each_rtx (expr, altered_reg_used, this_altered))
+ if (altered_reg_used (*expr, this_altered))
goto out;
/* Likewise for the conditions. */
@@ -2030,8 +2143,8 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
rtx note = *pnote;
rtx old_cond = XEXP (note, 0);
- pnote_next = &XEXP (note, 1);
- if (for_each_rtx (&old_cond, altered_reg_used, this_altered))
+ pnote_next = (rtx_expr_list **)&XEXP (note, 1);
+ if (altered_reg_used (old_cond, this_altered))
{
*pnote = *pnote_next;
pnote_next = pnote;
@@ -2049,7 +2162,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
can't return it to the caller. However, it is still valid for
further simplification, so keep searching to see if we can
eventually turn it into a constant. */
- if (for_each_rtx (expr, altered_reg_used, altered))
+ if (altered_reg_used (*expr, altered))
expression_valid = false;
if (expression_valid)
last_valid_expr = *expr;
@@ -2074,7 +2187,7 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
is SIGNED_P to DESC. */
static void
-shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
+shorten_into_mode (struct rtx_iv *iv, machine_mode mode,
enum rtx_code cond, bool signed_p, struct niter_desc *desc)
{
rtx mmin, mmax, cond_over, cond_under;
@@ -2136,7 +2249,7 @@ static bool
canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
enum rtx_code cond, struct niter_desc *desc)
{
- enum machine_mode comp_mode;
+ machine_mode comp_mode;
bool signed_p;
/* If the ivs behave specially in the first iteration, or are
@@ -2248,13 +2361,13 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
a number of fields in DESC already filled in. OLD_NITER is the original
expression for the number of iterations, before we tried to simplify it. */
-static unsigned HOST_WIDEST_INT
+static uint64_t
determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
{
rtx niter = desc->niter_expr;
rtx mmin, mmax, cmp;
- unsigned HOST_WIDEST_INT nmax, inc;
- unsigned HOST_WIDEST_INT andmax = 0;
+ uint64_t nmax, inc;
+ uint64_t andmax = 0;
/* We used to look for constant operand 0 of AND,
but canonicalization should always make this impossible. */
@@ -2269,7 +2382,7 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
}
get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
- nmax = INTVAL (mmax) - INTVAL (mmin);
+ nmax = UINTVAL (mmax) - UINTVAL (mmin);
if (GET_CODE (niter) == UDIV)
{
@@ -2297,7 +2410,7 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
if (andmax)
nmax = MIN (nmax, andmax);
if (dump_file)
- fprintf (dump_file, ";; Determined upper bound "HOST_WIDEST_INT_PRINT_DEC".\n",
+ fprintf (dump_file, ";; Determined upper bound %"PRId64".\n",
nmax);
return nmax;
}
@@ -2307,17 +2420,17 @@ determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
(basically its rtl version), complicated by things like subregs. */
static void
-iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
+iv_number_of_iterations (struct loop *loop, rtx_insn *insn, rtx condition,
struct niter_desc *desc)
{
rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
struct rtx_iv iv0, iv1, tmp_iv;
rtx assumption, may_not_xform;
enum rtx_code cond;
- enum machine_mode mode, comp_mode;
+ machine_mode mode, comp_mode;
rtx mmin, mmax, mode_mmin, mode_mmax;
- unsigned HOST_WIDEST_INT s, size, d, inv, max;
- HOST_WIDEST_INT up, down, inc, step_val;
+ uint64_t s, size, d, inv, max;
+ int64_t up, down, inc, step_val;
int was_sharp = false;
rtx old_niter;
bool step_is_pow2;
@@ -2397,7 +2510,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
comp_mode = iv0.extend_mode;
mode = iv0.mode;
- size = GET_MODE_BITSIZE (mode);
+ size = GET_MODE_PRECISION (mode);
get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
@@ -2607,11 +2720,10 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
down = INTVAL (CONST_INT_P (iv0.base)
? iv0.base
: mode_mmin);
- max = (up - down) / inc + 1;
+ max = (uint64_t) (up - down) / inc + 1;
if (!desc->infinite
&& !desc->assumptions)
- record_niter_bound (loop, double_int::from_uhwi (max),
- false, true);
+ record_niter_bound (loop, max, false, true);
if (iv0.step == const0_rtx)
{
@@ -2650,8 +2762,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
iv1.step = const0_rtx;
if (INTVAL (iv0.step) < 0)
{
- iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
- iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
+ iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, comp_mode);
+ iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, comp_mode);
}
iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
@@ -2665,7 +2777,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
d *= 2;
size--;
}
- bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
+ bound = GEN_INT (((uint64_t) 1 << (size - 1 ) << 1) - 1);
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
tmp = simplify_gen_binary (UMOD, mode, tmp1, gen_int_mode (d, mode));
@@ -2819,14 +2931,13 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
if (CONST_INT_P (desc->niter_expr))
{
- unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
+ uint64_t val = INTVAL (desc->niter_expr);
desc->const_iter = true;
desc->niter = val & GET_MODE_MASK (desc->mode);
if (!desc->infinite
&& !desc->assumptions)
- record_niter_bound (loop, double_int::from_uhwi (desc->niter),
- false, true);
+ record_niter_bound (loop, desc->niter, false, true);
}
else
{
@@ -2835,8 +2946,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
goto zero_iter_simplify;
if (!desc->infinite
&& !desc->assumptions)
- record_niter_bound (loop, double_int::from_uhwi (max),
- false, true);
+ record_niter_bound (loop, max, false, true);
/* simplify_using_initial_values does a copy propagation on the registers
in the expression for the number of iterations. This prolongs life
@@ -2861,8 +2971,7 @@ zero_iter_simplify:
zero_iter:
desc->const_iter = true;
desc->niter = 0;
- record_niter_bound (loop, double_int_zero,
- true, true);
+ record_niter_bound (loop, 0, true, true);
desc->noloop_assumptions = NULL_RTX;
desc->niter_expr = const0_rtx;
return;
@@ -2872,6 +2981,49 @@ fail:
return;
}
+/* Return true if LOOP has a complex exit, but is still good for further
+ analysis. Return false otherwise. BB is LOOP's exit block. */
+
+static bool
+check_complex_exit_p (struct loop* loop, basic_block bb)
+{
+ edge e;
+ basic_block pred, exit;
+
+ if (EDGE_COUNT (bb->preds) > 1)
+ return false;
+
+ e = EDGE_PRED (bb, 0);
+
+ pred = e->src;
+ if (EDGE_COUNT (pred->succs) != 2)
+ return false;
+
+ /* Predecessor must be tested (at least) once during any iteration. */
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, pred))
+ return false;
+
+ if (EDGE_SUCC (pred, 0)->dest == bb)
+ exit = EDGE_SUCC (pred, 1)->dest;
+ else
+ exit = EDGE_SUCC (pred, 0)->dest;
+
+ /* Check that EXIT is really loop exit. */
+ if (flow_bb_inside_loop_p (loop, exit))
+ {
+ edge_iterator eei;
+ edge ee;
+
+ FOR_EACH_EDGE (ee, eei, exit->succs)
+ {
+ if (!flow_bb_inside_loop_p (loop, ee->dest))
+ return true;
+ }
+ }
+ return false;
+
+}
+
/* Checks whether E is a simple exit from LOOP and stores its description
into DESC. */
@@ -2879,7 +3031,8 @@ static void
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
{
basic_block exit_bb;
- rtx condition, at;
+ rtx condition;
+ rtx_insn *at;
edge ein;
exit_bb = e->src;
@@ -2890,7 +3043,8 @@ check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
return;
/* It must be tested (at least) once during any iteration. */
- if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb))
+ if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit_bb)
+ && !check_complex_exit_p (loop, exit_bb))
return;
/* It must end in a simple conditional jump. */
@@ -3021,7 +3175,7 @@ get_simple_loop_desc (struct loop *loop)
/* At least desc->infinite is not always initialized by
find_simple_loop_exit. */
- desc = ggc_alloc_cleared_niter_desc ();
+ desc = ggc_cleared_alloc<niter_desc> ();
iv_analysis_loop_init (loop);
find_simple_exit (loop, desc);
loop->simple_loop_desc = desc;