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

Data Structures

struct  bblst
struct  candidate
struct  edgelst


typedef sbitmap edgeset


static int is_cfg_nonregular (void)
static void find_single_block_region (bool)
static void find_rgns (void)
static bool too_large (int, int *, int *)
static void extract_edgelst (sbitmap, edgelst *)
static void split_edges (int, int, edgelst *)
static void compute_trg_info (int)
void debug_candidate (int)
void debug_candidates (int)
static int check_live_1 (int, rtx)
static void update_live_1 (int, rtx)
static int is_pfree (rtx, int, int)
static int find_conditional_protection (rtx, int)
static int is_conditionally_protected (rtx, int, int)
static int is_prisky (rtx, int, int)
static int is_exception_free (rtx, int, int)
static bool sets_likely_spilled (rtx)
static void sets_likely_spilled_1 (rtx, const_rtx, void *)
static void add_branch_dependences (rtx, rtx)
static void compute_block_dependences (int)
static void schedule_region (int)
static void concat_insn_mem_list (rtx, rtx, rtx *, rtx *)
static void propagate_deps (int, struct deps_desc *)
static void free_pending_lists (void)
static void extract_edgelst ()
DEBUG_FUNCTION void debug_regions ()
DEBUG_FUNCTION void debug_region ()
static bool bb_in_region_p ()
void dump_region_dot ()
void dump_region_dot_file ()
static void find_single_block_region ()
static int rgn_estimate_number_of_insns ()
static bool too_large ()
static void haifa_find_rgns ()
static int gather_region_statistics (int **)
static void print_region_statistics (int *, int, int *, int)
static int gather_region_statistics ()
static void print_region_statistics ()
void extend_rgns ()
static void compute_dom_prob_ps ()
static void split_edges ()
static void compute_trg_info ()
static void free_trg_info ()
DEBUG_FUNCTION void debug_candidate ()
DEBUG_FUNCTION void debug_candidates ()
static int check_live_1 ()
static void update_live_1 ()
static int check_live ()
static void update_live ()
static void set_spec_fed ()
static int find_conditional_protection ()
static int is_conditionally_protected ()
static int is_pfree ()
static int is_prisky ()
static int is_exception_free ()
static void init_ready_list (void)
static int can_schedule_ready_p (rtx)
static void begin_schedule_ready (rtx)
static ds_t new_ready (rtx, ds_t)
static int schedule_more_p (void)
static const char * rgn_print_insn (const_rtx, int)
static int rgn_rank (rtx, rtx)
static void compute_jump_reg_dependencies (rtx, regset)
static void rgn_add_remove_insn (rtx, int)
static void rgn_add_block (basic_block, basic_block)
static void rgn_fix_recovery_cfg (int, int, int)
static basic_block advance_target_bb (basic_block, rtx)
static int can_schedule_ready_p ()
static void begin_schedule_ready ()
static ds_t new_ready ()
static const char * rgn_print_insn ()
static int rgn_rank ()
int contributes_to_priority ()
static bool rgn_insn_finishes_block_p ()
int get_rgn_sched_max_insns_priority ()
static bool sets_likely_spilled ()
static void sets_likely_spilled_1 ()
static void add_branch_dependences ()
void deps_join ()
static void propagate_deps ()
static void compute_block_dependences ()
static void free_block_dependencies ()
DEBUG_FUNCTION void debug_rgn_dependencies ()
void debug_dependencies (rtx head, rtx tail)
bool sched_is_disabled_for_current_region_p ()
void free_rgn_deps ()
void compute_priorities ()
static void realloc_bb_state_array ()
static void free_bb_state_array ()
static void schedule_region ()
void sched_rgn_init ()
void sched_rgn_finish ()
void rgn_setup_region ()
void sched_rgn_compute_dependencies ()
void sched_rgn_local_init ()
void sched_rgn_local_free ()
void sched_rgn_local_finish ()
void rgn_setup_common_sched_info ()
void rgn_setup_sched_infos ()
void schedule_insns ()
static void rgn_add_remove_insn ()
void extend_regions ()
void rgn_make_new_region_out_of_new_block ()
static void rgn_add_block ()
static void rgn_fix_recovery_cfg ()
static basic_block advance_target_bb ()
static bool gate_handle_sched ()
static unsigned int rest_of_handle_sched ()
static bool gate_handle_sched2 ()
static unsigned int rest_of_handle_sched2 ()
rtl_opt_passmake_pass_sched ()
rtl_opt_passmake_pass_sched2 ()


static int nr_inter
static int nr_spec
int nr_regions = 0
regionrgn_table = NULL
int * rgn_bb_table = NULL
int * block_to_bb = NULL
int * containing_rgn = NULL
int * ebb_head = NULL
static int min_spec_prob
int current_nr_blocks
int current_blocks
static basic_blockbblst_table
static int bblst_size
static int bblst_last
static char * bb_state_array = NULL
static state_tbb_state = NULL
static candidatecandidate_table
int target_bb
static edgeedgelst_table
static int edgelst_last
static sbitmapdom
static int * prob
static int rgn_nr_edges
static edgergn_edges
static edgesetpot_split
static edgesetancestor_edges
static bitmap_head not_in_df
static int sched_target_n_insns
static int target_n_insns
static int sched_n_insns
static struct common_sched_info_def rgn_common_sched_info
static struct sched_deps_info_def rgn_sched_deps_info
static struct sched_deps_info_def rgn_const_sched_deps_info
static struct sched_deps_info_def rgn_const_sel_sched_deps_info
static struct haifa_sched_info rgn_const_sched_info
static struct haifa_sched_info rgn_sched_info
static sbitmap insn_referenced
static struct deps_descbb_deps
static int rgn_n_insns

