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   /* Nonzero if priority has been computed already.  */
 541   unsigned int priority_known : 1;
 542
 543   /* Nonzero if instruction has internal dependence
 544      (e.g. add_dependence was invoked with (insn == elem)).  */
 545   unsigned int has_internal_dep : 1;
 546
 547   /* What speculations are necessary to apply to schedule the instruction.  */
 548   ds_t todo_spec;
 549   /* What speculations were already applied.  */
 550   ds_t done_spec;
 551   /* What speculations are checked by this instruction.  */
 552   ds_t check_spec;
 553
 554   /* Recovery block for speculation checks.  */
 555   basic_block recovery_block;
 556
 557   /* Original pattern of the instruction.  */
 558   rtx orig_pat;
 559 };
 560
 561 extern struct haifa_insn_data *h_i_d;
 562 /* Used only if (current_sched_info->flags & USE_GLAT) != 0.
 563    These regsets store global_live_at_{start, end} information
 564    for each basic block.  */
 565 extern regset *glat_start, *glat_end;
 566
 567 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 568    sched-rgn.c.  */
 569 #define INSN_BACK_DEPS(INSN) (h_i_d[INSN_UID (INSN)].back_deps)
 570 #define INSN_FORW_DEPS(INSN) (h_i_d[INSN_UID (INSN)].forw_deps)
 571 #define INSN_RESOLVED_BACK_DEPS(INSN) \
 572   (h_i_d[INSN_UID (INSN)].resolved_back_deps)
 573 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 574 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 575 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 576 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 577 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
 578 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 579 #define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
 580 #define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
 581 #define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
 582 #define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
 583 #define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
 584 #define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
 585
 586 /* INSN is either a simple or a branchy speculation check.  */
 587 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
 588
 589 /* INSN is a speculation check that will simply reexecute the speculatively
 590    scheduled instruction if the speculation fails.  */
 591 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
 592   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
 593
 594 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
 595    speculation fails.  Insns in that block will reexecute the speculatively
 596    scheduled code and then will return immediately after INSN thus preserving
 597    semantics of the program.  */
 598 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
 599   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
 600
 601 /* Dep status (aka ds_t) of the link encapsulates information, that is needed
 602    for speculative scheduling.  Namely, it is 4 integers in the range
 603    [0, MAX_DEP_WEAK] and 3 bits.
 604    The integers correspond to the probability of the dependence to *not*
 605    exist, it is the probability, that overcoming of this dependence will
 606    not be followed by execution of the recovery code.  Nevertheless,
 607    whatever high the probability of success is, recovery code should still
 608    be generated to preserve semantics of the program.  To find a way to
 609    get/set these integers, please refer to the {get, set}_dep_weak ()
 610    functions in sched-deps.c .
 611    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
 612    output- and anti- dependence.  It is not enough for speculative scheduling
 613    to know just the major type of all the dependence between two instructions,
 614    as only true dependence can be overcome.
 615    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
 616    for using to describe instruction's status.  It is set whenever instruction
 617    has at least one dependence, that cannot be overcame.
 618    See also: check_dep_status () in sched-deps.c .  */
 619
 620 /* We exclude sign bit.  */
 621 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
 622
 623 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
 624    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
 625    dep weakness.  */
 626 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
 627
 628 /* Mask of speculative weakness in dep_status.  */
 629 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
 630
 631 /* This constant means that dependence is fake with 99.999...% probability.
 632    This is the maximum value, that can appear in dep_status.
 633    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
 634    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
 635    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
 636 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
 637
 638 /* This constant means that dependence is 99.999...% real and it is a really
 639    bad idea to overcome it (though this can be done, preserving program
 640    semantics).  */
 641 #define MIN_DEP_WEAK 1
 642
 643 /* This constant represents 100% probability.
 644    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
 645 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
 646
 647 /* Default weakness of speculative dependence.  Used when we can't say
 648    neither bad nor good about the dependence.  */
 649 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
 650
 651 /* Offset for speculative weaknesses in dep_status.  */
 652 enum SPEC_TYPES_OFFSETS {
 653   BEGIN_DATA_BITS_OFFSET = 0,
 654   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 655   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 656   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
 657 };
 658
 659 /* The following defines provide numerous constants used to distinguish between
 660    different types of speculative dependencies.  */
 661
 662 /* Dependence can be overcome with generation of new data speculative
 663    instruction.  */
 664 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
 665
 666 /* This dependence is to the instruction in the recovery block, that was
 667    formed to recover after data-speculation failure.
 668    Thus, this dependence can overcome with generating of the copy of
 669    this instruction in the recovery block.  */
 670 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
 671
 672 /* Dependence can be overcome with generation of new control speculative
 673    instruction.  */
 674 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
 675
 676 /* This dependence is to the instruction in the recovery block, that was
 677    formed to recover after control-speculation failure.
 678    Thus, this dependence can be overcome with generating of the copy of
 679    this instruction in the recovery block.  */
 680 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
 681
 682 /* A few convenient combinations.  */
 683 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
 684 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
 685 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
 686 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
 687 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
 688
 689 /* Constants, that are helpful in iterating through dep_status.  */
 690 #define FIRST_SPEC_TYPE BEGIN_DATA
 691 #define LAST_SPEC_TYPE BE_IN_CONTROL
 692 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
 693
 694 /* Dependence on instruction can be of multiple types
 695    (e.g. true and output). This fields enhance REG_NOTE_KIND information
 696    of the dependence.  */
 697 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
 698 #define DEP_OUTPUT (DEP_TRUE << 1)
 699 #define DEP_ANTI (DEP_OUTPUT << 1)
 700
 701 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
 702
 703 /* Instruction has non-speculative dependence.  This bit represents the
 704    property of an instruction - not the one of a dependence.
 705    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
 706 #define HARD_DEP (DEP_ANTI << 1)
 707
 708 /* This represents the results of calling sched-deps.c functions,
 709    which modify dependencies.  Possible choices are: a dependence
 710    is already present and nothing has been changed; a dependence type
 711    has been changed; brand new dependence has been created.  */
 712 enum DEPS_ADJUST_RESULT {
 713   DEP_PRESENT = 1,
 714   DEP_CHANGED = 2,
 715   DEP_CREATED = 3
 716 };
 717
 718 /* Represents the bits that can be set in the flags field of the
 719    sched_info structure.  */
 720 enum SCHED_FLAGS {
 721   /* If set, generate links between instruction as DEPS_LIST.
 722      Otherwise, generate usual INSN_LIST links.  */
 723   USE_DEPS_LIST = 1,
 724   /* Perform data or control (or both) speculation.
 725      Results in generation of data and control speculative dependencies.
 726      Requires USE_DEPS_LIST set.  */
 727   DO_SPECULATION = USE_DEPS_LIST << 1,
 728   SCHED_RGN = DO_SPECULATION << 1,
 729   SCHED_EBB = SCHED_RGN << 1,
 730   /* Detach register live information from basic block headers.
 731      This is necessary to invoke functions, that change CFG (e.g. split_edge).
 732      Requires USE_GLAT.  */
 733   DETACH_LIFE_INFO = SCHED_EBB << 1,
 734   /* Save register live information from basic block headers to
 735      glat_{start, end} arrays.  */
 736   USE_GLAT = DETACH_LIFE_INFO << 1
 737 };
 738
 739 enum SPEC_SCHED_FLAGS {
 740   COUNT_SPEC_IN_CRITICAL_PATH = 1,
 741   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
 742   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
 743 };
 744
 745 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE)  \
 746                                                != NOTE_INSN_BASIC_BLOCK))
 747
 748 extern FILE *sched_dump;
 749 extern int sched_verbose;
 750
 751 /* Exception Free Loads:
 752
 753    We define five classes of speculative loads: IFREE, IRISKY,
 754    PFREE, PRISKY, and MFREE.
 755
 756    IFREE loads are loads that are proved to be exception-free, just
 757    by examining the load insn.  Examples for such loads are loads
 758    from TOC and loads of global data.
 759
 760    IRISKY loads are loads that are proved to be exception-risky,
 761    just by examining the load insn.  Examples for such loads are
 762    volatile loads and loads from shared memory.
 763
 764    PFREE loads are loads for which we can prove, by examining other
 765    insns, that they are exception-free.  Currently, this class consists
 766    of loads for which we are able to find a "similar load", either in
 767    the target block, or, if only one split-block exists, in that split
 768    block.  Load2 is similar to load1 if both have same single base
 769    register.  We identify only part of the similar loads, by finding
 770    an insn upon which both load1 and load2 have a DEF-USE dependence.
 771
 772    PRISKY loads are loads for which we can prove, by examining other
 773    insns, that they are exception-risky.  Currently we have two proofs for
 774    such loads.  The first proof detects loads that are probably guarded by a
 775    test on the memory address.  This proof is based on the
 776    backward and forward data dependence information for the region.
 777    Let load-insn be the examined load.
 778    Load-insn is PRISKY iff ALL the following hold:
 779
 780    - insn1 is not in the same block as load-insn
 781    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
 782    - test-insn is either a compare or a branch, not in the same block
 783      as load-insn
 784    - load-insn is reachable from test-insn
 785    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
 786
 787    This proof might fail when the compare and the load are fed
 788    by an insn not in the region.  To solve this, we will add to this
 789    group all loads that have no input DEF-USE dependence.
 790
 791    The second proof detects loads that are directly or indirectly
 792    fed by a speculative load.  This proof is affected by the
 793    scheduling process.  We will use the flag  fed_by_spec_load.
 794    Initially, all insns have this flag reset.  After a speculative
 795    motion of an insn, if insn is either a load, or marked as
 796    fed_by_spec_load, we will also mark as fed_by_spec_load every
 797    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
 798    load which is fed_by_spec_load is also PRISKY.
 799
 800    MFREE (maybe-free) loads are all the remaining loads. They may be
 801    exception-free, but we cannot prove it.
 802
 803    Now, all loads in IFREE and PFREE classes are considered
 804    exception-free, while all loads in IRISKY and PRISKY classes are
 805    considered exception-risky.  As for loads in the MFREE class,
 806    these are considered either exception-free or exception-risky,
 807    depending on whether we are pessimistic or optimistic.  We have
 808    to take the pessimistic approach to assure the safety of
 809    speculative scheduling, but we can take the optimistic approach
 810    by invoking the -fsched_spec_load_dangerous option.  */
 811
 812 enum INSN_TRAP_CLASS
 813 {
 814   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
 815   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
 816 };
 817
 818 #define WORST_CLASS(class1, class2) \
 819 ((class1 > class2) ? class1 : class2)
 820
 821 #ifndef __GNUC__
 822 #define __inline
 823 #endif
 824
 825 #ifndef HAIFA_INLINE
 826 #define HAIFA_INLINE __inline
 827 #endif
 828
 829 /* Functions in sched-vis.c.  */
 830 extern void print_insn (char *, rtx, int);
 831
 832 /* Functions in sched-deps.c.  */
 833 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
 834 extern void add_dependence (rtx, rtx, enum reg_note);
 835 extern void sched_analyze (struct deps *, rtx, rtx);
 836 extern void init_deps (struct deps *);
 837 extern void free_deps (struct deps *);
 838 extern void init_deps_global (void);
 839 extern void finish_deps_global (void);
 840 extern void add_forw_dep (dep_link_t);
 841 extern void compute_forward_dependences (rtx, rtx);
 842 extern void init_dependency_caches (int);
 843 extern void free_dependency_caches (void);
 844 extern void extend_dependency_caches (int, bool);
 845 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
 846                                                        enum reg_note, ds_t);
 847 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 848 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 849 extern void delete_back_forw_dep (dep_link_t);
 850 extern dw_t get_dep_weak (ds_t, ds_t);
 851 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
 852 extern ds_t ds_merge (ds_t, ds_t);
 853
 854 /* Functions in haifa-sched.c.  */
 855 extern int haifa_classify_insn (rtx);
 856 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
 857 extern int no_real_insns_p (rtx, rtx);
 858
 859 extern void rm_other_notes (rtx, rtx);
 860
 861 extern int insn_cost (rtx);
 862 extern int dep_cost (dep_t);
 863 extern int set_priorities (rtx, rtx);
 864
 865 extern void schedule_block (basic_block *, int);
 866 extern void sched_init (void);
 867 extern void sched_finish (void);
 868
 869 extern int try_ready (rtx);
 870 extern void * xrecalloc (void *, size_t, size_t, size_t);
 871 extern void unlink_bb_notes (basic_block, basic_block);
 872 extern void add_block (basic_block, basic_block);
 873 extern void attach_life_info (void);
 874 extern rtx bb_note (basic_block);
 875
 876 #ifdef ENABLE_CHECKING
 877 extern void check_reg_live (bool);
 878 #endif
 879
 880 #endif /* GCC_SCHED_INT_H */