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. */
324 add_reg_note (jump, REG_BR_PROB, const0_rtx);
326 LABEL_NUSES (label)++;
328 make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
332 /* Modify the loop to use the low-overhead looping insn where LOOP
333 describes the loop, DESC describes the number of iterations of the
334 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
335 end of the loop. CONDITION is the condition separated from the
336 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP.
337 ZERO_EXTEND_P says to zero extend COUNT after the increment of it to
341 doloop_modify (struct loop *loop, struct niter_desc *desc,
342 rtx doloop_seq, rtx condition, rtx count, bool zero_extend_p)
345 rtx tmp, noloop = NULL_RTX;
350 bool increment_count;
351 basic_block loop_end = desc->out_edge->src;
352 enum machine_mode mode;
355 jump_insn = BB_END (loop_end);
359 fprintf (dump_file, "Doloop: Inserting doloop pattern (");
360 if (desc->const_iter)
361 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
363 fputs ("runtime", dump_file);
364 fputs (" iterations).\n", dump_file);
367 /* Get the probability of the original branch. If it exists we would
368 need to update REG_BR_PROB of the new jump_insn. */
369 true_prob_val = find_reg_note (jump_insn, REG_BR_PROB, NULL_RTX);
371 /* Discard original jump to continue loop. The original compare
372 result may still be live, so it cannot be discarded explicitly. */
373 delete_insn (jump_insn);
375 counter_reg = XEXP (condition, 0);
376 if (GET_CODE (counter_reg) == PLUS)
377 counter_reg = XEXP (counter_reg, 0);
378 mode = GET_MODE (counter_reg);
380 increment_count = false;
381 switch (GET_CODE (condition))
384 /* Currently only NE tests against zero and one are supported. */
385 noloop = XEXP (condition, 1);
386 if (noloop != const0_rtx)
388 gcc_assert (noloop == const1_rtx);
389 increment_count = true;
394 /* Currently only GE tests against zero are supported. */
395 gcc_assert (XEXP (condition, 1) == const0_rtx);
397 noloop = constm1_rtx;
399 /* The iteration count does not need incrementing for a GE test. */
400 increment_count = false;
402 /* Determine if the iteration counter will be non-negative.
403 Note that the maximum value loaded is iterations_max - 1. */
405 <= ((unsigned HOST_WIDEST_INT) 1
406 << (GET_MODE_BITSIZE (mode) - 1)))
410 /* Abort if an invalid doloop pattern has been generated. */
416 count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
419 count = simplify_gen_unary (ZERO_EXTEND, word_mode,
422 /* Insert initialization of the count register into the loop header. */
424 tmp = force_operand (count, counter_reg);
425 convert_move (counter_reg, tmp, 1);
426 sequence = get_insns ();
428 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
430 if (desc->noloop_assumptions)
432 rtx ass = copy_rtx (desc->noloop_assumptions);
433 basic_block preheader = loop_preheader_edge (loop)->src;
435 = split_edge (loop_preheader_edge (loop));
436 basic_block new_preheader
437 = split_edge (loop_preheader_edge (loop));
440 /* Expand the condition testing the assumptions and if it does not pass,
441 reset the count register to 0. */
442 redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader);
443 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
446 set_zero->frequency = 0;
448 te = single_succ_edge (preheader);
449 for (; ass; ass = XEXP (ass, 1))
450 if (!add_test (XEXP (ass, 0), &te, set_zero))
455 /* We reached a condition that is always true. This is very hard to
456 reproduce (such a loop does not roll, and thus it would most
457 likely get optimized out by some of the preceding optimizations).
458 In fact, I do not have any testcase for it. However, it would
459 also be very hard to show that it is impossible, so we must
461 set_zero->count = preheader->count;
462 set_zero->frequency = preheader->frequency;
465 if (EDGE_COUNT (set_zero->preds) == 0)
467 /* All the conditions were simplified to false, remove the
468 unreachable set_zero block. */
469 delete_basic_block (set_zero);
473 /* Reset the counter to zero in the set_zero block. */
475 convert_move (counter_reg, noloop, 0);
476 sequence = get_insns ();
478 emit_insn_after (sequence, BB_END (set_zero));
480 set_immediate_dominator (CDI_DOMINATORS, set_zero,
481 recompute_dominator (CDI_DOMINATORS,
485 set_immediate_dominator (CDI_DOMINATORS, new_preheader,
486 recompute_dominator (CDI_DOMINATORS,
490 /* Some targets (eg, C4x) need to initialize special looping
492 #ifdef HAVE_doloop_begin
495 unsigned level = get_loop_level (loop) + 1;
496 init = gen_doloop_begin (counter_reg,
497 desc->const_iter ? desc->niter_expr : const0_rtx,
498 GEN_INT (desc->niter_max),
504 sequence = get_insns ();
506 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
511 /* Insert the new low-overhead looping insn. */
512 emit_jump_insn_after (doloop_seq, BB_END (loop_end));
513 jump_insn = BB_END (loop_end);
514 jump_label = block_label (desc->in_edge->dest);
515 JUMP_LABEL (jump_insn) = jump_label;
516 LABEL_NUSES (jump_label)++;
518 /* Ensure the right fallthru edge is marked, for case we have reversed
520 desc->in_edge->flags &= ~EDGE_FALLTHRU;
521 desc->out_edge->flags |= EDGE_FALLTHRU;
523 /* Add a REG_NONNEG note if the actual or estimated maximum number
524 of iterations is non-negative. */
526 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
528 /* Update the REG_BR_PROB note. */
531 /* Seems safer to use the branch probability. */
532 add_reg_note (jump_insn, REG_BR_PROB,
533 GEN_INT (desc->in_edge->probability));
537 /* Process loop described by LOOP validating that the loop is suitable for
538 conversion to use a low overhead looping instruction, replacing the jump
539 insn where suitable. Returns true if the loop was successfully
543 doloop_optimize (struct loop *loop)
545 enum machine_mode mode;
546 rtx doloop_seq, doloop_pat, doloop_reg;
547 rtx iterations, count;
551 unsigned level, est_niter;
553 struct niter_desc *desc;
554 unsigned word_mode_size;
555 unsigned HOST_WIDE_INT word_mode_max;
556 bool zero_extend_p = false;
559 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
561 iv_analysis_loop_init (loop);
563 /* Find the simple exit of a LOOP. */
564 desc = get_simple_loop_desc (loop);
566 /* Check that loop is a candidate for a low-overhead looping insn. */
567 if (!doloop_valid_p (loop, desc))
571 "Doloop: The loop is not suitable.\n");
577 if (desc->const_iter)
578 est_niter = desc->niter;
579 /* If the estimate on number of iterations is reliable (comes from profile
580 feedback), use it. Do not use it normally, since the expected number
581 of iterations of an unrolled loop is 2. */
582 if (loop->header->count)
583 est_niter = expected_loop_iterations (loop);
589 "Doloop: Too few iterations (%u) to be profitable.\n",
595 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
596 if (rtx_cost (desc->niter_expr, SET, optimize_loop_for_speed_p (loop))
601 "Doloop: number of iterations too costly to compute.\n");
605 count = copy_rtx (desc->niter_expr);
606 iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
607 iterations_max = GEN_INT (desc->niter_max);
608 level = get_loop_level (loop) + 1;
610 /* Generate looping insn. If the pattern FAILs then give up trying
611 to modify the loop since there is some aspect the back-end does
613 start_label = block_label (desc->in_edge->dest);
614 doloop_reg = gen_reg_rtx (mode);
615 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
616 GEN_INT (level), start_label);
618 word_mode_size = GET_MODE_BITSIZE (word_mode);
620 = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
623 /* Before trying mode different from the one in that # of iterations is
624 computed, we must be sure that the number of iterations fits into
626 && (word_mode_size >= GET_MODE_BITSIZE (mode)
627 || desc->niter_max <= word_mode_max))
629 if (word_mode_size > GET_MODE_BITSIZE (mode))
631 zero_extend_p = true;
632 iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
634 iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
635 iterations_max, mode);
639 count = lowpart_subreg (word_mode, count, mode);
640 iterations = lowpart_subreg (word_mode, iterations, mode);
641 iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
643 PUT_MODE (doloop_reg, word_mode);
644 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
645 GEN_INT (level), start_label);
651 "Doloop: Target unwilling to use doloop pattern!\n");
655 /* If multiple instructions were created, the last must be the
656 jump instruction. Also, a raw define_insn may yield a plain
658 doloop_pat = doloop_seq;
659 if (INSN_P (doloop_pat))
661 while (NEXT_INSN (doloop_pat) != NULL_RTX)
662 doloop_pat = NEXT_INSN (doloop_pat);
663 if (!JUMP_P (doloop_pat))
664 doloop_pat = NULL_RTX;
668 || ! (condition = doloop_condition_get (doloop_pat)))
671 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
675 doloop_modify (loop, desc, doloop_seq, condition, count, zero_extend_p);
679 /* This is the main entry point. Process all loops using doloop_optimize. */
682 doloop_optimize_loops (void)
687 FOR_EACH_LOOP (li, loop, 0)
689 doloop_optimize (loop);
694 #ifdef ENABLE_CHECKING
695 verify_dominators (CDI_DOMINATORS);
696 verify_loop_structure ();
699 #endif /* HAVE_doloop_end */