gcc/dependence.c

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