sched-ebb.c revision 90075
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) 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 2, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING. If not, write to the Free 21Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2202111-1307, USA. */ 23 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" 41 42/* The number of insns to be scheduled in total. */ 43static int target_n_insns; 44/* The number of insns scheduled so far. */ 45static int sched_n_insns; 46 47/* Implementations of the sched_info functions for region scheduling. */ 48static void init_ready_list PARAMS ((struct ready_list *)); 49static int can_schedule_ready_p PARAMS ((rtx)); 50static int new_ready PARAMS ((rtx)); 51static int schedule_more_p PARAMS ((void)); 52static const char *print_insn PARAMS ((rtx, int)); 53static int rank PARAMS ((rtx, rtx)); 54static int contributes_to_priority PARAMS ((rtx, rtx)); 55static void compute_jump_reg_dependencies PARAMS ((rtx, regset)); 56static void schedule_ebb PARAMS ((rtx, rtx)); 57 58/* Return nonzero if there are more insns that should be scheduled. */ 59 60static int 61schedule_more_p () 62{ 63 return sched_n_insns < target_n_insns; 64} 65 66/* Add all insns that are initially ready to the ready list READY. Called 67 once before scheduling a set of insns. */ 68 69static void 70init_ready_list (ready) 71 struct ready_list *ready; 72{ 73 rtx prev_head = current_sched_info->prev_head; 74 rtx next_tail = current_sched_info->next_tail; 75 rtx insn; 76 77 target_n_insns = 0; 78 sched_n_insns = 0; 79 80#if 0 81 /* Print debugging information. */ 82 if (sched_verbose >= 5) 83 debug_dependencies (); 84#endif 85 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)) 89 { 90 rtx next; 91 92 if (! INSN_P (insn)) 93 continue; 94 next = NEXT_INSN (insn); 95 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++; 101 } 102} 103 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. */ 106 107static int 108can_schedule_ready_p (insn) 109 rtx insn ATTRIBUTE_UNUSED; 110{ 111 sched_n_insns++; 112 return 1; 113} 114 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. */ 118static int 119new_ready (next) 120 rtx next ATTRIBUTE_UNUSED; 121{ 122 return 1; 123} 124 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. */ 129 130static const char * 131print_insn (insn, aligned) 132 rtx insn; 133 int aligned ATTRIBUTE_UNUSED; 134{ 135 static char tmp[80]; 136 137 sprintf (tmp, "%4d", INSN_UID (insn)); 138 return tmp; 139} 140 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. */ 144 145static int 146rank (insn1, insn2) 147 rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED; 148{ 149 return 0; 150} 151 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. */ 155 156static int 157contributes_to_priority (next, insn) 158 rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED; 159{ 160 return 1; 161} 162 163/* INSN is a JUMP_INSN. Store the set of registers that must be considered 164 to be set by this jump in SET. */ 165 166static void 167compute_jump_reg_dependencies (insn, set) 168 rtx insn; 169 regset set; 170{ 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) 175 { 176 bitmap_operation (set, set, e->dest->global_live_at_start, 177 BITMAP_IOR); 178 } 179} 180 181/* Used in schedule_insns to initialize current_sched_info for scheduling 182 regions (or single basic blocks). */ 183 184static struct sched_info ebb_sched_info = 185{ 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, 194 195 NULL, NULL, 196 NULL, NULL, 197 0, 1 198}; 199 200/* Schedule a single extended basic block, defined by the boundaries HEAD 201 and TAIL. */ 202 203static void 204schedule_ebb (head, tail) 205 rtx head, tail; 206{ 207 int n_insns; 208 struct deps tmp_deps; 209 210 if (no_real_insns_p (head, tail)) 211 return; 212 213 init_deps_global (); 214 215 /* Compute LOG_LINKS. */ 216 init_deps (&tmp_deps); 217 sched_analyze (&tmp_deps, head, tail); 218 free_deps (&tmp_deps); 219 220 /* Compute INSN_DEPEND. */ 221 compute_forward_dependences (head, tail); 222 223 /* Set priorities. */ 224 n_insns = set_priorities (head, tail); 225 226 current_sched_info->prev_head = PREV_INSN (head); 227 current_sched_info->next_tail = NEXT_INSN (tail); 228 229 if (write_symbols != NO_DEBUG) 230 { 231 save_line_notes (0, head, tail); 232 rm_line_notes (head, tail); 233 } 234 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)) 242 { 243 rtx note; 244 245 for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 246 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 247 { 248 remove_note (head, note); 249 note = XEXP (note, 1); 250 remove_note (head, note); 251 } 252 } 253 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); 258 259 current_sched_info->queue_must_finish_empty = 1; 260 261 schedule_block (-1, n_insns); 262 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; 268 269 if (write_symbols != NO_DEBUG) 270 restore_line_notes (head, tail); 271 272 finish_deps_global (); 273} 274 275/* The one entry point in this file. DUMP_FILE is the dump file for 276 this pass. */ 277 278void 279schedule_ebbs (dump_file) 280 FILE *dump_file; 281{ 282 int i; 283 284 /* Taking care of this degenerate case makes the rest of 285 this code simpler. */ 286 if (n_basic_blocks == 0) 287 return; 288 289 scope_to_insns_initialize (); 290 291 sched_init (dump_file); 292 293 current_sched_info = &ebb_sched_info; 294 295 allocate_reg_life_data (); 296 compute_bb_for_insn (get_max_uid ()); 297 298 /* Schedule every region in the subroutine. */ 299 for (i = 0; i < n_basic_blocks; i++) 300 { 301 rtx head = BASIC_BLOCK (i)->head; 302 rtx tail; 303 304 for (;;) 305 { 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) 318 { 319 rtx x = find_reg_note (tail, REG_BR_PROB, 0); 320 if (x) 321 { 322 int pred_val = INTVAL (XEXP (x, 0)); 323 if (pred_val > REG_BR_PROB_BASE / 2) 324 break; 325 } 326 } 327 328 i++; 329 } 330 331 /* Blah. We should fix the rest of the code not to get confused by 332 a note or two. */ 333 while (head != tail) 334 { 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; 343 } 344 345 schedule_ebb (head, tail); 346 } 347 348 /* It doesn't make much sense to try and update life information here - we 349 probably messed up even the flow graph. */ 350 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 ()); 355 356 if (write_symbols != NO_DEBUG) 357 rm_redundant_line_notes (); 358 359 scope_to_insns_finalize (); 360 361 sched_finish (); 362} 363