1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002 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
PARAMS ((struct loops
*,
82 struct loop
*, basic_block
));
83 static void unswitch_single_loop
PARAMS ((struct loops
*, struct loop
*,
85 static bool may_unswitch_on_p
PARAMS ((struct loops
*, basic_block
,
86 struct loop
*, basic_block
*));
87 static rtx reversed_condition
PARAMS ((rtx
));
89 /* Main entry point. Perform loop unswitching on all suitable LOOPS. */
91 unswitch_loops (loops
)
97 /* Go through inner loops (only original ones). */
100 for (i
= 1; i
< num
; i
++)
103 loop
= loops
->parray
[i
];
110 unswitch_single_loop (loops
, loop
, NULL_RTX
, 0);
111 #ifdef ENABLE_CHECKING
112 verify_dominators (loops
->cfg
.dom
);
113 verify_loop_structure (loops
);
118 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
119 basic blocks (for what it means see comments below). List of basic blocks
120 inside LOOP is provided in BODY to save time. */
122 may_unswitch_on_p (loops
, bb
, loop
, body
)
131 /* BB must end in a simple conditional jump. */
132 if (!bb
->succ
|| !bb
->succ
->succ_next
|| bb
->succ
->succ_next
->succ_next
)
134 if (!any_condjump_p (bb
->end
))
137 /* With branches inside loop. */
138 if (!flow_bb_inside_loop_p (loop
, bb
->succ
->dest
)
139 || !flow_bb_inside_loop_p (loop
, bb
->succ
->succ_next
->dest
))
142 /* It must be executed just once each iteration (because otherwise we
143 are unable to update dominator/irreducible loop information correctly). */
144 if (!just_once_each_iteration_p (loops
, loop
, bb
))
147 /* Condition must be invariant. We use just a stupid test of invariantness
148 of the condition: all used regs must not be modified inside loop body. */
149 test
= get_condition (bb
->end
, NULL
);
153 for (i
= 0; i
< loop
->num_nodes
; i
++)
154 if (modified_between_p (test
, body
[i
]->head
, NEXT_INSN (body
[i
]->end
)))
160 /* Reverses CONDition; returns NULL if we cannot. */
162 reversed_condition (cond
)
165 enum rtx_code reversed
;
166 reversed
= reversed_comparison_code (cond
, NULL
);
167 if (reversed
== UNKNOWN
)
170 return gen_rtx_fmt_ee (reversed
,
171 GET_MODE (cond
), XEXP (cond
, 0),
175 /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
176 unswitched on and are therefore known to be true in this LOOP. NUM is
177 number of unswitchings done; do not allow it to grow too much, it is too
178 easy to create example on that the code would grow exponentially. */
180 unswitch_single_loop (loops
, loop
, cond_checked
, num
)
186 basic_block
*bbs
, bb
;
190 rtx cond
, rcond
, conds
, rconds
, acond
, split_before
;
196 /* Do not unswitch too much. */
197 if (num
> PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL
))
200 fprintf (rtl_dump_file
, ";; Not unswitching anymore, hit max level\n");
204 /* Only unswitch innermost loops. */
208 fprintf (rtl_dump_file
, ";; Not unswitching, not innermost loop\n");
212 /* We must be able to duplicate loop body. */
213 if (!can_duplicate_loop_p (loop
))
216 fprintf (rtl_dump_file
, ";; Not unswitching, can't duplicate loop\n");
220 /* The loop should not be too large, to limit code growth. */
221 if (num_loop_insns (loop
) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS
))
224 fprintf (rtl_dump_file
, ";; Not unswitching, loop too big\n");
228 /* Do not unswitch in cold areas. */
229 if (!maybe_hot_bb_p (loop
->header
))
232 fprintf (rtl_dump_file
, ";; Not unswitching, not hot area\n");
236 /* Nor if the loop usually does not roll. */
237 if (expected_loop_iterations (loop
) < 1)
240 fprintf (rtl_dump_file
, ";; Not unswitching, loop iterations < 1\n");
248 /* Find a bb to unswitch on. */
249 bbs
= get_loop_body (loop
);
250 for (i
= 0; i
< loop
->num_nodes
; i
++)
251 if (may_unswitch_on_p (loops
, bbs
[i
], loop
, bbs
))
254 if (i
== loop
->num_nodes
)
260 if (!(cond
= get_condition (bbs
[i
]->end
, &split_before
)))
262 rcond
= reversed_condition (cond
);
264 /* Check whether the result can be predicted. */
267 for (acond
= cond_checked
; acond
; acond
= XEXP (acond
, 1))
269 if (rtx_equal_p (cond
, XEXP (acond
, 0)))
274 if (rtx_equal_p (rcond
, XEXP (acond
, 0)))
283 /* Remove false path. */
284 for (e
= bbs
[i
]->succ
; !(e
->flags
& EDGE_FALLTHRU
); e
= e
->succ_next
);
285 remove_path (loops
, e
);
289 else if (always_false
)
291 /* Remove true path. */
292 for (e
= bbs
[i
]->succ
; e
->flags
& EDGE_FALLTHRU
; e
= e
->succ_next
);
293 remove_path (loops
, e
);
299 /* We found the condition we can unswitch on. */
300 conds
= alloc_EXPR_LIST (0, cond
, cond_checked
);
302 rconds
= alloc_EXPR_LIST (0, rcond
, cond_checked
);
304 rconds
= cond_checked
;
306 /* Separate condition in a single basic block. */
307 bb
= split_loop_bb (loops
, bbs
[i
], PREV_INSN (split_before
))->dest
;
309 true_first
= !(bb
->succ
->flags
& EDGE_FALLTHRU
);
311 fprintf (rtl_dump_file
, ";; Unswitching loop\n");
313 /* Unswitch the loop on this condition. */
314 nloop
= unswitch_loop (loops
, loop
, bb
);
318 /* Invoke itself on modified loops. */
319 unswitch_single_loop (loops
, nloop
, true_first
? conds
: rconds
, num
+ 1);
320 unswitch_single_loop (loops
, loop
, true_first
? rconds
: conds
, num
+ 1);
322 free_EXPR_LIST_node (conds
);
324 free_EXPR_LIST_node (rconds
);
327 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
328 unswitching of innermost loops. UNSWITCH_ON must be executed in every
329 iteration, i.e. it must dominate LOOP latch, and should only contain code
330 for the condition we unswitch on. Returns NULL if impossible, new
333 unswitch_loop (loops
, loop
, unswitch_on
)
336 basic_block unswitch_on
;
338 edge entry
, latch_edge
;
339 basic_block switch_bb
, unswitch_on_alt
, src
;
344 /* Some sanity checking. */
345 if (!flow_bb_inside_loop_p (loop
, unswitch_on
))
347 if (!unswitch_on
->succ
|| !unswitch_on
->succ
->succ_next
||
348 unswitch_on
->succ
->succ_next
->succ_next
)
350 if (!just_once_each_iteration_p (loops
, loop
, unswitch_on
))
354 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->dest
))
356 if (!flow_bb_inside_loop_p (loop
, unswitch_on
->succ
->succ_next
->dest
))
359 /* Will we be able to perform redirection? */
360 if (!any_condjump_p (unswitch_on
->end
))
362 if (!cfg_layout_can_duplicate_bb_p (unswitch_on
))
365 entry
= loop_preheader_edge (loop
);
369 irred_flag
= entry
->flags
& EDGE_IRREDUCIBLE_LOOP
;
370 entry
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
371 zero_bitmap
= sbitmap_alloc (2);
372 sbitmap_zero (zero_bitmap
);
373 if (!duplicate_loop_to_header_edge (loop
, entry
, loops
, 1,
374 zero_bitmap
, NULL
, NULL
, NULL
, 0))
377 entry
->flags
|= irred_flag
;
379 /* Record the block with condition we unswitch on. */
380 unswitch_on_alt
= unswitch_on
->rbi
->copy
;
382 /* Make a copy of the block containing the condition; we will use
383 it as switch to decide which loop we want to use. */
384 switch_bb
= cfg_layout_duplicate_bb (unswitch_on
, NULL
);
387 switch_bb
->flags
|= BB_IRREDUCIBLE_LOOP
;
388 switch_bb
->succ
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
389 switch_bb
->succ
->succ_next
->flags
|= EDGE_IRREDUCIBLE_LOOP
;
393 switch_bb
->flags
&= ~BB_IRREDUCIBLE_LOOP
;
394 switch_bb
->succ
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
395 switch_bb
->succ
->succ_next
->flags
&= ~EDGE_IRREDUCIBLE_LOOP
;
397 add_to_dominance_info (loops
->cfg
.dom
, switch_bb
);
398 unswitch_on
->rbi
->copy
= unswitch_on_alt
;
400 /* Loopify from the copy of LOOP body, constructing the new loop. */
401 for (latch_edge
= loop
->latch
->rbi
->copy
->succ
;
402 latch_edge
->dest
!= loop
->header
;
403 latch_edge
= latch_edge
->succ_next
);
404 nloop
= loopify (loops
, latch_edge
,
405 loop
->header
->rbi
->copy
->pred
, switch_bb
);
407 /* Remove branches that are now unreachable in new loops. We rely on the
408 fact that cfg_layout_duplicate_bb reverses list of edges. */
409 remove_path (loops
, unswitch_on
->succ
);
410 remove_path (loops
, unswitch_on_alt
->succ
);
412 /* One of created loops do not have to be subloop of the outer loop now,
413 so fix its placement in loop datastructure. */
414 fix_loop_placement (loop
);
415 fix_loop_placement (nloop
);