1/* Instruction scheduling pass. 2 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 3 1999, 2000, 2001, 2002, 2003, 2004, 2005 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/* This pass implements list scheduling within basic blocks. It is 25 run twice: (1) after flow analysis, but before register allocation, 26 and (2) after register allocation. 27 28 The first run performs interblock scheduling, moving insns between 29 different blocks in the same "region", and the second runs only 30 basic block scheduling. 31 32 Interblock motions performed are useful motions and speculative 33 motions, including speculative loads. Motions requiring code 34 duplication are not supported. The identification of motion type 35 and the check for validity of speculative motions requires 36 construction and analysis of the function's control flow graph. 37 38 The main entry point for this pass is schedule_insns(), called for 39 each function. The work of the scheduler is organized in three 40 levels: (1) function level: insns are subject to splitting, 41 control-flow-graph is constructed, regions are computed (after 42 reload, each region is of one block), (2) region level: control 43 flow graph attributes required for interblock scheduling are 44 computed (dominators, reachability, etc.), data dependences and 45 priorities are computed, and (3) block level: insns in the block 46 are actually scheduled. */ 47 48#include "config.h" 49#include "system.h" 50#include "coretypes.h" 51#include "tm.h" 52#include "toplev.h" 53#include "rtl.h" 54#include "tm_p.h" 55#include "hard-reg-set.h" 56#include "regs.h" 57#include "function.h" 58#include "flags.h" 59#include "insn-config.h" 60#include "insn-attr.h" 61#include "except.h" 62#include "toplev.h" 63#include "recog.h" 64#include "cfglayout.h" 65#include "params.h" 66#include "sched-int.h" 67#include "target.h" 68#include "timevar.h" 69#include "tree-pass.h" 70 71/* Define when we want to do count REG_DEAD notes before and after scheduling 72 for sanity checking. We can't do that when conditional execution is used, 73 as REG_DEAD exist only for unconditional deaths. */ 74 75#if !defined (HAVE_conditional_execution) && defined (ENABLE_CHECKING) 76#define CHECK_DEAD_NOTES 1 77#else 78#define CHECK_DEAD_NOTES 0 79#endif 80 81 82#ifdef INSN_SCHEDULING 83/* Some accessor macros for h_i_d members only used within this file. */ 84#define INSN_REF_COUNT(INSN) (h_i_d[INSN_UID (INSN)].ref_count) 85#define FED_BY_SPEC_LOAD(insn) (h_i_d[INSN_UID (insn)].fed_by_spec_load) 86#define IS_LOAD_INSN(insn) (h_i_d[INSN_UID (insn)].is_load_insn) 87 88/* nr_inter/spec counts interblock/speculative motion for the function. */ 89static int nr_inter, nr_spec; 90 91static int is_cfg_nonregular (void); 92static bool sched_is_disabled_for_current_region_p (void); 93 94/* A region is the main entity for interblock scheduling: insns 95 are allowed to move between blocks in the same region, along 96 control flow graph edges, in the 'up' direction. */ 97typedef struct 98{ 99 int rgn_nr_blocks; /* Number of blocks in region. */ 100 int rgn_blocks; /* cblocks in the region (actually index in rgn_bb_table). */ 101} 102region; 103 104/* Number of regions in the procedure. */ 105static int nr_regions; 106 107/* Table of region descriptions. */ 108static region *rgn_table; 109 110/* Array of lists of regions' blocks. */ 111static int *rgn_bb_table; 112 113/* Topological order of blocks in the region (if b2 is reachable from 114 b1, block_to_bb[b2] > block_to_bb[b1]). Note: A basic block is 115 always referred to by either block or b, while its topological 116 order name (in the region) is referred to by bb. */ 117static int *block_to_bb; 118 119/* The number of the region containing a block. */ 120static int *containing_rgn; 121 122#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks) 123#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks) 124#define BLOCK_TO_BB(block) (block_to_bb[block]) 125#define CONTAINING_RGN(block) (containing_rgn[block]) 126 127void debug_regions (void); 128static void find_single_block_region (void); 129static void find_rgns (void); 130static bool too_large (int, int *, int *); 131 132extern void debug_live (int, int); 133 134/* Blocks of the current region being scheduled. */ 135static int current_nr_blocks; 136static int current_blocks; 137 138/* The mapping from bb to block. */ 139#define BB_TO_BLOCK(bb) (rgn_bb_table[current_blocks + (bb)]) 140 141/* Target info declarations. 142 143 The block currently being scheduled is referred to as the "target" block, 144 while other blocks in the region from which insns can be moved to the 145 target are called "source" blocks. The candidate structure holds info 146 about such sources: are they valid? Speculative? Etc. */ 147typedef struct 148{ 149 basic_block *first_member; 150 int nr_members; 151} 152bblst; 153 154typedef struct 155{ 156 char is_valid; 157 char is_speculative; 158 int src_prob; 159 bblst split_bbs; 160 bblst update_bbs; 161} 162candidate; 163 164static candidate *candidate_table; 165 166/* A speculative motion requires checking live information on the path 167 from 'source' to 'target'. The split blocks are those to be checked. 168 After a speculative motion, live information should be modified in 169 the 'update' blocks. 170 171 Lists of split and update blocks for each candidate of the current 172 target are in array bblst_table. */ 173static basic_block *bblst_table; 174static int bblst_size, bblst_last; 175 176#define IS_VALID(src) ( candidate_table[src].is_valid ) 177#define IS_SPECULATIVE(src) ( candidate_table[src].is_speculative ) 178#define SRC_PROB(src) ( candidate_table[src].src_prob ) 179 180/* The bb being currently scheduled. */ 181static int target_bb; 182 183/* List of edges. */ 184typedef struct 185{ 186 edge *first_member; 187 int nr_members; 188} 189edgelst; 190 191static edge *edgelst_table; 192static int edgelst_last; 193 194static void extract_edgelst (sbitmap, edgelst *); 195 196 197/* Target info functions. */ 198static void split_edges (int, int, edgelst *); 199static void compute_trg_info (int); 200void debug_candidate (int); 201void debug_candidates (int); 202 203/* Dominators array: dom[i] contains the sbitmap of dominators of 204 bb i in the region. */ 205static sbitmap *dom; 206 207/* bb 0 is the only region entry. */ 208#define IS_RGN_ENTRY(bb) (!bb) 209 210/* Is bb_src dominated by bb_trg. */ 211#define IS_DOMINATED(bb_src, bb_trg) \ 212( TEST_BIT (dom[bb_src], bb_trg) ) 213 214/* Probability: Prob[i] is a float in [0, 1] which is the probability 215 of bb i relative to the region entry. */ 216static float *prob; 217 218/* The probability of bb_src, relative to bb_trg. Note, that while the 219 'prob[bb]' is a float in [0, 1], this macro returns an integer 220 in [0, 100]. */ 221#define GET_SRC_PROB(bb_src, bb_trg) ((int) (100.0 * (prob[bb_src] / \ 222 prob[bb_trg]))) 223 224/* Bit-set of edges, where bit i stands for edge i. */ 225typedef sbitmap edgeset; 226 227/* Number of edges in the region. */ 228static int rgn_nr_edges; 229 230/* Array of size rgn_nr_edges. */ 231static edge *rgn_edges; 232 233/* Mapping from each edge in the graph to its number in the rgn. */ 234#define EDGE_TO_BIT(edge) ((int)(size_t)(edge)->aux) 235#define SET_EDGE_TO_BIT(edge,nr) ((edge)->aux = (void *)(size_t)(nr)) 236 237/* The split edges of a source bb is different for each target 238 bb. In order to compute this efficiently, the 'potential-split edges' 239 are computed for each bb prior to scheduling a region. This is actually 240 the split edges of each bb relative to the region entry. 241 242 pot_split[bb] is the set of potential split edges of bb. */ 243static edgeset *pot_split; 244 245/* For every bb, a set of its ancestor edges. */ 246static edgeset *ancestor_edges; 247 248static void compute_dom_prob_ps (int); 249 250#define INSN_PROBABILITY(INSN) (SRC_PROB (BLOCK_TO_BB (BLOCK_NUM (INSN)))) 251#define IS_SPECULATIVE_INSN(INSN) (IS_SPECULATIVE (BLOCK_TO_BB (BLOCK_NUM (INSN)))) 252#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN))) 253 254/* Speculative scheduling functions. */ 255static int check_live_1 (int, rtx); 256static void update_live_1 (int, rtx); 257static int check_live (rtx, int); 258static void update_live (rtx, int); 259static void set_spec_fed (rtx); 260static int is_pfree (rtx, int, int); 261static int find_conditional_protection (rtx, int); 262static int is_conditionally_protected (rtx, int, int); 263static int is_prisky (rtx, int, int); 264static int is_exception_free (rtx, int, int); 265 266static bool sets_likely_spilled (rtx); 267static void sets_likely_spilled_1 (rtx, rtx, void *); 268static void add_branch_dependences (rtx, rtx); 269static void compute_block_backward_dependences (int); 270void debug_dependencies (void); 271 272static void init_regions (void); 273static void schedule_region (int); 274static rtx concat_INSN_LIST (rtx, rtx); 275static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *); 276static void propagate_deps (int, struct deps *); 277static void free_pending_lists (void); 278 279/* Functions for construction of the control flow graph. */ 280 281/* Return 1 if control flow graph should not be constructed, 0 otherwise. 282 283 We decide not to build the control flow graph if there is possibly more 284 than one entry to the function, if computed branches exist, if we 285 have nonlocal gotos, or if we have an unreachable loop. */ 286 287static int 288is_cfg_nonregular (void) 289{ 290 basic_block b; 291 rtx insn; 292 293 /* If we have a label that could be the target of a nonlocal goto, then 294 the cfg is not well structured. */ 295 if (nonlocal_goto_handler_labels) 296 return 1; 297 298 /* If we have any forced labels, then the cfg is not well structured. */ 299 if (forced_labels) 300 return 1; 301 302 /* If we have exception handlers, then we consider the cfg not well 303 structured. ?!? We should be able to handle this now that flow.c 304 computes an accurate cfg for EH. */ 305 if (current_function_has_exception_handlers ()) 306 return 1; 307 308 /* If we have non-jumping insns which refer to labels, then we consider 309 the cfg not well structured. */ 310 FOR_EACH_BB (b) 311 FOR_BB_INSNS (b, insn) 312 { 313 /* Check for labels referred by non-jump insns. */ 314 if (NONJUMP_INSN_P (insn) || CALL_P (insn)) 315 { 316 rtx note = find_reg_note (insn, REG_LABEL, NULL_RTX); 317 if (note 318 && ! (JUMP_P (NEXT_INSN (insn)) 319 && find_reg_note (NEXT_INSN (insn), REG_LABEL, 320 XEXP (note, 0)))) 321 return 1; 322 } 323 /* If this function has a computed jump, then we consider the cfg 324 not well structured. */ 325 else if (JUMP_P (insn) && computed_jump_p (insn)) 326 return 1; 327 } 328 329 /* Unreachable loops with more than one basic block are detected 330 during the DFS traversal in find_rgns. 331 332 Unreachable loops with a single block are detected here. This 333 test is redundant with the one in find_rgns, but it's much 334 cheaper to go ahead and catch the trivial case here. */ 335 FOR_EACH_BB (b) 336 { 337 if (EDGE_COUNT (b->preds) == 0 338 || (single_pred_p (b) 339 && single_pred (b) == b)) 340 return 1; 341 } 342 343 /* All the tests passed. Consider the cfg well structured. */ 344 return 0; 345} 346 347/* Extract list of edges from a bitmap containing EDGE_TO_BIT bits. */ 348 349static void 350extract_edgelst (sbitmap set, edgelst *el) 351{ 352 unsigned int i = 0; 353 sbitmap_iterator sbi; 354 355 /* edgelst table space is reused in each call to extract_edgelst. */ 356 edgelst_last = 0; 357 358 el->first_member = &edgelst_table[edgelst_last]; 359 el->nr_members = 0; 360 361 /* Iterate over each word in the bitset. */ 362 EXECUTE_IF_SET_IN_SBITMAP (set, 0, i, sbi) 363 { 364 edgelst_table[edgelst_last++] = rgn_edges[i]; 365 el->nr_members++; 366 } 367} 368 369/* Functions for the construction of regions. */ 370 371/* Print the regions, for debugging purposes. Callable from debugger. */ 372 373void 374debug_regions (void) 375{ 376 int rgn, bb; 377 378 fprintf (sched_dump, "\n;; ------------ REGIONS ----------\n\n"); 379 for (rgn = 0; rgn < nr_regions; rgn++) 380 { 381 fprintf (sched_dump, ";;\trgn %d nr_blocks %d:\n", rgn, 382 rgn_table[rgn].rgn_nr_blocks); 383 fprintf (sched_dump, ";;\tbb/block: "); 384 385 for (bb = 0; bb < rgn_table[rgn].rgn_nr_blocks; bb++) 386 { 387 current_blocks = RGN_BLOCKS (rgn); 388 389 gcc_assert (bb == BLOCK_TO_BB (BB_TO_BLOCK (bb))); 390 fprintf (sched_dump, " %d/%d ", bb, BB_TO_BLOCK (bb)); 391 } 392 393 fprintf (sched_dump, "\n\n"); 394 } 395} 396 397/* Build a single block region for each basic block in the function. 398 This allows for using the same code for interblock and basic block 399 scheduling. */ 400 401static void 402find_single_block_region (void) 403{ 404 basic_block bb; 405 406 nr_regions = 0; 407 408 FOR_EACH_BB (bb) 409 { 410 rgn_bb_table[nr_regions] = bb->index; 411 RGN_NR_BLOCKS (nr_regions) = 1; 412 RGN_BLOCKS (nr_regions) = nr_regions; 413 CONTAINING_RGN (bb->index) = nr_regions; 414 BLOCK_TO_BB (bb->index) = 0; 415 nr_regions++; 416 } 417} 418 419/* Update number of blocks and the estimate for number of insns 420 in the region. Return true if the region is "too large" for interblock 421 scheduling (compile time considerations). */ 422 423static bool 424too_large (int block, int *num_bbs, int *num_insns) 425{ 426 (*num_bbs)++; 427 (*num_insns) += (INSN_LUID (BB_END (BASIC_BLOCK (block))) 428 - INSN_LUID (BB_HEAD (BASIC_BLOCK (block)))); 429 430 return ((*num_bbs > PARAM_VALUE (PARAM_MAX_SCHED_REGION_BLOCKS)) 431 || (*num_insns > PARAM_VALUE (PARAM_MAX_SCHED_REGION_INSNS))); 432} 433 434/* Update_loop_relations(blk, hdr): Check if the loop headed by max_hdr[blk] 435 is still an inner loop. Put in max_hdr[blk] the header of the most inner 436 loop containing blk. */ 437#define UPDATE_LOOP_RELATIONS(blk, hdr) \ 438{ \ 439 if (max_hdr[blk] == -1) \ 440 max_hdr[blk] = hdr; \ 441 else if (dfs_nr[max_hdr[blk]] > dfs_nr[hdr]) \ 442 RESET_BIT (inner, hdr); \ 443 else if (dfs_nr[max_hdr[blk]] < dfs_nr[hdr]) \ 444 { \ 445 RESET_BIT (inner,max_hdr[blk]); \ 446 max_hdr[blk] = hdr; \ 447 } \ 448} 449 450/* Find regions for interblock scheduling. 451 452 A region for scheduling can be: 453 454 * A loop-free procedure, or 455 456 * A reducible inner loop, or 457 458 * A basic block not contained in any other region. 459 460 ?!? In theory we could build other regions based on extended basic 461 blocks or reverse extended basic blocks. Is it worth the trouble? 462 463 Loop blocks that form a region are put into the region's block list 464 in topological order. 465 466 This procedure stores its results into the following global (ick) variables 467 468 * rgn_nr 469 * rgn_table 470 * rgn_bb_table 471 * block_to_bb 472 * containing region 473 474 We use dominator relationships to avoid making regions out of non-reducible 475 loops. 476 477 This procedure needs to be converted to work on pred/succ lists instead 478 of edge tables. That would simplify it somewhat. */ 479 480static void 481find_rgns (void) 482{ 483 int *max_hdr, *dfs_nr, *degree; 484 char no_loops = 1; 485 int node, child, loop_head, i, head, tail; 486 int count = 0, sp, idx = 0; 487 edge_iterator current_edge; 488 edge_iterator *stack; 489 int num_bbs, num_insns, unreachable; 490 int too_large_failure; 491 basic_block bb; 492 493 /* Note if a block is a natural loop header. */ 494 sbitmap header; 495 496 /* Note if a block is a natural inner loop header. */ 497 sbitmap inner; 498 499 /* Note if a block is in the block queue. */ 500 sbitmap in_queue; 501 502 /* Note if a block is in the block queue. */ 503 sbitmap in_stack; 504 505 /* Perform a DFS traversal of the cfg. Identify loop headers, inner loops 506 and a mapping from block to its loop header (if the block is contained 507 in a loop, else -1). 508 509 Store results in HEADER, INNER, and MAX_HDR respectively, these will 510 be used as inputs to the second traversal. 511 512 STACK, SP and DFS_NR are only used during the first traversal. */ 513 514 /* Allocate and initialize variables for the first traversal. */ 515 max_hdr = xmalloc (last_basic_block * sizeof (int)); 516 dfs_nr = xcalloc (last_basic_block, sizeof (int)); 517 stack = xmalloc (n_edges * sizeof (edge_iterator)); 518 519 inner = sbitmap_alloc (last_basic_block); 520 sbitmap_ones (inner); 521 522 header = sbitmap_alloc (last_basic_block); 523 sbitmap_zero (header); 524 525 in_queue = sbitmap_alloc (last_basic_block); 526 sbitmap_zero (in_queue); 527 528 in_stack = sbitmap_alloc (last_basic_block); 529 sbitmap_zero (in_stack); 530 531 for (i = 0; i < last_basic_block; i++) 532 max_hdr[i] = -1; 533 534 #define EDGE_PASSED(E) (ei_end_p ((E)) || ei_edge ((E))->aux) 535 #define SET_EDGE_PASSED(E) (ei_edge ((E))->aux = ei_edge ((E))) 536 537 /* DFS traversal to find inner loops in the cfg. */ 538 539 current_edge = ei_start (single_succ (ENTRY_BLOCK_PTR)->succs); 540 sp = -1; 541 542 while (1) 543 { 544 if (EDGE_PASSED (current_edge)) 545 { 546 /* We have reached a leaf node or a node that was already 547 processed. Pop edges off the stack until we find 548 an edge that has not yet been processed. */ 549 while (sp >= 0 && EDGE_PASSED (current_edge)) 550 { 551 /* Pop entry off the stack. */ 552 current_edge = stack[sp--]; 553 node = ei_edge (current_edge)->src->index; 554 gcc_assert (node != ENTRY_BLOCK); 555 child = ei_edge (current_edge)->dest->index; 556 gcc_assert (child != EXIT_BLOCK); 557 RESET_BIT (in_stack, child); 558 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child])) 559 UPDATE_LOOP_RELATIONS (node, max_hdr[child]); 560 ei_next (¤t_edge); 561 } 562 563 /* See if have finished the DFS tree traversal. */ 564 if (sp < 0 && EDGE_PASSED (current_edge)) 565 break; 566 567 /* Nope, continue the traversal with the popped node. */ 568 continue; 569 } 570 571 /* Process a node. */ 572 node = ei_edge (current_edge)->src->index; 573 gcc_assert (node != ENTRY_BLOCK); 574 SET_BIT (in_stack, node); 575 dfs_nr[node] = ++count; 576 577 /* We don't traverse to the exit block. */ 578 child = ei_edge (current_edge)->dest->index; 579 if (child == EXIT_BLOCK) 580 { 581 SET_EDGE_PASSED (current_edge); 582 ei_next (¤t_edge); 583 continue; 584 } 585 586 /* If the successor is in the stack, then we've found a loop. 587 Mark the loop, if it is not a natural loop, then it will 588 be rejected during the second traversal. */ 589 if (TEST_BIT (in_stack, child)) 590 { 591 no_loops = 0; 592 SET_BIT (header, child); 593 UPDATE_LOOP_RELATIONS (node, child); 594 SET_EDGE_PASSED (current_edge); 595 ei_next (¤t_edge); 596 continue; 597 } 598 599 /* If the child was already visited, then there is no need to visit 600 it again. Just update the loop relationships and restart 601 with a new edge. */ 602 if (dfs_nr[child]) 603 { 604 if (max_hdr[child] >= 0 && TEST_BIT (in_stack, max_hdr[child])) 605 UPDATE_LOOP_RELATIONS (node, max_hdr[child]); 606 SET_EDGE_PASSED (current_edge); 607 ei_next (¤t_edge); 608 continue; 609 } 610 611 /* Push an entry on the stack and continue DFS traversal. */ 612 stack[++sp] = current_edge; 613 SET_EDGE_PASSED (current_edge); 614 current_edge = ei_start (ei_edge (current_edge)->dest->succs); 615 } 616 617 /* Reset ->aux field used by EDGE_PASSED. */ 618 FOR_ALL_BB (bb) 619 { 620 edge_iterator ei; 621 edge e; 622 FOR_EACH_EDGE (e, ei, bb->succs) 623 e->aux = NULL; 624 } 625 626 627 /* Another check for unreachable blocks. The earlier test in 628 is_cfg_nonregular only finds unreachable blocks that do not 629 form a loop. 630 631 The DFS traversal will mark every block that is reachable from 632 the entry node by placing a nonzero value in dfs_nr. Thus if 633 dfs_nr is zero for any block, then it must be unreachable. */ 634 unreachable = 0; 635 FOR_EACH_BB (bb) 636 if (dfs_nr[bb->index] == 0) 637 { 638 unreachable = 1; 639 break; 640 } 641 642 /* Gross. To avoid wasting memory, the second pass uses the dfs_nr array 643 to hold degree counts. */ 644 degree = dfs_nr; 645 646 FOR_EACH_BB (bb) 647 degree[bb->index] = EDGE_COUNT (bb->preds); 648 649 /* Do not perform region scheduling if there are any unreachable 650 blocks. */ 651 if (!unreachable) 652 { 653 int *queue; 654 655 if (no_loops) 656 SET_BIT (header, 0); 657 658 /* Second traversal:find reducible inner loops and topologically sort 659 block of each region. */ 660 661 queue = xmalloc (n_basic_blocks * sizeof (int)); 662 663 /* Find blocks which are inner loop headers. We still have non-reducible 664 loops to consider at this point. */ 665 FOR_EACH_BB (bb) 666 { 667 if (TEST_BIT (header, bb->index) && TEST_BIT (inner, bb->index)) 668 { 669 edge e; 670 edge_iterator ei; 671 basic_block jbb; 672 673 /* Now check that the loop is reducible. We do this separate 674 from finding inner loops so that we do not find a reducible 675 loop which contains an inner non-reducible loop. 676 677 A simple way to find reducible/natural loops is to verify 678 that each block in the loop is dominated by the loop 679 header. 680 681 If there exists a block that is not dominated by the loop 682 header, then the block is reachable from outside the loop 683 and thus the loop is not a natural loop. */ 684 FOR_EACH_BB (jbb) 685 { 686 /* First identify blocks in the loop, except for the loop 687 entry block. */ 688 if (bb->index == max_hdr[jbb->index] && bb != jbb) 689 { 690 /* Now verify that the block is dominated by the loop 691 header. */ 692 if (!dominated_by_p (CDI_DOMINATORS, jbb, bb)) 693 break; 694 } 695 } 696 697 /* If we exited the loop early, then I is the header of 698 a non-reducible loop and we should quit processing it 699 now. */ 700 if (jbb != EXIT_BLOCK_PTR) 701 continue; 702 703 /* I is a header of an inner loop, or block 0 in a subroutine 704 with no loops at all. */ 705 head = tail = -1; 706 too_large_failure = 0; 707 loop_head = max_hdr[bb->index]; 708 709 /* Decrease degree of all I's successors for topological 710 ordering. */ 711 FOR_EACH_EDGE (e, ei, bb->succs) 712 if (e->dest != EXIT_BLOCK_PTR) 713 --degree[e->dest->index]; 714 715 /* Estimate # insns, and count # blocks in the region. */ 716 num_bbs = 1; 717 num_insns = (INSN_LUID (BB_END (bb)) 718 - INSN_LUID (BB_HEAD (bb))); 719 720 /* Find all loop latches (blocks with back edges to the loop 721 header) or all the leaf blocks in the cfg has no loops. 722 723 Place those blocks into the queue. */ 724 if (no_loops) 725 { 726 FOR_EACH_BB (jbb) 727 /* Leaf nodes have only a single successor which must 728 be EXIT_BLOCK. */ 729 if (single_succ_p (jbb) 730 && single_succ (jbb) == EXIT_BLOCK_PTR) 731 { 732 queue[++tail] = jbb->index; 733 SET_BIT (in_queue, jbb->index); 734 735 if (too_large (jbb->index, &num_bbs, &num_insns)) 736 { 737 too_large_failure = 1; 738 break; 739 } 740 } 741 } 742 else 743 { 744 edge e; 745 746 FOR_EACH_EDGE (e, ei, bb->preds) 747 { 748 if (e->src == ENTRY_BLOCK_PTR) 749 continue; 750 751 node = e->src->index; 752 753 if (max_hdr[node] == loop_head && node != bb->index) 754 { 755 /* This is a loop latch. */ 756 queue[++tail] = node; 757 SET_BIT (in_queue, node); 758 759 if (too_large (node, &num_bbs, &num_insns)) 760 { 761 too_large_failure = 1; 762 break; 763 } 764 } 765 } 766 } 767 768 /* Now add all the blocks in the loop to the queue. 769 770 We know the loop is a natural loop; however the algorithm 771 above will not always mark certain blocks as being in the 772 loop. Consider: 773 node children 774 a b,c 775 b c 776 c a,d 777 d b 778 779 The algorithm in the DFS traversal may not mark B & D as part 780 of the loop (i.e. they will not have max_hdr set to A). 781 782 We know they can not be loop latches (else they would have 783 had max_hdr set since they'd have a backedge to a dominator 784 block). So we don't need them on the initial queue. 785 786 We know they are part of the loop because they are dominated 787 by the loop header and can be reached by a backwards walk of 788 the edges starting with nodes on the initial queue. 789 790 It is safe and desirable to include those nodes in the 791 loop/scheduling region. To do so we would need to decrease 792 the degree of a node if it is the target of a backedge 793 within the loop itself as the node is placed in the queue. 794 795 We do not do this because I'm not sure that the actual 796 scheduling code will properly handle this case. ?!? */ 797 798 while (head < tail && !too_large_failure) 799 { 800 edge e; 801 child = queue[++head]; 802 803 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->preds) 804 { 805 node = e->src->index; 806 807 /* See discussion above about nodes not marked as in 808 this loop during the initial DFS traversal. */ 809 if (e->src == ENTRY_BLOCK_PTR 810 || max_hdr[node] != loop_head) 811 { 812 tail = -1; 813 break; 814 } 815 else if (!TEST_BIT (in_queue, node) && node != bb->index) 816 { 817 queue[++tail] = node; 818 SET_BIT (in_queue, node); 819 820 if (too_large (node, &num_bbs, &num_insns)) 821 { 822 too_large_failure = 1; 823 break; 824 } 825 } 826 } 827 } 828 829 if (tail >= 0 && !too_large_failure) 830 { 831 /* Place the loop header into list of region blocks. */ 832 degree[bb->index] = -1; 833 rgn_bb_table[idx] = bb->index; 834 RGN_NR_BLOCKS (nr_regions) = num_bbs; 835 RGN_BLOCKS (nr_regions) = idx++; 836 CONTAINING_RGN (bb->index) = nr_regions; 837 BLOCK_TO_BB (bb->index) = count = 0; 838 839 /* Remove blocks from queue[] when their in degree 840 becomes zero. Repeat until no blocks are left on the 841 list. This produces a topological list of blocks in 842 the region. */ 843 while (tail >= 0) 844 { 845 if (head < 0) 846 head = tail; 847 child = queue[head]; 848 if (degree[child] == 0) 849 { 850 edge e; 851 852 degree[child] = -1; 853 rgn_bb_table[idx++] = child; 854 BLOCK_TO_BB (child) = ++count; 855 CONTAINING_RGN (child) = nr_regions; 856 queue[head] = queue[tail--]; 857 858 FOR_EACH_EDGE (e, ei, BASIC_BLOCK (child)->succs) 859 if (e->dest != EXIT_BLOCK_PTR) 860 --degree[e->dest->index]; 861 } 862 else 863 --head; 864 } 865 ++nr_regions; 866 } 867 } 868 } 869 free (queue); 870 } 871 872 /* Any block that did not end up in a region is placed into a region 873 by itself. */ 874 FOR_EACH_BB (bb) 875 if (degree[bb->index] >= 0) 876 { 877 rgn_bb_table[idx] = bb->index; 878 RGN_NR_BLOCKS (nr_regions) = 1; 879 RGN_BLOCKS (nr_regions) = idx++; 880 CONTAINING_RGN (bb->index) = nr_regions++; 881 BLOCK_TO_BB (bb->index) = 0; 882 } 883 884 free (max_hdr); 885 free (dfs_nr); 886 free (stack); 887 sbitmap_free (header); 888 sbitmap_free (inner); 889 sbitmap_free (in_queue); 890 sbitmap_free (in_stack); 891} 892 893/* Functions for regions scheduling information. */ 894 895/* Compute dominators, probability, and potential-split-edges of bb. 896 Assume that these values were already computed for bb's predecessors. */ 897 898static void 899compute_dom_prob_ps (int bb) 900{ 901 int pred_bb; 902 int nr_out_edges, nr_rgn_out_edges; 903 edge_iterator in_ei, out_ei; 904 edge in_edge, out_edge; 905 906 prob[bb] = 0.0; 907 if (IS_RGN_ENTRY (bb)) 908 { 909 SET_BIT (dom[bb], 0); 910 prob[bb] = 1.0; 911 return; 912 } 913 914 /* Initialize dom[bb] to '111..1'. */ 915 sbitmap_ones (dom[bb]); 916 917 FOR_EACH_EDGE (in_edge, in_ei, BASIC_BLOCK (BB_TO_BLOCK (bb))->preds) 918 { 919 if (in_edge->src == ENTRY_BLOCK_PTR) 920 continue; 921 922 pred_bb = BLOCK_TO_BB (in_edge->src->index); 923 sbitmap_a_and_b (dom[bb], dom[bb], dom[pred_bb]); 924 sbitmap_a_or_b (ancestor_edges[bb], 925 ancestor_edges[bb], ancestor_edges[pred_bb]); 926 927 SET_BIT (ancestor_edges[bb], EDGE_TO_BIT (in_edge)); 928 929 sbitmap_a_or_b (pot_split[bb], pot_split[bb], pot_split[pred_bb]); 930 931 nr_out_edges = 0; 932 nr_rgn_out_edges = 0; 933 934 FOR_EACH_EDGE (out_edge, out_ei, in_edge->src->succs) 935 { 936 ++nr_out_edges; 937 938 /* The successor doesn't belong in the region? */ 939 if (out_edge->dest != EXIT_BLOCK_PTR 940 && CONTAINING_RGN (out_edge->dest->index) 941 != CONTAINING_RGN (BB_TO_BLOCK (bb))) 942 ++nr_rgn_out_edges; 943 944 SET_BIT (pot_split[bb], EDGE_TO_BIT (out_edge)); 945 } 946 947 /* Now nr_rgn_out_edges is the number of region-exit edges from 948 pred, and nr_out_edges will be the number of pred out edges 949 not leaving the region. */ 950 nr_out_edges -= nr_rgn_out_edges; 951 if (nr_rgn_out_edges > 0) 952 prob[bb] += 0.9 * prob[pred_bb] / nr_out_edges; 953 else 954 prob[bb] += prob[pred_bb] / nr_out_edges; 955 } 956 957 SET_BIT (dom[bb], bb); 958 sbitmap_difference (pot_split[bb], pot_split[bb], ancestor_edges[bb]); 959 960 if (sched_verbose >= 2) 961 fprintf (sched_dump, ";; bb_prob(%d, %d) = %3d\n", bb, BB_TO_BLOCK (bb), 962 (int) (100.0 * prob[bb])); 963} 964 965/* Functions for target info. */ 966 967/* Compute in BL the list of split-edges of bb_src relatively to bb_trg. 968 Note that bb_trg dominates bb_src. */ 969 970static void 971split_edges (int bb_src, int bb_trg, edgelst *bl) 972{ 973 sbitmap src = sbitmap_alloc (pot_split[bb_src]->n_bits); 974 sbitmap_copy (src, pot_split[bb_src]); 975 976 sbitmap_difference (src, src, pot_split[bb_trg]); 977 extract_edgelst (src, bl); 978 sbitmap_free (src); 979} 980 981/* Find the valid candidate-source-blocks for the target block TRG, compute 982 their probability, and check if they are speculative or not. 983 For speculative sources, compute their update-blocks and split-blocks. */ 984 985static void 986compute_trg_info (int trg) 987{ 988 candidate *sp; 989 edgelst el; 990 int i, j, k, update_idx; 991 basic_block block; 992 sbitmap visited; 993 edge_iterator ei; 994 edge e; 995 996 /* Define some of the fields for the target bb as well. */ 997 sp = candidate_table + trg; 998 sp->is_valid = 1; 999 sp->is_speculative = 0; 1000 sp->src_prob = 100; 1001 1002 visited = sbitmap_alloc (last_basic_block - (INVALID_BLOCK + 1)); 1003 1004 for (i = trg + 1; i < current_nr_blocks; i++) 1005 { 1006 sp = candidate_table + i; 1007 1008 sp->is_valid = IS_DOMINATED (i, trg); 1009 if (sp->is_valid) 1010 { 1011 sp->src_prob = GET_SRC_PROB (i, trg); 1012 sp->is_valid = (sp->src_prob >= PARAM_VALUE (PARAM_MIN_SPEC_PROB)); 1013 } 1014 1015 if (sp->is_valid) 1016 { 1017 split_edges (i, trg, &el); 1018 sp->is_speculative = (el.nr_members) ? 1 : 0; 1019 if (sp->is_speculative && !flag_schedule_speculative) 1020 sp->is_valid = 0; 1021 } 1022 1023 if (sp->is_valid) 1024 { 1025 /* Compute split blocks and store them in bblst_table. 1026 The TO block of every split edge is a split block. */ 1027 sp->split_bbs.first_member = &bblst_table[bblst_last]; 1028 sp->split_bbs.nr_members = el.nr_members; 1029 for (j = 0; j < el.nr_members; bblst_last++, j++) 1030 bblst_table[bblst_last] = el.first_member[j]->dest; 1031 sp->update_bbs.first_member = &bblst_table[bblst_last]; 1032 1033 /* Compute update blocks and store them in bblst_table. 1034 For every split edge, look at the FROM block, and check 1035 all out edges. For each out edge that is not a split edge, 1036 add the TO block to the update block list. This list can end 1037 up with a lot of duplicates. We need to weed them out to avoid 1038 overrunning the end of the bblst_table. */ 1039 1040 update_idx = 0; 1041 sbitmap_zero (visited); 1042 for (j = 0; j < el.nr_members; j++) 1043 { 1044 block = el.first_member[j]->src; 1045 FOR_EACH_EDGE (e, ei, block->succs) 1046 { 1047 if (!TEST_BIT (visited, 1048 e->dest->index - (INVALID_BLOCK + 1))) 1049 { 1050 for (k = 0; k < el.nr_members; k++) 1051 if (e == el.first_member[k]) 1052 break; 1053 1054 if (k >= el.nr_members) 1055 { 1056 bblst_table[bblst_last++] = e->dest; 1057 SET_BIT (visited, 1058 e->dest->index - (INVALID_BLOCK + 1)); 1059 update_idx++; 1060 } 1061 } 1062 } 1063 } 1064 sp->update_bbs.nr_members = update_idx; 1065 1066 /* Make sure we didn't overrun the end of bblst_table. */ 1067 gcc_assert (bblst_last <= bblst_size); 1068 } 1069 else 1070 { 1071 sp->split_bbs.nr_members = sp->update_bbs.nr_members = 0; 1072 1073 sp->is_speculative = 0; 1074 sp->src_prob = 0; 1075 } 1076 } 1077 1078 sbitmap_free (visited); 1079} 1080 1081/* Print candidates info, for debugging purposes. Callable from debugger. */ 1082 1083void 1084debug_candidate (int i) 1085{ 1086 if (!candidate_table[i].is_valid) 1087 return; 1088 1089 if (candidate_table[i].is_speculative) 1090 { 1091 int j; 1092 fprintf (sched_dump, "src b %d bb %d speculative \n", BB_TO_BLOCK (i), i); 1093 1094 fprintf (sched_dump, "split path: "); 1095 for (j = 0; j < candidate_table[i].split_bbs.nr_members; j++) 1096 { 1097 int b = candidate_table[i].split_bbs.first_member[j]->index; 1098 1099 fprintf (sched_dump, " %d ", b); 1100 } 1101 fprintf (sched_dump, "\n"); 1102 1103 fprintf (sched_dump, "update path: "); 1104 for (j = 0; j < candidate_table[i].update_bbs.nr_members; j++) 1105 { 1106 int b = candidate_table[i].update_bbs.first_member[j]->index; 1107 1108 fprintf (sched_dump, " %d ", b); 1109 } 1110 fprintf (sched_dump, "\n"); 1111 } 1112 else 1113 { 1114 fprintf (sched_dump, " src %d equivalent\n", BB_TO_BLOCK (i)); 1115 } 1116} 1117 1118/* Print candidates info, for debugging purposes. Callable from debugger. */ 1119 1120void 1121debug_candidates (int trg) 1122{ 1123 int i; 1124 1125 fprintf (sched_dump, "----------- candidate table: target: b=%d bb=%d ---\n", 1126 BB_TO_BLOCK (trg), trg); 1127 for (i = trg + 1; i < current_nr_blocks; i++) 1128 debug_candidate (i); 1129} 1130 1131/* Functions for speculative scheduling. */ 1132 1133/* Return 0 if x is a set of a register alive in the beginning of one 1134 of the split-blocks of src, otherwise return 1. */ 1135 1136static int 1137check_live_1 (int src, rtx x) 1138{ 1139 int i; 1140 int regno; 1141 rtx reg = SET_DEST (x); 1142 1143 if (reg == 0) 1144 return 1; 1145 1146 while (GET_CODE (reg) == SUBREG 1147 || GET_CODE (reg) == ZERO_EXTRACT 1148 || GET_CODE (reg) == STRICT_LOW_PART) 1149 reg = XEXP (reg, 0); 1150 1151 if (GET_CODE (reg) == PARALLEL) 1152 { 1153 int i; 1154 1155 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 1156 if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 1157 if (check_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0))) 1158 return 1; 1159 1160 return 0; 1161 } 1162 1163 if (!REG_P (reg)) 1164 return 1; 1165 1166 regno = REGNO (reg); 1167 1168 if (regno < FIRST_PSEUDO_REGISTER && global_regs[regno]) 1169 { 1170 /* Global registers are assumed live. */ 1171 return 0; 1172 } 1173 else 1174 { 1175 if (regno < FIRST_PSEUDO_REGISTER) 1176 { 1177 /* Check for hard registers. */ 1178 int j = hard_regno_nregs[regno][GET_MODE (reg)]; 1179 while (--j >= 0) 1180 { 1181 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++) 1182 { 1183 basic_block b = candidate_table[src].split_bbs.first_member[i]; 1184 1185 if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start, 1186 regno + j)) 1187 { 1188 return 0; 1189 } 1190 } 1191 } 1192 } 1193 else 1194 { 1195 /* Check for pseudo registers. */ 1196 for (i = 0; i < candidate_table[src].split_bbs.nr_members; i++) 1197 { 1198 basic_block b = candidate_table[src].split_bbs.first_member[i]; 1199 1200 if (REGNO_REG_SET_P (b->il.rtl->global_live_at_start, regno)) 1201 { 1202 return 0; 1203 } 1204 } 1205 } 1206 } 1207 1208 return 1; 1209} 1210 1211/* If x is a set of a register R, mark that R is alive in the beginning 1212 of every update-block of src. */ 1213 1214static void 1215update_live_1 (int src, rtx x) 1216{ 1217 int i; 1218 int regno; 1219 rtx reg = SET_DEST (x); 1220 1221 if (reg == 0) 1222 return; 1223 1224 while (GET_CODE (reg) == SUBREG 1225 || GET_CODE (reg) == ZERO_EXTRACT 1226 || GET_CODE (reg) == STRICT_LOW_PART) 1227 reg = XEXP (reg, 0); 1228 1229 if (GET_CODE (reg) == PARALLEL) 1230 { 1231 int i; 1232 1233 for (i = XVECLEN (reg, 0) - 1; i >= 0; i--) 1234 if (XEXP (XVECEXP (reg, 0, i), 0) != 0) 1235 update_live_1 (src, XEXP (XVECEXP (reg, 0, i), 0)); 1236 1237 return; 1238 } 1239 1240 if (!REG_P (reg)) 1241 return; 1242 1243 /* Global registers are always live, so the code below does not apply 1244 to them. */ 1245 1246 regno = REGNO (reg); 1247 1248 if (regno >= FIRST_PSEUDO_REGISTER || !global_regs[regno]) 1249 { 1250 if (regno < FIRST_PSEUDO_REGISTER) 1251 { 1252 int j = hard_regno_nregs[regno][GET_MODE (reg)]; 1253 while (--j >= 0) 1254 { 1255 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++) 1256 { 1257 basic_block b = candidate_table[src].update_bbs.first_member[i]; 1258 1259 SET_REGNO_REG_SET (b->il.rtl->global_live_at_start, 1260 regno + j); 1261 } 1262 } 1263 } 1264 else 1265 { 1266 for (i = 0; i < candidate_table[src].update_bbs.nr_members; i++) 1267 { 1268 basic_block b = candidate_table[src].update_bbs.first_member[i]; 1269 1270 SET_REGNO_REG_SET (b->il.rtl->global_live_at_start, regno); 1271 } 1272 } 1273 } 1274} 1275 1276/* Return 1 if insn can be speculatively moved from block src to trg, 1277 otherwise return 0. Called before first insertion of insn to 1278 ready-list or before the scheduling. */ 1279 1280static int 1281check_live (rtx insn, int src) 1282{ 1283 /* Find the registers set by instruction. */ 1284 if (GET_CODE (PATTERN (insn)) == SET 1285 || GET_CODE (PATTERN (insn)) == CLOBBER) 1286 return check_live_1 (src, PATTERN (insn)); 1287 else if (GET_CODE (PATTERN (insn)) == PARALLEL) 1288 { 1289 int j; 1290 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) 1291 if ((GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET 1292 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) 1293 && !check_live_1 (src, XVECEXP (PATTERN (insn), 0, j))) 1294 return 0; 1295 1296 return 1; 1297 } 1298 1299 return 1; 1300} 1301 1302/* Update the live registers info after insn was moved speculatively from 1303 block src to trg. */ 1304 1305static void 1306update_live (rtx insn, int src) 1307{ 1308 /* Find the registers set by instruction. */ 1309 if (GET_CODE (PATTERN (insn)) == SET 1310 || GET_CODE (PATTERN (insn)) == CLOBBER) 1311 update_live_1 (src, PATTERN (insn)); 1312 else if (GET_CODE (PATTERN (insn)) == PARALLEL) 1313 { 1314 int j; 1315 for (j = XVECLEN (PATTERN (insn), 0) - 1; j >= 0; j--) 1316 if (GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == SET 1317 || GET_CODE (XVECEXP (PATTERN (insn), 0, j)) == CLOBBER) 1318 update_live_1 (src, XVECEXP (PATTERN (insn), 0, j)); 1319 } 1320} 1321 1322/* Nonzero if block bb_to is equal to, or reachable from block bb_from. */ 1323#define IS_REACHABLE(bb_from, bb_to) \ 1324 (bb_from == bb_to \ 1325 || IS_RGN_ENTRY (bb_from) \ 1326 || (TEST_BIT (ancestor_edges[bb_to], \ 1327 EDGE_TO_BIT (single_pred_edge (BASIC_BLOCK (BB_TO_BLOCK (bb_from))))))) 1328 1329/* Turns on the fed_by_spec_load flag for insns fed by load_insn. */ 1330 1331static void 1332set_spec_fed (rtx load_insn) 1333{ 1334 rtx link; 1335 1336 for (link = INSN_DEPEND (load_insn); link; link = XEXP (link, 1)) 1337 if (GET_MODE (link) == VOIDmode) 1338 FED_BY_SPEC_LOAD (XEXP (link, 0)) = 1; 1339} /* set_spec_fed */ 1340 1341/* On the path from the insn to load_insn_bb, find a conditional 1342branch depending on insn, that guards the speculative load. */ 1343 1344static int 1345find_conditional_protection (rtx insn, int load_insn_bb) 1346{ 1347 rtx link; 1348 1349 /* Iterate through DEF-USE forward dependences. */ 1350 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) 1351 { 1352 rtx next = XEXP (link, 0); 1353 if ((CONTAINING_RGN (BLOCK_NUM (next)) == 1354 CONTAINING_RGN (BB_TO_BLOCK (load_insn_bb))) 1355 && IS_REACHABLE (INSN_BB (next), load_insn_bb) 1356 && load_insn_bb != INSN_BB (next) 1357 && GET_MODE (link) == VOIDmode 1358 && (JUMP_P (next) 1359 || find_conditional_protection (next, load_insn_bb))) 1360 return 1; 1361 } 1362 return 0; 1363} /* find_conditional_protection */ 1364 1365/* Returns 1 if the same insn1 that participates in the computation 1366 of load_insn's address is feeding a conditional branch that is 1367 guarding on load_insn. This is true if we find a the two DEF-USE 1368 chains: 1369 insn1 -> ... -> conditional-branch 1370 insn1 -> ... -> load_insn, 1371 and if a flow path exist: 1372 insn1 -> ... -> conditional-branch -> ... -> load_insn, 1373 and if insn1 is on the path 1374 region-entry -> ... -> bb_trg -> ... load_insn. 1375 1376 Locate insn1 by climbing on LOG_LINKS from load_insn. 1377 Locate the branch by following INSN_DEPEND from insn1. */ 1378 1379static int 1380is_conditionally_protected (rtx load_insn, int bb_src, int bb_trg) 1381{ 1382 rtx link; 1383 1384 for (link = LOG_LINKS (load_insn); link; link = XEXP (link, 1)) 1385 { 1386 rtx insn1 = XEXP (link, 0); 1387 1388 /* Must be a DEF-USE dependence upon non-branch. */ 1389 if (GET_MODE (link) != VOIDmode 1390 || JUMP_P (insn1)) 1391 continue; 1392 1393 /* Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn. */ 1394 if (INSN_BB (insn1) == bb_src 1395 || (CONTAINING_RGN (BLOCK_NUM (insn1)) 1396 != CONTAINING_RGN (BB_TO_BLOCK (bb_src))) 1397 || (!IS_REACHABLE (bb_trg, INSN_BB (insn1)) 1398 && !IS_REACHABLE (INSN_BB (insn1), bb_trg))) 1399 continue; 1400 1401 /* Now search for the conditional-branch. */ 1402 if (find_conditional_protection (insn1, bb_src)) 1403 return 1; 1404 1405 /* Recursive step: search another insn1, "above" current insn1. */ 1406 return is_conditionally_protected (insn1, bb_src, bb_trg); 1407 } 1408 1409 /* The chain does not exist. */ 1410 return 0; 1411} /* is_conditionally_protected */ 1412 1413/* Returns 1 if a clue for "similar load" 'insn2' is found, and hence 1414 load_insn can move speculatively from bb_src to bb_trg. All the 1415 following must hold: 1416 1417 (1) both loads have 1 base register (PFREE_CANDIDATEs). 1418 (2) load_insn and load1 have a def-use dependence upon 1419 the same insn 'insn1'. 1420 (3) either load2 is in bb_trg, or: 1421 - there's only one split-block, and 1422 - load1 is on the escape path, and 1423 1424 From all these we can conclude that the two loads access memory 1425 addresses that differ at most by a constant, and hence if moving 1426 load_insn would cause an exception, it would have been caused by 1427 load2 anyhow. */ 1428 1429static int 1430is_pfree (rtx load_insn, int bb_src, int bb_trg) 1431{ 1432 rtx back_link; 1433 candidate *candp = candidate_table + bb_src; 1434 1435 if (candp->split_bbs.nr_members != 1) 1436 /* Must have exactly one escape block. */ 1437 return 0; 1438 1439 for (back_link = LOG_LINKS (load_insn); 1440 back_link; back_link = XEXP (back_link, 1)) 1441 { 1442 rtx insn1 = XEXP (back_link, 0); 1443 1444 if (GET_MODE (back_link) == VOIDmode) 1445 { 1446 /* Found a DEF-USE dependence (insn1, load_insn). */ 1447 rtx fore_link; 1448 1449 for (fore_link = INSN_DEPEND (insn1); 1450 fore_link; fore_link = XEXP (fore_link, 1)) 1451 { 1452 rtx insn2 = XEXP (fore_link, 0); 1453 if (GET_MODE (fore_link) == VOIDmode) 1454 { 1455 /* Found a DEF-USE dependence (insn1, insn2). */ 1456 if (haifa_classify_insn (insn2) != PFREE_CANDIDATE) 1457 /* insn2 not guaranteed to be a 1 base reg load. */ 1458 continue; 1459 1460 if (INSN_BB (insn2) == bb_trg) 1461 /* insn2 is the similar load, in the target block. */ 1462 return 1; 1463 1464 if (*(candp->split_bbs.first_member) == BLOCK_FOR_INSN (insn2)) 1465 /* insn2 is a similar load, in a split-block. */ 1466 return 1; 1467 } 1468 } 1469 } 1470 } 1471 1472 /* Couldn't find a similar load. */ 1473 return 0; 1474} /* is_pfree */ 1475 1476/* Return 1 if load_insn is prisky (i.e. if load_insn is fed by 1477 a load moved speculatively, or if load_insn is protected by 1478 a compare on load_insn's address). */ 1479 1480static int 1481is_prisky (rtx load_insn, int bb_src, int bb_trg) 1482{ 1483 if (FED_BY_SPEC_LOAD (load_insn)) 1484 return 1; 1485 1486 if (LOG_LINKS (load_insn) == NULL) 1487 /* Dependence may 'hide' out of the region. */ 1488 return 1; 1489 1490 if (is_conditionally_protected (load_insn, bb_src, bb_trg)) 1491 return 1; 1492 1493 return 0; 1494} 1495 1496/* Insn is a candidate to be moved speculatively from bb_src to bb_trg. 1497 Return 1 if insn is exception-free (and the motion is valid) 1498 and 0 otherwise. */ 1499 1500static int 1501is_exception_free (rtx insn, int bb_src, int bb_trg) 1502{ 1503 int insn_class = haifa_classify_insn (insn); 1504 1505 /* Handle non-load insns. */ 1506 switch (insn_class) 1507 { 1508 case TRAP_FREE: 1509 return 1; 1510 case TRAP_RISKY: 1511 return 0; 1512 default:; 1513 } 1514 1515 /* Handle loads. */ 1516 if (!flag_schedule_speculative_load) 1517 return 0; 1518 IS_LOAD_INSN (insn) = 1; 1519 switch (insn_class) 1520 { 1521 case IFREE: 1522 return (1); 1523 case IRISKY: 1524 return 0; 1525 case PFREE_CANDIDATE: 1526 if (is_pfree (insn, bb_src, bb_trg)) 1527 return 1; 1528 /* Don't 'break' here: PFREE-candidate is also PRISKY-candidate. */ 1529 case PRISKY_CANDIDATE: 1530 if (!flag_schedule_speculative_load_dangerous 1531 || is_prisky (insn, bb_src, bb_trg)) 1532 return 0; 1533 break; 1534 default:; 1535 } 1536 1537 return flag_schedule_speculative_load_dangerous; 1538} 1539 1540/* The number of insns from the current block scheduled so far. */ 1541static int sched_target_n_insns; 1542/* The number of insns from the current block to be scheduled in total. */ 1543static int target_n_insns; 1544/* The number of insns from the entire region scheduled so far. */ 1545static int sched_n_insns; 1546/* Nonzero if the last scheduled insn was a jump. */ 1547static int last_was_jump; 1548 1549/* Implementations of the sched_info functions for region scheduling. */ 1550static void init_ready_list (struct ready_list *); 1551static int can_schedule_ready_p (rtx); 1552static int new_ready (rtx); 1553static int schedule_more_p (void); 1554static const char *rgn_print_insn (rtx, int); 1555static int rgn_rank (rtx, rtx); 1556static int contributes_to_priority (rtx, rtx); 1557static void compute_jump_reg_dependencies (rtx, regset, regset, regset); 1558 1559/* Return nonzero if there are more insns that should be scheduled. */ 1560 1561static int 1562schedule_more_p (void) 1563{ 1564 return ! last_was_jump && sched_target_n_insns < target_n_insns; 1565} 1566 1567/* Add all insns that are initially ready to the ready list READY. Called 1568 once before scheduling a set of insns. */ 1569 1570static void 1571init_ready_list (struct ready_list *ready) 1572{ 1573 rtx prev_head = current_sched_info->prev_head; 1574 rtx next_tail = current_sched_info->next_tail; 1575 int bb_src; 1576 rtx insn; 1577 1578 target_n_insns = 0; 1579 sched_target_n_insns = 0; 1580 sched_n_insns = 0; 1581 last_was_jump = 0; 1582 1583 /* Print debugging information. */ 1584 if (sched_verbose >= 5) 1585 debug_dependencies (); 1586 1587 /* Prepare current target block info. */ 1588 if (current_nr_blocks > 1) 1589 { 1590 candidate_table = xmalloc (current_nr_blocks * sizeof (candidate)); 1591 1592 bblst_last = 0; 1593 /* bblst_table holds split blocks and update blocks for each block after 1594 the current one in the region. split blocks and update blocks are 1595 the TO blocks of region edges, so there can be at most rgn_nr_edges 1596 of them. */ 1597 bblst_size = (current_nr_blocks - target_bb) * rgn_nr_edges; 1598 bblst_table = xmalloc (bblst_size * sizeof (basic_block)); 1599 1600 edgelst_last = 0; 1601 edgelst_table = xmalloc (rgn_nr_edges * sizeof (edge)); 1602 1603 compute_trg_info (target_bb); 1604 } 1605 1606 /* Initialize ready list with all 'ready' insns in target block. 1607 Count number of insns in the target block being scheduled. */ 1608 for (insn = NEXT_INSN (prev_head); insn != next_tail; insn = NEXT_INSN (insn)) 1609 { 1610 if (INSN_DEP_COUNT (insn) == 0) 1611 { 1612 ready_add (ready, insn); 1613 1614 if (targetm.sched.adjust_priority) 1615 INSN_PRIORITY (insn) = 1616 targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn)); 1617 } 1618 target_n_insns++; 1619 } 1620 1621 /* Add to ready list all 'ready' insns in valid source blocks. 1622 For speculative insns, check-live, exception-free, and 1623 issue-delay. */ 1624 for (bb_src = target_bb + 1; bb_src < current_nr_blocks; bb_src++) 1625 if (IS_VALID (bb_src)) 1626 { 1627 rtx src_head; 1628 rtx src_next_tail; 1629 rtx tail, head; 1630 1631 get_block_head_tail (BB_TO_BLOCK (bb_src), &head, &tail); 1632 src_next_tail = NEXT_INSN (tail); 1633 src_head = head; 1634 1635 for (insn = src_head; insn != src_next_tail; insn = NEXT_INSN (insn)) 1636 { 1637 if (! INSN_P (insn)) 1638 continue; 1639 1640 if (!CANT_MOVE (insn) 1641 && (!IS_SPECULATIVE_INSN (insn) 1642 || ((recog_memoized (insn) < 0 1643 || min_insn_conflict_delay (curr_state, 1644 insn, insn) <= 3) 1645 && check_live (insn, bb_src) 1646 && is_exception_free (insn, bb_src, target_bb)))) 1647 if (INSN_DEP_COUNT (insn) == 0) 1648 { 1649 ready_add (ready, insn); 1650 1651 if (targetm.sched.adjust_priority) 1652 INSN_PRIORITY (insn) = 1653 targetm.sched.adjust_priority (insn, INSN_PRIORITY (insn)); 1654 } 1655 } 1656 } 1657} 1658 1659/* Called after taking INSN from the ready list. Returns nonzero if this 1660 insn can be scheduled, nonzero if we should silently discard it. */ 1661 1662static int 1663can_schedule_ready_p (rtx insn) 1664{ 1665 if (JUMP_P (insn)) 1666 last_was_jump = 1; 1667 1668 /* An interblock motion? */ 1669 if (INSN_BB (insn) != target_bb) 1670 { 1671 basic_block b1; 1672 1673 if (IS_SPECULATIVE_INSN (insn)) 1674 { 1675 if (!check_live (insn, INSN_BB (insn))) 1676 return 0; 1677 update_live (insn, INSN_BB (insn)); 1678 1679 /* For speculative load, mark insns fed by it. */ 1680 if (IS_LOAD_INSN (insn) || FED_BY_SPEC_LOAD (insn)) 1681 set_spec_fed (insn); 1682 1683 nr_spec++; 1684 } 1685 nr_inter++; 1686 1687 /* Update source block boundaries. */ 1688 b1 = BLOCK_FOR_INSN (insn); 1689 if (insn == BB_HEAD (b1) && insn == BB_END (b1)) 1690 { 1691 /* We moved all the insns in the basic block. 1692 Emit a note after the last insn and update the 1693 begin/end boundaries to point to the note. */ 1694 rtx note = emit_note_after (NOTE_INSN_DELETED, insn); 1695 BB_HEAD (b1) = note; 1696 BB_END (b1) = note; 1697 } 1698 else if (insn == BB_END (b1)) 1699 { 1700 /* We took insns from the end of the basic block, 1701 so update the end of block boundary so that it 1702 points to the first insn we did not move. */ 1703 BB_END (b1) = PREV_INSN (insn); 1704 } 1705 else if (insn == BB_HEAD (b1)) 1706 { 1707 /* We took insns from the start of the basic block, 1708 so update the start of block boundary so that 1709 it points to the first insn we did not move. */ 1710 BB_HEAD (b1) = NEXT_INSN (insn); 1711 } 1712 } 1713 else 1714 { 1715 /* In block motion. */ 1716 sched_target_n_insns++; 1717 } 1718 sched_n_insns++; 1719 1720 return 1; 1721} 1722 1723/* Called after INSN has all its dependencies resolved. Return nonzero 1724 if it should be moved to the ready list or the queue, or zero if we 1725 should silently discard it. */ 1726static int 1727new_ready (rtx next) 1728{ 1729 /* For speculative insns, before inserting to ready/queue, 1730 check live, exception-free, and issue-delay. */ 1731 if (INSN_BB (next) != target_bb 1732 && (!IS_VALID (INSN_BB (next)) 1733 || CANT_MOVE (next) 1734 || (IS_SPECULATIVE_INSN (next) 1735 && ((recog_memoized (next) >= 0 1736 && min_insn_conflict_delay (curr_state, next, next) > 3) 1737 || !check_live (next, INSN_BB (next)) 1738 || !is_exception_free (next, INSN_BB (next), target_bb))))) 1739 return 0; 1740 return 1; 1741} 1742 1743/* Return a string that contains the insn uid and optionally anything else 1744 necessary to identify this insn in an output. It's valid to use a 1745 static buffer for this. The ALIGNED parameter should cause the string 1746 to be formatted so that multiple output lines will line up nicely. */ 1747 1748static const char * 1749rgn_print_insn (rtx insn, int aligned) 1750{ 1751 static char tmp[80]; 1752 1753 if (aligned) 1754 sprintf (tmp, "b%3d: i%4d", INSN_BB (insn), INSN_UID (insn)); 1755 else 1756 { 1757 if (current_nr_blocks > 1 && INSN_BB (insn) != target_bb) 1758 sprintf (tmp, "%d/b%d", INSN_UID (insn), INSN_BB (insn)); 1759 else 1760 sprintf (tmp, "%d", INSN_UID (insn)); 1761 } 1762 return tmp; 1763} 1764 1765/* Compare priority of two insns. Return a positive number if the second 1766 insn is to be preferred for scheduling, and a negative one if the first 1767 is to be preferred. Zero if they are equally good. */ 1768 1769static int 1770rgn_rank (rtx insn1, rtx insn2) 1771{ 1772 /* Some comparison make sense in interblock scheduling only. */ 1773 if (INSN_BB (insn1) != INSN_BB (insn2)) 1774 { 1775 int spec_val, prob_val; 1776 1777 /* Prefer an inblock motion on an interblock motion. */ 1778 if ((INSN_BB (insn2) == target_bb) && (INSN_BB (insn1) != target_bb)) 1779 return 1; 1780 if ((INSN_BB (insn1) == target_bb) && (INSN_BB (insn2) != target_bb)) 1781 return -1; 1782 1783 /* Prefer a useful motion on a speculative one. */ 1784 spec_val = IS_SPECULATIVE_INSN (insn1) - IS_SPECULATIVE_INSN (insn2); 1785 if (spec_val) 1786 return spec_val; 1787 1788 /* Prefer a more probable (speculative) insn. */ 1789 prob_val = INSN_PROBABILITY (insn2) - INSN_PROBABILITY (insn1); 1790 if (prob_val) 1791 return prob_val; 1792 } 1793 return 0; 1794} 1795 1796/* NEXT is an instruction that depends on INSN (a backward dependence); 1797 return nonzero if we should include this dependence in priority 1798 calculations. */ 1799 1800static int 1801contributes_to_priority (rtx next, rtx insn) 1802{ 1803 return BLOCK_NUM (next) == BLOCK_NUM (insn); 1804} 1805 1806/* INSN is a JUMP_INSN, COND_SET is the set of registers that are 1807 conditionally set before INSN. Store the set of registers that 1808 must be considered as used by this jump in USED and that of 1809 registers that must be considered as set in SET. */ 1810 1811static void 1812compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED, 1813 regset cond_exec ATTRIBUTE_UNUSED, 1814 regset used ATTRIBUTE_UNUSED, 1815 regset set ATTRIBUTE_UNUSED) 1816{ 1817 /* Nothing to do here, since we postprocess jumps in 1818 add_branch_dependences. */ 1819} 1820 1821/* Used in schedule_insns to initialize current_sched_info for scheduling 1822 regions (or single basic blocks). */ 1823 1824static struct sched_info region_sched_info = 1825{ 1826 init_ready_list, 1827 can_schedule_ready_p, 1828 schedule_more_p, 1829 new_ready, 1830 rgn_rank, 1831 rgn_print_insn, 1832 contributes_to_priority, 1833 compute_jump_reg_dependencies, 1834 1835 NULL, NULL, 1836 NULL, NULL, 1837 0, 0, 0 1838}; 1839 1840/* Determine if PAT sets a CLASS_LIKELY_SPILLED_P register. */ 1841 1842static bool 1843sets_likely_spilled (rtx pat) 1844{ 1845 bool ret = false; 1846 note_stores (pat, sets_likely_spilled_1, &ret); 1847 return ret; 1848} 1849 1850static void 1851sets_likely_spilled_1 (rtx x, rtx pat, void *data) 1852{ 1853 bool *ret = (bool *) data; 1854 1855 if (GET_CODE (pat) == SET 1856 && REG_P (x) 1857 && REGNO (x) < FIRST_PSEUDO_REGISTER 1858 && CLASS_LIKELY_SPILLED_P (REGNO_REG_CLASS (REGNO (x)))) 1859 *ret = true; 1860} 1861 1862/* Add dependences so that branches are scheduled to run last in their 1863 block. */ 1864 1865static void 1866add_branch_dependences (rtx head, rtx tail) 1867{ 1868 rtx insn, last; 1869 1870 /* For all branches, calls, uses, clobbers, cc0 setters, and instructions 1871 that can throw exceptions, force them to remain in order at the end of 1872 the block by adding dependencies and giving the last a high priority. 1873 There may be notes present, and prev_head may also be a note. 1874 1875 Branches must obviously remain at the end. Calls should remain at the 1876 end since moving them results in worse register allocation. Uses remain 1877 at the end to ensure proper register allocation. 1878 1879 cc0 setters remain at the end because they can't be moved away from 1880 their cc0 user. 1881 1882 COND_EXEC insns cannot be moved past a branch (see e.g. PR17808). 1883 1884 Insns setting CLASS_LIKELY_SPILLED_P registers (usually return values) 1885 are not moved before reload because we can wind up with register 1886 allocation failures. */ 1887 1888 insn = tail; 1889 last = 0; 1890 while (CALL_P (insn) 1891 || JUMP_P (insn) 1892 || (NONJUMP_INSN_P (insn) 1893 && (GET_CODE (PATTERN (insn)) == USE 1894 || GET_CODE (PATTERN (insn)) == CLOBBER 1895 || can_throw_internal (insn) 1896#ifdef HAVE_cc0 1897 || sets_cc0_p (PATTERN (insn)) 1898#endif 1899 || (!reload_completed 1900 && sets_likely_spilled (PATTERN (insn))))) 1901 || NOTE_P (insn)) 1902 { 1903 if (!NOTE_P (insn)) 1904 { 1905 if (last != 0 && !find_insn_list (insn, LOG_LINKS (last))) 1906 { 1907 if (! sched_insns_conditions_mutex_p (last, insn)) 1908 add_dependence (last, insn, REG_DEP_ANTI); 1909 INSN_REF_COUNT (insn)++; 1910 } 1911 1912 CANT_MOVE (insn) = 1; 1913 1914 last = insn; 1915 } 1916 1917 /* Don't overrun the bounds of the basic block. */ 1918 if (insn == head) 1919 break; 1920 1921 insn = PREV_INSN (insn); 1922 } 1923 1924 /* Make sure these insns are scheduled last in their block. */ 1925 insn = last; 1926 if (insn != 0) 1927 while (insn != head) 1928 { 1929 insn = prev_nonnote_insn (insn); 1930 1931 if (INSN_REF_COUNT (insn) != 0) 1932 continue; 1933 1934 if (! sched_insns_conditions_mutex_p (last, insn)) 1935 add_dependence (last, insn, REG_DEP_ANTI); 1936 INSN_REF_COUNT (insn) = 1; 1937 } 1938 1939#ifdef HAVE_conditional_execution 1940 /* Finally, if the block ends in a jump, and we are doing intra-block 1941 scheduling, make sure that the branch depends on any COND_EXEC insns 1942 inside the block to avoid moving the COND_EXECs past the branch insn. 1943 1944 We only have to do this after reload, because (1) before reload there 1945 are no COND_EXEC insns, and (2) the region scheduler is an intra-block 1946 scheduler after reload. 1947 1948 FIXME: We could in some cases move COND_EXEC insns past the branch if 1949 this scheduler would be a little smarter. Consider this code: 1950 1951 T = [addr] 1952 C ? addr += 4 1953 !C ? X += 12 1954 C ? T += 1 1955 C ? jump foo 1956 1957 On a target with a one cycle stall on a memory access the optimal 1958 sequence would be: 1959 1960 T = [addr] 1961 C ? addr += 4 1962 C ? T += 1 1963 C ? jump foo 1964 !C ? X += 12 1965 1966 We don't want to put the 'X += 12' before the branch because it just 1967 wastes a cycle of execution time when the branch is taken. 1968 1969 Note that in the example "!C" will always be true. That is another 1970 possible improvement for handling COND_EXECs in this scheduler: it 1971 could remove always-true predicates. */ 1972 1973 if (!reload_completed || ! JUMP_P (tail)) 1974 return; 1975 1976 insn = tail; 1977 while (insn != head) 1978 { 1979 insn = PREV_INSN (insn); 1980 1981 /* Note that we want to add this dependency even when 1982 sched_insns_conditions_mutex_p returns true. The whole point 1983 is that we _want_ this dependency, even if these insns really 1984 are independent. */ 1985 if (INSN_P (insn) && GET_CODE (PATTERN (insn)) == COND_EXEC) 1986 add_dependence (tail, insn, REG_DEP_ANTI); 1987 } 1988#endif 1989} 1990 1991/* Data structures for the computation of data dependences in a regions. We 1992 keep one `deps' structure for every basic block. Before analyzing the 1993 data dependences for a bb, its variables are initialized as a function of 1994 the variables of its predecessors. When the analysis for a bb completes, 1995 we save the contents to the corresponding bb_deps[bb] variable. */ 1996 1997static struct deps *bb_deps; 1998 1999/* Duplicate the INSN_LIST elements of COPY and prepend them to OLD. */ 2000 2001static rtx 2002concat_INSN_LIST (rtx copy, rtx old) 2003{ 2004 rtx new = old; 2005 for (; copy ; copy = XEXP (copy, 1)) 2006 new = alloc_INSN_LIST (XEXP (copy, 0), new); 2007 return new; 2008} 2009 2010static void 2011concat_insn_mem_list (rtx copy_insns, rtx copy_mems, rtx *old_insns_p, 2012 rtx *old_mems_p) 2013{ 2014 rtx new_insns = *old_insns_p; 2015 rtx new_mems = *old_mems_p; 2016 2017 while (copy_insns) 2018 { 2019 new_insns = alloc_INSN_LIST (XEXP (copy_insns, 0), new_insns); 2020 new_mems = alloc_EXPR_LIST (VOIDmode, XEXP (copy_mems, 0), new_mems); 2021 copy_insns = XEXP (copy_insns, 1); 2022 copy_mems = XEXP (copy_mems, 1); 2023 } 2024 2025 *old_insns_p = new_insns; 2026 *old_mems_p = new_mems; 2027} 2028 2029/* After computing the dependencies for block BB, propagate the dependencies 2030 found in TMP_DEPS to the successors of the block. */ 2031static void 2032propagate_deps (int bb, struct deps *pred_deps) 2033{ 2034 basic_block block = BASIC_BLOCK (BB_TO_BLOCK (bb)); 2035 edge_iterator ei; 2036 edge e; 2037 2038 /* bb's structures are inherited by its successors. */ 2039 FOR_EACH_EDGE (e, ei, block->succs) 2040 { 2041 struct deps *succ_deps; 2042 unsigned reg; 2043 reg_set_iterator rsi; 2044 2045 /* Only bbs "below" bb, in the same region, are interesting. */ 2046 if (e->dest == EXIT_BLOCK_PTR 2047 || CONTAINING_RGN (block->index) != CONTAINING_RGN (e->dest->index) 2048 || BLOCK_TO_BB (e->dest->index) <= bb) 2049 continue; 2050 2051 succ_deps = bb_deps + BLOCK_TO_BB (e->dest->index); 2052 2053 /* The reg_last lists are inherited by successor. */ 2054 EXECUTE_IF_SET_IN_REG_SET (&pred_deps->reg_last_in_use, 0, reg, rsi) 2055 { 2056 struct deps_reg *pred_rl = &pred_deps->reg_last[reg]; 2057 struct deps_reg *succ_rl = &succ_deps->reg_last[reg]; 2058 2059 succ_rl->uses = concat_INSN_LIST (pred_rl->uses, succ_rl->uses); 2060 succ_rl->sets = concat_INSN_LIST (pred_rl->sets, succ_rl->sets); 2061 succ_rl->clobbers = concat_INSN_LIST (pred_rl->clobbers, 2062 succ_rl->clobbers); 2063 succ_rl->uses_length += pred_rl->uses_length; 2064 succ_rl->clobbers_length += pred_rl->clobbers_length; 2065 } 2066 IOR_REG_SET (&succ_deps->reg_last_in_use, &pred_deps->reg_last_in_use); 2067 2068 /* Mem read/write lists are inherited by successor. */ 2069 concat_insn_mem_list (pred_deps->pending_read_insns, 2070 pred_deps->pending_read_mems, 2071 &succ_deps->pending_read_insns, 2072 &succ_deps->pending_read_mems); 2073 concat_insn_mem_list (pred_deps->pending_write_insns, 2074 pred_deps->pending_write_mems, 2075 &succ_deps->pending_write_insns, 2076 &succ_deps->pending_write_mems); 2077 2078 succ_deps->last_pending_memory_flush 2079 = concat_INSN_LIST (pred_deps->last_pending_memory_flush, 2080 succ_deps->last_pending_memory_flush); 2081 2082 succ_deps->pending_lists_length += pred_deps->pending_lists_length; 2083 succ_deps->pending_flush_length += pred_deps->pending_flush_length; 2084 2085 /* last_function_call is inherited by successor. */ 2086 succ_deps->last_function_call 2087 = concat_INSN_LIST (pred_deps->last_function_call, 2088 succ_deps->last_function_call); 2089 2090 /* sched_before_next_call is inherited by successor. */ 2091 succ_deps->sched_before_next_call 2092 = concat_INSN_LIST (pred_deps->sched_before_next_call, 2093 succ_deps->sched_before_next_call); 2094 } 2095 2096 /* These lists should point to the right place, for correct 2097 freeing later. */ 2098 bb_deps[bb].pending_read_insns = pred_deps->pending_read_insns; 2099 bb_deps[bb].pending_read_mems = pred_deps->pending_read_mems; 2100 bb_deps[bb].pending_write_insns = pred_deps->pending_write_insns; 2101 bb_deps[bb].pending_write_mems = pred_deps->pending_write_mems; 2102 2103 /* Can't allow these to be freed twice. */ 2104 pred_deps->pending_read_insns = 0; 2105 pred_deps->pending_read_mems = 0; 2106 pred_deps->pending_write_insns = 0; 2107 pred_deps->pending_write_mems = 0; 2108} 2109 2110/* Compute backward dependences inside bb. In a multiple blocks region: 2111 (1) a bb is analyzed after its predecessors, and (2) the lists in 2112 effect at the end of bb (after analyzing for bb) are inherited by 2113 bb's successors. 2114 2115 Specifically for reg-reg data dependences, the block insns are 2116 scanned by sched_analyze () top-to-bottom. Two lists are 2117 maintained by sched_analyze (): reg_last[].sets for register DEFs, 2118 and reg_last[].uses for register USEs. 2119 2120 When analysis is completed for bb, we update for its successors: 2121 ; - DEFS[succ] = Union (DEFS [succ], DEFS [bb]) 2122 ; - USES[succ] = Union (USES [succ], DEFS [bb]) 2123 2124 The mechanism for computing mem-mem data dependence is very 2125 similar, and the result is interblock dependences in the region. */ 2126 2127static void 2128compute_block_backward_dependences (int bb) 2129{ 2130 rtx head, tail; 2131 struct deps tmp_deps; 2132 2133 tmp_deps = bb_deps[bb]; 2134 2135 /* Do the analysis for this block. */ 2136 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail); 2137 sched_analyze (&tmp_deps, head, tail); 2138 add_branch_dependences (head, tail); 2139 2140 if (current_nr_blocks > 1) 2141 propagate_deps (bb, &tmp_deps); 2142 2143 /* Free up the INSN_LISTs. */ 2144 free_deps (&tmp_deps); 2145} 2146 2147/* Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add 2148 them to the unused_*_list variables, so that they can be reused. */ 2149 2150static void 2151free_pending_lists (void) 2152{ 2153 int bb; 2154 2155 for (bb = 0; bb < current_nr_blocks; bb++) 2156 { 2157 free_INSN_LIST_list (&bb_deps[bb].pending_read_insns); 2158 free_INSN_LIST_list (&bb_deps[bb].pending_write_insns); 2159 free_EXPR_LIST_list (&bb_deps[bb].pending_read_mems); 2160 free_EXPR_LIST_list (&bb_deps[bb].pending_write_mems); 2161 } 2162} 2163 2164/* Print dependences for debugging, callable from debugger. */ 2165 2166void 2167debug_dependencies (void) 2168{ 2169 int bb; 2170 2171 fprintf (sched_dump, ";; --------------- forward dependences: ------------ \n"); 2172 for (bb = 0; bb < current_nr_blocks; bb++) 2173 { 2174 rtx head, tail; 2175 rtx next_tail; 2176 rtx insn; 2177 2178 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail); 2179 next_tail = NEXT_INSN (tail); 2180 fprintf (sched_dump, "\n;; --- Region Dependences --- b %d bb %d \n", 2181 BB_TO_BLOCK (bb), bb); 2182 2183 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n", 2184 "insn", "code", "bb", "dep", "prio", "cost", 2185 "reservation"); 2186 fprintf (sched_dump, ";; %7s%6s%6s%6s%6s%6s%14s\n", 2187 "----", "----", "--", "---", "----", "----", 2188 "-----------"); 2189 2190 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 2191 { 2192 rtx link; 2193 2194 if (! INSN_P (insn)) 2195 { 2196 int n; 2197 fprintf (sched_dump, ";; %6d ", INSN_UID (insn)); 2198 if (NOTE_P (insn)) 2199 { 2200 n = NOTE_LINE_NUMBER (insn); 2201 if (n < 0) 2202 fprintf (sched_dump, "%s\n", GET_NOTE_INSN_NAME (n)); 2203 else 2204 { 2205 expanded_location xloc; 2206 NOTE_EXPANDED_LOCATION (xloc, insn); 2207 fprintf (sched_dump, "line %d, file %s\n", 2208 xloc.line, xloc.file); 2209 } 2210 } 2211 else 2212 fprintf (sched_dump, " {%s}\n", GET_RTX_NAME (GET_CODE (insn))); 2213 continue; 2214 } 2215 2216 fprintf (sched_dump, 2217 ";; %s%5d%6d%6d%6d%6d%6d ", 2218 (SCHED_GROUP_P (insn) ? "+" : " "), 2219 INSN_UID (insn), 2220 INSN_CODE (insn), 2221 INSN_BB (insn), 2222 INSN_DEP_COUNT (insn), 2223 INSN_PRIORITY (insn), 2224 insn_cost (insn, 0, 0)); 2225 2226 if (recog_memoized (insn) < 0) 2227 fprintf (sched_dump, "nothing"); 2228 else 2229 print_reservation (sched_dump, insn); 2230 2231 fprintf (sched_dump, "\t: "); 2232 for (link = INSN_DEPEND (insn); link; link = XEXP (link, 1)) 2233 fprintf (sched_dump, "%d ", INSN_UID (XEXP (link, 0))); 2234 fprintf (sched_dump, "\n"); 2235 } 2236 } 2237 fprintf (sched_dump, "\n"); 2238} 2239 2240/* Returns true if all the basic blocks of the current region have 2241 NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region. */ 2242static bool 2243sched_is_disabled_for_current_region_p (void) 2244{ 2245 int bb; 2246 2247 for (bb = 0; bb < current_nr_blocks; bb++) 2248 if (!(BASIC_BLOCK (BB_TO_BLOCK (bb))->flags & BB_DISABLE_SCHEDULE)) 2249 return false; 2250 2251 return true; 2252} 2253 2254/* Schedule a region. A region is either an inner loop, a loop-free 2255 subroutine, or a single basic block. Each bb in the region is 2256 scheduled after its flow predecessors. */ 2257 2258static void 2259schedule_region (int rgn) 2260{ 2261 basic_block block; 2262 edge_iterator ei; 2263 edge e; 2264 int bb; 2265 int rgn_n_insns = 0; 2266 int sched_rgn_n_insns = 0; 2267 2268 /* Set variables for the current region. */ 2269 current_nr_blocks = RGN_NR_BLOCKS (rgn); 2270 current_blocks = RGN_BLOCKS (rgn); 2271 2272 /* Don't schedule region that is marked by 2273 NOTE_DISABLE_SCHED_OF_BLOCK. */ 2274 if (sched_is_disabled_for_current_region_p ()) 2275 return; 2276 2277 init_deps_global (); 2278 2279 /* Initializations for region data dependence analysis. */ 2280 bb_deps = xmalloc (sizeof (struct deps) * current_nr_blocks); 2281 for (bb = 0; bb < current_nr_blocks; bb++) 2282 init_deps (bb_deps + bb); 2283 2284 /* Compute LOG_LINKS. */ 2285 for (bb = 0; bb < current_nr_blocks; bb++) 2286 compute_block_backward_dependences (bb); 2287 2288 /* Compute INSN_DEPEND. */ 2289 for (bb = current_nr_blocks - 1; bb >= 0; bb--) 2290 { 2291 rtx head, tail; 2292 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail); 2293 2294 compute_forward_dependences (head, tail); 2295 2296 if (targetm.sched.dependencies_evaluation_hook) 2297 targetm.sched.dependencies_evaluation_hook (head, tail); 2298 2299 } 2300 2301 /* Set priorities. */ 2302 for (bb = 0; bb < current_nr_blocks; bb++) 2303 { 2304 rtx head, tail; 2305 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail); 2306 2307 rgn_n_insns += set_priorities (head, tail); 2308 } 2309 2310 /* Compute interblock info: probabilities, split-edges, dominators, etc. */ 2311 if (current_nr_blocks > 1) 2312 { 2313 prob = xmalloc ((current_nr_blocks) * sizeof (float)); 2314 2315 dom = sbitmap_vector_alloc (current_nr_blocks, current_nr_blocks); 2316 sbitmap_vector_zero (dom, current_nr_blocks); 2317 2318 /* Use ->aux to implement EDGE_TO_BIT mapping. */ 2319 rgn_nr_edges = 0; 2320 FOR_EACH_BB (block) 2321 { 2322 if (CONTAINING_RGN (block->index) != rgn) 2323 continue; 2324 FOR_EACH_EDGE (e, ei, block->succs) 2325 SET_EDGE_TO_BIT (e, rgn_nr_edges++); 2326 } 2327 2328 rgn_edges = xmalloc (rgn_nr_edges * sizeof (edge)); 2329 rgn_nr_edges = 0; 2330 FOR_EACH_BB (block) 2331 { 2332 if (CONTAINING_RGN (block->index) != rgn) 2333 continue; 2334 FOR_EACH_EDGE (e, ei, block->succs) 2335 rgn_edges[rgn_nr_edges++] = e; 2336 } 2337 2338 /* Split edges. */ 2339 pot_split = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges); 2340 sbitmap_vector_zero (pot_split, current_nr_blocks); 2341 ancestor_edges = sbitmap_vector_alloc (current_nr_blocks, rgn_nr_edges); 2342 sbitmap_vector_zero (ancestor_edges, current_nr_blocks); 2343 2344 /* Compute probabilities, dominators, split_edges. */ 2345 for (bb = 0; bb < current_nr_blocks; bb++) 2346 compute_dom_prob_ps (bb); 2347 } 2348 2349 /* Now we can schedule all blocks. */ 2350 for (bb = 0; bb < current_nr_blocks; bb++) 2351 { 2352 rtx head, tail; 2353 int b = BB_TO_BLOCK (bb); 2354 2355 get_block_head_tail (b, &head, &tail); 2356 2357 if (no_real_insns_p (head, tail)) 2358 continue; 2359 2360 current_sched_info->prev_head = PREV_INSN (head); 2361 current_sched_info->next_tail = NEXT_INSN (tail); 2362 2363 if (write_symbols != NO_DEBUG) 2364 { 2365 save_line_notes (b, head, tail); 2366 rm_line_notes (head, tail); 2367 } 2368 2369 /* rm_other_notes only removes notes which are _inside_ the 2370 block---that is, it won't remove notes before the first real insn 2371 or after the last real insn of the block. So if the first insn 2372 has a REG_SAVE_NOTE which would otherwise be emitted before the 2373 insn, it is redundant with the note before the start of the 2374 block, and so we have to take it out. */ 2375 if (INSN_P (head)) 2376 { 2377 rtx note; 2378 2379 for (note = REG_NOTES (head); note; note = XEXP (note, 1)) 2380 if (REG_NOTE_KIND (note) == REG_SAVE_NOTE) 2381 remove_note (head, note); 2382 } 2383 2384 /* Remove remaining note insns from the block, save them in 2385 note_list. These notes are restored at the end of 2386 schedule_block (). */ 2387 rm_other_notes (head, tail); 2388 2389 target_bb = bb; 2390 2391 current_sched_info->queue_must_finish_empty 2392 = current_nr_blocks > 1 && !flag_schedule_interblock; 2393 2394 schedule_block (b, rgn_n_insns); 2395 sched_rgn_n_insns += sched_n_insns; 2396 2397 /* Update target block boundaries. */ 2398 if (head == BB_HEAD (BASIC_BLOCK (b))) 2399 BB_HEAD (BASIC_BLOCK (b)) = current_sched_info->head; 2400 if (tail == BB_END (BASIC_BLOCK (b))) 2401 BB_END (BASIC_BLOCK (b)) = current_sched_info->tail; 2402 2403 /* Clean up. */ 2404 if (current_nr_blocks > 1) 2405 { 2406 free (candidate_table); 2407 free (bblst_table); 2408 free (edgelst_table); 2409 } 2410 } 2411 2412 /* Sanity check: verify that all region insns were scheduled. */ 2413 gcc_assert (sched_rgn_n_insns == rgn_n_insns); 2414 2415 /* Restore line notes. */ 2416 if (write_symbols != NO_DEBUG) 2417 { 2418 for (bb = 0; bb < current_nr_blocks; bb++) 2419 { 2420 rtx head, tail; 2421 get_block_head_tail (BB_TO_BLOCK (bb), &head, &tail); 2422 restore_line_notes (head, tail); 2423 } 2424 } 2425 2426 /* Done with this region. */ 2427 free_pending_lists (); 2428 2429 finish_deps_global (); 2430 2431 free (bb_deps); 2432 2433 if (current_nr_blocks > 1) 2434 { 2435 /* Cleanup ->aux used for EDGE_TO_BIT mapping. */ 2436 FOR_EACH_BB (block) 2437 { 2438 if (CONTAINING_RGN (block->index) != rgn) 2439 continue; 2440 FOR_EACH_EDGE (e, ei, block->succs) 2441 e->aux = NULL; 2442 } 2443 2444 free (prob); 2445 sbitmap_vector_free (dom); 2446 sbitmap_vector_free (pot_split); 2447 sbitmap_vector_free (ancestor_edges); 2448 free (rgn_edges); 2449 } 2450} 2451 2452/* Indexed by region, holds the number of death notes found in that region. 2453 Used for consistency checks. */ 2454static int *deaths_in_region; 2455 2456/* Initialize data structures for region scheduling. */ 2457 2458static void 2459init_regions (void) 2460{ 2461 sbitmap blocks; 2462 int rgn; 2463 2464 nr_regions = 0; 2465 rgn_table = xmalloc ((n_basic_blocks) * sizeof (region)); 2466 rgn_bb_table = xmalloc ((n_basic_blocks) * sizeof (int)); 2467 block_to_bb = xmalloc ((last_basic_block) * sizeof (int)); 2468 containing_rgn = xmalloc ((last_basic_block) * sizeof (int)); 2469 2470 /* Compute regions for scheduling. */ 2471 if (reload_completed 2472 || n_basic_blocks == 1 2473 || !flag_schedule_interblock 2474 || is_cfg_nonregular ()) 2475 { 2476 find_single_block_region (); 2477 } 2478 else 2479 { 2480 /* Compute the dominators and post dominators. */ 2481 calculate_dominance_info (CDI_DOMINATORS); 2482 2483 /* Find regions. */ 2484 find_rgns (); 2485 2486 if (sched_verbose >= 3) 2487 debug_regions (); 2488 2489 /* For now. This will move as more and more of haifa is converted 2490 to using the cfg code in flow.c. */ 2491 free_dominance_info (CDI_DOMINATORS); 2492 } 2493 2494 2495 if (CHECK_DEAD_NOTES) 2496 { 2497 blocks = sbitmap_alloc (last_basic_block); 2498 deaths_in_region = xmalloc (sizeof (int) * nr_regions); 2499 /* Remove all death notes from the subroutine. */ 2500 for (rgn = 0; rgn < nr_regions; rgn++) 2501 { 2502 int b; 2503 2504 sbitmap_zero (blocks); 2505 for (b = RGN_NR_BLOCKS (rgn) - 1; b >= 0; --b) 2506 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn) + b]); 2507 2508 deaths_in_region[rgn] = count_or_remove_death_notes (blocks, 1); 2509 } 2510 sbitmap_free (blocks); 2511 } 2512 else 2513 count_or_remove_death_notes (NULL, 1); 2514} 2515 2516/* The one entry point in this file. DUMP_FILE is the dump file for 2517 this pass. */ 2518 2519void 2520schedule_insns (FILE *dump_file) 2521{ 2522 sbitmap large_region_blocks, blocks; 2523 int rgn; 2524 int any_large_regions; 2525 basic_block bb; 2526 2527 /* Taking care of this degenerate case makes the rest of 2528 this code simpler. */ 2529 if (n_basic_blocks == 0) 2530 return; 2531 2532 nr_inter = 0; 2533 nr_spec = 0; 2534 2535 sched_init (dump_file); 2536 2537 init_regions (); 2538 2539 current_sched_info = ®ion_sched_info; 2540 2541 /* Schedule every region in the subroutine. */ 2542 for (rgn = 0; rgn < nr_regions; rgn++) 2543 schedule_region (rgn); 2544 2545 /* Update life analysis for the subroutine. Do single block regions 2546 first so that we can verify that live_at_start didn't change. Then 2547 do all other blocks. */ 2548 /* ??? There is an outside possibility that update_life_info, or more 2549 to the point propagate_block, could get called with nonzero flags 2550 more than once for one basic block. This would be kinda bad if it 2551 were to happen, since REG_INFO would be accumulated twice for the 2552 block, and we'd have twice the REG_DEAD notes. 2553 2554 I'm fairly certain that this _shouldn't_ happen, since I don't think 2555 that live_at_start should change at region heads. Not sure what the 2556 best way to test for this kind of thing... */ 2557 2558 allocate_reg_life_data (); 2559 compute_bb_for_insn (); 2560 2561 any_large_regions = 0; 2562 large_region_blocks = sbitmap_alloc (last_basic_block); 2563 sbitmap_zero (large_region_blocks); 2564 FOR_EACH_BB (bb) 2565 SET_BIT (large_region_blocks, bb->index); 2566 2567 blocks = sbitmap_alloc (last_basic_block); 2568 sbitmap_zero (blocks); 2569 2570 /* Update life information. For regions consisting of multiple blocks 2571 we've possibly done interblock scheduling that affects global liveness. 2572 For regions consisting of single blocks we need to do only local 2573 liveness. */ 2574 for (rgn = 0; rgn < nr_regions; rgn++) 2575 if (RGN_NR_BLOCKS (rgn) > 1) 2576 any_large_regions = 1; 2577 else 2578 { 2579 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 2580 RESET_BIT (large_region_blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 2581 } 2582 2583 /* Don't update reg info after reload, since that affects 2584 regs_ever_live, which should not change after reload. */ 2585 update_life_info (blocks, UPDATE_LIFE_LOCAL, 2586 (reload_completed ? PROP_DEATH_NOTES 2587 : PROP_DEATH_NOTES | PROP_REG_INFO)); 2588 if (any_large_regions) 2589 { 2590 update_life_info (large_region_blocks, UPDATE_LIFE_GLOBAL, 2591 PROP_DEATH_NOTES | PROP_REG_INFO); 2592 } 2593 2594 if (CHECK_DEAD_NOTES) 2595 { 2596 /* Verify the counts of basic block notes in single the basic block 2597 regions. */ 2598 for (rgn = 0; rgn < nr_regions; rgn++) 2599 if (RGN_NR_BLOCKS (rgn) == 1) 2600 { 2601 sbitmap_zero (blocks); 2602 SET_BIT (blocks, rgn_bb_table[RGN_BLOCKS (rgn)]); 2603 2604 gcc_assert (deaths_in_region[rgn] 2605 == count_or_remove_death_notes (blocks, 0)); 2606 } 2607 free (deaths_in_region); 2608 } 2609 2610 /* Reposition the prologue and epilogue notes in case we moved the 2611 prologue/epilogue insns. */ 2612 if (reload_completed) 2613 reposition_prologue_and_epilogue_notes (get_insns ()); 2614 2615 /* Delete redundant line notes. */ 2616 if (write_symbols != NO_DEBUG) 2617 rm_redundant_line_notes (); 2618 2619 if (sched_verbose) 2620 { 2621 if (reload_completed == 0 && flag_schedule_interblock) 2622 { 2623 fprintf (sched_dump, 2624 "\n;; Procedure interblock/speculative motions == %d/%d \n", 2625 nr_inter, nr_spec); 2626 } 2627 else 2628 gcc_assert (nr_inter <= 0); 2629 fprintf (sched_dump, "\n\n"); 2630 } 2631 2632 /* Clean up. */ 2633 free (rgn_table); 2634 free (rgn_bb_table); 2635 free (block_to_bb); 2636 free (containing_rgn); 2637 2638 sched_finish (); 2639 2640 sbitmap_free (blocks); 2641 sbitmap_free (large_region_blocks); 2642} 2643#endif 2644 2645static bool 2646gate_handle_sched (void) 2647{ 2648#ifdef INSN_SCHEDULING 2649 return flag_schedule_insns; 2650#else 2651 return 0; 2652#endif 2653} 2654 2655/* Run instruction scheduler. */ 2656static void 2657rest_of_handle_sched (void) 2658{ 2659#ifdef INSN_SCHEDULING 2660 /* Do control and data sched analysis, 2661 and write some of the results to dump file. */ 2662 2663 schedule_insns (dump_file); 2664#endif 2665} 2666 2667static bool 2668gate_handle_sched2 (void) 2669{ 2670#ifdef INSN_SCHEDULING 2671 return optimize > 0 && flag_schedule_insns_after_reload; 2672#else 2673 return 0; 2674#endif 2675} 2676 2677/* Run second scheduling pass after reload. */ 2678static void 2679rest_of_handle_sched2 (void) 2680{ 2681#ifdef INSN_SCHEDULING 2682 /* Do control and data sched analysis again, 2683 and write some more of the results to dump file. */ 2684 2685 split_all_insns (1); 2686 2687 if (flag_sched2_use_superblocks || flag_sched2_use_traces) 2688 { 2689 schedule_ebbs (dump_file); 2690 /* No liveness updating code yet, but it should be easy to do. 2691 reg-stack recomputes the liveness when needed for now. */ 2692 count_or_remove_death_notes (NULL, 1); 2693 cleanup_cfg (CLEANUP_EXPENSIVE); 2694 } 2695 else 2696 schedule_insns (dump_file); 2697#endif 2698} 2699 2700struct tree_opt_pass pass_sched = 2701{ 2702 "sched1", /* name */ 2703 gate_handle_sched, /* gate */ 2704 rest_of_handle_sched, /* execute */ 2705 NULL, /* sub */ 2706 NULL, /* next */ 2707 0, /* static_pass_number */ 2708 TV_SCHED, /* tv_id */ 2709 0, /* properties_required */ 2710 0, /* properties_provided */ 2711 0, /* properties_destroyed */ 2712 0, /* todo_flags_start */ 2713 TODO_dump_func | 2714 TODO_ggc_collect, /* todo_flags_finish */ 2715 'S' /* letter */ 2716}; 2717 2718struct tree_opt_pass pass_sched2 = 2719{ 2720 "sched2", /* name */ 2721 gate_handle_sched2, /* gate */ 2722 rest_of_handle_sched2, /* execute */ 2723 NULL, /* sub */ 2724 NULL, /* next */ 2725 0, /* static_pass_number */ 2726 TV_SCHED2, /* tv_id */ 2727 0, /* properties_required */ 2728 0, /* properties_provided */ 2729 0, /* properties_destroyed */ 2730 0, /* todo_flags_start */ 2731 TODO_dump_func | 2732 TODO_ggc_collect, /* todo_flags_finish */ 2733 'R' /* letter */ 2734}; 2735 2736