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