Typedef Documentation

typedef sbitmap edgeset
   Bit-set of edges, where bit i stands for edge i.  

Function Documentation

static void add_branch_dependences ( rtx  ,
static void add_branch_dependences ( )
   Add dependences so that branches are scheduled to run last in their
     For all branches, calls, uses, clobbers, cc0 setters, and instructions
     that can throw exceptions, force them to remain in order at the end of
     the block by adding dependencies and giving the last a high priority.
     There may be notes present, and prev_head may also be a note.

     Branches must obviously remain at the end.  Calls should remain at the
     end since moving them results in worse register allocation.  Uses remain
     at the end to ensure proper register allocation.

     cc0 setters remain at the end because they can't be moved away from
     their cc0 user.

     COND_EXEC insns cannot be moved past a branch (see e.g. PR17808).

     Insns setting TARGET_CLASS_LIKELY_SPILLED_P registers (usually return
     values) are not moved before reload because we can wind up with register
     allocation failures.  
         Don't overrun the bounds of the basic block.  
     Make sure these insns are scheduled last in their block.  
     Finally, if the block ends in a jump, and we are doing intra-block
     scheduling, make sure that the branch depends on any COND_EXEC insns
     inside the block to avoid moving the COND_EXECs past the branch insn.

     We only have to do this after reload, because (1) before reload there
     are no COND_EXEC insns, and (2) the region scheduler is an intra-block
     scheduler after reload.

     FIXME: We could in some cases move COND_EXEC insns past the branch if
     this scheduler would be a little smarter.  Consider this code:

                T = [addr]
        C  ?    addr += 4
        !C ?    X += 12
        C  ?    T += 1
        C  ?    jump foo

     On a target with a one cycle stall on a memory access the optimal
     sequence would be:

                T = [addr]
        C  ?    addr += 4
        C  ?    T += 1
        C  ?    jump foo
        !C ?    X += 12

     We don't want to put the 'X += 12' before the branch because it just
     wastes a cycle of execution time when the branch is taken.

     Note that in the example "!C" will always be true.  That is another
     possible improvement for handling COND_EXECs in this scheduler: it
     could remove always-true predicates.  
         Note that we want to add this dependency even when
         sched_insns_conditions_mutex_p returns true.  The whole point
         is that we _want_ this dependency, even if these insns really
         are independent.  

References deps_join(), edge_def::dest, basic_block_def::index, deps_desc::pending_jump_insns, deps_desc::pending_read_insns, deps_desc::pending_read_mems, deps_desc::pending_write_insns, deps_desc::pending_write_mems, and basic_block_def::succs.

static basic_block advance_target_bb ( basic_block  ,
static basic_block advance_target_bb ( )
   Return next block in ebb chain.  For parameter meaning please refer to
   sched-int.h: struct sched_info: advance_target_bb.  
static bool bb_in_region_p ( )
   True when a bb with index BB_INDEX contained in region RGN.  

References probability_cutoff, and profile_info.

static void begin_schedule_ready ( rtx  )
static void begin_schedule_ready ( )
   Updates counter and other information.  Split from can_schedule_ready_p ()
   because when we schedule insn speculatively then insn passed to
   can_schedule_ready_p () differs from the one passed to
   begin_schedule_ready ().  
     An interblock motion?  
             For speculative load, mark insns fed by it.  
         In block motion.  
static int can_schedule_ready_p ( rtx  )
static int can_schedule_ready_p ( )
   Called after taking INSN from the ready list.  Returns nonzero if this
   insn can be scheduled, nonzero if we should silently discard it.  
     An interblock motion?  
static int check_live ( )
   Return 1 if insn can be speculatively moved from block src to trg,
   otherwise return 0.  Called before first insertion of insn to
   ready-list or before the scheduling.  
     Find the registers set by instruction.  

References bblst::nr_members, and candidate::split_bbs.

Referenced by is_prisky().

static int check_live_1 ( int  ,
   Speculative scheduling functions.  

Referenced by check_live_1().

static int check_live_1 ( )
   Return 0 if x is a set of a register alive in the beginning of one
   of the split-blocks of src, otherwise return 1.  
         Global registers are assumed live.  
             Check for hard registers.  
                     We can have split blocks, that were recently generated.
                     Such blocks are always outside current region.  
             Check for pseudo registers.  

References check_live_1(), and SET.

static void compute_block_dependences ( int  )
static void compute_block_dependences ( )
   Compute dependences inside bb.  In a multiple blocks region:
   (1) a bb is analyzed after its predecessors, and (2) the lists in
   effect at the end of bb (after analyzing for bb) are inherited by
   bb's successors.

   Specifically for reg-reg data dependences, the block insns are
   scanned by sched_analyze () top-to-bottom.  Three lists are
   maintained by sched_analyze (): reg_last[].sets for register DEFs,
   reg_last[].implicit_sets for implicit hard register DEFs, and
   reg_last[].uses for register USEs.

   When analysis is completed for bb, we update for its successors:
   ;  - DEFS[succ] = Union (DEFS [succ], DEFS [bb])
   ;  - IMPLICIT_DEFS[succ] = Union (IMPLICIT_DEFS [succ], IMPLICIT_DEFS [bb])
   ;  - USES[succ] = Union (USES [succ], DEFS [bb])

   The mechanism for computing mem-mem data dependence is very
   similar, and the result is interblock dependences in the region.  
     Do the analysis for this block.  
     Selective scheduling handles control dependencies by itself.  
     Free up the INSN_LISTs.  
static void compute_dom_prob_ps ( )
   Functions for regions scheduling information.  
   Compute dominators, probability, and potential-split-edges of bb.
   Assume that these values were already computed for bb's predecessors.  
     We shouldn't have any real ebbs yet.  
     Initialize dom[bb] to '111..1'.  
static void compute_jump_reg_dependencies ( rtx  insn,
regset  used 
   INSN is a JUMP_INSN.  Store the set of registers that must be
   considered as used by this jump in USED.  
     Nothing to do here, since we postprocess jumps in
void compute_priorities ( void  )
   Compute insn priority for a current region.  
static void compute_trg_info ( int  )
static void compute_trg_info ( )
   Find the valid candidate-source-blocks for the target block TRG, compute
   their probability, and check if they are speculative or not.
   For speculative sources, compute their update-blocks and split-blocks.  
     bblst_table holds split blocks and update blocks for each block after
     the current one in the region.  split blocks and update blocks are
     the TO blocks of region edges, so there can be at most rgn_nr_edges
     of them.  
     Define some of the fields for the target bb as well.  
             In CFGs with low probability edges TF can possibly be zero.  
             Compute split blocks and store them in bblst_table.
             The TO block of every split edge is a split block.  
             Compute update blocks and store them in bblst_table.
             For every split edge, look at the FROM block, and check
             all out edges.  For each out edge that is not a split edge,
             add the TO block to the update block list.  This list can end
             up with a lot of duplicates.  We need to weed them out to avoid
             overrunning the end of the bblst_table.  
             Make sure we didn't overrun the end of bblst_table.  

References bblst::first_member, basic_block_def::index, bblst::nr_members, candidate::split_bbs, and candidate::update_bbs.

static void concat_insn_mem_list ( rtx  copy_insns,
rtx  copy_mems,
rtx old_insns_p,
rtx old_mems_p 
int contributes_to_priority ( )
   NEXT is an instruction that depends on INSN (a backward dependence);
   return nonzero if we should include this dependence in priority
     NEXT and INSN reside in one ebb.  
void debug_candidate ( int  )
DEBUG_FUNCTION void debug_candidate ( )
   Print candidates info, for debugging purposes.  Callable from debugger.  

References global_regs, and update_live_1().

void debug_candidates ( int  )
DEBUG_FUNCTION void debug_candidates ( )
   Print candidates info, for debugging purposes.  Callable from debugger.  

References bitmap_set_bit(), bitmap_set_range(), df_get_live_in(), bblst::first_member, bblst::nr_members, and candidate::update_bbs.

void debug_dependencies ( rtx  head,
rtx  tail 
   Print dependencies information for instructions between HEAD and TAIL.
   ??? This function would probably fit best in haifa-sched.c.  
DEBUG_FUNCTION void debug_region ( )
   Print the region's basic blocks.  
     We don't have ebb_head initialized yet, so we can't use
     BB_TO_BLOCK ().  
DEBUG_FUNCTION void debug_regions ( void  )
   Functions for the construction of regions.  
   Print the regions, for debugging purposes.  Callable from debugger.  
         We don't have ebb_head initialized yet, so we can't use
         BB_TO_BLOCK ().  

References current_blocks, dump_bb(), and rgn_bb_table.

Referenced by free_rgn_deps().

DEBUG_FUNCTION void debug_rgn_dependencies ( )
   Print dependences for debugging starting from FROM_BB.
   Callable from debugger.  
   Print dependences for debugging starting from FROM_BB.
   Callable from debugger.  
void deps_join ( )
   Join PRED_DEPS to the SUCC_DEPS.  
     The reg_last lists are inherited by successor.  
     Mem read/write lists are inherited by successor.  
     last_function_call is inherited by successor.  
     last_function_call_may_noreturn is inherited by successor.  
     sched_before_next_call is inherited by successor.  
void dump_region_dot ( )
   Dump region RGN to file F using dot syntax.  
     We don't have ebb_head initialized yet, so we can't use
     BB_TO_BLOCK ().  
void dump_region_dot_file ( )
   The same, but first open a file specified by FNAME.  
void extend_regions ( void  )
   Extend internal data structures.  
void extend_rgns ( )
   Extend regions.
   DEGREE - Array of incoming edge count, considering only
   the edges, that don't have their sources in formed regions yet.
   IDXP - pointer to the next available index in rgn_bb_table.
   HEADER - set of all region heads.
   LOOP_HDR - mapping from block to the containing loop
   (two blocks can reside within one region if they have
   the same loop header).  
           This block already was processed in find_rgns.  
     The idea is to topologically walk through CFG in top-down order.
     During the traversal, if all the predecessors of a node are
     marked to be in the same region (they all have the same max_hdr),
     then current node is also marked to be a part of that region.
     Otherwise the node starts its own region.
     CFG should be traversed until no further changes are made.  On each
     iteration the set of the region heads is extended (the set of those
     blocks that have max_hdr[bbi] == bbi).  This set is upper bounded by the
     set of all basic blocks, thus the algorithm is guaranteed to
                         If pred wasn't processed in find_rgns.  
                         And pred and bb reside in the same loop.
                         (Or out of any loop).  
                           Then bb extends the containing region of pred.  
                           Too bad, there are at least two predecessors
                           that reside in different regions.  Thus, BB should
                           begin its own region.  
                       BB starts its own region.  
                     If BB start its own region,
                     update set of headers with BB.  
     Statistics were gathered on the SPEC2000 package of tests with
     mainline weekly snapshot gcc-4.1-20051015 on ia64.

     Statistics for SPECint:
     1 iteration : 1751 cases (38.7%)
     2 iterations: 2770 cases (61.3%)
     Blocks wrapped in regions by find_rgns without extension: 18295 blocks
     Blocks wrapped in regions by 2 iterations in extend_rgns: 23821 blocks
     (We don't count single block regions here).

     Statistics for SPECfp:
     1 iteration : 621 cases (35.9%)
     2 iterations: 1110 cases (64.1%)
     Blocks wrapped in regions by find_rgns without extension: 6476 blocks
     Blocks wrapped in regions by 2 iterations in extend_rgns: 11155 blocks
     (We don't count single block regions here).

     By default we do at most 2 iterations.
     This can be overridden with max-sched-extend-regions-iters parameter:
     0 - disable region extension,
     N > 0 - do at most N iterations.  
         Save the old statistics for later printout.  
         We have succeeded.  Now assemble the regions.  
               BBN is a region head.  
                   Here we check whether the region is too_large.  
                   If the region is too_large, then wrap every block of
                   the region into single block region.
                   Here we wrap region head only.  Other blocks are
                   processed in the below cycle.  
                       This cycle iterates over all basic blocks, that
                       are supposed to be in the region with head BBN,
                       and wraps them into that region (or in single
                       block region).  
                           Wrap SUCCN into single block region.  
             Get the new statistics and print the comparison with the
             one before calling this function.  
static void extract_edgelst ( sbitmap  ,
static void extract_edgelst ( )
   Extract list of edges from a bitmap containing EDGE_TO_BIT bits.  
     edgelst table space is reused in each call to extract_edgelst.  
     Iterate over each word in the bitset.  
static int find_conditional_protection ( rtx  ,

Referenced by update_live_1().

static int find_conditional_protection ( )

On the path from the insn to load_insn_bb, find a conditional branch depending on insn, that guards the speculative load.

     Iterate through DEF-USE forward dependences.  
static void find_rgns ( )
   Wrapper function.
   If FLAG_SEL_SCHED_PIPELINING is set, then use custom function to form
   regions.  Otherwise just call find_rgns_haifa.  

Referenced by free_rgn_deps().

static void find_single_block_region ( bool  )
static void find_single_block_region ( )
   Build a single block region for each basic block in the function.
   This allows for using the same code for interblock and basic block
static void free_bb_state_array ( )
   Free the arrays of DFA states at the end of each basic block.  
static void free_block_dependencies ( )
   Free dependencies of instructions inside BB.  
static void free_pending_lists ( )
   Remove all INSN_LISTs and EXPR_LISTs from the pending lists and add
   them to the unused_*_list variables, so that they can be reused.  
void free_rgn_deps ( void  )
   Free all region dependencies saved in INSN_BACK_DEPS and
   INSN_RESOLVED_BACK_DEPS.  The Haifa scheduler does this on the fly
   when scheduling, so this function is supposed to be called from
   the selective scheduling only.  

References calculate_dominance_info(), CDI_DOMINATORS, debug_regions(), find_rgns(), free_dominance_info(), sched_verbose, and sel_sched_p().

static void free_trg_info ( )
   Free the computed target info.  
static bool gate_handle_sched ( )
static bool gate_handle_sched2 ( )

Referenced by schedule_insns().

static int gather_region_statistics ( int **  )
static int gather_region_statistics ( )
   Calculate the histogram that shows the number of regions having the
   given number of basic blocks, and store it in the RSP array.  Return
   the size of this array.  
     a[i] is the number of regions that have (i + 1) basic blocks.  

References bitmap_bit_p(), basic_block_def::index, and edge_def::src.

int get_rgn_sched_max_insns_priority ( void  )
   Returns maximum priority that an insn was assigned to.  
static void haifa_find_rgns ( )
   Find regions for interblock scheduling.

   A region for scheduling can be:

     * A loop-free procedure, or

     * A reducible inner loop, or

     * A basic block not contained in any other region.

   ?!? In theory we could build other regions based on extended basic
   blocks or reverse extended basic blocks.  Is it worth the trouble?

   Loop blocks that form a region are put into the region's block list
   in topological order.

   This procedure stores its results into the following global (ick) variables

     * rgn_nr
     * rgn_table
     * rgn_bb_table
     * block_to_bb
     * containing region

   We use dominator relationships to avoid making regions out of non-reducible

   This procedure needs to be converted to work on pred/succ lists instead
   of edge tables.  That would simplify it somewhat.  
     Note if a block is a natural loop header.  
     Note if a block is a natural inner loop header.  
     Note if a block is in the block queue.  
     Note if a block is in the block queue.  
     Perform a DFS traversal of the cfg.  Identify loop headers, inner loops
     and a mapping from block to its loop header (if the block is contained
     in a loop, else -1).

     Store results in HEADER, INNER, and MAX_HDR respectively, these will
     be used as inputs to the second traversal.

     STACK, SP and DFS_NR are only used during the first traversal.  
     Allocate and initialize variables for the first traversal.  
     DFS traversal to find inner loops in the cfg.  
             We have reached a leaf node or a node that was already
             processed.  Pop edges off the stack until we find
             an edge that has not yet been processed.  
                 Pop entry off the stack.  
             See if have finished the DFS tree traversal.  
             Nope, continue the traversal with the popped node.  
         Process a node.  
         We don't traverse to the exit block.  
         If the successor is in the stack, then we've found a loop.
         Mark the loop, if it is not a natural loop, then it will
         be rejected during the second traversal.  
         If the child was already visited, then there is no need to visit
         it again.  Just update the loop relationships and restart
         with a new edge.  
         Push an entry on the stack and continue DFS traversal.  
     Reset ->aux field used by EDGE_PASSED.  
     Another check for unreachable blocks.  The earlier test in
     is_cfg_nonregular only finds unreachable blocks that do not
     form a loop.

     The DFS traversal will mark every block that is reachable from
     the entry node by placing a nonzero value in dfs_nr.  Thus if
     dfs_nr is zero for any block, then it must be unreachable.  
     Gross.  To avoid wasting memory, the second pass uses the dfs_nr array
     to hold degree counts.  
     Do not perform region scheduling if there are any unreachable
         We use EXTENDED_RGN_HEADER as an addition to HEADER and put
         there basic blocks, which are forced to be region heads.
         This is done to try to assemble few smaller regions
         from a too_large region.  
         Second traversal:find reducible inner loops and topologically sort
         block of each region.  
         Find blocks which are inner loop headers.  We still have non-reducible
         loops to consider at this point.  
                 Now check that the loop is reducible.  We do this separate
                 from finding inner loops so that we do not find a reducible
                 loop which contains an inner non-reducible loop.

                 A simple way to find reducible/natural loops is to verify
                 that each block in the loop is dominated by the loop

                 If there exists a block that is not dominated by the loop
                 header, then the block is reachable from outside the loop
                 and thus the loop is not a natural loop.  
                     First identify blocks in the loop, except for the loop
                     entry block.  
                         Now verify that the block is dominated by the loop
                 If we exited the loop early, then I is the header of
                 a non-reducible loop and we should quit processing it
                 I is a header of an inner loop, or block 0 in a subroutine
                 with no loops at all.  
                   We save degree in case when we meet a too_large region
                   and cancel it.  We need a correct degree later when
                   calling extend_rgns.  
                 Decrease degree of all I's successors for topological
                 Estimate # insns, and count # blocks in the region.  
                 Find all loop latches (blocks with back edges to the loop
                 header) or all the leaf blocks in the cfg has no loops.

                 Place those blocks into the queue.  
                       Leaf nodes have only a single successor which must
                       be EXIT_BLOCK.  
                             This is a loop latch.  
                 Now add all the blocks in the loop to the queue.

             We know the loop is a natural loop; however the algorithm
             above will not always mark certain blocks as being in the
             loop.  Consider:
                node   children
                 a        b,c
                 b        c
                 c        a,d
                 d        b

             The algorithm in the DFS traversal may not mark B & D as part
             of the loop (i.e. they will not have max_hdr set to A).

             We know they can not be loop latches (else they would have
             had max_hdr set since they'd have a backedge to a dominator
             block).  So we don't need them on the initial queue.

             We know they are part of the loop because they are dominated
             by the loop header and can be reached by a backwards walk of
             the edges starting with nodes on the initial queue.

             It is safe and desirable to include those nodes in the
             loop/scheduling region.  To do so we would need to decrease
             the degree of a node if it is the target of a backedge
             within the loop itself as the node is placed in the queue.

             We do not do this because I'm not sure that the actual
             scheduling code will properly handle this case. ?!? 
                         See discussion above about nodes not marked as in
                         this loop during the initial DFS traversal.  
                     Place the loop header into list of region blocks.  
                     Remove blocks from queue[] when their in degree
                     becomes zero.  Repeat until no blocks are left on the
                     list.  This produces a topological list of blocks in
                     the region.  
                     Restore DEGREE.  
                     And force successors of BB to be region heads.
                     This may provide several smaller regions instead
                     of one too_large region.  
     Any block that did not end up in a region is placed into a region
     by itself.  
static void init_ready_list ( void  )
   Implementations of the sched_info functions for region scheduling.  
   Add all insns that are initially ready to the ready list READY.  Called
   once before scheduling a set of insns.  
     Print debugging information.  
     Prepare current target block info.  
     Initialize ready list with all 'ready' insns in target block.
     Count number of insns in the target block being scheduled.  
     Add to ready list all 'ready' insns in valid source blocks.
     For speculative insns, check-live, exception-free, and

References target_bb.

static int is_cfg_nonregular ( )
   Functions for construction of the control flow graph.  
   Return 1 if control flow graph should not be constructed, 0 otherwise.

   We decide not to build the control flow graph if there is possibly more
   than one entry to the function, if computed branches exist, if we
   have nonlocal gotos, or if we have an unreachable loop.  
     If we have a label that could be the target of a nonlocal goto, then
     the cfg is not well structured.  
     If we have any forced labels, then the cfg is not well structured.  
     If we have exception handlers, then we consider the cfg not well
     structured.  ?!?  We should be able to handle this now that we
     compute an accurate cfg for EH.  
     If we have insns which refer to labels as non-jumped-to operands,
     then we consider the cfg not well structured.  
           If this function has a computed jump, then we consider the cfg
           not well structured.  
           For that label not to be seen as a referred-to label, this
           must be a single-set which is feeding a jump *only*.  This
           could be a conditional jump with the label split off for
           machine-specific reasons or a casesi/tablejump.  
     Unreachable loops with more than one basic block are detected
     during the DFS traversal in find_rgns.

     Unreachable loops with a single block are detected here.  This
     test is redundant with the one in find_rgns, but it's much
     cheaper to go ahead and catch the trivial case here.  
     All the tests passed.  Consider the cfg well structured.  
static int is_conditionally_protected ( rtx  ,
int  ,

Referenced by set_spec_fed(), and update_live_1().

static int is_conditionally_protected ( )
   Returns 1 if the same insn1 that participates in the computation
   of load_insn's address is feeding a conditional branch that is
   guarding on load_insn. This is true if we find two DEF-USE
   insn1 -> ... -> conditional-branch
   insn1 -> ... -> load_insn,
   and if a flow path exists:
   insn1 -> ... -> conditional-branch -> ... -> load_insn,
   and if insn1 is on the path
   region-entry -> ... -> bb_trg -> ... load_insn.

   Locate insn1 by climbing on INSN_BACK_DEPS from load_insn.
   Locate the branch by following INSN_FORW_DEPS from insn1.  
         Must be a DEF-USE dependence upon non-branch.  
         Must exist a path: region-entry -> ... -> bb_trg -> ... load_insn.  
         Now search for the conditional-branch.  
         Recursive step: search another insn1, "above" current insn1.  
     The chain does not exist.  
static int is_exception_free ( rtx  ,
int  ,
static int is_exception_free ( )
   Insn is a candidate to be moved speculatively from bb_src to bb_trg.
   Return 1 if insn is exception-free (and the motion is valid)
   and 0 otherwise.  
     Handle non-load insns.  
     Handle loads.  
         Don't 'break' here: PFREE-candidate is also PRISKY-candidate.  
static int is_pfree ( rtx  ,
int  ,
static int is_pfree ( )
   Returns 1 if a clue for "similar load" 'insn2' is found, and hence
   load_insn can move speculatively from bb_src to bb_trg.  All the
   following must hold:

   (1) both loads have 1 base register (PFREE_CANDIDATEs).
   (2) load_insn and load1 have a def-use dependence upon
   the same insn 'insn1'.
   (3) either load2 is in bb_trg, or:
   - there's only one split-block, and
   - load1 is on the escape path, and

   From all these we can conclude that the two loads access memory
   addresses that differ at most by a constant, and hence if moving
   load_insn would cause an exception, it would have been caused by
   load2 anyhow.  
       Must have exactly one escape block.  
           Found a DEF-USE dependence (insn1, load_insn).  
                     Found a DEF-USE dependence (insn1, insn2).  
                       insn2 not guaranteed to be a 1 base reg load.  
                       insn2 is the similar load, in the target block.  
                       insn2 is a similar load, in a split-block.  
     Couldn't find a similar load.  
static int is_prisky ( rtx  ,
int  ,
static int is_prisky ( )
   Return 1 if load_insn is prisky (i.e. if load_insn is fed by
   a load moved speculatively, or if load_insn is protected by
   a compare on load_insn's address).  
       Dependence may 'hide' out of the region.  

References check_live(), nr_inter, nr_spec, set_spec_fed(), target_bb, and update_live().

rtl_opt_pass* make_pass_sched ( )
rtl_opt_pass* make_pass_sched2 ( )

Referenced by schedule_insns().

static ds_t new_ready ( rtx  ,
static ds_t new_ready ( )
   Called after INSN has all its hard dependencies resolved and the speculation
   of type TS is enough to overcome them all.
   Return nonzero if it should be moved to the ready list or the queue, or zero
   if we should silently discard it.  
         For speculative insns, before inserting to ready/queue,
         check live, exception-free, and issue-delay.  
                 We are here because is_exception_free () == false.
                 But we possibly can handle that with control speculation.  
                 Add control speculation to NEXT's dependency type.  
                 Check if NEXT can be speculated with new dependency type.  
                   Here we got new control-speculative instruction.  
                   NEXT isn't ready yet.  
               NEXT isn't ready yet.  

References rgn_sched_info, and haifa_sched_info::sched_max_insns_priority.

static void print_region_statistics ( int *  ,
int  ,
int *  ,
static void print_region_statistics ( )
   Print regions statistics.  S1 and S2 denote the data before and after
   calling extend_rgns, respectively.  
     We iterate until s2_sz because extend_rgns does not decrease
     the maximal region size.  
static void propagate_deps ( int  ,
struct deps_desc  
static void propagate_deps ( )
   After computing the dependencies for block BB, propagate the dependencies
   found in TMP_DEPS to the successors of the block.  
     bb's structures are inherited by its successors.  
         Only bbs "below" bb, in the same region, are interesting.  
     These lists should point to the right place, for correct
     freeing later.  
     Can't allow these to be freed twice.  
static void realloc_bb_state_array ( )
   (Re-)initialize the arrays of DFA states at the end of each basic block.

   SAVED_LAST_BASIC_BLOCK is the previous length of the arrays.  It must be
   zero for the first call to this function, to allocate the arrays for the
   first time.

   This function is called once during initialization of the scheduler, and
   called again to resize the arrays if new basic blocks have been created,
   for example for speculation recovery code.  
     Nothing to do if nothing changed since the last time this was called.  
     The selective scheduler doesn't use the state arrays.  
     If BB_STATE_ARRAY has moved, fixup all the state pointers array.
     Otherwise only fixup the newly allocated ones.  For the state
     array itself, only initialize the new entries.  
static unsigned int rest_of_handle_sched ( )
   Run instruction scheduler.  
static unsigned int rest_of_handle_sched2 ( )
   Run second scheduling pass after reload.  
         Do control and data sched analysis again,
         and write some more of the results to dump file.  

Referenced by schedule_insns().

static void rgn_add_block ( basic_block  ,
static void rgn_add_block ( )
   BB was added to ebb after AFTER.  
         We need to fix rgn_table, block_to_bb, containing_rgn
         and ebb_head.  
         We extend ebb_head to one more position to
         easily find the last position of the last ebb in
         the current region.  Thus, ebb_head[BLOCK_TO_BB (after) + 1]
         is _always_ valid for access.  
         Now POS is the index of the last block in the region.  
         Find index of basic block AFTER.  
         i - ebb right after "AFTER".  
         ebb_head[i] - VALID.  
         Source position: ebb_head[i]
         Destination position: ebb_head[i] + 1
         Last position:
           RGN_BLOCKS (nr_regions) - 1
         Number of elements to copy: (last_position) - (source_position) + 1
static void rgn_add_remove_insn ( rtx  ,
   Functions for speculative scheduling.  
static void rgn_add_remove_insn ( )
   INSN has been added to/removed from current region.  
static int rgn_estimate_number_of_insns ( )
   Estimate number of the insns in the BB.  
static void rgn_fix_recovery_cfg ( int  ,
int  ,
static void rgn_fix_recovery_cfg ( )
   Fix internal data after interblock movement of jump instruction.
   For parameter meaning please refer to
   sched-int.h: struct sched_info: fix_recovery_cfg.  
static bool rgn_insn_finishes_block_p ( )
   Return true if scheduling INSN will trigger finish of scheduling
   current block.  
       INSN is the last not-scheduled instruction in the current block.  

References alloc_INSN_LIST().

void rgn_make_new_region_out_of_new_block ( )
     I - first free position in rgn_bb_table.  
static const char* rgn_print_insn ( const_rtx  ,
static const char* rgn_print_insn ( )
   Return a string that contains the insn uid and optionally anything else
   necessary to identify this insn in an output.  It's valid to use a
   static buffer for this.  The ALIGNED parameter should cause the string
   to be formatted so that multiple output lines will line up nicely.  
static int rgn_rank ( rtx  ,
static int rgn_rank ( )
   Compare priority of two insns.  Return a positive number if the second
   insn is to be preferred for scheduling, and a negative one if the first
   is to be preferred.  Zero if they are equally good.  
     Some comparison make sense in interblock scheduling only.  
         Prefer an inblock motion on an interblock motion.  
         Prefer a useful motion on a speculative one.  
         Prefer a more probable (speculative) insn.  
void rgn_setup_common_sched_info ( void  )
   Setup scheduler infos.  

References RTL_PASS.

void rgn_setup_region ( )
   Setup global variables like CURRENT_BLOCKS and CURRENT_NR_BLOCK to
   point to the region RGN.  
     Set variables for the current region.  
     EBB_HEAD is a region-scope structure.  But we realloc it for
     each region to save time/memory/something else.
     See comments in add_block1, for what reasons we allocate +1 element.  

References ebb_head, basic_block_def::index, and rgn_bb_table.

void rgn_setup_sched_infos ( void  )
   Setup all *_sched_info structures (for the Haifa frontend
   and for the dependence analysis) in the interblock scheduler.  

Referenced by code_motion_process_successors().

bool sched_is_disabled_for_current_region_p ( void  )
   Returns true if all the basic blocks of the current region have
   NOTE_DISABLE_SCHED_OF_BLOCK which means not to schedule that region.  
void sched_rgn_compute_dependencies ( )
   Compute instruction dependencies in region RGN.  
         Initializations for region data dependence analysis.  
         Initialize bitmap used in add_branch_dependences.  
         Compute backward dependencies.  
         We don't want to recalculate this twice.  
       (This is a recovery block.  It is always a single block region.)
       OR (We use selective scheduling.)  
void sched_rgn_finish ( void  )
   Free data structures for region scheduling.  
     Reposition the prologue and epilogue notes in case we moved the
     prologue/epilogue insns.  
void sched_rgn_init ( )
   Initialize data structures for region scheduling.  
     Compute regions for scheduling.  
         Compute the dominators and post dominators.  
         Find regions.  
         For now.  This will move as more and more of haifa is converted
         to using the cfg code.  
void sched_rgn_local_finish ( void  )
   Free data computed for the finished region.  
void sched_rgn_local_free ( void  )
   Free data computed for the finished region.  

References maybe_skip_selective_scheduling(), and run_selective_scheduling().

void sched_rgn_local_init ( )
   Init region data structures.  Returns true if this region should
   not be scheduled.  
     Compute interblock info: probabilities, split-edges, dominators, etc.  
         Use ->aux to implement EDGE_TO_BIT mapping.  
         Split edges.  
         Compute probabilities, dominators, split_edges.  
         Cleanup ->aux used for EDGE_TO_BIT mapping.  
         We don't need them anymore.  But we want to avoid duplication of
         aux fields in the newly created edges.  
void schedule_insns ( void  )
   The one entry point in this file.  
     Taking care of this degenerate case makes the rest of
     this code simpler.  
     Schedule every region in the subroutine.  
     Clean up.  

References execute(), gate_handle_sched2(), make_pass_sched2(), rest_of_handle_sched2(), and RTL_PASS.

static int schedule_more_p ( void  )
   Return nonzero if there are more insns that should be scheduled.  
static void schedule_region ( int  )
static void schedule_region ( )
   Schedule a region.  A region is either an inner loop, a loop-free
   subroutine, or a single basic block.  Each bb in the region is
   scheduled after its flow predecessors.  
     Don't schedule region that is marked by
     Set priorities.  
     Now we can schedule all blocks.  
         Clean up.  
     Sanity check: verify that all region insns were scheduled.  
     Done with this region.  
     Free dependencies.  
static void set_spec_fed ( )
   Turns on the fed_by_spec_load flag for insns fed by load_insn.  

References is_conditionally_protected(), and sd_lists_empty_p().

Referenced by is_prisky().

static bool sets_likely_spilled ( rtx  )
static bool sets_likely_spilled ( )
   Determine if PAT sets a TARGET_CLASS_LIKELY_SPILLED_P register.  
static void sets_likely_spilled_1 ( rtx  ,
const_rtx  ,
void *   
static void sets_likely_spilled_1 ( )
static void split_edges ( int  ,
int  ,
   Target info functions.  
static void split_edges ( )
   Functions for target info.  
   Compute in BL the list of split-edges of bb_src relatively to bb_trg.
   Note that bb_trg dominates bb_src.  

References free().

static bool too_large ( int  ,
int *  ,
int *   
static bool too_large ( )
   Update number of blocks and the estimate for number of insns
   in the region.  Return true if the region is "too large" for interblock
   scheduling (compile time considerations).  

References bitmap_clear(), bitmap_ones(), count, sbitmap_alloc(), and stack.

static void update_live ( )
   Update the live registers info after insn was moved speculatively from
   block src to trg.  
     Find the registers set by instruction.  

References bblst::first_member, haifa_classify_insn(), PFREE_CANDIDATE, and candidate::split_bbs.

Referenced by is_prisky().

static void update_live_1 ( int  ,

Referenced by debug_candidate().

static void update_live_1 ( )
   If x is a set of a register R, mark that R is alive in the beginning
   of every update-block of src.  
     Global registers are always live, so the code below does not apply
     to them.  

References find_conditional_protection(), and is_conditionally_protected().

Variable Documentation

edgeset* ancestor_edges
   For every bb, a set of its ancestor edges.  
struct deps_desc* bb_deps
   Data structures for the computation of data dependences in a regions.  We
   keep one `deps' structure for every basic block.  Before analyzing the
   data dependences for a bb, its variables are initialized as a function of
   the variables of its predecessors.  When the analysis for a bb completes,
   we save the contents to the corresponding bb_deps[bb] variable.  
state_t* bb_state = NULL
char* bb_state_array = NULL
   Arrays that hold the DFA state at the end of a basic block, to re-use
   as the initial state at the start of successor blocks.  The BB_STATE
   array holds the actual DFA state, and BB_STATE_ARRAY[I] is a pointer
   into BB_STATE for basic block I.  FIXME: This should be a vec.  
int bblst_last
int bblst_size
basic_block* bblst_table
   A speculative motion requires checking live information on the path
   from 'source' to 'target'.  The split blocks are those to be checked.
   After a speculative motion, live information should be modified in
   the 'update' blocks.

   Lists of split and update blocks for each candidate of the current
   target are in array bblst_table.  
int* block_to_bb = NULL
   Topological order of blocks in the region (if b2 is reachable from
   b1, block_to_bb[b2] > block_to_bb[b1]).  Note: A basic block is
   always referred to by either block or b, while its topological
   order name (in the region) is referred to by bb.  
candidate* candidate_table
int* containing_rgn = NULL
   The number of the region containing a block.  
int current_blocks

Referenced by debug_regions().

int current_nr_blocks
   Blocks of the current region being scheduled.  

Referenced by code_motion_process_successors(), and mark_regno_birth_or_death().

sbitmap* dom
   Dominators array: dom[i] contains the sbitmap of dominators of
   bb i in the region.  

Referenced by determine_dominators_for_sons(), do_partial_partial_insertion(), get_immediate_dominator(), isl_id_for_ssa_name(), and occ_new().

int* ebb_head = NULL
   ebb_head [i] - is index in rgn_bb_table of the head basic block of i'th ebb.
   Currently we can get a ebb only through splitting of currently
   scheduling block, therefore, we don't need ebb_head array for every region,
   hence, its sufficient to hold it for current one only.  

Referenced by rgn_setup_region().

int edgelst_last
edge* edgelst_table
sbitmap insn_referenced
   A bitmap to note insns that participate in any dependency.  Used in
int min_spec_prob
   The minimum probability of reaching a source block so that it will be
   considered for speculative scheduling.  
bitmap_head not_in_df
   Functions for speculative scheduling.  
int nr_inter
   nr_inter/spec counts interblock/speculative motion for the function.  

Referenced by is_prisky().

int nr_regions = 0
   Number of regions in the procedure.  
int nr_spec

Referenced by is_prisky().

edgeset* pot_split
   The split edges of a source bb is different for each target
   bb.  In order to compute this efficiently, the 'potential-split edges'
   are computed for each bb prior to scheduling a region.  This is actually
   the split edges of each bb relative to the region entry.

   pot_split[bb] is the set of potential split edges of bb.  
int* prob
   Probability: Prob[i] is an int in [0, REG_BR_PROB_BASE] which is
   the probability of bb i relative to the region entry.  

Referenced by create_empty_if_region_on_edge(), estimate_ipcp_clone_size_and_time(), find_traces_1_round(), fixup_new_cold_bb(), scale_dominated_blocks_in_loop(), and vect_create_cond_for_alias_checks().

int* rgn_bb_table = NULL
   Array of lists of regions' blocks.  

Referenced by debug_regions(), and rgn_setup_region().

struct common_sched_info_def rgn_common_sched_info
   This variable holds common_sched_info hooks and data relevant to
   the interblock scheduler.  
struct sched_deps_info_def rgn_const_sched_deps_info
Initial value:
0, 0, 0
   This holds constant data used for initializing the above structure
   for the Haifa scheduler.  
struct haifa_sched_info rgn_const_sched_info
Initial value:
   Used in schedule_insns to initialize current_sched_info for scheduling
   regions (or single basic blocks).  
struct sched_deps_info_def rgn_const_sel_sched_deps_info
Initial value:
0, 0, 0
   Same as above, but for the selective scheduler.  
edge* rgn_edges
   Array of size rgn_nr_edges.  
int rgn_n_insns
int rgn_nr_edges
   Number of edges in the region.  
struct sched_deps_info_def rgn_sched_deps_info
   This holds data for the dependence analysis relevant to
   the interblock scheduler.  
struct haifa_sched_info rgn_sched_info
   This variable holds the data and hooks needed to the Haifa scheduler backend
   for the interblock scheduler frontend.  

Referenced by new_ready().

region* rgn_table = NULL
   Table of region descriptions.  
int sched_n_insns
   The number of insns from the entire region scheduled so far.  
int sched_target_n_insns
   The number of insns from the current block scheduled so far.  
int target_bb
   The bb being currently scheduled.  

Referenced by init_ready_list(), and is_prisky().

int target_n_insns
   The number of insns from the current block to be scheduled in total.