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)
| 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)
|
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}
| 935 else if (code == PARALLEL) 936 { 937 int i; 938 for (i = XVECLEN (x, 0) - 1; i >= 0; i--) 939 { 940 rtx sub = XVECEXP (x, 0, i); 941 code = GET_CODE (sub); 942 943 if (code == COND_EXEC) 944 { 945 sched_analyze_2 (deps, COND_EXEC_TEST (sub), insn); 946 sub = COND_EXEC_CODE (sub); 947 code = GET_CODE (sub); 948 } 949 if (code == SET || code == CLOBBER) 950 sched_analyze_1 (deps, sub, insn); 951 else 952 sched_analyze_2 (deps, sub, insn); 953 } 954 } 955 else 956 sched_analyze_2 (deps, x, insn); 957 958 /* Mark registers CLOBBERED or used by called function. */ 959 if (GET_CODE (insn) == CALL_INSN) 960 { 961 for (link = CALL_INSN_FUNCTION_USAGE (insn); link; link = XEXP (link, 1)) 962 { 963 if (GET_CODE (XEXP (link, 0)) == CLOBBER) 964 sched_analyze_1 (deps, XEXP (link, 0), insn); 965 else 966 sched_analyze_2 (deps, XEXP (link, 0), insn); 967 } 968 if (find_reg_note (insn, REG_SETJMP, NULL)) 969 reg_pending_barrier = true; 970 } 971 972 if (GET_CODE (insn) == JUMP_INSN) 973 { 974 rtx next; 975 next = next_nonnote_insn (insn); 976 if (next && GET_CODE (next) == BARRIER) 977 reg_pending_barrier = true; 978 else 979 { 980 rtx pending, pending_mem; 981 regset_head tmp; 982 INIT_REG_SET (&tmp); 983 984 (*current_sched_info->compute_jump_reg_dependencies) (insn, &tmp); 985 IOR_REG_SET (reg_pending_uses, &tmp); 986 CLEAR_REG_SET (&tmp); 987 988 /* All memory writes and volatile reads must happen before the 989 jump. Non-volatile reads must happen before the jump iff 990 the result is needed by the above register used mask. */ 991 992 pending = deps->pending_write_insns; 993 pending_mem = deps->pending_write_mems; 994 while (pending) 995 { 996 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 997 pending = XEXP (pending, 1); 998 pending_mem = XEXP (pending_mem, 1); 999 } 1000 1001 pending = deps->pending_read_insns; 1002 pending_mem = deps->pending_read_mems; 1003 while (pending) 1004 { 1005 if (MEM_VOLATILE_P (XEXP (pending_mem, 0))) 1006 add_dependence (insn, XEXP (pending, 0), REG_DEP_OUTPUT); 1007 pending = XEXP (pending, 1); 1008 pending_mem = XEXP (pending_mem, 1); 1009 } 1010 1011 add_dependence_list (insn, deps->last_pending_memory_flush, 1012 REG_DEP_ANTI); 1013 } 1014 } 1015 1016 /* If there is a {LOOP,EHREGION}_{BEG,END} note in the middle of a basic 1017 block, then we must be sure that no instructions are scheduled across it. 1018 Otherwise, the reg_n_refs info (which depends on loop_depth) would 1019 become incorrect. */ 1020 if (loop_notes) 1021 { 1022 rtx link; 1023 1024 /* Update loop_notes with any notes from this insn. Also determine 1025 if any of the notes on the list correspond to instruction scheduling 1026 barriers (loop, eh & setjmp notes, but not range notes). */ 1027 link = loop_notes; 1028 while (XEXP (link, 1)) 1029 { 1030 if (INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_BEG 1031 || INTVAL (XEXP (link, 0)) == NOTE_INSN_LOOP_END 1032 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_BEG 1033 || INTVAL (XEXP (link, 0)) == NOTE_INSN_EH_REGION_END) 1034 reg_pending_barrier = true; 1035 1036 link = XEXP (link, 1); 1037 } 1038 XEXP (link, 1) = REG_NOTES (insn); 1039 REG_NOTES (insn) = loop_notes; 1040 } 1041 1042 /* If this instruction can throw an exception, then moving it changes 1043 where block boundaries fall. This is mighty confusing elsewhere. 1044 Therefore, prevent such an instruction from being moved. */ 1045 if (can_throw_internal (insn)) 1046 reg_pending_barrier = true; 1047 1048 /* Add dependencies if a scheduling barrier was found. */ 1049 if (reg_pending_barrier) 1050 { 1051 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1052 { 1053 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1054 { 1055 struct deps_reg *reg_last = &deps->reg_last[i]; 1056 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1057 add_dependence_list (insn, reg_last->sets, 0); 1058 add_dependence_list (insn, reg_last->clobbers, 0); 1059 }); 1060 } 1061 else 1062 { 1063 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1064 { 1065 struct deps_reg *reg_last = &deps->reg_last[i]; 1066 add_dependence_list_and_free (insn, ®_last->uses, 1067 REG_DEP_ANTI); 1068 add_dependence_list_and_free (insn, ®_last->sets, 0); 1069 add_dependence_list_and_free (insn, ®_last->clobbers, 0); 1070 reg_last->uses_length = 0; 1071 reg_last->clobbers_length = 0; 1072 }); 1073 } 1074 1075 for (i = 0; i < deps->max_reg; i++) 1076 { 1077 struct deps_reg *reg_last = &deps->reg_last[i]; 1078 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1079 SET_REGNO_REG_SET (&deps->reg_last_in_use, i); 1080 } 1081 1082 flush_pending_lists (deps, insn, true, true); 1083 reg_pending_barrier = false; 1084 } 1085 else 1086 { 1087 /* If the current insn is conditional, we can't free any 1088 of the lists. */ 1089 if (GET_CODE (PATTERN (insn)) == COND_EXEC) 1090 { 1091 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 1092 { 1093 struct deps_reg *reg_last = &deps->reg_last[i]; 1094 add_dependence_list (insn, reg_last->sets, 0); 1095 add_dependence_list (insn, reg_last->clobbers, 0); 1096 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 1097 reg_last->uses_length++; 1098 }); 1099 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 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->uses, REG_DEP_ANTI); 1104 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 1105 reg_last->clobbers_length++; 1106 }); 1107 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 1108 { 1109 struct deps_reg *reg_last = &deps->reg_last[i]; 1110 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 1111 add_dependence_list (insn, reg_last->clobbers, REG_DEP_OUTPUT); 1112 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1113 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1114 }); 1115 } 1116 else 1117 { 1118 EXECUTE_IF_SET_IN_REG_SET (reg_pending_uses, 0, i, 1119 { 1120 struct deps_reg *reg_last = &deps->reg_last[i]; 1121 add_dependence_list (insn, reg_last->sets, 0); 1122 add_dependence_list (insn, reg_last->clobbers, 0); 1123 reg_last->uses_length++; 1124 reg_last->uses = alloc_INSN_LIST (insn, reg_last->uses); 1125 }); 1126 EXECUTE_IF_SET_IN_REG_SET (reg_pending_clobbers, 0, i, 1127 { 1128 struct deps_reg *reg_last = &deps->reg_last[i]; 1129 if (reg_last->uses_length > MAX_PENDING_LIST_LENGTH 1130 || reg_last->clobbers_length > MAX_PENDING_LIST_LENGTH) 1131 { 1132 add_dependence_list_and_free (insn, ®_last->sets, 1133 REG_DEP_OUTPUT); 1134 add_dependence_list_and_free (insn, ®_last->uses, 1135 REG_DEP_ANTI); 1136 add_dependence_list_and_free (insn, ®_last->clobbers, 1137 REG_DEP_OUTPUT); 1138 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1139 reg_last->clobbers_length = 0; 1140 reg_last->uses_length = 0; 1141 } 1142 else 1143 { 1144 add_dependence_list (insn, reg_last->sets, REG_DEP_OUTPUT); 1145 add_dependence_list (insn, reg_last->uses, REG_DEP_ANTI); 1146 } 1147 reg_last->clobbers_length++; 1148 reg_last->clobbers = alloc_INSN_LIST (insn, reg_last->clobbers); 1149 }); 1150 EXECUTE_IF_SET_IN_REG_SET (reg_pending_sets, 0, i, 1151 { 1152 struct deps_reg *reg_last = &deps->reg_last[i]; 1153 add_dependence_list_and_free (insn, ®_last->sets, 1154 REG_DEP_OUTPUT); 1155 add_dependence_list_and_free (insn, ®_last->clobbers, 1156 REG_DEP_OUTPUT); 1157 add_dependence_list_and_free (insn, ®_last->uses, 1158 REG_DEP_ANTI); 1159 reg_last->sets = alloc_INSN_LIST (insn, reg_last->sets); 1160 reg_last->uses_length = 0; 1161 reg_last->clobbers_length = 0; 1162 }); 1163 } 1164 1165 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_uses); 1166 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_clobbers); 1167 IOR_REG_SET (&deps->reg_last_in_use, reg_pending_sets); 1168 } 1169 CLEAR_REG_SET (reg_pending_uses); 1170 CLEAR_REG_SET (reg_pending_clobbers); 1171 CLEAR_REG_SET (reg_pending_sets); 1172 1173 /* If we are currently in a libcall scheduling group, then mark the 1174 current insn as being in a scheduling group and that it can not 1175 be moved into a different basic block. */ 1176 1177 if (deps->libcall_block_tail_insn) 1178 { 1179 set_sched_group_p (insn); 1180 CANT_MOVE (insn) = 1; 1181 } 1182 1183 /* If a post-call group is still open, see if it should remain so. 1184 This insn must be a simple move of a hard reg to a pseudo or 1185 vice-versa. 1186 1187 We must avoid moving these insns for correctness on 1188 SMALL_REGISTER_CLASS machines, and for special registers like 1189 PIC_OFFSET_TABLE_REGNUM. For simplicity, extend this to all 1190 hard regs for all targets. */ 1191 1192 if (deps->in_post_call_group_p) 1193 { 1194 rtx tmp, set = single_set (insn); 1195 int src_regno, dest_regno; 1196 1197 if (set == NULL) 1198 goto end_call_group; 1199 1200 tmp = SET_DEST (set); 1201 if (GET_CODE (tmp) == SUBREG) 1202 tmp = SUBREG_REG (tmp); 1203 if (GET_CODE (tmp) == REG) 1204 dest_regno = REGNO (tmp); 1205 else 1206 goto end_call_group; 1207 1208 tmp = SET_SRC (set); 1209 if (GET_CODE (tmp) == SUBREG) 1210 tmp = SUBREG_REG (tmp); 1211 if (GET_CODE (tmp) == REG) 1212 src_regno = REGNO (tmp); 1213 else 1214 goto end_call_group; 1215 1216 if (src_regno < FIRST_PSEUDO_REGISTER 1217 || dest_regno < FIRST_PSEUDO_REGISTER) 1218 { 1219 set_sched_group_p (insn); 1220 CANT_MOVE (insn) = 1; 1221 } 1222 else 1223 { 1224 end_call_group: 1225 deps->in_post_call_group_p = false; 1226 } 1227 } 1228} 1229 1230/* Analyze every insn between HEAD and TAIL inclusive, creating LOG_LINKS 1231 for every dependency. */ 1232 1233void 1234sched_analyze (deps, head, tail) 1235 struct deps *deps; 1236 rtx head, tail; 1237{ 1238 rtx insn; 1239 rtx loop_notes = 0; 1240 1241 if (current_sched_info->use_cselib) 1242 cselib_init (); 1243 1244 for (insn = head;; insn = NEXT_INSN (insn)) 1245 { 1246 rtx link, end_seq, r0, set, note; 1247 1248 if (GET_CODE (insn) == INSN || GET_CODE (insn) == JUMP_INSN) 1249 { 1250 /* Clear out the stale LOG_LINKS from flow. */ 1251 free_INSN_LIST_list (&LOG_LINKS (insn)); 1252 1253 /* Clear out stale SCHED_GROUP_P. */ 1254 SCHED_GROUP_P (insn) = 0; 1255 1256 /* Make each JUMP_INSN a scheduling barrier for memory 1257 references. */ 1258 if (GET_CODE (insn) == JUMP_INSN) 1259 { 1260 /* Keep the list a reasonable size. */ 1261 if (deps->pending_flush_length++ > MAX_PENDING_LIST_LENGTH) 1262 flush_pending_lists (deps, insn, true, true); 1263 else 1264 deps->last_pending_memory_flush 1265 = alloc_INSN_LIST (insn, deps->last_pending_memory_flush); 1266 } 1267 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 1268 loop_notes = 0; 1269 } 1270 else if (GET_CODE (insn) == CALL_INSN) 1271 { 1272 int i; 1273 1274 CANT_MOVE (insn) = 1; 1275 1276 /* Clear out the stale LOG_LINKS from flow. */ 1277 free_INSN_LIST_list (&LOG_LINKS (insn)); 1278 1279 if (find_reg_note (insn, REG_SETJMP, NULL)) 1280 { 1281 /* This is setjmp. Assume that all registers, not just 1282 hard registers, may be clobbered by this call. */ 1283 reg_pending_barrier = true; 1284 } 1285 else 1286 { 1287 for (i = 0; i < FIRST_PSEUDO_REGISTER; i++) 1288 /* A call may read and modify global register variables. */ 1289 if (global_regs[i]) 1290 { 1291 SET_REGNO_REG_SET (reg_pending_sets, i); 1292 SET_REGNO_REG_SET (reg_pending_uses, i); 1293 } 1294 /* Other call-clobbered hard regs may be clobbered. */ 1295 else if (TEST_HARD_REG_BIT (regs_invalidated_by_call, i)) 1296 SET_REGNO_REG_SET (reg_pending_clobbers, i); 1297 /* We don't know what set of fixed registers might be used 1298 by the function, but it is certain that the stack pointer 1299 is among them, but be conservative. */ 1300 else if (fixed_regs[i]) 1301 SET_REGNO_REG_SET (reg_pending_uses, i); 1302 /* The frame pointer is normally not used by the function 1303 itself, but by the debugger. */ 1304 /* ??? MIPS o32 is an exception. It uses the frame pointer 1305 in the macro expansion of jal but does not represent this 1306 fact in the call_insn rtl. */ 1307 else if (i == FRAME_POINTER_REGNUM 1308 || (i == HARD_FRAME_POINTER_REGNUM 1309 && (! reload_completed || frame_pointer_needed))) 1310 SET_REGNO_REG_SET (reg_pending_uses, i); 1311 } 1312 1313 /* For each insn which shouldn't cross a call, add a dependence 1314 between that insn and this call insn. */ 1315 add_dependence_list_and_free (insn, &deps->sched_before_next_call, 1316 REG_DEP_ANTI); 1317 1318 sched_analyze_insn (deps, PATTERN (insn), insn, loop_notes); 1319 loop_notes = 0; 1320 1321 /* In the absence of interprocedural alias analysis, we must flush 1322 all pending reads and writes, and start new dependencies starting 1323 from here. But only flush writes for constant calls (which may 1324 be passed a pointer to something we haven't written yet). */ 1325 flush_pending_lists (deps, insn, true, !CONST_OR_PURE_CALL_P (insn)); 1326 1327 /* Remember the last function call for limiting lifetimes. */ 1328 free_INSN_LIST_list (&deps->last_function_call); 1329 deps->last_function_call = alloc_INSN_LIST (insn, NULL_RTX); 1330 1331 /* Before reload, begin a post-call group, so as to keep the 1332 lifetimes of hard registers correct. */ 1333 if (! reload_completed) 1334 deps->in_post_call_group_p = true; 1335 } 1336 1337 /* See comments on reemit_notes as to why we do this. 1338 ??? Actually, the reemit_notes just say what is done, not why. */ 1339 1340 else if (GET_CODE (insn) == NOTE 1341 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_BEG 1342 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_RANGE_END)) 1343 { 1344 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, NOTE_RANGE_INFO (insn), 1345 loop_notes); 1346 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1347 GEN_INT (NOTE_LINE_NUMBER (insn)), 1348 loop_notes); 1349 } 1350 else if (GET_CODE (insn) == NOTE 1351 && (NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_BEG 1352 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_LOOP_END 1353 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 1354 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END)) 1355 { 1356 rtx rtx_region; 1357 1358 if (NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_BEG 1359 || NOTE_LINE_NUMBER (insn) == NOTE_INSN_EH_REGION_END) 1360 rtx_region = GEN_INT (NOTE_EH_HANDLER (insn)); 1361 else 1362 rtx_region = GEN_INT (0); 1363 1364 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1365 rtx_region, 1366 loop_notes); 1367 loop_notes = alloc_EXPR_LIST (REG_SAVE_NOTE, 1368 GEN_INT (NOTE_LINE_NUMBER (insn)), 1369 loop_notes); 1370 CONST_OR_PURE_CALL_P (loop_notes) = CONST_OR_PURE_CALL_P (insn); 1371 } 1372 1373 if (current_sched_info->use_cselib) 1374 cselib_process_insn (insn); 1375 1376 /* Now that we have completed handling INSN, check and see if it is 1377 a CLOBBER beginning a libcall block. If it is, record the 1378 end of the libcall sequence. 1379 1380 We want to schedule libcall blocks as a unit before reload. While 1381 this restricts scheduling, it preserves the meaning of a libcall 1382 block. 1383 1384 As a side effect, we may get better code due to decreased register 1385 pressure as well as less chance of a foreign insn appearing in 1386 a libcall block. */ 1387 if (!reload_completed 1388 /* Note we may have nested libcall sequences. We only care about 1389 the outermost libcall sequence. */ 1390 && deps->libcall_block_tail_insn == 0 1391 /* The sequence must start with a clobber of a register. */ 1392 && GET_CODE (insn) == INSN 1393 && GET_CODE (PATTERN (insn)) == CLOBBER 1394 && (r0 = XEXP (PATTERN (insn), 0), GET_CODE (r0) == REG) 1395 && GET_CODE (XEXP (PATTERN (insn), 0)) == REG 1396 /* The CLOBBER must also have a REG_LIBCALL note attached. */ 1397 && (link = find_reg_note (insn, REG_LIBCALL, NULL_RTX)) != 0 1398 && (end_seq = XEXP (link, 0)) != 0 1399 /* The insn referenced by the REG_LIBCALL note must be a 1400 simple nop copy with the same destination as the register 1401 mentioned in the clobber. */ 1402 && (set = single_set (end_seq)) != 0 1403 && SET_DEST (set) == r0 && SET_SRC (set) == r0 1404 /* And finally the insn referenced by the REG_LIBCALL must 1405 also contain a REG_EQUAL note and a REG_RETVAL note. */ 1406 && find_reg_note (end_seq, REG_EQUAL, NULL_RTX) != 0 1407 && find_reg_note (end_seq, REG_RETVAL, NULL_RTX) != 0) 1408 deps->libcall_block_tail_insn = XEXP (link, 0); 1409 1410 /* If we have reached the end of a libcall block, then close the 1411 block. */ 1412 if (deps->libcall_block_tail_insn == insn) 1413 deps->libcall_block_tail_insn = 0; 1414 1415 if (insn == tail) 1416 { 1417 if (current_sched_info->use_cselib) 1418 cselib_finish (); 1419 return; 1420 } 1421 } 1422 abort (); 1423} 1424 1425/* Examine insns in the range [ HEAD, TAIL ] and Use the backward 1426 dependences from LOG_LINKS to build forward dependences in 1427 INSN_DEPEND. */ 1428 1429void 1430compute_forward_dependences (head, tail) 1431 rtx head, tail; 1432{ 1433 rtx insn, link; 1434 rtx next_tail; 1435 enum reg_note dep_type; 1436 1437 next_tail = NEXT_INSN (tail); 1438 for (insn = head; insn != next_tail; insn = NEXT_INSN (insn)) 1439 { 1440 if (! INSN_P (insn)) 1441 continue; 1442 1443 insn = group_leader (insn); 1444 1445 for (link = LOG_LINKS (insn); link; link = XEXP (link, 1)) 1446 { 1447 rtx x = group_leader (XEXP (link, 0)); 1448 rtx new_link; 1449 1450 if (x != XEXP (link, 0)) 1451 continue; 1452 1453#ifdef ENABLE_CHECKING 1454 /* If add_dependence is working properly there should never 1455 be notes, deleted insns or duplicates in the backward 1456 links. Thus we need not check for them here. 1457 1458 However, if we have enabled checking we might as well go 1459 ahead and verify that add_dependence worked properly. */ 1460 if (GET_CODE (x) == NOTE 1461 || INSN_DELETED_P (x) 1462 || (forward_dependency_cache != NULL 1463 && TEST_BIT (forward_dependency_cache[INSN_LUID (x)], 1464 INSN_LUID (insn))) 1465 || (forward_dependency_cache == NULL 1466 && find_insn_list (insn, INSN_DEPEND (x)))) 1467 abort (); 1468 if (forward_dependency_cache != NULL) 1469 SET_BIT (forward_dependency_cache[INSN_LUID (x)], 1470 INSN_LUID (insn)); 1471#endif 1472 1473 new_link = alloc_INSN_LIST (insn, INSN_DEPEND (x)); 1474 1475 dep_type = REG_NOTE_KIND (link); 1476 PUT_REG_NOTE_KIND (new_link, dep_type); 1477 1478 INSN_DEPEND (x) = new_link; 1479 INSN_DEP_COUNT (insn) += 1; 1480 } 1481 } 1482} 1483 1484/* Initialize variables for region data dependence analysis. 1485 n_bbs is the number of region blocks. */ 1486 1487void 1488init_deps (deps) 1489 struct deps *deps; 1490{ 1491 int max_reg = (reload_completed ? FIRST_PSEUDO_REGISTER : max_reg_num ()); 1492 1493 deps->max_reg = max_reg; 1494 deps->reg_last = (struct deps_reg *) 1495 xcalloc (max_reg, sizeof (struct deps_reg)); 1496 INIT_REG_SET (&deps->reg_last_in_use); 1497 1498 deps->pending_read_insns = 0; 1499 deps->pending_read_mems = 0; 1500 deps->pending_write_insns = 0; 1501 deps->pending_write_mems = 0; 1502 deps->pending_lists_length = 0; 1503 deps->pending_flush_length = 0; 1504 deps->last_pending_memory_flush = 0; 1505 deps->last_function_call = 0; 1506 deps->sched_before_next_call = 0; 1507 deps->in_post_call_group_p = false; 1508 deps->libcall_block_tail_insn = 0; 1509} 1510 1511/* Free insn lists found in DEPS. */ 1512 1513void 1514free_deps (deps) 1515 struct deps *deps; 1516{ 1517 int i; 1518 1519 free_INSN_LIST_list (&deps->pending_read_insns); 1520 free_EXPR_LIST_list (&deps->pending_read_mems); 1521 free_INSN_LIST_list (&deps->pending_write_insns); 1522 free_EXPR_LIST_list (&deps->pending_write_mems); 1523 free_INSN_LIST_list (&deps->last_pending_memory_flush); 1524 1525 /* Without the EXECUTE_IF_SET, this loop is executed max_reg * nr_regions 1526 times. For a test case with 42000 regs and 8000 small basic blocks, 1527 this loop accounted for nearly 60% (84 sec) of the total -O2 runtime. */ 1528 EXECUTE_IF_SET_IN_REG_SET (&deps->reg_last_in_use, 0, i, 1529 { 1530 struct deps_reg *reg_last = &deps->reg_last[i]; 1531 free_INSN_LIST_list (®_last->uses); 1532 free_INSN_LIST_list (®_last->sets); 1533 free_INSN_LIST_list (®_last->clobbers); 1534 }); 1535 CLEAR_REG_SET (&deps->reg_last_in_use); 1536 1537 free (deps->reg_last); 1538} 1539 1540/* If it is profitable to use them, initialize caches for tracking 1541 dependency informatino. LUID is the number of insns to be scheduled, 1542 it is used in the estimate of profitability. */ 1543 1544void 1545init_dependency_caches (luid) 1546 int luid; 1547{ 1548 /* ?!? We could save some memory by computing a per-region luid mapping 1549 which could reduce both the number of vectors in the cache and the size 1550 of each vector. Instead we just avoid the cache entirely unless the 1551 average number of instructions in a basic block is very high. See 1552 the comment before the declaration of true_dependency_cache for 1553 what we consider "very high". */ 1554 if (luid / n_basic_blocks > 100 * 5) 1555 { 1556 true_dependency_cache = sbitmap_vector_alloc (luid, luid); 1557 sbitmap_vector_zero (true_dependency_cache, luid); 1558 anti_dependency_cache = sbitmap_vector_alloc (luid, luid); 1559 sbitmap_vector_zero (anti_dependency_cache, luid); 1560 output_dependency_cache = sbitmap_vector_alloc (luid, luid); 1561 sbitmap_vector_zero (output_dependency_cache, luid); 1562#ifdef ENABLE_CHECKING 1563 forward_dependency_cache = sbitmap_vector_alloc (luid, luid); 1564 sbitmap_vector_zero (forward_dependency_cache, luid); 1565#endif 1566 } 1567} 1568 1569/* Free the caches allocated in init_dependency_caches. */ 1570 1571void 1572free_dependency_caches () 1573{ 1574 if (true_dependency_cache) 1575 { 1576 sbitmap_vector_free (true_dependency_cache); 1577 true_dependency_cache = NULL; 1578 sbitmap_vector_free (anti_dependency_cache); 1579 anti_dependency_cache = NULL; 1580 sbitmap_vector_free (output_dependency_cache); 1581 output_dependency_cache = NULL; 1582#ifdef ENABLE_CHECKING 1583 sbitmap_vector_free (forward_dependency_cache); 1584 forward_dependency_cache = NULL; 1585#endif 1586 } 1587} 1588 1589/* Initialize some global variables needed by the dependency analysis 1590 code. */ 1591 1592void 1593init_deps_global () 1594{ 1595 reg_pending_sets = INITIALIZE_REG_SET (reg_pending_sets_head); 1596 reg_pending_clobbers = INITIALIZE_REG_SET (reg_pending_clobbers_head); 1597 reg_pending_uses = INITIALIZE_REG_SET (reg_pending_uses_head); 1598 reg_pending_barrier = false; 1599} 1600 1601/* Free everything used by the dependency analysis code. */ 1602 1603void 1604finish_deps_global () 1605{ 1606 FREE_REG_SET (reg_pending_sets); 1607 FREE_REG_SET (reg_pending_clobbers); 1608 FREE_REG_SET (reg_pending_uses); 1609}
|