diagnostic-show-locus.c: remove unused field from class colorizer
[official-gcc.git] / gcc / loop-doloop.c
blob49861b8e3625a36cc318778fe23cff2598d58ce6
1 /* Perform doloop optimizations
2 Copyright (C) 2004-2017 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 e2->count = e2->src->count.apply_probability (prob);
397 (*e)->probability = prob.invert ();
398 (*e)->count = (*e)->count.apply_probability (prob);
399 update_br_prob_note (e2->src);
400 return true;
403 /* Modify the loop to use the low-overhead looping insn where LOOP
404 describes the loop, DESC describes the number of iterations of the
405 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
406 end of the loop. CONDITION is the condition separated from the
407 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
409 static void
410 doloop_modify (struct loop *loop, struct niter_desc *desc,
411 rtx_insn *doloop_seq, rtx condition, rtx count)
413 rtx counter_reg;
414 rtx tmp, noloop = NULL_RTX;
415 rtx_insn *sequence;
416 rtx_insn *jump_insn;
417 rtx_code_label *jump_label;
418 int nonneg = 0;
419 bool increment_count;
420 basic_block loop_end = desc->out_edge->src;
421 machine_mode mode;
422 widest_int iterations;
424 jump_insn = BB_END (loop_end);
426 if (dump_file)
428 fprintf (dump_file, "Doloop: Inserting doloop pattern (");
429 if (desc->const_iter)
430 fprintf (dump_file, "%" PRId64, desc->niter);
431 else
432 fputs ("runtime", dump_file);
433 fputs (" iterations).\n", dump_file);
436 /* Discard original jump to continue loop. The original compare
437 result may still be live, so it cannot be discarded explicitly. */
438 delete_insn (jump_insn);
440 counter_reg = XEXP (condition, 0);
441 if (GET_CODE (counter_reg) == PLUS)
442 counter_reg = XEXP (counter_reg, 0);
443 mode = GET_MODE (counter_reg);
445 increment_count = false;
446 switch (GET_CODE (condition))
448 case NE:
449 /* Currently only NE tests against zero and one are supported. */
450 noloop = XEXP (condition, 1);
451 if (noloop != const0_rtx)
453 gcc_assert (noloop == const1_rtx);
454 increment_count = true;
456 break;
458 case GE:
459 /* Currently only GE tests against zero are supported. */
460 gcc_assert (XEXP (condition, 1) == const0_rtx);
462 noloop = constm1_rtx;
464 /* The iteration count does not need incrementing for a GE test. */
465 increment_count = false;
467 /* Determine if the iteration counter will be non-negative.
468 Note that the maximum value loaded is iterations_max - 1. */
469 if (get_max_loop_iterations (loop, &iterations)
470 && wi::leu_p (iterations,
471 wi::set_bit_in_zero <widest_int>
472 (GET_MODE_PRECISION (mode) - 1)))
473 nonneg = 1;
474 break;
476 /* Abort if an invalid doloop pattern has been generated. */
477 default:
478 gcc_unreachable ();
481 if (increment_count)
482 count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
484 /* Insert initialization of the count register into the loop header. */
485 start_sequence ();
486 /* count has been already copied through copy_rtx. */
487 reset_used_flags (count);
488 set_used_flags (condition);
489 tmp = force_operand (count, counter_reg);
490 convert_move (counter_reg, tmp, 1);
491 sequence = get_insns ();
492 unshare_all_rtl_in_chain (sequence);
493 end_sequence ();
494 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
496 if (desc->noloop_assumptions)
498 rtx ass = copy_rtx (desc->noloop_assumptions);
499 basic_block preheader = loop_preheader_edge (loop)->src;
500 basic_block set_zero = split_edge (loop_preheader_edge (loop));
501 basic_block new_preheader = split_edge (loop_preheader_edge (loop));
502 edge te;
504 /* Expand the condition testing the assumptions and if it does not pass,
505 reset the count register to 0. */
506 redirect_edge_and_branch_force (single_succ_edge (preheader), new_preheader);
507 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
509 set_zero->count = profile_count::uninitialized ();
510 set_zero->frequency = 0;
512 te = single_succ_edge (preheader);
513 for (; ass; ass = XEXP (ass, 1))
514 if (!add_test (XEXP (ass, 0), &te, set_zero))
515 break;
517 if (ass)
519 /* We reached a condition that is always true. This is very hard to
520 reproduce (such a loop does not roll, and thus it would most
521 likely get optimized out by some of the preceding optimizations).
522 In fact, I do not have any testcase for it. However, it would
523 also be very hard to show that it is impossible, so we must
524 handle this case. */
525 set_zero->count = preheader->count;
526 set_zero->frequency = preheader->frequency;
529 if (EDGE_COUNT (set_zero->preds) == 0)
531 /* All the conditions were simplified to false, remove the
532 unreachable set_zero block. */
533 delete_basic_block (set_zero);
535 else
537 /* Reset the counter to zero in the set_zero block. */
538 start_sequence ();
539 convert_move (counter_reg, noloop, 0);
540 sequence = get_insns ();
541 end_sequence ();
542 emit_insn_after (sequence, BB_END (set_zero));
544 set_immediate_dominator (CDI_DOMINATORS, set_zero,
545 recompute_dominator (CDI_DOMINATORS,
546 set_zero));
549 set_immediate_dominator (CDI_DOMINATORS, new_preheader,
550 recompute_dominator (CDI_DOMINATORS,
551 new_preheader));
554 /* Some targets (eg, C4x) need to initialize special looping
555 registers. */
556 if (targetm.have_doloop_begin ())
557 if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq))
558 emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src));
560 /* Insert the new low-overhead looping insn. */
561 emit_jump_insn_after (doloop_seq, BB_END (loop_end));
562 jump_insn = BB_END (loop_end);
563 jump_label = block_label (desc->in_edge->dest);
564 JUMP_LABEL (jump_insn) = jump_label;
565 LABEL_NUSES (jump_label)++;
567 /* Ensure the right fallthru edge is marked, for case we have reversed
568 the condition. */
569 desc->in_edge->flags &= ~EDGE_FALLTHRU;
570 desc->out_edge->flags |= EDGE_FALLTHRU;
572 /* Add a REG_NONNEG note if the actual or estimated maximum number
573 of iterations is non-negative. */
574 if (nonneg)
575 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
577 /* Update the REG_BR_PROB note. */
578 if (desc->in_edge->probability.initialized_p ())
579 add_reg_br_prob_note (jump_insn, desc->in_edge->probability);
582 /* Called through note_stores. */
584 static void
585 record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
587 bitmap mod = (bitmap)data;
588 if (REG_P (x))
590 unsigned int regno = REGNO (x);
591 if (HARD_REGISTER_P (x))
593 unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
595 bitmap_set_bit (mod, regno);
596 while (++regno < end_regno);
598 else
599 bitmap_set_bit (mod, regno);
603 /* Process loop described by LOOP validating that the loop is suitable for
604 conversion to use a low overhead looping instruction, replacing the jump
605 insn where suitable. Returns true if the loop was successfully
606 modified. */
608 static bool
609 doloop_optimize (struct loop *loop)
611 machine_mode mode;
612 rtx doloop_reg;
613 rtx count;
614 widest_int iterations, iterations_max;
615 rtx_code_label *start_label;
616 rtx condition;
617 unsigned level;
618 HOST_WIDE_INT est_niter;
619 int max_cost;
620 struct niter_desc *desc;
621 unsigned word_mode_size;
622 unsigned HOST_WIDE_INT word_mode_max;
623 int entered_at_top;
625 if (dump_file)
626 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
628 iv_analysis_loop_init (loop);
630 /* Find the simple exit of a LOOP. */
631 desc = get_simple_loop_desc (loop);
633 /* Check that loop is a candidate for a low-overhead looping insn. */
634 if (!doloop_valid_p (loop, desc))
636 if (dump_file)
637 fprintf (dump_file,
638 "Doloop: The loop is not suitable.\n");
639 return false;
641 mode = desc->mode;
643 est_niter = get_estimated_loop_iterations_int (loop);
644 if (est_niter == -1)
645 est_niter = get_likely_max_loop_iterations_int (loop);
647 if (est_niter >= 0 && est_niter < 3)
649 if (dump_file)
650 fprintf (dump_file,
651 "Doloop: Too few iterations (%u) to be profitable.\n",
652 (unsigned int)est_niter);
653 return false;
656 max_cost
657 = COSTS_N_INSNS (PARAM_VALUE (PARAM_MAX_ITERATIONS_COMPUTATION_COST));
658 if (set_src_cost (desc->niter_expr, mode, optimize_loop_for_speed_p (loop))
659 > max_cost)
661 if (dump_file)
662 fprintf (dump_file,
663 "Doloop: number of iterations too costly to compute.\n");
664 return false;
667 if (desc->const_iter)
668 iterations = widest_int::from (rtx_mode_t (desc->niter_expr, mode),
669 UNSIGNED);
670 else
671 iterations = 0;
672 if (!get_max_loop_iterations (loop, &iterations_max))
673 iterations_max = 0;
674 level = get_loop_level (loop) + 1;
675 entered_at_top = (loop->latch == desc->in_edge->dest
676 && contains_no_active_insn_p (loop->latch));
677 if (!targetm.can_use_doloop_p (iterations, iterations_max, level,
678 entered_at_top))
680 if (dump_file)
681 fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n");
682 return false;
685 /* Generate looping insn. If the pattern FAILs then give up trying
686 to modify the loop since there is some aspect the back-end does
687 not like. */
688 count = copy_rtx (desc->niter_expr);
689 start_label = block_label (desc->in_edge->dest);
690 doloop_reg = gen_reg_rtx (mode);
691 rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
693 word_mode_size = GET_MODE_PRECISION (word_mode);
694 word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1;
695 if (! doloop_seq
696 && mode != word_mode
697 /* Before trying mode different from the one in that # of iterations is
698 computed, we must be sure that the number of iterations fits into
699 the new mode. */
700 && (word_mode_size >= GET_MODE_PRECISION (mode)
701 || wi::leu_p (iterations_max, word_mode_max)))
703 if (word_mode_size > GET_MODE_PRECISION (mode))
704 count = simplify_gen_unary (ZERO_EXTEND, word_mode, count, mode);
705 else
706 count = lowpart_subreg (word_mode, count, mode);
707 PUT_MODE (doloop_reg, word_mode);
708 doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
710 if (! doloop_seq)
712 if (dump_file)
713 fprintf (dump_file,
714 "Doloop: Target unwilling to use doloop pattern!\n");
715 return false;
718 /* If multiple instructions were created, the last must be the
719 jump instruction. */
720 rtx_insn *doloop_insn = doloop_seq;
721 while (NEXT_INSN (doloop_insn) != NULL_RTX)
722 doloop_insn = NEXT_INSN (doloop_insn);
723 if (!JUMP_P (doloop_insn)
724 || !(condition = doloop_condition_get (doloop_insn)))
726 if (dump_file)
727 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
728 return false;
731 /* Ensure that the new sequence doesn't clobber a register that
732 is live at the end of the block. */
734 bitmap modified = BITMAP_ALLOC (NULL);
736 for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i))
737 note_stores (PATTERN (i), record_reg_sets, modified);
739 basic_block loop_end = desc->out_edge->src;
740 bool fail = bitmap_intersect_p (df_get_live_out (loop_end), modified);
741 BITMAP_FREE (modified);
743 if (fail)
745 if (dump_file)
746 fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n");
747 return false;
751 doloop_modify (loop, desc, doloop_seq, condition, count);
752 return true;
755 /* This is the main entry point. Process all loops using doloop_optimize. */
757 void
758 doloop_optimize_loops (void)
760 struct loop *loop;
762 if (optimize == 1)
764 df_live_add_problem ();
765 df_live_set_all_dirty ();
768 FOR_EACH_LOOP (loop, 0)
770 doloop_optimize (loop);
773 if (optimize == 1)
774 df_remove_problem (df_live);
776 iv_analysis_done ();
778 checking_verify_loop_structure ();