DDG - Implementing Swing Modulo Scheduling in GCC (cont.)

[Mostafa Hagog <MUSTAFA at il dot ibm dot com>]

Following http://gcc.gnu.org/ml/gcc/2003-09/msg00954.html:

...
>Infrastructure requirements for implementing SMS in GCC
>-------------------------------------------------------
[snip]
>2. Building a dependance graph (for loops) with loop carried dependancies;
>   intra-loop dependancies could be based on the standard
>   LOG_LINKS/INSN_DEPEND structures. Loop carried dependancies
>   calculations must be added, with their associated distances (from
>   dependence.c?).
>   The following functionality must be implemented:
>   1. Identifying cycles (strongly connected components) in the
>      dependance graph.
>   2. Find the set of all predecessor [all successor] nodes for a given
>      set of nodes in the dependance graph.
>   3. Find all nodes that lie on some directed path between two strongly
>      connected subgraphs.
...

Here are the interfaces and implementation of the Data Dependence Graph
required above.

Data dependence information is collected in gcc during the scheduling
passes, and we plan to invoke SMS as part of the first scheduling pass.
Therefore, the dependence information collected for the scheduler can
serve SMS. However, SMS requires additional information, some of which
must be kept on the dependence edges. This requires a fundamental change
in the rtl LOG_LINKS.

Our solution is to build a new and different representation of the data
dependence information. The attached ddg.h and ddg.c files define and
implement this representation. It is based on a general graph of nodes
and edge structures, with basic information such as dependence distance
and latency of edges, as well as allowing algorithm-specific information
in the "data" union. The graph is built from the current LOG_LINKS
dependency information (ddg.c/build_deps()), although it can be easily
built from other representations if/when needed.
In addition the DDG calculates loop carried dependencies,
strongly-connected
components and their maximum recurrence length (e.g. to compute recMII).
We tried to make the DDG as generic as possible for potential use by other
algorithms or optimizations.

Comments are welcome.
Ayal & Mostafa.



ddg.h:
------

/* DDG - Data Dependence Graph - interface.  */

typedef struct ddg_node *ddg_node_ptr;
typedef struct ddg_edge *ddg_edge_ptr;
typedef struct ddg *ddg_ptr;
typedef struct ddg_scc *ddg_scc_ptr;
typedef struct ddg_all_sccs *ddg_all_sccs_ptr;

typedef enum {TRUE_DEP, OUTPUT_DEP, ANTI_DEP} dep_type;
typedef enum {REG_OR_MEM_DEP, REG_DEP, MEM_DEP, REG_AND_MEM_DEP}
             dep_data_type;

#define NODE_SUCCESSORS(x)  ((x)->successors)
#define NODE_PREDECESSORS(x)  ((x)->predecessors)

/* A structure that represents a node in the DDG.  */
struct ddg_node
{
  /* Each node has a number which is the order of the insn in the BB that
     this node represents.  */
  int num;

  /* The insn represented by the node.  */
  rtx insn;

  /* Incoming/Outgoing dependency edges.  */
  ddg_edge_ptr in;
  ddg_edge_ptr out;

  /* Each bit is set if the node is a successor/predecessor according to
     the node number.  */
  sbitmap successors;
  sbitmap predecessors;

  /* For general use by algorithms manipulating the ddg.  */
  union {
    int count;
    void *info;
  } data;
};

/* A structure that represents an edge in the DDG.  */
struct ddg_edge
{
  /* The source and destination nodes of the dependency edge.  */
  ddg_node_ptr src;
  ddg_node_ptr dest;

  /* Dependency type.  */
  dep_type type;

  /* REG or MEM dependency.  ??? Not implemented yet.  */
  dep_data_type data_type;

  /* Latency of the depedency.  */
  int latency;

  /* The distance: number of loop iterations the dependency crosses.  */
  int distance;

  /* The following two fields are used to form a linked list of the in/out
     going edges to/from each node.  */
  ddg_edge_ptr next_in;
  ddg_edge_ptr next_out;

  /* For general use by algorithms manipulating the ddg.  */
  union {
    int count;
    void *info;
  } data;
};

/* This structure holds the Data Dependence Graph for a basic block.  */
struct ddg
{
  /* The basic block for which this DDG is built.  */
  basic_block bb;

  /* Allow speculative movements when set.  */
  int speculative;

  /* Number of instructions in the basic block.  */
  int num_nodes;

