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