* tree-ssa-loop-ivcanon.c: New file.

	* tree-ssa-loop-manip.c (create_iv): New function.
	* Makefile.in (tree-ssa-loop-ivcanon.o): Add.
	(tree-ssa-loop.o, tree-ssa-loop-manip.o): Add SCEV_H dependency.
	* cfgloop.c (mark_single_exit_loops): New function.
	(verify_loop_structure): Verify single-exit loops.
	* cfgloop.h (struct loop): Add single_exit field.
	(LOOPS_HAVE_MARKED_SINGLE_EXITS): New constant.
	(mark_single_exit_loops): Declare.
	(tree_num_loop_insns): Declare.
	* cfgloopmanip.c (update_single_exits_after_duplication): New function.
	(duplicate_loop_to_header_edge): Use it.
	* common.opt (fivcanon): New flag.
	* timevar.def (TV_TREE_LOOP_IVCANON, TV_COMPLETE_UNROLL): New timevars.
	* tree-cfg.c (tree_find_edge_insert_loc): Return newly created block.
	(bsi_commit_edge_inserts_1): Pass null to tree_find_edge_insert_loc.
	(bsi_insert_on_edge_immediate): New function.
	* tree-flow.h (bsi_insert_on_edge_immediate,
	canonicalize_induction_variables, tree_unroll_loops_completely,
	create_iv): Declare.
	* tree-optimize.c (init_tree_optimization_passes): Add
	pass_iv_canon and pass_complete_unroll.
	* tree-pass.h (pass_iv_canon, pass_complete_unroll): Declare.
	* tree-scalar-evolution.c (get_loop_exit_condition,
	get_exit_conditions_rec, number_of_iterations_in_loop,
	scev_initialize): Use single_exit information.
	* tree-ssa-loop-niter.c (number_of_iterations_cond): Record
	missing assumptions.
	(loop_niter_by_eval):  Return number of iterations as unsigned
	int.
	* tree-ssa-loop.c (tree_ssa_loop_init): Mark single exit loops.
	(tree_ssa_loop_ivcanon, gate_tree_ssa_loop_ivcanon, pass_iv_canon,
	tree_complete_unroll, gate_tree_complete_unroll, pass_complete_unroll):
	New passes.
	(tree_ssa_loop_done): Call free_numbers_of_iterations_estimates.
	* tree-ssanames.c (make_ssa_name): Allow creating ssa name before
	the defining statement is ready.
	* tree-vectorizer.c (vect_create_iv_simple): Removed.
	(vect_create_index_for_array_ref, vect_transform_loop_bound):
	Use create_iv.
	(vect_transform_loop_bound): Use single_exit information.
	(vect_analyze_loop_form): Cleanup bogus tests.
	(vectorize_loops): Do not call flow_loop_scan.
	* tree.h (may_negate_without_overflow_p): Declare.
	* fold-const.c (may_negate_without_overflow_p): Split out from ...
	(negate_expr_p): ... this function.
	(tree_expr_nonzero_p): Handle overflowed constants correctly.
	* doc/invoke.texi (-fivcanon): Document.
	* doc/passes.texi: Document canonical induction variable creation.

	* gcc.dg/tree-ssa/loop-1.c: New test.


git-svn-id: svn+ssh://gcc.gnu.org/svn/gcc/trunk@86516 138bc75d-0d04-0410-961f-82ee72b054a4

1 files changed, 299 insertions, 0 deletions