  /* This array holds the nodes in the graph; it is indexed by the node
     number, which follows the order of the instructions in the BB.  */
  ddg_node_ptr nodes;

  /* The size of the allocated array for holding nodes.  Can be different
     from num_nodes because we pre-allocate memory for the virtual nodes
     created when unrolling the loop.  */
  int node_arr_size;

  /* Array and number of back-arcs in the DDG.  */
  ddg_edge_ptr *backarcs;
  int num_backarcs;
};


/* Holds information on an SCC (Strongly Connected Component) of the DDG.  */
struct ddg_scc
{
  /* A bitmap that represents the nodes of the DDG that are in the SCC.  */
  sbitmap nodes;

  /* The backarc edges in the SCC, and their number.  */
  ddg_edge_ptr *backarcs;
  int num_backarcs;

  /* The maximum of (total_latency/total_distance) over all cycles in the SCC.  */
  int recurrence_length;
};

/* This structure holds the SCCs of the DDG.  */
struct ddg_all_sccs
{
  /* Array that holds the SCCs in the DDG, and their number.  */
  ddg_scc_ptr *sccs;
  int num_sccs;

  ddg_ptr ddg;
};


ddg_ptr create_ddg (basic_block, int allow_speculative_moves);
void free_ddg (ddg_ptr);
void print_ddg (FILE *, ddg_ptr);

ddg_node_ptr get_node_number_by_insn (ddg_ptr, rtx);

ddg_edge_ptr create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest, dep_type,
                              dep_data_type, int latency, int distance);
void add_edge_to_ddg (ddg_ptr, ddg_edge_ptr);
void add_backarc_to_scc (ddg_scc_ptr, ddg_edge_ptr);
void print_ddg_edge (FILE *, ddg_edge_ptr);

void find_successors (sbitmap result, ddg_ptr, sbitmap);
void find_predecessors (sbitmap result, ddg_ptr, sbitmap);

ddg_all_sccs_ptr create_ddg_all_sccs (ddg_ptr);
void free_ddg_all_sccs (ddg_all_sccs_ptr);

int find_nodes_on_paths (sbitmap result, ddg_ptr, sbitmap from, sbitmap to);
int longest_simple_path (ddg_ptr, int from, int to, sbitmap via);


ddg.c:
------
/* DDG - Data Dependence Graph implementation.  */

#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 "sbitmap.h"

#include "ddg.h"


#define IS_ARTIFICIAL(x)   ((x)->data.info ? 1 : 0)
#define ART2ORIG(x)        ((x)->data.info)

enum edge_flag {NOT_IN_SCC, IN_SCC};

