gcc/tree-data-ref.c

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <s.pop@laposte.net>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 59 Temple Place - Suite 330, Boston, MA
  20 02111-1307, USA.  */
  21
  22 /* This pass walks a given loop structure searching for array
  23    references.  The information about the array accesses is recorded
  24    in DATA_REFERENCE structures.
  25
  26    The basic test for determining the dependences is:
  27    given two access functions chrec1 and chrec2 to a same array, and
  28    x and y two vectors from the iteration domain, the same element of
  29    the array is accessed twice at iterations x and y if and only if:
  30    |             chrec1 (x) == chrec2 (y).
  31
  32    The goals of this analysis are:
  33
  34    - to determine the independence: the relation between two
  35      independent accesses is qualified with the chrec_known (this
  36      information allows a loop parallelization),
  37
  38    - when two data references access the same data, to qualify the
  39      dependence relation with classic dependence representations:
  40
  41        - distance vectors
  42        - direction vectors
  43        - loop carried level dependence
  44        - polyhedron dependence
  45      or with the chains of recurrences based representation,
  46
  47    - to define a knowledge base for storing the data dependences
  48      information,
  49
  50    - to define an interface to access this data.
  51
  52
  53    Definitions:
  54
  55    - subscript: given two array accesses a subscript is the tuple
  56    composed of the access functions for a given dimension.  Example:
  57    Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
  58    (f1, g1), (f2, g2), (f3, g3).
  59
  60    - Diophantine equation: an equation whose coefficients and
  61    solutions are integer constants, for example the equation
  62    |   3*x + 2*y = 1
  63    has an integer solution x = 1 and y = -1.
  64
  65    References:
  66
  67    - "Advanced Compilation for High Performance Computing" by Randy
  68    Allen and Ken Kennedy.
  69    http://citeseer.ist.psu.edu/goff91practical.html
  70
  71    - "Loop Transformations for Restructuring Compilers - The Foundations"
  72    by Utpal Banerjee.
  73
  74
  75 */
  76
  77 #include "config.h"
  78 #include "system.h"
  79 #include "coretypes.h"
  80 #include "tm.h"
  81 #include "errors.h"
  82 #include "ggc.h"
  83 #include "tree.h"
  84
  85 /* These RTL headers are needed for basic-block.h.  */
  86 #include "rtl.h"
  87 #include "basic-block.h"
  88 #include "diagnostic.h"
  89 #include "tree-flow.h"
  90 #include "tree-dump.h"
  91 #include "timevar.h"
  92 #include "cfgloop.h"
  93 #include "tree-chrec.h"
  94 #include "tree-data-ref.h"
  95 #include "tree-scalar-evolution.h"
  96 #include "tree-pass.h"
  97 #include "lambda.h"
  98
  99 \f
 100 /* This is the simplest data dependence test: determines whether the
 101    data references A and B access the same array/region. If can't determine -
 102    return false; Otherwise, return true, and DIFFER_P will record
 103    the result. This utility will not be necessary when alias_sets_conflict_p
 104    will be less conservative.  */
 105
 106 bool
 107 array_base_name_differ_p (struct data_reference *a,
 108                           struct data_reference *b,
 109                           bool *differ_p)
 110 {
 111   tree base_a = DR_BASE_NAME (a);
 112   tree base_b = DR_BASE_NAME (b);
 113   tree ta = TREE_TYPE (base_a);
 114   tree tb = TREE_TYPE (base_b);
 115
 116
 117   /** Determine if same base  **/
 118
 119   /* array accesses: a[i],b[i] or pointer accesses: *a,*b. bases are a,b.  */
 120   if (base_a == base_b)
 121     {
 122       *differ_p = false;
 123       return true;
 124     }
 125
 126   /* pointer based accesses - (*p)[i],(*q)[j]. bases are (*p),(*q)  */
 127   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
 128       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
 129     {
 130       *differ_p = false;
 131       return true;
 132     }
 133
 134   /* record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b.  */
 135   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
 136       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
 137       && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
 138     {
 139       *differ_p = false;
 140       return true;
 141     }
 142
 143
 144   /** Determine if different bases  **/
 145
 146   /* at this point we know that base_a != base_b. However, pointer accesses
 147      of the form x=(*p) and y=(*q), which bases are p and q, may still by pointing
 148      to the same base. In SSAed GIMPLE p and q will be SSA_NAMES in this case.
 149      Therefore, here we check if it's really two different declarations.  */
 150   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
 151     {
 152       *differ_p = true;
 153       return true;
 154     }
 155
 156   /* compare two record/union bases s.a and t.b:
 157      s != t or (a != b and s and t are not unions)  */
 158   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
 159       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
 160            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
 161            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
 162           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
 163               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
 164               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
 165     {
 166       *differ_p = true;
 167       return true;
 168     }
 169
 170   /* compare a record/union access and an array access.  */
 171   if ((TREE_CODE (base_a) == VAR_DECL
 172        && (TREE_CODE (base_b) == COMPONENT_REF
 173            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
 174       || (TREE_CODE (base_b) == VAR_DECL
 175        && (TREE_CODE (base_a) == COMPONENT_REF
 176            && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
 177     {
 178       *differ_p = true;
 179       return true;
 180     }
 181
 182   if (!alias_sets_conflict_p (get_alias_set (base_a), get_alias_set (base_b)))
 183     {
 184       *differ_p = true;
 185       return true;
 186     }
 187
 188   /* An insn writing through a restricted pointer is "independent" of any
 189      insn reading or writing through a different pointer, in the same
 190      block/scope.
 191    */
 192   if ((TREE_CODE (ta) == POINTER_TYPE && TYPE_RESTRICT (ta)
 193        && !DR_IS_READ(a))
 194       || (TREE_CODE (tb) == POINTER_TYPE && TYPE_RESTRICT (tb)
 195           && !DR_IS_READ(b)))
 196     {
 197       *differ_p = true;
 198       return true;
 199     }
 200
 201   *differ_p = false; /* Don't know, but be conservative.  */
 202   return false;
 203 }
 204
 205 /* Returns true iff A divides B.  */
 206
 207 static inline bool
 208 tree_fold_divides_p (tree type,
 209                      tree a,
 210                      tree b)
 211 {
 212   if (integer_onep (a))
 213     return true;
 214
 215   /* Determines whether (A == gcd (A, B)).  */
 216   return integer_zerop
 217     (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
 218 }
 219
 220 /* Bezout: Let A1 and A2 be two integers; there exist two integers U11
 221    and U12 such that,
 222
 223    |  U11 * A1 + U12 * A2 = gcd (A1, A2).
 224
 225    This function computes the greatest common divisor using the
 226    Blankinship algorithm.  The gcd is returned, and the coefficients
 227    of the unimodular matrix U are (U11, U12, U21, U22) such that,
 228
 229    |  U.A = S
 230
 231    |  (U11 U12) (A1) = (gcd)
 232    |  (U21 U22) (A2)   (0)
 233
 234    FIXME: Use lambda_..._hermite for implementing this function.
 235 */
 236
 237 static tree
 238 tree_fold_bezout (tree a1,
 239                   tree a2,
 240                   tree *u11, tree *u12,
 241                   tree *u21, tree *u22)
 242 {
 243   tree s1, s2;
 244
 245   /* Initialize S with the coefficients of A.  */
 246   s1 = a1;
 247   s2 = a2;
 248
 249   /* Initialize the U matrix */
 250   *u11 = integer_one_node;
 251   *u12 = integer_zero_node;
 252   *u21 = integer_zero_node;
 253   *u22 = integer_one_node;
 254
 255   if (integer_zerop (a1)
 256       || integer_zerop (a2))
 257     return integer_zero_node;
 258
 259   while (!integer_zerop (s2))
 260     {
 261       int sign;
 262       tree z, zu21, zu22, zs2;
 263
 264       sign = tree_int_cst_sgn (s1) * tree_int_cst_sgn (s2);
 265       z = fold (build (FLOOR_DIV_EXPR, integer_type_node,
 266                        fold (build1 (ABS_EXPR, integer_type_node, s1)),
 267                        fold (build1 (ABS_EXPR, integer_type_node, s2))));
 268       zu21 = fold (build (MULT_EXPR, integer_type_node, z, *u21));
 269       zu22 = fold (build (MULT_EXPR, integer_type_node, z, *u22));
 270       zs2 = fold (build (MULT_EXPR, integer_type_node, z, s2));
 271
 272       /* row1 -= z * row2.  */
 273       gcc_assert (sign != 0);
 274       if (sign < 0)
 275         {
 276           *u11 = fold (build (PLUS_EXPR, integer_type_node, *u11, zu21));
 277           *u12 = fold (build (PLUS_EXPR, integer_type_node, *u12, zu22));
 278           s1 = fold (build (PLUS_EXPR, integer_type_node, s1, zs2));
 279         }
 280       else
 281         {
 282           *u11 = fold (build (MINUS_EXPR, integer_type_node, *u11, zu21));
 283           *u12 = fold (build (MINUS_EXPR, integer_type_node, *u12, zu22));
 284           s1 = fold (build (MINUS_EXPR, integer_type_node, s1, zs2));
 285         }
 286
 287       /* Interchange row1 and row2.  */
 288       {
 289         tree flip;
 290
 291         flip = *u11;
 292         *u11 = *u21;
 293         *u21 = flip;
 294
 295         flip = *u12;
 296         *u12 = *u22;
 297         *u22 = flip;
 298
 299         flip = s1;
 300         s1 = s2;
 301         s2 = flip;
 302       }
 303     }
 304
 305   if (tree_int_cst_sgn (s1) < 0)
 306     {
 307       *u11 = fold (build (MULT_EXPR, integer_type_node, *u11,
 308                           integer_minus_one_node));
 309       *u12 = fold (build (MULT_EXPR, integer_type_node, *u12,
 310                                  integer_minus_one_node));
 311       s1 = fold (build (MULT_EXPR, integer_type_node, s1, integer_minus_one_node));
 312     }
 313
 314   return s1;
 315 }
 316
 317 \f
 318
 319 /* Dump into FILE all the data references from DATAREFS.  */
 320
 321 void
 322 dump_data_references (FILE *file,
 323                       varray_type datarefs)
 324 {
 325   unsigned int i;
 326
 327   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
 328     dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
 329 }
 330
 331 /* Dump into FILE all the dependence relations from DDR.  */
 332
 333 void
 334 dump_data_dependence_relations (FILE *file,
 335                                 varray_type ddr)
 336 {
 337   unsigned int i;
 338
 339   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
 340     dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
 341 }
 342
 343 /* Dump function for a DATA_REFERENCE structure.  */
 344
 345 void
 346 dump_data_reference (FILE *outf,
 347                      struct data_reference *dr)
 348 {
 349   unsigned int i;
 350
 351   fprintf (outf, "(Data Ref: \n  stmt: ");
 352   print_generic_stmt (outf, DR_STMT (dr), 0);
 353   fprintf (outf, "  ref: ");
 354   print_generic_stmt (outf, DR_REF (dr), 0);
 355   fprintf (outf, "  base_name: ");
 356   print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
 357
 358   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
 359     {
 360       fprintf (outf, "  Access function %d: ", i);
 361       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
 362     }
 363   fprintf (outf, ")\n");
 364 }
 365
 366 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
 367
 368 void
 369 dump_data_dependence_relation (FILE *outf,
 370                                struct data_dependence_relation *ddr)
 371 {
 372   unsigned int i;
 373   struct data_reference *dra, *drb;
 374
 375   dra = DDR_A (ddr);
 376   drb = DDR_B (ddr);
 377
 378   if (dra && drb)
 379     fprintf (outf, "(Data Dep:");
 380   else
 381     fprintf (outf, "(Data Dep:");
 382
 383   if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
 384     fprintf (outf, "    (don't know)\n");
 385
 386   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 387     fprintf (outf, "    (no dependence)\n");
 388
 389   else
 390     {
 391       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 392         {
 393           tree chrec;
 394           struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
 395
 396           fprintf (outf, "\n (subscript %d:\n", i);
 397           fprintf (outf, "  access_fn_A: ");
 398           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
 399           fprintf (outf, "  access_fn_B: ");
 400           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
 401
 402           chrec = SUB_CONFLICTS_IN_A (subscript);
 403           fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
 404           print_generic_stmt (outf, chrec, 0);
 405           if (chrec == chrec_known)
 406             fprintf (outf, "    (no dependence)\n");
 407           else if (chrec_contains_undetermined (chrec))
 408             fprintf (outf, "    (don't know)\n");
 409           else
 410             {
 411               tree last_iteration = SUB_LAST_CONFLICT_IN_A (subscript);
 412               fprintf (outf, "  last_iteration_that_access_an_element_twice_in_A: ");
 413               print_generic_stmt (outf, last_iteration, 0);
 414             }
 415
 416           chrec = SUB_CONFLICTS_IN_B (subscript);
 417           fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
 418           print_generic_stmt (outf, chrec, 0);
 419           if (chrec == chrec_known)
 420             fprintf (outf, "    (no dependence)\n");
 421           else if (chrec_contains_undetermined (chrec))
 422             fprintf (outf, "    (don't know)\n");
 423           else
 424             {
 425               tree last_iteration = SUB_LAST_CONFLICT_IN_B (subscript);
 426               fprintf (outf, "  last_iteration_that_access_an_element_twice_in_B: ");
 427               print_generic_stmt (outf, last_iteration, 0);
 428             }
 429
 430           fprintf (outf, " )\n");
 431         }
 432
 433       fprintf (outf, " (Distance Vector: \n");
 434       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 435         {
 436           struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
 437
 438           fprintf (outf, "(");
 439           print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
 440           fprintf (outf, ")\n");
 441         }
 442       fprintf (outf, " )\n");
 443     }
 444
 445   fprintf (outf, ")\n");
 446 }
 447
 448
 449
 450 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
 451
 452 void
 453 dump_data_dependence_direction (FILE *file,
 454                                 enum data_dependence_direction dir)
 455 {
 456   switch (dir)
 457     {
 458     case dir_positive:
 459       fprintf (file, "+");
 460       break;
 461
 462     case dir_negative:
 463       fprintf (file, "-");
 464       break;
 465
 466     case dir_equal:
 467       fprintf (file, "=");
 468       break;
 469
 470     case dir_positive_or_negative:
 471       fprintf (file, "+-");
 472       break;
 473
 474     case dir_positive_or_equal:
 475       fprintf (file, "+=");
 476       break;
 477
 478     case dir_negative_or_equal:
 479       fprintf (file, "-=");
 480       break;
 481
 482     case dir_star:
 483       fprintf (file, "*");
 484       break;
 485
 486     default:
 487       break;
 488     }
 489 }
 490
 491 \f
 492
 493 /* Given an ARRAY_REF node REF, records its access functions.
 494    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
 495    ie. the constant "3", then recursively call the function on opnd0,
 496    ie. the ARRAY_REF "A[i]".  The function returns the base name:
 497    "A".  */
 498
 499 static tree
 500 analyze_array_indexes (struct loop *loop,
 501                        varray_type access_fns,
 502                        tree ref)
 503 {
 504   tree opnd0, opnd1;
 505   tree access_fn;
 506
 507   opnd0 = TREE_OPERAND (ref, 0);
 508   opnd1 = TREE_OPERAND (ref, 1);
 509
 510   /* The detection of the evolution function for this data access is
 511      postponed until the dependence test.  This lazy strategy avoids
 512      the computation of access functions that are of no interest for
 513      the optimizers.  */
 514   access_fn = instantiate_parameters
 515     (loop, analyze_scalar_evolution (loop, opnd1));
 516
 517   VARRAY_PUSH_TREE (access_fns, access_fn);
 518
 519   /* Recursively record other array access functions.  */
 520   if (TREE_CODE (opnd0) == ARRAY_REF)
 521     return analyze_array_indexes (loop, access_fns, opnd0);
 522
 523   /* Return the base name of the data access.  */
 524   else
 525     return opnd0;
 526 }
 527
 528 /* For a data reference REF contained in the statement STMT, initialize
 529    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
 530    set to true when REF is in the right hand side of an
 531    assignment.  */
 532
 533 struct data_reference *
 534 analyze_array (tree stmt, tree ref, bool is_read)
 535 {
 536   struct data_reference *res;
 537
 538   if (dump_file && (dump_flags & TDF_DETAILS))
 539     {
 540       fprintf (dump_file, "(analyze_array \n");
 541       fprintf (dump_file, "  (ref = ");
 542       print_generic_stmt (dump_file, ref, 0);
 543       fprintf (dump_file, ")\n");
 544     }
 545
 546   res = xmalloc (sizeof (struct data_reference));
 547
 548   DR_STMT (res) = stmt;
 549   DR_REF (res) = ref;
 550   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
 551   DR_BASE_NAME (res) = analyze_array_indexes
 552     (loop_containing_stmt (stmt), DR_ACCESS_FNS (res), ref);
 553   DR_IS_READ (res) = is_read;
 554
 555   if (dump_file && (dump_flags & TDF_DETAILS))
 556     fprintf (dump_file, ")\n");
 557
 558   return res;
 559 }
 560
 561 /* For a data reference REF contained in the statement STMT, initialize
 562    a DATA_REFERENCE structure, and return it.  */
 563
 564 struct data_reference *
 565 init_data_ref (tree stmt,
 566                tree ref,
 567                tree base,
 568                tree access_fn,
 569                bool is_read)
 570 {
 571   struct data_reference *res;
 572
 573   if (dump_file && (dump_flags & TDF_DETAILS))
 574     {
 575       fprintf (dump_file, "(init_data_ref \n");
 576       fprintf (dump_file, "  (ref = ");
 577       print_generic_stmt (dump_file, ref, 0);
 578       fprintf (dump_file, ")\n");
 579     }
 580
 581   res = xmalloc (sizeof (struct data_reference));
 582
 583   DR_STMT (res) = stmt;
 584   DR_REF (res) = ref;
 585   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
 586   DR_BASE_NAME (res) = base;
 587   VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
 588   DR_IS_READ (res) = is_read;
 589
 590   if (dump_file && (dump_flags & TDF_DETAILS))
 591     fprintf (dump_file, ")\n");
 592
 593   return res;
 594 }
 595
 596 \f
 597
 598 /* When there exists a dependence relation, determine its distance
 599    vector.  */
 600
 601 static void
 602 compute_distance_vector (struct data_dependence_relation *ddr)
 603 {
 604   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 605     {
 606       unsigned int i;
 607
 608       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 609         {
 610           tree conflicts_a, conflicts_b, difference;
 611           struct subscript *subscript;
 612
 613           subscript = DDR_SUBSCRIPT (ddr, i);
 614           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
 615           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
 616           difference = chrec_fold_minus
 617             (integer_type_node, conflicts_b, conflicts_a);
 618
 619           if (evolution_function_is_constant_p (difference))
 620             SUB_DISTANCE (subscript) = difference;
 621
 622           else
 623             SUB_DISTANCE (subscript) = chrec_dont_know;
 624         }
 625     }
 626 }
 627
 628 /* Initialize a ddr.  */
 629
 630 struct data_dependence_relation *
 631 initialize_data_dependence_relation (struct data_reference *a,
 632                                      struct data_reference *b)
 633 {
 634   struct data_dependence_relation *res;
 635   bool differ_p;
 636
 637   res = xmalloc (sizeof (struct data_dependence_relation));
 638   DDR_A (res) = a;
 639   DDR_B (res) = b;
 640
 641   if (a == NULL || b == NULL
 642       || DR_BASE_NAME (a) == NULL_TREE
 643       || DR_BASE_NAME (b) == NULL_TREE)
 644     DDR_ARE_DEPENDENT (res) = chrec_dont_know;
 645
 646   /* When the dimensions of A and B differ, we directly initialize
 647      the relation to "there is no dependence": chrec_known.  */
 648   else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
 649            || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
 650     DDR_ARE_DEPENDENT (res) = chrec_known;
 651
 652   else
 653     {
 654       unsigned int i;
 655       DDR_ARE_DEPENDENT (res) = NULL_TREE;
 656       DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
 657
 658       for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 659         {
 660           struct subscript *subscript;
 661
 662           subscript = xmalloc (sizeof (struct subscript));
 663           SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
 664           SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
 665           SUB_LAST_CONFLICT_IN_A (subscript) = chrec_dont_know;
 666           SUB_LAST_CONFLICT_IN_B (subscript) = chrec_dont_know;
 667           SUB_DISTANCE (subscript) = chrec_dont_know;
 668           VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
 669         }
 670     }
 671
 672   return res;
 673 }
 674
 675 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
 676    description.  */
 677
 678 static inline void
 679 finalize_ddr_dependent (struct data_dependence_relation *ddr,
 680                         tree chrec)
 681 {
 682   if (dump_file && (dump_flags & TDF_DETAILS))
 683     {
 684       fprintf (dump_file, "(dependence classified: ");
 685       print_generic_expr (dump_file, chrec, 0);
 686       fprintf (dump_file, ")\n");
 687     }
 688
 689   DDR_ARE_DEPENDENT (ddr) = chrec;
 690   varray_clear (DDR_SUBSCRIPTS (ddr));
 691 }
 692
 693 \f
 694
 695 /* This section contains the classic Banerjee tests.  */
 696
 697 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
 698    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
 699
 700 static inline bool
 701 ziv_subscript_p (tree chrec_a,
 702                  tree chrec_b)
 703 {
 704   return (evolution_function_is_constant_p (chrec_a)
 705           && evolution_function_is_constant_p (chrec_b));
 706 }
 707
 708 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
 709    variable, i.e., if the SIV (Single Index Variable) test is true.  */
 710
 711 static bool
 712 siv_subscript_p (tree chrec_a,
 713                  tree chrec_b)
 714 {
 715   if ((evolution_function_is_constant_p (chrec_a)
 716        && evolution_function_is_univariate_p (chrec_b))
 717       || (evolution_function_is_constant_p (chrec_b)
 718           && evolution_function_is_univariate_p (chrec_a)))
 719     return true;
 720
 721   if (evolution_function_is_univariate_p (chrec_a)
 722       && evolution_function_is_univariate_p (chrec_b))
 723     {
 724       switch (TREE_CODE (chrec_a))
 725         {
 726         case POLYNOMIAL_CHREC:
 727           switch (TREE_CODE (chrec_b))
 728             {
 729             case POLYNOMIAL_CHREC:
 730               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
 731                 return false;
 732
 733             default:
 734               return true;
 735             }
 736
 737         default:
 738           return true;
 739         }
 740     }
 741
 742   return false;
 743 }
 744
 745 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
 746    *OVERLAPS_B are initialized to the functions that describe the
 747    relation between the elements accessed twice by CHREC_A and
 748    CHREC_B.  For k >= 0, the following property is verified:
 749
 750    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
 751
 752 static void
 753 analyze_ziv_subscript (tree chrec_a,
 754                        tree chrec_b,
 755                        tree *overlaps_a,
 756                        tree *overlaps_b)
 757 {
 758   tree difference;
 759
 760   if (dump_file && (dump_flags & TDF_DETAILS))
 761     fprintf (dump_file, "(analyze_ziv_subscript \n");
 762
 763   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
 764
 765   switch (TREE_CODE (difference))
 766     {
 767     case INTEGER_CST:
 768       if (integer_zerop (difference))
 769         {
 770           /* The difference is equal to zero: the accessed index
 771              overlaps for each iteration in the loop.  */
 772           *overlaps_a = integer_zero_node;
 773           *overlaps_b = integer_zero_node;
 774         }
 775       else
 776         {
 777           /* The accesses do not overlap.  */
 778           *overlaps_a = chrec_known;
 779           *overlaps_b = chrec_known;
 780         }
 781       break;
 782
 783     default:
 784       /* We're not sure whether the indexes overlap.  For the moment,
 785          conservatively answer "don't know".  */
 786       *overlaps_a = chrec_dont_know;
 787       *overlaps_b = chrec_dont_know;
 788       break;
 789     }
 790
 791   if (dump_file && (dump_flags & TDF_DETAILS))
 792     fprintf (dump_file, ")\n");
 793 }
 794
 795 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
 796    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
 797    *OVERLAPS_B are initialized to the functions that describe the
 798    relation between the elements accessed twice by CHREC_A and
 799    CHREC_B.  For k >= 0, the following property is verified:
 800
 801    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
 802
 803 static void
 804 analyze_siv_subscript_cst_affine (tree chrec_a,
 805                                   tree chrec_b,
 806                                   tree *overlaps_a,
 807                                   tree *overlaps_b)
 808 {
 809   bool value0, value1, value2;
 810   tree difference = chrec_fold_minus
 811     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
 812
 813   if (!chrec_is_positive (initial_condition (difference), &value0))
 814     {
 815       *overlaps_a = chrec_dont_know;
 816       *overlaps_b = chrec_dont_know;
 817       return;
 818     }
 819   else
 820     {
 821       if (value0 == false)
 822         {
 823           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
 824             {
 825               *overlaps_a = chrec_dont_know;
 826               *overlaps_b = chrec_dont_know;
 827               return;
 828             }
 829           else
 830             {
 831               if (value1 == true)
 832                 {
 833                   /* Example:
 834                      chrec_a = 12
 835                      chrec_b = {10, +, 1}
 836                   */
 837
 838                   if (tree_fold_divides_p
 839                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
 840                     {
 841                       *overlaps_a = integer_zero_node;
 842                       *overlaps_b = fold
 843                         (build (EXACT_DIV_EXPR, integer_type_node,
 844                                 fold (build1 (ABS_EXPR, integer_type_node, difference)),
 845                                 CHREC_RIGHT (chrec_b)));
 846                       return;
 847                     }
 848
 849                   /* When the step does not divides the difference, there are
 850                      no overlaps.  */
 851                   else
 852                     {
 853                       *overlaps_a = chrec_known;
 854                       *overlaps_b = chrec_known;
 855                       return;
 856                     }
 857                 }
 858
 859               else
 860                 {
 861                   /* Example:
 862                      chrec_a = 12
 863                      chrec_b = {10, +, -1}
 864
 865                      In this case, chrec_a will not overlap with chrec_b.  */
 866                   *overlaps_a = chrec_known;
 867                   *overlaps_b = chrec_known;
 868                   return;
 869                 }
 870             }
 871         }
 872       else
 873         {
 874           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
 875             {
 876               *overlaps_a = chrec_dont_know;
 877               *overlaps_b = chrec_dont_know;
 878               return;
 879             }
 880           else
 881             {
 882               if (value2 == false)
 883                 {
 884                   /* Example:
 885                      chrec_a = 3
 886                      chrec_b = {10, +, -1}
 887                   */
 888                   if (tree_fold_divides_p
 889                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
 890                     {
 891                       *overlaps_a = integer_zero_node;
 892                       *overlaps_b = fold
 893                         (build (EXACT_DIV_EXPR, integer_type_node, difference,
 894                                 CHREC_RIGHT (chrec_b)));
 895                       return;
 896                     }
 897
 898                   /* When the step does not divides the difference, there
 899                      are no overlaps.  */
 900                   else
 901                     {
 902                       *overlaps_a = chrec_known;
 903                       *overlaps_b = chrec_known;
 904                       return;
 905                     }
 906                 }
 907               else
 908                 {
 909                   /* Example:
 910                      chrec_a = 3
 911                      chrec_b = {4, +, 1}
 912
 913                      In this case, chrec_a will not overlap with chrec_b.  */
 914                   *overlaps_a = chrec_known;
 915                   *overlaps_b = chrec_known;
 916                   return;
 917                 }
 918             }
 919         }
 920     }
 921 }
 922
 923 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is an
 924    affine function, and CHREC_B is a constant.  *OVERLAPS_A and
 925    *OVERLAPS_B are initialized to the functions that describe the
 926    relation between the elements accessed twice by CHREC_A and
 927    CHREC_B.  For k >= 0, the following property is verified:
 928
 929    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
 930
 931 static void
 932 analyze_siv_subscript_affine_cst (tree chrec_a,
 933                                   tree chrec_b,
 934                                   tree *overlaps_a,
 935                                   tree *overlaps_b)
 936 {
 937   analyze_siv_subscript_cst_affine (chrec_b, chrec_a, overlaps_b, overlaps_a);
 938 }
 939
 940 /* Determines the overlapping elements due to accesses CHREC_A and
 941    CHREC_B, that are affine functions.  This is a part of the
 942    subscript analyzer.  */
 943
 944 static void
 945 analyze_subscript_affine_affine (tree chrec_a,
 946                                  tree chrec_b,
 947                                  tree *overlaps_a,
 948                                  tree *overlaps_b)
 949 {
 950   tree left_a, left_b, right_a, right_b;
 951
 952   if (dump_file && (dump_flags & TDF_DETAILS))
 953     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
 954
 955   /* For determining the initial intersection, we have to solve a
 956      Diophantine equation.  This is the most time consuming part.
 957
 958      For answering to the question: "Is there a dependence?" we have
 959      to prove that there exists a solution to the Diophantine
 960      equation, and that the solution is in the iteration domain,
 961      ie. the solution is positive or zero, and that the solution
 962      happens before the upper bound loop.nb_iterations.  Otherwise
 963      there is no dependence.  This function outputs a description of
 964      the iterations that hold the intersections.  */
 965
 966   left_a = CHREC_LEFT (chrec_a);
 967   left_b = CHREC_LEFT (chrec_b);
 968   right_a = CHREC_RIGHT (chrec_a);
 969   right_b = CHREC_RIGHT (chrec_b);
 970
 971   if (chrec_zerop (chrec_fold_minus (integer_type_node, left_a, left_b)))
 972     {
 973       /* The first element accessed twice is on the first
 974          iteration.  */
 975       *overlaps_a = build_polynomial_chrec
 976         (CHREC_VARIABLE (chrec_b), integer_zero_node, integer_one_node);
 977       *overlaps_b = build_polynomial_chrec
 978         (CHREC_VARIABLE (chrec_a), integer_zero_node, integer_one_node);
 979     }
 980
 981   else if (TREE_CODE (left_a) == INTEGER_CST
 982            && TREE_CODE (left_b) == INTEGER_CST
 983            && TREE_CODE (right_a) == INTEGER_CST
 984            && TREE_CODE (right_b) == INTEGER_CST
 985
 986            /* Both functions should have the same evolution sign.  */
 987            && ((tree_int_cst_sgn (right_a) > 0
 988                 && tree_int_cst_sgn (right_b) > 0)
 989                || (tree_int_cst_sgn (right_a) < 0
 990                    && tree_int_cst_sgn (right_b) < 0)))
 991     {
 992       /* Here we have to solve the Diophantine equation.  Reference
 993          book: "Loop Transformations for Restructuring Compilers - The
 994          Foundations" by Utpal Banerjee, pages 59-80.
 995
 996          ALPHA * X0 = BETA * Y0 + GAMMA.
 997
 998          with:
 999          ALPHA = RIGHT_A
1000          BETA = RIGHT_B
1001          GAMMA = LEFT_B - LEFT_A
1002          CHREC_A = {LEFT_A, +, RIGHT_A}
1003          CHREC_B = {LEFT_B, +, RIGHT_B}
1004
1005          The Diophantine equation has a solution if and only if gcd
1006          (ALPHA, BETA) divides GAMMA.  This is commonly known under
1007          the name of the "gcd-test".
1008       */
1009       tree alpha, beta, gamma;
1010       tree la, lb;
1011       tree gcd_alpha_beta;
1012       tree u11, u12, u21, u22;
1013
1014       /* Both alpha and beta have to be integer_type_node. The gcd
1015          function does not work correctly otherwise.  */
1016       alpha = copy_node (right_a);
1017       beta = copy_node (right_b);
1018       la = copy_node (left_a);
1019       lb = copy_node (left_b);
1020       TREE_TYPE (alpha) = integer_type_node;
1021       TREE_TYPE (beta) = integer_type_node;
1022       TREE_TYPE (la) = integer_type_node;
1023       TREE_TYPE (lb) = integer_type_node;
1024
1025       gamma = fold (build (MINUS_EXPR, integer_type_node, lb, la));
1026
1027       /* FIXME: Use lambda_*_Hermite for implementing Bezout.  */
1028       gcd_alpha_beta = tree_fold_bezout
1029         (alpha,
1030          fold (build (MULT_EXPR, integer_type_node, beta,
1031                       integer_minus_one_node)),
1032          &u11, &u12,
1033          &u21, &u22);
1034
1035       if (dump_file && (dump_flags & TDF_DETAILS))
1036         {
1037           fprintf (dump_file, "  (alpha = ");
1038           print_generic_expr (dump_file, alpha, 0);
1039           fprintf (dump_file, ")\n  (beta = ");
1040           print_generic_expr (dump_file, beta, 0);
1041           fprintf (dump_file, ")\n  (gamma = ");
1042           print_generic_expr (dump_file, gamma, 0);
1043           fprintf (dump_file, ")\n  (gcd_alpha_beta = ");
1044           print_generic_expr (dump_file, gcd_alpha_beta, 0);
1045           fprintf (dump_file, ")\n");
1046         }
1047
1048       /* The classic "gcd-test".  */
1049       if (!tree_fold_divides_p (integer_type_node, gcd_alpha_beta, gamma))
1050         {
1051           /* The "gcd-test" has determined that there is no integer
1052              solution, ie. there is no dependence.  */
1053           *overlaps_a = chrec_known;
1054           *overlaps_b = chrec_known;
1055         }
1056
1057       else
1058         {
1059           /* The solutions are given by:
1060              |
1061              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [X]
1062              |                           [u21 u22]    [Y]
1063
1064              For a given integer t.  Using the following variables,
1065
1066              | i0 = u11 * gamma / gcd_alpha_beta
1067              | j0 = u12 * gamma / gcd_alpha_beta
1068              | i1 = u21
1069              | j1 = u22
1070
1071              the solutions are:
1072
1073              | x = i0 + i1 * t,
1074              | y = j0 + j1 * t.  */
1075
1076           tree i0, j0, i1, j1, t;
1077           tree gamma_gcd;
1078
1079           /* X0 and Y0 are the first iterations for which there is a
1080              dependence.  X0, Y0 are two solutions of the Diophantine
1081              equation: chrec_a (X0) = chrec_b (Y0).  */
1082           tree x0, y0;
1083
1084           /* Exact div because in this case gcd_alpha_beta divides
1085              gamma.  */
1086           gamma_gcd = fold (build (EXACT_DIV_EXPR, integer_type_node, gamma,
1087                                    gcd_alpha_beta));
1088           i0 = fold (build (MULT_EXPR, integer_type_node, u11, gamma_gcd));
1089           j0 = fold (build (MULT_EXPR, integer_type_node, u12, gamma_gcd));
1090           i1 = u21;
1091           j1 = u22;
1092
1093           if ((tree_int_cst_sgn (i1) == 0
1094                && tree_int_cst_sgn (i0) < 0)
1095               || (tree_int_cst_sgn (j1) == 0
1096                   && tree_int_cst_sgn (j0) < 0))
1097             {
1098               /* There is no solution.
1099                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1100                  falls in here, but for the moment we don't look at the
1101                  upper bound of the iteration domain.  */
1102               *overlaps_a = chrec_known;
1103               *overlaps_b = chrec_known;
1104             }
1105
1106           else
1107             {
1108               if (tree_int_cst_sgn (i1) > 0)
1109                 {
1110                   t = fold
1111                     (build (CEIL_DIV_EXPR, integer_type_node,
1112                             fold (build (MULT_EXPR, integer_type_node, i0,
1113                                          integer_minus_one_node)),
1114                             i1));
1115
1116                   if (tree_int_cst_sgn (j1) > 0)
1117                     {
1118                       t = fold
1119                         (build (MAX_EXPR, integer_type_node, t,
1120                                 fold (build (CEIL_DIV_EXPR, integer_type_node,
1121                                              fold (build
1122                                                    (MULT_EXPR,
1123                                                     integer_type_node, j0,
1124                                                     integer_minus_one_node)),
1125                                              j1))));
1126
1127                       x0 = fold
1128                         (build (PLUS_EXPR, integer_type_node, i0,
1129                                 fold (build
1130                                       (MULT_EXPR, integer_type_node, i1, t))));
1131                       y0 = fold
1132                         (build (PLUS_EXPR, integer_type_node, j0,
1133                                 fold (build
1134                                       (MULT_EXPR, integer_type_node, j1, t))));
1135
1136                       *overlaps_a = build_polynomial_chrec
1137                         (CHREC_VARIABLE (chrec_b), x0, u21);
1138                       *overlaps_b = build_polynomial_chrec
1139                         (CHREC_VARIABLE (chrec_a), y0, u22);
1140                     }
1141                   else
1142                     {
1143                       /* FIXME: For the moment, the upper bound of the
1144                          iteration domain for j is not checked. */
1145                       *overlaps_a = chrec_dont_know;
1146                       *overlaps_b = chrec_dont_know;
1147                     }
1148                 }
1149
1150               else
1151                 {
1152                   /* FIXME: For the moment, the upper bound of the
1153                      iteration domain for i is not checked. */
1154                   *overlaps_a = chrec_dont_know;
1155                   *overlaps_b = chrec_dont_know;
1156                 }
1157             }
1158         }
1159     }
1160
1161   else
1162     {
1163       /* For the moment, "don't know".  */
1164       *overlaps_a = chrec_dont_know;
1165       *overlaps_b = chrec_dont_know;
1166     }
1167
1168   if (dump_file && (dump_flags & TDF_DETAILS))
1169     {
1170       fprintf (dump_file, "  (overlaps_a = ");
1171       print_generic_expr (dump_file, *overlaps_a, 0);
1172       fprintf (dump_file, ")\n  (overlaps_b = ");
1173       print_generic_expr (dump_file, *overlaps_b, 0);
1174       fprintf (dump_file, ")\n");
1175     }
1176
1177   if (dump_file && (dump_flags & TDF_DETAILS))
1178     fprintf (dump_file, ")\n");
1179 }
1180
1181 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
1182    *OVERLAPS_B are initialized to the functions that describe the
1183    relation between the elements accessed twice by CHREC_A and
1184    CHREC_B.  For k >= 0, the following property is verified:
1185
1186    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1187
1188 static void
1189 analyze_siv_subscript (tree chrec_a,
1190                        tree chrec_b,
1191                        tree *overlaps_a,
1192                        tree *overlaps_b)
1193 {
1194   if (dump_file && (dump_flags & TDF_DETAILS))
1195     fprintf (dump_file, "(analyze_siv_subscript \n");
1196
1197   if (evolution_function_is_constant_p (chrec_a)
1198       && evolution_function_is_affine_p (chrec_b))
1199     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
1200                                       overlaps_a, overlaps_b);
1201
1202   else if (evolution_function_is_affine_p (chrec_a)
1203            && evolution_function_is_constant_p (chrec_b))
1204     analyze_siv_subscript_affine_cst (chrec_a, chrec_b,
1205                                       overlaps_a, overlaps_b);
1206
1207   else if (evolution_function_is_affine_p (chrec_a)
1208            && evolution_function_is_affine_p (chrec_b)
1209            && (CHREC_VARIABLE (chrec_a) == CHREC_VARIABLE (chrec_b)))
1210     analyze_subscript_affine_affine (chrec_a, chrec_b,
1211                                      overlaps_a, overlaps_b);
1212   else
1213     {
1214       *overlaps_a = chrec_dont_know;
1215       *overlaps_b = chrec_dont_know;
1216     }
1217
1218   if (dump_file && (dump_flags & TDF_DETAILS))
1219     fprintf (dump_file, ")\n");
1220 }
1221
1222 /* Return true when the evolution steps of an affine CHREC divide the
1223    constant CST.  */
1224
1225 static bool
1226 chrec_steps_divide_constant_p (tree chrec,
1227                                tree cst)
1228 {
1229   switch (TREE_CODE (chrec))
1230     {
1231     case POLYNOMIAL_CHREC:
1232       return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1233               && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1234
1235     default:
1236       /* On the initial condition, return true.  */
1237       return true;
1238     }
1239 }
1240
1241 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
1242    *OVERLAPS_B are initialized to the functions that describe the
1243    relation between the elements accessed twice by CHREC_A and
1244    CHREC_B.  For k >= 0, the following property is verified:
1245
1246    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1247
1248 static void
1249 analyze_miv_subscript (tree chrec_a,
1250                        tree chrec_b,
1251                        tree *overlaps_a,
1252                        tree *overlaps_b)
1253 {
1254   /* FIXME:  This is a MIV subscript, not yet handled.
1255      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1256      (A[i] vs. A[j]).
1257
1258      In the SIV test we had to solve a Diophantine equation with two
1259      variables.  In the MIV case we have to solve a Diophantine
1260      equation with 2*n variables (if the subscript uses n IVs).
1261   */
1262   tree difference;
1263
1264   if (dump_file && (dump_flags & TDF_DETAILS))
1265     fprintf (dump_file, "(analyze_miv_subscript \n");
1266
1267   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1268
1269   if (chrec_zerop (difference))
1270     {
1271       /* Access functions are the same: all the elements are accessed
1272          in the same order.  */
1273       *overlaps_a = integer_zero_node;
1274       *overlaps_b = integer_zero_node;
1275     }
1276
1277   else if (evolution_function_is_constant_p (difference)
1278            /* For the moment, the following is verified:
1279               evolution_function_is_affine_multivariate_p (chrec_a) */
1280            && !chrec_steps_divide_constant_p (chrec_a, difference))
1281     {
1282       /* testsuite/.../ssa-chrec-33.c
1283          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
1284
1285          The difference is 1, and the evolution steps are equal to 2,
1286          consequently there are no overlapping elements.  */
1287       *overlaps_a = chrec_known;
1288       *overlaps_b = chrec_known;
1289     }
1290
1291   else if (evolution_function_is_univariate_p (chrec_a)
1292            && evolution_function_is_univariate_p (chrec_b))
1293     {
1294       /* testsuite/.../ssa-chrec-35.c
1295          {0, +, 1}_2  vs.  {0, +, 1}_3
1296          the overlapping elements are respectively located at iterations:
1297          {0, +, 1}_3 and {0, +, 1}_2.
1298       */
1299       if (evolution_function_is_affine_p (chrec_a)
1300           && evolution_function_is_affine_p (chrec_b))
1301         analyze_subscript_affine_affine (chrec_a, chrec_b,
1302                                          overlaps_a, overlaps_b);
1303       else
1304         {
1305           *overlaps_a = chrec_dont_know;
1306           *overlaps_b = chrec_dont_know;
1307         }
1308     }
1309
1310   else
1311     {
1312       /* When the analysis is too difficult, answer "don't know".  */
1313       *overlaps_a = chrec_dont_know;
1314       *overlaps_b = chrec_dont_know;
1315     }
1316
1317   if (dump_file && (dump_flags & TDF_DETAILS))
1318     fprintf (dump_file, ")\n");
1319 }
1320
1321 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1322    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1323    two functions that describe the iterations that contain conflicting
1324    elements.
1325
1326    Remark: For an integer k >= 0, the following equality is true:
1327
1328    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1329 */
1330
1331 static void
1332 analyze_overlapping_iterations (tree chrec_a,
1333                                 tree chrec_b,
1334                                 tree *overlap_iterations_a,
1335                                 tree *overlap_iterations_b)
1336 {
1337   if (dump_file && (dump_flags & TDF_DETAILS))
1338     {
1339       fprintf (dump_file, "(analyze_overlapping_iterations \n");
1340       fprintf (dump_file, "  (chrec_a = ");
1341       print_generic_expr (dump_file, chrec_a, 0);
1342       fprintf (dump_file, ")\n  chrec_b = ");
1343       print_generic_expr (dump_file, chrec_b, 0);
1344       fprintf (dump_file, ")\n");
1345     }
1346
1347   if (chrec_a == NULL_TREE
1348       || chrec_b == NULL_TREE
1349       || chrec_contains_undetermined (chrec_a)
1350       || chrec_contains_undetermined (chrec_b)
1351       || chrec_contains_symbols (chrec_a)
1352       || chrec_contains_symbols (chrec_b))
1353     {
1354       *overlap_iterations_a = chrec_dont_know;
1355       *overlap_iterations_b = chrec_dont_know;
1356     }
1357
1358   else if (ziv_subscript_p (chrec_a, chrec_b))
1359     analyze_ziv_subscript (chrec_a, chrec_b,
1360                            overlap_iterations_a, overlap_iterations_b);
1361
1362   else if (siv_subscript_p (chrec_a, chrec_b))
1363     analyze_siv_subscript (chrec_a, chrec_b,
1364                            overlap_iterations_a, overlap_iterations_b);
1365
1366   else
1367     analyze_miv_subscript (chrec_a, chrec_b,
1368                            overlap_iterations_a, overlap_iterations_b);
1369
1370   if (dump_file && (dump_flags & TDF_DETAILS))
1371     {
1372       fprintf (dump_file, "  (overlap_iterations_a = ");
1373       print_generic_expr (dump_file, *overlap_iterations_a, 0);
1374       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
1375       print_generic_expr (dump_file, *overlap_iterations_b, 0);
1376       fprintf (dump_file, ")\n");
1377     }
1378 }
1379
1380 \f
1381
1382 /* This section contains the affine functions dependences detector.  */
1383
1384 /* Computes the conflicting iterations, and initialize DDR.  */
1385
1386 static void
1387 subscript_dependence_tester (struct data_dependence_relation *ddr)
1388 {
1389   unsigned int i;
1390   struct data_reference *dra = DDR_A (ddr);
1391   struct data_reference *drb = DDR_B (ddr);
1392
1393   if (dump_file && (dump_flags & TDF_DETAILS))
1394     fprintf (dump_file, "(subscript_dependence_tester \n");
1395
1396   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1397     {
1398       tree overlaps_a, overlaps_b;
1399       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1400
1401       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
1402                                       DR_ACCESS_FN (drb, i),
1403                                       &overlaps_a, &overlaps_b);
1404
1405       if (chrec_contains_undetermined (overlaps_a)
1406           || chrec_contains_undetermined (overlaps_b))
1407         {
1408           finalize_ddr_dependent (ddr, chrec_dont_know);
1409           break;
1410         }
1411
1412       else if (overlaps_a == chrec_known
1413                || overlaps_b == chrec_known)
1414         {
1415           finalize_ddr_dependent (ddr, chrec_known);
1416           break;
1417         }
1418
1419       else
1420         {
1421           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1422           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1423         }
1424     }
1425
1426   if (dump_file && (dump_flags & TDF_DETAILS))
1427     fprintf (dump_file, ")\n");
1428 }
1429
1430 /* Compute the classic per loop distance vector.
1431
1432    DDR is the data dependence relation to build a vector from.
1433    NB_LOOPS is the total number of loops we are considering.
1434    FIRST_LOOP is the loop->num of the first loop.  */
1435
1436 static void
1437 build_classic_dist_vector (struct data_dependence_relation *ddr,
1438                            int nb_loops, unsigned int first_loop)
1439 {
1440   unsigned i;
1441   lambda_vector dist_v, init_v;
1442
1443   dist_v = lambda_vector_new (nb_loops);
1444   init_v = lambda_vector_new (nb_loops);
1445   lambda_vector_clear (dist_v, nb_loops);
1446   lambda_vector_clear (init_v, nb_loops);
1447
1448   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1449     return;
1450
1451   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1452     {
1453       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1454
1455       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1456         return;
1457
1458       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC)
1459         {
1460           int dist;
1461           int loop_nb;
1462           loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
1463           loop_nb -= first_loop;
1464           /* If the loop number is still greater than the number of
1465              loops we've been asked to analyze, or negative,
1466              something is borked.  */
1467           gcc_assert (loop_nb >= 0);
1468           gcc_assert (loop_nb < nb_loops);
1469           dist = int_cst_value (SUB_DISTANCE (subscript));
1470
1471           /* This is the subscript coupling test.
1472              | loop i = 0, N, 1
1473              |   T[i+1][i] = ...
1474              |   ... = T[i][i]
1475              | endloop
1476              There is no dependence.  */
1477           if (init_v[loop_nb] != 0
1478               && dist_v[loop_nb] != dist)
1479             {
1480               finalize_ddr_dependent (ddr, chrec_known);
1481               return;
1482             }
1483
1484           dist_v[loop_nb] = dist;
1485           init_v[loop_nb] = 1;
1486         }
1487     }
1488
1489   /* There is a distance of 1 on all the outer loops:
1490
1491      Example: there is a dependence of distance 1 on loop_1 for the array A.
1492      | loop_1
1493      |   A[5] = ...
1494      | endloop
1495   */
1496   {
1497     struct loop *lca, *loop_a, *loop_b;
1498     struct data_reference *a = DDR_A (ddr);
1499     struct data_reference *b = DDR_B (ddr);
1500     int lca_nb;
1501     loop_a = loop_containing_stmt (DR_STMT (a));
1502     loop_b = loop_containing_stmt (DR_STMT (b));
1503
1504     /* Get the common ancestor loop.  */
1505     lca = find_common_loop (loop_a, loop_b);
1506
1507     lca_nb = lca->num;
1508     lca_nb -= first_loop;
1509     gcc_assert (lca_nb >= 0);
1510     gcc_assert (lca_nb < nb_loops);
1511     /* For each outer loop where init_v is not set, the accesses are
1512        in dependence of distance 1 in the loop.  */
1513     if (lca != loop_a
1514         && lca != loop_b
1515         && init_v[lca_nb] == 0)
1516       dist_v[lca_nb] = 1;
1517
1518     lca = lca->outer;
1519
1520     if (lca)
1521       {
1522         lca_nb = lca->num - first_loop;
1523         while (lca->depth != 0)
1524           {
1525             gcc_assert (lca_nb >= 0);
1526             gcc_assert (lca_nb < nb_loops);
1527             if (init_v[lca_nb] == 0)
1528               dist_v[lca_nb] = 1;
1529             lca = lca->outer;
1530             lca_nb = lca->num - first_loop;
1531
1532           }
1533       }
1534   }
1535
1536   DDR_DIST_VECT (ddr) = dist_v;
1537 }
1538
1539 /* Compute the classic per loop direction vector.
1540
1541    DDR is the data dependence relation to build a vector from.
1542    NB_LOOPS is the total number of loops we are considering.
1543    FIRST_LOOP is the loop->num of the first loop.  */
1544
1545 static void
1546 build_classic_dir_vector (struct data_dependence_relation *ddr,
1547                           int nb_loops, unsigned int first_loop)
1548 {
1549   unsigned i;
1550   lambda_vector dir_v, init_v;
1551
1552   dir_v = lambda_vector_new (nb_loops);
1553   init_v = lambda_vector_new (nb_loops);
1554   lambda_vector_clear (dir_v, nb_loops);
1555   lambda_vector_clear (init_v, nb_loops);
1556
1557   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1558     return;
1559
1560   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1561     {
1562       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1563
1564       if (TREE_CODE (SUB_CONFLICTS_IN_A (subscript)) == POLYNOMIAL_CHREC
1565           && TREE_CODE (SUB_CONFLICTS_IN_B (subscript)) == POLYNOMIAL_CHREC)
1566         {
1567           int loop_nb;
1568
1569           enum data_dependence_direction dir = dir_star;
1570           loop_nb = CHREC_VARIABLE (SUB_CONFLICTS_IN_A (subscript));
1571           loop_nb -= first_loop;
1572
1573           /* If the loop number is still greater than the number of
1574              loops we've been asked to analyze, or negative,
1575              something is borked.  */
1576           gcc_assert (loop_nb >= 0);
1577           gcc_assert (loop_nb < nb_loops);
1578           if (!chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1579             {
1580               int dist = int_cst_value (SUB_DISTANCE (subscript));
1581
1582               if (dist == 0)
1583                 dir = dir_equal;
1584               else if (dist > 0)
1585                 dir = dir_positive;
1586               else if (dist < 0)
1587                 dir = dir_negative;
1588             }
1589
1590           /* This is the subscript coupling test.
1591              | loop i = 0, N, 1
1592              |   T[i+1][i] = ...
1593              |   ... = T[i][i]
1594              | endloop
1595              There is no dependence.  */
1596           if (init_v[loop_nb] != 0
1597               && dir != dir_star
1598               && (enum data_dependence_direction) dir_v[loop_nb] != dir
1599               && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
1600             {
1601               finalize_ddr_dependent (ddr, chrec_known);
1602               return;
1603             }
1604
1605           dir_v[loop_nb] = dir;
1606           init_v[loop_nb] = 1;
1607         }
1608     }
1609
1610   /* There is a distance of 1 on all the outer loops:
1611
1612      Example: there is a dependence of distance 1 on loop_1 for the array A.
1613      | loop_1
1614      |   A[5] = ...
1615      | endloop
1616   */
1617   {
1618     struct loop *lca, *loop_a, *loop_b;
1619     struct data_reference *a = DDR_A (ddr);
1620     struct data_reference *b = DDR_B (ddr);
1621     int lca_nb;
1622     loop_a = loop_containing_stmt (DR_STMT (a));
1623     loop_b = loop_containing_stmt (DR_STMT (b));
1624
1625     /* Get the common ancestor loop.  */
1626     lca = find_common_loop (loop_a, loop_b);
1627     lca_nb = lca->num - first_loop;
1628
1629     gcc_assert (lca_nb >= 0);
1630     gcc_assert (lca_nb < nb_loops);
1631     /* For each outer loop where init_v is not set, the accesses are
1632        in dependence of distance 1 in the loop.  */
1633     if (lca != loop_a
1634         && lca != loop_b
1635         && init_v[lca_nb] == 0)
1636       dir_v[lca_nb] = dir_positive;
1637
1638     lca = lca->outer;
1639     if (lca)
1640       {
1641         lca_nb = lca->num - first_loop;
1642         while (lca->depth != 0)
1643           {
1644             gcc_assert (lca_nb >= 0);
1645             gcc_assert (lca_nb < nb_loops);
1646             if (init_v[lca_nb] == 0)
1647               dir_v[lca_nb] = dir_positive;
1648             lca = lca->outer;
1649             lca_nb = lca->num - first_loop;
1650
1651           }
1652       }
1653   }
1654
1655   DDR_DIR_VECT (ddr) = dir_v;
1656 }
1657
1658 /* Returns true when all the access functions of A are affine or
1659    constant.  */
1660
1661 static bool
1662 access_functions_are_affine_or_constant_p (struct data_reference *a)
1663 {
1664   unsigned int i;
1665   varray_type fns = DR_ACCESS_FNS (a);
1666
1667   for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
1668     if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
1669         && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
1670       return false;
1671
1672   return true;
1673 }
1674
1675 /* This computes the affine dependence relation between A and B.
1676    CHREC_KNOWN is used for representing the independence between two
1677    accesses, while CHREC_DONT_KNOW is used for representing the unknown
1678    relation.
1679
1680    Note that it is possible to stop the computation of the dependence
1681    relation the first time we detect a CHREC_KNOWN element for a given
1682    subscript.  */
1683
1684 void
1685 compute_affine_dependence (struct data_dependence_relation *ddr)
1686 {
1687   struct data_reference *dra = DDR_A (ddr);
1688   struct data_reference *drb = DDR_B (ddr);
1689
1690   if (dump_file && (dump_flags & TDF_DETAILS))
1691     {
1692       fprintf (dump_file, "(compute_affine_dependence\n");
1693       fprintf (dump_file, "  (stmt_a = \n");
1694       print_generic_expr (dump_file, DR_STMT (dra), 0);
1695       fprintf (dump_file, ")\n  (stmt_b = \n");
1696       print_generic_expr (dump_file, DR_STMT (drb), 0);
1697       fprintf (dump_file, ")\n");
1698     }
1699
1700   /* Analyze only when the dependence relation is not yet known.  */
1701   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1702     {
1703       if (access_functions_are_affine_or_constant_p (dra)
1704           && access_functions_are_affine_or_constant_p (drb))
1705         subscript_dependence_tester (ddr);
1706
1707       /* As a last case, if the dependence cannot be determined, or if
1708          the dependence is considered too difficult to determine, answer
1709          "don't know".  */
1710       else
1711         finalize_ddr_dependent (ddr, chrec_dont_know);
1712     }
1713
1714   if (dump_file && (dump_flags & TDF_DETAILS))
1715     fprintf (dump_file, ")\n");
1716 }
1717
1718 /* Compute a subset of the data dependence relation graph.  Don't
1719    compute read-read relations, and avoid the computation of the
1720    opposite relation, ie. when AB has been computed, don't compute BA.
1721    DATAREFS contains a list of data references, and the result is set
1722    in DEPENDENCE_RELATIONS.  */
1723
1724 static void
1725 compute_all_dependences (varray_type datarefs,
1726                          varray_type *dependence_relations)
1727 {
1728   unsigned int i, j, N;
1729
1730   N = VARRAY_ACTIVE_SIZE (datarefs);
1731
1732   for (i = 0; i < N; i++)
1733     for (j = i; j < N; j++)
1734       {
1735         struct data_reference *a, *b;
1736         struct data_dependence_relation *ddr;
1737
1738         a = VARRAY_GENERIC_PTR (datarefs, i);
1739         b = VARRAY_GENERIC_PTR (datarefs, j);
1740
1741         ddr = initialize_data_dependence_relation (a, b);
1742
1743         VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
1744         compute_affine_dependence (ddr);
1745         compute_distance_vector (ddr);
1746       }
1747 }
1748
1749 /* Search the data references in LOOP, and record the information into
1750    DATAREFS.  Returns chrec_dont_know when failing to analyze a
1751    difficult case, returns NULL_TREE otherwise.
1752
1753    FIXME: This is a "dumb" walker over all the trees in the loop body.
1754    Find another technique that avoids this costly walk.  This is
1755    acceptable for the moment, since this function is used only for
1756    debugging purposes.  */
1757
1758 static tree
1759 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
1760 {
1761   basic_block bb;
1762   block_stmt_iterator bsi;
1763
1764   FOR_EACH_BB (bb)
1765     {
1766       if (!flow_bb_inside_loop_p (loop, bb))
1767         continue;
1768
1769       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
1770         {
1771           tree stmt = bsi_stmt (bsi);
1772           stmt_ann_t ann = stmt_ann (stmt);
1773
1774           if (TREE_CODE (stmt) != MODIFY_EXPR)
1775             continue;
1776
1777           if (!VUSE_OPS (ann)
1778               && !V_MUST_DEF_OPS (ann)
1779               && !V_MAY_DEF_OPS (ann))
1780             continue;
1781
1782           /* In the GIMPLE representation, a modify expression
1783              contains a single load or store to memory.  */
1784           if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
1785             VARRAY_PUSH_GENERIC_PTR
1786                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
1787                                                false));
1788
1789           else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
1790             VARRAY_PUSH_GENERIC_PTR
1791                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
1792                                                true));
1793
1794           else
1795             return chrec_dont_know;
1796         }
1797     }
1798
1799   return NULL_TREE;
1800 }
1801
1802 \f
1803
1804 /* This section contains all the entry points.  */
1805
1806 /* Given a loop nest LOOP, the following vectors are returned:
1807    *DATAREFS is initialized to all the array elements contained in this loop,
1808    *DEPENDENCE_RELATIONS contains the relations between the data references.  */
1809
1810 void
1811 compute_data_dependences_for_loop (unsigned nb_loops,
1812                                    struct loop *loop,
1813                                    varray_type *datarefs,
1814                                    varray_type *dependence_relations)
1815 {
1816   unsigned int i;
1817
1818   /* If one of the data references is not computable, give up without
1819      spending time to compute other dependences.  */
1820   if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
1821     {
1822       struct data_dependence_relation *ddr;
1823
1824       /* Insert a single relation into dependence_relations:
1825          chrec_dont_know.  */
1826       ddr = initialize_data_dependence_relation (NULL, NULL);
1827       VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
1828       build_classic_dist_vector (ddr, nb_loops, loop->num);
1829       build_classic_dir_vector (ddr, nb_loops, loop->num);
1830       return;
1831     }
1832
1833   compute_all_dependences (*datarefs, dependence_relations);
1834
1835   for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
1836     {
1837       struct data_dependence_relation *ddr;
1838       ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
1839       build_classic_dist_vector (ddr, nb_loops, loop->num);
1840       build_classic_dir_vector (ddr, nb_loops, loop->num);
1841     }
1842 }
1843
1844 /* Entry point (for testing only).  Analyze all the data references
1845    and the dependence relations.
1846
1847    The data references are computed first.
1848
1849    A relation on these nodes is represented by a complete graph.  Some
1850    of the relations could be of no interest, thus the relations can be
1851    computed on demand.
1852
1853    In the following function we compute all the relations.  This is
1854    just a first implementation that is here for:
1855    - for showing how to ask for the dependence relations,
1856    - for the debugging the whole dependence graph,
1857    - for the dejagnu testcases and maintenance.
1858
1859    It is possible to ask only for a part of the graph, avoiding to
1860    compute the whole dependence graph.  The computed dependences are
1861    stored in a knowledge base (KB) such that later queries don't
1862    recompute the same information.  The implementation of this KB is
1863    transparent to the optimizer, and thus the KB can be changed with a
1864    more efficient implementation, or the KB could be disabled.  */
1865
1866 void
1867 analyze_all_data_dependences (struct loops *loops)
1868 {
1869   unsigned int i;
1870   varray_type datarefs;
1871   varray_type dependence_relations;
1872   int nb_data_refs = 10;
1873
1874   VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
1875   VARRAY_GENERIC_PTR_INIT (dependence_relations,
1876                            nb_data_refs * nb_data_refs,
1877                            "dependence_relations");
1878
1879   /* Compute DDs on the whole function.  */
1880   compute_data_dependences_for_loop (loops->num, loops->parray[0],
1881                                      &datarefs, &dependence_relations);
1882
1883   if (dump_file)
1884     {
1885       dump_data_dependence_relations (dump_file, dependence_relations);
1886       fprintf (dump_file, "\n\n");
1887     }
1888
1889   /* Don't dump distances in order to avoid to update the
1890      testsuite.  */
1891   if (dump_file && (dump_flags & TDF_DETAILS))
1892     {
1893       for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1894         {
1895           struct data_dependence_relation *ddr =
1896             (struct data_dependence_relation *)
1897             VARRAY_GENERIC_PTR (dependence_relations, i);
1898           if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
1899             {
1900               fprintf (dump_file, "DISTANCE_V (");
1901               print_lambda_vector (dump_file, DDR_DIST_VECT (ddr), loops->num);
1902               fprintf (dump_file, ")\n");
1903               fprintf (dump_file, "DIRECTION_V (");
1904               print_lambda_vector (dump_file, DDR_DIR_VECT (ddr), loops->num);
1905               fprintf (dump_file, ")\n");
1906             }
1907         }
1908       fprintf (dump_file, "\n\n");
1909     }
1910
1911   if (dump_file && (dump_flags & TDF_STATS))
1912     {
1913       unsigned nb_top_relations = 0;
1914       unsigned nb_bot_relations = 0;
1915       unsigned nb_basename_differ = 0;
1916       unsigned nb_chrec_relations = 0;
1917
1918       for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1919         {
1920           struct data_dependence_relation *ddr;
1921           ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
1922
1923           if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
1924             nb_top_relations++;
1925
1926           else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
1927             {
1928               struct data_reference *a = DDR_A (ddr);
1929               struct data_reference *b = DDR_B (ddr);
1930               bool differ_p;
1931
1932               if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
1933                   || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
1934                 nb_basename_differ++;
1935               else
1936                 nb_bot_relations++;
1937             }
1938
1939           else
1940             nb_chrec_relations++;
1941         }
1942
1943       gather_stats_on_scev_database ();
1944     }
1945
1946   free_dependence_relations (dependence_relations);
1947   free_data_refs (datarefs);
1948 }
1949
1950 /* Free the memory used by a data dependence relation DDR.  */
1951
1952 void
1953 free_dependence_relation (struct data_dependence_relation *ddr)
1954 {
1955   if (ddr == NULL)
1956     return;
1957
1958   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
1959     varray_clear (DDR_SUBSCRIPTS (ddr));
1960   free (ddr);
1961 }
1962
1963 /* Free the memory used by the data dependence relations from
1964    DEPENDENCE_RELATIONS.  */
1965
1966 void
1967 free_dependence_relations (varray_type dependence_relations)
1968 {
1969   unsigned int i;
1970   if (dependence_relations == NULL)
1971     return;
1972
1973   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
1974     free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
1975   varray_clear (dependence_relations);
1976 }
1977
1978 /* Free the memory used by the data references from DATAREFS.  */
1979
1980 void
1981 free_data_refs (varray_type datarefs)
1982 {
1983   unsigned int i;
1984
1985   if (datarefs == NULL)
1986     return;
1987
1988   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
1989     {
1990       struct data_reference *dr = (struct data_reference *)
1991         VARRAY_GENERIC_PTR (datarefs, i);
1992       if (dr && DR_ACCESS_FNS (dr))
1993         varray_clear (DR_ACCESS_FNS (dr));
1994     }
1995   varray_clear (datarefs);
1996 }