OSDN Git Service

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