Subversion Repositories openrisc

/* Swing Modulo Scheduling implementation.

   Copyright (C) 2004, 2005, 2006, 2007, 2008

   Free Software Foundation, Inc.

   Contributed by Ayal Zaks and Mustafa Hagog <zaks,mustafa@il.ibm.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/>.  */

#include "config.h"

#include "system.h"

#include "coretypes.h"

#include "tm.h"

#include "toplev.h"

#include "rtl.h"

#include "tm_p.h"

#include "hard-reg-set.h"

#include "regs.h"

#include "function.h"

#include "flags.h"

#include "insn-config.h"

#include "insn-attr.h"

#include "except.h"

#include "toplev.h"

#include "recog.h"

#include "sched-int.h"

#include "target.h"

#include "cfglayout.h"

#include "cfgloop.h"

#include "cfghooks.h"

#include "expr.h"

#include "params.h"

#include "gcov-io.h"

#include "ddg.h"

#include "timevar.h"

#include "tree-pass.h"

#include "dbgcnt.h"

#ifdef INSN_SCHEDULING

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

         up).

      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 partial_schedule *partial_schedule_ptr;

typedef struct ps_insn *ps_insn_ptr;

/* The minimum (absolute) cycle that a node of ps was scheduled in.  */

#define PS_MIN_CYCLE(ps) (((partial_schedule_ptr)(ps))->min_cycle)

/* The maximum (absolute) cycle that a node of ps was scheduled in.  */

#define PS_MAX_CYCLE(ps) (((partial_schedule_ptr)(ps))->max_cycle)

/* Perform signed modulo, always returning a non-negative value.  */

#define SMODULO(x,y) ((x) % (y) < 0 ? ((x) % (y) + (y)) : (x) % (y))

/* The number of different iterations the nodes in ps span, assuming

   the stage boundaries are placed efficiently.  */

#define PS_STAGE_COUNT(ps) ((PS_MAX_CYCLE (ps) - PS_MIN_CYCLE (ps) \

                             + 1 + (ps)->ii - 1) / (ps)->ii)

/* A single instruction in the partial schedule.  */

struct ps_insn

{

  /* The corresponding DDG_NODE.  */

  ddg_node_ptr node;

  /* The (absolute) cycle in which the PS instruction is scheduled.

     Same as SCHED_TIME (node).  */

  int cycle;

  /* The next/prev PS_INSN in the same row.  */

  ps_insn_ptr next_in_row,

              prev_in_row;

  /* The number of nodes in the same row that come after this node.  */

  int row_rest_count;

};

/* Holds the partial schedule as an array of II rows.  Each entry of the

   array points to a linked list of PS_INSNs, which represents the

   instructions that are scheduled for that row.  */

struct partial_schedule

{

  int ii;       /* Number of rows in the partial schedule.  */

  int history;  /* Threshold for conflict checking using DFA.  */

  /* rows[i] points to linked list of insns scheduled in row i (0<=i<ii).  */

  ps_insn_ptr *rows;

  /* The earliest absolute cycle of an insn in the partial schedule.  */

  int min_cycle;

  /* The latest absolute cycle of an insn in the partial schedule.  */

  int max_cycle;

  ddg_ptr g;    /* The DDG of the insns in the partial schedule.  */

};

/* We use this to record all the register replacements we do in

   the kernel so we can undo SMS if it is not profitable.  */

struct undo_replace_buff_elem

{

  rtx insn;

  rtx orig_reg;

  rtx new_reg;

  struct undo_replace_buff_elem *next;

};

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,

                                                ddg_node_ptr node, int cycle,

                                                sbitmap must_precede,

                                                sbitmap must_follow);

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);

/* This page defines constants and structures for the modulo scheduling

   driver.  */

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 void duplicate_insns_of_cycles (partial_schedule_ptr,

                                       int, int, int, rtx);

#define SCHED_ASAP(x) (((node_sched_params_ptr)(x)->aux.info)->asap)

#define SCHED_TIME(x) (((node_sched_params_ptr)(x)->aux.info)->time)

#define SCHED_FIRST_REG_MOVE(x) \

        (((node_sched_params_ptr)(x)->aux.info)->first_reg_move)

