![[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
1.1.1.2 ! root 98: correspondence between the insn that sets and uses CC0. The insns are
1.1 root 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: /* Called when INSN is being moved from a location near the target of a jump.
1.1.1.2 ! root 1762: We leave a marker of the form (use (INSN)) immediately in front
1.1 root 1763: of WHERE for mark_target_live_regs. These markers will be deleted when
1.1.1.2 ! root 1764: reorg finishes.
! 1765:
! 1766: We used to try to update the live status of registers if WHERE is at
! 1767: the start of a basic block, but that can't work since we may remove a
! 1768: BARRIER in relax_delay_slots. */
1.1 root 1769:
1770: static void
1771: update_block (insn, where)
1772: rtx insn;
1773: rtx where;
1774: {
1.1.1.2 ! root 1775: int b;
! 1776:
1.1 root 1777: /* Ignore if this was in a delay slot and it came from the target of
1778: a branch. */
1779: if (INSN_FROM_TARGET_P (insn))
1780: return;
1781:
1.1.1.2 ! root 1782: emit_insn_before (gen_rtx (USE, VOIDmode, insn), where);
1.1 root 1783:
1784: /* INSN might be making a value live in a block where it didn't use to
1785: be. So recompute liveness information for this block. */
1.1.1.2 ! root 1786:
! 1787: b = find_basic_block (insn);
! 1788: if (b != -1)
! 1789: bb_ticks[b]++;
1.1 root 1790: }
1791:
1792: /* Marks registers possibly live at the current place being scanned by
1793: mark_target_live_regs. Used only by next two function. */
1794:
1795: static HARD_REG_SET current_live_regs;
1796:
1797: /* Marks registers for which we have seen a REG_DEAD note but no assignment.
1798: Also only used by the next two functions. */
1799:
1800: static HARD_REG_SET pending_dead_regs;
1801:
1802: /* Utility function called from mark_target_live_regs via note_stores.
1803: It deadens any CLOBBERed registers and livens any SET registers. */
1804:
1805: static void
1806: update_live_status (dest, x)
1807: rtx dest;
1808: rtx x;
1809: {
1810: int first_regno, last_regno;
1811: int i;
1812:
1813: if (GET_CODE (dest) != REG
1814: && (GET_CODE (dest) != SUBREG || GET_CODE (SUBREG_REG (dest)) != REG))
1815: return;
1816:
1817: if (GET_CODE (dest) == SUBREG)
1818: first_regno = REGNO (SUBREG_REG (dest)) + SUBREG_WORD (dest);
1819: else
1820: first_regno = REGNO (dest);
1821:
1822: last_regno = first_regno + HARD_REGNO_NREGS (first_regno, GET_MODE (dest));
1823:
1824: if (GET_CODE (x) == CLOBBER)
1825: for (i = first_regno; i < last_regno; i++)
1826: CLEAR_HARD_REG_BIT (current_live_regs, i);
1827: else
1828: for (i = first_regno; i < last_regno; i++)
1829: {
1830: SET_HARD_REG_BIT (current_live_regs, i);
1831: CLEAR_HARD_REG_BIT (pending_dead_regs, i);
1832: }
1833: }
1834:
1835: /* Similar to next_insn, but ignores insns in the delay slots of
1836: an annulled branch. */
1837:
1838: static rtx
1839: next_insn_no_annul (insn)
1840: rtx insn;
1841: {
1842: if (insn)
1843: {
1844: /* If INSN is an annulled branch, skip any insns from the target
1845: of the branch. */
1846: if (INSN_ANNULLED_BRANCH_P (insn)
1847: && NEXT_INSN (PREV_INSN (insn)) != insn)
1848: while (INSN_FROM_TARGET_P (NEXT_INSN (insn)))
1849: insn = NEXT_INSN (insn);
1850:
1851: insn = NEXT_INSN (insn);
1852: if (insn && GET_CODE (insn) == INSN
1853: && GET_CODE (PATTERN (insn)) == SEQUENCE)
1854: insn = XVECEXP (PATTERN (insn), 0, 0);
1855: }
1856:
1857: return insn;
1858: }
1859:
1860: /* Set the resources that are live at TARGET.
1861:
1862: If TARGET is zero, we refer to the end of the current function and can
1863: return our precomputed value.
1864:
1865: Otherwise, we try to find out what is live by consulting the basic block
1866: information. This is tricky, because we must consider the actions of
1867: reload and jump optimization, which occur after the basic block information
1868: has been computed.
1869:
1870: Accordingly, we proceed as follows::
1871:
1872: We find the previous BARRIER and look at all immediately following labels
1873: (with no intervening active insns) to see if any of them start a basic
1874: block. If we hit the start of the function first, we use block 0.
1875:
1876: Once we have found a basic block and a corresponding first insns, we can
1877: accurately compute the live status from basic_block_live_regs and
1878: reg_renumber. (By starting at a label following a BARRIER, we are immune
1879: to actions taken by reload and jump.) Then we scan all insns between
1880: that point and our target. For each CLOBBER (or for call-clobbered regs
1881: when we pass a CALL_INSN), mark the appropriate registers are dead. For
1882: a SET, mark them as live.
1883:
1884: We have to be careful when using REG_DEAD notes because they are not
1885: updated by such things as find_equiv_reg. So keep track of registers
1886: marked as dead that haven't been assigned to, and mark them dead at the
1887: next CODE_LABEL since reload and jump won't propagate values across labels.
1888:
1889: If we cannot find the start of a basic block (should be a very rare
1890: case, if it can happen at all), mark everything as potentially live.
1891:
1892: Next, scan forward from TARGET looking for things set or clobbered
1893: before they are used. These are not live.
1894:
1895: Because we can be called many times on the same target, save our results
1896: in a hash table indexed by INSN_UID. */
1897:
1898: static void
1899: mark_target_live_regs (target, res)
1900: rtx target;
1901: struct resources *res;
1902: {
1903: int b = -1;
1904: int i;
1905: struct target_info *tinfo;
1906: rtx insn, next;
1907: rtx jump_insn = 0;
1908: HARD_REG_SET scratch;
1909: struct resources set, needed;
1910: int jump_count = 0;
1911:
1912: /* Handle end of function. */
1913: if (target == 0)
1914: {
1915: *res = end_of_function_needs;
1916: return;
1917: }
1918:
1919: /* We have to assume memory is needed, but the CC isn't. */
1920: res->memory = 1;
1921: res->volatil = 0;
1922: res->cc = 0;
1923:
1924: /* See if we have computed this value already. */
1925: for (tinfo = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1926: tinfo; tinfo = tinfo->next)
1927: if (tinfo->uid == INSN_UID (target))
1928: break;
1929:
1930: /* Start by getting the basic block number. If we have saved information,
1931: we can get it from there unless the insn at the start of the basic block
1932: has been deleted. */
1933: if (tinfo && tinfo->block != -1
1934: && ! INSN_DELETED_P (basic_block_head[tinfo->block]))
1935: b = tinfo->block;
1936:
1937: if (b == -1)
1938: b = find_basic_block (target);
1939:
1940: if (tinfo)
1941: {
1942: /* If the information is up-to-date, use it. Otherwise, we will
1943: update it below. */
1944: if (b == tinfo->block && b != -1 && tinfo->bb_tick == bb_ticks[b])
1945: {
1946: COPY_HARD_REG_SET (res->regs, tinfo->live_regs);
1947: return;
1948: }
1949: }
1950: else
1951: {
1952: /* Allocate a place to put our results and chain it into the
1953: hash table. */
1954: tinfo = (struct target_info *) oballoc (sizeof (struct target_info));
1955: tinfo->uid = INSN_UID (target);
1956: tinfo->block = b;
1957: tinfo->next = target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME];
1958: target_hash_table[INSN_UID (target) % TARGET_HASH_PRIME] = tinfo;
1959: }
1960:
1961: CLEAR_HARD_REG_SET (pending_dead_regs);
1962:
1963: /* If we found a basic block, get the live registers from it and update
1964: them with anything set or killed between its start and the insn before
1965: TARGET. Otherwise, we must assume everything is live. */
1966: if (b != -1)
1967: {
1968: regset regs_live = basic_block_live_at_start[b];
1969: int offset, bit, j;
1970: int regno;
1971: rtx start_insn, stop_insn;
1972:
1973: /* Compute hard regs live at start of block -- this is the real hard regs
1974: marked live, plus live pseudo regs that have been renumbered to
1975: hard regs. */
1976:
1977: #ifdef HARD_REG_SET
1978: current_live_regs = *regs_live;
1979: #else
1980: COPY_HARD_REG_SET (current_live_regs, regs_live);
1981: #endif
1982:
1983: for (offset = 0, i = 0; offset < regset_size; offset++)
1984: {
1985: if (regs_live[offset] == 0)
1986: i += HOST_BITS_PER_INT;
1987: else
1988: for (bit = 1; bit && i < max_regno; bit <<= 1, i++)
1989: if ((regs_live[offset] & bit)
1990: && (regno = reg_renumber[i]) >= 0)
1991: for (j = regno;
1992: j < regno + HARD_REGNO_NREGS (regno,
1993: PSEUDO_REGNO_MODE (i));
1994: j++)
1995: SET_HARD_REG_BIT (current_live_regs, j);
1996: }
1997:
1998: /* Get starting and ending insn, handling the case where each might
1999: be a SEQUENCE. */
2000: start_insn = (b == 0 ? get_insns () : basic_block_head[b]);
2001: stop_insn = target;
2002:
2003: if (GET_CODE (start_insn) == INSN
2004: && GET_CODE (PATTERN (start_insn)) == SEQUENCE)
2005: start_insn = XVECEXP (PATTERN (start_insn), 0, 0);
2006:
2007: if (GET_CODE (stop_insn) == INSN
2008: && GET_CODE (PATTERN (stop_insn)) == SEQUENCE)
2009: stop_insn = next_insn (PREV_INSN (stop_insn));
2010:
2011: for (insn = start_insn; insn != stop_insn;
2012: insn = next_insn_no_annul (insn))
2013: {
2014: rtx link;
2015: rtx real_insn = insn;
2016:
2017: /* If this insn is from the target of a branch, it isn't going to
2018: be used in the sequel. If it is used in both cases, this
2019: test will not be true. */
2020: if (INSN_FROM_TARGET_P (insn))
2021: continue;
2022:
2023: /* If this insn is a USE made by update_block, we care about the
2024: underlying insn. */
2025: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
2026: && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
2027: || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN
2028: || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN))
2029: real_insn = XEXP (PATTERN (insn), 0);
2030:
2031: if (GET_CODE (real_insn) == CALL_INSN)
2032: {
2033: /* CALL clobbers all call-used regs that aren't fixed except
2034: sp, ap, and fp. Do this before setting the result of the
2035: call live. */
2036: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
2037: if (call_used_regs[i]
2038: && i != STACK_POINTER_REGNUM && i != FRAME_POINTER_REGNUM
2039: && i != ARG_POINTER_REGNUM
2040: #if ARG_POINTER_REGNUM != FRAME_POINTER_REGNUM
2041: && ! (i == ARG_POINTER_REGNUM && fixed_regs[i])
2042: #endif
2043: #ifdef PIC_OFFSET_TABLE_REGNUM
2044: && ! (i == PIC_OFFSET_TABLE_REGNUM && flag_pic)
2045: #endif
2046: )
2047: CLEAR_HARD_REG_BIT (current_live_regs, i);
1.1.1.2 ! root 2048:
! 2049: /* A CALL_INSN sets any global register live, since it may
! 2050: have been modified by the call. */
! 2051: for (i = 0; i < FIRST_PSEUDO_REGISTER; i++)
! 2052: if (global_regs[i])
! 2053: SET_HARD_REG_BIT (current_live_regs, i);
1.1 root 2054: }
2055:
2056: /* Mark anything killed in an insn to be deadened at the next
2057: label. Ignore USE insns; the only REG_DEAD notes will be for
2058: parameters. But they might be early. A CALL_INSN will usually
2059: clobber registers used for parameters. It isn't worth bothering
2060: with the unlikely case when it won't. */
2061: if ((GET_CODE (real_insn) == INSN
2062: && GET_CODE (PATTERN (real_insn)) != USE)
2063: || GET_CODE (real_insn) == JUMP_INSN
2064: || GET_CODE (real_insn) == CALL_INSN)
2065: {
2066: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2067: if (REG_NOTE_KIND (link) == REG_DEAD
2068: && GET_CODE (XEXP (link, 0)) == REG
2069: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2070: {
2071: int first_regno = REGNO (XEXP (link, 0));
2072: int last_regno
2073: = (first_regno
2074: + HARD_REGNO_NREGS (first_regno,
2075: GET_MODE (XEXP (link, 0))));
2076:
2077: for (i = first_regno; i < last_regno; i++)
2078: SET_HARD_REG_BIT (pending_dead_regs, i);
2079: }
2080:
2081: note_stores (PATTERN (real_insn), update_live_status);
2082:
2083: /* If any registers were unused after this insn, kill them.
2084: These notes will always be accurate. */
2085: for (link = REG_NOTES (real_insn); link; link = XEXP (link, 1))
2086: if (REG_NOTE_KIND (link) == REG_UNUSED
2087: && GET_CODE (XEXP (link, 0)) == REG
2088: && REGNO (XEXP (link, 0)) < FIRST_PSEUDO_REGISTER)
2089: {
2090: int first_regno = REGNO (XEXP (link, 0));
2091: int last_regno
2092: = (first_regno
2093: + HARD_REGNO_NREGS (first_regno,
2094: GET_MODE (XEXP (link, 0))));
2095:
2096: for (i = first_regno; i < last_regno; i++)
2097: CLEAR_HARD_REG_BIT (current_live_regs, i);
2098: }
2099: }
2100:
2101: if (GET_CODE (real_insn) == CODE_LABEL)
2102: {
2103: /* A label clobbers the pending dead registers since neither
2104: reload nor jump will propagate a value across a label. */
2105: AND_COMPL_HARD_REG_SET (current_live_regs, pending_dead_regs);
2106: CLEAR_HARD_REG_SET (pending_dead_regs);
2107: }
2108: }
2109:
2110: COPY_HARD_REG_SET (res->regs, current_live_regs);
2111: tinfo->block = b;
2112: tinfo->bb_tick = bb_ticks[b];
2113: }
2114: else
2115: /* We didn't find the start of a basic block. Assume everything
2116: in use. This should happen only extremely rarely. */
2117: SET_HARD_REG_SET (res->regs);
2118:
2119: /* Now step forward from TARGET looking for registers that are set before
2120: they are used. These are dead. If we pass a label, any pending dead
2121: registers that weren't yet used can be made dead. Stop when we pass a
2122: conditional JUMP_INSN; follow the first few unconditional branches. */
2123:
2124: CLEAR_RESOURCE (&set);
2125: CLEAR_RESOURCE (&needed);
2126:
2127: for (insn = target; insn; insn = next)
2128: {
2129: rtx main_insn = insn;
2130:
2131: next = NEXT_INSN (insn);
2132: switch (GET_CODE (insn))
2133: {
2134: case CODE_LABEL:
2135: AND_COMPL_HARD_REG_SET (pending_dead_regs, needed.regs);
2136: AND_COMPL_HARD_REG_SET (res->regs, pending_dead_regs);
2137: CLEAR_HARD_REG_SET (pending_dead_regs);
2138: continue;
2139:
2140: case BARRIER:
2141: case NOTE:
2142: continue;
2143:
2144: case INSN:
2145: if (GET_CODE (PATTERN (insn)) == USE
2146: || GET_CODE (PATTERN (insn)) == CLOBBER)
2147: continue;
2148: if (GET_CODE (PATTERN (insn)) == SEQUENCE)
2149: main_insn = XVECEXP (PATTERN (insn), 0, 0);
2150: }
2151:
2152: if (GET_CODE (main_insn) == JUMP_INSN)
2153: {
2154: if (jump_count++ < 10
2155: && (simplejump_p (main_insn)
2156: || GET_CODE (PATTERN (main_insn)) == RETURN))
2157: {
2158: next = next_active_insn (JUMP_LABEL (main_insn));
2159: if (jump_insn == 0)
2160: jump_insn = insn;
2161: }
2162: else
2163: break;
2164: }
2165:
2166: mark_referenced_resources (insn, &needed, 1);
2167: mark_set_resources (insn, &set, 1);
2168:
2169: COPY_HARD_REG_SET (scratch, set.regs);
2170: AND_COMPL_HARD_REG_SET (scratch, needed.regs);
2171: AND_COMPL_HARD_REG_SET (res->regs, scratch);
2172: }
2173:
2174: /* If we hit an unconditional branch, we have another way of finding out
2175: what is live: we can see what is live at the branch target and include
2176: anything used but not set before the branch. The only things that are
1.1.1.2 ! root 2177: live are those that are live using the above test and the test below.
! 2178:
! 2179: Don't try this if we expired our jump count above, since that would
! 2180: mean there may be an infinite loop in the function being compiled. */
! 2181:
! 2182: if (jump_insn && jump_count < 10)
1.1 root 2183: {
2184: rtx jump_target = (GET_CODE (jump_insn) == INSN
2185: ? JUMP_LABEL (XVECEXP (PATTERN (jump_insn), 0, 0))
2186: : JUMP_LABEL (jump_insn));
2187: struct resources new_resources;
2188: rtx stop_insn = next_active_insn (jump_insn);
2189:
2190: mark_target_live_regs (next_active_insn (jump_target), &new_resources);
2191: CLEAR_RESOURCE (&set);
2192: CLEAR_RESOURCE (&needed);
2193:
2194: /* Include JUMP_INSN in the needed registers. */
2195: for (insn = target; insn != stop_insn; insn = next_active_insn (insn))
2196: {
2197: mark_referenced_resources (insn, &needed, 1);
2198:
2199: COPY_HARD_REG_SET (scratch, needed.regs);
2200: AND_COMPL_HARD_REG_SET (scratch, set.regs);
2201: IOR_HARD_REG_SET (new_resources.regs, scratch);
2202:
2203: mark_set_resources (insn, &set, 1);
2204: }
2205:
2206: AND_HARD_REG_SET (res->regs, new_resources.regs);
2207: }
2208:
2209: COPY_HARD_REG_SET (tinfo->live_regs, res->regs);
2210: }
2211:
2212: /* Scan a function looking for insns that need a delay slot and find insns to
2213: put into the delay slot.
2214:
2215: NON_JUMPS_P is non-zero if we are to only try to fill non-jump insns (such
2216: as calls). We do these first since we don't want jump insns (that are
2217: easier to fill) to get the only insns that could be used for non-jump insns.
2218: When it is zero, only try to fill JUMP_INSNs.
2219:
2220: When slots are filled in this manner, the insns (including the
2221: delay_insn) are put together in a SEQUENCE rtx. In this fashion,
2222: it is possible to tell whether a delay slot has really been filled
2223: or not. `final' knows how to deal with this, by communicating
2224: through FINAL_SEQUENCE. */
2225:
2226: static void
2227: fill_simple_delay_slots (first, non_jumps_p)
2228: rtx first;
2229: {
2230: register rtx insn, pat, trial, next_trial;
2231: register int i;
2232: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2233: struct resources needed, set;
2234: register int slots_to_fill, slots_filled;
2235: rtx delay_list;
2236:
2237: for (i = 0; i < num_unfilled_slots; i++)
2238: {
2239: /* Get the next insn to fill. If it has already had any slots assigned,
2240: we can't do anything with it. Maybe we'll improve this later. */
2241:
2242: insn = unfilled_slots_base[i];
2243: if (insn == 0
2244: || INSN_DELETED_P (insn)
2245: || (GET_CODE (insn) == INSN
2246: && GET_CODE (PATTERN (insn)) == SEQUENCE)
2247: || (GET_CODE (insn) == JUMP_INSN && non_jumps_p)
2248: || (GET_CODE (insn) != JUMP_INSN && ! non_jumps_p))
2249: continue;
2250:
2251: slots_to_fill = num_delay_slots (insn);
2252: if (slots_to_fill == 0)
2253: abort ();
2254:
2255: /* This insn needs, or can use, some delay slots. SLOTS_TO_FILL
2256: says how many. After initialization, scan backwards from the
2257: insn to search for a potential delay-slot candidate. Stop
2258: searching when a label or jump is hit.
2259:
2260: For each candidate, if it is to go into the delay slot (moved
2261: forward in execution sequence), it must not need or set any resources
2262: that were set by later insns and must not set any resources that
2263: are needed for those insns.
2264:
2265: The delay slot insn itself sets resources unless it is a call
2266: (in which case the called routine, not the insn itself, is doing
2267: the setting). */
2268:
2269: slots_filled = 0;
2270: delay_list = 0;
2271: CLEAR_RESOURCE (&needed);
2272: CLEAR_RESOURCE (&set);
2273: mark_set_resources (insn, &set, 0);
2274: mark_referenced_resources (insn, &needed, 0);
2275:
2276: for (trial = prev_nonnote_insn (insn); ! stop_search_p (trial, 1);
2277: trial = next_trial)
2278: {
2279: next_trial = prev_nonnote_insn (trial);
2280:
2281: /* This must be an INSN or CALL_INSN. */
2282: pat = PATTERN (trial);
2283:
2284: /* USE and CLOBBER at this level was just for flow; ignore it. */
2285: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2286: continue;
2287:
2288: /* Check for resource conflict first, to avoid unnecessary
2289: splitting. */
2290: if (! insn_references_resource_p (trial, &set, 1)
2291: && ! insn_sets_resource_p (trial, &set, 1)
2292: && ! insn_sets_resource_p (trial, &needed, 1)
2293: #ifdef HAVE_cc0
2294: /* Can't separate set of cc0 from its use. */
2295: && ! (reg_mentioned_p (cc0_rtx, pat)
2296: && ! sets_cc0_p (cc0_rtx, pat))
2297: #endif
2298: )
2299: {
2300: trial = try_split (pat, trial, 1);
2301: next_trial = prev_nonnote_insn (trial);
2302: if (eligible_for_delay (insn, slots_filled, trial))
2303: {
2304: /* In this case, we are searching backward, so if we
2305: find insns to put on the delay list, we want
2306: to put them at the head, rather than the
2307: tail, of the list. */
2308:
2309: delay_list = gen_rtx (INSN_LIST, VOIDmode,
2310: trial, delay_list);
2311: update_block (trial, trial);
2312: delete_insn (trial);
2313: if (slots_to_fill == ++slots_filled)
2314: break;
2315: continue;
2316: }
2317: }
2318:
2319: mark_set_resources (trial, &set, 1);
2320: mark_referenced_resources (trial, &needed, 1);
2321: }
2322:
2323: if (slots_filled == slots_to_fill)
2324: /* happy. */ ;
2325:
2326: /* If all needed slots haven't been filled, we come here. */
2327:
2328: /* Try to optimize case of jumping around a single insn. */
2329: #if defined(ANNUL_IFFALSE_SLOTS) || defined(ANNUL_IFTRUE_SLOTS)
2330: else if (delay_list == 0
2331: && GET_CODE (insn) == JUMP_INSN && condjump_p (insn))
2332: {
2333: delay_list = optimize_skip (insn);
2334: if (delay_list)
2335: slots_filled += 1;
2336: }
2337: #endif
2338:
2339: /* @@ This would be a good place to optimize:
2340:
2341: call _foo call _foo
2342: nop add %o7,.-L1,%o7
2343: b,a L1
2344: nop
2345:
2346: Someday... */
2347:
2348: /* Try to get insns from beyond the insn needing the delay slot.
2349: These insns can neither set or reference resources set in insns being
2350: skipped, cannot set resources in the insn being skipped, and, if this
2351: is a CALL_INSN (or a CALL_INSN is passed), cannot trap (because the
2352: call might not return).
2353:
2354: If this is a conditional jump, see if it merges back to us early
2355: enough for us to pick up insns from the merge point. Don't do
2356: this if there is another branch to our label unless we pass all of
2357: them.
2358:
2359: Another similar merge is if we jump to the same place that a
2360: later unconditional jump branches to. In that case, we don't
2361: care about the number of uses of our label. */
2362:
2363: else if (GET_CODE (insn) != JUMP_INSN
2364: || (condjump_p (insn) && ! simplejump_p (insn)
2365: && JUMP_LABEL (insn) != 0))
2366: {
2367: rtx target = 0;
2368: int maybe_never = 0;
2369: int passed_label = 0;
2370: int target_uses;
2371: struct resources needed_at_jump;
2372:
2373: CLEAR_RESOURCE (&needed);
2374: CLEAR_RESOURCE (&set);
2375:
2376: if (GET_CODE (insn) == CALL_INSN)
2377: {
2378: mark_set_resources (insn, &set, 1);
2379: mark_referenced_resources (insn, &needed, 1);
2380: maybe_never = 1;
2381: }
2382: else if (GET_CODE (insn) == JUMP_INSN)
2383: {
2384: /* Get our target and show how many more uses we want to
2385: see before we hit the label. */
2386: target = JUMP_LABEL (insn);
2387: target_uses = LABEL_NUSES (target) - 1;
2388: }
2389:
2390: for (trial = next_nonnote_insn (insn); trial; trial = next_trial)
2391: {
2392: rtx pat, trial_delay;
2393:
2394: next_trial = next_nonnote_insn (trial);
2395:
2396: if (GET_CODE (trial) == CODE_LABEL)
2397: {
2398: passed_label = 1;
2399:
2400: /* If this is our target, see if we have seen all its uses.
2401: If so, indicate we have passed our target and ignore it.
2402: All other labels cause us to stop our search. */
2403: if (trial == target && target_uses == 0)
2404: {
2405: target = 0;
2406: continue;
2407: }
2408: else
2409: break;
2410: }
2411: else if (GET_CODE (trial) == BARRIER)
2412: break;
2413:
2414: /* We must have an INSN, JUMP_INSN, or CALL_INSN. */
2415: pat = PATTERN (trial);
2416:
2417: /* Stand-alone USE and CLOBBER are just for flow. */
2418: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2419: continue;
2420:
2421: /* If this already has filled delay slots, get the insn needing
2422: the delay slots. */
2423: if (GET_CODE (pat) == SEQUENCE)
2424: trial_delay = XVECEXP (pat, 0, 0);
2425: else
2426: trial_delay = trial;
2427:
2428: /* If this is a jump insn to our target, indicate that we have
2429: seen another jump to it. If we aren't handling a conditional
2430: jump, stop our search. Otherwise, compute the needs at its
2431: target and add them to NEEDED. */
2432: if (GET_CODE (trial_delay) == JUMP_INSN)
2433: {
2434: if (target == 0)
2435: break;
2436: else if (JUMP_LABEL (trial_delay) == target)
2437: target_uses--;
2438: else
2439: {
2440: mark_target_live_regs
2441: (next_active_insn (JUMP_LABEL (trial_delay)),
2442: &needed_at_jump);
2443: needed.memory |= needed_at_jump.memory;
2444: IOR_HARD_REG_SET (needed.regs, needed_at_jump.regs);
2445: }
2446: }
2447:
2448: /* See if we have a resource problem before we try to
2449: split. */
2450: if (target == 0
2451: && GET_CODE (pat) != SEQUENCE
2452: && ! insn_references_resource_p (trial, &set, 1)
2453: && ! insn_sets_resource_p (trial, &set, 1)
2454: && ! insn_sets_resource_p (trial, &needed, 1)
2455: #ifdef HAVE_cc0
2456: && ! (reg_mentioned_p (cc0_rtx, pat) && ! sets_cc0_p (pat))
2457: #endif
2458: && ! (maybe_never && may_trap_p (pat))
2459: && (trial = try_split (pat, trial, 0))
2460: && eligible_for_delay (insn, slots_filled, trial))
2461: {
2462: next_trial = next_nonnote_insn (trial);
2463: delay_list = add_to_delay_list (trial, delay_list);
2464:
2465: #ifdef HAVE_cc0
2466: if (reg_mentioned_p (cc0_rtx, pat))
2467: link_cc0_insns (trial);
2468: #endif
2469:
2470: if (passed_label)
2471: update_block (trial, trial);
2472: delete_insn (trial);
2473: if (slots_to_fill == ++slots_filled)
2474: break;
2475: continue;
2476: }
2477:
2478: mark_set_resources (trial, &set, 1);
2479: mark_referenced_resources (trial, &needed, 1);
2480:
2481: /* Ensure we don't put insns between the setting of cc and the
2482: comparison by moving a setting of cc into an earlier delay
2483: slot since these insns could clobber the condition code. */
2484: set.cc = 1;
2485:
2486: /* If this is a call or jump, we might not get here. */
2487: if (GET_CODE (trial) == CALL_INSN
2488: || GET_CODE (trial) == JUMP_INSN)
2489: maybe_never = 1;
2490: }
2491:
2492: /* If there are slots left to fill and our search was stopped by an
2493: unconditional branch, try the insn at the branch target. We can
2494: redirect the branch if it works. */
2495: if (slots_to_fill != slots_filled
2496: && trial
2497: && GET_CODE (trial) == JUMP_INSN
2498: && simplejump_p (trial)
2499: && (target == 0 || JUMP_LABEL (trial) == target)
2500: && (next_trial = next_active_insn (JUMP_LABEL (trial))) != 0
2501: && ! (GET_CODE (next_trial) == INSN
2502: && GET_CODE (PATTERN (next_trial)) == SEQUENCE)
2503: && ! insn_references_resource_p (next_trial, &set, 1)
2504: && ! insn_sets_resource_p (next_trial, &set, 1)
2505: && ! insn_sets_resource_p (next_trial, &needed, 1)
2506: #ifdef HAVE_cc0
2507: && ! (reg_mentioned_p (cc0_rtx, PATTERN (next_trial))
2508: && ! sets_cc0_p (PATTERN (next_trial)))
2509: #endif
2510: && ! (maybe_never && may_trap_p (PATTERN (next_trial)))
2511: && (next_trial = try_split (PATTERN (next_trial), next_trial, 0))
2512: && eligible_for_delay (insn, slots_filled, next_trial))
2513: {
2514: rtx new_label = next_active_insn (next_trial);
2515:
2516: if (new_label != 0)
2517: new_label = get_label_before (new_label);
2518:
2519: delay_list
2520: = add_to_delay_list (copy_rtx (next_trial), delay_list);
2521: slots_filled++;
2522: redirect_jump (trial, new_label);
2523:
2524: /* If we merged because we both jumped to the same place,
2525: redirect the original insn also. */
2526: if (target)
2527: redirect_jump (insn, new_label);
2528: }
2529: }
2530:
2531: if (delay_list)
2532: unfilled_slots_base[i]
2533: = emit_delay_sequence (insn, delay_list,
2534: slots_filled, slots_to_fill);
2535:
2536: if (slots_to_fill == slots_filled)
2537: unfilled_slots_base[i] = 0;
2538:
2539: note_delay_statistics (slots_filled, 0);
2540: }
2541:
2542: #ifdef DELAY_SLOTS_FOR_EPILOGUE
2543: /* See if the epilogue needs any delay slots. Try to fill them if so.
2544: The only thing we can do is scan backwards from the end of the
2545: function. If we did this in a previous pass, it is incorrect to do it
2546: again. */
2547: if (current_function_epilogue_delay_list)
2548: return;
2549:
2550: slots_to_fill = DELAY_SLOTS_FOR_EPILOGUE;
2551: if (slots_to_fill == 0)
2552: return;
2553:
2554: slots_filled = 0;
2555: CLEAR_RESOURCE (&needed);
2556: CLEAR_RESOURCE (&set);
2557:
2558: for (trial = get_last_insn (); ! stop_search_p (trial, 1);
2559: trial = PREV_INSN (trial))
2560: {
2561: if (GET_CODE (trial) == NOTE)
2562: continue;
2563: pat = PATTERN (trial);
2564: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2565: continue;
2566:
2567: if (! insn_references_resource_p (trial, &set, 1)
2568: && ! insn_sets_resource_p (trial, &needed, 1)
2569: #ifdef HAVE_cc0
2570: /* Don't want to mess with cc0 here. */
2571: && ! reg_mentioned_p (cc0_rtx, pat)
2572: #endif
2573: )
2574: {
2575: trial = try_split (pat, trial, 1);
2576: if (ELIGIBLE_FOR_EPILOGUE_DELAY (trial, slots_filled))
2577: {
2578: /* Here as well we are searching backward, so put the
2579: insns we find on the head of the list. */
2580:
2581: current_function_epilogue_delay_list
2582: = gen_rtx (INSN_LIST, VOIDmode, trial,
2583: current_function_epilogue_delay_list);
2584: mark_referenced_resources (trial, &end_of_function_needs, 1);
2585: update_block (trial, trial);
2586: delete_insn (trial);
2587:
2588: /* Clear deleted bit so final.c will output the insn. */
2589: INSN_DELETED_P (trial) = 0;
2590:
2591: if (slots_to_fill == ++slots_filled)
2592: break;
2593: continue;
2594: }
2595: }
2596:
2597: mark_set_resources (trial, &set, 1);
2598: mark_referenced_resources (trial, &needed, 1);
2599: }
2600:
2601: note_delay_statistics (slots_filled, 0);
2602: #endif
2603: }
2604:
2605: /* Try to find insns to place in delay slots.
2606:
2607: INSN is the jump needing SLOTS_TO_FILL delay slots. It tests CONDITION
2608: or is an unconditional branch if CONDITION is const_true_rtx.
2609: *PSLOTS_FILLED is updated with the number of slots that we have filled.
2610:
2611: THREAD is a flow-of-control, either the insns to be executed if the
2612: branch is true or if the branch is false, THREAD_IF_TRUE says which.
2613:
2614: OPPOSITE_THREAD is the thread in the opposite direction. It is used
2615: to see if any potential delay slot insns set things needed there.
2616:
2617: LIKELY is non-zero if it is extremely likely that the branch will be
2618: taken and THREAD_IF_TRUE is set. This is used for the branch at the
2619: end of a loop back up to the top.
2620:
2621: OWN_THREAD and OWN_OPPOSITE_THREAD are true if we are the only user of the
2622: thread. I.e., it is the fallthrough code of our jump or the target of the
2623: jump when we are the only jump going there.
2624:
2625: If OWN_THREAD is false, it must be the "true" thread of a jump. In that
2626: case, we can only take insns from the head of the thread for our delay
2627: slot. We then adjust the jump to point after the insns we have taken. */
2628:
2629: static rtx
2630: fill_slots_from_thread (insn, condition, thread, opposite_thread, likely,
2631: thread_if_true, own_thread, own_opposite_thread,
2632: slots_to_fill, pslots_filled)
2633: rtx insn;
2634: rtx condition;
2635: rtx thread, opposite_thread;
2636: int likely;
2637: int thread_if_true;
2638: int own_thread, own_opposite_thread;
2639: int slots_to_fill, *pslots_filled;
2640: {
1.1.1.2 ! root 2641: rtx new_thread;
1.1 root 2642: rtx delay_list = 0;
2643: struct resources opposite_needed, set, needed;
2644: rtx trial;
2645: int lose = 0;
2646: int must_annul = 0;
2647:
2648: /* Validate our arguments. */
2649: if ((condition == const_true_rtx && ! thread_if_true)
2650: || (! own_thread && ! thread_if_true))
2651: abort ();
2652:
2653: /* If our thread is the end of subroutine, we can't get any delay
2654: insns from that. */
2655: if (thread == 0)
2656: return 0;
2657:
2658: /* If this is an unconditional branch, nothing is needed at the
2659: opposite thread. Otherwise, compute what is needed there. */
2660: if (condition == const_true_rtx)
2661: CLEAR_RESOURCE (&opposite_needed);
2662: else
2663: mark_target_live_regs (opposite_thread, &opposite_needed);
2664:
1.1.1.2 ! root 2665: /* If the insn at THREAD can be split, do it here to avoid having to
! 2666: update THREAD and NEW_THREAD if it is done in the loop below. Also
! 2667: initialize NEW_THREAD. */
! 2668:
! 2669: new_thread = thread = try_split (PATTERN (thread), thread, 0);
! 2670:
1.1 root 2671: /* Scan insns at THREAD. We are looking for an insn that can be removed
2672: from THREAD (it neither sets nor references resources that were set
2673: ahead of it and it doesn't set anything needs by the insns ahead of
2674: it) and that either can be placed in an annulling insn or aren't
2675: needed at OPPOSITE_THREAD. */
2676:
2677: CLEAR_RESOURCE (&needed);
2678: CLEAR_RESOURCE (&set);
2679:
2680: /* If we do not own this thread, we must stop as soon as we find
2681: something that we can't put in a delay slot, since all we can do
2682: is branch into THREAD at a later point. Therefore, labels stop
2683: the search if this is not the `true' thread. */
2684:
2685: for (trial = thread;
2686: ! stop_search_p (trial, ! thread_if_true) && (! lose || own_thread);
2687: trial = next_nonnote_insn (trial))
2688: {
2689: rtx pat;
2690:
2691: /* If we have passed a label, we no longer own this thread. */
2692: if (GET_CODE (trial) == CODE_LABEL)
2693: {
2694: own_thread = 0;
2695: continue;
2696: }
2697:
2698: pat = PATTERN (trial);
2699: if (GET_CODE (pat) == USE || GET_CODE (pat) == CLOBBER)
2700: continue;
2701:
2702: /* If TRIAL conflicts with the insns ahead of it, we lose. Also,
2703: don't separate or copy insns that set and use CC0. */
2704: if (! insn_references_resource_p (trial, &set, 1)
2705: && ! insn_sets_resource_p (trial, &set, 1)
2706: && ! insn_sets_resource_p (trial, &needed, 1)
2707: #ifdef HAVE_cc0
2708: && ! (reg_mentioned_p (cc0_rtx, pat)
2709: && (! own_thread || ! sets_cc0_p (pat)))
2710: #endif
2711: )
2712: {
2713: /* If TRIAL is redundant with some insn before INSN, we don't
2714: actually need to add it to the delay list; we can merely pretend
2715: we did. */
2716: if (redundant_insn_p (trial, insn, delay_list))
2717: {
2718: if (own_thread)
2719: {
2720: update_block (trial, thread);
2721: delete_insn (trial);
2722: }
2723: else
2724: new_thread = next_active_insn (trial);
2725:
2726: continue;
2727: }
2728:
2729: /* There are two ways we can win: If TRIAL doesn't set anything
2730: needed at the opposite thread and can't trap, or if it can
2731: go into an annulled delay slot. */
2732: if (condition == const_true_rtx
2733: || (! insn_sets_resource_p (trial, &opposite_needed, 1)
2734: && ! may_trap_p (pat)))
2735: {
2736: trial = try_split (pat, trial, 0);
2737: pat = PATTERN (trial);
2738: if (eligible_for_delay (insn, *pslots_filled, trial))
2739: goto winner;
2740: }
2741: else if (0
2742: #ifdef ANNUL_IFTRUE_SLOTS
2743: || ! thread_if_true
2744: #endif
2745: #ifdef ANNUL_IFFALSE_SLOTS
2746: || thread_if_true
2747: #endif
2748: )
2749: {
2750: trial = try_split (pat, trial, 0);
2751: pat = PATTERN (trial);
2752: if ((thread_if_true
2753: ? eligible_for_annul_false (insn, *pslots_filled, trial)
2754: : eligible_for_annul_true (insn, *pslots_filled, trial)))
2755: {
2756: rtx temp;
2757:
2758: must_annul = 1;
2759: winner:
2760:
2761: #ifdef HAVE_cc0
2762: if (reg_mentioned_p (cc0_rtx, pat))
2763: link_cc0_insns (trial);
2764: #endif
2765:
2766: /* If we own this thread, delete the insn. If this is the
2767: destination of a branch, show that a basic block status
2768: may have been updated. In any case, mark the new
2769: starting point of this thread. */
2770: if (own_thread)
2771: {
2772: update_block (trial, thread);
2773: delete_insn (trial);
2774: }
2775: else
2776: new_thread = next_active_insn (trial);
2777:
2778: temp = own_thread ? trial : copy_rtx (trial);
2779: if (thread_if_true)
2780: INSN_FROM_TARGET_P (temp) = 1;
2781:
2782: delay_list = add_to_delay_list (temp, delay_list);
2783:
2784: if (slots_to_fill == ++(*pslots_filled))
2785: {
2786: /* Even though we have filled all the slots, we
2787: may be branching to a location that has a
2788: redundant insn. Skip any if so. */
2789: while (new_thread && ! own_thread
2790: && ! insn_sets_resource_p (new_thread, &set, 1)
2791: && ! insn_sets_resource_p (new_thread, &needed, 1)
2792: && ! insn_references_resource_p (new_thread,
2793: &set, 1)
2794: && redundant_insn_p (new_thread, insn,
2795: delay_list))
2796: new_thread = next_active_insn (new_thread);
2797: break;
2798: }
2799:
2800: continue;
2801: }
2802: }
2803: }
2804:
2805: /* This insn can't go into a delay slot. */
2806: lose = 1;
2807: mark_set_resources (trial, &set, 1);
2808: mark_referenced_resources (trial, &needed, 1);
2809:
2810: /* Ensure we don't put insns between the setting of cc and the comparison
2811: by moving a setting of cc into an earlier delay slot since these insns
2812: could clobber the condition code. */
2813: set.cc = 1;
2814:
2815: /* If this insn is a register-register copy and the next insn has
2816: a use of our destination, change it to use our source. That way,
2817: it will become a candidate for our delay slot the next time
2818: through this loop. This case occurs commonly in loops that
2819: scan a list.
2820:
2821: We could check for more complex cases than those tested below,
2822: but it doesn't seem worth it. It might also be a good idea to try
1.1.1.2 ! root 2823: to swap the two insns. That might do better.
! 2824:
! 2825: We can't do this if the next insn modifies our source, because that
! 2826: would make the replacement into the insn invalid. This also
! 2827: prevents updating the contents of a PRE_INC. */
1.1 root 2828:
2829: if (GET_CODE (trial) == INSN && GET_CODE (pat) == SET
2830: && GET_CODE (SET_SRC (pat)) == REG
2831: && GET_CODE (SET_DEST (pat)) == REG)
2832: {
2833: rtx next = next_nonnote_insn (trial);
2834:
2835: if (next && GET_CODE (next) == INSN
1.1.1.2 ! root 2836: && GET_CODE (PATTERN (next)) != USE
! 2837: && ! reg_set_p (SET_DEST (pat), next)
! 2838: && reg_referenced_p (SET_DEST (pat), PATTERN (next)))
1.1 root 2839: validate_replace_rtx (SET_DEST (pat), SET_SRC (pat), next);
2840: }
2841: }
2842:
2843: /* If we stopped on a branch insn that has delay slots, see if we can
2844: steal some of the insns in those slots. */
2845: if (trial && GET_CODE (trial) == INSN
2846: && GET_CODE (PATTERN (trial)) == SEQUENCE
2847: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN)
2848: {
2849: /* If this is the `true' thread, we will want to follow the jump,
2850: so we can only do this if we have taken everything up to here. */
2851: if (thread_if_true && trial == new_thread)
2852: delay_list
2853: = steal_delay_list_from_target (insn, condition, PATTERN (trial),
2854: delay_list, &set, &needed,
2855: &opposite_needed, slots_to_fill,
2856: pslots_filled, &must_annul,
2857: &new_thread);
2858: else if (! thread_if_true)
2859: delay_list
2860: = steal_delay_list_from_fallthrough (insn, condition,
2861: PATTERN (trial),
2862: delay_list, &set, &needed,
2863: &opposite_needed, slots_to_fill,
2864: pslots_filled, &must_annul);
2865: }
2866:
2867: /* If we haven't found anything for this delay slot and it is very
2868: likely that the branch will be taken, see if the insn at our target
1.1.1.2 ! root 2869: increments or decrements a register with an increment that does not
! 2870: depend on the destination register. If so, try to place the opposite
1.1 root 2871: arithmetic insn after the jump insn and put the arithmetic insn in the
2872: delay slot. If we can't do this, return. */
2873: if (delay_list == 0 && likely && new_thread && GET_CODE (new_thread) == INSN)
2874: {
2875: rtx pat = PATTERN (new_thread);
2876: rtx dest;
2877: rtx src;
2878:
1.1.1.2 ! root 2879: trial = new_thread;
1.1 root 2880: pat = PATTERN (trial);
2881:
2882: if (GET_CODE (trial) != INSN || GET_CODE (pat) != SET
2883: || ! eligible_for_delay (insn, 0, trial))
2884: return 0;
2885:
2886: dest = SET_DEST (pat), src = SET_SRC (pat);
2887: if ((GET_CODE (src) == PLUS || GET_CODE (src) == MINUS)
1.1.1.2 ! root 2888: && rtx_equal_p (XEXP (src, 0), dest)
! 2889: && ! reg_overlap_mentioned_p (dest, XEXP (src, 1)))
1.1 root 2890: {
2891: rtx other = XEXP (src, 1);
2892: rtx new_arith;
2893: rtx ninsn;
2894:
2895: /* If this is a constant adjustment, use the same code with
2896: the negated constant. Otherwise, reverse the sense of the
2897: arithmetic. */
2898: if (GET_CODE (other) == CONST_INT)
2899: new_arith = gen_rtx (GET_CODE (src), GET_MODE (src), dest,
2900: negate_rtx (GET_MODE (src), other));
2901: else
2902: new_arith = gen_rtx (GET_CODE (src) == PLUS ? MINUS : PLUS,
2903: GET_MODE (src), dest, other);
2904:
2905: ninsn = emit_insn_after (gen_rtx (SET, VOIDmode, dest, new_arith),
2906: insn);
2907:
2908: if (recog_memoized (ninsn) < 0
2909: || (insn_extract (ninsn),
2910: ! constrain_operands (INSN_CODE (ninsn), 1)))
2911: {
2912: delete_insn (ninsn);
2913: return 0;
2914: }
2915:
2916: if (own_thread)
2917: {
2918: update_block (trial, thread);
2919: delete_insn (trial);
2920: }
2921: else
2922: new_thread = next_active_insn (trial);
2923:
2924: ninsn = own_thread ? trial : copy_rtx (trial);
2925: if (thread_if_true)
2926: INSN_FROM_TARGET_P (ninsn) = 1;
2927:
2928: delay_list = add_to_delay_list (ninsn, 0);
2929: (*pslots_filled)++;
2930: }
2931: }
2932:
2933: if (delay_list && must_annul)
2934: INSN_ANNULLED_BRANCH_P (insn) = 1;
2935:
2936: /* If we are to branch into the middle of this thread, find an appropriate
2937: label or make a new one if none, and redirect INSN to it. If we hit the
2938: end of the function, use the end-of-function label. */
2939: if (new_thread != thread)
2940: {
2941: rtx label;
2942:
2943: if (! thread_if_true)
2944: abort ();
2945:
2946: if (new_thread && GET_CODE (new_thread) == JUMP_INSN
2947: && (simplejump_p (new_thread)
2948: || GET_CODE (PATTERN (new_thread)) == RETURN))
2949: new_thread = follow_jumps (JUMP_LABEL (new_thread), 1);
2950:
2951: if (new_thread == 0)
2952: label = find_end_label ();
2953: else if (GET_CODE (new_thread) == CODE_LABEL)
2954: label = new_thread;
2955: else
2956: label = get_label_before (new_thread);
2957:
2958: redirect_jump (insn, label);
2959: }
2960:
2961: return delay_list;
2962: }
2963:
2964: /* Make another attempt to find insns to place in delay slots.
2965:
2966: We previously looked for insns located in front of the delay insn
2967: and, for non-jump delay insns, located behind the delay insn.
2968:
2969: Here only try to schedule jump insns and try to move insns from either
2970: the target or the following insns into the delay slot. If annulling is
2971: supported, we will be likely to do this. Otherwise, we can do this only
2972: if safe. */
2973:
2974: static void
2975: fill_eager_delay_slots (first)
2976: rtx first;
2977: {
2978: register rtx insn;
2979: register int i;
2980: int num_unfilled_slots = unfilled_slots_next - unfilled_slots_base;
2981:
2982: for (i = 0; i < num_unfilled_slots; i++)
2983: {
2984: rtx condition;
2985: rtx target_label, insn_at_target, fallthrough_insn;
2986: rtx delay_list = 0;
2987: int own_target;
2988: int own_fallthrough;
2989: int prediction, slots_to_fill, slots_filled;
2990:
2991: insn = unfilled_slots_base[i];
2992: if (insn == 0
2993: || INSN_DELETED_P (insn)
2994: || GET_CODE (insn) != JUMP_INSN
2995: || ! condjump_p (insn))
2996: continue;
2997:
2998: slots_to_fill = num_delay_slots (insn);
2999: if (slots_to_fill == 0)
3000: abort ();
3001:
3002: slots_filled = 0;
3003: target_label = JUMP_LABEL (insn);
3004: condition = get_branch_condition (insn, target_label);
3005:
3006: if (condition == 0)
3007: continue;
3008:
3009: /* Get the next active fallthough and target insns and see if we own
3010: them. Then see whether the branch is likely true. We don't need
3011: to do a lot of this for unconditional branches. */
3012:
3013: insn_at_target = next_active_insn (target_label);
3014: own_target = own_thread_p (target_label, target_label, 0);
3015:
3016: if (condition == const_true_rtx)
3017: {
3018: own_fallthrough = 0;
3019: fallthrough_insn = 0;
3020: prediction = 2;
3021: }
3022: else
3023: {
3024: fallthrough_insn = next_active_insn (insn);
3025: own_fallthrough = own_thread_p (NEXT_INSN (insn), 0, 1);
3026: prediction = mostly_true_jump (insn, condition);
3027: }
3028:
3029: /* If this insn is expected to branch, first try to get insns from our
3030: target, then our fallthrough insns. If it is not, expected to branch,
3031: try the other order. */
3032:
3033: if (prediction)
3034: {
3035: delay_list
3036: = fill_slots_from_thread (insn, condition, insn_at_target,
3037: fallthrough_insn, prediction == 2, 1,
3038: own_target, own_fallthrough,
3039: slots_to_fill, &slots_filled);
3040:
3041: if (delay_list == 0 && own_fallthrough)
3042: {
3043: /* Even though we didn't find anything for delay slots,
3044: we might have found a redundant insn which we deleted
3045: from the thread that was filled. So we have to recompute
3046: the next insn at the target. */
3047: target_label = JUMP_LABEL (insn);
3048: insn_at_target = next_active_insn (target_label);
3049:
3050: delay_list
3051: = fill_slots_from_thread (insn, condition, fallthrough_insn,
3052: insn_at_target, 0, 0,
3053: own_fallthrough, own_target,
3054: slots_to_fill, &slots_filled);
3055: }
3056: }
3057: else
3058: {
3059: if (own_fallthrough)
3060: delay_list
3061: = fill_slots_from_thread (insn, condition, fallthrough_insn,
3062: insn_at_target, 0, 0,
3063: own_fallthrough, own_target,
3064: slots_to_fill, &slots_filled);
3065:
3066: if (delay_list == 0)
3067: delay_list
3068: = fill_slots_from_thread (insn, condition, insn_at_target,
3069: next_active_insn (insn), 0, 1,
3070: own_target, own_fallthrough,
3071: slots_to_fill, &slots_filled);
3072: }
3073:
3074: if (delay_list)
3075: unfilled_slots_base[i]
3076: = emit_delay_sequence (insn, delay_list,
3077: slots_filled, slots_to_fill);
3078:
3079: if (slots_to_fill == slots_filled)
3080: unfilled_slots_base[i] = 0;
3081:
3082: note_delay_statistics (slots_filled, 1);
3083: }
3084: }
3085:
3086: /* Once we have tried two ways to fill a delay slot, make a pass over the
3087: code to try to improve the results and to do such things as more jump
3088: threading. */
3089:
3090: static void
3091: relax_delay_slots (first)
3092: rtx first;
3093: {
3094: register rtx insn, next, pat;
3095: register rtx trial, delay_insn, target_label;
3096:
3097: /* Look at every JUMP_INSN and see if we can improve it. */
3098: for (insn = first; insn; insn = next)
3099: {
3100: rtx other;
3101:
3102: next = next_active_insn (insn);
3103:
3104: /* If this is a jump insn, see if it now jumps to a jump, jumps to
3105: the next insn, or jumps to a label that is not the last of a
3106: group of consecutive labels. */
3107: if (GET_CODE (insn) == JUMP_INSN
3108: && (target_label = JUMP_LABEL (insn)) != 0)
3109: {
3110: target_label = follow_jumps (target_label, 1);
3111: target_label = prev_label (next_active_insn (target_label));
3112:
3113: if (next_active_insn (target_label) == next)
3114: {
3115: delete_jump (insn);
3116: continue;
3117: }
3118:
3119: if (target_label != JUMP_LABEL (insn))
3120: redirect_jump (insn,
3121: target_label ? target_label : find_end_label ());
3122:
3123: /* See if this jump branches around a unconditional jump.
3124: If so, invert this jump and point it to the target of the
3125: second jump. */
3126: if (next && GET_CODE (next) == JUMP_INSN
3127: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3128: && next_active_insn (target_label) == next_active_insn (next)
3129: && no_labels_between_p (insn, next))
3130: {
3131: rtx label = JUMP_LABEL (next);
3132:
3133: /* Be careful how we do this to avoid deleting code or
3134: labels that are momentarily dead. See similar optimization
3135: in jump.c.
3136:
3137: We also need to ensure we properly handle the case when
3138: invert_jump fails. */
3139:
3140: ++LABEL_NUSES (target_label);
3141: if (label)
3142: ++LABEL_NUSES (label);
3143:
3144: if (invert_jump (insn, label))
3145: {
3146: delete_insn (next);
3147: next = insn;
3148: }
3149:
3150: if (label)
3151: --LABEL_NUSES (label);
3152:
3153: if (--LABEL_NUSES (target_label) == 0)
3154: delete_insn (target_label);
3155:
3156: continue;
3157: }
3158: }
3159:
3160: /* If this is an unconditional jump and the previous insn is a
3161: conditional jump, try reversing the condition of the previous
3162: insn and swapping our targets. The next pass might be able to
3163: fill the slots.
3164:
3165: Don't do this if we expect the conditional branch to be true, because
3166: we would then be making the more common case longer. */
3167:
3168: if (GET_CODE (insn) == JUMP_INSN
3169: && (simplejump_p (insn) || GET_CODE (PATTERN (insn)) == RETURN)
3170: && (other = prev_active_insn (insn)) != 0
3171: && condjump_p (other)
3172: && no_labels_between_p (other, insn)
3173: && ! mostly_true_jump (other,
3174: get_branch_condition (other,
3175: JUMP_LABEL (other))))
3176: {
3177: rtx other_target = JUMP_LABEL (other);
3178:
3179: /* Increment the count of OTHER_TARGET, so it doesn't get deleted
3180: as we move the label. */
3181: if (other_target)
3182: ++LABEL_NUSES (other_target);
3183:
3184: if (invert_jump (other, target_label))
3185: redirect_jump (insn, other_target);
3186:
3187: if (other_target)
3188: --LABEL_NUSES (other_target);
3189: }
3190:
3191: /* Now look only at cases where we have filled a delay slot. */
3192: if (GET_CODE (insn) != INSN
3193: || GET_CODE (PATTERN (insn)) != SEQUENCE)
3194: continue;
3195:
3196: pat = PATTERN (insn);
3197: delay_insn = XVECEXP (pat, 0, 0);
3198:
3199: /* See if the first insn in the delay slot is redundant with some
3200: previous insn. Remove it from the delay slot if so; then set up
3201: to reprocess this insn. */
3202: if (redundant_insn_p (XVECEXP (pat, 0, 1), delay_insn, 0))
3203: {
3204: delete_from_delay_slot (XVECEXP (pat, 0, 1));
3205: next = prev_active_insn (next);
3206: continue;
3207: }
3208:
3209: /* Now look only at the cases where we have a filled JUMP_INSN. */
3210: if (GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3211: || ! condjump_p (XVECEXP (PATTERN (insn), 0, 0)))
3212: continue;
3213:
3214: target_label = JUMP_LABEL (delay_insn);
3215:
3216: if (target_label)
3217: {
3218: /* If this jump goes to another unconditional jump, thread it, but
3219: don't convert a jump into a RETURN here. */
3220: trial = follow_jumps (target_label, 1);
3221: trial = prev_label (next_active_insn (trial));
3222: if (trial == 0 && target_label != 0)
3223: trial = find_end_label ();
3224:
3225: if (trial != target_label)
3226: {
3227: redirect_jump (delay_insn, trial);
3228: target_label = trial;
3229: }
3230:
3231: /* If the first insn at TARGET_LABEL is redundant with a previous
3232: insn, redirect the jump to the following insn process again. */
3233: trial = next_active_insn (target_label);
3234: if (trial && GET_CODE (PATTERN (trial)) != SEQUENCE
3235: && redundant_insn_p (trial, insn, 0))
3236: {
3237: trial = next_active_insn (trial);
3238: if (trial == 0)
3239: target_label = find_end_label ();
3240: else
3241: target_label = get_label_before (trial);
3242: redirect_jump (delay_insn, target_label);
3243: next = insn;
3244: continue;
3245: }
3246:
3247: /* Similarly, if it is an unconditional jump with one insn in its
3248: delay list and that insn is redundant, thread the jump. */
3249: if (trial && GET_CODE (PATTERN (trial)) == SEQUENCE
3250: && XVECLEN (PATTERN (trial), 0) == 2
3251: && GET_CODE (XVECEXP (PATTERN (trial), 0, 0)) == JUMP_INSN
3252: && (simplejump_p (XVECEXP (PATTERN (trial), 0, 0))
3253: || GET_CODE (PATTERN (XVECEXP (PATTERN (trial), 0, 0))) == RETURN)
3254: && redundant_insn_p (XVECEXP (PATTERN (trial), 0, 1), insn, 0))
3255: {
3256: target_label = JUMP_LABEL (XVECEXP (PATTERN (trial), 0, 0));
3257: if (target_label == 0)
3258: target_label = find_end_label ();
3259: redirect_jump (delay_insn, target_label);
3260: next = insn;
3261: continue;
3262: }
3263: }
3264:
3265: if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3266: && prev_active_insn (target_label) == insn
3267: #ifdef HAVE_cc0
3268: /* If the last insn in the delay slot sets CC0 for some insn,
3269: various code assumes that it is in a delay slot. We could
3270: put it back where it belonged and delete the register notes,
3271: but it doesn't seem worhwhile in this uncommon case. */
3272: && ! find_reg_note (XVECEXP (pat, 0, XVECLEN (pat, 0) - 1),
3273: REG_CC_USER, 0)
3274: #endif
3275: )
3276: {
3277: /* All this insn does is execute its delay list and jump to the
3278: following insn. So delete the jump and just execute the delay
3279: list insns.
3280:
3281: We do this by deleting the INSN containing the SEQUENCE, then
3282: re-emitting the insns separately, and then deleting the jump.
3283: This allows the count of the jump target to be properly
3284: decremented. */
3285:
3286: trial = PREV_INSN (insn);
3287: delete_insn (insn);
3288: emit_insn_after (pat, trial);
3289: delete_scheduled_jump (delay_insn);
3290: continue;
3291: }
3292:
3293: /* See if this jump (with its delay slots) branches around another
3294: jump (without delay slots). If so, invert this jump and point
3295: it to the target of the second jump. We cannot do this for
3296: annulled jumps, though. Again, don't convert a jump to a RETURN
3297: here. */
3298: if (! INSN_ANNULLED_BRANCH_P (delay_insn)
3299: && next && GET_CODE (next) == JUMP_INSN
3300: && (simplejump_p (next) || GET_CODE (PATTERN (next)) == RETURN)
3301: && next_active_insn (target_label) == next_active_insn (next)
3302: && no_labels_between_p (insn, next))
3303: {
3304: rtx label = JUMP_LABEL (next);
3305: rtx old_label = JUMP_LABEL (delay_insn);
3306:
3307: if (label == 0)
3308: label = find_end_label ();
3309:
3310: /* Be careful how we do this to avoid deleting code or labels
3311: that are momentarily dead. See similar optimization in jump.c */
3312: if (old_label)
3313: ++LABEL_NUSES (old_label);
3314:
3315: if (invert_jump (delay_insn, label))
3316: {
3317: delete_insn (next);
3318: next = insn;
3319: }
3320:
3321: if (old_label && --LABEL_NUSES (old_label) == 0)
3322: delete_insn (old_label);
3323: continue;
3324: }
3325:
3326: /* If we own the thread opposite the way this insn branches, see if we
3327: can merge its delay slots with following insns. */
3328: if (INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3329: && own_thread_p (NEXT_INSN (insn), 0, 1))
3330: try_merge_delay_insns (insn, next);
3331: else if (! INSN_FROM_TARGET_P (XVECEXP (pat, 0, 1))
3332: && own_thread_p (target_label, target_label, 0))
3333: try_merge_delay_insns (insn, next_active_insn (target_label));
3334:
3335: /* If we get here, we haven't deleted INSN. But we may have deleted
3336: NEXT, so recompute it. */
3337: next = next_active_insn (insn);
3338: }
3339: }
3340:
3341: #ifdef HAVE_return
3342:
3343: /* Look for filled jumps to the end of function label. We can try to convert
3344: them into RETURN insns if the insns in the delay slot are valid for the
3345: RETURN as well. */
3346:
3347: static void
3348: make_return_insns (first)
3349: rtx first;
3350: {
3351: rtx insn, jump_insn, pat;
3352: rtx real_return_label = end_of_function_label;
3353: int slots, i;
3354:
3355: /* See if there is a RETURN insn in the function other than the one we
3356: made for END_OF_FUNCTION_LABEL. If so, set up anything we can't change
3357: into a RETURN to jump to it. */
3358: for (insn = first; insn; insn = NEXT_INSN (insn))
3359: if (GET_CODE (insn) == JUMP_INSN && GET_CODE (PATTERN (insn)) == RETURN)
3360: {
3361: real_return_label = get_label_before (insn);
3362: break;
3363: }
3364:
3365: /* Show an extra usage of REAL_RETURN_LABEL so it won't go away if it
3366: was equal to END_OF_FUNCTION_LABEL. */
3367: LABEL_NUSES (real_return_label)++;
3368:
3369: /* Clear the list of insns to fill so we can use it. */
3370: obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3371:
3372: for (insn = first; insn; insn = NEXT_INSN (insn))
3373: {
3374: /* Only look at filled JUMP_INSNs that go to the end of function
3375: label. */
3376: if (GET_CODE (insn) != INSN
3377: || GET_CODE (PATTERN (insn)) != SEQUENCE
3378: || GET_CODE (XVECEXP (PATTERN (insn), 0, 0)) != JUMP_INSN
3379: || JUMP_LABEL (XVECEXP (PATTERN (insn), 0, 0)) != end_of_function_label)
3380: continue;
3381:
3382: pat = PATTERN (insn);
3383: jump_insn = XVECEXP (pat, 0, 0);
3384:
3385: /* If we can't make the jump into a RETURN, redirect it to the best
3386: RETURN and go on to the next insn. */
3387: if (! redirect_jump (jump_insn, 0))
3388: {
3389: redirect_jump (jump_insn, real_return_label);
3390: continue;
3391: }
3392:
3393: /* See if this RETURN can accept the insns current in its delay slot.
3394: It can if it has more or an equal number of slots and the contents
3395: of each is valid. */
3396:
3397: slots = num_delay_slots (jump_insn);
3398: if (slots >= XVECLEN (pat, 0) - 1)
3399: {
3400: for (i = 1; i < XVECLEN (pat, 0); i++)
3401: if (! (
3402: #ifdef ANNUL_IFFALSE_SLOTS
3403: (INSN_ANNULLED_BRANCH_P (jump_insn)
3404: && INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3405: ? eligible_for_annul_false (jump_insn, i - 1,
3406: XVECEXP (pat, 0, i)) :
3407: #endif
3408: #ifdef ANNUL_IFTRUE_SLOTS
3409: (INSN_ANNULLED_BRANCH_P (jump_insn)
3410: && ! INSN_FROM_TARGET_P (XVECEXP (pat, 0, i)))
3411: ? eligible_for_annul_true (jump_insn, i - 1,
3412: XVECEXP (pat, 0, i)) :
3413: #endif
3414: eligible_for_delay (jump_insn, i -1, XVECEXP (pat, 0, i))))
3415: break;
3416: }
3417: else
3418: i = 0;
3419:
3420: if (i == XVECLEN (pat, 0))
3421: continue;
3422:
3423: /* We have to do something with this insn. If it is an unconditional
3424: RETURN, delete the SEQUENCE and output the individual insns,
3425: followed by the RETURN. Then set things up so we try to find
3426: insns for its delay slots, if it needs some. */
3427: if (GET_CODE (PATTERN (jump_insn)) == RETURN)
3428: {
3429: rtx prev = PREV_INSN (insn);
3430:
3431: delete_insn (insn);
3432: for (i = 1; i < XVECLEN (pat, 0); i++)
3433: prev = emit_insn_after (PATTERN (XVECEXP (pat, 0, i)), prev);
3434:
3435: insn = emit_jump_insn_after (PATTERN (jump_insn), prev);
3436: emit_barrier_after (insn);
3437:
3438: if (slots)
3439: obstack_ptr_grow (&unfilled_slots_obstack, insn);
3440: }
3441: else
3442: /* It is probably more efficient to keep this with its current
3443: delay slot as a branch to a RETURN. */
3444: redirect_jump (jump_insn, real_return_label);
3445: }
3446:
3447: /* Now delete REAL_RETURN_LABEL if we never used it. Then try to fill any
3448: new delay slots we have created. */
3449: if (--LABEL_NUSES (real_return_label) == 0)
3450: delete_insn (real_return_label);
3451:
3452: fill_simple_delay_slots (first, 1);
3453: fill_simple_delay_slots (first, 0);
3454: }
3455: #endif
3456:
3457: /* Try to find insns to place in delay slots. */
3458:
3459: void
3460: dbr_schedule (first, file)
3461: rtx first;
3462: FILE *file;
3463: {
3464: rtx insn, next;
3465: int i;
3466: #if 0
3467: int old_flag_no_peephole = flag_no_peephole;
3468:
3469: /* Execute `final' once in prescan mode to delete any insns that won't be
3470: used. Don't let final try to do any peephole optimization--it will
3471: ruin dataflow information for this pass. */
3472:
3473: flag_no_peephole = 1;
3474: final (first, 0, NO_DEBUG, 1, 1);
3475: flag_no_peephole = old_flag_no_peephole;
3476: #endif
3477:
3478: /* Find the highest INSN_UID and allocate and initialize our map from
3479: INSN_UID's to position in code. */
3480: for (max_uid = 0, insn = first; insn; insn = NEXT_INSN (insn))
3481: if (INSN_UID (insn) > max_uid)
3482: max_uid = INSN_UID (insn);
3483:
3484: uid_to_ruid = (int *) alloca ((max_uid + 1) * sizeof (int *));
3485: for (i = 0, insn = first; insn; i++, insn = NEXT_INSN (insn))
3486: uid_to_ruid[INSN_UID (insn)] = i;
3487:
3488: /* Initialize the list of insns that need filling. */
3489: if (unfilled_firstobj == 0)
3490: {
3491: gcc_obstack_init (&unfilled_slots_obstack);
3492: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3493: }
3494:
3495: for (insn = next_active_insn (first); insn; insn = next_active_insn (insn))
3496: {
3497: rtx target;
3498:
3499: INSN_ANNULLED_BRANCH_P (insn) = 0;
3500: INSN_FROM_TARGET_P (insn) = 0;
3501:
3502: /* Skip vector tables. We can't get attributes for them. */
3503: if (GET_CODE (insn) == JUMP_INSN
3504: && (GET_CODE (PATTERN (insn)) == ADDR_VEC
3505: || GET_CODE (PATTERN (insn)) == ADDR_DIFF_VEC))
3506: continue;
3507:
3508: if (num_delay_slots (insn) > 0)
3509: obstack_ptr_grow (&unfilled_slots_obstack, insn);
3510:
3511: /* Ensure all jumps go to the last of a set of consecutive labels. */
3512: if (GET_CODE (insn) == JUMP_INSN && condjump_p (insn)
3513: && JUMP_LABEL (insn) != 0
3514: && ((target = prev_label (next_active_insn (JUMP_LABEL (insn))))
3515: != JUMP_LABEL (insn)))
3516: redirect_jump (insn, target);
3517: }
3518:
3519: /* Indicate what resources are required to be valid at the end of the current
3520: function. The condition code never is and memory always is. If the
3521: frame pointer is needed, it is and so is the stack pointer unless
3522: EXIT_IGNORE_STACK is non-zero. If the frame pointer is not needed, the
3523: stack pointer is. In addition, registers used to return the function
3524: value are needed. */
3525:
3526: end_of_function_needs.cc = 0;
3527: end_of_function_needs.memory = 1;
3528: CLEAR_HARD_REG_SET (end_of_function_needs.regs);
3529:
3530: if (frame_pointer_needed)
3531: {
3532: SET_HARD_REG_BIT (end_of_function_needs.regs, FRAME_POINTER_REGNUM);
3533: #ifdef EXIT_IGNORE_STACK
3534: if (! EXIT_IGNORE_STACK)
3535: #endif
3536: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3537: }
3538: else
3539: SET_HARD_REG_BIT (end_of_function_needs.regs, STACK_POINTER_REGNUM);
3540:
3541: if (current_function_return_rtx != 0
3542: && GET_CODE (current_function_return_rtx) == REG)
3543: mark_referenced_resources (current_function_return_rtx,
3544: &end_of_function_needs, 0);
3545:
3546: /* Show we haven't computed an end-of-function label yet. */
3547: end_of_function_label = 0;
3548:
3549: /* Allocate and initialize the tables used by mark_target_live_regs. */
3550: target_hash_table
3551: = (struct target_info **) alloca ((TARGET_HASH_PRIME
3552: * sizeof (struct target_info *)));
3553: bzero (target_hash_table, TARGET_HASH_PRIME * sizeof (struct target_info *));
3554:
3555: bb_ticks = (int *) alloca (n_basic_blocks * sizeof (int));
3556: bzero (bb_ticks, n_basic_blocks * sizeof (int));
3557:
3558: /* Initialize the statistics for this function. */
3559: bzero (num_insns_needing_delays, sizeof num_insns_needing_delays);
3560: bzero (num_filled_delays, sizeof num_filled_delays);
3561:
3562: /* Now do the delay slot filling. Try everything twice in case earlier
3563: changes make more slots fillable. */
3564:
3565: for (reorg_pass_number = 0;
3566: reorg_pass_number < MAX_REORG_PASSES;
3567: reorg_pass_number++)
3568: {
3569: fill_simple_delay_slots (first, 1);
3570: fill_simple_delay_slots (first, 0);
3571: fill_eager_delay_slots (first);
3572: relax_delay_slots (first);
3573: }
3574:
3575: /* Delete any USE insns made by update_block; subsequent passes don't need
3576: them or know how to deal with them. */
3577: for (insn = first; insn; insn = next)
3578: {
3579: next = NEXT_INSN (insn);
3580:
3581: if (GET_CODE (insn) == INSN && GET_CODE (PATTERN (insn)) == USE
3582: && (GET_CODE (XEXP (PATTERN (insn), 0)) == INSN
3583: || GET_CODE (XEXP (PATTERN (insn), 0)) == JUMP_INSN
3584: || GET_CODE (XEXP (PATTERN (insn), 0)) == CALL_INSN))
3585: next = delete_insn (insn);
3586: }
3587:
3588: /* If we made an end of function label, indicate that it is now
3589: safe to delete it by undoing our prior adjustment to LABEL_NUSES.
3590: If it is now unused, delete it. */
3591: if (end_of_function_label && --LABEL_NUSES (end_of_function_label) == 0)
3592: delete_insn (end_of_function_label);
3593:
3594: #ifdef HAVE_return
3595: if (HAVE_return && end_of_function_label != 0)
3596: make_return_insns (first);
3597: #endif
3598:
3599: obstack_free (&unfilled_slots_obstack, unfilled_firstobj);
3600:
3601: /* It is not clear why the line below is needed, but it does seem to be. */
3602: unfilled_firstobj = (rtx *) obstack_alloc (&unfilled_slots_obstack, 0);
3603:
3604: if (file)
3605: {
3606: register int i, j, need_comma;
3607:
3608: for (reorg_pass_number = 0;
3609: reorg_pass_number < MAX_REORG_PASSES;
3610: reorg_pass_number++)
3611: {
3612: fprintf (file, ";; Reorg pass #%d:\n", reorg_pass_number + 1);
3613: for (i = 0; i < NUM_REORG_FUNCTIONS; i++)
3614: {
3615: need_comma = 0;
3616: fprintf (file, ";; Reorg function #%d\n", i);
3617:
3618: fprintf (file, ";; %d insns needing delay slots\n;; ",
3619: num_insns_needing_delays[i][reorg_pass_number]);
3620:
3621: for (j = 0; j < MAX_DELAY_HISTOGRAM; j++)
3622: if (num_filled_delays[i][j][reorg_pass_number])
3623: {
3624: if (need_comma)
3625: fprintf (file, ", ");
3626: need_comma = 1;
3627: fprintf (file, "%d got %d delays",
3628: num_filled_delays[i][j][reorg_pass_number], j);
3629: }
3630: fprintf (file, "\n");
3631: }
3632: }
3633: }
3634: }
3635: #endif /* DELAY_SLOTS */
This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.