1/* Loop header copying on trees.
2   Copyright (C) 2004-2015 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 "hash-set.h"
25#include "machmode.h"
26#include "vec.h"
27#include "double-int.h"
28#include "input.h"
29#include "alias.h"
30#include "symtab.h"
31#include "wide-int.h"
32#include "inchash.h"
33#include "tree.h"
34#include "fold-const.h"
35#include "tm_p.h"
36#include "predict.h"
37#include "hard-reg-set.h"
38#include "input.h"
39#include "function.h"
40#include "dominance.h"
41#include "cfg.h"
42#include "basic-block.h"
43#include "tree-ssa-alias.h"
44#include "internal-fn.h"
45#include "gimple-expr.h"
46#include "is-a.h"
47#include "gimple.h"
48#include "gimple-iterator.h"
49#include "gimple-ssa.h"
50#include "tree-cfg.h"
51#include "tree-into-ssa.h"
52#include "tree-pass.h"
53#include "cfgloop.h"
54#include "tree-inline.h"
55#include "flags.h"
56#include "tree-ssa-threadedge.h"
57
58/* Duplicates headers of loops if they are small enough, so that the statements
59   in the loop body are always executed when the loop is entered.  This
60   increases effectiveness of code motion optimizations, and reduces the need
61   for loop preconditioning.  */
62
63/* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
64   instructions should be duplicated, limit is decreased by the actual
65   amount.  */
66
67static bool
68should_duplicate_loop_header_p (basic_block header, struct loop *loop,
69				int *limit)
70{
71  gimple_stmt_iterator bsi;
72  gimple last;
73
74  /* Do not copy one block more than once (we do not really want to do
75     loop peeling here).  */
76  if (header->aux)
77    return false;
78
79  /* Loop header copying usually increases size of the code.  This used not to
80     be true, since quite often it is possible to verify that the condition is
81     satisfied in the first iteration and therefore to eliminate it.  Jump
82     threading handles these cases now.  */
83  if (optimize_loop_for_size_p (loop))
84    return false;
85
86  gcc_assert (EDGE_COUNT (header->succs) > 0);
87  if (single_succ_p (header))
88    return false;
89  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
90      && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
91    return false;
92
93  /* If this is not the original loop header, we want it to have just
94     one predecessor in order to match the && pattern.  */
95  if (header != loop->header && !single_pred_p (header))
96    return false;
97
98  last = last_stmt (header);
99  if (gimple_code (last) != GIMPLE_COND)
100    return false;
101
102  /* Approximately copy the conditions that used to be used in jump.c --
103     at most 20 insns and no calls.  */
104  for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
105    {
106      last = gsi_stmt (bsi);
107
108      if (gimple_code (last) == GIMPLE_LABEL)
109	continue;
110
111      if (is_gimple_debug (last))
112	continue;
113
114      if (is_gimple_call (last))
115	return false;
116
117      *limit -= estimate_num_insns (last, &eni_size_weights);
118      if (*limit < 0)
119	return false;
120    }
121
122  return true;
123}
124
125/* Checks whether LOOP is a do-while style loop.  */
126
127static bool
128do_while_loop_p (struct loop *loop)
129{
130  gimple stmt = last_stmt (loop->latch);
131
132  /* If the latch of the loop is not empty, it is not a do-while loop.  */
133  if (stmt
134      && gimple_code (stmt) != GIMPLE_LABEL)
135    return false;
136
137  /* If the header contains just a condition, it is not a do-while loop.  */
138  stmt = last_and_only_stmt (loop->header);
139  if (stmt
140      && gimple_code (stmt) == GIMPLE_COND)
141    return false;
142
143  return true;
144}
145
146/* For all loops, copy the condition at the end of the loop body in front
147   of the loop.  This is beneficial since it increases efficiency of
148   code motion optimizations.  It also saves one jump on entry to the loop.  */
149
150namespace {
151
152const pass_data pass_data_ch =
153{
154  GIMPLE_PASS, /* type */
155  "ch", /* name */
156  OPTGROUP_LOOP, /* optinfo_flags */
157  TV_TREE_CH, /* tv_id */
158  ( PROP_cfg | PROP_ssa ), /* properties_required */
159  0, /* properties_provided */
160  0, /* properties_destroyed */
161  0, /* todo_flags_start */
162  0, /* todo_flags_finish */
163};
164
165class pass_ch : public gimple_opt_pass
166{
167public:
168  pass_ch (gcc::context *ctxt)
169    : gimple_opt_pass (pass_data_ch, ctxt)
170  {}
171
172  /* opt_pass methods: */
173  virtual bool gate (function *) { return flag_tree_ch != 0; }
174  virtual unsigned int execute (function *);
175
176}; // class pass_ch
177
178unsigned int
179pass_ch::execute (function *fun)
180{
181  struct loop *loop;
182  basic_block header;
183  edge exit, entry;
184  basic_block *bbs, *copied_bbs;
185  unsigned n_bbs;
186  unsigned bbs_size;
187  bool changed = false;
188
189  loop_optimizer_init (LOOPS_HAVE_PREHEADERS
190		       | LOOPS_HAVE_SIMPLE_LATCHES);
191  if (number_of_loops (fun) <= 1)
192    {
193      loop_optimizer_finalize ();
194      return 0;
195    }
196
197  bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
198  copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
199  bbs_size = n_basic_blocks_for_fn (fun);
200
201  FOR_EACH_LOOP (loop, 0)
202    {
203      /* Copy at most 20 insns.  */
204      int limit = 20;
205
206      header = loop->header;
207
208      /* If the loop is already a do-while style one (either because it was
209	 written as such, or because jump threading transformed it into one),
210	 we might be in fact peeling the first iteration of the loop.  This
211	 in general is not a good idea.  */
212      if (do_while_loop_p (loop))
213	continue;
214
215      /* Iterate the header copying up to limit; this takes care of the cases
216	 like while (a && b) {...}, where we want to have both of the conditions
217	 copied.  TODO -- handle while (a || b) - like cases, by not requiring
218	 the header to have just a single successor and copying up to
219	 postdominator.  */
220
221      exit = NULL;
222      n_bbs = 0;
223      while (should_duplicate_loop_header_p (header, loop, &limit))
224	{
225	  /* Find a successor of header that is inside a loop; i.e. the new
226	     header after the condition is copied.  */
227	  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
228	    exit = EDGE_SUCC (header, 0);
229	  else
230	    exit = EDGE_SUCC (header, 1);
231	  bbs[n_bbs++] = header;
232	  gcc_assert (bbs_size > n_bbs);
233	  header = exit->dest;
234	}
235
236      if (!exit)
237	continue;
238
239      if (dump_file && (dump_flags & TDF_DETAILS))
240	fprintf (dump_file,
241		 "Duplicating header of the loop %d up to edge %d->%d.\n",
242		 loop->num, exit->src->index, exit->dest->index);
243
244      /* Ensure that the header will have just the latch as a predecessor
245	 inside the loop.  */
246      if (!single_pred_p (exit->dest))
247	exit = single_pred_edge (split_edge (exit));
248
249      entry = loop_preheader_edge (loop);
250
251      propagate_threaded_block_debug_into (exit->dest, entry->dest);
252      if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
253					 true))
254	{
255	  fprintf (dump_file, "Duplication failed.\n");
256	  continue;
257	}
258
259      /* If the loop has the form "for (i = j; i < j + 10; i++)" then
260	 this copying can introduce a case where we rely on undefined
261	 signed overflow to eliminate the preheader condition, because
262	 we assume that "j < j + 10" is true.  We don't want to warn
263	 about that case for -Wstrict-overflow, because in general we
264	 don't warn about overflow involving loops.  Prevent the
265	 warning by setting the no_warning flag in the condition.  */
266      if (warn_strict_overflow > 0)
267	{
268	  unsigned int i;
269
270	  for (i = 0; i < n_bbs; ++i)
271	    {
272	      gimple_stmt_iterator bsi;
273
274	      for (bsi = gsi_start_bb (copied_bbs[i]);
275		   !gsi_end_p (bsi);
276		   gsi_next (&bsi))
277		{
278		  gimple stmt = gsi_stmt (bsi);
279		  if (gimple_code (stmt) == GIMPLE_COND)
280		    gimple_set_no_warning (stmt, true);
281		  else if (is_gimple_assign (stmt))
282		    {
283		      enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
284		      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
285			gimple_set_no_warning (stmt, true);
286		    }
287		}
288	    }
289	}
290
291      /* Ensure that the latch and the preheader is simple (we know that they
292	 are not now, since there was the loop exit condition.  */
293      split_edge (loop_preheader_edge (loop));
294      split_edge (loop_latch_edge (loop));
295
296      changed = true;
297    }
298
299  update_ssa (TODO_update_ssa);
300  free (bbs);
301  free (copied_bbs);
302
303  loop_optimizer_finalize ();
304  return changed ? TODO_cleanup_cfg : 0;
305}
306
307} // anon namespace
308
309gimple_opt_pass *
310make_pass_ch (gcc::context *ctxt)
311{
312  return new pass_ch (ctxt);
313}
314