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