#define SCHED_NREG_MOVES(x) \

        (((node_sched_params_ptr)(x)->aux.info)->nreg_moves)

#define SCHED_ROW(x) (((node_sched_params_ptr)(x)->aux.info)->row)

#define SCHED_STAGE(x) (((node_sched_params_ptr)(x)->aux.info)->stage)

#define SCHED_COLUMN(x) (((node_sched_params_ptr)(x)->aux.info)->column)

/* The scheduling parameters held for each node.  */

typedef struct node_sched_params

{

  int asap;     /* A lower-bound on the absolute scheduling cycle.  */

  int time;     /* The absolute scheduling cycle (time >= asap).  */

  /* The following field (first_reg_move) is a pointer to the first

     register-move instruction added to handle the modulo-variable-expansion

     of the register defined by this node.  This register-move copies the

     original register defined by the node.  */

  rtx first_reg_move;

  /* The number of register-move instructions added, immediately preceding

     first_reg_move.  */

  int nreg_moves;

  int row;    /* Holds time % ii.  */

  int stage;  /* Holds time / ii.  */

  /* The column of a node inside the ps.  If nodes u, v are on the same row,

     u will precede v if column (u) < column (v).  */

  int column;

} *node_sched_params_ptr;

/* 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 const char *

sms_print_insn (const_rtx insn, int aligned ATTRIBUTE_UNUSED)

{

  static char tmp[80];

  sprintf (tmp, "i%4d", INSN_UID (insn));

  return tmp;

}

static void

compute_jump_reg_dependencies (rtx insn ATTRIBUTE_UNUSED,

                               regset cond_exec ATTRIBUTE_UNUSED,

                               regset used ATTRIBUTE_UNUSED,

                               regset set ATTRIBUTE_UNUSED)

{

}

static struct common_sched_info_def sms_common_sched_info;

static struct sched_deps_info_def sms_sched_deps_info =

  {

    compute_jump_reg_dependencies,

    NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL, NULL,

    NULL,

    0, 0, 0

  };

static struct haifa_sched_info sms_sched_info =

{

  NULL,

  NULL,

  NULL,

  NULL,

  NULL,

  sms_print_insn,

  NULL,

  NULL, /* insn_finishes_block_p */

  NULL, NULL,

  NULL, NULL,

  0, 0,

  NULL, NULL, NULL,

};

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

static rtx

doloop_register_get (rtx head ATTRIBUTE_UNUSED, rtx tail ATTRIBUTE_UNUSED)

{

#ifdef HAVE_doloop_end

  rtx reg, condition, insn, first_insn_not_to_check;

  if (!JUMP_P (tail))

    return NULL_RTX;

  /* TODO: Free SMS's dependence on doloop_condition_get.  */

  condition = doloop_condition_get (tail);

  if (! condition)

    return NULL_RTX;

  if (REG_P (XEXP (condition, 0)))

    reg = XEXP (condition, 0);

  else if (GET_CODE (XEXP (condition, 0)) == PLUS

           && REG_P (XEXP (XEXP (condition, 0), 0)))

    reg = XEXP (XEXP (condition, 0), 0);

  else

    gcc_unreachable ();

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

  first_insn_not_to_check = (GET_CODE (PATTERN (tail)) == PARALLEL ? tail

                             : PREV_INSN (tail));

  for (insn = head; insn != first_insn_not_to_check; insn = NEXT_INSN (insn))

    if (reg_mentioned_p (reg, insn))

      {

        if (dump_file)

        {

          fprintf (dump_file, "SMS count_reg found ");

          print_rtl_single (dump_file, reg);

          fprintf (dump_file, " outside control in insn:\n");

          print_rtl_single (dump_file, insn);

        }

        return NULL_RTX;

      }

  return reg;

#else

  return NULL_RTX;

#endif

}

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

static rtx

const_iteration_count (rtx count_reg, basic_block pre_header,

                       HOST_WIDEST_INT * count)

