1/* Instruction scheduling pass. This file computes dependencies between 2 instructions. 3 Copyright (C) 1992-2020 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 3, 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 COPYING3. If not see 21<http://www.gnu.org/licenses/>. */ 22 23#include "config.h" 24#include "system.h" 25#include "coretypes.h" 26#include "backend.h" 27#include "target.h" 28#include "rtl.h" 29#include "tree.h" 30#include "df.h" 31#include "insn-config.h" 32#include "regs.h" 33#include "memmodel.h" 34#include "ira.h" 35#include "ira-int.h" 36#include "insn-attr.h" 37#include "cfgbuild.h" 38#include "sched-int.h" 39#include "cselib.h" 40#include "function-abi.h" 41 42#ifdef INSN_SCHEDULING 43 44/* Holds current parameters for the dependency analyzer. */ 45struct sched_deps_info_def *sched_deps_info; 46 47/* The data is specific to the Haifa scheduler. */ 48vec<haifa_deps_insn_data_def> 49 h_d_i_d = vNULL; 50 51/* Return the major type present in the DS. */ 52enum reg_note 53ds_to_dk (ds_t ds) 54{ 55 if (ds & DEP_TRUE) 56 return REG_DEP_TRUE; 57 58 if (ds & DEP_OUTPUT) 59 return REG_DEP_OUTPUT; 60 61 if (ds & DEP_CONTROL) 62 return REG_DEP_CONTROL; 63 64 gcc_assert (ds & DEP_ANTI); 65 66 return REG_DEP_ANTI; 67} 68 69/* Return equivalent dep_status. */ 70ds_t 71dk_to_ds (enum reg_note dk) 72{ 73 switch (dk) 74 { 75 case REG_DEP_TRUE: 76 return DEP_TRUE; 77 78 case REG_DEP_OUTPUT: 79 return DEP_OUTPUT; 80 81 case REG_DEP_CONTROL: 82 return DEP_CONTROL; 83 84 default: 85 gcc_assert (dk == REG_DEP_ANTI); 86 return DEP_ANTI; 87 } 88} 89 90/* Functions to operate with dependence information container - dep_t. */ 91 92/* Init DEP with the arguments. */ 93void 94init_dep_1 (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note type, ds_t ds) 95{ 96 DEP_PRO (dep) = pro; 97 DEP_CON (dep) = con; 98 DEP_TYPE (dep) = type; 99 DEP_STATUS (dep) = ds; 100 DEP_COST (dep) = UNKNOWN_DEP_COST; 101 DEP_NONREG (dep) = 0; 102 DEP_MULTIPLE (dep) = 0; 103 DEP_REPLACE (dep) = NULL; 104 dep->unused = 0; 105} 106 107/* Init DEP with the arguments. 108 While most of the scheduler (including targets) only need the major type 109 of the dependency, it is convenient to hide full dep_status from them. */ 110void 111init_dep (dep_t dep, rtx_insn *pro, rtx_insn *con, enum reg_note kind) 112{ 113 ds_t ds; 114 115 if ((current_sched_info->flags & USE_DEPS_LIST)) 116 ds = dk_to_ds (kind); 117 else 118 ds = 0; 119 120 init_dep_1 (dep, pro, con, kind, ds); 121} 122 123/* Make a copy of FROM in TO. */ 124static void 125copy_dep (dep_t to, dep_t from) 126{ 127 memcpy (to, from, sizeof (*to)); 128} 129 130static void dump_ds (FILE *, ds_t); 131 132/* Define flags for dump_dep (). */ 133 134/* Dump producer of the dependence. */ 135#define DUMP_DEP_PRO (2) 136 137/* Dump consumer of the dependence. */ 138#define DUMP_DEP_CON (4) 139 140/* Dump type of the dependence. */ 141#define DUMP_DEP_TYPE (8) 142 143/* Dump status of the dependence. */ 144#define DUMP_DEP_STATUS (16) 145 146/* Dump all information about the dependence. */ 147#define DUMP_DEP_ALL (DUMP_DEP_PRO | DUMP_DEP_CON | DUMP_DEP_TYPE \ 148 |DUMP_DEP_STATUS) 149 150/* Dump DEP to DUMP. 151 FLAGS is a bit mask specifying what information about DEP needs 152 to be printed. 153 If FLAGS has the very first bit set, then dump all information about DEP 154 and propagate this bit into the callee dump functions. */ 155static void 156dump_dep (FILE *dump, dep_t dep, int flags) 157{ 158 if (flags & 1) 159 flags |= DUMP_DEP_ALL; 160 161 fprintf (dump, "<"); 162 163 if (flags & DUMP_DEP_PRO) 164 fprintf (dump, "%d; ", INSN_UID (DEP_PRO (dep))); 165 166 if (flags & DUMP_DEP_CON) 167 fprintf (dump, "%d; ", INSN_UID (DEP_CON (dep))); 168 169 if (flags & DUMP_DEP_TYPE) 170 { 171 char t; 172 enum reg_note type = DEP_TYPE (dep); 173 174 switch (type) 175 { 176 case REG_DEP_TRUE: 177 t = 't'; 178 break; 179 180 case REG_DEP_OUTPUT: 181 t = 'o'; 182 break; 183 184 case REG_DEP_CONTROL: 185 t = 'c'; 186 break; 187 188 case REG_DEP_ANTI: 189 t = 'a'; 190 break; 191 192 default: 193 gcc_unreachable (); 194 break; 195 } 196 197 fprintf (dump, "%c; ", t); 198 } 199 200 if (flags & DUMP_DEP_STATUS) 201 { 202 if (current_sched_info->flags & USE_DEPS_LIST) 203 dump_ds (dump, DEP_STATUS (dep)); 204 } 205 206 fprintf (dump, ">"); 207} 208 209/* Default flags for dump_dep (). */ 210static int dump_dep_flags = (DUMP_DEP_PRO | DUMP_DEP_CON); 211 212/* Dump all fields of DEP to STDERR. */ 213void 214sd_debug_dep (dep_t dep) 215{ 216 dump_dep (stderr, dep, 1); 217 fprintf (stderr, "\n"); 218} 219 220/* Determine whether DEP is a dependency link of a non-debug insn on a 221 debug insn. */ 222 223static inline bool 224depl_on_debug_p (dep_link_t dep) 225{ 226 return (DEBUG_INSN_P (DEP_LINK_PRO (dep)) 227 && !DEBUG_INSN_P (DEP_LINK_CON (dep))); 228} 229 230/* Functions to operate with a single link from the dependencies lists - 231 dep_link_t. */ 232 233/* Attach L to appear after link X whose &DEP_LINK_NEXT (X) is given by 234 PREV_NEXT_P. */ 235static void 236attach_dep_link (dep_link_t l, dep_link_t *prev_nextp) 237{ 238 dep_link_t next = *prev_nextp; 239 240 gcc_assert (DEP_LINK_PREV_NEXTP (l) == NULL 241 && DEP_LINK_NEXT (l) == NULL); 242 243 /* Init node being inserted. */ 244 DEP_LINK_PREV_NEXTP (l) = prev_nextp; 245 DEP_LINK_NEXT (l) = next; 246 247 /* Fix next node. */ 248 if (next != NULL) 249 { 250 gcc_assert (DEP_LINK_PREV_NEXTP (next) == prev_nextp); 251 252 DEP_LINK_PREV_NEXTP (next) = &DEP_LINK_NEXT (l); 253 } 254 255 /* Fix prev node. */ 256 *prev_nextp = l; 257} 258 259/* Add dep_link LINK to deps_list L. */ 260static void 261add_to_deps_list (dep_link_t link, deps_list_t l) 262{ 263 attach_dep_link (link, &DEPS_LIST_FIRST (l)); 264 265 /* Don't count debug deps. */ 266 if (!depl_on_debug_p (link)) 267 ++DEPS_LIST_N_LINKS (l); 268} 269 270/* Detach dep_link L from the list. */ 271static void 272detach_dep_link (dep_link_t l) 273{ 274 dep_link_t *prev_nextp = DEP_LINK_PREV_NEXTP (l); 275 dep_link_t next = DEP_LINK_NEXT (l); 276 277 *prev_nextp = next; 278 279 if (next != NULL) 280 DEP_LINK_PREV_NEXTP (next) = prev_nextp; 281 282 DEP_LINK_PREV_NEXTP (l) = NULL; 283 DEP_LINK_NEXT (l) = NULL; 284} 285 286/* Remove link LINK from list LIST. */ 287static void 288remove_from_deps_list (dep_link_t link, deps_list_t list) 289{ 290 detach_dep_link (link); 291 292 /* Don't count debug deps. */ 293 if (!depl_on_debug_p (link)) 294 --DEPS_LIST_N_LINKS (list); 295} 296 297/* Move link LINK from list FROM to list TO. */ 298static void 299move_dep_link (dep_link_t link, deps_list_t from, deps_list_t to) 300{ 301 remove_from_deps_list (link, from); 302 add_to_deps_list (link, to); 303} 304 305/* Return true of LINK is not attached to any list. */ 306static bool 307dep_link_is_detached_p (dep_link_t link) 308{ 309 return DEP_LINK_PREV_NEXTP (link) == NULL; 310} 311 312/* Pool to hold all dependency nodes (dep_node_t). */ 313static object_allocator<_dep_node> *dn_pool; 314 315/* Number of dep_nodes out there. */ 316static int dn_pool_diff = 0; 317 318/* Create a dep_node. */ 319static dep_node_t 320create_dep_node (void) 321{ 322 dep_node_t n = dn_pool->allocate (); 323 dep_link_t back = DEP_NODE_BACK (n); 324 dep_link_t forw = DEP_NODE_FORW (n); 325 326 DEP_LINK_NODE (back) = n; 327 DEP_LINK_NEXT (back) = NULL; 328 DEP_LINK_PREV_NEXTP (back) = NULL; 329 330 DEP_LINK_NODE (forw) = n; 331 DEP_LINK_NEXT (forw) = NULL; 332 DEP_LINK_PREV_NEXTP (forw) = NULL; 333 334 ++dn_pool_diff; 335 336 return n; 337} 338 339/* Delete dep_node N. N must not be connected to any deps_list. */ 340static void 341delete_dep_node (dep_node_t n) 342{ 343 gcc_assert (dep_link_is_detached_p (DEP_NODE_BACK (n)) 344 && dep_link_is_detached_p (DEP_NODE_FORW (n))); 345 346 XDELETE (DEP_REPLACE (DEP_NODE_DEP (n))); 347 348 --dn_pool_diff; 349 350 dn_pool->remove (n); 351} 352 353/* Pool to hold dependencies lists (deps_list_t). */ 354static object_allocator<_deps_list> *dl_pool; 355 356/* Number of deps_lists out there. */ 357static int dl_pool_diff = 0; 358 359/* Functions to operate with dependences lists - deps_list_t. */ 360 361/* Return true if list L is empty. */ 362static bool 363deps_list_empty_p (deps_list_t l) 364{ 365 return DEPS_LIST_N_LINKS (l) == 0; 366} 367 368/* Create a new deps_list. */ 369static deps_list_t 370create_deps_list (void) 371{ 372 deps_list_t l = dl_pool->allocate (); 373 374 DEPS_LIST_FIRST (l) = NULL; 375 DEPS_LIST_N_LINKS (l) = 0; 376 377 ++dl_pool_diff; 378 return l; 379} 380 381/* Free deps_list L. */ 382static void 383free_deps_list (deps_list_t l) 384{ 385 gcc_assert (deps_list_empty_p (l)); 386 387 --dl_pool_diff; 388 389 dl_pool->remove (l); 390} 391 392/* Return true if there is no dep_nodes and deps_lists out there. 393 After the region is scheduled all the dependency nodes and lists 394 should [generally] be returned to pool. */ 395bool 396deps_pools_are_empty_p (void) 397{ 398 return dn_pool_diff == 0 && dl_pool_diff == 0; 399} 400 401/* Remove all elements from L. */ 402static void 403clear_deps_list (deps_list_t l) 404{ 405 do 406 { 407 dep_link_t link = DEPS_LIST_FIRST (l); 408 409 if (link == NULL) 410 break; 411 412 remove_from_deps_list (link, l); 413 } 414 while (1); 415} 416 417/* Decide whether a dependency should be treated as a hard or a speculative 418 dependency. */ 419static bool 420dep_spec_p (dep_t dep) 421{ 422 if (current_sched_info->flags & DO_SPECULATION) 423 { 424 if (DEP_STATUS (dep) & SPECULATIVE) 425 return true; 426 } 427 if (current_sched_info->flags & DO_PREDICATION) 428 { 429 if (DEP_TYPE (dep) == REG_DEP_CONTROL) 430 return true; 431 } 432 if (DEP_REPLACE (dep) != NULL) 433 return true; 434 return false; 435} 436 437static regset reg_pending_sets; 438static regset reg_pending_clobbers; 439static regset reg_pending_uses; 440static regset reg_pending_control_uses; 441static enum reg_pending_barrier_mode reg_pending_barrier; 442 443/* Hard registers implicitly clobbered or used (or may be implicitly 444 clobbered or used) by the currently analyzed insn. For example, 445 insn in its constraint has one register class. Even if there is 446 currently no hard register in the insn, the particular hard 447 register will be in the insn after reload pass because the 448 constraint requires it. */ 449static HARD_REG_SET implicit_reg_pending_clobbers; 450static HARD_REG_SET implicit_reg_pending_uses; 451 452/* To speed up the test for duplicate dependency links we keep a 453 record of dependencies created by add_dependence when the average 454 number of instructions in a basic block is very large. 455 456 Studies have shown that there is typically around 5 instructions between 457 branches for typical C code. So we can make a guess that the average 458 basic block is approximately 5 instructions long; we will choose 100X 459 the average size as a very large basic block. 460 461 Each insn has associated bitmaps for its dependencies. Each bitmap 462 has enough entries to represent a dependency on any other insn in 463 the insn chain. All bitmap for true dependencies cache is 464 allocated then the rest two ones are also allocated. */ 465static bitmap true_dependency_cache = NULL; 466static bitmap output_dependency_cache = NULL; 467static bitmap anti_dependency_cache = NULL; 468static bitmap control_dependency_cache = NULL; 469static bitmap spec_dependency_cache = NULL; 470static int cache_size; 471 472/* True if we should mark added dependencies as a non-register deps. */ 473static bool mark_as_hard; 474 475static int deps_may_trap_p (const_rtx); 476static void add_dependence_1 (rtx_insn *, rtx_insn *, enum reg_note); 477static void add_dependence_list (rtx_insn *, rtx_insn_list *, int, 478 enum reg_note, bool); 479static void add_dependence_list_and_free (class deps_desc *, rtx_insn *, 480 rtx_insn_list **, int, enum reg_note, 481 bool); 482static void delete_all_dependences (rtx_insn *); 483static void chain_to_prev_insn (rtx_insn *); 484 485static void flush_pending_lists (class deps_desc *, rtx_insn *, int, int); 486static void sched_analyze_1 (class deps_desc *, rtx, rtx_insn *); 487static void sched_analyze_2 (class deps_desc *, rtx, rtx_insn *); 488static void sched_analyze_insn (class deps_desc *, rtx, rtx_insn *); 489 490static bool sched_has_condition_p (const rtx_insn *); 491static int conditions_mutex_p (const_rtx, const_rtx, bool, bool); 492 493static enum DEPS_ADJUST_RESULT maybe_add_or_update_dep_1 (dep_t, bool, 494 rtx, rtx); 495static enum DEPS_ADJUST_RESULT add_or_update_dep_1 (dep_t, bool, rtx, rtx); 496 497static void check_dep (dep_t, bool); 498 499 500/* Return nonzero if a load of the memory reference MEM can cause a trap. */ 501 502static int 503deps_may_trap_p (const_rtx mem) 504{ 505 const_rtx addr = XEXP (mem, 0); 506 507 if (REG_P (addr) && REGNO (addr) >= FIRST_PSEUDO_REGISTER) 508 { 509 const_rtx t = get_reg_known_value (REGNO (addr)); 510 if (t) 511 addr = t; 512 } 513 return rtx_addr_can_trap_p (addr); 514} 515 516 517/* Find the condition under which INSN is executed. If REV is not NULL, 518 it is set to TRUE when the returned comparison should be reversed 519 to get the actual condition. */ 520static rtx 521sched_get_condition_with_rev_uncached (const rtx_insn *insn, bool *rev) 522{ 523 rtx pat = PATTERN (insn); 524 rtx src; 525 526 if (rev) 527 *rev = false; 528 529 if (GET_CODE (pat) == COND_EXEC) 530 return COND_EXEC_TEST (pat); 531 532 if (!any_condjump_p (insn) || !onlyjump_p (insn)) 533 return 0; 534 535 src = SET_SRC (pc_set (insn)); 536 537 if (XEXP (src, 2) == pc_rtx) 538 return XEXP (src, 0); 539 else if (XEXP (src, 1) == pc_rtx) 540 { 541 rtx cond = XEXP (src, 0); 542 enum rtx_code revcode = reversed_comparison_code (cond, insn); 543 544 if (revcode == UNKNOWN) 545 return 0; 546 547 if (rev) 548 *rev = true; 549 return cond; 550 } 551 552 return 0; 553} 554 555/* Return the condition under which INSN does not execute (i.e. the 556 not-taken condition for a conditional branch), or NULL if we cannot 557 find such a condition. The caller should make a copy of the condition 558 before using it. */ 559rtx 560sched_get_reverse_condition_uncached (const rtx_insn *insn) 561{ 562 bool rev; 563 rtx cond = sched_get_condition_with_rev_uncached (insn, &rev); 564 if (cond == NULL_RTX) 565 return cond; 566 if (!rev) 567 { 568 enum rtx_code revcode = reversed_comparison_code (cond, insn); 569 cond = gen_rtx_fmt_ee (revcode, GET_MODE (cond), 570 XEXP (cond, 0), 571 XEXP (cond, 1)); 572 } 573 return cond; 574} 575 576/* Caching variant of sched_get_condition_with_rev_uncached. 577 We only do actual work the first time we come here for an insn; the 578 results are cached in INSN_CACHED_COND and INSN_REVERSE_COND. */ 579static rtx 580sched_get_condition_with_rev (const rtx_insn *insn, bool *rev) 581{ 582 bool tmp; 583 584 if (INSN_LUID (insn) == 0) 585 return sched_get_condition_with_rev_uncached (insn, rev); 586 587 if (INSN_CACHED_COND (insn) == const_true_rtx) 588 return NULL_RTX; 589 590 if (INSN_CACHED_COND (insn) != NULL_RTX) 591 { 592 if (rev) 593 *rev = INSN_REVERSE_COND (insn); 594 return INSN_CACHED_COND (insn); 595 } 596 597 INSN_CACHED_COND (insn) = sched_get_condition_with_rev_uncached (insn, &tmp); 598 INSN_REVERSE_COND (insn) = tmp; 599 600 if (INSN_CACHED_COND (insn) == NULL_RTX) 601 { 602 INSN_CACHED_COND (insn) = const_true_rtx; 603 return NULL_RTX; 604 } 605 606 if (rev) 607 *rev = INSN_REVERSE_COND (insn); 608 return INSN_CACHED_COND (insn); 609} 610 611/* True when we can find a condition under which INSN is executed. */ 612static bool 613sched_has_condition_p (const rtx_insn *insn) 614{ 615 return !! sched_get_condition_with_rev (insn, NULL); 616} 617 618 619 620/* Return nonzero if conditions COND1 and COND2 can never be both true. */ 621static int 622conditions_mutex_p (const_rtx cond1, const_rtx cond2, bool rev1, bool rev2) 623{ 624 if (COMPARISON_P (cond1) 625 && COMPARISON_P (cond2) 626 && GET_CODE (cond1) == 627 (rev1==rev2 628 ? reversed_comparison_code (cond2, NULL) 629 : GET_CODE (cond2)) 630 && rtx_equal_p (XEXP (cond1, 0), XEXP (cond2, 0)) 631 && XEXP (cond1, 1) == XEXP (cond2, 1)) 632 return 1; 633 return 0; 634} 635 636/* Return true if insn1 and insn2 can never depend on one another because 637 the conditions under which they are executed are mutually exclusive. */ 638bool 639sched_insns_conditions_mutex_p (const rtx_insn *insn1, const rtx_insn *insn2) 640{ 641 rtx cond1, cond2; 642 bool rev1 = false, rev2 = false; 643 644 /* df doesn't handle conditional lifetimes entirely correctly; 645 calls mess up the conditional lifetimes. */ 646 if (!CALL_P (insn1) && !CALL_P (insn2)) 647 { 648 cond1 = sched_get_condition_with_rev (insn1, &rev1); 649 cond2 = sched_get_condition_with_rev (insn2, &rev2); 650 if (cond1 && cond2 651 && conditions_mutex_p (cond1, cond2, rev1, rev2) 652 /* Make sure first instruction doesn't affect condition of second 653 instruction if switched. */ 654 && !modified_in_p (cond1, insn2) 655 /* Make sure second instruction doesn't affect condition of first 656 instruction if switched. */ 657 && !modified_in_p (cond2, insn1)) 658 return true; 659 } 660 return false; 661} 662 663 664/* Return true if INSN can potentially be speculated with type DS. */ 665bool 666sched_insn_is_legitimate_for_speculation_p (const rtx_insn *insn, ds_t ds) 667{ 668 if (HAS_INTERNAL_DEP (insn)) 669 return false; 670 671 if (!NONJUMP_INSN_P (insn)) 672 return false; 673 674 if (SCHED_GROUP_P (insn)) 675 return false; 676 677 if (IS_SPECULATION_CHECK_P (CONST_CAST_RTX_INSN (insn))) 678 return false; 679 680 if (side_effects_p (PATTERN (insn))) 681 return false; 682 683 if (ds & BE_IN_SPEC) 684 /* The following instructions, which depend on a speculatively scheduled 685 instruction, cannot be speculatively scheduled along. */ 686 { 687 if (may_trap_or_fault_p (PATTERN (insn))) 688 /* If instruction might fault, it cannot be speculatively scheduled. 689 For control speculation it's obvious why and for data speculation 690 it's because the insn might get wrong input if speculation 691 wasn't successful. */ 692 return false; 693 694 if ((ds & BE_IN_DATA) 695 && sched_has_condition_p (insn)) 696 /* If this is a predicated instruction, then it cannot be 697 speculatively scheduled. See PR35659. */ 698 return false; 699 } 700 701 return true; 702} 703 704/* Initialize LIST_PTR to point to one of the lists present in TYPES_PTR, 705 initialize RESOLVED_P_PTR with true if that list consists of resolved deps, 706 and remove the type of returned [through LIST_PTR] list from TYPES_PTR. 707 This function is used to switch sd_iterator to the next list. 708 !!! For internal use only. Might consider moving it to sched-int.h. */ 709void 710sd_next_list (const_rtx insn, sd_list_types_def *types_ptr, 711 deps_list_t *list_ptr, bool *resolved_p_ptr) 712{ 713 sd_list_types_def types = *types_ptr; 714 715 if (types & SD_LIST_HARD_BACK) 716 { 717 *list_ptr = INSN_HARD_BACK_DEPS (insn); 718 *resolved_p_ptr = false; 719 *types_ptr = types & ~SD_LIST_HARD_BACK; 720 } 721 else if (types & SD_LIST_SPEC_BACK) 722 { 723 *list_ptr = INSN_SPEC_BACK_DEPS (insn); 724 *resolved_p_ptr = false; 725 *types_ptr = types & ~SD_LIST_SPEC_BACK; 726 } 727 else if (types & SD_LIST_FORW) 728 { 729 *list_ptr = INSN_FORW_DEPS (insn); 730 *resolved_p_ptr = false; 731 *types_ptr = types & ~SD_LIST_FORW; 732 } 733 else if (types & SD_LIST_RES_BACK) 734 { 735 *list_ptr = INSN_RESOLVED_BACK_DEPS (insn); 736 *resolved_p_ptr = true; 737 *types_ptr = types & ~SD_LIST_RES_BACK; 738 } 739 else if (types & SD_LIST_RES_FORW) 740 { 741 *list_ptr = INSN_RESOLVED_FORW_DEPS (insn); 742 *resolved_p_ptr = true; 743 *types_ptr = types & ~SD_LIST_RES_FORW; 744 } 745 else 746 { 747 *list_ptr = NULL; 748 *resolved_p_ptr = false; 749 *types_ptr = SD_LIST_NONE; 750 } 751} 752 753/* Return the summary size of INSN's lists defined by LIST_TYPES. */ 754int 755sd_lists_size (const_rtx insn, sd_list_types_def list_types) 756{ 757 int size = 0; 758 759 while (list_types != SD_LIST_NONE) 760 { 761 deps_list_t list; 762 bool resolved_p; 763 764 sd_next_list (insn, &list_types, &list, &resolved_p); 765 if (list) 766 size += DEPS_LIST_N_LINKS (list); 767 } 768 769 return size; 770} 771 772/* Return true if INSN's lists defined by LIST_TYPES are all empty. */ 773 774bool 775sd_lists_empty_p (const_rtx insn, sd_list_types_def list_types) 776{ 777 while (list_types != SD_LIST_NONE) 778 { 779 deps_list_t list; 780 bool resolved_p; 781 782 sd_next_list (insn, &list_types, &list, &resolved_p); 783 if (!deps_list_empty_p (list)) 784 return false; 785 } 786 787 return true; 788} 789 790/* Initialize data for INSN. */ 791void 792sd_init_insn (rtx_insn *insn) 793{ 794 INSN_HARD_BACK_DEPS (insn) = create_deps_list (); 795 INSN_SPEC_BACK_DEPS (insn) = create_deps_list (); 796 INSN_RESOLVED_BACK_DEPS (insn) = create_deps_list (); 797 INSN_FORW_DEPS (insn) = create_deps_list (); 798 INSN_RESOLVED_FORW_DEPS (insn) = create_deps_list (); 799 800 /* ??? It would be nice to allocate dependency caches here. */ 801} 802 803/* Free data for INSN. */ 804void 805sd_finish_insn (rtx_insn *insn) 806{ 807 /* ??? It would be nice to deallocate dependency caches here. */ 808 809 free_deps_list (INSN_HARD_BACK_DEPS (insn)); 810 INSN_HARD_BACK_DEPS (insn) = NULL; 811 812 free_deps_list (INSN_SPEC_BACK_DEPS (insn)); 813 INSN_SPEC_BACK_DEPS (insn) = NULL; 814 815 free_deps_list (INSN_RESOLVED_BACK_DEPS (insn)); 816 INSN_RESOLVED_BACK_DEPS (insn) = NULL; 817 818 free_deps_list (INSN_FORW_DEPS (insn)); 819 INSN_FORW_DEPS (insn) = NULL; 820 821 free_deps_list (INSN_RESOLVED_FORW_DEPS (insn)); 822 INSN_RESOLVED_FORW_DEPS (insn) = NULL; 823} 824 825/* Find a dependency between producer PRO and consumer CON. 826 Search through resolved dependency lists if RESOLVED_P is true. 827 If no such dependency is found return NULL, 828 otherwise return the dependency and initialize SD_IT_PTR [if it is nonnull] 829 with an iterator pointing to it. */ 830static dep_t 831sd_find_dep_between_no_cache (rtx pro, rtx con, bool resolved_p, 832 sd_iterator_def *sd_it_ptr) 833{ 834 sd_list_types_def pro_list_type; 835 sd_list_types_def con_list_type; 836 sd_iterator_def sd_it; 837 dep_t dep; 838 bool found_p = false; 839 840 if (resolved_p) 841 { 842 pro_list_type = SD_LIST_RES_FORW; 843 con_list_type = SD_LIST_RES_BACK; 844 } 845 else 846 { 847 pro_list_type = SD_LIST_FORW; 848 con_list_type = SD_LIST_BACK; 849 } 850 851 /* Walk through either back list of INSN or forw list of ELEM 852 depending on which one is shorter. */ 853 if (sd_lists_size (con, con_list_type) < sd_lists_size (pro, pro_list_type)) 854 { 855 /* Find the dep_link with producer PRO in consumer's back_deps. */ 856 FOR_EACH_DEP (con, con_list_type, sd_it, dep) 857 if (DEP_PRO (dep) == pro) 858 { 859 found_p = true; 860 break; 861 } 862 } 863 else 864 { 865 /* Find the dep_link with consumer CON in producer's forw_deps. */ 866 FOR_EACH_DEP (pro, pro_list_type, sd_it, dep) 867 if (DEP_CON (dep) == con) 868 { 869 found_p = true; 870 break; 871 } 872 } 873 874 if (found_p) 875 { 876 if (sd_it_ptr != NULL) 877 *sd_it_ptr = sd_it; 878 879 return dep; 880 } 881 882 return NULL; 883} 884 885/* Find a dependency between producer PRO and consumer CON. 886 Use dependency [if available] to check if dependency is present at all. 887 Search through resolved dependency lists if RESOLVED_P is true. 888 If the dependency or NULL if none found. */ 889dep_t 890sd_find_dep_between (rtx pro, rtx con, bool resolved_p) 891{ 892 if (true_dependency_cache != NULL) 893 /* Avoiding the list walk below can cut compile times dramatically 894 for some code. */ 895 { 896 int elem_luid = INSN_LUID (pro); 897 int insn_luid = INSN_LUID (con); 898 899 if (!bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid) 900 && !bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid) 901 && !bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid) 902 && !bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid)) 903 return NULL; 904 } 905 906 return sd_find_dep_between_no_cache (pro, con, resolved_p, NULL); 907} 908 909/* Add or update a dependence described by DEP. 910 MEM1 and MEM2, if non-null, correspond to memory locations in case of 911 data speculation. 912 913 The function returns a value indicating if an old entry has been changed 914 or a new entry has been added to insn's backward deps. 915 916 This function merely checks if producer and consumer is the same insn 917 and doesn't create a dep in this case. Actual manipulation of 918 dependence data structures is performed in add_or_update_dep_1. */ 919static enum DEPS_ADJUST_RESULT 920maybe_add_or_update_dep_1 (dep_t dep, bool resolved_p, rtx mem1, rtx mem2) 921{ 922 rtx_insn *elem = DEP_PRO (dep); 923 rtx_insn *insn = DEP_CON (dep); 924 925 gcc_assert (INSN_P (insn) && INSN_P (elem)); 926 927 /* Don't depend an insn on itself. */ 928 if (insn == elem) 929 { 930 if (sched_deps_info->generate_spec_deps) 931 /* INSN has an internal dependence, which we can't overcome. */ 932 HAS_INTERNAL_DEP (insn) = 1; 933 934 return DEP_NODEP; 935 } 936 937 return add_or_update_dep_1 (dep, resolved_p, mem1, mem2); 938} 939 940/* Ask dependency caches what needs to be done for dependence DEP. 941 Return DEP_CREATED if new dependence should be created and there is no 942 need to try to find one searching the dependencies lists. 943 Return DEP_PRESENT if there already is a dependence described by DEP and 944 hence nothing is to be done. 945 Return DEP_CHANGED if there already is a dependence, but it should be 946 updated to incorporate additional information from DEP. */ 947static enum DEPS_ADJUST_RESULT 948ask_dependency_caches (dep_t dep) 949{ 950 int elem_luid = INSN_LUID (DEP_PRO (dep)); 951 int insn_luid = INSN_LUID (DEP_CON (dep)); 952 953 gcc_assert (true_dependency_cache != NULL 954 && output_dependency_cache != NULL 955 && anti_dependency_cache != NULL 956 && control_dependency_cache != NULL); 957 958 if (!(current_sched_info->flags & USE_DEPS_LIST)) 959 { 960 enum reg_note present_dep_type; 961 962 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)) 963 present_dep_type = REG_DEP_TRUE; 964 else if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)) 965 present_dep_type = REG_DEP_OUTPUT; 966 else if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)) 967 present_dep_type = REG_DEP_ANTI; 968 else if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid)) 969 present_dep_type = REG_DEP_CONTROL; 970 else 971 /* There is no existing dep so it should be created. */ 972 return DEP_CREATED; 973 974 if ((int) DEP_TYPE (dep) >= (int) present_dep_type) 975 /* DEP does not add anything to the existing dependence. */ 976 return DEP_PRESENT; 977 } 978 else 979 { 980 ds_t present_dep_types = 0; 981 982 if (bitmap_bit_p (&true_dependency_cache[insn_luid], elem_luid)) 983 present_dep_types |= DEP_TRUE; 984 if (bitmap_bit_p (&output_dependency_cache[insn_luid], elem_luid)) 985 present_dep_types |= DEP_OUTPUT; 986 if (bitmap_bit_p (&anti_dependency_cache[insn_luid], elem_luid)) 987 present_dep_types |= DEP_ANTI; 988 if (bitmap_bit_p (&control_dependency_cache[insn_luid], elem_luid)) 989 present_dep_types |= DEP_CONTROL; 990 991 if (present_dep_types == 0) 992 /* There is no existing dep so it should be created. */ 993 return DEP_CREATED; 994 995 if (!(current_sched_info->flags & DO_SPECULATION) 996 || !bitmap_bit_p (&spec_dependency_cache[insn_luid], elem_luid)) 997 { 998 if ((present_dep_types | (DEP_STATUS (dep) & DEP_TYPES)) 999 == present_dep_types) 1000 /* DEP does not add anything to the existing dependence. */ 1001 return DEP_PRESENT; 1002 } 1003 else 1004 { 1005 /* Only true dependencies can be data speculative and 1006 only anti dependencies can be control speculative. */ 1007 gcc_assert ((present_dep_types & (DEP_TRUE | DEP_ANTI)) 1008 == present_dep_types); 1009 1010 /* if (DEP is SPECULATIVE) then 1011 ..we should update DEP_STATUS 1012 else 1013 ..we should reset existing dep to non-speculative. */ 1014 } 1015 } 1016 1017 return DEP_CHANGED; 1018} 1019 1020/* Set dependency caches according to DEP. */ 1021static void 1022set_dependency_caches (dep_t dep) 1023{ 1024 int elem_luid = INSN_LUID (DEP_PRO (dep)); 1025 int insn_luid = INSN_LUID (DEP_CON (dep)); 1026 1027 if (!(current_sched_info->flags & USE_DEPS_LIST)) 1028 { 1029 switch (DEP_TYPE (dep)) 1030 { 1031 case REG_DEP_TRUE: 1032 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid); 1033 break; 1034 1035 case REG_DEP_OUTPUT: 1036 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid); 1037 break; 1038 1039 case REG_DEP_ANTI: 1040 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid); 1041 break; 1042 1043 case REG_DEP_CONTROL: 1044 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid); 1045 break; 1046 1047 default: 1048 gcc_unreachable (); 1049 } 1050 } 1051 else 1052 { 1053 ds_t ds = DEP_STATUS (dep); 1054 1055 if (ds & DEP_TRUE) 1056 bitmap_set_bit (&true_dependency_cache[insn_luid], elem_luid); 1057 if (ds & DEP_OUTPUT) 1058 bitmap_set_bit (&output_dependency_cache[insn_luid], elem_luid); 1059 if (ds & DEP_ANTI) 1060 bitmap_set_bit (&anti_dependency_cache[insn_luid], elem_luid); 1061 if (ds & DEP_CONTROL) 1062 bitmap_set_bit (&control_dependency_cache[insn_luid], elem_luid); 1063 1064 if (ds & SPECULATIVE) 1065 { 1066 gcc_assert (current_sched_info->flags & DO_SPECULATION); 1067 bitmap_set_bit (&spec_dependency_cache[insn_luid], elem_luid); 1068 } 1069 } 1070} 1071 1072/* Type of dependence DEP have changed from OLD_TYPE. Update dependency 1073 caches accordingly. */ 1074static void 1075update_dependency_caches (dep_t dep, enum reg_note old_type) 1076{ 1077 int elem_luid = INSN_LUID (DEP_PRO (dep)); 1078 int insn_luid = INSN_LUID (DEP_CON (dep)); 1079 1080 /* Clear corresponding cache entry because type of the link 1081 may have changed. Keep them if we use_deps_list. */ 1082 if (!(current_sched_info->flags & USE_DEPS_LIST)) 1083 { 1084 switch (old_type) 1085 { 1086 case REG_DEP_OUTPUT: 1087 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid); 1088 break; 1089 1090 case REG_DEP_ANTI: 1091 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid); 1092 break; 1093 1094 case REG_DEP_CONTROL: 1095 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid); 1096 break; 1097 1098 default: 1099 gcc_unreachable (); 1100 } 1101 } 1102 1103 set_dependency_caches (dep); 1104} 1105 1106/* Convert a dependence pointed to by SD_IT to be non-speculative. */ 1107static void 1108change_spec_dep_to_hard (sd_iterator_def sd_it) 1109{ 1110 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); 1111 dep_link_t link = DEP_NODE_BACK (node); 1112 dep_t dep = DEP_NODE_DEP (node); 1113 rtx_insn *elem = DEP_PRO (dep); 1114 rtx_insn *insn = DEP_CON (dep); 1115 1116 move_dep_link (link, INSN_SPEC_BACK_DEPS (insn), INSN_HARD_BACK_DEPS (insn)); 1117 1118 DEP_STATUS (dep) &= ~SPECULATIVE; 1119 1120 if (true_dependency_cache != NULL) 1121 /* Clear the cache entry. */ 1122 bitmap_clear_bit (&spec_dependency_cache[INSN_LUID (insn)], 1123 INSN_LUID (elem)); 1124} 1125 1126/* Update DEP to incorporate information from NEW_DEP. 1127 SD_IT points to DEP in case it should be moved to another list. 1128 MEM1 and MEM2, if nonnull, correspond to memory locations in case if 1129 data-speculative dependence should be updated. */ 1130static enum DEPS_ADJUST_RESULT 1131update_dep (dep_t dep, dep_t new_dep, 1132 sd_iterator_def sd_it ATTRIBUTE_UNUSED, 1133 rtx mem1 ATTRIBUTE_UNUSED, 1134 rtx mem2 ATTRIBUTE_UNUSED) 1135{ 1136 enum DEPS_ADJUST_RESULT res = DEP_PRESENT; 1137 enum reg_note old_type = DEP_TYPE (dep); 1138 bool was_spec = dep_spec_p (dep); 1139 1140 DEP_NONREG (dep) |= DEP_NONREG (new_dep); 1141 DEP_MULTIPLE (dep) = 1; 1142 1143 /* If this is a more restrictive type of dependence than the 1144 existing one, then change the existing dependence to this 1145 type. */ 1146 if ((int) DEP_TYPE (new_dep) < (int) old_type) 1147 { 1148 DEP_TYPE (dep) = DEP_TYPE (new_dep); 1149 res = DEP_CHANGED; 1150 } 1151 1152 if (current_sched_info->flags & USE_DEPS_LIST) 1153 /* Update DEP_STATUS. */ 1154 { 1155 ds_t dep_status = DEP_STATUS (dep); 1156 ds_t ds = DEP_STATUS (new_dep); 1157 ds_t new_status = ds | dep_status; 1158 1159 if (new_status & SPECULATIVE) 1160 { 1161 /* Either existing dep or a dep we're adding or both are 1162 speculative. */ 1163 if (!(ds & SPECULATIVE) 1164 || !(dep_status & SPECULATIVE)) 1165 /* The new dep can't be speculative. */ 1166 new_status &= ~SPECULATIVE; 1167 else 1168 { 1169 /* Both are speculative. Merge probabilities. */ 1170 if (mem1 != NULL) 1171 { 1172 dw_t dw; 1173 1174 dw = estimate_dep_weak (mem1, mem2); 1175 ds = set_dep_weak (ds, BEGIN_DATA, dw); 1176 } 1177 1178 new_status = ds_merge (dep_status, ds); 1179 } 1180 } 1181 1182 ds = new_status; 1183 1184 if (dep_status != ds) 1185 { 1186 DEP_STATUS (dep) = ds; 1187 res = DEP_CHANGED; 1188 } 1189 } 1190 1191 if (was_spec && !dep_spec_p (dep)) 1192 /* The old dep was speculative, but now it isn't. */ 1193 change_spec_dep_to_hard (sd_it); 1194 1195 if (true_dependency_cache != NULL 1196 && res == DEP_CHANGED) 1197 update_dependency_caches (dep, old_type); 1198 1199 return res; 1200} 1201 1202/* Add or update a dependence described by DEP. 1203 MEM1 and MEM2, if non-null, correspond to memory locations in case of 1204 data speculation. 1205 1206 The function returns a value indicating if an old entry has been changed 1207 or a new entry has been added to insn's backward deps or nothing has 1208 been updated at all. */ 1209static enum DEPS_ADJUST_RESULT 1210add_or_update_dep_1 (dep_t new_dep, bool resolved_p, 1211 rtx mem1 ATTRIBUTE_UNUSED, rtx mem2 ATTRIBUTE_UNUSED) 1212{ 1213 bool maybe_present_p = true; 1214 bool present_p = false; 1215 1216 gcc_assert (INSN_P (DEP_PRO (new_dep)) && INSN_P (DEP_CON (new_dep)) 1217 && DEP_PRO (new_dep) != DEP_CON (new_dep)); 1218 1219 if (flag_checking) 1220 check_dep (new_dep, mem1 != NULL); 1221 1222 if (true_dependency_cache != NULL) 1223 { 1224 switch (ask_dependency_caches (new_dep)) 1225 { 1226 case DEP_PRESENT: 1227 dep_t present_dep; 1228 sd_iterator_def sd_it; 1229 1230 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep), 1231 DEP_CON (new_dep), 1232 resolved_p, &sd_it); 1233 DEP_MULTIPLE (present_dep) = 1; 1234 return DEP_PRESENT; 1235 1236 case DEP_CHANGED: 1237 maybe_present_p = true; 1238 present_p = true; 1239 break; 1240 1241 case DEP_CREATED: 1242 maybe_present_p = false; 1243 present_p = false; 1244 break; 1245 1246 default: 1247 gcc_unreachable (); 1248 break; 1249 } 1250 } 1251 1252 /* Check that we don't already have this dependence. */ 1253 if (maybe_present_p) 1254 { 1255 dep_t present_dep; 1256 sd_iterator_def sd_it; 1257 1258 gcc_assert (true_dependency_cache == NULL || present_p); 1259 1260 present_dep = sd_find_dep_between_no_cache (DEP_PRO (new_dep), 1261 DEP_CON (new_dep), 1262 resolved_p, &sd_it); 1263 1264 if (present_dep != NULL) 1265 /* We found an existing dependency between ELEM and INSN. */ 1266 return update_dep (present_dep, new_dep, sd_it, mem1, mem2); 1267 else 1268 /* We didn't find a dep, it shouldn't present in the cache. */ 1269 gcc_assert (!present_p); 1270 } 1271 1272 /* Might want to check one level of transitivity to save conses. 1273 This check should be done in maybe_add_or_update_dep_1. 1274 Since we made it to add_or_update_dep_1, we must create 1275 (or update) a link. */ 1276 1277 if (mem1 != NULL_RTX) 1278 { 1279 gcc_assert (sched_deps_info->generate_spec_deps); 1280 DEP_STATUS (new_dep) = set_dep_weak (DEP_STATUS (new_dep), BEGIN_DATA, 1281 estimate_dep_weak (mem1, mem2)); 1282 } 1283 1284 sd_add_dep (new_dep, resolved_p); 1285 1286 return DEP_CREATED; 1287} 1288 1289/* Initialize BACK_LIST_PTR with consumer's backward list and 1290 FORW_LIST_PTR with producer's forward list. If RESOLVED_P is true 1291 initialize with lists that hold resolved deps. */ 1292static void 1293get_back_and_forw_lists (dep_t dep, bool resolved_p, 1294 deps_list_t *back_list_ptr, 1295 deps_list_t *forw_list_ptr) 1296{ 1297 rtx_insn *con = DEP_CON (dep); 1298 1299 if (!resolved_p) 1300 { 1301 if (dep_spec_p (dep)) 1302 *back_list_ptr = INSN_SPEC_BACK_DEPS (con); 1303 else 1304 *back_list_ptr = INSN_HARD_BACK_DEPS (con); 1305 1306 *forw_list_ptr = INSN_FORW_DEPS (DEP_PRO (dep)); 1307 } 1308 else 1309 { 1310 *back_list_ptr = INSN_RESOLVED_BACK_DEPS (con); 1311 *forw_list_ptr = INSN_RESOLVED_FORW_DEPS (DEP_PRO (dep)); 1312 } 1313} 1314 1315/* Add dependence described by DEP. 1316 If RESOLVED_P is true treat the dependence as a resolved one. */ 1317void 1318sd_add_dep (dep_t dep, bool resolved_p) 1319{ 1320 dep_node_t n = create_dep_node (); 1321 deps_list_t con_back_deps; 1322 deps_list_t pro_forw_deps; 1323 rtx_insn *elem = DEP_PRO (dep); 1324 rtx_insn *insn = DEP_CON (dep); 1325 1326 gcc_assert (INSN_P (insn) && INSN_P (elem) && insn != elem); 1327 1328 if ((current_sched_info->flags & DO_SPECULATION) == 0 1329 || !sched_insn_is_legitimate_for_speculation_p (insn, DEP_STATUS (dep))) 1330 DEP_STATUS (dep) &= ~SPECULATIVE; 1331 1332 copy_dep (DEP_NODE_DEP (n), dep); 1333 1334 get_back_and_forw_lists (dep, resolved_p, &con_back_deps, &pro_forw_deps); 1335 1336 add_to_deps_list (DEP_NODE_BACK (n), con_back_deps); 1337 1338 if (flag_checking) 1339 check_dep (dep, false); 1340 1341 add_to_deps_list (DEP_NODE_FORW (n), pro_forw_deps); 1342 1343 /* If we are adding a dependency to INSN's LOG_LINKs, then note that 1344 in the bitmap caches of dependency information. */ 1345 if (true_dependency_cache != NULL) 1346 set_dependency_caches (dep); 1347} 1348 1349/* Add or update backward dependence between INSN and ELEM 1350 with given type DEP_TYPE and dep_status DS. 1351 This function is a convenience wrapper. */ 1352enum DEPS_ADJUST_RESULT 1353sd_add_or_update_dep (dep_t dep, bool resolved_p) 1354{ 1355 return add_or_update_dep_1 (dep, resolved_p, NULL_RTX, NULL_RTX); 1356} 1357 1358/* Resolved dependence pointed to by SD_IT. 1359 SD_IT will advance to the next element. */ 1360void 1361sd_resolve_dep (sd_iterator_def sd_it) 1362{ 1363 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); 1364 dep_t dep = DEP_NODE_DEP (node); 1365 rtx_insn *pro = DEP_PRO (dep); 1366 rtx_insn *con = DEP_CON (dep); 1367 1368 if (dep_spec_p (dep)) 1369 move_dep_link (DEP_NODE_BACK (node), INSN_SPEC_BACK_DEPS (con), 1370 INSN_RESOLVED_BACK_DEPS (con)); 1371 else 1372 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con), 1373 INSN_RESOLVED_BACK_DEPS (con)); 1374 1375 move_dep_link (DEP_NODE_FORW (node), INSN_FORW_DEPS (pro), 1376 INSN_RESOLVED_FORW_DEPS (pro)); 1377} 1378 1379/* Perform the inverse operation of sd_resolve_dep. Restore the dependence 1380 pointed to by SD_IT to unresolved state. */ 1381void 1382sd_unresolve_dep (sd_iterator_def sd_it) 1383{ 1384 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); 1385 dep_t dep = DEP_NODE_DEP (node); 1386 rtx_insn *pro = DEP_PRO (dep); 1387 rtx_insn *con = DEP_CON (dep); 1388 1389 if (dep_spec_p (dep)) 1390 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con), 1391 INSN_SPEC_BACK_DEPS (con)); 1392 else 1393 move_dep_link (DEP_NODE_BACK (node), INSN_RESOLVED_BACK_DEPS (con), 1394 INSN_HARD_BACK_DEPS (con)); 1395 1396 move_dep_link (DEP_NODE_FORW (node), INSN_RESOLVED_FORW_DEPS (pro), 1397 INSN_FORW_DEPS (pro)); 1398} 1399 1400/* Make TO depend on all the FROM's producers. 1401 If RESOLVED_P is true add dependencies to the resolved lists. */ 1402void 1403sd_copy_back_deps (rtx_insn *to, rtx_insn *from, bool resolved_p) 1404{ 1405 sd_list_types_def list_type; 1406 sd_iterator_def sd_it; 1407 dep_t dep; 1408 1409 list_type = resolved_p ? SD_LIST_RES_BACK : SD_LIST_BACK; 1410 1411 FOR_EACH_DEP (from, list_type, sd_it, dep) 1412 { 1413 dep_def _new_dep, *new_dep = &_new_dep; 1414 1415 copy_dep (new_dep, dep); 1416 DEP_CON (new_dep) = to; 1417 sd_add_dep (new_dep, resolved_p); 1418 } 1419} 1420 1421/* Remove a dependency referred to by SD_IT. 1422 SD_IT will point to the next dependence after removal. */ 1423void 1424sd_delete_dep (sd_iterator_def sd_it) 1425{ 1426 dep_node_t n = DEP_LINK_NODE (*sd_it.linkp); 1427 dep_t dep = DEP_NODE_DEP (n); 1428 rtx_insn *pro = DEP_PRO (dep); 1429 rtx_insn *con = DEP_CON (dep); 1430 deps_list_t con_back_deps; 1431 deps_list_t pro_forw_deps; 1432 1433 if (true_dependency_cache != NULL) 1434 { 1435 int elem_luid = INSN_LUID (pro); 1436 int insn_luid = INSN_LUID (con); 1437 1438 bitmap_clear_bit (&true_dependency_cache[insn_luid], elem_luid); 1439 bitmap_clear_bit (&anti_dependency_cache[insn_luid], elem_luid); 1440 bitmap_clear_bit (&control_dependency_cache[insn_luid], elem_luid); 1441 bitmap_clear_bit (&output_dependency_cache[insn_luid], elem_luid); 1442 1443 if (current_sched_info->flags & DO_SPECULATION) 1444 bitmap_clear_bit (&spec_dependency_cache[insn_luid], elem_luid); 1445 } 1446 1447 get_back_and_forw_lists (dep, sd_it.resolved_p, 1448 &con_back_deps, &pro_forw_deps); 1449 1450 remove_from_deps_list (DEP_NODE_BACK (n), con_back_deps); 1451 remove_from_deps_list (DEP_NODE_FORW (n), pro_forw_deps); 1452 1453 delete_dep_node (n); 1454} 1455 1456/* Dump size of the lists. */ 1457#define DUMP_LISTS_SIZE (2) 1458 1459/* Dump dependencies of the lists. */ 1460#define DUMP_LISTS_DEPS (4) 1461 1462/* Dump all information about the lists. */ 1463#define DUMP_LISTS_ALL (DUMP_LISTS_SIZE | DUMP_LISTS_DEPS) 1464 1465/* Dump deps_lists of INSN specified by TYPES to DUMP. 1466 FLAGS is a bit mask specifying what information about the lists needs 1467 to be printed. 1468 If FLAGS has the very first bit set, then dump all information about 1469 the lists and propagate this bit into the callee dump functions. */ 1470static void 1471dump_lists (FILE *dump, rtx insn, sd_list_types_def types, int flags) 1472{ 1473 sd_iterator_def sd_it; 1474 dep_t dep; 1475 int all; 1476 1477 all = (flags & 1); 1478 1479 if (all) 1480 flags |= DUMP_LISTS_ALL; 1481 1482 fprintf (dump, "["); 1483 1484 if (flags & DUMP_LISTS_SIZE) 1485 fprintf (dump, "%d; ", sd_lists_size (insn, types)); 1486 1487 if (flags & DUMP_LISTS_DEPS) 1488 { 1489 FOR_EACH_DEP (insn, types, sd_it, dep) 1490 { 1491 dump_dep (dump, dep, dump_dep_flags | all); 1492 fprintf (dump, " "); 1493 } 1494 } 1495} 1496 1497/* Dump all information about deps_lists of INSN specified by TYPES 1498 to STDERR. */ 1499void 1500sd_debug_lists (rtx insn, sd_list_types_def types) 1501{ 1502 dump_lists (stderr, insn, types, 1); 1503 fprintf (stderr, "\n"); 1504} 1505 1506/* A wrapper around add_dependence_1, to add a dependence of CON on 1507 PRO, with type DEP_TYPE. This function implements special handling 1508 for REG_DEP_CONTROL dependencies. For these, we optionally promote 1509 the type to REG_DEP_ANTI if we can determine that predication is 1510 impossible; otherwise we add additional true dependencies on the 1511 INSN_COND_DEPS list of the jump (which PRO must be). */ 1512void 1513add_dependence (rtx_insn *con, rtx_insn *pro, enum reg_note dep_type) 1514{ 1515 if (dep_type == REG_DEP_CONTROL 1516 && !(current_sched_info->flags & DO_PREDICATION)) 1517 dep_type = REG_DEP_ANTI; 1518 1519 /* A REG_DEP_CONTROL dependence may be eliminated through predication, 1520 so we must also make the insn dependent on the setter of the 1521 condition. */ 1522 if (dep_type == REG_DEP_CONTROL) 1523 { 1524 rtx_insn *real_pro = pro; 1525 rtx_insn *other = real_insn_for_shadow (real_pro); 1526 rtx cond; 1527 1528 if (other != NULL_RTX) 1529 real_pro = other; 1530 cond = sched_get_reverse_condition_uncached (real_pro); 1531 /* Verify that the insn does not use a different value in 1532 the condition register than the one that was present at 1533 the jump. */ 1534 if (cond == NULL_RTX) 1535 dep_type = REG_DEP_ANTI; 1536 else if (INSN_CACHED_COND (real_pro) == const_true_rtx) 1537 { 1538 HARD_REG_SET uses; 1539 CLEAR_HARD_REG_SET (uses); 1540 note_uses (&PATTERN (con), record_hard_reg_uses, &uses); 1541 if (TEST_HARD_REG_BIT (uses, REGNO (XEXP (cond, 0)))) 1542 dep_type = REG_DEP_ANTI; 1543 } 1544 if (dep_type == REG_DEP_CONTROL) 1545 { 1546 if (sched_verbose >= 5) 1547 fprintf (sched_dump, "making DEP_CONTROL for %d\n", 1548 INSN_UID (real_pro)); 1549 add_dependence_list (con, INSN_COND_DEPS (real_pro), 0, 1550 REG_DEP_TRUE, false); 1551 } 1552 } 1553 1554 add_dependence_1 (con, pro, dep_type); 1555} 1556 1557/* A convenience wrapper to operate on an entire list. HARD should be 1558 true if DEP_NONREG should be set on newly created dependencies. */ 1559 1560static void 1561add_dependence_list (rtx_insn *insn, rtx_insn_list *list, int uncond, 1562 enum reg_note dep_type, bool hard) 1563{ 1564 mark_as_hard = hard; 1565 for (; list; list = list->next ()) 1566 { 1567 if (uncond || ! sched_insns_conditions_mutex_p (insn, list->insn ())) 1568 add_dependence (insn, list->insn (), dep_type); 1569 } 1570 mark_as_hard = false; 1571} 1572 1573/* Similar, but free *LISTP at the same time, when the context 1574 is not readonly. HARD should be true if DEP_NONREG should be set on 1575 newly created dependencies. */ 1576 1577static void 1578add_dependence_list_and_free (class deps_desc *deps, rtx_insn *insn, 1579 rtx_insn_list **listp, 1580 int uncond, enum reg_note dep_type, bool hard) 1581{ 1582 add_dependence_list (insn, *listp, uncond, dep_type, hard); 1583 1584 /* We don't want to short-circuit dependencies involving debug 1585 insns, because they may cause actual dependencies to be 1586 disregarded. */ 1587 if (deps->readonly || DEBUG_INSN_P (insn)) 1588 return; 1589 1590 free_INSN_LIST_list (listp); 1591} 1592 1593/* Remove all occurrences of INSN from LIST. Return the number of 1594 occurrences removed. */ 1595 1596static int 1597remove_from_dependence_list (rtx_insn *insn, rtx_insn_list **listp) 1598{ 1599 int removed = 0; 1600 1601 while (*listp) 1602 { 1603 if ((*listp)->insn () == insn) 1604 { 1605 remove_free_INSN_LIST_node (listp); 1606 removed++; 1607 continue; 1608 } 1609 1610 listp = (rtx_insn_list **)&XEXP (*listp, 1); 1611 } 1612 1613 return removed; 1614} 1615 1616/* Same as above, but process two lists at once. */ 1617static int 1618remove_from_both_dependence_lists (rtx_insn *insn, 1619 rtx_insn_list **listp, 1620 rtx_expr_list **exprp) 1621{ 1622 int removed = 0; 1623 1624 while (*listp) 1625 { 1626 if (XEXP (*listp, 0) == insn) 1627 { 1628 remove_free_INSN_LIST_node (listp); 1629 remove_free_EXPR_LIST_node (exprp); 1630 removed++; 1631 continue; 1632 } 1633 1634 listp = (rtx_insn_list **)&XEXP (*listp, 1); 1635 exprp = (rtx_expr_list **)&XEXP (*exprp, 1); 1636 } 1637 1638 return removed; 1639} 1640 1641/* Clear all dependencies for an insn. */ 1642static void 1643delete_all_dependences (rtx_insn *insn) 1644{ 1645 sd_iterator_def sd_it; 1646 dep_t dep; 1647 1648 /* The below cycle can be optimized to clear the caches and back_deps 1649 in one call but that would provoke duplication of code from 1650 delete_dep (). */ 1651 1652 for (sd_it = sd_iterator_start (insn, SD_LIST_BACK); 1653 sd_iterator_cond (&sd_it, &dep);) 1654 sd_delete_dep (sd_it); 1655} 1656 1657/* All insns in a scheduling group except the first should only have 1658 dependencies on the previous insn in the group. So we find the 1659 first instruction in the scheduling group by walking the dependence 1660 chains backwards. Then we add the dependencies for the group to 1661 the previous nonnote insn. */ 1662 1663static void 1664chain_to_prev_insn (rtx_insn *insn) 1665{ 1666 sd_iterator_def sd_it; 1667 dep_t dep; 1668 rtx_insn *prev_nonnote; 1669 1670 FOR_EACH_DEP (insn, SD_LIST_BACK, sd_it, dep) 1671 { 1672 rtx_insn *i = insn; 1673 rtx_insn *pro = DEP_PRO (dep); 1674 1675 do 1676 { 1677 i = prev_nonnote_insn (i); 1678 1679 if (pro == i) 1680 goto next_link; 1681 } while (SCHED_GROUP_P (i) || DEBUG_INSN_P (i)); 1682 1683 if (! sched_insns_conditions_mutex_p (i, pro)) 1684 add_dependence (i, pro, DEP_TYPE (dep)); 1685 next_link:; 1686 } 1687 1688 delete_all_dependences (insn); 1689 1690 prev_nonnote = prev_nonnote_nondebug_insn (insn); 1691 if (BLOCK_FOR_INSN (insn) == BLOCK_FOR_INSN (prev_nonnote) 1692 && ! sched_insns_conditions_mutex_p (insn, prev_nonnote)) 1693 add_dependence (insn, prev_nonnote, REG_DEP_ANTI); 1694} 1695 1696/* Process an insn's memory dependencies. There are four kinds of 1697 dependencies: 1698 1699 (0) read dependence: read follows read 1700 (1) true dependence: read follows write 1701 (2) output dependence: write follows write 1702 (3) anti dependence: write follows read 1703 1704 We are careful to build only dependencies which actually exist, and 1705 use transitivity to avoid building too many links. */ 1706 1707/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. 1708 The MEM is a memory reference contained within INSN, which we are saving 1709 so that we can do memory aliasing on it. */ 1710 1711static void 1712add_insn_mem_dependence (class deps_desc *deps, bool read_p, 1713 rtx_insn *insn, rtx mem) 1714{ 1715 rtx_insn_list **insn_list; 1716 rtx_insn_list *insn_node; 1717 rtx_expr_list **mem_list; 1718 rtx_expr_list *mem_node; 1719 1720 gcc_assert (!deps->readonly); 1721 if (read_p) 1722 { 1723 insn_list = &deps->pending_read_insns; 1724 mem_list = &deps->pending_read_mems; 1725 if (!DEBUG_INSN_P (insn)) 1726 deps->pending_read_list_length++; 1727 } 1728 else 1729 { 1730 insn_list = &deps->pending_write_insns; 1731 mem_list = &deps->pending_write_mems; 1732 deps->pending_write_list_length++; 1733 } 1734 1735 insn_node = alloc_INSN_LIST (insn, *insn_list); 1736 *insn_list = insn_node; 1737 1738 if (sched_deps_info->use_cselib) 1739 { 1740 mem = shallow_copy_rtx (mem); 1741 XEXP (mem, 0) = cselib_subst_to_values_from_insn (XEXP (mem, 0), 1742 GET_MODE (mem), insn); 1743 } 1744 mem_node = alloc_EXPR_LIST (VOIDmode, canon_rtx (mem), *mem_list); 1745 *mem_list = mem_node; 1746} 1747 1748/* Make a dependency between every memory reference on the pending lists 1749 and INSN, thus flushing the pending lists. FOR_READ is true if emitting 1750 dependencies for a read operation, similarly with FOR_WRITE. */ 1751 1752static void 1753flush_pending_lists (class deps_desc *deps, rtx_insn *insn, int for_read, 1754 int for_write) 1755{ 1756 if (for_write) 1757 { 1758 add_dependence_list_and_free (deps, insn, &deps->pending_read_insns, 1759 1, REG_DEP_ANTI, true); 1760 if (!deps->readonly) 1761 { 1762 free_EXPR_LIST_list (&deps->pending_read_mems); 1763 deps->pending_read_list_length = 0; 1764 } 1765 } 1766 1767 add_dependence_list_and_free (deps, insn, &deps->pending_write_insns, 1, 1768 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT, 1769 true); 1770 1771 add_dependence_list_and_free (deps, insn, 1772 &deps->last_pending_memory_flush, 1, 1773 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT, 1774 true); 1775 1776 add_dependence_list_and_free (deps, insn, &deps->pending_jump_insns, 1, 1777 REG_DEP_ANTI, true); 1778 1779 if (DEBUG_INSN_P (insn)) 1780 { 1781 if (for_write) 1782 free_INSN_LIST_list (&deps->pending_read_insns); 1783 free_INSN_LIST_list (&deps->pending_write_insns); 1784 free_INSN_LIST_list (&deps->last_pending_memory_flush); 1785 free_INSN_LIST_list (&deps->pending_jump_insns); 1786 } 1787 1788 if (!deps->readonly) 1789 { 1790 free_EXPR_LIST_list (&deps->pending_write_mems); 1791 deps->pending_write_list_length = 0; 1792 1793 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); 1794 deps->pending_flush_length = 1; 1795 } 1796 mark_as_hard = false; 1797} 1798 1799/* Instruction which dependencies we are analyzing. */ 1800static rtx_insn *cur_insn = NULL; 1801 1802/* Implement hooks for haifa scheduler. */ 1803 1804static void 1805haifa_start_insn (rtx_insn *insn) 1806{ 1807 gcc_assert (insn && !cur_insn); 1808 1809 cur_insn = insn; 1810} 1811 1812static void 1813haifa_finish_insn (void) 1814{ 1815 cur_insn = NULL; 1816} 1817 1818void 1819haifa_note_reg_set (int regno) 1820{ 1821 SET_REGNO_REG_SET (reg_pending_sets, regno); 1822} 1823 1824void 1825haifa_note_reg_clobber (int regno) 1826{ 1827 SET_REGNO_REG_SET (reg_pending_clobbers, regno); 1828} 1829 1830void 1831haifa_note_reg_use (int regno) 1832{ 1833 SET_REGNO_REG_SET (reg_pending_uses, regno); 1834} 1835 1836static void 1837haifa_note_mem_dep (rtx mem, rtx pending_mem, rtx_insn *pending_insn, ds_t ds) 1838{ 1839 if (!(ds & SPECULATIVE)) 1840 { 1841 mem = NULL_RTX; 1842 pending_mem = NULL_RTX; 1843 } 1844 else 1845 gcc_assert (ds & BEGIN_DATA); 1846 1847 { 1848 dep_def _dep, *dep = &_dep; 1849 1850 init_dep_1 (dep, pending_insn, cur_insn, ds_to_dt (ds), 1851 current_sched_info->flags & USE_DEPS_LIST ? ds : 0); 1852 DEP_NONREG (dep) = 1; 1853 maybe_add_or_update_dep_1 (dep, false, pending_mem, mem); 1854 } 1855 1856} 1857 1858static void 1859haifa_note_dep (rtx_insn *elem, ds_t ds) 1860{ 1861 dep_def _dep; 1862 dep_t dep = &_dep; 1863 1864 init_dep (dep, elem, cur_insn, ds_to_dt (ds)); 1865 if (mark_as_hard) 1866 DEP_NONREG (dep) = 1; 1867 maybe_add_or_update_dep_1 (dep, false, NULL_RTX, NULL_RTX); 1868} 1869 1870static void 1871note_reg_use (int r) 1872{ 1873 if (sched_deps_info->note_reg_use) 1874 sched_deps_info->note_reg_use (r); 1875} 1876 1877static void 1878note_reg_set (int r) 1879{ 1880 if (sched_deps_info->note_reg_set) 1881 sched_deps_info->note_reg_set (r); 1882} 1883 1884static void 1885note_reg_clobber (int r) 1886{ 1887 if (sched_deps_info->note_reg_clobber) 1888 sched_deps_info->note_reg_clobber (r); 1889} 1890 1891static void 1892note_mem_dep (rtx m1, rtx m2, rtx_insn *e, ds_t ds) 1893{ 1894 if (sched_deps_info->note_mem_dep) 1895 sched_deps_info->note_mem_dep (m1, m2, e, ds); 1896} 1897 1898static void 1899note_dep (rtx_insn *e, ds_t ds) 1900{ 1901 if (sched_deps_info->note_dep) 1902 sched_deps_info->note_dep (e, ds); 1903} 1904 1905/* Return corresponding to DS reg_note. */ 1906enum reg_note 1907ds_to_dt (ds_t ds) 1908{ 1909 if (ds & DEP_TRUE) 1910 return REG_DEP_TRUE; 1911 else if (ds & DEP_OUTPUT) 1912 return REG_DEP_OUTPUT; 1913 else if (ds & DEP_ANTI) 1914 return REG_DEP_ANTI; 1915 else 1916 { 1917 gcc_assert (ds & DEP_CONTROL); 1918 return REG_DEP_CONTROL; 1919 } 1920} 1921 1922 1923 1924/* Functions for computation of info needed for register pressure 1925 sensitive insn scheduling. */ 1926 1927 1928/* Allocate and return reg_use_data structure for REGNO and INSN. */ 1929static struct reg_use_data * 1930create_insn_reg_use (int regno, rtx_insn *insn) 1931{ 1932 struct reg_use_data *use; 1933 1934 use = (struct reg_use_data *) xmalloc (sizeof (struct reg_use_data)); 1935 use->regno = regno; 1936 use->insn = insn; 1937 use->next_insn_use = INSN_REG_USE_LIST (insn); 1938 INSN_REG_USE_LIST (insn) = use; 1939 return use; 1940} 1941 1942/* Allocate reg_set_data structure for REGNO and INSN. */ 1943static void 1944create_insn_reg_set (int regno, rtx insn) 1945{ 1946 struct reg_set_data *set; 1947 1948 set = (struct reg_set_data *) xmalloc (sizeof (struct reg_set_data)); 1949 set->regno = regno; 1950 set->insn = insn; 1951 set->next_insn_set = INSN_REG_SET_LIST (insn); 1952 INSN_REG_SET_LIST (insn) = set; 1953} 1954 1955/* Set up insn register uses for INSN and dependency context DEPS. */ 1956static void 1957setup_insn_reg_uses (class deps_desc *deps, rtx_insn *insn) 1958{ 1959 unsigned i; 1960 reg_set_iterator rsi; 1961 struct reg_use_data *use, *use2, *next; 1962 struct deps_reg *reg_last; 1963 1964 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi) 1965 { 1966 if (i < FIRST_PSEUDO_REGISTER 1967 && TEST_HARD_REG_BIT (ira_no_alloc_regs, i)) 1968 continue; 1969 1970 if (find_regno_note (insn, REG_DEAD, i) == NULL_RTX 1971 && ! REGNO_REG_SET_P (reg_pending_sets, i) 1972 && ! REGNO_REG_SET_P (reg_pending_clobbers, i)) 1973 /* Ignore use which is not dying. */ 1974 continue; 1975 1976 use = create_insn_reg_use (i, insn); 1977 use->next_regno_use = use; 1978 reg_last = &deps->reg_last[i]; 1979 1980 /* Create the cycle list of uses. */ 1981 for (rtx_insn_list *list = reg_last->uses; list; list = list->next ()) 1982 { 1983 use2 = create_insn_reg_use (i, list->insn ()); 1984 next = use->next_regno_use; 1985 use->next_regno_use = use2; 1986 use2->next_regno_use = next; 1987 } 1988 } 1989} 1990 1991/* Register pressure info for the currently processed insn. */ 1992static struct reg_pressure_data reg_pressure_info[N_REG_CLASSES]; 1993 1994/* Return TRUE if INSN has the use structure for REGNO. */ 1995static bool 1996insn_use_p (rtx insn, int regno) 1997{ 1998 struct reg_use_data *use; 1999 2000 for (use = INSN_REG_USE_LIST (insn); use != NULL; use = use->next_insn_use) 2001 if (use->regno == regno) 2002 return true; 2003 return false; 2004} 2005 2006/* Update the register pressure info after birth of pseudo register REGNO 2007 in INSN. Arguments CLOBBER_P and UNUSED_P say correspondingly that 2008 the register is in clobber or unused after the insn. */ 2009static void 2010mark_insn_pseudo_birth (rtx insn, int regno, bool clobber_p, bool unused_p) 2011{ 2012 int incr, new_incr; 2013 enum reg_class cl; 2014 2015 gcc_assert (regno >= FIRST_PSEUDO_REGISTER); 2016 cl = sched_regno_pressure_class[regno]; 2017 if (cl != NO_REGS) 2018 { 2019 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)]; 2020 if (clobber_p) 2021 { 2022 new_incr = reg_pressure_info[cl].clobber_increase + incr; 2023 reg_pressure_info[cl].clobber_increase = new_incr; 2024 } 2025 else if (unused_p) 2026 { 2027 new_incr = reg_pressure_info[cl].unused_set_increase + incr; 2028 reg_pressure_info[cl].unused_set_increase = new_incr; 2029 } 2030 else 2031 { 2032 new_incr = reg_pressure_info[cl].set_increase + incr; 2033 reg_pressure_info[cl].set_increase = new_incr; 2034 if (! insn_use_p (insn, regno)) 2035 reg_pressure_info[cl].change += incr; 2036 create_insn_reg_set (regno, insn); 2037 } 2038 gcc_assert (new_incr < (1 << INCREASE_BITS)); 2039 } 2040} 2041 2042/* Like mark_insn_pseudo_regno_birth except that NREGS saying how many 2043 hard registers involved in the birth. */ 2044static void 2045mark_insn_hard_regno_birth (rtx insn, int regno, int nregs, 2046 bool clobber_p, bool unused_p) 2047{ 2048 enum reg_class cl; 2049 int new_incr, last = regno + nregs; 2050 2051 while (regno < last) 2052 { 2053 gcc_assert (regno < FIRST_PSEUDO_REGISTER); 2054 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)) 2055 { 2056 cl = sched_regno_pressure_class[regno]; 2057 if (cl != NO_REGS) 2058 { 2059 if (clobber_p) 2060 { 2061 new_incr = reg_pressure_info[cl].clobber_increase + 1; 2062 reg_pressure_info[cl].clobber_increase = new_incr; 2063 } 2064 else if (unused_p) 2065 { 2066 new_incr = reg_pressure_info[cl].unused_set_increase + 1; 2067 reg_pressure_info[cl].unused_set_increase = new_incr; 2068 } 2069 else 2070 { 2071 new_incr = reg_pressure_info[cl].set_increase + 1; 2072 reg_pressure_info[cl].set_increase = new_incr; 2073 if (! insn_use_p (insn, regno)) 2074 reg_pressure_info[cl].change += 1; 2075 create_insn_reg_set (regno, insn); 2076 } 2077 gcc_assert (new_incr < (1 << INCREASE_BITS)); 2078 } 2079 } 2080 regno++; 2081 } 2082} 2083 2084/* Update the register pressure info after birth of pseudo or hard 2085 register REG in INSN. Arguments CLOBBER_P and UNUSED_P say 2086 correspondingly that the register is in clobber or unused after the 2087 insn. */ 2088static void 2089mark_insn_reg_birth (rtx insn, rtx reg, bool clobber_p, bool unused_p) 2090{ 2091 int regno; 2092 2093 if (GET_CODE (reg) == SUBREG) 2094 reg = SUBREG_REG (reg); 2095 2096 if (! REG_P (reg)) 2097 return; 2098 2099 regno = REGNO (reg); 2100 if (regno < FIRST_PSEUDO_REGISTER) 2101 mark_insn_hard_regno_birth (insn, regno, REG_NREGS (reg), 2102 clobber_p, unused_p); 2103 else 2104 mark_insn_pseudo_birth (insn, regno, clobber_p, unused_p); 2105} 2106 2107/* Update the register pressure info after death of pseudo register 2108 REGNO. */ 2109static void 2110mark_pseudo_death (int regno) 2111{ 2112 int incr; 2113 enum reg_class cl; 2114 2115 gcc_assert (regno >= FIRST_PSEUDO_REGISTER); 2116 cl = sched_regno_pressure_class[regno]; 2117 if (cl != NO_REGS) 2118 { 2119 incr = ira_reg_class_max_nregs[cl][PSEUDO_REGNO_MODE (regno)]; 2120 reg_pressure_info[cl].change -= incr; 2121 } 2122} 2123 2124/* Like mark_pseudo_death except that NREGS saying how many hard 2125 registers involved in the death. */ 2126static void 2127mark_hard_regno_death (int regno, int nregs) 2128{ 2129 enum reg_class cl; 2130 int last = regno + nregs; 2131 2132 while (regno < last) 2133 { 2134 gcc_assert (regno < FIRST_PSEUDO_REGISTER); 2135 if (! TEST_HARD_REG_BIT (ira_no_alloc_regs, regno)) 2136 { 2137 cl = sched_regno_pressure_class[regno]; 2138 if (cl != NO_REGS) 2139 reg_pressure_info[cl].change -= 1; 2140 } 2141 regno++; 2142 } 2143} 2144 2145/* Update the register pressure info after death of pseudo or hard 2146 register REG. */ 2147static void 2148mark_reg_death (rtx reg) 2149{ 2150 int regno; 2151 2152 if (GET_CODE (reg) == SUBREG) 2153 reg = SUBREG_REG (reg); 2154 2155 if (! REG_P (reg)) 2156 return; 2157 2158 regno = REGNO (reg); 2159 if (regno < FIRST_PSEUDO_REGISTER) 2160 mark_hard_regno_death (regno, REG_NREGS (reg)); 2161 else 2162 mark_pseudo_death (regno); 2163} 2164 2165/* Process SETTER of REG. DATA is an insn containing the setter. */ 2166static void 2167mark_insn_reg_store (rtx reg, const_rtx setter, void *data) 2168{ 2169 if (setter != NULL_RTX && GET_CODE (setter) != SET) 2170 return; 2171 mark_insn_reg_birth 2172 ((rtx) data, reg, false, 2173 find_reg_note ((const_rtx) data, REG_UNUSED, reg) != NULL_RTX); 2174} 2175 2176/* Like mark_insn_reg_store except notice just CLOBBERs; ignore SETs. */ 2177static void 2178mark_insn_reg_clobber (rtx reg, const_rtx setter, void *data) 2179{ 2180 if (GET_CODE (setter) == CLOBBER) 2181 mark_insn_reg_birth ((rtx) data, reg, true, false); 2182} 2183 2184/* Set up reg pressure info related to INSN. */ 2185void 2186init_insn_reg_pressure_info (rtx_insn *insn) 2187{ 2188 int i, len; 2189 enum reg_class cl; 2190 static struct reg_pressure_data *pressure_info; 2191 rtx link; 2192 2193 gcc_assert (sched_pressure != SCHED_PRESSURE_NONE); 2194 2195 if (! INSN_P (insn)) 2196 return; 2197 2198 for (i = 0; i < ira_pressure_classes_num; i++) 2199 { 2200 cl = ira_pressure_classes[i]; 2201 reg_pressure_info[cl].clobber_increase = 0; 2202 reg_pressure_info[cl].set_increase = 0; 2203 reg_pressure_info[cl].unused_set_increase = 0; 2204 reg_pressure_info[cl].change = 0; 2205 } 2206 2207 note_stores (insn, mark_insn_reg_clobber, insn); 2208 2209 note_stores (insn, mark_insn_reg_store, insn); 2210 2211 if (AUTO_INC_DEC) 2212 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 2213 if (REG_NOTE_KIND (link) == REG_INC) 2214 mark_insn_reg_store (XEXP (link, 0), NULL_RTX, insn); 2215 2216 for (link = REG_NOTES (insn); link; link = XEXP (link, 1)) 2217 if (REG_NOTE_KIND (link) == REG_DEAD) 2218 mark_reg_death (XEXP (link, 0)); 2219 2220 len = sizeof (struct reg_pressure_data) * ira_pressure_classes_num; 2221 pressure_info 2222 = INSN_REG_PRESSURE (insn) = (struct reg_pressure_data *) xmalloc (len); 2223 if (sched_pressure == SCHED_PRESSURE_WEIGHTED) 2224 INSN_MAX_REG_PRESSURE (insn) = (int *) xcalloc (ira_pressure_classes_num 2225 * sizeof (int), 1); 2226 for (i = 0; i < ira_pressure_classes_num; i++) 2227 { 2228 cl = ira_pressure_classes[i]; 2229 pressure_info[i].clobber_increase 2230 = reg_pressure_info[cl].clobber_increase; 2231 pressure_info[i].set_increase = reg_pressure_info[cl].set_increase; 2232 pressure_info[i].unused_set_increase 2233 = reg_pressure_info[cl].unused_set_increase; 2234 pressure_info[i].change = reg_pressure_info[cl].change; 2235 } 2236} 2237 2238 2239 2240 2241/* Internal variable for sched_analyze_[12] () functions. 2242 If it is nonzero, this means that sched_analyze_[12] looks 2243 at the most toplevel SET. */ 2244static bool can_start_lhs_rhs_p; 2245 2246/* Extend reg info for the deps context DEPS given that 2247 we have just generated a register numbered REGNO. */ 2248static void 2249extend_deps_reg_info (class deps_desc *deps, int regno) 2250{ 2251 int max_regno = regno + 1; 2252 2253 gcc_assert (!reload_completed); 2254 2255 /* In a readonly context, it would not hurt to extend info, 2256 but it should not be needed. */ 2257 if (reload_completed && deps->readonly) 2258 { 2259 deps->max_reg = max_regno; 2260 return; 2261 } 2262 2263 if (max_regno > deps->max_reg) 2264 { 2265 deps->reg_last = XRESIZEVEC (struct deps_reg, deps->reg_last, 2266 max_regno); 2267 memset (&deps->reg_last[deps->max_reg], 2268 0, (max_regno - deps->max_reg) 2269 * sizeof (struct deps_reg)); 2270 deps->max_reg = max_regno; 2271 } 2272} 2273 2274/* Extends REG_INFO_P if needed. */ 2275void 2276maybe_extend_reg_info_p (void) 2277{ 2278 /* Extend REG_INFO_P, if needed. */ 2279 if ((unsigned int)max_regno - 1 >= reg_info_p_size) 2280 { 2281 size_t new_reg_info_p_size = max_regno + 128; 2282 2283 gcc_assert (!reload_completed && sel_sched_p ()); 2284 2285 reg_info_p = (struct reg_info_t *) xrecalloc (reg_info_p, 2286 new_reg_info_p_size, 2287 reg_info_p_size, 2288 sizeof (*reg_info_p)); 2289 reg_info_p_size = new_reg_info_p_size; 2290 } 2291} 2292 2293/* Analyze a single reference to register (reg:MODE REGNO) in INSN. 2294 The type of the reference is specified by REF and can be SET, 2295 CLOBBER, PRE_DEC, POST_DEC, PRE_INC, POST_INC or USE. */ 2296 2297static void 2298sched_analyze_reg (class deps_desc *deps, int regno, machine_mode mode, 2299 enum rtx_code ref, rtx_insn *insn) 2300{ 2301 /* We could emit new pseudos in renaming. Extend the reg structures. */ 2302 if (!reload_completed && sel_sched_p () 2303 && (regno >= max_reg_num () - 1 || regno >= deps->max_reg)) 2304 extend_deps_reg_info (deps, regno); 2305 2306 maybe_extend_reg_info_p (); 2307 2308 /* A hard reg in a wide mode may really be multiple registers. 2309 If so, mark all of them just like the first. */ 2310 if (regno < FIRST_PSEUDO_REGISTER) 2311 { 2312 int i = hard_regno_nregs (regno, mode); 2313 if (ref == SET) 2314 { 2315 while (--i >= 0) 2316 note_reg_set (regno + i); 2317 } 2318 else if (ref == USE) 2319 { 2320 while (--i >= 0) 2321 note_reg_use (regno + i); 2322 } 2323 else 2324 { 2325 while (--i >= 0) 2326 note_reg_clobber (regno + i); 2327 } 2328 } 2329 2330 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 2331 it does not reload. Ignore these as they have served their 2332 purpose already. */ 2333 else if (regno >= deps->max_reg) 2334 { 2335 enum rtx_code code = GET_CODE (PATTERN (insn)); 2336 gcc_assert (code == USE || code == CLOBBER); 2337 } 2338 2339 else 2340 { 2341 if (ref == SET) 2342 note_reg_set (regno); 2343 else if (ref == USE) 2344 note_reg_use (regno); 2345 else 2346 note_reg_clobber (regno); 2347 2348 /* Pseudos that are REG_EQUIV to something may be replaced 2349 by that during reloading. We need only add dependencies for 2350 the address in the REG_EQUIV note. */ 2351 if (!reload_completed && get_reg_known_equiv_p (regno)) 2352 { 2353 rtx t = get_reg_known_value (regno); 2354 if (MEM_P (t)) 2355 sched_analyze_2 (deps, XEXP (t, 0), insn); 2356 } 2357 2358 /* Don't let it cross a call after scheduling if it doesn't 2359 already cross one. */ 2360 if (REG_N_CALLS_CROSSED (regno) == 0) 2361 { 2362 if (!deps->readonly && ref == USE && !DEBUG_INSN_P (insn)) 2363 deps->sched_before_next_call 2364 = alloc_INSN_LIST (insn, deps->sched_before_next_call); 2365 else 2366 add_dependence_list (insn, deps->last_function_call, 1, 2367 REG_DEP_ANTI, false); 2368 } 2369 } 2370} 2371 2372/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC 2373 rtx, X, creating all dependencies generated by the write to the 2374 destination of X, and reads of everything mentioned. */ 2375 2376static void 2377sched_analyze_1 (class deps_desc *deps, rtx x, rtx_insn *insn) 2378{ 2379 rtx dest = XEXP (x, 0); 2380 enum rtx_code code = GET_CODE (x); 2381 bool cslr_p = can_start_lhs_rhs_p; 2382 2383 can_start_lhs_rhs_p = false; 2384 2385 gcc_assert (dest); 2386 if (dest == 0) 2387 return; 2388 2389 if (cslr_p && sched_deps_info->start_lhs) 2390 sched_deps_info->start_lhs (dest); 2391 2392 if (GET_CODE (dest) == PARALLEL) 2393 { 2394 int i; 2395 2396 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) 2397 if (XEXP (XVECEXP (dest, 0, i), 0) != 0) 2398 sched_analyze_1 (deps, 2399 gen_rtx_CLOBBER (VOIDmode, 2400 XEXP (XVECEXP (dest, 0, i), 0)), 2401 insn); 2402 2403 if (cslr_p && sched_deps_info->finish_lhs) 2404 sched_deps_info->finish_lhs (); 2405 2406 if (code == SET) 2407 { 2408 can_start_lhs_rhs_p = cslr_p; 2409 2410 sched_analyze_2 (deps, SET_SRC (x), insn); 2411 2412 can_start_lhs_rhs_p = false; 2413 } 2414 2415 return; 2416 } 2417 2418 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG 2419 || GET_CODE (dest) == ZERO_EXTRACT) 2420 { 2421 if (GET_CODE (dest) == STRICT_LOW_PART 2422 || GET_CODE (dest) == ZERO_EXTRACT 2423 || read_modify_subreg_p (dest)) 2424 { 2425 /* These both read and modify the result. We must handle 2426 them as writes to get proper dependencies for following 2427 instructions. We must handle them as reads to get proper 2428 dependencies from this to previous instructions. 2429 Thus we need to call sched_analyze_2. */ 2430 2431 sched_analyze_2 (deps, XEXP (dest, 0), insn); 2432 } 2433 if (GET_CODE (dest) == ZERO_EXTRACT) 2434 { 2435 /* The second and third arguments are values read by this insn. */ 2436 sched_analyze_2 (deps, XEXP (dest, 1), insn); 2437 sched_analyze_2 (deps, XEXP (dest, 2), insn); 2438 } 2439 dest = XEXP (dest, 0); 2440 } 2441 2442 if (REG_P (dest)) 2443 { 2444 int regno = REGNO (dest); 2445 machine_mode mode = GET_MODE (dest); 2446 2447 sched_analyze_reg (deps, regno, mode, code, insn); 2448 2449#ifdef STACK_REGS 2450 /* Treat all writes to a stack register as modifying the TOS. */ 2451 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG) 2452 { 2453 /* Avoid analyzing the same register twice. */ 2454 if (regno != FIRST_STACK_REG) 2455 sched_analyze_reg (deps, FIRST_STACK_REG, mode, code, insn); 2456 2457 add_to_hard_reg_set (&implicit_reg_pending_uses, mode, 2458 FIRST_STACK_REG); 2459 } 2460#endif 2461 } 2462 else if (MEM_P (dest)) 2463 { 2464 /* Writing memory. */ 2465 rtx t = dest; 2466 2467 if (sched_deps_info->use_cselib) 2468 { 2469 machine_mode address_mode = get_address_mode (dest); 2470 2471 t = shallow_copy_rtx (dest); 2472 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1, 2473 GET_MODE (t), insn); 2474 XEXP (t, 0) 2475 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t), 2476 insn); 2477 } 2478 t = canon_rtx (t); 2479 2480 /* Pending lists can't get larger with a readonly context. */ 2481 if (!deps->readonly 2482 && ((deps->pending_read_list_length + deps->pending_write_list_length) 2483 >= param_max_pending_list_length)) 2484 { 2485 /* Flush all pending reads and writes to prevent the pending lists 2486 from getting any larger. Insn scheduling runs too slowly when 2487 these lists get long. When compiling GCC with itself, 2488 this flush occurs 8 times for sparc, and 10 times for m88k using 2489 the default value of 32. */ 2490 flush_pending_lists (deps, insn, false, true); 2491 } 2492 else 2493 { 2494 rtx_insn_list *pending; 2495 rtx_expr_list *pending_mem; 2496 2497 pending = deps->pending_read_insns; 2498 pending_mem = deps->pending_read_mems; 2499 while (pending) 2500 { 2501 if (anti_dependence (pending_mem->element (), t) 2502 && ! sched_insns_conditions_mutex_p (insn, pending->insn ())) 2503 note_mem_dep (t, pending_mem->element (), pending->insn (), 2504 DEP_ANTI); 2505 2506 pending = pending->next (); 2507 pending_mem = pending_mem->next (); 2508 } 2509 2510 pending = deps->pending_write_insns; 2511 pending_mem = deps->pending_write_mems; 2512 while (pending) 2513 { 2514 if (output_dependence (pending_mem->element (), t) 2515 && ! sched_insns_conditions_mutex_p (insn, pending->insn ())) 2516 note_mem_dep (t, pending_mem->element (), 2517 pending->insn (), 2518 DEP_OUTPUT); 2519 2520 pending = pending->next (); 2521 pending_mem = pending_mem-> next (); 2522 } 2523 2524 add_dependence_list (insn, deps->last_pending_memory_flush, 1, 2525 REG_DEP_ANTI, true); 2526 add_dependence_list (insn, deps->pending_jump_insns, 1, 2527 REG_DEP_CONTROL, true); 2528 2529 if (!deps->readonly) 2530 add_insn_mem_dependence (deps, false, insn, dest); 2531 } 2532 sched_analyze_2 (deps, XEXP (dest, 0), insn); 2533 } 2534 2535 if (cslr_p && sched_deps_info->finish_lhs) 2536 sched_deps_info->finish_lhs (); 2537 2538 /* Analyze reads. */ 2539 if (GET_CODE (x) == SET) 2540 { 2541 can_start_lhs_rhs_p = cslr_p; 2542 2543 sched_analyze_2 (deps, SET_SRC (x), insn); 2544 2545 can_start_lhs_rhs_p = false; 2546 } 2547} 2548 2549/* Analyze the uses of memory and registers in rtx X in INSN. */ 2550static void 2551sched_analyze_2 (class deps_desc *deps, rtx x, rtx_insn *insn) 2552{ 2553 int i; 2554 int j; 2555 enum rtx_code code; 2556 const char *fmt; 2557 bool cslr_p = can_start_lhs_rhs_p; 2558 2559 can_start_lhs_rhs_p = false; 2560 2561 gcc_assert (x); 2562 if (x == 0) 2563 return; 2564 2565 if (cslr_p && sched_deps_info->start_rhs) 2566 sched_deps_info->start_rhs (x); 2567 2568 code = GET_CODE (x); 2569 2570 switch (code) 2571 { 2572 CASE_CONST_ANY: 2573 case SYMBOL_REF: 2574 case CONST: 2575 case LABEL_REF: 2576 /* Ignore constants. */ 2577 if (cslr_p && sched_deps_info->finish_rhs) 2578 sched_deps_info->finish_rhs (); 2579 2580 return; 2581 2582 case CC0: 2583 if (!HAVE_cc0) 2584 gcc_unreachable (); 2585 2586 /* User of CC0 depends on immediately preceding insn. */ 2587 SCHED_GROUP_P (insn) = 1; 2588 /* Don't move CC0 setter to another block (it can set up the 2589 same flag for previous CC0 users which is safe). */ 2590 CANT_MOVE (prev_nonnote_insn (insn)) = 1; 2591 2592 if (cslr_p && sched_deps_info->finish_rhs) 2593 sched_deps_info->finish_rhs (); 2594 2595 return; 2596 2597 case REG: 2598 { 2599 int regno = REGNO (x); 2600 machine_mode mode = GET_MODE (x); 2601 2602 sched_analyze_reg (deps, regno, mode, USE, insn); 2603 2604#ifdef STACK_REGS 2605 /* Treat all reads of a stack register as modifying the TOS. */ 2606 if (regno >= FIRST_STACK_REG && regno <= LAST_STACK_REG) 2607 { 2608 /* Avoid analyzing the same register twice. */ 2609 if (regno != FIRST_STACK_REG) 2610 sched_analyze_reg (deps, FIRST_STACK_REG, mode, USE, insn); 2611 sched_analyze_reg (deps, FIRST_STACK_REG, mode, SET, insn); 2612 } 2613#endif 2614 2615 if (cslr_p && sched_deps_info->finish_rhs) 2616 sched_deps_info->finish_rhs (); 2617 2618 return; 2619 } 2620 2621 case MEM: 2622 { 2623 /* Reading memory. */ 2624 rtx_insn_list *u; 2625 rtx_insn_list *pending; 2626 rtx_expr_list *pending_mem; 2627 rtx t = x; 2628 2629 if (sched_deps_info->use_cselib) 2630 { 2631 machine_mode address_mode = get_address_mode (t); 2632 2633 t = shallow_copy_rtx (t); 2634 cselib_lookup_from_insn (XEXP (t, 0), address_mode, 1, 2635 GET_MODE (t), insn); 2636 XEXP (t, 0) 2637 = cselib_subst_to_values_from_insn (XEXP (t, 0), GET_MODE (t), 2638 insn); 2639 } 2640 2641 if (!DEBUG_INSN_P (insn)) 2642 { 2643 t = canon_rtx (t); 2644 pending = deps->pending_read_insns; 2645 pending_mem = deps->pending_read_mems; 2646 while (pending) 2647 { 2648 if (read_dependence (pending_mem->element (), t) 2649 && ! sched_insns_conditions_mutex_p (insn, 2650 pending->insn ())) 2651 note_mem_dep (t, pending_mem->element (), 2652 pending->insn (), 2653 DEP_ANTI); 2654 2655 pending = pending->next (); 2656 pending_mem = pending_mem->next (); 2657 } 2658 2659 pending = deps->pending_write_insns; 2660 pending_mem = deps->pending_write_mems; 2661 while (pending) 2662 { 2663 if (true_dependence (pending_mem->element (), VOIDmode, t) 2664 && ! sched_insns_conditions_mutex_p (insn, 2665 pending->insn ())) 2666 note_mem_dep (t, pending_mem->element (), 2667 pending->insn (), 2668 sched_deps_info->generate_spec_deps 2669 ? BEGIN_DATA | DEP_TRUE : DEP_TRUE); 2670 2671 pending = pending->next (); 2672 pending_mem = pending_mem->next (); 2673 } 2674 2675 for (u = deps->last_pending_memory_flush; u; u = u->next ()) 2676 add_dependence (insn, u->insn (), REG_DEP_ANTI); 2677 2678 for (u = deps->pending_jump_insns; u; u = u->next ()) 2679 if (deps_may_trap_p (x)) 2680 { 2681 if ((sched_deps_info->generate_spec_deps) 2682 && sel_sched_p () && (spec_info->mask & BEGIN_CONTROL)) 2683 { 2684 ds_t ds = set_dep_weak (DEP_ANTI, BEGIN_CONTROL, 2685 MAX_DEP_WEAK); 2686 2687 note_dep (u->insn (), ds); 2688 } 2689 else 2690 add_dependence (insn, u->insn (), REG_DEP_CONTROL); 2691 } 2692 } 2693 2694 /* Always add these dependencies to pending_reads, since 2695 this insn may be followed by a write. */ 2696 if (!deps->readonly) 2697 { 2698 if ((deps->pending_read_list_length 2699 + deps->pending_write_list_length) 2700 >= param_max_pending_list_length 2701 && !DEBUG_INSN_P (insn)) 2702 flush_pending_lists (deps, insn, true, true); 2703 add_insn_mem_dependence (deps, true, insn, x); 2704 } 2705 2706 sched_analyze_2 (deps, XEXP (x, 0), insn); 2707 2708 if (cslr_p && sched_deps_info->finish_rhs) 2709 sched_deps_info->finish_rhs (); 2710 2711 return; 2712 } 2713 2714 /* Force pending stores to memory in case a trap handler needs them. 2715 Also force pending loads from memory; loads and stores can segfault 2716 and the signal handler won't be triggered if the trap insn was moved 2717 above load or store insn. */ 2718 case TRAP_IF: 2719 flush_pending_lists (deps, insn, true, true); 2720 break; 2721 2722 case PREFETCH: 2723 if (PREFETCH_SCHEDULE_BARRIER_P (x)) 2724 reg_pending_barrier = TRUE_BARRIER; 2725 /* Prefetch insn contains addresses only. So if the prefetch 2726 address has no registers, there will be no dependencies on 2727 the prefetch insn. This is wrong with result code 2728 correctness point of view as such prefetch can be moved below 2729 a jump insn which usually generates MOVE_BARRIER preventing 2730 to move insns containing registers or memories through the 2731 barrier. It is also wrong with generated code performance 2732 point of view as prefetch withouth dependecies will have a 2733 tendency to be issued later instead of earlier. It is hard 2734 to generate accurate dependencies for prefetch insns as 2735 prefetch has only the start address but it is better to have 2736 something than nothing. */ 2737 if (!deps->readonly) 2738 { 2739 rtx x = gen_rtx_MEM (Pmode, XEXP (PATTERN (insn), 0)); 2740 if (sched_deps_info->use_cselib) 2741 cselib_lookup_from_insn (x, Pmode, true, VOIDmode, insn); 2742 add_insn_mem_dependence (deps, true, insn, x); 2743 } 2744 break; 2745 2746 case UNSPEC_VOLATILE: 2747 flush_pending_lists (deps, insn, true, true); 2748 /* FALLTHRU */ 2749 2750 case ASM_OPERANDS: 2751 case ASM_INPUT: 2752 { 2753 /* Traditional and volatile asm instructions must be considered to use 2754 and clobber all hard registers, all pseudo-registers and all of 2755 memory. So must TRAP_IF and UNSPEC_VOLATILE operations. 2756 2757 Consider for instance a volatile asm that changes the fpu rounding 2758 mode. An insn should not be moved across this even if it only uses 2759 pseudo-regs because it might give an incorrectly rounded result. */ 2760 if ((code != ASM_OPERANDS || MEM_VOLATILE_P (x)) 2761 && !DEBUG_INSN_P (insn)) 2762 reg_pending_barrier = TRUE_BARRIER; 2763 2764 /* For all ASM_OPERANDS, we must traverse the vector of input operands. 2765 We cannot just fall through here since then we would be confused 2766 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 2767 traditional asms unlike their normal usage. */ 2768 2769 if (code == ASM_OPERANDS) 2770 { 2771 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 2772 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn); 2773 2774 if (cslr_p && sched_deps_info->finish_rhs) 2775 sched_deps_info->finish_rhs (); 2776 2777 return; 2778 } 2779 break; 2780 } 2781 2782 case PRE_DEC: 2783 case POST_DEC: 2784 case PRE_INC: 2785 case POST_INC: 2786 /* These both read and modify the result. We must handle them as writes 2787 to get proper dependencies for following instructions. We must handle 2788 them as reads to get proper dependencies from this to previous 2789 instructions. Thus we need to pass them to both sched_analyze_1 2790 and sched_analyze_2. We must call sched_analyze_2 first in order 2791 to get the proper antecedent for the read. */ 2792 sched_analyze_2 (deps, XEXP (x, 0), insn); 2793 sched_analyze_1 (deps, x, insn); 2794 2795 if (cslr_p && sched_deps_info->finish_rhs) 2796 sched_deps_info->finish_rhs (); 2797 2798 return; 2799 2800 case POST_MODIFY: 2801 case PRE_MODIFY: 2802 /* op0 = op0 + op1 */ 2803 sched_analyze_2 (deps, XEXP (x, 0), insn); 2804 sched_analyze_2 (deps, XEXP (x, 1), insn); 2805 sched_analyze_1 (deps, x, insn); 2806 2807 if (cslr_p && sched_deps_info->finish_rhs) 2808 sched_deps_info->finish_rhs (); 2809 2810 return; 2811 2812 default: 2813 break; 2814 } 2815 2816 /* Other cases: walk the insn. */ 2817 fmt = GET_RTX_FORMAT (code); 2818 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 2819 { 2820 if (fmt[i] == 'e') 2821 sched_analyze_2 (deps, XEXP (x, i), insn); 2822 else if (fmt[i] == 'E') 2823 for (j = 0; j < XVECLEN (x, i); j++) 2824 sched_analyze_2 (deps, XVECEXP (x, i, j), insn); 2825 } 2826 2827 if (cslr_p && sched_deps_info->finish_rhs) 2828 sched_deps_info->finish_rhs (); 2829} 2830 2831/* Try to group two fusible insns together to prevent scheduler 2832 from scheduling them apart. */ 2833 2834static void 2835sched_macro_fuse_insns (rtx_insn *insn) 2836{ 2837 rtx_insn *prev; 2838 /* No target hook would return true for debug insn as any of the 2839 hook operand, and with very large sequences of only debug insns 2840 where on each we call sched_macro_fuse_insns it has quadratic 2841 compile time complexity. */ 2842 if (DEBUG_INSN_P (insn)) 2843 return; 2844 prev = prev_nonnote_nondebug_insn (insn); 2845 if (!prev) 2846 return; 2847 2848 if (any_condjump_p (insn)) 2849 { 2850 unsigned int condreg1, condreg2; 2851 rtx cc_reg_1; 2852 if (targetm.fixed_condition_code_regs (&condreg1, &condreg2)) 2853 { 2854 cc_reg_1 = gen_rtx_REG (CCmode, condreg1); 2855 if (reg_referenced_p (cc_reg_1, PATTERN (insn)) 2856 && modified_in_p (cc_reg_1, prev)) 2857 { 2858 if (targetm.sched.macro_fusion_pair_p (prev, insn)) 2859 SCHED_GROUP_P (insn) = 1; 2860 return; 2861 } 2862 } 2863 } 2864 2865 if (single_set (insn) && single_set (prev)) 2866 { 2867 if (targetm.sched.macro_fusion_pair_p (prev, insn)) 2868 SCHED_GROUP_P (insn) = 1; 2869 } 2870} 2871 2872/* Get the implicit reg pending clobbers for INSN and save them in TEMP. */ 2873void 2874get_implicit_reg_pending_clobbers (HARD_REG_SET *temp, rtx_insn *insn) 2875{ 2876 extract_insn (insn); 2877 preprocess_constraints (insn); 2878 alternative_mask preferred = get_preferred_alternatives (insn); 2879 ira_implicitly_set_insn_hard_regs (temp, preferred); 2880 *temp &= ~ira_no_alloc_regs; 2881} 2882 2883/* Analyze an INSN with pattern X to find all dependencies. */ 2884static void 2885sched_analyze_insn (class deps_desc *deps, rtx x, rtx_insn *insn) 2886{ 2887 RTX_CODE code = GET_CODE (x); 2888 rtx link; 2889 unsigned i; 2890 reg_set_iterator rsi; 2891 2892 if (! reload_completed) 2893 { 2894 HARD_REG_SET temp; 2895 get_implicit_reg_pending_clobbers (&temp, insn); 2896 implicit_reg_pending_clobbers |= temp; 2897 } 2898 2899 can_start_lhs_rhs_p = (NONJUMP_INSN_P (insn) 2900 && code == SET); 2901 2902 /* Group compare and branch insns for macro-fusion. */ 2903 if (!deps->readonly 2904 && targetm.sched.macro_fusion_p 2905 && targetm.sched.macro_fusion_p ()) 2906 sched_macro_fuse_insns (insn); 2907 2908 if (may_trap_p (x)) 2909 /* Avoid moving trapping instructions across function calls that might 2910 not always return. */ 2911 add_dependence_list (insn, deps->last_function_call_may_noreturn, 2912 1, REG_DEP_ANTI, true); 2913 2914 /* We must avoid creating a situation in which two successors of the 2915 current block have different unwind info after scheduling. If at any 2916 point the two paths re-join this leads to incorrect unwind info. */ 2917 /* ??? There are certain situations involving a forced frame pointer in 2918 which, with extra effort, we could fix up the unwind info at a later 2919 CFG join. However, it seems better to notice these cases earlier 2920 during prologue generation and avoid marking the frame pointer setup 2921 as frame-related at all. */ 2922 if (RTX_FRAME_RELATED_P (insn)) 2923 { 2924 /* Make sure prologue insn is scheduled before next jump. */ 2925 deps->sched_before_next_jump 2926 = alloc_INSN_LIST (insn, deps->sched_before_next_jump); 2927 2928 /* Make sure epilogue insn is scheduled after preceding jumps. */ 2929 add_dependence_list (insn, deps->last_pending_memory_flush, 1, 2930 REG_DEP_ANTI, true); 2931 add_dependence_list (insn, deps->pending_jump_insns, 1, REG_DEP_ANTI, 2932 true); 2933 } 2934 2935 if (code == COND_EXEC) 2936 { 2937 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn); 2938 2939 /* ??? Should be recording conditions so we reduce the number of 2940 false dependencies. */ 2941 x = COND_EXEC_CODE (x); 2942 code = GET_CODE (x); 2943 } 2944 if (code == SET || code == CLOBBER) 2945 { 2946 sched_analyze_1 (deps, x, insn); 2947 2948 /* Bare clobber insns are used for letting life analysis, reg-stack 2949 and others know that a value is dead. Depend on the last call 2950 instruction so that reg-stack won't get confused. */ 2951 if (code == CLOBBER) 2952 add_dependence_list (insn, deps->last_function_call, 1, 2953 REG_DEP_OUTPUT, true); 2954 } 2955 else if (code == PARALLEL) 2956 { 2957 for (i = XVECLEN (x, 0); i--;) 2958 { 2959 rtx sub = XVECEXP (x, 0, i); 2960 code = GET_CODE (sub); 2961 2962 if (code == COND_EXEC) 2963 { 2964 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); 2965 sub = COND_EXEC_CODE (sub); 2966 code = GET_CODE (sub); 2967 } 2968 else if (code == SET || code == CLOBBER) 2969 sched_analyze_1 (deps, sub, insn); 2970 else 2971 sched_analyze_2 (deps, sub, insn); 2972 } 2973 } 2974 else 2975 sched_analyze_2 (deps, x, insn); 2976 2977 /* Mark registers CLOBBERED or used by called function. */ 2978 if (CALL_P (insn)) 2979 { 2980 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 2981 { 2982 if (GET_CODE (XEXP (link, 0)) == CLOBBER) 2983 sched_analyze_1 (deps, XEXP (link, 0), insn); 2984 else if (GET_CODE (XEXP (link, 0)) != SET) 2985 sched_analyze_2 (deps, XEXP (link, 0), insn); 2986 } 2987 /* Don't schedule anything after a tail call, tail call needs 2988 to use at least all call-saved registers. */ 2989 if (SIBLING_CALL_P (insn)) 2990 reg_pending_barrier = TRUE_BARRIER; 2991 else if (find_reg_note (insn, REG_SETJMP, NULL)) 2992 reg_pending_barrier = MOVE_BARRIER; 2993 } 2994 2995 if (JUMP_P (insn)) 2996 { 2997 rtx_insn *next = next_nonnote_nondebug_insn (insn); 2998 /* ??? For tablejumps, the barrier may appear not immediately after 2999 the jump, but after a label and a jump_table_data insn. */ 3000 if (next && LABEL_P (next) && NEXT_INSN (next) 3001 && JUMP_TABLE_DATA_P (NEXT_INSN (next))) 3002 next = NEXT_INSN (NEXT_INSN (next)); 3003 if (next && BARRIER_P (next)) 3004 reg_pending_barrier = MOVE_BARRIER; 3005 else 3006 { 3007 rtx_insn_list *pending; 3008 rtx_expr_list *pending_mem; 3009 3010 if (sched_deps_info->compute_jump_reg_dependencies) 3011 { 3012 (*sched_deps_info->compute_jump_reg_dependencies) 3013 (insn, reg_pending_control_uses); 3014 3015 /* Make latency of jump equal to 0 by using anti-dependence. */ 3016 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi) 3017 { 3018 struct deps_reg *reg_last = &deps->reg_last[i]; 3019 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, 3020 false); 3021 add_dependence_list (insn, reg_last->implicit_sets, 3022 0, REG_DEP_ANTI, false); 3023 add_dependence_list (insn, reg_last->clobbers, 0, 3024 REG_DEP_ANTI, false); 3025 } 3026 } 3027 3028 /* All memory writes and volatile reads must happen before the 3029 jump. Non-volatile reads must happen before the jump iff 3030 the result is needed by the above register used mask. */ 3031 3032 pending = deps->pending_write_insns; 3033 pending_mem = deps->pending_write_mems; 3034 while (pending) 3035 { 3036 if (! sched_insns_conditions_mutex_p (insn, pending->insn ())) 3037 add_dependence (insn, pending->insn (), 3038 REG_DEP_OUTPUT); 3039 pending = pending->next (); 3040 pending_mem = pending_mem->next (); 3041 } 3042 3043 pending = deps->pending_read_insns; 3044 pending_mem = deps->pending_read_mems; 3045 while (pending) 3046 { 3047 if (MEM_VOLATILE_P (pending_mem->element ()) 3048 && ! sched_insns_conditions_mutex_p (insn, pending->insn ())) 3049 add_dependence (insn, pending->insn (), 3050 REG_DEP_OUTPUT); 3051 pending = pending->next (); 3052 pending_mem = pending_mem->next (); 3053 } 3054 3055 add_dependence_list (insn, deps->last_pending_memory_flush, 1, 3056 REG_DEP_ANTI, true); 3057 add_dependence_list (insn, deps->pending_jump_insns, 1, 3058 REG_DEP_ANTI, true); 3059 } 3060 } 3061 3062 /* If this instruction can throw an exception, then moving it changes 3063 where block boundaries fall. This is mighty confusing elsewhere. 3064 Therefore, prevent such an instruction from being moved. Same for 3065 non-jump instructions that define block boundaries. 3066 ??? Unclear whether this is still necessary in EBB mode. If not, 3067 add_branch_dependences should be adjusted for RGN mode instead. */ 3068 if (((CALL_P (insn) || JUMP_P (insn)) && can_throw_internal (insn)) 3069 || (NONJUMP_INSN_P (insn) && control_flow_insn_p (insn))) 3070 reg_pending_barrier = MOVE_BARRIER; 3071 3072 if (sched_pressure != SCHED_PRESSURE_NONE) 3073 { 3074 setup_insn_reg_uses (deps, insn); 3075 init_insn_reg_pressure_info (insn); 3076 } 3077 3078 /* Add register dependencies for insn. */ 3079 if (DEBUG_INSN_P (insn)) 3080 { 3081 rtx_insn *prev = deps->last_debug_insn; 3082 rtx_insn_list *u; 3083 3084 if (!deps->readonly) 3085 deps->last_debug_insn = insn; 3086 3087 if (prev) 3088 add_dependence (insn, prev, REG_DEP_ANTI); 3089 3090 add_dependence_list (insn, deps->last_function_call, 1, 3091 REG_DEP_ANTI, false); 3092 3093 if (!sel_sched_p ()) 3094 for (u = deps->last_pending_memory_flush; u; u = u->next ()) 3095 add_dependence (insn, u->insn (), REG_DEP_ANTI); 3096 3097 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi) 3098 { 3099 struct deps_reg *reg_last = &deps->reg_last[i]; 3100 add_dependence_list (insn, reg_last->sets, 1, REG_DEP_ANTI, false); 3101 /* There's no point in making REG_DEP_CONTROL dependencies for 3102 debug insns. */ 3103 add_dependence_list (insn, reg_last->clobbers, 1, REG_DEP_ANTI, 3104 false); 3105 3106 if (!deps->readonly) 3107 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 3108 } 3109 CLEAR_REG_SET (reg_pending_uses); 3110 3111 /* Quite often, a debug insn will refer to stuff in the 3112 previous instruction, but the reason we want this 3113 dependency here is to make sure the scheduler doesn't 3114 gratuitously move a debug insn ahead. This could dirty 3115 DF flags and cause additional analysis that wouldn't have 3116 occurred in compilation without debug insns, and such 3117 additional analysis can modify the generated code. */ 3118 prev = PREV_INSN (insn); 3119 3120 if (prev && NONDEBUG_INSN_P (prev)) 3121 add_dependence (insn, prev, REG_DEP_ANTI); 3122 } 3123 else 3124 { 3125 regset_head set_or_clobbered; 3126 3127 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, rsi) 3128 { 3129 struct deps_reg *reg_last = &deps->reg_last[i]; 3130 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false); 3131 add_dependence_list (insn, reg_last->implicit_sets, 0, REG_DEP_ANTI, 3132 false); 3133 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE, 3134 false); 3135 3136 if (!deps->readonly) 3137 { 3138 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 3139 reg_last->uses_length++; 3140 } 3141 } 3142 3143 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3144 if (TEST_HARD_REG_BIT (implicit_reg_pending_uses, i)) 3145 { 3146 struct deps_reg *reg_last = &deps->reg_last[i]; 3147 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_TRUE, false); 3148 add_dependence_list (insn, reg_last->implicit_sets, 0, 3149 REG_DEP_ANTI, false); 3150 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_TRUE, 3151 false); 3152 3153 if (!deps->readonly) 3154 { 3155 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 3156 reg_last->uses_length++; 3157 } 3158 } 3159 3160 if (targetm.sched.exposed_pipeline) 3161 { 3162 INIT_REG_SET (&set_or_clobbered); 3163 bitmap_ior (&set_or_clobbered, reg_pending_clobbers, 3164 reg_pending_sets); 3165 EXECUTE_IF_SET_IN_REG_SET (&set_or_clobbered, 0, i, rsi) 3166 { 3167 struct deps_reg *reg_last = &deps->reg_last[i]; 3168 rtx list; 3169 for (list = reg_last->uses; list; list = XEXP (list, 1)) 3170 { 3171 rtx other = XEXP (list, 0); 3172 if (INSN_CACHED_COND (other) != const_true_rtx 3173 && refers_to_regno_p (i, INSN_CACHED_COND (other))) 3174 INSN_CACHED_COND (other) = const_true_rtx; 3175 } 3176 } 3177 } 3178 3179 /* If the current insn is conditional, we can't free any 3180 of the lists. */ 3181 if (sched_has_condition_p (insn)) 3182 { 3183 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi) 3184 { 3185 struct deps_reg *reg_last = &deps->reg_last[i]; 3186 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT, 3187 false); 3188 add_dependence_list (insn, reg_last->implicit_sets, 0, 3189 REG_DEP_ANTI, false); 3190 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, 3191 false); 3192 add_dependence_list (insn, reg_last->control_uses, 0, 3193 REG_DEP_CONTROL, false); 3194 3195 if (!deps->readonly) 3196 { 3197 reg_last->clobbers 3198 = alloc_INSN_LIST (insn, reg_last->clobbers); 3199 reg_last->clobbers_length++; 3200 } 3201 } 3202 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi) 3203 { 3204 struct deps_reg *reg_last = &deps->reg_last[i]; 3205 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT, 3206 false); 3207 add_dependence_list (insn, reg_last->implicit_sets, 0, 3208 REG_DEP_ANTI, false); 3209 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_OUTPUT, 3210 false); 3211 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, 3212 false); 3213 add_dependence_list (insn, reg_last->control_uses, 0, 3214 REG_DEP_CONTROL, false); 3215 3216 if (!deps->readonly) 3217 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 3218 } 3219 } 3220 else 3221 { 3222 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, rsi) 3223 { 3224 struct deps_reg *reg_last = &deps->reg_last[i]; 3225 if (reg_last->uses_length >= param_max_pending_list_length 3226 || reg_last->clobbers_length >= param_max_pending_list_length) 3227 { 3228 add_dependence_list_and_free (deps, insn, ®_last->sets, 0, 3229 REG_DEP_OUTPUT, false); 3230 add_dependence_list_and_free (deps, insn, 3231 ®_last->implicit_sets, 0, 3232 REG_DEP_ANTI, false); 3233 add_dependence_list_and_free (deps, insn, ®_last->uses, 0, 3234 REG_DEP_ANTI, false); 3235 add_dependence_list_and_free (deps, insn, 3236 ®_last->control_uses, 0, 3237 REG_DEP_ANTI, false); 3238 add_dependence_list_and_free (deps, insn, 3239 ®_last->clobbers, 0, 3240 REG_DEP_OUTPUT, false); 3241 3242 if (!deps->readonly) 3243 { 3244 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 3245 reg_last->clobbers_length = 0; 3246 reg_last->uses_length = 0; 3247 } 3248 } 3249 else 3250 { 3251 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_OUTPUT, 3252 false); 3253 add_dependence_list (insn, reg_last->implicit_sets, 0, 3254 REG_DEP_ANTI, false); 3255 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, 3256 false); 3257 add_dependence_list (insn, reg_last->control_uses, 0, 3258 REG_DEP_CONTROL, false); 3259 } 3260 3261 if (!deps->readonly) 3262 { 3263 reg_last->clobbers_length++; 3264 reg_last->clobbers 3265 = alloc_INSN_LIST (insn, reg_last->clobbers); 3266 } 3267 } 3268 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, rsi) 3269 { 3270 struct deps_reg *reg_last = &deps->reg_last[i]; 3271 3272 add_dependence_list_and_free (deps, insn, ®_last->sets, 0, 3273 REG_DEP_OUTPUT, false); 3274 add_dependence_list_and_free (deps, insn, 3275 ®_last->implicit_sets, 3276 0, REG_DEP_ANTI, false); 3277 add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0, 3278 REG_DEP_OUTPUT, false); 3279 add_dependence_list_and_free (deps, insn, ®_last->uses, 0, 3280 REG_DEP_ANTI, false); 3281 add_dependence_list (insn, reg_last->control_uses, 0, 3282 REG_DEP_CONTROL, false); 3283 3284 if (!deps->readonly) 3285 { 3286 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 3287 reg_last->uses_length = 0; 3288 reg_last->clobbers_length = 0; 3289 } 3290 } 3291 } 3292 if (!deps->readonly) 3293 { 3294 EXECUTE_IF_SET_IN_REG_SET (reg_pending_control_uses, 0, i, rsi) 3295 { 3296 struct deps_reg *reg_last = &deps->reg_last[i]; 3297 reg_last->control_uses 3298 = alloc_INSN_LIST (insn, reg_last->control_uses); 3299 } 3300 } 3301 } 3302 3303 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3304 if (TEST_HARD_REG_BIT (implicit_reg_pending_clobbers, i)) 3305 { 3306 struct deps_reg *reg_last = &deps->reg_last[i]; 3307 add_dependence_list (insn, reg_last->sets, 0, REG_DEP_ANTI, false); 3308 add_dependence_list (insn, reg_last->clobbers, 0, REG_DEP_ANTI, false); 3309 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, false); 3310 add_dependence_list (insn, reg_last->control_uses, 0, REG_DEP_ANTI, 3311 false); 3312 3313 if (!deps->readonly) 3314 reg_last->implicit_sets 3315 = alloc_INSN_LIST (insn, reg_last->implicit_sets); 3316 } 3317 3318 if (!deps->readonly) 3319 { 3320 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); 3321 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); 3322 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); 3323 IOR_REG_SET_HRS (&deps->reg_last_in_use, 3324 implicit_reg_pending_uses 3325 | implicit_reg_pending_clobbers); 3326 3327 /* Set up the pending barrier found. */ 3328 deps->last_reg_pending_barrier = reg_pending_barrier; 3329 } 3330 3331 CLEAR_REG_SET (reg_pending_uses); 3332 CLEAR_REG_SET (reg_pending_clobbers); 3333 CLEAR_REG_SET (reg_pending_sets); 3334 CLEAR_REG_SET (reg_pending_control_uses); 3335 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers); 3336 CLEAR_HARD_REG_SET (implicit_reg_pending_uses); 3337 3338 /* Add dependencies if a scheduling barrier was found. */ 3339 if (reg_pending_barrier) 3340 { 3341 /* In the case of barrier the most added dependencies are not 3342 real, so we use anti-dependence here. */ 3343 if (sched_has_condition_p (insn)) 3344 { 3345 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi) 3346 { 3347 struct deps_reg *reg_last = &deps->reg_last[i]; 3348 add_dependence_list (insn, reg_last->uses, 0, REG_DEP_ANTI, 3349 true); 3350 add_dependence_list (insn, reg_last->sets, 0, 3351 reg_pending_barrier == TRUE_BARRIER 3352 ? REG_DEP_TRUE : REG_DEP_ANTI, true); 3353 add_dependence_list (insn, reg_last->implicit_sets, 0, 3354 REG_DEP_ANTI, true); 3355 add_dependence_list (insn, reg_last->clobbers, 0, 3356 reg_pending_barrier == TRUE_BARRIER 3357 ? REG_DEP_TRUE : REG_DEP_ANTI, true); 3358 } 3359 } 3360 else 3361 { 3362 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi) 3363 { 3364 struct deps_reg *reg_last = &deps->reg_last[i]; 3365 add_dependence_list_and_free (deps, insn, ®_last->uses, 0, 3366 REG_DEP_ANTI, true); 3367 add_dependence_list_and_free (deps, insn, 3368 ®_last->control_uses, 0, 3369 REG_DEP_CONTROL, true); 3370 add_dependence_list_and_free (deps, insn, ®_last->sets, 0, 3371 reg_pending_barrier == TRUE_BARRIER 3372 ? REG_DEP_TRUE : REG_DEP_ANTI, 3373 true); 3374 add_dependence_list_and_free (deps, insn, 3375 ®_last->implicit_sets, 0, 3376 REG_DEP_ANTI, true); 3377 add_dependence_list_and_free (deps, insn, ®_last->clobbers, 0, 3378 reg_pending_barrier == TRUE_BARRIER 3379 ? REG_DEP_TRUE : REG_DEP_ANTI, 3380 true); 3381 3382 if (!deps->readonly) 3383 { 3384 reg_last->uses_length = 0; 3385 reg_last->clobbers_length = 0; 3386 } 3387 } 3388 } 3389 3390 if (!deps->readonly) 3391 for (i = 0; i < (unsigned)deps->max_reg; i++) 3392 { 3393 struct deps_reg *reg_last = &deps->reg_last[i]; 3394 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 3395 SET_REGNO_REG_SET (&deps->reg_last_in_use, i); 3396 } 3397 3398 /* Don't flush pending lists on speculative checks for 3399 selective scheduling. */ 3400 if (!sel_sched_p () || !sel_insn_is_speculation_check (insn)) 3401 flush_pending_lists (deps, insn, true, true); 3402 3403 reg_pending_barrier = NOT_A_BARRIER; 3404 } 3405 3406 /* If a post-call group is still open, see if it should remain so. 3407 This insn must be a simple move of a hard reg to a pseudo or 3408 vice-versa. 3409 3410 We must avoid moving these insns for correctness on targets 3411 with small register classes, and for special registers like 3412 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all 3413 hard regs for all targets. */ 3414 3415 if (deps->in_post_call_group_p) 3416 { 3417 rtx tmp, set = single_set (insn); 3418 int src_regno, dest_regno; 3419 3420 if (set == NULL) 3421 { 3422 if (DEBUG_INSN_P (insn)) 3423 /* We don't want to mark debug insns as part of the same 3424 sched group. We know they really aren't, but if we use 3425 debug insns to tell that a call group is over, we'll 3426 get different code if debug insns are not there and 3427 instructions that follow seem like they should be part 3428 of the call group. 3429 3430 Also, if we did, chain_to_prev_insn would move the 3431 deps of the debug insn to the call insn, modifying 3432 non-debug post-dependency counts of the debug insn 3433 dependencies and otherwise messing with the scheduling 3434 order. 3435 3436 Instead, let such debug insns be scheduled freely, but 3437 keep the call group open in case there are insns that 3438 should be part of it afterwards. Since we grant debug 3439 insns higher priority than even sched group insns, it 3440 will all turn out all right. */ 3441 goto debug_dont_end_call_group; 3442 else 3443 goto end_call_group; 3444 } 3445 3446 tmp = SET_DEST (set); 3447 if (GET_CODE (tmp) == SUBREG) 3448 tmp = SUBREG_REG (tmp); 3449 if (REG_P (tmp)) 3450 dest_regno = REGNO (tmp); 3451 else 3452 goto end_call_group; 3453 3454 tmp = SET_SRC (set); 3455 if (GET_CODE (tmp) == SUBREG) 3456 tmp = SUBREG_REG (tmp); 3457 if ((GET_CODE (tmp) == PLUS 3458 || GET_CODE (tmp) == MINUS) 3459 && REG_P (XEXP (tmp, 0)) 3460 && REGNO (XEXP (tmp, 0)) == STACK_POINTER_REGNUM 3461 && dest_regno == STACK_POINTER_REGNUM) 3462 src_regno = STACK_POINTER_REGNUM; 3463 else if (REG_P (tmp)) 3464 src_regno = REGNO (tmp); 3465 else 3466 goto end_call_group; 3467 3468 if (src_regno < FIRST_PSEUDO_REGISTER 3469 || dest_regno < FIRST_PSEUDO_REGISTER) 3470 { 3471 if (!deps->readonly 3472 && deps->in_post_call_group_p == post_call_initial) 3473 deps->in_post_call_group_p = post_call; 3474 3475 if (!sel_sched_p () || sched_emulate_haifa_p) 3476 { 3477 SCHED_GROUP_P (insn) = 1; 3478 CANT_MOVE (insn) = 1; 3479 } 3480 } 3481 else 3482 { 3483 end_call_group: 3484 if (!deps->readonly) 3485 deps->in_post_call_group_p = not_post_call; 3486 } 3487 } 3488 3489 debug_dont_end_call_group: 3490 if ((current_sched_info->flags & DO_SPECULATION) 3491 && !sched_insn_is_legitimate_for_speculation_p (insn, 0)) 3492 /* INSN has an internal dependency (e.g. r14 = [r14]) and thus cannot 3493 be speculated. */ 3494 { 3495 if (sel_sched_p ()) 3496 sel_mark_hard_insn (insn); 3497 else 3498 { 3499 sd_iterator_def sd_it; 3500 dep_t dep; 3501 3502 for (sd_it = sd_iterator_start (insn, SD_LIST_SPEC_BACK); 3503 sd_iterator_cond (&sd_it, &dep);) 3504 change_spec_dep_to_hard (sd_it); 3505 } 3506 } 3507 3508 /* We do not yet have code to adjust REG_ARGS_SIZE, therefore we must 3509 honor their original ordering. */ 3510 if (find_reg_note (insn, REG_ARGS_SIZE, NULL)) 3511 { 3512 if (deps->last_args_size) 3513 add_dependence (insn, deps->last_args_size, REG_DEP_OUTPUT); 3514 if (!deps->readonly) 3515 deps->last_args_size = insn; 3516 } 3517 3518 /* We must not mix prologue and epilogue insns. See PR78029. */ 3519 if (prologue_contains (insn)) 3520 { 3521 add_dependence_list (insn, deps->last_epilogue, true, REG_DEP_ANTI, true); 3522 if (!deps->readonly) 3523 { 3524 if (deps->last_logue_was_epilogue) 3525 free_INSN_LIST_list (&deps->last_prologue); 3526 deps->last_prologue = alloc_INSN_LIST (insn, deps->last_prologue); 3527 deps->last_logue_was_epilogue = false; 3528 } 3529 } 3530 3531 if (epilogue_contains (insn)) 3532 { 3533 add_dependence_list (insn, deps->last_prologue, true, REG_DEP_ANTI, true); 3534 if (!deps->readonly) 3535 { 3536 if (!deps->last_logue_was_epilogue) 3537 free_INSN_LIST_list (&deps->last_epilogue); 3538 deps->last_epilogue = alloc_INSN_LIST (insn, deps->last_epilogue); 3539 deps->last_logue_was_epilogue = true; 3540 } 3541 } 3542} 3543 3544/* Return TRUE if INSN might not always return normally (e.g. call exit, 3545 longjmp, loop forever, ...). */ 3546/* FIXME: Why can't this function just use flags_from_decl_or_type and 3547 test for ECF_NORETURN? */ 3548static bool 3549call_may_noreturn_p (rtx_insn *insn) 3550{ 3551 rtx call; 3552 3553 /* const or pure calls that aren't looping will always return. */ 3554 if (RTL_CONST_OR_PURE_CALL_P (insn) 3555 && !RTL_LOOPING_CONST_OR_PURE_CALL_P (insn)) 3556 return false; 3557 3558 call = get_call_rtx_from (insn); 3559 if (call && GET_CODE (XEXP (XEXP (call, 0), 0)) == SYMBOL_REF) 3560 { 3561 rtx symbol = XEXP (XEXP (call, 0), 0); 3562 if (SYMBOL_REF_DECL (symbol) 3563 && TREE_CODE (SYMBOL_REF_DECL (symbol)) == FUNCTION_DECL) 3564 { 3565 if (DECL_BUILT_IN_CLASS (SYMBOL_REF_DECL (symbol)) 3566 == BUILT_IN_NORMAL) 3567 switch (DECL_FUNCTION_CODE (SYMBOL_REF_DECL (symbol))) 3568 { 3569 case BUILT_IN_BCMP: 3570 case BUILT_IN_BCOPY: 3571 case BUILT_IN_BZERO: 3572 case BUILT_IN_INDEX: 3573 case BUILT_IN_MEMCHR: 3574 case BUILT_IN_MEMCMP: 3575 case BUILT_IN_MEMCPY: 3576 case BUILT_IN_MEMMOVE: 3577 case BUILT_IN_MEMPCPY: 3578 case BUILT_IN_MEMSET: 3579 case BUILT_IN_RINDEX: 3580 case BUILT_IN_STPCPY: 3581 case BUILT_IN_STPNCPY: 3582 case BUILT_IN_STRCAT: 3583 case BUILT_IN_STRCHR: 3584 case BUILT_IN_STRCMP: 3585 case BUILT_IN_STRCPY: 3586 case BUILT_IN_STRCSPN: 3587 case BUILT_IN_STRLEN: 3588 case BUILT_IN_STRNCAT: 3589 case BUILT_IN_STRNCMP: 3590 case BUILT_IN_STRNCPY: 3591 case BUILT_IN_STRPBRK: 3592 case BUILT_IN_STRRCHR: 3593 case BUILT_IN_STRSPN: 3594 case BUILT_IN_STRSTR: 3595 /* Assume certain string/memory builtins always return. */ 3596 return false; 3597 default: 3598 break; 3599 } 3600 } 3601 } 3602 3603 /* For all other calls assume that they might not always return. */ 3604 return true; 3605} 3606 3607/* Return true if INSN should be made dependent on the previous instruction 3608 group, and if all INSN's dependencies should be moved to the first 3609 instruction of that group. */ 3610 3611static bool 3612chain_to_prev_insn_p (rtx_insn *insn) 3613{ 3614 /* INSN forms a group with the previous instruction. */ 3615 if (SCHED_GROUP_P (insn)) 3616 return true; 3617 3618 /* If the previous instruction clobbers a register R and this one sets 3619 part of R, the clobber was added specifically to help us track the 3620 liveness of R. There's no point scheduling the clobber and leaving 3621 INSN behind, especially if we move the clobber to another block. */ 3622 rtx_insn *prev = prev_nonnote_nondebug_insn (insn); 3623 if (prev 3624 && INSN_P (prev) 3625 && BLOCK_FOR_INSN (prev) == BLOCK_FOR_INSN (insn) 3626 && GET_CODE (PATTERN (prev)) == CLOBBER) 3627 { 3628 rtx x = XEXP (PATTERN (prev), 0); 3629 if (set_of (x, insn)) 3630 return true; 3631 } 3632 3633 return false; 3634} 3635 3636/* Analyze INSN with DEPS as a context. */ 3637void 3638deps_analyze_insn (class deps_desc *deps, rtx_insn *insn) 3639{ 3640 if (sched_deps_info->start_insn) 3641 sched_deps_info->start_insn (insn); 3642 3643 /* Record the condition for this insn. */ 3644 if (NONDEBUG_INSN_P (insn)) 3645 { 3646 rtx t; 3647 sched_get_condition_with_rev (insn, NULL); 3648 t = INSN_CACHED_COND (insn); 3649 INSN_COND_DEPS (insn) = NULL; 3650 if (reload_completed 3651 && (current_sched_info->flags & DO_PREDICATION) 3652 && COMPARISON_P (t) 3653 && REG_P (XEXP (t, 0)) 3654 && CONSTANT_P (XEXP (t, 1))) 3655 { 3656 unsigned int regno; 3657 int nregs; 3658 rtx_insn_list *cond_deps = NULL; 3659 t = XEXP (t, 0); 3660 regno = REGNO (t); 3661 nregs = REG_NREGS (t); 3662 while (nregs-- > 0) 3663 { 3664 struct deps_reg *reg_last = &deps->reg_last[regno + nregs]; 3665 cond_deps = concat_INSN_LIST (reg_last->sets, cond_deps); 3666 cond_deps = concat_INSN_LIST (reg_last->clobbers, cond_deps); 3667 cond_deps = concat_INSN_LIST (reg_last->implicit_sets, cond_deps); 3668 } 3669 INSN_COND_DEPS (insn) = cond_deps; 3670 } 3671 } 3672 3673 if (JUMP_P (insn)) 3674 { 3675 /* Make each JUMP_INSN (but not a speculative check) 3676 a scheduling barrier for memory references. */ 3677 if (!deps->readonly 3678 && !(sel_sched_p () 3679 && sel_insn_is_speculation_check (insn))) 3680 { 3681 /* Keep the list a reasonable size. */ 3682 if (deps->pending_flush_length++ >= param_max_pending_list_length) 3683 flush_pending_lists (deps, insn, true, true); 3684 else 3685 deps->pending_jump_insns 3686 = alloc_INSN_LIST (insn, deps->pending_jump_insns); 3687 } 3688 3689 /* For each insn which shouldn't cross a jump, add a dependence. */ 3690 add_dependence_list_and_free (deps, insn, 3691 &deps->sched_before_next_jump, 1, 3692 REG_DEP_ANTI, true); 3693 3694 sched_analyze_insn (deps, PATTERN (insn), insn); 3695 } 3696 else if (NONJUMP_INSN_P (insn) || DEBUG_INSN_P (insn)) 3697 { 3698 sched_analyze_insn (deps, PATTERN (insn), insn); 3699 } 3700 else if (CALL_P (insn)) 3701 { 3702 int i; 3703 3704 CANT_MOVE (insn) = 1; 3705 3706 if (find_reg_note (insn, REG_SETJMP, NULL)) 3707 { 3708 /* This is setjmp. Assume that all registers, not just 3709 hard registers, may be clobbered by this call. */ 3710 reg_pending_barrier = MOVE_BARRIER; 3711 } 3712 else 3713 { 3714 function_abi callee_abi = insn_callee_abi (insn); 3715 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 3716 /* A call may read and modify global register variables. */ 3717 if (global_regs[i]) 3718 { 3719 SET_REGNO_REG_SET (reg_pending_sets, i); 3720 SET_HARD_REG_BIT (implicit_reg_pending_uses, i); 3721 } 3722 /* Other call-clobbered hard regs may be clobbered. 3723 Since we only have a choice between 'might be clobbered' 3724 and 'definitely not clobbered', we must include all 3725 partly call-clobbered registers here. */ 3726 else if (callee_abi.clobbers_at_least_part_of_reg_p (i)) 3727 SET_REGNO_REG_SET (reg_pending_clobbers, i); 3728 /* We don't know what set of fixed registers might be used 3729 by the function, but it is certain that the stack pointer 3730 is among them, but be conservative. */ 3731 else if (fixed_regs[i]) 3732 SET_HARD_REG_BIT (implicit_reg_pending_uses, i); 3733 /* The frame pointer is normally not used by the function 3734 itself, but by the debugger. */ 3735 /* ??? MIPS o32 is an exception. It uses the frame pointer 3736 in the macro expansion of jal but does not represent this 3737 fact in the call_insn rtl. */ 3738 else if (i == FRAME_POINTER_REGNUM 3739 || (i == HARD_FRAME_POINTER_REGNUM 3740 && (! reload_completed || frame_pointer_needed))) 3741 SET_HARD_REG_BIT (implicit_reg_pending_uses, i); 3742 } 3743 3744 /* For each insn which shouldn't cross a call, add a dependence 3745 between that insn and this call insn. */ 3746 add_dependence_list_and_free (deps, insn, 3747 &deps->sched_before_next_call, 1, 3748 REG_DEP_ANTI, true); 3749 3750 sched_analyze_insn (deps, PATTERN (insn), insn); 3751 3752 /* If CALL would be in a sched group, then this will violate 3753 convention that sched group insns have dependencies only on the 3754 previous instruction. 3755 3756 Of course one can say: "Hey! What about head of the sched group?" 3757 And I will answer: "Basic principles (one dep per insn) are always 3758 the same." */ 3759 gcc_assert (!SCHED_GROUP_P (insn)); 3760 3761 /* In the absence of interprocedural alias analysis, we must flush 3762 all pending reads and writes, and start new dependencies starting 3763 from here. But only flush writes for constant calls (which may 3764 be passed a pointer to something we haven't written yet). */ 3765 flush_pending_lists (deps, insn, true, ! RTL_CONST_OR_PURE_CALL_P (insn)); 3766 3767 if (!deps->readonly) 3768 { 3769 /* Remember the last function call for limiting lifetimes. */ 3770 free_INSN_LIST_list (&deps->last_function_call); 3771 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); 3772 3773 if (call_may_noreturn_p (insn)) 3774 { 3775 /* Remember the last function call that might not always return 3776 normally for limiting moves of trapping insns. */ 3777 free_INSN_LIST_list (&deps->last_function_call_may_noreturn); 3778 deps->last_function_call_may_noreturn 3779 = alloc_INSN_LIST (insn, NULL_RTX); 3780 } 3781 3782 /* Before reload, begin a post-call group, so as to keep the 3783 lifetimes of hard registers correct. */ 3784 if (! reload_completed) 3785 deps->in_post_call_group_p = post_call; 3786 } 3787 } 3788 3789 if (sched_deps_info->use_cselib) 3790 cselib_process_insn (insn); 3791 3792 if (sched_deps_info->finish_insn) 3793 sched_deps_info->finish_insn (); 3794 3795 /* Fixup the dependencies in the sched group. */ 3796 if ((NONJUMP_INSN_P (insn) || JUMP_P (insn)) 3797 && chain_to_prev_insn_p (insn) 3798 && !sel_sched_p ()) 3799 chain_to_prev_insn (insn); 3800} 3801 3802/* Initialize DEPS for the new block beginning with HEAD. */ 3803void 3804deps_start_bb (class deps_desc *deps, rtx_insn *head) 3805{ 3806 gcc_assert (!deps->readonly); 3807 3808 /* Before reload, if the previous block ended in a call, show that 3809 we are inside a post-call group, so as to keep the lifetimes of 3810 hard registers correct. */ 3811 if (! reload_completed && !LABEL_P (head)) 3812 { 3813 rtx_insn *insn = prev_nonnote_nondebug_insn (head); 3814 3815 if (insn && CALL_P (insn)) 3816 deps->in_post_call_group_p = post_call_initial; 3817 } 3818} 3819 3820/* Analyze every insn between HEAD and TAIL inclusive, creating backward 3821 dependencies for each insn. */ 3822void 3823sched_analyze (class deps_desc *deps, rtx_insn *head, rtx_insn *tail) 3824{ 3825 rtx_insn *insn; 3826 3827 if (sched_deps_info->use_cselib) 3828 cselib_init (CSELIB_RECORD_MEMORY); 3829 3830 deps_start_bb (deps, head); 3831 3832 for (insn = head;; insn = NEXT_INSN (insn)) 3833 { 3834 3835 if (INSN_P (insn)) 3836 { 3837 /* And initialize deps_lists. */ 3838 sd_init_insn (insn); 3839 /* Clean up SCHED_GROUP_P which may be set by last 3840 scheduler pass. */ 3841 if (SCHED_GROUP_P (insn)) 3842 SCHED_GROUP_P (insn) = 0; 3843 } 3844 3845 deps_analyze_insn (deps, insn); 3846 3847 if (insn == tail) 3848 { 3849 if (sched_deps_info->use_cselib) 3850 cselib_finish (); 3851 return; 3852 } 3853 } 3854 gcc_unreachable (); 3855} 3856 3857/* Helper for sched_free_deps (). 3858 Delete INSN's (RESOLVED_P) backward dependencies. */ 3859static void 3860delete_dep_nodes_in_back_deps (rtx_insn *insn, bool resolved_p) 3861{ 3862 sd_iterator_def sd_it; 3863 dep_t dep; 3864 sd_list_types_def types; 3865 3866 if (resolved_p) 3867 types = SD_LIST_RES_BACK; 3868 else 3869 types = SD_LIST_BACK; 3870 3871 for (sd_it = sd_iterator_start (insn, types); 3872 sd_iterator_cond (&sd_it, &dep);) 3873 { 3874 dep_link_t link = *sd_it.linkp; 3875 dep_node_t node = DEP_LINK_NODE (link); 3876 deps_list_t back_list; 3877 deps_list_t forw_list; 3878 3879 get_back_and_forw_lists (dep, resolved_p, &back_list, &forw_list); 3880 remove_from_deps_list (link, back_list); 3881 delete_dep_node (node); 3882 } 3883} 3884 3885/* Delete (RESOLVED_P) dependencies between HEAD and TAIL together with 3886 deps_lists. */ 3887void 3888sched_free_deps (rtx_insn *head, rtx_insn *tail, bool resolved_p) 3889{ 3890 rtx_insn *insn; 3891 rtx_insn *next_tail = NEXT_INSN (tail); 3892 3893 /* We make two passes since some insns may be scheduled before their 3894 dependencies are resolved. */ 3895 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 3896 if (INSN_P (insn) && INSN_LUID (insn) > 0) 3897 { 3898 /* Clear forward deps and leave the dep_nodes to the 3899 corresponding back_deps list. */ 3900 if (resolved_p) 3901 clear_deps_list (INSN_RESOLVED_FORW_DEPS (insn)); 3902 else 3903 clear_deps_list (INSN_FORW_DEPS (insn)); 3904 } 3905 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 3906 if (INSN_P (insn) && INSN_LUID (insn) > 0) 3907 { 3908 /* Clear resolved back deps together with its dep_nodes. */ 3909 delete_dep_nodes_in_back_deps (insn, resolved_p); 3910 3911 sd_finish_insn (insn); 3912 } 3913} 3914 3915/* Initialize variables for region data dependence analysis. 3916 When LAZY_REG_LAST is true, do not allocate reg_last array 3917 of class deps_desc immediately. */ 3918 3919void 3920init_deps (class deps_desc *deps, bool lazy_reg_last) 3921{ 3922 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ()); 3923 3924 deps->max_reg = max_reg; 3925 if (lazy_reg_last) 3926 deps->reg_last = NULL; 3927 else 3928 deps->reg_last = XCNEWVEC (struct deps_reg, max_reg); 3929 INIT_REG_SET (&deps->reg_last_in_use); 3930 3931 deps->pending_read_insns = 0; 3932 deps->pending_read_mems = 0; 3933 deps->pending_write_insns = 0; 3934 deps->pending_write_mems = 0; 3935 deps->pending_jump_insns = 0; 3936 deps->pending_read_list_length = 0; 3937 deps->pending_write_list_length = 0; 3938 deps->pending_flush_length = 0; 3939 deps->last_pending_memory_flush = 0; 3940 deps->last_function_call = 0; 3941 deps->last_function_call_may_noreturn = 0; 3942 deps->sched_before_next_call = 0; 3943 deps->sched_before_next_jump = 0; 3944 deps->in_post_call_group_p = not_post_call; 3945 deps->last_debug_insn = 0; 3946 deps->last_args_size = 0; 3947 deps->last_prologue = 0; 3948 deps->last_epilogue = 0; 3949 deps->last_logue_was_epilogue = false; 3950 deps->last_reg_pending_barrier = NOT_A_BARRIER; 3951 deps->readonly = 0; 3952} 3953 3954/* Init only reg_last field of DEPS, which was not allocated before as 3955 we inited DEPS lazily. */ 3956void 3957init_deps_reg_last (class deps_desc *deps) 3958{ 3959 gcc_assert (deps && deps->max_reg > 0); 3960 gcc_assert (deps->reg_last == NULL); 3961 3962 deps->reg_last = XCNEWVEC (struct deps_reg, deps->max_reg); 3963} 3964 3965 3966/* Free insn lists found in DEPS. */ 3967 3968void 3969free_deps (class deps_desc *deps) 3970{ 3971 unsigned i; 3972 reg_set_iterator rsi; 3973 3974 /* We set max_reg to 0 when this context was already freed. */ 3975 if (deps->max_reg == 0) 3976 { 3977 gcc_assert (deps->reg_last == NULL); 3978 return; 3979 } 3980 deps->max_reg = 0; 3981 3982 free_INSN_LIST_list (&deps->pending_read_insns); 3983 free_EXPR_LIST_list (&deps->pending_read_mems); 3984 free_INSN_LIST_list (&deps->pending_write_insns); 3985 free_EXPR_LIST_list (&deps->pending_write_mems); 3986 free_INSN_LIST_list (&deps->last_pending_memory_flush); 3987 3988 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions 3989 times. For a testcase with 42000 regs and 8000 small basic blocks, 3990 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */ 3991 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi) 3992 { 3993 struct deps_reg *reg_last = &deps->reg_last[i]; 3994 if (reg_last->uses) 3995 free_INSN_LIST_list (®_last->uses); 3996 if (reg_last->sets) 3997 free_INSN_LIST_list (®_last->sets); 3998 if (reg_last->implicit_sets) 3999 free_INSN_LIST_list (®_last->implicit_sets); 4000 if (reg_last->control_uses) 4001 free_INSN_LIST_list (®_last->control_uses); 4002 if (reg_last->clobbers) 4003 free_INSN_LIST_list (®_last->clobbers); 4004 } 4005 CLEAR_REG_SET (&deps->reg_last_in_use); 4006 4007 /* As we initialize reg_last lazily, it is possible that we didn't allocate 4008 it at all. */ 4009 free (deps->reg_last); 4010 deps->reg_last = NULL; 4011 4012 deps = NULL; 4013} 4014 4015/* Remove INSN from dependence contexts DEPS. */ 4016void 4017remove_from_deps (class deps_desc *deps, rtx_insn *insn) 4018{ 4019 int removed; 4020 unsigned i; 4021 reg_set_iterator rsi; 4022 4023 removed = remove_from_both_dependence_lists (insn, &deps->pending_read_insns, 4024 &deps->pending_read_mems); 4025 if (!DEBUG_INSN_P (insn)) 4026 deps->pending_read_list_length -= removed; 4027 removed = remove_from_both_dependence_lists (insn, &deps->pending_write_insns, 4028 &deps->pending_write_mems); 4029 deps->pending_write_list_length -= removed; 4030 4031 removed = remove_from_dependence_list (insn, &deps->pending_jump_insns); 4032 deps->pending_flush_length -= removed; 4033 removed = remove_from_dependence_list (insn, &deps->last_pending_memory_flush); 4034 deps->pending_flush_length -= removed; 4035 4036 unsigned to_clear = -1U; 4037 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, rsi) 4038 { 4039 if (to_clear != -1U) 4040 { 4041 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear); 4042 to_clear = -1U; 4043 } 4044 struct deps_reg *reg_last = &deps->reg_last[i]; 4045 if (reg_last->uses) 4046 remove_from_dependence_list (insn, ®_last->uses); 4047 if (reg_last->sets) 4048 remove_from_dependence_list (insn, ®_last->sets); 4049 if (reg_last->implicit_sets) 4050 remove_from_dependence_list (insn, ®_last->implicit_sets); 4051 if (reg_last->clobbers) 4052 remove_from_dependence_list (insn, ®_last->clobbers); 4053 if (!reg_last->uses && !reg_last->sets && !reg_last->implicit_sets 4054 && !reg_last->clobbers) 4055 to_clear = i; 4056 } 4057 if (to_clear != -1U) 4058 CLEAR_REGNO_REG_SET (&deps->reg_last_in_use, to_clear); 4059 4060 if (CALL_P (insn)) 4061 { 4062 remove_from_dependence_list (insn, &deps->last_function_call); 4063 remove_from_dependence_list (insn, 4064 &deps->last_function_call_may_noreturn); 4065 } 4066 remove_from_dependence_list (insn, &deps->sched_before_next_call); 4067} 4068 4069/* Init deps data vector. */ 4070static void 4071init_deps_data_vector (void) 4072{ 4073 int reserve = (sched_max_luid + 1 - h_d_i_d.length ()); 4074 if (reserve > 0 && ! h_d_i_d.space (reserve)) 4075 h_d_i_d.safe_grow_cleared (3 * sched_max_luid / 2); 4076} 4077 4078/* If it is profitable to use them, initialize or extend (depending on 4079 GLOBAL_P) dependency data. */ 4080void 4081sched_deps_init (bool global_p) 4082{ 4083 /* Average number of insns in the basic block. 4084 '+ 1' is used to make it nonzero. */ 4085 int insns_in_block = sched_max_luid / n_basic_blocks_for_fn (cfun) + 1; 4086 4087 init_deps_data_vector (); 4088 4089 /* We use another caching mechanism for selective scheduling, so 4090 we don't use this one. */ 4091 if (!sel_sched_p () && global_p && insns_in_block > 100 * 5) 4092 { 4093 /* ?!? We could save some memory by computing a per-region luid mapping 4094 which could reduce both the number of vectors in the cache and the 4095 size of each vector. Instead we just avoid the cache entirely unless 4096 the average number of instructions in a basic block is very high. See 4097 the comment before the declaration of true_dependency_cache for 4098 what we consider "very high". */ 4099 cache_size = 0; 4100 extend_dependency_caches (sched_max_luid, true); 4101 } 4102 4103 if (global_p) 4104 { 4105 dl_pool = new object_allocator<_deps_list> ("deps_list"); 4106 /* Allocate lists for one block at a time. */ 4107 dn_pool = new object_allocator<_dep_node> ("dep_node"); 4108 /* Allocate nodes for one block at a time. */ 4109 } 4110} 4111 4112 4113/* Create or extend (depending on CREATE_P) dependency caches to 4114 size N. */ 4115void 4116extend_dependency_caches (int n, bool create_p) 4117{ 4118 if (create_p || true_dependency_cache) 4119 { 4120 int i, luid = cache_size + n; 4121 4122 true_dependency_cache = XRESIZEVEC (bitmap_head, true_dependency_cache, 4123 luid); 4124 output_dependency_cache = XRESIZEVEC (bitmap_head, 4125 output_dependency_cache, luid); 4126 anti_dependency_cache = XRESIZEVEC (bitmap_head, anti_dependency_cache, 4127 luid); 4128 control_dependency_cache = XRESIZEVEC (bitmap_head, control_dependency_cache, 4129 luid); 4130 4131 if (current_sched_info->flags & DO_SPECULATION) 4132 spec_dependency_cache = XRESIZEVEC (bitmap_head, spec_dependency_cache, 4133 luid); 4134 4135 for (i = cache_size; i < luid; i++) 4136 { 4137 bitmap_initialize (&true_dependency_cache[i], 0); 4138 bitmap_initialize (&output_dependency_cache[i], 0); 4139 bitmap_initialize (&anti_dependency_cache[i], 0); 4140 bitmap_initialize (&control_dependency_cache[i], 0); 4141 4142 if (current_sched_info->flags & DO_SPECULATION) 4143 bitmap_initialize (&spec_dependency_cache[i], 0); 4144 } 4145 cache_size = luid; 4146 } 4147} 4148 4149/* Finalize dependency information for the whole function. */ 4150void 4151sched_deps_finish (void) 4152{ 4153 gcc_assert (deps_pools_are_empty_p ()); 4154 delete dn_pool; 4155 delete dl_pool; 4156 dn_pool = NULL; 4157 dl_pool = NULL; 4158 4159 h_d_i_d.release (); 4160 cache_size = 0; 4161 4162 if (true_dependency_cache) 4163 { 4164 int i; 4165 4166 for (i = 0; i < cache_size; i++) 4167 { 4168 bitmap_clear (&true_dependency_cache[i]); 4169 bitmap_clear (&output_dependency_cache[i]); 4170 bitmap_clear (&anti_dependency_cache[i]); 4171 bitmap_clear (&control_dependency_cache[i]); 4172 4173 if (sched_deps_info->generate_spec_deps) 4174 bitmap_clear (&spec_dependency_cache[i]); 4175 } 4176 free (true_dependency_cache); 4177 true_dependency_cache = NULL; 4178 free (output_dependency_cache); 4179 output_dependency_cache = NULL; 4180 free (anti_dependency_cache); 4181 anti_dependency_cache = NULL; 4182 free (control_dependency_cache); 4183 control_dependency_cache = NULL; 4184 4185 if (sched_deps_info->generate_spec_deps) 4186 { 4187 free (spec_dependency_cache); 4188 spec_dependency_cache = NULL; 4189 } 4190 4191 } 4192} 4193 4194/* Initialize some global variables needed by the dependency analysis 4195 code. */ 4196 4197void 4198init_deps_global (void) 4199{ 4200 CLEAR_HARD_REG_SET (implicit_reg_pending_clobbers); 4201 CLEAR_HARD_REG_SET (implicit_reg_pending_uses); 4202 reg_pending_sets = ALLOC_REG_SET (®_obstack); 4203 reg_pending_clobbers = ALLOC_REG_SET (®_obstack); 4204 reg_pending_uses = ALLOC_REG_SET (®_obstack); 4205 reg_pending_control_uses = ALLOC_REG_SET (®_obstack); 4206 reg_pending_barrier = NOT_A_BARRIER; 4207 4208 if (!sel_sched_p () || sched_emulate_haifa_p) 4209 { 4210 sched_deps_info->start_insn = haifa_start_insn; 4211 sched_deps_info->finish_insn = haifa_finish_insn; 4212 4213 sched_deps_info->note_reg_set = haifa_note_reg_set; 4214 sched_deps_info->note_reg_clobber = haifa_note_reg_clobber; 4215 sched_deps_info->note_reg_use = haifa_note_reg_use; 4216 4217 sched_deps_info->note_mem_dep = haifa_note_mem_dep; 4218 sched_deps_info->note_dep = haifa_note_dep; 4219 } 4220} 4221 4222/* Free everything used by the dependency analysis code. */ 4223 4224void 4225finish_deps_global (void) 4226{ 4227 FREE_REG_SET (reg_pending_sets); 4228 FREE_REG_SET (reg_pending_clobbers); 4229 FREE_REG_SET (reg_pending_uses); 4230 FREE_REG_SET (reg_pending_control_uses); 4231} 4232 4233/* Estimate the weakness of dependence between MEM1 and MEM2. */ 4234dw_t 4235estimate_dep_weak (rtx mem1, rtx mem2) 4236{ 4237 if (mem1 == mem2) 4238 /* MEMs are the same - don't speculate. */ 4239 return MIN_DEP_WEAK; 4240 4241 rtx r1 = XEXP (mem1, 0); 4242 rtx r2 = XEXP (mem2, 0); 4243 4244 if (sched_deps_info->use_cselib) 4245 { 4246 /* We cannot call rtx_equal_for_cselib_p because the VALUEs might be 4247 dangling at this point, since we never preserve them. Instead we 4248 canonicalize manually to get stable VALUEs out of hashing. */ 4249 if (GET_CODE (r1) == VALUE && CSELIB_VAL_PTR (r1)) 4250 r1 = canonical_cselib_val (CSELIB_VAL_PTR (r1))->val_rtx; 4251 if (GET_CODE (r2) == VALUE && CSELIB_VAL_PTR (r2)) 4252 r2 = canonical_cselib_val (CSELIB_VAL_PTR (r2))->val_rtx; 4253 } 4254 4255 if (r1 == r2 4256 || (REG_P (r1) && REG_P (r2) && REGNO (r1) == REGNO (r2))) 4257 /* Again, MEMs are the same. */ 4258 return MIN_DEP_WEAK; 4259 else if ((REG_P (r1) && !REG_P (r2)) || (!REG_P (r1) && REG_P (r2))) 4260 /* Different addressing modes - reason to be more speculative, 4261 than usual. */ 4262 return NO_DEP_WEAK - (NO_DEP_WEAK - UNCERTAIN_DEP_WEAK) / 2; 4263 else 4264 /* We can't say anything about the dependence. */ 4265 return UNCERTAIN_DEP_WEAK; 4266} 4267 4268/* Add or update backward dependence between INSN and ELEM with type DEP_TYPE. 4269 This function can handle same INSN and ELEM (INSN == ELEM). 4270 It is a convenience wrapper. */ 4271static void 4272add_dependence_1 (rtx_insn *insn, rtx_insn *elem, enum reg_note dep_type) 4273{ 4274 ds_t ds; 4275 bool internal; 4276 4277 if (dep_type == REG_DEP_TRUE) 4278 ds = DEP_TRUE; 4279 else if (dep_type == REG_DEP_OUTPUT) 4280 ds = DEP_OUTPUT; 4281 else if (dep_type == REG_DEP_CONTROL) 4282 ds = DEP_CONTROL; 4283 else 4284 { 4285 gcc_assert (dep_type == REG_DEP_ANTI); 4286 ds = DEP_ANTI; 4287 } 4288 4289 /* When add_dependence is called from inside sched-deps.c, we expect 4290 cur_insn to be non-null. */ 4291 internal = cur_insn != NULL; 4292 if (internal) 4293 gcc_assert (insn == cur_insn); 4294 else 4295 cur_insn = insn; 4296 4297 note_dep (elem, ds); 4298 if (!internal) 4299 cur_insn = NULL; 4300} 4301 4302/* Return weakness of speculative type TYPE in the dep_status DS, 4303 without checking to prevent ICEs on malformed input. */ 4304static dw_t 4305get_dep_weak_1 (ds_t ds, ds_t type) 4306{ 4307 ds = ds & type; 4308 4309 switch (type) 4310 { 4311 case BEGIN_DATA: ds >>= BEGIN_DATA_BITS_OFFSET; break; 4312 case BE_IN_DATA: ds >>= BE_IN_DATA_BITS_OFFSET; break; 4313 case BEGIN_CONTROL: ds >>= BEGIN_CONTROL_BITS_OFFSET; break; 4314 case BE_IN_CONTROL: ds >>= BE_IN_CONTROL_BITS_OFFSET; break; 4315 default: gcc_unreachable (); 4316 } 4317 4318 return (dw_t) ds; 4319} 4320 4321/* Return weakness of speculative type TYPE in the dep_status DS. */ 4322dw_t 4323get_dep_weak (ds_t ds, ds_t type) 4324{ 4325 dw_t dw = get_dep_weak_1 (ds, type); 4326 4327 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK); 4328 return dw; 4329} 4330 4331/* Return the dep_status, which has the same parameters as DS, except for 4332 speculative type TYPE, that will have weakness DW. */ 4333ds_t 4334set_dep_weak (ds_t ds, ds_t type, dw_t dw) 4335{ 4336 gcc_assert (MIN_DEP_WEAK <= dw && dw <= MAX_DEP_WEAK); 4337 4338 ds &= ~type; 4339 switch (type) 4340 { 4341 case BEGIN_DATA: ds |= ((ds_t) dw) << BEGIN_DATA_BITS_OFFSET; break; 4342 case BE_IN_DATA: ds |= ((ds_t) dw) << BE_IN_DATA_BITS_OFFSET; break; 4343 case BEGIN_CONTROL: ds |= ((ds_t) dw) << BEGIN_CONTROL_BITS_OFFSET; break; 4344 case BE_IN_CONTROL: ds |= ((ds_t) dw) << BE_IN_CONTROL_BITS_OFFSET; break; 4345 default: gcc_unreachable (); 4346 } 4347 return ds; 4348} 4349 4350/* Return the join of two dep_statuses DS1 and DS2. 4351 If MAX_P is true then choose the greater probability, 4352 otherwise multiply probabilities. 4353 This function assumes that both DS1 and DS2 contain speculative bits. */ 4354static ds_t 4355ds_merge_1 (ds_t ds1, ds_t ds2, bool max_p) 4356{ 4357 ds_t ds, t; 4358 4359 gcc_assert ((ds1 & SPECULATIVE) && (ds2 & SPECULATIVE)); 4360 4361 ds = (ds1 & DEP_TYPES) | (ds2 & DEP_TYPES); 4362 4363 t = FIRST_SPEC_TYPE; 4364 do 4365 { 4366 if ((ds1 & t) && !(ds2 & t)) 4367 ds |= ds1 & t; 4368 else if (!(ds1 & t) && (ds2 & t)) 4369 ds |= ds2 & t; 4370 else if ((ds1 & t) && (ds2 & t)) 4371 { 4372 dw_t dw1 = get_dep_weak (ds1, t); 4373 dw_t dw2 = get_dep_weak (ds2, t); 4374 ds_t dw; 4375 4376 if (!max_p) 4377 { 4378 dw = ((ds_t) dw1) * ((ds_t) dw2); 4379 dw /= MAX_DEP_WEAK; 4380 if (dw < MIN_DEP_WEAK) 4381 dw = MIN_DEP_WEAK; 4382 } 4383 else 4384 { 4385 if (dw1 >= dw2) 4386 dw = dw1; 4387 else 4388 dw = dw2; 4389 } 4390 4391 ds = set_dep_weak (ds, t, (dw_t) dw); 4392 } 4393 4394 if (t == LAST_SPEC_TYPE) 4395 break; 4396 t <<= SPEC_TYPE_SHIFT; 4397 } 4398 while (1); 4399 4400 return ds; 4401} 4402 4403/* Return the join of two dep_statuses DS1 and DS2. 4404 This function assumes that both DS1 and DS2 contain speculative bits. */ 4405ds_t 4406ds_merge (ds_t ds1, ds_t ds2) 4407{ 4408 return ds_merge_1 (ds1, ds2, false); 4409} 4410 4411/* Return the join of two dep_statuses DS1 and DS2. */ 4412ds_t 4413ds_full_merge (ds_t ds, ds_t ds2, rtx mem1, rtx mem2) 4414{ 4415 ds_t new_status = ds | ds2; 4416 4417 if (new_status & SPECULATIVE) 4418 { 4419 if ((ds && !(ds & SPECULATIVE)) 4420 || (ds2 && !(ds2 & SPECULATIVE))) 4421 /* Then this dep can't be speculative. */ 4422 new_status &= ~SPECULATIVE; 4423 else 4424 { 4425 /* Both are speculative. Merging probabilities. */ 4426 if (mem1) 4427 { 4428 dw_t dw; 4429 4430 dw = estimate_dep_weak (mem1, mem2); 4431 ds = set_dep_weak (ds, BEGIN_DATA, dw); 4432 } 4433 4434 if (!ds) 4435 new_status = ds2; 4436 else if (!ds2) 4437 new_status = ds; 4438 else 4439 new_status = ds_merge (ds2, ds); 4440 } 4441 } 4442 4443 return new_status; 4444} 4445 4446/* Return the join of DS1 and DS2. Use maximum instead of multiplying 4447 probabilities. */ 4448ds_t 4449ds_max_merge (ds_t ds1, ds_t ds2) 4450{ 4451 if (ds1 == 0 && ds2 == 0) 4452 return 0; 4453 4454 if (ds1 == 0 && ds2 != 0) 4455 return ds2; 4456 4457 if (ds1 != 0 && ds2 == 0) 4458 return ds1; 4459 4460 return ds_merge_1 (ds1, ds2, true); 4461} 4462 4463/* Return the probability of speculation success for the speculation 4464 status DS. */ 4465dw_t 4466ds_weak (ds_t ds) 4467{ 4468 ds_t res = 1, dt; 4469 int n = 0; 4470 4471 dt = FIRST_SPEC_TYPE; 4472 do 4473 { 4474 if (ds & dt) 4475 { 4476 res *= (ds_t) get_dep_weak (ds, dt); 4477 n++; 4478 } 4479 4480 if (dt == LAST_SPEC_TYPE) 4481 break; 4482 dt <<= SPEC_TYPE_SHIFT; 4483 } 4484 while (1); 4485 4486 gcc_assert (n); 4487 while (--n) 4488 res /= MAX_DEP_WEAK; 4489 4490 if (res < MIN_DEP_WEAK) 4491 res = MIN_DEP_WEAK; 4492 4493 gcc_assert (res <= MAX_DEP_WEAK); 4494 4495 return (dw_t) res; 4496} 4497 4498/* Return a dep status that contains all speculation types of DS. */ 4499ds_t 4500ds_get_speculation_types (ds_t ds) 4501{ 4502 if (ds & BEGIN_DATA) 4503 ds |= BEGIN_DATA; 4504 if (ds & BE_IN_DATA) 4505 ds |= BE_IN_DATA; 4506 if (ds & BEGIN_CONTROL) 4507 ds |= BEGIN_CONTROL; 4508 if (ds & BE_IN_CONTROL) 4509 ds |= BE_IN_CONTROL; 4510 4511 return ds & SPECULATIVE; 4512} 4513 4514/* Return a dep status that contains maximal weakness for each speculation 4515 type present in DS. */ 4516ds_t 4517ds_get_max_dep_weak (ds_t ds) 4518{ 4519 if (ds & BEGIN_DATA) 4520 ds = set_dep_weak (ds, BEGIN_DATA, MAX_DEP_WEAK); 4521 if (ds & BE_IN_DATA) 4522 ds = set_dep_weak (ds, BE_IN_DATA, MAX_DEP_WEAK); 4523 if (ds & BEGIN_CONTROL) 4524 ds = set_dep_weak (ds, BEGIN_CONTROL, MAX_DEP_WEAK); 4525 if (ds & BE_IN_CONTROL) 4526 ds = set_dep_weak (ds, BE_IN_CONTROL, MAX_DEP_WEAK); 4527 4528 return ds; 4529} 4530 4531/* Dump information about the dependence status S. */ 4532static void 4533dump_ds (FILE *f, ds_t s) 4534{ 4535 fprintf (f, "{"); 4536 4537 if (s & BEGIN_DATA) 4538 fprintf (f, "BEGIN_DATA: %d; ", get_dep_weak_1 (s, BEGIN_DATA)); 4539 if (s & BE_IN_DATA) 4540 fprintf (f, "BE_IN_DATA: %d; ", get_dep_weak_1 (s, BE_IN_DATA)); 4541 if (s & BEGIN_CONTROL) 4542 fprintf (f, "BEGIN_CONTROL: %d; ", get_dep_weak_1 (s, BEGIN_CONTROL)); 4543 if (s & BE_IN_CONTROL) 4544 fprintf (f, "BE_IN_CONTROL: %d; ", get_dep_weak_1 (s, BE_IN_CONTROL)); 4545 4546 if (s & HARD_DEP) 4547 fprintf (f, "HARD_DEP; "); 4548 4549 if (s & DEP_TRUE) 4550 fprintf (f, "DEP_TRUE; "); 4551 if (s & DEP_OUTPUT) 4552 fprintf (f, "DEP_OUTPUT; "); 4553 if (s & DEP_ANTI) 4554 fprintf (f, "DEP_ANTI; "); 4555 if (s & DEP_CONTROL) 4556 fprintf (f, "DEP_CONTROL; "); 4557 4558 fprintf (f, "}"); 4559} 4560 4561DEBUG_FUNCTION void 4562debug_ds (ds_t s) 4563{ 4564 dump_ds (stderr, s); 4565 fprintf (stderr, "\n"); 4566} 4567 4568/* Verify that dependence type and status are consistent. 4569 If RELAXED_P is true, then skip dep_weakness checks. */ 4570static void 4571check_dep (dep_t dep, bool relaxed_p) 4572{ 4573 enum reg_note dt = DEP_TYPE (dep); 4574 ds_t ds = DEP_STATUS (dep); 4575 4576 gcc_assert (DEP_PRO (dep) != DEP_CON (dep)); 4577 4578 if (!(current_sched_info->flags & USE_DEPS_LIST)) 4579 { 4580 gcc_assert (ds == 0); 4581 return; 4582 } 4583 4584 /* Check that dependence type contains the same bits as the status. */ 4585 if (dt == REG_DEP_TRUE) 4586 gcc_assert (ds & DEP_TRUE); 4587 else if (dt == REG_DEP_OUTPUT) 4588 gcc_assert ((ds & DEP_OUTPUT) 4589 && !(ds & DEP_TRUE)); 4590 else if (dt == REG_DEP_ANTI) 4591 gcc_assert ((ds & DEP_ANTI) 4592 && !(ds & (DEP_OUTPUT | DEP_TRUE))); 4593 else 4594 gcc_assert (dt == REG_DEP_CONTROL 4595 && (ds & DEP_CONTROL) 4596 && !(ds & (DEP_OUTPUT | DEP_ANTI | DEP_TRUE))); 4597 4598 /* HARD_DEP cannot appear in dep_status of a link. */ 4599 gcc_assert (!(ds & HARD_DEP)); 4600 4601 /* Check that dependence status is set correctly when speculation is not 4602 supported. */ 4603 if (!sched_deps_info->generate_spec_deps) 4604 gcc_assert (!(ds & SPECULATIVE)); 4605 else if (ds & SPECULATIVE) 4606 { 4607 if (!relaxed_p) 4608 { 4609 ds_t type = FIRST_SPEC_TYPE; 4610 4611 /* Check that dependence weakness is in proper range. */ 4612 do 4613 { 4614 if (ds & type) 4615 get_dep_weak (ds, type); 4616 4617 if (type == LAST_SPEC_TYPE) 4618 break; 4619 type <<= SPEC_TYPE_SHIFT; 4620 } 4621 while (1); 4622 } 4623 4624 if (ds & BEGIN_SPEC) 4625 { 4626 /* Only true dependence can be data speculative. */ 4627 if (ds & BEGIN_DATA) 4628 gcc_assert (ds & DEP_TRUE); 4629 4630 /* Control dependencies in the insn scheduler are represented by 4631 anti-dependencies, therefore only anti dependence can be 4632 control speculative. */ 4633 if (ds & BEGIN_CONTROL) 4634 gcc_assert (ds & DEP_ANTI); 4635 } 4636 else 4637 { 4638 /* Subsequent speculations should resolve true dependencies. */ 4639 gcc_assert ((ds & DEP_TYPES) == DEP_TRUE); 4640 } 4641 4642 /* Check that true and anti dependencies can't have other speculative 4643 statuses. */ 4644 if (ds & DEP_TRUE) 4645 gcc_assert (ds & (BEGIN_DATA | BE_IN_SPEC)); 4646 /* An output dependence can't be speculative at all. */ 4647 gcc_assert (!(ds & DEP_OUTPUT)); 4648 if (ds & DEP_ANTI) 4649 gcc_assert (ds & BEGIN_CONTROL); 4650 } 4651} 4652 4653/* The following code discovers opportunities to switch a memory reference 4654 and an increment by modifying the address. We ensure that this is done 4655 only for dependencies that are only used to show a single register 4656 dependence (using DEP_NONREG and DEP_MULTIPLE), and so that every memory 4657 instruction involved is subject to only one dep that can cause a pattern 4658 change. 4659 4660 When we discover a suitable dependency, we fill in the dep_replacement 4661 structure to show how to modify the memory reference. */ 4662 4663/* Holds information about a pair of memory reference and register increment 4664 insns which depend on each other, but could possibly be interchanged. */ 4665struct mem_inc_info 4666{ 4667 rtx_insn *inc_insn; 4668 rtx_insn *mem_insn; 4669 4670 rtx *mem_loc; 4671 /* A register occurring in the memory address for which we wish to break 4672 the dependence. This must be identical to the destination register of 4673 the increment. */ 4674 rtx mem_reg0; 4675 /* Any kind of index that is added to that register. */ 4676 rtx mem_index; 4677 /* The constant offset used in the memory address. */ 4678 HOST_WIDE_INT mem_constant; 4679 /* The constant added in the increment insn. Negated if the increment is 4680 after the memory address. */ 4681 HOST_WIDE_INT inc_constant; 4682 /* The source register used in the increment. May be different from mem_reg0 4683 if the increment occurs before the memory address. */ 4684 rtx inc_input; 4685}; 4686 4687/* Verify that the memory location described in MII can be replaced with 4688 one using NEW_ADDR. Return the new memory reference or NULL_RTX. The 4689 insn remains unchanged by this function. */ 4690 4691static rtx 4692attempt_change (struct mem_inc_info *mii, rtx new_addr) 4693{ 4694 rtx mem = *mii->mem_loc; 4695 rtx new_mem; 4696 4697 /* Jump through a lot of hoops to keep the attributes up to date. We 4698 do not want to call one of the change address variants that take 4699 an offset even though we know the offset in many cases. These 4700 assume you are changing where the address is pointing by the 4701 offset. */ 4702 new_mem = replace_equiv_address_nv (mem, new_addr); 4703 if (! validate_change (mii->mem_insn, mii->mem_loc, new_mem, 0)) 4704 { 4705 if (sched_verbose >= 5) 4706 fprintf (sched_dump, "validation failure\n"); 4707 return NULL_RTX; 4708 } 4709 4710 /* Put back the old one. */ 4711 validate_change (mii->mem_insn, mii->mem_loc, mem, 0); 4712 4713 return new_mem; 4714} 4715 4716/* Return true if INSN is of a form "a = b op c" where a and b are 4717 regs. op is + if c is a reg and +|- if c is a const. Fill in 4718 informantion in MII about what is found. 4719 BEFORE_MEM indicates whether the increment is found before or after 4720 a corresponding memory reference. */ 4721 4722static bool 4723parse_add_or_inc (struct mem_inc_info *mii, rtx_insn *insn, bool before_mem) 4724{ 4725 rtx pat = single_set (insn); 4726 rtx src, cst; 4727 bool regs_equal; 4728 4729 if (RTX_FRAME_RELATED_P (insn) || !pat) 4730 return false; 4731 4732 /* Do not allow breaking data dependencies for insns that are marked 4733 with REG_STACK_CHECK. */ 4734 if (find_reg_note (insn, REG_STACK_CHECK, NULL)) 4735 return false; 4736 4737 /* Result must be single reg. */ 4738 if (!REG_P (SET_DEST (pat))) 4739 return false; 4740 4741 if (GET_CODE (SET_SRC (pat)) != PLUS) 4742 return false; 4743 4744 mii->inc_insn = insn; 4745 src = SET_SRC (pat); 4746 mii->inc_input = XEXP (src, 0); 4747 4748 if (!REG_P (XEXP (src, 0))) 4749 return false; 4750 4751 if (!rtx_equal_p (SET_DEST (pat), mii->mem_reg0)) 4752 return false; 4753 4754 cst = XEXP (src, 1); 4755 if (!CONST_INT_P (cst)) 4756 return false; 4757 mii->inc_constant = INTVAL (cst); 4758 4759 regs_equal = rtx_equal_p (mii->inc_input, mii->mem_reg0); 4760 4761 if (!before_mem) 4762 { 4763 mii->inc_constant = -mii->inc_constant; 4764 if (!regs_equal) 4765 return false; 4766 } 4767 4768 if (regs_equal && REGNO (SET_DEST (pat)) == STACK_POINTER_REGNUM) 4769 { 4770 /* Note that the sign has already been reversed for !before_mem. */ 4771 if (STACK_GROWS_DOWNWARD) 4772 return mii->inc_constant > 0; 4773 else 4774 return mii->inc_constant < 0; 4775 } 4776 return true; 4777} 4778 4779/* Once a suitable mem reference has been found and the corresponding data 4780 in MII has been filled in, this function is called to find a suitable 4781 add or inc insn involving the register we found in the memory 4782 reference. */ 4783 4784static bool 4785find_inc (struct mem_inc_info *mii, bool backwards) 4786{ 4787 sd_iterator_def sd_it; 4788 dep_t dep; 4789 4790 sd_it = sd_iterator_start (mii->mem_insn, 4791 backwards ? SD_LIST_HARD_BACK : SD_LIST_FORW); 4792 while (sd_iterator_cond (&sd_it, &dep)) 4793 { 4794 dep_node_t node = DEP_LINK_NODE (*sd_it.linkp); 4795 rtx_insn *pro = DEP_PRO (dep); 4796 rtx_insn *con = DEP_CON (dep); 4797 rtx_insn *inc_cand = backwards ? pro : con; 4798 if (DEP_NONREG (dep) || DEP_MULTIPLE (dep)) 4799 goto next; 4800 if (parse_add_or_inc (mii, inc_cand, backwards)) 4801 { 4802 struct dep_replacement *desc; 4803 df_ref def; 4804 rtx newaddr, newmem; 4805 4806 if (sched_verbose >= 5) 4807 fprintf (sched_dump, "candidate mem/inc pair: %d %d\n", 4808 INSN_UID (mii->mem_insn), INSN_UID (inc_cand)); 4809 4810 /* Need to assure that none of the operands of the inc 4811 instruction are assigned to by the mem insn. */ 4812 FOR_EACH_INSN_DEF (def, mii->mem_insn) 4813 if (reg_overlap_mentioned_p (DF_REF_REG (def), mii->inc_input) 4814 || reg_overlap_mentioned_p (DF_REF_REG (def), mii->mem_reg0)) 4815 { 4816 if (sched_verbose >= 5) 4817 fprintf (sched_dump, 4818 "inc conflicts with store failure.\n"); 4819 goto next; 4820 } 4821 4822 newaddr = mii->inc_input; 4823 if (mii->mem_index != NULL_RTX) 4824 newaddr = gen_rtx_PLUS (GET_MODE (newaddr), newaddr, 4825 mii->mem_index); 4826 newaddr = plus_constant (GET_MODE (newaddr), newaddr, 4827 mii->mem_constant + mii->inc_constant); 4828 newmem = attempt_change (mii, newaddr); 4829 if (newmem == NULL_RTX) 4830 goto next; 4831 if (sched_verbose >= 5) 4832 fprintf (sched_dump, "successful address replacement\n"); 4833 desc = XCNEW (struct dep_replacement); 4834 DEP_REPLACE (dep) = desc; 4835 desc->loc = mii->mem_loc; 4836 desc->newval = newmem; 4837 desc->orig = *desc->loc; 4838 desc->insn = mii->mem_insn; 4839 move_dep_link (DEP_NODE_BACK (node), INSN_HARD_BACK_DEPS (con), 4840 INSN_SPEC_BACK_DEPS (con)); 4841 if (backwards) 4842 { 4843 FOR_EACH_DEP (mii->inc_insn, SD_LIST_BACK, sd_it, dep) 4844 add_dependence_1 (mii->mem_insn, DEP_PRO (dep), 4845 REG_DEP_TRUE); 4846 } 4847 else 4848 { 4849 FOR_EACH_DEP (mii->inc_insn, SD_LIST_FORW, sd_it, dep) 4850 add_dependence_1 (DEP_CON (dep), mii->mem_insn, 4851 REG_DEP_ANTI); 4852 } 4853 return true; 4854 } 4855 next: 4856 sd_iterator_next (&sd_it); 4857 } 4858 return false; 4859} 4860 4861/* A recursive function that walks ADDRESS_OF_X to find memory references 4862 which could be modified during scheduling. We call find_inc for each 4863 one we find that has a recognizable form. MII holds information about 4864 the pair of memory/increment instructions. 4865 We ensure that every instruction with a memory reference (which will be 4866 the location of the replacement) is assigned at most one breakable 4867 dependency. */ 4868 4869static bool 4870find_mem (struct mem_inc_info *mii, rtx *address_of_x) 4871{ 4872 rtx x = *address_of_x; 4873 enum rtx_code code = GET_CODE (x); 4874 const char *const fmt = GET_RTX_FORMAT (code); 4875 int i; 4876 4877 if (code == MEM) 4878 { 4879 rtx reg0 = XEXP (x, 0); 4880 4881 mii->mem_loc = address_of_x; 4882 mii->mem_index = NULL_RTX; 4883 mii->mem_constant = 0; 4884 if (GET_CODE (reg0) == PLUS && CONST_INT_P (XEXP (reg0, 1))) 4885 { 4886 mii->mem_constant = INTVAL (XEXP (reg0, 1)); 4887 reg0 = XEXP (reg0, 0); 4888 } 4889 if (GET_CODE (reg0) == PLUS) 4890 { 4891 mii->mem_index = XEXP (reg0, 1); 4892 reg0 = XEXP (reg0, 0); 4893 } 4894 if (REG_P (reg0)) 4895 { 4896 df_ref use; 4897 int occurrences = 0; 4898 4899 /* Make sure this reg appears only once in this insn. Can't use 4900 count_occurrences since that only works for pseudos. */ 4901 FOR_EACH_INSN_USE (use, mii->mem_insn) 4902 if (reg_overlap_mentioned_p (reg0, DF_REF_REG (use))) 4903 if (++occurrences > 1) 4904 { 4905 if (sched_verbose >= 5) 4906 fprintf (sched_dump, "mem count failure\n"); 4907 return false; 4908 } 4909 4910 mii->mem_reg0 = reg0; 4911 return find_inc (mii, true) || find_inc (mii, false); 4912 } 4913 return false; 4914 } 4915 4916 if (code == SIGN_EXTRACT || code == ZERO_EXTRACT) 4917 { 4918 /* If REG occurs inside a MEM used in a bit-field reference, 4919 that is unacceptable. */ 4920 return false; 4921 } 4922 4923 /* Time for some deep diving. */ 4924 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 4925 { 4926 if (fmt[i] == 'e') 4927 { 4928 if (find_mem (mii, &XEXP (x, i))) 4929 return true; 4930 } 4931 else if (fmt[i] == 'E') 4932 { 4933 int j; 4934 for (j = XVECLEN (x, i) - 1; j >= 0; j--) 4935 if (find_mem (mii, &XVECEXP (x, i, j))) 4936 return true; 4937 } 4938 } 4939 return false; 4940} 4941 4942 4943/* Examine the instructions between HEAD and TAIL and try to find 4944 dependencies that can be broken by modifying one of the patterns. */ 4945 4946void 4947find_modifiable_mems (rtx_insn *head, rtx_insn *tail) 4948{ 4949 rtx_insn *insn, *next_tail = NEXT_INSN (tail); 4950 int success_in_block = 0; 4951 4952 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 4953 { 4954 struct mem_inc_info mii; 4955 4956 if (!NONDEBUG_INSN_P (insn) || RTX_FRAME_RELATED_P (insn)) 4957 continue; 4958 4959 mii.mem_insn = insn; 4960 if (find_mem (&mii, &PATTERN (insn))) 4961 success_in_block++; 4962 } 4963 if (success_in_block && sched_verbose >= 5) 4964 fprintf (sched_dump, "%d candidates for address modification found.\n", 4965 success_in_block); 4966} 4967 4968#endif /* INSN_SCHEDULING */ 4969