[thirdparty/gcc.git] / gcc / tree-ssa-loop-ivcanon.c

/* 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 = EDGE_SUCC (exit->src, 0);
  if (in == exit)
    in = EDGE_SUCC (exit->src, 1);

  /* 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)));
  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));
  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 (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
					       loops, n_unroll, NULL,
					       NULL, NULL, NULL, 0))
	{
	  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)));
    }
  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);
    }

  /* Clean up the information about numbers of iterations, since brute force
     evaluation could reveal new information.  */
  scev_reset ();

#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_tree_loop_ivcanon);
    }

  /* Clean up the information about numbers of iterations, since complete
     unrolling might have invalidated it.  */
  scev_reset ();

#if 0
  /* The necessary infrastructure is not in yet.  */
  if (changed)
    cleanup_tree_cfg_loop ();
#endif
}
Commit	Line	Data
bb445479	1	/* Induction variable canonicalization.
	2	Copyright (C) 2004 Free Software Foundation, Inc.
	3
	4	This file is part of GCC.
	5
	6	GCC is free software; you can redistribute it and/or modify it
	7	under the terms of the GNU General Public License as published by the
	8	Free Software Foundation; either version 2, or (at your option) any
	9	later version.
	10
	11	GCC is distributed in the hope that it will be useful, but WITHOUT
	12	ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
	13	FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
	14	for more details.
	15
	16	You should have received a copy of the GNU General Public License
	17	along with GCC; see the file COPYING. If not, write to the Free
	18	Software Foundation, 59 Temple Place - Suite 330, Boston, MA
	19	02111-1307, USA. */
	20
	21	/* This pass detects the loops that iterate a constant number of times,
	22	adds a canonical induction variable (step -1, tested against 0)
	23	and replaces the exit test. This enables the less powerful rtl
	24	level analysis to use this information.
	25
	26	This might spoil the code in some cases (by increasing register pressure).
	27	Note that in the case the new variable is not needed, ivopts will get rid
	28	of it, so it might only be a problem when there are no other linear induction
	29	variables. In that case the created optimization possibilities are likely
	30	to pay up.
	31
	32	Additionally in case we detect that it is beneficial to unroll the
	33	loop completely, we do it right here to expose the optimization
	34	possibilities to the following passes. */
	35
	36	#include "config.h"
	37	#include "system.h"
	38	#include "coretypes.h"
	39	#include "tm.h"
	40	#include "tree.h"
	41	#include "rtl.h"
	42	#include "tm_p.h"
	43	#include "hard-reg-set.h"
	44	#include "basic-block.h"
	45	#include "output.h"
	46	#include "diagnostic.h"
	47	#include "tree-flow.h"
	48	#include "tree-dump.h"
	49	#include "cfgloop.h"
	50	#include "tree-pass.h"
	51	#include "ggc.h"
	52	#include "tree-chrec.h"
	53	#include "tree-scalar-evolution.h"
	54	#include "params.h"
	55	#include "flags.h"
	56	#include "tree-inline.h"
	57
	58	/* Adds a canonical induction variable to LOOP iterating NITER times. EXIT
	59	is the exit edge whose condition is replaced. */
	60
	61	static void
	62	create_canonical_iv (struct loop *loop, edge exit, tree niter)
	63	{
	64	edge in;
65	tree cond, type, var;
66	block_stmt_iterator incr_at;
67	enum tree_code cmp;
68
69	if (dump_file && (dump_flags & TDF_DETAILS))
70	{
71	fprintf (dump_file, "Added canonical iv to loop %d, ", loop->num);
72	print_generic_expr (dump_file, niter, TDF_SLIM);
73	fprintf (dump_file, " iterations.\n");
74	}
75
76	cond = last_stmt (exit->src);
cd665a06	77	in = EDGE_SUCC (exit->src, 0);
bb445479	78	if (in == exit)
cd665a06	79	in = EDGE_SUCC (exit->src, 1);
bb445479	80
	81	/* Note that we do not need to worry about overflows, since
	82	type of niter is always unsigned and all comparisons are
	83	just for equality/nonequality -- i.e. everything works
	84	with a modulo arithmetics. */
	85
	86	type = TREE_TYPE (niter);
	87	niter = fold (build2 (PLUS_EXPR, type,
	88	niter,
7016c612	89	build_int_cst (type, 1)));
bb445479	90	incr_at = bsi_last (in->src);
	91	create_iv (niter,
	92	fold_convert (type, integer_minus_one_node),
	93	NULL_TREE, loop,
	94	&incr_at, false, NULL, &var);
	95
	96	cmp = (exit->flags & EDGE_TRUE_VALUE) ? EQ_EXPR : NE_EXPR;
	97	COND_EXPR_COND (cond) = build2 (cmp, boolean_type_node,
	98	var,
7016c612	99	build_int_cst (type, 0));
bb445479	100	modify_stmt (cond);
	101	}
	102
	103	/* Computes an estimated number of insns in LOOP. */
	104
	105	unsigned
	106	tree_num_loop_insns (struct loop *loop)
	107	{
	108	basic_block *body = get_loop_body (loop);
	109	block_stmt_iterator bsi;
	110	unsigned size = 1, i;
	111
	112	for (i = 0; i < loop->num_nodes; i++)
	113	for (bsi = bsi_start (body[i]); !bsi_end_p (bsi); bsi_next (&bsi))
	114	size += estimate_num_insns (bsi_stmt (bsi));
	115	free (body);
	116
	117	return size;
	118	}
	119
	120	/* Tries to unroll LOOP completely, i.e. NITER times. LOOPS is the
	121	loop tree. COMPLETELY_UNROLL is true if we should unroll the loop
	122	even if it may cause code growth. EXIT is the exit of the loop
	123	that should be eliminated. */
	124
	125	static bool
	126	try_unroll_loop_completely (struct loops *loops ATTRIBUTE_UNUSED,
	127	struct loop *loop,
	128	edge exit, tree niter,
	129	bool completely_unroll)
	130	{
	131	unsigned HOST_WIDE_INT n_unroll, ninsns, max_unroll;
	132	tree old_cond, cond, dont_exit, do_exit;
	133
	134	if (loop->inner)
	135	return false;
	136
	137	if (!host_integerp (niter, 1))
	138	return false;
	139	n_unroll = tree_low_cst (niter, 1);
	140
	141	max_unroll = PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES);
	142	if (n_unroll > max_unroll)
	143	return false;
	144
	145	if (n_unroll)
	146	{
	147	if (!completely_unroll)
	148	return false;
	149
	150	ninsns = tree_num_loop_insns (loop);
	151
	152	if (n_unroll * ninsns
	153	> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS))
	154	return false;
	155	}
	156
	157	if (exit->flags & EDGE_TRUE_VALUE)
	158	{
	159	dont_exit = boolean_false_node;
	160	do_exit = boolean_true_node;
	161	}
	162	else
	163	{
164	dont_exit = boolean_true_node;
165	do_exit = boolean_false_node;
166	}
167	cond = last_stmt (exit->src);
168
169	if (n_unroll)
170	{
171	if (!flag_unroll_loops)
172	return false;
173
174	old_cond = COND_EXPR_COND (cond);
175	COND_EXPR_COND (cond) = dont_exit;
176	modify_stmt (cond);
177
bb445479	178	if (!tree_duplicate_loop_to_header_edge (loop, loop_preheader_edge (loop),
	179	loops, n_unroll, NULL,
	180	NULL, NULL, NULL, 0))
bb445479	181	{
	182	COND_EXPR_COND (cond) = old_cond;
	183	return false;
	184	}
	185	}
	186
	187	COND_EXPR_COND (cond) = do_exit;
	188	modify_stmt (cond);
	189
	190	if (dump_file && (dump_flags & TDF_DETAILS))
	191	fprintf (dump_file, "Unrolled loop %d completely.\n", loop->num);
	192
	193	return true;
	194	}
	195
	196	/* Adds a canonical induction variable to LOOP if suitable. LOOPS is the loops
	197	tree. CREATE_IV is true if we may create a new iv. COMPLETELY_UNROLL is
	198	true if we should do complete unrolling even if it may cause the code
	199	growth. If TRY_EVAL is true, we try to determine the number of iterations
	200	of a loop by direct evaluation. Returns true if cfg is changed. */
	201
	202	static bool
	203	canonicalize_loop_induction_variables (struct loops loops, struct loop loop,
	204	bool create_iv, bool completely_unroll,
	205	bool try_eval)
	206	{
	207	edge exit = NULL;
	208	tree niter;
	209
	210	niter = number_of_iterations_in_loop (loop);
	211	if (TREE_CODE (niter) == INTEGER_CST)
	212	{
	213	exit = loop->single_exit;
	214	if (!just_once_each_iteration_p (loop, exit->src))
	215	return false;
	216
	217	/* The result of number_of_iterations_in_loop is by one higher than
	218	we expect (i.e. it returns number of executions of the exit
	219	condition, not of the loop latch edge). */
	220	niter = fold (build2 (MINUS_EXPR, TREE_TYPE (niter), niter,
7016c612	221	build_int_cst (TREE_TYPE (niter), 1)));
bb445479	222	}
	223	else if (try_eval)
	224	niter = find_loop_niter_by_eval (loop, &exit);
	225
	226	if (chrec_contains_undetermined (niter)
	227	\|\| TREE_CODE (niter) != INTEGER_CST)
	228	return false;
	229
	230	if (dump_file && (dump_flags & TDF_DETAILS))
	231	{
	232	fprintf (dump_file, "Loop %d iterates ", loop->num);
	233	print_generic_expr (dump_file, niter, TDF_SLIM);
	234	fprintf (dump_file, " times.\n");
	235	}
	236
	237	if (try_unroll_loop_completely (loops, loop, exit, niter, completely_unroll))
	238	return true;
	239
	240	if (create_iv)
	241	create_canonical_iv (loop, exit, niter);
	242
	243	return false;
	244	}
	245
	246	/* The main entry point of the pass. Adds canonical induction variables
	247	to the suitable LOOPS. */
	248
	249	void
	250	canonicalize_induction_variables (struct loops *loops)
	251	{
	252	unsigned i;
	253	struct loop *loop;
	254
	255	for (i = 1; i < loops->num; i++)
	256	{
	257	loop = loops->parray[i];
	258
	259	if (loop)
	260	canonicalize_loop_induction_variables (loops, loop, true, false, true);
	261	}
	262
08162157	263	/* Clean up the information about numbers of iterations, since brute force
	264	evaluation could reveal new information. */
	265	scev_reset ();
	266
bb445479	267	#if 0
	268	/* The necessary infrastructure is not in yet. */
	269	if (changed)
	270	cleanup_tree_cfg_loop ();
	271	#endif
	272	}
	273
	274	/* Unroll LOOPS completely if they iterate just few times. */
	275
	276	void
	277	tree_unroll_loops_completely (struct loops *loops)
	278	{
	279	unsigned i;
	280	struct loop *loop;
	281	bool changed = false;
	282
	283	for (i = 1; i < loops->num; i++)
	284	{
	285	loop = loops->parray[i];
	286
	287	if (!loop)
	288	continue;
	289
	290	changed \|= canonicalize_loop_induction_variables (loops, loop,
	291	false, true,
41b5cc78	292	!flag_tree_loop_ivcanon);
bb445479	293	}
bb445479	294
08162157	295	/* Clean up the information about numbers of iterations, since complete
	296	unrolling might have invalidated it. */
	297	scev_reset ();
	298
bb445479	299	#if 0
	300	/* The necessary infrastructure is not in yet. */
	301	if (changed)
	302	cleanup_tree_cfg_loop ();
	303	#endif
	304	}