osprey/kg++fe/gnu/dependence.c

Go to the documentation of this file.

/* Analyze loop dependencies
   Copyright (C) 2000, 2002 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.  */

/* References:
   Practical Dependence Testing, Goff, Kennedy, Tseng, PLDI, 1991
   High Performance Compilers for Parallel Computing, Wolfe
*/

#include "config.h"
#include "system.h"

#include "rtl.h"
#include "expr.h"
#include "tree.h"
#include "c-common.h"
#include "flags.h"
#include "varray.h"

#define MAX_SUBSCRIPTS 13

/*
   We perform the following steps:

   Build the data structures def_use_chain, loop_chain, and induction_chain.

   Determine if a loop index is a normalized induction variable.
   A loop is currently considered to be a for loop having an index set to an
   initial value, conditional check of the index, and increment/decrement of
   the index.

   Determine the distance and direction vectors.  Both are two dimensioned
   arrays where the first dimension represents a loop and the second
   dimension represents a subscript.  Dependencies are actually per loop, not
   per subscript.  So for:
   for (i = 0; i < 10; i++)
       for (j = 0; j < 10; j++)
           array [i][j] = array[i][j-1]
   We find the dependencies: loop1/sub_i, loop1/sub_j, loop2/sub_i, loop2/sub_j
   and then intersect loop1/sub_i V loop2/sub_i and loop1/sub_i V loop2/sub_j
   We determine the type of dependence, which determines which test we use.
   We then try to refine the type of dependence we have and add the
   dependence to the dep_chain
*/

enum dependence_type {dt_flow, dt_anti, dt_output, dt_none};
#if 0
static const char *const dependence_string [] = {"flow", "anti", "output", "none"};
#endif
enum direction_type {lt, le, eq, gt, ge, star, independent, undef};
#if 0
static const char *const direction_string [] = {"<", "<=", "=", ">", ">=", "*",
             "INDEPENDENT", "UNDEFINED"};
#endif
enum def_use_type {def, use, init_def_use};

enum du_status_type {seen, unseen};

enum loop_status_type {normal, unnormal};

enum complexity_type {ziv, strong_siv, weak_siv, weak_zero_siv,
          weak_crossing_siv, miv};

/* Given a def/use one can chase the next chain to follow the def/use
   for that variable.  Alternately one can sequentially follow each
   element of def_use_chain.  */

typedef struct def_use
{
  /* outermost loop */
  tree outer_loop;
  /* loop containing this def/use */
  tree containing_loop;
  /* this expression */
  tree expression;
  /* our name */
  const char *variable;
  /* def or use */
  enum def_use_type type;
  /* status flags */
  enum du_status_type status;
  /* next def/use for this same name */
  struct def_use *next;
  /* dependencies for this def */
  struct dependence *dep;
} def_use;

/* Given a loop* one can chase the next_nest chain to follow the nested
   loops for that loop.  Alternately one can sequentially follow each
   element of loop_chain and check outer_loop to get all loops
   contained within a certain loop.  */

typedef struct loop
{
  /* outermost loop containing this loop */
  tree outer_loop;
  /* this loop */
  tree containing_loop;
  /* nest level for this loop */
  int  depth;
  /* can loop be normalized? */
  enum loop_status_type status;
  /* loop* for loop contained in this loop */
  struct loop *next_nest;
  /* induction variables for this loop.  Currently only the index variable.  */
  struct induction *ind;
} loop;

/* Pointed to by loop. One per induction variable.  */

typedef struct induction
{
  /* our name */
  const char *variable;
  /* increment.  Currently only +1 or -1 */
  int  increment;
  /* lower bound */
  int  low_bound;
  /* upper bound */
  int  high_bound;
  /* next induction variable for this loop.  Currently null.  */
  struct induction *next;
} induction;

/* Pointed to by def/use.  One per dependence.  */

typedef struct dependence
{
  tree source;
  tree destination;
  enum dependence_type dependence;
  enum direction_type direction[MAX_SUBSCRIPTS];
  int distance[MAX_SUBSCRIPTS];
  struct dependence *next;
} dependence;
  
/* subscripts are represented by an array of these.  Each reflects one
   X * i + Y term, where X and Y are constants.  */

typedef struct subscript
{
  /* ordinal subscript number */
  int position;
  /* X in X * i + Y */
  int coefficient;
  /* Y in X * i + Y */
  int offset;
  /* our name */
  const char *variable;
  /* next subscript term.  Currently null.  */
  struct subscript *next;
} subscript;

/* Remember the destination the front end encountered.  */

static tree dest_to_remember;

/* Chain for def_use */
static varray_type def_use_chain;

/* Chain for dependence */
static varray_type dep_chain;

/* Chain for loop */
static varray_type loop_chain;

/* Chain for induction */
static varray_type induction_chain;

void init_dependence_analysis PARAMS ((tree));
static void build_def_use PARAMS ((tree, enum def_use_type));
static loop* add_loop PARAMS ((tree, tree, int));
static int find_induction_variable PARAMS ((tree, tree, tree, loop*));
static int get_low_bound PARAMS ((tree, const char*));
static int have_induction_variable PARAMS ((tree, const char*));
static void link_loops PARAMS ((void));
static void get_node_dependence PARAMS ((void));
static void check_node_dependence PARAMS ((def_use*));
static int get_coefficients PARAMS ((def_use*, subscript[]));
static int get_one_coefficient PARAMS ((tree, subscript*, def_use*, enum tree_code*));
static void normalize_coefficients PARAMS ((subscript[], loop*, int));
static void classify_dependence PARAMS ((subscript[], subscript[],
         enum complexity_type[], int*, int));
