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

/* Loop header copying on trees.
   Copyright (C) 2004, 2005 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, 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, 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 unsigned int
copy_loop_headers (void)
{
  struct loops *loops;
  unsigned i;
  struct loop *loop;
  basic_block header;
  edge exit, entry;
  basic_block *bbs, *copied_bbs;
  unsigned n_bbs;
  unsigned bbs_size;

  loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
			       | LOOPS_HAVE_SIMPLE_LATCHES);
  if (!loops)
    return 0;

#ifdef ENABLE_CHECKING
  verify_loop_structure (loops);
#endif

  bbs = XNEWVEC (basic_block, n_basic_blocks);
  copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
  bbs_size = 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;
	  gcc_assert (bbs_size > n_bbs);
	  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_pred_edge (loop_split_edge_with (exit, NULL));

      entry = loop_preheader_edge (loop);

      if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
	{
	  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);
  free (copied_bbs);

  loop_optimizer_finalize (loops);
  return 0;
}

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	1	/* Loop header copying on trees.
c6c81aa6	2	Copyright (C) 2004, 2005 Free Software Foundation, Inc.
5f240ec4 ZD	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
366ccddb KC	18	Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
366ccddb KC	19	02110-1301, USA. */
5f240ec4 ZD	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
c2924966	123	static unsigned int
5f240ec4 ZD	124	copy_loop_headers (void)
	125	{
	126	struct loops *loops;
	127	unsigned i;
	128	struct loop *loop;
	129	basic_block header;
33156717 JH	130	edge exit, entry;
33156717 JH	131	basic_block bbs, copied_bbs;
42759f1e	132	unsigned n_bbs;
33156717	133	unsigned bbs_size;
5f240ec4	134
10d22567 ZD	135	loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
10d22567 ZD	136	\| LOOPS_HAVE_SIMPLE_LATCHES);
5f240ec4	137	if (!loops)
c2924966	138	return 0;
5f240ec4 ZD	139
	140	#ifdef ENABLE_CHECKING
	141	verify_loop_structure (loops);
	142	#endif
	143
5ed6ace5 MD	144	bbs = XNEWVEC (basic_block, n_basic_blocks);
5ed6ace5 MD	145	copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
33156717	146	bbs_size = n_basic_blocks;
42759f1e	147
5f240ec4 ZD	148	for (i = 1; i < loops->num; i++)
	149	{
	150	/* Copy at most 20 insns. */
	151	int limit = 20;
	152
	153	loop = loops->parray[i];
d16464bb DB	154	if (!loop)
d16464bb DB	155	continue;
42759f1e	156	header = loop->header;
5f240ec4 ZD	157
	158	/* If the loop is already a do-while style one (either because it was
	159	written as such, or because jump threading transformed it into one),
	160	we might be in fact peeling the first iteration of the loop. This
	161	in general is not a good idea. */
	162	if (do_while_loop_p (loop))
	163	continue;
	164
	165	/* Iterate the header copying up to limit; this takes care of the cases
	166	like while (a && b) {...}, where we want to have both of the conditions
	167	copied. TODO -- handle while (a \|\| b) - like cases, by not requiring
	168	the header to have just a single successor and copying up to
42759f1e ZD	169	postdominator. */
	170
	171	exit = NULL;
	172	n_bbs = 0;
5f240ec4 ZD	173	while (should_duplicate_loop_header_p (header, loop, &limit))
5f240ec4 ZD	174	{
5f240ec4 ZD	175	/* Find a successor of header that is inside a loop; i.e. the new
5f240ec4 ZD	176	header after the condition is copied. */
628f6a4e BE	177	if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
628f6a4e BE	178	exit = EDGE_SUCC (header, 0);
5f240ec4	179	else
628f6a4e	180	exit = EDGE_SUCC (header, 1);
42759f1e	181	bbs[n_bbs++] = header;
33156717	182	gcc_assert (bbs_size > n_bbs);
42759f1e	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	196	if (!single_pred_p (exit->dest))
77fcaf4b	197	exit = single_pred_edge (loop_split_edge_with (exit, NULL));
42759f1e	198
33156717	199	entry = loop_preheader_edge (loop);
33156717 JH	200
33156717 JH	201	if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
42759f1e ZD	202	{
	203	fprintf (dump_file, "Duplication failed.\n");
	204	continue;
	205	}
	206
	207	/* Ensure that the latch and the preheader is simple (we know that they
	208	are not now, since there was the loop exit condition. */
	209	loop_split_edge_with (loop_preheader_edge (loop), NULL);
	210	loop_split_edge_with (loop_latch_edge (loop), NULL);
5f240ec4 ZD	211	}
5f240ec4 ZD	212
42759f1e	213	free (bbs);
33156717	214	free (copied_bbs);
42759f1e	215
10d22567	216	loop_optimizer_finalize (loops);
c2924966	217	return 0;
5f240ec4 ZD	218	}
	219
	220	static bool
	221	gate_ch (void)
	222	{
	223	return flag_tree_ch != 0;
	224	}
	225
	226	struct tree_opt_pass pass_ch =
	227	{
	228	"ch", /* name */
	229	gate_ch, /* gate */
	230	copy_loop_headers, /* execute */
	231	NULL, /* sub */
	232	NULL, /* next */
	233	0, /* static_pass_number */
	234	TV_TREE_CH, /* tv_id */
42759f1e	235	PROP_cfg \| PROP_ssa, /* properties_required */
5f240ec4 ZD	236	0, /* properties_provided */
	237	0, /* properties_destroyed */
	238	0, /* todo_flags_start */
88a40e67 DB	239	TODO_cleanup_cfg \| TODO_dump_func
88a40e67 DB	240	\| TODO_verify_ssa, /* todo_flags_finish */
9f8628ba	241	0 /* letter */
5f240ec4	242	};