gcc/sched-int.h

   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
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* Pointer to data describing the current DFA state.  */
  24 extern state_t curr_state;
  25
  26 /* Forward declaration.  */
  27 struct ready_list;
  28
  29 /* Describe state of dependencies used during sched_analyze phase.  */
  30 struct deps
  31 {
  32   /* The *_insns and *_mems are paired lists.  Each pending memory operation
  33      will have a pointer to the MEM rtx on one list and a pointer to the
  34      containing insn on the other list in the same place in the list.  */
  35
  36   /* We can't use add_dependence like the old code did, because a single insn
  37      may have multiple memory accesses, and hence needs to be on the list
  38      once for each memory access.  Add_dependence won't let you add an insn
  39      to a list more than once.  */
  40
  41   /* An INSN_LIST containing all insns with pending read operations.  */
  42   rtx pending_read_insns;
  43
  44   /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
  45   rtx pending_read_mems;
  46
  47   /* An INSN_LIST containing all insns with pending write operations.  */
  48   rtx pending_write_insns;
  49
  50   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
  51   rtx pending_write_mems;
  52
  53   /* Indicates the combined length of the two pending lists.  We must prevent
  54      these lists from ever growing too large since the number of dependencies
  55      produced is at least O(N*N), and execution time is at least O(4*N*N), as
  56      a function of the length of these pending lists.  */
  57   int pending_lists_length;
  58
  59   /* Length of the pending memory flush list. Large functions with no
  60      calls may build up extremely large lists.  */
  61   int pending_flush_length;
  62
  63   /* The last insn upon which all memory references must depend.
  64      This is an insn which flushed the pending lists, creating a dependency
  65      between it and all previously pending memory references.  This creates
  66      a barrier (or a checkpoint) which no memory reference is allowed to cross.
  67
  68      This includes all non constant CALL_INSNs.  When we do interprocedural
  69      alias analysis, this restriction can be relaxed.
  70      This may also be an INSN that writes memory if the pending lists grow
  71      too large.  */
  72   rtx last_pending_memory_flush;
  73
  74   /* A list of the last function calls we have seen.  We use a list to
  75      represent last function calls from multiple predecessor blocks.
  76      Used to prevent register lifetimes from expanding unnecessarily.  */
  77   rtx last_function_call;
  78
  79   /* A list of insns which use a pseudo register that does not already
  80      cross a call.  We create dependencies between each of those insn
  81      and the next call insn, to ensure that they won't cross a call after
  82      scheduling is done.  */
  83   rtx sched_before_next_call;
  84
  85   /* Used to keep post-call psuedo/hard reg movements together with
  86      the call.  */
  87   bool in_post_call_group_p;
  88
  89   /* Set to the tail insn of the outermost libcall block.
  90
  91      When nonzero, we will mark each insn processed by sched_analyze_insn
  92      with SCHED_GROUP_P to ensure libcalls are scheduled as a unit.  */
  93   rtx libcall_block_tail_insn;
  94
  95   /* The maximum register number for the following arrays.  Before reload
  96      this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
  97   int max_reg;
  98
  99   /* Element N is the next insn that sets (hard or pseudo) register
 100      N within the current basic block; or zero, if there is no
 101      such insn.  Needed for new registers which may be introduced
 102      by splitting insns.  */
 103   struct deps_reg
 104     {
 105       rtx uses;
 106       rtx sets;
 107       rtx clobbers;
 108       int uses_length;
 109       int clobbers_length;
 110     } *reg_last;
 111
 112   /* Element N is set for each register that has any non-zero element
 113      in reg_last[N].{uses,sets,clobbers}.  */
 114   regset_head reg_last_in_use;
 115 };
 116
 117 /* This structure holds some state of the current scheduling pass, and
 118    contains some function pointers that abstract out some of the non-generic
 119    functionality from functions such as schedule_block or schedule_insn.
 120    There is one global variable, current_sched_info, which points to the
 121    sched_info structure currently in use.  */
 122 struct sched_info
 123 {
 124   /* Add all insns that are initially ready to the ready list.  Called once
 125      before scheduling a set of insns.  */
 126   void (*init_ready_list) PARAMS ((struct ready_list *));
 127   /* Called after taking an insn from the ready list.  Returns nonzero if
 128      this insn can be scheduled, nonzero if we should silently discard it.  */
 129   int (*can_schedule_ready_p) PARAMS ((rtx));
 130   /* Return nonzero if there are more insns that should be scheduled.  */
 131   int (*schedule_more_p) PARAMS ((void));
 132   /* Called after an insn has all its dependencies resolved.  Return nonzero
 133      if it should be moved to the ready list or the queue, or zero if we
 134      should silently discard it.  */
 135   int (*new_ready) PARAMS ((rtx));
 136   /* Compare priority of two insns.  Return a positive number if the second
 137      insn is to be preferred for scheduling, and a negative one if the first
 138      is to be preferred.  Zero if they are equally good.  */
 139   int (*rank) PARAMS ((rtx, rtx));
 140   /* Return a string that contains the insn uid and optionally anything else
 141      necessary to identify this insn in an output.  It's valid to use a
 142      static buffer for this.  The ALIGNED parameter should cause the string
 143      to be formatted so that multiple output lines will line up nicely.  */
 144   const char *(*print_insn) PARAMS ((rtx, int));
 145   /* Return nonzero if an insn should be included in priority
 146      calculations.  */
 147   int (*contributes_to_priority) PARAMS ((rtx, rtx));
 148   /* Called when computing dependencies for a JUMP_INSN.  This function
 149      should store the set of registers that must be considered as set by
 150      the jump in the regset.  */
 151   void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset));
 152
 153   /* The boundaries of the set of insns to be scheduled.  */
 154   rtx prev_head, next_tail;
 155
 156   /* Filled in after the schedule is finished; the first and last scheduled
 157      insns.  */
 158   rtx head, tail;
 159
 160   /* If nonzero, enables an additional sanity check in schedule_block.  */
 161   unsigned int queue_must_finish_empty:1;
 162   /* Nonzero if we should use cselib for better alias analysis.  This
 163      must be 0 if the dependency information is used after sched_analyze
 164      has completed, e.g. if we're using it to initialize state for successor
 165      blocks in region scheduling.  */
 166   unsigned int use_cselib:1;
 167 };
 168
 169 extern struct sched_info *current_sched_info;
 170
 171 /* Indexed by INSN_UID, the collection of all data associated with
 172    a single instruction.  */
 173
 174 struct 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
 228 extern 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
 258 extern FILE *sched_dump;
 259 extern 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.  */
 270 extern void init_target_units PARAMS ((void));
 271 extern void insn_print_units PARAMS ((rtx));
 272 extern void init_block_visualization PARAMS ((void));
 273 extern void print_block_visualization PARAMS ((const char *));
 274 extern void visualize_scheduled_insns PARAMS ((int));
 275 extern void visualize_no_unit PARAMS ((rtx));
 276 extern void visualize_stall_cycles PARAMS ((int));
 277 extern void visualize_alloc PARAMS ((void));
 278 extern void visualize_free PARAMS ((void));
 279
 280 /* Functions in sched-deps.c.  */
 281 extern void add_dependence PARAMS ((rtx, rtx, enum reg_note));
 282 extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
 283                                              rtx));
 284 extern void sched_analyze PARAMS ((struct deps *, rtx, rtx));
 285 extern void init_deps PARAMS ((struct deps *));
 286 extern void free_deps PARAMS ((struct deps *));
 287 extern void init_deps_global PARAMS ((void));
 288 extern void finish_deps_global PARAMS ((void));
 289 extern void compute_forward_dependences PARAMS ((rtx, rtx));
 290 extern rtx find_insn_list PARAMS ((rtx, rtx));
 291 extern void init_dependency_caches PARAMS ((int));
 292 extern void free_dependency_caches PARAMS ((void));
 293
 294 /* Functions in haifa-sched.c.  */
 295 extern void get_block_head_tail PARAMS ((int, rtx *, rtx *));
 296 extern int no_real_insns_p PARAMS ((rtx, rtx));
 297
 298 extern void rm_line_notes PARAMS ((rtx, rtx));
 299 extern void save_line_notes PARAMS ((int, rtx, rtx));
 300 extern void restore_line_notes PARAMS ((rtx, rtx));
 301 extern void rm_redundant_line_notes PARAMS ((void));
 302 extern void rm_other_notes PARAMS ((rtx, rtx));
 303
 304 extern int insn_issue_delay PARAMS ((rtx));
 305 extern int set_priorities PARAMS ((rtx, rtx));
 306
 307 extern rtx sched_emit_insn PARAMS ((rtx));
 308 extern void schedule_block PARAMS ((int, int));
 309 extern void sched_init PARAMS ((FILE *));
 310 extern void sched_finish PARAMS ((void));
 311
 312 extern 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.  */
 316 extern int insn_unit PARAMS ((rtx));
 317 extern int insn_cost PARAMS ((rtx, rtx, rtx));
 318 extern rtx get_unit_last_insn PARAMS ((int));
 319 extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
 320 extern void print_insn PARAMS ((char *, rtx, int));