static void ziv_test PARAMS ((subscript[], subscript[],
            enum direction_type[][MAX_SUBSCRIPTS],
            int[][MAX_SUBSCRIPTS], loop*, int));
static void siv_test PARAMS ((subscript[], subscript[],
            enum direction_type[][MAX_SUBSCRIPTS],
            int[][MAX_SUBSCRIPTS], loop*, int));
static int check_subscript_induction PARAMS ((subscript*, subscript*, loop*));
static void gcd_test PARAMS ((subscript[], subscript[], enum
            direction_type[][MAX_SUBSCRIPTS],
            int[][MAX_SUBSCRIPTS], loop*, int));
static int find_gcd PARAMS ((int, int));
static void merge_dependencies PARAMS ((enum direction_type[][MAX_SUBSCRIPTS],
          int[][MAX_SUBSCRIPTS], int, int));
static void dump_array_ref PARAMS ((tree));
#if 0
static void dump_one_node PARAMS ((def_use*, varray_type*));
static void dump_node_dependence PARAMS ((void));
#endif
int search_dependence PARAMS ((tree));
void remember_dest_for_dependence PARAMS ((tree));
int have_dependence_p PARAMS ((rtx, rtx, enum direction_type[], int[]));
void end_dependence_analysis PARAMS ((void));

/* Build dependence chain 'dep_chain', which is used by have_dependence_p,
   for the function given by EXP.  */

void
init_dependence_analysis (exp)
     tree exp;
{
  def_use *du_ptr;

  VARRAY_GENERIC_PTR_INIT (def_use_chain, 50, "def_use_chain");
  VARRAY_GENERIC_PTR_INIT (dep_chain, 50, "dep_chain");
  VARRAY_GENERIC_PTR_INIT (loop_chain, 50, "loop_chain");
  VARRAY_GENERIC_PTR_INIT (induction_chain, 50, "induction_chain");

  build_def_use (exp, init_def_use);

  link_loops ();

  get_node_dependence ();

  /* dump_node_dependence (&def_use_chain);*/

  for (du_ptr = VARRAY_TOP (def_use_chain, generic);
       VARRAY_POP (def_use_chain);
       du_ptr = VARRAY_TOP (def_use_chain, generic))
    {
      free (du_ptr);
    }

  VARRAY_FREE (def_use_chain);
  VARRAY_FREE (loop_chain);
  VARRAY_FREE (induction_chain);
}

/* Build ARRAY_REF def/use info 'def_use_chain' starting at EXP which is a def
   or use DU_TYPE */ 

static void
build_def_use (exp, du_type)
     tree exp;
     enum def_use_type du_type;
{
  static tree outer_loop;
  static int nloop;
  static tree current_loop;
  static int du_idx;
  static loop *loop_def;
  tree node = exp;
  tree array_ref;
  def_use *du_ptr;

  if (du_type == init_def_use)
    {
      outer_loop = 0;
      nloop = 0;
      du_idx = 0;
    }
  
  while (node)
    switch (TREE_CODE (node))
      {
      case COMPOUND_STMT:
  node = TREE_OPERAND (node, 0);
  break;
      case TREE_LIST:
  build_def_use (TREE_VALUE (node), 0);
  node = TREE_CHAIN (node);
  break;
      case CALL_EXPR:
  node = TREE_CHAIN (node);
  break;
      case FOR_STMT:
  if (! nloop) outer_loop = node;
  nloop++;
  current_loop = node;
  loop_def = add_loop (node, outer_loop, nloop);
  if (find_induction_variable (TREE_OPERAND (node, 0),
             TREE_OPERAND (node, 1),
             TREE_OPERAND (node, 2), loop_def)
      == 0)
    loop_def->status = unnormal;
    
  build_def_use (TREE_OPERAND (node, 3), 0);
  nloop--;
  current_loop = 0;
  node = TREE_CHAIN (node);
  break;
      case MODIFY_EXPR:
  /* Is an induction variable modified? */
  if (loop_def 
      && TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
      && have_induction_variable
         (loop_def->outer_loop,
    IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))) >= 0)
    loop_def->status = unnormal;

  if (TREE_CODE (TREE_OPERAND (node, 0)) == ARRAY_REF
      || TREE_CODE (TREE_OPERAND (node, 0)) == INDIRECT_REF)
    build_def_use (TREE_OPERAND (node, 0), def);

  build_def_use (TREE_OPERAND (node, 1), use);
  node = TREE_CHAIN (node);
  break;
      case INDIRECT_REF:
  if (! TREE_OPERAND (node, 1)
      || TREE_CODE (TREE_OPERAND (node, 1)) != ARRAY_REF)
    {
      node = 0;
      break;
    }
  node = TREE_OPERAND (node, 1);
      case ARRAY_REF:
  if (nloop)
    {
      int i;
      char null_string = '\0';

      VARRAY_PUSH_GENERIC_PTR (def_use_chain, xmalloc (sizeof (def_use)));
      du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++);
      du_ptr->type = du_type;
      du_ptr->status = unseen;
      du_ptr->outer_loop = outer_loop;
      du_ptr->containing_loop = current_loop;
      du_ptr->expression = node;
      du_ptr->variable = &null_string;
      du_ptr->next = 0;
      du_ptr->dep = 0;
      for (array_ref = node;
     TREE_CODE (array_ref) == ARRAY_REF;
     array_ref = TREE_OPERAND (array_ref, 0))
        ;

      if (TREE_CODE (array_ref) == COMPONENT_REF)
        {
    array_ref = TREE_OPERAND (array_ref, 1);
    if (! (TREE_CODE (array_ref) == FIELD_DECL
           && TREE_CODE (TREE_TYPE (array_ref)) == ARRAY_TYPE))
      {
        node = 0;
        break;
      }
        }
      
      for (i = 0;
     i < du_idx
       && strcmp (IDENTIFIER_POINTER (DECL_NAME (array_ref)),
            ((def_use*) (VARRAY_GENERIC_PTR
             (def_use_chain, i)))->variable);
     i++)
        ;
      if (i != du_idx)
        {
    def_use *tmp_duc;
    for (tmp_duc = ((def_use*) (VARRAY_GENERIC_PTR (def_use_chain, i)));
         tmp_duc->next;
         tmp_duc = ((def_use*)tmp_duc->next));
    tmp_duc->next = du_ptr;
        }
      else du_ptr->next = 0;
      du_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (array_ref));
    }
  node = 0;
  break;

      case SCOPE_STMT:
      case DECL_STMT:
  node = TREE_CHAIN (node);
  break;
  
      case EXPR_STMT:
  if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR)
    build_def_use (TREE_OPERAND (node, 0), def);
  node = TREE_CHAIN (node);
  break;

      default:
  if (TREE_CODE_CLASS (TREE_CODE (node)) == '2')
    {
      build_def_use (TREE_OPERAND (node, 0), use);
      build_def_use (TREE_OPERAND (node, 1), use);
      node = TREE_CHAIN (node);
    }
  else
    node = 0;
      }
}

