gcc/tree-data-ref.c

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
   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, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, 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 "ggc.h"
  82 #include "tree.h"
  83
  84 /* These RTL headers are needed for basic-block.h.  */
  85 #include "rtl.h"
  86 #include "basic-block.h"
  87 #include "diagnostic.h"
  88 #include "tree-flow.h"
  89 #include "tree-dump.h"
  90 #include "timevar.h"
  91 #include "cfgloop.h"
  92 #include "tree-chrec.h"
  93 #include "tree-data-ref.h"
  94 #include "tree-scalar-evolution.h"
  95 #include "tree-pass.h"
  96 #include "langhooks.h"
  97
  98 static struct datadep_stats
  99 {
 100   int num_dependence_tests;
 101   int num_dependence_dependent;
 102   int num_dependence_independent;
 103   int num_dependence_undetermined;
 104
 105   int num_subscript_tests;
 106   int num_subscript_undetermined;
 107   int num_same_subscript_function;
 108
 109   int num_ziv;
 110   int num_ziv_independent;
 111   int num_ziv_dependent;
 112   int num_ziv_unimplemented;
 113
 114   int num_siv;
 115   int num_siv_independent;
 116   int num_siv_dependent;
 117   int num_siv_unimplemented;
 118
 119   int num_miv;
 120   int num_miv_independent;
 121   int num_miv_dependent;
 122   int num_miv_unimplemented;
 123 } dependence_stats;
 124
 125 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
 126                                            struct data_reference *,
 127                                            struct data_reference *,
 128                                            struct loop *);
 129 /* Returns true iff A divides B.  */
 130
 131 static inline bool
 132 tree_fold_divides_p (tree a, tree b)
 133 {
 134   gcc_assert (TREE_CODE (a) == INTEGER_CST);
 135   gcc_assert (TREE_CODE (b) == INTEGER_CST);
 136   return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
 137 }
 138
 139 /* Returns true iff A divides B.  */
 140
 141 static inline bool
 142 int_divides_p (int a, int b)
 143 {
 144   return ((b % a) == 0);
 145 }
 146
 147 \f
 148
 149 /* Dump into FILE all the data references from DATAREFS.  */
 150
 151 void
 152 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
 153 {
 154   unsigned int i;
 155   struct data_reference *dr;
 156
 157   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
 158     dump_data_reference (file, dr);
 159 }
 160
 161 /* Dump into FILE all the dependence relations from DDRS.  */
 162
 163 void
 164 dump_data_dependence_relations (FILE *file,
 165                                 VEC (ddr_p, heap) *ddrs)
 166 {
 167   unsigned int i;
 168   struct data_dependence_relation *ddr;
 169
 170   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 171     dump_data_dependence_relation (file, ddr);
 172 }
 173
 174 /* Dump function for a DATA_REFERENCE structure.  */
 175
 176 void
 177 dump_data_reference (FILE *outf,
 178                      struct data_reference *dr)
 179 {
 180   unsigned int i;
 181
 182   fprintf (outf, "(Data Ref: \n  stmt: ");
 183   print_generic_stmt (outf, DR_STMT (dr), 0);
 184   fprintf (outf, "  ref: ");
 185   print_generic_stmt (outf, DR_REF (dr), 0);
 186   fprintf (outf, "  base_object: ");
 187   print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
 188
 189   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
 190     {
 191       fprintf (outf, "  Access function %d: ", i);
 192       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
 193     }
 194   fprintf (outf, ")\n");
 195 }
 196
 197 /* Dumps the affine function described by FN to the file OUTF.  */
 198
 199 static void
 200 dump_affine_function (FILE *outf, affine_fn fn)
 201 {
 202   unsigned i;
 203   tree coef;
 204
 205   print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
 206   for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
 207     {
 208       fprintf (outf, " + ");
 209       print_generic_expr (outf, coef, TDF_SLIM);
 210       fprintf (outf, " * x_%u", i);
 211     }
 212 }
 213
 214 /* Dumps the conflict function CF to the file OUTF.  */
 215
 216 static void
 217 dump_conflict_function (FILE *outf, conflict_function *cf)
 218 {
 219   unsigned i;
 220
 221   if (cf->n == NO_DEPENDENCE)
 222     fprintf (outf, "no dependence\n");
 223   else if (cf->n == NOT_KNOWN)
 224     fprintf (outf, "not known\n");
 225   else
 226     {
 227       for (i = 0; i < cf->n; i++)
 228         {
 229           fprintf (outf, "[");
 230           dump_affine_function (outf, cf->fns[i]);
 231           fprintf (outf, "]\n");
 232         }
 233     }
 234 }
 235
 236 /* Dump function for a SUBSCRIPT structure.  */
 237
 238 void
 239 dump_subscript (FILE *outf, struct subscript *subscript)
 240 {
 241   conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
 242
 243   fprintf (outf, "\n (subscript \n");
 244   fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
 245   dump_conflict_function (outf, cf);
 246   if (CF_NONTRIVIAL_P (cf))
 247     {
 248       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 249       fprintf (outf, "  last_conflict: ");
 250       print_generic_stmt (outf, last_iteration, 0);
 251     }
 252
 253   cf = SUB_CONFLICTS_IN_B (subscript);
 254   fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
 255   dump_conflict_function (outf, cf);
 256   if (CF_NONTRIVIAL_P (cf))
 257     {
 258       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 259       fprintf (outf, "  last_conflict: ");
 260       print_generic_stmt (outf, last_iteration, 0);
 261     }
 262
 263   fprintf (outf, "  (Subscript distance: ");
 264   print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
 265   fprintf (outf, "  )\n");
 266   fprintf (outf, " )\n");
 267 }
 268
 269 /* Print the classic direction vector DIRV to OUTF.  */
 270
 271 void
 272 print_direction_vector (FILE *outf,
 273                         lambda_vector dirv,
 274                         int length)
 275 {
 276   int eq;
 277
 278   for (eq = 0; eq < length; eq++)
 279     {
 280       enum data_dependence_direction dir = dirv[eq];
 281
 282       switch (dir)
 283         {
 284         case dir_positive:
 285           fprintf (outf, "    +");
 286           break;
 287         case dir_negative:
 288           fprintf (outf, "    -");
 289           break;
 290         case dir_equal:
 291           fprintf (outf, "    =");
 292           break;
 293         case dir_positive_or_equal:
 294           fprintf (outf, "   +=");
 295           break;
 296         case dir_positive_or_negative:
 297           fprintf (outf, "   +-");
 298           break;
 299         case dir_negative_or_equal:
 300           fprintf (outf, "   -=");
 301           break;
 302         case dir_star:
 303           fprintf (outf, "    *");
 304           break;
 305         default:
 306           fprintf (outf, "indep");
 307           break;
 308         }
 309     }
 310   fprintf (outf, "\n");
 311 }
 312
 313 /* Print a vector of direction vectors.  */
 314
 315 void
 316 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
 317                    int length)
 318 {
 319   unsigned j;
 320   lambda_vector v;
 321
 322   for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
 323     print_direction_vector (outf, v, length);
 324 }
 325
 326 /* Print a vector of distance vectors.  */
 327
 328 void
 329 print_dist_vectors  (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
 330                      int length)
 331 {
 332   unsigned j;
 333   lambda_vector v;
 334
 335   for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
 336     print_lambda_vector (outf, v, length);
 337 }
 338
 339 /* Debug version.  */
 340
 341 void
 342 debug_data_dependence_relation (struct data_dependence_relation *ddr)
 343 {
 344   dump_data_dependence_relation (stderr, ddr);
 345 }
 346
 347 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
 348
 349 void
 350 dump_data_dependence_relation (FILE *outf,
 351                                struct data_dependence_relation *ddr)
 352 {
 353   struct data_reference *dra, *drb;
 354
 355   dra = DDR_A (ddr);
 356   drb = DDR_B (ddr);
 357   fprintf (outf, "(Data Dep: \n");
 358   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 359     fprintf (outf, "    (don't know)\n");
 360
 361   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 362     fprintf (outf, "    (no dependence)\n");
 363
 364   else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 365     {
 366       unsigned int i;
 367       struct loop *loopi;
 368
 369       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 370         {
 371           fprintf (outf, "  access_fn_A: ");
 372           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
 373           fprintf (outf, "  access_fn_B: ");
 374           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
 375           dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
 376         }
 377
 378       fprintf (outf, "  inner loop index: %d\n", DDR_INNER_LOOP (ddr));
 379       fprintf (outf, "  loop nest: (");
 380       for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
 381         fprintf (outf, "%d ", loopi->num);
 382       fprintf (outf, ")\n");
 383
 384       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
 385         {
 386           fprintf (outf, "  distance_vector: ");
 387           print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
 388                                DDR_NB_LOOPS (ddr));
 389         }
 390
 391       for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
 392         {
 393           fprintf (outf, "  direction_vector: ");
 394           print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
 395                                   DDR_NB_LOOPS (ddr));
 396         }
 397     }
 398
 399   fprintf (outf, ")\n");
 400 }
 401
 402 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
 403
 404 void
 405 dump_data_dependence_direction (FILE *file,
 406                                 enum data_dependence_direction dir)
 407 {
 408   switch (dir)
 409     {
 410     case dir_positive:
 411       fprintf (file, "+");
 412       break;
 413
 414     case dir_negative:
 415       fprintf (file, "-");
 416       break;
 417
 418     case dir_equal:
 419       fprintf (file, "=");
 420       break;
 421
 422     case dir_positive_or_negative:
 423       fprintf (file, "+-");
 424       break;
 425
 426     case dir_positive_or_equal:
 427       fprintf (file, "+=");
 428       break;
 429
 430     case dir_negative_or_equal:
 431       fprintf (file, "-=");
 432       break;
 433
 434     case dir_star:
 435       fprintf (file, "*");
 436       break;
 437
 438     default:
 439       break;
 440     }
 441 }
 442
 443 /* Dumps the distance and direction vectors in FILE.  DDRS contains
 444    the dependence relations, and VECT_SIZE is the size of the
 445    dependence vectors, or in other words the number of loops in the
 446    considered nest.  */
 447
 448 void
 449 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
 450 {
 451   unsigned int i, j;
 452   struct data_dependence_relation *ddr;
 453   lambda_vector v;
 454
 455   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 456     if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
 457       {
 458         for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
 459           {
 460             fprintf (file, "DISTANCE_V (");
 461             print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
 462             fprintf (file, ")\n");
 463           }
 464
 465         for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
 466           {
 467             fprintf (file, "DIRECTION_V (");
 468             print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
 469             fprintf (file, ")\n");
 470           }
 471       }
 472
 473   fprintf (file, "\n\n");
 474 }
 475
 476 /* Dumps the data dependence relations DDRS in FILE.  */
 477
 478 void
 479 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
 480 {
 481   unsigned int i;
 482   struct data_dependence_relation *ddr;
 483
 484   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 485     dump_data_dependence_relation (file, ddr);
 486
 487   fprintf (file, "\n\n");
 488 }
 489
 490 /* Expresses EXP as VAR + OFF, where off is a constant.  The type of OFF
 491    will be ssizetype.  */
 492
 493 static void
 494 split_constant_offset (tree exp, tree *var, tree *off)
 495 {
 496   tree type = TREE_TYPE (exp), otype;
 497   tree var0, var1;
 498   tree off0, off1;
 499   enum tree_code code;
 500
 501   *var = exp;
 502   STRIP_NOPS (exp);
 503   otype = TREE_TYPE (exp);
 504   code = TREE_CODE (exp);
 505
 506   switch (code)
 507     {
 508     case INTEGER_CST:
 509       *var = build_int_cst (type, 0);
 510       *off = fold_convert (ssizetype, exp);
 511       return;
 512
 513     case POINTER_PLUS_EXPR:
 514       code = PLUS_EXPR;
 515       /* FALLTHROUGH */
 516     case PLUS_EXPR:
 517     case MINUS_EXPR:
 518       split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
 519       split_constant_offset (TREE_OPERAND (exp, 1), &var1, &off1);
 520       *var = fold_convert (type, fold_build2 (TREE_CODE (exp), otype,
 521                                               var0, var1));
 522       *off = size_binop (code, off0, off1);
 523       return;
 524
 525     case MULT_EXPR:
 526       off1 = TREE_OPERAND (exp, 1);
 527       if (TREE_CODE (off1) != INTEGER_CST)
 528         break;
 529
 530       split_constant_offset (TREE_OPERAND (exp, 0), &var0, &off0);
 531       *var = fold_convert (type, fold_build2 (MULT_EXPR, otype,
 532                                               var0, off1));
 533       *off = size_binop (MULT_EXPR, off0, fold_convert (ssizetype, off1));
 534       return;
 535
 536     case ADDR_EXPR:
 537       {
 538         tree op, base, poffset;
 539         HOST_WIDE_INT pbitsize, pbitpos;
 540         enum machine_mode pmode;
 541         int punsignedp, pvolatilep;
 542
 543         op = TREE_OPERAND (exp, 0);
 544         if (!handled_component_p (op))
 545           break;
 546
 547         base = get_inner_reference (op, &pbitsize, &pbitpos, &poffset,
 548                                     &pmode, &punsignedp, &pvolatilep, false);
 549
 550         if (pbitpos % BITS_PER_UNIT != 0)
 551           break;
 552         base = build_fold_addr_expr (base);
 553         off0 = ssize_int (pbitpos / BITS_PER_UNIT);
 554
 555         if (poffset)
 556           {
 557             split_constant_offset (poffset, &poffset, &off1);
 558             off0 = size_binop (PLUS_EXPR, off0, off1);
 559             base = fold_build2 (PLUS_EXPR, TREE_TYPE (base),
 560                                 base,
 561                                 fold_convert (TREE_TYPE (base), poffset));
 562           }
 563
 564         *var = fold_convert (type, base);
 565         *off = off0;
 566         return;
 567       }
 568
 569     default:
 570       break;
 571     }
 572
 573   *off = ssize_int (0);
 574 }
 575
 576 /* Returns the address ADDR of an object in a canonical shape (without nop
 577    casts, and with type of pointer to the object).  */
 578
 579 static tree
 580 canonicalize_base_object_address (tree addr)
 581 {
 582   tree orig = addr;
 583
 584   STRIP_NOPS (addr);
 585
 586   /* The base address may be obtained by casting from integer, in that case
 587      keep the cast.  */
 588   if (!POINTER_TYPE_P (TREE_TYPE (addr)))
 589     return orig;
 590
 591   if (TREE_CODE (addr) != ADDR_EXPR)
 592     return addr;
 593
 594   return build_fold_addr_expr (TREE_OPERAND (addr, 0));
 595 }
 596
 597 /* Analyzes the behavior of the memory reference DR in the innermost loop that
 598    contains it.  */
 599
 600 void
 601 dr_analyze_innermost (struct data_reference *dr)
 602 {
 603   tree stmt = DR_STMT (dr);
 604   struct loop *loop = loop_containing_stmt (stmt);
 605   tree ref = DR_REF (dr);
 606   HOST_WIDE_INT pbitsize, pbitpos;
 607   tree base, poffset;
 608   enum machine_mode pmode;
 609   int punsignedp, pvolatilep;
 610   affine_iv base_iv, offset_iv;
 611   tree init, dinit, step;
 612
 613   if (dump_file && (dump_flags & TDF_DETAILS))
 614     fprintf (dump_file, "analyze_innermost: ");
 615
 616   base = get_inner_reference (ref, &pbitsize, &pbitpos, &poffset,
 617                               &pmode, &punsignedp, &pvolatilep, false);
 618   gcc_assert (base != NULL_TREE);
 619
 620   if (pbitpos % BITS_PER_UNIT != 0)
 621     {
 622       if (dump_file && (dump_flags & TDF_DETAILS))
 623         fprintf (dump_file, "failed: bit offset alignment.\n");
 624       return;
 625     }
 626
 627   base = build_fold_addr_expr (base);
 628   if (!simple_iv (loop, stmt, base, &base_iv, false))
 629     {
 630       if (dump_file && (dump_flags & TDF_DETAILS))
 631         fprintf (dump_file, "failed: evolution of base is not affine.\n");
 632       return;
 633     }
 634   if (!poffset)
 635     {
 636       offset_iv.base = ssize_int (0);
 637       offset_iv.step = ssize_int (0);
 638     }
 639   else if (!simple_iv (loop, stmt, poffset, &offset_iv, false))
 640     {
 641       if (dump_file && (dump_flags & TDF_DETAILS))
 642         fprintf (dump_file, "failed: evolution of offset is not affine.\n");
 643       return;
 644     }
 645
 646   init = ssize_int (pbitpos / BITS_PER_UNIT);
 647   split_constant_offset (base_iv.base, &base_iv.base, &dinit);
 648   init =  size_binop (PLUS_EXPR, init, dinit);
 649   split_constant_offset (offset_iv.base, &offset_iv.base, &dinit);
 650   init =  size_binop (PLUS_EXPR, init, dinit);
 651
 652   step = size_binop (PLUS_EXPR,
 653                      fold_convert (ssizetype, base_iv.step),
 654                      fold_convert (ssizetype, offset_iv.step));
 655
 656   DR_BASE_ADDRESS (dr) = canonicalize_base_object_address (base_iv.base);
 657
 658   DR_OFFSET (dr) = fold_convert (ssizetype, offset_iv.base);
 659   DR_INIT (dr) = init;
 660   DR_STEP (dr) = step;
 661
 662   DR_ALIGNED_TO (dr) = size_int (highest_pow2_factor (offset_iv.base));
 663
 664   if (dump_file && (dump_flags & TDF_DETAILS))
 665     fprintf (dump_file, "success.\n");
 666 }
 667
 668 /* Determines the base object and the list of indices of memory reference
 669    DR, analyzed in loop nest NEST.  */
 670
 671 static void
 672 dr_analyze_indices (struct data_reference *dr, struct loop *nest)
 673 {
 674   tree stmt = DR_STMT (dr);
 675   struct loop *loop = loop_containing_stmt (stmt);
 676   VEC (tree, heap) *access_fns = NULL;
 677   tree ref = unshare_expr (DR_REF (dr)), aref = ref, op;
 678   tree base, off, access_fn;
 679
 680   while (handled_component_p (aref))
 681     {
 682       if (TREE_CODE (aref) == ARRAY_REF)
 683         {
 684           op = TREE_OPERAND (aref, 1);
 685           access_fn = analyze_scalar_evolution (loop, op);
 686           access_fn = resolve_mixers (nest, access_fn);
 687           VEC_safe_push (tree, heap, access_fns, access_fn);
 688
 689           TREE_OPERAND (aref, 1) = build_int_cst (TREE_TYPE (op), 0);
 690         }
 691
 692       aref = TREE_OPERAND (aref, 0);
 693     }
 694
 695   if (INDIRECT_REF_P (aref))
 696     {
 697       op = TREE_OPERAND (aref, 0);
 698       access_fn = analyze_scalar_evolution (loop, op);
 699       access_fn = resolve_mixers (nest, access_fn);
 700       base = initial_condition (access_fn);
 701       split_constant_offset (base, &base, &off);
 702       access_fn = chrec_replace_initial_condition (access_fn,
 703                         fold_convert (TREE_TYPE (base), off));
 704
 705       TREE_OPERAND (aref, 0) = base;
 706       VEC_safe_push (tree, heap, access_fns, access_fn);
 707     }
 708
 709   DR_BASE_OBJECT (dr) = ref;
 710   DR_ACCESS_FNS (dr) = access_fns;
 711 }
 712
 713 /* Extracts the alias analysis information from the memory reference DR.  */
 714
 715 static void
 716 dr_analyze_alias (struct data_reference *dr)
 717 {
 718   tree stmt = DR_STMT (dr);
 719   tree ref = DR_REF (dr);
 720   tree base = get_base_address (ref), addr, smt = NULL_TREE;
 721   ssa_op_iter it;
 722   tree op;
 723   bitmap vops;
 724
 725   if (DECL_P (base))
 726     smt = base;
 727   else if (INDIRECT_REF_P (base))
 728     {
 729       addr = TREE_OPERAND (base, 0);
 730       if (TREE_CODE (addr) == SSA_NAME)
 731         {
 732           smt = symbol_mem_tag (SSA_NAME_VAR (addr));
 733           DR_PTR_INFO (dr) = SSA_NAME_PTR_INFO (addr);
 734         }
 735     }
 736
 737   DR_SYMBOL_TAG (dr) = smt;
 738   if (smt && var_can_have_subvars (smt))
 739     DR_SUBVARS (dr) = get_subvars_for_var (smt);
 740
 741   vops = BITMAP_ALLOC (NULL);
 742   FOR_EACH_SSA_TREE_OPERAND (op, stmt, it, SSA_OP_VIRTUAL_USES)
 743     {
 744       bitmap_set_bit (vops, DECL_UID (SSA_NAME_VAR (op)));
 745     }
 746
 747   DR_VOPS (dr) = vops;
 748 }
 749
 750 /* Returns true if the address of DR is invariant.  */
 751
 752 static bool
 753 dr_address_invariant_p (struct data_reference *dr)
 754 {
 755   unsigned i;
 756   tree idx;
 757
 758   for (i = 0; VEC_iterate (tree, DR_ACCESS_FNS (dr), i, idx); i++)
 759     if (tree_contains_chrecs (idx, NULL))
 760       return false;
 761
 762   return true;
 763 }
 764
 765 /* Frees data reference DR.  */
 766
 767 static void
 768 free_data_ref (data_reference_p dr)
 769 {
 770   BITMAP_FREE (DR_VOPS (dr));
 771   VEC_free (tree, heap, DR_ACCESS_FNS (dr));
 772   free (dr);
 773 }
 774
 775 /* Analyzes memory reference MEMREF accessed in STMT.  The reference
 776    is read if IS_READ is true, write otherwise.  Returns the
 777    data_reference description of MEMREF.  NEST is the outermost loop of the
 778    loop nest in that the reference should be analyzed.  */
 779
 780 struct data_reference *
 781 create_data_ref (struct loop *nest, tree memref, tree stmt, bool is_read)
 782 {
 783   struct data_reference *dr;
 784
 785   if (dump_file && (dump_flags & TDF_DETAILS))
 786     {
 787       fprintf (dump_file, "Creating dr for ");
 788       print_generic_expr (dump_file, memref, TDF_SLIM);
 789       fprintf (dump_file, "\n");
 790     }
 791
 792   dr = XCNEW (struct data_reference);
 793   DR_STMT (dr) = stmt;
 794   DR_REF (dr) = memref;
 795   DR_IS_READ (dr) = is_read;
 796
 797   dr_analyze_innermost (dr);
 798   dr_analyze_indices (dr, nest);
 799   dr_analyze_alias (dr);
 800
 801   if (dump_file && (dump_flags & TDF_DETAILS))
 802     {
 803       fprintf (dump_file, "\tbase_address: ");
 804       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
 805       fprintf (dump_file, "\n\toffset from base address: ");
 806       print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
 807       fprintf (dump_file, "\n\tconstant offset from base address: ");
 808       print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
 809       fprintf (dump_file, "\n\tstep: ");
 810       print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
 811       fprintf (dump_file, "\n\taligned to: ");
 812       print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
 813       fprintf (dump_file, "\n\tbase_object: ");
 814       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
 815       fprintf (dump_file, "\n\tsymbol tag: ");
 816       print_generic_expr (dump_file, DR_SYMBOL_TAG (dr), TDF_SLIM);
 817       fprintf (dump_file, "\n");
 818     }
 819
 820   return dr;
 821 }
 822
 823 /* Returns true if FNA == FNB.  */
 824
 825 static bool
 826 affine_function_equal_p (affine_fn fna, affine_fn fnb)
 827 {
 828   unsigned i, n = VEC_length (tree, fna);
 829
 830   if (n != VEC_length (tree, fnb))
 831     return false;
 832
 833   for (i = 0; i < n; i++)
 834     if (!operand_equal_p (VEC_index (tree, fna, i),
 835                           VEC_index (tree, fnb, i), 0))
 836       return false;
 837
 838   return true;
 839 }
 840
 841 /* If all the functions in CF are the same, returns one of them,
 842    otherwise returns NULL.  */
 843
 844 static affine_fn
 845 common_affine_function (conflict_function *cf)
 846 {
 847   unsigned i;
 848   affine_fn comm;
 849
 850   if (!CF_NONTRIVIAL_P (cf))
 851     return NULL;
 852
 853   comm = cf->fns[0];
 854
 855   for (i = 1; i < cf->n; i++)
 856     if (!affine_function_equal_p (comm, cf->fns[i]))
 857       return NULL;
 858
 859   return comm;
 860 }
 861
 862 /* Returns the base of the affine function FN.  */
 863
 864 static tree
 865 affine_function_base (affine_fn fn)
 866 {
 867   return VEC_index (tree, fn, 0);
 868 }
 869
 870 /* Returns true if FN is a constant.  */
 871
 872 static bool
 873 affine_function_constant_p (affine_fn fn)
 874 {
 875   unsigned i;
 876   tree coef;
 877
 878   for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
 879     if (!integer_zerop (coef))
 880       return false;
 881
 882   return true;
 883 }
 884
 885 /* Returns true if FN is the zero constant function.  */
 886
 887 static bool
 888 affine_function_zero_p (affine_fn fn)
 889 {
 890   return (integer_zerop (affine_function_base (fn))
 891           && affine_function_constant_p (fn));
 892 }
 893
 894 /* Applies operation OP on affine functions FNA and FNB, and returns the
 895    result.  */
 896
 897 static affine_fn
 898 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
 899 {
 900   unsigned i, n, m;
 901   affine_fn ret;
 902   tree coef;
 903
 904   if (VEC_length (tree, fnb) > VEC_length (tree, fna))
 905     {
 906       n = VEC_length (tree, fna);
 907       m = VEC_length (tree, fnb);
 908     }
 909   else
 910     {
 911       n = VEC_length (tree, fnb);
 912       m = VEC_length (tree, fna);
 913     }
 914
 915   ret = VEC_alloc (tree, heap, m);
 916   for (i = 0; i < n; i++)
 917     VEC_quick_push (tree, ret,
 918                     fold_build2 (op, integer_type_node,
 919                                  VEC_index (tree, fna, i),
 920                                  VEC_index (tree, fnb, i)));
 921
 922   for (; VEC_iterate (tree, fna, i, coef); i++)
 923     VEC_quick_push (tree, ret,
 924                     fold_build2 (op, integer_type_node,
 925                                  coef, integer_zero_node));
 926   for (; VEC_iterate (tree, fnb, i, coef); i++)
 927     VEC_quick_push (tree, ret,
 928                     fold_build2 (op, integer_type_node,
 929                                  integer_zero_node, coef));
 930
 931   return ret;
 932 }
 933
 934 /* Returns the sum of affine functions FNA and FNB.  */
 935
 936 static affine_fn
 937 affine_fn_plus (affine_fn fna, affine_fn fnb)
 938 {
 939   return affine_fn_op (PLUS_EXPR, fna, fnb);
 940 }
 941
 942 /* Returns the difference of affine functions FNA and FNB.  */
 943
 944 static affine_fn
 945 affine_fn_minus (affine_fn fna, affine_fn fnb)
 946 {
 947   return affine_fn_op (MINUS_EXPR, fna, fnb);
 948 }
 949
 950 /* Frees affine function FN.  */
 951
 952 static void
 953 affine_fn_free (affine_fn fn)
 954 {
 955   VEC_free (tree, heap, fn);
 956 }
 957
 958 /* Determine for each subscript in the data dependence relation DDR
 959    the distance.  */
 960
 961 static void
 962 compute_subscript_distance (struct data_dependence_relation *ddr)
 963 {
 964   conflict_function *cf_a, *cf_b;
 965   affine_fn fn_a, fn_b, diff;
 966
 967   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 968     {
 969       unsigned int i;
 970
 971       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 972         {
 973           struct subscript *subscript;
 974
 975           subscript = DDR_SUBSCRIPT (ddr, i);
 976           cf_a = SUB_CONFLICTS_IN_A (subscript);
 977           cf_b = SUB_CONFLICTS_IN_B (subscript);
 978
 979           fn_a = common_affine_function (cf_a);
 980           fn_b = common_affine_function (cf_b);
 981           if (!fn_a || !fn_b)
 982             {
 983               SUB_DISTANCE (subscript) = chrec_dont_know;
 984               return;
 985             }
 986           diff = affine_fn_minus (fn_a, fn_b);
 987
 988           if (affine_function_constant_p (diff))
 989             SUB_DISTANCE (subscript) = affine_function_base (diff);
 990           else
 991             SUB_DISTANCE (subscript) = chrec_dont_know;
 992
 993           affine_fn_free (diff);
 994         }
 995     }
 996 }
 997
 998 /* Returns the conflict function for "unknown".  */
 999
