1 /* Loop header copying on trees.
2    Copyright (C) 2004-2018 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 3, 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 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 "backend.h"
24 #include "tree.h"
25 #include "gimple.h"
26 #include "cfghooks.h"
27 #include "tree-pass.h"
28 #include "gimple-ssa.h"
29 #include "gimple-iterator.h"
30 #include "tree-cfg.h"
31 #include "tree-into-ssa.h"
32 #include "cfgloop.h"
33 #include "tree-inline.h"
34 #include "tree-ssa-scopedtables.h"
35 #include "tree-ssa-threadedge.h"
36 #include "params.h"
37 
38 /* Duplicates headers of loops if they are small enough, so that the statements
39    in the loop body are always executed when the loop is entered.  This
40    increases effectiveness of code motion optimizations, and reduces the need
41    for loop preconditioning.  */
42 
43 /* Check whether we should duplicate HEADER of LOOP.  At most *LIMIT
44    instructions should be duplicated, limit is decreased by the actual
45    amount.  */
46 
47 static bool
48 should_duplicate_loop_header_p (basic_block header, struct loop *loop,
49 				int *limit)
50 {
51   gimple_stmt_iterator bsi;
52   gimple *last;
53 
54   gcc_assert (!header->aux);
55 
56   /* Loop header copying usually increases size of the code.  This used not to
57      be true, since quite often it is possible to verify that the condition is
58      satisfied in the first iteration and therefore to eliminate it.  Jump
59      threading handles these cases now.  */
60   if (optimize_loop_for_size_p (loop)
61       && !loop->force_vectorize)
62     {
63       if (dump_file && (dump_flags & TDF_DETAILS))
64 	fprintf (dump_file,
65 		 "  Not duplicating bb %i: optimizing for size.\n",
66 		 header->index);
67       return false;
68     }
69 
70   gcc_assert (EDGE_COUNT (header->succs) > 0);
71   if (single_succ_p (header))
72     {
73       if (dump_file && (dump_flags & TDF_DETAILS))
74 	fprintf (dump_file,
75 		 "  Not duplicating bb %i: it is single succ.\n",
76 		 header->index);
77       return false;
78     }
79 
80   if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest)
81       && flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 1)->dest))
82     {
83       if (dump_file && (dump_flags & TDF_DETAILS))
84 	fprintf (dump_file,
85 		 "  Not duplicating bb %i: both sucessors are in loop.\n",
86 		 loop->num);
87       return false;
88     }
89 
90   /* If this is not the original loop header, we want it to have just
91      one predecessor in order to match the && pattern.  */
92   if (header != loop->header && !single_pred_p (header))
93     {
94       if (dump_file && (dump_flags & TDF_DETAILS))
95 	fprintf (dump_file,
96 		 "  Not duplicating bb %i: it has mutiple predecestors.\n",
97 		 header->index);
98       return false;
99     }
100 
101   last = last_stmt (header);
102   if (gimple_code (last) != GIMPLE_COND)
103     {
104       if (dump_file && (dump_flags & TDF_DETAILS))
105 	fprintf (dump_file,
106 		 "  Not duplicating bb %i: it does not end by conditional.\n",
107 		 header->index);
108       return false;
109     }
110 
111   /* Count number of instructions and punt on calls.  */
112   for (bsi = gsi_start_bb (header); !gsi_end_p (bsi); gsi_next (&bsi))
113     {
114       last = gsi_stmt (bsi);
115 
116       if (gimple_code (last) == GIMPLE_LABEL)
117 	continue;
118 
119       if (is_gimple_debug (last))
120 	continue;
121 
122       if (gimple_code (last) == GIMPLE_CALL
123 	  && (!gimple_inexpensive_call_p (as_a <gcall *> (last))
124 	      /* IFN_LOOP_DIST_ALIAS means that inner loop is distributed
125 		 at current loop's header.  Don't copy in this case.  */
126 	      || gimple_call_internal_p (last, IFN_LOOP_DIST_ALIAS)))
127 	{
128 	  if (dump_file && (dump_flags & TDF_DETAILS))
129 	    fprintf (dump_file,
130 		     "  Not duplicating bb %i: it contains call.\n",
131 		     header->index);
132 	  return false;
133 	}
134 
135       *limit -= estimate_num_insns (last, &eni_size_weights);
136       if (*limit < 0)
137 	{
138 	  if (dump_file && (dump_flags & TDF_DETAILS))
139 	    fprintf (dump_file,
140 		     "  Not duplicating bb %i contains too many insns.\n",
141 		     header->index);
142 	  return false;
143 	}
144     }
145   if (dump_file && (dump_flags & TDF_DETAILS))
146     fprintf (dump_file, "    Will duplicate bb %i\n", header->index);
147   return true;
148 }
149 
150 /* Checks whether LOOP is a do-while style loop.  */
151 
152 static bool
153 do_while_loop_p (struct loop *loop)
154 {
155   gimple *stmt = last_stmt (loop->latch);
156 
157   /* If the latch of the loop is not empty, it is not a do-while loop.  */
158   if (stmt
159       && gimple_code (stmt) != GIMPLE_LABEL)
160     {
161       if (dump_file && (dump_flags & TDF_DETAILS))
162 	fprintf (dump_file,
163 		 "Loop %i is not do-while loop: latch is not empty.\n",
164 		 loop->num);
165       return false;
166     }
167 
168   /* If the header contains just a condition, it is not a do-while loop.  */
169   stmt = last_and_only_stmt (loop->header);
170   if (stmt
171       && gimple_code (stmt) == GIMPLE_COND)
172     {
173       if (dump_file && (dump_flags & TDF_DETAILS))
174 	fprintf (dump_file,
175 		 "Loop %i is not do-while loop: "
176 		 "header contains just condition.\n", loop->num);
177       return false;
178     }
179   if (dump_file && (dump_flags & TDF_DETAILS))
180     fprintf (dump_file, "Loop %i is do-while loop\n", loop->num);
181 
182   return true;
183 }
184 
185 namespace {
186 
187 /* Common superclass for both header-copying phases.  */
188 class ch_base : public gimple_opt_pass
189 {
190   protected:
191     ch_base (pass_data data, gcc::context *ctxt)
192       : gimple_opt_pass (data, ctxt)
193     {}
194 
195   /* Copies headers of all loops in FUN for which process_loop_p is true.  */
196   unsigned int copy_headers (function *fun);
197 
198   /* Return true to copy headers of LOOP or false to skip.  */
199   virtual bool process_loop_p (struct loop *loop) = 0;
200 };
201 
202 const pass_data pass_data_ch =
203 {
204   GIMPLE_PASS, /* type */
205   "ch", /* name */
206   OPTGROUP_LOOP, /* optinfo_flags */
207   TV_TREE_CH, /* tv_id */
208   ( PROP_cfg | PROP_ssa ), /* properties_required */
209   0, /* properties_provided */
210   0, /* properties_destroyed */
211   0, /* todo_flags_start */
212   0, /* todo_flags_finish */
213 };
214 
215 class pass_ch : public ch_base
216 {
217 public:
218   pass_ch (gcc::context *ctxt)
219     : ch_base (pass_data_ch, ctxt)
220   {}
221 
222   /* opt_pass methods: */
223   virtual bool gate (function *) { return flag_tree_ch != 0; }
224 
225   /* Initialize and finalize loop structures, copying headers inbetween.  */
226   virtual unsigned int execute (function *);
227 
228   opt_pass * clone () { return new pass_ch (m_ctxt); }
229 
230 protected:
231   /* ch_base method: */
232   virtual bool process_loop_p (struct loop *loop);
233 }; // class pass_ch
234 
235 const pass_data pass_data_ch_vect =
236 {
237   GIMPLE_PASS, /* type */
238   "ch_vect", /* name */
239   OPTGROUP_LOOP, /* optinfo_flags */
240   TV_TREE_CH, /* tv_id */
241   ( PROP_cfg | PROP_ssa ), /* properties_required */
242   0, /* properties_provided */
243   0, /* properties_destroyed */
244   0, /* todo_flags_start */
245   0, /* todo_flags_finish */
246 };
247 
248 /* This is a more aggressive version of the same pass, designed to run just
249    before if-conversion and vectorization, to put more loops into the form
250    required for those phases.  */
251 class pass_ch_vect : public ch_base
252 {
253 public:
254   pass_ch_vect (gcc::context *ctxt)
255     : ch_base (pass_data_ch_vect, ctxt)
256   {}
257 
258   /* opt_pass methods: */
259   virtual bool gate (function *fun)
260   {
261     return flag_tree_ch != 0
262 	   && (flag_tree_loop_vectorize != 0 || fun->has_force_vectorize_loops);
263   }
264 
265   /* Just copy headers, no initialization/finalization of loop structures.  */
266   virtual unsigned int execute (function *);
267 
268 protected:
269   /* ch_base method: */
270   virtual bool process_loop_p (struct loop *loop);
271 }; // class pass_ch_vect
272 
273 /* For all loops, copy the condition at the end of the loop body in front
274    of the loop.  This is beneficial since it increases efficiency of
275    code motion optimizations.  It also saves one jump on entry to the loop.  */
276 
277 unsigned int
278 ch_base::copy_headers (function *fun)
279 {
280   struct loop *loop;
281   basic_block header;
282   edge exit, entry;
283   basic_block *bbs, *copied_bbs;
284   unsigned n_bbs;
285   unsigned bbs_size;
286   bool changed = false;
287 
288   if (number_of_loops (fun) <= 1)
289       return 0;
290 
291   bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
292   copied_bbs = XNEWVEC (basic_block, n_basic_blocks_for_fn (fun));
293   bbs_size = n_basic_blocks_for_fn (fun);
294 
295   FOR_EACH_LOOP (loop, 0)
296     {
297       int initial_limit = PARAM_VALUE (PARAM_MAX_LOOP_HEADER_INSNS);
298       int remaining_limit = initial_limit;
299       if (dump_file && (dump_flags & TDF_DETAILS))
300 	fprintf (dump_file,
301 		 "Analyzing loop %i\n", loop->num);
302 
303       header = loop->header;
304 
305       /* If the loop is already a do-while style one (either because it was
306 	 written as such, or because jump threading transformed it into one),
307 	 we might be in fact peeling the first iteration of the loop.  This
308 	 in general is not a good idea.  */
309       if (!process_loop_p (loop))
310 	continue;
311 
312       /* Iterate the header copying up to limit; this takes care of the cases
313 	 like while (a && b) {...}, where we want to have both of the conditions
314 	 copied.  TODO -- handle while (a || b) - like cases, by not requiring
315 	 the header to have just a single successor and copying up to
316 	 postdominator.  */
317 
318       exit = NULL;
319       n_bbs = 0;
320       while (should_duplicate_loop_header_p (header, loop, &remaining_limit))
321 	{
322 	  /* Find a successor of header that is inside a loop; i.e. the new
323 	     header after the condition is copied.  */
324 	  if (flow_bb_inside_loop_p (loop, EDGE_SUCC (header, 0)->dest))
325 	    exit = EDGE_SUCC (header, 0);
326 	  else
327 	    exit = EDGE_SUCC (header, 1);
328 	  bbs[n_bbs++] = header;
329 	  gcc_assert (bbs_size > n_bbs);
330 	  header = exit->dest;
331 	}
332 
333       if (!exit)
334 	continue;
335 
336       if (dump_file && (dump_flags & TDF_DETAILS))
337 	fprintf (dump_file,
338 		 "Duplicating header of the loop %d up to edge %d->%d,"
339 		 " %i insns.\n",
340 		 loop->num, exit->src->index, exit->dest->index,
341 		 initial_limit - remaining_limit);
342 
343       /* Ensure that the header will have just the latch as a predecessor
344 	 inside the loop.  */
345       if (!single_pred_p (exit->dest))
346 	exit = single_pred_edge (split_edge (exit));
347 
348       entry = loop_preheader_edge (loop);
349 
350       propagate_threaded_block_debug_into (exit->dest, entry->dest);
351       if (!gimple_duplicate_sese_region (entry, exit, bbs, n_bbs, copied_bbs,
352 					 true))
353 	{
354 	  fprintf (dump_file, "Duplication failed.\n");
355 	  continue;
356 	}
357 
358       /* If the loop has the form "for (i = j; i < j + 10; i++)" then
359 	 this copying can introduce a case where we rely on undefined
360 	 signed overflow to eliminate the preheader condition, because
361 	 we assume that "j < j + 10" is true.  We don't want to warn
362 	 about that case for -Wstrict-overflow, because in general we
363 	 don't warn about overflow involving loops.  Prevent the
364 	 warning by setting the no_warning flag in the condition.  */
365       if (warn_strict_overflow > 0)
366 	{
367 	  unsigned int i;
368 
369 	  for (i = 0; i < n_bbs; ++i)
370 	    {
371 	      gimple_stmt_iterator bsi;
372 
373 	      for (bsi = gsi_start_bb (copied_bbs[i]);
374 		   !gsi_end_p (bsi);
375 		   gsi_next (&bsi))
376 		{
377 		  gimple *stmt = gsi_stmt (bsi);
378 		  if (gimple_code (stmt) == GIMPLE_COND)
379 		    gimple_set_no_warning (stmt, true);
380 		  else if (is_gimple_assign (stmt))
381 		    {
382 		      enum tree_code rhs_code = gimple_assign_rhs_code (stmt);
383 		      if (TREE_CODE_CLASS (rhs_code) == tcc_comparison)
384 			gimple_set_no_warning (stmt, true);
385 		    }
386 		}
387 	    }
388 	}
389 
390       /* Ensure that the latch and the preheader is simple (we know that they
391 	 are not now, since there was the loop exit condition.  */
392       split_edge (loop_preheader_edge (loop));
393       split_edge (loop_latch_edge (loop));
394 
395       changed = true;
396     }
397 
398   if (changed)
399     update_ssa (TODO_update_ssa);
400   free (bbs);
401   free (copied_bbs);
402 
403   return changed ? TODO_cleanup_cfg : 0;
404 }
405 
406 /* Initialize the loop structures we need, and finalize after.  */
407 
408 unsigned int
409 pass_ch::execute (function *fun)
410 {
411   loop_optimizer_init (LOOPS_HAVE_PREHEADERS
412 		       | LOOPS_HAVE_SIMPLE_LATCHES);
413 
414   unsigned int res = copy_headers (fun);
415 
416   loop_optimizer_finalize ();
417   return res;
418 }
419 
420 /* Assume an earlier phase has already initialized all the loop structures that
421    we need here (and perhaps others too), and that these will be finalized by
422    a later phase.  */
423 
424 unsigned int
425 pass_ch_vect::execute (function *fun)
426 {
427   return copy_headers (fun);
428 }
429 
430 /* Apply header copying according to a very simple test of do-while shape.  */
431 
432 bool
433 pass_ch::process_loop_p (struct loop *loop)
434 {
435   return !do_while_loop_p (loop);
436 }
437 
438 /* Apply header-copying to loops where we might enable vectorization.  */
439 
440 bool
441 pass_ch_vect::process_loop_p (struct loop *loop)
442 {
443   if (!flag_tree_loop_vectorize && !loop->force_vectorize)
444     return false;
445 
446   if (loop->dont_vectorize)
447     return false;
448 
449   if (!do_while_loop_p (loop))
450     return true;
451 
452  /* The vectorizer won't handle anything with multiple exits, so skip.  */
453   edge exit = single_exit (loop);
454   if (!exit)
455     return false;
456 
457   /* Copy headers iff there looks to be code in the loop after the exit block,
458      i.e. the exit block has an edge to another block (besides the latch,
459      which should be empty).  */
460   edge_iterator ei;
461   edge e;
462   FOR_EACH_EDGE (e, ei, exit->src->succs)
463     if (!loop_exit_edge_p (loop, e)
464 	&& e->dest != loop->header
465 	&& e->dest != loop->latch)
466       return true;
467 
468   return false;
469 }
470 
471 } // anon namespace
472 
473 gimple_opt_pass *
474 make_pass_ch_vect (gcc::context *ctxt)
475 {
476   return new pass_ch_vect (ctxt);
477 }
478 
479 gimple_opt_pass *
480 make_pass_ch (gcc::context *ctxt)
481 {
482   return new pass_ch (ctxt);
483 }
484