* g++.dg/ext/altivec-17.C: Adjust error message.

[pf3gnuchains/gcc-fork.git] / gcc / loop-iv.c

diff --git a/gcc/loop-iv.c b/gcc/loop-iv.c
index ed0defb..16e9a52 100644 (file)
--- a/gcc/loop-iv.c
+++ b/gcc/loop-iv.c
@@ -1,51 +1,52 @@
 /* Rtl-level induction variable analysis.
 /* Rtl-level induction variable analysis.

-   Copyright (C) 2004 Free Software Foundation, Inc.
-   
+   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009
+   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
 under the terms of the GNU General Public License as published by the
 GCC is free software; you can redistribute it and/or modify it
 under the terms of the GNU General Public License as published by the

-Free Software Foundation; either version 2, or (at your option) any
+Free Software Foundation; either version 3, or (at your option) any

 later version.
 later version.

-   
+

 GCC is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.
 GCC is distributed in the hope that it will be useful, but WITHOUT
 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
 for more details.

-   
+

 You should have received a copy of the GNU General Public License
 You should have received a copy of the GNU General Public License

-along with GCC; see the file COPYING.  If not, write to the Free
-Software Foundation, 59 Temple Place - Suite 330, Boston, MA
-02111-1307, USA.  */
-
-/* This is just a very simplistic analysis of induction variables of the loop.
-   The major use is for determining the number of iterations of a loop for
-   loop unrolling, doloop optimization and branch prediction.  For this we
-   are only interested in bivs and a fairly limited set of givs that are
-   needed in the exit condition.  We also only compute the iv information on
-   demand.
-
-   The interesting registers are determined.  A register is interesting if
-
-   -- it is set only in the blocks that dominate the latch of the current loop
-   -- all its sets are simple -- i.e. in the form we understand
-
-   We also number the insns sequentially in each basic block.  For a use of the
-   interesting reg, it is now easy to find a reaching definition (there may be
-   only one).
-
-   Induction variable is then simply analyzed by walking the use-def
-   chains.
-   
-   Usage:
-
-   iv_analysis_loop_init (loop);
-   insn = iv_get_reaching_def (where, reg);
-   if (iv_analyze (insn, reg, &iv))
-     {
-       ...
-     }
-   iv_analysis_done (); */
+along with GCC; see the file COPYING3.  If not see
+<http://www.gnu.org/licenses/>.  */
+
+/* This is a simple analysis of induction variables of the loop.  The major use
+   is for determining the number of iterations of a loop for loop unrolling,
+   doloop optimization and branch prediction.  The iv information is computed
+   on demand.
+
+   Induction variables are analyzed by walking the use-def chains.  When
+   a basic induction variable (biv) is found, it is cached in the bivs
+   hash table.  When register is proved to be a biv, its description
+   is stored to DF_REF_DATA of the def reference.
+
+   The analysis works always with one loop -- you must call
+   iv_analysis_loop_init (loop) for it.  All the other functions then work with
+   this loop.   When you need to work with another loop, just call
+   iv_analysis_loop_init for it.  When you no longer need iv analysis, call
+   iv_analysis_done () to clean up the memory.
+
+   The available functions are:
+
+   iv_analyze (insn, reg, iv): Stores the description of the induction variable
+     corresponding to the use of register REG in INSN to IV.  Returns true if
+     REG is an induction variable in INSN. false otherwise.
+     If use of REG is not found in INSN, following insns are scanned (so that
+     we may call this function on insn returned by get_condition).
+   iv_analyze_result (insn, def, iv):  Stores to IV the description of the iv
+     corresponding to DEF, which is a register defined in INSN.
+   iv_analyze_expr (insn, rhs, mode, iv):  Stores to IV the description of iv
+     corresponding to expression EXPR evaluated at INSN.  All registers used bu
+     EXPR must also be used in INSN.
+*/

 
 #include "config.h"
 #include "system.h"
 
 #include "config.h"
 #include "system.h"


@@ -53,44 +54,64 @@ Software Foundation, 59 Temple Place - Suite 330, Boston, MA
 #include "tm.h"
 #include "rtl.h"
 #include "hard-reg-set.h"
 #include "tm.h"
 #include "rtl.h"
 #include "hard-reg-set.h"

+#include "obstack.h"

 #include "basic-block.h"
 #include "cfgloop.h"
 #include "expr.h"
 #include "basic-block.h"
 #include "cfgloop.h"
 #include "expr.h"

+#include "intl.h"

 #include "output.h"
 #include "output.h"

+#include "toplev.h"
+#include "df.h"
+#include "hashtab.h"

 
 

-/* The insn information.  */
+/* Possible return values of iv_get_reaching_def.  */

 
 

-struct insn_info
+enum iv_grd_result

 {
 {

-  /* Id of the insn.  */
-  unsigned luid;
+  /* More than one reaching def, or reaching def that does not
+     dominate the use.  */
+  GRD_INVALID,

 
 

-  /* The previous definition of the register defined by the single
-     set in the insn.  */
-  rtx prev_def;
+  /* The use is trivial invariant of the loop, i.e. is not changed
+     inside the loop.  */
+  GRD_INVARIANT,

 
 

-  /* The description of the iv.  */
-  struct rtx_iv iv;
+  /* The use is reached by initial value and a value from the
+     previous iteration.  */
+  GRD_MAYBE_BIV,
+
+  /* The use has single dominating def.  */
+  GRD_SINGLE_DOM
+};
+
+/* Information about a biv.  */
+
+struct biv_entry
+{
+  unsigned regno;      /* The register of the biv.  */
+  struct rtx_iv iv;    /* Value of the biv.  */

 };
 
 };
 

-static struct insn_info *insn_info;
+static bool clean_slate = true;

 
 

-/* The last definition of register.  */
+static unsigned int iv_ref_table_size = 0;

 
 

-static rtx *last_def;
+/* Table of rtx_ivs indexed by the df_ref uid field.  */
+static struct rtx_iv ** iv_ref_table;

 
 

-/* The bivs.  */
+/* Induction variable stored at the reference.  */
+#define DF_REF_IV(REF) iv_ref_table[DF_REF_ID(REF)]
+#define DF_REF_IV_SET(REF, IV) iv_ref_table[DF_REF_ID(REF)] = (IV)

 
 

-static struct rtx_iv *bivs;
+/* The current loop.  */

 
 

-/* Maximal insn number for that there is place in insn_info array.  */
+static struct loop *current_loop;

 
 

-static unsigned max_insn_no;
+/* Bivs of the current loop.  */

 
 

-/* Maximal register number for that there is place in bivs and last_def
-   arrays.  */
+static htab_t bivs;

 
 

-static unsigned max_reg_no;
+static bool iv_analyze_op (rtx, rtx, struct rtx_iv *);

 
 /* Dumps information about IV to FILE.  */
 
 
 /* Dumps information about IV to FILE.  */
 


@@ -136,23 +157,6 @@ dump_iv_info (FILE *file, struct rtx_iv *iv)
     fprintf (file, " (first special)");
 }
 
     fprintf (file, " (first special)");
 }
 

-/* Assigns luids to insns in basic block BB.  */
-
-static void
-assign_luids (basic_block bb)
-{
-  unsigned i = 0, uid;
-  rtx insn;
-
-  FOR_BB_INSNS (bb, insn)
-    {
-      uid = INSN_UID (insn);
-      insn_info[uid].luid = i++;
-      insn_info[uid].prev_def = NULL_RTX;
-      insn_info[uid].iv.analysed = false;
-    }
-}
-

 /* Generates a subreg to get the least significant part of EXPR (in mode
    INNER_MODE) to OUTER_MODE.  */
 
 /* Generates a subreg to get the least significant part of EXPR (in mode
    INNER_MODE) to OUTER_MODE.  */
 


@@ -164,6 +168,20 @@ lowpart_subreg (enum machine_mode outer_mode, rtx expr,
                              subreg_lowpart_offset (outer_mode, inner_mode));
 }
 
                              subreg_lowpart_offset (outer_mode, inner_mode));
 }
 

+static void
+check_iv_ref_table_size (void)
+{
+  if (iv_ref_table_size < DF_DEFS_TABLE_SIZE())
+    {
+      unsigned int new_size = DF_DEFS_TABLE_SIZE () + (DF_DEFS_TABLE_SIZE () / 4);
+      iv_ref_table = XRESIZEVEC (struct rtx_iv *, iv_ref_table, new_size);
+      memset (&iv_ref_table[iv_ref_table_size], 0,
+             (new_size - iv_ref_table_size) * sizeof (struct rtx_iv *));
+      iv_ref_table_size = new_size;
+    }
+}
+
+

 /* Checks whether REG is a well-behaved register.  */
 
 static bool
 /* Checks whether REG is a well-behaved register.  */
 
 static bool


@@ -188,229 +206,176 @@ simple_reg_p (rtx reg)
   if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
     return false;
 
   if (GET_MODE_CLASS (GET_MODE (reg)) != MODE_INT)
     return false;
 

-  if (last_def[r] == const0_rtx)
-    return false;
-

   return true;
 }
 
   return true;
 }
 

-/* Checks whether assignment LHS = RHS is simple enough for us to process.  */
+/* Clears the information about ivs stored in df.  */

 
 

-static bool
-simple_set_p (rtx lhs, rtx rhs)
+static void
+clear_iv_info (void)

 {
 {

-  rtx op0, op1;
-
-  if (!REG_P (lhs)
-      || !simple_reg_p (lhs))
-    return false;
-
-  if (CONSTANT_P (rhs))
-    return true;
+  unsigned i, n_defs = DF_DEFS_TABLE_SIZE ();
+  struct rtx_iv *iv;

 
 

-  switch (GET_CODE (rhs))
+  check_iv_ref_table_size ();
+  for (i = 0; i < n_defs; i++)

     {
     {

-    case SUBREG:
-    case REG:
-      return simple_reg_p (rhs);
-
-    case SIGN_EXTEND:
-    case ZERO_EXTEND:
-    case NEG:
-      return simple_reg_p (XEXP (rhs, 0));
-
-    case PLUS:
-    case MINUS:
-    case MULT:
-    case ASHIFT:
-      op0 = XEXP (rhs, 0);
-      op1 = XEXP (rhs, 1);
-
-      if (!simple_reg_p (op0)
-         && !CONSTANT_P (op0))
-       return false;
-
-      if (!simple_reg_p (op1)
-         && !CONSTANT_P (op1))
-       return false;
-
-      if (GET_CODE (rhs) == MULT
-         && !CONSTANT_P (op0)
-         && !CONSTANT_P (op1))
-       return false;
-
-      if (GET_CODE (rhs) == ASHIFT
-         && CONSTANT_P (op0))
-       return false;
-
-      return true;
-
-    default:
-      return false;
+      iv = iv_ref_table[i];
+      if (iv)
+       {
+         free (iv);
+         iv_ref_table[i] = NULL;
+       }

     }
     }

+
+  htab_empty (bivs);

 }
 
 }
 

-/* Mark single SET in INSN.  */
+/* Returns hash value for biv B.  */

 
 

-static rtx
-mark_single_set (rtx insn, rtx set)
+static hashval_t
+biv_hash (const void *b)

 {
 {

-  rtx def = SET_DEST (set), src;
-  unsigned regno, uid;
-
-  src = find_reg_equal_equiv_note (insn);
-  if (src)
-    src = XEXP (src, 0);
-  else
-    src = SET_SRC (set);
-
-  if (!simple_set_p (SET_DEST (set), src))
-    return NULL_RTX;
-
-  regno = REGNO (def);
-  uid = INSN_UID (insn);
-
-  bivs[regno].analysed = false;
-  insn_info[uid].prev_def = last_def[regno];
-  last_def[regno] = insn;
-
-  return def;
+  return ((const struct biv_entry *) b)->regno;

 }
 
 }
 

-/* Invalidate register REG unless it is equal to EXCEPT.  */
+/* Compares biv B and register R.  */

 
 