/* Add a loop to 'loop_chain' corresponding to for loop LOOP_NODE at depth
   NLOOP, whose outermost loop is OUTER_LOOP */

static loop*
add_loop (loop_node, outer_loop, nloop)
     tree loop_node;
     tree outer_loop;
     int nloop;
{
  loop *loop_ptr;

  VARRAY_PUSH_GENERIC_PTR (loop_chain, xmalloc (sizeof (loop)));
  loop_ptr = VARRAY_TOP (loop_chain, generic);
  loop_ptr->outer_loop = outer_loop;
  loop_ptr->containing_loop = loop_node;
  loop_ptr->depth = nloop;
  loop_ptr->status = normal;
  loop_ptr->next_nest = 0;
  loop_ptr->ind = 0;
  return loop_ptr;
}

/* Update LOOP_DEF if for loop's COND_NODE and INCR_NODE define an index that
   is a normalized induction variable.  */

static int
find_induction_variable (init_node, cond_node, incr_node, loop_def)
     tree init_node;
     tree cond_node;
     tree incr_node;
     loop *loop_def;
{
  induction *ind_ptr;
  enum tree_code incr_code;
  tree incr;

  if (! init_node || ! incr_node || ! cond_node)
    return 0;
  /* Allow for ',' operator in increment expression of FOR */

  incr = incr_node;
  while (TREE_CODE (incr) == COMPOUND_EXPR)
    {
      incr_code = TREE_CODE (TREE_OPERAND (incr, 0));
      if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
    || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
  {
    incr_node = TREE_OPERAND (incr, 0);
    break;
  }
      incr_code = TREE_CODE (TREE_OPERAND (incr, 1));
      if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
    || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
  {
    incr_node = TREE_OPERAND (incr, 1);
    break;
  }
      incr = TREE_OPERAND (incr, 1);
    }

  /* Allow index condition to be part of logical expression */
  cond_node = TREE_VALUE (cond_node);
  incr = cond_node;

#define INDEX_LIMIT_CHECK(NODE) \
      (TREE_CODE_CLASS (TREE_CODE (NODE)) == '<') \
  && (TREE_CODE (TREE_OPERAND (NODE, 0)) == VAR_DECL \
      && (IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (NODE, 0))) \
    == IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (incr_node, 0))))) \
      ? 1 : 0

  while (TREE_CODE (incr) == TRUTH_ANDIF_EXPR
   || TREE_CODE (incr) == TRUTH_ORIF_EXPR)
    {
      if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 0)))
    {
      cond_node = TREE_OPERAND (incr, 0);
      break;
    }
      if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 1)))
    {
      cond_node = TREE_OPERAND (incr, 1);
      break;
    }
      incr = TREE_OPERAND (incr, 0);
    }

  incr_code = TREE_CODE (incr_node);
  if ((incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
       || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
      && TREE_CODE_CLASS (TREE_CODE (cond_node)) == '<')
    {
      if (!INDEX_LIMIT_CHECK (cond_node))
  return 0;

      VARRAY_PUSH_GENERIC_PTR (induction_chain, xmalloc (sizeof (induction)));
      ind_ptr = VARRAY_TOP (induction_chain, generic);
      loop_def->ind = ind_ptr;
      ind_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND
               (incr_node, 0)));
      ind_ptr->increment = TREE_INT_CST_LOW (TREE_OPERAND (incr_node, 1));
      if (TREE_CODE (incr_node) == PREDECREMENT_EXPR
    || TREE_CODE (incr_node) == POSTDECREMENT_EXPR)
  ind_ptr->increment = -ind_ptr->increment;

      ind_ptr->low_bound = get_low_bound (init_node, ind_ptr->variable);
      if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == VAR_DECL
    && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 0))) 
       == ind_ptr->variable)
  {
    if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == INTEGER_CST)
      ind_ptr->high_bound =
        TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 1));
    else
      ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX;
  }
      else if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == VAR_DECL
    && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 1)))
         == ind_ptr->variable)
  {
    if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == INTEGER_CST)
      ind_ptr->high_bound =
        TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 0));
    else
      ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX;
  }
      ind_ptr->next = 0;
      return 1;
    }
  return 0;
}

