/* Algorithm for ordering the nodes of a DDG for modulo scheduling.
   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 "recog.h"
#include "sched-int.h"
#include "target.h"
#include "cfglayout.h"
#include "cfgloop.h"
#include "sbitmap.h"
#include "ddg.h"

#define ORDER_PARAMS(x) ((struct node_order_params *) (x)->aux.info)
#define ASAP(x) (ORDER_PARAMS ((x))->asap)
#define ALAP(x) (ORDER_PARAMS ((x))->alap)
#define HEIGHT(x) (ORDER_PARAMS ((x))->height)
#define MOB(x) (ALAP ((x)) - ASAP ((x)))
#define DEPTH(x) (ASAP ((x)))

typedef struct node_order_params * nopa;

int sms_order_nodes (ddg_ptr, int mii, int * result);
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 mii);
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);

enum sms_direction {BOTTOMUP, TOPDOWN};

struct node_order_params
{
  int asap;
  int alap;
  int height;
};

/* Check if NODE_ORDER contains a permutation of 0 .. NUM_NODES-1.  */
static void
check_nodes_order (int *node_order, int num_nodes)
{
  int i;
  sbitmap tmp = sbitmap_alloc (num_nodes);

  sbitmap_zero (tmp);

  for (i=0; i < num_nodes; i++)
    {
      int u = node_order[i];

      if (u >= num_nodes || u < 0 || TEST_BIT (tmp, u))
	abort ();

      SET_BIT (tmp, u);
    }

  sbitmap_free (tmp);
}

/* Order the nodes of G for scheduling and pass the result in
   NODE_ORDER.  Also set aux.count of each node to ASAP.
   Return the recMII for the given DDG.  */
int
sms_order_nodes (ddg_ptr g, int mii, int * node_order)
{
  int i;
  int rec_mii = 0;
  ddg_all_sccs_ptr sccs = create_ddg_all_sccs (g);

  nopa nops = calculate_order_params (g, mii);

  order_nodes_of_sccs (sccs, node_order);

  if (sccs->num_sccs > 0)
    /* First SCC has the largest recurrence_length.  */
    rec_mii = sccs->sccs[0]->recurrence_length;

  /* Save ASAP before destroying node_order_params.  */
  for (i=0; i < g->num_nodes; i++)
    {
      ddg_node_ptr v = &g->nodes[i];
      v->aux.count = ASAP (v);
    }

  free (nops);
  free_ddg_all_sccs (sccs);
  check_nodes_order (node_order, g->num_nodes);

  return rec_mii;
}