-static void
-kill_sets (rtx reg, rtx by ATTRIBUTE_UNUSED, void *except)
+static int
+biv_eq (const void *b, const void *r)

 {
 {

-  if (GET_CODE (reg) == SUBREG)
-    reg = SUBREG_REG (reg);
-  if (!REG_P (reg))
-    return;
-  if (reg == except)
-    return;
-
-  last_def[REGNO (reg)] = const0_rtx;
+  return ((const struct biv_entry *) b)->regno == REGNO ((const_rtx) r);

 }
 
 }
 

-/* Marks sets in basic block BB.  If DOM is true, BB dominates the loop
-   latch.  */
+/* Prepare the data for an induction variable analysis of a LOOP.  */

 
 

-static void
-mark_sets (basic_block bb, bool dom)
+void
+iv_analysis_loop_init (struct loop *loop)

 {
 {

-  rtx insn, set, def;
+  basic_block *body = get_loop_body_in_dom_order (loop), bb;
+  bitmap blocks = BITMAP_ALLOC (NULL);
+  unsigned i;
+
+  current_loop = loop;

 
 

-  FOR_BB_INSNS (bb, insn)
+  /* Clear the information from the analysis of the previous loop.  */
+  if (clean_slate)

     {
     {

-      if (!INSN_P (insn))
-       continue;
+      df_set_flags (DF_EQ_NOTES + DF_DEFER_INSN_RESCAN);
+      bivs = htab_create (10, biv_hash, biv_eq, free);
+      clean_slate = false;
+    }
+  else
+    clear_iv_info ();

 
 

-      if (dom
-         && (set = single_set (insn)))
-       def = mark_single_set (insn, set);
-      else
-       def = NULL_RTX;
+  for (i = 0; i < loop->num_nodes; i++)
+    {
+      bb = body[i];
+      bitmap_set_bit (blocks, bb->index);
+    }
+  /* Get rid of the ud chains before processing the rescans.  Then add
+     the problem back.  */
+  df_remove_problem (df_chain);
+  df_process_deferred_rescans ();
+  df_chain_add_problem (DF_UD_CHAIN);
+  df_note_add_problem ();
+  df_set_blocks (blocks);
+  df_analyze ();
+  if (dump_file)
+    df_dump_region (dump_file);

 
 

-      note_stores (PATTERN (insn), kill_sets, def);
-    }
+  check_iv_ref_table_size ();
+  BITMAP_FREE (blocks);
+  free (body);

 }
 
 }
 

-/* Prepare the data for an induction variable analysis of a LOOP.  */
+/* Finds the definition of REG that dominates loop latch and stores
+   it to DEF.  Returns false if there is not a single definition
+   dominating the latch.  If REG has no definition in loop, DEF
+   is set to NULL and true is returned.  */

 
 

-void
-iv_analysis_loop_init (struct loop *loop)
+static bool
+latch_dominating_def (rtx reg, df_ref *def)

 {
 {

-  basic_block *body = get_loop_body_in_dom_order (loop);
-  unsigned b;
+  df_ref single_rd = NULL, adef;
+  unsigned regno = REGNO (reg);
+  struct df_rd_bb_info *bb_info = DF_RD_BB_INFO (current_loop->latch);

 
 

-  if ((unsigned) get_max_uid () >= max_insn_no)
+  for (adef = DF_REG_DEF_CHAIN (regno); adef; adef = DF_REF_NEXT_REG (adef))

     {
     {

-      /* Add some reserve for insns and registers produced in optimizations.  */
-      max_insn_no = get_max_uid () + 100;
-      if (insn_info)
-       free (insn_info);
-      insn_info = xmalloc (max_insn_no * sizeof (struct insn_info));
-    }
+      if (!bitmap_bit_p (df->blocks_to_analyze, DF_REF_BBNO (adef))
+         || !bitmap_bit_p (bb_info->out, DF_REF_ID (adef)))
+       continue;

 
 

-  if ((unsigned) max_reg_num () >= max_reg_no)
-    {
-      max_reg_no = max_reg_num () + 100;
-      if (last_def)
-       free (last_def);
-      last_def = xmalloc (max_reg_no * sizeof (rtx));
-      if (bivs)
-       free (bivs);
-      bivs = xmalloc (max_reg_no * sizeof (struct rtx_iv));
-    }
+      /* More than one reaching definition.  */
+      if (single_rd)
+       return false;

 
 

-  memset (last_def, 0, max_reg_num () * sizeof (rtx));
+      if (!just_once_each_iteration_p (current_loop, DF_REF_BB (adef)))
+       return false;

 
 

-  for (b = 0; b < loop->num_nodes; b++)
-    {
-      assign_luids (body[b]);
-      mark_sets (body[b], just_once_each_iteration_p (loop, body[b]));
+      single_rd = adef;

     }
 
     }
 

-  free (body);
+  *def = single_rd;
+  return true;

 }
 
 }
 

-/* Gets definition of REG reaching the INSN.  If REG is not simple, const0_rtx
-   is returned.  If INSN is before the first def in the loop, NULL_RTX is
-   returned.  */
+/* Gets definition of REG reaching its use in INSN and stores it to DEF.  */

 
 

