1/* Perform doloop optimizations
2 Copyright (C) 2004-2023 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 "dumpfile.h"
36#include "loop-unroll.h"
37#include "regs.h"
38#include "df.h"
39
40/* This module is used to modify loops with a determinable number of
41 iterations to use special low-overhead looping instructions.
42
43 It first validates whether the loop is well behaved and has a
44 determinable number of iterations (either at compile or run-time).
45 It then modifies the loop to use a low-overhead looping pattern as
46 follows:
47
48 1. A pseudo register is allocated as the loop iteration counter.
49
50 2. The number of loop iterations is calculated and is stored
51 in the loop counter.
52
53 3. At the end of the loop, the jump insn is replaced by the
54 doloop_end pattern. The compare must remain because it might be
55 used elsewhere. If the loop-variable or condition register are
56 used elsewhere, they will be eliminated by flow.
57
58 4. An optional doloop_begin pattern is inserted at the top of the
59 loop.
60
61 TODO The optimization should only performed when either the biv used for exit
62 condition is unused at all except for the exit test, or if we do not have to
63 change its value, since otherwise we have to add a new induction variable,
64 which usually will not pay up (unless the cost of the doloop pattern is
65 somehow extremely lower than the cost of compare & jump, or unless the bct
66 register cannot be used for anything else but doloop -- ??? detect these
67 cases). */
68
69/* Return the loop termination condition for PATTERN or zero
70 if it is not a decrement and branch jump insn. */
71
72rtx
73doloop_condition_get (rtx_insn *doloop_pat)
74{
75 rtx cmp;
76 rtx inc;
77 rtx reg;
78 rtx inc_src;
79 rtx condition;
80 rtx pattern;
81 rtx cc_reg = NULL_RTX;
82 rtx reg_orig = NULL_RTX;
83
84 /* The canonical doloop pattern we expect has one of the following
85 forms:
86
87 1) (parallel [(set (pc) (if_then_else (condition)
88 (label_ref (label))
89 (pc)))
90 (set (reg) (plus (reg) (const_int -1)))
91 (additional clobbers and uses)])
92
93 The branch must be the first entry of the parallel (also required
94 by jump.cc), and the second entry of the parallel must be a set of
95 the loop counter register. Some targets (IA-64) wrap the set of
96 the loop counter in an if_then_else too.
97
98 2) (set (reg) (plus (reg) (const_int -1))
99 (set (pc) (if_then_else (reg != 0)
100 (label_ref (label))
101 (pc))).
102
103 Some targets (ARM) do the comparison before the branch, as in the
104 following form:
105
106 3) (parallel [(set (cc) (compare ((plus (reg) (const_int -1), 0)))
107 (set (reg) (plus (reg) (const_int -1)))])
108 (set (pc) (if_then_else (cc == NE)
109 (label_ref (label))
110 (pc))) */
111
112 pattern = PATTERN (insn: doloop_pat);
113
114 if (GET_CODE (pattern) != PARALLEL)
115 {
116 rtx cond;
117 rtx_insn *prev_insn = prev_nondebug_insn (doloop_pat);
118 rtx cmp_arg1, cmp_arg2;
119 rtx cmp_orig;
120
121 /* In case the pattern is not PARALLEL we expect two forms
122 of doloop which are cases 2) and 3) above: in case 2) the
123 decrement immediately precedes the branch, while in case 3)
124 the compare and decrement instructions immediately precede
125 the branch. */
126
127 if (prev_insn == NULL_RTX || !INSN_P (prev_insn))
128 return 0;
129
130 cmp = pattern;
131 if (GET_CODE (PATTERN (prev_insn)) == PARALLEL)
132 {
133 /* The third case: the compare and decrement instructions
134 immediately precede the branch. */
135 cmp_orig = XVECEXP (PATTERN (prev_insn), 0, 0);
136 if (GET_CODE (cmp_orig) != SET)
137 return 0;
138 if (GET_CODE (SET_SRC (cmp_orig)) != COMPARE)
139 return 0;
140 cmp_arg1 = XEXP (SET_SRC (cmp_orig), 0);
141 cmp_arg2 = XEXP (SET_SRC (cmp_orig), 1);
142 if (cmp_arg2 != const0_rtx
143 || GET_CODE (cmp_arg1) != PLUS)
144 return 0;
145 reg_orig = XEXP (cmp_arg1, 0);
146 if (XEXP (cmp_arg1, 1) != GEN_INT (-1)
147 || !REG_P (reg_orig))
148 return 0;
149 cc_reg = SET_DEST (cmp_orig);
150
151 inc = XVECEXP (PATTERN (prev_insn), 0, 1);
152 }
153 else
154 inc = PATTERN (insn: prev_insn);
155 if (GET_CODE (cmp) == SET && GET_CODE (SET_SRC (cmp)) == IF_THEN_ELSE)
156 {
157 /* We expect the condition to be of the form (reg != 0) */
158 cond = XEXP (SET_SRC (cmp), 0);
159 if (GET_CODE (cond) != NE || XEXP (cond, 1) != const0_rtx)
160 return 0;
161 }
162 }
163 else
164 {
165 cmp = XVECEXP (pattern, 0, 0);
166 inc = XVECEXP (pattern, 0, 1);
167 }
168
169 /* Check for (set (reg) (something)). */
170 if (GET_CODE (inc) != SET)
171 return 0;
172 reg = SET_DEST (inc);
173 if (! REG_P (reg))
174 return 0;
175
176 /* Check if something = (plus (reg) (const_int -1)).
177 On IA-64, this decrement is wrapped in an if_then_else. */
178 inc_src = SET_SRC (inc);
179 if (GET_CODE (inc_src) == IF_THEN_ELSE)
180 inc_src = XEXP (inc_src, 1);
181 if (GET_CODE (inc_src) != PLUS
182 || XEXP (inc_src, 0) != reg
183 || XEXP (inc_src, 1) != constm1_rtx)
184 return 0;
185
186 /* Check for (set (pc) (if_then_else (condition)
187 (label_ref (label))
188 (pc))). */
189 if (GET_CODE (cmp) != SET
190 || SET_DEST (cmp) != pc_rtx
191 || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
192 || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
193 || XEXP (SET_SRC (cmp), 2) != pc_rtx)
194 return 0;
195
196 /* Extract loop termination condition. */
197 condition = XEXP (SET_SRC (cmp), 0);
198
199 /* We expect a GE or NE comparison with 0 or 1. */
200 if ((GET_CODE (condition) != GE
201 && GET_CODE (condition) != NE)
202 || (XEXP (condition, 1) != const0_rtx
203 && XEXP (condition, 1) != const1_rtx))
204 return 0;
205
206 if ((XEXP (condition, 0) == reg)
207 /* For the third case: */
208 || ((cc_reg != NULL_RTX)
209 && (XEXP (condition, 0) == cc_reg)
210 && (reg_orig == reg))
211 || (GET_CODE (XEXP (condition, 0)) == PLUS
212 && XEXP (XEXP (condition, 0), 0) == reg))
213 {
214 if (GET_CODE (pattern) != PARALLEL)
215 /* For the second form we expect:
216
217 (set (reg) (plus (reg) (const_int -1))
218 (set (pc) (if_then_else (reg != 0)
219 (label_ref (label))
220 (pc))).
221
222 is equivalent to the following:
223
224 (parallel [(set (pc) (if_then_else (reg != 1)
225 (label_ref (label))
226 (pc)))
227 (set (reg) (plus (reg) (const_int -1)))
228 (additional clobbers and uses)])
229
230 For the third form we expect:
231
232 (parallel [(set (cc) (compare ((plus (reg) (const_int -1)), 0))
233 (set (reg) (plus (reg) (const_int -1)))])
234 (set (pc) (if_then_else (cc == NE)
235 (label_ref (label))
236 (pc)))
237
238 which is equivalent to the following:
239
240 (parallel [(set (cc) (compare (reg, 1))
241 (set (reg) (plus (reg) (const_int -1)))
242 (set (pc) (if_then_else (NE == cc)
243 (label_ref (label))
244 (pc))))])
245
246 So we return the second form instead for the two cases.
247
248 */
249 condition = gen_rtx_fmt_ee (NE, VOIDmode, inc_src, const1_rtx);
250
251 return condition;
252 }
253
254 /* ??? If a machine uses a funny comparison, we could return a
255 canonicalized form here. */
256
257 return 0;
258}
259
260/* Return nonzero if the loop specified by LOOP is suitable for
261 the use of special low-overhead looping instructions. DESC
262 describes the number of iterations of the loop. */
263
264static bool
265doloop_valid_p (class loop *loop, class niter_desc *desc)
266{
267 basic_block *body = get_loop_body (loop), bb;
268 rtx_insn *insn;
269 unsigned i;
270 bool result = true;
271
272 /* Check for loops that may not terminate under special conditions. */
273 if (!desc->simple_p
274 || desc->assumptions
275 || desc->infinite)
276 {
277 /* There are some cases that would require a special attention.
278 For example if the comparison is LEU and the comparison value
279 is UINT_MAX then the loop will not terminate. Similarly, if the
280 comparison code is GEU and the comparison value is 0, the
281 loop will not terminate.
282
283 If the absolute increment is not 1, the loop can be infinite
284 even with LTU/GTU, e.g. for (i = 3; i > 0; i -= 2)
285
286 ??? We could compute these conditions at run-time and have a
287 additional jump around the loop to ensure an infinite loop.
288 However, it is very unlikely that this is the intended
289 behavior of the loop and checking for these rare boundary
290 conditions would pessimize all other code.
291
292 If the loop is executed only a few times an extra check to
293 restart the loop could use up most of the benefits of using a
294 count register loop. Note however, that normally, this
295 restart branch would never execute, so it could be predicted
296 well by the CPU. We should generate the pessimistic code by
297 default, and have an option, e.g. -funsafe-loops that would
298 enable count-register loops in this case. */
299 if (dump_file)
300 fprintf (stream: dump_file, format: "Doloop: Possible infinite iteration case.\n");
301 result = false;
302 goto cleanup;
303 }
304
305 for (i = 0; i < loop->num_nodes; i++)
306 {
307 bb = body[i];
308
309 for (insn = BB_HEAD (bb);
310 insn != NEXT_INSN (BB_END (bb));
311 insn = NEXT_INSN (insn))
312 {
313 /* Different targets have different necessities for low-overhead
314 looping. Call the back end for each instruction within the loop
315 to let it decide whether the insn prohibits a low-overhead loop.
316 It will then return the cause for it to emit to the dump file. */
317 const char * invalid = targetm.invalid_within_doloop (insn);
318 if (invalid)
319 {
320 if (dump_file)
321 fprintf (stream: dump_file, format: "Doloop: %s\n", invalid);
322 result = false;
323 goto cleanup;
324 }
325 }
326 }
327 result = true;
328
329cleanup:
330 free (ptr: body);
331
332 return result;
333}
334
335/* Adds test of COND jumping to DEST on edge *E and set *E to the new fallthru
336 edge. If the condition is always false, do not do anything. If it is always
337 true, redirect E to DEST and return false. In all other cases, true is
338 returned. */
339
340static bool
341add_test (rtx cond, edge *e, basic_block dest)
342{
343 rtx_insn *seq, *jump;
344 rtx_code_label *label;
345 machine_mode mode;
346 rtx op0 = XEXP (cond, 0), op1 = XEXP (cond, 1);
347 enum rtx_code code = GET_CODE (cond);
348 basic_block bb;
349 /* The jump is supposed to handle an unlikely special case. */
350 profile_probability prob = profile_probability::guessed_never ();
351
352 mode = GET_MODE (XEXP (cond, 0));
353 if (mode == VOIDmode)
354 mode = GET_MODE (XEXP (cond, 1));
355
356 start_sequence ();
357 op0 = force_operand (op0, NULL_RTX);
358 op1 = force_operand (op1, NULL_RTX);
359 label = block_label (dest);
360 do_compare_rtx_and_jump (op0, op1, code, 0, mode, NULL_RTX, NULL, label,
361 prob);
362
363 jump = get_last_insn ();
364 if (!jump || !JUMP_P (jump))
365 {
366 /* The condition is always false and the jump was optimized out. */
367 end_sequence ();
368 return true;
369 }
370
371 seq = get_insns ();
372 unshare_all_rtl_in_chain (seq);
373 end_sequence ();
374
375 /* There always is at least the jump insn in the sequence. */
376 gcc_assert (seq != NULL_RTX);
377
378 bb = split_edge_and_insert (*e, seq);
379 *e = single_succ_edge (bb);
380
381 if (any_uncondjump_p (jump) && onlyjump_p (jump))
382 {
383 /* The condition is always true. */
384 delete_insn (jump);
385 redirect_edge_and_branch_force (*e, dest);
386 return false;
387 }
388
389 JUMP_LABEL (jump) = label;
390
391 LABEL_NUSES (label)++;
392
393 edge e2 = make_edge (bb, dest, (*e)->flags & ~EDGE_FALLTHRU);
394 e2->probability = prob;
395 (*e)->probability = prob.invert ();
396 update_br_prob_note (e2->src);
397 return true;
398}
399
400/* Fold (add -1; zero_ext; add +1) operations to zero_ext if not wrapping. i.e:
401
402 73: r145:SI=r123:DI#0-0x1
403 74: r144:DI=zero_extend (r145:SI)
404 75: r143:DI=r144:DI+0x1
405 ...
406 31: r135:CC=cmp (r123:DI,0)
407 72: {pc={(r143:DI!=0x1)?L70:pc};r143:DI=r143:DI-0x1;...}
408
409 r123:DI#0-0x1 is param count derived from loop->niter_expr equal to number of
410 loop iterations, if loop iterations expression doesn't overflow, then
411 (zero_extend (r123:DI#0-1))+1 can be simplified to zero_extend. */
412
413static rtx
414doloop_simplify_count (class loop *loop, scalar_int_mode mode, rtx count)
415{
416 widest_int iterations;
417 if (GET_CODE (count) == ZERO_EXTEND)
418 {
419 rtx extop0 = XEXP (count, 0);
420 if (GET_CODE (extop0) == PLUS)
421 {
422 rtx addop0 = XEXP (extop0, 0);
423 rtx addop1 = XEXP (extop0, 1);
424
425 if (get_max_loop_iterations (loop, nit: &iterations)
426 && wi::ltu_p (x: iterations, GET_MODE_MASK (GET_MODE (addop0)))
427 && addop1 == constm1_rtx)
428 return simplify_gen_unary (code: ZERO_EXTEND, mode, op: addop0,
429 GET_MODE (addop0));
430 }
431 }
432
433 return simplify_gen_binary (code: PLUS, mode, op0: count, const1_rtx);
434}
435
436/* Modify the loop to use the low-overhead looping insn where LOOP
437 describes the loop, DESC describes the number of iterations of the
438 loop, and DOLOOP_INSN is the low-overhead looping insn to emit at the
439 end of the loop. CONDITION is the condition separated from the
440 DOLOOP_SEQ. COUNT is the number of iterations of the LOOP. */
441
442static void
443doloop_modify (class loop *loop, class niter_desc *desc,
444 rtx_insn *doloop_seq, rtx condition, rtx count)
445{
446 rtx counter_reg;
447 rtx tmp, noloop = NULL_RTX;
448 rtx_insn *sequence;
449 rtx_insn *jump_insn;
450 rtx_code_label *jump_label;
451 int nonneg = 0;
452 bool increment_count;
453 basic_block loop_end = desc->out_edge->src;
454 scalar_int_mode mode;
455 widest_int iterations;
456
457 jump_insn = BB_END (loop_end);
458
459 if (dump_file)
460 {
461 fprintf (stream: dump_file, format: "Doloop: Inserting doloop pattern (");
462 if (desc->const_iter)
463 fprintf (stream: dump_file, format: "%" PRId64, desc->niter);
464 else
465 fputs (s: "runtime", stream: dump_file);
466 fputs (s: " iterations).\n", stream: dump_file);
467 }
468
469 /* Discard original jump to continue loop. The original compare
470 result may still be live, so it cannot be discarded explicitly. */
471 delete_insn (jump_insn);
472
473 counter_reg = XEXP (condition, 0);
474 if (GET_CODE (counter_reg) == PLUS)
475 counter_reg = XEXP (counter_reg, 0);
476 /* These patterns must operate on integer counters. */
477 mode = as_a <scalar_int_mode> (GET_MODE (counter_reg));
478
479 increment_count = false;
480 switch (GET_CODE (condition))
481 {
482 case NE:
483 /* Currently only NE tests against zero and one are supported. */
484 noloop = XEXP (condition, 1);
485 if (noloop != const0_rtx)
486 {
487 gcc_assert (noloop == const1_rtx);
488 increment_count = true;
489 }
490 break;
491
492 case GE:
493 /* Currently only GE tests against zero are supported. */
494 gcc_assert (XEXP (condition, 1) == const0_rtx);
495
496 noloop = constm1_rtx;
497
498 /* The iteration count does not need incrementing for a GE test. */
499 increment_count = false;
500
501 /* Determine if the iteration counter will be non-negative.
502 Note that the maximum value loaded is iterations_max - 1. */
503 if (get_max_loop_iterations (loop, nit: &iterations)
504 && wi::leu_p (x: iterations,
505 y: wi::set_bit_in_zero <widest_int>
506 (GET_MODE_PRECISION (mode) - 1)))
507 nonneg = 1;
508 break;
509
510 /* Abort if an invalid doloop pattern has been generated. */
511 default:
512 gcc_unreachable ();
513 }
514
515 if (increment_count)
516 count = doloop_simplify_count (loop, mode, count);
517
518 /* Insert initialization of the count register into the loop header. */
519 start_sequence ();
520 /* count has been already copied through copy_rtx. */
521 reset_used_flags (count);
522 set_used_flags (condition);
523 tmp = force_operand (count, counter_reg);
524 convert_move (counter_reg, tmp, 1);
525 sequence = get_insns ();
526 unshare_all_rtl_in_chain (sequence);
527 end_sequence ();
528 emit_insn_after (sequence, BB_END (loop_preheader_edge (loop)->src));
529
530 if (desc->noloop_assumptions)
531 {
532 rtx ass = copy_rtx (desc->noloop_assumptions);
533 basic_block preheader = loop_preheader_edge (loop)->src;
534 basic_block set_zero = split_edge (loop_preheader_edge (loop));
535 basic_block new_preheader = split_edge (loop_preheader_edge (loop));
536 edge te;
537
538 /* Expand the condition testing the assumptions and if it does not pass,
539 reset the count register to 0. */
540 redirect_edge_and_branch_force (single_succ_edge (bb: preheader), new_preheader);
541 set_immediate_dominator (CDI_DOMINATORS, new_preheader, preheader);
542
543 set_zero->count = profile_count::uninitialized ();
544
545 te = single_succ_edge (bb: preheader);
546 for (; ass; ass = XEXP (ass, 1))
547 if (!add_test (XEXP (ass, 0), e: &te, dest: set_zero))
548 break;
549
550 if (ass)
551 {
552 /* We reached a condition that is always true. This is very hard to
553 reproduce (such a loop does not roll, and thus it would most
554 likely get optimized out by some of the preceding optimizations).
555 In fact, I do not have any testcase for it. However, it would
556 also be very hard to show that it is impossible, so we must
557 handle this case. */
558 set_zero->count = preheader->count;
559 }
560
561 if (EDGE_COUNT (set_zero->preds) == 0)
562 {
563 /* All the conditions were simplified to false, remove the
564 unreachable set_zero block. */
565 delete_basic_block (set_zero);
566 }
567 else
568 {
569 /* Reset the counter to zero in the set_zero block. */
570 start_sequence ();
571 convert_move (counter_reg, noloop, 0);
572 sequence = get_insns ();
573 end_sequence ();
574 emit_insn_after (sequence, BB_END (set_zero));
575
576 set_immediate_dominator (CDI_DOMINATORS, set_zero,
577 recompute_dominator (CDI_DOMINATORS,
578 set_zero));
579 }
580
581 set_immediate_dominator (CDI_DOMINATORS, new_preheader,
582 recompute_dominator (CDI_DOMINATORS,
583 new_preheader));
584 }
585
586 /* Some targets (eg, C4x) need to initialize special looping
587 registers. */
588 if (targetm.have_doloop_begin ())
589 if (rtx_insn *seq = targetm.gen_doloop_begin (counter_reg, doloop_seq))
590 emit_insn_after (seq, BB_END (loop_preheader_edge (loop)->src));
591
592 /* Insert the new low-overhead looping insn. */
593 emit_jump_insn_after (doloop_seq, BB_END (loop_end));
594 jump_insn = BB_END (loop_end);
595 jump_label = block_label (desc->in_edge->dest);
596 JUMP_LABEL (jump_insn) = jump_label;
597 LABEL_NUSES (jump_label)++;
598
599 /* Ensure the right fallthru edge is marked, for case we have reversed
600 the condition. */
601 desc->in_edge->flags &= ~EDGE_FALLTHRU;
602 desc->out_edge->flags |= EDGE_FALLTHRU;
603
604 /* Add a REG_NONNEG note if the actual or estimated maximum number
605 of iterations is non-negative. */
606 if (nonneg)
607 add_reg_note (jump_insn, REG_NONNEG, NULL_RTX);
608
609 /* Update the REG_BR_PROB note. */
610 if (desc->in_edge->probability.initialized_p ())
611 add_reg_br_prob_note (jump_insn, desc->in_edge->probability);
612}
613
614/* Called through note_stores. */
615
616static void
617record_reg_sets (rtx x, const_rtx pat ATTRIBUTE_UNUSED, void *data)
618{
619 bitmap mod = (bitmap)data;
620 if (REG_P (x))
621 {
622 unsigned int regno = REGNO (x);
623 if (HARD_REGISTER_P (x))
624 {
625 unsigned int end_regno = end_hard_regno (GET_MODE (x), regno);
626 do
627 bitmap_set_bit (mod, regno);
628 while (++regno < end_regno);
629 }
630 else
631 bitmap_set_bit (mod, regno);
632 }
633}
634
635/* Process loop described by LOOP validating that the loop is suitable for
636 conversion to use a low overhead looping instruction, replacing the jump
637 insn where suitable. Returns true if the loop was successfully
638 modified. */
639
640static bool
641doloop_optimize (class loop *loop)
642{
643 scalar_int_mode mode;
644 rtx doloop_reg;
645 rtx count;
646 widest_int iterations, iterations_max;
647 rtx_code_label *start_label;
648 rtx condition;
649 unsigned level;
650 HOST_WIDE_INT est_niter;
651 int max_cost;
652 class niter_desc *desc;
653 unsigned word_mode_size;
654 unsigned HOST_WIDE_INT word_mode_max;
655 int entered_at_top;
656
657 if (dump_file)
658 fprintf (stream: dump_file, format: "Doloop: Processing loop %d.\n", loop->num);
659
660 iv_analysis_loop_init (loop);
661
662 /* Find the simple exit of a LOOP. */
663 desc = get_simple_loop_desc (loop);
664
665 /* Check that loop is a candidate for a low-overhead looping insn. */
666 if (!doloop_valid_p (loop, desc))
667 {
668 if (dump_file)
669 fprintf (stream: dump_file,
670 format: "Doloop: The loop is not suitable.\n");
671 return false;
672 }
673 mode = desc->mode;
674
675 est_niter = get_estimated_loop_iterations_int (loop);
676 if (est_niter == -1)
677 est_niter = get_likely_max_loop_iterations_int (loop);
678
679 if (est_niter >= 0 && est_niter < 3)
680 {
681 if (dump_file)
682 fprintf (stream: dump_file,
683 format: "Doloop: Too few iterations (%u) to be profitable.\n",
684 (unsigned int)est_niter);
685 return false;
686 }
687
688 max_cost
689 = COSTS_N_INSNS (param_max_iterations_computation_cost);
690 if (set_src_cost (x: desc->niter_expr, mode, speed_p: optimize_loop_for_speed_p (loop))
691 > max_cost)
692 {
693 if (dump_file)
694 fprintf (stream: dump_file,
695 format: "Doloop: number of iterations too costly to compute.\n");
696 return false;
697 }
698
699 if (desc->const_iter)
700 iterations = widest_int::from (x: rtx_mode_t (desc->niter_expr, mode),
701 sgn: UNSIGNED);
702 else
703 iterations = 0;
704 if (!get_max_loop_iterations (loop, nit: &iterations_max))
705 iterations_max = 0;
706 level = get_loop_level (loop) + 1;
707 entered_at_top = (loop->latch == desc->in_edge->dest
708 && contains_no_active_insn_p (loop->latch));
709 if (!targetm.can_use_doloop_p (iterations, iterations_max, level,
710 entered_at_top))
711 {
712 if (dump_file)
713 fprintf (stream: dump_file, format: "Loop rejected by can_use_doloop_p.\n");
714 return false;
715 }
716
717 /* Generate looping insn. If the pattern FAILs then give up trying
718 to modify the loop since there is some aspect the back-end does
719 not like. */
720 count = copy_rtx (desc->niter_expr);
721 start_label = block_label (desc->in_edge->dest);
722 doloop_reg = gen_reg_rtx (mode);
723 rtx_insn *doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
724
725 word_mode_size = GET_MODE_PRECISION (mode: word_mode);
726 word_mode_max = (HOST_WIDE_INT_1U << (word_mode_size - 1) << 1) - 1;
727 if (! doloop_seq
728 && mode != word_mode
729 /* Before trying mode different from the one in that # of iterations is
730 computed, we must be sure that the number of iterations fits into
731 the new mode. */
732 && (word_mode_size >= GET_MODE_PRECISION (mode)
733 || wi::leu_p (x: iterations_max, y: word_mode_max)))
734 {
735 if (word_mode_size > GET_MODE_PRECISION (mode))
736 count = simplify_gen_unary (code: ZERO_EXTEND, mode: word_mode, op: count, op_mode: mode);
737 else
738 count = lowpart_subreg (outermode: word_mode, op: count, innermode: mode);
739 PUT_MODE (x: doloop_reg, mode: word_mode);
740 doloop_seq = targetm.gen_doloop_end (doloop_reg, start_label);
741 }
742 if (! doloop_seq)
743 {
744 if (dump_file)
745 fprintf (stream: dump_file,
746 format: "Doloop: Target unwilling to use doloop pattern!\n");
747 return false;
748 }
749
750 /* If multiple instructions were created, the last must be the
751 jump instruction. */
752 rtx_insn *doloop_insn = doloop_seq;
753 while (NEXT_INSN (insn: doloop_insn) != NULL_RTX)
754 doloop_insn = NEXT_INSN (insn: doloop_insn);
755 if (!JUMP_P (doloop_insn)
756 || !(condition = doloop_condition_get (doloop_pat: doloop_insn)))
757 {
758 if (dump_file)
759 fprintf (stream: dump_file, format: "Doloop: Unrecognizable doloop pattern!\n");
760 return false;
761 }
762
763 /* Ensure that the new sequence doesn't clobber a register that
764 is live at the end of the block. */
765 {
766 bitmap modified = BITMAP_ALLOC (NULL);
767
768 for (rtx_insn *i = doloop_seq; i != NULL; i = NEXT_INSN (insn: i))
769 note_stores (i, record_reg_sets, modified);
770
771 basic_block loop_end = desc->out_edge->src;
772 bool fail = bitmap_intersect_p (df_get_live_out (bb: loop_end), modified);
773 BITMAP_FREE (modified);
774
775 if (fail)
776 {
777 if (dump_file)
778 fprintf (stream: dump_file, format: "Doloop: doloop pattern clobbers live out\n");
779 return false;
780 }
781 }
782
783 doloop_modify (loop, desc, doloop_seq, condition, count);
784 return true;
785}
786
787/* This is the main entry point. Process all loops using doloop_optimize. */
788
789void
790doloop_optimize_loops (void)
791{
792 if (optimize == 1)
793 {
794 df_live_add_problem ();
795 df_live_set_all_dirty ();
796 }
797
798 for (auto loop : loops_list (cfun, 0))
799 doloop_optimize (loop);
800
801 if (optimize == 1)
802 df_remove_problem (df_live);
803
804 iv_analysis_done ();
805
806 checking_verify_loop_structure ();
807}
808

source code of gcc/loop-doloop.cc