* Makefile.in (tree-ssa-loop-endcond.o): Add TREE_DATA_REF_H and

	LAMBDA_H dependency.
	* common.opt (freverse-loops): New flag.
	* passes.c (init_optimization_passes): Add pass_loop_reversal.
	* timevar.def (TV_TREE_LOOP_REVERSE): New timevar.
	* tree-pass.h (pass_loop_reversal): Declare.
	* tree-ssa-loop-endcond.c: Include tree-data-ref.h and lambda.h.
	(final_value_of_iv, may_reverse_loop_p, endcond_candidate_cost,
	best_endcond_candidate_cost, num_of_forward_traversals,
	profitable_to_reverse_loop_p, reverse_biv, replace_exit_condition,
	reverse_loop, loop_reversal, tree_ssa_reverse_loops): New functions.
	(select_condition_shape): Use final_value_of_iv.
	(compare_cost): Moved from tree-ssa-loop-ivopts.c.
	* tree-ssa-loop-ivopts.c (compare_cost): Moved to
	tree-ssa-loop-endcond.c.
	* tree-ssa-loop.c (tree_ssa_loop_reversal,
	* gate_tree_ssa_loop_reversal, pass_loop_reversal): New.
	* doc/invoke.texi (-freverse-loops): Document.
	* doc/passes.texi: Document loop reversal, tree-affine.c and
	tree-ssa-loop-endcond.c.

	* testsuite/gcc.dg/20050105-1.c: Do not pass -floop-optimize2.
	* testsuite/gcc.dg/tree-ssa/loop-12.c: New test.


git-svn-id: https://gcc.gnu.org/svn/gcc/branches/killloop-branch@104420 138bc75d-0d04-0410-961f-82ee72b054a4

13 files changed, 579 insertions, 22 deletions

