sched-int.h revision 117395
1314125Sdelphij/* Instruction scheduling pass. This file contains definitions used 296593Smarkm internally in the scheduler. 396593Smarkm Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 4142429Snectar 1999, 2000, 2001 Free Software Foundation, Inc. 596593Smarkm 696593SmarkmThis file is part of GCC. 796593Smarkm 896593SmarkmGCC is free software; you can redistribute it and/or modify it under 996593Smarkmthe terms of the GNU General Public License as published by the Free 1096593SmarkmSoftware Foundation; either version 2, or (at your option) any later 1196593Smarkmversion. 1296593Smarkm 1396593SmarkmGCC is distributed in the hope that it will be useful, but WITHOUT ANY 1496593SmarkmWARRANTY; without even the implied warranty of MERCHANTABILITY or 1596593SmarkmFITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License 1696593Smarkmfor more details. 1796593Smarkm 1896593SmarkmYou should have received a copy of the GNU General Public License 1996593Smarkmalong with GCC; see the file COPYING. If not, write to the Free 20215698SsimonSoftware Foundation, 59 Temple Place - Suite 330, Boston, MA 21215698Ssimon02111-1307, USA. */ 22215698Ssimon 23215698Ssimon/* Pointer to data describing the current DFA state. */ 24215698Ssimonextern state_t curr_state; 2596593Smarkm 2696593Smarkm/* Forward declaration. */ 2796593Smarkmstruct ready_list; 2896593Smarkm 2996593Smarkm/* Describe state of dependencies used during sched_analyze phase. */ 3096593Smarkmstruct deps 3196593Smarkm{ 3296593Smarkm /* The *_insns and *_mems are paired lists. Each pending memory operation 3396593Smarkm will have a pointer to the MEM rtx on one list and a pointer to the 3496593Smarkm containing insn on the other list in the same place in the list. */ 3596593Smarkm 3696593Smarkm /* We can't use add_dependence like the old code did, because a single insn 3796593Smarkm may have multiple memory accesses, and hence needs to be on the list 3896593Smarkm once for each memory access. Add_dependence won't let you add an insn 3996593Smarkm to a list more than once. */ 4096593Smarkm 41276861Sjkim /* An INSN_LIST containing all insns with pending read operations. */ 42276861Sjkim rtx pending_read_insns; 4396593Smarkm 4496593Smarkm /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 45215698Ssimon rtx pending_read_mems; 46215698Ssimon 47215698Ssimon /* An INSN_LIST containing all insns with pending write operations. */ 48215698Ssimon rtx pending_write_insns; 49314125Sdelphij 50215698Ssimon /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 51142429Snectar rtx pending_write_mems; 52142429Snectar 53276861Sjkim /* Indicates the combined length of the two pending lists. We must prevent 54276861Sjkim these lists from ever growing too large since the number of dependencies 55276861Sjkim produced is at least O(N*N), and execution time is at least O(4*N*N), as 5696593Smarkm a function of the length of these pending lists. */ 57314125Sdelphij int pending_lists_length; 58314125Sdelphij 59314125Sdelphij /* Length of the pending memory flush list. Large functions with no 60314125Sdelphij calls may build up extremely large lists. */ 61215698Ssimon int pending_flush_length; 62314125Sdelphij 63314125Sdelphij /* The last insn upon which all memory references must depend. 64314125Sdelphij This is an insn which flushed the pending lists, creating a dependency 65276861Sjkim between it and all previously pending memory references. This creates 66215698Ssimon a barrier (or a checkpoint) which no memory reference is allowed to cross. 6796593Smarkm 6896593Smarkm This includes all non constant CALL_INSNs. When we do interprocedural 6996593Smarkm alias analysis, this restriction can be relaxed. 7096593Smarkm This may also be an INSN that writes memory if the pending lists grow 7196593Smarkm too large. */ 7296593Smarkm rtx last_pending_memory_flush; 7396593Smarkm 7496593Smarkm /* A list of the last function calls we have seen. We use a list to 7596593Smarkm represent last function calls from multiple predecessor blocks. 7696593Smarkm Used to prevent register lifetimes from expanding unnecessarily. */ 7796593Smarkm rtx last_function_call; 7896593Smarkm 7996593Smarkm /* A list of insns which use a pseudo register that does not already 8096593Smarkm cross a call. We create dependencies between each of those insn 8196593Smarkm and the next call insn, to ensure that they won't cross a call after 8296593Smarkm scheduling is done. */ 8396593Smarkm rtx sched_before_next_call; 8496593Smarkm 8596593Smarkm /* Used to keep post-call psuedo/hard reg movements together with 8696593Smarkm the call. */ 8796593Smarkm bool in_post_call_group_p; 8896593Smarkm 8996593Smarkm /* Set to the tail insn of the outermost libcall block. 9096593Smarkm 9196593Smarkm When nonzero, we will mark each insn processed by sched_analyze_insn 9296593Smarkm with SCHED_GROUP_P to ensure libcalls are scheduled as a unit. */ 9396593Smarkm rtx libcall_block_tail_insn; 9496593Smarkm 9596593Smarkm /* The maximum register number for the following arrays. Before reload 9696593Smarkm this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 9796593Smarkm int max_reg; 9896593Smarkm 9996593Smarkm /* Element N is the next insn that sets (hard or pseudo) register 10096593Smarkm N within the current basic block; or zero, if there is no 10196593Smarkm such insn. Needed for new registers which may be introduced 10296593Smarkm by splitting insns. */ 10396593Smarkm struct deps_reg 10496593Smarkm { 10596593Smarkm rtx uses; 10696593Smarkm rtx sets; 10796593Smarkm rtx clobbers; 10896593Smarkm int uses_length; 10996593Smarkm int clobbers_length; 11096593Smarkm } *reg_last; 11196593Smarkm 11296593Smarkm /* Element N is set for each register that has any nonzero element 11396593Smarkm in reg_last[N].{uses,sets,clobbers}. */ 11496593Smarkm regset_head reg_last_in_use; 11596593Smarkm}; 11696593Smarkm 11796593Smarkm/* This structure holds some state of the current scheduling pass, and 11896593Smarkm contains some function pointers that abstract out some of the non-generic 11996593Smarkm functionality from functions such as schedule_block or schedule_insn. 12096593Smarkm There is one global variable, current_sched_info, which points to the 12196593Smarkm sched_info structure currently in use. */ 12296593Smarkmstruct sched_info 12396593Smarkm{ 12496593Smarkm /* Add all insns that are initially ready to the ready list. Called once 12596593Smarkm before scheduling a set of insns. */ 12696593Smarkm void (*init_ready_list) PARAMS ((struct ready_list *)); 12796593Smarkm /* Called after taking an insn from the ready list. Returns nonzero if 12896593Smarkm this insn can be scheduled, nonzero if we should silently discard it. */ 129142429Snectar int (*can_schedule_ready_p) PARAMS ((rtx)); 13096593Smarkm /* Return nonzero if there are more insns that should be scheduled. */ 131100946Snectar int (*schedule_more_p) PARAMS ((void)); 132314125Sdelphij /* Called after an insn has all its dependencies resolved. Return nonzero 133215698Ssimon if it should be moved to the ready list or the queue, or zero if we 134215698Ssimon should silently discard it. */ 135215698Ssimon int (*new_ready) PARAMS ((rtx)); 136215698Ssimon /* Compare priority of two insns. Return a positive number if the second 13796593Smarkm insn is to be preferred for scheduling, and a negative one if the first 13896593Smarkm is to be preferred. Zero if they are equally good. */ 13996593Smarkm int (*rank) PARAMS ((rtx, rtx)); 14096593Smarkm /* Return a string that contains the insn uid and optionally anything else 14196593Smarkm necessary to identify this insn in an output. It's valid to use a 14296593Smarkm static buffer for this. The ALIGNED parameter should cause the string 14396593Smarkm to be formatted so that multiple output lines will line up nicely. */ 144215698Ssimon const char *(*print_insn) PARAMS ((rtx, int)); 14596593Smarkm /* Return nonzero if an insn should be included in priority 14696593Smarkm calculations. */ 147215698Ssimon int (*contributes_to_priority) PARAMS ((rtx, rtx)); 14896593Smarkm /* Called when computing dependencies for a JUMP_INSN. This function 149215698Ssimon should store the set of registers that must be considered as set by 15096593Smarkm the jump in the regset. */ 15196593Smarkm void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset)); 15296593Smarkm 15396593Smarkm /* The boundaries of the set of insns to be scheduled. */ 15496593Smarkm rtx prev_head, next_tail; 15596593Smarkm 15696593Smarkm /* Filled in after the schedule is finished; the first and last scheduled 15796593Smarkm insns. */ 15896593Smarkm rtx head, tail; 15996593Smarkm 16096593Smarkm /* If nonzero, enables an additional sanity check in schedule_block. */ 16196593Smarkm unsigned int queue_must_finish_empty:1; 16296593Smarkm /* Nonzero if we should use cselib for better alias analysis. This 16396593Smarkm must be 0 if the dependency information is used after sched_analyze 16496593Smarkm has completed, e.g. if we're using it to initialize state for successor 16596593Smarkm blocks in region scheduling. */ 16696593Smarkm unsigned int use_cselib:1; 16796593Smarkm}; 16896593Smarkm 169142429Snectarextern struct sched_info *current_sched_info; 17096593Smarkm 17196593Smarkm/* Indexed by INSN_UID, the collection of all data associated with 17296593Smarkm a single instruction. */ 17396593Smarkm 17496593Smarkmstruct haifa_insn_data 175{ 176 /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 177 it represents forward dependencies. */ 178 rtx depend; 179 180 /* The line number note in effect for each insn. For line number 181 notes, this indicates whether the note may be reused. */ 182 rtx line_note; 183 184 /* Logical uid gives the original ordering of the insns. */ 185 int luid; 186 187 /* A priority for each insn. */ 188 int priority; 189 190 /* The number of incoming edges in the forward dependency graph. 191 As scheduling proceds, counts are decreased. An insn moves to 192 the ready queue when its counter reaches zero. */ 193 int dep_count; 194 195 /* An encoding of the blockage range function. Both unit and range 196 are coded. This member is used only for old pipeline interface. */ 197 unsigned int blockage; 198 199 /* Number of instructions referring to this insn. */ 200 int ref_count; 201 202 /* The minimum clock tick at which the insn becomes ready. This is 203 used to note timing constraints for the insns in the pending list. */ 204 int tick; 205 206 short cost; 207 208 /* An encoding of the function units used. This member is used only 209 for old pipeline interface. */ 210 short units; 211 212 /* This weight is an estimation of the insn's contribution to 213 register pressure. */ 214 short reg_weight; 215 216 /* Some insns (e.g. call) are not allowed to move across blocks. */ 217 unsigned int cant_move : 1; 218 219 /* Set if there's DEF-USE dependence between some speculatively 220 moved load insn and this one. */ 221 unsigned int fed_by_spec_load : 1; 222 unsigned int is_load_insn : 1; 223 224 /* Nonzero if priority has been computed already. */ 225 unsigned int priority_known : 1; 226}; 227 228extern struct haifa_insn_data *h_i_d; 229 230/* Accessor macros for h_i_d. There are more in haifa-sched.c and 231 sched-rgn.c. */ 232#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 233#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 234#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 235#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 236#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 237#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 238#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 239#define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) 240#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 241 242#define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) 243#define UNIT_BITS 5 244#define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) 245#define ENCODE_BLOCKAGE(U, R) \ 246 (((U) << BLOCKAGE_BITS \ 247 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ 248 | MAX_BLOCKAGE_COST (R)) 249#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) 250#define BLOCKAGE_RANGE(B) \ 251 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ 252 | ((B) & BLOCKAGE_MASK)) 253 254/* Encodings of the `<name>_unit_blockage_range' function. */ 255#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) 256#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) 257 258extern FILE *sched_dump; 259extern int sched_verbose; 260 261#ifndef __GNUC__ 262#define __inline 263#endif 264 265#ifndef HAIFA_INLINE 266#define HAIFA_INLINE __inline 267#endif 268 269/* Functions in sched-vis.c. */ 270extern void init_target_units PARAMS ((void)); 271extern void insn_print_units PARAMS ((rtx)); 272extern void init_block_visualization PARAMS ((void)); 273extern void print_block_visualization PARAMS ((const char *)); 274extern void visualize_scheduled_insns PARAMS ((int)); 275extern void visualize_no_unit PARAMS ((rtx)); 276extern void visualize_stall_cycles PARAMS ((int)); 277extern void visualize_alloc PARAMS ((void)); 278extern void visualize_free PARAMS ((void)); 279 280/* Functions in sched-deps.c. */ 281extern void add_dependence PARAMS ((rtx, rtx, enum reg_note)); 282extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, 283 rtx)); 284extern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); 285extern void init_deps PARAMS ((struct deps *)); 286extern void free_deps PARAMS ((struct deps *)); 287extern void init_deps_global PARAMS ((void)); 288extern void finish_deps_global PARAMS ((void)); 289extern void compute_forward_dependences PARAMS ((rtx, rtx)); 290extern rtx find_insn_list PARAMS ((rtx, rtx)); 291extern void init_dependency_caches PARAMS ((int)); 292extern void free_dependency_caches PARAMS ((void)); 293 294/* Functions in haifa-sched.c. */ 295extern void get_block_head_tail PARAMS ((int, rtx *, rtx *)); 296extern int no_real_insns_p PARAMS ((rtx, rtx)); 297 298extern void rm_line_notes PARAMS ((rtx, rtx)); 299extern void save_line_notes PARAMS ((int, rtx, rtx)); 300extern void restore_line_notes PARAMS ((rtx, rtx)); 301extern void rm_redundant_line_notes PARAMS ((void)); 302extern void rm_other_notes PARAMS ((rtx, rtx)); 303 304extern int insn_issue_delay PARAMS ((rtx)); 305extern int set_priorities PARAMS ((rtx, rtx)); 306 307extern rtx sched_emit_insn PARAMS ((rtx)); 308extern void schedule_block PARAMS ((int, int)); 309extern void sched_init PARAMS ((FILE *)); 310extern void sched_finish PARAMS ((void)); 311 312extern void ready_add PARAMS ((struct ready_list *, rtx)); 313 314/* The following are exported for the benefit of debugging functions. It 315 would be nicer to keep them private to haifa-sched.c. */ 316extern int insn_unit PARAMS ((rtx)); 317extern int insn_cost PARAMS ((rtx, rtx, rtx)); 318extern rtx get_unit_last_insn PARAMS ((int)); 319extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); 320extern void print_insn PARAMS ((char *, rtx, int)); 321