- Generated by
1.8.1.1
|
GCC Middle and Back End API Reference
|
Go to the source code of this file.
Data Structures | |
| struct | expr_history_def_1 |
| struct | _expr |
| struct | _def |
| struct | _bnd |
| struct | _fence |
| struct | flist_tail_def |
| struct | _list_node |
| struct | _list_iterator |
| struct | idata_def |
| struct | vinsn_def |
| struct | transformed_insns |
| struct | _sel_insn_data |
| struct | sel_global_bb_info_def |
| struct | sel_region_bb_info_def |
| struct | succ_iterator |
| struct | succs_info |
Typedefs | |
| typedef void * | tc_t |
| typedef struct _list_node * | _list_t |
| typedef struct idata_def * | idata_t |
| typedef struct vinsn_def * | vinsn_t |
| typedef _list_t | _xlist_t |
| typedef rtx | insn_t |
| typedef _xlist_t | ilist_t |
| typedef struct expr_history_def_1 | expr_history_def |
| typedef struct _expr | expr_def |
| typedef expr_def * | expr_t |
| typedef struct _def * | def_t |
| typedef _list_t | av_set_t |
| typedef struct _bnd * | bnd_t |
| typedef _list_t | blist_t |
| typedef struct _fence * | fence_t |
| typedef _list_t | flist_t |
| typedef struct flist_tail_def * | flist_tail_t |
| typedef _list_iterator | _xlist_iterator |
| typedef _xlist_iterator | ilist_iterator |
| typedef _list_iterator | av_set_iterator |
| typedef _list_t | def_list_t |
| typedef _list_iterator | def_list_iterator |
| typedef struct _sel_insn_data | sel_insn_data_def |
| typedef sel_insn_data_def * | sel_insn_data_t |
| typedef enum deps_where_def | deps_where_t |
| typedef sel_global_bb_info_def * | sel_global_bb_info_t |
| typedef sel_region_bb_info_def * | sel_region_bb_info_t |
Enumerations | |
| enum | local_trans_type { TRANS_SUBSTITUTION, TRANS_SPECULATION } |
| enum | deps_where_def { DEPS_IN_INSN, DEPS_IN_LHS, DEPS_IN_RHS, DEPS_IN_NOWHERE } |
| typedef struct _list_node* _list_t |
List backend.
| typedef _list_iterator _xlist_iterator |
| typedef _list_iterator av_set_iterator |
Av set iterators.
| typedef _list_iterator def_list_iterator |
| typedef _list_t def_list_t |
Def list iterators.
| typedef enum deps_where_def deps_where_t |
| typedef struct expr_history_def_1 expr_history_def |
| typedef struct flist_tail_def* flist_tail_t |
| typedef _xlist_iterator ilist_iterator |
| typedef struct _sel_insn_data sel_insn_data_def |
| typedef sel_insn_data_def* sel_insn_data_t |
| typedef void* tc_t |
For state_t.
For reg_note.
tc_t is a short for target context. This is a state of the target backend.
| enum deps_where_def |
| enum local_trans_type |
|
inlinestatic |
Returns true when E1 is an eligible successor edge, possibly skipping empty blocks. When E2P is not null, the resulting edge is written there. FLAGS are used to specify whether back edges and out-of-region edges should be considered.
References succ_iterator::bb, succ_iterator::current_flags, edge_def::dest, succ_iterator::e2, succ_iterator::flags, in_current_region_p(), basic_block_def::index, basic_block_def::loop_father, pipelining_p, sel_bb_empty_or_nop_p(), sel_bb_empty_p(), edge_def::src, and basic_block_def::succs.
|
inlinestatic |
References _list_alloc().
Referenced by _xlist_add().
|
inlinestatic |
References pool_alloc().
Referenced by _list_add().
|
inlinestatic |
References _list_remove().
|
inlinestatic |
|
inline |
|
inlinestatic |
Used through _FOR_EACH.
|
inlinestatic |
References _list_iterator::lp, and _list_iterator::removed_p.
|
inlinestatic |
References _list_remove(), _list_iterator::can_remove_p, _list_iterator::lp, and _list_iterator::removed_p.
|
inlinestatic |
|
inlinestatic |
References _list_iterator::can_remove_p, _list_iterator::lp, and _list_iterator::removed_p.
|
inlinestatic |
References pool_free().
Referenced by _list_clear(), and _list_iter_remove().
|
inlinestatic |
Referenced by _list_iter_remove_nofree().
|
inlinestatic |
References succ_iterator::bb, succ_iterator::bb_end, bb_note(), succ_iterator::current_exit, succ_iterator::current_flags, edge_def::dest, succ_iterator::e1, succ_iterator::e2, succ_iterator::ei, ei_cond(), ei_next(), exit_insn, succ_iterator::flags, get_all_loop_exits(), in_current_region_p(), basic_block_def::index, succ_iterator::loop_exits, and sel_bb_head().
|
inlinestatic |
|
inlinestatic |
We need to return a succ_iterator to avoid 'unitialized' warning during bootstrap.
References succ_iterator::bb, succ_iterator::bb_end, edge_iterator::container, succ_iterator::current_exit, succ_iterator::current_flags, succ_iterator::e1, succ_iterator::e2, succ_iterator::ei, succ_iterator::flags, edge_iterator::index, succ_iterator::loop_exits, and basic_block_def::succs.
|
inlinestatic |
_xlist_t functions.
References _list_add().
|
inlinestatic |
| void add_clean_fence_to_fences | ( | flist_tail_t | , |
| insn_t | , | ||
| fence_t | |||
| ) |
Referenced by extract_new_fences_from().
| void add_dirty_fence_to_fences | ( | flist_tail_t | , |
| insn_t | , | ||
| fence_t | |||
| ) |
Referenced by extract_new_fences_from().
Deps context functions.
Referenced by update_boundaries().
| void alloc_sched_pools | ( | void | ) |
Referenced by sel_global_init().
Av set functions.
Referenced by compute_av_set_inside_bb(), find_sequential_best_exprs(), and undo_transformations().
| void av_set_clear | ( | av_set_t * | ) |
Referenced by code_motion_path_driver().
Referenced by collect_unavailable_regs_from_bnds(), compute_av_set_at_bb_end(), and fill_insns().
| void av_set_iter_remove | ( | av_set_iterator * | ) |
| void av_set_leave_one_nonspec | ( | av_set_t * | ) |
Referenced by code_motion_path_driver().
Referenced by code_motion_path_driver(), compute_av_set_inside_bb(), and update_and_record_unavailable_insns().
| void av_set_split_usefulness | ( | av_set_t | , |
| int | , | ||
| int | |||
| ) |
Referenced by compute_av_set_at_bb_end().
| void av_set_substract_cond_branches | ( | av_set_t * | ) |
Referenced by compute_av_set_at_bb_end().
Referenced by compute_av_set_at_bb_end(), compute_av_set_on_boundaries(), and undo_transformations().
Referenced by compute_av_set_at_bb_end().
| bool bb_ends_ebb_p | ( | basic_block | ) |
Referenced by find_ebb_boundaries(), and sel_sched_region_1().
| bool bb_header_p | ( | insn_t | ) |
|
inlinestatic |
Return the next block of BB not running into inconsistencies.
References basic_block_def::next_bb, single_succ(), and basic_block_def::succs.
Referenced by find_ebb_boundaries(), and sel_sched_region_1().
Referenced by fill_insns(), and update_boundaries().
| void blist_remove | ( | blist_t * | ) |
Referenced by fill_insns(), and update_boundaries().
| bool bookkeeping_can_be_created_if_moved_through_p | ( | insn_t | ) |
Referenced by moveup_expr(), and moving_insn_creates_bookkeeping_block_p().
| void clear_expr | ( | expr_t | ) |
| void clear_outdated_rtx_info | ( | basic_block | ) |
Referenced by sel_sched_region_1().
|
read |
Referenced by compute_av_set_at_bb_end().
| bool considered_for_pipelining_p | ( | struct loop * | ) |
| void copy_data_sets | ( | basic_block | , |
| basic_block | |||
| ) |
EXPR functions.
Referenced by compute_av_set_inside_bb(), and undo_transformations().
Referenced by equal_after_moveup_path_p(), and move_op_orig_expr_found().
Referenced by emit_bookkeeping_insn(), and substitute_reg_in_expr().
Expression transformation routines.
Referenced by create_insn_rtx_with_lhs(), create_insn_rtx_with_rhs(), and create_speculation_check().
| tc_t create_target_context | ( | bool | ) |
Target context functions.
Referenced by emit_bookkeeping_insn(), replace_dest_with_reg_in_expr(), and substitute_reg_in_expr().
| void def_list_add | ( | def_list_t * | , |
| insn_t | , | ||
| bool | |||
| ) |
Referenced by fur_orig_expr_found().
| void exchange_data_sets | ( | basic_block | , |
| basic_block | |||
| ) |
Referenced by generate_bookkeeping_insn().
Referenced by maybe_emit_renaming_copy(), and substitute_reg_in_expr().
| unsigned expr_dest_regno | ( | expr_t | ) |
| basic_block fallthru_bb_of_jump | ( | rtx | ) |
Referenced by moveup_expr().
| int find_in_history_vect | ( | vec< expr_history_def > | , |
| rtx | , | ||
| vinsn_t | , | ||
| bool | |||
| ) |
Referenced by undo_transformations().
| void flist_clear | ( | flist_t * | ) |
Referenced by calculate_new_fences().
Referenced by find_place_for_bookkeeping(), and sel_dump_cfg_2().
| void flist_tail_init | ( | flist_tail_t | ) |
Referenced by calculate_new_fences(), and sel_sched_region_1().
| void free_bb_note_pool | ( | void | ) |
Referenced by sel_global_finish().
| void free_data_for_scheduled_insn | ( | insn_t | ) |
Referenced by update_seqnos_and_stage().
| void free_data_sets | ( | basic_block | ) |
| void free_lv_sets | ( | void | ) |
Referenced by sel_global_finish().
| void free_nop_and_exit_insns | ( | void | ) |
Referenced by sel_global_finish().
| void free_nop_pool | ( | void | ) |
Referenced by sel_region_finish().
| void free_nop_vinsn | ( | void | ) |
Referenced by sel_region_finish().
| void free_regset_pool | ( | void | ) |
Referenced by sel_global_finish().
| void free_sched_pools | ( | void | ) |
Referenced by sel_global_finish().
| void free_succs_info | ( | struct succs_info * | ) |
Referenced by compute_av_set_at_bb_end().
Collect all loop exits recursively, skipping empty BBs between them. E.g. if BB is a loop header which has several loop exits, traverse all of them and if any of them turns out to be another loop header (after skipping empty BBs), add its loop exits to the resulting vector as well.
References edge_def::dest, loop::exits, get_loop_exit_edges_unique_dests(), in_current_region_p(), inner_loop_header_p(), basic_block_def::loop_father, loop_outer(), sel_bb_empty_or_nop_p(), single_succ(), basic_block_def::succs, and vNULL.
Referenced by _succ_iter_cond().
| int get_av_level | ( | insn_t | ) |
| regset get_clear_regset_from_pool | ( | void | ) |
Referenced by compute_live_after_bb(), find_best_reg_for_expr(), fur_orig_expr_found(), and move_cond_jump().
Referenced by replace_src_with_reg_ok_p().
Return exit edges of LOOP, filtering out edges with the same dest bb.
References edge_def::dest, loop_exit::e, loop::exits, loop::latch, LOOPS_HAVE_RECORDED_EXITS, loop_exit::next, and vNULL.
Referenced by get_all_loop_exits().
| loop_p get_loop_nest_for_rgn | ( | unsigned | int | ) |
Referenced by setup_current_loop_nest().
Referenced by prepare_place_to_insert(), and remove_insn_from_stream().
| regset get_regset_from_pool | ( | void | ) |
Pool functions.
Referenced by compute_live().
| int get_seqno_by_preds | ( | rtx | ) |
Referenced by find_seqno_for_bookkeeping().
Referenced by moveup_expr(), and moveup_expr_inside_insn_group().
| bool in_current_region_p | ( | basic_block | ) |
Referenced by extract_new_fences_from().
| void init_fences | ( | insn_t | ) |
Fences functions.
Referenced by sel_sched_region_1().
| void init_lv_sets | ( | void | ) |
Various initialization functions.
Referenced by sel_global_init().
|
inlinestatic |
True when BB is a header of the inner loop.
References flow_bb_inside_loop_p(), loop::header, loop_depth(), and basic_block_def::loop_father.
Referenced by get_all_loop_exits().
| void insert_in_history_vect | ( | vec< expr_history_def > * | , |
| unsigned | , | ||
| enum | local_trans_type, | ||
| vinsn_t | , | ||
| vinsn_t | , | ||
| ds_t | |||
| ) |
Referenced by moveup_expr_cached(), and try_transformation_cache().
| bool insn_at_boundary_p | ( | insn_t | ) |
| bool insn_eligible_for_subst_p | ( | insn_t | ) |
| sel_insn_data_def insn_sid | ( | insn_t | ) |
Functions to work with insns.
Referenced by move_op_orig_expr_not_found().
| void make_region_from_loop_preheader | ( | vec< basic_block > *& | ) |
Referenced by compute_av_set_at_bb_end().
Referenced by move_op_merge_succs().
| expr_t merge_with_other_exprs | ( | av_set_t * | , |
| av_set_iterator * | , | ||
| expr_t | |||
| ) |
Referenced by moveup_set_expr().
| void move_fence_to_fences | ( | flist_t | , |
| flist_tail_t | |||
| ) |
Referenced by calculate_new_fences(), and extract_new_fences_from().
| void purge_empty_blocks | ( | void | ) |
Referenced by sel_sched_region_1().
| void recompute_vinsn_lhs_rhs | ( | vinsn_t | ) |
Referenced by av_set_could_be_blocked_by_bookkeeping_p(), and substitute_reg_in_expr().
| void reset_target_context | ( | tc_t | , |
| bool | |||
| ) |
Referenced by fill_insns().
| void return_nop_to_pool | ( | insn_t | , |
| bool | |||
| ) |
Referenced by remove_temp_moveop_nops(), and schedule_expr_on_boundary().
| void return_regset_to_pool | ( | regset | ) |
Referenced by compute_live(), find_best_reg_for_expr(), and fur_orig_expr_found().
| void sel_add_loop_preheaders | ( | bb_vec_t * | ) |
Referenced by setup_current_loop_nest().
|
static |
References first, last, sel_bb_end(), and sel_bb_head().
Referenced by _eligible_successor_edge_p(), and get_all_loop_exits().
| bool sel_bb_empty_p | ( | basic_block | ) |
| insn_t sel_bb_end | ( | basic_block | ) |
| bool sel_bb_end_p | ( | insn_t | ) |
Referenced by code_motion_path_driver(), compute_av_set_at_bb_end(), extract_new_fences_from(), fill_insns(), and update_boundaries().
| insn_t sel_bb_head | ( | basic_block | ) |
Basic block and CFG functions.
Referenced by _succ_iter_cond(), code_motion_path_driver(), compute_live_after_bb(), create_block_for_bookkeeping(), extract_new_fences_from(), find_place_for_bookkeeping(), generate_bookkeeping_insn(), move_cond_jump(), moveup_expr_cached(), need_nop_to_preserve_insn_bb(), sel_bb_empty_or_nop_p(), sel_region_init(), sel_sched_region_1(), and update_and_record_unavailable_insns().
| bool sel_bb_head_p | ( | insn_t | ) |
| void sel_clear_has_dependence | ( | void | ) |
Dependence analysis functions.
Referenced by moveup_expr().
| basic_block sel_create_recovery_block | ( | insn_t | ) |
Referenced by create_speculation_check().
| void sel_extend_global_bb_info | ( | void | ) |
Referenced by sel_global_init().
| void sel_finish_bbs | ( | void | ) |
Referenced by sel_region_finish().
| void sel_finish_global_and_expr | ( | void | ) |
Referenced by sel_region_finish().
| void sel_finish_global_bb_info | ( | void | ) |
Referenced by sel_global_finish().
| void sel_finish_pipelining | ( | void | ) |
Referenced by sel_global_finish().
Referenced by emit_insn_from_expr_after().
Referenced by create_speculation_check(), and maybe_emit_renaming_copy().
Referenced by create_speculation_check().
| void sel_init_bbs | ( | bb_vec_t | ) |
Referenced by sel_region_init().
| void sel_init_global_and_expr | ( | bb_vec_t | ) |
Referenced by sel_region_init().
| void sel_init_invalid_data_sets | ( | insn_t | ) |
| void sel_init_pipelining | ( | void | ) |
| bool sel_insn_has_single_succ_p | ( | insn_t | , |
| int | |||
| ) |
| bool sel_is_loop_preheader_p | ( | basic_block | ) |
Referenced by sel_region_init(), sel_region_target_finish(), and sel_sched_region_1().
Referenced by schedule_expr_on_boundary().
| bool sel_num_cfg_preds_gt_1 | ( | insn_t | ) |
Referenced by move_op_at_first_insn().
| bool sel_redirect_edge_and_branch | ( | edge | , |
| basic_block | |||
| ) |
Referenced by create_block_for_bookkeeping().
| void sel_redirect_edge_and_branch_force | ( | edge | , |
| basic_block | |||
| ) |
Referenced by create_block_for_bookkeeping().
| void sel_register_cfg_hooks | ( | void | ) |
Referenced by sel_region_init().
| bool sel_remove_insn | ( | insn_t | , |
| bool | , | ||
| bool | |||
| ) |
Referenced by remove_insn_from_stream().
| void sel_save_haifa_priorities | ( | void | ) |
| void sel_sched_region | ( | int | ) |
Referenced by run_selective_scheduling().
| void sel_set_sched_flags | ( | void | ) |
Referenced by sel_region_init().
| void sel_setup_sched_infos | ( | void | ) |
Referenced by sel_global_init(), and sel_region_init().
| basic_block sel_split_edge | ( | edge | ) |
Referenced by move_cond_jump().
| void sel_unregister_cfg_hooks | ( | void | ) |
Referenced by sel_region_finish().
| int sel_vinsn_cost | ( | vinsn_t | ) |
Referenced by create_speculation_check(), fill_vec_av_set(), and find_best_reg_for_expr().
| void set_target_context | ( | tc_t | ) |
Referenced by fill_insns().
| void setup_nop_and_exit_insns | ( | void | ) |
Referenced by sel_global_init().
| void setup_nop_vinsn | ( | void | ) |
Referenced by sel_region_init().
Referenced by create_speculation_check(), and moveup_expr().
Referenced by fill_vec_av_set().
| bool tidy_control_flow | ( | basic_block | , |
| bool | |||
| ) |
Referenced by move_cond_jump(), and move_op_at_first_insn().
| void vinsn_attach | ( | vinsn_t | ) |
Referenced by moveup_expr_cached(), update_transformation_cache(), and vinsn_vec_add().
| bool vinsn_cond_branch_p | ( | vinsn_t | ) |
Referenced by schedule_expr_on_boundary().
Referenced by schedule_expr_on_boundary(), and try_transformation_cache().
| void vinsn_detach | ( | vinsn_t | ) |
Referenced by moveup_expr_cached(), and vinsn_vec_clear().
Referenced by equal_after_moveup_path_p(), undo_transformations(), and vinsn_vec_has_expr_p().
| bool vinsn_separable_p | ( | vinsn_t | ) |
Vinsns functions.
| basic_block after_recovery |
Some needed definitions.
Basic block just before the EXIT_BLOCK and after recovery, if we have created it.
Referenced by sel_global_init().
| sbitmap bbs_pipelined |
Saves pipelined blocks. Bitmap is indexed by bb->index.
| bitmap blocks_to_reschedule |
Blocks that need to be rescheduled after pipelining.
| bool bookkeeping_p |
True if bookkeeping is enabled.
Referenced by remove_insns_that_need_bookkeeping(), sel_sched_region_1(), and sel_setup_region_sched_flags().
| struct loop* current_loop_nest |
The loop nest being pipelined.
Referenced by create_block_for_bookkeeping(), fill_vec_av_set(), schedule_expr_on_boundary(), sel_region_init(), sel_sched_region_1(), sel_setup_region_sched_flags(), and setup_current_loop_nest().
| bool enable_moveup_set_path_p |
Various flags.
| rtx exit_insn |
An insn that 'contained' in EXIT block.
Referenced by _succ_iter_cond().
| flist_t fences |
A list of fences currently in the works.
Current fences.
Referenced by calculate_new_fences(), schedule_on_fences(), and sel_dump_cfg_2().
| bitmap_head* forced_ebb_heads |
Used in bb_in_ebb_p.
| int global_level |
A global level shows whether an insn is valid or not.
GLOBAL_LEVEL is used to discard information stored in basic block headers av_sets. Av_set of bb header is valid if its (bb header's) level is equal to GLOBAL_LEVEL. And invalid if lesser. This is primarily used to advance scheduling window.
Referenced by compute_av_set_inside_bb(), move_cond_jump(), sel_sched_region_1(), and update_seqnos_and_stage().
| int max_insns_to_rename |
Maximum number of insns that are eligible for renaming.
Referenced by fill_vec_av_set(), and sel_setup_region_sched_flags().
| rtx nop_pattern |
A NOP pattern used as a placeholder for real insns.
| bool pipelining_p |
@verbatim Instruction scheduling pass. Selective scheduler and pipeliner.
Copyright (C) 2006-2013 Free Software Foundation, Inc.
This file is part of GCC.
GCC is free software; you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation; either version 3, or (at your option) any later version.
GCC is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.
You should have received a copy of the GNU General Public License along with GCC; see the file COPYING3. If not see http://www.gnu.org/licenses/.
Implementation of selective scheduling approach.
The below implementation follows the original approach with the following
changes:
o the scheduler works after register allocation (but can be also tuned
to work before RA);
o some instructions are not copied or register renamed;
o conditional jumps are not moved with code duplication;
o several jumps in one parallel group are not supported;
o when pipelining outer loops, code motion through inner loops
is not supported;
o control and data speculation are supported;
o some improvements for better compile time/performance were made.
Terminology
===========
A vinsn, or virtual insn, is an insn with additional data characterizing
insn pattern, such as LHS, RHS, register sets used/set/clobbered, etc.
Vinsns also act as smart pointers to save memory by reusing them in
different expressions. A vinsn is described by vinsn_t type.
An expression is a vinsn with additional data characterizing its properties
at some point in the control flow graph. The data may be its usefulness,
priority, speculative status, whether it was renamed/subsituted, etc.
An expression is described by expr_t type.
Availability set (av_set) is a set of expressions at a given control flow
point. It is represented as av_set_t. The expressions in av sets are kept
sorted in the terms of expr_greater_p function. It allows to truncate
the set while leaving the best expressions.
A fence is a point through which code motion is prohibited. On each step,
we gather a parallel group of insns at a fence. It is possible to have
multiple fences. A fence is represented via fence_t.
A boundary is the border between the fence group and the rest of the code.
Currently, we never have more than one boundary per fence, as we finalize
the fence group when a jump is scheduled. A boundary is represented
via bnd_t.
High-level overview
===================
The scheduler finds regions to schedule, schedules each one, and finalizes.
The regions are formed starting from innermost loops, so that when the inner
loop is pipelined, its prologue can be scheduled together with yet unprocessed
outer loop. The rest of acyclic regions are found using extend_rgns:
the blocks that are not yet allocated to any regions are traversed in top-down
order, and a block is added to a region to which all its predecessors belong;
otherwise, the block starts its own region.
The main scheduling loop (sel_sched_region_2) consists of just
scheduling on each fence and updating fences. For each fence,
we fill a parallel group of insns (fill_insns) until some insns can be added.
First, we compute available exprs (av-set) at the boundary of the current
group. Second, we choose the best expression from it. If the stall is
required to schedule any of the expressions, we advance the current cycle
appropriately. So, the final group does not exactly correspond to a VLIW
word. Third, we move the chosen expression to the boundary (move_op)
and update the intermediate av sets and liveness sets. We quit fill_insns
when either no insns left for scheduling or we have scheduled enough insns
so we feel like advancing a scheduling point.
Computing available expressions
===============================
The computation (compute_av_set) is a bottom-up traversal. At each insn,
we're moving the union of its successors' sets through it via
moveup_expr_set. The dependent expressions are removed. Local
transformations (substitution, speculation) are applied to move more
exprs. Then the expr corresponding to the current insn is added.
The result is saved on each basic block header.
When traversing the CFG, we're moving down for no more than max_ws insns.
Also, we do not move down to ineligible successors (is_ineligible_successor),
which include moving along a back-edge, moving to already scheduled code,
and moving to another fence. The first two restrictions are lifted during
pipelining, which allows us to move insns along a back-edge. We always have
an acyclic region for scheduling because we forbid motion through fences.
Choosing the best expression
============================
We sort the final availability set via sel_rank_for_schedule, then we remove
expressions which are not yet ready (tick_check_p) or which dest registers
cannot be used. For some of them, we choose another register via
find_best_reg. To do this, we run find_used_regs to calculate the set of
registers which cannot be used. The find_used_regs function performs
a traversal of code motion paths for an expr. We consider for renaming
only registers which are from the same regclass as the original one and
using which does not interfere with any live ranges. Finally, we convert
the resulting set to the ready list format and use max_issue and reorder*
hooks similarly to the Haifa scheduler.
Scheduling the best expression
==============================
We run the move_op routine to perform the same type of code motion paths
traversal as in find_used_regs. (These are working via the same driver,
code_motion_path_driver.) When moving down the CFG, we look for original
instruction that gave birth to a chosen expression. We undo
the transformations performed on an expression via the history saved in it.
When found, we remove the instruction or leave a reg-reg copy/speculation
check if needed. On a way up, we insert bookkeeping copies at each join
point. If a copy is not needed, it will be removed later during this
traversal. We update the saved av sets and liveness sets on the way up, too.
Finalizing the schedule
=======================
When pipelining, we reschedule the blocks from which insns were pipelined
to get a tighter schedule. On Itanium, we also perform bundling via
the same routine from ia64.c.
Dependence analysis changes
===========================
We augmented the sched-deps.c with hooks that get called when a particular
dependence is found in a particular part of an insn. Using these hooks, we
can do several actions such as: determine whether an insn can be moved through
another (has_dependence_p, moveup_expr); find out whether an insn can be
scheduled on the current cycle (tick_check_p); find out registers that
are set/used/clobbered by an insn and find out all the strange stuff that
restrict its movement, like SCHED_GROUP_P or CANT_MOVE (done in
init_global_and_expr_for_insn).
Initialization changes
======================
There are parts of haifa-sched.c, sched-deps.c, and sched-rgn.c that are
reused in all of the schedulers. We have split up the initialization of data
of such parts into different functions prefixed with scheduler type and
postfixed with the type of data initialized: {,sel_,haifa_}sched_{init,finish},
sched_rgn_init/finish, sched_deps_init/finish, sched_init_{luids/bbs}, etc.
The same splitting is done with current_sched_info structure:
dependence-related parts are in sched_deps_info, common part is in
common_sched_info, and haifa/sel/etc part is in current_sched_info.
Target contexts
===============
As we now have multiple-point scheduling, this would not work with backends
which save some of the scheduler state to use it in the target hooks.
For this purpose, we introduce a concept of target contexts, which
encapsulate such information. The backend should implement simple routines
of allocating/freeing/setting such a context. The scheduler calls these
as target hooks and handles the target context as an opaque pointer (similar
to the DFA state type, state_t).
Various speedups
================
As the correct data dependence graph is not supported during scheduling (which
is to be changed in mid-term), we cache as much of the dependence analysis
results as possible to avoid reanalyzing. This includes: bitmap caches on
each insn in stream of the region saying yes/no for a query with a pair of
UIDs; hashtables with the previously done transformations on each insn in
stream; a vector keeping a history of transformations on each expr.
Also, we try to minimize the dependence context used on each fence to check
whether the given expression is ready for scheduling by removing from it
insns that are definitely completed the execution. The results of
tick_check_p checks are also cached in a vector on each fence.
We keep a valid liveness set on each insn in a region to avoid the high
cost of recomputation on large basic blocks.
Finally, we try to minimize the number of needed updates to the availability
sets. The updates happen in two cases: when fill_insns terminates,
we advance all fences and increase the stage number to show that the region
has changed and the sets are to be recomputed; and when the next iteration
of a loop in fill_insns happens (but this one reuses the saved av sets
on bb headers.) Thus, we try to break the fill_insns loop only when
"significant" number of insns from the current scheduling window was
scheduled. This should be made a target param.
TODO: correctly support the data dependence graph at all stages and get rid
of all caches. This should speed up the scheduler.
TODO: implement moving cond jumps with bookkeeping copies on both targets.
TODO: tune the scheduler before RA so it does not create too much pseudos.
References:
S.-M. Moon and K. Ebcioglu. Parallelizing nonnumerical code with
selective scheduling and software pipelining.
ACM TOPLAS, Vol 19, No. 6, pages 853--898, Nov. 1997.
Andrey Belevantsev, Maxim Kuvyrkov, Vladimir Makarov, Dmitry Melnik,
and Dmitry Zhurikhin. An interblock VLIW-targeted instruction scheduler
for GCC. In Proceedings of GCC Developers' Summit 2006.
Arutyun Avetisyan, Andrey Belevantsev, and Dmitry Melnik. GCC Instruction
Scheduler and Software Pipeliner on the Itanium Platform. EPIC-7 Workshop.
http://rogue.colorado.edu/EPIC7/. True when pipelining is enabled.
Referenced by _eligible_successor_edge_p(), extract_new_fences_from(), fill_insns(), fill_vec_av_set(), find_seqno_for_bookkeeping(), invoke_reorder_hooks(), is_ineligible_successor(), process_spec_exprs(), process_use_exprs(), schedule_expr_on_boundary(), sel_sched_region(), sel_sched_region_1(), sel_setup_region_sched_flags(), and update_seqnos_and_stage().
| bool preheader_removed |
Referenced by sel_region_init().
| vec<sel_insn_data_def> s_i_d |
Referenced by sel_print_insn().
| alloc_pool sched_lists_pool |
_list_t functions. All of _*list_* functions are used through accessor macros, thus we can't move them in sel-sched-ir.c.
| regset sel_all_regs |
| vec<sel_global_bb_info_def> sel_global_bb_info |
Per basic block data. This array is indexed by basic block index.
| vec<sel_region_bb_info_def> sel_region_bb_info |
Per basic block data. This array is indexed by basic block index.
1.8.1.1