GCC Middle and Back End API Reference
haifa-sched.c File Reference

Data Structures

struct  delay_pair
struct  delay_i1_hasher
struct  delay_i2_hasher
struct  model_pressure_data
struct  model_insn_info
struct  model_pressure_limit
struct  model_pressure_group
struct  sched_block_state
struct  haifa_saved_data
struct  choice_entry




static int may_trap_exp (const_rtx, int)
static int haifa_luid_for_non_insn (rtx x)
static int insn_delay ()
static int may_trap_exp ()
static int haifa_classify_rtx ()
int haifa_classify_insn ()
void set_modulo_params ()
int haifa_htab_i2_traverse ()
int haifa_htab_i1_traverse ()
void discard_delay_pairs_above ()
void record_delay_slot_pair ()
rtx real_insn_for_shadow ()
static int pair_delay ()
void add_delay_dependencies ()
static int priority (rtx)
static int rank_for_schedule (const void *, const void *)
static void swap_sort (rtx *, int)
static void queue_insn (rtx, int, const char *)
static int schedule_insn (rtx)
static void adjust_priority (rtx)
static void advance_one_cycle (void)
static void extend_h_i_d (void)
static void ready_add (struct ready_list *, rtx, bool)
static rtx ready_remove_first (struct ready_list *)
static rtx ready_remove_first_dispatch (struct ready_list *ready)
static void queue_to_ready (struct ready_list *)
static int early_queue_to_ready (state_t, struct ready_list *)
static void debug_ready_list (struct ready_list *)
static rtx ready_remove (struct ready_list *, int)
static void ready_remove_insn (rtx)
static void fix_inter_tick (rtx, rtx)
static int fix_tick_ready (rtx)
static void change_queue_index (rtx, int)
static void init_h_i_d (rtx)
static int haifa_speculate_insn (rtx, ds_t, rtx *)
static void generate_recovery_code (rtx)
static void process_insn_forw_deps_be_in_spec (rtx, rtx, ds_t)
static void begin_speculative_block (rtx)
static void add_to_speculative_block (rtx)
static void init_before_recovery (basic_block *)
static void create_check_block_twin (rtx, bool)
static void fix_recovery_deps (basic_block)
static bool haifa_change_pattern (rtx, rtx)
static void dump_new_block_header (int, basic_block, rtx, rtx)
static void restore_bb_notes (basic_block)
static void fix_jump_move (rtx)
static void move_block_after_check (rtx)
static void move_succs (vec< edge, va_gc > **, basic_block)
static void sched_remove_insn (rtx)
static void clear_priorities (rtx, rtx_vec_t *)
static void calc_priorities (rtx_vec_t)
static void add_jump_dependencies (rtx, rtx)
void schedule_insns ()
void sched_init_region_reg_pressure_info ()
static void mark_regno_birth_or_death ()
static void initiate_reg_pressure_info ()
static void setup_ref_regs ()
static void initiate_bb_reg_pressure_info ()
static void save_reg_pressure ()
static void restore_reg_pressure ()
static bool dying_use_p ()
static void print_curr_reg_pressure ()
static bool cond_clobbered_p ()
static void update_insn_after_change ()
static void apply_replacement (dep_t, bool)
static void restore_pattern (dep_t, bool)
static ds_t recompute_todo_spec ()
int insn_cost ()
int dep_cost_1 ()
int dep_cost ()
void increase_insn_priority ()
static bool contributes_to_priority_p ()
static int dep_list_size ()
static int priority ()
static void calculate_reg_deaths (rtx insn, int *death))
static void setup_insn_reg_pressure_info ()
static int model_index ()
static void model_update_limit_points_in_group ()
static void model_update_limit_points ()
static int model_last_use_except ()
static void model_start_update_pressure (struct model_pressure_group *group, int point, int pci, int delta)
static int model_update_pressure (struct model_pressure_group *group, int point, int pci, int delta)
static void model_recompute ()
static bool must_restore_pattern_p ()
static int model_spill_cost ()
static int model_excess_group_cost (struct model_pressure_group *group, int point, int pci, int delta)
static int model_excess_cost ()
static void model_dump_pressure_points ()
static void model_set_excess_costs ()
static int rank_for_schedule ()
static HAIFA_INLINE void swap_sort ()
static HAIFA_INLINE void queue_insn ()
static void queue_remove ()
rtxready_lastpos ()
static HAIFA_INLINE void ready_add ()
static HAIFA_INLINE rtx ready_remove_first ()
rtx ready_element ()
static HAIFA_INLINE rtx ready_remove ()
static void ready_remove_insn ()
void ready_sort ()
static HAIFA_INLINE void adjust_priority ()
void advance_state ()
static void update_register_pressure ()
static void setup_insn_max_reg_pressure ()
static void update_reg_and_insn_max_reg_pressure ()
void sched_setup_bb_reg_pressure_info ()
static void check_clobbered_conditions ()
static int model_classify_pressure ()
static int model_order_p ()
static void model_add_to_worklist_at (struct model_insn_info *insn, struct model_insn_info *prev)
static void model_remove_from_worklist ()
static void model_add_to_worklist (struct model_insn_info *insn, struct model_insn_info *prev, struct model_insn_info *next)
static void model_promote_insn ()
static void model_add_to_schedule ()
static void model_analyze_insns ()
static void model_init_pressure_group ()
static void model_record_pressure (struct model_pressure_group *group, int point, int pci, int pressure)
static void model_record_pressures ()
static void model_record_final_pressures ()
static void model_add_successors_to_worklist ()
static void model_promote_predecessors ()
static void model_choose_insn ()
static void model_reset_queue_indices ()
static void model_dump_pressure_summary ()
static void model_start_schedule ()
static void model_finalize_pressure_group ()
static void model_end_schedule ()
static int schedule_insn ()
void concat_note_lists ()
void remove_notes ()
static void mark_backtrack_feeds ()
static void save_backtrack_point (struct delay_pair *pair, struct sched_block_state sched_block)
static void toggle_cancelled_flags ()
static void undo_replacements_for_backtrack ()
static void unschedule_insns_until ()
static void restore_last_backtrack_point ()
static void free_topmost_backtrack_point ()
static void free_backtrack_queue ()
static void apply_replacement ()
static void restore_pattern ()
static void perform_replacements_new_cycle ()
static bool estimate_insn_tick ()
static int estimate_shadow_tick ()
static void resolve_dependencies ()
void get_ebb_head_tail ()
int no_real_insns_p ()
rtx restore_other_notes ()
static void undo_all_replacements ()
static void queue_to_ready ()
static bool ok_for_early_queue_removal ()
static int early_queue_to_ready ()
static void debug_ready_list ()
void reemit_notes ()
static void move_insn ()
static bool insn_finishes_cycle_p ()
int max_issue (struct ready_list *ready, int privileged_n, state_t state, bool first_cycle_insn_p, int *index)
static int choose_ready (struct ready_list *ready, bool first_cycle_insn_p, rtx *insn_ptr)
static void commit_schedule ()
static void prune_ready_list (state_t temp_state, bool first_cycle_insn_p, bool shadows_only_p, bool modulo_epilogue_p)
static struct haifa_saved_dataverify_shadows ()
bool schedule_block ()
int set_priorities ()
void setup_sched_dump ()
void sched_init ()
static void haifa_init_only_bb (basic_block, basic_block)
void haifa_sched_init ()
void haifa_sched_finish ()
void sched_finish ()
void free_delay_pairs ()
static void fix_inter_tick ()
int try_ready ()
static int fix_tick_ready ()
static void change_queue_index ()
void sched_extend_ready_list ()
void sched_finish_ready_list ()
static int haifa_luid_for_non_insn ()
static void generate_recovery_code ()
static void process_insn_forw_deps_be_in_spec ()
static void begin_speculative_block ()
static void haifa_init_insn (rtx)
static void add_to_speculative_block ()
void * xrecalloc ()
edge find_fallthru_edge_from ()
static void sched_extend_bb ()
void sched_init_bbs ()
static void init_before_recovery ()
basic_block sched_create_recovery_block ()
void sched_create_recovery_edges (basic_block first_bb, basic_block rec, basic_block second_bb)
static void create_check_block_twin ()
static void fix_recovery_deps ()
static bool haifa_change_pattern ()
int sched_speculate_insn ()
static int haifa_speculate_insn ()
static void dump_new_block_header ()
void unlink_bb_notes ()
static void restore_bb_notes ()
static void fix_jump_move ()
static void move_block_after_check ()
static void move_succs ()
static void sched_remove_insn ()
static void clear_priorities ()
static void calc_priorities ()
static void add_jump_dependencies ()
void sched_extend_luids ()
void sched_init_insn_luid ()
void sched_init_luids ()
void sched_finish_luids ()
int insn_luid ()
void sched_extend_target ()
static void init_h_i_d ()
void haifa_init_h_i_d ()
void haifa_finish_h_i_d ()
static void haifa_init_insn ()
static void haifa_init_only_bb ()
basic_block sched_split_block_1 ()
basic_block sched_create_empty_bb_1 ()
rtx sched_emit_insn ()
static rtx ready_remove_first_dispatch ()
int number_in_ready ()
rtx get_ready_element ()


int issue_rate
bool sched_no_dce
static int modulo_ii
static int modulo_max_stages
static int modulo_n_insns
static int modulo_insns_scheduled
static int modulo_iter0_max_uid
static int modulo_backtracks_left
static int modulo_last_stage
int sched_verbose = 0
FILE * sched_dump = 0
struct common_sched_info_defcommon_sched_info
rtx note_list
static struct spec_info_def spec_info_var
spec_info_t spec_info = NULL
static bool haifa_recovery_bb_recently_added_p
bool haifa_recovery_bb_ever_added_p
static int nr_begin_data
static int nr_be_in_data
static int nr_begin_control
static int nr_be_in_control
static rtxbb_header = 0
static basic_block before_recovery
basic_block after_recovery
bool adding_bb_to_current_region_p = true
static rtxinsn_queue
static int q_ptr = 0
static int q_size = 0
state_t curr_state
size_t dfa_state_size
char * ready_try = NULL
struct ready_list ready = {NULL, 0, 0, 0, 0}
static struct ready_listreadyp = &ready
static int clock_var
static int last_clock_var
static bool must_backtrack
int cycle_issued_insns
static vec< rtxscheduled_insns
struct common_sched_info_def haifa_common_sched_info
vec< int > sched_luids = vNULL
int sched_max_luid = 1
vec< haifa_insn_data_defh_i_d = vNULL
void(* sched_init_only_bb )(basic_block, basic_block)
basic_block(* sched_split_block )(basic_block, rtx)
basic_block(* sched_create_empty_bb )(basic_block)
static hash_table
< delay_i1_hasher
static hash_table
< delay_i2_hasher
struct haifa_sched_infocurrent_sched_info
enum sched_pressure_algorithm sched_pressure
enum reg_class * sched_regno_pressure_class
static int curr_reg_pressure [N_REG_CLASSES]
static int saved_reg_pressure [N_REG_CLASSES]
static bitmap curr_reg_live
static bitmap saved_reg_live
static bitmap region_ref_regs
static vec< dep_tnext_cycle_replace_deps
static vec< int > next_cycle_apply
static rtx last_scheduled_insn
static rtx last_nondebug_scheduled_insn
static rtx nonscheduled_insns_begin
static vec< rtxmodel_schedule
static struct model_insn_infomodel_worklist
static struct model_insn_infomodel_insns
static int model_num_insns
static int model_curr_point
static struct model_pressure_group model_before_pressure
static unsigned int model_next_priority
static struct haifa_saved_databacktrack_queue
static struct choice_entrychoice_stack
int dfa_lookahead
static int max_lookahead_tries
static int cached_first_cycle_multipass_dfa_lookahead = 0
static int cached_issue_rate = 0
static int sched_ready_n_insns = -1

Typedef Documentation

typedef TARGET_SCHED_FIRST_CYCLE_MULTIPASS_DATA_T first_cycle_multipass_data_t

Function Documentation

void add_delay_dependencies ( )
   Given an insn INSN, add a dependence on its delayed shadow if it
   has one.  Also try to find situations where shadows depend on each other
   and add dependencies to the real insns to limit the amount of backtracking