diff --git a/gcc/ChangeLog.killloop b/gcc/ChangeLog.killloop
index b84a40070f2..87a9e5cca88 100644
--- a/gcc/ChangeLog.killloop
+++ b/gcc/ChangeLog.killloop
@@ -1,3 +1,29 @@
+2005-09-19  Zdenek Dvorak  <dvorakz@suse.cz>
+
+	* Makefile.in (tree-ssa-loop-endcond.o): Add TREE_DATA_REF_H and
+	LAMBDA_H dependency.
+	* common.opt (freverse-loops): New flag.
+	* passes.c (init_optimization_passes): Add pass_loop_reversal.
+	* timevar.def (TV_TREE_LOOP_REVERSE): New timevar.
+	* tree-pass.h (pass_loop_reversal): Declare.
+	* tree-ssa-loop-endcond.c: Include tree-data-ref.h and lambda.h.
+	(final_value_of_iv, may_reverse_loop_p, endcond_candidate_cost,
+	best_endcond_candidate_cost, num_of_forward_traversals,
+	profitable_to_reverse_loop_p, reverse_biv, replace_exit_condition,
+	reverse_loop, loop_reversal, tree_ssa_reverse_loops): New functions.
+	(select_condition_shape): Use final_value_of_iv.
+	(compare_cost): Moved from tree-ssa-loop-ivopts.c.
+	* tree-ssa-loop-ivopts.c (compare_cost): Moved to
+	tree-ssa-loop-endcond.c.
+	* tree-ssa-loop.c (tree_ssa_loop_reversal,
+	* gate_tree_ssa_loop_reversal, pass_loop_reversal): New.
+	* doc/invoke.texi (-freverse-loops): Document.
+	* doc/passes.texi: Document loop reversal, tree-affine.c and
+	tree-ssa-loop-endcond.c.
+
+	* testsuite/gcc.dg/20050105-1.c: Do not pass -floop-optimize2.
+	* testsuite/gcc.dg/tree-ssa/loop-12.c: New test.
+
 2005-09-15  Zdenek Dvorak  <dvorakz@suse.cz>
 
 	* tree-data-ref.c (analyze_array, analyze_indirect_ref, init_data_ref,
diff --git a/gcc/Makefile.in b/gcc/Makefile.in
index 1decc0f3a17..ebc3abf38ab 100644
--- a/gcc/Makefile.in
+++ b/gcc/Makefile.in
@@ -1907,7 +1907,7 @@ tree-ssa-loop-endcond.o : tree-ssa-loop-endcond.c $(TREE_FLOW_H) $(CONFIG_H) \
    output.h $(DIAGNOSTIC_H) $(TIMEVAR_H) $(TM_H) coretypes.h $(TREE_DUMP_H) \
    tree-pass.h $(GGC_H) $(RECOG_H) insn-config.h $(HASHTAB_H) $(SCEV_H) \
    $(CFGLOOP_H) $(PARAMS_H) langhooks.h $(BASIC_BLOCK_H) hard-reg-set.h \
-   tree-chrec.h $(VARRAY_H)
+   tree-chrec.h $(VARRAY_H) $(TREE_DATA_REF_H) $(LAMBDA_H)
 tree-affine.o : tree-affine.c tree-affine.h $(CONFIG_H) \
    $(SYSTEM_H) $(RTL_H) $(TREE_H) $(TM_P_H) \
    output.h $(DIAGNOSTIC_H) $(TM_H) coretypes.h $(TREE_DUMP_H)
diff --git a/gcc/common.opt b/gcc/common.opt
index 002d837ccaa..eb2d68b51fc 100644
--- a/gcc/common.opt
+++ b/gcc/common.opt
@@ -709,6 +709,10 @@ frerun-loop-opt
 Common Report Var(flag_rerun_loop_opt)
 Run the loop optimizer twice
 
+freverse-loops
+Common Report Var(flag_loop_reversal) Init(0)
+Reverse loops when profittable.
+
 frounding-math
 Common Report Var(flag_rounding_math)
 Disable optimizations that assume default FP rounding behavior
diff --git a/gcc/doc/invoke.texi b/gcc/doc/invoke.texi
index d52e6ec49a6..018068e421e 100644
--- a/gcc/doc/invoke.texi
+++ b/gcc/doc/invoke.texi
@@ -337,7 +337,7 @@ Objective-C and Objective-C++ Dialects}.
 -ftree-loop-linear -ftree-loop-im -ftree-loop-ivcanon -fivopts @gol
 -ftree-dominator-opts -ftree-dse -ftree-copyrename -ftree-sink @gol
 -ftree-ch -ftree-sra -ftree-ter -ftree-lrs -ftree-fre -ftree-vectorize @gol
--ftree-salias -fweb @gol
+-ftree-salias -fweb -freverse-loops @gol
 -ftree-copy-prop -ftree-store-ccp -ftree-store-copy-prop -fwhole-program @gol
 --param @var{name}=@var{value}
 -O  -O0  -O1  -O2  -O3  -Os}
@@ -5002,6 +5002,11 @@ determining number of iterations requires complicated analysis.  Later
 optimizations then may determine the number easily.  Useful especially
 in connection with unrolling.
 
+@item -freverse-loops
+Reverse loops if it is profitable, i.e., enables the exit test of the
+loop to be a compare with zero or other constant, without need to
+introduce a new induction variable.
+
 @item -fivopts
 Perform induction variable optimizations (strength reduction, induction
 variable merging and induction variable elimination) on trees.
diff --git a/gcc/doc/passes.texi b/gcc/doc/passes.texi
index e2fcc7a5d02..a10eab50118 100644
--- a/gcc/doc/passes.texi
+++ b/gcc/doc/passes.texi
@@ -388,10 +388,18 @@ loop using it, in case when a complicated analysis is necessary to determine
 the number of iterations.  Later optimizations then may determine the number
 easily.  The pass is implemented in @file{tree-ssa-loop-ivcanon.c}.
 