-rtx
-iv_get_reaching_def (rtx insn, rtx reg)
+static enum iv_grd_result
+iv_get_reaching_def (rtx insn, rtx reg, df_ref *def)

 {
 {

-  unsigned regno, luid, auid;
-  rtx ainsn;
-  basic_block bb, abb;
+  df_ref use, adef;
+  basic_block def_bb, use_bb;
+  rtx def_insn;
+  bool dom_p;

 
 

+  *def = NULL;
+  if (!simple_reg_p (reg))
+    return GRD_INVALID;

   if (GET_CODE (reg) == SUBREG)
   if (GET_CODE (reg) == SUBREG)

-    {
-      if (!subreg_lowpart_p (reg))
-       return const0_rtx;
-      reg = SUBREG_REG (reg);
-    }
-  if (!REG_P (reg))
-    return NULL_RTX;
+    reg = SUBREG_REG (reg);
+  gcc_assert (REG_P (reg));

 
 

-  regno = REGNO (reg);
-  if (!last_def[regno]
-      || last_def[regno] == const0_rtx)
-    return last_def[regno];
+  use = df_find_use (insn, reg);
+  gcc_assert (use != NULL);

 
 

-  bb = BLOCK_FOR_INSN (insn);
-  luid = insn_info[INSN_UID (insn)].luid;
+  if (!DF_REF_CHAIN (use))
+    return GRD_INVARIANT;

 
 

-  ainsn = last_def[regno];
-  while (1)
-    {
-      abb = BLOCK_FOR_INSN (ainsn);
+  /* More than one reaching def.  */
+  if (DF_REF_CHAIN (use)->next)
+    return GRD_INVALID;

 
 

-      if (dominated_by_p (CDI_DOMINATORS, bb, abb))
-       break;
+  adef = DF_REF_CHAIN (use)->ref;

 
 

-      auid = INSN_UID (ainsn);
-      ainsn = insn_info[auid].prev_def;
+  /* We do not handle setting only part of the register.  */
+  if (DF_REF_FLAGS (adef) & DF_REF_READ_WRITE)
+    return GRD_INVALID;

 
 

-      if (!ainsn)
-       return NULL_RTX;
-    }
+  def_insn = DF_REF_INSN (adef);
+  def_bb = DF_REF_BB (adef);
+  use_bb = BLOCK_FOR_INSN (insn);

 
 

-  while (1)
+  if (use_bb == def_bb)
+    dom_p = (DF_INSN_LUID (def_insn) < DF_INSN_LUID (insn));
+  else
+    dom_p = dominated_by_p (CDI_DOMINATORS, use_bb, def_bb);
+
+  if (dom_p)

     {
     {

-      abb = BLOCK_FOR_INSN (ainsn);
-      if (abb != bb)
-       return ainsn;
+      *def = adef;
+      return GRD_SINGLE_DOM;
+    }

 
 

-      auid = INSN_UID (ainsn);
-      if (luid > insn_info[auid].luid)
-       return ainsn;
+  /* The definition does not dominate the use.  This is still OK if
+     this may be a use of a biv, i.e. if the def_bb dominates loop
+     latch.  */
+  if (just_once_each_iteration_p (current_loop, def_bb))
+    return GRD_MAYBE_BIV;

 
 

-      ainsn = insn_info[auid].prev_def;
-      if (!ainsn)
-       return NULL_RTX;
-    }
+  return GRD_INVALID;

 }
 
 /* Sets IV to invariant CST in MODE.  Always returns true (just for
 }
 
 /* Sets IV to invariant CST in MODE.  Always returns true (just for


@@ -422,7 +387,6 @@ iv_constant (struct rtx_iv *iv, rtx cst, enum machine_mode mode)
   if (mode == VOIDmode)
     mode = GET_MODE (cst);
 
   if (mode == VOIDmode)
     mode = GET_MODE (cst);
 

-  iv->analysed = true;

   iv->mode = mode;
   iv->base = cst;
   iv->step = const0_rtx;
   iv->mode = mode;
   iv->base = cst;
   iv->step = const0_rtx;


@@ -650,26 +614,31 @@ iv_shift (struct rtx_iv *iv, rtx mby)
 }
 
 /* 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 in INSN wrto initial value of REG inside loop, in shape described
+   defined by DEF wrto initial value of REG inside loop, in shape described

    at get_biv_step.  */
 
 static bool
    at get_biv_step.  */
 
 static bool

-get_biv_step_1 (rtx insn, rtx reg,
+get_biv_step_1 (df_ref def, rtx reg,

                rtx *inner_step, enum machine_mode *inner_mode,
                enum rtx_code *extend, enum machine_mode outer_mode,
                rtx *outer_step)
 {
                rtx *inner_step, enum machine_mode *inner_mode,
                enum rtx_code *extend, enum machine_mode outer_mode,
                rtx *outer_step)
 {

-  rtx set, lhs, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
-  rtx next, nextr, def_insn, tmp;
+  rtx set, rhs, op0 = NULL_RTX, op1 = NULL_RTX;
+  rtx next, nextr, tmp;

   enum rtx_code code;
   enum rtx_code code;

+  rtx insn = DF_REF_INSN (def);
+  df_ref next_def;
+  enum iv_grd_result res;

 
   set = single_set (insn);
 
   set = single_set (insn);

+  if (!set)
+    return false;
+

   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)
     rhs = XEXP (rhs, 0);
   else
     rhs = SET_SRC (set);
   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)
     rhs = XEXP (rhs, 0);
   else
     rhs = SET_SRC (set);

-  lhs = SET_DEST (set);

 
   code = GET_CODE (rhs);
   switch (code)
 
   code = GET_CODE (rhs);
   switch (code)


@@ -740,11 +709,12 @@ get_biv_step_1 (rtx insn, rtx reg,
   else
     nextr = next;
 
   else
     nextr = next;
 

-  def_insn = iv_get_reaching_def (insn, nextr);
-  if (def_insn == const0_rtx)
+  res = iv_get_reaching_def (insn, nextr, &next_def);
+
+  if (res == GRD_INVALID || res == GRD_INVARIANT)

     return false;
 
     return false;
 

-  if (!def_insn)
+  if (res == GRD_MAYBE_BIV)

     {
       if (!rtx_equal_p (nextr, reg))
        return false;
     {
       if (!rtx_equal_p (nextr, reg))
        return false;


@@ -754,7 +724,7 @@ get_biv_step_1 (rtx insn, rtx reg,
       *inner_mode = outer_mode;
       *outer_step = const0_rtx;
     }
       *inner_mode = outer_mode;
       *outer_step = const0_rtx;
     }

-  else if (!get_biv_step_1 (def_insn, reg,
+  else if (!get_biv_step_1 (next_def, reg,

                            inner_step, inner_mode, extend, outer_mode,
                            outer_step))
     return false;
                            inner_step, inner_mode, extend, outer_mode,
                            outer_step))
     return false;


@@ -793,16 +763,15 @@ get_biv_step_1 (rtx insn, rtx reg,
 
     case SIGN_EXTEND:
     case ZERO_EXTEND:
 
     case SIGN_EXTEND:
     case ZERO_EXTEND:

-      if (GET_MODE (op0) != *inner_mode
-         || *extend != UNKNOWN
-         || *outer_step != const0_rtx)
-       abort ();
+      gcc_assert (GET_MODE (op0) == *inner_mode
+                 && *extend == UNKNOWN
+                 && *outer_step == const0_rtx);

 
       *extend = code;
       break;
 
     default:
 
       *extend = code;
       break;
 
     default:

-      abort ();
+      return false;

     }
 
   return true;
     }
 
   return true;


@@ -812,53 +781,85 @@ get_biv_step_1 (rtx insn, rtx reg,
 
    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.  */

 
 static bool
 
 static bool

-get_biv_step (rtx reg, rtx *inner_step, enum machine_mode *inner_mode,
-             enum rtx_code *extend, enum machine_mode *outer_mode,
-             rtx *outer_step)
+get_biv_step (df_ref last_def, rtx reg, rtx *inner_step,
+             enum machine_mode *inner_mode, enum rtx_code *extend,
+             enum machine_mode *outer_mode, rtx *outer_step)

 {
   *outer_mode = GET_MODE (reg);
 
 {
   *outer_mode = GET_MODE (reg);
 

-  if (!get_biv_step_1 (last_def[REGNO (reg)], reg,
+  if (!get_biv_step_1 (last_def, reg,

                       inner_step, inner_mode, extend, *outer_mode,
                       outer_step))
     return false;
 
                       inner_step, inner_mode, extend, *outer_mode,
                       outer_step))
     return false;
 

-  if (*inner_mode != *outer_mode
-      && *extend == UNKNOWN)
-    abort ();
+  gcc_assert ((*inner_mode == *outer_mode) != (*extend != UNKNOWN));
+  gcc_assert (*inner_mode != *outer_mode || *outer_step == const0_rtx);
+
+  return true;
+}
+
+/* Records information that DEF is induction variable IV.  */
+
+static void
+record_iv (df_ref def, struct rtx_iv *iv)
+{
+  struct rtx_iv *recorded_iv = XNEW (struct rtx_iv);
+
+  *recorded_iv = *iv;
+  check_iv_ref_table_size ();
+  DF_REF_IV_SET (def, recorded_iv);
+}

 
 

-  if (*inner_mode == *outer_mode
-      && *extend != UNKNOWN)
-    abort ();
+/* If DEF was already analyzed for bivness, store the description of the biv to
+   IV and return true.  Otherwise return false.  */
+
+static bool
+analyzed_for_bivness_p (rtx def, struct rtx_iv *iv)
+{
+  struct biv_entry *biv =
+    (struct biv_entry *) htab_find_with_hash (bivs, def, REGNO (def));

 
 

-  if (*inner_mode == *outer_mode
-      && *outer_step != const0_rtx)
-    abort ();
+  if (!biv)
+    return false;

 
 

+  *iv = biv->iv;

   return true;
 }
 
   return true;
 }
 

+static void
+record_biv (rtx def, struct rtx_iv *iv)
+{
+  struct biv_entry *biv = XNEW (struct biv_entry);
+  void **slot = htab_find_slot_with_hash (bivs, def, REGNO (def), INSERT);
+
+  biv->regno = REGNO (def);
+  biv->iv = *iv;
+  gcc_assert (!*slot);
+  *slot = biv;
+}
+

 /* Determines whether DEF is a biv and if so, stores its description
    to *IV.  */
 
 static bool
 iv_analyze_biv (rtx def, struct rtx_iv *iv)
 {
 /* Determines whether DEF is a biv and if so, stores its description
    to *IV.  */
 
 static bool
 iv_analyze_biv (rtx def, struct rtx_iv *iv)
 {

-  unsigned regno;

   rtx inner_step, outer_step;
   enum machine_mode inner_mode, outer_mode;
   enum rtx_code extend;
   rtx inner_step, outer_step;
   enum machine_mode inner_mode, outer_mode;
   enum rtx_code extend;

+  df_ref last_def;

 
   if (dump_file)
     {
 
   if (dump_file)
     {

-      fprintf (dump_file, "Analysing ");
+      fprintf (dump_file, "Analyzing ");

       print_rtl (dump_file, def);
       fprintf (dump_file, " for bivness.\n");
     }
       print_rtl (dump_file, def);
       fprintf (dump_file, " for bivness.\n");
     }

-    
+

   if (!REG_P (def))
     {
       if (!CONSTANT_P (def))
   if (!REG_P (def))
     {
       if (!CONSTANT_P (def))


@@ -867,31 +868,24 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
       return iv_constant (iv, def, VOIDmode);
     }
 
       return iv_constant (iv, def, VOIDmode);
     }
 

-  regno = REGNO (def);
-  if (last_def[regno] == const0_rtx)
+  if (!latch_dominating_def (def, &last_def))

     {
       if (dump_file)
        fprintf (dump_file, "  not simple.\n");
       return false;
     }
 
     {
       if (dump_file)
        fprintf (dump_file, "  not simple.\n");
       return false;
     }
 

-  if (last_def[regno] && bivs[regno].analysed)
+  if (!last_def)
+    return iv_constant (iv, def, VOIDmode);
+
+  if (analyzed_for_bivness_p (def, iv))

     {
       if (dump_file)
        fprintf (dump_file, "  already analysed.\n");
     {
       if (dump_file)
        fprintf (dump_file, "  already analysed.\n");

-
-      *iv = bivs[regno];

       return iv->base != NULL_RTX;
     }
 
       return iv->base != NULL_RTX;
     }
 

-  if (!last_def[regno])
-    {
-      iv_constant (iv, def, VOIDmode);
-      goto end;
-    }
-
-  iv->analysed = true;
-  if (!get_biv_step (def, &inner_step, &inner_mode, &extend,
+  if (!get_biv_step (last_def, def, &inner_step, &inner_mode, &extend,

                     &outer_mode, &outer_step))
     {
       iv->base = NULL_RTX;
                     &outer_mode, &outer_step))
     {
       iv->base = NULL_RTX;


@@ -921,119 +915,155 @@ iv_analyze_biv (rtx def, struct rtx_iv *iv)
       fprintf (dump_file, "\n");
     }
 
       fprintf (dump_file, "\n");
     }
 

-  bivs[regno] = *iv;
-
+  record_biv (def, iv);

   return iv->base != NULL_RTX;
 }
 
   return iv->base != NULL_RTX;
 }
 

-/* Analyzes operand OP of INSN and stores the result to *IV.  */
+/* Analyzes expression RHS used at INSN and stores the result to *IV.
+   The mode of the induction variable is MODE.  */

 
 

-static bool
-iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
+bool
+iv_analyze_expr (rtx insn, rtx rhs, enum machine_mode mode, struct rtx_iv *iv)

 {
 {

-  rtx def_insn;
-  unsigned regno;
-  bool inv = CONSTANT_P (op);
+  rtx mby = NULL_RTX, tmp;
+  rtx op0 = NULL_RTX, op1 = NULL_RTX;
+  struct rtx_iv iv0, iv1;
+  enum rtx_code code = GET_CODE (rhs);
+  enum machine_mode omode = mode;

 
 

-  if (dump_file)
-    {
-      fprintf (dump_file, "Analysing operand ");
-      print_rtl (dump_file, op);
-      fprintf (dump_file, " of insn ");
-      print_rtl_single (dump_file, insn);
-    }
+  iv->mode = VOIDmode;
+  iv->base = NULL_RTX;
+  iv->step = NULL_RTX;

 
 

-  if (GET_CODE (op) == SUBREG)
-    {
-      if (!subreg_lowpart_p (op))
-       return false;
+  gcc_assert (GET_MODE (rhs) == mode || GET_MODE (rhs) == VOIDmode);

 
 

-      if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
+  if (CONSTANT_P (rhs)
+      || REG_P (rhs)
+      || code == SUBREG)
+    {
+      if (!iv_analyze_op (insn, rhs, iv))

        return false;
 
        return false;
 

-      return iv_subreg (iv, GET_MODE (op));
-    }
-
-  if (!inv)
-    {
-      regno = REGNO (op);
-      if (!last_def[regno])
-       inv = true;
-      else if (last_def[regno] == const0_rtx)
+      if (iv->mode == VOIDmode)

        {
        {

-         if (dump_file)
-           fprintf (dump_file, "  not simple.\n");
-         return false;
+         iv->mode = mode;
+         iv->extend_mode = mode;

        }
        }

+
+      return true;

     }
 
     }
 

-  if (inv)
+  switch (code)

     {
     {

-      iv_constant (iv, op, VOIDmode);
+    case REG:
+      op0 = rhs;
+      break;

 
 

-      if (dump_file)
+    case SIGN_EXTEND:
+    case ZERO_EXTEND:
+    case NEG:
+      op0 = XEXP (rhs, 0);
+      omode = GET_MODE (op0);
+      break;
+
+    case PLUS:
+    case MINUS:
+      op0 = XEXP (rhs, 0);
+      op1 = XEXP (rhs, 1);
+      break;
+
+    case MULT:
+      op0 = XEXP (rhs, 0);
+      mby = XEXP (rhs, 1);
+      if (!CONSTANT_P (mby))

        {
        {

-         fprintf (dump_file, "  ");
-         dump_iv_info (dump_file, iv);
-         fprintf (dump_file, "\n");
+         tmp = op0;
+         op0 = mby;
+         mby = tmp;

        }
        }

-      return true;
-    }
+      if (!CONSTANT_P (mby))
+       return false;
+      break;

 
 

-  def_insn = iv_get_reaching_def (insn, op);
-  if (def_insn == const0_rtx)
-    {
-      if (dump_file)
-       fprintf (dump_file, "  not simple.\n");
+    case ASHIFT:
+      op0 = XEXP (rhs, 0);
+      mby = XEXP (rhs, 1);
+      if (!CONSTANT_P (mby))
+       return false;
+      break;
+
+    default:

       return false;
     }
 
       return false;
     }
 

-  return iv_analyze (def_insn, op, iv);
-}
-
-/* Analyzes iv DEF defined in INSN and stores the result to *IV.  */
-
-bool
-iv_analyze (rtx insn, rtx def, struct rtx_iv *iv)
-{
-  unsigned uid;
-  rtx set, rhs, mby = NULL_RTX, tmp;
-  rtx op0 = NULL_RTX, op1 = NULL_RTX;
-  struct rtx_iv iv0, iv1;
-  enum machine_mode amode;
-  enum rtx_code code;
+  if (op0
+      && !iv_analyze_expr (insn, op0, omode, &iv0))
+    return false;

 
 

-  if (insn == const0_rtx)
+  if (op1
+      && !iv_analyze_expr (insn, op1, omode, &iv1))

     return false;
 
     return false;
 

-  if (GET_CODE (def) == SUBREG)
+  switch (code)

     {
     {

-      if (!subreg_lowpart_p (def))
+    case SIGN_EXTEND:
+    case ZERO_EXTEND:
+      if (!iv_extend (&iv0, code, mode))
+       return false;
+      break;
+
+    case NEG:
+      if (!iv_neg (&iv0))

        return false;
        return false;

+      break;
+
+    case PLUS:
+    case MINUS:
+      if (!iv_add (&iv0, &iv1, code))
+       return false;
+      break;

 
 

-      if (!iv_analyze (insn, SUBREG_REG (def), iv))
+    case MULT:
+      if (!iv_mult (&iv0, mby))

        return false;
        return false;

+      break;

 
 

-      return iv_subreg (iv, GET_MODE (def));
+    case ASHIFT:
+      if (!iv_shift (&iv0, mby))
+       return false;
+      break;
+
+    default:
+      break;

     }
 
     }
 

-  if (!insn)
-    return iv_analyze_biv (def, iv);
+  *iv = iv0;
+  return iv->base != NULL_RTX;
+}
+
+/* Analyzes iv DEF and stores the result to *IV.  */
+
+static bool
+iv_analyze_def (df_ref def, struct rtx_iv *iv)
+{
+  rtx insn = DF_REF_INSN (def);
+  rtx reg = DF_REF_REG (def);
+  rtx set, rhs;

 
   if (dump_file)
     {
 
   if (dump_file)
     {

-      fprintf (dump_file, "Analysing def of ");
-      print_rtl (dump_file, def);
+      fprintf (dump_file, "Analyzing def of ");
+      print_rtl (dump_file, reg);

       fprintf (dump_file, " in insn ");
       print_rtl_single (dump_file, insn);
     }
 
       fprintf (dump_file, " in insn ");
       print_rtl_single (dump_file, insn);
     }
 

-  uid = INSN_UID (insn);
-  if (insn_info[uid].iv.analysed)
+  check_iv_ref_table_size ();
+  if (DF_REF_IV (def))

     {
       if (dump_file)
        fprintf (dump_file, "  already analysed.\n");
     {
       if (dump_file)
        fprintf (dump_file, "  already analysed.\n");

-      *iv = insn_info[uid].iv;
+      *iv = *DF_REF_IV (def);

       return iv->base != NULL_RTX;
     }
 
       return iv->base != NULL_RTX;
     }
 


@@ -1041,149 +1071,137 @@ iv_analyze (rtx insn, rtx def, struct rtx_iv *iv)
   iv->base = NULL_RTX;
   iv->step = NULL_RTX;
 
   iv->base = NULL_RTX;
   iv->step = NULL_RTX;
 

+  if (!REG_P (reg))
+    return false;
+

   set = single_set (insn);
   set = single_set (insn);

+  if (!set)
+    return false;
+
+  if (!REG_P (SET_DEST (set)))
+    return false;
+
+  gcc_assert (SET_DEST (set) == reg);

   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)
     rhs = XEXP (rhs, 0);
   else
     rhs = SET_SRC (set);
   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)
     rhs = XEXP (rhs, 0);
   else
     rhs = SET_SRC (set);

-  code = GET_CODE (rhs);

 
 

-  if (CONSTANT_P (rhs))
+  iv_analyze_expr (insn, rhs, GET_MODE (reg), iv);
+  record_iv (def, iv);
+
+  if (dump_file)

     {
     {

-      op0 = rhs;
-      amode = GET_MODE (def);
+      print_rtl (dump_file, reg);
+      fprintf (dump_file, " in insn ");
+      print_rtl_single (dump_file, insn);
+      fprintf (dump_file, "  is ");
+      dump_iv_info (dump_file, iv);
+      fprintf (dump_file, "\n");

     }
     }

-  else
-    {
-      switch (code)
-       {
-       case SUBREG:
-         if (!subreg_lowpart_p (rhs))
-           goto end;
-         op0 = rhs;
-         break;
-         
-       case REG:
-         op0 = rhs;
-         break;

 
 

-       case SIGN_EXTEND:
-       case ZERO_EXTEND:
-       case NEG:
-         op0 = XEXP (rhs, 0);
-         break;
+  return iv->base != NULL_RTX;
+}

 
 

-       case PLUS:
-       case MINUS:
-         op0 = XEXP (rhs, 0);
-         op1 = XEXP (rhs, 1);
-         break;
+/* Analyzes operand OP of INSN and stores the result to *IV.  */

 
 

-       case MULT:
-         op0 = XEXP (rhs, 0);
-         mby = XEXP (rhs, 1);
-         if (!CONSTANT_P (mby))
-           {
-             if (!CONSTANT_P (op0))
-               abort ();
-             tmp = op0;
-             op0 = mby;
-             mby = tmp;
-           }
-         break;
+static bool
+iv_analyze_op (rtx insn, rtx op, struct rtx_iv *iv)
+{
+  df_ref def = NULL;
+  enum iv_grd_result res;

 
 

-       case ASHIFT:
-         if (CONSTANT_P (XEXP (rhs, 0)))
-           abort ();
-         op0 = XEXP (rhs, 0);
-         mby = XEXP (rhs, 1);
-         break;
+  if (dump_file)
+    {
+      fprintf (dump_file, "Analyzing operand ");
+      print_rtl (dump_file, op);
+      fprintf (dump_file, " of insn ");
+      print_rtl_single (dump_file, insn);
+    }

 
 

-       default:
-         abort ();
-       }
+  if (function_invariant_p (op))
+    res = GRD_INVARIANT;
+  else if (GET_CODE (op) == SUBREG)
+    {
+      if (!subreg_lowpart_p (op))
+       return false;

 
 

-      amode = GET_MODE (rhs);
-    }
+      if (!iv_analyze_op (insn, SUBREG_REG (op), iv))
+       return false;

 
 

-  if (op0)
+      return iv_subreg (iv, GET_MODE (op));
+    }
+  else

     {
     {

-      if (!iv_analyze_op (insn, op0, &iv0))
-       goto end;
-       
-      if (iv0.mode == VOIDmode)
+      res = iv_get_reaching_def (insn, op, &def);
+      if (res == GRD_INVALID)

        {
        {

-         iv0.mode = amode;
-         iv0.extend_mode = amode;
+         if (dump_file)
+           fprintf (dump_file, "  not simple.\n");
+         return false;

        }
     }
 
        }
     }
 

-  if (op1)
+  if (res == GRD_INVARIANT)

     {
     {

-      if (!iv_analyze_op (insn, op1, &iv1))
-       goto end;
+      iv_constant (iv, op, VOIDmode);

 
 

-      if (iv1.mode == VOIDmode)
+      if (dump_file)

        {
        {

-         iv1.mode = amode;
-         iv1.extend_mode = amode;
+         fprintf (dump_file, "  ");
+         dump_iv_info (dump_file, iv);
+         fprintf (dump_file, "\n");

        }
        }

+      return true;

     }
 
     }
 

-  switch (code)
-    {
-    case SIGN_EXTEND:
-    case ZERO_EXTEND:
-      if (!iv_extend (&iv0, code, amode))
-       goto end;
-      break;
+  if (res == GRD_MAYBE_BIV)
+    return iv_analyze_biv (op, iv);

 
 

-    case NEG:
-      if (!iv_neg (&iv0))
-       goto end;
-      break;
+  return iv_analyze_def (def, iv);
+}

 
 

-    case PLUS:
-    case MINUS:
-      if (!iv_add (&iv0, &iv1, code))
-       goto end;
-      break;
+/* Analyzes value VAL at INSN and stores the result to *IV.  */

 
 

-    case MULT:
-      if (!iv_mult (&iv0, mby))
-       goto end;
-      break;
+bool
+iv_analyze (rtx insn, rtx val, struct rtx_iv *iv)
+{
+  rtx reg;

 
 

-    case ASHIFT:
-      if (!iv_shift (&iv0, mby))
-       goto end;
-      break;
+  /* We must find the insn in that val is used, so that we get to UD chains.
+     Since the function is sometimes called on result of get_condition,
+     this does not necessarily have to be directly INSN; scan also the
+     following insns.  */
+  if (simple_reg_p (val))
+    {
+      if (GET_CODE (val) == SUBREG)
+       reg = SUBREG_REG (val);
+      else
+       reg = val;

 
 

-    default:
-      break;
+      while (!df_find_use (insn, reg))
+       insn = NEXT_INSN (insn);

     }
 
     }
 

-  *iv = iv0;
+  return iv_analyze_op (insn, val, iv);
+}

 
 

- end:
-  iv->analysed = true;
-  insn_info[uid].iv = *iv;
+/* Analyzes definition of DEF in INSN and stores the result to IV.  */

 
 

-  if (dump_file)
-    {
-      print_rtl (dump_file, def);
-      fprintf (dump_file, " in insn ");
-      print_rtl_single (dump_file, insn);
-      fprintf (dump_file, "  is ");
-      dump_iv_info (dump_file, iv);
-      fprintf (dump_file, "\n");
-    }
+bool
+iv_analyze_result (rtx insn, rtx def, struct rtx_iv *iv)
+{
+  df_ref adef;

 
 

-  return iv->base != NULL_RTX;
+  adef = df_find_def (insn, def);
+  if (!adef)
+    return false;
+
+  return iv_analyze_def (adef, iv);

 }
 
 }
 

-/* Checks whether definition of register REG in INSN a basic induction
+/* Checks whether definition of register REG in INSN is a basic induction

    variable.  IV analysis must have been initialized (via a call to
    iv_analysis_loop_init) for this function to produce a result.  */
 
    variable.  IV analysis must have been initialized (via a call to
    iv_analysis_loop_init) for this function to produce a result.  */
 


@@ -1191,14 +1209,22 @@ bool
 biv_p (rtx insn, rtx reg)
 {
   struct rtx_iv iv;
 biv_p (rtx insn, rtx reg)
 {
   struct rtx_iv iv;

+  df_ref def, last_def;

 
 

-  if (!REG_P (reg))
+  if (!simple_reg_p (reg))
+    return false;
+
+  def = df_find_def (insn, reg);
+  gcc_assert (def != NULL);
+  if (!latch_dominating_def (reg, &last_def))
+    return false;
+  if (last_def != def)

     return false;
 
     return false;
 

-  if (last_def[REGNO (reg)] != insn)
+  if (!iv_analyze_biv (reg, &iv))

     return false;
 
     return false;
 

-  return iv_analyze_biv (reg, &iv);
+  return iv.step != const0_rtx;

 }
 
 /* Calculates value of IV at ITERATION-th iteration.  */
 }
 
 /* Calculates value of IV at ITERATION-th iteration.  */


@@ -1210,8 +1236,7 @@ get_iv_value (struct rtx_iv *iv, rtx iteration)
 
   /* We would need to generate some if_then_else patterns, and so far
      it is not needed anywhere.  */
 
   /* We would need to generate some if_then_else patterns, and so far
      it is not needed anywhere.  */

-  if (iv->first_special)
-    abort ();
+  gcc_assert (!iv->first_special);

 
   if (iv->step != const0_rtx && iteration != const0_rtx)
     val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,
 
   if (iv->step != const0_rtx && iteration != const0_rtx)
     val = simplify_gen_binary (PLUS, iv->extend_mode, iv->base,


@@ -1241,107 +1266,36 @@ get_iv_value (struct rtx_iv *iv, rtx iteration)
 void
 iv_analysis_done (void)
 {
 void
 iv_analysis_done (void)
 {

-  max_insn_no = 0;
-  max_reg_no = 0;
-  if (insn_info)
-    {
-      free (insn_info);
-      insn_info = NULL;
-    }
-  if (last_def)
-    {
-      free (last_def);
-      last_def = NULL;
-    }
-  if (bivs)
-    {
-      free (bivs);
+  if (!clean_slate)
+    {
+      clear_iv_info ();
+      clean_slate = true;
+      df_finish_pass (true);
+      htab_delete (bivs);
+      free (iv_ref_table);
+      iv_ref_table = NULL;
+      iv_ref_table_size = 0;

       bivs = NULL;
     }
       bivs = NULL;
     }

-}
-
-/* Computes inverse to X modulo (1 << MOD).  */
-
-static unsigned HOST_WIDEST_INT
-inverse (unsigned HOST_WIDEST_INT x, int mod)
-{
-  unsigned HOST_WIDEST_INT mask =
-         ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
-  unsigned HOST_WIDEST_INT rslt = 1;
-  int i;
-
-  for (i = 0; i < mod - 1; i++)
-    {
-      rslt = (rslt * x) & mask;
-      x = (x * x) & mask;
-    }
-
-  return rslt;
-}
-
-/* Tries to estimate the maximum number of iterations.  */
-
-static unsigned HOST_WIDEST_INT
-determine_max_iter (struct niter_desc *desc)
-{
-  rtx niter = desc->niter_expr;
-  rtx mmin, mmax, left, right;
-  unsigned HOST_WIDEST_INT nmax, inc;
-
-  if (GET_CODE (niter) == AND
-      && GET_CODE (XEXP (niter, 0)) == CONST_INT)
-    {
-      nmax = INTVAL (XEXP (niter, 0));
-      if (!(nmax & (nmax + 1)))
-       {
-         desc->niter_max = nmax;
-         return nmax;
-       }
-    }
-
-  get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
-  nmax = INTVAL (mmax) - INTVAL (mmin);
-
-  if (GET_CODE (niter) == UDIV)
-    {
-      if (GET_CODE (XEXP (niter, 1)) != CONST_INT)
-       {
-         desc->niter_max = nmax;
-         return nmax;
-       }
-      inc = INTVAL (XEXP (niter, 1));
-      niter = XEXP (niter, 0);
-    }
-  else
-    inc = 1;
+}

 
 

-  if (GET_CODE (niter) == PLUS)
-    {
-      left = XEXP (niter, 0);
-      right = XEXP (niter, 0);
+/* Computes inverse to X modulo (1 << MOD).  */

 
 

-      if (GET_CODE (right) == CONST_INT)
-       right = GEN_INT (-INTVAL (right));
-    }
-  else if (GET_CODE (niter) == MINUS)
-    {
-      left = XEXP (niter, 0);
-      right = XEXP (niter, 0);
-    }
-  else
+static unsigned HOST_WIDEST_INT
+inverse (unsigned HOST_WIDEST_INT x, int mod)
+{
+  unsigned HOST_WIDEST_INT mask =
+         ((unsigned HOST_WIDEST_INT) 1 << (mod - 1) << 1) - 1;
+  unsigned HOST_WIDEST_INT rslt = 1;
+  int i;
+
+  for (i = 0; i < mod - 1; i++)

     {
     {

-      left = niter;
-      right = mmin;
+      rslt = (rslt * x) & mask;
+      x = (x * x) & mask;

     }
 
     }
 

-  if (GET_CODE (left) == CONST_INT)
-    mmax = left;
-  if (GET_CODE (right) == CONST_INT)
-    mmin = right;
-  nmax = INTVAL (mmax) - INTVAL (mmin);
-
-  desc->niter_max = nmax / inc;
-  return nmax / inc;
+  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.  */


@@ -1352,20 +1306,20 @@ altered_reg_used (rtx *reg, void *alt)
   if (!REG_P (*reg))
     return 0;
 
   if (!REG_P (*reg))
     return 0;
 

-  return REGNO_REG_SET_P (alt, REGNO (*reg));
+  return REGNO_REG_SET_P ((bitmap) alt, REGNO (*reg));

 }
 
 /* Marks registers altered by EXPR in set ALT.  */
 
 static void
 }
 
 /* Marks registers altered by EXPR in set ALT.  */
 
 static void

-mark_altered (rtx expr, rtx by ATTRIBUTE_UNUSED, void *alt)
+mark_altered (rtx expr, const_rtx by ATTRIBUTE_UNUSED, void *alt)

 {
   if (GET_CODE (expr) == SUBREG)
     expr = SUBREG_REG (expr);
   if (!REG_P (expr))
     return;
 
 {
   if (GET_CODE (expr) == SUBREG)
     expr = SUBREG_REG (expr);
   if (!REG_P (expr))
     return;
 

-  SET_REGNO_REG_SET (alt, REGNO (expr));
+  SET_REGNO_REG_SET ((bitmap) alt, REGNO (expr));

 }
 
 /* Checks whether RHS is simple enough to process.  */
 }
 
 /* Checks whether RHS is simple enough to process.  */


@@ -1375,62 +1329,114 @@ simple_rhs_p (rtx rhs)
 {
   rtx op0, op1;
 
 {
   rtx op0, op1;
 

-  if (CONSTANT_P (rhs)
-      || REG_P (rhs))
+  if (function_invariant_p (rhs)
+      || (REG_P (rhs) && !HARD_REGISTER_P (rhs)))

     return true;
 
   switch (GET_CODE (rhs))
     {
     case PLUS:
     case MINUS:
     return true;
 
   switch (GET_CODE (rhs))
     {
     case PLUS:
     case MINUS:

+    case AND:

       op0 = XEXP (rhs, 0);
       op1 = XEXP (rhs, 1);
       op0 = XEXP (rhs, 0);
       op1 = XEXP (rhs, 1);

-      /* Allow reg + const sets only.  */
-      if (REG_P (op0) && CONSTANT_P (op1))
-       return true;
-      if (REG_P (op1) && CONSTANT_P (op0))
-       return true;
+      /* Allow reg OP const and reg OP reg.  */
+      if (!(REG_P (op0) && !HARD_REGISTER_P (op0))
+         && !function_invariant_p (op0))
+       return false;
+      if (!(REG_P (op1) && !HARD_REGISTER_P (op1))
+         && !function_invariant_p (op1))
+       return false;

 
 

-      return false;
+      return true;
+
+    case ASHIFT:
+    case ASHIFTRT:
+    case LSHIFTRT:
+    case MULT:
+      op0 = XEXP (rhs, 0);
+      op1 = XEXP (rhs, 1);
+      /* Allow reg OP const.  */
+      if (!(REG_P (op0) && !HARD_REGISTER_P (op0)))
+       return false;
+      if (!function_invariant_p (op1))
+       return false;
+
+      return true;

 
     default:
       return false;
     }
 }
 
 
     default:
       return false;
     }
 }
 

-/* Simplifies *EXPR using assignment in INSN.  ALTERED is the set of registers
-   altered so far.  */
+/* If REG has a single definition, replace it with its known value in EXPR.
+   Callback for for_each_rtx.  */

 
 

-static void
-simplify_using_assignment (rtx insn, rtx *expr, regset altered)
+static int
+replace_single_def_regs (rtx *reg, void *expr1)

 {
 {

-  rtx set = single_set (insn);
-  rtx lhs = NULL_RTX, rhs;
-  bool ret = false;
+  unsigned regno;
+  df_ref adef;
+  rtx set, src;
+  rtx *expr = (rtx *)expr1;

 
 

-  if (set)
-    {
-      lhs = SET_DEST (set);
-      if (!REG_P (lhs)
-         || altered_reg_used (&lhs, altered))
-       ret = true;
-    }
-  else
-    ret = true;
+  if (!REG_P (*reg))
+    return 0;

 
 

-  note_stores (PATTERN (insn), mark_altered, altered);
-  if (CALL_P (insn))
+  regno = REGNO (*reg);
+  for (;;)

     {
     {

-      int i;
+      rtx note;
+      adef = DF_REG_DEF_CHAIN (regno);
+      if (adef == NULL || DF_REF_NEXT_REG (adef) != NULL
+           || DF_REF_IS_ARTIFICIAL (adef))
+       return -1;
+
+      set = single_set (DF_REF_INSN (adef));
+      if (set == NULL || !REG_P (SET_DEST (set))
+         || REGNO (SET_DEST (set)) != regno)
+       return -1;
+
+      note = find_reg_equal_equiv_note (DF_REF_INSN (adef));
+
+      if (note && function_invariant_p (XEXP (note, 0)))
+       {
+         src = XEXP (note, 0);
+         break;
+       }
+      src = SET_SRC (set);

 
 

-      /* Kill all call clobbered registers.  */
-      for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
-       if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
-         SET_REGNO_REG_SET (altered, i);
+      if (REG_P (src))
+       {
+         regno = REGNO (src);
+         continue;
+       }
+      break;

     }
     }

+  if (!function_invariant_p (src))
+    return -1;

 
 

-  if (ret)
-    return;
+  *expr = simplify_replace_rtx (*expr, *reg, src);
+  return 1;
+}
+
+/* A subroutine of simplify_using_initial_values, this function examines INSN
+   to see if it contains a suitable set that we can use to make a replacement.
+   If it is suitable, return true and set DEST and SRC to the lhs and rhs of
+   the set; return false otherwise.  */
+
+static bool
+suitable_set_for_replacement (rtx insn, rtx *dest, rtx *src)
+{
+  rtx set = single_set (insn);
+  rtx lhs = NULL_RTX, rhs;
+
+  if (!set)
+    return false;
+
+  lhs = SET_DEST (set);
+  if (!REG_P (lhs))
+    return false;

 
   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)
 
   rhs = find_reg_equal_equiv_note (insn);
   if (rhs)


@@ -1439,12 +1445,25 @@ simplify_using_assignment (rtx insn, rtx *expr, regset altered)
     rhs = SET_SRC (set);
 
   if (!simple_rhs_p (rhs))
     rhs = SET_SRC (set);
 
   if (!simple_rhs_p (rhs))

-    return;
+    return false;

 
 

-  if (for_each_rtx (&rhs, altered_reg_used, altered))
-    return;
+  *dest = lhs;
+  *src = rhs;
+  return true;
+}

 
 

-  *expr = simplify_replace_rtx (*expr, lhs, rhs);
+/* Using the data returned by suitable_set_for_replacement, replace DEST
+   with SRC in *EXPR and return the new expression.  Also call
+   replace_single_def_regs if the replacement changed something.  */
+static void
+replace_in_expr (rtx *expr, rtx dest, rtx src)
+{
+  rtx old = *expr;
+  *expr = simplify_replace_rtx (*expr, dest, src);
+  if (old == *expr)
+    return;
+  while (for_each_rtx (expr, replace_single_def_regs, expr) != 0)
+    continue;

 }
 
 /* Checks whether A implies B.  */
 }
 
 /* Checks whether A implies B.  */


@@ -1475,14 +1494,34 @@ implies_p (rtx a, rtx b)
        }
     }
 
        }
     }
 

