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