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