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

Data Structures

struct  ps_insn
struct  ps_reg_move_info
struct  partial_schedule
struct  node_sched_params
struct  node_order_params


typedef struct partial_schedulepartial_schedule_ptr
typedef struct ps_insnps_insn_ptr
typedef struct ps_reg_move_info ps_reg_move_info
typedef struct node_sched_paramsnode_sched_params_ptr
typedef struct node_sched_params node_sched_params
typedef struct node_order_paramsnopa


enum  sms_direction { BOTTOMUP, TOPDOWN }


static partial_schedule_ptr create_partial_schedule (int ii, ddg_ptr, int history)
static void free_partial_schedule (partial_schedule_ptr)
static void reset_partial_schedule (partial_schedule_ptr, int new_ii)
void print_partial_schedule (partial_schedule_ptr, FILE *)
static void verify_partial_schedule (partial_schedule_ptr, sbitmap)
static ps_insn_ptr ps_add_node_check_conflicts (partial_schedule_ptr, int, int, sbitmap, sbitmap)
static void rotate_partial_schedule (partial_schedule_ptr, int)
void set_row_column_for_ps (partial_schedule_ptr)
static void ps_insert_empty_row (partial_schedule_ptr, int, sbitmap)
static int compute_split_row (sbitmap, int, int, int, ddg_node_ptr)
static int sms_order_nodes (ddg_ptr, int, int *, int *)
static void set_node_sched_params (ddg_ptr)
static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int, int *)
static void permute_partial_schedule (partial_schedule_ptr, rtx)
static void generate_prolog_epilog (partial_schedule_ptr, struct loop *, rtx, rtx)
static int calculate_stage_count (partial_schedule_ptr, int)
static void calculate_must_precede_follow (ddg_node_ptr, int, int, int, int, sbitmap, sbitmap, sbitmap)
static int get_sched_window (partial_schedule_ptr, ddg_node_ptr, sbitmap, int, int *, int *, int *)
static bool try_scheduling_node_in_cycle (partial_schedule_ptr, int, int, sbitmap, int *, sbitmap, sbitmap)
static void remove_node_from_ps (partial_schedule_ptr, ps_insn_ptr)
static const char * sms_print_insn ()
static void compute_jump_reg_dependencies (rtx insn, regset used)
static struct ps_reg_move_infops_reg_move ()
static rtx ps_rtl_insn ()
static rtx ps_first_note ()
static int ps_num_consecutive_stages ()
static rtx doloop_register_get ()
static rtx const_iteration_count (rtx count_reg, basic_block pre_header, HOST_WIDEST_INT *count)
static int res_MII ()
static void set_node_sched_params ()
static void extend_node_sched_params ()
static void update_node_sched_params ()
static void print_node_sched_params ()
static void set_columns_for_row ()
static void set_columns_for_ps ()
static bool schedule_reg_move (partial_schedule_ptr ps, int i_reg_move, sbitmap distance1_uses, sbitmap must_follow)
static bool schedule_reg_moves ()
static void apply_reg_moves ()
static void reset_sched_times ()
static void permute_partial_schedule ()
static void set_must_precede_follow (sbitmap *tmp_follow, sbitmap must_follow, sbitmap *tmp_precede, sbitmap must_precede, int c, int start, int end, int step)
static bool optimize_sc ()
static void duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage, int to_stage, rtx count_reg)
static void mark_loop_unsched ()
static bool loop_single_full_bb_p ()
static void dump_insn_location ()
static bool loop_canon_p ()
static void canon_loop ()
static void setup_sched_infos ()
static void sms_schedule ()
static partial_schedule_ptr sms_schedule_by_order ()
static void verify_partial_schedule ()
static void order_nodes_of_sccs (ddg_all_sccs_ptr, int *result)
static int order_nodes_in_scc (ddg_ptr, sbitmap, sbitmap, int *, int)
static nopa calculate_order_params (ddg_ptr, int, int *)
static int find_max_asap (ddg_ptr, sbitmap)
static int find_max_hv_min_mob (ddg_ptr, sbitmap)
static int find_max_dv_min_mob (ddg_ptr, sbitmap)
static void check_nodes_order ()
static int sms_order_nodes ()
static void order_nodes_of_sccs ()
static struct node_order_paramscalculate_order_params ()
static int find_max_asap ()
static int find_max_hv_min_mob ()
static int find_max_dv_min_mob ()
static partial_schedule_ptr create_partial_schedule ()
static void free_ps_insns ()
static void free_partial_schedule ()
static void reset_partial_schedule ()
void print_partial_schedule ()
static ps_insn_ptr create_ps_insn ()
static void remove_node_from_ps ()
static bool ps_insn_find_column (partial_schedule_ptr ps, ps_insn_ptr ps_i, sbitmap must_precede, sbitmap must_follow)
static int ps_insn_advance_column (partial_schedule_ptr ps, ps_insn_ptr ps_i, sbitmap must_follow)
static ps_insn_ptr add_node_to_ps (partial_schedule_ptr ps, int id, int cycle, sbitmap must_precede, sbitmap must_follow)
static void advance_one_cycle ()
static int ps_has_conflicts ()
int calculate_stage_count ()
void rotate_partial_schedule ()
static bool gate_handle_sms ()
static unsigned int rest_of_handle_sms ()
rtl_opt_passmake_pass_sms ()


