/* Swing Modulo Scheduling implementation.
   Copyright (C) 2004
   Free Software Foundation, Inc.

This file is part of GCC.

GCC is free software; you can redistribute it and/or modify it under
the terms of the GNU General Public License as published by the Free
Software Foundation; either version 2, 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 COPYING.  If not, write to the Free
Software Foundation, 59 Temple Place - Suite 330, Boston, MA
02111-1307, USA.  */


#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 "basic-block.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 "expr.h"  /* For gen_move_insn.  */
#include "params.h"  /* For MAX_SMS_PASSES.  */
#include "gcov-io.h" /* For profile_info. */

#include "ddg.h"
#include "modulo-ps.h"

/* Do not apply SMS to loops that iterate less than some small
   (SMS_MIN_LOOP_COUNT) number of iterations, when that number is a
   compile-time constant.  Reset based on experiments.  */
#define SMS_MIN_LOOP_COUNT 7

/* From haifa-sched.c (begin):  */
/* issue_rate is the number of insns that can be scheduled in the same
   machine cycle.  It can be defined in the config/mach/mach.h file,
   otherwise we set it to 1.  */

int issue_rate;
/* From haifa-sched.c (end).  */

/* For printing DDG to a dump_file when debugging.  */
static FILE *vcg_dump_file;

/* For printing statistics.  */
static FILE *stats_file;

void sms_schedule (FILE *);
int sms_order_nodes (ddg_ptr, int, int * result);
static void set_node_sched_params (ddg_ptr);
static partial_schedule_ptr sms_schedule_by_order (ddg_ptr, int, int,
						   int *, FILE*);
static void permute_partial_schedule (partial_schedule_ptr ps, rtx last);
static void generate_prolog_epilog (partial_schedule_ptr);
static void duplicate_insns_of_stages (partial_schedule_ptr ps,
				       int from_stage, int to_stage,
				       int is_prolog);

