1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001 Free Software Foundation, Inc.
4 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by,
5 and currently maintained by, Jim Wilson (wilson@cygnus.com)
7 This file is part of GNU CC.
9 GNU CC is free software; you can redistribute it and/or modify it
10 under the terms of the GNU General Public License as published by the
11 Free Software Foundation; either version 2, or (at your option) any
14 GNU CC is distributed in the hope that it will be useful, but WITHOUT
15 ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
16 FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
19 You should have received a copy of the GNU General Public License
20 along with GNU CC; see the file COPYING. If not, write to the Free
21 the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
39 #include "sched-int.h"
41 /* The number of insns to be scheduled in total. */
42 static int target_n_insns
;
43 /* The number of insns scheduled so far. */
44 static int sched_n_insns
;
46 /* Implementations of the sched_info functions for region scheduling. */
47 static void init_ready_list
PARAMS ((struct ready_list
*));
48 static int can_schedule_ready_p
PARAMS ((rtx
));
49 static int new_ready
PARAMS ((rtx
));
50 static int schedule_more_p
PARAMS ((void));
51 static const char *print_insn
PARAMS ((rtx
, int));
52 static int rank
PARAMS ((rtx
, rtx
));
53 static int contributes_to_priority
PARAMS ((rtx
, rtx
));
54 static void compute_jump_reg_dependencies
PARAMS ((rtx
, regset
));
55 static void schedule_ebb
PARAMS ((rtx
, rtx
));
57 /* Return nonzero if there are more insns that should be scheduled. */
62 return sched_n_insns
< target_n_insns
;
65 /* Add all insns that are initially ready to the ready list READY. Called
66 once before scheduling a set of insns. */
69 init_ready_list (ready
)
70 struct ready_list
*ready
;
72 rtx prev_head
= current_sched_info
->prev_head
;
73 rtx next_tail
= current_sched_info
->next_tail
;
80 /* Print debugging information. */
81 if (sched_verbose
>= 5)
82 debug_dependencies ();
85 /* Initialize ready list with all 'ready' insns in target block.
86 Count number of insns in the target block being scheduled. */
87 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
93 next
= NEXT_INSN (insn
);
95 if (INSN_DEP_COUNT (insn
) == 0
96 && (SCHED_GROUP_P (next
) == 0 || ! INSN_P (next
)))
97 ready_add (ready
, insn
);
98 if (!(SCHED_GROUP_P (insn
)))
103 /* Called after taking INSN from the ready list. Returns nonzero if this
104 insn can be scheduled, nonzero if we should silently discard it. */
107 can_schedule_ready_p (insn
)
108 rtx insn ATTRIBUTE_UNUSED
;
114 /* Called after INSN has all its dependencies resolved. Return nonzero
115 if it should be moved to the ready list or the queue, or zero if we
116 should silently discard it. */
119 rtx next ATTRIBUTE_UNUSED
;
124 /* Return a string that contains the insn uid and optionally anything else
125 necessary to identify this insn in an output. It's valid to use a
126 static buffer for this. The ALIGNED parameter should cause the string
127 to be formatted so that multiple output lines will line up nicely. */
130 print_insn (insn
, aligned
)
132 int aligned ATTRIBUTE_UNUSED
;
136 sprintf (tmp
, "%4d", INSN_UID (insn
));
140 /* Compare priority of two insns. Return a positive number if the second
141 insn is to be preferred for scheduling, and a negative one if the first
142 is to be preferred. Zero if they are equally good. */
146 rtx insn1 ATTRIBUTE_UNUSED
, insn2 ATTRIBUTE_UNUSED
;
151 /* NEXT is an instruction that depends on INSN (a backward dependence);
152 return nonzero if we should include this dependence in priority
156 contributes_to_priority (next
, insn
)
157 rtx next ATTRIBUTE_UNUSED
, insn ATTRIBUTE_UNUSED
;
162 /* INSN is a JUMP_INSN. Store the set of registers that must be considered
163 to be set by this jump in SET. */
166 compute_jump_reg_dependencies (insn
, set
)
170 basic_block b
= BLOCK_FOR_INSN (insn
);
172 for (e
= b
->succ
; e
; e
= e
->succ_next
)
173 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
175 bitmap_operation (set
, set
, e
->dest
->global_live_at_start
,
180 /* Used in schedule_insns to initialize current_sched_info for scheduling
181 regions (or single basic blocks). */
183 static struct sched_info ebb_sched_info
=
186 can_schedule_ready_p
,
191 contributes_to_priority
,
192 compute_jump_reg_dependencies
,
199 /* Schedule a single extended basic block, defined by the boundaries HEAD
203 schedule_ebb (head
, tail
)
207 struct deps tmp_deps
;
209 if (no_real_insns_p (head
, tail
))
214 /* Compute LOG_LINKS. */
215 init_deps (&tmp_deps
);
216 sched_analyze (&tmp_deps
, head
, tail
);
217 free_deps (&tmp_deps
);
219 /* Compute INSN_DEPEND. */
220 compute_forward_dependences (head
, tail
);
222 /* Set priorities. */
223 n_insns
= set_priorities (head
, tail
);
225 current_sched_info
->prev_head
= PREV_INSN (head
);
226 current_sched_info
->next_tail
= NEXT_INSN (tail
);
228 if (write_symbols
!= NO_DEBUG
)
230 save_line_notes (0, head
, tail
);
231 rm_line_notes (head
, tail
);
234 /* rm_other_notes only removes notes which are _inside_ the
235 block---that is, it won't remove notes before the first real insn
236 or after the last real insn of the block. So if the first insn
237 has a REG_SAVE_NOTE which would otherwise be emitted before the
238 insn, it is redundant with the note before the start of the
239 block, and so we have to take it out. */
244 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
245 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
247 remove_note (head
, note
);
248 note
= XEXP (note
, 1);
249 remove_note (head
, note
);
253 /* Remove remaining note insns from the block, save them in
254 note_list. These notes are restored at the end of
255 schedule_block (). */
256 rm_other_notes (head
, tail
);
258 current_sched_info
->queue_must_finish_empty
= 1;
260 schedule_block (-1, n_insns
);
262 /* Sanity check: verify that all region insns were scheduled. */
263 if (sched_n_insns
!= n_insns
)
265 head
= current_sched_info
->head
;
266 tail
= current_sched_info
->tail
;
268 if (write_symbols
!= NO_DEBUG
)
269 restore_line_notes (head
, tail
);
271 finish_deps_global ();
274 /* The one entry point in this file. DUMP_FILE is the dump file for
278 schedule_ebbs (dump_file
)
283 /* Taking care of this degenerate case makes the rest of
284 this code simpler. */
285 if (n_basic_blocks
== 0)
288 sched_init (dump_file
);
290 current_sched_info
= &ebb_sched_info
;
292 allocate_reg_life_data ();
293 compute_bb_for_insn (get_max_uid ());
295 /* Schedule every region in the subroutine. */
296 for (i
= 0; i
< n_basic_blocks
; i
++)
298 rtx head
= BASIC_BLOCK (i
)->head
;
303 basic_block b
= BASIC_BLOCK (i
);
306 if (i
+ 1 == n_basic_blocks
307 || GET_CODE (BLOCK_HEAD (i
+ 1)) == CODE_LABEL
)
309 for (e
= b
->succ
; e
; e
= e
->succ_next
)
310 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
314 if (GET_CODE (tail
) == JUMP_INSN
)
316 rtx x
= find_reg_note (tail
, REG_BR_PROB
, 0);
319 int pred_val
= INTVAL (XEXP (x
, 0));
320 if (pred_val
> REG_BR_PROB_BASE
/ 2)
328 /* Blah. We should fix the rest of the code not to get confused by
332 if (GET_CODE (head
) == NOTE
)
333 head
= NEXT_INSN (head
);
334 else if (GET_CODE (tail
) == NOTE
)
335 tail
= PREV_INSN (tail
);
336 else if (GET_CODE (head
) == CODE_LABEL
)
337 head
= NEXT_INSN (head
);
342 schedule_ebb (head
, tail
);
345 /* It doesn't make much sense to try and update life information here - we
346 probably messed up even the flow graph. */
348 /* Reposition the prologue and epilogue notes in case we moved the
349 prologue/epilogue insns. */
350 if (reload_completed
)
351 reposition_prologue_and_epilogue_notes (get_insns ());
353 if (write_symbols
!= NO_DEBUG
)
354 rm_redundant_line_notes ();