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

/* Loop header copying on trees.
   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 "tree-pass.h"
#include "timevar.h"
#include "cfgloop.h"
#include "tree-inline.h"
#include "flags.h"
#include "tree-inline.h"

/* Duplicates headers of loops if they are small enough, so that the statements
   in the loop body are always executed when the loop is entered.  This
   increases effectiveness of code motion optimizations, and reduces the need
   for loop preconditioning.  */

/* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
   instructions should be duplicated, limit is decreased by the actual
   amount.  */

static bool
should_duplicate_loop_header_p (basic_block header, struct loop *loop,
				int *limit)
{
  block_stmt_iterator bsi;
  tree last;

  /* Do not copy one block more than once (we do not really want to do
     loop peeling here).  */
  if (header->aux)
    return false;

  gcc_assert (EDGE_COUNT (header->succs) > 0);
  if (single_succ_p (header))
    return false;
  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
      && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
    return false;

  /* If this is not the original loop header, we want it to have just
     one predecessor in order to match the && pattern.  */
  if (header != loop->header && !single_pred_p (header))
    return false;

  last = last_stmt (header);
  if (TREE_CODE (last) != COND_EXPR)
    return false;

  /* Approximately copy the conditions that used to be used in jump.c --
     at most 20 insns and no calls.  */
  for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
    {
      last = bsi_stmt (bsi);

      if (TREE_CODE (last) == LABEL_EXPR)
	continue;

      if (get_call_expr_in (last))
	return false;

      *limit -= estimate_num_insns (last);
      if (*limit < 0)
	return false;
    }

  return true;
}

/* Checks whether LOOP is a do-while style loop.  */

static bool
do_while_loop_p (struct loop *loop)
{
  tree stmt = last_stmt (loop->latch);

  /* If the latch of the loop is not empty, it is not a do-while loop.  */
  if (stmt
      && TREE_CODE (stmt) != LABEL_EXPR)
    return false;

  /* If the header contains just a condition, it is not a do-while loop.  */
  stmt = last_and_only_stmt (loop->header);
  if (stmt
      && TREE_CODE (stmt) == COND_EXPR)
    return false;

  return true;
}

/* For all loops, copy the condition at the end of the loop body in front
   of the loop.  This is beneficial since it increases efficiency of
   code motion optimizations.  It also saves one jump on entry to the loop.  */

static void
copy_loop_headers (void)
{
  struct loops *loops;
  unsigned i;
  struct loop *loop;
  basic_block header;
  edge exit;
  basic_block *bbs;
  unsigned n_bbs;

  loops = loop_optimizer_init (dump_file);
  if (!loops)
    return;
  rewrite_into_loop_closed_ssa (NULL);
  
  /* We do not try to keep the information about irreducible regions
     up-to-date.  */
  loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;

#ifdef ENABLE_CHECKING
  verify_loop_structure (loops);
#endif

  bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);

  for (i = 1; i < loops->num; i++)
    {
      /* Copy at most 20 insns.  */
      int limit = 20;

      loop = loops->parray[i];
      if (!loop)
	continue;
      header = loop->header;

      /* If the loop is already a do-while style one (either because it was
	 written as such, or because jump threading transformed it into one),
	 we might be in fact peeling the first iteration of the loop.  This
	 in general is not a good idea.  */
      if (do_while_loop_p (loop))
	continue;

      /* Iterate the header copying up to limit; this takes care of the cases
	 like while (a && b) {...}, where we want to have both of the conditions
	 copied.  TODO -- handle while (a || b) - like cases, by not requiring
	 the header to have just a single successor and copying up to
	 postdominator.  */

      exit = NULL;
      n_bbs = 0;
      while (should_duplicate_loop_header_p (header, loop, &limit))
	{
	  /* Find a successor of header that is inside a loop; i.e. the new
	     header after the condition is copied.  */
	  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
	    exit = EDGE_SUCC (header, 0);
	  else
	    exit = EDGE_SUCC (header, 1);
	  bbs[n_bbs++] = header;
	  header = exit->dest;
	}

      if (!exit)
	continue;

      if (dump_file && (dump_flags & TDF_DETAILS))
	fprintf (dump_file,
		 "Duplicating header of the loop %d up to edge %d->%d.\n",
		 loop->num, exit->src->index, exit->dest->index);

      /* Ensure that the header will have just the latch as a predecessor
	 inside the loop.  */
      if (!single_pred_p (exit->dest))
	exit = single_succ_edge (loop_split_edge_with (exit, NULL));

      if (!tree_duplicate_sese_region (loop_preheader_edge (loop), exit,
				       bbs, n_bbs, NULL))
	{
	  fprintf (dump_file, "Duplication failed.\n");
	  continue;
	}

      /* Ensure that the latch and the preheader is simple (we know that they
	 are not now, since there was the loop exit condition.  */
      loop_split_edge_with (loop_preheader_edge (loop), NULL);
      loop_split_edge_with (loop_latch_edge (loop), NULL);
    }

  free (bbs);

