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 dependence
  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
  98 /* This is the simplest data dependence test: determines whether the
  99    data references A and B access the same array/region.  Returns
 100    false when the property is not computable at compile time.
 101    Otherwise return true, and DIFFER_P will record the result. This
 102    utility will not be necessary when alias_sets_conflict_p will be
 103    less conservative.  */
 104
 105 bool
 106 array_base_name_differ_p (struct data_reference *a,
 107                           struct data_reference *b,
 108                           bool *differ_p)
 109 {
 110   tree base_a = DR_BASE_NAME (a);
 111   tree base_b = DR_BASE_NAME (b);
 112   tree ta = TREE_TYPE (base_a);
 113   tree tb = TREE_TYPE (base_b);
 114
 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
 143   /* Determine if different bases.  */
 144
 145   /* At this point we know that base_a != base_b.  However, pointer
 146      accesses of the form x=(*p) and y=(*q), whose bases are p and q,
 147      may still be pointing to the same base. In SSAed GIMPLE p and q will
 148      be SSA_NAMES in this case.  Therefore, here we check if they are
 149      really two different declarations.  */
 150   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
 151     {
 152       *differ_p = true;
 153       return true;
 154     }
 155
 156   /* Compare two record/union bases s.a and t.b: s != t or (a != b and
 157      s and t are not unions).  */
 158   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
 159       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
 160            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
 161            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
 162           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
 163               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
 164               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
 165     {
 166       *differ_p = true;
 167       return true;
 168     }
 169
 170   /* Compare a record/union access and an array access.  */
 171   if ((TREE_CODE (base_a) == VAR_DECL
 172        && (TREE_CODE (base_b) == COMPONENT_REF
 173            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL))
 174       || (TREE_CODE (base_b) == VAR_DECL
 175        && (TREE_CODE (base_a) == COMPONENT_REF
 176            && TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL)))
 177     {
 178       *differ_p = true;
 179       return true;
 180     }
 181
 182   if (!alias_sets_conflict_p (get_alias_set (base_a), get_alias_set (base_b)))
 183     {
 184       *differ_p = true;
 185       return true;
 186     }
 187
 188   /* An instruction writing through a restricted pointer is
 189      "independent" of any instruction reading or writing through a
 190      different pointer, in the same block/scope.  */
 191   if ((TREE_CODE (ta) == POINTER_TYPE && TYPE_RESTRICT (ta)
 192        && !DR_IS_READ(a))
 193       || (TREE_CODE (tb) == POINTER_TYPE && TYPE_RESTRICT (tb)
 194           && !DR_IS_READ(b)))
 195     {
 196       *differ_p = true;
 197       return true;
 198     }
 199
 200   return false;
 201 }
 202
 203 /* Returns true iff A divides B.  */
 204
 205 static inline bool
 206 tree_fold_divides_p (tree type,
 207                      tree a,
 208                      tree b)
 209 {
 210   /* Determines whether (A == gcd (A, B)).  */
 211   return integer_zerop
 212     (fold (build (MINUS_EXPR, type, a, tree_fold_gcd (a, b))));
 213 }
 214
 215 /* Compute the greatest common denominator of two numbers using
 216    Euclid's algorithm.  */
 217
 218 static int
 219 gcd (int a, int b)
 220 {
 221
 222   int x, y, z;
 223
 224   x = abs (a);
 225   y = abs (b);
 226
 227   while (x>0)
 228     {
 229       z = y % x;
 230       y = x;
 231       x = z;
 232     }
 233
 234   return (y);
 235 }
 236
 237 /* Returns true iff A divides B.  */
 238
 239 static inline bool
 240 int_divides_p (int a, int b)
 241 {
 242   return ((b % a) == 0);
 243 }
 244
 245 \f
 246
 247 /* Dump into FILE all the data references from DATAREFS.  */
 248
 249 void
 250 dump_data_references (FILE *file,
 251                       varray_type datarefs)
 252 {
 253   unsigned int i;
 254
 255   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
 256     dump_data_reference (file, VARRAY_GENERIC_PTR (datarefs, i));
 257 }
 258
 259 /* Dump into FILE all the dependence relations from DDR.  */
 260
 261 void
 262 dump_data_dependence_relations (FILE *file,
 263                                 varray_type ddr)
 264 {
 265   unsigned int i;
 266
 267   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddr); i++)
 268     dump_data_dependence_relation (file, VARRAY_GENERIC_PTR (ddr, i));
 269 }
 270
 271 /* Dump function for a DATA_REFERENCE structure.  */
 272
 273 void
 274 dump_data_reference (FILE *outf,
 275                      struct data_reference *dr)
 276 {
 277   unsigned int i;
 278
 279   fprintf (outf, "(Data Ref: \n  stmt: ");
 280   print_generic_stmt (outf, DR_STMT (dr), 0);
 281   fprintf (outf, "  ref: ");
 282   print_generic_stmt (outf, DR_REF (dr), 0);
 283   fprintf (outf, "  base_name: ");
 284   print_generic_stmt (outf, DR_BASE_NAME (dr), 0);
 285
 286   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
 287     {
 288       fprintf (outf, "  Access function %d: ", i);
 289       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
 290     }
 291   fprintf (outf, ")\n");
 292 }
 293
 294 /* Dump function for a SUBSCRIPT structure.  */
 295
 296 void
 297 dump_subscript (FILE *outf, struct subscript *subscript)
 298 {
 299   tree chrec = SUB_CONFLICTS_IN_A (subscript);
 300
 301   fprintf (outf, "\n (subscript \n");
 302   fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
 303   print_generic_stmt (outf, chrec, 0);
 304   if (chrec == chrec_known)
 305     fprintf (outf, "    (no dependence)\n");
 306   else if (chrec_contains_undetermined (chrec))
 307     fprintf (outf, "    (don't know)\n");
 308   else
 309     {
 310       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 311       fprintf (outf, "  last_conflict: ");
 312       print_generic_stmt (outf, last_iteration, 0);
 313     }
 314
 315   chrec = SUB_CONFLICTS_IN_B (subscript);
 316   fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
 317   print_generic_stmt (outf, chrec, 0);
 318   if (chrec == chrec_known)
 319     fprintf (outf, "    (no dependence)\n");
 320   else if (chrec_contains_undetermined (chrec))
 321     fprintf (outf, "    (don't know)\n");
 322   else
 323     {
 324       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 325       fprintf (outf, "  last_conflict: ");
 326       print_generic_stmt (outf, last_iteration, 0);
 327     }
 328
 329   fprintf (outf, "  (Subscript distance: ");
 330   print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
 331   fprintf (outf, "  )\n");
 332   fprintf (outf, " )\n");
 333 }
 334
 335 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
 336
 337 void
 338 dump_data_dependence_relation (FILE *outf,
 339                                struct data_dependence_relation *ddr)
 340 {
 341   struct data_reference *dra, *drb;
 342
 343   dra = DDR_A (ddr);
 344   drb = DDR_B (ddr);
 345   fprintf (outf, "(Data Dep: \n");
 346   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 347     fprintf (outf, "    (don't know)\n");
 348
 349   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 350     fprintf (outf, "    (no dependence)\n");
 351
 352   else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 353     {
 354       unsigned int i;
 355       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 356         {
 357           fprintf (outf, "  access_fn_A: ");
 358           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
 359           fprintf (outf, "  access_fn_B: ");
 360           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
 361           dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
 362         }
 363       if (DDR_DIST_VECT (ddr))
 364         {
 365           fprintf (outf, "  distance_vect: ");
 366           print_lambda_vector (outf, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
 367         }
 368       if (DDR_DIR_VECT (ddr))
 369         {
 370           fprintf (outf, "  direction_vect: ");
 371           print_lambda_vector (outf, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
 372         }
 373     }
 374
 375   fprintf (outf, ")\n");
 376 }
 377
 378
 379
 380 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
 381
 382 void
 383 dump_data_dependence_direction (FILE *file,
 384                                 enum data_dependence_direction dir)
 385 {
 386   switch (dir)
 387     {
 388     case dir_positive:
 389       fprintf (file, "+");
 390       break;
 391
 392     case dir_negative:
 393       fprintf (file, "-");
 394       break;
 395
 396     case dir_equal:
 397       fprintf (file, "=");
 398       break;
 399
 400     case dir_positive_or_negative:
 401       fprintf (file, "+-");
 402       break;
 403
 404     case dir_positive_or_equal:
 405       fprintf (file, "+=");
 406       break;
 407
 408     case dir_negative_or_equal:
 409       fprintf (file, "-=");
 410       break;
 411
 412     case dir_star:
 413       fprintf (file, "*");
 414       break;
 415
 416     default:
 417       break;
 418     }
 419 }
 420
 421 /* Dumps the distance and direction vectors in FILE.  DDRS contains
 422    the dependence relations, and VECT_SIZE is the size of the
 423    dependence vectors, or in other words the number of loops in the
 424    considered nest.  */
 425
 426 void
 427 dump_dist_dir_vectors (FILE *file, varray_type ddrs)
 428 {
 429   unsigned int i;
 430
 431   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
 432     {
 433       struct data_dependence_relation *ddr =
 434         (struct data_dependence_relation *)
 435         VARRAY_GENERIC_PTR (ddrs, i);
 436       if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
 437           && DDR_AFFINE_P (ddr))
 438         {
 439           fprintf (file, "DISTANCE_V (");
 440           print_lambda_vector (file, DDR_DIST_VECT (ddr), DDR_SIZE_VECT (ddr));
 441           fprintf (file, ")\n");
 442           fprintf (file, "DIRECTION_V (");
 443           print_lambda_vector (file, DDR_DIR_VECT (ddr), DDR_SIZE_VECT (ddr));
 444           fprintf (file, ")\n");
 445         }
 446     }
 447   fprintf (file, "\n\n");
 448 }
 449
 450 /* Dumps the data dependence relations DDRS in FILE.  */
 451
 452 void
 453 dump_ddrs (FILE *file, varray_type ddrs)
 454 {
 455   unsigned int i;
 456
 457   for (i = 0; i < VARRAY_ACTIVE_SIZE (ddrs); i++)
 458     {
 459       struct data_dependence_relation *ddr =
 460         (struct data_dependence_relation *)
 461         VARRAY_GENERIC_PTR (ddrs, i);
 462       dump_data_dependence_relation (file, ddr);
 463     }
 464   fprintf (file, "\n\n");
 465 }
 466
 467 \f
 468
 469 /* Compute the lowest iteration bound for LOOP.  It is an
 470    INTEGER_CST.  */
 471
 472 static void
 473 compute_estimated_nb_iterations (struct loop *loop)
 474 {
 475   tree estimation;
 476   struct nb_iter_bound *bound, *next;
 477
 478   for (bound = loop->bounds; bound; bound = next)
 479     {
 480       next = bound->next;
 481       estimation = bound->bound;
 482
 483       if (TREE_CODE (estimation) != INTEGER_CST)
 484         continue;
 485
 486       if (loop->estimated_nb_iterations)
 487         {
 488           /* Update only if estimation is smaller.  */
 489           if (tree_int_cst_lt (estimation, loop->estimated_nb_iterations))
 490             loop->estimated_nb_iterations = estimation;
 491         }
 492       else
 493         loop->estimated_nb_iterations = estimation;
 494     }
 495 }
 496
 497 /* Estimate the number of iterations from the size of the data and the
 498    access functions.  */
 499
 500 static void
 501 estimate_niter_from_size_of_data (struct loop *loop,
 502                                   tree opnd0,
 503                                   tree access_fn,
 504                                   tree stmt)
 505 {
 506   tree estimation;
 507   tree array_size, data_size, element_size;
 508   tree init, step;
 509
 510   init = initial_condition (access_fn);
 511   step = evolution_part_in_loop_num (access_fn, loop->num);
 512
 513   array_size = TYPE_SIZE (TREE_TYPE (opnd0));
 514   element_size = TYPE_SIZE (TREE_TYPE (TREE_TYPE (opnd0)));
 515   if (array_size == NULL_TREE
 516       || element_size == NULL_TREE)
 517     return;
 518
 519   data_size = fold (build2 (EXACT_DIV_EXPR, integer_type_node,
 520                            array_size, element_size));
 521
 522   if (init != NULL_TREE
 523       && step != NULL_TREE
 524       && TREE_CODE (init) == INTEGER_CST
 525       && TREE_CODE (step) == INTEGER_CST)
 526     {
 527       estimation = fold (build2 (CEIL_DIV_EXPR, integer_type_node,
 528                                  fold (build2 (MINUS_EXPR, integer_type_node,
 529                                                data_size, init)), step));
 530
 531       record_estimate (loop, estimation, boolean_true_node, stmt);
 532     }
 533 }
 534
 535 /* Given an ARRAY_REF node REF, records its access functions.
 536    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
 537    i.e. the constant "3", then recursively call the function on opnd0,
 538    i.e. the ARRAY_REF "A[i]".  The function returns the base name:
 539    "A".  */
 540
 541 static tree
 542 analyze_array_indexes (struct loop *loop,
 543                        varray_type *access_fns,
 544                        tree ref, tree stmt)
 545 {
 546   tree opnd0, opnd1;
 547   tree access_fn;
 548
 549   opnd0 = TREE_OPERAND (ref, 0);
 550   opnd1 = TREE_OPERAND (ref, 1);
 551
 552   /* The detection of the evolution function for this data access is
 553      postponed until the dependence test.  This lazy strategy avoids
 554      the computation of access functions that are of no interest for
 555      the optimizers.  */
 556   access_fn = instantiate_parameters
 557     (loop, analyze_scalar_evolution (loop, opnd1));
 558
 559   if (loop->estimated_nb_iterations == NULL_TREE)
 560     estimate_niter_from_size_of_data (loop, opnd0, access_fn, stmt);
 561
 562   VARRAY_PUSH_TREE (*access_fns, access_fn);
 563
 564   /* Recursively record other array access functions.  */
 565   if (TREE_CODE (opnd0) == ARRAY_REF)
 566     return analyze_array_indexes (loop, access_fns, opnd0, stmt);
 567
 568   /* Return the base name of the data access.  */
 569   else
 570     return opnd0;
 571 }
 572
 573 /* For a data reference REF contained in the statement STMT, initialize
 574    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
 575    set to true when REF is in the right hand side of an
 576    assignment.  */
 577
 578 struct data_reference *
 579 analyze_array (tree stmt, tree ref, bool is_read)
 580 {
 581   struct data_reference *res;
 582
 583   if (dump_file && (dump_flags & TDF_DETAILS))
 584     {
 585       fprintf (dump_file, "(analyze_array \n");
 586       fprintf (dump_file, "  (ref = ");
 587       print_generic_stmt (dump_file, ref, 0);
 588       fprintf (dump_file, ")\n");
 589     }
 590
 591   res = xmalloc (sizeof (struct data_reference));
 592
 593   DR_STMT (res) = stmt;
 594   DR_REF (res) = ref;
 595   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 3, "access_fns");
 596   DR_BASE_NAME (res) = analyze_array_indexes
 597     (loop_containing_stmt (stmt), &(DR_ACCESS_FNS (res)), ref, stmt);
 598   DR_IS_READ (res) = is_read;
 599
 600   if (dump_file && (dump_flags & TDF_DETAILS))
 601     fprintf (dump_file, ")\n");
 602
 603   return res;
 604 }
 605
 606 /* For a data reference REF contained in the statement STMT, initialize
 607    a DATA_REFERENCE structure, and return it.  */
 608
 609 struct data_reference *
 610 init_data_ref (tree stmt,
 611                tree ref,
 612                tree base,
 613                tree access_fn,
 614                bool is_read)
 615 {
 616   struct data_reference *res;
 617
 618   if (dump_file && (dump_flags & TDF_DETAILS))
 619     {
 620       fprintf (dump_file, "(init_data_ref \n");
 621       fprintf (dump_file, "  (ref = ");
 622       print_generic_stmt (dump_file, ref, 0);
 623       fprintf (dump_file, ")\n");
 624     }
 625
 626   res = xmalloc (sizeof (struct data_reference));
 627
 628   DR_STMT (res) = stmt;
 629   DR_REF (res) = ref;
 630   VARRAY_TREE_INIT (DR_ACCESS_FNS (res), 5, "access_fns");
 631   DR_BASE_NAME (res) = base;
 632   VARRAY_PUSH_TREE (DR_ACCESS_FNS (res), access_fn);
 633   DR_IS_READ (res) = is_read;
 634
 635   if (dump_file && (dump_flags & TDF_DETAILS))
 636     fprintf (dump_file, ")\n");
 637
 638   return res;
 639 }
 640
 641 \f
 642
 643 /* Returns true when all the functions of a tree_vec CHREC are the
 644    same.  */
 645
 646 static bool
 647 all_chrecs_equal_p (tree chrec)
 648 {
 649   int j;
 650
 651   for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
 652     {
 653       tree chrec_j = TREE_VEC_ELT (chrec, j);
 654       tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
 655       if (!integer_zerop
 656           (chrec_fold_minus
 657            (integer_type_node, chrec_j, chrec_j_1)))
 658         return false;
 659     }
 660   return true;
 661 }
 662
 663 /* Determine for each subscript in the data dependence relation DDR
 664    the distance.  */
 665
 666 static void
 667 compute_subscript_distance (struct data_dependence_relation *ddr)
 668 {
 669   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 670     {
 671       unsigned int i;
 672
 673       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 674         {
 675           tree conflicts_a, conflicts_b, difference;
 676           struct subscript *subscript;
 677
 678           subscript = DDR_SUBSCRIPT (ddr, i);
 679           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
 680           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
 681
 682           if (TREE_CODE (conflicts_a) == TREE_VEC)
 683             {
 684               if (!all_chrecs_equal_p (conflicts_a))
 685                 {
 686                   SUB_DISTANCE (subscript) = chrec_dont_know;
 687                   return;
 688                 }
 689               else
 690                 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
 691             }
 692
 693           if (TREE_CODE (conflicts_b) == TREE_VEC)
 694             {
 695               if (!all_chrecs_equal_p (conflicts_b))
 696                 {
 697                   SUB_DISTANCE (subscript) = chrec_dont_know;
 698                   return;
 699                 }
 700               else
 701                 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
 702             }
 703
 704           difference = chrec_fold_minus
 705             (integer_type_node, conflicts_b, conflicts_a);
 706
 707           if (evolution_function_is_constant_p (difference))
 708             SUB_DISTANCE (subscript) = difference;
 709
 710           else
 711             SUB_DISTANCE (subscript) = chrec_dont_know;
 712         }
 713     }
 714 }
 715
 716 /* Initialize a ddr.  */
 717
 718 struct data_dependence_relation *
 719 initialize_data_dependence_relation (struct data_reference *a,
 720                                      struct data_reference *b)
 721 {
 722   struct data_dependence_relation *res;
 723   bool differ_p;
 724
 725   res = xmalloc (sizeof (struct data_dependence_relation));
 726   DDR_A (res) = a;
 727   DDR_B (res) = b;
 728
 729   if (a == NULL || b == NULL
 730       || DR_BASE_NAME (a) == NULL_TREE
 731       || DR_BASE_NAME (b) == NULL_TREE)
 732     DDR_ARE_DEPENDENT (res) = chrec_dont_know;
 733
 734   /* When the dimensions of A and B differ, we directly initialize
 735      the relation to "there is no dependence": chrec_known.  */
 736   else if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
 737            || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
 738     DDR_ARE_DEPENDENT (res) = chrec_known;
 739
 740   else
 741     {
 742       unsigned int i;
 743       DDR_AFFINE_P (res) = true;
 744       DDR_ARE_DEPENDENT (res) = NULL_TREE;
 745       DDR_SUBSCRIPTS_VECTOR_INIT (res, DR_NUM_DIMENSIONS (a));
 746       DDR_SIZE_VECT (res) = 0;
 747       DDR_DIST_VECT (res) = NULL;
 748       DDR_DIR_VECT (res) = NULL;
 749
 750       for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
 751         {
 752           struct subscript *subscript;
 753
 754           subscript = xmalloc (sizeof (struct subscript));
 755           SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
 756           SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
 757           SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
 758           SUB_DISTANCE (subscript) = chrec_dont_know;
 759           VARRAY_PUSH_GENERIC_PTR (DDR_SUBSCRIPTS (res), subscript);
 760         }
 761     }
 762
 763   return res;
 764 }
 765
 766 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
 767    description.  */
 768
 769 static inline void
 770 finalize_ddr_dependent (struct data_dependence_relation *ddr,
 771                         tree chrec)
 772 {
 773   if (dump_file && (dump_flags & TDF_DETAILS))
 774     {
 775       fprintf (dump_file, "(dependence classified: ");
 776       print_generic_expr (dump_file, chrec, 0);
 777       fprintf (dump_file, ")\n");
 778     }
 779
 780   DDR_ARE_DEPENDENT (ddr) = chrec;
 781   varray_clear (DDR_SUBSCRIPTS (ddr));
 782 }
 783
 784 /* The dependence relation DDR cannot be represented by a distance
 785    vector.  */
 786
 787 static inline void
 788 non_affine_dependence_relation (struct data_dependence_relation *ddr)
 789 {
 790   if (dump_file && (dump_flags & TDF_DETAILS))
 791     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
 792
 793   DDR_AFFINE_P (ddr) = false;
 794 }
 795
 796 \f
 797
 798 /* This section contains the classic Banerjee tests.  */
 799
 800 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
 801    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
 802
 803 static inline bool
 804 ziv_subscript_p (tree chrec_a,
 805                  tree chrec_b)
 806 {
 807   return (evolution_function_is_constant_p (chrec_a)
 808           && evolution_function_is_constant_p (chrec_b));
 809 }
 810
 811 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
 812    variable, i.e., if the SIV (Single Index Variable) test is true.  */
 813
 814 static bool
 815 siv_subscript_p (tree chrec_a,
 816                  tree chrec_b)
 817 {
 818   if ((evolution_function_is_constant_p (chrec_a)
 819        && evolution_function_is_univariate_p (chrec_b))
 820       || (evolution_function_is_constant_p (chrec_b)
 821           && evolution_function_is_univariate_p (chrec_a)))
 822     return true;
 823
 824   if (evolution_function_is_univariate_p (chrec_a)
 825       && evolution_function_is_univariate_p (chrec_b))
 826     {
 827       switch (TREE_CODE (chrec_a))
 828         {
 829         case POLYNOMIAL_CHREC:
 830           switch (TREE_CODE (chrec_b))
 831             {
 832             case POLYNOMIAL_CHREC:
 833               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
 834                 return false;
 835
 836             default:
 837               return true;
 838             }
 839
 840         default:
 841           return true;
 842         }
 843     }
 844
 845   return false;
 846 }
 847
 848 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
 849    *OVERLAPS_B are initialized to the functions that describe the
 850    relation between the elements accessed twice by CHREC_A and
 851    CHREC_B.  For k >= 0, the following property is verified:
 852
 853    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
 854
 855 static void
 856 analyze_ziv_subscript (tree chrec_a,
 857                        tree chrec_b,
 858                        tree *overlaps_a,
 859                        tree *overlaps_b,
 860                        tree *last_conflicts)
 861 {
 862   tree difference;
 863
 864   if (dump_file && (dump_flags & TDF_DETAILS))
 865     fprintf (dump_file, "(analyze_ziv_subscript \n");
 866
 867   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
 868
 869   switch (TREE_CODE (difference))
 870     {
 871     case INTEGER_CST:
 872       if (integer_zerop (difference))
 873         {
 874           /* The difference is equal to zero: the accessed index
 875              overlaps for each iteration in the loop.  */
 876           *overlaps_a = integer_zero_node;
 877           *overlaps_b = integer_zero_node;
 878           *last_conflicts = chrec_dont_know;
 879         }
 880       else
 881         {
 882           /* The accesses do not overlap.  */
 883           *overlaps_a = chrec_known;
 884           *overlaps_b = chrec_known;
 885           *last_conflicts = integer_zero_node;
 886         }
 887       break;
 888
 889     default:
 890       /* We're not sure whether the indexes overlap.  For the moment,
 891          conservatively answer "don't know".  */
 892       *overlaps_a = chrec_dont_know;
 893       *overlaps_b = chrec_dont_know;
 894       *last_conflicts = chrec_dont_know;
 895       break;
 896     }
 897
 898   if (dump_file && (dump_flags & TDF_DETAILS))
 899     fprintf (dump_file, ")\n");
 900 }
 901
 902 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
 903    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
 904    *OVERLAPS_B are initialized to the functions that describe the
 905    relation between the elements accessed twice by CHREC_A and
 906    CHREC_B.  For k >= 0, the following property is verified:
 907
 908    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
 909
 910 static void
 911 analyze_siv_subscript_cst_affine (tree chrec_a,
 912                                   tree chrec_b,
 913                                   tree *overlaps_a,
 914                                   tree *overlaps_b,
 915                                   tree *last_conflicts)
 916 {
 917   bool value0, value1, value2;
 918   tree difference = chrec_fold_minus
 919     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
 920
 921   if (!chrec_is_positive (initial_condition (difference), &value0))
 922     {
 923       *overlaps_a = chrec_dont_know;
 924       *overlaps_b = chrec_dont_know;
 925       *last_conflicts = chrec_dont_know;
 926       return;
 927     }
 928   else
 929     {
 930       if (value0 == false)
 931         {
 932           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
 933             {
 934               *overlaps_a = chrec_dont_know;
 935               *overlaps_b = chrec_dont_know;
 936               *last_conflicts = chrec_dont_know;
 937               return;
 938             }
 939           else
 940             {
 941               if (value1 == true)
 942                 {
 943                   /* Example:
 944                      chrec_a = 12
 945                      chrec_b = {10, +, 1}
 946                   */
 947
 948                   if (tree_fold_divides_p
 949                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
 950                     {
 951                       *overlaps_a = integer_zero_node;
 952                       *overlaps_b = fold
 953                         (build (EXACT_DIV_EXPR, integer_type_node,
 954                                 fold (build1 (ABS_EXPR, integer_type_node, difference)),
 955                                 CHREC_RIGHT (chrec_b)));
 956                       *last_conflicts = integer_one_node;
 957                       return;
 958                     }
 959
 960                   /* When the step does not divides the difference, there are
 961                      no overlaps.  */
 962                   else
 963                     {
 964                       *overlaps_a = chrec_known;
 965                       *overlaps_b = chrec_known;
 966                       *last_conflicts = integer_zero_node;
 967                       return;
 968                     }
 969                 }
 970
 971               else
 972                 {
 973                   /* Example:
 974                      chrec_a = 12
 975                      chrec_b = {10, +, -1}
 976
 977                      In this case, chrec_a will not overlap with chrec_b.  */
 978                   *overlaps_a = chrec_known;
 979                   *overlaps_b = chrec_known;
 980                   *last_conflicts = integer_zero_node;
 981                   return;
 982                 }
 983             }
 984         }
 985       else
 986         {
 987           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
 988             {
 989               *overlaps_a = chrec_dont_know;
 990               *overlaps_b = chrec_dont_know;
 991               *last_conflicts = chrec_dont_know;
 992               return;
 993             }
 994           else
 995             {
 996               if (value2 == false)
 997                 {
 998                   /* Example:
 999                      chrec_a = 3
1000                      chrec_b = {10, +, -1}
1001                   */
1002                   if (tree_fold_divides_p
1003                       (integer_type_node, CHREC_RIGHT (chrec_b), difference))
1004                     {
1005                       *overlaps_a = integer_zero_node;
1006                       *overlaps_b = fold
1007                         (build (EXACT_DIV_EXPR, integer_type_node, difference,
1008                                 CHREC_RIGHT (chrec_b)));
1009                       *last_conflicts = integer_one_node;
1010                       return;
1011                     }
1012
1013                   /* When the step does not divides the difference, there
1014                      are no overlaps.  */
1015                   else
1016                     {
1017                       *overlaps_a = chrec_known;
1018                       *overlaps_b = chrec_known;
1019                       *last_conflicts = integer_zero_node;
1020                       return;
1021                     }
1022                 }
1023               else
1024                 {
1025                   /* Example:
1026                      chrec_a = 3
1027                      chrec_b = {4, +, 1}
1028
1029                      In this case, chrec_a will not overlap with chrec_b.  */
1030                   *overlaps_a = chrec_known;
1031                   *overlaps_b = chrec_known;
1032                   *last_conflicts = integer_zero_node;
1033                   return;
1034                 }
1035             }
1036         }
1037     }
1038 }
1039
1040 /* Helper recursive function for initializing the matrix A.  Returns
1041    the initial value of CHREC.  */
1042
1043 static int
1044 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1045 {
1046   gcc_assert (chrec);
1047
1048   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1049     return int_cst_value (chrec);
1050
1051   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1052   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1053 }
1054
1055 #define FLOOR_DIV(x,y) ((x) / (y))
1056
1057 /* Solves the special case of the Diophantine equation:
1058    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1059
1060    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
1061    number of iterations that loops X and Y run.  The overlaps will be
1062    constructed as evolutions in dimension DIM.  */
1063
1064 static void
1065 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1066                                          tree *overlaps_a, tree *overlaps_b,
1067                                          tree *last_conflicts, int dim)
1068 {
1069   if (((step_a > 0 && step_b > 0)
1070        || (step_a < 0 && step_b < 0)))
1071     {
1072       int step_overlaps_a, step_overlaps_b;
1073       int gcd_steps_a_b, last_conflict, tau2;
1074
1075       gcd_steps_a_b = gcd (step_a, step_b);
1076       step_overlaps_a = step_b / gcd_steps_a_b;
1077       step_overlaps_b = step_a / gcd_steps_a_b;
1078
1079       tau2 = FLOOR_DIV (niter, step_overlaps_a);
1080       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1081       last_conflict = tau2;
1082
1083       *overlaps_a = build_polynomial_chrec
1084         (dim, integer_zero_node,
1085          build_int_cst (NULL_TREE, step_overlaps_a));
1086       *overlaps_b = build_polynomial_chrec
1087         (dim, integer_zero_node,
1088          build_int_cst (NULL_TREE, step_overlaps_b));
1089       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1090     }
1091
1092   else
1093     {
1094       *overlaps_a = integer_zero_node;
1095       *overlaps_b = integer_zero_node;
1096       *last_conflicts = integer_zero_node;
1097     }
1098 }
1099
1100
1101 /* Solves the special case of a Diophantine equation where CHREC_A is
1102    an affine bivariate function, and CHREC_B is an affine univariate
1103    function.  For example,
1104
1105    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1106
1107    has the following overlapping functions:
1108
1109    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1110    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1111    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1112
1113    FORNOW: This is a specialized implementation for a case occuring in
1114    a common benchmark.  Implement the general algorithm.  */
1115
1116 static void
1117 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1118                                       tree *overlaps_a, tree *overlaps_b,
1119                                       tree *last_conflicts)
1120 {
1121   bool xz_p, yz_p, xyz_p;
1122   int step_x, step_y, step_z;
1123   int niter_x, niter_y, niter_z, niter;
1124   tree numiter_x, numiter_y, numiter_z;
1125   tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
1126   tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
1127   tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
1128
1129   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1130   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1131   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1132
1133   numiter_x = number_of_iterations_in_loop
1134     (current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]);
1135   numiter_y = number_of_iterations_in_loop
1136     (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1137   numiter_z = number_of_iterations_in_loop
1138     (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1139
1140   if (TREE_CODE (numiter_x) != INTEGER_CST)
1141     numiter_x = current_loops->parray[CHREC_VARIABLE (CHREC_LEFT (chrec_a))]
1142       ->estimated_nb_iterations;
1143   if (TREE_CODE (numiter_y) != INTEGER_CST)
1144     numiter_y = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1145       ->estimated_nb_iterations;
1146   if (TREE_CODE (numiter_z) != INTEGER_CST)
1147     numiter_z = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1148       ->estimated_nb_iterations;
1149
1150   if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
1151       || numiter_z == NULL_TREE)
1152     {
1153       *overlaps_a = chrec_dont_know;
1154       *overlaps_b = chrec_dont_know;
1155       *last_conflicts = chrec_dont_know;
1156       return;
1157     }
1158
1159   niter_x = int_cst_value (numiter_x);
1160   niter_y = int_cst_value (numiter_y);
1161   niter_z = int_cst_value (numiter_z);
1162
1163   niter = MIN (niter_x, niter_z);
1164   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1165                                            &overlaps_a_xz,
1166                                            &overlaps_b_xz,
1167                                            &last_conflicts_xz, 1);
1168   niter = MIN (niter_y, niter_z);
1169   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1170                                            &overlaps_a_yz,
1171                                            &overlaps_b_yz,
1172                                            &last_conflicts_yz, 2);
1173   niter = MIN (niter_x, niter_z);
1174   niter = MIN (niter_y, niter);
1175   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1176                                            &overlaps_a_xyz,
1177                                            &overlaps_b_xyz,
1178                                            &last_conflicts_xyz, 3);
1179
1180   xz_p = !integer_zerop (last_conflicts_xz);
1181   yz_p = !integer_zerop (last_conflicts_yz);
1182   xyz_p = !integer_zerop (last_conflicts_xyz);
1183
1184   if (xz_p || yz_p || xyz_p)
1185     {
1186       *overlaps_a = make_tree_vec (2);
1187       TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
1188       TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
1189       *overlaps_b = integer_zero_node;
1190       if (xz_p)
1191         {
1192           TREE_VEC_ELT (*overlaps_a, 0) =
1193             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1194                              overlaps_a_xz);
1195           *overlaps_b =
1196             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
1197           *last_conflicts = last_conflicts_xz;
1198         }
1199       if (yz_p)
1200         {
1201           TREE_VEC_ELT (*overlaps_a, 1) =
1202             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1203                              overlaps_a_yz);
1204           *overlaps_b =
1205             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
1206           *last_conflicts = last_conflicts_yz;
1207         }
1208       if (xyz_p)
1209         {
1210           TREE_VEC_ELT (*overlaps_a, 0) =
1211             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
1212                              overlaps_a_xyz);
1213           TREE_VEC_ELT (*overlaps_a, 1) =
1214             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
1215                              overlaps_a_xyz);
1216           *overlaps_b =
1217             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
1218           *last_conflicts = last_conflicts_xyz;
1219         }
1220     }
1221   else
1222     {
1223       *overlaps_a = integer_zero_node;
1224       *overlaps_b = integer_zero_node;
1225       *last_conflicts = integer_zero_node;
1226     }
1227 }
1228
1229 /* Determines the overlapping elements due to accesses CHREC_A and
1230    CHREC_B, that are affine functions.  This is a part of the
1231    subscript analyzer.  */
1232
1233 static void
1234 analyze_subscript_affine_affine (tree chrec_a,
1235                                  tree chrec_b,
1236                                  tree *overlaps_a,
1237                                  tree *overlaps_b,
1238                                  tree *last_conflicts)
1239 {
1240   unsigned nb_vars_a, nb_vars_b, dim;
1241   int init_a, init_b, gamma, gcd_alpha_beta;
1242   int tau1, tau2;
1243   lambda_matrix A, U, S;
1244
1245   if (dump_file && (dump_flags & TDF_DETAILS))
1246     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1247
1248   /* For determining the initial intersection, we have to solve a
1249      Diophantine equation.  This is the most time consuming part.
1250
1251      For answering to the question: "Is there a dependence?" we have
1252      to prove that there exists a solution to the Diophantine
1253      equation, and that the solution is in the iteration domain,
1254      i.e. the solution is positive or zero, and that the solution
1255      happens before the upper bound loop.nb_iterations.  Otherwise
1256      there is no dependence.  This function outputs a description of
1257      the iterations that hold the intersections.  */
1258
1259
1260   nb_vars_a = nb_vars_in_chrec (chrec_a);
1261   nb_vars_b = nb_vars_in_chrec (chrec_b);
1262
1263   dim = nb_vars_a + nb_vars_b;
1264   U = lambda_matrix_new (dim, dim);
1265   A = lambda_matrix_new (dim, 1);
1266   S = lambda_matrix_new (dim, 1);
1267
1268   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
1269   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
1270   gamma = init_b - init_a;
1271
1272   /* Don't do all the hard work of solving the Diophantine equation
1273      when we already know the solution: for example,
1274      | {3, +, 1}_1
1275      | {3, +, 4}_2
1276      | gamma = 3 - 3 = 0.
1277      Then the first overlap occurs during the first iterations:
1278      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
1279   */
1280   if (gamma == 0)
1281     {
1282       if (nb_vars_a == 1 && nb_vars_b == 1)
1283         {
1284           int step_a, step_b;
1285           int niter, niter_a, niter_b;
1286           tree numiter_a, numiter_b;
1287
1288           numiter_a = number_of_iterations_in_loop
1289             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1290           numiter_b = number_of_iterations_in_loop
1291             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1292
1293           if (TREE_CODE (numiter_a) != INTEGER_CST)
1294             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1295               ->estimated_nb_iterations;
1296           if (TREE_CODE (numiter_b) != INTEGER_CST)
1297             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1298               ->estimated_nb_iterations;
1299           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1300             {
1301               *overlaps_a = chrec_dont_know;
1302               *overlaps_b = chrec_dont_know;
1303               *last_conflicts = chrec_dont_know;
1304               return;
1305             }
1306
1307           niter_a = int_cst_value (numiter_a);
1308           niter_b = int_cst_value (numiter_b);
1309           niter = MIN (niter_a, niter_b);
1310
1311           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
1312           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
1313
1314           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
1315                                                    overlaps_a, overlaps_b,
1316                                                    last_conflicts, 1);
1317         }
1318
1319       else if (nb_vars_a == 2 && nb_vars_b == 1)
1320         compute_overlap_steps_for_affine_1_2
1321           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
1322
1323       else if (nb_vars_a == 1 && nb_vars_b == 2)
1324         compute_overlap_steps_for_affine_1_2
1325           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
1326
1327       else
1328         {
1329           *overlaps_a = chrec_dont_know;
1330           *overlaps_b = chrec_dont_know;
1331           *last_conflicts = chrec_dont_know;
1332         }
1333       return;
1334     }
1335
1336   /* U.A = S */
1337   lambda_matrix_right_hermite (A, dim, 1, S, U);
1338
1339   if (S[0][0] < 0)
1340     {
1341       S[0][0] *= -1;
1342       lambda_matrix_row_negate (U, dim, 0);
1343     }
1344   gcd_alpha_beta = S[0][0];
1345
1346   /* The classic "gcd-test".  */
1347   if (!int_divides_p (gcd_alpha_beta, gamma))
1348     {
1349       /* The "gcd-test" has determined that there is no integer
1350          solution, i.e. there is no dependence.  */
1351       *overlaps_a = chrec_known;
1352       *overlaps_b = chrec_known;
1353       *last_conflicts = integer_zero_node;
1354     }
1355
1356   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
1357   else if (nb_vars_a == 1 && nb_vars_b == 1)
1358     {
1359       /* Both functions should have the same evolution sign.  */
1360       if (((A[0][0] > 0 && -A[1][0] > 0)
1361            || (A[0][0] < 0 && -A[1][0] < 0)))
1362         {
1363           /* The solutions are given by:
1364              |
1365              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
1366              |                           [u21 u22]    [y0]
1367
1368              For a given integer t.  Using the following variables,
1369
1370              | i0 = u11 * gamma / gcd_alpha_beta
1371              | j0 = u12 * gamma / gcd_alpha_beta
1372              | i1 = u21
1373              | j1 = u22
1374
1375              the solutions are:
1376
1377              | x0 = i0 + i1 * t,
1378              | y0 = j0 + j1 * t.  */
1379
1380           int i0, j0, i1, j1;
1381
1382           /* X0 and Y0 are the first iterations for which there is a
1383              dependence.  X0, Y0 are two solutions of the Diophantine
1384              equation: chrec_a (X0) = chrec_b (Y0).  */
1385           int x0, y0;
1386           int niter, niter_a, niter_b;
1387           tree numiter_a, numiter_b;
1388
1389           numiter_a = number_of_iterations_in_loop
1390             (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1391           numiter_b = number_of_iterations_in_loop
1392             (current_loops->parray[CHREC_VARIABLE (chrec_b)]);
1393
1394           if (TREE_CODE (numiter_a) != INTEGER_CST)
1395             numiter_a = current_loops->parray[CHREC_VARIABLE (chrec_a)]
1396               ->estimated_nb_iterations;
1397           if (TREE_CODE (numiter_b) != INTEGER_CST)
1398             numiter_b = current_loops->parray[CHREC_VARIABLE (chrec_b)]
1399               ->estimated_nb_iterations;
1400           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
1401             {
1402               *overlaps_a = chrec_dont_know;
1403               *overlaps_b = chrec_dont_know;
1404               *last_conflicts = chrec_dont_know;
1405               return;
1406             }
1407
1408           niter_a = int_cst_value (numiter_a);
1409           niter_b = int_cst_value (numiter_b);
1410           niter = MIN (niter_a, niter_b);
1411
1412           i0 = U[0][0] * gamma / gcd_alpha_beta;
1413           j0 = U[0][1] * gamma / gcd_alpha_beta;
1414           i1 = U[1][0];
1415           j1 = U[1][1];
1416
1417           if ((i1 == 0 && i0 < 0)
1418               || (j1 == 0 && j0 < 0))
1419             {
1420               /* There is no solution.
1421                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
1422                  falls in here, but for the moment we don't look at the
1423                  upper bound of the iteration domain.  */
1424               *overlaps_a = chrec_known;
1425               *overlaps_b = chrec_known;
1426               *last_conflicts = integer_zero_node;
1427             }
1428
1429           else
1430             {
1431               if (i1 > 0)
1432                 {
1433                   tau1 = CEIL (-i0, i1);
1434                   tau2 = FLOOR_DIV (niter - i0, i1);
1435
1436                   if (j1 > 0)
1437                     {
1438                       int last_conflict;
1439                       tau1 = MAX (tau1, CEIL (-j0, j1));
1440                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
1441
1442                       x0 = (i1 * tau1 + i0) % i1;
1443                       y0 = (j1 * tau1 + j0) % j1;
1444                       tau1 = (x0 - i0)/i1;
1445                       last_conflict = tau2 - tau1;
1446
1447                       *overlaps_a = build_polynomial_chrec
1448                         (1,
1449                          build_int_cst (NULL_TREE, x0),
1450                          build_int_cst (NULL_TREE, i1));
1451                       *overlaps_b = build_polynomial_chrec
1452                         (1,
1453                          build_int_cst (NULL_TREE, y0),
1454                          build_int_cst (NULL_TREE, j1));
1455                       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1456                     }
1457                   else
1458                     {
1459                       /* FIXME: For the moment, the upper bound of the
1460                          iteration domain for j is not checked.  */
1461                       *overlaps_a = chrec_dont_know;
1462                       *overlaps_b = chrec_dont_know;
1463                       *last_conflicts = chrec_dont_know;
1464                     }
1465                 }
1466
1467               else
1468                 {
1469                   /* FIXME: For the moment, the upper bound of the
1470                      iteration domain for i is not checked.  */
1471                   *overlaps_a = chrec_dont_know;
1472                   *overlaps_b = chrec_dont_know;
1473                   *last_conflicts = chrec_dont_know;
1474                 }
1475             }
1476         }
1477       else
1478         {
1479           *overlaps_a = chrec_dont_know;
1480           *overlaps_b = chrec_dont_know;
1481           *last_conflicts = chrec_dont_know;
1482         }
1483     }
1484
1485   else
1486     {
1487       *overlaps_a = chrec_dont_know;
1488       *overlaps_b = chrec_dont_know;
1489       *last_conflicts = chrec_dont_know;
1490     }
1491
1492
1493   if (dump_file && (dump_flags & TDF_DETAILS))
1494     {
1495       fprintf (dump_file, "  (overlaps_a = ");
1496       print_generic_expr (dump_file, *overlaps_a, 0);
1497       fprintf (dump_file, ")\n  (overlaps_b = ");
1498       print_generic_expr (dump_file, *overlaps_b, 0);
1499       fprintf (dump_file, ")\n");
1500     }
1501
1502   if (dump_file && (dump_flags & TDF_DETAILS))
1503     fprintf (dump_file, ")\n");
1504 }
1505
1506 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
1507    *OVERLAPS_B are initialized to the functions that describe the
1508    relation between the elements accessed twice by CHREC_A and
1509    CHREC_B.  For k >= 0, the following property is verified:
1510
1511    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1512
1513 static void
1514 analyze_siv_subscript (tree chrec_a,
1515                        tree chrec_b,
1516                        tree *overlaps_a,
1517                        tree *overlaps_b,
1518                        tree *last_conflicts)
1519 {
1520   if (dump_file && (dump_flags & TDF_DETAILS))
1521     fprintf (dump_file, "(analyze_siv_subscript \n");
1522
1523   if (evolution_function_is_constant_p (chrec_a)
1524       && evolution_function_is_affine_p (chrec_b))
1525     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
1526                                       overlaps_a, overlaps_b, last_conflicts);
1527
1528   else if (evolution_function_is_affine_p (chrec_a)
1529            && evolution_function_is_constant_p (chrec_b))
1530     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
1531                                       overlaps_b, overlaps_a, last_conflicts);
1532
1533   else if (evolution_function_is_affine_p (chrec_a)
1534            && evolution_function_is_affine_p (chrec_b))
1535     analyze_subscript_affine_affine (chrec_a, chrec_b,
1536                                      overlaps_a, overlaps_b, last_conflicts);
1537   else
1538     {
1539       *overlaps_a = chrec_dont_know;
1540       *overlaps_b = chrec_dont_know;
1541       *last_conflicts = chrec_dont_know;
1542     }
1543
1544   if (dump_file && (dump_flags & TDF_DETAILS))
1545     fprintf (dump_file, ")\n");
1546 }
1547
1548 /* Return true when the evolution steps of an affine CHREC divide the
1549    constant CST.  */
1550
1551 static bool
1552 chrec_steps_divide_constant_p (tree chrec,
1553                                tree cst)
1554 {
1555   switch (TREE_CODE (chrec))
1556     {
1557     case POLYNOMIAL_CHREC:
1558       return (tree_fold_divides_p (integer_type_node, CHREC_RIGHT (chrec), cst)
1559               && chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst));
1560
1561     default:
1562       /* On the initial condition, return true.  */
1563       return true;
1564     }
1565 }
1566
1567 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
1568    *OVERLAPS_B are initialized to the functions that describe the
1569    relation between the elements accessed twice by CHREC_A and
1570    CHREC_B.  For k >= 0, the following property is verified:
1571
1572    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1573
1574 static void
1575 analyze_miv_subscript (tree chrec_a,
1576                        tree chrec_b,
1577                        tree *overlaps_a,
1578                        tree *overlaps_b,
1579                        tree *last_conflicts)
1580 {
1581   /* FIXME:  This is a MIV subscript, not yet handled.
1582      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
1583      (A[i] vs. A[j]).
1584
1585      In the SIV test we had to solve a Diophantine equation with two
1586      variables.  In the MIV case we have to solve a Diophantine
1587      equation with 2*n variables (if the subscript uses n IVs).
1588   */
1589   tree difference;
1590
1591   if (dump_file && (dump_flags & TDF_DETAILS))
1592     fprintf (dump_file, "(analyze_miv_subscript \n");
1593
1594   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1595
1596   if (chrec_zerop (difference))
1597     {
1598       /* Access functions are the same: all the elements are accessed
1599          in the same order.  */
1600       *overlaps_a = integer_zero_node;
1601       *overlaps_b = integer_zero_node;
1602       *last_conflicts = number_of_iterations_in_loop
1603         (current_loops->parray[CHREC_VARIABLE (chrec_a)]);
1604     }
1605
1606   else if (evolution_function_is_constant_p (difference)
1607            /* For the moment, the following is verified:
1608               evolution_function_is_affine_multivariate_p (chrec_a) */
1609            && !chrec_steps_divide_constant_p (chrec_a, difference))
1610     {
1611       /* testsuite/.../ssa-chrec-33.c
1612          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
1613
1614          The difference is 1, and the evolution steps are equal to 2,
1615          consequently there are no overlapping elements.  */
1616       *overlaps_a = chrec_known;
1617       *overlaps_b = chrec_known;
1618       *last_conflicts = integer_zero_node;
1619     }
1620
1621   else if (evolution_function_is_affine_multivariate_p (chrec_a)
1622            && evolution_function_is_affine_multivariate_p (chrec_b))
1623     {
1624       /* testsuite/.../ssa-chrec-35.c
1625          {0, +, 1}_2  vs.  {0, +, 1}_3
1626          the overlapping elements are respectively located at iterations:
1627          {0, +, 1}_x and {0, +, 1}_x,
1628          in other words, we have the equality:
1629          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
1630
1631          Other examples:
1632          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
1633          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
1634
1635          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
1636          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
1637       */
1638       analyze_subscript_affine_affine (chrec_a, chrec_b,
1639                                        overlaps_a, overlaps_b, last_conflicts);
1640     }
1641
1642   else
1643     {
1644       /* When the analysis is too difficult, answer "don't know".  */
1645       *overlaps_a = chrec_dont_know;
1646       *overlaps_b = chrec_dont_know;
1647       *last_conflicts = chrec_dont_know;
1648     }
1649
1650   if (dump_file && (dump_flags & TDF_DETAILS))
1651     fprintf (dump_file, ")\n");
1652 }
1653
1654 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
1655    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
1656    two functions that describe the iterations that contain conflicting
1657    elements.
1658
1659    Remark: For an integer k >= 0, the following equality is true:
1660
1661    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
1662 */
1663
1664 static void
1665 analyze_overlapping_iterations (tree chrec_a,
1666                                 tree chrec_b,
1667                                 tree *overlap_iterations_a,
1668                                 tree *overlap_iterations_b,
1669                                 tree *last_conflicts)
1670 {
1671   if (dump_file && (dump_flags & TDF_DETAILS))
1672     {
1673       fprintf (dump_file, "(analyze_overlapping_iterations \n");
1674       fprintf (dump_file, "  (chrec_a = ");
1675       print_generic_expr (dump_file, chrec_a, 0);
1676       fprintf (dump_file, ")\n  chrec_b = ");
1677       print_generic_expr (dump_file, chrec_b, 0);
1678       fprintf (dump_file, ")\n");
1679     }
1680
1681   if (chrec_a == NULL_TREE
1682       || chrec_b == NULL_TREE
1683       || chrec_contains_undetermined (chrec_a)
1684       || chrec_contains_undetermined (chrec_b)
1685       || chrec_contains_symbols (chrec_a)
1686       || chrec_contains_symbols (chrec_b))
1687     {
1688       *overlap_iterations_a = chrec_dont_know;
1689       *overlap_iterations_b = chrec_dont_know;
1690     }
1691
1692   else if (ziv_subscript_p (chrec_a, chrec_b))
1693     analyze_ziv_subscript (chrec_a, chrec_b,
1694                            overlap_iterations_a, overlap_iterations_b,
1695                            last_conflicts);
1696
1697   else if (siv_subscript_p (chrec_a, chrec_b))
1698     analyze_siv_subscript (chrec_a, chrec_b,
1699                            overlap_iterations_a, overlap_iterations_b,
1700                            last_conflicts);
1701
1702   else
1703     analyze_miv_subscript (chrec_a, chrec_b,
1704                            overlap_iterations_a, overlap_iterations_b,
1705                            last_conflicts);
1706
1707   if (dump_file && (dump_flags & TDF_DETAILS))
1708     {
1709       fprintf (dump_file, "  (overlap_iterations_a = ");
1710       print_generic_expr (dump_file, *overlap_iterations_a, 0);
1711       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
1712       print_generic_expr (dump_file, *overlap_iterations_b, 0);
1713       fprintf (dump_file, ")\n");
1714     }
1715 }
1716
1717 \f
1718
1719 /* This section contains the affine functions dependences detector.  */
1720
1721 /* Computes the conflicting iterations, and initialize DDR.  */
1722
1723 static void
1724 subscript_dependence_tester (struct data_dependence_relation *ddr)
1725 {
1726   unsigned int i;
1727   struct data_reference *dra = DDR_A (ddr);
1728   struct data_reference *drb = DDR_B (ddr);
1729   tree last_conflicts;
1730
1731   if (dump_file && (dump_flags & TDF_DETAILS))
1732     fprintf (dump_file, "(subscript_dependence_tester \n");
1733
1734   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1735     {
1736       tree overlaps_a, overlaps_b;
1737       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1738
1739       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
1740                                       DR_ACCESS_FN (drb, i),
1741                                       &overlaps_a, &overlaps_b,
1742                                       &last_conflicts);
1743
1744       if (chrec_contains_undetermined (overlaps_a)
1745           || chrec_contains_undetermined (overlaps_b))
1746         {
1747           finalize_ddr_dependent (ddr, chrec_dont_know);
1748           break;
1749         }
1750
1751       else if (overlaps_a == chrec_known
1752                || overlaps_b == chrec_known)
1753         {
1754           finalize_ddr_dependent (ddr, chrec_known);
1755           break;
1756         }
1757
1758       else
1759         {
1760           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
1761           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
1762           SUB_LAST_CONFLICT (subscript) = last_conflicts;
1763         }
1764     }
1765
1766   if (dump_file && (dump_flags & TDF_DETAILS))
1767     fprintf (dump_file, ")\n");
1768 }
1769
1770 /* Compute the classic per loop distance vector.
1771
1772    DDR is the data dependence relation to build a vector from.
1773    NB_LOOPS is the total number of loops we are considering.
1774    FIRST_LOOP is the loop->num of the first loop in the analyzed
1775    loop nest.  */
1776
1777 static void
1778 build_classic_dist_vector (struct data_dependence_relation *ddr,
1779                            int nb_loops, unsigned int first_loop)
1780 {
1781   unsigned i;
1782   lambda_vector dist_v, init_v;
1783
1784   dist_v = lambda_vector_new (nb_loops);
1785   init_v = lambda_vector_new (nb_loops);
1786   lambda_vector_clear (dist_v, nb_loops);
1787   lambda_vector_clear (init_v, nb_loops);
1788
1789   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1790     return;
1791
1792   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1793     {
1794       tree access_fn_a, access_fn_b;
1795       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1796
1797       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1798         {
1799           non_affine_dependence_relation (ddr);
1800           return;
1801         }
1802
1803       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1804       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1805
1806       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1807           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1808         {
1809           int dist, loop_nb;
1810           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1811           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1812           struct loop *loop_a = current_loops->parray[loop_nb_a];
1813           struct loop *loop_b = current_loops->parray[loop_nb_b];
1814
1815           if (loop_nb_a != loop_nb_b
1816               && !flow_loop_nested_p (loop_a, loop_b)
1817               && !flow_loop_nested_p (loop_b, loop_a))
1818             {
1819               /* Example: when there are two consecutive loops,
1820
1821                  | loop_1
1822                  |   A[{0, +, 1}_1]
1823                  | endloop_1
1824                  | loop_2
1825                  |   A[{0, +, 1}_2]
1826                  | endloop_2
1827
1828                  the dependence relation cannot be captured by the
1829                  distance abstraction.  */
1830               non_affine_dependence_relation (ddr);
1831               return;
1832             }
1833
1834           /* The dependence is carried by the outermost loop.  Example:
1835              | loop_1
1836              |   A[{4, +, 1}_1]
1837              |   loop_2
1838              |     A[{5, +, 1}_2]
1839              |   endloop_2
1840              | endloop_1
1841              In this case, the dependence is carried by loop_1.  */
1842           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
1843           loop_nb -= first_loop;
1844
1845           /* If the loop number is still greater than the number of
1846              loops we've been asked to analyze, or negative,
1847              something is borked.  */
1848           gcc_assert (loop_nb >= 0);
1849           gcc_assert (loop_nb < nb_loops);
1850           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1851             {
1852               non_affine_dependence_relation (ddr);
1853               return;
1854             }
1855
1856           dist = int_cst_value (SUB_DISTANCE (subscript));
1857
1858           /* This is the subscript coupling test.
1859              | loop i = 0, N, 1
1860              |   T[i+1][i] = ...
1861              |   ... = T[i][i]
1862              | endloop
1863              There is no dependence.  */
1864           if (init_v[loop_nb] != 0
1865               && dist_v[loop_nb] != dist)
1866             {
1867               finalize_ddr_dependent (ddr, chrec_known);
1868               return;
1869             }
1870
1871           dist_v[loop_nb] = dist;
1872           init_v[loop_nb] = 1;
1873         }
1874     }
1875
1876   /* There is a distance of 1 on all the outer loops:
1877
1878      Example: there is a dependence of distance 1 on loop_1 for the array A.
1879      | loop_1
1880      |   A[5] = ...
1881      | endloop
1882   */
1883   {
1884     struct loop *lca, *loop_a, *loop_b;
1885     struct data_reference *a = DDR_A (ddr);
1886     struct data_reference *b = DDR_B (ddr);
1887     int lca_nb;
1888     loop_a = loop_containing_stmt (DR_STMT (a));
1889     loop_b = loop_containing_stmt (DR_STMT (b));
1890
1891     /* Get the common ancestor loop.  */
1892     lca = find_common_loop (loop_a, loop_b);
1893
1894     lca_nb = lca->num;
1895     lca_nb -= first_loop;
1896     gcc_assert (lca_nb >= 0);
1897     gcc_assert (lca_nb < nb_loops);
1898
1899     /* For each outer loop where init_v is not set, the accesses are
1900        in dependence of distance 1 in the loop.  */
1901     if (lca != loop_a
1902         && lca != loop_b
1903         && init_v[lca_nb] == 0)
1904       dist_v[lca_nb] = 1;
1905
1906     lca = lca->outer;
1907
1908     if (lca)
1909       {
1910         lca_nb = lca->num - first_loop;
1911         while (lca->depth != 0)
1912           {
1913             /* If we're considering just a sub-nest, then don't record
1914                any information on the outer loops.  */
1915             if (lca_nb < 0)
1916               break;
1917
1918             gcc_assert (lca_nb < nb_loops);
1919
1920             if (init_v[lca_nb] == 0)
1921               dist_v[lca_nb] = 1;
1922             lca = lca->outer;
1923             lca_nb = lca->num - first_loop;
1924
1925           }
1926       }
1927   }
1928
1929   DDR_DIST_VECT (ddr) = dist_v;
1930   DDR_SIZE_VECT (ddr) = nb_loops;
1931 }
1932
1933 /* Compute the classic per loop direction vector.
1934
1935    DDR is the data dependence relation to build a vector from.
1936    NB_LOOPS is the total number of loops we are considering.
1937    FIRST_LOOP is the loop->num of the first loop in the analyzed
1938    loop nest.  */
1939
1940 static void
1941 build_classic_dir_vector (struct data_dependence_relation *ddr,
1942                           int nb_loops, unsigned int first_loop)
1943 {
1944   unsigned i;
1945   lambda_vector dir_v, init_v;
1946
1947   dir_v = lambda_vector_new (nb_loops);
1948   init_v = lambda_vector_new (nb_loops);
1949   lambda_vector_clear (dir_v, nb_loops);
1950   lambda_vector_clear (init_v, nb_loops);
1951
1952   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
1953     return;
1954
1955   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
1956     {
1957       tree access_fn_a, access_fn_b;
1958       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
1959
1960       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
1961         {
1962           non_affine_dependence_relation (ddr);
1963           return;
1964         }
1965
1966       access_fn_a = DR_ACCESS_FN (DDR_A (ddr), i);
1967       access_fn_b = DR_ACCESS_FN (DDR_B (ddr), i);
1968       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
1969           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
1970         {
1971           int dist, loop_nb;
1972           enum data_dependence_direction dir = dir_star;
1973           int loop_nb_a = CHREC_VARIABLE (access_fn_a);
1974           int loop_nb_b = CHREC_VARIABLE (access_fn_b);
1975           struct loop *loop_a = current_loops->parray[loop_nb_a];
1976           struct loop *loop_b = current_loops->parray[loop_nb_b];
1977
1978           if (loop_nb_a != loop_nb_b
1979               && !flow_loop_nested_p (loop_a, loop_b)
1980               && !flow_loop_nested_p (loop_b, loop_a))
1981             {
1982               /* Example: when there are two consecutive loops,
1983
1984                  | loop_1
1985                  |   A[{0, +, 1}_1]
1986                  | endloop_1
1987                  | loop_2
1988                  |   A[{0, +, 1}_2]
1989                  | endloop_2
1990
1991                  the dependence relation cannot be captured by the
1992                  distance abstraction.  */
1993               non_affine_dependence_relation (ddr);
1994               return;
1995             }
1996
1997           /* The dependence is carried by the outermost loop.  Example:
1998              | loop_1
1999              |   A[{4, +, 1}_1]
2000              |   loop_2
2001              |     A[{5, +, 1}_2]
2002              |   endloop_2
2003              | endloop_1
2004              In this case, the dependence is carried by loop_1.  */
2005           loop_nb = loop_nb_a < loop_nb_b ? loop_nb_a : loop_nb_b;
2006           loop_nb -= first_loop;
2007
2008           /* If the loop number is still greater than the number of
2009              loops we've been asked to analyze, or negative,
2010              something is borked.  */
2011           gcc_assert (loop_nb >= 0);
2012           gcc_assert (loop_nb < nb_loops);
2013
2014           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2015             {
2016               non_affine_dependence_relation (ddr);
2017               return;
2018             }
2019
2020           dist = int_cst_value (SUB_DISTANCE (subscript));
2021
2022           if (dist == 0)
2023             dir = dir_equal;
2024           else if (dist > 0)
2025             dir = dir_positive;
2026           else if (dist < 0)
2027             dir = dir_negative;
2028
2029           /* This is the subscript coupling test.
2030              | loop i = 0, N, 1
2031              |   T[i+1][i] = ...
2032              |   ... = T[i][i]
2033              | endloop
2034              There is no dependence.  */
2035           if (init_v[loop_nb] != 0
2036               && dir != dir_star
2037               && (enum data_dependence_direction) dir_v[loop_nb] != dir
2038               && (enum data_dependence_direction) dir_v[loop_nb] != dir_star)
2039             {
2040               finalize_ddr_dependent (ddr, chrec_known);
2041               return;
2042             }
2043
2044           dir_v[loop_nb] = dir;
2045           init_v[loop_nb] = 1;
2046         }
2047     }
2048
2049   /* There is a distance of 1 on all the outer loops:
2050
2051      Example: there is a dependence of distance 1 on loop_1 for the array A.
2052      | loop_1
2053      |   A[5] = ...
2054      | endloop
2055   */
2056   {
2057     struct loop *lca, *loop_a, *loop_b;
2058     struct data_reference *a = DDR_A (ddr);
2059     struct data_reference *b = DDR_B (ddr);
2060     int lca_nb;
2061     loop_a = loop_containing_stmt (DR_STMT (a));
2062     loop_b = loop_containing_stmt (DR_STMT (b));
2063
2064     /* Get the common ancestor loop.  */
2065     lca = find_common_loop (loop_a, loop_b);
2066     lca_nb = lca->num - first_loop;
2067
2068     gcc_assert (lca_nb >= 0);
2069     gcc_assert (lca_nb < nb_loops);
2070
2071     /* For each outer loop where init_v is not set, the accesses are
2072        in dependence of distance 1 in the loop.  */
2073     if (lca != loop_a
2074         && lca != loop_b
2075         && init_v[lca_nb] == 0)
2076       dir_v[lca_nb] = dir_positive;
2077
2078     lca = lca->outer;
2079     if (lca)
2080       {
2081         lca_nb = lca->num - first_loop;
2082         while (lca->depth != 0)
2083           {
2084             /* If we're considering just a sub-nest, then don't record
2085                any information on the outer loops.  */
2086             if (lca_nb < 0)
2087               break;
2088
2089             gcc_assert (lca_nb < nb_loops);
2090
2091             if (init_v[lca_nb] == 0)
2092               dir_v[lca_nb] = dir_positive;
2093             lca = lca->outer;
2094             lca_nb = lca->num - first_loop;
2095
2096           }
2097       }
2098   }
2099
2100   DDR_DIR_VECT (ddr) = dir_v;
2101   DDR_SIZE_VECT (ddr) = nb_loops;
2102 }
2103
2104 /* Returns true when all the access functions of A are affine or
2105    constant.  */
2106
2107 static bool
2108 access_functions_are_affine_or_constant_p (struct data_reference *a)
2109 {
2110   unsigned int i;
2111   varray_type fns = DR_ACCESS_FNS (a);
2112
2113   for (i = 0; i < VARRAY_ACTIVE_SIZE (fns); i++)
2114     if (!evolution_function_is_constant_p (VARRAY_TREE (fns, i))
2115         && !evolution_function_is_affine_multivariate_p (VARRAY_TREE (fns, i)))
2116       return false;
2117
2118   return true;
2119 }
2120
2121 /* This computes the affine dependence relation between A and B.
2122    CHREC_KNOWN is used for representing the independence between two
2123    accesses, while CHREC_DONT_KNOW is used for representing the unknown
2124    relation.
2125
2126    Note that it is possible to stop the computation of the dependence
2127    relation the first time we detect a CHREC_KNOWN element for a given
2128    subscript.  */
2129
2130 void
2131 compute_affine_dependence (struct data_dependence_relation *ddr)
2132 {
2133   struct data_reference *dra = DDR_A (ddr);
2134   struct data_reference *drb = DDR_B (ddr);
2135
2136   if (dump_file && (dump_flags & TDF_DETAILS))
2137     {
2138       fprintf (dump_file, "(compute_affine_dependence\n");
2139       fprintf (dump_file, "  (stmt_a = \n");
2140       print_generic_expr (dump_file, DR_STMT (dra), 0);
2141       fprintf (dump_file, ")\n  (stmt_b = \n");
2142       print_generic_expr (dump_file, DR_STMT (drb), 0);
2143       fprintf (dump_file, ")\n");
2144     }
2145
2146   /* Analyze only when the dependence relation is not yet known.  */
2147   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2148     {
2149       if (access_functions_are_affine_or_constant_p (dra)
2150           && access_functions_are_affine_or_constant_p (drb))
2151         subscript_dependence_tester (ddr);
2152
2153       /* As a last case, if the dependence cannot be determined, or if
2154          the dependence is considered too difficult to determine, answer
2155          "don't know".  */
2156       else
2157         finalize_ddr_dependent (ddr, chrec_dont_know);
2158     }
2159
2160   if (dump_file && (dump_flags & TDF_DETAILS))
2161     fprintf (dump_file, ")\n");
2162 }
2163
2164 /* Compute a subset of the data dependence relation graph.  Don't
2165    compute read-read relations, and avoid the computation of the
2166    opposite relation, i.e. when AB has been computed, don't compute BA.
2167    DATAREFS contains a list of data references, and the result is set
2168    in DEPENDENCE_RELATIONS.  */
2169
2170 static void
2171 compute_all_dependences (varray_type datarefs,
2172                          varray_type *dependence_relations)
2173 {
2174   unsigned int i, j, N;
2175
2176   N = VARRAY_ACTIVE_SIZE (datarefs);
2177
2178   for (i = 0; i < N; i++)
2179     for (j = i; j < N; j++)
2180       {
2181         struct data_reference *a, *b;
2182         struct data_dependence_relation *ddr;
2183
2184         a = VARRAY_GENERIC_PTR (datarefs, i);
2185         b = VARRAY_GENERIC_PTR (datarefs, j);
2186         ddr = initialize_data_dependence_relation (a, b);
2187
2188         VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2189         compute_affine_dependence (ddr);
2190         compute_subscript_distance (ddr);
2191       }
2192 }
2193
2194 /* Search the data references in LOOP, and record the information into
2195    DATAREFS.  Returns chrec_dont_know when failing to analyze a
2196    difficult case, returns NULL_TREE otherwise.
2197
2198    FIXME: This is a "dumb" walker over all the trees in the loop body.
2199    Find another technique that avoids this costly walk.  This is
2200    acceptable for the moment, since this function is used only for
2201    debugging purposes.  */
2202
2203 tree
2204 find_data_references_in_loop (struct loop *loop, varray_type *datarefs)
2205 {
2206   bool dont_know_node_not_inserted = true;
2207   basic_block bb;
2208   block_stmt_iterator bsi;
2209
2210   FOR_EACH_BB (bb)
2211     {
2212       if (!flow_bb_inside_loop_p (loop, bb))
2213         continue;
2214
2215       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
2216         {
2217           tree stmt = bsi_stmt (bsi);
2218           stmt_ann_t ann = stmt_ann (stmt);
2219
2220           if (TREE_CODE (stmt) != MODIFY_EXPR)
2221             continue;
2222
2223           if (!VUSE_OPS (ann)
2224               && !V_MUST_DEF_OPS (ann)
2225               && !V_MAY_DEF_OPS (ann))
2226             continue;
2227
2228           /* In the GIMPLE representation, a modify expression
2229              contains a single load or store to memory.  */
2230           if (TREE_CODE (TREE_OPERAND (stmt, 0)) == ARRAY_REF)
2231             VARRAY_PUSH_GENERIC_PTR
2232                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 0),
2233                                                false));
2234
2235           else if (TREE_CODE (TREE_OPERAND (stmt, 1)) == ARRAY_REF)
2236             VARRAY_PUSH_GENERIC_PTR
2237                     (*datarefs, analyze_array (stmt, TREE_OPERAND (stmt, 1),
2238                                                true));
2239
2240           else
2241             {
2242               if (dont_know_node_not_inserted)
2243                 {
2244                   struct data_reference *res;
2245                   res = xmalloc (sizeof (struct data_reference));
2246                   DR_STMT (res) = NULL_TREE;
2247                   DR_REF (res) = NULL_TREE;
2248                   DR_ACCESS_FNS (res) = NULL;
2249                   DR_BASE_NAME (res) = NULL;
2250                   DR_IS_READ (res) = false;
2251                   VARRAY_PUSH_GENERIC_PTR (*datarefs, res);
2252
2253                   dont_know_node_not_inserted = false;
2254                 }
2255             }
2256
2257           /* When there are no defs in the loop, the loop is parallel.  */
2258           if (NUM_V_MAY_DEFS (STMT_V_MAY_DEF_OPS (stmt)) > 0
2259               || NUM_V_MUST_DEFS (STMT_V_MUST_DEF_OPS (stmt)) > 0)
2260             bb->loop_father->parallel_p = false;
2261         }
2262
2263       if (bb->loop_father->estimated_nb_iterations == NULL_TREE)
2264         compute_estimated_nb_iterations (bb->loop_father);
2265     }
2266
2267   return dont_know_node_not_inserted ? NULL_TREE : chrec_dont_know;
2268 }
2269
2270 \f
2271
2272 /* This section contains all the entry points.  */
2273
2274 /* Given a loop nest LOOP, the following vectors are returned:
2275    *DATAREFS is initialized to all the array elements contained in this loop,
2276    *DEPENDENCE_RELATIONS contains the relations between the data references.  */
2277
2278 void
2279 compute_data_dependences_for_loop (unsigned nb_loops,
2280                                    struct loop *loop,
2281                                    varray_type *datarefs,
2282                                    varray_type *dependence_relations)
2283 {
2284   unsigned int i;
2285
2286   /* If one of the data references is not computable, give up without
2287      spending time to compute other dependences.  */
2288   if (find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
2289     {
2290       struct data_dependence_relation *ddr;
2291
2292       /* Insert a single relation into dependence_relations:
2293          chrec_dont_know.  */
2294       ddr = initialize_data_dependence_relation (NULL, NULL);
2295       VARRAY_PUSH_GENERIC_PTR (*dependence_relations, ddr);
2296       build_classic_dist_vector (ddr, nb_loops, loop->num);
2297       build_classic_dir_vector (ddr, nb_loops, loop->num);
2298       return;
2299     }
2300
2301   compute_all_dependences (*datarefs, dependence_relations);
2302
2303   for (i = 0; i < VARRAY_ACTIVE_SIZE (*dependence_relations); i++)
2304     {
2305       struct data_dependence_relation *ddr;
2306       ddr = VARRAY_GENERIC_PTR (*dependence_relations, i);
2307       build_classic_dist_vector (ddr, nb_loops, loop->num);
2308       build_classic_dir_vector (ddr, nb_loops, loop->num);
2309     }
2310 }
2311
2312 /* Entry point (for testing only).  Analyze all the data references
2313    and the dependence relations.
2314
2315    The data references are computed first.
2316
2317    A relation on these nodes is represented by a complete graph.  Some
2318    of the relations could be of no interest, thus the relations can be
2319    computed on demand.
2320
2321    In the following function we compute all the relations.  This is
2322    just a first implementation that is here for:
2323    - for showing how to ask for the dependence relations,
2324    - for the debugging the whole dependence graph,
2325    - for the dejagnu testcases and maintenance.
2326
2327    It is possible to ask only for a part of the graph, avoiding to
2328    compute the whole dependence graph.  The computed dependences are
2329    stored in a knowledge base (KB) such that later queries don't
2330    recompute the same information.  The implementation of this KB is
2331    transparent to the optimizer, and thus the KB can be changed with a
2332    more efficient implementation, or the KB could be disabled.  */
2333
2334 void
2335 analyze_all_data_dependences (struct loops *loops)
2336 {
2337   unsigned int i;
2338   varray_type datarefs;
2339   varray_type dependence_relations;
2340   int nb_data_refs = 10;
2341
2342   VARRAY_GENERIC_PTR_INIT (datarefs, nb_data_refs, "datarefs");
2343   VARRAY_GENERIC_PTR_INIT (dependence_relations,
2344                            nb_data_refs * nb_data_refs,
2345                            "dependence_relations");
2346
2347   /* Compute DDs on the whole function.  */
2348   compute_data_dependences_for_loop (loops->num, loops->parray[0],
2349                                      &datarefs, &dependence_relations);
2350
2351   if (dump_file)
2352     {
2353       dump_data_dependence_relations (dump_file, dependence_relations);
2354       fprintf (dump_file, "\n\n");
2355
2356       if (dump_flags & TDF_DETAILS)
2357         dump_dist_dir_vectors (dump_file, dependence_relations);
2358
2359       if (dump_flags & TDF_STATS)
2360         {
2361           unsigned nb_top_relations = 0;
2362           unsigned nb_bot_relations = 0;
2363           unsigned nb_basename_differ = 0;
2364           unsigned nb_chrec_relations = 0;
2365
2366           for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2367             {
2368               struct data_dependence_relation *ddr;
2369               ddr = VARRAY_GENERIC_PTR (dependence_relations, i);
2370
2371               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
2372                 nb_top_relations++;
2373
2374               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
2375                 {
2376                   struct data_reference *a = DDR_A (ddr);
2377                   struct data_reference *b = DDR_B (ddr);
2378                   bool differ_p;
2379
2380                   if (DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b)
2381                       || (array_base_name_differ_p (a, b, &differ_p) && differ_p))
2382                     nb_basename_differ++;
2383                   else
2384                     nb_bot_relations++;
2385                 }
2386
2387               else
2388                 nb_chrec_relations++;
2389             }
2390
2391           gather_stats_on_scev_database ();
2392         }
2393     }
2394
2395   free_dependence_relations (dependence_relations);
2396   free_data_refs (datarefs);
2397 }
2398
2399 /* Free the memory used by a data dependence relation DDR.  */
2400
2401 void
2402 free_dependence_relation (struct data_dependence_relation *ddr)
2403 {
2404   if (ddr == NULL)
2405     return;
2406
2407   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
2408     varray_clear (DDR_SUBSCRIPTS (ddr));
2409   free (ddr);
2410 }
2411
2412 /* Free the memory used by the data dependence relations from
2413    DEPENDENCE_RELATIONS.  */
2414
2415 void
2416 free_dependence_relations (varray_type dependence_relations)
2417 {
2418   unsigned int i;
2419   if (dependence_relations == NULL)
2420     return;
2421
2422   for (i = 0; i < VARRAY_ACTIVE_SIZE (dependence_relations); i++)
2423     free_dependence_relation (VARRAY_GENERIC_PTR (dependence_relations, i));
2424   varray_clear (dependence_relations);
2425 }
2426
2427 /* Free the memory used by the data references from DATAREFS.  */
2428
2429 void
2430 free_data_refs (varray_type datarefs)
2431 {
2432   unsigned int i;
2433
2434   if (datarefs == NULL)
2435     return;
2436
2437   for (i = 0; i < VARRAY_ACTIVE_SIZE (datarefs); i++)
2438     {
2439       struct data_reference *dr = (struct data_reference *)
2440         VARRAY_GENERIC_PTR (datarefs, i);
2441       if (dr && DR_ACCESS_FNS (dr))
2442         varray_clear (DR_ACCESS_FNS (dr));
2443     }
2444   varray_clear (datarefs);
2445 }
2446