Subversion Repositories openrisc

/* Instruction scheduling pass.  This file contains definitions used

   internally in the scheduler.

   Copyright (C) 1992, 1993, 1994, 1995, 1996, 1997, 1998, 1999, 2000,

   2001, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010

   Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under

the terms of the GNU General Public License as published by the Free

Software Foundation; either version 3, or (at your option) any later

version.

GCC is distributed in the hope that it will be useful, but WITHOUT ANY

WARRANTY; without even the implied warranty of MERCHANTABILITY or

FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

for more details.

You should have received a copy of the GNU General Public License

along with GCC; see the file COPYING3.  If not see

<http://www.gnu.org/licenses/>.  */

#ifndef GCC_SCHED_INT_H

#define GCC_SCHED_INT_H

#ifdef INSN_SCHEDULING

/* For state_t.  */

#include "insn-attr.h"

#include "df.h"

#include "basic-block.h"

/* For VEC (int, heap).  */

#include "vecprim.h"

/* Identificator of a scheduler pass.  */

enum sched_pass_id_t { SCHED_PASS_UNKNOWN, SCHED_RGN_PASS, SCHED_EBB_PASS,

                       SCHED_SMS_PASS, SCHED_SEL_PASS };

typedef VEC (basic_block, heap) *bb_vec_t;

typedef VEC (rtx, heap) *insn_vec_t;

typedef VEC (rtx, heap) *rtx_vec_t;

extern void sched_init_bbs (void);

extern void sched_extend_luids (void);

extern void sched_init_insn_luid (rtx);

extern void sched_init_luids (bb_vec_t);

extern void sched_finish_luids (void);

extern void sched_extend_target (void);

extern void haifa_init_h_i_d (bb_vec_t);

extern void haifa_finish_h_i_d (void);

/* Hooks that are common to all the schedulers.  */

struct common_sched_info_def

{

  /* Called after blocks were rearranged due to movement of jump instruction.

     The first parameter - index of basic block, in which jump currently is.

     The second parameter - index of basic block, in which jump used

     to be.

     The third parameter - index of basic block, that follows the second

     parameter.  */

  void (*fix_recovery_cfg) (int, int, int);

  /* Called to notify frontend, that new basic block is being added.

     The first parameter - new basic block.

     The second parameter - block, after which new basic block is being added,

     or EXIT_BLOCK_PTR, if recovery block is being added,

     or NULL, if standalone block is being added.  */

  void (*add_block) (basic_block, basic_block);

  /* Estimate number of insns in the basic block.  */

  int (*estimate_number_of_insns) (basic_block);

  /* Given a non-insn (!INSN_P (x)) return

     -1 - if this rtx don't need a luid.

     1 - if it needs a separate luid.  */

  int (*luid_for_non_insn) (rtx);

  /* Scheduler pass identifier.  It is preferably used in assertions.  */

  enum sched_pass_id_t sched_pass_id;

};

extern struct common_sched_info_def *common_sched_info;

extern const struct common_sched_info_def haifa_common_sched_info;

/* Return true if selective scheduling pass is working.  */

static inline bool

sel_sched_p (void)

{

  return common_sched_info->sched_pass_id == SCHED_SEL_PASS;

}

/* Returns maximum priority that an insn was assigned to.  */

extern int get_rgn_sched_max_insns_priority (void);

/* Increases effective priority for INSN by AMOUNT.  */

extern void sel_add_to_insn_priority (rtx, int);

/* True if during selective scheduling we need to emulate some of haifa

   scheduler behaviour.  */

extern int sched_emulate_haifa_p;

/* Mapping from INSN_UID to INSN_LUID.  In the end all other per insn data

   structures should be indexed by luid.  */

extern VEC (int, heap) *sched_luids;

#define INSN_LUID(INSN) (VEC_index (int, sched_luids, INSN_UID (INSN)))

#define LUID_BY_UID(UID) (VEC_index (int, sched_luids, UID))

#define SET_INSN_LUID(INSN, LUID) \

(VEC_replace (int, sched_luids, INSN_UID (INSN), (LUID)))

