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"
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.
338 ZERO_EXTEND_P says to zero extend COUNT after the increment of it to
339 word_mode from FROM_MODE. */
342 doloop_modify (struct loop
*loop
, struct niter_desc
*desc
,
343 rtx doloop_seq
, rtx condition
, rtx count
,
344 bool zero_extend_p
, enum machine_mode from_mode
)
347 rtx tmp
, noloop
= NULL_RTX
;
352 bool increment_count
;
353 basic_block loop_end
= desc
->out_edge
->src
;
354 enum machine_mode mode
;
357 jump_insn
= BB_END (loop_end
);
361 fprintf (dump_file
, "Doloop: Inserting doloop pattern (");
362 if (desc
->const_iter
)
363 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
365 fputs ("runtime", dump_file
);
366 fputs (" iterations).\n", dump_file
);
369 /* Get the probability of the original branch. If it exists we would
370 need to update REG_BR_PROB of the new jump_insn. */
371 true_prob_val
= find_reg_note (jump_insn
, REG_BR_PROB
, NULL_RTX
);
373 /* Discard original jump to continue loop. The original compare
374 result may still be live, so it cannot be discarded explicitly. */
375 delete_insn (jump_insn
);
377 counter_reg
= XEXP (condition
, 0);
378 if (GET_CODE (counter_reg
) == PLUS
)
379 counter_reg
= XEXP (counter_reg
, 0);
380 mode
= GET_MODE (counter_reg
);
382 increment_count
= false;
383 switch (GET_CODE (condition
))
386 /* Currently only NE tests against zero and one are supported. */
387 noloop
= XEXP (condition
, 1);
388 if (noloop
!= const0_rtx
)
390 gcc_assert (noloop
== const1_rtx
);
391 increment_count
= true;
396 /* Currently only GE tests against zero are supported. */
397 gcc_assert (XEXP (condition
, 1) == const0_rtx
);
399 noloop
= constm1_rtx
;
401 /* The iteration count does not need incrementing for a GE test. */
402 increment_count
= false;
404 /* Determine if the iteration counter will be non-negative.
405 Note that the maximum value loaded is iterations_max - 1. */
407 <= ((unsigned HOST_WIDEST_INT
) 1
408 << (GET_MODE_BITSIZE (mode
) - 1)))
412 /* Abort if an invalid doloop pattern has been generated. */
418 count
= simplify_gen_binary (PLUS
, from_mode
, count
, const1_rtx
);
421 count
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
424 /* Insert initialization of the count register into the loop header. */
426 tmp
= force_operand (count
, counter_reg
);
427 convert_move (counter_reg
, tmp
, 1);
428 sequence
= get_insns ();
430 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
432 if (desc
->noloop_assumptions
)
434 rtx ass
= copy_rtx (desc
->noloop_assumptions
);
435 basic_block preheader
= loop_preheader_edge (loop
)->src
;
437 = split_edge (loop_preheader_edge (loop
));
438 basic_block new_preheader
439 = split_edge (loop_preheader_edge (loop
));
442 /* Expand the condition testing the assumptions and if it does not pass,
443 reset the count register to 0. */
444 redirect_edge_and_branch_force (single_succ_edge (preheader
), new_preheader
);
445 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
, preheader
);
448 set_zero
->frequency
= 0;
450 te
= single_succ_edge (preheader
);
451 for (; ass
; ass
= XEXP (ass
, 1))
452 if (!add_test (XEXP (ass
, 0), &te
, set_zero
))
457 /* We reached a condition that is always true. This is very hard to
458 reproduce (such a loop does not roll, and thus it would most
459 likely get optimized out by some of the preceding optimizations).
460 In fact, I do not have any testcase for it. However, it would
461 also be very hard to show that it is impossible, so we must
463 set_zero
->count
= preheader
->count
;
464 set_zero
->frequency
= preheader
->frequency
;
467 if (EDGE_COUNT (set_zero
->preds
) == 0)
469 /* All the conditions were simplified to false, remove the
470 unreachable set_zero block. */
471 delete_basic_block (set_zero
);
475 /* Reset the counter to zero in the set_zero block. */
477 convert_move (counter_reg
, noloop
, 0);
478 sequence
= get_insns ();
480 emit_insn_after (sequence
, BB_END (set_zero
));
482 set_immediate_dominator (CDI_DOMINATORS
, set_zero
,
483 recompute_dominator (CDI_DOMINATORS
,
487 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
,
488 recompute_dominator (CDI_DOMINATORS
,
492 /* Some targets (eg, C4x) need to initialize special looping
494 #ifdef HAVE_doloop_begin
497 unsigned level
= get_loop_level (loop
) + 1;
498 init
= gen_doloop_begin (counter_reg
,
499 desc
->const_iter
? desc
->niter_expr
: const0_rtx
,
500 GEN_INT (desc
->niter_max
),
506 sequence
= get_insns ();
508 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
513 /* Insert the new low-overhead looping insn. */
514 emit_jump_insn_after (doloop_seq
, BB_END (loop_end
));
515 jump_insn
= BB_END (loop_end
);
516 jump_label
= block_label (desc
->in_edge
->dest
);
517 JUMP_LABEL (jump_insn
) = jump_label
;
518 LABEL_NUSES (jump_label
)++;
520 /* Ensure the right fallthru edge is marked, for case we have reversed
522 desc
->in_edge
->flags
&= ~EDGE_FALLTHRU
;
523 desc
->out_edge
->flags
|= EDGE_FALLTHRU
;
525 /* Add a REG_NONNEG note if the actual or estimated maximum number
526 of iterations is non-negative. */
528 add_reg_note (jump_insn
, REG_NONNEG
, NULL_RTX
);
530 /* Update the REG_BR_PROB note. */
533 /* Seems safer to use the branch probability. */
534 add_reg_note (jump_insn
, REG_BR_PROB
,
535 GEN_INT (desc
->in_edge
->probability
));
539 /* Process loop described by LOOP validating that the loop is suitable for
540 conversion to use a low overhead looping instruction, replacing the jump
541 insn where suitable. Returns true if the loop was successfully
545 doloop_optimize (struct loop
*loop
)
547 enum machine_mode mode
;
548 rtx doloop_seq
, doloop_pat
, doloop_reg
;
549 rtx iterations
, count
;
553 unsigned level
, est_niter
;
555 struct niter_desc
*desc
;
556 unsigned word_mode_size
;
557 unsigned HOST_WIDE_INT word_mode_max
;
558 bool zero_extend_p
= false;
561 fprintf (dump_file
, "Doloop: Processing loop %d.\n", loop
->num
);
563 iv_analysis_loop_init (loop
);
565 /* Find the simple exit of a LOOP. */
566 desc
= get_simple_loop_desc (loop
);
568 /* Check that loop is a candidate for a low-overhead looping insn. */
569 if (!doloop_valid_p (loop
, desc
))
573 "Doloop: The loop is not suitable.\n");
579 if (desc
->const_iter
)
580 est_niter
= desc
->niter
;
581 /* If the estimate on number of iterations is reliable (comes from profile
582 feedback), use it. Do not use it normally, since the expected number
583 of iterations of an unrolled loop is 2. */
584 if (loop
->header
->count
)
585 est_niter
= expected_loop_iterations (loop
);
591 "Doloop: Too few iterations (%u) to be profitable.\n",
597 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST
));
598 if (rtx_cost (desc
->niter_expr
, SET
, optimize_loop_for_speed_p (loop
))
603 "Doloop: number of iterations too costly to compute.\n");
607 count
= copy_rtx (desc
->niter_expr
);
608 iterations
= desc
->const_iter
? desc
->niter_expr
: const0_rtx
;
609 iterations_max
= GEN_INT (desc
->niter_max
);
610 level
= get_loop_level (loop
) + 1;
612 /* Generate looping insn. If the pattern FAILs then give up trying
613 to modify the loop since there is some aspect the back-end does
615 start_label
= block_label (desc
->in_edge
->dest
);
616 doloop_reg
= gen_reg_rtx (mode
);
617 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
618 GEN_INT (level
), start_label
);
620 word_mode_size
= GET_MODE_BITSIZE (word_mode
);
622 = ((unsigned HOST_WIDE_INT
) 1 << (word_mode_size
- 1) << 1) - 1;
625 /* Before trying mode different from the one in that # of iterations is
626 computed, we must be sure that the number of iterations fits into
628 && (word_mode_size
>= GET_MODE_BITSIZE (mode
)
629 || desc
->niter_max
<= word_mode_max
))
631 if (word_mode_size
> GET_MODE_BITSIZE (mode
))
633 zero_extend_p
= true;
634 iterations
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
636 iterations_max
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
637 iterations_max
, mode
);
641 count
= lowpart_subreg (word_mode
, count
, mode
);
642 iterations
= lowpart_subreg (word_mode
, iterations
, mode
);
643 iterations_max
= lowpart_subreg (word_mode
, iterations_max
, mode
);
645 PUT_MODE (doloop_reg
, word_mode
);
646 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
647 GEN_INT (level
), start_label
);
653 "Doloop: Target unwilling to use doloop pattern!\n");
657 /* If multiple instructions were created, the last must be the
658 jump instruction. Also, a raw define_insn may yield a plain
660 doloop_pat
= doloop_seq
;
661 if (INSN_P (doloop_pat
))
663 while (NEXT_INSN (doloop_pat
) != NULL_RTX
)
664 doloop_pat
= NEXT_INSN (doloop_pat
);
665 if (!JUMP_P (doloop_pat
))
666 doloop_pat
= NULL_RTX
;
670 || ! (condition
= doloop_condition_get (doloop_pat
)))
673 fprintf (dump_file
, "Doloop: Unrecognizable doloop pattern!\n");
677 doloop_modify (loop
, desc
, doloop_seq
, condition
, count
,
678 zero_extend_p
, mode
);
682 /* This is the main entry point. Process all loops using doloop_optimize. */
685 doloop_optimize_loops (void)
690 FOR_EACH_LOOP (li
, loop
, 0)
692 doloop_optimize (loop
);
697 #ifdef ENABLE_CHECKING
698 verify_dominators (CDI_DOMINATORS
);
699 verify_loop_structure ();
702 #endif /* HAVE_doloop_end */