+Loop reversal.  This pass revereses loops if it is profitable, i.e, when
+this enables the exit test of the loop to be a compare with zero or other
+constant, without need to introduce a new induction variable, and this
+was not possible for the original loop.  This pass is implemented in
+@file{tree-ssa-loop-endcond.c}.
+
 Induction variable optimizations.  This pass performs standard induction
 variable optimizations, including strength reduction, induction variable
 merging and induction variable elimination.  The pass is implemented in
-@file{tree-ssa-loop-ivopts.c}.
+@file{tree-ssa-loop-ivopts.c}, and uses utility functions implemented in
+@file{tree-ssa-address.c}, @file{tree-affine.c} and
+@file{tree-ssa-loop-endcond.c}.
 
 Loop unswitching.  This pass moves the conditional jumps that are invariant
 out of the loops.  To achieve this, a duplicate of the loop is created for
diff --git a/gcc/passes.c b/gcc/passes.c
index 83873d737e5..cc8286d3e60 100644
--- a/gcc/passes.c
+++ b/gcc/passes.c
@@ -573,6 +573,7 @@ init_optimization_passes (void)
      pass_may_alias.  */
   NEXT_PASS (pass_lower_vector_ssa);
   NEXT_PASS (pass_complete_unroll);
+  NEXT_PASS (pass_loop_reversal);
   NEXT_PASS (pass_loop_prefetch);
   NEXT_PASS (pass_iv_optimize);
   NEXT_PASS (pass_tree_loop_done);
diff --git a/gcc/testsuite/gcc.dg/20050105-1.c b/gcc/testsuite/gcc.dg/20050105-1.c
index 46a742ffe63..58a75150bdb 100644
--- a/gcc/testsuite/gcc.dg/20050105-1.c
+++ b/gcc/testsuite/gcc.dg/20050105-1.c
@@ -1,6 +1,6 @@
 /* PR rtl-optimization/18861 */
 /* { dg-do compile } */
-/* { dg-options "-O2 -floop-optimize2" } */
+/* { dg-options "-O2" } */
 
 extern void abort (void);
 
