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