1/* Instruction scheduling pass. This file contains definitions used 2 internally in the scheduler. 3 Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4 1999, 2000, 2001, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 5 6This file is part of GCC. 7 8GCC is free software; you can redistribute it and/or modify it under 9the terms of the GNU General Public License as published by the Free 10Software Foundation; either version 2, or (at your option) any later 11version. 12 13GCC is distributed in the hope that it will be useful, but WITHOUT ANY 14WARRANTY; without even the implied warranty of MERCHANTABILITY or 15FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 16for more details. 17 18You should have received a copy of the GNU General Public License 19along with GCC; see the file COPYING. If not, write to the Free 20Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 2102110-1301, USA. */ 22 23#ifndef GCC_SCHED_INT_H 24#define GCC_SCHED_INT_H 25 26/* For state_t. */ 27#include "insn-attr.h" 28/* For regset_head. */ 29#include "basic-block.h" 30/* For reg_note. */ 31#include "rtl.h" 32 33/* Pointer to data describing the current DFA state. */ 34extern state_t curr_state; 35 36/* Forward declaration. */ 37struct ready_list; 38 39/* Type to represent status of a dependence. */ 40typedef int ds_t; 41 42/* Type to represent weakness of speculative dependence. */ 43typedef int dw_t; 44 45/* Describe state of dependencies used during sched_analyze phase. */ 46struct deps 47{ 48 /* The *_insns and *_mems are paired lists. Each pending memory operation 49 will have a pointer to the MEM rtx on one list and a pointer to the 50 containing insn on the other list in the same place in the list. */ 51 52 /* We can't use add_dependence like the old code did, because a single insn 53 may have multiple memory accesses, and hence needs to be on the list 54 once for each memory access. Add_dependence won't let you add an insn 55 to a list more than once. */ 56 57 /* An INSN_LIST containing all insns with pending read operations. */ 58 rtx pending_read_insns; 59 60 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 61 rtx pending_read_mems; 62 63 /* An INSN_LIST containing all insns with pending write operations. */ 64 rtx pending_write_insns; 65 66 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 67 rtx pending_write_mems; 68 69 /* Indicates the combined length of the two pending lists. We must prevent 70 these lists from ever growing too large since the number of dependencies 71 produced is at least O(N*N), and execution time is at least O(4*N*N), as 72 a function of the length of these pending lists. */ 73 int pending_lists_length; 74 75 /* Length of the pending memory flush list. Large functions with no 76 calls may build up extremely large lists. */ 77 int pending_flush_length; 78 79 /* The last insn upon which all memory references must depend. 80 This is an insn which flushed the pending lists, creating a dependency 81 between it and all previously pending memory references. This creates 82 a barrier (or a checkpoint) which no memory reference is allowed to cross. 83 84 This includes all non constant CALL_INSNs. When we do interprocedural 85 alias analysis, this restriction can be relaxed. 86 This may also be an INSN that writes memory if the pending lists grow 87 too large. */ 88 rtx last_pending_memory_flush; 89 90 /* A list of the last function calls we have seen. We use a list to 91 represent last function calls from multiple predecessor blocks. 92 Used to prevent register lifetimes from expanding unnecessarily. */ 93 rtx last_function_call; 94 95 /* A list of insns which use a pseudo register that does not already 96 cross a call. We create dependencies between each of those insn 97 and the next call insn, to ensure that they won't cross a call after 98 scheduling is done. */ 99 rtx sched_before_next_call; 100 101 /* Used to keep post-call pseudo/hard reg movements together with 102 the call. */ 103 enum { not_post_call, post_call, post_call_initial } in_post_call_group_p; 104 105 /* Set to the tail insn of the outermost libcall block. 106 107 When nonzero, we will mark each insn processed by sched_analyze_insn 108 with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */ 109 rtx libcall_block_tail_insn; 110 111 /* The maximum register number for the following arrays. Before reload 112 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 113 int max_reg; 114 115 /* Element N is the next insn that sets (hard or pseudo) register 116 N within the current basic block; or zero, if there is no 117 such insn. Needed for new registers which may be introduced 118 by splitting insns. */ 119 struct deps_reg 120 { 121 rtx uses; 122 rtx sets; 123 rtx clobbers; 124 int uses_length; 125 int clobbers_length; 126 } *reg_last; 127 128 /* Element N is set for each register that has any nonzero element 129 in reg_last[N].{uses,sets,clobbers}. */ 130 regset_head reg_last_in_use; 131 132 /* Element N is set for each register that is conditionally set. */ 133 regset_head reg_conditional_sets; 134}; 135 136/* This structure holds some state of the current scheduling pass, and 137 contains some function pointers that abstract out some of the non-generic 138 functionality from functions such as schedule_block or schedule_insn. 139 There is one global variable, current_sched_info, which points to the 140 sched_info structure currently in use. */ 141struct sched_info 142{ 143 /* Add all insns that are initially ready to the ready list. Called once 144 before scheduling a set of insns. */ 145 void (*init_ready_list) (void); 146 /* Called after taking an insn from the ready list. Returns nonzero if 147 this insn can be scheduled, nonzero if we should silently discard it. */ 148 int (*can_schedule_ready_p) (rtx); 149 /* Return nonzero if there are more insns that should be scheduled. */ 150 int (*schedule_more_p) (void); 151 /* Called after an insn has all its hard dependencies resolved. 152 Adjusts status of instruction (which is passed through second parameter) 153 to indicate if instruction should be moved to the ready list or the 154 queue, or if it should silently discard it (until next resolved 155 dependence). */ 156 ds_t (*new_ready) (rtx, ds_t); 157 /* Compare priority of two insns. Return a positive number if the second 158 insn is to be preferred for scheduling, and a negative one if the first 159 is to be preferred. Zero if they are equally good. */ 160 int (*rank) (rtx, rtx); 161 /* Return a string that contains the insn uid and optionally anything else 162 necessary to identify this insn in an output. It's valid to use a 163 static buffer for this. The ALIGNED parameter should cause the string 164 to be formatted so that multiple output lines will line up nicely. */ 165 const char *(*print_insn) (rtx, int); 166 /* Return nonzero if an insn should be included in priority 167 calculations. */ 168 int (*contributes_to_priority) (rtx, rtx); 169 /* Called when computing dependencies for a JUMP_INSN. This function 170 should store the set of registers that must be considered as set by 171 the jump in the regset. */ 172 void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset); 173 174 /* The boundaries of the set of insns to be scheduled. */ 175 rtx prev_head, next_tail; 176 177 /* Filled in after the schedule is finished; the first and last scheduled 178 insns. */ 179 rtx head, tail; 180 181 /* If nonzero, enables an additional sanity check in schedule_block. */ 182 unsigned int queue_must_finish_empty:1; 183 /* Nonzero if we should use cselib for better alias analysis. This 184 must be 0 if the dependency information is used after sched_analyze 185 has completed, e.g. if we're using it to initialize state for successor 186 blocks in region scheduling. */ 187 unsigned int use_cselib:1; 188 189 /* Maximum priority that has been assigned to an insn. */ 190 int sched_max_insns_priority; 191 192 /* Hooks to support speculative scheduling. */ 193 194 /* Called to notify frontend that instruction is being added (second 195 parameter == 0) or removed (second parameter == 1). */ 196 void (*add_remove_insn) (rtx, int); 197 198 /* Called to notify frontend that instruction is being scheduled. 199 The first parameter - instruction to scheduled, the second parameter - 200 last scheduled instruction. */ 201 void (*begin_schedule_ready) (rtx, rtx); 202 203 /* Called to notify frontend, that new basic block is being added. 204 The first parameter - new basic block. 205 The second parameter - block, after which new basic block is being added, 206 or EXIT_BLOCK_PTR, if recovery block is being added, 207 or NULL, if standalone block is being added. */ 208 void (*add_block) (basic_block, basic_block); 209 210 /* If the second parameter is not NULL, return nonnull value, if the 211 basic block should be advanced. 212 If the second parameter is NULL, return the next basic block in EBB. 213 The first parameter is the current basic block in EBB. */ 214 basic_block (*advance_target_bb) (basic_block, rtx); 215 216 /* Called after blocks were rearranged due to movement of jump instruction. 217 The first parameter - index of basic block, in which jump currently is. 218 The second parameter - index of basic block, in which jump used 219 to be. 220 The third parameter - index of basic block, that follows the second 221 parameter. */ 222 void (*fix_recovery_cfg) (int, int, int); 223 224#ifdef ENABLE_CHECKING 225 /* If the second parameter is zero, return nonzero, if block is head of the 226 region. 227 If the second parameter is nonzero, return nonzero, if block is leaf of 228 the region. 229 global_live_at_start should not change in region heads and 230 global_live_at_end should not change in region leafs due to scheduling. */ 231 int (*region_head_or_leaf_p) (basic_block, int); 232#endif 233 234 /* ??? FIXME: should use straight bitfields inside sched_info instead of 235 this flag field. */ 236 unsigned int flags; 237}; 238 239/* This structure holds description of the properties for speculative 240 scheduling. */ 241struct spec_info_def 242{ 243 /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL}, 244 BE_IN_{DATA_CONTROL}. */ 245 int mask; 246 247 /* A dump file for additional information on speculative scheduling. */ 248 FILE *dump; 249 250 /* Minimal cumulative weakness of speculative instruction's 251 dependencies, so that insn will be scheduled. */ 252 dw_t weakness_cutoff; 253 254 /* Flags from the enum SPEC_SCHED_FLAGS. */ 255 int flags; 256}; 257typedef struct spec_info_def *spec_info_t; 258 259extern struct sched_info *current_sched_info; 260 261/* Indexed by INSN_UID, the collection of all data associated with 262 a single instruction. */ 263 264struct haifa_insn_data 265{ 266 /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 267 it represents forward dependencies. */ 268 rtx depend; 269 270 /* A list of scheduled producers of the instruction. Links are being moved 271 from LOG_LINKS to RESOLVED_DEPS during scheduling. */ 272 rtx resolved_deps; 273 274 /* The line number note in effect for each insn. For line number 275 notes, this indicates whether the note may be reused. */ 276 rtx line_note; 277 278 /* Logical uid gives the original ordering of the insns. */ 279 int luid; 280 281 /* A priority for each insn. */ 282 int priority; 283 284 /* The number of incoming edges in the forward dependency graph. 285 As scheduling proceeds, counts are decreased. An insn moves to 286 the ready queue when its counter reaches zero. */ 287 int dep_count; 288 289 /* Number of instructions referring to this insn. */ 290 int ref_count; 291 292 /* The minimum clock tick at which the insn becomes ready. This is 293 used to note timing constraints for the insns in the pending list. */ 294 int tick; 295 296 /* INTER_TICK is used to adjust INSN_TICKs of instructions from the 297 subsequent blocks in a region. */ 298 int inter_tick; 299 300 /* See comment on QUEUE_INDEX macro in haifa-sched.c. */ 301 int queue_index; 302 303 short cost; 304 305 /* This weight is an estimation of the insn's contribution to 306 register pressure. */ 307 short reg_weight; 308 309 /* Some insns (e.g. call) are not allowed to move across blocks. */ 310 unsigned int cant_move : 1; 311 312 /* Set if there's DEF-USE dependence between some speculatively 313 moved load insn and this one. */ 314 unsigned int fed_by_spec_load : 1; 315 unsigned int is_load_insn : 1; 316 317 /* Nonzero if priority has been computed already. */ 318 unsigned int priority_known : 1; 319 320 /* Nonzero if instruction has internal dependence 321 (e.g. add_dependence was invoked with (insn == elem)). */ 322 unsigned int has_internal_dep : 1; 323 324 /* What speculations are necessary to apply to schedule the instruction. */ 325 ds_t todo_spec; 326 /* What speculations were already applied. */ 327 ds_t done_spec; 328 /* What speculations are checked by this instruction. */ 329 ds_t check_spec; 330 331 /* Recovery block for speculation checks. */ 332 basic_block recovery_block; 333 334 /* Original pattern of the instruction. */ 335 rtx orig_pat; 336}; 337 338extern struct haifa_insn_data *h_i_d; 339/* Used only if (current_sched_info->flags & USE_GLAT) != 0. 340 These regsets store global_live_at_{start, end} information 341 for each basic block. */ 342extern regset *glat_start, *glat_end; 343 344/* Accessor macros for h_i_d. There are more in haifa-sched.c and 345 sched-rgn.c. */ 346#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 347#define RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps) 348#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 349#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 350#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 351#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 352#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 353#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 354#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 355#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep) 356#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec) 357#define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec) 358#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec) 359#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block) 360#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat) 361 362/* INSN is either a simple or a branchy speculation check. */ 363#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL) 364 365/* INSN is a speculation check that will simply reexecute the speculatively 366 scheduled instruction if the speculation fails. */ 367#define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \ 368 (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR) 369 370/* INSN is a speculation check that will branch to RECOVERY_BLOCK if the 371 speculation fails. Insns in that block will reexecute the speculatively 372 scheduled code and then will return immediately after INSN thus preserving 373 semantics of the program. */ 374#define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \ 375 (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR) 376 377/* DEP_STATUS of the link encapsulates information, that is needed for 378 speculative scheduling. Namely, it is 4 integers in the range 379 [0, MAX_DEP_WEAK] and 3 bits. 380 The integers correspond to the probability of the dependence to *not* 381 exist, it is the probability, that overcoming of this dependence will 382 not be followed by execution of the recovery code. Nevertheless, 383 whatever high the probability of success is, recovery code should still 384 be generated to preserve semantics of the program. To find a way to 385 get/set these integers, please refer to the {get, set}_dep_weak () 386 functions in sched-deps.c . 387 The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-, 388 output- and anti- dependence. It is not enough for speculative scheduling 389 to know just the major type of all the dependence between two instructions, 390 as only true dependence can be overcome. 391 There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved 392 for using to describe instruction's status. It is set whenever instruction 393 has at least one dependence, that cannot be overcome. 394 See also: check_dep_status () in sched-deps.c . */ 395#define DEP_STATUS(LINK) XINT (LINK, 2) 396 397/* We exclude sign bit. */ 398#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1) 399 400/* First '4' stands for 3 dep type bits and HARD_DEP bit. 401 Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL} 402 dep weakness. */ 403#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4) 404 405/* Mask of speculative weakness in dep_status. */ 406#define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1) 407 408/* This constant means that dependence is fake with 99.999...% probability. 409 This is the maximum value, that can appear in dep_status. 410 Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for 411 debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when 412 done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */ 413#define MAX_DEP_WEAK (DEP_WEAK_MASK - 1) 414 415/* This constant means that dependence is 99.999...% real and it is a really 416 bad idea to overcome it (though this can be done, preserving program 417 semantics). */ 418#define MIN_DEP_WEAK 1 419 420/* This constant represents 100% probability. 421 E.g. it is used to represent weakness of dependence, that doesn't exist. */ 422#define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK) 423 424/* Default weakness of speculative dependence. Used when we can't say 425 neither bad nor good about the dependence. */ 426#define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4) 427 428/* Offset for speculative weaknesses in dep_status. */ 429enum SPEC_TYPES_OFFSETS { 430 BEGIN_DATA_BITS_OFFSET = 0, 431 BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 432 BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 433 BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK 434}; 435 436/* The following defines provide numerous constants used to distinguish between 437 different types of speculative dependencies. */ 438 439/* Dependence can be overcome with generation of new data speculative 440 instruction. */ 441#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET) 442 443/* This dependence is to the instruction in the recovery block, that was 444 formed to recover after data-speculation failure. 445 Thus, this dependence can overcome with generating of the copy of 446 this instruction in the recovery block. */ 447#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET) 448 449/* Dependence can be overcome with generation of new control speculative 450 instruction. */ 451#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET) 452 453/* This dependence is to the instruction in the recovery block, that was 454 formed to recover after control-speculation failure. 455 Thus, this dependence can be overcome with generating of the copy of 456 this instruction in the recovery block. */ 457#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET) 458 459/* A few convenient combinations. */ 460#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL) 461#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA) 462#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL) 463#define SPECULATIVE (DATA_SPEC | CONTROL_SPEC) 464#define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL) 465 466/* Constants, that are helpful in iterating through dep_status. */ 467#define FIRST_SPEC_TYPE BEGIN_DATA 468#define LAST_SPEC_TYPE BE_IN_CONTROL 469#define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK 470 471/* Dependence on instruction can be of multiple types 472 (e.g. true and output). This fields enhance REG_NOTE_KIND information 473 of the dependence. */ 474#define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK)) 475#define DEP_OUTPUT (DEP_TRUE << 1) 476#define DEP_ANTI (DEP_OUTPUT << 1) 477 478#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI) 479 480/* Instruction has non-speculative dependence. This bit represents the 481 property of an instruction - not the one of a dependence. 482 Therefore, it can appear only in TODO_SPEC field of an instruction. */ 483#define HARD_DEP (DEP_ANTI << 1) 484 485/* This represents the results of calling sched-deps.c functions, 486 which modify dependencies. Possible choices are: a dependence 487 is already present and nothing has been changed; a dependence type 488 has been changed; brand new dependence has been created. */ 489enum DEPS_ADJUST_RESULT { 490 DEP_PRESENT = 1, 491 DEP_CHANGED = 2, 492 DEP_CREATED = 3 493}; 494 495/* Represents the bits that can be set in the flags field of the 496 sched_info structure. */ 497enum SCHED_FLAGS { 498 /* If set, generate links between instruction as DEPS_LIST. 499 Otherwise, generate usual INSN_LIST links. */ 500 USE_DEPS_LIST = 1, 501 /* Perform data or control (or both) speculation. 502 Results in generation of data and control speculative dependencies. 503 Requires USE_DEPS_LIST set. */ 504 DO_SPECULATION = USE_DEPS_LIST << 1, 505 SCHED_RGN = DO_SPECULATION << 1, 506 SCHED_EBB = SCHED_RGN << 1, 507 /* Detach register live information from basic block headers. 508 This is necessary to invoke functions, that change CFG (e.g. split_edge). 509 Requires USE_GLAT. */ 510 DETACH_LIFE_INFO = SCHED_EBB << 1, 511 /* Save register live information from basic block headers to 512 glat_{start, end} arrays. */ 513 USE_GLAT = DETACH_LIFE_INFO << 1 514}; 515 516enum SPEC_SCHED_FLAGS { 517 COUNT_SPEC_IN_CRITICAL_PATH = 1, 518 PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1, 519 PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1 520}; 521 522#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE) \ 523 != NOTE_INSN_BASIC_BLOCK)) 524 525extern FILE *sched_dump; 526extern int sched_verbose; 527 528/* Exception Free Loads: 529 530 We define five classes of speculative loads: IFREE, IRISKY, 531 PFREE, PRISKY, and MFREE. 532 533 IFREE loads are loads that are proved to be exception-free, just 534 by examining the load insn. Examples for such loads are loads 535 from TOC and loads of global data. 536 537 IRISKY loads are loads that are proved to be exception-risky, 538 just by examining the load insn. Examples for such loads are 539 volatile loads and loads from shared memory. 540 541 PFREE loads are loads for which we can prove, by examining other 542 insns, that they are exception-free. Currently, this class consists 543 of loads for which we are able to find a "similar load", either in 544 the target block, or, if only one split-block exists, in that split 545 block. Load2 is similar to load1 if both have same single base 546 register. We identify only part of the similar loads, by finding 547 an insn upon which both load1 and load2 have a DEF-USE dependence. 548 549 PRISKY loads are loads for which we can prove, by examining other 550 insns, that they are exception-risky. Currently we have two proofs for 551 such loads. The first proof detects loads that are probably guarded by a 552 test on the memory address. This proof is based on the 553 backward and forward data dependence information for the region. 554 Let load-insn be the examined load. 555 Load-insn is PRISKY iff ALL the following hold: 556 557 - insn1 is not in the same block as load-insn 558 - there is a DEF-USE dependence chain (insn1, ..., load-insn) 559 - test-insn is either a compare or a branch, not in the same block 560 as load-insn 561 - load-insn is reachable from test-insn 562 - there is a DEF-USE dependence chain (insn1, ..., test-insn) 563 564 This proof might fail when the compare and the load are fed 565 by an insn not in the region. To solve this, we will add to this 566 group all loads that have no input DEF-USE dependence. 567 568 The second proof detects loads that are directly or indirectly 569 fed by a speculative load. This proof is affected by the 570 scheduling process. We will use the flag fed_by_spec_load. 571 Initially, all insns have this flag reset. After a speculative 572 motion of an insn, if insn is either a load, or marked as 573 fed_by_spec_load, we will also mark as fed_by_spec_load every 574 insn1 for which a DEF-USE dependence (insn, insn1) exists. A 575 load which is fed_by_spec_load is also PRISKY. 576 577 MFREE (maybe-free) loads are all the remaining loads. They may be 578 exception-free, but we cannot prove it. 579 580 Now, all loads in IFREE and PFREE classes are considered 581 exception-free, while all loads in IRISKY and PRISKY classes are 582 considered exception-risky. As for loads in the MFREE class, 583 these are considered either exception-free or exception-risky, 584 depending on whether we are pessimistic or optimistic. We have 585 to take the pessimistic approach to assure the safety of 586 speculative scheduling, but we can take the optimistic approach 587 by invoking the -fsched_spec_load_dangerous option. */ 588 589enum INSN_TRAP_CLASS 590{ 591 TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2, 592 PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5 593}; 594 595#define WORST_CLASS(class1, class2) \ 596((class1 > class2) ? class1 : class2) 597 598#ifndef __GNUC__ 599#define __inline 600#endif 601 602#ifndef HAIFA_INLINE 603#define HAIFA_INLINE __inline 604#endif 605 606/* Functions in sched-vis.c. */ 607extern void print_insn (char *, rtx, int); 608 609/* Functions in sched-deps.c. */ 610extern bool sched_insns_conditions_mutex_p (rtx, rtx); 611extern void add_dependence (rtx, rtx, enum reg_note); 612extern void sched_analyze (struct deps *, rtx, rtx); 613extern void init_deps (struct deps *); 614extern void free_deps (struct deps *); 615extern void init_deps_global (void); 616extern void finish_deps_global (void); 617extern void add_forw_dep (rtx, rtx); 618extern void compute_forward_dependences (rtx, rtx); 619extern rtx find_insn_list (rtx, rtx); 620extern void init_dependency_caches (int); 621extern void free_dependency_caches (void); 622extern void extend_dependency_caches (int, bool); 623extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx, 624 enum reg_note, ds_t); 625extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t); 626extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t); 627extern void delete_back_forw_dep (rtx, rtx); 628extern dw_t get_dep_weak (ds_t, ds_t); 629extern ds_t set_dep_weak (ds_t, ds_t, dw_t); 630extern ds_t ds_merge (ds_t, ds_t); 631 632/* Functions in haifa-sched.c. */ 633extern int haifa_classify_insn (rtx); 634extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *); 635extern int no_real_insns_p (rtx, rtx); 636 637extern void rm_line_notes (rtx, rtx); 638extern void save_line_notes (int, rtx, rtx); 639extern void restore_line_notes (rtx, rtx); 640extern void rm_redundant_line_notes (void); 641extern void rm_other_notes (rtx, rtx); 642 643extern int insn_cost (rtx, rtx, rtx); 644extern int set_priorities (rtx, rtx); 645 646extern void schedule_block (basic_block *, int); 647extern void sched_init (void); 648extern void sched_finish (void); 649 650extern int try_ready (rtx); 651extern void * xrecalloc (void *, size_t, size_t, size_t); 652extern void unlink_bb_notes (basic_block, basic_block); 653extern void add_block (basic_block, basic_block); 654extern void attach_life_info (void); 655extern rtx bb_note (basic_block); 656 657#ifdef ENABLE_CHECKING 658extern void check_reg_live (bool); 659#endif 660 661#endif /* GCC_SCHED_INT_H */ 662