gcc/dependence.c

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