/* The highest INSN_LUID.  */

extern int sched_max_luid;

extern int insn_luid (rtx);

/* This list holds ripped off notes from the current block.  These notes will

   be attached to the beginning of the block when its scheduling is

   finished.  */

extern rtx note_list;

extern void remove_notes (rtx, rtx);

extern rtx restore_other_notes (rtx, basic_block);

extern void sched_insns_init (rtx);

extern void sched_insns_finish (void);

extern void *xrecalloc (void *, size_t, size_t, size_t);

extern void reemit_notes (rtx);

/* Functions in haifa-sched.c.  */

extern int haifa_classify_insn (const_rtx);

/* Functions in sel-sched-ir.c.  */

extern void sel_find_rgns (void);

extern void sel_mark_hard_insn (rtx);

extern size_t dfa_state_size;

extern void advance_state (state_t);

extern void setup_sched_dump (void);

extern void sched_init (void);

extern void sched_finish (void);

extern bool sel_insn_is_speculation_check (rtx);

/* Describe the ready list of the scheduler.

   VEC holds space enough for all insns in the current region.  VECLEN

   says how many exactly.

   FIRST is the index of the element with the highest priority; i.e. the

   last one in the ready list, since elements are ordered by ascending

   priority.

   N_READY determines how many insns are on the ready list.

   N_DEBUG determines how many debug insns are on the ready list.  */

struct ready_list

{

  rtx *vec;

  int veclen;

  int first;

  int n_ready;

  int n_debug;

};

extern char *ready_try;

extern struct ready_list ready;

extern int max_issue (struct ready_list *, int, state_t, bool, int *);

extern void ebb_compute_jump_reg_dependencies (rtx, regset);

extern edge find_fallthru_edge_from (basic_block);

extern void (* sched_init_only_bb) (basic_block, basic_block);

extern basic_block (* sched_split_block) (basic_block, rtx);

extern basic_block sched_split_block_1 (basic_block, rtx);

extern basic_block (* sched_create_empty_bb) (basic_block);

extern basic_block sched_create_empty_bb_1 (basic_block);

extern basic_block sched_create_recovery_block (basic_block *);

extern void sched_create_recovery_edges (basic_block, basic_block,

                                         basic_block);

/* Pointer to data describing the current DFA state.  */

extern state_t curr_state;

/* Type to represent status of a dependence.  */

typedef int ds_t;

/* Type to represent weakness of speculative dependence.  */

typedef int dw_t;

extern enum reg_note ds_to_dk (ds_t);

extern ds_t dk_to_ds (enum reg_note);

/* Information about the dependency.  */

struct _dep

{

  /* Producer.  */

  rtx pro;

  /* Consumer.  */

  rtx con;

  /* Dependency major type.  This field is superseded by STATUS below.

     Though, it is still in place because some targets use it.  */

  enum reg_note type;

  /* Dependency status.  This field holds all dependency types and additional

     information for speculative dependencies.  */

  ds_t status;

  /* Cached cost of the dependency.  */

  int cost;

};

typedef struct _dep dep_def;

typedef dep_def *dep_t;

#define DEP_PRO(D) ((D)->pro)

#define DEP_CON(D) ((D)->con)

#define DEP_TYPE(D) ((D)->type)

#define DEP_STATUS(D) ((D)->status)

#define DEP_COST(D) ((D)->cost)

#define UNKNOWN_DEP_COST INT_MIN

/* Functions to work with dep.  */

extern void init_dep_1 (dep_t, rtx, rtx, enum reg_note, ds_t);

extern void init_dep (dep_t, rtx, rtx, enum reg_note);

extern void sd_debug_dep (dep_t);

/* Definition of this struct resides below.  */

struct _dep_node;

typedef struct _dep_node *dep_node_t;

/* A link in the dependency list.  This is essentially an equivalent of a

   single {INSN, DEPS}_LIST rtx.  */

struct _dep_link

{

  /* Dep node with all the data.  */

  dep_node_t node;

  /* Next link in the list. For the last one it is NULL.  */

  struct _dep_link *next;

