* config/alpha/alpha.c: Follow spelling conventions.
[official-gcc.git] / gcc / doloop.c
blobf3b302907bc35eb24d18414c55d2ee27489eab53
1 /* Perform doloop optimizations
2 Copyright (C) 1999, 2000, 2001, 2002 Free Software Foundation, Inc.
3 Contributed 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, 59 Temple Place - Suite 330, Boston, MA
20 02111-1307, USA. */
22 #include "config.h"
23 #include "system.h"
24 #include "rtl.h"
25 #include "flags.h"
26 #include "expr.h"
27 #include "loop.h"
28 #include "hard-reg-set.h"
29 #include "basic-block.h"
30 #include "toplev.h"
31 #include "tm_p.h"
34 /* This module is used to modify loops with a determinable number of
35 iterations to use special low-overhead looping instructions.
37 It first validates whether the loop is well behaved and has a
38 determinable number of iterations (either at compile or run-time).
39 It then modifies the loop to use a low-overhead looping pattern as
40 follows:
42 1. A pseudo register is allocated as the loop iteration counter.
44 2. The number of loop iterations is calculated and is stored
45 in the loop counter.
47 3. At the end of the loop, the jump insn is replaced by the
48 doloop_end pattern. The compare must remain because it might be
49 used elsewhere. If the loop-variable or condition register are
50 used elsewhere, they will be eliminated by flow.
52 4. An optional doloop_begin pattern is inserted at the top of the
53 loop.
57 #ifdef HAVE_doloop_end
59 static rtx doloop_condition_get
60 PARAMS ((rtx));
61 static unsigned HOST_WIDE_INT doloop_iterations_max
62 PARAMS ((const struct loop_info *, enum machine_mode, int));
63 static int doloop_valid_p
64 PARAMS ((const struct loop *, rtx));
65 static int doloop_modify
66 PARAMS ((const struct loop *, rtx, rtx, rtx, rtx, rtx));
67 static int doloop_modify_runtime
68 PARAMS ((const struct loop *, rtx, rtx, rtx, enum machine_mode, rtx));
71 /* Return the loop termination condition for PATTERN or zero
72 if it is not a decrement and branch jump insn. */
73 static rtx
74 doloop_condition_get (pattern)
75 rtx pattern;
77 rtx cmp;
78 rtx inc;
79 rtx reg;
80 rtx condition;
82 /* The canonical doloop pattern we expect is:
84 (parallel [(set (pc) (if_then_else (condition)
85 (label_ref (label))
86 (pc)))
87 (set (reg) (plus (reg) (const_int -1)))
88 (additional clobbers and uses)])
90 Some machines (IA-64) make the decrement conditional on
91 the condition as well, so we don't bother verifying the
92 actual decrement. In summary, the branch must be the
93 first entry of the parallel (also required by jump.c),
94 and the second entry of the parallel must be a set of
95 the loop counter 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 || ! REG_P (SET_DEST (inc)))
105 return 0;
107 /* Extract loop counter register. */
108 reg = SET_DEST (inc);
110 /* Check for (set (pc) (if_then_else (condition)
111 (label_ref (label))
112 (pc))). */
113 if (GET_CODE (cmp) != SET
114 || SET_DEST (cmp) != pc_rtx
115 || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
116 || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
117 || XEXP (SET_SRC (cmp), 2) != pc_rtx)
118 return 0;
120 /* Extract loop termination condition. */
121 condition = XEXP (SET_SRC (cmp), 0);
123 if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
124 || GET_CODE (XEXP (condition, 1)) != CONST_INT)
125 return 0;
127 if (XEXP (condition, 0) == reg)
128 return condition;
130 if (GET_CODE (XEXP (condition, 0)) == PLUS
131 && XEXP (XEXP (condition, 0), 0) == reg)
132 return condition;
134 /* ??? If a machine uses a funny comparison, we could return a
135 canonicalised form here. */
137 return 0;
141 /* Return an estimate of the maximum number of loop iterations for the
142 loop specified by LOOP or zero if the loop is not normal.
143 MODE is the mode of the iteration count and NONNEG is non-zero if
144 the iteration count has been proved to be non-negative. */
145 static unsigned HOST_WIDE_INT
146 doloop_iterations_max (loop_info, mode, nonneg)
147 const struct loop_info *loop_info;
148 enum machine_mode mode;
149 int nonneg;
151 unsigned HOST_WIDE_INT n_iterations_max;
152 enum rtx_code code;
153 rtx min_value;
154 rtx max_value;
155 HOST_WIDE_INT abs_inc;
156 int neg_inc;
158 neg_inc = 0;
159 abs_inc = INTVAL (loop_info->increment);
160 if (abs_inc < 0)
162 abs_inc = -abs_inc;
163 neg_inc = 1;
166 if (neg_inc)
168 code = swap_condition (loop_info->comparison_code);
169 min_value = loop_info->final_equiv_value;
170 max_value = loop_info->initial_equiv_value;
172 else
174 code = loop_info->comparison_code;
175 min_value = loop_info->initial_equiv_value;
176 max_value = loop_info->final_equiv_value;
179 /* Since the loop has a VTOP, we know that the initial test will be
180 true and thus the value of max_value should be greater than the
181 value of min_value. Thus the difference should always be positive
182 and the code must be LT, LE, LTU, LEU, or NE. Otherwise the loop is
183 not normal, e.g., `for (i = 0; i < 10; i--)'. */
184 switch (code)
186 case LTU:
187 case LEU:
189 unsigned HOST_WIDE_INT umax;
190 unsigned HOST_WIDE_INT umin;
192 if (GET_CODE (min_value) == CONST_INT)
193 umin = INTVAL (min_value);
194 else
195 umin = 0;
197 if (GET_CODE (max_value) == CONST_INT)
198 umax = INTVAL (max_value);
199 else
200 umax = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
202 n_iterations_max = umax - umin;
203 break;
206 case LT:
207 case LE:
209 HOST_WIDE_INT smax;
210 HOST_WIDE_INT smin;
212 if (GET_CODE (min_value) == CONST_INT)
213 smin = INTVAL (min_value);
214 else
215 smin = -((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1));
217 if (GET_CODE (max_value) == CONST_INT)
218 smax = INTVAL (max_value);
219 else
220 smax = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
222 n_iterations_max = smax - smin;
223 break;
226 case NE:
227 if (GET_CODE (min_value) == CONST_INT
228 && GET_CODE (max_value) == CONST_INT)
229 n_iterations_max = INTVAL (max_value) - INTVAL (min_value);
230 else
231 /* We need to conservatively assume that we might have the maximum
232 number of iterations without any additional knowledge. */
233 n_iterations_max = ((unsigned) 2 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
234 break;
236 default:
237 return 0;
240 n_iterations_max /= abs_inc;
242 /* If we know that the iteration count is non-negative then adjust
243 n_iterations_max if it is so large that it appears negative. */
244 if (nonneg
245 && n_iterations_max > ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)))
246 n_iterations_max = ((unsigned) 1 << (GET_MODE_BITSIZE (mode) - 1)) - 1;
248 return n_iterations_max;
252 /* Return non-zero if the loop specified by LOOP is suitable for
253 the use of special low-overhead looping instructions. */
254 static int
255 doloop_valid_p (loop, jump_insn)
256 const struct loop *loop;
257 rtx jump_insn;
259 const struct loop_info *loop_info = LOOP_INFO (loop);
261 /* The loop must have a conditional jump at the end. */
262 if (! any_condjump_p (jump_insn)
263 || ! onlyjump_p (jump_insn))
265 if (loop_dump_stream)
266 fprintf (loop_dump_stream,
267 "Doloop: Invalid jump at loop end.\n");
268 return 0;
271 /* Give up if a loop has been completely unrolled. */
272 if (loop_info->n_iterations == loop_info->unroll_number)
274 if (loop_dump_stream)
275 fprintf (loop_dump_stream,
276 "Doloop: Loop completely unrolled.\n");
277 return 0;
280 /* The loop must have a single exit target. A break or return
281 statement within a loop will generate multiple loop exits.
282 Another example of a loop that currently generates multiple exit
283 targets is for (i = 0; i < (foo ? 8 : 4); i++) { }. */
284 if (loop_info->has_multiple_exit_targets || loop->exit_count)
286 if (loop_dump_stream)
287 fprintf (loop_dump_stream,
288 "Doloop: Loop has multiple exit targets.\n");
289 return 0;
292 /* An indirect jump may jump out of the loop. */
293 if (loop_info->has_indirect_jump)
295 if (loop_dump_stream)
296 fprintf (loop_dump_stream,
297 "Doloop: Indirect jump in function.\n");
298 return 0;
301 /* A called function may clobber any special registers required for
302 low-overhead looping. */
303 if (loop_info->has_call)
305 if (loop_dump_stream)
306 fprintf (loop_dump_stream,
307 "Doloop: Function call in loop.\n");
308 return 0;
311 /* Some targets (eg, PPC) use the count register for branch on table
312 instructions. ??? This should be a target specific check. */
313 if (loop_info->has_tablejump)
315 if (loop_dump_stream)
316 fprintf (loop_dump_stream,
317 "Doloop: Computed branch in the loop.\n");
318 return 0;
321 if (! loop_info->increment)
323 if (loop_dump_stream)
324 fprintf (loop_dump_stream,
325 "Doloop: Could not determine iteration info.\n");
326 return 0;
329 if (GET_CODE (loop_info->increment) != CONST_INT)
331 if (loop_dump_stream)
332 fprintf (loop_dump_stream,
333 "Doloop: Increment not an integer constant.\n");
334 return 0;
337 /* There is no guarantee that a NE loop will terminate if the
338 absolute increment is not unity. ??? We could compute this
339 condition at run-time and have an additional jump around the loop
340 to ensure an infinite loop. */
341 if (loop_info->comparison_code == NE
342 && INTVAL (loop_info->increment) != -1
343 && INTVAL (loop_info->increment) != 1)
345 if (loop_dump_stream)
346 fprintf (loop_dump_stream,
347 "Doloop: NE loop with non-unity increment.\n");
348 return 0;
351 /* Check for loops that may not terminate under special conditions. */
352 if (! loop_info->n_iterations
353 && ((loop_info->comparison_code == LEU
354 && INTVAL (loop_info->increment) > 0)
355 || (loop_info->comparison_code == GEU
356 && INTVAL (loop_info->increment) < 0)
357 || (loop_info->comparison_code == LTU
358 && INTVAL (loop_info->increment) > 1)
359 || (loop_info->comparison_code == GTU
360 && INTVAL (loop_info->increment) < -1)))
362 /* If the comparison is LEU and the comparison value is UINT_MAX
363 then the loop will not terminate. Similarly, if the
364 comparison code is GEU and the comparison value is 0, the
365 loop will not terminate.
367 If the absolute increment is not 1, the loop can be infinite
368 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
370 Note that with LE and GE, the loop behavior is undefined
371 (C++ standard section 5 clause 5) if an overflow occurs, say
372 between INT_MAX and INT_MAX + 1. We thus don't have to worry
373 about these two cases.
375 ??? We could compute these conditions at run-time and have a
376 additional jump around the loop to ensure an infinite loop.
377 However, it is very unlikely that this is the intended
378 behavior of the loop and checking for these rare boundary
379 conditions would pessimize all other code.
381 If the loop is executed only a few times an extra check to
382 restart the loop could use up most of the benefits of using a
383 count register loop. Note however, that normally, this
384 restart branch would never execute, so it could be predicted
385 well by the CPU. We should generate the pessimistic code by
386 default, and have an option, e.g. -funsafe-loops that would
387 enable count-register loops in this case. */
388 if (loop_dump_stream)
389 fprintf (loop_dump_stream,
390 "Doloop: Possible infinite iteration case ignored.\n");
393 return 1;
397 /* Modify the loop to use the low-overhead looping insn where LOOP
398 describes the loop, ITERATIONS is an RTX containing the desired
399 number of loop iterations, ITERATIONS_MAX is a CONST_INT specifying
400 the maximum number of loop iterations, and DOLOOP_INSN is the
401 low-overhead looping insn to emit at the end of the loop. This
402 returns non-zero if it was successful. */
403 static int
404 doloop_modify (loop, iterations, iterations_max,
405 doloop_seq, start_label, condition)
406 const struct loop *loop;
407 rtx iterations;
408 rtx iterations_max;
409 rtx doloop_seq;
410 rtx start_label;
411 rtx condition;
413 rtx counter_reg;
414 rtx count;
415 rtx sequence;
416 rtx jump_insn;
417 int nonneg = 0;
418 int decrement_count;
420 jump_insn = prev_nonnote_insn (loop->end);
422 if (loop_dump_stream)
424 fprintf (loop_dump_stream, "Doloop: Inserting doloop pattern (");
425 if (GET_CODE (iterations) == CONST_INT)
426 fprintf (loop_dump_stream, HOST_WIDE_INT_PRINT_DEC,
427 INTVAL (iterations));
428 else
429 fputs ("runtime", loop_dump_stream);
430 fputs (" iterations).", loop_dump_stream);
433 /* Emit the label that will delimit the top of the loop.
434 This has to be done before the delete_insn call below, to prevent
435 delete_insn from deleting too much. */
436 emit_label_after (start_label, loop->top ? loop->top : loop->start);
437 LABEL_NUSES (start_label)++;
439 /* Discard original jump to continue loop. The original compare
440 result may still be live, so it cannot be discarded explicitly. */
441 delete_related_insns (jump_insn);
443 counter_reg = XEXP (condition, 0);
444 if (GET_CODE (counter_reg) == PLUS)
445 counter_reg = XEXP (counter_reg, 0);
447 start_sequence ();
449 count = iterations;
450 decrement_count = 0;
451 switch (GET_CODE (condition))
453 case NE:
454 /* Currently only NE tests against zero and one are supported. */
455 if (XEXP (condition, 1) == const0_rtx)
456 decrement_count = 1;
457 else if (XEXP (condition, 1) != const1_rtx)
458 abort ();
459 break;
461 case GE:
462 /* Currently only GE tests against zero are supported. */
463 if (XEXP (condition, 1) != const0_rtx)
464 abort ();
466 /* The iteration count needs decrementing for a GE test. */
467 decrement_count = 1;
469 /* Determine if the iteration counter will be non-negative.
470 Note that the maximum value loaded is iterations_max - 1. */
471 if ((unsigned HOST_WIDE_INT) INTVAL (iterations_max)
472 <= ((unsigned) 1 << (GET_MODE_BITSIZE (GET_MODE (counter_reg)) - 1)))
473 nonneg = 1;
474 break;
476 /* Abort if an invalid doloop pattern has been generated. */
477 default:
478 abort ();
481 if (decrement_count)
483 if (GET_CODE (count) == CONST_INT)
484 count = GEN_INT (INTVAL (count) - 1);
485 else
486 count = expand_simple_binop (GET_MODE (counter_reg), MINUS,
487 count, GEN_INT (1),
488 0, 0, OPTAB_LIB_WIDEN);
491 /* Insert initialization of the count register into the loop header. */
492 convert_move (counter_reg, count, 1);
493 sequence = get_insns ();
494 end_sequence ();
495 emit_insn_before (sequence, loop->start);
497 /* Some targets (eg, C4x) need to initialize special looping
498 registers. */
499 #ifdef HAVE_doloop_begin
501 rtx init;
503 init = gen_doloop_begin (counter_reg,
504 GET_CODE (iterations) == CONST_INT
505 ? iterations : const0_rtx, iterations_max,
506 GEN_INT (loop->level));
507 if (init)
509 start_sequence ();
510 emit_insn (init);
511 sequence = get_insns ();
512 end_sequence ();
513 emit_insn_after (sequence, loop->start);
516 #endif
518 /* Insert the new low-overhead looping insn. */
519 emit_jump_insn_before (doloop_seq, loop->end);
520 jump_insn = prev_nonnote_insn (loop->end);
521 JUMP_LABEL (jump_insn) = start_label;
523 /* Add a REG_NONNEG note if the actual or estimated maximum number
524 of iterations is non-negative. */
525 if (nonneg)
527 REG_NOTES (jump_insn)
528 = gen_rtx_EXPR_LIST (REG_NONNEG, NULL_RTX, REG_NOTES (jump_insn));
530 return 1;
534 /* Handle the more complex case, where the bounds are not known at
535 compile time. In this case we generate a run_time calculation of
536 the number of iterations. We rely on the existence of a run-time
537 guard to ensure that the loop executes at least once, i.e.,
538 initial_value obeys the loop comparison condition. If a guard is
539 not present, we emit one. The loop to modify is described by LOOP.
540 ITERATIONS_MAX is a CONST_INT specifying the estimated maximum
541 number of loop iterations. DOLOOP_INSN is the low-overhead looping
542 insn to insert. Returns non-zero if loop successfully modified. */
543 static int
544 doloop_modify_runtime (loop, iterations_max,
545 doloop_seq, start_label, mode, condition)
546 const struct loop *loop;
547 rtx iterations_max;
548 rtx doloop_seq;
549 rtx start_label;
550 enum machine_mode mode;
551 rtx condition;
553 const struct loop_info *loop_info = LOOP_INFO (loop);
554 HOST_WIDE_INT abs_inc;
555 HOST_WIDE_INT abs_loop_inc;
556 int neg_inc;
557 rtx diff;
558 rtx sequence;
559 rtx iterations;
560 rtx initial_value;
561 rtx final_value;
562 rtx increment;
563 int unsigned_p;
564 enum rtx_code comparison_code;
566 increment = loop_info->increment;
567 initial_value = loop_info->initial_value;
568 final_value = loop_info->final_value;
570 neg_inc = 0;
571 abs_inc = INTVAL (increment);
572 if (abs_inc < 0)
574 abs_inc = -abs_inc;
575 neg_inc = 1;
578 comparison_code = loop_info->comparison_code;
579 unsigned_p = (comparison_code == LTU
580 || comparison_code == LEU
581 || comparison_code == GTU
582 || comparison_code == GEU
583 || comparison_code == NE);
585 /* The number of iterations (prior to any loop unrolling) is given by:
587 n = (abs (final - initial) + abs_inc - 1) / abs_inc.
589 However, it is possible for the summation to overflow, and a
590 safer method is:
592 n = abs (final - initial) / abs_inc;
593 n += (abs (final - initial) % abs_inc) != 0;
595 But when abs_inc is a power of two, the summation won't overflow
596 except in cases where the loop never terminates. So we don't
597 need to use this more costly calculation.
599 If the loop has been unrolled, the full calculation is
601 t1 = abs_inc * unroll_number; increment per loop
602 n = abs (final - initial) / t1; full loops
603 n += (abs (final - initial) % t1) != 0; partial loop
605 However, in certain cases the unrolled loop will be preconditioned
606 by emitting copies of the loop body with conditional branches,
607 so that the unrolled loop is always a full loop and thus needs
608 no exit tests. In this case we don't want to add the partial
609 loop count. As above, when t1 is a power of two we don't need to
610 worry about overflow.
612 The division and modulo operations can be avoided by requiring
613 that the increment is a power of 2 (precondition_loop_p enforces
614 this requirement). Nevertheless, the RTX_COSTS should be checked
615 to see if a fast divmod is available. */
617 start_sequence ();
618 /* abs (final - initial) */
619 diff = expand_simple_binop (mode, MINUS,
620 copy_rtx (neg_inc ? initial_value : final_value),
621 copy_rtx (neg_inc ? final_value : initial_value),
622 NULL_RTX, unsigned_p, OPTAB_LIB_WIDEN);
624 /* Some code transformations can result in code akin to
626 tmp = i + 1;
628 goto scan_start;
629 top:
630 tmp = tmp + 1;
631 scan_start:
632 i = tmp;
633 if (i < n) goto top;
635 We'll have already detected this form of loop in scan_loop,
636 and set loop->top and loop->scan_start appropriately.
638 In this situation, we skip the increment the first time through
639 the loop, which results in an incorrect estimate of the number
640 of iterations. Adjust the difference to compensate. */
641 /* ??? Logically, it would seem this belongs in loop_iterations.
642 However, this causes regressions e.g. on x86 execute/20011008-3.c,
643 so I do not believe we've properly characterized the exact nature
644 of the problem. In the meantime, this fixes execute/20011126-2.c
645 on ia64 and some Ada front end miscompilation on ppc. */
647 if (loop->scan_start)
649 rtx iteration_var = loop_info->iteration_var;
650 struct loop_ivs *ivs = LOOP_IVS (loop);
651 struct iv_class *bl;
653 if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == BASIC_INDUCT)
654 bl = REG_IV_CLASS (ivs, REGNO (iteration_var));
655 else if (REG_IV_TYPE (ivs, REGNO (iteration_var)) == GENERAL_INDUCT)
657 struct induction *v = REG_IV_INFO (ivs, REGNO (iteration_var));
658 bl = REG_IV_CLASS (ivs, REGNO (v->src_reg));
660 else
661 /* Iteration var must be an induction variable to get here. */
662 abort ();
664 if (INSN_UID (bl->biv->insn) < max_uid_for_loop
665 && INSN_LUID (bl->biv->insn) < INSN_LUID (loop->scan_start))
667 if (loop_dump_stream)
668 fprintf (loop_dump_stream,
669 "Doloop: Basic induction var skips initial incr.\n");
671 diff = expand_simple_binop (mode, PLUS, diff, increment, diff,
672 unsigned_p, OPTAB_LIB_WIDEN);
676 abs_loop_inc = abs_inc * loop_info->unroll_number;
677 if (abs_loop_inc != 1)
679 int shift_count;
681 shift_count = exact_log2 (abs_loop_inc);
682 if (shift_count < 0)
683 abort ();
685 if (!loop_info->preconditioned)
686 diff = expand_simple_binop (GET_MODE (diff), PLUS,
687 diff, GEN_INT (abs_loop_inc - 1),
688 diff, 1, OPTAB_LIB_WIDEN);
690 /* (abs (final - initial) + abs_inc * unroll_number - 1)
691 / (abs_inc * unroll_number) */
692 diff = expand_simple_binop (GET_MODE (diff), LSHIFTRT,
693 diff, GEN_INT (shift_count),
694 diff, 1, OPTAB_LIB_WIDEN);
696 iterations = diff;
698 /* If there is a NOTE_INSN_LOOP_VTOP, we have a `for' or `while'
699 style loop, with a loop exit test at the start. Thus, we can
700 assume that the loop condition was true when the loop was
701 entered.
703 `do-while' loops require special treatment since the exit test is
704 not executed before the start of the loop. We need to determine
705 if the loop will terminate after the first pass and to limit the
706 iteration count to one if necessary. */
707 if (! loop->vtop)
709 if (loop_dump_stream)
710 fprintf (loop_dump_stream, "Doloop: Do-while loop.\n");
712 /* A `do-while' loop must iterate at least once. For code like
713 i = initial; do { ... } while (++i < final);
714 we will calculate a bogus iteration count if initial > final.
715 So detect this and set the iteration count to 1.
716 Note that if the loop has been unrolled, then the loop body
717 is guaranteed to execute at least once. Also, when the
718 comparison is NE, our calculated count will be OK. */
719 if (loop_info->unroll_number == 1 && comparison_code != NE)
721 rtx label;
723 /* Emit insns to test if the loop will immediately
724 terminate and to set the iteration count to 1 if true. */
725 label = gen_label_rtx();
726 emit_cmp_and_jump_insns (copy_rtx (initial_value),
727 copy_rtx (loop_info->comparison_value),
728 comparison_code, NULL_RTX, mode, 0,
729 label);
730 JUMP_LABEL (get_last_insn ()) = label;
731 LABEL_NUSES (label)++;
732 emit_move_insn (iterations, const1_rtx);
733 emit_label (label);
737 sequence = get_insns ();
738 end_sequence ();
739 emit_insn_before (sequence, loop->start);
741 return doloop_modify (loop, iterations, iterations_max, doloop_seq,
742 start_label, condition);
746 /* This is the main entry point. Process loop described by LOOP
747 validating that the loop is suitable for conversion to use a low
748 overhead looping instruction, replacing the jump insn where
749 suitable. We distinguish between loops with compile-time bounds
750 and those with run-time bounds. Information from LOOP is used to
751 compute the number of iterations and to determine whether the loop
752 is a candidate for this optimization. Returns non-zero if loop
753 successfully modified. */
755 doloop_optimize (loop)
756 const struct loop *loop;
758 struct loop_info *loop_info = LOOP_INFO (loop);
759 rtx initial_value;
760 rtx final_value;
761 rtx increment;
762 rtx jump_insn;
763 enum machine_mode mode;
764 unsigned HOST_WIDE_INT n_iterations;
765 unsigned HOST_WIDE_INT n_iterations_max;
766 rtx doloop_seq, doloop_pat, doloop_reg;
767 rtx iterations;
768 rtx iterations_max;
769 rtx start_label;
770 rtx condition;
772 if (loop_dump_stream)
773 fprintf (loop_dump_stream,
774 "Doloop: Processing loop %d, enclosed levels %d.\n",
775 loop->num, loop->level);
777 jump_insn = prev_nonnote_insn (loop->end);
779 /* Check that loop is a candidate for a low-overhead looping insn. */
780 if (! doloop_valid_p (loop, jump_insn))
781 return 0;
783 /* Determine if the loop can be safely, and profitably,
784 preconditioned. While we don't precondition the loop in a loop
785 unrolling sense, this test ensures that the loop is well behaved
786 and that the increment is a constant integer. */
787 if (! precondition_loop_p (loop, &initial_value, &final_value,
788 &increment, &mode))
790 if (loop_dump_stream)
791 fprintf (loop_dump_stream,
792 "Doloop: Cannot precondition loop.\n");
793 return 0;
796 /* Determine or estimate the maximum number of loop iterations. */
797 n_iterations = loop_info->n_iterations;
798 if (n_iterations)
800 /* This is the simple case where the initial and final loop
801 values are constants. */
802 n_iterations_max = n_iterations;
804 else
806 int nonneg = find_reg_note (jump_insn, REG_NONNEG, 0) != 0;
808 /* This is the harder case where the initial and final loop
809 values may not be constants. */
810 n_iterations_max = doloop_iterations_max (loop_info, mode, nonneg);
812 if (! n_iterations_max)
814 /* We have something like `for (i = 0; i < 10; i--)'. */
815 if (loop_dump_stream)
816 fprintf (loop_dump_stream,
817 "Doloop: Not normal loop.\n");
818 return 0;
822 /* Account for loop unrolling in the iteration count. This will
823 have no effect if loop_iterations could not determine the number
824 of iterations. */
825 n_iterations /= loop_info->unroll_number;
826 n_iterations_max /= loop_info->unroll_number;
828 if (n_iterations && n_iterations < 3)
830 if (loop_dump_stream)
831 fprintf (loop_dump_stream,
832 "Doloop: Too few iterations (%ld) to be profitable.\n",
833 (long int) n_iterations);
834 return 0;
837 iterations = GEN_INT (n_iterations);
838 iterations_max = GEN_INT (n_iterations_max);
840 /* Generate looping insn. If the pattern FAILs then give up trying
841 to modify the loop since there is some aspect the back-end does
842 not like. */
843 start_label = gen_label_rtx ();
844 doloop_reg = gen_reg_rtx (mode);
845 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
846 GEN_INT (loop->level), start_label);
847 if (! doloop_seq && mode != word_mode)
849 PUT_MODE (doloop_reg, word_mode);
850 doloop_seq = gen_doloop_end (doloop_reg, iterations, iterations_max,
851 GEN_INT (loop->level), start_label);
853 if (! doloop_seq)
855 if (loop_dump_stream)
856 fprintf (loop_dump_stream,
857 "Doloop: Target unwilling to use doloop pattern!\n");
858 return 0;
861 /* If multiple instructions were created, the last must be the
862 jump instruction. Also, a raw define_insn may yield a plain
863 pattern. */
864 doloop_pat = doloop_seq;
865 if (INSN_P (doloop_pat))
867 while (NEXT_INSN (doloop_pat) != NULL_RTX)
868 doloop_pat = NEXT_INSN (doloop_pat);
869 if (GET_CODE (doloop_pat) == JUMP_INSN)
870 doloop_pat = PATTERN (doloop_pat);
871 else
872 doloop_pat = NULL_RTX;
875 if (! doloop_pat
876 || ! (condition = doloop_condition_get (doloop_pat)))
878 if (loop_dump_stream)
879 fprintf (loop_dump_stream,
880 "Doloop: Unrecognizable doloop pattern!\n");
881 return 0;
884 if (n_iterations != 0)
885 /* Handle the simpler case, where we know the iteration count at
886 compile time. */
887 return doloop_modify (loop, iterations, iterations_max, doloop_seq,
888 start_label, condition);
889 else
890 /* Handle the harder case, where we must add additional runtime tests. */
891 return doloop_modify_runtime (loop, iterations_max, doloop_seq,
892 start_label, mode, condition);
895 #endif /* HAVE_doloop_end */