{

  rtx insn;

  rtx head, tail;

  if (! pre_header)

    return NULL_RTX;

  get_ebb_head_tail (pre_header, pre_header, &head, &tail);

  for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))

    if (NONDEBUG_INSN_P (insn) && single_set (insn) &&

        rtx_equal_p (count_reg, SET_DEST (single_set (insn))))

      {

        rtx pat = single_set (insn);

        if (CONST_INT_P (SET_SRC (pat)))

          {

            *count = INTVAL (SET_SRC (pat));

            return insn;

          }

        return NULL_RTX;

      }

  return NULL_RTX;

}

/* 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 int

res_MII (ddg_ptr g)

{

  if (targetm.sched.sms_res_mii)

    return targetm.sched.sms_res_mii (g);

  return ((g->num_nodes - g->num_debug) / issue_rate);

}

/* Points to the array that contains the sched data for each node.  */

static node_sched_params_ptr node_sched_params;

/* Allocate sched_params for each node and initialize it.  Assumes that

   the aux field of each node contain the asap bound (computed earlier),

   and copies it into the sched_params field.  */

static void

set_node_sched_params (ddg_ptr g)

{

  int i;

  /* Allocate for each node in the DDG a place to hold the "sched_data".  */

  /* Initialize ASAP/ALAP/HIGHT to zero.  */

  node_sched_params = (node_sched_params_ptr)

                       xcalloc (g->num_nodes,

                                sizeof (struct node_sched_params));

  /* Set the pointer of the general data of the node to point to the

     appropriate sched_params structure.  */

  for (i = 0; i < g->num_nodes; i++)

    {

      /* Watch out for aliasing problems?  */

      node_sched_params[i].asap = g->nodes[i].aux.count;

      g->nodes[i].aux.info = &node_sched_params[i];

    }

}

static void

print_node_sched_params (FILE *file, int num_nodes, ddg_ptr g)

{

  int i;

  if (! file)

    return;

  for (i = 0; i < num_nodes; i++)

    {

      node_sched_params_ptr nsp = &node_sched_params[i];

      rtx reg_move = nsp->first_reg_move;

      int j;

      fprintf (file, "Node = %d; INSN = %d\n", i,

               (INSN_UID (g->nodes[i].insn)));

      fprintf (file, " asap = %d:\n", nsp->asap);

      fprintf (file, " time = %d:\n", nsp->time);

      fprintf (file, " nreg_moves = %d:\n", nsp->nreg_moves);

      for (j = 0; j < nsp->nreg_moves; j++)

        {

          fprintf (file, " reg_move = ");

          print_rtl_single (file, reg_move);

          reg_move = PREV_INSN (reg_move);

        }

    }

}

/*

   Breaking intra-loop register anti-dependences:

   Each intra-loop register anti-dependence implies a cross-iteration true

   dependence of distance 1. Therefore, we can remove such false dependencies

   and figure out if the partial schedule broke them by checking if (for a

   true-dependence of distance 1): SCHED_TIME (def) < SCHED_TIME (use) and

   if so generate a register move.   The number of such moves is equal to:

              SCHED_TIME (use) - SCHED_TIME (def)       { 0 broken

   nreg_moves = ----------------------------------- + 1 - {   dependence.

                            ii                          { 1 if not.

*/

static struct undo_replace_buff_elem *

generate_reg_moves (partial_schedule_ptr ps, bool rescan)