static void
order_nodes_of_sccs (ddg_all_sccs_ptr all_sccs, int * node_order)
{
  int i, pos = 0;
  ddg_ptr g = all_sccs->ddg;
  int num_nodes = g->num_nodes;
  sbitmap prev_sccs = sbitmap_alloc (num_nodes);
  sbitmap on_path = sbitmap_alloc (num_nodes);
  sbitmap tmp = sbitmap_alloc (num_nodes);
  sbitmap ones = sbitmap_alloc (num_nodes);

  sbitmap_zero (prev_sccs);
  sbitmap_ones (ones);

  /* Perfrom the node ordering starting from the SCC with the highest recMII.
     For each SCC order the nodes according to their ASAP/ALAP etc.  */
  for (i = 0; i < all_sccs->num_sccs; i++)
    {
      ddg_scc_ptr scc = all_sccs->sccs[i];

      /* Add nodes on paths from previous SCCs to the current SCC.  */
      find_nodes_on_paths (on_path, g, prev_sccs, scc->nodes);
      sbitmap_a_or_b (tmp, scc->nodes, on_path);

      /* Add nodes on paths from the current SCC to previous SCCs.  */
      find_nodes_on_paths (on_path, g, scc->nodes, prev_sccs);
      sbitmap_a_or_b (tmp, tmp, on_path);

      /* Remove nodes of previous SCCs from current extended SCC.  */
      sbitmap_difference (tmp, tmp, prev_sccs);

      pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
      /* 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.  */
  while ( pos < g->num_nodes)
    {
      sbitmap_difference (tmp, ones, prev_sccs);
      pos = order_nodes_in_scc (g, prev_sccs, tmp, node_order, pos);
    }
  sbitmap_free (prev_sccs);
  sbitmap_free (on_path);
  sbitmap_free (tmp);
  sbitmap_free (ones);
}

/* MII needed if we consider backarcs (not on recursive cycles).  */
static struct node_order_params *
calculate_order_params (struct ddg * g, int mii ATTRIBUTE_UNUSED)
{
  int u;
  int max_asap;
  int num_nodes = g->num_nodes;
  ddg_edge_ptr e;
  /* Allocate a place to hold ordering params for each node in the DDG. */
  nopa node_order_params_arr;

  /* Initialize of ASAP/ALAP/HEIGHT to zero.  */
  node_order_params_arr = (nopa) xcalloc (num_nodes,
					  sizeof (struct node_order_params));

  /* Set the aux pointer of each node to point to its order_params strcture.  */
  for (u = 0; u < num_nodes; u++)
    g->nodes[u].aux.info = &node_order_params_arr[u];

  /* disregarding a backarcs from each recursive cycle to obtain a DAG,
     calculate ASAP, ALAP, mobility, distance, and height for each node
     in the dependance (direct acyclic) graph.  */

  /* We assume that the nodes in the array are in topological order.  */

  max_asap = 0;
  for (u=0; u<num_nodes; u++)
    {
      ddg_node_ptr u_node = &g->nodes[u];

      ASAP (u_node) = 0;
      for (e = u_node->in; e; e = e->next_in)
	if (e->distance == 0)
	  ASAP (u_node) = MAX (ASAP (u_node),
			       ASAP (e->src) + e->latency);
      max_asap = MAX (max_asap, ASAP (u_node));
    }

  for (u=num_nodes-1; u>-1; u--)
    {
      ddg_node_ptr u_node = &g->nodes[u];

      ALAP (u_node) = max_asap;
      HEIGHT (u_node) = 0;
      for (e = u_node->out; e; e = e->next_out)
	if (e->distance == 0)
	  {
	    ALAP (u_node) = MIN (ALAP (u_node),
				 ALAP (e->dest) - e->latency);
	    HEIGHT (u_node) = MAX (HEIGHT (u_node),
				   HEIGHT (e->dest) + e->latency);
	  }
    }

  return node_order_params_arr;
}

static int
find_max_asap (ddg_ptr g, sbitmap nodes)
{
  int u;
  int max_asap = -1;
  int result = -1;

  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
    {
      ddg_node_ptr u_node = &g->nodes[u];

      if (max_asap < ASAP (u_node))
	{
	  max_asap = ASAP (u_node);
	  result = u;
	}
    });
  return result;
}

static int
find_max_hv_min_mob (ddg_ptr g, sbitmap nodes)
{
  int u;
  int max_hv = -1;
  int min_mob = INT_MAX;
  int result = -1;

  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
    {
      ddg_node_ptr u_node = &g->nodes[u];

      if (max_hv < HEIGHT (u_node))
	{
	  max_hv = HEIGHT (u_node);
	  min_mob = MOB (u_node);
	  result = u;
	}
      else if ((max_hv == HEIGHT (u_node))
	       && (min_mob > MOB (u_node)))
	{
	  min_mob = MOB (u_node);
	  result = u;
	}
    });
  return result;
}

