![[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:
6: GNU CC is distributed in the hope that it will be useful,
7: but WITHOUT ANY WARRANTY. No author or distributor
8: accepts responsibility to anyone for the consequences of using it
9: or for whether it serves any particular purpose or works at all,
10: unless he says so in writing. Refer to the GNU CC General Public
11: License for full details.
12:
13: Everyone is granted permission to copy, modify and redistribute
14: GNU CC, but only under the conditions described in the
15: GNU CC General Public License. A copy of this license is
16: supposed to have been given to you along with GNU CC so you
17: can know your rights and responsibilities. It should be in a
18: file named COPYING. Among other things, the copyright notice
19: and this notice must be preserved on all copies. */
20:
21:
22: /* This is the loop optimization pass of the compiler.
23: It finds invariant computations within loops and moves them
24: to the beginning of the loop.
25:
26: It also finds cases where
27: a register is set within the loop by zero-extending a narrower value
28: and changes these to zero the entire register once before the loop
29: and merely copy the low part within the loop.
30:
31: Most of the complexity is in heuristics to decide when it is worth
32: while to do these things. */
33:
34: /* ??? verify_loop would run faster if we made one table
35: of the minimum and maximum luids from which each label is reached.
36: Also, it would be faster if loop_store_addrs were a hash table. */
37:
38: #include "config.h"
39: #include "rtl.h"
40: #include "insn-config.h"
41: #include "regs.h"
42: #include "recog.h"
1.1.1.2 root 43: #include <stdio.h>
1.1 root 44:
45: /* Vector mapping INSN_UIDs to luids.
46: The luids are like uids but increase monononically always.
47: We use them to see whether a jump comes from outside a given loop. */
48:
49: static short *uid_luid;
50:
51: /* Get the luid of an insn. */
52:
53: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])
54:
55: /* 1 + largest uid of any insn. */
56:
57: static int max_uid;
58:
59: /* 1 + luid of last insn. */
60:
61: static int max_luid;
62:
63: /* Nonzero if somewhere in the current loop
64: there is either a subroutine call,
65: or a store into a memory address that is not fixed,
66: or a store in a BLKmode memory operand,
67: or too many different fixed addresses stored in
68: to record them all in `loop_store_addrs'.
69:
70: In any of these cases, no memory location can be regarded
71: as invariant. */
72:
73: static int unknown_address_altered;
74:
75: /* Nonzero if somewhere in the current loop there is a store
76: into a memory address that is not fixed but is known to be
77: part of an aggregate.
78:
79: In this case, no memory reference in an aggregate may be
80: considered invariant. */
81:
82: static int unknown_aggregate_altered;
83:
84: /* Nonzero if somewhere in the current loop there is a store
85: into a memory address other than a fixed address not in an aggregate.
86:
87: In this case, no memory reference in an aggregate at a varying address
88: may be considered invariant. */
89:
90: static int fixed_aggregate_altered;
91:
92: /* Nonzero if there is a subroutine call in the current loop.
93: (unknown_address_altered is also nonzero in this case.) */
94:
95: static int loop_has_call;
96:
97: /* Array of fixed memory addresses that are stored in this loop.
98: If there are too many to fit here,
99: we just turn on unknown_address_altered. */
100:
101: #define NUM_STORES 10
102: static rtx loop_store_addrs[NUM_STORES];
103: static int loop_store_widths[NUM_STORES];
104:
105: /* Index of first available slot in above array. */
106: static int loop_store_addrs_idx;
107:
108: /* During the analysis of a loop, a chain of `struct movable's
109: is made to record all the movable insns found.
110: Then the entire chain can be scanned to decide which to move. */
111:
112: struct movable
113: {
114: rtx insn; /* A movable insn */
1.1.1.2 root 115: int consec; /* Number of consecutive following insns
116: that must be moved with this one. */
1.1 root 117: int regno; /* The register it sets */
118: short lifetime; /* lifetime of that register;
119: may be adjusted when matching movables
120: that load the same value are found. */
1.1.1.2 root 121: short times_used; /* Number of times the register is used,
122: plus uses of related insns that could
123: be moved if this one is. */
1.1 root 124: unsigned int cond : 1; /* 1 if only conditionally movable */
125: unsigned int force : 1; /* 1 means MUST move this insn */
126: unsigned int global : 1; /* 1 means reg is live outside this loop */
1.1.1.2 root 127: unsigned int done : 1; /* 1 inhibits further processing of this */
128: unsigned int partial : 1; /* Moving this doesn't make it invariant. */
1.1 root 129: struct movable *match; /* First entry for same value */
130: struct movable *forces; /* An insn that must be moved if this is */
131: struct movable *next;
132: };
133:
1.1.1.2 root 134: static FILE *loop_dump_stream;
135:
1.1 root 136: static rtx verify_loop ();
137: static int invariant_p ();
1.1.1.4 ! root 138: static int consec_sets_invariant_p ();
1.1 root 139: static int can_jump_into_range_p ();
140: static void count_loop_regs_set ();
141: static void note_addr_stored ();
142: static int loop_reg_used_before_p ();
143: static void constant_high_bytes ();
144: static void scan_loop ();
145: static rtx replace_regs ();
1.1.1.2 root 146: static void move_movables ();
147: static int may_trap_p ();
1.1 root 148:
149: /* Entry point of this file. Perform loop optimization
150: on the current function. F is the first insn of the function
151: and NREGS is the number of register numbers used. */
152:
1.1.1.2 root 153: void
154: loop_optimize (f, nregs, dumpfile)
1.1 root 155: /* f is the first instruction of a chain of insns for one function */
156: rtx f;
157: /* nregs is the total number of registers used in it */
158: int nregs;
1.1.1.2 root 159: FILE *dumpfile;
1.1 root 160: {
161: register rtx insn;
162: register int i;
163: rtx end;
164: rtx last_insn;
165:
1.1.1.2 root 166: loop_dump_stream = dumpfile;
167:
1.1 root 168: init_recog ();
169:
170: /* First find the last real insn, and count the number of insns,
171: and assign insns their suids. */
172:
173: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
174: if (INSN_UID (insn) > i)
175: i = INSN_UID (insn);
176:
177: max_uid = i + 1;
178: uid_luid = (short *) alloca ((i + 1) * sizeof (short));
179: bzero (uid_luid, (i + 1) * sizeof (short));
180:
181: /* Compute the mapping from uids to luids.
182: LUIDs are numbers assigned to insns, like uids,
183: except that luids increase monotonically through the code. */
184:
185: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
186: {
187: last_insn = insn;
188: INSN_LUID (insn) = ++i;
189: }
190:
191: max_luid = i;
192:
193: /* Don't leave gaps in uid_luid for insns that have been
194: deleted. It is possible that the first or last insn
195: using some register has been deleted by cross-jumping.
196: Make sure that uid_luid for that former insn's uid
197: points to the general area where that insn used to be. */
198: for (i = 0; i < max_uid; i++)
1.1.1.2 root 199: {
200: uid_luid[0] = uid_luid[i];
201: if (uid_luid[0] != 0)
202: break;
203: }
204: for (i = 0; i < max_uid; i++)
1.1 root 205: if (uid_luid[i] == 0)
206: uid_luid[i] = uid_luid[i - 1];
207:
208: /* Find and process each loop.
209: We scan from the end, and process each loop when its start is seen,
210: so we process innermost loops first. */
211:
212: for (insn = last_insn; insn; insn = PREV_INSN (insn))
213: if (GET_CODE (insn) == NOTE
1.1.1.4 ! root 214: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
! 215: {
1.1 root 216: /* Make sure it really is a loop -- no jumps in from outside. */
1.1.1.4 ! root 217: end = verify_loop (f, insn);
! 218: if (end != 0)
! 219: /* If so, optimize this loop. */
! 220: scan_loop (insn, end, nregs);
! 221: else if (loop_dump_stream)
! 222: fprintf (loop_dump_stream,
! 223: "\nLoop at %d ignored due to multiple entry points.\n",
! 224: INSN_UID (insn));
! 225: }
1.1 root 226: }
227:
228: /* Optimize one loop whose start is LOOP_START and end is END.
229: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
230: NOTE_INSN_LOOP_END. */
231:
232: static void
233: scan_loop (loop_start, end, nregs)
234: rtx loop_start, end;
235: int nregs;
236: {
237: register int i;
238: register rtx p = NEXT_INSN (loop_start);
239: /* 1 if we are scanning insns that could be executed zero times. */
240: int maybe_never = 0;
1.1.1.3 root 241: /* 1 if we are scanning insns that might never be executed
242: due to a subroutine call which might exit before they are reached. */
243: int call_passed = 0;
1.1 root 244: /* For a rotated loop that is entered near the bottom,
245: this is the label at the top. Otherwise it is zero. */
246: rtx loop_top = 0;
1.1.1.2 root 247: /* This is the insn (whatever kind) before the NOTE that starts the loop.
248: Any insns moved out of the loop will follow it. */
249: rtx before_start = PREV_INSN (loop_start);
1.1 root 250: /* Jump insn that enters the loop, or 0 if control drops in. */
251: rtx loop_entry_jump = 0;
252: /* Place in the loop where control enters. */
253: rtx scan_start;
254: /* Number of insns in the loop. */
255: int insn_count;
256: int tem;
257: /* Indexed by register number, contains the number of times the reg
258: is set during the loop being scanned, or -1 if the insns that set it
259: have all been scanned as candidates for being moved out of the loop.
260: 0 indicates an invariant register; -1 a conditionally invariant one. */
261: short *n_times_set;
262: /* Indexed by register number, contains the number of times the reg
1.1.1.3 root 263: was used during the loop being scanned, not counting changes due
1.1 root 264: to moving these insns out of the loop. */
265: short *n_times_used;
266: /* Indexed by register number, contains 1 for a register whose
267: assignments may not be moved out of the loop. */
268: char *may_not_move;
269: /* Chain describing insns movable in current loop. */
270: struct movable *movables = 0;
271: /* Last element in `movables' -- so we can add elements at the end. */
272: struct movable *last_movable = 0;
273: /* Ratio of extra register life span we can justify
274: for saving an instruction. More if loop doesn't call subroutines
275: since in that case saving an insn makes more difference
276: and more registers are available. */
1.1.1.2 root 277: int threshold = loop_has_call ? 17 : 34;
1.1 root 278:
279: n_times_set = (short *) alloca (nregs * sizeof (short));
280: n_times_used = (short *) alloca (nregs * sizeof (short));
281: may_not_move = (char *) alloca (nregs);
282:
283: /* Determine whether this loop starts with a jump down
284: to a test at the end. */
285: while (p != end
286: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)
287: p = NEXT_INSN (p);
288:
289: /* "Loop" contains neither jumps nor labels;
290: it must have been a dummy. Think no more about it. */
291: if (p == end)
292: return;
293:
1.1.1.2 root 294: scan_start = p;
295:
1.1 root 296: /* If loop has a jump before the first label,
297: the true entry is the target of that jump.
298: Start scan from there.
299: But record in LOOP_TOP the place where the end-test jumps
300: back to so we can scan that after the end of the loop. */
301: if (GET_CODE (p) == JUMP_INSN)
302: {
303: loop_entry_jump = p;
304: loop_top = NEXT_INSN (p);
305: /* Loop entry will never be a conditional jump.
306: If we see one, this must not be a real loop. */
307: if (GET_CODE (loop_top) != BARRIER)
308: return;
309: p = JUMP_LABEL (p);
310: /* Check to see whether the jump actually
311: jumps out of the loop (meaning it's no loop).
312: This case can happen for things like
313: do {..} while (0). */
1.1.1.2 root 314: if (p == 0
315: || INSN_LUID (p) < INSN_LUID (loop_start)
1.1 root 316: || INSN_LUID (p) >= INSN_LUID (end))
1.1.1.2 root 317: {
318: if (loop_dump_stream)
319: fprintf (loop_dump_stream, "\nLoop from %d to %d is phony.\n\n",
320: INSN_UID (loop_start), INSN_UID (end));
321: return;
322: }
323:
324: /* Find the first label after the entry-jump. */
325: while (GET_CODE (loop_top) != CODE_LABEL)
326: {
327: loop_top = NEXT_INSN (loop_top);
328: if (loop_top == 0)
329: abort ();
330: }
331:
332: /* Maybe rearrange the loop to drop straight in
333: with a new test to jump around it entirely.
334: (The latter is considered outside the loop.)
335: If this is done, we no longer enter with a jump. */
336: if (loop_skip_over (loop_start, end, loop_entry_jump))
337: loop_top = 0;
338: else
339: /* We really do enter with a jump;
340: scan the loop from the place where the jump jumps to. */
341: scan_start = p;
1.1 root 342: }
343:
344: /* Count number of times each reg is set during this loop.
345: Set MAY_NOT_MOVE[I] if it is not safe to move out
346: the setting of register I. */
347:
348: bzero (n_times_set, nregs * sizeof (short));
349: bzero (may_not_move, nregs);
1.1.1.2 root 350: count_loop_regs_set (loop_top ? loop_top : loop_start, end,
351: n_times_set, may_not_move,
1.1 root 352: &insn_count, nregs);
353: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
354: may_not_move[i] = 1, n_times_set[i] = 1;
355: bcopy (n_times_set, n_times_used, nregs * sizeof (short));
356:
1.1.1.2 root 357: if (loop_dump_stream)
358: fprintf (loop_dump_stream, "\nLoop from %d to %d: %d real insns\n\n",
359: INSN_UID (loop_start), INSN_UID (end), insn_count);
360:
1.1 root 361: /* Scan through the loop finding insns that are safe to move.
362: In each such insn, store QImode as the mode, to mark it.
363: Then set n_times_set to -1 for the reg being set, so that
364: this reg will be considered invariant for subsequent insns.
365: We consider whether subsequent insns use the reg
366: in deciding whether it is worth actually moving.
367:
368: MAYBE_NEVER is nonzero if we have passed a conditional jump insn
369: and therefore it is possible that the insns we are scanning
370: would never be executed. At such times, we must make sure
371: that it is safe to execute the insn once instead of zero times.
372: When MAYBE_NEVER is 0, all insns will be executed at least once
373: so that is not a problem. */
374:
1.1.1.2 root 375: p = scan_start;
1.1 root 376: while (1)
377: {
378: p = NEXT_INSN (p);
379: /* At end of a straight-in loop, we are done.
380: At end of a loop entered at the bottom, scan the top. */
381: if (p == scan_start)
382: break;
383: if (p == end)
384: {
385: if (loop_top != 0)
386: p = NEXT_INSN (loop_top);
387: else
388: break;
389: if (p == scan_start)
390: break;
391: }
392: if (GET_CODE (p) == INSN
393: && GET_CODE (PATTERN (p)) == SET
394: && GET_CODE (SET_DEST (PATTERN (p))) == REG
395: && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))])
396: {
1.1.1.4 ! root 397: int tem1 = 0;
1.1 root 398: /* If this register is used or set outside the loop,
399: then we can move it only if we know this insn is
400: executed exactly once per iteration,
401: and we can check all the insns executed before it
402: to make sure none of them used the value that
403: was lying around at entry to the loop. */
404: if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end)
405: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start))
406: && (maybe_never
407: || loop_reg_used_before_p (p, loop_start, scan_start, end)))
408: ;
409: else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set))
410: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1
1.1.1.4 ! root 411: || (tem1
! 412: = consec_sets_invariant_p (SET_DEST (PATTERN (p)),
! 413: n_times_set[REGNO (SET_DEST (PATTERN (p)))],
! 414: p, n_times_set)))
1.1.1.3 root 415: /* If the insn can cause a trap (such as divide by zero),
416: can't move it unless it's guaranteed to be executed
417: once loop is entered. Even a function call might
418: prevent the trap insn from being reached
419: (since it might exit!) */
420: && ! ((maybe_never || call_passed)
421: && may_trap_p (SET_SRC (PATTERN (p)))))
1.1 root 422: {
423: register struct movable *m;
424: register int regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.2 root 425: int count;
1.1 root 426: m = (struct movable *) alloca (sizeof (struct movable));
427: m->next = 0;
428: m->insn = p;
429: m->force = 0;
1.1.1.2 root 430: m->consec = n_times_set[REGNO (SET_DEST (PATTERN (p)))] - 1;
431: m->done = 0;
1.1 root 432: m->forces = 0;
1.1.1.2 root 433: m->partial = 0;
1.1 root 434: m->regno = regno;
1.1.1.4 ! root 435: /* Set M->cond if either invariant_p or consec_sets_invariant_p
! 436: returned 2 (only conditionally invariant). */
! 437: m->cond = ((tem | tem1) > 1);
1.1 root 438: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
439: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
440: m->match = 0;
441: m->lifetime = (uid_luid[regno_last_uid[regno]]
442: - uid_luid[regno_first_uid[regno]]);
1.1.1.2 root 443: m->times_used = n_times_used[regno];
1.1 root 444: n_times_set[regno] = -1;
445: /* Add M to the end of the chain MOVABLES. */
446: if (movables == 0)
447: movables = m;
448: else
449: last_movable->next = m;
450: last_movable = m;
1.1.1.2 root 451: /* Skip the consecutive insns, if there are any. */
452: for (count = m->consec - 1; count >= 0; count--)
453: {
454: do p = NEXT_INSN (p);
455: while (GET_CODE (p) == NOTE);
456: }
1.1 root 457: }
1.1.1.2 root 458: /* If this register is always set within a STRICT_LOW_PART
459: or set to zero, then its high bytes are constant.
1.1 root 460: So clear them outside the loop and within the loop
461: just load the low bytes.
462: We must check that the machine has an instruction to do so.
463: Also, if the value loaded into the register
464: depends on the same register, this cannot be done. */
1.1.1.2 root 465: else if (SET_SRC (PATTERN (p)) == const0_rtx
466: && GET_CODE (NEXT_INSN (p)) == INSN
467: && GET_CODE (PATTERN (NEXT_INSN (p))) == SET
468: && (GET_CODE (SET_DEST (PATTERN (NEXT_INSN (p))))
469: == STRICT_LOW_PART)
470: && (GET_CODE (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
471: == SUBREG)
472: && (SUBREG_REG (XEXP (SET_DEST (PATTERN (NEXT_INSN (p))), 0))
473: == SET_DEST (PATTERN (p)))
1.1 root 474: && !reg_mentioned_p (SET_DEST (PATTERN (p)),
1.1.1.2 root 475: SET_SRC (PATTERN (NEXT_INSN (p)))))
1.1 root 476: {
477: register int regno = REGNO (SET_DEST (PATTERN (p)));
1.1.1.2 root 478: if (n_times_set[regno] == 2)
479: {
480: register struct movable *m;
481: int count;
482: m = (struct movable *) alloca (sizeof (struct movable));
483: m->next = 0;
484: m->insn = p;
485: m->force = 0;
486: m->consec = 0;
487: m->done = 0;
488: m->forces = 0;
489: m->partial = 1;
490: m->regno = regno;
491: m->cond = 0;
492: /* Say "global" so this register is not combined
493: with any other. In fact, it is sometimes possible
494: to combine two of these registers, but the criteria
495: are special and have not been programmed in. */
496: m->global = 1;
497: m->match = 0;
498: m->lifetime = (uid_luid[regno_last_uid[regno]]
499: - uid_luid[regno_first_uid[regno]]);
500: m->times_used = n_times_used[regno];
501: n_times_set[regno] = -1;
502: /* Add M to the end of the chain MOVABLES. */
503: if (movables == 0)
504: movables = m;
505: else
506: last_movable->next = m;
507: last_movable = m;
508: /* Skip the consecutive insns, if there are any. */
509: for (count = m->consec - 1; count >= 0; count--)
510: {
511: do p = NEXT_INSN (p);
512: while (GET_CODE (p) == NOTE);
513: }
514: }
1.1 root 515: }
516: }
1.1.1.3 root 517: /* Past a call insn, we get to insns which might not be executed
518: because the call might exit. This matters for insns that trap. */
519: else if (GET_CODE (p) == CALL_INSN)
520: call_passed = 1;
1.1 root 521: /* Past a label or a jump, we get to insns for which we
522: can't count on whether or how many times they will be
523: executed during each iteration. Therefore, we can
524: only move out sets of trivial variables
525: (those not used after the loop). */
526: else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
527: maybe_never = 1;
528: }
529:
530: /* For each movable insn, see if the reg that it loads
1.1.1.2 root 531: leads when it dies right into another conditionally movable insn.
532: If so, record that the second insn "forces" the first one,
533: since the second can be moved only if the first is. */
534:
1.1 root 535: {
536: register struct movable *m, *m1;
537: for (m1 = movables; m1; m1 = m1->next)
538: {
539: int regno = m1->regno;
540: for (m = m1->next; m; m = m->next)
541: if (INSN_UID (m->insn) == regno_last_uid[regno])
542: break;
543: if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn)))
544: m = 0;
1.1.1.2 root 545:
546: /* Increase the priority of the moving the first insn
547: since it permits the second to be moved as well. */
548: if (m != 0)
549: {
550: m->forces = m1;
551: m1->lifetime += m->lifetime;
552: m1->times_used += m1->times_used;
553: }
1.1 root 554: }
555: }
556:
557: /* See if there are multiple movable insns that load the same value.
558: If there are, make all but the first point at the first one
559: through the `match' field, and add the priorities of them
560: all together as the priority of the first. */
1.1.1.2 root 561:
1.1 root 562: {
563: register struct movable *m;
564: char *matched_regs = (char *) alloca (nregs);
565:
1.1.1.2 root 566: /* Regs that are used more than once are not allowed to match
567: or be matched. I'm no longer sure why not. */
1.1 root 568:
569: for (m = movables; m; m = m->next)
1.1.1.2 root 570: if (m->match == 0 && n_times_used[m->regno] == 1)
1.1 root 571: {
572: register struct movable *m1;
1.1.1.2 root 573: int regno = m->regno;
1.1 root 574:
575: bzero (matched_regs, nregs);
1.1.1.2 root 576: matched_regs[regno] = 1;
1.1 root 577:
578: for (m1 = m->next; m1; m1 = m1->next)
1.1.1.2 root 579: if (m1->match == 0 && n_times_used[m1->regno] == 1
580: /* A reg used outside the loop mustn't be eliminated. */
581: && !m1->global
582: && (matched_regs[m1->regno]
583: ||
584: (
585: /* Can't combine regs with different modes
586: even if loaded from the same constant. */
587: (GET_MODE (SET_DEST (PATTERN (m->insn)))
588: == GET_MODE (SET_DEST (PATTERN (m1->insn))))
589: /* See if the source of M1 says it matches M. */
590: && ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG
591: && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))])
592: || rtx_equal_p (SET_SRC (PATTERN (m->insn)),
593: SET_SRC (PATTERN (m1->insn)))
594: || (REG_NOTES (m->insn) && REG_NOTES (m1->insn)
595: && REG_NOTE_KIND (REG_NOTES (m->insn)) == REG_EQUIV
596: && REG_NOTE_KIND (REG_NOTES (m1->insn)) == REG_EQUIV
597: && rtx_equal_p (XEXP (REG_NOTES (m->insn), 0),
598: XEXP (REG_NOTES (m1->insn), 0)))))))
599: {
600: m->lifetime += m1->lifetime;
601: m->times_used += m1->times_used;
602: m1->match = m;
603: matched_regs[m1->regno] = 1;
604: }
605: }
606: }
607:
608: /* Now consider each movable insn to decide whether it is worth moving. */
609:
610: move_movables (movables, n_times_set, n_times_used, threshold,
611: insn_count, loop_start, end, nregs);
612: }
613:
614: /* Scan MOVABLES, and move the insns that deserve to be moved.
615: If two matching movables are combined, replace one reg with the
616: other throughout. */
617:
618: static void
619: move_movables (movables, n_times_set, n_times_used, threshold,
620: insn_count, loop_start, end, nregs)
621: struct movable *movables;
622: short *n_times_set;
623: short *n_times_used;
624: int threshold;
625: int insn_count;
626: rtx loop_start;
627: rtx end;
628: int nregs;
629: {
630: rtx new_start = 0;
631: register struct movable *m;
632: register rtx p;
633: /* Map of pseudo-register replacements to handle combining
634: when we move several insns that load the same value
635: into different pseudo-registers. */
636: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
637: char *already_moved = (char *) alloca (nregs);
638:
639: bzero (already_moved, nregs);
640: bzero (reg_map, nregs * sizeof (rtx));
641:
642: for (m = movables; m; m = m->next)
643: {
644: /* Describe this movable insn. */
645:
646: if (loop_dump_stream)
647: {
648: fprintf (loop_dump_stream, "Insn %d: regno %d (life %d), ",
649: INSN_UID (m->insn), m->regno, m->lifetime);
650: if (m->consec > 0)
651: fprintf (loop_dump_stream, "consec %d, ", m->consec);
652: if (m->cond)
653: fprintf (loop_dump_stream, "cond ");
654: if (m->force)
655: fprintf (loop_dump_stream, "force ");
656: if (m->global)
657: fprintf (loop_dump_stream, "global ");
658: if (m->done)
659: fprintf (loop_dump_stream, "done ");
660: if (m->match)
661: fprintf (loop_dump_stream, "matches %d ",
662: INSN_UID (m->match->insn));
663: if (m->forces)
664: fprintf (loop_dump_stream, "forces %d ",
665: INSN_UID (m->forces->insn));
666: }
667:
668: /* Ignore the insn if it's already done (it matched something else).
669: Otherwise, see if it is now safe to move. */
670:
671: if (!m->done
672: && (! m->cond
1.1.1.4 ! root 673: || (1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set)
! 674: && (m->consec == 0
! 675: || 1 == consec_sets_invariant_p (SET_DEST (PATTERN (m->insn)),
! 676: m->consec + 1,
! 677: m->insn, n_times_set))))
1.1.1.2 root 678: && (! m->forces || m->forces->done))
679: {
680: register int regno;
681: register rtx p;
682: int times_used = m->times_used + m->consec;
683:
684: /* We have an insn that is safe to move.
685: Compute its desirability. */
686:
687: p = m->insn;
688: regno = m->regno;
689:
690: if (loop_dump_stream)
691: fprintf (loop_dump_stream, "reg uses %d ", times_used);
692:
693: /* An insn MUST be moved if we already moved something else
694: which is safe only if this one is moved too: that is,
695: if already_moved[REGNO] is nonzero. */
696:
697: /* An insn is desirable to move if the new lifetime of the
698: register is no more than THRESHOLD times the old lifetime.
699: If it's not desirable, it means the loop is so big
700: that moving won't speed things up much,
701: and it is liable to make register usage worse. */
702:
703: /* It is also desirable to move if it can be moved at no
704: extra cost because something else was already moved. */
705:
706: if (already_moved[regno]
707: || (threshold * times_used * m->lifetime) >= insn_count
708: || (m->forces && m->forces->done
709: && n_times_used[m->forces->regno] == 1))
1.1 root 710: {
1.1.1.2 root 711: int count;
712: register struct movable *m1;
713:
714: for (count = m->consec; count >= 0; count--)
1.1 root 715: {
1.1.1.2 root 716: rtx i1 = emit_insn_before (PATTERN (p), loop_start);
717: if (new_start == 0)
718: new_start = i1;
719:
720: if (loop_dump_stream)
721: fprintf (loop_dump_stream, "moved to %d", INSN_UID (i1));
722:
723: /* Mark the moved, invariant reg as being equivalent to
724: its constant value. */
725: REG_NOTES (i1) = REG_NOTES (p);
726: if (REG_NOTES (i1) == 0
727: && ! m->partial /* But not if its a zero-extend clr. */
728: && ! m->global /* and not if used outside the loop
729: (since it might get set outside). */
730: && CONSTANT_P (SET_SRC (PATTERN (p))))
731: REG_NOTES (i1)
732: = gen_rtx (EXPR_LIST, REG_EQUIV,
733: SET_SRC (PATTERN (p)), REG_NOTES (i1));
734: delete_insn (p);
735: do p = NEXT_INSN (p);
736: while (GET_CODE (p) == NOTE);
737:
738: /* The more insns we move, the less we like moving them. */
739: threshold -= 2;
1.1 root 740: }
1.1.1.2 root 741:
742: /* Any other movable that loads the same register
743: MUST be moved. */
744: already_moved[regno] = 1;
745:
746: /* The reg set here is now invariant. */
747: if (! m->partial)
748: n_times_set[regno] = 0;
749:
750: m->done = 1;
751:
752: /* Combine with this moved insn any other matching movables. */
1.1 root 753:
754: for (m1 = m->next; m1; m1 = m1->next)
755: if (m1->match == m)
756: {
757: /* Schedule the reg loaded by M1
758: for replacement so that shares the reg of M. */
759: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn));
1.1.1.2 root 760: /* Get rid of the matching insn
1.1 root 761: and prevent further processing of it. */
1.1.1.2 root 762: m1->done = 1;
1.1 root 763: delete_insn (m1->insn);
1.1.1.2 root 764:
765: /* Any other movable that loads the same register
766: MUST be moved. */
767: already_moved[m1->regno] = 1;
768:
769: /* The reg merged here is now invariant. */
770: if (m->partial)
771: n_times_set[m1->regno] = 0;
1.1 root 772: }
773: }
1.1.1.2 root 774: else if (loop_dump_stream)
775: fprintf (loop_dump_stream, "not desirable");
1.1 root 776: }
1.1.1.2 root 777: else if (loop_dump_stream && !m->match)
778: fprintf (loop_dump_stream, "not safe");
1.1 root 779:
1.1.1.2 root 780: if (loop_dump_stream)
781: fprintf (loop_dump_stream, "\n");
782: }
1.1 root 783:
1.1.1.2 root 784: if (new_start == 0)
785: new_start = loop_start;
1.1 root 786:
1.1.1.2 root 787: /* Go through all the instructions in the loop, making
788: all the register substitutions scheduled in REG_MAP. */
789: for (p = new_start; p != end; p = NEXT_INSN (p))
790: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
791: || GET_CODE (p) == CALL_INSN)
792: replace_regs (PATTERN (p), reg_map);
793: }
794:
795: /* Optionally change a loop which enters just before the endtest
796: to one which falls straight in
797: after skipping around the entire loop if the endtest would drop out.
798: Returns 1 if the change was made, 0 if the loop was not really suitable. */
799:
800: int
801: loop_skip_over (start, end, loop_entry_jump)
802: rtx start;
803: rtx end;
804: rtx loop_entry_jump;
805: {
806: rtx endtestjump;
807: register rtx p = JUMP_LABEL (loop_entry_jump);
1.1 root 808:
1.1.1.2 root 809: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN
810: && GET_CODE (p) != CALL_INSN)
811: p = NEXT_INSN (p);
812: endtestjump = next_real_insn (p);
813:
814: /* Check that we (1) enter at a compare insn and (2)
815: the insn (presumably a jump) following that compare
816: is the last in the loop and jumps back to the loop beginning. */
817:
818: if (GET_CODE (PATTERN (p)) == SET
819: && SET_DEST (PATTERN (p)) == cc0_rtx
820: && endtestjump == prev_real_insn (end)
821: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump)
1.1 root 822: {
1.1.1.2 root 823: rtx newlab;
824: /* This is the jump that we insert. */
825: rtx new_jump;
826:
827: /* Ok, duplicate that test before start of loop. */
828: emit_insn_before (copy_rtx (PATTERN (p)), start);
829: /* Make a new entry-jump (before the original one)
830: whose condition is opposite to the loop-around endtest
831: and which jumps around the loop (to just after the endtest). */
832: newlab = gen_label_rtx ();
833: emit_label_after (newlab, endtestjump);
834: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), start);
835: new_jump = PREV_INSN (start);
836: JUMP_LABEL (new_jump) = JUMP_LABEL (endtestjump);
837: LABEL_NUSES (JUMP_LABEL (endtestjump))++;
838: invert_jump (new_jump, newlab);
839: /* Delete the original entry-jump. */
840: delete_insn (loop_entry_jump);
1.1 root 841:
1.1.1.2 root 842: return 1;
1.1 root 843: }
1.1.1.2 root 844:
845: return 0;
1.1 root 846: }
847:
848: /* Throughout the rtx X, replace many registers according to REG_MAP.
849: Return the replacement for X (which may be X with altered contents).
850: REG_MAP[R] is the replacement for register R, or 0 for don't replace. */
851:
852: static rtx
853: replace_regs (x, reg_map)
854: rtx x;
855: rtx *reg_map;
856: {
857: register RTX_CODE code = GET_CODE (x);
858: register int i;
859: register char *fmt;
860:
861: switch (code)
862: {
863: case PC:
864: case CC0:
865: case CONST_INT:
866: case CONST_DOUBLE:
867: case CONST:
868: case SYMBOL_REF:
869: case LABEL_REF:
870: return x;
871:
872: case REG:
873: if (reg_map[REGNO (x)] != 0)
874: return reg_map[REGNO (x)];
875: return x;
876: }
877:
878: fmt = GET_RTX_FORMAT (code);
879: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
880: {
881: if (fmt[i] == 'e')
882: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map);
883: if (fmt[i] == 'E')
884: {
885: register int j;
886: for (j = 0; j < XVECLEN (x, i); j++)
887: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map);
888: }
889: }
890: return x;
891: }
892:
1.1.1.4 ! root 893: #if 0
1.1 root 894: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
895: Replace it with an instruction to load just the low bytes
896: if the machine supports such an instruction,
897: and insert above LOOP_START an instruction to clear the register. */
898:
899: static void
900: constant_high_bytes (p, loop_start)
901: rtx p, loop_start;
902: {
903: register rtx new;
904: register int insn_code_number;
905:
906: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
907: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
908:
909: new = gen_rtx (SET, VOIDmode,
910: gen_rtx (STRICT_LOW_PART, VOIDmode,
911: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
912: SET_DEST (PATTERN (p)),
913: 0)),
914: XEXP (SET_SRC (PATTERN (p)), 0));
915: insn_code_number = recog (new, p);
916:
917: if (insn_code_number)
918: {
919: register int i;
920:
921: /* Clear destination register before the loop. */
922: emit_insn_before (gen_rtx (SET, VOIDmode,
923: SET_DEST (PATTERN (p)),
924: const0_rtx),
925: loop_start);
926:
927: /* Inside the loop, just load the low part. */
928: PATTERN (p) = new;
929: }
930: }
1.1.1.4 ! root 931: #endif
1.1 root 932:
933: /* Verify that the ostensible loop starting at START
934: really is a loop: nothing jumps into it from outside.
935: Return the marker for the end of the loop, or zero if not a real loop.
936:
937: Also set the variables `unknown_*_altered' and `loop_has_call',
938: and fill in the array `loop_store_addrs'. */
939:
940: static rtx
941: verify_loop (f, start)
942: rtx f, start;
943: {
944: register int level = 1;
945: register rtx insn, end;
946:
947: /* First find the LOOP_END that matches.
948: Also check each insn for storing in memory and record where. */
949:
950: unknown_address_altered = 0;
951: unknown_aggregate_altered = 0;
952: fixed_aggregate_altered = 0;
953: loop_has_call = 0;
954: loop_store_addrs_idx = 0;
955:
956: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn))
957: {
958: if (insn == 0)
1.1.1.2 root 959: /* Parse errors can cause a loop-beg with no loop-end. */
960: return 0;
1.1 root 961: if (GET_CODE (insn) == NOTE)
962: {
963: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
964: ++level;
965: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
1.1.1.2 root 966: {
967: --level;
968: if (level == 0)
969: {
970: end = insn;
971: break;
972: }
973: }
1.1 root 974: }
975: else if (GET_CODE (insn) == CALL_INSN)
976: {
977: unknown_address_altered = 1;
978: loop_has_call = 1;
979: }
980: else if (! unknown_address_altered)
981: {
982: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
983: note_stores (PATTERN (insn), note_addr_stored);
984: }
985: }
986:
987: /* Now scan all jumps in the function and see if any of them can
988: reach a label within the range of the loop. */
989:
990: for (insn = f; insn; insn = NEXT_INSN (insn))
991: if (GET_CODE (insn) == JUMP_INSN
992: /* Don't get fooled by jumps inserted by loop-optimize.
993: They don't have valid LUIDs, and they never jump into loops. */
994: && INSN_UID (insn) < max_uid
995: && (INSN_LUID (insn) < INSN_LUID (start)
996: || INSN_LUID (insn) > INSN_LUID (end))
997: /* We have a jump that is outside the loop.
998: Does it jump into the loop? */
999: && can_jump_into_range_p (PATTERN (insn),
1000: INSN_LUID (start), INSN_LUID (end)))
1001: return 0;
1002:
1003: #if 0
1004: /* Now scan all labels between them and check for any jumps from outside.
1005: This uses the ref-chains set up by find_basic_blocks.
1006: This code is not used because it's more convenient for other reasons
1007: to do the loop optimization before find_basic_blocks. */
1008:
1009: for (insn = start; insn != end; insn = NEXT_INSN (insn))
1010: if (GET_CODE (insn) == CODE_LABEL)
1011: {
1012: register rtx y;
1013: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
1014: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
1015: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
1016: return 0;
1017: }
1018: #endif
1019:
1020: return end;
1021: }
1022:
1023: /* Return 1 if somewhere in X is a LABEL_REF to a label
1024: located between BEG and END. */
1025:
1026: static int
1027: can_jump_into_range_p (x, beg, end)
1028: rtx x;
1029: int beg, end;
1030: {
1031: register RTX_CODE code = GET_CODE (x);
1032: register int i;
1033: register char *fmt;
1034:
1035: if (code == LABEL_REF)
1036: {
1037: register int luid = INSN_LUID (XEXP (x, 0));
1038: return luid > beg && luid < end;
1039: }
1040:
1041: fmt = GET_RTX_FORMAT (code);
1042: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1043: {
1044: if (fmt[i] == 'e')
1045: {
1046: if (can_jump_into_range_p (XEXP (x, i), beg, end))
1047: return 1;
1048: }
1049: else if (fmt[i] == 'E')
1050: {
1051: register int j;
1052: for (j = 0; j < XVECLEN (x, i); j++)
1053: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
1054: return 1;
1055: }
1056: }
1057:
1058: return 0;
1059: }
1060:
1061: /* Record that a memory reference X is being set. */
1062:
1063: static void
1064: note_addr_stored (x)
1065: rtx x;
1066: {
1067: rtx addr;
1068: if (x == 0 || GET_CODE (x) != MEM)
1069: return;
1.1.1.2 root 1070: if (GET_MODE (x) == BLKmode)
1071: unknown_address_altered = 1;
1072: else if (rtx_addr_varies_p (x))
1.1 root 1073: {
1074: if (GET_CODE (XEXP (x, 0)) == PLUS)
1075: unknown_aggregate_altered = 1;
1076: else
1077: unknown_address_altered = 1;
1078: }
1079: else
1080: {
1081: register int i;
1082: register rtx addr = XEXP (x, 0);
1083:
1084: if (x->in_struct)
1085: fixed_aggregate_altered = 1;
1086: for (i = 0; i < loop_store_addrs_idx; i++)
1087: if (rtx_equal_p (loop_store_addrs[i], addr))
1088: {
1089: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
1090: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
1091: break;
1092: }
1093: if (i == NUM_STORES)
1094: unknown_address_altered = 1;
1095: else if (i == loop_store_addrs_idx)
1096: {
1.1.1.2 root 1097: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
1.1 root 1098: loop_store_addrs[loop_store_addrs_idx++] = addr;
1099: }
1100: }
1101: }
1102:
1103: /* Return nonzero if the rtx X is invariant over the current loop.
1104: N_TIMES_SET is a vector whose element I is nonzero if register I
1105: is set during the loop.
1106:
1107: The value is 2 if we refer to something only conditionally invariant.
1108:
1109: If `unknown_address_altered' is nonzero, no memory ref is invariant.
1110: Otherwise if `unknown_aggregate_altered' is nonzero,
1111: a memory ref is invariant if it is not part of an aggregate
1112: and its address is fixed and not in `loop_store_addrs'.
1113: Otherwise if `fixed_aggregate_altered' is nonzero,
1114: a memory ref is invariant
1115: if its address is fixed and not in `loop_store_addrs'.
1116: Otherwise, a memory ref is invariant if its address is fixed and not in
1117: `loop_store_addrs' or if it is not an aggregate. */
1118:
1119: static int
1120: invariant_p (x, n_times_set)
1121: register rtx x;
1122: short *n_times_set;
1123: {
1124: register int i;
1125: register RTX_CODE code = GET_CODE (x);
1126: register char *fmt;
1127: int conditional = 0;
1128:
1129: switch (code)
1130: {
1131: case CONST_INT:
1132: case CONST_DOUBLE:
1133: case SYMBOL_REF:
1134: case LABEL_REF:
1135: case CONST:
1136: return 1;
1137:
1138: case PC:
1139: case CC0:
1140: return 0;
1141:
1142: case REG:
1.1.1.2 root 1143: if (x == frame_pointer_rtx || x == arg_pointer_rtx
1144: || x->unchanging)
1145: return 1;
1.1 root 1146: if (n_times_set[REGNO (x)] == -1)
1147: return 2;
1148: return n_times_set[REGNO (x)] == 0;
1149:
1150: case MEM:
1151: /* A store in a varying-address scalar (or a subroutine call)
1152: could clobber anything in memory. */
1153: if (unknown_address_altered)
1154: return 0;
1.1.1.2 root 1155: /* Don't mess with volatile memory references. */
1156: if (x->volatil)
1157: return 0;
1158: /* If it's declared read-only, it is invariant
1159: if its address is invariant. */
1160: if (x->unchanging)
1161: return invariant_p (XEXP (x, 0), n_times_set);
1.1 root 1162: /* A store in a varying-address aggregate component
1163: could clobber anything except a scalar with a fixed address. */
1164: if (unknown_aggregate_altered
1165: && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
1166: || rtx_addr_varies_p (x)))
1167: return 0;
1168: /* A store in a fixed-address aggregate component
1169: could clobber anything whose address is not fixed,
1170: even an aggregate component. */
1171: if (fixed_aggregate_altered
1172: && rtx_addr_varies_p (x))
1173: return 0;
1174: /* Any store could clobber a varying-address scalar. */
1175: if (loop_store_addrs_idx
1176: && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
1177: && rtx_addr_varies_p (x))
1178: return 0;
1179: /* A store in a fixed address clobbers overlapping references. */
1180: for (i = loop_store_addrs_idx - 1; i >= 0; i--)
1.1.1.2 root 1181: if (addr_overlap_p (x, loop_store_addrs[i], loop_store_widths[i]))
1.1 root 1182: return 0;
1183: /* It's not invalidated by a store in memory
1184: but we must still verify the address is invariant. */
1.1.1.2 root 1185: break;
1186:
1187: case ASM_OPERANDS:
1188: /* Don't mess with insns declared volatile. */
1189: if (x->volatil)
1190: return 0;
1.1 root 1191: }
1192:
1193: fmt = GET_RTX_FORMAT (code);
1194: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1195: {
1196: if (fmt[i] == 'e')
1197: {
1198: int tem = invariant_p (XEXP (x, i), n_times_set);
1199: if (tem == 0)
1200: return 0;
1201: if (tem == 2)
1202: conditional = 1;
1203: }
1.1.1.2 root 1204: else if (fmt[i] == 'E')
1205: {
1206: register int j;
1207: for (j = 0; j < XVECLEN (x, i); j++)
1208: {
1209: int tem = invariant_p (XVECEXP (x, i, j), n_times_set);
1210: if (tem == 0)
1211: return 0;
1212: if (tem == 2)
1213: conditional = 1;
1214: }
1215:
1216: }
1.1 root 1217: }
1218:
1219: return 1 + conditional;
1220: }
1221:
1222: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
1223: which is SIZE bytes starting at BASE. */
1224:
1225: int
1226: addr_overlap_p (other, base, size)
1227: rtx other;
1228: rtx base;
1229: int size;
1230: {
1231: int start = 0, end;
1232:
1233: if (GET_CODE (base) == CONST)
1234: base = XEXP (base, 0);
1235: if (GET_CODE (base) == PLUS
1236: && GET_CODE (XEXP (base, 1)) == CONST_INT)
1237: {
1238: start = INTVAL (XEXP (base, 1));
1239: base = XEXP (base, 0);
1240: }
1241:
1242: end = start + size;
1243: return refers_to_mem_p (other, base, start, end);
1244: }
1.1.1.2 root 1245:
1.1.1.4 ! root 1246: /* Return nonzero if all the insns in the loop that set REG
1.1.1.2 root 1247: are INSN and the immediately following insns,
1248: and if each of those insns sets REG in an invariant way
1249: according to TABLE (not counting uses of REG in them).
1250:
1.1.1.4 ! root 1251: The value is 2 if some of these insns are only conditionally invariant.
! 1252:
1.1.1.2 root 1253: We assume that INSN itself is the first set of REG
1254: and that its source is invariant. */
1255:
1256: static int
1.1.1.4 ! root 1257: consec_sets_invariant_p (reg, n_sets, insn, table)
! 1258: int n_sets;
1.1.1.2 root 1259: rtx reg, insn;
1260: short *table;
1261: {
1262: register rtx p = insn;
1263: register int regno = REGNO (reg);
1264: /* Number of sets we have to insist on finding after INSN. */
1.1.1.4 ! root 1265: int count = n_sets - 1;
1.1.1.2 root 1266: int old = table[regno];
1.1.1.4 ! root 1267: int tem = 0;
1.1.1.2 root 1268:
1269: table[regno] = 0;
1270:
1271: while (count > 0)
1272: {
1273: register enum rtx_code code;
1274: p = NEXT_INSN (p);
1275: code = GET_CODE (p);
1276: if (code == INSN && GET_CODE (PATTERN (p)) == SET
1277: && GET_CODE (SET_DEST (PATTERN (p))) == REG
1278: && REGNO (SET_DEST (PATTERN (p))) == regno
1.1.1.4 ! root 1279: && (tem |= invariant_p (SET_SRC (PATTERN (p)), table)))
1.1.1.2 root 1280: count--;
1281: else if (code != NOTE)
1282: {
1283: table[regno] = old;
1284: return 0;
1285: }
1286: }
1287:
1288: table[regno] = old;
1.1.1.4 ! root 1289: /* If invariant_p ever returned 2, we return 2. */
! 1290: return 1 + (tem & 2);
1.1.1.2 root 1291: }
1292:
1293: #if 0
1294: /* I don't think this condition is sufficient to allow INSN
1295: to be moved, so we no longer test it. */
1.1 root 1296:
1297: /* Return 1 if all insns in the basic block of INSN and following INSN
1298: that set REG are invariant according to TABLE. */
1299:
1300: static int
1301: all_sets_invariant_p (reg, insn, table)
1302: rtx reg, insn;
1.1.1.2 root 1303: short *table;
1.1 root 1304: {
1305: register rtx p = insn;
1306: register int regno = REGNO (reg);
1307:
1308: while (1)
1309: {
1310: register enum rtx_code code;
1311: p = NEXT_INSN (p);
1312: code = GET_CODE (p);
1313: if (code == CODE_LABEL || code == JUMP_INSN)
1314: return 1;
1315: if (code == INSN && GET_CODE (PATTERN (p)) == SET
1316: && GET_CODE (SET_DEST (PATTERN (p))) == REG
1317: && REGNO (SET_DEST (PATTERN (p))) == regno)
1318: {
1319: if (!invariant_p (SET_SRC (PATTERN (p)), table))
1320: return 0;
1321: }
1322: }
1323: }
1.1.1.2 root 1324: #endif /* 0 */
1.1 root 1325:
1326: /* Increment N_TIMES_SET at the index of each register
1327: that is modified by an insn between FROM and TO.
1328: If the value of an element of N_TIMES_SET becomes 2 or more,
1329: do not keep incrementing it; all values >= 2 would be
1330: equivalent anyway, and this way we avoid danger of overflow.
1331:
1332: Store in *COUNT_PTR the number of actual instruction
1333: in the loop. We use this to decide what is worth moving out. */
1334:
1335: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
1336: In that case, it is the insn that last set reg n. */
1337:
1338: static void
1339: count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs)
1340: register rtx from, to;
1341: short *n_times_set;
1342: char *may_not_move;
1343: int *count_ptr;
1344: int nregs;
1345: {
1346: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
1347: register rtx insn;
1348: register int count = 0;
1349: register rtx dest;
1350:
1351: bzero (last_set, nregs * sizeof (rtx));
1352: for (insn = from; insn != to; insn = NEXT_INSN (insn))
1353: {
1.1.1.2 root 1354: if (GET_CODE (insn) == CALL_INSN)
1355: {
1356: /* If a register is used as a subroutine address,
1357: don't allow this register's setting to be moved out of the loop.
1358: This condition is not at all logically correct
1359: but it averts a very common lossage pattern
1360: and creates lossage much less often. */
1361: if (GET_CODE (PATTERN (insn)) == CALL
1362: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM
1363: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG)
1364: {
1365: register int regno
1366: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0));
1367: may_not_move[regno] = 1;
1368: }
1369: else if (GET_CODE (PATTERN (insn)) == SET
1370: && GET_CODE (SET_SRC (PATTERN (insn))) == CALL
1371: && GET_CODE (XEXP (SET_SRC (PATTERN (insn)), 0)) == MEM
1372: && GET_CODE (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0)) == REG)
1373: {
1374: register int regno
1375: = REGNO (XEXP (XEXP (SET_SRC (PATTERN (insn)), 0), 0));
1376: may_not_move[regno] = 1;
1377: /* The call insn itself sets a reg, which cannot be moved. */
1378: may_not_move[REGNO (SET_DEST (PATTERN (insn)))] = 1;
1379: n_times_set[REGNO (SET_DEST (PATTERN (insn)))]++;
1380: }
1381: }
1382: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
1.1 root 1383: {
1384: ++count;
1.1.1.2 root 1385: if (GET_CODE (PATTERN (insn)) == CLOBBER
1386: && GET_CODE (XEXP (PATTERN (insn), 0)) == REG)
1387: /* Don't move a reg that has an explicit clobber.
1388: We might do so sometimes, but it's not worth the pain. */
1389: may_not_move[REGNO (XEXP (PATTERN (insn), 0))] = 1;
1390: else if (GET_CODE (PATTERN (insn)) == SET)
1.1 root 1391: {
1392: dest = SET_DEST (PATTERN (insn));
1393: while (GET_CODE (dest) == SUBREG
1394: || GET_CODE (dest) == ZERO_EXTRACT
1395: || GET_CODE (dest) == SIGN_EXTRACT
1396: || GET_CODE (dest) == STRICT_LOW_PART)
1397: dest = XEXP (dest, 0);
1398: if (GET_CODE (dest) == REG)
1399: {
1400: register int regno = REGNO (dest);
1401: /* If this is the first setting of this reg
1402: in current basic block, and it was set before,
1403: it must be set in two basic blocks, so it cannot
1404: be moved out of the loop. */
1405: if (n_times_set[regno] > 0 && last_set[regno] == 0)
1406: may_not_move[regno] = 1;
1407: /* If this is not first setting in current basic block,
1408: see if reg was used in between previous one and this.
1409: If so, neither one can be moved. */
1410: if (last_set[regno] != 0
1411: && reg_used_between_p (dest, last_set[regno], insn))
1412: may_not_move[regno] = 1;
1413: ++n_times_set[regno];
1414: last_set[regno] = insn;
1415: }
1416: }
1417: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1418: {
1419: register int i;
1420: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1421: {
1422: register rtx x = XVECEXP (PATTERN (insn), 0, i);
1.1.1.2 root 1423: if (GET_CODE (x) == CLOBBER && GET_CODE (XEXP (x, 0)) == REG)
1424: /* Don't move a reg that has an explicit clobber.
1425: It's not worth the pain to try to do it correctly. */
1426: may_not_move[REGNO (XEXP (x, 0))] = 1;
1.1 root 1427: if (GET_CODE (x) == SET)
1428: {
1429: dest = SET_DEST (x);
1430: while (GET_CODE (dest) == SUBREG
1431: || GET_CODE (dest) == ZERO_EXTRACT
1432: || GET_CODE (dest) == SIGN_EXTRACT
1433: || GET_CODE (dest) == STRICT_LOW_PART)
1434: dest = XEXP (dest, 0);
1435: if (GET_CODE (dest) == REG)
1436: {
1437: register int regno = REGNO (dest);
1438: ++n_times_set[regno];
1439: may_not_move[regno] = 1;
1440: last_set[regno] = insn;
1441: }
1442: }
1443: }
1444: }
1445: }
1446: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
1447: bzero (last_set, nregs * sizeof (rtx));
1448: }
1449: *count_ptr = count;
1450: }
1451:
1452: /* Given a loop that is bounded by LOOP_START and LOOP_END
1453: and that is entered at SCAN_START,
1454: return 1 if the register set by insn INSN is used by
1455: any insn that precedes INSN in cyclic order starting
1456: from the loop entry point. */
1457:
1458: static int
1459: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end)
1460: rtx insn, loop_start, scan_start, loop_end;
1461: {
1462: rtx reg = SET_DEST (PATTERN (insn));
1463: if (INSN_LUID (scan_start) > INSN_LUID (insn))
1464: return (reg_used_between_p (reg, scan_start, loop_end)
1465: || reg_used_between_p (reg, loop_start, insn));
1466: else
1467: return reg_used_between_p (reg, scan_start, insn);
1468: }
1.1.1.2 root 1469:
1.1.1.3 root 1470: /* Return nonzero if evaluating rtx X might cause a trap. */
1.1.1.2 root 1471:
1472: static int
1473: may_trap_p (x)
1474: rtx x;
1475: {
1.1.1.3 root 1476: int i;
1477: enum rtx_code code = GET_CODE (x);
1478: char *fmt;
1479:
1480: switch (code)
1.1.1.2 root 1481: {
1.1.1.3 root 1482: /* Handle these cases fast. */
1483: case CONST_INT:
1484: case CONST_DOUBLE:
1485: case SYMBOL_REF:
1486: case LABEL_REF:
1487: case CONST:
1488: case PC:
1489: case CC0:
1490: case REG:
1491: return 0;
1492:
1493: /* Division by a non-constant might trap. */
1.1.1.2 root 1494: case DIV:
1495: case MOD:
1496: case UDIV:
1497: case UMOD:
1498: if (! CONSTANT_P (XEXP (x, 1))
1499: && GET_CODE (XEXP (x, 1)) != CONST_DOUBLE)
1500: return 1;
1.1.1.3 root 1501: break;
1502:
1503: /* Memory ref can trap unless it's a static var or a stack slot. */
1504: case MEM:
1505: return rtx_varies_p (XEXP (x, 0));
1.1.1.4 ! root 1506:
! 1507: case SET:
! 1508: /* Any floating arithmetic may trap. */
! 1509: if (GET_MODE_CLASS (GET_MODE (SET_DEST (x))) == MODE_FLOAT
! 1510: && GET_CODE (SET_SRC (x)) != REG
! 1511: && GET_CODE (SET_SRC (x)) != MEM)
! 1512: return 1;
1.1.1.3 root 1513: }
1514:
1515: fmt = GET_RTX_FORMAT (code);
1516: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
1517: {
1518: if (fmt[i] == 'e')
1519: {
1520: if (may_trap_p (XEXP (x, i)))
1521: return 1;
1522: }
1523: else if (fmt[i] == 'E')
1524: {
1525: register int j;
1526: for (j = 0; j < XVECLEN (x, i); j++)
1527: if (may_trap_p (XVECEXP (x, i, j)))
1528: return 1;
1529: }
1.1.1.2 root 1530: }
1531: return 0;
1532: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.