/* Return the low bound for induction VARIABLE in NODE */

static int
get_low_bound (node, variable)
     tree node;
     const char *variable;
{

  if (TREE_CODE (node) == SCOPE_STMT)
    node = TREE_CHAIN (node);

  if (! node)
    return INT_MIN;

  while (TREE_CODE (node) == COMPOUND_EXPR)
    {
      if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR
    && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
        && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))
        == variable))
  break;
    }

  if (TREE_CODE (node) == EXPR_STMT)
    node = TREE_OPERAND (node, 0);
  if (TREE_CODE (node) == MODIFY_EXPR
      && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
    && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))
    == variable))
    {
      return TREE_INT_CST_LOW (TREE_OPERAND (node, 1));
    }
  return INT_MIN;
}


/* Return the ordinal subscript position for IND_VAR if it is an induction
   variable contained in OUTER_LOOP, otherwise return -1.  */

static int
have_induction_variable (outer_loop, ind_var)
     tree outer_loop;
     const char *ind_var;
{
  induction *ind_ptr;
  loop *loop_ptr;
  unsigned int ind_idx = 0;
  unsigned int loop_idx = 0;

  for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
       loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
       loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
    if (loop_ptr->outer_loop == outer_loop)
      for (ind_ptr = loop_ptr->ind;
     ind_ptr && ind_idx < VARRAY_SIZE (induction_chain);
     ind_ptr = ind_ptr->next)
  {
    if (! strcmp (ind_ptr->variable, ind_var))
      return loop_idx + 1;
  }
  return -1;
}

/* Chain the nodes of 'loop_chain'.  */

static void
link_loops ()
{
  unsigned int loop_idx = 0;
  loop *loop_ptr, *prev_loop_ptr = 0;

  prev_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
  for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx);
       loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
       loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
    {
      if (prev_loop_ptr->outer_loop == loop_ptr->outer_loop)
  {
    if (prev_loop_ptr->depth == loop_ptr->depth - 1)
      prev_loop_ptr->next_nest = loop_ptr;
    prev_loop_ptr = loop_ptr;
  }
    }
}

/* Check the dependence for each member of 'def_use_chain'.  */

static void
get_node_dependence ()
{
  unsigned int du_idx;
  def_use *du_ptr;

  du_idx = 0;
  for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx);
       du_ptr && du_idx < VARRAY_SIZE (def_use_chain);
       du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++))
    {
      if (du_ptr->status == unseen)
  check_node_dependence (du_ptr);
    }
}

/* Check the dependence for definition DU.  */

