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