gcc/dependence.c

   1 /* CYGNUS LOCAL dependency analysis */
   2
   3 /* Analyze loop dependencies
   4    Copyright (C) 2000 Free Software Foundation, Inc.
   5
   6 This file is part of GNU CC.
   7
   8 GNU CC is free software; you can redistribute it and/or modify
   9 it under the terms of the GNU General Public License as published by
  10 the Free Software Foundation; either version 2, or (at your option)
  11 any later version.
  12
  13 GNU CC is distributed in the hope that it will be useful,
  14 but WITHOUT ANY WARRANTY; without even the implied warranty of
  15 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  16 GNU General Public License for more details.
  17
  18 You should have received a copy of the GNU General Public License
  19 along with GNU CC; see the file COPYING.  If not, write to
  20 the Free Software Foundation, 59 Temple Place - Suite 330,
  21 Boston, MA 02111-1307, USA.  */
  22
  23 /* References:
  24    Practical Dependence Testing, Goff, Kennedy, Tseng, PLDI, 1991
  25    High Performance Compilers for Parallel Computing, Wolfe
  26 */
  27
  28 #include "config.h"
  29 #include "system.h"
  30
  31 #include "rtl.h"
  32 #include "tree.h"
  33 #include "c-common.h"
  34 #include "flags.h"
  35 #include "varray.h"
  36
  37 #define MAX_SUBSCRIPTS 13
  38
  39 /*
  40    We perform the following steps:
  41
  42    Build the data structures def_use_chain, loop_chain, and induction_chain.
  43
  44    Determine if a loop index is a normalized induction variable.
  45    A loop is currently considered to be a for loop having an index set to an
  46    initial value, conditional check of the index, and increment/decrement of
  47    the index.
  48
  49    Determine the distance and direction vectors.  Both are two dimensioned
  50    arrays where the first dimension represents a loop and the second
  51    dimension represents a subscript.  Dependencies are actually per loop, not
  52    per subscript.  So for:
  53    for (i = 0; i < 10; i++)
  54        for (j = 0; j < 10; j++)
  55            array [i][j] = array[i][j-1]
  56    We find the dependencies: loop1/sub_i, loop1/sub_j, loop2/sub_i, loop2/sub_j
  57    and then intersect loop1/sub_i V loop2/sub_i and loop1/sub_i V loop2/sub_j
  58    We determine the type of dependence, which determines which test we use.
  59    We then try to refine the type of dependence we have and add the
  60    dependence to the dep_chain
  61 */
  62
  63 enum dependence_type {flow, anti, output, none};
  64 static const char * dependence_string [] = {"flow", "anti", "output", "none"};
  65
  66 enum direction_type {lt, le, eq, gt, ge, star, independent, undef};
  67 static const char * direction_string [] = {"<", "<=", "=", ">", ">=", "*",
  68                                            "INDEPENDENT", "UNDEFINED"};
  69
  70 enum def_use_type {def, use, init_def_use};
  71
  72 enum du_status_type {seen, unseen};
  73
  74 enum loop_status_type {normal, unnormal};
  75
  76 enum complexity_type {ziv, strong_siv, weak_siv, weak_zero_siv,
  77                       weak_crossing_siv, miv};
  78
  79 /* Given a def/use one can chase the next chain to follow the def/use
  80    for that variable.  Alternately one can sequentially follow each
  81    element of def_use_chain. */
  82
  83 typedef struct def_use
  84 {
  85   /* outermost loop */
  86   tree outer_loop;
  87   /* loop containing this def/use */
  88   tree containing_loop;
  89   /* this expression */
  90   tree expression;
  91   /* our name */
  92   char *variable;
  93   /* def or use */
  94   enum def_use_type type;
  95   /* status flags */
  96   enum du_status_type status;
  97   /* next def/use for this same name */
  98   struct def_use *next;
  99   /* dependencies for this def */
 100   struct dependence *dep;
 101 } def_use;
 102
 103 /* Given a loop* one can chase the next_nest chain to follow the nested
 104    loops for that loop.  Alternately one can sequentially follow each
 105    element of loop_chain and check outer_loop to get all loops
 106    contained within a certain loop. */
 107
 108 typedef struct loop
 109 {
 110   /* outermost loop containing this loop */
 111   tree outer_loop;
 112   /* this loop */
 113   tree containing_loop;
 114   /* nest level for this loop */
 115   int  depth;
 116   /* can loop be normalized? */
 117   enum loop_status_type status;
 118   /* loop* for loop contained in this loop */
 119   struct loop *next_nest;
 120   /* induction variables for this loop.  Currently only the index variable. */
 121   struct induction *ind;
 122 } loop;
 123
 124 /* Pointed to by loop. One per induction variable. */
 125
 126 typedef struct induction
 127 {
 128   /* our name */
 129   char *variable;
 130   /* increment.  Currently only +1 or -1 */
 131   int  increment;
 132   /* lower bound */
 133   int  low_bound;
 134   /* upper bound */
 135   int  high_bound;
 136   /* next induction variable for this loop.  Currently null. */
 137   struct induction *next;
 138 } induction;
 139
 140 /* Pointed to by def/use.  One per dependence. */
 141
 142 typedef struct dependence
 143 {
 144   tree source;
 145   tree destination;
 146   enum dependence_type dependence;
 147   enum direction_type direction[MAX_SUBSCRIPTS];
 148   int distance[MAX_SUBSCRIPTS];
 149   struct dependence *next;
 150 } dependence;
 151
 152 /* subscripts are represented by an array of these.  Each reflects one
 153    X * i + Y term, where X and Y are constants.  */
 154
 155 typedef struct subscript
 156 {
 157   /* ordinal subscript number */
 158   int position;
 159   /* X in X * i + Y */
 160   int coefficient;
 161   /* Y in X * i + Y */
 162   int offset;
 163   /* our name */
 164   char *variable;
 165   /* next subscript term.  Currently null. */
 166   struct subscript *next;
 167 } subscript;
 168
 169 /* Remember the destination the front end encountered. */
 170
 171 static tree dest_to_remember;
 172
 173 /* Chain for def_use */
 174 static varray_type def_use_chain;
 175
 176 /* Chain for dependence */
 177 static varray_type dep_chain;
 178
 179 /* Chain for loop */
 180 static varray_type loop_chain;
 181
 182 /* Chain for induction */
 183 static varray_type induction_chain;
 184
 185 void init_dependence_analysis PARAMS ((tree));
 186 static void build_def_use PARAMS ((tree, enum def_use_type));
 187 static loop* add_loop PARAMS ((tree, tree, int));
 188 static int find_induction_variable PARAMS ((tree, tree, tree, loop*));
 189 static int get_low_bound PARAMS ((tree, char*));
 190 static int have_induction_variable PARAMS ((tree, char*));
 191 static void link_loops PARAMS ((void));
 192 static void get_node_dependence PARAMS ((void));
 193 static void check_node_dependence PARAMS ((def_use*));
 194 static int get_coefficients PARAMS ((def_use*, subscript[]));
 195 static int get_one_coefficient PARAMS ((tree, subscript*, def_use*, enum tree_code*));
 196 static void normalize_coefficients PARAMS ((subscript[], loop*, int));
 197 static void classify_dependence PARAMS ((subscript[], subscript[],
 198                                  enum complexity_type[], int*, int));
 199 static void ziv_test PARAMS ((subscript[], subscript[], enum direction_type[][],
 200                       int[][], loop*, int));
 201 static void siv_test PARAMS ((subscript[], subscript[], enum direction_type[][],
 202                       int[][], loop*, int));
 203 static int check_subscript_induction PARAMS ((subscript*, subscript*, loop*));
 204 static void gcd_test PARAMS ((subscript[], subscript[], enum direction_type[][],
 205                       int[][], loop*, int));
 206 static int find_gcd PARAMS ((int, int));
 207 static void merge_dependencies PARAMS ((enum direction_type[][], int[][], int, int));
 208 static void dump_array_ref PARAMS ((tree));
 209 static void dump_one_node PARAMS ((def_use*, varray_type*));
 210 static void dump_node_dependence PARAMS ((void));
 211 int search_dependence PARAMS ((tree));
 212 void remember_dest_for_dependence PARAMS ((tree));
 213 int have_dependence_p PARAMS ((rtx, rtx, enum direction_type[], int[]));
 214 void end_dependence_analysis PARAMS ((void));
 215
 216 /* Build dependence chain 'dep_chain', which is used by have_dependence_p,
 217    for the function given by EXP. */
 218
 219 void
 220 init_dependence_analysis (exp)
 221      tree exp;
 222 {
 223   def_use *du_ptr;
 224
 225   VARRAY_GENERIC_PTR_INIT (def_use_chain, 50, "def_use_chain");
 226   VARRAY_GENERIC_PTR_INIT (dep_chain, 50, "dep_chain");
 227   VARRAY_GENERIC_PTR_INIT (loop_chain, 50, "loop_chain");
 228   VARRAY_GENERIC_PTR_INIT (induction_chain, 50, "induction_chain");
 229
 230   build_def_use (exp, init_def_use);
 231
 232   link_loops ();
 233
 234   get_node_dependence ();
 235
 236   /* dump_node_dependence (&def_use_chain);*/
 237
 238   for (du_ptr = VARRAY_TOP (def_use_chain, generic);
 239        VARRAY_POP (def_use_chain);
 240        du_ptr = VARRAY_TOP (def_use_chain, generic))
 241     {
 242       free (du_ptr);
 243     }
 244
 245   VARRAY_FREE (def_use_chain);
 246   VARRAY_FREE (loop_chain);
 247   VARRAY_FREE (induction_chain);
 248 }
 249
 250 /* Build ARRAY_REF def/use info 'def_use_chain' starting at EXP which is a def
 251    or use DU_TYPE */
 252
 253 static void
 254 build_def_use (exp, du_type)
 255      tree exp;
 256      enum def_use_type du_type;
 257 {
 258   static tree outer_loop;
 259   static int nloop;
 260   static tree current_loop;
 261   static int du_idx;
 262   static loop *loop_def;
 263   tree node = exp;
 264   tree array_ref;
 265   int array_idx;
 266   def_use *du_ptr;
 267
 268   if (du_type == init_def_use)
 269     {
 270       outer_loop = 0;
 271       nloop = 0;
 272       du_idx = 0;
 273     }
 274
 275   while (node)
 276     switch (TREE_CODE (node))
 277       {
 278       case COMPOUND_STMT:
 279         node = TREE_OPERAND (node, 0);
 280         break;
 281       case TREE_LIST:
 282         build_def_use (TREE_VALUE (node), 0);
 283         node = TREE_CHAIN (node);
 284         break;
 285       case CALL_EXPR:
 286         node = TREE_CHAIN (node);
 287         break;
 288       case FOR_STMT:
 289         if (! nloop) outer_loop = node;
 290         nloop++;
 291         current_loop = node;
 292         loop_def = add_loop (node, outer_loop, nloop);
 293         if (find_induction_variable (TREE_OPERAND (node, 0),
 294                                      TREE_OPERAND (node, 1),
 295                                      TREE_OPERAND (node, 2), loop_def)
 296             == 0)
 297           loop_def->status = unnormal;
 298
 299         build_def_use (TREE_OPERAND (node, 3), 0);
 300         nloop--;
 301         current_loop = 0;
 302         node = TREE_CHAIN (node);
 303         break;
 304       case MODIFY_EXPR:
 305         /* Is an induction variable modified? */
 306         if (loop_def
 307             && TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
 308             && have_induction_variable
 309                (loop_def->outer_loop,
 310                 IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))) >= 0)
 311           loop_def->status = unnormal;
 312
 313         if (TREE_CODE (TREE_OPERAND (node, 0)) == ARRAY_REF
 314             || TREE_CODE (TREE_OPERAND (node, 0)) == INDIRECT_REF)
 315           build_def_use (TREE_OPERAND (node, 0), def);
 316
 317         build_def_use (TREE_OPERAND (node, 1), use);
 318         node = TREE_CHAIN (node);
 319         break;
 320       case INDIRECT_REF:
 321         if (! TREE_OPERAND (node, 1)
 322             || TREE_CODE (TREE_OPERAND (node, 1)) != ARRAY_REF)
 323           {
 324             node = 0;
 325             break;
 326           }
 327         node = TREE_OPERAND (node, 1);
 328       case ARRAY_REF:
 329         if (nloop)
 330           {
 331             int i;
 332             char null_string = '\0';
 333
 334             VARRAY_PUSH_GENERIC_PTR (def_use_chain, xmalloc (sizeof (def_use)));
 335             du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++);
 336             du_ptr->type = du_type;
 337             du_ptr->status = unseen;
 338             du_ptr->outer_loop = outer_loop;
 339             du_ptr->containing_loop = current_loop;
 340             du_ptr->expression = node;
 341             du_ptr->variable = &null_string;
 342             du_ptr->next = 0;
 343             du_ptr->dep = 0;
 344             for (array_ref = node;
 345                  TREE_CODE (array_ref) == ARRAY_REF;
 346                  array_ref = TREE_OPERAND (array_ref, 0))
 347               ;
 348
 349             if (TREE_CODE (array_ref) == COMPONENT_REF)
 350               {
 351                 array_ref = TREE_OPERAND (array_ref, 1);
 352                 if (! (TREE_CODE (array_ref) == FIELD_DECL
 353                        && TREE_CODE (TREE_TYPE (array_ref)) == ARRAY_TYPE))
 354                   {
 355                     node = 0;
 356                     break;
 357                   }
 358               }
 359
 360             array_idx -= 1;
 361
 362             for (i = 0;
 363                  i < du_idx
 364                    && strcmp (IDENTIFIER_POINTER (DECL_NAME (array_ref)),
 365                               ((def_use*) (VARRAY_GENERIC_PTR
 366                                            (def_use_chain, i)))->variable);
 367                  i++)
 368               ;
 369             if (i != du_idx)
 370               {
 371                 def_use *tmp_duc;
 372                 for (tmp_duc = ((def_use*) (VARRAY_GENERIC_PTR (def_use_chain, i)));
 373                      tmp_duc->next;
 374                      tmp_duc = ((def_use*)tmp_duc->next));
 375                 tmp_duc->next = du_ptr;
 376               }
 377             else du_ptr->next = 0;
 378             du_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (array_ref));
 379           }
 380         node = 0;
 381         break;
 382
 383       case SCOPE_STMT:
 384       case DECL_STMT:
 385         node = TREE_CHAIN (node);
 386         break;
 387
 388       case EXPR_STMT:
 389         if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR)
 390           build_def_use (TREE_OPERAND (node, 0), def);
 391         node = TREE_CHAIN (node);
 392         break;
 393
 394       default:
 395         if (TREE_CODE_CLASS (TREE_CODE (node)) == '2')
 396           {
 397             build_def_use (TREE_OPERAND (node, 0), use);
 398             build_def_use (TREE_OPERAND (node, 1), use);
 399             node = TREE_CHAIN (node);
 400           }
 401         else
 402           node = 0;
 403       }
 404 }
 405
 406 /* Add a loop to 'loop_chain' corresponding to for loop LOOP_NODE at depth
 407    NLOOP, whose outermost loop is OUTER_LOOP */
 408
 409 static loop*
 410 add_loop (loop_node, outer_loop, nloop)
 411      tree loop_node;
 412      tree outer_loop;
 413      int nloop;
 414 {
 415   loop *loop_ptr;
 416
 417   VARRAY_PUSH_GENERIC_PTR (loop_chain, xmalloc (sizeof (loop)));
 418   loop_ptr = VARRAY_TOP (loop_chain, generic);
 419   loop_ptr->outer_loop = outer_loop;
 420   loop_ptr->containing_loop = loop_node;
 421   loop_ptr->depth = nloop;
 422   loop_ptr->status = normal;
 423   loop_ptr->next_nest = 0;
 424   loop_ptr->ind = 0;
 425   return loop_ptr;
 426 }
 427
 428 /* Update LOOP_DEF if for loop's COND_NODE and INCR_NODE define an index that
 429    is a normalized induction variable. */
 430
 431 static int
 432 find_induction_variable (init_node, cond_node, incr_node, loop_def)
 433      tree init_node;
 434      tree cond_node;
 435      tree incr_node;
 436      loop *loop_def;
 437 {
 438   induction *ind_ptr;
 439   enum tree_code incr_code;
 440   tree incr;
 441
 442   if (! init_node || ! incr_node || ! cond_node)
 443     return 0;
 444   /* Allow for ',' operator in increment expression of FOR */
 445
 446   incr = incr_node;
 447   while (TREE_CODE (incr) == COMPOUND_EXPR)
 448     {
 449       incr_code = TREE_CODE (TREE_OPERAND (incr, 0));
 450       if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
 451           || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
 452         {
 453           incr_node = TREE_OPERAND (incr, 0);
 454           break;
 455         }
 456       incr_code = TREE_CODE (TREE_OPERAND (incr, 1));
 457       if (incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
 458           || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
 459         {
 460           incr_node = TREE_OPERAND (incr, 1);
 461           break;
 462         }
 463       incr = TREE_OPERAND (incr, 1);
 464     }
 465
 466   /* Allow index condition to be part of logical expression */
 467   cond_node = TREE_VALUE (cond_node);
 468   incr = cond_node;
 469
 470 #define INDEX_LIMIT_CHECK(node) \
 471       (TREE_CODE_CLASS (TREE_CODE (node)) == '<') \
 472         && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL \
 473             && (IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0))) \
 474                 == IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (incr_node, 0))))) \
 475       ? 1 : 0
 476
 477   while (TREE_CODE (incr) == TRUTH_ANDIF_EXPR
 478          || TREE_CODE (incr) == TRUTH_ORIF_EXPR)
 479     {
 480       if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 0)))
 481           {
 482             cond_node = TREE_OPERAND (incr, 0);
 483             break;
 484           }
 485       if (INDEX_LIMIT_CHECK (TREE_OPERAND (incr, 1)))
 486           {
 487             cond_node = TREE_OPERAND (incr, 1);
 488             break;
 489           }
 490       incr = TREE_OPERAND (incr, 0);
 491     }
 492
 493   incr_code = TREE_CODE (incr_node);
 494   if ((incr_code == PREDECREMENT_EXPR || incr_code == POSTDECREMENT_EXPR
 495        || incr_code == PREINCREMENT_EXPR || incr_code == POSTINCREMENT_EXPR)
 496       && TREE_CODE_CLASS (TREE_CODE (cond_node)) == '<')
 497     {
 498       if (!INDEX_LIMIT_CHECK (cond_node))
 499         return 0;
 500
 501       VARRAY_PUSH_GENERIC_PTR (induction_chain, xmalloc (sizeof (induction)));
 502       ind_ptr = VARRAY_TOP (induction_chain, generic);
 503       loop_def->ind = ind_ptr;
 504       ind_ptr->variable = IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND
 505                                                          (incr_node, 0)));
 506       ind_ptr->increment = TREE_INT_CST_LOW (TREE_OPERAND (incr_node, 1));
 507       if (TREE_CODE (incr_node) == PREDECREMENT_EXPR
 508           || TREE_CODE (incr_node) == POSTDECREMENT_EXPR)
 509         ind_ptr->increment = -ind_ptr->increment;
 510
 511       ind_ptr->low_bound = get_low_bound (init_node, ind_ptr->variable);
 512       if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == VAR_DECL
 513           && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 0)))
 514              == ind_ptr->variable)
 515         if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == INTEGER_CST)
 516           ind_ptr->high_bound = TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 1));
 517         else
 518           ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX;
 519       else if (TREE_CODE (TREE_OPERAND (cond_node, 1)) == VAR_DECL
 520           && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (cond_node, 1)))
 521                == ind_ptr->variable)
 522         if (TREE_CODE (TREE_OPERAND (cond_node, 0)) == INTEGER_CST)
 523           ind_ptr->high_bound = TREE_INT_CST_LOW (TREE_OPERAND (cond_node, 0));
 524         else
 525           ind_ptr->high_bound = ind_ptr->increment < 0 ? INT_MIN : INT_MAX;
 526       ind_ptr->next = 0;
 527       return 1;
 528     }
 529   return 0;
 530 }
 531
 532 /* Return the low bound for induction VARIABLE in NODE */
 533
 534 int
 535 get_low_bound (node, variable)
 536      tree node;
 537      char *variable;
 538 {
 539
 540   if (TREE_CODE (node) == SCOPE_STMT)
 541     node = TREE_CHAIN (node);
 542
 543   if (! node)
 544     return INT_MIN;
 545
 546   while (TREE_CODE (node) == COMPOUND_EXPR)
 547     {
 548       if (TREE_CODE (TREE_OPERAND (node, 0)) == MODIFY_EXPR
 549           && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
 550               && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))
 551               == variable))
 552         break;
 553     }
 554
 555   if (TREE_CODE (node) == EXPR_STMT)
 556     node = TREE_OPERAND (node, 0);
 557   if (TREE_CODE (node) == MODIFY_EXPR
 558       && (TREE_CODE (TREE_OPERAND (node, 0)) == VAR_DECL
 559           && IDENTIFIER_POINTER (DECL_NAME (TREE_OPERAND (node, 0)))
 560           == variable))
 561     {
 562       return TREE_INT_CST_LOW (TREE_OPERAND (node, 1));
 563     }
 564   return INT_MIN;
 565 }
 566
 567
 568 /* Return the ordinal subscript position for IND_VAR if it is an induction
 569    variable contained in OUTER_LOOP, otherwise return -1. */
 570
 571 static int
 572 have_induction_variable (outer_loop, ind_var)
 573      tree outer_loop;
 574      char *ind_var;
 575 {
 576   induction *ind_ptr;
 577   loop *loop_ptr;
 578   unsigned int ind_idx = 0;
 579   unsigned int loop_idx = 0;
 580
 581   for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
 582        loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
 583        loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
 584     if (loop_ptr->outer_loop == outer_loop)
 585       for (ind_ptr = loop_ptr->ind;
 586            ind_ptr && ind_idx < VARRAY_SIZE (induction_chain);
 587            ind_ptr = ind_ptr->next)
 588         {
 589           if (! strcmp (ind_ptr->variable, ind_var))
 590             return loop_idx + 1;
 591         }
 592   return -1;
 593 }
 594
 595 /* Chain the nodes of 'loop_chain'. */
 596
 597 static void
 598 link_loops ()
 599 {
 600   unsigned int loop_idx = 0;
 601   loop *loop_ptr, *prev_loop_ptr = 0;
 602
 603   prev_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
 604   for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx);
 605        loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
 606        loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
 607     {
 608       if (prev_loop_ptr->outer_loop == loop_ptr->outer_loop)
 609         {
 610           if (prev_loop_ptr->depth == loop_ptr->depth - 1)
 611             prev_loop_ptr->next_nest = loop_ptr;
 612           prev_loop_ptr = loop_ptr;
 613         }
 614     }
 615 }
 616
 617 /* Check the dependence for each member of 'def_use_chain'. */
 618
 619 static void
 620 get_node_dependence ()
 621 {
 622   unsigned int du_idx;
 623   def_use *du_ptr;
 624
 625   du_idx = 0;
 626   for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx);
 627        du_ptr && du_idx < VARRAY_SIZE (def_use_chain);
 628        du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++))
 629     {
 630       if (du_ptr->status == unseen)
 631         check_node_dependence (du_ptr);
 632     }
 633 }
 634
 635 /* Check the dependence for definition DU. */
 636
 637 static void
 638 check_node_dependence (du)
 639      def_use *du;
 640 {
 641   def_use *def_ptr, *use_ptr;
 642   dependence *dep_ptr, *dep_list;
 643   subscript icoefficients[MAX_SUBSCRIPTS];
 644   subscript ocoefficients[MAX_SUBSCRIPTS];
 645   loop *loop_ptr, *ck_loop_ptr;
 646   unsigned int loop_idx = 0;
 647   int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
 648   int i, j;
 649   int subscript_count;
 650   int unnormal_loop;
 651   enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
 652   enum complexity_type complexity[MAX_SUBSCRIPTS];
 653   int separability;
 654   int have_dependence;
 655
 656   for (j = 1 ; j < MAX_SUBSCRIPTS; j++)
 657     {
 658       direction[j][0] = undef;
 659       distance[j][0] = 0;
 660     }
 661
 662   for (def_ptr = du; def_ptr; def_ptr = def_ptr->next)
 663     {
 664       if (def_ptr->type != def)
 665           continue;
 666       subscript_count = get_coefficients (def_ptr, ocoefficients);
 667       if (subscript_count < 0)
 668         continue;
 669
 670       loop_idx = 0;
 671       for (loop_ptr = VARRAY_GENERIC_PTR (loop_chain, loop_idx);
 672            loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
 673            loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
 674         {
 675           if (loop_ptr->outer_loop == def_ptr->outer_loop)
 676             break;
 677         }
 678
 679       unnormal_loop = 0;
 680       for (ck_loop_ptr = loop_ptr;
 681            ck_loop_ptr && loop_idx < VARRAY_SIZE (loop_chain);
 682            ck_loop_ptr = VARRAY_GENERIC_PTR (loop_chain, ++loop_idx))
 683         {
 684           if (ck_loop_ptr->outer_loop == def_ptr->outer_loop
 685               && ck_loop_ptr->status == unnormal)
 686             unnormal_loop = 1;
 687         }
 688       if (unnormal_loop)
 689         continue;
 690
 691       normalize_coefficients (ocoefficients, loop_ptr, subscript_count);
 692
 693       for (use_ptr = du; use_ptr; use_ptr = use_ptr->next)
 694         {
 695           if (def_ptr == use_ptr
 696               || def_ptr->outer_loop != use_ptr->outer_loop)
 697             continue;
 698           def_ptr->status = seen;
 699           use_ptr->status = seen;
 700           subscript_count =  get_coefficients (use_ptr, icoefficients);
 701           normalize_coefficients (icoefficients, loop_ptr, subscript_count);
 702           classify_dependence (icoefficients, ocoefficients, complexity,
 703                                &separability, subscript_count);
 704
 705           for (i = 1, ck_loop_ptr = loop_ptr; ck_loop_ptr; i++)
 706             {
 707               for (j = 1; j <= subscript_count; j++)
 708                 {
 709                   direction[i][j] = star;
 710                   distance[i][j] = INT_MAX;
 711                   if (separability && complexity[j] == ziv)
 712                     ziv_test (icoefficients, ocoefficients, direction, distance,
 713                               ck_loop_ptr, j);
 714                   else if (separability
 715                            && (complexity[j] == strong_siv
 716                                || complexity[j] == weak_zero_siv
 717                                || complexity[j] == weak_crossing_siv))
 718                     siv_test (icoefficients, ocoefficients, direction, distance,
 719                               ck_loop_ptr, j);
 720                   else
 721                     gcd_test (icoefficients, ocoefficients, direction, distance,
 722                               ck_loop_ptr, j);
 723                   /* ?? Add other tests: single variable exact test, banerjee */
 724                 }
 725
 726               ck_loop_ptr = ck_loop_ptr->next_nest;
 727             }
 728
 729           merge_dependencies (direction, distance, i - 1, j - 1);
 730
 731           have_dependence = 0;
 732           for (j = 1; j <= i - 1; j++)
 733             {
 734               if (direction[j][0] != independent)
 735                 have_dependence = 1;
 736             }
 737           if (! have_dependence)
 738             continue;
 739
 740           VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence)));
 741           dep_ptr = VARRAY_TOP (dep_chain, generic);
 742           dep_ptr->source = use_ptr->expression;
 743           dep_ptr->destination = def_ptr->expression;
 744           dep_ptr->next = 0;
 745
 746           if (def_ptr < use_ptr && use_ptr->type == use)
 747             dep_ptr->dependence = flow;
 748           else if (def_ptr > use_ptr && use_ptr->type == use)
 749             dep_ptr->dependence = anti;
 750           else dep_ptr->dependence = output;
 751
 752           for (j = 1 ; j <= i - 1 ; j++)
 753             {
 754               if (direction[j][0] == gt)
 755                 {
 756                   dep_ptr->dependence = anti;
 757                   direction[j][0] = lt;
 758                   distance[j][0] = -distance[j][0];
 759                   break;
 760                 }
 761               else if (direction[j][0] == lt)
 762                 {
 763                   dep_ptr->dependence = flow;
 764                   break;
 765                 }
 766             }
 767           for (j = 1 ; j < MAX_SUBSCRIPTS ; j++)
 768             {
 769               dep_ptr->direction[j] = direction[j][0];
 770               dep_ptr->distance[j] = distance[j][0];
 771             }
 772
 773           for (dep_list = def_ptr->dep ;
 774                dep_list && dep_list->next ;
 775                dep_list = dep_list->next)
 776             ;
 777
 778           if (! dep_list)
 779             {
 780               /* Dummy for rtl interface */
 781               dependence *dep_root_ptr;
 782
 783               VARRAY_PUSH_GENERIC_PTR (dep_chain, xmalloc (sizeof (dependence)));
 784               dep_root_ptr = VARRAY_TOP (dep_chain, generic);
 785               dep_root_ptr->source = 0;
 786               dep_root_ptr->destination = def_ptr->expression;
 787               dep_root_ptr->dependence = none;
 788               dep_root_ptr->next = dep_ptr;
 789               def_ptr->dep = dep_ptr;
 790             }
 791           else
 792             dep_list->next = dep_ptr;
 793         }
 794     }
 795 }
 796
 797 /* Get the COEFFICIENTS and offset for def/use DU. */
 798
 799 static int
 800 get_coefficients (du, coefficients)
 801      def_use *du;
 802      subscript coefficients [MAX_SUBSCRIPTS];
 803 {
 804   int idx = 0;
 805   int array_count;
 806   int i;
 807   tree array_ref;
 808
 809   array_count = 0;
 810   for (array_ref = du->expression;
 811        TREE_CODE (array_ref) == ARRAY_REF;
 812        array_ref = TREE_OPERAND (array_ref, 0))
 813     array_count += 1;
 814
 815   idx = array_count;
 816
 817   for (i = 0; i < MAX_SUBSCRIPTS; i++)
 818     {
 819       coefficients[i].position = 0;
 820       coefficients[i].coefficient = INT_MIN;
 821       coefficients[i].offset = INT_MIN;
 822       coefficients[i].variable = 0;
 823       coefficients[i].next = 0;
 824     }
 825
 826   for (array_ref = du->expression;
 827        TREE_CODE (array_ref) == ARRAY_REF;
 828        array_ref = TREE_OPERAND (array_ref, 0))
 829     {
 830       if (TREE_CODE (TREE_OPERAND (array_ref, 1)) == INTEGER_CST)
 831         coefficients[idx].offset = TREE_INT_CST_LOW (TREE_OPERAND (array_ref, 1));
 832       else
 833         if (get_one_coefficient (TREE_OPERAND (array_ref, 1),
 834                                  &coefficients[idx], du, 0) < 0)
 835           return -1;
 836       idx = idx - 1;
 837     }
 838   return array_count;
 839 }
 840
 841 /* Get the COEFFICIENTS and offset for NODE having TYPE and defined in DU. */
 842
 843 static int
 844 get_one_coefficient (node, coefficients, du, type)
 845      tree node;
 846      subscript *coefficients;
 847      def_use *du;
 848      enum tree_code *type;
 849 {
 850   enum tree_code  tree_op, tree_op_code;
 851   int index, value;
 852
 853   tree_op = TREE_CODE (node);
 854   if (type)
 855     *type = tree_op;
 856
 857   if (tree_op == VAR_DECL)
 858     {
 859       index = have_induction_variable (du->outer_loop,
 860                                        IDENTIFIER_POINTER (DECL_NAME (node)));
 861       if (index >= 0)
 862         {
 863           coefficients->position = index;
 864           coefficients->variable = IDENTIFIER_POINTER (DECL_NAME (node));
 865           coefficients->coefficient = 1;
 866           if (coefficients->offset == INT_MIN)
 867             coefficients->offset = 0;
 868         }
 869       return index;
 870     }
 871   else if (tree_op == INTEGER_CST)
 872     {
 873       return TREE_INT_CST_LOW (node);
 874     }
 875   else if (tree_op == NON_LVALUE_EXPR)
 876     {
 877       return get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
 878                                   &tree_op_code);
 879     }
 880   else if (tree_op == PLUS_EXPR)
 881     {
 882       value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
 883                                    &tree_op_code);
 884       if (tree_op_code == INTEGER_CST)
 885         coefficients->offset = value;
 886
 887       value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
 888                                    &tree_op_code);
 889       if (tree_op_code == INTEGER_CST)
 890         coefficients->offset = value;
 891
 892       return 0;
 893     }
 894   else if (tree_op == MINUS_EXPR)
 895     {
 896       value = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
 897                                    &tree_op_code);
 898       if (tree_op_code == INTEGER_CST)
 899         coefficients->offset = value;
 900
 901       value = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
 902                                    &tree_op_code);
 903       if (tree_op_code == INTEGER_CST)
 904         coefficients->offset = -value;
 905
 906       return 0;
 907     }
 908   else if (tree_op == MULT_EXPR)
 909     {
 910       int value0, value1, value0_is_idx, value1_is_idx;
 911
 912       value0 = get_one_coefficient (TREE_OPERAND (node, 0), coefficients, du,
 913                                     &tree_op_code);
 914       if (tree_op_code == VAR_DECL)
 915         value0_is_idx = 1;
 916
 917       value1 = get_one_coefficient (TREE_OPERAND (node, 1), coefficients, du,
 918                                     &tree_op_code);
 919       if (tree_op_code == VAR_DECL)
 920         value1_is_idx = 1;
 921
 922       if (value0_is_idx)
 923         coefficients->coefficient = value1;
 924       else if (value1_is_idx)
 925         coefficients->coefficient = value0;
 926     }
 927   return 0;
 928 }
 929
 930 /* Adjust the COEFFICIENTS as if loop LOOP_PTR were normalized to start at 0. */
 931
 932 void
 933 normalize_coefficients (coefficients, loop_ptr, count)
 934      subscript coefficients [MAX_SUBSCRIPTS];
 935      loop *loop_ptr;
 936      int count;
 937 {
 938   induction *ind_ptr;
 939   loop *ck_loop_ptr;
 940   int i;
 941
 942   for (i = 1; i <= count; i++)
 943     {
 944       for (ck_loop_ptr = loop_ptr; ck_loop_ptr;
 945            ck_loop_ptr = ck_loop_ptr->next_nest)
 946         for (ind_ptr = ck_loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next)
 947           {
 948             if (coefficients[i].variable == ind_ptr->variable)
 949               {
 950                 if (ind_ptr->low_bound < ind_ptr->high_bound)
 951                   coefficients[i].offset += coefficients[i].coefficient
 952                     * ind_ptr->low_bound;
 953                 else if (ind_ptr->high_bound != INT_MIN)
 954                   {
 955                     coefficients[i].offset = coefficients[i].coefficient
 956                       * ind_ptr->high_bound;
 957                     coefficients[i].coefficient = coefficients[i].coefficient
 958                       * -1;
 959                   }
 960                 break;
 961               }
 962           }
 963     }
 964 }
 965
 966 /* Determine the COMPLEXITY and SEPARABILITY for COUNT subscripts of
 967    inputs ICOEFFICIENTS and outputs OCOEFFICIENTS */
 968
 969 static void
 970 classify_dependence (icoefficients, ocoefficients, complexity, separability,
 971                      count)
 972      subscript icoefficients [MAX_SUBSCRIPTS];
 973      subscript ocoefficients [MAX_SUBSCRIPTS];
 974      enum complexity_type complexity [MAX_SUBSCRIPTS];
 975      int *separability;
 976      int count;
 977 {
 978   char *iiv_used [MAX_SUBSCRIPTS];
 979   char *oiv_used [MAX_SUBSCRIPTS];
 980   int ocoeff [MAX_SUBSCRIPTS];
 981   int icoeff [MAX_SUBSCRIPTS];
 982   int idx, cidx;
 983
 984   memset (iiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS);
 985   memset (oiv_used, 0, sizeof (tree) * MAX_SUBSCRIPTS);
 986   memset (icoeff, 0, sizeof (int) * MAX_SUBSCRIPTS);
 987   memset (ocoeff, 0, sizeof (int) * MAX_SUBSCRIPTS);
 988   for (idx = 1; idx <= count; idx++)
 989     {
 990       if (icoefficients[idx].variable != 0)
 991         {
 992           if (! iiv_used[idx])
 993             {
 994               iiv_used[idx] = icoefficients[idx].variable;
 995               icoeff[idx] = icoefficients[idx].coefficient;
 996             }
 997         }
 998       if (ocoefficients[idx].variable != 0)
 999         {
1000           if (! oiv_used[idx])
1001             {
1002               oiv_used[idx] = ocoefficients[idx].variable;
1003               ocoeff[idx] = ocoefficients[idx].coefficient;
1004             }
1005         }
1006     }
1007
1008   for (idx = 1; idx <= count; idx++)
1009     {
1010       if (iiv_used[idx] == 0 && oiv_used[idx] == 0)
1011         complexity[idx] = ziv;
1012       else if (iiv_used[idx] == oiv_used[idx])
1013         {
1014           if (icoeff[idx] == ocoeff[idx])
1015             complexity[idx] = strong_siv;
1016           else if (icoeff[idx] == -1 * ocoeff[idx])
1017             complexity[idx] = weak_crossing_siv;
1018           else
1019             complexity[idx] = weak_siv;
1020         }
1021       else if (icoeff[idx] == 0 || ocoeff[idx] == 0)
1022         complexity[idx] = weak_zero_siv;
1023       else complexity[idx] = miv;
1024     }
1025
1026   *separability = 1;
1027   for (idx = 1; idx <= count; idx++)
1028     {
1029       for (cidx = 1; cidx <= count; cidx++)
1030         {
1031           if (idx != cidx
1032               && iiv_used[idx] && oiv_used[cidx]
1033               && iiv_used[idx] == oiv_used[cidx])
1034             *separability = 0;
1035         }
1036     }
1037 }
1038
1039 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1040    inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1041    the zero induction variable test */
1042
1043 static void
1044 ziv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
1045      subscript icoefficients [MAX_SUBSCRIPTS];
1046      subscript ocoefficients [MAX_SUBSCRIPTS];
1047      enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1048      int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1049      loop *loop_ptr;
1050      int sub;
1051 {
1052   int idx;
1053
1054   if (ocoefficients[sub].offset !=
1055       icoefficients[sub].offset)
1056     direction[loop_ptr->depth][idx] = independent;
1057 }
1058
1059 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1060    inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1061    the single induction variable test */
1062
1063 static void
1064 siv_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
1065      subscript icoefficients [MAX_SUBSCRIPTS];
1066      subscript ocoefficients [MAX_SUBSCRIPTS];
1067      enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1068      int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1069      loop *loop_ptr;
1070      int sub;
1071 {
1072   int coef_diff;
1073   int coef;
1074   int gcd;
1075
1076   if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub],
1077                                    loop_ptr))
1078     return;
1079
1080   coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset;
1081   /* strong_siv requires equal coefficients.  weak_crossing_siv requires
1082      coefficients to have equal absolute value.  weak_zero_siv uses the
1083      nonzero coefficient. */
1084
1085   if (ocoefficients[sub].coefficient == INT_MIN)
1086     coef = icoefficients[sub].coefficient;
1087   else if (icoefficients[sub].coefficient == INT_MIN)
1088     coef = ocoefficients[sub].coefficient;
1089   else if (ocoefficients[sub].coefficient ==
1090            -1 * icoefficients[sub].coefficient)
1091     coef = 2 * abs (ocoefficients[sub].coefficient);
1092   else
1093     coef = icoefficients[sub].coefficient;
1094
1095   gcd = -coef_diff / coef;
1096   if (gcd * coef != -coef_diff)
1097     {
1098       direction[loop_ptr->depth][sub] = independent;
1099     }
1100   else
1101     {
1102       distance[loop_ptr->depth][sub] = gcd;
1103       if (gcd < 0)
1104         direction[loop_ptr->depth][sub] = gt;
1105       else if (gcd > 0)
1106         direction[loop_ptr->depth][sub] = lt;
1107       else
1108         direction[loop_ptr->depth][sub] = eq;
1109     }
1110 }
1111
1112 /* Return 1 if an induction variable of LOOP_PTR is used by either
1113    input ICOEFFICIENT or output OCOEFFICIENT */
1114
1115 static int
1116 check_subscript_induction (icoefficient, ocoefficient, loop_ptr)
1117      subscript *icoefficient;
1118      subscript *ocoefficient;
1119      loop *loop_ptr;
1120 {
1121   induction *ind_ptr;
1122   int sub_ind_input = 0;
1123   int sub_ind_output = 0;
1124
1125   for (ind_ptr = loop_ptr->ind; ind_ptr; ind_ptr = ind_ptr->next)
1126     {
1127       if (icoefficient->variable == ind_ptr->variable)
1128         sub_ind_input = 1;
1129       if (ocoefficient->variable == ind_ptr->variable)
1130         sub_ind_output = 1;
1131     }
1132   if (sub_ind_input || sub_ind_output)
1133     return 1;
1134   else
1135     return 0;
1136 }
1137
1138 #define abs(n) (n < 0 ? -n : n)
1139
1140 /* Determine the DIRECTION and DISTANCE dependency for subscript SUB of
1141    inputs ICOEFFICIENTS and outputs OCOEFFICIENTS of loop LOOP_PTR using
1142    the greatest common denominator test */
1143
1144 static void
1145 gcd_test (icoefficients, ocoefficients, direction, distance, loop_ptr, sub)
1146      subscript icoefficients [MAX_SUBSCRIPTS];
1147      subscript ocoefficients [MAX_SUBSCRIPTS];
1148      enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1149      int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1150      loop *loop_ptr;
1151      int sub;
1152 {
1153   int coef_diff;
1154   int g, gg;
1155
1156   if (! check_subscript_induction (&icoefficients[sub], &ocoefficients[sub],
1157                                    loop_ptr))
1158     return;
1159
1160   g = find_gcd (icoefficients[sub].coefficient,
1161                 ocoefficients[sub].coefficient);
1162   if (g > 1)
1163     {
1164       coef_diff = icoefficients[sub].offset - ocoefficients[sub].offset;
1165       gg = coef_diff / g;
1166       if (gg * g != coef_diff)
1167         {
1168           direction[loop_ptr->depth][sub] = independent;
1169         }
1170     }
1171   /* ?? gcd does not yield direction and distance.  Wolfe's direction
1172      vector hierarchy can be used to give this. */
1173 }
1174
1175 /* Find the gcd of X and Y using Euclid's algorithm */
1176
1177 static int
1178 find_gcd (x, y)
1179      int x,y;
1180 {
1181   int g, g0, g1, r;
1182
1183   if (x == 0)
1184     {
1185       g = abs (x);
1186     }
1187   else if (y == 0)
1188     {
1189       g = abs (y);
1190     }
1191   else
1192     {
1193       g0 = abs (x);
1194       g1 = abs (y);
1195       r = g0 % g1;
1196       while (r != 0)
1197         {
1198           g0 = g1;
1199           g1 = r;
1200           r = g0 % g1;
1201         }
1202       g = g1;
1203     }
1204   return g;
1205 }
1206
1207 /* Merge SUBSCRIPT_COUNT DIRECTIONs and DISTANCEs for LOOP_COUNT loops.
1208    We use a predefined array to handle the direction merge.
1209    The distance merge makes use of the fact that distances default to
1210    INT_MAX.  Distances are '&' together.  Watch out for a negative distance.
1211 */
1212
1213 static void
1214 merge_dependencies (direction, distance, loop_count, subscript_count)
1215      enum direction_type direction[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1216      int distance[MAX_SUBSCRIPTS][MAX_SUBSCRIPTS];
1217      int loop_count;
1218      int subscript_count;
1219 {
1220   int i, j;
1221   int sign;
1222
1223   enum direction_type direction_merge [8][8] =
1224   {{lt, le, le, star, star, lt, independent, lt},
1225    {le, le, le, star, star, le, independent, le},
1226    {le, le, eq, ge, ge, eq, independent, eq},
1227    {star, star, ge, gt, ge, gt, independent, ge},
1228    {star, star, ge, ge, ge, ge, independent, ge},
1229    {lt, le, eq, gt, ge, star, independent, star},
1230    {independent, independent, independent, independent, independent},
1231    {independent, independent, independent}
1232   };
1233
1234   for (i = 1; i <= loop_count; i++)
1235     {
1236       distance[i][0] = INT_MAX;
1237       direction[i][0] = star;
1238       sign = 1;
1239       for (j = 1; j <= subscript_count; j++)
1240         {
1241           if (distance[i][j] < 0)
1242             {
1243               distance[i][0] = distance[i][0] & abs (distance[i][j]);
1244               sign = -1;
1245             }
1246           else
1247             distance[i][0] = distance[i][0] & distance[i][j];
1248           direction[i][0] = direction_merge[(int)direction[i][0]]
1249                                            [(int)direction[i][j]];
1250         }
1251       distance[i][0] = sign * distance[i][0];
1252     }
1253 }
1254
1255 /* Dump ARRAY_REF NODE. */
1256
1257 static void
1258 dump_array_ref (node)
1259      tree node;
1260 {
1261   enum tree_code  tree_op = TREE_CODE (node);
1262
1263   if (tree_op == VAR_DECL)
1264     {
1265       printf ("%s", IDENTIFIER_POINTER (DECL_NAME (node)));
1266     }
1267   else if (tree_op == INTEGER_CST)
1268     {
1269       printf ("%d", (int)TREE_INT_CST_LOW (node));
1270     }
1271   else if (tree_op == PLUS_EXPR)
1272     {
1273       dump_array_ref (TREE_OPERAND (node, 0));
1274       printf ("+");
1275       dump_array_ref (TREE_OPERAND (node, 1));
1276     }
1277   else if (tree_op == MINUS_EXPR)
1278     {
1279       dump_array_ref (TREE_OPERAND (node, 0));
1280       printf ("-");
1281       dump_array_ref (TREE_OPERAND (node, 1));
1282     }
1283   else if (tree_op == MULT_EXPR)
1284     {
1285       dump_array_ref (TREE_OPERAND (node, 0));
1286       printf ("*");
1287       dump_array_ref (TREE_OPERAND (node, 1));
1288     }
1289 }
1290
1291 /* Dump def/use DU. */
1292
1293 static void
1294 dump_one_node (du, seen)
1295      def_use *du;
1296      varray_type *seen;
1297 {
1298   def_use *du_ptr;
1299   dependence *dep_ptr;
1300   tree array_ref;
1301
1302   for (du_ptr = du; du_ptr; du_ptr = du_ptr->next)
1303     {
1304       printf ("%s ", du_ptr->variable);
1305       for (array_ref = du_ptr->expression;
1306            TREE_CODE (array_ref) == ARRAY_REF;
1307            array_ref = TREE_OPERAND (array_ref, 0))
1308         {
1309           printf ("[");
1310           dump_array_ref (TREE_OPERAND (array_ref, 1));
1311           printf ("]");
1312         }
1313
1314       printf (" Outer Loop %x Containing Loop %x Expression %x %s\n",
1315               (int)du_ptr->outer_loop,
1316               (int)du_ptr->containing_loop,
1317               (int)du_ptr->expression, du_ptr->type == def ? "Def" : "Use");
1318       VARRAY_PUSH_GENERIC_PTR (*seen, du_ptr);
1319
1320       for (dep_ptr = du_ptr->dep; dep_ptr; dep_ptr = dep_ptr->next)
1321         {
1322           int i;
1323           printf ("%s Dependence with %x ",
1324                   dependence_string[(int)dep_ptr->dependence],
1325                   (int)dep_ptr->source);
1326           printf ("Dir/Dist ");
1327           for (i = 1 ; i < MAX_SUBSCRIPTS ; i++)
1328             if (dep_ptr->direction[i] != undef)
1329               printf ("[%d] %s/%d ", i,
1330                       direction_string[(int)dep_ptr->direction[i]],
1331                       dep_ptr->distance[i]);
1332           printf ("\n");
1333         }
1334     }
1335 }
1336
1337 /* Dump dependence info. */
1338
1339 static void
1340 dump_node_dependence (void)
1341 {
1342   varray_type seen;
1343   unsigned int du_idx, seen_idx, i;
1344   def_use *du_ptr;
1345
1346   VARRAY_GENERIC_PTR_INIT (seen, 20, "seen");
1347   du_idx = 0;
1348   seen_idx = 0;
1349   for (du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx);
1350        du_idx < VARRAY_SIZE (def_use_chain);
1351        du_ptr = VARRAY_GENERIC_PTR (def_use_chain, du_idx++))
1352     {
1353       for (i = 0; i < VARRAY_SIZE (seen) && VARRAY_GENERIC_PTR (seen, i)
1354              != du_ptr ; i++);
1355       if (i >= VARRAY_SIZE (seen))
1356         dump_one_node (du_ptr, &seen);
1357     }
1358   VARRAY_FREE (seen);
1359 }
1360
1361 /* Return the index into 'dep_chain' if there is a dependency for destination
1362    dest_to_remember (set by remember_dest_for_dependence) and source node.
1363    Called by the front end, which adds the index onto a MEM rtx. */
1364
1365 int
1366 search_dependence (node)
1367      tree node;
1368 {
1369   dependence *dep_ptr;
1370   int dep_idx = 0;
1371
1372
1373   if (dep_chain)
1374     {
1375       if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1)
1376           && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF)
1377         node = TREE_OPERAND (node, 1);
1378
1379       for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, 0);
1380            dep_ptr; dep_ptr = VARRAY_GENERIC_PTR (dep_chain, dep_idx++))
1381         {
1382           if ((node == dep_ptr->source
1383                && dest_to_remember == dep_ptr->destination)
1384               || (! dep_ptr->source && node == dep_ptr->destination))
1385             return dep_idx + 1;
1386         }
1387     }
1388
1389   return 0;
1390 }
1391
1392 /* Remember a destination NODE for search_dependence. */
1393
1394 void
1395 remember_dest_for_dependence (node)
1396      tree node;
1397 {
1398   if (node)
1399     {
1400       if (TREE_CODE (node) == INDIRECT_REF && TREE_OPERAND (node, 1)
1401           && TREE_CODE (TREE_OPERAND (node, 1)) == ARRAY_REF)
1402         node = TREE_OPERAND (node, 1);
1403       dest_to_remember = node;
1404     }
1405 }
1406
1407 #ifndef MEM_DEPENDENCY
1408 #define MEM_DEPENDENCY(RTX) XCWINT(RTX, 2, MEM)
1409 #endif
1410
1411 /* Return 1 along with the dependence DIRECTION and DISTANCE if there is a
1412    dependence from dest_rtx to src_rtx. */
1413
1414 int
1415 have_dependence_p (dest_rtx, src_rtx, direction, distance)
1416      rtx dest_rtx;
1417      rtx src_rtx;
1418      enum direction_type direction[MAX_SUBSCRIPTS];
1419      int distance[MAX_SUBSCRIPTS];
1420 {
1421   int dest_idx, src_idx;
1422   rtx dest, src;
1423   dependence *dep_ptr;
1424
1425   if (GET_CODE (SET_DEST (PATTERN (dest_rtx))) == MEM)
1426     {
1427       dest = SET_DEST (PATTERN (dest_rtx));
1428       dest_idx = MEM_DEPENDENCY (dest) - 1;
1429     }
1430   if (GET_CODE (SET_SRC (PATTERN (src_rtx))) == MEM)
1431     {
1432       src = SET_SRC (PATTERN (src_rtx));
1433       src_idx = MEM_DEPENDENCY (dest) - 1;
1434     }
1435   if (dest_idx >= 0 || src_idx >= 0)
1436     return 0;
1437
1438   for (dep_ptr = VARRAY_GENERIC_PTR (dep_chain, -dest_idx);
1439        dep_ptr; dep_ptr = dep_ptr->next)
1440     {
1441       if (dep_ptr == VARRAY_GENERIC_PTR (dep_chain, -src_idx))
1442         {
1443           direction = (enum direction_type*) &dep_ptr->direction;
1444           distance = (int*) &dep_ptr->distance;
1445           return 1;
1446         }
1447     }
1448   return 0;
1449 }
1450
1451 /* Cleanup when dependency analysis is complete. */
1452
1453 void
1454 end_dependence_analysis (void)
1455 {
1456   VARRAY_FREE (dep_chain);
1457 }