{

  ddg_ptr g = ps->g;

  int ii = ps->ii;

  int i;

  struct undo_replace_buff_elem *reg_move_replaces = NULL;

  for (i = 0; i < g->num_nodes; i++)

    {

      ddg_node_ptr u = &g->nodes[i];

      ddg_edge_ptr e;

      int nreg_moves = 0, i_reg_move;

      sbitmap *uses_of_defs;

      rtx last_reg_move;

      rtx prev_reg, old_reg;

      /* Compute the number of reg_moves needed for u, by looking at life

         ranges started at u (excluding self-loops).  */

      for (e = u->out; e; e = e->next_out)

        if (e->type == TRUE_DEP && e->dest != e->src)

          {

            int nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;

            if (e->distance == 1)

              nreg_moves4e = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;

            /* If dest precedes src in the schedule of the kernel, then dest

               will read before src writes and we can save one reg_copy.  */

            if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)

                && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))

              nreg_moves4e--;

            nreg_moves = MAX (nreg_moves, nreg_moves4e);

          }

      if (nreg_moves == 0)

        continue;

      /* Every use of the register defined by node may require a different

         copy of this register, depending on the time the use is scheduled.

         Set a bitmap vector, telling which nodes use each copy of this

         register.  */

      uses_of_defs = sbitmap_vector_alloc (nreg_moves, g->num_nodes);

      sbitmap_vector_zero (uses_of_defs, nreg_moves);

      for (e = u->out; e; e = e->next_out)

        if (e->type == TRUE_DEP && e->dest != e->src)

          {

            int dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src)) / ii;

            if (e->distance == 1)

              dest_copy = (SCHED_TIME (e->dest) - SCHED_TIME (e->src) + ii) / ii;

            if (SCHED_ROW (e->dest) == SCHED_ROW (e->src)

                && SCHED_COLUMN (e->dest) < SCHED_COLUMN (e->src))

              dest_copy--;

            if (dest_copy)

              SET_BIT (uses_of_defs[dest_copy - 1], e->dest->cuid);

          }

      /* Now generate the reg_moves, attaching relevant uses to them.  */

      SCHED_NREG_MOVES (u) = nreg_moves;

      old_reg = prev_reg = copy_rtx (SET_DEST (single_set (u->insn)));

      /* Insert the reg-moves right before the notes which precede

         the insn they relates to.  */

      last_reg_move = u->first_note;

      for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)

        {

          unsigned int i_use = 0;

          rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));

          rtx reg_move = gen_move_insn (new_reg, prev_reg);

          sbitmap_iterator sbi;

          add_insn_before (reg_move, last_reg_move, NULL);

          last_reg_move = reg_move;

          if (!SCHED_FIRST_REG_MOVE (u))

            SCHED_FIRST_REG_MOVE (u) = reg_move;

          EXECUTE_IF_SET_IN_SBITMAP (uses_of_defs[i_reg_move], 0, i_use, sbi)

            {

              struct undo_replace_buff_elem *rep;

              rep = (struct undo_replace_buff_elem *)

                    xcalloc (1, sizeof (struct undo_replace_buff_elem));

              rep->insn = g->nodes[i_use].insn;

              rep->orig_reg = old_reg;

              rep->new_reg = new_reg;

              if (! reg_move_replaces)

                reg_move_replaces = rep;

              else

                {

                  rep->next = reg_move_replaces;

                  reg_move_replaces = rep;

                }

              replace_rtx (g->nodes[i_use].insn, old_reg, new_reg);

              if (rescan)

                df_insn_rescan (g->nodes[i_use].insn);

            }

          prev_reg = new_reg;

        }

      sbitmap_vector_free (uses_of_defs);

    }

  return reg_move_replaces;

}

/* Free memory allocated for the undo buffer.  */

static void

free_undo_replace_buff (struct undo_replace_buff_elem *reg_move_replaces)

{

  while (reg_move_replaces)

    {

      struct undo_replace_buff_elem *rep = reg_move_replaces;

      reg_move_replaces = reg_move_replaces->next;

      free (rep);

    }

}

/* Bump the SCHED_TIMEs of all nodes to start from zero.  Set the values

   of SCHED_ROW and SCHED_STAGE.  */

static void

normalize_sched_times (partial_schedule_ptr ps)

{

  int row;

  int amount = PS_MIN_CYCLE (ps);

  int ii = ps->ii;

  ps_insn_ptr crr_insn;

  for (row = 0; row < ii; row++)

    for (crr_insn = ps->rows[row]; crr_insn; crr_insn = crr_insn->next_in_row)

      {

        ddg_node_ptr u = crr_insn->node;

        int normalized_time = SCHED_TIME (u) - amount;

        if (dump_file)

          fprintf (dump_file, "crr_insn->node=%d, crr_insn->cycle=%d,\

                   min_cycle=%d\n", crr_insn->node->cuid, SCHED_TIME

                   (u), ps->min_cycle);

        gcc_assert (SCHED_TIME (u) >= ps->min_cycle);

        gcc_assert (SCHED_TIME (u) <= ps->max_cycle);

        SCHED_TIME (u) = normalized_time;

        SCHED_ROW (u) = normalized_time % ii;

        SCHED_STAGE (u) = normalized_time / ii;

      }

}

