tree-scalar-evolution.c: New file.

	* tree-scalar-evolution.c: New file.
	* tree-scalar-evolution.h: New file.
	* tree-ssa-loop-niter.c: New file.
	* Makefile.in (SCEV_H): New.
	(tree-scalar-evolution.o, tree-ssa-loop-niter.o): Add new files.
	* cfgloop.h (struct loop): Add bounds field.
	* tree-flow.h (struct tree_niter_desc): New type.
	(number_of_iterations_cond, number_of_iterations_exit,
	loop_niter_by_eval, find_loop_niter_by_eval,
	estimate_numbers_of_iterations, can_count_iv_in_wider_type,
	free_numbers_of_iterations_estimates): Declare.
	* tree.h (lower_bound_in_type, upper_bound_in_type): Declare.
	* params.def (PARAM_MAX_ITERATIONS_TO_TRACK): New parameter.
	* doc/invoke.texi (max-iterations-to-track): Document.

From-SVN: r84340

10 files changed, 1487 insertions, 1 deletions

diff --git a/gcc/ChangeLog b/gcc/ChangeLog
index 20ac905..8136c4e 100644
--- a/gcc/ChangeLog
+++ b/gcc/ChangeLog
@@ -1,3 +1,20 @@
+2004-07-08  Zdenek Dvorak  <rakdver@atrey.karlin.mff.cuni.cz>
+
+	* tree-scalar-evolution.c: New file.
+	* tree-scalar-evolution.h: New file.
+	* tree-ssa-loop-niter.c: New file.
+	* Makefile.in (SCEV_H): New.
+	(tree-scalar-evolution.o, tree-ssa-loop-niter.o): Add new files.
+	* cfgloop.h (struct loop): Add bounds field.
+	* tree-flow.h (struct tree_niter_desc): New type.
+	(number_of_iterations_cond, number_of_iterations_exit,
+	loop_niter_by_eval, find_loop_niter_by_eval,
+	estimate_numbers_of_iterations, can_count_iv_in_wider_type,
+	free_numbers_of_iterations_estimates): Declare.
+	* tree.h (lower_bound_in_type, upper_bound_in_type): Declare.
+	* params.def (PARAM_MAX_ITERATIONS_TO_TRACK): New parameter.
+	* doc/invoke.texi (max-iterations-to-track): Document.
+
 2004-07-08  Kaz Kojima  <kkojima@gcc.gnu.org>
 
 	* config/sh/sh.c (sh_va_arg): Initinalize lab_over.
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index f4acac2..3e20a0c 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -728,6 +728,7 @@ TREE_SSA_LIVE_H = tree-ssa-live.h $(PARTITION_H)
 PRETTY_PRINT_H = pretty-print.h input.h $(OBSTACK_H)
 DIAGNOSTIC_H = diagnostic.h diagnostic.def $(PRETTY_PRINT_H)
 C_PRETTY_PRINT_H = $(PRETTY_PRINT_H) $(C_COMMON_H) $(TREE_H)
+SCEV_H = tree-scalar-evolution.h $(GGC_H) tree-chrec.h
 
 #
 # Now figure out from those variables how to compile and link.
@@ -886,7 +887,7 @@ C_OBJS = c-parse.o c-lang.o stub-objc.o $(C_AND_OBJC_OBJS)
 # Language-independent object files.
 
 OBJS-common = \
- tree-chrec.o                                                              \
+ tree-chrec.o tree-scalar-evolution.o					   \
  tree-cfg.o tree-dfa.o tree-eh.o tree-ssa.o tree-optimize.o tree-gimple.o  \
  tree-alias-type.o gimplify.o tree-pretty-print.o tree-into-ssa.o          \
  tree-outof-ssa.o tree-alias-common.o tree-ssa-ccp.o tree-vn.o             \
@@ -895,6 +896,7 @@ OBJS-common = \
  tree-ssa-phiopt.o tree-ssa-forwprop.o tree-nested.o tree-ssa-dse.o	   \
  tree-ssa-dom.o domwalk.o tree-tailcall.o gimple-low.o tree-iterator.o	   \
  tree-phinodes.o tree-ssanames.o tree-sra.o tree-complex.o tree-ssa-loop.o \
+ tree-ssa-loop-niter.o \
  alias.o bb-reorder.o bitmap.o builtins.o caller-save.o calls.o	  	   \
  cfg.o cfganal.o cfgbuild.o cfgcleanup.o cfglayout.o cfgloop.o		   \
  cfgloopanal.o cfgloopmanip.o loop-init.o loop-unswitch.o loop-unroll.o	   \
@@ -1676,6 +1678,10 @@ tree-ssa-loop.o : tree-ssa-loop.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) \
    output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    tree-pass.h $(FLAGS_H) tree-inline.h
+tree-ssa-loop-niter.o : tree-ssa-loop-niter.c $(TREE_FLOW_H) $(CONFIG_H) \
+   $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) cfgloop.h $(PARAMS_H) tree-inline.h \
+   output.h diagnostic.h $(TM_H) coretypes.h $(TREE_DUMP_H) flags.h \
+   tree-pass.h $(SCEV_H)		 
 tree-ssa-loop-ch.o : tree-ssa-loop-ch.c $(TREE_FLOW_H) $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) $(CFGLOOP_H) tree-inline.h \
    output.h diagnostic.h $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
@@ -1708,6 +1714,10 @@ tree-browser.o : tree-browser.c tree-browser.def $(CONFIG_H) $(SYSTEM_H) \
    $(TM_H) coretypes.h
 tree-chrec.o: tree-chrec.c $(CONFIG_H) $(SYSTEM_H) coretypes.h $(TM_H) \
    errors.h $(GGC_H) $(TREE_H) tree-chrec.h tree-pass.h
+tree-scalar-evolution.o: tree-scalar-evolution.c $(CONFIG_H) $(SYSTEM_H) \
+   coretypes.h $(TM_H) errors.h $(GGC_H) $(TREE_H) $(RTL_H) \
+   $(BASIC_BLOCK_H) diagnostic.h $(TREE_FLOW_H) $(TREE_DUMP_H) \
+   $(TIMEVAR_H) cfgloop.h $(SCEV_H)
 tree-gimple.o : tree-gimple.c $(CONFIG_H) $(SYSTEM_H) $(TREE_H) $(EXPR_H) \
 	$(RTL_H) $(TREE_GIMPLE_H) $(TM_H) coretypes.h bitmap.h $(GGC_H)
 tree-mudflap.o : $(CONFIG_H) errors.h $(SYSTEM_H) $(TREE_H) tree-inline.h \
diff --git a/gcc/cfgloop.h b/gcc/cfgloop.h
index d73c99b..156438a 100644
--- a/gcc/cfgloop.h
+++ b/gcc/cfgloop.h
@@ -175,6 +175,9 @@ struct loop
   /* The number of LABEL_REFs on exit_labels for this loop and all
      loops nested inside it.  */
   int exit_count;
+
+  /* Upper bound on number of iterations of a loop.  */
+  struct nb_iter_bound *bounds;
 };
 
 /* Flags for state of loop structure.  */
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index ca7e12e..aed9010 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -5174,6 +5174,11 @@ The maximum number of insns of an unswitched loop.
 @item max-unswitch-level
 The maximum number of branches unswitched in a single loop.
 
