1 /* Perform doloop optimizations
2 Copyright (C) 2004, 2005 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 2, 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 COPYING. If not, write to the Free
19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
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 pattern
)
81 /* The canonical doloop pattern we expect is:
83 (parallel [(set (pc) (if_then_else (condition)
86 (set (reg) (plus (reg) (const_int -1)))
87 (additional clobbers and uses)])
89 Some targets (IA-64) wrap the set of the loop counter in
92 In summary, the branch must be the first entry of the
93 parallel (also required by jump.c), and the second
94 entry of the parallel must be a set of the loop counter
97 if (GET_CODE (pattern
) != PARALLEL
)
100 cmp
= XVECEXP (pattern
, 0, 0);
101 inc
= XVECEXP (pattern
, 0, 1);
103 /* Check for (set (reg) (something)). */
104 if (GET_CODE (inc
) != SET
)
106 reg
= SET_DEST (inc
);
110 /* Check if something = (plus (reg) (const_int -1)).
111 On IA-64, this decrement is wrapped in an if_then_else. */
112 inc_src
= SET_SRC (inc
);
113 if (GET_CODE (inc_src
) == IF_THEN_ELSE
)
114 inc_src
= XEXP (inc_src
, 1);
115 if (GET_CODE (inc_src
) != PLUS
116 || XEXP (inc_src
, 0) != reg
117 || XEXP (inc_src
, 1) != constm1_rtx
)
120 /* Check for (set (pc) (if_then_else (condition)
123 if (GET_CODE (cmp
) != SET
124 || SET_DEST (cmp
) != pc_rtx
125 || GET_CODE (SET_SRC (cmp
)) != IF_THEN_ELSE
126 || GET_CODE (XEXP (SET_SRC (cmp
), 1)) != LABEL_REF
127 || XEXP (SET_SRC (cmp
), 2) != pc_rtx
)
130 /* Extract loop termination condition. */
131 condition
= XEXP (SET_SRC (cmp
), 0);
133 /* We expect a GE or NE comparison with 0 or 1. */
134 if ((GET_CODE (condition
) != GE
135 && GET_CODE (condition
) != NE
)
136 || (XEXP (condition
, 1) != const0_rtx
137 && XEXP (condition
, 1) != const1_rtx
))
140 if ((XEXP (condition
, 0) == reg
)
141 || (GET_CODE (XEXP (condition
, 0)) == PLUS
142 && XEXP (XEXP (condition
, 0), 0) == reg
))
145 /* ??? If a machine uses a funny comparison, we could return a
146 canonicalized form here. */
151 /* Return nonzero if the loop specified by LOOP is suitable for
152 the use of special low-overhead looping instructions. DESC
153 describes the number of iterations of the loop. */
156 doloop_valid_p (struct loop
*loop
, struct niter_desc
*desc
)
158 basic_block
*body
= get_loop_body (loop
), bb
;
163 /* Check for loops that may not terminate under special conditions. */
168 /* There are some cases that would require a special attention.
169 For example if the comparison is LEU and the comparison value
170 is UINT_MAX then the loop will not terminate. Similarly, if the
171 comparison code is GEU and the comparison value is 0, the
172 loop will not terminate.
174 If the absolute increment is not 1, the loop can be infinite
175 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
177 ??? We could compute these conditions at run-time and have a
178 additional jump around the loop to ensure an infinite loop.
179 However, it is very unlikely that this is the intended
180 behavior of the loop and checking for these rare boundary
181 conditions would pessimize all other code.
183 If the loop is executed only a few times an extra check to
184 restart the loop could use up most of the benefits of using a
185 count register loop. Note however, that normally, this
186 restart branch would never execute, so it could be predicted
187 well by the CPU. We should generate the pessimistic code by
188 default, and have an option, e.g. -funsafe-loops that would
189 enable count-register loops in this case. */
191 fprintf (dump_file
, "Doloop: Possible infinite iteration case.\n");
196 for (i
= 0; i
< loop
->num_nodes
; i
++)
200 for (insn
= BB_HEAD (bb
);
201 insn
!= NEXT_INSN (BB_END (bb
));
202 insn
= NEXT_INSN (insn
))
204 /* Different targets have different necessities for low-overhead
205 looping. Call the back end for each instruction within the loop
206 to let it decide whether the insn is valid. */
207 if (!targetm
.insn_valid_within_doloop (insn
))
222 /* Adds test of COND jumping to DEST to the end of BB. */
225 add_test (rtx cond
, basic_block bb
, basic_block dest
)
227 rtx seq
, jump
, label
;
228 enum machine_mode mode
;
229 rtx op0
= XEXP (cond
, 0), op1
= XEXP (cond
, 1);
230 enum rtx_code code
= GET_CODE (cond
);
232 mode
= GET_MODE (XEXP (cond
, 0));
233 if (mode
== VOIDmode
)
234 mode
= GET_MODE (XEXP (cond
, 1));
237 op0
= force_operand (op0
, NULL_RTX
);
238 op1
= force_operand (op1
, NULL_RTX
);
239 label
= block_label (dest
);
240 do_compare_rtx_and_jump (op0
, op1
, code
, 0, mode
, NULL_RTX
, NULL_RTX
, label
);
242 jump
= get_last_insn ();
243 JUMP_LABEL (jump
) = label
;
245 /* The jump is supposed to handle an unlikely special case. */
247 = gen_rtx_EXPR_LIST (REG_BR_PROB
,
248 const0_rtx
, REG_NOTES (jump
));
250 LABEL_NUSES (label
)++;
254 emit_insn_after (seq
, BB_END (bb
));
257 /* Modify the loop to use the low-overhead looping insn where LOOP
258 describes the loop, DESC describes the number of iterations of the
259 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
260 end of the loop. CONDITION is the condition separated from the
261 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
264 doloop_modify (struct loop
*loop
, struct niter_desc
*desc
,
265 rtx doloop_seq
, rtx condition
, rtx count
)
268 rtx tmp
, noloop
= NULL_RTX
;
273 bool increment_count
;
274 basic_block loop_end
= desc
->out_edge
->src
;
275 enum machine_mode mode
;
277 jump_insn
= BB_END (loop_end
);
281 fprintf (dump_file
, "Doloop: Inserting doloop pattern (");
282 if (desc
->const_iter
)
283 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
285 fputs ("runtime", dump_file
);
286 fputs (" iterations).\n", dump_file
);
289 /* Discard original jump to continue loop. The original compare
290 result may still be live, so it cannot be discarded explicitly. */
291 delete_insn (jump_insn
);
293 counter_reg
= XEXP (condition
, 0);
294 if (GET_CODE (counter_reg
) == PLUS
)
295 counter_reg
= XEXP (counter_reg
, 0);
296 mode
= GET_MODE (counter_reg
);
298 increment_count
= false;
299 switch (GET_CODE (condition
))
302 /* Currently only NE tests against zero and one are supported. */
303 noloop
= XEXP (condition
, 1);
304 if (noloop
!= const0_rtx
)
306 gcc_assert (noloop
== const1_rtx
);
307 increment_count
= true;
312 /* Currently only GE tests against zero are supported. */
313 gcc_assert (XEXP (condition
, 1) == const0_rtx
);
315 noloop
= constm1_rtx
;
317 /* The iteration count does not need incrementing for a GE test. */
318 increment_count
= false;
320 /* Determine if the iteration counter will be non-negative.
321 Note that the maximum value loaded is iterations_max - 1. */
323 <= ((unsigned HOST_WIDEST_INT
) 1
324 << (GET_MODE_BITSIZE (mode
) - 1)))
328 /* Abort if an invalid doloop pattern has been generated. */
334 count
= simplify_gen_binary (PLUS
, mode
, count
, const1_rtx
);
336 /* Insert initialization of the count register into the loop header. */
338 tmp
= force_operand (count
, counter_reg
);
339 convert_move (counter_reg
, tmp
, 1);
340 sequence
= get_insns ();
342 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
344 if (desc
->noloop_assumptions
)
346 rtx ass
= copy_rtx (desc
->noloop_assumptions
);
347 basic_block preheader
= loop_preheader_edge (loop
)->src
;
349 = loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
350 basic_block new_preheader
351 = loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
356 /* Expand the condition testing the assumptions and if it does not pass,
357 reset the count register to 0. */
358 add_test (XEXP (ass
, 0), preheader
, set_zero
);
359 single_succ_edge (preheader
)->flags
&= ~EDGE_FALLTHRU
;
360 cnt
= single_succ_edge (preheader
)->count
;
361 single_succ_edge (preheader
)->probability
= 0;
362 single_succ_edge (preheader
)->count
= 0;
363 irr
= single_succ_edge (preheader
)->flags
& EDGE_IRREDUCIBLE_LOOP
;
364 te
= make_edge (preheader
, new_preheader
, EDGE_FALLTHRU
| irr
);
365 te
->probability
= REG_BR_PROB_BASE
;
367 set_immediate_dominator (CDI_DOMINATORS
, new_preheader
, preheader
);
370 set_zero
->frequency
= 0;
372 for (ass
= XEXP (ass
, 1); ass
; ass
= XEXP (ass
, 1))
374 bb
= loop_split_edge_with (te
, NULL_RTX
);
375 te
= single_succ_edge (bb
);
376 add_test (XEXP (ass
, 0), bb
, set_zero
);
377 make_edge (bb
, set_zero
, irr
);
381 convert_move (counter_reg
, noloop
, 0);
382 sequence
= get_insns ();
384 emit_insn_after (sequence
, BB_END (set_zero
));
387 /* Some targets (eg, C4x) need to initialize special looping
389 #ifdef HAVE_doloop_begin
392 unsigned level
= get_loop_level (loop
) + 1;
393 init
= gen_doloop_begin (counter_reg
,
394 desc
->const_iter
? desc
->niter_expr
: const0_rtx
,
401 sequence
= get_insns ();
403 emit_insn_after (sequence
, BB_END (loop_preheader_edge (loop
)->src
));
408 /* Insert the new low-overhead looping insn. */
409 emit_jump_insn_after (doloop_seq
, BB_END (loop_end
));
410 jump_insn
= BB_END (loop_end
);
411 jump_label
= block_label (desc
->in_edge
->dest
);
412 JUMP_LABEL (jump_insn
) = jump_label
;
413 LABEL_NUSES (jump_label
)++;
415 /* Ensure the right fallthru edge is marked, for case we have reversed
417 desc
->in_edge
->flags
&= ~EDGE_FALLTHRU
;
418 desc
->out_edge
->flags
|= EDGE_FALLTHRU
;
420 /* Add a REG_NONNEG note if the actual or estimated maximum number
421 of iterations is non-negative. */
424 REG_NOTES (jump_insn
)
425 = gen_rtx_EXPR_LIST (REG_NONNEG
, NULL_RTX
, REG_NOTES (jump_insn
));
429 /* Process loop described by LOOP validating that the loop is suitable for
430 conversion to use a low overhead looping instruction, replacing the jump
431 insn where suitable. Returns true if the loop was successfully
435 doloop_optimize (struct loop
*loop
)
437 enum machine_mode mode
;
438 rtx doloop_seq
, doloop_pat
, doloop_reg
;
439 rtx iterations
, count
;
443 unsigned level
, est_niter
;
444 struct niter_desc
*desc
;
445 unsigned word_mode_size
;
446 unsigned HOST_WIDE_INT word_mode_max
;
449 fprintf (dump_file
, "Doloop: Processing loop %d.\n", loop
->num
);
451 iv_analysis_loop_init (loop
);
453 /* Find the simple exit of a LOOP. */
454 desc
= get_simple_loop_desc (loop
);
456 /* Check that loop is a candidate for a low-overhead looping insn. */
457 if (!doloop_valid_p (loop
, desc
))
461 "Doloop: The loop is not suitable.\n");
467 if (desc
->const_iter
)
468 est_niter
= desc
->niter
;
469 /* If the estimate on number of iterations is reliable (comes from profile
470 feedback), use it. Do not use it normally, since the expected number
471 of iterations of an unrolled loop is 2. */
472 if (loop
->header
->count
)
473 est_niter
= expected_loop_iterations (loop
);
479 "Doloop: Too few iterations (%u) to be profitable.\n",
484 count
= copy_rtx (desc
->niter_expr
);
485 iterations
= desc
->const_iter
? desc
->niter_expr
: const0_rtx
;
486 iterations_max
= GEN_INT (desc
->niter_max
);
487 level
= get_loop_level (loop
) + 1;
489 /* Generate looping insn. If the pattern FAILs then give up trying
490 to modify the loop since there is some aspect the back-end does
492 start_label
= block_label (desc
->in_edge
->dest
);
493 doloop_reg
= gen_reg_rtx (mode
);
494 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
495 GEN_INT (level
), start_label
);
497 word_mode_size
= GET_MODE_BITSIZE (word_mode
);
499 = ((unsigned HOST_WIDE_INT
) 1 << (word_mode_size
- 1) << 1) - 1;
502 /* Before trying mode different from the one in that # of iterations is
503 computed, we must be sure that the number of iterations fits into
505 && (word_mode_size
>= GET_MODE_BITSIZE (mode
)
506 || desc
->niter_max
<= word_mode_max
))
508 if (word_mode_size
> GET_MODE_BITSIZE (mode
))
510 count
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
512 iterations
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
514 iterations_max
= simplify_gen_unary (ZERO_EXTEND
, word_mode
,
515 iterations_max
, mode
);
519 count
= lowpart_subreg (word_mode
, count
, mode
);
520 iterations
= lowpart_subreg (word_mode
, iterations
, mode
);
521 iterations_max
= lowpart_subreg (word_mode
, iterations_max
, mode
);
523 PUT_MODE (doloop_reg
, word_mode
);
524 doloop_seq
= gen_doloop_end (doloop_reg
, iterations
, iterations_max
,
525 GEN_INT (level
), start_label
);
531 "Doloop: Target unwilling to use doloop pattern!\n");
535 /* If multiple instructions were created, the last must be the
536 jump instruction. Also, a raw define_insn may yield a plain
538 doloop_pat
= doloop_seq
;
539 if (INSN_P (doloop_pat
))
541 while (NEXT_INSN (doloop_pat
) != NULL_RTX
)
542 doloop_pat
= NEXT_INSN (doloop_pat
);
543 if (JUMP_P (doloop_pat
))
544 doloop_pat
= PATTERN (doloop_pat
);
546 doloop_pat
= NULL_RTX
;
550 || ! (condition
= doloop_condition_get (doloop_pat
)))
553 fprintf (dump_file
, "Doloop: Unrecognizable doloop pattern!\n");
557 doloop_modify (loop
, desc
, doloop_seq
, condition
, count
);
561 /* This is the main entry point. Process all LOOPS using doloop_optimize. */
564 doloop_optimize_loops (struct loops
*loops
)
569 for (i
= 1; i
< loops
->num
; i
++)
571 loop
= loops
->parray
[i
];
575 doloop_optimize (loop
);
580 #ifdef ENABLE_CHECKING
581 verify_dominators (CDI_DOMINATORS
);
582 verify_loop_structure (loops
);
585 #endif /* HAVE_doloop_end */