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