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