gcc/dependence.c

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