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