  /* Pointer to the next field of the previous link in the list.

     For the first link this points to the deps_list->first.

     With help of this field it is easy to remove and insert links to the

     list.  */

  struct _dep_link **prev_nextp;

};

typedef struct _dep_link *dep_link_t;

#define DEP_LINK_NODE(N) ((N)->node)

#define DEP_LINK_NEXT(N) ((N)->next)

#define DEP_LINK_PREV_NEXTP(N) ((N)->prev_nextp)

/* Macros to work dep_link.  For most usecases only part of the dependency

   information is need.  These macros conveniently provide that piece of

   information.  */

#define DEP_LINK_DEP(N) (DEP_NODE_DEP (DEP_LINK_NODE (N)))

#define DEP_LINK_PRO(N) (DEP_PRO (DEP_LINK_DEP (N)))

#define DEP_LINK_CON(N) (DEP_CON (DEP_LINK_DEP (N)))

#define DEP_LINK_TYPE(N) (DEP_TYPE (DEP_LINK_DEP (N)))

#define DEP_LINK_STATUS(N) (DEP_STATUS (DEP_LINK_DEP (N)))

/* A list of dep_links.  */

struct _deps_list

{

  /* First element.  */

  dep_link_t first;

  /* Total number of elements in the list.  */

  int n_links;

};

typedef struct _deps_list *deps_list_t;

#define DEPS_LIST_FIRST(L) ((L)->first)

#define DEPS_LIST_N_LINKS(L) ((L)->n_links)

/* Suppose we have a dependence Y between insn pro1 and con1, where pro1 has

   additional dependents con0 and con2, and con1 is dependent on additional

   insns pro0 and pro1:

   .con0      pro0

   . ^         |

   . |         |

   . |         |

   . X         A

   . |         |

   . |         |

   . |         V

   .pro1--Y-->con1

   . |         ^

   . |         |

   . |         |

   . Z         B

   . |         |

   . |         |

   . V         |

   .con2      pro2

   This is represented using a "dep_node" for each dependence arc, which are

   connected as follows (diagram is centered around Y which is fully shown;

   other dep_nodes shown partially):

   .          +------------+    +--------------+    +------------+

   .          : dep_node X :    |  dep_node Y  |    : dep_node Z :

   .          :            :    |              |    :            :

   .          :            :    |              |    :            :

   .          : forw       :    |  forw        |    : forw       :

   .          : +--------+ :    |  +--------+  |    : +--------+ :

   forw_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :

   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL

   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   . ^  ^     : |     ^  | :    |  |     ^  |  |    : |        | :

   . |  |     : |     |  | :    |  |     |  |  |    : |        | :

   . |  +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :

   . |        : |  |     | :    |  |  |     |  |    : |  |     | :

   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   . |        : | |prev| | :    |  | |prev| |  |    : | |prev| | :

   . |        : | |next| | :    |  | |next| |  |    : | |next| | :

   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   . |        : |        | :<-+ |  |        |  |<-+ : |        | :<-+

   . |        : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |

   . |        : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+

   . |        : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   . |        : |        | :    |  |        |  |    : |        | :

   . |        : +--------+ :    |  +--------+  |    : +--------+ :

   . |        :            :    |              |    :            :

   . |        :  SAME pro1 :    |  +--------+  |    :  SAME pro1 :

   . |        :  DIFF con0 :    |  |dep     |  |    :  DIFF con2 :

   . |        :            :    |  |        |  |    :            :

   . |                          |  | +----+ |  |

   .RTX<------------------------+--+-|pro1| |  |

   .pro1                        |  | +----+ |  |

   .                            |  |        |  |

   .                            |  | +----+ |  |

   .RTX<------------------------+--+-|con1| |  |

   .con1                        |  | +----+ |  |

   . |                          |  |        |  |

   . |                          |  | +----+ |  |

   . |                          |  | |kind| |  |

   . |                          |  | +----+ |  |

   . |        :            :    |  | |stat| |  |    :            :

   . |        :  DIFF pro0 :    |  | +----+ |  |    :  DIFF pro2 :

   . |        :  SAME con1 :    |  |        |  |    :  SAME con1 :

   . |        :            :    |  +--------+  |    :            :

   . |        :            :    |              |    :            :

   . |        : back       :    |  back        |    : back       :

   . v        : +--------+ :    |  +--------+  |    : +--------+ :

   back_deps  : |dep_link| :    |  |dep_link|  |    : |dep_link| :

   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   |first|----->| |next|-+------+->| |next|-+--+----->| |next|-+--->NULL

   +-----+    : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   .    ^     : |     ^  | :    |  |     ^  |  |    : |        | :

   .    |     : |     |  | :    |  |     |  |  |    : |        | :

   .    +--<----+--+  +--+---<--+--+--+  +--+--+--<---+--+     | :

   .          : |  |     | :    |  |  |     |  |    : |  |     | :

   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   .          : | |prev| | :    |  | |prev| |  |    : | |prev| | :

   .          : | |next| | :    |  | |next| |  |    : | |next| | :

   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   .          : |        | :<-+ |  |        |  |<-+ : |        | :<-+

   .          : | +----+ | :  | |  | +----+ |  |  | : | +----+ | :  |

   .          : | |node|-+----+ |  | |node|-+--+--+ : | |node|-+----+

   .          : | +----+ | :    |  | +----+ |  |    : | +----+ | :

   .          : |        | :    |  |        |  |    : |        | :

   .          : +--------+ :    |  +--------+  |    : +--------+ :

   .          :            :    |              |    :            :

   .          : dep_node A :    |  dep_node Y  |    : dep_node B :

   .          +------------+    +--------------+    +------------+

*/