/* From cfglayout.c.  */
rtx duplicate_insn_chain (rtx, 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 include a lower-bound
   on it's scheduling cycle (asap); the absolute cycle we decided to
   schedule it (time; time >= asap); a pointer to the first register-
   move instruction added to handle the modulo-variable-expansion (mve)
   of the register defined by this node (first_reg_move; copies the
   original register defined by the node); the number of such register-
   move instructions generated (nreg_moves; they immediately preceed
   first_reg_move); the row and stage of the node (caching results of
   % and /) and the column of the node in the partial schedule.  */
typedef struct node_sched_params
{
  int asap;
  int time;
  rtx 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 preceed 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 dependecies.
   They are used when initializing the sched_info structure.  */
static const char *
sms_print_insn (rtx insn, int aligned ATTRIBUTE_UNUSED)
{
  static char tmp[80];

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

static int
contributes_to_priority (rtx next, rtx insn)
{
  return BLOCK_NUM (next) == BLOCK_NUM (insn);
}

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 sched_info sms_sched_info =
{
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  sms_print_insn,
  contributes_to_priority,
  compute_jump_reg_dependencies,
  NULL, NULL,
  NULL, NULL,
  0, 0, 0
};


/* Return the register decremented and tested or zero if it is not a
   decrement and branch jump insn (similar to doloop_condition_get).  */
static rtx
doloop_register_get (rtx insn)
{
  rtx pattern, cmp, inc, reg, condition;

  if (GET_CODE (insn) != JUMP_INSN)
    return NULL_RTX;
  pattern = PATTERN (insn);

  /* The canonical doloop pattern we expect is:

     (parallel [(set (pc) (if_then_else (condition)
					(label_ref (label))
					(pc)))
		(set (reg) (plus (reg) (const_int -1)))
		(additional clobbers and uses)])

    where condition is further restricted to be
      (ne (reg) (const_int 1)).  */

  if (GET_CODE (pattern) != PARALLEL)
    return NULL_RTX;

  cmp = XVECEXP (pattern, 0, 0);
  inc = XVECEXP (pattern, 0, 1);

  /* Check for (set (reg) (something)).  */
  if (GET_CODE (inc) != SET || ! REG_P (SET_DEST (inc)))
    return NULL_RTX;

  /* Extract loop counter register.  */
  reg = SET_DEST (inc);

  /* Check if something = (plus (reg) (const_int -1)).  */
  if (GET_CODE (SET_SRC (inc)) != PLUS
      || XEXP (SET_SRC (inc), 0) != reg
      || XEXP (SET_SRC (inc), 1) != constm1_rtx)
    return NULL_RTX;

  /* Check for (set (pc) (if_then_else (condition)
				       (label_ref (label))
				       (pc))).  */
  if (GET_CODE (cmp) != SET
      || SET_DEST (cmp) != pc_rtx
      || GET_CODE (SET_SRC (cmp)) != IF_THEN_ELSE
      || GET_CODE (XEXP (SET_SRC (cmp), 1)) != LABEL_REF
      || XEXP (SET_SRC (cmp), 2) != pc_rtx)
    return NULL_RTX;

  /* Extract loop termination condition.  */
  condition = XEXP (SET_SRC (cmp), 0);

  /* Check if condition = (ne (reg) (const_int 1)), which is more
     restrictive than the check in doloop_condition_get:
     if ((GET_CODE (condition) != GE && GET_CODE (condition) != NE)
	 || GET_CODE (XEXP (condition, 1)) != CONST_INT).  */
  if (GET_CODE (condition) != NE
      || XEXP (condition, 1) != const1_rtx)
    return NULL_RTX;

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

  return NULL_RTX;
}

/* 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, int * count)
{
  rtx insn;
  rtx head, tail;
  get_block_head_tail (pre_header->index, &head, &tail);

  for (insn = tail; insn != PREV_INSN (head); insn = PREV_INSN (insn))
    if (INSN_P (insn) && single_set (insn) &&
	rtx_equal_p (count_reg, SET_DEST (single_set (insn))))
      {
	rtx pat = single_set (insn);

	if (GET_CODE (SET_SRC (pat)) == CONST_INT)
	  {
	    *count = INTVAL (SET_SRC (pat));
	    return insn;
	  }

	return NULL_RTX;
      }

  return NULL_RTX;
}

/* A very simple resource-based lower bound on the initiation interval.
   Todo: improve the accuracy of this bound by considering the
   utilization of various units.  */
static int
res_MII (ddg_ptr g)
{
  return (g->num_nodes / 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 strcture.  */
  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 * dump_file, int num_nodes)
{
  int i;

  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 (dump_file, "Node %d:\n", i);
      fprintf (dump_file, " asap = %d:\n", nsp->asap);
      fprintf (dump_file, " time = %d:\n", nsp->time);
      fprintf (dump_file, " nreg_moves = %d:\n", nsp->nreg_moves);
      for (j = 0; j < nsp->nreg_moves; j++)
	{
	  fprintf (dump_file, " reg_move = ");
	  print_rtl_single (dump_file, reg_move);
	  reg_move = PREV_INSN (reg_move);
	}
    }
}

/* Calculate an upper bound for II. SMS should not schedule the loop if it
   requires more cycles than this bound. Currently set to the sum of the
   longest latency edge for each node. Reset based on experiments.  */
static int
calculate_maxii (ddg_ptr g)
{
  int i;
  int maxii = 0;

  for (i=0; i<g->num_nodes; i++)
    {
      ddg_node_ptr u = &g->nodes[i];
      ddg_edge_ptr e;
      int max_edge_latency = 0;

      for (e = u->out; e ; e = e->next_out)
	max_edge_latency = MAX (max_edge_latency , e->latency);

      maxii += max_edge_latency;
    }
  return maxii;
}


/* Given the partial schdule, generate register moves when the length
   of the register live range is more than ii; the number of moves is
   determined according to the following equation:
		SCHED_TIME (use) - SCHED_TIME (def)   { 1 broken loop-carried
   nreg_moves = ----------------------------------- - {   dependecnce.
			      ii		      { 0 if not.
   This handles the modulo-variable-expansions (mve's) needed for the ps.  */
static void
generate_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;
      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 dest preceeds 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 (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)));
      last_reg_move = u->insn;

      for (i_reg_move = 0; i_reg_move < nreg_moves; i_reg_move++)
	{
	  int i_use;
	  rtx new_reg = gen_reg_rtx (GET_MODE (prev_reg));
	  rtx reg_move = gen_move_insn (new_reg, prev_reg);

	  add_insn_before (reg_move, last_reg_move);
	  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,
	    replace_rtx (g->nodes[i_use].insn, old_reg, new_reg));

	  prev_reg = new_reg;
	}
    }
}

