sched-int.h revision 96263
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 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, 59 Temple Place - Suite 330, Boston, MA 2102111-1307, USA. */ 22 23/* Forward declaration. */ 24struct ready_list; 25 26/* Describe state of dependencies used during sched_analyze phase. */ 27struct deps 28{ 29 /* The *_insns and *_mems are paired lists. Each pending memory operation 30 will have a pointer to the MEM rtx on one list and a pointer to the 31 containing insn on the other list in the same place in the list. */ 32 33 /* We can't use add_dependence like the old code did, because a single insn 34 may have multiple memory accesses, and hence needs to be on the list 35 once for each memory access. Add_dependence won't let you add an insn 36 to a list more than once. */ 37 38 /* An INSN_LIST containing all insns with pending read operations. */ 39 rtx pending_read_insns; 40 41 /* An EXPR_LIST containing all MEM rtx's which are pending reads. */ 42 rtx pending_read_mems; 43 44 /* An INSN_LIST containing all insns with pending write operations. */ 45 rtx pending_write_insns; 46 47 /* An EXPR_LIST containing all MEM rtx's which are pending writes. */ 48 rtx pending_write_mems; 49 50 /* Indicates the combined length of the two pending lists. We must prevent 51 these lists from ever growing too large since the number of dependencies 52 produced is at least O(N*N), and execution time is at least O(4*N*N), as 53 a function of the length of these pending lists. */ 54 int pending_lists_length; 55 56 /* Length of the pending memory flush list. Large functions with no 57 calls may build up extremely large lists. */ 58 int pending_flush_length; 59 60 /* The last insn upon which all memory references must depend. 61 This is an insn which flushed the pending lists, creating a dependency 62 between it and all previously pending memory references. This creates 63 a barrier (or a checkpoint) which no memory reference is allowed to cross. 64 65 This includes all non constant CALL_INSNs. When we do interprocedural 66 alias analysis, this restriction can be relaxed. 67 This may also be an INSN that writes memory if the pending lists grow 68 too large. */ 69 rtx last_pending_memory_flush; 70 71 /* A list of the last function calls we have seen. We use a list to 72 represent last function calls from multiple predecessor blocks. 73 Used to prevent register lifetimes from expanding unnecessarily. */ 74 rtx last_function_call; 75 76 /* A list of insns which use a pseudo register that does not already 77 cross a call. We create dependencies between each of those insn 78 and the next call insn, to ensure that they won't cross a call after 79 scheduling is done. */ 80 rtx sched_before_next_call; 81 82 /* Used to keep post-call psuedo/hard reg movements together with 83 the call. */ 84 bool in_post_call_group_p; 85 86 /* The maximum register number for the following arrays. Before reload 87 this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER. */ 88 int max_reg; 89 90 /* Element N is the next insn that sets (hard or pseudo) register 91 N within the current basic block; or zero, if there is no 92 such insn. Needed for new registers which may be introduced 93 by splitting insns. */ 94 struct deps_reg 95 { 96 rtx uses; 97 rtx sets; 98 rtx clobbers; 99 int uses_length; 100 int clobbers_length; 101 } *reg_last; 102 103 /* Element N is set for each register that has any non-zero element 104 in reg_last[N].{uses,sets,clobbers}. */ 105 regset_head reg_last_in_use; 106}; 107 108/* This structure holds some state of the current scheduling pass, and 109 contains some function pointers that abstract out some of the non-generic 110 functionality from functions such as schedule_block or schedule_insn. 111 There is one global variable, current_sched_info, which points to the 112 sched_info structure currently in use. */ 113struct sched_info 114{ 115 /* Add all insns that are initially ready to the ready list. Called once 116 before scheduling a set of insns. */ 117 void (*init_ready_list) PARAMS ((struct ready_list *)); 118 /* Called after taking an insn from the ready list. Returns nonzero if 119 this insn can be scheduled, nonzero if we should silently discard it. */ 120 int (*can_schedule_ready_p) PARAMS ((rtx)); 121 /* Return nonzero if there are more insns that should be scheduled. */ 122 int (*schedule_more_p) PARAMS ((void)); 123 /* Called after an insn has all its dependencies resolved. Return nonzero 124 if it should be moved to the ready list or the queue, or zero if we 125 should silently discard it. */ 126 int (*new_ready) PARAMS ((rtx)); 127 /* Compare priority of two insns. Return a positive number if the second 128 insn is to be preferred for scheduling, and a negative one if the first 129 is to be preferred. Zero if they are equally good. */ 130 int (*rank) PARAMS ((rtx, rtx)); 131 /* Return a string that contains the insn uid and optionally anything else 132 necessary to identify this insn in an output. It's valid to use a 133 static buffer for this. The ALIGNED parameter should cause the string 134 to be formatted so that multiple output lines will line up nicely. */ 135 const char *(*print_insn) PARAMS ((rtx, int)); 136 /* Return nonzero if an insn should be included in priority 137 calculations. */ 138 int (*contributes_to_priority) PARAMS ((rtx, rtx)); 139 /* Called when computing dependencies for a JUMP_INSN. This function 140 should store the set of registers that must be considered as set by 141 the jump in the regset. */ 142 void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset)); 143 144 /* The boundaries of the set of insns to be scheduled. */ 145 rtx prev_head, next_tail; 146 147 /* Filled in after the schedule is finished; the first and last scheduled 148 insns. */ 149 rtx head, tail; 150 151 /* If nonzero, enables an additional sanity check in schedule_block. */ 152 unsigned int queue_must_finish_empty:1; 153 /* Nonzero if we should use cselib for better alias analysis. This 154 must be 0 if the dependency information is used after sched_analyze 155 has completed, e.g. if we're using it to initialize state for successor 156 blocks in region scheduling. */ 157 unsigned int use_cselib:1; 158}; 159 160extern struct sched_info *current_sched_info; 161 162/* Indexed by INSN_UID, the collection of all data associated with 163 a single instruction. */ 164 165struct haifa_insn_data 166{ 167 /* A list of insns which depend on the instruction. Unlike LOG_LINKS, 168 it represents forward dependencies. */ 169 rtx depend; 170 171 /* The line number note in effect for each insn. For line number 172 notes, this indicates whether the note may be reused. */ 173 rtx line_note; 174 175 /* Logical uid gives the original ordering of the insns. */ 176 int luid; 177 178 /* A priority for each insn. */ 179 int priority; 180 181 /* The number of incoming edges in the forward dependency graph. 182 As scheduling proceds, counts are decreased. An insn moves to 183 the ready queue when its counter reaches zero. */ 184 int dep_count; 185 186 /* An encoding of the blockage range function. Both unit and range 187 are coded. */ 188 unsigned int blockage; 189 190 /* Number of instructions referring to this insn. */ 191 int ref_count; 192 193 /* The minimum clock tick at which the insn becomes ready. This is 194 used to note timing constraints for the insns in the pending list. */ 195 int tick; 196 197 short cost; 198 199 /* An encoding of the function units used. */ 200 short units; 201 202 /* This weight is an estimation of the insn's contribution to 203 register pressure. */ 204 short reg_weight; 205 206 /* Some insns (e.g. call) are not allowed to move across blocks. */ 207 unsigned int cant_move : 1; 208 209 /* Set if there's DEF-USE dependence between some speculatively 210 moved load insn and this one. */ 211 unsigned int fed_by_spec_load : 1; 212 unsigned int is_load_insn : 1; 213 214 /* Nonzero if priority has been computed already. */ 215 unsigned int priority_known : 1; 216}; 217 218extern struct haifa_insn_data *h_i_d; 219 220/* Accessor macros for h_i_d. There are more in haifa-sched.c and 221 sched-rgn.c. */ 222#define INSN_DEPEND(INSN) (h_i_d[INSN_UID (INSN)].depend) 223#define INSN_LUID(INSN) (h_i_d[INSN_UID (INSN)].luid) 224#define CANT_MOVE(insn) (h_i_d[INSN_UID (insn)].cant_move) 225#define INSN_DEP_COUNT(INSN) (h_i_d[INSN_UID (INSN)].dep_count) 226#define INSN_PRIORITY(INSN) (h_i_d[INSN_UID (INSN)].priority) 227#define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known) 228#define INSN_COST(INSN) (h_i_d[INSN_UID (INSN)].cost) 229#define INSN_UNIT(INSN) (h_i_d[INSN_UID (INSN)].units) 230#define INSN_REG_WEIGHT(INSN) (h_i_d[INSN_UID (INSN)].reg_weight) 231 232#define INSN_BLOCKAGE(INSN) (h_i_d[INSN_UID (INSN)].blockage) 233#define UNIT_BITS 5 234#define BLOCKAGE_MASK ((1 << BLOCKAGE_BITS) - 1) 235#define ENCODE_BLOCKAGE(U, R) \ 236 (((U) << BLOCKAGE_BITS \ 237 | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS \ 238 | MAX_BLOCKAGE_COST (R)) 239#define UNIT_BLOCKED(B) ((B) >> (2 * BLOCKAGE_BITS)) 240#define BLOCKAGE_RANGE(B) \ 241 (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \ 242 | ((B) & BLOCKAGE_MASK)) 243 244/* Encodings of the `<name>_unit_blockage_range' function. */ 245#define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2)) 246#define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1)) 247 248extern FILE *sched_dump; 249extern int sched_verbose; 250 251#ifndef __GNUC__ 252#define __inline 253#endif 254 255#ifndef HAIFA_INLINE 256#define HAIFA_INLINE __inline 257#endif 258 259/* Functions in sched-vis.c. */ 260extern void init_target_units PARAMS ((void)); 261extern void insn_print_units PARAMS ((rtx)); 262extern void init_block_visualization PARAMS ((void)); 263extern void print_block_visualization PARAMS ((const char *)); 264extern void visualize_scheduled_insns PARAMS ((int)); 265extern void visualize_no_unit PARAMS ((rtx)); 266extern void visualize_stall_cycles PARAMS ((int)); 267extern void visualize_alloc PARAMS ((void)); 268extern void visualize_free PARAMS ((void)); 269 270/* Functions in sched-deps.c. */ 271extern void add_dependence PARAMS ((rtx, rtx, enum reg_note)); 272extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx, 273 rtx)); 274extern void sched_analyze PARAMS ((struct deps *, rtx, rtx)); 275extern void init_deps PARAMS ((struct deps *)); 276extern void free_deps PARAMS ((struct deps *)); 277extern void init_deps_global PARAMS ((void)); 278extern void finish_deps_global PARAMS ((void)); 279extern void compute_forward_dependences PARAMS ((rtx, rtx)); 280extern rtx find_insn_list PARAMS ((rtx, rtx)); 281extern void init_dependency_caches PARAMS ((int)); 282extern void free_dependency_caches PARAMS ((void)); 283 284/* Functions in haifa-sched.c. */ 285extern void get_block_head_tail PARAMS ((int, rtx *, rtx *)); 286extern int no_real_insns_p PARAMS ((rtx, rtx)); 287 288extern void rm_line_notes PARAMS ((rtx, rtx)); 289extern void save_line_notes PARAMS ((int, rtx, rtx)); 290extern void restore_line_notes PARAMS ((rtx, rtx)); 291extern void rm_redundant_line_notes PARAMS ((void)); 292extern void rm_other_notes PARAMS ((rtx, rtx)); 293 294extern int insn_issue_delay PARAMS ((rtx)); 295extern int set_priorities PARAMS ((rtx, rtx)); 296 297extern rtx sched_emit_insn PARAMS ((rtx)); 298extern void schedule_block PARAMS ((int, int)); 299extern void sched_init PARAMS ((FILE *)); 300extern void sched_finish PARAMS ((void)); 301 302extern void ready_add PARAMS ((struct ready_list *, rtx)); 303 304/* The following are exported for the benefit of debugging functions. It 305 would be nicer to keep them private to haifa-sched.c. */ 306extern int insn_unit PARAMS ((rtx)); 307extern int insn_cost PARAMS ((rtx, rtx, rtx)); 308extern rtx get_unit_last_insn PARAMS ((int)); 309extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int)); 310 311