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