1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005 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 2, or (at your option) any later
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
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
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
35 /* This pass moves constant conditions out of loops, duplicating the loop
36 in progress, i.e. this code:
50 where nothing inside the loop alters cond is transformed
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. */
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
*);
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. */
91 compare_and_jump_seq (rtx op0
, rtx op1
, enum rtx_code comp
, rtx label
, int prob
,
95 enum machine_mode mode
;
97 mode
= GET_MODE (op0
);
99 mode
= GET_MODE (op1
);
102 if (GET_MODE_CLASS (mode
) == MODE_CC
)
104 /* A hack -- there seems to be no easy generic way how to make a
105 conditional jump from a ccmode comparison. */
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);
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
)++;
129 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
, GEN_INT (prob
),
137 /* Main entry point. Perform loop unswitching on all suitable loops. */
139 unswitch_loops (void)
144 /* Go through inner loops (only original ones). */
145 num
= current_loops
->num
;
147 for (i
= 1; i
< num
; i
++)
150 loop
= current_loops
->parray
[i
];
157 unswitch_single_loop (loop
, NULL_RTX
, 0);
158 #ifdef ENABLE_CHECKING
159 verify_dominators (CDI_DOMINATORS
);
160 verify_loop_structure ();
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. */
172 may_unswitch_on (basic_block bb
, struct loop
*loop
, rtx
*cinsn
)
174 rtx test
, at
, op
[2], stest
;
177 enum machine_mode mode
;
179 /* BB must end in a simple conditional jump. */
180 if (EDGE_COUNT (bb
->succs
) != 2)
182 if (!any_condjump_p (BB_END (bb
)))
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
))
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
))
195 /* Condition must be invariant. */
196 test
= get_condition (BB_END (bb
), &at
, true, false);
200 for (i
= 0; i
< 2; i
++)
202 op
[i
] = XEXP (test
, i
);
204 if (CONSTANT_P (op
[i
]))
207 if (!iv_analyze (at
, op
[i
], &iv
))
209 if (iv
.step
!= const0_rtx
213 op
[i
] = get_iv_value (&iv
, const0_rtx
);
216 mode
= GET_MODE (op
[0]);
217 if (mode
== VOIDmode
)
218 mode
= GET_MODE (op
[1]);
219 if (GET_MODE_CLASS (mode
) == MODE_CC
)
221 if (at
!= BB_END (bb
))
224 if (!rtx_equal_p (op
[0], XEXP (test
, 0))
225 || !rtx_equal_p (op
[1], XEXP (test
, 1)))
228 *cinsn
= BB_END (bb
);
232 stest
= simplify_gen_relational (GET_CODE (test
), SImode
,
234 if (stest
== const0_rtx
235 || stest
== const_true_rtx
)
238 return canon_condition (gen_rtx_fmt_ee (GET_CODE (test
), SImode
,
242 /* Reverses CONDition; returns NULL if we cannot. */
244 reversed_condition (rtx cond
)
246 enum rtx_code reversed
;
247 reversed
= reversed_comparison_code (cond
, NULL
);
248 if (reversed
== UNKNOWN
)
251 return gen_rtx_fmt_ee (reversed
,
252 GET_MODE (cond
), XEXP (cond
, 0),
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. */
261 unswitch_single_loop (struct loop
*loop
, rtx cond_checked
, int num
)
266 rtx cond
, rcond
= NULL_RTX
, conds
, rconds
, acond
, cinsn
;
270 /* Do not unswitch too much. */
271 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
274 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
278 /* Only unswitch innermost loops. */
282 fprintf (dump_file
, ";; Not unswitching, not innermost loop\n");
286 /* We must be able to duplicate loop body. */
287 if (!can_duplicate_loop_p (loop
))
290 fprintf (dump_file
, ";; Not unswitching, can't duplicate loop\n");
294 /* The loop should not be too large, to limit code growth. */
295 if (num_loop_insns (loop
) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
298 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
302 /* Do not unswitch in cold areas. */
303 if (!maybe_hot_bb_p (loop
->header
))
306 fprintf (dump_file
, ";; Not unswitching, not hot area\n");
310 /* Nor if the loop usually does not roll. */
311 if (expected_loop_iterations (loop
) < 1)
314 fprintf (dump_file
, ";; Not unswitching, loop iterations < 1\n");
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
)))
330 if (i
== loop
->num_nodes
)
336 if (cond
!= const0_rtx
337 && cond
!= const_true_rtx
)
339 rcond
= reversed_condition (cond
);
341 rcond
= canon_condition (rcond
);
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
);
348 if (cond
== const_true_rtx
)
350 /* Remove false path. */
351 e
= FALLTHRU_EDGE (bbs
[i
]);
356 else if (cond
== const0_rtx
)
358 /* Remove true path. */
359 e
= BRANCH_EDGE (bbs
[i
]);
366 /* We found the condition we can unswitch on. */
367 conds
= alloc_EXPR_LIST (0, cond
, cond_checked
);
369 rconds
= alloc_EXPR_LIST (0, rcond
, cond_checked
);
371 rconds
= cond_checked
;
374 fprintf (dump_file
, ";; Unswitching loop\n");
376 /* Unswitch the loop on this condition. */
377 nloop
= unswitch_loop (loop
, bbs
[i
], cond
, cinsn
);
380 /* Invoke itself on modified loops. */
381 unswitch_single_loop (nloop
, rconds
, num
+ 1);
382 unswitch_single_loop (loop
, conds
, num
+ 1);
384 free_EXPR_LIST_node (conds
);
386 free_EXPR_LIST_node (rconds
);
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. */
399 unswitch_loop (struct loop
*loop
, basic_block unswitch_on
, rtx cond
, rtx cinsn
)
401 edge entry
, latch_edge
, true_edge
, false_edge
, e
;
402 basic_block switch_bb
, unswitch_on_alt
;
405 int irred_flag
, prob
;
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
));
416 entry
= loop_preheader_edge (loop
);
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))
426 sbitmap_free (zero_bitmap
);
429 sbitmap_free (zero_bitmap
);
430 entry
->flags
|= irred_flag
;
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
));
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
),
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
;
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
;
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
;
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);
470 /* Remove branches that are now unreachable in new loops. */
471 remove_path (true_edge
);
472 remove_path (false_edge
);
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
);
479 /* Preserve the simple loop preheaders. */
480 split_edge (loop_preheader_edge (loop
));
481 split_edge (loop_preheader_edge (nloop
));