]>
Commit | Line | Data |
---|---|---|
23b2ce53 | 1 | /* Loop optimization definitions for GNU C-Compiler |
5e5c9768 | 2 | Copyright (C) 1991, 1995, 1998, 1999 Free Software Foundation, Inc. |
23b2ce53 RS |
3 | |
4 | This file is part of GNU CC. | |
5 | ||
6 | GNU CC is free software; you can redistribute it and/or modify | |
7 | it under the terms of the GNU General Public License as published by | |
8 | the Free Software Foundation; either version 2, or (at your option) | |
9 | any later version. | |
10 | ||
11 | GNU CC is distributed in the hope that it will be useful, | |
12 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
13 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the | |
14 | GNU General Public License for more details. | |
15 | ||
16 | You should have received a copy of the GNU General Public License | |
17 | along with GNU CC; see the file COPYING. If not, write to | |
a35311b0 RK |
18 | the Free Software Foundation, 59 Temple Place - Suite 330, |
19 | Boston, MA 02111-1307, USA. */ | |
23b2ce53 | 20 | |
3ec2b590 | 21 | #include "varray.h" |
a2be868f | 22 | #include "basic-block.h" |
3ec2b590 | 23 | |
23b2ce53 RS |
24 | /* Get the luid of an insn. Catch the error of trying to reference the LUID |
25 | of an insn added during loop, since these don't have LUIDs. */ | |
26 | ||
27 | #define INSN_LUID(INSN) \ | |
28 | (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \ | |
29 | : (abort (), -1)) | |
30 | ||
31 | /* A "basic induction variable" or biv is a pseudo reg that is set | |
32 | (within this loop) only by incrementing or decrementing it. */ | |
33 | /* A "general induction variable" or giv is a pseudo reg whose | |
34 | value is a linear function of a biv. */ | |
35 | ||
36 | /* Bivs are recognized by `basic_induction_var'; | |
37 | Givs by `general_induct_var'. */ | |
38 | ||
39 | /* An enum for the two different types of givs, those that are used | |
40 | as memory addresses and those that are calculated into registers. */ | |
41 | enum g_types { DEST_ADDR, DEST_REG }; | |
42 | ||
43 | /* A `struct induction' is created for every instruction that sets | |
44 | an induction variable (either a biv or a giv). */ | |
45 | ||
46 | struct induction | |
47 | { | |
48 | rtx insn; /* The insn that sets a biv or giv */ | |
49 | rtx new_reg; /* New register, containing strength reduced | |
50 | version of this giv. */ | |
51 | rtx src_reg; /* Biv from which this giv is computed. | |
52 | (If this is a biv, then this is the biv.) */ | |
53 | enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG */ | |
54 | rtx dest_reg; /* Destination register for insn: this is the | |
55 | register which was the biv or giv. | |
56 | For a biv, this equals src_reg. | |
57 | For a DEST_ADDR type giv, this is 0. */ | |
58 | rtx *location; /* Place in the insn where this giv occurs. | |
59 | If GIV_TYPE is DEST_REG, this is 0. */ | |
3ec2b590 R |
60 | /* For a biv, this is the place where add_val |
61 | was found. */ | |
23b2ce53 RS |
62 | enum machine_mode mode; /* The mode of this biv or giv */ |
63 | enum machine_mode mem_mode; /* For DEST_ADDR, mode of the memory object. */ | |
64 | rtx mult_val; /* Multiplicative factor for src_reg. */ | |
65 | rtx add_val; /* Additive constant for that product. */ | |
66 | int benefit; /* Gain from eliminating this insn. */ | |
67 | rtx final_value; /* If the giv is used outside the loop, and its | |
68 | final value could be calculated, it is put | |
69 | here, and the giv is made replaceable. Set | |
70 | the giv to this value before the loop. */ | |
3ec2b590 R |
71 | unsigned combined_with; /* The number of givs this giv has been |
72 | combined with. If nonzero, this giv | |
73 | cannot combine with any other giv. */ | |
23b2ce53 RS |
74 | unsigned replaceable : 1; /* 1 if we can substitute the strength-reduced |
75 | variable for the original variable. | |
76 | 0 means they must be kept separate and the | |
77 | new one must be copied into the old pseudo | |
78 | reg each time the old one is set. */ | |
79 | unsigned not_replaceable : 1; /* Used to prevent duplicating work. This is | |
80 | 1 if we know that the giv definitely can | |
81 | not be made replaceable, in which case we | |
82 | don't bother checking the variable again | |
83 | even if further info is available. | |
84 | Both this and the above can be zero. */ | |
85 | unsigned ignore : 1; /* 1 prohibits further processing of giv */ | |
125e4dcf JW |
86 | unsigned always_computable : 1;/* 1 if this value is computable every |
87 | iteration. */ | |
88 | unsigned always_executed : 1; /* 1 if this set occurs each iteration. */ | |
8fd297fb RK |
89 | unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv |
90 | update may be done multiple times per | |
91 | iteration. */ | |
23b2ce53 RS |
92 | unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive |
93 | another giv. This occurs in many cases | |
94 | where a giv's lifetime spans an update to | |
95 | a biv. */ | |
23b2ce53 RS |
96 | unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, |
97 | we won't use it to eliminate a biv, it | |
98 | would probably lose. */ | |
125e4dcf JW |
99 | unsigned auto_inc_opt : 1; /* 1 if this giv had its increment output next |
100 | to it to try to form an auto-inc address. */ | |
7e7ca3a1 JW |
101 | unsigned unrolled : 1; /* 1 if new register has been allocated and |
102 | initialized in unrolled loop. */ | |
9ae8ffe7 | 103 | unsigned shared : 1; |
45f97e2e | 104 | unsigned no_const_addval : 1; /* 1 if add_val does not contain a const. */ |
60fb6df9 | 105 | unsigned multi_insn_incr : 1; /* 1 if multiple insns updated the biv. */ |
23b2ce53 | 106 | int lifetime; /* Length of life of this giv */ |
23b2ce53 RS |
107 | rtx derive_adjustment; /* If nonzero, is an adjustment to be |
108 | subtracted from add_val when this giv | |
109 | derives another. This occurs when the | |
110 | giv spans a biv update by incrementation. */ | |
111 | struct induction *next_iv; /* For givs, links together all givs that are | |
112 | based on the same biv. For bivs, links | |
113 | together all biv entries that refer to the | |
114 | same biv register. */ | |
115 | struct induction *same; /* If this giv has been combined with another | |
116 | giv, this points to the base giv. The base | |
117 | giv will have COMBINED_WITH non-zero. */ | |
4d87f7a7 R |
118 | struct induction *derived_from;/* For a giv, if we decided to derive this |
119 | giv from another one. */ | |
3245eea0 | 120 | HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv |
23b2ce53 RS |
121 | is split, and a constant is eliminated from |
122 | the address, the -constant is stored here | |
123 | for later use. */ | |
3ec2b590 R |
124 | int ix; /* Used by recombine_givs, as n index into |
125 | the stats array. */ | |
2a2af110 JW |
126 | struct induction *same_insn; /* If there are multiple identical givs in |
127 | the same insn, then all but one have this | |
128 | field set, and they all point to the giv | |
129 | that doesn't have this field set. */ | |
3ec2b590 R |
130 | rtx last_use; /* For a giv made from a biv increment, this is |
131 | a substitute for the lifetime information. */ | |
23b2ce53 RS |
132 | }; |
133 | ||
134 | /* A `struct iv_class' is created for each biv. */ | |
135 | ||
136 | struct iv_class { | |
137 | int regno; /* Pseudo reg which is the biv. */ | |
138 | int biv_count; /* Number of insns setting this reg. */ | |
139 | struct induction *biv; /* List of all insns that set this reg. */ | |
140 | int giv_count; /* Number of DEST_REG givs computed from this | |
141 | biv. The resulting count is only used in | |
142 | check_dbra_loop. */ | |
143 | struct induction *giv; /* List of all insns that compute a giv | |
144 | from this reg. */ | |
145 | int total_benefit; /* Sum of BENEFITs of all those givs */ | |
146 | rtx initial_value; /* Value of reg at loop start */ | |
147 | rtx initial_test; /* Test performed on BIV before loop */ | |
148 | struct iv_class *next; /* Links all class structures together */ | |
6dc42e49 | 149 | rtx init_insn; /* insn which initializes biv, 0 if none. */ |
23b2ce53 RS |
150 | rtx init_set; /* SET of INIT_INSN, if any. */ |
151 | unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ | |
152 | unsigned eliminable : 1; /* 1 if plausible candidate for elimination. */ | |
153 | unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for this. */ | |
154 | unsigned reversed : 1; /* 1 if we reversed the loop that this | |
155 | biv controls. */ | |
156 | }; | |
157 | ||
302670f3 MH |
158 | /* Information required to calculate the number of loop iterations. |
159 | This is set by loop_iterations. */ | |
160 | ||
161 | struct loop_info | |
162 | { | |
3c748bb6 MH |
163 | /* Nonzero if there is a subroutine call in the current loop. */ |
164 | int has_call; | |
165 | /* Nonzero if there is a volatile memory reference in the current | |
166 | loop. */ | |
167 | int has_volatile; | |
168 | /* Nonzero if there is a tablejump in the current loop. */ | |
169 | int has_tablejump; | |
170 | /* Nonzero if there are ways to leave the loop other than falling | |
171 | off the end. */ | |
172 | int has_multiple_exit_targets; | |
173 | /* Nonzero if there is an indirect jump in the current function. */ | |
174 | int has_indirect_jump; | |
302670f3 MH |
175 | /* Register or constant initial loop value. */ |
176 | rtx initial_value; | |
177 | /* Register or constant value used for comparison test. */ | |
178 | rtx comparison_value; | |
179 | /* Register or constant approximate final value. */ | |
180 | rtx final_value; | |
181 | /* Register or constant initial loop value with term common to | |
182 | final_value removed. */ | |
183 | rtx initial_equiv_value; | |
184 | /* Register or constant final loop value with term common to | |
185 | initial_value removed. */ | |
186 | rtx final_equiv_value; | |
187 | /* Register corresponding to iteration variable. */ | |
188 | rtx iteration_var; | |
189 | /* Constant loop increment. */ | |
190 | rtx increment; | |
191 | enum rtx_code comparison_code; | |
192 | /* Holds the number of loop iterations. It is zero if the number | |
193 | could not be calculated. Must be unsigned since the number of | |
194 | iterations can be as high as 2^wordsize - 1. For loops with a | |
195 | wider iterator, this number will be zero if the number of loop | |
196 | iterations is too large for an unsigned integer to hold. */ | |
197 | unsigned HOST_WIDE_INT n_iterations; | |
3c748bb6 | 198 | /* The number of times the loop body was unrolled. */ |
35704c46 | 199 | unsigned int unroll_number; |
a2be868f | 200 | int used_count_register; |
302670f3 MH |
201 | }; |
202 | ||
23b2ce53 RS |
203 | /* Definitions used by the basic induction variable discovery code. */ |
204 | enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, | |
205 | GENERAL_INDUCT }; | |
206 | ||
207 | /* Variables declared in loop.c, but also needed in unroll.c. */ | |
208 | ||
209 | extern int *uid_luid; | |
210 | extern int max_uid_for_loop; | |
23b2ce53 | 211 | extern int max_reg_before_loop; |
a2be868f | 212 | extern struct loop **uid_loop; |
23b2ce53 RS |
213 | extern FILE *loop_dump_stream; |
214 | ||
3ec2b590 R |
215 | extern varray_type reg_iv_type; |
216 | extern varray_type reg_iv_info; | |
217 | ||
218 | #define REG_IV_TYPE(n) \ | |
219 | (*(enum iv_mode *) &VARRAY_INT(reg_iv_type, (n))) | |
220 | #define REG_IV_INFO(n) \ | |
221 | (*(struct induction **) &VARRAY_GENERIC_PTR(reg_iv_info, (n))) | |
222 | ||
23b2ce53 RS |
223 | extern struct iv_class **reg_biv_class; |
224 | extern struct iv_class *loop_iv_list; | |
225 | ||
3ec2b590 R |
226 | extern int first_increment_giv, last_increment_giv; |
227 | ||
23b2ce53 RS |
228 | /* Forward declarations for non-static functions declared in loop.c and |
229 | unroll.c. */ | |
3fe41456 KG |
230 | int invariant_p PARAMS ((rtx)); |
231 | rtx get_condition_for_loop PARAMS ((rtx)); | |
232 | void emit_iv_add_mult PARAMS ((rtx, rtx, rtx, rtx, rtx)); | |
233 | rtx express_from PARAMS ((struct induction *, struct induction *)); | |
234 | ||
235 | void unroll_loop PARAMS ((struct loop *, int, rtx, int)); | |
236 | rtx biv_total_increment PARAMS ((struct iv_class *, rtx, rtx)); | |
237 | unsigned HOST_WIDE_INT loop_iterations PARAMS ((struct loop *)); | |
238 | int precondition_loop_p PARAMS ((rtx, struct loop_info *, | |
e96b4d7a MH |
239 | rtx *, rtx *, rtx *, |
240 | enum machine_mode *mode)); | |
3fe41456 | 241 | rtx final_biv_value PARAMS ((struct iv_class *, rtx, rtx, |
302670f3 | 242 | unsigned HOST_WIDE_INT)); |
3fe41456 | 243 | rtx final_giv_value PARAMS ((struct induction *, rtx, rtx, |
302670f3 | 244 | unsigned HOST_WIDE_INT)); |
3fe41456 KG |
245 | void emit_unrolled_add PARAMS ((rtx, rtx, rtx)); |
246 | int back_branch_in_range_p PARAMS ((rtx, rtx, rtx)); | |
8c660648 | 247 | |
3fe41456 | 248 | int loop_insn_first_p PARAMS ((rtx, rtx)); |
cac8ce95 | 249 | |
c99f8c2a | 250 | /* Forward declarations for non-static functions declared in stmt.c. */ |
3fe41456 KG |
251 | void find_loop_tree_blocks PARAMS ((void)); |
252 | void unroll_block_trees PARAMS ((void)); |