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