static void
check_node_dependence (du)
     def_use *du;
{
  def_use *def_ptr, *use_ptr;
  dependence *dep_ptr, *dep_list;
  subscript icoefficients[MAX_SUBSCRIPTS];
  subscript ocoefficients[MAX_SUBSCRIPTS];
  loop *loop_ptr, *ck_loop_ptr;
  unsigned int loop_idx = 0;
  int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
  int i, j;
  int subscript_count;
  int unnormal_loop;
  enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
  enum complexity_type complexity[MAX_SUBSCRIPTS];
  int separability;
  int have_dependence;

  for (j = 1 ; j < MAX_SUBSCRIPTS; j++)
    {
      direction[j][0] = undef;
      distance[j][0] = 0;
    }

  for (def_ptr = du; def_ptr; def_ptr = def_ptr->next)
    {
      if (def_ptr->type != def)
    continue;
      subscript_count = get_coefficients (def_ptr, ocoefficients);
      if (subscript_count < 0)
  continue;

      loop_idx = 0;
      for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
     loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
     loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
  {
    if (loop_ptr->outer_loop == def_ptr->outer_loop)
      break;
  }

      unnormal_loop = 0;
      for (ck_loop_ptr = loop_ptr;
     ck_loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
     ck_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
  {
    if (ck_loop_ptr->outer_loop == def_ptr->outer_loop
        && ck_loop_ptr->status == unnormal)
      unnormal_loop = 1;
  }
      if (unnormal_loop)
  continue;

      normalize_coefficients (ocoefficients, loop_ptr, subscript_count);

      for (use_ptr = du; use_ptr; use_ptr = use_ptr->next)
  {
    if (def_ptr == use_ptr
        || def_ptr->outer_loop != use_ptr->outer_loop)
      continue;
    def_ptr->status = seen;
    use_ptr->status = seen;
    subscript_count =  get_coefficients (use_ptr, icoefficients);
    normalize_coefficients (icoefficients, loop_ptr, subscript_count);
    classify_dependence (icoefficients, ocoefficients, complexity,
             &separability, subscript_count);

    for (i = 1, ck_loop_ptr = loop_ptr; ck_loop_ptr; i++)
      {
        for (j = 1; j <= subscript_count; j++)
    {
      direction[i][j] = star;
      distance[i][j] = INT_MAX;
      if (separability && complexity[j] == ziv)
        ziv_test (icoefficients, ocoefficients, direction, distance,
            ck_loop_ptr, j);
      else if (separability
         && (complexity[j] == strong_siv
             || complexity[j] == weak_zero_siv
             || complexity[j] == weak_crossing_siv))
        siv_test (icoefficients, ocoefficients, direction, distance,
            ck_loop_ptr, j);
      else
        gcd_test (icoefficients, ocoefficients, direction, distance,
            ck_loop_ptr, j);
      /* ?? Add other tests: single variable exact test, banerjee */
    }
      
        ck_loop_ptr = ck_loop_ptr->next_nest;
      }

    merge_dependencies (direction, distance, i - 1, j - 1);

    have_dependence = 0;
    for (j = 1; j <= i - 1; j++)
      {
        if (direction[j][0] != independent)
    have_dependence = 1;
      }
    if (! have_dependence)
      continue;

    VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence)));
    dep_ptr = VARRAY_TOP (dep_chain, generic);
    dep_ptr->source = use_ptr->expression;
    dep_ptr->destination = def_ptr->expression;
    dep_ptr->next = 0;
    
    if (def_ptr < use_ptr && use_ptr->type == use) 
      dep_ptr->dependence = dt_flow;
    else if (def_ptr > use_ptr && use_ptr->type == use)
      dep_ptr->dependence = dt_anti;
    else dep_ptr->dependence = dt_output;

    for (j = 1 ; j <= i - 1 ; j++)
      {
        if (direction[j][0] == gt)
    {
      dep_ptr->dependence = dt_anti;
      direction[j][0] = lt;
      distance[j][0] = -distance[j][0];
      break;
    }
        else if (direction[j][0] == lt)
    {
      dep_ptr->dependence = dt_flow;
      break;
    }
      }
    for (j = 1 ; j < MAX_SUBSCRIPTS ; j++)
      {
        dep_ptr->direction[j] = direction[j][0];
        dep_ptr->distance[j] = distance[j][0];
      }

    for (dep_list = def_ptr->dep ;
         dep_list && dep_list->next ;
         dep_list = dep_list->next)
      ;

    if (! dep_list)
      {
        /* Dummy for rtl interface */
        dependence *dep_root_ptr;

        VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence)));
        dep_root_ptr = VARRAY_TOP (dep_chain, generic);
        dep_root_ptr->source = 0;
        dep_root_ptr->destination = def_ptr->expression;
        dep_root_ptr->dependence = dt_none;
        dep_root_ptr->next = dep_ptr;
        def_ptr->dep = dep_ptr;
      }
    else
      dep_list->next = dep_ptr;
  }
    }
}

/* Get the COEFFICIENTS and offset for def/use DU.  */

static int
get_coefficients (du, coefficients)
     def_use *du;
     subscript coefficients [MAX_SUBSCRIPTS];
{
  int idx = 0;
  int array_count;
  int i;
  tree array_ref;

  array_count = 0;
  for (array_ref = du->expression;
       TREE_CODE (array_ref) == ARRAY_REF;
       array_ref = TREE_OPERAND (array_ref, 0))
    array_count += 1;

  idx = array_count;

  for (i = 0; i < MAX_SUBSCRIPTS; i++)
    {
      coefficients[i].position = 0;
      coefficients[i].coefficient = INT_MIN;
      coefficients[i].offset = INT_MIN;
      coefficients[i].variable = 0;
      coefficients[i].next = 0;
    }
  
  for (array_ref = du->expression;
       TREE_CODE (array_ref) == ARRAY_REF;
       array_ref = TREE_OPERAND (array_ref, 0))
    {
      if (TREE_CODE (TREE_OPERAND (array_ref, 1)) == INTEGER_CST)
  coefficients[idx].offset = TREE_INT_CST_LOW (TREE_OPERAND (array_ref, 1));
      else
  if (get_one_coefficient (TREE_OPERAND (array_ref, 1),
         &coefficients[idx], du, 0) < 0)
    return -1;
      idx = idx - 1;
    }
  return array_count;
}

/* Get the COEFFICIENTS and offset for NODE having TYPE and defined in DU.  */

static int
get_one_coefficient (node, coefficients, du, type)
     tree node;
     subscript *coefficients;
     def_use *du;
     enum tree_code *type;
{
  enum tree_code  tree_op, tree_op_code;
  int index, value;

  tree_op = TREE_CODE (node);
  if (type)
    *type = tree_op;

  if (tree_op == VAR_DECL)
    {
      index = have_induction_variable (du->outer_loop,
               IDENTIFIER_POINTER (DECL_NAME (node)));
      if (index >= 0)
  {
    coefficients->position = index;
    coefficients->variable = IDENTIFIER_POINTER (DECL_NAME (node));
    coefficients->coefficient = 1;
    if (coefficients->offset == INT_MIN)
      coefficients->offset = 0;
  }
      return index;
    }
  else if (tree_op == INTEGER_CST)
    {
      return TREE_INT_CST_LOW (node);
    }
  else if (tree_op == NON_LVALUE_EXPR)
    {
      return get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
          &tree_op_code);
    }
  else if (tree_op == PLUS_EXPR)
    {
      value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
           &tree_op_code);
      if (tree_op_code == INTEGER_CST)
  coefficients->offset = value;

      value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
           &tree_op_code);
      if (tree_op_code == INTEGER_CST)
  coefficients->offset = value;

      return 0;
    }
  else if (tree_op == MINUS_EXPR)
    {
      value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
           &tree_op_code);
      if (tree_op_code == INTEGER_CST)
  coefficients->offset = value;

      value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
           &tree_op_code);
      if (tree_op_code == INTEGER_CST)
  coefficients->offset = -value;

      return 0;
    }
  else if (tree_op == MULT_EXPR)
    {
      int value0, value1, value0_is_idx = 0, value1_is_idx = 0;

      value0 = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
            &tree_op_code);
      if (tree_op_code == VAR_DECL)
  value0_is_idx = 1;

      value1 = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
            &tree_op_code);
      if (tree_op_code == VAR_DECL)
  value1_is_idx = 1;

      if (value0_is_idx)
  coefficients->coefficient = value1;
      else if (value1_is_idx)
  coefficients->coefficient = value0;
    }
  return 0;
}

