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