diff --git a/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c b/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c
new file mode 100644
index 00000000000..3fe6ac206f5
--- /dev/null
+++ b/gcc/testsuite/gcc.dg/tree-ssa/loop-12.c
@@ -0,0 +1,112 @@
+/* A test for loop reversal.  */
+
+/* { dg-do compile } */
+/* { dg-options "-O2 -freverse-loops -fdump-tree-revloops-details" } */
+
+int a[1000], b[1000];
+
+void bar(void);
+void bla(int);
+
+void foo1 (int n)
+{
+  int i;
+
+  /* This loop can be reversed, but there is no reason for doing it.  */
+  for (i = 0; i < n; i++)
+    a[i] = b[n - i - 1];
+}
+
+void foo2 (int n)
+{
+  int i;
+
+  /* This loop can be reversed, and we get a better code if we do it
+     (but the array is traversed backwards -- this test may need some
+     tweaking if some architecture defines PREFER_PASSING_MEMORY_FORWARDS).  */
+  for (i = 0; i < n; i++)
+    a[i] = b[i];
+}
+
+void foo3 (int n)
+{
+  int i;
+
+  /* This loop can be reversed, but would make things worse.  */
+  for (i = 0; i < n; i++)
+    a[n - i - 1] = n - i;
+}
+
+void foo4 (int n)
+{
+  int i;
+
+  /* This loop can be reversed, but it it is doubtful whether it is
+     profitable.  */
+  for (i = 0; i < n; i++)
+    a[n - i - 1] = i;
+}
+
+void foo4a (int n)
+{
+  int i;
+
+  /* This loop can be reversed, and it is profitable.  */
+  for (i = 1000; i > n; i--)
+    a[i] = i;
+}
+
+/* The following three loops cannot be reversed.  */
+void foo5 (int n)
+{
+  int i;
+
+  for (i = 0; i < n; i++)
+    a[i + 1] = a[i];
+}
+
+void foo6 (int n)
+{
+  int i;
+
+  for (i = 0; i < n; i++)
+    a[i] = a[i + 1];
+}
+
+void foo7 (int n)
+{
+  int i;
+
+  for (i = 0; i < n; i++)
+    bla(i);
+}
+
+void foo8 (int n)
+{
+  int i;
+
+  /* The following loop can be reversed, but we fail to detect it.
+     Nevertheless, reversing it is not useful anyway, we may just
+     create a countdown iv.  */
+  for (i = 0; i < n; i++)
+    bar ();
+}
+
+void foo9 (int n)
+{
+  int i;
+
+  /* The following loop cannot be reversed.  */
+  for (i = 0; i < 100; i++)
+    {
+      a[7] = i;
+      a[10] = i;
+      b[i] = i;
+    }
+}
+
+/* { dg-final { scan-tree-dump-times "SUCCESS: may be reversed" 5 "revloops" } } */
+/* { dg-final { scan-tree-dump-times "SUCCESS: profitable to reverse" 2 "revloops" } } */
+/* { dg-final { scan-tree-dump-times "FAILED: dependence check failed" 5 "revloops" } } */
+
+/* { dg-final { cleanup-tree-dump "revloops" } } */
diff --git a/gcc/timevar.def b/gcc/timevar.def
index 27dc698b606..57811c0c62a 100644
--- a/gcc/timevar.def
+++ b/gcc/timevar.def
@@ -108,6 +108,7 @@ DEFTIMEVAR (TV_TREE_VECTORIZATION    , "tree vectorization")
 DEFTIMEVAR (TV_TREE_LINEAR_TRANSFORM , "tree loop linear")
 DEFTIMEVAR (TV_TREE_PREFETCH	     , "tree prefetching")
 DEFTIMEVAR (TV_TREE_LOOP_IVOPTS	     , "tree iv optimization")
+DEFTIMEVAR (TV_TREE_LOOP_REVERSE     , "tree loop reversal")
 DEFTIMEVAR (TV_TREE_LOOP_INIT	     , "tree loop init")
 DEFTIMEVAR (TV_TREE_LOOP_FINI	     , "tree loop fini")
 DEFTIMEVAR (TV_TREE_CH		     , "tree copy headers")
diff --git a/gcc/tree-pass.h b/gcc/tree-pass.h
index 93717ee4344..c9b19849e67 100644
--- a/gcc/tree-pass.h
+++ b/gcc/tree-pass.h
@@ -237,6 +237,7 @@ extern struct tree_opt_pass pass_record_bounds;
 extern struct tree_opt_pass pass_if_conversion;
 extern struct tree_opt_pass pass_vectorize;
 extern struct tree_opt_pass pass_complete_unroll;
+extern struct tree_opt_pass pass_loop_reversal;
 extern struct tree_opt_pass pass_loop_prefetch;
 extern struct tree_opt_pass pass_iv_optimize;
 extern struct tree_opt_pass pass_tree_loop_done;
diff --git a/gcc/tree-ssa-loop-endcond.c b/gcc/tree-ssa-loop-endcond.c
index 86dce7a4a62..953f267cfb1 100644
--- a/gcc/tree-ssa-loop-endcond.c
+++ b/gcc/tree-ssa-loop-endcond.c
@@ -80,6 +80,8 @@ Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
 #include "cfgloop.h"
 #include "params.h"
 #include "langhooks.h"
+#include "tree-data-ref.h"
+#include "lambda.h"
 
 /* Returns period of induction variable with step STEP.  */
 
@@ -198,6 +200,19 @@ may_wrap_around_type_range_p (tree niter, tree step)
   return !nonzero_p (fold_build2 (LE_EXPR, boolean_type_node, niter, range));
 }
 
