Subversion Repositories openrisc

/* Swing Modulo Scheduling implementation.

   Copyright (C) 2004, 2005, 2006, 2007, 2008, 2009, 2010, 2011, 2012

   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 "diagnostic-core.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 "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"

#include "df.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 CALC_STAGE_COUNT(max_cycle,min_cycle,ii) ((max_cycle - min_cycle \

                         + 1 + ii - 1) / ii)

/* The stage count of ps.  */

#define PS_STAGE_COUNT(ps) (((partial_schedule_ptr)(ps))->stage_count)

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

struct ps_insn

{

  /* Identifies the instruction to be scheduled.  Values smaller than

     the ddg's num_nodes refer directly to ddg nodes.  A value of

     X - num_nodes refers to register move X.  */

  int id;

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

};

/* Information about a register move that has been added to a partial

   schedule.  */

struct ps_reg_move_info

{

  /* The source of the move is defined by the ps_insn with id DEF.

     The destination is used by the ps_insns with the ids in USES.  */

  int def;

  sbitmap uses;

  /* The original form of USES' instructions used OLD_REG, but they

     should now use NEW_REG.  */

  rtx old_reg;

  rtx new_reg;

  /* The number of consecutive stages that the move occupies.  */

  int num_consecutive_stages;

  /* An instruction that sets NEW_REG to the correct value.  The first

     move associated with DEF will have an rhs of OLD_REG; later moves

     use the result of the previous move.  */

  rtx insn;

};

typedef struct ps_reg_move_info ps_reg_move_info;

DEF_VEC_O (ps_reg_move_info);

DEF_VEC_ALLOC_O (ps_reg_move_info, heap);

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

  /* All the moves added for this partial schedule.  Index X has

     a ps_insn id of X + g->num_nodes.  */

  VEC (ps_reg_move_info, heap) *reg_moves;

  /*  rows_length[i] holds the number of instructions in the row.

      It is used only (as an optimization) to back off quickly from

      trying to schedule a node in a full row; that is, to avoid running

      through futile DFA state transitions.  */

  int *rows_length;

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

  int stage_count;  /* The stage count of the partial schedule.  */

};

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

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

#define NODE_ASAP(node) ((node)->aux.count)

#define SCHED_PARAMS(x) VEC_index (node_sched_params, node_sched_param_vec, x)

#define SCHED_TIME(x) (SCHED_PARAMS (x)->time)

#define SCHED_ROW(x) (SCHED_PARAMS (x)->row)

#define SCHED_STAGE(x) (SCHED_PARAMS (x)->stage)

#define SCHED_COLUMN(x) (SCHED_PARAMS (x)->column)

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

typedef struct node_sched_params

{

  int time;     /* The absolute scheduling cycle.  */

  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;

typedef struct node_sched_params node_sched_params;

DEF_VEC_O (node_sched_params);

DEF_VEC_ALLOC_O (node_sched_params, heap);

/* 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 used 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, NULL,

  NULL, NULL,

};

/* Partial schedule instruction ID in PS is a register move.  Return

   information about it.  */

static struct ps_reg_move_info *

ps_reg_move (partial_schedule_ptr ps, int id)

{

  gcc_checking_assert (id >= ps->g->num_nodes);

  return VEC_index (ps_reg_move_info, ps->reg_moves, id - ps->g->num_nodes);

}

/* Return the rtl instruction that is being scheduled by partial schedule

   instruction ID, which belongs to schedule PS.  */

static rtx

ps_rtl_insn (partial_schedule_ptr ps, int id)

{

  if (id < ps->g->num_nodes)

    return ps->g->nodes[id].insn;

  else

    return ps_reg_move (ps, id)->insn;

}

/* Partial schedule instruction ID, which belongs to PS, occured 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.  */

static rtx

ps_first_note (partial_schedule_ptr ps, int id)

{

  gcc_assert (id < ps->g->num_nodes);

  return ps->g->nodes[id].first_note;

}

/* Return the number of consecutive stages that are occupied by

   partial schedule instruction ID in PS.  */

static int

ps_num_consecutive_stages (partial_schedule_ptr ps, int id)

{

  if (id < ps->g->num_nodes)

    return 1;

  else

    return ps_reg_move (ps, id)->num_consecutive_stages;

}

/* 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_nondebug_insn (tail));

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

    if (!DEBUG_INSN_P (insn) && 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);

}

/* A vector that contains the sched data for each ps_insn.  */

static VEC (node_sched_params, heap) *node_sched_param_vec;

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

static void

set_node_sched_params (ddg_ptr g)

{

  VEC_truncate (node_sched_params, node_sched_param_vec, 0);

  VEC_safe_grow_cleared (node_sched_params, heap,

                         node_sched_param_vec, g->num_nodes);

}

/* Make sure that node_sched_param_vec has an entry for every move in PS.  */

static void

extend_node_sched_params (partial_schedule_ptr ps)

{

  VEC_safe_grow_cleared (node_sched_params, heap, node_sched_param_vec,

                         ps->g->num_nodes + VEC_length (ps_reg_move_info,

                                                        ps->reg_moves));

}

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

static void

update_node_sched_params (int u, int ii, int cycle, int min_cycle)

{

  int sc_until_cycle_zero;

  int stage;

  SCHED_TIME (u) = cycle;

  SCHED_ROW (u) = SMODULO (cycle, ii);

  /* The calculation of stage count is done adding the number

     of stages before cycle zero and after cycle zero.  */

  sc_until_cycle_zero = CALC_STAGE_COUNT (-1, min_cycle, ii);

  if (SCHED_TIME (u) < 0)

    {

      stage = CALC_STAGE_COUNT (-1, SCHED_TIME (u), ii);

      SCHED_STAGE (u) = sc_until_cycle_zero - stage;

    }

  else

    {

      stage = CALC_STAGE_COUNT (SCHED_TIME (u), 0, ii);

      SCHED_STAGE (u) = sc_until_cycle_zero + stage - 1;

    }

}

static void

print_node_sched_params (FILE *file, int num_nodes, partial_schedule_ptr ps)

{

  int i;

  if (! file)

    return;

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

    {

      node_sched_params_ptr nsp = SCHED_PARAMS (i);

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

               INSN_UID (ps_rtl_insn (ps, i)));

      fprintf (file, " asap = %d:\n", NODE_ASAP (&ps->g->nodes[i]));

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

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

    }

}

