1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002, 2003, 2004 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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
27 #include "basic-block.h"
29 #include "cfglayout.h"
34 /* This pass moves constant conditions out of loops, duplicating the loop
35 in progress, i.e. this code:
49 where nothing inside the loop alters cond is transformed
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 loops
*, struct loop
*,
82 basic_block
, rtx
, rtx
);
83 static void unswitch_single_loop (struct loops
*, 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. */
108 cond
= XEXP (SET_SRC (pc_set (cinsn
)), 0);
109 if (GET_CODE (cond
) != comp
110 || !rtx_equal_p (op0
, XEXP (cond
, 0))
111 || !rtx_equal_p (op1
, XEXP (cond
, 1)))
113 emit_jump_insn (copy_insn (PATTERN (cinsn
)));
114 jump
= get_last_insn ();
115 JUMP_LABEL (jump
) = JUMP_LABEL (cinsn
);
116 LABEL_NUSES (JUMP_LABEL (jump
))++;
117 redirect_jump (jump
, label
, 0);
124 op0
= force_operand (op0
, NULL_RTX
);
125 op1
= force_operand (op1
, NULL_RTX
);
126 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
127 mode
, NULL_RTX
, NULL_RTX
, label
);
128 jump
= get_last_insn ();
129 JUMP_LABEL (jump
) = label
;
130 LABEL_NUSES (label
)++;
132 REG_NOTES (jump
) = gen_rtx_EXPR_LIST (REG_BR_PROB
, GEN_INT (prob
),
140 /* Main entry point. Perform loop unswitching on all suitable LOOPS. */
142 unswitch_loops (struct loops
*loops
)
147 /* Go through inner loops (only original ones). */
150 for (i
= 1; i
< num
; i
++)
153 loop
= loops
->parray
[i
];
160 unswitch_single_loop (loops
, loop
, NULL_RTX
, 0);
161 #ifdef ENABLE_CHECKING
162 verify_dominators (CDI_DOMINATORS
);
163 verify_loop_structure (loops
);
170 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
171 basic blocks (for what it means see comments below). In case condition
172 compares loop invariant cc mode register, return the jump in CINSN. */
175 may_unswitch_on (basic_block bb
, struct loop
*loop
, rtx
*cinsn
)
177 rtx test
, at
, insn
, op
[2];
180 enum machine_mode mode
;
182 /* BB must end in a simple conditional jump. */
183 if (!bb
->succ
|| !bb
->succ
->succ_next
|| bb
->succ
->succ_next
->succ_next
)
185 if (!any_condjump_p (BB_END (bb
)))
188 /* With branches inside loop. */
189 if (!flow_bb_inside_loop_p (loop
, bb
->succ
->dest
)
190 || !flow_bb_inside_loop_p (loop
, bb
->succ
->succ_next
->dest
))
193 /* It must be executed just once each iteration (because otherwise we
194 are unable to update dominator/irreducible loop information correctly). */
195 if (!just_once_each_iteration_p (loop
, bb
))
198 /* Condition must be invariant. */
199 test
= get_condition (BB_END (bb
), &at
, true);
203 for (i
= 0; i
< 2; i
++)
205 op
[i
] = XEXP (test
, i
);
207 if (CONSTANT_P (op
[i
]))
210 insn
= iv_get_reaching_def (at
, op
[i
]);
211 if (!iv_analyze (insn
, op
[i
], &iv
))
213 if (iv
.step
!= const0_rtx
217 op
[i
] = get_iv_value (&iv
, const0_rtx
);
220 mode
= GET_MODE (op
[0]);
221 if (mode
== VOIDmode
)
222 mode
= GET_MODE (op
[1]);
223 if (GET_MODE_CLASS (mode
) == MODE_CC
)
225 if (at
!= BB_END (bb
))
228 *cinsn
= BB_END (bb
);
229 if (!rtx_equal_p (op
[0], XEXP (test
, 0))
230 || !rtx_equal_p (op
[1], XEXP (test
, 1)))
236 return canon_condition (gen_rtx_fmt_ee (GET_CODE (test
), SImode
,
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
)
249 return gen_rtx_fmt_ee (reversed
,
250 GET_MODE (cond
), XEXP (cond
, 0),
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. */
259 unswitch_single_loop (struct loops
*loops
, struct loop
*loop
,
260 rtx cond_checked
, int num
)
265 rtx cond
, rcond
, conds
, rconds
, acond
, cinsn
= NULL_RTX
;
269 /* Do not unswitch too much. */
270 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
273 fprintf (dump_file
, ";; Not unswitching anymore, hit max level\n");
277 /* Only unswitch innermost loops. */
281 fprintf (dump_file
, ";; Not unswitching, not innermost loop\n");
285 /* We must be able to duplicate loop body. */
286 if (!can_duplicate_loop_p (loop
))
289 fprintf (dump_file
, ";; Not unswitching, can't duplicate loop\n");
293 /* The loop should not be too large, to limit code growth. */
294 if (num_loop_insns (loop
) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
297 fprintf (dump_file
, ";; Not unswitching, loop too big\n");
301 /* Do not unswitch in cold areas. */
302 if (!maybe_hot_bb_p (loop
->header
))
305 fprintf (dump_file
, ";; Not unswitching, not hot area\n");
309 /* Nor if the loop usually does not roll. */
310 if (expected_loop_iterations (loop
) < 1)
313 fprintf (dump_file
, ";; Not unswitching, loop iterations < 1\n");
321 /* Find a bb to unswitch on. */
322 bbs
= get_loop_body (loop
);
323 iv_analysis_loop_init (loop
);
324 for (i
= 0; i
< loop
->num_nodes
; i
++)
325 if ((cond
= may_unswitch_on (bbs
[i
], loop
, &cinsn
)))
328 if (i
== loop
->num_nodes
)
334 rcond
= reversed_condition (cond
);
336 rcond
= canon_condition (rcond
);
338 /* Check whether the result can be predicted. */
339 for (acond
= cond_checked
; acond
; acond
= XEXP (acond
, 1))
340 simplify_using_condition (XEXP (acond
, 0), &cond
, NULL
);
342 if (cond
== const_true_rtx
)
344 /* Remove false path. */
345 e
= FALLTHRU_EDGE (bbs
[i
]);
346 remove_path (loops
, e
);
350 else if (cond
== const0_rtx
)
352 /* Remove true path. */
353 e
= BRANCH_EDGE (bbs
[i
]);
354 remove_path (loops
, e
);
360 /* We found the condition we can unswitch on. */
361 conds
= alloc_EXPR_LIST (0, cond
, cond_checked
);
363 rconds
= alloc_EXPR_LIST (0, rcond
, cond_checked
);
365 rconds
= cond_checked
;
368 fprintf (dump_file
, ";; Unswitching loop\n");
370 /* Unswitch the loop on this condition. */
371 nloop
= unswitch_loop (loops
, loop
, bbs
[i
], cond
, cinsn
);
375 /* Invoke itself on modified loops. */
376 unswitch_single_loop (loops
, nloop
, rconds
, num
+ 1);
377 unswitch_single_loop (loops
, loop
, conds
, num
+ 1);
379 free_EXPR_LIST_node (conds
);
381 free_EXPR_LIST_node (rconds
);
386 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
387 unswitching of innermost loops. UNSWITCH_ON must be executed in every
388 iteration, i.e. it must dominate LOOP latch. COND is the condition
389 determining which loop is entered. Returns NULL if impossible, new loop
390 otherwise. The new loop is entered if COND is true. If CINSN is not
391 NULL, it is the insn in that COND is compared. */
394 unswitch_loop (struct loops
*loops
, struct loop
*loop
, basic_block unswitch_on
,
397 edge entry
, latch_edge
, true_edge
, false_edge
, e
;
398 basic_block switch_bb
, unswitch_on_alt
, src
;
401 int irred_flag
, prob
;
404 /* Some sanity checking. */
405 if (!flow_bb_inside_loop_p (loop
, unswitch_on
))
407 if (!unswitch_on
->succ
|| !unswitch_on
->succ
->succ_next
||
408 unswitch_on
->succ
->succ_next
->succ_next
)
410 if (!just_once_each_iteration_p (loop
, unswitch_on
))
414 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->dest
))
416 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->succ_next
->dest
))
419 entry
= loop_preheader_edge (loop
);
423 irred_flag
= entry
->flags
& EDGE_IRREDUCIBLE_LOOP
;
424 entry
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
425 zero_bitmap
= sbitmap_alloc (2);
426 sbitmap_zero (zero_bitmap
);
427 if (!duplicate_loop_to_header_edge (loop
, entry
, loops
, 1,
428 zero_bitmap
, NULL
, NULL
, NULL
, 0))
431 entry
->flags
|= irred_flag
;
433 /* Record the block with condition we unswitch on. */
434 unswitch_on_alt
= unswitch_on
->rbi
->copy
;
435 true_edge
= BRANCH_EDGE (unswitch_on_alt
);
436 false_edge
= FALLTHRU_EDGE (unswitch_on
);
437 latch_edge
= loop
->latch
->rbi
->copy
->succ
;
439 /* Create a block with the condition. */
440 prob
= true_edge
->probability
;
441 switch_bb
= create_empty_bb (EXIT_BLOCK_PTR
->prev_bb
);
442 seq
= compare_and_jump_seq (XEXP (cond
, 0), XEXP (cond
, 1), GET_CODE (cond
),
443 block_label (true_edge
->dest
),
445 emit_insn_after (seq
, BB_END (switch_bb
));
446 e
= make_edge (switch_bb
, true_edge
->dest
, 0);
447 e
->probability
= prob
;
448 e
->count
= latch_edge
->count
* prob
/ REG_BR_PROB_BASE
;
449 e
= make_edge (switch_bb
, FALLTHRU_EDGE (unswitch_on
)->dest
, EDGE_FALLTHRU
);
450 e
->probability
= false_edge
->probability
;
451 e
->count
= latch_edge
->count
* (false_edge
->probability
) / REG_BR_PROB_BASE
;
455 switch_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
456 switch_bb
->succ
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
457 switch_bb
->succ
->succ_next
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
461 switch_bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
462 switch_bb
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
463 switch_bb
->succ
->succ_next
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
466 /* Loopify from the copy of LOOP body, constructing the new loop. */
467 nloop
= loopify (loops
, latch_edge
,
468 loop
->header
->rbi
->copy
->pred
, switch_bb
);
470 /* Remove branches that are now unreachable in new loops. */
471 remove_path (loops
, true_edge
);
472 remove_path (loops
, 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 loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
481 loop_split_edge_with (loop_preheader_edge (nloop
), NULL_RTX
);