2014-01-24 Ed Smith-Rowland <3dw4rd@verizon.net>
[official-gcc.git] / gcc / loop-unswitch.c
blobfff0fd16e5272fe5bdd845fee33ef2ecf82c1f08
1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002-2014 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 "params.h"
30 #include "expr.h"
31 #include "dumpfile.h"
33 /* This pass moves constant conditions out of loops, duplicating the loop
34 in progress, i.e. this code:
36 while (loop_cond)
39 if (cond)
40 branch1;
41 else
42 branch2;
44 if (cond)
45 branch3;
48 where nothing inside the loop alters cond is transformed
49 into
51 if (cond)
53 while (loop_cond)
56 branch1;
58 branch3;
62 else
64 while (loop_cond)
67 branch2;
73 Duplicating the loop might lead to code growth exponential in number of
74 branches inside loop, so we limit the number of unswitchings performed
75 in a single loop to PARAM_MAX_UNSWITCH_LEVEL. We only perform the
76 transformation on innermost loops, as the benefit of doing it on loops
77 containing subloops would not be very large compared to complications
78 with handling this case. */
80 static struct loop *unswitch_loop (struct loop *, basic_block, rtx, rtx);
81 static bool unswitch_single_loop (struct loop *, rtx, int);
82 static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
84 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
85 true, with probability PROB. If CINSN is not NULL, it is the insn to copy
86 in order to create a jump. */
88 rtx
89 compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
90 rtx cinsn)
92 rtx seq, jump, cond;
93 enum machine_mode mode;
95 mode = GET_MODE (op0);
96 if (mode == VOIDmode)
97 mode = GET_MODE (op1);
99 start_sequence ();
100 if (GET_MODE_CLASS (mode) == MODE_CC)
102 /* A hack -- there seems to be no easy generic way how to make a
103 conditional jump from a ccmode comparison. */
104 gcc_assert (cinsn);
105 cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
106 gcc_assert (GET_CODE (cond) == comp);
107 gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
108 gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
109 emit_jump_insn (copy_insn (PATTERN (cinsn)));
110 jump = get_last_insn ();
111 gcc_assert (JUMP_P (jump));
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, -1);
124 jump = get_last_insn ();
125 gcc_assert (JUMP_P (jump));
126 JUMP_LABEL (jump) = label;
127 LABEL_NUSES (label)++;
129 add_int_reg_note (jump, REG_BR_PROB, prob);
131 seq = get_insns ();
132 end_sequence ();
134 return seq;
137 /* Main entry point. Perform loop unswitching on all suitable loops. */
138 void
139 unswitch_loops (void)
141 struct loop *loop;
142 bool changed = false;
144 /* Go through inner loops (only original ones). */
146 FOR_EACH_LOOP (loop, LI_ONLY_INNERMOST)
147 changed |= unswitch_single_loop (loop, NULL_RTX, 0);
149 iv_analysis_done ();
151 /* If we unswitched any loop discover new loops that are eventually
152 exposed by making irreducible regions reducible. */
153 if (changed)
155 calculate_dominance_info (CDI_DOMINATORS);
156 fix_loop_structure (NULL);
160 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
161 basic blocks (for what it means see comments below). In case condition
162 compares loop invariant cc mode register, return the jump in CINSN. */
164 static rtx
165 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
167 rtx test, at, op[2], stest;
168 struct rtx_iv iv;
169 unsigned i;
170 enum machine_mode mode;
172 /* BB must end in a simple conditional jump. */
173 if (EDGE_COUNT (bb->succs) != 2)
174 return NULL_RTX;
175 if (!any_condjump_p (BB_END (bb)))
176 return NULL_RTX;
178 /* With branches inside loop. */
179 if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
180 || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
181 return NULL_RTX;
183 /* It must be executed just once each iteration (because otherwise we
184 are unable to update dominator/irreducible loop information correctly). */
185 if (!just_once_each_iteration_p (loop, bb))
186 return NULL_RTX;
188 /* Condition must be invariant. */
189 test = get_condition (BB_END (bb), &at, true, false);
190 if (!test)
191 return NULL_RTX;
193 mode = VOIDmode;
194 for (i = 0; i < 2; i++)
196 op[i] = XEXP (test, i);
198 if (CONSTANT_P (op[i]))
199 continue;
201 if (!iv_analyze (at, op[i], &iv))
202 return NULL_RTX;
203 if (iv.step != const0_rtx
204 || iv.first_special)
205 return NULL_RTX;
207 op[i] = get_iv_value (&iv, const0_rtx);
208 if (iv.extend != IV_UNKNOWN_EXTEND
209 && iv.mode != iv.extend_mode)
210 op[i] = lowpart_subreg (iv.mode, op[i], iv.extend_mode);
211 if (mode == VOIDmode)
212 mode = iv.mode;
213 else
214 gcc_assert (mode == iv.mode);
217 if (GET_MODE_CLASS (mode) == MODE_CC)
219 if (at != BB_END (bb))
220 return NULL_RTX;
222 if (!rtx_equal_p (op[0], XEXP (test, 0))
223 || !rtx_equal_p (op[1], XEXP (test, 1)))
224 return NULL_RTX;
226 *cinsn = BB_END (bb);
227 return test;
230 stest = simplify_gen_relational (GET_CODE (test), SImode,
231 mode, op[0], op[1]);
232 if (stest == const0_rtx
233 || stest == const_true_rtx)
234 return stest;
236 return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
237 op[0], op[1]));
240 /* Reverses CONDition; returns NULL if we cannot. */
242 reversed_condition (rtx cond)
244 enum rtx_code reversed;
245 reversed = reversed_comparison_code (cond, NULL);
246 if (reversed == UNKNOWN)
247 return NULL_RTX;
248 else
249 return gen_rtx_fmt_ee (reversed,
250 GET_MODE (cond), XEXP (cond, 0),
251 XEXP (cond, 1));
254 /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
255 unswitched on and are therefore known to be true in this LOOP. NUM is
256 number of unswitchings done; do not allow it to grow too much, it is too
257 easy to create example on that the code would grow exponentially.
258 Returns true LOOP was unswitched. */
259 static bool
260 unswitch_single_loop (struct loop *loop, rtx cond_checked, int num)
262 basic_block *bbs;
263 struct loop *nloop;
264 unsigned i;
265 rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
266 int repeat;
267 edge e;
268 HOST_WIDE_INT iterations;
270 /* Do not unswitch too much. */
271 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
273 if (dump_file)
274 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
275 return false;
278 /* Only unswitch innermost loops. */
279 if (loop->inner)
281 if (dump_file)
282 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
283 return false;
286 /* We must be able to duplicate loop body. */
287 if (!can_duplicate_loop_p (loop))
289 if (dump_file)
290 fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
291 return false;
294 /* The loop should not be too large, to limit code growth. */
295 if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
297 if (dump_file)
298 fprintf (dump_file, ";; Not unswitching, loop too big\n");
299 return false;
302 /* Do not unswitch in cold areas. */
303 if (optimize_loop_for_size_p (loop))
305 if (dump_file)
306 fprintf (dump_file, ";; Not unswitching, not hot area\n");
307 return false;
310 /* Nor if the loop usually does not roll. */
311 iterations = get_estimated_loop_iterations_int (loop);
312 if (iterations >= 0 && iterations <= 1)
314 if (dump_file)
315 fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
316 return false;
321 repeat = 0;
322 cinsn = NULL_RTX;
324 /* Find a bb to unswitch on. */
325 bbs = get_loop_body (loop);
326 iv_analysis_loop_init (loop);
327 for (i = 0; i < loop->num_nodes; i++)
328 if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
329 break;
331 if (i == loop->num_nodes)
333 free (bbs);
334 return false;
337 if (cond != const0_rtx
338 && cond != const_true_rtx)
340 rcond = reversed_condition (cond);
341 if (rcond)
342 rcond = canon_condition (rcond);
344 /* Check whether the result can be predicted. */
345 for (acond = cond_checked; acond; acond = XEXP (acond, 1))
346 simplify_using_condition (XEXP (acond, 0), &cond, NULL);
349 if (cond == const_true_rtx)
351 /* Remove false path. */
352 e = FALLTHRU_EDGE (bbs[i]);
353 remove_path (e);
354 free (bbs);
355 repeat = 1;
357 else if (cond == const0_rtx)
359 /* Remove true path. */
360 e = BRANCH_EDGE (bbs[i]);
361 remove_path (e);
362 free (bbs);
363 repeat = 1;
365 } while (repeat);
367 /* We found the condition we can unswitch on. */
368 conds = alloc_EXPR_LIST (0, cond, cond_checked);
369 if (rcond)
370 rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
371 else
372 rconds = cond_checked;
374 if (dump_file)
375 fprintf (dump_file, ";; Unswitching loop\n");
377 /* Unswitch the loop on this condition. */
378 nloop = unswitch_loop (loop, bbs[i], copy_rtx_if_shared (cond), cinsn);
379 gcc_assert (nloop);
381 /* Invoke itself on modified loops. */
382 unswitch_single_loop (nloop, rconds, num + 1);
383 unswitch_single_loop (loop, conds, num + 1);
385 free_EXPR_LIST_node (conds);
386 if (rcond)
387 free_EXPR_LIST_node (rconds);
389 free (bbs);
391 return true;
394 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
395 unswitching of innermost loops. UNSWITCH_ON must be executed in every
396 iteration, i.e. it must dominate LOOP latch. COND is the condition
397 determining which loop is entered. Returns NULL if impossible, new loop
398 otherwise. The new loop is entered if COND is true. If CINSN is not
399 NULL, it is the insn in that COND is compared. */
401 static struct loop *
402 unswitch_loop (struct loop *loop, basic_block unswitch_on, rtx cond, rtx cinsn)
404 edge entry, latch_edge, true_edge, false_edge, e;
405 basic_block switch_bb, unswitch_on_alt;
406 struct loop *nloop;
407 int irred_flag, prob;
408 rtx seq;
410 /* Some sanity checking. */
411 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
412 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
413 gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
414 gcc_assert (!loop->inner);
415 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
416 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
418 entry = loop_preheader_edge (loop);
420 /* Make a copy. */
421 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
422 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
423 if (!duplicate_loop_to_header_edge (loop, entry, 1,
424 NULL, NULL, NULL, 0))
425 return NULL;
426 entry->flags |= irred_flag;
428 /* Record the block with condition we unswitch on. */
429 unswitch_on_alt = get_bb_copy (unswitch_on);
430 true_edge = BRANCH_EDGE (unswitch_on_alt);
431 false_edge = FALLTHRU_EDGE (unswitch_on);
432 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
434 /* Create a block with the condition. */
435 prob = true_edge->probability;
436 switch_bb = create_empty_bb (EXIT_BLOCK_PTR_FOR_FN (cfun)->prev_bb);
437 seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
438 block_label (true_edge->dest),
439 prob, cinsn);
440 emit_insn_after (seq, BB_END (switch_bb));
441 e = make_edge (switch_bb, true_edge->dest, 0);
442 e->probability = prob;
443 e->count = apply_probability (latch_edge->count, prob);
444 e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
445 e->probability = false_edge->probability;
446 e->count = apply_probability (latch_edge->count, false_edge->probability);
448 if (irred_flag)
450 switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
451 EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
452 EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
454 else
456 switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
457 EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
458 EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
461 /* Loopify from the copy of LOOP body, constructing the new loop. */
462 nloop = loopify (latch_edge,
463 single_pred_edge (get_bb_copy (loop->header)), switch_bb,
464 BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true,
465 prob, REG_BR_PROB_BASE - prob);
467 copy_loop_info (loop, nloop);
468 /* Remove branches that are now unreachable in new loops. */
469 remove_path (true_edge);
470 remove_path (false_edge);
472 /* Preserve the simple loop preheaders. */
473 split_edge (loop_preheader_edge (loop));
474 split_edge (loop_preheader_edge (nloop));
476 return nloop;