static void add_jump_dependencies ( rtx  ,
static void add_jump_dependencies ( )
   Add dependences between JUMP and other instructions in the recovery
   block.  INSN is the first insn the recovery block.  
static void add_to_speculative_block ( rtx  )

Referenced by haifa_sched_finish().

static void add_to_speculative_block ( )
   Generates recovery code for BE_IN speculative INSN.  
     First we convert all simple checks to branchy.  
             Restart search.  
           Continue search.  
         Get the first backward dependency of INSN.  
           INSN has no backward dependencies left.  
           INSN_BB (insn) isn't determined for twin insns yet.
           So we can't use current_sched_info->print_insn.  
         Add dependences between TWIN and all appropriate
         instructions from REC.  
             INSN might have dependencies from the instructions from
             several recovery blocks.  At this iteration we process those
             producers that reside in REC.  
         Remove all dependencies between INSN and insns in REC.  
     We couldn't have added the dependencies between INSN and TWINS earlier
     because that would make TWINS appear in the INSN_BACK_DEPS (INSN).  
static void adjust_priority ( rtx  )
static HAIFA_INLINE void adjust_priority ( )
   PREV is an insn that is ready to execute.  Adjust its priority if that
   will help shorten or lengthen register lifetimes as appropriate.  Also
   provide a hook for the target to tweak itself.  
     ??? There used to be code here to try and estimate how an insn
     affected register lifetimes, but it did it by looking at REG_DEAD
     notes, which we removed in schedule_region.  Nor did it try to
     take into account register pressure or anything useful like that.

     Revisit when we have a machine model to work with and not before.  
static HAIFA_INLINE void advance_one_cycle ( )
   Advance time on one cycle.  
void advance_state ( )
   Advance DFA state STATE on one cycle.  
static void apply_replacement ( dep_t  ,
static void apply_replacement ( )
   Apply a replacement described by DESC.  If IMMEDIATELY is false, we
   may have to postpone the replacement until the start of the next cycle,
   at which point we will be called again with IMMEDIATELY true.  This is
   only done for machines which have instruction packets with explicit
   parallelism however.  
static void begin_speculative_block ( rtx  )

Referenced by haifa_sched_finish().

static void begin_speculative_block ( )
   Generates recovery code for BEGIN speculative INSN.  
static void calc_priorities ( rtx_vec_t  )
static void calc_priorities ( )
   Recompute priorities of instructions, whose priorities might have been
   changed.  ROOTS is a vector of instructions whose priority computation will
   trigger initialization of all cleared priorities.  
static void calculate_reg_deaths ( rtx  insn,
int *  death 
   For each pressure class CL, set DEATH[CL] to the number of registers
   in that class that die in INSN.  

Referenced by priority(), and ready_remove_insn().

static void change_queue_index ( rtx  ,
static void change_queue_index ( )
   Move NEXT to the proper queue list with (DELAY >= 1),
   or add it to the ready list (DELAY == QUEUE_READY),
   or remove it from ready and queue lists at all (DELAY == QUEUE_NOWHERE).  
       We have nothing to do.  
     Remove NEXT from wherever it is now.  
     Add it to the proper place.  
static void check_clobbered_conditions ( )
   If doing predication while scheduling, verify whether INSN, which
   has just been scheduled, clobbers the conditions of any
   instructions that must be predicated in order to break their
   dependencies.  If so, remove them from the queues so that they will
   only be scheduled once their control dependency is resolved.  

References model_insn_info::alap, dep_list_size(), model_insn_info::insn, model_add_to_worklist(), model_insn_info::old_queue, and model_insn_info::unscheduled_preds.

static int choose_ready ( struct ready_list ready,
bool  first_cycle_insn_p,
rtx insn_ptr 
   The following function chooses insn from READY and modifies
   READY.  The following function is used only for first
   cycle multipass scheduling.
   -1 if cycle should be advanced,
   0 if INSN_PTR is set to point to the desirable insn,
   1 if choose_ready () should be restarted without advancing the cycle.  
           INSN is in the ready_list.  
         INSN is in the queue.  Advance cycle to move it to the ready list.  
         Try to choose the better insn.  
           Discard speculative instruction that stands first in the ready
         Let the target filter the search space.  
               If this insn is recognizable we should have already
               recognized it earlier.
               ??? Not very clear where this is supposed to be done.
               See dep_cost_1.  

References targetm.

static void clear_priorities ( rtx  ,
static void clear_priorities ( )
   Clear priorities of all instructions, that are forward dependent on INSN.
   Store in vector pointed to by ROOTS_PTR insns on which priority () should
   be invoked to initialize all cleared priorities.  
             If DEP doesn't contribute to priority then INSN itself should
             be added to priority roots.  
static void commit_schedule ( )
   This function is called when we have successfully scheduled a
   block.  It uses the schedule stored in the scheduled_insns vector
   to rearrange the RTL.  PREV_HEAD is used as the anchor to which we
   append the scheduled insns; TAIL is the insn after the scheduled
   block.  TARGET_BB is the argument passed to schedule_block.  

References sched_verbose.

void concat_note_lists ( )
   Functions for handling of notes.  
   Add note list that ends on FROM_END to the end of TO_ENDP.  
     It's easy when have nothing to concat.  
     It's also easy when destination is empty.  
static bool cond_clobbered_p ( )
   Determine if INSN has a condition that is clobbered if a register
   in SET_REGS is modified.  

Referenced by ready_element().

static bool contributes_to_priority_p ( )
   Return 'true' if DEP should be included in priority calculations.  
     Critical path is meaningful in block boundaries only.  
     If flag COUNT_SPEC_IN_CRITICAL_PATH is set,
     then speculative instructions will less likely be
     scheduled.  That is because the priority of
     their producers will increase, and, thus, the
     producers will more likely be scheduled, thus,
     resolving the dependence.  

Referenced by increase_insn_priority().

static void create_check_block_twin ( rtx  ,

Referenced by free_delay_pairs().

static void create_check_block_twin ( )
   This function creates recovery code for INSN.  If MUTATE_P is nonzero,
   INSN is a simple check, that should be converted to branchy one.  
     Create recovery block.  
     Emit CHECK.  
         To have mem_reg alive at the beginning of second_bb,
         we emit check BEFORE insn, so insn after splitting
         insn will be at the beginning of second_bb, which will
         provide us with the correct life information.  
     Extend data structures.  
     CHECK is being added to current region.  Extend ready list.  
     Initialize TWIN (twin is a duplicate of original instruction
     in the recovery block).  
           INSN_BB (insn) isn't determined for twin insns yet.
           So we can't use current_sched_info->print_insn.  
         ??? We probably should change all OUTPUT dependencies to
         (TRUE | OUTPUT).  
     Copy all resolved back dependencies of INSN to TWIN.  This will
     provide correct value for INSN_TICK (TWIN).  
       In case of branchy check, fix CFG.  
     Move backward dependences from INSN to CHECK and
     move forward dependences from INSN to TWIN.  
     First, create dependencies between INSN's producers and CHECK & TWIN.  
         If BEGIN_DATA: [insn ~~TRUE~~> producer]:
         check --TRUE--> producer  ??? or ANTI ???
         twin  --TRUE--> producer
         twin  --ANTI--> check

         If BEGIN_CONTROL: [insn ~~ANTI~~> producer]:
         check --ANTI--> producer
         twin  --ANTI--> producer
         twin  --ANTI--> check

         If BE_IN_SPEC: [insn ~~TRUE~~> producer]:
         check ~~TRUE~~> producer
         twin  ~~TRUE~~> producer
         twin  --ANTI--> check  
     Second, remove backward dependencies of INSN.  
           We can delete this dep because we overcome it with
     Future Speculations.  Determine what BE_IN speculations will be like.  
     Fields (DONE_SPEC (x) & BEGIN_SPEC) and CHECK_SPEC (x) are set only
         Luckiness of future speculations solely depends upon initial
         BEGIN speculation.  
     Future speculations: call the helper.  
         Which types of dependencies should we use here is,
         generally, machine-dependent question...  But, for now,
         it is not.  
             Remove all dependencies of the INSN.  
             If former check (INSN) already was moved to the ready (or queue)
             list, add new check (CHECK) there too.  
             Remove old check from instruction stream and free its
       Fix priorities.  If MUTATE_P is nonzero, this is not necessary,
       because it'll be done later in add_to_speculative_block.  

References df_mark_solutions_dirty(), common_sched_info_def::fix_recovery_cfg, basic_block_def::index, link_block(), move_succs(), basic_block_def::next_bb, basic_block_def::succs, unlink_block(), and update_bb_for_insn().

static void debug_ready_list ( struct ready_list )
static void debug_ready_list ( )
   Print the ready list for debugging purposes.  Callable from debugger.  
int dep_cost ( )
   Compute cost of dependence LINK.
   This is the number of cycles between instruction issue and
   instruction results.  

Referenced by increase_insn_priority(), and resolve_dependencies().

int dep_cost_1 ( )
   Compute cost of dependence LINK.
   This is the number of cycles between instruction issue and
   instruction results.
   ??? We also use this function to call recog_memoized on all insns.  
     A USE insn should never require the value used to be computed.
     This allows the computation of a function's result and parameter
     values to overlap the return and call.  We don't care about the
     dependence cost when only decreasing register pressure.  
             This variable is used for backward compatibility with the
             Make it self-cycled, so that if some tries to walk over this
             incomplete list he/she will be caught in an endless loop.  
             Targets use only REG_NOTE_KIND of the link.  

References haifa_sched_info::contributes_to_priority, COUNT_SPEC_IN_CRITICAL_PATH, spec_info_def::flags, sched_deps_info_def::generate_spec_deps, sched_deps_info, and spec_info.

static int dep_list_size ( )
   Compute the number of nondebug deps in list LIST for INSN.  

References dying_use_p(), mark_regno_birth_or_death(), reg_use_data::next_insn_use, and reg_use_data::regno.

Referenced by check_clobbered_conditions().

void discard_delay_pairs_above ( )
static void dump_new_block_header ( int  ,
basic_block  ,
rtx  ,
static void dump_new_block_header ( )
   Print some information about block BB, which starts with HEAD and
   ends with TAIL, before scheduling it.
   I is zero, if scheduler is about to start with the fresh ebb.  
static bool dying_use_p ( )
   Return TRUE if the register is dying after its USE.  

References sd_lists_empty_p().

Referenced by dep_list_size().

static int early_queue_to_ready ( state_t  ,
struct ready_list  
static int early_queue_to_ready ( )
   Remove insns from the queue, before they become "ready" with respect
   to FU latency considerations.  
                   non-negative to indicate that it's not ready
                   to avoid infinite Q->R->Q->R... 
                         move from Q to R 
                           Remove no more than flag_sched_stalled_insns insns
                           from Q at a time.  

References choice_stack, dfa_lookahead, dfa_state_size, choice_entry::index, insn_finishes_cycle_p(), memcpy(), choice_entry::n, ready_element(), ready_try, choice_entry::rest, choice_entry::state, choice_entry::target_data, and targetm.

static bool estimate_insn_tick ( )
   Compute INSN_TICK_ESTIMATE for INSN.  PROCESSED is a bitmap of
   instructions we've previously encountered, a set bit prevents
   recursion.  BUDGET is a limit on how far ahead we look, it is
   reduced on recursive calls.  Return true if we produced a good
   estimate, or false if we exceeded the budget.  

References ready_add(), and sched_verbose.

Referenced by restore_last_backtrack_point().

static int estimate_shadow_tick ( )
   Examine the pair of insns in P, and estimate (optimistically, assuming
   infinite resources) the cycle in which the delayed shadow can be issued.
   Return the number of cycles that must pass before the real insn can be
   issued in order to meet this constraint.  

Referenced by max_issue().

static void extend_h_i_d ( void  )
   The following functions are used to implement scheduling of data/control
   speculative instructions.  
   Extend global scheduler structures (those, that live across calls to
   schedule_block) to include information about just emitted INSN.  
edge find_fallthru_edge_from ( )
   Helper function.
   Find fallthru edge from PRED.  
static void fix_inter_tick ( rtx  ,
static void fix_inter_tick ( )
   Fix INSN_TICKs of the instructions in the current block as well as
   INSN_TICKs of their dependents.
   HEAD and TAIL are the begin and the end of the current scheduled block.  
     Set of instructions with corrected INSN_TICK.  
     ??? It is doubtful if we should assume that cycle advance happens on
     basic block boundaries.  Basically insns that are unconditionally ready
     on the start of the block are more preferable then those which have
     a one cycle dependency over insn from the previous block.  
     Iterates over scheduled instructions and fix their INSN_TICKs and
     INSN_TICKs of dependent instructions, so that INSN_TICKs are consistent
     across different blocks.  
             Fix INSN_TICK of instruction from just scheduled block.  
                     If NEXT has its INSN_TICK calculated, fix it.
                     If not - it will be properly calculated from
                     scratch later in fix_tick_ready.  
static void fix_jump_move ( rtx  )
static void fix_jump_move ( )
   Helper function.
   Fix CFG after both in- and inter-block movement of
   control_flow_insn_p JUMP.  
       if jump_bb_next is not empty.  
       Then there are instruction after jump that should be placed
       to jump_bb_next.  
       Otherwise jump_bb_next is empty.  
     To make assertion in move_insn happy.  
static void fix_recovery_deps ( basic_block  )
static void fix_recovery_deps ( )
   Removes dependency between instructions in the recovery block REC
   and usual region instructions.  It keeps inner dependences so it
   won't be necessary to recompute them.  
     NOTE - a basic block note.  
     Try to add instructions to the ready or queue list.  
     Fixing jump's dependences.  
static int fix_tick_ready ( rtx  )
static int fix_tick_ready ( )
   Calculate INSN_TICK of NEXT and add it to either ready or queue list.  
         if tick is not equal to INVALID_TICK, then update
         INSN_TICK of NEXT with the most recent resolved dependence
         cost.  Otherwise, recalculate from scratch.  
static void free_backtrack_queue ( )
   Free the entire backtrack queue.  
void free_delay_pairs ( void  )
   Free all delay_pair structures that were recorded.  

References create_check_block_twin(), nr_begin_control, and nr_begin_data.

static void free_topmost_backtrack_point ( )
   Discard all data associated with the topmost entry in the backtrack
   queue.  If RESET_TICK is false, we just want to free the data.  If true,
   we are doing this because we discovered a reason to backtrack.  In the
   latter case, also reset the INSN_TICK for the shadow insn.  
static void generate_recovery_code ( rtx  )
static void generate_recovery_code ( )
   Generates recovery code for INSN.  
     Here we have insn with no dependencies to
     instructions other then CHECK_SPEC ones.  
void get_ebb_head_tail ( )
   Return the head and tail pointers of ebb starting at BEG and ending
   at END.  
     Don't include any notes or labels at the beginning of the BEG
     basic block, or notes at the end of the END basic blocks.  

References dfa_state_size, free_INSN_LIST_node(), memcpy(), ok_for_early_queue_removal(), haifa_sched_info::print_insn, print_rtl_single(), q_ptr, q_size, ready_add(), recog_memoized(), and sched_verbose.

Referenced by add_inter_loop_mem_dep(), and generate_prolog_epilog().

rtx get_ready_element ( )
   Get number of ready's in the ready list.  
static bool haifa_change_pattern ( rtx  ,
static bool haifa_change_pattern ( )
   Change pattern of INSN to NEW_PAT.  Invalidate cached haifa
   instruction data.  

References reg_use_data::insn, ready_remove(), and targetm.

int haifa_classify_insn ( )

Referenced by update_live().

static int haifa_classify_rtx ( )
   Classifies rtx X of an insn for the purpose of verifying that X can be
   executed speculatively (and consequently the insn can be moved
   speculatively), by examining X, returning:
   TRAP_RISKY: store, or risky non-load insn (e.g. division by variable).
   TRAP_FREE: non-load insn.
   IFREE: load from a globally safe location.
   IRISKY: volatile load.
   PFREE_CANDIDATE, PRISKY_CANDIDATE: load that need to be checked for
   being either PFREE or PRISKY.  
             Test if it is a 'store'.  
             Test if it is a store.  
             Test if it is a load.  
void haifa_finish_h_i_d ( void  )
   Finalize haifa_insn_data.  
int haifa_htab_i1_traverse ( )
   Called through htab_traverse.  Walk the hashtable using I2 as
   index, and delete all elements involving an UID higher than
   that pointed to by *DATA.  

Referenced by delay_i2_hasher::hash().

int haifa_htab_i2_traverse ( )
   Called through htab_traverse.  Walk the hashtable using I2 as
   index, and delete all elements involving an UID higher than
   that pointed to by *DATA.  

References hash_table< Descriptor, Allocator >::create(), delay_pair::cycles, hash_table< Descriptor, Allocator >::find_slot_with_hash(), i1, delay_pair::i1, i2, delay_pair::i2, hash_table< Descriptor, Allocator >::is_created(), delay_pair::next_same_i1, and delay_pair::stages.

Referenced by delay_i2_hasher::hash().

void haifa_init_h_i_d ( )
   Initialize haifa_insn_data for BBS.  

Referenced by code_motion_process_successors().

static void haifa_init_insn ( rtx  )
static void haifa_init_insn ( )
   Init data for the new insn INSN.  
         Extend dependency caches by one element.  
static void haifa_init_only_bb ( basic_block  ,
static void haifa_init_only_bb ( )
   Init data for the new basic block BB which comes after AFTER.  
       This changes only data structures of the front-end.  
static int haifa_luid_for_non_insn ( rtx  x)
   Returns a class that insn with GET_DEST(insn)=x may belong to,
   as found by analyzing insn's expression.  
static int haifa_luid_for_non_insn ( )
void haifa_sched_finish ( void  )
   Finish work with the data specific to the Haifa scheduler.  
     Finalize h_i_d, dependency caches, and luids for the whole
     function.  Target will be finalized in md_global_finish ().  

References add_to_speculative_block(), and begin_speculative_block().

void haifa_sched_init ( void  )
   Initialize data structures specific to the Haifa scheduler.  
     Initialize luids, dependency caches, target and h_i_d for the
     whole function.  

References dfa_state_size, choice_entry::state, and targetm.

Referenced by loop_canon_p().

static int haifa_speculate_insn ( rtx  ,
ds_t  ,
static int haifa_speculate_insn ( )

References ready_list::n_ready.

void increase_insn_priority ( )
   Use this sel-sched.c friendly function in reorder2 instead of increasing
   INSN_PRIORITY explicitly.  
         We're dealing with haifa-sched.c INSN_PRIORITY.  
         In sel-sched.c INSN_PRIORITY is not kept up to date.
         Use EXPR_PRIORITY instead. 

References contributes_to_priority_p(), and dep_cost().

static void init_before_recovery ( basic_block )
static void init_before_recovery ( )
   Initialize BEFORE_RECOVERY variable.  
         We create two basic blocks:
         1. Single instruction block is inserted right after E->SRC
         and has jump to
         2. Empty block right before EXIT_BLOCK.
         Between these two blocks recovery blocks will be emitted.  
         If the fallthrough edge to exit we've found is from the block we've
         created before, don't do anything more.  
         Add new blocks to the root loop.  

References targetm.

static void init_h_i_d ( rtx  )
static void init_h_i_d ( )
   Initialize h_i_d entry of the INSN with default values.
   Values, that are not explicitly initialized here, hold zero.  
static void initiate_bb_reg_pressure_info ( )
   Initiate current register pressure related info at the start of
   basic block BB.  
static void initiate_reg_pressure_info ( )
   Initiate current register pressure related info from living
   registers given by LIVE.  

Referenced by mark_regno_birth_or_death().

int insn_cost ( )
   Compute cost of executing INSN.
   This is the number of cycles between instruction issue and
   instruction results.  
         A USE insn, or something else we don't need to
         understand.  We can't pass these directly to
         result_ready_cost or insn_default_latency because it will
         trigger a fatal error for unrecognizable insns.  

References targetm.

static int insn_delay ( )
   Return the number of cycles until INSN is expected to be ready.
   Return zero if it already is.  
static bool insn_finishes_cycle_p ( )
   Return true if scheduling INSN will finish current clock cycle.  
       After issuing INSN, rest of the sched_group will be forced to issue
       in order.  Don't make any plans for the rest of cycle.  
     Finishing the block will, apparently, finish the cycle.  

References ready_element(), ready_try, recog_memoized(), and targetm.

Referenced by early_queue_to_ready().

int insn_luid ( )
   Return logical uid of INSN.  Helpful while debugging.  
static void mark_backtrack_feeds ( )
   For every dependency of INSN, set the FEEDS_BACKTRACK_INSN bit according
   to SET_P.  
static void mark_regno_birth_or_death ( )
   PRESSURE[CL] describes the pressure on register class CL.  Update it
   for the birth (if BIRTH_P) or death (if !BIRTH_P) of register REGNO.
   LIVE tracks the set of live registers; if it is null, assume that
   every birth or death is genuine.  

References bb_has_eh_pred(), bitmap_bit_p(), current_nr_blocks, df_get_live_in(), initiate_reg_pressure_info(), and setup_ref_regs().

Referenced by dep_list_size(), and model_last_use_except().

int max_issue ( struct ready_list ready,
int  privileged_n,
state_t  state,
bool  first_cycle_insn_p,
int *  index 
   The following function returns maximal (or close to maximal) number
   of insns which can be issued on the same cycle and one of which
   insns is insns with the best rank (the first insn in READY).  To
   make this function tries different samples of ready insns.  READY
   is current queue `ready'.  Global array READY_TRY reflects what
   insns are already issued in this try.  The function stops immediately,
   if it reached the such a solution, that all instruction can be issued.
   INDEX will contain index of the best insn in READY.  The following
   function is used only for first cycle multipass scheduling.


   This function expects recognized insns only.  All USEs,
   CLOBBERs, etc must be filtered elsewhere.  
     Init max_points.  
     The number of the issued insns in the best solution.  
     Set initial state of the search.  
     Count the number of the insns to search among.  
     I is the index of the insn to try next.  
             or have nothing else to try...  
             or should not issue more.  
             ??? (... || i == n_ready).  
             We should not issue more than issue_rate instructions.  
                     Try to find issued privileged insn.  
                     Or a privileged insn will be issued.  
                   Then we have a solution.  
                     This is the index of the insn issued first in this
             Set ready-list index to point to the last insn
             ('i++' below will advance it to the next insn).  
                   We won't issue any more instructions in the next
                 Advance to the next choice_entry.  
                 Initialize it.  
         Increase ready-list index.  
     Restore the original state of the DFA.  

References asm_noperands(), clock_var, dfa_state_size, estimate_shadow_tick(), hash_table< Descriptor, Allocator >::find_with_hash(), hash_table< Descriptor, Allocator >::is_created(), memcpy(), choice_entry::n, ready_list::n_ready, delay_pair::next_same_i1, queue_insn(), ready_element(), ready_remove(), recog_memoized(), SCHED_PRESSURE_MODEL, and SCHED_PRESSURE_NONE.

static int may_trap_exp ( const_rtx  ,

Referenced by may_trap_exp().

static int may_trap_exp ( )
         The insn uses memory:  a volatile load.  
         An exception-free load.  
         A load with 1 base register, to be further checked.  
         No info on the load, to be further checked.  
         Neither store nor load, check if it may cause a trap.  
         Recursive step: walk the insn...  

References IRISKY, may_trap_exp(), and TRAP_RISKY.

static void model_add_successors_to_worklist ( )
   Update all successors of INSN, given that INSN has just been scheduled.  
         Ignore debug instructions, and instructions from other blocks.  
             Update the depth field of each true-dependent successor.
             Increasing the depth gives them a higher priority than
             If this is a true dependency, or if there are no remaining
             dependencies for CON (meaning that CON only had non-true
             dependencies), make sure that CON is on the worklist.
             We don't bother otherwise because it would tend to fill the
             worklist with a lot of low-priority instructions that are not
             yet ready to issue.  
static void model_add_to_schedule ( )
   Add INSN to the end of the model schedule.  
static void model_add_to_worklist ( struct model_insn_info insn,
struct model_insn_info prev,
struct model_insn_info next 
   Add INSN to the model worklist.  Start looking for a suitable position
   between neighbors PREV and NEXT, testing at most MAX_SCHED_READY_INSNS
   insns either side.  A null PREV indicates the beginning of the list and
   a null NEXT indicates the end.  

Referenced by check_clobbered_conditions(), and model_promote_insn().

static void model_add_to_worklist_at ( struct model_insn_info insn,
struct model_insn_info prev 
   Add INSN to the model worklist immediately after PREV.  Add it to the
   beginning of the list if PREV is null.  

Referenced by setup_insn_max_reg_pressure().

static void model_analyze_insns ( )
   Analyze the instructions that are to be scheduled, setting up
   MODEL_INSN_INFO (...) and model_num_insns accordingly.  Add ready
   instructions to model_worklist.  

References model_insn_info::alap, model_insn_info::depth, model_insn_info::insn, model_insn_info::model_priority, model_worklist, and model_insn_info::next.

static void model_choose_insn ( )
   Pick one instruction from model_worklist and process it.  
     Look for a ready instruction whose model_classify_priority is zero
     or negative, picking the highest-priority one.  Adding such an
     instruction to the schedule now should do no harm, and may actually
     do some good.

     Failing that, see whether there is an instruction with the highest
     extant model_priority that is not yet ready, but which would reduce
     pressure if it became ready.  This is designed to catch cases like:

       (set (mem (reg R1)) (reg R2))

     where the instruction is the last remaining use of R1 and where the
     value of R2 is not yet available (or vice versa).  The death of R1
     means that this instruction already reduces pressure.  It is of
     course possible that the computation of R2 involves other registers
     that are hard to kill, but such cases are rare enough for this
     heuristic to be a win in general.

     Failing that, just pick the highest-priority instruction in the
       INSN isn't yet ready to issue.  Give all its predecessors the
       highest priority.  
         INSN is ready.  Add it to the end of model_schedule and
         process its successors.  
static int model_classify_pressure ( )
   Return (in order):

   - positive if INSN adversely affects the pressure on one
     register class

   - negative if INSN reduces the pressure on one register class

   - 0 if INSN doesn't affect the pressure on any register class.  

References model_pressure_group::limits, model_pressure_limit::point, and model_pressure_limit::pressure.

Referenced by model_init_pressure_group().

static void model_dump_pressure_points ( )
   Dump the next points of maximum pressure for GROUP.  
static void model_dump_pressure_summary ( )
   We have calculated the model schedule and spill costs.  Print a summary
   to sched_dump.  
static void model_end_schedule ( )
   Free the information created by model_start_schedule.  
static int model_excess_cost ( )
   Return baseECC (MODEL_INSN (INSN)).  Dump the costs to sched_dump
   if PRINT_P.  
     Sum up the individual costs for each register class.  
static int model_excess_group_cost ( struct model_pressure_group group,
int  point,
int  pci,
int  delta 
   Return baseECC (ira_pressure_classes[PCI], POINT), given that
   P = curr_reg_pressure[ira_pressure_classes[PCI]] and that
   P' = P + DELTA.  

Referenced by must_restore_pattern_p().

static void model_finalize_pressure_group ( )
   Free the information associated with GROUP.  

References dep_replacement::insn.

static int model_index ( )
   Return INSN's index in the model schedule, or model_num_insns if it
   doesn't belong to that schedule.  

References reg_use_data::regno.

Referenced by model_promote_predecessors().

static void model_init_pressure_group ( )
   The global state describes the register pressure at the start of the
   model schedule.  Initialize GROUP accordingly.  
     Use index model_num_insns to record the state after the last
     instruction in the model schedule.  

References model_insn_info::insn, model_classify_pressure(), model_insn_info::model_priority, model_worklist, and model_insn_info::unscheduled_preds.

static int model_last_use_except ( )
   Return the model_index of the last unscheduled use in chain USE
   outside of USE's instruction.  Return -1 if there are no other uses,
   or model_num_insns if the register is live at the end of the block.  

References mark_regno_birth_or_death(), and sched_verbose.

static int model_order_p ( )
   Return true if INSN1 should come before INSN2 in the model schedule.  
     Prefer instructions with a higher model priority.  
     Combine the length of the longest path of satisfied true dependencies
     that leads to each instruction (depth) with the length of the longest
     path of any dependencies that leads from the instruction (alap).
     Prefer instructions with the greatest combined length.  If the combined
     lengths are equal, prefer instructions with the greatest depth.

     The idea is that, if we have a set S of "equal" instructions that each
     have ALAP value X, and we pick one such instruction I, any true-dependent
     successors of I that have ALAP value X - 1 should be preferred over S.
     This encourages the schedule to be "narrow" rather than "wide".
     However, if I is a low-priority instruction that we decided to
     schedule because of its model_classify_pressure, and if there
     is a set of higher-priority instructions T, the aforementioned
     successors of I should not have the edge over T.  
     We have no real preference between INSN1 an INSN2 as far as attempts
     to reduce pressure go.  Prefer instructions with higher priorities.  
     Use the original rtl sequence as a tie-breaker.  

Referenced by setup_insn_max_reg_pressure().

static void model_promote_insn ( )
   INSN may now have a higher priority (in the model_order_p sense)
   than before.  Move it up the worklist if necessary.  

References first, model_insn_info::insn, model_add_to_worklist(), model_next_priority, model_insn_info::model_priority, model_remove_from_worklist(), model_insn_info::next, and sched_verbose.

Referenced by model_remove_from_worklist().

static void model_promote_predecessors ( )
   Give INSN a higher priority than any current instruction, then give
   unscheduled predecessors of INSN a higher priority still.  If any of
   those predecessors are not on the model worklist, do the same for its
   predecessors, and so on.  
             The first test is to ignore debug instructions, and instructions
             from other blocks.  
                     PRO is already in the worklist, but it now has
                     a higher priority than before.  Move it at the
                     appropriate place.  
                     PRO isn't in the worklist.  Recursively process
                     its predecessors until we find one that is.  

References reg_pressure_data::change, clock_var, model_index(), haifa_sched_info::print_insn, recog_memoized(), reg_class_names, SCHED_PRESSURE_MODEL, reg_pressure_data::set_increase, and str_pattern_slim().

static void model_recompute ( )
   INSN has just been scheduled.  Update the model schedule accordingly.  
     The destinations of INSN were previously live from POINT onwards, but are
     now live from model_curr_point onwards.  Set up DELTA accordingly.  
     Record which registers previously died at POINT, but which now die
     before POINT.  Adjust DELTA so that it represents the effect of
     this change after POINT - 1.  Set NUM_PENDING_BIRTHS to the number of
     registers that will be born in the range [model_curr_point, POINT).  
             This register is no longer live after POINT - 1.  
     Also set each group pressure limit for POINT.  
     Walk the model schedule backwards, starting immediately before POINT.  
               DELTA describes the effect of the move on the register pressure
               after POINT.  Make it describe the effect on the pressure
               before POINT.  
                       This register is now live again.  
                       Remove this use from the array.  
           Adjust the pressure at POINT.  Set MIX to nonzero if POINT - 1
           might have changed as well.  
static void model_record_final_pressures ( )
   All instructions have been added to the model schedule.  Record the
   final register pressure in GROUP and set up all MODEL_MAX_PRESSUREs.  
         Record the final pressure for this class.  
         Record the original maximum pressure.  
         Update the MODEL_MAX_PRESSURE for every point of the schedule.  
static void model_record_pressure ( struct model_pressure_group group,
int  point,
int  pci,
int  pressure 
   Update the maximum pressure for the whole schedule.  
static void model_record_pressures ( )
   INSN has just been added to the end of the model schedule.  Record its
   register-pressure information.  
static void model_remove_from_worklist ( )
   Remove INSN from the model worklist.  

References model_insn_info::depth, model_insn_info::insn, and model_promote_insn().

Referenced by model_promote_insn().

static void model_reset_queue_indices ( )
   Restore all QUEUE_INDEXs to the values that they had before
   model_start_schedule was called.  

References try_ready().

static void model_set_excess_costs ( )
     Record the baseECC value for each instruction in the model schedule,
     except that negative costs are converted to zero ones now rather thatn
     later.  Do not assign a cost to debug instructions, since they must
     not change code-generation decisions.  Experiments suggest we also
     get better results by not assigning a cost to instructions from
     a different block.

     Set PRIORITY_BASE to baseP in the block comment above.  This is the
     maximum priority of the "cheap" instructions, which should always
     include the next model instruction.  
     Use MAX (baseECC, 0) and baseP to calculcate ECC for each
static int model_spill_cost ( )
   model_spill_cost (CL, P, P') returns the cost of increasing the
   pressure on CL from P to P'.  We use this to calculate a "base ECC",
   baseECC (CL, X), for each pressure class CL and each instruction X.
   Supposing X changes the pressure on CL from P to P', and that the
   maximum pressure on CL in the current model schedule is MP', then:

   * if X occurs before or at the next point of maximum pressure in
     the model schedule and P' > MP', then:

       baseECC (CL, X) = model_spill_cost (CL, MP, P')

     The idea is that the pressure after scheduling a fixed set of
     instructions -- in this case, the set up to and including the
     next maximum pressure point -- is going to be the same regardless
     of the order; we simply want to keep the intermediate pressure
     under control.  Thus X has a cost of zero unless scheduling it
     now would exceed MP'.

     If all increases in the set are by the same amount, no zero-cost
     instruction will ever cause the pressure to exceed MP'.  However,
     if X is instead moved past an instruction X' with pressure in the
     range (MP' - (P' - P), MP'), the pressure at X' will increase
     beyond MP'.  Since baseECC is very much a heuristic anyway,
     it doesn't seem worth the overhead of tracking cases like these.

     The cost of exceeding MP' is always based on the original maximum
     pressure MP.  This is so that going 2 registers over the original
     limit has the same cost regardless of whether it comes from two
     separate +1 deltas or from a single +2 delta.

   * if X occurs after the next point of maximum pressure in the model
     schedule and P' > P, then:

       baseECC (CL, X) = model_spill_cost (CL, MP, MP' + (P' - P))

     That is, if we move X forward across a point of maximum pressure,
     and if X increases the pressure by P' - P, then we conservatively
     assume that scheduling X next would increase the maximum pressure
     by P' - P.  Again, the cost of doing this is based on the original
     maximum pressure MP, for the same reason as above.

   * if P' < P, P > MP, and X occurs at or after the next point of
     maximum pressure, then:

       baseECC (CL, X) = -model_spill_cost (CL, MAX (MP, P'), P)

     That is, if we have already exceeded the original maximum pressure MP,
     and if X might reduce the maximum pressure again -- or at least push
     it further back, and thus allow more scheduling freedom -- it is given
     a negative cost to reflect the improvement.

   * otherwise,

       baseECC (CL, X) = 0

     In this case, X is not expected to affect the maximum pressure MP',
     so it has zero cost.

   We then create a combined value baseECC (X) that is the sum of
   baseECC (CL, X) for each pressure class CL.

   baseECC (X) could itself be used as the ECC value described above.
   However, this is often too conservative, in the sense that it
   tends to make high-priority instructions that increase pressure
   wait too long in cases where introducing a spill would be better.
   For this reason the final ECC is a priority-adjusted form of
   baseECC (X).  Specifically, we calculate:

     P (X) = INSN_PRIORITY (X) - insn_delay (X) - baseECC (X)
     baseP = MAX { P (X) | baseECC (X) <= 0 }


     ECC (X) = MAX (MIN (baseP - P (X), baseECC (X)), 0)

   Thus an instruction's effect on pressure is ignored if it has a high
   enough priority relative to the ones that don't increase pressure.
   Negative values of baseECC (X) do not increase the priority of X
   itself, but they do make it harder for other instructions to
   increase the pressure further.

   This pressure cost is deliberately timid.  The intention has been
   to choose a heuristic that rarely interferes with the normal list
   scheduler in cases where that scheduler would produce good code.
   We simply want to curb some of its worst excesses.  
   Return the cost of increasing the pressure in class CL from FROM to TO.

   Here we use the very simplistic cost model that every register above
   ira_class_hard_regs_num[CL] has a spill cost of 1.  We could use other
   measures instead, such as one based on MEMORY_MOVE_COST.  However:

      (1) In order for an instruction to be scheduled, the higher cost
          would need to be justified in a single saving of that many stalls.
          This is overly pessimistic, because the benefit of spilling is
          often to avoid a sequence of several short stalls rather than
          a single long one.

      (2) The cost is still arbitrary.  Because we are not allocating
          registers during scheduling, we have no way of knowing for
          sure how many memory accesses will be required by each spill,
          where the spills will be placed within the block, or even
          which block(s) will contain the spills.

   So a higher cost than 1 is often too conservative in practice,
   forcing blocks to contain unnecessary stalls instead of spill code.
   The simple cost below seems to be the best compromise.  It reduces
   the interference with the normal list scheduler, which helps make
   it more suitable for a default-on option.  
static void model_start_schedule ( )
   Initialize the SCHED_PRESSURE_MODEL information for the current
   scheduling region.  
static void model_start_update_pressure ( struct model_pressure_group group,
int  point,
int  pci,
int  delta 
   An instruction with model_index POINT has just been scheduled, and it
   adds DELTA to the pressure on ira_pressure_classes[PCI] after POINT - 1.
         The instruction wasn't part of the model schedule; it was moved
         from a different block.  Update the pressure for the end of
         the model schedule.  
         Record that this instruction has been scheduled.  Nothing now
         changes between POINT and POINT + 1, so get the maximum pressure
         from the latter.  If the maximum pressure decreases, the new
         pressure point may be before POINT.  
static void model_update_limit_points ( )
   Make sure that all register-pressure limits are up-to-date for the
   current position in the model schedule.  
static void model_update_limit_points_in_group ( )
   Make sure that GROUP->limits is up-to-date for the current point
   of the model schedule.  
         We may have passed the final point at which the pressure in
         group->limits[pci].pressure was reached.  Update the limit if so.  
         Find the point at which MAX_PRESSURE is first reached.  We need
         to search in three cases:

         - We've already moved past the previous pressure point.
           In this case we search forward from model_curr_point.

         - We scheduled the previous point of maximum pressure ahead of
           its position in the model schedule, but doing so didn't bring
           the pressure point earlier.  In this case we search forward
           from that previous pressure point.

         - Scheduling an instruction early caused the maximum pressure
           to decrease.  In this case we will have set the pressure
           point to -1, and we search forward from model_curr_point.  
static int model_update_pressure ( struct model_pressure_group group,
int  point,
int  pci,
int  delta 
   Record that scheduling a later instruction has changed the pressure
   at point POINT of the model schedule by DELTA (which might be 0).
   Update GROUP accordingly.  Return nonzero if these changes might
   trigger changes to previous points as well.  
     If POINT hasn't yet been scheduled, update its pressure.  
         Check whether the maximum pressure in the overall schedule
         has increased.  (This means that the MODEL_MAX_PRESSURE of
         every point <= POINT will need to increae too; see below.)  
         If we are at maximum pressure, and the maximum pressure
         point was previously unknown or later than POINT,
         bring it forward.  
         If POINT used to be the point of maximum pressure, but isn't
         any longer, we need to recalculate it using a forward walk.  
     Update the maximum pressure at POINT.  Changes here might also
     affect the maximum pressure at POINT - 1.  
static void move_block_after_check ( rtx  )
static void move_block_after_check ( )
   Fix CFG after interblock movement of control_flow_insn_p JUMP.  
static void move_insn ( )
   Move INSN.  Reemit notes if needed.  Update CFG, if needed.  
         BB_HEAD is either LABEL or NOTE.  
           If this is last instruction in BB, move end marker one
           instruction up.  
             Jumps are always placed at the end of basic block.  
           We move the block note along with jump.  
         Update BB_END, if needed.  

Referenced by ira_init_once().

static void move_succs ( vec< edge, va_gc > **  ,

Referenced by create_check_block_twin().

static void move_succs ( )
   Helper function for move_block_after_check.
   This functions attaches edge vector pointed to by SUCCSP to
   block TO.  
static bool must_restore_pattern_p ( )
   After DEP, which was cancelled, has been resolved for insn NEXT,
   check whether the insn's pattern needs restoring.  

References model_before_pressure, model_excess_group_cost(), reg_class_names, and reg_pressure_data::set_increase.

int no_real_insns_p ( )
   Return nonzero if there are no real insns in the range [ HEAD, TAIL ].  
int number_in_ready ( void  )
   Get number of ready insn in the ready list.  
static bool ok_for_early_queue_removal ( )
   Used by early_queue_to_ready.  Determines whether it is "ok" to
   prematurely move INSN from the queue to the ready list.  Currently,
   if a target defines the hook 'is_costly_dependence', this function
   uses the hook to check whether there exist any dependences which are
   considered costly by the target, between INSN and other insns that
   have already been scheduled.  Dependences are checked up to Y cycles
   back, with default Y=1; The flag -fsched-stalled-insns-dep=Y allows
   controlling this value.
   (Other considerations could be taken into account instead (or in
   addition) depending on user flags and target hooks.  

References choice_stack, cycle_issued_insns, dfa_lookahead, dfa_state_size, issue_rate, memcpy(), choice_entry::n, ready_list::n_ready, ready_try, choice_entry::rest, choice_entry::state, choice_entry::target_data, and targetm.

Referenced by get_ebb_head_tail().

static int pair_delay ( )
   For a pair P of insns, return the fixed distance in cycles from the first
   insn after which the second must be scheduled.  

Referenced by restore_last_backtrack_point().

static void perform_replacements_new_cycle ( )
   Perform pattern replacements that were queued up until the next
static void print_curr_reg_pressure ( )
   Print info about the current register pressure and its excess for
   each pressure class.  
static int priority ( rtx  )
static int priority ( )
   Compute the priority number for INSN.  
     We should not be interested in priority of an already scheduled insn.  
           ??? We should set INSN_PRIORITY to insn_cost when and insn has
           some forward deps but all of them are ignored by
           contributes_to_priority hook.  At the moment we set priority of
           such insn to 0.  
             For recovery check instructions we calculate priority slightly
             different than that of normal instructions.  Instead of walking
             through INSN_FORW_DEPS (check) list, we walk through
             INSN_FORW_DEPS list of each instruction in the corresponding
             recovery block.  
             Selective scheduling does not define RECOVERY_BLOCK macro.  

References calculate_reg_deaths(), and reg_pressure_data::set_increase.

static void process_insn_forw_deps_be_in_spec ( rtx  ,
rtx  ,
static void process_insn_forw_deps_be_in_spec ( )
   Helper function.
   Tries to add speculative dependencies of type FS between instructions
   in deps_list L and TWIN.  
             And we can do that because this is a true dep.  
               Then we have a choice: keep the dep 'begin speculative'
               or transform it into 'be in speculative'.  
                       Transform it to be in speculative.  
               Mark the dep as 'be in speculative'.  
static void prune_ready_list ( state_t  temp_state,
bool  first_cycle_insn_p,
bool  shadows_only_p,
bool  modulo_epilogue_p 
   Examine all insns on the ready list and queue those which can't be
   issued in this cycle.  TEMP_STATE is temporary scheduler state we
   can use as scratch space.  If FIRST_CYCLE_INSN_P is true, no insns
   have been issued for the current cycle, which means it is valid to
   issue an asm statement.

   If SHADOWS_ONLY_P is true, we eliminate all real insns and only
   leave those for which SHADOW_P is true.  If MODULO_EPILOGUE is true,
   we only leave insns which have an INSN_EXACT_TICK.  
     Make two passes if there's a SCHED_GROUP_P insn; make sure to handle
     such an insn first and note its cost, then schedule all other insns
     for one cycle later.  

References haifa_sched_info::begin_schedule_ready, ready_list::n_ready, ready_element(), ready_remove_first(), ready_sort(), and schedule_insn().

static void queue_insn ( rtx  ,
int  ,
const char *   

Referenced by max_issue().

static HAIFA_INLINE void queue_insn ( )
   Add INSN to the insn queue so that it can be executed at least
   N_CYCLES after the currently executing insn.  Preserve insns
   chain for debugging purposes.  REASON will be printed in debugging

References targetm.

static void queue_remove ( )
   Remove INSN from queue.  
static void queue_to_ready ( struct ready_list )
static void queue_to_ready ( )
   Move insns that became ready to fire from queue to ready list.  
         If debug counter is activated do not requeue the first
         nonscheduled insn.  
     Add all pending insns that can be scheduled without stalls to the
     ready list.  
         If the ready list is full, delay the insn for 1 cycle.
         See the comment in schedule_block for the rationale.  
                     Limit pressure recalculations to MAX_SCHED_READY_INSNS
                     instructions too.  
                  Always allow the next model instruction to issue.  
     If there are no ready insns, stall until one is ready and add all
     of the pending insns at that point to the ready list.  
static int rank_for_schedule ( const void *  ,
const void *   
static int rank_for_schedule ( )
   Returns a positive value if x is preferred; returns a negative value if
   y is preferred.  Should never return 0, since that will make the sort
         Schedule debug insns as early as possible.  
     The insn in a schedule group should be issued the first.  
     Make sure that priority of TMP and TMP2 are initialized.  
         Prefer insn whose scheduling results in the smallest register
         pressure excess.  
     If we are doing backtracking in this schedule, prefer insns that
     have forward dependencies with negative cost against an insn that
     was already scheduled.  
     Prefer insn with higher priority.  
     Prefer speculative insn with greater dependencies weakness.  
     Compare insns based on their relation to the last scheduled
     non-debug insn.  
         Classify the instructions into three classes:
         1) Data dependent on last schedule insn.
         2) Anti/Output dependent on last scheduled insn.
         3) Independent of last scheduled insn, or has latency of one.
         Choose the insn from the highest numbered class if different.  
     Prefer instructions that occur earlier in the model schedule.  
     Prefer the insn which has more later insns that depend on it.
     This gives the scheduler more freedom when scheduling later
     instructions at the expense of added register pressure.  
     If insns are equally good, sort by INSN_LUID (original insn order),
     so that we make the sort stable.  This minimizes instruction movement,
     thus minimizing sched's effect on debugging and cross-jumping.  

References clock_var, must_backtrack, and sched_verbose.

static void ready_add ( struct ready_list ,
rtx  ,
   Notes handling mechanism:
   Generally, NOTES are saved before scheduling and restored after scheduling.
   The scheduler distinguishes between two types of notes:

   Before scheduling a region, a pointer to the note is added to the insn
   that follows or precedes it.  (This happens as part of the data dependence
   computation).  After scheduling an insn, the pointer contained in it is
   used for regenerating the corresponding note (in reemit_notes).

   (2) All other notes (e.g. INSN_DELETED):  Before scheduling a block,
   these notes are put in a list (in rm_other_notes() and
   unlink_other_notes ()).  After scheduling the block, these notes are
   inserted at the beginning of the block (in schedule_block()).  

Referenced by estimate_insn_tick(), and get_ebb_head_tail().

static HAIFA_INLINE void ready_add ( )
   Add an element INSN to the ready list so that it ends up with the
   lowest/highest priority depending on FIRST_P.  
               ready_lastpos() fails when called with (ready->n_ready == 0).  
rtx ready_element ( )
   The following code implements multi-pass scheduling for the first
   cycle.  In other words, we will try to choose ready insn which
   permits to start maximum number of insns on the same cycle.  
   Return a pointer to the element INDEX from the ready.  INDEX for
   insn with the highest priority is 0, and the lowest priority has
   N_READY - 1.  

References cond_clobbered_p(), and ready_remove_insn().

Referenced by early_queue_to_ready(), insn_finishes_cycle_p(), max_issue(), and prune_ready_list().

rtx* ready_lastpos ( )
   Return a pointer to the bottom of the ready list, i.e. the insn
   with the lowest priority.  

References reg_set_data::insn, and save_reg_pressure().

static rtx ready_remove ( struct ready_list ,
   The following functions are used to implement multi-pass scheduling
   on the first cycle.  

Referenced by haifa_change_pattern(), and max_issue().

static HAIFA_INLINE rtx ready_remove ( )
   Remove the element INDEX from the ready list and return it.  INDEX
   for insn with the highest priority is 0, and the lowest priority
   has N_READY - 1.  
static rtx ready_remove_first ( struct ready_list )

Referenced by prune_ready_list().

static HAIFA_INLINE rtx ready_remove_first ( )
   Remove the element with the highest priority from the ready list and
   return it.  
     If the queue becomes empty, reset it.  
static rtx ready_remove_first_dispatch ( struct ready_list ready)
static rtx ready_remove_first_dispatch ( )
   This function returns a candidate satisfying dispatch constraints from
   the ready list.  
             Return ith element of ready.  
         Return i-th element of ready.  
static void ready_remove_insn ( rtx  )

Referenced by ready_element(), and reemit_notes().

static void ready_remove_insn ( )
   Remove INSN from the ready list.  

References calculate_reg_deaths(), model_insn_info::insn, and reg_pressure_data::set_increase.

void ready_sort ( )
   Sort the ready list READY by ascending priority, using the SCHED_SORT

Referenced by prune_ready_list().

rtx real_insn_for_shadow ( )
   Examine the delay pair hashtable to see if INSN is a shadow for another,
   and return the other insn if so.  Return NULL otherwise.  

Referenced by sd_copy_back_deps().

static ds_t recompute_todo_spec ( )
   Look at the remaining dependencies for insn NEXT, and compute and return
   the TODO_SPEC value we should use for it.  This is called after one of
   NEXT's dependencies has been resolved.
   We also perform pattern replacements for predication, and for broken
   replacement dependencies.  The latter is only done if FOR_BACKTRACK is
       NEXT has all its dependencies resolved.  
     Now we've got NEXT with speculative deps only.
     1. Look at the deps to see what we have to do.
     2. Check if we can do 'todo'.  
         Find the last scheduled insn that modifies the condition register.
         We can stop looking once we find the insn we depend on through the
         REG_DEP_CONTROL; if the condition register isn't modified after it,
         we know that it still has the right value.  
     We can't handle the case where there are both speculative and control
     dependencies, so we return HARD_DEP in such a case.  Also fail if
     we have speculative dependencies with not enough points, or more than
     one control dependency.  
             Too few points?  
void record_delay_slot_pair ( )
   This function can be called by a port just before it starts the final
   scheduling pass.  It records the fact that an instruction with delay
   slots has been split into two insns, I1 and I2.  The first one will be
   scheduled normally and initiates the operation.  The second one is a
   shadow which must follow a specific number of cycles after I1; its only
   purpose is to show the side effect that occurs at that cycle in the RTL.
   If a JUMP_INSN or a CALL_INSN has been split, I1 should be a normal INSN,
   while I2 retains the original insn type.

   There are two ways in which the number of cycles can be specified,
   involving the CYCLES and STAGES arguments to this function.  If STAGES
   is zero, we just use the value of CYCLES.  Otherwise, STAGES is a factor
   which is multiplied by MODULO_II to give the number of cycles.  This is
   only useful if the caller also calls set_modulo_params to enable modulo
void reemit_notes ( )
   Search INSN for REG_SAVE_NOTE notes and convert them back into insn
   NOTEs.  This is used for NOTE_INSN_EPILOGUE_BEG, so that sched-ebb
   replaces the epilogue note in the correct basic block.  

References next_nonnote_insn(), nonscheduled_insns_begin, and ready_remove_insn().

void remove_notes ( )
   Delete notes between HEAD and TAIL and put them in the chain
   of notes ended by NOTE_LIST.  
             Add the note to list that ends at NOTE_LIST.  
static void resolve_dependencies ( )
   If INSN has no unresolved backwards dependencies, add it to the schedule and
   recursively resolve all its forward dependencies.  
     Don't use sd_lists_empty_p; it ignores debug insns.  
     Update dependent instructions.  
         Resolve the dependence between INSN and NEXT.
         sd_resolve_dep () moves current dep to another list thus
         advancing the iterator.  
           Check always has only one forward dependence (to the first insn in
           the recovery block), therefore, this will be executed only once.  

References dep_cost(), sd_find_dep_between(), and targetm.

static void restore_bb_notes ( basic_block  )
static void restore_bb_notes ( )
   Restore basic block notes.
   FIRST is the first basic block in the ebb.  
     We DON'T unlink basic block notes of the first block in the ebb.  
     Remember: FIRST is actually a second basic block in the ebb.  
static void restore_last_backtrack_point ( )
   Restore scheduler state from the topmost entry on the backtracking queue.
   PSCHED_BLOCK_P points to the local data of schedule_block that we must
   overwrite with the saved data.
   The caller must already have called unschedule_insns_until.  
     Do this first since it clobbers INSN_TICK of the involved
     Clear the QUEUE_INDEX of everything in the ready list or one
     of the queues.  

References bitmap_clear(), clock_var, estimate_insn_tick(), delay_pair::i2, pair_delay(), and processed.

rtx restore_other_notes ( )
   Restore-other-notes: NOTE_LIST is the end of a chain of notes
   previously found among the insns.  Insert them just before HEAD.  
         In the above cycle we've missed this note.  
static void restore_pattern ( dep_t  ,
static void restore_pattern ( )
   We have determined that a pattern involved in DEP must be restored.
   If IMMEDIATELY is false, we may have to postpone the replacement
   until the start of the next cycle, at which point we will be called
   again with IMMEDIATELY true.  
     If we already scheduled the insn, the modified version is
static void restore_reg_pressure ( )
   Restore saved register pressure related info.  
static void save_backtrack_point ( struct delay_pair pair,
struct sched_block_state  sched_block 
   Save the current scheduler state so that we can backtrack to it
   later if necessary.  PAIR gives the insns that make it necessary to
   save this point.  SCHED_BLOCK is the local state of schedule_block
   that need to be saved.  

References haifa_saved_data::delay_pair, delay_pair::i2, delay_pair::next_same_i1, and undo_replacements_for_backtrack().

static void save_reg_pressure ( )
   Save current register pressure related info.  

References sd_iterator_next().

Referenced by ready_lastpos().

basic_block sched_create_empty_bb_1 ( )
   A generic version of sched_create_empty_bb ().  
basic_block sched_create_recovery_block ( )
   Returns new recovery block.  
     A recovery block always ends with an unconditional jump.  

Referenced by haifa_luid_for_non_insn().

void sched_create_recovery_edges ( basic_block  first_bb,
basic_block  rec,
basic_block  second_bb 
   and emit necessary jumps.  
     This is fixing of incoming edge.  
     ??? Which other flags should be specified?  
       Partition type is the same, if it is "unpartitioned".  
       Partition type is the same, if it is "unpartitioned".  
         Rewritten from cfgrtl.c.  
             We don't need the same note for the check because
             any_condjump_p (check) == true.  
rtx sched_emit_insn ( )
   Insert PAT as an INSN into the schedule and update the necessary data
   structures to account for it. 
static void sched_extend_bb ( )
   Extend per basic block data structures.  
     The following is done to keep current_sched_info->next_tail non null.  
             Don't emit a NOTE if it would end up before a BARRIER.  
         Make note appear outside BB.  
void sched_extend_luids ( void  )
   Extend data structures for logical insn UID.  
void sched_extend_ready_list ( )
   Initialize per region data structures.  
       At the first call we need to initialize one more choice_stack
     We allocate +1 element to save initial state in the choice_stack[0]

References add_reg_note(), block_label(), CDI_DOMINATORS, dom_info_available_p(), emit_jump_insn_after(), make_edge(), make_single_succ_edge(), and set_immediate_dominator().

Referenced by av_set_could_be_blocked_by_bookkeeping_p().

void sched_extend_target ( void  )
   Extend per insn data in the target.  
void sched_finish ( void  )
   Free global data used during insn scheduling.  This function works with
   the common data shared between the schedulers.  

References sched_insn_is_legitimate_for_speculation_p().

void sched_finish_luids ( void  )
   Free LUIDs.  
void sched_finish_ready_list ( void  )
   Free per region data structures.  
void sched_init ( void  )
   Initialize some global state for the scheduler.  This function works
   with the common data shared between all the schedulers.  It is called
   from the scheduler specific initialization routine.  
     Disable speculative loads in their presence if cc0 defined.  
     Initialize SPEC_INFO.  
           So we won't read anything accidentally.  
       So we won't read anything accidentally.  
     Initialize issue_rate.  
         To invalidate max_lookahead_tries:  
     More problems needed for interloop dep calculation in SMS.  
     Do not run DCE after reload, as this can kill nops inserted
     by bundling.  
           We need info about pseudos for rtl dumps about pseudo
           classes and costs.  
void sched_init_bbs ( void  )
   Init per basic block data structures.  

References DO_SPECULATION, and haifa_sched_info::flags.

void sched_init_insn_luid ( )
   Initialize LUID for INSN.  
void sched_init_luids ( )
   Initialize luids for BBS.
   The hook common_sched_info->luid_for_non_insn () is used to determine
   if notes, labels, etc. need luids.  

Referenced by code_motion_process_successors().

void sched_init_region_reg_pressure_info ( void  )
   Initiate register pressure relative info for scheduling the current
   region.  Currently it is only clearing register mentioned in the
   current region.  
static void sched_remove_insn ( rtx  )
static void sched_remove_insn ( )
   Remove INSN from the instruction stream.
   INSN should have any dependencies.  
void sched_setup_bb_reg_pressure_info ( )
   Set up register pressure at the beginning of basic block BB whose
   insns starting after insn AFTER.  Set up also max register pressure
   for all insns of the basic block.  

References model_insn_info::insn, haifa_sched_info::next_tail, and haifa_sched_info::prev_head.

int sched_speculate_insn ( )
   -1 - can't speculate,
   0 - for speculation with REQUEST mode it is OK to use
   current instruction pattern,
   1 - need to change pattern for *NEW_PAT to be speculative.  

References targetm.

basic_block sched_split_block_1 ( )
   A generic version of sched_split_block ().  
     sched_split_block emits note if *check == BB_END.  Probably it
     is better to rip that note off.  
bool schedule_block ( )
   Use forward list scheduling to rearrange insns of block pointed to by
   TARGET_BB, possibly bringing insns from subsequent blocks in the same
     Head/tail info for this block.  
     We used to have code to avoid getting parameters moved from hard
     argument registers into pseudos.

     However, it was removed when it proved to be of marginal benefit
     and caused problems because schedule_block and compute_forward_dependences
     had different notions of what the "head" insn was.  
     Debug info.  
     Clear the ready list.  
     It is used for first cycle multipass scheduling.  
     We start inserting insns after PREV_HEAD.  
     Initialize INSN_QUEUE.  Q_SIZE is the total number of insns in the
     Start just before the beginning of time.  
     We need queue and ready lists and clock_var be initialized
     in try_ready () (which is called through init_ready_list ()).  
     The algorithm is O(n^2) in the number of ready insns at any given
     time in the worst case.  Before reload we are more likely to have
     big lists so truncate them to a reasonable size.  
         Find first free-standing insn past MAX_SCHED_READY_INSNS.
         If there are debug insns, we know they're first.  
         Delay all insns past it for 1 cycle.  If debug counter is
         activated make an exception for the insn right after
     Now we can restore basic block notes and maintain precise cfg.  
     Loop until all the insns in BB are scheduled.  
             Add to the ready list all pending insns that can be issued now.
             If there are no ready insns, increment clock until one
             is ready and add all pending insns at that point to the ready
                 Sort the ready list based on priority.  This must be
                 done every iteration through the loop, as schedule_insn
                 may have readied additional insns that will not be
                 sorted correctly.  
             We don't want md sched reorder to even see debug isns, so put
             them out right away.  
             Allow the target to reorder the list, typically for
             better instruction bundling.  
                 Allow scheduling insns directly from the queue in case
                 there's nothing better to do (ready list is empty) but
                 there are still vacant dispatch slots in the current cycle.  
             Select and remove the insn from the ready list.  
                   Finish cycle.  
               SORT_P is used by the target to override sorting
               of the ready list.  This is needed when the target
               has modified its internal structures expecting that
               the insn will be issued next.  As we need the insn
               to have the highest priority (so it will be returned by
               the ready_remove_first call above), we invoke
               ready_add (&ready, insn, true).
               But, still, there is one issue: INSN can be later
               discarded by scheduler's front end through
               current_sched_info->can_schedule_ready_p, hence, won't
               be issued next.  
               We normally get here only if we don't want to move
               insn from the split block.  
                 If this insn is the first part of a delay-slot pair, record a
                 backtrack point.  
             DECISION is made.  
             Update counters, etc in the scheduler's front end.  
             A naked CLOBBER or USE generates no instruction, so do
             not count them against the issue rate.  
             After issuing an asm insn we should start a new cycle.  
             Clear these queues.  
             Delay by at least a cycle.  This could cause additional
         Once again, debug insn suckiness: they can be on the ready list
         even if they have unresolved dependencies.  To make our view
         of the world consistent, remove such "ready" insns.  
     Debug info.  
       Sanity check -- queue must be empty now.  Meaningless if region has
       multiple bbs.  
         We must maintain QUEUE_INDEX between blocks in region.  
         INSN_TICK (minimum clock tick at which the insn becomes
         ready) may be not correct for the insn in the subsequent
         blocks of the region.  We should use a correct value of
         `clock_var' or modify INSN_TICK.  It is better to keep
         clock_var value equal to 0 at the start of a basic block.
         Therefore we modify INSN_TICK here.  
         Target might have added some instructions to the scheduled block
         in its md_finish () hook.  These new insns don't have any data
         initialized and to identify them we extend h_i_d so that they'll
         get zero luids.  
     Update head/tail boundaries.  

References targetm.

static int schedule_insn ( rtx  )

Referenced by prune_ready_list().

static int schedule_insn ( )
   INSN is the "currently executing insn".  Launch each insn which was
   waiting on INSN.  READY is the ready list which contains the insns
   that are ready to fire.  CLOCK is the current cycle.  The function
   returns necessary cycle advance after issuing the insn (it is not
   zero for insns in a schedule group).  
     Scheduling instruction should have all its dependencies resolved and
     should have been removed from the ready list.  
     Reset debug insns invalidated by moving this insn.  
           ??? Rather than resetting the debug insn, we might be able
           to emit a debug temp before the just-scheduled insn, but
           this would involve checking that the expression at the
           point of the debug insn is equivalent to the expression
           before the just-scheduled insn.  They might not be: the
           expression in the debug insn may depend on other insns not
           yet scheduled that set MEMs, REGs or even other debug
           insns.  It's not clear that attempting to preserve debug
           information in these cases is worth the effort, given how
           uncommon these resets are and the likelihood that the debug
           temps introduced won't survive the schedule change.  
           Unknown location doesn't use any registers.  
               Remove use from the cyclic next_regno_use chain first.  
           We delete rather than resolve these deps, otherwise we
           crash in sched_free_deps(), because forward deps are
           expected to be released before backward deps.  
       INSN has been prematurely moved from the queue to the ready list.
       This is possible only if following flag is set.  
     ??? Probably, if INSN is scheduled prematurely, we should leave
     INSN_TICK untouched.  This is a machine-dependent issue, actually.  
     Update dependent instructions.  First, see if by scheduling this insn
     now we broke a dependence in a way that requires us to change another
     Go through and resolve forward dependencies.  
         Resolve the dependence between INSN and NEXT.
         sd_resolve_dep () moves current dep to another list thus
         advancing the iterator.  
         Don't bother trying to mark next as ready if insn is a debug
         insn.  If insn is the last hard dependency, it will have
         already been discounted.  
           Check always has only one forward dependence (to the first insn in
           the recovery block), therefore, this will be executed only once.  
     Annotate the instruction with issue information -- TImode
     indicates that the instruction is expected not to be able
     to issue on the same cycle as the previous insn.  A machine
     may use this information to decide how the instruction should
     be aligned.  
void schedule_insns ( void  )
   In sched-rgn.c.  
void set_modulo_params ( )
   After the scheduler initialization function has been called, this function
   can be called to enable modulo scheduling.  II is the initiation interval
   we should use, it affects the delays for delay_pairs that were recorded as
   separated by a given number of stages.

   MAX_STAGES provides us with a limit
   after which we give up scheduling; the caller must have unrolled at least
   as many copies of the loop body and recorded delay_pairs for them.
   INSNS is the number of real (non-debug) insns in one iteration of
   the loop.  MAX_UID can be used to test whether an insn belongs to
   the first iteration of the loop; all of them have a uid lower than
int set_priorities ( )
   Set_priorities: compute priority of each insn in the block.  
static void setup_insn_max_reg_pressure ( )
   Set up or update (if UPDATE_P) max register pressure (see its
   meaning in sched-int.h::_haifa_insn_data) for all current BB insns
   after insn AFTER.  

References count, model_add_to_worklist_at(), model_order_p(), model_insn_info::next, and model_insn_info::prev.

static void setup_insn_reg_pressure_info ( )
   Setup info about the current register pressure impact of scheduling
   INSN at the current scheduling point.  
static void setup_ref_regs ( )
   Mark registers in X as mentioned in the current region.  

References reg_class_names, and sched_dump.

Referenced by mark_regno_birth_or_death().

void setup_sched_dump ( void  )
   Set dump and sched_verbose for the desired debugging output.  If no
   dump-file was specified, but -fsched-verbose=N (any N), print to stderr.
   For -fsched-verbose=N, N>=10, print everything to stderr.  
static void swap_sort ( rtx ,
static HAIFA_INLINE void swap_sort ( )
   Resort the array A in which only element at index N may be out of order.  
static void toggle_cancelled_flags ( )
   Walk the ready list and all queues. If any insns have unresolved backwards
   dependencies, these must be cancelled deps, broken by predication.  Set or
   clear (depending on SET) the DEP_CANCELLED bit in DEP_STATUS.  
int try_ready ( )
   Check if NEXT is ready to be added to the ready or queue list.
   If "yes", add it to the proper list.
      -1 - is not ready yet,
       0 - added to the ready list,
   0 < N - queued for N cycles.  
     * if !(old_ts & SPECULATIVE) (e.g. HARD_DEP or 0), then insn might
     have its original pattern or changed (speculative) one.  This is due
     to changing ebb in region scheduling.
     * But if (old_ts & SPECULATIVE), then we are pretty sure that insn
     has speculative pattern.

     We can't assert (!(new_ts & HARD_DEP) || new_ts == old_ts) here because
     control-speculative NEXT could have been discarded by sched-rgn.c
     (the same case as when discarded by can_schedule_ready_p ()).  
         If (old_ts == new_ts), then (old_ts & SPECULATIVE) and we don't
         need to change anything.  
             It would be nice to change DEP_STATUS of all dependences,
             which have ((DEP_STATUS & SPECULATIVE) == new_ts) to HARD_DEP,
             so we won't reanalyze anything.  
             We follow the rule, that every speculative insn
             has non-null ORIG_PAT.  
               If we gonna to overwrite the original pattern of insn,
               save it.  
     We need to restore pattern only if (new_ts == 0), because otherwise it is
     either correct (new_ts & SPECULATIVE),
     or we simply don't care (new_ts & HARD_DEP).  
         We can't assert (QUEUE_INDEX (next) == QUEUE_NOWHERE) here because
         control-speculative NEXT could have been discarded by sched-rgn.c
         (the same case as when discarded by can_schedule_ready_p ()).  
       We should change pattern of every previously speculative
       instruction - and we determine if NEXT was speculative by using
       ORIG_PAT field.  Except one case - speculation checks have ORIG_PAT
       pat too, so skip them.  

References init_dep(), and sd_add_dep().

Referenced by model_reset_queue_indices().

static void undo_all_replacements ( )
   When we know we are going to discard the schedule due to a failed attempt
   at modulo scheduling, undo all replacements.  
         See if we must undo a replacement.  
static void undo_replacements_for_backtrack ( )
   Undo the replacements that have occurred after backtrack point SAVE
   was placed.  

Referenced by save_backtrack_point().

void unlink_bb_notes ( )
   Unlink basic block notes and labels and saves them, so they
   can be easily restored.  We unlink basic block notes in EBB to
   provide back-compatibility with the previous code, as target backends
   assume, that there'll be only instructions between
   current_sched_info->{head and tail}.  We restore these notes as soon
   as we can.
   FIRST (LAST) is the first (last) basic block in the ebb.
   NB: In usual case (FIRST == LAST) nothing is really done.  
     We DON'T unlink basic block notes of the first block in the ebb.  
     Make a sentinel.  
static void unschedule_insns_until ( )
   Pop entries from the SCHEDULED_INSNS vector up to and including INSN.
   Restore their dependencies to an unresolved state, and mark them as
   queued nowhere.  
     Make two passes over the insns to be unscheduled.  First, we clear out
     dependencies and other trivial bookkeeping.  
         This will be changed by restore_backtrack_point if the insn is in
         any queue.  
     A second pass, to update ready and speculation status for insns
     depending on the unscheduled ones.  The first pass must have
     popped the scheduled_insns vector up to the point where we
     restart scheduling, as recompute_todo_spec requires it to be
static void update_insn_after_change ( )
   This function should be called after modifying the pattern of INSN,
   to update scheduler data structures as needed.  
     Invalidate INSN_COST, so it'll be recalculated.  
     Invalidate INSN_TICK, so it'll be recalculated.  
static void update_reg_and_insn_max_reg_pressure ( )
   Update the current register pressure after scheduling INSN.  Update
   also max register pressure for unscheduled insns of the current
static void update_register_pressure ( )
   Update register pressure after scheduling INSN.  
static struct haifa_saved_data* verify_shadows ( )
   Called when we detect that the schedule is impossible.  We examine the
   backtrack queue to find the earliest insn that caused this condition.  
void* xrecalloc ( )
   Extends and fills with zeros (only the new part) array pointed to by P.  

Variable Documentation

bool adding_bb_to_current_region_p = true
   FALSE if we add bb to another region, so we don't need to initialize it.  
basic_block after_recovery
   Basic block just before the EXIT_BLOCK and after recovery, if we have
   created it.  
struct haifa_saved_data* backtrack_queue
   A record, in reverse order, of all scheduled insns which have delay slots
   and may require backtracking.  
rtx* bb_header = 0
   Array used in {unlink, restore}_bb_notes.  
basic_block before_recovery
   Basic block after which recovery blocks will be created.  
int cached_first_cycle_multipass_dfa_lookahead = 0
   The following value is value of hook
   `first_cycle_multipass_dfa_lookahead' at the last call of
int cached_issue_rate = 0
   The following value is value of `issue_rate' at the last call of
struct choice_entry* choice_stack
   The following array is used to implement a stack of choices used in
   function max_issue.  

Referenced by early_queue_to_ready(), and ok_for_early_queue_removal().

int clock_var
struct common_sched_info_def* common_sched_info
   This is a placeholder for the scheduler parameters common
   to all schedulers.  

Referenced by dump_insn_location().

bitmap curr_reg_live
   Register living at given scheduling point.  
int curr_reg_pressure[N_REG_CLASSES]
   The current register pressure.  Only elements corresponding pressure
   classes are defined.  
state_t curr_state
   The following variable value refers for all current and future
   reservations of the processor units.  

Referenced by create_composed_state(), and NDFA_to_DFA().

struct haifa_sched_info* current_sched_info
   Point to state used for the current scheduling pass.  

Referenced by debug_ebb_dependencies(), dump_insn_location(), sched_free_deps(), sd_add_dep(), and sd_copy_back_deps().

int cycle_issued_insns
   The following variable value is number of essential insns issued on
   the current cycle.  An insn is essential one if it changes the
   processors state.  

Referenced by ok_for_early_queue_removal().

hash_table<delay_i1_hasher> delay_htab
   Two hash tables to record delay_pairs, one indexed by I1 and the other
   indexed by I2.  
hash_table<delay_i2_hasher> delay_htab_i2
int dfa_lookahead
   This holds the value of the target dfa_lookahead hook.  

Referenced by early_queue_to_ready(), and ok_for_early_queue_removal().

size_t dfa_state_size
   The following variable value is size of memory representing all
   current and future reservations of the processor units.  

Referenced by early_queue_to_ready(), get_ebb_head_tail(), haifa_sched_init(), max_issue(), ok_for_early_queue_removal(), and remove_insns_that_need_bookkeeping().

   Haifa Instruction Data.  
struct common_sched_info_def haifa_common_sched_info
Initial value:
   Haifa version of sched_info hooks common to all headers.  

Referenced by dump_insn_location().

bool haifa_recovery_bb_ever_added_p
   True, if recovery block was added during this scheduling pass.
   Used to determine if we should have empty memory pools of dependencies
   after finishing current region.  
bool haifa_recovery_bb_recently_added_p
   True, if recovery block was added during scheduling of current block.
   Used to determine, if we need to fix INSN_TICKs.  
rtx* insn_queue
   Queues, etc.  
   An instruction is ready to be scheduled when all insns preceding it
   have already been scheduled.  It is important to ensure that all
   insns which use its result will not be executed until its result
   has been computed.  An insn is maintained in one of four structures:

   (P) the "Pending" set of insns which cannot be scheduled until
   their dependencies have been satisfied.
   (Q) the "Queued" set of insns that can be scheduled when sufficient
   time has passed.
   (R) the "Ready" list of unscheduled, uncommitted insns.
   (S) the "Scheduled" list of insns.

   Initially, all insns are either "Pending" or "Ready" depending on
   whether their dependencies are satisfied.

   Insns move from the "Ready" list to the "Scheduled" list as they
   are committed to the schedule.  As this occurs, the insns in the
   "Pending" list have their dependencies satisfied and move to either
   the "Ready" list or the "Queued" set depending on whether
   sufficient time has passed to make them ready.  As time passes,
   insns move from the "Queued" set to the "Ready" list.

   The "Pending" list (P) are the insns in the INSN_FORW_DEPS of the
   unscheduled insns, i.e., those that are ready, queued, and pending.
   The "Queued" set (Q) is implemented by the variable `insn_queue'.
   The "Ready" list (R) is implemented by the variables `ready' and
   The "Scheduled" list (S) is the new insn chain built by this pass.

   The transition (R->S) is implemented in the scheduling loop in
   `schedule_block' when the best insn to schedule is chosen.
   The transitions (P->R and P->Q) are implemented in `schedule_insn' as
   insns move from the ready list to the scheduled list.
   The transition (Q->R) is implemented in 'queue_to_insn' as time
   passes or stalls are introduced.  
   Implement a circular buffer to delay instructions until sufficient
   time has passed.  For the new pipeline description interface,
   MAX_INSN_QUEUE_INDEX is a power of two minus one which is not less
   than maximal time of instruction execution computed by genattr.c on
   the base maximal time of functional unit reservations and getting a
   result.  This is the longest time an insn may be queued.  
int issue_rate

Instruction scheduling pass. Copyright (C) 1992-2013 Free Software Foundation, Inc. Contributed by Michael Tiemann (tiema.nosp@m.nn@c.nosp@m.ygnus.nosp@m..com) Enhanced by, and currently maintained by, Jim Wilson (wilso.nosp@m.n@cy.nosp@m.gnus..nosp@m.com)

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/.

   Instruction scheduling pass.  This file, along with sched-deps.c,
   contains the generic parts.  The actual entry point is found for
   the normal instruction scheduling pass is found in sched-rgn.c.

   We compute insn priorities based on data dependencies.  Flow
   analysis only creates a fraction of the data-dependencies we must
   observe: namely, only those dependencies which the combiner can be
   expected to use.  For this pass, we must therefore create the
   remaining dependencies we need to observe: register dependencies,
   memory dependencies, dependencies to keep function calls in order,
   and the dependence between a conditional branch and the setting of
   condition codes are all dealt with here.

   The scheduler first traverses the data flow graph, starting with
   the last instruction, and proceeding to the first, assigning values
   to insn_priority as it goes.  This sorts the instructions
   topologically by data dependence.

   Once priorities have been established, we order the insns using
   list scheduling.  This works as follows: starting with a list of
   all the ready insns, and sorted according to priority number, we
   schedule the insn from the end of the list by placing its
   predecessors in the list according to their priority order.  We
   consider this insn scheduled by setting the pointer to the "end" of
   the list to point to the previous insn.  When an insn has no
   predecessors, we either queue it until sufficient time has elapsed
   or add it to the ready list.  As the instructions are scheduled or
   when stalls are introduced, the queue advances and dumps insns into
   the ready list.  When all insns down to the lowest priority have
   been scheduled, the critical path of the basic block has been made
   as short as possible.  The remaining insns are then scheduled in
   remaining slots.

   The following list shows the order in which we want to break ties
   among insns in the ready list:

   1.  choose insn with the longest path to end of bb, ties
   broken by
   2.  choose insn with least contribution to register pressure,
   ties broken by
   3.  prefer in-block upon interblock motion, ties broken by
   4.  prefer useful upon speculative motion, ties broken by
   5.  choose insn with largest control flow probability, ties
   broken by
   6.  choose insn with the least dependences upon the previously
   scheduled insn, or finally
   7   choose the insn which has the most insns dependent on it.
   8.  choose insn with lowest UID.

   Memory references complicate matters.  Only if we can be certain
   that memory references are not part of the data dependency graph
   (via true, anti, or output dependence), can we move operations past
   memory references.  To first approximation, reads can be done
   independently, while writes introduce dependencies.  Better
   approximations will yield fewer dependencies.

   Before reload, an extended analysis of interblock data dependences
   is required for interblock scheduling.  This is performed in
   compute_block_backward_dependences ().

   Dependencies set up by memory references are treated in exactly the
   same way as other dependencies, by using insn backward dependences
   INSN_BACK_DEPS.  INSN_BACK_DEPS are translated into forward dependences
   INSN_FORW_DEPS the purpose of forward list scheduling.

   Having optimized the critical path, we may have also unduly
   extended the lifetimes of some registers.  If an operation requires
   that constants be loaded into registers, it is certainly desirable
   to load those constants as early as necessary, but no earlier.
   I.e., it will not do to load up a bunch of registers at the
   beginning of a basic block only to use them at the end, if they
   could be loaded later, since this may result in excessive register

   Note that since branches are never in basic blocks, but only end
   basic blocks, this pass will not move branches.  But that is ok,
   since we can use GNU's delayed branch scheduling pass to take care
   of this case.

   Also note that no further optimizations based on algebraic
   identities are performed, so this pass would be a good one to
   perform instruction splitting, such as breaking up a multiply
   instruction into shifts and adds where that is profitable.

   Given the memory aliasing analysis that this pass should perform,
   it should be possible to remove redundant stores to memory, and to
   load values from registers instead of hitting memory.

   Before reload, speculative insns are moved only if a 'proof' exists
   that no exception will be caused by this, and if no live registers
   exist that inhibit the motion (live registers constraints are not
   represented by data dependence edges).

   This pass must update information that subsequent passes expect to
   be correct.  Namely: reg_n_refs, reg_n_sets, reg_n_deaths,
   reg_n_calls_crossed, and reg_live_length.  Also, BB_HEAD, BB_END.

   The information in the line number notes is carefully retained by
   this pass.  Notes that refer to the starting and ending of
   exception regions are also carefully retained by this pass.  All
   other NOTE insns are grouped in their same relative order at the
   beginning of basic blocks and regions that have been scheduled.  
   issue_rate is the number of insns that can be scheduled in the same
   machine cycle.  It can be defined in the config/mach/mach.h file,
   otherwise we set it to 1.  
int last_clock_var
   Clock at which the previous instruction was issued.  
rtx last_nondebug_scheduled_insn
   Pointer to the last nondebug instruction scheduled within the
   block, or the prev_head of the scheduling block.  Used by
   rank_for_schedule, so that insns independent of the last scheduled
   insn will be preferred over dependent instructions.  
rtx last_scheduled_insn
   Pointer to the last instruction scheduled.  
int max_lookahead_tries
   The following variable value is maximal number of tries of issuing
   insns for the first cycle multipass insn scheduling.  We define
   this value as constant*(DFA_LOOKAHEAD**ISSUE_RATE).  We would not
   need this constraint if all real insns (with non-negative codes)
   had reservations because in this case the algorithm complexity is
   O(DFA_LOOKAHEAD**ISSUE_RATE).  Unfortunately, the dfa descriptions
   might be incomplete and such insn might occur.  For such
   descriptions, the complexity of algorithm (without the constraint)
   could achieve DFA_LOOKAHEAD ** N , where N is the queue length.  
struct model_pressure_group model_before_pressure
   Describes the pressure before each instruction in the model schedule.  

Referenced by must_restore_pattern_p().

int model_curr_point
   The index of the first instruction in model_schedule that hasn't yet been
   added to the main schedule, or model_num_insns if all of them have.  
struct model_insn_info* model_insns
   Index I describes the instruction with INSN_LUID I.  
unsigned int model_next_priority
   The first unused model_priority value (as used in model_insn_info).  

Referenced by model_promote_insn().

int model_num_insns
   The number of instructions in the model schedule.  
vec<rtx> model_schedule
   Index POINT gives the instruction at point POINT of the model schedule.
   This array doesn't change during main scheduling.  
struct model_insn_info* model_worklist
   The list of instructions in the model worklist, sorted in order of
   decreasing priority.  

Referenced by model_analyze_insns(), and model_init_pressure_group().

int modulo_backtracks_left
   The number of times we should attempt to backtrack when modulo scheduling.
   Decreased each time we have to backtrack.  
int modulo_ii
   The current initiation interval used when modulo scheduling.  
int modulo_insns_scheduled
   The current count of insns in the first iteration of the loop that have
   already been scheduled.  
int modulo_iter0_max_uid
   The maximum uid of insns from the first iteration of the loop.  
int modulo_last_stage
   The stage in which the last insn from the original loop was
int modulo_max_stages
   The maximum number of stages we are prepared to handle.  
int modulo_n_insns
   The number of insns that exist in each iteration of the loop.  We use this
   to detect when we've scheduled all insns from the first iteration.  
bool must_backtrack
   Set to true if, when queuing a shadow insn, we discover that it would be
   scheduled too late.  

Referenced by rank_for_schedule().

vec<int> next_cycle_apply
vec<dep_t> next_cycle_replace_deps
   Two VECs, one to hold dependencies for which pattern replacements
   need to be applied or restored at the start of the next cycle, and
   another to hold an integer that is either one, to apply the
   corresponding replacement, or zero to restore it.  
rtx nonscheduled_insns_begin
   Pointer that iterates through the list of unscheduled insns if we
   have a dbg_cnt enabled.  It always points at an insn prior to the
   first unscheduled one.  

Referenced by reemit_notes().

rtx note_list
   List of important notes we must keep around.  This is a pointer to the
   last element in the list.  
int nr_be_in_control
int nr_be_in_data
int nr_begin_control

Referenced by free_delay_pairs().

int nr_begin_data
   Counters of different types of speculative instructions.  

Referenced by free_delay_pairs().

int q_ptr = 0

Referenced by get_ebb_head_tail().

int q_size = 0

Referenced by get_ebb_head_tail().

struct ready_list ready = {NULL, 0, 0, 0, 0}
   The ready list.  

Referenced by av_set_could_be_blocked_by_bookkeeping_p(), and vinsn_vec_add().

char* ready_try = NULL
   The following array is used to find the best insn from ready when
   the automaton pipeline interface is used.  

Referenced by av_set_could_be_blocked_by_bookkeeping_p(), early_queue_to_ready(), insn_finishes_cycle_p(), and ok_for_early_queue_removal().

struct ready_list* readyp = &ready
   The pointer to the ready list (to be removed).  
bitmap region_ref_regs
   Registers mentioned in the current region.  
bitmap saved_reg_live
   Saved value of the previous array.  
int saved_reg_pressure[N_REG_CLASSES]
   Saved value of the previous array.  
basic_block(* sched_create_empty_bb)(basic_block)
   Create empty basic block after the specified block.  
FILE* sched_dump = 0
   Debugging file.  All printouts are sent to dump, which is always set,
   either to stderr, or to the dump listing file (-dRS).  

Referenced by code_motion_process_successors(), ds_get_max_dep_weak(), dump_ds(), dump_flist(), setup_ref_regs(), and switch_dump().

void(* sched_init_only_bb)(basic_block, basic_block)
vec<int> sched_luids = vNULL
   Mapping from instruction UID to its Logical UID.  
int sched_max_luid = 1
   Next LUID to assign to an instruction.  
bool sched_no_dce
   This can be set to true by a backend if the scheduler should not
   enable a DCE pass.  
enum sched_pressure_algorithm sched_pressure
   Do register pressure sensitive insn scheduling if the flag is set

Referenced by mark_insn_hard_regno_birth().

int sched_ready_n_insns = -1
enum reg_class* sched_regno_pressure_class
   Map regno -> its pressure class.  The map defined only when
basic_block(* sched_split_block)(basic_block, rtx)
   Split block function.  Different schedulers might use different functions
   to handle their internal data consistent.  
int sched_verbose = 0
   sched-verbose controls the amount of debugging output the
   scheduler prints.  It is controlled by -fsched-verbose=N:
   N>0 and no -DSR : the output is directed to stderr.
   N>=10 will direct the printouts to stderr (regardless of -dSR).
   N=1: same as -dSR.
   N=2: bb's probabilities, detailed ready list info, unit/insn info.
   N=3: rtl at abort point, control-flow, regions info.
   N=5: dependences info.  

Referenced by advance_one_cycle(), code_motion_path_driver_cleanup(), code_motion_process_successors(), commit_schedule(), debug_ebb_dependencies(), ds_get_max_dep_weak(), dump_ds(), equal_after_moveup_path_p(), estimate_insn_tick(), free_rgn_deps(), get_ebb_head_tail(), maybe_emit_renaming_copy(), model_last_use_except(), model_promote_insn(), moveup_set_expr(), moving_insn_creates_bookkeeping_block_p(), need_nop_to_preserve_insn_bb(), rank_for_schedule(), remove_insn_from_stream(), sel_region_init(), and undo_transformations().

vec<rtx> scheduled_insns
   This records the actual schedule.  It is built up during the main phase
   of schedule_block, and afterwards used to reorder the insns in the RTL.  

Referenced by sel_region_init().

spec_info_t spec_info = NULL
   Description of the speculative part of the scheduling.
   If NULL - no speculation.  

Referenced by collect_unavailable_regs_from_bnds(), compute_live_below_insn(), and dep_cost_1().

struct spec_info_def spec_info_var