static int
find_max_dv_min_mob (ddg_ptr g, sbitmap nodes)
{
  int u;
  int max_dv = -1;
  int min_mob = INT_MAX;
  int result = -1;

  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
    {
      ddg_node_ptr u_node = &g->nodes[u];

      if (max_dv < DEPTH (u_node))
	{
	  max_dv = DEPTH (u_node);
	  min_mob = MOB (u_node);
	  result = u;
	}
      else if ((max_dv == DEPTH (u_node))
	       && (min_mob > MOB (u_node)))
	{
	  min_mob = MOB (u_node);
	  result = u;
	}
    });
  return result;
}

/* 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.  */
static int
order_nodes_in_scc (struct ddg * g, sbitmap nodes_ordered, sbitmap scc,
    int * node_order, int pos)
{
  enum sms_direction dir;
  int num_nodes = g->num_nodes;
  sbitmap workset = sbitmap_alloc (num_nodes);
  sbitmap tmp = sbitmap_alloc (num_nodes);
  sbitmap zero_bitmap = sbitmap_alloc (num_nodes);
  sbitmap predecessors = sbitmap_alloc (num_nodes);
  sbitmap successors = sbitmap_alloc (num_nodes);

  sbitmap_zero (predecessors);
  find_predecessors (predecessors, g, nodes_ordered);

  sbitmap_zero (successors);
  find_successors (successors, g, nodes_ordered);

  sbitmap_zero (tmp);
  if (sbitmap_a_and_b_cg (tmp, predecessors, scc))
    {
      sbitmap_copy (workset, tmp);
      dir = BOTTOMUP;
    }
  else if (sbitmap_a_and_b_cg (tmp, successors, scc))
    {
      sbitmap_copy (workset, tmp);
      dir = TOPDOWN;
    }
  else
    {
      int u;
      sbitmap_zero (workset);
      if ((u = find_max_asap (g, scc)) >= 0)
	SET_BIT (workset, u);
      dir = BOTTOMUP;
    }

  sbitmap_zero (zero_bitmap);
  while (!sbitmap_equal (workset, zero_bitmap))
    {
      int v;
      ddg_node_ptr v_node;
      sbitmap v_node_preds;
      sbitmap v_node_succs;

      if (dir == TOPDOWN)
	{
	  while (!sbitmap_equal (workset, zero_bitmap))
	    {
	      v = find_max_hv_min_mob (g, workset);
	      v_node = &g->nodes[v];
	      node_order[pos++] = v;
	      v_node_succs = NODE_SUCCESSORS (v_node);
	      sbitmap_a_and_b (tmp, v_node_succs, scc);
	      /* Don't consider the already ordered successors again.  */
	      sbitmap_difference (tmp, tmp, nodes_ordered);
	      sbitmap_a_or_b (workset, workset, tmp);
	      RESET_BIT (workset, v);
	      SET_BIT (nodes_ordered, v);
	    }
	  dir = BOTTOMUP;
	  sbitmap_zero (predecessors);
	  find_predecessors (predecessors, g, nodes_ordered);
	  sbitmap_a_and_b (workset, predecessors, scc);
	}
      else
	{
	  while (!sbitmap_equal (workset, zero_bitmap))
	    {
	      v = find_max_dv_min_mob (g, workset);
	      v_node = &g->nodes[v];
	      node_order[pos++] = v;
	      v_node_preds = NODE_PREDECESSORS (v_node);
	      sbitmap_a_and_b (tmp, v_node_preds, scc);
	      /* Don't consider the already ordered predecessors again.  */
	      sbitmap_difference (tmp, tmp, nodes_ordered);
	      sbitmap_a_or_b (workset, workset, tmp);
	      RESET_BIT (workset, v);
	      SET_BIT (nodes_ordered, v);
	    }
	  dir = TOPDOWN;
	  sbitmap_zero (successors);
	  find_successors (successors, g, nodes_ordered);
	  sbitmap_a_and_b (workset, successors, scc);
	}
    }
  sbitmap_free (tmp);
  sbitmap_free (workset);
  sbitmap_free (zero_bitmap);
  sbitmap_free (predecessors);
  sbitmap_free (successors);
  return pos;
}