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