/* 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 i;
  ddg_ptr g = ps->g;
  int amount = PS_MIN_CYCLE (ps);
  int ii = ps->ii;

  for (i = 0; i < g->num_nodes; i++)
    {
      ddg_node_ptr u = &g->nodes[i];
      int normalized_time = SCHED_TIME (u) - amount;

      if (normalized_time < 0)
	abort ();

      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)
      reorder_insns_nobb (ps_ij->node->first_note, ps_ij->node->insn,
			  PREV_INSN (last));
}

/* Used to generate the prologue & epilogue. Duplicate the subset of
   nodes whose stages are between FROM_STAGE and TO_STAGE (inclusive
   of both), together with a prefix/suffix of their reg_moves.  */
static void
duplicate_insns_of_stages (partial_schedule_ptr ps, int from_stage,
			   int to_stage, int for_prolog)
{
  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;

	if (for_prolog)
	  {
	    /* SCHED_STAGE (u_node) >= from_stage == 0. Generate increasing
	       number of reg_moves starting with the second occurance of
	       u_node, which is generated if its SCHED_STAGE <= to_stage.  */
	    i_reg_moves = to_stage - SCHED_STAGE (u_node);
	    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)
{
  int first_stage = 0;
  int last_stage = PS_STAGE_COUNT (ps) - 1;
  int from_stage;
  int to_stage;
  edge e;

  /* Generate the prolog, inserting its insns on the loop-entry edge.  */
  start_sequence ();

  from_stage = first_stage;
  to_stage = first_stage;
  for (; to_stage < last_stage; to_stage++)
    duplicate_insns_of_stages (ps, from_stage, to_stage, 1);

  e = ps->g->bb->pred;
  if (e->src == ps->g->bb)
    e = e->pred_next;

  /* No need to call insert_insn_on_edge; we prepared the sequence.  */
  e->insns = get_insns ();
  end_sequence ();

  /* Generate the epilog, inserting its insns on the loop-exit edge.  */
  start_sequence ();

  from_stage = first_stage + 1;
  to_stage = last_stage;
  for (; from_stage <= to_stage; from_stage++)
    duplicate_insns_of_stages (ps, from_stage, to_stage, 0);

  e = ps->g->bb->succ;
  if (e->dest == ps->g->bb)
    e = e->succ_next;

  e->insns = get_insns ();
  end_sequence ();

  commit_edge_insertions ();
}

/* Return the line note insn preceding INSN, for debugging.  Taken from
   emit-rtl.c.  */
static rtx
find_line_note (rtx insn)
{
  for (; insn; insn = PREV_INSN (insn))
    if (GET_CODE (insn) == NOTE
	&& NOTE_LINE_NUMBER (insn) >= 0)
      break;

  return insn;
}

/* Main entry point, perform SMS scheduling on the loops of the function
   that consist of single basic blocks.  */
void
sms_schedule (FILE *dump_file)
{
  static int passes = 0;
  rtx insn;
  ddg_ptr g;
  basic_block bb, pre_header;
  int * node_order;
  int maxii;
  partial_schedule_ptr ps;

  if (dump_file)
    {
      /* Todo: rename this file as appropriate.  */
      vcg_dump_file = fopen ("vcg_dump_file.vcd","w");

      /* All statistics are collected into the same file.
	 Todo: rename this file as appropriate.  */
      if (profile_info && flag_branch_probabilities)
	stats_file = fopen ("~/sms-count-stats.txt", "a");
      else
	stats_file = fopen ("~/sms-stats.txt", "a");
    }
  else
    {
      vcg_dump_file = 0;
      stats_file = 0;
    }

  if (targetm.sched.issue_rate)
    {
      int temp = reload_completed;
      reload_completed = 1;
      issue_rate = (*targetm.sched.issue_rate) ();
      reload_completed = temp;
    }
  else
    issue_rate = 1;


  FOR_EACH_BB (bb)
    {
      rtx head, tail;
      rtx count_reg, count_init;
      int mii, rec_mii;
      int stage_count = 0;
      int loop_count;
      edge e;

      if (bb->index < 0)
	continue;

      /* Check if bb has two successors, one being itself.  */
      e = bb->succ;
      if (!e || !e->succ_next || e->succ_next->succ_next)
	continue;

      if (e->dest != bb && e->succ_next->dest != bb)
	continue;

      if ((e->flags & EDGE_COMPLEX)
	  || (e->succ_next->flags & EDGE_COMPLEX))
	continue;

      /* Check if bb has two predecessors, one being itself.  */
      /* In view of above, suffices to check e->pred_next->pred_next?  */
      e = bb->pred;
      if (!e || !e->pred_next || e->pred_next->pred_next)
	continue;

      if (e->src != bb && e->pred_next->src != bb)
	continue;

      if ((e->flags & EDGE_COMPLEX)
	  || (e->pred_next->flags & EDGE_COMPLEX))
	continue;

      if (passes++ > MAX_SMS_PASSES && MAX_SMS_PASSES != -1)
	{
	  if (dump_file)
	    fprintf (dump_file, "SMS reached MAX_PASSES... \n");
	  break;
	}

      get_block_head_tail (bb->index, &head, &tail);

      if (stats_file)
	{
	  rtx line_note = find_line_note (tail);

	  if (line_note)
	    fprintf (stats_file, "SMS bb %s %d (file, line)\n",
		     NOTE_SOURCE_FILE (line_note),
		     NOTE_LINE_NUMBER (line_note));
	  fprintf (stats_file, "SMS single-bb-loop\n");
	  if (profile_info && flag_branch_probabilities)
	    {
	      fprintf (stats_file, "SMS loop-count ");
	      fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
		       (HOST_WIDEST_INT) bb->count);
	      fprintf (stats_file, "\n");
	      fprintf (stats_file, "SMS preheader-count ");
	      if (bb->pred->src != bb)
		fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
			 (HOST_WIDEST_INT) bb->pred->count);
	      else
		fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
			 (HOST_WIDEST_INT) bb->pred->pred_next->count);
	      fprintf (stats_file, "\n");
	      fprintf (stats_file, "SMS profile-sum-max ");
	      fprintf (stats_file, HOST_WIDEST_INT_PRINT_DEC,
		       (HOST_WIDEST_INT) profile_info->sum_max);
	      fprintf (stats_file, "\n");
	    }
	}

      /* Make sure this is a doloop.  */
      if ( !(count_reg = doloop_register_get (tail)))
	continue;

      if (stats_file)
	fprintf (stats_file, "SMS doloop\n");

      e = bb->pred;
      if (e->src == bb)
	pre_header = e->pred_next->src;
      else
	pre_header = e->src;

      if ( !(count_init = const_iteration_count (count_reg, pre_header,
						 &loop_count)))
	continue;

      if (stats_file)
	fprintf (stats_file, "SMS const-doloop %d\n", loop_count);

      if (loop_count < SMS_MIN_LOOP_COUNT)
	continue;

      if (stats_file)
	fprintf (stats_file, "SMS const-iter-above-threshold\n");

      /* Don't handle BBs with calls or barriers, or !single_set insns.  */
      for (insn = head; insn != NEXT_INSN (tail); insn = NEXT_INSN (insn))
	if (GET_CODE (insn) == CALL_INSN
	    || GET_CODE (insn) == BARRIER
	    || (INSN_P (insn) && GET_CODE (insn) != JUMP_INSN
		&& !single_set (insn) && GET_CODE (PATTERN (insn)) != USE))
	  break;

      if (insn != NEXT_INSN (tail))
	{
	  if (stats_file)
	    {
	      if (GET_CODE (insn) == CALL_INSN)
		fprintf (stats_file, "SMS loop-with-call\n");
	      else if (GET_CODE (insn) == BARRIER)
		fprintf (stats_file, "SMS loop-with-barrier\n");
	      else
		fprintf (stats_file, "SMS loop-with-not-single-set\n");
	      print_rtl_single (stats_file, insn);
	    }

	  continue;
	}

      if (! (g = create_ddg (bb, 0)))
	continue;

      if (stats_file)
	fprintf (stats_file, "SMS built-ddg %d\n", g->num_nodes);

      node_order = (int *) xmalloc (sizeof (int) * g->num_nodes);

      if (dump_file)
	print_ddg (dump_file, g);
      if (vcg_dump_file)
	vcg_print_ddg (vcg_dump_file, g);

      /* Initilize the scheduler.  */
      current_sched_info = &sms_sched_info;
      sched_init (dump_file);

      mii = 1; /* Need to pass some estimate of mii.  */
      rec_mii = sms_order_nodes (g, mii, node_order);
      mii = MAX (res_MII (g), rec_mii);
      maxii = calculate_maxii (g);

      if (stats_file)
	fprintf (stats_file, "SMS iis %d %d %d (rec_mii, mii, maxii)\n",
		 rec_mii, mii, maxii);

      /* Place set_node_sched_params() after sms_order_nodes and before
	 sms_schedule_by_order, to copy over ASAP.  */
      set_node_sched_params (g);

      ps = sms_schedule_by_order (g, mii, maxii, node_order, dump_file);

      if (ps)
	stage_count = PS_STAGE_COUNT (ps);

      if (stage_count == 0 || stage_count > loop_count)
	{
	  if (dump_file)
	    fprintf (dump_file, "SMS failed... \n");
	  if (stats_file)
	    fprintf (stats_file, "SMS sched-failed %d\n", stage_count);
	}
      else
	{
	  if (stats_file)
	    {
	      fprintf (stats_file,
		       "SMS succeeded %d %d (with ii, sc)\n", ps->ii,
		       stage_count);
	      print_partial_schedule (ps, dump_file);
	      fprintf (dump_file,
		       "SMS Branch (%d) will be scheduled at cycle %d.\n",
		       g->closing_branch->cuid, PS_MIN_CYCLE (ps) - 1);
	    }

	  /* Set the stage boundaries. If the DDG is built with
	     closing_branch_deps, the closing_branch was scheduled and should
	     appear in the last (ii-1) row. Otherwise, we are free to
	     schedule the branch, and we let nodes that were scheduled at the
	     first PS_MIN_CYCLE cycle appear in the first row; this should
	     reduce stage_count to minimum.  */
	  normalize_sched_times (ps);
	  rotate_partial_schedule (ps, PS_MIN_CYCLE (ps));
	  set_columns_for_ps (ps);

	  permute_partial_schedule (ps, g->closing_branch->first_note);
	  generate_reg_moves (ps);
	  if (dump_file)
	    print_node_sched_params (dump_file, g->num_nodes);

	  /* Set new iteration count of loop kernel.  */
	  SET_SRC (single_set (count_init)) = GEN_INT (loop_count
						       - stage_count + 1);

	  /* Generate prolog and epilog.  */
	  generate_prolog_epilog (ps);
	}

      /* Release scheduler data.  */
      sched_finish ();

      free_partial_schedule (ps);
      free (node_sched_params);
      free (node_order);
      free_ddg (g);
    }
  if (stats_file)
    fclose (stats_file);
  if (vcg_dump_file)
    fclose (vcg_dump_file);
}

