Daily bump.
[official-gcc.git] / gcc / sched-ebb.c
blob31b5f3c19a113c12e639517a23e2894517078992
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 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
12 version.
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
17 for more details.
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
22 02111-1307, USA. */
24 #include "config.h"
25 #include "system.h"
26 #include "toplev.h"
27 #include "rtl.h"
28 #include "tm_p.h"
29 #include "hard-reg-set.h"
30 #include "basic-block.h"
31 #include "regs.h"
32 #include "function.h"
33 #include "flags.h"
34 #include "insn-config.h"
35 #include "insn-attr.h"
36 #include "except.h"
37 #include "toplev.h"
38 #include "recog.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 *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. */
60 static int
61 schedule_more_p ()
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. */
69 static void
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;
75 rtx insn;
77 target_n_insns = 0;
78 sched_n_insns = 0;
80 #if 0
81 /* Print debugging information. */
82 if (sched_verbose >= 5)
83 debug_dependencies ();
84 #endif
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))
90 rtx next;
92 if (! INSN_P (insn))
93 continue;
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)))
100 target_n_insns++;
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. */
107 static int
108 can_schedule_ready_p (insn)
109 rtx insn ATTRIBUTE_UNUSED;
111 sched_n_insns++;
112 return 1;
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. */
118 static int
119 new_ready (next)
120 rtx next ATTRIBUTE_UNUSED;
122 return 1;
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. */
130 static const char *
131 print_insn (insn, aligned)
132 rtx insn;
133 int aligned ATTRIBUTE_UNUSED;
135 static char tmp[80];
137 sprintf (tmp, "%4d", INSN_UID (insn));
138 return tmp;
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. */
145 static int
146 rank (insn1, insn2)
147 rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED;
149 return 0;
152 /* NEXT is an instruction that depends on INSN (a backward dependence);
153 return nonzero if we should include this dependence in priority
154 calculations. */
156 static int
157 contributes_to_priority (next, insn)
158 rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED;
160 return 1;
163 /* INSN is a JUMP_INSN. Store the set of registers that must be considered
164 to be set by this jump in SET. */
166 static void
167 compute_jump_reg_dependencies (insn, set)
168 rtx insn;
169 regset set;
171 basic_block b = BLOCK_FOR_INSN (insn);
172 edge e;
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,
177 BITMAP_IOR);
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 =
186 init_ready_list,
187 can_schedule_ready_p,
188 schedule_more_p,
189 new_ready,
190 rank,
191 print_insn,
192 contributes_to_priority,
193 compute_jump_reg_dependencies,
195 NULL, NULL,
196 NULL, NULL,
197 0, 1
200 /* Schedule a single extended basic block, defined by the boundaries HEAD
201 and TAIL. */
203 static void
204 schedule_ebb (head, tail)
205 rtx head, tail;
207 int n_insns;
208 struct deps tmp_deps;
210 if (no_real_insns_p (head, tail))
211 return;
213 init_deps_global ();
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. */
241 if (INSN_P (head))
243 rtx note;
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)
265 abort ();
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
276 this pass. */
278 void
279 schedule_ebbs (dump_file)
280 FILE *dump_file;
282 int i;
284 /* Taking care of this degenerate case makes the rest of
285 this code simpler. */
286 if (n_basic_blocks == 0)
287 return;
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;
302 rtx tail;
304 for (;;)
306 basic_block b = BASIC_BLOCK (i);
307 edge e;
308 tail = b->end;
309 if (i + 1 == n_basic_blocks
310 || GET_CODE (BLOCK_HEAD (i + 1)) == CODE_LABEL)
311 break;
312 for (e = b->succ; e; e = e->succ_next)
313 if ((e->flags & EDGE_FALLTHRU) != 0)
314 break;
315 if (! e)
316 break;
317 if (GET_CODE (tail) == JUMP_INSN)
319 rtx x = find_reg_note (tail, REG_BR_PROB, 0);
320 if (x)
322 int pred_val = INTVAL (XEXP (x, 0));
323 if (pred_val > REG_BR_PROB_BASE / 2)
324 break;
328 i++;
331 /* Blah. We should fix the rest of the code not to get confused by
332 a note or two. */
333 while (head != tail)
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);
341 else
342 break;
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 ();
361 sched_finish ();