struct _dep_node

{

  /* Backward link.  */

  struct _dep_link back;

  /* The dep.  */

  struct _dep dep;

  /* Forward link.  */

  struct _dep_link forw;

};

#define DEP_NODE_BACK(N) (&(N)->back)

#define DEP_NODE_DEP(N) (&(N)->dep)

#define DEP_NODE_FORW(N) (&(N)->forw)

/* The following enumeration values tell us what dependencies we

   should use to implement the barrier.  We use true-dependencies for

   TRUE_BARRIER and anti-dependencies for MOVE_BARRIER.  */

enum reg_pending_barrier_mode

{

  NOT_A_BARRIER = 0,

  MOVE_BARRIER,

  TRUE_BARRIER

};

/* Whether a register movement is associated with a call.  */

enum post_call_group

{

  not_post_call,

  post_call,

  post_call_initial

};

/* Insns which affect pseudo-registers.  */

struct deps_reg

{

  rtx uses;

  rtx sets;

  rtx implicit_sets;

  rtx control_uses;

  rtx clobbers;

  int uses_length;

  int clobbers_length;

};

/* Describe state of dependencies used during sched_analyze phase.  */

struct deps_desc

{

  /* The *_insns and *_mems are paired lists.  Each pending memory operation

     will have a pointer to the MEM rtx on one list and a pointer to the

     containing insn on the other list in the same place in the list.  */

  /* We can't use add_dependence like the old code did, because a single insn

     may have multiple memory accesses, and hence needs to be on the list

     once for each memory access.  Add_dependence won't let you add an insn

     to a list more than once.  */

  /* An INSN_LIST containing all insns with pending read operations.  */

  rtx pending_read_insns;

  /* An EXPR_LIST containing all MEM rtx's which are pending reads.  */

  rtx pending_read_mems;

  /* An INSN_LIST containing all insns with pending write operations.  */

  rtx pending_write_insns;

  /* An EXPR_LIST containing all MEM rtx's which are pending writes.  */

  rtx pending_write_mems;

  /* An INSN_LIST containing all jump insns.  */

  rtx pending_jump_insns;

  /* We must prevent the above lists from ever growing too large since

     the number of dependencies produced is at least O(N*N),

     and execution time is at least O(4*N*N), as a function of the

     length of these pending lists.  */

  /* Indicates the length of the pending_read list.  */

  int pending_read_list_length;

  /* Indicates the length of the pending_write list.  */

  int pending_write_list_length;

