Daily bump.
[official-gcc.git] / gcc / loop-unswitch.c
blob54c39a5698ac142ad6619acf89b35eb260d4ef4d
1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005, 2007 Free Software Foundation, Inc.
4 This file is part of GCC.
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 3, or (at your option) any later
9 version.
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.
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/>. */
20 #include "config.h"
21 #include "system.h"
22 #include "coretypes.h"
23 #include "tm.h"
24 #include "rtl.h"
25 #include "hard-reg-set.h"
26 #include "obstack.h"
27 #include "basic-block.h"
28 #include "cfgloop.h"
29 #include "cfglayout.h"
30 #include "params.h"
31 #include "output.h"
32 #include "expr.h"
34 /* This pass moves constant conditions out of loops, duplicating the loop
35 in progress, i.e. this code:
37 while (loop_cond)
40 if (cond)
41 branch1;
42 else
43 branch2;
45 if (cond)
46 branch3;
49 where nothing inside the loop alters cond is transformed
50 into
52 if (cond)
54 while (loop_cond)
57 branch1;
59 branch3;
63 else
65 while (loop_cond)
68 branch2;
74 Duplicating the loop might lead to code growth exponential in number of
75 branches inside loop, so we limit the number of unswitchings performed
76 in a single loop to PARAM_MAX_UNSWITCH_LEVEL. We only perform the
77 transformation on innermost loops, as the benefit of doing it on loops
78 containing subloops would not be very large compared to complications
79 with handling this case. */
81 static struct loop *unswitch_loop (struct loop *, basic_block, rtx, rtx);
82 static void unswitch_single_loop (struct loop *, rtx, int);
83 static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
85 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
86 true, with probability PROB. If CINSN is not NULL, it is the insn to copy
87 in order to create a jump. */
89 rtx
90 compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
91 rtx cinsn)
93 rtx seq, jump, cond;
94 enum machine_mode mode;
96 mode = GET_MODE (op0);
97 if (mode == VOIDmode)
98 mode = GET_MODE (op1);
100 start_sequence ();
101 if (GET_MODE_CLASS (mode) == MODE_CC)
103 /* A hack -- there seems to be no easy generic way how to make a
104 conditional jump from a ccmode comparison. */
105 gcc_assert (cinsn);
106 cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
107 gcc_assert (GET_CODE (cond) == comp);
108 gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
109 gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
110 emit_jump_insn (copy_insn (PATTERN (cinsn)));
111 jump = get_last_insn ();
112 JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
113 LABEL_NUSES (JUMP_LABEL (jump))++;
114 redirect_jump (jump, label, 0);
116 else
118 gcc_assert (!cinsn);
120 op0 = force_operand (op0, NULL_RTX);
121 op1 = force_operand (op1, NULL_RTX);
122 do_compare_rtx_and_jump (op0, op1, comp, 0,
123 mode, NULL_RTX, NULL_RTX, label);
124 jump = get_last_insn ();
125 JUMP_LABEL (jump) = label;
126 LABEL_NUSES (label)++;
128 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
129 REG_NOTES (jump));
130 seq = get_insns ();
131 end_sequence ();
133 return seq;
136 /* Main entry point. Perform loop unswitching on all suitable loops. */
137 void
138 unswitch_loops (void)
140 loop_iterator li;
141 struct loop *loop;
143 /* Go through inner loops (only original ones). */
145 FOR_EACH_LOOP (li, loop, LI_ONLY_INNERMOST)
147 unswitch_single_loop (loop, NULL_RTX, 0);
148 #ifdef ENABLE_CHECKING
149 verify_dominators (CDI_DOMINATORS);
150 verify_loop_structure ();
151 #endif
154 iv_analysis_done ();
157 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
158 basic blocks (for what it means see comments below). In case condition
159 compares loop invariant cc mode register, return the jump in CINSN. */
161 static rtx
162 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
164 rtx test, at, op[2], stest;
165 struct rtx_iv iv;
166 unsigned i;
167 enum machine_mode mode;
169 /* BB must end in a simple conditional jump. */
170 if (EDGE_COUNT (bb->succs) != 2)
171 return NULL_RTX;
172 if (!any_condjump_p (BB_END (bb)))
173 return NULL_RTX;
175 /* With branches inside loop. */
176 if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
177 || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
178 return NULL_RTX;
180 /* It must be executed just once each iteration (because otherwise we
181 are unable to update dominator/irreducible loop information correctly). */
182 if (!just_once_each_iteration_p (loop, bb))
183 return NULL_RTX;
185 /* Condition must be invariant. */
186 test = get_condition (BB_END (bb), &at, true, false);
187 if (!test)
188 return NULL_RTX;
190 for (i = 0; i < 2; i++)
192 op[i] = XEXP (test, i);
194 if (CONSTANT_P (op[i]))
195 continue;
197 if (!iv_analyze (at, op[i], &iv))
198 return NULL_RTX;
199 if (iv.step != const0_rtx
200 || iv.first_special)
201 return NULL_RTX;
203 op[i] = get_iv_value (&iv, const0_rtx);
206 mode = GET_MODE (op[0]);
207 if (mode == VOIDmode)
208 mode = GET_MODE (op[1]);
209 if (GET_MODE_CLASS (mode) == MODE_CC)
211 if (at != BB_END (bb))
212 return NULL_RTX;
214 if (!rtx_equal_p (op[0], XEXP (test, 0))
215 || !rtx_equal_p (op[1], XEXP (test, 1)))
216 return NULL_RTX;
218 *cinsn = BB_END (bb);
219 return test;
222 stest = simplify_gen_relational (GET_CODE (test), SImode,
223 mode, op[0], op[1]);
224 if (stest == const0_rtx
225 || stest == const_true_rtx)
226 return stest;
228 return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
229 op[0], op[1]));
232 /* Reverses CONDition; returns NULL if we cannot. */
234 reversed_condition (rtx cond)
236 enum rtx_code reversed;
237 reversed = reversed_comparison_code (cond, NULL);
238 if (reversed == UNKNOWN)
239 return NULL_RTX;
240 else
241 return gen_rtx_fmt_ee (reversed,
242 GET_MODE (cond), XEXP (cond, 0),
243 XEXP (cond, 1));
246 /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
247 unswitched on and are therefore known to be true in this LOOP. NUM is
248 number of unswitchings done; do not allow it to grow too much, it is too
249 easy to create example on that the code would grow exponentially. */
250 static void
251 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
253 basic_block *bbs;
254 struct loop *nloop;
255 unsigned i;
256 rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
257 int repeat;
258 edge e;
260 /* Do not unswitch too much. */
261 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
263 if (dump_file)
264 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
265 return;
268 /* Only unswitch innermost loops. */
269 if (loop->inner)
271 if (dump_file)
272 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
273 return;
276 /* We must be able to duplicate loop body. */
277 if (!can_duplicate_loop_p (loop))
279 if (dump_file)
280 fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
281 return;
284 /* The loop should not be too large, to limit code growth. */
285 if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
287 if (dump_file)
288 fprintf (dump_file, ";; Not unswitching, loop too big\n");
289 return;
292 /* Do not unswitch in cold areas. */
293 if (!maybe_hot_bb_p (loop->header))
295 if (dump_file)
296 fprintf (dump_file, ";; Not unswitching, not hot area\n");
297 return;
300 /* Nor if the loop usually does not roll. */
301 if (expected_loop_iterations (loop) < 1)
303 if (dump_file)
304 fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
305 return;
310 repeat = 0;
311 cinsn = NULL_RTX;
313 /* Find a bb to unswitch on. */
314 bbs = get_loop_body (loop);
315 iv_analysis_loop_init (loop);
316 for (i = 0; i < loop->num_nodes; i++)
317 if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
318 break;
320 if (i == loop->num_nodes)
322 free (bbs);
323 return;
326 if (cond != const0_rtx
327 && cond != const_true_rtx)
329 rcond = reversed_condition (cond);
330 if (rcond)
331 rcond = canon_condition (rcond);
333 /* Check whether the result can be predicted. */
334 for (acond = cond_checked; acond; acond = XEXP (acond, 1))
335 simplify_using_condition (XEXP (acond, 0), &cond, NULL);
338 if (cond == const_true_rtx)
340 /* Remove false path. */
341 e = FALLTHRU_EDGE (bbs[i]);
342 remove_path (e);
343 free (bbs);
344 repeat = 1;
346 else if (cond == const0_rtx)
348 /* Remove true path. */
349 e = BRANCH_EDGE (bbs[i]);
350 remove_path (e);
351 free (bbs);
352 repeat = 1;
354 } while (repeat);
356 /* We found the condition we can unswitch on. */
357 conds = alloc_EXPR_LIST (0, cond, cond_checked);
358 if (rcond)
359 rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
360 else
361 rconds = cond_checked;
363 if (dump_file)
364 fprintf (dump_file, ";; Unswitching loop\n");
366 /* Unswitch the loop on this condition. */
367 nloop = unswitch_loop (loop, bbs[i], cond, cinsn);
368 gcc_assert (nloop);
370 /* Invoke itself on modified loops. */
371 unswitch_single_loop (nloop, rconds, num + 1);
372 unswitch_single_loop (loop, conds, num + 1);
374 free_EXPR_LIST_node (conds);
375 if (rcond)
376 free_EXPR_LIST_node (rconds);
378 free (bbs);
381 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
382 unswitching of innermost loops. UNSWITCH_ON must be executed in every
383 iteration, i.e. it must dominate LOOP latch. COND is the condition
384 determining which loop is entered. Returns NULL if impossible, new loop
385 otherwise. The new loop is entered if COND is true. If CINSN is not
386 NULL, it is the insn in that COND is compared. */
388 static struct loop *
389 unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
391 edge entry, latch_edge, true_edge, false_edge, e;
392 basic_block switch_bb, unswitch_on_alt;
393 struct loop *nloop;
394 sbitmap zero_bitmap;
395 int irred_flag, prob;
396 rtx seq;
398 /* Some sanity checking. */
399 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
400 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
401 gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
402 gcc_assert (!loop->inner);
403 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
404 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
406 entry = loop_preheader_edge (loop);
408 /* Make a copy. */
409 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
410 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
411 zero_bitmap = sbitmap_alloc (2);
412 if (!duplicate_loop_to_header_edge (loop, entry, 1,
413 NULL, NULL, NULL, 0))
414 return NULL;
415 entry->flags |= irred_flag;
417 /* Record the block with condition we unswitch on. */
418 unswitch_on_alt = get_bb_copy (unswitch_on);
419 true_edge = BRANCH_EDGE (unswitch_on_alt);
420 false_edge = FALLTHRU_EDGE (unswitch_on);
421 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
423 /* Create a block with the condition. */
424 prob = true_edge->probability;
425 switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
426 seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
427 block_label (true_edge->dest),
428 prob, cinsn);
429 emit_insn_after (seq, BB_END (switch_bb));
430 e = make_edge (switch_bb, true_edge->dest, 0);
431 e->probability = prob;
432 e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
433 e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
434 e->probability = false_edge->probability;
435 e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
437 if (irred_flag)
439 switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
440 EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
441 EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
443 else
445 switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
446 EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
447 EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
450 /* Loopify from the copy of LOOP body, constructing the new loop. */
451 nloop = loopify (latch_edge,
452 single_pred_edge (get_bb_copy (loop->header)), switch_bb,
453 BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true,
454 prob, REG_BR_PROB_BASE - prob);
456 /* Remove branches that are now unreachable in new loops. */
457 remove_path (true_edge);
458 remove_path (false_edge);
460 /* Preserve the simple loop preheaders. */
461 split_edge (loop_preheader_edge (loop));
462 split_edge (loop_preheader_edge (nloop));
464 return nloop;