diff --git a/gcc/tree-ssa-loop-ivcanon.c b/gcc/tree-ssa-loop-ivcanon.c
new file mode 100644
index 00000000000..67c599856c6
--- /dev/null
+++ b/gcc/tree-ssa-loop-ivcanon.c
@@ -0,0 +1,299 @@
+/* Induction variable canonicalization.
+   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.  */
+
+/* This pass detects the loops that iterate a constant number of times,
+   adds a canonical induction variable (step -1, tested against 0) 
+   and replaces the exit test.  This enables the less powerful rtl
+   level analysis to use this information.
+
+   This might spoil the code in some cases (by increasing register pressure).
+   Note that in the case the new variable is not needed, ivopts will get rid
+   of it, so it might only be a problem when there are no other linear induction
+   variables.  In that case the created optimization possibilities are likely
+   to pay up.
+
+   Additionally in case we detect that it is beneficial to unroll the
+   loop completely, we do it right here to expose the optimization
+   possibilities to the following passes.  */
+
+#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"
+
+/* Adds a canonical induction variable to LOOP iterating NITER times.  EXIT
+   is the exit edge whose condition is replaced.  */
+
+static void
+create_canonical_iv (struct loop *loop, edge exit, tree niter)
+{
+  edge in;
+  tree cond, type, var;
+  block_stmt_iterator incr_at;
+  enum tree_code cmp;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
+      print_generic_expr (dump_file, niter, TDF_SLIM);
+      fprintf (dump_file, " iterations.\n");
+    }
+
+  cond = last_stmt (exit->src);
+  in = exit->src->succ;
+  if (in == exit)
+    in = in->succ_next;
+
+  /* Note that we do not need to worry about overflows, since
+     type of niter is always unsigned and all comparisons are
+     just for equality/nonequality -- i.e. everything works
+     with a modulo arithmetics.  */
+
+  type = TREE_TYPE (niter);
+  niter = fold (build2 (PLUS_EXPR, type,
+			niter,
+			build_int_cst (type, 1, 0)));
+  incr_at = bsi_last (in->src);
+  create_iv (niter,
+	     fold_convert (type, integer_minus_one_node),
+	     NULL_TREE, loop,
+	     &incr_at, false, NULL, &var);
+
+  cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
+  COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
+				  var,
+				  build_int_cst (type, 0, 0));
+  modify_stmt (cond);
+}
+
+/* Computes an estimated number of insns in LOOP.  */
+
+unsigned
+tree_num_loop_insns (struct loop *loop)
+{
+  basic_block *body = get_loop_body (loop);
+  block_stmt_iterator bsi;
+  unsigned size = 1, i;
+
+  for (i = 0; i < loop->num_nodes; i++)
+    for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
+      size += estimate_num_insns (bsi_stmt (bsi));
+  free (body);
+
+  return size;
+}
+
+/* Tries to unroll LOOP completely, i.e. NITER times.  LOOPS is the
+   loop tree.  COMPLETELY_UNROLL is true if we should unroll the loop
+   even if it may cause code growth.  EXIT is the exit of the loop
+   that should be eliminated.  */
+
+static bool
+try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
+			    struct loop *loop,
+			    edge exit, tree niter,
+			    bool completely_unroll)
+{
+  unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll;
+  tree old_cond, cond, dont_exit, do_exit;
+
+  if (loop->inner)
+    return false;
+
+  if (!host_integerp (niter, 1))
+    return false;
+  n_unroll = tree_low_cst (niter, 1);
+
+  max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
+  if (n_unroll > max_unroll)
+    return false;
+
+  if (n_unroll)
+    {
+      if (!completely_unroll)
+	return false;
+
+      ninsns = tree_num_loop_insns (loop);
+
+      if (n_unroll * ninsns
+	  > (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
+	return false;
+    }
+
+  if (exit->flags & EDGE_TRUE_VALUE)
+    {
+      dont_exit = boolean_false_node;
+      do_exit = boolean_true_node;
+    }
+  else
+    {
+      dont_exit = boolean_true_node;
+      do_exit = boolean_false_node;
+    }
+  cond = last_stmt (exit->src);
+    
+  if (n_unroll)
+    {
+      if (!flag_unroll_loops)
+	return false;
+
+      old_cond = COND_EXPR_COND (cond);
+      COND_EXPR_COND (cond) = dont_exit;
+      modify_stmt (cond);
+
+#if 0
+      /* The necessary infrastructure is not in yet.  */
+      if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
+					       loops, n_unroll, NULL,
+					       NULL, NULL, NULL, 0))
+#endif
+	{
+	  COND_EXPR_COND (cond) = old_cond;
+	  return false;
+	}
+    }
+  
+  COND_EXPR_COND (cond) = do_exit;
+  modify_stmt (cond);
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
+
+  return true;
+}
+
+/* Adds a canonical induction variable to LOOP if suitable.  LOOPS is the loops
+   tree.  CREATE_IV is true if we may create a new iv.  COMPLETELY_UNROLL is
+   true if we should do complete unrolling even if it may cause the code
+   growth.  If TRY_EVAL is true, we try to determine the number of iterations
+   of a loop by direct evaluation.  Returns true if cfg is changed.  */
+
+static bool
+canonicalize_loop_induction_variables (struct loops *loops, struct loop *loop,
+				       bool create_iv, bool completely_unroll,
+				       bool try_eval)
+{
+  edge exit = NULL;
+  tree niter;
+
+  niter = number_of_iterations_in_loop (loop);
+  if (TREE_CODE (niter) == INTEGER_CST)
+    {
+      exit = loop->single_exit;
+      if (!just_once_each_iteration_p (loop, exit->src))
+	return false;
+
+      /* The result of number_of_iterations_in_loop is by one higher than
+	 we expect (i.e. it returns number of executions of the exit
+	 condition, not of the loop latch edge).  */
+      niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
+			    build_int_cst (TREE_TYPE (niter), 1, 0)));
+    }
+  else if (try_eval)
+    niter = find_loop_niter_by_eval (loop, &exit);
+
+  if (chrec_contains_undetermined (niter)
+      || TREE_CODE (niter) != INTEGER_CST)
+    return false;
+
+  if (dump_file && (dump_flags & TDF_DETAILS))
+    {
+      fprintf (dump_file, "Loop %d iterates ", loop->num);
+      print_generic_expr (dump_file, niter, TDF_SLIM);
+      fprintf (dump_file, " times.\n");
+    }
+
+  if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
+    return true;
+
+  if (create_iv)
+    create_canonical_iv (loop, exit, niter);
+
+  return false;
+}
+
+/* The main entry point of the pass.  Adds canonical induction variables
+   to the suitable LOOPS.  */
+
+void
+canonicalize_induction_variables (struct loops *loops)
+{
+  unsigned i;
+  struct loop *loop;
+  
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+
+      if (loop)
+	canonicalize_loop_induction_variables (loops, loop, true, false, true);
+    }
+
+#if 0
+  /* The necessary infrastructure is not in yet.  */
+  if (changed)
+    cleanup_tree_cfg_loop ();
+#endif
+}
+
+/* Unroll LOOPS completely if they iterate just few times.  */
+
+void
+tree_unroll_loops_completely (struct loops *loops)
+{
+  unsigned i;
+  struct loop *loop;
+  bool changed = false;
+
+  for (i = 1; i < loops->num; i++)
+    {
+      loop = loops->parray[i];
+
+      if (!loop)
+	continue;
+
+      changed |= canonicalize_loop_induction_variables (loops, loop,
+							false, true,
+							!flag_ivcanon);
+    }
+
+#if 0
+  /* The necessary infrastructure is not in yet.  */
+  if (changed)
+    cleanup_tree_cfg_loop ();
+#endif
+}