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)
4
5This file is part of GCC.
6
7GCC is free software; you can redistribute it and/or modify it under
8the terms of the GNU General Public License as published by the Free
9Software Foundation; either version 3, or (at your option) any later
10version.
11
12GCC is distributed in the hope that it will be useful, but WITHOUT ANY
13WARRANTY; without even the implied warranty of MERCHANTABILITY or
14FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
15for more details.
16
17You should have received a copy of the GNU General Public License
18along with GCC; see the file COPYING3. If not see
19<http://www.gnu.org/licenses/>. */
20
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"
40
41/* This module is used to modify loops with a determinable number of
42 iterations to use special low-overhead looping instructions.
43
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:
48
49 1. A pseudo register is allocated as the loop iteration counter.
50
51 2. The number of loop iterations is calculated and is stored
52 in the loop counter.
53
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.
58
59 4. An optional doloop_begin pattern is inserted at the top of the
60 loop.
61
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). */
69
70/* Return the loop termination condition for PATTERN or zero
71 if it is not a decrement and branch jump insn. */
72
73rtx
74doloop_condition_get (rtx_insn *doloop_pat)
75{
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;
84
85 /* The canonical doloop pattern we expect has one of the following
86 forms:
87
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)])
93
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.
98
99 2) (set (reg) (plus (reg) (const_int -1))
100 (set (pc) (if_then_else (reg != 0)
101 (label_ref (label))
102 (pc))).
103
104 Some targets (ARM) do the comparison before the branch, as in the
105 following form:
106
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))) */
112
113 pattern = PATTERN (doloop_pat);
114
115 if (GET_CODE (pattern) != PARALLEL)
116 {
117 rtx cond;
118 rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
119 rtx cmp_arg1, cmp_arg2;
120 rtx cmp_orig;
121
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. */
127
128 if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
129 return 0;
130
131 cmp = pattern;
132 if (GET_CODE (PATTERN (prev_insn)) == PARALLEL)
133 {
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);
151
152 inc = XVECEXP (PATTERN (prev_insn), 0, 1);
153 }
154 else
155 inc = PATTERN (prev_insn);
156 if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE)
157 {
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;
162 }
163 }
164 else
165 {
166 cmp = XVECEXP (pattern, 0, 0);
167 inc = XVECEXP (pattern, 0, 1);
168 }
169
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;
176
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;
186
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;
196
197 /* Extract loop termination condition. */
198 condition = XEXP (SET_SRC (cmp), 0);
199
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;
206
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))
214 {
215 if (GET_CODE (pattern) != PARALLEL)
216 /* For the second form we expect:
217
218 (set (reg) (plus (reg) (const_int -1))
219 (set (pc) (if_then_else (reg != 0)
220 (label_ref (label))
221 (pc))).
222
223 is equivalent to the following:
224
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)])
230
231 For the third form we expect:
232
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)))
238
239 which is equivalent to the following:
240
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))))])
246
247 So we return the second form instead for the two cases.
248
249 */
250 condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx);
251
252 return condition;
253 }
254
255 /* ??? If a machine uses a funny comparison, we could return a
256 canonicalized form here. */
257
258 return 0;
259}
260
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. */
264
265static bool
266doloop_valid_p (struct loop *loop, struct niter_desc *desc)
267{
268 basic_block *body = get_loop_body (loop), bb;
269 rtx_insn *insn;
270 unsigned i;
271 bool result = true;
272
273 /* Check for loops that may not terminate under special conditions. */
274 if (!desc->simple_p
275 || desc->assumptions
276 || desc->infinite)
277 {
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.
283
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)
286
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.
292
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;
304 }
305
306 for (i = 0; i < loop->num_nodes; i++)
307 {
308 bb = body[i];
309
310 for (insn = BB_HEAD (bb);
311 insn != NEXT_INSN (BB_END (bb));
312 insn = NEXT_INSN (insn))
313 {
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)
320 {
321 if (dump_file)
322 fprintf (dump_file, "Doloop: %s\n", invalid);
323 result = false;
324 goto cleanup;
325 }
326 }
327 }
328 result = true;
329
330cleanup:
331 free (body);
332
333 return result;
334}
335
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. */
340
341static bool
342add_test (rtx cond, edge *e, basic_block dest)
343{
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 ();
352
353 mode = GET_MODE (XEXP (cond, 0));
354 if (mode == VOIDmode)
355 mode = GET_MODE (XEXP (cond, 1));
356
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);
363
364 jump = get_last_insn ();
365 if (!jump || !JUMP_P (jump))
366 {
367 /* The condition is always false and the jump was optimized out. */
368 end_sequence ();
369 return true;
370 }
371
372 seq = get_insns ();
373 unshare_all_rtl_in_chain (seq);
374 end_sequence ();
375
376 /* There always is at least the jump insn in the sequence. */
377 gcc_assert (seq != NULL_RTX);
378
379 bb = split_edge_and_insert (*e, seq);
380 *e = single_succ_edge (bb);
381
382 if (any_uncondjump_p (jump))
383 {
384 /* The condition is always true. */
385 delete_insn (jump);
386 redirect_edge_and_branch_force (*e, dest);
387 return false;
388 }
389
390 JUMP_LABEL (jump) = label;
391
392 LABEL_NUSES (label)++;
393
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;
399}
400
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. */
406
407static void
408doloop_modify (struct loop *loop, struct niter_desc *desc,
409 rtx_insn *doloop_seq, rtx condition, rtx count)
410{
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;
421
422 jump_insn = BB_END (loop_end);
423
424 if (dump_file)
425 {
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);
432 }
433
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);
437
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));
443
444 increment_count = false;
445 switch (GET_CODE (condition))
446 {
447 case NE:
448 /* Currently only NE tests against zero and one are supported. */
449 noloop = XEXP (condition, 1);
450 if (noloop != const0_rtx)
451 {
452 gcc_assert (noloop == const1_rtx);
453 increment_count = true;
454 }
455 break;
456
457 case GE:
458 /* Currently only GE tests against zero are supported. */
459 gcc_assert (XEXP (condition, 1) == const0_rtx);
460
461 noloop = constm1_rtx;
462
463 /* The iteration count does not need incrementing for a GE test. */
464 increment_count = false;
465
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;
474
475 /* Abort if an invalid doloop pattern has been generated. */
476 default:
477 gcc_unreachable ();
478 }
479
480 if (increment_count)
481 count = simplify_gen_binary (PLUS, mode, count, const1_rtx);
482
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));
494
495 if (desc->noloop_assumptions)
496 {
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;
502
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);
507
508 set_zero->count = profile_count::uninitialized ();
509
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;
514
515 if (ass)
516 {
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;
524 }
525
526 if (EDGE_COUNT (set_zero->preds) == 0)
527 {
528 /* All the conditions were simplified to false, remove the
529 unreachable set_zero block. */
530 delete_basic_block (set_zero);
531 }
532 else
533 {
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));
540
541 set_immediate_dominator (CDI_DOMINATORS, set_zero,
542 recompute_dominator (CDI_DOMINATORS,
543 set_zero));
544 }
545
546 set_immediate_dominator (CDI_DOMINATORS, new_preheader,
547 recompute_dominator (CDI_DOMINATORS,
548 new_preheader));
549 }
550
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));
556
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)++;
563
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;
568
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);
573
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);
577}
578
579/* Called through note_stores. */
580
581static void
582record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
583{
584 bitmap mod = (bitmap)data;
585 if (REG_P (x))
586 {
587 unsigned int regno = REGNO (x);
588 if (HARD_REGISTER_P (x))
589 {
590 unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
591 do
592 bitmap_set_bit (mod, regno);
593 while (++regno < end_regno);
594 }
595 else
596 bitmap_set_bit (mod, regno);
597 }
598}
599
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. */
604
605static bool
606doloop_optimize (struct loop *loop)
607{
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;
621
622 if (dump_file)
623 fprintf (dump_file, "Doloop: Processing loop %d.\n", loop->num);
624
625 iv_analysis_loop_init (loop);
626
627 /* Find the simple exit of a LOOP. */
628 desc = get_simple_loop_desc (loop);
629
630 /* Check that loop is a candidate for a low-overhead looping insn. */
631 if (!doloop_valid_p (loop, desc))
632 {
633 if (dump_file)
634 fprintf (dump_file,
635 "Doloop: The loop is not suitable.\n");
636 return false;
637 }
638 mode = desc->mode;
639
640 est_niter = get_estimated_loop_iterations_int (loop);
641 if (est_niter == -1)
642 est_niter = get_likely_max_loop_iterations_int (loop);
643
644 if (est_niter >= 0 && est_niter < 3)
645 {
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;
651 }
652
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)
657 {
658 if (dump_file)
659 fprintf (dump_file,
660 "Doloop: number of iterations too costly to compute.\n");
661 return false;
662 }
663
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))
676 {
677 if (dump_file)
678 fprintf (dump_file, "Loop rejected by can_use_doloop_p.\n");
679 return false;
680 }
681
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);
689
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)))
699 {
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);
706 }
707 if (! doloop_seq)
708 {
709 if (dump_file)
710 fprintf (dump_file,
711 "Doloop: Target unwilling to use doloop pattern!\n");
712 return false;
713 }
714
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)))
722 {
723 if (dump_file)
724 fprintf (dump_file, "Doloop: Unrecognizable doloop pattern!\n");
725 return false;
726 }
727
728 /* Ensure that the new sequence doesn't clobber a register that
729 is live at the end of the block. */
730 {
731 bitmap modified = BITMAP_ALLOC (NULL);
732
733 for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (i))
734 note_stores (PATTERN (i), record_reg_sets, modified);
735
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);
739
740 if (fail)
741 {
742 if (dump_file)
743 fprintf (dump_file, "Doloop: doloop pattern clobbers live out\n");
744 return false;
745 }
746 }
747
748 doloop_modify (loop, desc, doloop_seq, condition, count);
749 return true;
750}
751
752/* This is the main entry point. Process all loops using doloop_optimize. */
753
754void
755doloop_optimize_loops (void)
756{
757 struct loop *loop;
758
759 if (optimize == 1)
760 {
761 df_live_add_problem ();
762 df_live_set_all_dirty ();
763 }
764
765 FOR_EACH_LOOP (loop, 0)
766 {
767 doloop_optimize (loop);
768 }
769
770 if (optimize == 1)
771 df_remove_problem (df_live);
772
773 iv_analysis_done ();
774
775 checking_verify_loop_structure ();
776}
777