]>
Commit | Line | Data |
---|---|---|
23b2ce53 | 1 | /* Loop optimization definitions for GNU C-Compiler |
97e300e9 | 2 | Copyright (C) 1991, 1995, 1998, 1999, 2000, 2001, 2002 |
d24b8f53 | 3 | Free Software Foundation, Inc. |
23b2ce53 | 4 | |
1322177d | 5 | This file is part of GCC. |
23b2ce53 | 6 | |
1322177d LB |
7 | GCC is free software; you can redistribute it and/or modify it under |
8 | the terms of the GNU General Public License as published by the Free | |
9 | Software Foundation; either version 2, or (at your option) any later | |
10 | version. | |
23b2ce53 | 11 | |
1322177d LB |
12 | GCC is distributed in the hope that it will be useful, but WITHOUT ANY |
13 | WARRANTY; without even the implied warranty of MERCHANTABILITY or | |
14 | FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License | |
15 | for more details. | |
23b2ce53 RS |
16 | |
17 | You should have received a copy of the GNU General Public License | |
1322177d LB |
18 | along with GCC; see the file COPYING. If not, write to the Free |
19 | Software Foundation, 59 Temple Place - Suite 330, Boston, MA | |
20 | 02111-1307, USA. */ | |
23b2ce53 | 21 | |
efc9bd41 | 22 | #include "bitmap.h" |
96a45535 MH |
23 | #include "sbitmap.h" |
24 | #include "hard-reg-set.h" | |
25 | #include "basic-block.h" | |
efc9bd41 | 26 | |
1bf14ad7 JH |
27 | /* Flags passed to loop_optimize. */ |
28 | #define LOOP_UNROLL 1 | |
29 | #define LOOP_BCT 2 | |
0dd0e980 | 30 | #define LOOP_PREFETCH 4 |
5e1afb11 | 31 | #define LOOP_AUTO_UNROLL 8 |
1bf14ad7 | 32 | |
52b38064 | 33 | /* Get the loop info pointer of a loop. */ |
fd5d5b07 | 34 | #define LOOP_INFO(LOOP) ((struct loop_info *) (LOOP)->aux) |
52b38064 | 35 | |
6ec92010 | 36 | /* Get a pointer to the loop movables structure. */ |
97e300e9 | 37 | #define LOOP_MOVABLES(LOOP) (&LOOP_INFO (LOOP)->movables) |
6ec92010 | 38 | |
1ecd860b | 39 | /* Get a pointer to the loop registers structure. */ |
97e300e9 | 40 | #define LOOP_REGS(LOOP) (&LOOP_INFO (LOOP)->regs) |
1ecd860b | 41 | |
ed5bb68d | 42 | /* Get a pointer to the loop induction variables structure. */ |
97e300e9 | 43 | #define LOOP_IVS(LOOP) (&LOOP_INFO (LOOP)->ivs) |
ed5bb68d | 44 | |
23b2ce53 RS |
45 | /* Get the luid of an insn. Catch the error of trying to reference the LUID |
46 | of an insn added during loop, since these don't have LUIDs. */ | |
47 | ||
48 | #define INSN_LUID(INSN) \ | |
49 | (INSN_UID (INSN) < max_uid_for_loop ? uid_luid[INSN_UID (INSN)] \ | |
50 | : (abort (), -1)) | |
51 | ||
8529a489 MH |
52 | #define REGNO_FIRST_LUID(REGNO) uid_luid[REGNO_FIRST_UID (REGNO)] |
53 | #define REGNO_LAST_LUID(REGNO) uid_luid[REGNO_LAST_UID (REGNO)] | |
54 | ||
55 | ||
23b2ce53 RS |
56 | /* A "basic induction variable" or biv is a pseudo reg that is set |
57 | (within this loop) only by incrementing or decrementing it. */ | |
58 | /* A "general induction variable" or giv is a pseudo reg whose | |
59 | value is a linear function of a biv. */ | |
60 | ||
61 | /* Bivs are recognized by `basic_induction_var'; | |
14be28e5 | 62 | Givs by `general_induction_var'. */ |
23b2ce53 RS |
63 | |
64 | /* An enum for the two different types of givs, those that are used | |
65 | as memory addresses and those that are calculated into registers. */ | |
fd5d5b07 KH |
66 | enum g_types |
67 | { | |
68 | DEST_ADDR, | |
69 | DEST_REG | |
70 | }; | |
23b2ce53 | 71 | |
14be28e5 | 72 | |
23b2ce53 RS |
73 | /* A `struct induction' is created for every instruction that sets |
74 | an induction variable (either a biv or a giv). */ | |
75 | ||
76 | struct induction | |
77 | { | |
78 | rtx insn; /* The insn that sets a biv or giv */ | |
79 | rtx new_reg; /* New register, containing strength reduced | |
80 | version of this giv. */ | |
81 | rtx src_reg; /* Biv from which this giv is computed. | |
82 | (If this is a biv, then this is the biv.) */ | |
83 | enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG */ | |
84 | rtx dest_reg; /* Destination register for insn: this is the | |
85 | register which was the biv or giv. | |
86 | For a biv, this equals src_reg. | |
87 | For a DEST_ADDR type giv, this is 0. */ | |
88 | rtx *location; /* Place in the insn where this giv occurs. | |
89 | If GIV_TYPE is DEST_REG, this is 0. */ | |
3ec2b590 R |
90 | /* For a biv, this is the place where add_val |
91 | was found. */ | |
23b2ce53 | 92 | enum machine_mode mode; /* The mode of this biv or giv */ |
099f0f3f | 93 | rtx mem; /* For DEST_ADDR, the memory object. */ |
23b2ce53 RS |
94 | rtx mult_val; /* Multiplicative factor for src_reg. */ |
95 | rtx add_val; /* Additive constant for that product. */ | |
96 | int benefit; /* Gain from eliminating this insn. */ | |
97 | rtx final_value; /* If the giv is used outside the loop, and its | |
98 | final value could be calculated, it is put | |
99 | here, and the giv is made replaceable. Set | |
100 | the giv to this value before the loop. */ | |
3ec2b590 R |
101 | unsigned combined_with; /* The number of givs this giv has been |
102 | combined with. If nonzero, this giv | |
103 | cannot combine with any other giv. */ | |
23b2ce53 RS |
104 | unsigned replaceable : 1; /* 1 if we can substitute the strength-reduced |
105 | variable for the original variable. | |
106 | 0 means they must be kept separate and the | |
107 | new one must be copied into the old pseudo | |
108 | reg each time the old one is set. */ | |
109 | unsigned not_replaceable : 1; /* Used to prevent duplicating work. This is | |
110 | 1 if we know that the giv definitely can | |
111 | not be made replaceable, in which case we | |
112 | don't bother checking the variable again | |
113 | even if further info is available. | |
114 | Both this and the above can be zero. */ | |
115 | unsigned ignore : 1; /* 1 prohibits further processing of giv */ | |
125e4dcf JW |
116 | unsigned always_computable : 1;/* 1 if this value is computable every |
117 | iteration. */ | |
118 | unsigned always_executed : 1; /* 1 if this set occurs each iteration. */ | |
8fd297fb RK |
119 | unsigned maybe_multiple : 1; /* Only used for a biv and 1 if this biv |
120 | update may be done multiple times per | |
fd5d5b07 | 121 | iteration. */ |
23b2ce53 RS |
122 | unsigned cant_derive : 1; /* For giv's, 1 if this giv cannot derive |
123 | another giv. This occurs in many cases | |
124 | where a giv's lifetime spans an update to | |
fd5d5b07 | 125 | a biv. */ |
23b2ce53 RS |
126 | unsigned maybe_dead : 1; /* 1 if this giv might be dead. In that case, |
127 | we won't use it to eliminate a biv, it | |
fd5d5b07 | 128 | would probably lose. */ |
125e4dcf | 129 | unsigned auto_inc_opt : 1; /* 1 if this giv had its increment output next |
fd5d5b07 | 130 | to it to try to form an auto-inc address. */ |
7e7ca3a1 JW |
131 | unsigned unrolled : 1; /* 1 if new register has been allocated and |
132 | initialized in unrolled loop. */ | |
9ae8ffe7 | 133 | unsigned shared : 1; |
fd5d5b07 | 134 | unsigned no_const_addval : 1; /* 1 if add_val does not contain a const. */ |
23b2ce53 | 135 | int lifetime; /* Length of life of this giv */ |
23b2ce53 RS |
136 | rtx derive_adjustment; /* If nonzero, is an adjustment to be |
137 | subtracted from add_val when this giv | |
138 | derives another. This occurs when the | |
fd5d5b07 | 139 | giv spans a biv update by incrementation. */ |
affd4f33 | 140 | rtx ext_dependent; /* If nonzero, is a sign or zero extension |
ff7cc307 | 141 | if a biv on which this giv is dependent. */ |
23b2ce53 RS |
142 | struct induction *next_iv; /* For givs, links together all givs that are |
143 | based on the same biv. For bivs, links | |
144 | together all biv entries that refer to the | |
145 | same biv register. */ | |
146 | struct induction *same; /* If this giv has been combined with another | |
147 | giv, this points to the base giv. The base | |
cc2902df | 148 | giv will have COMBINED_WITH nonzero. */ |
3245eea0 | 149 | HOST_WIDE_INT const_adjust; /* Used by loop unrolling, when an address giv |
23b2ce53 RS |
150 | is split, and a constant is eliminated from |
151 | the address, the -constant is stored here | |
fd5d5b07 | 152 | for later use. */ |
2a2af110 JW |
153 | struct induction *same_insn; /* If there are multiple identical givs in |
154 | the same insn, then all but one have this | |
155 | field set, and they all point to the giv | |
156 | that doesn't have this field set. */ | |
3ec2b590 | 157 | rtx last_use; /* For a giv made from a biv increment, this is |
fd5d5b07 | 158 | a substitute for the lifetime information. */ |
23b2ce53 RS |
159 | }; |
160 | ||
14be28e5 | 161 | |
23b2ce53 RS |
162 | /* A `struct iv_class' is created for each biv. */ |
163 | ||
fd5d5b07 KH |
164 | struct iv_class |
165 | { | |
770ae6cc | 166 | unsigned int regno; /* Pseudo reg which is the biv. */ |
23b2ce53 RS |
167 | int biv_count; /* Number of insns setting this reg. */ |
168 | struct induction *biv; /* List of all insns that set this reg. */ | |
169 | int giv_count; /* Number of DEST_REG givs computed from this | |
170 | biv. The resulting count is only used in | |
171 | check_dbra_loop. */ | |
172 | struct induction *giv; /* List of all insns that compute a giv | |
173 | from this reg. */ | |
e304a8e6 MH |
174 | int total_benefit; /* Sum of BENEFITs of all those givs. */ |
175 | rtx initial_value; /* Value of reg at loop start. */ | |
176 | rtx initial_test; /* Test performed on BIV before loop. */ | |
177 | rtx final_value; /* Value of reg at loop end, if known. */ | |
178 | struct iv_class *next; /* Links all class structures together. */ | |
fd5d5b07 KH |
179 | rtx init_insn; /* insn which initializes biv, 0 if none. */ |
180 | rtx init_set; /* SET of INIT_INSN, if any. */ | |
23b2ce53 | 181 | unsigned incremented : 1; /* 1 if somewhere incremented/decremented */ |
e304a8e6 MH |
182 | unsigned eliminable : 1; /* 1 if plausible candidate for |
183 | elimination. */ | |
184 | unsigned nonneg : 1; /* 1 if we added a REG_NONNEG note for | |
185 | this. */ | |
23b2ce53 | 186 | unsigned reversed : 1; /* 1 if we reversed the loop that this |
fd5d5b07 | 187 | biv controls. */ |
e304a8e6 | 188 | unsigned all_reduced : 1; /* 1 if all givs using this biv have |
19eb1ad7 | 189 | been reduced. */ |
23b2ce53 RS |
190 | }; |
191 | ||
14be28e5 MH |
192 | |
193 | /* Definitions used by the basic induction variable discovery code. */ | |
194 | enum iv_mode | |
afa1738b | 195 | { |
14be28e5 MH |
196 | UNKNOWN_INDUCT, |
197 | BASIC_INDUCT, | |
198 | NOT_BASIC_INDUCT, | |
199 | GENERAL_INDUCT | |
200 | }; | |
afa1738b | 201 | |
14be28e5 MH |
202 | |
203 | /* A `struct iv' is created for every register. */ | |
204 | ||
205 | struct iv | |
ed5bb68d | 206 | { |
14be28e5 | 207 | enum iv_mode type; |
e11e816e | 208 | union |
14be28e5 MH |
209 | { |
210 | struct iv_class *class; | |
211 | struct induction *info; | |
212 | } iv; | |
213 | }; | |
214 | ||
215 | ||
216 | #define REG_IV_TYPE(ivs, n) ivs->regs[n].type | |
217 | #define REG_IV_INFO(ivs, n) ivs->regs[n].iv.info | |
218 | #define REG_IV_CLASS(ivs, n) ivs->regs[n].iv.class | |
fd5d5b07 | 219 | |
14be28e5 MH |
220 | |
221 | struct loop_ivs | |
222 | { | |
ed5bb68d | 223 | /* Indexed by register number, contains pointer to `struct |
14be28e5 MH |
224 | iv' if register is an induction variable. */ |
225 | struct iv *regs; | |
ed5bb68d | 226 | |
14be28e5 MH |
227 | /* Size of regs array. */ |
228 | unsigned int n_regs; | |
fd5d5b07 | 229 | |
ed5bb68d MH |
230 | /* The head of a list which links together (via the next field) |
231 | every iv class for the current loop. */ | |
14be28e5 | 232 | struct iv_class *list; |
ed5bb68d MH |
233 | }; |
234 | ||
14be28e5 MH |
235 | |
236 | typedef struct loop_mem_info | |
237 | { | |
238 | rtx mem; /* The MEM itself. */ | |
239 | rtx reg; /* Corresponding pseudo, if any. */ | |
240 | int optimize; /* Nonzero if we can optimize access to this MEM. */ | |
241 | } loop_mem_info; | |
242 | ||
243 | ||
1ecd860b | 244 | |
f1d4ac80 MH |
245 | struct loop_reg |
246 | { | |
247 | /* Number of times the reg is set during the loop being scanned. | |
248 | During code motion, a negative value indicates a reg that has | |
249 | been made a candidate; in particular -2 means that it is an | |
250 | candidate that we know is equal to a constant and -1 means that | |
251 | it is an candidate not known equal to a constant. After code | |
252 | motion, regs moved have 0 (which is accurate now) while the | |
253 | failed candidates have the original number of times set. | |
fd5d5b07 | 254 | |
1ecd860b MH |
255 | Therefore, at all times, == 0 indicates an invariant register; |
256 | < 0 a conditionally invariant one. */ | |
f1d4ac80 | 257 | int set_in_loop; |
1ecd860b MH |
258 | |
259 | /* Original value of set_in_loop; same except that this value | |
260 | is not set negative for a reg whose sets have been made candidates | |
261 | and not set to 0 for a reg that is moved. */ | |
f1d4ac80 | 262 | int n_times_set; |
fd5d5b07 | 263 | |
1ecd860b MH |
264 | /* Contains the insn in which a register was used if it was used |
265 | exactly once; contains const0_rtx if it was used more than once. */ | |
f1d4ac80 MH |
266 | rtx single_usage; |
267 | ||
268 | /* Nonzero indicates that the register cannot be moved or strength | |
269 | reduced. */ | |
270 | char may_not_optimize; | |
fd5d5b07 | 271 | |
1ecd860b MH |
272 | /* Nonzero means reg N has already been moved out of one loop. |
273 | This reduces the desire to move it out of another. */ | |
f1d4ac80 MH |
274 | char moved_once; |
275 | }; | |
276 | ||
1ecd860b | 277 | |
f1d4ac80 MH |
278 | struct loop_regs |
279 | { | |
280 | int num; /* Number of regs used in table. */ | |
281 | int size; /* Size of table. */ | |
282 | struct loop_reg *array; /* Register usage info. array. */ | |
283 | int multiple_uses; /* Nonzero if a reg has multiple uses. */ | |
1ecd860b MH |
284 | }; |
285 | ||
6ec92010 | 286 | |
f1d4ac80 | 287 | |
6ec92010 MH |
288 | struct loop_movables |
289 | { | |
290 | /* Head of movable chain. */ | |
291 | struct movable *head; | |
292 | /* Last movable in chain. */ | |
293 | struct movable *last; | |
6ec92010 MH |
294 | }; |
295 | ||
296 | ||
1ecd860b | 297 | /* Information pertaining to a loop. */ |
302670f3 MH |
298 | |
299 | struct loop_info | |
300 | { | |
3c748bb6 MH |
301 | /* Nonzero if there is a subroutine call in the current loop. */ |
302 | int has_call; | |
6ec92010 MH |
303 | /* Nonzero if there is a libcall in the current loop. */ |
304 | int has_libcall; | |
305 | /* Nonzero if there is a non constant call in the current loop. */ | |
306 | int has_nonconst_call; | |
62e6ca55 JJ |
307 | /* Nonzero if there is a prefetch instruction in the current loop. */ |
308 | int has_prefetch; | |
3c748bb6 MH |
309 | /* Nonzero if there is a volatile memory reference in the current |
310 | loop. */ | |
311 | int has_volatile; | |
312 | /* Nonzero if there is a tablejump in the current loop. */ | |
313 | int has_tablejump; | |
314 | /* Nonzero if there are ways to leave the loop other than falling | |
315 | off the end. */ | |
316 | int has_multiple_exit_targets; | |
317 | /* Nonzero if there is an indirect jump in the current function. */ | |
318 | int has_indirect_jump; | |
8b583747 AM |
319 | /* Whether loop unrolling has emitted copies of the loop body so |
320 | that the main loop needs no exit tests. */ | |
321 | int preconditioned; | |
302670f3 MH |
322 | /* Register or constant initial loop value. */ |
323 | rtx initial_value; | |
324 | /* Register or constant value used for comparison test. */ | |
325 | rtx comparison_value; | |
326 | /* Register or constant approximate final value. */ | |
327 | rtx final_value; | |
328 | /* Register or constant initial loop value with term common to | |
329 | final_value removed. */ | |
330 | rtx initial_equiv_value; | |
331 | /* Register or constant final loop value with term common to | |
332 | initial_value removed. */ | |
333 | rtx final_equiv_value; | |
334 | /* Register corresponding to iteration variable. */ | |
335 | rtx iteration_var; | |
336 | /* Constant loop increment. */ | |
337 | rtx increment; | |
338 | enum rtx_code comparison_code; | |
339 | /* Holds the number of loop iterations. It is zero if the number | |
340 | could not be calculated. Must be unsigned since the number of | |
341 | iterations can be as high as 2^wordsize - 1. For loops with a | |
342 | wider iterator, this number will be zero if the number of loop | |
343 | iterations is too large for an unsigned integer to hold. */ | |
344 | unsigned HOST_WIDE_INT n_iterations; | |
3c748bb6 | 345 | /* The number of times the loop body was unrolled. */ |
35704c46 | 346 | unsigned int unroll_number; |
a2be868f | 347 | int used_count_register; |
0a5b41f2 MH |
348 | /* The loop iterator induction variable. */ |
349 | struct iv_class *iv; | |
afa1738b MH |
350 | /* List of MEMs that are stored in this loop. */ |
351 | rtx store_mems; | |
352 | /* Array of MEMs that are used (read or written) in this loop, but | |
353 | cannot be aliased by anything in this loop, except perhaps | |
354 | themselves. In other words, if mems[i] is altered during | |
355 | the loop, it is altered by an expression that is rtx_equal_p to | |
356 | it. */ | |
357 | loop_mem_info *mems; | |
358 | /* The index of the next available slot in MEMS. */ | |
359 | int mems_idx; | |
360 | /* The number of elements allocated in MEMS. */ | |
361 | int mems_allocated; | |
362 | /* Nonzero if we don't know what MEMs were changed in the current | |
363 | loop. This happens if the loop contains a call (in which case | |
364 | `has_call' will also be set) or if we store into more than | |
365 | NUM_STORES MEMs. */ | |
366 | int unknown_address_altered; | |
367 | /* The above doesn't count any readonly memory locations that are | |
368 | stored. This does. */ | |
369 | int unknown_constant_address_altered; | |
370 | /* Count of memory write instructions discovered in the loop. */ | |
371 | int num_mem_sets; | |
372 | /* The insn where the first of these was found. */ | |
373 | rtx first_loop_store_insn; | |
6ec92010 MH |
374 | /* The chain of movable insns in loop. */ |
375 | struct loop_movables movables; | |
1ecd860b MH |
376 | /* The registers used the in loop. */ |
377 | struct loop_regs regs; | |
ed5bb68d MH |
378 | /* The induction variable information in loop. */ |
379 | struct loop_ivs ivs; | |
cc2902df | 380 | /* Nonzero if call is in pre_header extended basic block. */ |
e304a8e6 | 381 | int pre_header_has_call; |
302670f3 MH |
382 | }; |
383 | ||
23b2ce53 RS |
384 | |
385 | /* Variables declared in loop.c, but also needed in unroll.c. */ | |
386 | ||
387 | extern int *uid_luid; | |
388 | extern int max_uid_for_loop; | |
770ae6cc | 389 | extern unsigned int max_reg_before_loop; |
a2be868f | 390 | extern struct loop **uid_loop; |
23b2ce53 RS |
391 | extern FILE *loop_dump_stream; |
392 | ||
3ec2b590 | 393 | |
23b2ce53 RS |
394 | /* Forward declarations for non-static functions declared in loop.c and |
395 | unroll.c. */ | |
0534b804 MH |
396 | int loop_invariant_p PARAMS ((const struct loop *, rtx)); |
397 | rtx get_condition_for_loop PARAMS ((const struct loop *, rtx)); | |
96a45535 MH |
398 | void loop_iv_add_mult_hoist PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); |
399 | void loop_iv_add_mult_sink PARAMS ((const struct loop *, rtx, rtx, rtx, rtx)); | |
e11e816e | 400 | void loop_iv_add_mult_emit_before PARAMS ((const struct loop *, rtx, |
96a45535 MH |
401 | rtx, rtx, rtx, |
402 | basic_block, rtx)); | |
3fe41456 | 403 | rtx express_from PARAMS ((struct induction *, struct induction *)); |
e8cb4873 | 404 | rtx extend_value_for_giv PARAMS ((struct induction *, rtx)); |
3fe41456 | 405 | |
96a45535 | 406 | void unroll_loop PARAMS ((struct loop *, int, int)); |
099f0f3f | 407 | rtx biv_total_increment PARAMS ((const struct iv_class *)); |
3fe41456 | 408 | unsigned HOST_WIDE_INT loop_iterations PARAMS ((struct loop *)); |
0534b804 | 409 | int precondition_loop_p PARAMS ((const struct loop *, |
fd5d5b07 KH |
410 | rtx *, rtx *, rtx *, |
411 | enum machine_mode *mode)); | |
0534b804 MH |
412 | rtx final_biv_value PARAMS ((const struct loop *, struct iv_class *)); |
413 | rtx final_giv_value PARAMS ((const struct loop *, struct induction *)); | |
3fe41456 | 414 | void emit_unrolled_add PARAMS ((rtx, rtx, rtx)); |
0534b804 | 415 | int back_branch_in_range_p PARAMS ((const struct loop *, rtx)); |
8c660648 | 416 | |
3fe41456 | 417 | int loop_insn_first_p PARAMS ((rtx, rtx)); |
e8cb4873 | 418 | typedef rtx (*loop_insn_callback) PARAMS ((struct loop *, rtx, int, int)); |
5e787f07 | 419 | void for_each_insn_in_loop PARAMS ((struct loop *, loop_insn_callback)); |
e11e816e | 420 | rtx loop_insn_emit_before PARAMS((const struct loop *, basic_block, |
86e21212 | 421 | rtx, rtx)); |
96a45535 | 422 | rtx loop_insn_sink PARAMS((const struct loop *, rtx)); |
804a718a | 423 | rtx loop_insn_hoist PARAMS((const struct loop *, rtx)); |
cac8ce95 | 424 | |
5527bf14 RH |
425 | /* Forward declarations for non-static functions declared in doloop.c. */ |
426 | int doloop_optimize PARAMS ((const struct loop *)); |