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, 2003 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 nonzero element
 113      in reg_last[N].{uses,sets,clobbers}.  */
 114   regset_head reg_last_in_use;
 115
 116   /* Element N is set for each register that is conditionally set.  */
 117   regset_head reg_conditional_sets;
 118 };
 119
 120 /* This structure holds some state of the current scheduling pass, and
 121    contains some function pointers that abstract out some of the non-generic
 122    functionality from functions such as schedule_block or schedule_insn.
 123    There is one global variable, current_sched_info, which points to the
 124    sched_info structure currently in use.  */
 125 struct sched_info
 126 {
 127   /* Add all insns that are initially ready to the ready list.  Called once
 128      before scheduling a set of insns.  */
 129   void (*init_ready_list) (struct ready_list *);
 130   /* Called after taking an insn from the ready list.  Returns nonzero if
 131      this insn can be scheduled, nonzero if we should silently discard it.  */
 132   int (*can_schedule_ready_p) (rtx);
 133   /* Return nonzero if there are more insns that should be scheduled.  */
 134   int (*schedule_more_p) (void);
 135   /* Called after an insn has all its dependencies resolved.  Return nonzero
 136      if it should be moved to the ready list or the queue, or zero if we
 137      should silently discard it.  */
 138   int (*new_ready) (rtx);
 139   /* Compare priority of two insns.  Return a positive number if the second
 140      insn is to be preferred for scheduling, and a negative one if the first
 141      is to be preferred.  Zero if they are equally good.  */
 142   int (*rank) (rtx, rtx);
 143   /* Return a string that contains the insn uid and optionally anything else
 144      necessary to identify this insn in an output.  It's valid to use a
 145      static buffer for this.  The ALIGNED parameter should cause the string
 146      to be formatted so that multiple output lines will line up nicely.  */
 147   const char *(*print_insn) (rtx, int);
 148   /* Return nonzero if an insn should be included in priority
 149      calculations.  */
 150   int (*contributes_to_priority) (rtx, rtx);
 151   /* Called when computing dependencies for a JUMP_INSN.  This function
 152      should store the set of registers that must be considered as set by
 153      the jump in the regset.  */
 154   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 155
 156   /* The boundaries of the set of insns to be scheduled.  */
 157   rtx prev_head, next_tail;
 158
 159   /* Filled in after the schedule is finished; the first and last scheduled
 160      insns.  */
 161   rtx head, tail;
 162
 163   /* If nonzero, enables an additional sanity check in schedule_block.  */
 164   unsigned int queue_must_finish_empty:1;
 165   /* Nonzero if we should use cselib for better alias analysis.  This
 166      must be 0 if the dependency information is used after sched_analyze
 167      has completed, e.g. if we're using it to initialize state for successor
 168      blocks in region scheduling.  */
 169   unsigned int use_cselib:1;
 170 };
 171
 172 extern struct sched_info *current_sched_info;
 173
 174 /* Indexed by INSN_UID, the collection of all data associated with
 175    a single instruction.  */
 176
 177 struct haifa_insn_data
 178 {
 179   /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
 180      it represents forward dependencies.  */
 181   rtx depend;
 182
 183   /* The line number note in effect for each insn.  For line number
 184      notes, this indicates whether the note may be reused.  */
 185   rtx line_note;
 186
 187   /* Logical uid gives the original ordering of the insns.  */
 188   int luid;
 189
 190   /* A priority for each insn.  */
 191   int priority;
 192
 193   /* The number of incoming edges in the forward dependency graph.
 194      As scheduling proceeds, counts are decreased.  An insn moves to
 195      the ready queue when its counter reaches zero.  */
 196   int dep_count;
 197
 198   /* An encoding of the blockage range function.  Both unit and range
 199      are coded.  This member is used only for old pipeline interface.  */
 200   unsigned int blockage;
 201
 202   /* Number of instructions referring to this insn.  */
 203   int ref_count;
 204
 205   /* The minimum clock tick at which the insn becomes ready.  This is
 206      used to note timing constraints for the insns in the pending list.  */
 207   int tick;
 208
 209   short cost;
 210
 211   /* An encoding of the function units used.  This member is used only
 212      for old pipeline interface.  */
 213   short units;
 214
 215   /* This weight is an estimation of the insn's contribution to
 216      register pressure.  */
 217   short reg_weight;
 218
 219   /* Some insns (e.g. call) are not allowed to move across blocks.  */
 220   unsigned int cant_move : 1;
 221
 222   /* Set if there's DEF-USE dependence between some speculatively
 223      moved load insn and this one.  */
 224   unsigned int fed_by_spec_load : 1;
 225   unsigned int is_load_insn : 1;
 226
 227   /* Nonzero if priority has been computed already.  */
 228   unsigned int priority_known : 1;
 229 };
 230
 231 extern struct haifa_insn_data *h_i_d;
 232
 233 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 234    sched-rgn.c.  */
 235 #define INSN_DEPEND(INSN)       (h_i_d[INSN_UID (INSN)].depend)
 236 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 237 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 238 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 239 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 240 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
 241 #define INSN_COST(INSN)         (h_i_d[INSN_UID (INSN)].cost)
 242 #define INSN_UNIT(INSN)         (h_i_d[INSN_UID (INSN)].units)
 243 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 244
 245 #define INSN_BLOCKAGE(INSN)     (h_i_d[INSN_UID (INSN)].blockage)
 246 #define UNIT_BITS               5
 247 #define BLOCKAGE_MASK           ((1 << BLOCKAGE_BITS) - 1)
 248 #define ENCODE_BLOCKAGE(U, R)                   \
 249   (((U) << BLOCKAGE_BITS                        \
 250     | MIN_BLOCKAGE_COST (R)) << BLOCKAGE_BITS   \
 251    | MAX_BLOCKAGE_COST (R))
 252 #define UNIT_BLOCKED(B)         ((B) >> (2 * BLOCKAGE_BITS))
 253 #define BLOCKAGE_RANGE(B)                                                \
 254   (((((B) >> BLOCKAGE_BITS) & BLOCKAGE_MASK) << (HOST_BITS_PER_INT / 2)) \
 255    | ((B) & BLOCKAGE_MASK))
 256
 257 /* Encodings of the `<name>_unit_blockage_range' function.  */
 258 #define MIN_BLOCKAGE_COST(R) ((R) >> (HOST_BITS_PER_INT / 2))
 259 #define MAX_BLOCKAGE_COST(R) ((R) & ((1 << (HOST_BITS_PER_INT / 2)) - 1))
 260
 261 extern FILE *sched_dump;
 262 extern int sched_verbose;
 263
 264 /* Exception Free Loads:
 265
 266    We define five classes of speculative loads: IFREE, IRISKY,
 267    PFREE, PRISKY, and MFREE.
 268
 269    IFREE loads are loads that are proved to be exception-free, just
 270    by examining the load insn.  Examples for such loads are loads
 271    from TOC and loads of global data.
 272
 273    IRISKY loads are loads that are proved to be exception-risky,
 274    just by examining the load insn.  Examples for such loads are
 275    volatile loads and loads from shared memory.
 276
 277    PFREE loads are loads for which we can prove, by examining other
 278    insns, that they are exception-free.  Currently, this class consists
 279    of loads for which we are able to find a "similar load", either in
 280    the target block, or, if only one split-block exists, in that split
 281    block.  Load2 is similar to load1 if both have same single base
 282    register.  We identify only part of the similar loads, by finding
 283    an insn upon which both load1 and load2 have a DEF-USE dependence.
 284
 285    PRISKY loads are loads for which we can prove, by examining other
 286    insns, that they are exception-risky.  Currently we have two proofs for
 287    such loads.  The first proof detects loads that are probably guarded by a
 288    test on the memory address.  This proof is based on the
 289    backward and forward data dependence information for the region.
 290    Let load-insn be the examined load.
 291    Load-insn is PRISKY iff ALL the following hold:
 292
 293    - insn1 is not in the same block as load-insn
 294    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
 295    - test-insn is either a compare or a branch, not in the same block
 296      as load-insn
 297    - load-insn is reachable from test-insn
 298    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
 299
 300    This proof might fail when the compare and the load are fed
 301    by an insn not in the region.  To solve this, we will add to this
 302    group all loads that have no input DEF-USE dependence.
 303
 304    The second proof detects loads that are directly or indirectly
 305    fed by a speculative load.  This proof is affected by the
 306    scheduling process.  We will use the flag  fed_by_spec_load.
 307    Initially, all insns have this flag reset.  After a speculative
 308    motion of an insn, if insn is either a load, or marked as
 309    fed_by_spec_load, we will also mark as fed_by_spec_load every
 310    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
 311    load which is fed_by_spec_load is also PRISKY.
 312
 313    MFREE (maybe-free) loads are all the remaining loads. They may be
 314    exception-free, but we cannot prove it.
 315
 316    Now, all loads in IFREE and PFREE classes are considered
 317    exception-free, while all loads in IRISKY and PRISKY classes are
 318    considered exception-risky.  As for loads in the MFREE class,
 319    these are considered either exception-free or exception-risky,
 320    depending on whether we are pessimistic or optimistic.  We have
 321    to take the pessimistic approach to assure the safety of
 322    speculative scheduling, but we can take the optimistic approach
 323    by invoking the -fsched_spec_load_dangerous option.  */
 324
 325 enum INSN_TRAP_CLASS
 326 {
 327   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
 328   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
 329 };
 330
 331 #define WORST_CLASS(class1, class2) \
 332 ((class1 > class2) ? class1 : class2)
 333
 334 #ifndef __GNUC__
 335 #define __inline
 336 #endif
 337
 338 #ifndef HAIFA_INLINE
 339 #define HAIFA_INLINE __inline
 340 #endif
 341
 342 /* Functions in sched-vis.c.  */
 343 extern void init_target_units (void);
 344 extern void insn_print_units (rtx);
 345 extern void init_block_visualization (void);
 346 extern void print_block_visualization (const char *);
 347 extern void visualize_scheduled_insns (int);
 348 extern void visualize_no_unit (rtx);
 349 extern void visualize_stall_cycles (int);
 350 extern void visualize_alloc (void);
 351 extern void visualize_free (void);
 352
 353 /* Functions in sched-deps.c.  */
 354 extern int add_dependence (rtx, rtx, enum reg_note);
 355 extern void add_insn_mem_dependence (struct deps *, rtx *, rtx *, rtx, rtx);
 356 extern void sched_analyze (struct deps *, rtx, rtx);
 357 extern void init_deps (struct deps *);
 358 extern void free_deps (struct deps *);
 359 extern void init_deps_global (void);
 360 extern void finish_deps_global (void);
 361 extern void add_forward_dependence (rtx, rtx, enum reg_note);
 362 extern void compute_forward_dependences (rtx, rtx);
 363 extern rtx find_insn_list (rtx, rtx);
 364 extern void init_dependency_caches (int);
 365 extern void free_dependency_caches (void);
 366
 367 /* Functions in haifa-sched.c.  */
 368 extern int haifa_classify_insn (rtx);
 369 extern void get_block_head_tail (int, rtx *, rtx *);
 370 extern int no_real_insns_p (rtx, rtx);
 371
 372 extern void rm_line_notes (rtx, rtx);
 373 extern void save_line_notes (int, rtx, rtx);
 374 extern void restore_line_notes (rtx, rtx);
 375 extern void rm_redundant_line_notes (void);
 376 extern void rm_other_notes (rtx, rtx);
 377
 378 extern int insn_issue_delay (rtx);
 379 extern int set_priorities (rtx, rtx);
 380
 381 extern rtx sched_emit_insn (rtx);
 382 extern void schedule_block (int, int);
 383 extern void sched_init (FILE *);
 384 extern void sched_finish (void);
 385
 386 extern void ready_add (struct ready_list *, rtx);
 387
 388 /* The following are exported for the benefit of debugging functions.  It
 389    would be nicer to keep them private to haifa-sched.c.  */
 390 extern int insn_unit (rtx);
 391 extern int insn_cost (rtx, rtx, rtx);
 392 extern rtx get_unit_last_insn (int);
 393 extern int actual_hazard_this_instance (int, int, rtx, int, int);
 394 extern void print_insn (char *, rtx, int);