1 /* Perform doloop optimizations
2 Copyright (C) 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
3 Based on code by Michael P. Hayes (m.hayes@elec.canterbury.ac.nz)
5 This file is part of GCC.
7 GCC is free software; you can redistribute it and/or modify it under
8 the terms of the GNU General Public License as published by the Free
9 Software Foundation; either version 3, or (at your option) any later
12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
14 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
17 You should have received a copy of the GNU General Public License
18 along with GCC; see the file COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
23 #include "coretypes.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
37 /* This module is used to modify loops with a determinable number of
38 iterations to use special low-overhead looping instructions.
40 It first validates whether the loop is well behaved and has a
41 determinable number of iterations (either at compile or run-time).
42 It then modifies the loop to use a low-overhead looping pattern as
45 1. A pseudo register is allocated as the loop iteration counter.
47 2. The number of loop iterations is calculated and is stored
50 3. At the end of the loop, the jump insn is replaced by the
51 doloop_end pattern. The compare must remain because it might be
52 used elsewhere. If the loop-variable or condition register are
53 used elsewhere, they will be eliminated by flow.
55 4. An optional doloop_begin pattern is inserted at the top of the
58 TODO The optimization should only performed when either the biv used for exit
59 condition is unused at all except for the exit test, or if we do not have to
60 change its value, since otherwise we have to add a new induction variable,
61 which usually will not pay up (unless the cost of the doloop pattern is
62 somehow extremely lower than the cost of compare & jump, or unless the bct
63 register cannot be used for anything else but doloop -- ??? detect these
66 #ifdef HAVE_doloop_end
68 /* Return the loop termination condition for PATTERN or zero
69 if it is not a decrement and branch jump insn. */
72 doloop_condition_get (rtx pattern
)
80 /* The canonical doloop pattern we expect is:
82 (parallel [(set (pc) (if_then_else (condition)
85 (set (reg) (plus (reg) (const_int -1)))
86 (additional clobbers and uses)])
88 Some targets (IA-64) wrap the set of the loop counter in
91 In summary, the branch must be the first entry of the
92 parallel (also required by jump.c), and the second
93 entry of the parallel must be a set of the loop counter
96 if (GET_CODE (pattern
) != PARALLEL
)
99 cmp
= XVECEXP (pattern
, 0, 0);
100 inc
= XVECEXP (pattern
, 0, 1);
102 /* Check for (set (reg) (something)). */
103 if (GET_CODE (inc
) != SET
)
105 reg
= SET_DEST (inc
);
109 /* Check if something = (plus (reg) (const_int -1)).
110 On IA-64, this decrement is wrapped in an if_then_else. */
111 inc_src
= SET_SRC (inc
);
112 if (GET_CODE (inc_src
) == IF_THEN_ELSE
)
113 inc_src
= XEXP (inc_src
, 1);
114 if (GET_CODE (inc_src
) != PLUS
115 || XEXP (inc_src
, 0) != reg
116 || XEXP (inc_src
, 1) != constm1_rtx
)
119 /* Check for (set (pc) (if_then_else (condition)
122 if (GET_CODE (cmp
) != SET
123 || SET_DEST (cmp
) != pc_rtx
124 || GET_CODE (SET_SRC (cmp
)) != IF_THEN_ELSE
125 || GET_CODE (XEXP (SET_SRC (cmp
), 1)) != LABEL_REF
126 || XEXP (SET_SRC (cmp
), 2) != pc_rtx
)
129 /* Extract loop termination condition. */
130 condition
= XEXP (SET_SRC (cmp
), 0);
132 /* We expect a GE or NE comparison with 0 or 1. */
133 if ((GET_CODE (condition
) != GE
134 && GET_CODE (condition
) != NE
)
135 || (XEXP (condition
, 1) != const0_rtx
136 && XEXP (condition
, 1) != const1_rtx
))
139 if ((XEXP (condition
, 0) == reg
)
140 || (GET_CODE (XEXP (condition
, 0)) == PLUS
141 && XEXP (XEXP (condition
, 0), 0) == reg
))
144 /* ??? If a machine uses a funny comparison, we could return a
145 canonicalized form here. */
150 /* Return nonzero if the loop specified by LOOP is suitable for
151 the use of special low-overhead looping instructions. DESC
152 describes the number of iterations of the loop. */
155 doloop_valid_p (struct loop
*loop
, struct niter_desc
*desc
)
157 basic_block
*body
= get_loop_body (loop
), bb
;
162 /* Check for loops that may not terminate under special conditions. */
167 /* There are some cases that would require a special attention.
168 For example if the comparison is LEU and the comparison value
169 is UINT_MAX then the loop will not terminate. Similarly, if the
170 comparison code is GEU and the comparison value is 0, the
171 loop will not terminate.
173 If the absolute increment is not 1, the loop can be infinite
174 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
176 ??? We could compute these conditions at run-time and have a
177 additional jump around the loop to ensure an infinite loop.
178 However, it is very unlikely that this is the intended
179 behavior of the loop and checking for these rare boundary
180 conditions would pessimize all other code.
182 If the loop is executed only a few times an extra check to
183 restart the loop could use up most of the benefits of using a
184 count register loop. Note however, that normally, this
185 restart branch would never execute, so it could be predicted
186 well by the CPU. We should generate the pessimistic code by
187 default, and have an option, e.g. -funsafe-loops that would
188 enable count-register loops in this case. */
190 fprintf (dump_file
, "Doloop: Possible infinite iteration case.\n");
195 for (i
= 0; i
< loop
->num_nodes
; i
++)
199 for (insn
= BB_HEAD (bb
);
200 insn
!= NEXT_INSN (BB_END (bb
));
201 insn
= NEXT_INSN (insn
))
203 /* Different targets have different necessities for low-overhead
204 looping. Call the back end for each instruction within the loop
205 to let it decide whether the insn prohibits a low-overhead loop.
206 It will then return the cause for it to emit to the dump file. */
207 const char * invalid
= targetm
.invalid_within_doloop (insn
);
211 fprintf (dump_file
, "Doloop: %s\n", invalid
);
225 /* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru
226 edge. If the condition is always false, do not do anything. If it is always
227 true, redirect E to DEST and return false. In all other cases, true is
231 add_test (rtx cond
, edge
*e
, basic_block dest
)
233 rtx seq
, jump
, label
;
234 enum machine_mode mode
;
235 rtx op0
= XEXP (cond
, 0), op1
= XEXP (cond
, 1);
236 enum rtx_code code
= GET_CODE (cond
);
239 mode
= GET_MODE (XEXP (cond
, 0));
240 if (mode
== VOIDmode
)
241 mode
= GET_MODE (XEXP (cond
, 1));
244 op0
= force_operand (op0
, NULL_RTX
);
245 op1
= force_operand (op1
, NULL_RTX
);
246 label
= block_label (dest
);
247 do_compare_rtx_and_jump (op0
, op1
, code
, 0, mode
, NULL_RTX
, NULL_RTX
, label
);
249 jump
= get_last_insn ();
250 if (!jump
|| !JUMP_P (jump
))
252 /* The condition is always false and the jump was optimized out. */
260 /* There always is at least the jump insn in the sequence. */
261 gcc_assert (seq
!= NULL_RTX
);
263 bb
= split_edge_and_insert (*e
, seq
);
264 *e
= single_succ_edge (bb
);
266 if (any_uncondjump_p (jump
))
268 /* The condition is always true. */
270 redirect_edge_and_branch_force (*e
, dest
);
274 JUMP_LABEL (jump
) = label
;
276 /* The jump is supposed to handle an unlikely special case. */
278 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
279 const0_rtx
, REG_NOTES (jump
));
280 LABEL_NUSES (label
)++;
282 make_edge (bb
, dest
, (*e
)->flags
& ~EDGE_FALLTHRU
);
286 /* Modify the loop to use the low-overhead looping insn where LOOP
287 describes the loop, DESC describes the number of iterations of the
288 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
289 end of the loop. CONDITION is the condition separated from the
290 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
293 doloop_modify (struct loop
*loop
, struct niter_desc
*desc
,
294 rtx doloop_seq
, rtx condition
, rtx count
)
297 rtx tmp
, noloop
= NULL_RTX
;
302 bool increment_count
;
303 basic_block loop_end
= desc
->out_edge
->src
;
304 enum machine_mode mode
;
306 jump_insn
= BB_END (loop_end
);
310 fprintf (dump_file
, "Doloop: Inserting doloop pattern (");
311 if (desc
->const_iter
)
312 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
314 fputs ("runtime", dump_file
);
315 fputs (" iterations).\n", dump_file
);
318 /* Discard original jump to continue loop. The original compare
319 result may still be live, so it cannot be discarded explicitly. */
320 delete_insn (jump_insn
);
322 counter_reg
= XEXP (condition
, 0);
323 if (GET_CODE (counter_reg
) == PLUS
)
324 counter_reg
= XEXP (counter_reg
, 0);
325 mode
= GET_MODE (counter_reg
);
327 increment_count
= false;
328 switch (GET_CODE (condition
))
331 /* Currently only NE tests against zero and one are supported. */
332 noloop
= XEXP (condition
, 1);
333 if (noloop
!= const0_rtx
)
335 gcc_assert (noloop
== const1_rtx
);
336 increment_count
= true;
341 /* Currently only GE tests against zero are supported. */
342 gcc_assert (XEXP (condition
, 1) == const0_rtx
);
344 noloop
= constm1_rtx
;
346 /* The iteration count does not need incrementing for a GE test. */
347 increment_count
= false;
349 /* Determine if the iteration counter will be non-negative.
350 Note that the maximum value loaded is iterations_max - 1. */
352 <= ((unsigned HOST_WIDEST_INT
) 1
353 << (GET_MODE_BITSIZE (mode
) - 1)))
357 /* Abort if an invalid doloop pattern has been generated. */
363 count
= simplify_gen_binary (PLUS
, mode
, count
, const1_rtx
);
365 /* Insert initialization of the count register into the loop header. */
367 tmp
= force_operand (count
, counter_reg
);
368 convert_move (counter_reg
, tmp
, 1);
369 sequence
= get_insns ();
371 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
373 if (desc
->noloop_assumptions
)
375 rtx ass
= copy_rtx (desc
->noloop_assumptions
);
376 basic_block preheader
= loop_preheader_edge (loop
)->src
;
378 = split_edge (loop_preheader_edge (loop
));
379 basic_block new_preheader
380 = split_edge (loop_preheader_edge (loop
));
383 /* Expand the condition testing the assumptions and if it does not pass,
384 reset the count register to 0. */
385 redirect_edge_and_branch_force (single_succ_edge (preheader
), new_preheader
);
386 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
, preheader
);
389 set_zero
->frequency
= 0;
391 te
= single_succ_edge (preheader
);
392 for (; ass
; ass
= XEXP (ass
, 1))
393 if (!add_test (XEXP (ass
, 0), &te
, set_zero
))
398 /* We reached a condition that is always true. This is very hard to
399 reproduce (such a loop does not roll, and thus it would most
400 likely get optimized out by some of the preceding optimizations).
401 In fact, I do not have any testcase for it. However, it would
402 also be very hard to show that it is impossible, so we must
404 set_zero
->count
= preheader
->count
;
405 set_zero
->frequency
= preheader
->frequency
;
408 if (EDGE_COUNT (set_zero
->preds
) == 0)
410 /* All the conditions were simplified to false, remove the
411 unreachable set_zero block. */
412 delete_basic_block (set_zero
);
416 /* Reset the counter to zero in the set_zero block. */
418 convert_move (counter_reg
, noloop
, 0);
419 sequence
= get_insns ();
421 emit_insn_after (sequence
, BB_END (set_zero
));
423 set_immediate_dominator (CDI_DOMINATORS
, set_zero
,
424 recompute_dominator (CDI_DOMINATORS
,
428 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
,
429 recompute_dominator (CDI_DOMINATORS
,
433 /* Some targets (eg, C4x) need to initialize special looping
435 #ifdef HAVE_doloop_begin
438 unsigned level
= get_loop_level (loop
) + 1;
439 init
= gen_doloop_begin (counter_reg
,
440 desc
->const_iter
? desc
->niter_expr
: const0_rtx
,
441 GEN_INT (desc
->niter_max
),
447 sequence
= get_insns ();
449 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
454 /* Insert the new low-overhead looping insn. */
455 emit_jump_insn_after (doloop_seq
, BB_END (loop_end
));
456 jump_insn
= BB_END (loop_end
);
457 jump_label
= block_label (desc
->in_edge
->dest
);
458 JUMP_LABEL (jump_insn
) = jump_label
;
459 LABEL_NUSES (jump_label
)++;
461 /* Ensure the right fallthru edge is marked, for case we have reversed
463 desc
->in_edge
->flags
&= ~EDGE_FALLTHRU
;
464 desc
->out_edge
->flags
|= EDGE_FALLTHRU
;
466 /* Add a REG_NONNEG note if the actual or estimated maximum number
467 of iterations is non-negative. */
470 REG_NOTES (jump_insn
)
471 = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
, REG_NOTES (jump_insn
));
475 /* Process loop described by LOOP validating that the loop is suitable for
476 conversion to use a low overhead looping instruction, replacing the jump
477 insn where suitable. Returns true if the loop was successfully
481 doloop_optimize (struct loop
*loop
)
483 enum machine_mode mode
;
484 rtx doloop_seq
, doloop_pat
, doloop_reg
;
485 rtx iterations
, count
;
489 unsigned level
, est_niter
;
491 struct niter_desc
*desc
;
492 unsigned word_mode_size
;
493 unsigned HOST_WIDE_INT word_mode_max
;
496 fprintf (dump_file
, "Doloop: Processing loop %d.\n", loop
->num
);
498 iv_analysis_loop_init (loop
);
500 /* Find the simple exit of a LOOP. */
501 desc
= get_simple_loop_desc (loop
);
503 /* Check that loop is a candidate for a low-overhead looping insn. */
504 if (!doloop_valid_p (loop
, desc
))
508 "Doloop: The loop is not suitable.\n");
514 if (desc
->const_iter
)
515 est_niter
= desc
->niter
;
516 /* If the estimate on number of iterations is reliable (comes from profile
517 feedback), use it. Do not use it normally, since the expected number
518 of iterations of an unrolled loop is 2. */
519 if (loop
->header
->count
)
520 est_niter
= expected_loop_iterations (loop
);
526 "Doloop: Too few iterations (%u) to be profitable.\n",
532 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST
));
533 if (rtx_cost (desc
->niter_expr
, SET
) > max_cost
)
537 "Doloop: number of iterations too costly to compute.\n");
541 count
= copy_rtx (desc
->niter_expr
);
542 iterations
= desc
->const_iter
? desc
->niter_expr
: const0_rtx
;
543 iterations_max
= GEN_INT (desc
->niter_max
);
544 level
= get_loop_level (loop
) + 1;
546 /* Generate looping insn. If the pattern FAILs then give up trying
547 to modify the loop since there is some aspect the back-end does
549 start_label
= block_label (desc
->in_edge
->dest
);
550 doloop_reg
= gen_reg_rtx (mode
);
551 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
552 GEN_INT (level
), start_label
);
554 word_mode_size
= GET_MODE_BITSIZE (word_mode
);
556 = ((unsigned HOST_WIDE_INT
) 1 << (word_mode_size
- 1) << 1) - 1;
559 /* Before trying mode different from the one in that # of iterations is
560 computed, we must be sure that the number of iterations fits into
562 && (word_mode_size
>= GET_MODE_BITSIZE (mode
)
563 || desc
->niter_max
<= word_mode_max
))
565 if (word_mode_size
> GET_MODE_BITSIZE (mode
))
567 count
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
569 iterations
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
571 iterations_max
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
572 iterations_max
, mode
);
576 count
= lowpart_subreg (word_mode
, count
, mode
);
577 iterations
= lowpart_subreg (word_mode
, iterations
, mode
);
578 iterations_max
= lowpart_subreg (word_mode
, iterations_max
, mode
);
580 PUT_MODE (doloop_reg
, word_mode
);
581 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
582 GEN_INT (level
), start_label
);
588 "Doloop: Target unwilling to use doloop pattern!\n");
592 /* If multiple instructions were created, the last must be the
593 jump instruction. Also, a raw define_insn may yield a plain
595 doloop_pat
= doloop_seq
;
596 if (INSN_P (doloop_pat
))
598 while (NEXT_INSN (doloop_pat
) != NULL_RTX
)
599 doloop_pat
= NEXT_INSN (doloop_pat
);
600 if (JUMP_P (doloop_pat
))
601 doloop_pat
= PATTERN (doloop_pat
);
603 doloop_pat
= NULL_RTX
;
607 || ! (condition
= doloop_condition_get (doloop_pat
)))
610 fprintf (dump_file
, "Doloop: Unrecognizable doloop pattern!\n");
614 doloop_modify (loop
, desc
, doloop_seq
, condition
, count
);
618 /* This is the main entry point. Process all loops using doloop_optimize. */
621 doloop_optimize_loops (void)
626 FOR_EACH_LOOP (li
, loop
, 0)
628 doloop_optimize (loop
);
633 #ifdef ENABLE_CHECKING
634 verify_dominators (CDI_DOMINATORS
);
635 verify_loop_structure ();
638 #endif /* HAVE_doloop_end */