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