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 Free Software Foundation, Inc.
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify it
   9 under the terms of the GNU General Public License as published by the
  10 Free Software Foundation; either version 2, or (at your option) any
  11 later version.
  12
  13 GNU CC is distributed in the hope that it will be useful, but WITHOUT
  14 ANY 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 GNU CC; see the file COPYING.  If not, write to the Free
  20 the Free Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  21 02111-1307, USA.  */
  22
  23 /* Forward declaration.  */
  24 struct ready_list;
  25
  26 /* Describe state of dependencies used during sched_analyze phase.  */
  27 struct 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   /* The last insn upon which all memory references must depend.
  57      This is an insn which flushed the pending lists, creating a dependency
  58      between it and all previously pending memory references.  This creates
  59      a barrier (or a checkpoint) which no memory reference is allowed to cross.
  60
  61      This includes all non constant CALL_INSNs.  When we do interprocedural
  62      alias analysis, this restriction can be relaxed.
  63      This may also be an INSN that writes memory if the pending lists grow
  64      too large.  */
  65   rtx last_pending_memory_flush;
  66
  67   /* The last function call we have seen.  All hard regs, and, of course,
  68      the last function call, must depend on this.  */
  69   rtx last_function_call;
  70
  71   /* Used to keep post-call psuedo/hard reg movements together with
  72      the call.  */
  73   int in_post_call_group_p;
  74
  75   /* The LOG_LINKS field of this is a list of insns which use a pseudo
  76      register that does not already cross a call.  We create
  77      dependencies between each of those insn and the next call insn,
  78      to ensure that they won't cross a call after scheduling is done.  */
  79   rtx sched_before_next_call;
  80
  81   /* Element N is the next insn that sets (hard or pseudo) register
  82      N within the current basic block; or zero, if there is no
  83      such insn.  Needed for new registers which may be introduced
  84      by splitting insns.  */
  85   rtx *reg_last_uses;
  86   rtx *reg_last_sets;
  87   rtx *reg_last_clobbers;
  88 };
  89
  90 /* This structure holds some state of the current scheduling pass, and
  91    contains some function pointers that abstract out some of the non-generic
  92    functionality from functions such as schedule_block or schedule_insn.
  93    There is one global variable, current_sched_info, which points to the
  94    sched_info structure currently in use.  */
  95 struct sched_info
  96 {
  97   /* Add all insns that are initially ready to the ready list.  Called once
  98      before scheduling a set of insns.  */
  99   void (*init_ready_list) PARAMS ((struct ready_list *));
 100   /* Called after taking an insn from the ready list.  Returns nonzero if
 101      this insn can be scheduled, nonzero if we should silently discard it.  */
 102   int (*can_schedule_ready_p) PARAMS ((rtx));
 103   /* Return nonzero if there are more insns that should be scheduled.  */
 104   int (*schedule_more_p) PARAMS ((void));
 105   /* Called after an insn has all its dependencies resolved.  Return nonzero
 106      if it should be moved to the ready list or the queue, or zero if we
 107      should silently discard it.  */
 108   int (*new_ready) PARAMS ((rtx));
 109   /* Compare priority of two insns.  Return a positive number if the second
 110      insn is to be preferred for scheduling, and a negative one if the first
 111      is to be preferred.  Zero if they are equally good.  */
 112   int (*rank) PARAMS ((rtx, rtx));
 113   /* Return a string that contains the insn uid and optionally anything else
 114      necessary to identify this insn in an output.  It's valid to use a
 115      static buffer for this.  The ALIGNED parameter should cause the string
 116      to be formatted so that multiple output lines will line up nicely.  */
 117   const char *(*print_insn) PARAMS ((rtx, int));
 118   /* Return nonzero if an insn should be included in priority
 119      calculations.  */
 120   int (*contributes_to_priority) PARAMS ((rtx, rtx));
 121   /* Called when computing dependencies for a JUMP_INSN.  This function
 122      should store the set of registers that must be considered as set by
 123      the jump in the regset.  */
 124   void (*compute_jump_reg_dependencies) PARAMS ((rtx, regset));
 125
 126   /* The boundaries of the set of insns to be scheduled.  */
 127   rtx prev_head, next_tail;
 128
 129   /* Filled in after the schedule is finished; the first and last scheduled
 130      insns.  */
 131   rtx head, tail;
 132
 133   /* If nonzero, enables an additional sanity check in schedule_block.  */
 134   int queue_must_finish_empty;
 135 };
 136
 137 extern struct sched_info *current_sched_info;
 138
 139 /* Indexed by INSN_UID, the collection of all data associated with
 140    a single instruction.  */
 141
 142 struct haifa_insn_data
 143 {
 144   /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
 145      it represents forward dependancies.  */
 146   rtx depend;
 147
 148   /* The line number note in effect for each insn.  For line number
 149      notes, this indicates whether the note may be reused.  */
 150   rtx line_note;
 151
 152   /* Logical uid gives the original ordering of the insns.  */
 153   int luid;
 154
 155   /* A priority for each insn.  */
 156   int priority;
 157
 158   /* The number of incoming edges in the forward dependency graph.
 159      As scheduling proceds, counts are decreased.  An insn moves to
 160      the ready queue when its counter reaches zero.  */
 161   int dep_count;
 162
 163   /* An encoding of the blockage range function.  Both unit and range
 164      are coded.  */
 165   unsigned int blockage;
 166
 167   /* Number of instructions referring to this insn.  */
 168   int ref_count;
 169
 170   /* The minimum clock tick at which the insn becomes ready.  This is
 171      used to note timing constraints for the insns in the pending list.  */
 172   int tick;
 173
 174   short cost;
 175
 176   /* An encoding of the function units used.  */
 177   short units;
 178
 179   /* This weight is an estimation of the insn's contribution to
 180      register pressure.  */
 181   short reg_weight;
 182
 183   /* Some insns (e.g. call) are not allowed to move across blocks.  */
 184   unsigned int cant_move : 1;
 185
 186   /* Set if there's DEF-USE dependance between some speculatively
 187      moved load insn and this one.  */
 188   unsigned int fed_by_spec_load : 1;
 189   unsigned int is_load_insn : 1;
 190 };
 191
 192 extern struct haifa_insn_data *h_i_d;
 193
 194 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 195    sched-rgn.c.  */
 196 #define INSN_DEPEND(INSN)       (h_i_d[INSN_UID (INSN)].depend)
 197 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 198 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 199 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 200 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 201 #define INSN_COST(INSN)         (h_i_d[INSN_UID (INSN)].cost)
 202 #define INSN_UNIT(INSN)         (h_i_d[INSN_UID (INSN)].units)
 203 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 204
 205 #define INSN_BLOCKAGE(INSN)     (h_i_d[INSN_UID (INSN)].blockage)
 206 #define UNIT_BITS               5
 207 #define BLOCKAGE_MASK           ((1 << BLOCKAGE_BITS) - 1)
 208 #define ENCODE_BLOCKAGE(U, R)                   \
 209   (((U) << BLOCKAGE_BITS                        \
 210     | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS   \
 211    | MAX_BLOCKAGE_COST (R))
 212 #define UNIT_BLOCKED(B)         ((B) >> (2 * BLOCKAGE_BITS))
 213 #define BLOCKAGE_RANGE(B)                                                \
 214   (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
 215    | ((B) & BLOCKAGE_MASK))
 216
 217 /* Encodings of the `<name>_unit_blockage_range' function.  */
 218 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
 219 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
 220
 221 extern FILE *sched_dump;
 222 extern int sched_verbose;
 223
 224 #ifndef __GNUC__
 225 #define __inline
 226 #endif
 227
 228 #ifndef HAIFA_INLINE
 229 #define HAIFA_INLINE __inline
 230 #endif
 231
 232 /* Functions in sched-vis.c.  */
 233 extern void init_target_units PARAMS ((void));
 234 extern void insn_print_units PARAMS ((rtx));
 235 extern void init_block_visualization PARAMS ((void));
 236 extern void print_block_visualization PARAMS ((const char *));
 237 extern void visualize_scheduled_insns PARAMS ((int));
 238 extern void visualize_no_unit PARAMS ((rtx));
 239 extern void visualize_stall_cycles PARAMS ((int));
 240 extern void visualize_alloc PARAMS ((void));
 241 extern void visualize_free PARAMS ((void));
 242
 243 /* Functions in sched-deps.c.  */
 244 extern void add_dependence PARAMS ((rtx, rtx, enum reg_note));
 245 extern void add_insn_mem_dependence PARAMS ((struct deps *, rtx *, rtx *, rtx,
 246                                              rtx));
 247 extern void sched_analyze PARAMS ((struct deps *, rtx, rtx));
 248 extern void init_deps PARAMS ((struct deps *));
 249 extern void free_deps PARAMS ((struct deps *));
 250 extern void init_deps_global PARAMS ((void));
 251 extern void finish_deps_global PARAMS ((void));
 252 extern void compute_forward_dependences PARAMS ((rtx, rtx));
 253 extern int find_insn_mem_list PARAMS ((rtx, rtx, rtx, rtx));
 254 extern rtx find_insn_list PARAMS ((rtx, rtx));
 255 extern void init_dependency_caches PARAMS ((int));
 256 extern void free_dependency_caches PARAMS ((void));
 257
 258 /* Functions in haifa-sched.c.  */
 259 extern void get_block_head_tail PARAMS ((int, rtx *, rtx *));
 260 extern int no_real_insns_p PARAMS ((rtx, rtx));
 261
 262 extern void rm_line_notes PARAMS ((rtx, rtx));
 263 extern void save_line_notes PARAMS ((int, rtx, rtx));
 264 extern void restore_line_notes PARAMS ((int, rtx, rtx));
 265 extern void rm_redundant_line_notes PARAMS ((void));
 266 extern void rm_other_notes PARAMS ((rtx, rtx));
 267
 268 extern int insn_issue_delay PARAMS ((rtx));
 269 extern int set_priorities PARAMS ((rtx, rtx));
 270
 271 extern void schedule_block PARAMS ((int, int));
 272 extern void sched_init PARAMS ((FILE *));
 273 extern void sched_finish PARAMS ((void));
 274
 275 extern void ready_add PARAMS ((struct ready_list *, rtx));
 276
 277 /* The following are exported for the benefit of debugging functions.  It
 278    would be nicer to keep them private to haifa-sched.c.  */
 279 extern int insn_unit PARAMS ((rtx));
 280 extern int insn_cost PARAMS ((rtx, rtx, rtx));
 281 extern rtx get_unit_last_insn PARAMS ((int));
 282 extern int actual_hazard_this_instance PARAMS ((int, int, rtx, int, int));
 283