/* Forward declarations.  */
static ddg_node_ptr add_artificial_node_to_ddg (ddg_ptr, rtx, ddg_node_ptr);
static void add_backarc_edge_to_ddg (ddg_ptr, ddg_edge_ptr);
static void add_scc_to_ddg (ddg_all_sccs_ptr, ddg_scc_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 *
ddg_print_insn (rtx insn, int aligned)
{
  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 ddg_sched_info =
{
  NULL,
  NULL,
  NULL,
  NULL,
  NULL,
  ddg_print_insn,
  contributes_to_priority,
  compute_jump_reg_dependencies,
  NULL, NULL,
  NULL, NULL,
  0, 0, 0
};


/* The following three functions build the data dependence graph including
   loop-carried dependences, by first creating an artificial copy of the
   loop (by unrolling), then calculating intra-(extended)-block dependences,
   and finally generating ddg_edges for such dependneces and removing the
   artificial copy.  */

/* Unroll the loop, assuming it contains a single basic block, and
   add the insns of the new iteration as artificial nodes to the ddg.  */
static void
add_artificial_loop_copy_to_ddg (ddg_ptr g)
{
  int i, num_orig_nodes = g->num_nodes;
  rtx art_insn, first_art_insn, last_art_insn;
  /* The last insn before the jump out of the loop.  */
  rtx last_orig_insn = prev_nonnote_insn (g->bb->end);
  rtx next_last_orig_insn = NEXT_INSN (last_orig_insn);
  /* Prev_first_art_insn is the last insn in the original instruction chain;
     duplicated insns will start after this insn.  */
  rtx prev_first_art_insn;

  /* Unroll the single basic block loop, by duplicating the instructions
     (except for the latch jump) and chaining them after the last
     instruction of the loop.  */

  /* Avoid updating the boundaries of previous basic block.  The
     note is later deleted.  */
  prev_first_art_insn = emit_note (NOTE_INSN_DELETED);

  last_art_insn = get_last_insn (); /* I.e., prev_first_art_insn.  */

  /* Create copy at the end of INSN chain.  The chain will
     be repositioned later.  */
  for (i = 0; i < num_orig_nodes; i++)
    {
      ddg_node_ptr node = &g->nodes[i];
      if (GET_CODE (node->insn) == JUMP_INSN)
        /* This is the end of the basic block.  */
      break;

      duplicate_insn (node->insn);
      art_insn = get_last_insn ();
      if (art_insn == last_art_insn)
      continue;

      add_artificial_node_to_ddg (g, art_insn, node);
      last_art_insn = art_insn;
    }

  first_art_insn = NEXT_INSN (prev_first_art_insn);
  delete_insn (prev_first_art_insn);
  if (! first_art_insn)
    return;

  /* Connect the virutal unroll chain to the original BB insn chain.  */

  NEXT_INSN (PREV_INSN (first_art_insn)) = NEXT_INSN (last_art_insn);
  if (NEXT_INSN (last_art_insn) != NULL_RTX)
    PREV_INSN (NEXT_INSN (last_art_insn)) = PREV_INSN (first_art_insn);

  /* Our last_insn moved so update the global last_insn to what it was.  */
  set_last_insn (PREV_INSN (first_art_insn));

  NEXT_INSN (last_orig_insn) = first_art_insn;
  PREV_INSN (first_art_insn) = last_orig_insn;
  NEXT_INSN (last_art_insn) = next_last_orig_insn;
  PREV_INSN (next_last_orig_insn) = last_art_insn;
}

/* Delete the instructions of the artificial loop copy.  We assume that
   the artificial nodes are concentrated at the end of g->nodes array.  */
static void
remove_artificial_loop_copy_from_ddg (ddg_ptr g)
{
  int i;

  for (i = g->num_nodes - 1; i >= 0; i--)
    {
      ddg_node_ptr node = &g->nodes[i];
      if (! node->data.info)
        break;
      /* This is node is artificial.  */
      if (! INSN_DELETED_P (node->insn))
        delete_insn (node->insn);
    }
  g->num_nodes = i + 1;
}

/* Do Data Dependency analysis and connect the nodes in the DDG.
   We assume the loop has a single basic block, and unroll it once
   to compute loop carried dependecies.  */
static void
build_deps (ddg_ptr g)
{
  int i;
  /* Hold the dependency analysis state during the dependency calculations.  */
  struct deps tmp_deps;
  rtx head, tail, link;

  /* Unroll the loop to expose cross iteration dependecies.  */
  add_artificial_loop_copy_to_ddg (g);

  /* Initilize the scheduler.  */
  current_sched_info = &ddg_sched_info;
  sched_init (NULL);

  /* Build the dependence information, using the sched_analyze function.  */
  init_deps_global ();
  init_deps (&tmp_deps);

  /* Do the data dependence analysis for the given block.  */
  get_block_head_tail (g->bb->index, &head, &tail);
  sched_analyze (&tmp_deps, head, tail);

  /* Add dependences so that branches are scheduled to run last in their
     block.  */
  /* add_branch_dependences (head, tail); ??? static in sched-rgn.c */

  /* Create DDG edges according to LOG_LINKS.  */
  for (i = 0; i < g->num_nodes; i++)
    {
      ddg_node_ptr dest_node = &g->nodes[i];
      int dest_is_art;

      if (! INSN_P (dest_node->insn))
      continue;

      dest_is_art = IS_ARTIFICIAL (dest_node);

      for (link = LOG_LINKS (dest_node->insn); link; link = XEXP (link, 1))
        {
          ddg_edge_ptr e;
          int latency;
          ddg_node_ptr src_node = get_node_number_by_insn (g,
                                                           XEXP (link, 0));
          dep_type t = TRUE_DEP;

          /* We consider only orig--->art and art--->art dependencies.  */
          if (!src_node || IS_ARTIFICIAL (src_node))
            continue;

              add_forward_dependence (XEXP (link, 0), dest_node->insn,
                                  REG_NOTE_KIND (link));

          latency = insn_cost (dest_node->insn, link, XEXP (link, 0));

          if (REG_NOTE_KIND (link) == REG_DEP_ANTI)
            t = ANTI_DEP;
          else if (REG_NOTE_KIND (link) == REG_DEP_OUTPUT)
            t = OUTPUT_DEP;

          /* If dest is an artificial node, then the dependency crosses a
             backarc. Otherwise it is a regular (intra-loop) dependency.  */
          if (dest_is_art)
            {
            ddg_node_ptr orig_dest_node = ART2ORIG (dest_node);
            /* Every insn is output dependent on itself; ignore such deps.  */
              if (src_node != orig_dest_node || t != OUTPUT_DEP)
                {
                  e = create_ddg_edge (src_node, orig_dest_node, t,
                               REG_OR_MEM_DEP, latency, 1);
                  add_backarc_edge_to_ddg (g, e);
                }
            }
          else
            {
              e = create_ddg_edge (src_node, dest_node, t,
                                   REG_OR_MEM_DEP, latency, 0);
              add_edge_to_ddg (g, e);
            }
        }

    }

  remove_artificial_loop_copy_from_ddg (g);

  /* Free the INSN_LISTs.  */
  free_deps (&tmp_deps);

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

/* Given a basic block, create its DDG and return a pointer to a variable
   of ddg type that represents it.
   Initialize the ddg structure fields to the appropriate values.  */
ddg_ptr
create_ddg (basic_block bb, int allow_speculative_moves)
{
  ddg_ptr g;
  rtx insn;
  int i;
  int num_nodes = 0;

  g = (ddg_ptr) xmalloc (sizeof (struct ddg));
  memset (g, 0, sizeof (struct ddg));

  g->bb = bb;
  g->speculative = allow_speculative_moves;

  /* Count the number of insns in the BB.  */
  for (insn = bb->head; insn != NEXT_INSN (bb->end); insn = NEXT_INSN (insn))
    num_nodes++;
  g->num_nodes = num_nodes;

  /* Allocate the nodes array, and initialize the nodes.  */
  g->node_arr_size = num_nodes * 2; /* Twice to hold artificial copies.  */
  g->nodes = (ddg_node_ptr) xmalloc (sizeof (struct ddg_node)
                                     * g->node_arr_size);

  /* The "upper" num_nodes nodes are zeroed lazily.  */
  memset (g->nodes, 0, sizeof (struct ddg_node) * num_nodes);

  i = 0;
  for (insn = bb->head; insn != NEXT_INSN (bb->end); insn = NEXT_INSN (insn))
    {
      g->nodes[i].num = i;
      g->nodes[i].successors = sbitmap_alloc (num_nodes);
      sbitmap_zero (g->nodes[i].successors);
      g->nodes[i].predecessors = sbitmap_alloc (num_nodes);
      sbitmap_zero (g->nodes[i].predecessors);
      g->nodes[i++].insn = insn;
    }

  /* Build the data dependecy graph.  */
  build_deps (g);

  return g;
}

/* Free all the memory allocated for the DDG.  */
void
free_ddg (ddg_ptr g)
{
  int i;

  for (i = 0; i < g->num_nodes; i++)
    {
      ddg_edge_ptr e = g->nodes[i].out;
      while (e)
      {
        ddg_edge_ptr next = e->next_out;
        free (e);
        e = next;
      }
    }
  free (g->nodes);
  free (g);
}

void
print_ddg_edge (FILE *dump_file, ddg_edge_ptr e)
{
  char dep_c;

  switch (e->type) {
    case OUTPUT_DEP :
      dep_c = 'O';
      break;
    case ANTI_DEP   :
      dep_c = 'A';
      break;
    default:
      dep_c = 'T';
  }

  fprintf (dump_file, " [%d -(%c,%d,%d)-> %d] ", INSN_UID (e->src->insn),
           dep_c, e->latency, e->distance, INSN_UID (e->dest->insn));
}

void
print_ddg (FILE *dump_file, ddg_ptr g)
{
  int i;

  for (i = 0; i < g->num_nodes; i++)
    {
      ddg_edge_ptr e;
      print_rtl_single (dump_file, g->nodes[i].insn);
      fprintf (dump_file, "OUT ARCS: ");
      for (e = g->nodes[i].out; e; e = e->next_out)
        print_ddg_edge (dump_file, e);

      fprintf (dump_file, "\nIN ARCS: ");
      for (e = g->nodes[i].in; e; e = e->next_in)
        print_ddg_edge (dump_file, e);

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

/* Create an edge and initialize it with given values.  */
ddg_edge_ptr
create_ddg_edge (ddg_node_ptr src, ddg_node_ptr dest,
                 dep_type t, dep_data_type dt, int l, int d)
{
  ddg_edge_ptr e = (ddg_edge_ptr) xmalloc (sizeof (struct ddg_edge));

  e->src = src;
  e->dest = dest;
  e->type = t;
  e->data_type = dt;
  e->latency = l;
  e->distance = d;
  e->next_in = e->next_out = NULL;
  e->data.info = 0;
  return e;
}

/* Add the given edge to the in/out linked lists of the DDG nodes.  */
void
add_edge_to_ddg (ddg_ptr g, ddg_edge_ptr e)
{
  ddg_node_ptr src = e->src;
  ddg_node_ptr dest = e->dest;

  SET_BIT (src->successors, dest->num);
  SET_BIT (dest->predecessors, src->num);
  e->next_in = g->nodes[dest->num].in;
  g->nodes[dest->num].in = e;
  e->next_out = g->nodes[src->num].out;
  g->nodes[src->num].out = e;
}



/* Algorithm for computing the recurrence_length of an scc. We assume at first that
   cycles in the data dependence graph contain a single backarc. This simplifies
   the algorithm, and can be generalized later.  */
static void
set_recurrence_length (ddg_scc_ptr scc, ddg_ptr g)
{
  int j;
  int result = -1;

  for (j = 0; j < scc->num_backarcs; j++)
    {
      ddg_edge_ptr backarc = scc->backarcs[j];
      int length;
      int distance = backarc->distance;
      ddg_node_ptr src = backarc->dest;
      ddg_node_ptr dest = backarc->src;

      length = longest_simple_path (g, src->num, dest->num, scc->nodes);
      if (length < 0 )
        {
          fprintf (stderr, "Found backarc not on simple cycle in SCC.\n");
          continue;
        }
      length += backarc->latency;
      result = MAX (result, (length / distance));
    }
  scc->recurrence_length = result;
}

/* Create a new SCC given the set of its nodes.  Compute its recurrence_length,
   and mark edges that belong to this scc as IN_SCC.  */
static ddg_scc_ptr
create_scc (ddg_ptr g, sbitmap nodes)
{
  ddg_scc_ptr scc;
  int u;

  scc = (ddg_scc_ptr) xmalloc (sizeof (struct ddg_scc));
  scc->backarcs = NULL;
  scc->num_backarcs = 0;
  scc->nodes = sbitmap_alloc (g->num_nodes);
  sbitmap_copy (scc->nodes, nodes);

  /* Mark the backarcs that belong to this SCC.  */
  EXECUTE_IF_SET_IN_SBITMAP (nodes, 0, u,
    {
      ddg_edge_ptr e;
      ddg_node_ptr n = &g->nodes[u];

      for (e = n->out; e; e = e->next_out)
        if (TEST_BIT (nodes, e->dest->num))
          {
            e->data.count = IN_SCC;
            if (e->distance > 0)
              add_backarc_to_scc (scc, e);

          }

    });

  set_recurrence_length (scc, g);
  return scc;
}

/* Cleans the memory allocation of a given SCC.  */
static void
free_scc (ddg_scc_ptr scc)
{
  if (!scc)
    return;
  sbitmap_free (scc->nodes);
  if (scc->num_backarcs > 0)
    free (scc->backarcs);
  free (scc);
}


/* Add a given edge known to be a backarc to the given DDG.  */
void
add_backarc_edge_to_ddg (ddg_ptr g, ddg_edge_ptr e)
{
  add_edge_to_ddg (g, e);
  if (g->num_backarcs == 0)
    g->backarcs = (ddg_edge_ptr *) xmalloc (sizeof (ddg_edge_ptr));
  else
    g->backarcs = (ddg_edge_ptr *) xrealloc (g->backarcs,
                                             (g->num_backarcs + 1)
                                             * sizeof (ddg_edge_ptr));
  g->backarcs[g->num_backarcs++] = e;
}

/* Add backarc to an SCC.  */
void
add_backarc_to_scc (ddg_scc_ptr scc, ddg_edge_ptr e)
{
  if (scc->num_backarcs == 0)
    scc->backarcs = (ddg_edge_ptr *) xmalloc (sizeof (ddg_edge_ptr));
  else
    scc->backarcs = (ddg_edge_ptr *) xrealloc (scc->backarcs,
                                               (scc->num_backarcs + 1)
                                               * sizeof (ddg_edge_ptr));
  scc->backarcs[scc->num_backarcs++] = e;
}

/* Add the given SCC to the DDG.  */
static void
add_scc_to_ddg (ddg_all_sccs_ptr g, ddg_scc_ptr scc)
{
  if (g->num_sccs == 0)
    g->sccs = (ddg_scc_ptr *) xmalloc (sizeof (ddg_scc_ptr));
  else
    g->sccs = (ddg_scc_ptr *) xrealloc (g->sccs,
                                        (g->num_sccs +1)
                                        * sizeof (ddg_scc_ptr));
  g->sccs[g->num_sccs++] = scc;
}

/* Create an artificial node and add it as the last node of the DDG.  */
ddg_node_ptr
add_artificial_node_to_ddg (ddg_ptr g, rtx art_insn, ddg_node_ptr orig_node)
{
  ddg_node_ptr new_art_node;

  if (g->num_nodes == 0)
    return NULL;
  if (g->num_nodes == g->node_arr_size)
    abort ();

  new_art_node = &g->nodes[g->num_nodes];
  memset (new_art_node, 0, sizeof (struct ddg_node));
  new_art_node->num = g->num_nodes++;
  new_art_node->insn = art_insn;
  new_art_node->data.info = orig_node;
  return new_art_node;
}

/* Given the instruction INSN return the node number that represents it.  */
ddg_node_ptr
get_node_number_by_insn (ddg_ptr g, rtx insn)
{
  int i;

  for (i = 0; i < g->num_nodes; i++)
    if (insn == g->nodes[i].insn)
      return &g->nodes[i];
  return NULL;
}

/* Given a set OPS of nodes in the DDG, find
   the set of their successors which are not in OPS, and set their
   bits in SUCC. Leaves the other bits in SUCC unchanged.  */
void
find_successors (sbitmap succ, ddg_ptr g, sbitmap ops)
{
  int i;

  EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
    {
      sbitmap node_succ = NODE_SUCCESSORS (&g->nodes[i]);
      sbitmap_a_or_b (succ, succ, node_succ);
    });

  /* We want those that are not in ops.  */
  sbitmap_difference (succ, succ, ops);
}

/* Given a set OPS of nodes in the DDG, find
   the set of their predecessors which are not in OPS, and set their
   bits in PREDS. Leaves the other bits in PREDS unchanged.  */
void
find_predecessors (sbitmap preds, ddg_ptr g, sbitmap ops)
{
  int i;

  EXECUTE_IF_SET_IN_SBITMAP (ops, 0, i,
    {
      const sbitmap node_preds = NODE_PREDECESSORS (&g->nodes[i]);
      sbitmap_a_or_b (preds, preds, node_preds);
    });

  /* We want those that are not in ops.  */
  sbitmap_difference (preds, preds, ops);
}

/* Compare function to be passed to qsort to order the
   backarcs in descending recMII order.  */
static int
compare_sccs (ddg_scc_ptr s1, ddg_scc_ptr s2)
{
  return (s2->recurrence_length - s1->recurrence_length);
}

/* Order the backarcs in descending recMII order using compare_sccs.  */
static void
order_sccs (ddg_all_sccs_ptr g)
{
  qsort (g->sccs, g->num_sccs, sizeof (ddg_scc_ptr),
         (int (*) (const void *, const void *)) compare_sccs);
}

/* Perform the Strongly Connected Components decomposing algorithm on the
   DDG and return DDG_ALL_SCCS structure that contains them.  */
ddg_all_sccs_ptr
create_ddg_all_sccs (ddg_ptr g)
{
  int i;
  int num_nodes = g->num_nodes;
  sbitmap from = sbitmap_alloc (num_nodes);
  sbitmap to = sbitmap_alloc (num_nodes);
  sbitmap scc_nodes = sbitmap_alloc (num_nodes);
  ddg_all_sccs_ptr sccs = (ddg_all_sccs_ptr)
                          xmalloc (sizeof (struct ddg_all_sccs));

  for (i = 0; i < g->num_backarcs; i++)
    {
      ddg_scc_ptr  scc;
      ddg_edge_ptr backarc = g->backarcs[i];
      ddg_node_ptr src = backarc->src;
      ddg_node_ptr dest = backarc->dest;

      /* If the backarc already belongs to an SCC, continue.  */
      if (backarc->data.count == IN_SCC)
        continue;

      sbitmap_zero (from);
      sbitmap_zero (to);
      SET_BIT (from, dest->num);
      SET_BIT (to, src->num);

      if (find_nodes_on_paths (scc_nodes, g, from, to))
        {
          scc = create_scc (g, scc_nodes);
          add_scc_to_ddg (sccs, scc);
        }
    }
  order_sccs (sccs);
  return sccs;
}

/* Frees the memory allocated for all SCCs of the DDG, but keeps the DDG.  */
void
free_ddg_all_sccs (ddg_all_sccs_ptr all_sccs)
{
  int i;

  for (i = 0; i < all_sccs->num_sccs; i++)
    free_scc (all_sccs->sccs[i]);

  free (all_sccs);
}


/* Given FROM - a bitmap of source nodes - and TO - a bitmap of destination
   nodes - find all nodes that lie on paths from FROM to TO (not excluding
   nodes from FROM and TO).  Return non zero if nodes exist.  */
int
find_nodes_on_paths (sbitmap result, ddg_ptr g, sbitmap from, sbitmap to)
{
  int change, u;
  int num_nodes = g->num_nodes;
  sbitmap workset = sbitmap_alloc (num_nodes);
  sbitmap reachable_from = sbitmap_alloc (num_nodes);
  sbitmap reach_to = sbitmap_alloc (num_nodes);
  sbitmap tmp = sbitmap_alloc (num_nodes);

  sbitmap_copy (reachable_from, from);
  sbitmap_copy (tmp, from);

  change = 1;
  while (change)
    {
      change = 0;
      sbitmap_copy (workset, tmp);
      sbitmap_zero (tmp);
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
      {
          ddg_edge_ptr e;
          ddg_node_ptr u_node = &g->nodes[u];

        for (e = u_node->out; e != (ddg_edge_ptr) 0; e = e->next_out)
          {
            ddg_node_ptr v_node = e->dest;
              int v = v_node->num;

            if (!TEST_BIT (reachable_from, v))
              {
                SET_BIT (reachable_from, v);
                SET_BIT (tmp, v);
              change = 1;
              }
          }
        });
    }

  sbitmap_copy (reach_to, to);
  sbitmap_copy (tmp, to);

  change = 1;
  while (change)
    {
      change = 0;
      sbitmap_copy (workset, tmp);
      sbitmap_zero (tmp);
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
      {
          ddg_edge_ptr e;
        ddg_node_ptr u_node = &g->nodes[u];

        for (e = u_node->in; e != (ddg_edge_ptr) 0; e = e->next_in)
          {
            ddg_node_ptr v_node = e->src;
              int v = v_node->num;

            if (!TEST_BIT (reach_to, v))
              {
                SET_BIT (reach_to, v);
                SET_BIT (tmp, v);
              change = 1;
              }
          }
        });
    }

  return sbitmap_a_and_b_cg (result, reachable_from, reach_to);
}

/* Find the length of a longest path from SRC to DEST in G,
   going only through NODES, and disregarding backarcs.  */
int
longest_simple_path (struct ddg * g, int src, int dest, sbitmap nodes)
{
  int i;
  int v, u;
  struct ddg_edge * e;
  int change = 1;
  int result;
  int num_nodes = g->num_nodes;
  sbitmap workset = sbitmap_alloc (num_nodes);
  sbitmap tmp = sbitmap_alloc (num_nodes);


  /* Data will hold the distance of the longest path found so far from
     src to each node.  Initialize to less than minimum (-1).  */
  for (i=0; i<g->num_nodes; i++)
    g->nodes[i].data.count = -1;
  g->nodes[src].data.count = 0;

  sbitmap_zero (tmp);
  SET_BIT (tmp, src);

  while (change)
    {
      change = 0;
      sbitmap_copy (workset, tmp);
      sbitmap_zero (tmp);
      EXECUTE_IF_SET_IN_SBITMAP (workset, 0, u,
      {
        ddg_node_ptr u_node = &g->nodes[u];
        for (e = u_node->out; e; e = e->next_out)
          {
            ddg_node_ptr v_node = e->dest;
            v = v_node->num;
            if (TEST_BIT (nodes, v)
                && (e->distance == 0)
                && (v_node->data.count < u_node->data.count + e->latency))
              {
                v_node->data.count = u_node->data.count + e->latency;
                SET_BIT (tmp, v);
              change = 1;
              }
          }
        });
    }
  result = g->nodes[dest].data.count;
  return result;
}