[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
f3d9a16c	1	/* Loop header copying on trees.
b7119a5a	2	Copyright (C) 2004, 2005 Free Software Foundation, Inc.
f3d9a16c	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
67ce556b	18	Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
67ce556b	19	02110-1301, USA. */
f3d9a16c	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
c26a6416	43	increases effectiveness of code motion optimizations, and reduces the need
f3d9a16c	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
cd665a06	62	gcc_assert (EDGE_COUNT (header->succs) > 0);
ea091dfd	63	if (single_succ_p (header))
f3d9a16c	64	return false;
cd665a06	65	if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
cd665a06	66	&& flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
f3d9a16c	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. */
ea091dfd	71	if (header != loop->header && !single_pred_p (header))
f3d9a16c	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
f3d9a16c	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
2a1990e9	123	static unsigned int
f3d9a16c	124	copy_loop_headers (void)
	125	{
	126	struct loops *loops;
	127	unsigned i;
	128	struct loop *loop;
	129	basic_block header;
4d6b11ab	130	edge exit, entry;
4d6b11ab	131	basic_block bbs, copied_bbs;
d8b5b4fe	132	unsigned n_bbs;
4d6b11ab	133	unsigned bbs_size;
f3d9a16c	134
3f5be5f4	135	loops = loop_optimizer_init (LOOPS_HAVE_PREHEADERS
3f5be5f4	136	\| LOOPS_HAVE_SIMPLE_LATCHES);
f3d9a16c	137	if (!loops)
2a1990e9	138	return 0;
f3d9a16c	139
	140	#ifdef ENABLE_CHECKING
	141	verify_loop_structure (loops);
	142	#endif
	143
4c36ffe6	144	bbs = XNEWVEC (basic_block, n_basic_blocks);
4c36ffe6	145	copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
4d6b11ab	146	bbs_size = n_basic_blocks;
d8b5b4fe	147
f3d9a16c	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];
dda28f7c	154	if (!loop)
dda28f7c	155	continue;
d8b5b4fe	156	header = loop->header;
f3d9a16c	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
d8b5b4fe	169	postdominator. */
	170
	171	exit = NULL;
	172	n_bbs = 0;
f3d9a16c	173	while (should_duplicate_loop_header_p (header, loop, &limit))
f3d9a16c	174	{
f3d9a16c	175	/* Find a successor of header that is inside a loop; i.e. the new
f3d9a16c	176	header after the condition is copied. */
cd665a06	177	if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
cd665a06	178	exit = EDGE_SUCC (header, 0);
f3d9a16c	179	else
cd665a06	180	exit = EDGE_SUCC (header, 1);
d8b5b4fe	181	bbs[n_bbs++] = header;
4d6b11ab	182	gcc_assert (bbs_size > n_bbs);
d8b5b4fe	183	header = exit->dest;
f3d9a16c	184	}
f3d9a16c	185
d8b5b4fe	186	if (!exit)
d8b5b4fe	187	continue;
f3d9a16c	188
d8b5b4fe	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. */
ea091dfd	196	if (!single_pred_p (exit->dest))
00bd8b44	197	exit = single_pred_edge (loop_split_edge_with (exit, NULL));
d8b5b4fe	198
4d6b11ab	199	entry = loop_preheader_edge (loop);
4d6b11ab	200
4d6b11ab	201	if (!tree_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
d8b5b4fe	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);
f3d9a16c	211	}
f3d9a16c	212
d8b5b4fe	213	free (bbs);
4d6b11ab	214	free (copied_bbs);
d8b5b4fe	215
3f5be5f4	216	loop_optimizer_finalize (loops);
2a1990e9	217	return 0;
f3d9a16c	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 */
d8b5b4fe	235	PROP_cfg \| PROP_ssa, /* properties_required */
f3d9a16c	236	0, /* properties_provided */
	237	0, /* properties_destroyed */
	238	0, /* todo_flags_start */
cbcbd868	239	TODO_cleanup_cfg \| TODO_dump_func
cbcbd868	240	\| TODO_verify_ssa, /* todo_flags_finish */
0f9005dd	241	0 /* letter */
f3d9a16c	242	};