+  if (b == const_true_rtx)
+    return true;
+
+  if ((GET_RTX_CLASS (GET_CODE (a)) != RTX_COMM_COMPARE
+       && GET_RTX_CLASS (GET_CODE (a)) != RTX_COMPARE)
+      || (GET_RTX_CLASS (GET_CODE (b)) != RTX_COMM_COMPARE
+         && GET_RTX_CLASS (GET_CODE (b)) != RTX_COMPARE))
+    return false;
+
+  op0 = XEXP (a, 0);
+  op1 = XEXP (a, 1);
+  opb0 = XEXP (b, 0);
+  opb1 = XEXP (b, 1);
+
+  mode = GET_MODE (op0);
+  if (mode != GET_MODE (opb0))
+    mode = VOIDmode;
+  else if (mode == VOIDmode)
+    {
+      mode = GET_MODE (op1);
+      if (mode != GET_MODE (opb1))
+       mode = VOIDmode;
+    }
+

   /* A < B implies A + 1 <= B.  */
   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
     {
   /* A < B implies A + 1 <= B.  */
   if ((GET_CODE (a) == GT || GET_CODE (a) == LT)
       && (GET_CODE (b) == GE || GET_CODE (b) == LE))
     {

-      op0 = XEXP (a, 0);
-      op1 = XEXP (a, 1);
-      opb0 = XEXP (b, 0);
-      opb1 = XEXP (b, 1);

 
       if (GET_CODE (a) == GT)
        {
 
       if (GET_CODE (a) == GT)
        {


@@ -1498,22 +1537,83 @@ implies_p (rtx a, rtx b)
          opb1 = r;
        }
 
          opb1 = r;
        }
 

-      mode = GET_MODE (op0);
-      if (mode != GET_MODE (opb0))
-       mode = VOIDmode;
-      else if (mode == VOIDmode)
-       {
-         mode = GET_MODE (op1);
-         if (mode != GET_MODE (opb1))
-           mode = VOIDmode;
-       }
-
-      if (mode != VOIDmode
+      if (SCALAR_INT_MODE_P (mode)

          && rtx_equal_p (op1, opb1)
          && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
        return true;
          && rtx_equal_p (op1, opb1)
          && simplify_gen_binary (MINUS, mode, opb0, op0) == const1_rtx)
        return true;

+      return false;
+    }
+
+  /* A < B or A > B imply A != B.  TODO: Likewise
+     A + n < B implies A != B + n if neither wraps.  */
+  if (GET_CODE (b) == NE
+      && (GET_CODE (a) == GT || GET_CODE (a) == GTU
+         || GET_CODE (a) == LT || GET_CODE (a) == LTU))
+    {
+      if (rtx_equal_p (op0, opb0)
+         && rtx_equal_p (op1, opb1))
+       return true;

     }
 
     }
 

+  /* For unsigned comparisons, A != 0 implies A > 0 and A >= 1.  */
+  if (GET_CODE (a) == NE
+      && op1 == const0_rtx)
+    {
+      if ((GET_CODE (b) == GTU
+          && opb1 == const0_rtx)
+         || (GET_CODE (b) == GEU
+             && opb1 == const1_rtx))
+       return rtx_equal_p (op0, opb0);
+    }
+
+  /* A != N is equivalent to A - (N + 1) <u -1.  */
+  if (GET_CODE (a) == NE
+      && CONST_INT_P (op1)
+      && GET_CODE (b) == LTU
+      && opb1 == constm1_rtx
+      && GET_CODE (opb0) == PLUS
+      && CONST_INT_P (XEXP (opb0, 1))
+      /* Avoid overflows.  */
+      && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+         != ((unsigned HOST_WIDE_INT)1
+             << (HOST_BITS_PER_WIDE_INT - 1)) - 1)
+      && INTVAL (XEXP (opb0, 1)) + 1 == -INTVAL (op1))
+    return rtx_equal_p (op0, XEXP (opb0, 0));
+
+  /* Likewise, A != N implies A - N > 0.  */
+  if (GET_CODE (a) == NE
+      && CONST_INT_P (op1))
+    {
+      if (GET_CODE (b) == GTU
+         && GET_CODE (opb0) == PLUS
+         && opb1 == const0_rtx
+         && CONST_INT_P (XEXP (opb0, 1))
+         /* Avoid overflows.  */
+         && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+             != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+         && rtx_equal_p (XEXP (opb0, 0), op0))
+       return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
+      if (GET_CODE (b) == GEU
+         && GET_CODE (opb0) == PLUS
+         && opb1 == const1_rtx
+         && CONST_INT_P (XEXP (opb0, 1))
+         /* Avoid overflows.  */
+         && ((unsigned HOST_WIDE_INT) INTVAL (XEXP (opb0, 1))
+             != ((unsigned HOST_WIDE_INT) 1 << (HOST_BITS_PER_WIDE_INT - 1)))
+         && rtx_equal_p (XEXP (opb0, 0), op0))
+       return INTVAL (op1) == -INTVAL (XEXP (opb0, 1));
+    }
+
+  /* A >s X, where X is positive, implies A <u Y, if Y is negative.  */
+  if ((GET_CODE (a) == GT || GET_CODE (a) == GE)
+      && CONST_INT_P (op1)
+      && ((GET_CODE (a) == GT && op1 == constm1_rtx)
+         || INTVAL (op1) >= 0)
+      && GET_CODE (b) == LTU
+      && CONST_INT_P (opb1)
+      && rtx_equal_p (op0, opb0))
+    return INTVAL (opb1) < 0;
+

   return false;
 }
 
   return false;
 }
 