/* The SMS scheduling algorithm itself
   -----------------------------------
   Input: 'O' an ordered list of insns of a loop.
   Output: A scheduling of the loop - kernel, prolog, and epilogue.

   'Q' is the empty Set
   'PS' is the partial schedule; it holds the currently scheduled nodes with
	their cycle/slot.
   'PSP' previously scheduled predecessors.
   'PSS' previously scheduled successors.
   't(u)' the cycle where u is scheduled.
   'l(u)' is the latency of u.
   'd(v,u)' is the dependence distance from v to u.
   'ASAP(u)' the earliest time at which u could be scheduled as computed in
	     the node ordering phase.
   'check_hardware_resources_conflicts(u, PS, c)'
		run a trace around cycle/slot through DFA model
		to check resource conflicts involving instruction u
		at cycle c given the partial schedule PS.
   'add_to_partial_schedule_at_time(u, PS, c)'
		Add the node/instruction u to the partial schedule
		PS at time c.
   'calculate_register_pressure(PS)'
		Given a schedule of instructions, calculate the register
		pressure it implies. One implementation could be the
		maximum number of overlapping live ranges.
   'maxRP' The maximum allowed register pressure, it is usually derived from
	the number registers available in the hardware.

   1. II = MII.
   2. PS = empty list
   3. for each node u in O in pre-computed order
   4.   if (PSP(u) != Q && PSS(u) == Q) then
   5.     Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over v in PSP(u).
   6.     start = Early_start; end = Early_start + II - 1; step = 1
   11.  else if (PSP(u) == Q && PSS(u) != Q) then
   12.      Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over v in PSS(u).
   13.     start = Late_start; end = Late_start - II + 1; step = -1
   14.  else if (PSP(u) != Q && PSS(u) != Q) then
   15.     Early_start(u) = max ( t(v) + l(v) - d(v,u)*II ) over v in PSP(u).
   16.     Late_start(u) = min ( t(v) - l(v) + d(v,u)*II ) over v in PSS(u).
   17.     start = Early_start;
   18.     end = min(Early_start + II - 1 , Late_start);
   19.     step = 1
   20.     else "if (PSP(u) == Q && PSS(u) == Q)"
   21.	  start = ASAP(u); end = start + II - 1; step = 1
   22.  endif

   23.  success = false
   24.  for (c = start ; c != end ; c += step)
   25.     if check_hardware_resources_conflicts(u, PS, c) then
   26.       add_to_partial_schedule_at_time(u, PS, c)
   27.       success = true
   28.       break
   29.     endif
   30.  endfor
   31.  if (success == false) then
   32.    II = II + 1
   33.    if (II > maxII) then
   34.       finish - failed to schedule
   35.	 endif
   36.    goto 2.
   37.  endif
   38. endfor
   39. if (calculate_register_pressure(PS) > maxRP) then
   40.    goto 32.
   41. endif
   42. compute epilogue & prologue
   43. finish - succeeded to schedule
*/

