1 /* Perform doloop optimizations
2 Copyright (C) 2004, 2005, 2006, 2007, 2008 Free Software Foundation,
4 Based on code by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
6 This file is part of GCC.
8 GCC is free software; you can redistribute it and/or modify it under
9 the terms of the GNU General Public License as published by the Free
10 Software Foundation; either version 3, or (at your option) any later
13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
15 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
18 You should have received a copy of the GNU General Public License
19 along with GCC; see the file COPYING3. If not see
20 <http://www.gnu.org/licenses/>. */
24 #include "coretypes.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
38 /* This module is used to modify loops with a determinable number of
39 iterations to use special low-overhead looping instructions.
41 It first validates whether the loop is well behaved and has a
42 determinable number of iterations (either at compile or run-time).
43 It then modifies the loop to use a low-overhead looping pattern as
46 1. A pseudo register is allocated as the loop iteration counter.
48 2. The number of loop iterations is calculated and is stored
51 3. At the end of the loop, the jump insn is replaced by the
52 doloop_end pattern. The compare must remain because it might be
53 used elsewhere. If the loop-variable or condition register are
54 used elsewhere, they will be eliminated by flow.
56 4. An optional doloop_begin pattern is inserted at the top of the
59 TODO The optimization should only performed when either the biv used for exit
60 condition is unused at all except for the exit test, or if we do not have to
61 change its value, since otherwise we have to add a new induction variable,
62 which usually will not pay up (unless the cost of the doloop pattern is
63 somehow extremely lower than the cost of compare & jump, or unless the bct
64 register cannot be used for anything else but doloop -- ??? detect these
67 #ifdef HAVE_doloop_end
69 /* Return the loop termination condition for PATTERN or zero
70 if it is not a decrement and branch jump insn. */
73 doloop_condition_get (rtx doloop_pat
)
82 /* The canonical doloop pattern we expect has one of the following
85 1) (parallel [(set (pc) (if_then_else (condition)
88 (set (reg) (plus (reg) (const_int -1)))
89 (additional clobbers and uses)])
91 The branch must be the first entry of the parallel (also required
92 by jump.c), and the second entry of the parallel must be a set of
93 the loop counter register. Some targets (IA-64) wrap the set of
94 the loop counter in an if_then_else too.
96 2) (set (reg) (plus (reg) (const_int -1))
97 (set (pc) (if_then_else (reg != 0)
101 pattern
= PATTERN (doloop_pat
);
103 if (GET_CODE (pattern
) != PARALLEL
)
107 /* We expect the decrement to immediately precede the branch. */
109 if ((PREV_INSN (doloop_pat
) == NULL_RTX
)
110 || !INSN_P (PREV_INSN (doloop_pat
)))
114 inc
= PATTERN (PREV_INSN (doloop_pat
));
115 /* We expect the condition to be of the form (reg != 0) */
116 cond
= XEXP (SET_SRC (cmp
), 0);
117 if (GET_CODE (cond
) != NE
|| XEXP (cond
, 1) != const0_rtx
)
123 cmp
= XVECEXP (pattern
, 0, 0);
124 inc
= XVECEXP (pattern
, 0, 1);
127 /* Check for (set (reg) (something)). */
128 if (GET_CODE (inc
) != SET
)
130 reg
= SET_DEST (inc
);
134 /* Check if something = (plus (reg) (const_int -1)).
135 On IA-64, this decrement is wrapped in an if_then_else. */
136 inc_src
= SET_SRC (inc
);
137 if (GET_CODE (inc_src
) == IF_THEN_ELSE
)
138 inc_src
= XEXP (inc_src
, 1);
139 if (GET_CODE (inc_src
) != PLUS
140 || XEXP (inc_src
, 0) != reg
141 || XEXP (inc_src
, 1) != constm1_rtx
)
144 /* Check for (set (pc) (if_then_else (condition)
147 if (GET_CODE (cmp
) != SET
148 || SET_DEST (cmp
) != pc_rtx
149 || GET_CODE (SET_SRC (cmp
)) != IF_THEN_ELSE
150 || GET_CODE (XEXP (SET_SRC (cmp
), 1)) != LABEL_REF
151 || XEXP (SET_SRC (cmp
), 2) != pc_rtx
)
154 /* Extract loop termination condition. */
155 condition
= XEXP (SET_SRC (cmp
), 0);
157 /* We expect a GE or NE comparison with 0 or 1. */
158 if ((GET_CODE (condition
) != GE
159 && GET_CODE (condition
) != NE
)
160 || (XEXP (condition
, 1) != const0_rtx
161 && XEXP (condition
, 1) != const1_rtx
))
164 if ((XEXP (condition
, 0) == reg
)
165 || (GET_CODE (XEXP (condition
, 0)) == PLUS
166 && XEXP (XEXP (condition
, 0), 0) == reg
))
168 if (GET_CODE (pattern
) != PARALLEL
)
169 /* The second form we expect:
171 (set (reg) (plus (reg) (const_int -1))
172 (set (pc) (if_then_else (reg != 0)
176 is equivalent to the following:
178 (parallel [(set (pc) (if_then_else (reg != 1)
181 (set (reg) (plus (reg) (const_int -1)))
182 (additional clobbers and uses)])
184 So we return that form instead.
186 condition
= gen_rtx_fmt_ee (NE
, VOIDmode
, inc_src
, const1_rtx
);
191 /* ??? If a machine uses a funny comparison, we could return a
192 canonicalized form here. */
197 /* Return nonzero if the loop specified by LOOP is suitable for
198 the use of special low-overhead looping instructions. DESC
199 describes the number of iterations of the loop. */
202 doloop_valid_p (struct loop
*loop
, struct niter_desc
*desc
)
204 basic_block
*body
= get_loop_body (loop
), bb
;
209 /* Check for loops that may not terminate under special conditions. */
214 /* There are some cases that would require a special attention.
215 For example if the comparison is LEU and the comparison value
216 is UINT_MAX then the loop will not terminate. Similarly, if the
217 comparison code is GEU and the comparison value is 0, the
218 loop will not terminate.
220 If the absolute increment is not 1, the loop can be infinite
221 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
223 ??? We could compute these conditions at run-time and have a
224 additional jump around the loop to ensure an infinite loop.
225 However, it is very unlikely that this is the intended
226 behavior of the loop and checking for these rare boundary
227 conditions would pessimize all other code.
229 If the loop is executed only a few times an extra check to
230 restart the loop could use up most of the benefits of using a
231 count register loop. Note however, that normally, this
232 restart branch would never execute, so it could be predicted
233 well by the CPU. We should generate the pessimistic code by
234 default, and have an option, e.g. -funsafe-loops that would
235 enable count-register loops in this case. */
237 fprintf (dump_file
, "Doloop: Possible infinite iteration case.\n");
242 for (i
= 0; i
< loop
->num_nodes
; i
++)
246 for (insn
= BB_HEAD (bb
);
247 insn
!= NEXT_INSN (BB_END (bb
));
248 insn
= NEXT_INSN (insn
))
250 /* Different targets have different necessities for low-overhead
251 looping. Call the back end for each instruction within the loop
252 to let it decide whether the insn prohibits a low-overhead loop.
253 It will then return the cause for it to emit to the dump file. */
254 const char * invalid
= targetm
.invalid_within_doloop (insn
);
258 fprintf (dump_file
, "Doloop: %s\n", invalid
);
272 /* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru
273 edge. If the condition is always false, do not do anything. If it is always
274 true, redirect E to DEST and return false. In all other cases, true is
278 add_test (rtx cond
, edge
*e
, basic_block dest
)
280 rtx seq
, jump
, label
;
281 enum machine_mode mode
;
282 rtx op0
= XEXP (cond
, 0), op1
= XEXP (cond
, 1);
283 enum rtx_code code
= GET_CODE (cond
);
286 mode
= GET_MODE (XEXP (cond
, 0));
287 if (mode
== VOIDmode
)
288 mode
= GET_MODE (XEXP (cond
, 1));
291 op0
= force_operand (op0
, NULL_RTX
);
292 op1
= force_operand (op1
, NULL_RTX
);
293 label
= block_label (dest
);
294 do_compare_rtx_and_jump (op0
, op1
, code
, 0, mode
, NULL_RTX
, NULL_RTX
, label
);
296 jump
= get_last_insn ();
297 if (!jump
|| !JUMP_P (jump
))
299 /* The condition is always false and the jump was optimized out. */
307 /* There always is at least the jump insn in the sequence. */
308 gcc_assert (seq
!= NULL_RTX
);
310 bb
= split_edge_and_insert (*e
, seq
);
311 *e
= single_succ_edge (bb
);
313 if (any_uncondjump_p (jump
))
315 /* The condition is always true. */
317 redirect_edge_and_branch_force (*e
, dest
);
321 JUMP_LABEL (jump
) = label
;
323 /* The jump is supposed to handle an unlikely special case. */
325 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
326 const0_rtx
, REG_NOTES (jump
));
327 LABEL_NUSES (label
)++;
329 make_edge (bb
, dest
, (*e
)->flags
& ~EDGE_FALLTHRU
);
333 /* Modify the loop to use the low-overhead looping insn where LOOP
334 describes the loop, DESC describes the number of iterations of the
335 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
336 end of the loop. CONDITION is the condition separated from the
337 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
340 doloop_modify (struct loop
*loop
, struct niter_desc
*desc
,
341 rtx doloop_seq
, rtx condition
, rtx count
)
344 rtx tmp
, noloop
= NULL_RTX
;
349 bool increment_count
;
350 basic_block loop_end
= desc
->out_edge
->src
;
351 enum machine_mode mode
;
354 jump_insn
= BB_END (loop_end
);
358 fprintf (dump_file
, "Doloop: Inserting doloop pattern (");
359 if (desc
->const_iter
)
360 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
362 fputs ("runtime", dump_file
);
363 fputs (" iterations).\n", dump_file
);
366 /* Get the probability of the original branch. If it exists we would
367 need to update REG_BR_PROB of the new jump_insn. */
368 true_prob_val
= find_reg_note (jump_insn
, REG_BR_PROB
, NULL_RTX
);
370 /* Discard original jump to continue loop. The original compare
371 result may still be live, so it cannot be discarded explicitly. */
372 delete_insn (jump_insn
);
374 counter_reg
= XEXP (condition
, 0);
375 if (GET_CODE (counter_reg
) == PLUS
)
376 counter_reg
= XEXP (counter_reg
, 0);
377 mode
= GET_MODE (counter_reg
);
379 increment_count
= false;
380 switch (GET_CODE (condition
))
383 /* Currently only NE tests against zero and one are supported. */
384 noloop
= XEXP (condition
, 1);
385 if (noloop
!= const0_rtx
)
387 gcc_assert (noloop
== const1_rtx
);
388 increment_count
= true;
393 /* Currently only GE tests against zero are supported. */
394 gcc_assert (XEXP (condition
, 1) == const0_rtx
);
396 noloop
= constm1_rtx
;
398 /* The iteration count does not need incrementing for a GE test. */
399 increment_count
= false;
401 /* Determine if the iteration counter will be non-negative.
402 Note that the maximum value loaded is iterations_max - 1. */
404 <= ((unsigned HOST_WIDEST_INT
) 1
405 << (GET_MODE_BITSIZE (mode
) - 1)))
409 /* Abort if an invalid doloop pattern has been generated. */
415 count
= simplify_gen_binary (PLUS
, mode
, count
, const1_rtx
);
417 /* Insert initialization of the count register into the loop header. */
419 tmp
= force_operand (count
, counter_reg
);
420 convert_move (counter_reg
, tmp
, 1);
421 sequence
= get_insns ();
423 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
425 if (desc
->noloop_assumptions
)
427 rtx ass
= copy_rtx (desc
->noloop_assumptions
);
428 basic_block preheader
= loop_preheader_edge (loop
)->src
;
430 = split_edge (loop_preheader_edge (loop
));
431 basic_block new_preheader
432 = split_edge (loop_preheader_edge (loop
));
435 /* Expand the condition testing the assumptions and if it does not pass,
436 reset the count register to 0. */
437 redirect_edge_and_branch_force (single_succ_edge (preheader
), new_preheader
);
438 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
, preheader
);
441 set_zero
->frequency
= 0;
443 te
= single_succ_edge (preheader
);
444 for (; ass
; ass
= XEXP (ass
, 1))
445 if (!add_test (XEXP (ass
, 0), &te
, set_zero
))
450 /* We reached a condition that is always true. This is very hard to
451 reproduce (such a loop does not roll, and thus it would most
452 likely get optimized out by some of the preceding optimizations).
453 In fact, I do not have any testcase for it. However, it would
454 also be very hard to show that it is impossible, so we must
456 set_zero
->count
= preheader
->count
;
457 set_zero
->frequency
= preheader
->frequency
;
460 if (EDGE_COUNT (set_zero
->preds
) == 0)
462 /* All the conditions were simplified to false, remove the
463 unreachable set_zero block. */
464 delete_basic_block (set_zero
);
468 /* Reset the counter to zero in the set_zero block. */
470 convert_move (counter_reg
, noloop
, 0);
471 sequence
= get_insns ();
473 emit_insn_after (sequence
, BB_END (set_zero
));
475 set_immediate_dominator (CDI_DOMINATORS
, set_zero
,
476 recompute_dominator (CDI_DOMINATORS
,
480 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
,
481 recompute_dominator (CDI_DOMINATORS
,
485 /* Some targets (eg, C4x) need to initialize special looping
487 #ifdef HAVE_doloop_begin
490 unsigned level
= get_loop_level (loop
) + 1;
491 init
= gen_doloop_begin (counter_reg
,
492 desc
->const_iter
? desc
->niter_expr
: const0_rtx
,
493 GEN_INT (desc
->niter_max
),
499 sequence
= get_insns ();
501 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
506 /* Insert the new low-overhead looping insn. */
507 emit_jump_insn_after (doloop_seq
, BB_END (loop_end
));
508 jump_insn
= BB_END (loop_end
);
509 jump_label
= block_label (desc
->in_edge
->dest
);
510 JUMP_LABEL (jump_insn
) = jump_label
;
511 LABEL_NUSES (jump_label
)++;
513 /* Ensure the right fallthru edge is marked, for case we have reversed
515 desc
->in_edge
->flags
&= ~EDGE_FALLTHRU
;
516 desc
->out_edge
->flags
|= EDGE_FALLTHRU
;
518 /* Add a REG_NONNEG note if the actual or estimated maximum number
519 of iterations is non-negative. */
522 REG_NOTES (jump_insn
)
523 = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
, REG_NOTES (jump_insn
));
525 /* Update the REG_BR_PROB note. */
528 /* Seems safer to use the branch probability. */
529 REG_NOTES (jump_insn
) =
530 gen_rtx_EXPR_LIST (REG_BR_PROB
,
531 GEN_INT (desc
->in_edge
->probability
),
532 REG_NOTES (jump_insn
));
536 /* Process loop described by LOOP validating that the loop is suitable for
537 conversion to use a low overhead looping instruction, replacing the jump
538 insn where suitable. Returns true if the loop was successfully
542 doloop_optimize (struct loop
*loop
)
544 enum machine_mode mode
;
545 rtx doloop_seq
, doloop_pat
, doloop_reg
;
546 rtx iterations
, count
;
550 unsigned level
, est_niter
;
552 struct niter_desc
*desc
;
553 unsigned word_mode_size
;
554 unsigned HOST_WIDE_INT word_mode_max
;
557 fprintf (dump_file
, "Doloop: Processing loop %d.\n", loop
->num
);
559 iv_analysis_loop_init (loop
);
561 /* Find the simple exit of a LOOP. */
562 desc
= get_simple_loop_desc (loop
);
564 /* Check that loop is a candidate for a low-overhead looping insn. */
565 if (!doloop_valid_p (loop
, desc
))
569 "Doloop: The loop is not suitable.\n");
575 if (desc
->const_iter
)
576 est_niter
= desc
->niter
;
577 /* If the estimate on number of iterations is reliable (comes from profile
578 feedback), use it. Do not use it normally, since the expected number
579 of iterations of an unrolled loop is 2. */
580 if (loop
->header
->count
)
581 est_niter
= expected_loop_iterations (loop
);
587 "Doloop: Too few iterations (%u) to be profitable.\n",
593 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST
));
594 if (rtx_cost (desc
->niter_expr
, SET
) > max_cost
)
598 "Doloop: number of iterations too costly to compute.\n");
602 count
= copy_rtx (desc
->niter_expr
);
603 iterations
= desc
->const_iter
? desc
->niter_expr
: const0_rtx
;
604 iterations_max
= GEN_INT (desc
->niter_max
);
605 level
= get_loop_level (loop
) + 1;
607 /* Generate looping insn. If the pattern FAILs then give up trying
608 to modify the loop since there is some aspect the back-end does
610 start_label
= block_label (desc
->in_edge
->dest
);
611 doloop_reg
= gen_reg_rtx (mode
);
612 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
613 GEN_INT (level
), start_label
);
615 word_mode_size
= GET_MODE_BITSIZE (word_mode
);
617 = ((unsigned HOST_WIDE_INT
) 1 << (word_mode_size
- 1) << 1) - 1;
620 /* Before trying mode different from the one in that # of iterations is
621 computed, we must be sure that the number of iterations fits into
623 && (word_mode_size
>= GET_MODE_BITSIZE (mode
)
624 || desc
->niter_max
<= word_mode_max
))
626 if (word_mode_size
> GET_MODE_BITSIZE (mode
))
628 count
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
630 iterations
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
632 iterations_max
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
633 iterations_max
, mode
);
637 count
= lowpart_subreg (word_mode
, count
, mode
);
638 iterations
= lowpart_subreg (word_mode
, iterations
, mode
);
639 iterations_max
= lowpart_subreg (word_mode
, iterations_max
, mode
);
641 PUT_MODE (doloop_reg
, word_mode
);
642 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
643 GEN_INT (level
), start_label
);
649 "Doloop: Target unwilling to use doloop pattern!\n");
653 /* If multiple instructions were created, the last must be the
654 jump instruction. Also, a raw define_insn may yield a plain
656 doloop_pat
= doloop_seq
;
657 if (INSN_P (doloop_pat
))
659 while (NEXT_INSN (doloop_pat
) != NULL_RTX
)
660 doloop_pat
= NEXT_INSN (doloop_pat
);
661 if (!JUMP_P (doloop_pat
))
662 doloop_pat
= NULL_RTX
;
666 || ! (condition
= doloop_condition_get (doloop_pat
)))
669 fprintf (dump_file
, "Doloop: Unrecognizable doloop pattern!\n");
673 doloop_modify (loop
, desc
, doloop_seq
, condition
, count
);
677 /* This is the main entry point. Process all loops using doloop_optimize. */
680 doloop_optimize_loops (void)
685 FOR_EACH_LOOP (li
, loop
, 0)
687 doloop_optimize (loop
);
692 #ifdef ENABLE_CHECKING
693 verify_dominators (CDI_DOMINATORS
);
694 verify_loop_structure ();
697 #endif /* HAVE_doloop_end */