  /* Length of the pending memory flush list plus the length of the pending

     jump insn list.  Large functions with no calls may build up extremely

     large lists.  */

  int pending_flush_length;

  /* The last insn upon which all memory references must depend.

     This is an insn which flushed the pending lists, creating a dependency

     between it and all previously pending memory references.  This creates

     a barrier (or a checkpoint) which no memory reference is allowed to cross.

     This includes all non constant CALL_INSNs.  When we do interprocedural

     alias analysis, this restriction can be relaxed.

     This may also be an INSN that writes memory if the pending lists grow

     too large.  */

  rtx last_pending_memory_flush;

  /* A list of the last function calls we have seen.  We use a list to

     represent last function calls from multiple predecessor blocks.

     Used to prevent register lifetimes from expanding unnecessarily.  */

  rtx last_function_call;

  /* A list of the last function calls that may not return normally

     we have seen.  We use a list to represent last function calls from

     multiple predecessor blocks.  Used to prevent moving trapping insns

     across such calls.  */

  rtx last_function_call_may_noreturn;

  /* A list of insns which use a pseudo register that does not already

     cross a call.  We create dependencies between each of those insn

     and the next call insn, to ensure that they won't cross a call after

     scheduling is done.  */

  rtx sched_before_next_call;

  /* Similarly, a list of insns which should not cross a branch.  */

  rtx sched_before_next_jump;

  /* Used to keep post-call pseudo/hard reg movements together with

     the call.  */

  enum post_call_group in_post_call_group_p;

  /* The last debug insn we've seen.  */

  rtx last_debug_insn;

  /* The maximum register number for the following arrays.  Before reload

     this is max_reg_num; after reload it is FIRST_PSEUDO_REGISTER.  */

  int max_reg;

  /* Element N is the next insn that sets (hard or pseudo) register

     N within the current basic block; or zero, if there is no

     such insn.  Needed for new registers which may be introduced

     by splitting insns.  */

  struct deps_reg *reg_last;

  /* Element N is set for each register that has any nonzero element

     in reg_last[N].{uses,sets,clobbers}.  */

  regset_head reg_last_in_use;

  /* Shows the last value of reg_pending_barrier associated with the insn.  */

  enum reg_pending_barrier_mode last_reg_pending_barrier;

  /* True when this context should be treated as a readonly by

     the analysis.  */

  BOOL_BITFIELD readonly : 1;

};

typedef struct deps_desc *deps_t;

/* This structure holds some state of the current scheduling pass, and

   contains some function pointers that abstract out some of the non-generic

   functionality from functions such as schedule_block or schedule_insn.

   There is one global variable, current_sched_info, which points to the

   sched_info structure currently in use.  */

struct haifa_sched_info

{

  /* Add all insns that are initially ready to the ready list.  Called once

     before scheduling a set of insns.  */

  void (*init_ready_list) (void);

  /* Called after taking an insn from the ready list.  Returns nonzero if

     this insn can be scheduled, nonzero if we should silently discard it.  */

  int (*can_schedule_ready_p) (rtx);

  /* Return nonzero if there are more insns that should be scheduled.  */

  int (*schedule_more_p) (void);

  /* Called after an insn has all its hard dependencies resolved.

     Adjusts status of instruction (which is passed through second parameter)

     to indicate if instruction should be moved to the ready list or the

     queue, or if it should silently discard it (until next resolved

     dependence).  */

  ds_t (*new_ready) (rtx, ds_t);

  /* Compare priority of two insns.  Return a positive number if the second

     insn is to be preferred for scheduling, and a negative one if the first

     is to be preferred.  Zero if they are equally good.  */

  int (*rank) (rtx, rtx);

  /* Return a string that contains the insn uid and optionally anything else

     necessary to identify this insn in an output.  It's valid to use a

     static buffer for this.  The ALIGNED parameter should cause the string

     to be formatted so that multiple output lines will line up nicely.  */

  const char *(*print_insn) (const_rtx, int);

  /* Return nonzero if an insn should be included in priority

     calculations.  */

