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, 1999, 2000,
   4    2001, 2003, 2004, 2005, 2006, 2007 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 #include "df.h"
  33
  34 /* Pointer to data describing the current DFA state.  */
  35 extern state_t curr_state;
  36
  37 /* Forward declaration.  */
  38 struct ready_list;
  39
  40 /* Type to represent status of a dependence.  */
  41 typedef int ds_t;
  42
  43 /* Type to represent weakness of speculative dependence.  */
  44 typedef int dw_t;
  45
  46 extern enum reg_note ds_to_dk (ds_t);
  47 extern ds_t dk_to_ds (enum reg_note);
  48
  49 /* Information about the dependency.  */
  50 struct _dep
  51 {
  52   /* Producer.  */
  53   rtx pro;
  54
  55   /* Consumer.  */
  56   rtx con;
  57
  58   /* Dependency kind (aka dependency major type).  This field is superseded
  59      by STATUS below.  Though, it is still in place because all the backends
  60      use it.  */
  61   enum reg_note kind;
  62
  63   /* Dependency status.  This field holds all dependency types and additional
  64      information for speculative dependencies.  */
  65   ds_t status;
  66 };
  67 typedef struct _dep *dep_t;
  68
  69 #define DEP_PRO(D) ((D)->pro)
  70 #define DEP_CON(D) ((D)->con)
  71 #define DEP_KIND(D) ((D)->kind)
  72 #define DEP_STATUS(D) ((D)->status)
  73
  74 /* Functions to work with dep.  */
  75
  76 extern void init_dep (dep_t, rtx, rtx, enum reg_note);
  77
  78 /* Definition of this struct resides below.  */
  79 struct _dep_node;
  80
  81 /* A link in the dependency list.  This is essentially an equivalent of a
  82    single {INSN, DEPS}_LIST rtx.  */
  83 struct _dep_link
  84 {
  85   /* Dep node with all the data.  */
  86   struct _dep_node *node;
  87
  88   /* Next link in the list. For the last one it is NULL.  */
  89   struct _dep_link *next;
  90
  91   /* Pointer to the next field of the previous link in the list.
  92      For the first link this points to the deps_list->first.
  93
  94      With help of this field it is easy to remove and insert links to the
  95      list.  */
  96   struct _dep_link **prev_nextp;
  97 };
  98 typedef struct _dep_link *dep_link_t;
  99
 100 #define DEP_LINK_NODE(N) ((N)->node)
 101 #define DEP_LINK_NEXT(N) ((N)->next)
 102 #define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)
 103
 104 /* Macros to work dep_link.  For most usecases only part of the dependency
 105    information is need.  These macros conveniently provide that piece of
 106    information.  */
 107
 108 #define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))
 109 #define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))
 110 #define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))
 111 #define DEP_LINK_KIND(N) (DEP_KIND (DEP_LINK_DEP (N)))
 112 #define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))
 113
 114 void debug_dep_links (dep_link_t);
 115
 116 /* A list of dep_links.  */
 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   /* ??? FIXME: should use straight bitfields inside sched_info instead of
 442      this flag field.  */
 443   unsigned int flags;
 444 };
 445
 446 /* This structure holds description of the properties for speculative
 447    scheduling.  */
 448 struct spec_info_def
 449 {
 450   /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
 451      BE_IN_{DATA_CONTROL}.  */
 452   int mask;
 453
 454   /* A dump file for additional information on speculative scheduling.  */
 455   FILE *dump;
 456
 457   /* Minimal cumulative weakness of speculative instruction's
 458      dependencies, so that insn will be scheduled.  */
 459   dw_t weakness_cutoff;
 460
 461   /* Flags from the enum SPEC_SCHED_FLAGS.  */
 462   int flags;
 463 };
 464 typedef struct spec_info_def *spec_info_t;
 465
 466 extern struct sched_info *current_sched_info;
 467
 468 /* Indexed by INSN_UID, the collection of all data associated with
 469    a single instruction.  */
 470
 471 struct haifa_insn_data
 472 {
 473   /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into
 474      h_i_d because when h_i_d extends, addresses of the deps_list->first
 475      change without updating deps_list->first->next->prev_nextp.  Thus
 476      BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS
 477      list is allocated on the obstack.  */
 478
 479   /* A list of backward dependencies.  The insn is a consumer of all the
 480      deps mentioned here.  */
 481   deps_list_t back_deps;
 482
 483   /* A list of insns which depend on the instruction.  Unlike 'back_deps',
 484      it represents forward dependencies.  */
 485   deps_list_t forw_deps;
 486
 487   /* A list of scheduled producers of the instruction.  Links are being moved
 488      from 'back_deps' to 'resolved_back_deps' while scheduling.  */
 489   deps_list_t resolved_back_deps;
 490
 491   /* Logical uid gives the original ordering of the insns.  */
 492   int luid;
 493
 494   /* A priority for each insn.  */
 495   int priority;
 496
 497   /* The number of incoming edges in the forward dependency graph.
 498      As scheduling proceeds, counts are decreased.  An insn moves to
 499      the ready queue when its counter reaches zero.  */
 500   int dep_count;
 501
 502   /* Number of instructions referring to this insn.  */
 503   int ref_count;
 504
 505   /* The minimum clock tick at which the insn becomes ready.  This is
 506      used to note timing constraints for the insns in the pending list.  */
 507   int tick;
 508
 509   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
 510      subsequent blocks in a region.  */
 511   int inter_tick;
 512
 513   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
 514   int queue_index;
 515
 516   short cost;
 517
 518   /* This weight is an estimation of the insn's contribution to
 519      register pressure.  */
 520   short reg_weight;
 521
 522   /* Some insns (e.g. call) are not allowed to move across blocks.  */
 523   unsigned int cant_move : 1;
 524
 525   /* Set if there's DEF-USE dependence between some speculatively
 526      moved load insn and this one.  */
 527   unsigned int fed_by_spec_load : 1;
 528   unsigned int is_load_insn : 1;
 529
 530   /* '> 0' if priority is valid,
 531      '== 0' if priority was not yet computed,
 532      '< 0' if priority in invalid and should be recomputed.  */
 533   signed char priority_status;
 534
 535   /* Nonzero if instruction has internal dependence
 536      (e.g. add_dependence was invoked with (insn == elem)).  */
 537   unsigned int has_internal_dep : 1;
 538
 539   /* What speculations are necessary to apply to schedule the instruction.  */
 540   ds_t todo_spec;
 541   /* What speculations were already applied.  */
 542   ds_t done_spec;
 543   /* What speculations are checked by this instruction.  */
 544   ds_t check_spec;
 545
 546   /* Recovery block for speculation checks.  */
 547   basic_block recovery_block;
 548
 549   /* Original pattern of the instruction.  */
 550   rtx orig_pat;
 551 };
 552
 553 extern struct haifa_insn_data *h_i_d;
 554
 555 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 556    sched-rgn.c.  */
 557 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
 558 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
 559 #define INSN_RESOLVED_BACK_DEPS(INSN) \
 560   (h_i_d[INSN_UID (INSN)].resolved_back_deps)
 561 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 562 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 563 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 564 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 565 #define INSN_PRIORITY_STATUS(INSN) (h_i_d[INSN_UID (INSN)].priority_status)
 566 #define INSN_PRIORITY_KNOWN(INSN) (INSN_PRIORITY_STATUS (INSN) > 0)
 567 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 568 #define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
 569 #define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
 570 #define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
 571 #define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
 572 #define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
 573 #define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
 574
 575 /* INSN is either a simple or a branchy speculation check.  */
 576 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
 577
 578 /* INSN is a speculation check that will simply reexecute the speculatively
 579    scheduled instruction if the speculation fails.  */
 580 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
 581   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
 582
 583 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
 584    speculation fails.  Insns in that block will reexecute the speculatively
 585    scheduled code and then will return immediately after INSN thus preserving
 586    semantics of the program.  */
 587 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
 588   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
 589
 590 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
 591    for speculative scheduling.  Namely, it is 4 integers in the range
 592    [0, MAX_DEP_WEAK] and 3 bits.
 593    The integers correspond to the probability of the dependence to *not*
 594    exist, it is the probability, that overcoming of this dependence will
 595    not be followed by execution of the recovery code.  Nevertheless,
 596    whatever high the probability of success is, recovery code should still
 597    be generated to preserve semantics of the program.  To find a way to
 598    get/set these integers, please refer to the {get, set}_dep_weak ()
 599    functions in sched-deps.c .
 600    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
 601    output- and anti- dependence.  It is not enough for speculative scheduling
 602    to know just the major type of all the dependence between two instructions,
 603    as only true dependence can be overcome.
 604    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
 605    for using to describe instruction's status.  It is set whenever instruction
 606    has at least one dependence, that cannot be overcame.
 607    See also: check_dep_status () in sched-deps.c .  */
 608
 609 /* We exclude sign bit.  */
 610 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
 611
 612 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
 613    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
 614    dep weakness.  */
 615 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
 616
 617 /* Mask of speculative weakness in dep_status.  */
 618 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
 619
 620 /* This constant means that dependence is fake with 99.999...% probability.
 621    This is the maximum value, that can appear in dep_status.
 622    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
 623    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
 624    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
 625 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
 626
 627 /* This constant means that dependence is 99.999...% real and it is a really
 628    bad idea to overcome it (though this can be done, preserving program
 629    semantics).  */
 630 #define MIN_DEP_WEAK 1
 631
 632 /* This constant represents 100% probability.
 633    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
 634 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
 635
 636 /* Default weakness of speculative dependence.  Used when we can't say
 637    neither bad nor good about the dependence.  */
 638 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
 639
 640 /* Offset for speculative weaknesses in dep_status.  */
 641 enum SPEC_TYPES_OFFSETS {
 642   BEGIN_DATA_BITS_OFFSET = 0,
 643   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 644   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 645   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
 646 };
 647
 648 /* The following defines provide numerous constants used to distinguish between
 649    different types of speculative dependencies.  */
 650
 651 /* Dependence can be overcome with generation of new data speculative
 652    instruction.  */
 653 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
 654
 655 /* This dependence is to the instruction in the recovery block, that was
 656    formed to recover after data-speculation failure.
 657    Thus, this dependence can overcome with generating of the copy of
 658    this instruction in the recovery block.  */
 659 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
 660
 661 /* Dependence can be overcome with generation of new control speculative
 662    instruction.  */
 663 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
 664
 665 /* This dependence is to the instruction in the recovery block, that was
 666    formed to recover after control-speculation failure.
 667    Thus, this dependence can be overcome with generating of the copy of
 668    this instruction in the recovery block.  */
 669 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
 670
 671 /* A few convenient combinations.  */
 672 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
 673 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
 674 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
 675 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
 676 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
 677
 678 /* Constants, that are helpful in iterating through dep_status.  */
 679 #define FIRST_SPEC_TYPE BEGIN_DATA
 680 #define LAST_SPEC_TYPE BE_IN_CONTROL
 681 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
 682
 683 /* Dependence on instruction can be of multiple types
 684    (e.g. true and output). This fields enhance REG_NOTE_KIND information
 685    of the dependence.  */
 686 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
 687 #define DEP_OUTPUT (DEP_TRUE << 1)
 688 #define DEP_ANTI (DEP_OUTPUT << 1)
 689
 690 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
 691
 692 /* Instruction has non-speculative dependence.  This bit represents the
 693    property of an instruction - not the one of a dependence.
 694    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
 695 #define HARD_DEP (DEP_ANTI << 1)
 696
 697 /* This represents the results of calling sched-deps.c functions,
 698    which modify dependencies.  Possible choices are: a dependence
 699    is already present and nothing has been changed; a dependence type
 700    has been changed; brand new dependence has been created.  */
 701 enum DEPS_ADJUST_RESULT {
 702   DEP_PRESENT = 1,
 703   DEP_CHANGED = 2,
 704   DEP_CREATED = 3
 705 };
 706
 707 /* Represents the bits that can be set in the flags field of the
 708    sched_info structure.  */
 709 enum SCHED_FLAGS {
 710   /* If set, generate links between instruction as DEPS_LIST.
 711      Otherwise, generate usual INSN_LIST links.  */
 712   USE_DEPS_LIST = 1,
 713   /* Perform data or control (or both) speculation.
 714      Results in generation of data and control speculative dependencies.
 715      Requires USE_DEPS_LIST set.  */
 716   DO_SPECULATION = USE_DEPS_LIST << 1,
 717   SCHED_RGN = DO_SPECULATION << 1,
 718   SCHED_EBB = SCHED_RGN << 1,
 719   /* Scheduler can possible create new basic blocks.  Used for assertions.  */
 720   NEW_BBS = SCHED_EBB << 1
 721 };
 722
 723 enum SPEC_SCHED_FLAGS {
 724   COUNT_SPEC_IN_CRITICAL_PATH = 1,
 725   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
 726   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
 727 };
 728
 729 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_KIND (NOTE) \
 730                                                != NOTE_INSN_BASIC_BLOCK))
 731
 732 extern FILE *sched_dump;
 733 extern int sched_verbose;
 734
 735 /* Exception Free Loads:
 736
 737    We define five classes of speculative loads: IFREE, IRISKY,
 738    PFREE, PRISKY, and MFREE.
 739
 740    IFREE loads are loads that are proved to be exception-free, just
 741    by examining the load insn.  Examples for such loads are loads
 742    from TOC and loads of global data.
 743
 744    IRISKY loads are loads that are proved to be exception-risky,
 745    just by examining the load insn.  Examples for such loads are
 746    volatile loads and loads from shared memory.
 747
 748    PFREE loads are loads for which we can prove, by examining other
 749    insns, that they are exception-free.  Currently, this class consists
 750    of loads for which we are able to find a "similar load", either in
 751    the target block, or, if only one split-block exists, in that split
 752    block.  Load2 is similar to load1 if both have same single base
 753    register.  We identify only part of the similar loads, by finding
 754    an insn upon which both load1 and load2 have a DEF-USE dependence.
 755
 756    PRISKY loads are loads for which we can prove, by examining other
 757    insns, that they are exception-risky.  Currently we have two proofs for
 758    such loads.  The first proof detects loads that are probably guarded by a
 759    test on the memory address.  This proof is based on the
 760    backward and forward data dependence information for the region.
 761    Let load-insn be the examined load.
 762    Load-insn is PRISKY iff ALL the following hold:
 763
 764    - insn1 is not in the same block as load-insn
 765    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
 766    - test-insn is either a compare or a branch, not in the same block
 767      as load-insn
 768    - load-insn is reachable from test-insn
 769    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
 770
 771    This proof might fail when the compare and the load are fed
 772    by an insn not in the region.  To solve this, we will add to this
 773    group all loads that have no input DEF-USE dependence.
 774
 775    The second proof detects loads that are directly or indirectly
 776    fed by a speculative load.  This proof is affected by the
 777    scheduling process.  We will use the flag  fed_by_spec_load.
 778    Initially, all insns have this flag reset.  After a speculative
 779    motion of an insn, if insn is either a load, or marked as
 780    fed_by_spec_load, we will also mark as fed_by_spec_load every
 781    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
 782    load which is fed_by_spec_load is also PRISKY.
 783
 784    MFREE (maybe-free) loads are all the remaining loads. They may be
 785    exception-free, but we cannot prove it.
 786
 787    Now, all loads in IFREE and PFREE classes are considered
 788    exception-free, while all loads in IRISKY and PRISKY classes are
 789    considered exception-risky.  As for loads in the MFREE class,
 790    these are considered either exception-free or exception-risky,
 791    depending on whether we are pessimistic or optimistic.  We have
 792    to take the pessimistic approach to assure the safety of
 793    speculative scheduling, but we can take the optimistic approach
 794    by invoking the -fsched_spec_load_dangerous option.  */
 795
 796 enum INSN_TRAP_CLASS
 797 {
 798   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
 799   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
 800 };
 801
 802 #define WORST_CLASS(class1, class2) \
 803 ((class1 > class2) ? class1 : class2)
 804
 805 #ifndef __GNUC__
 806 #define __inline
 807 #endif
 808
 809 #ifndef HAIFA_INLINE
 810 #define HAIFA_INLINE __inline
 811 #endif
 812
 813 /* Functions in sched-vis.c.  */
 814 extern void print_insn (char *, rtx, int);
 815
 816 /* Functions in sched-deps.c.  */
 817 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
 818 extern void add_dependence (rtx, rtx, enum reg_note);
 819 extern void sched_analyze (struct deps *, rtx, rtx);
 820 extern void init_deps (struct deps *);
 821 extern void free_deps (struct deps *);
 822 extern void init_deps_global (void);
 823 extern void finish_deps_global (void);
 824 extern void add_forw_dep (dep_link_t);
 825 extern void compute_forward_dependences (rtx, rtx);
 826 extern void init_dependency_caches (int);
 827 extern void free_dependency_caches (void);
 828 extern void extend_dependency_caches (int, bool);
 829 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
 830                                                        enum reg_note, ds_t);
 831 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 832 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 833 extern void delete_back_forw_dep (dep_link_t);
 834 extern dw_t get_dep_weak (ds_t, ds_t);
 835 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
 836 extern ds_t ds_merge (ds_t, ds_t);
 837
 838 /* Functions in haifa-sched.c.  */
 839 extern int haifa_classify_insn (rtx);
 840 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
 841 extern int no_real_insns_p (rtx, rtx);
 842
 843 extern void rm_other_notes (rtx, rtx);
 844
 845 extern int insn_cost (rtx);
 846 extern int dep_cost (dep_t);
 847 extern int set_priorities (rtx, rtx);
 848
 849 extern void schedule_block (basic_block *, int);
 850 extern void sched_init (void);
 851 extern void sched_finish (void);
 852
 853 extern int try_ready (rtx);
 854 extern void * xrecalloc (void *, size_t, size_t, size_t);
 855 extern void unlink_bb_notes (basic_block, basic_block);
 856 extern void add_block (basic_block, basic_block);
 857 extern rtx bb_note (basic_block);
 858
 859 /* Functions in sched-rgn.c.  */
 860 extern void debug_dependencies (rtx, rtx);
 861
 862 #endif /* GCC_SCHED_INT_H */