1 /* Loop unrolling and peeling.
2 Copyright (C) 2002, 2003, 2004, 2005 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 2, 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 COPYING. If not, write to the Free
18 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
37 /* This pass performs loop unrolling and peeling. We only perform these
38 optimizations on innermost loops (with single exception) because
39 the impact on performance is greatest here, and we want to avoid
40 unnecessary code size growth. The gain is caused by greater sequentiality
41 of code, better code to optimize for further passes and in some cases
42 by fewer testings of exit conditions. The main problem is code growth,
43 that impacts performance negatively due to effect of caches.
47 -- complete peeling of once-rolling loops; this is the above mentioned
48 exception, as this causes loop to be cancelled completely and
49 does not cause code growth
50 -- complete peeling of loops that roll (small) constant times.
51 -- simple peeling of first iterations of loops that do not roll much
52 (according to profile feedback)
53 -- unrolling of loops that roll constant times; this is almost always
54 win, as we get rid of exit condition tests.
55 -- unrolling of loops that roll number of times that we can compute
56 in runtime; we also get rid of exit condition tests here, but there
57 is the extra expense for calculating the number of iterations
58 -- simple unrolling of remaining loops; this is performed only if we
59 are asked to, as the gain is questionable in this case and often
60 it may even slow down the code
61 For more detailed descriptions of each of those, see comments at
62 appropriate function below.
64 There is a lot of parameters (defined and described in params.def) that
65 control how much we unroll/peel.
67 ??? A great problem is that we don't have a good way how to determine
68 how many times we should unroll the loop; the experiments I have made
69 showed that this choice may affect performance in order of several %.
72 /* Information about induction variables to split. */
76 rtx insn
; /* The insn in that the induction variable occurs. */
77 rtx base_var
; /* The variable on that the values in the further
78 iterations are based. */
79 rtx step
; /* Step of the induction variable. */
81 unsigned loc
[3]; /* Location where the definition of the induction
82 variable occurs in the insn. For example if
83 N_LOC is 2, the expression is located at
84 XEXP (XEXP (single_set, loc[0]), loc[1]). */
88 DEF_VEC_ALLOC_P(rtx
,heap
);
90 /* Information about accumulators to expand. */
94 rtx insn
; /* The insn in that the variable expansion occurs. */
95 rtx reg
; /* The accumulator which is expanded. */
96 VEC(rtx
,heap
) *var_expansions
; /* The copies of the accumulator which is expanded. */
97 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
99 int expansion_count
; /* Count the number of expansions generated so far. */
100 int reuse_expansion
; /* The expansion we intend to reuse to expand
101 the accumulator. If REUSE_EXPANSION is 0 reuse
102 the original accumulator. Else use
103 var_expansions[REUSE_EXPANSION - 1]. */
106 /* Information about optimization applied in
107 the unrolled loop. */
111 htab_t insns_to_split
; /* A hashtable of insns to split. */
112 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
114 unsigned first_new_block
; /* The first basic block that was
116 basic_block loop_exit
; /* The loop exit basic block. */
117 basic_block loop_preheader
; /* The loop preheader basic block. */
120 static void decide_unrolling_and_peeling (struct loops
*, int);
121 static void peel_loops_completely (struct loops
*, int);
122 static void decide_peel_simple (struct loop
*, int);
123 static void decide_peel_once_rolling (struct loop
*, int);
124 static void decide_peel_completely (struct loop
*, int);
125 static void decide_unroll_stupid (struct loop
*, int);
126 static void decide_unroll_constant_iterations (struct loop
*, int);
127 static void decide_unroll_runtime_iterations (struct loop
*, int);
128 static void peel_loop_simple (struct loops
*, struct loop
*);
129 static void peel_loop_completely (struct loops
*, struct loop
*);
130 static void unroll_loop_stupid (struct loops
*, struct loop
*);
131 static void unroll_loop_constant_iterations (struct loops
*, struct loop
*);
132 static void unroll_loop_runtime_iterations (struct loops
*, struct loop
*);
133 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
134 static void opt_info_start_duplication (struct opt_info
*);
135 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
136 static void free_opt_info (struct opt_info
*);
137 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
138 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
);
139 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
140 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
141 static int insert_var_expansion_initialization (void **, void *);
142 static int combine_var_copies_in_loop_exit (void **, void *);
143 static int release_var_copies (void **, void *);
144 static rtx
get_expansion (struct var_to_expand
*);
146 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
148 unroll_and_peel_loops (struct loops
*loops
, int flags
)
150 struct loop
*loop
, *next
;
153 /* First perform complete loop peeling (it is almost surely a win,
154 and affects parameters for further decision a lot). */
155 peel_loops_completely (loops
, flags
);
157 /* Now decide rest of unrolling and peeling. */
158 decide_unrolling_and_peeling (loops
, flags
);
160 loop
= loops
->tree_root
;
164 /* Scan the loops, inner ones first. */
165 while (loop
!= loops
->tree_root
)
177 /* And perform the appropriate transformations. */
178 switch (loop
->lpt_decision
.decision
)
180 case LPT_PEEL_COMPLETELY
:
183 case LPT_PEEL_SIMPLE
:
184 peel_loop_simple (loops
, loop
);
186 case LPT_UNROLL_CONSTANT
:
187 unroll_loop_constant_iterations (loops
, loop
);
189 case LPT_UNROLL_RUNTIME
:
190 unroll_loop_runtime_iterations (loops
, loop
);
192 case LPT_UNROLL_STUPID
:
193 unroll_loop_stupid (loops
, loop
);
203 #ifdef ENABLE_CHECKING
204 verify_dominators (CDI_DOMINATORS
);
205 verify_loop_structure (loops
);
214 /* Check whether exit of the LOOP is at the end of loop body. */
217 loop_exit_at_end_p (struct loop
*loop
)
219 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
222 if (desc
->in_edge
->dest
!= loop
->latch
)
225 /* Check that the latch is empty. */
226 FOR_BB_INSNS (loop
->latch
, insn
)
235 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
237 peel_loops_completely (struct loops
*loops
, int flags
)
239 struct loop
*loop
, *next
;
241 loop
= loops
->tree_root
;
245 while (loop
!= loops
->tree_root
)
256 loop
->lpt_decision
.decision
= LPT_NONE
;
260 "\n;; *** Considering loop %d for complete peeling ***\n",
263 loop
->ninsns
= num_loop_insns (loop
);
265 decide_peel_once_rolling (loop
, flags
);
266 if (loop
->lpt_decision
.decision
== LPT_NONE
)
267 decide_peel_completely (loop
, flags
);
269 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
271 peel_loop_completely (loops
, loop
);
272 #ifdef ENABLE_CHECKING
273 verify_dominators (CDI_DOMINATORS
);
274 verify_loop_structure (loops
);
281 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
283 decide_unrolling_and_peeling (struct loops
*loops
, int flags
)
285 struct loop
*loop
= loops
->tree_root
, *next
;
290 /* Scan the loops, inner ones first. */
291 while (loop
!= loops
->tree_root
)
302 loop
->lpt_decision
.decision
= LPT_NONE
;
305 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
307 /* Do not peel cold areas. */
308 if (!maybe_hot_bb_p (loop
->header
))
311 fprintf (dump_file
, ";; Not considering loop, cold area\n");
316 /* Can the loop be manipulated? */
317 if (!can_duplicate_loop_p (loop
))
321 ";; Not considering loop, cannot duplicate\n");
326 /* Skip non-innermost loops. */
330 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
335 loop
->ninsns
= num_loop_insns (loop
);
336 loop
->av_ninsns
= average_num_loop_insns (loop
);
338 /* Try transformations one by one in decreasing order of
341 decide_unroll_constant_iterations (loop
, flags
);
342 if (loop
->lpt_decision
.decision
== LPT_NONE
)
343 decide_unroll_runtime_iterations (loop
, flags
);
344 if (loop
->lpt_decision
.decision
== LPT_NONE
)
345 decide_unroll_stupid (loop
, flags
);
346 if (loop
->lpt_decision
.decision
== LPT_NONE
)
347 decide_peel_simple (loop
, flags
);
353 /* Decide whether the LOOP is once rolling and suitable for complete
356 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
358 struct niter_desc
*desc
;
361 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
363 /* Is the loop small enough? */
364 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
367 fprintf (dump_file
, ";; Not considering loop, is too big\n");
371 /* Check for simple loops. */
372 desc
= get_simple_loop_desc (loop
);
374 /* Check number of iterations. */
383 ";; Unable to prove that the loop rolls exactly once\n");
389 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
390 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
393 /* Decide whether the LOOP is suitable for complete peeling. */
395 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
398 struct niter_desc
*desc
;
401 fprintf (dump_file
, "\n;; Considering peeling completely\n");
403 /* Skip non-innermost loops. */
407 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
411 /* Do not peel cold areas. */
412 if (!maybe_hot_bb_p (loop
->header
))
415 fprintf (dump_file
, ";; Not considering loop, cold area\n");
419 /* Can the loop be manipulated? */
420 if (!can_duplicate_loop_p (loop
))
424 ";; Not considering loop, cannot duplicate\n");
428 /* npeel = number of iterations to peel. */
429 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
430 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
431 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
433 /* Is the loop small enough? */
437 fprintf (dump_file
, ";; Not considering loop, is too big\n");
441 /* Check for simple loops. */
442 desc
= get_simple_loop_desc (loop
);
444 /* Check number of iterations. */
452 ";; Unable to prove that the loop iterates constant times\n");
456 if (desc
->niter
> npeel
- 1)
461 ";; Not peeling loop completely, rolls too much (");
462 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
463 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
470 fprintf (dump_file
, ";; Decided to peel loop completely\n");
471 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
474 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
475 completely. The transformation done:
477 for (i = 0; i < 4; i++)
489 peel_loop_completely (struct loops
*loops
, struct loop
*loop
)
492 unsigned HOST_WIDE_INT npeel
;
493 unsigned n_remove_edges
, i
;
494 edge
*remove_edges
, ein
;
495 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
496 struct opt_info
*opt_info
= NULL
;
504 wont_exit
= sbitmap_alloc (npeel
+ 1);
505 sbitmap_ones (wont_exit
);
506 RESET_BIT (wont_exit
, 0);
507 if (desc
->noloop_assumptions
)
508 RESET_BIT (wont_exit
, 1);
510 remove_edges
= xcalloc (npeel
, sizeof (edge
));
513 if (flag_split_ivs_in_unroller
)
514 opt_info
= analyze_insns_in_loop (loop
);
516 opt_info_start_duplication (opt_info
);
517 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
519 wont_exit
, desc
->out_edge
,
520 remove_edges
, &n_remove_edges
,
521 DLTHE_FLAG_UPDATE_FREQ
522 | DLTHE_FLAG_COMPLETTE_PEEL
524 ? DLTHE_RECORD_COPY_NUMBER
: 0));
531 apply_opt_in_copies (opt_info
, npeel
, false, true);
532 free_opt_info (opt_info
);
535 /* Remove the exit edges. */
536 for (i
= 0; i
< n_remove_edges
; i
++)
537 remove_path (loops
, remove_edges
[i
]);
542 free_simple_loop_desc (loop
);
544 /* Now remove the unreachable part of the last iteration and cancel
546 remove_path (loops
, ein
);
549 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
552 /* Decide whether to unroll LOOP iterating constant number of times
556 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
558 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
559 struct niter_desc
*desc
;
561 if (!(flags
& UAP_UNROLL
))
563 /* We were not asked to, just return back silently. */
569 "\n;; Considering unrolling loop with constant "
570 "number of iterations\n");
572 /* nunroll = total number of copies of the original loop body in
573 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
574 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
576 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
577 if (nunroll
> nunroll_by_av
)
578 nunroll
= nunroll_by_av
;
579 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
580 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
582 /* Skip big loops. */
586 fprintf (dump_file
, ";; Not considering loop, is too big\n");
590 /* Check for simple loops. */
591 desc
= get_simple_loop_desc (loop
);
593 /* Check number of iterations. */
594 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
598 ";; Unable to prove that the loop iterates constant times\n");
602 /* Check whether the loop rolls enough to consider. */
603 if (desc
->niter
< 2 * nunroll
)
606 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
610 /* Success; now compute number of iterations to unroll. We alter
611 nunroll so that as few as possible copies of loop body are
612 necessary, while still not decreasing the number of unrollings
613 too much (at most by 1). */
614 best_copies
= 2 * nunroll
+ 10;
617 if (i
- 1 >= desc
->niter
)
620 for (; i
>= nunroll
- 1; i
--)
622 unsigned exit_mod
= desc
->niter
% (i
+ 1);
624 if (!loop_exit_at_end_p (loop
))
625 n_copies
= exit_mod
+ i
+ 1;
626 else if (exit_mod
!= (unsigned) i
627 || desc
->noloop_assumptions
!= NULL_RTX
)
628 n_copies
= exit_mod
+ i
+ 2;
632 if (n_copies
< best_copies
)
634 best_copies
= n_copies
;
640 fprintf (dump_file
, ";; max_unroll %d (%d copies, initial %d).\n",
641 best_unroll
+ 1, best_copies
, nunroll
);
643 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
644 loop
->lpt_decision
.times
= best_unroll
;
648 ";; Decided to unroll the constant times rolling loop, %d times.\n",
649 loop
->lpt_decision
.times
);
652 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
653 times. The transformation does this:
655 for (i = 0; i < 102; i++)
672 unroll_loop_constant_iterations (struct loops
*loops
, struct loop
*loop
)
674 unsigned HOST_WIDE_INT niter
;
677 unsigned n_remove_edges
, i
;
679 unsigned max_unroll
= loop
->lpt_decision
.times
;
680 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
681 bool exit_at_end
= loop_exit_at_end_p (loop
);
682 struct opt_info
*opt_info
= NULL
;
687 /* Should not get here (such loop should be peeled instead). */
688 gcc_assert (niter
> max_unroll
+ 1);
690 exit_mod
= niter
% (max_unroll
+ 1);
692 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
693 sbitmap_ones (wont_exit
);
695 remove_edges
= xcalloc (max_unroll
+ exit_mod
+ 1, sizeof (edge
));
697 if (flag_split_ivs_in_unroller
698 || flag_variable_expansion_in_unroller
)
699 opt_info
= analyze_insns_in_loop (loop
);
703 /* The exit is not at the end of the loop; leave exit test
704 in the first copy, so that the loops that start with test
705 of exit condition have continuous body after unrolling. */
708 fprintf (dump_file
, ";; Condition on beginning of loop.\n");
710 /* Peel exit_mod iterations. */
711 RESET_BIT (wont_exit
, 0);
712 if (desc
->noloop_assumptions
)
713 RESET_BIT (wont_exit
, 1);
717 opt_info_start_duplication (opt_info
);
718 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
720 wont_exit
, desc
->out_edge
,
721 remove_edges
, &n_remove_edges
,
722 DLTHE_FLAG_UPDATE_FREQ
723 | (opt_info
&& exit_mod
> 1
724 ? DLTHE_RECORD_COPY_NUMBER
728 if (opt_info
&& exit_mod
> 1)
729 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
731 desc
->noloop_assumptions
= NULL_RTX
;
732 desc
->niter
-= exit_mod
;
733 desc
->niter_max
-= exit_mod
;
736 SET_BIT (wont_exit
, 1);
740 /* Leave exit test in last copy, for the same reason as above if
741 the loop tests the condition at the end of loop body. */
744 fprintf (dump_file
, ";; Condition on end of loop.\n");
746 /* We know that niter >= max_unroll + 2; so we do not need to care of
747 case when we would exit before reaching the loop. So just peel
748 exit_mod + 1 iterations. */
749 if (exit_mod
!= max_unroll
750 || desc
->noloop_assumptions
)
752 RESET_BIT (wont_exit
, 0);
753 if (desc
->noloop_assumptions
)
754 RESET_BIT (wont_exit
, 1);
756 opt_info_start_duplication (opt_info
);
757 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
759 wont_exit
, desc
->out_edge
,
760 remove_edges
, &n_remove_edges
,
761 DLTHE_FLAG_UPDATE_FREQ
762 | (opt_info
&& exit_mod
> 0
763 ? DLTHE_RECORD_COPY_NUMBER
767 if (opt_info
&& exit_mod
> 0)
768 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
770 desc
->niter
-= exit_mod
+ 1;
771 desc
->niter_max
-= exit_mod
+ 1;
772 desc
->noloop_assumptions
= NULL_RTX
;
774 SET_BIT (wont_exit
, 0);
775 SET_BIT (wont_exit
, 1);
778 RESET_BIT (wont_exit
, max_unroll
);
781 /* Now unroll the loop. */
783 opt_info_start_duplication (opt_info
);
784 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
786 wont_exit
, desc
->out_edge
,
787 remove_edges
, &n_remove_edges
,
788 DLTHE_FLAG_UPDATE_FREQ
790 ? DLTHE_RECORD_COPY_NUMBER
796 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
797 free_opt_info (opt_info
);
804 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
805 /* Find a new in and out edge; they are in the last copy we have made. */
807 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
809 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
810 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
814 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
815 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
819 desc
->niter
/= max_unroll
+ 1;
820 desc
->niter_max
/= max_unroll
+ 1;
821 desc
->niter_expr
= GEN_INT (desc
->niter
);
823 /* Remove the edges. */
824 for (i
= 0; i
< n_remove_edges
; i
++)
825 remove_path (loops
, remove_edges
[i
]);
830 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
831 max_unroll
, num_loop_insns (loop
));
834 /* Decide whether to unroll LOOP iterating runtime computable number of times
837 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
839 unsigned nunroll
, nunroll_by_av
, i
;
840 struct niter_desc
*desc
;
842 if (!(flags
& UAP_UNROLL
))
844 /* We were not asked to, just return back silently. */
850 "\n;; Considering unrolling loop with runtime "
851 "computable number of iterations\n");
853 /* nunroll = total number of copies of the original loop body in
854 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
855 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
856 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
857 if (nunroll
> nunroll_by_av
)
858 nunroll
= nunroll_by_av
;
859 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
860 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
862 /* Skip big loops. */
866 fprintf (dump_file
, ";; Not considering loop, is too big\n");
870 /* Check for simple loops. */
871 desc
= get_simple_loop_desc (loop
);
873 /* Check simpleness. */
874 if (!desc
->simple_p
|| desc
->assumptions
)
878 ";; Unable to prove that the number of iterations "
879 "can be counted in runtime\n");
883 if (desc
->const_iter
)
886 fprintf (dump_file
, ";; Loop iterates constant times\n");
890 /* If we have profile feedback, check whether the loop rolls. */
891 if (loop
->header
->count
&& expected_loop_iterations (loop
) < 2 * nunroll
)
894 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
898 /* Success; now force nunroll to be power of 2, as we are unable to
899 cope with overflows in computation of number of iterations. */
900 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
903 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
904 loop
->lpt_decision
.times
= i
- 1;
908 ";; Decided to unroll the runtime computable "
909 "times rolling loop, %d times.\n",
910 loop
->lpt_decision
.times
);
913 /* Unroll LOOP for that we are able to count number of iterations in runtime
914 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
915 extra care for case n < 0):
917 for (i = 0; i < n; i++)
945 unroll_loop_runtime_iterations (struct loops
*loops
, struct loop
*loop
)
947 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
949 basic_block preheader
, *body
, *dom_bbs
, swtch
, ezc_swtch
;
953 unsigned n_peel
, n_remove_edges
;
954 edge
*remove_edges
, e
;
955 bool extra_zero_check
, last_may_exit
;
956 unsigned max_unroll
= loop
->lpt_decision
.times
;
957 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
958 bool exit_at_end
= loop_exit_at_end_p (loop
);
959 struct opt_info
*opt_info
= NULL
;
962 if (flag_split_ivs_in_unroller
963 || flag_variable_expansion_in_unroller
)
964 opt_info
= analyze_insns_in_loop (loop
);
966 /* Remember blocks whose dominators will have to be updated. */
967 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
970 body
= get_loop_body (loop
);
971 for (i
= 0; i
< loop
->num_nodes
; i
++)
976 nldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
], &ldom
);
977 for (j
= 0; j
< nldom
; j
++)
978 if (!flow_bb_inside_loop_p (loop
, ldom
[j
]))
979 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
987 /* Leave exit in first copy (for explanation why see comment in
988 unroll_loop_constant_iterations). */
990 n_peel
= max_unroll
- 1;
991 extra_zero_check
= true;
992 last_may_exit
= false;
996 /* Leave exit in last copy (for explanation why see comment in
997 unroll_loop_constant_iterations). */
998 may_exit_copy
= max_unroll
;
1000 extra_zero_check
= false;
1001 last_may_exit
= true;
1004 /* Get expression for number of iterations. */
1006 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
1007 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
1009 emit_move_insn (niter
, tmp
);
1011 /* Count modulo by ANDing it with max_unroll; we use the fact that
1012 the number of unrollings is a power of two, and thus this is correct
1013 even if there is overflow in the computation. */
1014 niter
= expand_simple_binop (desc
->mode
, AND
,
1016 GEN_INT (max_unroll
),
1017 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1019 init_code
= get_insns ();
1022 /* Precondition the loop. */
1023 loop_split_edge_with (loop_preheader_edge (loop
), init_code
);
1025 remove_edges
= xcalloc (max_unroll
+ n_peel
+ 1, sizeof (edge
));
1028 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1030 /* Peel the first copy of loop body (almost always we must leave exit test
1031 here; the only exception is when we have extra zero check and the number
1032 of iterations is reliable. Also record the place of (possible) extra
1034 sbitmap_zero (wont_exit
);
1035 if (extra_zero_check
1036 && !desc
->noloop_assumptions
)
1037 SET_BIT (wont_exit
, 1);
1038 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1039 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1041 wont_exit
, desc
->out_edge
,
1042 remove_edges
, &n_remove_edges
,
1043 DLTHE_FLAG_UPDATE_FREQ
);
1046 /* Record the place where switch will be built for preconditioning. */
1047 swtch
= loop_split_edge_with (loop_preheader_edge (loop
),
1050 for (i
= 0; i
< n_peel
; i
++)
1052 /* Peel the copy. */
1053 sbitmap_zero (wont_exit
);
1054 if (i
!= n_peel
- 1 || !last_may_exit
)
1055 SET_BIT (wont_exit
, 1);
1056 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1058 wont_exit
, desc
->out_edge
,
1059 remove_edges
, &n_remove_edges
,
1060 DLTHE_FLAG_UPDATE_FREQ
);
1063 /* Create item for switch. */
1064 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1065 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1067 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1068 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1069 block_label (preheader
), p
,
1072 swtch
= loop_split_edge_with (single_pred_edge (swtch
), branch_code
);
1073 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1074 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1075 e
= make_edge (swtch
, preheader
,
1076 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1080 if (extra_zero_check
)
1082 /* Add branch for zero iterations. */
1083 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1085 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1086 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1087 block_label (preheader
), p
,
1090 swtch
= loop_split_edge_with (single_succ_edge (swtch
), branch_code
);
1091 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1092 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1093 e
= make_edge (swtch
, preheader
,
1094 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1098 /* Recount dominators for outer blocks. */
1099 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
1101 /* And unroll loop. */
1103 sbitmap_ones (wont_exit
);
1104 RESET_BIT (wont_exit
, may_exit_copy
);
1105 opt_info_start_duplication (opt_info
);
1107 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1109 wont_exit
, desc
->out_edge
,
1110 remove_edges
, &n_remove_edges
,
1111 DLTHE_FLAG_UPDATE_FREQ
1113 ? DLTHE_RECORD_COPY_NUMBER
1119 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1120 free_opt_info (opt_info
);
1127 basic_block exit_block
= get_bb_copy (desc
->in_edge
->src
);
1128 /* Find a new in and out edge; they are in the last copy we have
1131 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1133 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1134 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1138 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1139 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1143 /* Remove the edges. */
1144 for (i
= 0; i
< n_remove_edges
; i
++)
1145 remove_path (loops
, remove_edges
[i
]);
1146 free (remove_edges
);
1148 /* We must be careful when updating the number of iterations due to
1149 preconditioning and the fact that the value must be valid at entry
1150 of the loop. After passing through the above code, we see that
1151 the correct new number of iterations is this: */
1152 gcc_assert (!desc
->const_iter
);
1154 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1155 GEN_INT (max_unroll
+ 1));
1156 desc
->niter_max
/= max_unroll
+ 1;
1160 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1161 desc
->noloop_assumptions
= NULL_RTX
;
1167 ";; Unrolled loop %d times, counting # of iterations "
1168 "in runtime, %i insns\n",
1169 max_unroll
, num_loop_insns (loop
));
1172 /* Decide whether to simply peel LOOP and how much. */
1174 decide_peel_simple (struct loop
*loop
, int flags
)
1177 struct niter_desc
*desc
;
1179 if (!(flags
& UAP_PEEL
))
1181 /* We were not asked to, just return back silently. */
1186 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1188 /* npeel = number of iterations to peel. */
1189 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1190 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1191 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1193 /* Skip big loops. */
1197 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1201 /* Check for simple loops. */
1202 desc
= get_simple_loop_desc (loop
);
1204 /* Check number of iterations. */
1205 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1208 fprintf (dump_file
, ";; Loop iterates constant times\n");
1212 /* Do not simply peel loops with branches inside -- it increases number
1214 if (num_loop_branches (loop
) > 1)
1217 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1221 if (loop
->header
->count
)
1223 unsigned niter
= expected_loop_iterations (loop
);
1224 if (niter
+ 1 > npeel
)
1228 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1229 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1230 (HOST_WIDEST_INT
) (niter
+ 1));
1231 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1240 /* For now we have no good heuristics to decide whether loop peeling
1241 will be effective, so disable it. */
1244 ";; Not peeling loop, no evidence it will be profitable\n");
1249 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1250 loop
->lpt_decision
.times
= npeel
;
1253 fprintf (dump_file
, ";; Decided to simply peel the loop, %d times.\n",
1254 loop
->lpt_decision
.times
);
1257 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1263 if (!cond) goto end;
1265 if (!cond) goto end;
1272 peel_loop_simple (struct loops
*loops
, struct loop
*loop
)
1275 unsigned npeel
= loop
->lpt_decision
.times
;
1276 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1277 struct opt_info
*opt_info
= NULL
;
1280 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1281 opt_info
= analyze_insns_in_loop (loop
);
1283 wont_exit
= sbitmap_alloc (npeel
+ 1);
1284 sbitmap_zero (wont_exit
);
1286 opt_info_start_duplication (opt_info
);
1288 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1289 loops
, npeel
, wont_exit
,
1291 NULL
, DLTHE_FLAG_UPDATE_FREQ
1293 ? DLTHE_RECORD_COPY_NUMBER
1301 apply_opt_in_copies (opt_info
, npeel
, false, false);
1302 free_opt_info (opt_info
);
1307 if (desc
->const_iter
)
1309 desc
->niter
-= npeel
;
1310 desc
->niter_expr
= GEN_INT (desc
->niter
);
1311 desc
->noloop_assumptions
= NULL_RTX
;
1315 /* We cannot just update niter_expr, as its value might be clobbered
1316 inside loop. We could handle this by counting the number into
1317 temporary just like we do in runtime unrolling, but it does not
1319 free_simple_loop_desc (loop
);
1323 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1326 /* Decide whether to unroll LOOP stupidly and how much. */
1328 decide_unroll_stupid (struct loop
*loop
, int flags
)
1330 unsigned nunroll
, nunroll_by_av
, i
;
1331 struct niter_desc
*desc
;
1333 if (!(flags
& UAP_UNROLL_ALL
))
1335 /* We were not asked to, just return back silently. */
1340 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1342 /* nunroll = total number of copies of the original loop body in
1343 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1344 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1346 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1347 if (nunroll
> nunroll_by_av
)
1348 nunroll
= nunroll_by_av
;
1349 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1350 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1352 /* Skip big loops. */
1356 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1360 /* Check for simple loops. */
1361 desc
= get_simple_loop_desc (loop
);
1363 /* Check simpleness. */
1364 if (desc
->simple_p
&& !desc
->assumptions
)
1367 fprintf (dump_file
, ";; The loop is simple\n");
1371 /* Do not unroll loops with branches inside -- it increases number
1373 if (num_loop_branches (loop
) > 1)
1376 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1380 /* If we have profile feedback, check whether the loop rolls. */
1381 if (loop
->header
->count
1382 && expected_loop_iterations (loop
) < 2 * nunroll
)
1385 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1389 /* Success. Now force nunroll to be power of 2, as it seems that this
1390 improves results (partially because of better alignments, partially
1391 because of some dark magic). */
1392 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1395 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1396 loop
->lpt_decision
.times
= i
- 1;
1400 ";; Decided to unroll the loop stupidly, %d times.\n",
1401 loop
->lpt_decision
.times
);
1404 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1422 unroll_loop_stupid (struct loops
*loops
, struct loop
*loop
)
1425 unsigned nunroll
= loop
->lpt_decision
.times
;
1426 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1427 struct opt_info
*opt_info
= NULL
;
1430 if (flag_split_ivs_in_unroller
1431 || flag_variable_expansion_in_unroller
)
1432 opt_info
= analyze_insns_in_loop (loop
);
1435 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1436 sbitmap_zero (wont_exit
);
1437 opt_info_start_duplication (opt_info
);
1439 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1440 loops
, nunroll
, wont_exit
,
1442 DLTHE_FLAG_UPDATE_FREQ
1444 ? DLTHE_RECORD_COPY_NUMBER
1450 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1451 free_opt_info (opt_info
);
1458 /* We indeed may get here provided that there are nontrivial assumptions
1459 for a loop to be really simple. We could update the counts, but the
1460 problem is that we are unable to decide which exit will be taken
1461 (not really true in case the number of iterations is constant,
1462 but noone will do anything with this information, so we do not
1464 desc
->simple_p
= false;
1468 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1469 nunroll
, num_loop_insns (loop
));
1472 /* A hash function for information about insns to split. */
1475 si_info_hash (const void *ivts
)
1477 return htab_hash_pointer (((struct iv_to_split
*) ivts
)->insn
);
1480 /* An equality functions for information about insns to split. */
1483 si_info_eq (const void *ivts1
, const void *ivts2
)
1485 const struct iv_to_split
*i1
= ivts1
;
1486 const struct iv_to_split
*i2
= ivts2
;
1488 return i1
->insn
== i2
->insn
;
1491 /* Return a hash for VES, which is really a "var_to_expand *". */
1494 ve_info_hash (const void *ves
)
1496 return htab_hash_pointer (((struct var_to_expand
*) ves
)->insn
);
1499 /* Return true if IVTS1 and IVTS2 (which are really both of type
1500 "var_to_expand *") refer to the same instruction. */
1503 ve_info_eq (const void *ivts1
, const void *ivts2
)
1505 const struct var_to_expand
*i1
= ivts1
;
1506 const struct var_to_expand
*i2
= ivts2
;
1508 return i1
->insn
== i2
->insn
;
1511 /* Returns true if REG is referenced in one insn in LOOP. */
1514 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
)
1516 basic_block
*body
, bb
;
1521 body
= get_loop_body (loop
);
1522 for (i
= 0; i
< loop
->num_nodes
; i
++)
1526 FOR_BB_INSNS (bb
, insn
)
1528 if (rtx_referenced_p (reg
, insn
))
1532 return (count_ref
== 1);
1535 /* Determine whether INSN contains an accumulator
1536 which can be expanded into separate copies,
1537 one for each copy of the LOOP body.
1539 for (i = 0 ; i < n; i++)
1553 Return NULL if INSN contains no opportunity for expansion of accumulator.
1554 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1555 information and return a pointer to it.
1558 static struct var_to_expand
*
1559 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1561 rtx set
, dest
, src
, op1
;
1562 struct var_to_expand
*ves
;
1563 enum machine_mode mode1
, mode2
;
1565 set
= single_set (insn
);
1569 dest
= SET_DEST (set
);
1570 src
= SET_SRC (set
);
1572 if (GET_CODE (src
) != PLUS
1573 && GET_CODE (src
) != MINUS
1574 && GET_CODE (src
) != MULT
)
1577 /* Hmm, this is a bit paradoxical. We know that INSN is a valid insn
1578 in MD. But if there is no optab to generate the insn, we can not
1579 perform the variable expansion. This can happen if an MD provides
1580 an insn but not a named pattern to generate it, for example to avoid
1581 producing code that needs additional mode switches like for x87/mmx.
1583 So we check have_insn_for which looks for an optab for the operation
1584 in SRC. If it doesn't exist, we can't perform the expansion even
1585 though INSN is valid. */
1586 if (!have_insn_for (GET_CODE (src
), GET_MODE (src
)))
1592 op1
= XEXP (src
, 0);
1595 && !(GET_CODE (dest
) == SUBREG
1596 && REG_P (SUBREG_REG (dest
))))
1599 if (!rtx_equal_p (dest
, op1
))
1602 if (!referenced_in_one_insn_in_loop_p (loop
, dest
))
1605 if (rtx_referenced_p (dest
, XEXP (src
, 1)))
1608 mode1
= GET_MODE (dest
);
1609 mode2
= GET_MODE (XEXP (src
, 1));
1610 if ((FLOAT_MODE_P (mode1
)
1611 || FLOAT_MODE_P (mode2
))
1612 && !flag_unsafe_math_optimizations
)
1615 /* Record the accumulator to expand. */
1616 ves
= xmalloc (sizeof (struct var_to_expand
));
1618 ves
->var_expansions
= VEC_alloc (rtx
, heap
, 1);
1619 ves
->reg
= copy_rtx (dest
);
1620 ves
->op
= GET_CODE (src
);
1621 ves
->expansion_count
= 0;
1622 ves
->reuse_expansion
= 0;
1626 /* Determine whether there is an induction variable in INSN that
1627 we would like to split during unrolling.
1647 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1648 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1651 static struct iv_to_split
*
1652 analyze_iv_to_split_insn (rtx insn
)
1656 struct iv_to_split
*ivts
;
1659 /* For now we just split the basic induction variables. Later this may be
1660 extended for example by selecting also addresses of memory references. */
1661 set
= single_set (insn
);
1665 dest
= SET_DEST (set
);
1669 if (!biv_p (insn
, dest
))
1672 ok
= iv_analyze_result (insn
, dest
, &iv
);
1675 if (iv
.step
== const0_rtx
1676 || iv
.mode
!= iv
.extend_mode
)
1679 /* Record the insn to split. */
1680 ivts
= xmalloc (sizeof (struct iv_to_split
));
1682 ivts
->base_var
= NULL_RTX
;
1683 ivts
->step
= iv
.step
;
1690 /* Determines which of insns in LOOP can be optimized.
1691 Return a OPT_INFO struct with the relevant hash tables filled
1692 with all insns to be optimized. The FIRST_NEW_BLOCK field
1693 is undefined for the return value. */
1695 static struct opt_info
*
1696 analyze_insns_in_loop (struct loop
*loop
)
1698 basic_block
*body
, bb
;
1699 unsigned i
, num_edges
= 0;
1700 struct opt_info
*opt_info
= xcalloc (1, sizeof (struct opt_info
));
1702 struct iv_to_split
*ivts
= NULL
;
1703 struct var_to_expand
*ves
= NULL
;
1706 edge
*edges
= get_loop_exit_edges (loop
, &num_edges
);
1707 bool can_apply
= false;
1709 iv_analysis_loop_init (loop
);
1711 body
= get_loop_body (loop
);
1713 if (flag_split_ivs_in_unroller
)
1714 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1715 si_info_hash
, si_info_eq
, free
);
1717 /* Record the loop exit bb and loop preheader before the unrolling. */
1718 if (!loop_preheader_edge (loop
)->src
)
1720 loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1721 opt_info
->loop_preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1724 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1727 && !(edges
[0]->flags
& EDGE_COMPLEX
))
1729 opt_info
->loop_exit
= loop_split_edge_with (edges
[0], NULL_RTX
);
1733 if (flag_variable_expansion_in_unroller
1735 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1736 ve_info_hash
, ve_info_eq
, free
);
1738 for (i
= 0; i
< loop
->num_nodes
; i
++)
1741 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1744 FOR_BB_INSNS (bb
, insn
)
1749 if (opt_info
->insns_to_split
)
1750 ivts
= analyze_iv_to_split_insn (insn
);
1754 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1759 if (opt_info
->insns_with_var_to_expand
)
1760 ves
= analyze_insn_to_expand_var (loop
, insn
);
1764 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1775 /* Called just before loop duplication. Records start of duplicated area
1779 opt_info_start_duplication (struct opt_info
*opt_info
)
1782 opt_info
->first_new_block
= last_basic_block
;
1785 /* Determine the number of iterations between initialization of the base
1786 variable and the current copy (N_COPY). N_COPIES is the total number
1787 of newly created copies. UNROLLING is true if we are unrolling
1788 (not peeling) the loop. */
1791 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1795 /* If we are unrolling, initialization is done in the original loop
1801 /* If we are peeling, the copy in that the initialization occurs has
1802 number 1. The original loop (number 0) is the last. */
1810 /* Locate in EXPR the expression corresponding to the location recorded
1811 in IVTS, and return a pointer to the RTX for this location. */
1814 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1819 for (i
= 0; i
< ivts
->n_loc
; i
++)
1820 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1825 /* Allocate basic variable for the induction variable chain. Callback for
1829 allocate_basic_variable (void **slot
, void *data ATTRIBUTE_UNUSED
)
1831 struct iv_to_split
*ivts
= *slot
;
1832 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1834 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1839 /* Insert initialization of basic variable of IVTS before INSN, taking
1840 the initial value from INSN. */
1843 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
1845 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
1849 expr
= force_operand (expr
, ivts
->base_var
);
1850 if (expr
!= ivts
->base_var
)
1851 emit_move_insn (ivts
->base_var
, expr
);
1855 emit_insn_before (seq
, insn
);
1858 /* Replace the use of induction variable described in IVTS in INSN
1859 by base variable + DELTA * step. */
1862 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
1864 rtx expr
, *loc
, seq
, incr
, var
;
1865 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
1868 /* Construct base + DELTA * step. */
1870 expr
= ivts
->base_var
;
1873 incr
= simplify_gen_binary (MULT
, mode
,
1874 ivts
->step
, gen_int_mode (delta
, mode
));
1875 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1876 ivts
->base_var
, incr
);
1879 /* Figure out where to do the replacement. */
1880 loc
= get_ivts_expr (single_set (insn
), ivts
);
1882 /* If we can make the replacement right away, we're done. */
1883 if (validate_change (insn
, loc
, expr
, 0))
1886 /* Otherwise, force EXPR into a register and try again. */
1888 var
= gen_reg_rtx (mode
);
1889 expr
= force_operand (expr
, var
);
1891 emit_move_insn (var
, expr
);
1894 emit_insn_before (seq
, insn
);
1896 if (validate_change (insn
, loc
, var
, 0))
1899 /* The last chance. Try recreating the assignment in insn
1900 completely from scratch. */
1901 set
= single_set (insn
);
1906 src
= copy_rtx (SET_SRC (set
));
1907 dest
= copy_rtx (SET_DEST (set
));
1908 src
= force_operand (src
, dest
);
1910 emit_move_insn (dest
, src
);
1914 emit_insn_before (seq
, insn
);
1919 /* Return one expansion of the accumulator recorded in struct VE. */
1922 get_expansion (struct var_to_expand
*ve
)
1926 if (ve
->reuse_expansion
== 0)
1929 reg
= VEC_index (rtx
, ve
->var_expansions
, ve
->reuse_expansion
- 1);
1931 if (VEC_length (rtx
, ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
1932 ve
->reuse_expansion
= 0;
1934 ve
->reuse_expansion
++;
1940 /* Given INSN replace the uses of the accumulator recorded in VE
1941 with a new register. */
1944 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
1947 bool really_new_expansion
= false;
1949 set
= single_set (insn
);
1952 /* Generate a new register only if the expansion limit has not been
1953 reached. Else reuse an already existing expansion. */
1954 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
1956 really_new_expansion
= true;
1957 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1960 new_reg
= get_expansion (ve
);
1962 validate_change (insn
, &SET_DEST (set
), new_reg
, 1);
1963 validate_change (insn
, &XEXP (SET_SRC (set
), 0), new_reg
, 1);
1965 if (apply_change_group ())
1966 if (really_new_expansion
)
1968 VEC_safe_push (rtx
, heap
, ve
->var_expansions
, new_reg
);
1969 ve
->expansion_count
++;
1973 /* Initialize the variable expansions in loop preheader.
1974 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1975 basic block where the initialization of the expansions
1976 should take place. */
1979 insert_var_expansion_initialization (void **slot
, void *place_p
)
1981 struct var_to_expand
*ve
= *slot
;
1982 basic_block place
= (basic_block
)place_p
;
1983 rtx seq
, var
, zero_init
, insn
;
1986 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
1990 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1991 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
1993 zero_init
= CONST0_RTX (GET_MODE (var
));
1994 emit_move_insn (var
, zero_init
);
1996 else if (ve
->op
== MULT
)
1997 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
1999 zero_init
= CONST1_RTX (GET_MODE (var
));
2000 emit_move_insn (var
, zero_init
);
2006 insn
= BB_HEAD (place
);
2007 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2008 insn
= NEXT_INSN (insn
);
2010 emit_insn_after (seq
, insn
);
2011 /* Continue traversing the hash table. */
2015 /* Combine the variable expansions at the loop exit.
2016 Callbacks for htab_traverse. PLACE_P is the loop exit
2017 basic block where the summation of the expansions should
2021 combine_var_copies_in_loop_exit (void **slot
, void *place_p
)
2023 struct var_to_expand
*ve
= *slot
;
2024 basic_block place
= (basic_block
)place_p
;
2026 rtx expr
, seq
, var
, insn
;
2029 if (VEC_length (rtx
, ve
->var_expansions
) == 0)
2033 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
2034 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2036 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
),
2039 else if (ve
->op
== MULT
)
2040 for (i
= 0; VEC_iterate (rtx
, ve
->var_expansions
, i
, var
); i
++)
2042 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
),
2046 expr
= force_operand (sum
, ve
->reg
);
2047 if (expr
!= ve
->reg
)
2048 emit_move_insn (ve
->reg
, expr
);
2052 insn
= BB_HEAD (place
);
2053 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2054 insn
= NEXT_INSN (insn
);
2056 emit_insn_after (seq
, insn
);
2058 /* Continue traversing the hash table. */
2062 /* Apply loop optimizations in loop copies using the
2063 data which gathered during the unrolling. Structure
2064 OPT_INFO record that data.
2066 UNROLLING is true if we unrolled (not peeled) the loop.
2067 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2068 the loop (as it should happen in complete unrolling, but not in ordinary
2069 peeling of the loop). */
2072 apply_opt_in_copies (struct opt_info
*opt_info
,
2073 unsigned n_copies
, bool unrolling
,
2074 bool rewrite_original_loop
)
2077 basic_block bb
, orig_bb
;
2078 rtx insn
, orig_insn
, next
;
2079 struct iv_to_split ivts_templ
, *ivts
;
2080 struct var_to_expand ve_templ
, *ves
;
2082 /* Sanity check -- we need to put initialization in the original loop
2084 gcc_assert (!unrolling
|| rewrite_original_loop
);
2086 /* Allocate the basic variables (i0). */
2087 if (opt_info
->insns_to_split
)
2088 htab_traverse (opt_info
->insns_to_split
, allocate_basic_variable
, NULL
);
2090 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2092 bb
= BASIC_BLOCK (i
);
2093 orig_bb
= get_bb_original (bb
);
2095 /* bb->aux holds position in copy sequence initialized by
2096 duplicate_loop_to_header_edge. */
2097 delta
= determine_split_iv_delta ((size_t)bb
->aux
, n_copies
,
2100 orig_insn
= BB_HEAD (orig_bb
);
2101 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2103 next
= NEXT_INSN (insn
);
2107 while (!INSN_P (orig_insn
))
2108 orig_insn
= NEXT_INSN (orig_insn
);
2110 ivts_templ
.insn
= orig_insn
;
2111 ve_templ
.insn
= orig_insn
;
2113 /* Apply splitting iv optimization. */
2114 if (opt_info
->insns_to_split
)
2116 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2120 gcc_assert (GET_CODE (PATTERN (insn
))
2121 == GET_CODE (PATTERN (orig_insn
)));
2124 insert_base_initialization (ivts
, insn
);
2125 split_iv (ivts
, insn
, delta
);
2128 /* Apply variable expansion optimization. */
2129 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2131 ves
= htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2134 gcc_assert (GET_CODE (PATTERN (insn
))
2135 == GET_CODE (PATTERN (orig_insn
)));
2136 expand_var_during_unrolling (ves
, insn
);
2139 orig_insn
= NEXT_INSN (orig_insn
);
2143 if (!rewrite_original_loop
)
2146 /* Initialize the variable expansions in the loop preheader
2147 and take care of combining them at the loop exit. */
2148 if (opt_info
->insns_with_var_to_expand
)
2150 htab_traverse (opt_info
->insns_with_var_to_expand
,
2151 insert_var_expansion_initialization
,
2152 opt_info
->loop_preheader
);
2153 htab_traverse (opt_info
->insns_with_var_to_expand
,
2154 combine_var_copies_in_loop_exit
,
2155 opt_info
->loop_exit
);
2158 /* Rewrite also the original loop body. Find them as originals of the blocks
2159 in the last copied iteration, i.e. those that have
2160 get_bb_copy (get_bb_original (bb)) == bb. */
2161 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2163 bb
= BASIC_BLOCK (i
);
2164 orig_bb
= get_bb_original (bb
);
2165 if (get_bb_copy (orig_bb
) != bb
)
2168 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2169 for (orig_insn
= BB_HEAD (orig_bb
);
2170 orig_insn
!= NEXT_INSN (BB_END (bb
));
2173 next
= NEXT_INSN (orig_insn
);
2175 if (!INSN_P (orig_insn
))
2178 ivts_templ
.insn
= orig_insn
;
2179 if (opt_info
->insns_to_split
)
2181 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2185 insert_base_initialization (ivts
, orig_insn
);
2186 split_iv (ivts
, orig_insn
, delta
);
2195 /* Release the data structures used for the variable expansion
2196 optimization. Callbacks for htab_traverse. */
2199 release_var_copies (void **slot
, void *data ATTRIBUTE_UNUSED
)
2201 struct var_to_expand
*ve
= *slot
;
2203 VEC_free (rtx
, heap
, ve
->var_expansions
);
2205 /* Continue traversing the hash table. */
2209 /* Release OPT_INFO. */
2212 free_opt_info (struct opt_info
*opt_info
)
2214 if (opt_info
->insns_to_split
)
2215 htab_delete (opt_info
->insns_to_split
);
2216 if (opt_info
->insns_with_var_to_expand
)
2218 htab_traverse (opt_info
->insns_with_var_to_expand
,
2219 release_var_copies
, NULL
);
2220 htab_delete (opt_info
->insns_with_var_to_expand
);