sched-ebb.c revision 119256
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) 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 *ebb_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, regset, 56 regset)); 57static void schedule_ebb PARAMS ((rtx, rtx)); 58 59/* Return nonzero if there are more insns that should be scheduled. */ 60 61static int 62schedule_more_p () 63{ 64 return sched_n_insns < target_n_insns; 65} 66 67/* Add all insns that are initially ready to the ready list READY. Called 68 once before scheduling a set of insns. */ 69 70static void 71init_ready_list (ready) 72 struct ready_list *ready; 73{ 74 rtx prev_head = current_sched_info->prev_head; 75 rtx next_tail = current_sched_info->next_tail; 76 rtx insn; 77 78 target_n_insns = 0; 79 sched_n_insns = 0; 80 81#if 0 82 /* Print debugging information. */ 83 if (sched_verbose >= 5) 84 debug_dependencies (); 85#endif 86 87 /* Initialize ready list with all 'ready' insns in target block. 88 Count number of insns in the target block being scheduled. */ 89 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn)) 90 { 91 rtx next; 92 93 if (! INSN_P (insn)) 94 continue; 95 next = NEXT_INSN (insn); 96 97 if (INSN_DEP_COUNT (insn) == 0 98 && (! INSN_P (next) || SCHED_GROUP_P (next) == 0)) 99 ready_add (ready, insn); 100 if (!(SCHED_GROUP_P (insn))) 101 target_n_insns++; 102 } 103} 104 105/* Called after taking INSN from the ready list. Returns nonzero if this 106 insn can be scheduled, nonzero if we should silently discard it. */ 107 108static int 109can_schedule_ready_p (insn) 110 rtx insn ATTRIBUTE_UNUSED; 111{ 112 sched_n_insns++; 113 return 1; 114} 115 116/* Called after INSN has all its dependencies resolved. Return nonzero 117 if it should be moved to the ready list or the queue, or zero if we 118 should silently discard it. */ 119static int 120new_ready (next) 121 rtx next ATTRIBUTE_UNUSED; 122{ 123 return 1; 124} 125 126/* Return a string that contains the insn uid and optionally anything else 127 necessary to identify this insn in an output. It's valid to use a 128 static buffer for this. The ALIGNED parameter should cause the string 129 to be formatted so that multiple output lines will line up nicely. */ 130 131static const char * 132ebb_print_insn (insn, aligned) 133 rtx insn; 134 int aligned ATTRIBUTE_UNUSED; 135{ 136 static char tmp[80]; 137 138 sprintf (tmp, "%4d", INSN_UID (insn)); 139 return tmp; 140} 141 142/* Compare priority of two insns. Return a positive number if the second 143 insn is to be preferred for scheduling, and a negative one if the first 144 is to be preferred. Zero if they are equally good. */ 145 146static int 147rank (insn1, insn2) 148 rtx insn1 ATTRIBUTE_UNUSED, insn2 ATTRIBUTE_UNUSED; 149{ 150 return 0; 151} 152 153/* NEXT is an instruction that depends on INSN (a backward dependence); 154 return nonzero if we should include this dependence in priority 155 calculations. */ 156 157static int 158contributes_to_priority (next, insn) 159 rtx next ATTRIBUTE_UNUSED, insn ATTRIBUTE_UNUSED; 160{ 161 return 1; 162} 163 164/* INSN is a JUMP_INSN, COND_SET is the set of registers that are 165 conditionally set before INSN. Store the set of registers that 166 must be considered as used by this jump in USED and that of 167 registers that must be considered as set in SET. */ 168 169static void 170compute_jump_reg_dependencies (insn, cond_set, used, set) 171 rtx insn; 172 regset cond_set, used, set; 173{ 174 basic_block b = BLOCK_FOR_INSN (insn); 175 edge e; 176 for (e = b->succ; e; e = e->succ_next) 177 if (e->flags & EDGE_FALLTHRU) 178 /* The jump may be a by-product of a branch that has been merged 179 in the main codepath after being conditionalized. Therefore 180 it may guard the fallthrough block from using a value that has 181 conditionally overwritten that of the main codepath. So we 182 consider that it restores the value of the main codepath. */ 183 bitmap_operation (set, e->dest->global_live_at_start, cond_set, 184 BITMAP_AND); 185 else 186 bitmap_operation (used, used, e->dest->global_live_at_start, 187 BITMAP_IOR); 188} 189 190/* Used in schedule_insns to initialize current_sched_info for scheduling 191 regions (or single basic blocks). */ 192 193static struct sched_info ebb_sched_info = 194{ 195 init_ready_list, 196 can_schedule_ready_p, 197 schedule_more_p, 198 new_ready, 199 rank, 200 ebb_print_insn, 201 contributes_to_priority, 202 compute_jump_reg_dependencies, 203 204 NULL, NULL, 205 NULL, NULL, 206 0, 1 207}; 208 209/* Schedule a single extended basic block, defined by the boundaries HEAD 210 and TAIL. */ 211 212static void 213schedule_ebb (head, tail) 214 rtx head, tail; 215{ 216 int n_insns; 217 struct deps tmp_deps; 218 219 if (no_real_insns_p (head, tail)) 220 return; 221 222 init_deps_global (); 223 224 /* Compute LOG_LINKS. */ 225 init_deps (&tmp_deps); 226 sched_analyze (&tmp_deps, head, tail); 227 free_deps (&tmp_deps); 228 229 /* Compute INSN_DEPEND. */ 230 compute_forward_dependences (head, tail); 231 232 /* Set priorities. */ 233 n_insns = set_priorities (head, tail); 234 235 current_sched_info->prev_head = PREV_INSN (head); 236 current_sched_info->next_tail = NEXT_INSN (tail); 237 238 if (write_symbols != NO_DEBUG) 239 { 240 save_line_notes (0, head, tail); 241 rm_line_notes (head, tail); 242 } 243 244 /* rm_other_notes only removes notes which are _inside_ the 245 block---that is, it won't remove notes before the first real insn 246 or after the last real insn of the block. So if the first insn 247 has a REG_SAVE_NOTE which would otherwise be emitted before the 248 insn, it is redundant with the note before the start of the 249 block, and so we have to take it out. */ 250 if (INSN_P (head)) 251 { 252 rtx note; 253 254 for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 255 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 256 { 257 remove_note (head, note); 258 note = XEXP (note, 1); 259 remove_note (head, note); 260 } 261 } 262 263 /* Remove remaining note insns from the block, save them in 264 note_list. These notes are restored at the end of 265 schedule_block (). */ 266 rm_other_notes (head, tail); 267 268 current_sched_info->queue_must_finish_empty = 1; 269 270 schedule_block (-1, n_insns); 271 272 /* Sanity check: verify that all region insns were scheduled. */ 273 if (sched_n_insns != n_insns) 274 abort (); 275 head = current_sched_info->head; 276 tail = current_sched_info->tail; 277 278 if (write_symbols != NO_DEBUG) 279 restore_line_notes (head, tail); 280 281 finish_deps_global (); 282} 283 284/* The one entry point in this file. DUMP_FILE is the dump file for 285 this pass. */ 286 287void 288schedule_ebbs (dump_file) 289 FILE *dump_file; 290{ 291 basic_block bb; 292 293 /* Taking care of this degenerate case makes the rest of 294 this code simpler. */ 295 if (n_basic_blocks == 0) 296 return; 297 298 sched_init (dump_file); 299 300 current_sched_info = &ebb_sched_info; 301 302 allocate_reg_life_data (); 303 compute_bb_for_insn (); 304 305 /* Schedule every region in the subroutine. */ 306 FOR_EACH_BB (bb) 307 { 308 rtx head = bb->head; 309 rtx tail; 310 311 for (;;) 312 { 313 edge e; 314 tail = bb->end; 315 if (bb->next_bb == EXIT_BLOCK_PTR 316 || GET_CODE (bb->next_bb->head) == CODE_LABEL) 317 break; 318 for (e = bb->succ; e; e = e->succ_next) 319 if ((e->flags & EDGE_FALLTHRU) != 0) 320 break; 321 if (! e) 322 break; 323 if (GET_CODE (tail) == JUMP_INSN) 324 { 325 rtx x = find_reg_note (tail, REG_BR_PROB, 0); 326 if (x) 327 { 328 int pred_val = INTVAL (XEXP (x, 0)); 329 if (pred_val > REG_BR_PROB_BASE / 2) 330 break; 331 } 332 } 333 334 bb = bb->next_bb; 335 } 336 337 /* Blah. We should fix the rest of the code not to get confused by 338 a note or two. */ 339 while (head != tail) 340 { 341 if (GET_CODE (head) == NOTE) 342 head = NEXT_INSN (head); 343 else if (GET_CODE (tail) == NOTE) 344 tail = PREV_INSN (tail); 345 else if (GET_CODE (head) == CODE_LABEL) 346 head = NEXT_INSN (head); 347 else 348 break; 349 } 350 351 schedule_ebb (head, tail); 352 } 353 354 /* It doesn't make much sense to try and update life information here - we 355 probably messed up even the flow graph. */ 356 357 /* Reposition the prologue and epilogue notes in case we moved the 358 prologue/epilogue insns. */ 359 if (reload_completed) 360 reposition_prologue_and_epilogue_notes (get_insns ()); 361 362 if (write_symbols != NO_DEBUG) 363 rm_redundant_line_notes (); 364 365 sched_finish (); 366} 367