#ifdef ENABLE_CHECKING
  verify_loop_closed_ssa ();
#endif

  loop_optimizer_finalize (loops, NULL);
}

static bool
gate_ch (void)
{
  return flag_tree_ch != 0;
}

struct tree_opt_pass pass_ch = 
{
  "ch",					/* name */
  gate_ch,				/* gate */
  copy_loop_headers,			/* execute */
  NULL,					/* sub */
  NULL,					/* next */
  0,					/* static_pass_number */
  TV_TREE_CH,				/* tv_id */
  PROP_cfg | PROP_ssa,			/* properties_required */
  0,					/* properties_provided */
  0,					/* properties_destroyed */
  0,					/* todo_flags_start */
  TODO_cleanup_cfg | TODO_dump_func 
  | TODO_verify_ssa,			/* todo_flags_finish */
  0					/* letter */
};
Commit	Line	Data
5f240ec4 ZD	1	/* Loop header copying on trees.
	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	#include "config.h"
	22	#include "system.h"
	23	#include "coretypes.h"
	24	#include "tm.h"
	25	#include "tree.h"
	26	#include "rtl.h"
	27	#include "tm_p.h"
	28	#include "hard-reg-set.h"
	29	#include "basic-block.h"
	30	#include "output.h"
	31	#include "diagnostic.h"
	32	#include "tree-flow.h"
	33	#include "tree-dump.h"
	34	#include "tree-pass.h"
	35	#include "timevar.h"
	36	#include "cfgloop.h"
	37	#include "tree-inline.h"
	38	#include "flags.h"
	39	#include "tree-inline.h"
	40
	41	/* Duplicates headers of loops if they are small enough, so that the statements
	42	in the loop body are always executed when the loop is entered. This
b01d837f	43	increases effectiveness of code motion optimizations, and reduces the need
5f240ec4 ZD	44	for loop preconditioning. */
	45
	46	/* Check whether we should duplicate HEADER of LOOP. At most *LIMIT
	47	instructions should be duplicated, limit is decreased by the actual
	48	amount. */
	49
	50	static bool
	51	should_duplicate_loop_header_p (basic_block header, struct loop *loop,
	52	int *limit)
	53	{
	54	block_stmt_iterator bsi;
	55	tree last;
	56
	57	/* Do not copy one block more than once (we do not really want to do
	58	loop peeling here). */
	59	if (header->aux)
	60	return false;
	61
628f6a4e	62	gcc_assert (EDGE_COUNT (header->succs) > 0);
c5cbcccf	63	if (single_succ_p (header))
5f240ec4	64	return false;
628f6a4e BE	65	if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
628f6a4e BE	66	&& flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
5f240ec4 ZD	67	return false;
	68
	69	/* If this is not the original loop header, we want it to have just
	70	one predecessor in order to match the && pattern. */
c5cbcccf	71	if (header != loop->header && !single_pred_p (header))
5f240ec4 ZD	72	return false;
	73
	74	last = last_stmt (header);
	75	if (TREE_CODE (last) != COND_EXPR)
	76	return false;
	77
	78	/* Approximately copy the conditions that used to be used in jump.c --
	79	at most 20 insns and no calls. */
	80	for (bsi = bsi_start (header); !bsi_end_p (bsi); bsi_next (&bsi))
	81	{
	82	last = bsi_stmt (bsi);
	83
	84	if (TREE_CODE (last) == LABEL_EXPR)
	85	continue;
	86
	87	if (get_call_expr_in (last))
	88	return false;
	89
	90	*limit -= estimate_num_insns (last);
	91	if (*limit < 0)
	92	return false;
	93	}
	94
	95	return true;
	96	}
	97
