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