@@ -1547,10 +1647,9 @@ canon_condition (rtx cond)
   mode = GET_MODE (op0);
   if (mode == VOIDmode)
     mode = GET_MODE (op1);
   mode = GET_MODE (op0);
   if (mode == VOIDmode)
     mode = GET_MODE (op1);

-  if (mode == VOIDmode)
-    abort ();
+  gcc_assert (mode != VOIDmode);

 
 

-  if (GET_CODE (op1) == CONST_INT
+  if (CONST_INT_P (op1)

       && GET_MODE_CLASS (mode) != MODE_CC
       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
     {
       && GET_MODE_CLASS (mode) != MODE_CC
       && GET_MODE_BITSIZE (mode) <= HOST_BITS_PER_WIDE_INT)
     {


@@ -1607,15 +1706,22 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
 {
   rtx rev, reve, exp = *expr;
 
 {
   rtx rev, reve, exp = *expr;
 

-  if (!COMPARISON_P (exp))
-    return;
-

   /* If some register gets altered later, we do not really speak about its
      value at the time of comparison.  */
   if (altered
       && for_each_rtx (&cond, altered_reg_used, altered))
     return;
 
   /* If some register gets altered later, we do not really speak about its
      value at the time of comparison.  */
   if (altered
       && for_each_rtx (&cond, altered_reg_used, altered))
     return;
 

+  if (GET_CODE (cond) == EQ
+      && REG_P (XEXP (cond, 0)) && CONSTANT_P (XEXP (cond, 1)))
+    {
+      *expr = simplify_replace_rtx (*expr, XEXP (cond, 0), XEXP (cond, 1));
+      return;
+    }
+
+  if (!COMPARISON_P (exp))
+    return;
+

   rev = reversed_condition (cond);
   reve = reversed_condition (exp);
 
   rev = reversed_condition (cond);
   reve = reversed_condition (exp);
 


@@ -1632,7 +1738,6 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
       return;
     }
 
       return;
     }
 

-

   if (rev && rtx_equal_p (exp, rev))
     {
       *expr = const0_rtx;
   if (rev && rtx_equal_p (exp, rev))
     {
       *expr = const0_rtx;


@@ -1644,7 +1749,7 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
       *expr = const_true_rtx;
       return;
     }
       *expr = const_true_rtx;
       return;
     }

-  
+

   if (reve && implies_p (cond, reve))
     {
       *expr = const0_rtx;
   if (reve && implies_p (cond, reve))
     {
       *expr = const0_rtx;


@@ -1677,20 +1782,23 @@ simplify_using_condition (rtx cond, rtx *expr, regset altered)
 static void
 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
 {
 static void
 eliminate_implied_condition (enum rtx_code op, rtx a, rtx *b)
 {

-  if (op == AND)
+  switch (op)

     {
     {

+    case AND:

       /* If A implies *B, we may replace *B by true.  */
       if (implies_p (a, *b))
        *b = const_true_rtx;
       /* If A implies *B, we may replace *B by true.  */
       if (implies_p (a, *b))
        *b = const_true_rtx;

-    }
-  else if (op == IOR)
-    {
+      break;
+
+    case IOR:

       /* If *B implies A, we may replace *B by false.  */
       if (implies_p (*b, a))
        *b = const0_rtx;
       /* If *B implies A, we may replace *B by false.  */
       if (implies_p (*b, a))
        *b = const0_rtx;

+      break;
+
+    default:
+      gcc_unreachable ();

     }
     }

-  else
-    abort ();

 }
 
 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the
 }
 
 /* Eliminates the conditions in TAIL that are implied by HEAD.  OP is the


@@ -1713,10 +1821,10 @@ eliminate_implied_conditions (enum rtx_code op, rtx *head, rtx tail)
 static void
 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
 {
 static void
 simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
 {

-  rtx head, tail, insn;
+  bool expression_valid;
+  rtx head, tail, insn, cond_list, last_valid_expr;

   rtx neutral, aggr;
   rtx neutral, aggr;

-  regset altered;
-  regset_head altered_head;
+  regset altered, this_altered;

   edge e;
 
   if (!*expr)
   edge e;
 
   if (!*expr)


@@ -1732,18 +1840,21 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
 
       eliminate_implied_conditions (op, &head, tail);
 
 
       eliminate_implied_conditions (op, &head, tail);
 

-      if (op == AND)
+      switch (op)

        {
        {

+       case AND:

          neutral = const_true_rtx;
          aggr = const0_rtx;
          neutral = const_true_rtx;
          aggr = const0_rtx;

-       }
-      else if (op == IOR)
-       {
+         break;
+
+       case IOR:

          neutral = const0_rtx;
          aggr = const_true_rtx;
          neutral = const0_rtx;
          aggr = const_true_rtx;

+         break;
+
+       default:
+         gcc_unreachable ();

        }
        }

-      else
-       abort ();

 
       simplify_using_initial_values (loop, UNKNOWN, &head);
       if (head == aggr)
 
       simplify_using_initial_values (loop, UNKNOWN, &head);
       if (head == aggr)


@@ -1765,67 +1876,144 @@ simplify_using_initial_values (struct loop *loop, enum rtx_code op, rtx *expr)
          *expr = tail;
          return;
        }
          *expr = tail;
          return;
        }

-  
+

       XEXP (*expr, 0) = head;
       XEXP (*expr, 1) = tail;
       return;
     }
 
       XEXP (*expr, 0) = head;
       XEXP (*expr, 1) = tail;
       return;
     }
 

-  if (op != UNKNOWN)
-    abort ();
+  gcc_assert (op == UNKNOWN);
+
+  for (;;)
+    if (for_each_rtx (expr, replace_single_def_regs, expr) == 0)
+      break;
+  if (CONSTANT_P (*expr))
+    return;

 
   e = loop_preheader_edge (loop);
   if (e->src == ENTRY_BLOCK_PTR)
     return;
 
 
   e = loop_preheader_edge (loop);
   if (e->src == ENTRY_BLOCK_PTR)
     return;
 

-  altered = INITIALIZE_REG_SET (altered_head);
+  altered = ALLOC_REG_SET (&reg_obstack);
+  this_altered = ALLOC_REG_SET (&reg_obstack);

 
 

+  expression_valid = true;
+  last_valid_expr = *expr;
+  cond_list = NULL_RTX;

   while (1)
     {
   while (1)
     {

-      basic_block tmp_bb;
-

       insn = BB_END (e->src);
       if (any_condjump_p (insn))
        {
          rtx cond = get_condition (BB_END (e->src), NULL, false, true);
       insn = BB_END (e->src);
       if (any_condjump_p (insn))
        {
          rtx cond = get_condition (BB_END (e->src), NULL, false, true);

-      
+

          if (cond && (e->flags & EDGE_FALLTHRU))
            cond = reversed_condition (cond);
          if (cond)
            {
          if (cond && (e->flags & EDGE_FALLTHRU))
            cond = reversed_condition (cond);
          if (cond)
            {

+             rtx old = *expr;

              simplify_using_condition (cond, expr, altered);
              simplify_using_condition (cond, expr, altered);

-             if (CONSTANT_P (*expr))
+             if (old != *expr)

                {
                {

-                 FREE_REG_SET (altered);
-                 return;
+                 rtx note;
+                 if (CONSTANT_P (*expr))
+                   goto out;
+                 for (note = cond_list; note; note = XEXP (note, 1))
+                   {
+                     simplify_using_condition (XEXP (note, 0), expr, altered);
+                     if (CONSTANT_P (*expr))
+                       goto out;
+                   }

                }
                }

+             cond_list = alloc_EXPR_LIST (0, cond, cond_list);

            }
        }
 
       FOR_BB_INSNS_REVERSE (e->src, insn)
        {
            }
        }
 
       FOR_BB_INSNS_REVERSE (e->src, insn)
        {

+         rtx src, dest;
+         rtx old = *expr;
+

          if (!INSN_P (insn))
            continue;
          if (!INSN_P (insn))
            continue;

-           
-         simplify_using_assignment (insn, expr, altered);
-         if (CONSTANT_P (*expr))
+
+         CLEAR_REG_SET (this_altered);
+         note_stores (PATTERN (insn), mark_altered, this_altered);
+         if (CALL_P (insn))
+           {
+             int i;
+
+             /* Kill all call clobbered registers.  */
+             for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
+               if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i))
+                 SET_REGNO_REG_SET (this_altered, i);
+           }
+
+         if (suitable_set_for_replacement (insn, &dest, &src))

            {
            {

-             FREE_REG_SET (altered);
-             return;
+             rtx *pnote, *pnote_next;
+
+             replace_in_expr (expr, dest, src);
+             if (CONSTANT_P (*expr))
+               goto out;
+
+             for (pnote = &cond_list; *pnote; pnote = pnote_next)
+               {
+                 rtx note = *pnote;
+                 rtx old_cond = XEXP (note, 0);
+
+                 pnote_next = &XEXP (note, 1);
+                 replace_in_expr (&XEXP (note, 0), dest, src);
+
+                 /* We can no longer use a condition that has been simplified
+                    to a constant, and simplify_using_condition will abort if
+                    we try.  */
+                 if (CONSTANT_P (XEXP (note, 0)))
+                   {
+                     *pnote = *pnote_next;
+                     pnote_next = pnote;
+                     free_EXPR_LIST_node (note);
+                   }
+                 /* Retry simplifications with this condition if either the
+                    expression or the condition changed.  */
+                 else if (old_cond != XEXP (note, 0) || old != *expr)
+                   simplify_using_condition (XEXP (note, 0), expr, altered);
+               }

            }
            }

+         else
+           /* If we did not use this insn to make a replacement, any overlap
+              between stores in this insn and our expression will cause the
+              expression to become invalid.  */
+           if (for_each_rtx (expr, altered_reg_used, this_altered))
+             goto out;
+
+         if (CONSTANT_P (*expr))
+           goto out;
+
+         IOR_REG_SET (altered, this_altered);
+
+         /* If the expression now contains regs that have been altered, we
+            can't return it to the caller.  However, it is still valid for
+            further simplification, so keep searching to see if we can
+            eventually turn it into a constant.  */
+         if (for_each_rtx (expr, altered_reg_used, altered))
+           expression_valid = false;
+         if (expression_valid)
+           last_valid_expr = *expr;

        }
 
        }
 