+/* Determines the final value of iv with base BASE and step STEP, in loop
+   that iterates NITER times.  */
+
+static tree
+final_value_of_iv (tree base, tree step, tree niter)
+{
+  tree type = TREE_TYPE (base);
+
+  return fold_build2 (PLUS_EXPR, type, base,
+		      fold_build2 (MULT_EXPR, type, step,
+				   fold_convert (type, niter)));
+}
+
 /* Given an exit condition comparing an induction variable with value
    BASE + STEP * i, such that the condition should be true
    (false if EXIT_P is true) for exactly NITER iterations, choose a best shape
@@ -214,7 +229,6 @@ select_condition_shape (tree niter, tree base, tree step,
 			bool exit_p, enum tree_code *cmp, tree *bound)
 {
   tree nit_type = TREE_TYPE (niter), per_type, wider_type;
-  tree iv_type = TREE_TYPE (step);
   tree period, final;
 
   /* To have chance to use this induction variable, its period must be at least
@@ -232,9 +246,7 @@ select_condition_shape (tree niter, tree base, tree step,
     return false;
 
   /* Determine the final value of the iv.  */
-  final = fold_build2 (PLUS_EXPR, iv_type, base,
-		       fold_build2 (MULT_EXPR, iv_type, step,
-				    fold_convert (iv_type, niter)));
+  final = final_value_of_iv (base, step, niter);
 
   /* At this point, we know that we can express the condition as
      IV != FINAL.  */
@@ -265,3 +277,369 @@ end:
 
   return true;
 }
