sched-deps.c revision 103445
1/* Instruction scheduling pass. This file computes dependencies between 2 instructions. 3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4 1999, 2000, 2001, 2002 Free Software Foundation, Inc. 5 Contributed by Michael Tiemann (tiemann@cygnus.com) Enhanced by, 6 and currently maintained by, Jim Wilson (wilson@cygnus.com) 7 8This file is part of GCC. 9 10GCC is free software; you can redistribute it and/or modify it under 11the terms of the GNU General Public License as published by the Free 12Software Foundation; either version 2, or (at your option) any later 13version. 14 15GCC is distributed in the hope that it will be useful, but WITHOUT ANY 16WARRANTY; without even the implied warranty of MERCHANTABILITY or 17FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 18for more details. 19 20You should have received a copy of the GNU General Public License 21along with GCC; see the file COPYING. If not, write to the Free 22Software Foundation, 59 Temple Place - Suite 330, Boston, MA 2302111-1307, USA. */ 24 25#include "config.h" 26#include "system.h" 27#include "toplev.h" 28#include "rtl.h" 29#include "tm_p.h" 30#include "hard-reg-set.h" 31#include "basic-block.h" 32#include "regs.h" 33#include "function.h" 34#include "flags.h" 35#include "insn-config.h" 36#include "insn-attr.h" 37#include "except.h" 38#include "toplev.h" 39#include "recog.h" 40#include "sched-int.h" 41#include "params.h" 42#include "cselib.h" 43 44extern char *reg_known_equiv_p; 45extern rtx *reg_known_value; 46 47static regset_head reg_pending_sets_head; 48static regset_head reg_pending_clobbers_head; 49static regset_head reg_pending_uses_head; 50 51static regset reg_pending_sets; 52static regset reg_pending_clobbers; 53static regset reg_pending_uses; 54static bool reg_pending_barrier; 55 56/* To speed up the test for duplicate dependency links we keep a 57 record of dependencies created by add_dependence when the average 58 number of instructions in a basic block is very large. 59 60 Studies have shown that there is typically around 5 instructions between 61 branches for typical C code. So we can make a guess that the average 62 basic block is approximately 5 instructions long; we will choose 100X 63 the average size as a very large basic block. 64 65 Each insn has associated bitmaps for its dependencies. Each bitmap 66 has enough entries to represent a dependency on any other insn in 67 the insn chain. All bitmap for true dependencies cache is 68 allocated then the rest two ones are also allocated. */ 69static sbitmap *true_dependency_cache; 70static sbitmap *anti_dependency_cache; 71static sbitmap *output_dependency_cache; 72 73/* To speed up checking consistency of formed forward insn 74 dependencies we use the following cache. Another possible solution 75 could be switching off checking duplication of insns in forward 76 dependencies. */ 77#ifdef ENABLE_CHECKING 78static sbitmap *forward_dependency_cache; 79#endif 80 81static int deps_may_trap_p PARAMS ((rtx)); 82static void add_dependence_list PARAMS ((rtx, rtx, enum reg_note)); 83static void add_dependence_list_and_free PARAMS ((rtx, rtx *, enum reg_note)); 84static void remove_dependence PARAMS ((rtx, rtx)); 85static void set_sched_group_p PARAMS ((rtx)); 86 87static void flush_pending_lists PARAMS ((struct deps *, rtx, int, int)); 88static void sched_analyze_1 PARAMS ((struct deps *, rtx, rtx)); 89static void sched_analyze_2 PARAMS ((struct deps *, rtx, rtx)); 90static void sched_analyze_insn PARAMS ((struct deps *, rtx, rtx, rtx)); 91static rtx group_leader PARAMS ((rtx)); 92 93static rtx get_condition PARAMS ((rtx)); 94static int conditions_mutex_p PARAMS ((rtx, rtx)); 95 96/* Return nonzero if a load of the memory reference MEM can cause a trap. */ 97 98static int 99deps_may_trap_p (mem) 100 rtx mem; 101{ 102 rtx addr = XEXP (mem, 0); 103 104 if (REG_P (addr) 105 && REGNO (addr) >= FIRST_PSEUDO_REGISTER 106 && reg_known_value[REGNO (addr)]) 107 addr = reg_known_value[REGNO (addr)]; 108 return rtx_addr_can_trap_p (addr); 109} 110 111/* Return the INSN_LIST containing INSN in LIST, or NULL 112 if LIST does not contain INSN. */ 113 114rtx 115find_insn_list (insn, list) 116 rtx insn; 117 rtx list; 118{ 119 while (list) 120 { 121 if (XEXP (list, 0) == insn) 122 return list; 123 list = XEXP (list, 1); 124 } 125 return 0; 126} 127 128/* Find the condition under which INSN is executed. */ 129 130static rtx 131get_condition (insn) 132 rtx insn; 133{ 134 rtx pat = PATTERN (insn); 135 rtx cond; 136 137 if (pat == 0) 138 return 0; 139 if (GET_CODE (pat) == COND_EXEC) 140 return COND_EXEC_TEST (pat); 141 if (GET_CODE (insn) != JUMP_INSN) 142 return 0; 143 if (GET_CODE (pat) != SET || SET_SRC (pat) != pc_rtx) 144 return 0; 145 if (GET_CODE (SET_DEST (pat)) != IF_THEN_ELSE) 146 return 0; 147 pat = SET_DEST (pat); 148 cond = XEXP (pat, 0); 149 if (GET_CODE (XEXP (cond, 1)) == LABEL_REF 150 && XEXP (cond, 2) == pc_rtx) 151 return cond; 152 else if (GET_CODE (XEXP (cond, 2)) == LABEL_REF 153 && XEXP (cond, 1) == pc_rtx) 154 return gen_rtx_fmt_ee (reverse_condition (GET_CODE (cond)), GET_MODE (cond), 155 XEXP (cond, 0), XEXP (cond, 1)); 156 else 157 return 0; 158} 159 160/* Return nonzero if conditions COND1 and COND2 can never be both true. */ 161 162static int 163conditions_mutex_p (cond1, cond2) 164 rtx cond1, cond2; 165{ 166 if (GET_RTX_CLASS (GET_CODE (cond1)) == '<' 167 && GET_RTX_CLASS (GET_CODE (cond2)) == '<' 168 && GET_CODE (cond1) == reverse_condition (GET_CODE (cond2)) 169 && XEXP (cond1, 0) == XEXP (cond2, 0) 170 && XEXP (cond1, 1) == XEXP (cond2, 1)) 171 return 1; 172 return 0; 173} 174 175/* Add ELEM wrapped in an INSN_LIST with reg note kind DEP_TYPE to the 176 LOG_LINKS of INSN, if not already there. DEP_TYPE indicates the type 177 of dependence that this link represents. */ 178 179void 180add_dependence (insn, elem, dep_type) 181 rtx insn; 182 rtx elem; 183 enum reg_note dep_type; 184{ 185 rtx link, next; 186 int present_p; 187 rtx cond1, cond2; 188 189 /* Don't depend an insn on itself. */ 190 if (insn == elem) 191 return; 192 193 /* We can get a dependency on deleted insns due to optimizations in 194 the register allocation and reloading or due to splitting. Any 195 such dependency is useless and can be ignored. */ 196 if (GET_CODE (elem) == NOTE) 197 return; 198 199 /* flow.c doesn't handle conditional lifetimes entirely correctly; 200 calls mess up the conditional lifetimes. */ 201 /* ??? add_dependence is the wrong place to be eliding dependencies, 202 as that forgets that the condition expressions themselves may 203 be dependent. */ 204 if (GET_CODE (insn) != CALL_INSN && GET_CODE (elem) != CALL_INSN) 205 { 206 cond1 = get_condition (insn); 207 cond2 = get_condition (elem); 208 if (cond1 && cond2 209 && conditions_mutex_p (cond1, cond2) 210 /* Make sure first instruction doesn't affect condition of second 211 instruction if switched. */ 212 && !modified_in_p (cond1, elem) 213 /* Make sure second instruction doesn't affect condition of first 214 instruction if switched. */ 215 && !modified_in_p (cond2, insn)) 216 return; 217 } 218 219 /* If elem is part of a sequence that must be scheduled together, then 220 make the dependence point to the last insn of the sequence. 221 When HAVE_cc0, it is possible for NOTEs to exist between users and 222 setters of the condition codes, so we must skip past notes here. 223 Otherwise, NOTEs are impossible here. */ 224 next = next_nonnote_insn (elem); 225 if (next && SCHED_GROUP_P (next) 226 && GET_CODE (next) != CODE_LABEL) 227 { 228 /* Notes will never intervene here though, so don't bother checking 229 for them. */ 230 /* Hah! Wrong. */ 231 /* We must reject CODE_LABELs, so that we don't get confused by one 232 that has LABEL_PRESERVE_P set, which is represented by the same 233 bit in the rtl as SCHED_GROUP_P. A CODE_LABEL can never be 234 SCHED_GROUP_P. */ 235 236 rtx nnext; 237 while ((nnext = next_nonnote_insn (next)) != NULL 238 && SCHED_GROUP_P (nnext) 239 && GET_CODE (nnext) != CODE_LABEL) 240 next = nnext; 241 242 /* Again, don't depend an insn on itself. */ 243 if (insn == next) 244 return; 245 246 /* Make the dependence to NEXT, the last insn of the group, instead 247 of the original ELEM. */ 248 elem = next; 249 } 250 251 present_p = 1; 252#ifdef INSN_SCHEDULING 253 /* ??? No good way to tell from here whether we're doing interblock 254 scheduling. Possibly add another callback. */ 255#if 0 256 /* (This code is guarded by INSN_SCHEDULING, otherwise INSN_BB is undefined.) 257 No need for interblock dependences with calls, since 258 calls are not moved between blocks. Note: the edge where 259 elem is a CALL is still required. */ 260 if (GET_CODE (insn) == CALL_INSN 261 && (INSN_BB (elem) != INSN_BB (insn))) 262 return; 263#endif 264 265 /* If we already have a dependency for ELEM, then we do not need to 266 do anything. Avoiding the list walk below can cut compile times 267 dramatically for some code. */ 268 if (true_dependency_cache != NULL) 269 { 270 enum reg_note present_dep_type = 0; 271 272 if (anti_dependency_cache == NULL || output_dependency_cache == NULL) 273 abort (); 274 if (TEST_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem))) 275 /* Do nothing (present_set_type is already 0). */ 276 ; 277 else if (TEST_BIT (anti_dependency_cache[INSN_LUID (insn)], 278 INSN_LUID (elem))) 279 present_dep_type = REG_DEP_ANTI; 280 else if (TEST_BIT (output_dependency_cache[INSN_LUID (insn)], 281 INSN_LUID (elem))) 282 present_dep_type = REG_DEP_OUTPUT; 283 else 284 present_p = 0; 285 if (present_p && (int) dep_type >= (int) present_dep_type) 286 return; 287 } 288#endif 289 290 /* Check that we don't already have this dependence. */ 291 if (present_p) 292 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 293 if (XEXP (link, 0) == elem) 294 { 295#ifdef INSN_SCHEDULING 296 /* Clear corresponding cache entry because type of the link 297 may be changed. */ 298 if (true_dependency_cache != NULL) 299 { 300 if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 301 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 302 INSN_LUID (elem)); 303 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT 304 && output_dependency_cache) 305 RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 306 INSN_LUID (elem)); 307 else 308 abort (); 309 } 310#endif 311 312 /* If this is a more restrictive type of dependence than the existing 313 one, then change the existing dependence to this type. */ 314 if ((int) dep_type < (int) REG_NOTE_KIND (link)) 315 PUT_REG_NOTE_KIND (link, dep_type); 316 317#ifdef INSN_SCHEDULING 318 /* If we are adding a dependency to INSN's LOG_LINKs, then 319 note that in the bitmap caches of dependency information. */ 320 if (true_dependency_cache != NULL) 321 { 322 if ((int) REG_NOTE_KIND (link) == 0) 323 SET_BIT (true_dependency_cache[INSN_LUID (insn)], 324 INSN_LUID (elem)); 325 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 326 SET_BIT (anti_dependency_cache[INSN_LUID (insn)], 327 INSN_LUID (elem)); 328 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 329 SET_BIT (output_dependency_cache[INSN_LUID (insn)], 330 INSN_LUID (elem)); 331 } 332#endif 333 return; 334 } 335 /* Might want to check one level of transitivity to save conses. */ 336 337 link = alloc_INSN_LIST (elem, LOG_LINKS (insn)); 338 LOG_LINKS (insn) = link; 339 340 /* Insn dependency, not data dependency. */ 341 PUT_REG_NOTE_KIND (link, dep_type); 342 343#ifdef INSN_SCHEDULING 344 /* If we are adding a dependency to INSN's LOG_LINKs, then note that 345 in the bitmap caches of dependency information. */ 346 if (true_dependency_cache != NULL) 347 { 348 if ((int) dep_type == 0) 349 SET_BIT (true_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 350 else if (dep_type == REG_DEP_ANTI) 351 SET_BIT (anti_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 352 else if (dep_type == REG_DEP_OUTPUT) 353 SET_BIT (output_dependency_cache[INSN_LUID (insn)], INSN_LUID (elem)); 354 } 355#endif 356} 357 358/* A convenience wrapper to operate on an entire list. */ 359 360static void 361add_dependence_list (insn, list, dep_type) 362 rtx insn, list; 363 enum reg_note dep_type; 364{ 365 for (; list; list = XEXP (list, 1)) 366 add_dependence (insn, XEXP (list, 0), dep_type); 367} 368 369/* Similar, but free *LISTP at the same time. */ 370 371static void 372add_dependence_list_and_free (insn, listp, dep_type) 373 rtx insn; 374 rtx *listp; 375 enum reg_note dep_type; 376{ 377 rtx list, next; 378 for (list = *listp, *listp = NULL; list ; list = next) 379 { 380 next = XEXP (list, 1); 381 add_dependence (insn, XEXP (list, 0), dep_type); 382 free_INSN_LIST_node (list); 383 } 384} 385 386/* Remove ELEM wrapped in an INSN_LIST from the LOG_LINKS 387 of INSN. Abort if not found. */ 388 389static void 390remove_dependence (insn, elem) 391 rtx insn; 392 rtx elem; 393{ 394 rtx prev, link, next; 395 int found = 0; 396 397 for (prev = 0, link = LOG_LINKS (insn); link; link = next) 398 { 399 next = XEXP (link, 1); 400 if (XEXP (link, 0) == elem) 401 { 402 if (prev) 403 XEXP (prev, 1) = next; 404 else 405 LOG_LINKS (insn) = next; 406 407#ifdef INSN_SCHEDULING 408 /* If we are removing a dependency from the LOG_LINKS list, 409 make sure to remove it from the cache too. */ 410 if (true_dependency_cache != NULL) 411 { 412 if (REG_NOTE_KIND (link) == 0) 413 RESET_BIT (true_dependency_cache[INSN_LUID (insn)], 414 INSN_LUID (elem)); 415 else if (REG_NOTE_KIND (link) == REG_DEP_ANTI) 416 RESET_BIT (anti_dependency_cache[INSN_LUID (insn)], 417 INSN_LUID (elem)); 418 else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT) 419 RESET_BIT (output_dependency_cache[INSN_LUID (insn)], 420 INSN_LUID (elem)); 421 } 422#endif 423 424 free_INSN_LIST_node (link); 425 426 found = 1; 427 } 428 else 429 prev = link; 430 } 431 432 if (!found) 433 abort (); 434 return; 435} 436 437/* Return an insn which represents a SCHED_GROUP, which is 438 the last insn in the group. */ 439 440static rtx 441group_leader (insn) 442 rtx insn; 443{ 444 rtx prev; 445 446 do 447 { 448 prev = insn; 449 insn = next_nonnote_insn (insn); 450 } 451 while (insn && SCHED_GROUP_P (insn) && (GET_CODE (insn) != CODE_LABEL)); 452 453 return prev; 454} 455 456/* Set SCHED_GROUP_P and care for the rest of the bookkeeping that 457 goes along with that. */ 458 459static void 460set_sched_group_p (insn) 461 rtx insn; 462{ 463 rtx link, prev; 464 465 SCHED_GROUP_P (insn) = 1; 466 467 /* There may be a note before this insn now, but all notes will 468 be removed before we actually try to schedule the insns, so 469 it won't cause a problem later. We must avoid it here though. */ 470 prev = prev_nonnote_insn (insn); 471 472 /* Make a copy of all dependencies on the immediately previous insn, 473 and add to this insn. This is so that all the dependencies will 474 apply to the group. Remove an explicit dependence on this insn 475 as SCHED_GROUP_P now represents it. */ 476 477 if (find_insn_list (prev, LOG_LINKS (insn))) 478 remove_dependence (insn, prev); 479 480 for (link = LOG_LINKS (prev); link; link = XEXP (link, 1)) 481 add_dependence (insn, XEXP (link, 0), REG_NOTE_KIND (link)); 482} 483 484/* Process an insn's memory dependencies. There are four kinds of 485 dependencies: 486 487 (0) read dependence: read follows read 488 (1) true dependence: read follows write 489 (2) anti dependence: write follows read 490 (3) output dependence: write follows write 491 492 We are careful to build only dependencies which actually exist, and 493 use transitivity to avoid building too many links. */ 494 495/* Add an INSN and MEM reference pair to a pending INSN_LIST and MEM_LIST. 496 The MEM is a memory reference contained within INSN, which we are saving 497 so that we can do memory aliasing on it. */ 498 499void 500add_insn_mem_dependence (deps, insn_list, mem_list, insn, mem) 501 struct deps *deps; 502 rtx *insn_list, *mem_list, insn, mem; 503{ 504 rtx link; 505 506 link = alloc_INSN_LIST (insn, *insn_list); 507 *insn_list = link; 508 509 if (current_sched_info->use_cselib) 510 { 511 mem = shallow_copy_rtx (mem); 512 XEXP (mem, 0) = cselib_subst_to_values (XEXP (mem, 0)); 513 } 514 link = alloc_EXPR_LIST (VOIDmode, mem, *mem_list); 515 *mem_list = link; 516 517 deps->pending_lists_length++; 518} 519 520/* Make a dependency between every memory reference on the pending lists 521 and INSN, thus flushing the pending lists. FOR_READ is true if emitting 522 dependencies for a read operation, similarly with FOR_WRITE. */ 523 524static void 525flush_pending_lists (deps, insn, for_read, for_write) 526 struct deps *deps; 527 rtx insn; 528 int for_read, for_write; 529{ 530 if (for_write) 531 { 532 add_dependence_list_and_free (insn, &deps->pending_read_insns, 533 REG_DEP_ANTI); 534 free_EXPR_LIST_list (&deps->pending_read_mems); 535 } 536 537 add_dependence_list_and_free (insn, &deps->pending_write_insns, 538 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 539 free_EXPR_LIST_list (&deps->pending_write_mems); 540 deps->pending_lists_length = 0; 541 542 add_dependence_list_and_free (insn, &deps->last_pending_memory_flush, 543 for_read ? REG_DEP_ANTI : REG_DEP_OUTPUT); 544 deps->last_pending_memory_flush = alloc_INSN_LIST (insn, NULL_RTX); 545 deps->pending_flush_length = 1; 546} 547 548/* Analyze a single SET, CLOBBER, PRE_DEC, POST_DEC, PRE_INC or POST_INC 549 rtx, X, creating all dependencies generated by the write to the 550 destination of X, and reads of everything mentioned. */ 551 552static void 553sched_analyze_1 (deps, x, insn) 554 struct deps *deps; 555 rtx x; 556 rtx insn; 557{ 558 int regno; 559 rtx dest = XEXP (x, 0); 560 enum rtx_code code = GET_CODE (x); 561 562 if (dest == 0) 563 return; 564 565 if (GET_CODE (dest) == PARALLEL) 566 { 567 int i; 568 569 for (i = XVECLEN (dest, 0) - 1; i >= 0; i--) 570 if (XEXP (XVECEXP (dest, 0, i), 0) != 0) 571 sched_analyze_1 (deps, 572 gen_rtx_CLOBBER (VOIDmode, 573 XEXP (XVECEXP (dest, 0, i), 0)), 574 insn); 575 576 if (GET_CODE (x) == SET) 577 sched_analyze_2 (deps, SET_SRC (x), insn); 578 return; 579 } 580 581 while (GET_CODE (dest) == STRICT_LOW_PART || GET_CODE (dest) == SUBREG 582 || GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 583 { 584 if (GET_CODE (dest) == ZERO_EXTRACT || GET_CODE (dest) == SIGN_EXTRACT) 585 { 586 /* The second and third arguments are values read by this insn. */ 587 sched_analyze_2 (deps, XEXP (dest, 1), insn); 588 sched_analyze_2 (deps, XEXP (dest, 2), insn); 589 } 590 dest = XEXP (dest, 0); 591 } 592 593 if (GET_CODE (dest) == REG) 594 { 595 regno = REGNO (dest); 596 597 /* A hard reg in a wide mode may really be multiple registers. 598 If so, mark all of them just like the first. */ 599 if (regno < FIRST_PSEUDO_REGISTER) 600 { 601 int i = HARD_REGNO_NREGS (regno, GET_MODE (dest)); 602 if (code == SET) 603 { 604 while (--i >= 0) 605 SET_REGNO_REG_SET (reg_pending_sets, regno + i); 606 } 607 else 608 { 609 while (--i >= 0) 610 SET_REGNO_REG_SET (reg_pending_clobbers, regno + i); 611 } 612 } 613 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 614 it does not reload. Ignore these as they have served their 615 purpose already. */ 616 else if (regno >= deps->max_reg) 617 { 618 if (GET_CODE (PATTERN (insn)) != USE 619 && GET_CODE (PATTERN (insn)) != CLOBBER) 620 abort (); 621 } 622 else 623 { 624 if (code == SET) 625 SET_REGNO_REG_SET (reg_pending_sets, regno); 626 else 627 SET_REGNO_REG_SET (reg_pending_clobbers, regno); 628 629 /* Pseudos that are REG_EQUIV to something may be replaced 630 by that during reloading. We need only add dependencies for 631 the address in the REG_EQUIV note. */ 632 if (!reload_completed 633 && reg_known_equiv_p[regno] 634 && GET_CODE (reg_known_value[regno]) == MEM) 635 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); 636 637 /* Don't let it cross a call after scheduling if it doesn't 638 already cross one. */ 639 if (REG_N_CALLS_CROSSED (regno) == 0) 640 add_dependence_list (insn, deps->last_function_call, REG_DEP_ANTI); 641 } 642 } 643 else if (GET_CODE (dest) == MEM) 644 { 645 /* Writing memory. */ 646 rtx t = dest; 647 648 if (current_sched_info->use_cselib) 649 { 650 t = shallow_copy_rtx (dest); 651 cselib_lookup (XEXP (t, 0), Pmode, 1); 652 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0)); 653 } 654 655 if (deps->pending_lists_length > MAX_PENDING_LIST_LENGTH) 656 { 657 /* Flush all pending reads and writes to prevent the pending lists 658 from getting any larger. Insn scheduling runs too slowly when 659 these lists get long. When compiling GCC with itself, 660 this flush occurs 8 times for sparc, and 10 times for m88k using 661 the default value of 32. */ 662 flush_pending_lists (deps, insn, false, true); 663 } 664 else 665 { 666 rtx pending, pending_mem; 667 668 pending = deps->pending_read_insns; 669 pending_mem = deps->pending_read_mems; 670 while (pending) 671 { 672 if (anti_dependence (XEXP (pending_mem, 0), t)) 673 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); 674 675 pending = XEXP (pending, 1); 676 pending_mem = XEXP (pending_mem, 1); 677 } 678 679 pending = deps->pending_write_insns; 680 pending_mem = deps->pending_write_mems; 681 while (pending) 682 { 683 if (output_dependence (XEXP (pending_mem, 0), t)) 684 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 685 686 pending = XEXP (pending, 1); 687 pending_mem = XEXP (pending_mem, 1); 688 } 689 690 add_dependence_list (insn, deps->last_pending_memory_flush, 691 REG_DEP_ANTI); 692 693 add_insn_mem_dependence (deps, &deps->pending_write_insns, 694 &deps->pending_write_mems, insn, dest); 695 } 696 sched_analyze_2 (deps, XEXP (dest, 0), insn); 697 } 698 699 /* Analyze reads. */ 700 if (GET_CODE (x) == SET) 701 sched_analyze_2 (deps, SET_SRC (x), insn); 702} 703 704/* Analyze the uses of memory and registers in rtx X in INSN. */ 705 706static void 707sched_analyze_2 (deps, x, insn) 708 struct deps *deps; 709 rtx x; 710 rtx insn; 711{ 712 int i; 713 int j; 714 enum rtx_code code; 715 const char *fmt; 716 717 if (x == 0) 718 return; 719 720 code = GET_CODE (x); 721 722 switch (code) 723 { 724 case CONST_INT: 725 case CONST_DOUBLE: 726 case CONST_VECTOR: 727 case SYMBOL_REF: 728 case CONST: 729 case LABEL_REF: 730 /* Ignore constants. Note that we must handle CONST_DOUBLE here 731 because it may have a cc0_rtx in its CONST_DOUBLE_CHAIN field, but 732 this does not mean that this insn is using cc0. */ 733 return; 734 735#ifdef HAVE_cc0 736 case CC0: 737 /* User of CC0 depends on immediately preceding insn. */ 738 set_sched_group_p (insn); 739 return; 740#endif 741 742 case REG: 743 { 744 int regno = REGNO (x); 745 if (regno < FIRST_PSEUDO_REGISTER) 746 { 747 int i = HARD_REGNO_NREGS (regno, GET_MODE (x)); 748 while (--i >= 0) 749 SET_REGNO_REG_SET (reg_pending_uses, regno + i); 750 } 751 /* ??? Reload sometimes emits USEs and CLOBBERs of pseudos that 752 it does not reload. Ignore these as they have served their 753 purpose already. */ 754 else if (regno >= deps->max_reg) 755 { 756 if (GET_CODE (PATTERN (insn)) != USE 757 && GET_CODE (PATTERN (insn)) != CLOBBER) 758 abort (); 759 } 760 else 761 { 762 SET_REGNO_REG_SET (reg_pending_uses, regno); 763 764 /* Pseudos that are REG_EQUIV to something may be replaced 765 by that during reloading. We need only add dependencies for 766 the address in the REG_EQUIV note. */ 767 if (!reload_completed 768 && reg_known_equiv_p[regno] 769 && GET_CODE (reg_known_value[regno]) == MEM) 770 sched_analyze_2 (deps, XEXP (reg_known_value[regno], 0), insn); 771 772 /* If the register does not already cross any calls, then add this 773 insn to the sched_before_next_call list so that it will still 774 not cross calls after scheduling. */ 775 if (REG_N_CALLS_CROSSED (regno) == 0) 776 deps->sched_before_next_call 777 = alloc_INSN_LIST (insn, deps->sched_before_next_call); 778 } 779 return; 780 } 781 782 case MEM: 783 { 784 /* Reading memory. */ 785 rtx u; 786 rtx pending, pending_mem; 787 rtx t = x; 788 789 if (current_sched_info->use_cselib) 790 { 791 t = shallow_copy_rtx (t); 792 cselib_lookup (XEXP (t, 0), Pmode, 1); 793 XEXP (t, 0) = cselib_subst_to_values (XEXP (t, 0)); 794 } 795 pending = deps->pending_read_insns; 796 pending_mem = deps->pending_read_mems; 797 while (pending) 798 { 799 if (read_dependence (XEXP (pending_mem, 0), t)) 800 add_dependence (insn, XEXP (pending, 0), REG_DEP_ANTI); 801 802 pending = XEXP (pending, 1); 803 pending_mem = XEXP (pending_mem, 1); 804 } 805 806 pending = deps->pending_write_insns; 807 pending_mem = deps->pending_write_mems; 808 while (pending) 809 { 810 if (true_dependence (XEXP (pending_mem, 0), VOIDmode, 811 t, rtx_varies_p)) 812 add_dependence (insn, XEXP (pending, 0), 0); 813 814 pending = XEXP (pending, 1); 815 pending_mem = XEXP (pending_mem, 1); 816 } 817 818 for (u = deps->last_pending_memory_flush; u; u = XEXP (u, 1)) 819 if (GET_CODE (XEXP (u, 0)) != JUMP_INSN 820 || deps_may_trap_p (x)) 821 add_dependence (insn, XEXP (u, 0), REG_DEP_ANTI); 822 823 /* Always add these dependencies to pending_reads, since 824 this insn may be followed by a write. */ 825 add_insn_mem_dependence (deps, &deps->pending_read_insns, 826 &deps->pending_read_mems, insn, x); 827 828 /* Take advantage of tail recursion here. */ 829 sched_analyze_2 (deps, XEXP (x, 0), insn); 830 return; 831 } 832 833 /* Force pending stores to memory in case a trap handler needs them. */ 834 case TRAP_IF: 835 flush_pending_lists (deps, insn, true, false); 836 break; 837 838 case ASM_OPERANDS: 839 case ASM_INPUT: 840 case UNSPEC_VOLATILE: 841 { 842 /* Traditional and volatile asm instructions must be considered to use 843 and clobber all hard registers, all pseudo-registers and all of 844 memory. So must TRAP_IF and UNSPEC_VOLATILE operations. 845 846 Consider for instance a volatile asm that changes the fpu rounding 847 mode. An insn should not be moved across this even if it only uses 848 pseudo-regs because it might give an incorrectly rounded result. */ 849 if (code != ASM_OPERANDS || MEM_VOLATILE_P (x)) 850 reg_pending_barrier = true; 851 852 /* For all ASM_OPERANDS, we must traverse the vector of input operands. 853 We can not just fall through here since then we would be confused 854 by the ASM_INPUT rtx inside ASM_OPERANDS, which do not indicate 855 traditional asms unlike their normal usage. */ 856 857 if (code == ASM_OPERANDS) 858 { 859 for (j = 0; j < ASM_OPERANDS_INPUT_LENGTH (x); j++) 860 sched_analyze_2 (deps, ASM_OPERANDS_INPUT (x, j), insn); 861 return; 862 } 863 break; 864 } 865 866 case PRE_DEC: 867 case POST_DEC: 868 case PRE_INC: 869 case POST_INC: 870 /* These both read and modify the result. We must handle them as writes 871 to get proper dependencies for following instructions. We must handle 872 them as reads to get proper dependencies from this to previous 873 instructions. Thus we need to pass them to both sched_analyze_1 874 and sched_analyze_2. We must call sched_analyze_2 first in order 875 to get the proper antecedent for the read. */ 876 sched_analyze_2 (deps, XEXP (x, 0), insn); 877 sched_analyze_1 (deps, x, insn); 878 return; 879 880 case POST_MODIFY: 881 case PRE_MODIFY: 882 /* op0 = op0 + op1 */ 883 sched_analyze_2 (deps, XEXP (x, 0), insn); 884 sched_analyze_2 (deps, XEXP (x, 1), insn); 885 sched_analyze_1 (deps, x, insn); 886 return; 887 888 default: 889 break; 890 } 891 892 /* Other cases: walk the insn. */ 893 fmt = GET_RTX_FORMAT (code); 894 for (i = GET_RTX_LENGTH (code) - 1; i >= 0; i--) 895 { 896 if (fmt[i] == 'e') 897 sched_analyze_2 (deps, XEXP (x, i), insn); 898 else if (fmt[i] == 'E') 899 for (j = 0; j < XVECLEN (x, i); j++) 900 sched_analyze_2 (deps, XVECEXP (x, i, j), insn); 901 } 902} 903 904/* Analyze an INSN with pattern X to find all dependencies. */ 905 906static void 907sched_analyze_insn (deps, x, insn, loop_notes) 908 struct deps *deps; 909 rtx x, insn; 910 rtx loop_notes; 911{ 912 RTX_CODE code = GET_CODE (x); 913 rtx link; 914 int i; 915 916 if (code == COND_EXEC) 917 { 918 sched_analyze_2 (deps, COND_EXEC_TEST (x), insn); 919 920 /* ??? Should be recording conditions so we reduce the number of 921 false dependencies. */ 922 x = COND_EXEC_CODE (x); 923 code = GET_CODE (x); 924 } 925 if (code == SET || code == CLOBBER) 926 sched_analyze_1 (deps, x, insn); 927 else if (code == PARALLEL) 928 { 929 int i; 930 for (i = XVECLEN (x, 0) - 1; i >= 0; i--) 931 { 932 rtx sub = XVECEXP (x, 0, i); 933 code = GET_CODE (sub); 934 935 if (code == COND_EXEC) 936 { 937 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); 938 sub = COND_EXEC_CODE (sub); 939 code = GET_CODE (sub); 940 } 941 if (code == SET || code == CLOBBER) 942 sched_analyze_1 (deps, sub, insn); 943 else 944 sched_analyze_2 (deps, sub, insn); 945 } 946 } 947 else 948 sched_analyze_2 (deps, x, insn); 949 950 /* Mark registers CLOBBERED or used by called function. */ 951 if (GET_CODE (insn) == CALL_INSN) 952 { 953 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 954 { 955 if (GET_CODE (XEXP (link, 0)) == CLOBBER) 956 sched_analyze_1 (deps, XEXP (link, 0), insn); 957 else 958 sched_analyze_2 (deps, XEXP (link, 0), insn); 959 } 960 if (find_reg_note (insn, REG_SETJMP, NULL)) 961 reg_pending_barrier = true; 962 } 963 964 if (GET_CODE (insn) == JUMP_INSN) 965 { 966 rtx next; 967 next = next_nonnote_insn (insn); 968 if (next && GET_CODE (next) == BARRIER) 969 reg_pending_barrier = true; 970 else 971 { 972 rtx pending, pending_mem; 973 regset_head tmp; 974 INIT_REG_SET (&tmp); 975 976 (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp); 977 IOR_REG_SET (reg_pending_uses, &tmp); 978 CLEAR_REG_SET (&tmp); 979 980 /* All memory writes and volatile reads must happen before the 981 jump. Non-volatile reads must happen before the jump iff 982 the result is needed by the above register used mask. */ 983 984 pending = deps->pending_write_insns; 985 pending_mem = deps->pending_write_mems; 986 while (pending) 987 { 988 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 989 pending = XEXP (pending, 1); 990 pending_mem = XEXP (pending_mem, 1); 991 } 992 993 pending = deps->pending_read_insns; 994 pending_mem = deps->pending_read_mems; 995 while (pending) 996 { 997 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))) 998 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 999 pending = XEXP (pending, 1); 1000 pending_mem = XEXP (pending_mem, 1); 1001 } 1002 1003 add_dependence_list (insn, deps->last_pending_memory_flush, 1004 REG_DEP_ANTI); 1005 } 1006 } 1007 1008 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic 1009 block, then we must be sure that no instructions are scheduled across it. 1010 Otherwise, the reg_n_refs info (which depends on loop_depth) would 1011 become incorrect. */ 1012 if (loop_notes) 1013 { 1014 rtx link; 1015 1016 /* Update loop_notes with any notes from this insn. Also determine 1017 if any of the notes on the list correspond to instruction scheduling 1018 barriers (loop, eh & setjmp notes, but not range notes). */ 1019 link = loop_notes; 1020 while (XEXP (link, 1)) 1021 { 1022 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG 1023 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END 1024 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG 1025 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END) 1026 reg_pending_barrier = true; 1027 1028 link = XEXP (link, 1); 1029 } 1030 XEXP (link, 1) = REG_NOTES (insn); 1031 REG_NOTES (insn) = loop_notes; 1032 } 1033 1034 /* If this instruction can throw an exception, then moving it changes 1035 where block boundaries fall. This is mighty confusing elsewhere. 1036 Therefore, prevent such an instruction from being moved. */ 1037 if (can_throw_internal (insn)) 1038 reg_pending_barrier = true; 1039 1040 /* Add dependencies if a scheduling barrier was found. */ 1041 if (reg_pending_barrier) 1042 { 1043 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1044 { 1045 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1046 { 1047 struct deps_reg *reg_last = &deps->reg_last[i]; 1048 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1049 add_dependence_list (insn, reg_last->sets, 0); 1050 add_dependence_list (insn, reg_last->clobbers, 0); 1051 }); 1052 } 1053 else 1054 { 1055 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1056 { 1057 struct deps_reg *reg_last = &deps->reg_last[i]; 1058 add_dependence_list_and_free (insn, ®_last->uses, 1059 REG_DEP_ANTI); 1060 add_dependence_list_and_free (insn, ®_last->sets, 0); 1061 add_dependence_list_and_free (insn, ®_last->clobbers, 0); 1062 reg_last->uses_length = 0; 1063 reg_last->clobbers_length = 0; 1064 }); 1065 } 1066 1067 for (i = 0; i < deps->max_reg; i++) 1068 { 1069 struct deps_reg *reg_last = &deps->reg_last[i]; 1070 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1071 SET_REGNO_REG_SET (&deps->reg_last_in_use, i); 1072 } 1073 1074 flush_pending_lists (deps, insn, true, true); 1075 reg_pending_barrier = false; 1076 } 1077 else 1078 { 1079 /* If the current insn is conditional, we can't free any 1080 of the lists. */ 1081 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1082 { 1083 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 1084 { 1085 struct deps_reg *reg_last = &deps->reg_last[i]; 1086 add_dependence_list (insn, reg_last->sets, 0); 1087 add_dependence_list (insn, reg_last->clobbers, 0); 1088 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 1089 reg_last->uses_length++; 1090 }); 1091 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 1092 { 1093 struct deps_reg *reg_last = &deps->reg_last[i]; 1094 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 1095 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1096 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 1097 reg_last->clobbers_length++; 1098 }); 1099 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 1100 { 1101 struct deps_reg *reg_last = &deps->reg_last[i]; 1102 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 1103 add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT); 1104 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1105 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1106 }); 1107 } 1108 else 1109 { 1110 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 1111 { 1112 struct deps_reg *reg_last = &deps->reg_last[i]; 1113 add_dependence_list (insn, reg_last->sets, 0); 1114 add_dependence_list (insn, reg_last->clobbers, 0); 1115 reg_last->uses_length++; 1116 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 1117 }); 1118 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 1119 { 1120 struct deps_reg *reg_last = &deps->reg_last[i]; 1121 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH 1122 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH) 1123 { 1124 add_dependence_list_and_free (insn, ®_last->sets, 1125 REG_DEP_OUTPUT); 1126 add_dependence_list_and_free (insn, ®_last->uses, 1127 REG_DEP_ANTI); 1128 add_dependence_list_and_free (insn, ®_last->clobbers, 1129 REG_DEP_OUTPUT); 1130 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1131 reg_last->clobbers_length = 0; 1132 reg_last->uses_length = 0; 1133 } 1134 else 1135 { 1136 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 1137 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1138 } 1139 reg_last->clobbers_length++; 1140 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 1141 }); 1142 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 1143 { 1144 struct deps_reg *reg_last = &deps->reg_last[i]; 1145 add_dependence_list_and_free (insn, ®_last->sets, 1146 REG_DEP_OUTPUT); 1147 add_dependence_list_and_free (insn, ®_last->clobbers, 1148 REG_DEP_OUTPUT); 1149 add_dependence_list_and_free (insn, ®_last->uses, 1150 REG_DEP_ANTI); 1151 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1152 reg_last->uses_length = 0; 1153 reg_last->clobbers_length = 0; 1154 }); 1155 } 1156 1157 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); 1158 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); 1159 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); 1160 } 1161 CLEAR_REG_SET (reg_pending_uses); 1162 CLEAR_REG_SET (reg_pending_clobbers); 1163 CLEAR_REG_SET (reg_pending_sets); 1164 1165 /* If we are currently in a libcall scheduling group, then mark the 1166 current insn as being in a scheduling group and that it can not 1167 be moved into a different basic block. */ 1168 1169 if (deps->libcall_block_tail_insn) 1170 { 1171 set_sched_group_p (insn); 1172 CANT_MOVE (insn) = 1; 1173 } 1174 1175 /* If a post-call group is still open, see if it should remain so. 1176 This insn must be a simple move of a hard reg to a pseudo or 1177 vice-versa. 1178 1179 We must avoid moving these insns for correctness on 1180 SMALL_REGISTER_CLASS machines, and for special registers like 1181 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all 1182 hard regs for all targets. */ 1183 1184 if (deps->in_post_call_group_p) 1185 { 1186 rtx tmp, set = single_set (insn); 1187 int src_regno, dest_regno; 1188 1189 if (set == NULL) 1190 goto end_call_group; 1191 1192 tmp = SET_DEST (set); 1193 if (GET_CODE (tmp) == SUBREG) 1194 tmp = SUBREG_REG (tmp); 1195 if (GET_CODE (tmp) == REG) 1196 dest_regno = REGNO (tmp); 1197 else 1198 goto end_call_group; 1199 1200 tmp = SET_SRC (set); 1201 if (GET_CODE (tmp) == SUBREG) 1202 tmp = SUBREG_REG (tmp); 1203 if (GET_CODE (tmp) == REG) 1204 src_regno = REGNO (tmp); 1205 else 1206 goto end_call_group; 1207 1208 if (src_regno < FIRST_PSEUDO_REGISTER 1209 || dest_regno < FIRST_PSEUDO_REGISTER) 1210 { 1211 set_sched_group_p (insn); 1212 CANT_MOVE (insn) = 1; 1213 } 1214 else 1215 { 1216 end_call_group: 1217 deps->in_post_call_group_p = false; 1218 } 1219 } 1220} 1221 1222/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS 1223 for every dependency. */ 1224 1225void 1226sched_analyze (deps, head, tail) 1227 struct deps *deps; 1228 rtx head, tail; 1229{ 1230 rtx insn; 1231 rtx loop_notes = 0; 1232 1233 if (current_sched_info->use_cselib) 1234 cselib_init (); 1235 1236 for (insn = head;; insn = NEXT_INSN (insn)) 1237 { 1238 rtx link, end_seq, r0, set, note; 1239 1240 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1241 { 1242 /* Clear out the stale LOG_LINKS from flow. */ 1243 free_INSN_LIST_list (&LOG_LINKS (insn)); 1244 1245 /* Clear out stale SCHED_GROUP_P. */ 1246 SCHED_GROUP_P (insn) = 0; 1247 1248 /* Make each JUMP_INSN a scheduling barrier for memory 1249 references. */ 1250 if (GET_CODE (insn) == JUMP_INSN) 1251 { 1252 /* Keep the list a reasonable size. */ 1253 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH) 1254 flush_pending_lists (deps, insn, true, true); 1255 else 1256 deps->last_pending_memory_flush 1257 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); 1258 } 1259 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 1260 loop_notes = 0; 1261 } 1262 else if (GET_CODE (insn) == CALL_INSN) 1263 { 1264 int i; 1265 1266 CANT_MOVE (insn) = 1; 1267 1268 /* Clear out the stale LOG_LINKS from flow. */ 1269 free_INSN_LIST_list (&LOG_LINKS (insn)); 1270 1271 if (find_reg_note (insn, REG_SETJMP, NULL)) 1272 { 1273 /* This is setjmp. Assume that all registers, not just 1274 hard registers, may be clobbered by this call. */ 1275 reg_pending_barrier = true; 1276 } 1277 else 1278 { 1279 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1280 /* A call may read and modify global register variables. */ 1281 if (global_regs[i]) 1282 { 1283 SET_REGNO_REG_SET (reg_pending_sets, i); 1284 SET_REGNO_REG_SET (reg_pending_uses, i); 1285 } 1286 /* Other call-clobbered hard regs may be clobbered. */ 1287 else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1288 SET_REGNO_REG_SET (reg_pending_clobbers, i); 1289 /* We don't know what set of fixed registers might be used 1290 by the function, but it is certain that the stack pointer 1291 is among them, but be conservative. */ 1292 else if (fixed_regs[i]) 1293 SET_REGNO_REG_SET (reg_pending_uses, i); 1294 /* The frame pointer is normally not used by the function 1295 itself, but by the debugger. */ 1296 /* ??? MIPS o32 is an exception. It uses the frame pointer 1297 in the macro expansion of jal but does not represent this 1298 fact in the call_insn rtl. */ 1299 else if (i == FRAME_POINTER_REGNUM 1300 || (i == HARD_FRAME_POINTER_REGNUM 1301 && (! reload_completed || frame_pointer_needed))) 1302 SET_REGNO_REG_SET (reg_pending_uses, i); 1303 } 1304 1305 /* For each insn which shouldn't cross a call, add a dependence 1306 between that insn and this call insn. */ 1307 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1308 REG_DEP_ANTI); 1309 1310 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 1311 loop_notes = 0; 1312 1313 /* In the absence of interprocedural alias analysis, we must flush 1314 all pending reads and writes, and start new dependencies starting 1315 from here. But only flush writes for constant calls (which may 1316 be passed a pointer to something we haven't written yet). */ 1317 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn)); 1318 1319 /* Remember the last function call for limiting lifetimes. */ 1320 free_INSN_LIST_list (&deps->last_function_call); 1321 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); 1322 1323 /* Before reload, begin a post-call group, so as to keep the 1324 lifetimes of hard registers correct. */ 1325 if (! reload_completed) 1326 deps->in_post_call_group_p = true; 1327 } 1328 1329 /* See comments on reemit_notes as to why we do this. 1330 ??? Actually, the reemit_notes just say what is done, not why. */ 1331 1332 else if (GET_CODE (insn) == NOTE 1333 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG 1334 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END)) 1335 { 1336 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn), 1337 loop_notes); 1338 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1339 GEN_INT (NOTE_LINE_NUMBER (insn)), 1340 loop_notes); 1341 } 1342 else if (GET_CODE (insn) == NOTE 1343 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 1344 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END 1345 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 1346 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 1347 { 1348 rtx rtx_region; 1349 1350 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 1351 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) 1352 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); 1353 else 1354 rtx_region = GEN_INT (0); 1355 1356 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1357 rtx_region, 1358 loop_notes); 1359 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1360 GEN_INT (NOTE_LINE_NUMBER (insn)), 1361 loop_notes); 1362 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn); 1363 } 1364 1365 if (current_sched_info->use_cselib) 1366 cselib_process_insn (insn); 1367 1368 /* Now that we have completed handling INSN, check and see if it is 1369 a CLOBBER beginning a libcall block. If it is, record the 1370 end of the libcall sequence. 1371 1372 We want to schedule libcall blocks as a unit before reload. While 1373 this restricts scheduling, it preserves the meaning of a libcall 1374 block. 1375 1376 As a side effect, we may get better code due to decreased register 1377 pressure as well as less chance of a foreign insn appearing in 1378 a libcall block. */ 1379 if (!reload_completed 1380 /* Note we may have nested libcall sequences. We only care about 1381 the outermost libcall sequence. */ 1382 && deps->libcall_block_tail_insn == 0 1383 /* The sequence must start with a clobber of a register. */ 1384 && GET_CODE (insn) == INSN 1385 && GET_CODE (PATTERN (insn)) == CLOBBER 1386 && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG) 1387 && GET_CODE (XEXP (PATTERN (insn), 0)) == REG 1388 /* The CLOBBER must also have a REG_LIBCALL note attached. */ 1389 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 1390 && (end_seq = XEXP (link, 0)) != 0 1391 /* The insn referenced by the REG_LIBCALL note must be a 1392 simple nop copy with the same destination as the register 1393 mentioned in the clobber. */ 1394 && (set = single_set (end_seq)) != 0 1395 && SET_DEST (set) == r0 && SET_SRC (set) == r0 1396 /* And finally the insn referenced by the REG_LIBCALL must 1397 also contain a REG_EQUAL note and a REG_RETVAL note. */ 1398 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0 1399 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0) 1400 deps->libcall_block_tail_insn = XEXP (link, 0); 1401 1402 /* If we have reached the end of a libcall block, then close the 1403 block. */ 1404 if (deps->libcall_block_tail_insn == insn) 1405 deps->libcall_block_tail_insn = 0; 1406 1407 if (insn == tail) 1408 { 1409 if (current_sched_info->use_cselib) 1410 cselib_finish (); 1411 return; 1412 } 1413 } 1414 abort (); 1415} 1416 1417/* Examine insns in the range [ HEAD, TAIL ] and Use the backward 1418 dependences from LOG_LINKS to build forward dependences in 1419 INSN_DEPEND. */ 1420 1421void 1422compute_forward_dependences (head, tail) 1423 rtx head, tail; 1424{ 1425 rtx insn, link; 1426 rtx next_tail; 1427 enum reg_note dep_type; 1428 1429 next_tail = NEXT_INSN (tail); 1430 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 1431 { 1432 if (! INSN_P (insn)) 1433 continue; 1434 1435 insn = group_leader (insn); 1436 1437 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 1438 { 1439 rtx x = group_leader (XEXP (link, 0)); 1440 rtx new_link; 1441 1442 if (x != XEXP (link, 0)) 1443 continue; 1444 1445#ifdef ENABLE_CHECKING 1446 /* If add_dependence is working properly there should never 1447 be notes, deleted insns or duplicates in the backward 1448 links. Thus we need not check for them here. 1449 1450 However, if we have enabled checking we might as well go 1451 ahead and verify that add_dependence worked properly. */ 1452 if (GET_CODE (x) == NOTE 1453 || INSN_DELETED_P (x) 1454 || (forward_dependency_cache != NULL 1455 && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], 1456 INSN_LUID (insn))) 1457 || (forward_dependency_cache == NULL 1458 && find_insn_list (insn, INSN_DEPEND (x)))) 1459 abort (); 1460 if (forward_dependency_cache != NULL) 1461 SET_BIT (forward_dependency_cache[INSN_LUID (x)], 1462 INSN_LUID (insn)); 1463#endif 1464 1465 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); 1466 1467 dep_type = REG_NOTE_KIND (link); 1468 PUT_REG_NOTE_KIND (new_link, dep_type); 1469 1470 INSN_DEPEND (x) = new_link; 1471 INSN_DEP_COUNT (insn) += 1; 1472 } 1473 } 1474} 1475 1476/* Initialize variables for region data dependence analysis. 1477 n_bbs is the number of region blocks. */ 1478 1479void 1480init_deps (deps) 1481 struct deps *deps; 1482{ 1483 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ()); 1484 1485 deps->max_reg = max_reg; 1486 deps->reg_last = (struct deps_reg *) 1487 xcalloc (max_reg, sizeof (struct deps_reg)); 1488 INIT_REG_SET (&deps->reg_last_in_use); 1489 1490 deps->pending_read_insns = 0; 1491 deps->pending_read_mems = 0; 1492 deps->pending_write_insns = 0; 1493 deps->pending_write_mems = 0; 1494 deps->pending_lists_length = 0; 1495 deps->pending_flush_length = 0; 1496 deps->last_pending_memory_flush = 0; 1497 deps->last_function_call = 0; 1498 deps->sched_before_next_call = 0; 1499 deps->in_post_call_group_p = false; 1500 deps->libcall_block_tail_insn = 0; 1501} 1502 1503/* Free insn lists found in DEPS. */ 1504 1505void 1506free_deps (deps) 1507 struct deps *deps; 1508{ 1509 int i; 1510 1511 free_INSN_LIST_list (&deps->pending_read_insns); 1512 free_EXPR_LIST_list (&deps->pending_read_mems); 1513 free_INSN_LIST_list (&deps->pending_write_insns); 1514 free_EXPR_LIST_list (&deps->pending_write_mems); 1515 free_INSN_LIST_list (&deps->last_pending_memory_flush); 1516 1517 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions 1518 times. For a test case with 42000 regs and 8000 small basic blocks, 1519 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */ 1520 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1521 { 1522 struct deps_reg *reg_last = &deps->reg_last[i]; 1523 free_INSN_LIST_list (®_last->uses); 1524 free_INSN_LIST_list (®_last->sets); 1525 free_INSN_LIST_list (®_last->clobbers); 1526 }); 1527 CLEAR_REG_SET (&deps->reg_last_in_use); 1528 1529 free (deps->reg_last); 1530} 1531 1532/* If it is profitable to use them, initialize caches for tracking 1533 dependency informatino. LUID is the number of insns to be scheduled, 1534 it is used in the estimate of profitability. */ 1535 1536void 1537init_dependency_caches (luid) 1538 int luid; 1539{ 1540 /* ?!? We could save some memory by computing a per-region luid mapping 1541 which could reduce both the number of vectors in the cache and the size 1542 of each vector. Instead we just avoid the cache entirely unless the 1543 average number of instructions in a basic block is very high. See 1544 the comment before the declaration of true_dependency_cache for 1545 what we consider "very high". */ 1546 if (luid / n_basic_blocks > 100 * 5) 1547 { 1548 true_dependency_cache = sbitmap_vector_alloc (luid, luid); 1549 sbitmap_vector_zero (true_dependency_cache, luid); 1550 anti_dependency_cache = sbitmap_vector_alloc (luid, luid); 1551 sbitmap_vector_zero (anti_dependency_cache, luid); 1552 output_dependency_cache = sbitmap_vector_alloc (luid, luid); 1553 sbitmap_vector_zero (output_dependency_cache, luid); 1554#ifdef ENABLE_CHECKING 1555 forward_dependency_cache = sbitmap_vector_alloc (luid, luid); 1556 sbitmap_vector_zero (forward_dependency_cache, luid); 1557#endif 1558 } 1559} 1560 1561/* Free the caches allocated in init_dependency_caches. */ 1562 1563void 1564free_dependency_caches () 1565{ 1566 if (true_dependency_cache) 1567 { 1568 sbitmap_vector_free (true_dependency_cache); 1569 true_dependency_cache = NULL; 1570 sbitmap_vector_free (anti_dependency_cache); 1571 anti_dependency_cache = NULL; 1572 sbitmap_vector_free (output_dependency_cache); 1573 output_dependency_cache = NULL; 1574#ifdef ENABLE_CHECKING 1575 sbitmap_vector_free (forward_dependency_cache); 1576 forward_dependency_cache = NULL; 1577#endif 1578 } 1579} 1580 1581/* Initialize some global variables needed by the dependency analysis 1582 code. */ 1583 1584void 1585init_deps_global () 1586{ 1587 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); 1588 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); 1589 reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head); 1590 reg_pending_barrier = false; 1591} 1592 1593/* Free everything used by the dependency analysis code. */ 1594 1595void 1596finish_deps_global () 1597{ 1598 FREE_REG_SET (reg_pending_sets); 1599 FREE_REG_SET (reg_pending_clobbers); 1600 FREE_REG_SET (reg_pending_uses); 1601} 1602