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 (num_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. */
308 if (bb
->next_bb
== EXIT_BLOCK_PTR
309 || GET_CODE (bb
->next_bb
->head
) == CODE_LABEL
)
311 for (e
= bb
->succ
; e
; e
= e
->succ_next
)
312 if ((e
->flags
& EDGE_FALLTHRU
) != 0)
316 if (GET_CODE (tail
) == JUMP_INSN
)
318 rtx x
= find_reg_note (tail
, REG_BR_PROB
, 0);
321 int pred_val
= INTVAL (XEXP (x
, 0));
322 if (pred_val
> REG_BR_PROB_BASE
/ 2)
330 /* Blah. We should fix the rest of the code not to get confused by
334 if (GET_CODE (head
) == NOTE
)
335 head
= NEXT_INSN (head
);
336 else if (GET_CODE (tail
) == NOTE
)
337 tail
= PREV_INSN (tail
);
338 else if (GET_CODE (head
) == CODE_LABEL
)
339 head
= NEXT_INSN (head
);
344 schedule_ebb (head
, tail
);
347 /* It doesn't make much sense to try and update life information here - we
348 probably messed up even the flow graph. */
350 /* Reposition the prologue and epilogue notes in case we moved the
351 prologue/epilogue insns. */
352 if (reload_completed
)
353 reposition_prologue_and_epilogue_notes (get_insns ());
355 if (write_symbols
!= NO_DEBUG
)
356 rm_redundant_line_notes ();
358 scope_to_insns_finalize ();