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
)
219 /* Scan the loops, inner ones first. */
220 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
222 loop
->lpt_decision
.decision
= LPT_NONE
;
223 dump_user_location_t locus
= get_loop_location (loop
);
225 if (dump_enabled_p ())
226 dump_printf_loc (MSG_NOTE
, locus
,
227 "considering unrolling loop %d at BB %d\n",
228 loop
->num
, loop
->header
->index
);
230 if (loop
->unroll
== 1)
234 ";; Not unrolling loop, user didn't want it unrolled\n");
238 /* Do not peel cold areas. */
239 if (optimize_loop_for_size_p (loop
))
242 fprintf (dump_file
, ";; Not considering loop, cold area\n");
246 /* Can the loop be manipulated? */
247 if (!can_duplicate_loop_p (loop
))
251 ";; Not considering loop, cannot duplicate\n");
255 /* Skip non-innermost loops. */
259 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
263 loop
->ninsns
= num_loop_insns (loop
);
264 loop
->av_ninsns
= average_num_loop_insns (loop
);
266 /* Try transformations one by one in decreasing order of priority. */
267 decide_unroll_constant_iterations (loop
, flags
);
268 if (loop
->lpt_decision
.decision
== LPT_NONE
)
269 decide_unroll_runtime_iterations (loop
, flags
);
270 if (loop
->lpt_decision
.decision
== LPT_NONE
)
271 decide_unroll_stupid (loop
, flags
);
273 report_unroll (loop
, locus
);
279 unroll_loops (int flags
)
282 bool changed
= false;
284 /* Now decide rest of unrolling. */
285 decide_unrolling (flags
);
287 /* Scan the loops, inner ones first. */
288 FOR_EACH_LOOP (loop
, LI_FROM_INNERMOST
)
290 /* And perform the appropriate transformations. */
291 switch (loop
->lpt_decision
.decision
)
293 case LPT_UNROLL_CONSTANT
:
294 unroll_loop_constant_iterations (loop
);
297 case LPT_UNROLL_RUNTIME
:
298 unroll_loop_runtime_iterations (loop
);
301 case LPT_UNROLL_STUPID
:
302 unroll_loop_stupid (loop
);
314 calculate_dominance_info (CDI_DOMINATORS
);
315 fix_loop_structure (NULL
);
321 /* Check whether exit of the LOOP is at the end of loop body. */
324 loop_exit_at_end_p (class loop
*loop
)
326 class niter_desc
*desc
= get_simple_loop_desc (loop
);
329 /* We should never have conditional in latch block. */
330 gcc_assert (desc
->in_edge
->dest
!= loop
->header
);
332 if (desc
->in_edge
->dest
!= loop
->latch
)
335 /* Check that the latch is empty. */
336 FOR_BB_INSNS (loop
->latch
, insn
)
338 if (INSN_P (insn
) && active_insn_p (insn
))
345 /* Decide whether to unroll LOOP iterating constant number of times
349 decide_unroll_constant_iterations (class loop
*loop
, int flags
)
351 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
352 class niter_desc
*desc
;
353 widest_int iterations
;
355 /* If we were not asked to unroll this loop, just return back silently. */
356 if (!(flags
& UAP_UNROLL
) && !loop
->unroll
)
359 if (dump_enabled_p ())
360 dump_printf (MSG_NOTE
,
361 "considering unrolling loop with constant "
362 "number of iterations\n");
364 /* nunroll = total number of copies of the original loop body in
365 unrolled loop (i.e. if it is 2, we have to duplicate loop body once). */
366 nunroll
= param_max_unrolled_insns
/ loop
->ninsns
;
368 = param_max_average_unrolled_insns
/ loop
->av_ninsns
;
369 if (nunroll
> nunroll_by_av
)
370 nunroll
= nunroll_by_av
;
371 if (nunroll
> (unsigned) param_max_unroll_times
)
372 nunroll
= param_max_unroll_times
;
374 if (targetm
.loop_unroll_adjust
)
375 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
377 /* Skip big loops. */
381 fprintf (dump_file
, ";; Not considering loop, is too big\n");
385 /* Check for simple loops. */
386 desc
= get_simple_loop_desc (loop
);
388 /* Check number of iterations. */
389 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
393 ";; Unable to prove that the loop iterates constant times\n");
397 /* Check for an explicit unrolling factor. */
398 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
400 /* However we cannot unroll completely at the RTL level a loop with
401 constant number of iterations; it should have been peeled instead. */
402 if (desc
->niter
== 0 || (unsigned) loop
->unroll
> desc
->niter
- 1)
405 fprintf (dump_file
, ";; Loop should have been peeled\n");
409 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
410 loop
->lpt_decision
.times
= loop
->unroll
- 1;
415 /* Check whether the loop rolls enough to consider.
416 Consult also loop bounds and profile; in the case the loop has more
417 than one exit it may well loop less than determined maximal number
419 if (desc
->niter
< 2 * nunroll
420 || ((get_estimated_loop_iterations (loop
, &iterations
)
421 || get_likely_max_loop_iterations (loop
, &iterations
))
422 && wi::ltu_p (iterations
, 2 * nunroll
)))
425 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
429 /* Success; now compute number of iterations to unroll. We alter
430 nunroll so that as few as possible copies of loop body are
431 necessary, while still not decreasing the number of unrollings
432 too much (at most by 1). */
433 best_copies
= 2 * nunroll
+ 10;
436 if (i
> desc
->niter
- 2)
439 for (; i
>= nunroll
- 1; i
--)
441 unsigned exit_mod
= desc
->niter
% (i
+ 1);
443 if (!loop_exit_at_end_p (loop
))
444 n_copies
= exit_mod
+ i
+ 1;
445 else if (exit_mod
!= (unsigned) i
446 || desc
->noloop_assumptions
!= NULL_RTX
)
447 n_copies
= exit_mod
+ i
+ 2;
451 if (n_copies
< best_copies
)
453 best_copies
= n_copies
;
458 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
459 loop
->lpt_decision
.times
= best_unroll
;
462 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES times.
463 The transformation does this:
465 for (i = 0; i < 102; i++)
468 ==> (LOOP->LPT_DECISION.TIMES == 3)
482 unroll_loop_constant_iterations (class loop
*loop
)
484 unsigned HOST_WIDE_INT niter
;
488 unsigned max_unroll
= loop
->lpt_decision
.times
;
489 class niter_desc
*desc
= get_simple_loop_desc (loop
);
490 bool exit_at_end
= loop_exit_at_end_p (loop
);
491 struct opt_info
*opt_info
= NULL
;
496 /* Should not get here (such loop should be peeled instead). */
497 gcc_assert (niter
> max_unroll
+ 1);
499 exit_mod
= niter
% (max_unroll
+ 1);
501 auto_sbitmap
wont_exit (max_unroll
+ 2);
502 bitmap_ones (wont_exit
);
504 auto_vec
<edge
> remove_edges
;
505 if (flag_split_ivs_in_unroller
506 || flag_variable_expansion_in_unroller
)
507 opt_info
= analyze_insns_in_loop (loop
);
511 /* The exit is not at the end of the loop; leave exit test
512 in the first copy, so that the loops that start with test
513 of exit condition have continuous body after unrolling. */
516 fprintf (dump_file
, ";; Condition at beginning of loop.\n");
518 /* Peel exit_mod iterations. */
519 bitmap_clear_bit (wont_exit
, 0);
520 if (desc
->noloop_assumptions
)
521 bitmap_clear_bit (wont_exit
, 1);
525 opt_info_start_duplication (opt_info
);
526 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
528 wont_exit
, desc
->out_edge
,
530 DLTHE_FLAG_UPDATE_FREQ
531 | (opt_info
&& exit_mod
> 1
532 ? DLTHE_RECORD_COPY_NUMBER
536 if (opt_info
&& exit_mod
> 1)
537 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
539 desc
->noloop_assumptions
= NULL_RTX
;
540 desc
->niter
-= exit_mod
;
541 loop
->nb_iterations_upper_bound
-= exit_mod
;
542 if (loop
->any_estimate
543 && wi::leu_p (exit_mod
, loop
->nb_iterations_estimate
))
544 loop
->nb_iterations_estimate
-= exit_mod
;
546 loop
->any_estimate
= false;
547 if (loop
->any_likely_upper_bound
548 && wi::leu_p (exit_mod
, loop
->nb_iterations_likely_upper_bound
))
549 loop
->nb_iterations_likely_upper_bound
-= exit_mod
;
551 loop
->any_likely_upper_bound
= false;
554 bitmap_set_bit (wont_exit
, 1);
558 /* Leave exit test in last copy, for the same reason as above if
559 the loop tests the condition at the end of loop body. */
562 fprintf (dump_file
, ";; Condition at end of loop.\n");
564 /* We know that niter >= max_unroll + 2; so we do not need to care of
565 case when we would exit before reaching the loop. So just peel
566 exit_mod + 1 iterations. */
567 if (exit_mod
!= max_unroll
568 || desc
->noloop_assumptions
)
570 bitmap_clear_bit (wont_exit
, 0);
571 if (desc
->noloop_assumptions
)
572 bitmap_clear_bit (wont_exit
, 1);
574 opt_info_start_duplication (opt_info
);
575 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
577 wont_exit
, desc
->out_edge
,
579 DLTHE_FLAG_UPDATE_FREQ
580 | (opt_info
&& exit_mod
> 0
581 ? DLTHE_RECORD_COPY_NUMBER
585 if (opt_info
&& exit_mod
> 0)
586 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
588 desc
->niter
-= exit_mod
+ 1;
589 loop
->nb_iterations_upper_bound
-= exit_mod
+ 1;
590 if (loop
->any_estimate
591 && wi::leu_p (exit_mod
+ 1, loop
->nb_iterations_estimate
))
592 loop
->nb_iterations_estimate
-= exit_mod
+ 1;
594 loop
->any_estimate
= false;
595 if (loop
->any_likely_upper_bound
596 && wi::leu_p (exit_mod
+ 1, loop
->nb_iterations_likely_upper_bound
))
597 loop
->nb_iterations_likely_upper_bound
-= exit_mod
+ 1;
599 loop
->any_likely_upper_bound
= false;
600 desc
->noloop_assumptions
= NULL_RTX
;
602 bitmap_set_bit (wont_exit
, 0);
603 bitmap_set_bit (wont_exit
, 1);
606 bitmap_clear_bit (wont_exit
, max_unroll
);
609 /* Now unroll the loop. */
611 opt_info_start_duplication (opt_info
);
612 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
614 wont_exit
, desc
->out_edge
,
616 DLTHE_FLAG_UPDATE_FREQ
618 ? DLTHE_RECORD_COPY_NUMBER
624 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
625 free_opt_info (opt_info
);
630 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
631 /* Find a new in and out edge; they are in the last copy we have made. */
633 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
635 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
636 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
640 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
641 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
645 desc
->niter
/= max_unroll
+ 1;
646 loop
->nb_iterations_upper_bound
647 = wi::udiv_trunc (loop
->nb_iterations_upper_bound
, max_unroll
+ 1);
648 if (loop
->any_estimate
)
649 loop
->nb_iterations_estimate
650 = wi::udiv_trunc (loop
->nb_iterations_estimate
, max_unroll
+ 1);
651 if (loop
->any_likely_upper_bound
)
652 loop
->nb_iterations_likely_upper_bound
653 = wi::udiv_trunc (loop
->nb_iterations_likely_upper_bound
, max_unroll
+ 1);
654 desc
->niter_expr
= gen_int_mode (desc
->niter
, desc
->mode
);
656 /* Remove the edges. */
657 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
662 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
663 max_unroll
, num_loop_insns (loop
));
666 /* Decide whether to unroll LOOP iterating runtime computable number of times
669 decide_unroll_runtime_iterations (class loop
*loop
, int flags
)
671 unsigned nunroll
, nunroll_by_av
, i
;
672 class niter_desc
*desc
;
673 widest_int iterations
;
675 /* If we were not asked to unroll this loop, just return back silently. */
676 if (!(flags
& UAP_UNROLL
) && !loop
->unroll
)
679 if (dump_enabled_p ())
680 dump_printf (MSG_NOTE
,
681 "considering unrolling loop with runtime-"
682 "computable number of iterations\n");
684 /* nunroll = total number of copies of the original loop body in
685 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
686 nunroll
= param_max_unrolled_insns
/ loop
->ninsns
;
687 nunroll_by_av
= param_max_average_unrolled_insns
/ loop
->av_ninsns
;
688 if (nunroll
> nunroll_by_av
)
689 nunroll
= nunroll_by_av
;
690 if (nunroll
> (unsigned) param_max_unroll_times
)
691 nunroll
= param_max_unroll_times
;
693 if (targetm
.loop_unroll_adjust
)
694 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
696 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
697 nunroll
= loop
->unroll
;
699 /* Skip big loops. */
703 fprintf (dump_file
, ";; Not considering loop, is too big\n");
707 /* Check for simple loops. */
708 desc
= get_simple_loop_desc (loop
);
710 /* Check simpleness. */
711 if (!desc
->simple_p
|| desc
->assumptions
)
715 ";; Unable to prove that the number of iterations "
716 "can be counted in runtime\n");
720 if (desc
->const_iter
)
723 fprintf (dump_file
, ";; Loop iterates constant times\n");
727 /* Check whether the loop rolls. */
728 if ((get_estimated_loop_iterations (loop
, &iterations
)
729 || get_likely_max_loop_iterations (loop
, &iterations
))
730 && wi::ltu_p (iterations
, 2 * nunroll
))
733 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
737 /* Success; now force nunroll to be power of 2, as code-gen
738 requires it, we are unable to cope with overflows in
739 computation of number of iterations. */
740 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
743 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
744 loop
->lpt_decision
.times
= i
- 1;
747 /* Splits edge E and inserts the sequence of instructions INSNS on it, and
748 returns the newly created block. If INSNS is NULL_RTX, nothing is changed
749 and NULL is returned instead. */
752 split_edge_and_insert (edge e
, rtx_insn
*insns
)
759 emit_insn_after (insns
, BB_END (bb
));
761 /* ??? We used to assume that INSNS can contain control flow insns, and
762 that we had to try to find sub basic blocks in BB to maintain a valid
763 CFG. For this purpose we used to set the BB_SUPERBLOCK flag on BB
764 and call break_superblocks when going out of cfglayout mode. But it
765 turns out that this never happens; and that if it does ever happen,
766 the verify_flow_info at the end of the RTL loop passes would fail.
768 There are two reasons why we expected we could have control flow insns
769 in INSNS. The first is when a comparison has to be done in parts, and
770 the second is when the number of iterations is computed for loops with
771 the number of iterations known at runtime. In both cases, test cases
772 to get control flow in INSNS appear to be impossible to construct:
774 * If do_compare_rtx_and_jump needs several branches to do comparison
775 in a mode that needs comparison by parts, we cannot analyze the
776 number of iterations of the loop, and we never get to unrolling it.
778 * The code in expand_divmod that was suspected to cause creation of
779 branching code seems to be only accessed for signed division. The
780 divisions used by # of iterations analysis are always unsigned.
781 Problems might arise on architectures that emits branching code
782 for some operations that may appear in the unroller (especially
783 for division), but we have no such architectures.
785 Considering all this, it was decided that we should for now assume
786 that INSNS can in theory contain control flow insns, but in practice
787 it never does. So we don't handle the theoretical case, and should
788 a real failure ever show up, we have a pretty good clue for how to
794 /* Prepare a sequence comparing OP0 with OP1 using COMP and jumping to LABEL if
795 true, with probability PROB. If CINSN is not NULL, it is the insn to copy
796 in order to create a jump. */
799 compare_and_jump_seq (rtx op0
, rtx op1
, enum rtx_code comp
,
800 rtx_code_label
*label
, profile_probability prob
,
808 mode
= GET_MODE (op0
);
809 if (mode
== VOIDmode
)
810 mode
= GET_MODE (op1
);
813 if (GET_MODE_CLASS (mode
) == MODE_CC
)
815 /* A hack -- there seems to be no easy generic way how to make a
816 conditional jump from a ccmode comparison. */
818 cond
= XEXP (SET_SRC (pc_set (cinsn
)), 0);
819 gcc_assert (GET_CODE (cond
) == comp
);
820 gcc_assert (rtx_equal_p (op0
, XEXP (cond
, 0)));
821 gcc_assert (rtx_equal_p (op1
, XEXP (cond
, 1)));
822 emit_jump_insn (copy_insn (PATTERN (cinsn
)));
823 jump
= as_a
<rtx_jump_insn
*> (get_last_insn ());
824 JUMP_LABEL (jump
) = JUMP_LABEL (cinsn
);
825 LABEL_NUSES (JUMP_LABEL (jump
))++;
826 redirect_jump (jump
, label
, 0);
832 op0
= force_operand (op0
, NULL_RTX
);
833 op1
= force_operand (op1
, NULL_RTX
);
834 do_compare_rtx_and_jump (op0
, op1
, comp
, 0,
835 mode
, NULL_RTX
, NULL
, label
,
836 profile_probability::uninitialized ());
837 jump
= as_a
<rtx_jump_insn
*> (get_last_insn ());
838 jump
->set_jump_target (label
);
839 LABEL_NUSES (label
)++;
841 if (prob
.initialized_p ())
842 add_reg_br_prob_note (jump
, prob
);
850 /* Unroll LOOP for which we are able to count number of iterations in
851 runtime LOOP->LPT_DECISION.TIMES times. The times value must be a
852 power of two. The transformation does this (with some extra care
855 for (i = 0; i < n; i++)
858 ==> (LOOP->LPT_DECISION.TIMES == 3)
883 unroll_loop_runtime_iterations (class loop
*loop
)
885 rtx old_niter
, niter
, tmp
;
886 rtx_insn
*init_code
, *branch_code
;
888 profile_probability p
;
889 basic_block preheader
, *body
, swtch
, ezc_swtch
= NULL
;
891 profile_count iter_count
, new_count
;
894 bool extra_zero_check
, last_may_exit
;
895 unsigned max_unroll
= loop
->lpt_decision
.times
;
896 class niter_desc
*desc
= get_simple_loop_desc (loop
);
897 bool exit_at_end
= loop_exit_at_end_p (loop
);
898 struct opt_info
*opt_info
= NULL
;
901 if (flag_split_ivs_in_unroller
902 || flag_variable_expansion_in_unroller
)
903 opt_info
= analyze_insns_in_loop (loop
);
905 /* Remember blocks whose dominators will have to be updated. */
906 auto_vec
<basic_block
> dom_bbs
;
908 body
= get_loop_body (loop
);
909 for (i
= 0; i
< loop
->num_nodes
; i
++)
911 for (basic_block bb
: get_dominated_by (CDI_DOMINATORS
, body
[i
]))
912 if (!flow_bb_inside_loop_p (loop
, bb
))
913 dom_bbs
.safe_push (bb
);
919 /* Leave exit in first copy (for explanation why see comment in
920 unroll_loop_constant_iterations). */
922 n_peel
= max_unroll
- 1;
923 extra_zero_check
= true;
924 last_may_exit
= false;
928 /* Leave exit in last copy (for explanation why see comment in
929 unroll_loop_constant_iterations). */
930 may_exit_copy
= max_unroll
;
932 extra_zero_check
= false;
933 last_may_exit
= true;
936 /* Get expression for number of iterations. */
938 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
939 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
941 emit_move_insn (niter
, tmp
);
943 /* For loops that exit at end and whose number of iterations is reliable,
944 add one to niter to account for first pass through loop body before
945 reaching exit test. */
946 if (exit_at_end
&& !desc
->noloop_assumptions
)
948 niter
= expand_simple_binop (desc
->mode
, PLUS
,
950 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
954 /* Count modulo by ANDing it with max_unroll; we use the fact that
955 the number of unrollings is a power of two, and thus this is correct
956 even if there is overflow in the computation. */
957 niter
= expand_simple_binop (desc
->mode
, AND
,
958 niter
, gen_int_mode (max_unroll
, desc
->mode
),
959 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
961 init_code
= get_insns ();
963 unshare_all_rtl_in_chain (init_code
);
965 /* Precondition the loop. */
966 split_edge_and_insert (loop_preheader_edge (loop
), init_code
);
968 auto_vec
<edge
> remove_edges
;
970 auto_sbitmap
wont_exit (max_unroll
+ 2);
972 if (extra_zero_check
|| desc
->noloop_assumptions
)
974 /* Peel the first copy of loop body. Leave the exit test if the number
975 of iterations is not reliable. Also record the place of the extra zero
977 bitmap_clear (wont_exit
);
978 if (!desc
->noloop_assumptions
)
979 bitmap_set_bit (wont_exit
, 1);
980 ezc_swtch
= loop_preheader_edge (loop
)->src
;
981 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
982 1, wont_exit
, desc
->out_edge
,
984 DLTHE_FLAG_UPDATE_FREQ
);
988 /* Record the place where switch will be built for preconditioning. */
989 swtch
= split_edge (loop_preheader_edge (loop
));
991 /* Compute count increments for each switch block and initialize
992 innermost switch block. Switch blocks and peeled loop copies are built
993 from innermost outward. */
994 iter_count
= new_count
= swtch
->count
.apply_scale (1, max_unroll
+ 1);
995 swtch
->count
= new_count
;
997 for (i
= 0; i
< n_peel
; i
++)
1000 bitmap_clear (wont_exit
);
1001 if (i
!= n_peel
- 1 || !last_may_exit
)
1002 bitmap_set_bit (wont_exit
, 1);
1003 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1004 1, wont_exit
, desc
->out_edge
,
1006 DLTHE_FLAG_UPDATE_FREQ
);
1009 /* Create item for switch. */
1010 unsigned j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1011 p
= profile_probability::always ().apply_scale (1, i
+ 2);
1013 preheader
= split_edge (loop_preheader_edge (loop
));
1014 /* Add in count of edge from switch block. */
1015 preheader
->count
+= iter_count
;
1016 branch_code
= compare_and_jump_seq (copy_rtx (niter
),
1017 gen_int_mode (j
, desc
->mode
), EQ
,
1018 block_label (preheader
), p
, NULL
);
1020 /* We rely on the fact that the compare and jump cannot be optimized out,
1021 and hence the cfg we create is correct. */
1022 gcc_assert (branch_code
!= NULL_RTX
);
1024 swtch
= split_edge_and_insert (single_pred_edge (swtch
), branch_code
);
1025 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1026 single_succ_edge (swtch
)->probability
= p
.invert ();
1027 new_count
+= iter_count
;
1028 swtch
->count
= new_count
;
1029 e
= make_edge (swtch
, preheader
,
1030 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1034 if (extra_zero_check
)
1036 /* Add branch for zero iterations. */
1037 p
= profile_probability::always ().apply_scale (1, max_unroll
+ 1);
1039 preheader
= split_edge (loop_preheader_edge (loop
));
1040 /* Recompute count adjustments since initial peel copy may
1041 have exited and reduced those values that were computed above. */
1042 iter_count
= swtch
->count
.apply_scale (1, max_unroll
+ 1);
1043 /* Add in count of edge from switch block. */
1044 preheader
->count
+= iter_count
;
1045 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1046 block_label (preheader
), p
,
1048 gcc_assert (branch_code
!= NULL_RTX
);
1050 swtch
= split_edge_and_insert (single_succ_edge (swtch
), branch_code
);
1051 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1052 single_succ_edge (swtch
)->probability
= p
.invert ();
1053 e
= make_edge (swtch
, preheader
,
1054 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1058 /* Recount dominators for outer blocks. */
1059 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, false);
1061 /* And unroll loop. */
1063 bitmap_ones (wont_exit
);
1064 bitmap_clear_bit (wont_exit
, may_exit_copy
);
1065 opt_info_start_duplication (opt_info
);
1067 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1069 wont_exit
, desc
->out_edge
,
1071 DLTHE_FLAG_UPDATE_FREQ
1073 ? DLTHE_RECORD_COPY_NUMBER
1079 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1080 free_opt_info (opt_info
);
1085 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1086 /* Find a new in and out edge; they are in the last copy we have
1089 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1091 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1092 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1096 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1097 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1101 /* Remove the edges. */
1102 FOR_EACH_VEC_ELT (remove_edges
, i
, e
)
1105 /* We must be careful when updating the number of iterations due to
1106 preconditioning and the fact that the value must be valid at entry
1107 of the loop. After passing through the above code, we see that
1108 the correct new number of iterations is this: */
1109 gcc_assert (!desc
->const_iter
);
1111 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1112 gen_int_mode (max_unroll
+ 1, desc
->mode
));
1113 loop
->nb_iterations_upper_bound
1114 = wi::udiv_trunc (loop
->nb_iterations_upper_bound
, max_unroll
+ 1);
1115 if (loop
->any_estimate
)
1116 loop
->nb_iterations_estimate
1117 = wi::udiv_trunc (loop
->nb_iterations_estimate
, max_unroll
+ 1);
1118 if (loop
->any_likely_upper_bound
)
1119 loop
->nb_iterations_likely_upper_bound
1120 = wi::udiv_trunc (loop
->nb_iterations_likely_upper_bound
, max_unroll
+ 1);
1124 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1125 desc
->noloop_assumptions
= NULL_RTX
;
1126 --loop
->nb_iterations_upper_bound
;
1127 if (loop
->any_estimate
1128 && loop
->nb_iterations_estimate
!= 0)
1129 --loop
->nb_iterations_estimate
;
1131 loop
->any_estimate
= false;
1132 if (loop
->any_likely_upper_bound
1133 && loop
->nb_iterations_likely_upper_bound
!= 0)
1134 --loop
->nb_iterations_likely_upper_bound
;
1136 loop
->any_likely_upper_bound
= false;
1141 ";; Unrolled loop %d times, counting # of iterations "
1142 "in runtime, %i insns\n",
1143 max_unroll
, num_loop_insns (loop
));
1146 /* Decide whether to unroll LOOP stupidly and how much. */
1148 decide_unroll_stupid (class loop
*loop
, int flags
)
1150 unsigned nunroll
, nunroll_by_av
, i
;
1151 class niter_desc
*desc
;
1152 widest_int iterations
;
1154 /* If we were not asked to unroll this loop, just return back silently. */
1155 if (!(flags
& UAP_UNROLL_ALL
) && !loop
->unroll
)
1158 if (dump_enabled_p ())
1159 dump_printf (MSG_NOTE
, "considering unrolling loop stupidly\n");
1161 /* nunroll = total number of copies of the original loop body in
1162 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1163 nunroll
= param_max_unrolled_insns
/ loop
->ninsns
;
1165 = param_max_average_unrolled_insns
/ loop
->av_ninsns
;
1166 if (nunroll
> nunroll_by_av
)
1167 nunroll
= nunroll_by_av
;
1168 if (nunroll
> (unsigned) param_max_unroll_times
)
1169 nunroll
= param_max_unroll_times
;
1171 if (targetm
.loop_unroll_adjust
)
1172 nunroll
= targetm
.loop_unroll_adjust (nunroll
, loop
);
1174 if (loop
->unroll
> 0 && loop
->unroll
< USHRT_MAX
)
1175 nunroll
= loop
->unroll
;
1177 /* Skip big loops. */
1181 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1185 /* Check for simple loops. */
1186 desc
= get_simple_loop_desc (loop
);
1188 /* Check simpleness. */
1189 if (desc
->simple_p
&& !desc
->assumptions
)
1192 fprintf (dump_file
, ";; Loop is simple\n");
1196 /* Do not unroll loops with branches inside -- it increases number
1198 TODO: this heuristic needs tunning; call inside the loop body
1199 is also relatively good reason to not unroll. */
1200 if (num_loop_branches (loop
) > 1)
1203 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1207 /* Check whether the loop rolls. */
1208 if ((get_estimated_loop_iterations (loop
, &iterations
)
1209 || get_likely_max_loop_iterations (loop
, &iterations
))
1210 && wi::ltu_p (iterations
, 2 * nunroll
))
1213 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1217 /* Success. Now force nunroll to be power of 2, as it seems that this
1218 improves results (partially because of better alignments, partially
1219 because of some dark magic). */
1220 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1223 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1224 loop
->lpt_decision
.times
= i
- 1;
1227 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation does this:
1232 ==> (LOOP->LPT_DECISION.TIMES == 3)
1246 unroll_loop_stupid (class loop
*loop
)
1248 unsigned nunroll
= loop
->lpt_decision
.times
;
1249 class niter_desc
*desc
= get_simple_loop_desc (loop
);
1250 struct opt_info
*opt_info
= NULL
;
1253 if (flag_split_ivs_in_unroller
1254 || flag_variable_expansion_in_unroller
)
1255 opt_info
= analyze_insns_in_loop (loop
);
1257 auto_sbitmap
wont_exit (nunroll
+ 1);
1258 bitmap_clear (wont_exit
);
1259 opt_info_start_duplication (opt_info
);
1261 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1264 DLTHE_FLAG_UPDATE_FREQ
1266 ? DLTHE_RECORD_COPY_NUMBER
1272 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1273 free_opt_info (opt_info
);
1278 /* We indeed may get here provided that there are nontrivial assumptions
1279 for a loop to be really simple. We could update the counts, but the
1280 problem is that we are unable to decide which exit will be taken
1281 (not really true in case the number of iterations is constant,
1282 but no one will do anything with this information, so we do not
1284 desc
->simple_p
= false;
1288 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1289 nunroll
, num_loop_insns (loop
));
1292 /* Returns true if REG is referenced in one nondebug insn in LOOP.
1293 Set *DEBUG_USES to the number of debug insns that reference the
1297 referenced_in_one_insn_in_loop_p (class loop
*loop
, rtx reg
,
1300 basic_block
*body
, bb
;
1305 body
= get_loop_body (loop
);
1306 for (i
= 0; i
< loop
->num_nodes
; i
++)
1310 FOR_BB_INSNS (bb
, insn
)
1311 if (!rtx_referenced_p (reg
, insn
))
1313 else if (DEBUG_INSN_P (insn
))
1315 else if (++count_ref
> 1)
1319 return (count_ref
== 1);
1322 /* Reset the DEBUG_USES debug insns in LOOP that reference REG. */
1325 reset_debug_uses_in_loop (class loop
*loop
, rtx reg
, int debug_uses
)
1327 basic_block
*body
, bb
;
1331 body
= get_loop_body (loop
);
1332 for (i
= 0; debug_uses
&& i
< loop
->num_nodes
; i
++)
1336 FOR_BB_INSNS (bb
, insn
)
1337 if (!DEBUG_INSN_P (insn
) || !rtx_referenced_p (reg
, insn
))
1341 validate_change (insn
, &INSN_VAR_LOCATION_LOC (insn
),
1342 gen_rtx_UNKNOWN_VAR_LOC (), 0);
1350 /* Determine whether INSN contains an accumulator
1351 which can be expanded into separate copies,
1352 one for each copy of the LOOP body.
1354 for (i = 0 ; i < n; i++)
1368 Return NULL if INSN contains no opportunity for expansion of accumulator.
1369 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1370 information and return a pointer to it.
1373 static struct var_to_expand
*
1374 analyze_insn_to_expand_var (class loop
*loop
, rtx_insn
*insn
)
1377 struct var_to_expand
*ves
;
1382 set
= single_set (insn
);
1386 dest
= SET_DEST (set
);
1387 src
= SET_SRC (set
);
1388 code
= GET_CODE (src
);
1390 if (code
!= PLUS
&& code
!= MINUS
&& code
!= MULT
&& code
!= FMA
)
1393 if (FLOAT_MODE_P (GET_MODE (dest
)))
1395 if (!flag_associative_math
)
1397 /* In the case of FMA, we're also changing the rounding. */
1398 if (code
== FMA
&& !flag_unsafe_math_optimizations
)
1402 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1403 in MD. But if there is no optab to generate the insn, we cannot
1404 perform the variable expansion. This can happen if an MD provides
1405 an insn but not a named pattern to generate it, for example to avoid
1406 producing code that needs additional mode switches like for x87/mmx.
1408 So we check have_insn_for which looks for an optab for the operation
1409 in SRC. If it doesn't exist, we can't perform the expansion even
1410 though INSN is valid. */
1411 if (!have_insn_for (code
, GET_MODE (src
)))
1415 && !(GET_CODE (dest
) == SUBREG
1416 && REG_P (SUBREG_REG (dest
))))
1419 /* Find the accumulator use within the operation. */
1422 /* We only support accumulation via FMA in the ADD position. */
1423 if (!rtx_equal_p (dest
, XEXP (src
, 2)))
1427 else if (rtx_equal_p (dest
, XEXP (src
, 0)))
1429 else if (rtx_equal_p (dest
, XEXP (src
, 1)))
1431 /* The method of expansion that we are using; which includes the
1432 initialization of the expansions with zero and the summation of
1433 the expansions at the end of the computation will yield wrong
1434 results for (x = something - x) thus avoid using it in that case. */
1442 /* It must not otherwise be used. */
1445 if (rtx_referenced_p (dest
, XEXP (src
, 0))
1446 || rtx_referenced_p (dest
, XEXP (src
, 1)))
1449 else if (rtx_referenced_p (dest
, XEXP (src
, 1 - accum_pos
)))
1452 /* It must be used in exactly one insn. */
1453 if (!referenced_in_one_insn_in_loop_p (loop
, dest
, &debug_uses
))
1458 fprintf (dump_file
, "\n;; Expanding Accumulator ");
1459 print_rtl (dump_file
, dest
);
1460 fprintf (dump_file
, "\n");
1464 /* Instead of resetting the debug insns, we could replace each
1465 debug use in the loop with the sum or product of all expanded
1466 accumulators. Since we'll only know of all expansions at the
1467 end, we'd have to keep track of which vars_to_expand a debug
1468 insn in the loop references, take note of each copy of the
1469 debug insn during unrolling, and when it's all done, compute
1470 the sum or product of each variable and adjust the original
1471 debug insn and each copy thereof. What a pain! */
1472 reset_debug_uses_in_loop (loop
, dest
, debug_uses
);
1474 /* Record the accumulator to expand. */
1475 ves
= XNEW (struct var_to_expand
);
1477 ves
->reg
= copy_rtx (dest
);
1478 ves
->var_expansions
.create (1);
1480 ves
->op
= GET_CODE (src
);
1481 ves
->expansion_count
= 0;
1482 ves
->reuse_expansion
= 0;
1486 /* Determine whether there is an induction variable in INSN that
1487 we would like to split during unrolling.
1507 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1508 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1511 static struct iv_to_split
*
1512 analyze_iv_to_split_insn (rtx_insn
*insn
)
1516 struct iv_to_split
*ivts
;
1517 scalar_int_mode mode
;
1520 /* For now we just split the basic induction variables. Later this may be
1521 extended for example by selecting also addresses of memory references. */
1522 set
= single_set (insn
);
1526 dest
= SET_DEST (set
);
1527 if (!REG_P (dest
) || !is_a
<scalar_int_mode
> (GET_MODE (dest
), &mode
))
1530 if (!biv_p (insn
, mode
, dest
))
1533 ok
= iv_analyze_result (insn
, dest
, &iv
);
1535 /* This used to be an assert under the assumption that if biv_p returns
1536 true that iv_analyze_result must also return true. However, that
1537 assumption is not strictly correct as evidenced by pr25569.
1539 Returning NULL when iv_analyze_result returns false is safe and
1540 avoids the problems in pr25569 until the iv_analyze_* routines
1541 can be fixed, which is apparently hard and time consuming
1542 according to their author. */
1546 if (iv
.step
== const0_rtx
1547 || iv
.mode
!= iv
.extend_mode
)
1550 /* Record the insn to split. */
1551 ivts
= XNEW (struct iv_to_split
);
1553 ivts
->orig_var
= dest
;
1554 ivts
->base_var
= NULL_RTX
;
1555 ivts
->step
= iv
.step
;
1561 /* Determines which of insns in LOOP can be optimized.
1562 Return a OPT_INFO struct with the relevant hash tables filled
1563 with all insns to be optimized. The FIRST_NEW_BLOCK field
1564 is undefined for the return value. */
1566 static struct opt_info
*
1567 analyze_insns_in_loop (class loop
*loop
)
1569 basic_block
*body
, bb
;
1571 struct opt_info
*opt_info
= XCNEW (struct opt_info
);
1573 struct iv_to_split
*ivts
= NULL
;
1574 struct var_to_expand
*ves
= NULL
;
1575 iv_to_split
**slot1
;
1576 var_to_expand
**slot2
;
1577 auto_vec
<edge
> edges
= get_loop_exit_edges (loop
);
1579 bool can_apply
= false;
1581 iv_analysis_loop_init (loop
);
1583 body
= get_loop_body (loop
);
1585 if (flag_split_ivs_in_unroller
)
1587 opt_info
->insns_to_split
1588 = new hash_table
<iv_split_hasher
> (5 * loop
->num_nodes
);
1589 opt_info
->iv_to_split_head
= NULL
;
1590 opt_info
->iv_to_split_tail
= &opt_info
->iv_to_split_head
;
1593 /* Record the loop exit bb and loop preheader before the unrolling. */
1594 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1596 if (edges
.length () == 1)
1599 if (!(exit
->flags
& EDGE_COMPLEX
))
1601 opt_info
->loop_exit
= split_edge (exit
);
1606 if (flag_variable_expansion_in_unroller
1609 opt_info
->insns_with_var_to_expand
1610 = new hash_table
<var_expand_hasher
> (5 * loop
->num_nodes
);
1611 opt_info
->var_to_expand_head
= NULL
;
1612 opt_info
->var_to_expand_tail
= &opt_info
->var_to_expand_head
;
1615 for (i
= 0; i
< loop
->num_nodes
; i
++)
1618 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1621 FOR_BB_INSNS (bb
, insn
)
1626 if (opt_info
->insns_to_split
)
1627 ivts
= analyze_iv_to_split_insn (insn
);
1631 slot1
= opt_info
->insns_to_split
->find_slot (ivts
, INSERT
);
1632 gcc_assert (*slot1
== NULL
);
1634 *opt_info
->iv_to_split_tail
= ivts
;
1635 opt_info
->iv_to_split_tail
= &ivts
->next
;
1639 if (opt_info
->insns_with_var_to_expand
)
1640 ves
= analyze_insn_to_expand_var (loop
, insn
);
1644 slot2
= opt_info
->insns_with_var_to_expand
->find_slot (ves
, INSERT
);
1645 gcc_assert (*slot2
== NULL
);
1647 *opt_info
->var_to_expand_tail
= ves
;
1648 opt_info
->var_to_expand_tail
= &ves
->next
;
1657 /* Called just before loop duplication. Records start of duplicated area
1661 opt_info_start_duplication (struct opt_info
*opt_info
)
1664 opt_info
->first_new_block
= last_basic_block_for_fn (cfun
);
1667 /* Determine the number of iterations between initialization of the base
1668 variable and the current copy (N_COPY). N_COPIES is the total number
1669 of newly created copies. UNROLLING is true if we are unrolling
1670 (not peeling) the loop. */
1673 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1677 /* If we are unrolling, initialization is done in the original loop
1683 /* If we are peeling, the copy in that the initialization occurs has
1684 number 1. The original loop (number 0) is the last. */
1692 /* Allocate basic variable for the induction variable chain. */
1695 allocate_basic_variable (struct iv_to_split
*ivts
)
1697 rtx expr
= SET_SRC (single_set (ivts
->insn
));
1699 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1702 /* Insert initialization of basic variable of IVTS before INSN, taking
1703 the initial value from INSN. */
1706 insert_base_initialization (struct iv_to_split
*ivts
, rtx_insn
*insn
)
1708 rtx expr
= copy_rtx (SET_SRC (single_set (insn
)));
1712 expr
= force_operand (expr
, ivts
->base_var
);
1713 if (expr
!= ivts
->base_var
)
1714 emit_move_insn (ivts
->base_var
, expr
);
1718 emit_insn_before (seq
, insn
);
1721 /* Replace the use of induction variable described in IVTS in INSN
1722 by base variable + DELTA * step. */
1725 split_iv (struct iv_to_split
*ivts
, rtx_insn
*insn
, unsigned delta
)
1727 rtx expr
, *loc
, incr
, var
;
1729 machine_mode mode
= GET_MODE (ivts
->base_var
);
1732 /* Construct base + DELTA * step. */
1734 expr
= ivts
->base_var
;
1737 incr
= simplify_gen_binary (MULT
, mode
,
1738 copy_rtx (ivts
->step
),
1739 gen_int_mode (delta
, mode
));
1740 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1741 ivts
->base_var
, incr
);
1744 /* Figure out where to do the replacement. */
1745 loc
= &SET_SRC (single_set (insn
));
1747 /* If we can make the replacement right away, we're done. */
1748 if (validate_change (insn
, loc
, expr
, 0))
1751 /* Otherwise, force EXPR into a register and try again. */
1753 var
= gen_reg_rtx (mode
);
1754 expr
= force_operand (expr
, var
);
1756 emit_move_insn (var
, expr
);
1759 emit_insn_before (seq
, insn
);
1761 if (validate_change (insn
, loc
, var
, 0))
1764 /* The last chance. Try recreating the assignment in insn
1765 completely from scratch. */
1766 set
= single_set (insn
);
1771 src
= copy_rtx (SET_SRC (set
));
1772 dest
= copy_rtx (SET_DEST (set
));
1773 src
= force_operand (src
, dest
);
1775 emit_move_insn (dest
, src
);
1779 emit_insn_before (seq
, insn
);
1784 /* Return one expansion of the accumulator recorded in struct VE. */
1787 get_expansion (struct var_to_expand
*ve
)
1791 if (ve
->reuse_expansion
== 0)
1794 reg
= ve
->var_expansions
[ve
->reuse_expansion
- 1];
1796 if (ve
->var_expansions
.length () == (unsigned) ve
->reuse_expansion
)
1797 ve
->reuse_expansion
= 0;
1799 ve
->reuse_expansion
++;
1805 /* Given INSN replace the uses of the accumulator recorded in VE
1806 with a new register. */
1809 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx_insn
*insn
)
1812 bool really_new_expansion
= false;
1814 set
= single_set (insn
);
1817 /* Generate a new register only if the expansion limit has not been
1818 reached. Else reuse an already existing expansion. */
1819 if (param_max_variable_expansions
> ve
->expansion_count
)
1821 really_new_expansion
= true;
1822 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1825 new_reg
= get_expansion (ve
);
1827 validate_replace_rtx_group (SET_DEST (set
), new_reg
, insn
);
1828 if (apply_change_group ())
1829 if (really_new_expansion
)
1831 ve
->var_expansions
.safe_push (new_reg
);
1832 ve
->expansion_count
++;
1836 /* Initialize the variable expansions in loop preheader. PLACE is the
1837 loop-preheader basic block where the initialization of the
1838 expansions should take place. The expansions are initialized with
1839 (-0) when the operation is plus or minus to honor sign zero. This
1840 way we can prevent cases where the sign of the final result is
1841 effected by the sign of the expansion. Here is an example to
1844 for (i = 0 ; i < n; i++)
1858 When SUM is initialized with -zero and SOMETHING is also -zero; the
1859 final result of sum should be -zero thus the expansions sum1 and sum2
1860 should be initialized with -zero as well (otherwise we will get +zero
1861 as the final result). */
1864 insert_var_expansion_initialization (struct var_to_expand
*ve
,
1870 machine_mode mode
= GET_MODE (ve
->reg
);
1871 bool honor_signed_zero_p
= HONOR_SIGNED_ZEROS (mode
);
1873 if (ve
->var_expansions
.length () == 0)
1880 /* Note that we only accumulate FMA via the ADD operand. */
1883 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1885 if (honor_signed_zero_p
)
1886 zero_init
= simplify_gen_unary (NEG
, mode
, CONST0_RTX (mode
), mode
);
1888 zero_init
= CONST0_RTX (mode
);
1889 emit_move_insn (var
, zero_init
);
1894 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1896 zero_init
= CONST1_RTX (GET_MODE (var
));
1897 emit_move_insn (var
, zero_init
);
1908 emit_insn_after (seq
, BB_END (place
));
1911 /* Combine the variable expansions at the loop exit. PLACE is the
1912 loop exit basic block where the summation of the expansions should
1916 combine_var_copies_in_loop_exit (struct var_to_expand
*ve
, basic_block place
)
1920 rtx_insn
*seq
, *insn
;
1923 if (ve
->var_expansions
.length () == 0)
1926 /* ve->reg might be SUBREG or some other non-shareable RTL, and we use
1927 it both here and as the destination of the assignment. */
1928 sum
= copy_rtx (sum
);
1933 /* Note that we only accumulate FMA via the ADD operand. */
1936 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1937 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
), var
, sum
);
1941 FOR_EACH_VEC_ELT (ve
->var_expansions
, i
, var
)
1942 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
), var
, sum
);
1949 expr
= force_operand (sum
, ve
->reg
);
1950 if (expr
!= ve
->reg
)
1951 emit_move_insn (ve
->reg
, expr
);
1955 insn
= BB_HEAD (place
);
1956 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
1957 insn
= NEXT_INSN (insn
);
1959 emit_insn_after (seq
, insn
);
1962 /* Strip away REG_EQUAL notes for IVs we're splitting.
1964 Updating REG_EQUAL notes for IVs we split is tricky: We
1965 cannot tell until after unrolling, DF-rescanning, and liveness
1966 updating, whether an EQ_USE is reached by the split IV while
1967 the IV reg is still live. See PR55006.
1969 ??? We cannot use remove_reg_equal_equiv_notes_for_regno,
1970 because RTL loop-iv requires us to defer rescanning insns and
1971 any notes attached to them. So resort to old techniques... */
1974 maybe_strip_eq_note_for_split_iv (struct opt_info
*opt_info
, rtx_insn
*insn
)
1976 struct iv_to_split
*ivts
;
1977 rtx note
= find_reg_equal_equiv_note (insn
);
1980 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
1981 if (reg_mentioned_p (ivts
->orig_var
, note
))
1983 remove_note (insn
, note
);
1988 /* Apply loop optimizations in loop copies using the
1989 data which gathered during the unrolling. Structure
1990 OPT_INFO record that data.
1992 UNROLLING is true if we unrolled (not peeled) the loop.
1993 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
1994 the loop (as it should happen in complete unrolling, but not in ordinary
1995 peeling of the loop). */
1998 apply_opt_in_copies (struct opt_info
*opt_info
,
1999 unsigned n_copies
, bool unrolling
,
2000 bool rewrite_original_loop
)
2003 basic_block bb
, orig_bb
;
2004 rtx_insn
*insn
, *orig_insn
, *next
;
2005 struct iv_to_split ivts_templ
, *ivts
;
2006 struct var_to_expand ve_templ
, *ves
;
2008 /* Sanity check -- we need to put initialization in the original loop
2010 gcc_assert (!unrolling
|| rewrite_original_loop
);
2012 /* Allocate the basic variables (i0). */
2013 if (opt_info
->insns_to_split
)
2014 for (ivts
= opt_info
->iv_to_split_head
; ivts
; ivts
= ivts
->next
)
2015 allocate_basic_variable (ivts
);
2017 for (i
= opt_info
->first_new_block
;
2018 i
< (unsigned) last_basic_block_for_fn (cfun
);
2021 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2022 orig_bb
= get_bb_original (bb
);
2024 /* bb->aux holds position in copy sequence initialized by
2025 duplicate_loop_to_header_edge. */
2026 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2029 orig_insn
= BB_HEAD (orig_bb
);
2030 FOR_BB_INSNS_SAFE (bb
, insn
, next
)
2033 || (DEBUG_BIND_INSN_P (insn
)
2034 && INSN_VAR_LOCATION_DECL (insn
)
2035 && TREE_CODE (INSN_VAR_LOCATION_DECL (insn
)) == LABEL_DECL
))
2038 while (!INSN_P (orig_insn
)
2039 || (DEBUG_BIND_INSN_P (orig_insn
)
2040 && INSN_VAR_LOCATION_DECL (orig_insn
)
2041 && (TREE_CODE (INSN_VAR_LOCATION_DECL (orig_insn
))
2043 orig_insn
= NEXT_INSN (orig_insn
);
2045 ivts_templ
.insn
= orig_insn
;
2046 ve_templ
.insn
= orig_insn
;
2048 /* Apply splitting iv optimization. */
2049 if (opt_info
->insns_to_split
)
2051 maybe_strip_eq_note_for_split_iv (opt_info
, insn
);
2053 ivts
= opt_info
->insns_to_split
->find (&ivts_templ
);
2057 gcc_assert (GET_CODE (PATTERN (insn
))
2058 == GET_CODE (PATTERN (orig_insn
)));
2061 insert_base_initialization (ivts
, insn
);
2062 split_iv (ivts
, insn
, delta
);
2065 /* Apply variable expansion optimization. */
2066 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2068 ves
= (struct var_to_expand
*)
2069 opt_info
->insns_with_var_to_expand
->find (&ve_templ
);
2072 gcc_assert (GET_CODE (PATTERN (insn
))
2073 == GET_CODE (PATTERN (orig_insn
)));
2074 expand_var_during_unrolling (ves
, insn
);
2077 orig_insn
= NEXT_INSN (orig_insn
);
2081 if (!rewrite_original_loop
)
2084 /* Initialize the variable expansions in the loop preheader
2085 and take care of combining them at the loop exit. */
2086 if (opt_info
->insns_with_var_to_expand
)
2088 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2089 insert_var_expansion_initialization (ves
, opt_info
->loop_preheader
);
2090 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2091 combine_var_copies_in_loop_exit (ves
, opt_info
->loop_exit
);
2094 /* Rewrite also the original loop body. Find them as originals of the blocks
2095 in the last copied iteration, i.e. those that have
2096 get_bb_copy (get_bb_original (bb)) == bb. */
2097 for (i
= opt_info
->first_new_block
;
2098 i
< (unsigned) last_basic_block_for_fn (cfun
);
2101 bb
= BASIC_BLOCK_FOR_FN (cfun
, i
);
2102 orig_bb
= get_bb_original (bb
);
2103 if (get_bb_copy (orig_bb
) != bb
)
2106 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2107 for (orig_insn
= BB_HEAD (orig_bb
);
2108 orig_insn
!= NEXT_INSN (BB_END (bb
));
2111 next
= NEXT_INSN (orig_insn
);
2113 if (!INSN_P (orig_insn
))
2116 ivts_templ
.insn
= orig_insn
;
2117 if (opt_info
->insns_to_split
)
2119 maybe_strip_eq_note_for_split_iv (opt_info
, orig_insn
);
2121 ivts
= (struct iv_to_split
*)
2122 opt_info
->insns_to_split
->find (&ivts_templ
);
2126 insert_base_initialization (ivts
, orig_insn
);
2127 split_iv (ivts
, orig_insn
, delta
);
2136 /* Release OPT_INFO. */
2139 free_opt_info (struct opt_info
*opt_info
)
2141 delete opt_info
->insns_to_split
;
2142 opt_info
->insns_to_split
= NULL
;
2143 if (opt_info
->insns_with_var_to_expand
)
2145 struct var_to_expand
*ves
;
2147 for (ves
= opt_info
->var_to_expand_head
; ves
; ves
= ves
->next
)
2148 ves
->var_expansions
.release ();
2149 delete opt_info
->insns_with_var_to_expand
;
2150 opt_info
->insns_with_var_to_expand
= NULL
;