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, 2004, 2005, 2006 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, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 #ifndef GCC_SCHED_INT_H
  24 #define GCC_SCHED_INT_H
  25
  26 /* For state_t.  */
  27 #include "insn-attr.h"
  28 /* For regset_head.  */
  29 #include "basic-block.h"
  30 /* For reg_note.  */
  31 #include "rtl.h"
  32
  33 /* Pointer to data describing the current DFA state.  */
  34 extern state_t curr_state;
  35
  36 /* Forward declaration.  */
  37 struct ready_list;
  38
  39 /* Type to represent status of a dependence.  */
  40 typedef int ds_t;
  41
  42 /* Type to represent weakness of speculative dependence.  */
  43 typedef int dw_t;
  44
  45 extern enum reg_note ds_to_dk (ds_t);
  46 extern ds_t dk_to_ds (enum reg_note);
  47
  48 /* Information about the dependency.  */
  49 struct _dep
  50 {
  51   /* Producer.  */
  52   rtx pro;
  53
  54   /* Consumer.  */
  55   rtx con;
  56
  57   /* Dependency kind (aka dependency major type).  This field is superseded
  58      by STATUS below.  Though, it is still in place because all the backends
  59      use it.  */
  60   enum reg_note kind;
  61
  62   /* Dependency status.  This field holds all dependency types and additional
  63      information for speculative dependencies.  */
  64   ds_t status;
  65 };
  66 typedef struct _dep *dep_t;
  67
  68 #define DEP_PRO(D) ((D)->pro)
  69 #define DEP_CON(D) ((D)->con)
  70 #define DEP_KIND(D) ((D)->kind)
  71 #define DEP_STATUS(D) ((D)->status)
  72
  73 /* Functions to work with dep.  */
  74
  75 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
  76
  77 /* Definition of this struct resides below.  */
  78 struct _dep_node;
  79
  80 /* A link in the dependency list.  This is essentially an equivalent of a
  81    single {INSN, DEPS}_LIST rtx.  */
  82 struct _dep_link
  83 {
  84   /* Dep node with all the data.  */
  85   struct _dep_node *node;
  86
  87   /* Next link in the list. For the last one it is NULL.  */
  88   struct _dep_link *next;
  89
  90   /* Pointer to the next field of the previous link in the list.
  91      For the first link this points to the deps_list->first.
  92
  93      With help of this field it is easy to remove and insert links to the
  94      list.  */
  95   struct _dep_link **prev_nextp;
  96 };
  97 typedef struct _dep_link *dep_link_t;
  98
  99 #define DEP_LINK_NODE(N) ((N)->node)
 100 #define DEP_LINK_NEXT(N) ((N)->next)
 101 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
 102
 103 /* Macros to work dep_link.  For most usecases only part of the dependency
 104    information is need.  These macros conveniently provide that piece of
 105    information.  */
 106
 107 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
 108 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
 109 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
 110 #define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N)))
 111 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
 112
 113 void debug_dep_links (dep_link_t);
 114
 115 /* A list of dep_links.  Lists of this type are now used instead of rtx
 116    LOG_LINKS and alike lists.  */
 117 struct _deps_list
 118 {
 119   dep_link_t first;
 120 };
 121 typedef struct _deps_list *deps_list_t;
 122
 123 #define DEPS_LIST_FIRST(L) ((L)->first)
 124
 125 /* Macro to walk through deps_list.  */
 126 #define FOR_EACH_DEP_LINK(LINK, LIST) \
 127   for ((LINK) = DEPS_LIST_FIRST (LIST); \
 128        (LINK) != NULL; \
 129        (LINK) = DEP_LINK_NEXT (LINK))
 130
 131 /* Functions to work with deps_list.  */
 132
 133 deps_list_t create_deps_list (bool);
 134 void free_deps_list (deps_list_t);
 135 void delete_deps_list (deps_list_t);
 136 bool deps_list_empty_p (deps_list_t);
 137 void debug_deps_list (deps_list_t);
 138 void add_back_dep_to_deps_list (deps_list_t, dep_t);
 139 dep_link_t find_link_by_pro_in_deps_list (deps_list_t, rtx);
 140 dep_link_t find_link_by_con_in_deps_list (deps_list_t, rtx);
 141 void copy_deps_list_change_con (deps_list_t, deps_list_t, rtx);
 142
 143 void move_dep_link (dep_link_t, deps_list_t);
 144
 145 /* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has
 146    additional dependents con0 and con2, and con1 is dependent on additional
 147    insns pro0 and pro1:
 148
 149    .con0      pro0
 150    . ^         |
 151    . |         |
 152    . |         |
 153    . X         A
 154    . |         |
 155    . |         |
 156    . |         V
 157    .pro1--Y-->con1
 158    . |         ^
 159    . |         |
 160    . |         |
 161    . Z         B
 162    . |         |
 163    . |         |
 164    . V         |
 165    .con2      pro2
 166
 167    This is represented using a "dep_node" for each dependence arc, which are
 168    connected as follows (diagram is centered around Y which is fully shown;
 169    other dep_nodes shown partially):
 170
 171    .          +------------+    +--------------+    +------------+
 172    .          : dep_node X :    |  dep_node Y  |    : dep_node Z :
 173    .          :            :    |              |    :            :
 174    .          :            :    |              |    :            :
 175    .          : forw       :    |  forw        |    : forw       :
 176    .          : +--------+ :    |  +--------+  |    : +--------+ :
 177    forw_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
 178    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 179    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
 180    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 181    . ^  ^     : |     ^  | :    |  |     ^  |  |    : |        | :
 182    . |  |     : |     |  | :    |  |     |  |  |    : |        | :
 183    . |  +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
 184    . |        : |  |     | :    |  |  |     |  |    : |  |     | :
 185    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 186    . |        : | |prev| | :    |  | |prev| |  |    : | |prev| | :
 187    . |        : | |next| | :    |  | |next| |  |    : | |next| | :
 188    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 189    . |        : |        | :<-+ |  |        |  |<-+ : |        | :<-+
 190    . |        : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
 191    . |        : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
 192    . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 193    . |        : |        | :    |  |        |  |    : |        | :
 194    . |        : +--------+ :    |  +--------+  |    : +--------+ :
 195    . |        :            :    |              |    :            :
 196    . |        :  SAME pro1 :    |  +--------+  |    :  SAME pro1 :
 197    . |        :  DIFF con0 :    |  |dep     |  |    :  DIFF con2 :
 198    . |        :            :    |  |        |  |    :            :
 199    . |                          |  | +----+ |  |
 200    .RTX<------------------------+--+-|pro1| |  |
 201    .pro1                        |  | +----+ |  |
 202    .                            |  |        |  |
 203    .                            |  | +----+ |  |
 204    .RTX<------------------------+--+-|con1| |  |
 205    .con1                        |  | +----+ |  |
 206    . |                          |  |        |  |
 207    . |                          |  | +----+ |  |
 208    . |                          |  | |kind| |  |
 209    . |                          |  | +----+ |  |
 210    . |        :            :    |  | |stat| |  |    :            :
 211    . |        :  DIFF pro0 :    |  | +----+ |  |    :  DIFF pro2 :
 212    . |        :  SAME con1 :    |  |        |  |    :  SAME con1 :
 213    . |        :            :    |  +--------+  |    :            :
 214    . |        :            :    |              |    :            :
 215    . |        : back       :    |  back        |    : back       :
 216    . v        : +--------+ :    |  +--------+  |    : +--------+ :
 217    back_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :
 218    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 219    |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL
 220    +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 221    .    ^     : |     ^  | :    |  |     ^  |  |    : |        | :
 222    .    |     : |     |  | :    |  |     |  |  |    : |        | :
 223    .    +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :
 224    .          : |  |     | :    |  |  |     |  |    : |  |     | :
 225    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 226    .          : | |prev| | :    |  | |prev| |  |    : | |prev| | :
 227    .          : | |next| | :    |  | |next| |  |    : | |next| | :
 228    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 229    .          : |        | :<-+ |  |        |  |<-+ : |        | :<-+
 230    .          : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |
 231    .          : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+
 232    .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :
 233    .          : |        | :    |  |        |  |    : |        | :
 234    .          : +--------+ :    |  +--------+  |    : +--------+ :
 235    .          :            :    |              |    :            :
 236    .          : dep_node A :    |  dep_node Y  |    : dep_node B :
 237    .          +------------+    +--------------+    +------------+
 238 */
 239
 240 struct _dep_node
 241 {
 242   /* Backward link.  */
 243   struct _dep_link back;
 244
 245   /* The dep.  */
 246   struct _dep dep;
 247
 248   /* Forward link.  */
 249   struct _dep_link forw;
 250 };
 251 typedef struct _dep_node *dep_node_t;
 252
 253 #define DEP_NODE_BACK(N) (&(N)->back)
 254 #define DEP_NODE_DEP(N) (&(N)->dep)
 255 #define DEP_NODE_FORW(N) (&(N)->forw)
 256
 257 /* Describe state of dependencies used during sched_analyze phase.  */
 258 struct deps
 259 {
 260   /* The *_insns and *_mems are paired lists.  Each pending memory operation
 261      will have a pointer to the MEM rtx on one list and a pointer to the
 262      containing insn on the other list in the same place in the list.  */
 263
 264   /* We can't use add_dependence like the old code did, because a single insn
 265      may have multiple memory accesses, and hence needs to be on the list
 266      once for each memory access.  Add_dependence won't let you add an insn
 267      to a list more than once.  */
 268
 269   /* An INSN_LIST containing all insns with pending read operations.  */
 270   rtx pending_read_insns;
 271
 272   /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
 273   rtx pending_read_mems;
 274
 275   /* An INSN_LIST containing all insns with pending write operations.  */
 276   rtx pending_write_insns;
 277
 278   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
 279   rtx pending_write_mems;
 280
 281   /* We must prevent the above lists from ever growing too large since
 282      the number of dependencies produced is at least O(N*N),
 283      and execution time is at least O(4*N*N), as a function of the
 284      length of these pending lists.  */
 285
 286   /* Indicates the length of the pending_read list.  */
 287   int pending_read_list_length;
 288
 289   /* Indicates the length of the pending_write list.  */
 290   int pending_write_list_length;
 291
 292   /* Length of the pending memory flush list. Large functions with no
 293      calls may build up extremely large lists.  */
 294   int pending_flush_length;
 295
 296   /* The last insn upon which all memory references must depend.
 297      This is an insn which flushed the pending lists, creating a dependency
 298      between it and all previously pending memory references.  This creates
 299      a barrier (or a checkpoint) which no memory reference is allowed to cross.
 300
 301      This includes all non constant CALL_INSNs.  When we do interprocedural
 302      alias analysis, this restriction can be relaxed.
 303      This may also be an INSN that writes memory if the pending lists grow
 304      too large.  */
 305   rtx last_pending_memory_flush;
 306
 307   /* A list of the last function calls we have seen.  We use a list to
 308      represent last function calls from multiple predecessor blocks.
 309      Used to prevent register lifetimes from expanding unnecessarily.  */
 310   rtx last_function_call;
 311
 312   /* A list of insns which use a pseudo register that does not already
 313      cross a call.  We create dependencies between each of those insn
 314      and the next call insn, to ensure that they won't cross a call after
 315      scheduling is done.  */
 316   rtx sched_before_next_call;
 317
 318   /* Used to keep post-call pseudo/hard reg movements together with
 319      the call.  */
 320   enum { not_post_call, post_call, post_call_initial } in_post_call_group_p;
 321
 322   /* Set to the tail insn of the outermost libcall block.
 323
 324      When nonzero, we will mark each insn processed by sched_analyze_insn
 325      with SCHED_GROUP_P to ensure libcalls are scheduled as a unit.  */
 326   rtx libcall_block_tail_insn;
 327
 328   /* The maximum register number for the following arrays.  Before reload
 329      this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
 330   int max_reg;
 331
 332   /* Element N is the next insn that sets (hard or pseudo) register
 333      N within the current basic block; or zero, if there is no
 334      such insn.  Needed for new registers which may be introduced
 335      by splitting insns.  */
 336   struct deps_reg
 337     {
 338       rtx uses;
 339       rtx sets;
 340       rtx clobbers;
 341       int uses_length;
 342       int clobbers_length;
 343     } *reg_last;
 344
 345   /* Element N is set for each register that has any nonzero element
 346      in reg_last[N].{uses,sets,clobbers}.  */
 347   regset_head reg_last_in_use;
 348
 349   /* Element N is set for each register that is conditionally set.  */
 350   regset_head reg_conditional_sets;
 351 };
 352
 353 /* This structure holds some state of the current scheduling pass, and
 354    contains some function pointers that abstract out some of the non-generic
 355    functionality from functions such as schedule_block or schedule_insn.
 356    There is one global variable, current_sched_info, which points to the
 357    sched_info structure currently in use.  */
 358 struct sched_info
 359 {
 360   /* Add all insns that are initially ready to the ready list.  Called once
 361      before scheduling a set of insns.  */
 362   void (*init_ready_list) (void);
 363   /* Called after taking an insn from the ready list.  Returns nonzero if
 364      this insn can be scheduled, nonzero if we should silently discard it.  */
 365   int (*can_schedule_ready_p) (rtx);
 366   /* Return nonzero if there are more insns that should be scheduled.  */
 367   int (*schedule_more_p) (void);
 368   /* Called after an insn has all its hard dependencies resolved.
 369      Adjusts status of instruction (which is passed through second parameter)
 370      to indicate if instruction should be moved to the ready list or the
 371      queue, or if it should silently discard it (until next resolved
 372      dependence).  */
 373   ds_t (*new_ready) (rtx, ds_t);
 374   /* Compare priority of two insns.  Return a positive number if the second
 375      insn is to be preferred for scheduling, and a negative one if the first
 376      is to be preferred.  Zero if they are equally good.  */
 377   int (*rank) (rtx, rtx);
 378   /* Return a string that contains the insn uid and optionally anything else
 379      necessary to identify this insn in an output.  It's valid to use a
 380      static buffer for this.  The ALIGNED parameter should cause the string
 381      to be formatted so that multiple output lines will line up nicely.  */
 382   const char *(*print_insn) (rtx, int);
 383   /* Return nonzero if an insn should be included in priority
 384      calculations.  */
 385   int (*contributes_to_priority) (rtx, rtx);
 386   /* Called when computing dependencies for a JUMP_INSN.  This function
 387      should store the set of registers that must be considered as set by
 388      the jump in the regset.  */
 389   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 390
 391   /* The boundaries of the set of insns to be scheduled.  */
 392   rtx prev_head, next_tail;
 393
 394   /* Filled in after the schedule is finished; the first and last scheduled
 395      insns.  */
 396   rtx head, tail;
 397
 398   /* If nonzero, enables an additional sanity check in schedule_block.  */
 399   unsigned int queue_must_finish_empty:1;
 400   /* Nonzero if we should use cselib for better alias analysis.  This
 401      must be 0 if the dependency information is used after sched_analyze
 402      has completed, e.g. if we're using it to initialize state for successor
 403      blocks in region scheduling.  */
 404   unsigned int use_cselib:1;
 405
 406   /* Maximum priority that has been assigned to an insn.  */
 407   int sched_max_insns_priority;
 408
 409   /* Hooks to support speculative scheduling.  */
 410
 411   /* Called to notify frontend that instruction is being added (second
 412      parameter == 0) or removed (second parameter == 1).  */
 413   void (*add_remove_insn) (rtx, int);
 414
 415   /* Called to notify frontend that instruction is being scheduled.
 416      The first parameter - instruction to scheduled, the second parameter -
 417      last scheduled instruction.  */
 418   void (*begin_schedule_ready) (rtx, rtx);
 419
 420   /* Called to notify frontend, that new basic block is being added.
 421      The first parameter - new basic block.
 422      The second parameter - block, after which new basic block is being added,
 423      or EXIT_BLOCK_PTR, if recovery block is being added,
 424      or NULL, if standalone block is being added.  */
 425   void (*add_block) (basic_block, basic_block);
 426
 427   /* If the second parameter is not NULL, return nonnull value, if the
 428      basic block should be advanced.
 429      If the second parameter is NULL, return the next basic block in EBB.
 430      The first parameter is the current basic block in EBB.  */
 431   basic_block (*advance_target_bb) (basic_block, rtx);
 432
 433   /* Called after blocks were rearranged due to movement of jump instruction.
 434      The first parameter - index of basic block, in which jump currently is.
 435      The second parameter - index of basic block, in which jump used
 436      to be.
 437      The third parameter - index of basic block, that follows the second
 438      parameter.  */
 439   void (*fix_recovery_cfg) (int, int, int);
 440
 441 #ifdef ENABLE_CHECKING
 442   /* If the second parameter is zero, return nonzero, if block is head of the
 443      region.
 444      If the second parameter is nonzero, return nonzero, if block is leaf of
 445      the region.
 446      global_live_at_start should not change in region heads and
 447      global_live_at_end should not change in region leafs due to scheduling.  */
 448   int (*region_head_or_leaf_p) (basic_block, int);
 449 #endif
 450
 451   /* ??? FIXME: should use straight bitfields inside sched_info instead of
 452      this flag field.  */
 453   unsigned int flags;
 454 };
 455
 456 /* This structure holds description of the properties for speculative
 457    scheduling.  */
 458 struct spec_info_def
 459 {
 460   /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
 461      BE_IN_{DATA_CONTROL}.  */
 462   int mask;
 463
 464   /* A dump file for additional information on speculative scheduling.  */
 465   FILE *dump;
 466
 467   /* Minimal cumulative weakness of speculative instruction's
 468      dependencies, so that insn will be scheduled.  */
 469   dw_t weakness_cutoff;
 470
 471   /* Flags from the enum SPEC_SCHED_FLAGS.  */
 472   int flags;
 473 };
 474 typedef struct spec_info_def *spec_info_t;
 475
 476 extern struct sched_info *current_sched_info;
 477
 478 /* Indexed by INSN_UID, the collection of all data associated with
 479    a single instruction.  */
 480
 481 struct haifa_insn_data
 482 {
 483   /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
 484      h_i_d because when h_i_d extends, addresses of the deps_list->first
 485      change without updating deps_list->first->next->prev_nextp.  Thus
 486      BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
 487      list is allocated on the obstack.  */
 488
 489   /* A list of backward dependencies.  The insn is a consumer of all the
 490      deps mentioned here.  */
 491   deps_list_t back_deps;
 492
 493   /* A list of insns which depend on the instruction.  Unlike 'back_deps',
 494      it represents forward dependencies.  */
 495   deps_list_t forw_deps;
 496
 497   /* A list of scheduled producers of the instruction.  Links are being moved
 498      from 'back_deps' to 'resolved_back_deps' while scheduling.  */
 499   deps_list_t resolved_back_deps;
 500
 501   /* Logical uid gives the original ordering of the insns.  */
 502   int luid;
 503
 504   /* A priority for each insn.  */
 505   int priority;
 506
 507   /* The number of incoming edges in the forward dependency graph.
 508      As scheduling proceeds, counts are decreased.  An insn moves to
 509      the ready queue when its counter reaches zero.  */
 510   int dep_count;
 511
 512   /* Number of instructions referring to this insn.  */
 513   int ref_count;
 514
 515   /* The minimum clock tick at which the insn becomes ready.  This is
 516      used to note timing constraints for the insns in the pending list.  */
 517   int tick;
 518
 519   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
 520      subsequent blocks in a region.  */
 521   int inter_tick;
 522
 523   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
 524   int queue_index;
 525
 526   short cost;
 527
 528   /* This weight is an estimation of the insn's contribution to
 529      register pressure.  */
 530   short reg_weight;
 531
 532   /* Some insns (e.g. call) are not allowed to move across blocks.  */
 533   unsigned int cant_move : 1;
 534
 535   /* Set if there's DEF-USE dependence between some speculatively
 536      moved load insn and this one.  */
 537   unsigned int fed_by_spec_load : 1;
 538   unsigned int is_load_insn : 1;
 539
 540   /* '> 0' if priority is valid,
 541      '== 0' if priority was not yet computed,
 542      '< 0' if priority in invalid and should be recomputed.  */
 543   signed char priority_status;
 544
 545   /* Nonzero if instruction has internal dependence
 546      (e.g. add_dependence was invoked with (insn == elem)).  */
 547   unsigned int has_internal_dep : 1;
 548
 549   /* What speculations are necessary to apply to schedule the instruction.  */
 550   ds_t todo_spec;
 551   /* What speculations were already applied.  */
 552   ds_t done_spec;
 553   /* What speculations are checked by this instruction.  */
 554   ds_t check_spec;
 555
 556   /* Recovery block for speculation checks.  */
 557   basic_block recovery_block;
 558
 559   /* Original pattern of the instruction.  */
 560   rtx orig_pat;
 561 };
 562
 563 extern struct haifa_insn_data *h_i_d;
 564 /* Used only if (current_sched_info->flags & USE_GLAT) != 0.
 565    These regsets store global_live_at_{start, end} information
 566    for each basic block.  */
 567 extern regset *glat_start, *glat_end;
 568
 569 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 570    sched-rgn.c.  */
 571 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
 572 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
 573 #define INSN_RESOLVED_BACK_DEPS(INSN) \
 574   (h_i_d[INSN_UID (INSN)].resolved_back_deps)
 575 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 576 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 577 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 578 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 579 #define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status)
 580 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
 581 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 582 #define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
 583 #define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
 584 #define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
 585 #define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
 586 #define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
 587 #define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
 588
 589 /* INSN is either a simple or a branchy speculation check.  */
 590 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
 591
 592 /* INSN is a speculation check that will simply reexecute the speculatively
 593    scheduled instruction if the speculation fails.  */
 594 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
 595   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
 596
 597 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
 598    speculation fails.  Insns in that block will reexecute the speculatively
 599    scheduled code and then will return immediately after INSN thus preserving
 600    semantics of the program.  */
 601 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
 602   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
 603
 604 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
 605    for speculative scheduling.  Namely, it is 4 integers in the range
 606    [0, MAX_DEP_WEAK] and 3 bits.
 607    The integers correspond to the probability of the dependence to *not*
 608    exist, it is the probability, that overcoming of this dependence will
 609    not be followed by execution of the recovery code.  Nevertheless,
 610    whatever high the probability of success is, recovery code should still
 611    be generated to preserve semantics of the program.  To find a way to
 612    get/set these integers, please refer to the {get, set}_dep_weak ()
 613    functions in sched-deps.c .
 614    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
 615    output- and anti- dependence.  It is not enough for speculative scheduling
 616    to know just the major type of all the dependence between two instructions,
 617    as only true dependence can be overcome.
 618    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
 619    for using to describe instruction's status.  It is set whenever instruction
 620    has at least one dependence, that cannot be overcame.
 621    See also: check_dep_status () in sched-deps.c .  */
 622
 623 /* We exclude sign bit.  */
 624 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
 625
 626 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
 627    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
 628    dep weakness.  */
 629 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
 630
 631 /* Mask of speculative weakness in dep_status.  */
 632 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
 633
 634 /* This constant means that dependence is fake with 99.999...% probability.
 635    This is the maximum value, that can appear in dep_status.
 636    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
 637    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
 638    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
 639 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
 640
 641 /* This constant means that dependence is 99.999...% real and it is a really
 642    bad idea to overcome it (though this can be done, preserving program
 643    semantics).  */
 644 #define MIN_DEP_WEAK 1
 645
 646 /* This constant represents 100% probability.
 647    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
 648 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
 649
 650 /* Default weakness of speculative dependence.  Used when we can't say
 651    neither bad nor good about the dependence.  */
 652 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
 653
 654 /* Offset for speculative weaknesses in dep_status.  */
 655 enum SPEC_TYPES_OFFSETS {
 656   BEGIN_DATA_BITS_OFFSET = 0,
 657   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 658   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 659   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
 660 };
 661
 662 /* The following defines provide numerous constants used to distinguish between
 663    different types of speculative dependencies.  */
 664
 665 /* Dependence can be overcome with generation of new data speculative
 666    instruction.  */
 667 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
 668
 669 /* This dependence is to the instruction in the recovery block, that was
 670    formed to recover after data-speculation failure.
 671    Thus, this dependence can overcome with generating of the copy of
 672    this instruction in the recovery block.  */
 673 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
 674
 675 /* Dependence can be overcome with generation of new control speculative
 676    instruction.  */
 677 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
 678
 679 /* This dependence is to the instruction in the recovery block, that was
 680    formed to recover after control-speculation failure.
 681    Thus, this dependence can be overcome with generating of the copy of
 682    this instruction in the recovery block.  */
 683 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
 684
 685 /* A few convenient combinations.  */
 686 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
 687 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
 688 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
 689 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
 690 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
 691
 692 /* Constants, that are helpful in iterating through dep_status.  */
 693 #define FIRST_SPEC_TYPE BEGIN_DATA
 694 #define LAST_SPEC_TYPE BE_IN_CONTROL
 695 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
 696
 697 /* Dependence on instruction can be of multiple types
 698    (e.g. true and output). This fields enhance REG_NOTE_KIND information
 699    of the dependence.  */
 700 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
 701 #define DEP_OUTPUT (DEP_TRUE << 1)
 702 #define DEP_ANTI (DEP_OUTPUT << 1)
 703
 704 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
 705
 706 /* Instruction has non-speculative dependence.  This bit represents the
 707    property of an instruction - not the one of a dependence.
 708    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
 709 #define HARD_DEP (DEP_ANTI << 1)
 710
 711 /* This represents the results of calling sched-deps.c functions,
 712    which modify dependencies.  Possible choices are: a dependence
 713    is already present and nothing has been changed; a dependence type
 714    has been changed; brand new dependence has been created.  */
 715 enum DEPS_ADJUST_RESULT {
 716   DEP_PRESENT = 1,
 717   DEP_CHANGED = 2,
 718   DEP_CREATED = 3
 719 };
 720
 721 /* Represents the bits that can be set in the flags field of the
 722    sched_info structure.  */
 723 enum SCHED_FLAGS {
 724   /* If set, generate links between instruction as DEPS_LIST.
 725      Otherwise, generate usual INSN_LIST links.  */
 726   USE_DEPS_LIST = 1,
 727   /* Perform data or control (or both) speculation.
 728      Results in generation of data and control speculative dependencies.
 729      Requires USE_DEPS_LIST set.  */
 730   DO_SPECULATION = USE_DEPS_LIST << 1,
 731   SCHED_RGN = DO_SPECULATION << 1,
 732   SCHED_EBB = SCHED_RGN << 1,
 733   /* Detach register live information from basic block headers.
 734      This is necessary to invoke functions, that change CFG (e.g. split_edge).
 735      Requires USE_GLAT.  */
 736   DETACH_LIFE_INFO = SCHED_EBB << 1,
 737   /* Save register live information from basic block headers to
 738      glat_{start, end} arrays.  */
 739   USE_GLAT = DETACH_LIFE_INFO << 1
 740 };
 741
 742 enum SPEC_SCHED_FLAGS {
 743   COUNT_SPEC_IN_CRITICAL_PATH = 1,
 744   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
 745   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
 746 };
 747
 748 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
 749                                                != NOTE_INSN_BASIC_BLOCK))
 750
 751 extern FILE *sched_dump;
 752 extern int sched_verbose;
 753
 754 /* Exception Free Loads:
 755
 756    We define five classes of speculative loads: IFREE, IRISKY,
 757    PFREE, PRISKY, and MFREE.
 758
 759    IFREE loads are loads that are proved to be exception-free, just
 760    by examining the load insn.  Examples for such loads are loads
 761    from TOC and loads of global data.
 762
 763    IRISKY loads are loads that are proved to be exception-risky,
 764    just by examining the load insn.  Examples for such loads are
 765    volatile loads and loads from shared memory.
 766
 767    PFREE loads are loads for which we can prove, by examining other
 768    insns, that they are exception-free.  Currently, this class consists
 769    of loads for which we are able to find a "similar load", either in
 770    the target block, or, if only one split-block exists, in that split
 771    block.  Load2 is similar to load1 if both have same single base
 772    register.  We identify only part of the similar loads, by finding
 773    an insn upon which both load1 and load2 have a DEF-USE dependence.
 774
 775    PRISKY loads are loads for which we can prove, by examining other
 776    insns, that they are exception-risky.  Currently we have two proofs for
 777    such loads.  The first proof detects loads that are probably guarded by a
 778    test on the memory address.  This proof is based on the
 779    backward and forward data dependence information for the region.
 780    Let load-insn be the examined load.
 781    Load-insn is PRISKY iff ALL the following hold:
 782
 783    - insn1 is not in the same block as load-insn
 784    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
 785    - test-insn is either a compare or a branch, not in the same block
 786      as load-insn
 787    - load-insn is reachable from test-insn
 788    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
 789
 790    This proof might fail when the compare and the load are fed
 791    by an insn not in the region.  To solve this, we will add to this
 792    group all loads that have no input DEF-USE dependence.
 793
 794    The second proof detects loads that are directly or indirectly
 795    fed by a speculative load.  This proof is affected by the
 796    scheduling process.  We will use the flag  fed_by_spec_load.
 797    Initially, all insns have this flag reset.  After a speculative
 798    motion of an insn, if insn is either a load, or marked as
 799    fed_by_spec_load, we will also mark as fed_by_spec_load every
 800    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
 801    load which is fed_by_spec_load is also PRISKY.
 802
 803    MFREE (maybe-free) loads are all the remaining loads. They may be
 804    exception-free, but we cannot prove it.
 805
 806    Now, all loads in IFREE and PFREE classes are considered
 807    exception-free, while all loads in IRISKY and PRISKY classes are
 808    considered exception-risky.  As for loads in the MFREE class,
 809    these are considered either exception-free or exception-risky,
 810    depending on whether we are pessimistic or optimistic.  We have
 811    to take the pessimistic approach to assure the safety of
 812    speculative scheduling, but we can take the optimistic approach
 813    by invoking the -fsched_spec_load_dangerous option.  */
 814
 815 enum INSN_TRAP_CLASS
 816 {
 817   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
 818   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
 819 };
 820
 821 #define WORST_CLASS(class1, class2) \
 822 ((class1 > class2) ? class1 : class2)
 823
 824 #ifndef __GNUC__
 825 #define __inline
 826 #endif
 827
 828 #ifndef HAIFA_INLINE
 829 #define HAIFA_INLINE __inline
 830 #endif
 831
 832 /* Functions in sched-vis.c.  */
 833 extern void print_insn (char *, rtx, int);
 834
 835 /* Functions in sched-deps.c.  */
 836 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
 837 extern void add_dependence (rtx, rtx, enum reg_note);
 838 extern void sched_analyze (struct deps *, rtx, rtx);
 839 extern void init_deps (struct deps *);
 840 extern void free_deps (struct deps *);
 841 extern void init_deps_global (void);
 842 extern void finish_deps_global (void);
 843 extern void add_forw_dep (dep_link_t);
 844 extern void compute_forward_dependences (rtx, rtx);
 845 extern void init_dependency_caches (int);
 846 extern void free_dependency_caches (void);
 847 extern void extend_dependency_caches (int, bool);
 848 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
 849                                                        enum reg_note, ds_t);
 850 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 851 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 852 extern void delete_back_forw_dep (dep_link_t);
 853 extern dw_t get_dep_weak (ds_t, ds_t);
 854 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
 855 extern ds_t ds_merge (ds_t, ds_t);
 856
 857 /* Functions in haifa-sched.c.  */
 858 extern int haifa_classify_insn (rtx);
 859 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
 860 extern int no_real_insns_p (rtx, rtx);
 861
 862 extern void rm_other_notes (rtx, rtx);
 863
 864 extern int insn_cost (rtx);
 865 extern int dep_cost (dep_t);
 866 extern int set_priorities (rtx, rtx);
 867
 868 extern void schedule_block (basic_block *, int);
 869 extern void sched_init (void);
 870 extern void sched_finish (void);
 871
 872 extern int try_ready (rtx);
 873 extern void * xrecalloc (void *, size_t, size_t, size_t);
 874 extern void unlink_bb_notes (basic_block, basic_block);
 875 extern void add_block (basic_block, basic_block);
 876 extern void attach_life_info (void);
 877 extern rtx bb_note (basic_block);
 878
 879 #ifdef ENABLE_CHECKING
 880 extern void check_reg_live (bool);
 881 #endif
 882
 883 /* Functions in sched-rgn.c.  */
 884 extern void debug_dependencies (rtx, rtx);
 885
 886 #endif /* GCC_SCHED_INT_H */