Commit | Line | Data |
---|---|---|
91df63bb WJ |
1 | /* Move constant computations out of loops. |
2 | Copyright (C) 1987, 1988, 1989 Free Software Foundation, Inc. | |
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 1, 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 | |
18 | the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ | |
19 | ||
20 | ||
21 | /* This is the loop optimization pass of the compiler. | |
22 | It finds invariant computations within loops and moves them | |
23 | to the beginning of the loop. Then it identifies basic and | |
24 | general induction variables. Strength reduction is applied to the general | |
25 | induction variables, and induction variable elimination is applied to | |
26 | the basic induction variables. | |
27 | ||
28 | It also finds cases where | |
29 | a register is set within the loop by zero-extending a narrower value | |
30 | and changes these to zero the entire register once before the loop | |
31 | and merely copy the low part within the loop. | |
32 | ||
33 | Most of the complexity is in heuristics to decide when it is worth | |
34 | while to do these things. */ | |
35 | ||
36 | /* ??? verify_loop would run faster if we made one table | |
37 | of the minimum and maximum luids from which each label is reached. | |
38 | Also, it would be faster if loop_store_addrs were a hash table. */ | |
39 | ||
40 | #include "config.h" | |
41 | #include "rtl.h" | |
42 | #include "expr.h" | |
43 | #include "insn-config.h" | |
44 | #include "regs.h" | |
45 | #include "hard-reg-set.h" | |
46 | #include "recog.h" | |
47 | #include "flags.h" | |
48 | #include <stdio.h> | |
49 | ||
50 | /* Vector mapping INSN_UIDs to luids. | |
51 | The luids are like uids but increase monononically always. | |
52 | We use them to see whether a jump comes from outside a given loop. */ | |
53 | ||
54 | static int *uid_luid; | |
55 | ||
56 | /* Get the luid of an insn. */ | |
57 | ||
58 | #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)]) | |
59 | ||
60 | /* 1 + largest uid of any insn. */ | |
61 | ||
62 | static int max_uid; | |
63 | ||
64 | /* 1 + luid of last insn. */ | |
65 | ||
66 | static int max_luid; | |
67 | ||
68 | /* Nonzero if somewhere in the current loop | |
69 | there is either a subroutine call, | |
70 | or a store into a memory address that is not fixed, | |
71 | or a store in a BLKmode memory operand, | |
72 | or too many different fixed addresses stored in | |
73 | to record them all in `loop_store_addrs'. | |
74 | ||
75 | In any of these cases, no memory location can be regarded | |
76 | as invariant. */ | |
77 | ||
78 | static int unknown_address_altered; | |
79 | ||
80 | /* Nonzero if somewhere in the current loop there is a store | |
81 | into a memory address that is not fixed but is known to be | |
82 | part of an aggregate. | |
83 | ||
84 | In this case, no memory reference in an aggregate may be | |
85 | considered invariant. */ | |
86 | ||
87 | static int unknown_aggregate_altered; | |
88 | ||
89 | /* Nonzero if somewhere in the current loop there is a store | |
90 | into a memory address other than a fixed address not in an aggregate. | |
91 | ||
92 | In this case, no memory reference in an aggregate at a varying address | |
93 | may be considered invariant. */ | |
94 | ||
95 | static int fixed_aggregate_altered; | |
96 | ||
97 | /* Nonzero if there is a subroutine call in the current loop. | |
98 | (unknown_address_altered is also nonzero in this case.) */ | |
99 | ||
100 | static int loop_has_call; | |
101 | ||
102 | /* Added loop_continue which is the NOTE_INSN_LOOP_CONT of the | |
103 | current loop. A continue statement will generate a branch to | |
104 | NEXT_INSN (loop_continue). */ | |
105 | ||
106 | static rtx loop_continue; | |
107 | ||
108 | /* Indexed by register number, contains the number of times the reg | |
109 | is set during the loop being scanned. | |
110 | During code motion, -1 indicates a reg that has been made a candidate. | |
111 | After code motion, regs moved have 0 (which is accurate now) | |
112 | while the failed candidates have the original number of times set. | |
113 | ||
114 | Therefore, at all times, 0 indicates an invariant register; | |
115 | -1 a conditionally invariant one. */ | |
116 | ||
117 | static short *n_times_set; | |
118 | ||
119 | /* Original value of n_times_set; same except that this value | |
120 | is not set to -1 for a reg whose sets have been made candidates | |
121 | and not set to 0 for a reg that is moved. */ | |
122 | ||
123 | static short *n_times_used; | |
124 | ||
125 | /* Index by register number, 1 indicates that the register | |
126 | cannot be moved or strength reduced. */ | |
127 | ||
128 | static char *may_not_optimize; | |
129 | ||
130 | /* Nonzero means reg N has already been moved out of one loop. | |
131 | This reduces the desire to move it out of another. */ | |
132 | ||
133 | static char *moved_once; | |
134 | ||
135 | /* Array of fixed memory addresses that are stored in this loop. | |
136 | If there are too many to fit here, | |
137 | we just turn on unknown_address_altered. */ | |
138 | ||
139 | #define NUM_STORES 10 | |
140 | static rtx loop_store_addrs[NUM_STORES]; | |
141 | static int loop_store_widths[NUM_STORES]; | |
142 | ||
143 | /* Index of first available slot in above array. */ | |
144 | static int loop_store_addrs_idx; | |
145 | ||
146 | /* Count of movable (i.e. invariant) instructions discovered in the loop. */ | |
147 | static int num_movables; | |
148 | ||
149 | /* Count of memory write instructions discovered in the loop. */ | |
150 | static int num_mem_sets; | |
151 | ||
152 | /* Number of loops contained within the current one, including itself. */ | |
153 | static int loops_enclosed; | |
154 | ||
155 | /* Bound on pseudo register number before loop optimization. | |
156 | A pseudo has valid regscan info if its number is < old_max_reg. */ | |
157 | static int old_max_reg; | |
158 | ||
159 | /* During the analysis of a loop, a chain of `struct movable's | |
160 | is made to record all the movable insns found. | |
161 | Then the entire chain can be scanned to decide which to move. */ | |
162 | ||
163 | struct movable | |
164 | { | |
165 | rtx insn; /* A movable insn */ | |
166 | rtx set_src; /* The expression this reg is set from. | |
167 | Either SET_SRC (body) or a REG_EQUAL. */ | |
168 | int consec; /* Number of consecutive following insns | |
169 | that must be moved with this one. */ | |
170 | int regno; /* The register it sets */ | |
171 | short lifetime; /* lifetime of that register; | |
172 | may be adjusted when matching movables | |
173 | that load the same value are found. */ | |
174 | short savings; /* Number of insns we can move for this reg, | |
175 | including other movables that force this | |
176 | or match this one. */ | |
177 | unsigned int cond : 1; /* 1 if only conditionally movable */ | |
178 | unsigned int force : 1; /* 1 means MUST move this insn */ | |
179 | unsigned int global : 1; /* 1 means reg is live outside this loop */ | |
180 | /* If PARTIAL is 1, GLOBAL means something different: | |
181 | that the reg is live outside the range from where it is set | |
182 | to the following label. */ | |
183 | unsigned int done : 1; /* 1 inhibits further processing of this */ | |
184 | /* 1 in PARTIAL means this reg is used for zero-extending. | |
185 | In particular, moving it does not make it invariant. */ | |
186 | unsigned int partial : 1; | |
187 | enum machine_mode savemode; /* Nonzero means it is a mode for a low part | |
188 | that we should avoid changing when clearing | |
189 | the rest of the reg. */ | |
190 | struct movable *match; /* First entry for same value */ | |
191 | struct movable *forces; /* An insn that must be moved if this is */ | |
192 | struct movable *next; | |
193 | }; | |
194 | ||
195 | static FILE *loop_dump_stream; | |
196 | ||
197 | /* Forward declarations. */ | |
198 | ||
199 | struct induction; | |
200 | struct iv_class; | |
201 | ||
202 | static rtx loop_find_reg_equal (); | |
203 | static int reg_in_basic_block_p (); | |
204 | static rtx verify_loop (); | |
205 | static int invariant_p (); | |
206 | static int consec_sets_invariant_p (); | |
207 | static int can_jump_into_range_p (); | |
208 | static int labels_in_range_p (); | |
209 | static void count_loop_regs_set (); | |
210 | static void note_addr_stored (); | |
211 | static int loop_reg_used_before_p (); | |
212 | static void constant_high_bytes (); | |
213 | static void scan_loop (); | |
214 | static rtx replace_regs (); | |
215 | static void replace_call_address (); | |
216 | static rtx skip_consec_insns (); | |
217 | static void ignore_some_movables (); | |
218 | static void force_movables (); | |
219 | static void combine_movables (); | |
220 | static int rtx_equal_for_loop_p (); | |
221 | static void move_movables (); | |
222 | static void strength_reduce (); | |
223 | static void find_mem_givs (); | |
224 | static void record_giv (); | |
225 | static void delete_insn_forces (); | |
226 | static int basic_induction_var (); | |
227 | static int general_induction_var (); | |
228 | static int consec_sets_giv (); | |
229 | static int check_dbra_loop (); | |
230 | static void emit_iv_init_code (); | |
231 | static int product_cheap_p (); | |
232 | static void emit_iv_inc (); | |
233 | static void check_eliminate_biv (); | |
234 | static int can_eliminate_biv_p (); | |
235 | static void eliminate_biv (); | |
236 | static rtx final_biv_value (); | |
237 | static int last_use_this_basic_block (); | |
238 | \f | |
239 | /* Entry point of this file. Perform loop optimization | |
240 | on the current function. F is the first insn of the function | |
241 | and DUMPFILE is a stream for output of a trace of actions taken | |
242 | (or 0 if none should be output). */ | |
243 | ||
244 | void | |
245 | loop_optimize (f, dumpfile) | |
246 | /* f is the first instruction of a chain of insns for one function */ | |
247 | rtx f; | |
248 | FILE *dumpfile; | |
249 | { | |
250 | register rtx insn; | |
251 | register int i; | |
252 | rtx end; | |
253 | rtx last_insn; | |
254 | ||
255 | loop_dump_stream = dumpfile; | |
256 | ||
257 | init_recog (); | |
258 | ||
259 | old_max_reg = max_reg_num (); | |
260 | ||
261 | moved_once = (char *) alloca (old_max_reg); | |
262 | bzero (moved_once, old_max_reg); | |
263 | ||
264 | /* First find the last real insn, and count the number of insns, | |
265 | and assign insns their luids. */ | |
266 | ||
267 | for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) | |
268 | if (INSN_UID (insn) > i) | |
269 | i = INSN_UID (insn); | |
270 | ||
271 | max_uid = i + 1; | |
272 | uid_luid = (int *) alloca ((i + 1) * sizeof (int)); | |
273 | bzero (uid_luid, (i + 1) * sizeof (int)); | |
274 | ||
275 | /* Compute the mapping from uids to luids. | |
276 | LUIDs are numbers assigned to insns, like uids, | |
277 | except that luids increase monotonically through the code. | |
278 | Don't assign luids to line-number NOTEs, so that the distance in luids | |
279 | between two insns is not affected by -g. */ | |
280 | ||
281 | for (insn = f, i = 0; insn; insn = NEXT_INSN (insn)) | |
282 | { | |
283 | last_insn = insn; | |
284 | if (GET_CODE (insn) != NOTE | |
285 | || NOTE_LINE_NUMBER (insn) < 0) | |
286 | INSN_LUID (insn) = ++i; | |
287 | else | |
288 | /* Give a line number note the same luid as preceding insn. */ | |
289 | INSN_LUID (insn) = i; | |
290 | } | |
291 | ||
292 | max_luid = i; | |
293 | ||
294 | /* Don't leave gaps in uid_luid for insns that have been | |
295 | deleted. It is possible that the first or last insn | |
296 | using some register has been deleted by cross-jumping. | |
297 | Make sure that uid_luid for that former insn's uid | |
298 | points to the general area where that insn used to be. */ | |
299 | for (i = 0; i < max_uid; i++) | |
300 | { | |
301 | uid_luid[0] = uid_luid[i]; | |
302 | if (uid_luid[0] != 0) | |
303 | break; | |
304 | } | |
305 | for (i = 0; i < max_uid; i++) | |
306 | if (uid_luid[i] == 0) | |
307 | uid_luid[i] = uid_luid[i - 1]; | |
308 | ||
309 | /* Find and process each loop. | |
310 | We scan from the end, and process each loop when its start is seen, | |
311 | so we process innermost loops first. */ | |
312 | ||
313 | for (insn = last_insn; insn; insn = PREV_INSN (insn)) | |
314 | if (GET_CODE (insn) == NOTE | |
315 | && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) | |
316 | { | |
317 | /* Make sure it really is a loop -- no jumps in from outside. */ | |
318 | end = verify_loop (f, insn); | |
319 | if (end != 0) | |
320 | /* If so, optimize this loop. */ | |
321 | scan_loop (insn, end, max_reg_num ()); | |
322 | else if (loop_dump_stream) | |
323 | fprintf (loop_dump_stream, | |
324 | "\nLoop at %d ignored due to multiple entry points.\n", | |
325 | INSN_UID (insn)); | |
326 | } | |
327 | } | |
328 | \f | |
329 | /* Optimize one loop whose start is LOOP_START and end is END. | |
330 | LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching | |
331 | NOTE_INSN_LOOP_END. */ | |
332 | ||
333 | /* ??? can also move memory writes out of loop if destination | |
334 | address is invariant? */ | |
335 | ||
336 | static void | |
337 | scan_loop (loop_start, end, nregs) | |
338 | rtx loop_start, end; | |
339 | int nregs; | |
340 | { | |
341 | register int i; | |
342 | register rtx p = NEXT_INSN (loop_start); | |
343 | /* 1 if we are scanning insns that could be executed zero times. */ | |
344 | int maybe_never = 0; | |
345 | /* 1 if we are scanning insns that might never be executed | |
346 | due to a subroutine call which might exit before they are reached. */ | |
347 | int call_passed = 0; | |
348 | /* For a rotated loop that is entered near the bottom, | |
349 | this is the label at the top. Otherwise it is zero. */ | |
350 | rtx loop_top = 0; | |
351 | /* Jump insn that enters the loop, or 0 if control drops in. */ | |
352 | rtx loop_entry_jump = 0; | |
353 | /* Place in the loop where control enters. */ | |
354 | rtx scan_start; | |
355 | /* Number of insns in the loop. */ | |
356 | int insn_count; | |
357 | int tem; | |
358 | rtx temp; | |
359 | /* Chain describing insns movable in current loop. */ | |
360 | struct movable *movables = 0; | |
361 | /* Last element in `movables' -- so we can add elements at the end. */ | |
362 | struct movable *last_movable = 0; | |
363 | /* Ratio of extra register life span we can justify | |
364 | for saving an instruction. More if loop doesn't call subroutines | |
365 | since in that case saving an insn makes more difference | |
366 | and more registers are available. */ | |
367 | int threshold = loop_has_call ? 15 : 30; | |
368 | /* Nonzero if the insn that jumps into the real loop | |
369 | is not the very first thing after the loop-beginning note. */ | |
370 | int something_before_entry_jump = 0; | |
371 | ||
372 | n_times_set = (short *) alloca (nregs * sizeof (short)); | |
373 | n_times_used = (short *) alloca (nregs * sizeof (short)); | |
374 | may_not_optimize = (char *) alloca (nregs); | |
375 | ||
376 | /* Determine whether this loop starts with a jump down | |
377 | to a test at the end. */ | |
378 | while (p != end | |
379 | && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN) | |
380 | { | |
381 | if (GET_CODE (p) == CALL_INSN || GET_CODE (p) == INSN) | |
382 | something_before_entry_jump = 1; | |
383 | p = NEXT_INSN (p); | |
384 | } | |
385 | ||
386 | /* "Loop" contains neither jumps nor labels; | |
387 | it must have been a dummy. Think no more about it. */ | |
388 | if (p == end) | |
389 | return; | |
390 | ||
391 | scan_start = p; | |
392 | ||
393 | /* If loop has a jump before the first label, | |
394 | the true entry is the target of that jump. | |
395 | Start scan from there. | |
396 | But record in LOOP_TOP the place where the end-test jumps | |
397 | back to so we can scan that after the end of the loop. */ | |
398 | if (GET_CODE (p) == JUMP_INSN) | |
399 | { | |
400 | loop_entry_jump = p; | |
401 | loop_top = NEXT_INSN (p); | |
402 | /* Loop entry will never be a conditional jump. | |
403 | If we see one, this must not be a real loop. | |
404 | Also, a return-insn isn't a jump to enter the loop. */ | |
405 | if (GET_CODE (loop_top) != BARRIER | |
406 | || GET_CODE (PATTERN (p)) != SET) | |
407 | return; | |
408 | /* Get the label at which the loop is entered. */ | |
409 | p = XEXP (SET_SRC (PATTERN (p)), 0); | |
410 | /* Check to see whether the jump actually | |
411 | jumps out of the loop (meaning it's no loop). | |
412 | This case can happen for things like | |
413 | do {..} while (0). */ | |
414 | if (p == 0 | |
415 | || INSN_LUID (p) < INSN_LUID (loop_start) | |
416 | || INSN_LUID (p) >= INSN_LUID (end)) | |
417 | { | |
418 | if (loop_dump_stream) | |
419 | fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n", | |
420 | INSN_UID (loop_start), INSN_UID (end)); | |
421 | return; | |
422 | } | |
423 | ||
424 | /* Find the first label after the entry-jump. */ | |
425 | while (GET_CODE (loop_top) != CODE_LABEL) | |
426 | { | |
427 | loop_top = NEXT_INSN (loop_top); | |
428 | if (loop_top == 0) | |
429 | abort (); | |
430 | } | |
431 | ||
432 | /* Maybe rearrange the loop to drop straight in | |
433 | with a new test to jump around it entirely. | |
434 | (The latter is considered outside the loop.) | |
435 | If this is done, we no longer enter with a jump. */ | |
436 | if (! something_before_entry_jump | |
437 | && loop_skip_over (loop_start, end, loop_entry_jump)) | |
438 | { | |
439 | scan_start = loop_top; | |
440 | loop_top = 0; | |
441 | } | |
442 | else | |
443 | /* We really do enter with a jump; | |
444 | scan the loop from the place where the jump jumps to. */ | |
445 | scan_start = p; | |
446 | } | |
447 | ||
448 | /* Count number of times each reg is set during this loop. | |
449 | Set may_not_optimize[I] if it is not safe to move out | |
450 | the setting of register I. */ | |
451 | ||
452 | bzero (n_times_set, nregs * sizeof (short)); | |
453 | bzero (may_not_optimize, nregs); | |
454 | count_loop_regs_set (loop_top ? loop_top : loop_start, end, | |
455 | may_not_optimize, &insn_count, nregs); | |
456 | for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) | |
457 | may_not_optimize[i] = 1, n_times_set[i] = 1; | |
458 | bcopy (n_times_set, n_times_used, nregs * sizeof (short)); | |
459 | ||
460 | if (loop_dump_stream) | |
461 | { | |
462 | fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns.\n", | |
463 | INSN_UID (loop_start), INSN_UID (end), insn_count); | |
464 | if (loop_continue) | |
465 | fprintf (loop_dump_stream, "Continue at insn %d.\n", | |
466 | INSN_UID (loop_continue)); | |
467 | } | |
468 | ||
469 | /* Scan through the loop finding insns that are safe to move. | |
470 | In each such insn, store QImode as the mode, to mark it. | |
471 | Then set n_times_set to -1 for the reg being set, so that | |
472 | this reg will be considered invariant for subsequent insns. | |
473 | We consider whether subsequent insns use the reg | |
474 | in deciding whether it is worth actually moving. | |
475 | ||
476 | MAYBE_NEVER is nonzero if we have passed a conditional jump insn | |
477 | and therefore it is possible that the insns we are scanning | |
478 | would never be executed. At such times, we must make sure | |
479 | that it is safe to execute the insn once instead of zero times. | |
480 | When MAYBE_NEVER is 0, all insns will be executed at least once | |
481 | so that is not a problem. */ | |
482 | ||
483 | p = scan_start; | |
484 | while (1) | |
485 | { | |
486 | p = NEXT_INSN (p); | |
487 | /* At end of a straight-in loop, we are done. | |
488 | At end of a loop entered at the bottom, scan the top. */ | |
489 | if (p == scan_start) | |
490 | break; | |
491 | if (p == end) | |
492 | { | |
493 | if (loop_top != 0) | |
494 | p = NEXT_INSN (loop_top); | |
495 | else | |
496 | break; | |
497 | if (p == scan_start) | |
498 | break; | |
499 | } | |
500 | if (GET_CODE (p) == INSN | |
501 | && GET_CODE (PATTERN (p)) == SET | |
502 | && GET_CODE (SET_DEST (PATTERN (p))) == REG | |
503 | && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))]) | |
504 | { | |
505 | int tem1 = 0; | |
506 | /* Don't try to optimize a register that was made | |
507 | by loop-optimization for an inner loop. | |
508 | We don't know its life-span, so we can't compute the benefit. */ | |
509 | if (REGNO (SET_DEST (PATTERN (p))) >= old_max_reg) | |
510 | ; | |
511 | /* IN order to move a register, we need to have one of three cases: | |
512 | (1) it is used only in the same basic block as the set | |
513 | (2) it is not a user variable. | |
514 | (3) the set is guaranteed to be executed once the loop starts, | |
515 | and the reg is not used until after that. */ | |
516 | else if (! ((! maybe_never | |
517 | && ! loop_reg_used_before_p (p, loop_start, scan_start, end)) | |
518 | || ! REG_USERVAR_P (SET_DEST (PATTERN (p))) | |
519 | || reg_in_basic_block_p (p, SET_DEST (PATTERN (p))))) | |
520 | ; | |
521 | else if (((tem = invariant_p (SET_SRC (PATTERN (p)))) | |
522 | || ((temp = loop_find_reg_equal (p)) | |
523 | && (tem = invariant_p (XEXP (temp, 0))))) | |
524 | && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1 | |
525 | || (tem1 | |
526 | = consec_sets_invariant_p (SET_DEST (PATTERN (p)), | |
527 | n_times_set[REGNO (SET_DEST (PATTERN (p)))], | |
528 | p))) | |
529 | /* If the insn can cause a trap (such as divide by zero), | |
530 | can't move it unless it's guaranteed to be executed | |
531 | once loop is entered. Even a function call might | |
532 | prevent the trap insn from being reached | |
533 | (since it might exit!) */ | |
534 | && ! ((maybe_never || call_passed) | |
535 | && (may_trap_p (SET_SRC (PATTERN (p))) | |
536 | || ((temp = loop_find_reg_equal (p)) | |
537 | && may_trap_p (XEXP (temp, 0)))))) | |
538 | { | |
539 | register struct movable *m; | |
540 | register int regno = REGNO (SET_DEST (PATTERN (p))); | |
541 | int count; | |
542 | m = (struct movable *) alloca (sizeof (struct movable)); | |
543 | m->next = 0; | |
544 | m->insn = p; | |
545 | temp = loop_find_reg_equal (p); | |
546 | if (temp) | |
547 | m->set_src = XEXP (temp, 0); | |
548 | else | |
549 | m->set_src = SET_SRC (PATTERN (p)); | |
550 | m->force = 0; | |
551 | m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1; | |
552 | m->done = 0; | |
553 | m->forces = 0; | |
554 | m->partial = 0; | |
555 | m->savemode = VOIDmode; | |
556 | m->regno = regno; | |
557 | /* Set M->cond if either invariant_p or consec_sets_invariant_p | |
558 | returned 2 (only conditionally invariant). */ | |
559 | m->cond = ((tem | tem1) > 1); | |
560 | m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) | |
561 | || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start)); | |
562 | m->match = 0; | |
563 | m->lifetime = (uid_luid[regno_last_uid[regno]] | |
564 | - uid_luid[regno_first_uid[regno]]); | |
565 | m->savings = n_times_used[regno]; | |
566 | n_times_set[regno] = -1; | |
567 | /* Add M to the end of the chain MOVABLES. */ | |
568 | if (movables == 0) | |
569 | movables = m; | |
570 | else | |
571 | last_movable->next = m; | |
572 | last_movable = m; | |
573 | if (m->consec > 0) | |
574 | { | |
575 | /* Skip this insn, not checking REG_LIBCALL notes. */ | |
576 | p = NEXT_INSN (p); | |
577 | /* Skip the consecutive insns, if there are any. */ | |
578 | p = skip_consec_insns (p, m->consec); | |
579 | /* Back up, so the main loop will advance to the right place. */ | |
580 | p = PREV_INSN (p); | |
581 | } | |
582 | } | |
583 | /* If this register is always set within a STRICT_LOW_PART | |
584 | or set to zero, then its high bytes are constant. | |
585 | So clear them outside the loop and within the loop | |
586 | just load the low bytes. | |
587 | We must check that the machine has an instruction to do so. | |
588 | Also, if the value loaded into the register | |
589 | depends on the same register, this cannot be done. */ | |
590 | else if (SET_SRC (PATTERN (p)) == const0_rtx | |
591 | && GET_CODE (NEXT_INSN (p)) == INSN | |
592 | && GET_CODE (PATTERN (NEXT_INSN (p))) == SET | |
593 | && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p)))) | |
594 | == STRICT_LOW_PART) | |
595 | && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) | |
596 | == SUBREG) | |
597 | && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0)) | |
598 | == SET_DEST (PATTERN (p))) | |
599 | && !reg_mentioned_p (SET_DEST (PATTERN (p)), | |
600 | SET_SRC (PATTERN (NEXT_INSN (p))))) | |
601 | { | |
602 | register int regno = REGNO (SET_DEST (PATTERN (p))); | |
603 | if (n_times_set[regno] == 2) | |
604 | { | |
605 | register struct movable *m; | |
606 | int count; | |
607 | m = (struct movable *) alloca (sizeof (struct movable)); | |
608 | m->next = 0; | |
609 | m->insn = p; | |
610 | m->force = 0; | |
611 | m->consec = 0; | |
612 | m->done = 0; | |
613 | m->forces = 0; | |
614 | m->partial = 1; | |
615 | /* If the insn may not be executed on some cycles, | |
616 | we can't clear the whole reg; clear just high part. | |
617 | Not even if the reg is used only within this loop. | |
618 | Consider this: | |
619 | while (1) | |
620 | while (s != t) { | |
621 | if (foo ()) x = *s; | |
622 | use (x); | |
623 | } | |
624 | Clearing x before the inner loop could clobber a value | |
625 | being saved from the last time around the outer loop. | |
626 | However, if the reg is not used outside this loop | |
627 | and all uses of the register are in the same | |
628 | basic block as the store, there is no problem. */ | |
629 | m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end) | |
630 | || uid_luid[regno_first_uid[regno]] < INSN_LUID (p) | |
631 | || (labels_in_range_p | |
632 | (p, uid_luid[regno_first_uid[regno]]))); | |
633 | if (maybe_never && m->global) | |
634 | m->savemode = GET_MODE (SET_SRC (PATTERN (NEXT_INSN (p)))); | |
635 | else | |
636 | m->savemode = VOIDmode; | |
637 | m->regno = regno; | |
638 | m->cond = 0; | |
639 | m->match = 0; | |
640 | m->lifetime = (uid_luid[regno_last_uid[regno]] | |
641 | - uid_luid[regno_first_uid[regno]]); | |
642 | m->savings = 1; | |
643 | n_times_set[regno] = -1; | |
644 | /* Add M to the end of the chain MOVABLES. */ | |
645 | if (movables == 0) | |
646 | movables = m; | |
647 | else | |
648 | last_movable->next = m; | |
649 | last_movable = m; | |
650 | } | |
651 | } | |
652 | } | |
653 | /* Past a call insn, we get to insns which might not be executed | |
654 | because the call might exit. This matters for insns that trap. */ | |
655 | else if (GET_CODE (p) == CALL_INSN) | |
656 | call_passed = 1; | |
657 | /* Past a label or a jump, we get to insns for which we | |
658 | can't count on whether or how many times they will be | |
659 | executed during each iteration. Therefore, we can | |
660 | only move out sets of trivial variables | |
661 | (those not used after the loop). */ | |
662 | else if ((GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) | |
663 | /* If we enter the loop in the middle, and scan around | |
664 | to the beginning, don't set maybe_never for that. */ | |
665 | && ! (NEXT_INSN (p) == end && GET_CODE (p) == JUMP_INSN | |
666 | && simplejump_p (p))) | |
667 | maybe_never = 1; | |
668 | } | |
669 | ||
670 | /* If one movable subsumes another, ignore that other. */ | |
671 | ||
672 | ignore_some_movables (movables); | |
673 | ||
674 | /* For each movable insn, see if the reg that it loads | |
675 | leads when it dies right into another conditionally movable insn. | |
676 | If so, record that the second insn "forces" the first one, | |
677 | since the second can be moved only if the first is. */ | |
678 | ||
679 | force_movables (movables); | |
680 | ||
681 | /* See if there are multiple movable insns that load the same value. | |
682 | If there are, make all but the first point at the first one | |
683 | through the `match' field, and add the priorities of them | |
684 | all together as the priority of the first. */ | |
685 | ||
686 | combine_movables (movables, nregs); | |
687 | ||
688 | /* Now consider each movable insn to decide whether it is worth moving. | |
689 | Store 0 in n_times_set for each reg that is moved. */ | |
690 | ||
691 | move_movables (movables, threshold, | |
692 | insn_count, loop_start, end, nregs); | |
693 | ||
694 | /* Now candidates that still have -1 are those not moved. | |
695 | Change n_times_set to indicate that those are not actually invariant. */ | |
696 | for (i = 0; i < nregs; i++) | |
697 | if (n_times_set[i] < 0) | |
698 | n_times_set[i] = n_times_used[i]; | |
699 | ||
700 | if (flag_strength_reduce) | |
701 | strength_reduce (scan_start, end, loop_top, | |
702 | insn_count, loop_start, end, nregs); | |
703 | } | |
704 | ||
705 | /* Return 1 if all uses of REG | |
706 | are between INSN and the end of the basic block. */ | |
707 | ||
708 | static int | |
709 | reg_in_basic_block_p (insn, reg) | |
710 | rtx insn, reg; | |
711 | { | |
712 | int regno = REGNO (reg); | |
713 | rtx p; | |
714 | ||
715 | if (regno_first_uid[regno] != INSN_UID (insn)) | |
716 | return 0; | |
717 | ||
718 | /* Search this basic block for the already recorded last use of the reg. */ | |
719 | for (p = insn; p; p = NEXT_INSN (p)) | |
720 | { | |
721 | switch (GET_CODE (p)) | |
722 | { | |
723 | case NOTE: | |
724 | break; | |
725 | ||
726 | case INSN: | |
727 | case CALL_INSN: | |
728 | /* Ordinary insn: if this is the last use, we win. */ | |
729 | if (regno_last_uid[regno] == INSN_UID (p)) | |
730 | return 1; | |
731 | break; | |
732 | ||
733 | case JUMP_INSN: | |
734 | /* Jump insn: if this is the last use, we win. */ | |
735 | if (regno_last_uid[regno] == INSN_UID (p)) | |
736 | return 1; | |
737 | /* Otherwise, it's the end of the basic block, so we lose. */ | |
738 | return 0; | |
739 | ||
740 | case CODE_LABEL: | |
741 | case BARRIER: | |
742 | /* It's the end of the basic block, so we lose. */ | |
743 | return 0; | |
744 | } | |
745 | } | |
746 | ||
747 | /* The "last use" doesn't follow the "first use"?? */ | |
748 | abort (); | |
749 | } | |
750 | \f | |
751 | /* Skip COUNT insns from INSN, counting library calls as 1 insn. */ | |
752 | ||
753 | static rtx | |
754 | skip_consec_insns (insn, count) | |
755 | rtx insn; | |
756 | int count; | |
757 | { | |
758 | for (; count > 0; count--) | |
759 | { | |
760 | if (GET_CODE (insn) == NOTE) | |
761 | insn = NEXT_INSN (insn); | |
762 | else if (GET_CODE (insn) == BARRIER || GET_CODE (insn) == CODE_LABEL) | |
763 | abort (); | |
764 | else | |
765 | { | |
766 | rtx i1, temp; | |
767 | ||
768 | /* If first insn of gnulib call sequence, skip to end. */ | |
769 | /* Do this at start of loop, since INSN is guaranteed to | |
770 | be an insn here. */ | |
771 | if (temp = find_reg_note (insn, REG_LIBCALL, 0)) | |
772 | insn = XEXP (temp, 0); | |
773 | ||
774 | do insn = NEXT_INSN (insn); | |
775 | while (GET_CODE (insn) == NOTE); | |
776 | } | |
777 | } | |
778 | ||
779 | return insn; | |
780 | } | |
781 | ||
782 | /* Find a REG_EQUAL note in INSN but only if it is safe to use for our | |
783 | purposes. Those put in by CSE are not safe since they may fail to | |
784 | use the registers that appear in the actual insn source. */ | |
785 | ||
786 | static rtx | |
787 | loop_find_reg_equal (insn) | |
788 | rtx insn; | |
789 | { | |
790 | return (find_reg_note (insn, REG_RETVAL, 0) | |
791 | ? find_reg_note (insn, REG_EQUAL, 0) | |
792 | : 0); | |
793 | } | |
794 | ||
795 | /* Ignore any movable whose insn falls within a libcall | |
796 | which is part of another movable. | |
797 | We make use of the fact that the movable for the libcall value | |
798 | was made later and so appears later on the chain. */ | |
799 | ||
800 | static void | |
801 | ignore_some_movables (movables) | |
802 | struct movable *movables; | |
803 | { | |
804 | register struct movable *m, *m1; | |
805 | ||
806 | for (m = movables; m; m = m->next) | |
807 | { | |
808 | /* Is this a movable for the value of a libcall? */ | |
809 | rtx note = find_reg_note (m->insn, REG_RETVAL, 0); | |
810 | if (note) | |
811 | { | |
812 | /* Find the beginning of that libcall. */ | |
813 | rtx first_insn = XEXP (note, 0); | |
814 | /* Check for earlier movables inside that range, | |
815 | and mark them invalid. */ | |
816 | for (m1 = movables; m1 != m; m1 = m1->next) | |
817 | if (INSN_LUID (m1->insn) >= INSN_LUID (first_insn) | |
818 | && INSN_LUID (m1->insn) < INSN_LUID (m->insn)) | |
819 | m1->done = 1; | |
820 | } | |
821 | } | |
822 | } | |
823 | ||
824 | /* For each movable insn, see if the reg that it loads | |
825 | leads when it dies right into another conditionally movable insn. | |
826 | If so, record that the second insn "forces" the first one, | |
827 | since the second can be moved only if the first is. */ | |
828 | ||
829 | static void | |
830 | force_movables (movables) | |
831 | struct movable *movables; | |
832 | { | |
833 | register struct movable *m, *m1; | |
834 | for (m1 = movables; m1; m1 = m1->next) | |
835 | /* Omit this if moving just the (SET (REG) 0) of a zero-extend. */ | |
836 | if (!m1->partial && !m1->done) | |
837 | { | |
838 | int regno = m1->regno; | |
839 | for (m = m1->next; m; m = m->next) | |
840 | /* ??? Could this be a bug? What if CSE caused the | |
841 | register of M1 to be used after this insn? | |
842 | Since CSE does not update regno_last_uid, | |
843 | this insn M->insn might not be where it dies. | |
844 | But very likely this doesn't matter; what matters is | |
845 | that M's reg is computed from M1's reg. */ | |
846 | if (INSN_UID (m->insn) == regno_last_uid[regno] | |
847 | && !m->done) | |
848 | break; | |
849 | if (m != 0 && m->set_src == SET_DEST (PATTERN (m1->insn))) | |
850 | m = 0; | |
851 | ||
852 | /* Increase the priority of the moving the first insn | |
853 | since it permits the second to be moved as well. */ | |
854 | if (m != 0) | |
855 | { | |
856 | m->forces = m1; | |
857 | m1->lifetime += m->lifetime; | |
858 | m1->savings += m1->savings; | |
859 | } | |
860 | } | |
861 | } | |
862 | \f | |
863 | /* Find invariant expressions that are equal and can be combined into | |
864 | one register. */ | |
865 | ||
866 | static void | |
867 | combine_movables (movables, nregs) | |
868 | struct movable *movables; | |
869 | int nregs; | |
870 | { | |
871 | register struct movable *m; | |
872 | char *matched_regs = (char *) alloca (nregs); | |
873 | enum machine_mode mode; | |
874 | ||
875 | /* Regs that are set more than once are not allowed to match | |
876 | or be matched. I'm no longer sure why not. */ | |
877 | /* Perhaps testing m->consec_sets would be more appropriate here? */ | |
878 | ||
879 | for (m = movables; m; m = m->next) | |
880 | if (m->match == 0 && n_times_used[m->regno] == 1 && !m->partial) | |
881 | { | |
882 | register struct movable *m1; | |
883 | int regno = m->regno; | |
884 | ||
885 | bzero (matched_regs, nregs); | |
886 | matched_regs[regno] = 1; | |
887 | ||
888 | for (m1 = m->next; m1; m1 = m1->next) | |
889 | if (m1->match == 0 && n_times_used[m1->regno] == 1 | |
890 | /* A reg used outside the loop mustn't be eliminated. */ | |
891 | && !m1->global | |
892 | /* A reg used for zero-extending mustn't be eliminated. */ | |
893 | && !m1->partial | |
894 | && (matched_regs[m1->regno] | |
895 | || | |
896 | ( | |
897 | /* Can't combine regs with different modes | |
898 | even if loaded from the same constant. */ | |
899 | (GET_MODE (SET_DEST (PATTERN (m->insn))) | |
900 | == GET_MODE (SET_DEST (PATTERN (m1->insn)))) | |
901 | /* See if the source of M1 says it matches M. */ | |
902 | && ((GET_CODE (m1->set_src) == REG | |
903 | && matched_regs[REGNO (m1->set_src)]) | |
904 | || rtx_equal_for_loop_p (m->set_src, m1->set_src, | |
905 | movables) | |
906 | || (REG_NOTES (m->insn) && REG_NOTES (m1->insn) | |
907 | && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV | |
908 | && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV | |
909 | && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0), | |
910 | XEXP (REG_NOTES (m1->insn), 0))))))) | |
911 | { | |
912 | m->lifetime += m1->lifetime; | |
913 | m->savings += m1->savings; | |
914 | m1->match = m; | |
915 | matched_regs[m1->regno] = 1; | |
916 | } | |
917 | } | |
918 | ||
919 | /* Now combine the regs used for zero-extension. | |
920 | This can be done for those not marked `global' | |
921 | provided their lives don't overlap. */ | |
922 | ||
923 | for (mode = VOIDmode; (int) mode < (int) MAX_MACHINE_MODE; | |
924 | mode = (enum machine_mode) ((int) mode + 1)) | |
925 | if (GET_MODE_CLASS (mode) == MODE_INT) | |
926 | { | |
927 | register struct movable *m0 = 0; | |
928 | ||
929 | /* Combine all the registers for extension from mode MODE. | |
930 | Don't combine any that are used outside this loop. */ | |
931 | for (m = movables; m; m = m->next) | |
932 | if (m->partial && ! m->global | |
933 | && mode == GET_MODE (SET_SRC (PATTERN (NEXT_INSN (m->insn))))) | |
934 | { | |
935 | register struct movable *m1; | |
936 | int first = uid_luid[regno_first_uid[m->regno]]; | |
937 | int last = uid_luid[regno_last_uid[m->regno]]; | |
938 | ||
939 | if (m0 == 0) | |
940 | { | |
941 | /* First one: don't check for overlap, just record it. */ | |
942 | m0 = m; | |
943 | continue; | |
944 | } | |
945 | ||
946 | /* Make sure they extend to the same mode. | |
947 | (Almost always true.) */ | |
948 | if (GET_MODE (SET_DEST (PATTERN (m->insn))) | |
949 | != GET_MODE (SET_DEST (PATTERN (m0->insn)))) | |
950 | continue; | |
951 | ||
952 | /* We already have one: check for overlap with those | |
953 | already combined together. */ | |
954 | for (m1 = movables; m1 != m; m1 = m1->next) | |
955 | if (m1 == m0 || (m1->partial && m1->match == m0)) | |
956 | if (! (uid_luid[regno_first_uid[m1->regno]] > last | |
957 | || uid_luid[regno_last_uid[m1->regno]] < first)) | |
958 | goto overlap; | |
959 | ||
960 | /* No overlap: we can combine this with the others. */ | |
961 | m0->lifetime += m->lifetime; | |
962 | m0->savings += m->savings; | |
963 | m->match = m0; | |
964 | ||
965 | overlap: ; | |
966 | } | |
967 | } | |
968 | } | |
969 | \f | |
970 | /* Return 1 if regs X and Y will become the same if moved. */ | |
971 | ||
972 | static int | |
973 | regs_match_p (x, y, movables) | |
974 | rtx x, y; | |
975 | struct movable *movables; | |
976 | { | |
977 | int xn = REGNO (x); | |
978 | int yn = REGNO (y); | |
979 | struct movable *mx, *my; | |
980 | ||
981 | for (mx = movables; mx; mx = mx->next) | |
982 | if (mx->regno == xn) | |
983 | break; | |
984 | ||
985 | for (my = movables; my; my = my->next) | |
986 | if (my->regno == yn) | |
987 | break; | |
988 | ||
989 | return (mx && my | |
990 | && ((mx->match == my->match && mx->match != 0) | |
991 | || mx->match == my | |
992 | || mx == my->match)); | |
993 | } | |
994 | ||
995 | /* Return 1 if X and Y are identical-looking rtx's. | |
996 | This is the Lisp function EQUAL for rtx arguments. */ | |
997 | ||
998 | static int | |
999 | rtx_equal_for_loop_p (x, y, movables) | |
1000 | rtx x, y; | |
1001 | struct movable *movables; | |
1002 | { | |
1003 | register int i; | |
1004 | register int j; | |
1005 | register enum rtx_code code; | |
1006 | register char *fmt; | |
1007 | ||
1008 | if (x == y) | |
1009 | return 1; | |
1010 | if (x == 0 || y == 0) | |
1011 | return 0; | |
1012 | ||
1013 | code = GET_CODE (x); | |
1014 | /* Rtx's of different codes cannot be equal. */ | |
1015 | if (code != GET_CODE (y)) | |
1016 | return 0; | |
1017 | ||
1018 | /* (MULT:SI x y) and (MULT:HI x y) are NOT equivalent. | |
1019 | (REG:SI x) and (REG:HI x) are NOT equivalent. */ | |
1020 | ||
1021 | if (GET_MODE (x) != GET_MODE (y)) | |
1022 | return 0; | |
1023 | ||
1024 | /* These three types of rtx's can be compared nonrecursively. */ | |
1025 | /* Until the end of reload, | |
1026 | don't consider the a reference to the return register of the current | |
1027 | function the same as the return from a called function. This eases | |
1028 | the job of function integration. Once the distinction no longer | |
1029 | matters, the insn will be deleted. */ | |
1030 | if (code == REG) | |
1031 | return ((REGNO (x) == REGNO (y) | |
1032 | && REG_FUNCTION_VALUE_P (x) == REG_FUNCTION_VALUE_P (y)) | |
1033 | || regs_match_p (x, y, movables)); | |
1034 | ||
1035 | if (code == LABEL_REF) | |
1036 | return XEXP (x, 0) == XEXP (y, 0); | |
1037 | if (code == SYMBOL_REF) | |
1038 | return XSTR (x, 0) == XSTR (y, 0); | |
1039 | ||
1040 | /* Compare the elements. If any pair of corresponding elements | |
1041 | fail to match, return 0 for the whole things. */ | |
1042 | ||
1043 | fmt = GET_RTX_FORMAT (code); | |
1044 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1045 | { | |
1046 | switch (fmt[i]) | |
1047 | { | |
1048 | case 'i': | |
1049 | if (XINT (x, i) != XINT (y, i)) | |
1050 | return 0; | |
1051 | break; | |
1052 | ||
1053 | case 'E': | |
1054 | /* Two vectors must have the same length. */ | |
1055 | if (XVECLEN (x, i) != XVECLEN (y, i)) | |
1056 | return 0; | |
1057 | ||
1058 | /* And the corresponding elements must match. */ | |
1059 | for (j = 0; j < XVECLEN (x, i); j++) | |
1060 | if (rtx_equal_for_loop_p (XVECEXP (x, i, j), XVECEXP (y, i, j), movables) == 0) | |
1061 | return 0; | |
1062 | break; | |
1063 | ||
1064 | case 'e': | |
1065 | if (rtx_equal_for_loop_p (XEXP (x, i), XEXP (y, i), movables) == 0) | |
1066 | return 0; | |
1067 | break; | |
1068 | ||
1069 | case 's': | |
1070 | if (strcmp (XSTR (x, i), XSTR (y, i))) | |
1071 | return 0; | |
1072 | break; | |
1073 | ||
1074 | case 'u': | |
1075 | /* These are just backpointers, so they don't matter. */ | |
1076 | break; | |
1077 | ||
1078 | case '0': | |
1079 | break; | |
1080 | ||
1081 | /* It is believed that rtx's at this level will never | |
1082 | contain anything but integers and other rtx's, | |
1083 | except for within LABEL_REFs and SYMBOL_REFs. */ | |
1084 | default: | |
1085 | abort (); | |
1086 | } | |
1087 | } | |
1088 | return 1; | |
1089 | } | |
1090 | \f | |
1091 | /* Scan MOVABLES, and move the insns that deserve to be moved. | |
1092 | If two matching movables are combined, replace one reg with the | |
1093 | other throughout. */ | |
1094 | ||
1095 | static void | |
1096 | move_movables (movables, threshold, insn_count, loop_start, end, nregs) | |
1097 | struct movable *movables; | |
1098 | int threshold; | |
1099 | int insn_count; | |
1100 | rtx loop_start; | |
1101 | rtx end; | |
1102 | int nregs; | |
1103 | { | |
1104 | rtx new_start = 0; | |
1105 | register struct movable *m; | |
1106 | register rtx p; | |
1107 | /* Map of pseudo-register replacements to handle combining | |
1108 | when we move several insns that load the same value | |
1109 | into different pseudo-registers. */ | |
1110 | rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx)); | |
1111 | char *already_moved = (char *) alloca (nregs); | |
1112 | ||
1113 | bzero (already_moved, nregs); | |
1114 | bzero (reg_map, nregs * sizeof (rtx)); | |
1115 | ||
1116 | num_movables = 0; | |
1117 | ||
1118 | for (m = movables; m; m = m->next) | |
1119 | { | |
1120 | /* Describe this movable insn. */ | |
1121 | ||
1122 | if (loop_dump_stream) | |
1123 | { | |
1124 | fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ", | |
1125 | INSN_UID (m->insn), m->regno, m->lifetime); | |
1126 | if (m->consec > 0) | |
1127 | fprintf (loop_dump_stream, "consec %d, ", m->consec); | |
1128 | if (m->cond) | |
1129 | fprintf (loop_dump_stream, "cond "); | |
1130 | if (m->force) | |
1131 | fprintf (loop_dump_stream, "force "); | |
1132 | if (m->global) | |
1133 | fprintf (loop_dump_stream, "global "); | |
1134 | if (m->done) | |
1135 | fprintf (loop_dump_stream, "done "); | |
1136 | if (m->match) | |
1137 | fprintf (loop_dump_stream, "matches %d ", | |
1138 | INSN_UID (m->match->insn)); | |
1139 | if (m->forces) | |
1140 | fprintf (loop_dump_stream, "forces %d ", | |
1141 | INSN_UID (m->forces->insn)); | |
1142 | } | |
1143 | ||
1144 | /* Count movables. Value used in heuristics in strength_reduce. */ | |
1145 | num_movables++; | |
1146 | ||
1147 | /* Ignore the insn if it's already done (it matched something else). | |
1148 | Otherwise, see if it is now safe to move. */ | |
1149 | ||
1150 | if (!m->done | |
1151 | && (! m->cond | |
1152 | || (1 == invariant_p (m->set_src) | |
1153 | && (m->consec == 0 | |
1154 | || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)), | |
1155 | m->consec + 1, | |
1156 | m->insn)))) | |
1157 | && (! m->forces || m->forces->done)) | |
1158 | { | |
1159 | register int regno; | |
1160 | register rtx p; | |
1161 | int savings = m->savings; | |
1162 | ||
1163 | /* We have an insn that is safe to move. | |
1164 | Compute its desirability. */ | |
1165 | ||
1166 | p = m->insn; | |
1167 | regno = m->regno; | |
1168 | ||
1169 | if (loop_dump_stream) | |
1170 | fprintf (loop_dump_stream, "savings %d ", savings); | |
1171 | ||
1172 | if (moved_once[regno]) | |
1173 | { | |
1174 | insn_count *= 2; | |
1175 | ||
1176 | if (loop_dump_stream) | |
1177 | fprintf (loop_dump_stream, "halved since already moved "); | |
1178 | } | |
1179 | ||
1180 | /* An insn MUST be moved if we already moved something else | |
1181 | which is safe only if this one is moved too: that is, | |
1182 | if already_moved[REGNO] is nonzero. */ | |
1183 | ||
1184 | /* An insn is desirable to move if the new lifetime of the | |
1185 | register is no more than THRESHOLD times the old lifetime. | |
1186 | If it's not desirable, it means the loop is so big | |
1187 | that moving won't speed things up much, | |
1188 | and it is liable to make register usage worse. */ | |
1189 | ||
1190 | /* It is also desirable to move if it can be moved at no | |
1191 | extra cost because something else was already moved. */ | |
1192 | ||
1193 | if (already_moved[regno] | |
1194 | || (threshold * savings * m->lifetime) >= insn_count | |
1195 | || (m->forces && m->forces->done | |
1196 | && n_times_used[m->forces->regno] == 1)) | |
1197 | { | |
1198 | int count; | |
1199 | register struct movable *m1; | |
1200 | rtx first; | |
1201 | ||
1202 | /* Now move the insns that set the reg. */ | |
1203 | ||
1204 | for (count = m->consec; count >= 0; count--) | |
1205 | { | |
1206 | rtx i1, temp; | |
1207 | ||
1208 | /* If first insn of gnulib call sequence, skip to end. */ | |
1209 | /* Do this at start of loop, since p is guaranteed to | |
1210 | be an insn here. */ | |
1211 | if (temp = find_reg_note (p, REG_LIBCALL, 0)) | |
1212 | p = XEXP (temp, 0); | |
1213 | ||
1214 | /* If last insn of gnulib call sequence, move all | |
1215 | insns except the last before the loop. The last insn is | |
1216 | handled in the normal manner. */ | |
1217 | if (temp = find_reg_note (p, REG_RETVAL | |
1218 | , 0)) | |
1219 | { | |
1220 | rtx fn_address = 0; | |
1221 | rtx fn_reg = 0; | |
1222 | first = 0; | |
1223 | for (temp = XEXP (temp, 0); temp != p; | |
1224 | temp = NEXT_INSN (temp)) | |
1225 | { | |
1226 | rtx body = PATTERN (temp); | |
1227 | rtx n; | |
1228 | /* Extract the function address from the insn | |
1229 | that loads it into a register. | |
1230 | If this insn was cse'd, we get incorrect code. | |
1231 | So delete it and stick the fn address right | |
1232 | into the call insn. Since the moved insns | |
1233 | won't be cse'd, that does no harm. */ | |
1234 | if (GET_CODE (NEXT_INSN (temp)) == CALL_INSN | |
1235 | && GET_CODE (body) == SET | |
1236 | && GET_CODE (SET_DEST (body)) == REG | |
1237 | && (n = find_reg_note (temp, REG_EQUIV, 0))) | |
1238 | { | |
1239 | fn_reg = SET_SRC (body); | |
1240 | if (GET_CODE (fn_reg) != REG) | |
1241 | fn_reg = SET_DEST (body); | |
1242 | fn_address = XEXP (n, 0); | |
1243 | continue; | |
1244 | } | |
1245 | /* We have the call insn. | |
1246 | Substitute the fn address for the reg | |
1247 | that we believe this insn will use. */ | |
1248 | if (GET_CODE (temp) == CALL_INSN | |
1249 | && fn_address != 0) | |
1250 | replace_call_address (body, fn_reg, fn_address); | |
1251 | if (GET_CODE (temp) == CALL_INSN) | |
1252 | i1 = emit_call_insn_before (body, loop_start); | |
1253 | else | |
1254 | i1 = emit_insn_before (body, loop_start); | |
1255 | if (first == 0) | |
1256 | first = i1; | |
1257 | REG_NOTES (i1) = REG_NOTES (temp); | |
1258 | delete_insn (temp); | |
1259 | } | |
1260 | } | |
1261 | if (m->savemode != VOIDmode) | |
1262 | { | |
1263 | /* P sets REG to zero; but we should clear only the bits | |
1264 | that are not covered by the mode m->savemode. */ | |
1265 | rtx reg = SET_DEST (PATTERN (p)); | |
1266 | i1 = emit_insn_before | |
1267 | (gen_rtx (SET, VOIDmode, reg, | |
1268 | gen_rtx (AND, GET_MODE (reg), | |
1269 | reg, | |
1270 | gen_rtx (CONST_INT, VOIDmode, | |
1271 | (1 << GET_MODE_BITSIZE (m->savemode)) - 1))), | |
1272 | loop_start); | |
1273 | } | |
1274 | else if (GET_CODE (PATTERN (p)) == CALL_INSN) | |
1275 | i1 = emit_call_insn_before (PATTERN (p), loop_start); | |
1276 | else | |
1277 | i1 = emit_insn_before (PATTERN (p), loop_start); | |
1278 | ||
1279 | if (new_start == 0) | |
1280 | new_start = i1; | |
1281 | ||
1282 | if (loop_dump_stream) | |
1283 | fprintf (loop_dump_stream, " moved to %d", INSN_UID (i1)); | |
1284 | ||
1285 | /* Mark the moved, invariant reg as being equivalent to | |
1286 | its constant value. */ | |
1287 | REG_NOTES (i1) = REG_NOTES (p); | |
1288 | if (REG_NOTES (i1) == 0 | |
1289 | && ! m->partial /* But not if it's a zero-extend clr. */ | |
1290 | && ! m->global /* and not if used outside the loop | |
1291 | (since it might get set outside). */ | |
1292 | && CONSTANT_P (SET_SRC (PATTERN (p)))) | |
1293 | REG_NOTES (i1) | |
1294 | = gen_rtx (EXPR_LIST, REG_EQUIV, | |
1295 | SET_SRC (PATTERN (p)), REG_NOTES (i1)); | |
1296 | ||
1297 | /* If library call, now fix the REG_NOTES that contain | |
1298 | insn pointers, namely REG_LIBCALL on FIRST | |
1299 | and REG_RETVAL on I1. */ | |
1300 | if (temp = find_reg_note (i1, REG_RETVAL, 0)) | |
1301 | { | |
1302 | XEXP (temp, 0) = first; | |
1303 | temp = find_reg_note (first, REG_LIBCALL, 0); | |
1304 | XEXP (temp, 0) = i1; | |
1305 | } | |
1306 | ||
1307 | delete_insn (p); | |
1308 | do p = NEXT_INSN (p); | |
1309 | while (p != 0 && GET_CODE (p) == NOTE); | |
1310 | } | |
1311 | ||
1312 | /* The more regs we move, the less we like moving them. */ | |
1313 | threshold -= 3; | |
1314 | ||
1315 | /* Any other movable that loads the same register | |
1316 | MUST be moved. */ | |
1317 | already_moved[regno] = 1; | |
1318 | ||
1319 | /* This reg has been moved out of one loop. */ | |
1320 | moved_once[regno] = 1; | |
1321 | ||
1322 | /* The reg set here is now invariant. */ | |
1323 | if (! m->partial) | |
1324 | n_times_set[regno] = 0; | |
1325 | ||
1326 | m->done = 1; | |
1327 | ||
1328 | /* Change the length-of-life info for the register | |
1329 | to say it lives at least the full length of this loop. | |
1330 | This will help guide optimizations in outer loops. */ | |
1331 | ||
1332 | if (uid_luid[regno_first_uid[regno]] > INSN_LUID (loop_start)) | |
1333 | /* This is the old insn before all the moved insns. | |
1334 | We can't use the moved insn because it is out of range | |
1335 | in uid_luid. Only the old insns have luids. */ | |
1336 | regno_first_uid[regno] = INSN_UID (loop_start); | |
1337 | if (uid_luid[regno_last_uid[regno]] < INSN_LUID (end)) | |
1338 | regno_last_uid[regno] = INSN_UID (end); | |
1339 | ||
1340 | /* Combine with this moved insn any other matching movables. */ | |
1341 | ||
1342 | for (m1 = m->next; m1; m1 = m1->next) | |
1343 | if (m1->match == m) | |
1344 | { | |
1345 | rtx temp; | |
1346 | ||
1347 | /* Schedule the reg loaded by M1 | |
1348 | for replacement so that shares the reg of M. */ | |
1349 | reg_map[m1->regno] = SET_DEST (PATTERN (m->insn)); | |
1350 | /* Get rid of the matching insn | |
1351 | and prevent further processing of it. */ | |
1352 | m1->done = 1; | |
1353 | ||
1354 | /* if library call, delete all insn except last, which | |
1355 | is deleted below */ | |
1356 | if (temp = find_reg_note (m1->insn, REG_RETVAL, 0)) | |
1357 | { | |
1358 | for (temp = XEXP (temp, 0); temp != m1->insn; | |
1359 | temp = NEXT_INSN (temp)) | |
1360 | delete_insn (temp); | |
1361 | } | |
1362 | delete_insn (m1->insn); | |
1363 | ||
1364 | /* Any other movable that loads the same register | |
1365 | MUST be moved. */ | |
1366 | already_moved[m1->regno] = 1; | |
1367 | ||
1368 | /* The reg merged here is now invariant, | |
1369 | if the reg it matches is invariant. */ | |
1370 | if (! m->partial) | |
1371 | n_times_set[m1->regno] = 0; | |
1372 | } | |
1373 | } | |
1374 | else if (loop_dump_stream) | |
1375 | fprintf (loop_dump_stream, "not desirable"); | |
1376 | } | |
1377 | else if (loop_dump_stream && !m->match) | |
1378 | fprintf (loop_dump_stream, "not safe"); | |
1379 | ||
1380 | if (loop_dump_stream) | |
1381 | fprintf (loop_dump_stream, "\n"); | |
1382 | } | |
1383 | ||
1384 | if (new_start == 0) | |
1385 | new_start = loop_start; | |
1386 | ||
1387 | /* Go through all the instructions in the loop, making | |
1388 | all the register substitutions scheduled in REG_MAP. */ | |
1389 | for (p = new_start; p != end; p = NEXT_INSN (p)) | |
1390 | if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN | |
1391 | || GET_CODE (p) == CALL_INSN) | |
1392 | { | |
1393 | rtx tail; | |
1394 | ||
1395 | replace_regs (PATTERN (p), reg_map, nregs); | |
1396 | /* Subsitute registers in the equivalent expression also. */ | |
1397 | for (tail = REG_NOTES (p); tail; tail = XEXP (tail, 1)) | |
1398 | if (REG_NOTE_KIND (tail) == REG_EQUAL | |
1399 | || REG_NOTE_KIND (tail) == REG_EQUIV) | |
1400 | replace_regs (XEXP (tail, 0), reg_map, nregs); | |
1401 | } | |
1402 | } | |
1403 | \f | |
1404 | /* Optionally change a loop which enters just before the endtest | |
1405 | to one which falls straight in | |
1406 | after skipping around the entire loop if the endtest would drop out. | |
1407 | Returns 1 if the change was made, 0 if the loop was not really suitable. */ | |
1408 | ||
1409 | int | |
1410 | loop_skip_over (start, end, loop_entry_jump) | |
1411 | rtx start; | |
1412 | rtx end; | |
1413 | rtx loop_entry_jump; | |
1414 | { | |
1415 | rtx entry_insn; | |
1416 | rtx endtest; | |
1417 | rtx endtestjump; | |
1418 | register rtx p = JUMP_LABEL (loop_entry_jump); | |
1419 | ||
1420 | while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN | |
1421 | && GET_CODE (p) != CALL_INSN) | |
1422 | p = NEXT_INSN (p); | |
1423 | entry_insn = p; | |
1424 | ||
1425 | /* Skip any ordinary arithmetic insns to find the compare. */ | |
1426 | for (; p != 0; p = NEXT_INSN (p)) | |
1427 | if (GET_CODE (p) != NOTE) | |
1428 | if (GET_CODE (p) != INSN || sets_cc0_p (PATTERN (p))) | |
1429 | break; | |
1430 | if (p == 0 || GET_CODE (p) != INSN) | |
1431 | return 0; | |
1432 | endtest = p; | |
1433 | endtestjump = next_real_insn (p); | |
1434 | ||
1435 | /* Check that (1) we have reached a compare insn and (2) | |
1436 | the insn (presumably a jump) following that compare | |
1437 | is the last in the loop and jumps back to the loop beginning. */ | |
1438 | ||
1439 | if (sets_cc0_p (PATTERN (endtest)) > 0 | |
1440 | && endtestjump == prev_real_insn (end) | |
1441 | && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump) | |
1442 | { | |
1443 | rtx newlab; | |
1444 | /* This is the jump that we insert. */ | |
1445 | rtx new_jump; | |
1446 | ||
1447 | /* Duplicate the ordinary arith insns before the compare. */ | |
1448 | for (p = entry_insn; p != endtest; p = NEXT_INSN (p)) | |
1449 | if (GET_CODE (p) == INSN) | |
1450 | { | |
1451 | rtx new = emit_insn_before (copy_rtx (PATTERN (p)), start); | |
1452 | if (REG_NOTES (p)) | |
1453 | REG_NOTES (new) = copy_rtx (REG_NOTES (p)); | |
1454 | } | |
1455 | ||
1456 | /* Ok, duplicate that test before start of loop. */ | |
1457 | emit_insn_before (copy_rtx (PATTERN (endtest)), start); | |
1458 | /* Make a new entry-jump (before the original one) | |
1459 | whose condition is opposite to the loop-around endtest | |
1460 | and which jumps around the loop (to just after the ending NOTE). */ | |
1461 | newlab = gen_label_rtx (); | |
1462 | emit_label_after (newlab, end); | |
1463 | emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start); | |
1464 | new_jump = PREV_INSN (start); | |
1465 | JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump); | |
1466 | LABEL_NUSES (JUMP_LABEL (endtestjump))++; | |
1467 | invert_jump (new_jump, newlab); | |
1468 | /* Delete the original entry-jump. */ | |
1469 | delete_insn (loop_entry_jump); | |
1470 | ||
1471 | return 1; | |
1472 | } | |
1473 | ||
1474 | return 0; | |
1475 | } | |
1476 | \f | |
1477 | /* Throughout the rtx X, replace many registers according to REG_MAP. | |
1478 | Return the replacement for X (which may be X with altered contents). | |
1479 | REG_MAP[R] is the replacement for register R, or 0 for don't replace. | |
1480 | NREGS is the length of REG_MAP; regs >= NREGS are not mapped. */ | |
1481 | ||
1482 | static rtx | |
1483 | replace_regs (x, reg_map, nregs) | |
1484 | rtx x; | |
1485 | rtx *reg_map; | |
1486 | int nregs; | |
1487 | { | |
1488 | register enum rtx_code code; | |
1489 | register int i; | |
1490 | register char *fmt; | |
1491 | ||
1492 | if (x == 0) | |
1493 | return x; | |
1494 | ||
1495 | code = GET_CODE (x); | |
1496 | switch (code) | |
1497 | { | |
1498 | case PC: | |
1499 | case CC0: | |
1500 | case CONST_INT: | |
1501 | case CONST_DOUBLE: | |
1502 | case CONST: | |
1503 | case SYMBOL_REF: | |
1504 | case LABEL_REF: | |
1505 | return x; | |
1506 | ||
1507 | case REG: | |
1508 | /* Verify that the register has an entry before trying to access it. */ | |
1509 | if (REGNO (x) < nregs && reg_map[REGNO (x)] != 0) | |
1510 | return reg_map[REGNO (x)]; | |
1511 | return x; | |
1512 | } | |
1513 | ||
1514 | fmt = GET_RTX_FORMAT (code); | |
1515 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1516 | { | |
1517 | if (fmt[i] == 'e') | |
1518 | XEXP (x, i) = replace_regs (XEXP (x, i), reg_map, nregs); | |
1519 | if (fmt[i] == 'E') | |
1520 | { | |
1521 | register int j; | |
1522 | for (j = 0; j < XVECLEN (x, i); j++) | |
1523 | XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map, nregs); | |
1524 | } | |
1525 | } | |
1526 | return x; | |
1527 | } | |
1528 | \f | |
1529 | /* Scan X and replace the address of any MEM in it with ADDR. | |
1530 | REG is the address that MEM should have before the replacement. */ | |
1531 | ||
1532 | static void | |
1533 | replace_call_address (x, reg, addr) | |
1534 | rtx x, reg, addr; | |
1535 | { | |
1536 | register enum rtx_code code; | |
1537 | register int i; | |
1538 | register char *fmt; | |
1539 | ||
1540 | if (x == 0) | |
1541 | return; | |
1542 | code = GET_CODE (x); | |
1543 | switch (code) | |
1544 | { | |
1545 | case PC: | |
1546 | case CC0: | |
1547 | case CONST_INT: | |
1548 | case CONST_DOUBLE: | |
1549 | case CONST: | |
1550 | case SYMBOL_REF: | |
1551 | case LABEL_REF: | |
1552 | case REG: | |
1553 | return; | |
1554 | ||
1555 | case SET: | |
1556 | /* Short cut for very common case. */ | |
1557 | replace_call_address (XEXP (x, 1), reg, addr); | |
1558 | return; | |
1559 | ||
1560 | case CALL: | |
1561 | /* Short cut for very common case. */ | |
1562 | replace_call_address (XEXP (x, 0), reg, addr); | |
1563 | return; | |
1564 | ||
1565 | case MEM: | |
1566 | /* If this MEM uses a reg other than the one we expected, | |
1567 | something is wrong. */ | |
1568 | if (XEXP (x, 0) != reg) | |
1569 | abort (); | |
1570 | XEXP (x, 0) = addr; | |
1571 | return; | |
1572 | } | |
1573 | ||
1574 | fmt = GET_RTX_FORMAT (code); | |
1575 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1576 | { | |
1577 | if (fmt[i] == 'e') | |
1578 | replace_call_address (XEXP (x, i), reg, addr); | |
1579 | if (fmt[i] == 'E') | |
1580 | { | |
1581 | register int j; | |
1582 | for (j = 0; j < XVECLEN (x, i); j++) | |
1583 | replace_call_address (XVECEXP (x, i, j), reg, addr); | |
1584 | } | |
1585 | } | |
1586 | } | |
1587 | \f | |
1588 | /* Return the number of memory refs to addresses that vary | |
1589 | in the rtx X. */ | |
1590 | ||
1591 | static int | |
1592 | count_nonfixed_reads (x) | |
1593 | rtx x; | |
1594 | { | |
1595 | register enum rtx_code code; | |
1596 | register int i; | |
1597 | register char *fmt; | |
1598 | int value; | |
1599 | ||
1600 | if (x == 0) | |
1601 | return 0; | |
1602 | ||
1603 | code = GET_CODE (x); | |
1604 | switch (code) | |
1605 | { | |
1606 | case PC: | |
1607 | case CC0: | |
1608 | case CONST_INT: | |
1609 | case CONST_DOUBLE: | |
1610 | case CONST: | |
1611 | case SYMBOL_REF: | |
1612 | case LABEL_REF: | |
1613 | case REG: | |
1614 | return 0; | |
1615 | ||
1616 | case MEM: | |
1617 | return rtx_varies_p (XEXP (x, 0)) + count_nonfixed_reads (XEXP (x, 0)); | |
1618 | } | |
1619 | ||
1620 | value = 0; | |
1621 | fmt = GET_RTX_FORMAT (code); | |
1622 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1623 | { | |
1624 | if (fmt[i] == 'e') | |
1625 | value += count_nonfixed_reads (XEXP (x, i)); | |
1626 | if (fmt[i] == 'E') | |
1627 | { | |
1628 | register int j; | |
1629 | for (j = 0; j < XVECLEN (x, i); j++) | |
1630 | value += count_nonfixed_reads (XVECEXP (x, i, j)); | |
1631 | } | |
1632 | } | |
1633 | return value; | |
1634 | } | |
1635 | ||
1636 | \f | |
1637 | #if 0 | |
1638 | /* P is an instruction that sets a register to the result of a ZERO_EXTEND. | |
1639 | Replace it with an instruction to load just the low bytes | |
1640 | if the machine supports such an instruction, | |
1641 | and insert above LOOP_START an instruction to clear the register. */ | |
1642 | ||
1643 | static void | |
1644 | constant_high_bytes (p, loop_start) | |
1645 | rtx p, loop_start; | |
1646 | { | |
1647 | register rtx new; | |
1648 | register int insn_code_number; | |
1649 | ||
1650 | /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...))) | |
1651 | to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */ | |
1652 | ||
1653 | new = gen_rtx (SET, VOIDmode, | |
1654 | gen_rtx (STRICT_LOW_PART, VOIDmode, | |
1655 | gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)), | |
1656 | SET_DEST (PATTERN (p)), | |
1657 | 0)), | |
1658 | XEXP (SET_SRC (PATTERN (p)), 0)); | |
1659 | insn_code_number = recog (new, p); | |
1660 | ||
1661 | if (insn_code_number) | |
1662 | { | |
1663 | register int i; | |
1664 | ||
1665 | /* Clear destination register before the loop. */ | |
1666 | emit_insn_before (gen_rtx (SET, VOIDmode, | |
1667 | SET_DEST (PATTERN (p)), | |
1668 | const0_rtx), | |
1669 | loop_start); | |
1670 | ||
1671 | /* Inside the loop, just load the low part. */ | |
1672 | PATTERN (p) = new; | |
1673 | } | |
1674 | } | |
1675 | #endif | |
1676 | \f | |
1677 | /* Verify that the ostensible loop starting at START | |
1678 | really is a loop: nothing jumps into it from outside. | |
1679 | Return the marker for the end of the loop, or zero if not a real loop. | |
1680 | ||
1681 | Also set the variables `unknown_*_altered' and `loop_has_call', | |
1682 | and fill in the array `loop_store_addrs'. */ | |
1683 | ||
1684 | static rtx | |
1685 | verify_loop (f, start) | |
1686 | rtx f, start; | |
1687 | { | |
1688 | register int level = 1; | |
1689 | register rtx insn, end; | |
1690 | ||
1691 | /* First find the LOOP_END that matches. | |
1692 | Also check each insn for storing in memory and record where. */ | |
1693 | ||
1694 | unknown_address_altered = 0; | |
1695 | unknown_aggregate_altered = 0; | |
1696 | fixed_aggregate_altered = 0; | |
1697 | loop_has_call = 0; | |
1698 | loop_store_addrs_idx = 0; | |
1699 | ||
1700 | num_mem_sets = 0; | |
1701 | loops_enclosed = 1; | |
1702 | loop_continue = 0; | |
1703 | ||
1704 | for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn)) | |
1705 | { | |
1706 | if (insn == 0) | |
1707 | /* Parse errors can cause a loop-beg with no loop-end. */ | |
1708 | return 0; | |
1709 | if (GET_CODE (insn) == NOTE) | |
1710 | { | |
1711 | if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG) | |
1712 | { | |
1713 | ++level; | |
1714 | /* Count number of loops contained in this one. */ | |
1715 | loops_enclosed++; | |
1716 | } | |
1717 | else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END) | |
1718 | { | |
1719 | --level; | |
1720 | if (level == 0) | |
1721 | { | |
1722 | end = insn; | |
1723 | break; | |
1724 | } | |
1725 | } | |
1726 | else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_CONT) | |
1727 | { | |
1728 | if (level == 1) | |
1729 | loop_continue = insn; | |
1730 | } | |
1731 | ||
1732 | /* Don't optimize loops containing setjmps. | |
1733 | On some machines, longjmp does not restore the reg | |
1734 | values as of the time of the setjmp. */ | |
1735 | else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_SETJMP) | |
1736 | return 0; | |
1737 | } | |
1738 | else if (GET_CODE (insn) == CALL_INSN) | |
1739 | { | |
1740 | unknown_address_altered = 1; | |
1741 | loop_has_call = 1; | |
1742 | } | |
1743 | /* ??? | |
1744 | else if (! unknown_address_altered) */ | |
1745 | else | |
1746 | { | |
1747 | if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) | |
1748 | note_stores (PATTERN (insn), note_addr_stored); | |
1749 | } | |
1750 | } | |
1751 | ||
1752 | /* Now scan all jumps in the function and see if any of them can | |
1753 | reach a label within the range of the loop. */ | |
1754 | ||
1755 | for (insn = f; insn; insn = NEXT_INSN (insn)) | |
1756 | if (GET_CODE (insn) == JUMP_INSN | |
1757 | /* Don't get fooled by jumps inserted by loop-optimize. | |
1758 | They don't have valid LUIDs, and they never jump into loops. */ | |
1759 | && INSN_UID (insn) < max_uid | |
1760 | && (INSN_LUID (insn) < INSN_LUID (start) | |
1761 | || INSN_LUID (insn) > INSN_LUID (end)) | |
1762 | /* We have a jump that is outside the loop. | |
1763 | Does it jump into the loop? */ | |
1764 | && can_jump_into_range_p (PATTERN (insn), | |
1765 | INSN_LUID (start), INSN_LUID (end))) | |
1766 | return 0; | |
1767 | ||
1768 | #if 0 | |
1769 | /* Now scan all labels between them and check for any jumps from outside. | |
1770 | This uses the ref-chains set up by find_basic_blocks. | |
1771 | This code is not used because it's more convenient for other reasons | |
1772 | to do the loop optimization before find_basic_blocks. */ | |
1773 | ||
1774 | for (insn = start; insn != end; insn = NEXT_INSN (insn)) | |
1775 | if (GET_CODE (insn) == CODE_LABEL) | |
1776 | { | |
1777 | register rtx y; | |
1778 | for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y)) | |
1779 | if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start) | |
1780 | || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end)) | |
1781 | return 0; | |
1782 | } | |
1783 | #endif | |
1784 | ||
1785 | return end; | |
1786 | } | |
1787 | \f | |
1788 | /* Return 1 if somewhere in X is a LABEL_REF to a label | |
1789 | located between BEG and END. */ | |
1790 | ||
1791 | static int | |
1792 | can_jump_into_range_p (x, beg, end) | |
1793 | rtx x; | |
1794 | int beg, end; | |
1795 | { | |
1796 | register enum rtx_code code = GET_CODE (x); | |
1797 | register int i; | |
1798 | register char *fmt; | |
1799 | ||
1800 | if (code == LABEL_REF) | |
1801 | { | |
1802 | register int luid = INSN_LUID (XEXP (x, 0)); | |
1803 | return luid > beg && luid < end; | |
1804 | } | |
1805 | ||
1806 | fmt = GET_RTX_FORMAT (code); | |
1807 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1808 | { | |
1809 | if (fmt[i] == 'e') | |
1810 | { | |
1811 | if (can_jump_into_range_p (XEXP (x, i), beg, end)) | |
1812 | return 1; | |
1813 | } | |
1814 | else if (fmt[i] == 'E') | |
1815 | { | |
1816 | register int j; | |
1817 | for (j = 0; j < XVECLEN (x, i); j++) | |
1818 | if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end)) | |
1819 | return 1; | |
1820 | } | |
1821 | } | |
1822 | ||
1823 | return 0; | |
1824 | } | |
1825 | ||
1826 | /* Return nonzero if there is a label in the range from | |
1827 | insn INSN to the insn whose luid is END. */ | |
1828 | ||
1829 | static int | |
1830 | labels_in_range_p (insn, end) | |
1831 | rtx insn; | |
1832 | int end; | |
1833 | { | |
1834 | while (insn && INSN_LUID (insn) <= end) | |
1835 | { | |
1836 | if (GET_CODE (insn) == CODE_LABEL) | |
1837 | return 0; | |
1838 | insn = NEXT_INSN (insn); | |
1839 | } | |
1840 | ||
1841 | return 0; | |
1842 | } | |
1843 | ||
1844 | /* Record that a memory reference X is being set. */ | |
1845 | ||
1846 | static void | |
1847 | note_addr_stored (x) | |
1848 | rtx x; | |
1849 | { | |
1850 | if (x == 0 || GET_CODE (x) != MEM) | |
1851 | return; | |
1852 | ||
1853 | /* Count number of memory writes. | |
1854 | This affects heuristics in strength_reduce. */ | |
1855 | num_mem_sets++; | |
1856 | if (unknown_address_altered) | |
1857 | return; | |
1858 | ||
1859 | if (GET_MODE (x) == BLKmode) | |
1860 | unknown_address_altered = 1; | |
1861 | else if (rtx_addr_varies_p (x)) | |
1862 | { | |
1863 | if (GET_CODE (XEXP (x, 0)) == PLUS) | |
1864 | unknown_aggregate_altered = 1; | |
1865 | else | |
1866 | unknown_address_altered = 1; | |
1867 | } | |
1868 | else | |
1869 | { | |
1870 | register int i; | |
1871 | register rtx addr = XEXP (x, 0); | |
1872 | ||
1873 | if (MEM_IN_STRUCT_P (x)) | |
1874 | fixed_aggregate_altered = 1; | |
1875 | for (i = 0; i < loop_store_addrs_idx; i++) | |
1876 | if (rtx_equal_p (loop_store_addrs[i], addr)) | |
1877 | { | |
1878 | if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x))) | |
1879 | loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); | |
1880 | break; | |
1881 | } | |
1882 | if (i == NUM_STORES) | |
1883 | unknown_address_altered = 1; | |
1884 | else if (i == loop_store_addrs_idx) | |
1885 | { | |
1886 | loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x)); | |
1887 | loop_store_addrs[loop_store_addrs_idx++] = addr; | |
1888 | } | |
1889 | } | |
1890 | } | |
1891 | \f | |
1892 | /* Return nonzero if the rtx X is invariant over the current loop. | |
1893 | ||
1894 | The value is 2 if we refer to something only conditionally invariant. | |
1895 | ||
1896 | If `unknown_address_altered' is nonzero, no memory ref is invariant. | |
1897 | Otherwise if `unknown_aggregate_altered' is nonzero, | |
1898 | a memory ref is invariant if it is not part of an aggregate | |
1899 | and its address is fixed and not in `loop_store_addrs'. | |
1900 | Otherwise if `fixed_aggregate_altered' is nonzero, | |
1901 | a memory ref is invariant | |
1902 | if its address is fixed and not in `loop_store_addrs'. | |
1903 | Otherwise, a memory ref is invariant if its address is fixed and not in | |
1904 | `loop_store_addrs' or if it is not an aggregate. */ | |
1905 | ||
1906 | static int | |
1907 | invariant_p (x) | |
1908 | register rtx x; | |
1909 | { | |
1910 | register int i; | |
1911 | register enum rtx_code code; | |
1912 | register char *fmt; | |
1913 | int conditional = 0; | |
1914 | ||
1915 | if (x == 0) | |
1916 | return 1; | |
1917 | code = GET_CODE (x); | |
1918 | switch (code) | |
1919 | { | |
1920 | case CONST_INT: | |
1921 | case CONST_DOUBLE: | |
1922 | case SYMBOL_REF: | |
1923 | case LABEL_REF: | |
1924 | case CONST: | |
1925 | return 1; | |
1926 | ||
1927 | case PC: | |
1928 | case CC0: | |
1929 | return 0; | |
1930 | ||
1931 | case REG: | |
1932 | /* We used to check RTX_UNCHANGING_P (x) here, but that is invalid | |
1933 | since the reg might be set by initialization within the loop. */ | |
1934 | if (x == frame_pointer_rtx || x == arg_pointer_rtx) | |
1935 | return 1; | |
1936 | if (n_times_set[REGNO (x)] == -1) | |
1937 | return 2; | |
1938 | return n_times_set[REGNO (x)] == 0; | |
1939 | ||
1940 | case MEM: | |
1941 | /* Constants in the constant pool are invariant. | |
1942 | ?? Really we should detect any constant address in the | |
1943 | text section. */ | |
1944 | if (GET_CODE (XEXP (x, 0)) == SYMBOL_REF | |
1945 | && CONSTANT_POOL_ADDRESS_P (XEXP (x, 0))) | |
1946 | return 1; | |
1947 | /* A store in a varying-address scalar (or a subroutine call) | |
1948 | could clobber anything in memory. */ | |
1949 | if (unknown_address_altered) | |
1950 | return 0; | |
1951 | /* Don't mess with volatile memory references. */ | |
1952 | if (MEM_VOLATILE_P (x)) | |
1953 | return 0; | |
1954 | #if 0 | |
1955 | /* If it's declared read-only, it is invariant | |
1956 | if its address is invariant. */ | |
1957 | if (RTX_UNCHANGING_P (x)) | |
1958 | return invariant_p (XEXP (x, 0)); | |
1959 | #endif | |
1960 | /* A store in a varying-address aggregate component | |
1961 | could clobber anything except a scalar with a fixed address. */ | |
1962 | if (unknown_aggregate_altered | |
1963 | && ((MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) | |
1964 | || rtx_addr_varies_p (x))) | |
1965 | return 0; | |
1966 | /* A store in a fixed-address aggregate component | |
1967 | could clobber anything whose address is not fixed, | |
1968 | even an aggregate component. */ | |
1969 | if (fixed_aggregate_altered | |
1970 | && rtx_addr_varies_p (x)) | |
1971 | return 0; | |
1972 | /* Any store could clobber a varying-address scalar. */ | |
1973 | if (loop_store_addrs_idx | |
1974 | && !(MEM_IN_STRUCT_P (x) || GET_CODE (XEXP (x, 0)) == PLUS) | |
1975 | && rtx_addr_varies_p (x)) | |
1976 | return 0; | |
1977 | /* A store in a fixed address clobbers overlapping references. */ | |
1978 | for (i = loop_store_addrs_idx - 1; i >= 0; i--) | |
1979 | if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i])) | |
1980 | return 0; | |
1981 | /* It's not invalidated by a store in memory | |
1982 | but we must still verify the address is invariant. */ | |
1983 | break; | |
1984 | ||
1985 | case ASM_OPERANDS: | |
1986 | /* Don't mess with insns declared volatile. */ | |
1987 | if (MEM_VOLATILE_P (x)) | |
1988 | return 0; | |
1989 | } | |
1990 | ||
1991 | fmt = GET_RTX_FORMAT (code); | |
1992 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
1993 | { | |
1994 | if (fmt[i] == 'e') | |
1995 | { | |
1996 | int tem = invariant_p (XEXP (x, i)); | |
1997 | if (tem == 0) | |
1998 | return 0; | |
1999 | if (tem == 2) | |
2000 | conditional = 1; | |
2001 | } | |
2002 | else if (fmt[i] == 'E') | |
2003 | { | |
2004 | register int j; | |
2005 | for (j = 0; j < XVECLEN (x, i); j++) | |
2006 | { | |
2007 | int tem = invariant_p (XVECEXP (x, i, j)); | |
2008 | if (tem == 0) | |
2009 | return 0; | |
2010 | if (tem == 2) | |
2011 | conditional = 1; | |
2012 | } | |
2013 | ||
2014 | } | |
2015 | } | |
2016 | ||
2017 | return 1 + conditional; | |
2018 | } | |
2019 | ||
2020 | /* Return 1 if OTHER (a mem ref) overlaps the area of memory | |
2021 | which is SIZE bytes starting at BASE. */ | |
2022 | ||
2023 | int | |
2024 | addr_overlap_p (other, base, size) | |
2025 | rtx other; | |
2026 | rtx base; | |
2027 | int size; | |
2028 | { | |
2029 | int start = 0, end; | |
2030 | ||
2031 | if (GET_CODE (base) == CONST) | |
2032 | base = XEXP (base, 0); | |
2033 | if (GET_CODE (base) == PLUS | |
2034 | && GET_CODE (XEXP (base, 1)) == CONST_INT) | |
2035 | { | |
2036 | start = INTVAL (XEXP (base, 1)); | |
2037 | base = XEXP (base, 0); | |
2038 | } | |
2039 | ||
2040 | end = start + size; | |
2041 | return refers_to_mem_p (other, base, start, end); | |
2042 | } | |
2043 | \f | |
2044 | /* Return nonzero if all the insns in the loop that set REG | |
2045 | are INSN and the immediately following insns, | |
2046 | and if each of those insns sets REG in an invariant way | |
2047 | (not counting uses of REG in them). | |
2048 | ||
2049 | The value is 2 if some of these insns are only conditionally invariant. | |
2050 | ||
2051 | We assume that INSN itself is the first set of REG | |
2052 | and that its source is invariant. */ | |
2053 | ||
2054 | static int | |
2055 | consec_sets_invariant_p (reg, n_sets, insn) | |
2056 | int n_sets; | |
2057 | rtx reg, insn; | |
2058 | { | |
2059 | register rtx p = insn; | |
2060 | register int regno = REGNO (reg); | |
2061 | rtx temp; | |
2062 | /* Number of sets we have to insist on finding after INSN. */ | |
2063 | int count = n_sets - 1; | |
2064 | int old = n_times_set[regno]; | |
2065 | int value = 0; | |
2066 | int this; | |
2067 | ||
2068 | /* If N_SETS hit the limit, we can't rely on its value. */ | |
2069 | if (n_sets == 127) | |
2070 | return 0; | |
2071 | ||
2072 | n_times_set[regno] = 0; | |
2073 | ||
2074 | while (count > 0) | |
2075 | { | |
2076 | register enum rtx_code code; | |
2077 | p = NEXT_INSN (p); | |
2078 | code = GET_CODE (p); | |
2079 | ||
2080 | /* If library call, skip to end of of it. */ | |
2081 | if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) | |
2082 | p = XEXP (temp, 0); | |
2083 | ||
2084 | this = 0; | |
2085 | if (code == INSN && GET_CODE (PATTERN (p)) == SET | |
2086 | && GET_CODE (SET_DEST (PATTERN (p))) == REG | |
2087 | && REGNO (SET_DEST (PATTERN (p))) == regno) | |
2088 | { | |
2089 | this = invariant_p (SET_SRC (PATTERN (p))); | |
2090 | if (this != 0) | |
2091 | value |= this; | |
2092 | else if (temp = loop_find_reg_equal (p)) | |
2093 | { | |
2094 | this = invariant_p (XEXP (temp, 0)); | |
2095 | if (this != 0) | |
2096 | value |= this; | |
2097 | } | |
2098 | } | |
2099 | if (this != 0) | |
2100 | count--; | |
2101 | else if (code != NOTE) | |
2102 | { | |
2103 | n_times_set[regno] = old; | |
2104 | return 0; | |
2105 | } | |
2106 | } | |
2107 | ||
2108 | n_times_set[regno] = old; | |
2109 | /* If invariant_p ever returned 2, we return 2. */ | |
2110 | return 1 + (value & 2); | |
2111 | } | |
2112 | ||
2113 | #if 0 | |
2114 | /* I don't think this condition is sufficient to allow INSN | |
2115 | to be moved, so we no longer test it. */ | |
2116 | ||
2117 | /* Return 1 if all insns in the basic block of INSN and following INSN | |
2118 | that set REG are invariant according to TABLE. */ | |
2119 | ||
2120 | static int | |
2121 | all_sets_invariant_p (reg, insn, table) | |
2122 | rtx reg, insn; | |
2123 | short *table; | |
2124 | { | |
2125 | register rtx p = insn; | |
2126 | register int regno = REGNO (reg); | |
2127 | ||
2128 | while (1) | |
2129 | { | |
2130 | register enum rtx_code code; | |
2131 | p = NEXT_INSN (p); | |
2132 | code = GET_CODE (p); | |
2133 | if (code == CODE_LABEL || code == JUMP_INSN) | |
2134 | return 1; | |
2135 | if (code == INSN && GET_CODE (PATTERN (p)) == SET | |
2136 | && GET_CODE (SET_DEST (PATTERN (p))) == REG | |
2137 | && REGNO (SET_DEST (PATTERN (p))) == regno) | |
2138 | { | |
2139 | if (!invariant_p (SET_SRC (PATTERN (p)), table)) | |
2140 | return 0; | |
2141 | } | |
2142 | } | |
2143 | } | |
2144 | #endif /* 0 */ | |
2145 | \f | |
2146 | /* Increment N_TIMES_SET at the index of each register | |
2147 | that is modified by an insn between FROM and TO. | |
2148 | If the value of an element of N_TIMES_SET becomes 127 or more, | |
2149 | stop incrementing it, to avoid overflow. | |
2150 | ||
2151 | Store in *COUNT_PTR the number of actual instruction | |
2152 | in the loop. We use this to decide what is worth moving out. */ | |
2153 | ||
2154 | /* last_set[n] is nonzero iff reg n has been set in the current basic block. | |
2155 | In that case, it is the insn that last set reg n. */ | |
2156 | ||
2157 | static void | |
2158 | count_loop_regs_set (from, to, may_not_move, count_ptr, nregs) | |
2159 | register rtx from, to; | |
2160 | char *may_not_move; | |
2161 | int *count_ptr; | |
2162 | int nregs; | |
2163 | { | |
2164 | register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx)); | |
2165 | register rtx insn; | |
2166 | register int count = 0; | |
2167 | register rtx dest; | |
2168 | ||
2169 | bzero (last_set, nregs * sizeof (rtx)); | |
2170 | for (insn = from; insn != to; insn = NEXT_INSN (insn)) | |
2171 | { | |
2172 | if (GET_CODE (insn) == CALL_INSN) | |
2173 | { | |
2174 | /* If a register is used as a subroutine address, | |
2175 | don't allow this register's setting to be moved out of the loop. | |
2176 | This condition is not at all logically correct | |
2177 | but it averts a very common lossage pattern | |
2178 | and creates lossage much less often. */ | |
2179 | if (GET_CODE (PATTERN (insn)) == CALL | |
2180 | && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM | |
2181 | && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG) | |
2182 | { | |
2183 | register int regno | |
2184 | = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0)); | |
2185 | may_not_move[regno] = 1; | |
2186 | } | |
2187 | else if (GET_CODE (PATTERN (insn)) == SET | |
2188 | && GET_CODE (SET_SRC (PATTERN (insn))) == CALL | |
2189 | && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM | |
2190 | && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG) | |
2191 | { | |
2192 | register int regno | |
2193 | = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)); | |
2194 | may_not_move[regno] = 1; | |
2195 | /* The call insn itself sets a reg, which cannot be moved. */ | |
2196 | may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1; | |
2197 | if (n_times_set[REGNO (SET_DEST (PATTERN (insn)))] < 127) | |
2198 | n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++; | |
2199 | } | |
2200 | } | |
2201 | if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) | |
2202 | { | |
2203 | ++count; | |
2204 | if (GET_CODE (PATTERN (insn)) == CLOBBER | |
2205 | && GET_CODE (XEXP (PATTERN (insn), 0)) == REG) | |
2206 | /* Don't move a reg that has an explicit clobber. | |
2207 | We might do so sometimes, but it's not worth the pain. */ | |
2208 | may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1; | |
2209 | else if (GET_CODE (PATTERN (insn)) == SET) | |
2210 | { | |
2211 | dest = SET_DEST (PATTERN (insn)); | |
2212 | while (GET_CODE (dest) == SUBREG | |
2213 | || GET_CODE (dest) == ZERO_EXTRACT | |
2214 | || GET_CODE (dest) == SIGN_EXTRACT | |
2215 | || GET_CODE (dest) == STRICT_LOW_PART) | |
2216 | dest = XEXP (dest, 0); | |
2217 | if (GET_CODE (dest) == REG) | |
2218 | { | |
2219 | register int regno = REGNO (dest); | |
2220 | /* If this is the first setting of this reg | |
2221 | in current basic block, and it was set before, | |
2222 | it must be set in two basic blocks, so it cannot | |
2223 | be moved out of the loop. */ | |
2224 | if (n_times_set[regno] > 0 && last_set[regno] == 0) | |
2225 | may_not_move[regno] = 1; | |
2226 | /* If this is not first setting in current basic block, | |
2227 | see if reg was used in between previous one and this. | |
2228 | If so, neither one can be moved. */ | |
2229 | if (last_set[regno] != 0 | |
2230 | && reg_used_between_p (dest, last_set[regno], insn)) | |
2231 | may_not_move[regno] = 1; | |
2232 | if (n_times_set[regno] < 127) | |
2233 | ++n_times_set[regno]; | |
2234 | last_set[regno] = insn; | |
2235 | } | |
2236 | } | |
2237 | else if (GET_CODE (PATTERN (insn)) == PARALLEL) | |
2238 | { | |
2239 | register int i; | |
2240 | for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--) | |
2241 | { | |
2242 | register rtx x = XVECEXP (PATTERN (insn), 0, i); | |
2243 | if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG) | |
2244 | /* Don't move a reg that has an explicit clobber. | |
2245 | It's not worth the pain to try to do it correctly. */ | |
2246 | may_not_move[REGNO (XEXP (x, 0))] = 1; | |
2247 | if (GET_CODE (x) == SET) | |
2248 | { | |
2249 | dest = SET_DEST (x); | |
2250 | while (GET_CODE (dest) == SUBREG | |
2251 | || GET_CODE (dest) == ZERO_EXTRACT | |
2252 | || GET_CODE (dest) == SIGN_EXTRACT | |
2253 | || GET_CODE (dest) == STRICT_LOW_PART) | |
2254 | dest = XEXP (dest, 0); | |
2255 | if (GET_CODE (dest) == REG) | |
2256 | { | |
2257 | register int regno = REGNO (dest); | |
2258 | if (n_times_set[regno] < 127) | |
2259 | ++n_times_set[regno]; | |
2260 | may_not_move[regno] = 1; | |
2261 | last_set[regno] = insn; | |
2262 | } | |
2263 | } | |
2264 | } | |
2265 | } | |
2266 | } | |
2267 | if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN) | |
2268 | bzero (last_set, nregs * sizeof (rtx)); | |
2269 | } | |
2270 | *count_ptr = count; | |
2271 | } | |
2272 | \f | |
2273 | /* Given a loop that is bounded by LOOP_START and LOOP_END | |
2274 | and that is entered at SCAN_START, | |
2275 | return 1 if the register set by insn INSN is used by | |
2276 | any insn that precedes INSN in cyclic order starting | |
2277 | from the loop entry point. */ | |
2278 | ||
2279 | static int | |
2280 | loop_reg_used_before_p (insn, loop_start, scan_start, loop_end) | |
2281 | rtx insn, loop_start, scan_start, loop_end; | |
2282 | { | |
2283 | rtx reg = SET_DEST (PATTERN (insn)); | |
2284 | if (INSN_LUID (scan_start) > INSN_LUID (insn)) | |
2285 | return (reg_used_between_p (reg, scan_start, loop_end) | |
2286 | || reg_used_between_p (reg, loop_start, insn)); | |
2287 | else | |
2288 | return reg_used_between_p (reg, scan_start, insn); | |
2289 | } | |
2290 | \f | |
2291 | /* A "basic induction variable" or biv is a pseudo reg that is set | |
2292 | (within this loop) only by incrementing or decrementing it. */ | |
2293 | /* A "general induction variable" or giv is a pseudo reg whose | |
2294 | value is a linear function of a biv. */ | |
2295 | ||
2296 | /* Bivs are recognized by `basic_induction_var'; | |
2297 | Givs by `general_induct_var'. */ | |
2298 | ||
2299 | /* An enum for the two different types of givs, those that are used | |
2300 | as memory addresses and those that are calculated into registers. */ | |
2301 | enum g_types { DEST_ADDR, DEST_REG }; | |
2302 | ||
2303 | /* A `struct induction' is created for every instruction that sets | |
2304 | an induction variable (either a biv or a giv). */ | |
2305 | ||
2306 | struct induction | |
2307 | { | |
2308 | rtx insn; /* The insn that sets a biv or giv */ | |
2309 | rtx new_reg; /* New register, containing strength reduced | |
2310 | version of this giv. */ | |
2311 | int src_regno; /* Biv from which this giv is computed. | |
2312 | (If this is a biv, then this is the biv.) */ | |
2313 | enum g_types giv_type; /* Indicate whether DEST_ADDR or DEST_REG giv */ | |
2314 | int dest_regno; /* Destination register for insn: this is the | |
2315 | register which was the biv or giv. | |
2316 | For a biv, this equals src_reg. | |
2317 | For a DEST_ADDR type giv, this is 0. */ | |
2318 | rtx *location; /* Place in the insn where this giv occurs. | |
2319 | If GIV_TYPE is DEST_REG, this is 0. */ | |
2320 | enum machine_mode mode; /* The mode of this biv or giv */ | |
2321 | rtx mult_val; /* Multiplicative factor for src_reg. */ | |
2322 | rtx add_val; /* Additive constant for that product. */ | |
2323 | int benefit; /* Gain from eliminating this insn. */ | |
2324 | int consec; /* The number of consecutive insn that set this | |
2325 | register; they are all eliminated if this | |
2326 | one is. */ | |
2327 | char replaceable; /* 1 if we can substitute the strength-reduced | |
2328 | variable for the original variable. | |
2329 | 0 means they must be kept separate and the | |
2330 | new one must be copied into the old pseudo | |
2331 | reg each time the old one is set. */ | |
2332 | char ignore; /* 1 prohibits further processing of this giv */ | |
2333 | int lifetime; /* Length of life of this giv */ | |
2334 | int times_used; /* # times this giv is used. */ | |
2335 | struct induction *family; /* Links together all induction variables that | |
2336 | have the same src register. */ | |
2337 | struct induction *forces; /* Points to an induction variable insn which | |
2338 | is used only once, to compute this giv, | |
2339 | and hence can be deleted if this insn is | |
2340 | strength reduced. */ | |
2341 | struct induction *forces2; /* Likewise. */ | |
2342 | struct induction *same; /* Links together all induction variables that | |
2343 | have the same tuple (src, mult, add). */ | |
2344 | }; | |
2345 | ||
2346 | /* A `struct iv_class' is created for each biv. */ | |
2347 | ||
2348 | struct iv_class { | |
2349 | int regno; /* Pseudo reg which is the biv. */ | |
2350 | int biv_count; /* Number of insns setting this reg. */ | |
2351 | struct induction *biv; /* List of all insns that set this reg. */ | |
2352 | int giv_count; /* Number of DEST_REG givs computed from this | |
2353 | biv. The resulting count is only used in | |
2354 | check_dbra_loop. */ | |
2355 | struct induction *giv; /* List of all insns that compute a giv | |
2356 | from this reg. */ | |
2357 | int total_benefit; /* Sum of BENEFITs of all those givs */ | |
2358 | rtx initial_value; /* Value of reg at loop start */ | |
2359 | struct iv_class *next; /* Links all class structures together */ | |
2360 | rtx init_insn; /* insn which intializes biv, 0 if none seen. */ | |
2361 | char eliminable; /* 1 if plausible candidate for elimination. */ | |
2362 | char nonneg; /* 1 if we added a REG_NONNEG note for this. */ | |
2363 | }; | |
2364 | ||
2365 | /* Definitions used by the basic induction variable discovery code. */ | |
2366 | enum iv_mode { UNKNOWN_INDUCT, BASIC_INDUCT, NOT_BASIC_INDUCT, | |
2367 | GENERAL_INDUCT }; | |
2368 | ||
2369 | /* Relative gain of eliminating various kinds of operations. */ | |
2370 | #define NO_BENEFIT 0 | |
2371 | #define ADD_BENEFIT 1 | |
2372 | #define SHIFT_BENEFIT 2 | |
2373 | #define MULT_BENEFIT 4 | |
2374 | #define LIBCALL_BENEFIT 15 | |
2375 | /* Benefit penalty, if a giv is not replaceable, i.e. must emit an insn to | |
2376 | copy the value of the strength reduced giv to its original register. */ | |
2377 | #define COPY_PENALTY 2 | |
2378 | ||
2379 | /* Indexed by register number, indicates whether or not register is an | |
2380 | induction variable, and if so what type. */ | |
2381 | ||
2382 | static enum iv_mode *induct_var; | |
2383 | ||
2384 | /* Indexed by register number, contains pointer to `struct induction' | |
2385 | if register is a general induction variable. */ | |
2386 | ||
2387 | static struct induction **induct_struct; | |
2388 | ||
2389 | /* Indexed by register number, contains pointer to `struct iv_class' | |
2390 | if register is a basic induction variable. */ | |
2391 | ||
2392 | static struct iv_class **class_struct; | |
2393 | ||
2394 | /*********************************/ | |
2395 | ||
2396 | /* ??? Unfinished optimizations, wilson@ji.Berkeley.EDU */ | |
2397 | ||
2398 | /* strength reduce addresses found in sources (set () (mem ())*/ | |
2399 | ||
2400 | /* There is one more optimization you might be interested in doing: to | |
2401 | allocate pseudo registers for frequently-accessed memory locations. | |
2402 | If the same memory location is referenced each time around, it might | |
2403 | be possible to copy it into a register before and out after. | |
2404 | This is especially useful when the memory location is a variable which | |
2405 | is in a stack slot because somewhere its address is taken. If the | |
2406 | loop doesn't contain a function call and the variable isn't volatile, | |
2407 | it is safe to keep the value in a register for the duration of the | |
2408 | loop. One tricky thing is that the copying of the value back from the | |
2409 | register has to be done on all exits from the loop. You need to check that | |
2410 | all the exits from the loop go to the same place. */ | |
2411 | ||
2412 | /* WARNING: the interaction of biv elimination, and recognizing 'constant' | |
2413 | bivs may cause problems */ | |
2414 | ||
2415 | /* add heuristic so that DEST_ADDR strength reduction does not cause | |
2416 | performance problems */ | |
2417 | ||
2418 | /* don't eliminate things that can be combined with an addressing mode? | |
2419 | find all giv that have same biv and mult_val (now must also have | |
2420 | same add_val), then for each giv, check to see if its only use | |
2421 | dies in a following memory address, generate a new memory address | |
2422 | and check to see if valid, if valid then store modified mem addr, | |
2423 | else if not valid addr mark giv as not done so that it will get its | |
2424 | own iv */ | |
2425 | ||
2426 | /* consec_sets_giv does not calculate replaceable and forces correctly, | |
2427 | forces should be a more general linked list instead of two entries */ | |
2428 | ||
2429 | /* try to optimize branches when it is known that a biv is always positive */ | |
2430 | ||
2431 | /* when replace biv in compare insn, should replace with closest giv so that | |
2432 | an optimized branch can still be recognized by combiner, i.e. VAXen acb */ | |
2433 | ||
2434 | /* should merge final_value calculation in check_dbra_loop with the | |
2435 | new final_biv_value function */ | |
2436 | ||
2437 | /* many of the checks involving uid_luid could be simplified if regscan | |
2438 | was rerun in loop_optimize() whenever a register was added or moved, | |
2439 | also some of the optimizations could be a little less conservative */ | |
2440 | \f | |
2441 | /* Perform strength reduction and induction variable elimination. */ | |
2442 | ||
2443 | /* Pseudo registers created during this function will be beyond the last | |
2444 | valid index in several tables including n_times_set and regno_last_uid. | |
2445 | This does not cause a problem here, because the added registers cannot be | |
2446 | givs outside of their loop, and hence will never be reconsidered. | |
2447 | But scan_loop must check regnos to make sure they are in bounds. */ | |
2448 | ||
2449 | static void | |
2450 | strength_reduce (scan_start, end, loop_top, insn_count, | |
2451 | loop_start, loop_end, nregs) | |
2452 | rtx scan_start; | |
2453 | rtx end; | |
2454 | rtx loop_top; | |
2455 | int insn_count; | |
2456 | rtx loop_start; | |
2457 | rtx loop_end; | |
2458 | int nregs; | |
2459 | { | |
2460 | rtx p; | |
2461 | rtx inc_val; | |
2462 | rtx mult_val; | |
2463 | int dest_regno; | |
2464 | int biv_found; | |
2465 | /* This is 1 if current insn could be executed zero times in the loop. */ | |
2466 | int maybe_never = 0; | |
2467 | /* List of all possible basic induction variables. */ | |
2468 | struct iv_class *iv_list = 0; | |
2469 | /* Temporary list pointers for traversing iv_list. */ | |
2470 | struct iv_class *bl, *backbl; | |
2471 | /* Ratio of extra register life span we can justify | |
2472 | for saving an instruction. More if loop doesn't call subroutines | |
2473 | since in that case saving an insn makes more difference | |
2474 | and more registers are available. */ | |
2475 | /* ??? could set this to last value of threshold in move_movables */ | |
2476 | int threshold = loop_has_call ? 17 : 34; | |
2477 | /* Map of pseudo-register replacements. */ | |
2478 | rtx *reg_map; | |
2479 | int call_seen; | |
2480 | ||
2481 | induct_var = (enum iv_mode *) alloca (nregs * sizeof (induct_var[0])); | |
2482 | bzero ((char *)induct_var, nregs * sizeof (induct_var[0])); | |
2483 | induct_struct = (struct induction **) | |
2484 | alloca (nregs * sizeof (struct induction *)); | |
2485 | bzero ((char *)induct_struct, nregs * sizeof (struct induction *)); | |
2486 | class_struct = (struct iv_class **) | |
2487 | alloca (nregs * sizeof (struct iv_class *)); | |
2488 | bzero ((char *)class_struct, nregs * sizeof (struct iv_class *)); | |
2489 | ||
2490 | /* Scan through loop to find all possible bivs. */ | |
2491 | ||
2492 | for (p = NEXT_INSN (loop_start); p != end; p = NEXT_INSN (p)) | |
2493 | { | |
2494 | if (GET_CODE (p) == INSN | |
2495 | && GET_CODE (PATTERN (p)) == SET | |
2496 | && GET_CODE (SET_DEST (PATTERN (p))) == REG) | |
2497 | { | |
2498 | dest_regno = REGNO (SET_DEST (PATTERN (p))); | |
2499 | if (induct_var[dest_regno] != NOT_BASIC_INDUCT | |
2500 | && dest_regno >= FIRST_PSEUDO_REGISTER) | |
2501 | { | |
2502 | if (basic_induction_var (SET_SRC (PATTERN (p)), dest_regno, | |
2503 | &inc_val, &mult_val)) | |
2504 | { | |
2505 | /* It is a possible basic induction variable. | |
2506 | Create and initialize an induction structure for it. */ | |
2507 | ||
2508 | struct induction *v = | |
2509 | (struct induction *) alloca (sizeof (struct induction)); | |
2510 | ||
2511 | v->insn = p; | |
2512 | v->src_regno = dest_regno; | |
2513 | v->dest_regno = dest_regno; | |
2514 | v->mult_val = mult_val; | |
2515 | v->add_val = inc_val; | |
2516 | v->mode = GET_MODE (SET_DEST (PATTERN (p))); | |
2517 | ||
2518 | /* Add this to the reg's iv_class, creating a class | |
2519 | if this is the first incrementation of the reg. */ | |
2520 | ||
2521 | bl = class_struct[dest_regno]; | |
2522 | if (bl) | |
2523 | { | |
2524 | v->family = bl->biv; | |
2525 | bl->biv = v; | |
2526 | bl->biv_count++; | |
2527 | } | |
2528 | else | |
2529 | { | |
2530 | /* Create and initialize new iv_class. */ | |
2531 | ||
2532 | bl = (struct iv_class *) alloca (sizeof (struct iv_class)); | |
2533 | ||
2534 | bl->regno = dest_regno; | |
2535 | bl->biv = v; | |
2536 | v->family = 0; | |
2537 | bl->giv = 0; | |
2538 | bl->biv_count = 1; | |
2539 | bl->giv_count = 0; | |
2540 | ||
2541 | /* Set initial value to the reg itself. */ | |
2542 | bl->initial_value = SET_DEST (PATTERN (p)); | |
2543 | /* We haven't seen the intializing insn yet */ | |
2544 | bl->init_insn = 0; | |
2545 | bl->eliminable = 0; | |
2546 | bl->nonneg = 0; | |
2547 | ||
2548 | /* Add this insn to iv_list. */ | |
2549 | bl->next = iv_list; | |
2550 | iv_list = bl; | |
2551 | ||
2552 | /* Put it in the array of iv_lists. */ | |
2553 | class_struct[dest_regno] = bl; | |
2554 | } | |
2555 | ||
2556 | induct_var[dest_regno] = BASIC_INDUCT; | |
2557 | ||
2558 | if (loop_dump_stream) | |
2559 | { | |
2560 | fprintf (loop_dump_stream, | |
2561 | "Insn %d: possible biv, reg %d,", | |
2562 | INSN_UID (p), dest_regno); | |
2563 | if (GET_CODE (inc_val) == CONST_INT) | |
2564 | fprintf (loop_dump_stream, " const = %d\n", | |
2565 | INTVAL (inc_val)); | |
2566 | else | |
2567 | { | |
2568 | fprintf (loop_dump_stream, " const = "); | |
2569 | print_rtl (loop_dump_stream, inc_val); | |
2570 | fprintf (loop_dump_stream, "\n"); | |
2571 | } | |
2572 | } | |
2573 | } | |
2574 | else | |
2575 | induct_var[dest_regno] = NOT_BASIC_INDUCT; | |
2576 | } | |
2577 | } | |
2578 | } | |
2579 | ||
2580 | /* Scan iv_list to remove all regs that proved not to be bivs. | |
2581 | Make a sanity check against n_times_set. */ | |
2582 | ||
2583 | biv_found = 0; | |
2584 | ||
2585 | for (backbl = bl = iv_list; bl; backbl = bl, bl = bl->next) | |
2586 | { | |
2587 | if (induct_var[bl->regno] != BASIC_INDUCT) | |
2588 | { | |
2589 | /* Not a basic induction variable, remove this iv_class. */ | |
2590 | ||
2591 | if (backbl == bl) | |
2592 | iv_list = bl->next; | |
2593 | else | |
2594 | backbl->next = bl->next; | |
2595 | ||
2596 | if (loop_dump_stream) | |
2597 | fprintf (loop_dump_stream, "Reg %d: biv discarded, not induct\n", | |
2598 | bl->regno); | |
2599 | } | |
2600 | else if (n_times_set[bl->regno] != bl->biv_count) | |
2601 | { | |
2602 | /* This happens if register modified by subreg, etc. */ | |
2603 | /* Make sure it is not recognized as a basic induction var: */ | |
2604 | /* remove this iv_class from iv_list. */ | |
2605 | ||
2606 | induct_var[bl->regno] = NOT_BASIC_INDUCT; | |
2607 | ||
2608 | if (backbl == bl) | |
2609 | iv_list = bl->next; | |
2610 | else | |
2611 | backbl->next = bl->next; | |
2612 | ||
2613 | if (loop_dump_stream) | |
2614 | fprintf (loop_dump_stream, "Reg %d: biv discarded, count error\n", | |
2615 | bl->regno); | |
2616 | } | |
2617 | else | |
2618 | { | |
2619 | /* This is a valid basic induction variable. */ | |
2620 | ||
2621 | biv_found++; | |
2622 | ||
2623 | if (loop_dump_stream) | |
2624 | fprintf (loop_dump_stream, "Reg %d: biv verified\n", bl->regno); | |
2625 | } | |
2626 | } | |
2627 | ||
2628 | /* Exit if there are no bivs. */ | |
2629 | if (!iv_list) | |
2630 | return; | |
2631 | ||
2632 | /* Find initial value for each biv. */ | |
2633 | /* Search backwards from loop_start, halting at first label | |
2634 | or when all bivs have been seen. */ | |
2635 | ||
2636 | call_seen = 0; | |
2637 | p = loop_start; | |
2638 | while (biv_found) | |
2639 | { | |
2640 | p = PREV_INSN (p); | |
2641 | if (p == 0) | |
2642 | break; | |
2643 | ||
2644 | if (GET_CODE (p) == CALL_INSN) | |
2645 | call_seen = 1; | |
2646 | ||
2647 | if (GET_CODE (p) == INSN | |
2648 | && GET_CODE (PATTERN (p)) == SET) | |
2649 | { | |
2650 | rtx dest = SET_DEST (PATTERN (p)); | |
2651 | ||
2652 | while (GET_CODE (dest) == SUBREG | |
2653 | || GET_CODE (dest) == ZERO_EXTRACT | |
2654 | || GET_CODE (dest) == SIGN_EXTRACT | |
2655 | || GET_CODE (dest) == STRICT_LOW_PART) | |
2656 | dest = XEXP (dest, 0); | |
2657 | ||
2658 | if (GET_CODE (dest) == REG) | |
2659 | { | |
2660 | int dest_regno = REGNO (dest); | |
2661 | if (induct_var[dest_regno] == BASIC_INDUCT | |
2662 | && class_struct[dest_regno]->init_insn == 0) | |
2663 | { | |
2664 | /* This is the first modification found for this reg. */ | |
2665 | ||
2666 | rtx src = SET_SRC (PATTERN (p)); | |
2667 | ||
2668 | /* Record the intializing INSN */ | |
2669 | ||
2670 | class_struct[dest_regno]->init_insn = p; | |
2671 | ||
2672 | if (loop_dump_stream) | |
2673 | fprintf (loop_dump_stream, "Biv %d initialized at insn %d: ", | |
2674 | dest_regno, INSN_UID (p)); | |
2675 | ||
2676 | /* Save value if it is a constant or register. */ | |
2677 | if (CONSTANT_P (src) | |
2678 | || (GET_CODE (src) == REG | |
2679 | /* Don't try to use a value in a hard reg | |
2680 | across a call which clobbers it. */ | |
2681 | && ! (REGNO (src) < FIRST_PSEUDO_REGISTER | |
2682 | && call_used_regs[REGNO (src)] | |
2683 | && call_seen) | |
2684 | && ! reg_set_between_p (src, p, loop_start))) | |
2685 | { | |
2686 | class_struct[dest_regno]->initial_value = src; | |
2687 | ||
2688 | if (loop_dump_stream) | |
2689 | fprintf (loop_dump_stream, "initial value "); | |
2690 | if (loop_dump_stream) | |
2691 | { | |
2692 | if (GET_CODE (src) == CONST_INT) | |
2693 | fprintf (loop_dump_stream, "%d\n", INTVAL (src)); | |
2694 | else | |
2695 | { | |
2696 | print_rtl (loop_dump_stream, src); | |
2697 | fprintf (loop_dump_stream, "\n"); | |
2698 | } | |
2699 | } | |
2700 | } | |
2701 | else | |
2702 | { | |
2703 | /* Biv initial value is not simple move, | |
2704 | so let it keep intial value of "itself". */ | |
2705 | ||
2706 | if (loop_dump_stream) | |
2707 | fprintf (loop_dump_stream, "complex initial value\n"); | |
2708 | } | |
2709 | ||
2710 | biv_found--; | |
2711 | } | |
2712 | } | |
2713 | } | |
2714 | else if (GET_CODE (p) == CODE_LABEL) | |
2715 | break; | |
2716 | } | |
2717 | ||
2718 | /* Search the loop for general induction variables. */ | |
2719 | ||
2720 | /* A register is a giv if: it is only set once, it is a function of a | |
2721 | biv and a constant (or invariant), and it is not a biv. */ | |
2722 | ||
2723 | p = scan_start; | |
2724 | while (1) | |
2725 | { | |
2726 | p = NEXT_INSN (p); | |
2727 | /* At end of a straight-in loop, we are done. | |
2728 | At end of a loop entered at the bottom, scan the top. */ | |
2729 | if (p == scan_start) | |
2730 | break; | |
2731 | if (p == end) | |
2732 | { | |
2733 | if (loop_top != 0) | |
2734 | p = NEXT_INSN (loop_top); | |
2735 | else | |
2736 | break; | |
2737 | if (p == scan_start) | |
2738 | break; | |
2739 | } | |
2740 | ||
2741 | /* Look for a general induction variable in a register. */ | |
2742 | if (GET_CODE (p) == INSN | |
2743 | && GET_CODE (PATTERN (p)) == SET | |
2744 | && GET_CODE (SET_DEST (PATTERN (p))) == REG | |
2745 | && ! may_not_optimize[REGNO (SET_DEST (PATTERN (p)))]) | |
2746 | { | |
2747 | int src_regno; | |
2748 | rtx add_val; | |
2749 | rtx mult_val; | |
2750 | int benefit; | |
2751 | rtx regnote = 0; | |
2752 | struct induction *forces = 0; | |
2753 | struct induction *forces2 = 0; | |
2754 | ||
2755 | dest_regno = REGNO (SET_DEST (PATTERN (p))); | |
2756 | if (dest_regno < FIRST_PSEUDO_REGISTER) | |
2757 | continue; | |
2758 | ||
2759 | if (/* Normal giv. */ | |
2760 | ((benefit = general_induction_var (SET_SRC (PATTERN (p)), | |
2761 | &src_regno, &add_val, | |
2762 | &mult_val, | |
2763 | &forces, &forces2)) | |
2764 | /* Giv set with call to a library routine. */ | |
2765 | || ((regnote = loop_find_reg_equal (p)) | |
2766 | && | |
2767 | (benefit = general_induction_var (XEXP (regnote, 0), | |
2768 | &src_regno, | |
2769 | &add_val, &mult_val, | |
2770 | &forces, &forces2)))) | |
2771 | /* Don't try to handle any regs made by loop optimization. | |
2772 | We have nothing on them in regno_first_uid, etc. */ | |
2773 | && dest_regno < old_max_reg | |
2774 | /* Don't recognize a BASIC_INDUCT_VAR here. */ | |
2775 | && dest_regno != src_regno | |
2776 | /* This must be the only place where the register is set. */ | |
2777 | && (n_times_set[dest_regno] == 1 | |
2778 | || (benefit = consec_sets_giv (benefit, p, | |
2779 | src_regno, dest_regno, | |
2780 | &add_val, &mult_val)))) | |
2781 | { | |
2782 | int count; | |
2783 | struct induction *v = | |
2784 | (struct induction *) alloca (sizeof (struct induction)); | |
2785 | rtx temp; | |
2786 | ||
2787 | record_giv (v, p, src_regno, dest_regno, mult_val, add_val, benefit, | |
2788 | forces, forces2, DEST_REG, maybe_never, 0, loop_end); | |
2789 | ||
2790 | /* Skip the consecutive insns, if there are any. */ | |
2791 | for (count = v->consec - 1; count >= 0; count--) | |
2792 | { | |
2793 | /* If first insn of libcall sequence, skip to end. */ | |
2794 | /* Do this at start of loop, since INSN is guaranteed to | |
2795 | be an insn here. */ | |
2796 | if (temp = find_reg_note (p, REG_LIBCALL, 0)) | |
2797 | { | |
2798 | /* Eliminating a libcall does more good than | |
2799 | eliminating a single insn to do the same job. */ | |
2800 | benefit += LIBCALL_BENEFIT; | |
2801 | p = XEXP (temp, 0); | |
2802 | } | |
2803 | ||
2804 | do p = NEXT_INSN (p); | |
2805 | while (GET_CODE (p) == NOTE); | |
2806 | } | |
2807 | } | |
2808 | } | |
2809 | ||
2810 | #ifndef DONT_REDUCE_ADDR | |
2811 | /* Look for givs which are memory addresses. */ | |
2812 | /* This resulted in worse code on a VAX 8600. I wonder if it | |
2813 | still does. */ | |
2814 | if (GET_CODE (p) == INSN) | |
2815 | find_mem_givs (PATTERN (p), p, maybe_never, loop_end); | |
2816 | #endif | |
2817 | ||
2818 | /* Past a label or a jump, we get to insns for which we can't count | |
2819 | on whether or how many times they will be executed during each | |
2820 | iteration. Givs found afterwards cannot be marked replaceable. */ | |
2821 | if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN) | |
2822 | maybe_never = 1; | |
2823 | } | |
2824 | ||
2825 | /* Try to prove that the loop counter variable (if any) is always | |
2826 | nonnegative; if so, record that fact with a REG_NONNEG note | |
2827 | so that "decrement and branch until zero" insn can be used. */ | |
2828 | check_dbra_loop (loop_end, iv_list, insn_count, loop_start); | |
2829 | ||
2830 | /* Create reg_map to hold substitutions for replaceable giv regs. */ | |
2831 | reg_map = (rtx *) alloca (nregs * sizeof (rtx)); | |
2832 | bzero ((char *)reg_map, nregs * sizeof (rtx)); | |
2833 | ||
2834 | /* Examine each iv class for feasibility of strength reduction/induction | |
2835 | variable elimination. */ | |
2836 | ||
2837 | for (bl = iv_list; bl; bl = bl->next) | |
2838 | { | |
2839 | struct induction *v; | |
2840 | int benefit; | |
2841 | int replaceable; | |
2842 | int all_reduced; | |
2843 | rtx final_value = 0; | |
2844 | ||
2845 | /* Test whether it will be possible to eliminate this biv | |
2846 | provided all givs are reduced. This is possible if either | |
2847 | the reg is not used outside the loop, or we can compute | |
2848 | what its final value will be. | |
2849 | ||
2850 | Don't try if we put a REG_NONNEG note on the endtest for this biv. | |
2851 | ??? That should be only on machines that have dbra insns. */ | |
2852 | ||
2853 | /* Compare against bl->init_insn rather than loop_start. | |
2854 | We aren't concerned with any uses of the biv between | |
2855 | init_insn and loop_start since these won't be affected | |
2856 | by the value of the biv elsewhere in the function, so | |
2857 | long as init_insn doesn't use the biv itself. | |
2858 | March 14, 1989 -- self@bayes.arc.nasa.gov */ | |
2859 | ||
2860 | if ((uid_luid[regno_last_uid[bl->regno]] < INSN_LUID (loop_end) | |
2861 | && bl->init_insn | |
2862 | && INSN_UID (bl->init_insn) < max_uid | |
2863 | && uid_luid[regno_first_uid[bl->regno]] >= INSN_LUID (bl->init_insn) | |
2864 | && ! reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), | |
2865 | SET_SRC (PATTERN (bl->init_insn))) | |
2866 | && ! bl->nonneg) | |
2867 | || (final_value = final_biv_value (bl, loop_end))) | |
2868 | check_eliminate_biv (bl, loop_start, end); | |
2869 | else | |
2870 | { | |
2871 | if (loop_dump_stream) | |
2872 | { | |
2873 | fprintf (loop_dump_stream, | |
2874 | "Cannot eliminate biv %d.\n", | |
2875 | bl->regno); | |
2876 | fprintf (loop_dump_stream, | |
2877 | "First use: insn %d, last use: insn %d.\n", | |
2878 | regno_first_uid[bl->regno], | |
2879 | regno_last_uid[bl->regno]); | |
2880 | } | |
2881 | } | |
2882 | ||
2883 | /* This will be true at the end, if all givs which depend on this | |
2884 | biv have been strength reduced. | |
2885 | We can't (currently) eliminate the biv unless this is so. */ | |
2886 | all_reduced = 1; | |
2887 | ||
2888 | /* Check each giv in this class. */ | |
2889 | ||
2890 | for (v = bl->giv; v; v = v->family) | |
2891 | { | |
2892 | struct induction *tv; | |
2893 | ||
2894 | if (v->ignore) | |
2895 | continue; | |
2896 | ||
2897 | benefit = v->benefit; | |
2898 | replaceable = v->replaceable; | |
2899 | ||
2900 | /* Reduce benefit if not replaceable, since we will insert | |
2901 | a move-insn to replace the insn that calculates this giv. */ | |
2902 | if (!replaceable && ! bl->eliminable) | |
2903 | benefit -= COPY_PENALTY; | |
2904 | ||
2905 | /* Decrease the benefit to count the add-insns that we will | |
2906 | insert to increment the reduced reg for the giv. */ | |
2907 | benefit -= ADD_BENEFIT * bl->biv_count; | |
2908 | ||
2909 | /* Find all equivalent givs (that bear same relation to the biv). | |
2910 | Link them via the `same' field and add their benefits together. | |
2911 | They can be replaced with a single register. */ | |
2912 | ||
2913 | for (tv = v->family; tv; tv = tv->family) | |
2914 | { | |
2915 | if (tv->ignore == 0 | |
2916 | && tv->src_regno == v->src_regno | |
2917 | && rtx_equal_p (tv->mult_val, v->mult_val) | |
2918 | && rtx_equal_p (tv->add_val, v->add_val)) | |
2919 | { | |
2920 | benefit += tv->benefit; | |
2921 | if (! tv->replaceable) | |
2922 | benefit -= COPY_PENALTY; | |
2923 | v->lifetime += tv->lifetime; | |
2924 | v->times_used += tv->times_used; | |
2925 | tv->ignore = 1; | |
2926 | ||
2927 | /* Link them together via `same' field. */ | |
2928 | tv->same = v->same; | |
2929 | v->same = tv; | |
2930 | ||
2931 | if (loop_dump_stream) | |
2932 | fprintf (loop_dump_stream, | |
2933 | "giv of insn %d combined with that of %d.\n", | |
2934 | INSN_UID (v->insn), INSN_UID (tv->insn)); | |
2935 | } | |
2936 | } | |
2937 | ||
2938 | /* Decide whether to strength-reduce this giv | |
2939 | or to leave the code unchanged | |
2940 | (recompute it from the biv each time it is used). | |
2941 | This decision can be made independently for each giv. */ | |
2942 | ||
2943 | /* ??? Perhaps attempt to guess whether autoincrement will handle | |
2944 | some of the new add insns; if so, can increase BENEFIT | |
2945 | (undo the subtraction of ADD_BENEFIT that was done above). */ | |
2946 | ||
2947 | /* If an insn is not to be strength reduced, then set its ignore | |
2948 | flag, and clear all_reduced. */ | |
2949 | ||
2950 | /* Is it right to consider times_used? */ | |
2951 | ||
2952 | /* ??? What about the insns that are 'forced' by this one? | |
2953 | Although this insn is not worthwhile to reduce, it may be | |
2954 | worthwhile to reduce the simpler givs used to compute this | |
2955 | complex giv. */ | |
2956 | ||
2957 | /* ??? Hey! If a giv has its forces field set, then that means | |
2958 | it is not computed directly from the biv, it is instead computed | |
2959 | from a simpler giv. If we define UNFORCE_INSNS, then the simpler | |
2960 | giv will be considered for strength reduction, and this giv should | |
2961 | not cause all_reduced to be cleared because it DOESN'T use the | |
2962 | biv!!! If the simpler giv can not be reduced, then that simpler | |
2963 | biv will still cause all_reduced to be cleared. */ | |
2964 | ||
2965 | if (benefit <= 0) | |
2966 | { | |
2967 | if (loop_dump_stream) | |
2968 | fprintf (loop_dump_stream, "giv of insn %d, no benefit\n", | |
2969 | INSN_UID (v->insn)); | |
2970 | v->ignore = 1; | |
2971 | all_reduced = 0; | |
2972 | } | |
2973 | ||
2974 | if (v->lifetime * threshold * benefit < insn_count) | |
2975 | { | |
2976 | if (loop_dump_stream) | |
2977 | fprintf (loop_dump_stream, | |
2978 | "giv of insn %d not worth while, %d vs %d.\n", | |
2979 | INSN_UID (v->insn), | |
2980 | v->lifetime * threshold * benefit, insn_count); | |
2981 | v->ignore = 1; | |
2982 | all_reduced = 0; | |
2983 | } | |
2984 | ||
2985 | /* Now check that we can increment the reduced giv | |
2986 | without needing a multiply insn. If not, reject it. */ | |
2987 | ||
2988 | if (! v->ignore) | |
2989 | { | |
2990 | int success = 1; | |
2991 | ||
2992 | for (tv = bl->biv; tv; tv = tv->family) | |
2993 | if (tv->mult_val == const1_rtx) | |
2994 | success &= product_cheap_p (tv->add_val, v->mult_val); | |
2995 | ||
2996 | if (! success) | |
2997 | { | |
2998 | if (loop_dump_stream) | |
2999 | fprintf (loop_dump_stream, | |
3000 | "giv of insn %d: would need a multiply.\n", | |
3001 | INSN_UID (v->insn)); | |
3002 | v->ignore = 1; | |
3003 | all_reduced = 0; | |
3004 | } | |
3005 | } | |
3006 | } | |
3007 | ||
3008 | /* Reduce each giv that we decided to reduce. */ | |
3009 | ||
3010 | for (v = bl->giv; v; v = v->family) | |
3011 | { | |
3012 | struct induction *tv; | |
3013 | if (! v->ignore) | |
3014 | { | |
3015 | rtx new_reg; | |
3016 | ||
3017 | /* Note Iris compiler dies if ?: is used inside gen_reg_rtx. */ | |
3018 | if (v->giv_type == DEST_ADDR) | |
3019 | new_reg = gen_reg_rtx (Pmode); | |
3020 | else | |
3021 | new_reg = gen_reg_rtx (GET_MODE (SET_DEST (PATTERN (v->insn)))); | |
3022 | ||
3023 | /* For each place where the biv is incremented, | |
3024 | add an insn to increment the new, reduced reg for the giv. | |
3025 | Insert it before the insn that sets the biv, | |
3026 | so that the biv increment remains last before the endtest, | |
3027 | so that dbra will still be recognized. */ | |
3028 | ||
3029 | for (tv = bl->biv; tv; tv = tv->family) | |
3030 | { | |
3031 | struct induction *iv; | |
3032 | rtx before_insn = tv->insn; | |
3033 | ||
3034 | /* If this increment is between the setting of the giv and | |
3035 | its use, don't increment until after the use. */ | |
3036 | for (iv = v; iv; iv = iv->same) | |
3037 | { | |
3038 | if (INSN_LUID (tv->insn) <= INSN_LUID (iv->insn) | |
3039 | && ((iv->forces | |
3040 | && (INSN_LUID (tv->insn) | |
3041 | >= INSN_LUID (iv->forces->insn)) | |
3042 | || (iv->forces2 | |
3043 | && (INSN_LUID (tv->insn) | |
3044 | >= INSN_LUID (iv->forces2->insn)))))) | |
3045 | { | |
3046 | before_insn = NEXT_INSN (iv->insn); | |
3047 | break; | |
3048 | } | |
3049 | } | |
3050 | ||
3051 | if (tv->mult_val == const1_rtx) | |
3052 | emit_iv_inc (tv->add_val, v->mult_val, | |
3053 | new_reg, before_insn); | |
3054 | else /* tv->mult_val == const0_rtx */ | |
3055 | /* A multiply is acceptable here | |
3056 | since this is presumed to be seldom executed. */ | |
3057 | emit_iv_init_code (tv->add_val, v->mult_val, | |
3058 | v->add_val, new_reg, before_insn); | |
3059 | } | |
3060 | ||
3061 | /* Add code at loop start to initialize giv's reduced reg. */ | |
3062 | ||
3063 | emit_iv_init_code (bl->initial_value, v->mult_val, | |
3064 | v->add_val, new_reg, loop_start); | |
3065 | /* If the initial value uses a register, | |
3066 | then we may have just extended its range of appearance. | |
3067 | Update this conservatively for the sake of outer loops. */ | |
3068 | if (GET_CODE (bl->initial_value) == REG | |
3069 | && (uid_luid[regno_last_uid[REGNO (bl->initial_value)]] | |
3070 | < INSN_LUID (loop_start))) | |
3071 | uid_luid[regno_last_uid[REGNO (bl->initial_value)]] | |
3072 | = INSN_LUID (loop_start); | |
3073 | ||
3074 | /* For each giv register that can be reduced now: | |
3075 | delete old insn that modifies the giv, | |
3076 | if replaceable, substitute reduced reg | |
3077 | wherever the old giv occurs; | |
3078 | else add new move insn "giv_reg = reduced_reg". */ | |
3079 | ||
3080 | for (tv = v; tv; tv = tv->same) | |
3081 | { | |
3082 | /* Record the identity of the reduced reg. */ | |
3083 | tv->new_reg = new_reg; | |
3084 | ||
3085 | if (tv->giv_type == DEST_ADDR) | |
3086 | { | |
3087 | /* Store reduced reg as the address in the memref | |
3088 | where we found this giv. */ | |
3089 | * tv->location = new_reg; | |
3090 | } | |
3091 | else if (tv->replaceable) | |
3092 | { | |
3093 | reg_map[tv->dest_regno] = new_reg; | |
3094 | /* If giv lives after end of loop, | |
3095 | emit insn to copy reduced reg into old reg, | |
3096 | at the end of the loop. | |
3097 | ?? insufficient; used before loop could | |
3098 | mean live after loop, due to surrounding loop. */ | |
3099 | /* Currently a giv used outside | |
3100 | the loop will not be marked replaceable, | |
3101 | so these deficiencies don't really hurt. */ | |
3102 | if (uid_luid[regno_last_uid[tv->dest_regno]] | |
3103 | > uid_luid[INSN_UID (loop_end)]) | |
3104 | { | |
3105 | /* ?? This won't work. We need to do this at | |
3106 | ALL exits. */ | |
3107 | emit_insn_after (gen_rtx (SET, VOIDmode, | |
3108 | SET_DEST (PATTERN (tv->insn)), | |
3109 | new_reg), | |
3110 | loop_end); | |
3111 | abort (); | |
3112 | } | |
3113 | } | |
3114 | else | |
3115 | { | |
3116 | /* Not replaceable; emit an insn to set the | |
3117 | original giv reg from the reduced giv. */ | |
3118 | ||
3119 | int count; | |
3120 | rtx after_insn = tv->insn; | |
3121 | ||
3122 | for (count = tv->consec; count > 0; count--) | |
3123 | after_insn = next_real_insn (after_insn); | |
3124 | ||
3125 | /* Put new insn after, not before, in case | |
3126 | after_insn is the end of a libcall. */ | |
3127 | emit_insn_after (gen_rtx (SET, VOIDmode, | |
3128 | SET_DEST (PATTERN (tv->insn)), | |
3129 | new_reg), | |
3130 | after_insn); | |
3131 | } | |
3132 | ||
3133 | /* Delete the insn that used to set the old giv reg, | |
3134 | unless we modified an address in it. | |
3135 | In any case, delete the other insns used for this one. */ | |
3136 | delete_insn_forces (tv, tv->giv_type != DEST_ADDR); | |
3137 | ||
3138 | if (loop_dump_stream) | |
3139 | fprintf (loop_dump_stream, "giv at %d reduced to reg %d\n", | |
3140 | INSN_UID (tv->insn), REGNO (new_reg)); | |
3141 | } | |
3142 | /* One set of equivalent givs has been strength-reduced. */ | |
3143 | } | |
3144 | #if 0 | |
3145 | else if (v->new_reg == 0) | |
3146 | { | |
3147 | /* This giv wasn't reduced and is not worth reducing. */ | |
3148 | ||
3149 | for (tv = v; tv; tv = tv->same) | |
3150 | if (loop_dump_stream) | |
3151 | fprintf (loop_dump_stream, "giv at %d not reduced\n", | |
3152 | INSN_UID (tv->insn)); | |
3153 | ||
3154 | all_reduced = 0; | |
3155 | } | |
3156 | #endif | |
3157 | } | |
3158 | ||
3159 | /* All the givs in this family have been reduced if they merit it. */ | |
3160 | ||
3161 | /* Try to eliminate the biv, if it is a candidate. | |
3162 | This won't work if ! all_reduced, | |
3163 | since the givs we planned to use might not have been reduced. */ | |
3164 | ||
3165 | if (all_reduced == 1 && bl->eliminable) | |
3166 | { | |
3167 | /* Get the REG rtx for the biv. */ | |
3168 | rtx reg = SET_DEST (PATTERN (bl->biv->insn)); | |
3169 | ||
3170 | for (p = loop_start; p != end; p = NEXT_INSN (p)) | |
3171 | { | |
3172 | enum rtx_code code = GET_CODE (p); | |
3173 | if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) | |
3174 | && reg_mentioned_p (reg, PATTERN (p)) | |
3175 | && SET_DEST (PATTERN (p)) == cc0_rtx) | |
3176 | /* Found a compare instruction using this biv; | |
3177 | rewrite it to use a related giv. */ | |
3178 | { | |
3179 | struct induction *v1; | |
3180 | /* If this is an insn which uses the biv ONLY in the | |
3181 | calculation of a giv which is in the family of this | |
3182 | biv, it's ok becuase it will go away when the giv is | |
3183 | reduced. */ | |
3184 | for (v1 = bl->giv; v1; v1 = v1->family) | |
3185 | if (v1->insn == p) | |
3186 | { | |
3187 | if (v1->giv_type == DEST_REG | |
3188 | || (v1->giv_type == DEST_ADDR | |
3189 | /* I thought the test was backwards, | |
3190 | but then I found the real problem | |
3191 | was in the subroutine. */ | |
3192 | && ! other_reg_use_p (reg, *(v1->location), | |
3193 | PATTERN (p)))) | |
3194 | break; | |
3195 | } | |
3196 | if (!v1) | |
3197 | eliminate_biv (p, bl, loop_start); | |
3198 | } | |
3199 | } | |
3200 | ||
3201 | /* Biv is no longer really needed inside the loop, | |
3202 | so delete all insns that set the biv. */ | |
3203 | ||
3204 | for (v = bl->biv; v; v = v->family) | |
3205 | delete_insn (v->insn); | |
3206 | ||
3207 | /* ?? If we created a new test to bypass the loop entirely, | |
3208 | or otherwise drop straight in, based on this test, then | |
3209 | we might want to rewrite it also. This way some later | |
3210 | pass has more hope of removing the intialization of this | |
3211 | biv entirely. */ | |
3212 | ||
3213 | /* If final_value != 0, then biv may be used after loop end | |
3214 | and we must emit an insn to set it just in case. */ | |
3215 | if (final_value != 0) | |
3216 | emit_insn_after (gen_rtx (SET, VOIDmode, reg, final_value), | |
3217 | loop_end); | |
3218 | ||
3219 | if (loop_dump_stream) | |
3220 | fprintf (loop_dump_stream, "Reg %d: biv eliminated\n", | |
3221 | bl->regno); | |
3222 | } | |
3223 | } | |
3224 | ||
3225 | /* Go through all the instructions in the loop, making all the | |
3226 | register substitutions scheduled in REG_MAP. */ | |
3227 | ||
3228 | for (p = loop_start; p != end; p = NEXT_INSN (p)) | |
3229 | if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN | |
3230 | || GET_CODE (p) == CALL_INSN) | |
3231 | replace_regs (PATTERN (p), reg_map, nregs); | |
3232 | ||
3233 | if (loop_dump_stream) | |
3234 | fprintf (loop_dump_stream, "\n"); | |
3235 | } | |
3236 | \f | |
3237 | /* Nonzero if register REG appears somewhere within IN, other than in | |
3238 | subexpressions EQ to EXPR. This is a modification of reg_mentioned_p. */ | |
3239 | ||
3240 | int | |
3241 | other_reg_use_p (reg, expr, in) | |
3242 | register rtx reg, expr, in; | |
3243 | { | |
3244 | register char *fmt; | |
3245 | register int i; | |
3246 | register enum rtx_code code; | |
3247 | ||
3248 | if (in == 0 || in == expr) | |
3249 | return 0; | |
3250 | ||
3251 | if (reg == in) | |
3252 | return 1; | |
3253 | ||
3254 | code = GET_CODE (in); | |
3255 | ||
3256 | switch (code) | |
3257 | { | |
3258 | /* Compare registers by number. */ | |
3259 | case REG: | |
3260 | return GET_CODE (reg) == REG && REGNO (in) == REGNO (reg); | |
3261 | ||
3262 | /* These codes have no constituent expressions | |
3263 | and are unique. */ | |
3264 | case CC0: | |
3265 | case PC: | |
3266 | case CONST_INT: | |
3267 | case CONST_DOUBLE: | |
3268 | case SYMBOL_REF: | |
3269 | case CODE_LABEL: | |
3270 | return 0; | |
3271 | } | |
3272 | ||
3273 | fmt = GET_RTX_FORMAT (code); | |
3274 | ||
3275 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
3276 | { | |
3277 | if (fmt[i] == 'E') | |
3278 | { | |
3279 | register int j; | |
3280 | for (j = XVECLEN (in, i) - 1; j >= 0; j--) | |
3281 | if (other_reg_use_p (reg, expr, XVECEXP (in, i, j))) | |
3282 | return 1; | |
3283 | } | |
3284 | else if (fmt[i] == 'e' | |
3285 | && other_reg_use_p (reg, expr, XEXP (in, i))) | |
3286 | return 1; | |
3287 | } | |
3288 | return 0; | |
3289 | } | |
3290 | \f | |
3291 | /* Scan X for memory refs and check each memory address | |
3292 | as a possible giv. INSN is the insn whose pattern X comes from. | |
3293 | MAYBE_NEVER is 1 if the loop might execute INSN zero times. */ | |
3294 | ||
3295 | static void | |
3296 | find_mem_givs (x, insn, maybe_never, loop_end) | |
3297 | rtx x; | |
3298 | rtx insn; | |
3299 | int maybe_never; | |
3300 | rtx loop_end; | |
3301 | { | |
3302 | register int i, j; | |
3303 | register enum rtx_code code; | |
3304 | register char *fmt; | |
3305 | ||
3306 | if (x == 0) | |
3307 | return; | |
3308 | ||
3309 | code = GET_CODE (x); | |
3310 | switch (code) | |
3311 | { | |
3312 | case REG: | |
3313 | case CONST_INT: | |
3314 | case CONST: | |
3315 | case CONST_DOUBLE: | |
3316 | case SYMBOL_REF: | |
3317 | case LABEL_REF: | |
3318 | case PC: | |
3319 | case CC0: | |
3320 | case ADDR_VEC: | |
3321 | case ADDR_DIFF_VEC: | |
3322 | case USE: | |
3323 | case CLOBBER: | |
3324 | return; | |
3325 | ||
3326 | case MEM: | |
3327 | { | |
3328 | int src_regno; | |
3329 | rtx add_val; | |
3330 | rtx mult_val; | |
3331 | int benefit; | |
3332 | struct induction *forces = 0; | |
3333 | struct induction *forces2 = 0; | |
3334 | ||
3335 | benefit = general_induction_var (XEXP (x, 0), | |
3336 | &src_regno, &add_val, &mult_val, | |
3337 | &forces, &forces2); | |
3338 | if (benefit > 0) | |
3339 | { | |
3340 | /* Found one; record it. */ | |
3341 | struct induction *v = | |
3342 | (struct induction *) oballoc (sizeof (struct induction)); | |
3343 | ||
3344 | record_giv (v, insn, src_regno, 0, mult_val, add_val, benefit, | |
3345 | forces, forces2, DEST_ADDR, maybe_never, &XEXP (x, 0), | |
3346 | loop_end); | |
3347 | } | |
3348 | return; | |
3349 | } | |
3350 | } | |
3351 | ||
3352 | /* Recursively scan the subexpressions for other mem refs. */ | |
3353 | ||
3354 | fmt = GET_RTX_FORMAT (code); | |
3355 | for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) | |
3356 | if (fmt[i] == 'e') | |
3357 | find_mem_givs (XEXP (x, i), insn, maybe_never, loop_end); | |
3358 | else if (fmt[i] == 'E') | |
3359 | for (j = 0; j < XVECLEN (x, i); j++) | |
3360 | find_mem_givs (XVECEXP (x, i, j), insn, maybe_never, loop_end); | |
3361 | } | |
3362 | \f | |
3363 | /* Fill in the data about one giv. | |
3364 | V is the `struct induction' in which we record the giv. (It is | |
3365 | allocated by the caller, with alloca.) | |
3366 | INSN is the insn that sets it. | |
3367 | BENEFIT estimates the savings from deleting this insn. | |
3368 | TYPE is DEST_REG or DEST_ADDR; it says whether the giv is computed | |
3369 | into a register or is used as a memory address. | |
3370 | ||
3371 | SRC_REGNO is the biv reg number which the giv is computed from. | |
3372 | DEST_REGNO is the giv's reg number (if the giv is stored in a reg). | |
3373 | MULT_VAL and ADD_VAL are the coefficients used to compute the giv. | |
3374 | FORCES and FORCES2, if nonzero, are other `struct induction's for | |
3375 | other givs which are used to compute this giv indirectly. | |
3376 | LOCATION points to the place where this giv's value appears in INSN. */ | |
3377 | ||
3378 | static void | |
3379 | record_giv (v, insn, src_regno, dest_regno, mult_val, add_val, benefit, | |
3380 | forces, forces2, type, maybe_never, location, loop_end) | |
3381 | struct induction *v; | |
3382 | rtx insn; | |
3383 | int src_regno, dest_regno; | |
3384 | rtx mult_val, add_val; | |
3385 | int benefit; | |
3386 | struct induction *forces, *forces2; | |
3387 | enum g_types type; | |
3388 | int maybe_never; | |
3389 | rtx *location; | |
3390 | rtx loop_end; | |
3391 | { | |
3392 | struct induction *b; | |
3393 | struct iv_class *bl; | |
3394 | ||
3395 | v->insn = insn; | |
3396 | v->src_regno = src_regno; | |
3397 | v->giv_type = type; | |
3398 | v->dest_regno = dest_regno; | |
3399 | v->mult_val = mult_val; | |
3400 | v->add_val = add_val; | |
3401 | v->benefit = benefit; | |
3402 | v->location = location; | |
3403 | ||
3404 | if (type == DEST_ADDR) | |
3405 | { | |
3406 | v->mode = GET_MODE (*location); | |
3407 | v->consec = 0; | |
3408 | v->lifetime = 1; | |
3409 | v->times_used = 1; | |
3410 | } | |
3411 | else /* type == DEST_REG */ | |
3412 | { | |
3413 | v->mode = GET_MODE (SET_DEST (PATTERN (insn))); | |
3414 | v->consec = n_times_set[dest_regno] - 1; | |
3415 | v->lifetime = (uid_luid[regno_last_uid[dest_regno]] | |
3416 | - uid_luid[regno_first_uid[dest_regno]]); | |
3417 | v->times_used = n_times_used[dest_regno]; | |
3418 | } | |
3419 | ||
3420 | v->same = 0; | |
3421 | v->forces = 0; | |
3422 | v->forces2 = 0; | |
3423 | v->ignore = 0; | |
3424 | v->new_reg = 0; | |
3425 | ||
3426 | /* Mark giv as forced if it is only used to compute another giv. */ | |
3427 | ||
3428 | /* This check is not sufficient as INSN may have been moved giving | |
3429 | it a new uid, so make another check by calculating lifetimes. | |
3430 | This is overconservative but seems to be correct. */ | |
3431 | ||
3432 | if (forces) | |
3433 | { | |
3434 | v->benefit += forces->benefit; | |
3435 | if ((regno_last_uid[forces->dest_regno] == INSN_UID (insn) | |
3436 | || | |
3437 | ((uid_luid[regno_last_uid[forces->dest_regno]] | |
3438 | - uid_luid[regno_first_uid[forces->dest_regno]]) | |
3439 | == (INSN_LUID (insn) - INSN_LUID (forces->insn)))) | |
3440 | && !reg_used_between_p (SET_DEST (PATTERN (forces->insn)), | |
3441 | forces->insn, insn)) | |
3442 | { | |
3443 | v->forces = forces; | |
3444 | forces->ignore = 1; | |
3445 | } | |
3446 | } | |
3447 | ||
3448 | if (forces2) | |
3449 | { | |
3450 | v->benefit += forces2->benefit; | |
3451 | if ((regno_last_uid[forces2->dest_regno] == INSN_UID (insn) | |
3452 | || | |
3453 | ((uid_luid[regno_last_uid[forces2->dest_regno]] | |
3454 | - uid_luid[regno_first_uid[forces2->dest_regno]]) | |
3455 | == (INSN_LUID (insn) - INSN_LUID (forces2->insn)))) | |
3456 | && !reg_used_between_p (SET_DEST (PATTERN (forces2->insn)), | |
3457 | forces2->insn, insn)) | |
3458 | { | |
3459 | if (v->forces) | |
3460 | v->forces2 = forces2; | |
3461 | else | |
3462 | v->forces = forces2; | |
3463 | forces2->ignore = 1; | |
3464 | } | |
3465 | } | |
3466 | ||
3467 | if (type == DEST_REG) | |
3468 | { | |
3469 | induct_var[dest_regno] = GENERAL_INDUCT; | |
3470 | induct_struct[dest_regno] = v; | |
3471 | } | |
3472 | ||
3473 | /* Add the giv to the class of givs computed from one biv. */ | |
3474 | ||
3475 | bl = class_struct[src_regno]; | |
3476 | if (bl) | |
3477 | { | |
3478 | v->family = bl->giv; | |
3479 | bl->giv = v; | |
3480 | /* Don't count DEST_ADDR. This is supposed to count the number of | |
3481 | insns that calculate givs. */ | |
3482 | if (type == DEST_REG) | |
3483 | bl->giv_count++; | |
3484 | bl->total_benefit += benefit; | |
3485 | } | |
3486 | else | |
3487 | /* Fatal error, biv missing for this giv? */ | |
3488 | abort (); | |
3489 | ||
3490 | if (type == DEST_ADDR) | |
3491 | v->replaceable = 1; | |
3492 | else | |
3493 | { | |
3494 | /* The giv can be replaced outright by the reduced register if | |
3495 | - the insn that sets the giv is always executed on any iteration | |
3496 | on which the giv is used at all | |
3497 | (there are two ways to deduce this: | |
3498 | either the insn is executed on every iteration, | |
3499 | or all uses follow that insn in the same basic block), | |
3500 | - the giv is not used before the insn that sets it, | |
3501 | i.e. no definition outside loop reaches into loop | |
3502 | - no assignments to the biv occur during the giv's lifetime. */ | |
3503 | ||
3504 | /* Is this right? Don't we need to make sure the giv is not used | |
3505 | outside the loop. Someday we will know where all the loop exits | |
3506 | are so we can do better, but until then.... | |
3507 | March 18, 1989 -- self@bayes.arc.nasa.gov */ | |
3508 | ||
3509 | if (regno_first_uid[dest_regno] == INSN_UID (insn) | |
3510 | /* Previous line always fails if INSN was moved by loop opt. */ | |
3511 | && uid_luid[regno_last_uid[dest_regno]] < INSN_LUID (loop_end) | |
3512 | && (!maybe_never || last_use_this_basic_block (dest_regno, insn))) | |
3513 | { | |
3514 | v->replaceable = 1; | |
3515 | for (b = bl->biv; b; b = b->family) | |
3516 | { | |
3517 | if ((uid_luid[INSN_UID (b->insn)] >= uid_luid[regno_first_uid[dest_regno]]) | |
3518 | && | |
3519 | (uid_luid[INSN_UID (b->insn)] | |
3520 | <= uid_luid[regno_last_uid[dest_regno]])) | |
3521 | { | |
3522 | v->replaceable = 0; | |
3523 | break; | |
3524 | } | |
3525 | } | |
3526 | } | |
3527 | else | |
3528 | v->replaceable = 0; | |
3529 | } | |
3530 | ||
3531 | if (loop_dump_stream) | |
3532 | { | |
3533 | if (type == DEST_REG) | |
3534 | fprintf (loop_dump_stream, "Insn %d: giv reg %d", | |
3535 | INSN_UID (insn), dest_regno); | |
3536 | else | |
3537 | fprintf (loop_dump_stream, "Insn %d: dest address", | |
3538 | INSN_UID (insn)); | |
3539 | ||
3540 | fprintf (loop_dump_stream, " src reg %d benefit %d", | |
3541 | src_regno, v->benefit); | |
3542 | fprintf (loop_dump_stream, " used %d lifetime %d", | |
3543 | v->times_used, v->lifetime); | |
3544 | ||
3545 | if (v->replaceable) | |
3546 | fprintf (loop_dump_stream, " replaceable"); | |
3547 | ||
3548 | if (GET_CODE (mult_val) == CONST_INT) | |
3549 | fprintf (loop_dump_stream, " mult %d", | |
3550 | INTVAL (mult_val)); | |
3551 | else | |
3552 | { | |
3553 | fprintf (loop_dump_stream, " mult "); | |
3554 | print_rtl (loop_dump_stream, mult_val); | |
3555 | } | |
3556 | ||
3557 | if (GET_CODE (add_val) == CONST_INT) | |
3558 | fprintf (loop_dump_stream, " add %d", | |
3559 | INTVAL (add_val)); | |
3560 | else | |
3561 | { | |
3562 | fprintf (loop_dump_stream, " add "); | |
3563 | print_rtl (loop_dump_stream, add_val); | |
3564 | } | |
3565 | } | |
3566 | ||
3567 | if (loop_dump_stream && v->forces) | |
3568 | fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces->insn)); | |
3569 | if (loop_dump_stream && v->forces2) | |
3570 | fprintf (loop_dump_stream, " forces insn %d", INSN_UID (v->forces2->insn)); | |
3571 | if (loop_dump_stream && v->consec) | |
3572 | fprintf (loop_dump_stream, " consec %d", v->consec); | |
3573 | if (loop_dump_stream) | |
3574 | fprintf (loop_dump_stream, "\n"); | |
3575 | } | |
3576 | \f | |
3577 | /* Delete the insns forced by the insn described by V. | |
3578 | If THIS_TOO is nonzero, delete that insn itself as well. */ | |
3579 | ||
3580 | static void | |
3581 | delete_insn_forces (v, this_too) | |
3582 | struct induction *v; | |
3583 | int this_too; | |
3584 | { | |
3585 | rtx x, p; | |
3586 | int count; | |
3587 | rtx insn; | |
3588 | ||
3589 | if (this_too) | |
3590 | { | |
3591 | insn = v->insn; | |
3592 | for (count = v->consec; count >= 0; count--) | |
3593 | { | |
3594 | /* If first insn of libcall sequence, skip to end. */ | |
3595 | /* Do this at start of loop, since p is guaranteed to | |
3596 | be an insn here. */ | |
3597 | if (x = find_reg_note (insn, REG_LIBCALL, 0)) | |
3598 | insn = XEXP (x, 0); | |
3599 | ||
3600 | if (x = find_reg_note (insn, REG_RETVAL, 0)) | |
3601 | { | |
3602 | /* This is a library call; delete all insns backward until get to | |
3603 | first insn in this group. */ | |
3604 | rtx first = XEXP (x, 0); | |
3605 | for (p = insn; p != first; p = PREV_INSN (p)) | |
3606 | delete_insn (p); | |
3607 | /* Delete first insn also. */ | |
3608 | delete_insn (p); | |
3609 | } | |
3610 | else | |
3611 | delete_insn (insn); | |
3612 | ||
3613 | do insn = NEXT_INSN (insn); | |
3614 | while (GET_CODE (insn) == NOTE); | |
3615 | } | |
3616 | } | |
3617 | ||
3618 | if (v->forces) | |
3619 | delete_insn_forces (v->forces, 1); | |
3620 | if (v->forces2) | |
3621 | delete_insn_forces (v->forces2, 1); | |
3622 | } | |
3623 | \f | |
3624 | /* Check whether an insn is an increment legitimate for a basic induction var. | |
3625 | X is the source of the insn. | |
3626 | DEST_REG is the putative biv, also the destination of the insn. | |
3627 | We accept patterns of these forms: | |
3628 | REG = REG + INVARIANT | |
3629 | REG = INVARIANT + REG | |
3630 | REG = REG - CONSTANT | |
3631 | ||
3632 | If X is suitable, we return 1, | |
3633 | and store the factor multiplying REF in X into *MULT_VAL | |
3634 | and the additive term into *INC_VAL. | |
3635 | Otherwise we return 0. */ | |
3636 | ||
3637 | static int | |
3638 | basic_induction_var (x, dest_regno, inc_val, mult_val) | |
3639 | register rtx x; | |
3640 | int dest_regno; | |
3641 | rtx *inc_val; | |
3642 | rtx *mult_val; | |
3643 | { | |
3644 | register enum rtx_code code; | |
3645 | rtx arg; | |
3646 | ||
3647 | if (x == 0) | |
3648 | return 0; | |
3649 | code = GET_CODE (x); | |
3650 | switch (code) | |
3651 | { | |
3652 | case PLUS: | |
3653 | if (GET_CODE (XEXP (x, 0)) == REG | |
3654 | && REGNO (XEXP (x, 0)) == dest_regno) | |
3655 | arg = XEXP (x, 1); | |
3656 | else if (GET_CODE (XEXP (x, 1)) == REG | |
3657 | && REGNO (XEXP (x, 1)) == dest_regno) | |
3658 | arg = XEXP (x, 0); | |
3659 | else | |
3660 | return 0; | |
3661 | ||
3662 | if (invariant_p (arg) == 1) | |
3663 | *inc_val = arg; | |
3664 | else | |
3665 | return 0; | |
3666 | ||
3667 | *mult_val = const1_rtx; | |
3668 | return 1; | |
3669 | ||
3670 | case MINUS: | |
3671 | if (GET_CODE (XEXP (x, 0)) == REG | |
3672 | && REGNO (XEXP (x, 0)) == dest_regno | |
3673 | && GET_CODE (XEXP (x, 1)) == CONST_INT) | |
3674 | *inc_val = gen_rtx (CONST_INT, VOIDmode, | |
3675 | - INTVAL (XEXP (x, 1))); | |
3676 | else | |
3677 | return 0; | |
3678 | *mult_val = const1_rtx; | |
3679 | return 1; | |
3680 | ||
3681 | /* Can accept constant setting of biv only when inside inner most loop. | |
3682 | Otherwise, a biv of an inner loop may be incorrectly recognized | |
3683 | as a biv of the outer loop, | |
3684 | causing code to be moved INTO the inner loop. */ | |
3685 | case REG: | |
3686 | if (!invariant_p (x)) | |
3687 | return 0; | |
3688 | case CONST_INT: | |
3689 | case SYMBOL_REF: | |
3690 | case CONST: | |
3691 | if (loops_enclosed == 1) | |
3692 | { | |
3693 | *inc_val = x; | |
3694 | *mult_val = const0_rtx; | |
3695 | return 1; | |
3696 | } | |
3697 | else | |
3698 | return 0; | |
3699 | ||
3700 | default: | |
3701 | return 0; | |
3702 | } | |
3703 | } | |
3704 | \f | |
3705 | /* A general induction variable (giv) is any quantity that is a linear function | |
3706 | of a basic induction variable, i.e. giv = biv * mult_val + add_val. | |
3707 | The coefficients can be any loop invariant quantity. | |
3708 | A giv need not be computed directly from the biv; | |
3709 | it can be computed by way of other givs. */ | |
3710 | ||
3711 | /* Determine whether X computes a giv. | |
3712 | If it does, return a nonzero value | |
3713 | which is the benefit from eliminating the computation of X; | |
3714 | set *SRC_REGNO to the register number of the biv that it is computed from; | |
3715 | set *ADD_VAL and *MULT_VAL to the coefficients, | |
3716 | such that the value of X is biv * mult + add; | |
3717 | set forces (and forces2) to identify any other givs that are used | |
3718 | solely to compute this one. */ | |
3719 | ||
3720 | /* This routine recognizes four types of patterns that generate givs: | |
3721 | - giv = biv op invariant v = 0, g = 0 | |
3722 | - giv1 = giv2 op invariant v = 0, g = giv2 | |
3723 | where giv1 and giv2 are functions of the same biv | |
3724 | - giv1 = biv op giv2 v = giv2, g = 0 | |
3725 | where giv2 is a function of biv | |
3726 | - giv1 = giv2 op giv3 v = giv3, g = giv2 | |
3727 | where giv2 and giv3 are functions of the save biv */ | |
3728 | ||
3729 | static int | |
3730 | general_induction_var (x, src_regno, add_val, mult_val, forces, forces2) | |
3731 | rtx x; | |
3732 | int *src_regno; | |
3733 | rtx *add_val; | |
3734 | rtx *mult_val; | |
3735 | struct induction **forces; | |
3736 | struct induction **forces2; | |
3737 | { | |
3738 | register enum rtx_code code; | |
3739 | rtx arg; | |
3740 | struct induction *g = 0; | |
3741 | struct induction *v = 0; | |
3742 | int subexp = 0; | |
3743 | int tem; | |
3744 | ||
3745 | if (x == 0) | |
3746 | return 0; | |
3747 | ||
3748 | code = GET_CODE (x); | |
3749 | switch (code) | |
3750 | { | |
3751 | case NEG: | |
3752 | /* This can generate givs also, but it is not handled. */ | |
3753 | return 0; | |
3754 | ||
3755 | case MULT: | |
3756 | case UMULT: | |
3757 | /* Reject widening multiply in version 1. | |
3758 | That is safer than trying to handle it. */ | |
3759 | { | |
3760 | enum machine_mode m0 = GET_MODE (XEXP (x, 0)); | |
3761 | enum machine_mode m1 = GET_MODE (XEXP (x, 1)); | |
3762 | if (m0 != VOIDmode && m0 != GET_MODE (x)) | |
3763 | return 0; | |
3764 | if (m1 != VOIDmode && m1 != GET_MODE (x)) | |
3765 | return 0; | |
3766 | } | |
3767 | case PLUS: | |
3768 | case MINUS: | |
3769 | /* Result is linear in both operands. */ | |
3770 | /* Determine which operand is the biv, and put the other in ARG. */ | |
3771 | if (GET_CODE (XEXP (x, 0)) == REG | |
3772 | && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) | |
3773 | { | |
3774 | *src_regno = REGNO (XEXP (x, 0)); | |
3775 | arg = XEXP (x, 1); | |
3776 | ||
3777 | } | |
3778 | else if (GET_CODE (XEXP (x, 1)) == REG | |
3779 | && induct_var[REGNO (XEXP (x, 1))] == BASIC_INDUCT) | |
3780 | { | |
3781 | *src_regno = REGNO (XEXP (x, 1)); | |
3782 | arg = XEXP (x, 0); | |
3783 | ||
3784 | } | |
3785 | /* Check for an rtl subexpression that is a giv. Memory address | |
3786 | givs often look like (plus (reg) (mult (biv) (const))). */ | |
3787 | /* Do this before checking for a giv operand, as this function will | |
3788 | fail if this special operand is not recognized. */ | |
3789 | #ifndef DONT_REDUCE_ADDR | |
3790 | else if (tem = general_induction_var (XEXP (x, 1), src_regno, | |
3791 | add_val, mult_val, | |
3792 | forces, forces2) | |
3793 | && code != MINUS) | |
3794 | { | |
3795 | /* Set subexp true so that this can be handled a little | |
3796 | differently from the normal case of g set. */ | |
3797 | /* Note that SRC_REGNO is already set. */ | |
3798 | subexp = TRUE; | |
3799 | g = (struct induction *) alloca (sizeof (struct induction)); | |
3800 | g->mult_val = *mult_val; | |
3801 | g->add_val = *add_val; | |
3802 | /* Fake out the test below. */ | |
3803 | g->replaceable = 1; | |
3804 | /* Count this multiply as a shift, since that's what it | |
3805 | really will do. */ | |
3806 | if (tem == MULT_BENEFIT) | |
3807 | g->benefit = SHIFT_BENEFIT; | |
3808 | else | |
3809 | g->benefit = tem; | |
3810 | arg = XEXP (x, 0); | |
3811 | } | |
3812 | else if (tem = general_induction_var (XEXP (x, 0), src_regno, | |
3813 | add_val, mult_val, | |
3814 | forces, forces2)) | |
3815 | { | |
3816 | /* Set subexp true so that this can be handled a little | |
3817 | differently from the normal case of g set. */ | |
3818 | /* Note that SRC_REGNO is already set. */ | |
3819 | subexp = TRUE; | |
3820 | g = (struct induction *) alloca (sizeof (struct induction)); | |
3821 | g->mult_val = *mult_val; | |
3822 | g->add_val = *add_val; | |
3823 | /* Fake out the test below. */ | |
3824 | g->replaceable = 1; | |
3825 | /* Count this multiply as a shift, since that's what it | |
3826 | really will do. */ | |
3827 | if (tem == MULT_BENEFIT) | |
3828 | g->benefit = SHIFT_BENEFIT; | |
3829 | else | |
3830 | g->benefit = tem; | |
3831 | arg = XEXP (x, 1); | |
3832 | } | |
3833 | #endif | |
3834 | /* Also allow general induction variables. | |
3835 | Could have a mult followed by an add (i.e. an address calculation), | |
3836 | thereby generating two related general induction variables | |
3837 | of which only the second is actually used. */ | |
3838 | /* Do this after checking both args for basic induction variables. */ | |
3839 | else if (GET_CODE (XEXP (x, 0)) == REG | |
3840 | && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) | |
3841 | { | |
3842 | g = induct_struct[REGNO (XEXP (x, 0))]; | |
3843 | *src_regno = g->src_regno; | |
3844 | arg = XEXP (x, 1); | |
3845 | } | |
3846 | else if (GET_CODE (XEXP (x, 1)) == REG | |
3847 | && induct_var[REGNO (XEXP (x, 1))] == GENERAL_INDUCT | |
3848 | && code != MINUS) | |
3849 | { | |
3850 | g = induct_struct[REGNO (XEXP (x, 1))]; | |
3851 | *src_regno = g->src_regno; | |
3852 | arg = XEXP (x, 0); | |
3853 | } | |
3854 | else | |
3855 | return 0; | |
3856 | ||
3857 | /* Overall form of expression looks good. */ | |
3858 | break; | |
3859 | ||
3860 | /* Could handle these also. */ | |
3861 | case DIV: | |
3862 | case UDIV: | |
3863 | /* For a 68020 could handle these? */ | |
3864 | case LSHIFT: | |
3865 | case ASHIFT: | |
3866 | case ASHIFTRT: | |
3867 | case LSHIFTRT: | |
3868 | /* These operations are linear only in first operand. | |
3869 | Check for a biv or giv there; if found, put other operand in ARG. */ | |
3870 | if (GET_CODE (XEXP (x, 0)) == REG | |
3871 | && induct_var[REGNO (XEXP (x, 0))] == BASIC_INDUCT) | |
3872 | { | |
3873 | *src_regno = REGNO (XEXP (x, 0)); | |
3874 | arg = XEXP (x, 1); | |
3875 | } | |
3876 | /* Also allow general induction variable. */ | |
3877 | else if (GET_CODE (XEXP (x, 0)) == REG | |
3878 | && induct_var[REGNO (XEXP (x, 0))] == GENERAL_INDUCT) | |
3879 | { | |
3880 | g = induct_struct[REGNO (XEXP (x, 0))]; | |
3881 | *src_regno = g->src_regno; | |
3882 | arg = XEXP (x, 1); | |
3883 | } | |
3884 | else | |
3885 | return 0; | |
3886 | ||
3887 | /* Overall form of expression looks good. */ | |
3888 | break; | |
3889 | ||
3890 | default: | |
3891 | return 0; | |
3892 | } | |
3893 | ||
3894 | /* ARG is the operand that is NOT a biv or giv. | |
3895 | Test it for superficial validity. */ | |
3896 | ||
3897 | /* This is just a special case of invariant values, | |
3898 | it is not really needed, but it's a shortcut. */ | |
3899 | if (GET_CODE (arg) == CONST_INT) | |
3900 | ; | |
3901 | ||
3902 | /* Depends on previous general induction variable, which has | |
3903 | the same basic induction variable */ | |
3904 | /* This code detects mults that have been generated as shift and add. */ | |
3905 | else if (GET_CODE (arg) == REG | |
3906 | && induct_var[REGNO (arg)] == GENERAL_INDUCT | |
3907 | && induct_struct[REGNO (arg)]->src_regno == *src_regno) | |
3908 | { | |
3909 | v = induct_struct[REGNO (arg)]; | |
3910 | /* Dependence indicated by forces, sort of kludgey. */ | |
3911 | } | |
3912 | ||
3913 | /* Invariant expression, could be a constant-valued register. */ | |
3914 | else if (invariant_p (arg) == 1) | |
3915 | ; | |
3916 | ||
3917 | /* Failure */ | |
3918 | else | |
3919 | return 0; | |
3920 | ||
3921 | /* Until we can do the correct thing, suppress use of nonreplaceable givs | |
3922 | as sources for other givs. */ | |
3923 | if ((g && ! g->replaceable) | |
3924 | || (v && ! v->replaceable)) | |
3925 | return 0; | |
3926 | ||
3927 | /* Now we know looks like a giv; extract the coefficients. | |
3928 | We can still fail if the coefficients are not what we can handle. */ | |
3929 | ||
3930 | /* Only succeed if result mult_val and add_val are only one level of rtl, | |
3931 | for example, (NEG:SI (REG:SI 34)) is not accepted. | |
3932 | This mainly causes problems with the MINUS code. */ | |
3933 | ||
3934 | switch (code) | |
3935 | { | |
3936 | case PLUS: | |
3937 | if (v && g) | |
3938 | { | |
3939 | if (GET_CODE (g->mult_val) == CONST_INT) | |
3940 | { | |
3941 | if (g->mult_val == const0_rtx) | |
3942 | *mult_val = v->mult_val; | |
3943 | else if (GET_CODE (v->mult_val) == CONST_INT) | |
3944 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
3945 | INTVAL (g->mult_val) | |
3946 | + INTVAL (v->mult_val)); | |
3947 | else | |
3948 | return 0; | |
3949 | } | |
3950 | else if (v->mult_val == const0_rtx) | |
3951 | *mult_val = g->mult_val; | |
3952 | else | |
3953 | return 0; | |
3954 | ||
3955 | if (GET_CODE (g->add_val) == CONST_INT) | |
3956 | { | |
3957 | if (g->add_val == const0_rtx) | |
3958 | *add_val = v->add_val; | |
3959 | else if (GET_CODE (v->add_val) == CONST_INT) | |
3960 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
3961 | INTVAL (g->add_val) | |
3962 | + INTVAL (v->add_val)); | |
3963 | else | |
3964 | return 0; | |
3965 | } | |
3966 | else if (v->add_val == const0_rtx) | |
3967 | *add_val = g->add_val; | |
3968 | else | |
3969 | return 0; | |
3970 | ||
3971 | if (subexp) | |
3972 | { | |
3973 | /* g deleted when return, can't return pointer to it */ | |
3974 | if (*forces2 == 0) | |
3975 | *forces2 = v; | |
3976 | return ADD_BENEFIT + g->benefit; | |
3977 | } | |
3978 | else | |
3979 | { | |
3980 | *forces = g; | |
3981 | *forces2 = v; | |
3982 | return ADD_BENEFIT; | |
3983 | } | |
3984 | } | |
3985 | else if (v) | |
3986 | { | |
3987 | if (GET_CODE (v->mult_val) == CONST_INT) | |
3988 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
3989 | INTVAL (v->mult_val) + 1); | |
3990 | else | |
3991 | return 0; | |
3992 | *add_val = v->add_val; | |
3993 | *forces = v; | |
3994 | return ADD_BENEFIT; | |
3995 | } | |
3996 | else if (g) | |
3997 | { | |
3998 | *mult_val = g->mult_val; | |
3999 | if (GET_CODE (g->add_val) == CONST_INT | |
4000 | && nonmemory_operand (arg, GET_MODE (arg))) | |
4001 | *add_val = plus_constant (arg, INTVAL (g->add_val)); | |
4002 | else if (GET_CODE (arg) == CONST_INT | |
4003 | && nonmemory_operand (g->add_val, GET_MODE (g->add_val))) | |
4004 | *add_val = plus_constant (g->add_val, INTVAL (arg)); | |
4005 | else | |
4006 | /* Could succeed if arg == 0, but that will never occur. */ | |
4007 | return 0; | |
4008 | ||
4009 | if (subexp) | |
4010 | /* g deleted when return, can't return pointer to it */ | |
4011 | return ADD_BENEFIT + g->benefit; | |
4012 | else | |
4013 | { | |
4014 | *forces = g; | |
4015 | return ADD_BENEFIT; | |
4016 | } | |
4017 | } | |
4018 | else | |
4019 | { | |
4020 | *mult_val = const1_rtx; | |
4021 | *add_val = arg; | |
4022 | return ADD_BENEFIT; | |
4023 | } | |
4024 | ||
4025 | /* Takes a lot of code and will rarely succeed. */ | |
4026 | case MINUS: | |
4027 | if (v && g) | |
4028 | { | |
4029 | /* G is the first argument of MINUS. */ | |
4030 | ||
4031 | if (GET_CODE (g->mult_val) == CONST_INT) | |
4032 | { | |
4033 | if (g->mult_val == const0_rtx) | |
4034 | #if 0 /* Should not have to fail here */ | |
4035 | *mult_val = gen_rtx (NEG, SImode, v->mult_val); | |
4036 | #endif | |
4037 | return 0; | |
4038 | else if (GET_CODE (v->mult_val) == CONST_INT) | |
4039 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4040 | INTVAL (g->mult_val) | |
4041 | - INTVAL (v->mult_val)); | |
4042 | else | |
4043 | return 0; | |
4044 | } | |
4045 | else if (v->mult_val == const0_rtx) | |
4046 | *mult_val = g->mult_val; | |
4047 | else | |
4048 | return 0; | |
4049 | ||
4050 | if (GET_CODE (g->add_val) == CONST_INT) | |
4051 | { | |
4052 | if (g->add_val == const0_rtx) | |
4053 | #if 0 /* should not have to fail here */ | |
4054 | *add_val = v->add_val; | |
4055 | #endif | |
4056 | return 0; | |
4057 | else if (GET_CODE (v->add_val) == CONST_INT) | |
4058 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4059 | INTVAL (g->add_val) | |
4060 | - INTVAL (v->add_val)); | |
4061 | else | |
4062 | return 0; | |
4063 | } | |
4064 | else if (v->add_val == const0_rtx) | |
4065 | *add_val = g->add_val; | |
4066 | else | |
4067 | return 0; | |
4068 | ||
4069 | if (subexp) | |
4070 | { | |
4071 | /* G deleted when return, can't return pointer to it */ | |
4072 | if (*forces2 == 0) | |
4073 | *forces2 = v; | |
4074 | return ADD_BENEFIT + g->benefit; | |
4075 | } | |
4076 | else | |
4077 | { | |
4078 | *forces = g; | |
4079 | *forces2 = v; | |
4080 | return ADD_BENEFIT; | |
4081 | } | |
4082 | } | |
4083 | else if (v) | |
4084 | { | |
4085 | if (GET_CODE (v->mult_val) != CONST_INT) | |
4086 | return 0; | |
4087 | if (arg == XEXP (x, 0)) /* giv1 = giv2 - biv */ | |
4088 | { | |
4089 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4090 | INTVAL (v->mult_val) - 1); | |
4091 | *add_val = v->add_val; | |
4092 | } | |
4093 | else /* giv1 = biv - giv2 */ | |
4094 | { | |
4095 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4096 | 1 - INTVAL (v->mult_val)); | |
4097 | if (GET_CODE (v->add_val) == CONST_INT) | |
4098 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4099 | - INTVAL (v->add_val)); | |
4100 | else | |
4101 | return 0; | |
4102 | } | |
4103 | *forces = v; | |
4104 | return ADD_BENEFIT; | |
4105 | } | |
4106 | else if (g) | |
4107 | { | |
4108 | if (arg == XEXP (x, 1)) | |
4109 | *mult_val = g->mult_val; | |
4110 | else | |
4111 | { | |
4112 | if (GET_CODE (g->mult_val) == CONST_INT) | |
4113 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4114 | - INTVAL (g->mult_val)); | |
4115 | else | |
4116 | return 0; | |
4117 | } | |
4118 | if (GET_CODE (g->add_val) == CONST_INT) | |
4119 | { | |
4120 | if (g->add_val == const0_rtx) | |
4121 | { | |
4122 | if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ | |
4123 | { | |
4124 | /* Fail unless arg is a constant. */ | |
4125 | if (GET_CODE (arg) == CONST_INT) | |
4126 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4127 | -INTVAL (arg)); | |
4128 | else | |
4129 | return 0; | |
4130 | } | |
4131 | else /* giv1 = arg - giv2 */ | |
4132 | *add_val = arg; | |
4133 | } | |
4134 | else if (GET_CODE (arg) == CONST_INT) | |
4135 | { | |
4136 | if (arg == XEXP (x, 1)) /* giv1 = giv2 - arg */ | |
4137 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4138 | INTVAL (g->add_val) | |
4139 | - INTVAL (arg)); | |
4140 | else /* giv1 = arg - giv2 */ | |
4141 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4142 | INTVAL (arg), | |
4143 | - INTVAL (g->add_val)); | |
4144 | } | |
4145 | else | |
4146 | return 0; | |
4147 | } | |
4148 | else | |
4149 | /* Could succeed if arg == 0, but that will never occur. */ | |
4150 | return 0; | |
4151 | ||
4152 | if (subexp) | |
4153 | /* G deleted when return, can't return pointer to it. */ | |
4154 | return ADD_BENEFIT + g->benefit; | |
4155 | else | |
4156 | { | |
4157 | *forces = g; | |
4158 | return ADD_BENEFIT; | |
4159 | } | |
4160 | } | |
4161 | else if (GET_CODE (arg) == CONST_INT) | |
4162 | { | |
4163 | if (arg == XEXP (x, 1)) | |
4164 | { | |
4165 | *add_val = gen_rtx (CONST_INT, VOIDmode, - INTVAL (arg)); | |
4166 | *mult_val = const1_rtx; | |
4167 | } | |
4168 | else | |
4169 | { | |
4170 | *add_val = arg; | |
4171 | *mult_val = gen_rtx (CONST_INT, VOIDmode, -1); | |
4172 | } | |
4173 | return ADD_BENEFIT; | |
4174 | } | |
4175 | else | |
4176 | return 0; | |
4177 | ||
4178 | /* UMULT can be handled like MULT since C ignores overflows. */ | |
4179 | case MULT: | |
4180 | case UMULT: | |
4181 | if (v && g) | |
4182 | { | |
4183 | /* Quadratic term, just fail. */ | |
4184 | return 0; | |
4185 | } | |
4186 | else if (v) | |
4187 | { | |
4188 | /* Quadratic term, just fail. */ | |
4189 | return 0; | |
4190 | } | |
4191 | else if (g) | |
4192 | { | |
4193 | /* Takes a lot of code and will rarely succeed. */ | |
4194 | /* dest = m * arg * b + a * arg */ | |
4195 | if (GET_CODE (g->mult_val) == CONST_INT) | |
4196 | { | |
4197 | if (g->mult_val == const0_rtx) | |
4198 | *mult_val = const0_rtx; | |
4199 | else if (g->mult_val == const1_rtx) | |
4200 | *mult_val = arg; | |
4201 | else if (GET_CODE (arg) == CONST_INT) | |
4202 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4203 | INTVAL (g->mult_val) * INTVAL (arg)); | |
4204 | else | |
4205 | return 0; | |
4206 | } | |
4207 | else | |
4208 | /* Could suceed if arg == 1 or 0, but this will never occur. */ | |
4209 | return 0; | |
4210 | ||
4211 | if (GET_CODE (g->add_val) == CONST_INT) | |
4212 | { | |
4213 | if (g->add_val == const0_rtx) | |
4214 | *add_val = const0_rtx; | |
4215 | else if (g->add_val == const1_rtx) | |
4216 | *add_val = arg; | |
4217 | else if (GET_CODE (arg) == CONST_INT) | |
4218 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4219 | INTVAL (g->add_val) * INTVAL (arg)); | |
4220 | else | |
4221 | return 0; | |
4222 | } | |
4223 | else | |
4224 | /* Could suceed if arg == 1 or 0, but this will never occur. */ | |
4225 | return 0; | |
4226 | ||
4227 | if (subexp) | |
4228 | /* G deleted when return, can't return pointer to it. */ | |
4229 | return MULT_BENEFIT + g->benefit; | |
4230 | else | |
4231 | { | |
4232 | *forces = g; | |
4233 | return MULT_BENEFIT; | |
4234 | } | |
4235 | } | |
4236 | else | |
4237 | { | |
4238 | *mult_val = arg; | |
4239 | *add_val = const0_rtx; | |
4240 | return MULT_BENEFIT; | |
4241 | } | |
4242 | ||
4243 | /* These are not worth the trouble. */ | |
4244 | case DIV: | |
4245 | case UDIV: | |
4246 | return 0; | |
4247 | ||
4248 | /* Handle these, but only for left shift. */ | |
4249 | case LSHIFT: | |
4250 | case ASHIFT: | |
4251 | if (v && g) | |
4252 | { | |
4253 | /* Quadratic term, just fail. */ | |
4254 | return 0; | |
4255 | } | |
4256 | else if (v) | |
4257 | { | |
4258 | /* Quadratic term, just fail. */ | |
4259 | return 0; | |
4260 | } | |
4261 | else if (g) | |
4262 | { | |
4263 | /* Takes a lot of code and will rarely succeed. */ | |
4264 | /* dest = ((m * b) << arg) + (a << arg) */ | |
4265 | if (GET_CODE (g->mult_val) == CONST_INT) | |
4266 | { | |
4267 | if (g->mult_val == const0_rtx) | |
4268 | *mult_val = const0_rtx; | |
4269 | else if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) | |
4270 | *mult_val = gen_rtx (CONST_INT, VOIDmode, | |
4271 | INTVAL (g->mult_val) | |
4272 | * (1 << INTVAL (arg))); | |
4273 | else | |
4274 | return 0; | |
4275 | } | |
4276 | else | |
4277 | /* Could suceed if arg == 0, but this will never occur. */ | |
4278 | return 0; | |
4279 | ||
4280 | if (GET_CODE (g->add_val) == CONST_INT) | |
4281 | { | |
4282 | if (g->add_val == const0_rtx) | |
4283 | *add_val = const0_rtx; | |
4284 | else if (GET_CODE (arg) == CONST_INT) | |
4285 | *add_val = gen_rtx (CONST_INT, VOIDmode, | |
4286 | INTVAL (g->add_val) | |
4287 | * (1 << INTVAL (arg))); | |
4288 | else | |
4289 | return 0; | |
4290 | } | |
4291 | else | |
4292 | /* Could suceed if arg == 0, but this will never occur. */ | |
4293 | return 0; | |
4294 | ||
4295 | if (subexp) | |
4296 | /* G deleted when return, can't return pointer to it. */ | |
4297 | return SHIFT_BENEFIT + g->benefit; | |
4298 | else | |
4299 | { | |
4300 | *forces = g; | |
4301 | return SHIFT_BENEFIT; | |
4302 | } | |
4303 | } | |
4304 | ||
4305 | if (GET_CODE (arg) == CONST_INT && INTVAL (arg) >= 0) | |
4306 | *mult_val = gen_rtx (CONST_INT, VOIDmode, 1 << INTVAL (arg)); | |
4307 | else | |
4308 | return 0; | |
4309 | *add_val = const0_rtx; | |
4310 | return SHIFT_BENEFIT; | |
4311 | ||
4312 | /* These are not worth the trouble. */ | |
4313 | case ASHIFTRT: | |
4314 | case LSHIFTRT: | |
4315 | return 0; | |
4316 | ||
4317 | /* should never reach here */ | |
4318 | default: | |
4319 | abort (); | |
4320 | return 0; | |
4321 | } | |
4322 | } | |
4323 | \f | |
4324 | /* Help detect a giv that is calculated by several consecutive insns; | |
4325 | for example, | |
4326 | giv = biv * M | |
4327 | giv = giv + A | |
4328 | The caller has already identified the first insn P as having a giv as dest; | |
4329 | we check that all other insns that set the same register follow | |
4330 | immediately after P, that they alter nothing else, | |
4331 | and that the result of the last is still a giv. | |
4332 | ||
4333 | The value is 0 if the reg set in P is not really a giv. | |
4334 | Otherwise, the value is the amount gained by eliminating | |
4335 | all the consecutive insns that compute the value. | |
4336 | ||
4337 | FIRST_BENEFIT is the amount gained by eliminating the first insn, P. | |
4338 | SRC_REGNO is the regno of the biv; DEST_REGNO is that of the giv. | |
4339 | ||
4340 | The coefficients of the ultimate giv value are stored in | |
4341 | *MULT_VAL and *ADD_VAL. */ | |
4342 | ||
4343 | static int | |
4344 | consec_sets_giv (first_benefit, p, src_regno, dest_regno, | |
4345 | add_val, mult_val) | |
4346 | int first_benefit; | |
4347 | rtx p; | |
4348 | int src_regno; | |
4349 | int dest_regno; | |
4350 | rtx *add_val; | |
4351 | rtx *mult_val; | |
4352 | { | |
4353 | int count; | |
4354 | int benefit = first_benefit; | |
4355 | enum rtx_code code; | |
4356 | struct induction *forces, *forces2; | |
4357 | rtx temp; | |
4358 | int tem; | |
4359 | ||
4360 | /* Initialize info used by general_induction_var. */ | |
4361 | struct induction *v = | |
4362 | (struct induction *) oballoc (sizeof (struct induction)); | |
4363 | v->src_regno = src_regno; | |
4364 | v->mult_val = *mult_val; | |
4365 | v->add_val = *add_val; | |
4366 | ||
4367 | induct_var[dest_regno] = GENERAL_INDUCT; | |
4368 | induct_struct[dest_regno] = v; | |
4369 | ||
4370 | count = n_times_set[dest_regno] - 1; | |
4371 | ||
4372 | while (count > 0) | |
4373 | { | |
4374 | p = NEXT_INSN (p); | |
4375 | code = GET_CODE (p); | |
4376 | ||
4377 | /* If libcall, skip to end of call sequence. */ | |
4378 | if (code == INSN && (temp = find_reg_note (p, REG_LIBCALL, 0))) | |
4379 | p = XEXP (temp, 0); | |
4380 | ||
4381 | if (code == INSN && GET_CODE (PATTERN (p)) == SET | |
4382 | && GET_CODE (SET_DEST (PATTERN (p))) == REG | |
4383 | && REGNO (SET_DEST (PATTERN (p))) == dest_regno | |
4384 | && ((tem = general_induction_var (SET_SRC (PATTERN (p)), &src_regno, | |
4385 | add_val, mult_val, | |
4386 | &forces, &forces2)) | |
4387 | /* Giv created by call to library routine. */ | |
4388 | || ((temp = loop_find_reg_equal (p)) | |
4389 | && (tem = general_induction_var (XEXP (temp, 0), &src_regno, | |
4390 | add_val, mult_val, | |
4391 | &forces, &forces2)))) | |
4392 | && src_regno == v->src_regno) | |
4393 | { | |
4394 | count--; | |
4395 | benefit += tem; | |
4396 | v->mult_val = *mult_val; | |
4397 | v->add_val = *add_val; | |
4398 | } | |
4399 | else if (code != NOTE) | |
4400 | { | |
4401 | induct_var[dest_regno] = UNKNOWN_INDUCT; | |
4402 | return 0; | |
4403 | } | |
4404 | } | |
4405 | ||
4406 | return benefit; | |
4407 | } | |
4408 | \f | |
4409 | /* Generate a SEQUENCE to multiply OP0 and OP1 with result in TARGET. | |
4410 | Use expand_mult to "optimally" do the multiply. | |
4411 | This also works for machines that do not have multiply insns. | |
4412 | If one of the operands is a constant, it must be the second. */ | |
4413 | ||
4414 | static rtx | |
4415 | gen_iv_mult (mode, op0, op1, target) | |
4416 | enum machine_mode mode; | |
4417 | register rtx op0, op1, target; | |
4418 | { | |
4419 | extern rtx gen_sequence (); | |
4420 | extern rtx start_sequence (); | |
4421 | rtx saved, result, temp; | |
4422 | ||
4423 | saved = start_sequence (); | |
4424 | ||
4425 | /* ??? It is very unmodular to use expand_mult here! | |
4426 | This should be redesigned. */ | |
4427 | ||
4428 | /* UNSIGNEDP arg can be zero since operands/target always same width. */ | |
4429 | temp = expand_mult (mode, op0, op1, target, 0); | |
4430 | ||
4431 | /* Move to target register, if expand_mult did not put it there. */ | |
4432 | if (target != 0 && temp != target) | |
4433 | emit_move_insn (target, temp); | |
4434 | ||
4435 | result = gen_sequence (); | |
4436 | end_sequence (saved); | |
4437 | ||
4438 | return result; | |
4439 | } | |
4440 | ||
4441 | /* Emit code to initialize an induction variable created by strength | |
4442 | reduction. | |
4443 | More precisely, emit code before INSERT_BEFORE | |
4444 | to set REG = B * M + A. */ | |
4445 | ||
4446 | static void | |
4447 | emit_iv_init_code (b, m, a, reg, insert_before) | |
4448 | rtx b; /* initial value of basic induction variable */ | |
4449 | rtx m; /* multiplicative constant */ | |
4450 | rtx a; /* additive constant */ | |
4451 | rtx reg; /* destination register */ | |
4452 | rtx insert_before; | |
4453 | { | |
4454 | rtx seq; | |
4455 | rtx result; | |
4456 | ||
4457 | /* Prevent unexpected sharing of these rtx. */ | |
4458 | a = copy_rtx (a); | |
4459 | b = copy_rtx (b); | |
4460 | ||
4461 | start_sequence (); | |
4462 | result = expand_mult_add (b, m, a, GET_MODE (reg), 0); | |
4463 | if (reg != result) | |
4464 | emit_move_insn (reg, result); | |
4465 | seq = gen_sequence (); | |
4466 | end_sequence (); | |
4467 | ||
4468 | emit_insn_before (seq, insert_before); | |
4469 | } | |
4470 | ||
4471 | /* Emit code to increment the induction variable inside the loop. | |
4472 | Try to emit optimal code for the expression | |
4473 | REG = REG + BIV_ADD * GIV_MULT. */ | |
4474 | ||
4475 | static void | |
4476 | emit_iv_inc (biv_add, giv_mult, reg, insn) | |
4477 | rtx biv_add; /* increment value for biv */ | |
4478 | rtx giv_mult; /* multiply value of giv */ | |
4479 | rtx reg; /* create insn to set this reg */ | |
4480 | rtx insn; /* where to insert the new insn */ | |
4481 | { | |
4482 | emit_iv_init_code (biv_add, giv_mult, reg, reg, insn); | |
4483 | } | |
4484 | \f | |
4485 | /* Test whethen BIV_ADD * GIV_MULT can be computed without | |
4486 | an actual multiply insn. Value is 1 if so. */ | |
4487 | ||
4488 | static int | |
4489 | product_cheap_p (biv_add, giv_mult) | |
4490 | rtx biv_add; | |
4491 | rtx giv_mult; | |
4492 | { | |
4493 | /* Indicates which of MULT/ADD are constants. */ | |
4494 | int status = 0; | |
4495 | int const_val; | |
4496 | rtx tmp; | |
4497 | ||
4498 | if (GET_CODE (biv_add) == CONST_INT) | |
4499 | status |= 0x1; | |
4500 | if (GET_CODE (giv_mult) == CONST_INT) | |
4501 | status |= 0x2; | |
4502 | ||
4503 | switch (status) | |
4504 | { | |
4505 | case 0: | |
4506 | /* Neither is constant: would need a multiply insn, so fail. */ | |
4507 | return 0; | |
4508 | ||
4509 | case 1: | |
4510 | /* BIV_ADD value is constant */ | |
4511 | /* Equivalent to state 2, just switch values of BIV_ADD and GIV_MULT | |
4512 | and fall through. */ | |
4513 | tmp = biv_add; | |
4514 | biv_add = giv_mult; | |
4515 | giv_mult = tmp; | |
4516 | ||
4517 | case 2: | |
4518 | /* GIV_MULT value is constant. | |
4519 | If it is 1, 0 or -1 then we win. */ | |
4520 | const_val = INTVAL (giv_mult); | |
4521 | if (const_val < -1 || const_val > 1) | |
4522 | { | |
4523 | tmp = gen_iv_mult (GET_MODE (biv_add), biv_add, giv_mult, 0); | |
4524 | /* Don't emit a multiply insn, just fail instead. */ | |
4525 | if ((GET_CODE (tmp) == SET && GET_CODE (SET_SRC (tmp)) == MULT) | |
4526 | /* Also fail if library call (which generates more | |
4527 | then two insn) is needed. */ | |
4528 | || (GET_CODE (tmp) == SEQUENCE && XVECLEN (tmp, 0) > 2)) | |
4529 | return 0; | |
4530 | } | |
4531 | return 1; | |
4532 | ||
4533 | case 3: | |
4534 | /* Both BIV_ADD and GIV_MULT are constant; | |
4535 | can compute the product at compile time. */ | |
4536 | return 1; | |
4537 | ||
4538 | default: | |
4539 | abort (); | |
4540 | } | |
4541 | } | |
4542 | ||
4543 | \f | |
4544 | /* Check to see if loop can be terminated by a "decrement and branch until | |
4545 | zero" instruction. If so, add a REG_NONNEG note to the branch insn if so. | |
4546 | Also try reversing an increment loop to a decrement loop | |
4547 | to see if the optimization can be performed. | |
4548 | Value is nonzero if optimization was performed. */ | |
4549 | ||
4550 | static int | |
4551 | check_dbra_loop (loop_end, iv_list, insn_count, loop_start) | |
4552 | rtx loop_end; | |
4553 | struct iv_class *iv_list; | |
4554 | int insn_count; | |
4555 | rtx loop_start; | |
4556 | { | |
4557 | struct iv_class *bl; | |
4558 | rtx reg; | |
4559 | rtx jump_label; | |
4560 | rtx final_value; | |
4561 | rtx start_value; | |
4562 | enum rtx_code branch_code; | |
4563 | rtx new_add_val; | |
4564 | rtx tested_before_loop = 0; | |
4565 | rtx p; | |
4566 | ||
4567 | /* See if the loop is contained in `if (X >= 0)' for some reg X. | |
4568 | If so, then we know X is initially nonnegative even though | |
4569 | we don't know its initial value. | |
4570 | Record X in TESTED_BEFORE_LOOP. */ | |
4571 | ||
4572 | for (p = loop_start; p != 0; p = PREV_INSN (p)) | |
4573 | if (GET_CODE (p) != NOTE) | |
4574 | break; | |
4575 | ||
4576 | /* See if a conditional branch preceeds the loop. | |
4577 | There may be no other insns or labels between it and | |
4578 | the beginning of the loop. */ | |
4579 | if (p != 0 && GET_CODE (p) == JUMP_INSN && condjump_p (p) | |
4580 | && SET_SRC (PATTERN (p)) != pc_rtx | |
4581 | && ((GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == LT | |
4582 | && XEXP (SET_SRC (PATTERN (p)), 2) == pc_rtx) | |
4583 | || | |
4584 | (GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == GE | |
4585 | && XEXP (SET_SRC (PATTERN (p)), 1) == pc_rtx)) | |
4586 | && next_real_insn (JUMP_LABEL (p)) == next_real_insn (loop_end)) | |
4587 | { | |
4588 | /* Before the branch should be a test or compare. | |
4589 | See if we are comparing something against zero. */ | |
4590 | p = PREV_INSN (p); | |
4591 | if (GET_CODE (p) == INSN && GET_CODE (PATTERN (p)) == SET | |
4592 | && SET_DEST (PATTERN (p)) == cc0_rtx) | |
4593 | { | |
4594 | if (GET_CODE (SET_SRC (PATTERN (p))) == REG) | |
4595 | tested_before_loop = SET_SRC (PATTERN (p)); | |
4596 | else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE | |
4597 | && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 0)) == REG | |
4598 | && XEXP (SET_SRC (PATTERN (p)), 1) == const0_rtx) | |
4599 | tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 0); | |
4600 | else if (GET_CODE (SET_SRC (PATTERN (p))) == COMPARE | |
4601 | && GET_CODE (XEXP (SET_SRC (PATTERN (p)), 1)) == REG | |
4602 | && XEXP (SET_SRC (PATTERN (p)), 0) == const0_rtx) | |
4603 | tested_before_loop = XEXP (SET_SRC (PATTERN (p)), 1); | |
4604 | } | |
4605 | } | |
4606 | ||
4607 | /* If last insn is a conditional branch, and the insn before tests a register | |
4608 | value, then try to optimize it. */ | |
4609 | ||
4610 | if (GET_CODE (PREV_INSN (loop_end)) == JUMP_INSN | |
4611 | && GET_CODE (PATTERN (PREV_INSN (loop_end))) == SET | |
4612 | && GET_CODE (SET_SRC (PATTERN (PREV_INSN (loop_end)))) == IF_THEN_ELSE | |
4613 | && GET_CODE (PREV_INSN (PREV_INSN (loop_end))) == INSN | |
4614 | && GET_CODE (PATTERN (PREV_INSN (PREV_INSN (loop_end)))) == SET | |
4615 | && (GET_CODE (SET_DEST (PATTERN (PREV_INSN (PREV_INSN (loop_end))))) == | |
4616 | CC0)) | |
4617 | { | |
4618 | /* Check all of the bivs to see if the compare uses one of them. */ | |
4619 | ||
4620 | for (bl = iv_list; bl; bl = bl->next) | |
4621 | { | |
4622 | if (reg_mentioned_p (SET_DEST (PATTERN (bl->biv->insn)), | |
4623 | PREV_INSN (PREV_INSN (loop_end)))) | |
4624 | break; | |
4625 | } | |
4626 | ||
4627 | /* If biv set more than once, then give up. | |
4628 | We can't guarantee that it will be zero on the last iteration. | |
4629 | Also give up if the biv is used between its update and the test | |
4630 | insn. */ | |
4631 | if (bl && bl->biv_count == 1 | |
4632 | && ! reg_used_between_p (regno_reg_rtx[bl->regno], bl->biv->insn, | |
4633 | PREV_INSN (PREV_INSN (loop_end)))) | |
4634 | { | |
4635 | /* Look for the case where the basic induction variable is always | |
4636 | nonnegative, and equals zero on the last iteration. | |
4637 | In this case, add a reg_note REG_NONNEG, which allows the | |
4638 | m68k DBRA instruction to be used. */ | |
4639 | ||
4640 | /* the decrement case */ | |
4641 | ||
4642 | if (GET_CODE (bl->biv->add_val) == CONST_INT | |
4643 | && INTVAL (bl->biv->add_val) < 0) | |
4644 | { | |
4645 | /* Initial value must be greater than 0, | |
4646 | init_val % -dec_value == 0 to ensure that it equals zero on | |
4647 | the last iteration */ | |
4648 | ||
4649 | if (GET_CODE (bl->initial_value) == CONST_INT | |
4650 | && INTVAL (bl->initial_value) > 0 | |
4651 | && (INTVAL (bl->initial_value) % | |
4652 | (-INTVAL (bl->biv->add_val))) == 0) | |
4653 | { | |
4654 | /* register always nonnegative, add REG_NOTE to branch */ | |
4655 | REG_NOTES (PREV_INSN (loop_end)) | |
4656 | = gen_rtx (EXPR_LIST, REG_NONNEG, 0, | |
4657 | REG_NOTES (PREV_INSN (loop_end))); | |
4658 | bl->nonneg = 1; | |
4659 | ||
4660 | return 1; | |
4661 | } | |
4662 | ||
4663 | /* If the decrement is 1 and the value was tested as >= 0 before | |
4664 | the loop, then we can safely optimize. */ | |
4665 | if (SET_DEST (PATTERN (bl->biv->insn)) == tested_before_loop | |
4666 | && INTVAL (bl->biv->add_val) == -1) | |
4667 | { | |
4668 | REG_NOTES (PREV_INSN (loop_end)) | |
4669 | = gen_rtx (EXPR_LIST, REG_NONNEG, 0, | |
4670 | REG_NOTES (PREV_INSN (loop_end))); | |
4671 | bl->nonneg = 1; | |
4672 | ||
4673 | return 1; | |
4674 | } | |
4675 | } | |
4676 | else if (num_mem_sets <= 1) | |
4677 | { | |
4678 | /* Try to change inc to dec, so can apply above optimization. */ | |
4679 | /* Can do this if: | |
4680 | all registers modified are induction variables or invariant, | |
4681 | all memory references have non-overlapping addresses | |
4682 | (obviously true if only one write) | |
4683 | allow 2 insns for the compare/jump at the end of the loop. */ | |
4684 | int num_nonfixed_reads = 0; | |
4685 | rtx p; | |
4686 | ||
4687 | for (p = loop_start; p != loop_end; p = NEXT_INSN (p)) | |
4688 | if (GET_CODE (p) == INSN || GET_CODE (p) == CALL_INSN | |
4689 | || GET_CODE (p) == JUMP_INSN) | |
4690 | num_nonfixed_reads += count_nonfixed_reads (PATTERN (p)); | |
4691 | ||
4692 | /* This code only acts for innermost loops. Also it simplifies | |
4693 | the memory address check by only reversing loops with | |
4694 | zero or one memory access. | |
4695 | Two memory accesses could involve parts of the same array, | |
4696 | and that can't be reversed. */ | |
4697 | ||
4698 | if (num_nonfixed_reads <= 1 | |
4699 | && !loop_has_call | |
4700 | && (bl->giv_count + bl->biv_count + num_mem_sets | |
4701 | + num_movables + 2 == insn_count)) | |
4702 | { | |
4703 | rtx src_two_before_end; | |
4704 | int constant; | |
4705 | int win; | |
4706 | ||
4707 | /* Loop can be reversed. */ | |
4708 | if (loop_dump_stream) | |
4709 | fprintf (loop_dump_stream, "Can reverse loop\n"); | |
4710 | ||
4711 | /* Now check other conditions: | |
4712 | initial_value must be zero, | |
4713 | final_value % add_val == 0, so that when reversed, the | |
4714 | biv will be zero on the last iteration. */ | |
4715 | ||
4716 | /* Calculating the final value non trivial. | |
4717 | If branch is (LT (CC0) (CONST 0), | |
4718 | then value in compare is final value. | |
4719 | If branch is (LE (CC0) (CONST 0), | |
4720 | then value in compare is final_value - add_val */ | |
4721 | ||
4722 | branch_code | |
4723 | = GET_CODE (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0)); | |
4724 | src_two_before_end | |
4725 | = SET_SRC (PATTERN (PREV_INSN (PREV_INSN (loop_end)))); | |
4726 | ||
4727 | win = 1; | |
4728 | if (GET_CODE (src_two_before_end) == REG) | |
4729 | constant = 0; | |
4730 | else if (GET_CODE (src_two_before_end) == COMPARE | |
4731 | && GET_CODE (XEXP (src_two_before_end, 1)) == CONST_INT) | |
4732 | constant = INTVAL (XEXP (src_two_before_end, 1)); | |
4733 | else | |
4734 | win = 0; | |
4735 | ||
4736 | if (win && bl->initial_value == const0_rtx | |
4737 | && (branch_code == LT || branch_code == LE) | |
4738 | && XEXP (XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 0), 1) == const0_rtx | |
4739 | && (constant % INTVAL (bl->biv->add_val)) == 0) | |
4740 | { | |
4741 | /* Register will always be nonnegative, with value | |
4742 | 0 on last iteration if loop reversed */ | |
4743 | ||
4744 | /* Save some info needed to produce the new insns. */ | |
4745 | reg = SET_DEST (PATTERN (bl->biv->insn)); | |
4746 | jump_label = XEXP (SET_SRC (PATTERN (PREV_INSN (loop_end))), 1); | |
4747 | new_add_val = gen_rtx (CONST_INT, VOIDmode, | |
4748 | - INTVAL (bl->biv->add_val)); | |
4749 | ||
4750 | ||
4751 | if (branch_code == LT) | |
4752 | { | |
4753 | final_value | |
4754 | = gen_rtx (CONST_INT, VOIDmode, constant); | |
4755 | start_value | |
4756 | = gen_rtx (CONST_INT, VOIDmode, | |
4757 | (constant - INTVAL (bl->biv->add_val))); | |
4758 | } | |
4759 | else /* branch_code == LE */ | |
4760 | { | |
4761 | start_value | |
4762 | = gen_rtx (CONST_INT, VOIDmode, constant); | |
4763 | final_value | |
4764 | = gen_rtx (CONST_INT, VOIDmode, | |
4765 | (constant + INTVAL (bl->biv->add_val))); | |
4766 | } | |
4767 | ||
4768 | /* Initialize biv to start_value before loop start. | |
4769 | The old initializing insn will be deleted as a | |
4770 | dead store by flow.c. */ | |
4771 | emit_insn_before (gen_rtx (SET, VOIDmode, reg, | |
4772 | start_value), | |
4773 | loop_start); | |
4774 | ||
4775 | /* Add insn to decrement register, and delete insn | |
4776 | that incremented the register. */ | |
4777 | emit_insn_before (gen_rtx (SET, VOIDmode, reg, | |
4778 | gen_rtx (PLUS, GET_MODE (reg), reg, | |
4779 | new_add_val)), | |
4780 | bl->biv->insn); | |
4781 | /* Update biv info to reflect its new status. */ | |
4782 | bl->biv->insn = PREV_INSN (bl->biv->insn); | |
4783 | delete_insn (NEXT_INSN (bl->biv->insn)); | |
4784 | ||
4785 | /* Inc LABEL_NUSES so that delete_insn will | |
4786 | not delete the label. */ | |
4787 | LABEL_NUSES (XEXP (jump_label, 0)) ++; | |
4788 | ||
4789 | if (regno_last_uid[bl->regno] != INSN_UID (PREV_INSN (loop_end))) | |
4790 | emit_insn_after (gen_rtx (SET, VOIDmode, reg, | |
4791 | final_value), | |
4792 | loop_end); | |
4793 | ||
4794 | /* Delete compare/branch at end of loop. */ | |
4795 | delete_insn (PREV_INSN (loop_end)); | |
4796 | delete_insn (PREV_INSN (loop_end)); | |
4797 | ||
4798 | /* Add new compare/branch insn at end of loop. */ | |
4799 | emit_insn_before (gen_rtx (SET, VOIDmode, cc0_rtx, reg), | |
4800 | loop_end); | |
4801 | emit_jump_insn_before (gen_rtx (SET, VOIDmode, pc_rtx, | |
4802 | gen_rtx (IF_THEN_ELSE, VOIDmode, | |
4803 | gen_rtx (GE, VOIDmode, cc0_rtx, | |
4804 | const0_rtx), | |
4805 | jump_label, | |
4806 | pc_rtx)), | |
4807 | loop_end); | |
4808 | ||
4809 | JUMP_LABEL (PREV_INSN (loop_end)) = XEXP (jump_label, 0); | |
4810 | /* Increment of LABEL_NUSES done above. */ | |
4811 | ||
4812 | /* Register is now always nonnegative, | |
4813 | so add REG_NONNEG note to the branch. */ | |
4814 | REG_NOTES (PREV_INSN (loop_end)) | |
4815 | = gen_rtx (EXPR_LIST, REG_NONNEG, 0, | |
4816 | REG_NOTES (PREV_INSN (loop_end))); | |
4817 | bl->nonneg = 1; | |
4818 | ||
4819 | /* Update rest of biv info. */ | |
4820 | bl->initial_value = start_value; | |
4821 | bl->biv->add_val = new_add_val; | |
4822 | ||
4823 | if (loop_dump_stream) | |
4824 | fprintf (loop_dump_stream, "Reversed loop and added reg_nonneg\n"); | |
4825 | ||
4826 | return 1; | |
4827 | } | |
4828 | } | |
4829 | } | |
4830 | } | |
4831 | } | |
4832 | return 0; | |
4833 | } | |
4834 | \f | |
4835 | /* Verify whether the biv BL appears to be eliminable, | |
4836 | based on the insns in the loop that refer to it. | |
4837 | LOOP_START is the first insn of the loop, and END is the end insn. */ | |
4838 | ||
4839 | static void | |
4840 | check_eliminate_biv (bl, loop_start, end) | |
4841 | struct iv_class *bl; | |
4842 | rtx loop_start; | |
4843 | rtx end; | |
4844 | { | |
4845 | /* Get the REG rtx for the biv. */ | |
4846 | rtx reg = SET_DEST (PATTERN (bl->biv->insn)); | |
4847 | rtx p; | |
4848 | struct induction *v; | |
4849 | ||
4850 | bl->eliminable = 0; | |
4851 | ||
4852 | for (p = loop_start; p != end; p = NEXT_INSN (p)) | |
4853 | { | |
4854 | enum rtx_code code = GET_CODE (p); | |
4855 | if ((code == INSN || code == JUMP_INSN || code == CALL_INSN) | |
4856 | && reg_mentioned_p (reg, PATTERN (p))) | |
4857 | { | |
4858 | /* This insn uses the biv. If we can't understand it, | |
4859 | then we can't eliminate the biv. */ | |
4860 | if (GET_CODE (PATTERN (p)) != SET) | |
4861 | { | |
4862 | if (loop_dump_stream) | |
4863 | fprintf (loop_dump_stream, | |
4864 | "Cannot eliminate biv %d: cannot understand insn %d.\n", | |
4865 | bl->regno, INSN_UID (p)); | |
4866 | break; | |
4867 | } | |
4868 | ||
4869 | /* The insns that increment the biv are no problem. */ | |
4870 | if (SET_DEST (PATTERN (p)) == reg) | |
4871 | continue; | |
4872 | ||
4873 | /* If this is an insn which uses the biv ONLY in the | |
4874 | calculation of a giv which is in the family of this | |
4875 | biv, it's ok becuase it will go away when the giv is | |
4876 | reduced. March 14, 1989 -- self@bayes.arc.nasa.gov */ | |
4877 | for (v = bl->giv; v; v = v->family) | |
4878 | if (v->insn == p) | |
4879 | { | |
4880 | if (v->giv_type == DEST_REG | |
4881 | || (v->giv_type == DEST_ADDR | |
4882 | && ! other_reg_use_p (reg, *(v->location), | |
4883 | PATTERN (p)))) | |
4884 | break; | |
4885 | } | |
4886 | if (v) | |
4887 | continue; | |
4888 | ||
4889 | /* If can rewrite this insn not to use the biv, it's ok. */ | |
4890 | if (can_eliminate_biv_p (p, bl)) | |
4891 | continue; | |
4892 | ||
4893 | /* Biv is used in a way we cannot eliminate. */ | |
4894 | if (loop_dump_stream) | |
4895 | fprintf (loop_dump_stream, | |
4896 | "Cannot eliminate biv %d: biv used in insn %d.\n", | |
4897 | bl->regno, INSN_UID (p)); | |
4898 | break; | |
4899 | } | |
4900 | } | |
4901 | ||
4902 | if (p == end) | |
4903 | { | |
4904 | bl->eliminable = 1; | |
4905 | if (loop_dump_stream) | |
4906 | fprintf (loop_dump_stream, "Can eliminate biv %d.\n", | |
4907 | bl->regno); | |
4908 | } | |
4909 | } | |
4910 | \f | |
4911 | /* Return 1 if INSN, a compare insn which tests the biv described by BL, | |
4912 | can be rewritten to use instead some reduced giv related to that biv. | |
4913 | Does not change the rtl. | |
4914 | ||
4915 | We make the assumption that all the givs depending on this biv | |
4916 | will be reduced, since only in that case will an attempt to eliminate | |
4917 | the biv actually be made. | |
4918 | ||
4919 | The following function is very parallel to this one. */ | |
4920 | ||
4921 | static int | |
4922 | can_eliminate_biv_p (insn, bl) | |
4923 | rtx insn; | |
4924 | struct iv_class *bl; | |
4925 | { | |
4926 | rtx src; | |
4927 | enum rtx_code code; | |
4928 | struct induction *v, *tv; | |
4929 | rtx arg; | |
4930 | int arg_operand; | |
4931 | /* Mode of this biv. */ | |
4932 | enum machine_mode mode = bl->biv->mode; | |
4933 | ||
4934 | if (SET_DEST (PATTERN (insn)) != cc0_rtx) | |
4935 | return 0; | |
4936 | ||
4937 | src = SET_SRC (PATTERN (insn)); | |
4938 | code = GET_CODE (src); | |
4939 | ||
4940 | switch (code) | |
4941 | { | |
4942 | /* a test insn */ | |
4943 | case REG: | |
4944 | /* Can replace with any giv that has (MULT_VAL != 0) and (ADD_VAL == 0) | |
4945 | Require a constant integer for MULT_VAL, so we know it's nonzero. */ | |
4946 | ||
4947 | for (v = bl->giv; v; v = v->family) | |
4948 | if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx | |
4949 | && v->add_val == const0_rtx | |
4950 | && ! v->ignore | |
4951 | && v->mode == mode) | |
4952 | return 1; | |
4953 | ||
4954 | /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0) | |
4955 | where ADD_VAL is a constant or a register; | |
4956 | can replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). | |
4957 | Require a constant integer for MULT_VAL, so we know it's nonzero. */ | |
4958 | ||
4959 | for (v = bl->giv; v; v = v->family) | |
4960 | if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx | |
4961 | && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT) | |
4962 | && ! v->ignore | |
4963 | && v->mode == mode) | |
4964 | return 1; | |
4965 | ||
4966 | if (loop_dump_stream) | |
4967 | fprintf (loop_dump_stream, "Cannot eliminate biv %d in test insn %d: no appropriate giv.\n", | |
4968 | bl->regno, INSN_UID (insn)); | |
4969 | ||
4970 | return 0; | |
4971 | ||
4972 | /* a compare insn */ | |
4973 | case COMPARE: | |
4974 | /* Figure out which operand is the biv. */ | |
4975 | if ((GET_CODE (XEXP (src, 0)) == REG) | |
4976 | && (REGNO (XEXP (src, 0)) == bl->regno)) | |
4977 | { | |
4978 | arg = XEXP (src, 1); | |
4979 | arg_operand = 1; | |
4980 | } | |
4981 | else if ((GET_CODE (XEXP (src, 1)) == REG) | |
4982 | && (REGNO (XEXP (src, 1)) == bl->regno)) | |
4983 | { | |
4984 | arg = XEXP (src, 0); | |
4985 | arg_operand = 0; | |
4986 | } | |
4987 | else | |
4988 | return 0; | |
4989 | ||
4990 | if (GET_CODE (arg) == CONST_INT) | |
4991 | { | |
4992 | /* Can replace with any giv that has constant coefficients. */ | |
4993 | ||
4994 | for (v = bl->giv; v; v = v->family) | |
4995 | if (GET_CODE (v->mult_val) == CONST_INT | |
4996 | && GET_CODE (v->add_val) == CONST_INT | |
4997 | && ! v->ignore | |
4998 | && v->mode == mode) | |
4999 | return 1; | |
5000 | ||
5001 | /* Look for giv with constant mult_val and nonconst add_val, | |
5002 | since we can insert add insn before loop | |
5003 | to calculate new compare value. */ | |
5004 | ||
5005 | for (v = bl->giv; v; v = v->family) | |
5006 | if (GET_CODE (v->mult_val) == CONST_INT | |
5007 | && ! v->ignore | |
5008 | && v->mode == mode) | |
5009 | return 1; | |
5010 | } | |
5011 | else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) | |
5012 | { | |
5013 | /* Comparing against invariant register or memref can be handled. */ | |
5014 | ||
5015 | if (invariant_p (arg)) | |
5016 | { | |
5017 | /* Look for giv with constant mult_val and nonconst add_val. | |
5018 | Insert add-insn before loop to compute new compare value. */ | |
5019 | ||
5020 | for (v = bl->giv; v; v = v->family) | |
5021 | if ((GET_CODE (v->mult_val) == CONST_INT) | |
5022 | && ! v->ignore | |
5023 | && v->mode == mode) | |
5024 | return 1; | |
5025 | } | |
5026 | ||
5027 | /* Otherwise, only comparing against a biv can be handled. */ | |
5028 | if (GET_CODE (arg) != REG | |
5029 | || induct_var[REGNO (arg)] != BASIC_INDUCT) | |
5030 | return 0; | |
5031 | ||
5032 | /* Look for a giv for each biv that have identical | |
5033 | values for mult_val and add_val. */ | |
5034 | for (v = bl->giv; v; v = v->family) | |
5035 | if (v->mode == mode | |
5036 | && ! v->ignore) | |
5037 | { | |
5038 | for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) | |
5039 | if ((tv->new_reg != 0) | |
5040 | && rtx_equal_p (tv->mult_val, v->mult_val) | |
5041 | && rtx_equal_p (tv->mult_val, v->mult_val) | |
5042 | && ! tv->ignore | |
5043 | && tv->mode == mode) | |
5044 | return 1; | |
5045 | } | |
5046 | } | |
5047 | return 0; | |
5048 | ||
5049 | default: | |
5050 | return 0; | |
5051 | } | |
5052 | } | |
5053 | \f | |
5054 | /* Rewrite a compare insn INSN which uses the biv described by BL | |
5055 | so that it doesn't use that biv any more. | |
5056 | Instead it will use some reduced giv related to that biv. | |
5057 | ||
5058 | The preceding function is very parallel to this one. */ | |
5059 | ||
5060 | static void | |
5061 | eliminate_biv (insn, bl, loop_start) | |
5062 | rtx insn; | |
5063 | struct iv_class *bl; | |
5064 | rtx loop_start; | |
5065 | { | |
5066 | rtx src = SET_SRC (PATTERN (insn)); | |
5067 | enum rtx_code code = GET_CODE (src); | |
5068 | struct induction *v, *tv; | |
5069 | rtx arg, temp; | |
5070 | int arg_operand; | |
5071 | /* Mode of this biv. */ | |
5072 | enum machine_mode mode = bl->biv->mode; | |
5073 | ||
5074 | switch (code) | |
5075 | { | |
5076 | /* a test insn */ | |
5077 | case REG: | |
5078 | /* Can replace with any giv that was reduced and | |
5079 | that has (MULT_VAL != 0) and (ADD_VAL == 0). | |
5080 | Require a constant integer for MULT_VAL, so we know it's nonzero. */ | |
5081 | ||
5082 | for (v = bl->giv; v; v = v->family) | |
5083 | if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx | |
5084 | && v->add_val == const0_rtx | |
5085 | && v->new_reg != 0 | |
5086 | && v->mode == mode) | |
5087 | break; | |
5088 | if (v) | |
5089 | { | |
5090 | /* We can test the sign of that giv's reduced reg. */ | |
5091 | SET_SRC (PATTERN (insn)) = v->new_reg; | |
5092 | /* If the giv has the opposite direction of change, | |
5093 | then reverse the comparison. */ | |
5094 | if (INTVAL (v->mult_val) < 0) | |
5095 | SET_SRC (PATTERN (insn)) | |
5096 | = gen_rtx (COMPARE, GET_MODE (v->new_reg), | |
5097 | const0_rtx, v->new_reg); | |
5098 | return; | |
5099 | } | |
5100 | ||
5101 | /* Look for a giv with (MULT_VAL != 0) and (ADD_VAL != 0) | |
5102 | where ADD_VAL is a constant or a register; | |
5103 | replace test insn with a compare insn (cmp REDUCED_GIV ADD_VAL). | |
5104 | Require a constant integer for MULT_VAL, so we know it's nonzero. */ | |
5105 | ||
5106 | for (v = bl->giv; v; v = v->family) | |
5107 | if (GET_CODE (v->mult_val) == CONST_INT && v->mult_val != const0_rtx | |
5108 | && (GET_CODE (v->add_val) == REG || GET_CODE (v->add_val) == CONST_INT) | |
5109 | && v->new_reg != 0 | |
5110 | && v->mode == mode) | |
5111 | break; | |
5112 | if (v) | |
5113 | { | |
5114 | /* Replace biv with the giv's reduced register. */ | |
5115 | SET_SRC (PATTERN (insn)) = gen_rtx (COMPARE, GET_MODE (v->new_reg), | |
5116 | v->new_reg, | |
5117 | copy_rtx (v->add_val)); | |
5118 | ||
5119 | /* If the giv has the opposite direction of change, | |
5120 | then reverse the comparison. */ | |
5121 | if (INTVAL (v->mult_val) < 0) | |
5122 | { | |
5123 | XEXP (SET_SRC (PATTERN (insn)), 0) | |
5124 | = XEXP (SET_SRC (PATTERN (insn)), 1); | |
5125 | XEXP (SET_SRC (PATTERN (insn)), 1) = v->new_reg; | |
5126 | } | |
5127 | #if 0 | |
5128 | /* add_val must be invariant, so don't bother storing in a register */ | |
5129 | /* calculate the appropriate constant to compare against */ | |
5130 | emit_insn_before (gen_rtx (SET, VOIDmode, compare_value, | |
5131 | copy_rtx (v->add_val)), | |
5132 | loop_start); | |
5133 | #endif | |
5134 | return; | |
5135 | } | |
5136 | abort (); | |
5137 | break; | |
5138 | ||
5139 | /* a compare insn */ | |
5140 | case COMPARE: | |
5141 | /* Figure out which operand is the biv. */ | |
5142 | if (GET_CODE (XEXP (src, 0)) == REG | |
5143 | && REGNO (XEXP (src, 0)) == bl->regno) | |
5144 | { | |
5145 | arg = XEXP (src, 1); | |
5146 | arg_operand = 1; | |
5147 | } | |
5148 | else if (GET_CODE (XEXP (src, 1)) == REG | |
5149 | && REGNO (XEXP (src, 1)) == bl->regno) | |
5150 | { | |
5151 | arg = XEXP (src, 0); | |
5152 | arg_operand = 0; | |
5153 | } | |
5154 | else | |
5155 | abort (); | |
5156 | ||
5157 | if (GET_CODE (arg) == CONST_INT) | |
5158 | { | |
5159 | /* Can replace with any giv that has constant mult_val and add_val. | |
5160 | Make sure it was strength reduced by checking new_reg != 0. */ | |
5161 | ||
5162 | for (v = bl->giv; v; v = v->family) | |
5163 | if (GET_CODE (v->mult_val) == CONST_INT | |
5164 | && GET_CODE (v->add_val) == CONST_INT | |
5165 | && v->new_reg | |
5166 | && v->mode == mode) | |
5167 | break; | |
5168 | if (v) | |
5169 | { | |
5170 | rtx newval; | |
5171 | /* Replace biv with the giv's reduced reg. */ | |
5172 | XEXP (src, 1-arg_operand) = v->new_reg; | |
5173 | /* Calculate the appropriate constant to compare against. */ | |
5174 | newval = gen_rtx (CONST_INT, VOIDmode, | |
5175 | (INTVAL (arg) * INTVAL (v->mult_val) | |
5176 | + INTVAL (v->add_val))); | |
5177 | XEXP (src, arg_operand) = newval; | |
5178 | /* If that constant is no good in a compare, | |
5179 | put it in a register. */ | |
5180 | if (recog (PATTERN (insn), insn) < 0) | |
5181 | { | |
5182 | temp = gen_reg_rtx (mode); | |
5183 | emit_iv_init_code (arg, v->mult_val, v->add_val, | |
5184 | temp, loop_start); | |
5185 | XEXP (src, arg_operand) = temp; | |
5186 | } | |
5187 | ||
5188 | /* If the giv has the opposite direction of change, | |
5189 | then reverse the comparison. */ | |
5190 | if (INTVAL (v->mult_val) < 0) | |
5191 | { | |
5192 | temp = XEXP (src, 0); | |
5193 | XEXP (src, 0) = XEXP (src, 1); | |
5194 | XEXP (src, 1) = temp; | |
5195 | } | |
5196 | return; | |
5197 | } | |
5198 | ||
5199 | /* Look for giv with constant mult_val and nonconst add_val. | |
5200 | Insert add insn before loop to calculate new compare value. */ | |
5201 | ||
5202 | for (v = bl->giv; v; v = v->family) | |
5203 | if (GET_CODE (v->mult_val) == CONST_INT | |
5204 | && v->new_reg | |
5205 | && v->mode == mode) | |
5206 | break; | |
5207 | if (v) | |
5208 | { | |
5209 | rtx compare_value = gen_reg_rtx (mode); | |
5210 | ||
5211 | /* Replace biv with giv's reduced register. */ | |
5212 | XEXP (src, 1-arg_operand) = v->new_reg; | |
5213 | ||
5214 | /* At start of loop, compute value to compare against. */ | |
5215 | emit_iv_init_code (arg, v->mult_val, v->add_val, | |
5216 | compare_value, loop_start); | |
5217 | /* Use it in this insn. */ | |
5218 | XEXP (src, arg_operand) = compare_value; | |
5219 | ||
5220 | /* If the giv has the opposite direction of change, | |
5221 | then reverse the comparison. */ | |
5222 | if (INTVAL (v->mult_val) < 0) | |
5223 | { | |
5224 | temp = XEXP (src, 0); | |
5225 | XEXP (src, 0) = XEXP (src, 1); | |
5226 | XEXP (src, 1) = temp; | |
5227 | } | |
5228 | return; | |
5229 | } | |
5230 | abort (); | |
5231 | } | |
5232 | else if (GET_CODE (arg) == REG || GET_CODE (arg) == MEM) | |
5233 | { | |
5234 | if (invariant_p (arg)) | |
5235 | { | |
5236 | /* Look for giv with constant mult_val and nonconst add_val. | |
5237 | Insert add-insn before loop to compute new compare value. */ | |
5238 | ||
5239 | for (v = bl->giv; v; v = v->family) | |
5240 | if (GET_CODE (v->mult_val) == CONST_INT | |
5241 | && v->new_reg | |
5242 | && v->mode == mode) | |
5243 | break; | |
5244 | if (v) | |
5245 | { | |
5246 | rtx compare_value = gen_reg_rtx (mode); | |
5247 | ||
5248 | /* Replace biv with giv's reduced register. */ | |
5249 | XEXP (src, 1-arg_operand) = v->new_reg; | |
5250 | ||
5251 | /* At start of loop, compute value to compare against. */ | |
5252 | emit_iv_init_code (arg, v->mult_val, v->add_val, | |
5253 | compare_value, loop_start); | |
5254 | XEXP (src, arg_operand) = compare_value; | |
5255 | ||
5256 | /* If the giv has the opposite direction of change, | |
5257 | then reverse the comparison. */ | |
5258 | if (INTVAL (v->mult_val) < 0) | |
5259 | { | |
5260 | temp = XEXP (src, 0); | |
5261 | XEXP (src, 0) = XEXP (src, 1); | |
5262 | XEXP (src, 1) = temp; | |
5263 | } | |
5264 | return; | |
5265 | } | |
5266 | } | |
5267 | ||
5268 | /* Otherwise the reg compared with had better be a biv. */ | |
5269 | if (GET_CODE (arg) != REG | |
5270 | || induct_var[REGNO (arg)] != BASIC_INDUCT) | |
5271 | abort (); | |
5272 | ||
5273 | /* Look for a pair of givs, one for each biv, | |
5274 | with identical coefficients. */ | |
5275 | for (v = bl->giv; v; v = v->family) | |
5276 | { | |
5277 | if (!v->new_reg && v->mode == mode) | |
5278 | continue; | |
5279 | for (tv = class_struct[REGNO (arg)]->giv; tv; tv = tv->family) | |
5280 | if ((tv->new_reg != 0) | |
5281 | && rtx_equal_p (tv->mult_val, v->mult_val) | |
5282 | && rtx_equal_p (tv->add_val, v->add_val) | |
5283 | && tv->mode == mode) | |
5284 | break; | |
5285 | if (tv) | |
5286 | break; | |
5287 | } | |
5288 | if (v) | |
5289 | { | |
5290 | /* Replace biv with its giv's reduced reg. */ | |
5291 | XEXP (src, 1-arg_operand) = v->new_reg; | |
5292 | /* Replace other operand with the other giv's reduced reg. */ | |
5293 | XEXP (src, arg_operand) = tv->new_reg; | |
5294 | ||
5295 | /* If the giv has the opposite direction of change, | |
5296 | then reverse the comparison. */ | |
5297 | if (INTVAL (v->mult_val) < 0) | |
5298 | { | |
5299 | temp = XEXP (src, 0); | |
5300 | XEXP (src, 0) = XEXP (src, 1); | |
5301 | XEXP (src, 1) = temp; | |
5302 | } | |
5303 | return; | |
5304 | } | |
5305 | } | |
5306 | abort (); | |
5307 | ||
5308 | default: | |
5309 | abort (); | |
5310 | } | |
5311 | } | |
5312 | \f | |
5313 | /* Try to calculate the final value of the biv, | |
5314 | the value it will have at the end of the loop. | |
5315 | If we can do it, return that value. */ | |
5316 | ||
5317 | /* ??? One case that should be simple to handle | |
5318 | is when the biv is incremented by an invariant | |
5319 | exactly once each time around the loop, | |
5320 | and when the number of iterations can be determined | |
5321 | (as the value of some invariant). | |
5322 | Then the final value would be BIV + (INCREMENT * NUM_ITERATIONS). | |
5323 | ||
5324 | Once that case is handled, it would become desirable to detect empty | |
5325 | loops and delete them, since this optimization could make empty loops. */ | |
5326 | ||
5327 | static rtx | |
5328 | final_biv_value (bl, loop_end) | |
5329 | struct iv_class *bl; | |
5330 | rtx loop_end; | |
5331 | { | |
5332 | /* wimpy, but guaranteed to work */ | |
5333 | return 0; | |
5334 | } | |
5335 | ||
5336 | /* Return nonzero if the last use of reg REGNO | |
5337 | is in an insn following INSN in the same basic block. */ | |
5338 | ||
5339 | static int | |
5340 | last_use_this_basic_block (regno, insn) | |
5341 | int regno; | |
5342 | rtx insn; | |
5343 | { | |
5344 | rtx n; | |
5345 | for (n = insn; | |
5346 | n && GET_CODE (n) != CODE_LABEL && GET_CODE (n) != JUMP_INSN; | |
5347 | n = NEXT_INSN (n)) | |
5348 | { | |
5349 | if (regno_last_uid[regno] == INSN_UID (n)) | |
5350 | return 1; | |
5351 | } | |
5352 | return 0; | |
5353 | } |