1/* Loop header copying on trees.
2   Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it
7under the terms of the GNU General Public License as published by the
8Free Software Foundation; either version 3, or (at your option) any
9later version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT
12ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3.  If not see
18<http://www.gnu.org/licenses/>.  */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "tm.h"
24#include "tree.h"
25#include "rtl.h"
26#include "tm_p.h"
27#include "hard-reg-set.h"
28#include "basic-block.h"
29#include "output.h"
30#include "diagnostic.h"
31#include "tree-flow.h"
32#include "tree-dump.h"
33#include "tree-pass.h"
34#include "timevar.h"
35#include "cfgloop.h"
36#include "tree-inline.h"
37#include "flags.h"
38#include "tree-inline.h"
39
40/* Duplicates headers of loops if they are small enough, so that the statements
41   in the loop body are always executed when the loop is entered.  This
42   increases effectiveness of code motion optimizations, and reduces the need
43   for loop preconditioning.  */
44
45/* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
46   instructions should be duplicated, limit is decreased by the actual
47   amount.  */
48
49static bool
50should_duplicate_loop_header_p (basic_block header, struct loop *loop,
51				int *limit)
52{
53  gimple_stmt_iterator bsi;
54  gimple last;
55
56  /* Do not copy one block more than once (we do not really want to do
57     loop peeling here).  */
58  if (header->aux)
59    return false;
60
61  /* Loop header copying usually increases size of the code.  This used not to
62     be true, since quite often it is possible to verify that the condition is
63     satisfied in the first iteration and therefore to eliminate it.  Jump
64     threading handles these cases now.  */
65  if (optimize_loop_for_size_p (loop))
66    return false;
67
68  gcc_assert (EDGE_COUNT (header->succs) > 0);
69  if (single_succ_p (header))
70    return false;
71  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
72      && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
73    return false;
74
75  /* If this is not the original loop header, we want it to have just
76     one predecessor in order to match the && pattern.  */
77  if (header != loop->header && !single_pred_p (header))
78    return false;
79
80  last = last_stmt (header);
81  if (gimple_code (last) != GIMPLE_COND)
82    return false;
83
84  /* Approximately copy the conditions that used to be used in jump.c --
85     at most 20 insns and no calls.  */
86  for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
87    {
88      last = gsi_stmt (bsi);
89
90      if (gimple_code (last) == GIMPLE_LABEL)
91	continue;
92
93      if (is_gimple_debug (last))
94	continue;
95
96      if (is_gimple_call (last))
97	return false;
98
99      *limit -= estimate_num_insns (last, &eni_size_weights);
100      if (*limit < 0)
101	return false;
102    }
103
104  return true;
105}
106
107/* Checks whether LOOP is a do-while style loop.  */
108
109static bool
110do_while_loop_p (struct loop *loop)
111{
112  gimple stmt = last_stmt (loop->latch);
113
114  /* If the latch of the loop is not empty, it is not a do-while loop.  */
115  if (stmt
116      && gimple_code (stmt) != GIMPLE_LABEL)
117    return false;
118
119  /* If the header contains just a condition, it is not a do-while loop.  */
120  stmt = last_and_only_stmt (loop->header);
121  if (stmt
122      && gimple_code (stmt) == GIMPLE_COND)
123    return false;
124
125  return true;
126}
127
128/* For all loops, copy the condition at the end of the loop body in front
129   of the loop.  This is beneficial since it increases efficiency of
130   code motion optimizations.  It also saves one jump on entry to the loop.  */
131
132static unsigned int
133copy_loop_headers (void)
134{
135  loop_iterator li;
136  struct loop *loop;
137  basic_block header;
138  edge exit, entry;
139  basic_block *bbs, *copied_bbs;
140  unsigned n_bbs;
141  unsigned bbs_size;
142
143  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
144		       | LOOPS_HAVE_SIMPLE_LATCHES);
145  if (number_of_loops () <= 1)
146    {
147      loop_optimizer_finalize ();
148      return 0;
149    }
150
151#ifdef ENABLE_CHECKING
152  verify_loop_structure ();
153#endif
154
155  bbs = XNEWVEC (basic_block, n_basic_blocks);
156  copied_bbs = XNEWVEC (basic_block, n_basic_blocks);
157  bbs_size = n_basic_blocks;
158
159  FOR_EACH_LOOP (li, loop, 0)
160    {
161      /* Copy at most 20 insns.  */
162      int limit = 20;
163
164      header = loop->header;
165
166      /* If the loop is already a do-while style one (either because it was
167	 written as such, or because jump threading transformed it into one),
168	 we might be in fact peeling the first iteration of the loop.  This
169	 in general is not a good idea.  */
170      if (do_while_loop_p (loop))
171	continue;
172
173      /* Iterate the header copying up to limit; this takes care of the cases
174	 like while (a && b) {...}, where we want to have both of the conditions
175	 copied.  TODO -- handle while (a || b) - like cases, by not requiring
176	 the header to have just a single successor and copying up to
177	 postdominator.  */
178
179      exit = NULL;
180      n_bbs = 0;
181      while (should_duplicate_loop_header_p (header, loop, &limit))
182	{
183	  /* Find a successor of header that is inside a loop; i.e. the new
184	     header after the condition is copied.  */
185	  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
186	    exit = EDGE_SUCC (header, 0);
187	  else
188	    exit = EDGE_SUCC (header, 1);
189	  bbs[n_bbs++] = header;
190	  gcc_assert (bbs_size > n_bbs);
191	  header = exit->dest;
192	}
193
194      if (!exit)
195	continue;
196
197      if (dump_file && (dump_flags & TDF_DETAILS))
198	fprintf (dump_file,
199		 "Duplicating header of the loop %d up to edge %d->%d.\n",
200		 loop->num, exit->src->index, exit->dest->index);
201
202      /* Ensure that the header will have just the latch as a predecessor
203	 inside the loop.  */
204      if (!single_pred_p (exit->dest))
205	exit = single_pred_edge (split_edge (exit));
206
207      entry = loop_preheader_edge (loop);
208
209      if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs))
210	{
211	  fprintf (dump_file, "Duplication failed.\n");
212	  continue;
213	}
214
215      /* If the loop has the form "for (i = j; i < j + 10; i++)" then
216	 this copying can introduce a case where we rely on undefined
217	 signed overflow to eliminate the preheader condition, because
218	 we assume that "j < j + 10" is true.  We don't want to warn
219	 about that case for -Wstrict-overflow, because in general we
220	 don't warn about overflow involving loops.  Prevent the
221	 warning by setting the no_warning flag in the condition.  */
222      if (warn_strict_overflow > 0)
223	{
224	  unsigned int i;
225
226	  for (i = 0; i < n_bbs; ++i)
227	    {
228	      gimple_stmt_iterator bsi;
229
230	      for (bsi = gsi_start_bb (copied_bbs[i]);
231		   !gsi_end_p (bsi);
232		   gsi_next (&bsi))
233		{
234		  gimple stmt = gsi_stmt (bsi);
235		  if (gimple_code (stmt) == GIMPLE_COND)
236		    gimple_set_no_warning (stmt, true);
237		  else if (is_gimple_assign (stmt))
238		    {
239		      enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
240		      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
241			gimple_set_no_warning (stmt, true);
242		    }
243		}
244	    }
245	}
246
247      /* Ensure that the latch and the preheader is simple (we know that they
248	 are not now, since there was the loop exit condition.  */
249      split_edge (loop_preheader_edge (loop));
250      split_edge (loop_latch_edge (loop));
251    }
252
253  free (bbs);
254  free (copied_bbs);
255
256  loop_optimizer_finalize ();
257  return 0;
258}
259
260static bool
261gate_ch (void)
262{
263  return flag_tree_ch != 0;
264}
265
266struct gimple_opt_pass pass_ch =
267{
268 {
269  GIMPLE_PASS,
270  "ch",					/* name */
271  gate_ch,				/* gate */
272  copy_loop_headers,			/* execute */
273  NULL,					/* sub */
274  NULL,					/* next */
275  0,					/* static_pass_number */
276  TV_TREE_CH,				/* tv_id */
277  PROP_cfg | PROP_ssa,			/* properties_required */
278  0,					/* properties_provided */
279  0,					/* properties_destroyed */
280  0,					/* todo_flags_start */
281  TODO_cleanup_cfg | TODO_dump_func
282  | TODO_verify_ssa			/* todo_flags_finish */
283 }
284};
285