-      /* This is a bit subtle.  Store away e->src in tmp_bb, since we
-        modify `e' and this can invalidate the subsequent count of
-        e->src's predecessors by looking at the wrong block.  */
-      tmp_bb = e->src;
-      e = EDGE_PRED (tmp_bb, 0);
-      if (EDGE_COUNT (tmp_bb->preds) > 1
-         || e->src == ENTRY_BLOCK_PTR)
+      if (!single_pred_p (e->src)
+         || single_pred (e->src) == ENTRY_BLOCK_PTR)

        break;
        break;

+      e = single_pred_edge (e->src);

     }
 
     }
 

+ out:
+  free_EXPR_LIST_list (&cond_list);
+  if (!CONSTANT_P (*expr))
+    *expr = last_valid_expr;

   FREE_REG_SET (altered);
   FREE_REG_SET (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


@@ -1880,7 +2068,7 @@ shorten_into_mode (struct rtx_iv *iv, enum machine_mode mode,
        break;
 
       default:
        break;
 
       default:

-       abort ();
+       gcc_unreachable ();

     }
 
   iv->mode = mode;
     }
 
   iv->mode = mode;


@@ -1938,7 +2126,7 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
        break;
 
       default:
        break;
 
       default:

-       abort ();
+       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


@@ -1949,7 +2137,7 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
      in different modes.  This does not seem impossible to handle, but
      it hardly ever occurs in practice.
      and iv0 and iv1 are both ivs iterating in SI mode, but calculated
      in different modes.  This does not seem impossible to handle, but
      it hardly ever occurs in practice.

