190075Sobrien/* Instruction scheduling pass. This file contains definitions used 290075Sobrien internally in the scheduler. 390075Sobrien Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4169689Skan 1999, 2000, 2001, 2003, 2004, 2005, 2006 Free Software Foundation, Inc. 590075Sobrien 690075SobrienThis file is part of GCC. 790075Sobrien 890075SobrienGCC is free software; you can redistribute it and/or modify it under 990075Sobrienthe terms of the GNU General Public License as published by the Free 1090075SobrienSoftware Foundation; either version 2, or (at your option) any later 1190075Sobrienversion. 1290075Sobrien 1390075SobrienGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1490075SobrienWARRANTY; without even the implied warranty of MERCHANTABILITY or 1590075SobrienFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1690075Sobrienfor more details. 1790075Sobrien 1890075SobrienYou should have received a copy of the GNU General Public License 1990075Sobrienalong with GCC; see the file COPYING. If not, write to the Free 20169689SkanSoftware Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 21169689Skan02110-1301, USA. */ 2290075Sobrien 23169689Skan#ifndef GCC_SCHED_INT_H 24169689Skan#define GCC_SCHED_INT_H 25169689Skan 26169689Skan/* For state_t. */ 27169689Skan#include "insn-attr.h" 28169689Skan/* For regset_head. */ 29169689Skan#include "basic-block.h" 30169689Skan/* For reg_note. */ 31169689Skan#include "rtl.h" 32169689Skan 33117395Skan/* Pointer to data describing the current DFA state. */ 34117395Skanextern state_t curr_state; 35117395Skan 3690075Sobrien/* Forward declaration. */ 3790075Sobrienstruct ready_list; 3890075Sobrien 39169689Skan/* Type to represent status of a dependence. */ 40169689Skantypedef int ds_t; 41169689Skan 42169689Skan/* Type to represent weakness of speculative dependence. */ 43169689Skantypedef int dw_t; 44169689Skan 4590075Sobrien/* Describe state of dependencies used during sched_analyze phase. */ 4690075Sobrienstruct deps 4790075Sobrien{ 4890075Sobrien /* The *_insns and *_mems are paired lists. Each pending memory operation 4990075Sobrien will have a pointer to the MEM rtx on one list and a pointer to the 5090075Sobrien containing insn on the other list in the same place in the list. */ 5190075Sobrien 5290075Sobrien /* We can't use add_dependence like the old code did, because a single insn 5390075Sobrien may have multiple memory accesses, and hence needs to be on the list 5490075Sobrien once for each memory access. Add_dependence won't let you add an insn 5590075Sobrien to a list more than once. */ 5690075Sobrien 5790075Sobrien /* An INSN_LIST containing all insns with pending read operations. */ 5890075Sobrien rtx pending_read_insns; 5990075Sobrien 6090075Sobrien /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 6190075Sobrien rtx pending_read_mems; 6290075Sobrien 6390075Sobrien /* An INSN_LIST containing all insns with pending write operations. */ 6490075Sobrien rtx pending_write_insns; 6590075Sobrien 6690075Sobrien /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 6790075Sobrien rtx pending_write_mems; 6890075Sobrien 6990075Sobrien /* Indicates the combined length of the two pending lists. We must prevent 7090075Sobrien these lists from ever growing too large since the number of dependencies 7190075Sobrien produced is at least O(N*N), and execution time is at least O(4*N*N), as 7290075Sobrien a function of the length of these pending lists. */ 7390075Sobrien int pending_lists_length; 7490075Sobrien 7590075Sobrien /* Length of the pending memory flush list. Large functions with no 7690075Sobrien calls may build up extremely large lists. */ 7790075Sobrien int pending_flush_length; 7890075Sobrien 7990075Sobrien /* The last insn upon which all memory references must depend. 8090075Sobrien This is an insn which flushed the pending lists, creating a dependency 8190075Sobrien between it and all previously pending memory references. This creates 8290075Sobrien a barrier (or a checkpoint) which no memory reference is allowed to cross. 8390075Sobrien 8490075Sobrien This includes all non constant CALL_INSNs. When we do interprocedural 8590075Sobrien alias analysis, this restriction can be relaxed. 8690075Sobrien This may also be an INSN that writes memory if the pending lists grow 8790075Sobrien too large. */ 8890075Sobrien rtx last_pending_memory_flush; 8990075Sobrien 9090075Sobrien /* A list of the last function calls we have seen. We use a list to 9190075Sobrien represent last function calls from multiple predecessor blocks. 9290075Sobrien Used to prevent register lifetimes from expanding unnecessarily. */ 9390075Sobrien rtx last_function_call; 9490075Sobrien 9590075Sobrien /* A list of insns which use a pseudo register that does not already 9690075Sobrien cross a call. We create dependencies between each of those insn 9790075Sobrien and the next call insn, to ensure that they won't cross a call after 9890075Sobrien scheduling is done. */ 9990075Sobrien rtx sched_before_next_call; 10090075Sobrien 101132718Skan /* Used to keep post-call pseudo/hard reg movements together with 10290075Sobrien the call. */ 103169689Skan enum { not_post_call, post_call, post_call_initial } in_post_call_group_p; 10490075Sobrien 105102780Skan /* Set to the tail insn of the outermost libcall block. 106102780Skan 107102780Skan When nonzero, we will mark each insn processed by sched_analyze_insn 108102780Skan with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */ 109102780Skan rtx libcall_block_tail_insn; 110102780Skan 11190075Sobrien /* The maximum register number for the following arrays. Before reload 11290075Sobrien this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 11390075Sobrien int max_reg; 11490075Sobrien 11590075Sobrien /* Element N is the next insn that sets (hard or pseudo) register 11690075Sobrien N within the current basic block; or zero, if there is no 11790075Sobrien such insn. Needed for new registers which may be introduced 11890075Sobrien by splitting insns. */ 11990075Sobrien struct deps_reg 12090075Sobrien { 12190075Sobrien rtx uses; 12290075Sobrien rtx sets; 12390075Sobrien rtx clobbers; 12490075Sobrien int uses_length; 12590075Sobrien int clobbers_length; 12690075Sobrien } *reg_last; 12790075Sobrien 128117395Skan /* Element N is set for each register that has any nonzero element 12990075Sobrien in reg_last[N].{uses,sets,clobbers}. */ 13090075Sobrien regset_head reg_last_in_use; 131119256Skan 132119256Skan /* Element N is set for each register that is conditionally set. */ 133119256Skan regset_head reg_conditional_sets; 13490075Sobrien}; 13590075Sobrien 13690075Sobrien/* This structure holds some state of the current scheduling pass, and 13790075Sobrien contains some function pointers that abstract out some of the non-generic 13890075Sobrien functionality from functions such as schedule_block or schedule_insn. 13990075Sobrien There is one global variable, current_sched_info, which points to the 14090075Sobrien sched_info structure currently in use. */ 14190075Sobrienstruct sched_info 14290075Sobrien{ 14390075Sobrien /* Add all insns that are initially ready to the ready list. Called once 14490075Sobrien before scheduling a set of insns. */ 145169689Skan void (*init_ready_list) (void); 14690075Sobrien /* Called after taking an insn from the ready list. Returns nonzero if 14790075Sobrien this insn can be scheduled, nonzero if we should silently discard it. */ 148132718Skan int (*can_schedule_ready_p) (rtx); 14990075Sobrien /* Return nonzero if there are more insns that should be scheduled. */ 150132718Skan int (*schedule_more_p) (void); 151169689Skan /* Called after an insn has all its hard dependencies resolved. 152169689Skan Adjusts status of instruction (which is passed through second parameter) 153169689Skan to indicate if instruction should be moved to the ready list or the 154169689Skan queue, or if it should silently discard it (until next resolved 155169689Skan dependence). */ 156169689Skan ds_t (*new_ready) (rtx, ds_t); 15790075Sobrien /* Compare priority of two insns. Return a positive number if the second 15890075Sobrien insn is to be preferred for scheduling, and a negative one if the first 15990075Sobrien is to be preferred. Zero if they are equally good. */ 160132718Skan int (*rank) (rtx, rtx); 16190075Sobrien /* Return a string that contains the insn uid and optionally anything else 16290075Sobrien necessary to identify this insn in an output. It's valid to use a 16390075Sobrien static buffer for this. The ALIGNED parameter should cause the string 16490075Sobrien to be formatted so that multiple output lines will line up nicely. */ 165132718Skan const char *(*print_insn) (rtx, int); 16690075Sobrien /* Return nonzero if an insn should be included in priority 16790075Sobrien calculations. */ 168132718Skan int (*contributes_to_priority) (rtx, rtx); 16990075Sobrien /* Called when computing dependencies for a JUMP_INSN. This function 170132718Skan should store the set of registers that must be considered as set by 171132718Skan the jump in the regset. */ 172132718Skan void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset); 17390075Sobrien 17490075Sobrien /* The boundaries of the set of insns to be scheduled. */ 17590075Sobrien rtx prev_head, next_tail; 17690075Sobrien 17790075Sobrien /* Filled in after the schedule is finished; the first and last scheduled 17890075Sobrien insns. */ 17990075Sobrien rtx head, tail; 18090075Sobrien 18190075Sobrien /* If nonzero, enables an additional sanity check in schedule_block. */ 18290075Sobrien unsigned int queue_must_finish_empty:1; 18390075Sobrien /* Nonzero if we should use cselib for better alias analysis. This 18490075Sobrien must be 0 if the dependency information is used after sched_analyze 18590075Sobrien has completed, e.g. if we're using it to initialize state for successor 18690075Sobrien blocks in region scheduling. */ 18790075Sobrien unsigned int use_cselib:1; 188132718Skan 189132718Skan /* Maximum priority that has been assigned to an insn. */ 190132718Skan int sched_max_insns_priority; 191169689Skan 192169689Skan /* Hooks to support speculative scheduling. */ 193169689Skan 194169689Skan /* Called to notify frontend that instruction is being added (second 195169689Skan parameter == 0) or removed (second parameter == 1). */ 196169689Skan void (*add_remove_insn) (rtx, int); 197169689Skan 198169689Skan /* Called to notify frontend that instruction is being scheduled. 199169689Skan The first parameter - instruction to scheduled, the second parameter - 200169689Skan last scheduled instruction. */ 201169689Skan void (*begin_schedule_ready) (rtx, rtx); 202169689Skan 203169689Skan /* Called to notify frontend, that new basic block is being added. 204169689Skan The first parameter - new basic block. 205169689Skan The second parameter - block, after which new basic block is being added, 206169689Skan or EXIT_BLOCK_PTR, if recovery block is being added, 207169689Skan or NULL, if standalone block is being added. */ 208169689Skan void (*add_block) (basic_block, basic_block); 209169689Skan 210169689Skan /* If the second parameter is not NULL, return nonnull value, if the 211169689Skan basic block should be advanced. 212169689Skan If the second parameter is NULL, return the next basic block in EBB. 213169689Skan The first parameter is the current basic block in EBB. */ 214169689Skan basic_block (*advance_target_bb) (basic_block, rtx); 215169689Skan 216169689Skan /* Called after blocks were rearranged due to movement of jump instruction. 217169689Skan The first parameter - index of basic block, in which jump currently is. 218169689Skan The second parameter - index of basic block, in which jump used 219169689Skan to be. 220169689Skan The third parameter - index of basic block, that follows the second 221169689Skan parameter. */ 222169689Skan void (*fix_recovery_cfg) (int, int, int); 223169689Skan 224169689Skan#ifdef ENABLE_CHECKING 225169689Skan /* If the second parameter is zero, return nonzero, if block is head of the 226169689Skan region. 227169689Skan If the second parameter is nonzero, return nonzero, if block is leaf of 228169689Skan the region. 229169689Skan global_live_at_start should not change in region heads and 230169689Skan global_live_at_end should not change in region leafs due to scheduling. */ 231169689Skan int (*region_head_or_leaf_p) (basic_block, int); 232169689Skan#endif 233169689Skan 234169689Skan /* ??? FIXME: should use straight bitfields inside sched_info instead of 235169689Skan this flag field. */ 236169689Skan unsigned int flags; 23790075Sobrien}; 23890075Sobrien 239169689Skan/* This structure holds description of the properties for speculative 240169689Skan scheduling. */ 241169689Skanstruct spec_info_def 242169689Skan{ 243169689Skan /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL}, 244169689Skan BE_IN_{DATA_CONTROL}. */ 245169689Skan int mask; 246169689Skan 247169689Skan /* A dump file for additional information on speculative scheduling. */ 248169689Skan FILE *dump; 249169689Skan 250169689Skan /* Minimal cumulative weakness of speculative instruction's 251169689Skan dependencies, so that insn will be scheduled. */ 252169689Skan dw_t weakness_cutoff; 253169689Skan 254169689Skan /* Flags from the enum SPEC_SCHED_FLAGS. */ 255169689Skan int flags; 256169689Skan}; 257169689Skantypedef struct spec_info_def *spec_info_t; 258169689Skan 25990075Sobrienextern struct sched_info *current_sched_info; 26090075Sobrien 26190075Sobrien/* Indexed by INSN_UID, the collection of all data associated with 26290075Sobrien a single instruction. */ 26390075Sobrien 26490075Sobrienstruct haifa_insn_data 26590075Sobrien{ 26690075Sobrien /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 26790075Sobrien it represents forward dependencies. */ 26890075Sobrien rtx depend; 26990075Sobrien 270169689Skan /* A list of scheduled producers of the instruction. Links are being moved 271169689Skan from LOG_LINKS to RESOLVED_DEPS during scheduling. */ 272169689Skan rtx resolved_deps; 273169689Skan 27490075Sobrien /* The line number note in effect for each insn. For line number 27590075Sobrien notes, this indicates whether the note may be reused. */ 27690075Sobrien rtx line_note; 27790075Sobrien 27890075Sobrien /* Logical uid gives the original ordering of the insns. */ 27990075Sobrien int luid; 28090075Sobrien 28190075Sobrien /* A priority for each insn. */ 28290075Sobrien int priority; 28390075Sobrien 28490075Sobrien /* The number of incoming edges in the forward dependency graph. 285132718Skan As scheduling proceeds, counts are decreased. An insn moves to 28690075Sobrien the ready queue when its counter reaches zero. */ 28790075Sobrien int dep_count; 28890075Sobrien 28990075Sobrien /* Number of instructions referring to this insn. */ 29090075Sobrien int ref_count; 29190075Sobrien 29290075Sobrien /* The minimum clock tick at which the insn becomes ready. This is 29390075Sobrien used to note timing constraints for the insns in the pending list. */ 29490075Sobrien int tick; 29590075Sobrien 296169689Skan /* INTER_TICK is used to adjust INSN_TICKs of instructions from the 297169689Skan subsequent blocks in a region. */ 298169689Skan int inter_tick; 299169689Skan 300169689Skan /* See comment on QUEUE_INDEX macro in haifa-sched.c. */ 301169689Skan int queue_index; 302169689Skan 30390075Sobrien short cost; 30490075Sobrien 30590075Sobrien /* This weight is an estimation of the insn's contribution to 30690075Sobrien register pressure. */ 30790075Sobrien short reg_weight; 30890075Sobrien 30990075Sobrien /* Some insns (e.g. call) are not allowed to move across blocks. */ 31090075Sobrien unsigned int cant_move : 1; 31190075Sobrien 31290075Sobrien /* Set if there's DEF-USE dependence between some speculatively 31390075Sobrien moved load insn and this one. */ 31490075Sobrien unsigned int fed_by_spec_load : 1; 31590075Sobrien unsigned int is_load_insn : 1; 31690075Sobrien 31790075Sobrien /* Nonzero if priority has been computed already. */ 31890075Sobrien unsigned int priority_known : 1; 319169689Skan 320169689Skan /* Nonzero if instruction has internal dependence 321169689Skan (e.g. add_dependence was invoked with (insn == elem)). */ 322169689Skan unsigned int has_internal_dep : 1; 323169689Skan 324169689Skan /* What speculations are necessary to apply to schedule the instruction. */ 325169689Skan ds_t todo_spec; 326169689Skan /* What speculations were already applied. */ 327169689Skan ds_t done_spec; 328169689Skan /* What speculations are checked by this instruction. */ 329169689Skan ds_t check_spec; 330169689Skan 331169689Skan /* Recovery block for speculation checks. */ 332169689Skan basic_block recovery_block; 333169689Skan 334169689Skan /* Original pattern of the instruction. */ 335169689Skan rtx orig_pat; 33690075Sobrien}; 33790075Sobrien 33890075Sobrienextern struct haifa_insn_data *h_i_d; 339169689Skan/* Used only if (current_sched_info->flags & USE_GLAT) != 0. 340169689Skan These regsets store global_live_at_{start, end} information 341169689Skan for each basic block. */ 342169689Skanextern regset *glat_start, *glat_end; 34390075Sobrien 34490075Sobrien/* Accessor macros for h_i_d. There are more in haifa-sched.c and 34590075Sobrien sched-rgn.c. */ 34690075Sobrien#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 347169689Skan#define RESOLVED_DEPS(INSN) (h_i_d[INSN_UID (INSN)].resolved_deps) 34890075Sobrien#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 34990075Sobrien#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 35090075Sobrien#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 35190075Sobrien#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 35290075Sobrien#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 35390075Sobrien#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 35490075Sobrien#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 355169689Skan#define HAS_INTERNAL_DEP(INSN) (h_i_d[INSN_UID (INSN)].has_internal_dep) 356169689Skan#define TODO_SPEC(INSN) (h_i_d[INSN_UID (INSN)].todo_spec) 357169689Skan#define DONE_SPEC(INSN) (h_i_d[INSN_UID (INSN)].done_spec) 358169689Skan#define CHECK_SPEC(INSN) (h_i_d[INSN_UID (INSN)].check_spec) 359169689Skan#define RECOVERY_BLOCK(INSN) (h_i_d[INSN_UID (INSN)].recovery_block) 360169689Skan#define ORIG_PAT(INSN) (h_i_d[INSN_UID (INSN)].orig_pat) 36190075Sobrien 362169689Skan/* INSN is either a simple or a branchy speculation check. */ 363169689Skan#define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL) 36490075Sobrien 365169689Skan/* INSN is a speculation check that will simply reexecute the speculatively 366169689Skan scheduled instruction if the speculation fails. */ 367169689Skan#define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \ 368169689Skan (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR) 36990075Sobrien 370169689Skan/* INSN is a speculation check that will branch to RECOVERY_BLOCK if the 371169689Skan speculation fails. Insns in that block will reexecute the speculatively 372169689Skan scheduled code and then will return immediately after INSN thus preserving 373169689Skan semantics of the program. */ 374169689Skan#define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \ 375169689Skan (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR) 376169689Skan 377169689Skan/* DEP_STATUS of the link encapsulates information, that is needed for 378169689Skan speculative scheduling. Namely, it is 4 integers in the range 379169689Skan [0, MAX_DEP_WEAK] and 3 bits. 380169689Skan The integers correspond to the probability of the dependence to *not* 381169689Skan exist, it is the probability, that overcoming of this dependence will 382169689Skan not be followed by execution of the recovery code. Nevertheless, 383169689Skan whatever high the probability of success is, recovery code should still 384169689Skan be generated to preserve semantics of the program. To find a way to 385169689Skan get/set these integers, please refer to the {get, set}_dep_weak () 386169689Skan functions in sched-deps.c . 387169689Skan The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-, 388169689Skan output- and anti- dependence. It is not enough for speculative scheduling 389169689Skan to know just the major type of all the dependence between two instructions, 390169689Skan as only true dependence can be overcome. 391169689Skan There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved 392169689Skan for using to describe instruction's status. It is set whenever instruction 393169689Skan has at least one dependence, that cannot be overcome. 394169689Skan See also: check_dep_status () in sched-deps.c . */ 395169689Skan#define DEP_STATUS(LINK) XINT (LINK, 2) 396169689Skan 397169689Skan/* We exclude sign bit. */ 398169689Skan#define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1) 399169689Skan 400169689Skan/* First '4' stands for 3 dep type bits and HARD_DEP bit. 401169689Skan Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL} 402169689Skan dep weakness. */ 403169689Skan#define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4) 404169689Skan 405169689Skan/* Mask of speculative weakness in dep_status. */ 406169689Skan#define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1) 407169689Skan 408169689Skan/* This constant means that dependence is fake with 99.999...% probability. 409169689Skan This is the maximum value, that can appear in dep_status. 410169689Skan Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for 411169689Skan debugging reasons. Though, it can be set to DEP_WEAK_MASK, and, when 412169689Skan done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK. */ 413169689Skan#define MAX_DEP_WEAK (DEP_WEAK_MASK - 1) 414169689Skan 415169689Skan/* This constant means that dependence is 99.999...% real and it is a really 416169689Skan bad idea to overcome it (though this can be done, preserving program 417169689Skan semantics). */ 418169689Skan#define MIN_DEP_WEAK 1 419169689Skan 420169689Skan/* This constant represents 100% probability. 421169689Skan E.g. it is used to represent weakness of dependence, that doesn't exist. */ 422169689Skan#define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK) 423169689Skan 424169689Skan/* Default weakness of speculative dependence. Used when we can't say 425169689Skan neither bad nor good about the dependence. */ 426169689Skan#define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4) 427169689Skan 428169689Skan/* Offset for speculative weaknesses in dep_status. */ 429169689Skanenum SPEC_TYPES_OFFSETS { 430169689Skan BEGIN_DATA_BITS_OFFSET = 0, 431169689Skan BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 432169689Skan BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK, 433169689Skan BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK 434169689Skan}; 435169689Skan 436169689Skan/* The following defines provide numerous constants used to distinguish between 437169689Skan different types of speculative dependencies. */ 438169689Skan 439169689Skan/* Dependence can be overcome with generation of new data speculative 440169689Skan instruction. */ 441169689Skan#define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET) 442169689Skan 443169689Skan/* This dependence is to the instruction in the recovery block, that was 444169689Skan formed to recover after data-speculation failure. 445169689Skan Thus, this dependence can overcome with generating of the copy of 446169689Skan this instruction in the recovery block. */ 447169689Skan#define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET) 448169689Skan 449169689Skan/* Dependence can be overcome with generation of new control speculative 450169689Skan instruction. */ 451169689Skan#define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET) 452169689Skan 453169689Skan/* This dependence is to the instruction in the recovery block, that was 454169689Skan formed to recover after control-speculation failure. 455169689Skan Thus, this dependence can be overcome with generating of the copy of 456169689Skan this instruction in the recovery block. */ 457169689Skan#define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET) 458169689Skan 459169689Skan/* A few convenient combinations. */ 460169689Skan#define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL) 461169689Skan#define DATA_SPEC (BEGIN_DATA | BE_IN_DATA) 462169689Skan#define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL) 463169689Skan#define SPECULATIVE (DATA_SPEC | CONTROL_SPEC) 464169689Skan#define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL) 465169689Skan 466169689Skan/* Constants, that are helpful in iterating through dep_status. */ 467169689Skan#define FIRST_SPEC_TYPE BEGIN_DATA 468169689Skan#define LAST_SPEC_TYPE BE_IN_CONTROL 469169689Skan#define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK 470169689Skan 471169689Skan/* Dependence on instruction can be of multiple types 472169689Skan (e.g. true and output). This fields enhance REG_NOTE_KIND information 473169689Skan of the dependence. */ 474169689Skan#define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK)) 475169689Skan#define DEP_OUTPUT (DEP_TRUE << 1) 476169689Skan#define DEP_ANTI (DEP_OUTPUT << 1) 477169689Skan 478169689Skan#define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI) 479169689Skan 480169689Skan/* Instruction has non-speculative dependence. This bit represents the 481169689Skan property of an instruction - not the one of a dependence. 482169689Skan Therefore, it can appear only in TODO_SPEC field of an instruction. */ 483169689Skan#define HARD_DEP (DEP_ANTI << 1) 484169689Skan 485169689Skan/* This represents the results of calling sched-deps.c functions, 486169689Skan which modify dependencies. Possible choices are: a dependence 487169689Skan is already present and nothing has been changed; a dependence type 488169689Skan has been changed; brand new dependence has been created. */ 489169689Skanenum DEPS_ADJUST_RESULT { 490169689Skan DEP_PRESENT = 1, 491169689Skan DEP_CHANGED = 2, 492169689Skan DEP_CREATED = 3 493169689Skan}; 494169689Skan 495169689Skan/* Represents the bits that can be set in the flags field of the 496169689Skan sched_info structure. */ 497169689Skanenum SCHED_FLAGS { 498169689Skan /* If set, generate links between instruction as DEPS_LIST. 499169689Skan Otherwise, generate usual INSN_LIST links. */ 500169689Skan USE_DEPS_LIST = 1, 501169689Skan /* Perform data or control (or both) speculation. 502169689Skan Results in generation of data and control speculative dependencies. 503169689Skan Requires USE_DEPS_LIST set. */ 504169689Skan DO_SPECULATION = USE_DEPS_LIST << 1, 505169689Skan SCHED_RGN = DO_SPECULATION << 1, 506169689Skan SCHED_EBB = SCHED_RGN << 1, 507169689Skan /* Detach register live information from basic block headers. 508169689Skan This is necessary to invoke functions, that change CFG (e.g. split_edge). 509169689Skan Requires USE_GLAT. */ 510169689Skan DETACH_LIFE_INFO = SCHED_EBB << 1, 511169689Skan /* Save register live information from basic block headers to 512169689Skan glat_{start, end} arrays. */ 513169689Skan USE_GLAT = DETACH_LIFE_INFO << 1 514169689Skan}; 515169689Skan 516169689Skanenum SPEC_SCHED_FLAGS { 517169689Skan COUNT_SPEC_IN_CRITICAL_PATH = 1, 518169689Skan PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1, 519169689Skan PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1 520169689Skan}; 521169689Skan 522169689Skan#define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE) \ 523169689Skan != NOTE_INSN_BASIC_BLOCK)) 524169689Skan 52590075Sobrienextern FILE *sched_dump; 52690075Sobrienextern int sched_verbose; 52790075Sobrien 528132718Skan/* Exception Free Loads: 529132718Skan 530132718Skan We define five classes of speculative loads: IFREE, IRISKY, 531132718Skan PFREE, PRISKY, and MFREE. 532132718Skan 533132718Skan IFREE loads are loads that are proved to be exception-free, just 534132718Skan by examining the load insn. Examples for such loads are loads 535132718Skan from TOC and loads of global data. 536132718Skan 537132718Skan IRISKY loads are loads that are proved to be exception-risky, 538132718Skan just by examining the load insn. Examples for such loads are 539132718Skan volatile loads and loads from shared memory. 540132718Skan 541132718Skan PFREE loads are loads for which we can prove, by examining other 542132718Skan insns, that they are exception-free. Currently, this class consists 543132718Skan of loads for which we are able to find a "similar load", either in 544132718Skan the target block, or, if only one split-block exists, in that split 545132718Skan block. Load2 is similar to load1 if both have same single base 546132718Skan register. We identify only part of the similar loads, by finding 547132718Skan an insn upon which both load1 and load2 have a DEF-USE dependence. 548132718Skan 549132718Skan PRISKY loads are loads for which we can prove, by examining other 550132718Skan insns, that they are exception-risky. Currently we have two proofs for 551132718Skan such loads. The first proof detects loads that are probably guarded by a 552132718Skan test on the memory address. This proof is based on the 553132718Skan backward and forward data dependence information for the region. 554132718Skan Let load-insn be the examined load. 555132718Skan Load-insn is PRISKY iff ALL the following hold: 556132718Skan 557132718Skan - insn1 is not in the same block as load-insn 558132718Skan - there is a DEF-USE dependence chain (insn1, ..., load-insn) 559132718Skan - test-insn is either a compare or a branch, not in the same block 560132718Skan as load-insn 561132718Skan - load-insn is reachable from test-insn 562132718Skan - there is a DEF-USE dependence chain (insn1, ..., test-insn) 563132718Skan 564132718Skan This proof might fail when the compare and the load are fed 565132718Skan by an insn not in the region. To solve this, we will add to this 566132718Skan group all loads that have no input DEF-USE dependence. 567132718Skan 568132718Skan The second proof detects loads that are directly or indirectly 569132718Skan fed by a speculative load. This proof is affected by the 570132718Skan scheduling process. We will use the flag fed_by_spec_load. 571132718Skan Initially, all insns have this flag reset. After a speculative 572132718Skan motion of an insn, if insn is either a load, or marked as 573132718Skan fed_by_spec_load, we will also mark as fed_by_spec_load every 574132718Skan insn1 for which a DEF-USE dependence (insn, insn1) exists. A 575132718Skan load which is fed_by_spec_load is also PRISKY. 576132718Skan 577132718Skan MFREE (maybe-free) loads are all the remaining loads. They may be 578132718Skan exception-free, but we cannot prove it. 579132718Skan 580132718Skan Now, all loads in IFREE and PFREE classes are considered 581132718Skan exception-free, while all loads in IRISKY and PRISKY classes are 582132718Skan considered exception-risky. As for loads in the MFREE class, 583132718Skan these are considered either exception-free or exception-risky, 584132718Skan depending on whether we are pessimistic or optimistic. We have 585132718Skan to take the pessimistic approach to assure the safety of 586132718Skan speculative scheduling, but we can take the optimistic approach 587132718Skan by invoking the -fsched_spec_load_dangerous option. */ 588132718Skan 589132718Skanenum INSN_TRAP_CLASS 590132718Skan{ 591132718Skan TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2, 592132718Skan PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5 593132718Skan}; 594132718Skan 595132718Skan#define WORST_CLASS(class1, class2) \ 596132718Skan((class1 > class2) ? class1 : class2) 597132718Skan 59890075Sobrien#ifndef __GNUC__ 59990075Sobrien#define __inline 60090075Sobrien#endif 60190075Sobrien 60290075Sobrien#ifndef HAIFA_INLINE 60390075Sobrien#define HAIFA_INLINE __inline 60490075Sobrien#endif 60590075Sobrien 60690075Sobrien/* Functions in sched-vis.c. */ 607169689Skanextern void print_insn (char *, rtx, int); 60890075Sobrien 60990075Sobrien/* Functions in sched-deps.c. */ 610169689Skanextern bool sched_insns_conditions_mutex_p (rtx, rtx); 611169689Skanextern void add_dependence (rtx, rtx, enum reg_note); 612132718Skanextern void sched_analyze (struct deps *, rtx, rtx); 613132718Skanextern void init_deps (struct deps *); 614132718Skanextern void free_deps (struct deps *); 615132718Skanextern void init_deps_global (void); 616132718Skanextern void finish_deps_global (void); 617169689Skanextern void add_forw_dep (rtx, rtx); 618132718Skanextern void compute_forward_dependences (rtx, rtx); 619132718Skanextern rtx find_insn_list (rtx, rtx); 620132718Skanextern void init_dependency_caches (int); 621132718Skanextern void free_dependency_caches (void); 622169689Skanextern void extend_dependency_caches (int, bool); 623169689Skanextern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx, 624169689Skan enum reg_note, ds_t); 625169689Skanextern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t); 626169689Skanextern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t); 627169689Skanextern void delete_back_forw_dep (rtx, rtx); 628169689Skanextern dw_t get_dep_weak (ds_t, ds_t); 629169689Skanextern ds_t set_dep_weak (ds_t, ds_t, dw_t); 630169689Skanextern ds_t ds_merge (ds_t, ds_t); 63190075Sobrien 63290075Sobrien/* Functions in haifa-sched.c. */ 633132718Skanextern int haifa_classify_insn (rtx); 634169689Skanextern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *); 635132718Skanextern int no_real_insns_p (rtx, rtx); 63690075Sobrien 637132718Skanextern void rm_line_notes (rtx, rtx); 638132718Skanextern void save_line_notes (int, rtx, rtx); 639132718Skanextern void restore_line_notes (rtx, rtx); 640132718Skanextern void rm_redundant_line_notes (void); 641132718Skanextern void rm_other_notes (rtx, rtx); 64290075Sobrien 643169689Skanextern int insn_cost (rtx, rtx, rtx); 644132718Skanextern int set_priorities (rtx, rtx); 64590075Sobrien 646169689Skanextern void schedule_block (basic_block *, int); 647169689Skanextern void sched_init (void); 648132718Skanextern void sched_finish (void); 64990075Sobrien 650169689Skanextern int try_ready (rtx); 651169689Skanextern void * xrecalloc (void *, size_t, size_t, size_t); 652169689Skanextern void unlink_bb_notes (basic_block, basic_block); 653169689Skanextern void add_block (basic_block, basic_block); 654169689Skanextern void attach_life_info (void); 655169689Skanextern rtx bb_note (basic_block); 65690075Sobrien 657169689Skan#ifdef ENABLE_CHECKING 658169689Skanextern void check_reg_live (bool); 659169689Skan#endif 660169689Skan 661169689Skan#endif /* GCC_SCHED_INT_H */ 662