1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002, 2003 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
*,
83 static void unswitch_single_loop (struct loops
*, struct loop
*, rtx
, int);
84 static bool may_unswitch_on_p (struct loops
*, basic_block
, struct loop
*,
86 static rtx
reversed_condition (rtx
);
88 /* Main entry point. Perform loop unswitching on all suitable LOOPS. */
90 unswitch_loops (struct loops
*loops
)
95 /* Go through inner loops (only original ones). */
98 for (i
= 1; i
< num
; i
++)
101 loop
= loops
->parray
[i
];
108 unswitch_single_loop (loops
, loop
, NULL_RTX
, 0);
109 #ifdef ENABLE_CHECKING
110 verify_dominators (loops
->cfg
.dom
);
111 verify_loop_structure (loops
);
116 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
117 basic blocks (for what it means see comments below). List of basic blocks
118 inside LOOP is provided in BODY to save time. */
120 may_unswitch_on_p (struct loops
*loops
, basic_block bb
, struct loop
*loop
,
126 /* BB must end in a simple conditional jump. */
127 if (!bb
->succ
|| !bb
->succ
->succ_next
|| bb
->succ
->succ_next
->succ_next
)
129 if (!any_condjump_p (BB_END (bb
)))
132 /* With branches inside loop. */
133 if (!flow_bb_inside_loop_p (loop
, bb
->succ
->dest
)
134 || !flow_bb_inside_loop_p (loop
, bb
->succ
->succ_next
->dest
))
137 /* It must be executed just once each iteration (because otherwise we
138 are unable to update dominator/irreducible loop information correctly). */
139 if (!just_once_each_iteration_p (loops
, loop
, bb
))
142 /* Condition must be invariant. We use just a stupid test of invariantness
143 of the condition: all used regs must not be modified inside loop body. */
144 test
= get_condition (BB_END (bb
), NULL
, true);
148 for (i
= 0; i
< loop
->num_nodes
; i
++)
149 if (modified_between_p (test
, BB_HEAD (body
[i
]), NEXT_INSN (BB_END (body
[i
]))))
155 /* Reverses CONDition; returns NULL if we cannot. */
157 reversed_condition (rtx cond
)
159 enum rtx_code reversed
;
160 reversed
= reversed_comparison_code (cond
, NULL
);
161 if (reversed
== UNKNOWN
)
164 return gen_rtx_fmt_ee (reversed
,
165 GET_MODE (cond
), XEXP (cond
, 0),
169 /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
170 unswitched on and are therefore known to be true in this LOOP. NUM is
171 number of unswitchings done; do not allow it to grow too much, it is too
172 easy to create example on that the code would grow exponentially. */
174 unswitch_single_loop (struct loops
*loops
, struct loop
*loop
,
175 rtx cond_checked
, int num
)
177 basic_block
*bbs
, bb
;
181 rtx cond
, rcond
, conds
, rconds
, acond
, split_before
;
187 /* Do not unswitch too much. */
188 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
191 fprintf (rtl_dump_file
, ";; Not unswitching anymore, hit max level\n");
195 /* Only unswitch innermost loops. */
199 fprintf (rtl_dump_file
, ";; Not unswitching, not innermost loop\n");
203 /* We must be able to duplicate loop body. */
204 if (!can_duplicate_loop_p (loop
))
207 fprintf (rtl_dump_file
, ";; Not unswitching, can't duplicate loop\n");
211 /* The loop should not be too large, to limit code growth. */
212 if (num_loop_insns (loop
) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
215 fprintf (rtl_dump_file
, ";; Not unswitching, loop too big\n");
219 /* Do not unswitch in cold areas. */
220 if (!maybe_hot_bb_p (loop
->header
))
223 fprintf (rtl_dump_file
, ";; Not unswitching, not hot area\n");
227 /* Nor if the loop usually does not roll. */
228 if (expected_loop_iterations (loop
) < 1)
231 fprintf (rtl_dump_file
, ";; Not unswitching, loop iterations < 1\n");
239 /* Find a bb to unswitch on. */
240 bbs
= get_loop_body (loop
);
241 for (i
= 0; i
< loop
->num_nodes
; i
++)
242 if (may_unswitch_on_p (loops
, bbs
[i
], loop
, bbs
))
245 if (i
== loop
->num_nodes
)
251 if (!(cond
= get_condition (BB_END (bbs
[i
]), &split_before
, true)))
253 rcond
= reversed_condition (cond
);
255 /* Check whether the result can be predicted. */
258 for (acond
= cond_checked
; acond
; acond
= XEXP (acond
, 1))
260 if (rtx_equal_p (cond
, XEXP (acond
, 0)))
265 if (rtx_equal_p (rcond
, XEXP (acond
, 0)))
274 /* Remove false path. */
275 for (e
= bbs
[i
]->succ
; !(e
->flags
& EDGE_FALLTHRU
); e
= e
->succ_next
);
276 remove_path (loops
, e
);
280 else if (always_false
)
282 /* Remove true path. */
283 for (e
= bbs
[i
]->succ
; e
->flags
& EDGE_FALLTHRU
; e
= e
->succ_next
);
284 remove_path (loops
, e
);
290 /* We found the condition we can unswitch on. */
291 conds
= alloc_EXPR_LIST (0, cond
, cond_checked
);
293 rconds
= alloc_EXPR_LIST (0, rcond
, cond_checked
);
295 rconds
= cond_checked
;
297 /* Separate condition in a single basic block. */
298 bb
= split_loop_bb (loops
, bbs
[i
], PREV_INSN (split_before
))->dest
;
300 true_first
= !(bb
->succ
->flags
& EDGE_FALLTHRU
);
302 fprintf (rtl_dump_file
, ";; Unswitching loop\n");
304 /* Unswitch the loop on this condition. */
305 nloop
= unswitch_loop (loops
, loop
, bb
);
309 /* Invoke itself on modified loops. */
310 unswitch_single_loop (loops
, nloop
, true_first
? conds
: rconds
, num
+ 1);
311 unswitch_single_loop (loops
, loop
, true_first
? rconds
: conds
, num
+ 1);
313 free_EXPR_LIST_node (conds
);
315 free_EXPR_LIST_node (rconds
);
318 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
319 unswitching of innermost loops. UNSWITCH_ON must be executed in every
320 iteration, i.e. it must dominate LOOP latch, and should only contain code
321 for the condition we unswitch on. Returns NULL if impossible, new
324 unswitch_loop (struct loops
*loops
, struct loop
*loop
, basic_block unswitch_on
)
326 edge entry
, latch_edge
;
327 basic_block switch_bb
, unswitch_on_alt
, src
;
332 /* Some sanity checking. */
333 if (!flow_bb_inside_loop_p (loop
, unswitch_on
))
335 if (!unswitch_on
->succ
|| !unswitch_on
->succ
->succ_next
||
336 unswitch_on
->succ
->succ_next
->succ_next
)
338 if (!just_once_each_iteration_p (loops
, loop
, unswitch_on
))
342 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->dest
))
344 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->succ_next
->dest
))
347 /* Will we be able to perform redirection? */
348 if (!any_condjump_p (BB_END (unswitch_on
)))
350 if (!cfg_layout_can_duplicate_bb_p (unswitch_on
))
353 entry
= loop_preheader_edge (loop
);
357 irred_flag
= entry
->flags
& EDGE_IRREDUCIBLE_LOOP
;
358 entry
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
359 zero_bitmap
= sbitmap_alloc (2);
360 sbitmap_zero (zero_bitmap
);
361 if (!duplicate_loop_to_header_edge (loop
, entry
, loops
, 1,
362 zero_bitmap
, NULL
, NULL
, NULL
, 0))
365 entry
->flags
|= irred_flag
;
367 /* Record the block with condition we unswitch on. */
368 unswitch_on_alt
= unswitch_on
->rbi
->copy
;
370 /* Make a copy of the block containing the condition; we will use
371 it as switch to decide which loop we want to use. */
372 switch_bb
= cfg_layout_duplicate_bb (unswitch_on
, NULL
);
375 switch_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
376 switch_bb
->succ
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
377 switch_bb
->succ
->succ_next
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
381 switch_bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
382 switch_bb
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
383 switch_bb
->succ
->succ_next
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
385 add_to_dominance_info (loops
->cfg
.dom
, switch_bb
);
386 unswitch_on
->rbi
->copy
= unswitch_on_alt
;
388 /* Loopify from the copy of LOOP body, constructing the new loop. */
389 for (latch_edge
= loop
->latch
->rbi
->copy
->succ
;
390 latch_edge
->dest
!= loop
->header
;
391 latch_edge
= latch_edge
->succ_next
);
392 nloop
= loopify (loops
, latch_edge
,
393 loop
->header
->rbi
->copy
->pred
, switch_bb
);
395 /* Remove branches that are now unreachable in new loops. We rely on the
396 fact that cfg_layout_duplicate_bb reverses list of edges. */
397 remove_path (loops
, unswitch_on
->succ
);
398 remove_path (loops
, unswitch_on_alt
->succ
);
400 /* One of created loops do not have to be subloop of the outer loop now,
401 so fix its placement in loop data structure. */
402 fix_loop_placement (loop
);
403 fix_loop_placement (nloop
);