-     
+

      The only exception is the case when one of operands is invariant.
      For example pentium 3 generates comparisons like
      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we
      The only exception is the case when one of operands is invariant.
      For example pentium 3 generates comparisons like
      (lt (subreg:HI (reg:SI)) 100).  Here we assign HImode to 100, but we


@@ -2002,6 +2190,61 @@ canonicalize_iv_subregs (struct rtx_iv *iv0, struct rtx_iv *iv1,
   return true;
 }
 
   return true;
 }
 

+/* Tries to estimate the maximum number of iterations in LOOP, and store the
+   result in DESC.  This function is called from iv_number_of_iterations with
+   a number of fields in DESC already filled in.  OLD_NITER is the original
+   expression for the number of iterations, before we tried to simplify it.  */
+
+static unsigned HOST_WIDEST_INT
+determine_max_iter (struct loop *loop, struct niter_desc *desc, rtx old_niter)
+{
+  rtx niter = desc->niter_expr;
+  rtx mmin, mmax, cmp;
+  unsigned HOST_WIDEST_INT nmax, inc;
+
+  if (GET_CODE (niter) == AND
+      && CONST_INT_P (XEXP (niter, 0)))
+    {
+      nmax = INTVAL (XEXP (niter, 0));
+      if (!(nmax & (nmax + 1)))
+       {
+         desc->niter_max = nmax;
+         return nmax;
+       }
+    }
+
+  get_mode_bounds (desc->mode, desc->signed_p, desc->mode, &mmin, &mmax);
+  nmax = INTVAL (mmax) - INTVAL (mmin);
+
+  if (GET_CODE (niter) == UDIV)
+    {
+      if (!CONST_INT_P (XEXP (niter, 1)))
+       {
+         desc->niter_max = nmax;
+         return nmax;
+       }
+      inc = INTVAL (XEXP (niter, 1));
+      niter = XEXP (niter, 0);
+    }
+  else
+    inc = 1;
+
+  /* We could use a binary search here, but for now improving the upper
+     bound by just one eliminates one important corner case.  */
+  cmp = simplify_gen_relational (desc->signed_p ? LT : LTU, VOIDmode,
+                                desc->mode, old_niter, mmax);
+  simplify_using_initial_values (loop, UNKNOWN, &cmp);
+  if (cmp == const_true_rtx)
+    {
+      nmax--;
+
+      if (dump_file)
+       fprintf (dump_file, ";; improved upper bound by one.\n");
+    }
+  desc->niter_max = nmax / inc;
+  return nmax / inc;
+}
+

 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
    the result into DESC.  Very similar to determine_number_of_iterations
    (basically its rtl version), complicated by things like subregs.  */
 /* Computes number of iterations of the CONDITION in INSN in LOOP and stores
    the result into DESC.  Very similar to determine_number_of_iterations
    (basically its rtl version), complicated by things like subregs.  */


@@ -2010,16 +2253,17 @@ static void
 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
                         struct niter_desc *desc)
 {
 iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
                         struct niter_desc *desc)
 {

-  rtx op0, op1, delta, step, bound, may_xform, def_insn, tmp, tmp0, tmp1;
+  rtx op0, op1, delta, step, bound, may_xform, tmp, tmp0, tmp1;

   struct rtx_iv iv0, iv1, tmp_iv;
   rtx assumption, may_not_xform;
   enum rtx_code cond;
   enum machine_mode mode, comp_mode;
   rtx mmin, mmax, mode_mmin, mode_mmax;
   unsigned HOST_WIDEST_INT s, size, d, inv;
   struct rtx_iv iv0, iv1, tmp_iv;
   rtx assumption, may_not_xform;
   enum rtx_code cond;
   enum machine_mode mode, comp_mode;
   rtx mmin, mmax, mode_mmin, mode_mmax;
   unsigned HOST_WIDEST_INT s, size, d, inv;

-  HOST_WIDEST_INT up, down, inc;
+  HOST_WIDEST_INT up, down, inc, step_val;

   int was_sharp = false;
   rtx old_niter;
   int was_sharp = false;
   rtx old_niter;

+  bool step_is_pow2;

 
   /* The meaning of these assumptions is this:
      if !assumptions
 
   /* The meaning of these assumptions is this:
      if !assumptions


@@ -2037,15 +2281,13 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
   desc->niter_max = 0;
 
   cond = GET_CODE (condition);
   desc->niter_max = 0;
 
   cond = GET_CODE (condition);

-  if (!COMPARISON_P (condition))
-    abort ();
+  gcc_assert (COMPARISON_P (condition));

 
   mode = GET_MODE (XEXP (condition, 0));
   if (mode == VOIDmode)
     mode = GET_MODE (XEXP (condition, 1));
   /* The constant comparisons should be folded.  */
 
   mode = GET_MODE (XEXP (condition, 0));
   if (mode == VOIDmode)
     mode = GET_MODE (XEXP (condition, 1));
   /* The constant comparisons should be folded.  */

-  if (mode == VOIDmode)
-    abort ();
+  gcc_assert (mode != VOIDmode);

 
   /* We only handle integers or pointers.  */
   if (GET_MODE_CLASS (mode) != MODE_INT
 
   /* We only handle integers or pointers.  */
   if (GET_MODE_CLASS (mode) != MODE_INT


@@ -2053,15 +2295,13 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
     goto fail;
 
   op0 = XEXP (condition, 0);
     goto fail;
 
   op0 = XEXP (condition, 0);

-  def_insn = iv_get_reaching_def (insn, op0);
-  if (!iv_analyze (def_insn, op0, &iv0))
+  if (!iv_analyze (insn, op0, &iv0))

     goto fail;
   if (iv0.extend_mode == VOIDmode)
     iv0.mode = iv0.extend_mode = mode;
     goto fail;
   if (iv0.extend_mode == VOIDmode)
     iv0.mode = iv0.extend_mode = mode;

-  
+

   op1 = XEXP (condition, 1);
   op1 = XEXP (condition, 1);

-  def_insn = iv_get_reaching_def (insn, op1);
-  if (!iv_analyze (def_insn, op1, &iv1))
+  if (!iv_analyze (insn, op1, &iv1))

     goto fail;
   if (iv1.extend_mode == VOIDmode)
     iv1.mode = iv1.extend_mode = mode;
     goto fail;
   if (iv1.extend_mode == VOIDmode)
     iv1.mode = iv1.extend_mode = mode;


@@ -2106,7 +2346,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
 
   mode_mmin = lowpart_subreg (mode, mmin, comp_mode);
   mode_mmax = lowpart_subreg (mode, mmax, comp_mode);
 

-  if (GET_CODE (iv0.step) != CONST_INT || GET_CODE (iv1.step) != CONST_INT)
+  if (!CONST_INT_P (iv0.step) || !CONST_INT_P (iv1.step))

     goto fail;
 
   /* We can take care of the case of two induction variables chasing each other
     goto fail;
 
   /* We can take care of the case of two induction variables chasing each other


@@ -2126,10 +2366,26 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
     goto fail;
 
   if (iv0.step == const0_rtx && iv1.step == const0_rtx)
     goto fail;
 

-  /* Ignore loops of while (i-- < 10) type.  */
-  if (cond != NE
-      && (INTVAL (iv0.step) < 0 || INTVAL (iv1.step) > 0))
-    goto fail;
+  if (cond != NE)
+    {
+      if (iv0.step == const0_rtx)
+       step_val = -INTVAL (iv1.step);
+      else
+       step_val = INTVAL (iv0.step);
+
+      /* Ignore loops of while (i-- < 10) type.  */
+      if (step_val < 0)
+       goto fail;
+
+      step_is_pow2 = !(step_val & (step_val - 1));
+    }
+  else
+    {
+      /* We do not care about whether the step is power of two in this
+        case.  */
+      step_is_pow2 = false;
+      step_val = 0;
+    }

 
   /* Some more condition normalization.  We must record some assumptions
      due to overflows.  */
 
   /* Some more condition normalization.  We must record some assumptions
      due to overflows.  */


@@ -2149,7 +2405,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
                                                  mode_mmax);
            if (assumption == const_true_rtx)
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
                                                  mode_mmax);
            if (assumption == const_true_rtx)

-             goto zero_iter;
+             goto zero_iter_simplify;

            iv0.base = simplify_gen_binary (PLUS, comp_mode,
                                            iv0.base, const1_rtx);
          }
            iv0.base = simplify_gen_binary (PLUS, comp_mode,
                                            iv0.base, const1_rtx);
          }


@@ -2159,7 +2415,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
                                                  mode_mmin);
            if (assumption == const_true_rtx)
            assumption = simplify_gen_relational (EQ, SImode, mode, tmp,
                                                  mode_mmin);
            if (assumption == const_true_rtx)

-             goto zero_iter;
+             goto zero_iter_simplify;

            iv1.base = simplify_gen_binary (PLUS, comp_mode,
                                            iv1.base, constm1_rtx);
          }
            iv1.base = simplify_gen_binary (PLUS, comp_mode,
                                            iv1.base, constm1_rtx);
          }


@@ -2186,7 +2442,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
            {
              desc->infinite =
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
            {
              desc->infinite =
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);

-             return;
+             /* Fill in the remaining fields somehow.  */
+             goto zero_iter_simplify;

            }
        }
       else
            }
        }
       else


@@ -2196,7 +2453,8 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
            {
              desc->infinite =
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);
            {
              desc->infinite =
                      alloc_EXPR_LIST (0, const_true_rtx, NULL_RTX);

-             return;
+             /* Fill in the remaining fields somehow.  */
+             goto zero_iter_simplify;

            }
        }
     }
            }
        }
     }