/* Set SCHED_COLUMN of each node according to its position in PS.  */

static void

set_columns_for_ps (partial_schedule_ptr ps)

{

  int row;

  for (row = 0; row < ps->ii; row++)

    {

      ps_insn_ptr cur_insn = ps->rows[row];

      int column = 0;

      for (; cur_insn; cur_insn = cur_insn->next_in_row)

        SCHED_COLUMN (cur_insn->node) = column++;

    }

}

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

permute_partial_schedule (partial_schedule_ptr ps, rtx last)

{

  int ii = ps->ii;

  int row;

  ps_insn_ptr ps_ij;

  for (row = 0; row < ii ; row++)

    for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)

      if (PREV_INSN (last) != ps_ij->node->insn)

        reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,

                            PREV_INSN (last));

}

static void

duplicate_insns_of_cycles (partial_schedule_ptr ps, int from_stage,

                           int to_stage, int for_prolog, rtx count_reg)

{

  int row;

  ps_insn_ptr ps_ij;

  for (row = 0; row < ps->ii; row++)

    for (ps_ij = ps->rows[row]; ps_ij; ps_ij = ps_ij->next_in_row)

      {

        ddg_node_ptr u_node = ps_ij->node;

        int j, i_reg_moves;

        rtx reg_move = NULL_RTX;

        /* Do not duplicate any insn which refers to count_reg as it

           belongs to the control part.

           TODO: This should be done by analyzing the control part of

           the loop.  */

        if (reg_mentioned_p (count_reg, u_node->insn))

          continue;

        if (for_prolog)

          {

            /* SCHED_STAGE (u_node) >= from_stage == 0.  Generate increasing

               number of reg_moves starting with the second occurrence of

               u_node, which is generated if its SCHED_STAGE <= to_stage.  */

            i_reg_moves = to_stage - SCHED_STAGE (u_node) + 1;

            i_reg_moves = MAX (i_reg_moves, 0);

            i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));

            /* The reg_moves start from the *first* reg_move backwards.  */

            if (i_reg_moves)

              {

                reg_move = SCHED_FIRST_REG_MOVE (u_node);

                for (j = 1; j < i_reg_moves; j++)

                  reg_move = PREV_INSN (reg_move);

              }

          }

        else /* It's for the epilog.  */

          {

            /* SCHED_STAGE (u_node) <= to_stage.  Generate all reg_moves,

               starting to decrease one stage after u_node no longer occurs;

               that is, generate all reg_moves until

               SCHED_STAGE (u_node) == from_stage - 1.  */

            i_reg_moves = SCHED_NREG_MOVES (u_node)

                       - (from_stage - SCHED_STAGE (u_node) - 1);

            i_reg_moves = MAX (i_reg_moves, 0);

            i_reg_moves = MIN (i_reg_moves, SCHED_NREG_MOVES (u_node));

            /* The reg_moves start from the *last* reg_move forwards.  */

            if (i_reg_moves)

              {

                reg_move = SCHED_FIRST_REG_MOVE (u_node);

                for (j = 1; j < SCHED_NREG_MOVES (u_node); j++)

                  reg_move = PREV_INSN (reg_move);

              }

          }

        for (j = 0; j < i_reg_moves; j++, reg_move = NEXT_INSN (reg_move))

          emit_insn (copy_rtx (PATTERN (reg_move)));

        if (SCHED_STAGE (u_node) >= from_stage

            && SCHED_STAGE (u_node) <= to_stage)

          duplicate_insn_chain (u_node->first_note, u_node->insn);

      }

}

/* Generate the instructions (including reg_moves) for prolog & epilog.  */

static void

generate_prolog_epilog (partial_schedule_ptr ps, struct loop *loop,

                        rtx count_reg, rtx count_init)

{

  int i;

  int last_stage = PS_STAGE_COUNT (ps) - 1;