+@item max-iterations-to-track
+
+The maximum number of iterations of a loop the brute force algorithm
+for analysis of # of iterations of the loop tries to evaluate.
+
 @item hot-bb-count-fraction
 Select fraction of the maximal count of repetitions of basic block in program
 given basic block needs to have to be considered hot.
diff --git a/gcc/params.def b/gcc/params.def
index 72095af..56d8360 100644
--- a/gcc/params.def
+++ b/gcc/params.def
@@ -229,6 +229,14 @@ DEFPARAM(PARAM_MAX_UNSWITCH_LEVEL,
 	"The maximum number of unswitchings in a single loop",
 	3)
 
+/* The maximum number of iterations of a loop the brute force algorithm
+   for analysis of # of iterations of the loop tries to evaluate.  */
+DEFPARAM(PARAM_MAX_ITERATIONS_TO_TRACK,
+	"max-iterations-to-track",
+	"Bound on the number of iterations the brute force # of iterations \
+	 analysis algorithm evaluates",
+	1000)
+
 DEFPARAM(PARAM_MAX_SMS_LOOP_NUMBER,
 	 "max-sms-loop-number",
 	 "Maximum number of loops to perform swing modulo scheduling on \
diff --git a/gcc/tree-flow.h b/gcc/tree-flow.h
index f9f8115..102b6ea 100644
--- a/gcc/tree-flow.h
+++ b/gcc/tree-flow.h
@@ -597,6 +597,50 @@ extern void propagate_tree_value (tree *, tree);
 extern void replace_exp (use_operand_p, tree);
 extern bool may_propagate_copy (tree, tree);
 
+/* Description of number of iterations of a loop.  All the expressions inside
+   the structure can be evaluated at the end of the loop's preheader
+   (and due to ssa form, also anywhere inside the body of the loop).  */
+
+struct tree_niter_desc
+{
+  tree assumptions;	/* The boolean expression.  If this expression evalutes
+			   to false, then the other fields in this structure
+			   should not be used; there is no guarantee that they
+			   will be correct.  */
+  tree may_be_zero;	/* The booleand expression.  If it evaluates to true,
+			   the loop will exit in the first iteration (i.e.
+			   its latch will not be executed), even if the niter
+			   field says otherwise.  */
+  tree niter;		/* The expression giving the number of iterations of
+			   a loop (provided that assumptions == true and
+			   may_be_zero == false), more precisely the number
+			   of executions of the latch of the loop.  */
+  tree additional_info;	/* The boolean expression.  Sometimes we use additional
+			   knowledge to simplify the other expressions
+			   contained in this structure (for example the
+			   knowledge about value ranges of operands on entry to
+			   the loop).  If this is a case, conjunction of such
+			   condition is stored in this field, so that we do not
+			   lose the information: for example if may_be_zero
+			   is (n <= 0) and niter is (unsigned) n, we know
+			   that the number of iterations is at most
+			   MAX_SIGNED_INT.  However if the (n <= 0) assumption
+			   is eliminated (by looking at the guard on entry of
+			   the loop), then the information would be lost.  */
+};
+
+/* In tree-ssa-loop*.c  */
+
+void number_of_iterations_cond (tree, tree, tree, enum tree_code, tree, tree,
+				struct tree_niter_desc *);
+bool number_of_iterations_exit (struct loop *, edge,
+				struct tree_niter_desc *niter);
+tree loop_niter_by_eval (struct loop *, edge);
+tree find_loop_niter_by_eval (struct loop *, edge *);
+void estimate_numbers_of_iterations (struct loops *);
+tree can_count_iv_in_wider_type (struct loop *, tree, tree, tree, tree);
+void free_numbers_of_iterations_estimates (struct loops *);
+
 /* In tree-flow-inline.h  */
 static inline int phi_arg_from_edge (tree, edge);
 static inline bool is_call_clobbered (tree);
diff --git a/gcc/tree-scalar-evolution.c b/gcc/tree-scalar-evolution.c
new file mode 100644
index 0000000..fc671e3
--- /dev/null
+++ b/gcc/tree-scalar-evolution.c
@@ -0,0 +1,61 @@
+/* Scalar evolution detector.
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+   Contributed by Sebastian Pop <s.pop@laposte.net>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "errors.h"
+#include "ggc.h"
+#include "tree.h"
+#include "rtl.h"
+#include "basic-block.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "timevar.h"
+#include "cfgloop.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+
+/* Analyze all the parameters of the chrec that were left under a
+   symbolic form.  LOOP is the loop in which symbolic names have to
+   be analyzed and instantiated.  */
+
+tree
+instantiate_parameters (struct loop *loop ATTRIBUTE_UNUSED,
+			tree chrec)
+{
+  /* Just a dummy definition for now.  */
+  return chrec;
+}
+
+/* Checks whether OP behaves as a simple affine iv of LOOP in STMT and returns
+   its BASE and STEP if possible.  */
+
+bool
+simple_iv (struct loop *loop ATTRIBUTE_UNUSED, tree stmt ATTRIBUTE_UNUSED,
+	   tree op ATTRIBUTE_UNUSED, tree *base ATTRIBUTE_UNUSED,
+	   tree *step ATTRIBUTE_UNUSED)
+{
+  /* Just a dummy definition for now.  */
+  return false;
+}
diff --git a/gcc/tree-scalar-evolution.h b/gcc/tree-scalar-evolution.h
new file mode 100644
index 0000000..d39fd93
--- /dev/null
+++ b/gcc/tree-scalar-evolution.h
@@ -0,0 +1,28 @@
+/* Scalar evolution detector.
+   Copyright (C) 2003, 2004 Free Software Foundation, Inc.
+   Contributed by Sebastian Pop <s.pop@laposte.net>
+
+This file is part of GCC.
+
+GCC is free software; you can redistribute it and/or modify it under
+the terms of the GNU General Public License as published by the Free
+Software Foundation; either version 2, or (at your option) any later
+version.
+
+GCC is distributed in the hope that it will be useful, but WITHOUT ANY
+WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#ifndef GCC_TREE_SCALAR_EVOLUTION_H
+#define GCC_TREE_SCALAR_EVOLUTION_H
+
+extern tree instantiate_parameters (struct loop *, tree);
+extern bool simple_iv (struct loop *, tree, tree, tree *, tree *);
+
+#endif  /* GCC_TREE_SCALAR_EVOLUTION_H  */
diff --git a/gcc/tree-ssa-loop-niter.c b/gcc/tree-ssa-loop-niter.c
new file mode 100644
index 0000000..67663e4
--- /dev/null
+++ b/gcc/tree-ssa-loop-niter.c
@@ -0,0 +1,1305 @@
+/* Functions to determine/estimate number of iterations of a loop.
+   Copyright (C) 2004 Free Software Foundation, Inc.
+   
+This file is part of GCC.
+   
+GCC is free software; you can redistribute it and/or modify it
+under the terms of the GNU General Public License as published by the
+Free Software Foundation; either version 2, or (at your option) any
+later version.
+   
+GCC is distributed in the hope that it will be useful, but WITHOUT
+ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
+FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
+for more details.
+   
+You should have received a copy of the GNU General Public License
+along with GCC; see the file COPYING.  If not, write to the Free
+Software Foundation, 59 Temple Place - Suite 330, Boston, MA
+02111-1307, USA.  */
+
+#include "config.h"
+#include "system.h"
+#include "coretypes.h"
+#include "tm.h"
+#include "tree.h"
+#include "rtl.h"
+#include "tm_p.h"
+#include "hard-reg-set.h"
+#include "basic-block.h"
+#include "output.h"
+#include "diagnostic.h"
+#include "tree-flow.h"
+#include "tree-dump.h"
+#include "cfgloop.h"
+#include "tree-pass.h"
+#include "ggc.h"
+#include "tree-chrec.h"
+#include "tree-scalar-evolution.h"
+#include "params.h"
+#include "flags.h"
+#include "tree-inline.h"
+
+#define SWAP(X, Y) do { void *tmp = (X); (X) = (Y); (Y) = tmp; } while (0)
+
+/* Just to shorten the ugly names.  */
+#define EXEC_BINARY nondestructive_fold_binary_to_constant
+#define EXEC_UNARY nondestructive_fold_unary_to_constant
+
+/*
+
+   Analysis of number of iterations of an affine exit test.
+
+*/
+
+/* Returns true if ARG is either NULL_TREE or constant zero.  */
+
+static bool
+zero_p (tree arg)
+{
+  if (!arg)
+    return true;
+
+  return integer_zerop (arg);
+}
+
+/* Returns inverse of X modulo 2^s, where MASK = 2^s-1.  */
+
+static tree
+inverse (tree x, tree mask)
+{
+  tree type = TREE_TYPE (x);
+  tree ctr = EXEC_BINARY (RSHIFT_EXPR, type, mask, integer_one_node);
+  tree rslt = convert (type, integer_one_node);
+
+  while (integer_nonzerop (ctr))
+    {
+      rslt = EXEC_BINARY (MULT_EXPR, type, rslt, x);
+      rslt = EXEC_BINARY (BIT_AND_EXPR, type, rslt, mask);
+      x = EXEC_BINARY (MULT_EXPR, type, x, x);
+      x = EXEC_BINARY (BIT_AND_EXPR, type, x, mask);
+      ctr = EXEC_BINARY (RSHIFT_EXPR, type, ctr, integer_one_node);
+    }
+
+  return rslt;
+}
+
+/* Returns unsigned variant of TYPE.  */
+
+static tree
+unsigned_type_for (tree type)
+{
+  return make_unsigned_type (TYPE_PRECISION (type));
+}
+
+/* Returns signed variant of TYPE.  */
+
+static tree
+signed_type_for (tree type)
+{
+  return make_signed_type (TYPE_PRECISION (type));
+}
+
+/* Determine the number of iterations according to condition (for staying
+   inside loop) which compares two induction variables using comparison
+   operator CODE.  The induction variable on left side of the comparison
+   has base BASE0 and step STEP0. the right-hand side one has base
+   BASE1 and step STEP1.  Both induction variables must have type TYPE,
+   which must be an integer or pointer type.  STEP0 and STEP1 must be
+   constants (or NULL_TREE, which is interpreted as constant zero).
+   
+   The results (number of iterations and assumptions as described in
+   comments at struct tree_niter_desc in tree-flow.h) are stored to NITER.
+   In case we are unable to determine number of iterations, contents of
+   this structure is unchanged.  */
+
+void
+number_of_iterations_cond (tree type, tree base0, tree step0,
+			   enum tree_code code, tree base1, tree step1,
+			   struct tree_niter_desc *niter)
+{
+  tree step, delta, mmin, mmax;
+  tree may_xform, bound, s, d, tmp;
+  bool was_sharp = false;
+  tree assumption;
+  tree assumptions = boolean_true_node;
+  tree noloop_assumptions = boolean_false_node;
+  tree niter_type, signed_niter_type;
+
+  /* The meaning of these assumptions is this:
+     if !assumptions
+       then the rest of information does not have to be valid
+     if noloop_assumptions then the loop does not have to roll
+       (but it is only conservative approximation, i.e. it only says that
+       if !noloop_assumptions, then the loop does not end before the computed
+       number of iterations)  */
+
+  /* Make < comparison from > ones.  */
+  if (code == GE_EXPR
+      || code == GT_EXPR)
+    {
+      SWAP (base0, base1);
+      SWAP (step0, step1);
+      code = swap_tree_comparison (code);
+    }
+
+  /* We can handle the case when neither of the sides of the comparison is
+     invariant, provided that the test is NE_EXPR.  This rarely occurs in
+     practice, but it is simple enough to manage.  */
+  if (!zero_p (step0) && !zero_p (step1))
+    {
+      if (code != NE_EXPR)
+	return;
+
+      step0 = EXEC_BINARY (MINUS_EXPR, type, step0, step1);
+      step1 = NULL_TREE;
+    }
+
+  /* If the result is a constant,  the loop is weird.  More precise handling
+     would be possible, but the situation is not common enough to waste time
+     on it.  */
+  if (zero_p (step0) && zero_p (step1))
+    return;
+
+  /* Ignore loops of while (i-- < 10) type.  */
+  if (code != NE_EXPR)
+    {
+      if (step0 && !tree_expr_nonnegative_p (step0))
+	return;
+
+      if (!zero_p (step1) && tree_expr_nonnegative_p (step1))
+	return;
+    }
+
+  if (TREE_CODE (type) == POINTER_TYPE)
+    {
+      /* We assume pointer arithmetic never overflows.  */
+      mmin = mmax = NULL_TREE;
+    }
+  else
+    {
+      mmin = TYPE_MIN_VALUE (type);
+      mmax = TYPE_MAX_VALUE (type);
+    }
+
+  /* Some more condition normalization.  We must record some assumptions
+     due to overflows.  */
+
+  if (code == LT_EXPR)
+    {
+      /* We want to take care only of <=; this is easy,
+	 as in cases the overflow would make the transformation unsafe the loop
+	 does not roll.  Seemingly it would make more sense to want to take
+	 care of <, as NE is more simmilar to it, but the problem is that here
+	 the transformation would be more difficult due to possibly infinite
+	 loops.  */
+      if (zero_p (step0))
+	{
+	  if (mmax)
+	    assumption = fold (build (EQ_EXPR, boolean_type_node, base0, mmax));
+	  else
+	    assumption = boolean_false_node;
+	  if (integer_nonzerop (assumption))
+	    goto zero_iter;
+	  base0 = fold (build (PLUS_EXPR, type, base0,
+			       convert (type, integer_one_node)));
+	}
+      else
+	{
+	  if (mmin)
+	    assumption = fold (build (EQ_EXPR, boolean_type_node, base1, mmin));
+	  else
+	    assumption = boolean_false_node;
+	  if (integer_nonzerop (assumption))
+	    goto zero_iter;
+	  base1 = fold (build (MINUS_EXPR, type, base1,
+			       convert (type, integer_one_node)));
+	}
+      noloop_assumptions = assumption;
+      code = LE_EXPR;
+
+      /* It will be useful to be able to tell the difference once more in
+	 <= -> != reduction.  */
+      was_sharp = true;
+    }
+
+  /* Take care of trivially infinite loops.  */
+  if (code != NE_EXPR)
+    {
+      if (zero_p (step0)
+	  && mmin
+	  && operand_equal_p (base0, mmin, 0))
+	return;
+      if (zero_p (step1)
+	  && mmax
+	  && operand_equal_p (base1, mmax, 0))
+	return;
+    }
+
+  /* If we can we want to take care of NE conditions instead of size
+     comparisons, as they are much more friendly (most importantly
+     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
+     lower bound, their difference is constant c modulo step and that
+     there is not an overflow.  */
+  if (code != NE_EXPR)
+    {
+      if (zero_p (step0))
+	step = EXEC_UNARY (NEGATE_EXPR, type, step1);
+      else
+	step = step0;
+      delta = build (MINUS_EXPR, type, base1, base0);
+      delta = fold (build (FLOOR_MOD_EXPR, type, delta, step));
+      may_xform = boolean_false_node;
+
+      if (TREE_CODE (delta) == INTEGER_CST)
+	{
+	  tmp = EXEC_BINARY (MINUS_EXPR, type, step,
+			     convert (type, integer_one_node));
+	  if (was_sharp
+	      && operand_equal_p (delta, tmp, 0))
+	    {
+	      /* A special case.  We have transformed condition of type
+		 for (i = 0; i < 4; i += 4)
+		 into
+		 for (i = 0; i <= 3; i += 4)
+		 obviously if the test for overflow during that transformation
+		 passed, we cannot overflow here.  Most importantly any
+		 loop with sharp end condition and step 1 falls into this
+		 cathegory, so handling this case specially is definitely
+		 worth the troubles.  */
+	      may_xform = boolean_true_node;
+	    }
+	  else if (zero_p (step0))
+	    {
+	      if (!mmin)
+		may_xform = boolean_true_node;
+	      else
+		{
+		  bound = EXEC_BINARY (PLUS_EXPR, type, mmin, step);
+		  bound = EXEC_BINARY (MINUS_EXPR, type, bound, delta);
+		  may_xform = fold (build (LE_EXPR, boolean_type_node,
+					   bound, base0));
+		}
+	    }
+	  else
+	    {
+	      if (!mmax)
+		may_xform = boolean_true_node;
+	      else
+		{
+		  bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step);
+		  bound = EXEC_BINARY (PLUS_EXPR, type, bound, delta);
+		  may_xform = fold (build (LE_EXPR, boolean_type_node,
+					   base1, bound));
+		}
+	    }
+	}
+
+      if (!integer_zerop (may_xform))
+	{
+	  /* We perform the transformation always provided that it is not
+	     completely senseless.  This is OK, as we would need this assumption
+	     to determine the number of iterations anyway.  */
+	  if (!integer_nonzerop (may_xform))
+	    assumptions = may_xform;
+
+	  if (zero_p (step0))
+	    {
+	      base0 = build (PLUS_EXPR, type, base0, delta);
+	      base0 = fold (build (MINUS_EXPR, type, base0, step));
+	    }
+	  else
+	    {
+	      base1 = build (MINUS_EXPR, type, base1, delta);
+	      base1 = fold (build (PLUS_EXPR, type, base1, step));
+	    }
+
+	  assumption = fold (build (GT_EXPR, boolean_type_node, base0, base1));
+	  noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+					    noloop_assumptions, assumption));
+	  code = NE_EXPR;
+	}
+    }
+
+  /* Count the number of iterations.  */
+  niter_type = unsigned_type_for (type);
+  signed_niter_type = signed_type_for (type);
+
+  if (code == NE_EXPR)
+    {
+      /* Everything we do here is just arithmetics modulo size of mode.  This
+	 makes us able to do more involved computations of number of iterations
+	 than in other cases.  First transform the condition into shape
+	 s * i <> c, with s positive.  */
+      base1 = fold (build (MINUS_EXPR, type, base1, base0));
+      base0 = NULL_TREE;
+      if (!zero_p (step1))
+  	step0 = EXEC_UNARY (NEGATE_EXPR, type, step1);
+      step1 = NULL_TREE;
+      if (!tree_expr_nonnegative_p (convert (signed_niter_type, step0)))
+	{
+	  step0 = EXEC_UNARY (NEGATE_EXPR, type, step0);
+	  base1 = fold (build1 (NEGATE_EXPR, type, base1));
+	}
+
+      base1 = convert (niter_type, base1);
+      step0 = convert (niter_type, step0);
+
+      /* Let nsd (s, size of mode) = d.  If d does not divide c, the loop
+	 is infinite.  Otherwise, the number of iterations is
+	 (inverse(s/d) * (c/d)) mod (size of mode/d).  */
+      s = step0;
+      d = integer_one_node;
+      bound = convert (niter_type, build_int_2 (~0, ~0));
+      while (1)
+	{
+	  tmp = EXEC_BINARY (BIT_AND_EXPR, niter_type, s,
+			     convert (niter_type, integer_one_node));
+	  if (integer_nonzerop (tmp))
+	    break;
+	  
+	  s = EXEC_BINARY (RSHIFT_EXPR, niter_type, s,
+			   convert (niter_type, integer_one_node));
+	  d = EXEC_BINARY (LSHIFT_EXPR, niter_type, d,
+			   convert (niter_type, integer_one_node));
+	  bound = EXEC_BINARY (RSHIFT_EXPR, niter_type, bound,
+			       convert (niter_type, integer_one_node));
+	}
+
+      tmp = fold (build (EXACT_DIV_EXPR, niter_type, base1, d));
+      tmp = fold (build (MULT_EXPR, niter_type, tmp, inverse (s, bound)));
+      niter->niter = fold (build (BIT_AND_EXPR, niter_type, tmp, bound));
+    }
+  else
+    {
+      if (zero_p (step1))
+	/* Condition in shape a + s * i <= b
+	   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
+	   seem that we in fact could be more clever about testing the b + s
+	   overflow condition using some information about b - a mod s,
+	   but it was already taken into account during LE -> NE transform).  */
+	{
+	  if (mmax)
+	    {
+	      bound = EXEC_BINARY (MINUS_EXPR, type, mmax, step0);
+	      assumption = fold (build (LE_EXPR, boolean_type_node,
+					base1, bound));
+	      assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+					 assumptions, assumption));
+	    }
+
+	  step = step0;
+	  tmp = fold (build (PLUS_EXPR, type, base1, step0));
+	  assumption = fold (build (GT_EXPR, boolean_type_node, base0, tmp));
+	  delta = fold (build (PLUS_EXPR, type, base1, step));
+	  delta = fold (build (MINUS_EXPR, type, delta, base0));
+	  delta = convert (niter_type, delta);
+	}
+      else
+	{
+	  /* Condition in shape a <= b - s * i
+	     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.  */
+	  if (mmin)
+	    {
+	      bound = EXEC_BINARY (MINUS_EXPR, type, mmin, step1);
+	      assumption = fold (build (LE_EXPR, boolean_type_node,
+					bound, base0));
+	      assumptions = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+					 assumptions, assumption));
+	    }
+	  step = fold (build1 (NEGATE_EXPR, type, step1));
+	  tmp = fold (build (PLUS_EXPR, type, base0, step1));
+	  assumption = fold (build (GT_EXPR, boolean_type_node, tmp, base1));
+	  delta = fold (build (MINUS_EXPR, type, base0, step));
+	  delta = fold (build (MINUS_EXPR, type, base1, delta));
+	  delta = convert (niter_type, delta);
+	}
+      noloop_assumptions = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+					noloop_assumptions, assumption));
+      delta = fold (build (FLOOR_DIV_EXPR, niter_type, delta,
+			   convert (niter_type, step)));
+      niter->niter = delta;
+    }
+
+  niter->assumptions = assumptions;
+  niter->may_be_zero = noloop_assumptions;
+  return;
+
+zero_iter:
+  niter->assumptions = boolean_true_node;
+  niter->may_be_zero = boolean_true_node;
+  niter->niter = convert (type, integer_zero_node);
+  return;
+}
+
+/* Tries to simplify EXPR using the evolutions of the loop invariants
+   in the superloops of LOOP.  Returns the simplified expression
+   (or EXPR unchanged, if no simplification was possible).  */
+
+static tree
+simplify_using_outer_evolutions (struct loop *loop, tree expr)
+{
+  enum tree_code code = TREE_CODE (expr);
+  bool changed;
+  tree e, e0, e1, e2;
+
+  if (is_gimple_min_invariant (expr))
+    return expr;
+
+  if (code == TRUTH_OR_EXPR
+      || code == TRUTH_AND_EXPR
+      || code == COND_EXPR)
+    {
+      changed = false;
+
+      e0 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 0));
+      if (TREE_OPERAND (expr, 0) != e0)
+	changed = true;
+
+      e1 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 1));
+      if (TREE_OPERAND (expr, 1) != e1)
+	changed = true;
+
+      if (code == COND_EXPR)
+	{
+	  e2 = simplify_using_outer_evolutions (loop, TREE_OPERAND (expr, 2));
+	  if (TREE_OPERAND (expr, 2) != e2)
+	    changed = true;
+	}
+      else
+	e2 = NULL_TREE;
+
+      if (changed)
+	{
+	  if (code == COND_EXPR)
+	    expr = build (code, boolean_type_node, e0, e1, e2);
+	  else
+	    expr = build (code, boolean_type_node, e0, e1);
+	  expr = fold (expr);
+	}
+
+      return expr;
+    }
+
+  e = instantiate_parameters (loop, expr);
+  if (is_gimple_min_invariant (e))
+    return e;
+
+  return expr;
+}
+
+/* Tries to simplify EXPR using the condition COND.  Returns the simplified
+   expression (or EXPR unchanged, if no simplification was possible).*/
+
+static tree
+tree_simplify_using_condition (tree cond, tree expr)
+{
+  bool changed;
+  tree e, e0, e1, e2, notcond;
+  enum tree_code code = TREE_CODE (expr);
+
+  if (code == INTEGER_CST)
+    return expr;
+
+  if (code == TRUTH_OR_EXPR
+      || code == TRUTH_AND_EXPR
+      || code == COND_EXPR)
+    {
+      changed = false;
+
+      e0 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 0));
+      if (TREE_OPERAND (expr, 0) != e0)
+	changed = true;
+
+      e1 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 1));
+      if (TREE_OPERAND (expr, 1) != e1)
+	changed = true;
+
+      if (code == COND_EXPR)
+	{
+	  e2 = tree_simplify_using_condition (cond, TREE_OPERAND (expr, 2));
+	  if (TREE_OPERAND (expr, 2) != e2)
+	    changed = true;
+	}
+      else
+	e2 = NULL_TREE;
+
+      if (changed)
+	{
+	  if (code == COND_EXPR)
+	    expr = build (code, boolean_type_node, e0, e1, e2);
+	  else
+	    expr = build (code, boolean_type_node, e0, e1);
+	  expr = fold (expr);
+	}
+
+      return expr;
+    }
+
+  /* Check whether COND ==> EXPR.  */
+  notcond = invert_truthvalue (cond);
+  e = fold (build (TRUTH_OR_EXPR, boolean_type_node,
+		   notcond, expr));
+  if (integer_nonzerop (e))
+    return e;
+
+  /* Check whether COND ==> not EXPR.  */
+  e = fold (build (TRUTH_AND_EXPR, boolean_type_node,
+		   cond, expr));
+  if (integer_zerop (e))
+    return e;
+
+  return expr;
+}
+
+/* Tries to simplify EXPR using the conditions on entry to LOOP.
+   Record the conditions used for simplification to CONDS_USED.
+   Returns the simplified expression (or EXPR unchanged, if no
+   simplification was possible).*/
+
+static tree
+simplify_using_initial_conditions (struct loop *loop, tree expr,
+				   tree *conds_used)
+{
+  edge e;
+  basic_block bb;
+  tree exp, cond;
+
+  if (TREE_CODE (expr) == INTEGER_CST)
+    return expr;
+
+  for (bb = loop->header;
+       bb != ENTRY_BLOCK_PTR;
+       bb = get_immediate_dominator (CDI_DOMINATORS, bb))
+    {
+      e = bb->pred;
+      if (e->pred_next)
+	continue;
+
+      if (!(e->flags & (EDGE_TRUE_VALUE | EDGE_FALSE_VALUE)))
+	continue;
+
+      cond = COND_EXPR_COND (last_stmt (e->src));
+      if (e->flags & EDGE_FALSE_VALUE)
+	cond = invert_truthvalue (cond);
+      exp = tree_simplify_using_condition (cond, expr);
+
+      if (exp != expr)
+	*conds_used = fold (build (TRUTH_AND_EXPR,
+				   boolean_type_node,
+				   *conds_used,
+				   cond));
+
+      expr = exp;
+    }
+
+  return expr;
+}
+
+/* Stores description of number of iterations of LOOP derived from
+   EXIT (an exit edge of the LOOP) in NITER.  Returns true if some
+   useful information could be derived (and fields of NITER has
+   meaning described in comments at struct tree_niter_desc
+   declaration), false otherwise.  */
+
+bool
+number_of_iterations_exit (struct loop *loop, edge exit,
+			   struct tree_niter_desc *niter)
+{
+  tree stmt, cond, type;
+  tree op0, base0, step0;
+  tree op1, base1, step1;
+  enum tree_code code;
+
+  if (!dominated_by_p (CDI_DOMINATORS, loop->latch, exit->src))
+    return false;
+
+  niter->assumptions = boolean_false_node;
+  stmt = last_stmt (exit->src);
+  if (!stmt || TREE_CODE (stmt) != COND_EXPR)
+    return false;
+
+  /* We want the condition for staying inside loop.  */
+  cond = COND_EXPR_COND (stmt);
+  if (exit->flags & EDGE_TRUE_VALUE)
+    cond = invert_truthvalue (cond);
+
+  code = TREE_CODE (cond);
+  switch (code)
+    {
+    case GT_EXPR:
+    case GE_EXPR:
+    case NE_EXPR:
+    case LT_EXPR:
+    case LE_EXPR:
+      break;
+
+    default:
+      return false;
+    }
+  
+  op0 = TREE_OPERAND (cond, 0);
+  op1 = TREE_OPERAND (cond, 1);
+  type = TREE_TYPE (op0);
+
+  if (TREE_CODE (type) != INTEGER_TYPE
+    && TREE_CODE (type) != POINTER_TYPE)
+    return false;
+     
+  if (!simple_iv (loop, stmt, op0, &base0, &step0))
+    return false;
+  if (!simple_iv (loop, stmt, op1, &base1, &step1))
+    return false;
+
+  niter->niter = NULL_TREE;
+  number_of_iterations_cond (type, base0, step0, code, base1, step1,
+			     niter);
+  if (!niter->niter)
+    return false;
+
+  niter->assumptions = simplify_using_outer_evolutions (loop,
+							niter->assumptions);
+  niter->may_be_zero = simplify_using_outer_evolutions (loop,
+							niter->may_be_zero);
+  niter->niter = simplify_using_outer_evolutions (loop, niter->niter);
+
+  niter->additional_info = boolean_true_node;
+  niter->assumptions
+	  = simplify_using_initial_conditions (loop,
+					       niter->assumptions,
+					       &niter->additional_info);
+  niter->may_be_zero
+	  = simplify_using_initial_conditions (loop,
+					       niter->may_be_zero,
+					       &niter->additional_info);
+  return integer_onep (niter->assumptions);
+}
+
+/*
+
+   Analysis of a number of iterations of a loop by a brute-force evaluation.
+
+*/
+
+/* Bound on the number of iterations we try to evaluate.  */
+
+#define MAX_ITERATIONS_TO_TRACK \
+  ((unsigned) PARAM_VALUE (PARAM_MAX_ITERATIONS_TO_TRACK))
+
+/* Returns the loop phi node of LOOP such that ssa name X is derived from its
+   result by a chain of operations such that all but exactly one of their
+   operands are constants.  */
+
+static tree
+chain_of_csts_start (struct loop *loop, tree x)
+{
+  tree stmt = SSA_NAME_DEF_STMT (x);
+  basic_block bb = bb_for_stmt (stmt);
+  use_optype uses;
+
+  if (!bb
+      || !flow_bb_inside_loop_p (loop, bb))
+    return NULL_TREE;
+  
+  if (TREE_CODE (stmt) == PHI_NODE)
+    {
+      if (bb == loop->header)
+	return stmt;
+
+      return NULL_TREE;
+    }
+
+  if (TREE_CODE (stmt) != MODIFY_EXPR)
+    return NULL_TREE;
+
+  get_stmt_operands (stmt);
+  if (NUM_VUSES (STMT_VUSE_OPS (stmt)) > 0)
+    return NULL_TREE;
+  if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0)
+    return NULL_TREE;
+  if (NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
+    return NULL_TREE;
+  if (NUM_DEFS (STMT_DEF_OPS (stmt)) > 1)
+    return NULL_TREE;
+  uses = STMT_USE_OPS (stmt);
+  if (NUM_USES (uses) != 1)
+    return NULL_TREE;
+
+  return chain_of_csts_start (loop, USE_OP (uses, 0));
+}
+
+/* Determines whether the expression X is derived from a result of a phi node
+   in header of LOOP such that
+
+   * the derivation of X consists only from operations with constants
+   * the initial value of the phi node is constant
+   * the value of the phi node in the next iteration can be derived from the
+     value in the current iteration by a chain of operations with constants.
+   
+   If such phi node exists, it is returned.  If X is a constant, X is returned
+   unchanged.  Otherwise NULL_TREE is returned.  */
+
+static tree
+get_base_for (struct loop *loop, tree x)
+{
+  tree phi, init, next;
+
+  if (is_gimple_min_invariant (x))
+    return x;
+
+  phi = chain_of_csts_start (loop, x);
+  if (!phi)
+    return NULL_TREE;
+
+  init = PHI_ARG_DEF_FROM_EDGE (phi, loop_preheader_edge (loop));
+  next = PHI_ARG_DEF_FROM_EDGE (phi, loop_latch_edge (loop));
+
+  if (TREE_CODE (next) != SSA_NAME)
+    return NULL_TREE;
+
+  if (!is_gimple_min_invariant (init))
+    return NULL_TREE;
+
+  if (chain_of_csts_start (loop, next) != phi)
+    return NULL_TREE;
+
+  return phi;
+}
+
+/* Given an expression X, then 
+ 
+   * if BASE is NULL_TREE, X must be a constant and we return X.
+   * otherwise X is a SSA name, whose value in the considered loop is derived
+     by a chain of operations with constant from a result of a phi node in
+     the header of the loop.  Then we return value of X when the value of the
+     result of this phi node is given by the constant BASE.  */
+
+static tree
+get_val_for (tree x, tree base)
+{
+  tree stmt, nx, val;
+  use_optype uses;
+  use_operand_p op;
+
+  if (!x)
+    return base;
+
+  stmt = SSA_NAME_DEF_STMT (x);
+  if (TREE_CODE (stmt) == PHI_NODE)
+    return base;
+
+  uses = STMT_USE_OPS (stmt);
+  op = USE_OP_PTR (uses, 0);
+
+  nx = USE_FROM_PTR (op);
+  val = get_val_for (nx, base);
+  SET_USE (op, val);
+  val = fold (TREE_OPERAND (stmt, 1));
+  SET_USE (op, nx);
+
+  return val;
+}
+
+/* Tries to count the number of iterations of LOOP till it exits by EXIT
+   by brute force -- i.e. by determining the value of the operands of the
+   condition at EXIT in first few iterations of the loop (assuming that
+   these values are constant) and determining the first one in that the
+   condition is not satisfied.  Returns the constant giving the number
+   of the iterations of LOOP if successful, chrec_dont_know otherwise.  */
+
+tree
+loop_niter_by_eval (struct loop *loop, edge exit)
+{
+  tree cond, cnd, acnd;
+  tree op[2], val[2], next[2], aval[2], phi[2];
+  unsigned i, j;
+  enum tree_code cmp;
+
+  cond = last_stmt (exit->src);
+  if (!cond || TREE_CODE (cond) != COND_EXPR)
+    return chrec_dont_know;
+
+  cnd = COND_EXPR_COND (cond);
+  if (exit->flags & EDGE_TRUE_VALUE)
+    cnd = invert_truthvalue (cnd);
+
+  cmp = TREE_CODE (cnd);
+  switch (cmp)
+    {
+    case EQ_EXPR:
+    case NE_EXPR:
+    case GT_EXPR:
+    case GE_EXPR:
+    case LT_EXPR:
+    case LE_EXPR:
+      for (j = 0; j < 2; j++)
+	op[j] = TREE_OPERAND (cnd, j);
+      break;
+
+    default:
+      return chrec_dont_know;
+    }
+
+  for (j = 0; j < 2; j++)
+    {
+      phi[j] = get_base_for (loop, op[j]);
+      if (!phi[j])
+	return chrec_dont_know;
+    }
+
+  for (j = 0; j < 2; j++)
+    {
+      if (TREE_CODE (phi[j]) == PHI_NODE)
+	{
+	  val[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_preheader_edge (loop));
+	  next[j] = PHI_ARG_DEF_FROM_EDGE (phi[j], loop_latch_edge (loop));
+	}
+      else
+	{
+	  val[j] = phi[j];
+	  next[j] = NULL_TREE;
+	  op[j] = NULL_TREE;
+	}
+    }
+
+  for (i = 0; i < MAX_ITERATIONS_TO_TRACK; i++)
+    {
+      for (j = 0; j < 2; j++)
+	aval[j] = get_val_for (op[j], val[j]);
+
+      acnd = fold (build (cmp, boolean_type_node, aval[0], aval[1]));
+      if (integer_zerop (acnd))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file,
+		     "Proved that loop %d iterates %d times using brute force.\n",
+		     loop->num, i);
+	  return build_int_2 (i, 0);
+	}
+
+      for (j = 0; j < 2; j++)
+	val[j] = get_val_for (next[j], val[j]);
+    }
+
+  return chrec_dont_know;
+}
+
+/* Finds the exit of the LOOP by that the loop exits after a constant
+   number of iterations and stores the exit edge to *EXIT.  The constant
+   giving the number of iterations of LOOP is returned.  The number of
+   iterations is determined using loop_niter_by_eval (i.e. by brute force
+   evaluation).  If we are unable to find the exit for that loop_niter_by_eval
+   determines the number of iterations, chrec_dont_know is returned.  */
+
+tree
+find_loop_niter_by_eval (struct loop *loop, edge *exit)
+{
+  unsigned n_exits, i;
+  edge *exits = get_loop_exit_edges (loop, &n_exits);
+  edge ex;
+  tree niter = NULL_TREE, aniter;
+
+  *exit = NULL;
+  for (i = 0; i < n_exits; i++)
+    {
+      ex = exits[i];
+      if (!just_once_each_iteration_p (loop, ex->src))
+	continue;
+
+      aniter = loop_niter_by_eval (loop, ex);
+      if (chrec_contains_undetermined (aniter)
+	  || TREE_CODE (aniter) != INTEGER_CST)
+	continue;
+
+      if (niter
+	  && !integer_nonzerop (fold (build (LT_EXPR, boolean_type_node,
+					     aniter, niter))))
+	continue;
+
+      niter = aniter;
+      *exit = ex;
+    }
+  free (exits);
+
+  return niter ? niter : chrec_dont_know;
+}
+
+/*
+
+   Analysis of upper bounds on number of iterations of a loop.
+
+*/
+
+/* The structure describing a bound on number of iterations of a loop.  */
+
+struct nb_iter_bound
+{
+  tree bound;		/* The expression whose value is an upper bound on the
+			   number of executions of anything after ...  */
+  tree at_stmt;		/* ... this statement during one execution of loop.  */
+  tree additional;	/* A conjunction of conditions the operands of BOUND
+			   satisfy.  The additional information about the value
+			   of the bound may be derived from it.  */
+  struct nb_iter_bound *next;
+			/* The next bound in a list.  */
+};
+
+/* Records that AT_STMT is executed at most BOUND times in LOOP.  The
+   additional condition ADDITIONAL is recorded with the bound.  */
+
+static void
+record_estimate (struct loop *loop, tree bound, tree additional, tree at_stmt)
+{
+  struct nb_iter_bound *elt = xmalloc (sizeof (struct nb_iter_bound));
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Statements after ");
+      print_generic_expr (dump_file, at_stmt, TDF_SLIM);
+      fprintf (dump_file, " are executed at most ");
+      print_generic_expr (dump_file, bound, TDF_SLIM);
+      fprintf (dump_file, " times in loop %d.\n", loop->num);
+    }
+
+  elt->bound = bound;
+  elt->at_stmt = at_stmt;
+  elt->additional = additional;
+  elt->next = loop->bounds;
+  loop->bounds = elt;
+}
+
+/* Records estimates on numbers of iterations of LOOP.  */
+
+static void
+estimate_numbers_of_iterations_loop (struct loop *loop)
+{
+  edge *exits;
+  tree niter, type;
+  unsigned i, n_exits;
+  struct tree_niter_desc niter_desc;
+
+  exits = get_loop_exit_edges (loop, &n_exits);
+  for (i = 0; i < n_exits; i++)
+    {
+      if (!number_of_iterations_exit (loop, exits[i], &niter_desc))
+	continue;
+
+      niter = niter_desc.niter;
+      type = TREE_TYPE (niter);
+      if (!integer_zerop (niter_desc.may_be_zero)
+	  && !integer_nonzerop (niter_desc.may_be_zero))
+	niter = build (COND_EXPR, type, niter_desc.may_be_zero,
+		       convert (type, integer_zero_node),
+		       niter);
+      record_estimate (loop, niter,
+		       niter_desc.additional_info,
+		       last_stmt (exits[i]->src));
+    }
+  free (exits);
+  
+  /* TODO Here we could use other possibilities, like bounds of arrays accessed
+     in the loop.  */
+}
+
+/* Records estimates on numbers of iterations of LOOPS.  */
+
+void
+estimate_numbers_of_iterations (struct loops *loops)
+{
+  unsigned i;
+  struct loop *loop;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (loop)
+	estimate_numbers_of_iterations_loop (loop);
+    }
+}
+
+/* If A > B, returns -1.  If A == B, returns 0.  If A < B, returns 1.
+   If neither of these relations can be proved, returns 2.  */
+
+static int
+compare_trees (tree a, tree b)
+{
+  tree typea = TREE_TYPE (a), typeb = TREE_TYPE (b);
+  tree type;
+
+  if (TYPE_PRECISION (typea) > TYPE_PRECISION (typeb))
+    type = typea;
+  else
+    type = typeb;
+
+  a = convert (type, a);
+  b = convert (type, b);
+
+  if (integer_nonzerop (fold (build (EQ_EXPR, boolean_type_node, a, b))))
+    return 0;
+  if (integer_nonzerop (fold (build (LT_EXPR, boolean_type_node, a, b))))
+    return 1;
+  if (integer_nonzerop (fold (build (GT_EXPR, boolean_type_node, a, b))))
+    return -1;
+
+  return 2;
+}
+
+/* Returns the largest value obtainable by casting something in INNER type to
+   OUTER type.  */
+
+tree
+upper_bound_in_type (tree outer, tree inner)
+{
+  unsigned HOST_WIDE_INT lo, hi;
+  unsigned bits = TYPE_PRECISION (inner);
+
+  if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
+    {
+      /* Zero extending in these cases.  */
+      if (bits <= HOST_BITS_PER_WIDE_INT)
+	{
+	  hi = 0;
+	  lo = (~(unsigned HOST_WIDE_INT) 0)
+		  >> (HOST_BITS_PER_WIDE_INT - bits);
+	}
+      else
+	{
+	  hi = (~(unsigned HOST_WIDE_INT) 0)
+		  >> (2 * HOST_BITS_PER_WIDE_INT - bits);
+	  lo = ~(unsigned HOST_WIDE_INT) 0;
+	}
+    }
+  else
+    {
+      /* Sign extending in these cases.  */
+      if (bits <= HOST_BITS_PER_WIDE_INT)
+	{
+	  hi = 0;
+	  lo = (~(unsigned HOST_WIDE_INT) 0)
+		  >> (HOST_BITS_PER_WIDE_INT - bits) >> 1;
+	}
+      else
+	{
+	  hi = (~(unsigned HOST_WIDE_INT) 0)
+		  >> (2 * HOST_BITS_PER_WIDE_INT - bits) >> 1;
+	  lo = ~(unsigned HOST_WIDE_INT) 0;
+	}
+    }
+
+  return convert (outer,
+		  convert (inner,
+			   build_int_2 (lo, hi)));
+}
+
+/* Returns the smallest value obtainable by casting something in INNER type to
+   OUTER type.  */
+
+tree
+lower_bound_in_type (tree outer, tree inner)
+{
+  unsigned HOST_WIDE_INT lo, hi;
+  unsigned bits = TYPE_PRECISION (inner);
+
+  if (TYPE_UNSIGNED (outer) || TYPE_UNSIGNED (inner))
+    lo = hi = 0;
+  else if (bits <= HOST_BITS_PER_WIDE_INT)
+    {
+      hi = ~(unsigned HOST_WIDE_INT) 0;
+      lo = (~(unsigned HOST_WIDE_INT) 0) << (bits - 1);
+    }
+  else
+    {
+      hi = (~(unsigned HOST_WIDE_INT) 0) << (bits - HOST_BITS_PER_WIDE_INT - 1);
+      lo = 0;
+    }
+
+  return convert (outer,
+		  convert (inner,
+			   build_int_2 (lo, hi)));
+}
+
+/* Returns true if statement S1 dominates statement S2.  */
+
+static bool
+stmt_dominates_stmt_p (tree s1, tree s2)
+{
+  basic_block bb1 = bb_for_stmt (s1), bb2 = bb_for_stmt (s2);
+
+  if (!bb1
+      || s1 == s2)
+    return true;
+
+  if (bb1 == bb2)
+    {
+      block_stmt_iterator bsi;
+
+      for (bsi = bsi_start (bb1); bsi_stmt (bsi) != s2; bsi_next (&bsi))
+	if (bsi_stmt (bsi) == s1)
+	  return true;
+
+      return false;
+    }
+
+  return dominated_by_p (CDI_DOMINATORS, bb2, bb1);
+}
+
+/* Checks whether it is correct to count the induction variable BASE + STEP * I
+   at AT_STMT in wider TYPE, using the fact that statement OF is executed at
+   most BOUND times in the loop.  If it is possible, return the value of step
+   of the induction variable in the TYPE, otherwise return NULL_TREE.
+   
+   ADDITIONAL is the additional condition recorded for operands of the bound.
+   This is useful in the following case, created by loop header copying:
+
+   i = 0;
+   if (n > 0)
+     do
+       {
+         something;
+       } while (++i < n)
+
+   If the n > 0 condition is taken into account, the number of iterations of the
+   loop can be expressed as n - 1.  If the type of n is signed, the ADDITIONAL
+   assumption "n > 0" says us that the value of the number of iterations is at
+   most MAX_TYPE - 1 (without this assumption, it might overflow).  */
+
+static tree
+can_count_iv_in_wider_type_bound (tree type, tree base, tree step,
+				  tree at_stmt,
+				  tree bound,
+				  tree additional,
+				  tree of)
+{
+  tree inner_type = TREE_TYPE (base), b, bplusstep, new_step, new_step_abs;
+  tree valid_niter, extreme, unsigned_type, delta, bound_type;
+  tree cond;
+
+  b = convert (type, base);
+  bplusstep = convert (type,
+		       fold (build (PLUS_EXPR, inner_type, base, step)));
+  new_step = fold (build (MINUS_EXPR, type, bplusstep, b));
+  if (TREE_CODE (new_step) != INTEGER_CST)
+    return NULL_TREE;
+
+  switch (compare_trees (bplusstep, b))
+    {
+    case -1:
+      extreme = upper_bound_in_type (type, inner_type);
+      delta = fold (build (MINUS_EXPR, type, extreme, b));
+      new_step_abs = new_step;
+      break;
+
+    case 1:
+      extreme = lower_bound_in_type (type, inner_type);
+      new_step_abs = fold (build (NEGATE_EXPR, type, new_step));
+      delta = fold (build (MINUS_EXPR, type, b, extreme));
+      break;
+
+    case 0:
+      return new_step;
+
+    default:
+      return NULL_TREE;
+    }
+
+  unsigned_type = unsigned_type_for (type);
+  delta = convert (unsigned_type, delta);
+  new_step_abs = convert (unsigned_type, new_step_abs);
+  valid_niter = fold (build (FLOOR_DIV_EXPR, unsigned_type,
+			     delta, new_step_abs));
+
+  bound_type = TREE_TYPE (bound);
+  if (TYPE_PRECISION (type) > TYPE_PRECISION (bound_type))
+    bound = convert (unsigned_type, bound);
+  else
+    valid_niter = convert (bound_type, valid_niter);
+    
+  if (at_stmt && stmt_dominates_stmt_p (of, at_stmt))
+    {
+      /* After the statement OF we know that anything is executed at most
+	 BOUND times.  */
+      cond = build (GE_EXPR, boolean_type_node, valid_niter, bound);
+    }
+  else
+    {
+      /* Before the statement OF we know that anything is executed at most
+	 BOUND + 1 times.  */
+      cond = build (GT_EXPR, boolean_type_node, valid_niter, bound);
+    }
+
+  cond = fold (cond);
+  if (integer_nonzerop (cond))
+    return new_step;
+
+  /* Try taking additional conditions into account.  */
+  cond = build (TRUTH_OR_EXPR, boolean_type_node,
+		invert_truthvalue (additional),
+		cond);
+  cond = fold (cond);
+  if (integer_nonzerop (cond))
+    return new_step;
+
+  return NULL_TREE;
+}
+
+/* Checks whether it is correct to count the induction variable BASE + STEP * I
+   at AT_STMT in wider TYPE, using the bounds on numbers of iterations of a
+   LOOP.  If it is possible, return the value of step of the induction variable
+   in the TYPE, otherwise return NULL_TREE.  */
+
+tree
+can_count_iv_in_wider_type (struct loop *loop, tree type, tree base, tree step,
+			    tree at_stmt)
+{
+  struct nb_iter_bound *bound;
+  tree new_step;
+
+  for (bound = loop->bounds; bound; bound = bound->next)
+    {
+      new_step = can_count_iv_in_wider_type_bound (type, base, step,
+						   at_stmt,
+						   bound->bound,
+						   bound->additional,
+						   bound->at_stmt);
+
+      if (new_step)
+	return new_step;
+    }
+
+  return NULL_TREE;
+}
+
+/* Frees the information on upper bounds on numbers of iterations of LOOP.  */
+
+static void
+free_numbers_of_iterations_estimates_loop (struct loop *loop)
+{
+  struct nb_iter_bound *bound, *next;
+  
+  for (bound = loop->bounds; bound; bound = next)
+    {
+      next = bound->next;
+      free (bound);
+    }
+
+  loop->bounds = NULL;
+}
+
+/* Frees the information on upper bounds on numbers of iterations of LOOPS.  */
+
+void
+free_numbers_of_iterations_estimates (struct loops *loops)
+{
+  unsigned i;
+  struct loop *loop;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (loop)
+	free_numbers_of_iterations_estimates_loop (loop);
+    }
+}
diff --git a/gcc/tree.h b/gcc/tree.h
index af3d1d5..ac13f12 100644
--- a/gcc/tree.h
+++ b/gcc/tree.h
@@ -3754,4 +3754,9 @@ extern int tree_node_sizes[];
    restricted to creating gimple expressions.  */
 extern bool in_gimple_form;
     
+/* In tree-ssa-loop-niter.c.  */
+
+tree lower_bound_in_type (tree, tree);
+tree upper_bound_in_type (tree, tree);
+
 #endif  /* GCC_TREE_H  */