OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [reorg.c] - Blame information for rev 859

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.