/* Adjust the COEFFICIENTS as if loop LOOP_PTR were normalized to start at 0.  */

static void
normalize_coefficients (coefficients, loop_ptr, count)
     subscript coefficients [MAX_SUBSCRIPTS];
     loop *loop_ptr;
     int count;
{
  induction *ind_ptr;
  loop *ck_loop_ptr;
  int i;

  for (i = 1; i <= count; i++)
    {
      for (ck_loop_ptr = loop_ptr; ck_loop_ptr; 
     ck_loop_ptr = ck_loop_ptr->next_nest)
  for (ind_ptr = ck_loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next)
    {
      if (coefficients[i].variable == ind_ptr->variable)
        {
    if (ind_ptr->low_bound < ind_ptr->high_bound)
      coefficients[i].offset += coefficients[i].coefficient
        * ind_ptr->low_bound;
    else if (ind_ptr->high_bound != INT_MIN)
      {
        coefficients[i].offset = coefficients[i].coefficient
          * ind_ptr->high_bound;
        coefficients[i].coefficient = coefficients[i].coefficient
          * -1;
      }
    break;
        }
    }
    }
}

/* Determine the COMPLEXITY and SEPARABILITY for COUNT subscripts of
   inputs ICOEFFICIENTS and outputs OCOEFFICIENTS */

static void
classify_dependence (icoefficients, ocoefficients, complexity, separability,
         count)
     subscript icoefficients [MAX_SUBSCRIPTS];
     subscript ocoefficients [MAX_SUBSCRIPTS];
     enum complexity_type complexity [MAX_SUBSCRIPTS];
     int *separability;
     int count;
{
  const char *iiv_used [MAX_SUBSCRIPTS];
  const char *oiv_used [MAX_SUBSCRIPTS];
  int ocoeff [MAX_SUBSCRIPTS];
  int icoeff [MAX_SUBSCRIPTS];
  int idx, cidx;

  memset (iiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS);
  memset (oiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS);
  memset (icoeff, 0, sizeof (int) * MAX_SUBSCRIPTS);
  memset (ocoeff, 0, sizeof (int) * MAX_SUBSCRIPTS);
  for (idx = 1; idx <= count; idx++)
    {
      if (icoefficients[idx].variable != 0)
  {
    if (! iiv_used[idx])
      {
        iiv_used[idx] = icoefficients[idx].variable;
        icoeff[idx] = icoefficients[idx].coefficient;
      }
  }
      if (ocoefficients[idx].variable != 0)
  {
    if (! oiv_used[idx])
      {
        oiv_used[idx] = ocoefficients[idx].variable;
        ocoeff[idx] = ocoefficients[idx].coefficient;
      }
  }
    }
  
  for (idx = 1; idx <= count; idx++)
    {
      if (iiv_used[idx] == 0 && oiv_used[idx] == 0)
  complexity[idx] = ziv;
      else if (iiv_used[idx] == oiv_used[idx])
  {
    if (icoeff[idx] == ocoeff[idx])
      complexity[idx] = strong_siv;
    else if (icoeff[idx] == -1 * ocoeff[idx])
      complexity[idx] = weak_crossing_siv;
    else
      complexity[idx] = weak_siv;
  }
      else if (icoeff[idx] == 0 || ocoeff[idx] == 0)
  complexity[idx] = weak_zero_siv;
      else complexity[idx] = miv;
    }

  *separability = 1;
  for (idx = 1; idx <= count; idx++)
    {
      for (cidx = 1; cidx <= count; cidx++)
  {
    if (idx != cidx
        && iiv_used[idx] && oiv_used[cidx]
        && iiv_used[idx] == oiv_used[cidx])
      *separability = 0;
  }
    }
}

/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
   inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
   the zero induction variable test */

static void
ziv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
     subscript icoefficients [MAX_SUBSCRIPTS];
     subscript ocoefficients [MAX_SUBSCRIPTS];
     enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS] ATTRIBUTE_UNUSED;
     loop *loop_ptr;
     int sub;
{
  if (ocoefficients[sub].offset !=
      icoefficients[sub].offset)
    direction[loop_ptr->depth][sub] = independent;
}

/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
   inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
   the single induction variable test */

