![[BACK]](/cvsweb/icons/back.gif){kind=icon}
Return to reorg.c CVS log ![[TXT]](/cvsweb/icons/text.gif){kind=icon}
![[DIR]](/cvsweb/icons/dir.gif){kind=icon}
Up to [GCC 2.x] / gcc|
Return to reorg.c CVS log | Up to [GCC 2.x] / gcc |
1.1 root 1: /* Perform instruction reorganizations for delay slot filling.
2: Copyright (C) 1992 Free Software Foundation, Inc.
3: Contributed by Richard Kenner ([email protected]).
4: Hacked by Michael Tiemann ([email protected]).
5:
6: This file is part of GNU CC.
7:
8: GNU CC is free software; you can redistribute it and/or modify
9: it under the terms of the GNU General Public License as published by
10: the Free Software Foundation; either version 2, or (at your option)
11: any later version.
12:
13: GNU CC is distributed in the hope that it will be useful,
14: but WITHOUT ANY WARRANTY; without even the implied warranty of
15: MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
16: GNU General Public License for more details.
17:
18: You should have received a copy of the GNU General Public License
19: along with GNU CC; see the file COPYING. If not, write to
20: the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
21:
22:
23: #include "insn-attr.h"
24:
25: #ifdef DELAY_SLOTS
26:
27: /* Instruction reorganization pass.
28:
29: This pass runs after register allocation and final jump
30: optimization. It should be the last pass to run before peephole.
31: It serves primarily to fill delay slots of insns, typically branch
32: and call insns. Other insns typically involve more complicated
33: interractions of data dependencies and resource constraints, and
34: are better handled by scheduling before register allocation (by the
35: function `schedule_insns').
36:
37: The Branch Penalty is the number of extra cycles that are needed to
38: execute a branch insn. On an ideal machine, branches take a single
39: cycle, and the Branch Penalty is 0. Several RISC machines approach
40: branch delays differently:
41:
42: The MIPS and AMD 29000 have a single branch delay slot. Most insns
43: (except other branches) can be used to fill this slot. When the
44: slot is filled, two insns execute in two cycles, reducing the
45: branch penalty to zero.
46:
47: The Motorola 88000 conditionally exposes its branch delay slot,
48: so code is shorter when it is turned off, but will run faster
49: when useful insns are scheduled there.
50:
51: The IBM ROMP has two forms of branch and call insns, both with and
52: without a delay slot. Much like the 88k, insns not using the delay
53: slot can be shorted (2 bytes vs. 4 bytes), but will run slowed.
54:
55: The SPARC always has a branch delay slot, but its effects can be
56: annulled when the branch is not taken. This means that failing to
57: find other sources of insns, we can hoist an insn from the branch
58: target that would only be safe to execute knowing that the branch
59: is taken.
60:
61: Three techniques for filling delay slots have been implemented so far:
62:
63: (1) `fill_simple_delay_slots' is the simplest, most efficient way
64: to fill delay slots. This pass first looks for insns which come
65: from before the branch and which are safe to execute after the
66: branch. Then it searches after the insn requiring delay slots or,
67: in the case of a branch, for insns that are after the point at
68: which the branch merges into the fallthrough code, if such a point
69: exists. When such insns are found, the branch penalty decreases
70: and no code expansion takes place.
71:
72: (2) `fill_eager_delay_slots' is more complicated: it is used for
73: scheduling conditional jumps, or for scheduling jumps which cannot
74: be filled using (1). A machine need not have annulled jumps to use
75: this strategy, but it helps (by keeping more options open).
76: `fill_eager_delay_slots' tries to guess the direction the branch
77: will go; if it guesses right 100% of the time, it can reduce the
78: branch penalty as much as `fill_eager_delay_slots' does. If it
79: guesses wrong 100% of the time, it might as well schedule nops (or
80: on the m88k, unexpose the branch slot). When
81: `fill_eager_delay_slots' takes insns from the fall-through path of
82: the jump, usually there is no code expansion; when it takes insns
83: from the branch target, there is code expansion if it is not the
84: only way to reach that target.
85:
86: (3) `relax_delay_slots' uses a set of rules to simplify code that
87: has been reorganized by (1) and (2). It finds cases where
88: conditional test can be eliminated, jumps can be threaded, extra
89: insns can be eliminated, etc. It is the job of (1) and (2) to do a
90: good job of scheduling locally; `relax_delay_slots' takes care of
91: making the various individual schedules work well together. It is
92: especially tuned to handle the control flow interactions of branch
93: insns. It does nothing for insns with delay slots that do not
94: branch.
95:
96: On machines that use CC0, we are very conservative. We will not make
97: a copy of an insn involving CC0 since we want to maintain a 1-1
98: correspondance between the insn that sets and uses CC0. The insns are
99: allowed to be separated by placing an insn that sets CC0 (but not an insn
100: that uses CC0; we could do this, but it doesn't seem worthwhile) in a
101: delay slot. In that case, we point each insn at the other with REG_CC_USER
102: and REG_CC_SETTER notes. Note that these restrictions affect very few
103: machines because most RISC machines with delay slots will not use CC0
104: (the RT is the only known exception at this point).
105:
106: Not yet implemented:
107:
108: The Acorn Risc Machine can conditionally execute most insns, so
109: it is profitable to move single insns into a position to execute
110: based on the condition code of the previous insn.
111:
112: The HP-PA can conditionally nullify insns, providing a similar
113: effect to the ARM, differing mostly in which insn is "in charge". */
114:
115: #include <stdio.h>
116: #include "config.h"
117: #include "rtl.h"
118: #include "insn-config.h"
119: #include "conditions.h"
120: #include "hard-reg-set.h"
121: #include "basic-block.h"
122: #include "regs.h"
123: #include "insn-flags.h"
124: #include "recog.h"
125: #include "flags.h"
126: #include "output.h"
127: #include "obstack.h"
128:
129: #define obstack_chunk_alloc xmalloc
130: #define obstack_chunk_free free
131:
132: extern int xmalloc ();
133: extern void free ();
134:
135: #ifndef ANNUL_IFTRUE_SLOTS
136: #define eligible_for_annul_true(INSN, SLOTS, TRIAL) 0
137: #endif
138: #ifndef ANNUL_IFFALSE_SLOTS
139: #define eligible_for_annul_false(INSN, SLOTS, TRIAL) 0
140: #endif
141:
142: /* Insns which have delay slots that have not yet been filled. */
143:
144: static struct obstack unfilled_slots_obstack;
145: static rtx *unfilled_firstobj;
146:
147: /* Define macros to refer to the first and last slot containing unfilled
148: insns. These are used because the list may move and its address
149: should be recomputed at each use. */
150:
151: #define unfilled_slots_base \
152: ((rtx *) obstack_base (&unfilled_slots_obstack))
153:
154: #define unfilled_slots_next \
155: ((rtx *) obstack_next_free (&unfilled_slots_obstack))
156:
157: /* This structure is used to indicate which hardware resources are set or
158: needed by insns so far. */
159:
160: struct resources
161: {
162: char memory; /* Insn sets or needs a memory location. */
163: char volatil; /* Insn sets or needs a volatile memory loc. */
164: char cc; /* Insn sets or needs the condition codes. */
165: HARD_REG_SET regs; /* Which registers are set or needed. */
166: };
167:
168: /* Macro to clear all resources. */
169: #define CLEAR_RESOURCE(RES) \
170: do { (RES)->memory = (RES)->volatil = (RES)->cc = 0; \
171: CLEAR_HARD_REG_SET ((RES)->regs); } while (0)
172:
173: /* Indicates what resources are required at function end. */
174: static struct resources end_of_function_needs;
175:
176: /* Points to the label before the end of the function. */
177: static rtx end_of_function_label;
178:
179: /* This structure is used to record livness information at the targets or
180: fallthrough insns of branches. We will most likely need the information
181: at targets again, so save them in a hash table rather than recomputing them
182: each time. */
183:
184: struct target_info
185: {
186: int uid; /* INSN_UID of target. */
187: struct target_info *next; /* Next info for same hash bucket. */
188: HARD_REG_SET live_regs; /* Registers live at target. */
189: int block; /* Basic block number containing target. */
190: int bb_tick; /* Generation count of basic block info. */
191: };
192:
193: #define TARGET_HASH_PRIME 257
194:
195: /* Define the hash table itself. */
196: static struct target_info **target_hash_table;
197:
198: /* For each basic block, we maintain a generation number of its basic
199: block info, which is updated each time we move an insn from the
200: target of a jump. This is the generation number indexed by block
201: number. */
202:
203: static int *bb_ticks;
204:
205: /* Mapping between INSN_UID's and position in the code since INSN_UID's do
206: not always monotonically increase. */
207: static int *uid_to_ruid;
208:
209: /* Highest valid index in `uid_to_ruid'. */
210: static int max_uid;
211:
212: /* Forward references: */
213:
214: static int redundant_insn_p ();
215: static void update_block ();
216:
217: /* Given X, some rtl, and RES, a pointer to a `struct resource', mark
218: which resources are references by the insn. If INCLUDE_CALLED_ROUTINE
219: is TRUE, resources used by the called routine will be included for
220: CALL_INSNs. */
221:
222: static void
223: mark_referenced_resources (x, res, include_called_routine)
224: register rtx x;
225: register struct resources *res;
226: register int include_called_routine;
227: {
228: register enum rtx_code code = GET_CODE (x);
229: register int i, j;
230: register char *format_ptr;
231:
232: /* Handle leaf items for which we set resource flags. Also, special-case
233: CALL, SET and CLOBBER operators. */
234: switch (code)
235: {
236: case CONST:
237: case CONST_INT:
238: case CONST_DOUBLE:
239: case PC:
240: case SYMBOL_REF:
241: case LABEL_REF:
242: return;
243:
244: case SUBREG:
245: if (GET_CODE (SUBREG_REG (x)) != REG)
246: mark_referenced_resources (SUBREG_REG (x), res, 0);
247: else
248: {
249: int regno = REGNO (SUBREG_REG (x)) + SUBREG_WORD (x);
250: int last_regno = regno + HARD_REGNO_NREGS (regno, GET_MODE (x));
251: for (i = regno; i < last_regno; i++)
252: SET_HARD_REG_BIT (res->regs, i);
253: }
254: return;
255:
256: case REG:
257: for (i = 0; i < HARD_REGNO_NREGS (REGNO (x), GET_MODE (x)); i++)
258: SET_HARD_REG_BIT (res->regs, REGNO (x) + i);
259: return;
260:
261: case MEM:
262: /* If this memory shouldn't change, it really isn't referencing
263: memory. */
264: if (! RTX_UNCHANGING_P (x))
265: res->memory = 1;
266: res->volatil = MEM_VOLATILE_P (x);
267:
268: /* Mark registers used to access memory. */
269: mark_referenced_resources (XEXP (x, 0), res, 0);
270: return;
271:
272: case CC0:
273: res->cc = 1;
274: return;
275:
276: case UNSPEC_VOLATILE:
277: case ASM_INPUT:
278: /* Traditional asm's are always volatile. */
279: res->volatil = 1;
280: return;
281:
282: case ASM_OPERANDS:
283: res->volatil = MEM_VOLATILE_P (x);
284:
285: /* For all ASM_OPERANDS, we must traverse the vector of input operands.
286: We can not just fall through here since then we would be confused
287: by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate
288: traditional asms unlike their normal usage. */
289:
290: for (i = 0; i < ASM_OPERANDS_INPUT_LENGTH (x); i++)
291: mark_referenced_resources (ASM_OPERANDS_INPUT (x, i), res, 0);
292: return;
293:
294: case CALL:
295: /* The first operand will be a (MEM (xxx)) but doesn't really reference
296: memory. The second operand may be referenced, though. */
297: mark_referenced_resources (XEXP (XEXP (x, 0), 0), res, 0);
298: mark_referenced_resources (XEXP (x, 1), res, 0);
299: return;
300:
301: case SET:
302: /* Usually, the first operand of SET is set, not referenced. But
303: registers used to access memory are referenced. SET_DEST is
304: also referenced if it is a ZERO_EXTRACT or SIGN_EXTRACT. */
305:
306: mark_referenced_resources (SET_SRC (x), res, 0);
307:
308: x = SET_DEST (x);
309: if (GET_CODE (x) == SIGN_EXTRACT || GET_CODE (x) == ZERO_EXTRACT)
310: mark_referenced_resources (x, res, 0);
311: else if (GET_CODE (x) == SUBREG)
312: x = SUBREG_REG (x);
313: if (GET_CODE (x) == MEM)
314: mark_referenced_resources (XEXP (x, 0), res, 0);
315: return;
316:
317: case CLOBBER:
318: return;
319:
320: case CALL_INSN:
321: if (include_called_routine)
322: {
323: /* A CALL references memory, the frame pointer if it exists, the
324: stack pointer, any global registers and any registers given in
325: USE insns immediately in front of the CALL.
326:
327: However, we may have moved some of the parameter loading insns
328: into the delay slot of this CALL. If so, the USE's for them
329: don't count and should be skipped. */
330: rtx insn = PREV_INSN (x);
331: rtx sequence = 0;
332: int seq_size = 0;
333: int i;
334:
335: /* If we are part of a delay slot sequence, point at the SEQUENCE. */
336: if (NEXT_INSN (insn) != x)
337: {
338: sequence = PATTERN (NEXT_INSN (insn));
339: seq_size = XVECLEN (sequence, 0);
340: if (GET_CODE (sequence) != SEQUENCE)
341: abort ();
342: }
343:
344: res->memory = 1;
345: SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
346: if (frame_pointer_needed)
347: SET_HARD_REG_BIT (res->regs, FRAME_POINTER_REGNUM);
348:
349: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
350: if (global_regs[i])
351: SET_HARD_REG_BIT (res->regs, i);
352:
353: /* Skip any labels between the CALL_INSN and possible USE insns. */
354: while (GET_CODE (insn) == CODE_LABEL)
355: insn = PREV_INSN (insn);
356:
357: for ( ; (insn && GET_CODE (insn) == INSN
358: && GET_CODE (PATTERN (insn)) == USE);
359: insn = PREV_INSN (insn))
360: {
361: for (i = 1; i < seq_size; i++)
362: {
363: rtx slot_pat = PATTERN (XVECEXP (sequence, 0, i));
364: if (GET_CODE (slot_pat) == SET
365: && rtx_equal_p (SET_DEST (slot_pat),
366: XEXP (PATTERN (insn), 0)))
367: break;
368: }
369: if (i >= seq_size)
370: mark_referenced_resources (XEXP (PATTERN (insn), 0), res, 0);
371: }
372: }
373:
374: /* ... fall through to other INSN procesing ... */
375:
376: case INSN:
377: case JUMP_INSN:
378: /* No special processing, just speed up. */
379: mark_referenced_resources (PATTERN (x), res, include_called_routine);
380: return;
381: }
382:
383: /* Process each sub-expression and flag what it needs. */
384: format_ptr = GET_RTX_FORMAT (code);
385: for (i = 0; i < GET_RTX_LENGTH (code); i++)
386: switch (*format_ptr++)
387: {
388: case 'e':
389: mark_referenced_resources (XEXP (x, i), res, include_called_routine);
390: break;
391:
392: case 'E':
393: for (j = 0; j < XVECLEN (x, i); j++)
394: mark_referenced_resources (XVECEXP (x, i, j), res,
395: include_called_routine);
396: break;
397: }
398: }
399:
400: /* Given an insn, INSN, and a pointer to a `struct resource', RES, indicate
401: which resources are modified by the insn. If INCLUDE_CALLED_ROUTINE
402: is TRUE, also mark resources potentially set by the called routine.
403:
404: We never mark the insn as modifying the condition code unless it explicitly
405: SETs CC0 even though this is not totally correct. The reason for this is
406: that we require a SET of CC0 to immediately preceed the reference to CC0.
407: So if some other insn sets CC0 as a side-effect, we know it cannot affect
408: our computation and thus may be placed in a delay slot. */
409:
410: static void
411: mark_set_resources (insn, res, include_called_routine)
412: register rtx insn;
413: register struct resources *res;
414: int include_called_routine;
415: {
416: register int i;
417:
418: switch (GET_CODE (insn))
419: {
420: case NOTE:
421: case BARRIER:
422: case CODE_LABEL:
423: /* These don't set any resources. */
424: return;
425:
426: case CALL_INSN:
427: /* Called routine modifies the condition code, memory, any registers
428: that aren't saved across calls, global registers and anything
429: explicitly CLOBBERed immediately after the CALL_INSN. */
430:
431: if (include_called_routine)
432: {
433: rtx next = NEXT_INSN (insn);
434:
435: res->cc = res->memory = 1;
436: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
437: if (call_used_regs[i] || global_regs[i])
438: SET_HARD_REG_BIT (res->regs, i);
439:
440: /* Skip any possible labels between the CALL_INSN and CLOBBERs. */
441: while (GET_CODE (next) == CODE_LABEL)
442: next = NEXT_INSN (next);
443:
444: for (; (next && GET_CODE (next) == INSN
445: && GET_CODE (PATTERN (next)) == CLOBBER);
446: next = NEXT_INSN (next))
447: mark_referenced_resources (XEXP (PATTERN (next), 0), res, 0);
448: }
449:
450: /* ... and also what it's RTL says it modifies, if anything. */
451:
452: case JUMP_INSN:
453: case INSN:
454: {
455: register rtx body = PATTERN (insn);
456: register rtx note;
457:
458: /* An insn consisting of just a CLOBBER (or USE) is
459: just for flow and doesn't actually do anything, so we don't check
460: for it.
461:
462: If the source of a SET is a CALL, this is actually done by
463: the called routine. So only include it if we are to include the
464: effects of the calling routine. */
465:
466: if (GET_CODE (body) == SET
467: && (include_called_routine || GET_CODE (SET_SRC (body)) != CALL))
468: mark_referenced_resources (SET_DEST (body), res, 0);
469: else if (GET_CODE (body) == PARALLEL)
470: {
471: for (i = 0; i < XVECLEN (body, 0); i++)
472: if ((GET_CODE (XVECEXP (body, 0, i)) == SET
473: && (include_called_routine
474: || GET_CODE (SET_SRC (XVECEXP (body, 0, i))) != CALL))
475: || GET_CODE (XVECEXP (body, 0, i)) == CLOBBER)
476: mark_referenced_resources (SET_DEST (XVECEXP (body, 0, i)),
477: res, 0);
478: }
479: else if (GET_CODE (body) == SEQUENCE)
480: for (i = 0; i < XVECLEN (body, 0); i++)
481: if (! (INSN_ANNULLED_BRANCH_P (XVECEXP (body, 0, 0))
482: && INSN_FROM_TARGET_P (XVECEXP (body, 0, i))))
483: mark_set_resources (XVECEXP (body, 0, i), res,
484: include_called_routine);
485:
486: #ifdef AUTO_INC_DEC
487: /* If any register are incremented or decremented in an address,
488: they are set here. */
489: for (note = REG_NOTES (insn); note; note = XEXP (note, 1))
490: if (REG_NOTE_KIND (note) == REG_INC)
491: mark_referenced_resources (XEXP (note, 0), res, 0);
492: #endif
493:
494: #ifdef PUSH_ROUNDING
495: /* An insn that has a PRE_DEC on SP will not have a REG_INC note.
496: Until we fix this correctly, consider all insns as modifying
497: SP on such machines. So far, we don't have delay slot scheduling
498: on any machines with PUSH_ROUNDING. */
499: SET_HARD_REG_BIT (res->regs, STACK_POINTER_REGNUM);
500: #endif
501: return;
502: }
503:
504: default:
505: abort ();
506: }
507: }
508:
509: /* Return TRUE if this insn should stop the search for insn to fill delay
510: slots. LABELS_P indicates that labels should terminate the search.
511: In all cases, jumps terminate the search. */
512:
513: static int
514: stop_search_p (insn, labels_p)
515: rtx insn;
516: int labels_p;
517: {
518: if (insn == 0)
519: return 1;
520:
521: switch (GET_CODE (insn))
522: {
523: case NOTE:
524: case CALL_INSN:
525: return 0;
526:
527: case CODE_LABEL:
528: return labels_p;
529:
530: case JUMP_INSN:
531: case BARRIER:
532: return 1;
533:
534: case INSN:
535: /* OK unless it contains a delay slot or is an `asm' insn of some type.
536: We don't know anything about these. */
537: return (GET_CODE (PATTERN (insn)) == SEQUENCE
538: || GET_CODE (PATTERN (insn)) == ASM_INPUT
539: || asm_noperands (PATTERN (insn)) >= 0);
540:
541: default:
542: abort ();
543: }
544: }
545:
546: /* Return TRUE if any resources are marked in both RES1 and RES2 or if either
547: resource set contains a volatile memory reference. Otherwise, return FALSE. */
548:
549: static int
550: resource_conflicts_p (res1, res2)
551: struct resources *res1, *res2;
552: {
553: if ((res1->cc && res2->cc) || (res1->memory && res2->memory)
554: || res1->volatil || res2->volatil)
555: return 1;
556:
557: #ifdef HARD_REG_SET
558: return (res1->regs & res2->regs) != HARD_CONST (0);
559: #else
560: {
561: int i;
562:
563: for (i = 0; i < HARD_REG_SET_LONGS; i++)
564: if ((res1->regs[i] & res2->regs[i]) != 0)
565: return 1;
566: return 0;
567: }
568: #endif
569: }
570:
571: /* Return TRUE if any resource marked in RES, a `struct resources', is
572: referenced by INSN. If INCLUDE_CALLED_ROUTINE is set, return if the called
573: routine is using those resources.
574:
575: We compute this by computing all the resources referenced by INSN and
576: seeing if this conflicts with RES. It might be faster to directly check
577: ourselves, and this is the way it used to work, but it means duplicating
578: a large block of complex code. */
579:
580: static int
581: insn_references_resource_p (insn, res, include_called_routine)
582: register rtx insn;
583: register struct resources *res;
584: int include_called_routine;
585: {
586: struct resources insn_res;
587:
588: CLEAR_RESOURCE (&insn_res);
589: mark_referenced_resources (insn, &insn_res, include_called_routine);
590: return resource_conflicts_p (&insn_res, res);
591: }
592:
593: /* Return TRUE if INSN modifies resources that are marked in RES.
594: INCLUDE_CALLED_ROUTINE is set if the actions of that routine should be
595: included. CC0 is only modified if it is explicitly set; see comments
596: in front of mark_set_resources for details. */
597:
598: static int
599: insn_sets_resource_p (insn, res, include_called_routine)
600: register rtx insn;
601: register struct resources *res;
602: int include_called_routine;
603: {
604: struct resources insn_sets;
605:
606: CLEAR_RESOURCE (&insn_sets);
607: mark_set_resources (insn, &insn_sets, include_called_routine);
608: return resource_conflicts_p (&insn_sets, res);
609: }
610:
611: /* Find a label at the end of the function or before a RETURN. If there is
612: none, make one. */
613:
614: static rtx
615: find_end_label ()
616: {
617: rtx insn;
618:
619: /* If we found one previously, return it. */
620: if (end_of_function_label)
621: return end_of_function_label;
622:
623: /* Otherwise, see if there is a label at the end of the function. If there
624: is, it must be that RETURN insns aren't needed, so that is our return
625: label and we don't have to do anything else. */
626:
627: insn = get_last_insn ();
628: while (GET_CODE (insn) == NOTE
629: || (GET_CODE (insn) == INSN
630: && (GET_CODE (PATTERN (insn)) == USE
631: || GET_CODE (PATTERN (insn)) == CLOBBER)))
632: insn = PREV_INSN (insn);
633:
634: if (GET_CODE (insn) == CODE_LABEL)
635: end_of_function_label = insn;
636: else
637: {
638: /* Otherwise, make a new label and emit a RETURN and BARRIER,
639: if needed. */
640: end_of_function_label = gen_label_rtx ();
641: LABEL_NUSES (end_of_function_label) = 0;
642: emit_label (end_of_function_label);
643: #ifdef HAVE_return
644: if (HAVE_return)
645: {
646: emit_jump_insn (gen_return ());
647: emit_barrier ();
648: }
649: #endif
650: }
651:
652: /* Show one additional use for this label so it won't go away until
653: we are done. */
654: ++LABEL_NUSES (end_of_function_label);
655:
656: return end_of_function_label;
657: }
658:
659: /* Put INSN and LIST together in a SEQUENCE rtx of LENGTH, and replace
660: the pattern of INSN with the SEQUENCE.
661:
662: Chain the insns so that NEXT_INSN of each insn in the sequence points to
663: the next and NEXT_INSN of the last insn in the sequence points to
664: the first insn after the sequence. Similarly for PREV_INSN. This makes
665: it easier to scan all insns.
666:
667: Returns the SEQUENCE that replaces INSN. */
668:
669: static rtx
670: emit_delay_sequence (insn, list, length, avail)
671: rtx insn;
672: rtx list;
673: int length;
674: int avail;
675: {
676: register int i = 1;
677: register rtx li;
678: int had_barrier = 0;
679:
680: /* Allocate the the rtvec to hold the insns and the SEQUENCE. */
681: rtvec seqv = rtvec_alloc (length + 1);
682: rtx seq = gen_rtx (SEQUENCE, VOIDmode, seqv);
683: rtx seq_insn = make_insn_raw (seq);
684: rtx first = get_insns ();
685: rtx last = get_last_insn ();
686:
687: /* Make a copy of the insn having delay slots. */
688: rtx delay_insn = copy_rtx (insn);
689:
690: /* If INSN is followed by a BARRIER, delete the BARRIER since it will only
691: confuse further processing. Update LAST in case it was the last insn.
692: We will put the BARRIER back in later. */
693: if (NEXT_INSN (insn) && GET_CODE (NEXT_INSN (insn)) == BARRIER)
694: {
695: delete_insn (NEXT_INSN (insn));
696: last = get_last_insn ();
697: had_barrier = 1;
698: }
699:
700: /* Splice our SEQUENCE into the insn stream where INSN used to be. */
701: NEXT_INSN (seq_insn) = NEXT_INSN (insn);
702: PREV_INSN (seq_insn) = PREV_INSN (insn);
703:
704: if (insn == last)
705: set_new_first_and_last_insn (first, seq_insn);
706: else
707: PREV_INSN (NEXT_INSN (seq_insn)) = seq_insn;
708:
709: if (insn == first)
710: set_new_first_and_last_insn (seq_insn, last);
711: else
712: NEXT_INSN (PREV_INSN (seq_insn)) = seq_insn;
713:
714: /* Build our SEQUENCE and rebuild the insn chain. */
715: XVECEXP (seq, 0, 0) = delay_insn;
716: INSN_DELETED_P (delay_insn) = 0;
717: PREV_INSN (delay_insn) = PREV_INSN (seq_insn);
718:
719: for (li = list; li; li = XEXP (li, 1), i++)
720: {
721: rtx tem = XEXP (li, 0);
722: rtx note;
723:
724: /* Show that this copy of the insn isn't deleted. */
725: INSN_DELETED_P (tem) = 0;
726:
727: XVECEXP (seq, 0, i) = tem;
728: PREV_INSN (tem) = XVECEXP (seq, 0, i - 1);
729: NEXT_INSN (XVECEXP (seq, 0, i - 1)) = tem;
730:
731: /* Remove any REG_DEAD notes because we can't rely on them now
732: that the insn has been moved. */
733: for (note = REG_NOTES (tem); note; note = XEXP (note, 1))
734: if (REG_NOTE_KIND (note) == REG_DEAD)
735: XEXP (note, 0) = const0_rtx;
736: }
737:
738: NEXT_INSN (XVECEXP (seq, 0, length)) = NEXT_INSN (seq_insn);
739:
740: /* If the previous insn is a SEQUENCE, update the NEXT_INSN pointer on the
741: last insn in that SEQUENCE to point to us. Similarly for the first
742: insn in the following insn if it is a SEQUENCE. */
743:
744: if (PREV_INSN (seq_insn) && GET_CODE (PREV_INSN (seq_insn)) == INSN
745: && GET_CODE (PATTERN (PREV_INSN (seq_insn))) == SEQUENCE)
746: NEXT_INSN (XVECEXP (PATTERN (PREV_INSN (seq_insn)), 0,
747: XVECLEN (PATTERN (PREV_INSN (seq_insn)), 0) - 1))
748: = seq_insn;
749:
750: if (NEXT_INSN (seq_insn) && GET_CODE (NEXT_INSN (seq_insn)) == INSN
751: && GET_CODE (PATTERN (NEXT_INSN (seq_insn))) == SEQUENCE)
752: PREV_INSN (XVECEXP (PATTERN (NEXT_INSN (seq_insn)), 0, 0)) = seq_insn;
753:
754: /* If there used to be a BARRIER, put it back. */
755: if (had_barrier)
756: emit_barrier_after (seq_insn);
757:
758: if (i != length + 1)
759: abort ();
760:
761: return seq_insn;
762: }
763:
764: /* Add INSN to DELAY_LIST and return the head of the new list. The list must
765: be in the order in which the insns are to be executed. */
766:
767: static rtx
768: add_to_delay_list (insn, delay_list)
769: rtx insn;
770: rtx delay_list;
771: {
772: /* If we have an empty list, just make a new list element. */
773: if (delay_list == 0)
774: return gen_rtx (INSN_LIST, VOIDmode, insn, 0);
775:
776: /* Otherwise this must be an INSN_LIST. Add INSN to the end of the
777: list. */
778: XEXP (delay_list, 1) = add_to_delay_list (insn, XEXP (delay_list, 1));
779:
780: return delay_list;
781: }
782:
783: #ifdef HAVE_cc0
784: /* INSN uses CC0 and is being moved into a delay slot. Set up REG_CC_SETTER
785: and REG_CC_USER notes so we can find it. */
786:
787: static void
788: link_cc0_insns (insn)
789: rtx insn;
790: {
791: rtx user = next_nonnote_insn (insn);
792:
793: if (GET_CODE (user) == INSN && GET_CODE (PATTERN (user)) == SEQUENCE)
794: user = XVECEXP (PATTERN (user), 0, 0);
795:
796: REG_NOTES (user) = gen_rtx (INSN_LIST, REG_CC_SETTER, insn,
797: REG_NOTES (user));
798: REG_NOTES (insn) = gen_rtx (INSN_LIST, REG_CC_USER, user, REG_NOTES (insn));
799: }
800: #endif
801:
802: /* Delete INSN from the the delay slot of the insn that it is in. This may
803: produce an insn without anything in its delay slots. */
804:
805: static void
806: delete_from_delay_slot (insn)
807: rtx insn;
808: {
809: rtx trial, seq_insn, seq, prev;
810: rtx delay_list = 0;
811: int i;
812:
813: /* We first must find the insn containing the SEQUENCE with INSN in its
814: delay slot. Do this by finding an insn, TRIAL, where
815: PREV_INSN (NEXT_INSN (TRIAL)) != TRIAL. */
816:
817: for (trial = insn;
818: PREV_INSN (NEXT_INSN (trial)) == trial;
819: trial = NEXT_INSN (trial))
820: ;
821:
822: seq_insn = PREV_INSN (NEXT_INSN (trial));
823: seq = PATTERN (seq_insn);
824:
825: /* Create a delay list consisting of all the insns other than the one
826: we are deleting (unless we were the only one). */
827: if (XVECLEN (seq, 0) > 2)
828: for (i = 1; i < XVECLEN (seq, 0); i++)
829: if (XVECEXP (seq, 0, i) != insn)
830: delay_list = add_to_delay_list (XVECEXP (seq, 0, i), delay_list);
831:
832: /* Delete the old SEQUENCE, re-emit the insn that used to have the delay
833: list, and rebuild the delay list if non-empty. */
834: prev = PREV_INSN (seq_insn);
835: trial = XVECEXP (seq, 0, 0);
836: delete_insn (seq_insn);
837: add_insn_after (trial, prev);
838:
839: if (GET_CODE (trial) == JUMP_INSN
840: && (simplejump_p (trial) || GET_CODE (PATTERN (trial)) == RETURN))
841: emit_barrier_after (trial);
842:
843: /* If there are any delay insns, remit them. Otherwise clear the
844: annul flag. */
845: if (delay_list)
846: trial = emit_delay_sequence (trial, delay_list, XVECLEN (seq, 0) - 2, 0);
847: else
848: INSN_ANNULLED_BRANCH_P (trial) = 0;
849:
850: INSN_FROM_TARGET_P (insn) = 0;
851:
852: /* Show we need to fill this insn again. */
853: obstack_ptr_grow (&unfilled_slots_obstack, trial);
854: }
855:
856: /* Delete INSN, a JUMP_INSN. If it is a conditional jump, we must track down
857: the insn that sets CC0 for it and delete it too. */
858:
859: static void
860: delete_scheduled_jump (insn)
861: rtx insn;
862: {
863: /* Delete the insn that sets cc0 for us. On machines without cc0, we could
864: delete the insn that sets the condition code, but it is hard to find it.
865: Since this case is rare anyway, don't bother trying; there would likely
866: be other insns that became dead anyway, which we wouldn't know to
867: delete. */
868:
869: #ifdef HAVE_cc0
870: if (reg_mentioned_p (cc0_rtx, insn))
871: {
872: rtx note = find_reg_note (insn, REG_CC_SETTER, 0);
873:
874: /* If a reg-note was found, it points to an insn to set CC0. This
875: insn is in the delay list of some other insn. So delete it from
876: the delay list it was in. */
877: if (note)
878: {
879: if (! FIND_REG_INC_NOTE (XEXP (note, 0), 0)
880: && sets_cc0_p (PATTERN (XEXP (note, 0))) == 1)
881: delete_from_delay_slot (XEXP (note, 0));
882: }
883: else
884: {
885: /* The insn setting CC0 is our previous insn, but it may be in
886: a delay slot. It will be the last insn in the delay slot, if
887: it is. */
888: rtx trial = previous_insn (insn);
889: if (GET_CODE (trial) == NOTE)
890: trial = prev_nonnote_insn (trial);
891: if (sets_cc0_p (PATTERN (trial)) != 1
892: || FIND_REG_INC_NOTE (trial, 0))
893: return;
894: if (PREV_INSN (NEXT_INSN (trial)) == trial)
895: delete_insn (trial);
896: else
897: delete_from_delay_slot (trial);
898: }
899: }
900: #endif
901:
902: delete_insn (insn);
903: }
904:
905: /* Counters for delay-slot filling. */
906:
907: #define NUM_REORG_FUNCTIONS 2
908: #define MAX_DELAY_HISTOGRAM 3
909: #define MAX_REORG_PASSES 2
910:
911: static int num_insns_needing_delays[NUM_REORG_FUNCTIONS][MAX_REORG_PASSES];
912:
913: static int num_filled_delays[NUM_REORG_FUNCTIONS][MAX_DELAY_HISTOGRAM+1][MAX_REORG_PASSES];
914:
915: static int reorg_pass_number;
916:
917: static void
918: note_delay_statistics (slots_filled, index)
919: int slots_filled, index;
920: {
921: num_insns_needing_delays[index][reorg_pass_number]++;
922: if (slots_filled > MAX_DELAY_HISTOGRAM)
923: slots_filled = MAX_DELAY_HISTOGRAM;
924: num_filled_delays[index][slots_filled][reorg_pass_number]++;
925: }
926:
927: #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
928:
929: /* Optimize the following cases:
930:
931: 1. When a conditional branch skips over only one instruction,
932: use an annulling branch and put that insn in the delay slot.
933: Use either a branch that annulls when the condition if true or
934: invert the test with a branch that annulls when the condition is
935: false. This saves insns, since otherwise we must copy an insn
936: from the L1 target.
937:
938: (orig) (skip) (otherwise)
939: Bcc.n L1 Bcc',a L1 Bcc,a L1'
940: insn insn insn2
941: L1: L1: L1:
942: insn2 insn2 insn2
943: insn3 insn3 L1':
944: insn3
945:
946: 2. When a conditional branch skips over only one instruction,
947: and after that, it unconditionally branches somewhere else,
948: perform the similar optimization. This saves executing the
949: second branch in the case where the inverted condition is true.
950:
951: Bcc.n L1 Bcc',a L2
952: insn insn
953: L1: L1:
954: Bra L2 Bra L2
955:
956: INSN is a JUMP_INSN.
957:
958: This should be expanded to skip over N insns, where N is the number
959: of delay slots required. */
960:
961: static rtx
962: optimize_skip (insn)
963: register rtx insn;
964: {
965: register rtx trial = next_nonnote_insn (insn);
966: rtx next_trial = next_active_insn (trial);
967: rtx delay_list = 0;
968: rtx target_label;
969:
970: if (trial == 0
971: || GET_CODE (trial) != INSN
972: || GET_CODE (PATTERN (trial)) == SEQUENCE
973: || recog_memoized (trial) < 0
974: || (! eligible_for_annul_false (insn, 0, trial)
975: && ! eligible_for_annul_true (insn, 0, trial)))
976: return 0;
977:
978: /* There are two cases where we are just executing one insn (we assume
979: here that a branch requires only one insn; this should be generalized
980: at some point): Where the branch goes around a single insn or where
981: we have one insn followed by a branch to the same label we branch to.
982: In both of these cases, inverting the jump and annulling the delay
983: slot give the same effect in fewer insns. */
984: if ((next_trial == next_active_insn (JUMP_LABEL (insn)))
985: || (next_trial != 0
986: && GET_CODE (next_trial) == JUMP_INSN
987: && JUMP_LABEL (insn) == JUMP_LABEL (next_trial)
988: && (simplejump_p (next_trial)
989: || GET_CODE (PATTERN (next_trial)) == RETURN)))
990: {
991: if (eligible_for_annul_false (insn, 0, trial))
992: {
993: if (invert_jump (insn, JUMP_LABEL (insn)))
994: INSN_FROM_TARGET_P (trial) = 1;
995: else if (! eligible_for_annul_true (insn, 0, trial))
996: return 0;
997: }
998:
999: delay_list = add_to_delay_list (trial, 0);
1000: next_trial = next_active_insn (trial);
1001: update_block (trial, trial);
1002: delete_insn (trial);
1003:
1004: /* Also, if we are targeting an unconditional
1005: branch, thread our jump to the target of that branch. Don't
1006: change this into a RETURN here, because it may not accept what
1007: we have in the delay slot. We'll fix this up later. */
1008: if (next_trial && GET_CODE (next_trial) == JUMP_INSN
1009: && (simplejump_p (next_trial)
1010: || GET_CODE (PATTERN (next_trial)) == RETURN))
1011: {
1012: target_label = JUMP_LABEL (next_trial);
1013: if (target_label == 0)
1014: target_label = find_end_label ();
1015: redirect_jump (insn, target_label);
1016: }
1017:
1018: INSN_ANNULLED_BRANCH_P (insn) = 1;
1019: }
1020:
1021: return delay_list;
1022: }
1023: #endif
1024:
1025: /* Return truth value of the statement that this branch
1026: is mostly taken. If we think that the branch is extremely likely
1027: to be taken, we return 2. If the branch is slightly more likely to be
1028: taken, return 1. Otherwise, return 0.
1029:
1030: CONDITION, if non-zero, is the condition that JUMP_INSN is testing. */
1031:
1032: static int
1033: mostly_true_jump (jump_insn, condition)
1034: rtx jump_insn, condition;
1035: {
1036: rtx target_label = JUMP_LABEL (jump_insn);
1037: rtx insn;
1038:
1039: /* If this is a conditional return insn, assume it won't return. */
1040: if (target_label == 0)
1041: return 0;
1042:
1043: /* If TARGET_LABEL has no jumps between it and the end of the function,
1044: this is essentially a conditional return, so predict it as false. */
1045: for (insn = NEXT_INSN (target_label);
1046: insn && GET_CODE (insn) != JUMP_INSN;
1047: insn = NEXT_INSN (insn))
1048: ;
1049:
1050: if (insn == 0)
1051: return 0;
1052:
1053: /* If this is the test of a loop, it is very likely true. We scan backwards
1054: from the target label. If we find a NOTE_INSN_LOOP_BEG before the next
1055: real insn, we assume the branch is to the top of the loop. */
1056: for (insn = PREV_INSN (target_label);
1057: insn && GET_CODE (insn) == NOTE;
1058: insn = PREV_INSN (insn))
1059: if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG)
1060: return 2;
1061:
1062: /* If we couldn't figure out what this jump was, assume it won't be
1063: taken. This should be rare. */
1064: if (condition == 0)
1065: return 0;
1066:
1067: /* EQ tests are usually false and NE tests are usually true. Also,
1068: most quantities are positive, so we can make the appropriate guesses
1069: about signed comparisons against zero. */
1070: switch (GET_CODE (condition))
1071: {
1072: case CONST_INT:
1073: /* Unconditional branch. */
1074: return 1;
1075: case EQ:
1076: return 0;
1077: case NE:
1078: return 1;
1079: case LE:
1080: case LT:
1081: if (XEXP (condition, 1) == const0_rtx)
1082: return 0;
1083: break;
1084: case GE:
1085: case GT:
1086: if (XEXP (condition, 1) == const0_rtx)
1087: return 1;
1088: break;
1089: }
1090:
1091: /* Predict backward branches usually take, forward branches usually not. If
1092: we don't know whether this is forward or backward, assume the branch
1093: will be taken, since most are. */
1094: return (INSN_UID (jump_insn) > max_uid || INSN_UID (target_label) > max_uid
1095: || (uid_to_ruid[INSN_UID (jump_insn)]
1096: > uid_to_ruid[INSN_UID (target_label)]));;
1097: }
1098:
1099: /* Return the condition under which INSN will branch to TARGET. If TARGET
1100: is zero, return the condition under which INSN will return. If INSN is
1101: an unconditional branch, return const_true_rtx. If INSN isn't a simple
1102: type of jump, or it doesn't go to TARGET, return 0. */
1103:
1104: static rtx
1105: get_branch_condition (insn, target)
1106: rtx insn;
1107: rtx target;
1108: {
1109: rtx pat = PATTERN (insn);
1110: rtx src;
1111:
1112: if (GET_CODE (pat) == RETURN)
1113: return target == 0 ? const_true_rtx : 0;
1114:
1115: else if (GET_CODE (pat) != SET || SET_DEST (pat) != pc_rtx)
1116: return 0;
1117:
1118: src = SET_SRC (pat);
1119: if (GET_CODE (src) == LABEL_REF && XEXP (src, 0) == target)
1120: return const_true_rtx;
1121:
1122: else if (GET_CODE (src) == IF_THEN_ELSE
1123: && ((target == 0 && GET_CODE (XEXP (src, 1)) == RETURN)
1124: || (GET_CODE (XEXP (src, 1)) == LABEL_REF
1125: && XEXP (XEXP (src, 1), 0) == target))
1126: && XEXP (src, 2) == pc_rtx)
1127: return XEXP (src, 0);
1128:
1129: else if (GET_CODE (src) == IF_THEN_ELSE
1130: && ((target == 0 && GET_CODE (XEXP (src, 2)) == RETURN)
1131: || (GET_CODE (XEXP (src, 2)) == LABEL_REF
1132: && XEXP (XEXP (src, 2), 0) == target))
1133: && XEXP (src, 1) == pc_rtx)
1134: return gen_rtx (reverse_condition (GET_CODE (XEXP (src, 0))),
1135: GET_MODE (XEXP (src, 0)),
1136: XEXP (XEXP (src, 0), 0), XEXP (XEXP (src, 0), 1));
1137: }
1138:
1139: /* Return non-zero if CONDITION is more strict than the condition of
1140: INSN, i.e., if INSN will always branch if CONDITION is true. */
1141:
1142: static int
1143: condition_dominates_p (condition, insn)
1144: rtx condition;
1145: rtx insn;
1146: {
1147: rtx other_condition = get_branch_condition (insn, JUMP_LABEL (insn));
1148: enum rtx_code code = GET_CODE (condition);
1149: enum rtx_code other_code;
1150:
1151: if (rtx_equal_p (condition, other_condition)
1152: || other_condition == const_true_rtx)
1153: return 1;
1154:
1155: else if (condition == const_true_rtx || other_condition == 0)
1156: return 0;
1157:
1158: other_code = GET_CODE (other_condition);
1159: if (GET_RTX_LENGTH (code) != 2 || GET_RTX_LENGTH (other_code) != 2
1160: || ! rtx_equal_p (XEXP (condition, 0), XEXP (other_condition, 0))
1161: || ! rtx_equal_p (XEXP (condition, 1), XEXP (other_condition, 1)))
1162: return 0;
1163:
1164: return comparison_dominates_p (code, other_code);
1165: }
1166:
1167: /* INSN branches to an insn whose pattern SEQ is a SEQUENCE. Given that
1168: the condition tested by INSN is CONDITION and the resources shown in
1169: OTHER_NEEDED are needed after INSN, see whether INSN can take all the insns
1170: from SEQ's delay list, in addition to whatever insns it may execute
1171: (in DELAY_LIST). SETS and NEEDED are denote resources already set and
1172: needed while searching for delay slot insns. Return the concatenated
1173: delay list if possible, otherwise, return 0.
1174:
1175: SLOTS_TO_FILL is the total number of slots required by INSN, and
1176: PSLOTS_FILLED points to the number filled so far (also the number of
1177: insns in DELAY_LIST). It is updated with the number that have been
1178: filled from the SEQUENCE, if any.
1179:
1180: PANNUL_P points to a non-zero value if we already know that we need
1181: to annul INSN. If this routine determines that annulling is needed,
1182: it may set that value non-zero.
1183:
1184: PNEW_THREAD points to a location that is to receive the place at which
1185: execution should continue. */
1186:
1187: static rtx
1188: steal_delay_list_from_target (insn, condition, seq, delay_list,
1189: sets, needed, other_needed,
1190: slots_to_fill, pslots_filled, pannul_p,
1191: pnew_thread)
1192: rtx insn, condition;
1193: rtx seq;
1194: rtx delay_list;
1195: struct resources *sets, *needed, *other_needed;
1196: int slots_to_fill;
1197: int *pslots_filled;
1198: int *pannul_p;
1199: rtx *pnew_thread;
1200: {
1201: rtx temp;
1202: int slots_remaining = slots_to_fill - *pslots_filled;
1203: int total_slots_filled = *pslots_filled;
1204: rtx new_delay_list = 0;
1205: int must_annul = *pannul_p;
1206: int i;
1207:
1208: /* We can't do anything if there are more delay slots in SEQ than we
1209: can handle, or if we don't know that it will be a taken branch.
1210:
1211: We know that it will be a taken branch if it is either an unconditional
1212: branch or a conditional branch with a stricter branch condition. */
1213:
1214: if (XVECLEN (seq, 0) - 1 > slots_remaining
1215: || ! condition_dominates_p (condition, XVECEXP (seq, 0, 0)))
1216: return delay_list;
1217:
1218: for (i = 1; i < XVECLEN (seq, 0); i++)
1219: {
1220: rtx trial = XVECEXP (seq, 0, i);
1221:
1222: if (insn_references_resource_p (trial, sets, 0)
1223: || insn_sets_resource_p (trial, needed, 0)
1224: || insn_sets_resource_p (trial, sets, 0)
1225: #ifdef HAVE_cc0
1226: /* If TRIAL sets CC0, we can't copy it, so we can't steal this
1227: delay list. */
1228: || find_reg_note (trial, REG_CC_USER, 0)
1229: #endif
1230: /* If TRIAL is from the fallthrough code of an annulled branch insn
1231: in SEQ, we cannot use it. */
1232: || (INSN_ANNULLED_BRANCH_P (XVECEXP (seq, 0, 0))
1233: && ! INSN_FROM_TARGET_P (trial)))
1234: return delay_list;
1235:
1236: /* If this insn was already done (usually in a previous delay slot),
1237: pretend we put it in our delay slot. */
1238: if (redundant_insn_p (trial, insn, new_delay_list))
1239: continue;
1240:
1241: if (! must_annul
1242: && ((condition == const_true_rtx
1243: || (! insn_sets_resource_p (trial, other_needed, 0)
1244: && ! may_trap_p (PATTERN (trial)))))
1245: ? eligible_for_delay (insn, total_slots_filled, trial)
1246: : (must_annul = 1,
1247: eligible_for_annul_false (insn, total_slots_filled, trial)))
1248: {
1249: temp = copy_rtx (trial);
1250: INSN_FROM_TARGET_P (temp) = 1;
1251: new_delay_list = add_to_delay_list (temp, new_delay_list);
1252: total_slots_filled++;
1253:
1254: if (--slots_remaining == 0)
1255: break;
1256: }
1257: else
1258: return delay_list;
1259: }
1260:
1261: /* Show the place to which we will be branching. */
1262: *pnew_thread = next_active_insn (JUMP_LABEL (XVECEXP (seq, 0, 0)));
1263:
1264: /* Add any new insns to the delay list and update the count of the
1265: number of slots filled. */
1266: *pslots_filled = total_slots_filled;
1267: *pannul_p = must_annul;
1268:
1269: if (delay_list == 0)
1270: return new_delay_list;
1271:
1272: for (temp = new_delay_list; temp; temp = XEXP (temp, 1))
1273: delay_list = add_to_delay_list (XEXP (temp, 0), delay_list);
1274:
1275: return delay_list;
1276: }
1277:
1278: /* Similar to steal_delay_list_from_target except that SEQ is on the
1279: fallthrough path of INSN. Here we only do something if the delay insn
1280: of SEQ is an unconditional branch. In that case we steal its delay slot
1281: for INSN since unconditional branches are much easier to fill. */
1282:
1283: static rtx
1284: steal_delay_list_from_fallthrough (insn, condition, seq,
1285: delay_list, sets, needed, other_needed,
1286: slots_to_fill, pslots_filled, pannul_p)
1287: rtx insn, condition;
1288: rtx seq;
1289: rtx delay_list;
1290: struct resources *sets, *needed, *other_needed;
1291: int slots_to_fill;
1292: int *pslots_filled;
1293: int *pannul_p;
1294: {
1295: int i;
1296:
1297: /* We can't do anything if SEQ's delay insn isn't an
1298: unconditional branch. */
1299:
1300: if (! simplejump_p (XVECEXP (seq, 0, 0))
1301: && GET_CODE (PATTERN (XVECEXP (seq, 0, 0))) != RETURN)
1302: return delay_list;
1303:
1304: for (i = 1; i < XVECLEN (seq, 0); i++)
1305: {
1306: rtx trial = XVECEXP (seq, 0, i);
1307:
1308: /* If TRIAL sets CC0, stealing it will move it too far from the use
1309: of CC0. */
1310: if (insn_references_resource_p (trial, sets, 0)
1311: || insn_sets_resource_p (trial, needed, 0)
1312: || insn_sets_resource_p (trial, sets, 0)
1313: #ifdef HAVE_cc0
1314: || sets_cc0_p (PATTERN (trial))
1315: #endif
1316: )
1317:
1318: break;
1319:
1320: /* If this insn was already done, we don't need it. */
1321: if (redundant_insn_p (trial, insn, delay_list))
1322: {
1323: delete_from_delay_slot (trial);
1324: continue;
1325: }
1326:
1327: if (! *pannul_p
1328: && ((condition == const_true_rtx
1329: || (! insn_sets_resource_p (trial, other_needed, 0)
1330: && ! may_trap_p (PATTERN (trial)))))
1331: ? eligible_for_delay (insn, *pslots_filled, trial)
1332: : (*pannul_p = 1,
1333: eligible_for_annul_true (insn, *pslots_filled, trial)))
1334: {
1335: delete_from_delay_slot (trial);
1336: delay_list = add_to_delay_list (trial, delay_list);
1337:
1338: if (++(*pslots_filled) == slots_to_fill)
1339: break;
1340: }
1341: else
1342: break;
1343: }
1344:
1345: return delay_list;
1346: }
1347:
1348: /* Try merging insns starting at THREAD which match exactly the insns in
1349: INSN's delay list.
1350:
1351: If all insns were matched and the insn was previously annulling, the
1352: annul bit will be cleared.
1353:
1354: For each insn that is merged, if the branch is or will be non-annulling,
1355: we delete the merged insn. */
1356:
1357: static void
1358: try_merge_delay_insns (insn, thread)
1359: rtx insn, thread;
1360: {
1361: rtx trial, next_trial;
1362: rtx delay_insn = XVECEXP (PATTERN (insn), 0, 0);
1363: int annul_p = INSN_ANNULLED_BRANCH_P (delay_insn);
1364: int slot_number = 1;
1365: int num_slots = XVECLEN (PATTERN (insn), 0);
1366: rtx next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1367: struct resources set, needed;
1368: rtx merged_insns = 0;
1369: int i;
1370:
1371: CLEAR_RESOURCE (&needed);
1372: CLEAR_RESOURCE (&set);
1373:
1374: /* If this is not an annulling branch, take into account anything needed in
1375: NEXT_TO_MATCH. This prevents two increments from being incorrectly
1376: folded into one. If we are annulling, this would be the correct
1377: thing to do. (The alternative, looking at things set in NEXT_TO_MATCH
1378: will essentially disable this optimization. This method is somewhat of
1379: a kludge, but I don't see a better way.) */
1380: if (! annul_p)
1381: mark_referenced_resources (next_to_match, &needed, 1);
1382:
1383: for (trial = thread; !stop_search_p (trial, 1); trial = next_trial)
1384: {
1385: rtx pat = PATTERN (trial);
1386:
1387: next_trial = next_nonnote_insn (trial);
1388:
1389: /* TRIAL must be a CALL_INSN or INSN. Skip USE and CLOBBER. */
1390: if (GET_CODE (trial) == INSN
1391: && (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER))
1392: continue;
1393:
1394: if (GET_CODE (next_to_match) == GET_CODE (trial)
1395: #ifdef HAVE_cc0
1396: /* We can't share an insn that sets cc0. */
1397: && ! sets_cc0_p (pat)
1398: #endif
1399: && ! insn_references_resource_p (trial, &set, 1)
1400: && ! insn_sets_resource_p (trial, &set, 1)
1401: && ! insn_sets_resource_p (trial, &needed, 1)
1402: && (trial = try_split (pat, trial, 0)) != 0
1403: && rtx_equal_p (PATTERN (next_to_match), PATTERN (trial))
1404: /* Have to test this condition if annul condition is different
1405: from (and less restrictive than) non-annulling one. */
1406: && eligible_for_delay (delay_insn, slot_number - 1, trial))
1407: {
1408: next_trial = next_nonnote_insn (trial);
1409:
1410: if (! annul_p)
1411: {
1412: update_block (trial, thread);
1413: delete_insn (trial);
1414: INSN_FROM_TARGET_P (next_to_match) = 0;
1415: }
1416: else
1417: merged_insns = gen_rtx (INSN_LIST, VOIDmode, trial, merged_insns);
1418:
1419: if (++slot_number == num_slots)
1420: break;
1421:
1422: next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1423: if (! annul_p)
1424: mark_referenced_resources (next_to_match, &needed, 1);
1425: }
1426:
1427: mark_set_resources (trial, &set, 1);
1428: mark_referenced_resources (trial, &needed, 1);
1429: }
1430:
1431: /* See if we stopped on a filled insn. If we did, try to see if its
1432: delay slots match. */
1433: if (slot_number != num_slots
1434: && trial && GET_CODE (trial) == INSN
1435: && GET_CODE (PATTERN (trial)) == SEQUENCE
1436: && ! INSN_ANNULLED_BRANCH_P (XVECEXP (PATTERN (trial), 0, 0)))
1437: {
1438: rtx pat = PATTERN (trial);
1439:
1440: for (i = 1; i < XVECLEN (pat, 0); i++)
1441: {
1442: rtx dtrial = XVECEXP (pat, 0, i);
1443:
1444: if (! insn_references_resource_p (dtrial, &set, 1)
1445: && ! insn_sets_resource_p (dtrial, &set, 1)
1446: && ! insn_sets_resource_p (dtrial, &needed, 1)
1447: #ifdef HAVE_cc0
1448: && ! sets_cc0_p (PATTERN (dtrial))
1449: #endif
1450: && rtx_equal_p (PATTERN (next_to_match), PATTERN (dtrial))
1451: && eligible_for_delay (delay_insn, slot_number - 1, dtrial))
1452: {
1453: if (! annul_p)
1454: {
1455: update_block (dtrial, thread);
1456: delete_from_delay_slot (dtrial);
1457: INSN_FROM_TARGET_P (next_to_match) = 0;
1458: }
1459: else
1460: merged_insns = gen_rtx (INSN_LIST, SImode, dtrial,
1461: merged_insns);
1462:
1463: if (++slot_number == num_slots)
1464: break;
1465:
1466: next_to_match = XVECEXP (PATTERN (insn), 0, slot_number);
1467: }
1468: }
1469: }
1470:
1471: /* If all insns in the delay slot have been matched and we were previously
1472: annulling the branch, we need not any more. In that case delete all the
1473: merged insns. Also clear the INSN_FROM_TARGET_P bit of each insn the
1474: the delay list so that we know that it isn't only being used at the
1475: target. */
1476: if (next_to_match == 0 && annul_p)
1477: {
1478: for (; merged_insns; merged_insns = XEXP (merged_insns, 1))
1479: {
1480: if (GET_MODE (merged_insns) == SImode)
1481: {
1482: update_block (XEXP (merged_insns, 0), thread);
1483: delete_from_delay_slot (XEXP (merged_insns, 0));
1484: }
1485: else
1486: {
1487: update_block (XEXP (merged_insns, 0), thread);
1488: delete_insn (XEXP (merged_insns, 0));
1489: }
1490: }
1491:
1492: INSN_ANNULLED_BRANCH_P (delay_insn) = 0;
1493:
1494: for (i = 0; i < XVECLEN (PATTERN (insn), 0); i++)
1495: INSN_FROM_TARGET_P (XVECEXP (PATTERN (insn), 0, i)) = 0;
1496: }
1497: }
1498:
1499: /* See if INSN is redundant with an insn in front of TARGET. Often this
1500: is called when INSN is a candidate for a delay slot of TARGET.
1501: DELAY_LIST are insns that will be placed in delay slots of TARGET in front
1502: of INSN. Often INSN will be redundant with an insn in a delay slot of
1503: some previous insn. This happens when we have a series of branches to the
1504: same label; in that case the first insn at the target might want to go
1505: into each of the delay slots.
1506:
1507: If we are not careful, this routine can take up a significant fraction
1508: of the total compilation time (4%), but only wins rarely. Hence we
1509: speed this routine up by making two passes. The first pass goes back
1510: until it hits a label and sees if it find an insn with an identical
1511: pattern. Only in this (relatively rare) event does it check for
1512: data conflicts.
1513:
1514: We do not split insns we encounter. This could cause us not to find a
1515: redundant insn, but the cost of splitting seems greater than the possible
1516: gain in rare cases. */
1517:
1518: static int
1519: redundant_insn_p (insn, target, delay_list)
1520: rtx insn;
1521: rtx target;
1522: rtx delay_list;
1523: {
1524: rtx target_main = target;
1525: rtx ipat = PATTERN (insn);
1526: rtx trial, pat;
1527: struct resources needed, set;
1528: int i;
1529:
1530: /* Scan backwards looking for a match. */
1531: for (trial = PREV_INSN (target); trial; trial = PREV_INSN (trial))
1532: {
1533: if (GET_CODE (trial) == CODE_LABEL)
1534: return 0;
1535:
1536: if (GET_CODE (trial) != INSN && GET_CODE (trial) != JUMP_INSN
1537: && GET_CODE (trial) != JUMP_INSN)
1538: continue;
1539:
1540: pat = PATTERN (trial);
1541: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1542: continue;
1543:
1544: if (GET_CODE (pat) == SEQUENCE)
1545: {
1546: /* Stop for a CALL and its delay slots because it difficult to track
1547: its resource needs correctly. */
1548: if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1549: return 0;
1550:
1551: for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1552: if (GET_CODE (XVECEXP (pat, 0, i)) == GET_CODE (insn)
1553: && rtx_equal_p (PATTERN (XVECEXP (pat, 0, i)), ipat))
1554: break;
1555:
1556: /* If found a match, exit this loop early. */
1557: if (i > 0)
1558: break;
1559: }
1560:
1561: else if (GET_CODE (trial) == GET_CODE (insn) && rtx_equal_p (pat, ipat))
1562: break;
1563: }
1564:
1565: /* If we didn't find an insn that matches, return 0. */
1566: if (trial == 0)
1567: return 0;
1568:
1569: /* See what resources this insn sets and needs. If they overlap, or
1570: if this insn references CC0, it can't be redundant. */
1571:
1572: CLEAR_RESOURCE (&needed);
1573: CLEAR_RESOURCE (&set);
1574: mark_set_resources (insn, &set, 1);
1575: mark_referenced_resources (insn, &needed, 1);
1576:
1577: /* If TARGET is a SEQUENCE, get the main insn. */
1578: if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1579: target_main = XVECEXP (PATTERN (target), 0, 0);
1580:
1581: if (resource_conflicts_p (&needed, &set)
1582: #ifdef HAVE_cc0
1583: || reg_mentioned_p (cc0_rtx, ipat)
1584: #endif
1585: /* The insn requiring the delay may not set anything needed or set by
1586: INSN. */
1587: || insn_sets_resource_p (target_main, &needed, 1)
1588: || insn_sets_resource_p (target_main, &set, 1))
1589: return 0;
1590:
1591: /* Insns we pass may not set either NEEDED or SET, so merge them for
1592: simpler tests. */
1593: needed.memory |= set.memory;
1594: IOR_HARD_REG_SET (needed.regs, set.regs);
1595:
1596: /* This insn isn't redundant if it conflicts with an insn that either is
1597: or will be in a delay slot of TARGET. */
1598:
1599: while (delay_list)
1600: {
1601: if (insn_sets_resource_p (XEXP (delay_list, 0), &needed, 1))
1602: return 0;
1603: delay_list = XEXP (delay_list, 1);
1604: }
1605:
1606: if (GET_CODE (target) == INSN && GET_CODE (PATTERN (target)) == SEQUENCE)
1607: for (i = 1; i < XVECLEN (PATTERN (target), 0); i++)
1608: if (insn_sets_resource_p (XVECEXP (PATTERN (target), 0, i), &needed, 1))
1609: return 0;
1610:
1611: /* Scan backwards until we reach a label or an insn that uses something
1612: INSN sets or sets something insn uses or sets. */
1613:
1614: for (trial = PREV_INSN (target);
1615: trial && GET_CODE (trial) != CODE_LABEL;
1616: trial = PREV_INSN (trial))
1617: {
1618: if (GET_CODE (trial) != INSN && GET_CODE (trial) != CALL_INSN
1619: && GET_CODE (trial) != JUMP_INSN)
1620: continue;
1621:
1622: pat = PATTERN (trial);
1623: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
1624: continue;
1625:
1626: if (GET_CODE (pat) == SEQUENCE)
1627: {
1628: /* If this is a CALL_INSN and its delay slots, it is hard to track
1629: the resource needs properly, so give up. */
1630: if (GET_CODE (XVECEXP (pat, 0, 0)) == CALL_INSN)
1631: return 0;
1632:
1633: /* See if any of the insns in the delay slot match, updating
1634: resource requirements as we go. */
1635: for (i = XVECLEN (pat, 0) - 1; i > 0; i--)
1636: {
1637: rtx candidate = XVECEXP (pat, 0, i);
1638:
1639: /* If an insn will be annulled if the branch is false, it isn't
1640: considered as a possible duplicate insn. */
1641: if (rtx_equal_p (PATTERN (candidate), ipat)
1642: && ! (INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1643: && INSN_FROM_TARGET_P (candidate)))
1644: {
1645: /* Show that this insn will be used in the sequel. */
1646: INSN_FROM_TARGET_P (candidate) = 0;
1647: return 1;
1648: }
1649:
1650: /* Unless this is an annulled insn from the target of a branch,
1651: we must stop if it sets anything needed or set by INSN. */
1652: if ((! INSN_ANNULLED_BRANCH_P (XVECEXP (pat, 0, 0))
1653: || ! INSN_FROM_TARGET_P (candidate))
1654: && insn_sets_resource_p (candidate, &needed, 1))
1655: return 0;
1656: }
1657:
1658:
1659: /* If the insn requiring the delay slot conflicts with INSN, we
1660: must stop. */
1661: if (insn_sets_resource_p (XVECEXP (pat, 0, 0), &needed, 1))
1662: return 0;
1663: }
1664: else
1665: {
1666: /* See if TRIAL is the same as INSN. */
1667: pat = PATTERN (trial);
1668: if (rtx_equal_p (pat, ipat))
1669: return 1;
1670:
1671: /* Can't go any further if TRIAL conflicts with INSN. */
1672: if (insn_sets_resource_p (trial, &needed, 1))
1673: return 0;
1674: }
1675: }
1676:
1677: return 0;
1678: }
1679:
1680: /* Return 1 if THREAD can only be executed in one way. If LABEL is non-zero,
1681: it is the target of the branch insn being scanned. If ALLOW_FALLTHROUGH
1682: is non-zero, we are allowed to fall into this thread; otherwise, we are
1683: not.
1684:
1685: If LABEL is used more than one or we pass a label other than LABEL before
1686: finding an active insn, we do not own this thread. */
1687:
1688: static int
1689: own_thread_p (thread, label, allow_fallthrough)
1690: rtx thread;
1691: rtx label;
1692: int allow_fallthrough;
1693: {
1694: rtx active_insn;
1695: rtx insn;
1696:
1697: /* We don't own the function end. */
1698: if (thread == 0)
1699: return 0;
1700:
1701: /* Get the first active insn, or THREAD, if it is an active insn. */
1702: active_insn = next_active_insn (PREV_INSN (thread));
1703:
1704: for (insn = thread; insn != active_insn; insn = NEXT_INSN (insn))
1705: if (GET_CODE (insn) == CODE_LABEL
1706: && (insn != label || LABEL_NUSES (insn) != 1))
1707: return 0;
1708:
1709: if (allow_fallthrough)
1710: return 1;
1711:
1712: /* Ensure that we reach a BARRIER before any insn or label. */
1713: for (insn = prev_nonnote_insn (thread);
1714: insn == 0 || GET_CODE (insn) != BARRIER;
1715: insn = prev_nonnote_insn (insn))
1716: if (insn == 0
1717: || GET_CODE (insn) == CODE_LABEL
1718: || (GET_CODE (insn) == INSN
1719: && GET_CODE (PATTERN (insn)) != USE
1720: && GET_CODE (PATTERN (insn)) != CLOBBER))
1721: return 0;
1722:
1723: return 1;
1724: }
1725:
1726: /* Find the number of the basic block that starts closest to INSN. Return -1
1727: if we couldn't find such a basic block. */
1728:
1729: static int
1730: find_basic_block (insn)
1731: rtx insn;
1732: {
1733: int i;
1734:
1735: /* Scan backwards to the previous BARRIER. Then see if we can find a
1736: label that starts a basic block. Return the basic block number. */
1737:
1738: for (insn = prev_nonnote_insn (insn);
1739: insn && GET_CODE (insn) != BARRIER;
1740: insn = prev_nonnote_insn (insn))
1741: ;
1742:
1743: /* The start of the function is basic block zero. */
1744: if (insn == 0)
1745: return 0;
1746:
1747: /* See if any of the upcoming CODE_LABELs start a basic block. If we reach
1748: anything other than a CODE_LABEL or note, we can't find this code. */
1749: for (insn = next_nonnote_insn (insn);
1750: insn && GET_CODE (insn) == CODE_LABEL;
1751: insn = next_nonnote_insn (insn))
1752: {
1753: for (i = 0; i < n_basic_blocks; i++)
1754: if (insn == basic_block_head[i])
1755: return i;
1756: }
1757:
1758: return -1;
1759: }
1760:
1761: /* Used for communication between the following two routines, contains
1762: the block number that insn was in. */
1763:
1764: static int current_block_number;
1765:
1766: /* Called via note_stores from update_block_status. It marks the
1767: registers set in this insn as live at the start of the block whose
1768: number is in current_block_number. */
1769:
1770: static void
1771: update_block_from_store (dest, x)
1772: rtx dest;
1773: rtx x;
1774: {
1775: int first_regno, last_regno;
1776: int offset = 0;
1777: int i;
1778:
1779: if (GET_CODE (x) != SET
1780: || (GET_CODE (dest) != REG && (GET_CODE (dest) != SUBREG
1781: || GET_CODE (SUBREG_REG (dest)) != REG)))
1782: return;
1783:
1784: if (GET_CODE (dest) == SUBREG)
1785: first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1786: else
1787: first_regno = REGNO (dest);
1788:
1789: last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1790: for (i = first_regno; i < last_regno; i++)
1791: basic_block_live_at_start[current_block_number][i / HOST_BITS_PER_INT]
1792: |= (1 << (i % HOST_BITS_PER_INT));
1793: }
1794:
1795: /* Called when INSN is being moved from a location near the target of a jump.
1796: If WHERE is the first active insn at the start of its basic block, we can
1797: just mark the registers set in INSN as live at the start of the basic block
1798: that starts immediately before INSN.
1799:
1800: Otherwise, we leave a marker of the form (use (INSN)) immediately in front
1801: of WHERE for mark_target_live_regs. These markers will be deleted when
1802: reorg finishes. */
1803:
1804: static void
1805: update_block (insn, where)
1806: rtx insn;
1807: rtx where;
1808: {
1809: /* Ignore if this was in a delay slot and it came from the target of
1810: a branch. */
1811: if (INSN_FROM_TARGET_P (insn))
1812: return;
1813:
1814: current_block_number = find_basic_block (insn);
1815: if (current_block_number == -1)
1816: return;
1817:
1818: if (where == next_active_insn (basic_block_head[current_block_number]))
1819: note_stores (PATTERN (insn), update_block_from_store);
1820: else
1821: emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
1822:
1823: /* INSN might be making a value live in a block where it didn't use to
1824: be. So recompute liveness information for this block. */
1825: bb_ticks[current_block_number]++;
1826: }
1827:
1828: /* Marks registers possibly live at the current place being scanned by
1829: mark_target_live_regs. Used only by next two function. */
1830:
1831: static HARD_REG_SET current_live_regs;
1832:
1833: /* Marks registers for which we have seen a REG_DEAD note but no assignment.
1834: Also only used by the next two functions. */
1835:
1836: static HARD_REG_SET pending_dead_regs;
1837:
1838: /* Utility function called from mark_target_live_regs via note_stores.
1839: It deadens any CLOBBERed registers and livens any SET registers. */
1840:
1841: static void
1842: update_live_status (dest, x)
1843: rtx dest;
1844: rtx x;
1845: {
1846: int first_regno, last_regno;
1847: int i;
1848:
1849: if (GET_CODE (dest) != REG
1850: && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
1851: return;
1852:
1853: if (GET_CODE (dest) == SUBREG)
1854: first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1855: else
1856: first_regno = REGNO (dest);
1857:
1858: last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1859:
1860: if (GET_CODE (x) == CLOBBER)
1861: for (i = first_regno; i < last_regno; i++)
1862: CLEAR_HARD_REG_BIT (current_live_regs, i);
1863: else
1864: for (i = first_regno; i < last_regno; i++)
1865: {
1866: SET_HARD_REG_BIT (current_live_regs, i);
1867: CLEAR_HARD_REG_BIT (pending_dead_regs, i);
1868: }
1869: }
1870:
1871: /* Similar to next_insn, but ignores insns in the delay slots of
1872: an annulled branch. */
1873:
1874: static rtx
1875: next_insn_no_annul (insn)
1876: rtx insn;
1877: {
1878: if (insn)
1879: {
1880: /* If INSN is an annulled branch, skip any insns from the target
1881: of the branch. */
1882: if (INSN_ANNULLED_BRANCH_P (insn)
1883: && NEXT_INSN (PREV_INSN (insn)) != insn)
1884: while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
1885: insn = NEXT_INSN (insn);
1886:
1887: insn = NEXT_INSN (insn);
1888: if (insn && GET_CODE (insn) == INSN
1889: && GET_CODE (PATTERN (insn)) == SEQUENCE)
1890: insn = XVECEXP (PATTERN (insn), 0, 0);
1891: }
1892:
1893: return insn;
1894: }
1895:
1896: /* Set the resources that are live at TARGET.
1897:
1898: If TARGET is zero, we refer to the end of the current function and can
1899: return our precomputed value.
1900:
1901: Otherwise, we try to find out what is live by consulting the basic block
1902: information. This is tricky, because we must consider the actions of
1903: reload and jump optimization, which occur after the basic block information
1904: has been computed.
1905:
1906: Accordingly, we proceed as follows::
1907:
1908: We find the previous BARRIER and look at all immediately following labels
1909: (with no intervening active insns) to see if any of them start a basic
1910: block. If we hit the start of the function first, we use block 0.
1911:
1912: Once we have found a basic block and a corresponding first insns, we can
1913: accurately compute the live status from basic_block_live_regs and
1914: reg_renumber. (By starting at a label following a BARRIER, we are immune
1915: to actions taken by reload and jump.) Then we scan all insns between
1916: that point and our target. For each CLOBBER (or for call-clobbered regs
1917: when we pass a CALL_INSN), mark the appropriate registers are dead. For
1918: a SET, mark them as live.
1919:
1920: We have to be careful when using REG_DEAD notes because they are not
1921: updated by such things as find_equiv_reg. So keep track of registers
1922: marked as dead that haven't been assigned to, and mark them dead at the
1923: next CODE_LABEL since reload and jump won't propagate values across labels.
1924:
1925: If we cannot find the start of a basic block (should be a very rare
1926: case, if it can happen at all), mark everything as potentially live.
1927:
1928: Next, scan forward from TARGET looking for things set or clobbered
1929: before they are used. These are not live.
1930:
1931: Because we can be called many times on the same target, save our results
1932: in a hash table indexed by INSN_UID. */
1933:
1934: static void
1935: mark_target_live_regs (target, res)
1936: rtx target;
1937: struct resources *res;
1938: {
1939: int b = -1;
1940: int i;
1941: struct target_info *tinfo;
1942: rtx insn, next;
1943: rtx jump_insn = 0;
1944: HARD_REG_SET scratch;
1945: struct resources set, needed;
1946: int jump_count = 0;
1947:
1948: /* Handle end of function. */
1949: if (target == 0)
1950: {
1951: *res = end_of_function_needs;
1952: return;
1953: }
1954:
1955: /* We have to assume memory is needed, but the CC isn't. */
1956: res->memory = 1;
1957: res->volatil = 0;
1958: res->cc = 0;
1959:
1960: /* See if we have computed this value already. */
1961: for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1962: tinfo; tinfo = tinfo->next)
1963: if (tinfo->uid == INSN_UID (target))
1964: break;
1965:
1966: /* Start by getting the basic block number. If we have saved information,
1967: we can get it from there unless the insn at the start of the basic block
1968: has been deleted. */
1969: if (tinfo && tinfo->block != -1
1970: && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
1971: b = tinfo->block;
1972:
1973: if (b == -1)
1974: b = find_basic_block (target);
1975:
1976: if (tinfo)
1977: {
1978: /* If the information is up-to-date, use it. Otherwise, we will
1979: update it below. */
1980: if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
1981: {
1982: COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
1983: return;
1984: }
1985: }
1986: else
1987: {
1988: /* Allocate a place to put our results and chain it into the
1989: hash table. */
1990: tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
1991: tinfo->uid = INSN_UID (target);
1992: tinfo->block = b;
1993: tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1994: target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
1995: }
1996:
1997: CLEAR_HARD_REG_SET (pending_dead_regs);
1998:
1999: /* If we found a basic block, get the live registers from it and update
2000: them with anything set or killed between its start and the insn before
2001: TARGET. Otherwise, we must assume everything is live. */
2002: if (b != -1)
2003: {
2004: regset regs_live = basic_block_live_at_start[b];
2005: int offset, bit, j;
2006: int regno;
2007: rtx start_insn, stop_insn;
2008:
2009: /* Compute hard regs live at start of block -- this is the real hard regs
2010: marked live, plus live pseudo regs that have been renumbered to
2011: hard regs. */
2012:
2013: #ifdef HARD_REG_SET
2014: current_live_regs = *regs_live;
2015: #else
2016: COPY_HARD_REG_SET (current_live_regs, regs_live);
2017: #endif
2018:
2019: for (offset = 0, i = 0; offset < regset_size; offset++)
2020: {
2021: if (regs_live[offset] == 0)
2022: i += HOST_BITS_PER_INT;
2023: else
2024: for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
2025: if ((regs_live[offset] & bit)
2026: && (regno = reg_renumber[i]) >= 0)
2027: for (j = regno;
2028: j < regno + HARD_REGNO_NREGS (regno,
2029: PSEUDO_REGNO_MODE (i));
2030: j++)
2031: SET_HARD_REG_BIT (current_live_regs, j);
2032: }
2033:
2034: /* Get starting and ending insn, handling the case where each might
2035: be a SEQUENCE. */
2036: start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2037: stop_insn = target;
2038:
2039: if (GET_CODE (start_insn) == INSN
2040: && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2041: start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2042:
2043: if (GET_CODE (stop_insn) == INSN
2044: && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2045: stop_insn = next_insn (PREV_INSN (stop_insn));
2046:
2047: for (insn = start_insn; insn != stop_insn;
2048: insn = next_insn_no_annul (insn))
2049: {
2050: rtx link;
2051: rtx real_insn = insn;
2052:
2053: /* If this insn is from the target of a branch, it isn't going to
2054: be used in the sequel. If it is used in both cases, this
2055: test will not be true. */
2056: if (INSN_FROM_TARGET_P (insn))
2057: continue;
2058:
2059: /* If this insn is a USE made by update_block, we care about the
2060: underlying insn. */
2061: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2062: && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
2063: || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
2064: || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
2065: real_insn = XEXP (PATTERN (insn), 0);
2066:
2067: if (GET_CODE (real_insn) == CALL_INSN)
2068: {
2069: /* CALL clobbers all call-used regs that aren't fixed except
2070: sp, ap, and fp. Do this before setting the result of the
2071: call live. */
2072: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2073: if (call_used_regs[i]
2074: && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2075: && i != ARG_POINTER_REGNUM
2076: #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2077: && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2078: #endif
2079: #ifdef PIC_OFFSET_TABLE_REGNUM
2080: && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2081: #endif
2082: )
2083: CLEAR_HARD_REG_BIT (current_live_regs, i);
2084: }
2085:
2086: /* Mark anything killed in an insn to be deadened at the next
2087: label. Ignore USE insns; the only REG_DEAD notes will be for
2088: parameters. But they might be early. A CALL_INSN will usually
2089: clobber registers used for parameters. It isn't worth bothering
2090: with the unlikely case when it won't. */
2091: if ((GET_CODE (real_insn) == INSN
2092: && GET_CODE (PATTERN (real_insn)) != USE)
2093: || GET_CODE (real_insn) == JUMP_INSN
2094: || GET_CODE (real_insn) == CALL_INSN)
2095: {
2096: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2097: if (REG_NOTE_KIND (link) == REG_DEAD
2098: && GET_CODE (XEXP (link, 0)) == REG
2099: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2100: {
2101: int first_regno = REGNO (XEXP (link, 0));
2102: int last_regno
2103: = (first_regno
2104: + HARD_REGNO_NREGS (first_regno,
2105: GET_MODE (XEXP (link, 0))));
2106:
2107: for (i = first_regno; i < last_regno; i++)
2108: SET_HARD_REG_BIT (pending_dead_regs, i);
2109: }
2110:
2111: note_stores (PATTERN (real_insn), update_live_status);
2112:
2113: /* If any registers were unused after this insn, kill them.
2114: These notes will always be accurate. */
2115: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2116: if (REG_NOTE_KIND (link) == REG_UNUSED
2117: && GET_CODE (XEXP (link, 0)) == REG
2118: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2119: {
2120: int first_regno = REGNO (XEXP (link, 0));
2121: int last_regno
2122: = (first_regno
2123: + HARD_REGNO_NREGS (first_regno,
2124: GET_MODE (XEXP (link, 0))));
2125:
2126: for (i = first_regno; i < last_regno; i++)
2127: CLEAR_HARD_REG_BIT (current_live_regs, i);
2128: }
2129: }
2130:
2131: if (GET_CODE (real_insn) == CODE_LABEL)
2132: {
2133: /* A label clobbers the pending dead registers since neither
2134: reload nor jump will propagate a value across a label. */
2135: AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2136: CLEAR_HARD_REG_SET (pending_dead_regs);
2137: }
2138: }
2139:
2140: COPY_HARD_REG_SET (res->regs, current_live_regs);
2141: tinfo->block = b;
2142: tinfo->bb_tick = bb_ticks[b];
2143: }
2144: else
2145: /* We didn't find the start of a basic block. Assume everything
2146: in use. This should happen only extremely rarely. */
2147: SET_HARD_REG_SET (res->regs);
2148:
2149: /* Now step forward from TARGET looking for registers that are set before
2150: they are used. These are dead. If we pass a label, any pending dead
2151: registers that weren't yet used can be made dead. Stop when we pass a
2152: conditional JUMP_INSN; follow the first few unconditional branches. */
2153:
2154: CLEAR_RESOURCE (&set);
2155: CLEAR_RESOURCE (&needed);
2156:
2157: for (insn = target; insn; insn = next)
2158: {
2159: rtx main_insn = insn;
2160:
2161: next = NEXT_INSN (insn);
2162: switch (GET_CODE (insn))
2163: {
2164: case CODE_LABEL:
2165: AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2166: AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2167: CLEAR_HARD_REG_SET (pending_dead_regs);
2168: continue;
2169:
2170: case BARRIER:
2171: case NOTE:
2172: continue;
2173:
2174: case INSN:
2175: if (GET_CODE (PATTERN (insn)) == USE
2176: || GET_CODE (PATTERN (insn)) == CLOBBER)
2177: continue;
2178: if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2179: main_insn = XVECEXP (PATTERN (insn), 0, 0);
2180: }
2181:
2182: if (GET_CODE (main_insn) == JUMP_INSN)
2183: {
2184: if (jump_count++ < 10
2185: && (simplejump_p (main_insn)
2186: || GET_CODE (PATTERN (main_insn)) == RETURN))
2187: {
2188: next = next_active_insn (JUMP_LABEL (main_insn));
2189: if (jump_insn == 0)
2190: jump_insn = insn;
2191: }
2192: else
2193: break;
2194: }
2195:
2196: mark_referenced_resources (insn, &needed, 1);
2197: mark_set_resources (insn, &set, 1);
2198:
2199: COPY_HARD_REG_SET (scratch, set.regs);
2200: AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2201: AND_COMPL_HARD_REG_SET (res->regs, scratch);
2202: }
2203:
2204: /* If we hit an unconditional branch, we have another way of finding out
2205: what is live: we can see what is live at the branch target and include
2206: anything used but not set before the branch. The only things that are
2207: live are those that are live using the above test and the test below. */
2208: if (jump_insn)
2209: {
2210: rtx jump_target = (GET_CODE (jump_insn) == INSN
2211: ? JUMP_LABEL (XVECEXP (PATTERN (jump_insn), 0, 0))
2212: : JUMP_LABEL (jump_insn));
2213: struct resources new_resources;
2214: rtx stop_insn = next_active_insn (jump_insn);
2215:
2216: mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2217: CLEAR_RESOURCE (&set);
2218: CLEAR_RESOURCE (&needed);
2219:
2220: /* Include JUMP_INSN in the needed registers. */
2221: for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2222: {
2223: mark_referenced_resources (insn, &needed, 1);
2224:
2225: COPY_HARD_REG_SET (scratch, needed.regs);
2226: AND_COMPL_HARD_REG_SET (scratch, set.regs);
2227: IOR_HARD_REG_SET (new_resources.regs, scratch);
2228:
2229: mark_set_resources (insn, &set, 1);
2230: }
2231:
2232: AND_HARD_REG_SET (res->regs, new_resources.regs);
2233: }
2234:
2235: COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2236: }
2237:
2238: /* Scan a function looking for insns that need a delay slot and find insns to
2239: put into the delay slot.
2240:
2241: NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2242: as calls). We do these first since we don't want jump insns (that are
2243: easier to fill) to get the only insns that could be used for non-jump insns.
2244: When it is zero, only try to fill JUMP_INSNs.
2245:
2246: When slots are filled in this manner, the insns (including the
2247: delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2248: it is possible to tell whether a delay slot has really been filled
2249: or not. `final' knows how to deal with this, by communicating
2250: through FINAL_SEQUENCE. */
2251:
2252: static void
2253: fill_simple_delay_slots (first, non_jumps_p)
2254: rtx first;
2255: {
2256: register rtx insn, pat, trial, next_trial;
2257: register int i;
2258: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2259: struct resources needed, set;
2260: register int slots_to_fill, slots_filled;
2261: rtx delay_list;
2262:
2263: for (i = 0; i < num_unfilled_slots; i++)
2264: {
2265: /* Get the next insn to fill. If it has already had any slots assigned,
2266: we can't do anything with it. Maybe we'll improve this later. */
2267:
2268: insn = unfilled_slots_base[i];
2269: if (insn == 0
2270: || INSN_DELETED_P (insn)
2271: || (GET_CODE (insn) == INSN
2272: && GET_CODE (PATTERN (insn)) == SEQUENCE)
2273: || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2274: || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2275: continue;
2276:
2277: slots_to_fill = num_delay_slots (insn);
2278: if (slots_to_fill == 0)
2279: abort ();
2280:
2281: /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2282: says how many. After initialization, scan backwards from the
2283: insn to search for a potential delay-slot candidate. Stop
2284: searching when a label or jump is hit.
2285:
2286: For each candidate, if it is to go into the delay slot (moved
2287: forward in execution sequence), it must not need or set any resources
2288: that were set by later insns and must not set any resources that
2289: are needed for those insns.
2290:
2291: The delay slot insn itself sets resources unless it is a call
2292: (in which case the called routine, not the insn itself, is doing
2293: the setting). */
2294:
2295: slots_filled = 0;
2296: delay_list = 0;
2297: CLEAR_RESOURCE (&needed);
2298: CLEAR_RESOURCE (&set);
2299: mark_set_resources (insn, &set, 0);
2300: mark_referenced_resources (insn, &needed, 0);
2301:
2302: for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2303: trial = next_trial)
2304: {
2305: next_trial = prev_nonnote_insn (trial);
2306:
2307: /* This must be an INSN or CALL_INSN. */
2308: pat = PATTERN (trial);
2309:
2310: /* USE and CLOBBER at this level was just for flow; ignore it. */
2311: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2312: continue;
2313:
2314: /* Check for resource conflict first, to avoid unnecessary
2315: splitting. */
2316: if (! insn_references_resource_p (trial, &set, 1)
2317: && ! insn_sets_resource_p (trial, &set, 1)
2318: && ! insn_sets_resource_p (trial, &needed, 1)
2319: #ifdef HAVE_cc0
2320: /* Can't separate set of cc0 from its use. */
2321: && ! (reg_mentioned_p (cc0_rtx, pat)
2322: && ! sets_cc0_p (cc0_rtx, pat))
2323: #endif
2324: )
2325: {
2326: trial = try_split (pat, trial, 1);
2327: next_trial = prev_nonnote_insn (trial);
2328: if (eligible_for_delay (insn, slots_filled, trial))
2329: {
2330: /* In this case, we are searching backward, so if we
2331: find insns to put on the delay list, we want
2332: to put them at the head, rather than the
2333: tail, of the list. */
2334:
2335: delay_list = gen_rtx (INSN_LIST, VOIDmode,
2336: trial, delay_list);
2337: update_block (trial, trial);
2338: delete_insn (trial);
2339: if (slots_to_fill == ++slots_filled)
2340: break;
2341: continue;
2342: }
2343: }
2344:
2345: mark_set_resources (trial, &set, 1);
2346: mark_referenced_resources (trial, &needed, 1);
2347: }
2348:
2349: if (slots_filled == slots_to_fill)
2350: /* happy. */ ;
2351:
2352: /* If all needed slots haven't been filled, we come here. */
2353:
2354: /* Try to optimize case of jumping around a single insn. */
2355: #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2356: else if (delay_list == 0
2357: && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
2358: {
2359: delay_list = optimize_skip (insn);
2360: if (delay_list)
2361: slots_filled += 1;
2362: }
2363: #endif
2364:
2365: /* @@ This would be a good place to optimize:
2366:
2367: call _foo call _foo
2368: nop add %o7,.-L1,%o7
2369: b,a L1
2370: nop
2371:
2372: Someday... */
2373:
2374: /* Try to get insns from beyond the insn needing the delay slot.
2375: These insns can neither set or reference resources set in insns being
2376: skipped, cannot set resources in the insn being skipped, and, if this
2377: is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2378: call might not return).
2379:
2380: If this is a conditional jump, see if it merges back to us early
2381: enough for us to pick up insns from the merge point. Don't do
2382: this if there is another branch to our label unless we pass all of
2383: them.
2384:
2385: Another similar merge is if we jump to the same place that a
2386: later unconditional jump branches to. In that case, we don't
2387: care about the number of uses of our label. */
2388:
2389: else if (GET_CODE (insn) != JUMP_INSN
2390: || (condjump_p (insn) && ! simplejump_p (insn)
2391: && JUMP_LABEL (insn) != 0))
2392: {
2393: rtx target = 0;
2394: int maybe_never = 0;
2395: int passed_label = 0;
2396: int target_uses;
2397: struct resources needed_at_jump;
2398:
2399: CLEAR_RESOURCE (&needed);
2400: CLEAR_RESOURCE (&set);
2401:
2402: if (GET_CODE (insn) == CALL_INSN)
2403: {
2404: mark_set_resources (insn, &set, 1);
2405: mark_referenced_resources (insn, &needed, 1);
2406: maybe_never = 1;
2407: }
2408: else if (GET_CODE (insn) == JUMP_INSN)
2409: {
2410: /* Get our target and show how many more uses we want to
2411: see before we hit the label. */
2412: target = JUMP_LABEL (insn);
2413: target_uses = LABEL_NUSES (target) - 1;
2414: }
2415:
2416: for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2417: {
2418: rtx pat, trial_delay;
2419:
2420: next_trial = next_nonnote_insn (trial);
2421:
2422: if (GET_CODE (trial) == CODE_LABEL)
2423: {
2424: passed_label = 1;
2425:
2426: /* If this is our target, see if we have seen all its uses.
2427: If so, indicate we have passed our target and ignore it.
2428: All other labels cause us to stop our search. */
2429: if (trial == target && target_uses == 0)
2430: {
2431: target = 0;
2432: continue;
2433: }
2434: else
2435: break;
2436: }
2437: else if (GET_CODE (trial) == BARRIER)
2438: break;
2439:
2440: /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2441: pat = PATTERN (trial);
2442:
2443: /* Stand-alone USE and CLOBBER are just for flow. */
2444: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2445: continue;
2446:
2447: /* If this already has filled delay slots, get the insn needing
2448: the delay slots. */
2449: if (GET_CODE (pat) == SEQUENCE)
2450: trial_delay = XVECEXP (pat, 0, 0);
2451: else
2452: trial_delay = trial;
2453:
2454: /* If this is a jump insn to our target, indicate that we have
2455: seen another jump to it. If we aren't handling a conditional
2456: jump, stop our search. Otherwise, compute the needs at its
2457: target and add them to NEEDED. */
2458: if (GET_CODE (trial_delay) == JUMP_INSN)
2459: {
2460: if (target == 0)
2461: break;
2462: else if (JUMP_LABEL (trial_delay) == target)
2463: target_uses--;
2464: else
2465: {
2466: mark_target_live_regs
2467: (next_active_insn (JUMP_LABEL (trial_delay)),
2468: &needed_at_jump);
2469: needed.memory |= needed_at_jump.memory;
2470: IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
2471: }
2472: }
2473:
2474: /* See if we have a resource problem before we try to
2475: split. */
2476: if (target == 0
2477: && GET_CODE (pat) != SEQUENCE
2478: && ! insn_references_resource_p (trial, &set, 1)
2479: && ! insn_sets_resource_p (trial, &set, 1)
2480: && ! insn_sets_resource_p (trial, &needed, 1)
2481: #ifdef HAVE_cc0
2482: && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2483: #endif
2484: && ! (maybe_never && may_trap_p (pat))
2485: && (trial = try_split (pat, trial, 0))
2486: && eligible_for_delay (insn, slots_filled, trial))
2487: {
2488: next_trial = next_nonnote_insn (trial);
2489: delay_list = add_to_delay_list (trial, delay_list);
2490:
2491: #ifdef HAVE_cc0
2492: if (reg_mentioned_p (cc0_rtx, pat))
2493: link_cc0_insns (trial);
2494: #endif
2495:
2496: if (passed_label)
2497: update_block (trial, trial);
2498: delete_insn (trial);
2499: if (slots_to_fill == ++slots_filled)
2500: break;
2501: continue;
2502: }
2503:
2504: mark_set_resources (trial, &set, 1);
2505: mark_referenced_resources (trial, &needed, 1);
2506:
2507: /* Ensure we don't put insns between the setting of cc and the
2508: comparison by moving a setting of cc into an earlier delay
2509: slot since these insns could clobber the condition code. */
2510: set.cc = 1;
2511:
2512: /* If this is a call or jump, we might not get here. */
2513: if (GET_CODE (trial) == CALL_INSN
2514: || GET_CODE (trial) == JUMP_INSN)
2515: maybe_never = 1;
2516: }
2517:
2518: /* If there are slots left to fill and our search was stopped by an
2519: unconditional branch, try the insn at the branch target. We can
2520: redirect the branch if it works. */
2521: if (slots_to_fill != slots_filled
2522: && trial
2523: && GET_CODE (trial) == JUMP_INSN
2524: && simplejump_p (trial)
2525: && (target == 0 || JUMP_LABEL (trial) == target)
2526: && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2527: && ! (GET_CODE (next_trial) == INSN
2528: && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2529: && ! insn_references_resource_p (next_trial, &set, 1)
2530: && ! insn_sets_resource_p (next_trial, &set, 1)
2531: && ! insn_sets_resource_p (next_trial, &needed, 1)
2532: #ifdef HAVE_cc0
2533: && ! (reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2534: && ! sets_cc0_p (PATTERN (next_trial)))
2535: #endif
2536: && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2537: && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2538: && eligible_for_delay (insn, slots_filled, next_trial))
2539: {
2540: rtx new_label = next_active_insn (next_trial);
2541:
2542: if (new_label != 0)
2543: new_label = get_label_before (new_label);
2544:
2545: delay_list
2546: = add_to_delay_list (copy_rtx (next_trial), delay_list);
2547: slots_filled++;
2548: redirect_jump (trial, new_label);
2549:
2550: /* If we merged because we both jumped to the same place,
2551: redirect the original insn also. */
2552: if (target)
2553: redirect_jump (insn, new_label);
2554: }
2555: }
2556:
2557: if (delay_list)
2558: unfilled_slots_base[i]
2559: = emit_delay_sequence (insn, delay_list,
2560: slots_filled, slots_to_fill);
2561:
2562: if (slots_to_fill == slots_filled)
2563: unfilled_slots_base[i] = 0;
2564:
2565: note_delay_statistics (slots_filled, 0);
2566: }
2567:
2568: #ifdef DELAY_SLOTS_FOR_EPILOGUE
2569: /* See if the epilogue needs any delay slots. Try to fill them if so.
2570: The only thing we can do is scan backwards from the end of the
2571: function. If we did this in a previous pass, it is incorrect to do it
2572: again. */
2573: if (current_function_epilogue_delay_list)
2574: return;
2575:
2576: slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2577: if (slots_to_fill == 0)
2578: return;
2579:
2580: slots_filled = 0;
2581: CLEAR_RESOURCE (&needed);
2582: CLEAR_RESOURCE (&set);
2583:
2584: for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2585: trial = PREV_INSN (trial))
2586: {
2587: if (GET_CODE (trial) == NOTE)
2588: continue;
2589: pat = PATTERN (trial);
2590: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2591: continue;
2592:
2593: if (! insn_references_resource_p (trial, &set, 1)
2594: && ! insn_sets_resource_p (trial, &needed, 1)
2595: #ifdef HAVE_cc0
2596: /* Don't want to mess with cc0 here. */
2597: && ! reg_mentioned_p (cc0_rtx, pat)
2598: #endif
2599: )
2600: {
2601: trial = try_split (pat, trial, 1);
2602: if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2603: {
2604: /* Here as well we are searching backward, so put the
2605: insns we find on the head of the list. */
2606:
2607: current_function_epilogue_delay_list
2608: = gen_rtx (INSN_LIST, VOIDmode, trial,
2609: current_function_epilogue_delay_list);
2610: mark_referenced_resources (trial, &end_of_function_needs, 1);
2611: update_block (trial, trial);
2612: delete_insn (trial);
2613:
2614: /* Clear deleted bit so final.c will output the insn. */
2615: INSN_DELETED_P (trial) = 0;
2616:
2617: if (slots_to_fill == ++slots_filled)
2618: break;
2619: continue;
2620: }
2621: }
2622:
2623: mark_set_resources (trial, &set, 1);
2624: mark_referenced_resources (trial, &needed, 1);
2625: }
2626:
2627: note_delay_statistics (slots_filled, 0);
2628: #endif
2629: }
2630:
2631: /* Try to find insns to place in delay slots.
2632:
2633: INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2634: or is an unconditional branch if CONDITION is const_true_rtx.
2635: *PSLOTS_FILLED is updated with the number of slots that we have filled.
2636:
2637: THREAD is a flow-of-control, either the insns to be executed if the
2638: branch is true or if the branch is false, THREAD_IF_TRUE says which.
2639:
2640: OPPOSITE_THREAD is the thread in the opposite direction. It is used
2641: to see if any potential delay slot insns set things needed there.
2642:
2643: LIKELY is non-zero if it is extremely likely that the branch will be
2644: taken and THREAD_IF_TRUE is set. This is used for the branch at the
2645: end of a loop back up to the top.
2646:
2647: OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2648: thread. I.e., it is the fallthrough code of our jump or the target of the
2649: jump when we are the only jump going there.
2650:
2651: If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2652: case, we can only take insns from the head of the thread for our delay
2653: slot. We then adjust the jump to point after the insns we have taken. */
2654:
2655: static rtx
2656: fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2657: thread_if_true, own_thread, own_opposite_thread,
2658: slots_to_fill, pslots_filled)
2659: rtx insn;
2660: rtx condition;
2661: rtx thread, opposite_thread;
2662: int likely;
2663: int thread_if_true;
2664: int own_thread, own_opposite_thread;
2665: int slots_to_fill, *pslots_filled;
2666: {
2667: rtx new_thread = thread;
2668: rtx delay_list = 0;
2669: struct resources opposite_needed, set, needed;
2670: rtx trial;
2671: int lose = 0;
2672: int must_annul = 0;
2673:
2674: /* Validate our arguments. */
2675: if ((condition == const_true_rtx && ! thread_if_true)
2676: || (! own_thread && ! thread_if_true))
2677: abort ();
2678:
2679: /* If our thread is the end of subroutine, we can't get any delay
2680: insns from that. */
2681: if (thread == 0)
2682: return 0;
2683:
2684: /* If this is an unconditional branch, nothing is needed at the
2685: opposite thread. Otherwise, compute what is needed there. */
2686: if (condition == const_true_rtx)
2687: CLEAR_RESOURCE (&opposite_needed);
2688: else
2689: mark_target_live_regs (opposite_thread, &opposite_needed);
2690:
2691: /* Scan insns at THREAD. We are looking for an insn that can be removed
2692: from THREAD (it neither sets nor references resources that were set
2693: ahead of it and it doesn't set anything needs by the insns ahead of
2694: it) and that either can be placed in an annulling insn or aren't
2695: needed at OPPOSITE_THREAD. */
2696:
2697: CLEAR_RESOURCE (&needed);
2698: CLEAR_RESOURCE (&set);
2699:
2700: /* If we do not own this thread, we must stop as soon as we find
2701: something that we can't put in a delay slot, since all we can do
2702: is branch into THREAD at a later point. Therefore, labels stop
2703: the search if this is not the `true' thread. */
2704:
2705: for (trial = thread;
2706: ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2707: trial = next_nonnote_insn (trial))
2708: {
2709: rtx pat;
2710:
2711: /* If we have passed a label, we no longer own this thread. */
2712: if (GET_CODE (trial) == CODE_LABEL)
2713: {
2714: own_thread = 0;
2715: continue;
2716: }
2717:
2718: pat = PATTERN (trial);
2719: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2720: continue;
2721:
2722: /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2723: don't separate or copy insns that set and use CC0. */
2724: if (! insn_references_resource_p (trial, &set, 1)
2725: && ! insn_sets_resource_p (trial, &set, 1)
2726: && ! insn_sets_resource_p (trial, &needed, 1)
2727: #ifdef HAVE_cc0
2728: && ! (reg_mentioned_p (cc0_rtx, pat)
2729: && (! own_thread || ! sets_cc0_p (pat)))
2730: #endif
2731: )
2732: {
2733: /* If TRIAL is redundant with some insn before INSN, we don't
2734: actually need to add it to the delay list; we can merely pretend
2735: we did. */
2736: if (redundant_insn_p (trial, insn, delay_list))
2737: {
2738: if (own_thread)
2739: {
2740: update_block (trial, thread);
2741: delete_insn (trial);
2742: }
2743: else
2744: new_thread = next_active_insn (trial);
2745:
2746: continue;
2747: }
2748:
2749: /* There are two ways we can win: If TRIAL doesn't set anything
2750: needed at the opposite thread and can't trap, or if it can
2751: go into an annulled delay slot. */
2752: if (condition == const_true_rtx
2753: || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2754: && ! may_trap_p (pat)))
2755: {
2756: trial = try_split (pat, trial, 0);
2757: pat = PATTERN (trial);
2758: if (eligible_for_delay (insn, *pslots_filled, trial))
2759: goto winner;
2760: }
2761: else if (0
2762: #ifdef ANNUL_IFTRUE_SLOTS
2763: || ! thread_if_true
2764: #endif
2765: #ifdef ANNUL_IFFALSE_SLOTS
2766: || thread_if_true
2767: #endif
2768: )
2769: {
2770: trial = try_split (pat, trial, 0);
2771: pat = PATTERN (trial);
2772: if ((thread_if_true
2773: ? eligible_for_annul_false (insn, *pslots_filled, trial)
2774: : eligible_for_annul_true (insn, *pslots_filled, trial)))
2775: {
2776: rtx temp;
2777:
2778: must_annul = 1;
2779: winner:
2780:
2781: #ifdef HAVE_cc0
2782: if (reg_mentioned_p (cc0_rtx, pat))
2783: link_cc0_insns (trial);
2784: #endif
2785:
2786: /* If we own this thread, delete the insn. If this is the
2787: destination of a branch, show that a basic block status
2788: may have been updated. In any case, mark the new
2789: starting point of this thread. */
2790: if (own_thread)
2791: {
2792: update_block (trial, thread);
2793: delete_insn (trial);
2794: }
2795: else
2796: new_thread = next_active_insn (trial);
2797:
2798: temp = own_thread ? trial : copy_rtx (trial);
2799: if (thread_if_true)
2800: INSN_FROM_TARGET_P (temp) = 1;
2801:
2802: delay_list = add_to_delay_list (temp, delay_list);
2803:
2804: if (slots_to_fill == ++(*pslots_filled))
2805: {
2806: /* Even though we have filled all the slots, we
2807: may be branching to a location that has a
2808: redundant insn. Skip any if so. */
2809: while (new_thread && ! own_thread
2810: && ! insn_sets_resource_p (new_thread, &set, 1)
2811: && ! insn_sets_resource_p (new_thread, &needed, 1)
2812: && ! insn_references_resource_p (new_thread,
2813: &set, 1)
2814: && redundant_insn_p (new_thread, insn,
2815: delay_list))
2816: new_thread = next_active_insn (new_thread);
2817: break;
2818: }
2819:
2820: continue;
2821: }
2822: }
2823: }
2824:
2825: /* This insn can't go into a delay slot. */
2826: lose = 1;
2827: mark_set_resources (trial, &set, 1);
2828: mark_referenced_resources (trial, &needed, 1);
2829:
2830: /* Ensure we don't put insns between the setting of cc and the comparison
2831: by moving a setting of cc into an earlier delay slot since these insns
2832: could clobber the condition code. */
2833: set.cc = 1;
2834:
2835: /* If this insn is a register-register copy and the next insn has
2836: a use of our destination, change it to use our source. That way,
2837: it will become a candidate for our delay slot the next time
2838: through this loop. This case occurs commonly in loops that
2839: scan a list.
2840:
2841: We could check for more complex cases than those tested below,
2842: but it doesn't seem worth it. It might also be a good idea to try
2843: to swap the two insns. That might do better. */
2844:
2845: if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2846: && GET_CODE (SET_SRC (pat)) == REG
2847: && GET_CODE (SET_DEST (pat)) == REG)
2848: {
2849: rtx next = next_nonnote_insn (trial);
2850: int our_dest = REGNO (SET_DEST (pat));
2851:
2852: if (next && GET_CODE (next) == INSN
2853: && GET_CODE (PATTERN (next)) == SET
2854: && GET_CODE (SET_DEST (PATTERN (next))) == REG
2855: && REGNO (SET_DEST (PATTERN (next))) != our_dest
2856: && refers_to_regno_p (our_dest, our_dest + 1,
2857: SET_SRC (PATTERN (next)), 0))
2858: validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2859: }
2860: }
2861:
2862: /* If we stopped on a branch insn that has delay slots, see if we can
2863: steal some of the insns in those slots. */
2864: if (trial && GET_CODE (trial) == INSN
2865: && GET_CODE (PATTERN (trial)) == SEQUENCE
2866: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2867: {
2868: /* If this is the `true' thread, we will want to follow the jump,
2869: so we can only do this if we have taken everything up to here. */
2870: if (thread_if_true && trial == new_thread)
2871: delay_list
2872: = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2873: delay_list, &set, &needed,
2874: &opposite_needed, slots_to_fill,
2875: pslots_filled, &must_annul,
2876: &new_thread);
2877: else if (! thread_if_true)
2878: delay_list
2879: = steal_delay_list_from_fallthrough (insn, condition,
2880: PATTERN (trial),
2881: delay_list, &set, &needed,
2882: &opposite_needed, slots_to_fill,
2883: pslots_filled, &must_annul);
2884: }
2885:
2886: /* If we haven't found anything for this delay slot and it is very
2887: likely that the branch will be taken, see if the insn at our target
2888: increments or decrements a register. If so, try to place the opposite
2889: arithmetic insn after the jump insn and put the arithmetic insn in the
2890: delay slot. If we can't do this, return. */
2891: if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
2892: {
2893: rtx pat = PATTERN (new_thread);
2894: rtx dest;
2895: rtx src;
2896:
2897: trial = try_split (pat, new_thread, 0);
2898: pat = PATTERN (trial);
2899:
2900: if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
2901: || ! eligible_for_delay (insn, 0, trial))
2902: return 0;
2903:
2904: dest = SET_DEST (pat), src = SET_SRC (pat);
2905: if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
2906: && rtx_equal_p (XEXP (src, 0), dest))
2907: {
2908: rtx other = XEXP (src, 1);
2909: rtx new_arith;
2910: rtx ninsn;
2911:
2912: /* If this is a constant adjustment, use the same code with
2913: the negated constant. Otherwise, reverse the sense of the
2914: arithmetic. */
2915: if (GET_CODE (other) == CONST_INT)
2916: new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
2917: negate_rtx (GET_MODE (src), other));
2918: else
2919: new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
2920: GET_MODE (src), dest, other);
2921:
2922: ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
2923: insn);
2924:
2925: if (recog_memoized (ninsn) < 0
2926: || (insn_extract (ninsn),
2927: ! constrain_operands (INSN_CODE (ninsn), 1)))
2928: {
2929: delete_insn (ninsn);
2930: return 0;
2931: }
2932:
2933: if (own_thread)
2934: {
2935: update_block (trial, thread);
2936: delete_insn (trial);
2937: }
2938: else
2939: new_thread = next_active_insn (trial);
2940:
2941: ninsn = own_thread ? trial : copy_rtx (trial);
2942: if (thread_if_true)
2943: INSN_FROM_TARGET_P (ninsn) = 1;
2944:
2945: delay_list = add_to_delay_list (ninsn, 0);
2946: (*pslots_filled)++;
2947: }
2948: }
2949:
2950: if (delay_list && must_annul)
2951: INSN_ANNULLED_BRANCH_P (insn) = 1;
2952:
2953: /* If we are to branch into the middle of this thread, find an appropriate
2954: label or make a new one if none, and redirect INSN to it. If we hit the
2955: end of the function, use the end-of-function label. */
2956: if (new_thread != thread)
2957: {
2958: rtx label;
2959:
2960: if (! thread_if_true)
2961: abort ();
2962:
2963: if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2964: && (simplejump_p (new_thread)
2965: || GET_CODE (PATTERN (new_thread)) == RETURN))
2966: new_thread = follow_jumps (JUMP_LABEL (new_thread), 1);
2967:
2968: if (new_thread == 0)
2969: label = find_end_label ();
2970: else if (GET_CODE (new_thread) == CODE_LABEL)
2971: label = new_thread;
2972: else
2973: label = get_label_before (new_thread);
2974:
2975: redirect_jump (insn, label);
2976: }
2977:
2978: return delay_list;
2979: }
2980:
2981: /* Make another attempt to find insns to place in delay slots.
2982:
2983: We previously looked for insns located in front of the delay insn
2984: and, for non-jump delay insns, located behind the delay insn.
2985:
2986: Here only try to schedule jump insns and try to move insns from either
2987: the target or the following insns into the delay slot. If annulling is
2988: supported, we will be likely to do this. Otherwise, we can do this only
2989: if safe. */
2990:
2991: static void
2992: fill_eager_delay_slots (first)
2993: rtx first;
2994: {
2995: register rtx insn;
2996: register int i;
2997: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2998:
2999: for (i = 0; i < num_unfilled_slots; i++)
3000: {
3001: rtx condition;
3002: rtx target_label, insn_at_target, fallthrough_insn;
3003: rtx delay_list = 0;
3004: int own_target;
3005: int own_fallthrough;
3006: int prediction, slots_to_fill, slots_filled;
3007:
3008: insn = unfilled_slots_base[i];
3009: if (insn == 0
3010: || INSN_DELETED_P (insn)
3011: || GET_CODE (insn) != JUMP_INSN
3012: || ! condjump_p (insn))
3013: continue;
3014:
3015: slots_to_fill = num_delay_slots (insn);
3016: if (slots_to_fill == 0)
3017: abort ();
3018:
3019: slots_filled = 0;
3020: target_label = JUMP_LABEL (insn);
3021: condition = get_branch_condition (insn, target_label);
3022:
3023: if (condition == 0)
3024: continue;
3025:
3026: /* Get the next active fallthough and target insns and see if we own
3027: them. Then see whether the branch is likely true. We don't need
3028: to do a lot of this for unconditional branches. */
3029:
3030: insn_at_target = next_active_insn (target_label);
3031: own_target = own_thread_p (target_label, target_label, 0);
3032:
3033: if (condition == const_true_rtx)
3034: {
3035: own_fallthrough = 0;
3036: fallthrough_insn = 0;
3037: prediction = 2;
3038: }
3039: else
3040: {
3041: fallthrough_insn = next_active_insn (insn);
3042: own_fallthrough = own_thread_p (NEXT_INSN (insn), 0, 1);
3043: prediction = mostly_true_jump (insn, condition);
3044: }
3045:
3046: /* If this insn is expected to branch, first try to get insns from our
3047: target, then our fallthrough insns. If it is not, expected to branch,
3048: try the other order. */
3049:
3050: if (prediction)
3051: {
3052: delay_list
3053: = fill_slots_from_thread (insn, condition, insn_at_target,
3054: fallthrough_insn, prediction == 2, 1,
3055: own_target, own_fallthrough,
3056: slots_to_fill, &slots_filled);
3057:
3058: if (delay_list == 0 && own_fallthrough)
3059: {
3060: /* Even though we didn't find anything for delay slots,
3061: we might have found a redundant insn which we deleted
3062: from the thread that was filled. So we have to recompute
3063: the next insn at the target. */
3064: target_label = JUMP_LABEL (insn);
3065: insn_at_target = next_active_insn (target_label);
3066:
3067: delay_list
3068: = fill_slots_from_thread (insn, condition, fallthrough_insn,
3069: insn_at_target, 0, 0,
3070: own_fallthrough, own_target,
3071: slots_to_fill, &slots_filled);
3072: }
3073: }
3074: else
3075: {
3076: if (own_fallthrough)
3077: delay_list
3078: = fill_slots_from_thread (insn, condition, fallthrough_insn,
3079: insn_at_target, 0, 0,
3080: own_fallthrough, own_target,
3081: slots_to_fill, &slots_filled);
3082:
3083: if (delay_list == 0)
3084: delay_list
3085: = fill_slots_from_thread (insn, condition, insn_at_target,
3086: next_active_insn (insn), 0, 1,
3087: own_target, own_fallthrough,
3088: slots_to_fill, &slots_filled);
3089: }
3090:
3091: if (delay_list)
3092: unfilled_slots_base[i]
3093: = emit_delay_sequence (insn, delay_list,
3094: slots_filled, slots_to_fill);
3095:
3096: if (slots_to_fill == slots_filled)
3097: unfilled_slots_base[i] = 0;
3098:
3099: note_delay_statistics (slots_filled, 1);
3100: }
3101: }
3102:
3103: /* Once we have tried two ways to fill a delay slot, make a pass over the
3104: code to try to improve the results and to do such things as more jump
3105: threading. */
3106:
3107: static void
3108: relax_delay_slots (first)
3109: rtx first;
3110: {
3111: register rtx insn, next, pat;
3112: register rtx trial, delay_insn, target_label;
3113:
3114: /* Look at every JUMP_INSN and see if we can improve it. */
3115: for (insn = first; insn; insn = next)
3116: {
3117: rtx other;
3118:
3119: next = next_active_insn (insn);
3120:
3121: /* If this is a jump insn, see if it now jumps to a jump, jumps to
3122: the next insn, or jumps to a label that is not the last of a
3123: group of consecutive labels. */
3124: if (GET_CODE (insn) == JUMP_INSN
3125: && (target_label = JUMP_LABEL (insn)) != 0)
3126: {
3127: target_label = follow_jumps (target_label, 1);
3128: target_label = prev_label (next_active_insn (target_label));
3129:
3130: if (next_active_insn (target_label) == next)
3131: {
3132: delete_jump (insn);
3133: continue;
3134: }
3135:
3136: if (target_label != JUMP_LABEL (insn))
3137: redirect_jump (insn,
3138: target_label ? target_label : find_end_label ());
3139:
3140: /* See if this jump branches around a unconditional jump.
3141: If so, invert this jump and point it to the target of the
3142: second jump. */
3143: if (next && GET_CODE (next) == JUMP_INSN
3144: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3145: && next_active_insn (target_label) == next_active_insn (next)
3146: && no_labels_between_p (insn, next))
3147: {
3148: rtx label = JUMP_LABEL (next);
3149:
3150: /* Be careful how we do this to avoid deleting code or
3151: labels that are momentarily dead. See similar optimization
3152: in jump.c.
3153:
3154: We also need to ensure we properly handle the case when
3155: invert_jump fails. */
3156:
3157: ++LABEL_NUSES (target_label);
3158: if (label)
3159: ++LABEL_NUSES (label);
3160:
3161: if (invert_jump (insn, label))
3162: {
3163: delete_insn (next);
3164: next = insn;
3165: }
3166:
3167: if (label)
3168: --LABEL_NUSES (label);
3169:
3170: if (--LABEL_NUSES (target_label) == 0)
3171: delete_insn (target_label);
3172:
3173: continue;
3174: }
3175: }
3176:
3177: /* If this is an unconditional jump and the previous insn is a
3178: conditional jump, try reversing the condition of the previous
3179: insn and swapping our targets. The next pass might be able to
3180: fill the slots.
3181:
3182: Don't do this if we expect the conditional branch to be true, because
3183: we would then be making the more common case longer. */
3184:
3185: if (GET_CODE (insn) == JUMP_INSN
3186: && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3187: && (other = prev_active_insn (insn)) != 0
3188: && condjump_p (other)
3189: && no_labels_between_p (other, insn)
3190: && ! mostly_true_jump (other,
3191: get_branch_condition (other,
3192: JUMP_LABEL (other))))
3193: {
3194: rtx other_target = JUMP_LABEL (other);
3195:
3196: /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3197: as we move the label. */
3198: if (other_target)
3199: ++LABEL_NUSES (other_target);
3200:
3201: if (invert_jump (other, target_label))
3202: redirect_jump (insn, other_target);
3203:
3204: if (other_target)
3205: --LABEL_NUSES (other_target);
3206: }
3207:
3208: /* Now look only at cases where we have filled a delay slot. */
3209: if (GET_CODE (insn) != INSN
3210: || GET_CODE (PATTERN (insn)) != SEQUENCE)
3211: continue;
3212:
3213: pat = PATTERN (insn);
3214: delay_insn = XVECEXP (pat, 0, 0);
3215:
3216: /* See if the first insn in the delay slot is redundant with some
3217: previous insn. Remove it from the delay slot if so; then set up
3218: to reprocess this insn. */
3219: if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0))
3220: {
3221: delete_from_delay_slot (XVECEXP (pat, 0, 1));
3222: next = prev_active_insn (next);
3223: continue;
3224: }
3225:
3226: /* Now look only at the cases where we have a filled JUMP_INSN. */
3227: if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3228: || ! condjump_p (XVECEXP (PATTERN (insn), 0, 0)))
3229: continue;
3230:
3231: target_label = JUMP_LABEL (delay_insn);
3232:
3233: if (target_label)
3234: {
3235: /* If this jump goes to another unconditional jump, thread it, but
3236: don't convert a jump into a RETURN here. */
3237: trial = follow_jumps (target_label, 1);
3238: trial = prev_label (next_active_insn (trial));
3239: if (trial == 0 && target_label != 0)
3240: trial = find_end_label ();
3241:
3242: if (trial != target_label)
3243: {
3244: redirect_jump (delay_insn, trial);
3245: target_label = trial;
3246: }
3247:
3248: /* If the first insn at TARGET_LABEL is redundant with a previous
3249: insn, redirect the jump to the following insn process again. */
3250: trial = next_active_insn (target_label);
3251: if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3252: && redundant_insn_p (trial, insn, 0))
3253: {
3254: trial = next_active_insn (trial);
3255: if (trial == 0)
3256: target_label = find_end_label ();
3257: else
3258: target_label = get_label_before (trial);
3259: redirect_jump (delay_insn, target_label);
3260: next = insn;
3261: continue;
3262: }
3263:
3264: /* Similarly, if it is an unconditional jump with one insn in its
3265: delay list and that insn is redundant, thread the jump. */
3266: if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3267: && XVECLEN (PATTERN (trial), 0) == 2
3268: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3269: && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3270: || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3271: && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3272: {
3273: target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3274: if (target_label == 0)
3275: target_label = find_end_label ();
3276: redirect_jump (delay_insn, target_label);
3277: next = insn;
3278: continue;
3279: }
3280: }
3281:
3282: if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3283: && prev_active_insn (target_label) == insn
3284: #ifdef HAVE_cc0
3285: /* If the last insn in the delay slot sets CC0 for some insn,
3286: various code assumes that it is in a delay slot. We could
3287: put it back where it belonged and delete the register notes,
3288: but it doesn't seem worhwhile in this uncommon case. */
3289: && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3290: REG_CC_USER, 0)
3291: #endif
3292: )
3293: {
3294: /* All this insn does is execute its delay list and jump to the
3295: following insn. So delete the jump and just execute the delay
3296: list insns.
3297:
3298: We do this by deleting the INSN containing the SEQUENCE, then
3299: re-emitting the insns separately, and then deleting the jump.
3300: This allows the count of the jump target to be properly
3301: decremented. */
3302:
3303: trial = PREV_INSN (insn);
3304: delete_insn (insn);
3305: emit_insn_after (pat, trial);
3306: delete_scheduled_jump (delay_insn);
3307: continue;
3308: }
3309:
3310: /* See if this jump (with its delay slots) branches around another
3311: jump (without delay slots). If so, invert this jump and point
3312: it to the target of the second jump. We cannot do this for
3313: annulled jumps, though. Again, don't convert a jump to a RETURN
3314: here. */
3315: if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3316: && next && GET_CODE (next) == JUMP_INSN
3317: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3318: && next_active_insn (target_label) == next_active_insn (next)
3319: && no_labels_between_p (insn, next))
3320: {
3321: rtx label = JUMP_LABEL (next);
3322: rtx old_label = JUMP_LABEL (delay_insn);
3323:
3324: if (label == 0)
3325: label = find_end_label ();
3326:
3327: /* Be careful how we do this to avoid deleting code or labels
3328: that are momentarily dead. See similar optimization in jump.c */
3329: if (old_label)
3330: ++LABEL_NUSES (old_label);
3331:
3332: if (invert_jump (delay_insn, label))
3333: {
3334: delete_insn (next);
3335: next = insn;
3336: }
3337:
3338: if (old_label && --LABEL_NUSES (old_label) == 0)
3339: delete_insn (old_label);
3340: continue;
3341: }
3342:
3343: /* If we own the thread opposite the way this insn branches, see if we
3344: can merge its delay slots with following insns. */
3345: if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3346: && own_thread_p (NEXT_INSN (insn), 0, 1))
3347: try_merge_delay_insns (insn, next);
3348: else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3349: && own_thread_p (target_label, target_label, 0))
3350: try_merge_delay_insns (insn, next_active_insn (target_label));
3351:
3352: /* If we get here, we haven't deleted INSN. But we may have deleted
3353: NEXT, so recompute it. */
3354: next = next_active_insn (insn);
3355: }
3356: }
3357:
3358: #ifdef HAVE_return
3359:
3360: /* Look for filled jumps to the end of function label. We can try to convert
3361: them into RETURN insns if the insns in the delay slot are valid for the
3362: RETURN as well. */
3363:
3364: static void
3365: make_return_insns (first)
3366: rtx first;
3367: {
3368: rtx insn, jump_insn, pat;
3369: rtx real_return_label = end_of_function_label;
3370: int slots, i;
3371:
3372: /* See if there is a RETURN insn in the function other than the one we
3373: made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3374: into a RETURN to jump to it. */
3375: for (insn = first; insn; insn = NEXT_INSN (insn))
3376: if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3377: {
3378: real_return_label = get_label_before (insn);
3379: break;
3380: }
3381:
3382: /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3383: was equal to END_OF_FUNCTION_LABEL. */
3384: LABEL_NUSES (real_return_label)++;
3385:
3386: /* Clear the list of insns to fill so we can use it. */
3387: obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3388:
3389: for (insn = first; insn; insn = NEXT_INSN (insn))
3390: {
3391: /* Only look at filled JUMP_INSNs that go to the end of function
3392: label. */
3393: if (GET_CODE (insn) != INSN
3394: || GET_CODE (PATTERN (insn)) != SEQUENCE
3395: || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3396: || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3397: continue;
3398:
3399: pat = PATTERN (insn);
3400: jump_insn = XVECEXP (pat, 0, 0);
3401:
3402: /* If we can't make the jump into a RETURN, redirect it to the best
3403: RETURN and go on to the next insn. */
3404: if (! redirect_jump (jump_insn, 0))
3405: {
3406: redirect_jump (jump_insn, real_return_label);
3407: continue;
3408: }
3409:
3410: /* See if this RETURN can accept the insns current in its delay slot.
3411: It can if it has more or an equal number of slots and the contents
3412: of each is valid. */
3413:
3414: slots = num_delay_slots (jump_insn);
3415: if (slots >= XVECLEN (pat, 0) - 1)
3416: {
3417: for (i = 1; i < XVECLEN (pat, 0); i++)
3418: if (! (
3419: #ifdef ANNUL_IFFALSE_SLOTS
3420: (INSN_ANNULLED_BRANCH_P (jump_insn)
3421: && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3422: ? eligible_for_annul_false (jump_insn, i - 1,
3423: XVECEXP (pat, 0, i)) :
3424: #endif
3425: #ifdef ANNUL_IFTRUE_SLOTS
3426: (INSN_ANNULLED_BRANCH_P (jump_insn)
3427: && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3428: ? eligible_for_annul_true (jump_insn, i - 1,
3429: XVECEXP (pat, 0, i)) :
3430: #endif
3431: eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
3432: break;
3433: }
3434: else
3435: i = 0;
3436:
3437: if (i == XVECLEN (pat, 0))
3438: continue;
3439:
3440: /* We have to do something with this insn. If it is an unconditional
3441: RETURN, delete the SEQUENCE and output the individual insns,
3442: followed by the RETURN. Then set things up so we try to find
3443: insns for its delay slots, if it needs some. */
3444: if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3445: {
3446: rtx prev = PREV_INSN (insn);
3447:
3448: delete_insn (insn);
3449: for (i = 1; i < XVECLEN (pat, 0); i++)
3450: prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3451:
3452: insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3453: emit_barrier_after (insn);
3454:
3455: if (slots)
3456: obstack_ptr_grow (&unfilled_slots_obstack, insn);
3457: }
3458: else
3459: /* It is probably more efficient to keep this with its current
3460: delay slot as a branch to a RETURN. */
3461: redirect_jump (jump_insn, real_return_label);
3462: }
3463:
3464: /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3465: new delay slots we have created. */
3466: if (--LABEL_NUSES (real_return_label) == 0)
3467: delete_insn (real_return_label);
3468:
3469: fill_simple_delay_slots (first, 1);
3470: fill_simple_delay_slots (first, 0);
3471: }
3472: #endif
3473:
3474: /* Try to find insns to place in delay slots. */
3475:
3476: void
3477: dbr_schedule (first, file)
3478: rtx first;
3479: FILE *file;
3480: {
3481: rtx insn, next;
3482: int i;
3483: #if 0
3484: int old_flag_no_peephole = flag_no_peephole;
3485:
3486: /* Execute `final' once in prescan mode to delete any insns that won't be
3487: used. Don't let final try to do any peephole optimization--it will
3488: ruin dataflow information for this pass. */
3489:
3490: flag_no_peephole = 1;
3491: final (first, 0, NO_DEBUG, 1, 1);
3492: flag_no_peephole = old_flag_no_peephole;
3493: #endif
3494:
3495: /* Find the highest INSN_UID and allocate and initialize our map from
3496: INSN_UID's to position in code. */
3497: for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3498: if (INSN_UID (insn) > max_uid)
3499: max_uid = INSN_UID (insn);
3500:
3501: uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
3502: for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3503: uid_to_ruid[INSN_UID (insn)] = i;
3504:
3505: /* Initialize the list of insns that need filling. */
3506: if (unfilled_firstobj == 0)
3507: {
3508: gcc_obstack_init (&unfilled_slots_obstack);
3509: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3510: }
3511:
3512: for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3513: {
3514: rtx target;
3515:
3516: INSN_ANNULLED_BRANCH_P (insn) = 0;
3517: INSN_FROM_TARGET_P (insn) = 0;
3518:
3519: /* Skip vector tables. We can't get attributes for them. */
3520: if (GET_CODE (insn) == JUMP_INSN
3521: && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3522: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3523: continue;
3524:
3525: if (num_delay_slots (insn) > 0)
3526: obstack_ptr_grow (&unfilled_slots_obstack, insn);
3527:
3528: /* Ensure all jumps go to the last of a set of consecutive labels. */
3529: if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn)
3530: && JUMP_LABEL (insn) != 0
3531: && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3532: != JUMP_LABEL (insn)))
3533: redirect_jump (insn, target);
3534: }
3535:
3536: /* Indicate what resources are required to be valid at the end of the current
3537: function. The condition code never is and memory always is. If the
3538: frame pointer is needed, it is and so is the stack pointer unless
3539: EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
3540: stack pointer is. In addition, registers used to return the function
3541: value are needed. */
3542:
3543: end_of_function_needs.cc = 0;
3544: end_of_function_needs.memory = 1;
3545: CLEAR_HARD_REG_SET (end_of_function_needs.regs);
3546:
3547: if (frame_pointer_needed)
3548: {
3549: SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
3550: #ifdef EXIT_IGNORE_STACK
3551: if (! EXIT_IGNORE_STACK)
3552: #endif
3553: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3554: }
3555: else
3556: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3557:
3558: if (current_function_return_rtx != 0
3559: && GET_CODE (current_function_return_rtx) == REG)
3560: mark_referenced_resources (current_function_return_rtx,
3561: &end_of_function_needs, 0);
3562:
3563: /* Show we haven't computed an end-of-function label yet. */
3564: end_of_function_label = 0;
3565:
3566: /* Allocate and initialize the tables used by mark_target_live_regs. */
3567: target_hash_table
3568: = (struct target_info **) alloca ((TARGET_HASH_PRIME
3569: * sizeof (struct target_info *)));
3570: bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *));
3571:
3572: bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
3573: bzero (bb_ticks, n_basic_blocks * sizeof (int));
3574:
3575: /* Initialize the statistics for this function. */
3576: bzero (num_insns_needing_delays, sizeof num_insns_needing_delays);
3577: bzero (num_filled_delays, sizeof num_filled_delays);
3578:
3579: /* Now do the delay slot filling. Try everything twice in case earlier
3580: changes make more slots fillable. */
3581:
3582: for (reorg_pass_number = 0;
3583: reorg_pass_number < MAX_REORG_PASSES;
3584: reorg_pass_number++)
3585: {
3586: fill_simple_delay_slots (first, 1);
3587: fill_simple_delay_slots (first, 0);
3588: fill_eager_delay_slots (first);
3589: relax_delay_slots (first);
3590: }
3591:
3592: /* Delete any USE insns made by update_block; subsequent passes don't need
3593: them or know how to deal with them. */
3594: for (insn = first; insn; insn = next)
3595: {
3596: next = NEXT_INSN (insn);
3597:
3598: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3599: && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
3600: || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
3601: || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
3602: next = delete_insn (insn);
3603: }
3604:
3605: /* If we made an end of function label, indicate that it is now
3606: safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3607: If it is now unused, delete it. */
3608: if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3609: delete_insn (end_of_function_label);
3610:
3611: #ifdef HAVE_return
3612: if (HAVE_return && end_of_function_label != 0)
3613: make_return_insns (first);
3614: #endif
3615:
3616: obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3617:
3618: /* It is not clear why the line below is needed, but it does seem to be. */
3619: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3620:
3621: if (file)
3622: {
3623: register int i, j, need_comma;
3624:
3625: for (reorg_pass_number = 0;
3626: reorg_pass_number < MAX_REORG_PASSES;
3627: reorg_pass_number++)
3628: {
3629: fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3630: for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3631: {
3632: need_comma = 0;
3633: fprintf (file, ";; Reorg function #%d\n", i);
3634:
3635: fprintf (file, ";; %d insns needing delay slots\n;; ",
3636: num_insns_needing_delays[i][reorg_pass_number]);
3637:
3638: for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
3639: if (num_filled_delays[i][j][reorg_pass_number])
3640: {
3641: if (need_comma)
3642: fprintf (file, ", ");
3643: need_comma = 1;
3644: fprintf (file, "%d got %d delays",
3645: num_filled_delays[i][j][reorg_pass_number], j);
3646: }
3647: fprintf (file, "\n");
3648: }
3649: }
3650: }
3651: }
3652: #endif /* DELAY_SLOTS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.