5f240ec4 ZD	98	/* Checks whether LOOP is a do-while style loop. */
	99
	100	static bool
	101	do_while_loop_p (struct loop *loop)
	102	{
	103	tree stmt = last_stmt (loop->latch);
	104
	105	/* If the latch of the loop is not empty, it is not a do-while loop. */
	106	if (stmt
	107	&& TREE_CODE (stmt) != LABEL_EXPR)
	108	return false;
	109
	110	/* If the header contains just a condition, it is not a do-while loop. */
	111	stmt = last_and_only_stmt (loop->header);
	112	if (stmt
	113	&& TREE_CODE (stmt) == COND_EXPR)
	114	return false;
	115
	116	return true;
	117	}
	118
	119	/* For all loops, copy the condition at the end of the loop body in front
	120	of the loop. This is beneficial since it increases efficiency of
	121	code motion optimizations. It also saves one jump on entry to the loop. */
	122
	123	static void
	124	copy_loop_headers (void)
	125	{
	126	struct loops *loops;
	127	unsigned i;
	128	struct loop *loop;
	129	basic_block header;
42759f1e ZD	130	edge exit;
	131	basic_block *bbs;
	132	unsigned n_bbs;
5f240ec4 ZD	133
	134	loops = loop_optimizer_init (dump_file);
	135	if (!loops)
	136	return;
2b271002	137	rewrite_into_loop_closed_ssa (NULL);
5f240ec4 ZD	138
	139	/* We do not try to keep the information about irreducible regions
	140	up-to-date. */
	141	loops->state &= ~LOOPS_HAVE_MARKED_IRREDUCIBLE_REGIONS;
	142
	143	#ifdef ENABLE_CHECKING
	144	verify_loop_structure (loops);
	145	#endif
	146
42759f1e ZD	147	bbs = xmalloc (sizeof (basic_block) * n_basic_blocks);
42759f1e ZD	148
5f240ec4 ZD	149	for (i = 1; i < loops->num; i++)
	150	{
	151	/* Copy at most 20 insns. */
	152	int limit = 20;
	153
	154	loop = loops->parray[i];
d16464bb DB	155	if (!loop)
d16464bb DB	156	continue;
42759f1e	157	header = loop->header;
5f240ec4 ZD	158
	159	/* If the loop is already a do-while style one (either because it was
	160	written as such, or because jump threading transformed it into one),
	161	we might be in fact peeling the first iteration of the loop. This
	162	in general is not a good idea. */
	163	if (do_while_loop_p (loop))
	164	continue;
	165
	166	/* Iterate the header copying up to limit; this takes care of the cases
	167	like while (a && b) {...}, where we want to have both of the conditions
	168	copied. TODO -- handle while (a \|\| b) - like cases, by not requiring
	169	the header to have just a single successor and copying up to
42759f1e ZD	170	postdominator. */
	171
	172	exit = NULL;
	173	n_bbs = 0;
5f240ec4 ZD	174	while (should_duplicate_loop_header_p (header, loop, &limit))
5f240ec4 ZD	175	{
5f240ec4 ZD	176	/* Find a successor of header that is inside a loop; i.e. the new
5f240ec4 ZD	177	header after the condition is copied. */
628f6a4e BE	178	if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
628f6a4e BE	179	exit = EDGE_SUCC (header, 0);
5f240ec4	180	else
628f6a4e	181	exit = EDGE_SUCC (header, 1);
42759f1e ZD	182	bbs[n_bbs++] = header;
42759f1e ZD	183	header = exit->dest;
5f240ec4	184	}
5f240ec4	185
42759f1e ZD	186	if (!exit)
42759f1e ZD	187	continue;
5f240ec4	188
42759f1e ZD	189	if (dump_file && (dump_flags & TDF_DETAILS))
	190	fprintf (dump_file,
	191	"Duplicating header of the loop %d up to edge %d->%d.\n",
	192	loop->num, exit->src->index, exit->dest->index);
	193
	194	/* Ensure that the header will have just the latch as a predecessor
	195	inside the loop. */
c5cbcccf ZD	196	if (!single_pred_p (exit->dest))
c5cbcccf ZD	197	exit = single_succ_edge (loop_split_edge_with (exit, NULL));
42759f1e ZD	198
	199	if (!tree_duplicate_sese_region (loop_preheader_edge (loop), exit,
	200	bbs, n_bbs, NULL))
	201	{
	202	fprintf (dump_file, "Duplication failed.\n");
	203	continue;
	204	}
	205
	206	/* Ensure that the latch and the preheader is simple (we know that they
	207	are not now, since there was the loop exit condition. */
	208	loop_split_edge_with (loop_preheader_edge (loop), NULL);
	209	loop_split_edge_with (loop_latch_edge (loop), NULL);
5f240ec4 ZD	210	}
5f240ec4 ZD	211
42759f1e ZD	212	free (bbs);
	213
	214	#ifdef ENABLE_CHECKING
	215	verify_loop_closed_ssa ();
	216	#endif
	217
	218	loop_optimizer_finalize (loops, NULL);
5f240ec4 ZD	219	}
	220
	221	static bool
	222	gate_ch (void)
	223	{
	224	return flag_tree_ch != 0;
	225	}
	226
	227	struct tree_opt_pass pass_ch =
	228	{
	229	"ch", /* name */
	230	gate_ch, /* gate */
	231	copy_loop_headers, /* execute */
	232	NULL, /* sub */
	233	NULL, /* next */
	234	0, /* static_pass_number */
	235	TV_TREE_CH, /* tv_id */
42759f1e	236	PROP_cfg \| PROP_ssa, /* properties_required */
5f240ec4 ZD	237	0, /* properties_provided */
	238	0, /* properties_destroyed */
	239	0, /* todo_flags_start */
88a40e67 DB	240	TODO_cleanup_cfg \| TODO_dump_func
88a40e67 DB	241	\| TODO_verify_ssa, /* todo_flags_finish */
9f8628ba	242	0 /* letter */
5f240ec4	243	};