/* A limit on the number of cycles that resource conflicts can span
   Todo: Should be provided by DFA, and be dependent on the type of insn
   scheduled. Currently set to 0 to save compile time.  */
#define DFA_HISTORY 0

static partial_schedule_ptr
sms_schedule_by_order (ddg_ptr g, int mii, int maxii, int *nodes_order,
		       FILE *dump_file)
{
  int ii = mii;
  int i, c, success;
  int try_again_with_larger_ii = 1;
  int num_nodes = g->num_nodes;
  ddg_edge_ptr e;
  int start, end, step; /* Place together into one struct?  */
  sbitmap sched_nodes = sbitmap_alloc (num_nodes);
  sbitmap psp = sbitmap_alloc (num_nodes);
  sbitmap pss = sbitmap_alloc (num_nodes);
  partial_schedule_ptr ps = create_partial_schedule (ii, g, DFA_HISTORY);

  while (try_again_with_larger_ii && ii < maxii)
    {
      if (dump_file)
	fprintf(dump_file, "Starting with ii=%d\n", ii);
      try_again_with_larger_ii = 0;
      sbitmap_zero (sched_nodes);

      for (i = 0; i<num_nodes; i++)
	{
	  int u = nodes_order[i];
	  ddg_node_ptr u_node = &g->nodes[u];
	  sbitmap u_node_preds = NODE_PREDECESSORS (u_node);
	  sbitmap u_node_succs = NODE_SUCCESSORS (u_node);
	  int psp_not_empty;
	  int pss_not_empty;
	  rtx insn = u_node->insn;

	  if (!INSN_P (insn))
	    continue;

	  if (GET_CODE (insn) == JUMP_INSN)
	    continue; /* Closing branch handled later.  */

	  /* 1. compute sched window for u (start, end, step).  */
	  sbitmap_zero (psp);
	  sbitmap_zero (pss);
	  psp_not_empty = sbitmap_a_and_b_cg (psp, u_node_preds, sched_nodes);
	  pss_not_empty = sbitmap_a_and_b_cg (pss, u_node_succs, sched_nodes);

	  if (psp_not_empty && !pss_not_empty)
	    {
	      int early_start = 0;

	      end = INT_MAX;
	      for (e=u_node->in; e!=0; e=e->next_in)
		{
		  ddg_node_ptr v_node = e->src;
		  if (TEST_BIT (sched_nodes, v_node->cuid))
		    {
		      early_start = MAX (early_start,
					 SCHED_TIME (v_node)
					 + e->latency - (e->distance * ii));
		      if (e->data_type == MEM_DEP)
			end = MIN (end, SCHED_TIME (v_node) + ii - 1);
		    }
		}
	      start = early_start;
	      end = MIN (end, early_start + ii);
	      step = 1;
	    }

	  else if (!psp_not_empty && pss_not_empty)
	    {
	      int late_start = INT_MAX;

	      end = INT_MIN;
	      for (e=u_node->out; e!=0; e=e->next_out)
		{
		  ddg_node_ptr v_node = e->dest;
		  if (TEST_BIT (sched_nodes, v_node->cuid))
		    {
		      late_start = MIN (late_start,
					SCHED_TIME (v_node) - e->latency
					+ (e->distance * ii));
		      if (e->data_type == MEM_DEP)
			end = MAX (end, SCHED_TIME (v_node) - ii + 1);
		    }
		}
	      start = late_start;
	      end = MAX (end, late_start - ii);
	      step = -1;
	    }

	  else if (psp_not_empty && pss_not_empty)
	    {
	      int early_start = 0;
	      int late_start = INT_MAX;

	      start = INT_MIN;
	      end = INT_MAX;
	      for (e=u_node->in; e!=0; e=e->next_in)
		{
		  ddg_node_ptr v_node = e->src;

		  if (TEST_BIT (sched_nodes, v_node->cuid))
		    {
		      early_start = MAX (early_start,
					 SCHED_TIME (v_node) + e->latency
					 - (e->distance * ii));
		      if (e->data_type == MEM_DEP)
			end = MIN (end, SCHED_TIME (v_node) + ii - 1);
		    }
		}
	      for (e=u_node->out; e!=0; e=e->next_out)
		{
		  ddg_node_ptr v_node = e->dest;

		  if (TEST_BIT (sched_nodes, v_node->cuid))
		    {
		      late_start = MIN (late_start,
					SCHED_TIME (v_node) - e->latency
					+ (e->distance * ii));
		      if (e->data_type == MEM_DEP)
			start = MAX (start, SCHED_TIME (v_node) - ii + 1);
		    }
		}
	      start = MAX (start, early_start);
	      end = MIN (end, MIN (early_start + ii, late_start + 1));
	      step = 1;
	    }
	  else /* psp is empty && pss is empty.  */
	    {
	      start = SCHED_ASAP (u_node);
	      end = start + ii;
	      step = 1;
	    }

	  /* 2. Try scheduling u in window.  */
	  if (dump_file)
	    fprintf(dump_file,
		    "Trying to schedule node %d in (%d .. %d) step %d\n",
		    u, start, end, step);

	  success = 0;
	  if ((step > 0 && start < end) ||  (step < 0 && start > end))
	    for (c = start; c != end; c += step)
	      {
		ps_insn_ptr psi = ps_add_node_check_conflicts (ps, u_node, c);

  		if (psi)
		  {
		    SCHED_TIME (u_node) = c;
		    SET_BIT (sched_nodes, u);
		    success = 1;
		    if (dump_file)
		      fprintf(dump_file, "Schedule in %d\n", c);
		    break;
		  }
	      }
	  if (!success)
	    {
	      /* Todo: try backtracking instead of immediately i++?  */
	      ii++;
	      try_again_with_larger_ii = 1;
	      reset_partial_schedule (ps, ii);
	      break;
	    }
	  /* Todo: if (success), check register pressure estimates.  */
	} /* Continue with next node.  */
    } /* While try_again_with_larger_ii.  */

  sbitmap_free (sched_nodes);
  sbitmap_free (psp);
  sbitmap_free (pss);

  if (ii >= maxii)
    {
      free_partial_schedule (ps);
      ps = NULL;
    }
  return ps;
}