1/* Loop unswitching.
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 "gimplify.h"
49#include "gimple-ssa.h"
50#include "tree-cfg.h"
51#include "tree-phinodes.h"
52#include "ssa-iterators.h"
53#include "tree-ssa-loop-niter.h"
54#include "tree-ssa-loop.h"
55#include "tree-into-ssa.h"
56#include "cfgloop.h"
57#include "params.h"
58#include "tree-pass.h"
59#include "tree-inline.h"
60
61/* This file implements the loop unswitching, i.e. transformation of loops like
62
63   while (A)
64     {
65       if (inv)
66         B;
67
68       X;
69
70       if (!inv)
71	 C;
72     }
73
74   where inv is the loop invariant, into
75
76   if (inv)
77     {
78       while (A)
79	 {
80           B;
81	   X;
82	 }
83     }
84   else
85     {
86       while (A)
87	 {
88	   X;
89	   C;
90	 }
91     }
92
93   Inv is considered invariant iff the values it compares are both invariant;
94   tree-ssa-loop-im.c ensures that all the suitable conditions are in this
95   shape.  */
96
97static struct loop *tree_unswitch_loop (struct loop *, basic_block, tree);
98static bool tree_unswitch_single_loop (struct loop *, int);
99static tree tree_may_unswitch_on (basic_block, struct loop *);
100
101/* Main entry point.  Perform loop unswitching on all suitable loops.  */
102
103unsigned int
104tree_ssa_unswitch_loops (void)
105{
106  struct loop *loop;
107  bool changed = false;
108  HOST_WIDE_INT iterations;
109
110  /* Go through inner loops (only original ones).  */
111  FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
112    {
113      if (dump_file && (dump_flags & TDF_DETAILS))
114        fprintf (dump_file, ";; Considering loop %d\n", loop->num);
115
116      /* Do not unswitch in cold regions. */
117      if (optimize_loop_for_size_p (loop))
118        {
119          if (dump_file && (dump_flags & TDF_DETAILS))
120            fprintf (dump_file, ";; Not unswitching cold loops\n");
121          continue;
122        }
123
124      /* The loop should not be too large, to limit code growth. */
125      if (tree_num_loop_insns (loop, &eni_size_weights)
126          > (unsigned) PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
127        {
128          if (dump_file && (dump_flags & TDF_DETAILS))
129            fprintf (dump_file, ";; Not unswitching, loop too big\n");
130          continue;
131        }
132
133      /* If the loop is not expected to iterate, there is no need
134	 for unswitching.  */
135      iterations = estimated_loop_iterations_int (loop);
136      if (iterations >= 0 && iterations <= 1)
137	{
138          if (dump_file && (dump_flags & TDF_DETAILS))
139            fprintf (dump_file, ";; Not unswitching, loop is not expected to iterate\n");
140          continue;
141	}
142
143      changed |= tree_unswitch_single_loop (loop, 0);
144    }
145
146  if (changed)
147    return TODO_cleanup_cfg;
148  return 0;
149}
150
151/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
152   basic blocks (for what it means see comments below).  */
153
154static tree
155tree_may_unswitch_on (basic_block bb, struct loop *loop)
156{
157  gimple last, def;
158  gcond *stmt;
159  tree cond, use;
160  basic_block def_bb;
161  ssa_op_iter iter;
162
163  /* BB must end in a simple conditional jump.  */
164  last = last_stmt (bb);
165  if (!last || gimple_code (last) != GIMPLE_COND)
166    return NULL_TREE;
167  stmt = as_a <gcond *> (last);
168
169  /* To keep the things simple, we do not directly remove the conditions,
170     but just replace tests with 0 != 0 resp. 1 != 0.  Prevent the infinite
171     loop where we would unswitch again on such a condition.  */
172  if (gimple_cond_true_p (stmt) || gimple_cond_false_p (stmt))
173    return NULL_TREE;
174
175  /* Condition must be invariant.  */
176  FOR_EACH_SSA_TREE_OPERAND (use, stmt, iter, SSA_OP_USE)
177    {
178      def = SSA_NAME_DEF_STMT (use);
179      def_bb = gimple_bb (def);
180      if (def_bb
181	  && flow_bb_inside_loop_p (loop, def_bb))
182	return NULL_TREE;
183    }
184
185  cond = build2 (gimple_cond_code (stmt), boolean_type_node,
186		 gimple_cond_lhs (stmt), gimple_cond_rhs (stmt));
187
188  return cond;
189}
190
191/* Simplifies COND using checks in front of the entry of the LOOP.  Just very
192   simplish (sufficient to prevent us from duplicating loop in unswitching
193   unnecessarily).  */
194
195static tree
196simplify_using_entry_checks (struct loop *loop, tree cond)
197{
198  edge e = loop_preheader_edge (loop);
199  gimple stmt;
200
201  while (1)
202    {
203      stmt = last_stmt (e->src);
204      if (stmt
205	  && gimple_code (stmt) == GIMPLE_COND
206	  && gimple_cond_code (stmt) == TREE_CODE (cond)
207	  && operand_equal_p (gimple_cond_lhs (stmt),
208			      TREE_OPERAND (cond, 0), 0)
209	  && operand_equal_p (gimple_cond_rhs (stmt),
210			      TREE_OPERAND (cond, 1), 0))
211	return (e->flags & EDGE_TRUE_VALUE
212		? boolean_true_node
213		: boolean_false_node);
214
215      if (!single_pred_p (e->src))
216	return cond;
217
218      e = single_pred_edge (e->src);
219      if (e->src == ENTRY_BLOCK_PTR_FOR_FN (cfun))
220	return cond;
221    }
222}
223
224/* Unswitch single LOOP.  NUM is number of unswitchings done; we do not allow
225   it to grow too much, it is too easy to create example on that the code would
226   grow exponentially.  */
227
228static bool
229tree_unswitch_single_loop (struct loop *loop, int num)
230{
231  basic_block *bbs;
232  struct loop *nloop;
233  unsigned i, found;
234  tree cond = NULL_TREE;
235  gimple stmt;
236  bool changed = false;
237
238  i = 0;
239  bbs = get_loop_body (loop);
240  found = loop->num_nodes;
241
242  while (1)
243    {
244      /* Find a bb to unswitch on.  */
245      for (; i < loop->num_nodes; i++)
246	if ((cond = tree_may_unswitch_on (bbs[i], loop)))
247	  break;
248
249      if (i == loop->num_nodes)
250	{
251	  if (dump_file
252	      && num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL)
253	      && (dump_flags & TDF_DETAILS))
254	    fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
255
256	  if (found == loop->num_nodes)
257	    {
258	      free (bbs);
259	      return changed;
260	    }
261	  break;
262	}
263
264      cond = simplify_using_entry_checks (loop, cond);
265      stmt = last_stmt (bbs[i]);
266      if (integer_nonzerop (cond))
267	{
268	  /* Remove false path.  */
269	  gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
270					       boolean_true_node);
271	  changed = true;
272	}
273      else if (integer_zerop (cond))
274	{
275	  /* Remove true path.  */
276	  gimple_cond_set_condition_from_tree (as_a <gcond *> (stmt),
277					       boolean_false_node);
278	  changed = true;
279	}
280      /* Do not unswitch too much.  */
281      else if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
282	{
283	  i++;
284	  continue;
285	}
286      /* In nested tree_unswitch_single_loop first optimize all conditions
287	 using entry checks, then discover still reachable blocks in the
288	 loop and find the condition only among those still reachable bbs.  */
289      else if (num != 0)
290	{
291	  if (found == loop->num_nodes)
292	    found = i;
293	  i++;
294	  continue;
295	}
296      else
297	{
298	  found = i;
299	  break;
300	}
301
302      update_stmt (stmt);
303      i++;
304    }
305
306  if (num != 0)
307    {
308      basic_block *tos, *worklist;
309
310      /* When called recursively, first do a quick discovery
311	 of reachable bbs after the above changes and only
312	 consider conditions in still reachable bbs.  */
313      tos = worklist = XNEWVEC (basic_block, loop->num_nodes);
314
315      for (i = 0; i < loop->num_nodes; i++)
316	bbs[i]->flags &= ~BB_REACHABLE;
317
318      /* Start with marking header.  */
319      *tos++ = bbs[0];
320      bbs[0]->flags |= BB_REACHABLE;
321
322      /* Iterate: find everything reachable from what we've already seen
323	 within the same innermost loop.  Don't look through false edges
324	 if condition is always true or true edges if condition is
325	 always false.  */
326      while (tos != worklist)
327	{
328	  basic_block b = *--tos;
329	  edge e;
330	  edge_iterator ei;
331	  int flags = 0;
332
333	  if (EDGE_COUNT (b->succs) == 2)
334	    {
335	      gimple stmt = last_stmt (b);
336	      if (stmt
337		  && gimple_code (stmt) == GIMPLE_COND)
338		{
339		  gcond *cond_stmt = as_a <gcond *> (stmt);
340		  if (gimple_cond_true_p (cond_stmt))
341		    flags = EDGE_FALSE_VALUE;
342		  else if (gimple_cond_false_p (cond_stmt))
343		    flags = EDGE_TRUE_VALUE;
344		}
345	    }
346
347	  FOR_EACH_EDGE (e, ei, b->succs)
348	    {
349	      basic_block dest = e->dest;
350
351	      if (dest->loop_father == loop
352		  && !(dest->flags & BB_REACHABLE)
353		  && !(e->flags & flags))
354		{
355		  *tos++ = dest;
356		  dest->flags |= BB_REACHABLE;
357		}
358	    }
359	}
360
361      free (worklist);
362
363      /* Find a bb to unswitch on.  */
364      for (; found < loop->num_nodes; found++)
365	if ((bbs[found]->flags & BB_REACHABLE)
366	    && (cond = tree_may_unswitch_on (bbs[found], loop)))
367	  break;
368
369      if (found == loop->num_nodes)
370	{
371	  free (bbs);
372	  return changed;
373	}
374    }
375
376  if (dump_file && (dump_flags & TDF_DETAILS))
377    fprintf (dump_file, ";; Unswitching loop\n");
378
379  initialize_original_copy_tables ();
380  /* Unswitch the loop on this condition.  */
381  nloop = tree_unswitch_loop (loop, bbs[found], cond);
382  if (!nloop)
383    {
384      free_original_copy_tables ();
385      free (bbs);
386      return changed;
387    }
388
389  /* Update the SSA form after unswitching.  */
390  update_ssa (TODO_update_ssa);
391  free_original_copy_tables ();
392
393  /* Invoke itself on modified loops.  */
394  tree_unswitch_single_loop (nloop, num + 1);
395  tree_unswitch_single_loop (loop, num + 1);
396  free (bbs);
397  return true;
398}
399
400/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
401   unswitching of innermost loops.  COND is the condition determining which
402   loop is entered -- the new loop is entered if COND is true.  Returns NULL
403   if impossible, new loop otherwise.  */
404
405static struct loop *
406tree_unswitch_loop (struct loop *loop,
407		    basic_block unswitch_on, tree cond)
408{
409  unsigned prob_true;
410  edge edge_true, edge_false;
411
412  /* Some sanity checking.  */
413  gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
414  gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
415  gcc_assert (loop->inner == NULL);
416
417  extract_true_false_edges_from_block (unswitch_on, &edge_true, &edge_false);
418  prob_true = edge_true->probability;
419  return loop_version (loop, unshare_expr (cond),
420		       NULL, prob_true, prob_true,
421		       REG_BR_PROB_BASE - prob_true, false);
422}
423
424/* Loop unswitching pass.  */
425
426namespace {
427
428const pass_data pass_data_tree_unswitch =
429{
430  GIMPLE_PASS, /* type */
431  "unswitch", /* name */
432  OPTGROUP_LOOP, /* optinfo_flags */
433  TV_TREE_LOOP_UNSWITCH, /* tv_id */
434  PROP_cfg, /* properties_required */
435  0, /* properties_provided */
436  0, /* properties_destroyed */
437  0, /* todo_flags_start */
438  0, /* todo_flags_finish */
439};
440
441class pass_tree_unswitch : public gimple_opt_pass
442{
443public:
444  pass_tree_unswitch (gcc::context *ctxt)
445    : gimple_opt_pass (pass_data_tree_unswitch, ctxt)
446  {}
447
448  /* opt_pass methods: */
449  virtual bool gate (function *) { return flag_unswitch_loops != 0; }
450  virtual unsigned int execute (function *);
451
452}; // class pass_tree_unswitch
453
454unsigned int
455pass_tree_unswitch::execute (function *fun)
456{
457  if (number_of_loops (fun) <= 1)
458    return 0;
459
460  return tree_ssa_unswitch_loops ();
461}
462
463} // anon namespace
464
465gimple_opt_pass *
466make_pass_tree_unswitch (gcc::context *ctxt)
467{
468  return new pass_tree_unswitch (ctxt);
469}
470
471
472