1/* Loop unrolling.
2 Copyright (C) 2002-2023 Free Software Foundation, Inc.
3
4This file is part of GCC.
5
6GCC is free software; you can redistribute it and/or modify it under
7the terms of the GNU General Public License as published by the Free
8Software Foundation; either version 3, or (at your option) any later
9version.
10
11GCC is distributed in the hope that it will be useful, but WITHOUT ANY
12WARRANTY; without even the implied warranty of MERCHANTABILITY or
13FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14for more details.
15
16You should have received a copy of the GNU General Public License
17along with GCC; see the file COPYING3. If not see
18<http://www.gnu.org/licenses/>. */
19
20#include "config.h"
21#include "system.h"
22#include "coretypes.h"
23#include "backend.h"
24#include "target.h"
25#include "rtl.h"
26#include "tree.h"
27#include "cfghooks.h"
28#include "memmodel.h"
29#include "optabs.h"
30#include "emit-rtl.h"
31#include "recog.h"
32#include "profile.h"
33#include "cfgrtl.h"
34#include "cfgloop.h"
35#include "dojump.h"
36#include "expr.h"
37#include "dumpfile.h"
38
39/* This pass performs loop unrolling. We only perform this
40 optimization on innermost loops (with single exception) because
41 the impact on performance is greatest here, and we want to avoid
42 unnecessary code size growth. The gain is caused by greater sequentiality
43 of code, better code to optimize for further passes and in some cases
44 by fewer testings of exit conditions. The main problem is code growth,
45 that impacts performance negatively due to effect of caches.
46
47 What we do:
48
49 -- unrolling of loops that roll constant times; this is almost always
50 win, as we get rid of exit condition tests.
51 -- unrolling of loops that roll number of times that we can compute
52 in runtime; we also get rid of exit condition tests here, but there
53 is the extra expense for calculating the number of iterations
54 -- simple unrolling of remaining loops; this is performed only if we
55 are asked to, as the gain is questionable in this case and often
56 it may even slow down the code
57 For more detailed descriptions of each of those, see comments at
58 appropriate function below.
59
60 There is a lot of parameters (defined and described in params.def) that
61 control how much we unroll.
62
63 ??? A great problem is that we don't have a good way how to determine
64 how many times we should unroll the loop; the experiments I have made
65 showed that this choice may affect performance in order of several %.
66 */
67
68/* Information about induction variables to split. */
69
70struct iv_to_split
71{
72 rtx_insn *insn; /* The insn in that the induction variable occurs. */
73 rtx orig_var; /* The variable (register) for the IV before split. */
74 rtx base_var; /* The variable on that the values in the further
75 iterations are based. */
76 rtx step; /* Step of the induction variable. */
77 struct iv_to_split *next; /* Next entry in walking order. */
78};
79
80/* Information about accumulators to expand. */
81
82struct var_to_expand
83{
84 rtx_insn *insn; /* The insn in that the variable expansion occurs. */
85 rtx reg; /* The accumulator which is expanded. */
86 vec<rtx> var_expansions; /* The copies of the accumulator which is expanded. */
87 struct var_to_expand *next; /* Next entry in walking order. */
88 enum rtx_code op; /* The type of the accumulation - addition, subtraction
89 or multiplication. */
90 int expansion_count; /* Count the number of expansions generated so far. */
91 int reuse_expansion; /* The expansion we intend to reuse to expand
92 the accumulator. If REUSE_EXPANSION is 0 reuse
93 the original accumulator. Else use
94 var_expansions[REUSE_EXPANSION - 1]. */
95};
96
97/* Hashtable helper for iv_to_split. */
98
99struct iv_split_hasher : free_ptr_hash <iv_to_split>
100{
101 static inline hashval_t hash (const iv_to_split *);
102 static inline bool equal (const iv_to_split *, const iv_to_split *);
103};
104
105
106/* A hash function for information about insns to split. */
107
108inline hashval_t
109iv_split_hasher::hash (const iv_to_split *ivts)
110{
111 return (hashval_t) INSN_UID (insn: ivts->insn);
112}
113
114/* An equality functions for information about insns to split. */
115
116inline bool
117iv_split_hasher::equal (const iv_to_split *i1, const iv_to_split *i2)
118{
119 return i1->insn == i2->insn;
120}
121
122/* Hashtable helper for iv_to_split. */
123
124struct var_expand_hasher : free_ptr_hash <var_to_expand>
125{
126 static inline hashval_t hash (const var_to_expand *);
127 static inline bool equal (const var_to_expand *, const var_to_expand *);
128};
129
130/* Return a hash for VES. */
131
132inline hashval_t
133var_expand_hasher::hash (const var_to_expand *ves)
134{
135 return (hashval_t) INSN_UID (insn: ves->insn);
136}
137
138/* Return true if I1 and I2 refer to the same instruction. */
139
140inline bool
141var_expand_hasher::equal (const var_to_expand *i1, const var_to_expand *i2)
142{
143 return i1->insn == i2->insn;
144}
145
146/* Information about optimization applied in
147 the unrolled loop. */
148
149struct opt_info
150{
151 hash_table<iv_split_hasher> *insns_to_split; /* A hashtable of insns to
152 split. */
153 struct iv_to_split *iv_to_split_head; /* The first iv to split. */
154 struct iv_to_split **iv_to_split_tail; /* Pointer to the tail of the list. */
155 hash_table<var_expand_hasher> *insns_with_var_to_expand; /* A hashtable of
156 insns with accumulators to expand. */
157 struct var_to_expand *var_to_expand_head; /* The first var to expand. */
158 struct var_to_expand **var_to_expand_tail; /* Pointer to the tail of the list. */
159 unsigned first_new_block; /* The first basic block that was
160 duplicated. */
161 basic_block loop_exit; /* The loop exit basic block. */
162 basic_block loop_preheader; /* The loop preheader basic block. */
163};
164
165static void decide_unroll_stupid (class loop *, int);
166static void decide_unroll_constant_iterations (class loop *, int);
167static void decide_unroll_runtime_iterations (class loop *, int);
168static void unroll_loop_stupid (class loop *);
169static void decide_unrolling (int);
170static void unroll_loop_constant_iterations (class loop *);
171static void unroll_loop_runtime_iterations (class loop *);
172static struct opt_info *analyze_insns_in_loop (class loop *);
173static void opt_info_start_duplication (struct opt_info *);
174static void apply_opt_in_copies (struct opt_info *, unsigned, bool, bool);
175static void free_opt_info (struct opt_info *);
176static struct var_to_expand *analyze_insn_to_expand_var (class loop*, rtx_insn *);
177static bool referenced_in_one_insn_in_loop_p (class loop *, rtx, int *);
178static struct iv_to_split *analyze_iv_to_split_insn (rtx_insn *);
179static void expand_var_during_unrolling (struct var_to_expand *, rtx_insn *);
180static void insert_var_expansion_initialization (struct var_to_expand *,
181 basic_block);
182static void combine_var_copies_in_loop_exit (struct var_to_expand *,
183 basic_block);
184static rtx get_expansion (struct var_to_expand *);
185
186/* Emit a message summarizing the unroll that will be
187 performed for LOOP, along with the loop's location LOCUS, if
188 appropriate given the dump or -fopt-info settings. */
189
190static void
191report_unroll (class loop *loop, dump_location_t locus)
192{
193 dump_flags_t report_flags = MSG_OPTIMIZED_LOCATIONS | TDF_DETAILS;
194
195 if (loop->lpt_decision.decision == LPT_NONE)
196 return;
197
198 if (!dump_enabled_p ())
199 return;
200
201 dump_metadata_t metadata (report_flags, locus.get_impl_location ());
202 dump_printf_loc (metadata, locus.get_user_location (),
203 "loop unrolled %d times",
204 loop->lpt_decision.times);
205 if (profile_info && loop->header->count.initialized_p ())
206 dump_printf (metadata,
207 " (header execution count %d)",
208 (int)loop->header->count.to_gcov_type ());
209
210 dump_printf (metadata, "\n");
211}
212
213/* Decide whether unroll loops and how much. */
214static void
215decide_unrolling (int flags)
216{
217 /* Scan the loops, inner ones first. */
218 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
219 {
220 loop->lpt_decision.decision = LPT_NONE;
221 dump_user_location_t locus = get_loop_location (loop);
222
223 if (dump_enabled_p ())
224 dump_printf_loc (MSG_NOTE, locus,
225 "considering unrolling loop %d at BB %d\n",
226 loop->num, loop->header->index);
227
228 if (loop->unroll == 1)
229 {
230 if (dump_file)
231 fprintf (stream: dump_file,
232 format: ";; Not unrolling loop, user didn't want it unrolled\n");
233 continue;
234 }
235
236 /* Do not peel cold areas. */
237 if (optimize_loop_for_size_p (loop))
238 {
239 if (dump_file)
240 fprintf (stream: dump_file, format: ";; Not considering loop, cold area\n");
241 continue;
242 }
243
244 /* Can the loop be manipulated? */
245 if (!can_duplicate_loop_p (loop))
246 {
247 if (dump_file)
248 fprintf (stream: dump_file,
249 format: ";; Not considering loop, cannot duplicate\n");
250 continue;
251 }
252
253 /* Skip non-innermost loops. */
254 if (loop->inner)
255 {
256 if (dump_file)
257 fprintf (stream: dump_file, format: ";; Not considering loop, is not innermost\n");
258 continue;
259 }
260
261 loop->ninsns = num_loop_insns (loop);
262 loop->av_ninsns = average_num_loop_insns (loop);
263
264 /* Try transformations one by one in decreasing order of priority. */
265 decide_unroll_constant_iterations (loop, flags);
266 if (loop->lpt_decision.decision == LPT_NONE)
267 decide_unroll_runtime_iterations (loop, flags);
268 if (loop->lpt_decision.decision == LPT_NONE)
269 decide_unroll_stupid (loop, flags);
270
271 report_unroll (loop, locus);
272 }
273}
274
275/* Unroll LOOPS. */
276void
277unroll_loops (int flags)
278{
279 bool changed = false;
280
281 /* Now decide rest of unrolling. */
282 decide_unrolling (flags);
283
284 /* Scan the loops, inner ones first. */
285 for (auto loop : loops_list (cfun, LI_FROM_INNERMOST))
286 {
287 /* And perform the appropriate transformations. */
288 switch (loop->lpt_decision.decision)
289 {
290 case LPT_UNROLL_CONSTANT:
291 unroll_loop_constant_iterations (loop);
292 changed = true;
293 break;
294 case LPT_UNROLL_RUNTIME:
295 unroll_loop_runtime_iterations (loop);
296 changed = true;
297 break;
298 case LPT_UNROLL_STUPID:
299 unroll_loop_stupid (loop);
300 changed = true;
301 break;
302 case LPT_NONE:
303 break;
304 default:
305 gcc_unreachable ();
306 }
307 }
308
309 if (changed)
310 {
311 calculate_dominance_info (CDI_DOMINATORS);
312 fix_loop_structure (NULL);
313 }
314
315 iv_analysis_done ();
316}
317
318/* Check whether exit of the LOOP is at the end of loop body. */
319
320static bool
321loop_exit_at_end_p (class loop *loop)
322{
323 class niter_desc *desc = get_simple_loop_desc (loop);
324 rtx_insn *insn;
325
326 /* We should never have conditional in latch block. */
327 gcc_assert (desc->in_edge->dest != loop->header);
328
329 if (desc->in_edge->dest != loop->latch)
330 return false;
331
332 /* Check that the latch is empty. */
333 FOR_BB_INSNS (loop->latch, insn)
334 {
335 if (INSN_P (insn) && active_insn_p (insn))
336 return false;
337 }
338
339 return true;
340}
341
342/* Decide whether to unroll LOOP iterating constant number of times
343 and how much. */
344
345static void
346decide_unroll_constant_iterations (class loop *loop, int flags)
347{
348 unsigned nunroll, nunroll_by_av, best_copies, best_unroll = 0, n_copies, i;
349 class niter_desc *desc;
350 widest_int iterations;
351
352 /* If we were not asked to unroll this loop, just return back silently. */
353 if (!(flags & UAP_UNROLL) && !loop->unroll)
354 return;
355
356 if (dump_enabled_p ())
357 dump_printf (MSG_NOTE,
358 "considering unrolling loop with constant "
359 "number of iterations\n");
360
361 /* nunroll = total number of copies of the original loop body in
362 unrolled loop (i.e. if it is 2, we have to duplicate loop body once). */
363 nunroll = param_max_unrolled_insns / loop->ninsns;
364 nunroll_by_av
365 = param_max_average_unrolled_insns / loop->av_ninsns;
366 if (nunroll > nunroll_by_av)
367 nunroll = nunroll_by_av;
368 if (nunroll > (unsigned) param_max_unroll_times)
369 nunroll = param_max_unroll_times;
370
371 if (targetm.loop_unroll_adjust)
372 nunroll = targetm.loop_unroll_adjust (nunroll, loop);
373
374 /* Skip big loops. */
375 if (nunroll <= 1)
376 {
377 if (dump_file)
378 fprintf (stream: dump_file, format: ";; Not considering loop, is too big\n");
379 return;
380 }
381
382 /* Check for simple loops. */
383 desc = get_simple_loop_desc (loop);
384
385 /* Check number of iterations. */
386 if (!desc->simple_p || !desc->const_iter || desc->assumptions)
387 {
388 if (dump_file)
389 fprintf (stream: dump_file,
390 format: ";; Unable to prove that the loop iterates constant times\n");
391 return;
392 }
393
394 /* Check for an explicit unrolling factor. */
395 if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
396 {
397 /* However we cannot unroll completely at the RTL level a loop with
398 constant number of iterations; it should have been peeled instead. */
399 if (desc->niter == 0 || (unsigned) loop->unroll > desc->niter - 1)
400 {
401 if (dump_file)
402 fprintf (stream: dump_file, format: ";; Loop should have been peeled\n");
403 }
404 else
405 {
406 loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
407 loop->lpt_decision.times = loop->unroll - 1;
408 }
409 return;
410 }
411
412 /* Check whether the loop rolls enough to consider.
413 Consult also loop bounds and profile; in the case the loop has more
414 than one exit it may well loop less than determined maximal number
415 of iterations. */
416 if (desc->niter < 2 * nunroll
417 || ((get_estimated_loop_iterations (loop, nit: &iterations)
418 || get_likely_max_loop_iterations (loop, nit: &iterations))
419 && wi::ltu_p (x: iterations, y: 2 * nunroll)))
420 {
421 if (dump_file)
422 fprintf (stream: dump_file, format: ";; Not unrolling loop, doesn't roll\n");
423 return;
424 }
425
426 /* Success; now compute number of iterations to unroll. We alter
427 nunroll so that as few as possible copies of loop body are
428 necessary, while still not decreasing the number of unrollings
429 too much (at most by 1). */
430 best_copies = 2 * nunroll + 10;
431
432 i = 2 * nunroll + 2;
433 if (i > desc->niter - 2)
434 i = desc->niter - 2;
435
436 for (; i >= nunroll - 1; i--)
437 {
438 unsigned exit_mod = desc->niter % (i + 1);
439
440 if (!loop_exit_at_end_p (loop))
441 n_copies = exit_mod + i + 1;
442 else if (exit_mod != (unsigned) i
443 || desc->noloop_assumptions != NULL_RTX)
444 n_copies = exit_mod + i + 2;
445 else
446 n_copies = i + 1;
447
448 if (n_copies < best_copies)
449 {
450 best_copies = n_copies;
451 best_unroll = i;
452 }
453 }
454
455 loop->lpt_decision.decision = LPT_UNROLL_CONSTANT;
456 loop->lpt_decision.times = best_unroll;
457}
458
459/* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
460 The transformation does this:
461
462 for (i = 0; i < 102; i++)
463 body;
464
465 ==> (LOOP->LPT_DECISION.TIMES == 3)
466
467 i = 0;
468 body; i++;
469 body; i++;
470 while (i < 102)
471 {
472 body; i++;
473 body; i++;
474 body; i++;
475 body; i++;
476 }
477 */
478static void
479unroll_loop_constant_iterations (class loop *loop)
480{
481 unsigned HOST_WIDE_INT niter;
482 unsigned exit_mod;
483 unsigned i;
484 edge e;
485 unsigned max_unroll = loop->lpt_decision.times;
486 class niter_desc *desc = get_simple_loop_desc (loop);
487 bool exit_at_end = loop_exit_at_end_p (loop);
488 struct opt_info *opt_info = NULL;
489 bool ok;
490 bool flat = maybe_flat_loop_profile (loop);
491 profile_count orig_exit_count = desc->out_edge->count ();
492
493 niter = desc->niter;
494
495 /* Should not get here (such loop should be peeled instead). */
496 gcc_assert (niter > max_unroll + 1);
497
498 exit_mod = niter % (max_unroll + 1);
499
500 auto_sbitmap wont_exit (max_unroll + 2);
501 bitmap_ones (wont_exit);
502
503 auto_vec<edge> remove_edges;
504 if (flag_split_ivs_in_unroller
505 || flag_variable_expansion_in_unroller)
506 opt_info = analyze_insns_in_loop (loop);
507
508 if (!exit_at_end)
509 {
510 /* The exit is not at the end of the loop; leave exit test
511 in the first copy, so that the loops that start with test
512 of exit condition have continuous body after unrolling. */
513
514 if (dump_file)
515 fprintf (stream: dump_file, format: ";; Condition at beginning of loop.\n");
516
517 /* Peel exit_mod iterations. */
518 bitmap_clear_bit (map: wont_exit, bitno: 0);
519 if (desc->noloop_assumptions)
520 bitmap_clear_bit (map: wont_exit, bitno: 1);
521
522 if (exit_mod)
523 {
524 opt_info_start_duplication (opt_info);
525 ok = duplicate_loop_body_to_header_edge (
526 loop, loop_preheader_edge (loop), exit_mod, wont_exit,
527 desc->out_edge, &remove_edges,
528 DLTHE_FLAG_UPDATE_FREQ
529 | (opt_info && exit_mod > 1 ? DLTHE_RECORD_COPY_NUMBER : 0));
530 gcc_assert (ok);
531
532 if (opt_info && exit_mod > 1)
533 apply_opt_in_copies (opt_info, exit_mod, false, false);
534
535 desc->noloop_assumptions = NULL_RTX;
536 desc->niter -= exit_mod;
537 loop->nb_iterations_upper_bound -= exit_mod;
538 if (loop->any_estimate
539 && wi::leu_p (x: exit_mod, y: loop->nb_iterations_estimate))
540 loop->nb_iterations_estimate -= exit_mod;
541 else
542 loop->any_estimate = false;
543 if (loop->any_likely_upper_bound
544 && wi::leu_p (x: exit_mod, y: loop->nb_iterations_likely_upper_bound))
545 loop->nb_iterations_likely_upper_bound -= exit_mod;
546 else
547 loop->any_likely_upper_bound = false;
548 }
549
550 bitmap_set_bit (map: wont_exit, bitno: 1);
551 }
552 else
553 {
554 /* Leave exit test in last copy, for the same reason as above if
555 the loop tests the condition at the end of loop body. */
556
557 if (dump_file)
558 fprintf (stream: dump_file, format: ";; Condition at end of loop.\n");
559
560 /* We know that niter >= max_unroll + 2; so we do not need to care of
561 case when we would exit before reaching the loop. So just peel
562 exit_mod + 1 iterations. */
563 if (exit_mod != max_unroll
564 || desc->noloop_assumptions)
565 {
566 bitmap_clear_bit (map: wont_exit, bitno: 0);
567 if (desc->noloop_assumptions)
568 bitmap_clear_bit (map: wont_exit, bitno: 1);
569
570 opt_info_start_duplication (opt_info);
571 ok = duplicate_loop_body_to_header_edge (
572 loop, loop_preheader_edge (loop), exit_mod + 1, wont_exit,
573 desc->out_edge, &remove_edges,
574 DLTHE_FLAG_UPDATE_FREQ
575 | (opt_info && exit_mod > 0 ? DLTHE_RECORD_COPY_NUMBER : 0));
576 gcc_assert (ok);
577
578 if (opt_info && exit_mod > 0)
579 apply_opt_in_copies (opt_info, exit_mod + 1, false, false);
580
581 desc->niter -= exit_mod + 1;
582 loop->nb_iterations_upper_bound -= exit_mod + 1;
583 if (loop->any_estimate
584 && wi::leu_p (x: exit_mod + 1, y: loop->nb_iterations_estimate))
585 loop->nb_iterations_estimate -= exit_mod + 1;
586 else
587 loop->any_estimate = false;
588 if (loop->any_likely_upper_bound
589 && wi::leu_p (x: exit_mod + 1, y: loop->nb_iterations_likely_upper_bound))
590 loop->nb_iterations_likely_upper_bound -= exit_mod + 1;
591 else
592 loop->any_likely_upper_bound = false;
593 desc->noloop_assumptions = NULL_RTX;
594
595 bitmap_set_bit (map: wont_exit, bitno: 0);
596 bitmap_set_bit (map: wont_exit, bitno: 1);
597 }
598
599 bitmap_clear_bit (map: wont_exit, bitno: max_unroll);
600 }
601
602 /* Now unroll the loop. */
603
604 opt_info_start_duplication (opt_info);
605 ok = duplicate_loop_body_to_header_edge (
606 loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
607 &remove_edges,
608 DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0)
609 | (flat ? DLTHE_FLAG_FLAT_PROFILE : 0));
610 gcc_assert (ok);
611
612 edge exit = update_loop_exit_probability_scale_dom_bbs
613 (loop, exit_edge: desc->out_edge, desired_count: orig_exit_count);
614 if (exit)
615 update_br_prob_note (exit->src);
616
617 if (opt_info)
618 {
619 apply_opt_in_copies (opt_info, max_unroll, true, true);
620 free_opt_info (opt_info);
621 }
622
623 if (exit_at_end)
624 {
625 basic_block exit_block = get_bb_copy (desc->in_edge->src);
626 /* Find a new in and out edge; they are in the last copy we have made. */
627
628 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
629 {
630 desc->out_edge = EDGE_SUCC (exit_block, 0);
631 desc->in_edge = EDGE_SUCC (exit_block, 1);
632 }
633 else
634 {
635 desc->out_edge = EDGE_SUCC (exit_block, 1);
636 desc->in_edge = EDGE_SUCC (exit_block, 0);
637 }
638 }
639
640 desc->niter /= max_unroll + 1;
641 loop->nb_iterations_upper_bound
642 = wi::udiv_trunc (x: loop->nb_iterations_upper_bound, y: max_unroll + 1);
643 if (loop->any_estimate)
644 loop->nb_iterations_estimate
645 = wi::udiv_trunc (x: loop->nb_iterations_estimate, y: max_unroll + 1);
646 if (loop->any_likely_upper_bound)
647 loop->nb_iterations_likely_upper_bound
648 = wi::udiv_trunc (x: loop->nb_iterations_likely_upper_bound, y: max_unroll + 1);
649 desc->niter_expr = gen_int_mode (desc->niter, desc->mode);
650
651 /* Remove the edges. */
652 FOR_EACH_VEC_ELT (remove_edges, i, e)
653 remove_path (e);
654
655 if (dump_file)
656 fprintf (stream: dump_file,
657 format: ";; Unrolled loop %d times, constant # of iterations %i insns\n",
658 max_unroll, num_loop_insns (loop));
659}
660
661/* Decide whether to unroll LOOP iterating runtime computable number of times
662 and how much. */
663static void
664decide_unroll_runtime_iterations (class loop *loop, int flags)
665{
666 unsigned nunroll, nunroll_by_av, i;
667 class niter_desc *desc;
668 widest_int iterations;
669
670 /* If we were not asked to unroll this loop, just return back silently. */
671 if (!(flags & UAP_UNROLL) && !loop->unroll)
672 return;
673
674 if (dump_enabled_p ())
675 dump_printf (MSG_NOTE,
676 "considering unrolling loop with runtime-"
677 "computable number of iterations\n");
678
679 /* nunroll = total number of copies of the original loop body in
680 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
681 nunroll = param_max_unrolled_insns / loop->ninsns;
682 nunroll_by_av = param_max_average_unrolled_insns / loop->av_ninsns;
683 if (nunroll > nunroll_by_av)
684 nunroll = nunroll_by_av;
685 if (nunroll > (unsigned) param_max_unroll_times)
686 nunroll = param_max_unroll_times;
687
688 if (targetm.loop_unroll_adjust)
689 nunroll = targetm.loop_unroll_adjust (nunroll, loop);
690
691 if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
692 nunroll = loop->unroll;
693
694 /* Skip big loops. */
695 if (nunroll <= 1)
696 {
697 if (dump_file)
698 fprintf (stream: dump_file, format: ";; Not considering loop, is too big\n");
699 return;
700 }
701
702 /* Check for simple loops. */
703 desc = get_simple_loop_desc (loop);
704
705 /* Check simpleness. */
706 if (!desc->simple_p || desc->assumptions)
707 {
708 if (dump_file)
709 fprintf (stream: dump_file,
710 format: ";; Unable to prove that the number of iterations "
711 "can be counted in runtime\n");
712 return;
713 }
714
715 if (desc->const_iter)
716 {
717 if (dump_file)
718 fprintf (stream: dump_file, format: ";; Loop iterates constant times\n");
719 return;
720 }
721
722 /* Check whether the loop rolls. */
723 if ((get_estimated_loop_iterations (loop, nit: &iterations)
724 || get_likely_max_loop_iterations (loop, nit: &iterations))
725 && wi::ltu_p (x: iterations, y: 2 * nunroll))
726 {
727 if (dump_file)
728 fprintf (stream: dump_file, format: ";; Not unrolling loop, doesn't roll\n");
729 return;
730 }
731
732 /* Success; now force nunroll to be power of 2, as code-gen
733 requires it, we are unable to cope with overflows in
734 computation of number of iterations. */
735 for (i = 1; 2 * i <= nunroll; i *= 2)
736 continue;
737
738 loop->lpt_decision.decision = LPT_UNROLL_RUNTIME;
739 loop->lpt_decision.times = i - 1;
740}
741
742/* Splits edge E and inserts the sequence of instructions INSNS on it, and
743 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
744 and NULL is returned instead. */
745
746basic_block
747split_edge_and_insert (edge e, rtx_insn *insns)
748{
749 basic_block bb;
750
751 if (!insns)
752 return NULL;
753 bb = split_edge (e);
754 emit_insn_after (insns, BB_END (bb));
755
756 /* ??? We used to assume that INSNS can contain control flow insns, and
757 that we had to try to find sub basic blocks in BB to maintain a valid
758 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
759 and call break_superblocks when going out of cfglayout mode. But it
760 turns out that this never happens; and that if it does ever happen,
761 the verify_flow_info at the end of the RTL loop passes would fail.
762
763 There are two reasons why we expected we could have control flow insns
764 in INSNS. The first is when a comparison has to be done in parts, and
765 the second is when the number of iterations is computed for loops with
766 the number of iterations known at runtime. In both cases, test cases
767 to get control flow in INSNS appear to be impossible to construct:
768
769 * If do_compare_rtx_and_jump needs several branches to do comparison
770 in a mode that needs comparison by parts, we cannot analyze the
771 number of iterations of the loop, and we never get to unrolling it.
772
773 * The code in expand_divmod that was suspected to cause creation of
774 branching code seems to be only accessed for signed division. The
775 divisions used by # of iterations analysis are always unsigned.
776 Problems might arise on architectures that emits branching code
777 for some operations that may appear in the unroller (especially
778 for division), but we have no such architectures.
779
780 Considering all this, it was decided that we should for now assume
781 that INSNS can in theory contain control flow insns, but in practice
782 it never does. So we don't handle the theoretical case, and should
783 a real failure ever show up, we have a pretty good clue for how to
784 fix it. */
785
786 return bb;
787}
788
789/* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
790 true, with probability PROB. If CINSN is not NULL, it is the insn to copy
791 in order to create a jump. */
792
793static rtx_insn *
794compare_and_jump_seq (rtx op0, rtx op1, enum rtx_code comp,
795 rtx_code_label *label, profile_probability prob,
796 rtx_insn *cinsn)
797{
798 rtx_insn *seq;
799 rtx_jump_insn *jump;
800 rtx cond;
801 machine_mode mode;
802
803 mode = GET_MODE (op0);
804 if (mode == VOIDmode)
805 mode = GET_MODE (op1);
806
807 start_sequence ();
808 if (GET_MODE_CLASS (mode) == MODE_CC)
809 {
810 /* A hack -- there seems to be no easy generic way how to make a
811 conditional jump from a ccmode comparison. */
812 gcc_assert (cinsn);
813 cond = XEXP (SET_SRC (pc_set (cinsn)), 0);
814 gcc_assert (GET_CODE (cond) == comp);
815 gcc_assert (rtx_equal_p (op0, XEXP (cond, 0)));
816 gcc_assert (rtx_equal_p (op1, XEXP (cond, 1)));
817 emit_jump_insn (copy_insn (PATTERN (insn: cinsn)));
818 jump = as_a <rtx_jump_insn *> (p: get_last_insn ());
819 JUMP_LABEL (jump) = JUMP_LABEL (cinsn);
820 LABEL_NUSES (JUMP_LABEL (jump))++;
821 redirect_jump (jump, label, 0);
822 }
823 else
824 {
825 gcc_assert (!cinsn);
826
827 op0 = force_operand (op0, NULL_RTX);
828 op1 = force_operand (op1, NULL_RTX);
829 do_compare_rtx_and_jump (op0, op1, comp, 0,
830 mode, NULL_RTX, NULL, label,
831 profile_probability::uninitialized ());
832 jump = as_a <rtx_jump_insn *> (p: get_last_insn ());
833 jump->set_jump_target (label);
834 LABEL_NUSES (label)++;
835 }
836 if (prob.initialized_p ())
837 add_reg_br_prob_note (jump, prob);
838
839 seq = get_insns ();
840 end_sequence ();
841
842 return seq;
843}
844
845/* Unroll LOOP for which we are able to count number of iterations in
846 runtime LOOP->LPT_DECISION.TIMES times. The times value must be a
847 power of two. The transformation does this (with some extra care
848 for case n < 0):
849
850 for (i = 0; i < n; i++)
851 body;
852
853 ==> (LOOP->LPT_DECISION.TIMES == 3)
854
855 i = 0;
856 mod = n % 4;
857
858 switch (mod)
859 {
860 case 3:
861 body; i++;
862 case 2:
863 body; i++;
864 case 1:
865 body; i++;
866 case 0: ;
867 }
868
869 while (i < n)
870 {
871 body; i++;
872 body; i++;
873 body; i++;
874 body; i++;
875 }
876 */
877static void
878unroll_loop_runtime_iterations (class loop *loop)
879{
880 rtx old_niter, niter, tmp;
881 rtx_insn *init_code, *branch_code;
882 unsigned i;
883 profile_probability p;
884 basic_block preheader, *body, swtch, ezc_swtch = NULL;
885 int may_exit_copy;
886 profile_count iter_count, new_count;
887 unsigned n_peel;
888 edge e;
889 bool extra_zero_check, last_may_exit;
890 unsigned max_unroll = loop->lpt_decision.times;
891 class niter_desc *desc = get_simple_loop_desc (loop);
892 bool exit_at_end = loop_exit_at_end_p (loop);
893 struct opt_info *opt_info = NULL;
894 bool ok;
895
896 if (flag_split_ivs_in_unroller
897 || flag_variable_expansion_in_unroller)
898 opt_info = analyze_insns_in_loop (loop);
899
900 /* Remember blocks whose dominators will have to be updated. */
901 auto_vec<basic_block> dom_bbs;
902
903 body = get_loop_body (loop);
904 for (i = 0; i < loop->num_nodes; i++)
905 {
906 for (basic_block bb : get_dominated_by (CDI_DOMINATORS, body[i]))
907 if (!flow_bb_inside_loop_p (loop, bb))
908 dom_bbs.safe_push (obj: bb);
909 }
910 free (ptr: body);
911
912 if (!exit_at_end)
913 {
914 /* Leave exit in first copy (for explanation why see comment in
915 unroll_loop_constant_iterations). */
916 may_exit_copy = 0;
917 n_peel = max_unroll - 1;
918 extra_zero_check = true;
919 last_may_exit = false;
920 }
921 else
922 {
923 /* Leave exit in last copy (for explanation why see comment in
924 unroll_loop_constant_iterations). */
925 may_exit_copy = max_unroll;
926 n_peel = max_unroll;
927 extra_zero_check = false;
928 last_may_exit = true;
929 }
930
931 /* Get expression for number of iterations. */
932 start_sequence ();
933 old_niter = niter = gen_reg_rtx (desc->mode);
934 tmp = force_operand (copy_rtx (desc->niter_expr), niter);
935 if (tmp != niter)
936 emit_move_insn (niter, tmp);
937
938 /* For loops that exit at end and whose number of iterations is reliable,
939 add one to niter to account for first pass through loop body before
940 reaching exit test. */
941 if (exit_at_end && !desc->noloop_assumptions)
942 {
943 niter = expand_simple_binop (desc->mode, PLUS,
944 niter, const1_rtx,
945 NULL_RTX, 0, OPTAB_LIB_WIDEN);
946 old_niter = niter;
947 }
948
949 /* Count modulo by ANDing it with max_unroll; we use the fact that
950 the number of unrollings is a power of two, and thus this is correct
951 even if there is overflow in the computation. */
952 niter = expand_simple_binop (desc->mode, AND,
953 niter, gen_int_mode (max_unroll, desc->mode),
954 NULL_RTX, 0, OPTAB_LIB_WIDEN);
955
956 init_code = get_insns ();
957 end_sequence ();
958 unshare_all_rtl_in_chain (init_code);
959
960 /* Precondition the loop. */
961 split_edge_and_insert (e: loop_preheader_edge (loop), insns: init_code);
962
963 auto_vec<edge> remove_edges;
964
965 auto_sbitmap wont_exit (max_unroll + 2);
966
967 if (extra_zero_check || desc->noloop_assumptions)
968 {
969 /* Peel the first copy of loop body. Leave the exit test if the number
970 of iterations is not reliable. Also record the place of the extra zero
971 check. */
972 bitmap_clear (wont_exit);
973 if (!desc->noloop_assumptions)
974 bitmap_set_bit (map: wont_exit, bitno: 1);
975 ezc_swtch = loop_preheader_edge (loop)->src;
976 ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
977 1, wont_exit, desc->out_edge,
978 &remove_edges,
979 DLTHE_FLAG_UPDATE_FREQ);
980 gcc_assert (ok);
981 }
982
983 /* Record the place where switch will be built for preconditioning. */
984 swtch = split_edge (loop_preheader_edge (loop));
985
986 /* Compute count increments for each switch block and initialize
987 innermost switch block. Switch blocks and peeled loop copies are built
988 from innermost outward. */
989 iter_count = new_count = swtch->count / (max_unroll + 1);
990 swtch->count = new_count;
991
992 for (i = 0; i < n_peel; i++)
993 {
994 /* Peel the copy. */
995 bitmap_clear (wont_exit);
996 if (i != n_peel - 1 || !last_may_exit)
997 bitmap_set_bit (map: wont_exit, bitno: 1);
998 ok = duplicate_loop_body_to_header_edge (loop, loop_preheader_edge (loop),
999 1, wont_exit, desc->out_edge,
1000 &remove_edges,
1001 DLTHE_FLAG_UPDATE_FREQ);
1002 gcc_assert (ok);
1003
1004 /* Create item for switch. */
1005 unsigned j = n_peel - i - (extra_zero_check ? 0 : 1);
1006 p = profile_probability::always () / (i + 2);
1007
1008 preheader = split_edge (loop_preheader_edge (loop));
1009 /* Add in count of edge from switch block. */
1010 preheader->count += iter_count;
1011 branch_code = compare_and_jump_seq (op0: copy_rtx (niter),
1012 op1: gen_int_mode (j, desc->mode), comp: EQ,
1013 label: block_label (preheader), prob: p, NULL);
1014
1015 /* We rely on the fact that the compare and jump cannot be optimized out,
1016 and hence the cfg we create is correct. */
1017 gcc_assert (branch_code != NULL_RTX);
1018
1019 swtch = split_edge_and_insert (e: single_pred_edge (bb: swtch), insns: branch_code);
1020 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1021 single_succ_edge (bb: swtch)->probability = p.invert ();
1022 new_count += iter_count;
1023 swtch->count = new_count;
1024 e = make_edge (swtch, preheader,
1025 single_succ_edge (bb: swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1026 e->probability = p;
1027 }
1028
1029 if (extra_zero_check)
1030 {
1031 /* Add branch for zero iterations. */
1032 p = profile_probability::always () / (max_unroll + 1);
1033 swtch = ezc_swtch;
1034 preheader = split_edge (loop_preheader_edge (loop));
1035 /* Recompute count adjustments since initial peel copy may
1036 have exited and reduced those values that were computed above. */
1037 iter_count = swtch->count / (max_unroll + 1);
1038 /* Add in count of edge from switch block. */
1039 preheader->count += iter_count;
1040 branch_code = compare_and_jump_seq (op0: copy_rtx (niter), const0_rtx, comp: EQ,
1041 label: block_label (preheader), prob: p,
1042 NULL);
1043 gcc_assert (branch_code != NULL_RTX);
1044
1045 swtch = split_edge_and_insert (e: single_succ_edge (bb: swtch), insns: branch_code);
1046 set_immediate_dominator (CDI_DOMINATORS, preheader, swtch);
1047 single_succ_edge (bb: swtch)->probability = p.invert ();
1048 e = make_edge (swtch, preheader,
1049 single_succ_edge (bb: swtch)->flags & EDGE_IRREDUCIBLE_LOOP);
1050 e->probability = p;
1051 }
1052
1053 /* Recount dominators for outer blocks. */
1054 iterate_fix_dominators (CDI_DOMINATORS, dom_bbs, false);
1055
1056 /* And unroll loop. */
1057
1058 bitmap_ones (wont_exit);
1059 bitmap_clear_bit (map: wont_exit, bitno: may_exit_copy);
1060 opt_info_start_duplication (opt_info);
1061
1062 ok = duplicate_loop_body_to_header_edge (
1063 loop, loop_latch_edge (loop), max_unroll, wont_exit, desc->out_edge,
1064 &remove_edges,
1065 DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
1066 gcc_assert (ok);
1067
1068 if (opt_info)
1069 {
1070 apply_opt_in_copies (opt_info, max_unroll, true, true);
1071 free_opt_info (opt_info);
1072 }
1073
1074 if (exit_at_end)
1075 {
1076 basic_block exit_block = get_bb_copy (desc->in_edge->src);
1077 /* Find a new in and out edge; they are in the last copy we have
1078 made. */
1079
1080 if (EDGE_SUCC (exit_block, 0)->dest == desc->out_edge->dest)
1081 {
1082 desc->out_edge = EDGE_SUCC (exit_block, 0);
1083 desc->in_edge = EDGE_SUCC (exit_block, 1);
1084 }
1085 else
1086 {
1087 desc->out_edge = EDGE_SUCC (exit_block, 1);
1088 desc->in_edge = EDGE_SUCC (exit_block, 0);
1089 }
1090 }
1091
1092 /* Remove the edges. */
1093 FOR_EACH_VEC_ELT (remove_edges, i, e)
1094 remove_path (e);
1095
1096 /* We must be careful when updating the number of iterations due to
1097 preconditioning and the fact that the value must be valid at entry
1098 of the loop. After passing through the above code, we see that
1099 the correct new number of iterations is this: */
1100 gcc_assert (!desc->const_iter);
1101 desc->niter_expr =
1102 simplify_gen_binary (code: UDIV, mode: desc->mode, op0: old_niter,
1103 op1: gen_int_mode (max_unroll + 1, desc->mode));
1104 loop->nb_iterations_upper_bound
1105 = wi::udiv_trunc (x: loop->nb_iterations_upper_bound, y: max_unroll + 1);
1106 if (loop->any_estimate)
1107 loop->nb_iterations_estimate
1108 = wi::udiv_trunc (x: loop->nb_iterations_estimate, y: max_unroll + 1);
1109 if (loop->any_likely_upper_bound)
1110 loop->nb_iterations_likely_upper_bound
1111 = wi::udiv_trunc (x: loop->nb_iterations_likely_upper_bound, y: max_unroll + 1);
1112 if (exit_at_end)
1113 {
1114 desc->niter_expr =
1115 simplify_gen_binary (code: MINUS, mode: desc->mode, op0: desc->niter_expr, const1_rtx);
1116 desc->noloop_assumptions = NULL_RTX;
1117 --loop->nb_iterations_upper_bound;
1118 if (loop->any_estimate
1119 && loop->nb_iterations_estimate != 0)
1120 --loop->nb_iterations_estimate;
1121 else
1122 loop->any_estimate = false;
1123 if (loop->any_likely_upper_bound
1124 && loop->nb_iterations_likely_upper_bound != 0)
1125 --loop->nb_iterations_likely_upper_bound;
1126 else
1127 loop->any_likely_upper_bound = false;
1128 }
1129
1130 if (dump_file)
1131 fprintf (stream: dump_file,
1132 format: ";; Unrolled loop %d times, counting # of iterations "
1133 "in runtime, %i insns\n",
1134 max_unroll, num_loop_insns (loop));
1135}
1136
1137/* Decide whether to unroll LOOP stupidly and how much. */
1138static void
1139decide_unroll_stupid (class loop *loop, int flags)
1140{
1141 unsigned nunroll, nunroll_by_av, i;
1142 class niter_desc *desc;
1143 widest_int iterations;
1144
1145 /* If we were not asked to unroll this loop, just return back silently. */
1146 if (!(flags & UAP_UNROLL_ALL) && !loop->unroll)
1147 return;
1148
1149 if (dump_enabled_p ())
1150 dump_printf (MSG_NOTE, "considering unrolling loop stupidly\n");
1151
1152 /* nunroll = total number of copies of the original loop body in
1153 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1154 nunroll = param_max_unrolled_insns / loop->ninsns;
1155 nunroll_by_av
1156 = param_max_average_unrolled_insns / loop->av_ninsns;
1157 if (nunroll > nunroll_by_av)
1158 nunroll = nunroll_by_av;
1159 if (nunroll > (unsigned) param_max_unroll_times)
1160 nunroll = param_max_unroll_times;
1161
1162 if (targetm.loop_unroll_adjust)
1163 nunroll = targetm.loop_unroll_adjust (nunroll, loop);
1164
1165 if (loop->unroll > 0 && loop->unroll < USHRT_MAX)
1166 nunroll = loop->unroll;
1167
1168 /* Skip big loops. */
1169 if (nunroll <= 1)
1170 {
1171 if (dump_file)
1172 fprintf (stream: dump_file, format: ";; Not considering loop, is too big\n");
1173 return;
1174 }
1175
1176 /* Check for simple loops. */
1177 desc = get_simple_loop_desc (loop);
1178
1179 /* Check simpleness. */
1180 if (desc->simple_p && !desc->assumptions)
1181 {
1182 if (dump_file)
1183 fprintf (stream: dump_file, format: ";; Loop is simple\n");
1184 return;
1185 }
1186
1187 /* Do not unroll loops with branches inside -- it increases number
1188 of mispredicts.
1189 TODO: this heuristic needs tunning; call inside the loop body
1190 is also relatively good reason to not unroll. */
1191 if (num_loop_branches (loop) > 1)
1192 {
1193 if (dump_file)
1194 fprintf (stream: dump_file, format: ";; Not unrolling, contains branches\n");
1195 return;
1196 }
1197
1198 /* Check whether the loop rolls. */
1199 if ((get_estimated_loop_iterations (loop, nit: &iterations)
1200 || get_likely_max_loop_iterations (loop, nit: &iterations))
1201 && wi::ltu_p (x: iterations, y: 2 * nunroll))
1202 {
1203 if (dump_file)
1204 fprintf (stream: dump_file, format: ";; Not unrolling loop, doesn't roll\n");
1205 return;
1206 }
1207
1208 /* Success. Now force nunroll to be power of 2, as it seems that this
1209 improves results (partially because of better alignments, partially
1210 because of some dark magic). */
1211 for (i = 1; 2 * i <= nunroll; i *= 2)
1212 continue;
1213
1214 loop->lpt_decision.decision = LPT_UNROLL_STUPID;
1215 loop->lpt_decision.times = i - 1;
1216}
1217
1218/* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1219
1220 while (cond)
1221 body;
1222
1223 ==> (LOOP->LPT_DECISION.TIMES == 3)
1224
1225 while (cond)
1226 {
1227 body;
1228 if (!cond) break;
1229 body;
1230 if (!cond) break;
1231 body;
1232 if (!cond) break;
1233 body;
1234 }
1235 */
1236static void
1237unroll_loop_stupid (class loop *loop)
1238{
1239 unsigned nunroll = loop->lpt_decision.times;
1240 class niter_desc *desc = get_simple_loop_desc (loop);
1241 struct opt_info *opt_info = NULL;
1242 bool ok;
1243
1244 if (flag_split_ivs_in_unroller
1245 || flag_variable_expansion_in_unroller)
1246 opt_info = analyze_insns_in_loop (loop);
1247
1248 auto_sbitmap wont_exit (nunroll + 1);
1249 bitmap_clear (wont_exit);
1250 opt_info_start_duplication (opt_info);
1251
1252 ok = duplicate_loop_body_to_header_edge (
1253 loop, loop_latch_edge (loop), nunroll, wont_exit, NULL, NULL,
1254 DLTHE_FLAG_UPDATE_FREQ | (opt_info ? DLTHE_RECORD_COPY_NUMBER : 0));
1255 gcc_assert (ok);
1256
1257 if (opt_info)
1258 {
1259 apply_opt_in_copies (opt_info, nunroll, true, true);
1260 free_opt_info (opt_info);
1261 }
1262
1263 if (desc->simple_p)
1264 {
1265 /* We indeed may get here provided that there are nontrivial assumptions
1266 for a loop to be really simple. We could update the counts, but the
1267 problem is that we are unable to decide which exit will be taken
1268 (not really true in case the number of iterations is constant,
1269 but no one will do anything with this information, so we do not
1270 worry about it). */
1271 desc->simple_p = false;
1272 }
1273
1274 if (dump_file)
1275 fprintf (stream: dump_file, format: ";; Unrolled loop %d times, %i insns\n",
1276 nunroll, num_loop_insns (loop));
1277}
1278
1279/* Returns true if REG is referenced in one nondebug insn in LOOP.
1280 Set *DEBUG_USES to the number of debug insns that reference the
1281 variable. */
1282
1283static bool
1284referenced_in_one_insn_in_loop_p (class loop *loop, rtx reg,
1285 int *debug_uses)
1286{
1287 basic_block *body, bb;
1288 unsigned i;
1289 int count_ref = 0;
1290 rtx_insn *insn;
1291
1292 body = get_loop_body (loop);
1293 for (i = 0; i < loop->num_nodes; i++)
1294 {
1295 bb = body[i];
1296
1297 FOR_BB_INSNS (bb, insn)
1298 if (!rtx_referenced_p (reg, insn))
1299 continue;
1300 else if (DEBUG_INSN_P (insn))
1301 ++*debug_uses;
1302 else if (++count_ref > 1)
1303 break;
1304 }
1305 free (ptr: body);
1306 return (count_ref == 1);
1307}
1308
1309/* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1310
1311static void
1312reset_debug_uses_in_loop (class loop *loop, rtx reg, int debug_uses)
1313{
1314 basic_block *body, bb;
1315 unsigned i;
1316 rtx_insn *insn;
1317
1318 body = get_loop_body (loop);
1319 for (i = 0; debug_uses && i < loop->num_nodes; i++)
1320 {
1321 bb = body[i];
1322
1323 FOR_BB_INSNS (bb, insn)
1324 if (!DEBUG_INSN_P (insn) || !rtx_referenced_p (reg, insn))
1325 continue;
1326 else
1327 {
1328 validate_change (insn, &INSN_VAR_LOCATION_LOC (insn),
1329 gen_rtx_UNKNOWN_VAR_LOC (), 0);
1330 if (!--debug_uses)
1331 break;
1332 }
1333 }
1334 free (ptr: body);
1335}
1336
1337/* Determine whether INSN contains an accumulator
1338 which can be expanded into separate copies,
1339 one for each copy of the LOOP body.
1340
1341 for (i = 0 ; i < n; i++)
1342 sum += a[i];
1343
1344 ==>
1345
1346 sum += a[i]
1347 ....
1348 i = i+1;
1349 sum1 += a[i]
1350 ....
1351 i = i+1
1352 sum2 += a[i];
1353 ....
1354
1355 Return NULL if INSN contains no opportunity for expansion of accumulator.
1356 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1357 information and return a pointer to it.
1358*/
1359
1360static struct var_to_expand *
1361analyze_insn_to_expand_var (class loop *loop, rtx_insn *insn)
1362{
1363 rtx set, dest, src;
1364 struct var_to_expand *ves;
1365 unsigned accum_pos;
1366 enum rtx_code code;
1367 int debug_uses = 0;
1368
1369 set = single_set (insn);
1370 if (!set)
1371 return NULL;
1372
1373 dest = SET_DEST (set);
1374 src = SET_SRC (set);
1375 code = GET_CODE (src);
1376
1377 if (code != PLUS && code != MINUS && code != MULT && code != FMA)
1378 return NULL;
1379
1380 if (FLOAT_MODE_P (GET_MODE (dest)))
1381 {
1382 if (!flag_associative_math)
1383 return NULL;
1384 /* In the case of FMA, we're also changing the rounding. */
1385 if (code == FMA && !flag_unsafe_math_optimizations)
1386 return NULL;
1387 }
1388
1389 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1390 in MD. But if there is no optab to generate the insn, we cannot
1391 perform the variable expansion. This can happen if an MD provides
1392 an insn but not a named pattern to generate it, for example to avoid
1393 producing code that needs additional mode switches like for x87/mmx.
1394
1395 So we check have_insn_for which looks for an optab for the operation
1396 in SRC. If it doesn't exist, we can't perform the expansion even
1397 though INSN is valid. */
1398 if (!have_insn_for (code, GET_MODE (src)))
1399 return NULL;
1400
1401 if (!REG_P (dest)
1402 && !(GET_CODE (dest) == SUBREG
1403 && REG_P (SUBREG_REG (dest))))
1404 return NULL;
1405
1406 /* Find the accumulator use within the operation. */
1407 if (code == FMA)
1408 {
1409 /* We only support accumulation via FMA in the ADD position. */
1410 if (!rtx_equal_p (dest, XEXP (src, 2)))
1411 return NULL;
1412 accum_pos = 2;
1413 }
1414 else if (rtx_equal_p (dest, XEXP (src, 0)))
1415 accum_pos = 0;
1416 else if (rtx_equal_p (dest, XEXP (src, 1)))
1417 {
1418 /* The method of expansion that we are using; which includes the
1419 initialization of the expansions with zero and the summation of
1420 the expansions at the end of the computation will yield wrong
1421 results for (x = something - x) thus avoid using it in that case. */
1422 if (code == MINUS)
1423 return NULL;
1424 accum_pos = 1;
1425 }
1426 else
1427 return NULL;
1428
1429 /* It must not otherwise be used. */
1430 if (code == FMA)
1431 {
1432 if (rtx_referenced_p (dest, XEXP (src, 0))
1433 || rtx_referenced_p (dest, XEXP (src, 1)))
1434 return NULL;
1435 }
1436 else if (rtx_referenced_p (dest, XEXP (src, 1 - accum_pos)))
1437 return NULL;
1438
1439 /* It must be used in exactly one insn. */
1440 if (!referenced_in_one_insn_in_loop_p (loop, reg: dest, debug_uses: &debug_uses))
1441 return NULL;
1442
1443 if (dump_file)
1444 {
1445 fprintf (stream: dump_file, format: "\n;; Expanding Accumulator ");
1446 print_rtl (dump_file, dest);
1447 fprintf (stream: dump_file, format: "\n");
1448 }
1449
1450 if (debug_uses)
1451 /* Instead of resetting the debug insns, we could replace each
1452 debug use in the loop with the sum or product of all expanded
1453 accumulators. Since we'll only know of all expansions at the
1454 end, we'd have to keep track of which vars_to_expand a debug
1455 insn in the loop references, take note of each copy of the
1456 debug insn during unrolling, and when it's all done, compute
1457 the sum or product of each variable and adjust the original
1458 debug insn and each copy thereof. What a pain! */
1459 reset_debug_uses_in_loop (loop, reg: dest, debug_uses);
1460
1461 /* Record the accumulator to expand. */
1462 ves = XNEW (struct var_to_expand);
1463 ves->insn = insn;
1464 ves->reg = copy_rtx (dest);
1465 ves->var_expansions.create (nelems: 1);
1466 ves->next = NULL;
1467 ves->op = GET_CODE (src);
1468 ves->expansion_count = 0;
1469 ves->reuse_expansion = 0;
1470 return ves;
1471}
1472
1473/* Determine whether there is an induction variable in INSN that
1474 we would like to split during unrolling.
1475
1476 I.e. replace
1477
1478 i = i + 1;
1479 ...
1480 i = i + 1;
1481 ...
1482 i = i + 1;
1483 ...
1484
1485 type chains by
1486
1487 i0 = i + 1
1488 ...
1489 i = i0 + 1
1490 ...
1491 i = i0 + 2
1492 ...
1493
1494 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1495 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1496 pointer to it. */
1497
1498static struct iv_to_split *
1499analyze_iv_to_split_insn (rtx_insn *insn)
1500{
1501 rtx set, dest;
1502 class rtx_iv iv;
1503 struct iv_to_split *ivts;
1504 scalar_int_mode mode;
1505 bool ok;
1506
1507 /* For now we just split the basic induction variables. Later this may be
1508 extended for example by selecting also addresses of memory references. */
1509 set = single_set (insn);
1510 if (!set)
1511 return NULL;
1512
1513 dest = SET_DEST (set);
1514 if (!REG_P (dest) || !is_a <scalar_int_mode> (GET_MODE (dest), result: &mode))
1515 return NULL;
1516
1517 if (!biv_p (insn, mode, dest))
1518 return NULL;
1519
1520 ok = iv_analyze_result (insn, dest, &iv);
1521
1522 /* This used to be an assert under the assumption that if biv_p returns
1523 true that iv_analyze_result must also return true. However, that
1524 assumption is not strictly correct as evidenced by pr25569.
1525
1526 Returning NULL when iv_analyze_result returns false is safe and
1527 avoids the problems in pr25569 until the iv_analyze_* routines
1528 can be fixed, which is apparently hard and time consuming
1529 according to their author. */
1530 if (! ok)
1531 return NULL;
1532
1533 if (iv.step == const0_rtx
1534 || iv.mode != iv.extend_mode)
1535 return NULL;
1536
1537 /* Record the insn to split. */
1538 ivts = XNEW (struct iv_to_split);
1539 ivts->insn = insn;
1540 ivts->orig_var = dest;
1541 ivts->base_var = NULL_RTX;
1542 ivts->step = iv.step;
1543 ivts->next = NULL;
1544
1545 return ivts;
1546}
1547
1548/* Determines which of insns in LOOP can be optimized.
1549 Return a OPT_INFO struct with the relevant hash tables filled
1550 with all insns to be optimized. The FIRST_NEW_BLOCK field
1551 is undefined for the return value. */
1552
1553static struct opt_info *
1554analyze_insns_in_loop (class loop *loop)
1555{
1556 basic_block *body, bb;
1557 unsigned i;
1558 struct opt_info *opt_info = XCNEW (struct opt_info);
1559 rtx_insn *insn;
1560 struct iv_to_split *ivts = NULL;
1561 struct var_to_expand *ves = NULL;
1562 iv_to_split **slot1;
1563 var_to_expand **slot2;
1564 auto_vec<edge> edges = get_loop_exit_edges (loop);
1565 edge exit;
1566 bool can_apply = false;
1567
1568 iv_analysis_loop_init (loop);
1569
1570 body = get_loop_body (loop);
1571
1572 if (flag_split_ivs_in_unroller)
1573 {
1574 opt_info->insns_to_split
1575 = new hash_table<iv_split_hasher> (5 * loop->num_nodes);
1576 opt_info->iv_to_split_head = NULL;
1577 opt_info->iv_to_split_tail = &opt_info->iv_to_split_head;
1578 }
1579
1580 /* Record the loop exit bb and loop preheader before the unrolling. */
1581 opt_info->loop_preheader = loop_preheader_edge (loop)->src;
1582
1583 if (edges.length () == 1)
1584 {
1585 exit = edges[0];
1586 if (!(exit->flags & EDGE_COMPLEX))
1587 {
1588 opt_info->loop_exit = split_edge (exit);
1589 can_apply = true;
1590 }
1591 }
1592
1593 if (flag_variable_expansion_in_unroller
1594 && can_apply)
1595 {
1596 opt_info->insns_with_var_to_expand
1597 = new hash_table<var_expand_hasher> (5 * loop->num_nodes);
1598 opt_info->var_to_expand_head = NULL;
1599 opt_info->var_to_expand_tail = &opt_info->var_to_expand_head;
1600 }
1601
1602 for (i = 0; i < loop->num_nodes; i++)
1603 {
1604 bb = body[i];
1605 if (!dominated_by_p (CDI_DOMINATORS, loop->latch, bb))
1606 continue;
1607
1608 FOR_BB_INSNS (bb, insn)
1609 {
1610 if (!INSN_P (insn))
1611 continue;
1612
1613 if (opt_info->insns_to_split)
1614 ivts = analyze_iv_to_split_insn (insn);
1615
1616 if (ivts)
1617 {
1618 slot1 = opt_info->insns_to_split->find_slot (value: ivts, insert: INSERT);
1619 gcc_assert (*slot1 == NULL);
1620 *slot1 = ivts;
1621 *opt_info->iv_to_split_tail = ivts;
1622 opt_info->iv_to_split_tail = &ivts->next;
1623 continue;
1624 }
1625
1626 if (opt_info->insns_with_var_to_expand)
1627 ves = analyze_insn_to_expand_var (loop, insn);
1628
1629 if (ves)
1630 {
1631 slot2 = opt_info->insns_with_var_to_expand->find_slot (value: ves, insert: INSERT);
1632 gcc_assert (*slot2 == NULL);
1633 *slot2 = ves;
1634 *opt_info->var_to_expand_tail = ves;
1635 opt_info->var_to_expand_tail = &ves->next;
1636 }
1637 }
1638 }
1639
1640 free (ptr: body);
1641 return opt_info;
1642}
1643
1644/* Called just before loop duplication. Records start of duplicated area
1645 to OPT_INFO. */
1646
1647static void
1648opt_info_start_duplication (struct opt_info *opt_info)
1649{
1650 if (opt_info)
1651 opt_info->first_new_block = last_basic_block_for_fn (cfun);
1652}
1653
1654/* Determine the number of iterations between initialization of the base
1655 variable and the current copy (N_COPY). N_COPIES is the total number
1656 of newly created copies. UNROLLING is true if we are unrolling
1657 (not peeling) the loop. */
1658
1659static unsigned
1660determine_split_iv_delta (unsigned n_copy, unsigned n_copies, bool unrolling)
1661{
1662 if (unrolling)
1663 {
1664 /* If we are unrolling, initialization is done in the original loop
1665 body (number 0). */
1666 return n_copy;
1667 }
1668 else
1669 {
1670 /* If we are peeling, the copy in that the initialization occurs has
1671 number 1. The original loop (number 0) is the last. */
1672 if (n_copy)
1673 return n_copy - 1;
1674 else
1675 return n_copies;
1676 }
1677}
1678
1679/* Allocate basic variable for the induction variable chain. */
1680
1681static void
1682allocate_basic_variable (struct iv_to_split *ivts)
1683{
1684 rtx expr = SET_SRC (single_set (ivts->insn));
1685
1686 ivts->base_var = gen_reg_rtx (GET_MODE (expr));
1687}
1688
1689/* Insert initialization of basic variable of IVTS before INSN, taking
1690 the initial value from INSN. */
1691
1692static void
1693insert_base_initialization (struct iv_to_split *ivts, rtx_insn *insn)
1694{
1695 rtx expr = copy_rtx (SET_SRC (single_set (insn)));
1696 rtx_insn *seq;
1697
1698 start_sequence ();
1699 expr = force_operand (expr, ivts->base_var);
1700 if (expr != ivts->base_var)
1701 emit_move_insn (ivts->base_var, expr);
1702 seq = get_insns ();
1703 end_sequence ();
1704
1705 emit_insn_before (seq, insn);
1706}
1707
1708/* Replace the use of induction variable described in IVTS in INSN
1709 by base variable + DELTA * step. */
1710
1711static void
1712split_iv (struct iv_to_split *ivts, rtx_insn *insn, unsigned delta)
1713{
1714 rtx expr, *loc, incr, var;
1715 rtx_insn *seq;
1716 machine_mode mode = GET_MODE (ivts->base_var);
1717 rtx src, dest, set;
1718
1719 /* Construct base + DELTA * step. */
1720 if (!delta)
1721 expr = ivts->base_var;
1722 else
1723 {
1724 incr = simplify_gen_binary (code: MULT, mode,
1725 op0: copy_rtx (ivts->step),
1726 op1: gen_int_mode (delta, mode));
1727 expr = simplify_gen_binary (code: PLUS, GET_MODE (ivts->base_var),
1728 op0: ivts->base_var, op1: incr);
1729 }
1730
1731 /* Figure out where to do the replacement. */
1732 loc = &SET_SRC (single_set (insn));
1733
1734 /* If we can make the replacement right away, we're done. */
1735 if (validate_change (insn, loc, expr, 0))
1736 return;
1737
1738 /* Otherwise, force EXPR into a register and try again. */
1739 start_sequence ();
1740 var = gen_reg_rtx (mode);
1741 expr = force_operand (expr, var);
1742 if (expr != var)
1743 emit_move_insn (var, expr);
1744 seq = get_insns ();
1745 end_sequence ();
1746 emit_insn_before (seq, insn);
1747
1748 if (validate_change (insn, loc, var, 0))
1749 return;
1750
1751 /* The last chance. Try recreating the assignment in insn
1752 completely from scratch. */
1753 set = single_set (insn);
1754 gcc_assert (set);
1755
1756 start_sequence ();
1757 *loc = var;
1758 src = copy_rtx (SET_SRC (set));
1759 dest = copy_rtx (SET_DEST (set));
1760 src = force_operand (src, dest);
1761 if (src != dest)
1762 emit_move_insn (dest, src);
1763 seq = get_insns ();
1764 end_sequence ();
1765
1766 emit_insn_before (seq, insn);
1767 delete_insn (insn);
1768}
1769
1770
1771/* Return one expansion of the accumulator recorded in struct VE. */
1772
1773static rtx
1774get_expansion (struct var_to_expand *ve)
1775{
1776 rtx reg;
1777
1778 if (ve->reuse_expansion == 0)
1779 reg = ve->reg;
1780 else
1781 reg = ve->var_expansions[ve->reuse_expansion - 1];
1782
1783 if (ve->var_expansions.length () == (unsigned) ve->reuse_expansion)
1784 ve->reuse_expansion = 0;
1785 else
1786 ve->reuse_expansion++;
1787
1788 return reg;
1789}
1790
1791
1792/* Given INSN replace the uses of the accumulator recorded in VE
1793 with a new register. */
1794
1795static void
1796expand_var_during_unrolling (struct var_to_expand *ve, rtx_insn *insn)
1797{
1798 rtx new_reg, set;
1799 bool really_new_expansion = false;
1800
1801 set = single_set (insn);
1802 gcc_assert (set);
1803
1804 /* Generate a new register only if the expansion limit has not been
1805 reached. Else reuse an already existing expansion. */
1806 if (param_max_variable_expansions > ve->expansion_count)
1807 {
1808 really_new_expansion = true;
1809 new_reg = gen_reg_rtx (GET_MODE (ve->reg));
1810 }
1811 else
1812 new_reg = get_expansion (ve);
1813
1814 validate_replace_rtx_group (SET_DEST (set), new_reg, insn);
1815 if (apply_change_group ())
1816 if (really_new_expansion)
1817 {
1818 ve->var_expansions.safe_push (obj: new_reg);
1819 ve->expansion_count++;
1820 }
1821}
1822
1823/* Initialize the variable expansions in loop preheader. PLACE is the
1824 loop-preheader basic block where the initialization of the
1825 expansions should take place. The expansions are initialized with
1826 (-0) when the operation is plus or minus to honor sign zero. This
1827 way we can prevent cases where the sign of the final result is
1828 effected by the sign of the expansion. Here is an example to
1829 demonstrate this:
1830
1831 for (i = 0 ; i < n; i++)
1832 sum += something;
1833
1834 ==>
1835
1836 sum += something
1837 ....
1838 i = i+1;
1839 sum1 += something
1840 ....
1841 i = i+1
1842 sum2 += something;
1843 ....
1844
1845 When SUM is initialized with -zero and SOMETHING is also -zero; the
1846 final result of sum should be -zero thus the expansions sum1 and sum2
1847 should be initialized with -zero as well (otherwise we will get +zero
1848 as the final result). */
1849
1850static void
1851insert_var_expansion_initialization (struct var_to_expand *ve,
1852 basic_block place)
1853{
1854 rtx_insn *seq;
1855 rtx var, zero_init;
1856 unsigned i;
1857 machine_mode mode = GET_MODE (ve->reg);
1858 bool honor_signed_zero_p = HONOR_SIGNED_ZEROS (mode);
1859
1860 if (ve->var_expansions.length () == 0)
1861 return;
1862
1863 start_sequence ();
1864 switch (ve->op)
1865 {
1866 case FMA:
1867 /* Note that we only accumulate FMA via the ADD operand. */
1868 case PLUS:
1869 case MINUS:
1870 FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1871 {
1872 if (honor_signed_zero_p)
1873 zero_init = simplify_gen_unary (code: NEG, mode, CONST0_RTX (mode), op_mode: mode);
1874 else
1875 zero_init = CONST0_RTX (mode);
1876 emit_move_insn (var, zero_init);
1877 }
1878 break;
1879
1880 case MULT:
1881 FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1882 {
1883 zero_init = CONST1_RTX (GET_MODE (var));
1884 emit_move_insn (var, zero_init);
1885 }
1886 break;
1887
1888 default:
1889 gcc_unreachable ();
1890 }
1891
1892 seq = get_insns ();
1893 end_sequence ();
1894
1895 emit_insn_after (seq, BB_END (place));
1896}
1897
1898/* Combine the variable expansions at the loop exit. PLACE is the
1899 loop exit basic block where the summation of the expansions should
1900 take place. */
1901
1902static void
1903combine_var_copies_in_loop_exit (struct var_to_expand *ve, basic_block place)
1904{
1905 rtx sum = ve->reg;
1906 rtx expr, var;
1907 rtx_insn *seq, *insn;
1908 unsigned i;
1909
1910 if (ve->var_expansions.length () == 0)
1911 return;
1912
1913 /* ve->reg might be SUBREG or some other non-shareable RTL, and we use
1914 it both here and as the destination of the assignment. */
1915 sum = copy_rtx (sum);
1916 start_sequence ();
1917 switch (ve->op)
1918 {
1919 case FMA:
1920 /* Note that we only accumulate FMA via the ADD operand. */
1921 case PLUS:
1922 case MINUS:
1923 FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1924 sum = simplify_gen_binary (code: PLUS, GET_MODE (ve->reg), op0: var, op1: sum);
1925 break;
1926
1927 case MULT:
1928 FOR_EACH_VEC_ELT (ve->var_expansions, i, var)
1929 sum = simplify_gen_binary (code: MULT, GET_MODE (ve->reg), op0: var, op1: sum);
1930 break;
1931
1932 default:
1933 gcc_unreachable ();
1934 }
1935
1936 expr = force_operand (sum, ve->reg);
1937 if (expr != ve->reg)
1938 emit_move_insn (ve->reg, expr);
1939 seq = get_insns ();
1940 end_sequence ();
1941
1942 insn = BB_HEAD (place);
1943 while (!NOTE_INSN_BASIC_BLOCK_P (insn))
1944 insn = NEXT_INSN (insn);
1945
1946 emit_insn_after (seq, insn);
1947}
1948
1949/* Strip away REG_EQUAL notes for IVs we're splitting.
1950
1951 Updating REG_EQUAL notes for IVs we split is tricky: We
1952 cannot tell until after unrolling, DF-rescanning, and liveness
1953 updating, whether an EQ_USE is reached by the split IV while
1954 the IV reg is still live. See PR55006.
1955
1956 ??? We cannot use remove_reg_equal_equiv_notes_for_regno,
1957 because RTL loop-iv requires us to defer rescanning insns and
1958 any notes attached to them. So resort to old techniques... */
1959
1960static void
1961maybe_strip_eq_note_for_split_iv (struct opt_info *opt_info, rtx_insn *insn)
1962{
1963 struct iv_to_split *ivts;
1964 rtx note = find_reg_equal_equiv_note (insn);
1965 if (! note)
1966 return;
1967 for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
1968 if (reg_mentioned_p (ivts->orig_var, note))
1969 {
1970 remove_note (insn, note);
1971 return;
1972 }
1973}
1974
1975/* Apply loop optimizations in loop copies using the
1976 data which gathered during the unrolling. Structure
1977 OPT_INFO record that data.
1978
1979 UNROLLING is true if we unrolled (not peeled) the loop.
1980 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
1981 the loop (as it should happen in complete unrolling, but not in ordinary
1982 peeling of the loop). */
1983
1984static void
1985apply_opt_in_copies (struct opt_info *opt_info,
1986 unsigned n_copies, bool unrolling,
1987 bool rewrite_original_loop)
1988{
1989 unsigned i, delta;
1990 basic_block bb, orig_bb;
1991 rtx_insn *insn, *orig_insn, *next;
1992 struct iv_to_split ivts_templ, *ivts;
1993 struct var_to_expand ve_templ, *ves;
1994
1995 /* Sanity check -- we need to put initialization in the original loop
1996 body. */
1997 gcc_assert (!unrolling || rewrite_original_loop);
1998
1999 /* Allocate the basic variables (i0). */
2000 if (opt_info->insns_to_split)
2001 for (ivts = opt_info->iv_to_split_head; ivts; ivts = ivts->next)
2002 allocate_basic_variable (ivts);
2003
2004 for (i = opt_info->first_new_block;
2005 i < (unsigned) last_basic_block_for_fn (cfun);
2006 i++)
2007 {
2008 bb = BASIC_BLOCK_FOR_FN (cfun, i);
2009 orig_bb = get_bb_original (bb);
2010
2011 /* bb->aux holds position in copy sequence initialized by
2012 duplicate_loop_body_to_header_edge. */
2013 delta = determine_split_iv_delta (n_copy: (size_t)bb->aux, n_copies,
2014 unrolling);
2015 bb->aux = 0;
2016 orig_insn = BB_HEAD (orig_bb);
2017 FOR_BB_INSNS_SAFE (bb, insn, next)
2018 {
2019 if (!INSN_P (insn)
2020 || (DEBUG_BIND_INSN_P (insn)
2021 && INSN_VAR_LOCATION_DECL (insn)
2022 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn)) == LABEL_DECL))
2023 continue;
2024
2025 while (!INSN_P (orig_insn)
2026 || (DEBUG_BIND_INSN_P (orig_insn)
2027 && INSN_VAR_LOCATION_DECL (orig_insn)
2028 && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn))
2029 == LABEL_DECL)))
2030 orig_insn = NEXT_INSN (insn: orig_insn);
2031
2032 ivts_templ.insn = orig_insn;
2033 ve_templ.insn = orig_insn;
2034
2035 /* Apply splitting iv optimization. */
2036 if (opt_info->insns_to_split)
2037 {
2038 maybe_strip_eq_note_for_split_iv (opt_info, insn);
2039
2040 ivts = opt_info->insns_to_split->find (value: &ivts_templ);
2041
2042 if (ivts)
2043 {
2044 gcc_assert (GET_CODE (PATTERN (insn))
2045 == GET_CODE (PATTERN (orig_insn)));
2046
2047 if (!delta)
2048 insert_base_initialization (ivts, insn);
2049 split_iv (ivts, insn, delta);
2050 }
2051 }
2052 /* Apply variable expansion optimization. */
2053 if (unrolling && opt_info->insns_with_var_to_expand)
2054 {
2055 ves = (struct var_to_expand *)
2056 opt_info->insns_with_var_to_expand->find (value: &ve_templ);
2057 if (ves)
2058 {
2059 gcc_assert (GET_CODE (PATTERN (insn))
2060 == GET_CODE (PATTERN (orig_insn)));
2061 expand_var_during_unrolling (ve: ves, insn);
2062 }
2063 }
2064 orig_insn = NEXT_INSN (insn: orig_insn);
2065 }
2066 }
2067
2068 if (!rewrite_original_loop)
2069 return;
2070
2071 /* Initialize the variable expansions in the loop preheader
2072 and take care of combining them at the loop exit. */
2073 if (opt_info->insns_with_var_to_expand)
2074 {
2075 for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2076 insert_var_expansion_initialization (ve: ves, place: opt_info->loop_preheader);
2077 for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2078 combine_var_copies_in_loop_exit (ve: ves, place: opt_info->loop_exit);
2079 }
2080
2081 /* Rewrite also the original loop body. Find them as originals of the blocks
2082 in the last copied iteration, i.e. those that have
2083 get_bb_copy (get_bb_original (bb)) == bb. */
2084 for (i = opt_info->first_new_block;
2085 i < (unsigned) last_basic_block_for_fn (cfun);
2086 i++)
2087 {
2088 bb = BASIC_BLOCK_FOR_FN (cfun, i);
2089 orig_bb = get_bb_original (bb);
2090 if (get_bb_copy (orig_bb) != bb)
2091 continue;
2092
2093 delta = determine_split_iv_delta (n_copy: 0, n_copies, unrolling);
2094 for (orig_insn = BB_HEAD (orig_bb);
2095 orig_insn != NEXT_INSN (BB_END (bb));
2096 orig_insn = next)
2097 {
2098 next = NEXT_INSN (insn: orig_insn);
2099
2100 if (!INSN_P (orig_insn))
2101 continue;
2102
2103 ivts_templ.insn = orig_insn;
2104 if (opt_info->insns_to_split)
2105 {
2106 maybe_strip_eq_note_for_split_iv (opt_info, insn: orig_insn);
2107
2108 ivts = (struct iv_to_split *)
2109 opt_info->insns_to_split->find (value: &ivts_templ);
2110 if (ivts)
2111 {
2112 if (!delta)
2113 insert_base_initialization (ivts, insn: orig_insn);
2114 split_iv (ivts, insn: orig_insn, delta);
2115 continue;
2116 }
2117 }
2118
2119 }
2120 }
2121}
2122
2123/* Release OPT_INFO. */
2124
2125static void
2126free_opt_info (struct opt_info *opt_info)
2127{
2128 delete opt_info->insns_to_split;
2129 opt_info->insns_to_split = NULL;
2130 if (opt_info->insns_with_var_to_expand)
2131 {
2132 struct var_to_expand *ves;
2133
2134 for (ves = opt_info->var_to_expand_head; ves; ves = ves->next)
2135 ves->var_expansions.release ();
2136 delete opt_info->insns_with_var_to_expand;
2137 opt_info->insns_with_var_to_expand = NULL;
2138 }
2139 free (ptr: opt_info);
2140}
2141

source code of gcc/loop-unroll.cc