1 /* Instruction scheduling pass.
2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
3 1999, 2000, 2001, 2002 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 GCC.
9 GCC is free software; you can redistribute it and/or modify it under
10 the terms of the GNU General Public License as published by the Free
11 Software Foundation; either version 2, or (at your option) any later
14 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
15 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 GCC; see the file COPYING. If not, write to the Free
21 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 "cfglayout.h"
40 #include "sched-int.h"
42 /* The number of insns to be scheduled in total. */
43 static int target_n_insns
;
44 /* The number of insns scheduled so far. */
45 static int sched_n_insns
;
47 /* Implementations of the sched_info functions for region scheduling. */
48 static void init_ready_list
PARAMS ((struct ready_list
*));
49 static int can_schedule_ready_p
PARAMS ((rtx
));
50 static int new_ready
PARAMS ((rtx
));
51 static int schedule_more_p
PARAMS ((void));
52 static const char *ebb_print_insn
PARAMS ((rtx
, int));
53 static int rank
PARAMS ((rtx
, rtx
));
54 static int contributes_to_priority
PARAMS ((rtx
, rtx
));
55 static void compute_jump_reg_dependencies
PARAMS ((rtx
, regset
));
56 static void schedule_ebb
PARAMS ((rtx
, rtx
));
58 /* Return nonzero if there are more insns that should be scheduled. */
63 return sched_n_insns
< target_n_insns
;
66 /* Add all insns that are initially ready to the ready list READY. Called
67 once before scheduling a set of insns. */
70 init_ready_list (ready
)
71 struct ready_list
*ready
;
73 rtx prev_head
= current_sched_info
->prev_head
;
74 rtx next_tail
= current_sched_info
->next_tail
;
81 /* Print debugging information. */
82 if (sched_verbose
>= 5)
83 debug_dependencies ();
86 /* Initialize ready list with all 'ready' insns in target block.
87 Count number of insns in the target block being scheduled. */
88 for (insn
= NEXT_INSN (prev_head
); insn
!= next_tail
; insn
= NEXT_INSN (insn
))
94 next
= NEXT_INSN (insn
);
96 if (INSN_DEP_COUNT (insn
) == 0
97 && (SCHED_GROUP_P (next
) == 0 || ! INSN_P (next
)))
98 ready_add (ready
, insn
);
99 if (!(SCHED_GROUP_P (insn
)))
104 /* Called after taking INSN from the ready list. Returns nonzero if this
105 insn can be scheduled, nonzero if we should silently discard it. */
108 can_schedule_ready_p (insn
)
109 rtx insn ATTRIBUTE_UNUSED
;
115 /* Called after INSN has all its dependencies resolved. Return nonzero
116 if it should be moved to the ready list or the queue, or zero if we
117 should silently discard it. */
120 rtx next ATTRIBUTE_UNUSED
;
125 /* Return a string that contains the insn uid and optionally anything else
126 necessary to identify this insn in an output. It's valid to use a
127 static buffer for this. The ALIGNED parameter should cause the string
128 to be formatted so that multiple output lines will line up nicely. */
131 ebb_print_insn (insn
, aligned
)
133 int aligned ATTRIBUTE_UNUSED
;
137 sprintf (tmp
, "%4d", INSN_UID (insn
));
141 /* Compare priority of two insns. Return a positive number if the second
142 insn is to be preferred for scheduling, and a negative one if the first
143 is to be preferred. Zero if they are equally good. */
147 rtx insn1 ATTRIBUTE_UNUSED
, insn2 ATTRIBUTE_UNUSED
;
152 /* NEXT is an instruction that depends on INSN (a backward dependence);
153 return nonzero if we should include this dependence in priority
157 contributes_to_priority (next
, insn
)
158 rtx next ATTRIBUTE_UNUSED
, insn ATTRIBUTE_UNUSED
;
163 /* INSN is a JUMP_INSN. Store the set of registers that must be considered
164 to be set by this jump in SET. */
167 compute_jump_reg_dependencies (insn
, set
)
171 basic_block b
= BLOCK_FOR_INSN (insn
);
173 for (e
= b
->succ
; e
; e
= e
->succ_next
)
174 if ((e
->flags
& EDGE_FALLTHRU
) == 0)
176 bitmap_operation (set
, set
, e
->dest
->global_live_at_start
,
181 /* Used in schedule_insns to initialize current_sched_info for scheduling
182 regions (or single basic blocks). */
184 static struct sched_info ebb_sched_info
=
187 can_schedule_ready_p
,
192 contributes_to_priority
,
193 compute_jump_reg_dependencies
,
200 /* Schedule a single extended basic block, defined by the boundaries HEAD
204 schedule_ebb (head
, tail
)
208 struct deps tmp_deps
;
210 if (no_real_insns_p (head
, tail
))
215 /* Compute LOG_LINKS. */
216 init_deps (&tmp_deps
);
217 sched_analyze (&tmp_deps
, head
, tail
);
218 free_deps (&tmp_deps
);
220 /* Compute INSN_DEPEND. */
221 compute_forward_dependences (head
, tail
);
223 /* Set priorities. */
224 n_insns
= set_priorities (head
, tail
);
226 current_sched_info
->prev_head
= PREV_INSN (head
);
227 current_sched_info
->next_tail
= NEXT_INSN (tail
);
229 if (write_symbols
!= NO_DEBUG
)
231 save_line_notes (0, head
, tail
);
232 rm_line_notes (head
, tail
);
235 /* rm_other_notes only removes notes which are _inside_ the
236 block---that is, it won't remove notes before the first real insn
237 or after the last real insn of the block. So if the first insn
238 has a REG_SAVE_NOTE which would otherwise be emitted before the
239 insn, it is redundant with the note before the start of the
240 block, and so we have to take it out. */
245 for (note
= REG_NOTES (head
); note
; note
= XEXP (note
, 1))
246 if (REG_NOTE_KIND (note
) == REG_SAVE_NOTE
)
248 remove_note (head
, note
);
249 note
= XEXP (note
, 1);
250 remove_note (head
, note
);
254 /* Remove remaining note insns from the block, save them in
255 note_list. These notes are restored at the end of
256 schedule_block (). */
257 rm_other_notes (head
, tail
);
259 current_sched_info
->queue_must_finish_empty
= 1;
261 schedule_block (-1, n_insns
);
263 /* Sanity check: verify that all region insns were scheduled. */
264 if (sched_n_insns
!= n_insns
)
266 head
= current_sched_info
->head
;
267 tail
= current_sched_info
->tail
;
269 if (write_symbols
!= NO_DEBUG
)
270 restore_line_notes (head
, tail
);
272 finish_deps_global ();
275 /* The one entry point in this file. DUMP_FILE is the dump file for
279 schedule_ebbs (dump_file
)
284 /* Taking care of this degenerate case makes the rest of
285 this code simpler. */
286 if (n_basic_blocks
== 0)
289 scope_to_insns_initialize ();
291 sched_init (dump_file
);
293 current_sched_info
= &ebb_sched_info
;
295 allocate_reg_life_data ();
296 compute_bb_for_insn (get_max_uid ());
298 /* Schedule every region in the subroutine. */
299 for (i
= 0; i
< n_basic_blocks
; i
++)
301 rtx head
= BASIC_BLOCK (i
)->head
;
306 basic_block b
= BASIC_BLOCK (i
);
309 if (i
+ 1 == n_basic_blocks
310 || GET_CODE (BLOCK_HEAD (i
+ 1)) == CODE_LABEL
)
312 for (e
= b
->succ
; e
; e
= e
->succ_next
)
313 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
317 if (GET_CODE (tail
) == JUMP_INSN
)
319 rtx x
= find_reg_note (tail
, REG_BR_PROB
, 0);
322 int pred_val
= INTVAL (XEXP (x
, 0));
323 if (pred_val
> REG_BR_PROB_BASE
/ 2)
331 /* Blah. We should fix the rest of the code not to get confused by
335 if (GET_CODE (head
) == NOTE
)
336 head
= NEXT_INSN (head
);
337 else if (GET_CODE (tail
) == NOTE
)
338 tail
= PREV_INSN (tail
);
339 else if (GET_CODE (head
) == CODE_LABEL
)
340 head
= NEXT_INSN (head
);
345 schedule_ebb (head
, tail
);
348 /* It doesn't make much sense to try and update life information here - we
349 probably messed up even the flow graph. */
351 /* Reposition the prologue and epilogue notes in case we moved the
352 prologue/epilogue insns. */
353 if (reload_completed
)
354 reposition_prologue_and_epilogue_notes (get_insns ());
356 if (write_symbols
!= NO_DEBUG
)
357 rm_redundant_line_notes ();
359 scope_to_insns_finalize ();