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