1000 static conflict_function *
1001 conflict_fn_not_known (void)
1002 {
1003   conflict_function *fn = XCNEW (conflict_function);
1004   fn->n = NOT_KNOWN;
1005
1006   return fn;
1007 }
1008
1009 /* Returns the conflict function for "independent".  */
1010
1011 static conflict_function *
1012 conflict_fn_no_dependence (void)
1013 {
1014   conflict_function *fn = XCNEW (conflict_function);
1015   fn->n = NO_DEPENDENCE;
1016
1017   return fn;
1018 }
1019
1020 /* Returns true if the address of OBJ is invariant in LOOP.  */
1021
1022 static bool
1023 object_address_invariant_in_loop_p (struct loop *loop, tree obj)
1024 {
1025   while (handled_component_p (obj))
1026     {
1027       if (TREE_CODE (obj) == ARRAY_REF)
1028         {
1029           /* Index of the ARRAY_REF was zeroed in analyze_indices, thus we only
1030              need to check the stride and the lower bound of the reference.  */
1031           if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1032                                                       loop->num)
1033               || chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 3),
1034                                                          loop->num))
1035             return false;
1036         }
1037       else if (TREE_CODE (obj) == COMPONENT_REF)
1038         {
1039           if (chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 2),
1040                                                       loop->num))
1041             return false;
1042         }
1043       obj = TREE_OPERAND (obj, 0);
1044     }
1045
1046   if (!INDIRECT_REF_P (obj))
1047     return true;
1048
1049   return !chrec_contains_symbols_defined_in_loop (TREE_OPERAND (obj, 0),
1050                                                   loop->num);
1051 }
1052
1053 /* Returns true if A and B are accesses to different objects, or to different
1054    fields of the same object.  */
1055
1056 static bool
1057 disjoint_objects_p (tree a, tree b)
1058 {
1059   tree base_a, base_b;
1060   VEC (tree, heap) *comp_a = NULL, *comp_b = NULL;
1061   bool ret;
1062
1063   base_a = get_base_address (a);
1064   base_b = get_base_address (b);
1065
1066   if (DECL_P (base_a)
1067       && DECL_P (base_b)
1068       && base_a != base_b)
1069     return true;
1070
1071   if (!operand_equal_p (base_a, base_b, 0))
1072     return false;
1073
1074   /* Compare the component references of A and B.  We must start from the inner
1075      ones, so record them to the vector first.  */
1076   while (handled_component_p (a))
1077     {
1078       VEC_safe_push (tree, heap, comp_a, a);
1079       a = TREE_OPERAND (a, 0);
1080     }
1081   while (handled_component_p (b))
1082     {
1083       VEC_safe_push (tree, heap, comp_b, b);
1084       b = TREE_OPERAND (b, 0);
1085     }
1086
1087   ret = false;
1088   while (1)
1089     {
1090       if (VEC_length (tree, comp_a) == 0
1091           || VEC_length (tree, comp_b) == 0)
1092         break;
1093
1094       a = VEC_pop (tree, comp_a);
1095       b = VEC_pop (tree, comp_b);
1096
1097       /* Real and imaginary part of a variable do not alias.  */
1098       if ((TREE_CODE (a) == REALPART_EXPR
1099            && TREE_CODE (b) == IMAGPART_EXPR)
1100           || (TREE_CODE (a) == IMAGPART_EXPR
1101               && TREE_CODE (b) == REALPART_EXPR))
1102         {
1103           ret = true;
1104           break;
1105         }
1106
1107       if (TREE_CODE (a) != TREE_CODE (b))
1108         break;
1109
1110       /* Nothing to do for ARRAY_REFs, as the indices of array_refs in
1111          DR_BASE_OBJECT are always zero.  */
1112       if (TREE_CODE (a) == ARRAY_REF)
1113         continue;
1114       else if (TREE_CODE (a) == COMPONENT_REF)
1115         {
1116           if (operand_equal_p (TREE_OPERAND (a, 1), TREE_OPERAND (b, 1), 0))
1117             continue;
1118
1119           /* Different fields of unions may overlap.  */
1120           base_a = TREE_OPERAND (a, 0);
1121           if (TREE_CODE (TREE_TYPE (base_a)) == UNION_TYPE)
1122             break;
1123
1124           /* Different fields of structures cannot.  */
1125           ret = true;
1126           break;
1127         }
1128       else
1129         break;
1130     }
1131
1132   VEC_free (tree, heap, comp_a);
1133   VEC_free (tree, heap, comp_b);
1134
1135   return ret;
1136 }
1137
1138 /* Returns false if we can prove that data references A and B do not alias,
1139    true otherwise.  */
1140
1141 static bool
1142 dr_may_alias_p (struct data_reference *a, struct data_reference *b)
1143 {
1144   tree addr_a = DR_BASE_ADDRESS (a);
1145   tree addr_b = DR_BASE_ADDRESS (b);
1146   tree type_a, type_b;
1147   tree decl_a = NULL_TREE, decl_b = NULL_TREE;
1148
1149   /* If the sets of virtual operands are disjoint, the memory references do not
1150      alias.  */
1151   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
1152     return false;
1153
1154   /* If the accessed objects are disjoint, the memory references do not
1155      alias.  */
1156   if (disjoint_objects_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b)))
1157     return false;
1158
1159   if (!addr_a || !addr_b)
1160     return true;
1161
1162   /* If the references are based on different static objects, they cannot alias
1163      (PTA should be able to disambiguate such accesses, but often it fails to,
1164      since currently we cannot distinguish between pointer and offset in pointer
1165      arithmetics).  */
1166   if (TREE_CODE (addr_a) == ADDR_EXPR
1167       && TREE_CODE (addr_b) == ADDR_EXPR)
1168     return TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0);
1169
1170   /* An instruction writing through a restricted pointer is "independent" of any
1171      instruction reading or writing through a different restricted pointer,
1172      in the same block/scope.  */
1173
1174   type_a = TREE_TYPE (addr_a);
1175   type_b = TREE_TYPE (addr_b);
1176   gcc_assert (POINTER_TYPE_P (type_a) && POINTER_TYPE_P (type_b));
1177
1178   if (TREE_CODE (addr_a) == SSA_NAME)
1179     decl_a = SSA_NAME_VAR (addr_a);
1180   if (TREE_CODE (addr_b) == SSA_NAME)
1181     decl_b = SSA_NAME_VAR (addr_b);
1182
1183   if (TYPE_RESTRICT (type_a) && TYPE_RESTRICT (type_b)
1184       && (!DR_IS_READ (a) || !DR_IS_READ (b))
1185       && decl_a && DECL_P (decl_a)
1186       && decl_b && DECL_P (decl_b)
1187       && decl_a != decl_b
1188       && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
1189       && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
1190     return false;
1191
1192   return true;
1193 }
1194
1195 /* Initialize a data dependence relation between data accesses A and
1196    B.  NB_LOOPS is the number of loops surrounding the references: the
1197    size of the classic distance/direction vectors.  */
1198
1199 static struct data_dependence_relation *
1200 initialize_data_dependence_relation (struct data_reference *a,
1201                                      struct data_reference *b,
1202                                      VEC (loop_p, heap) *loop_nest)
1203 {
1204   struct data_dependence_relation *res;
1205   unsigned int i;
1206
1207   res = XNEW (struct data_dependence_relation);
1208   DDR_A (res) = a;
1209   DDR_B (res) = b;
1210   DDR_LOOP_NEST (res) = NULL;
1211
1212   if (a == NULL || b == NULL)
1213     {
1214       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1215       return res;
1216     }
1217
1218   /* If the data references do not alias, then they are independent.  */
1219   if (!dr_may_alias_p (a, b))
1220     {
1221       DDR_ARE_DEPENDENT (res) = chrec_known;
1222       return res;
1223     }
1224
1225   /* If the references do not access the same object, we do not know
1226      whether they alias or not.  */
1227   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1228     {
1229       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1230       return res;
1231     }
1232
1233   /* If the base of the object is not invariant in the loop nest, we cannot
1234      analyze it.  TODO -- in fact, it would suffice to record that there may
1235      be arbitrary dependences in the loops where the base object varies.  */
1236   if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1237                                            DR_BASE_OBJECT (a)))
1238     {
1239       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1240       return res;
1241     }
1242
1243   gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1244
1245   DDR_AFFINE_P (res) = true;
1246   DDR_ARE_DEPENDENT (res) = NULL_TREE;
1247   DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1248   DDR_LOOP_NEST (res) = loop_nest;
1249   DDR_INNER_LOOP (res) = 0;
1250   DDR_DIR_VECTS (res) = NULL;
1251   DDR_DIST_VECTS (res) = NULL;
1252
1253   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1254     {
1255       struct subscript *subscript;
1256
1257       subscript = XNEW (struct subscript);
1258       SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1259       SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1260       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1261       SUB_DISTANCE (subscript) = chrec_dont_know;
1262       VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1263     }
1264
1265   return res;
1266 }
1267
1268 /* Frees memory used by the conflict function F.  */
1269
1270 static void
1271 free_conflict_function (conflict_function *f)
1272 {
1273   unsigned i;
1274
1275   if (CF_NONTRIVIAL_P (f))
1276     {
1277       for (i = 0; i < f->n; i++)
1278         affine_fn_free (f->fns[i]);
1279     }
1280   free (f);
1281 }
1282
1283 /* Frees memory used by SUBSCRIPTS.  */
1284
1285 static void
1286 free_subscripts (VEC (subscript_p, heap) *subscripts)
1287 {
1288   unsigned i;
1289   subscript_p s;
1290
1291   for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1292     {
1293       free_conflict_function (s->conflicting_iterations_in_a);
1294       free_conflict_function (s->conflicting_iterations_in_b);
1295     }
1296   VEC_free (subscript_p, heap, subscripts);
1297 }
1298
1299 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1300    description.  */
1301
1302 static inline void
1303 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1304                         tree chrec)
1305 {
1306   if (dump_file && (dump_flags & TDF_DETAILS))
1307     {
1308       fprintf (dump_file, "(dependence classified: ");
1309       print_generic_expr (dump_file, chrec, 0);
1310       fprintf (dump_file, ")\n");
1311     }
1312
1313   DDR_ARE_DEPENDENT (ddr) = chrec;
1314   free_subscripts (DDR_SUBSCRIPTS (ddr));
1315 }
1316
1317 /* The dependence relation DDR cannot be represented by a distance
1318    vector.  */
1319
1320 static inline void
1321 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1322 {
1323   if (dump_file && (dump_flags & TDF_DETAILS))
1324     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1325
1326   DDR_AFFINE_P (ddr) = false;
1327 }
1328
1329 \f
1330
1331 /* This section contains the classic Banerjee tests.  */
1332
1333 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1334    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
1335
1336 static inline bool
1337 ziv_subscript_p (tree chrec_a,
1338                  tree chrec_b)
1339 {
1340   return (evolution_function_is_constant_p (chrec_a)
1341           && evolution_function_is_constant_p (chrec_b));
1342 }
1343
1344 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1345    variable, i.e., if the SIV (Single Index Variable) test is true.  */
1346
1347 static bool
1348 siv_subscript_p (tree chrec_a,
1349                  tree chrec_b)
1350 {
1351   if ((evolution_function_is_constant_p (chrec_a)
1352        && evolution_function_is_univariate_p (chrec_b))
1353       || (evolution_function_is_constant_p (chrec_b)
1354           && evolution_function_is_univariate_p (chrec_a)))
1355     return true;
1356
1357   if (evolution_function_is_univariate_p (chrec_a)
1358       && evolution_function_is_univariate_p (chrec_b))
1359     {
1360       switch (TREE_CODE (chrec_a))
1361         {
1362         case POLYNOMIAL_CHREC:
1363           switch (TREE_CODE (chrec_b))
1364             {
1365             case POLYNOMIAL_CHREC:
1366               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1367                 return false;
1368
1369             default:
1370               return true;
1371             }
1372
1373         default:
1374           return true;
1375         }
1376     }
1377
1378   return false;
1379 }
1380
1381 /* Creates a conflict function with N dimensions.  The affine functions
1382    in each dimension follow.  */
1383
1384 static conflict_function *
1385 conflict_fn (unsigned n, ...)
1386 {
1387   unsigned i;
1388   conflict_function *ret = XCNEW (conflict_function);
1389   va_list ap;
1390
1391   gcc_assert (0 < n && n <= MAX_DIM);
1392   va_start(ap, n);
1393
1394   ret->n = n;
1395   for (i = 0; i < n; i++)
1396     ret->fns[i] = va_arg (ap, affine_fn);
1397   va_end(ap);
1398
1399   return ret;
1400 }
1401
1402 /* Returns constant affine function with value CST.  */
1403
1404 static affine_fn
1405 affine_fn_cst (tree cst)
1406 {
1407   affine_fn fn = VEC_alloc (tree, heap, 1);
1408   VEC_quick_push (tree, fn, cst);
1409   return fn;
1410 }
1411
1412 /* Returns affine function with single variable, CST + COEF * x_DIM.  */
1413
1414 static affine_fn
1415 affine_fn_univar (tree cst, unsigned dim, tree coef)
1416 {
1417   affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1418   unsigned i;
1419
1420   gcc_assert (dim > 0);
1421   VEC_quick_push (tree, fn, cst);
1422   for (i = 1; i < dim; i++)
1423     VEC_quick_push (tree, fn, integer_zero_node);
1424   VEC_quick_push (tree, fn, coef);
1425   return fn;
1426 }
1427
1428 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
1429    *OVERLAPS_B are initialized to the functions that describe the
1430    relation between the elements accessed twice by CHREC_A and
1431    CHREC_B.  For k >= 0, the following property is verified:
1432
1433    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1434
1435 static void
1436 analyze_ziv_subscript (tree chrec_a,
1437                        tree chrec_b,
1438                        conflict_function **overlaps_a,
1439                        conflict_function **overlaps_b,
1440                        tree *last_conflicts)
1441 {
1442   tree difference;
1443   dependence_stats.num_ziv++;
1444
1445   if (dump_file && (dump_flags & TDF_DETAILS))
1446     fprintf (dump_file, "(analyze_ziv_subscript \n");
1447
1448   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1449   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1450   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1451
1452   switch (TREE_CODE (difference))
1453     {
1454     case INTEGER_CST:
1455       if (integer_zerop (difference))
1456         {
1457           /* The difference is equal to zero: the accessed index
1458              overlaps for each iteration in the loop.  */
1459           *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1460           *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1461           *last_conflicts = chrec_dont_know;
1462           dependence_stats.num_ziv_dependent++;
1463         }
1464       else
1465         {
1466           /* The accesses do not overlap.  */
1467           *overlaps_a = conflict_fn_no_dependence ();
1468           *overlaps_b = conflict_fn_no_dependence ();
1469           *last_conflicts = integer_zero_node;
1470           dependence_stats.num_ziv_independent++;
1471         }
1472       break;
1473
1474     default:
1475       /* We're not sure whether the indexes overlap.  For the moment,
1476          conservatively answer "don't know".  */
1477       if (dump_file && (dump_flags & TDF_DETAILS))
1478         fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1479
1480       *overlaps_a = conflict_fn_not_known ();
1481       *overlaps_b = conflict_fn_not_known ();
1482       *last_conflicts = chrec_dont_know;
1483       dependence_stats.num_ziv_unimplemented++;
1484       break;
1485     }
1486
1487   if (dump_file && (dump_flags & TDF_DETAILS))
1488     fprintf (dump_file, ")\n");
1489 }
1490
1491 /* Sets NIT to the estimated number of executions of the statements in
1492    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
1493    large as the number of iterations.  If we have no reliable estimate,
1494    the function returns false, otherwise returns true.  */
1495
1496 bool
1497 estimated_loop_iterations (struct loop *loop, bool conservative,
1498                            double_int *nit)
1499 {
1500   estimate_numbers_of_iterations_loop (loop);
1501   if (conservative)
1502     {
1503       if (!loop->any_upper_bound)
1504         return false;
1505
1506       *nit = loop->nb_iterations_upper_bound;
1507     }
1508   else
1509     {
1510       if (!loop->any_estimate)
1511         return false;
1512
1513       *nit = loop->nb_iterations_estimate;
1514     }
1515
1516   return true;
1517 }
1518
1519 /* Similar to estimated_loop_iterations, but returns the estimate only
1520    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
1521    on the number of iterations of LOOP could not be derived, returns -1.  */
1522
1523 HOST_WIDE_INT
1524 estimated_loop_iterations_int (struct loop *loop, bool conservative)
1525 {
1526   double_int nit;
1527   HOST_WIDE_INT hwi_nit;
1528
1529   if (!estimated_loop_iterations (loop, conservative, &nit))
1530     return -1;
1531
1532   if (!double_int_fits_in_shwi_p (nit))
1533     return -1;
1534   hwi_nit = double_int_to_shwi (nit);
1535
1536   return hwi_nit < 0 ? -1 : hwi_nit;
1537 }
1538
1539 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1540    and only if it fits to the int type.  If this is not the case, or the
1541    estimate on the number of iterations of LOOP could not be derived, returns
1542    chrec_dont_know.  */
1543
1544 static tree
1545 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1546 {
1547   double_int nit;
1548   tree type;
1549
1550   if (!estimated_loop_iterations (loop, conservative, &nit))
1551     return chrec_dont_know;
1552
1553   type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1554   if (!double_int_fits_to_tree_p (type, nit))
1555     return chrec_dont_know;
1556
1557   return double_int_to_tree (type, nit);
1558 }
1559
1560 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1561    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
1562    *OVERLAPS_B are initialized to the functions that describe the
1563    relation between the elements accessed twice by CHREC_A and
1564    CHREC_B.  For k >= 0, the following property is verified:
1565
1566    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1567
1568 static void
1569 analyze_siv_subscript_cst_affine (tree chrec_a,
1570                                   tree chrec_b,
1571                                   conflict_function **overlaps_a,
1572                                   conflict_function **overlaps_b,
1573                                   tree *last_conflicts)
1574 {
1575   bool value0, value1, value2;
1576   tree difference, tmp;
1577
1578   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1579   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1580   difference = chrec_fold_minus
1581     (integer_type_node, initial_condition (chrec_b), chrec_a);
1582
1583   if (!chrec_is_positive (initial_condition (difference), &value0))
1584     {
1585       if (dump_file && (dump_flags & TDF_DETAILS))
1586         fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1587
1588       dependence_stats.num_siv_unimplemented++;
1589       *overlaps_a = conflict_fn_not_known ();
1590       *overlaps_b = conflict_fn_not_known ();
1591       *last_conflicts = chrec_dont_know;
1592       return;
1593     }
1594   else
1595     {
1596       if (value0 == false)
1597         {
1598           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1599             {
1600               if (dump_file && (dump_flags & TDF_DETAILS))
1601                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1602
1603               *overlaps_a = conflict_fn_not_known ();
1604               *overlaps_b = conflict_fn_not_known ();
1605               *last_conflicts = chrec_dont_know;
1606               dependence_stats.num_siv_unimplemented++;
1607               return;
1608             }
1609           else
1610             {
1611               if (value1 == true)
1612                 {
1613                   /* Example:
1614                      chrec_a = 12
1615                      chrec_b = {10, +, 1}
1616                   */
1617
1618                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1619                     {
1620                       HOST_WIDE_INT numiter;
1621                       struct loop *loop = get_chrec_loop (chrec_b);
1622
1623                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1624                       tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
1625                                          fold_build1 (ABS_EXPR,
1626                                                       integer_type_node,
1627                                                       difference),
1628                                          CHREC_RIGHT (chrec_b));
1629                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1630                       *last_conflicts = integer_one_node;
1631
1632
1633                       /* Perform weak-zero siv test to see if overlap is
1634                          outside the loop bounds.  */
1635                       numiter = estimated_loop_iterations_int (loop, false);
1636
1637                       if (numiter >= 0
1638                           && compare_tree_int (tmp, numiter) > 0)
1639                         {
1640                           free_conflict_function (*overlaps_a);
1641                           free_conflict_function (*overlaps_b);
1642                           *overlaps_a = conflict_fn_no_dependence ();
1643                           *overlaps_b = conflict_fn_no_dependence ();
1644                           *last_conflicts = integer_zero_node;
1645                           dependence_stats.num_siv_independent++;
1646                           return;
1647                         }
1648                       dependence_stats.num_siv_dependent++;
1649                       return;
1650                     }
1651
1652                   /* When the step does not divide the difference, there are
1653                      no overlaps.  */
1654                   else
1655                     {
1656                       *overlaps_a = conflict_fn_no_dependence ();
1657                       *overlaps_b = conflict_fn_no_dependence ();
1658                       *last_conflicts = integer_zero_node;
1659                       dependence_stats.num_siv_independent++;
1660                       return;
1661                     }
1662                 }
1663
1664               else
1665                 {
1666                   /* Example:
1667                      chrec_a = 12
1668                      chrec_b = {10, +, -1}
1669
1670                      In this case, chrec_a will not overlap with chrec_b.  */
1671                   *overlaps_a = conflict_fn_no_dependence ();
1672                   *overlaps_b = conflict_fn_no_dependence ();
1673                   *last_conflicts = integer_zero_node;
1674                   dependence_stats.num_siv_independent++;
1675                   return;
1676                 }
1677             }
1678         }
1679       else
1680         {
1681           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1682             {
1683               if (dump_file && (dump_flags & TDF_DETAILS))
1684                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1685
1686               *overlaps_a = conflict_fn_not_known ();
1687               *overlaps_b = conflict_fn_not_known ();
1688               *last_conflicts = chrec_dont_know;
1689               dependence_stats.num_siv_unimplemented++;
1690               return;
1691             }
1692           else
1693             {
1694               if (value2 == false)
1695                 {
1696                   /* Example:
1697                      chrec_a = 3
1698                      chrec_b = {10, +, -1}
1699                   */
1700                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1701                     {
1702                       HOST_WIDE_INT numiter;
1703                       struct loop *loop = get_chrec_loop (chrec_b);
1704
1705                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1706                       tmp = fold_build2 (EXACT_DIV_EXPR,
1707                                          integer_type_node, difference,
1708                                          CHREC_RIGHT (chrec_b));
1709                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1710                       *last_conflicts = integer_one_node;
1711
1712                       /* Perform weak-zero siv test to see if overlap is
1713                          outside the loop bounds.  */
1714                       numiter = estimated_loop_iterations_int (loop, false);
1715
1716                       if (numiter >= 0
1717                           && compare_tree_int (tmp, numiter) > 0)
1718                         {
1719                           free_conflict_function (*overlaps_a);
1720                           free_conflict_function (*overlaps_b);
1721                           *overlaps_a = conflict_fn_no_dependence ();
1722                           *overlaps_b = conflict_fn_no_dependence ();
1723                           *last_conflicts = integer_zero_node;
1724                           dependence_stats.num_siv_independent++;
1725                           return;
1726                         }
1727                       dependence_stats.num_siv_dependent++;
1728                       return;
1729                     }
1730
1731                   /* When the step does not divide the difference, there
1732                      are no overlaps.  */
1733                   else
1734                     {
1735                       *overlaps_a = conflict_fn_no_dependence ();
1736                       *overlaps_b = conflict_fn_no_dependence ();
1737                       *last_conflicts = integer_zero_node;
1738                       dependence_stats.num_siv_independent++;
1739                       return;
1740                     }
1741                 }
1742               else
1743                 {
1744                   /* Example:
1745                      chrec_a = 3
1746                      chrec_b = {4, +, 1}
1747
1748                      In this case, chrec_a will not overlap with chrec_b.  */
1749                   *overlaps_a = conflict_fn_no_dependence ();
1750                   *overlaps_b = conflict_fn_no_dependence ();
1751                   *last_conflicts = integer_zero_node;
1752                   dependence_stats.num_siv_independent++;
1753                   return;
1754                 }
1755             }
1756         }
1757     }
1758 }
1759
1760 /* Helper recursive function for initializing the matrix A.  Returns
1761    the initial value of CHREC.  */
1762
1763 static int
1764 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1765 {
1766   gcc_assert (chrec);
1767
1768   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1769     return int_cst_value (chrec);
1770
1771   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1772   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1773 }
1774
1775 #define FLOOR_DIV(x,y) ((x) / (y))
1776
1777 /* Solves the special case of the Diophantine equation:
1778    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1779
1780    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
1781    number of iterations that loops X and Y run.  The overlaps will be
1782    constructed as evolutions in dimension DIM.  */
1783
1784 static void
1785 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1786                                          affine_fn *overlaps_a,
1787                                          affine_fn *overlaps_b,
1788                                          tree *last_conflicts, int dim)
1789 {
1790   if (((step_a > 0 && step_b > 0)
1791        || (step_a < 0 && step_b < 0)))
1792     {
1793       int step_overlaps_a, step_overlaps_b;
1794       int gcd_steps_a_b, last_conflict, tau2;
1795
1796       gcd_steps_a_b = gcd (step_a, step_b);
1797       step_overlaps_a = step_b / gcd_steps_a_b;
1798       step_overlaps_b = step_a / gcd_steps_a_b;
1799
1800       tau2 = FLOOR_DIV (niter, step_overlaps_a);
1801       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1802       last_conflict = tau2;
1803
1804       *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1805                                       build_int_cst (NULL_TREE,
1806                                                      step_overlaps_a));
1807       *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1808                                       build_int_cst (NULL_TREE,
1809                                                      step_overlaps_b));
1810       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1811     }
1812
1813   else
1814     {
1815       *overlaps_a = affine_fn_cst (integer_zero_node);
1816       *overlaps_b = affine_fn_cst (integer_zero_node);
1817       *last_conflicts = integer_zero_node;
1818     }
1819 }
1820
1821 /* Solves the special case of a Diophantine equation where CHREC_A is
1822    an affine bivariate function, and CHREC_B is an affine univariate
1823    function.  For example,
1824
1825    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1826
1827    has the following overlapping functions:
1828
1829    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1830    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1831    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1832
1833    FORNOW: This is a specialized implementation for a case occurring in
1834    a common benchmark.  Implement the general algorithm.  */
1835
1836 static void
1837 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1838                                       conflict_function **overlaps_a,
1839                                       conflict_function **overlaps_b,
1840                                       tree *last_conflicts)
1841 {
1842   bool xz_p, yz_p, xyz_p;
1843   int step_x, step_y, step_z;
1844   HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1845   affine_fn overlaps_a_xz, overlaps_b_xz;
1846   affine_fn overlaps_a_yz, overlaps_b_yz;
1847   affine_fn overlaps_a_xyz, overlaps_b_xyz;
1848   affine_fn ova1, ova2, ovb;
1849   tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1850
1851   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1852   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1853   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1854
1855   niter_x =
1856     estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
1857                                    false);
1858   niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
1859   niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
1860
1861   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1862     {
1863       if (dump_file && (dump_flags & TDF_DETAILS))
1864         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1865
1866       *overlaps_a = conflict_fn_not_known ();
1867       *overlaps_b = conflict_fn_not_known ();
1868       *last_conflicts = chrec_dont_know;
1869       return;
1870     }
1871
1872   niter = MIN (niter_x, niter_z);
1873   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1874                                            &overlaps_a_xz,
1875                                            &overlaps_b_xz,
1876                                            &last_conflicts_xz, 1);
1877   niter = MIN (niter_y, niter_z);
1878   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1879                                            &overlaps_a_yz,
1880                                            &overlaps_b_yz,
1881                                            &last_conflicts_yz, 2);
1882   niter = MIN (niter_x, niter_z);
1883   niter = MIN (niter_y, niter);
1884   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1885                                            &overlaps_a_xyz,
1886                                            &overlaps_b_xyz,
1887                                            &last_conflicts_xyz, 3);
1888
1889   xz_p = !integer_zerop (last_conflicts_xz);
1890   yz_p = !integer_zerop (last_conflicts_yz);
1891   xyz_p = !integer_zerop (last_conflicts_xyz);
1892
1893   if (xz_p || yz_p || xyz_p)
1894     {
1895       ova1 = affine_fn_cst (integer_zero_node);
1896       ova2 = affine_fn_cst (integer_zero_node);
1897       ovb = affine_fn_cst (integer_zero_node);
1898       if (xz_p)
1899         {
1900           affine_fn t0 = ova1;
1901           affine_fn t2 = ovb;
1902
1903           ova1 = affine_fn_plus (ova1, overlaps_a_xz);
1904           ovb = affine_fn_plus (ovb, overlaps_b_xz);
1905           affine_fn_free (t0);
1906           affine_fn_free (t2);
1907           *last_conflicts = last_conflicts_xz;
1908         }
1909       if (yz_p)
1910         {
1911           affine_fn t0 = ova2;
1912           affine_fn t2 = ovb;
1913
1914           ova2 = affine_fn_plus (ova2, overlaps_a_yz);
1915           ovb = affine_fn_plus (ovb, overlaps_b_yz);
1916           affine_fn_free (t0);
1917           affine_fn_free (t2);
1918           *last_conflicts = last_conflicts_yz;
1919         }
1920       if (xyz_p)
1921         {
1922           affine_fn t0 = ova1;
1923           affine_fn t2 = ova2;
1924           affine_fn t4 = ovb;
1925
1926           ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
1927           ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
1928           ovb = affine_fn_plus (ovb, overlaps_b_xyz);
1929           affine_fn_free (t0);
1930           affine_fn_free (t2);
1931           affine_fn_free (t4);
1932           *last_conflicts = last_conflicts_xyz;
1933         }
1934       *overlaps_a = conflict_fn (2, ova1, ova2);
1935       *overlaps_b = conflict_fn (1, ovb);
1936     }
1937   else
1938     {
1939       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1940       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1941       *last_conflicts = integer_zero_node;
1942     }
1943
1944   affine_fn_free (overlaps_a_xz);
1945   affine_fn_free (overlaps_b_xz);
1946   affine_fn_free (overlaps_a_yz);
1947   affine_fn_free (overlaps_b_yz);
1948   affine_fn_free (overlaps_a_xyz);
1949   affine_fn_free (overlaps_b_xyz);
1950 }
1951
1952 /* Determines the overlapping elements due to accesses CHREC_A and
1953    CHREC_B, that are affine functions.  This function cannot handle
1954    symbolic evolution functions, ie. when initial conditions are
1955    parameters, because it uses lambda matrices of integers.  */
1956
1957 static void
1958 analyze_subscript_affine_affine (tree chrec_a,
1959                                  tree chrec_b,
1960                                  conflict_function **overlaps_a,
1961                                  conflict_function **overlaps_b,
1962                                  tree *last_conflicts)
1963 {
1964   unsigned nb_vars_a, nb_vars_b, dim;
1965   HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
1966   HOST_WIDE_INT tau1, tau2;
1967   lambda_matrix A, U, S;
1968
1969   if (eq_evolutions_p (chrec_a, chrec_b))
1970     {
1971       /* The accessed index overlaps for each iteration in the
1972          loop.  */
1973       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1974       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1975       *last_conflicts = chrec_dont_know;
1976       return;
1977     }
1978   if (dump_file && (dump_flags & TDF_DETAILS))
1979     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1980
1981   /* For determining the initial intersection, we have to solve a
1982      Diophantine equation.  This is the most time consuming part.
1983
1984      For answering to the question: "Is there a dependence?" we have
1985      to prove that there exists a solution to the Diophantine
1986      equation, and that the solution is in the iteration domain,
1987      i.e. the solution is positive or zero, and that the solution
1988      happens before the upper bound loop.nb_iterations.  Otherwise
1989      there is no dependence.  This function outputs a description of
1990      the iterations that hold the intersections.  */
1991
1992   nb_vars_a = nb_vars_in_chrec (chrec_a);
1993   nb_vars_b = nb_vars_in_chrec (chrec_b);
1994
1995   dim = nb_vars_a + nb_vars_b;
1996   U = lambda_matrix_new (dim, dim);
1997   A = lambda_matrix_new (dim, 1);
1998   S = lambda_matrix_new (dim, 1);
1999
2000   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2001   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2002   gamma = init_b - init_a;
2003
2004   /* Don't do all the hard work of solving the Diophantine equation
2005      when we already know the solution: for example,
2006      | {3, +, 1}_1
2007      | {3, +, 4}_2
2008      | gamma = 3 - 3 = 0.
2009      Then the first overlap occurs during the first iterations:
2010      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2011   */
2012   if (gamma == 0)
2013     {
2014       if (nb_vars_a == 1 && nb_vars_b == 1)
2015         {
2016           HOST_WIDE_INT step_a, step_b;
2017           HOST_WIDE_INT niter, niter_a, niter_b;
2018           affine_fn ova, ovb;
2019
2020           niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2021                                                    false);
2022           niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2023                                                    false);
2024           if (niter_a < 0 || niter_b < 0)
2025             {
2026               if (dump_file && (dump_flags & TDF_DETAILS))
2027                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2028               *overlaps_a = conflict_fn_not_known ();
2029               *overlaps_b = conflict_fn_not_known ();
2030               *last_conflicts = chrec_dont_know;
2031               goto end_analyze_subs_aa;
2032             }
2033
2034           niter = MIN (niter_a, niter_b);
2035
2036           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2037           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2038
2039           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2040                                                    &ova, &ovb,
2041                                                    last_conflicts, 1);
2042           *overlaps_a = conflict_fn (1, ova);
2043           *overlaps_b = conflict_fn (1, ovb);
2044         }
2045
2046       else if (nb_vars_a == 2 && nb_vars_b == 1)
2047         compute_overlap_steps_for_affine_1_2
2048           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2049
2050       else if (nb_vars_a == 1 && nb_vars_b == 2)
2051         compute_overlap_steps_for_affine_1_2
2052           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2053
2054       else
2055         {
2056           if (dump_file && (dump_flags & TDF_DETAILS))
2057             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2058           *overlaps_a = conflict_fn_not_known ();
2059           *overlaps_b = conflict_fn_not_known ();
2060           *last_conflicts = chrec_dont_know;
2061         }
2062       goto end_analyze_subs_aa;
2063     }
2064
2065   /* U.A = S */
2066   lambda_matrix_right_hermite (A, dim, 1, S, U);
2067
2068   if (S[0][0] < 0)
2069     {
2070       S[0][0] *= -1;
2071       lambda_matrix_row_negate (U, dim, 0);
2072     }
2073   gcd_alpha_beta = S[0][0];
2074
2075   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2076      but that is a quite strange case.  Instead of ICEing, answer
2077      don't know.  */
2078   if (gcd_alpha_beta == 0)
2079     {
2080       *overlaps_a = conflict_fn_not_known ();
2081       *overlaps_b = conflict_fn_not_known ();
2082       *last_conflicts = chrec_dont_know;
2083       goto end_analyze_subs_aa;
2084     }
2085
2086   /* The classic "gcd-test".  */
2087   if (!int_divides_p (gcd_alpha_beta, gamma))
2088     {
2089       /* The "gcd-test" has determined that there is no integer
2090          solution, i.e. there is no dependence.  */
2091       *overlaps_a = conflict_fn_no_dependence ();
2092       *overlaps_b = conflict_fn_no_dependence ();
2093       *last_conflicts = integer_zero_node;
2094     }
2095
2096   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2097   else if (nb_vars_a == 1 && nb_vars_b == 1)
2098     {
2099       /* Both functions should have the same evolution sign.  */
2100       if (((A[0][0] > 0 && -A[1][0] > 0)
2101            || (A[0][0] < 0 && -A[1][0] < 0)))
2102         {
2103           /* The solutions are given by:
2104              |
2105              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2106              |                           [u21 u22]    [y0]
2107
2108              For a given integer t.  Using the following variables,
2109
2110              | i0 = u11 * gamma / gcd_alpha_beta
2111              | j0 = u12 * gamma / gcd_alpha_beta
2112              | i1 = u21
2113              | j1 = u22
2114
2115              the solutions are:
2116
2117              | x0 = i0 + i1 * t,
2118              | y0 = j0 + j1 * t.  */
2119
2120           HOST_WIDE_INT i0, j0, i1, j1;
2121
2122           /* X0 and Y0 are the first iterations for which there is a
2123              dependence.  X0, Y0 are two solutions of the Diophantine
2124              equation: chrec_a (X0) = chrec_b (Y0).  */
2125           HOST_WIDE_INT x0, y0;
2126           HOST_WIDE_INT niter, niter_a, niter_b;
2127
2128           niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2129                                                    false);
2130           niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2131                                                    false);
2132
2133           if (niter_a < 0 || niter_b < 0)
2134             {
2135               if (dump_file && (dump_flags & TDF_DETAILS))
2136                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2137               *overlaps_a = conflict_fn_not_known ();
2138               *overlaps_b = conflict_fn_not_known ();
2139               *last_conflicts = chrec_dont_know;
2140               goto end_analyze_subs_aa;
2141             }
2142
2143           niter = MIN (niter_a, niter_b);
2144
2145           i0 = U[0][0] * gamma / gcd_alpha_beta;
2146           j0 = U[0][1] * gamma / gcd_alpha_beta;
2147           i1 = U[1][0];
2148           j1 = U[1][1];
2149
2150           if ((i1 == 0 && i0 < 0)
2151               || (j1 == 0 && j0 < 0))
2152             {
2153               /* There is no solution.
2154                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2155                  falls in here, but for the moment we don't look at the
2156                  upper bound of the iteration domain.  */
2157               *overlaps_a = conflict_fn_no_dependence ();
2158               *overlaps_b = conflict_fn_no_dependence ();
2159               *last_conflicts = integer_zero_node;
2160             }
2161
2162           else
2163             {
2164               if (i1 > 0)
2165                 {
2166                   tau1 = CEIL (-i0, i1);
2167                   tau2 = FLOOR_DIV (niter - i0, i1);
2168
2169                   if (j1 > 0)
2170                     {
2171                       int last_conflict, min_multiple;
2172                       tau1 = MAX (tau1, CEIL (-j0, j1));
2173                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2174
2175                       x0 = i1 * tau1 + i0;
2176                       y0 = j1 * tau1 + j0;
2177
2178                       /* At this point (x0, y0) is one of the
2179                          solutions to the Diophantine equation.  The
2180                          next step has to compute the smallest
2181                          positive solution: the first conflicts.  */
2182                       min_multiple = MIN (x0 / i1, y0 / j1);
2183                       x0 -= i1 * min_multiple;
2184                       y0 -= j1 * min_multiple;
2185
2186                       tau1 = (x0 - i0)/i1;
2187                       last_conflict = tau2 - tau1;
2188
2189                       /* If the overlap occurs outside of the bounds of the
2190                          loop, there is no dependence.  */
2191                       if (x0 > niter || y0  > niter)
2192                         {
2193                           *overlaps_a = conflict_fn_no_dependence ();
2194                           *overlaps_b = conflict_fn_no_dependence ();
2195                           *last_conflicts = integer_zero_node;
2196                         }
2197                       else
2198                         {
2199                           *overlaps_a
2200                             = conflict_fn (1,
2201                                 affine_fn_univar (build_int_cst (NULL_TREE, x0),
2202                                                   1,
2203                                                   build_int_cst (NULL_TREE, i1)));
2204                           *overlaps_b
2205                             = conflict_fn (1,
2206                                 affine_fn_univar (build_int_cst (NULL_TREE, y0),
2207                                                   1,
2208                                                   build_int_cst (NULL_TREE, j1)));
2209                           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2210                         }
2211                     }
2212                   else
2213                     {
2214                       /* FIXME: For the moment, the upper bound of the
2215                          iteration domain for j is not checked.  */
2216                       if (dump_file && (dump_flags & TDF_DETAILS))
2217                         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2218                       *overlaps_a = conflict_fn_not_known ();
2219                       *overlaps_b = conflict_fn_not_known ();
2220                       *last_conflicts = chrec_dont_know;
2221                     }
2222                 }
2223
2224               else
2225                 {
2226                   /* FIXME: For the moment, the upper bound of the
2227                      iteration domain for i is not checked.  */
2228                   if (dump_file && (dump_flags & TDF_DETAILS))
2229                     fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2230                   *overlaps_a = conflict_fn_not_known ();
2231                   *overlaps_b = conflict_fn_not_known ();
2232                   *last_conflicts = chrec_dont_know;
2233                 }
2234             }
2235         }
2236       else
2237         {
2238           if (dump_file && (dump_flags & TDF_DETAILS))
2239             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2240           *overlaps_a = conflict_fn_not_known ();
2241           *overlaps_b = conflict_fn_not_known ();
2242           *last_conflicts = chrec_dont_know;
2243         }
2244     }
2245
2246   else
2247     {
2248       if (dump_file && (dump_flags & TDF_DETAILS))
2249         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2250       *overlaps_a = conflict_fn_not_known ();
2251       *overlaps_b = conflict_fn_not_known ();
2252       *last_conflicts = chrec_dont_know;
2253     }
2254
2255 end_analyze_subs_aa:
2256   if (dump_file && (dump_flags & TDF_DETAILS))
2257     {
2258       fprintf (dump_file, "  (overlaps_a = ");
2259       dump_conflict_function (dump_file, *overlaps_a);
2260       fprintf (dump_file, ")\n  (overlaps_b = ");
2261       dump_conflict_function (dump_file, *overlaps_b);
2262       fprintf (dump_file, ")\n");
2263       fprintf (dump_file, ")\n");
2264     }
2265 }
2266
2267 /* Returns true when analyze_subscript_affine_affine can be used for
2268    determining the dependence relation between chrec_a and chrec_b,
2269    that contain symbols.  This function modifies chrec_a and chrec_b
2270    such that the analysis result is the same, and such that they don't
2271    contain symbols, and then can safely be passed to the analyzer.
2272
2273    Example: The analysis of the following tuples of evolutions produce
2274    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2275    vs. {0, +, 1}_1
2276
2277    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2278    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2279 */
2280
2281 static bool
2282 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2283 {
2284   tree diff, type, left_a, left_b, right_b;
2285
2286   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2287       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2288     /* FIXME: For the moment not handled.  Might be refined later.  */
2289     return false;
2290
2291   type = chrec_type (*chrec_a);
2292   left_a = CHREC_LEFT (*chrec_a);
2293   left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2294   diff = chrec_fold_minus (type, left_a, left_b);
2295
2296   if (!evolution_function_is_constant_p (diff))
2297     return false;
2298
2299   if (dump_file && (dump_flags & TDF_DETAILS))
2300     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2301
2302   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2303                                      diff, CHREC_RIGHT (*chrec_a));
2304   right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
2305   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2306                                      build_int_cst (type, 0),
2307                                      right_b);
2308   return true;
2309 }
2310
2311 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
2312    *OVERLAPS_B are initialized to the functions that describe the
2313    relation between the elements accessed twice by CHREC_A and
2314    CHREC_B.  For k >= 0, the following property is verified:
2315
2316    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2317
2318 static void
2319 analyze_siv_subscript (tree chrec_a,
2320                        tree chrec_b,
2321                        conflict_function **overlaps_a,
2322                        conflict_function **overlaps_b,
2323                        tree *last_conflicts)
2324 {
2325   dependence_stats.num_siv++;
2326
2327   if (dump_file && (dump_flags & TDF_DETAILS))
2328     fprintf (dump_file, "(analyze_siv_subscript \n");
2329
2330   if (evolution_function_is_constant_p (chrec_a)
2331       && evolution_function_is_affine_p (chrec_b))
2332     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2333                                       overlaps_a, overlaps_b, last_conflicts);
2334
2335   else if (evolution_function_is_affine_p (chrec_a)
2336            && evolution_function_is_constant_p (chrec_b))
2337     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2338                                       overlaps_b, overlaps_a, last_conflicts);
2339
2340   else if (evolution_function_is_affine_p (chrec_a)
2341            && evolution_function_is_affine_p (chrec_b))
2342     {
2343       if (!chrec_contains_symbols (chrec_a)
2344           && !chrec_contains_symbols (chrec_b))
2345         {
2346           analyze_subscript_affine_affine (chrec_a, chrec_b,
2347                                            overlaps_a, overlaps_b,
2348                                            last_conflicts);
2349
2350           if (CF_NOT_KNOWN_P (*overlaps_a)
2351               || CF_NOT_KNOWN_P (*overlaps_b))
2352             dependence_stats.num_siv_unimplemented++;
2353           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2354                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2355             dependence_stats.num_siv_independent++;
2356           else
2357             dependence_stats.num_siv_dependent++;
2358         }
2359       else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2360                                                         &chrec_b))
2361         {
2362           analyze_subscript_affine_affine (chrec_a, chrec_b,
2363                                            overlaps_a, overlaps_b,
2364                                            last_conflicts);
2365
2366           if (CF_NOT_KNOWN_P (*overlaps_a)
2367               || CF_NOT_KNOWN_P (*overlaps_b))
2368             dependence_stats.num_siv_unimplemented++;
2369           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2370                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2371             dependence_stats.num_siv_independent++;
2372           else
2373             dependence_stats.num_siv_dependent++;
2374         }
2375       else
2376         goto siv_subscript_dontknow;
2377     }
2378
2379   else
2380     {
2381     siv_subscript_dontknow:;
2382       if (dump_file && (dump_flags & TDF_DETAILS))
2383         fprintf (dump_file, "siv test failed: unimplemented.\n");
2384       *overlaps_a = conflict_fn_not_known ();
2385       *overlaps_b = conflict_fn_not_known ();
2386       *last_conflicts = chrec_dont_know;
2387       dependence_stats.num_siv_unimplemented++;
2388     }
2389
2390   if (dump_file && (dump_flags & TDF_DETAILS))
2391     fprintf (dump_file, ")\n");
2392 }
2393
2394 /* Returns false if we can prove that the greatest common divisor of the steps
2395    of CHREC does not divide CST, false otherwise.  */
2396
2397 static bool
2398 gcd_of_steps_may_divide_p (tree chrec, tree cst)
2399 {
2400   HOST_WIDE_INT cd = 0, val;
2401   tree step;
2402
2403   if (!host_integerp (cst, 0))
2404     return true;
2405   val = tree_low_cst (cst, 0);
2406
2407   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2408     {
2409       step = CHREC_RIGHT (chrec);
2410       if (!host_integerp (step, 0))
2411         return true;
2412       cd = gcd (cd, tree_low_cst (step, 0));
2413       chrec = CHREC_LEFT (chrec);
2414     }
2415
2416   return val % cd == 0;
2417 }
2418
2419 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2420    LOOP_NEST.  *OVERLAPS_A and *OVERLAPS_B are initialized to the
2421    functions that describe the relation between the elements accessed
2422    twice by CHREC_A and CHREC_B.  For k >= 0, the following property
2423    is verified:
2424
2425    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2426
2427 static void
2428 analyze_miv_subscript (tree chrec_a,
2429                        tree chrec_b,
2430                        conflict_function **overlaps_a,
2431                        conflict_function **overlaps_b,
2432                        tree *last_conflicts,
2433                        struct loop *loop_nest)
2434 {
2435   /* FIXME:  This is a MIV subscript, not yet handled.
2436      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2437      (A[i] vs. A[j]).
2438
2439      In the SIV test we had to solve a Diophantine equation with two
2440      variables.  In the MIV case we have to solve a Diophantine
2441      equation with 2*n variables (if the subscript uses n IVs).
2442   */
2443   tree difference;
2444   dependence_stats.num_miv++;
2445   if (dump_file && (dump_flags & TDF_DETAILS))
2446     fprintf (dump_file, "(analyze_miv_subscript \n");
2447
2448   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2449   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2450   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2451
2452   if (eq_evolutions_p (chrec_a, chrec_b))
2453     {
2454       /* Access functions are the same: all the elements are accessed
2455          in the same order.  */
2456       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2457       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2458       *last_conflicts = estimated_loop_iterations_tree
2459                                 (get_chrec_loop (chrec_a), true);
2460       dependence_stats.num_miv_dependent++;
2461     }
2462
2463   else if (evolution_function_is_constant_p (difference)
2464            /* For the moment, the following is verified:
2465               evolution_function_is_affine_multivariate_p (chrec_a,
2466               loop_nest->num) */
2467            && !gcd_of_steps_may_divide_p (chrec_a, difference))
2468     {
2469       /* testsuite/.../ssa-chrec-33.c
2470          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
2471
2472          The difference is 1, and all the evolution steps are multiples
2473          of 2, consequently there are no overlapping elements.  */
2474       *overlaps_a = conflict_fn_no_dependence ();
2475       *overlaps_b = conflict_fn_no_dependence ();
2476       *last_conflicts = integer_zero_node;
2477       dependence_stats.num_miv_independent++;
2478     }
2479
2480   else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2481            && !chrec_contains_symbols (chrec_a)
2482            && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2483            && !chrec_contains_symbols (chrec_b))
2484     {
2485       /* testsuite/.../ssa-chrec-35.c
2486          {0, +, 1}_2  vs.  {0, +, 1}_3
2487          the overlapping elements are respectively located at iterations:
2488          {0, +, 1}_x and {0, +, 1}_x,
2489          in other words, we have the equality:
2490          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2491
2492          Other examples:
2493          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2494          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2495
2496          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2497          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2498       */
2499       analyze_subscript_affine_affine (chrec_a, chrec_b,
2500                                        overlaps_a, overlaps_b, last_conflicts);
2501
2502       if (CF_NOT_KNOWN_P (*overlaps_a)
2503           || CF_NOT_KNOWN_P (*overlaps_b))
2504         dependence_stats.num_miv_unimplemented++;
2505       else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2506                || CF_NO_DEPENDENCE_P (*overlaps_b))
2507         dependence_stats.num_miv_independent++;
2508       else
2509         dependence_stats.num_miv_dependent++;
2510     }
2511
2512   else
2513     {
2514       /* When the analysis is too difficult, answer "don't know".  */
2515       if (dump_file && (dump_flags & TDF_DETAILS))
2516         fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2517
2518       *overlaps_a = conflict_fn_not_known ();
2519       *overlaps_b = conflict_fn_not_known ();
2520       *last_conflicts = chrec_dont_know;
2521       dependence_stats.num_miv_unimplemented++;
2522     }
2523
2524   if (dump_file && (dump_flags & TDF_DETAILS))
2525     fprintf (dump_file, ")\n");
2526 }
2527
2528 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2529    with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
2530    OVERLAP_ITERATIONS_B are initialized with two functions that
2531    describe the iterations that contain conflicting elements.
2532
2533    Remark: For an integer k >= 0, the following equality is true:
2534
2535    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2536 */
2537
2538 static void
2539 analyze_overlapping_iterations (tree chrec_a,
2540                                 tree chrec_b,
2541                                 conflict_function **overlap_iterations_a,
2542                                 conflict_function **overlap_iterations_b,
2543                                 tree *last_conflicts, struct loop *loop_nest)
2544 {
2545   unsigned int lnn = loop_nest->num;
2546
2547   dependence_stats.num_subscript_tests++;
2548
2549   if (dump_file && (dump_flags & TDF_DETAILS))
2550     {
2551       fprintf (dump_file, "(analyze_overlapping_iterations \n");
2552       fprintf (dump_file, "  (chrec_a = ");
2553       print_generic_expr (dump_file, chrec_a, 0);
2554       fprintf (dump_file, ")\n  (chrec_b = ");
2555       print_generic_expr (dump_file, chrec_b, 0);
2556       fprintf (dump_file, ")\n");
2557     }
2558
2559   if (chrec_a == NULL_TREE
2560       || chrec_b == NULL_TREE
2561       || chrec_contains_undetermined (chrec_a)
2562       || chrec_contains_undetermined (chrec_b))
2563     {
2564       dependence_stats.num_subscript_undetermined++;
2565
2566       *overlap_iterations_a = conflict_fn_not_known ();
2567       *overlap_iterations_b = conflict_fn_not_known ();
2568     }
2569
2570   /* If they are the same chrec, and are affine, they overlap
2571      on every iteration.  */
2572   else if (eq_evolutions_p (chrec_a, chrec_b)
2573            && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
2574     {
2575       dependence_stats.num_same_subscript_function++;
2576       *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2577       *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2578       *last_conflicts = chrec_dont_know;
2579     }
2580
2581   /* If they aren't the same, and aren't affine, we can't do anything
2582      yet. */
2583   else if ((chrec_contains_symbols (chrec_a)
2584             || chrec_contains_symbols (chrec_b))
2585            && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2586                || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2587     {
2588       dependence_stats.num_subscript_undetermined++;
2589       *overlap_iterations_a = conflict_fn_not_known ();
2590       *overlap_iterations_b = conflict_fn_not_known ();
2591     }
2592
2593   else if (ziv_subscript_p (chrec_a, chrec_b))
2594     analyze_ziv_subscript (chrec_a, chrec_b,
2595                            overlap_iterations_a, overlap_iterations_b,
2596                            last_conflicts);
2597
2598   else if (siv_subscript_p (chrec_a, chrec_b))
2599     analyze_siv_subscript (chrec_a, chrec_b,
2600                            overlap_iterations_a, overlap_iterations_b,
2601                            last_conflicts);
2602
2603   else
2604     analyze_miv_subscript (chrec_a, chrec_b,
2605                            overlap_iterations_a, overlap_iterations_b,
2606                            last_conflicts, loop_nest);
2607
2608   if (dump_file && (dump_flags & TDF_DETAILS))
2609     {
2610       fprintf (dump_file, "  (overlap_iterations_a = ");
2611       dump_conflict_function (dump_file, *overlap_iterations_a);
2612       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2613       dump_conflict_function (dump_file, *overlap_iterations_b);
2614       fprintf (dump_file, ")\n");
2615       fprintf (dump_file, ")\n");
2616     }
2617 }
2618
2619 /* Helper function for uniquely inserting distance vectors.  */
2620
2621 static void
2622 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2623 {
2624   unsigned i;
2625   lambda_vector v;
2626
2627   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2628     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2629       return;
2630
2631   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2632 }
2633
2634 /* Helper function for uniquely inserting direction vectors.  */
2635
2636 static void
2637 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2638 {
2639   unsigned i;
2640   lambda_vector v;
2641
2642   for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2643     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2644       return;
2645
2646   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2647 }
2648
2649 /* Add a distance of 1 on all the loops outer than INDEX.  If we
2650    haven't yet determined a distance for this outer loop, push a new
2651    distance vector composed of the previous distance, and a distance
2652    of 1 for this outer loop.  Example:
2653
2654    | loop_1
2655    |   loop_2
2656    |     A[10]
2657    |   endloop_2
2658    | endloop_1
2659
2660    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
2661    save (0, 1), then we have to save (1, 0).  */
2662
2663 static void
2664 add_outer_distances (struct data_dependence_relation *ddr,
2665                      lambda_vector dist_v, int index)
2666 {
2667   /* For each outer loop where init_v is not set, the accesses are
2668      in dependence of distance 1 in the loop.  */
2669   while (--index >= 0)
2670     {
2671       lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2672       lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2673       save_v[index] = 1;
2674       save_dist_v (ddr, save_v);
2675     }
2676 }
2677
2678 /* Return false when fail to represent the data dependence as a
2679    distance vector.  INIT_B is set to true when a component has been
2680    added to the distance vector DIST_V.  INDEX_CARRY is then set to
2681    the index in DIST_V that carries the dependence.  */
2682
2683 static bool
2684 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2685                              struct data_reference *ddr_a,
2686                              struct data_reference *ddr_b,
2687                              lambda_vector dist_v, bool *init_b,
2688                              int *index_carry)
2689 {
2690   unsigned i;
2691   lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2692
2693   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2694     {
2695       tree access_fn_a, access_fn_b;
2696       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2697
2698       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2699         {
2700           non_affine_dependence_relation (ddr);
2701           return false;
2702         }
2703
2704       access_fn_a = DR_ACCESS_FN (ddr_a, i);
2705       access_fn_b = DR_ACCESS_FN (ddr_b, i);
2706
2707       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2708           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2709         {
2710           int dist, index;
2711           int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2712                                             DDR_LOOP_NEST (ddr));
2713           int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2714                                             DDR_LOOP_NEST (ddr));
2715
2716           /* The dependence is carried by the outermost loop.  Example:
2717              | loop_1
2718              |   A[{4, +, 1}_1]
2719              |   loop_2
2720              |     A[{5, +, 1}_2]
2721              |   endloop_2
2722              | endloop_1
2723              In this case, the dependence is carried by loop_1.  */
2724           index = index_a < index_b ? index_a : index_b;
2725           *index_carry = MIN (index, *index_carry);
2726
2727           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2728             {
2729               non_affine_dependence_relation (ddr);
2730               return false;
2731             }
2732
2733           dist = int_cst_value (SUB_DISTANCE (subscript));
2734
2735           /* This is the subscript coupling test.  If we have already
2736              recorded a distance for this loop (a distance coming from
2737              another subscript), it should be the same.  For example,
2738              in the following code, there is no dependence:
2739
2740              | loop i = 0, N, 1
2741              |   T[i+1][i] = ...
2742              |   ... = T[i][i]
2743              | endloop
2744           */
2745           if (init_v[index] != 0 && dist_v[index] != dist)
2746             {
2747               finalize_ddr_dependent (ddr, chrec_known);
2748               return false;
2749             }
2750
2751           dist_v[index] = dist;
2752           init_v[index] = 1;
2753           *init_b = true;
2754         }
2755       else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2756         {
2757           /* This can be for example an affine vs. constant dependence
2758              (T[i] vs. T[3]) that is not an affine dependence and is
2759              not representable as a distance vector.  */
2760           non_affine_dependence_relation (ddr);
2761           return false;
2762         }
2763     }
2764
2765   return true;
2766 }
2767
2768 /* Return true when the DDR contains two data references that have the
2769    same access functions.  */
2770
2771 static bool
2772 same_access_functions (struct data_dependence_relation *ddr)
2773 {
2774   unsigned i;
2775
2776   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2777     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
2778                           DR_ACCESS_FN (DDR_B (ddr), i)))
2779       return false;
2780
2781   return true;
2782 }
2783
2784 /* Return true when the DDR contains only constant access functions.  */
2785
2786 static bool
2787 constant_access_functions (struct data_dependence_relation *ddr)
2788 {
2789   unsigned i;
2790
2791   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2792     if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2793         || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2794       return false;
2795
2796   return true;
2797 }
2798
2799
2800 /* Helper function for the case where DDR_A and DDR_B are the same
2801    multivariate access function.  */
2802
2803 static void
2804 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2805 {
2806   int x_1, x_2;
2807   tree c_1 = CHREC_LEFT (c_2);
2808   tree c_0 = CHREC_LEFT (c_1);
2809   lambda_vector dist_v;
2810   int v1, v2, cd;
2811
2812   /* Polynomials with more than 2 variables are not handled yet.  */
2813   if (TREE_CODE (c_0) != INTEGER_CST)
2814     {
2815       DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2816       return;
2817     }
2818
2819   x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2820   x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2821
2822   /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
2823   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2824   v1 = int_cst_value (CHREC_RIGHT (c_1));
2825   v2 = int_cst_value (CHREC_RIGHT (c_2));
2826   cd = gcd (v1, v2);
2827   v1 /= cd;
2828   v2 /= cd;
2829
2830   if (v2 < 0)
2831     {
2832       v2 = -v2;
2833       v1 = -v1;
2834     }
2835
2836   dist_v[x_1] = v2;
2837   dist_v[x_2] = -v1;
2838   save_dist_v (ddr, dist_v);
2839
2840   add_outer_distances (ddr, dist_v, x_1);
2841 }
2842
2843 /* Helper function for the case where DDR_A and DDR_B are the same
2844    access functions.  */
2845
2846 static void
2847 add_other_self_distances (struct data_dependence_relation *ddr)
2848 {
2849   lambda_vector dist_v;
2850   unsigned i;
2851   int index_carry = DDR_NB_LOOPS (ddr);
2852
2853   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2854     {
2855       tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2856
2857       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2858         {
2859           if (!evolution_function_is_univariate_p (access_fun))
2860             {
2861               if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2862                 {
2863                   DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2864                   return;
2865                 }
2866
2867               add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
2868               return;
2869             }
2870
2871           index_carry = MIN (index_carry,
2872                              index_in_loop_nest (CHREC_VARIABLE (access_fun),
2873                                                  DDR_LOOP_NEST (ddr)));
2874         }
2875     }
2876
2877   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2878   add_outer_distances (ddr, dist_v, index_carry);
2879 }
2880
2881 static void
2882 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2883 {
2884   lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2885
2886   dist_v[DDR_INNER_LOOP (ddr)] = 1;
2887   save_dist_v (ddr, dist_v);
2888 }
2889
2890 /* Adds a unit distance vector to DDR when there is a 0 overlap.  This
2891    is the case for example when access functions are the same and
2892    equal to a constant, as in:
2893
2894    | loop_1
2895    |   A[3] = ...
2896    |   ... = A[3]
2897    | endloop_1
2898
2899    in which case the distance vectors are (0) and (1).  */
2900
2901 static void
2902 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2903 {
2904   unsigned i, j;
2905
2906   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2907     {
2908       subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2909       conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2910       conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2911
2912       for (j = 0; j < ca->n; j++)
2913         if (affine_function_zero_p (ca->fns[j]))
2914           {
2915             insert_innermost_unit_dist_vector (ddr);
2916             return;
2917           }
2918
2919       for (j = 0; j < cb->n; j++)
2920         if (affine_function_zero_p (cb->fns[j]))
2921           {
2922             insert_innermost_unit_dist_vector (ddr);
2923             return;
2924           }
2925     }
2926 }
2927
2928 /* Compute the classic per loop distance vector.  DDR is the data
2929    dependence relation to build a vector from.  Return false when fail
2930    to represent the data dependence as a distance vector.  */
2931
2932 static bool
2933 build_classic_dist_vector (struct data_dependence_relation *ddr,
2934                            struct loop *loop_nest)
2935 {
2936   bool init_b = false;
2937   int index_carry = DDR_NB_LOOPS (ddr);
2938   lambda_vector dist_v;
2939
2940   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
2941     return true;
2942
2943   if (same_access_functions (ddr))
2944     {
2945       /* Save the 0 vector.  */
2946       dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2947       save_dist_v (ddr, dist_v);
2948
2949       if (constant_access_functions (ddr))
2950         add_distance_for_zero_overlaps (ddr);
2951
2952       if (DDR_NB_LOOPS (ddr) > 1)
2953         add_other_self_distances (ddr);
2954
2955       return true;
2956     }
2957
2958   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2959   if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
2960                                     dist_v, &init_b, &index_carry))
2961     return false;
2962
2963   /* Save the distance vector if we initialized one.  */
2964   if (init_b)
2965     {
2966       /* Verify a basic constraint: classic distance vectors should
2967          always be lexicographically positive.
2968
2969          Data references are collected in the order of execution of
2970          the program, thus for the following loop
2971
2972          | for (i = 1; i < 100; i++)
2973          |   for (j = 1; j < 100; j++)
2974          |     {
2975          |       t = T[j+1][i-1];  // A
2976          |       T[j][i] = t + 2;  // B
2977          |     }
2978
2979          references are collected following the direction of the wind:
2980          A then B.  The data dependence tests are performed also
2981          following this order, such that we're looking at the distance
2982          separating the elements accessed by A from the elements later
2983          accessed by B.  But in this example, the distance returned by
2984          test_dep (A, B) is lexicographically negative (-1, 1), that
2985          means that the access A occurs later than B with respect to
2986          the outer loop, ie. we're actually looking upwind.  In this
2987          case we solve test_dep (B, A) looking downwind to the
2988          lexicographically positive solution, that returns the
2989          distance vector (1, -1).  */
2990       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
2991         {
2992           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2993           subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2994                                          loop_nest);
2995           compute_subscript_distance (ddr);
2996           build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2997                                        save_v, &init_b, &index_carry);
2998           save_dist_v (ddr, save_v);
2999
3000           /* In this case there is a dependence forward for all the
3001              outer loops:
3002
3003              | for (k = 1; k < 100; k++)
3004              |  for (i = 1; i < 100; i++)
3005              |   for (j = 1; j < 100; j++)
3006              |     {
3007              |       t = T[j+1][i-1];  // A
3008              |       T[j][i] = t + 2;  // B
3009              |     }
3010
3011              the vectors are:
3012              (0,  1, -1)
3013              (1,  1, -1)
3014              (1, -1,  1)
3015           */
3016           if (DDR_NB_LOOPS (ddr) > 1)
3017             {
3018               add_outer_distances (ddr, save_v, index_carry);
3019               add_outer_distances (ddr, dist_v, index_carry);
3020             }
3021         }
3022       else
3023         {
3024           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3025           lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3026           save_dist_v (ddr, save_v);
3027
3028           if (DDR_NB_LOOPS (ddr) > 1)
3029             {
3030               lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3031
3032               subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3033                                              loop_nest);
3034               compute_subscript_distance (ddr);
3035               build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3036                                            opposite_v, &init_b, &index_carry);
3037
3038               add_outer_distances (ddr, dist_v, index_carry);
3039               add_outer_distances (ddr, opposite_v, index_carry);
3040             }
3041         }
3042     }
3043   else
3044     {
3045       /* There is a distance of 1 on all the outer loops: Example:
3046          there is a dependence of distance 1 on loop_1 for the array A.
3047
3048          | loop_1
3049          |   A[5] = ...
3050          | endloop
3051       */
3052       add_outer_distances (ddr, dist_v,
3053                            lambda_vector_first_nz (dist_v,
3054                                                    DDR_NB_LOOPS (ddr), 0));
3055     }
3056
3057   if (dump_file && (dump_flags & TDF_DETAILS))
3058     {
3059       unsigned i;
3060
3061       fprintf (dump_file, "(build_classic_dist_vector\n");
3062       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3063         {
3064           fprintf (dump_file, "  dist_vector = (");
3065           print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3066                                DDR_NB_LOOPS (ddr));
3067           fprintf (dump_file, "  )\n");
3068         }
3069       fprintf (dump_file, ")\n");
3070     }
3071
3072   return true;
3073 }
3074
3075 /* Return the direction for a given distance.
3076    FIXME: Computing dir this way is suboptimal, since dir can catch
3077    cases that dist is unable to represent.  */
3078
3079 static inline enum data_dependence_direction
3080 dir_from_dist (int dist)
3081 {
3082   if (dist > 0)
3083     return dir_positive;
3084   else if (dist < 0)
3085     return dir_negative;
3086   else
3087     return dir_equal;
3088 }
3089
3090 /* Compute the classic per loop direction vector.  DDR is the data
3091    dependence relation to build a vector from.  */
3092
3093 static void
3094 build_classic_dir_vector (struct data_dependence_relation *ddr)
3095 {
3096   unsigned i, j;
3097   lambda_vector dist_v;
3098
3099   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3100     {
3101       lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3102
3103       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3104         dir_v[j] = dir_from_dist (dist_v[j]);
3105
3106       save_dir_v (ddr, dir_v);
3107     }
3108 }
3109
3110 /* Helper function.  Returns true when there is a dependence between
3111    data references DRA and DRB.  */
3112
3113 static bool
3114 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3115                                struct data_reference *dra,
3116                                struct data_reference *drb,
3117                                struct loop *loop_nest)
3118 {
3119   unsigned int i;
3120   tree last_conflicts;
3121   struct subscript *subscript;
3122
3123   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3124        i++)
3125     {
3126       conflict_function *overlaps_a, *overlaps_b;
3127
3128       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3129                                       DR_ACCESS_FN (drb, i),
3130                                       &overlaps_a, &overlaps_b,
3131                                       &last_conflicts, loop_nest);
3132
3133       if (CF_NOT_KNOWN_P (overlaps_a)
3134           || CF_NOT_KNOWN_P (overlaps_b))
3135         {
3136           finalize_ddr_dependent (ddr, chrec_dont_know);
3137           dependence_stats.num_dependence_undetermined++;
3138           free_conflict_function (overlaps_a);
3139           free_conflict_function (overlaps_b);
3140           return false;
3141         }
3142
3143       else if (CF_NO_DEPENDENCE_P (overlaps_a)
3144                || CF_NO_DEPENDENCE_P (overlaps_b))
3145         {
3146           finalize_ddr_dependent (ddr, chrec_known);
3147           dependence_stats.num_dependence_independent++;
3148           free_conflict_function (overlaps_a);
3149           free_conflict_function (overlaps_b);
3150           return false;
3151         }
3152
3153       else
3154         {
3155           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3156           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3157           SUB_LAST_CONFLICT (subscript) = last_conflicts;
3158         }
3159     }
3160
3161   return true;
3162 }
3163
3164 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR.  */
3165
3166 static void
3167 subscript_dependence_tester (struct data_dependence_relation *ddr,
3168                              struct loop *loop_nest)
3169 {
3170
3171   if (dump_file && (dump_flags & TDF_DETAILS))
3172     fprintf (dump_file, "(subscript_dependence_tester \n");
3173
3174   if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3175     dependence_stats.num_dependence_dependent++;
3176
3177   compute_subscript_distance (ddr);
3178   if (build_classic_dist_vector (ddr, loop_nest))
3179     build_classic_dir_vector (ddr);
3180
3181   if (dump_file && (dump_flags & TDF_DETAILS))
3182     fprintf (dump_file, ")\n");
3183 }
3184
3185 /* Returns true when all the access functions of A are affine or
3186    constant with respect to LOOP_NEST.  */
3187
3188 static bool
3189 access_functions_are_affine_or_constant_p (struct data_reference *a,
3190                                            struct loop *loop_nest)
3191 {
3192   unsigned int i;
3193   VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3194   tree t;
3195
3196   for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3197     if (!evolution_function_is_invariant_p (t, loop_nest->num)
3198         && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3199       return false;
3200
3201   return true;
3202 }
3203
3204 /* Initializes an equation for an OMEGA problem using the information
3205    contained in the ACCESS_FUN.  Returns true when the operation
3206    succeeded.
3207
3208    PB is the omega constraint system.
3209    EQ is the number of the equation to be initialized.
3210    OFFSET is used for shifting the variables names in the constraints:
3211    a constrain is composed of 2 * the number of variables surrounding
3212    dependence accesses.  OFFSET is set either to 0 for the first n variables,
3213    then it is set to n.
3214    ACCESS_FUN is expected to be an affine chrec.  */
3215
3216 static bool
3217 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3218                        unsigned int offset, tree access_fun,
3219                        struct data_dependence_relation *ddr)
3220 {
3221   switch (TREE_CODE (access_fun))
3222     {
3223     case POLYNOMIAL_CHREC:
3224       {
3225         tree left = CHREC_LEFT (access_fun);
3226         tree right = CHREC_RIGHT (access_fun);
3227         int var = CHREC_VARIABLE (access_fun);
3228         unsigned var_idx;
3229
3230         if (TREE_CODE (right) != INTEGER_CST)
3231           return false;
3232
3233         var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3234         pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3235
3236         /* Compute the innermost loop index.  */
3237         DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3238
3239         if (offset == 0)
3240           pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3241             += int_cst_value (right);
3242
3243         switch (TREE_CODE (left))
3244           {
3245           case POLYNOMIAL_CHREC:
3246             return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3247
3248           case INTEGER_CST:
3249             pb->eqs[eq].coef[0] += int_cst_value (left);
3250             return true;
3251
3252           default:
3253             return false;
3254           }
3255       }
3256
3257     case INTEGER_CST:
3258       pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3259       return true;
3260
3261     default:
3262       return false;
3263     }
3264 }
3265
3266 /* As explained in the comments preceding init_omega_for_ddr, we have
3267    to set up a system for each loop level, setting outer loops
3268    variation to zero, and current loop variation to positive or zero.
3269    Save each lexico positive distance vector.  */
3270
3271 static void
3272 omega_extract_distance_vectors (omega_pb pb,
3273                                 struct data_dependence_relation *ddr)
3274 {
3275   int eq, geq;
3276   unsigned i, j;
3277   struct loop *loopi, *loopj;
3278   enum omega_result res;
3279
3280   /* Set a new problem for each loop in the nest.  The basis is the
3281      problem that we have initialized until now.  On top of this we
3282      add new constraints.  */
3283   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3284          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3285     {
3286       int dist = 0;
3287       omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3288                                            DDR_NB_LOOPS (ddr));
3289
3290       omega_copy_problem (copy, pb);
3291
3292       /* For all the outer loops "loop_j", add "dj = 0".  */
3293       for (j = 0;
3294            j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3295         {
3296           eq = omega_add_zero_eq (copy, omega_black);
3297           copy->eqs[eq].coef[j + 1] = 1;
3298         }
3299
3300       /* For "loop_i", add "0 <= di".  */
3301       geq = omega_add_zero_geq (copy, omega_black);
3302       copy->geqs[geq].coef[i + 1] = 1;
3303
3304       /* Reduce the constraint system, and test that the current
3305          problem is feasible.  */
3306       res = omega_simplify_problem (copy);
3307       if (res == omega_false
3308           || res == omega_unknown
3309           || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3310         goto next_problem;
3311
3312       for (eq = 0; eq < copy->num_subs; eq++)
3313         if (copy->subs[eq].key == (int) i + 1)
3314           {
3315             dist = copy->subs[eq].coef[0];
3316             goto found_dist;
3317           }
3318
3319       if (dist == 0)
3320         {
3321           /* Reinitialize problem...  */
3322           omega_copy_problem (copy, pb);
3323           for (j = 0;
3324                j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3325             {
3326               eq = omega_add_zero_eq (copy, omega_black);
3327               copy->eqs[eq].coef[j + 1] = 1;
3328             }
3329
3330           /* ..., but this time "di = 1".  */
3331           eq = omega_add_zero_eq (copy, omega_black);
3332           copy->eqs[eq].coef[i + 1] = 1;
3333           copy->eqs[eq].coef[0] = -1;
3334
3335           res = omega_simplify_problem (copy);
3336           if (res == omega_false
3337               || res == omega_unknown
3338               || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3339             goto next_problem;
3340
3341           for (eq = 0; eq < copy->num_subs; eq++)
3342             if (copy->subs[eq].key == (int) i + 1)
3343               {
3344                 dist = copy->subs[eq].coef[0];
3345                 goto found_dist;
3346               }
3347         }
3348
3349     found_dist:;
3350       /* Save the lexicographically positive distance vector.  */
3351       if (dist >= 0)
3352         {
3353           lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3354           lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3355
3356           dist_v[i] = dist;
3357
3358           for (eq = 0; eq < copy->num_subs; eq++)
3359             if (copy->subs[eq].key > 0)
3360               {
3361                 dist = copy->subs[eq].coef[0];
3362                 dist_v[copy->subs[eq].key - 1] = dist;
3363               }
3364
3365           for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3366             dir_v[j] = dir_from_dist (dist_v[j]);
3367
3368           save_dist_v (ddr, dist_v);
3369           save_dir_v (ddr, dir_v);
3370         }
3371
3372     next_problem:;
3373       omega_free_problem (copy);
3374     }
3375 }
3376
3377 /* This is called for each subscript of a tuple of data references:
3378    insert an equality for representing the conflicts.  */
3379
3380 static bool
3381 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3382                        struct data_dependence_relation *ddr,
3383                        omega_pb pb, bool *maybe_dependent)
3384 {
3385   int eq;
3386   tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
3387   tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
3388   tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
3389
3390   /* When the fun_a - fun_b is not constant, the dependence is not
3391      captured by the classic distance vector representation.  */
3392   if (TREE_CODE (difference) != INTEGER_CST)
3393     return false;
3394
3395   /* ZIV test.  */
3396   if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3397     {
3398       /* There is no dependence.  */
3399       *maybe_dependent = false;
3400       return true;
3401     }
3402
3403   fun_b = chrec_fold_multiply (integer_type_node, fun_b,
3404                                integer_minus_one_node);
3405
3406   eq = omega_add_zero_eq (pb, omega_black);
3407   if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3408       || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3409     /* There is probably a dependence, but the system of
3410        constraints cannot be built: answer "don't know".  */
3411     return false;
3412
3413   /* GCD test.  */
3414   if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3415       && !int_divides_p (lambda_vector_gcd
3416                          ((lambda_vector) &(pb->eqs[eq].coef[1]),
3417                           2 * DDR_NB_LOOPS (ddr)),
3418                          pb->eqs[eq].coef[0]))
3419     {
3420       /* There is no dependence.  */
3421       *maybe_dependent = false;
3422       return true;
3423     }
3424
3425   return true;
3426 }
3427
3428 /* Helper function, same as init_omega_for_ddr but specialized for
3429    data references A and B.  */
3430
3431 static bool
3432 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3433                       struct data_dependence_relation *ddr,
3434                       omega_pb pb, bool *maybe_dependent)
3435 {
3436   unsigned i;
3437   int ineq;
3438   struct loop *loopi;
3439   unsigned nb_loops = DDR_NB_LOOPS (ddr);
3440
3441   /* Insert an equality per subscript.  */
3442   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3443     {
3444       if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3445                                   ddr, pb, maybe_dependent))
3446         return false;
3447       else if (*maybe_dependent == false)
3448         {
3449           /* There is no dependence.  */
3450           DDR_ARE_DEPENDENT (ddr) = chrec_known;
3451           return true;
3452         }
3453     }
3454
3455   /* Insert inequalities: constraints corresponding to the iteration
3456      domain, i.e. the loops surrounding the references "loop_x" and
3457      the distance variables "dx".  The layout of the OMEGA
3458      representation is as follows:
3459      - coef[0] is the constant
3460      - coef[1..nb_loops] are the protected variables that will not be
3461      removed by the solver: the "dx"
3462      - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3463   */
3464   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3465          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3466     {
3467       HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3468
3469       /* 0 <= loop_x */
3470       ineq = omega_add_zero_geq (pb, omega_black);
3471       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3472
3473       /* 0 <= loop_x + dx */
3474       ineq = omega_add_zero_geq (pb, omega_black);
3475       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3476       pb->geqs[ineq].coef[i + 1] = 1;
3477
3478       if (nbi != -1)
3479         {
3480           /* loop_x <= nb_iters */
3481           ineq = omega_add_zero_geq (pb, omega_black);
3482           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3483           pb->geqs[ineq].coef[0] = nbi;
3484
3485           /* loop_x + dx <= nb_iters */
3486           ineq = omega_add_zero_geq (pb, omega_black);
3487           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3488           pb->geqs[ineq].coef[i + 1] = -1;
3489           pb->geqs[ineq].coef[0] = nbi;
3490
3491           /* A step "dx" bigger than nb_iters is not feasible, so
3492              add "0 <= nb_iters + dx",  */
3493           ineq = omega_add_zero_geq (pb, omega_black);
3494           pb->geqs[ineq].coef[i + 1] = 1;
3495           pb->geqs[ineq].coef[0] = nbi;
3496           /* and "dx <= nb_iters".  */
3497           ineq = omega_add_zero_geq (pb, omega_black);
3498           pb->geqs[ineq].coef[i + 1] = -1;
3499           pb->geqs[ineq].coef[0] = nbi;
3500         }
3501     }
3502
3503   omega_extract_distance_vectors (pb, ddr);
3504
3505   return true;
3506 }
3507
3508 /* Sets up the Omega dependence problem for the data dependence
3509    relation DDR.  Returns false when the constraint system cannot be
3510    built, ie. when the test answers "don't know".  Returns true
3511    otherwise, and when independence has been proved (using one of the
3512    trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3513    set MAYBE_DEPENDENT to true.
3514
3515    Example: for setting up the dependence system corresponding to the
3516    conflicting accesses
3517
3518    | loop_i
3519    |   loop_j
3520    |     A[i, i+1] = ...
3521    |     ... A[2*j, 2*(i + j)]
3522    |   endloop_j
3523    | endloop_i
3524
3525    the following constraints come from the iteration domain:
3526
3527    0 <= i <= Ni
3528    0 <= i + di <= Ni
3529    0 <= j <= Nj
3530    0 <= j + dj <= Nj
3531
3532    where di, dj are the distance variables.  The constraints
3533    representing the conflicting elements are:
3534
3535    i = 2 * (j + dj)
3536    i + 1 = 2 * (i + di + j + dj)
3537
3538    For asking that the resulting distance vector (di, dj) be
3539    lexicographically positive, we insert the constraint "di >= 0".  If
3540    "di = 0" in the solution, we fix that component to zero, and we
3541    look at the inner loops: we set a new problem where all the outer
3542    loop distances are zero, and fix this inner component to be
3543    positive.  When one of the components is positive, we save that
3544    distance, and set a new problem where the distance on this loop is
3545    zero, searching for other distances in the inner loops.  Here is
3546    the classic example that illustrates that we have to set for each
3547    inner loop a new problem:
3548
3549    | loop_1
3550    |   loop_2
3551    |     A[10]
3552    |   endloop_2
3553    | endloop_1
3554
3555    we have to save two distances (1, 0) and (0, 1).
3556
3557    Given two array references, refA and refB, we have to set the
3558    dependence problem twice, refA vs. refB and refB vs. refA, and we
3559    cannot do a single test, as refB might occur before refA in the
3560    inner loops, and the contrary when considering outer loops: ex.
3561
3562    | loop_0
3563    |   loop_1
3564    |     loop_2
3565    |       T[{1,+,1}_2][{1,+,1}_1]  // refA
3566    |       T[{2,+,1}_2][{0,+,1}_1]  // refB
3567    |     endloop_2
3568    |   endloop_1
3569    | endloop_0
3570
3571    refB touches the elements in T before refA, and thus for the same
3572    loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3573    but for successive loop_0 iterations, we have (1, -1, 1)
3574
3575    The Omega solver expects the distance variables ("di" in the
3576    previous example) to come first in the constraint system (as
3577    variables to be protected, or "safe" variables), the constraint
3578    system is built using the following layout:
3579
3580    "cst | distance vars | index vars".
3581 */
3582
3583 static bool
3584 init_omega_for_ddr (struct data_dependence_relation *ddr,
3585                     bool *maybe_dependent)
3586 {
3587   omega_pb pb;
3588   bool res = false;
3589
3590   *maybe_dependent = true;
3591
3592   if (same_access_functions (ddr))
3593     {
3594       unsigned j;
3595       lambda_vector dir_v;
3596
3597       /* Save the 0 vector.  */
3598       save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3599       dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3600       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3601         dir_v[j] = dir_equal;
3602       save_dir_v (ddr, dir_v);
3603
3604       /* Save the dependences carried by outer loops.  */
3605       pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3606       res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3607                                   maybe_dependent);
3608       omega_free_problem (pb);
3609       return res;
3610     }
3611
3612   /* Omega expects the protected variables (those that have to be kept
3613      after elimination) to appear first in the constraint system.
3614      These variables are the distance variables.  In the following
3615      initialization we declare NB_LOOPS safe variables, and the total
3616      number of variables for the constraint system is 2*NB_LOOPS.  */
3617   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3618   res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3619                               maybe_dependent);
3620   omega_free_problem (pb);
3621
3622   /* Stop computation if not decidable, or no dependence.  */
3623   if (res == false || *maybe_dependent == false)
3624     return res;
3625
3626   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3627   res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3628                               maybe_dependent);
3629   omega_free_problem (pb);
3630
3631   return res;
3632 }
3633
3634 /* Return true when DDR contains the same information as that stored
3635    in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
3636
3637 static bool
3638 ddr_consistent_p (FILE *file,
3639                   struct data_dependence_relation *ddr,
3640                   VEC (lambda_vector, heap) *dist_vects,
3641                   VEC (lambda_vector, heap) *dir_vects)
3642 {
3643   unsigned int i, j;
3644
3645   /* If dump_file is set, output there.  */
3646   if (dump_file && (dump_flags & TDF_DETAILS))
3647     file = dump_file;
3648
3649   if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3650     {
3651       lambda_vector b_dist_v;
3652       fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3653                VEC_length (lambda_vector, dist_vects),
3654                DDR_NUM_DIST_VECTS (ddr));
3655
3656       fprintf (file, "Banerjee dist vectors:\n");
3657       for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3658         print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3659
3660       fprintf (file, "Omega dist vectors:\n");
3661       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3662         print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3663
3664       fprintf (file, "data dependence relation:\n");
3665       dump_data_dependence_relation (file, ddr);
3666
3667       fprintf (file, ")\n");
3668       return false;
3669     }
3670
3671   if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3672     {
3673       fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3674                VEC_length (lambda_vector, dir_vects),
3675                DDR_NUM_DIR_VECTS (ddr));
3676       return false;
3677     }
3678
3679   for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3680     {
3681       lambda_vector a_dist_v;
3682       lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3683
3684       /* Distance vectors are not ordered in the same way in the DDR
3685          and in the DIST_VECTS: search for a matching vector.  */
3686       for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3687         if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3688           break;
3689
3690       if (j == VEC_length (lambda_vector, dist_vects))
3691         {
3692           fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3693           print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3694           fprintf (file, "not found in Omega dist vectors:\n");
3695           print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3696           fprintf (file, "data dependence relation:\n");
3697           dump_data_dependence_relation (file, ddr);
3698           fprintf (file, ")\n");
3699         }
3700     }
3701
3702   for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3703     {
3704       lambda_vector a_dir_v;
3705       lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3706
3707       /* Direction vectors are not ordered in the same way in the DDR
3708          and in the DIR_VECTS: search for a matching vector.  */
3709       for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3710         if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3711           break;
3712
3713       if (j == VEC_length (lambda_vector, dist_vects))
3714         {
3715           fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3716           print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3717           fprintf (file, "not found in Omega dir vectors:\n");
3718           print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3719           fprintf (file, "data dependence relation:\n");
3720           dump_data_dependence_relation (file, ddr);
3721           fprintf (file, ")\n");
3722         }
3723     }
3724
3725   return true;
3726 }
3727
3728 /* This computes the affine dependence relation between A and B with
3729    respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
3730    independence between two accesses, while CHREC_DONT_KNOW is used
3731    for representing the unknown relation.
3732
3733    Note that it is possible to stop the computation of the dependence
3734    relation the first time we detect a CHREC_KNOWN element for a given
3735    subscript.  */
3736
3737 static void
3738 compute_affine_dependence (struct data_dependence_relation *ddr,
3739                            struct loop *loop_nest)
3740 {
3741   struct data_reference *dra = DDR_A (ddr);
3742   struct data_reference *drb = DDR_B (ddr);
3743
3744   if (dump_file && (dump_flags & TDF_DETAILS))
3745     {
3746       fprintf (dump_file, "(compute_affine_dependence\n");
3747       fprintf (dump_file, "  (stmt_a = \n");
3748       print_generic_expr (dump_file, DR_STMT (dra), 0);
3749       fprintf (dump_file, ")\n  (stmt_b = \n");
3750       print_generic_expr (dump_file, DR_STMT (drb), 0);
3751       fprintf (dump_file, ")\n");
3752     }
3753
3754   /* Analyze only when the dependence relation is not yet known.  */
3755   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3756     {
3757       dependence_stats.num_dependence_tests++;
3758
3759       if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3760           && access_functions_are_affine_or_constant_p (drb, loop_nest))
3761         {
3762           if (flag_check_data_deps)
3763             {
3764               /* Compute the dependences using the first algorithm.  */
3765               subscript_dependence_tester (ddr, loop_nest);
3766
3767               if (dump_file && (dump_flags & TDF_DETAILS))
3768                 {
3769                   fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3770                   dump_data_dependence_relation (dump_file, ddr);
3771                 }
3772
3773               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3774                 {
3775                   bool maybe_dependent;
3776                   VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3777
3778                   /* Save the result of the first DD analyzer.  */
3779                   dist_vects = DDR_DIST_VECTS (ddr);
3780                   dir_vects = DDR_DIR_VECTS (ddr);
3781
3782                   /* Reset the information.  */
3783                   DDR_DIST_VECTS (ddr) = NULL;
3784                   DDR_DIR_VECTS (ddr) = NULL;
3785
3786                   /* Compute the same information using Omega.  */
3787                   if (!init_omega_for_ddr (ddr, &maybe_dependent))
3788                     goto csys_dont_know;
3789
3790                   if (dump_file && (dump_flags & TDF_DETAILS))
3791                     {
3792                       fprintf (dump_file, "Omega Analyzer\n");
3793                       dump_data_dependence_relation (dump_file, ddr);
3794                     }
3795
3796                   /* Check that we get the same information.  */
3797                   if (maybe_dependent)
3798                     gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3799                                                   dir_vects));
3800                 }
3801             }
3802           else
3803             subscript_dependence_tester (ddr, loop_nest);
3804         }
3805
3806       /* As a last case, if the dependence cannot be determined, or if
3807          the dependence is considered too difficult to determine, answer
3808          "don't know".  */
3809       else
3810         {
3811         csys_dont_know:;
3812           dependence_stats.num_dependence_undetermined++;
3813
3814           if (dump_file && (dump_flags & TDF_DETAILS))
3815             {
3816               fprintf (dump_file, "Data ref a:\n");
3817               dump_data_reference (dump_file, dra);
3818               fprintf (dump_file, "Data ref b:\n");
3819               dump_data_reference (dump_file, drb);
3820               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3821             }
3822           finalize_ddr_dependent (ddr, chrec_dont_know);
3823         }
3824     }
3825
3826   if (dump_file && (dump_flags & TDF_DETAILS))
3827     fprintf (dump_file, ")\n");
3828 }
3829
3830 /* This computes the dependence relation for the same data
3831    reference into DDR.  */
3832
3833 static void
3834 compute_self_dependence (struct data_dependence_relation *ddr)
3835 {
3836   unsigned int i;
3837   struct subscript *subscript;
3838
3839   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3840     return;
3841
3842   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3843        i++)
3844     {
3845       /* The accessed index overlaps for each iteration.  */
3846       SUB_CONFLICTS_IN_A (subscript)
3847               = conflict_fn (1, affine_fn_cst (integer_zero_node));
3848       SUB_CONFLICTS_IN_B (subscript)
3849               = conflict_fn (1, affine_fn_cst (integer_zero_node));
3850       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3851     }
3852
3853   /* The distance vector is the zero vector.  */
3854   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3855   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3856 }
3857
3858 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3859    the data references in DATAREFS, in the LOOP_NEST.  When
3860    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3861    relations.  */
3862
3863 void
3864 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3865                          VEC (ddr_p, heap) **dependence_relations,
3866                          VEC (loop_p, heap) *loop_nest,
3867                          bool compute_self_and_rr)
3868 {
3869   struct data_dependence_relation *ddr;
3870   struct data_reference *a, *b;
3871   unsigned int i, j;
3872
3873   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3874     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3875       if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3876         {
3877           ddr = initialize_data_dependence_relation (a, b, loop_nest);
3878           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3879           compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3880         }
3881
3882   if (compute_self_and_rr)
3883     for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3884       {
3885         ddr = initialize_data_dependence_relation (a, a, loop_nest);
3886         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3887         compute_self_dependence (ddr);
3888       }
3889 }
3890
3891 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
3892    true if STMT clobbers memory, false otherwise.  */
3893
3894 bool
3895 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3896 {
3897   bool clobbers_memory = false;
3898   data_ref_loc *ref;
3899   tree *op0, *op1, call;
3900
3901   *references = NULL;
3902
3903   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3904      Calls have side-effects, except those to const or pure
3905      functions.  */
3906   call = get_call_expr_in (stmt);
3907   if ((call
3908        && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
3909       || (TREE_CODE (stmt) == ASM_EXPR
3910           && ASM_VOLATILE_P (stmt)))
3911     clobbers_memory = true;
3912
3913   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3914     return clobbers_memory;
3915
3916   if (TREE_CODE (stmt) ==  GIMPLE_MODIFY_STMT)
3917     {
3918       op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
3919       op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
3920
3921       if (DECL_P (*op1)
3922           || REFERENCE_CLASS_P (*op1))
3923         {
3924           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3925           ref->pos = op1;
3926           ref->is_read = true;
3927         }
3928
3929       if (DECL_P (*op0)
3930           || REFERENCE_CLASS_P (*op0))
3931         {
3932           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3933           ref->pos = op0;
3934           ref->is_read = false;
3935         }
3936     }
3937
3938   if (call)
3939     {
3940       unsigned i, n = call_expr_nargs (call);
3941
3942       for (i = 0; i < n; i++)
3943         {
3944           op0 = &CALL_EXPR_ARG (call, i);
3945
3946           if (DECL_P (*op0)
3947               || REFERENCE_CLASS_P (*op0))
3948             {
3949               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3950               ref->pos = op0;
3951               ref->is_read = true;
3952             }
3953         }
3954     }
3955
3956   return clobbers_memory;
3957 }
3958
3959 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
3960    reference, returns false, otherwise returns true.  NEST is the outermost
3961    loop of the loop nest in that the references should be analyzed.  */
3962
3963 static bool
3964 find_data_references_in_stmt (struct loop *nest, tree stmt,
3965                               VEC (data_reference_p, heap) **datarefs)
3966 {
3967   unsigned i;
3968   VEC (data_ref_loc, heap) *references;
3969   data_ref_loc *ref;
3970   bool ret = true;
3971   data_reference_p dr;
3972
3973   if (get_references_in_stmt (stmt, &references))
3974     {
3975       VEC_free (data_ref_loc, heap, references);
3976       return false;
3977     }
3978
3979   for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
3980     {
3981       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
3982       gcc_assert (dr != NULL);
3983
3984       /* FIXME -- data dependence analysis does not work correctly for objects with
3985          invariant addresses.  Let us fail here until the problem is fixed.  */
3986       if (dr_address_invariant_p (dr))
3987         {
3988           free_data_ref (dr);
3989           if (dump_file && (dump_flags & TDF_DETAILS))
3990             fprintf (dump_file, "\tFAILED as dr address is invariant\n");
3991           ret = false;
3992           break;
3993         }
3994
3995       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
3996     }
3997   VEC_free (data_ref_loc, heap, references);
3998   return ret;
3999 }
4000
4001 /* Search the data references in LOOP, and record the information into
4002    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4003    difficult case, returns NULL_TREE otherwise.
4004
4005    TODO: This function should be made smarter so that it can handle address
4006    arithmetic as if they were array accesses, etc.  */
4007
4008 static tree
4009 find_data_references_in_loop (struct loop *loop,
4010                               VEC (data_reference_p, heap) **datarefs)
4011 {
4012   basic_block bb, *bbs;
4013   unsigned int i;
4014   block_stmt_iterator bsi;
4015
4016   bbs = get_loop_body_in_dom_order (loop);
4017
4018   for (i = 0; i < loop->num_nodes; i++)
4019     {
4020       bb = bbs[i];
4021
4022       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4023         {
4024           tree stmt = bsi_stmt (bsi);
4025
4026           if (!find_data_references_in_stmt (loop, stmt, datarefs))
4027             {
4028               struct data_reference *res;
4029               res = XCNEW (struct data_reference);
4030               VEC_safe_push (data_reference_p, heap, *datarefs, res);
4031
4032               free (bbs);
4033               return chrec_dont_know;
4034             }
4035         }
4036     }
4037   free (bbs);
4038
4039   return NULL_TREE;
4040 }
4041
4042 /* Recursive helper function.  */
4043
4044 static bool
4045 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4046 {
4047   /* Inner loops of the nest should not contain siblings.  Example:
4048      when there are two consecutive loops,
4049
4050      | loop_0
4051      |   loop_1
4052      |     A[{0, +, 1}_1]
4053      |   endloop_1
4054      |   loop_2
4055      |     A[{0, +, 1}_2]
4056      |   endloop_2
4057      | endloop_0
4058
4059      the dependence relation cannot be captured by the distance
4060      abstraction.  */
4061   if (loop->next)
4062     return false;
4063
4064   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4065   if (loop->inner)
4066     return find_loop_nest_1 (loop->inner, loop_nest);
4067   return true;
4068 }
4069
4070 /* Return false when the LOOP is not well nested.  Otherwise return
4071    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4072    contain the loops from the outermost to the innermost, as they will
4073    appear in the classic distance vector.  */
4074
4075 bool
4076 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4077 {
4078   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4079   if (loop->inner)
4080     return find_loop_nest_1 (loop->inner, loop_nest);
4081   return true;
4082 }
4083
4084 /* Given a loop nest LOOP, the following vectors are returned:
4085    DATAREFS is initialized to all the array elements contained in this loop,
4086    DEPENDENCE_RELATIONS contains the relations between the data references.
4087    Compute read-read and self relations if
4088    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4089
4090 void
4091 compute_data_dependences_for_loop (struct loop *loop,
4092                                    bool compute_self_and_read_read_dependences,
4093                                    VEC (data_reference_p, heap) **datarefs,
4094                                    VEC (ddr_p, heap) **dependence_relations)
4095 {
4096   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4097
4098   memset (&dependence_stats, 0, sizeof (dependence_stats));
4099
4100   /* If the loop nest is not well formed, or one of the data references
4101      is not computable, give up without spending time to compute other
4102      dependences.  */
4103   if (!loop
4104       || !find_loop_nest (loop, &vloops)
4105       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4106     {
4107       struct data_dependence_relation *ddr;
4108
4109       /* Insert a single relation into dependence_relations:
4110          chrec_dont_know.  */
4111       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4112       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4113     }
4114   else
4115     compute_all_dependences (*datarefs, dependence_relations, vloops,
4116                              compute_self_and_read_read_dependences);
4117
4118   if (dump_file && (dump_flags & TDF_STATS))
4119     {
4120       fprintf (dump_file, "Dependence tester statistics:\n");
4121
4122       fprintf (dump_file, "Number of dependence tests: %d\n",
4123                dependence_stats.num_dependence_tests);
4124       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4125                dependence_stats.num_dependence_dependent);
4126       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4127                dependence_stats.num_dependence_independent);
4128       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4129                dependence_stats.num_dependence_undetermined);
4130
4131       fprintf (dump_file, "Number of subscript tests: %d\n",
4132                dependence_stats.num_subscript_tests);
4133       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4134                dependence_stats.num_subscript_undetermined);
4135       fprintf (dump_file, "Number of same subscript function: %d\n",
4136                dependence_stats.num_same_subscript_function);
4137
4138       fprintf (dump_file, "Number of ziv tests: %d\n",
4139                dependence_stats.num_ziv);
4140       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4141                dependence_stats.num_ziv_dependent);
4142       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4143                dependence_stats.num_ziv_independent);
4144       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4145                dependence_stats.num_ziv_unimplemented);
4146
4147       fprintf (dump_file, "Number of siv tests: %d\n",
4148                dependence_stats.num_siv);
4149       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4150                dependence_stats.num_siv_dependent);
4151       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4152                dependence_stats.num_siv_independent);
4153       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4154                dependence_stats.num_siv_unimplemented);
4155
4156       fprintf (dump_file, "Number of miv tests: %d\n",
4157                dependence_stats.num_miv);
4158       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4159                dependence_stats.num_miv_dependent);
4160       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4161                dependence_stats.num_miv_independent);
4162       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4163                dependence_stats.num_miv_unimplemented);
4164     }
4165 }
4166
4167 /* Entry point (for testing only).  Analyze all the data references
4168    and the dependence relations in LOOP.
4169
4170    The data references are computed first.
4171
4172    A relation on these nodes is represented by a complete graph.  Some
4173    of the relations could be of no interest, thus the relations can be
4174    computed on demand.
4175
4176    In the following function we compute all the relations.  This is
4177    just a first implementation that is here for:
4178    - for showing how to ask for the dependence relations,
4179    - for the debugging the whole dependence graph,
4180    - for the dejagnu testcases and maintenance.
4181
4182    It is possible to ask only for a part of the graph, avoiding to
4183    compute the whole dependence graph.  The computed dependences are
4184    stored in a knowledge base (KB) such that later queries don't
4185    recompute the same information.  The implementation of this KB is
4186    transparent to the optimizer, and thus the KB can be changed with a
4187    more efficient implementation, or the KB could be disabled.  */
4188 static void
4189 analyze_all_data_dependences (struct loop *loop)
4190 {
4191   unsigned int i;
4192   int nb_data_refs = 10;
4193   VEC (data_reference_p, heap) *datarefs =
4194     VEC_alloc (data_reference_p, heap, nb_data_refs);
4195   VEC (ddr_p, heap) *dependence_relations =
4196     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4197
4198   /* Compute DDs on the whole function.  */
4199   compute_data_dependences_for_loop (loop, false, &datarefs,
4200                                      &dependence_relations);
4201
4202   if (dump_file)
4203     {
4204       dump_data_dependence_relations (dump_file, dependence_relations);
4205       fprintf (dump_file, "\n\n");
4206
4207       if (dump_flags & TDF_DETAILS)
4208         dump_dist_dir_vectors (dump_file, dependence_relations);
4209
4210       if (dump_flags & TDF_STATS)
4211         {
4212           unsigned nb_top_relations = 0;
4213           unsigned nb_bot_relations = 0;
4214           unsigned nb_basename_differ = 0;
4215           unsigned nb_chrec_relations = 0;
4216           struct data_dependence_relation *ddr;
4217
4218           for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4219             {
4220               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4221                 nb_top_relations++;
4222
4223               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4224                 {
4225                   struct data_reference *a = DDR_A (ddr);
4226                   struct data_reference *b = DDR_B (ddr);
4227
4228                   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4229                     nb_basename_differ++;
4230                   else
4231                     nb_bot_relations++;
4232                 }
4233
4234               else
4235                 nb_chrec_relations++;
4236             }
4237
4238           gather_stats_on_scev_database ();
4239         }
4240     }
4241
4242   free_dependence_relations (dependence_relations);
4243   free_data_refs (datarefs);
4244 }
4245
4246 /* Computes all the data dependences and check that the results of
4247    several analyzers are the same.  */
4248
4249 void
4250 tree_check_data_deps (void)
4251 {
4252   loop_iterator li;
4253   struct loop *loop_nest;
4254
4255   FOR_EACH_LOOP (li, loop_nest, 0)
4256     analyze_all_data_dependences (loop_nest);
4257 }
4258
4259 /* Free the memory used by a data dependence relation DDR.  */
4260
4261 void
4262 free_dependence_relation (struct data_dependence_relation *ddr)
4263 {
4264   if (ddr == NULL)
4265     return;
4266
4267   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4268     free_subscripts (DDR_SUBSCRIPTS (ddr));
4269
4270   free (ddr);
4271 }
4272
4273 /* Free the memory used by the data dependence relations from
4274    DEPENDENCE_RELATIONS.  */
4275
4276 void
4277 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4278 {
4279   unsigned int i;
4280   struct data_dependence_relation *ddr;
4281   VEC (loop_p, heap) *loop_nest = NULL;
4282
4283   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4284     {
4285       if (ddr == NULL)
4286         continue;
4287       if (loop_nest == NULL)
4288         loop_nest = DDR_LOOP_NEST (ddr);
4289       else
4290         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4291                     || DDR_LOOP_NEST (ddr) == loop_nest);
4292       free_dependence_relation (ddr);
4293     }
4294
4295   if (loop_nest)
4296     VEC_free (loop_p, heap, loop_nest);
4297   VEC_free (ddr_p, heap, dependence_relations);
4298 }
4299
4300 /* Free the memory used by the data references from DATAREFS.  */
4301
4302 void
4303 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4304 {
4305   unsigned int i;
4306   struct data_reference *dr;
4307
4308   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4309     free_data_ref (dr);
4310   VEC_free (data_reference_p, heap, datarefs);
4311 }
4312