1/* Instruction scheduling pass. This file contains definitions used 2 internally in the scheduler. 3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000, 4 2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010 5 Free Software Foundation, Inc. 6 7This file is part of GCC. 8 9GCC is free software; you can redistribute it and/or modify it under 10the terms of the GNU General Public License as published by the Free 11Software Foundation; either version 3, or (at your option) any later 12version. 13 14GCC is distributed in the hope that it will be useful, but WITHOUT ANY 15WARRANTY; without even the implied warranty of MERCHANTABILITY or 16FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 17for more details. 18 19You should have received a copy of the GNU General Public License 20along with GCC; see the file COPYING3. If not see 21<http://www.gnu.org/licenses/>. */ 22 23#ifndef GCC_SCHED_INT_H 24#define GCC_SCHED_INT_H 25 26#ifdef INSN_SCHEDULING 27 28/* For state_t. */ 29#include "insn-attr.h" 30#include "df.h" 31#include "basic-block.h" 32 33/* For VEC (int, heap). */ 34#include "vecprim.h" 35 36/* Identificator of a scheduler pass. */ 37enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS, 38 SCHED_SMS_PASS, SCHED_SEL_PASS }; 39 40typedef VEC (basic_block, heap) *bb_vec_t; 41typedef VEC (rtx, heap) *insn_vec_t; 42typedef VEC(rtx, heap) *rtx_vec_t; 43 44struct sched_scan_info_def 45{ 46 /* This hook notifies scheduler frontend to extend its internal per basic 47 block data structures. This hook should be called once before a series of 48 calls to bb_init (). */ 49 void (*extend_bb) (void); 50 51 /* This hook makes scheduler frontend to initialize its internal data 52 structures for the passed basic block. */ 53 void (*init_bb) (basic_block); 54 55 /* This hook notifies scheduler frontend to extend its internal per insn data 56 structures. This hook should be called once before a series of calls to 57 insn_init (). */ 58 void (*extend_insn) (void); 59 60 /* This hook makes scheduler frontend to initialize its internal data 61 structures for the passed insn. */ 62 void (*init_insn) (rtx); 63}; 64 65extern const struct sched_scan_info_def *sched_scan_info; 66 67extern void sched_scan (const struct sched_scan_info_def *, 68 bb_vec_t, basic_block, insn_vec_t, rtx); 69 70extern void sched_init_bbs (void); 71 72extern void sched_init_luids (bb_vec_t, basic_block, insn_vec_t, rtx); 73extern void sched_finish_luids (void); 74 75extern void sched_extend_target (void); 76 77extern void haifa_init_h_i_d (bb_vec_t, basic_block, insn_vec_t, rtx); 78extern void haifa_finish_h_i_d (void); 79 80/* Hooks that are common to all the schedulers. */ 81struct common_sched_info_def 82{ 83 /* Called after blocks were rearranged due to movement of jump instruction. 84 The first parameter - index of basic block, in which jump currently is. 85 The second parameter - index of basic block, in which jump used 86 to be. 87 The third parameter - index of basic block, that follows the second 88 parameter. */ 89 void (*fix_recovery_cfg) (int, int, int); 90 91 /* Called to notify frontend, that new basic block is being added. 92 The first parameter - new basic block. 93 The second parameter - block, after which new basic block is being added, 94 or EXIT_BLOCK_PTR, if recovery block is being added, 95 or NULL, if standalone block is being added. */ 96 void (*add_block) (basic_block, basic_block); 97 98 /* Estimate number of insns in the basic block. */ 99 int (*estimate_number_of_insns) (basic_block); 100 101 /* Given a non-insn (!INSN_P (x)) return 102 -1 - if this rtx don't need a luid. 103 0 - if it should have the same luid as the previous insn. 104 1 - if it needs a separate luid. */ 105 int (*luid_for_non_insn) (rtx); 106 107 /* Scheduler pass identifier. It is preferably used in assertions. */ 108 enum sched_pass_id_t sched_pass_id; 109}; 110 111extern struct common_sched_info_def *common_sched_info; 112 113extern const struct common_sched_info_def haifa_common_sched_info; 114 115/* Return true if selective scheduling pass is working. */ 116static inline bool 117sel_sched_p (void) 118{ 119 return common_sched_info->sched_pass_id == SCHED_SEL_PASS; 120} 121 122/* Returns maximum priority that an insn was assigned to. */ 123extern int get_rgn_sched_max_insns_priority (void); 124 125/* Increases effective priority for INSN by AMOUNT. */ 126extern void sel_add_to_insn_priority (rtx, int); 127 128/* True if during selective scheduling we need to emulate some of haifa 129 scheduler behaviour. */ 130extern int sched_emulate_haifa_p; 131 132/* Mapping from INSN_UID to INSN_LUID. In the end all other per insn data 133 structures should be indexed by luid. */ 134extern VEC (int, heap) *sched_luids; 135#define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN))) 136#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID)) 137 138#define SET_INSN_LUID(INSN, LUID) \ 139(VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID))) 140 141/* The highest INSN_LUID. */ 142extern int sched_max_luid; 143 144extern int insn_luid (rtx); 145 146/* This list holds ripped off notes from the current block. These notes will 147 be attached to the beginning of the block when its scheduling is 148 finished. */ 149extern rtx note_list; 150 151extern void remove_notes (rtx, rtx); 152extern rtx restore_other_notes (rtx, basic_block); 153extern void sched_insns_init (rtx); 154extern void sched_insns_finish (void); 155 156extern void *xrecalloc (void *, size_t, size_t, size_t); 157extern rtx bb_note (basic_block); 158 159extern void reemit_notes (rtx); 160 161/* Functions in haifa-sched.c. */ 162extern int haifa_classify_insn (const_rtx); 163 164/* Functions in sel-sched-ir.c. */ 165extern void sel_find_rgns (void); 166extern void sel_mark_hard_insn (rtx); 167 168extern size_t dfa_state_size; 169 170extern void advance_state (state_t); 171 172extern void setup_sched_dump (void); 173extern void sched_init (void); 174extern void sched_finish (void); 175 176extern bool sel_insn_is_speculation_check (rtx); 177 178/* Describe the ready list of the scheduler. 179 VEC holds space enough for all insns in the current region. VECLEN 180 says how many exactly. 181 FIRST is the index of the element with the highest priority; i.e. the 182 last one in the ready list, since elements are ordered by ascending 183 priority. 184 N_READY determines how many insns are on the ready list. 185 N_DEBUG determines how many debug insns are on the ready list. */ 186struct ready_list 187{ 188 rtx *vec; 189 int veclen; 190 int first; 191 int n_ready; 192 int n_debug; 193}; 194 195extern char *ready_try; 196extern struct ready_list ready; 197 198extern int max_issue (struct ready_list *, int, state_t, int *); 199 200extern void ebb_compute_jump_reg_dependencies (rtx, regset, regset, regset); 201 202extern edge find_fallthru_edge (basic_block); 203 204extern void (* sched_init_only_bb) (basic_block, basic_block); 205extern basic_block (* sched_split_block) (basic_block, rtx); 206extern basic_block sched_split_block_1 (basic_block, rtx); 207extern basic_block (* sched_create_empty_bb) (basic_block); 208extern basic_block sched_create_empty_bb_1 (basic_block); 209 210extern basic_block sched_create_recovery_block (basic_block *); 211extern void sched_create_recovery_edges (basic_block, basic_block, 212 basic_block); 213 214/* Pointer to data describing the current DFA state. */ 215extern state_t curr_state; 216 217/* Type to represent status of a dependence. */ 218typedef int ds_t; 219 220/* Type to represent weakness of speculative dependence. */ 221typedef int dw_t; 222 223extern enum reg_note ds_to_dk (ds_t); 224extern ds_t dk_to_ds (enum reg_note); 225 226/* Information about the dependency. */ 227struct _dep 228{ 229 /* Producer. */ 230 rtx pro; 231 232 /* Consumer. */ 233 rtx con; 234 235 /* Dependency major type. This field is superseded by STATUS below. 236 Though, it is still in place because some targets use it. */ 237 enum reg_note type; 238 239 /* Dependency status. This field holds all dependency types and additional 240 information for speculative dependencies. */ 241 ds_t status; 242}; 243 244typedef struct _dep dep_def; 245typedef dep_def *dep_t; 246 247#define DEP_PRO(D) ((D)->pro) 248#define DEP_CON(D) ((D)->con) 249#define DEP_TYPE(D) ((D)->type) 250#define DEP_STATUS(D) ((D)->status) 251 252/* Functions to work with dep. */ 253 254extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t); 255extern void init_dep (dep_t, rtx, rtx, enum reg_note); 256 257extern void sd_debug_dep (dep_t); 258 259/* Definition of this struct resides below. */ 260struct _dep_node; 261typedef struct _dep_node *dep_node_t; 262 263/* A link in the dependency list. This is essentially an equivalent of a 264 single {INSN, DEPS}_LIST rtx. */ 265struct _dep_link 266{ 267 /* Dep node with all the data. */ 268 dep_node_t node; 269 270 /* Next link in the list. For the last one it is NULL. */ 271 struct _dep_link *next; 272 273 /* Pointer to the next field of the previous link in the list. 274 For the first link this points to the deps_list->first. 275 276 With help of this field it is easy to remove and insert links to the 277 list. */ 278 struct _dep_link **prev_nextp; 279}; 280typedef struct _dep_link *dep_link_t; 281 282#define DEP_LINK_NODE(N) ((N)->node) 283#define DEP_LINK_NEXT(N) ((N)->next) 284#define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp) 285 286/* Macros to work dep_link. For most usecases only part of the dependency 287 information is need. These macros conveniently provide that piece of 288 information. */ 289 290#define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N))) 291#define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N))) 292#define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N))) 293#define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N))) 294#define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N))) 295 296/* A list of dep_links. */ 297struct _deps_list 298{ 299 /* First element. */ 300 dep_link_t first; 301 302 /* Total number of elements in the list. */ 303 int n_links; 304}; 305typedef struct _deps_list *deps_list_t; 306 307#define DEPS_LIST_FIRST(L) ((L)->first) 308#define DEPS_LIST_N_LINKS(L) ((L)->n_links) 309 310/* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has 311 additional dependents con0 and con2, and con1 is dependent on additional 312 insns pro0 and pro1: 313 314 .con0 pro0 315 . ^ | 316 . | | 317 . | | 318 . X A 319 . | | 320 . | | 321 . | V 322 .pro1--Y-->con1 323 . | ^ 324 . | | 325 . | | 326 . Z B 327 . | | 328 . | | 329 . V | 330 .con2 pro2 331 332 This is represented using a "dep_node" for each dependence arc, which are 333 connected as follows (diagram is centered around Y which is fully shown; 334 other dep_nodes shown partially): 335 336 . +------------+ +--------------+ +------------+ 337 . : dep_node X : | dep_node Y | : dep_node Z : 338 . : : | | : : 339 . : : | | : : 340 . : forw : | forw | : forw : 341 . : +--------+ : | +--------+ | : +--------+ : 342 forw_deps : |dep_link| : | |dep_link| | : |dep_link| : 343 +-----+ : | +----+ | : | | +----+ | | : | +----+ | : 344 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL 345 +-----+ : | +----+ | : | | +----+ | | : | +----+ | : 346 . ^ ^ : | ^ | : | | ^ | | : | | : 347 . | | : | | | : | | | | | : | | : 348 . | +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | : 349 . | : | | | : | | | | | : | | | : 350 . | : | +----+ | : | | +----+ | | : | +----+ | : 351 . | : | |prev| | : | | |prev| | | : | |prev| | : 352 . | : | |next| | : | | |next| | | : | |next| | : 353 . | : | +----+ | : | | +----+ | | : | +----+ | : 354 . | : | | :<-+ | | | |<-+ : | | :<-+ 355 . | : | +----+ | : | | | +----+ | | | : | +----+ | : | 356 . | : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+ 357 . | : | +----+ | : | | +----+ | | : | +----+ | : 358 . | : | | : | | | | : | | : 359 . | : +--------+ : | +--------+ | : +--------+ : 360 . | : : | | : : 361 . | : SAME pro1 : | +--------+ | : SAME pro1 : 362 . | : DIFF con0 : | |dep | | : DIFF con2 : 363 . | : : | | | | : : 364 . | | | +----+ | | 365 .RTX<------------------------+--+-|pro1| | | 366 .pro1 | | +----+ | | 367 . | | | | 368 . | | +----+ | | 369 .RTX<------------------------+--+-|con1| | | 370 .con1 | | +----+ | | 371 . | | | | | 372 . | | | +----+ | | 373 . | | | |kind| | | 374 . | | | +----+ | | 375 . | : : | | |stat| | | : : 376 . | : DIFF pro0 : | | +----+ | | : DIFF pro2 : 377 . | : SAME con1 : | | | | : SAME con1 : 378 . | : : | +--------+ | : : 379 . | : : | | : : 380 . | : back : | back | : back : 381 . v : +--------+ : | +--------+ | : +--------+ : 382 back_deps : |dep_link| : | |dep_link| | : |dep_link| : 383 +-----+ : | +----+ | : | | +----+ | | : | +----+ | : 384 |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL 385 +-----+ : | +----+ | : | | +----+ | | : | +----+ | : 386 . ^ : | ^ | : | | ^ | | : | | : 387 . | : | | | : | | | | | : | | : 388 . +--<----+--+ +--+---<--+--+--+ +--+--+--<---+--+ | : 389 . : | | | : | | | | | : | | | : 390 . : | +----+ | : | | +----+ | | : | +----+ | : 391 . : | |prev| | : | | |prev| | | : | |prev| | : 392 . : | |next| | : | | |next| | | : | |next| | : 393 . : | +----+ | : | | +----+ | | : | +----+ | : 394 . : | | :<-+ | | | |<-+ : | | :<-+ 395 . : | +----+ | : | | | +----+ | | | : | +----+ | : | 396 . : | |node|-+----+ | | |node|-+--+--+ : | |node|-+----+ 397 . : | +----+ | : | | +----+ | | : | +----+ | : 398 . : | | : | | | | : | | : 399 . : +--------+ : | +--------+ | : +--------+ : 400 . : : | | : : 401 . : dep_node A : | dep_node Y | : dep_node B : 402 . +------------+ +--------------+ +------------+ 403*/ 404 405struct _dep_node 406{ 407 /* Backward link. */ 408 struct _dep_link back; 409 410 /* The dep. */ 411 struct _dep dep; 412 413 /* Forward link. */ 414 struct _dep_link forw; 415}; 416 417#define DEP_NODE_BACK(N) (&(N)->back) 418#define DEP_NODE_DEP(N) (&(N)->dep) 419#define DEP_NODE_FORW(N) (&(N)->forw) 420 421/* The following enumeration values tell us what dependencies we 422 should use to implement the barrier. We use true-dependencies for 423 TRUE_BARRIER and anti-dependencies for MOVE_BARRIER. */ 424enum reg_pending_barrier_mode 425{ 426 NOT_A_BARRIER = 0, 427 MOVE_BARRIER, 428 TRUE_BARRIER 429}; 430 431/* Whether a register movement is associated with a call. */ 432enum post_call_group 433{ 434 not_post_call, 435 post_call, 436 post_call_initial 437}; 438 439/* Insns which affect pseudo-registers. */ 440struct deps_reg 441{ 442 rtx uses; 443 rtx sets; 444 rtx implicit_sets; 445 rtx clobbers; 446 int uses_length; 447 int clobbers_length; 448}; 449 450/* Describe state of dependencies used during sched_analyze phase. */ 451struct deps_desc 452{ 453 /* The *_insns and *_mems are paired lists. Each pending memory operation 454 will have a pointer to the MEM rtx on one list and a pointer to the 455 containing insn on the other list in the same place in the list. */ 456 457 /* We can't use add_dependence like the old code did, because a single insn 458 may have multiple memory accesses, and hence needs to be on the list 459 once for each memory access. Add_dependence won't let you add an insn 460 to a list more than once. */ 461 462 /* An INSN_LIST containing all insns with pending read operations. */ 463 rtx pending_read_insns; 464 465 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 466 rtx pending_read_mems; 467 468 /* An INSN_LIST containing all insns with pending write operations. */ 469 rtx pending_write_insns; 470 471 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 472 rtx pending_write_mems; 473 474 /* We must prevent the above lists from ever growing too large since 475 the number of dependencies produced is at least O(N*N), 476 and execution time is at least O(4*N*N), as a function of the 477 length of these pending lists. */ 478 479 /* Indicates the length of the pending_read list. */ 480 int pending_read_list_length; 481 482 /* Indicates the length of the pending_write list. */ 483 int pending_write_list_length; 484 485 /* Length of the pending memory flush list. Large functions with no 486 calls may build up extremely large lists. */ 487 int pending_flush_length; 488 489 /* The last insn upon which all memory references must depend. 490 This is an insn which flushed the pending lists, creating a dependency 491 between it and all previously pending memory references. This creates 492 a barrier (or a checkpoint) which no memory reference is allowed to cross. 493 494 This includes all non constant CALL_INSNs. When we do interprocedural 495 alias analysis, this restriction can be relaxed. 496 This may also be an INSN that writes memory if the pending lists grow 497 too large. */ 498 rtx last_pending_memory_flush; 499 500 /* A list of the last function calls we have seen. We use a list to 501 represent last function calls from multiple predecessor blocks. 502 Used to prevent register lifetimes from expanding unnecessarily. */ 503 rtx last_function_call; 504 505 /* A list of the last function calls that may not return normally 506 we have seen. We use a list to represent last function calls from 507 multiple predecessor blocks. Used to prevent moving trapping insns 508 across such calls. */ 509 rtx last_function_call_may_noreturn; 510 511 /* A list of insns which use a pseudo register that does not already 512 cross a call. We create dependencies between each of those insn 513 and the next call insn, to ensure that they won't cross a call after 514 scheduling is done. */ 515 rtx sched_before_next_call; 516 517 /* Used to keep post-call pseudo/hard reg movements together with 518 the call. */ 519 enum post_call_group in_post_call_group_p; 520 521 /* The last debug insn we've seen. */ 522 rtx last_debug_insn; 523 524 /* The maximum register number for the following arrays. Before reload 525 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 526 int max_reg; 527 528 /* Element N is the next insn that sets (hard or pseudo) register 529 N within the current basic block; or zero, if there is no 530 such insn. Needed for new registers which may be introduced 531 by splitting insns. */ 532 struct deps_reg *reg_last; 533 534 /* Element N is set for each register that has any nonzero element 535 in reg_last[N].{uses,sets,clobbers}. */ 536 regset_head reg_last_in_use; 537 538 /* Element N is set for each register that is conditionally set. */ 539 regset_head reg_conditional_sets; 540 541 /* Shows the last value of reg_pending_barrier associated with the insn. */ 542 enum reg_pending_barrier_mode last_reg_pending_barrier; 543 544 /* True when this context should be treated as a readonly by 545 the analysis. */ 546 BOOL_BITFIELD readonly : 1; 547}; 548 549typedef struct deps_desc *deps_t; 550 551/* This structure holds some state of the current scheduling pass, and 552 contains some function pointers that abstract out some of the non-generic 553 functionality from functions such as schedule_block or schedule_insn. 554 There is one global variable, current_sched_info, which points to the 555 sched_info structure currently in use. */ 556struct haifa_sched_info 557{ 558 /* Add all insns that are initially ready to the ready list. Called once 559 before scheduling a set of insns. */ 560 void (*init_ready_list) (void); 561 /* Called after taking an insn from the ready list. Returns nonzero if 562 this insn can be scheduled, nonzero if we should silently discard it. */ 563 int (*can_schedule_ready_p) (rtx); 564 /* Return nonzero if there are more insns that should be scheduled. */ 565 int (*schedule_more_p) (void); 566 /* Called after an insn has all its hard dependencies resolved. 567 Adjusts status of instruction (which is passed through second parameter) 568 to indicate if instruction should be moved to the ready list or the 569 queue, or if it should silently discard it (until next resolved 570 dependence). */ 571 ds_t (*new_ready) (rtx, ds_t); 572 /* Compare priority of two insns. Return a positive number if the second 573 insn is to be preferred for scheduling, and a negative one if the first 574 is to be preferred. Zero if they are equally good. */ 575 int (*rank) (rtx, rtx); 576 /* Return a string that contains the insn uid and optionally anything else 577 necessary to identify this insn in an output. It's valid to use a 578 static buffer for this. The ALIGNED parameter should cause the string 579 to be formatted so that multiple output lines will line up nicely. */ 580 const char *(*print_insn) (const_rtx, int); 581 /* Return nonzero if an insn should be included in priority 582 calculations. */ 583 int (*contributes_to_priority) (rtx, rtx); 584 585 /* Return true if scheduling insn (passed as the parameter) will trigger 586 finish of scheduling current block. */ 587 bool (*insn_finishes_block_p) (rtx); 588 589 /* The boundaries of the set of insns to be scheduled. */ 590 rtx prev_head, next_tail; 591 592 /* Filled in after the schedule is finished; the first and last scheduled 593 insns. */ 594 rtx head, tail; 595 596 /* If nonzero, enables an additional sanity check in schedule_block. */ 597 unsigned int queue_must_finish_empty:1; 598 599 /* Maximum priority that has been assigned to an insn. */ 600 int sched_max_insns_priority; 601 602 /* Hooks to support speculative scheduling. */ 603 604 /* Called to notify frontend that instruction is being added (second 605 parameter == 0) or removed (second parameter == 1). */ 606 void (*add_remove_insn) (rtx, int); 607 608 /* Called to notify frontend that instruction is being scheduled. 609 The first parameter - instruction to scheduled, the second parameter - 610 last scheduled instruction. */ 611 void (*begin_schedule_ready) (rtx, rtx); 612 613 /* If the second parameter is not NULL, return nonnull value, if the 614 basic block should be advanced. 615 If the second parameter is NULL, return the next basic block in EBB. 616 The first parameter is the current basic block in EBB. */ 617 basic_block (*advance_target_bb) (basic_block, rtx); 618 619 /* ??? FIXME: should use straight bitfields inside sched_info instead of 620 this flag field. */ 621 unsigned int flags; 622}; 623 624/* This structure holds description of the properties for speculative 625 scheduling. */ 626struct spec_info_def 627{ 628 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL}, 629 BE_IN_{DATA_CONTROL}. */ 630 int mask; 631 632 /* A dump file for additional information on speculative scheduling. */ 633 FILE *dump; 634 635 /* Minimal cumulative weakness of speculative instruction's 636 dependencies, so that insn will be scheduled. */ 637 dw_t data_weakness_cutoff; 638 639 /* Minimal usefulness of speculative instruction to be considered for 640 scheduling. */ 641 int control_weakness_cutoff; 642 643 /* Flags from the enum SPEC_SCHED_FLAGS. */ 644 int flags; 645}; 646typedef struct spec_info_def *spec_info_t; 647 648extern spec_info_t spec_info; 649 650extern struct haifa_sched_info *current_sched_info; 651 652/* Do register pressure sensitive insn scheduling if the flag is set 653 up. */ 654extern bool sched_pressure_p; 655 656/* Map regno -> its cover class. The map defined only when 657 SCHED_PRESSURE_P is true. */ 658extern enum reg_class *sched_regno_cover_class; 659 660/* Indexed by INSN_UID, the collection of all data associated with 661 a single instruction. */ 662 663struct _haifa_deps_insn_data 664{ 665 /* The number of incoming edges in the forward dependency graph. 666 As scheduling proceeds, counts are decreased. An insn moves to 667 the ready queue when its counter reaches zero. */ 668 int dep_count; 669 670 /* Nonzero if instruction has internal dependence 671 (e.g. add_dependence was invoked with (insn == elem)). */ 672 unsigned int has_internal_dep; 673 674 /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into 675 h_i_d because when h_i_d extends, addresses of the deps_list->first 676 change without updating deps_list->first->next->prev_nextp. Thus 677 BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS 678 list is allocated on the obstack. */ 679 680 /* A list of hard backward dependencies. The insn is a consumer of all the 681 deps mentioned here. */ 682 deps_list_t hard_back_deps; 683 684 /* A list of speculative (weak) dependencies. The insn is a consumer of all 685 the deps mentioned here. */ 686 deps_list_t spec_back_deps; 687 688 /* A list of insns which depend on the instruction. Unlike 'back_deps', 689 it represents forward dependencies. */ 690 deps_list_t forw_deps; 691 692 /* A list of scheduled producers of the instruction. Links are being moved 693 from 'back_deps' to 'resolved_back_deps' while scheduling. */ 694 deps_list_t resolved_back_deps; 695 696 /* A list of scheduled consumers of the instruction. Links are being moved 697 from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the 698 search in 'forw_deps'. */ 699 deps_list_t resolved_forw_deps; 700 701 /* Some insns (e.g. call) are not allowed to move across blocks. */ 702 unsigned int cant_move : 1; 703}; 704 705/* Bits used for storing values of the fields in the following 706 structure. */ 707#define INCREASE_BITS 8 708 709/* The structure describes how the corresponding insn increases the 710 register pressure for each cover class. */ 711struct reg_pressure_data 712{ 713 /* Pressure increase for given class because of clobber. */ 714 unsigned int clobber_increase : INCREASE_BITS; 715 /* Increase in register pressure for given class because of register 716 sets. */ 717 unsigned int set_increase : INCREASE_BITS; 718 /* Pressure increase for given class because of unused register 719 set. */ 720 unsigned int unused_set_increase : INCREASE_BITS; 721 /* Pressure change: #sets - #deaths. */ 722 int change : INCREASE_BITS; 723}; 724 725/* The following structure describes usage of registers by insns. */ 726struct reg_use_data 727{ 728 /* Regno used in the insn. */ 729 int regno; 730 /* Insn using the regno. */ 731 rtx insn; 732 /* Cyclic list of elements with the same regno. */ 733 struct reg_use_data *next_regno_use; 734 /* List of elements with the same insn. */ 735 struct reg_use_data *next_insn_use; 736}; 737 738/* The following structure describes used sets of registers by insns. 739 Registers are pseudos whose cover class is not NO_REGS or hard 740 registers available for allocations. */ 741struct reg_set_data 742{ 743 /* Regno used in the insn. */ 744 int regno; 745 /* Insn setting the regno. */ 746 rtx insn; 747 /* List of elements with the same insn. */ 748 struct reg_set_data *next_insn_set; 749}; 750 751struct _haifa_insn_data 752{ 753 /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t 754 because when h_i_d extends, addresses of the deps_list->first 755 change without updating deps_list->first->next->prev_nextp. */ 756 757 /* Logical uid gives the original ordering of the insns. */ 758 int luid; 759 760 /* A priority for each insn. */ 761 int priority; 762 763 /* The minimum clock tick at which the insn becomes ready. This is 764 used to note timing constraints for the insns in the pending list. */ 765 int tick; 766 767 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the 768 subsequent blocks in a region. */ 769 int inter_tick; 770 771 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */ 772 int queue_index; 773 774 short cost; 775 776 /* Set if there's DEF-USE dependence between some speculatively 777 moved load insn and this one. */ 778 unsigned int fed_by_spec_load : 1; 779 unsigned int is_load_insn : 1; 780 781 /* '> 0' if priority is valid, 782 '== 0' if priority was not yet computed, 783 '< 0' if priority in invalid and should be recomputed. */ 784 signed char priority_status; 785 786 /* What speculations are necessary to apply to schedule the instruction. */ 787 ds_t todo_spec; 788 789 /* What speculations were already applied. */ 790 ds_t done_spec; 791 792 /* What speculations are checked by this instruction. */ 793 ds_t check_spec; 794 795 /* Recovery block for speculation checks. */ 796 basic_block recovery_block; 797 798 /* Original pattern of the instruction. */ 799 rtx orig_pat; 800 801 /* The following array contains info how the insn increases register 802 pressure. There is an element for each cover class of pseudos 803 referenced in insns. */ 804 struct reg_pressure_data *reg_pressure; 805 /* The following array contains maximal reg pressure between last 806 scheduled insn and given insn. There is an element for each 807 cover class of pseudos referenced in insns. This info updated 808 after scheduling each insn for each insn between the two 809 mentioned insns. */ 810 int *max_reg_pressure; 811 /* The following list contains info about used pseudos and hard 812 registers available for allocation. */ 813 struct reg_use_data *reg_use_list; 814 /* The following list contains info about set pseudos and hard 815 registers available for allocation. */ 816 struct reg_set_data *reg_set_list; 817 /* Info about how scheduling the insn changes cost of register 818 pressure excess (between source and target). */ 819 int reg_pressure_excess_cost_change; 820}; 821 822typedef struct _haifa_insn_data haifa_insn_data_def; 823typedef haifa_insn_data_def *haifa_insn_data_t; 824 825DEF_VEC_O (haifa_insn_data_def); 826DEF_VEC_ALLOC_O (haifa_insn_data_def, heap); 827 828extern VEC(haifa_insn_data_def, heap) *h_i_d; 829 830#define HID(INSN) (VEC_index (haifa_insn_data_def, h_i_d, INSN_UID (INSN))) 831 832/* Accessor macros for h_i_d. There are more in haifa-sched.c and 833 sched-rgn.c. */ 834#define INSN_PRIORITY(INSN) (HID (INSN)->priority) 835#define INSN_REG_PRESSURE(INSN) (HID (INSN)->reg_pressure) 836#define INSN_MAX_REG_PRESSURE(INSN) (HID (INSN)->max_reg_pressure) 837#define INSN_REG_USE_LIST(INSN) (HID (INSN)->reg_use_list) 838#define INSN_REG_SET_LIST(INSN) (HID (INSN)->reg_set_list) 839#define INSN_REG_PRESSURE_EXCESS_COST_CHANGE(INSN) \ 840 (HID (INSN)->reg_pressure_excess_cost_change) 841#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status) 842 843typedef struct _haifa_deps_insn_data haifa_deps_insn_data_def; 844typedef haifa_deps_insn_data_def *haifa_deps_insn_data_t; 845 846DEF_VEC_O (haifa_deps_insn_data_def); 847DEF_VEC_ALLOC_O (haifa_deps_insn_data_def, heap); 848 849extern VEC(haifa_deps_insn_data_def, heap) *h_d_i_d; 850 851#define HDID(INSN) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \ 852 INSN_LUID (INSN))) 853#define INSN_DEP_COUNT(INSN) (HDID (INSN)->dep_count) 854#define HAS_INTERNAL_DEP(INSN) (HDID (INSN)->has_internal_dep) 855#define INSN_FORW_DEPS(INSN) (HDID (INSN)->forw_deps) 856#define INSN_RESOLVED_BACK_DEPS(INSN) (HDID (INSN)->resolved_back_deps) 857#define INSN_RESOLVED_FORW_DEPS(INSN) (HDID (INSN)->resolved_forw_deps) 858#define INSN_HARD_BACK_DEPS(INSN) (HDID (INSN)->hard_back_deps) 859#define INSN_SPEC_BACK_DEPS(INSN) (HDID (INSN)->spec_back_deps) 860#define CANT_MOVE(INSN) (HDID (INSN)->cant_move) 861#define CANT_MOVE_BY_LUID(LUID) (VEC_index (haifa_deps_insn_data_def, h_d_i_d, \ 862 LUID)->cant_move) 863 864 865#define INSN_PRIORITY(INSN) (HID (INSN)->priority) 866#define INSN_PRIORITY_STATUS(INSN) (HID (INSN)->priority_status) 867#define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0) 868#define TODO_SPEC(INSN) (HID (INSN)->todo_spec) 869#define DONE_SPEC(INSN) (HID (INSN)->done_spec) 870#define CHECK_SPEC(INSN) (HID (INSN)->check_spec) 871#define RECOVERY_BLOCK(INSN) (HID (INSN)->recovery_block) 872#define ORIG_PAT(INSN) (HID (INSN)->orig_pat) 873 874/* INSN is either a simple or a branchy speculation check. */ 875#define IS_SPECULATION_CHECK_P(INSN) \ 876 (sel_sched_p () ? sel_insn_is_speculation_check (INSN) : RECOVERY_BLOCK (INSN) != NULL) 877 878/* INSN is a speculation check that will simply reexecute the speculatively 879 scheduled instruction if the speculation fails. */ 880#define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \ 881 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR) 882 883/* INSN is a speculation check that will branch to RECOVERY_BLOCK if the 884 speculation fails. Insns in that block will reexecute the speculatively 885 scheduled code and then will return immediately after INSN thus preserving 886 semantics of the program. */ 887#define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \ 888 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR) 889 890/* The unchanging bit tracks whether a debug insn is to be handled 891 like an insn (i.e., schedule it) or like a note (e.g., it is next 892 to a basic block boundary. */ 893#define DEBUG_INSN_SCHED_P(insn) \ 894 (RTL_FLAG_CHECK1("DEBUG_INSN_SCHED_P", (insn), DEBUG_INSN)->unchanging) 895 896/* True if INSN is a debug insn that is next to a basic block 897 boundary, i.e., it is to be handled by the scheduler like a 898 note. */ 899#define BOUNDARY_DEBUG_INSN_P(insn) \ 900 (DEBUG_INSN_P (insn) && !DEBUG_INSN_SCHED_P (insn)) 901/* True if INSN is a debug insn that is not next to a basic block 902 boundary, i.e., it is to be handled by the scheduler like an 903 insn. */ 904#define SCHEDULE_DEBUG_INSN_P(insn) \ 905 (DEBUG_INSN_P (insn) && DEBUG_INSN_SCHED_P (insn)) 906 907/* Dep status (aka ds_t) of the link encapsulates information, that is needed 908 for speculative scheduling. Namely, it is 4 integers in the range 909 [0, MAX_DEP_WEAK] and 3 bits. 910 The integers correspond to the probability of the dependence to *not* 911 exist, it is the probability, that overcoming of this dependence will 912 not be followed by execution of the recovery code. Nevertheless, 913 whatever high the probability of success is, recovery code should still 914 be generated to preserve semantics of the program. To find a way to 915 get/set these integers, please refer to the {get, set}_dep_weak () 916 functions in sched-deps.c . 917 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-, 918 output- and anti- dependence. It is not enough for speculative scheduling 919 to know just the major type of all the dependence between two instructions, 920 as only true dependence can be overcome. 921 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved 922 for using to describe instruction's status. It is set whenever instruction 923 has at least one dependence, that cannot be overcame. 924 See also: check_dep_status () in sched-deps.c . */ 925 926/* We exclude sign bit. */ 927#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1) 928 929/* First '4' stands for 3 dep type bits and HARD_DEP bit. 930 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL} 931 dep weakness. */ 932#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4) 933 934/* Mask of speculative weakness in dep_status. */ 935#define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1) 936 937/* This constant means that dependence is fake with 99.999...% probability. 938 This is the maximum value, that can appear in dep_status. 939 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for 940 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when 941 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */ 942#define MAX_DEP_WEAK (DEP_WEAK_MASK - 1) 943 944/* This constant means that dependence is 99.999...% real and it is a really 945 bad idea to overcome it (though this can be done, preserving program 946 semantics). */ 947#define MIN_DEP_WEAK 1 948 949/* This constant represents 100% probability. 950 E.g. it is used to represent weakness of dependence, that doesn't exist. */ 951#define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK) 952 953/* Default weakness of speculative dependence. Used when we can't say 954 neither bad nor good about the dependence. */ 955#define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4) 956 957/* Offset for speculative weaknesses in dep_status. */ 958enum SPEC_TYPES_OFFSETS { 959 BEGIN_DATA_BITS_OFFSET = 0, 960 BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 961 BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 962 BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK 963}; 964 965/* The following defines provide numerous constants used to distinguish between 966 different types of speculative dependencies. */ 967 968/* Dependence can be overcome with generation of new data speculative 969 instruction. */ 970#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET) 971 972/* This dependence is to the instruction in the recovery block, that was 973 formed to recover after data-speculation failure. 974 Thus, this dependence can overcome with generating of the copy of 975 this instruction in the recovery block. */ 976#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET) 977 978/* Dependence can be overcome with generation of new control speculative 979 instruction. */ 980#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET) 981 982/* This dependence is to the instruction in the recovery block, that was 983 formed to recover after control-speculation failure. 984 Thus, this dependence can be overcome with generating of the copy of 985 this instruction in the recovery block. */ 986#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET) 987 988/* A few convenient combinations. */ 989#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL) 990#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA) 991#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL) 992#define SPECULATIVE (DATA_SPEC | CONTROL_SPEC) 993#define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL) 994 995/* Constants, that are helpful in iterating through dep_status. */ 996#define FIRST_SPEC_TYPE BEGIN_DATA 997#define LAST_SPEC_TYPE BE_IN_CONTROL 998#define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK 999 1000/* Dependence on instruction can be of multiple types 1001 (e.g. true and output). This fields enhance REG_NOTE_KIND information 1002 of the dependence. */ 1003#define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK)) 1004#define DEP_OUTPUT (DEP_TRUE << 1) 1005#define DEP_ANTI (DEP_OUTPUT << 1) 1006 1007#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI) 1008 1009/* Instruction has non-speculative dependence. This bit represents the 1010 property of an instruction - not the one of a dependence. 1011 Therefore, it can appear only in TODO_SPEC field of an instruction. */ 1012#define HARD_DEP (DEP_ANTI << 1) 1013 1014/* This represents the results of calling sched-deps.c functions, 1015 which modify dependencies. */ 1016enum DEPS_ADJUST_RESULT { 1017 /* No dependence needed (e.g. producer == consumer). */ 1018 DEP_NODEP, 1019 /* Dependence is already present and wasn't modified. */ 1020 DEP_PRESENT, 1021 /* Existing dependence was modified to include additional information. */ 1022 DEP_CHANGED, 1023 /* New dependence has been created. */ 1024 DEP_CREATED 1025}; 1026 1027/* Represents the bits that can be set in the flags field of the 1028 sched_info structure. */ 1029enum SCHED_FLAGS { 1030 /* If set, generate links between instruction as DEPS_LIST. 1031 Otherwise, generate usual INSN_LIST links. */ 1032 USE_DEPS_LIST = 1, 1033 /* Perform data or control (or both) speculation. 1034 Results in generation of data and control speculative dependencies. 1035 Requires USE_DEPS_LIST set. */ 1036 DO_SPECULATION = USE_DEPS_LIST << 1, 1037 SCHED_RGN = DO_SPECULATION << 1, 1038 SCHED_EBB = SCHED_RGN << 1, 1039 /* Scheduler can possibly create new basic blocks. Used for assertions. */ 1040 NEW_BBS = SCHED_EBB << 1, 1041 SEL_SCHED = NEW_BBS << 1 1042}; 1043 1044enum SPEC_SCHED_FLAGS { 1045 COUNT_SPEC_IN_CRITICAL_PATH = 1, 1046 PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1, 1047 PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1, 1048 SEL_SCHED_SPEC_DONT_CHECK_CONTROL = PREFER_NON_CONTROL_SPEC << 1 1049}; 1050 1051#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \ 1052 != NOTE_INSN_BASIC_BLOCK)) 1053 1054extern FILE *sched_dump; 1055extern int sched_verbose; 1056 1057extern spec_info_t spec_info; 1058extern bool haifa_recovery_bb_ever_added_p; 1059 1060/* Exception Free Loads: 1061 1062 We define five classes of speculative loads: IFREE, IRISKY, 1063 PFREE, PRISKY, and MFREE. 1064 1065 IFREE loads are loads that are proved to be exception-free, just 1066 by examining the load insn. Examples for such loads are loads 1067 from TOC and loads of global data. 1068 1069 IRISKY loads are loads that are proved to be exception-risky, 1070 just by examining the load insn. Examples for such loads are 1071 volatile loads and loads from shared memory. 1072 1073 PFREE loads are loads for which we can prove, by examining other 1074 insns, that they are exception-free. Currently, this class consists 1075 of loads for which we are able to find a "similar load", either in 1076 the target block, or, if only one split-block exists, in that split 1077 block. Load2 is similar to load1 if both have same single base 1078 register. We identify only part of the similar loads, by finding 1079 an insn upon which both load1 and load2 have a DEF-USE dependence. 1080 1081 PRISKY loads are loads for which we can prove, by examining other 1082 insns, that they are exception-risky. Currently we have two proofs for 1083 such loads. The first proof detects loads that are probably guarded by a 1084 test on the memory address. This proof is based on the 1085 backward and forward data dependence information for the region. 1086 Let load-insn be the examined load. 1087 Load-insn is PRISKY iff ALL the following hold: 1088 1089 - insn1 is not in the same block as load-insn 1090 - there is a DEF-USE dependence chain (insn1, ..., load-insn) 1091 - test-insn is either a compare or a branch, not in the same block 1092 as load-insn 1093 - load-insn is reachable from test-insn 1094 - there is a DEF-USE dependence chain (insn1, ..., test-insn) 1095 1096 This proof might fail when the compare and the load are fed 1097 by an insn not in the region. To solve this, we will add to this 1098 group all loads that have no input DEF-USE dependence. 1099 1100 The second proof detects loads that are directly or indirectly 1101 fed by a speculative load. This proof is affected by the 1102 scheduling process. We will use the flag fed_by_spec_load. 1103 Initially, all insns have this flag reset. After a speculative 1104 motion of an insn, if insn is either a load, or marked as 1105 fed_by_spec_load, we will also mark as fed_by_spec_load every 1106 insn1 for which a DEF-USE dependence (insn, insn1) exists. A 1107 load which is fed_by_spec_load is also PRISKY. 1108 1109 MFREE (maybe-free) loads are all the remaining loads. They may be 1110 exception-free, but we cannot prove it. 1111 1112 Now, all loads in IFREE and PFREE classes are considered 1113 exception-free, while all loads in IRISKY and PRISKY classes are 1114 considered exception-risky. As for loads in the MFREE class, 1115 these are considered either exception-free or exception-risky, 1116 depending on whether we are pessimistic or optimistic. We have 1117 to take the pessimistic approach to assure the safety of 1118 speculative scheduling, but we can take the optimistic approach 1119 by invoking the -fsched_spec_load_dangerous option. */ 1120 1121enum INSN_TRAP_CLASS 1122{ 1123 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2, 1124 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5 1125}; 1126 1127#define WORST_CLASS(class1, class2) \ 1128((class1 > class2) ? class1 : class2) 1129 1130#ifndef __GNUC__ 1131#define __inline 1132#endif 1133 1134#ifndef HAIFA_INLINE 1135#define HAIFA_INLINE __inline 1136#endif 1137 1138struct sched_deps_info_def 1139{ 1140 /* Called when computing dependencies for a JUMP_INSN. This function 1141 should store the set of registers that must be considered as set by 1142 the jump in the regset. */ 1143 void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset); 1144 1145 /* Start analyzing insn. */ 1146 void (*start_insn) (rtx); 1147 1148 /* Finish analyzing insn. */ 1149 void (*finish_insn) (void); 1150 1151 /* Start analyzing insn LHS (Left Hand Side). */ 1152 void (*start_lhs) (rtx); 1153 1154 /* Finish analyzing insn LHS. */ 1155 void (*finish_lhs) (void); 1156 1157 /* Start analyzing insn RHS (Right Hand Side). */ 1158 void (*start_rhs) (rtx); 1159 1160 /* Finish analyzing insn RHS. */ 1161 void (*finish_rhs) (void); 1162 1163 /* Note set of the register. */ 1164 void (*note_reg_set) (int); 1165 1166 /* Note clobber of the register. */ 1167 void (*note_reg_clobber) (int); 1168 1169 /* Note use of the register. */ 1170 void (*note_reg_use) (int); 1171 1172 /* Note memory dependence of type DS between MEM1 and MEM2 (which is 1173 in the INSN2). */ 1174 void (*note_mem_dep) (rtx mem1, rtx mem2, rtx insn2, ds_t ds); 1175 1176 /* Note a dependence of type DS from the INSN. */ 1177 void (*note_dep) (rtx insn, ds_t ds); 1178 1179 /* Nonzero if we should use cselib for better alias analysis. This 1180 must be 0 if the dependency information is used after sched_analyze 1181 has completed, e.g. if we're using it to initialize state for successor 1182 blocks in region scheduling. */ 1183 unsigned int use_cselib : 1; 1184 1185 /* If set, generate links between instruction as DEPS_LIST. 1186 Otherwise, generate usual INSN_LIST links. */ 1187 unsigned int use_deps_list : 1; 1188 1189 /* Generate data and control speculative dependencies. 1190 Requires USE_DEPS_LIST set. */ 1191 unsigned int generate_spec_deps : 1; 1192}; 1193 1194extern struct sched_deps_info_def *sched_deps_info; 1195 1196 1197/* Functions in sched-deps.c. */ 1198extern bool sched_insns_conditions_mutex_p (const_rtx, const_rtx); 1199extern bool sched_insn_is_legitimate_for_speculation_p (const_rtx, ds_t); 1200extern void add_dependence (rtx, rtx, enum reg_note); 1201extern void sched_analyze (struct deps_desc *, rtx, rtx); 1202extern void init_deps (struct deps_desc *, bool); 1203extern void init_deps_reg_last (struct deps_desc *); 1204extern void free_deps (struct deps_desc *); 1205extern void init_deps_global (void); 1206extern void finish_deps_global (void); 1207extern void deps_analyze_insn (struct deps_desc *, rtx); 1208extern void remove_from_deps (struct deps_desc *, rtx); 1209 1210extern dw_t get_dep_weak_1 (ds_t, ds_t); 1211extern dw_t get_dep_weak (ds_t, ds_t); 1212extern ds_t set_dep_weak (ds_t, ds_t, dw_t); 1213extern dw_t estimate_dep_weak (rtx, rtx); 1214extern ds_t ds_merge (ds_t, ds_t); 1215extern ds_t ds_full_merge (ds_t, ds_t, rtx, rtx); 1216extern ds_t ds_max_merge (ds_t, ds_t); 1217extern dw_t ds_weak (ds_t); 1218extern ds_t ds_get_speculation_types (ds_t); 1219extern ds_t ds_get_max_dep_weak (ds_t); 1220 1221extern void sched_deps_init (bool); 1222extern void sched_deps_finish (void); 1223 1224extern void haifa_note_reg_set (int); 1225extern void haifa_note_reg_clobber (int); 1226extern void haifa_note_reg_use (int); 1227 1228extern void maybe_extend_reg_info_p (void); 1229 1230extern void deps_start_bb (struct deps_desc *, rtx); 1231extern enum reg_note ds_to_dt (ds_t); 1232 1233extern bool deps_pools_are_empty_p (void); 1234extern void sched_free_deps (rtx, rtx, bool); 1235extern void extend_dependency_caches (int, bool); 1236 1237extern void debug_ds (ds_t); 1238 1239 1240/* Functions in haifa-sched.c. */ 1241extern void sched_init_region_reg_pressure_info (void); 1242extern int haifa_classify_insn (const_rtx); 1243extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *); 1244extern int no_real_insns_p (const_rtx, const_rtx); 1245 1246extern int insn_cost (rtx); 1247extern int dep_cost_1 (dep_t, dw_t); 1248extern int dep_cost (dep_t); 1249extern int set_priorities (rtx, rtx); 1250 1251extern void sched_setup_bb_reg_pressure_info (basic_block, rtx); 1252extern void schedule_block (basic_block *); 1253 1254extern int cycle_issued_insns; 1255extern int issue_rate; 1256extern int dfa_lookahead; 1257 1258extern void ready_sort (struct ready_list *); 1259extern rtx ready_element (struct ready_list *, int); 1260extern rtx *ready_lastpos (struct ready_list *); 1261 1262extern int try_ready (rtx); 1263extern void sched_extend_ready_list (int); 1264extern void sched_finish_ready_list (void); 1265extern void sched_change_pattern (rtx, rtx); 1266extern int sched_speculate_insn (rtx, ds_t, rtx *); 1267extern void unlink_bb_notes (basic_block, basic_block); 1268extern void add_block (basic_block, basic_block); 1269extern rtx bb_note (basic_block); 1270extern void concat_note_lists (rtx, rtx *); 1271extern rtx sched_emit_insn (rtx); 1272 1273 1274/* Types and functions in sched-rgn.c. */ 1275 1276/* A region is the main entity for interblock scheduling: insns 1277 are allowed to move between blocks in the same region, along 1278 control flow graph edges, in the 'up' direction. */ 1279typedef struct 1280{ 1281 /* Number of extended basic blocks in region. */ 1282 int rgn_nr_blocks; 1283 /* cblocks in the region (actually index in rgn_bb_table). */ 1284 int rgn_blocks; 1285 /* Dependencies for this region are already computed. Basically, indicates, 1286 that this is a recovery block. */ 1287 unsigned int dont_calc_deps : 1; 1288 /* This region has at least one non-trivial ebb. */ 1289 unsigned int has_real_ebb : 1; 1290} 1291region; 1292 1293extern int nr_regions; 1294extern region *rgn_table; 1295extern int *rgn_bb_table; 1296extern int *block_to_bb; 1297extern int *containing_rgn; 1298 1299/* Often used short-hand in the scheduler. The rest of the compiler uses 1300 BLOCK_FOR_INSN(INSN) and an indirect reference to get the basic block 1301 number ("index"). For historical reasons, the scheduler does not. */ 1302#define BLOCK_NUM(INSN) (BLOCK_FOR_INSN (INSN)->index + 0) 1303 1304#define RGN_NR_BLOCKS(rgn) (rgn_table[rgn].rgn_nr_blocks) 1305#define RGN_BLOCKS(rgn) (rgn_table[rgn].rgn_blocks) 1306#define RGN_DONT_CALC_DEPS(rgn) (rgn_table[rgn].dont_calc_deps) 1307#define RGN_HAS_REAL_EBB(rgn) (rgn_table[rgn].has_real_ebb) 1308#define BLOCK_TO_BB(block) (block_to_bb[block]) 1309#define CONTAINING_RGN(block) (containing_rgn[block]) 1310 1311/* The mapping from ebb to block. */ 1312extern int *ebb_head; 1313#define BB_TO_BLOCK(ebb) (rgn_bb_table[ebb_head[ebb]]) 1314#define EBB_FIRST_BB(ebb) BASIC_BLOCK (BB_TO_BLOCK (ebb)) 1315#define EBB_LAST_BB(ebb) BASIC_BLOCK (rgn_bb_table[ebb_head[ebb + 1] - 1]) 1316#define INSN_BB(INSN) (BLOCK_TO_BB (BLOCK_NUM (INSN))) 1317 1318extern int current_nr_blocks; 1319extern int current_blocks; 1320extern int target_bb; 1321 1322extern bool sched_is_disabled_for_current_region_p (void); 1323extern void sched_rgn_init (bool); 1324extern void sched_rgn_finish (void); 1325extern void rgn_setup_region (int); 1326extern void sched_rgn_compute_dependencies (int); 1327extern void sched_rgn_local_init (int); 1328extern void sched_rgn_local_finish (void); 1329extern void sched_rgn_local_free (void); 1330extern void extend_regions (void); 1331extern void rgn_make_new_region_out_of_new_block (basic_block); 1332 1333extern void compute_priorities (void); 1334extern void increase_insn_priority (rtx, int); 1335extern void debug_rgn_dependencies (int); 1336extern void debug_dependencies (rtx, rtx); 1337extern void free_rgn_deps (void); 1338extern int contributes_to_priority (rtx, rtx); 1339extern void extend_rgns (int *, int *, sbitmap, int *); 1340extern void deps_join (struct deps_desc *, struct deps_desc *); 1341 1342extern void rgn_setup_common_sched_info (void); 1343extern void rgn_setup_sched_infos (void); 1344 1345extern void debug_regions (void); 1346extern void debug_region (int); 1347extern void dump_region_dot (FILE *, int); 1348extern void dump_region_dot_file (const char *, int); 1349 1350extern void haifa_sched_init (void); 1351extern void haifa_sched_finish (void); 1352 1353/* sched-deps.c interface to walk, add, search, update, resolve, delete 1354 and debug instruction dependencies. */ 1355 1356/* Constants defining dependences lists. */ 1357 1358/* No list. */ 1359#define SD_LIST_NONE (0) 1360 1361/* hard_back_deps. */ 1362#define SD_LIST_HARD_BACK (1) 1363 1364/* spec_back_deps. */ 1365#define SD_LIST_SPEC_BACK (2) 1366 1367/* forw_deps. */ 1368#define SD_LIST_FORW (4) 1369 1370/* resolved_back_deps. */ 1371#define SD_LIST_RES_BACK (8) 1372 1373/* resolved_forw_deps. */ 1374#define SD_LIST_RES_FORW (16) 1375 1376#define SD_LIST_BACK (SD_LIST_HARD_BACK | SD_LIST_SPEC_BACK) 1377 1378/* A type to hold above flags. */ 1379typedef int sd_list_types_def; 1380 1381extern void sd_next_list (const_rtx, sd_list_types_def *, deps_list_t *, bool *); 1382 1383/* Iterator to walk through, resolve and delete dependencies. */ 1384struct _sd_iterator 1385{ 1386 /* What lists to walk. Can be any combination of SD_LIST_* flags. */ 1387 sd_list_types_def types; 1388 1389 /* Instruction dependencies lists of which will be walked. */ 1390 rtx insn; 1391 1392 /* Pointer to the next field of the previous element. This is not 1393 simply a pointer to the next element to allow easy deletion from the 1394 list. When a dep is being removed from the list the iterator 1395 will automatically advance because the value in *linkp will start 1396 referring to the next element. */ 1397 dep_link_t *linkp; 1398 1399 /* True if the current list is a resolved one. */ 1400 bool resolved_p; 1401}; 1402 1403typedef struct _sd_iterator sd_iterator_def; 1404 1405/* ??? We can move some definitions that are used in below inline functions 1406 out of sched-int.h to sched-deps.c provided that the below functions will 1407 become global externals. 1408 These definitions include: 1409 * struct _deps_list: opaque pointer is needed at global scope. 1410 * struct _dep_link: opaque pointer is needed at scope of sd_iterator_def. 1411 * struct _dep_node: opaque pointer is needed at scope of 1412 struct _deps_link. */ 1413 1414/* Return initialized iterator. */ 1415static inline sd_iterator_def 1416sd_iterator_start (rtx insn, sd_list_types_def types) 1417{ 1418 /* Some dep_link a pointer to which will return NULL. */ 1419 static dep_link_t null_link = NULL; 1420 1421 sd_iterator_def i; 1422 1423 i.types = types; 1424 i.insn = insn; 1425 i.linkp = &null_link; 1426 1427 /* Avoid 'uninitialized warning'. */ 1428 i.resolved_p = false; 1429 1430 return i; 1431} 1432 1433/* Return the current element. */ 1434static inline bool 1435sd_iterator_cond (sd_iterator_def *it_ptr, dep_t *dep_ptr) 1436{ 1437 dep_link_t link = *it_ptr->linkp; 1438 1439 if (link != NULL) 1440 { 1441 *dep_ptr = DEP_LINK_DEP (link); 1442 return true; 1443 } 1444 else 1445 { 1446 sd_list_types_def types = it_ptr->types; 1447 1448 if (types != SD_LIST_NONE) 1449 /* Switch to next list. */ 1450 { 1451 deps_list_t list; 1452 1453 sd_next_list (it_ptr->insn, 1454 &it_ptr->types, &list, &it_ptr->resolved_p); 1455 1456 it_ptr->linkp = &DEPS_LIST_FIRST (list); 1457 1458 if (list) 1459 return sd_iterator_cond (it_ptr, dep_ptr); 1460 } 1461 1462 *dep_ptr = NULL; 1463 return false; 1464 } 1465} 1466 1467/* Advance iterator. */ 1468static inline void 1469sd_iterator_next (sd_iterator_def *it_ptr) 1470{ 1471 it_ptr->linkp = &DEP_LINK_NEXT (*it_ptr->linkp); 1472} 1473 1474/* A cycle wrapper. */ 1475#define FOR_EACH_DEP(INSN, LIST_TYPES, ITER, DEP) \ 1476 for ((ITER) = sd_iterator_start ((INSN), (LIST_TYPES)); \ 1477 sd_iterator_cond (&(ITER), &(DEP)); \ 1478 sd_iterator_next (&(ITER))) 1479 1480extern int sd_lists_size (const_rtx, sd_list_types_def); 1481extern bool sd_lists_empty_p (const_rtx, sd_list_types_def); 1482extern void sd_init_insn (rtx); 1483extern void sd_finish_insn (rtx); 1484extern dep_t sd_find_dep_between (rtx, rtx, bool); 1485extern void sd_add_dep (dep_t, bool); 1486extern enum DEPS_ADJUST_RESULT sd_add_or_update_dep (dep_t, bool); 1487extern void sd_resolve_dep (sd_iterator_def); 1488extern void sd_copy_back_deps (rtx, rtx, bool); 1489extern void sd_delete_dep (sd_iterator_def); 1490extern void sd_debug_lists (rtx, sd_list_types_def); 1491 1492#endif /* INSN_SCHEDULING */ 1493 1494/* Functions in sched-vis.c. These must be outside INSN_SCHEDULING as 1495 sched-vis.c is compiled always. */ 1496extern void print_insn (char *, const_rtx, int); 1497extern void print_pattern (char *, const_rtx, int); 1498extern void print_value (char *, const_rtx, int); 1499 1500#endif /* GCC_SCHED_INT_H */ 1501