  int (*contributes_to_priority) (rtx, rtx);

  /* Return true if scheduling insn (passed as the parameter) will trigger

     finish of scheduling current block.  */

  bool (*insn_finishes_block_p) (rtx);

  /* The boundaries of the set of insns to be scheduled.  */

  rtx prev_head, next_tail;

  /* Filled in after the schedule is finished; the first and last scheduled

     insns.  */

  rtx head, tail;

  /* If nonzero, enables an additional sanity check in schedule_block.  */

  unsigned int queue_must_finish_empty:1;

  /* Maximum priority that has been assigned to an insn.  */

  int sched_max_insns_priority;

  /* Hooks to support speculative scheduling.  */

  /* Called to notify frontend that instruction is being added (second

     parameter == 0) or removed (second parameter == 1).  */

  void (*add_remove_insn) (rtx, int);

  /* Called to notify the frontend that instruction INSN is being

     scheduled.  */

  void (*begin_schedule_ready) (rtx insn);

  /* Called to notify the frontend that an instruction INSN is about to be

     moved to its correct place in the final schedule.  This is done for all

     insns in order of the schedule.  LAST indicates the last scheduled

     instruction.  */

  void (*begin_move_insn) (rtx insn, rtx last);

  /* If the second parameter is not NULL, return nonnull value, if the

     basic block should be advanced.

     If the second parameter is NULL, return the next basic block in EBB.

     The first parameter is the current basic block in EBB.  */

  basic_block (*advance_target_bb) (basic_block, rtx);

  /* Allocate memory, store the frontend scheduler state in it, and

     return it.  */

  void *(*save_state) (void);

  /* Restore frontend scheduler state from the argument, and free the

     memory.  */

  void (*restore_state) (void *);

  /* ??? FIXME: should use straight bitfields inside sched_info instead of

     this flag field.  */

  unsigned int flags;

};

/* This structure holds description of the properties for speculative

   scheduling.  */

struct spec_info_def

{

  /* Holds types of allowed speculations: BEGIN_{DATA|CONTROL},

     BE_IN_{DATA_CONTROL}.  */

  int mask;

  /* A dump file for additional information on speculative scheduling.  */

  FILE *dump;

  /* Minimal cumulative weakness of speculative instruction's

     dependencies, so that insn will be scheduled.  */

  dw_t data_weakness_cutoff;

  /* Minimal usefulness of speculative instruction to be considered for

     scheduling.  */

  int control_weakness_cutoff;

  /* Flags from the enum SPEC_SCHED_FLAGS.  */

  int flags;

};

typedef struct spec_info_def *spec_info_t;

extern spec_info_t spec_info;

extern struct haifa_sched_info *current_sched_info;

/* Do register pressure sensitive insn scheduling if the flag is set

   up.  */

extern bool sched_pressure_p;

/* Map regno -> its pressure class.  The map defined only when

   SCHED_PRESSURE_P is true.  */

extern enum reg_class *sched_regno_pressure_class;

/* Indexed by INSN_UID, the collection of all data associated with

   a single instruction.  */

struct _haifa_deps_insn_data

{

  /* The number of incoming edges in the forward dependency graph.

     As scheduling proceeds, counts are decreased.  An insn moves to

     the ready queue when its counter reaches zero.  */

  int dep_count;

  /* Nonzero if instruction has internal dependence

     (e.g. add_dependence was invoked with (insn == elem)).  */

  unsigned int has_internal_dep;

  /* NB: We can't place 'struct _deps_list' here instead of deps_list_t into

     h_i_d because when h_i_d extends, addresses of the deps_list->first

     change without updating deps_list->first->next->prev_nextp.  Thus

     BACK_DEPS and RESOLVED_BACK_DEPS are allocated on the heap and FORW_DEPS

     list is allocated on the obstack.  */

  /* A list of hard backward dependencies.  The insn is a consumer of all the

     deps mentioned here.  */

  deps_list_t hard_back_deps;

  /* A list of speculative (weak) dependencies.  The insn is a consumer of all

     the deps mentioned here.  */

  deps_list_t spec_back_deps;

