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, 59 Temple Place - Suite 330, Boston, MA
23 #include "coretypes.h"
26 #include "hard-reg-set.h"
28 #include "basic-block.h"
30 #include "cfglayout.h"
38 /* This pass performs loop unrolling and peeling. We only perform these
39 optimizations on innermost loops (with single exception) because
40 the impact on performance is greatest here, and we want to avoid
41 unnecessary code size growth. The gain is caused by greater sequentiality
42 of code, better code to optimize for further passes and in some cases
43 by fewer testings of exit conditions. The main problem is code growth,
44 that impacts performance negatively due to effect of caches.
48 -- complete peeling of once-rolling loops; this is the above mentioned
49 exception, as this causes loop to be cancelled completely and
50 does not cause code growth
51 -- complete peeling of loops that roll (small) constant times.
52 -- simple peeling of first iterations of loops that do not roll much
53 (according to profile feedback)
54 -- unrolling of loops that roll constant times; this is almost always
55 win, as we get rid of exit condition tests.
56 -- unrolling of loops that roll number of times that we can compute
57 in runtime; we also get rid of exit condition tests here, but there
58 is the extra expense for calculating the number of iterations
59 -- simple unrolling of remaining loops; this is performed only if we
60 are asked to, as the gain is questionable in this case and often
61 it may even slow down the code
62 For more detailed descriptions of each of those, see comments at
63 appropriate function below.
65 There is a lot of parameters (defined and described in params.def) that
66 control how much we unroll/peel.
68 ??? A great problem is that we don't have a good way how to determine
69 how many times we should unroll the loop; the experiments I have made
70 showed that this choice may affect performance in order of several %.
73 /* Information about induction variables to split. */
77 rtx insn
; /* The insn in that the induction variable occurs. */
78 rtx base_var
; /* The variable on that the values in the further
79 iterations are based. */
80 rtx step
; /* Step of the induction variable. */
82 unsigned loc
[3]; /* Location where the definition of the induction
83 variable occurs in the insn. For example if
84 N_LOC is 2, the expression is located at
85 XEXP (XEXP (single_set, loc[0]), loc[1]). */
88 /* Information about accumulators to expand. */
92 rtx insn
; /* The insn in that the variable expansion occurs. */
93 rtx reg
; /* The accumulator which is expanded. */
94 varray_type var_expansions
; /* The copies of the accumulator which is expanded. */
95 enum rtx_code op
; /* The type of the accumulation - addition, subtraction
97 int expansion_count
; /* Count the number of expansions generated so far. */
98 int reuse_expansion
; /* The expansion we intend to reuse to expand
99 the accumulator. If REUSE_EXPANSION is 0 reuse
100 the original accumulator. Else use
101 var_expansions[REUSE_EXPANSION - 1]. */
104 /* Information about optimization applied in
105 the unrolled loop. */
109 htab_t insns_to_split
; /* A hashtable of insns to split. */
110 htab_t insns_with_var_to_expand
; /* A hashtable of insns with accumulators
112 unsigned first_new_block
; /* The first basic block that was
114 basic_block loop_exit
; /* The loop exit basic block. */
115 basic_block loop_preheader
; /* The loop preheader basic block. */
118 static void decide_unrolling_and_peeling (struct loops
*, int);
119 static void peel_loops_completely (struct loops
*, int);
120 static void decide_peel_simple (struct loop
*, int);
121 static void decide_peel_once_rolling (struct loop
*, int);
122 static void decide_peel_completely (struct loop
*, int);
123 static void decide_unroll_stupid (struct loop
*, int);
124 static void decide_unroll_constant_iterations (struct loop
*, int);
125 static void decide_unroll_runtime_iterations (struct loop
*, int);
126 static void peel_loop_simple (struct loops
*, struct loop
*);
127 static void peel_loop_completely (struct loops
*, struct loop
*);
128 static void unroll_loop_stupid (struct loops
*, struct loop
*);
129 static void unroll_loop_constant_iterations (struct loops
*, struct loop
*);
130 static void unroll_loop_runtime_iterations (struct loops
*, struct loop
*);
131 static struct opt_info
*analyze_insns_in_loop (struct loop
*);
132 static void opt_info_start_duplication (struct opt_info
*);
133 static void apply_opt_in_copies (struct opt_info
*, unsigned, bool, bool);
134 static void free_opt_info (struct opt_info
*);
135 static struct var_to_expand
*analyze_insn_to_expand_var (struct loop
*, rtx
);
136 static bool referenced_in_one_insn_in_loop_p (struct loop
*, rtx
);
137 static struct iv_to_split
*analyze_iv_to_split_insn (rtx
);
138 static void expand_var_during_unrolling (struct var_to_expand
*, rtx
);
139 static int insert_var_expansion_initialization (void **, void *);
140 static int combine_var_copies_in_loop_exit (void **, void *);
141 static int release_var_copies (void **, void *);
142 static rtx
get_expansion (struct var_to_expand
*);
144 /* Unroll and/or peel (depending on FLAGS) LOOPS. */
146 unroll_and_peel_loops (struct loops
*loops
, int flags
)
148 struct loop
*loop
, *next
;
151 /* First perform complete loop peeling (it is almost surely a win,
152 and affects parameters for further decision a lot). */
153 peel_loops_completely (loops
, flags
);
155 /* Now decide rest of unrolling and peeling. */
156 decide_unrolling_and_peeling (loops
, flags
);
158 loop
= loops
->tree_root
;
162 /* Scan the loops, inner ones first. */
163 while (loop
!= loops
->tree_root
)
175 /* And perform the appropriate transformations. */
176 switch (loop
->lpt_decision
.decision
)
178 case LPT_PEEL_COMPLETELY
:
181 case LPT_PEEL_SIMPLE
:
182 peel_loop_simple (loops
, loop
);
184 case LPT_UNROLL_CONSTANT
:
185 unroll_loop_constant_iterations (loops
, loop
);
187 case LPT_UNROLL_RUNTIME
:
188 unroll_loop_runtime_iterations (loops
, loop
);
190 case LPT_UNROLL_STUPID
:
191 unroll_loop_stupid (loops
, loop
);
201 #ifdef ENABLE_CHECKING
202 verify_dominators (CDI_DOMINATORS
);
203 verify_loop_structure (loops
);
212 /* Check whether exit of the LOOP is at the end of loop body. */
215 loop_exit_at_end_p (struct loop
*loop
)
217 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
220 if (desc
->in_edge
->dest
!= loop
->latch
)
223 /* Check that the latch is empty. */
224 FOR_BB_INSNS (loop
->latch
, insn
)
233 /* Check whether to peel LOOPS (depending on FLAGS) completely and do so. */
235 peel_loops_completely (struct loops
*loops
, int flags
)
237 struct loop
*loop
, *next
;
239 loop
= loops
->tree_root
;
243 while (loop
!= loops
->tree_root
)
254 loop
->lpt_decision
.decision
= LPT_NONE
;
258 "\n;; *** Considering loop %d for complete peeling ***\n",
261 loop
->ninsns
= num_loop_insns (loop
);
263 decide_peel_once_rolling (loop
, flags
);
264 if (loop
->lpt_decision
.decision
== LPT_NONE
)
265 decide_peel_completely (loop
, flags
);
267 if (loop
->lpt_decision
.decision
== LPT_PEEL_COMPLETELY
)
269 peel_loop_completely (loops
, loop
);
270 #ifdef ENABLE_CHECKING
271 verify_dominators (CDI_DOMINATORS
);
272 verify_loop_structure (loops
);
279 /* Decide whether unroll or peel LOOPS (depending on FLAGS) and how much. */
281 decide_unrolling_and_peeling (struct loops
*loops
, int flags
)
283 struct loop
*loop
= loops
->tree_root
, *next
;
288 /* Scan the loops, inner ones first. */
289 while (loop
!= loops
->tree_root
)
300 loop
->lpt_decision
.decision
= LPT_NONE
;
303 fprintf (dump_file
, "\n;; *** Considering loop %d ***\n", loop
->num
);
305 /* Do not peel cold areas. */
306 if (!maybe_hot_bb_p (loop
->header
))
309 fprintf (dump_file
, ";; Not considering loop, cold area\n");
314 /* Can the loop be manipulated? */
315 if (!can_duplicate_loop_p (loop
))
319 ";; Not considering loop, cannot duplicate\n");
324 /* Skip non-innermost loops. */
328 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
333 loop
->ninsns
= num_loop_insns (loop
);
334 loop
->av_ninsns
= average_num_loop_insns (loop
);
336 /* Try transformations one by one in decreasing order of
339 decide_unroll_constant_iterations (loop
, flags
);
340 if (loop
->lpt_decision
.decision
== LPT_NONE
)
341 decide_unroll_runtime_iterations (loop
, flags
);
342 if (loop
->lpt_decision
.decision
== LPT_NONE
)
343 decide_unroll_stupid (loop
, flags
);
344 if (loop
->lpt_decision
.decision
== LPT_NONE
)
345 decide_peel_simple (loop
, flags
);
351 /* Decide whether the LOOP is once rolling and suitable for complete
354 decide_peel_once_rolling (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
356 struct niter_desc
*desc
;
359 fprintf (dump_file
, "\n;; Considering peeling once rolling loop\n");
361 /* Is the loop small enough? */
362 if ((unsigned) PARAM_VALUE (PARAM_MAX_ONCE_PEELED_INSNS
) < loop
->ninsns
)
365 fprintf (dump_file
, ";; Not considering loop, is too big\n");
369 /* Check for simple loops. */
370 desc
= get_simple_loop_desc (loop
);
372 /* Check number of iterations. */
380 ";; Unable to prove that the loop rolls exactly once\n");
386 fprintf (dump_file
, ";; Decided to peel exactly once rolling loop\n");
387 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
390 /* Decide whether the LOOP is suitable for complete peeling. */
392 decide_peel_completely (struct loop
*loop
, int flags ATTRIBUTE_UNUSED
)
395 struct niter_desc
*desc
;
398 fprintf (dump_file
, "\n;; Considering peeling completely\n");
400 /* Skip non-innermost loops. */
404 fprintf (dump_file
, ";; Not considering loop, is not innermost\n");
408 /* Do not peel cold areas. */
409 if (!maybe_hot_bb_p (loop
->header
))
412 fprintf (dump_file
, ";; Not considering loop, cold area\n");
416 /* Can the loop be manipulated? */
417 if (!can_duplicate_loop_p (loop
))
421 ";; Not considering loop, cannot duplicate\n");
425 /* npeel = number of iterations to peel. */
426 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEELED_INSNS
) / loop
->ninsns
;
427 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
))
428 npeel
= PARAM_VALUE (PARAM_MAX_COMPLETELY_PEEL_TIMES
);
430 /* Is the loop small enough? */
434 fprintf (dump_file
, ";; Not considering loop, is too big\n");
438 /* Check for simple loops. */
439 desc
= get_simple_loop_desc (loop
);
441 /* Check number of iterations. */
444 || !desc
->const_iter
)
448 ";; Unable to prove that the loop iterates constant times\n");
452 if (desc
->niter
> npeel
- 1)
457 ";; Not peeling loop completely, rolls too much (");
458 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
, desc
->niter
);
459 fprintf (dump_file
, " iterations > %d [maximum peelings])\n", npeel
);
466 fprintf (dump_file
, ";; Decided to peel loop completely\n");
467 loop
->lpt_decision
.decision
= LPT_PEEL_COMPLETELY
;
470 /* Peel all iterations of LOOP, remove exit edges and cancel the loop
471 completely. The transformation done:
473 for (i = 0; i < 4; i++)
485 peel_loop_completely (struct loops
*loops
, struct loop
*loop
)
488 unsigned HOST_WIDE_INT npeel
;
489 unsigned n_remove_edges
, i
;
490 edge
*remove_edges
, ein
;
491 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
492 struct opt_info
*opt_info
= NULL
;
500 wont_exit
= sbitmap_alloc (npeel
+ 1);
501 sbitmap_ones (wont_exit
);
502 RESET_BIT (wont_exit
, 0);
503 if (desc
->noloop_assumptions
)
504 RESET_BIT (wont_exit
, 1);
506 remove_edges
= xcalloc (npeel
, sizeof (edge
));
509 if (flag_split_ivs_in_unroller
)
510 opt_info
= analyze_insns_in_loop (loop
);
512 opt_info_start_duplication (opt_info
);
513 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
515 wont_exit
, desc
->out_edge
,
516 remove_edges
, &n_remove_edges
,
517 DLTHE_FLAG_UPDATE_FREQ
);
524 apply_opt_in_copies (opt_info
, npeel
, false, true);
525 free_opt_info (opt_info
);
528 /* Remove the exit edges. */
529 for (i
= 0; i
< n_remove_edges
; i
++)
530 remove_path (loops
, remove_edges
[i
]);
535 free_simple_loop_desc (loop
);
537 /* Now remove the unreachable part of the last iteration and cancel
539 remove_path (loops
, ein
);
542 fprintf (dump_file
, ";; Peeled loop completely, %d times\n", (int) npeel
);
545 /* Decide whether to unroll LOOP iterating constant number of times
549 decide_unroll_constant_iterations (struct loop
*loop
, int flags
)
551 unsigned nunroll
, nunroll_by_av
, best_copies
, best_unroll
= 0, n_copies
, i
;
552 struct niter_desc
*desc
;
554 if (!(flags
& UAP_UNROLL
))
556 /* We were not asked to, just return back silently. */
562 "\n;; Considering unrolling loop with constant "
563 "number of iterations\n");
565 /* nunroll = total number of copies of the original loop body in
566 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
567 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
569 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
570 if (nunroll
> nunroll_by_av
)
571 nunroll
= nunroll_by_av
;
572 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
573 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
575 /* Skip big loops. */
579 fprintf (dump_file
, ";; Not considering loop, is too big\n");
583 /* Check for simple loops. */
584 desc
= get_simple_loop_desc (loop
);
586 /* Check number of iterations. */
587 if (!desc
->simple_p
|| !desc
->const_iter
|| desc
->assumptions
)
591 ";; Unable to prove that the loop iterates constant times\n");
595 /* Check whether the loop rolls enough to consider. */
596 if (desc
->niter
< 2 * nunroll
)
599 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
603 /* Success; now compute number of iterations to unroll. We alter
604 nunroll so that as few as possible copies of loop body are
605 necessary, while still not decreasing the number of unrollings
606 too much (at most by 1). */
607 best_copies
= 2 * nunroll
+ 10;
610 if (i
- 1 >= desc
->niter
)
613 for (; i
>= nunroll
- 1; i
--)
615 unsigned exit_mod
= desc
->niter
% (i
+ 1);
617 if (!loop_exit_at_end_p (loop
))
618 n_copies
= exit_mod
+ i
+ 1;
619 else if (exit_mod
!= (unsigned) i
620 || desc
->noloop_assumptions
!= NULL_RTX
)
621 n_copies
= exit_mod
+ i
+ 2;
625 if (n_copies
< best_copies
)
627 best_copies
= n_copies
;
633 fprintf (dump_file
, ";; max_unroll %d (%d copies, initial %d).\n",
634 best_unroll
+ 1, best_copies
, nunroll
);
636 loop
->lpt_decision
.decision
= LPT_UNROLL_CONSTANT
;
637 loop
->lpt_decision
.times
= best_unroll
;
641 ";; Decided to unroll the constant times rolling loop, %d times.\n",
642 loop
->lpt_decision
.times
);
645 /* Unroll LOOP with constant number of iterations LOOP->LPT_DECISION.TIMES + 1
646 times. The transformation does this:
648 for (i = 0; i < 102; i++)
665 unroll_loop_constant_iterations (struct loops
*loops
, struct loop
*loop
)
667 unsigned HOST_WIDE_INT niter
;
670 unsigned n_remove_edges
, i
;
672 unsigned max_unroll
= loop
->lpt_decision
.times
;
673 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
674 bool exit_at_end
= loop_exit_at_end_p (loop
);
675 struct opt_info
*opt_info
= NULL
;
680 /* Should not get here (such loop should be peeled instead). */
681 gcc_assert (niter
> max_unroll
+ 1);
683 exit_mod
= niter
% (max_unroll
+ 1);
685 wont_exit
= sbitmap_alloc (max_unroll
+ 1);
686 sbitmap_ones (wont_exit
);
688 remove_edges
= xcalloc (max_unroll
+ exit_mod
+ 1, sizeof (edge
));
690 if (flag_split_ivs_in_unroller
691 || flag_variable_expansion_in_unroller
)
692 opt_info
= analyze_insns_in_loop (loop
);
696 /* The exit is not at the end of the loop; leave exit test
697 in the first copy, so that the loops that start with test
698 of exit condition have continuous body after unrolling. */
701 fprintf (dump_file
, ";; Condition on beginning of loop.\n");
703 /* Peel exit_mod iterations. */
704 RESET_BIT (wont_exit
, 0);
705 if (desc
->noloop_assumptions
)
706 RESET_BIT (wont_exit
, 1);
710 opt_info_start_duplication (opt_info
);
711 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
713 wont_exit
, desc
->out_edge
,
714 remove_edges
, &n_remove_edges
,
715 DLTHE_FLAG_UPDATE_FREQ
);
718 if (opt_info
&& exit_mod
> 1)
719 apply_opt_in_copies (opt_info
, exit_mod
, false, false);
721 desc
->noloop_assumptions
= NULL_RTX
;
722 desc
->niter
-= exit_mod
;
723 desc
->niter_max
-= exit_mod
;
726 SET_BIT (wont_exit
, 1);
730 /* Leave exit test in last copy, for the same reason as above if
731 the loop tests the condition at the end of loop body. */
734 fprintf (dump_file
, ";; Condition on end of loop.\n");
736 /* We know that niter >= max_unroll + 2; so we do not need to care of
737 case when we would exit before reaching the loop. So just peel
738 exit_mod + 1 iterations. */
739 if (exit_mod
!= max_unroll
740 || desc
->noloop_assumptions
)
742 RESET_BIT (wont_exit
, 0);
743 if (desc
->noloop_assumptions
)
744 RESET_BIT (wont_exit
, 1);
746 opt_info_start_duplication (opt_info
);
747 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
749 wont_exit
, desc
->out_edge
,
750 remove_edges
, &n_remove_edges
,
751 DLTHE_FLAG_UPDATE_FREQ
);
754 if (opt_info
&& exit_mod
> 0)
755 apply_opt_in_copies (opt_info
, exit_mod
+ 1, false, false);
757 desc
->niter
-= exit_mod
+ 1;
758 desc
->niter_max
-= exit_mod
+ 1;
759 desc
->noloop_assumptions
= NULL_RTX
;
761 SET_BIT (wont_exit
, 0);
762 SET_BIT (wont_exit
, 1);
765 RESET_BIT (wont_exit
, max_unroll
);
768 /* Now unroll the loop. */
770 opt_info_start_duplication (opt_info
);
771 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
773 wont_exit
, desc
->out_edge
,
774 remove_edges
, &n_remove_edges
,
775 DLTHE_FLAG_UPDATE_FREQ
);
780 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
781 free_opt_info (opt_info
);
788 basic_block exit_block
= desc
->in_edge
->src
->rbi
->copy
;
789 /* Find a new in and out edge; they are in the last copy we have made. */
791 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
793 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
794 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
798 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
799 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
803 desc
->niter
/= max_unroll
+ 1;
804 desc
->niter_max
/= max_unroll
+ 1;
805 desc
->niter_expr
= GEN_INT (desc
->niter
);
807 /* Remove the edges. */
808 for (i
= 0; i
< n_remove_edges
; i
++)
809 remove_path (loops
, remove_edges
[i
]);
814 ";; Unrolled loop %d times, constant # of iterations %i insns\n",
815 max_unroll
, num_loop_insns (loop
));
818 /* Decide whether to unroll LOOP iterating runtime computable number of times
821 decide_unroll_runtime_iterations (struct loop
*loop
, int flags
)
823 unsigned nunroll
, nunroll_by_av
, i
;
824 struct niter_desc
*desc
;
826 if (!(flags
& UAP_UNROLL
))
828 /* We were not asked to, just return back silently. */
834 "\n;; Considering unrolling loop with runtime "
835 "computable number of iterations\n");
837 /* nunroll = total number of copies of the original loop body in
838 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
839 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
840 nunroll_by_av
= PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
841 if (nunroll
> nunroll_by_av
)
842 nunroll
= nunroll_by_av
;
843 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
844 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
846 /* Skip big loops. */
850 fprintf (dump_file
, ";; Not considering loop, is too big\n");
854 /* Check for simple loops. */
855 desc
= get_simple_loop_desc (loop
);
857 /* Check simpleness. */
858 if (!desc
->simple_p
|| desc
->assumptions
)
862 ";; Unable to prove that the number of iterations "
863 "can be counted in runtime\n");
867 if (desc
->const_iter
)
870 fprintf (dump_file
, ";; Loop iterates constant times\n");
874 /* If we have profile feedback, check whether the loop rolls. */
875 if (loop
->header
->count
&& expected_loop_iterations (loop
) < 2 * nunroll
)
878 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
882 /* Success; now force nunroll to be power of 2, as we are unable to
883 cope with overflows in computation of number of iterations. */
884 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
887 loop
->lpt_decision
.decision
= LPT_UNROLL_RUNTIME
;
888 loop
->lpt_decision
.times
= i
- 1;
892 ";; Decided to unroll the runtime computable "
893 "times rolling loop, %d times.\n",
894 loop
->lpt_decision
.times
);
897 /* Unroll LOOP for that we are able to count number of iterations in runtime
898 LOOP->LPT_DECISION.TIMES + 1 times. The transformation does this (with some
899 extra care for case n < 0):
901 for (i = 0; i < n; i++)
929 unroll_loop_runtime_iterations (struct loops
*loops
, struct loop
*loop
)
931 rtx old_niter
, niter
, init_code
, branch_code
, tmp
;
933 basic_block preheader
, *body
, *dom_bbs
, swtch
, ezc_swtch
;
937 unsigned n_peel
, n_remove_edges
;
938 edge
*remove_edges
, e
;
939 bool extra_zero_check
, last_may_exit
;
940 unsigned max_unroll
= loop
->lpt_decision
.times
;
941 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
942 bool exit_at_end
= loop_exit_at_end_p (loop
);
943 struct opt_info
*opt_info
= NULL
;
946 if (flag_split_ivs_in_unroller
947 || flag_variable_expansion_in_unroller
)
948 opt_info
= analyze_insns_in_loop (loop
);
950 /* Remember blocks whose dominators will have to be updated. */
951 dom_bbs
= xcalloc (n_basic_blocks
, sizeof (basic_block
));
954 body
= get_loop_body (loop
);
955 for (i
= 0; i
< loop
->num_nodes
; i
++)
960 nldom
= get_dominated_by (CDI_DOMINATORS
, body
[i
], &ldom
);
961 for (j
= 0; j
< nldom
; j
++)
962 if (!flow_bb_inside_loop_p (loop
, ldom
[j
]))
963 dom_bbs
[n_dom_bbs
++] = ldom
[j
];
971 /* Leave exit in first copy (for explanation why see comment in
972 unroll_loop_constant_iterations). */
974 n_peel
= max_unroll
- 1;
975 extra_zero_check
= true;
976 last_may_exit
= false;
980 /* Leave exit in last copy (for explanation why see comment in
981 unroll_loop_constant_iterations). */
982 may_exit_copy
= max_unroll
;
984 extra_zero_check
= false;
985 last_may_exit
= true;
988 /* Get expression for number of iterations. */
990 old_niter
= niter
= gen_reg_rtx (desc
->mode
);
991 tmp
= force_operand (copy_rtx (desc
->niter_expr
), niter
);
993 emit_move_insn (niter
, tmp
);
995 /* Count modulo by ANDing it with max_unroll; we use the fact that
996 the number of unrollings is a power of two, and thus this is correct
997 even if there is overflow in the computation. */
998 niter
= expand_simple_binop (desc
->mode
, AND
,
1000 GEN_INT (max_unroll
),
1001 NULL_RTX
, 0, OPTAB_LIB_WIDEN
);
1003 init_code
= get_insns ();
1006 /* Precondition the loop. */
1007 loop_split_edge_with (loop_preheader_edge (loop
), init_code
);
1009 remove_edges
= xcalloc (max_unroll
+ n_peel
+ 1, sizeof (edge
));
1012 wont_exit
= sbitmap_alloc (max_unroll
+ 2);
1014 /* Peel the first copy of loop body (almost always we must leave exit test
1015 here; the only exception is when we have extra zero check and the number
1016 of iterations is reliable. Also record the place of (possible) extra
1018 sbitmap_zero (wont_exit
);
1019 if (extra_zero_check
1020 && !desc
->noloop_assumptions
)
1021 SET_BIT (wont_exit
, 1);
1022 ezc_swtch
= loop_preheader_edge (loop
)->src
;
1023 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1025 wont_exit
, desc
->out_edge
,
1026 remove_edges
, &n_remove_edges
,
1027 DLTHE_FLAG_UPDATE_FREQ
);
1030 /* Record the place where switch will be built for preconditioning. */
1031 swtch
= loop_split_edge_with (loop_preheader_edge (loop
),
1034 for (i
= 0; i
< n_peel
; i
++)
1036 /* Peel the copy. */
1037 sbitmap_zero (wont_exit
);
1038 if (i
!= n_peel
- 1 || !last_may_exit
)
1039 SET_BIT (wont_exit
, 1);
1040 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1042 wont_exit
, desc
->out_edge
,
1043 remove_edges
, &n_remove_edges
,
1044 DLTHE_FLAG_UPDATE_FREQ
);
1047 /* Create item for switch. */
1048 j
= n_peel
- i
- (extra_zero_check
? 0 : 1);
1049 p
= REG_BR_PROB_BASE
/ (i
+ 2);
1051 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1052 branch_code
= compare_and_jump_seq (copy_rtx (niter
), GEN_INT (j
), EQ
,
1053 block_label (preheader
), p
,
1056 swtch
= loop_split_edge_with (single_pred_edge (swtch
), branch_code
);
1057 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1058 single_pred_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1059 e
= make_edge (swtch
, preheader
,
1060 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1064 if (extra_zero_check
)
1066 /* Add branch for zero iterations. */
1067 p
= REG_BR_PROB_BASE
/ (max_unroll
+ 1);
1069 preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1070 branch_code
= compare_and_jump_seq (copy_rtx (niter
), const0_rtx
, EQ
,
1071 block_label (preheader
), p
,
1074 swtch
= loop_split_edge_with (single_succ_edge (swtch
), branch_code
);
1075 set_immediate_dominator (CDI_DOMINATORS
, preheader
, swtch
);
1076 single_succ_edge (swtch
)->probability
= REG_BR_PROB_BASE
- p
;
1077 e
= make_edge (swtch
, preheader
,
1078 single_succ_edge (swtch
)->flags
& EDGE_IRREDUCIBLE_LOOP
);
1082 /* Recount dominators for outer blocks. */
1083 iterate_fix_dominators (CDI_DOMINATORS
, dom_bbs
, n_dom_bbs
);
1085 /* And unroll loop. */
1087 sbitmap_ones (wont_exit
);
1088 RESET_BIT (wont_exit
, may_exit_copy
);
1089 opt_info_start_duplication (opt_info
);
1091 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1093 wont_exit
, desc
->out_edge
,
1094 remove_edges
, &n_remove_edges
,
1095 DLTHE_FLAG_UPDATE_FREQ
);
1100 apply_opt_in_copies (opt_info
, max_unroll
, true, true);
1101 free_opt_info (opt_info
);
1108 basic_block exit_block
= desc
->in_edge
->src
->rbi
->copy
;
1109 /* Find a new in and out edge; they are in the last copy we have
1112 if (EDGE_SUCC (exit_block
, 0)->dest
== desc
->out_edge
->dest
)
1114 desc
->out_edge
= EDGE_SUCC (exit_block
, 0);
1115 desc
->in_edge
= EDGE_SUCC (exit_block
, 1);
1119 desc
->out_edge
= EDGE_SUCC (exit_block
, 1);
1120 desc
->in_edge
= EDGE_SUCC (exit_block
, 0);
1124 /* Remove the edges. */
1125 for (i
= 0; i
< n_remove_edges
; i
++)
1126 remove_path (loops
, remove_edges
[i
]);
1127 free (remove_edges
);
1129 /* We must be careful when updating the number of iterations due to
1130 preconditioning and the fact that the value must be valid at entry
1131 of the loop. After passing through the above code, we see that
1132 the correct new number of iterations is this: */
1133 gcc_assert (!desc
->const_iter
);
1135 simplify_gen_binary (UDIV
, desc
->mode
, old_niter
,
1136 GEN_INT (max_unroll
+ 1));
1137 desc
->niter_max
/= max_unroll
+ 1;
1141 simplify_gen_binary (MINUS
, desc
->mode
, desc
->niter_expr
, const1_rtx
);
1142 desc
->noloop_assumptions
= NULL_RTX
;
1148 ";; Unrolled loop %d times, counting # of iterations "
1149 "in runtime, %i insns\n",
1150 max_unroll
, num_loop_insns (loop
));
1153 /* Decide whether to simply peel LOOP and how much. */
1155 decide_peel_simple (struct loop
*loop
, int flags
)
1158 struct niter_desc
*desc
;
1160 if (!(flags
& UAP_PEEL
))
1162 /* We were not asked to, just return back silently. */
1167 fprintf (dump_file
, "\n;; Considering simply peeling loop\n");
1169 /* npeel = number of iterations to peel. */
1170 npeel
= PARAM_VALUE (PARAM_MAX_PEELED_INSNS
) / loop
->ninsns
;
1171 if (npeel
> (unsigned) PARAM_VALUE (PARAM_MAX_PEEL_TIMES
))
1172 npeel
= PARAM_VALUE (PARAM_MAX_PEEL_TIMES
);
1174 /* Skip big loops. */
1178 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1182 /* Check for simple loops. */
1183 desc
= get_simple_loop_desc (loop
);
1185 /* Check number of iterations. */
1186 if (desc
->simple_p
&& !desc
->assumptions
&& desc
->const_iter
)
1189 fprintf (dump_file
, ";; Loop iterates constant times\n");
1193 /* Do not simply peel loops with branches inside -- it increases number
1195 if (num_loop_branches (loop
) > 1)
1198 fprintf (dump_file
, ";; Not peeling, contains branches\n");
1202 if (loop
->header
->count
)
1204 unsigned niter
= expected_loop_iterations (loop
);
1205 if (niter
+ 1 > npeel
)
1209 fprintf (dump_file
, ";; Not peeling loop, rolls too much (");
1210 fprintf (dump_file
, HOST_WIDEST_INT_PRINT_DEC
,
1211 (HOST_WIDEST_INT
) (niter
+ 1));
1212 fprintf (dump_file
, " iterations > %d [maximum peelings])\n",
1221 /* For now we have no good heuristics to decide whether loop peeling
1222 will be effective, so disable it. */
1225 ";; Not peeling loop, no evidence it will be profitable\n");
1230 loop
->lpt_decision
.decision
= LPT_PEEL_SIMPLE
;
1231 loop
->lpt_decision
.times
= npeel
;
1234 fprintf (dump_file
, ";; Decided to simply peel the loop, %d times.\n",
1235 loop
->lpt_decision
.times
);
1238 /* Peel a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1244 if (!cond) goto end;
1246 if (!cond) goto end;
1253 peel_loop_simple (struct loops
*loops
, struct loop
*loop
)
1256 unsigned npeel
= loop
->lpt_decision
.times
;
1257 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1258 struct opt_info
*opt_info
= NULL
;
1261 if (flag_split_ivs_in_unroller
&& npeel
> 1)
1262 opt_info
= analyze_insns_in_loop (loop
);
1264 wont_exit
= sbitmap_alloc (npeel
+ 1);
1265 sbitmap_zero (wont_exit
);
1267 opt_info_start_duplication (opt_info
);
1269 ok
= duplicate_loop_to_header_edge (loop
, loop_preheader_edge (loop
),
1270 loops
, npeel
, wont_exit
,
1272 NULL
, DLTHE_FLAG_UPDATE_FREQ
);
1279 apply_opt_in_copies (opt_info
, npeel
, false, false);
1280 free_opt_info (opt_info
);
1285 if (desc
->const_iter
)
1287 desc
->niter
-= npeel
;
1288 desc
->niter_expr
= GEN_INT (desc
->niter
);
1289 desc
->noloop_assumptions
= NULL_RTX
;
1293 /* We cannot just update niter_expr, as its value might be clobbered
1294 inside loop. We could handle this by counting the number into
1295 temporary just like we do in runtime unrolling, but it does not
1297 free_simple_loop_desc (loop
);
1301 fprintf (dump_file
, ";; Peeling loop %d times\n", npeel
);
1304 /* Decide whether to unroll LOOP stupidly and how much. */
1306 decide_unroll_stupid (struct loop
*loop
, int flags
)
1308 unsigned nunroll
, nunroll_by_av
, i
;
1309 struct niter_desc
*desc
;
1311 if (!(flags
& UAP_UNROLL_ALL
))
1313 /* We were not asked to, just return back silently. */
1318 fprintf (dump_file
, "\n;; Considering unrolling loop stupidly\n");
1320 /* nunroll = total number of copies of the original loop body in
1321 unrolled loop (i.e. if it is 2, we have to duplicate loop body once. */
1322 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLLED_INSNS
) / loop
->ninsns
;
1324 = PARAM_VALUE (PARAM_MAX_AVERAGE_UNROLLED_INSNS
) / loop
->av_ninsns
;
1325 if (nunroll
> nunroll_by_av
)
1326 nunroll
= nunroll_by_av
;
1327 if (nunroll
> (unsigned) PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
))
1328 nunroll
= PARAM_VALUE (PARAM_MAX_UNROLL_TIMES
);
1330 /* Skip big loops. */
1334 fprintf (dump_file
, ";; Not considering loop, is too big\n");
1338 /* Check for simple loops. */
1339 desc
= get_simple_loop_desc (loop
);
1341 /* Check simpleness. */
1342 if (desc
->simple_p
&& !desc
->assumptions
)
1345 fprintf (dump_file
, ";; The loop is simple\n");
1349 /* Do not unroll loops with branches inside -- it increases number
1351 if (num_loop_branches (loop
) > 1)
1354 fprintf (dump_file
, ";; Not unrolling, contains branches\n");
1358 /* If we have profile feedback, check whether the loop rolls. */
1359 if (loop
->header
->count
1360 && expected_loop_iterations (loop
) < 2 * nunroll
)
1363 fprintf (dump_file
, ";; Not unrolling loop, doesn't roll\n");
1367 /* Success. Now force nunroll to be power of 2, as it seems that this
1368 improves results (partially because of better alignments, partially
1369 because of some dark magic). */
1370 for (i
= 1; 2 * i
<= nunroll
; i
*= 2)
1373 loop
->lpt_decision
.decision
= LPT_UNROLL_STUPID
;
1374 loop
->lpt_decision
.times
= i
- 1;
1378 ";; Decided to unroll the loop stupidly, %d times.\n",
1379 loop
->lpt_decision
.times
);
1382 /* Unroll a LOOP LOOP->LPT_DECISION.TIMES times. The transformation:
1400 unroll_loop_stupid (struct loops
*loops
, struct loop
*loop
)
1403 unsigned nunroll
= loop
->lpt_decision
.times
;
1404 struct niter_desc
*desc
= get_simple_loop_desc (loop
);
1405 struct opt_info
*opt_info
= NULL
;
1408 if (flag_split_ivs_in_unroller
1409 || flag_variable_expansion_in_unroller
)
1410 opt_info
= analyze_insns_in_loop (loop
);
1413 wont_exit
= sbitmap_alloc (nunroll
+ 1);
1414 sbitmap_zero (wont_exit
);
1415 opt_info_start_duplication (opt_info
);
1417 ok
= duplicate_loop_to_header_edge (loop
, loop_latch_edge (loop
),
1418 loops
, nunroll
, wont_exit
,
1420 DLTHE_FLAG_UPDATE_FREQ
);
1425 apply_opt_in_copies (opt_info
, nunroll
, true, true);
1426 free_opt_info (opt_info
);
1433 /* We indeed may get here provided that there are nontrivial assumptions
1434 for a loop to be really simple. We could update the counts, but the
1435 problem is that we are unable to decide which exit will be taken
1436 (not really true in case the number of iterations is constant,
1437 but noone will do anything with this information, so we do not
1439 desc
->simple_p
= false;
1443 fprintf (dump_file
, ";; Unrolled loop %d times, %i insns\n",
1444 nunroll
, num_loop_insns (loop
));
1447 /* A hash function for information about insns to split. */
1450 si_info_hash (const void *ivts
)
1452 return htab_hash_pointer (((struct iv_to_split
*) ivts
)->insn
);
1455 /* An equality functions for information about insns to split. */
1458 si_info_eq (const void *ivts1
, const void *ivts2
)
1460 const struct iv_to_split
*i1
= ivts1
;
1461 const struct iv_to_split
*i2
= ivts2
;
1463 return i1
->insn
== i2
->insn
;
1466 /* Return a hash for VES, which is really a "var_to_expand *". */
1469 ve_info_hash (const void *ves
)
1471 return htab_hash_pointer (((struct var_to_expand
*) ves
)->insn
);
1474 /* Return true if IVTS1 and IVTS2 (which are really both of type
1475 "var_to_expand *") refer to the same instruction. */
1478 ve_info_eq (const void *ivts1
, const void *ivts2
)
1480 const struct var_to_expand
*i1
= ivts1
;
1481 const struct var_to_expand
*i2
= ivts2
;
1483 return i1
->insn
== i2
->insn
;
1486 /* Returns true if REG is referenced in one insn in LOOP. */
1489 referenced_in_one_insn_in_loop_p (struct loop
*loop
, rtx reg
)
1491 basic_block
*body
, bb
;
1496 body
= get_loop_body (loop
);
1497 for (i
= 0; i
< loop
->num_nodes
; i
++)
1501 FOR_BB_INSNS (bb
, insn
)
1503 if (rtx_referenced_p (reg
, insn
))
1507 return (count_ref
== 1);
1510 /* Determine whether INSN contains an accumulator
1511 which can be expanded into separate copies,
1512 one for each copy of the LOOP body.
1514 for (i = 0 ; i < n; i++)
1528 Return NULL if INSN contains no opportunity for expansion of accumulator.
1529 Otherwise, allocate a VAR_TO_EXPAND structure, fill it with the relevant
1530 information and return a pointer to it.
1533 static struct var_to_expand
*
1534 analyze_insn_to_expand_var (struct loop
*loop
, rtx insn
)
1536 rtx set
, dest
, src
, op1
;
1537 struct var_to_expand
*ves
;
1538 enum machine_mode mode1
, mode2
;
1540 set
= single_set (insn
);
1544 dest
= SET_DEST (set
);
1545 src
= SET_SRC (set
);
1547 if (GET_CODE (src
) != PLUS
1548 && GET_CODE (src
) != MINUS
1549 && GET_CODE (src
) != MULT
)
1555 op1
= XEXP (src
, 0);
1558 && !(GET_CODE (dest
) == SUBREG
1559 && REG_P (SUBREG_REG (dest
))))
1562 if (!rtx_equal_p (dest
, op1
))
1565 if (!referenced_in_one_insn_in_loop_p (loop
, dest
))
1568 if (rtx_referenced_p (dest
, XEXP (src
, 1)))
1571 mode1
= GET_MODE (dest
);
1572 mode2
= GET_MODE (XEXP (src
, 1));
1573 if ((FLOAT_MODE_P (mode1
)
1574 || FLOAT_MODE_P (mode2
))
1575 && !flag_unsafe_math_optimizations
)
1578 /* Record the accumulator to expand. */
1579 ves
= xmalloc (sizeof (struct var_to_expand
));
1581 VARRAY_RTX_INIT (ves
->var_expansions
, 1, "var_expansions");
1582 ves
->reg
= copy_rtx (dest
);
1583 ves
->op
= GET_CODE (src
);
1584 ves
->expansion_count
= 0;
1585 ves
->reuse_expansion
= 0;
1589 /* Determine whether there is an induction variable in INSN that
1590 we would like to split during unrolling.
1610 Return NULL if INSN contains no interesting IVs. Otherwise, allocate
1611 an IV_TO_SPLIT structure, fill it with the relevant information and return a
1614 static struct iv_to_split
*
1615 analyze_iv_to_split_insn (rtx insn
)
1619 struct iv_to_split
*ivts
;
1622 /* For now we just split the basic induction variables. Later this may be
1623 extended for example by selecting also addresses of memory references. */
1624 set
= single_set (insn
);
1628 dest
= SET_DEST (set
);
1632 if (!biv_p (insn
, dest
))
1635 ok
= iv_analyze (insn
, dest
, &iv
);
1638 if (iv
.step
== const0_rtx
1639 || iv
.mode
!= iv
.extend_mode
)
1642 /* Record the insn to split. */
1643 ivts
= xmalloc (sizeof (struct iv_to_split
));
1645 ivts
->base_var
= NULL_RTX
;
1646 ivts
->step
= iv
.step
;
1653 /* Determines which of insns in LOOP can be optimized.
1654 Return a OPT_INFO struct with the relevant hash tables filled
1655 with all insns to be optimized. The FIRST_NEW_BLOCK field
1656 is undefined for the return value. */
1658 static struct opt_info
*
1659 analyze_insns_in_loop (struct loop
*loop
)
1661 basic_block
*body
, bb
;
1662 unsigned i
, num_edges
= 0;
1663 struct opt_info
*opt_info
= xcalloc (1, sizeof (struct opt_info
));
1665 struct iv_to_split
*ivts
= NULL
;
1666 struct var_to_expand
*ves
= NULL
;
1669 edge
*edges
= get_loop_exit_edges (loop
, &num_edges
);
1670 bool can_apply
= false;
1672 iv_analysis_loop_init (loop
);
1674 body
= get_loop_body (loop
);
1676 if (flag_split_ivs_in_unroller
)
1677 opt_info
->insns_to_split
= htab_create (5 * loop
->num_nodes
,
1678 si_info_hash
, si_info_eq
, free
);
1680 /* Record the loop exit bb and loop preheader before the unrolling. */
1681 if (!loop_preheader_edge (loop
)->src
)
1683 loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1684 opt_info
->loop_preheader
= loop_split_edge_with (loop_preheader_edge (loop
), NULL_RTX
);
1687 opt_info
->loop_preheader
= loop_preheader_edge (loop
)->src
;
1690 && !(edges
[0]->flags
& EDGE_COMPLEX
))
1692 opt_info
->loop_exit
= loop_split_edge_with (edges
[0], NULL_RTX
);
1696 if (flag_variable_expansion_in_unroller
1698 opt_info
->insns_with_var_to_expand
= htab_create (5 * loop
->num_nodes
,
1699 ve_info_hash
, ve_info_eq
, free
);
1701 for (i
= 0; i
< loop
->num_nodes
; i
++)
1704 if (!dominated_by_p (CDI_DOMINATORS
, loop
->latch
, bb
))
1707 FOR_BB_INSNS (bb
, insn
)
1712 if (opt_info
->insns_to_split
)
1713 ivts
= analyze_iv_to_split_insn (insn
);
1717 slot1
= htab_find_slot (opt_info
->insns_to_split
, ivts
, INSERT
);
1722 if (opt_info
->insns_with_var_to_expand
)
1723 ves
= analyze_insn_to_expand_var (loop
, insn
);
1727 slot2
= htab_find_slot (opt_info
->insns_with_var_to_expand
, ves
, INSERT
);
1738 /* Called just before loop duplication. Records start of duplicated area
1742 opt_info_start_duplication (struct opt_info
*opt_info
)
1745 opt_info
->first_new_block
= last_basic_block
;
1748 /* Determine the number of iterations between initialization of the base
1749 variable and the current copy (N_COPY). N_COPIES is the total number
1750 of newly created copies. UNROLLING is true if we are unrolling
1751 (not peeling) the loop. */
1754 determine_split_iv_delta (unsigned n_copy
, unsigned n_copies
, bool unrolling
)
1758 /* If we are unrolling, initialization is done in the original loop
1764 /* If we are peeling, the copy in that the initialization occurs has
1765 number 1. The original loop (number 0) is the last. */
1773 /* Locate in EXPR the expression corresponding to the location recorded
1774 in IVTS, and return a pointer to the RTX for this location. */
1777 get_ivts_expr (rtx expr
, struct iv_to_split
*ivts
)
1782 for (i
= 0; i
< ivts
->n_loc
; i
++)
1783 ret
= &XEXP (*ret
, ivts
->loc
[i
]);
1788 /* Allocate basic variable for the induction variable chain. Callback for
1792 allocate_basic_variable (void **slot
, void *data ATTRIBUTE_UNUSED
)
1794 struct iv_to_split
*ivts
= *slot
;
1795 rtx expr
= *get_ivts_expr (single_set (ivts
->insn
), ivts
);
1797 ivts
->base_var
= gen_reg_rtx (GET_MODE (expr
));
1802 /* Insert initialization of basic variable of IVTS before INSN, taking
1803 the initial value from INSN. */
1806 insert_base_initialization (struct iv_to_split
*ivts
, rtx insn
)
1808 rtx expr
= copy_rtx (*get_ivts_expr (single_set (insn
), ivts
));
1812 expr
= force_operand (expr
, ivts
->base_var
);
1813 if (expr
!= ivts
->base_var
)
1814 emit_move_insn (ivts
->base_var
, expr
);
1818 emit_insn_before (seq
, insn
);
1821 /* Replace the use of induction variable described in IVTS in INSN
1822 by base variable + DELTA * step. */
1825 split_iv (struct iv_to_split
*ivts
, rtx insn
, unsigned delta
)
1827 rtx expr
, *loc
, seq
, incr
, var
;
1828 enum machine_mode mode
= GET_MODE (ivts
->base_var
);
1831 /* Construct base + DELTA * step. */
1833 expr
= ivts
->base_var
;
1836 incr
= simplify_gen_binary (MULT
, mode
,
1837 ivts
->step
, gen_int_mode (delta
, mode
));
1838 expr
= simplify_gen_binary (PLUS
, GET_MODE (ivts
->base_var
),
1839 ivts
->base_var
, incr
);
1842 /* Figure out where to do the replacement. */
1843 loc
= get_ivts_expr (single_set (insn
), ivts
);
1845 /* If we can make the replacement right away, we're done. */
1846 if (validate_change (insn
, loc
, expr
, 0))
1849 /* Otherwise, force EXPR into a register and try again. */
1851 var
= gen_reg_rtx (mode
);
1852 expr
= force_operand (expr
, var
);
1854 emit_move_insn (var
, expr
);
1857 emit_insn_before (seq
, insn
);
1859 if (validate_change (insn
, loc
, var
, 0))
1862 /* The last chance. Try recreating the assignment in insn
1863 completely from scratch. */
1864 set
= single_set (insn
);
1869 src
= copy_rtx (SET_SRC (set
));
1870 dest
= copy_rtx (SET_DEST (set
));
1871 src
= force_operand (src
, dest
);
1873 emit_move_insn (dest
, src
);
1877 emit_insn_before (seq
, insn
);
1882 /* Return one expansion of the accumulator recorded in struct VE. */
1885 get_expansion (struct var_to_expand
*ve
)
1889 if (ve
->reuse_expansion
== 0)
1892 reg
= VARRAY_RTX (ve
->var_expansions
, ve
->reuse_expansion
- 1);
1894 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == (unsigned) ve
->reuse_expansion
)
1895 ve
->reuse_expansion
= 0;
1897 ve
->reuse_expansion
++;
1903 /* Given INSN replace the uses of the accumulator recorded in VE
1904 with a new register. */
1907 expand_var_during_unrolling (struct var_to_expand
*ve
, rtx insn
)
1910 bool really_new_expansion
= false;
1912 set
= single_set (insn
);
1915 /* Generate a new register only if the expansion limit has not been
1916 reached. Else reuse an already existing expansion. */
1917 if (PARAM_VALUE (PARAM_MAX_VARIABLE_EXPANSIONS
) > ve
->expansion_count
)
1919 really_new_expansion
= true;
1920 new_reg
= gen_reg_rtx (GET_MODE (ve
->reg
));
1923 new_reg
= get_expansion (ve
);
1925 validate_change (insn
, &SET_DEST (set
), new_reg
, 1);
1926 validate_change (insn
, &XEXP (SET_SRC (set
), 0), new_reg
, 1);
1928 if (apply_change_group ())
1929 if (really_new_expansion
)
1931 VARRAY_PUSH_RTX (ve
->var_expansions
, new_reg
);
1932 ve
->expansion_count
++;
1936 /* Initialize the variable expansions in loop preheader.
1937 Callbacks for htab_traverse. PLACE_P is the loop-preheader
1938 basic block where the initialization of the expansions
1939 should take place. */
1942 insert_var_expansion_initialization (void **slot
, void *place_p
)
1944 struct var_to_expand
*ve
= *slot
;
1945 basic_block place
= (basic_block
)place_p
;
1946 rtx seq
, var
, zero_init
, insn
;
1949 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == 0)
1953 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1954 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1956 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1957 zero_init
= CONST0_RTX (GET_MODE (var
));
1958 emit_move_insn (var
, zero_init
);
1960 else if (ve
->op
== MULT
)
1961 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
1963 var
= VARRAY_RTX (ve
->var_expansions
, i
);
1964 zero_init
= CONST1_RTX (GET_MODE (var
));
1965 emit_move_insn (var
, zero_init
);
1971 insn
= BB_HEAD (place
);
1972 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
1973 insn
= NEXT_INSN (insn
);
1975 emit_insn_after (seq
, insn
);
1976 /* Continue traversing the hash table. */
1980 /* Combine the variable expansions at the loop exit.
1981 Callbacks for htab_traverse. PLACE_P is the loop exit
1982 basic block where the summation of the expansions should
1986 combine_var_copies_in_loop_exit (void **slot
, void *place_p
)
1988 struct var_to_expand
*ve
= *slot
;
1989 basic_block place
= (basic_block
)place_p
;
1991 rtx expr
, seq
, var
, insn
;
1994 if (VARRAY_ACTIVE_SIZE (ve
->var_expansions
) == 0)
1998 if (ve
->op
== PLUS
|| ve
->op
== MINUS
)
1999 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
2001 var
= VARRAY_RTX (ve
->var_expansions
, i
);
2002 sum
= simplify_gen_binary (PLUS
, GET_MODE (ve
->reg
),
2005 else if (ve
->op
== MULT
)
2006 for (i
= 0; i
< VARRAY_ACTIVE_SIZE (ve
->var_expansions
); i
++)
2008 var
= VARRAY_RTX (ve
->var_expansions
, i
);
2009 sum
= simplify_gen_binary (MULT
, GET_MODE (ve
->reg
),
2013 expr
= force_operand (sum
, ve
->reg
);
2014 if (expr
!= ve
->reg
)
2015 emit_move_insn (ve
->reg
, expr
);
2019 insn
= BB_HEAD (place
);
2020 while (!NOTE_INSN_BASIC_BLOCK_P (insn
))
2021 insn
= NEXT_INSN (insn
);
2023 emit_insn_after (seq
, insn
);
2025 /* Continue traversing the hash table. */
2029 /* Apply loop optimizations in loop copies using the
2030 data which gathered during the unrolling. Structure
2031 OPT_INFO record that data.
2033 UNROLLING is true if we unrolled (not peeled) the loop.
2034 REWRITE_ORIGINAL_BODY is true if we should also rewrite the original body of
2035 the loop (as it should happen in complete unrolling, but not in ordinary
2036 peeling of the loop). */
2039 apply_opt_in_copies (struct opt_info
*opt_info
,
2040 unsigned n_copies
, bool unrolling
,
2041 bool rewrite_original_loop
)
2044 basic_block bb
, orig_bb
;
2045 rtx insn
, orig_insn
, next
;
2046 struct iv_to_split ivts_templ
, *ivts
;
2047 struct var_to_expand ve_templ
, *ves
;
2049 /* Sanity check -- we need to put initialization in the original loop
2051 gcc_assert (!unrolling
|| rewrite_original_loop
);
2053 /* Allocate the basic variables (i0). */
2054 if (opt_info
->insns_to_split
)
2055 htab_traverse (opt_info
->insns_to_split
, allocate_basic_variable
, NULL
);
2057 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2059 bb
= BASIC_BLOCK (i
);
2060 orig_bb
= bb
->rbi
->original
;
2062 delta
= determine_split_iv_delta (bb
->rbi
->copy_number
, n_copies
,
2064 orig_insn
= BB_HEAD (orig_bb
);
2065 for (insn
= BB_HEAD (bb
); insn
!= NEXT_INSN (BB_END (bb
)); insn
= next
)
2067 next
= NEXT_INSN (insn
);
2071 while (!INSN_P (orig_insn
))
2072 orig_insn
= NEXT_INSN (orig_insn
);
2074 ivts_templ
.insn
= orig_insn
;
2075 ve_templ
.insn
= orig_insn
;
2077 /* Apply splitting iv optimization. */
2078 if (opt_info
->insns_to_split
)
2080 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2084 #ifdef ENABLE_CHECKING
2085 gcc_assert (rtx_equal_p (PATTERN (insn
), PATTERN (orig_insn
)));
2089 insert_base_initialization (ivts
, insn
);
2090 split_iv (ivts
, insn
, delta
);
2093 /* Apply variable expansion optimization. */
2094 if (unrolling
&& opt_info
->insns_with_var_to_expand
)
2096 ves
= htab_find (opt_info
->insns_with_var_to_expand
, &ve_templ
);
2099 #ifdef ENABLE_CHECKING
2100 gcc_assert (rtx_equal_p (PATTERN (insn
), PATTERN (orig_insn
)));
2102 expand_var_during_unrolling (ves
, insn
);
2105 orig_insn
= NEXT_INSN (orig_insn
);
2109 if (!rewrite_original_loop
)
2112 /* Initialize the variable expansions in the loop preheader
2113 and take care of combining them at the loop exit. */
2114 if (opt_info
->insns_with_var_to_expand
)
2116 htab_traverse (opt_info
->insns_with_var_to_expand
,
2117 insert_var_expansion_initialization
,
2118 opt_info
->loop_preheader
);
2119 htab_traverse (opt_info
->insns_with_var_to_expand
,
2120 combine_var_copies_in_loop_exit
,
2121 opt_info
->loop_exit
);
2124 /* Rewrite also the original loop body. Find them as originals of the blocks
2125 in the last copied iteration, i.e. those that have
2126 bb->rbi->original->copy == bb. */
2127 for (i
= opt_info
->first_new_block
; i
< (unsigned) last_basic_block
; i
++)
2129 bb
= BASIC_BLOCK (i
);
2130 orig_bb
= bb
->rbi
->original
;
2131 if (orig_bb
->rbi
->copy
!= bb
)
2134 delta
= determine_split_iv_delta (0, n_copies
, unrolling
);
2135 for (orig_insn
= BB_HEAD (orig_bb
);
2136 orig_insn
!= NEXT_INSN (BB_END (bb
));
2139 next
= NEXT_INSN (orig_insn
);
2141 if (!INSN_P (orig_insn
))
2144 ivts_templ
.insn
= orig_insn
;
2145 if (opt_info
->insns_to_split
)
2147 ivts
= htab_find (opt_info
->insns_to_split
, &ivts_templ
);
2151 insert_base_initialization (ivts
, orig_insn
);
2152 split_iv (ivts
, orig_insn
, delta
);
2161 /* Release the data structures used for the variable expansion
2162 optimization. Callbacks for htab_traverse. */
2165 release_var_copies (void **slot
, void *data ATTRIBUTE_UNUSED
)
2167 struct var_to_expand
*ve
= *slot
;
2169 VARRAY_CLEAR (ve
->var_expansions
);
2171 /* Continue traversing the hash table. */
2175 /* Release OPT_INFO. */
2178 free_opt_info (struct opt_info
*opt_info
)
2180 if (opt_info
->insns_to_split
)
2181 htab_delete (opt_info
->insns_to_split
);
2182 if (opt_info
->insns_with_var_to_expand
)
2184 htab_traverse (opt_info
->insns_with_var_to_expand
,
2185 release_var_copies
, NULL
);
2186 htab_delete (opt_info
->insns_with_var_to_expand
);