]>
Commit | Line | Data |
---|---|---|
18e720b3 BS |
1 | /* Instruction scheduling pass. |
2 | Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, | |
14052b68 | 3 | 1999, 2000, 2001 Free Software Foundation, Inc. |
18e720b3 BS |
4 | Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, |
5 | and currently maintained by, Jim Wilson (wilson@cygnus.com) | |
6 | ||
7 | This file is part of GNU CC. | |
8 | ||
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 | |
12 | later version. | |
13 | ||
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 | |
17 | for more details. | |
18 | ||
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 | |
22 | 02111-1307, USA. */ | |
23 | \f | |
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 "sched-int.h" | |
40 | \f | |
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; | |
45 | ||
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)); | |
56 | ||
57 | /* Return nonzero if there are more insns that should be scheduled. */ | |
58 | ||
59 | static int | |
60 | schedule_more_p () | |
61 | { | |
62 | return sched_n_insns < target_n_insns; | |
63 | } | |
64 | ||
65 | /* Add all insns that are initially ready to the ready list READY. Called | |
66 | once before scheduling a set of insns. */ | |
67 | ||
68 | static void | |
69 | init_ready_list (ready) | |
70 | struct ready_list *ready; | |
71 | { | |
72 | rtx prev_head = current_sched_info->prev_head; | |
73 | rtx next_tail = current_sched_info->next_tail; | |
74 | rtx insn; | |
75 | ||
76 | target_n_insns = 0; | |
77 | sched_n_insns = 0; | |
78 | ||
79 | #if 0 | |
80 | /* Print debugging information. */ | |
81 | if (sched_verbose >= 5) | |
82 | debug_dependencies (); | |
83 | #endif | |
84 | ||
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)) | |
88 | { | |
89 | rtx next; | |
90 | ||
91 | if (! INSN_P (insn)) | |
92 | continue; | |
93 | next = NEXT_INSN (insn); | |
94 | ||
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))) | |
99 | target_n_insns++; | |
100 | } | |
101 | } | |
102 | ||
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. */ | |
105 | ||
106 | static int | |
107 | can_schedule_ready_p (insn) | |
108 | rtx insn ATTRIBUTE_UNUSED; | |
109 | { | |
110 | sched_n_insns++; | |
111 | return 1; | |
112 | } | |
113 | ||
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. */ | |
117 | static int | |
118 | new_ready (next) | |
119 | rtx next ATTRIBUTE_UNUSED; | |
120 | { | |
121 | return 1; | |
122 | } | |
123 | ||
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. */ | |
128 | ||
129 | static const char * | |
130 | print_insn (insn, aligned) | |
131 | rtx insn; | |
132 | int aligned ATTRIBUTE_UNUSED; | |
133 | { | |
134 | static char tmp[80]; | |
135 | ||
136 | sprintf (tmp, "%4d", INSN_UID (insn)); | |
137 | return tmp; | |
138 | } | |
139 | ||
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. */ | |
143 | ||
144 | static int | |
145 | rank (insn1, insn2) | |
146 | rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED; | |
147 | { | |
148 | return 0; | |
149 | } | |
150 | ||
151 | /* NEXT is an instruction that depends on INSN (a backward dependence); | |
152 | return nonzero if we should include this dependence in priority | |
153 | calculations. */ | |
154 | ||
155 | static int | |
156 | contributes_to_priority (next, insn) | |
157 | rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED; | |
158 | { | |
159 | return 1; | |
160 | } | |
161 | ||
162 | /* INSN is a JUMP_INSN. Store the set of registers that must be considered | |
163 | to be set by this jump in SET. */ | |
164 | ||
165 | static void | |
166 | compute_jump_reg_dependencies (insn, set) | |
167 | rtx insn; | |
168 | regset set; | |
169 | { | |
170 | basic_block b = BLOCK_FOR_INSN (insn); | |
171 | edge e; | |
172 | for (e = b->succ; e; e = e->succ_next) | |
173 | if ((e->flags & EDGE_FALLTHRU) == 0) | |
174 | { | |
175 | bitmap_operation (set, set, e->dest->global_live_at_start, | |
176 | BITMAP_IOR); | |
177 | } | |
178 | } | |
179 | ||
180 | /* Used in schedule_insns to initialize current_sched_info for scheduling | |
181 | regions (or single basic blocks). */ | |
182 | ||
183 | static struct sched_info ebb_sched_info = | |
184 | { | |
185 | init_ready_list, | |
186 | can_schedule_ready_p, | |
187 | schedule_more_p, | |
188 | new_ready, | |
189 | rank, | |
190 | print_insn, | |
191 | contributes_to_priority, | |
192 | compute_jump_reg_dependencies, | |
193 | ||
194 | NULL, NULL, | |
195 | NULL, NULL, | |
4b6c5340 | 196 | 0, 1 |
18e720b3 BS |
197 | }; |
198 | \f | |
199 | /* Schedule a single extended basic block, defined by the boundaries HEAD | |
200 | and TAIL. */ | |
201 | ||
202 | static void | |
203 | schedule_ebb (head, tail) | |
204 | rtx head, tail; | |
205 | { | |
206 | int n_insns; | |
207 | struct deps tmp_deps; | |
208 | ||
209 | if (no_real_insns_p (head, tail)) | |
210 | return; | |
211 | ||
212 | init_deps_global (); | |
213 | ||
214 | /* Compute LOG_LINKS. */ | |
215 | init_deps (&tmp_deps); | |
216 | sched_analyze (&tmp_deps, head, tail); | |
217 | free_deps (&tmp_deps); | |
218 | ||
219 | /* Compute INSN_DEPEND. */ | |
220 | compute_forward_dependences (head, tail); | |
221 | ||
222 | /* Set priorities. */ | |
223 | n_insns = set_priorities (head, tail); | |
224 | ||
225 | current_sched_info->prev_head = PREV_INSN (head); | |
226 | current_sched_info->next_tail = NEXT_INSN (tail); | |
227 | ||
228 | if (write_symbols != NO_DEBUG) | |
229 | { | |
230 | save_line_notes (0, head, tail); | |
231 | rm_line_notes (head, tail); | |
232 | } | |
233 | ||
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 | |
570a98eb | 239 | block, and so we have to take it out. */ |
18e720b3 BS |
240 | if (INSN_P (head)) |
241 | { | |
242 | rtx note; | |
243 | ||
244 | for (note = REG_NOTES (head); note; note = XEXP (note, 1)) | |
245 | if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) | |
246 | { | |
570a98eb JH |
247 | remove_note (head, note); |
248 | note = XEXP (note, 1); | |
249 | remove_note (head, note); | |
18e720b3 BS |
250 | } |
251 | } | |
252 | ||
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); | |
257 | ||
258 | current_sched_info->queue_must_finish_empty = 1; | |
259 | ||
260 | schedule_block (-1, n_insns); | |
261 | ||
262 | /* Sanity check: verify that all region insns were scheduled. */ | |
263 | if (sched_n_insns != n_insns) | |
264 | abort (); | |
265 | head = current_sched_info->head; | |
266 | tail = current_sched_info->tail; | |
267 | ||
268 | if (write_symbols != NO_DEBUG) | |
14052b68 | 269 | restore_line_notes (head, tail); |
18e720b3 BS |
270 | |
271 | finish_deps_global (); | |
272 | } | |
273 | ||
274 | /* The one entry point in this file. DUMP_FILE is the dump file for | |
275 | this pass. */ | |
276 | ||
277 | void | |
278 | schedule_ebbs (dump_file) | |
279 | FILE *dump_file; | |
280 | { | |
281 | int i; | |
282 | ||
283 | /* Taking care of this degenerate case makes the rest of | |
284 | this code simpler. */ | |
285 | if (n_basic_blocks == 0) | |
286 | return; | |
287 | ||
288 | sched_init (dump_file); | |
289 | ||
290 | current_sched_info = &ebb_sched_info; | |
291 | ||
292 | allocate_reg_life_data (); | |
293 | compute_bb_for_insn (get_max_uid ()); | |
294 | ||
295 | /* Schedule every region in the subroutine. */ | |
296 | for (i = 0; i < n_basic_blocks; i++) | |
297 | { | |
298 | rtx head = BASIC_BLOCK (i)->head; | |
299 | rtx tail; | |
300 | ||
301 | for (;;) | |
302 | { | |
303 | basic_block b = BASIC_BLOCK (i); | |
304 | edge e; | |
305 | tail = b->end; | |
306 | if (i + 1 == n_basic_blocks | |
307 | || GET_CODE (BLOCK_HEAD (i + 1)) == CODE_LABEL) | |
308 | break; | |
309 | for (e = b->succ; e; e = e->succ_next) | |
310 | if ((e->flags & EDGE_FALLTHRU) != 0) | |
311 | break; | |
312 | if (! e) | |
313 | break; | |
314 | if (GET_CODE (tail) == JUMP_INSN) | |
315 | { | |
316 | rtx x = find_reg_note (tail, REG_BR_PROB, 0); | |
317 | if (x) | |
318 | { | |
319 | int pred_val = INTVAL (XEXP (x, 0)); | |
320 | if (pred_val > REG_BR_PROB_BASE / 2) | |
321 | break; | |
322 | } | |
323 | } | |
324 | ||
325 | i++; | |
326 | } | |
327 | ||
328 | /* Blah. We should fix the rest of the code not to get confused by | |
329 | a note or two. */ | |
330 | while (head != tail) | |
331 | { | |
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); | |
338 | else | |
339 | break; | |
340 | } | |
341 | ||
342 | schedule_ebb (head, tail); | |
343 | } | |
344 | ||
345 | /* It doesn't make much sense to try and update life information here - we | |
346 | probably messed up even the flow graph. */ | |
347 | ||
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 ()); | |
352 | ||
353 | if (write_symbols != NO_DEBUG) | |
354 | rm_redundant_line_notes (); | |
355 | ||
356 | sched_finish (); | |
357 | } |