![[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.
2: Copyright (C) 1987 Free Software Foundation, Inc.
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"
43:
44: /* Vector mapping INSN_UIDs to luids.
45: The luids are like uids but increase monononically always.
46: We use them to see whether a jump comes from outside a given loop. */
47:
48: static short *uid_luid;
49:
50: /* Get the luid of an insn. */
51:
52: #define INSN_LUID(INSN) (uid_luid[INSN_UID (INSN)])
53:
54: /* 1 + largest uid of any insn. */
55:
56: static int max_uid;
57:
58: /* 1 + luid of last insn. */
59:
60: static int max_luid;
61:
62: /* Nonzero if somewhere in the current loop
63: there is either a subroutine call,
64: or a store into a memory address that is not fixed,
65: or a store in a BLKmode memory operand,
66: or too many different fixed addresses stored in
67: to record them all in `loop_store_addrs'.
68:
69: In any of these cases, no memory location can be regarded
70: as invariant. */
71:
72: static int unknown_address_altered;
73:
74: /* Nonzero if somewhere in the current loop there is a store
75: into a memory address that is not fixed but is known to be
76: part of an aggregate.
77:
78: In this case, no memory reference in an aggregate may be
79: considered invariant. */
80:
81: static int unknown_aggregate_altered;
82:
83: /* Nonzero if somewhere in the current loop there is a store
84: into a memory address other than a fixed address not in an aggregate.
85:
86: In this case, no memory reference in an aggregate at a varying address
87: may be considered invariant. */
88:
89: static int fixed_aggregate_altered;
90:
91: /* Nonzero if there is a subroutine call in the current loop.
92: (unknown_address_altered is also nonzero in this case.) */
93:
94: static int loop_has_call;
95:
96: /* Array of fixed memory addresses that are stored in this loop.
97: If there are too many to fit here,
98: we just turn on unknown_address_altered. */
99:
100: #define NUM_STORES 10
101: static rtx loop_store_addrs[NUM_STORES];
102: static int loop_store_widths[NUM_STORES];
103:
104: /* Index of first available slot in above array. */
105: static int loop_store_addrs_idx;
106:
107: /* During the analysis of a loop, a chain of `struct movable's
108: is made to record all the movable insns found.
109: Then the entire chain can be scanned to decide which to move. */
110:
111: struct movable
112: {
113: rtx insn; /* A movable insn */
114: int regno; /* The register it sets */
115: short lifetime; /* lifetime of that register;
116: may be adjusted when matching movables
117: that load the same value are found. */
118: unsigned int cond : 1; /* 1 if only conditionally movable */
119: unsigned int force : 1; /* 1 means MUST move this insn */
120: unsigned int global : 1; /* 1 means reg is live outside this loop */
121: unsigned int dont : 1; /* 1 inhibits further processing of this */
122: struct movable *match; /* First entry for same value */
123: struct movable *forces; /* An insn that must be moved if this is */
124: struct movable *next;
125: };
126:
127: static rtx verify_loop ();
128: static int invariant_p ();
129: static int can_jump_into_range_p ();
130: static void count_loop_regs_set ();
131: static void note_addr_stored ();
132: static int loop_reg_used_before_p ();
133: static void constant_high_bytes ();
134: static void scan_loop ();
135: static rtx replace_regs ();
136:
137: /* Entry point of this file. Perform loop optimization
138: on the current function. F is the first insn of the function
139: and NREGS is the number of register numbers used. */
140:
141: int
142: loop_optimize (f, nregs)
143: /* f is the first instruction of a chain of insns for one function */
144: rtx f;
145: /* nregs is the total number of registers used in it */
146: int nregs;
147: {
148: register rtx insn;
149: register int i;
150: rtx end;
151: rtx last_insn;
152:
153: init_recog ();
154:
155: /* First find the last real insn, and count the number of insns,
156: and assign insns their suids. */
157:
158: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
159: if (INSN_UID (insn) > i)
160: i = INSN_UID (insn);
161:
162: max_uid = i + 1;
163: uid_luid = (short *) alloca ((i + 1) * sizeof (short));
164: bzero (uid_luid, (i + 1) * sizeof (short));
165:
166: /* Compute the mapping from uids to luids.
167: LUIDs are numbers assigned to insns, like uids,
168: except that luids increase monotonically through the code. */
169:
170: for (insn = f, i = 0; insn; insn = NEXT_INSN (insn))
171: {
172: last_insn = insn;
173: INSN_LUID (insn) = ++i;
174: }
175:
176: max_luid = i;
177:
178: /* Don't leave gaps in uid_luid for insns that have been
179: deleted. It is possible that the first or last insn
180: using some register has been deleted by cross-jumping.
181: Make sure that uid_luid for that former insn's uid
182: points to the general area where that insn used to be. */
183: for (i = 0; i < max_uid; i++)
184: if (uid_luid[i] == 0)
185: uid_luid[i] = uid_luid[i - 1];
186:
187: /* Find and process each loop.
188: We scan from the end, and process each loop when its start is seen,
189: so we process innermost loops first. */
190:
191: for (insn = last_insn; insn; insn = PREV_INSN (insn))
192: if (GET_CODE (insn) == NOTE
193: && NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG
194: /* Make sure it really is a loop -- no jumps in from outside. */
195: && (end = verify_loop (f, insn)))
196: scan_loop (insn, end, nregs);
197: }
198:
199: /* Optimize one loop whose start is LOOP_START and end is END.
200: LOOP_START is the NOTE_INSN_LOOP_BEG and END is the matching
201: NOTE_INSN_LOOP_END. */
202:
203: static void
204: scan_loop (loop_start, end, nregs)
205: rtx loop_start, end;
206: int nregs;
207: {
208: register int i;
209: register rtx p = NEXT_INSN (loop_start);
210: /* 1 if we are scanning insns that could be executed zero times. */
211: int maybe_never = 0;
212: /* For a rotated loop that is entered near the bottom,
213: this is the label at the top. Otherwise it is zero. */
214: rtx loop_top = 0;
215: /* Jump insn that enters the loop, or 0 if control drops in. */
216: rtx loop_entry_jump = 0;
217: /* Place in the loop where control enters. */
218: rtx scan_start;
219: /* Number of insns in the loop. */
220: int insn_count;
221: int tem;
222: /* Indexed by register number, contains the number of times the reg
223: is set during the loop being scanned, or -1 if the insns that set it
224: have all been scanned as candidates for being moved out of the loop.
225: 0 indicates an invariant register; -1 a conditionally invariant one. */
226: short *n_times_set;
227: /* Indexed by register number, contains the number of times the reg
228: was set during the loop being scanned, not counting changes due
229: to moving these insns out of the loop. */
230: short *n_times_used;
231: /* Indexed by register number, contains 1 for a register whose
232: assignments may not be moved out of the loop. */
233: char *may_not_move;
234: /* Chain describing insns movable in current loop. */
235: struct movable *movables = 0;
236: /* Last element in `movables' -- so we can add elements at the end. */
237: struct movable *last_movable = 0;
238: /* Ratio of extra register life span we can justify
239: for saving an instruction. More if loop doesn't call subroutines
240: since in that case saving an insn makes more difference
241: and more registers are available. */
242: int threshold = loop_has_call ? 15 : 30;
243:
244: n_times_set = (short *) alloca (nregs * sizeof (short));
245: n_times_used = (short *) alloca (nregs * sizeof (short));
246: may_not_move = (char *) alloca (nregs);
247:
248: /* Determine whether this loop starts with a jump down
249: to a test at the end. */
250: while (p != end
251: && GET_CODE (p) != CODE_LABEL && GET_CODE (p) != JUMP_INSN)
252: p = NEXT_INSN (p);
253:
254: /* "Loop" contains neither jumps nor labels;
255: it must have been a dummy. Think no more about it. */
256: if (p == end)
257: return;
258:
259: /* If loop has a jump before the first label,
260: the true entry is the target of that jump.
261: Start scan from there.
262: But record in LOOP_TOP the place where the end-test jumps
263: back to so we can scan that after the end of the loop. */
264: if (GET_CODE (p) == JUMP_INSN)
265: {
266: loop_entry_jump = p;
267: loop_top = NEXT_INSN (p);
268: /* Loop entry will never be a conditional jump.
269: If we see one, this must not be a real loop. */
270: if (GET_CODE (loop_top) != BARRIER)
271: return;
272: while (GET_CODE (loop_top) != CODE_LABEL)
273: loop_top = NEXT_INSN (loop_top);
274: p = JUMP_LABEL (p);
275: /* Check to see whether the jump actually
276: jumps out of the loop (meaning it's no loop).
277: This case can happen for things like
278: do {..} while (0). */
279: if (INSN_LUID (p) < INSN_LUID (loop_start)
280: || INSN_LUID (p) >= INSN_LUID (end))
281: return;
282: }
283:
284: /* Count number of times each reg is set during this loop.
285: Set MAY_NOT_MOVE[I] if it is not safe to move out
286: the setting of register I. */
287:
288: bzero (n_times_set, nregs * sizeof (short));
289: bzero (may_not_move, nregs);
290: count_loop_regs_set (loop_start, end, n_times_set, may_not_move,
291: &insn_count, nregs);
292: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
293: may_not_move[i] = 1, n_times_set[i] = 1;
294: bcopy (n_times_set, n_times_used, nregs * sizeof (short));
295:
296: /* Scan through the loop finding insns that are safe to move.
297: In each such insn, store QImode as the mode, to mark it.
298: Then set n_times_set to -1 for the reg being set, so that
299: this reg will be considered invariant for subsequent insns.
300: We consider whether subsequent insns use the reg
301: in deciding whether it is worth actually moving.
302:
303: MAYBE_NEVER is nonzero if we have passed a conditional jump insn
304: and therefore it is possible that the insns we are scanning
305: would never be executed. At such times, we must make sure
306: that it is safe to execute the insn once instead of zero times.
307: When MAYBE_NEVER is 0, all insns will be executed at least once
308: so that is not a problem. */
309:
310: scan_start = p;
311: while (1)
312: {
313: p = NEXT_INSN (p);
314: /* At end of a straight-in loop, we are done.
315: At end of a loop entered at the bottom, scan the top. */
316: if (p == scan_start)
317: break;
318: if (p == end)
319: {
320: if (loop_top != 0)
321: p = NEXT_INSN (loop_top);
322: else
323: break;
324: if (p == scan_start)
325: break;
326: }
327: if (GET_CODE (p) == INSN
328: && GET_CODE (PATTERN (p)) == SET
329: && GET_CODE (SET_DEST (PATTERN (p))) == REG
330: && ! may_not_move[REGNO (SET_DEST (PATTERN (p)))])
331: {
332: /* If this register is used or set outside the loop,
333: then we can move it only if we know this insn is
334: executed exactly once per iteration,
335: and we can check all the insns executed before it
336: to make sure none of them used the value that
337: was lying around at entry to the loop. */
338: if ((uid_luid[regno_last_uid[REGNO (SET_DEST (PATTERN (p)))]] > INSN_LUID (end)
339: || uid_luid[regno_first_uid[REGNO (SET_DEST (PATTERN (p)))]] < INSN_LUID (loop_start))
340: && (maybe_never
341: || loop_reg_used_before_p (p, loop_start, scan_start, end)))
342: ;
343: else if ((tem = invariant_p (SET_SRC (PATTERN (p)), n_times_set))
344: && (n_times_set[REGNO (SET_DEST (PATTERN (p)))] == 1
345: || all_sets_invariant_p (SET_DEST (PATTERN (p)),
346: p, n_times_set)))
347: {
348: register struct movable *m;
349: register int regno = REGNO (SET_DEST (PATTERN (p)));
350: m = (struct movable *) alloca (sizeof (struct movable));
351: m->next = 0;
352: m->insn = p;
353: m->force = 0;
354: m->dont = 0;
355: m->forces = 0;
356: m->regno = regno;
357: m->cond = (tem > 1);
358: m->global = (uid_luid[regno_last_uid[regno]] > INSN_LUID (end)
359: || uid_luid[regno_first_uid[regno]] < INSN_LUID (loop_start));
360: m->match = 0;
361: m->lifetime = (uid_luid[regno_last_uid[regno]]
362: - uid_luid[regno_first_uid[regno]]);
363: n_times_set[regno] = -1;
364: /* Add M to the end of the chain MOVABLES. */
365: if (movables == 0)
366: movables = m;
367: else
368: last_movable->next = m;
369: last_movable = m;
370: }
371: #ifdef SLOW_ZERO_EXTEND
372: /* If this register is set only once, and by zero-extending,
373: that means its high bytes are constant.
374: So clear them outside the loop and within the loop
375: just load the low bytes.
376: We must check that the machine has an instruction to do so.
377: Also, if the value loaded into the register
378: depends on the same register, this cannot be done. */
379:
380: else if (GET_CODE (SET_SRC (PATTERN (p))) == ZERO_EXTEND
381: && !reg_mentioned_p (SET_DEST (PATTERN (p)),
382: SET_SRC (PATTERN (p))))
383: {
384: register int regno = REGNO (SET_DEST (PATTERN (p)));
385: if ((threshold
386: * (uid_luid[regno_last_uid[regno]]
387: - uid_luid[regno_first_uid[regno]]))
388: >= insn_count)
389: constant_high_bytes (p, loop_start);
390: }
391: #endif /* SLOW_ZERO_EXTEND */
392: }
393: /* Past a label or a jump, we get to insns for which we
394: can't count on whether or how many times they will be
395: executed during each iteration. Therefore, we can
396: only move out sets of trivial variables
397: (those not used after the loop). */
398: else if (GET_CODE (p) == CODE_LABEL || GET_CODE (p) == JUMP_INSN)
399: maybe_never = 1;
400: }
401:
402: /* For each movable insn, see if the reg that it loads
403: leads when it dies right into another conditionally movable insn. */
404: {
405: register struct movable *m, *m1;
406: for (m1 = movables; m1; m1 = m1->next)
407: {
408: int regno = m1->regno;
409: for (m = m1->next; m; m = m->next)
410: if (INSN_UID (m->insn) == regno_last_uid[regno])
411: break;
412: if (m != 0 && SET_SRC (PATTERN (m->insn)) == SET_DEST (PATTERN (m1->insn)))
413: m = 0;
414: m1->forces = m;
415: }
416: }
417:
418: /* See if there are multiple movable insns that load the same value.
419: If there are, make all but the first point at the first one
420: through the `match' field, and add the priorities of them
421: all together as the priority of the first. */
422: {
423: register struct movable *m;
424: rtx *reg_map = (rtx *) alloca (nregs * sizeof (rtx));
425: char *matched_regs = (char *) alloca (nregs);
426:
427: bzero (reg_map, nregs * sizeof (rtx));
428:
429: for (m = movables; m; m = m->next)
430: if (m->match == 0 && n_times_used[m->regno] == 1 && !m->global
431: && (! movables->cond
432: || 1 == invariant_p (SET_SRC (PATTERN (movables->insn)), n_times_set)))
433: {
434: register struct movable *m1;
435: int matched = 0;
436: int lifetime = m->lifetime;
437: int times_used = n_times_used[m->regno];
438:
439: if (m->forces != 0) times_used++;
440:
441: bzero (matched_regs, nregs);
442: matched_regs[m->regno] = 1;
443:
444: for (m1 = m->next; m1; m1 = m1->next)
445: {
446: if (m1->match == 0 && n_times_used[m1->regno] == 1
447: && !m1->global
448: /* Perform already-scheduled replacements
449: on M1's insn before comparing them! */
450: && (replace_regs (PATTERN (m1->insn), reg_map),
451: ((GET_CODE (SET_SRC (PATTERN (m1->insn))) == REG
452: && matched_regs[REGNO (SET_SRC (PATTERN (m1->insn)))])
453: || rtx_equal_p (SET_SRC (PATTERN (m->insn)),
454: SET_SRC (PATTERN (m1->insn))))))
455: {
456: lifetime += m1->lifetime;
457: times_used += n_times_used[m1->regno];
458: if (m1->forces != 0) times_used++;
459: m1->match = m;
460: matched_regs[m1->regno] = 1;
461: matched = 1;
462: }
463: }
464:
465: /* If the movable insn M has others that match it
466: and all together they merit being moved,
467: go through the others now and replace their registers
468: with M's register. Mark the others with the `dont' field
469: and do all processing on them now. */
470: if (matched
471: && ((threshold * times_used * lifetime) >= insn_count
472: || m->force
473: || n_times_set[m->regno] == 0))
474: {
475: m->force = 1;
476: m->lifetime = lifetime;
477:
478: for (m1 = m->next; m1; m1 = m1->next)
479: if (m1->match == m)
480: {
481: /* Schedule the reg loaded by M1
482: for replacement so that shares the reg of M. */
483: reg_map[m1->regno] = SET_DEST (PATTERN (m->insn));
484: /* Get rid of the replaced reg
485: and prevent further processing of it. */
486: m1->dont = 1;
487: delete_insn (m1->insn);
488: }
489: }
490: }
491: /* Go through all the instructions in the loop, making
492: all the register substitutions scheduled above. */
493: for (p = loop_start; p != end; p = NEXT_INSN (p))
494: if (GET_CODE (p) == INSN || GET_CODE (p) == JUMP_INSN
495: || GET_CODE (p) == CALL_INSN)
496: replace_regs (PATTERN (p), reg_map);
497: }
498:
499: /* Now consider each movable insn to decide whether it is worth moving. */
500:
501: {
502: register struct movable *m;
503: for (m = movables; m; m = m->next)
504: if (!m->dont
505: && (! m->cond
506: || 1 == invariant_p (SET_SRC (PATTERN (m->insn)), n_times_set)))
507: /* We have an insn that is safe to move. */
508: {
509: register int regno;
510:
511: p = m->insn;
512: regno = m->regno;
513: if (m->forces != 0)
514: n_times_used[regno]++;
515:
516: /* Don't move something out of the loop
517: if that would cause it to be live over a range
518: THRESHOLD times as long. That means the loop is so big
519: that moving won't speed things up much,
520: and it is liable to make register usage worse. */
521: if (m->force
522: || (threshold * n_times_used[regno] * m->lifetime) >= insn_count
523: || n_times_set[regno] == 0)
524: {
525: rtx i1 = emit_insn_before (PATTERN (p), loop_start);
526: if (CONSTANT_ADDRESS_P (SET_SRC (PATTERN (p))))
527: REG_NOTES (i1)
528: = gen_rtx (EXPR_LIST, REG_CONST,
529: SET_DEST (PATTERN (p)), REG_NOTES (i1));
530: delete_insn (p);
531: n_times_set[regno] = 0;
532: /* Signal any other movables that match this one
533: that they should be moved too. */
534: m->force = 1;
535: /* Signal any conditionally movable computation
536: that uses this one that it should be moved too. */
537: if (m->forces != 0)
538: m->forces->force = 1;
539: }
540: }
541: }
542:
543: /* Now maybe duplicate the end-test before the loop. */
544: if (loop_entry_jump != 0)
545: {
546: rtx endtestjump;
547: p = scan_start;
548: while (GET_CODE (p) != INSN && GET_CODE (p) != JUMP_INSN
549: && GET_CODE (p) != CALL_INSN)
550: p = NEXT_INSN (p);
551: endtestjump = next_real_insn (p);
552: /* Check that we (1) enter at a compare insn and (2)
553: the insn (presumably a jump) following that compare
554: is the last in the loop and jumps back to the loop beginning. */
555: if (GET_CODE (PATTERN (p)) == SET
556: && SET_DEST (PATTERN (p)) == cc0_rtx
557: && endtestjump == prev_real_insn (end)
558: && prev_real_insn (JUMP_LABEL (endtestjump)) == loop_entry_jump)
559: {
560: rtx newlab;
561:
562: /* Ok, duplicate that test before loop entry. */
563: emit_insn_before (copy_rtx (PATTERN (p)), loop_entry_jump);
564: /* Make a new entry-jump (before the original)
565: that uses the opposite condition and jumps in
566: after this conitional jump. */
567: newlab = gen_label_rtx ();
568: emit_label_after (newlab, endtestjump);
569: emit_jump_insn_before (copy_rtx (PATTERN (endtestjump)), loop_entry_jump);
570: JUMP_LABEL (PREV_INSN (loop_entry_jump)) = JUMP_LABEL (endtestjump);
571: LABEL_NUSES (JUMP_LABEL (endtestjump))++;
572: invert_jump (PREV_INSN (loop_entry_jump), newlab);
573: /* Delete the original entry-jump. */
574: delete_insn (loop_entry_jump);
575: }
576: }
577: }
578:
579: /* Throughout the rtx X, replace many registers according to REG_MAP.
580: Return the replacement for X (which may be X with altered contents).
581: REG_MAP[R] is the replacement for register R, or 0 for don't replace. */
582:
583: static rtx
584: replace_regs (x, reg_map)
585: rtx x;
586: rtx *reg_map;
587: {
588: register RTX_CODE code = GET_CODE (x);
589: register int i;
590: register char *fmt;
591:
592: switch (code)
593: {
594: case PC:
595: case CC0:
596: case CONST_INT:
597: case CONST_DOUBLE:
598: case CONST:
599: case SYMBOL_REF:
600: case LABEL_REF:
601: return x;
602:
603: case REG:
604: if (reg_map[REGNO (x)] != 0)
605: return reg_map[REGNO (x)];
606: return x;
607: }
608:
609: fmt = GET_RTX_FORMAT (code);
610: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
611: {
612: if (fmt[i] == 'e')
613: XEXP (x, i) = replace_regs (XEXP (x, i), reg_map);
614: if (fmt[i] == 'E')
615: {
616: register int j;
617: for (j = 0; j < XVECLEN (x, i); j++)
618: XVECEXP (x, i, j) = replace_regs (XVECEXP (x, i, j), reg_map);
619: }
620: }
621: return x;
622: }
623:
624: /* P is an instruction that sets a register to the result of a ZERO_EXTEND.
625: Replace it with an instruction to load just the low bytes
626: if the machine supports such an instruction,
627: and insert above LOOP_START an instruction to clear the register. */
628:
629: static void
630: constant_high_bytes (p, loop_start)
631: rtx p, loop_start;
632: {
633: register rtx new;
634: register int insn_code_number;
635:
636: /* Try to change (SET (REG ...) (ZERO_EXTEND (..:B ...)))
637: to (SET (STRICT_LOW_PART (SUBREG:B (REG...))) ...). */
638:
639: new = gen_rtx (SET, VOIDmode,
640: gen_rtx (STRICT_LOW_PART, VOIDmode,
641: gen_rtx (SUBREG, GET_MODE (XEXP (SET_SRC (PATTERN (p)), 0)),
642: SET_DEST (PATTERN (p)),
643: 0)),
644: XEXP (SET_SRC (PATTERN (p)), 0));
645: insn_code_number = recog (new, p);
646:
647: if (insn_code_number)
648: {
649: register int i;
650:
651: /* Clear destination register before the loop. */
652: emit_insn_before (gen_rtx (SET, VOIDmode,
653: SET_DEST (PATTERN (p)),
654: const0_rtx),
655: loop_start);
656:
657: /* Inside the loop, just load the low part. */
658: PATTERN (p) = new;
659: }
660: }
661:
662: /* Verify that the ostensible loop starting at START
663: really is a loop: nothing jumps into it from outside.
664: Return the marker for the end of the loop, or zero if not a real loop.
665:
666: Also set the variables `unknown_*_altered' and `loop_has_call',
667: and fill in the array `loop_store_addrs'. */
668:
669: static rtx
670: verify_loop (f, start)
671: rtx f, start;
672: {
673: register int level = 1;
674: register rtx insn, end;
675:
676: /* First find the LOOP_END that matches.
677: Also check each insn for storing in memory and record where. */
678:
679: unknown_address_altered = 0;
680: unknown_aggregate_altered = 0;
681: fixed_aggregate_altered = 0;
682: loop_has_call = 0;
683: loop_store_addrs_idx = 0;
684:
685: for (insn = NEXT_INSN (start); level > 0; insn = NEXT_INSN (insn))
686: {
687: if (insn == 0)
688: abort ();
689: if (GET_CODE (insn) == NOTE)
690: {
691: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
692: ++level;
693: else if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END)
694: --level;
695: }
696: else if (GET_CODE (insn) == CALL_INSN)
697: {
698: unknown_address_altered = 1;
699: loop_has_call = 1;
700: }
701: else if (! unknown_address_altered)
702: {
703: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN)
704: note_stores (PATTERN (insn), note_addr_stored);
705: }
706: }
707:
708: end = insn;
709:
710: /* Now scan all jumps in the function and see if any of them can
711: reach a label within the range of the loop. */
712:
713: for (insn = f; insn; insn = NEXT_INSN (insn))
714: if (GET_CODE (insn) == JUMP_INSN
715: /* Don't get fooled by jumps inserted by loop-optimize.
716: They don't have valid LUIDs, and they never jump into loops. */
717: && INSN_UID (insn) < max_uid
718: && (INSN_LUID (insn) < INSN_LUID (start)
719: || INSN_LUID (insn) > INSN_LUID (end))
720: /* We have a jump that is outside the loop.
721: Does it jump into the loop? */
722: && can_jump_into_range_p (PATTERN (insn),
723: INSN_LUID (start), INSN_LUID (end)))
724: return 0;
725:
726: #if 0
727: /* Now scan all labels between them and check for any jumps from outside.
728: This uses the ref-chains set up by find_basic_blocks.
729: This code is not used because it's more convenient for other reasons
730: to do the loop optimization before find_basic_blocks. */
731:
732: for (insn = start; insn != end; insn = NEXT_INSN (insn))
733: if (GET_CODE (insn) == CODE_LABEL)
734: {
735: register rtx y;
736: for (y = LABEL_REFS (insn); y != insn; y = LABEL_NEXTREF (y))
737: if (INSN_LUID (CONTAINING_INSN (y)) < INSN_LUID (start)
738: || INSN_LUID (CONTAINING_INSN (y)) > INSN_LUID (end))
739: return 0;
740: }
741: #endif
742:
743: return end;
744: }
745:
746: /* Return 1 if somewhere in X is a LABEL_REF to a label
747: located between BEG and END. */
748:
749: static int
750: can_jump_into_range_p (x, beg, end)
751: rtx x;
752: int beg, end;
753: {
754: register RTX_CODE code = GET_CODE (x);
755: register int i;
756: register char *fmt;
757:
758: if (code == LABEL_REF)
759: {
760: register int luid = INSN_LUID (XEXP (x, 0));
761: return luid > beg && luid < end;
762: }
763:
764: fmt = GET_RTX_FORMAT (code);
765: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
766: {
767: if (fmt[i] == 'e')
768: {
769: if (can_jump_into_range_p (XEXP (x, i), beg, end))
770: return 1;
771: }
772: else if (fmt[i] == 'E')
773: {
774: register int j;
775: for (j = 0; j < XVECLEN (x, i); j++)
776: if (can_jump_into_range_p (XVECEXP (x, i, j), beg, end))
777: return 1;
778: }
779: }
780:
781: return 0;
782: }
783:
784: /* Record that a memory reference X is being set. */
785:
786: static void
787: note_addr_stored (x)
788: rtx x;
789: {
790: rtx addr;
791: if (x == 0 || GET_CODE (x) != MEM)
792: return;
793: if (rtx_addr_varies_p (x))
794: {
795: if (GET_CODE (XEXP (x, 0)) == PLUS)
796: unknown_aggregate_altered = 1;
797: else
798: unknown_address_altered = 1;
799: }
800: else if (GET_MODE (x) == BLKmode)
801: unknown_address_altered = 1;
802: else
803: {
804: register int i;
805: register rtx addr = XEXP (x, 0);
806:
807: if (x->in_struct)
808: fixed_aggregate_altered = 1;
809: for (i = 0; i < loop_store_addrs_idx; i++)
810: if (rtx_equal_p (loop_store_addrs[i], addr))
811: {
812: if (loop_store_widths[i] < GET_MODE_SIZE (GET_MODE (x)))
813: loop_store_widths[i] = GET_MODE_SIZE (GET_MODE (x));
814: break;
815: }
816: if (i == NUM_STORES)
817: unknown_address_altered = 1;
818: else if (i == loop_store_addrs_idx)
819: {
820: loop_store_widths[i] == GET_MODE_SIZE (GET_MODE (x));
821: loop_store_addrs[loop_store_addrs_idx++] = addr;
822: }
823: }
824: }
825:
826: /* Return nonzero if the rtx X is invariant over the current loop.
827: N_TIMES_SET is a vector whose element I is nonzero if register I
828: is set during the loop.
829:
830: The value is 2 if we refer to something only conditionally invariant.
831:
832: If `unknown_address_altered' is nonzero, no memory ref is invariant.
833: Otherwise if `unknown_aggregate_altered' is nonzero,
834: a memory ref is invariant if it is not part of an aggregate
835: and its address is fixed and not in `loop_store_addrs'.
836: Otherwise if `fixed_aggregate_altered' is nonzero,
837: a memory ref is invariant
838: if its address is fixed and not in `loop_store_addrs'.
839: Otherwise, a memory ref is invariant if its address is fixed and not in
840: `loop_store_addrs' or if it is not an aggregate. */
841:
842: static int
843: invariant_p (x, n_times_set)
844: register rtx x;
845: short *n_times_set;
846: {
847: register int i;
848: register RTX_CODE code = GET_CODE (x);
849: register char *fmt;
850: int conditional = 0;
851:
852: switch (code)
853: {
854: case CONST_INT:
855: case CONST_DOUBLE:
856: case SYMBOL_REF:
857: case LABEL_REF:
858: case CONST:
859: case UNCHANGING:
860: return 1;
861:
862: case PC:
863: case VOLATILE:
864: case CC0:
865: return 0;
866:
867: case REG:
868: if (n_times_set[REGNO (x)] == -1)
869: return 2;
870: return n_times_set[REGNO (x)] == 0;
871:
872: case MEM:
873: /* A store in a varying-address scalar (or a subroutine call)
874: could clobber anything in memory. */
875: if (unknown_address_altered)
876: return 0;
877: /* A store in a varying-address aggregate component
878: could clobber anything except a scalar with a fixed address. */
879: if (unknown_aggregate_altered
880: && ((x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
881: || rtx_addr_varies_p (x)))
882: return 0;
883: /* A store in a fixed-address aggregate component
884: could clobber anything whose address is not fixed,
885: even an aggregate component. */
886: if (fixed_aggregate_altered
887: && rtx_addr_varies_p (x))
888: return 0;
889: /* Any store could clobber a varying-address scalar. */
890: if (loop_store_addrs_idx
891: && !(x->in_struct || GET_CODE (XEXP (x, 0)) == PLUS)
892: && rtx_addr_varies_p (x))
893: return 0;
894: /* A store in a fixed address clobbers overlapping references. */
895: for (i = loop_store_addrs_idx - 1; i >= 0; i--)
896: if (addr_overlap_p (XEXP (x, 0), loop_store_addrs[i],
897: loop_store_widths[i]))
898: return 0;
899: /* It's not invalidated by a store in memory
900: but we must still verify the address is invariant. */
901: }
902:
903: fmt = GET_RTX_FORMAT (code);
904: for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--)
905: {
906: if (fmt[i] == 'E')
907: abort ();
908: if (fmt[i] == 'e')
909: {
910: int tem = invariant_p (XEXP (x, i), n_times_set);
911: if (tem == 0)
912: return 0;
913: if (tem == 2)
914: conditional = 1;
915: }
916: }
917:
918: return 1 + conditional;
919: }
920:
921: /* Return 1 if OTHER (a mem ref) overlaps the area of memory
922: which is SIZE bytes starting at BASE. */
923:
924: int
925: addr_overlap_p (other, base, size)
926: rtx other;
927: rtx base;
928: int size;
929: {
930: int start = 0, end;
931:
932: if (GET_CODE (base) == CONST)
933: base = XEXP (base, 0);
934: if (GET_CODE (base) == PLUS
935: && GET_CODE (XEXP (base, 1)) == CONST_INT)
936: {
937: start = INTVAL (XEXP (base, 1));
938: base = XEXP (base, 0);
939: }
940:
941: end = start + size;
942: return refers_to_mem_p (other, base, start, end);
943: }
944:
945: /* Return 1 if all insns in the basic block of INSN and following INSN
946: that set REG are invariant according to TABLE. */
947:
948: static int
949: all_sets_invariant_p (reg, insn, table)
950: rtx reg, insn;
951: char *table;
952: {
953: register rtx p = insn;
954: register int regno = REGNO (reg);
955:
956: while (1)
957: {
958: register enum rtx_code code;
959: p = NEXT_INSN (p);
960: code = GET_CODE (p);
961: if (code == CODE_LABEL || code == JUMP_INSN)
962: return 1;
963: if (code == INSN && GET_CODE (PATTERN (p)) == SET
964: && GET_CODE (SET_DEST (PATTERN (p))) == REG
965: && REGNO (SET_DEST (PATTERN (p))) == regno)
966: {
967: if (!invariant_p (SET_SRC (PATTERN (p)), table))
968: return 0;
969: }
970: }
971: }
972:
973: /* Increment N_TIMES_SET at the index of each register
974: that is modified by an insn between FROM and TO.
975: If the value of an element of N_TIMES_SET becomes 2 or more,
976: do not keep incrementing it; all values >= 2 would be
977: equivalent anyway, and this way we avoid danger of overflow.
978:
979: Store in *COUNT_PTR the number of actual instruction
980: in the loop. We use this to decide what is worth moving out. */
981:
982: /* last_set[n] is nonzero iff reg n has been set in the current basic block.
983: In that case, it is the insn that last set reg n. */
984:
985: static void
986: count_loop_regs_set (from, to, n_times_set, may_not_move, count_ptr, nregs)
987: register rtx from, to;
988: short *n_times_set;
989: char *may_not_move;
990: int *count_ptr;
991: int nregs;
992: {
993: register rtx *last_set = (rtx *) alloca (nregs * sizeof (rtx));
994: register rtx insn;
995: register int count = 0;
996: register rtx dest;
997:
998: bzero (last_set, nregs * sizeof (rtx));
999: for (insn = from; insn != to; insn = NEXT_INSN (insn))
1000: {
1001: if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN
1002: || GET_CODE (insn) == CALL_INSN)
1003: {
1004: ++count;
1005: if (GET_CODE (PATTERN (insn)) == SET)
1006: {
1007: dest = SET_DEST (PATTERN (insn));
1008: while (GET_CODE (dest) == SUBREG
1009: || GET_CODE (dest) == ZERO_EXTRACT
1010: || GET_CODE (dest) == SIGN_EXTRACT
1011: || GET_CODE (dest) == STRICT_LOW_PART)
1012: dest = XEXP (dest, 0);
1013: if (GET_CODE (dest) == REG)
1014: {
1015: register int regno = REGNO (dest);
1016: /* If this is the first setting of this reg
1017: in current basic block, and it was set before,
1018: it must be set in two basic blocks, so it cannot
1019: be moved out of the loop. */
1020: if (n_times_set[regno] > 0 && last_set[regno] == 0)
1021: may_not_move[regno] = 1;
1022: /* If this is not first setting in current basic block,
1023: see if reg was used in between previous one and this.
1024: If so, neither one can be moved. */
1025: if (last_set[regno] != 0
1026: && reg_used_between_p (dest, last_set[regno], insn))
1027: may_not_move[regno] = 1;
1028: ++n_times_set[regno];
1029: last_set[regno] = insn;
1030: }
1031: }
1032: else if (GET_CODE (PATTERN (insn)) == PARALLEL)
1033: {
1034: register int i;
1035: for (i = XVECLEN (PATTERN (insn), 0) - 1; i >= 0; i--)
1036: {
1037: register rtx x = XVECEXP (PATTERN (insn), 0, i);
1038: if (GET_CODE (x) == SET)
1039: {
1040: dest = SET_DEST (x);
1041: while (GET_CODE (dest) == SUBREG
1042: || GET_CODE (dest) == ZERO_EXTRACT
1043: || GET_CODE (dest) == SIGN_EXTRACT
1044: || GET_CODE (dest) == STRICT_LOW_PART)
1045: dest = XEXP (dest, 0);
1046: if (GET_CODE (dest) == REG)
1047: {
1048: register int regno = REGNO (dest);
1049: ++n_times_set[regno];
1050: may_not_move[regno] = 1;
1051: last_set[regno] = insn;
1052: }
1053: }
1054: }
1055: }
1056: /* If a register is used as a subroutine address,
1057: don't allow this register's setting to be moved out of the loop.
1058: This condition is not at all logically correct
1059: but it averts a very common lossage pattern
1060: and creates lossage much less often. */
1061: else if (GET_CODE (PATTERN (insn)) == CALL
1062: && GET_CODE (XEXP (PATTERN (insn), 0)) == MEM
1063: && GET_CODE (XEXP (XEXP (PATTERN (insn), 0), 0)) == REG)
1064: {
1065: register int regno
1066: = REGNO (XEXP (XEXP (PATTERN (insn), 0), 0));
1067: may_not_move[regno] = 1;
1068: }
1069: }
1070: if (GET_CODE (insn) == CODE_LABEL || GET_CODE (insn) == JUMP_INSN)
1071: bzero (last_set, nregs * sizeof (rtx));
1072: }
1073: *count_ptr = count;
1074: }
1075:
1076: /* Given a loop that is bounded by LOOP_START and LOOP_END
1077: and that is entered at SCAN_START,
1078: return 1 if the register set by insn INSN is used by
1079: any insn that precedes INSN in cyclic order starting
1080: from the loop entry point. */
1081:
1082: static int
1083: loop_reg_used_before_p (insn, loop_start, scan_start, loop_end)
1084: rtx insn, loop_start, scan_start, loop_end;
1085: {
1086: rtx reg = SET_DEST (PATTERN (insn));
1087: if (INSN_LUID (scan_start) > INSN_LUID (insn))
1088: return (reg_used_between_p (reg, scan_start, loop_end)
1089: || reg_used_between_p (reg, loop_start, insn));
1090: else
1091: return reg_used_between_p (reg, scan_start, insn);
1092: }
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.