gcc/sched-int.h

   1 /* Instruction scheduling pass.  This file contains definitions used
   2    internally in the scheduler.
   3    Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998,
   4    1999, 2000, 2001, 2003, 2004, 2005, 2006 Free Software Foundation, Inc.
   5
   6 This file is part of GCC.
   7
   8 GCC is free software; you can redistribute it and/or modify it under
   9 the terms of the GNU General Public License as published by the Free
  10 Software Foundation; either version 2, or (at your option) any later
  11 version.
  12
  13 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  14 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  15 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  16 for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GCC; see the file COPYING.  If not, write to the Free
  20 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  21 02110-1301, USA.  */
  22
  23 #ifndef GCC_SCHED_INT_H
  24 #define GCC_SCHED_INT_H
  25
  26 /* For state_t.  */
  27 #include "insn-attr.h"
  28 /* For regset_head.  */
  29 #include "basic-block.h"
  30 /* For reg_note.  */
  31 #include "rtl.h"
  32
  33 /* Pointer to data describing the current DFA state.  */
  34 extern state_t curr_state;
  35
  36 /* Forward declaration.  */
  37 struct ready_list;
  38
  39 /* Type to represent status of a dependence.  */
  40 typedef int ds_t;
  41
  42 /* Type to represent weakness of speculative dependence.  */
  43 typedef int dw_t;
  44
  45 /* Describe state of dependencies used during sched_analyze phase.  */
  46 struct deps
  47 {
  48   /* The *_insns and *_mems are paired lists.  Each pending memory operation
  49      will have a pointer to the MEM rtx on one list and a pointer to the
  50      containing insn on the other list in the same place in the list.  */
  51
  52   /* We can't use add_dependence like the old code did, because a single insn
  53      may have multiple memory accesses, and hence needs to be on the list
  54      once for each memory access.  Add_dependence won't let you add an insn
  55      to a list more than once.  */
  56
  57   /* An INSN_LIST containing all insns with pending read operations.  */
  58   rtx pending_read_insns;
  59
  60   /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */
  61   rtx pending_read_mems;
  62
  63   /* An INSN_LIST containing all insns with pending write operations.  */
  64   rtx pending_write_insns;
  65
  66   /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */
  67   rtx pending_write_mems;
  68
  69   /* Indicates the combined length of the two pending lists.  We must prevent
  70      these lists from ever growing too large since the number of dependencies
  71      produced is at least O(N*N), and execution time is at least O(4*N*N), as
  72      a function of the length of these pending lists.  */
  73   int pending_lists_length;
  74
  75   /* Length of the pending memory flush list. Large functions with no
  76      calls may build up extremely large lists.  */
  77   int pending_flush_length;
  78
  79   /* The last insn upon which all memory references must depend.
  80      This is an insn which flushed the pending lists, creating a dependency
  81      between it and all previously pending memory references.  This creates
  82      a barrier (or a checkpoint) which no memory reference is allowed to cross.
  83
  84      This includes all non constant CALL_INSNs.  When we do interprocedural
  85      alias analysis, this restriction can be relaxed.
  86      This may also be an INSN that writes memory if the pending lists grow
  87      too large.  */
  88   rtx last_pending_memory_flush;
  89
  90   /* A list of the last function calls we have seen.  We use a list to
  91      represent last function calls from multiple predecessor blocks.
  92      Used to prevent register lifetimes from expanding unnecessarily.  */
  93   rtx last_function_call;
  94
  95   /* A list of insns which use a pseudo register that does not already
  96      cross a call.  We create dependencies between each of those insn
  97      and the next call insn, to ensure that they won't cross a call after
  98      scheduling is done.  */
  99   rtx sched_before_next_call;
 100
 101   /* Used to keep post-call pseudo/hard reg movements together with
 102      the call.  */
 103   enum { not_post_call, post_call, post_call_initial } in_post_call_group_p;
 104
 105   /* Set to the tail insn of the outermost libcall block.
 106
 107      When nonzero, we will mark each insn processed by sched_analyze_insn
 108      with SCHED_GROUP_P to ensure libcalls are scheduled as a unit.  */
 109   rtx libcall_block_tail_insn;
 110
 111   /* The maximum register number for the following arrays.  Before reload
 112      this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */
 113   int max_reg;
 114
 115   /* Element N is the next insn that sets (hard or pseudo) register
 116      N within the current basic block; or zero, if there is no
 117      such insn.  Needed for new registers which may be introduced
 118      by splitting insns.  */
 119   struct deps_reg
 120     {
 121       rtx uses;
 122       rtx sets;
 123       rtx clobbers;
 124       int uses_length;
 125       int clobbers_length;
 126     } *reg_last;
 127
 128   /* Element N is set for each register that has any nonzero element
 129      in reg_last[N].{uses,sets,clobbers}.  */
 130   regset_head reg_last_in_use;
 131
 132   /* Element N is set for each register that is conditionally set.  */
 133   regset_head reg_conditional_sets;
 134 };
 135
 136 /* This structure holds some state of the current scheduling pass, and
 137    contains some function pointers that abstract out some of the non-generic
 138    functionality from functions such as schedule_block or schedule_insn.
 139    There is one global variable, current_sched_info, which points to the
 140    sched_info structure currently in use.  */
 141 struct sched_info
 142 {
 143   /* Add all insns that are initially ready to the ready list.  Called once
 144      before scheduling a set of insns.  */
 145   void (*init_ready_list) (void);
 146   /* Called after taking an insn from the ready list.  Returns nonzero if
 147      this insn can be scheduled, nonzero if we should silently discard it.  */
 148   int (*can_schedule_ready_p) (rtx);
 149   /* Return nonzero if there are more insns that should be scheduled.  */
 150   int (*schedule_more_p) (void);
 151   /* Called after an insn has all its hard dependencies resolved.
 152      Adjusts status of instruction (which is passed through second parameter)
 153      to indicate if instruction should be moved to the ready list or the
 154      queue, or if it should silently discard it (until next resolved
 155      dependence).  */
 156   ds_t (*new_ready) (rtx, ds_t);
 157   /* Compare priority of two insns.  Return a positive number if the second
 158      insn is to be preferred for scheduling, and a negative one if the first
 159      is to be preferred.  Zero if they are equally good.  */
 160   int (*rank) (rtx, rtx);
 161   /* Return a string that contains the insn uid and optionally anything else
 162      necessary to identify this insn in an output.  It's valid to use a
 163      static buffer for this.  The ALIGNED parameter should cause the string
 164      to be formatted so that multiple output lines will line up nicely.  */
 165   const char *(*print_insn) (rtx, int);
 166   /* Return nonzero if an insn should be included in priority
 167      calculations.  */
 168   int (*contributes_to_priority) (rtx, rtx);
 169   /* Called when computing dependencies for a JUMP_INSN.  This function
 170      should store the set of registers that must be considered as set by
 171      the jump in the regset.  */
 172   void (*compute_jump_reg_dependencies) (rtx, regset, regset, regset);
 173
 174   /* The boundaries of the set of insns to be scheduled.  */
 175   rtx prev_head, next_tail;
 176
 177   /* Filled in after the schedule is finished; the first and last scheduled
 178      insns.  */
 179   rtx head, tail;
 180
 181   /* If nonzero, enables an additional sanity check in schedule_block.  */
 182   unsigned int queue_must_finish_empty:1;
 183   /* Nonzero if we should use cselib for better alias analysis.  This
 184      must be 0 if the dependency information is used after sched_analyze
 185      has completed, e.g. if we're using it to initialize state for successor
 186      blocks in region scheduling.  */
 187   unsigned int use_cselib:1;
 188
 189   /* Maximum priority that has been assigned to an insn.  */
 190   int sched_max_insns_priority;
 191
 192   /* Hooks to support speculative scheduling.  */
 193
 194   /* Called to notify frontend that instruction is being added (second
 195      parameter == 0) or removed (second parameter == 1).  */
 196   void (*add_remove_insn) (rtx, int);
 197
 198   /* Called to notify frontend that instruction is being scheduled.
 199      The first parameter - instruction to scheduled, the second parameter -
 200      last scheduled instruction.  */
 201   void (*begin_schedule_ready) (rtx, rtx);
 202
 203   /* Called to notify frontend, that new basic block is being added.
 204      The first parameter - new basic block.
 205      The second parameter - block, after which new basic block is being added,
 206      or EXIT_BLOCK_PTR, if recovery block is being added,
 207      or NULL, if standalone block is being added.  */
 208   void (*add_block) (basic_block, basic_block);
 209
 210   /* If the second parameter is not NULL, return nonnull value, if the
 211      basic block should be advanced.
 212      If the second parameter is NULL, return the next basic block in EBB.
 213      The first parameter is the current basic block in EBB.  */
 214   basic_block (*advance_target_bb) (basic_block, rtx);
 215
 216   /* Called after blocks were rearranged due to movement of jump instruction.
 217      The first parameter - index of basic block, in which jump currently is.
 218      The second parameter - index of basic block, in which jump used
 219      to be.
 220      The third parameter - index of basic block, that follows the second
 221      parameter.  */
 222   void (*fix_recovery_cfg) (int, int, int);
 223
 224 #ifdef ENABLE_CHECKING
 225   /* If the second parameter is zero, return nonzero, if block is head of the
 226      region.
 227      If the second parameter is nonzero, return nonzero, if block is leaf of
 228      the region.
 229      global_live_at_start should not change in region heads and
 230      global_live_at_end should not change in region leafs due to scheduling.  */
 231   int (*region_head_or_leaf_p) (basic_block, int);
 232 #endif
 233
 234   /* ??? FIXME: should use straight bitfields inside sched_info instead of
 235      this flag field.  */
 236   unsigned int flags;
 237 };
 238
 239 /* This structure holds description of the properties for speculative
 240    scheduling.  */
 241 struct spec_info_def
 242 {
 243   /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},
 244      BE_IN_{DATA_CONTROL}.  */
 245   int mask;
 246
 247   /* A dump file for additional information on speculative scheduling.  */
 248   FILE *dump;
 249
 250   /* Minimal cumulative weakness of speculative instruction's
 251      dependencies, so that insn will be scheduled.  */
 252   dw_t weakness_cutoff;
 253
 254   /* Flags from the enum SPEC_SCHED_FLAGS.  */
 255   int flags;
 256 };
 257 typedef struct spec_info_def *spec_info_t;
 258
 259 extern struct sched_info *current_sched_info;
 260
 261 /* Indexed by INSN_UID, the collection of all data associated with
 262    a single instruction.  */
 263
 264 struct haifa_insn_data
 265 {
 266   /* A list of insns which depend on the instruction.  Unlike LOG_LINKS,
 267      it represents forward dependencies.  */
 268   rtx depend;
 269
 270   /* A list of scheduled producers of the instruction.  Links are being moved
 271      from LOG_LINKS to RESOLVED_DEPS during scheduling.  */
 272   rtx resolved_deps;
 273
 274   /* The line number note in effect for each insn.  For line number
 275      notes, this indicates whether the note may be reused.  */
 276   rtx line_note;
 277
 278   /* Logical uid gives the original ordering of the insns.  */
 279   int luid;
 280
 281   /* A priority for each insn.  */
 282   int priority;
 283
 284   /* The number of incoming edges in the forward dependency graph.
 285      As scheduling proceeds, counts are decreased.  An insn moves to
 286      the ready queue when its counter reaches zero.  */
 287   int dep_count;
 288
 289   /* Number of instructions referring to this insn.  */
 290   int ref_count;
 291
 292   /* The minimum clock tick at which the insn becomes ready.  This is
 293      used to note timing constraints for the insns in the pending list.  */
 294   int tick;
 295
 296   /* INTER_TICK is used to adjust INSN_TICKs of instructions from the
 297      subsequent blocks in a region.  */
 298   int inter_tick;
 299
 300   /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */
 301   int queue_index;
 302
 303   short cost;
 304
 305   /* This weight is an estimation of the insn's contribution to
 306      register pressure.  */
 307   short reg_weight;
 308
 309   /* Some insns (e.g. call) are not allowed to move across blocks.  */
 310   unsigned int cant_move : 1;
 311
 312   /* Set if there's DEF-USE dependence between some speculatively
 313      moved load insn and this one.  */
 314   unsigned int fed_by_spec_load : 1;
 315   unsigned int is_load_insn : 1;
 316
 317   /* Nonzero if priority has been computed already.  */
 318   unsigned int priority_known : 1;
 319
 320   /* Nonzero if instruction has internal dependence
 321      (e.g. add_dependence was invoked with (insn == elem)).  */
 322   unsigned int has_internal_dep : 1;
 323
 324   /* What speculations are necessary to apply to schedule the instruction.  */
 325   ds_t todo_spec;
 326   /* What speculations were already applied.  */
 327   ds_t done_spec;
 328   /* What speculations are checked by this instruction.  */
 329   ds_t check_spec;
 330
 331   /* Recovery block for speculation checks.  */
 332   basic_block recovery_block;
 333
 334   /* Original pattern of the instruction.  */
 335   rtx orig_pat;
 336 };
 337
 338 extern struct haifa_insn_data *h_i_d;
 339 /* Used only if (current_sched_info->flags & USE_GLAT) != 0.
 340    These regsets store global_live_at_{start, end} information
 341    for each basic block.  */
 342 extern regset *glat_start, *glat_end;
 343
 344 /* Accessor macros for h_i_d.  There are more in haifa-sched.c and
 345    sched-rgn.c.  */
 346 #define INSN_DEPEND(INSN)       (h_i_d[INSN_UID (INSN)].depend)
 347 #define RESOLVED_DEPS(INSN)     (h_i_d[INSN_UID (INSN)].resolved_deps)
 348 #define INSN_LUID(INSN)         (h_i_d[INSN_UID (INSN)].luid)
 349 #define CANT_MOVE(insn)         (h_i_d[INSN_UID (insn)].cant_move)
 350 #define INSN_DEP_COUNT(INSN)    (h_i_d[INSN_UID (INSN)].dep_count)
 351 #define INSN_PRIORITY(INSN)     (h_i_d[INSN_UID (INSN)].priority)
 352 #define INSN_PRIORITY_KNOWN(INSN) (h_i_d[INSN_UID (INSN)].priority_known)
 353 #define INSN_COST(INSN)         (h_i_d[INSN_UID (INSN)].cost)
 354 #define INSN_REG_WEIGHT(INSN)   (h_i_d[INSN_UID (INSN)].reg_weight)
 355 #define HAS_INTERNAL_DEP(INSN)  (h_i_d[INSN_UID (INSN)].has_internal_dep)
 356 #define TODO_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].todo_spec)
 357 #define DONE_SPEC(INSN)         (h_i_d[INSN_UID (INSN)].done_spec)
 358 #define CHECK_SPEC(INSN)        (h_i_d[INSN_UID (INSN)].check_spec)
 359 #define RECOVERY_BLOCK(INSN)    (h_i_d[INSN_UID (INSN)].recovery_block)
 360 #define ORIG_PAT(INSN)          (h_i_d[INSN_UID (INSN)].orig_pat)
 361
 362 /* INSN is either a simple or a branchy speculation check.  */
 363 #define IS_SPECULATION_CHECK_P(INSN) (RECOVERY_BLOCK (INSN) != NULL)
 364
 365 /* INSN is a speculation check that will simply reexecute the speculatively
 366    scheduled instruction if the speculation fails.  */
 367 #define IS_SPECULATION_SIMPLE_CHECK_P(INSN) \
 368   (RECOVERY_BLOCK (INSN) == EXIT_BLOCK_PTR)
 369
 370 /* INSN is a speculation check that will branch to RECOVERY_BLOCK if the
 371    speculation fails.  Insns in that block will reexecute the speculatively
 372    scheduled code and then will return immediately after INSN thus preserving
 373    semantics of the program.  */
 374 #define IS_SPECULATION_BRANCHY_CHECK_P(INSN) \
 375   (RECOVERY_BLOCK (INSN) != NULL && RECOVERY_BLOCK (INSN) != EXIT_BLOCK_PTR)
 376
 377 /* DEP_STATUS of the link encapsulates information, that is needed for
 378    speculative scheduling.  Namely, it is 4 integers in the range
 379    [0, MAX_DEP_WEAK] and 3 bits.
 380    The integers correspond to the probability of the dependence to *not*
 381    exist, it is the probability, that overcoming of this dependence will
 382    not be followed by execution of the recovery code.  Nevertheless,
 383    whatever high the probability of success is, recovery code should still
 384    be generated to preserve semantics of the program.  To find a way to
 385    get/set these integers, please refer to the {get, set}_dep_weak ()
 386    functions in sched-deps.c .
 387    The 3 bits in the DEP_STATUS correspond to 3 dependence types: true-,
 388    output- and anti- dependence.  It is not enough for speculative scheduling
 389    to know just the major type of all the dependence between two instructions,
 390    as only true dependence can be overcome.
 391    There also is the 4-th bit in the DEP_STATUS (HARD_DEP), that is reserved
 392    for using to describe instruction's status.  It is set whenever instruction
 393    has at least one dependence, that cannot be overcome.
 394    See also: check_dep_status () in sched-deps.c .  */
 395 #define DEP_STATUS(LINK) XINT (LINK, 2)
 396
 397 /* We exclude sign bit.  */
 398 #define BITS_PER_DEP_STATUS (HOST_BITS_PER_INT - 1)
 399
 400 /* First '4' stands for 3 dep type bits and HARD_DEP bit.
 401    Second '4' stands for BEGIN_{DATA, CONTROL}, BE_IN_{DATA, CONTROL}
 402    dep weakness.  */
 403 #define BITS_PER_DEP_WEAK ((BITS_PER_DEP_STATUS - 4) / 4)
 404
 405 /* Mask of speculative weakness in dep_status.  */
 406 #define DEP_WEAK_MASK ((1 << BITS_PER_DEP_WEAK) - 1)
 407
 408 /* This constant means that dependence is fake with 99.999...% probability.
 409    This is the maximum value, that can appear in dep_status.
 410    Note, that we don't want MAX_DEP_WEAK to be the same as DEP_WEAK_MASK for
 411    debugging reasons.  Though, it can be set to DEP_WEAK_MASK, and, when
 412    done so, we'll get fast (mul for)/(div by) NO_DEP_WEAK.  */
 413 #define MAX_DEP_WEAK (DEP_WEAK_MASK - 1)
 414
 415 /* This constant means that dependence is 99.999...% real and it is a really
 416    bad idea to overcome it (though this can be done, preserving program
 417    semantics).  */
 418 #define MIN_DEP_WEAK 1
 419
 420 /* This constant represents 100% probability.
 421    E.g. it is used to represent weakness of dependence, that doesn't exist.  */
 422 #define NO_DEP_WEAK (MAX_DEP_WEAK + MIN_DEP_WEAK)
 423
 424 /* Default weakness of speculative dependence.  Used when we can't say
 425    neither bad nor good about the dependence.  */
 426 #define UNCERTAIN_DEP_WEAK (MAX_DEP_WEAK - MAX_DEP_WEAK / 4)
 427
 428 /* Offset for speculative weaknesses in dep_status.  */
 429 enum SPEC_TYPES_OFFSETS {
 430   BEGIN_DATA_BITS_OFFSET = 0,
 431   BE_IN_DATA_BITS_OFFSET = BEGIN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 432   BEGIN_CONTROL_BITS_OFFSET = BE_IN_DATA_BITS_OFFSET + BITS_PER_DEP_WEAK,
 433   BE_IN_CONTROL_BITS_OFFSET = BEGIN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK
 434 };
 435
 436 /* The following defines provide numerous constants used to distinguish between
 437    different types of speculative dependencies.  */
 438
 439 /* Dependence can be overcome with generation of new data speculative
 440    instruction.  */
 441 #define BEGIN_DATA (((ds_t) DEP_WEAK_MASK) << BEGIN_DATA_BITS_OFFSET)
 442
 443 /* This dependence is to the instruction in the recovery block, that was
 444    formed to recover after data-speculation failure.
 445    Thus, this dependence can overcome with generating of the copy of
 446    this instruction in the recovery block.  */
 447 #define BE_IN_DATA (((ds_t) DEP_WEAK_MASK) << BE_IN_DATA_BITS_OFFSET)
 448
 449 /* Dependence can be overcome with generation of new control speculative
 450    instruction.  */
 451 #define BEGIN_CONTROL (((ds_t) DEP_WEAK_MASK) << BEGIN_CONTROL_BITS_OFFSET)
 452
 453 /* This dependence is to the instruction in the recovery block, that was
 454    formed to recover after control-speculation failure.
 455    Thus, this dependence can be overcome with generating of the copy of
 456    this instruction in the recovery block.  */
 457 #define BE_IN_CONTROL (((ds_t) DEP_WEAK_MASK) << BE_IN_CONTROL_BITS_OFFSET)
 458
 459 /* A few convenient combinations.  */
 460 #define BEGIN_SPEC (BEGIN_DATA | BEGIN_CONTROL)
 461 #define DATA_SPEC (BEGIN_DATA | BE_IN_DATA)
 462 #define CONTROL_SPEC (BEGIN_CONTROL | BE_IN_CONTROL)
 463 #define SPECULATIVE (DATA_SPEC | CONTROL_SPEC)
 464 #define BE_IN_SPEC (BE_IN_DATA | BE_IN_CONTROL)
 465
 466 /* Constants, that are helpful in iterating through dep_status.  */
 467 #define FIRST_SPEC_TYPE BEGIN_DATA
 468 #define LAST_SPEC_TYPE BE_IN_CONTROL
 469 #define SPEC_TYPE_SHIFT BITS_PER_DEP_WEAK
 470
 471 /* Dependence on instruction can be of multiple types
 472    (e.g. true and output). This fields enhance REG_NOTE_KIND information
 473    of the dependence.  */
 474 #define DEP_TRUE (((ds_t) 1) << (BE_IN_CONTROL_BITS_OFFSET + BITS_PER_DEP_WEAK))
 475 #define DEP_OUTPUT (DEP_TRUE << 1)
 476 #define DEP_ANTI (DEP_OUTPUT << 1)
 477
 478 #define DEP_TYPES (DEP_TRUE | DEP_OUTPUT | DEP_ANTI)
 479
 480 /* Instruction has non-speculative dependence.  This bit represents the
 481    property of an instruction - not the one of a dependence.
 482    Therefore, it can appear only in TODO_SPEC field of an instruction.  */
 483 #define HARD_DEP (DEP_ANTI << 1)
 484
 485 /* This represents the results of calling sched-deps.c functions,
 486    which modify dependencies.  Possible choices are: a dependence
 487    is already present and nothing has been changed; a dependence type
 488    has been changed; brand new dependence has been created.  */
 489 enum DEPS_ADJUST_RESULT {
 490   DEP_PRESENT = 1,
 491   DEP_CHANGED = 2,
 492   DEP_CREATED = 3
 493 };
 494
 495 /* Represents the bits that can be set in the flags field of the
 496    sched_info structure.  */
 497 enum SCHED_FLAGS {
 498   /* If set, generate links between instruction as DEPS_LIST.
 499      Otherwise, generate usual INSN_LIST links.  */
 500   USE_DEPS_LIST = 1,
 501   /* Perform data or control (or both) speculation.
 502      Results in generation of data and control speculative dependencies.
 503      Requires USE_DEPS_LIST set.  */
 504   DO_SPECULATION = USE_DEPS_LIST << 1,
 505   SCHED_RGN = DO_SPECULATION << 1,
 506   SCHED_EBB = SCHED_RGN << 1,
 507   /* Detach register live information from basic block headers.
 508      This is necessary to invoke functions, that change CFG (e.g. split_edge).
 509      Requires USE_GLAT.  */
 510   DETACH_LIFE_INFO = SCHED_EBB << 1,
 511   /* Save register live information from basic block headers to
 512      glat_{start, end} arrays.  */
 513   USE_GLAT = DETACH_LIFE_INFO << 1
 514 };
 515
 516 enum SPEC_SCHED_FLAGS {
 517   COUNT_SPEC_IN_CRITICAL_PATH = 1,
 518   PREFER_NON_DATA_SPEC = COUNT_SPEC_IN_CRITICAL_PATH << 1,
 519   PREFER_NON_CONTROL_SPEC = PREFER_NON_DATA_SPEC << 1
 520 };
 521
 522 #define NOTE_NOT_BB_P(NOTE) (NOTE_P (NOTE) && (NOTE_LINE_NUMBER (NOTE)  \
 523                                                != NOTE_INSN_BASIC_BLOCK))
 524
 525 extern FILE *sched_dump;
 526 extern int sched_verbose;
 527
 528 /* Exception Free Loads:
 529
 530    We define five classes of speculative loads: IFREE, IRISKY,
 531    PFREE, PRISKY, and MFREE.
 532
 533    IFREE loads are loads that are proved to be exception-free, just
 534    by examining the load insn.  Examples for such loads are loads
 535    from TOC and loads of global data.
 536
 537    IRISKY loads are loads that are proved to be exception-risky,
 538    just by examining the load insn.  Examples for such loads are
 539    volatile loads and loads from shared memory.
 540
 541    PFREE loads are loads for which we can prove, by examining other
 542    insns, that they are exception-free.  Currently, this class consists
 543    of loads for which we are able to find a "similar load", either in
 544    the target block, or, if only one split-block exists, in that split
 545    block.  Load2 is similar to load1 if both have same single base
 546    register.  We identify only part of the similar loads, by finding
 547    an insn upon which both load1 and load2 have a DEF-USE dependence.
 548
 549    PRISKY loads are loads for which we can prove, by examining other
 550    insns, that they are exception-risky.  Currently we have two proofs for
 551    such loads.  The first proof detects loads that are probably guarded by a
 552    test on the memory address.  This proof is based on the
 553    backward and forward data dependence information for the region.
 554    Let load-insn be the examined load.
 555    Load-insn is PRISKY iff ALL the following hold:
 556
 557    - insn1 is not in the same block as load-insn
 558    - there is a DEF-USE dependence chain (insn1, ..., load-insn)
 559    - test-insn is either a compare or a branch, not in the same block
 560      as load-insn
 561    - load-insn is reachable from test-insn
 562    - there is a DEF-USE dependence chain (insn1, ..., test-insn)
 563
 564    This proof might fail when the compare and the load are fed
 565    by an insn not in the region.  To solve this, we will add to this
 566    group all loads that have no input DEF-USE dependence.
 567
 568    The second proof detects loads that are directly or indirectly
 569    fed by a speculative load.  This proof is affected by the
 570    scheduling process.  We will use the flag  fed_by_spec_load.
 571    Initially, all insns have this flag reset.  After a speculative
 572    motion of an insn, if insn is either a load, or marked as
 573    fed_by_spec_load, we will also mark as fed_by_spec_load every
 574    insn1 for which a DEF-USE dependence (insn, insn1) exists.  A
 575    load which is fed_by_spec_load is also PRISKY.
 576
 577    MFREE (maybe-free) loads are all the remaining loads. They may be
 578    exception-free, but we cannot prove it.
 579
 580    Now, all loads in IFREE and PFREE classes are considered
 581    exception-free, while all loads in IRISKY and PRISKY classes are
 582    considered exception-risky.  As for loads in the MFREE class,
 583    these are considered either exception-free or exception-risky,
 584    depending on whether we are pessimistic or optimistic.  We have
 585    to take the pessimistic approach to assure the safety of
 586    speculative scheduling, but we can take the optimistic approach
 587    by invoking the -fsched_spec_load_dangerous option.  */
 588
 589 enum INSN_TRAP_CLASS
 590 {
 591   TRAP_FREE = 0, IFREE = 1, PFREE_CANDIDATE = 2,
 592   PRISKY_CANDIDATE = 3, IRISKY = 4, TRAP_RISKY = 5
 593 };
 594
 595 #define WORST_CLASS(class1, class2) \
 596 ((class1 > class2) ? class1 : class2)
 597
 598 #ifndef __GNUC__
 599 #define __inline
 600 #endif
 601
 602 #ifndef HAIFA_INLINE
 603 #define HAIFA_INLINE __inline
 604 #endif
 605
 606 /* Functions in sched-vis.c.  */
 607 extern void print_insn (char *, rtx, int);
 608
 609 /* Functions in sched-deps.c.  */
 610 extern bool sched_insns_conditions_mutex_p (rtx, rtx);
 611 extern void add_dependence (rtx, rtx, enum reg_note);
 612 extern void sched_analyze (struct deps *, rtx, rtx);
 613 extern void init_deps (struct deps *);
 614 extern void free_deps (struct deps *);
 615 extern void init_deps_global (void);
 616 extern void finish_deps_global (void);
 617 extern void add_forw_dep (rtx, rtx);
 618 extern void compute_forward_dependences (rtx, rtx);
 619 extern rtx find_insn_list (rtx, rtx);
 620 extern void init_dependency_caches (int);
 621 extern void free_dependency_caches (void);
 622 extern void extend_dependency_caches (int, bool);
 623 extern enum DEPS_ADJUST_RESULT add_or_update_back_dep (rtx, rtx,
 624                                                        enum reg_note, ds_t);
 625 extern void add_or_update_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 626 extern void add_back_forw_dep (rtx, rtx, enum reg_note, ds_t);
 627 extern void delete_back_forw_dep (rtx, rtx);
 628 extern dw_t get_dep_weak (ds_t, ds_t);
 629 extern ds_t set_dep_weak (ds_t, ds_t, dw_t);
 630 extern ds_t ds_merge (ds_t, ds_t);
 631
 632 /* Functions in haifa-sched.c.  */
 633 extern int haifa_classify_insn (rtx);
 634 extern void get_ebb_head_tail (basic_block, basic_block, rtx *, rtx *);
 635 extern int no_real_insns_p (rtx, rtx);
 636
 637 extern void rm_line_notes (rtx, rtx);
 638 extern void save_line_notes (int, rtx, rtx);
 639 extern void restore_line_notes (rtx, rtx);
 640 extern void rm_redundant_line_notes (void);
 641 extern void rm_other_notes (rtx, rtx);
 642
 643 extern int insn_cost (rtx, rtx, rtx);
 644 extern int set_priorities (rtx, rtx);
 645
 646 extern void schedule_block (basic_block *, int);
 647 extern void sched_init (void);
 648 extern void sched_finish (void);
 649
 650 extern int try_ready (rtx);
 651 extern void * xrecalloc (void *, size_t, size_t, size_t);
 652 extern void unlink_bb_notes (basic_block, basic_block);
 653 extern void add_block (basic_block, basic_block);
 654 extern void attach_life_info (void);
 655 extern rtx bb_note (basic_block);
 656
 657 #ifdef ENABLE_CHECKING
 658 extern void check_reg_live (bool);
 659 #endif
 660
 661 #endif /* GCC_SCHED_INT_H */