+
+/* Estimate cost of comparing with BOUND.  */
+
+unsigned
+compare_cost (tree bound)
+{
+  /* Prefer costants, and prefer zero even more.  */
+  if (zero_p (bound))
+    return 0;
+  else if (TREE_CODE (bound) == INTEGER_CST)
+    return 1;
+  else
+    return 2;
+}
+
+/* Returns true if it is possible to reverse the LOOP.  List of data references
+   in LOOP is stored to DATAREFS.  Number of iterations is stored in NITER.  */
+
+static bool
+may_reverse_loop_p (struct loop *loop, varray_type *datarefs, tree *niter)
+{
+  edge exit = single_dom_exit (loop);
+  varray_type dependence_relations;
+  lambda_trans_matrix trans;
+  bool ret = false;
+  struct tree_niter_desc niter_desc;
+  tree phi;
+
+  /* Only consider innermost loops with just one exit.  Not strictly necessary,
+     but it makes things simpler.  */
+  if (loop->inner || !exit)
+    return false;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "\nConsidering loop %d\n", loop->num);
+
+  /* Latch should be empty.  Similarly, this condition is not strictly
+     necessary, but keeps things simple.  */
+  if (!empty_block_p (loop->latch)
+      || !single_pred_p (loop->latch)
+      || single_pred (loop->latch) != exit->src)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  FAILED: nonempty latch\n");
+      return false;
+    }
+
+  /* We need to know # of iterations, and there should be no uses of values
+     defined inside loop outside of it, unless the values are invariants of
+     the loop.  */
+  if (!number_of_iterations_exit (loop, exit, &niter_desc, false)
+      || !zero_p (niter_desc.may_be_zero))
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  FAILED: cannot determine precise number of iterations\n");
+      return false;
+    }
+  *niter = niter_desc.niter;
+
+  for (phi = phi_nodes (exit->dest); phi; phi = PHI_CHAIN (phi))
+    {
+      tree val = PHI_ARG_DEF_FROM_EDGE (phi, exit);
+
+      if (is_gimple_reg (val)
+	  && !expr_invariant_in_loop_p (loop, val))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  FAILED: value used outside loop\n");
+	  return false;
+	}
+    }
+
+  /* The iterations of the loop may comunicate only through bivs that can be
+     reversed.  */
+  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+    {
+      tree def = PHI_RESULT (phi), base, step;
+
+      if (is_gimple_reg (def)
+	  && !simple_iv (loop, phi, def, &base, &step, true))
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  FAILED: non-biv phi node\n");
+	  return false;
+	}
+    }
+
+  VARRAY_GENERIC_PTR_INIT (*datarefs, 10, "datarefs");
+  VARRAY_GENERIC_PTR_INIT (dependence_relations, 10, "dependence_relations");
+
+  /* Check for problems with dependences.  */
+  compute_data_dependences_for_loop (loop, true, datarefs,
+				     &dependence_relations);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    dump_data_dependence_relations (dump_file, dependence_relations);
+
+  trans = lambda_trans_matrix_new (1, 1);
+  LTM_MATRIX (trans)[0][0] = -1;
+
+  if (lambda_transform_legal_p (trans, 1, dependence_relations))
+    {
+      ret = true;
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  SUCCESS: may be reversed\n");
+    }
+  else if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  FAILED: dependence check failed\n");
+
+  free_dependence_relations (dependence_relations);
+  return ret;
+}
+
+/* Returns cost of basing exit condition for loop that exits after NITER
+   iterations on induction variable with BASE and STEP.  If REVERSED
+   is true, we reverse the variable first.  */
+
+static unsigned
+endcond_candidate_cost (tree base, tree step, tree niter, bool reversed)
+{
+  tree bound;
+  enum tree_code cmp;
+
+  if (reversed)
+    {
+      base = final_value_of_iv (base, step, niter);
+      step = fold_build1 (NEGATE_EXPR, TREE_TYPE (step), step);
+    }
+
+  if (!select_condition_shape (niter, base, step, true, &cmp, &bound))
+    return 10;
+
+  return compare_cost (bound);
+}
+
+/* Returns the best cost of ending condition of LOOP based on an index of one
+   of DATAREFS.  NITER is number of iterations of the loop.  If REVERSED
+   is true, cost for reversed loop is returned, otherwise cost for original
+   loop is returned.  */
+
+static unsigned
+best_endcond_candidate_cost (struct loop *loop, varray_type datarefs,
+			     tree niter, bool reversed)
+{
+  unsigned best = 10, act, i, it;
+  tree base, step;
+
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+    {
+      struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
+
+      for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
+	{
+	  tree chrec = DR_ACCESS_FN (dr, it);
+
+	  if (TREE_CODE (chrec) != POLYNOMIAL_CHREC
+	      || CHREC_VARIABLE (chrec) != (unsigned) loop->num)
+	    continue;
+
+	  base = CHREC_LEFT (chrec);
+	  step = CHREC_RIGHT (chrec);
+	  if (TREE_CODE (step) != INTEGER_CST
+	      || tree_contains_chrecs (base, NULL)
+	      || chrec_contains_symbols_defined_in_loop (base, loop->num))
+	    continue;
+
+	  act = endcond_candidate_cost (base, step, niter, reversed);
+	  if (act < best)
+	    best = act;
+	}
+    }
+
+  return best;
+}
+
+/* Returns difference between number of arrays that are traversed forwards
+   and backwards in LOOP, according to DATAREFS.  */
+
+static int
+num_of_forward_traversals (struct loop *loop, varray_type datarefs)
+{
+  unsigned i, it;
+  int n_forward = 0;
+
+  /* Determine number of data references passed forwards/backwards
+     in loop.  */
+  for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
+    {
+      struct data_reference *dr = VARRAY_GENERIC_PTR (datarefs, i);
+
+      for (it = 0; it < DR_NUM_DIMENSIONS (dr); it++)
+	{
+	  tree chrec = DR_ACCESS_FN (dr, it);
+	  tree tstride = evolution_part_in_loop_num (chrec, loop->num);
+	  
+	  if (tstride != NULL_TREE && !zero_p (tstride))
+	    {
+	      if (TREE_CODE (tstride) != INTEGER_CST)
+		{
+		  /* Let's be conservative, and assume everything we do not
+		     understand goes forward.  */
+		  n_forward++;
+		}
+	      else if (tree_int_cst_sign_bit (tstride))
+		n_forward--;
+	      else
+		n_forward++;
+	      break;
+	    }
+	}
+    }
+
+  return n_forward;
+}
+
+/* This can be redefined by md, for architectures that prefer the arrays to be
+   traversed forwards (because of some simplistic hardware prefetching).  */
+
+#ifndef PREFER_PASSING_MEMORY_FORWARDS
+#define PREFER_PASSING_MEMORY_FORWARDS 0
+#endif
+
+/* Returns true if it seems to be profitable to reverse the direction
+   in that loop iterates.  DATAREFS is the list of data references in
+   loop.  NITER is the number of iterations of a loop.  */
+
+static bool
+profitable_to_reverse_loop_p (struct loop *loop, varray_type datarefs,
+			      tree niter)
+{
+  unsigned orig_cost, reversed_cost;
+
+  if (PREFER_PASSING_MEMORY_FORWARDS && datarefs)
+    {
+      int n_forward = num_of_forward_traversals (loop, datarefs);
+
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  %d forward traversals\n", n_forward);
+
+      if (n_forward > 0)
+	{
+	  if (dump_file && (dump_flags & TDF_DETAILS))
+	    fprintf (dump_file, "  FAILED: prefer traversing forwards\n");
+	  return false;
+	}
+
+      /* ??? Maybe we would like to reverse the loop just to get the arrays
+	 traversed in the right direction?  */
+    }
+
+  /* Check whether reversing the loop enables us to use a better ending
+     condition for it.  */
+  orig_cost = best_endcond_candidate_cost (loop, datarefs, niter, false);
+  reversed_cost = best_endcond_candidate_cost (loop, datarefs, niter, true);
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  costs: %d orig, %d reversed\n",
+	     orig_cost, reversed_cost);
+
+  if (orig_cost <= reversed_cost)
+    {
+      if (dump_file && (dump_flags & TDF_DETAILS))
+	fprintf (dump_file, "  FAILED: no gain from reversing the loop\n");
+      return false;
+    }
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "  SUCCESS: profitable to reverse\n");
+  return true;
+}
+
+/* Reverse the biv of LOOP defined in phi node PHI.  LOOP iterates NITER
+   times.  */
+
+static void
+reverse_biv (struct loop *loop, tree phi, tree niter)
+{
+  block_stmt_iterator bsi_incr = bsi_last (single_dom_exit (loop)->src);
+  edge entry = loop_preheader_edge (loop);
+  edge latch = loop_latch_edge (loop);
+  tree base, step, def = PHI_RESULT (phi), var = SSA_NAME_VAR (def);
+  tree new_def, stmts;
+  bool ok;
+      
+  ok = simple_iv (loop, phi, def, &base, &step, true);
+  gcc_assert (ok);
+
+  base = unshare_expr (final_value_of_iv (base, step, niter));
+  base = force_gimple_operand (base, &stmts, true, var);
+  if (stmts)
+    bsi_insert_on_edge_immediate_loop (entry, stmts);
+
+  SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, entry), base);
+
+  /* Create the increment.  */
+  new_def = create_increment_stmt (&bsi_incr, false, def, MINUS_EXPR,
+				   unshare_expr (step), var);
+  SET_USE (PHI_ARG_DEF_PTR_FROM_EDGE (phi, latch), new_def);
+}
+
+/* Replace exit condition of LOOP by a test whether NITER iterations
+   have elapsed.  */
+
+static void
+replace_exit_condition (struct loop *loop, tree niter)
+{
+  create_canonical_iv (loop, single_dom_exit (loop), niter);
+}
+
+/* Reverse LOOP.  NITER is number of its iterations.  */
+
+static void
+reverse_loop (struct loop *loop, tree niter)
+{
+  tree phi, var;
+
+  /* Rewrite the phi nodes and adjust increments of the bivs.  */
+  for (phi = phi_nodes (loop->header); phi; phi = PHI_CHAIN (phi))
+    {
+      var = PHI_RESULT (phi);
+      if (!is_gimple_reg (var))
+	continue;
+
+      reverse_biv (loop, phi, niter);
+    }
+
+  replace_exit_condition (loop, niter);
+}
+
+/* Reverse LOOP if possible and profitable.  Returns true if LOOP was
+   reversed.  */
+
+static bool
+loop_reversal (struct loop *loop)
+{
+  varray_type datarefs = NULL;
+  tree niter;
+  bool reversed = false;
+
+  if (may_reverse_loop_p (loop, &datarefs, &niter)
+      && profitable_to_reverse_loop_p (loop, datarefs, niter))
+    {
+      reverse_loop (loop, niter);
+      reversed = true;
+    }
+
+  free_data_refs (datarefs);
+  return reversed;
+}
+
+/* Try reversing the LOOPS, in case it gives a better ending condition.  */
+
+void
+tree_ssa_reverse_loops (struct loops *loops)
+{
+  unsigned i;
+  struct loop *loop;
+  bool changed = false;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+      if (loop)
+	changed |= loop_reversal (loop);
+    }
+
+  if (changed)
+    scev_reset ();
+}
diff --git a/gcc/tree-ssa-loop-ivopts.c b/gcc/tree-ssa-loop-ivopts.c
index c7de71fac61..ddd7a48c526 100644
--- a/gcc/tree-ssa-loop-ivopts.c
+++ b/gcc/tree-ssa-loop-ivopts.c
@@ -3627,20 +3627,6 @@ get_computation_cost (struct ivopts_data *data,
 				  use, cand, address_p, depends_on, use->stmt);
 }
 