static struct common_sched_info_def sms_common_sched_info
static struct sched_deps_info_def sms_sched_deps_info
static struct haifa_sched_info sms_sched_info
static vec< node_sched_paramsnode_sched_param_vec

Typedef Documentation

   The scheduling parameters held for each node.  
typedef struct node_order_params* nopa

Swing Modulo Scheduling implementation. Copyright (C) 2004-2013 Free Software Foundation, Inc. Contributed by Ayal Zaks and Mustafa Hagog <zaks,musta.nosp@m.fa@i.nosp@m.l.ibm.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/.

   This file contains the implementation of the Swing Modulo Scheduler,
   described in the following references:
   [1] J. Llosa, A. Gonzalez, E. Ayguade, M. Valero., and J. Eckhardt.
       Lifetime--sensitive modulo scheduling in a production environment.
       IEEE Trans. on Comps., 50(3), March 2001
   [2] J. Llosa, A. Gonzalez, E. Ayguade, and M. Valero.
       Swing Modulo Scheduling: A Lifetime Sensitive Approach.
       PACT '96 , pages 80-87, October 1996 (Boston - Massachusetts - USA).

   The basic structure is:
   1. Build a data-dependence graph (DDG) for each loop.
   2. Use the DDG to order the insns of a loop (not in topological order
      necessarily, but rather) trying to place each insn after all its
      predecessors _or_ after all its successors.
   3. Compute MII: a lower bound on the number of cycles to schedule the loop.
   4. Use the ordering to perform list-scheduling of the loop:
      1. Set II = MII.  We will try to schedule the loop within II cycles.
      2. Try to schedule the insns one by one according to the ordering.
         For each insn compute an interval of cycles by considering already-
         scheduled preds and succs (and associated latencies); try to place
         the insn in the cycles of this window checking for potential
         resource conflicts (using the DFA interface).
         Note: this is different from the cycle-scheduling of schedule_insns;
         here the insns are not scheduled monotonically top-down (nor bottom-
      3. If failed in scheduling all insns - bump II++ and try again, unless
         II reaches an upper bound MaxII, in which case report failure.
   5. If we succeeded in scheduling the loop within II cycles, we now
      generate prolog and epilog, decrease the counter of the loop, and
      perform modulo variable expansion for live ranges that span more than
      II cycles (i.e. use register copies to prevent a def from overwriting
      itself before reaching the use).

    SMS works with countable loops (1) whose control part can be easily
    decoupled from the rest of the loop and (2) whose loop count can
    be easily adjusted.  This is because we peel a constant number of
    iterations into a prologue and epilogue for which we want to avoid
    emitting the control part, and a kernel which is to iterate that
    constant number of iterations less than the original loop.  So the
    control part should be a set of insns clearly identified and having
    its own iv, not otherwise used in the loop (at-least for now), which
    initializes a register before the loop to the number of iterations.
    Currently SMS relies on the do-loop pattern to recognize such loops,
    where (1) the control part comprises of all insns defining and/or
    using a certain 'count' register and (2) the loop count can be
    adjusted by modifying this register prior to the loop.
    TODO: Rely on cfgloop analysis instead.  
   This page defines partial-schedule structures and functions for
   modulo scheduling.  
typedef struct ps_insn* ps_insn_ptr

Enumeration Type Documentation


Function Documentation

static ps_insn_ptr add_node_to_ps ( partial_schedule_ptr  ps,
int  id,
int  cycle,
sbitmap  must_precede,
sbitmap  must_follow 
   Inserts a DDG_NODE to the given partial schedule at the given cycle.
   Returns 0 if this is not possible and a PS_INSN otherwise.  Bit N is
   set in MUST_PRECEDE/MUST_FOLLOW if the node with cuid N must be come
   before/after (respectively) the node pointed to by PS_I when scheduled
   in the same cycle.  
     Finds and inserts PS_I according to MUST_FOLLOW and

References partial_schedule::rows, and partial_schedule::rows_length.

static void advance_one_cycle ( )
   Advance time one cycle.  Assumes DFA is being used.  
static void apply_reg_moves ( )
   Emit the moves associatied with PS.  Apply the substitutions
   associated with them.  

References add_insn_before(), partial_schedule::g, ps_insn::id, partial_schedule::ii, ps_insn::next_in_row, ddg::num_nodes, ps_first_note(), ps_rtl_insn(), reorder_insns_nobb(), and partial_schedule::rows.

static void calculate_must_precede_follow ( ddg_node_ptr  u_node,
int  start,
int  end,
int  step,
int  ii,
sbitmap  sched_nodes,
sbitmap  must_precede,
sbitmap  must_follow 
   Calculate MUST_PRECEDE/MUST_FOLLOW bitmaps of U_NODE; which is the
   node currently been scheduled.  At the end of the calculation
   MUST_PRECEDE/MUST_FOLLOW contains all predecessors/successors of
   U_NODE which are (1) already scheduled in the first/last row of
   U_NODE's scheduling window, (2) whose dependence inequality with U
   becomes an equality when U is scheduled in this same row, and (3)
   whose dependence latency is zero.

   The first and last rows are calculated using the following parameters:
   START/END rows - The cycles that begins/ends the traversal on the window;
   searching for an empty cycle to schedule U_NODE.
   STEP - The direction in which we traverse the window.
   II - The initiation interval.  
     Consider the following scheduling window:
     {first_cycle_in_window, first_cycle_in_window+1, ...,
     last_cycle_in_window}.  If step is 1 then the following will be
     the order we traverse the window: {start=first_cycle_in_window,
     first_cycle_in_window+1, ..., end=last_cycle_in_window+1},
     or {start=last_cycle_in_window, last_cycle_in_window-1, ...,
     end=first_cycle_in_window-1} if step is -1.  
     Instead of checking if:
      (SMODULO (SCHED_TIME (e->src), ii) == first_row_in_window)
      && ((SCHED_TIME (e->src) + e->latency - (e->distance * ii)) ==
      && e->latency == 0
     we use the fact that latency is non-negative:
      SCHED_TIME (e->src) - (e->distance * ii) <=
      SCHED_TIME (e->src) + e->latency - (e->distance * ii)) <=
     and check only if
      SCHED_TIME (e->src) - (e->distance * ii) == first_cycle_in_window  
     Instead of checking if:
      (SMODULO (SCHED_TIME (e->dest), ii) == last_row_in_window)
      && ((SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) ==
      && e->latency == 0
     we use the fact that latency is non-negative:
      SCHED_TIME (e->dest) + (e->distance * ii) >=
      SCHED_TIME (e->dest) - e->latency + (e->distance * ii)) >=
     and check only if
      SCHED_TIME (e->dest) + (e->distance * ii) == last_cycle_in_window  
static nopa calculate_order_params ( ddg_ptr  ,
int  ,
int *   
static struct node_order_params* calculate_order_params ( )
   MII is needed if we consider backarcs (that do not close recursive cycles).  
     Allocate a place to hold ordering params for each node in the DDG.  
     Initialize of ASAP/ALAP/HEIGHT to zero.  
     Set the aux pointer of each node to point to its order_params structure.  
     Disregarding a backarc from each recursive cycle to obtain a DAG,
     calculate ASAP, ALAP, mobility, distance, and height for each node
     in the dependence (direct acyclic) graph.  
     We assume that the nodes in the array are in topological order.  

References bitmap_and(), bitmap_and_compl(), bitmap_clear(), bitmap_clear_bit(), bitmap_copy(), bitmap_equal_p(), bitmap_ior(), bitmap_set_bit(), BOTTOMUP, find_max_asap(), find_max_hv_min_mob(), find_predecessors(), find_successors(), ddg::nodes, ddg::num_nodes, sbitmap_alloc(), and TOPDOWN.

static int calculate_stage_count ( partial_schedule_ptr  ,
int calculate_stage_count ( )
   Calculate the stage count of the partial schedule PS.  The calculation
   takes into account the rotation amount passed in ROTATION_AMOUNT.  
     The calculation of stage count is done adding the number of stages
     before cycle zero and after cycle zero.  
static void canon_loop ( )
   If there are more than one entry for the loop,
   make it one by splitting the first entry edge and
   redirecting the others to the new BB.  
     Avoid annoying special cases of edges going to exit
static void check_nodes_order ( )
   Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1.  
static void compute_jump_reg_dependencies ( rtx  insn,
regset  used 
static int compute_split_row ( sbitmap  sched_nodes,
int  low,
int  up,
int  ii,
ddg_node_ptr  u_node 
   Given U_NODE which is the node that failed to be scheduled; LOW and
   UP which are the boundaries of it's scheduling window; compute using
   SCHED_NODES and II a row in the partial schedule that can be split
   which will separate a critical predecessor from a critical successor
   thereby expanding the window, and return it.  
static rtx const_iteration_count ( rtx  count_reg,
basic_block  pre_header,
   Check if COUNT_REG is set to a constant in the PRE_HEADER block, so
   that the number of iterations is a compile-time constant.  If so,
   return the rtx that sets COUNT_REG to a constant, and set COUNT to
   this constant.  Otherwise return 0.  

References targetm.

static partial_schedule_ptr create_partial_schedule ( int  ii,
ddg_ptr  ,
int  history 
static partial_schedule_ptr create_partial_schedule ( )
   This page contains functions for manipulating partial-schedules during
   modulo scheduling.  
   Create a partial schedule and allocate a memory to hold II rows.  
static ps_insn_ptr create_ps_insn ( )
   Creates an object of PS_INSN and initializes it to the given parameters.  

Referenced by remove_node_from_ps().

static rtx doloop_register_get ( )
   Given HEAD and TAIL which are the first and last insns in a loop;
   return the register which controls the loop.  Return zero if it has
   more than one occurrence in the loop besides the control part or the
   do-loop pattern is not of the form we expect.  
     TODO: Free SMS's dependence on doloop_condition_get.  
     Check that the COUNT_REG has no other occurrences in the loop
     until the decrement.  We assume the control part consists of
     either a single (parallel) branch-on-count or a (non-parallel)
     branch immediately preceded by a single (decrement) insn.  

References dump_file, and print_rtl_single().

static void dump_insn_location ( )
static void duplicate_insns_of_cycles ( partial_schedule_ptr  ps,
int  from_stage,
int  to_stage,
rtx  count_reg 
           Do not duplicate any insn which refers to count_reg as it
           belongs to the control part.
           The closing branch is scheduled as well and thus should
           be ignored.
           TODO: This should be done by analyzing the control part of
           the loop.  
static void extend_node_sched_params ( )
   Make sure that node_sched_param_vec has an entry for every move in PS.  

References partial_schedule::g, ddg::nodes, ps_rtl_insn(), node_sched_params::stage, and node_sched_params::time.

static int find_max_asap ( ddg_ptr  ,

Referenced by calculate_order_params().

static int find_max_asap ( )
static int find_max_dv_min_mob ( ddg_ptr  ,
static int find_max_dv_min_mob ( )
static int find_max_hv_min_mob ( ddg_ptr  ,

Referenced by calculate_order_params().

static int find_max_hv_min_mob ( )
static void free_partial_schedule ( partial_schedule_ptr  )
static void free_partial_schedule ( )
   Free all the memory allocated to the partial schedule.  

References ps_insn::next_in_row, ps_insn::prev_in_row, and partial_schedule::rows.

static void free_ps_insns ( )
   Free the PS_INSNs in rows array of the given partial schedule.
   ??? Consider caching the PS_INSN's.  

Referenced by order_nodes_in_scc().

static bool gate_handle_sms ( )

Referenced by ps_has_conflicts().

static void generate_prolog_epilog ( partial_schedule_ptr  ps,
struct loop loop,
rtx  count_reg,
rtx  count_init 
   Generate the instructions (including reg_moves) for prolog & epilog.  
     Generate the prolog, inserting its insns on the loop-entry edge.  
         Generate instructions at the beginning of the prolog to
         adjust the loop count by STAGE_COUNT.  If loop count is constant
         (count_init), this constant is adjusted by STAGE_COUNT in
         generate_prolog_epilog function.  
     Put the prolog on the entry edge.  
     Generate the epilog, inserting its insns on the loop-exit edge.  
     Put the epilogue on the exit edge.  

References free(), get_ebb_head_tail(), get_loop_body(), loop::header, and loop::num_nodes.

static int get_sched_window ( partial_schedule_ptr  ps,
ddg_node_ptr  u_node,
sbitmap  sched_nodes,
int  ii,
int *  start_p,
int *  step_p,
int *  end_p 
   Given the partial schedule PS, this function calculates and returns the
   cycles in which we can schedule the node with the given index I.
   NOTE: Here we do the backtracking in SMS, in some special cases. We have
   noticed that there are several cases in which we fail    to SMS the loop
   because the sched window of a node is empty    due to tight data-deps. In
   such cases we want to unschedule    some of the predecessors/successors
   until we get non-empty    scheduling window.  It returns -1 if the
   scheduling window is empty and zero otherwise.  
     1. compute sched window for u (start, end, step).  
     We first compute a forward range (start <= end), then decide whether
     to reverse it.  
     Calculate early_start and limit end.  Both bounds are inclusive.  
     Calculate late_start and limit start.  Both bounds are inclusive.  
     Get a target scheduling window no bigger than ii.  
     Apply memory dependence limits.  
     If there are at least as many successors as predecessors, schedule the
     node close to its successors.  
     Now that we've finalized the window, make END an exclusive rather
     than an inclusive bound.  
static bool loop_canon_p ( )
   Return true if the loop is in its canonical form and false if not.
   i.e. SIMPLE_SMS_LOOP_P and have one preheader block, and single exit.  

References cfun, g, haifa_sched_init(), ps_reg_move_info::insn, issue_rate, loop_optimizer_finalize(), loop_optimizer_init(), LOOPS_HAVE_PREHEADERS, LOOPS_HAVE_RECORDED_EXITS, number_of_loops(), reload_completed, setup_sched_infos(), and targetm.

static bool loop_single_full_bb_p ( )
   Return true if all the BBs of the loop are empty except the
   loop header.  
         Make sure that basic blocks other than the header
         have only notes labels or jumps.  
rtl_opt_pass* make_pass_sms ( )

Referenced by ps_has_conflicts().

static void mark_loop_unsched ( )
   Mark LOOP as software pipelined so the later
   scheduling passes don't touch it.  
static bool optimize_sc ( )
   Return True if the branch can be moved to row ii-1 while
   normalizing the partial schedule PS to start from cycle zero and thus
   optimize the SC.  Otherwise return False.  
     Compare the SC after normalization and SC after bringing the branch
     to row ii-1.  If they are equal just bail out.  
     First, normalize the partial scheduling.  
     Calculate the new placement of the branch.  It should be in row
     ii-1 and fall into it's scheduling window.  
         Try to schedule the branch is it's new cycle.  
         Find the element in the partial schedule related to the closing
         branch so we can remove it from it's current cycle.  
             The branch was failed to be placed in row ii - 1.
             Put it back in it's original place in the partial
             The branch is placed in row ii - 1.  
static int order_nodes_in_scc ( ddg_ptr  g,
sbitmap  nodes_ordered,
sbitmap  scc,
int *  node_order,
int  pos 
   Places the nodes of SCC into the NODE_ORDER array starting
   at position POS, according to the SMS ordering algorithm.
   NODES_ORDERED (in&out parameter) holds the bitset of all nodes in
   the NODE_ORDER array, starting from position zero.  
                 Don't consider the already ordered successors again.  
                 Don't consider the already ordered predecessors again.  

References free_ps_insns(), and memset().

Referenced by verify_partial_schedule().

static void order_nodes_of_sccs ( ddg_all_sccs_ptr  ,
int *  result 
static void order_nodes_of_sccs ( )
     Perform the node ordering starting from the SCC with the highest recMII.
     For each SCC order the nodes according to their ASAP/ALAP/HEIGHT etc.  
         Add nodes on paths from previous SCCs to the current SCC.  
         Add nodes on paths from the current SCC to previous SCCs.  
         Remove nodes of previous SCCs from current extended SCC.  
         Above call to order_nodes_in_scc updated prev_sccs |= tmp.  
     Handle the remaining nodes that do not belong to any scc.  Each call
     to order_nodes_in_scc handles a single connected component.  

References ddg::nodes.

static void permute_partial_schedule ( partial_schedule_ptr  ,
static void permute_partial_schedule ( )
   Permute the insns according to their order in PS, from row 0 to
   row ii-1, and position them right before LAST.  This schedules
   the insns of the loop kernel.  
static void print_node_sched_params ( )
void print_partial_schedule ( partial_schedule_ptr  ,
FILE *   
void print_partial_schedule ( )
   Prints the partial schedule as an ii rows array, for each rows
   print the ids of the insns in it.  

References bitmap_bit_p(), ps_insn::cycle, ps_insn::id, partial_schedule::ii, ps_insn::next_in_row, ps_insn::prev_in_row, and partial_schedule::rows.

ps_insn_ptr ps_add_node_check_conflicts ( partial_schedule_ptr  ps,
int  n,
int  c,
sbitmap  must_precede,
sbitmap  must_follow 
   Checks if the given node causes resource conflicts when added to PS at
   cycle C.  If not the node is added to PS and returned; otherwise zero
   is returned.  Bit N is set in MUST_PRECEDE/MUST_FOLLOW if the node with
   cuid N must be come before/after (respectively) the node pointed to by
   PS_I when scheduled in the same cycle.  
     First add the node to the PS, if this succeeds check for
     conflicts, trying different issue slots in the same row.  
     Try different issue slots to find one that the given node can be
     scheduled in without conflicts.  
static rtx ps_first_note ( )
   Partial schedule instruction ID, which belongs to PS, occurred in
   the original (unscheduled) loop.  Return the first instruction
   in the loop that was associated with ps_rtl_insn (PS, ID).
   If the instruction had some notes before it, this is the first
   of those notes.  

Referenced by apply_reg_moves().

static int ps_has_conflicts ( )
   Checks if PS has resource conflicts according to DFA, starting from
   FROM cycle to TO cycle; returns true if there are conflicts and false
   if there are no conflicts.  Assumes DFA is being used.  
         Holds the remaining issue slots in the current row.  
         Walk through the DFA for the current row.  
             Check if there is room for the current insn.  
             Update the DFA state and return with failure if the DFA found
             resource conflicts.  
             A naked CLOBBER or USE generates no instruction, so don't
             let them consume issue slots.  
         Advance the DFA to the next cycle.  

References execute(), gate_handle_sms(), make_pass_sms(), rest_of_handle_sms(), and RTL_PASS.

static void ps_insert_empty_row ( partial_schedule_ptr  ps,
int  split_row,
sbitmap  sched_nodes 
   This function inserts a new empty row into PS at the position
   according to SPLITROW, keeping all already scheduled instructions
   intact and updating their SCHED_TIME and cycle accordingly.  
     We normalize sched_time and rotate ps to have only non-negative sched
     times, for simplicity of updating cycles after inserting new row.  
     Updating ps.  
static int ps_insn_advance_column ( partial_schedule_ptr  ps,
ps_insn_ptr  ps_i,
sbitmap  must_follow 
   Advances the PS_INSN one column in its current row; returns false
   in failure and true in success.  Bit N is set in MUST_FOLLOW if
   the node with cuid N must be come after the node pointed to by
   PS_I when scheduled in the same cycle.  
     Check if next_in_row is dependent on ps_i, both having same sched
     times (typically ANTI_DEP).  If so, ps_i cannot skip over it.  
     Advance PS_I over its next_in_row in the doubly linked list.  
static bool ps_insn_find_column ( partial_schedule_ptr  ps,
ps_insn_ptr  ps_i,
sbitmap  must_precede,
sbitmap  must_follow 
   Unlike what literature describes for modulo scheduling (which focuses
   on VLIW machines) the order of the instructions inside a cycle is
   important.  Given the bitmaps MUST_FOLLOW and MUST_PRECEDE we know
   where the current instruction should go relative to the already
   scheduled instructions in the given cycle.  Go over these
   instructions and find the first possible column to put it in.  
     Find the first must follow and the last must precede
     and insert the node immediately after the must precede
     but make sure that it there is no must follow after it.  
             If we have already met a node that must follow, then
             there is no possible column.  
         The closing branch must be the last in the row.  
     The closing branch is scheduled as well.  Make sure there is no
     dependent instruction after it as the branch should be the last
     instruction in the row.  
             Make the branch the last in the row.  New instructions
             will be inserted at the beginning of the row or after the
             last must_precede instruction thus the branch is guaranteed
             to remain the last instruction in the row.  
     Now insert the node after INSERT_AFTER_PSI.  

References targetm.

Referenced by remove_node_from_ps().

static int ps_num_consecutive_stages ( )
   Return the number of consecutive stages that are occupied by
   partial schedule instruction ID in PS.  
static struct ps_reg_move_info* ps_reg_move ( )
   Partial schedule instruction ID in PS is a register move.  Return
   information about it.  

References g, and ps_reg_move_info::num_consecutive_stages.

static rtx ps_rtl_insn ( )
   Return the rtl instruction that is being scheduled by partial schedule
   instruction ID, which belongs to schedule PS.  

Referenced by apply_reg_moves(), and extend_node_sched_params().

static void remove_node_from_ps ( partial_schedule_ptr  ,
static void remove_node_from_ps ( )
   Removes the given PS_INSN from the partial schedule.  

References create_ps_insn(), free(), partial_schedule::ii, issue_rate, ps_insn_find_column(), and partial_schedule::rows_length.

static int res_MII ( )
   A very simple resource-based lower bound on the initiation interval.
   ??? Improve the accuracy of this bound by considering the
   utilization of various units.  
static void reset_partial_schedule ( partial_schedule_ptr  ,
int  new_ii 
static void reset_partial_schedule ( )
   Clear the rows array with its PS_INSNs, and create a new one with
   NEW_II rows.  
static void reset_sched_times ( )
   Bump the SCHED_TIMEs of all nodes by AMOUNT.  Set the values of
   SCHED_ROW and SCHED_STAGE.  Instruction scheduled on cycle AMOUNT
   will move to cycle zero.  
               Print the scheduling times after the rotation.  

Referenced by sms_schedule_by_order().

static unsigned int rest_of_handle_sms ( )
   Run instruction scheduler.  
   Perform SMS module scheduling.  
     Collect loop information to be used in SMS.  
     Update the life information, because we add pseudos.  
     Finalize layout changes.  

Referenced by ps_has_conflicts().

static void rotate_partial_schedule ( partial_schedule_ptr  ,

Referenced by sms_schedule_by_order().

void rotate_partial_schedule ( )
   Rotate the rows of PS such that insns scheduled at time
   START_CYCLE will appear in row 0.  Updates max/min_cycles.  
     Revisit later and optimize this into a single loop.  
static bool schedule_reg_move ( partial_schedule_ptr  ps,
int  i_reg_move,
sbitmap  distance1_uses,
sbitmap  must_follow 
   Try to schedule the move with ps_insn identifier I_REG_MOVE in PS.
   Its single predecessor has already been scheduled, as has its
   ddg node successors.  (The move may have also another move as its
   successor, in which case that successor will be scheduled later.)

   The move is part of a chain that satisfies register dependencies
   between a producing ddg node and various consuming ddg nodes.
   If some of these dependencies have a distance of 1 (meaning that
   the use is upward-exposed) then DISTANCE1_USES is nonnull and
   contains the set of uses with distance-1 dependencies.
   DISTANCE1_USES is null otherwise.

   MUST_FOLLOW is a scratch bitmap that is big enough to hold
   all current ps_insn ids.

   Return true on success.  
     For dependencies of distance 1 between a producer ddg node A
     and consumer ddg node B, we have a chain of dependencies:

        A --(T,L1,1)--> M1 --(T,L2,0)--> M2 ... --(T,Ln,0)--> B

     where Mi is the ith move.  For dependencies of distance 0 between
     a producer ddg node A and consumer ddg node C, we have a chain of

        A --(T,L1',0)--> M1' --(T,L2',0)--> M2' ... --(T,Ln',0)--> C

     where Mi' occupies the same position as Mi but occurs a stage later.
     We can only schedule each move once, so if we have both types of
     chain, we model the second as:

        A --(T,L1',1)--> M1 --(T,L2',0)--> M2 ... --(T,Ln',-1)--> C

     First handle the dependencies between the previously-scheduled
     predecessor and the move.  
     Handle the dependencies between the move and previously-scheduled
static bool schedule_reg_moves ( )
         Skip instructions that do not set a register.  
         Compute the number of reg_moves needed for u, by looking at life
         ranges started at u (excluding self-loops).  
               If dest precedes src in the schedule of the kernel, then dest
               will read before src writes and we can save one reg_copy.  
                   !single_set instructions are not supported yet and
                   thus we do not except to encounter them in the loop
                   except from the doloop part.  For the latter case
                   we assume no regmoves are generated as the doloop
                   instructions are tied to the branch with an edge.  
                   If the instruction contains auto-inc register then
                   validate that the regmov is being generated for the
                   target regsiter rather then the inc'ed register.     
         Create NREG_MOVES register moves.  
         Record the moves associated with this node.  
         Generate each move.  
         Every use of the register defined by node may require a different
         copy of this register, depending on the time the use is scheduled.
         Record which uses require which move results.  
static void set_columns_for_ps ( )
   Set SCHED_COLUMN for each instruction in PS.  
static void set_columns_for_row ( )
   Set SCHED_COLUMN for each instruction in row ROW of PS.  
static void set_must_precede_follow ( sbitmap tmp_follow,
sbitmap  must_follow,
sbitmap tmp_precede,
sbitmap  must_precede,
int  c,
int  start,
int  end,
int  step 
   respectively only if cycle C falls on the border of the scheduling
   window boundaries marked by START and END cycles.  STEP is the
   direction of the window.  
static void set_node_sched_params ( ddg_ptr  )
static void set_node_sched_params ( )
   Allocate sched_params for each node and initialize it.  
void set_row_column_for_ps ( partial_schedule_ptr  )
static void setup_sched_infos ( )
   Setup infos.  

References dump_file, dump_insn_location(), loop::header, and loop::num.

Referenced by loop_canon_p().

static int sms_order_nodes ( ddg_ptr  ,
int  ,
int *  ,
int *   
   This page defines constants and structures for the modulo scheduling
static int sms_order_nodes ( )
   Order the nodes of G for scheduling and pass the result in
   NODE_ORDER.  Also set aux.count of each node to ASAP.
   Put maximal ASAP to PMAX_ASAP.  Return the recMII for the given DDG.  
       First SCC has the largest recurrence_length.  
     Save ASAP before destroying node_order_params.  
static const char* sms_print_insn ( )
   The following three functions are copied from the current scheduler
   code in order to use sched_analyze() for computing the dependencies.
   They are used when initializing the sched_info structure.  
static void sms_schedule ( )
   Main entry point, perform SMS scheduling on the loops of the function
   that consist of single basic blocks.  
     Initialize issue_rate.  
     Initialize the scheduler.  
     Allocate memory to hold the DDG array one entry for each loop.
     We use loop->num as index into this array.  
     Build DDGs for all the relevant loops and hold them in G_ARR
     indexed by the loop index.  
         For debugging.  
         Perform SMS only on loops that their average count is above threshold.  
         Make sure this is a doloop.  
         Don't handle BBs with calls or barriers
         or !single_set with the exception of instructions that include
         count_reg---these instructions are part of the control part
         that do-loop recognizes.
         ??? Should handle insns defining subregs.  
         Always schedule the closing branch with the rest of the
         instructions. The branch is rotated to be in row ii-1 at the
         end of the scheduling procedure to make sure it's the last
         instruction in the iteration.  
     We don't want to perform SMS on new loops - created by versioning.  
         In case of th loop have doloop register it gets special
                 Try to achieve optimized SC by normalizing the partial
                 schedule (having the cycles start from cycle zero).
                 The branch location must be placed in row ii-1 in the
                 final scheduling.      If failed, shift all instructions to
                 position the branch in row ii-1.  
                     Bring the branch to cycle ii-1.  
             The default value of PARAM_SMS_MIN_SC is 2 as stage count of
             1 means that there is no interleaving between iterations thus
             we let the scheduling passes do the job in this case.  
                 Rotate the partial schedule to have the branch in row ii-1.  
             Moves that handle incoming values might have been added
             to a new first stage.  Bump the stage count if so.

             ??? Perhaps we could consider rotating the schedule here
             The stage count should now be correct without rotation.  
             case the BCT count is not known , Do loop-versioning 
             Set new iteration count of loop kernel.  
             Now apply the scheduled kernel to the RTL of the loop.  
             Mark this loop as software pipelined so the later
             scheduling passes don't touch it.  
             The life-info is not valid any more.  
             Generate prolog and epilog.  
     Release scheduler data, needed until now because of DFA.  
static partial_schedule_ptr sms_schedule_by_order ( ddg_ptr  ,
int  ,
int  ,
int *   
static partial_schedule_ptr sms_schedule_by_order ( )
   This function implements the scheduling algorithm for SMS according to the
   above algorithm.  
             Try to get non-empty scheduling window.  
                 The scheduling window is exclusive of 'end'
                 whereas compute_split_window() expects an inclusive,
                 ordered range.  
             ??? If (success), check register pressure estimates.  

References ps_insn::cycle, dump_file, free(), ps_insn::id, partial_schedule::ii, partial_schedule::max_cycle, partial_schedule::min_cycle, ps_insn::next_in_row, reset_sched_times(), rotate_partial_schedule(), partial_schedule::rows, partial_schedule::rows_length, and verify_partial_schedule().

static bool try_scheduling_node_in_cycle ( partial_schedule_ptr  ps,
int  u,
int  cycle,
sbitmap  sched_nodes,
int *  num_splits,
sbitmap  must_precede,
sbitmap  must_follow 
   Return 1 if U_NODE can be scheduled in CYCLE.  Use the following
   parameters to decide if that's possible:
   PS - The partial schedule.
   U - The serial number of U_NODE.
   NUM_SPLITS - The number of row splits made so far.
   MUST_PRECEDE - The nodes that must precede U_NODE. (only valid at
   the first row of the scheduling window)
   MUST_FOLLOW - The nodes that must follow U_NODE. (only valid at the
   last row of the scheduling window)  
static void update_node_sched_params ( )
   Update the sched_params (time, row and stage) for node U using the II,
   the CYCLE of U and MIN_CYCLE.
   We're not simply taking the following
   SCHED_STAGE (u) = CALC_STAGE_COUNT (SCHED_TIME (u), min_cycle, ii);
   because the stages may not be aligned on cycle 0.  
     The calculation of stage count is done adding the number
     of stages before cycle zero and after cycle zero.  
static void verify_partial_schedule ( partial_schedule_ptr  ,

Referenced by sms_schedule_by_order().

static void verify_partial_schedule ( )
             ??? Test also that all nodes of sched_nodes are in ps, perhaps by
             popcount (sched_nodes) == number of insns in ps.  

References bitmap_and_compl(), bitmap_ior(), find_nodes_on_paths(), ddg_scc::nodes, order_nodes_in_scc(), and ddg_all_sccs::sccs.

Variable Documentation

vec<node_sched_params> node_sched_param_vec
   A vector that contains the sched data for each ps_insn.  
struct common_sched_info_def sms_common_sched_info

Referenced by dump_insn_location().

struct sched_deps_info_def sms_sched_deps_info
Initial value:
0, 0, 0

Referenced by dump_insn_location().

struct haifa_sched_info sms_sched_info
Initial value:
0, 0,

Referenced by dump_insn_location().