1/* Instruction scheduling pass. 2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004 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, 51 Franklin Street, Fifth Floor, Boston, MA 2202110-1301, USA. */ 23 24#include "config.h" 25#include "system.h" 26#include "coretypes.h" 27#include "tm.h" 28#include "toplev.h" 29#include "rtl.h" 30#include "tm_p.h" 31#include "hard-reg-set.h" 32#include "regs.h" 33#include "function.h" 34#include "flags.h" 35#include "insn-config.h" 36#include "insn-attr.h" 37#include "except.h" 38#include "toplev.h" 39#include "recog.h" 40#include "cfglayout.h" 41#include "params.h" 42#include "sched-int.h" 43#include "target.h" 44 45/* The number of insns to be scheduled in total. */ 46static int target_n_insns; 47/* The number of insns scheduled so far. */ 48static int sched_n_insns; 49 50/* Implementations of the sched_info functions for region scheduling. */ 51static void init_ready_list (struct ready_list *); 52static int can_schedule_ready_p (rtx); 53static int new_ready (rtx); 54static int schedule_more_p (void); 55static const char *ebb_print_insn (rtx, int); 56static int rank (rtx, rtx); 57static int contributes_to_priority (rtx, rtx); 58static void compute_jump_reg_dependencies (rtx, regset, regset, regset); 59static basic_block earliest_block_with_similiar_load (basic_block, rtx); 60static void add_deps_for_risky_insns (rtx, rtx); 61static basic_block schedule_ebb (rtx, rtx); 62static basic_block fix_basic_block_boundaries (basic_block, basic_block, rtx, 63 rtx); 64static void add_missing_bbs (rtx, basic_block, basic_block); 65 66/* Return nonzero if there are more insns that should be scheduled. */ 67 68static int 69schedule_more_p (void) 70{ 71 return sched_n_insns < target_n_insns; 72} 73 74/* Add all insns that are initially ready to the ready list READY. Called 75 once before scheduling a set of insns. */ 76 77static void 78init_ready_list (struct ready_list *ready) 79{ 80 rtx prev_head = current_sched_info->prev_head; 81 rtx next_tail = current_sched_info->next_tail; 82 rtx insn; 83 84 target_n_insns = 0; 85 sched_n_insns = 0; 86 87#if 0 88 /* Print debugging information. */ 89 if (sched_verbose >= 5) 90 debug_dependencies (); 91#endif 92 93 /* Initialize ready list with all 'ready' insns in target block. 94 Count number of insns in the target block being scheduled. */ 95 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn)) 96 { 97 if (INSN_DEP_COUNT (insn) == 0) 98 ready_add (ready, 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 106static int 107can_schedule_ready_p (rtx insn ATTRIBUTE_UNUSED) 108{ 109 sched_n_insns++; 110 return 1; 111} 112 113/* Called after INSN has all its dependencies resolved. Return nonzero 114 if it should be moved to the ready list or the queue, or zero if we 115 should silently discard it. */ 116static int 117new_ready (rtx next ATTRIBUTE_UNUSED) 118{ 119 return 1; 120} 121 122/* Return a string that contains the insn uid and optionally anything else 123 necessary to identify this insn in an output. It's valid to use a 124 static buffer for this. The ALIGNED parameter should cause the string 125 to be formatted so that multiple output lines will line up nicely. */ 126 127static const char * 128ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED) 129{ 130 static char tmp[80]; 131 132 sprintf (tmp, "%4d", INSN_UID (insn)); 133 return tmp; 134} 135 136/* Compare priority of two insns. Return a positive number if the second 137 insn is to be preferred for scheduling, and a negative one if the first 138 is to be preferred. Zero if they are equally good. */ 139 140static int 141rank (rtx insn1, rtx insn2) 142{ 143 basic_block bb1 = BLOCK_FOR_INSN (insn1); 144 basic_block bb2 = BLOCK_FOR_INSN (insn2); 145 146 if (bb1->count > bb2->count 147 || bb1->frequency > bb2->frequency) 148 return -1; 149 if (bb1->count < bb2->count 150 || bb1->frequency < bb2->frequency) 151 return 1; 152 return 0; 153} 154 155/* NEXT is an instruction that depends on INSN (a backward dependence); 156 return nonzero if we should include this dependence in priority 157 calculations. */ 158 159static int 160contributes_to_priority (rtx next ATTRIBUTE_UNUSED, 161 rtx insn ATTRIBUTE_UNUSED) 162{ 163 return 1; 164} 165 166 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are 167 conditionally set before INSN. Store the set of registers that 168 must be considered as used by this jump in USED and that of 169 registers that must be considered as set in SET. */ 170 171static void 172compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used, 173 regset set) 174{ 175 basic_block b = BLOCK_FOR_INSN (insn); 176 edge e; 177 edge_iterator ei; 178 179 FOR_EACH_EDGE (e, ei, b->succs) 180 if (e->flags & EDGE_FALLTHRU) 181 /* The jump may be a by-product of a branch that has been merged 182 in the main codepath after being conditionalized. Therefore 183 it may guard the fallthrough block from using a value that has 184 conditionally overwritten that of the main codepath. So we 185 consider that it restores the value of the main codepath. */ 186 bitmap_and (set, e->dest->il.rtl->global_live_at_start, cond_set); 187 else 188 bitmap_ior_into (used, e->dest->il.rtl->global_live_at_start); 189} 190 191/* Used in schedule_insns to initialize current_sched_info for scheduling 192 regions (or single basic blocks). */ 193 194static struct sched_info ebb_sched_info = 195{ 196 init_ready_list, 197 can_schedule_ready_p, 198 schedule_more_p, 199 new_ready, 200 rank, 201 ebb_print_insn, 202 contributes_to_priority, 203 compute_jump_reg_dependencies, 204 205 NULL, NULL, 206 NULL, NULL, 207 0, 1, 0 208}; 209 210/* It is possible that ebb scheduling eliminated some blocks. 211 Place blocks from FIRST to LAST before BEFORE. */ 212 213static void 214add_missing_bbs (rtx before, basic_block first, basic_block last) 215{ 216 for (; last != first->prev_bb; last = last->prev_bb) 217 { 218 before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before); 219 NOTE_BASIC_BLOCK (before) = last; 220 BB_HEAD (last) = before; 221 BB_END (last) = before; 222 update_bb_for_insn (last); 223 } 224} 225 226/* Fixup the CFG after EBB scheduling. Re-recognize the basic 227 block boundaries in between HEAD and TAIL and update basic block 228 structures between BB and LAST. */ 229 230static basic_block 231fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head, 232 rtx tail) 233{ 234 rtx insn = head; 235 rtx last_inside = BB_HEAD (bb); 236 rtx aftertail = NEXT_INSN (tail); 237 238 head = BB_HEAD (bb); 239 240 for (; insn != aftertail; insn = NEXT_INSN (insn)) 241 { 242 gcc_assert (!LABEL_P (insn)); 243 /* Create new basic blocks just before first insn. */ 244 if (inside_basic_block_p (insn)) 245 { 246 if (!last_inside) 247 { 248 rtx note; 249 250 /* Re-emit the basic block note for newly found BB header. */ 251 if (LABEL_P (insn)) 252 { 253 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn); 254 head = insn; 255 last_inside = note; 256 } 257 else 258 { 259 note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn); 260 head = note; 261 last_inside = insn; 262 } 263 } 264 else 265 last_inside = insn; 266 } 267 /* Control flow instruction terminate basic block. It is possible 268 that we've eliminated some basic blocks (made them empty). 269 Find the proper basic block using BLOCK_FOR_INSN and arrange things in 270 a sensible way by inserting empty basic blocks as needed. */ 271 if (control_flow_insn_p (insn) || (insn == tail && last_inside)) 272 { 273 basic_block curr_bb = BLOCK_FOR_INSN (insn); 274 rtx note; 275 276 if (!control_flow_insn_p (insn)) 277 curr_bb = last; 278 if (bb == last->next_bb) 279 { 280 edge f; 281 rtx h; 282 edge_iterator ei; 283 284 /* An obscure special case, where we do have partially dead 285 instruction scheduled after last control flow instruction. 286 In this case we can create new basic block. It is 287 always exactly one basic block last in the sequence. Handle 288 it by splitting the edge and repositioning the block. 289 This is somewhat hackish, but at least avoid cut&paste 290 291 A safer solution can be to bring the code into sequence, 292 do the split and re-emit it back in case this will ever 293 trigger problem. */ 294 295 FOR_EACH_EDGE (f, ei, bb->prev_bb->succs) 296 if (f->flags & EDGE_FALLTHRU) 297 break; 298 299 if (f) 300 { 301 last = curr_bb = split_edge (f); 302 h = BB_HEAD (curr_bb); 303 BB_HEAD (curr_bb) = head; 304 BB_END (curr_bb) = insn; 305 /* Edge splitting created misplaced BASIC_BLOCK note, kill 306 it. */ 307 delete_insn (h); 308 } 309 /* It may happen that code got moved past unconditional jump in 310 case the code is completely dead. Kill it. */ 311 else 312 { 313 rtx next = next_nonnote_insn (insn); 314 delete_insn_chain (head, insn); 315 /* We keep some notes in the way that may split barrier from the 316 jump. */ 317 if (BARRIER_P (next)) 318 { 319 emit_barrier_after (prev_nonnote_insn (head)); 320 delete_insn (next); 321 } 322 insn = NULL; 323 } 324 } 325 else 326 { 327 BB_HEAD (curr_bb) = head; 328 BB_END (curr_bb) = insn; 329 add_missing_bbs (BB_HEAD (curr_bb), bb, curr_bb->prev_bb); 330 } 331 note = LABEL_P (head) ? NEXT_INSN (head) : head; 332 NOTE_BASIC_BLOCK (note) = curr_bb; 333 update_bb_for_insn (curr_bb); 334 bb = curr_bb->next_bb; 335 last_inside = NULL; 336 if (!insn) 337 break; 338 } 339 } 340 add_missing_bbs (BB_HEAD (last->next_bb), bb, last); 341 return bb->prev_bb; 342} 343 344/* Returns the earliest block in EBB currently being processed where a 345 "similar load" 'insn2' is found, and hence LOAD_INSN can move 346 speculatively into the found block. All the following must hold: 347 348 (1) both loads have 1 base register (PFREE_CANDIDATEs). 349 (2) load_insn and load2 have a def-use dependence upon 350 the same insn 'insn1'. 351 352 From all these we can conclude that the two loads access memory 353 addresses that differ at most by a constant, and hence if moving 354 load_insn would cause an exception, it would have been caused by 355 load2 anyhow. 356 357 The function uses list (given by LAST_BLOCK) of already processed 358 blocks in EBB. The list is formed in `add_deps_for_risky_insns'. */ 359 360static basic_block 361earliest_block_with_similiar_load (basic_block last_block, rtx load_insn) 362{ 363 rtx back_link; 364 basic_block bb, earliest_block = NULL; 365 366 for (back_link = LOG_LINKS (load_insn); 367 back_link; 368 back_link = XEXP (back_link, 1)) 369 { 370 rtx insn1 = XEXP (back_link, 0); 371 372 if (GET_MODE (back_link) == VOIDmode) 373 { 374 /* Found a DEF-USE dependence (insn1, load_insn). */ 375 rtx fore_link; 376 377 for (fore_link = INSN_DEPEND (insn1); 378 fore_link; 379 fore_link = XEXP (fore_link, 1)) 380 { 381 rtx insn2 = XEXP (fore_link, 0); 382 basic_block insn2_block = BLOCK_FOR_INSN (insn2); 383 384 if (GET_MODE (fore_link) == VOIDmode) 385 { 386 if (earliest_block != NULL 387 && earliest_block->index < insn2_block->index) 388 continue; 389 390 /* Found a DEF-USE dependence (insn1, insn2). */ 391 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE) 392 /* insn2 not guaranteed to be a 1 base reg load. */ 393 continue; 394 395 for (bb = last_block; bb; bb = bb->aux) 396 if (insn2_block == bb) 397 break; 398 399 if (!bb) 400 /* insn2 is the similar load. */ 401 earliest_block = insn2_block; 402 } 403 } 404 } 405 } 406 407 return earliest_block; 408} 409 410/* The following function adds dependencies between jumps and risky 411 insns in given ebb. */ 412 413static void 414add_deps_for_risky_insns (rtx head, rtx tail) 415{ 416 rtx insn, prev; 417 int class; 418 rtx last_jump = NULL_RTX; 419 rtx next_tail = NEXT_INSN (tail); 420 basic_block last_block = NULL, bb; 421 422 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 423 if (JUMP_P (insn)) 424 { 425 bb = BLOCK_FOR_INSN (insn); 426 bb->aux = last_block; 427 last_block = bb; 428 last_jump = insn; 429 } 430 else if (INSN_P (insn) && last_jump != NULL_RTX) 431 { 432 class = haifa_classify_insn (insn); 433 prev = last_jump; 434 switch (class) 435 { 436 case PFREE_CANDIDATE: 437 if (flag_schedule_speculative_load) 438 { 439 bb = earliest_block_with_similiar_load (last_block, insn); 440 if (bb) 441 { 442 bb = bb->aux; 443 if (!bb) 444 break; 445 prev = BB_END (bb); 446 } 447 } 448 /* Fall through. */ 449 case TRAP_RISKY: 450 case IRISKY: 451 case PRISKY_CANDIDATE: 452 /* ??? We could implement better checking PRISKY_CANDIDATEs 453 analogous to sched-rgn.c. */ 454 /* We can not change the mode of the backward 455 dependency because REG_DEP_ANTI has the lowest 456 rank. */ 457 if (! sched_insns_conditions_mutex_p (insn, prev) 458 && add_dependence (insn, prev, REG_DEP_ANTI)) 459 add_forward_dependence (prev, insn, REG_DEP_ANTI); 460 break; 461 462 default: 463 break; 464 } 465 } 466 /* Maintain the invariant that bb->aux is clear after use. */ 467 while (last_block) 468 { 469 bb = last_block->aux; 470 last_block->aux = NULL; 471 last_block = bb; 472 } 473} 474 475/* Schedule a single extended basic block, defined by the boundaries HEAD 476 and TAIL. */ 477 478static basic_block 479schedule_ebb (rtx head, rtx tail) 480{ 481 int n_insns; 482 basic_block b; 483 struct deps tmp_deps; 484 basic_block first_bb = BLOCK_FOR_INSN (head); 485 basic_block last_bb = BLOCK_FOR_INSN (tail); 486 487 if (no_real_insns_p (head, tail)) 488 return BLOCK_FOR_INSN (tail); 489 490 init_deps_global (); 491 492 /* Compute LOG_LINKS. */ 493 init_deps (&tmp_deps); 494 sched_analyze (&tmp_deps, head, tail); 495 free_deps (&tmp_deps); 496 497 /* Compute INSN_DEPEND. */ 498 compute_forward_dependences (head, tail); 499 500 add_deps_for_risky_insns (head, tail); 501 502 if (targetm.sched.dependencies_evaluation_hook) 503 targetm.sched.dependencies_evaluation_hook (head, tail); 504 505 /* Set priorities. */ 506 n_insns = set_priorities (head, tail); 507 508 current_sched_info->prev_head = PREV_INSN (head); 509 current_sched_info->next_tail = NEXT_INSN (tail); 510 511 if (write_symbols != NO_DEBUG) 512 { 513 save_line_notes (first_bb->index, head, tail); 514 rm_line_notes (head, tail); 515 } 516 517 /* rm_other_notes only removes notes which are _inside_ the 518 block---that is, it won't remove notes before the first real insn 519 or after the last real insn of the block. So if the first insn 520 has a REG_SAVE_NOTE which would otherwise be emitted before the 521 insn, it is redundant with the note before the start of the 522 block, and so we have to take it out. */ 523 if (INSN_P (head)) 524 { 525 rtx note; 526 527 for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 528 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 529 remove_note (head, note); 530 } 531 532 /* Remove remaining note insns from the block, save them in 533 note_list. These notes are restored at the end of 534 schedule_block (). */ 535 rm_other_notes (head, tail); 536 537 current_sched_info->queue_must_finish_empty = 1; 538 539 schedule_block (-1, n_insns); 540 541 /* Sanity check: verify that all region insns were scheduled. */ 542 gcc_assert (sched_n_insns == n_insns); 543 head = current_sched_info->head; 544 tail = current_sched_info->tail; 545 546 if (write_symbols != NO_DEBUG) 547 restore_line_notes (head, tail); 548 b = fix_basic_block_boundaries (first_bb, last_bb, head, tail); 549 550 finish_deps_global (); 551 return b; 552} 553 554/* The one entry point in this file. DUMP_FILE is the dump file for 555 this pass. */ 556 557void 558schedule_ebbs (FILE *dump_file) 559{ 560 basic_block bb; 561 int probability_cutoff; 562 563 if (profile_info && flag_branch_probabilities) 564 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK); 565 else 566 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY); 567 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff; 568 569 /* Taking care of this degenerate case makes the rest of 570 this code simpler. */ 571 if (n_basic_blocks == 0) 572 return; 573 574 sched_init (dump_file); 575 576 current_sched_info = &ebb_sched_info; 577 578 compute_bb_for_insn (); 579 580 /* Schedule every region in the subroutine. */ 581 FOR_EACH_BB (bb) 582 { 583 rtx head = BB_HEAD (bb); 584 rtx tail; 585 586 for (;;) 587 { 588 edge e; 589 edge_iterator ei; 590 tail = BB_END (bb); 591 if (bb->next_bb == EXIT_BLOCK_PTR 592 || LABEL_P (BB_HEAD (bb->next_bb))) 593 break; 594 FOR_EACH_EDGE (e, ei, bb->succs) 595 if ((e->flags & EDGE_FALLTHRU) != 0) 596 break; 597 if (! e) 598 break; 599 if (e->probability <= probability_cutoff) 600 break; 601 bb = bb->next_bb; 602 } 603 604 /* Blah. We should fix the rest of the code not to get confused by 605 a note or two. */ 606 while (head != tail) 607 { 608 if (NOTE_P (head)) 609 head = NEXT_INSN (head); 610 else if (NOTE_P (tail)) 611 tail = PREV_INSN (tail); 612 else if (LABEL_P (head)) 613 head = NEXT_INSN (head); 614 else 615 break; 616 } 617 618 bb = schedule_ebb (head, tail); 619 } 620 621 /* Updating life info can be done by local propagation over the modified 622 superblocks. */ 623 624 /* Reposition the prologue and epilogue notes in case we moved the 625 prologue/epilogue insns. */ 626 if (reload_completed) 627 reposition_prologue_and_epilogue_notes (get_insns ()); 628 629 if (write_symbols != NO_DEBUG) 630 rm_redundant_line_notes (); 631 632 sched_finish (); 633} 634