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