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