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