  /* A list of insns which depend on the instruction.  Unlike 'back_deps',

     it represents forward dependencies.  */

  deps_list_t forw_deps;

  /* A list of scheduled producers of the instruction.  Links are being moved

     from 'back_deps' to 'resolved_back_deps' while scheduling.  */

  deps_list_t resolved_back_deps;

  /* A list of scheduled consumers of the instruction.  Links are being moved

     from 'forw_deps' to 'resolved_forw_deps' while scheduling to fasten the

     search in 'forw_deps'.  */

  deps_list_t resolved_forw_deps;

  /* If the insn is conditional (either through COND_EXEC, or because

     it is a conditional branch), this records the condition.  NULL

     for insns that haven't been seen yet or don't have a condition;

     const_true_rtx to mark an insn without a condition, or with a

     condition that has been clobbered by a subsequent insn.  */

  rtx cond;

  /* For a conditional insn, a list of insns that could set the condition

     register.  Used when generating control dependencies.  */

  rtx cond_deps;

  /* True if the condition in 'cond' should be reversed to get the actual

     condition.  */

  unsigned int reverse_cond : 1;

  /* Some insns (e.g. call) are not allowed to move across blocks.  */

  unsigned int cant_move : 1;

};

/* Bits used for storing values of the fields in the following

   structure.  */

#define INCREASE_BITS 8

/* The structure describes how the corresponding insn increases the

   register pressure for each pressure class.  */

struct reg_pressure_data

{

  /* Pressure increase for given class because of clobber.  */

  unsigned int clobber_increase : INCREASE_BITS;

  /* Increase in register pressure for given class because of register

     sets. */

  unsigned int set_increase : INCREASE_BITS;

  /* Pressure increase for given class because of unused register

     set.  */

  unsigned int unused_set_increase : INCREASE_BITS;

  /* Pressure change: #sets - #deaths.  */

  int change : INCREASE_BITS;

};

/* The following structure describes usage of registers by insns.  */

struct reg_use_data

{

  /* Regno used in the insn.  */

  int regno;

  /* Insn using the regno.  */

  rtx insn;

  /* Cyclic list of elements with the same regno.  */

  struct reg_use_data *next_regno_use;

  /* List of elements with the same insn.  */

  struct reg_use_data *next_insn_use;

};

/* The following structure describes used sets of registers by insns.

   Registers are pseudos whose pressure class is not NO_REGS or hard

   registers available for allocations.  */

struct reg_set_data

{

  /* Regno used in the insn.  */

  int regno;

  /* Insn setting the regno.  */

  rtx insn;

  /* List of elements with the same insn.  */

  struct reg_set_data *next_insn_set;

};

struct _haifa_insn_data

{

  /* We can't place 'struct _deps_list' into h_i_d instead of deps_list_t

     because when h_i_d extends, addresses of the deps_list->first

     change without updating deps_list->first->next->prev_nextp.  */

  /* Logical uid gives the original ordering of the insns.  */

  int luid;

  /* A priority for each insn.  */

  int priority;

  /* The minimum clock tick at which the insn becomes ready.  This is

     used to note timing constraints for the insns in the pending list.  */

  int tick;

  /* For insns that are scheduled at a fixed difference from another,

     this records the tick in which they must be ready.  */

  int exact_tick;

  /* INTER_TICK is used to adjust INSN_TICKs of instructions from the

     subsequent blocks in a region.  */

  int inter_tick;

  /* Used temporarily to estimate an INSN_TICK value for an insn given

     current knowledge.  */

  int tick_estimate;

  /* See comment on QUEUE_INDEX macro in haifa-sched.c.  */

  int queue_index;

  short cost;

  /* Set if there's DEF-USE dependence between some speculatively

     moved load insn and this one.  */

  unsigned int fed_by_spec_load : 1;

  unsigned int is_load_insn : 1;

  /* Nonzero if this insn has negative-cost forward dependencies against

     an already scheduled insn.  */

  unsigned int feeds_backtrack_insn : 1;

  /* Nonzero if this insn is a shadow of another, scheduled after a fixed