2006-02-09 Kaz Kojima <kkojima@gcc.gnu.org>
[official-gcc.git] / gcc / loop-doloop.c
blob3fcb79d9dc1fe7f16fcf4e39b36c2c2f1a7a7b0b
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
10 version.
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
15 for more details.
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, 51 Franklin Street, Fifth Floor, Boston, MA
20 02110-1301, USA. */
22 #include "config.h"
23 #include "system.h"
24 #include "coretypes.h"
25 #include "tm.h"
26 #include "rtl.h"
27 #include "flags.h"
28 #include "expr.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "toplev.h"
32 #include "tm_p.h"
33 #include "cfgloop.h"
34 #include "output.h"
35 #include "params.h"
36 #include "target.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
44 follows:
46 1. A pseudo register is allocated as the loop iteration counter.
48 2. The number of loop iterations is calculated and is stored
49 in the loop counter.
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
57 loop.
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
65 cases). */
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. */
72 rtx
73 doloop_condition_get (rtx pattern)
75 rtx cmp;
76 rtx inc;
77 rtx reg;
78 rtx inc_src;
79 rtx condition;
81 /* The canonical doloop pattern we expect is:
83 (parallel [(set (pc) (if_then_else (condition)
84 (label_ref (label))
85 (pc)))
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
90 an if_then_else too.
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
95 register. */
97 if (GET_CODE (pattern) != PARALLEL)
98 return 0;
100 cmp = XVECEXP (pattern, 0, 0);
101 inc = XVECEXP (pattern, 0, 1);
103 /* Check for (set (reg) (something)). */
104 if (GET_CODE (inc) != SET)
105 return 0;
106 reg = SET_DEST (inc);
107 if (! REG_P (reg))
108 return 0;
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)
118 return 0;
120 /* Check for (set (pc) (if_then_else (condition)
121 (label_ref (label))
122 (pc))). */
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)
128 return 0;
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))
138 return 0;
140 if ((XEXP (condition, 0) == reg)
141 || (GET_CODE (XEXP (condition, 0)) == PLUS
142 && XEXP (XEXP (condition, 0), 0) == reg))
143 return condition;
145 /* ??? If a machine uses a funny comparison, we could return a
146 canonicalized form here. */
148 return 0;
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. */
155 static bool
156 doloop_valid_p (struct loop *loop, struct niter_desc *desc)
158 basic_block *body = get_loop_body (loop), bb;
159 rtx insn;
160 unsigned i;
161 bool result = true;
163 /* Check for loops that may not terminate under special conditions. */
164 if (!desc->simple_p
165 || desc->assumptions
166 || desc->infinite)
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. */
190 if (dump_file)
191 fprintf (dump_file, "Doloop: Possible infinite iteration case.\n");
192 result = false;
193 goto cleanup;
196 for (i = 0; i < loop->num_nodes; i++)
198 bb = body[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 prohibits a low-overhead loop.
207 It will then return the cause for it to emit to the dump file. */
208 const char * invalid = targetm.invalid_within_doloop (insn);
209 if (invalid)
211 if (dump_file)
212 fprintf (dump_file, "Doloop: %s\n", invalid);
213 result = false;
214 goto cleanup;
218 result = true;
220 cleanup:
221 free (body);
223 return result;
226 /* Adds test of COND jumping to DEST to the end of BB. */
228 static void
229 add_test (rtx cond, basic_block bb, basic_block dest)
231 rtx seq, jump, label;
232 enum machine_mode mode;
233 rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
234 enum rtx_code code = GET_CODE (cond);
236 mode = GET_MODE (XEXP (cond, 0));
237 if (mode == VOIDmode)
238 mode = GET_MODE (XEXP (cond, 1));
240 start_sequence ();
241 op0 = force_operand (op0, NULL_RTX);
242 op1 = force_operand (op1, NULL_RTX);
243 label = block_label (dest);
244 do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL_RTX, label);
246 jump = get_last_insn ();
247 /* It is possible for the jump to be optimized out. */
248 if (JUMP_P (jump))
250 JUMP_LABEL (jump) = label;
252 /* The jump is supposed to handle an unlikely special case. */
253 REG_NOTES (jump)
254 = gen_rtx_EXPR_LIST (REG_BR_PROB,
255 const0_rtx, REG_NOTES (jump));
257 LABEL_NUSES (label)++;
260 seq = get_insns ();
261 end_sequence ();
262 emit_insn_after (seq, BB_END (bb));
265 /* Modify the loop to use the low-overhead looping insn where LOOP
266 describes the loop, DESC describes the number of iterations of the
267 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
268 end of the loop. CONDITION is the condition separated from the
269 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
271 static void
272 doloop_modify (struct loop *loop, struct niter_desc *desc,
273 rtx doloop_seq, rtx condition, rtx count)
275 rtx counter_reg;
276 rtx tmp, noloop = NULL_RTX;
277 rtx sequence;
278 rtx jump_insn;
279 rtx jump_label;
280 int nonneg = 0, irr;
281 bool increment_count;
282 basic_block loop_end = desc->out_edge->src;
283 enum machine_mode mode;
285 jump_insn = BB_END (loop_end);
287 if (dump_file)
289 fprintf (dump_file, "Doloop: Inserting doloop pattern (");
290 if (desc->const_iter)
291 fprintf (dump_file, HOST_WIDEST_INT_PRINT_DEC, desc->niter);
292 else
293 fputs ("runtime", dump_file);
294 fputs (" iterations).\n", dump_file);
297 /* Discard original jump to continue loop. The original compare
298 result may still be live, so it cannot be discarded explicitly. */
299 delete_insn (jump_insn);
301 counter_reg = XEXP (condition, 0);
302 if (GET_CODE (counter_reg) == PLUS)
303 counter_reg = XEXP (counter_reg, 0);
304 mode = GET_MODE (counter_reg);
306 increment_count = false;
307 switch (GET_CODE (condition))
309 case NE:
310 /* Currently only NE tests against zero and one are supported. */
311 noloop = XEXP (condition, 1);
312 if (noloop != const0_rtx)
314 gcc_assert (noloop == const1_rtx);
315 increment_count = true;
317 break;
319 case GE:
320 /* Currently only GE tests against zero are supported. */
321 gcc_assert (XEXP (condition, 1) == const0_rtx);
323 noloop = constm1_rtx;
325 /* The iteration count does not need incrementing for a GE test. */
326 increment_count = false;
328 /* Determine if the iteration counter will be non-negative.
329 Note that the maximum value loaded is iterations_max - 1. */
330 if (desc->niter_max
331 <= ((unsigned HOST_WIDEST_INT) 1
332 << (GET_MODE_BITSIZE (mode) - 1)))
333 nonneg = 1;
334 break;
336 /* Abort if an invalid doloop pattern has been generated. */
337 default:
338 gcc_unreachable ();
341 if (increment_count)
342 count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
344 /* Insert initialization of the count register into the loop header. */
345 start_sequence ();
346 tmp = force_operand (count, counter_reg);
347 convert_move (counter_reg, tmp, 1);
348 sequence = get_insns ();
349 end_sequence ();
350 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
352 if (desc->noloop_assumptions)
354 rtx ass = copy_rtx (desc->noloop_assumptions);
355 basic_block preheader = loop_preheader_edge (loop)->src;
356 basic_block set_zero
357 = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
358 basic_block new_preheader
359 = loop_split_edge_with (loop_preheader_edge (loop), NULL_RTX);
360 basic_block bb;
361 edge te;
362 gcov_type cnt;
364 /* Expand the condition testing the assumptions and if it does not pass,
365 reset the count register to 0. */
366 add_test (XEXP (ass, 0), preheader, set_zero);
367 single_succ_edge (preheader)->flags &= ~EDGE_FALLTHRU;
368 cnt = single_succ_edge (preheader)->count;
369 single_succ_edge (preheader)->probability = 0;
370 single_succ_edge (preheader)->count = 0;
371 irr = single_succ_edge (preheader)->flags & EDGE_IRREDUCIBLE_LOOP;
372 te = make_edge (preheader, new_preheader, EDGE_FALLTHRU | irr);
373 te->probability = REG_BR_PROB_BASE;
374 te->count = cnt;
375 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
377 set_zero->count = 0;
378 set_zero->frequency = 0;
380 for (ass = XEXP (ass, 1); ass; ass = XEXP (ass, 1))
382 bb = loop_split_edge_with (te, NULL_RTX);
383 te = single_succ_edge (bb);
384 add_test (XEXP (ass, 0), bb, set_zero);
385 make_edge (bb, set_zero, irr);
388 start_sequence ();
389 convert_move (counter_reg, noloop, 0);
390 sequence = get_insns ();
391 end_sequence ();
392 emit_insn_after (sequence, BB_END (set_zero));
395 /* Some targets (eg, C4x) need to initialize special looping
396 registers. */
397 #ifdef HAVE_doloop_begin
399 rtx init;
400 unsigned level = get_loop_level (loop) + 1;
401 init = gen_doloop_begin (counter_reg,
402 desc->const_iter ? desc->niter_expr : const0_rtx,
403 GEN_INT (desc->niter_max),
404 GEN_INT (level));
405 if (init)
407 start_sequence ();
408 emit_insn (init);
409 sequence = get_insns ();
410 end_sequence ();
411 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
414 #endif
416 /* Insert the new low-overhead looping insn. */
417 emit_jump_insn_after (doloop_seq, BB_END (loop_end));
418 jump_insn = BB_END (loop_end);
419 jump_label = block_label (desc->in_edge->dest);
420 JUMP_LABEL (jump_insn) = jump_label;
421 LABEL_NUSES (jump_label)++;
423 /* Ensure the right fallthru edge is marked, for case we have reversed
424 the condition. */
425 desc->in_edge->flags &= ~EDGE_FALLTHRU;
426 desc->out_edge->flags |= EDGE_FALLTHRU;
428 /* Add a REG_NONNEG note if the actual or estimated maximum number
429 of iterations is non-negative. */
430 if (nonneg)
432 REG_NOTES (jump_insn)
433 = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
437 /* Process loop described by LOOP validating that the loop is suitable for
438 conversion to use a low overhead looping instruction, replacing the jump
439 insn where suitable. Returns true if the loop was successfully
440 modified. */
442 static bool
443 doloop_optimize (struct loop *loop)
445 enum machine_mode mode;
446 rtx doloop_seq, doloop_pat, doloop_reg;
447 rtx iterations, count;
448 rtx iterations_max;
449 rtx start_label;
450 rtx condition;
451 unsigned level, est_niter;
452 struct niter_desc *desc;
453 unsigned word_mode_size;
454 unsigned HOST_WIDE_INT word_mode_max;
456 if (dump_file)
457 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
459 iv_analysis_loop_init (loop);
461 /* Find the simple exit of a LOOP. */
462 desc = get_simple_loop_desc (loop);
464 /* Check that loop is a candidate for a low-overhead looping insn. */
465 if (!doloop_valid_p (loop, desc))
467 if (dump_file)
468 fprintf (dump_file,
469 "Doloop: The loop is not suitable.\n");
470 return false;
472 mode = desc->mode;
474 est_niter = 3;
475 if (desc->const_iter)
476 est_niter = desc->niter;
477 /* If the estimate on number of iterations is reliable (comes from profile
478 feedback), use it. Do not use it normally, since the expected number
479 of iterations of an unrolled loop is 2. */
480 if (loop->header->count)
481 est_niter = expected_loop_iterations (loop);
483 if (est_niter < 3)
485 if (dump_file)
486 fprintf (dump_file,
487 "Doloop: Too few iterations (%u) to be profitable.\n",
488 est_niter);
489 return false;
492 count = copy_rtx (desc->niter_expr);
493 iterations = desc->const_iter ? desc->niter_expr : const0_rtx;
494 iterations_max = GEN_INT (desc->niter_max);
495 level = get_loop_level (loop) + 1;
497 /* Generate looping insn. If the pattern FAILs then give up trying
498 to modify the loop since there is some aspect the back-end does
499 not like. */
500 start_label = block_label (desc->in_edge->dest);
501 doloop_reg = gen_reg_rtx (mode);
502 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
503 GEN_INT (level), start_label);
505 word_mode_size = GET_MODE_BITSIZE (word_mode);
506 word_mode_max
507 = ((unsigned HOST_WIDE_INT) 1 << (word_mode_size - 1) << 1) - 1;
508 if (! doloop_seq
509 && mode != word_mode
510 /* Before trying mode different from the one in that # of iterations is
511 computed, we must be sure that the number of iterations fits into
512 the new mode. */
513 && (word_mode_size >= GET_MODE_BITSIZE (mode)
514 || desc->niter_max <= word_mode_max))
516 if (word_mode_size > GET_MODE_BITSIZE (mode))
518 count = simplify_gen_unary (ZERO_EXTEND, word_mode,
519 count, mode);
520 iterations = simplify_gen_unary (ZERO_EXTEND, word_mode,
521 iterations, mode);
522 iterations_max = simplify_gen_unary (ZERO_EXTEND, word_mode,
523 iterations_max, mode);
525 else
527 count = lowpart_subreg (word_mode, count, mode);
528 iterations = lowpart_subreg (word_mode, iterations, mode);
529 iterations_max = lowpart_subreg (word_mode, iterations_max, mode);
531 PUT_MODE (doloop_reg, word_mode);
532 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
533 GEN_INT (level), start_label);
535 if (! doloop_seq)
537 if (dump_file)
538 fprintf (dump_file,
539 "Doloop: Target unwilling to use doloop pattern!\n");
540 return false;
543 /* If multiple instructions were created, the last must be the
544 jump instruction. Also, a raw define_insn may yield a plain
545 pattern. */
546 doloop_pat = doloop_seq;
547 if (INSN_P (doloop_pat))
549 while (NEXT_INSN (doloop_pat) != NULL_RTX)
550 doloop_pat = NEXT_INSN (doloop_pat);
551 if (JUMP_P (doloop_pat))
552 doloop_pat = PATTERN (doloop_pat);
553 else
554 doloop_pat = NULL_RTX;
557 if (! doloop_pat
558 || ! (condition = doloop_condition_get (doloop_pat)))
560 if (dump_file)
561 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
562 return false;
565 doloop_modify (loop, desc, doloop_seq, condition, count);
566 return true;
569 /* This is the main entry point. Process all LOOPS using doloop_optimize. */
571 void
572 doloop_optimize_loops (struct loops *loops)
574 unsigned i;
575 struct loop *loop;
577 for (i = 1; i < loops->num; i++)
579 loop = loops->parray[i];
580 if (!loop)
581 continue;
583 doloop_optimize (loop);
586 iv_analysis_done ();
588 #ifdef ENABLE_CHECKING
589 verify_dominators (CDI_DOMINATORS);
590 verify_loop_structure (loops);
591 #endif
593 #endif /* HAVE_doloop_end */