1 /* Perform doloop optimizations
2 Copyright (C) 2004, 2005, 2006, 2007, 2008, 2010
3 Free Software Foundation, Inc.
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"
31 #include "diagnostic-core.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)
106 rtx prev_insn = prev_nondebug_insn (doloop_pat);
108 /* We expect the decrement to immediately precede the branch. */
110 if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
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,
295 NULL_RTX, label, -1);
297 jump = get_last_insn ();
298 if (!jump || !JUMP_P (jump))
300 /* The condition is always false and the jump was optimized out. */
308 /* There always is at least the jump insn in the sequence. */
309 gcc_assert (seq != NULL_RTX);
311 bb = split_edge_and_insert (*e, seq);
312 *e = single_succ_edge (bb);
314 if (any_uncondjump_p (jump))
316 /* The condition is always true. */
318 redirect_edge_and_branch_force (*e, dest);
322 JUMP_LABEL (jump) = label;
324 /* The jump is supposed to handle an unlikely special case. */
325 add_reg_note (jump, REG_BR_PROB, const0_rtx);
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. */
521 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
523 /* Update the REG_BR_PROB note. */
526 /* Seems safer to use the branch probability. */
527 add_reg_note (jump_insn, REG_BR_PROB,
528 GEN_INT (desc->in_edge->probability));
532 /* Process loop described by LOOP validating that the loop is suitable for
533 conversion to use a low overhead looping instruction, replacing the jump
534 insn where suitable. Returns true if the loop was successfully
538 doloop_optimize (struct loop *loop)
540 enum machine_mode mode;
541 rtx doloop_seq, doloop_pat, doloop_reg;
542 rtx iterations, count;
546 unsigned level, est_niter;
548 struct niter_desc *desc;
549 unsigned word_mode_size;
550 unsigned HOST_WIDE_INT word_mode_max;
553 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
555 iv_analysis_loop_init (loop);
557 /* Find the simple exit of a LOOP. */
558 desc = get_simple_loop_desc (loop);
560 /* Check that loop is a candidate for a low-overhead looping insn. */
561 if (!doloop_valid_p (loop, desc))
565 "Doloop: The loop is not suitable.\n");
571 if (desc->const_iter)
572 est_niter = desc->niter;
573 /* If the estimate on number of iterations is reliable (comes from profile
574 feedback), use it. Do not use it normally, since the expected number
575 of iterations of an unrolled loop is 2. */
576 if (loop->header->count)
577 est_niter = expected_loop_iterations (loop);
583 "Doloop: Too few iterations (%u) to be profitable.\n",
589 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
590 if (rtx_cost (desc->niter_expr, SET, optimize_loop_for_speed_p (loop))
595 "Doloop: number of iterations too costly to compute.\n");
599 count = copy_rtx (desc->niter_expr);
600 iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
601 iterations_max = GEN_INT (desc->niter_max);
602 level = get_loop_level (loop) + 1;
604 /* Generate looping insn. If the pattern FAILs then give up trying
605 to modify the loop since there is some aspect the back-end does
607 start_label = block_label (desc->in_edge->dest);
608 doloop_reg = gen_reg_rtx (mode);
609 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
610 GEN_INT (level), start_label);
612 word_mode_size = GET_MODE_BITSIZE (word_mode);
614 = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
617 /* Before trying mode different from the one in that # of iterations is
618 computed, we must be sure that the number of iterations fits into
620 && (word_mode_size >= GET_MODE_BITSIZE (mode)
621 || desc->niter_max <= word_mode_max))
623 if (word_mode_size > GET_MODE_BITSIZE (mode))
625 count = simplify_gen_unary (ZERO_EXTEND, word_mode,
627 iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
629 iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
630 iterations_max, mode);
634 count = lowpart_subreg (word_mode, count, mode);
635 iterations = lowpart_subreg (word_mode, iterations, mode);
636 iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
638 PUT_MODE (doloop_reg, word_mode);
639 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
640 GEN_INT (level), start_label);
646 "Doloop: Target unwilling to use doloop pattern!\n");
650 /* If multiple instructions were created, the last must be the
651 jump instruction. Also, a raw define_insn may yield a plain
653 doloop_pat = doloop_seq;
654 if (INSN_P (doloop_pat))
656 while (NEXT_INSN (doloop_pat) != NULL_RTX)
657 doloop_pat = NEXT_INSN (doloop_pat);
658 if (!JUMP_P (doloop_pat))
659 doloop_pat = NULL_RTX;
663 || ! (condition = doloop_condition_get (doloop_pat)))
666 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
670 doloop_modify (loop, desc, doloop_seq, condition, count);
674 /* This is the main entry point. Process all loops using doloop_optimize. */
677 doloop_optimize_loops (void)
682 FOR_EACH_LOOP (li, loop, 0)
684 doloop_optimize (loop);
689 #ifdef ENABLE_CHECKING
690 verify_dominators (CDI_DOMINATORS);
691 verify_loop_structure ();
694 #endif /* HAVE_doloop_end */