/* Set SCHED_COLUMN for each instruction in row ROW of PS.  */

static void

set_columns_for_row (partial_schedule_ptr ps, int row)

{

  ps_insn_ptr cur_insn;

  int column;

  column = 0;

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

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

}

/* Set SCHED_COLUMN for each instruction in PS.  */

static void

set_columns_for_ps (partial_schedule_ptr ps)

{

  int row;

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

    set_columns_for_row (ps, row);

}

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

static bool

schedule_reg_move (partial_schedule_ptr ps, int i_reg_move,

                   sbitmap distance1_uses, sbitmap must_follow)

{

  unsigned int u;

  int this_time, this_distance, this_start, this_end, this_latency;

  int start, end, c, ii;

  sbitmap_iterator sbi;

  ps_reg_move_info *move;

  rtx this_insn;

  ps_insn_ptr psi;

  move = ps_reg_move (ps, i_reg_move);

  ii = ps->ii;

  if (dump_file)

    {

      fprintf (dump_file, "Scheduling register move INSN %d; ii = %d"

               ", min cycle = %d\n\n", INSN_UID (move->insn), ii,

               PS_MIN_CYCLE (ps));

      print_rtl_single (dump_file, move->insn);

      fprintf (dump_file, "\n%11s %11s %5s\n", "start", "end", "time");

      fprintf (dump_file, "=========== =========== =====\n");

    }

  start = INT_MIN;

  end = INT_MAX;

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

     dependencies:

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

  this_insn = ps_rtl_insn (ps, move->def);

  this_latency = insn_latency (this_insn, move->insn);

  this_distance = distance1_uses && move->def < ps->g->num_nodes ? 1 : 0;

  this_time = SCHED_TIME (move->def) - this_distance * ii;

  this_start = this_time + this_latency;

  this_end = this_time + ii;

  if (dump_file)

    fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",

             this_start, this_end, SCHED_TIME (move->def),

             INSN_UID (this_insn), this_latency, this_distance,

             INSN_UID (move->insn));

  if (start < this_start)

    start = this_start;

  if (end > this_end)

    end = this_end;

  /* Handle the dependencies between the move and previously-scheduled

     successors.  */

  EXECUTE_IF_SET_IN_SBITMAP (move->uses, 0, u, sbi)

    {

      this_insn = ps_rtl_insn (ps, u);

      this_latency = insn_latency (move->insn, this_insn);

      if (distance1_uses && !TEST_BIT (distance1_uses, u))

        this_distance = -1;

      else

        this_distance = 0;

      this_time = SCHED_TIME (u) + this_distance * ii;

      this_start = this_time - ii;

      this_end = this_time - this_latency;

      if (dump_file)

        fprintf (dump_file, "%11d %11d %5d %d --(T,%d,%d)--> %d\n",

                 this_start, this_end, SCHED_TIME (u), INSN_UID (move->insn),

                 this_latency, this_distance, INSN_UID (this_insn));

      if (start < this_start)

        start = this_start;

      if (end > this_end)

        end = this_end;

    }

  if (dump_file)

    {

      fprintf (dump_file, "----------- ----------- -----\n");

      fprintf (dump_file, "%11d %11d %5s %s\n", start, end, "", "(max, min)");

    }

  sbitmap_zero (must_follow);

  SET_BIT (must_follow, move->def);

  start = MAX (start, end - (ii - 1));

  for (c = end; c >= start; c--)

    {

      psi = ps_add_node_check_conflicts (ps, i_reg_move, c,

                                         move->uses, must_follow);

      if (psi)

        {

          update_node_sched_params (i_reg_move, ii, c, PS_MIN_CYCLE (ps));

          if (dump_file)

            fprintf (dump_file, "\nScheduled register move INSN %d at"

                     " time %d, row %d\n\n", INSN_UID (move->insn), c,

                     SCHED_ROW (i_reg_move));

          return true;

        }

    }

  if (dump_file)

    fprintf (dump_file, "\nNo available slot\n\n");

  return false;

}

/*

   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 bool

schedule_reg_moves (partial_schedule_ptr ps)

{

  ddg_ptr g = ps->g;

  int ii = ps->ii;

  int i;

  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;

      rtx prev_reg, old_reg;

      int first_move;

      int distances[2];

      sbitmap must_follow;

      sbitmap distance1_uses;

      rtx set = single_set (u->insn);

      /* Skip instructions that do not set a register.  */

      if ((set && !REG_P (SET_DEST (set))))

        continue;

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

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

      distances[0] = distances[1] = false;

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

                                - SCHED_TIME (e->src->cuid)) / ii;

            if (e->distance == 1)

              nreg_moves4e = (SCHED_TIME (e->dest->cuid)