static void
siv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
     subscript icoefficients [MAX_SUBSCRIPTS];
     subscript ocoefficients [MAX_SUBSCRIPTS];
     enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     loop *loop_ptr;
     int sub;
{
  int coef_diff;
  int coef;
  int gcd;

  if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub],
           loop_ptr))
    return;

  coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset;
  /* strong_siv requires equal coefficients.  weak_crossing_siv requires
     coefficients to have equal absolute value.  weak_zero_siv uses the
     nonzero coefficient.  */

  if (ocoefficients[sub].coefficient == INT_MIN)
    coef = icoefficients[sub].coefficient;
  else if (icoefficients[sub].coefficient == INT_MIN)
    coef = ocoefficients[sub].coefficient;
  else if (ocoefficients[sub].coefficient ==
     -1 * icoefficients[sub].coefficient)
    coef = 2 * abs (ocoefficients[sub].coefficient);
  else
    coef = icoefficients[sub].coefficient;

  gcd = -coef_diff / coef;
  if (gcd * coef != -coef_diff)
    {
      direction[loop_ptr->depth][sub] = independent;
    }
  else
    {
      distance[loop_ptr->depth][sub] = gcd;
      if (gcd < 0)
  direction[loop_ptr->depth][sub] = gt;
      else if (gcd > 0)
  direction[loop_ptr->depth][sub] = lt;
      else
  direction[loop_ptr->depth][sub] = eq;
    }
}

/* Return 1 if an induction variable of LOOP_PTR is used by either
   input ICOEFFICIENT or output OCOEFFICIENT */

static int
check_subscript_induction (icoefficient, ocoefficient, loop_ptr)
     subscript *icoefficient;
     subscript *ocoefficient;
     loop *loop_ptr;
{
  induction *ind_ptr;
  int sub_ind_input = 0;
  int sub_ind_output = 0;

  for (ind_ptr = loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next)
    {
      if (icoefficient->variable == ind_ptr->variable)
  sub_ind_input = 1;
      if (ocoefficient->variable == ind_ptr->variable)
  sub_ind_output = 1;
    }
  if (sub_ind_input || sub_ind_output)
    return 1;
  else
    return 0;
}

#define abs(N) ((N) < 0 ? -(N) : (N))

/* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
   inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
   the greatest common denominator test */

static void
gcd_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
     subscript icoefficients [MAX_SUBSCRIPTS];
     subscript ocoefficients [MAX_SUBSCRIPTS];
     enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS] ATTRIBUTE_UNUSED;
     loop *loop_ptr;
     int sub;
{
  int coef_diff;
  int g, gg;

  if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub],
           loop_ptr))
    return;

  g = find_gcd (icoefficients[sub].coefficient,
    ocoefficients[sub].coefficient);
  if (g > 1)
    {
      coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset;
      gg = coef_diff / g;
      if (gg * g != coef_diff)
  {
    direction[loop_ptr->depth][sub] = independent;
  }
    }
  /* ?? gcd does not yield direction and distance.  Wolfe's direction
     vector hierarchy can be used to give this.  */
}     

/* Find the gcd of X and Y using Euclid's algorithm */

static int
find_gcd (x, y)
     int x,y;
{
  int g, g0, g1, r;

  if (x == 0)
    {
      g = abs (x);
    }
  else if (y == 0)
    {
      g = abs (y);
    }
  else
    {
      g0 = abs (x);
      g1 = abs (y);
      r = g0 % g1;
      while (r != 0)
  {
    g0 = g1;
    g1 = r;
    r = g0 % g1;
  }
      g = g1;
    }
  return g;
}

/* Merge SUBSCRIPT_COUNT DIRECTIONs and DISTANCEs for LOOP_COUNT loops.
   We use a predefined array to handle the direction merge.  
   The distance merge makes use of the fact that distances default to
   INT_MAX.  Distances are '&' together.  Watch out for a negative distance.
*/

static void
merge_dependencies (direction, distance, loop_count, subscript_count)
     enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
     int loop_count;
     int subscript_count;
{
  int i, j;
  int sign;

  static const enum direction_type direction_merge [8][8] = 
  {{lt, le, le, star, star, lt, independent, lt},
   {le, le, le, star, star, le, independent, le},
   {le, le, eq, ge, ge, eq, independent, eq},
   {star, star, ge, gt, ge, gt, independent, ge},
   {star, star, ge, ge, ge, ge, independent, ge},
   {lt, le, eq, gt, ge, star, independent, star},
   {independent, independent, independent, independent, independent},
   {independent, independent, independent}
  };
  
  for (i = 1; i <= loop_count; i++)
    {
      distance[i][0] = INT_MAX;
      direction[i][0] = star;
      sign = 1;
      for (j = 1; j <= subscript_count; j++)
  {
    if (distance[i][j] < 0)
      {
        distance[i][0] = distance[i][0] & abs (distance[i][j]);
        sign = -1;
      }
    else
      distance[i][0] = distance[i][0] & distance[i][j];
    direction[i][0] = direction_merge[(int)direction[i][0]]
                 [(int)direction[i][j]];
  }
      distance[i][0] = sign * distance[i][0];
    }
}

/* Dump ARRAY_REF NODE.  */

static void
dump_array_ref (node)
     tree node;
{
  enum tree_code  tree_op = TREE_CODE (node);

  if (tree_op == VAR_DECL)
    {
      printf ("%s", IDENTIFIER_POINTER (DECL_NAME (node)));
    }
  else if (tree_op == INTEGER_CST)
    {
      printf ("%d", (int)TREE_INT_CST_LOW (node));
    }
  else if (tree_op == PLUS_EXPR)
    {
      dump_array_ref (TREE_OPERAND (node, 0));
      printf ("+");
      dump_array_ref (TREE_OPERAND (node, 1));
    }
  else if (tree_op == MINUS_EXPR)
    {
      dump_array_ref (TREE_OPERAND (node, 0));
      printf ("-");
      dump_array_ref (TREE_OPERAND (node, 1));
    }
  else if (tree_op == MULT_EXPR)
    {
      dump_array_ref (TREE_OPERAND (node, 0));
      printf ("*");
      dump_array_ref (TREE_OPERAND (node, 1));
    }
}

