1/* Loop unswitching for GNU compiler.
2   Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 2, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; 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 COPYING.  If not, write to the Free
18Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
1902110-1301, USA.  */
20
21#include "config.h"
22#include "system.h"
23#include "coretypes.h"
24#include "tm.h"
25#include "rtl.h"
26#include "hard-reg-set.h"
27#include "obstack.h"
28#include "basic-block.h"
29#include "cfgloop.h"
30#include "cfglayout.h"
31#include "params.h"
32#include "output.h"
33#include "expr.h"
34
35/* This pass moves constant conditions out of loops, duplicating the loop
36   in progress, i.e. this code:
37
38   while (loop_cond)
39     {
40       A;
41       if (cond)
42         branch1;
43       else
44	 branch2;
45       B;
46       if (cond)
47         branch3;
48       C;
49     }
50   where nothing inside the loop alters cond is transformed
51   into
52
53   if (cond)
54     {
55       while (loop_cond)
56	 {
57	   A;
58	   branch1;
59	   B;
60	   branch3;
61	   C;
62	 }
63     }
64   else
65     {
66       while (loop_cond)
67	 {
68	   A;
69	   branch2;
70	   B;
71	   C;
72	 }
73     }
74
75  Duplicating the loop might lead to code growth exponential in number of
76  branches inside loop, so we limit the number of unswitchings performed
77  in a single loop to PARAM_MAX_UNSWITCH_LEVEL.  We only perform the
78  transformation on innermost loops, as the benefit of doing it on loops
79  containing subloops would not be very large compared to complications
80  with handling this case.  */
81
82static struct loop *unswitch_loop (struct loops *, struct loop *,
83				   basic_block, rtx, rtx);
84static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
85static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
86
87/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
88   true, with probability PROB.  If CINSN is not NULL, it is the insn to copy
89   in order to create a jump.  */
90
91rtx
92compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
93		      rtx cinsn)
94{
95  rtx seq, jump, cond;
96  enum machine_mode mode;
97
98  mode = GET_MODE (op0);
99  if (mode == VOIDmode)
100    mode = GET_MODE (op1);
101
102  start_sequence ();
103  if (GET_MODE_CLASS (mode) == MODE_CC)
104    {
105      /* A hack -- there seems to be no easy generic way how to make a
106	 conditional jump from a ccmode comparison.  */
107      gcc_assert (cinsn);
108      cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
109      gcc_assert (GET_CODE (cond) == comp);
110      gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
111      gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
112      emit_jump_insn (copy_insn (PATTERN (cinsn)));
113      jump = get_last_insn ();
114      JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
115      LABEL_NUSES (JUMP_LABEL (jump))++;
116      redirect_jump (jump, label, 0);
117    }
118  else
119    {
120      gcc_assert (!cinsn);
121
122      op0 = force_operand (op0, NULL_RTX);
123      op1 = force_operand (op1, NULL_RTX);
124      do_compare_rtx_and_jump (op0, op1, comp, 0,
125			       mode, NULL_RTX, NULL_RTX, label);
126      jump = get_last_insn ();
127      JUMP_LABEL (jump) = label;
128      LABEL_NUSES (label)++;
129    }
130  REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
131					REG_NOTES (jump));
132  seq = get_insns ();
133  end_sequence ();
134
135  return seq;
136}
137
138/* Main entry point.  Perform loop unswitching on all suitable LOOPS.  */
139void
140unswitch_loops (struct loops *loops)
141{
142  int i, num;
143  struct loop *loop;
144
145  /* Go through inner loops (only original ones).  */
146  num = loops->num;
147
148  for (i = 1; i < num; i++)
149    {
150      /* Removed loop?  */
151      loop = loops->parray[i];
152      if (!loop)
153	continue;
154
155      if (loop->inner)
156	continue;
157
158      unswitch_single_loop (loops, loop, NULL_RTX, 0);
159#ifdef ENABLE_CHECKING
160      verify_dominators (CDI_DOMINATORS);
161      verify_loop_structure (loops);
162#endif
163    }
164
165  iv_analysis_done ();
166}
167
168/* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
169   basic blocks (for what it means see comments below).  In case condition
170   compares loop invariant cc mode register, return the jump in CINSN.  */
171
172static rtx
173may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
174{
175  rtx test, at, op[2], stest;
176  struct rtx_iv iv;
177  unsigned i;
178  enum machine_mode mode;
179
180  /* BB must end in a simple conditional jump.  */
181  if (EDGE_COUNT (bb->succs) != 2)
182    return NULL_RTX;
183  if (!any_condjump_p (BB_END (bb)))
184    return NULL_RTX;
185
186  /* With branches inside loop.  */
187  if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
188      || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
189    return NULL_RTX;
190
191  /* It must be executed just once each iteration (because otherwise we
192     are unable to update dominator/irreducible loop information correctly).  */
193  if (!just_once_each_iteration_p (loop, bb))
194    return NULL_RTX;
195
196  /* Condition must be invariant.  */
197  test = get_condition (BB_END (bb), &at, true, false);
198  if (!test)
199    return NULL_RTX;
200
201  for (i = 0; i < 2; i++)
202    {
203      op[i] = XEXP (test, i);
204
205      if (CONSTANT_P (op[i]))
206	continue;
207
208      if (!iv_analyze (at, op[i], &iv))
209	return NULL_RTX;
210      if (iv.step != const0_rtx
211	  || iv.first_special)
212	return NULL_RTX;
213
214      op[i] = get_iv_value (&iv, const0_rtx);
215    }
216
217  mode = GET_MODE (op[0]);
218  if (mode == VOIDmode)
219    mode = GET_MODE (op[1]);
220  if (GET_MODE_CLASS (mode) == MODE_CC)
221    {
222      if (at != BB_END (bb))
223	return NULL_RTX;
224
225      if (!rtx_equal_p (op[0], XEXP (test, 0))
226	  || !rtx_equal_p (op[1], XEXP (test, 1)))
227	return NULL_RTX;
228
229      *cinsn = BB_END (bb);
230      return test;
231    }
232
233  stest = simplify_gen_relational (GET_CODE (test), SImode,
234				   mode, op[0], op[1]);
235  if (stest == const0_rtx
236      || stest == const_true_rtx)
237    return stest;
238
239  return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
240					  op[0], op[1]));
241}
242
243/* Reverses CONDition; returns NULL if we cannot.  */
244rtx
245reversed_condition (rtx cond)
246{
247  enum rtx_code reversed;
248  reversed = reversed_comparison_code (cond, NULL);
249  if (reversed == UNKNOWN)
250    return NULL_RTX;
251  else
252    return gen_rtx_fmt_ee (reversed,
253			   GET_MODE (cond), XEXP (cond, 0),
254			   XEXP (cond, 1));
255}
256
257/* Unswitch single LOOP.  COND_CHECKED holds list of conditions we already
258   unswitched on and are therefore known to be true in this LOOP.  NUM is
259   number of unswitchings done; do not allow it to grow too much, it is too
260   easy to create example on that the code would grow exponentially.  */
261static void
262unswitch_single_loop (struct loops *loops, struct loop *loop,
263		      rtx cond_checked, int num)
264{
265  basic_block *bbs;
266  struct loop *nloop;
267  unsigned i;
268  rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
269  int repeat;
270  edge e;
271
272  /* Do not unswitch too much.  */
273  if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
274    {
275      if (dump_file)
276	fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
277      return;
278    }
279
280  /* Only unswitch innermost loops.  */
281  if (loop->inner)
282    {
283      if (dump_file)
284	fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
285      return;
286    }
287
288  /* We must be able to duplicate loop body.  */
289  if (!can_duplicate_loop_p (loop))
290    {
291      if (dump_file)
292	fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
293      return;
294    }
295
296  /* The loop should not be too large, to limit code growth.  */
297  if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
298    {
299      if (dump_file)
300	fprintf (dump_file, ";; Not unswitching, loop too big\n");
301      return;
302    }
303
304  /* Do not unswitch in cold areas.  */
305  if (!maybe_hot_bb_p (loop->header))
306    {
307      if (dump_file)
308	fprintf (dump_file, ";; Not unswitching, not hot area\n");
309      return;
310    }
311
312  /* Nor if the loop usually does not roll.  */
313  if (expected_loop_iterations (loop) < 1)
314    {
315      if (dump_file)
316	fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
317      return;
318    }
319
320  do
321    {
322      repeat = 0;
323      cinsn = NULL_RTX;
324
325      /* Find a bb to unswitch on.  */
326      bbs = get_loop_body (loop);
327      iv_analysis_loop_init (loop);
328      for (i = 0; i < loop->num_nodes; i++)
329	if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
330	  break;
331
332      if (i == loop->num_nodes)
333	{
334	  free (bbs);
335	  return;
336	}
337
338      if (cond != const0_rtx
339	  && cond != const_true_rtx)
340	{
341	  rcond = reversed_condition (cond);
342	  if (rcond)
343	    rcond = canon_condition (rcond);
344
345	  /* Check whether the result can be predicted.  */
346	  for (acond = cond_checked; acond; acond = XEXP (acond, 1))
347	    simplify_using_condition (XEXP (acond, 0), &cond, NULL);
348	}
349
350      if (cond == const_true_rtx)
351	{
352	  /* Remove false path.  */
353	  e = FALLTHRU_EDGE (bbs[i]);
354	  remove_path (loops, e);
355	  free (bbs);
356	  repeat = 1;
357	}
358      else if (cond == const0_rtx)
359	{
360	  /* Remove true path.  */
361	  e = BRANCH_EDGE (bbs[i]);
362	  remove_path (loops, e);
363	  free (bbs);
364	  repeat = 1;
365	}
366    } while (repeat);
367
368  /* We found the condition we can unswitch on.  */
369  conds = alloc_EXPR_LIST (0, cond, cond_checked);
370  if (rcond)
371    rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
372  else
373    rconds = cond_checked;
374
375  if (dump_file)
376    fprintf (dump_file, ";; Unswitching loop\n");
377
378  /* Unswitch the loop on this condition.  */
379  nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
380  gcc_assert (nloop);
381
382  /* Invoke itself on modified loops.  */
383  unswitch_single_loop (loops, nloop, rconds, num + 1);
384  unswitch_single_loop (loops, loop, conds, num + 1);
385
386  free_EXPR_LIST_node (conds);
387  if (rcond)
388    free_EXPR_LIST_node (rconds);
389
390  free (bbs);
391}
392
393/* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON.  We only support
394   unswitching of innermost loops.  UNSWITCH_ON must be executed in every
395   iteration, i.e. it must dominate LOOP latch.  COND is the condition
396   determining which loop is entered.  Returns NULL if impossible, new loop
397   otherwise.  The new loop is entered if COND is true.  If CINSN is not
398   NULL, it is the insn in that COND is compared.  */
399
400static struct loop *
401unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
402	       rtx cond, rtx cinsn)
403{
404  edge entry, latch_edge, true_edge, false_edge, e;
405  basic_block switch_bb, unswitch_on_alt;
406  struct loop *nloop;
407  sbitmap zero_bitmap;
408  int irred_flag, prob;
409  rtx seq;
410
411  /* Some sanity checking.  */
412  gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
413  gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
414  gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
415  gcc_assert (!loop->inner);
416  gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
417  gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
418
419  entry = loop_preheader_edge (loop);
420
421  /* Make a copy.  */
422  irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
423  entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
424  zero_bitmap = sbitmap_alloc (2);
425  sbitmap_zero (zero_bitmap);
426  if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
427	zero_bitmap, NULL, NULL, NULL, 0))
428    {
429      sbitmap_free (zero_bitmap);
430      return NULL;
431    }
432  sbitmap_free (zero_bitmap);
433  entry->flags |= irred_flag;
434
435  /* Record the block with condition we unswitch on.  */
436  unswitch_on_alt = get_bb_copy (unswitch_on);
437  true_edge = BRANCH_EDGE (unswitch_on_alt);
438  false_edge = FALLTHRU_EDGE (unswitch_on);
439  latch_edge = single_succ_edge (get_bb_copy (loop->latch));
440
441  /* Create a block with the condition.  */
442  prob = true_edge->probability;
443  switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
444  seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
445			      block_label (true_edge->dest),
446			      prob, cinsn);
447  emit_insn_after (seq, BB_END (switch_bb));
448  e = make_edge (switch_bb, true_edge->dest, 0);
449  e->probability = prob;
450  e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
451  e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
452  e->probability = false_edge->probability;
453  e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
454
455  if (irred_flag)
456    {
457      switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
458      EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
459      EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
460    }
461  else
462    {
463      switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
464      EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
465      EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
466    }
467
468  /* Loopify from the copy of LOOP body, constructing the new loop.  */
469  nloop = loopify (loops, latch_edge,
470		   single_pred_edge (get_bb_copy (loop->header)), switch_bb,
471		   BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true);
472
473  /* Remove branches that are now unreachable in new loops.  */
474  remove_path (loops, true_edge);
475  remove_path (loops, false_edge);
476
477  /* One of created loops do not have to be subloop of the outer loop now,
478     so fix its placement in loop data structure.  */
479  fix_loop_placement (loop);
480  fix_loop_placement (nloop);
481
482  /* Preserve the simple loop preheaders.  */
483  loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
484  loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
485
486  return nloop;
487}
488