i386: Use const reference of struct ix86_frame to avoid copy
[official-gcc.git] / gcc / loop-doloop.c
blob4e8ce9f52785e8ae53eede6614b843434ee4fbb5
1 /* Perform doloop optimizations
2 Copyright (C) 2004-2018 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
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 COPYING3. If not see
19 <http://www.gnu.org/licenses/>. */
21 #include "config.h"
22 #include "system.h"
23 #include "coretypes.h"
24 #include "backend.h"
25 #include "target.h"
26 #include "rtl.h"
27 #include "tree.h"
28 #include "cfghooks.h"
29 #include "memmodel.h"
30 #include "emit-rtl.h"
31 #include "dojump.h"
32 #include "expr.h"
33 #include "cfgloop.h"
34 #include "cfgrtl.h"
35 #include "params.h"
36 #include "dumpfile.h"
37 #include "loop-unroll.h"
38 #include "regs.h"
39 #include "df.h"
41 /* This module is used to modify loops with a determinable number of
42 iterations to use special low-overhead looping instructions.
44 It first validates whether the loop is well behaved and has a
45 determinable number of iterations (either at compile or run-time).
46 It then modifies the loop to use a low-overhead looping pattern as
47 follows:
49 1. A pseudo register is allocated as the loop iteration counter.
51 2. The number of loop iterations is calculated and is stored
52 in the loop counter.
54 3. At the end of the loop, the jump insn is replaced by the
55 doloop_end pattern. The compare must remain because it might be
56 used elsewhere. If the loop-variable or condition register are
57 used elsewhere, they will be eliminated by flow.
59 4. An optional doloop_begin pattern is inserted at the top of the
60 loop.
62 TODO The optimization should only performed when either the biv used for exit
63 condition is unused at all except for the exit test, or if we do not have to
64 change its value, since otherwise we have to add a new induction variable,
65 which usually will not pay up (unless the cost of the doloop pattern is
66 somehow extremely lower than the cost of compare & jump, or unless the bct
67 register cannot be used for anything else but doloop -- ??? detect these
68 cases). */
70 /* Return the loop termination condition for PATTERN or zero
71 if it is not a decrement and branch jump insn. */
73 rtx
74 doloop_condition_get (rtx_insn *doloop_pat)
76 rtx cmp;
77 rtx inc;
78 rtx reg;
79 rtx inc_src;
80 rtx condition;
81 rtx pattern;
82 rtx cc_reg = NULL_RTX;
83 rtx reg_orig = NULL_RTX;
85 /* The canonical doloop pattern we expect has one of the following
86 forms:
88 1) (parallel [(set (pc) (if_then_else (condition)
89 (label_ref (label))
90 (pc)))
91 (set (reg) (plus (reg) (const_int -1)))
92 (additional clobbers and uses)])
94 The branch must be the first entry of the parallel (also required
95 by jump.c), and the second entry of the parallel must be a set of
96 the loop counter register. Some targets (IA-64) wrap the set of
97 the loop counter in an if_then_else too.
99 2) (set (reg) (plus (reg) (const_int -1))
100 (set (pc) (if_then_else (reg != 0)
101 (label_ref (label))
102 (pc))).
104 Some targets (ARM) do the comparison before the branch, as in the
105 following form:
107 3) (parallel [(set (cc) (compare ((plus (reg) (const_int -1), 0)))
108 (set (reg) (plus (reg) (const_int -1)))])
109 (set (pc) (if_then_else (cc == NE)
110 (label_ref (label))
111 (pc))) */
113 pattern = PATTERN (doloop_pat);
115 if (GET_CODE (pattern) != PARALLEL)
117 rtx cond;
118 rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
119 rtx cmp_arg1, cmp_arg2;
120 rtx cmp_orig;
122 /* In case the pattern is not PARALLEL we expect two forms
123 of doloop which are cases 2) and 3) above: in case 2) the
124 decrement immediately precedes the branch, while in case 3)
125 the compare and decrement instructions immediately precede
126 the branch. */
128 if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
129 return 0;
131 cmp = pattern;
132 if (GET_CODE (PATTERN (prev_insn)) == PARALLEL)
134 /* The third case: the compare and decrement instructions
135 immediately precede the branch. */
136 cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0);
137 if (GET_CODE (cmp_orig) != SET)
138 return 0;
139 if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE)
140 return 0;
141 cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0);
142 cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1);
143 if (cmp_arg2 != const0_rtx
144 || GET_CODE (cmp_arg1) != PLUS)
145 return 0;
146 reg_orig = XEXP (cmp_arg1, 0);
147 if (XEXP (cmp_arg1, 1) != GEN_INT (-1)
148 || !REG_P (reg_orig))
149 return 0;
150 cc_reg = SET_DEST (cmp_orig);
152 inc = XVECEXP (PATTERN (prev_insn), 0, 1);
154 else
155 inc = PATTERN (prev_insn);
156 if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE)
158 /* We expect the condition to be of the form (reg != 0) */
159 cond = XEXP (SET_SRC (cmp), 0);
160 if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx)
161 return 0;
164 else
166 cmp = XVECEXP (pattern, 0, 0);
167 inc = XVECEXP (pattern, 0, 1);
170 /* Check for (set (reg) (something)). */
171 if (GET_CODE (inc) != SET)
172 return 0;
173 reg = SET_DEST (inc);
174 if (! REG_P (reg))
175 return 0;
177 /* Check if something = (plus (reg) (const_int -1)).
178 On IA-64, this decrement is wrapped in an if_then_else. */
179 inc_src = SET_SRC (inc);
180 if (GET_CODE (inc_src) == IF_THEN_ELSE)
181 inc_src = XEXP (inc_src, 1);
182 if (GET_CODE (inc_src) != PLUS
183 || XEXP (inc_src, 0) != reg
184 || XEXP (inc_src, 1) != constm1_rtx)
185 return 0;
187 /* Check for (set (pc) (if_then_else (condition)
188 (label_ref (label))
189 (pc))). */
190 if (GET_CODE (cmp) != SET
191 || SET_DEST (cmp) != pc_rtx
192 || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
193 || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
194 || XEXP (SET_SRC (cmp), 2) != pc_rtx)
195 return 0;
197 /* Extract loop termination condition. */
198 condition = XEXP (SET_SRC (cmp), 0);
200 /* We expect a GE or NE comparison with 0 or 1. */
201 if ((GET_CODE (condition) != GE
202 && GET_CODE (condition) != NE)
203 || (XEXP (condition, 1) != const0_rtx
204 && XEXP (condition, 1) != const1_rtx))
205 return 0;
207 if ((XEXP (condition, 0) == reg)
208 /* For the third case: */
209 || ((cc_reg != NULL_RTX)
210 && (XEXP (condition, 0) == cc_reg)
211 && (reg_orig == reg))
212 || (GET_CODE (XEXP (condition, 0)) == PLUS
213 && XEXP (XEXP (condition, 0), 0) == reg))
215 if (GET_CODE (pattern) != PARALLEL)
216 /* For the second form we expect:
218 (set (reg) (plus (reg) (const_int -1))
219 (set (pc) (if_then_else (reg != 0)
220 (label_ref (label))
221 (pc))).
223 is equivalent to the following:
225 (parallel [(set (pc) (if_then_else (reg != 1)
226 (label_ref (label))
227 (pc)))
228 (set (reg) (plus (reg) (const_int -1)))
229 (additional clobbers and uses)])
231 For the third form we expect:
233 (parallel [(set (cc) (compare ((plus (reg) (const_int -1)), 0))
234 (set (reg) (plus (reg) (const_int -1)))])
235 (set (pc) (if_then_else (cc == NE)
236 (label_ref (label))
237 (pc)))
239 which is equivalent to the following:
241 (parallel [(set (cc) (compare (reg, 1))
242 (set (reg) (plus (reg) (const_int -1)))
243 (set (pc) (if_then_else (NE == cc)
244 (label_ref (label))
245 (pc))))])
247 So we return the second form instead for the two cases.
250 condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx);
252 return condition;
255 /* ??? If a machine uses a funny comparison, we could return a
256 canonicalized form here. */
258 return 0;
261 /* Return nonzero if the loop specified by LOOP is suitable for
262 the use of special low-overhead looping instructions. DESC
263 describes the number of iterations of the loop. */
265 static bool
266 doloop_valid_p (struct loop *loop, struct niter_desc *desc)
268 basic_block *body = get_loop_body (loop), bb;
269 rtx_insn *insn;
270 unsigned i;
271 bool result = true;
273 /* Check for loops that may not terminate under special conditions. */
274 if (!desc->simple_p
275 || desc->assumptions
276 || desc->infinite)
278 /* There are some cases that would require a special attention.
279 For example if the comparison is LEU and the comparison value
280 is UINT_MAX then the loop will not terminate. Similarly, if the
281 comparison code is GEU and the comparison value is 0, the
282 loop will not terminate.
284 If the absolute increment is not 1, the loop can be infinite
285 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
287 ??? We could compute these conditions at run-time and have a
288 additional jump around the loop to ensure an infinite loop.
289 However, it is very unlikely that this is the intended
290 behavior of the loop and checking for these rare boundary
291 conditions would pessimize all other code.
293 If the loop is executed only a few times an extra check to
294 restart the loop could use up most of the benefits of using a
295 count register loop. Note however, that normally, this
296 restart branch would never execute, so it could be predicted
297 well by the CPU. We should generate the pessimistic code by
298 default, and have an option, e.g. -funsafe-loops that would
299 enable count-register loops in this case. */
300 if (dump_file)
301 fprintf (dump_file, "Doloop: Possible infinite iteration case.\n");
302 result = false;
303 goto cleanup;
306 for (i = 0; i < loop->num_nodes; i++)
308 bb = body[i];
310 for (insn = BB_HEAD (bb);
311 insn != NEXT_INSN (BB_END (bb));
312 insn = NEXT_INSN (insn))
314 /* Different targets have different necessities for low-overhead
315 looping. Call the back end for each instruction within the loop
316 to let it decide whether the insn prohibits a low-overhead loop.
317 It will then return the cause for it to emit to the dump file. */
318 const char * invalid = targetm.invalid_within_doloop (insn);
319 if (invalid)
321 if (dump_file)
322 fprintf (dump_file, "Doloop: %s\n", invalid);
323 result = false;
324 goto cleanup;
328 result = true;
330 cleanup:
331 free (body);
333 return result;
336 /* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru
337 edge. If the condition is always false, do not do anything. If it is always
338 true, redirect E to DEST and return false. In all other cases, true is
339 returned. */
341 static bool
342 add_test (rtx cond, edge *e, basic_block dest)
344 rtx_insn *seq, *jump;
345 rtx_code_label *label;
346 machine_mode mode;
347 rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
348 enum rtx_code code = GET_CODE (cond);
349 basic_block bb;
350 /* The jump is supposed to handle an unlikely special case. */
351 profile_probability prob = profile_probability::guessed_never ();
353 mode = GET_MODE (XEXP (cond, 0));
354 if (mode == VOIDmode)
355 mode = GET_MODE (XEXP (cond, 1));
357 start_sequence ();
358 op0 = force_operand (op0, NULL_RTX);
359 op1 = force_operand (op1, NULL_RTX);
360 label = block_label (dest);
361 do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label,
362 prob);
364 jump = get_last_insn ();
365 if (!jump || !JUMP_P (jump))
367 /* The condition is always false and the jump was optimized out. */
368 end_sequence ();
369 return true;
372 seq = get_insns ();
373 unshare_all_rtl_in_chain (seq);
374 end_sequence ();
376 /* There always is at least the jump insn in the sequence. */
377 gcc_assert (seq != NULL_RTX);
379 bb = split_edge_and_insert (*e, seq);
380 *e = single_succ_edge (bb);
382 if (any_uncondjump_p (jump))
384 /* The condition is always true. */
385 delete_insn (jump);
386 redirect_edge_and_branch_force (*e, dest);
387 return false;
390 JUMP_LABEL (jump) = label;
392 LABEL_NUSES (label)++;
394 edge e2 = make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
395 e2->probability = prob;
396 (*e)->probability = prob.invert ();
397 update_br_prob_note (e2->src);
398 return true;
401 /* Modify the loop to use the low-overhead looping insn where LOOP
402 describes the loop, DESC describes the number of iterations of the
403 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
404 end of the loop. CONDITION is the condition separated from the
405 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
407 static void
408 doloop_modify (struct loop *loop, struct niter_desc *desc,
409 rtx_insn *doloop_seq, rtx condition, rtx count)
411 rtx counter_reg;
412 rtx tmp, noloop = NULL_RTX;
413 rtx_insn *sequence;
414 rtx_insn *jump_insn;
415 rtx_code_label *jump_label;
416 int nonneg = 0;
417 bool increment_count;
418 basic_block loop_end = desc->out_edge->src;
419 scalar_int_mode mode;
420 widest_int iterations;
422 jump_insn = BB_END (loop_end);
424 if (dump_file)
426 fprintf (dump_file, "Doloop: Inserting doloop pattern (");
427 if (desc->const_iter)
428 fprintf (dump_file, "%" PRId64, desc->niter);
429 else
430 fputs ("runtime", dump_file);
431 fputs (" iterations).\n", dump_file);
434 /* Discard original jump to continue loop. The original compare
435 result may still be live, so it cannot be discarded explicitly. */
436 delete_insn (jump_insn);
438 counter_reg = XEXP (condition, 0);
439 if (GET_CODE (counter_reg) == PLUS)
440 counter_reg = XEXP (counter_reg, 0);
441 /* These patterns must operate on integer counters. */
442 mode = as_a <scalar_int_mode> (GET_MODE (counter_reg));
444 increment_count = false;
445 switch (GET_CODE (condition))
447 case NE:
448 /* Currently only NE tests against zero and one are supported. */
449 noloop = XEXP (condition, 1);
450 if (noloop != const0_rtx)
452 gcc_assert (noloop == const1_rtx);
453 increment_count = true;
455 break;
457 case GE:
458 /* Currently only GE tests against zero are supported. */
459 gcc_assert (XEXP (condition, 1) == const0_rtx);
461 noloop = constm1_rtx;
463 /* The iteration count does not need incrementing for a GE test. */
464 increment_count = false;
466 /* Determine if the iteration counter will be non-negative.
467 Note that the maximum value loaded is iterations_max - 1. */
468 if (get_max_loop_iterations (loop, &iterations)
469 && wi::leu_p (iterations,
470 wi::set_bit_in_zero <widest_int>
471 (GET_MODE_PRECISION (mode) - 1)))
472 nonneg = 1;
473 break;
475 /* Abort if an invalid doloop pattern has been generated. */
476 default:
477 gcc_unreachable ();
480 if (increment_count)
481 count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
483 /* Insert initialization of the count register into the loop header. */
484 start_sequence ();
485 /* count has been already copied through copy_rtx. */
486 reset_used_flags (count);
487 set_used_flags (condition);
488 tmp = force_operand (count, counter_reg);
489 convert_move (counter_reg, tmp, 1);
490 sequence = get_insns ();
491 unshare_all_rtl_in_chain (sequence);
492 end_sequence ();
493 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
495 if (desc->noloop_assumptions)
497 rtx ass = copy_rtx (desc->noloop_assumptions);
498 basic_block preheader = loop_preheader_edge (loop)->src;
499 basic_block set_zero = split_edge (loop_preheader_edge (loop));
500 basic_block new_preheader = split_edge (loop_preheader_edge (loop));
501 edge te;
503 /* Expand the condition testing the assumptions and if it does not pass,
504 reset the count register to 0. */
505 redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader);
506 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
508 set_zero->count = profile_count::uninitialized ();
510 te = single_succ_edge (preheader);
511 for (; ass; ass = XEXP (ass, 1))
512 if (!add_test (XEXP (ass, 0), &te, set_zero))
513 break;
515 if (ass)
517 /* We reached a condition that is always true. This is very hard to
518 reproduce (such a loop does not roll, and thus it would most
519 likely get optimized out by some of the preceding optimizations).
520 In fact, I do not have any testcase for it. However, it would
521 also be very hard to show that it is impossible, so we must
522 handle this case. */
523 set_zero->count = preheader->count;
526 if (EDGE_COUNT (set_zero->preds) == 0)
528 /* All the conditions were simplified to false, remove the
529 unreachable set_zero block. */
530 delete_basic_block (set_zero);
532 else
534 /* Reset the counter to zero in the set_zero block. */
535 start_sequence ();
536 convert_move (counter_reg, noloop, 0);
537 sequence = get_insns ();
538 end_sequence ();
539 emit_insn_after (sequence, BB_END (set_zero));
541 set_immediate_dominator (CDI_DOMINATORS, set_zero,
542 recompute_dominator (CDI_DOMINATORS,
543 set_zero));
546 set_immediate_dominator (CDI_DOMINATORS, new_preheader,
547 recompute_dominator (CDI_DOMINATORS,
548 new_preheader));
551 /* Some targets (eg, C4x) need to initialize special looping
552 registers. */
553 if (targetm.have_doloop_begin ())
554 if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq))
555 emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src));
557 /* Insert the new low-overhead looping insn. */
558 emit_jump_insn_after (doloop_seq, BB_END (loop_end));
559 jump_insn = BB_END (loop_end);
560 jump_label = block_label (desc->in_edge->dest);
561 JUMP_LABEL (jump_insn) = jump_label;
562 LABEL_NUSES (jump_label)++;
564 /* Ensure the right fallthru edge is marked, for case we have reversed
565 the condition. */
566 desc->in_edge->flags &= ~EDGE_FALLTHRU;
567 desc->out_edge->flags |= EDGE_FALLTHRU;
569 /* Add a REG_NONNEG note if the actual or estimated maximum number
570 of iterations is non-negative. */
571 if (nonneg)
572 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
574 /* Update the REG_BR_PROB note. */
575 if (desc->in_edge->probability.initialized_p ())
576 add_reg_br_prob_note (jump_insn, desc->in_edge->probability);
579 /* Called through note_stores. */
581 static void
582 record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
584 bitmap mod = (bitmap)data;
585 if (REG_P (x))
587 unsigned int regno = REGNO (x);
588 if (HARD_REGISTER_P (x))
590 unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
592 bitmap_set_bit (mod, regno);
593 while (++regno < end_regno);
595 else
596 bitmap_set_bit (mod, regno);
600 /* Process loop described by LOOP validating that the loop is suitable for
601 conversion to use a low overhead looping instruction, replacing the jump
602 insn where suitable. Returns true if the loop was successfully
603 modified. */
605 static bool
606 doloop_optimize (struct loop *loop)
608 scalar_int_mode mode;
609 rtx doloop_reg;
610 rtx count;
611 widest_int iterations, iterations_max;
612 rtx_code_label *start_label;
613 rtx condition;
614 unsigned level;
615 HOST_WIDE_INT est_niter;
616 int max_cost;
617 struct niter_desc *desc;
618 unsigned word_mode_size;
619 unsigned HOST_WIDE_INT word_mode_max;
620 int entered_at_top;
622 if (dump_file)
623 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
625 iv_analysis_loop_init (loop);
627 /* Find the simple exit of a LOOP. */
628 desc = get_simple_loop_desc (loop);
630 /* Check that loop is a candidate for a low-overhead looping insn. */
631 if (!doloop_valid_p (loop, desc))
633 if (dump_file)
634 fprintf (dump_file,
635 "Doloop: The loop is not suitable.\n");
636 return false;
638 mode = desc->mode;
640 est_niter = get_estimated_loop_iterations_int (loop);
641 if (est_niter == -1)
642 est_niter = get_likely_max_loop_iterations_int (loop);
644 if (est_niter >= 0 && est_niter < 3)
646 if (dump_file)
647 fprintf (dump_file,
648 "Doloop: Too few iterations (%u) to be profitable.\n",
649 (unsigned int)est_niter);
650 return false;
653 max_cost
654 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
655 if (set_src_cost (desc->niter_expr, mode, optimize_loop_for_speed_p (loop))
656 > max_cost)
658 if (dump_file)
659 fprintf (dump_file,
660 "Doloop: number of iterations too costly to compute.\n");
661 return false;
664 if (desc->const_iter)
665 iterations = widest_int::from (rtx_mode_t (desc->niter_expr, mode),
666 UNSIGNED);
667 else
668 iterations = 0;
669 if (!get_max_loop_iterations (loop, &iterations_max))
670 iterations_max = 0;
671 level = get_loop_level (loop) + 1;
672 entered_at_top = (loop->latch == desc->in_edge->dest
673 && contains_no_active_insn_p (loop->latch));
674 if (!targetm.can_use_doloop_p (iterations, iterations_max, level,
675 entered_at_top))
677 if (dump_file)
678 fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n");
679 return false;
682 /* Generate looping insn. If the pattern FAILs then give up trying
683 to modify the loop since there is some aspect the back-end does
684 not like. */
685 count = copy_rtx (desc->niter_expr);
686 start_label = block_label (desc->in_edge->dest);
687 doloop_reg = gen_reg_rtx (mode);
688 rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
690 word_mode_size = GET_MODE_PRECISION (word_mode);
691 word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1;
692 if (! doloop_seq
693 && mode != word_mode
694 /* Before trying mode different from the one in that # of iterations is
695 computed, we must be sure that the number of iterations fits into
696 the new mode. */
697 && (word_mode_size >= GET_MODE_PRECISION (mode)
698 || wi::leu_p (iterations_max, word_mode_max)))
700 if (word_mode_size > GET_MODE_PRECISION (mode))
701 count = simplify_gen_unary (ZERO_EXTEND, word_mode, count, mode);
702 else
703 count = lowpart_subreg (word_mode, count, mode);
704 PUT_MODE (doloop_reg, word_mode);
705 doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
707 if (! doloop_seq)
709 if (dump_file)
710 fprintf (dump_file,
711 "Doloop: Target unwilling to use doloop pattern!\n");
712 return false;
715 /* If multiple instructions were created, the last must be the
716 jump instruction. */
717 rtx_insn *doloop_insn = doloop_seq;
718 while (NEXT_INSN (doloop_insn) != NULL_RTX)
719 doloop_insn = NEXT_INSN (doloop_insn);
720 if (!JUMP_P (doloop_insn)
721 || !(condition = doloop_condition_get (doloop_insn)))
723 if (dump_file)
724 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
725 return false;
728 /* Ensure that the new sequence doesn't clobber a register that
729 is live at the end of the block. */
731 bitmap modified = BITMAP_ALLOC (NULL);
733 for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i))
734 note_stores (PATTERN (i), record_reg_sets, modified);
736 basic_block loop_end = desc->out_edge->src;
737 bool fail = bitmap_intersect_p (df_get_live_out (loop_end), modified);
738 BITMAP_FREE (modified);
740 if (fail)
742 if (dump_file)
743 fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n");
744 return false;
748 doloop_modify (loop, desc, doloop_seq, condition, count);
749 return true;
752 /* This is the main entry point. Process all loops using doloop_optimize. */
754 void
755 doloop_optimize_loops (void)
757 struct loop *loop;
759 if (optimize == 1)
761 df_live_add_problem ();
762 df_live_set_all_dirty ();
765 FOR_EACH_LOOP (loop, 0)
767 doloop_optimize (loop);
770 if (optimize == 1)
771 df_remove_problem (df_live);
773 iv_analysis_done ();
775 checking_verify_loop_structure ();