1 /* Loop unswitching for GNU compiler.
2 Copyright (C) 2002, 2003, 2004, 2005 Free Software Foundation, Inc.
3
4 This file is part of GCC.
5
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
9 version.
10
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.
15
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
19 02110-1301, USA. */
20
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "tm.h"
25 #include "rtl.h"
26 #include "hard-reg-set.h"
27 #include "obstack.h"
28 #include "basic-block.h"
29 #include "cfgloop.h"
30 #include "cfglayout.h"
31 #include "params.h"
32 #include "output.h"
33 #include "expr.h"
34
35 /* This pass moves constant conditions out of loops, duplicating the loop
36 in progress, i.e. this code:
37
38 while (loop_cond)
39 {
40 A;
41 if (cond)
42 branch1;
43 else
44 branch2;
45 B;
46 if (cond)
47 branch3;
48 C;
49 }
50 where nothing inside the loop alters cond is transformed
51 into
52
53 if (cond)
54 {
55 while (loop_cond)
56 {
57 A;
58 branch1;
59 B;
60 branch3;
61 C;
62 }
63 }
64 else
65 {
66 while (loop_cond)
67 {
68 A;
69 branch2;
70 B;
71 C;
72 }
73 }
74
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. */
81
82 static struct loop *unswitch_loop (struct loops *, struct loop *,
83 basic_block, rtx, rtx);
84 static void unswitch_single_loop (struct loops *, struct loop *, rtx, int);
85 static rtx may_unswitch_on (basic_block, struct loop *, rtx *);
86
87 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
88 true, with probability PROB. If CINSN is not NULL, it is the insn to copy
89 in order to create a jump. */
90
91 rtx
compare_and_jump_seq(rtx op0,rtx op1,enum rtx_code comp,rtx label,int prob,rtx cinsn)92 compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp, rtx label, int prob,
93 rtx cinsn)
94 {
95 rtx seq, jump, cond;
96 enum machine_mode mode;
97
98 mode = GET_MODE (op0);
99 if (mode == VOIDmode)
100 mode = GET_MODE (op1);
101
102 start_sequence ();
103 if (GET_MODE_CLASS (mode) == MODE_CC)
104 {
105 /* A hack -- there seems to be no easy generic way how to make a
106 conditional jump from a ccmode comparison. */
107 gcc_assert (cinsn);
108 cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
109 gcc_assert (GET_CODE (cond) == comp);
110 gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
111 gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
112 emit_jump_insn (copy_insn (PATTERN (cinsn)));
113 jump = get_last_insn ();
114 JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
115 LABEL_NUSES (JUMP_LABEL (jump))++;
116 redirect_jump (jump, label, 0);
117 }
118 else
119 {
120 gcc_assert (!cinsn);
121
122 op0 = force_operand (op0, NULL_RTX);
123 op1 = force_operand (op1, NULL_RTX);
124 do_compare_rtx_and_jump (op0, op1, comp, 0,
125 mode, NULL_RTX, NULL_RTX, label);
126 jump = get_last_insn ();
127 JUMP_LABEL (jump) = label;
128 LABEL_NUSES (label)++;
129 }
130 REG_NOTES (jump) = gen_rtx_EXPR_LIST (REG_BR_PROB, GEN_INT (prob),
131 REG_NOTES (jump));
132 seq = get_insns ();
133 end_sequence ();
134
135 return seq;
136 }
137
138 /* Main entry point. Perform loop unswitching on all suitable LOOPS. */
139 void
unswitch_loops(struct loops * loops)140 unswitch_loops (struct loops *loops)
141 {
142 int i, num;
143 struct loop *loop;
144
145 /* Go through inner loops (only original ones). */
146 num = loops->num;
147
148 for (i = 1; i < num; i++)
149 {
150 /* Removed loop? */
151 loop = loops->parray[i];
152 if (!loop)
153 continue;
154
155 if (loop->inner)
156 continue;
157
158 unswitch_single_loop (loops, loop, NULL_RTX, 0);
159 #ifdef ENABLE_CHECKING
160 verify_dominators (CDI_DOMINATORS);
161 verify_loop_structure (loops);
162 #endif
163 }
164
165 iv_analysis_done ();
166 }
167
168 /* Checks whether we can unswitch LOOP on condition at end of BB -- one of its
169 basic blocks (for what it means see comments below). In case condition
170 compares loop invariant cc mode register, return the jump in CINSN. */
171
172 static rtx
may_unswitch_on(basic_block bb,struct loop * loop,rtx * cinsn)173 may_unswitch_on (basic_block bb, struct loop *loop, rtx *cinsn)
174 {
175 rtx test, at, op[2], stest;
176 struct rtx_iv iv;
177 unsigned i;
178 enum machine_mode mode;
179
180 /* BB must end in a simple conditional jump. */
181 if (EDGE_COUNT (bb->succs) != 2)
182 return NULL_RTX;
183 if (!any_condjump_p (BB_END (bb)))
184 return NULL_RTX;
185
186 /* With branches inside loop. */
187 if (!flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 0)->dest)
188 || !flow_bb_inside_loop_p (loop, EDGE_SUCC (bb, 1)->dest))
189 return NULL_RTX;
190
191 /* It must be executed just once each iteration (because otherwise we
192 are unable to update dominator/irreducible loop information correctly). */
193 if (!just_once_each_iteration_p (loop, bb))
194 return NULL_RTX;
195
196 /* Condition must be invariant. */
197 test = get_condition (BB_END (bb), &at, true, false);
198 if (!test)
199 return NULL_RTX;
200
201 for (i = 0; i < 2; i++)
202 {
203 op[i] = XEXP (test, i);
204
205 if (CONSTANT_P (op[i]))
206 continue;
207
208 if (!iv_analyze (at, op[i], &iv))
209 return NULL_RTX;
210 if (iv.step != const0_rtx
211 || iv.first_special)
212 return NULL_RTX;
213
214 op[i] = get_iv_value (&iv, const0_rtx);
215 }
216
217 mode = GET_MODE (op[0]);
218 if (mode == VOIDmode)
219 mode = GET_MODE (op[1]);
220 if (GET_MODE_CLASS (mode) == MODE_CC)
221 {
222 if (at != BB_END (bb))
223 return NULL_RTX;
224
225 if (!rtx_equal_p (op[0], XEXP (test, 0))
226 || !rtx_equal_p (op[1], XEXP (test, 1)))
227 return NULL_RTX;
228
229 *cinsn = BB_END (bb);
230 return test;
231 }
232
233 stest = simplify_gen_relational (GET_CODE (test), SImode,
234 mode, op[0], op[1]);
235 if (stest == const0_rtx
236 || stest == const_true_rtx)
237 return stest;
238
239 return canon_condition (gen_rtx_fmt_ee (GET_CODE (test), SImode,
240 op[0], op[1]));
241 }
242
243 /* Reverses CONDition; returns NULL if we cannot. */
244 rtx
reversed_condition(rtx cond)245 reversed_condition (rtx cond)
246 {
247 enum rtx_code reversed;
248 reversed = reversed_comparison_code (cond, NULL);
249 if (reversed == UNKNOWN)
250 return NULL_RTX;
251 else
252 return gen_rtx_fmt_ee (reversed,
253 GET_MODE (cond), XEXP (cond, 0),
254 XEXP (cond, 1));
255 }
256
257 /* Unswitch single LOOP. COND_CHECKED holds list of conditions we already
258 unswitched on and are therefore known to be true in this LOOP. NUM is
259 number of unswitchings done; do not allow it to grow too much, it is too
260 easy to create example on that the code would grow exponentially. */
261 static void
unswitch_single_loop(struct loops * loops,struct loop * loop,rtx cond_checked,int num)262 unswitch_single_loop (struct loops *loops, struct loop *loop,
263 rtx cond_checked, int num)
264 {
265 basic_block *bbs;
266 struct loop *nloop;
267 unsigned i;
268 rtx cond, rcond = NULL_RTX, conds, rconds, acond, cinsn;
269 int repeat;
270 edge e;
271
272 /* Do not unswitch too much. */
273 if (num > PARAM_VALUE (PARAM_MAX_UNSWITCH_LEVEL))
274 {
275 if (dump_file)
276 fprintf (dump_file, ";; Not unswitching anymore, hit max level\n");
277 return;
278 }
279
280 /* Only unswitch innermost loops. */
281 if (loop->inner)
282 {
283 if (dump_file)
284 fprintf (dump_file, ";; Not unswitching, not innermost loop\n");
285 return;
286 }
287
288 /* We must be able to duplicate loop body. */
289 if (!can_duplicate_loop_p (loop))
290 {
291 if (dump_file)
292 fprintf (dump_file, ";; Not unswitching, can't duplicate loop\n");
293 return;
294 }
295
296 /* The loop should not be too large, to limit code growth. */
297 if (num_loop_insns (loop) > PARAM_VALUE (PARAM_MAX_UNSWITCH_INSNS))
298 {
299 if (dump_file)
300 fprintf (dump_file, ";; Not unswitching, loop too big\n");
301 return;
302 }
303
304 /* Do not unswitch in cold areas. */
305 if (!maybe_hot_bb_p (loop->header))
306 {
307 if (dump_file)
308 fprintf (dump_file, ";; Not unswitching, not hot area\n");
309 return;
310 }
311
312 /* Nor if the loop usually does not roll. */
313 if (expected_loop_iterations (loop) < 1)
314 {
315 if (dump_file)
316 fprintf (dump_file, ";; Not unswitching, loop iterations < 1\n");
317 return;
318 }
319
320 do
321 {
322 repeat = 0;
323 cinsn = NULL_RTX;
324
325 /* Find a bb to unswitch on. */
326 bbs = get_loop_body (loop);
327 iv_analysis_loop_init (loop);
328 for (i = 0; i < loop->num_nodes; i++)
329 if ((cond = may_unswitch_on (bbs[i], loop, &cinsn)))
330 break;
331
332 if (i == loop->num_nodes)
333 {
334 free (bbs);
335 return;
336 }
337
338 if (cond != const0_rtx
339 && cond != const_true_rtx)
340 {
341 rcond = reversed_condition (cond);
342 if (rcond)
343 rcond = canon_condition (rcond);
344
345 /* Check whether the result can be predicted. */
346 for (acond = cond_checked; acond; acond = XEXP (acond, 1))
347 simplify_using_condition (XEXP (acond, 0), &cond, NULL);
348 }
349
350 if (cond == const_true_rtx)
351 {
352 /* Remove false path. */
353 e = FALLTHRU_EDGE (bbs[i]);
354 remove_path (loops, e);
355 free (bbs);
356 repeat = 1;
357 }
358 else if (cond == const0_rtx)
359 {
360 /* Remove true path. */
361 e = BRANCH_EDGE (bbs[i]);
362 remove_path (loops, e);
363 free (bbs);
364 repeat = 1;
365 }
366 } while (repeat);
367
368 /* We found the condition we can unswitch on. */
369 conds = alloc_EXPR_LIST (0, cond, cond_checked);
370 if (rcond)
371 rconds = alloc_EXPR_LIST (0, rcond, cond_checked);
372 else
373 rconds = cond_checked;
374
375 if (dump_file)
376 fprintf (dump_file, ";; Unswitching loop\n");
377
378 /* Unswitch the loop on this condition. */
379 nloop = unswitch_loop (loops, loop, bbs[i], cond, cinsn);
380 gcc_assert (nloop);
381
382 /* Invoke itself on modified loops. */
383 unswitch_single_loop (loops, nloop, rconds, num + 1);
384 unswitch_single_loop (loops, loop, conds, num + 1);
385
386 free_EXPR_LIST_node (conds);
387 if (rcond)
388 free_EXPR_LIST_node (rconds);
389
390 free (bbs);
391 }
392
393 /* Unswitch a LOOP w.r. to given basic block UNSWITCH_ON. We only support
394 unswitching of innermost loops. UNSWITCH_ON must be executed in every
395 iteration, i.e. it must dominate LOOP latch. COND is the condition
396 determining which loop is entered. Returns NULL if impossible, new loop
397 otherwise. The new loop is entered if COND is true. If CINSN is not
398 NULL, it is the insn in that COND is compared. */
399
400 static struct loop *
unswitch_loop(struct loops * loops,struct loop * loop,basic_block unswitch_on,rtx cond,rtx cinsn)401 unswitch_loop (struct loops *loops, struct loop *loop, basic_block unswitch_on,
402 rtx cond, rtx cinsn)
403 {
404 edge entry, latch_edge, true_edge, false_edge, e;
405 basic_block switch_bb, unswitch_on_alt;
406 struct loop *nloop;
407 sbitmap zero_bitmap;
408 int irred_flag, prob;
409 rtx seq;
410
411 /* Some sanity checking. */
412 gcc_assert (flow_bb_inside_loop_p (loop, unswitch_on));
413 gcc_assert (EDGE_COUNT (unswitch_on->succs) == 2);
414 gcc_assert (just_once_each_iteration_p (loop, unswitch_on));
415 gcc_assert (!loop->inner);
416 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 0)->dest));
417 gcc_assert (flow_bb_inside_loop_p (loop, EDGE_SUCC (unswitch_on, 1)->dest));
418
419 entry = loop_preheader_edge (loop);
420
421 /* Make a copy. */
422 irred_flag = entry->flags & EDGE_IRREDUCIBLE_LOOP;
423 entry->flags &= ~EDGE_IRREDUCIBLE_LOOP;
424 zero_bitmap = sbitmap_alloc (2);
425 sbitmap_zero (zero_bitmap);
426 if (!duplicate_loop_to_header_edge (loop, entry, loops, 1,
427 zero_bitmap, NULL, NULL, NULL, 0))
428 {
429 sbitmap_free (zero_bitmap);
430 return NULL;
431 }
432 sbitmap_free (zero_bitmap);
433 entry->flags |= irred_flag;
434
435 /* Record the block with condition we unswitch on. */
436 unswitch_on_alt = get_bb_copy (unswitch_on);
437 true_edge = BRANCH_EDGE (unswitch_on_alt);
438 false_edge = FALLTHRU_EDGE (unswitch_on);
439 latch_edge = single_succ_edge (get_bb_copy (loop->latch));
440
441 /* Create a block with the condition. */
442 prob = true_edge->probability;
443 switch_bb = create_empty_bb (EXIT_BLOCK_PTR->prev_bb);
444 seq = compare_and_jump_seq (XEXP (cond, 0), XEXP (cond, 1), GET_CODE (cond),
445 block_label (true_edge->dest),
446 prob, cinsn);
447 emit_insn_after (seq, BB_END (switch_bb));
448 e = make_edge (switch_bb, true_edge->dest, 0);
449 e->probability = prob;
450 e->count = latch_edge->count * prob / REG_BR_PROB_BASE;
451 e = make_edge (switch_bb, FALLTHRU_EDGE (unswitch_on)->dest, EDGE_FALLTHRU);
452 e->probability = false_edge->probability;
453 e->count = latch_edge->count * (false_edge->probability) / REG_BR_PROB_BASE;
454
455 if (irred_flag)
456 {
457 switch_bb->flags |= BB_IRREDUCIBLE_LOOP;
458 EDGE_SUCC (switch_bb, 0)->flags |= EDGE_IRREDUCIBLE_LOOP;
459 EDGE_SUCC (switch_bb, 1)->flags |= EDGE_IRREDUCIBLE_LOOP;
460 }
461 else
462 {
463 switch_bb->flags &= ~BB_IRREDUCIBLE_LOOP;
464 EDGE_SUCC (switch_bb, 0)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
465 EDGE_SUCC (switch_bb, 1)->flags &= ~EDGE_IRREDUCIBLE_LOOP;
466 }
467
468 /* Loopify from the copy of LOOP body, constructing the new loop. */
469 nloop = loopify (loops, latch_edge,
470 single_pred_edge (get_bb_copy (loop->header)), switch_bb,
471 BRANCH_EDGE (switch_bb), FALLTHRU_EDGE (switch_bb), true);
472
473 /* Remove branches that are now unreachable in new loops. */
474 remove_path (loops, true_edge);
475 remove_path (loops, false_edge);
476
477 /* One of created loops do not have to be subloop of the outer loop now,
478 so fix its placement in loop data structure. */
479 fix_loop_placement (loop);
480 fix_loop_placement (nloop);
481
482 /* Preserve the simple loop preheaders. */
483 loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
484 loop_split_edge_with (loop_preheader_edge (nloop), NULL_RTX);
485
486 return nloop;
487 }
488