sched-ebb.c revision 132718
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, 59 Temple Place - Suite 330, Boston, MA 2202111-1307, 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 "basic-block.h" 33#include "regs.h" 34#include "function.h" 35#include "flags.h" 36#include "insn-config.h" 37#include "insn-attr.h" 38#include "except.h" 39#include "toplev.h" 40#include "recog.h" 41#include "cfglayout.h" 42#include "params.h" 43#include "sched-int.h" 44#include "target.h" 45 46/* The number of insns to be scheduled in total. */ 47static int target_n_insns; 48/* The number of insns scheduled so far. */ 49static int sched_n_insns; 50 51/* Implementations of the sched_info functions for region scheduling. */ 52static void init_ready_list (struct ready_list *); 53static int can_schedule_ready_p (rtx); 54static int new_ready (rtx); 55static int schedule_more_p (void); 56static const char *ebb_print_insn (rtx, int); 57static int rank (rtx, rtx); 58static int contributes_to_priority (rtx, rtx); 59static void compute_jump_reg_dependencies (rtx, regset, regset, regset); 60static basic_block earliest_block_with_similiar_load (basic_block, rtx); 61static void add_deps_for_risky_insns (rtx, rtx); 62static basic_block schedule_ebb (rtx, rtx); 63static basic_block fix_basic_block_boundaries (basic_block, basic_block, rtx, 64 rtx); 65static void add_missing_bbs (rtx, basic_block, basic_block); 66 67/* Return nonzero if there are more insns that should be scheduled. */ 68 69static int 70schedule_more_p (void) 71{ 72 return sched_n_insns < target_n_insns; 73} 74 75/* Add all insns that are initially ready to the ready list READY. Called 76 once before scheduling a set of insns. */ 77 78static void 79init_ready_list (struct ready_list *ready) 80{ 81 rtx prev_head = current_sched_info->prev_head; 82 rtx next_tail = current_sched_info->next_tail; 83 rtx insn; 84 85 target_n_insns = 0; 86 sched_n_insns = 0; 87 88#if 0 89 /* Print debugging information. */ 90 if (sched_verbose >= 5) 91 debug_dependencies (); 92#endif 93 94 /* Initialize ready list with all 'ready' insns in target block. 95 Count number of insns in the target block being scheduled. */ 96 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn)) 97 { 98 if (INSN_DEP_COUNT (insn) == 0) 99 ready_add (ready, 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 (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. */ 117static int 118new_ready (rtx next ATTRIBUTE_UNUSED) 119{ 120 return 1; 121} 122 123/* Return a string that contains the insn uid and optionally anything else 124 necessary to identify this insn in an output. It's valid to use a 125 static buffer for this. The ALIGNED parameter should cause the string 126 to be formatted so that multiple output lines will line up nicely. */ 127 128static const char * 129ebb_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED) 130{ 131 static char tmp[80]; 132 133 sprintf (tmp, "%4d", INSN_UID (insn)); 134 return tmp; 135} 136 137/* Compare priority of two insns. Return a positive number if the second 138 insn is to be preferred for scheduling, and a negative one if the first 139 is to be preferred. Zero if they are equally good. */ 140 141static int 142rank (rtx insn1, rtx insn2) 143{ 144 basic_block bb1 = BLOCK_FOR_INSN (insn1); 145 basic_block bb2 = BLOCK_FOR_INSN (insn2); 146 147 if (bb1->count > bb2->count 148 || bb1->frequency > bb2->frequency) 149 return -1; 150 if (bb1->count < bb2->count 151 || bb1->frequency < bb2->frequency) 152 return 1; 153 return 0; 154} 155 156/* NEXT is an instruction that depends on INSN (a backward dependence); 157 return nonzero if we should include this dependence in priority 158 calculations. */ 159 160static int 161contributes_to_priority (rtx next ATTRIBUTE_UNUSED, 162 rtx insn ATTRIBUTE_UNUSED) 163{ 164 return 1; 165} 166 167 /* INSN is a JUMP_INSN, COND_SET is the set of registers that are 168 conditionally set before INSN. Store the set of registers that 169 must be considered as used by this jump in USED and that of 170 registers that must be considered as set in SET. */ 171 172static void 173compute_jump_reg_dependencies (rtx insn, regset cond_set, regset used, 174 regset set) 175{ 176 basic_block b = BLOCK_FOR_INSN (insn); 177 edge e; 178 for (e = b->succ; e; e = e->succ_next) 179 if (e->flags & EDGE_FALLTHRU) 180 /* The jump may be a by-product of a branch that has been merged 181 in the main codepath after being conditionalized. Therefore 182 it may guard the fallthrough block from using a value that has 183 conditionally overwritten that of the main codepath. So we 184 consider that it restores the value of the main codepath. */ 185 bitmap_operation (set, e->dest->global_live_at_start, cond_set, 186 BITMAP_AND); 187 else 188 bitmap_operation (used, used, e->dest->global_live_at_start, 189 BITMAP_IOR); 190} 191 192/* Used in schedule_insns to initialize current_sched_info for scheduling 193 regions (or single basic blocks). */ 194 195static struct sched_info ebb_sched_info = 196{ 197 init_ready_list, 198 can_schedule_ready_p, 199 schedule_more_p, 200 new_ready, 201 rank, 202 ebb_print_insn, 203 contributes_to_priority, 204 compute_jump_reg_dependencies, 205 206 NULL, NULL, 207 NULL, NULL, 208 0, 1, 0 209}; 210 211/* It is possible that ebb scheduling eliminated some blocks. 212 Place blocks from FIRST to LAST before BEFORE. */ 213 214static void 215add_missing_bbs (rtx before, basic_block first, basic_block last) 216{ 217 for (; last != first->prev_bb; last = last->prev_bb) 218 { 219 before = emit_note_before (NOTE_INSN_BASIC_BLOCK, before); 220 NOTE_BASIC_BLOCK (before) = last; 221 BB_HEAD (last) = before; 222 BB_END (last) = before; 223 update_bb_for_insn (last); 224 } 225} 226 227/* Fixup the CFG after EBB scheduling. Re-recognize the basic 228 block boundaries in between HEAD and TAIL and update basic block 229 structures between BB and LAST. */ 230 231static basic_block 232fix_basic_block_boundaries (basic_block bb, basic_block last, rtx head, 233 rtx tail) 234{ 235 rtx insn = head; 236 rtx last_inside = BB_HEAD (bb); 237 rtx aftertail = NEXT_INSN (tail); 238 239 head = BB_HEAD (bb); 240 241 for (; insn != aftertail; insn = NEXT_INSN (insn)) 242 { 243 if (GET_CODE (insn) == CODE_LABEL) 244 abort (); 245 /* Create new basic blocks just before first insn. */ 246 if (inside_basic_block_p (insn)) 247 { 248 if (!last_inside) 249 { 250 rtx note; 251 252 /* Re-emit the basic block note for newly found BB header. */ 253 if (GET_CODE (insn) == CODE_LABEL) 254 { 255 note = emit_note_after (NOTE_INSN_BASIC_BLOCK, insn); 256 head = insn; 257 last_inside = note; 258 } 259 else 260 { 261 note = emit_note_before (NOTE_INSN_BASIC_BLOCK, insn); 262 head = note; 263 last_inside = insn; 264 } 265 } 266 else 267 last_inside = insn; 268 } 269 /* Control flow instruction terminate basic block. It is possible 270 that we've eliminated some basic blocks (made them empty). 271 Find the proper basic block using BLOCK_FOR_INSN and arrange things in 272 a sensible way by inserting empty basic blocks as needed. */ 273 if (control_flow_insn_p (insn) || (insn == tail && last_inside)) 274 { 275 basic_block curr_bb = BLOCK_FOR_INSN (insn); 276 rtx note; 277 278 if (!control_flow_insn_p (insn)) 279 curr_bb = last; 280 if (bb == last->next_bb) 281 { 282 edge f; 283 rtx h; 284 285 /* An obscure special case, where we do have partially dead 286 instruction scheduled after last control flow instruction. 287 In this case we can create new basic block. It is 288 always exactly one basic block last in the sequence. Handle 289 it by splitting the edge and repositioning the block. 290 This is somewhat hackish, but at least avoid cut&paste 291 292 A safer solution can be to bring the code into sequence, 293 do the split and re-emit it back in case this will ever 294 trigger problem. */ 295 f = bb->prev_bb->succ; 296 while (f && !(f->flags & EDGE_FALLTHRU)) 297 f = f->succ_next; 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 (GET_CODE (next) == BARRIER) 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 = GET_CODE (head) == CODE_LABEL ? 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 (GET_CODE (insn) == JUMP_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 (add_dependence (insn, prev, REG_DEP_ANTI)) 458 add_forward_dependence (prev, insn, REG_DEP_ANTI); 459 break; 460 461 default: 462 break; 463 } 464 } 465 /* Maintain the invariant that bb->aux is clear after use. */ 466 while (last_block) 467 { 468 bb = last_block->aux; 469 last_block->aux = NULL; 470 last_block = bb; 471 } 472} 473 474/* Schedule a single extended basic block, defined by the boundaries HEAD 475 and TAIL. */ 476 477static basic_block 478schedule_ebb (rtx head, rtx tail) 479{ 480 int n_insns; 481 basic_block b; 482 struct deps tmp_deps; 483 basic_block first_bb = BLOCK_FOR_INSN (head); 484 basic_block last_bb = BLOCK_FOR_INSN (tail); 485 486 if (no_real_insns_p (head, tail)) 487 return BLOCK_FOR_INSN (tail); 488 489 init_deps_global (); 490 491 /* Compute LOG_LINKS. */ 492 init_deps (&tmp_deps); 493 sched_analyze (&tmp_deps, head, tail); 494 free_deps (&tmp_deps); 495 496 /* Compute INSN_DEPEND. */ 497 compute_forward_dependences (head, tail); 498 499 add_deps_for_risky_insns (head, tail); 500 501 if (targetm.sched.dependencies_evaluation_hook) 502 targetm.sched.dependencies_evaluation_hook (head, tail); 503 504 /* Set priorities. */ 505 n_insns = set_priorities (head, tail); 506 507 current_sched_info->prev_head = PREV_INSN (head); 508 current_sched_info->next_tail = NEXT_INSN (tail); 509 510 if (write_symbols != NO_DEBUG) 511 { 512 save_line_notes (first_bb->index, head, tail); 513 rm_line_notes (head, tail); 514 } 515 516 /* rm_other_notes only removes notes which are _inside_ the 517 block---that is, it won't remove notes before the first real insn 518 or after the last real insn of the block. So if the first insn 519 has a REG_SAVE_NOTE which would otherwise be emitted before the 520 insn, it is redundant with the note before the start of the 521 block, and so we have to take it out. */ 522 if (INSN_P (head)) 523 { 524 rtx note; 525 526 for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 527 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 528 { 529 remove_note (head, note); 530 note = XEXP (note, 1); 531 remove_note (head, note); 532 } 533 } 534 535 /* Remove remaining note insns from the block, save them in 536 note_list. These notes are restored at the end of 537 schedule_block (). */ 538 rm_other_notes (head, tail); 539 540 current_sched_info->queue_must_finish_empty = 1; 541 542 schedule_block (-1, n_insns); 543 544 /* Sanity check: verify that all region insns were scheduled. */ 545 if (sched_n_insns != n_insns) 546 abort (); 547 head = current_sched_info->head; 548 tail = current_sched_info->tail; 549 550 if (write_symbols != NO_DEBUG) 551 restore_line_notes (head, tail); 552 b = fix_basic_block_boundaries (first_bb, last_bb, head, tail); 553 554 finish_deps_global (); 555 return b; 556} 557 558/* The one entry point in this file. DUMP_FILE is the dump file for 559 this pass. */ 560 561void 562schedule_ebbs (FILE *dump_file) 563{ 564 basic_block bb; 565 int probability_cutoff; 566 567 if (profile_info && flag_branch_probabilities) 568 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY_FEEDBACK); 569 else 570 probability_cutoff = PARAM_VALUE (TRACER_MIN_BRANCH_PROBABILITY); 571 probability_cutoff = REG_BR_PROB_BASE / 100 * probability_cutoff; 572 573 /* Taking care of this degenerate case makes the rest of 574 this code simpler. */ 575 if (n_basic_blocks == 0) 576 return; 577 578 sched_init (dump_file); 579 580 current_sched_info = &ebb_sched_info; 581 582 allocate_reg_life_data (); 583 compute_bb_for_insn (); 584 585 /* Schedule every region in the subroutine. */ 586 FOR_EACH_BB (bb) 587 { 588 rtx head = BB_HEAD (bb); 589 rtx tail; 590 591 for (;;) 592 { 593 edge e; 594 tail = BB_END (bb); 595 if (bb->next_bb == EXIT_BLOCK_PTR 596 || GET_CODE (BB_HEAD (bb->next_bb)) == CODE_LABEL) 597 break; 598 for (e = bb->succ; e; e = e->succ_next) 599 if ((e->flags & EDGE_FALLTHRU) != 0) 600 break; 601 if (! e) 602 break; 603 if (e->probability <= probability_cutoff) 604 break; 605 bb = bb->next_bb; 606 } 607 608 /* Blah. We should fix the rest of the code not to get confused by 609 a note or two. */ 610 while (head != tail) 611 { 612 if (GET_CODE (head) == NOTE) 613 head = NEXT_INSN (head); 614 else if (GET_CODE (tail) == NOTE) 615 tail = PREV_INSN (tail); 616 else if (GET_CODE (head) == CODE_LABEL) 617 head = NEXT_INSN (head); 618 else 619 break; 620 } 621 622 bb = schedule_ebb (head, tail); 623 } 624 625 /* Updating life info can be done by local propagation over the modified 626 superblocks. */ 627 628 /* Reposition the prologue and epilogue notes in case we moved the 629 prologue/epilogue insns. */ 630 if (reload_completed) 631 reposition_prologue_and_epilogue_notes (get_insns ()); 632 633 if (write_symbols != NO_DEBUG) 634 rm_redundant_line_notes (); 635 636 sched_finish (); 637} 638