/* Rtl-level induction variable analysis.
|
/* Rtl-level induction variable analysis.
|
Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
|
Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
|
Free Software Foundation, Inc.
|
Free Software Foundation, Inc.
|
|
|
This file is part of GCC.
|
This file is part of GCC.
|
|
|
GCC is free software; you can redistribute it and/or modify it
|
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
|
under the terms of the GNU General Public License as published by the
|
Free Software Foundation; either version 3, or (at your option) any
|
Free Software Foundation; either version 3, or (at your option) any
|
later version.
|
later version.
|
|
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
GCC is distributed in the hope that it will be useful, but WITHOUT
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
|
for more details.
|
for more details.
|
|
|
You should have received a copy of the GNU General Public License
|
You should have received a copy of the GNU General Public License
|
along with GCC; see the file COPYING3. If not see
|
along with GCC; see the file COPYING3. If not see
|
<http://www.gnu.org/licenses/>. */
|
<http://www.gnu.org/licenses/>. */
|
|
|
/* This is a simple analysis of induction variables of the loop. The major use
|
/* 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,
|
is for determining the number of iterations of a loop for loop unrolling,
|
doloop optimization and branch prediction. The iv information is computed
|
doloop optimization and branch prediction. The iv information is computed
|
on demand.
|
on demand.
|
|
|
Induction variables are analyzed by walking the use-def chains. When
|
Induction variables are analyzed by walking the use-def chains. When
|
a basic induction variable (biv) is found, it is cached in the bivs
|
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
|
hash table. When register is proved to be a biv, its description
|
is stored to DF_REF_DATA of the def reference.
|
is stored to DF_REF_DATA of the def reference.
|
|
|
The analysis works always with one loop -- you must call
|
The analysis works always with one loop -- you must call
|
iv_analysis_loop_init (loop) for it. All the other functions then work with
|
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
|
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_loop_init for it. When you no longer need iv analysis, call
|
iv_analysis_done () to clean up the memory.
|
iv_analysis_done () to clean up the memory.
|
|
|
The available functions are:
|
The available functions are:
|
|
|
iv_analyze (insn, reg, iv): Stores the description of the induction variable
|
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
|
corresponding to the use of register REG in INSN to IV. Returns true if
|
REG is an induction variable in INSN. false otherwise.
|
REG is an induction variable in INSN. false otherwise.
|
If use of REG is not found in INSN, following insns are scanned (so that
|
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).
|
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
|
iv_analyze_result (insn, def, iv): Stores to IV the description of the iv
|
corresponding to DEF, which is a register defined in INSN.
|
corresponding to DEF, which is a register defined in INSN.
|
iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
|
iv_analyze_expr (insn, rhs, mode, iv): Stores to IV the description of iv
|
corresponding to expression EXPR evaluated at INSN. All registers used bu
|
corresponding to expression EXPR evaluated at INSN. All registers used bu
|
EXPR must also be used in INSN.
|
EXPR must also be used in INSN.
|
*/
|
*/
|
|
|
#include "config.h"
|
#include "config.h"
|
#include "system.h"
|
#include "system.h"
|
#include "coretypes.h"
|
#include "coretypes.h"
|
#include "tm.h"
|
#include "tm.h"
|
#include "rtl.h"
|
#include "rtl.h"
|
#include "hard-reg-set.h"
|
#include "hard-reg-set.h"
|
#include "obstack.h"
|
#include "obstack.h"
|
#include "basic-block.h"
|
#include "basic-block.h"
|
#include "cfgloop.h"
|
#include "cfgloop.h"
|
#include "expr.h"
|
#include "expr.h"
|
#include "intl.h"
|
#include "intl.h"
|
#include "output.h"
|
#include "output.h"
|
#include "toplev.h"
|
#include "toplev.h"
|
#include "df.h"
|
#include "df.h"
|
#include "hashtab.h"
|
#include "hashtab.h"
|
|
|
/* Possible return values of iv_get_reaching_def. */
|
/* Possible return values of iv_get_reaching_def. */
|
|
|
enum iv_grd_result
|
enum iv_grd_result
|
{
|
{
|
/* More than one reaching def, or reaching def that does not
|
/* More than one reaching def, or reaching def that does not
|
dominate the use. */
|
dominate the use. */
|
GRD_INVALID,
|
GRD_INVALID,
|
|
|
/* The use is trivial invariant of the loop, i.e. is not changed
|
/* The use is trivial invariant of the loop, i.e. is not changed
|
inside the loop. */
|
inside the loop. */
|
GRD_INVARIANT,
|
GRD_INVARIANT,
|
|
|
/* The use is reached by initial value and a value from the
|
/* The use is reached by initial value and a value from the
|
previous iteration. */
|
previous iteration. */
|
GRD_MAYBE_BIV,
|
GRD_MAYBE_BIV,
|
|
|
/* The use has single dominating def. */
|
/* The use has single dominating def. */
|
GRD_SINGLE_DOM
|
GRD_SINGLE_DOM
|
};
|
};
|
|
|
/* Information about a biv. */
|
/* Information about a biv. */
|
|
|
struct biv_entry
|
struct biv_entry
|
{
|
{
|
unsigned regno; /* The register of the biv. */
|
unsigned regno; /* The register of the biv. */
|
struct rtx_iv iv; /* Value of the biv. */
|
struct rtx_iv iv; /* Value of the biv. */
|
};
|
};
|
|
|
static bool clean_slate = true;
|
static bool clean_slate = true;
|
|
|
static unsigned int iv_ref_table_size = 0;
|
static unsigned int iv_ref_table_size = 0;
|
|
|
/* Table of rtx_ivs indexed by the df_ref uid field. */
|
/* Table of rtx_ivs indexed by the df_ref uid field. */
|
static struct rtx_iv ** iv_ref_table;
|
static struct rtx_iv ** iv_ref_table;
|
|
|
/* Induction variable stored at the reference. */
|
/* Induction variable stored at the reference. */
|
#define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
|
#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)
|
#define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)
|
|
|
/* The current loop. */
|
/* The current loop. */
|
|
|
static struct loop *current_loop;
|
static struct loop *current_loop;
|
|
|
/* Bivs of the current loop. */
|
/* Bivs of the current loop. */
|
|
|
static htab_t bivs;
|
static htab_t bivs;
|
|
|
static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
|
static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);
|
|
|
/* Dumps information about IV to FILE. */
|
/* Dumps information about IV to FILE. */
|
|
|
extern void dump_iv_info (FILE *, struct rtx_iv *);
|
extern void dump_iv_info (FILE *, struct rtx_iv *);
|
void
|
void
|
dump_iv_info (FILE *file, struct rtx_iv *iv)
|
dump_iv_info (FILE *file, struct rtx_iv *iv)
|
{
|
{
|
if (!iv->base)
|
if (!iv->base)
|
{
|
{
|
fprintf (file, "not simple");
|
fprintf (file, "not simple");
|
return;
|
return;
|
}
|
}
|
|
|
if (iv->step == const0_rtx
|
if (iv->step == const0_rtx
|
&& !iv->first_special)
|
&& !iv->first_special)
|
fprintf (file, "invariant ");
|
fprintf (file, "invariant ");
|
|
|
print_rtl (file, iv->base);
|
print_rtl (file, iv->base);
|
if (iv->step != const0_rtx)
|
if (iv->step != const0_rtx)
|
{
|
{
|
fprintf (file, " + ");
|
fprintf (file, " + ");
|
print_rtl (file, iv->step);
|
print_rtl (file, iv->step);
|
fprintf (file, " * iteration");
|
fprintf (file, " * iteration");
|
}
|
}
|
fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
|
fprintf (file, " (in %s)", GET_MODE_NAME (iv->mode));
|
|
|
if (iv->mode != iv->extend_mode)
|
if (iv->mode != iv->extend_mode)
|
fprintf (file, " %s to %s",
|
fprintf (file, " %s to %s",
|
rtx_name[iv->extend],
|
rtx_name[iv->extend],
|
GET_MODE_NAME (iv->extend_mode));
|
GET_MODE_NAME (iv->extend_mode));
|
|
|
if (iv->mult != const1_rtx)
|
if (iv->mult != const1_rtx)
|
{
|
{
|
fprintf (file, " * ");
|
fprintf (file, " * ");
|
print_rtl (file, iv->mult);
|
print_rtl (file, iv->mult);
|
}
|
}
|
if (iv->delta != const0_rtx)
|
if (iv->delta != const0_rtx)
|
{
|
{
|
fprintf (file, " + ");
|
fprintf (file, " + ");
|
print_rtl (file, iv->delta);
|
print_rtl (file, iv->delta);
|
}
|
}
|
if (iv->first_special)
|
if (iv->first_special)
|
fprintf (file, " (first special)");
|
fprintf (file, " (first special)");
|
}
|
}
|
|
|
/* Generates a subreg to get the least significant part of EXPR (in mode
|
/* Generates a subreg to get the least significant part of EXPR (in mode
|
INNER_MODE) to OUTER_MODE. */
|
INNER_MODE) to OUTER_MODE. */
|
|
|
rtx
|
rtx
|
lowpart_subreg (enum machine_mode outer_mode, rtx expr,
|
lowpart_subreg (enum machine_mode outer_mode, rtx expr,
|
enum machine_mode inner_mode)
|
enum machine_mode inner_mode)
|
{
|
{
|
return simplify_gen_subreg (outer_mode, expr, inner_mode,
|
return simplify_gen_subreg (outer_mode, expr, inner_mode,
|
subreg_lowpart_offset (outer_mode, inner_mode));
|
subreg_lowpart_offset (outer_mode, inner_mode));
|
}
|
}
|
|
|
static void
|
static void
|
check_iv_ref_table_size (void)
|
check_iv_ref_table_size (void)
|
{
|
{
|
if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
|
if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
|
{
|
{
|
unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
|
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);
|
iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
|
memset (&iv_ref_table[iv_ref_table_size], 0,
|
memset (&iv_ref_table[iv_ref_table_size], 0,
|
(new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
|
(new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
|
iv_ref_table_size = new_size;
|
iv_ref_table_size = new_size;
|
}
|
}
|
}
|
}
|
|
|
|
|
/* Checks whether REG is a well-behaved register. */
|
/* Checks whether REG is a well-behaved register. */
|
|
|
static bool
|
static bool
|
simple_reg_p (rtx reg)
|
simple_reg_p (rtx reg)
|
{
|
{
|
unsigned r;
|
unsigned r;
|
|
|
if (GET_CODE (reg) == SUBREG)
|
if (GET_CODE (reg) == SUBREG)
|
{
|
{
|
if (!subreg_lowpart_p (reg))
|
if (!subreg_lowpart_p (reg))
|
return false;
|
return false;
|
reg = SUBREG_REG (reg);
|
reg = SUBREG_REG (reg);
|
}
|
}
|
|
|
if (!REG_P (reg))
|
if (!REG_P (reg))
|
return false;
|
return false;
|
|
|
r = REGNO (reg);
|
r = REGNO (reg);
|
if (HARD_REGISTER_NUM_P (r))
|
if (HARD_REGISTER_NUM_P (r))
|
return false;
|
return false;
|
|
|
if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
|
if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Clears the information about ivs stored in df. */
|
/* Clears the information about ivs stored in df. */
|
|
|
static void
|
static void
|
clear_iv_info (void)
|
clear_iv_info (void)
|
{
|
{
|
unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
|
unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
|
struct rtx_iv *iv;
|
struct rtx_iv *iv;
|
|
|
check_iv_ref_table_size ();
|
check_iv_ref_table_size ();
|
for (i = 0; i < n_defs; i++)
|
for (i = 0; i < n_defs; i++)
|
{
|
{
|
iv = iv_ref_table[i];
|
iv = iv_ref_table[i];
|
if (iv)
|
if (iv)
|
{
|
{
|
free (iv);
|
free (iv);
|
iv_ref_table[i] = NULL;
|
iv_ref_table[i] = NULL;
|
}
|
}
|
}
|
}
|
|
|
htab_empty (bivs);
|
htab_empty (bivs);
|
}
|
}
|
|
|
/* Returns hash value for biv B. */
|
/* Returns hash value for biv B. */
|
|
|
static hashval_t
|
static hashval_t
|
biv_hash (const void *b)
|
biv_hash (const void *b)
|
{
|
{
|
return ((const struct biv_entry *) b)->regno;
|
return ((const struct biv_entry *) b)->regno;
|
}
|
}
|
|
|
/* Compares biv B and register R. */
|
/* Compares biv B and register R. */
|
|
|
static int
|
static int
|
biv_eq (const void *b, const void *r)
|
biv_eq (const void *b, const void *r)
|
{
|
{
|
return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);
|
return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);
|
}
|
}
|
|
|
/* Prepare the data for an induction variable analysis of a LOOP. */
|
/* Prepare the data for an induction variable analysis of a LOOP. */
|
|
|
void
|
void
|
iv_analysis_loop_init (struct loop *loop)
|
iv_analysis_loop_init (struct loop *loop)
|
{
|
{
|
basic_block *body = get_loop_body_in_dom_order (loop), bb;
|
basic_block *body = get_loop_body_in_dom_order (loop), bb;
|
bitmap blocks = BITMAP_ALLOC (NULL);
|
bitmap blocks = BITMAP_ALLOC (NULL);
|
unsigned i;
|
unsigned i;
|
|
|
current_loop = loop;
|
current_loop = loop;
|
|
|
/* Clear the information from the analysis of the previous loop. */
|
/* Clear the information from the analysis of the previous loop. */
|
if (clean_slate)
|
if (clean_slate)
|
{
|
{
|
df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
|
df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
|
bivs = htab_create (10, biv_hash, biv_eq, free);
|
bivs = htab_create (10, biv_hash, biv_eq, free);
|
clean_slate = false;
|
clean_slate = false;
|
}
|
}
|
else
|
else
|
clear_iv_info ();
|
clear_iv_info ();
|
|
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
bb = body[i];
|
bb = body[i];
|
bitmap_set_bit (blocks, bb->index);
|
bitmap_set_bit (blocks, bb->index);
|
}
|
}
|
/* Get rid of the ud chains before processing the rescans. Then add
|
/* Get rid of the ud chains before processing the rescans. Then add
|
the problem back. */
|
the problem back. */
|
df_remove_problem (df_chain);
|
df_remove_problem (df_chain);
|
df_process_deferred_rescans ();
|
df_process_deferred_rescans ();
|
df_chain_add_problem (DF_UD_CHAIN);
|
df_chain_add_problem (DF_UD_CHAIN);
|
df_note_add_problem ();
|
df_note_add_problem ();
|
df_set_blocks (blocks);
|
df_set_blocks (blocks);
|
df_analyze ();
|
df_analyze ();
|
if (dump_file)
|
if (dump_file)
|
df_dump_region (dump_file);
|
df_dump_region (dump_file);
|
|
|
check_iv_ref_table_size ();
|
check_iv_ref_table_size ();
|
BITMAP_FREE (blocks);
|
BITMAP_FREE (blocks);
|
free (body);
|
free (body);
|
}
|
}
|
|
|
/* Finds the definition of REG that dominates loop latch and stores
|
/* Finds the definition of REG that dominates loop latch and stores
|
it to DEF. Returns false if there is not a single definition
|
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. If REG has no definition in loop, DEF
|
is set to NULL and true is returned. */
|
is set to NULL and true is returned. */
|
|
|
static bool
|
static bool
|
latch_dominating_def (rtx reg, df_ref *def)
|
latch_dominating_def (rtx reg, df_ref *def)
|
{
|
{
|
df_ref single_rd = NULL, adef;
|
df_ref single_rd = NULL, adef;
|
unsigned regno = REGNO (reg);
|
unsigned regno = REGNO (reg);
|
struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);
|
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))
|
for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))
|
{
|
{
|
if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
|
if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
|
|| !bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
|
|| !bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
|
continue;
|
continue;
|
|
|
/* More than one reaching definition. */
|
/* More than one reaching definition. */
|
if (single_rd)
|
if (single_rd)
|
return false;
|
return false;
|
|
|
if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
|
if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
|
return false;
|
return false;
|
|
|
single_rd = adef;
|
single_rd = adef;
|
}
|
}
|
|
|
*def = single_rd;
|
*def = single_rd;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Gets definition of REG reaching its use in INSN and stores it to DEF. */
|
/* Gets definition of REG reaching its use in INSN and stores it to DEF. */
|
|
|
static enum iv_grd_result
|
static enum iv_grd_result
|
iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
|
iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)
|
{
|
{
|
df_ref use, adef;
|
df_ref use, adef;
|
basic_block def_bb, use_bb;
|
basic_block def_bb, use_bb;
|
rtx def_insn;
|
rtx def_insn;
|
bool dom_p;
|
bool dom_p;
|
|
|
*def = NULL;
|
*def = NULL;
|
if (!simple_reg_p (reg))
|
if (!simple_reg_p (reg))
|
return GRD_INVALID;
|
return GRD_INVALID;
|
if (GET_CODE (reg) == SUBREG)
|
if (GET_CODE (reg) == SUBREG)
|
reg = SUBREG_REG (reg);
|
reg = SUBREG_REG (reg);
|
gcc_assert (REG_P (reg));
|
gcc_assert (REG_P (reg));
|
|
|
use = df_find_use (insn, reg);
|
use = df_find_use (insn, reg);
|
gcc_assert (use != NULL);
|
gcc_assert (use != NULL);
|
|
|
if (!DF_REF_CHAIN (use))
|
if (!DF_REF_CHAIN (use))
|
return GRD_INVARIANT;
|
return GRD_INVARIANT;
|
|
|
/* More than one reaching def. */
|
/* More than one reaching def. */
|
if (DF_REF_CHAIN (use)->next)
|
if (DF_REF_CHAIN (use)->next)
|
return GRD_INVALID;
|
return GRD_INVALID;
|
|
|
adef = DF_REF_CHAIN (use)->ref;
|
adef = DF_REF_CHAIN (use)->ref;
|
|
|
/* We do not handle setting only part of the register. */
|
/* We do not handle setting only part of the register. */
|
if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
|
if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
|
return GRD_INVALID;
|
return GRD_INVALID;
|
|
|
def_insn = DF_REF_INSN (adef);
|
def_insn = DF_REF_INSN (adef);
|
def_bb = DF_REF_BB (adef);
|
def_bb = DF_REF_BB (adef);
|
use_bb = BLOCK_FOR_INSN (insn);
|
use_bb = BLOCK_FOR_INSN (insn);
|
|
|
if (use_bb == def_bb)
|
if (use_bb == def_bb)
|
dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
|
dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
|
else
|
else
|
dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
|
dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
|
|
|
if (dom_p)
|
if (dom_p)
|
{
|
{
|
*def = adef;
|
*def = adef;
|
return GRD_SINGLE_DOM;
|
return GRD_SINGLE_DOM;
|
}
|
}
|
|
|
/* The definition does not dominate the use. This is still OK if
|
/* 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
|
this may be a use of a biv, i.e. if the def_bb dominates loop
|
latch. */
|
latch. */
|
if (just_once_each_iteration_p (current_loop, def_bb))
|
if (just_once_each_iteration_p (current_loop, def_bb))
|
return GRD_MAYBE_BIV;
|
return GRD_MAYBE_BIV;
|
|
|
return GRD_INVALID;
|
return GRD_INVALID;
|
}
|
}
|
|
|
/* Sets IV to invariant CST in MODE. Always returns true (just for
|
/* Sets IV to invariant CST in MODE. Always returns true (just for
|
consistency with other iv manipulation functions that may fail). */
|
consistency with other iv manipulation functions that may fail). */
|
|
|
static bool
|
static bool
|
iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
|
iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
|
{
|
{
|
if (mode == VOIDmode)
|
if (mode == VOIDmode)
|
mode = GET_MODE (cst);
|
mode = GET_MODE (cst);
|
|
|
iv->mode = mode;
|
iv->mode = mode;
|
iv->base = cst;
|
iv->base = cst;
|
iv->step = const0_rtx;
|
iv->step = const0_rtx;
|
iv->first_special = false;
|
iv->first_special = false;
|
iv->extend = UNKNOWN;
|
iv->extend = UNKNOWN;
|
iv->extend_mode = iv->mode;
|
iv->extend_mode = iv->mode;
|
iv->delta = const0_rtx;
|
iv->delta = const0_rtx;
|
iv->mult = const1_rtx;
|
iv->mult = const1_rtx;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Evaluates application of subreg to MODE on IV. */
|
/* Evaluates application of subreg to MODE on IV. */
|
|
|
static bool
|
static bool
|
iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
|
iv_subreg (struct rtx_iv *iv, enum machine_mode mode)
|
{
|
{
|
/* If iv is invariant, just calculate the new value. */
|
/* If iv is invariant, just calculate the new value. */
|
if (iv->step == const0_rtx
|
if (iv->step == const0_rtx
|
&& !iv->first_special)
|
&& !iv->first_special)
|
{
|
{
|
rtx val = get_iv_value (iv, const0_rtx);
|
rtx val = get_iv_value (iv, const0_rtx);
|
val = lowpart_subreg (mode, val, iv->extend_mode);
|
val = lowpart_subreg (mode, val, iv->extend_mode);
|
|
|
iv->base = val;
|
iv->base = val;
|
iv->extend = UNKNOWN;
|
iv->extend = UNKNOWN;
|
iv->mode = iv->extend_mode = mode;
|
iv->mode = iv->extend_mode = mode;
|
iv->delta = const0_rtx;
|
iv->delta = const0_rtx;
|
iv->mult = const1_rtx;
|
iv->mult = const1_rtx;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (iv->extend_mode == mode)
|
if (iv->extend_mode == mode)
|
return true;
|
return true;
|
|
|
if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
|
if (GET_MODE_BITSIZE (mode) > GET_MODE_BITSIZE (iv->mode))
|
return false;
|
return false;
|
|
|
iv->extend = UNKNOWN;
|
iv->extend = UNKNOWN;
|
iv->mode = mode;
|
iv->mode = mode;
|
|
|
iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
|
iv->base = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
iv->base, iv->mult));
|
iv->base, iv->mult));
|
iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
|
iv->step = simplify_gen_binary (MULT, iv->extend_mode, iv->step, iv->mult);
|
iv->mult = const1_rtx;
|
iv->mult = const1_rtx;
|
iv->delta = const0_rtx;
|
iv->delta = const0_rtx;
|
iv->first_special = false;
|
iv->first_special = false;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Evaluates application of EXTEND to MODE on IV. */
|
/* Evaluates application of EXTEND to MODE on IV. */
|
|
|
static bool
|
static bool
|
iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
|
iv_extend (struct rtx_iv *iv, enum rtx_code extend, enum machine_mode mode)
|
{
|
{
|
/* If iv is invariant, just calculate the new value. */
|
/* If iv is invariant, just calculate the new value. */
|
if (iv->step == const0_rtx
|
if (iv->step == const0_rtx
|
&& !iv->first_special)
|
&& !iv->first_special)
|
{
|
{
|
rtx val = get_iv_value (iv, const0_rtx);
|
rtx val = get_iv_value (iv, const0_rtx);
|
val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
|
val = simplify_gen_unary (extend, mode, val, iv->extend_mode);
|
|
|
iv->base = val;
|
iv->base = val;
|
iv->extend = UNKNOWN;
|
iv->extend = UNKNOWN;
|
iv->mode = iv->extend_mode = mode;
|
iv->mode = iv->extend_mode = mode;
|
iv->delta = const0_rtx;
|
iv->delta = const0_rtx;
|
iv->mult = const1_rtx;
|
iv->mult = const1_rtx;
|
return true;
|
return true;
|
}
|
}
|
|
|
if (mode != iv->extend_mode)
|
if (mode != iv->extend_mode)
|
return false;
|
return false;
|
|
|
if (iv->extend != UNKNOWN
|
if (iv->extend != UNKNOWN
|
&& iv->extend != extend)
|
&& iv->extend != extend)
|
return false;
|
return false;
|
|
|
iv->extend = extend;
|
iv->extend = extend;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Evaluates negation of IV. */
|
/* Evaluates negation of IV. */
|
|
|
static bool
|
static bool
|
iv_neg (struct rtx_iv *iv)
|
iv_neg (struct rtx_iv *iv)
|
{
|
{
|
if (iv->extend == UNKNOWN)
|
if (iv->extend == UNKNOWN)
|
{
|
{
|
iv->base = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->base = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->base, iv->extend_mode);
|
iv->base, iv->extend_mode);
|
iv->step = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->step = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->step, iv->extend_mode);
|
iv->step, iv->extend_mode);
|
}
|
}
|
else
|
else
|
{
|
{
|
iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->delta = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->delta, iv->extend_mode);
|
iv->delta, iv->extend_mode);
|
iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->mult = simplify_gen_unary (NEG, iv->extend_mode,
|
iv->mult, iv->extend_mode);
|
iv->mult, iv->extend_mode);
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
|
/* Evaluates addition or subtraction (according to OP) of IV1 to IV0. */
|
|
|
static bool
|
static bool
|
iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
|
iv_add (struct rtx_iv *iv0, struct rtx_iv *iv1, enum rtx_code op)
|
{
|
{
|
enum machine_mode mode;
|
enum machine_mode mode;
|
rtx arg;
|
rtx arg;
|
|
|
/* Extend the constant to extend_mode of the other operand if necessary. */
|
/* Extend the constant to extend_mode of the other operand if necessary. */
|
if (iv0->extend == UNKNOWN
|
if (iv0->extend == UNKNOWN
|
&& iv0->mode == iv0->extend_mode
|
&& iv0->mode == iv0->extend_mode
|
&& iv0->step == const0_rtx
|
&& iv0->step == const0_rtx
|
&& GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
|
&& GET_MODE_SIZE (iv0->extend_mode) < GET_MODE_SIZE (iv1->extend_mode))
|
{
|
{
|
iv0->extend_mode = iv1->extend_mode;
|
iv0->extend_mode = iv1->extend_mode;
|
iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
|
iv0->base = simplify_gen_unary (ZERO_EXTEND, iv0->extend_mode,
|
iv0->base, iv0->mode);
|
iv0->base, iv0->mode);
|
}
|
}
|
if (iv1->extend == UNKNOWN
|
if (iv1->extend == UNKNOWN
|
&& iv1->mode == iv1->extend_mode
|
&& iv1->mode == iv1->extend_mode
|
&& iv1->step == const0_rtx
|
&& iv1->step == const0_rtx
|
&& GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
|
&& GET_MODE_SIZE (iv1->extend_mode) < GET_MODE_SIZE (iv0->extend_mode))
|
{
|
{
|
iv1->extend_mode = iv0->extend_mode;
|
iv1->extend_mode = iv0->extend_mode;
|
iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
|
iv1->base = simplify_gen_unary (ZERO_EXTEND, iv1->extend_mode,
|
iv1->base, iv1->mode);
|
iv1->base, iv1->mode);
|
}
|
}
|
|
|
mode = iv0->extend_mode;
|
mode = iv0->extend_mode;
|
if (mode != iv1->extend_mode)
|
if (mode != iv1->extend_mode)
|
return false;
|
return false;
|
|
|
if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
|
if (iv0->extend == UNKNOWN && iv1->extend == UNKNOWN)
|
{
|
{
|
if (iv0->mode != iv1->mode)
|
if (iv0->mode != iv1->mode)
|
return false;
|
return false;
|
|
|
iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
|
iv0->base = simplify_gen_binary (op, mode, iv0->base, iv1->base);
|
iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
|
iv0->step = simplify_gen_binary (op, mode, iv0->step, iv1->step);
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Handle addition of constant. */
|
/* Handle addition of constant. */
|
if (iv1->extend == UNKNOWN
|
if (iv1->extend == UNKNOWN
|
&& iv1->mode == mode
|
&& iv1->mode == mode
|
&& iv1->step == const0_rtx)
|
&& iv1->step == const0_rtx)
|
{
|
{
|
iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
|
iv0->delta = simplify_gen_binary (op, mode, iv0->delta, iv1->base);
|
return true;
|
return true;
|
}
|
}
|
|
|
if (iv0->extend == UNKNOWN
|
if (iv0->extend == UNKNOWN
|
&& iv0->mode == mode
|
&& iv0->mode == mode
|
&& iv0->step == const0_rtx)
|
&& iv0->step == const0_rtx)
|
{
|
{
|
arg = iv0->base;
|
arg = iv0->base;
|
*iv0 = *iv1;
|
*iv0 = *iv1;
|
if (op == MINUS
|
if (op == MINUS
|
&& !iv_neg (iv0))
|
&& !iv_neg (iv0))
|
return false;
|
return false;
|
|
|
iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
|
iv0->delta = simplify_gen_binary (PLUS, mode, iv0->delta, arg);
|
return true;
|
return true;
|
}
|
}
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Evaluates multiplication of IV by constant CST. */
|
/* Evaluates multiplication of IV by constant CST. */
|
|
|
static bool
|
static bool
|
iv_mult (struct rtx_iv *iv, rtx mby)
|
iv_mult (struct rtx_iv *iv, rtx mby)
|
{
|
{
|
enum machine_mode mode = iv->extend_mode;
|
enum machine_mode mode = iv->extend_mode;
|
|
|
if (GET_MODE (mby) != VOIDmode
|
if (GET_MODE (mby) != VOIDmode
|
&& GET_MODE (mby) != mode)
|
&& GET_MODE (mby) != mode)
|
return false;
|
return false;
|
|
|
if (iv->extend == UNKNOWN)
|
if (iv->extend == UNKNOWN)
|
{
|
{
|
iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
|
iv->base = simplify_gen_binary (MULT, mode, iv->base, mby);
|
iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
|
iv->step = simplify_gen_binary (MULT, mode, iv->step, mby);
|
}
|
}
|
else
|
else
|
{
|
{
|
iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
|
iv->delta = simplify_gen_binary (MULT, mode, iv->delta, mby);
|
iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
|
iv->mult = simplify_gen_binary (MULT, mode, iv->mult, mby);
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Evaluates shift of IV by constant CST. */
|
/* Evaluates shift of IV by constant CST. */
|
|
|
static bool
|
static bool
|
iv_shift (struct rtx_iv *iv, rtx mby)
|
iv_shift (struct rtx_iv *iv, rtx mby)
|
{
|
{
|
enum machine_mode mode = iv->extend_mode;
|
enum machine_mode mode = iv->extend_mode;
|
|
|
if (GET_MODE (mby) != VOIDmode
|
if (GET_MODE (mby) != VOIDmode
|
&& GET_MODE (mby) != mode)
|
&& GET_MODE (mby) != mode)
|
return false;
|
return false;
|
|
|
if (iv->extend == UNKNOWN)
|
if (iv->extend == UNKNOWN)
|
{
|
{
|
iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
|
iv->base = simplify_gen_binary (ASHIFT, mode, iv->base, mby);
|
iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
|
iv->step = simplify_gen_binary (ASHIFT, mode, iv->step, mby);
|
}
|
}
|
else
|
else
|
{
|
{
|
iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
|
iv->delta = simplify_gen_binary (ASHIFT, mode, iv->delta, mby);
|
iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
|
iv->mult = simplify_gen_binary (ASHIFT, mode, iv->mult, mby);
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* The recursive part of get_biv_step. Gets the value of the single value
|
/* The recursive part of get_biv_step. Gets the value of the single value
|
defined by DEF 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. */
|
at get_biv_step. */
|
|
|
static bool
|
static bool
|
get_biv_step_1 (df_ref def, rtx reg,
|
get_biv_step_1 (df_ref def, rtx reg,
|
rtx *inner_step, enum machine_mode *inner_mode,
|
rtx *inner_step, enum machine_mode *inner_mode,
|
enum rtx_code *extend, enum machine_mode outer_mode,
|
enum rtx_code *extend, enum machine_mode outer_mode,
|
rtx *outer_step)
|
rtx *outer_step)
|
{
|
{
|
rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
|
rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
|
rtx next, nextr, tmp;
|
rtx next, nextr, tmp;
|
enum rtx_code code;
|
enum rtx_code code;
|
rtx insn = DF_REF_INSN (def);
|
rtx insn = DF_REF_INSN (def);
|
df_ref next_def;
|
df_ref next_def;
|
enum iv_grd_result res;
|
enum iv_grd_result res;
|
|
|
set = single_set (insn);
|
set = single_set (insn);
|
if (!set)
|
if (!set)
|
return false;
|
return false;
|
|
|
rhs = find_reg_equal_equiv_note (insn);
|
rhs = find_reg_equal_equiv_note (insn);
|
if (rhs)
|
if (rhs)
|
rhs = XEXP (rhs, 0);
|
rhs = XEXP (rhs, 0);
|
else
|
else
|
rhs = SET_SRC (set);
|
rhs = SET_SRC (set);
|
|
|
code = GET_CODE (rhs);
|
code = GET_CODE (rhs);
|
switch (code)
|
switch (code)
|
{
|
{
|
case SUBREG:
|
case SUBREG:
|
case REG:
|
case REG:
|
next = rhs;
|
next = rhs;
|
break;
|
break;
|
|
|
case PLUS:
|
case PLUS:
|
case MINUS:
|
case MINUS:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
op1 = XEXP (rhs, 1);
|
op1 = XEXP (rhs, 1);
|
|
|
if (code == PLUS && CONSTANT_P (op0))
|
if (code == PLUS && CONSTANT_P (op0))
|
{
|
{
|
tmp = op0; op0 = op1; op1 = tmp;
|
tmp = op0; op0 = op1; op1 = tmp;
|
}
|
}
|
|
|
if (!simple_reg_p (op0)
|
if (!simple_reg_p (op0)
|
|| !CONSTANT_P (op1))
|
|| !CONSTANT_P (op1))
|
return false;
|
return false;
|
|
|
if (GET_MODE (rhs) != outer_mode)
|
if (GET_MODE (rhs) != outer_mode)
|
{
|
{
|
/* ppc64 uses expressions like
|
/* ppc64 uses expressions like
|
|
|
(set x:SI (plus:SI (subreg:SI y:DI) 1)).
|
(set x:SI (plus:SI (subreg:SI y:DI) 1)).
|
|
|
this is equivalent to
|
this is equivalent to
|
|
|
(set x':DI (plus:DI y:DI 1))
|
(set x':DI (plus:DI y:DI 1))
|
(set x:SI (subreg:SI (x':DI)). */
|
(set x:SI (subreg:SI (x':DI)). */
|
if (GET_CODE (op0) != SUBREG)
|
if (GET_CODE (op0) != SUBREG)
|
return false;
|
return false;
|
if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
|
if (GET_MODE (SUBREG_REG (op0)) != outer_mode)
|
return false;
|
return false;
|
}
|
}
|
|
|
next = op0;
|
next = op0;
|
break;
|
break;
|
|
|
case SIGN_EXTEND:
|
case SIGN_EXTEND:
|
case ZERO_EXTEND:
|
case ZERO_EXTEND:
|
if (GET_MODE (rhs) != outer_mode)
|
if (GET_MODE (rhs) != outer_mode)
|
return false;
|
return false;
|
|
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
if (!simple_reg_p (op0))
|
if (!simple_reg_p (op0))
|
return false;
|
return false;
|
|
|
next = op0;
|
next = op0;
|
break;
|
break;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
|
|
if (GET_CODE (next) == SUBREG)
|
if (GET_CODE (next) == SUBREG)
|
{
|
{
|
if (!subreg_lowpart_p (next))
|
if (!subreg_lowpart_p (next))
|
return false;
|
return false;
|
|
|
nextr = SUBREG_REG (next);
|
nextr = SUBREG_REG (next);
|
if (GET_MODE (nextr) != outer_mode)
|
if (GET_MODE (nextr) != outer_mode)
|
return false;
|
return false;
|
}
|
}
|
else
|
else
|
nextr = next;
|
nextr = next;
|
|
|
res = iv_get_reaching_def (insn, nextr, &next_def);
|
res = iv_get_reaching_def (insn, nextr, &next_def);
|
|
|
if (res == GRD_INVALID || res == GRD_INVARIANT)
|
if (res == GRD_INVALID || res == GRD_INVARIANT)
|
return false;
|
return false;
|
|
|
if (res == GRD_MAYBE_BIV)
|
if (res == GRD_MAYBE_BIV)
|
{
|
{
|
if (!rtx_equal_p (nextr, reg))
|
if (!rtx_equal_p (nextr, reg))
|
return false;
|
return false;
|
|
|
*inner_step = const0_rtx;
|
*inner_step = const0_rtx;
|
*extend = UNKNOWN;
|
*extend = UNKNOWN;
|
*inner_mode = outer_mode;
|
*inner_mode = outer_mode;
|
*outer_step = const0_rtx;
|
*outer_step = const0_rtx;
|
}
|
}
|
else if (!get_biv_step_1 (next_def, reg,
|
else if (!get_biv_step_1 (next_def, reg,
|
inner_step, inner_mode, extend, outer_mode,
|
inner_step, inner_mode, extend, outer_mode,
|
outer_step))
|
outer_step))
|
return false;
|
return false;
|
|
|
if (GET_CODE (next) == SUBREG)
|
if (GET_CODE (next) == SUBREG)
|
{
|
{
|
enum machine_mode amode = GET_MODE (next);
|
enum machine_mode amode = GET_MODE (next);
|
|
|
if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
|
if (GET_MODE_SIZE (amode) > GET_MODE_SIZE (*inner_mode))
|
return false;
|
return false;
|
|
|
*inner_mode = amode;
|
*inner_mode = amode;
|
*inner_step = simplify_gen_binary (PLUS, outer_mode,
|
*inner_step = simplify_gen_binary (PLUS, outer_mode,
|
*inner_step, *outer_step);
|
*inner_step, *outer_step);
|
*outer_step = const0_rtx;
|
*outer_step = const0_rtx;
|
*extend = UNKNOWN;
|
*extend = UNKNOWN;
|
}
|
}
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case REG:
|
case REG:
|
case SUBREG:
|
case SUBREG:
|
break;
|
break;
|
|
|
case PLUS:
|
case PLUS:
|
case MINUS:
|
case MINUS:
|
if (*inner_mode == outer_mode
|
if (*inner_mode == outer_mode
|
/* See comment in previous switch. */
|
/* See comment in previous switch. */
|
|| GET_MODE (rhs) != outer_mode)
|
|| GET_MODE (rhs) != outer_mode)
|
*inner_step = simplify_gen_binary (code, outer_mode,
|
*inner_step = simplify_gen_binary (code, outer_mode,
|
*inner_step, op1);
|
*inner_step, op1);
|
else
|
else
|
*outer_step = simplify_gen_binary (code, outer_mode,
|
*outer_step = simplify_gen_binary (code, outer_mode,
|
*outer_step, op1);
|
*outer_step, op1);
|
break;
|
break;
|
|
|
case SIGN_EXTEND:
|
case SIGN_EXTEND:
|
case ZERO_EXTEND:
|
case ZERO_EXTEND:
|
gcc_assert (GET_MODE (op0) == *inner_mode
|
gcc_assert (GET_MODE (op0) == *inner_mode
|
&& *extend == UNKNOWN
|
&& *extend == UNKNOWN
|
&& *outer_step == const0_rtx);
|
&& *outer_step == const0_rtx);
|
|
|
*extend = code;
|
*extend = code;
|
break;
|
break;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Gets the operation on register REG inside loop, in shape
|
/* Gets the operation on register REG inside loop, in shape
|
|
|
OUTER_STEP + EXTEND_{OUTER_MODE} (SUBREG_{INNER_MODE} (REG + INNER_STEP))
|
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. */
|
LAST_DEF is the definition of REG that dominates loop latch. */
|
|
|
static bool
|
static bool
|
get_biv_step (df_ref last_def, rtx reg, rtx *inner_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 *inner_mode, enum rtx_code *extend,
|
enum machine_mode *outer_mode, rtx *outer_step)
|
enum machine_mode *outer_mode, rtx *outer_step)
|
{
|
{
|
*outer_mode = GET_MODE (reg);
|
*outer_mode = GET_MODE (reg);
|
|
|
if (!get_biv_step_1 (last_def, reg,
|
if (!get_biv_step_1 (last_def, reg,
|
inner_step, inner_mode, extend, *outer_mode,
|
inner_step, inner_mode, extend, *outer_mode,
|
outer_step))
|
outer_step))
|
return false;
|
return false;
|
|
|
gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
|
gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
|
gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
|
gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Records information that DEF is induction variable IV. */
|
/* Records information that DEF is induction variable IV. */
|
|
|
static void
|
static void
|
record_iv (df_ref def, struct rtx_iv *iv)
|
record_iv (df_ref def, struct rtx_iv *iv)
|
{
|
{
|
struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
|
struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
|
|
|
*recorded_iv = *iv;
|
*recorded_iv = *iv;
|
check_iv_ref_table_size ();
|
check_iv_ref_table_size ();
|
DF_REF_IV_SET (def, recorded_iv);
|
DF_REF_IV_SET (def, recorded_iv);
|
}
|
}
|
|
|
/* If DEF was already analyzed for bivness, store the description of the biv to
|
/* If DEF was already analyzed for bivness, store the description of the biv to
|
IV and return true. Otherwise return false. */
|
IV and return true. Otherwise return false. */
|
|
|
static bool
|
static bool
|
analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
|
analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
|
{
|
{
|
struct biv_entry *biv =
|
struct biv_entry *biv =
|
(struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));
|
(struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));
|
|
|
if (!biv)
|
if (!biv)
|
return false;
|
return false;
|
|
|
*iv = biv->iv;
|
*iv = biv->iv;
|
return true;
|
return true;
|
}
|
}
|
|
|
static void
|
static void
|
record_biv (rtx def, struct rtx_iv *iv)
|
record_biv (rtx def, struct rtx_iv *iv)
|
{
|
{
|
struct biv_entry *biv = XNEW (struct biv_entry);
|
struct biv_entry *biv = XNEW (struct biv_entry);
|
void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
|
void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
|
|
|
biv->regno = REGNO (def);
|
biv->regno = REGNO (def);
|
biv->iv = *iv;
|
biv->iv = *iv;
|
gcc_assert (!*slot);
|
gcc_assert (!*slot);
|
*slot = biv;
|
*slot = biv;
|
}
|
}
|
|
|
/* Determines whether DEF is a biv and if so, stores its description
|
/* Determines whether DEF is a biv and if so, stores its description
|
to *IV. */
|
to *IV. */
|
|
|
static bool
|
static bool
|
iv_analyze_biv (rtx def, struct rtx_iv *iv)
|
iv_analyze_biv (rtx def, struct rtx_iv *iv)
|
{
|
{
|
rtx inner_step, outer_step;
|
rtx inner_step, outer_step;
|
enum machine_mode inner_mode, outer_mode;
|
enum machine_mode inner_mode, outer_mode;
|
enum rtx_code extend;
|
enum rtx_code extend;
|
df_ref last_def;
|
df_ref last_def;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Analyzing ");
|
fprintf (dump_file, "Analyzing ");
|
print_rtl (dump_file, def);
|
print_rtl (dump_file, def);
|
fprintf (dump_file, " for bivness.\n");
|
fprintf (dump_file, " for bivness.\n");
|
}
|
}
|
|
|
if (!REG_P (def))
|
if (!REG_P (def))
|
{
|
{
|
if (!CONSTANT_P (def))
|
if (!CONSTANT_P (def))
|
return false;
|
return false;
|
|
|
return iv_constant (iv, def, VOIDmode);
|
return iv_constant (iv, def, VOIDmode);
|
}
|
}
|
|
|
if (!latch_dominating_def (def, &last_def))
|
if (!latch_dominating_def (def, &last_def))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, " not simple.\n");
|
fprintf (dump_file, " not simple.\n");
|
return false;
|
return false;
|
}
|
}
|
|
|
if (!last_def)
|
if (!last_def)
|
return iv_constant (iv, def, VOIDmode);
|
return iv_constant (iv, def, VOIDmode);
|
|
|
if (analyzed_for_bivness_p (def, iv))
|
if (analyzed_for_bivness_p (def, iv))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, " already analysed.\n");
|
fprintf (dump_file, " already analysed.\n");
|
return iv->base != NULL_RTX;
|
return iv->base != NULL_RTX;
|
}
|
}
|
|
|
if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
|
if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,
|
&outer_mode, &outer_step))
|
&outer_mode, &outer_step))
|
{
|
{
|
iv->base = NULL_RTX;
|
iv->base = NULL_RTX;
|
goto end;
|
goto end;
|
}
|
}
|
|
|
/* Loop transforms base to es (base + inner_step) + outer_step,
|
/* Loop transforms base to es (base + inner_step) + outer_step,
|
where es means extend of subreg between inner_mode and outer_mode.
|
where es means extend of subreg between inner_mode and outer_mode.
|
The corresponding induction variable is
|
The corresponding induction variable is
|
|
|
es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
|
es ((base - outer_step) + i * (inner_step + outer_step)) + outer_step */
|
|
|
iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
|
iv->base = simplify_gen_binary (MINUS, outer_mode, def, outer_step);
|
iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
|
iv->step = simplify_gen_binary (PLUS, outer_mode, inner_step, outer_step);
|
iv->mode = inner_mode;
|
iv->mode = inner_mode;
|
iv->extend_mode = outer_mode;
|
iv->extend_mode = outer_mode;
|
iv->extend = extend;
|
iv->extend = extend;
|
iv->mult = const1_rtx;
|
iv->mult = const1_rtx;
|
iv->delta = outer_step;
|
iv->delta = outer_step;
|
iv->first_special = inner_mode != outer_mode;
|
iv->first_special = inner_mode != outer_mode;
|
|
|
end:
|
end:
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, " ");
|
fprintf (dump_file, " ");
|
dump_iv_info (dump_file, iv);
|
dump_iv_info (dump_file, iv);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
record_biv (def, iv);
|
record_biv (def, iv);
|
return iv->base != NULL_RTX;
|
return iv->base != NULL_RTX;
|
}
|
}
|
|
|
/* Analyzes expression RHS used at 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. */
|
The mode of the induction variable is MODE. */
|
|
|
bool
|
bool
|
iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
|
iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)
|
{
|
{
|
rtx mby = NULL_RTX, tmp;
|
rtx mby = NULL_RTX, tmp;
|
rtx op0 = NULL_RTX, op1 = NULL_RTX;
|
rtx op0 = NULL_RTX, op1 = NULL_RTX;
|
struct rtx_iv iv0, iv1;
|
struct rtx_iv iv0, iv1;
|
enum rtx_code code = GET_CODE (rhs);
|
enum rtx_code code = GET_CODE (rhs);
|
enum machine_mode omode = mode;
|
enum machine_mode omode = mode;
|
|
|
iv->mode = VOIDmode;
|
iv->mode = VOIDmode;
|
iv->base = NULL_RTX;
|
iv->base = NULL_RTX;
|
iv->step = NULL_RTX;
|
iv->step = NULL_RTX;
|
|
|
gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
|
gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);
|
|
|
if (CONSTANT_P (rhs)
|
if (CONSTANT_P (rhs)
|
|| REG_P (rhs)
|
|| REG_P (rhs)
|
|| code == SUBREG)
|
|| code == SUBREG)
|
{
|
{
|
if (!iv_analyze_op (insn, rhs, iv))
|
if (!iv_analyze_op (insn, rhs, iv))
|
return false;
|
return false;
|
|
|
if (iv->mode == VOIDmode)
|
if (iv->mode == VOIDmode)
|
{
|
{
|
iv->mode = mode;
|
iv->mode = mode;
|
iv->extend_mode = mode;
|
iv->extend_mode = mode;
|
}
|
}
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case REG:
|
case REG:
|
op0 = rhs;
|
op0 = rhs;
|
break;
|
break;
|
|
|
case SIGN_EXTEND:
|
case SIGN_EXTEND:
|
case ZERO_EXTEND:
|
case ZERO_EXTEND:
|
case NEG:
|
case NEG:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
omode = GET_MODE (op0);
|
omode = GET_MODE (op0);
|
break;
|
break;
|
|
|
case PLUS:
|
case PLUS:
|
case MINUS:
|
case MINUS:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
op1 = XEXP (rhs, 1);
|
op1 = XEXP (rhs, 1);
|
break;
|
break;
|
|
|
case MULT:
|
case MULT:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
mby = XEXP (rhs, 1);
|
mby = XEXP (rhs, 1);
|
if (!CONSTANT_P (mby))
|
if (!CONSTANT_P (mby))
|
{
|
{
|
tmp = op0;
|
tmp = op0;
|
op0 = mby;
|
op0 = mby;
|
mby = tmp;
|
mby = tmp;
|
}
|
}
|
if (!CONSTANT_P (mby))
|
if (!CONSTANT_P (mby))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case ASHIFT:
|
case ASHIFT:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
mby = XEXP (rhs, 1);
|
mby = XEXP (rhs, 1);
|
if (!CONSTANT_P (mby))
|
if (!CONSTANT_P (mby))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
|
|
if (op0
|
if (op0
|
&& !iv_analyze_expr (insn, op0, omode, &iv0))
|
&& !iv_analyze_expr (insn, op0, omode, &iv0))
|
return false;
|
return false;
|
|
|
if (op1
|
if (op1
|
&& !iv_analyze_expr (insn, op1, omode, &iv1))
|
&& !iv_analyze_expr (insn, op1, omode, &iv1))
|
return false;
|
return false;
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case SIGN_EXTEND:
|
case SIGN_EXTEND:
|
case ZERO_EXTEND:
|
case ZERO_EXTEND:
|
if (!iv_extend (&iv0, code, mode))
|
if (!iv_extend (&iv0, code, mode))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case NEG:
|
case NEG:
|
if (!iv_neg (&iv0))
|
if (!iv_neg (&iv0))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case PLUS:
|
case PLUS:
|
case MINUS:
|
case MINUS:
|
if (!iv_add (&iv0, &iv1, code))
|
if (!iv_add (&iv0, &iv1, code))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case MULT:
|
case MULT:
|
if (!iv_mult (&iv0, mby))
|
if (!iv_mult (&iv0, mby))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
case ASHIFT:
|
case ASHIFT:
|
if (!iv_shift (&iv0, mby))
|
if (!iv_shift (&iv0, mby))
|
return false;
|
return false;
|
break;
|
break;
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
|
|
*iv = iv0;
|
*iv = iv0;
|
return iv->base != NULL_RTX;
|
return iv->base != NULL_RTX;
|
}
|
}
|
|
|
/* Analyzes iv DEF and stores the result to *IV. */
|
/* Analyzes iv DEF and stores the result to *IV. */
|
|
|
static bool
|
static bool
|
iv_analyze_def (df_ref def, struct rtx_iv *iv)
|
iv_analyze_def (df_ref def, struct rtx_iv *iv)
|
{
|
{
|
rtx insn = DF_REF_INSN (def);
|
rtx insn = DF_REF_INSN (def);
|
rtx reg = DF_REF_REG (def);
|
rtx reg = DF_REF_REG (def);
|
rtx set, rhs;
|
rtx set, rhs;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Analyzing def of ");
|
fprintf (dump_file, "Analyzing def of ");
|
print_rtl (dump_file, reg);
|
print_rtl (dump_file, reg);
|
fprintf (dump_file, " in insn ");
|
fprintf (dump_file, " in insn ");
|
print_rtl_single (dump_file, insn);
|
print_rtl_single (dump_file, insn);
|
}
|
}
|
|
|
check_iv_ref_table_size ();
|
check_iv_ref_table_size ();
|
if (DF_REF_IV (def))
|
if (DF_REF_IV (def))
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, " already analysed.\n");
|
fprintf (dump_file, " already analysed.\n");
|
*iv = *DF_REF_IV (def);
|
*iv = *DF_REF_IV (def);
|
return iv->base != NULL_RTX;
|
return iv->base != NULL_RTX;
|
}
|
}
|
|
|
iv->mode = VOIDmode;
|
iv->mode = VOIDmode;
|
iv->base = NULL_RTX;
|
iv->base = NULL_RTX;
|
iv->step = NULL_RTX;
|
iv->step = NULL_RTX;
|
|
|
if (!REG_P (reg))
|
if (!REG_P (reg))
|
return false;
|
return false;
|
|
|
set = single_set (insn);
|
set = single_set (insn);
|
if (!set)
|
if (!set)
|
return false;
|
return false;
|
|
|
if (!REG_P (SET_DEST (set)))
|
if (!REG_P (SET_DEST (set)))
|
return false;
|
return false;
|
|
|
gcc_assert (SET_DEST (set) == reg);
|
gcc_assert (SET_DEST (set) == reg);
|
rhs = find_reg_equal_equiv_note (insn);
|
rhs = find_reg_equal_equiv_note (insn);
|
if (rhs)
|
if (rhs)
|
rhs = XEXP (rhs, 0);
|
rhs = XEXP (rhs, 0);
|
else
|
else
|
rhs = SET_SRC (set);
|
rhs = SET_SRC (set);
|
|
|
iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
|
iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
|
record_iv (def, iv);
|
record_iv (def, iv);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
print_rtl (dump_file, reg);
|
print_rtl (dump_file, reg);
|
fprintf (dump_file, " in insn ");
|
fprintf (dump_file, " in insn ");
|
print_rtl_single (dump_file, insn);
|
print_rtl_single (dump_file, insn);
|
fprintf (dump_file, " is ");
|
fprintf (dump_file, " is ");
|
dump_iv_info (dump_file, iv);
|
dump_iv_info (dump_file, iv);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
return iv->base != NULL_RTX;
|
return iv->base != NULL_RTX;
|
}
|
}
|
|
|
/* Analyzes operand OP of INSN and stores the result to *IV. */
|
/* Analyzes operand OP of INSN and stores the result to *IV. */
|
|
|
static bool
|
static bool
|
iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
|
iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
|
{
|
{
|
df_ref def = NULL;
|
df_ref def = NULL;
|
enum iv_grd_result res;
|
enum iv_grd_result res;
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, "Analyzing operand ");
|
fprintf (dump_file, "Analyzing operand ");
|
print_rtl (dump_file, op);
|
print_rtl (dump_file, op);
|
fprintf (dump_file, " of insn ");
|
fprintf (dump_file, " of insn ");
|
print_rtl_single (dump_file, insn);
|
print_rtl_single (dump_file, insn);
|
}
|
}
|
|
|
if (function_invariant_p (op))
|
if (function_invariant_p (op))
|
res = GRD_INVARIANT;
|
res = GRD_INVARIANT;
|
else if (GET_CODE (op) == SUBREG)
|
else if (GET_CODE (op) == SUBREG)
|
{
|
{
|
if (!subreg_lowpart_p (op))
|
if (!subreg_lowpart_p (op))
|
return false;
|
return false;
|
|
|
if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
|
if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
|
return false;
|
return false;
|
|
|
return iv_subreg (iv, GET_MODE (op));
|
return iv_subreg (iv, GET_MODE (op));
|
}
|
}
|
else
|
else
|
{
|
{
|
res = iv_get_reaching_def (insn, op, &def);
|
res = iv_get_reaching_def (insn, op, &def);
|
if (res == GRD_INVALID)
|
if (res == GRD_INVALID)
|
{
|
{
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, " not simple.\n");
|
fprintf (dump_file, " not simple.\n");
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
if (res == GRD_INVARIANT)
|
if (res == GRD_INVARIANT)
|
{
|
{
|
iv_constant (iv, op, VOIDmode);
|
iv_constant (iv, op, VOIDmode);
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
fprintf (dump_file, " ");
|
fprintf (dump_file, " ");
|
dump_iv_info (dump_file, iv);
|
dump_iv_info (dump_file, iv);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
return true;
|
return true;
|
}
|
}
|
|
|
if (res == GRD_MAYBE_BIV)
|
if (res == GRD_MAYBE_BIV)
|
return iv_analyze_biv (op, iv);
|
return iv_analyze_biv (op, iv);
|
|
|
return iv_analyze_def (def, iv);
|
return iv_analyze_def (def, iv);
|
}
|
}
|
|
|
/* Analyzes value VAL at INSN and stores the result to *IV. */
|
/* Analyzes value VAL at INSN and stores the result to *IV. */
|
|
|
bool
|
bool
|
iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
|
iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
|
{
|
{
|
rtx reg;
|
rtx reg;
|
|
|
/* We must find the insn in that val is used, so that we get to UD chains.
|
/* 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,
|
Since the function is sometimes called on result of get_condition,
|
this does not necessarily have to be directly INSN; scan also the
|
this does not necessarily have to be directly INSN; scan also the
|
following insns. */
|
following insns. */
|
if (simple_reg_p (val))
|
if (simple_reg_p (val))
|
{
|
{
|
if (GET_CODE (val) == SUBREG)
|
if (GET_CODE (val) == SUBREG)
|
reg = SUBREG_REG (val);
|
reg = SUBREG_REG (val);
|
else
|
else
|
reg = val;
|
reg = val;
|
|
|
while (!df_find_use (insn, reg))
|
while (!df_find_use (insn, reg))
|
insn = NEXT_INSN (insn);
|
insn = NEXT_INSN (insn);
|
}
|
}
|
|
|
return iv_analyze_op (insn, val, iv);
|
return iv_analyze_op (insn, val, iv);
|
}
|
}
|
|
|
/* Analyzes definition of DEF in INSN and stores the result to IV. */
|
/* Analyzes definition of DEF in INSN and stores the result to IV. */
|
|
|
bool
|
bool
|
iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
|
iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
|
{
|
{
|
df_ref adef;
|
df_ref adef;
|
|
|
adef = df_find_def (insn, def);
|
adef = df_find_def (insn, def);
|
if (!adef)
|
if (!adef)
|
return false;
|
return false;
|
|
|
return iv_analyze_def (adef, iv);
|
return iv_analyze_def (adef, iv);
|
}
|
}
|
|
|
/* Checks whether definition of register REG in INSN is 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
|
variable. IV analysis must have been initialized (via a call to
|
iv_analysis_loop_init) for this function to produce a result. */
|
iv_analysis_loop_init) for this function to produce a result. */
|
|
|
bool
|
bool
|
biv_p (rtx insn, rtx reg)
|
biv_p (rtx insn, rtx reg)
|
{
|
{
|
struct rtx_iv iv;
|
struct rtx_iv iv;
|
df_ref def, last_def;
|
df_ref def, last_def;
|
|
|
if (!simple_reg_p (reg))
|
if (!simple_reg_p (reg))
|
return false;
|
return false;
|
|
|
def = df_find_def (insn, reg);
|
def = df_find_def (insn, reg);
|
gcc_assert (def != NULL);
|
gcc_assert (def != NULL);
|
if (!latch_dominating_def (reg, &last_def))
|
if (!latch_dominating_def (reg, &last_def))
|
return false;
|
return false;
|
if (last_def != def)
|
if (last_def != def)
|
return false;
|
return false;
|
|
|
if (!iv_analyze_biv (reg, &iv))
|
if (!iv_analyze_biv (reg, &iv))
|
return false;
|
return false;
|
|
|
return iv.step != const0_rtx;
|
return iv.step != const0_rtx;
|
}
|
}
|
|
|
/* Calculates value of IV at ITERATION-th iteration. */
|
/* Calculates value of IV at ITERATION-th iteration. */
|
|
|
rtx
|
rtx
|
get_iv_value (struct rtx_iv *iv, rtx iteration)
|
get_iv_value (struct rtx_iv *iv, rtx iteration)
|
{
|
{
|
rtx val;
|
rtx val;
|
|
|
/* We would need to generate some if_then_else patterns, and so far
|
/* We would need to generate some if_then_else patterns, and so far
|
it is not needed anywhere. */
|
it is not needed anywhere. */
|
gcc_assert (!iv->first_special);
|
gcc_assert (!iv->first_special);
|
|
|
if (iv->step != const0_rtx && iteration != const0_rtx)
|
if (iv->step != const0_rtx && iteration != const0_rtx)
|
val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
|
val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
iv->step, iteration));
|
iv->step, iteration));
|
else
|
else
|
val = iv->base;
|
val = iv->base;
|
|
|
if (iv->extend_mode == iv->mode)
|
if (iv->extend_mode == iv->mode)
|
return val;
|
return val;
|
|
|
val = lowpart_subreg (iv->mode, val, iv->extend_mode);
|
val = lowpart_subreg (iv->mode, val, iv->extend_mode);
|
|
|
if (iv->extend == UNKNOWN)
|
if (iv->extend == UNKNOWN)
|
return val;
|
return val;
|
|
|
val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
|
val = simplify_gen_unary (iv->extend, iv->extend_mode, val, iv->mode);
|
val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
|
val = simplify_gen_binary (PLUS, iv->extend_mode, iv->delta,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
simplify_gen_binary (MULT, iv->extend_mode,
|
iv->mult, val));
|
iv->mult, val));
|
|
|
return val;
|
return val;
|
}
|
}
|
|
|
/* Free the data for an induction variable analysis. */
|
/* Free the data for an induction variable analysis. */
|
|
|
void
|
void
|
iv_analysis_done (void)
|
iv_analysis_done (void)
|
{
|
{
|
if (!clean_slate)
|
if (!clean_slate)
|
{
|
{
|
clear_iv_info ();
|
clear_iv_info ();
|
clean_slate = true;
|
clean_slate = true;
|
df_finish_pass (true);
|
df_finish_pass (true);
|
htab_delete (bivs);
|
htab_delete (bivs);
|
free (iv_ref_table);
|
free (iv_ref_table);
|
iv_ref_table = NULL;
|
iv_ref_table = NULL;
|
iv_ref_table_size = 0;
|
iv_ref_table_size = 0;
|
bivs = NULL;
|
bivs = NULL;
|
}
|
}
|
}
|
}
|
|
|
/* Computes inverse to X modulo (1 << MOD). */
|
/* Computes inverse to X modulo (1 << MOD). */
|
|
|
static unsigned HOST_WIDEST_INT
|
static unsigned HOST_WIDEST_INT
|
inverse (unsigned HOST_WIDEST_INT x, int mod)
|
inverse (unsigned HOST_WIDEST_INT x, int mod)
|
{
|
{
|
unsigned HOST_WIDEST_INT mask =
|
unsigned HOST_WIDEST_INT mask =
|
((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
|
((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
|
unsigned HOST_WIDEST_INT rslt = 1;
|
unsigned HOST_WIDEST_INT rslt = 1;
|
int i;
|
int i;
|
|
|
for (i = 0; i < mod - 1; i++)
|
for (i = 0; i < mod - 1; i++)
|
{
|
{
|
rslt = (rslt * x) & mask;
|
rslt = (rslt * x) & mask;
|
x = (x * x) & mask;
|
x = (x * x) & mask;
|
}
|
}
|
|
|
return rslt;
|
return rslt;
|
}
|
}
|
|
|
/* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
|
/* Checks whether register *REG is in set ALT. Callback for for_each_rtx. */
|
|
|
static int
|
static int
|
altered_reg_used (rtx *reg, void *alt)
|
altered_reg_used (rtx *reg, void *alt)
|
{
|
{
|
if (!REG_P (*reg))
|
if (!REG_P (*reg))
|
return 0;
|
return 0;
|
|
|
return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
|
return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));
|
}
|
}
|
|
|
/* Marks registers altered by EXPR in set ALT. */
|
/* Marks registers altered by EXPR in set ALT. */
|
|
|
static void
|
static void
|
mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
|
mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)
|
{
|
{
|
if (GET_CODE (expr) == SUBREG)
|
if (GET_CODE (expr) == SUBREG)
|
expr = SUBREG_REG (expr);
|
expr = SUBREG_REG (expr);
|
if (!REG_P (expr))
|
if (!REG_P (expr))
|
return;
|
return;
|
|
|
SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
|
SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));
|
}
|
}
|
|
|
/* Checks whether RHS is simple enough to process. */
|
/* Checks whether RHS is simple enough to process. */
|
|
|
static bool
|
static bool
|
simple_rhs_p (rtx rhs)
|
simple_rhs_p (rtx rhs)
|
{
|
{
|
rtx op0, op1;
|
rtx op0, op1;
|
|
|
if (function_invariant_p (rhs)
|
if (function_invariant_p (rhs)
|
|| (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
|
|| (REG_P (rhs) && !HARD_REGISTER_P (rhs)))
|
return true;
|
return true;
|
|
|
switch (GET_CODE (rhs))
|
switch (GET_CODE (rhs))
|
{
|
{
|
case PLUS:
|
case PLUS:
|
case MINUS:
|
case MINUS:
|
case AND:
|
case AND:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
op1 = XEXP (rhs, 1);
|
op1 = XEXP (rhs, 1);
|
/* Allow reg OP const and reg OP reg. */
|
/* Allow reg OP const and reg OP reg. */
|
if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
|
if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
|
&& !function_invariant_p (op0))
|
&& !function_invariant_p (op0))
|
return false;
|
return false;
|
if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
|
if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
|
&& !function_invariant_p (op1))
|
&& !function_invariant_p (op1))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
|
|
case ASHIFT:
|
case ASHIFT:
|
case ASHIFTRT:
|
case ASHIFTRT:
|
case LSHIFTRT:
|
case LSHIFTRT:
|
case MULT:
|
case MULT:
|
op0 = XEXP (rhs, 0);
|
op0 = XEXP (rhs, 0);
|
op1 = XEXP (rhs, 1);
|
op1 = XEXP (rhs, 1);
|
/* Allow reg OP const. */
|
/* Allow reg OP const. */
|
if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
|
if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
|
return false;
|
return false;
|
if (!function_invariant_p (op1))
|
if (!function_invariant_p (op1))
|
return false;
|
return false;
|
|
|
return true;
|
return true;
|
|
|
default:
|
default:
|
return false;
|
return false;
|
}
|
}
|
}
|
}
|
|
|
/* If REG has a single definition, replace it with its known value in EXPR.
|
/* If REG has a single definition, replace it with its known value in EXPR.
|
Callback for for_each_rtx. */
|
Callback for for_each_rtx. */
|
|
|
static int
|
static int
|
replace_single_def_regs (rtx *reg, void *expr1)
|
replace_single_def_regs (rtx *reg, void *expr1)
|
{
|
{
|
unsigned regno;
|
unsigned regno;
|
df_ref adef;
|
df_ref adef;
|
rtx set, src;
|
rtx set, src;
|
rtx *expr = (rtx *)expr1;
|
rtx *expr = (rtx *)expr1;
|
|
|
if (!REG_P (*reg))
|
if (!REG_P (*reg))
|
return 0;
|
return 0;
|
|
|
regno = REGNO (*reg);
|
regno = REGNO (*reg);
|
for (;;)
|
for (;;)
|
{
|
{
|
rtx note;
|
rtx note;
|
adef = DF_REG_DEF_CHAIN (regno);
|
adef = DF_REG_DEF_CHAIN (regno);
|
if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
|
if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
|
|| DF_REF_IS_ARTIFICIAL (adef))
|
|| DF_REF_IS_ARTIFICIAL (adef))
|
return -1;
|
return -1;
|
|
|
set = single_set (DF_REF_INSN (adef));
|
set = single_set (DF_REF_INSN (adef));
|
if (set == NULL || !REG_P (SET_DEST (set))
|
if (set == NULL || !REG_P (SET_DEST (set))
|
|| REGNO (SET_DEST (set)) != regno)
|
|| REGNO (SET_DEST (set)) != regno)
|
return -1;
|
return -1;
|
|
|
note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
|
note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
|
|
|
if (note && function_invariant_p (XEXP (note, 0)))
|
if (note && function_invariant_p (XEXP (note, 0)))
|
{
|
{
|
src = XEXP (note, 0);
|
src = XEXP (note, 0);
|
break;
|
break;
|
}
|
}
|
src = SET_SRC (set);
|
src = SET_SRC (set);
|
|
|
if (REG_P (src))
|
if (REG_P (src))
|
{
|
{
|
regno = REGNO (src);
|
regno = REGNO (src);
|
continue;
|
continue;
|
}
|
}
|
break;
|
break;
|
}
|
}
|
if (!function_invariant_p (src))
|
if (!function_invariant_p (src))
|
return -1;
|
return -1;
|
|
|
*expr = simplify_replace_rtx (*expr, *reg, src);
|
*expr = simplify_replace_rtx (*expr, *reg, src);
|
return 1;
|
return 1;
|
}
|
}
|
|
|
/* A subroutine of simplify_using_initial_values, this function examines INSN
|
/* 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.
|
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
|
If it is suitable, return true and set DEST and SRC to the lhs and rhs of
|
the set; return false otherwise. */
|
the set; return false otherwise. */
|
|
|
static bool
|
static bool
|
suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
|
suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
|
{
|
{
|
rtx set = single_set (insn);
|
rtx set = single_set (insn);
|
rtx lhs = NULL_RTX, rhs;
|
rtx lhs = NULL_RTX, rhs;
|
|
|
if (!set)
|
if (!set)
|
return false;
|
return false;
|
|
|
lhs = SET_DEST (set);
|
lhs = SET_DEST (set);
|
if (!REG_P (lhs))
|
if (!REG_P (lhs))
|
return false;
|
return false;
|
|
|
rhs = find_reg_equal_equiv_note (insn);
|
rhs = find_reg_equal_equiv_note (insn);
|
if (rhs)
|
if (rhs)
|
rhs = XEXP (rhs, 0);
|
rhs = XEXP (rhs, 0);
|
else
|
else
|
rhs = SET_SRC (set);
|
rhs = SET_SRC (set);
|
|
|
if (!simple_rhs_p (rhs))
|
if (!simple_rhs_p (rhs))
|
return false;
|
return false;
|
|
|
*dest = lhs;
|
*dest = lhs;
|
*src = rhs;
|
*src = rhs;
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Using the data returned by suitable_set_for_replacement, replace DEST
|
/* Using the data returned by suitable_set_for_replacement, replace DEST
|
with SRC in *EXPR and return the new expression. Also call
|
with SRC in *EXPR and return the new expression. Also call
|
replace_single_def_regs if the replacement changed something. */
|
replace_single_def_regs if the replacement changed something. */
|
static void
|
static void
|
replace_in_expr (rtx *expr, rtx dest, rtx src)
|
replace_in_expr (rtx *expr, rtx dest, rtx src)
|
{
|
{
|
rtx old = *expr;
|
rtx old = *expr;
|
*expr = simplify_replace_rtx (*expr, dest, src);
|
*expr = simplify_replace_rtx (*expr, dest, src);
|
if (old == *expr)
|
if (old == *expr)
|
return;
|
return;
|
while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
|
while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
|
continue;
|
continue;
|
}
|
}
|
|
|
/* Checks whether A implies B. */
|
/* Checks whether A implies B. */
|
|
|
static bool
|
static bool
|
implies_p (rtx a, rtx b)
|
implies_p (rtx a, rtx b)
|
{
|
{
|
rtx op0, op1, opb0, opb1, r;
|
rtx op0, op1, opb0, opb1, r;
|
enum machine_mode mode;
|
enum machine_mode mode;
|
|
|
if (GET_CODE (a) == EQ)
|
if (GET_CODE (a) == EQ)
|
{
|
{
|
op0 = XEXP (a, 0);
|
op0 = XEXP (a, 0);
|
op1 = XEXP (a, 1);
|
op1 = XEXP (a, 1);
|
|
|
if (REG_P (op0))
|
if (REG_P (op0))
|
{
|
{
|
r = simplify_replace_rtx (b, op0, op1);
|
r = simplify_replace_rtx (b, op0, op1);
|
if (r == const_true_rtx)
|
if (r == const_true_rtx)
|
return true;
|
return true;
|
}
|
}
|
|
|
if (REG_P (op1))
|
if (REG_P (op1))
|
{
|
{
|
r = simplify_replace_rtx (b, op1, op0);
|
r = simplify_replace_rtx (b, op1, op0);
|
if (r == const_true_rtx)
|
if (r == const_true_rtx)
|
return true;
|
return true;
|
}
|
}
|
}
|
}
|
|
|
if (b == const_true_rtx)
|
if (b == const_true_rtx)
|
return true;
|
return true;
|
|
|
if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
|
if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
|
&& GET_RTX_CLASS (GET_CODE (a)) != RTX_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_COMM_COMPARE
|
&& GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
|
&& GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
|
return false;
|
return false;
|
|
|
op0 = XEXP (a, 0);
|
op0 = XEXP (a, 0);
|
op1 = XEXP (a, 1);
|
op1 = XEXP (a, 1);
|
opb0 = XEXP (b, 0);
|
opb0 = XEXP (b, 0);
|
opb1 = XEXP (b, 1);
|
opb1 = XEXP (b, 1);
|
|
|
mode = GET_MODE (op0);
|
mode = GET_MODE (op0);
|
if (mode != GET_MODE (opb0))
|
if (mode != GET_MODE (opb0))
|
mode = VOIDmode;
|
mode = VOIDmode;
|
else if (mode == VOIDmode)
|
else if (mode == VOIDmode)
|
{
|
{
|
mode = GET_MODE (op1);
|
mode = GET_MODE (op1);
|
if (mode != GET_MODE (opb1))
|
if (mode != GET_MODE (opb1))
|
mode = VOIDmode;
|
mode = VOIDmode;
|
}
|
}
|
|
|
/* A < B implies A + 1 <= B. */
|
/* A < B implies A + 1 <= B. */
|
if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
|
if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
|
&& (GET_CODE (b) == GE || GET_CODE (b) == LE))
|
&& (GET_CODE (b) == GE || GET_CODE (b) == LE))
|
{
|
{
|
|
|
if (GET_CODE (a) == GT)
|
if (GET_CODE (a) == GT)
|
{
|
{
|
r = op0;
|
r = op0;
|
op0 = op1;
|
op0 = op1;
|
op1 = r;
|
op1 = r;
|
}
|
}
|
|
|
if (GET_CODE (b) == GE)
|
if (GET_CODE (b) == GE)
|
{
|
{
|
r = opb0;
|
r = opb0;
|
opb0 = opb1;
|
opb0 = opb1;
|
opb1 = r;
|
opb1 = r;
|
}
|
}
|
|
|
if (SCALAR_INT_MODE_P (mode)
|
if (SCALAR_INT_MODE_P (mode)
|
&& rtx_equal_p (op1, opb1)
|
&& rtx_equal_p (op1, opb1)
|
&& simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
|
&& simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
|
return true;
|
return true;
|
return false;
|
return false;
|
}
|
}
|
|
|
/* A < B or A > B imply A != B. TODO: Likewise
|
/* A < B or A > B imply A != B. TODO: Likewise
|
A + n < B implies A != B + n if neither wraps. */
|
A + n < B implies A != B + n if neither wraps. */
|
if (GET_CODE (b) == NE
|
if (GET_CODE (b) == NE
|
&& (GET_CODE (a) == GT || GET_CODE (a) == GTU
|
&& (GET_CODE (a) == GT || GET_CODE (a) == GTU
|
|| GET_CODE (a) == LT || GET_CODE (a) == LTU))
|
|| GET_CODE (a) == LT || GET_CODE (a) == LTU))
|
{
|
{
|
if (rtx_equal_p (op0, opb0)
|
if (rtx_equal_p (op0, opb0)
|
&& rtx_equal_p (op1, opb1))
|
&& rtx_equal_p (op1, opb1))
|
return true;
|
return true;
|
}
|
}
|
|
|
/* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
|
/* For unsigned comparisons, A != 0 implies A > 0 and A >= 1. */
|
if (GET_CODE (a) == NE
|
if (GET_CODE (a) == NE
|
&& op1 == const0_rtx)
|
&& op1 == const0_rtx)
|
{
|
{
|
if ((GET_CODE (b) == GTU
|
if ((GET_CODE (b) == GTU
|
&& opb1 == const0_rtx)
|
&& opb1 == const0_rtx)
|
|| (GET_CODE (b) == GEU
|
|| (GET_CODE (b) == GEU
|
&& opb1 == const1_rtx))
|
&& opb1 == const1_rtx))
|
return rtx_equal_p (op0, opb0);
|
return rtx_equal_p (op0, opb0);
|
}
|
}
|
|
|
/* A != N is equivalent to A - (N + 1) <u -1. */
|
/* A != N is equivalent to A - (N + 1) <u -1. */
|
if (GET_CODE (a) == NE
|
if (GET_CODE (a) == NE
|
&& CONST_INT_P (op1)
|
&& CONST_INT_P (op1)
|
&& GET_CODE (b) == LTU
|
&& GET_CODE (b) == LTU
|
&& opb1 == constm1_rtx
|
&& opb1 == constm1_rtx
|
&& GET_CODE (opb0) == PLUS
|
&& GET_CODE (opb0) == PLUS
|
&& CONST_INT_P (XEXP (opb0, 1))
|
&& CONST_INT_P (XEXP (opb0, 1))
|
/* Avoid overflows. */
|
/* Avoid overflows. */
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
!= ((unsigned HOST_WIDE_INT)1
|
!= ((unsigned HOST_WIDE_INT)1
|
<< (HOST_BITS_PER_WIDE_INT - 1)) - 1)
|
<< (HOST_BITS_PER_WIDE_INT - 1)) - 1)
|
&& INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
|
&& INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
|
return rtx_equal_p (op0, XEXP (opb0, 0));
|
return rtx_equal_p (op0, XEXP (opb0, 0));
|
|
|
/* Likewise, A != N implies A - N > 0. */
|
/* Likewise, A != N implies A - N > 0. */
|
if (GET_CODE (a) == NE
|
if (GET_CODE (a) == NE
|
&& CONST_INT_P (op1))
|
&& CONST_INT_P (op1))
|
{
|
{
|
if (GET_CODE (b) == GTU
|
if (GET_CODE (b) == GTU
|
&& GET_CODE (opb0) == PLUS
|
&& GET_CODE (opb0) == PLUS
|
&& opb1 == const0_rtx
|
&& opb1 == const0_rtx
|
&& CONST_INT_P (XEXP (opb0, 1))
|
&& CONST_INT_P (XEXP (opb0, 1))
|
/* Avoid overflows. */
|
/* Avoid overflows. */
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
|
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
|
&& rtx_equal_p (XEXP (opb0, 0), op0))
|
&& rtx_equal_p (XEXP (opb0, 0), op0))
|
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
|
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
|
if (GET_CODE (b) == GEU
|
if (GET_CODE (b) == GEU
|
&& GET_CODE (opb0) == PLUS
|
&& GET_CODE (opb0) == PLUS
|
&& opb1 == const1_rtx
|
&& opb1 == const1_rtx
|
&& CONST_INT_P (XEXP (opb0, 1))
|
&& CONST_INT_P (XEXP (opb0, 1))
|
/* Avoid overflows. */
|
/* Avoid overflows. */
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
&& ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
|
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
|
!= ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
|
&& rtx_equal_p (XEXP (opb0, 0), op0))
|
&& rtx_equal_p (XEXP (opb0, 0), op0))
|
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
|
return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
|
}
|
}
|
|
|
/* A >s X, where X is positive, implies A <u Y, if Y is negative. */
|
/* A >s X, where X is positive, implies A <u Y, if Y is negative. */
|
if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
|
if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
|
&& CONST_INT_P (op1)
|
&& CONST_INT_P (op1)
|
&& ((GET_CODE (a) == GT && op1 == constm1_rtx)
|
&& ((GET_CODE (a) == GT && op1 == constm1_rtx)
|
|| INTVAL (op1) >= 0)
|
|| INTVAL (op1) >= 0)
|
&& GET_CODE (b) == LTU
|
&& GET_CODE (b) == LTU
|
&& CONST_INT_P (opb1)
|
&& CONST_INT_P (opb1)
|
&& rtx_equal_p (op0, opb0))
|
&& rtx_equal_p (op0, opb0))
|
return INTVAL (opb1) < 0;
|
return INTVAL (opb1) < 0;
|
|
|
return false;
|
return false;
|
}
|
}
|
|
|
/* Canonicalizes COND so that
|
/* Canonicalizes COND so that
|
|
|
(1) Ensure that operands are ordered according to
|
(1) Ensure that operands are ordered according to
|
swap_commutative_operands_p.
|
swap_commutative_operands_p.
|
(2) (LE x const) will be replaced with (LT x <const+1>) and similarly
|
(2) (LE x const) will be replaced with (LT x <const+1>) and similarly
|
for GE, GEU, and LEU. */
|
for GE, GEU, and LEU. */
|
|
|
rtx
|
rtx
|
canon_condition (rtx cond)
|
canon_condition (rtx cond)
|
{
|
{
|
rtx tem;
|
rtx tem;
|
rtx op0, op1;
|
rtx op0, op1;
|
enum rtx_code code;
|
enum rtx_code code;
|
enum machine_mode mode;
|
enum machine_mode mode;
|
|
|
code = GET_CODE (cond);
|
code = GET_CODE (cond);
|
op0 = XEXP (cond, 0);
|
op0 = XEXP (cond, 0);
|
op1 = XEXP (cond, 1);
|
op1 = XEXP (cond, 1);
|
|
|
if (swap_commutative_operands_p (op0, op1))
|
if (swap_commutative_operands_p (op0, op1))
|
{
|
{
|
code = swap_condition (code);
|
code = swap_condition (code);
|
tem = op0;
|
tem = op0;
|
op0 = op1;
|
op0 = op1;
|
op1 = tem;
|
op1 = tem;
|
}
|
}
|
|
|
mode = GET_MODE (op0);
|
mode = GET_MODE (op0);
|
if (mode == VOIDmode)
|
if (mode == VOIDmode)
|
mode = GET_MODE (op1);
|
mode = GET_MODE (op1);
|
gcc_assert (mode != VOIDmode);
|
gcc_assert (mode != VOIDmode);
|
|
|
if (CONST_INT_P (op1)
|
if (CONST_INT_P (op1)
|
&& GET_MODE_CLASS (mode) != MODE_CC
|
&& GET_MODE_CLASS (mode) != MODE_CC
|
&& GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
|
&& GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
|
{
|
{
|
HOST_WIDE_INT const_val = INTVAL (op1);
|
HOST_WIDE_INT const_val = INTVAL (op1);
|
unsigned HOST_WIDE_INT uconst_val = const_val;
|
unsigned HOST_WIDE_INT uconst_val = const_val;
|
unsigned HOST_WIDE_INT max_val
|
unsigned HOST_WIDE_INT max_val
|
= (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
|
= (unsigned HOST_WIDE_INT) GET_MODE_MASK (mode);
|
|
|
switch (code)
|
switch (code)
|
{
|
{
|
case LE:
|
case LE:
|
if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
|
if ((unsigned HOST_WIDE_INT) const_val != max_val >> 1)
|
code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
|
code = LT, op1 = gen_int_mode (const_val + 1, GET_MODE (op0));
|
break;
|
break;
|
|
|
/* When cross-compiling, const_val might be sign-extended from
|
/* When cross-compiling, const_val might be sign-extended from
|
BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
|
BITS_PER_WORD to HOST_BITS_PER_WIDE_INT */
|
case GE:
|
case GE:
|
if ((HOST_WIDE_INT) (const_val & max_val)
|
if ((HOST_WIDE_INT) (const_val & max_val)
|
!= (((HOST_WIDE_INT) 1
|
!= (((HOST_WIDE_INT) 1
|
<< (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
|
<< (GET_MODE_BITSIZE (GET_MODE (op0)) - 1))))
|
code = GT, op1 = gen_int_mode (const_val - 1, mode);
|
code = GT, op1 = gen_int_mode (const_val - 1, mode);
|
break;
|
break;
|
|
|
case LEU:
|
case LEU:
|
if (uconst_val < max_val)
|
if (uconst_val < max_val)
|
code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
|
code = LTU, op1 = gen_int_mode (uconst_val + 1, mode);
|
break;
|
break;
|
|
|
case GEU:
|
case GEU:
|
if (uconst_val != 0)
|
if (uconst_val != 0)
|
code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
|
code = GTU, op1 = gen_int_mode (uconst_val - 1, mode);
|
break;
|
break;
|
|
|
default:
|
default:
|
break;
|
break;
|
}
|
}
|
}
|
}
|
|
|
if (op0 != XEXP (cond, 0)
|
if (op0 != XEXP (cond, 0)
|
|| op1 != XEXP (cond, 1)
|
|| op1 != XEXP (cond, 1)
|
|| code != GET_CODE (cond)
|
|| code != GET_CODE (cond)
|
|| GET_MODE (cond) != SImode)
|
|| GET_MODE (cond) != SImode)
|
cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
|
cond = gen_rtx_fmt_ee (code, SImode, op0, op1);
|
|
|
return cond;
|
return cond;
|
}
|
}
|
|
|
/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
|
/* Tries to use the fact that COND holds to simplify EXPR. ALTERED is the
|
set of altered regs. */
|
set of altered regs. */
|
|
|
void
|
void
|
simplify_using_condition (rtx cond, rtx *expr, regset altered)
|
simplify_using_condition (rtx cond, rtx *expr, regset altered)
|
{
|
{
|
rtx rev, reve, exp = *expr;
|
rtx rev, reve, exp = *expr;
|
|
|
/* If some register gets altered later, we do not really speak about its
|
/* If some register gets altered later, we do not really speak about its
|
value at the time of comparison. */
|
value at the time of comparison. */
|
if (altered
|
if (altered
|
&& for_each_rtx (&cond, altered_reg_used, altered))
|
&& for_each_rtx (&cond, altered_reg_used, altered))
|
return;
|
return;
|
|
|
if (GET_CODE (cond) == EQ
|
if (GET_CODE (cond) == EQ
|
&& REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
|
&& REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
|
{
|
{
|
*expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
|
*expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
|
return;
|
return;
|
}
|
}
|
|
|
if (!COMPARISON_P (exp))
|
if (!COMPARISON_P (exp))
|
return;
|
return;
|
|
|
rev = reversed_condition (cond);
|
rev = reversed_condition (cond);
|
reve = reversed_condition (exp);
|
reve = reversed_condition (exp);
|
|
|
cond = canon_condition (cond);
|
cond = canon_condition (cond);
|
exp = canon_condition (exp);
|
exp = canon_condition (exp);
|
if (rev)
|
if (rev)
|
rev = canon_condition (rev);
|
rev = canon_condition (rev);
|
if (reve)
|
if (reve)
|
reve = canon_condition (reve);
|
reve = canon_condition (reve);
|
|
|
if (rtx_equal_p (exp, cond))
|
if (rtx_equal_p (exp, cond))
|
{
|
{
|
*expr = const_true_rtx;
|
*expr = const_true_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
if (rev && rtx_equal_p (exp, rev))
|
if (rev && rtx_equal_p (exp, rev))
|
{
|
{
|
*expr = const0_rtx;
|
*expr = const0_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
if (implies_p (cond, exp))
|
if (implies_p (cond, exp))
|
{
|
{
|
*expr = const_true_rtx;
|
*expr = const_true_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
if (reve && implies_p (cond, reve))
|
if (reve && implies_p (cond, reve))
|
{
|
{
|
*expr = const0_rtx;
|
*expr = const0_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
/* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
|
/* A proof by contradiction. If *EXPR implies (not cond), *EXPR must
|
be false. */
|
be false. */
|
if (rev && implies_p (exp, rev))
|
if (rev && implies_p (exp, rev))
|
{
|
{
|
*expr = const0_rtx;
|
*expr = const0_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
/* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
|
/* Similarly, If (not *EXPR) implies (not cond), *EXPR must be true. */
|
if (rev && reve && implies_p (reve, rev))
|
if (rev && reve && implies_p (reve, rev))
|
{
|
{
|
*expr = const_true_rtx;
|
*expr = const_true_rtx;
|
return;
|
return;
|
}
|
}
|
|
|
/* We would like to have some other tests here. TODO. */
|
/* We would like to have some other tests here. TODO. */
|
|
|
return;
|
return;
|
}
|
}
|
|
|
/* Use relationship between A and *B to eventually eliminate *B.
|
/* Use relationship between A and *B to eventually eliminate *B.
|
OP is the operation we consider. */
|
OP is the operation we consider. */
|
|
|
static void
|
static void
|
eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
|
eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
|
{
|
{
|
switch (op)
|
switch (op)
|
{
|
{
|
case AND:
|
case AND:
|
/* If A implies *B, we may replace *B by true. */
|
/* If A implies *B, we may replace *B by true. */
|
if (implies_p (a, *b))
|
if (implies_p (a, *b))
|
*b = const_true_rtx;
|
*b = const_true_rtx;
|
break;
|
break;
|
|
|
case IOR:
|
case IOR:
|
/* If *B implies A, we may replace *B by false. */
|
/* If *B implies A, we may replace *B by false. */
|
if (implies_p (*b, a))
|
if (implies_p (*b, a))
|
*b = const0_rtx;
|
*b = const0_rtx;
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
}
|
}
|
|
|
/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
|
/* Eliminates the conditions in TAIL that are implied by HEAD. OP is the
|
operation we consider. */
|
operation we consider. */
|
|
|
static void
|
static void
|
eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
|
eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
|
{
|
{
|
rtx elt;
|
rtx elt;
|
|
|
for (elt = tail; elt; elt = XEXP (elt, 1))
|
for (elt = tail; elt; elt = XEXP (elt, 1))
|
eliminate_implied_condition (op, *head, &XEXP (elt, 0));
|
eliminate_implied_condition (op, *head, &XEXP (elt, 0));
|
for (elt = tail; elt; elt = XEXP (elt, 1))
|
for (elt = tail; elt; elt = XEXP (elt, 1))
|
eliminate_implied_condition (op, XEXP (elt, 0), head);
|
eliminate_implied_condition (op, XEXP (elt, 0), head);
|
}
|
}
|
|
|
/* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
|
/* Simplifies *EXPR using initial values at the start of the LOOP. If *EXPR
|
is a list, its elements are assumed to be combined using OP. */
|
is a list, its elements are assumed to be combined using OP. */
|
|
|
static void
|
static void
|
simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
|
simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
|
{
|
{
|
bool expression_valid;
|
bool expression_valid;
|
rtx head, tail, insn, cond_list, last_valid_expr;
|
rtx head, tail, insn, cond_list, last_valid_expr;
|
rtx neutral, aggr;
|
rtx neutral, aggr;
|
regset altered, this_altered;
|
regset altered, this_altered;
|
edge e;
|
edge e;
|
|
|
if (!*expr)
|
if (!*expr)
|
return;
|
return;
|
|
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
return;
|
return;
|
|
|
if (GET_CODE (*expr) == EXPR_LIST)
|
if (GET_CODE (*expr) == EXPR_LIST)
|
{
|
{
|
head = XEXP (*expr, 0);
|
head = XEXP (*expr, 0);
|
tail = XEXP (*expr, 1);
|
tail = XEXP (*expr, 1);
|
|
|
eliminate_implied_conditions (op, &head, tail);
|
eliminate_implied_conditions (op, &head, tail);
|
|
|
switch (op)
|
switch (op)
|
{
|
{
|
case AND:
|
case AND:
|
neutral = const_true_rtx;
|
neutral = const_true_rtx;
|
aggr = const0_rtx;
|
aggr = const0_rtx;
|
break;
|
break;
|
|
|
case IOR:
|
case IOR:
|
neutral = const0_rtx;
|
neutral = const0_rtx;
|
aggr = const_true_rtx;
|
aggr = const_true_rtx;
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
simplify_using_initial_values (loop, UNKNOWN, &head);
|
simplify_using_initial_values (loop, UNKNOWN, &head);
|
if (head == aggr)
|
if (head == aggr)
|
{
|
{
|
XEXP (*expr, 0) = aggr;
|
XEXP (*expr, 0) = aggr;
|
XEXP (*expr, 1) = NULL_RTX;
|
XEXP (*expr, 1) = NULL_RTX;
|
return;
|
return;
|
}
|
}
|
else if (head == neutral)
|
else if (head == neutral)
|
{
|
{
|
*expr = tail;
|
*expr = tail;
|
simplify_using_initial_values (loop, op, expr);
|
simplify_using_initial_values (loop, op, expr);
|
return;
|
return;
|
}
|
}
|
simplify_using_initial_values (loop, op, &tail);
|
simplify_using_initial_values (loop, op, &tail);
|
|
|
if (tail && XEXP (tail, 0) == aggr)
|
if (tail && XEXP (tail, 0) == aggr)
|
{
|
{
|
*expr = tail;
|
*expr = tail;
|
return;
|
return;
|
}
|
}
|
|
|
XEXP (*expr, 0) = head;
|
XEXP (*expr, 0) = head;
|
XEXP (*expr, 1) = tail;
|
XEXP (*expr, 1) = tail;
|
return;
|
return;
|
}
|
}
|
|
|
gcc_assert (op == UNKNOWN);
|
gcc_assert (op == UNKNOWN);
|
|
|
for (;;)
|
for (;;)
|
if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
|
if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
|
break;
|
break;
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
return;
|
return;
|
|
|
e = loop_preheader_edge (loop);
|
e = loop_preheader_edge (loop);
|
if (e->src == ENTRY_BLOCK_PTR)
|
if (e->src == ENTRY_BLOCK_PTR)
|
return;
|
return;
|
|
|
altered = ALLOC_REG_SET (®_obstack);
|
altered = ALLOC_REG_SET (®_obstack);
|
this_altered = ALLOC_REG_SET (®_obstack);
|
this_altered = ALLOC_REG_SET (®_obstack);
|
|
|
expression_valid = true;
|
expression_valid = true;
|
last_valid_expr = *expr;
|
last_valid_expr = *expr;
|
cond_list = NULL_RTX;
|
cond_list = NULL_RTX;
|
while (1)
|
while (1)
|
{
|
{
|
insn = BB_END (e->src);
|
insn = BB_END (e->src);
|
if (any_condjump_p (insn))
|
if (any_condjump_p (insn))
|
{
|
{
|
rtx cond = get_condition (BB_END (e->src), NULL, false, true);
|
rtx cond = get_condition (BB_END (e->src), NULL, false, true);
|
|
|
if (cond && (e->flags & EDGE_FALLTHRU))
|
if (cond && (e->flags & EDGE_FALLTHRU))
|
cond = reversed_condition (cond);
|
cond = reversed_condition (cond);
|
if (cond)
|
if (cond)
|
{
|
{
|
rtx old = *expr;
|
rtx old = *expr;
|
simplify_using_condition (cond, expr, altered);
|
simplify_using_condition (cond, expr, altered);
|
if (old != *expr)
|
if (old != *expr)
|
{
|
{
|
rtx note;
|
rtx note;
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
goto out;
|
goto out;
|
for (note = cond_list; note; note = XEXP (note, 1))
|
for (note = cond_list; note; note = XEXP (note, 1))
|
{
|
{
|
simplify_using_condition (XEXP (note, 0), expr, altered);
|
simplify_using_condition (XEXP (note, 0), expr, altered);
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
goto out;
|
goto out;
|
}
|
}
|
}
|
}
|
cond_list = alloc_EXPR_LIST (0, cond, cond_list);
|
cond_list = alloc_EXPR_LIST (0, cond, cond_list);
|
}
|
}
|
}
|
}
|
|
|
FOR_BB_INSNS_REVERSE (e->src, insn)
|
FOR_BB_INSNS_REVERSE (e->src, insn)
|
{
|
{
|
rtx src, dest;
|
rtx src, dest;
|
rtx old = *expr;
|
rtx old = *expr;
|
|
|
if (!INSN_P (insn))
|
if (!INSN_P (insn))
|
continue;
|
continue;
|
|
|
CLEAR_REG_SET (this_altered);
|
CLEAR_REG_SET (this_altered);
|
note_stores (PATTERN (insn), mark_altered, this_altered);
|
note_stores (PATTERN (insn), mark_altered, this_altered);
|
if (CALL_P (insn))
|
if (CALL_P (insn))
|
{
|
{
|
int i;
|
int i;
|
|
|
/* Kill all call clobbered registers. */
|
/* Kill all call clobbered registers. */
|
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
|
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
|
if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
|
SET_REGNO_REG_SET (this_altered, i);
|
SET_REGNO_REG_SET (this_altered, i);
|
}
|
}
|
|
|
if (suitable_set_for_replacement (insn, &dest, &src))
|
if (suitable_set_for_replacement (insn, &dest, &src))
|
{
|
{
|
rtx *pnote, *pnote_next;
|
rtx *pnote, *pnote_next;
|
|
|
replace_in_expr (expr, dest, src);
|
replace_in_expr (expr, dest, src);
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
goto out;
|
goto out;
|
|
|
for (pnote = &cond_list; *pnote; pnote = pnote_next)
|
for (pnote = &cond_list; *pnote; pnote = pnote_next)
|
{
|
{
|
rtx note = *pnote;
|
rtx note = *pnote;
|
rtx old_cond = XEXP (note, 0);
|
rtx old_cond = XEXP (note, 0);
|
|
|
pnote_next = &XEXP (note, 1);
|
pnote_next = &XEXP (note, 1);
|
replace_in_expr (&XEXP (note, 0), dest, src);
|
replace_in_expr (&XEXP (note, 0), dest, src);
|
|
|
/* We can no longer use a condition that has been simplified
|
/* We can no longer use a condition that has been simplified
|
to a constant, and simplify_using_condition will abort if
|
to a constant, and simplify_using_condition will abort if
|
we try. */
|
we try. */
|
if (CONSTANT_P (XEXP (note, 0)))
|
if (CONSTANT_P (XEXP (note, 0)))
|
{
|
{
|
*pnote = *pnote_next;
|
*pnote = *pnote_next;
|
pnote_next = pnote;
|
pnote_next = pnote;
|
free_EXPR_LIST_node (note);
|
free_EXPR_LIST_node (note);
|
}
|
}
|
/* Retry simplifications with this condition if either the
|
/* Retry simplifications with this condition if either the
|
expression or the condition changed. */
|
expression or the condition changed. */
|
else if (old_cond != XEXP (note, 0) || old != *expr)
|
else if (old_cond != XEXP (note, 0) || old != *expr)
|
simplify_using_condition (XEXP (note, 0), expr, altered);
|
simplify_using_condition (XEXP (note, 0), expr, altered);
|
}
|
}
|
}
|
}
|
else
|
else
|
/* If we did not use this insn to make a replacement, any overlap
|
/* If we did not use this insn to make a replacement, any overlap
|
between stores in this insn and our expression will cause the
|
between stores in this insn and our expression will cause the
|
expression to become invalid. */
|
expression to become invalid. */
|
if (for_each_rtx (expr, altered_reg_used, this_altered))
|
if (for_each_rtx (expr, altered_reg_used, this_altered))
|
goto out;
|
goto out;
|
|
|
if (CONSTANT_P (*expr))
|
if (CONSTANT_P (*expr))
|
goto out;
|
goto out;
|
|
|
IOR_REG_SET (altered, this_altered);
|
IOR_REG_SET (altered, this_altered);
|
|
|
/* If the expression now contains regs that have been altered, we
|
/* If the expression now contains regs that have been altered, we
|
can't return it to the caller. However, it is still valid for
|
can't return it to the caller. However, it is still valid for
|
further simplification, so keep searching to see if we can
|
further simplification, so keep searching to see if we can
|
eventually turn it into a constant. */
|
eventually turn it into a constant. */
|
if (for_each_rtx (expr, altered_reg_used, altered))
|
if (for_each_rtx (expr, altered_reg_used, altered))
|
expression_valid = false;
|
expression_valid = false;
|
if (expression_valid)
|
if (expression_valid)
|
last_valid_expr = *expr;
|
last_valid_expr = *expr;
|
}
|
}
|
|
|
if (!single_pred_p (e->src)
|
if (!single_pred_p (e->src)
|
|| single_pred (e->src) == ENTRY_BLOCK_PTR)
|
|| single_pred (e->src) == ENTRY_BLOCK_PTR)
|
break;
|
break;
|
e = single_pred_edge (e->src);
|
e = single_pred_edge (e->src);
|
}
|
}
|
|
|
out:
|
out:
|
free_EXPR_LIST_list (&cond_list);
|
free_EXPR_LIST_list (&cond_list);
|
if (!CONSTANT_P (*expr))
|
if (!CONSTANT_P (*expr))
|
*expr = last_valid_expr;
|
*expr = last_valid_expr;
|
FREE_REG_SET (altered);
|
FREE_REG_SET (altered);
|
FREE_REG_SET (this_altered);
|
FREE_REG_SET (this_altered);
|
}
|
}
|
|
|
/* Transforms invariant IV into MODE. Adds assumptions based on the fact
|
/* Transforms invariant IV into MODE. Adds assumptions based on the fact
|
that IV occurs as left operands of comparison COND and its signedness
|
that IV occurs as left operands of comparison COND and its signedness
|
is SIGNED_P to DESC. */
|
is SIGNED_P to DESC. */
|
|
|
static void
|
static void
|
shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
|
shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
|
enum rtx_code cond, bool signed_p, struct niter_desc *desc)
|
enum rtx_code cond, bool signed_p, struct niter_desc *desc)
|
{
|
{
|
rtx mmin, mmax, cond_over, cond_under;
|
rtx mmin, mmax, cond_over, cond_under;
|
|
|
get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
|
get_mode_bounds (mode, signed_p, iv->extend_mode, &mmin, &mmax);
|
cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
|
cond_under = simplify_gen_relational (LT, SImode, iv->extend_mode,
|
iv->base, mmin);
|
iv->base, mmin);
|
cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
|
cond_over = simplify_gen_relational (GT, SImode, iv->extend_mode,
|
iv->base, mmax);
|
iv->base, mmax);
|
|
|
switch (cond)
|
switch (cond)
|
{
|
{
|
case LE:
|
case LE:
|
case LT:
|
case LT:
|
case LEU:
|
case LEU:
|
case LTU:
|
case LTU:
|
if (cond_under != const0_rtx)
|
if (cond_under != const0_rtx)
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, cond_under, desc->infinite);
|
alloc_EXPR_LIST (0, cond_under, desc->infinite);
|
if (cond_over != const0_rtx)
|
if (cond_over != const0_rtx)
|
desc->noloop_assumptions =
|
desc->noloop_assumptions =
|
alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
|
alloc_EXPR_LIST (0, cond_over, desc->noloop_assumptions);
|
break;
|
break;
|
|
|
case GE:
|
case GE:
|
case GT:
|
case GT:
|
case GEU:
|
case GEU:
|
case GTU:
|
case GTU:
|
if (cond_over != const0_rtx)
|
if (cond_over != const0_rtx)
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, cond_over, desc->infinite);
|
alloc_EXPR_LIST (0, cond_over, desc->infinite);
|
if (cond_under != const0_rtx)
|
if (cond_under != const0_rtx)
|
desc->noloop_assumptions =
|
desc->noloop_assumptions =
|
alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
|
alloc_EXPR_LIST (0, cond_under, desc->noloop_assumptions);
|
break;
|
break;
|
|
|
case NE:
|
case NE:
|
if (cond_over != const0_rtx)
|
if (cond_over != const0_rtx)
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, cond_over, desc->infinite);
|
alloc_EXPR_LIST (0, cond_over, desc->infinite);
|
if (cond_under != const0_rtx)
|
if (cond_under != const0_rtx)
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, cond_under, desc->infinite);
|
alloc_EXPR_LIST (0, cond_under, desc->infinite);
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
iv->mode = mode;
|
iv->mode = mode;
|
iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
|
iv->extend = signed_p ? SIGN_EXTEND : ZERO_EXTEND;
|
}
|
}
|
|
|
/* Transforms IV0 and IV1 compared by COND so that they are both compared as
|
/* Transforms IV0 and IV1 compared by COND so that they are both compared as
|
subregs of the same mode if possible (sometimes it is necessary to add
|
subregs of the same mode if possible (sometimes it is necessary to add
|
some assumptions to DESC). */
|
some assumptions to DESC). */
|
|
|
static bool
|
static bool
|
canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
|
canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
|
enum rtx_code cond, struct niter_desc *desc)
|
enum rtx_code cond, struct niter_desc *desc)
|
{
|
{
|
enum machine_mode comp_mode;
|
enum machine_mode comp_mode;
|
bool signed_p;
|
bool signed_p;
|
|
|
/* If the ivs behave specially in the first iteration, or are
|
/* If the ivs behave specially in the first iteration, or are
|
added/multiplied after extending, we ignore them. */
|
added/multiplied after extending, we ignore them. */
|
if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
|
if (iv0->first_special || iv0->mult != const1_rtx || iv0->delta != const0_rtx)
|
return false;
|
return false;
|
if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
|
if (iv1->first_special || iv1->mult != const1_rtx || iv1->delta != const0_rtx)
|
return false;
|
return false;
|
|
|
/* If there is some extend, it must match signedness of the comparison. */
|
/* If there is some extend, it must match signedness of the comparison. */
|
switch (cond)
|
switch (cond)
|
{
|
{
|
case LE:
|
case LE:
|
case LT:
|
case LT:
|
if (iv0->extend == ZERO_EXTEND
|
if (iv0->extend == ZERO_EXTEND
|
|| iv1->extend == ZERO_EXTEND)
|
|| iv1->extend == ZERO_EXTEND)
|
return false;
|
return false;
|
signed_p = true;
|
signed_p = true;
|
break;
|
break;
|
|
|
case LEU:
|
case LEU:
|
case LTU:
|
case LTU:
|
if (iv0->extend == SIGN_EXTEND
|
if (iv0->extend == SIGN_EXTEND
|
|| iv1->extend == SIGN_EXTEND)
|
|| iv1->extend == SIGN_EXTEND)
|
return false;
|
return false;
|
signed_p = false;
|
signed_p = false;
|
break;
|
break;
|
|
|
case NE:
|
case NE:
|
if (iv0->extend != UNKNOWN
|
if (iv0->extend != UNKNOWN
|
&& iv1->extend != UNKNOWN
|
&& iv1->extend != UNKNOWN
|
&& iv0->extend != iv1->extend)
|
&& iv0->extend != iv1->extend)
|
return false;
|
return false;
|
|
|
signed_p = false;
|
signed_p = false;
|
if (iv0->extend != UNKNOWN)
|
if (iv0->extend != UNKNOWN)
|
signed_p = iv0->extend == SIGN_EXTEND;
|
signed_p = iv0->extend == SIGN_EXTEND;
|
if (iv1->extend != UNKNOWN)
|
if (iv1->extend != UNKNOWN)
|
signed_p = iv1->extend == SIGN_EXTEND;
|
signed_p = iv1->extend == SIGN_EXTEND;
|
break;
|
break;
|
|
|
default:
|
default:
|
gcc_unreachable ();
|
gcc_unreachable ();
|
}
|
}
|
|
|
/* Values of both variables should be computed in the same mode. These
|
/* Values of both variables should be computed in the same mode. These
|
might indeed be different, if we have comparison like
|
might indeed be different, if we have comparison like
|
|
|
(compare (subreg:SI (iv0)) (subreg:SI (iv1)))
|
(compare (subreg:SI (iv0)) (subreg:SI (iv1)))
|
|
|
and iv0 and iv1 are both ivs iterating in SI mode, but calculated
|
and iv0 and iv1 are both ivs iterating in SI mode, but calculated
|
in different modes. This does not seem impossible to handle, but
|
in different modes. This does not seem impossible to handle, but
|
it hardly ever occurs in practice.
|
it hardly ever occurs in practice.
|
|
|
The only exception is the case when one of operands is invariant.
|
The only exception is the case when one of operands is invariant.
|
For example pentium 3 generates comparisons like
|
For example pentium 3 generates comparisons like
|
(lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
|
(lt (subreg:HI (reg:SI)) 100). Here we assign HImode to 100, but we
|
definitely do not want this prevent the optimization. */
|
definitely do not want this prevent the optimization. */
|
comp_mode = iv0->extend_mode;
|
comp_mode = iv0->extend_mode;
|
if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
|
if (GET_MODE_BITSIZE (comp_mode) < GET_MODE_BITSIZE (iv1->extend_mode))
|
comp_mode = iv1->extend_mode;
|
comp_mode = iv1->extend_mode;
|
|
|
if (iv0->extend_mode != comp_mode)
|
if (iv0->extend_mode != comp_mode)
|
{
|
{
|
if (iv0->mode != iv0->extend_mode
|
if (iv0->mode != iv0->extend_mode
|
|| iv0->step != const0_rtx)
|
|| iv0->step != const0_rtx)
|
return false;
|
return false;
|
|
|
iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
|
iv0->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
|
comp_mode, iv0->base, iv0->mode);
|
comp_mode, iv0->base, iv0->mode);
|
iv0->extend_mode = comp_mode;
|
iv0->extend_mode = comp_mode;
|
}
|
}
|
|
|
if (iv1->extend_mode != comp_mode)
|
if (iv1->extend_mode != comp_mode)
|
{
|
{
|
if (iv1->mode != iv1->extend_mode
|
if (iv1->mode != iv1->extend_mode
|
|| iv1->step != const0_rtx)
|
|| iv1->step != const0_rtx)
|
return false;
|
return false;
|
|
|
iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
|
iv1->base = simplify_gen_unary (signed_p ? SIGN_EXTEND : ZERO_EXTEND,
|
comp_mode, iv1->base, iv1->mode);
|
comp_mode, iv1->base, iv1->mode);
|
iv1->extend_mode = comp_mode;
|
iv1->extend_mode = comp_mode;
|
}
|
}
|
|
|
/* Check that both ivs belong to a range of a single mode. If one of the
|
/* Check that both ivs belong to a range of a single mode. If one of the
|
operands is an invariant, we may need to shorten it into the common
|
operands is an invariant, we may need to shorten it into the common
|
mode. */
|
mode. */
|
if (iv0->mode == iv0->extend_mode
|
if (iv0->mode == iv0->extend_mode
|
&& iv0->step == const0_rtx
|
&& iv0->step == const0_rtx
|
&& iv0->mode != iv1->mode)
|
&& iv0->mode != iv1->mode)
|
shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
|
shorten_into_mode (iv0, iv1->mode, cond, signed_p, desc);
|
|
|
if (iv1->mode == iv1->extend_mode
|
if (iv1->mode == iv1->extend_mode
|
&& iv1->step == const0_rtx
|
&& iv1->step == const0_rtx
|
&& iv0->mode != iv1->mode)
|
&& iv0->mode != iv1->mode)
|
shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
|
shorten_into_mode (iv1, iv0->mode, swap_condition (cond), signed_p, desc);
|
|
|
if (iv0->mode != iv1->mode)
|
if (iv0->mode != iv1->mode)
|
return false;
|
return false;
|
|
|
desc->mode = iv0->mode;
|
desc->mode = iv0->mode;
|
desc->signed_p = signed_p;
|
desc->signed_p = signed_p;
|
|
|
return true;
|
return true;
|
}
|
}
|
|
|
/* Tries to estimate the maximum number of iterations in LOOP, and store the
|
/* 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
|
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
|
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. */
|
expression for the number of iterations, before we tried to simplify it. */
|
|
|
static unsigned HOST_WIDEST_INT
|
static unsigned HOST_WIDEST_INT
|
determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
|
determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
|
{
|
{
|
rtx niter = desc->niter_expr;
|
rtx niter = desc->niter_expr;
|
rtx mmin, mmax, cmp;
|
rtx mmin, mmax, cmp;
|
unsigned HOST_WIDEST_INT nmax, inc;
|
unsigned HOST_WIDEST_INT nmax, inc;
|
|
|
if (GET_CODE (niter) == AND
|
if (GET_CODE (niter) == AND
|
&& CONST_INT_P (XEXP (niter, 0)))
|
&& CONST_INT_P (XEXP (niter, 0)))
|
{
|
{
|
nmax = INTVAL (XEXP (niter, 0));
|
nmax = INTVAL (XEXP (niter, 0));
|
if (!(nmax & (nmax + 1)))
|
if (!(nmax & (nmax + 1)))
|
{
|
{
|
desc->niter_max = nmax;
|
desc->niter_max = nmax;
|
return nmax;
|
return nmax;
|
}
|
}
|
}
|
}
|
|
|
get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
|
get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
|
nmax = INTVAL (mmax) - INTVAL (mmin);
|
nmax = INTVAL (mmax) - INTVAL (mmin);
|
|
|
if (GET_CODE (niter) == UDIV)
|
if (GET_CODE (niter) == UDIV)
|
{
|
{
|
if (!CONST_INT_P (XEXP (niter, 1)))
|
if (!CONST_INT_P (XEXP (niter, 1)))
|
{
|
{
|
desc->niter_max = nmax;
|
desc->niter_max = nmax;
|
return nmax;
|
return nmax;
|
}
|
}
|
inc = INTVAL (XEXP (niter, 1));
|
inc = INTVAL (XEXP (niter, 1));
|
niter = XEXP (niter, 0);
|
niter = XEXP (niter, 0);
|
}
|
}
|
else
|
else
|
inc = 1;
|
inc = 1;
|
|
|
/* We could use a binary search here, but for now improving the upper
|
/* We could use a binary search here, but for now improving the upper
|
bound by just one eliminates one important corner case. */
|
bound by just one eliminates one important corner case. */
|
cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
|
cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
|
desc->mode, old_niter, mmax);
|
desc->mode, old_niter, mmax);
|
simplify_using_initial_values (loop, UNKNOWN, &cmp);
|
simplify_using_initial_values (loop, UNKNOWN, &cmp);
|
if (cmp == const_true_rtx)
|
if (cmp == const_true_rtx)
|
{
|
{
|
nmax--;
|
nmax--;
|
|
|
if (dump_file)
|
if (dump_file)
|
fprintf (dump_file, ";; improved upper bound by one.\n");
|
fprintf (dump_file, ";; improved upper bound by one.\n");
|
}
|
}
|
desc->niter_max = nmax / inc;
|
desc->niter_max = nmax / inc;
|
return nmax / inc;
|
return nmax / inc;
|
}
|
}
|
|
|
/* Computes number of iterations of the CONDITION in INSN in LOOP and stores
|
/* Computes number of iterations of the CONDITION in INSN in LOOP and stores
|
the result into DESC. Very similar to determine_number_of_iterations
|
the result into DESC. Very similar to determine_number_of_iterations
|
(basically its rtl version), complicated by things like subregs. */
|
(basically its rtl version), complicated by things like subregs. */
|
|
|
static void
|
static void
|
iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
|
iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
|
struct niter_desc *desc)
|
struct niter_desc *desc)
|
{
|
{
|
rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
|
rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;
|
struct rtx_iv iv0, iv1, tmp_iv;
|
struct rtx_iv iv0, iv1, tmp_iv;
|
rtx assumption, may_not_xform;
|
rtx assumption, may_not_xform;
|
enum rtx_code cond;
|
enum rtx_code cond;
|
enum machine_mode mode, comp_mode;
|
enum machine_mode mode, comp_mode;
|
rtx mmin, mmax, mode_mmin, mode_mmax;
|
rtx mmin, mmax, mode_mmin, mode_mmax;
|
unsigned HOST_WIDEST_INT s, size, d, inv;
|
unsigned HOST_WIDEST_INT s, size, d, inv;
|
HOST_WIDEST_INT up, down, inc, step_val;
|
HOST_WIDEST_INT up, down, inc, step_val;
|
int was_sharp = false;
|
int was_sharp = false;
|
rtx old_niter;
|
rtx old_niter;
|
bool step_is_pow2;
|
bool step_is_pow2;
|
|
|
/* The meaning of these assumptions is this:
|
/* The meaning of these assumptions is this:
|
if !assumptions
|
if !assumptions
|
then the rest of information does not have to be valid
|
then the rest of information does not have to be valid
|
if noloop_assumptions then the loop does not roll
|
if noloop_assumptions then the loop does not roll
|
if infinite then this exit is never used */
|
if infinite then this exit is never used */
|
|
|
desc->assumptions = NULL_RTX;
|
desc->assumptions = NULL_RTX;
|
desc->noloop_assumptions = NULL_RTX;
|
desc->noloop_assumptions = NULL_RTX;
|
desc->infinite = NULL_RTX;
|
desc->infinite = NULL_RTX;
|
desc->simple_p = true;
|
desc->simple_p = true;
|
|
|
desc->const_iter = false;
|
desc->const_iter = false;
|
desc->niter_expr = NULL_RTX;
|
desc->niter_expr = NULL_RTX;
|
desc->niter_max = 0;
|
desc->niter_max = 0;
|
|
|
cond = GET_CODE (condition);
|
cond = GET_CODE (condition);
|
gcc_assert (COMPARISON_P (condition));
|
gcc_assert (COMPARISON_P (condition));
|
|
|
mode = GET_MODE (XEXP (condition, 0));
|
mode = GET_MODE (XEXP (condition, 0));
|
if (mode == VOIDmode)
|
if (mode == VOIDmode)
|
mode = GET_MODE (XEXP (condition, 1));
|
mode = GET_MODE (XEXP (condition, 1));
|
/* The constant comparisons should be folded. */
|
/* The constant comparisons should be folded. */
|
gcc_assert (mode != VOIDmode);
|
gcc_assert (mode != VOIDmode);
|
|
|
/* We only handle integers or pointers. */
|
/* We only handle integers or pointers. */
|
if (GET_MODE_CLASS (mode) != MODE_INT
|
if (GET_MODE_CLASS (mode) != MODE_INT
|
&& GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
|
&& GET_MODE_CLASS (mode) != MODE_PARTIAL_INT)
|
goto fail;
|
goto fail;
|
|
|
op0 = XEXP (condition, 0);
|
op0 = XEXP (condition, 0);
|
if (!iv_analyze (insn, op0, &iv0))
|
if (!iv_analyze (insn, op0, &iv0))
|
goto fail;
|
goto fail;
|
if (iv0.extend_mode == VOIDmode)
|
if (iv0.extend_mode == VOIDmode)
|
iv0.mode = iv0.extend_mode = mode;
|
iv0.mode = iv0.extend_mode = mode;
|
|
|
op1 = XEXP (condition, 1);
|
op1 = XEXP (condition, 1);
|
if (!iv_analyze (insn, op1, &iv1))
|
if (!iv_analyze (insn, op1, &iv1))
|
goto fail;
|
goto fail;
|
if (iv1.extend_mode == VOIDmode)
|
if (iv1.extend_mode == VOIDmode)
|
iv1.mode = iv1.extend_mode = mode;
|
iv1.mode = iv1.extend_mode = mode;
|
|
|
if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
|
if (GET_MODE_BITSIZE (iv0.extend_mode) > HOST_BITS_PER_WIDE_INT
|
|| GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
|
|| GET_MODE_BITSIZE (iv1.extend_mode) > HOST_BITS_PER_WIDE_INT)
|
goto fail;
|
goto fail;
|
|
|
/* Check condition and normalize it. */
|
/* Check condition and normalize it. */
|
|
|
switch (cond)
|
switch (cond)
|
{
|
{
|
case GE:
|
case GE:
|
case GT:
|
case GT:
|
case GEU:
|
case GEU:
|
case GTU:
|
case GTU:
|
tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
|
tmp_iv = iv0; iv0 = iv1; iv1 = tmp_iv;
|
cond = swap_condition (cond);
|
cond = swap_condition (cond);
|
break;
|
break;
|
case NE:
|
case NE:
|
case LE:
|
case LE:
|
case LEU:
|
case LEU:
|
case LT:
|
case LT:
|
case LTU:
|
case LTU:
|
break;
|
break;
|
default:
|
default:
|
goto fail;
|
goto fail;
|
}
|
}
|
|
|
/* Handle extends. This is relatively nontrivial, so we only try in some
|
/* Handle extends. This is relatively nontrivial, so we only try in some
|
easy cases, when we can canonicalize the ivs (possibly by adding some
|
easy cases, when we can canonicalize the ivs (possibly by adding some
|
assumptions) to shape subreg (base + i * step). This function also fills
|
assumptions) to shape subreg (base + i * step). This function also fills
|
in desc->mode and desc->signed_p. */
|
in desc->mode and desc->signed_p. */
|
|
|
if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
|
if (!canonicalize_iv_subregs (&iv0, &iv1, cond, desc))
|
goto fail;
|
goto fail;
|
|
|
comp_mode = iv0.extend_mode;
|
comp_mode = iv0.extend_mode;
|
mode = iv0.mode;
|
mode = iv0.mode;
|
size = GET_MODE_BITSIZE (mode);
|
size = GET_MODE_BITSIZE (mode);
|
get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
|
get_mode_bounds (mode, (cond == LE || cond == LT), comp_mode, &mmin, &mmax);
|
mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
|
mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
|
mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
|
mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
|
|
|
if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
|
if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))
|
goto fail;
|
goto fail;
|
|
|
/* We can take care of the case of two induction variables chasing each other
|
/* We can take care of the case of two induction variables chasing each other
|
if the test is NE. I have never seen a loop using it, but still it is
|
if the test is NE. I have never seen a loop using it, but still it is
|
cool. */
|
cool. */
|
if (iv0.step != const0_rtx && iv1.step != const0_rtx)
|
if (iv0.step != const0_rtx && iv1.step != const0_rtx)
|
{
|
{
|
if (cond != NE)
|
if (cond != NE)
|
goto fail;
|
goto fail;
|
|
|
iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
|
iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
|
iv1.step = const0_rtx;
|
iv1.step = const0_rtx;
|
}
|
}
|
|
|
/* This is either infinite loop or the one that ends immediately, depending
|
/* This is either infinite loop or the one that ends immediately, depending
|
on initial values. Unswitching should remove this kind of conditions. */
|
on initial values. Unswitching should remove this kind of conditions. */
|
if (iv0.step == const0_rtx && iv1.step == const0_rtx)
|
if (iv0.step == const0_rtx && iv1.step == const0_rtx)
|
goto fail;
|
goto fail;
|
|
|
if (cond != NE)
|
if (cond != NE)
|
{
|
{
|
if (iv0.step == const0_rtx)
|
if (iv0.step == const0_rtx)
|
step_val = -INTVAL (iv1.step);
|
step_val = -INTVAL (iv1.step);
|
else
|
else
|
step_val = INTVAL (iv0.step);
|
step_val = INTVAL (iv0.step);
|
|
|
/* Ignore loops of while (i-- < 10) type. */
|
/* Ignore loops of while (i-- < 10) type. */
|
if (step_val < 0)
|
if (step_val < 0)
|
goto fail;
|
goto fail;
|
|
|
step_is_pow2 = !(step_val & (step_val - 1));
|
step_is_pow2 = !(step_val & (step_val - 1));
|
}
|
}
|
else
|
else
|
{
|
{
|
/* We do not care about whether the step is power of two in this
|
/* We do not care about whether the step is power of two in this
|
case. */
|
case. */
|
step_is_pow2 = false;
|
step_is_pow2 = false;
|
step_val = 0;
|
step_val = 0;
|
}
|
}
|
|
|
/* Some more condition normalization. We must record some assumptions
|
/* Some more condition normalization. We must record some assumptions
|
due to overflows. */
|
due to overflows. */
|
switch (cond)
|
switch (cond)
|
{
|
{
|
case LT:
|
case LT:
|
case LTU:
|
case LTU:
|
/* We want to take care only of non-sharp relationals; this is easy,
|
/* We want to take care only of non-sharp relationals; this is easy,
|
as in cases the overflow would make the transformation unsafe
|
as in cases the overflow would make the transformation unsafe
|
the loop does not roll. Seemingly it would make more sense to want
|
the loop does not roll. Seemingly it would make more sense to want
|
to take care of sharp relationals instead, as NE is more similar to
|
to take care of sharp relationals instead, as NE is more similar to
|
them, but the problem is that here the transformation would be more
|
them, but the problem is that here the transformation would be more
|
difficult due to possibly infinite loops. */
|
difficult due to possibly infinite loops. */
|
if (iv0.step == const0_rtx)
|
if (iv0.step == const0_rtx)
|
{
|
{
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
|
assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
|
mode_mmax);
|
mode_mmax);
|
if (assumption == const_true_rtx)
|
if (assumption == const_true_rtx)
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
iv0.base = simplify_gen_binary (PLUS, comp_mode,
|
iv0.base = simplify_gen_binary (PLUS, comp_mode,
|
iv0.base, const1_rtx);
|
iv0.base, const1_rtx);
|
}
|
}
|
else
|
else
|
{
|
{
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
|
assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
|
mode_mmin);
|
mode_mmin);
|
if (assumption == const_true_rtx)
|
if (assumption == const_true_rtx)
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
iv1.base = simplify_gen_binary (PLUS, comp_mode,
|
iv1.base = simplify_gen_binary (PLUS, comp_mode,
|
iv1.base, constm1_rtx);
|
iv1.base, constm1_rtx);
|
}
|
}
|
|
|
if (assumption != const0_rtx)
|
if (assumption != const0_rtx)
|
desc->noloop_assumptions =
|
desc->noloop_assumptions =
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
cond = (cond == LT) ? LE : LEU;
|
cond = (cond == LT) ? LE : LEU;
|
|
|
/* It will be useful to be able to tell the difference once more in
|
/* It will be useful to be able to tell the difference once more in
|
LE -> NE reduction. */
|
LE -> NE reduction. */
|
was_sharp = true;
|
was_sharp = true;
|
break;
|
break;
|
default: ;
|
default: ;
|
}
|
}
|
|
|
/* Take care of trivially infinite loops. */
|
/* Take care of trivially infinite loops. */
|
if (cond != NE)
|
if (cond != NE)
|
{
|
{
|
if (iv0.step == const0_rtx)
|
if (iv0.step == const0_rtx)
|
{
|
{
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
if (rtx_equal_p (tmp, mode_mmin))
|
if (rtx_equal_p (tmp, mode_mmin))
|
{
|
{
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
|
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
|
/* Fill in the remaining fields somehow. */
|
/* Fill in the remaining fields somehow. */
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
}
|
}
|
}
|
}
|
else
|
else
|
{
|
{
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
if (rtx_equal_p (tmp, mode_mmax))
|
if (rtx_equal_p (tmp, mode_mmax))
|
{
|
{
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
|
alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
|
/* Fill in the remaining fields somehow. */
|
/* Fill in the remaining fields somehow. */
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
}
|
}
|
}
|
}
|
}
|
}
|
|
|
/* If we can we want to take care of NE conditions instead of size
|
/* If we can we want to take care of NE conditions instead of size
|
comparisons, as they are much more friendly (most importantly
|
comparisons, as they are much more friendly (most importantly
|
this takes care of special handling of loops with step 1). We can
|
this takes care of special handling of loops with step 1). We can
|
do it if we first check that upper bound is greater or equal to
|
do it if we first check that upper bound is greater or equal to
|
lower bound, their difference is constant c modulo step and that
|
lower bound, their difference is constant c modulo step and that
|
there is not an overflow. */
|
there is not an overflow. */
|
if (cond != NE)
|
if (cond != NE)
|
{
|
{
|
if (iv0.step == const0_rtx)
|
if (iv0.step == const0_rtx)
|
step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
|
step = simplify_gen_unary (NEG, comp_mode, iv1.step, comp_mode);
|
else
|
else
|
step = iv0.step;
|
step = iv0.step;
|
delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
|
delta = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
|
delta = lowpart_subreg (mode, delta, comp_mode);
|
delta = lowpart_subreg (mode, delta, comp_mode);
|
delta = simplify_gen_binary (UMOD, mode, delta, step);
|
delta = simplify_gen_binary (UMOD, mode, delta, step);
|
may_xform = const0_rtx;
|
may_xform = const0_rtx;
|
may_not_xform = const_true_rtx;
|
may_not_xform = const_true_rtx;
|
|
|
if (CONST_INT_P (delta))
|
if (CONST_INT_P (delta))
|
{
|
{
|
if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
|
if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
|
{
|
{
|
/* A special case. We have transformed condition of type
|
/* A special case. We have transformed condition of type
|
for (i = 0; i < 4; i += 4)
|
for (i = 0; i < 4; i += 4)
|
into
|
into
|
for (i = 0; i <= 3; i += 4)
|
for (i = 0; i <= 3; i += 4)
|
obviously if the test for overflow during that transformation
|
obviously if the test for overflow during that transformation
|
passed, we cannot overflow here. Most importantly any
|
passed, we cannot overflow here. Most importantly any
|
loop with sharp end condition and step 1 falls into this
|
loop with sharp end condition and step 1 falls into this
|
category, so handling this case specially is definitely
|
category, so handling this case specially is definitely
|
worth the troubles. */
|
worth the troubles. */
|
may_xform = const_true_rtx;
|
may_xform = const_true_rtx;
|
}
|
}
|
else if (iv0.step == const0_rtx)
|
else if (iv0.step == const0_rtx)
|
{
|
{
|
bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
|
bound = simplify_gen_binary (PLUS, comp_mode, mmin, step);
|
bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
|
bound = simplify_gen_binary (MINUS, comp_mode, bound, delta);
|
bound = lowpart_subreg (mode, bound, comp_mode);
|
bound = lowpart_subreg (mode, bound, comp_mode);
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv0.base, comp_mode);
|
may_xform = simplify_gen_relational (cond, SImode, mode,
|
may_xform = simplify_gen_relational (cond, SImode, mode,
|
bound, tmp);
|
bound, tmp);
|
may_not_xform = simplify_gen_relational (reverse_condition (cond),
|
may_not_xform = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode,
|
SImode, mode,
|
bound, tmp);
|
bound, tmp);
|
}
|
}
|
else
|
else
|
{
|
{
|
bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
|
bound = simplify_gen_binary (MINUS, comp_mode, mmax, step);
|
bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
|
bound = simplify_gen_binary (PLUS, comp_mode, bound, delta);
|
bound = lowpart_subreg (mode, bound, comp_mode);
|
bound = lowpart_subreg (mode, bound, comp_mode);
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp = lowpart_subreg (mode, iv1.base, comp_mode);
|
may_xform = simplify_gen_relational (cond, SImode, mode,
|
may_xform = simplify_gen_relational (cond, SImode, mode,
|
tmp, bound);
|
tmp, bound);
|
may_not_xform = simplify_gen_relational (reverse_condition (cond),
|
may_not_xform = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode,
|
SImode, mode,
|
tmp, bound);
|
tmp, bound);
|
}
|
}
|
}
|
}
|
|
|
if (may_xform != const0_rtx)
|
if (may_xform != const0_rtx)
|
{
|
{
|
/* We perform the transformation always provided that it is not
|
/* We perform the transformation always provided that it is not
|
completely senseless. This is OK, as we would need this assumption
|
completely senseless. This is OK, as we would need this assumption
|
to determine the number of iterations anyway. */
|
to determine the number of iterations anyway. */
|
if (may_xform != const_true_rtx)
|
if (may_xform != const_true_rtx)
|
{
|
{
|
/* If the step is a power of two and the final value we have
|
/* If the step is a power of two and the final value we have
|
computed overflows, the cycle is infinite. Otherwise it
|
computed overflows, the cycle is infinite. Otherwise it
|
is nontrivial to compute the number of iterations. */
|
is nontrivial to compute the number of iterations. */
|
if (step_is_pow2)
|
if (step_is_pow2)
|
desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
|
desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
|
desc->infinite);
|
desc->infinite);
|
else
|
else
|
desc->assumptions = alloc_EXPR_LIST (0, may_xform,
|
desc->assumptions = alloc_EXPR_LIST (0, may_xform,
|
desc->assumptions);
|
desc->assumptions);
|
}
|
}
|
|
|
/* We are going to lose some information about upper bound on
|
/* We are going to lose some information about upper bound on
|
number of iterations in this step, so record the information
|
number of iterations in this step, so record the information
|
here. */
|
here. */
|
inc = INTVAL (iv0.step) - INTVAL (iv1.step);
|
inc = INTVAL (iv0.step) - INTVAL (iv1.step);
|
if (CONST_INT_P (iv1.base))
|
if (CONST_INT_P (iv1.base))
|
up = INTVAL (iv1.base);
|
up = INTVAL (iv1.base);
|
else
|
else
|
up = INTVAL (mode_mmax) - inc;
|
up = INTVAL (mode_mmax) - inc;
|
down = INTVAL (CONST_INT_P (iv0.base)
|
down = INTVAL (CONST_INT_P (iv0.base)
|
? iv0.base
|
? iv0.base
|
: mode_mmin);
|
: mode_mmin);
|
desc->niter_max = (up - down) / inc + 1;
|
desc->niter_max = (up - down) / inc + 1;
|
|
|
if (iv0.step == const0_rtx)
|
if (iv0.step == const0_rtx)
|
{
|
{
|
iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
|
iv0.base = simplify_gen_binary (PLUS, comp_mode, iv0.base, delta);
|
iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
|
iv0.base = simplify_gen_binary (MINUS, comp_mode, iv0.base, step);
|
}
|
}
|
else
|
else
|
{
|
{
|
iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
|
iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, delta);
|
iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
|
iv1.base = simplify_gen_binary (PLUS, comp_mode, iv1.base, step);
|
}
|
}
|
|
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode, tmp0, tmp1);
|
SImode, mode, tmp0, tmp1);
|
if (assumption == const_true_rtx)
|
if (assumption == const_true_rtx)
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
else if (assumption != const0_rtx)
|
else if (assumption != const0_rtx)
|
desc->noloop_assumptions =
|
desc->noloop_assumptions =
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
cond = NE;
|
cond = NE;
|
}
|
}
|
}
|
}
|
|
|
/* Count the number of iterations. */
|
/* Count the number of iterations. */
|
if (cond == NE)
|
if (cond == NE)
|
{
|
{
|
/* Everything we do here is just arithmetics modulo size of mode. This
|
/* Everything we do here is just arithmetics modulo size of mode. This
|
makes us able to do more involved computations of number of iterations
|
makes us able to do more involved computations of number of iterations
|
than in other cases. First transform the condition into shape
|
than in other cases. First transform the condition into shape
|
s * i <> c, with s positive. */
|
s * i <> c, with s positive. */
|
iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
|
iv1.base = simplify_gen_binary (MINUS, comp_mode, iv1.base, iv0.base);
|
iv0.base = const0_rtx;
|
iv0.base = const0_rtx;
|
iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
|
iv0.step = simplify_gen_binary (MINUS, comp_mode, iv0.step, iv1.step);
|
iv1.step = const0_rtx;
|
iv1.step = const0_rtx;
|
if (INTVAL (iv0.step) < 0)
|
if (INTVAL (iv0.step) < 0)
|
{
|
{
|
iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
|
iv0.step = simplify_gen_unary (NEG, comp_mode, iv0.step, mode);
|
iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
|
iv1.base = simplify_gen_unary (NEG, comp_mode, iv1.base, mode);
|
}
|
}
|
iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
|
iv0.step = lowpart_subreg (mode, iv0.step, comp_mode);
|
|
|
/* Let nsd (s, size of mode) = d. If d does not divide c, the loop
|
/* Let nsd (s, size of mode) = d. If d does not divide c, the loop
|
is infinite. Otherwise, the number of iterations is
|
is infinite. Otherwise, the number of iterations is
|
(inverse(s/d) * (c/d)) mod (size of mode/d). */
|
(inverse(s/d) * (c/d)) mod (size of mode/d). */
|
s = INTVAL (iv0.step); d = 1;
|
s = INTVAL (iv0.step); d = 1;
|
while (s % 2 != 1)
|
while (s % 2 != 1)
|
{
|
{
|
s /= 2;
|
s /= 2;
|
d *= 2;
|
d *= 2;
|
size--;
|
size--;
|
}
|
}
|
bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
|
bound = GEN_INT (((unsigned HOST_WIDEST_INT) 1 << (size - 1 ) << 1) - 1);
|
|
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
|
tmp = simplify_gen_binary (UMOD, mode, tmp1, GEN_INT (d));
|
assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
|
assumption = simplify_gen_relational (NE, SImode, mode, tmp, const0_rtx);
|
desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
|
desc->infinite = alloc_EXPR_LIST (0, assumption, desc->infinite);
|
|
|
tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
|
tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
|
inv = inverse (s, size);
|
inv = inverse (s, size);
|
tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
|
tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));
|
desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
|
desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (iv1.step == const0_rtx)
|
if (iv1.step == const0_rtx)
|
/* Condition in shape a + s * i <= b
|
/* Condition in shape a + s * i <= b
|
We must know that b + s does not overflow and a <= b + s and then we
|
We must know that b + s does not overflow and a <= b + s and then we
|
can compute number of iterations as (b + s - a) / s. (It might
|
can compute number of iterations as (b + s - a) / s. (It might
|
seem that we in fact could be more clever about testing the b + s
|
seem that we in fact could be more clever about testing the b + s
|
overflow condition using some information about b - a mod s,
|
overflow condition using some information about b - a mod s,
|
but it was already taken into account during LE -> NE transform). */
|
but it was already taken into account during LE -> NE transform). */
|
{
|
{
|
step = iv0.step;
|
step = iv0.step;
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
|
|
bound = simplify_gen_binary (MINUS, mode, mode_mmax,
|
bound = simplify_gen_binary (MINUS, mode, mode_mmax,
|
lowpart_subreg (mode, step,
|
lowpart_subreg (mode, step,
|
comp_mode));
|
comp_mode));
|
if (step_is_pow2)
|
if (step_is_pow2)
|
{
|
{
|
rtx t0, t1;
|
rtx t0, t1;
|
|
|
/* If s is power of 2, we know that the loop is infinite if
|
/* If s is power of 2, we know that the loop is infinite if
|
a % s <= b % s and b + s overflows. */
|
a % s <= b % s and b + s overflows. */
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode,
|
SImode, mode,
|
tmp1, bound);
|
tmp1, bound);
|
|
|
t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
|
t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
|
t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
|
t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
|
tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
|
tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
|
assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
|
assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, assumption, desc->infinite);
|
alloc_EXPR_LIST (0, assumption, desc->infinite);
|
}
|
}
|
else
|
else
|
{
|
{
|
assumption = simplify_gen_relational (cond, SImode, mode,
|
assumption = simplify_gen_relational (cond, SImode, mode,
|
tmp1, bound);
|
tmp1, bound);
|
desc->assumptions =
|
desc->assumptions =
|
alloc_EXPR_LIST (0, assumption, desc->assumptions);
|
alloc_EXPR_LIST (0, assumption, desc->assumptions);
|
}
|
}
|
|
|
tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
|
tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
|
tmp = lowpart_subreg (mode, tmp, comp_mode);
|
tmp = lowpart_subreg (mode, tmp, comp_mode);
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode, tmp0, tmp);
|
SImode, mode, tmp0, tmp);
|
|
|
delta = simplify_gen_binary (PLUS, mode, tmp1, step);
|
delta = simplify_gen_binary (PLUS, mode, tmp1, step);
|
delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
|
delta = simplify_gen_binary (MINUS, mode, delta, tmp0);
|
}
|
}
|
else
|
else
|
{
|
{
|
/* Condition in shape a <= b - s * i
|
/* Condition in shape a <= b - s * i
|
We must know that a - s does not overflow and a - s <= b and then
|
We must know that a - s does not overflow and a - s <= b and then
|
we can again compute number of iterations as (b - (a - s)) / s. */
|
we can again compute number of iterations as (b - (a - s)) / s. */
|
step = simplify_gen_unary (NEG, mode, iv1.step, mode);
|
step = simplify_gen_unary (NEG, mode, iv1.step, mode);
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
|
|
|
bound = simplify_gen_binary (PLUS, mode, mode_mmin,
|
bound = simplify_gen_binary (PLUS, mode, mode_mmin,
|
lowpart_subreg (mode, step, comp_mode));
|
lowpart_subreg (mode, step, comp_mode));
|
if (step_is_pow2)
|
if (step_is_pow2)
|
{
|
{
|
rtx t0, t1;
|
rtx t0, t1;
|
|
|
/* If s is power of 2, we know that the loop is infinite if
|
/* If s is power of 2, we know that the loop is infinite if
|
a % s <= b % s and a - s overflows. */
|
a % s <= b % s and a - s overflows. */
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode,
|
SImode, mode,
|
bound, tmp0);
|
bound, tmp0);
|
|
|
t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
|
t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
|
t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
|
t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
|
tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
|
tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
|
assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
|
assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
|
desc->infinite =
|
desc->infinite =
|
alloc_EXPR_LIST (0, assumption, desc->infinite);
|
alloc_EXPR_LIST (0, assumption, desc->infinite);
|
}
|
}
|
else
|
else
|
{
|
{
|
assumption = simplify_gen_relational (cond, SImode, mode,
|
assumption = simplify_gen_relational (cond, SImode, mode,
|
bound, tmp0);
|
bound, tmp0);
|
desc->assumptions =
|
desc->assumptions =
|
alloc_EXPR_LIST (0, assumption, desc->assumptions);
|
alloc_EXPR_LIST (0, assumption, desc->assumptions);
|
}
|
}
|
|
|
tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
|
tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
|
tmp = lowpart_subreg (mode, tmp, comp_mode);
|
tmp = lowpart_subreg (mode, tmp, comp_mode);
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
assumption = simplify_gen_relational (reverse_condition (cond),
|
SImode, mode,
|
SImode, mode,
|
tmp, tmp1);
|
tmp, tmp1);
|
delta = simplify_gen_binary (MINUS, mode, tmp0, step);
|
delta = simplify_gen_binary (MINUS, mode, tmp0, step);
|
delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
|
delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
|
}
|
}
|
if (assumption == const_true_rtx)
|
if (assumption == const_true_rtx)
|
goto zero_iter_simplify;
|
goto zero_iter_simplify;
|
else if (assumption != const0_rtx)
|
else if (assumption != const0_rtx)
|
desc->noloop_assumptions =
|
desc->noloop_assumptions =
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
|
delta = simplify_gen_binary (UDIV, mode, delta, step);
|
delta = simplify_gen_binary (UDIV, mode, delta, step);
|
desc->niter_expr = delta;
|
desc->niter_expr = delta;
|
}
|
}
|
|
|
old_niter = desc->niter_expr;
|
old_niter = desc->niter_expr;
|
|
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
if (desc->assumptions
|
if (desc->assumptions
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
goto fail;
|
goto fail;
|
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
|
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
|
simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
|
|
|
/* Rerun the simplification. Consider code (created by copying loop headers)
|
/* Rerun the simplification. Consider code (created by copying loop headers)
|
|
|
i = 0;
|
i = 0;
|
|
|
if (0 < n)
|
if (0 < n)
|
{
|
{
|
do
|
do
|
{
|
{
|
i++;
|
i++;
|
} while (i < n);
|
} while (i < n);
|
}
|
}
|
|
|
The first pass determines that i = 0, the second pass uses it to eliminate
|
The first pass determines that i = 0, the second pass uses it to eliminate
|
noloop assumption. */
|
noloop assumption. */
|
|
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
if (desc->assumptions
|
if (desc->assumptions
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
goto fail;
|
goto fail;
|
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
|
simplify_using_initial_values (loop, IOR, &desc->noloop_assumptions);
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
|
simplify_using_initial_values (loop, UNKNOWN, &desc->niter_expr);
|
|
|
if (desc->noloop_assumptions
|
if (desc->noloop_assumptions
|
&& XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
|
&& XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
|
goto zero_iter;
|
goto zero_iter;
|
|
|
if (CONST_INT_P (desc->niter_expr))
|
if (CONST_INT_P (desc->niter_expr))
|
{
|
{
|
unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
|
unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
|
|
|
desc->const_iter = true;
|
desc->const_iter = true;
|
desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
|
desc->niter_max = desc->niter = val & GET_MODE_MASK (desc->mode);
|
}
|
}
|
else
|
else
|
{
|
{
|
if (!desc->niter_max)
|
if (!desc->niter_max)
|
desc->niter_max = determine_max_iter (loop, desc, old_niter);
|
desc->niter_max = determine_max_iter (loop, desc, old_niter);
|
|
|
/* simplify_using_initial_values does a copy propagation on the registers
|
/* simplify_using_initial_values does a copy propagation on the registers
|
in the expression for the number of iterations. This prolongs life
|
in the expression for the number of iterations. This prolongs life
|
ranges of registers and increases register pressure, and usually
|
ranges of registers and increases register pressure, and usually
|
brings no gain (and if it happens to do, the cse pass will take care
|
brings no gain (and if it happens to do, the cse pass will take care
|
of it anyway). So prevent this behavior, unless it enabled us to
|
of it anyway). So prevent this behavior, unless it enabled us to
|
derive that the number of iterations is a constant. */
|
derive that the number of iterations is a constant. */
|
desc->niter_expr = old_niter;
|
desc->niter_expr = old_niter;
|
}
|
}
|
|
|
return;
|
return;
|
|
|
zero_iter_simplify:
|
zero_iter_simplify:
|
/* Simplify the assumptions. */
|
/* Simplify the assumptions. */
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
simplify_using_initial_values (loop, AND, &desc->assumptions);
|
if (desc->assumptions
|
if (desc->assumptions
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
&& XEXP (desc->assumptions, 0) == const0_rtx)
|
goto fail;
|
goto fail;
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
simplify_using_initial_values (loop, IOR, &desc->infinite);
|
|
|
/* Fallthru. */
|
/* Fallthru. */
|
zero_iter:
|
zero_iter:
|
desc->const_iter = true;
|
desc->const_iter = true;
|
desc->niter = 0;
|
desc->niter = 0;
|
desc->niter_max = 0;
|
desc->niter_max = 0;
|
desc->noloop_assumptions = NULL_RTX;
|
desc->noloop_assumptions = NULL_RTX;
|
desc->niter_expr = const0_rtx;
|
desc->niter_expr = const0_rtx;
|
return;
|
return;
|
|
|
fail:
|
fail:
|
desc->simple_p = false;
|
desc->simple_p = false;
|
return;
|
return;
|
}
|
}
|
|
|
/* Checks whether E is a simple exit from LOOP and stores its description
|
/* Checks whether E is a simple exit from LOOP and stores its description
|
into DESC. */
|
into DESC. */
|
|
|
static void
|
static void
|
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
|
check_simple_exit (struct loop *loop, edge e, struct niter_desc *desc)
|
{
|
{
|
basic_block exit_bb;
|
basic_block exit_bb;
|
rtx condition, at;
|
rtx condition, at;
|
edge ein;
|
edge ein;
|
|
|
exit_bb = e->src;
|
exit_bb = e->src;
|
desc->simple_p = false;
|
desc->simple_p = false;
|
|
|
/* It must belong directly to the loop. */
|
/* It must belong directly to the loop. */
|
if (exit_bb->loop_father != loop)
|
if (exit_bb->loop_father != loop)
|
return;
|
return;
|
|
|
/* It must be tested (at least) once during any iteration. */
|
/* 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))
|
return;
|
return;
|
|
|
/* It must end in a simple conditional jump. */
|
/* It must end in a simple conditional jump. */
|
if (!any_condjump_p (BB_END (exit_bb)))
|
if (!any_condjump_p (BB_END (exit_bb)))
|
return;
|
return;
|
|
|
ein = EDGE_SUCC (exit_bb, 0);
|
ein = EDGE_SUCC (exit_bb, 0);
|
if (ein == e)
|
if (ein == e)
|
ein = EDGE_SUCC (exit_bb, 1);
|
ein = EDGE_SUCC (exit_bb, 1);
|
|
|
desc->out_edge = e;
|
desc->out_edge = e;
|
desc->in_edge = ein;
|
desc->in_edge = ein;
|
|
|
/* Test whether the condition is suitable. */
|
/* Test whether the condition is suitable. */
|
if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
|
if (!(condition = get_condition (BB_END (ein->src), &at, false, false)))
|
return;
|
return;
|
|
|
if (ein->flags & EDGE_FALLTHRU)
|
if (ein->flags & EDGE_FALLTHRU)
|
{
|
{
|
condition = reversed_condition (condition);
|
condition = reversed_condition (condition);
|
if (!condition)
|
if (!condition)
|
return;
|
return;
|
}
|
}
|
|
|
/* Check that we are able to determine number of iterations and fill
|
/* Check that we are able to determine number of iterations and fill
|
in information about it. */
|
in information about it. */
|
iv_number_of_iterations (loop, at, condition, desc);
|
iv_number_of_iterations (loop, at, condition, desc);
|
}
|
}
|
|
|
/* Finds a simple exit of LOOP and stores its description into DESC. */
|
/* Finds a simple exit of LOOP and stores its description into DESC. */
|
|
|
void
|
void
|
find_simple_exit (struct loop *loop, struct niter_desc *desc)
|
find_simple_exit (struct loop *loop, struct niter_desc *desc)
|
{
|
{
|
unsigned i;
|
unsigned i;
|
basic_block *body;
|
basic_block *body;
|
edge e;
|
edge e;
|
struct niter_desc act;
|
struct niter_desc act;
|
bool any = false;
|
bool any = false;
|
edge_iterator ei;
|
edge_iterator ei;
|
|
|
desc->simple_p = false;
|
desc->simple_p = false;
|
body = get_loop_body (loop);
|
body = get_loop_body (loop);
|
|
|
for (i = 0; i < loop->num_nodes; i++)
|
for (i = 0; i < loop->num_nodes; i++)
|
{
|
{
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
FOR_EACH_EDGE (e, ei, body[i]->succs)
|
{
|
{
|
if (flow_bb_inside_loop_p (loop, e->dest))
|
if (flow_bb_inside_loop_p (loop, e->dest))
|
continue;
|
continue;
|
|
|
check_simple_exit (loop, e, &act);
|
check_simple_exit (loop, e, &act);
|
if (!act.simple_p)
|
if (!act.simple_p)
|
continue;
|
continue;
|
|
|
if (!any)
|
if (!any)
|
any = true;
|
any = true;
|
else
|
else
|
{
|
{
|
/* Prefer constant iterations; the less the better. */
|
/* Prefer constant iterations; the less the better. */
|
if (!act.const_iter
|
if (!act.const_iter
|
|| (desc->const_iter && act.niter >= desc->niter))
|
|| (desc->const_iter && act.niter >= desc->niter))
|
continue;
|
continue;
|
|
|
/* Also if the actual exit may be infinite, while the old one
|
/* Also if the actual exit may be infinite, while the old one
|
not, prefer the old one. */
|
not, prefer the old one. */
|
if (act.infinite && !desc->infinite)
|
if (act.infinite && !desc->infinite)
|
continue;
|
continue;
|
}
|
}
|
|
|
*desc = act;
|
*desc = act;
|
}
|
}
|
}
|
}
|
|
|
if (dump_file)
|
if (dump_file)
|
{
|
{
|
if (desc->simple_p)
|
if (desc->simple_p)
|
{
|
{
|
fprintf (dump_file, "Loop %d is simple:\n", loop->num);
|
fprintf (dump_file, "Loop %d is simple:\n", loop->num);
|
fprintf (dump_file, " simple exit %d -> %d\n",
|
fprintf (dump_file, " simple exit %d -> %d\n",
|
desc->out_edge->src->index,
|
desc->out_edge->src->index,
|
desc->out_edge->dest->index);
|
desc->out_edge->dest->index);
|
if (desc->assumptions)
|
if (desc->assumptions)
|
{
|
{
|
fprintf (dump_file, " assumptions: ");
|
fprintf (dump_file, " assumptions: ");
|
print_rtl (dump_file, desc->assumptions);
|
print_rtl (dump_file, desc->assumptions);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
if (desc->noloop_assumptions)
|
if (desc->noloop_assumptions)
|
{
|
{
|
fprintf (dump_file, " does not roll if: ");
|
fprintf (dump_file, " does not roll if: ");
|
print_rtl (dump_file, desc->noloop_assumptions);
|
print_rtl (dump_file, desc->noloop_assumptions);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
if (desc->infinite)
|
if (desc->infinite)
|
{
|
{
|
fprintf (dump_file, " infinite if: ");
|
fprintf (dump_file, " infinite if: ");
|
print_rtl (dump_file, desc->infinite);
|
print_rtl (dump_file, desc->infinite);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
|
|
fprintf (dump_file, " number of iterations: ");
|
fprintf (dump_file, " number of iterations: ");
|
print_rtl (dump_file, desc->niter_expr);
|
print_rtl (dump_file, desc->niter_expr);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
|
|
fprintf (dump_file, " upper bound: ");
|
fprintf (dump_file, " upper bound: ");
|
fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
|
fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter_max);
|
fprintf (dump_file, "\n");
|
fprintf (dump_file, "\n");
|
}
|
}
|
else
|
else
|
fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
|
fprintf (dump_file, "Loop %d is not simple.\n", loop->num);
|
}
|
}
|
|
|
free (body);
|
free (body);
|
}
|
}
|
|
|
/* Creates a simple loop description of LOOP if it was not computed
|
/* Creates a simple loop description of LOOP if it was not computed
|
already. */
|
already. */
|
|
|
struct niter_desc *
|
struct niter_desc *
|
get_simple_loop_desc (struct loop *loop)
|
get_simple_loop_desc (struct loop *loop)
|
{
|
{
|
struct niter_desc *desc = simple_loop_desc (loop);
|
struct niter_desc *desc = simple_loop_desc (loop);
|
|
|
if (desc)
|
if (desc)
|
return desc;
|
return desc;
|
|
|
/* At least desc->infinite is not always initialized by
|
/* At least desc->infinite is not always initialized by
|
find_simple_loop_exit. */
|
find_simple_loop_exit. */
|
desc = XCNEW (struct niter_desc);
|
desc = XCNEW (struct niter_desc);
|
iv_analysis_loop_init (loop);
|
iv_analysis_loop_init (loop);
|
find_simple_exit (loop, desc);
|
find_simple_exit (loop, desc);
|
loop->aux = desc;
|
loop->aux = desc;
|
|
|
if (desc->simple_p && (desc->assumptions || desc->infinite))
|
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. */
|
We already warned at the tree level if we ran optimizations there. */
|
if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
|
if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
|
{
|
{
|
if (desc->infinite)
|
if (desc->infinite)
|
{
|
{
|
wording =
|
wording =
|
flag_unsafe_loop_optimizations
|
flag_unsafe_loop_optimizations
|
? N_("assuming that the loop is not infinite")
|
? N_("assuming that the loop is not infinite")
|
: N_("cannot optimize possibly infinite loops");
|
: N_("cannot optimize possibly infinite loops");
|
warning (OPT_Wunsafe_loop_optimizations, "%s",
|
warning (OPT_Wunsafe_loop_optimizations, "%s",
|
gettext (wording));
|
gettext (wording));
|
}
|
}
|
if (desc->assumptions)
|
if (desc->assumptions)
|
{
|
{
|
wording =
|
wording =
|
flag_unsafe_loop_optimizations
|
flag_unsafe_loop_optimizations
|
? N_("assuming that the loop counter does not overflow")
|
? N_("assuming that the loop counter does not overflow")
|
: N_("cannot optimize loop, the loop counter may overflow");
|
: N_("cannot optimize loop, the loop counter may overflow");
|
warning (OPT_Wunsafe_loop_optimizations, "%s",
|
warning (OPT_Wunsafe_loop_optimizations, "%s",
|
gettext (wording));
|
gettext (wording));
|
}
|
}
|
}
|
}
|
|
|
if (flag_unsafe_loop_optimizations)
|
if (flag_unsafe_loop_optimizations)
|
{
|
{
|
desc->assumptions = NULL_RTX;
|
desc->assumptions = NULL_RTX;
|
desc->infinite = NULL_RTX;
|
desc->infinite = NULL_RTX;
|
}
|
}
|
}
|
}
|
|
|
return desc;
|
return desc;
|
}
|
}
|
|
|
/* Releases simple loop description for LOOP. */
|
/* Releases simple loop description for LOOP. */
|
|
|
void
|
void
|
free_simple_loop_desc (struct loop *loop)
|
free_simple_loop_desc (struct loop *loop)
|
{
|
{
|
struct niter_desc *desc = simple_loop_desc (loop);
|
struct niter_desc *desc = simple_loop_desc (loop);
|
|
|
if (!desc)
|
if (!desc)
|
return;
|
return;
|
|
|
free (desc);
|
free (desc);
|
loop->aux = NULL;
|
loop->aux = NULL;
|
}
|
}
|
|
|