@@ -2219,7 +2477,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       may_xform = const0_rtx;
       may_not_xform = const_true_rtx;
 
       may_xform = const0_rtx;
       may_not_xform = const_true_rtx;
 

-      if (GET_CODE (delta) == CONST_INT)
+      if (CONST_INT_P (delta))

        {
          if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
            {
        {
          if (was_sharp && INTVAL (delta) == INTVAL (step) - 1)
            {


@@ -2270,8 +2528,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
              /* If the step is a power of two and the final value we have
                 computed overflows, the cycle is infinite.  Otherwise it
                 is nontrivial to compute the number of iterations.  */
              /* If the step is a power of two and the final value we have
                 computed overflows, the cycle is infinite.  Otherwise it
                 is nontrivial to compute the number of iterations.  */

-             s = INTVAL (step);
-             if ((s & (s - 1)) == 0)
+             if (step_is_pow2)

                desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
                                                  desc->infinite);
              else
                desc->infinite = alloc_EXPR_LIST (0, may_not_xform,
                                                  desc->infinite);
              else


@@ -2283,11 +2540,11 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
             number of iterations in this step, so record the information
             here.  */
          inc = INTVAL (iv0.step) - INTVAL (iv1.step);
             number of iterations in this step, so record the information
             here.  */
          inc = INTVAL (iv0.step) - INTVAL (iv1.step);

-         if (GET_CODE (iv1.base) == CONST_INT)
+         if (CONST_INT_P (iv1.base))

            up = INTVAL (iv1.base);
          else
            up = INTVAL (mode_mmax) - inc;
            up = INTVAL (iv1.base);
          else
            up = INTVAL (mode_mmax) - inc;

-         down = INTVAL (GET_CODE (iv0.base) == CONST_INT
+         down = INTVAL (CONST_INT_P (iv0.base)

                         ? iv0.base
                         : mode_mmin);
          desc->niter_max = (up - down) / inc + 1;
                         ? iv0.base
                         : mode_mmin);
          desc->niter_max = (up - down) / inc + 1;


@@ -2308,7 +2565,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
          assumption = simplify_gen_relational (reverse_condition (cond),
                                                SImode, mode, tmp0, tmp1);
          if (assumption == const_true_rtx)
          assumption = simplify_gen_relational (reverse_condition (cond),
                                                SImode, mode, tmp0, tmp1);
          if (assumption == const_true_rtx)

-           goto zero_iter;
+           goto zero_iter_simplify;

          else if (assumption != const0_rtx)
            desc->noloop_assumptions =
                    alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
          else if (assumption != const0_rtx)
            desc->noloop_assumptions =
                    alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);


@@ -2353,8 +2610,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 
       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
       inv = inverse (s, size);
 
       tmp = simplify_gen_binary (UDIV, mode, tmp1, GEN_INT (d));
       inv = inverse (s, size);

-      inv = trunc_int_for_mode (inv, mode);
-      tmp = simplify_gen_binary (MULT, mode, tmp, GEN_INT (inv));
+      tmp = simplify_gen_binary (MULT, mode, tmp, gen_int_mode (inv, mode));

       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
     }
   else
       desc->niter_expr = simplify_gen_binary (AND, mode, tmp, bound);
     }
   else


@@ -2372,11 +2628,32 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 
          bound = simplify_gen_binary (MINUS, mode, mode_mmax,
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 
          bound = simplify_gen_binary (MINUS, mode, mode_mmax,

-                                      lowpart_subreg (mode, step, comp_mode));
-         assumption = simplify_gen_relational (cond, SImode, mode,
-                                               tmp1, bound);
-         desc->assumptions =
-                 alloc_EXPR_LIST (0, assumption, desc->assumptions);
+                                      lowpart_subreg (mode, step,
+                                                      comp_mode));
+         if (step_is_pow2)
+           {
+             rtx t0, t1;
+
+             /* If s is power of 2, we know that the loop is infinite if
+                a % s <= b % s and b + s overflows.  */
+             assumption = simplify_gen_relational (reverse_condition (cond),
+                                                   SImode, mode,
+                                                   tmp1, bound);
+
+             t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+             t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+             tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+             assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+             desc->infinite =
+                     alloc_EXPR_LIST (0, assumption, desc->infinite);
+           }
+         else
+           {
+             assumption = simplify_gen_relational (cond, SImode, mode,
+                                                   tmp1, bound);
+             desc->assumptions =
+                     alloc_EXPR_LIST (0, assumption, desc->assumptions);
+           }

 
          tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
          tmp = lowpart_subreg (mode, tmp, comp_mode);
 
          tmp = simplify_gen_binary (PLUS, comp_mode, iv1.base, iv0.step);
          tmp = lowpart_subreg (mode, tmp, comp_mode);


@@ -2395,12 +2672,32 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
          tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 
          tmp0 = lowpart_subreg (mode, iv0.base, comp_mode);
          tmp1 = lowpart_subreg (mode, iv1.base, comp_mode);
 

-         bound = simplify_gen_binary (MINUS, mode, mode_mmin,
+         bound = simplify_gen_binary (PLUS, mode, mode_mmin,

                                       lowpart_subreg (mode, step, comp_mode));
                                       lowpart_subreg (mode, step, comp_mode));

-         assumption = simplify_gen_relational (cond, SImode, mode,
-                                               bound, tmp0);
-         desc->assumptions =
-                 alloc_EXPR_LIST (0, assumption, desc->assumptions);
+         if (step_is_pow2)
+           {
+             rtx t0, t1;
+
+             /* If s is power of 2, we know that the loop is infinite if
+                a % s <= b % s and a - s overflows.  */
+             assumption = simplify_gen_relational (reverse_condition (cond),
+                                                   SImode, mode,
+                                                   bound, tmp0);
+
+             t0 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp0), step);
+             t1 = simplify_gen_binary (UMOD, mode, copy_rtx (tmp1), step);
+             tmp = simplify_gen_relational (cond, SImode, mode, t0, t1);
+             assumption = simplify_gen_binary (AND, SImode, assumption, tmp);
+             desc->infinite =
+                     alloc_EXPR_LIST (0, assumption, desc->infinite);
+           }
+         else
+           {
+             assumption = simplify_gen_relational (cond, SImode, mode,
+                                                   bound, tmp0);
+             desc->assumptions =
+                     alloc_EXPR_LIST (0, assumption, desc->assumptions);
+           }

 
          tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
          tmp = lowpart_subreg (mode, tmp, comp_mode);
 
          tmp = simplify_gen_binary (PLUS, comp_mode, iv0.base, iv1.step);
          tmp = lowpart_subreg (mode, tmp, comp_mode);


@@ -2411,7 +2708,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
          delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
        }
       if (assumption == const_true_rtx)
          delta = simplify_gen_binary (MINUS, mode, tmp1, delta);
        }
       if (assumption == const_true_rtx)

-       goto zero_iter;
+       goto zero_iter_simplify;

       else if (assumption != const0_rtx)
        desc->noloop_assumptions =
                alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);
       else if (assumption != const0_rtx)
        desc->noloop_assumptions =
                alloc_EXPR_LIST (0, assumption, desc->noloop_assumptions);


@@ -2456,7 +2753,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
     goto zero_iter;
 
       && XEXP (desc->noloop_assumptions, 0) == const_true_rtx)
     goto zero_iter;
 

-  if (GET_CODE (desc->niter_expr) == CONST_INT)
+  if (CONST_INT_P (desc->niter_expr))

     {
       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
 
     {
       unsigned HOST_WIDEST_INT val = INTVAL (desc->niter_expr);
 


@@ -2466,7 +2763,7 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
   else
     {
       if (!desc->niter_max)
   else
     {
       if (!desc->niter_max)

-       desc->niter_max = determine_max_iter (desc);
+       desc->niter_max = determine_max_iter (loop, desc, old_niter);

 
       /* simplify_using_initial_values does a copy propagation on the registers
         in the expression for the number of iterations.  This prolongs life
 
       /* simplify_using_initial_values does a copy propagation on the registers
         in the expression for the number of iterations.  This prolongs life


@@ -2479,16 +2776,26 @@ iv_number_of_iterations (struct loop *loop, rtx insn, rtx condition,
 
   return;
 
 
   return;
 

-fail:
-  desc->simple_p = false;
-  return;
+zero_iter_simplify:
+  /* Simplify the assumptions.  */
+  simplify_using_initial_values (loop, AND, &desc->assumptions);
+  if (desc->assumptions
+      && XEXP (desc->assumptions, 0) == const0_rtx)
+    goto fail;
+  simplify_using_initial_values (loop, IOR, &desc->infinite);

 
 

+  /* Fallthru.  */

 zero_iter:
   desc->const_iter = true;
   desc->niter = 0;
   desc->niter_max = 0;
 zero_iter:
   desc->const_iter = true;
   desc->niter = 0;
   desc->niter_max = 0;

+  desc->noloop_assumptions = NULL_RTX;

   desc->niter_expr = const0_rtx;
   return;
   desc->niter_expr = const0_rtx;
   return;

+
+fail:
+  desc->simple_p = false;
+  return;

 }
 
 /* Checks whether E is a simple exit from LOOP and stores its description
 }
 
 /* Checks whether E is a simple exit from LOOP and stores its description


@@ -2560,17 +2867,26 @@ find_simple_exit (struct loop *loop, struct niter_desc *desc)
        {
          if (flow_bb_inside_loop_p (loop, e->dest))
            continue;
        {
          if (flow_bb_inside_loop_p (loop, e->dest))
            continue;

-         
+

          check_simple_exit (loop, e, &act);
          if (!act.simple_p)
            continue;
 
          check_simple_exit (loop, e, &act);
          if (!act.simple_p)
            continue;
 

-         /* Prefer constant iterations; the less the better.  */

          if (!any)
            any = true;
          if (!any)
            any = true;

-         else if (!act.const_iter
-                  || (desc->const_iter && act.niter >= desc->niter))
-           continue;
+         else
+           {
+             /* Prefer constant iterations; the less the better.  */
+             if (!act.const_iter
+                 || (desc->const_iter && act.niter >= desc->niter))
+               continue;
+
+             /* Also if the actual exit may be infinite, while the old one
+                not, prefer the old one.  */
+             if (act.infinite && !desc->infinite)
+               continue;
+           }
+

          *desc = act;
        }
     }
          *desc = act;
        }
     }


@@ -2628,11 +2944,48 @@ get_simple_loop_desc (struct loop *loop)
   if (desc)
     return desc;
 
   if (desc)
     return desc;
 

-  desc = xmalloc (sizeof (struct niter_desc));
+  /* At least desc->infinite is not always initialized by
+     find_simple_loop_exit.  */
+  desc = XCNEW (struct niter_desc);

   iv_analysis_loop_init (loop);
   find_simple_exit (loop, desc);
   loop->aux = desc;
 
   iv_analysis_loop_init (loop);
   find_simple_exit (loop, desc);
   loop->aux = desc;
 

+  if (desc->simple_p && (desc->assumptions || desc->infinite))
+    {
+      const char *wording;
+
+      /* Assume that no overflow happens and that the loop is finite.
+        We already warned at the tree level if we ran optimizations there.  */
+      if (!flag_tree_loop_optimize && warn_unsafe_loop_optimizations)
+       {
+         if (desc->infinite)
+           {
+             wording =
+               flag_unsafe_loop_optimizations
+               ? N_("assuming that the loop is not infinite")
+               : N_("cannot optimize possibly infinite loops");
+             warning (OPT_Wunsafe_loop_optimizations, "%s",
+                      gettext (wording));
+           }
+         if (desc->assumptions)
+           {
+             wording =
+               flag_unsafe_loop_optimizations
+               ? N_("assuming that the loop counter does not overflow")
+               : N_("cannot optimize loop, the loop counter may overflow");
+             warning (OPT_Wunsafe_loop_optimizations, "%s",
+                      gettext (wording));
+           }
+       }
+
+      if (flag_unsafe_loop_optimizations)
+       {
+         desc->assumptions = NULL_RTX;
+         desc->infinite = NULL_RTX;
+       }
+    }
+

   return desc;
 }
 
   return desc;
 }