2 Copyright (C) 2002-2021 Free Software Foundation, Inc.
4 This file is part of GCC.
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
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
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/>. */
22 #include "coretypes.h"
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.
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.
60 There is a lot of parameters (defined and described in params.def) that
61 control how much we unroll.
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 %.
68 /* Information about induction variables to split. */
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. */
80 /* Information about accumulators to expand. */
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
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]. */
97 /* Hashtable helper for iv_to_split. */
99 struct iv_split_hasher
: free_ptr_hash
<iv_to_split
>
101 static inline hashval_t
hash (const iv_to_split
*);
102 static inline bool equal (const iv_to_split
*, const iv_to_split
*);
106 /* A hash function for information about insns to split. */
109 iv_split_hasher::hash (const iv_to_split
*ivts
)
111 return (hashval_t
) INSN_UID (ivts
->insn
);
114 /* An equality functions for information about insns to split. */
117 iv_split_hasher::equal (const iv_to_split
*i1
, const iv_to_split
*i2
)
119 return i1
->insn
== i2
->insn
;
122 /* Hashtable helper for iv_to_split. */
124 struct var_expand_hasher
: free_ptr_hash
<var_to_expand
>
126 static inline hashval_t
hash (const var_to_expand
*);
127 static inline bool equal (const var_to_expand
*, const var_to_expand
*);
130 /* Return a hash for VES. */
133 var_expand_hasher::hash (const var_to_expand
*ves
)
135 return (hashval_t
) INSN_UID (ves
->insn
);
138 /* Return true if I1 and I2 refer to the same instruction. */
141 var_expand_hasher::equal (const var_to_expand
*i1
, const var_to_expand
*i2
)
143 return i1
->insn
== i2
->insn
;
146 /* Information about optimization applied in
147 the unrolled loop. */
151 hash_table
<iv_split_hasher
> *insns_to_split
; /* A hashtable of insns to
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
161 basic_block loop_exit
; /* The loop exit basic block. */
162 basic_block loop_preheader
; /* The loop preheader basic block. */
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
*,
182 static void combine_var_copies_in_loop_exit (struct var_to_expand
*,
184 static rtx
get_expansion (struct var_to_expand
*);
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. */
191 report_unroll (class loop
*loop
, dump_location_t locus
)
193 dump_flags_t report_flags
= MSG_OPTIMIZED_LOCATIONS
| TDF_DETAILS
;
195 if (loop
->lpt_decision
.decision
== LPT_NONE
)
198 if (!dump_enabled_p ())
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 ());
210 dump_printf (metadata
, "\n");
213 /* Decide whether unroll loops and how much. */
215 decide_unrolling (int flags
)
217 /* Scan the loops, inner ones first. */
218 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
220 loop
->lpt_decision
.decision
= LPT_NONE
;
221 dump_user_location_t locus
= get_loop_location (loop
);
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
);
228 if (loop
->unroll
== 1)
232 ";; Not unrolling loop, user didn't want it unrolled\n");
236 /* Do not peel cold areas. */
237 if (optimize_loop_for_size_p (loop
))
240 fprintf (dump_file
, ";; Not considering loop, cold area\n");
244 /* Can the loop be manipulated? */
245 if (!can_duplicate_loop_p (loop
))
249 ";; Not considering loop, cannot duplicate\n");
253 /* Skip non-innermost loops. */
257 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
261 loop
->ninsns
= num_loop_insns (loop
);
262 loop
->av_ninsns
= average_num_loop_insns (loop
);
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
);
271 report_unroll (loop
, locus
);
277 unroll_loops (int flags
)
279 bool changed
= false;
281 /* Now decide rest of unrolling. */
282 decide_unrolling (flags
);
284 /* Scan the loops, inner ones first. */
285 for (auto loop
: loops_list (cfun
, LI_FROM_INNERMOST
))
287 /* And perform the appropriate transformations. */
288 switch (loop
->lpt_decision
.decision
)
290 case LPT_UNROLL_CONSTANT
:
291 unroll_loop_constant_iterations (loop
);
294 case LPT_UNROLL_RUNTIME
:
295 unroll_loop_runtime_iterations (loop
);
298 case LPT_UNROLL_STUPID
:
299 unroll_loop_stupid (loop
);
311 calculate_dominance_info (CDI_DOMINATORS
);
312 fix_loop_structure (NULL
);
318 /* Check whether exit of the LOOP is at the end of loop body. */
321 loop_exit_at_end_p (class loop
*loop
)
323 class niter_desc
*desc
= get_simple_loop_desc (loop
);
326 /* We should never have conditional in latch block. */
327 gcc_assert (desc
->in_edge
->dest
!= loop
->header
);
329 if (desc
->in_edge
->dest
!= loop
->latch
)
332 /* Check that the latch is empty. */
333 FOR_BB_INSNS (loop
->latch
, insn
)
335 if (INSN_P (insn
) && active_insn_p (insn
))
342 /* Decide whether to unroll LOOP iterating constant number of times
346 decide_unroll_constant_iterations (class loop
*loop
, int flags
)
348 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
349 class niter_desc
*desc
;
350 widest_int iterations
;
352 /* If we were not asked to unroll this loop, just return back silently. */
353 if (!(flags
& UAP_UNROLL
) && !loop
->unroll
)
356 if (dump_enabled_p ())
357 dump_printf (MSG_NOTE
,
358 "considering unrolling loop with constant "
359 "number of iterations\n");
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
;
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
;
371 if (targetm
.loop_unroll_adjust
)
372 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
374 /* Skip big loops. */
378 fprintf (dump_file
, ";; Not considering loop, is too big\n");
382 /* Check for simple loops. */
383 desc
= get_simple_loop_desc (loop
);
385 /* Check number of iterations. */
386 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
390 ";; Unable to prove that the loop iterates constant times\n");
394 /* Check for an explicit unrolling factor. */
395 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
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)
402 fprintf (dump_file
, ";; Loop should have been peeled\n");
406 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
407 loop
->lpt_decision
.times
= loop
->unroll
- 1;
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
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
)))
422 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
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;
433 if (i
> desc
->niter
- 2)
436 for (; i
>= nunroll
- 1; i
--)
438 unsigned exit_mod
= desc
->niter
% (i
+ 1);
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;
448 if (n_copies
< best_copies
)
450 best_copies
= n_copies
;
455 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
456 loop
->lpt_decision
.times
= best_unroll
;
459 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
460 The transformation does this:
462 for (i = 0; i < 102; i++)
465 ==> (LOOP->LPT_DECISION.TIMES == 3)
479 unroll_loop_constant_iterations (class loop
*loop
)
481 unsigned HOST_WIDE_INT niter
;
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
;
493 /* Should not get here (such loop should be peeled instead). */
494 gcc_assert (niter
> max_unroll
+ 1);
496 exit_mod
= niter
% (max_unroll
+ 1);
498 auto_sbitmap
wont_exit (max_unroll
+ 2);
499 bitmap_ones (wont_exit
);
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
);
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. */
513 fprintf (dump_file
, ";; Condition at beginning of loop.\n");
515 /* Peel exit_mod iterations. */
516 bitmap_clear_bit (wont_exit
, 0);
517 if (desc
->noloop_assumptions
)
518 bitmap_clear_bit (wont_exit
, 1);
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));
530 if (opt_info
&& exit_mod
> 1)
531 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
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
;
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
;
545 loop
->any_likely_upper_bound
= false;
548 bitmap_set_bit (wont_exit
, 1);
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. */
556 fprintf (dump_file
, ";; Condition at end of loop.\n");
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
)
564 bitmap_clear_bit (wont_exit
, 0);
565 if (desc
->noloop_assumptions
)
566 bitmap_clear_bit (wont_exit
, 1);
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));
576 if (opt_info
&& exit_mod
> 0)
577 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
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;
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;
590 loop
->any_likely_upper_bound
= false;
591 desc
->noloop_assumptions
= NULL_RTX
;
593 bitmap_set_bit (wont_exit
, 0);
594 bitmap_set_bit (wont_exit
, 1);
597 bitmap_clear_bit (wont_exit
, max_unroll
);
600 /* Now unroll the loop. */
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
,
606 DLTHE_FLAG_UPDATE_FREQ
| (opt_info
? DLTHE_RECORD_COPY_NUMBER
: 0));
611 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
612 free_opt_info (opt_info
);
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. */
620 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
622 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
623 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
627 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
628 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
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
);
643 /* Remove the edges. */
644 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
649 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
650 max_unroll
, num_loop_insns (loop
));
653 /* Decide whether to unroll LOOP iterating runtime computable number of times
656 decide_unroll_runtime_iterations (class loop
*loop
, int flags
)
658 unsigned nunroll
, nunroll_by_av
, i
;
659 class niter_desc
*desc
;
660 widest_int iterations
;
662 /* If we were not asked to unroll this loop, just return back silently. */
663 if (!(flags
& UAP_UNROLL
) && !loop
->unroll
)
666 if (dump_enabled_p ())
667 dump_printf (MSG_NOTE
,
668 "considering unrolling loop with runtime-"
669 "computable number of iterations\n");
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
;
680 if (targetm
.loop_unroll_adjust
)
681 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
683 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
684 nunroll
= loop
->unroll
;
686 /* Skip big loops. */
690 fprintf (dump_file
, ";; Not considering loop, is too big\n");
694 /* Check for simple loops. */
695 desc
= get_simple_loop_desc (loop
);
697 /* Check simpleness. */
698 if (!desc
->simple_p
|| desc
->assumptions
)
702 ";; Unable to prove that the number of iterations "
703 "can be counted in runtime\n");
707 if (desc
->const_iter
)
710 fprintf (dump_file
, ";; Loop iterates constant times\n");
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
))
720 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
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)
730 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
731 loop
->lpt_decision
.times
= i
- 1;
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. */
739 split_edge_and_insert (edge e
, rtx_insn
*insns
)
746 emit_insn_after (insns
, BB_END (bb
));
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.
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:
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.
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.
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
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. */
786 compare_and_jump_seq (rtx op0
, rtx op1
, enum rtx_code comp
,
787 rtx_code_label
*label
, profile_probability prob
,
795 mode
= GET_MODE (op0
);
796 if (mode
== VOIDmode
)
797 mode
= GET_MODE (op1
);
800 if (GET_MODE_CLASS (mode
) == MODE_CC
)
802 /* A hack -- there seems to be no easy generic way how to make a
803 conditional jump from a ccmode comparison. */
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);
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
)++;
828 if (prob
.initialized_p ())
829 add_reg_br_prob_note (jump
, prob
);
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
842 for (i = 0; i < n; i++)
845 ==> (LOOP->LPT_DECISION.TIMES == 3)
870 unroll_loop_runtime_iterations (class loop
*loop
)
872 rtx old_niter
, niter
, tmp
;
873 rtx_insn
*init_code
, *branch_code
;
875 profile_probability p
;
876 basic_block preheader
, *body
, swtch
, ezc_swtch
= NULL
;
878 profile_count iter_count
, new_count
;
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
;
888 if (flag_split_ivs_in_unroller
889 || flag_variable_expansion_in_unroller
)
890 opt_info
= analyze_insns_in_loop (loop
);
892 /* Remember blocks whose dominators will have to be updated. */
893 auto_vec
<basic_block
> dom_bbs
;
895 body
= get_loop_body (loop
);
896 for (i
= 0; i
< loop
->num_nodes
; i
++)
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
);
906 /* Leave exit in first copy (for explanation why see comment in
907 unroll_loop_constant_iterations). */
909 n_peel
= max_unroll
- 1;
910 extra_zero_check
= true;
911 last_may_exit
= false;
915 /* Leave exit in last copy (for explanation why see comment in
916 unroll_loop_constant_iterations). */
917 may_exit_copy
= max_unroll
;
919 extra_zero_check
= false;
920 last_may_exit
= true;
923 /* Get expression for number of iterations. */
925 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
926 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
928 emit_move_insn (niter
, tmp
);
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
)
935 niter
= expand_simple_binop (desc
->mode
, PLUS
,
937 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
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
);
948 init_code
= get_insns ();
950 unshare_all_rtl_in_chain (init_code
);
952 /* Precondition the loop. */
953 split_edge_and_insert (loop_preheader_edge (loop
), init_code
);
955 auto_vec
<edge
> remove_edges
;
957 auto_sbitmap
wont_exit (max_unroll
+ 2);
959 if (extra_zero_check
|| desc
->noloop_assumptions
)
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
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
,
971 DLTHE_FLAG_UPDATE_FREQ
);
975 /* Record the place where switch will be built for preconditioning. */
976 swtch
= split_edge (loop_preheader_edge (loop
));
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
;
984 for (i
= 0; i
< n_peel
; i
++)
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
,
993 DLTHE_FLAG_UPDATE_FREQ
);
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);
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
);
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
);
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
);
1021 if (extra_zero_check
)
1023 /* Add branch for zero iterations. */
1024 p
= profile_probability::always ().apply_scale (1, max_unroll
+ 1);
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
,
1035 gcc_assert (branch_code
!= NULL_RTX
);
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
);
1045 /* Recount dominators for outer blocks. */
1046 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
1048 /* And unroll loop. */
1050 bitmap_ones (wont_exit
);
1051 bitmap_clear_bit (wont_exit
, may_exit_copy
);
1052 opt_info_start_duplication (opt_info
);
1054 ok
= duplicate_loop_body_to_header_edge (
1055 loop
, loop_latch_edge (loop
), max_unroll
, wont_exit
, desc
->out_edge
,
1057 DLTHE_FLAG_UPDATE_FREQ
| (opt_info
? DLTHE_RECORD_COPY_NUMBER
: 0));
1062 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1063 free_opt_info (opt_info
);
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
1072 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1074 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1075 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1079 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1080 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1084 /* Remove the edges. */
1085 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
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
);
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);
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
;
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
;
1119 loop
->any_likely_upper_bound
= false;
1124 ";; Unrolled loop %d times, counting # of iterations "
1125 "in runtime, %i insns\n",
1126 max_unroll
, num_loop_insns (loop
));
1129 /* Decide whether to unroll LOOP stupidly and how much. */
1131 decide_unroll_stupid (class loop
*loop
, int flags
)
1133 unsigned nunroll
, nunroll_by_av
, i
;
1134 class niter_desc
*desc
;
1135 widest_int iterations
;
1137 /* If we were not asked to unroll this loop, just return back silently. */
1138 if (!(flags
& UAP_UNROLL_ALL
) && !loop
->unroll
)
1141 if (dump_enabled_p ())
1142 dump_printf (MSG_NOTE
, "considering unrolling loop stupidly\n");
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
;
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
;
1154 if (targetm
.loop_unroll_adjust
)
1155 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
1157 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
1158 nunroll
= loop
->unroll
;
1160 /* Skip big loops. */
1164 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1168 /* Check for simple loops. */
1169 desc
= get_simple_loop_desc (loop
);
1171 /* Check simpleness. */
1172 if (desc
->simple_p
&& !desc
->assumptions
)
1175 fprintf (dump_file
, ";; Loop is simple\n");
1179 /* Do not unroll loops with branches inside -- it increases number
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)
1186 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
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
))
1196 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
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)
1206 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1207 loop
->lpt_decision
.times
= i
- 1;
1210 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1215 ==> (LOOP->LPT_DECISION.TIMES == 3)
1229 unroll_loop_stupid (class loop
*loop
)
1231 unsigned nunroll
= loop
->lpt_decision
.times
;
1232 class niter_desc
*desc
= get_simple_loop_desc (loop
);
1233 struct opt_info
*opt_info
= NULL
;
1236 if (flag_split_ivs_in_unroller
1237 || flag_variable_expansion_in_unroller
)
1238 opt_info
= analyze_insns_in_loop (loop
);
1240 auto_sbitmap
wont_exit (nunroll
+ 1);
1241 bitmap_clear (wont_exit
);
1242 opt_info_start_duplication (opt_info
);
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));
1251 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1252 free_opt_info (opt_info
);
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
1263 desc
->simple_p
= false;
1267 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1268 nunroll
, num_loop_insns (loop
));
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
1276 referenced_in_one_insn_in_loop_p (class loop
*loop
, rtx reg
,
1279 basic_block
*body
, bb
;
1284 body
= get_loop_body (loop
);
1285 for (i
= 0; i
< loop
->num_nodes
; i
++)
1289 FOR_BB_INSNS (bb
, insn
)
1290 if (!rtx_referenced_p (reg
, insn
))
1292 else if (DEBUG_INSN_P (insn
))
1294 else if (++count_ref
> 1)
1298 return (count_ref
== 1);
1301 /* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1304 reset_debug_uses_in_loop (class loop
*loop
, rtx reg
, int debug_uses
)
1306 basic_block
*body
, bb
;
1310 body
= get_loop_body (loop
);
1311 for (i
= 0; debug_uses
&& i
< loop
->num_nodes
; i
++)
1315 FOR_BB_INSNS (bb
, insn
)
1316 if (!DEBUG_INSN_P (insn
) || !rtx_referenced_p (reg
, insn
))
1320 validate_change (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1321 gen_rtx_UNKNOWN_VAR_LOC (), 0);
1329 /* Determine whether INSN contains an accumulator
1330 which can be expanded into separate copies,
1331 one for each copy of the LOOP body.
1333 for (i = 0 ; i < n; i++)
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.
1352 static struct var_to_expand
*
1353 analyze_insn_to_expand_var (class loop
*loop
, rtx_insn
*insn
)
1356 struct var_to_expand
*ves
;
1361 set
= single_set (insn
);
1365 dest
= SET_DEST (set
);
1366 src
= SET_SRC (set
);
1367 code
= GET_CODE (src
);
1369 if (code
!= PLUS
&& code
!= MINUS
&& code
!= MULT
&& code
!= FMA
)
1372 if (FLOAT_MODE_P (GET_MODE (dest
)))
1374 if (!flag_associative_math
)
1376 /* In the case of FMA, we're also changing the rounding. */
1377 if (code
== FMA
&& !flag_unsafe_math_optimizations
)
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.
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
)))
1394 && !(GET_CODE (dest
) == SUBREG
1395 && REG_P (SUBREG_REG (dest
))))
1398 /* Find the accumulator use within the operation. */
1401 /* We only support accumulation via FMA in the ADD position. */
1402 if (!rtx_equal_p (dest
, XEXP (src
, 2)))
1406 else if (rtx_equal_p (dest
, XEXP (src
, 0)))
1408 else if (rtx_equal_p (dest
, XEXP (src
, 1)))
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. */
1421 /* It must not otherwise be used. */
1424 if (rtx_referenced_p (dest
, XEXP (src
, 0))
1425 || rtx_referenced_p (dest
, XEXP (src
, 1)))
1428 else if (rtx_referenced_p (dest
, XEXP (src
, 1 - accum_pos
)))
1431 /* It must be used in exactly one insn. */
1432 if (!referenced_in_one_insn_in_loop_p (loop
, dest
, &debug_uses
))
1437 fprintf (dump_file
, "\n;; Expanding Accumulator ");
1438 print_rtl (dump_file
, dest
);
1439 fprintf (dump_file
, "\n");
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
);
1453 /* Record the accumulator to expand. */
1454 ves
= XNEW (struct var_to_expand
);
1456 ves
->reg
= copy_rtx (dest
);
1457 ves
->var_expansions
.create (1);
1459 ves
->op
= GET_CODE (src
);
1460 ves
->expansion_count
= 0;
1461 ves
->reuse_expansion
= 0;
1465 /* Determine whether there is an induction variable in INSN that
1466 we would like to split during unrolling.
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
1490 static struct iv_to_split
*
1491 analyze_iv_to_split_insn (rtx_insn
*insn
)
1495 struct iv_to_split
*ivts
;
1496 scalar_int_mode mode
;
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
);
1505 dest
= SET_DEST (set
);
1506 if (!REG_P (dest
) || !is_a
<scalar_int_mode
> (GET_MODE (dest
), &mode
))
1509 if (!biv_p (insn
, mode
, dest
))
1512 ok
= iv_analyze_result (insn
, dest
, &iv
);
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.
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. */
1525 if (iv
.step
== const0_rtx
1526 || iv
.mode
!= iv
.extend_mode
)
1529 /* Record the insn to split. */
1530 ivts
= XNEW (struct iv_to_split
);
1532 ivts
->orig_var
= dest
;
1533 ivts
->base_var
= NULL_RTX
;
1534 ivts
->step
= iv
.step
;
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. */
1545 static struct opt_info
*
1546 analyze_insns_in_loop (class loop
*loop
)
1548 basic_block
*body
, bb
;
1550 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
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
);
1558 bool can_apply
= false;
1560 iv_analysis_loop_init (loop
);
1562 body
= get_loop_body (loop
);
1564 if (flag_split_ivs_in_unroller
)
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
;
1572 /* Record the loop exit bb and loop preheader before the unrolling. */
1573 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1575 if (edges
.length () == 1)
1578 if (!(exit
->flags
& EDGE_COMPLEX
))
1580 opt_info
->loop_exit
= split_edge (exit
);
1585 if (flag_variable_expansion_in_unroller
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
;
1594 for (i
= 0; i
< loop
->num_nodes
; i
++)
1597 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1600 FOR_BB_INSNS (bb
, insn
)
1605 if (opt_info
->insns_to_split
)
1606 ivts
= analyze_iv_to_split_insn (insn
);
1610 slot1
= opt_info
->insns_to_split
->find_slot (ivts
, INSERT
);
1611 gcc_assert (*slot1
== NULL
);
1613 *opt_info
->iv_to_split_tail
= ivts
;
1614 opt_info
->iv_to_split_tail
= &ivts
->next
;
1618 if (opt_info
->insns_with_var_to_expand
)
1619 ves
= analyze_insn_to_expand_var (loop
, insn
);
1623 slot2
= opt_info
->insns_with_var_to_expand
->find_slot (ves
, INSERT
);
1624 gcc_assert (*slot2
== NULL
);
1626 *opt_info
->var_to_expand_tail
= ves
;
1627 opt_info
->var_to_expand_tail
= &ves
->next
;
1636 /* Called just before loop duplication. Records start of duplicated area
1640 opt_info_start_duplication (struct opt_info
*opt_info
)
1643 opt_info
->first_new_block
= last_basic_block_for_fn (cfun
);
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. */
1652 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1656 /* If we are unrolling, initialization is done in the original loop
1662 /* If we are peeling, the copy in that the initialization occurs has
1663 number 1. The original loop (number 0) is the last. */
1671 /* Allocate basic variable for the induction variable chain. */
1674 allocate_basic_variable (struct iv_to_split
*ivts
)
1676 rtx expr
= SET_SRC (single_set (ivts
->insn
));
1678 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1681 /* Insert initialization of basic variable of IVTS before INSN, taking
1682 the initial value from INSN. */
1685 insert_base_initialization (struct iv_to_split
*ivts
, rtx_insn
*insn
)
1687 rtx expr
= copy_rtx (SET_SRC (single_set (insn
)));
1691 expr
= force_operand (expr
, ivts
->base_var
);
1692 if (expr
!= ivts
->base_var
)
1693 emit_move_insn (ivts
->base_var
, expr
);
1697 emit_insn_before (seq
, insn
);
1700 /* Replace the use of induction variable described in IVTS in INSN
1701 by base variable + DELTA * step. */
1704 split_iv (struct iv_to_split
*ivts
, rtx_insn
*insn
, unsigned delta
)
1706 rtx expr
, *loc
, incr
, var
;
1708 machine_mode mode
= GET_MODE (ivts
->base_var
);
1711 /* Construct base + DELTA * step. */
1713 expr
= ivts
->base_var
;
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
);
1723 /* Figure out where to do the replacement. */
1724 loc
= &SET_SRC (single_set (insn
));
1726 /* If we can make the replacement right away, we're done. */
1727 if (validate_change (insn
, loc
, expr
, 0))
1730 /* Otherwise, force EXPR into a register and try again. */
1732 var
= gen_reg_rtx (mode
);
1733 expr
= force_operand (expr
, var
);
1735 emit_move_insn (var
, expr
);
1738 emit_insn_before (seq
, insn
);
1740 if (validate_change (insn
, loc
, var
, 0))
1743 /* The last chance. Try recreating the assignment in insn
1744 completely from scratch. */
1745 set
= single_set (insn
);
1750 src
= copy_rtx (SET_SRC (set
));
1751 dest
= copy_rtx (SET_DEST (set
));
1752 src
= force_operand (src
, dest
);
1754 emit_move_insn (dest
, src
);
1758 emit_insn_before (seq
, insn
);
1763 /* Return one expansion of the accumulator recorded in struct VE. */
1766 get_expansion (struct var_to_expand
*ve
)
1770 if (ve
->reuse_expansion
== 0)
1773 reg
= ve
->var_expansions
[ve
->reuse_expansion
- 1];
1775 if (ve
->var_expansions
.length () == (unsigned) ve
->reuse_expansion
)
1776 ve
->reuse_expansion
= 0;
1778 ve
->reuse_expansion
++;
1784 /* Given INSN replace the uses of the accumulator recorded in VE
1785 with a new register. */
1788 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx_insn
*insn
)
1791 bool really_new_expansion
= false;
1793 set
= single_set (insn
);
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
)
1800 really_new_expansion
= true;
1801 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1804 new_reg
= get_expansion (ve
);
1806 validate_replace_rtx_group (SET_DEST (set
), new_reg
, insn
);
1807 if (apply_change_group ())
1808 if (really_new_expansion
)
1810 ve
->var_expansions
.safe_push (new_reg
);
1811 ve
->expansion_count
++;
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
1823 for (i = 0 ; i < n; i++)
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). */
1843 insert_var_expansion_initialization (struct var_to_expand
*ve
,
1849 machine_mode mode
= GET_MODE (ve
->reg
);
1850 bool honor_signed_zero_p
= HONOR_SIGNED_ZEROS (mode
);
1852 if (ve
->var_expansions
.length () == 0)
1859 /* Note that we only accumulate FMA via the ADD operand. */
1862 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1864 if (honor_signed_zero_p
)
1865 zero_init
= simplify_gen_unary (NEG
, mode
, CONST0_RTX (mode
), mode
);
1867 zero_init
= CONST0_RTX (mode
);
1868 emit_move_insn (var
, zero_init
);
1873 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1875 zero_init
= CONST1_RTX (GET_MODE (var
));
1876 emit_move_insn (var
, zero_init
);
1887 emit_insn_after (seq
, BB_END (place
));
1890 /* Combine the variable expansions at the loop exit. PLACE is the
1891 loop exit basic block where the summation of the expansions should
1895 combine_var_copies_in_loop_exit (struct var_to_expand
*ve
, basic_block place
)
1899 rtx_insn
*seq
, *insn
;
1902 if (ve
->var_expansions
.length () == 0)
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
);
1912 /* Note that we only accumulate FMA via the ADD operand. */
1915 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1916 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
), var
, sum
);
1920 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1921 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
), var
, sum
);
1928 expr
= force_operand (sum
, ve
->reg
);
1929 if (expr
!= ve
->reg
)
1930 emit_move_insn (ve
->reg
, expr
);
1934 insn
= BB_HEAD (place
);
1935 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
1936 insn
= NEXT_INSN (insn
);
1938 emit_insn_after (seq
, insn
);
1941 /* Strip away REG_EQUAL notes for IVs we're splitting.
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.
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... */
1953 maybe_strip_eq_note_for_split_iv (struct opt_info
*opt_info
, rtx_insn
*insn
)
1955 struct iv_to_split
*ivts
;
1956 rtx note
= find_reg_equal_equiv_note (insn
);
1959 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
1960 if (reg_mentioned_p (ivts
->orig_var
, note
))
1962 remove_note (insn
, note
);
1967 /* Apply loop optimizations in loop copies using the
1968 data which gathered during the unrolling. Structure
1969 OPT_INFO record that data.
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). */
1977 apply_opt_in_copies (struct opt_info
*opt_info
,
1978 unsigned n_copies
, bool unrolling
,
1979 bool rewrite_original_loop
)
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
;
1987 /* Sanity check -- we need to put initialization in the original loop
1989 gcc_assert (!unrolling
|| rewrite_original_loop
);
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
);
1996 for (i
= opt_info
->first_new_block
;
1997 i
< (unsigned) last_basic_block_for_fn (cfun
);
2000 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2001 orig_bb
= get_bb_original (bb
);
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
,
2008 orig_insn
= BB_HEAD (orig_bb
);
2009 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
2012 || (DEBUG_BIND_INSN_P (insn
)
2013 && INSN_VAR_LOCATION_DECL (insn
)
2014 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
))
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
))
2022 orig_insn
= NEXT_INSN (orig_insn
);
2024 ivts_templ
.insn
= orig_insn
;
2025 ve_templ
.insn
= orig_insn
;
2027 /* Apply splitting iv optimization. */
2028 if (opt_info
->insns_to_split
)
2030 maybe_strip_eq_note_for_split_iv (opt_info
, insn
);
2032 ivts
= opt_info
->insns_to_split
->find (&ivts_templ
);
2036 gcc_assert (GET_CODE (PATTERN (insn
))
2037 == GET_CODE (PATTERN (orig_insn
)));
2040 insert_base_initialization (ivts
, insn
);
2041 split_iv (ivts
, insn
, delta
);
2044 /* Apply variable expansion optimization. */
2045 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2047 ves
= (struct var_to_expand
*)
2048 opt_info
->insns_with_var_to_expand
->find (&ve_templ
);
2051 gcc_assert (GET_CODE (PATTERN (insn
))
2052 == GET_CODE (PATTERN (orig_insn
)));
2053 expand_var_during_unrolling (ves
, insn
);
2056 orig_insn
= NEXT_INSN (orig_insn
);
2060 if (!rewrite_original_loop
)
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
)
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
);
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
);
2080 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2081 orig_bb
= get_bb_original (bb
);
2082 if (get_bb_copy (orig_bb
) != bb
)
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
));
2090 next
= NEXT_INSN (orig_insn
);
2092 if (!INSN_P (orig_insn
))
2095 ivts_templ
.insn
= orig_insn
;
2096 if (opt_info
->insns_to_split
)
2098 maybe_strip_eq_note_for_split_iv (opt_info
, orig_insn
);
2100 ivts
= (struct iv_to_split
*)
2101 opt_info
->insns_to_split
->find (&ivts_templ
);
2105 insert_base_initialization (ivts
, orig_insn
);
2106 split_iv (ivts
, orig_insn
, delta
);
2115 /* Release OPT_INFO. */
2118 free_opt_info (struct opt_info
*opt_info
)
2120 delete opt_info
->insns_to_split
;
2121 opt_info
->insns_to_split
= NULL
;
2122 if (opt_info
->insns_with_var_to_expand
)
2124 struct var_to_expand
*ves
;
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
;