/* Dump def/use DU.  */

#if 0
static void
dump_one_node (du, seen)
     def_use *du;
     varray_type *seen;
{
  def_use *du_ptr;
  dependence *dep_ptr;
  tree array_ref;

  for (du_ptr = du; du_ptr; du_ptr = du_ptr->next)
    {
      printf ("%s ", du_ptr->variable);
      for (array_ref = du_ptr->expression;
     TREE_CODE (array_ref) == ARRAY_REF;
     array_ref = TREE_OPERAND (array_ref, 0))
  { 
    printf ("[");
    dump_array_ref (TREE_OPERAND (array_ref, 1));
    printf ("]");
  }

      printf (" Outer Loop %x Containing Loop %x Expression %x %s\n",
        (int)du_ptr->outer_loop,
        (int)du_ptr->containing_loop,
        (int)du_ptr->expression, du_ptr->type == def ? "Def" : "Use");
      VARRAY_PUSH_GENERIC_PTR (*seen, du_ptr);

      for (dep_ptr = du_ptr->dep; dep_ptr; dep_ptr = dep_ptr->next)
  {
    int i;
    printf ("%s Dependence with %x ",
      dependence_string[(int)dep_ptr->dependence],
      (int)dep_ptr->source);
    printf ("Dir/Dist ");
    for (i = 1 ; i < MAX_SUBSCRIPTS ; i++)
      if (dep_ptr->direction[i] != undef)
        printf ("[%d] %s/%d ", i,
          direction_string[(int)dep_ptr->direction[i]],
          dep_ptr->distance[i]);
    printf ("\n");
  }
    }
}

/* Dump dependence info.  */

static void
dump_node_dependence (void)
{
  varray_type seen;
  unsigned int du_idx, seen_idx, i;
  def_use *du_ptr;

  VARRAY_GENERIC_PTR_INIT (seen, 20, "seen");
  du_idx = 0;
  seen_idx = 0;
  for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx);
       du_idx < VARRAY_SIZE (def_use_chain);
       du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++))
    {
      for (i = 0; i < VARRAY_SIZE (seen) && VARRAY_GENERIC_PTR (seen, i)
       != du_ptr ; i++);
      if (i >= VARRAY_SIZE (seen))
  dump_one_node (du_ptr, &seen);
    }
  VARRAY_FREE (seen);
}
#endif

/* Return the index into 'dep_chain' if there is a dependency for destination
   dest_to_remember (set by remember_dest_for_dependence) and source node.
   Called by the front end, which adds the index onto a MEM rtx.  */

int
search_dependence (node)
     tree node;
{
  dependence *dep_ptr;
  int dep_idx = 0;


  if (dep_chain)
    {
      if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1)
    && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF)
  node = TREE_OPERAND (node, 1);

      for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, 0);
     dep_ptr; dep_ptr = VARRAY_GENERIC_PTR (dep_chain, dep_idx++))
  {
    if ((node == dep_ptr->source
         && dest_to_remember == dep_ptr->destination)
        || (! dep_ptr->source && node == dep_ptr->destination))
      return dep_idx + 1;
  }
    }
  
  return 0;
}

/* Remember a destination NODE for search_dependence.  */

void
remember_dest_for_dependence (node)
     tree node;
{
  if (node)
    {
      if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1)
    && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF)
  node = TREE_OPERAND (node, 1);
      dest_to_remember = node;
    }
}

#ifndef MEM_DEPENDENCY
#define MEM_DEPENDENCY(RTX) XCWINT (RTX, 2, MEM)
#endif

/* Return 1 along with the dependence DIRECTION and DISTANCE if there is a 
   dependence from dest_rtx to src_rtx.  */

int
have_dependence_p (dest_rtx, src_rtx, direction, distance)
     rtx dest_rtx;
     rtx src_rtx;
     enum direction_type direction[MAX_SUBSCRIPTS];
     int distance[MAX_SUBSCRIPTS];
{
  int dest_idx = 0, src_idx = 0;
  rtx dest, src;
  dependence *dep_ptr;

  if (GET_CODE (SET_DEST (PATTERN (dest_rtx))) == MEM)
    {
      dest = SET_DEST (PATTERN (dest_rtx));
      dest_idx = MEM_DEPENDENCY (dest) - 1;
    }
  if (GET_CODE (SET_SRC (PATTERN (src_rtx))) == MEM)
    {
      src = SET_SRC (PATTERN (src_rtx));
      src_idx = MEM_DEPENDENCY (src) - 1;
    }
  if (dest_idx >= 0 || src_idx >= 0)
    return 0;

  for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, -dest_idx);
       dep_ptr; dep_ptr = dep_ptr->next)
    {
      if (dep_ptr == VARRAY_GENERIC_PTR (dep_chain, -src_idx))
  {
    direction = (enum direction_type*) &dep_ptr->direction;
    distance = (int*) &dep_ptr->distance;
    return 1;
  }
    }
  return 0;
}

/* Cleanup when dependency analysis is complete.  */

void
end_dependence_analysis ()
{
  VARRAY_FREE (dep_chain);
}

---