-/* Estimate cost of comparing with BOUND.  */
-
-unsigned
-compare_cost (tree bound)
-{
-  /* Prefer costants, and prefer zero even more.  */
-  if (zero_p (bound))
-    return 0;
-  else if (TREE_CODE (bound) == INTEGER_CST)
-    return 1;
-  else
-    return 2;
-}
-
 /* Determines cost of basing replacement of USE on CAND in a generic
    expression.  */
 
diff --git a/gcc/tree-ssa-loop.c b/gcc/tree-ssa-loop.c
index 5e2e738ea43..f35827b3af8 100644
--- a/gcc/tree-ssa-loop.c
+++ b/gcc/tree-ssa-loop.c
@@ -406,6 +406,41 @@ struct tree_opt_pass pass_complete_unroll =
   0					/* letter */
 };
 
+/* Loop reversal.  */
+
+static void
+tree_ssa_loop_reversal (void)
+{
+  if (!current_loops)
+    return;
+
+  tree_ssa_reverse_loops (current_loops);
+}
+
+static bool
+gate_tree_ssa_loop_reversal (void)
+{
+  return flag_loop_reversal != 0;
+}
+
+struct tree_opt_pass pass_loop_reversal =
+{
+  "revloops",				/* name */
+  gate_tree_ssa_loop_reversal,		/* gate */
+  tree_ssa_loop_reversal,	       	/* execute */
+  NULL,					/* sub */
+  NULL,					/* next */
+  0,					/* static_pass_number */
+  TV_TREE_LOOP_REVERSE,	  		/* tv_id */
+  PROP_cfg | PROP_ssa,			/* properties_required */
+  0,					/* properties_provided */
+  0,					/* properties_destroyed */
+  0,					/* todo_flags_start */
+  TODO_dump_func | TODO_verify_loops,	/* todo_flags_finish */
+  0					/* letter */
+};
+
+
 /* Prefetching.  */
 
 static void