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   DDR_REVERSED_P (res) = false;
1212
1213   if (a == NULL || b == NULL)
1214     {
1215       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1216       return res;
1217     }
1218
1219   /* If the data references do not alias, then they are independent.  */
1220   if (!dr_may_alias_p (a, b))
1221     {
1222       DDR_ARE_DEPENDENT (res) = chrec_known;
1223       return res;
1224     }
1225
1226   /* If the references do not access the same object, we do not know
1227      whether they alias or not.  */
1228   if (!operand_equal_p (DR_BASE_OBJECT (a), DR_BASE_OBJECT (b), 0))
1229     {
1230       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1231       return res;
1232     }
1233
1234   /* If the base of the object is not invariant in the loop nest, we cannot
1235      analyze it.  TODO -- in fact, it would suffice to record that there may
1236      be arbitrary dependences in the loops where the base object varies.  */
1237   if (!object_address_invariant_in_loop_p (VEC_index (loop_p, loop_nest, 0),
1238                                            DR_BASE_OBJECT (a)))
1239     {
1240       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
1241       return res;
1242     }
1243
1244   gcc_assert (DR_NUM_DIMENSIONS (a) == DR_NUM_DIMENSIONS (b));
1245
1246   DDR_AFFINE_P (res) = true;
1247   DDR_ARE_DEPENDENT (res) = NULL_TREE;
1248   DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
1249   DDR_LOOP_NEST (res) = loop_nest;
1250   DDR_INNER_LOOP (res) = 0;
1251   DDR_DIR_VECTS (res) = NULL;
1252   DDR_DIST_VECTS (res) = NULL;
1253
1254   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
1255     {
1256       struct subscript *subscript;
1257
1258       subscript = XNEW (struct subscript);
1259       SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
1260       SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
1261       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
1262       SUB_DISTANCE (subscript) = chrec_dont_know;
1263       VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
1264     }
1265
1266   return res;
1267 }
1268
1269 /* Frees memory used by the conflict function F.  */
1270
1271 static void
1272 free_conflict_function (conflict_function *f)
1273 {
1274   unsigned i;
1275
1276   if (CF_NONTRIVIAL_P (f))
1277     {
1278       for (i = 0; i < f->n; i++)
1279         affine_fn_free (f->fns[i]);
1280     }
1281   free (f);
1282 }
1283
1284 /* Frees memory used by SUBSCRIPTS.  */
1285
1286 static void
1287 free_subscripts (VEC (subscript_p, heap) *subscripts)
1288 {
1289   unsigned i;
1290   subscript_p s;
1291
1292   for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
1293     {
1294       free_conflict_function (s->conflicting_iterations_in_a);
1295       free_conflict_function (s->conflicting_iterations_in_b);
1296     }
1297   VEC_free (subscript_p, heap, subscripts);
1298 }
1299
1300 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
1301    description.  */
1302
1303 static inline void
1304 finalize_ddr_dependent (struct data_dependence_relation *ddr,
1305                         tree chrec)
1306 {
1307   if (dump_file && (dump_flags & TDF_DETAILS))
1308     {
1309       fprintf (dump_file, "(dependence classified: ");
1310       print_generic_expr (dump_file, chrec, 0);
1311       fprintf (dump_file, ")\n");
1312     }
1313
1314   DDR_ARE_DEPENDENT (ddr) = chrec;
1315   free_subscripts (DDR_SUBSCRIPTS (ddr));
1316 }
1317
1318 /* The dependence relation DDR cannot be represented by a distance
1319    vector.  */
1320
1321 static inline void
1322 non_affine_dependence_relation (struct data_dependence_relation *ddr)
1323 {
1324   if (dump_file && (dump_flags & TDF_DETAILS))
1325     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
1326
1327   DDR_AFFINE_P (ddr) = false;
1328 }
1329
1330 \f
1331
1332 /* This section contains the classic Banerjee tests.  */
1333
1334 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
1335    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
1336
1337 static inline bool
1338 ziv_subscript_p (tree chrec_a,
1339                  tree chrec_b)
1340 {
1341   return (evolution_function_is_constant_p (chrec_a)
1342           && evolution_function_is_constant_p (chrec_b));
1343 }
1344
1345 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
1346    variable, i.e., if the SIV (Single Index Variable) test is true.  */
1347
1348 static bool
1349 siv_subscript_p (tree chrec_a,
1350                  tree chrec_b)
1351 {
1352   if ((evolution_function_is_constant_p (chrec_a)
1353        && evolution_function_is_univariate_p (chrec_b))
1354       || (evolution_function_is_constant_p (chrec_b)
1355           && evolution_function_is_univariate_p (chrec_a)))
1356     return true;
1357
1358   if (evolution_function_is_univariate_p (chrec_a)
1359       && evolution_function_is_univariate_p (chrec_b))
1360     {
1361       switch (TREE_CODE (chrec_a))
1362         {
1363         case POLYNOMIAL_CHREC:
1364           switch (TREE_CODE (chrec_b))
1365             {
1366             case POLYNOMIAL_CHREC:
1367               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
1368                 return false;
1369
1370             default:
1371               return true;
1372             }
1373
1374         default:
1375           return true;
1376         }
1377     }
1378
1379   return false;
1380 }
1381
1382 /* Creates a conflict function with N dimensions.  The affine functions
1383    in each dimension follow.  */
1384
1385 static conflict_function *
1386 conflict_fn (unsigned n, ...)
1387 {
1388   unsigned i;
1389   conflict_function *ret = XCNEW (conflict_function);
1390   va_list ap;
1391
1392   gcc_assert (0 < n && n <= MAX_DIM);
1393   va_start(ap, n);
1394
1395   ret->n = n;
1396   for (i = 0; i < n; i++)
1397     ret->fns[i] = va_arg (ap, affine_fn);
1398   va_end(ap);
1399
1400   return ret;
1401 }
1402
1403 /* Returns constant affine function with value CST.  */
1404
1405 static affine_fn
1406 affine_fn_cst (tree cst)
1407 {
1408   affine_fn fn = VEC_alloc (tree, heap, 1);
1409   VEC_quick_push (tree, fn, cst);
1410   return fn;
1411 }
1412
1413 /* Returns affine function with single variable, CST + COEF * x_DIM.  */
1414
1415 static affine_fn
1416 affine_fn_univar (tree cst, unsigned dim, tree coef)
1417 {
1418   affine_fn fn = VEC_alloc (tree, heap, dim + 1);
1419   unsigned i;
1420
1421   gcc_assert (dim > 0);
1422   VEC_quick_push (tree, fn, cst);
1423   for (i = 1; i < dim; i++)
1424     VEC_quick_push (tree, fn, integer_zero_node);
1425   VEC_quick_push (tree, fn, coef);
1426   return fn;
1427 }
1428
1429 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
1430    *OVERLAPS_B are initialized to the functions that describe the
1431    relation between the elements accessed twice by CHREC_A and
1432    CHREC_B.  For k >= 0, the following property is verified:
1433
1434    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1435
1436 static void
1437 analyze_ziv_subscript (tree chrec_a,
1438                        tree chrec_b,
1439                        conflict_function **overlaps_a,
1440                        conflict_function **overlaps_b,
1441                        tree *last_conflicts)
1442 {
1443   tree difference;
1444   dependence_stats.num_ziv++;
1445
1446   if (dump_file && (dump_flags & TDF_DETAILS))
1447     fprintf (dump_file, "(analyze_ziv_subscript \n");
1448
1449   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1450   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1451   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
1452
1453   switch (TREE_CODE (difference))
1454     {
1455     case INTEGER_CST:
1456       if (integer_zerop (difference))
1457         {
1458           /* The difference is equal to zero: the accessed index
1459              overlaps for each iteration in the loop.  */
1460           *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1461           *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1462           *last_conflicts = chrec_dont_know;
1463           dependence_stats.num_ziv_dependent++;
1464         }
1465       else
1466         {
1467           /* The accesses do not overlap.  */
1468           *overlaps_a = conflict_fn_no_dependence ();
1469           *overlaps_b = conflict_fn_no_dependence ();
1470           *last_conflicts = integer_zero_node;
1471           dependence_stats.num_ziv_independent++;
1472         }
1473       break;
1474
1475     default:
1476       /* We're not sure whether the indexes overlap.  For the moment,
1477          conservatively answer "don't know".  */
1478       if (dump_file && (dump_flags & TDF_DETAILS))
1479         fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
1480
1481       *overlaps_a = conflict_fn_not_known ();
1482       *overlaps_b = conflict_fn_not_known ();
1483       *last_conflicts = chrec_dont_know;
1484       dependence_stats.num_ziv_unimplemented++;
1485       break;
1486     }
1487
1488   if (dump_file && (dump_flags & TDF_DETAILS))
1489     fprintf (dump_file, ")\n");
1490 }
1491
1492 /* Sets NIT to the estimated number of executions of the statements in
1493    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
1494    large as the number of iterations.  If we have no reliable estimate,
1495    the function returns false, otherwise returns true.  */
1496
1497 bool
1498 estimated_loop_iterations (struct loop *loop, bool conservative,
1499                            double_int *nit)
1500 {
1501   estimate_numbers_of_iterations_loop (loop);
1502   if (conservative)
1503     {
1504       if (!loop->any_upper_bound)
1505         return false;
1506
1507       *nit = loop->nb_iterations_upper_bound;
1508     }
1509   else
1510     {
1511       if (!loop->any_estimate)
1512         return false;
1513
1514       *nit = loop->nb_iterations_estimate;
1515     }
1516
1517   return true;
1518 }
1519
1520 /* Similar to estimated_loop_iterations, but returns the estimate only
1521    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
1522    on the number of iterations of LOOP could not be derived, returns -1.  */
1523
1524 HOST_WIDE_INT
1525 estimated_loop_iterations_int (struct loop *loop, bool conservative)
1526 {
1527   double_int nit;
1528   HOST_WIDE_INT hwi_nit;
1529
1530   if (!estimated_loop_iterations (loop, conservative, &nit))
1531     return -1;
1532
1533   if (!double_int_fits_in_shwi_p (nit))
1534     return -1;
1535   hwi_nit = double_int_to_shwi (nit);
1536
1537   return hwi_nit < 0 ? -1 : hwi_nit;
1538 }
1539
1540 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
1541    and only if it fits to the int type.  If this is not the case, or the
1542    estimate on the number of iterations of LOOP could not be derived, returns
1543    chrec_dont_know.  */
1544
1545 static tree
1546 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
1547 {
1548   double_int nit;
1549   tree type;
1550
1551   if (!estimated_loop_iterations (loop, conservative, &nit))
1552     return chrec_dont_know;
1553
1554   type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
1555   if (!double_int_fits_to_tree_p (type, nit))
1556     return chrec_dont_know;
1557
1558   return double_int_to_tree (type, nit);
1559 }
1560
1561 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
1562    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
1563    *OVERLAPS_B are initialized to the functions that describe the
1564    relation between the elements accessed twice by CHREC_A and
1565    CHREC_B.  For k >= 0, the following property is verified:
1566
1567    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
1568
1569 static void
1570 analyze_siv_subscript_cst_affine (tree chrec_a,
1571                                   tree chrec_b,
1572                                   conflict_function **overlaps_a,
1573                                   conflict_function **overlaps_b,
1574                                   tree *last_conflicts)
1575 {
1576   bool value0, value1, value2;
1577   tree difference, tmp;
1578
1579   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
1580   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
1581   difference = chrec_fold_minus
1582     (integer_type_node, initial_condition (chrec_b), chrec_a);
1583
1584   if (!chrec_is_positive (initial_condition (difference), &value0))
1585     {
1586       if (dump_file && (dump_flags & TDF_DETAILS))
1587         fprintf (dump_file, "siv test failed: chrec is not positive.\n");
1588
1589       dependence_stats.num_siv_unimplemented++;
1590       *overlaps_a = conflict_fn_not_known ();
1591       *overlaps_b = conflict_fn_not_known ();
1592       *last_conflicts = chrec_dont_know;
1593       return;
1594     }
1595   else
1596     {
1597       if (value0 == false)
1598         {
1599           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
1600             {
1601               if (dump_file && (dump_flags & TDF_DETAILS))
1602                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1603
1604               *overlaps_a = conflict_fn_not_known ();
1605               *overlaps_b = conflict_fn_not_known ();
1606               *last_conflicts = chrec_dont_know;
1607               dependence_stats.num_siv_unimplemented++;
1608               return;
1609             }
1610           else
1611             {
1612               if (value1 == true)
1613                 {
1614                   /* Example:
1615                      chrec_a = 12
1616                      chrec_b = {10, +, 1}
1617                   */
1618
1619                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1620                     {
1621                       HOST_WIDE_INT numiter;
1622                       struct loop *loop = get_chrec_loop (chrec_b);
1623
1624                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1625                       tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
1626                                          fold_build1 (ABS_EXPR,
1627                                                       integer_type_node,
1628                                                       difference),
1629                                          CHREC_RIGHT (chrec_b));
1630                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1631                       *last_conflicts = integer_one_node;
1632
1633
1634                       /* Perform weak-zero siv test to see if overlap is
1635                          outside the loop bounds.  */
1636                       numiter = estimated_loop_iterations_int (loop, false);
1637
1638                       if (numiter >= 0
1639                           && compare_tree_int (tmp, numiter) > 0)
1640                         {
1641                           free_conflict_function (*overlaps_a);
1642                           free_conflict_function (*overlaps_b);
1643                           *overlaps_a = conflict_fn_no_dependence ();
1644                           *overlaps_b = conflict_fn_no_dependence ();
1645                           *last_conflicts = integer_zero_node;
1646                           dependence_stats.num_siv_independent++;
1647                           return;
1648                         }
1649                       dependence_stats.num_siv_dependent++;
1650                       return;
1651                     }
1652
1653                   /* When the step does not divide the difference, there are
1654                      no overlaps.  */
1655                   else
1656                     {
1657                       *overlaps_a = conflict_fn_no_dependence ();
1658                       *overlaps_b = conflict_fn_no_dependence ();
1659                       *last_conflicts = integer_zero_node;
1660                       dependence_stats.num_siv_independent++;
1661                       return;
1662                     }
1663                 }
1664
1665               else
1666                 {
1667                   /* Example:
1668                      chrec_a = 12
1669                      chrec_b = {10, +, -1}
1670
1671                      In this case, chrec_a will not overlap with chrec_b.  */
1672                   *overlaps_a = conflict_fn_no_dependence ();
1673                   *overlaps_b = conflict_fn_no_dependence ();
1674                   *last_conflicts = integer_zero_node;
1675                   dependence_stats.num_siv_independent++;
1676                   return;
1677                 }
1678             }
1679         }
1680       else
1681         {
1682           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
1683             {
1684               if (dump_file && (dump_flags & TDF_DETAILS))
1685                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
1686
1687               *overlaps_a = conflict_fn_not_known ();
1688               *overlaps_b = conflict_fn_not_known ();
1689               *last_conflicts = chrec_dont_know;
1690               dependence_stats.num_siv_unimplemented++;
1691               return;
1692             }
1693           else
1694             {
1695               if (value2 == false)
1696                 {
1697                   /* Example:
1698                      chrec_a = 3
1699                      chrec_b = {10, +, -1}
1700                   */
1701                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
1702                     {
1703                       HOST_WIDE_INT numiter;
1704                       struct loop *loop = get_chrec_loop (chrec_b);
1705
1706                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1707                       tmp = fold_build2 (EXACT_DIV_EXPR,
1708                                          integer_type_node, difference,
1709                                          CHREC_RIGHT (chrec_b));
1710                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
1711                       *last_conflicts = integer_one_node;
1712
1713                       /* Perform weak-zero siv test to see if overlap is
1714                          outside the loop bounds.  */
1715                       numiter = estimated_loop_iterations_int (loop, false);
1716
1717                       if (numiter >= 0
1718                           && compare_tree_int (tmp, numiter) > 0)
1719                         {
1720                           free_conflict_function (*overlaps_a);
1721                           free_conflict_function (*overlaps_b);
1722                           *overlaps_a = conflict_fn_no_dependence ();
1723                           *overlaps_b = conflict_fn_no_dependence ();
1724                           *last_conflicts = integer_zero_node;
1725                           dependence_stats.num_siv_independent++;
1726                           return;
1727                         }
1728                       dependence_stats.num_siv_dependent++;
1729                       return;
1730                     }
1731
1732                   /* When the step does not divide the difference, there
1733                      are no overlaps.  */
1734                   else
1735                     {
1736                       *overlaps_a = conflict_fn_no_dependence ();
1737                       *overlaps_b = conflict_fn_no_dependence ();
1738                       *last_conflicts = integer_zero_node;
1739                       dependence_stats.num_siv_independent++;
1740                       return;
1741                     }
1742                 }
1743               else
1744                 {
1745                   /* Example:
1746                      chrec_a = 3
1747                      chrec_b = {4, +, 1}
1748
1749                      In this case, chrec_a will not overlap with chrec_b.  */
1750                   *overlaps_a = conflict_fn_no_dependence ();
1751                   *overlaps_b = conflict_fn_no_dependence ();
1752                   *last_conflicts = integer_zero_node;
1753                   dependence_stats.num_siv_independent++;
1754                   return;
1755                 }
1756             }
1757         }
1758     }
1759 }
1760
1761 /* Helper recursive function for initializing the matrix A.  Returns
1762    the initial value of CHREC.  */
1763
1764 static int
1765 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1766 {
1767   gcc_assert (chrec);
1768
1769   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1770     return int_cst_value (chrec);
1771
1772   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1773   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1774 }
1775
1776 #define FLOOR_DIV(x,y) ((x) / (y))
1777
1778 /* Solves the special case of the Diophantine equation:
1779    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1780
1781    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
1782    number of iterations that loops X and Y run.  The overlaps will be
1783    constructed as evolutions in dimension DIM.  */
1784
1785 static void
1786 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1787                                          affine_fn *overlaps_a,
1788                                          affine_fn *overlaps_b,
1789                                          tree *last_conflicts, int dim)
1790 {
1791   if (((step_a > 0 && step_b > 0)
1792        || (step_a < 0 && step_b < 0)))
1793     {
1794       int step_overlaps_a, step_overlaps_b;
1795       int gcd_steps_a_b, last_conflict, tau2;
1796
1797       gcd_steps_a_b = gcd (step_a, step_b);
1798       step_overlaps_a = step_b / gcd_steps_a_b;
1799       step_overlaps_b = step_a / gcd_steps_a_b;
1800
1801       tau2 = FLOOR_DIV (niter, step_overlaps_a);
1802       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1803       last_conflict = tau2;
1804
1805       *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1806                                       build_int_cst (NULL_TREE,
1807                                                      step_overlaps_a));
1808       *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1809                                       build_int_cst (NULL_TREE,
1810                                                      step_overlaps_b));
1811       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1812     }
1813
1814   else
1815     {
1816       *overlaps_a = affine_fn_cst (integer_zero_node);
1817       *overlaps_b = affine_fn_cst (integer_zero_node);
1818       *last_conflicts = integer_zero_node;
1819     }
1820 }
1821
1822 /* Solves the special case of a Diophantine equation where CHREC_A is
1823    an affine bivariate function, and CHREC_B is an affine univariate
1824    function.  For example,
1825
1826    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1827
1828    has the following overlapping functions:
1829
1830    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1831    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1832    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1833
1834    FORNOW: This is a specialized implementation for a case occurring in
1835    a common benchmark.  Implement the general algorithm.  */
1836
1837 static void
1838 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1839                                       conflict_function **overlaps_a,
1840                                       conflict_function **overlaps_b,
1841                                       tree *last_conflicts)
1842 {
1843   bool xz_p, yz_p, xyz_p;
1844   int step_x, step_y, step_z;
1845   HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1846   affine_fn overlaps_a_xz, overlaps_b_xz;
1847   affine_fn overlaps_a_yz, overlaps_b_yz;
1848   affine_fn overlaps_a_xyz, overlaps_b_xyz;
1849   affine_fn ova1, ova2, ovb;
1850   tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1851
1852   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1853   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1854   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1855
1856   niter_x =
1857     estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
1858                                    false);
1859   niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
1860   niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
1861
1862   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1863     {
1864       if (dump_file && (dump_flags & TDF_DETAILS))
1865         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1866
1867       *overlaps_a = conflict_fn_not_known ();
1868       *overlaps_b = conflict_fn_not_known ();
1869       *last_conflicts = chrec_dont_know;
1870       return;
1871     }
1872
1873   niter = MIN (niter_x, niter_z);
1874   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1875                                            &overlaps_a_xz,
1876                                            &overlaps_b_xz,
1877                                            &last_conflicts_xz, 1);
1878   niter = MIN (niter_y, niter_z);
1879   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1880                                            &overlaps_a_yz,
1881                                            &overlaps_b_yz,
1882                                            &last_conflicts_yz, 2);
1883   niter = MIN (niter_x, niter_z);
1884   niter = MIN (niter_y, niter);
1885   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1886                                            &overlaps_a_xyz,
1887                                            &overlaps_b_xyz,
1888                                            &last_conflicts_xyz, 3);
1889
1890   xz_p = !integer_zerop (last_conflicts_xz);
1891   yz_p = !integer_zerop (last_conflicts_yz);
1892   xyz_p = !integer_zerop (last_conflicts_xyz);
1893
1894   if (xz_p || yz_p || xyz_p)
1895     {
1896       ova1 = affine_fn_cst (integer_zero_node);
1897       ova2 = affine_fn_cst (integer_zero_node);
1898       ovb = affine_fn_cst (integer_zero_node);
1899       if (xz_p)
1900         {
1901           affine_fn t0 = ova1;
1902           affine_fn t2 = ovb;
1903
1904           ova1 = affine_fn_plus (ova1, overlaps_a_xz);
1905           ovb = affine_fn_plus (ovb, overlaps_b_xz);
1906           affine_fn_free (t0);
1907           affine_fn_free (t2);
1908           *last_conflicts = last_conflicts_xz;
1909         }
1910       if (yz_p)
1911         {
1912           affine_fn t0 = ova2;
1913           affine_fn t2 = ovb;
1914
1915           ova2 = affine_fn_plus (ova2, overlaps_a_yz);
1916           ovb = affine_fn_plus (ovb, overlaps_b_yz);
1917           affine_fn_free (t0);
1918           affine_fn_free (t2);
1919           *last_conflicts = last_conflicts_yz;
1920         }
1921       if (xyz_p)
1922         {
1923           affine_fn t0 = ova1;
1924           affine_fn t2 = ova2;
1925           affine_fn t4 = ovb;
1926
1927           ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
1928           ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
1929           ovb = affine_fn_plus (ovb, overlaps_b_xyz);
1930           affine_fn_free (t0);
1931           affine_fn_free (t2);
1932           affine_fn_free (t4);
1933           *last_conflicts = last_conflicts_xyz;
1934         }
1935       *overlaps_a = conflict_fn (2, ova1, ova2);
1936       *overlaps_b = conflict_fn (1, ovb);
1937     }
1938   else
1939     {
1940       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1941       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1942       *last_conflicts = integer_zero_node;
1943     }
1944
1945   affine_fn_free (overlaps_a_xz);
1946   affine_fn_free (overlaps_b_xz);
1947   affine_fn_free (overlaps_a_yz);
1948   affine_fn_free (overlaps_b_yz);
1949   affine_fn_free (overlaps_a_xyz);
1950   affine_fn_free (overlaps_b_xyz);
1951 }
1952
1953 /* Determines the overlapping elements due to accesses CHREC_A and
1954    CHREC_B, that are affine functions.  This function cannot handle
1955    symbolic evolution functions, ie. when initial conditions are
1956    parameters, because it uses lambda matrices of integers.  */
1957
1958 static void
1959 analyze_subscript_affine_affine (tree chrec_a,
1960                                  tree chrec_b,
1961                                  conflict_function **overlaps_a,
1962                                  conflict_function **overlaps_b,
1963                                  tree *last_conflicts)
1964 {
1965   unsigned nb_vars_a, nb_vars_b, dim;
1966   HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
1967   HOST_WIDE_INT tau1, tau2;
1968   lambda_matrix A, U, S;
1969
1970   if (eq_evolutions_p (chrec_a, chrec_b))
1971     {
1972       /* The accessed index overlaps for each iteration in the
1973          loop.  */
1974       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
1975       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
1976       *last_conflicts = chrec_dont_know;
1977       return;
1978     }
1979   if (dump_file && (dump_flags & TDF_DETAILS))
1980     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
1981
1982   /* For determining the initial intersection, we have to solve a
1983      Diophantine equation.  This is the most time consuming part.
1984
1985      For answering to the question: "Is there a dependence?" we have
1986      to prove that there exists a solution to the Diophantine
1987      equation, and that the solution is in the iteration domain,
1988      i.e. the solution is positive or zero, and that the solution
1989      happens before the upper bound loop.nb_iterations.  Otherwise
1990      there is no dependence.  This function outputs a description of
1991      the iterations that hold the intersections.  */
1992
1993   nb_vars_a = nb_vars_in_chrec (chrec_a);
1994   nb_vars_b = nb_vars_in_chrec (chrec_b);
1995
1996   dim = nb_vars_a + nb_vars_b;
1997   U = lambda_matrix_new (dim, dim);
1998   A = lambda_matrix_new (dim, 1);
1999   S = lambda_matrix_new (dim, 1);
2000
2001   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2002   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2003   gamma = init_b - init_a;
2004
2005   /* Don't do all the hard work of solving the Diophantine equation
2006      when we already know the solution: for example,
2007      | {3, +, 1}_1
2008      | {3, +, 4}_2
2009      | gamma = 3 - 3 = 0.
2010      Then the first overlap occurs during the first iterations:
2011      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2012   */
2013   if (gamma == 0)
2014     {
2015       if (nb_vars_a == 1 && nb_vars_b == 1)
2016         {
2017           HOST_WIDE_INT step_a, step_b;
2018           HOST_WIDE_INT niter, niter_a, niter_b;
2019           affine_fn ova, ovb;
2020
2021           niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2022                                                    false);
2023           niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2024                                                    false);
2025           if (niter_a < 0 || niter_b < 0)
2026             {
2027               if (dump_file && (dump_flags & TDF_DETAILS))
2028                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2029               *overlaps_a = conflict_fn_not_known ();
2030               *overlaps_b = conflict_fn_not_known ();
2031               *last_conflicts = chrec_dont_know;
2032               goto end_analyze_subs_aa;
2033             }
2034
2035           niter = MIN (niter_a, niter_b);
2036
2037           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2038           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2039
2040           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2041                                                    &ova, &ovb,
2042                                                    last_conflicts, 1);
2043           *overlaps_a = conflict_fn (1, ova);
2044           *overlaps_b = conflict_fn (1, ovb);
2045         }
2046
2047       else if (nb_vars_a == 2 && nb_vars_b == 1)
2048         compute_overlap_steps_for_affine_1_2
2049           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2050
2051       else if (nb_vars_a == 1 && nb_vars_b == 2)
2052         compute_overlap_steps_for_affine_1_2
2053           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2054
2055       else
2056         {
2057           if (dump_file && (dump_flags & TDF_DETAILS))
2058             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2059           *overlaps_a = conflict_fn_not_known ();
2060           *overlaps_b = conflict_fn_not_known ();
2061           *last_conflicts = chrec_dont_know;
2062         }
2063       goto end_analyze_subs_aa;
2064     }
2065
2066   /* U.A = S */
2067   lambda_matrix_right_hermite (A, dim, 1, S, U);
2068
2069   if (S[0][0] < 0)
2070     {
2071       S[0][0] *= -1;
2072       lambda_matrix_row_negate (U, dim, 0);
2073     }
2074   gcd_alpha_beta = S[0][0];
2075
2076   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2077      but that is a quite strange case.  Instead of ICEing, answer
2078      don't know.  */
2079   if (gcd_alpha_beta == 0)
2080     {
2081       *overlaps_a = conflict_fn_not_known ();
2082       *overlaps_b = conflict_fn_not_known ();
2083       *last_conflicts = chrec_dont_know;
2084       goto end_analyze_subs_aa;
2085     }
2086
2087   /* The classic "gcd-test".  */
2088   if (!int_divides_p (gcd_alpha_beta, gamma))
2089     {
2090       /* The "gcd-test" has determined that there is no integer
2091          solution, i.e. there is no dependence.  */
2092       *overlaps_a = conflict_fn_no_dependence ();
2093       *overlaps_b = conflict_fn_no_dependence ();
2094       *last_conflicts = integer_zero_node;
2095     }
2096
2097   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2098   else if (nb_vars_a == 1 && nb_vars_b == 1)
2099     {
2100       /* Both functions should have the same evolution sign.  */
2101       if (((A[0][0] > 0 && -A[1][0] > 0)
2102            || (A[0][0] < 0 && -A[1][0] < 0)))
2103         {
2104           /* The solutions are given by:
2105              |
2106              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2107              |                           [u21 u22]    [y0]
2108
2109              For a given integer t.  Using the following variables,
2110
2111              | i0 = u11 * gamma / gcd_alpha_beta
2112              | j0 = u12 * gamma / gcd_alpha_beta
2113              | i1 = u21
2114              | j1 = u22
2115
2116              the solutions are:
2117
2118              | x0 = i0 + i1 * t,
2119              | y0 = j0 + j1 * t.  */
2120
2121           HOST_WIDE_INT i0, j0, i1, j1;
2122
2123           /* X0 and Y0 are the first iterations for which there is a
2124              dependence.  X0, Y0 are two solutions of the Diophantine
2125              equation: chrec_a (X0) = chrec_b (Y0).  */
2126           HOST_WIDE_INT x0, y0;
2127           HOST_WIDE_INT niter, niter_a, niter_b;
2128
2129           niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2130                                                    false);
2131           niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2132                                                    false);
2133
2134           if (niter_a < 0 || niter_b < 0)
2135             {
2136               if (dump_file && (dump_flags & TDF_DETAILS))
2137                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2138               *overlaps_a = conflict_fn_not_known ();
2139               *overlaps_b = conflict_fn_not_known ();
2140               *last_conflicts = chrec_dont_know;
2141               goto end_analyze_subs_aa;
2142             }
2143
2144           niter = MIN (niter_a, niter_b);
2145
2146           i0 = U[0][0] * gamma / gcd_alpha_beta;
2147           j0 = U[0][1] * gamma / gcd_alpha_beta;
2148           i1 = U[1][0];
2149           j1 = U[1][1];
2150
2151           if ((i1 == 0 && i0 < 0)
2152               || (j1 == 0 && j0 < 0))
2153             {
2154               /* There is no solution.
2155                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2156                  falls in here, but for the moment we don't look at the
2157                  upper bound of the iteration domain.  */
2158               *overlaps_a = conflict_fn_no_dependence ();
2159               *overlaps_b = conflict_fn_no_dependence ();
2160               *last_conflicts = integer_zero_node;
2161             }
2162
2163           else
2164             {
2165               if (i1 > 0)
2166                 {
2167                   tau1 = CEIL (-i0, i1);
2168                   tau2 = FLOOR_DIV (niter - i0, i1);
2169
2170                   if (j1 > 0)
2171                     {
2172                       int last_conflict, min_multiple;
2173                       tau1 = MAX (tau1, CEIL (-j0, j1));
2174                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2175
2176                       x0 = i1 * tau1 + i0;
2177                       y0 = j1 * tau1 + j0;
2178
2179                       /* At this point (x0, y0) is one of the
2180                          solutions to the Diophantine equation.  The
2181                          next step has to compute the smallest
2182                          positive solution: the first conflicts.  */
2183                       min_multiple = MIN (x0 / i1, y0 / j1);
2184                       x0 -= i1 * min_multiple;
2185                       y0 -= j1 * min_multiple;
2186
2187                       tau1 = (x0 - i0)/i1;
2188                       last_conflict = tau2 - tau1;
2189
2190                       /* If the overlap occurs outside of the bounds of the
2191                          loop, there is no dependence.  */
2192                       if (x0 > niter || y0  > niter)
2193                         {
2194                           *overlaps_a = conflict_fn_no_dependence ();
2195                           *overlaps_b = conflict_fn_no_dependence ();
2196                           *last_conflicts = integer_zero_node;
2197                         }
2198                       else
2199                         {
2200                           *overlaps_a
2201                             = conflict_fn (1,
2202                                 affine_fn_univar (build_int_cst (NULL_TREE, x0),
2203                                                   1,
2204                                                   build_int_cst (NULL_TREE, i1)));
2205                           *overlaps_b
2206                             = conflict_fn (1,
2207                                 affine_fn_univar (build_int_cst (NULL_TREE, y0),
2208                                                   1,
2209                                                   build_int_cst (NULL_TREE, j1)));
2210                           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2211                         }
2212                     }
2213                   else
2214                     {
2215                       /* FIXME: For the moment, the upper bound of the
2216                          iteration domain for j is not checked.  */
2217                       if (dump_file && (dump_flags & TDF_DETAILS))
2218                         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2219                       *overlaps_a = conflict_fn_not_known ();
2220                       *overlaps_b = conflict_fn_not_known ();
2221                       *last_conflicts = chrec_dont_know;
2222                     }
2223                 }
2224
2225               else
2226                 {
2227                   /* FIXME: For the moment, the upper bound of the
2228                      iteration domain for i is not checked.  */
2229                   if (dump_file && (dump_flags & TDF_DETAILS))
2230                     fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2231                   *overlaps_a = conflict_fn_not_known ();
2232                   *overlaps_b = conflict_fn_not_known ();
2233                   *last_conflicts = chrec_dont_know;
2234                 }
2235             }
2236         }
2237       else
2238         {
2239           if (dump_file && (dump_flags & TDF_DETAILS))
2240             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2241           *overlaps_a = conflict_fn_not_known ();
2242           *overlaps_b = conflict_fn_not_known ();
2243           *last_conflicts = chrec_dont_know;
2244         }
2245     }
2246
2247   else
2248     {
2249       if (dump_file && (dump_flags & TDF_DETAILS))
2250         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2251       *overlaps_a = conflict_fn_not_known ();
2252       *overlaps_b = conflict_fn_not_known ();
2253       *last_conflicts = chrec_dont_know;
2254     }
2255
2256 end_analyze_subs_aa:
2257   if (dump_file && (dump_flags & TDF_DETAILS))
2258     {
2259       fprintf (dump_file, "  (overlaps_a = ");
2260       dump_conflict_function (dump_file, *overlaps_a);
2261       fprintf (dump_file, ")\n  (overlaps_b = ");
2262       dump_conflict_function (dump_file, *overlaps_b);
2263       fprintf (dump_file, ")\n");
2264       fprintf (dump_file, ")\n");
2265     }
2266 }
2267
2268 /* Returns true when analyze_subscript_affine_affine can be used for
2269    determining the dependence relation between chrec_a and chrec_b,
2270    that contain symbols.  This function modifies chrec_a and chrec_b
2271    such that the analysis result is the same, and such that they don't
2272    contain symbols, and then can safely be passed to the analyzer.
2273
2274    Example: The analysis of the following tuples of evolutions produce
2275    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2276    vs. {0, +, 1}_1
2277
2278    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2279    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2280 */
2281
2282 static bool
2283 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2284 {
2285   tree diff, type, left_a, left_b, right_b;
2286
2287   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2288       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2289     /* FIXME: For the moment not handled.  Might be refined later.  */
2290     return false;
2291
2292   type = chrec_type (*chrec_a);
2293   left_a = CHREC_LEFT (*chrec_a);
2294   left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2295   diff = chrec_fold_minus (type, left_a, left_b);
2296
2297   if (!evolution_function_is_constant_p (diff))
2298     return false;
2299
2300   if (dump_file && (dump_flags & TDF_DETAILS))
2301     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2302
2303   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2304                                      diff, CHREC_RIGHT (*chrec_a));
2305   right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
2306   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2307                                      build_int_cst (type, 0),
2308                                      right_b);
2309   return true;
2310 }
2311
2312 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
2313    *OVERLAPS_B are initialized to the functions that describe the
2314    relation between the elements accessed twice by CHREC_A and
2315    CHREC_B.  For k >= 0, the following property is verified:
2316
2317    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2318
2319 static void
2320 analyze_siv_subscript (tree chrec_a,
2321                        tree chrec_b,
2322                        conflict_function **overlaps_a,
2323                        conflict_function **overlaps_b,
2324                        tree *last_conflicts)
2325 {
2326   dependence_stats.num_siv++;
2327
2328   if (dump_file && (dump_flags & TDF_DETAILS))
2329     fprintf (dump_file, "(analyze_siv_subscript \n");
2330
2331   if (evolution_function_is_constant_p (chrec_a)
2332       && evolution_function_is_affine_p (chrec_b))
2333     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2334                                       overlaps_a, overlaps_b, last_conflicts);
2335
2336   else if (evolution_function_is_affine_p (chrec_a)
2337            && evolution_function_is_constant_p (chrec_b))
2338     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2339                                       overlaps_b, overlaps_a, last_conflicts);
2340
2341   else if (evolution_function_is_affine_p (chrec_a)
2342            && evolution_function_is_affine_p (chrec_b))
2343     {
2344       if (!chrec_contains_symbols (chrec_a)
2345           && !chrec_contains_symbols (chrec_b))
2346         {
2347           analyze_subscript_affine_affine (chrec_a, chrec_b,
2348                                            overlaps_a, overlaps_b,
2349                                            last_conflicts);
2350
2351           if (CF_NOT_KNOWN_P (*overlaps_a)
2352               || CF_NOT_KNOWN_P (*overlaps_b))
2353             dependence_stats.num_siv_unimplemented++;
2354           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2355                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2356             dependence_stats.num_siv_independent++;
2357           else
2358             dependence_stats.num_siv_dependent++;
2359         }
2360       else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2361                                                         &chrec_b))
2362         {
2363           analyze_subscript_affine_affine (chrec_a, chrec_b,
2364                                            overlaps_a, overlaps_b,
2365                                            last_conflicts);
2366
2367           if (CF_NOT_KNOWN_P (*overlaps_a)
2368               || CF_NOT_KNOWN_P (*overlaps_b))
2369             dependence_stats.num_siv_unimplemented++;
2370           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2371                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2372             dependence_stats.num_siv_independent++;
2373           else
2374             dependence_stats.num_siv_dependent++;
2375         }
2376       else
2377         goto siv_subscript_dontknow;
2378     }
2379
2380   else
2381     {
2382     siv_subscript_dontknow:;
2383       if (dump_file && (dump_flags & TDF_DETAILS))
2384         fprintf (dump_file, "siv test failed: unimplemented.\n");
2385       *overlaps_a = conflict_fn_not_known ();
2386       *overlaps_b = conflict_fn_not_known ();
2387       *last_conflicts = chrec_dont_know;
2388       dependence_stats.num_siv_unimplemented++;
2389     }
2390
2391   if (dump_file && (dump_flags & TDF_DETAILS))
2392     fprintf (dump_file, ")\n");
2393 }
2394
2395 /* Returns false if we can prove that the greatest common divisor of the steps
2396    of CHREC does not divide CST, false otherwise.  */
2397
2398 static bool
2399 gcd_of_steps_may_divide_p (tree chrec, tree cst)
2400 {
2401   HOST_WIDE_INT cd = 0, val;
2402   tree step;
2403
2404   if (!host_integerp (cst, 0))
2405     return true;
2406   val = tree_low_cst (cst, 0);
2407
2408   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2409     {
2410       step = CHREC_RIGHT (chrec);
2411       if (!host_integerp (step, 0))
2412         return true;
2413       cd = gcd (cd, tree_low_cst (step, 0));
2414       chrec = CHREC_LEFT (chrec);
2415     }
2416
2417   return val % cd == 0;
2418 }
2419
2420 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2421    LOOP_NEST.  *OVERLAPS_A and *OVERLAPS_B are initialized to the
2422    functions that describe the relation between the elements accessed
2423    twice by CHREC_A and CHREC_B.  For k >= 0, the following property
2424    is verified:
2425
2426    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2427
2428 static void
2429 analyze_miv_subscript (tree chrec_a,
2430                        tree chrec_b,
2431                        conflict_function **overlaps_a,
2432                        conflict_function **overlaps_b,
2433                        tree *last_conflicts,
2434                        struct loop *loop_nest)
2435 {
2436   /* FIXME:  This is a MIV subscript, not yet handled.
2437      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2438      (A[i] vs. A[j]).
2439
2440      In the SIV test we had to solve a Diophantine equation with two
2441      variables.  In the MIV case we have to solve a Diophantine
2442      equation with 2*n variables (if the subscript uses n IVs).
2443   */
2444   tree difference;
2445   dependence_stats.num_miv++;
2446   if (dump_file && (dump_flags & TDF_DETAILS))
2447     fprintf (dump_file, "(analyze_miv_subscript \n");
2448
2449   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2450   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2451   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2452
2453   if (eq_evolutions_p (chrec_a, chrec_b))
2454     {
2455       /* Access functions are the same: all the elements are accessed
2456          in the same order.  */
2457       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2458       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2459       *last_conflicts = estimated_loop_iterations_tree
2460                                 (get_chrec_loop (chrec_a), true);
2461       dependence_stats.num_miv_dependent++;
2462     }
2463
2464   else if (evolution_function_is_constant_p (difference)
2465            /* For the moment, the following is verified:
2466               evolution_function_is_affine_multivariate_p (chrec_a,
2467               loop_nest->num) */
2468            && !gcd_of_steps_may_divide_p (chrec_a, difference))
2469     {
2470       /* testsuite/.../ssa-chrec-33.c
2471          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
2472
2473          The difference is 1, and all the evolution steps are multiples
2474          of 2, consequently there are no overlapping elements.  */
2475       *overlaps_a = conflict_fn_no_dependence ();
2476       *overlaps_b = conflict_fn_no_dependence ();
2477       *last_conflicts = integer_zero_node;
2478       dependence_stats.num_miv_independent++;
2479     }
2480
2481   else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2482            && !chrec_contains_symbols (chrec_a)
2483            && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2484            && !chrec_contains_symbols (chrec_b))
2485     {
2486       /* testsuite/.../ssa-chrec-35.c
2487          {0, +, 1}_2  vs.  {0, +, 1}_3
2488          the overlapping elements are respectively located at iterations:
2489          {0, +, 1}_x and {0, +, 1}_x,
2490          in other words, we have the equality:
2491          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2492
2493          Other examples:
2494          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2495          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2496
2497          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2498          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2499       */
2500       analyze_subscript_affine_affine (chrec_a, chrec_b,
2501                                        overlaps_a, overlaps_b, last_conflicts);
2502
2503       if (CF_NOT_KNOWN_P (*overlaps_a)
2504           || CF_NOT_KNOWN_P (*overlaps_b))
2505         dependence_stats.num_miv_unimplemented++;
2506       else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2507                || CF_NO_DEPENDENCE_P (*overlaps_b))
2508         dependence_stats.num_miv_independent++;
2509       else
2510         dependence_stats.num_miv_dependent++;
2511     }
2512
2513   else
2514     {
2515       /* When the analysis is too difficult, answer "don't know".  */
2516       if (dump_file && (dump_flags & TDF_DETAILS))
2517         fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2518
2519       *overlaps_a = conflict_fn_not_known ();
2520       *overlaps_b = conflict_fn_not_known ();
2521       *last_conflicts = chrec_dont_know;
2522       dependence_stats.num_miv_unimplemented++;
2523     }
2524
2525   if (dump_file && (dump_flags & TDF_DETAILS))
2526     fprintf (dump_file, ")\n");
2527 }
2528
2529 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2530    with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
2531    OVERLAP_ITERATIONS_B are initialized with two functions that
2532    describe the iterations that contain conflicting elements.
2533
2534    Remark: For an integer k >= 0, the following equality is true:
2535
2536    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2537 */
2538
2539 static void
2540 analyze_overlapping_iterations (tree chrec_a,
2541                                 tree chrec_b,
2542                                 conflict_function **overlap_iterations_a,
2543                                 conflict_function **overlap_iterations_b,
2544                                 tree *last_conflicts, struct loop *loop_nest)
2545 {
2546   unsigned int lnn = loop_nest->num;
2547
2548   dependence_stats.num_subscript_tests++;
2549
2550   if (dump_file && (dump_flags & TDF_DETAILS))
2551     {
2552       fprintf (dump_file, "(analyze_overlapping_iterations \n");
2553       fprintf (dump_file, "  (chrec_a = ");
2554       print_generic_expr (dump_file, chrec_a, 0);
2555       fprintf (dump_file, ")\n  (chrec_b = ");
2556       print_generic_expr (dump_file, chrec_b, 0);
2557       fprintf (dump_file, ")\n");
2558     }
2559
2560   if (chrec_a == NULL_TREE
2561       || chrec_b == NULL_TREE
2562       || chrec_contains_undetermined (chrec_a)
2563       || chrec_contains_undetermined (chrec_b))
2564     {
2565       dependence_stats.num_subscript_undetermined++;
2566
2567       *overlap_iterations_a = conflict_fn_not_known ();
2568       *overlap_iterations_b = conflict_fn_not_known ();
2569     }
2570
2571   /* If they are the same chrec, and are affine, they overlap
2572      on every iteration.  */
2573   else if (eq_evolutions_p (chrec_a, chrec_b)
2574            && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
2575     {
2576       dependence_stats.num_same_subscript_function++;
2577       *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2578       *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2579       *last_conflicts = chrec_dont_know;
2580     }
2581
2582   /* If they aren't the same, and aren't affine, we can't do anything
2583      yet. */
2584   else if ((chrec_contains_symbols (chrec_a)
2585             || chrec_contains_symbols (chrec_b))
2586            && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2587                || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2588     {
2589       dependence_stats.num_subscript_undetermined++;
2590       *overlap_iterations_a = conflict_fn_not_known ();
2591       *overlap_iterations_b = conflict_fn_not_known ();
2592     }
2593
2594   else if (ziv_subscript_p (chrec_a, chrec_b))
2595     analyze_ziv_subscript (chrec_a, chrec_b,
2596                            overlap_iterations_a, overlap_iterations_b,
2597                            last_conflicts);
2598
2599   else if (siv_subscript_p (chrec_a, chrec_b))
2600     analyze_siv_subscript (chrec_a, chrec_b,
2601                            overlap_iterations_a, overlap_iterations_b,
2602                            last_conflicts);
2603
2604   else
2605     analyze_miv_subscript (chrec_a, chrec_b,
2606                            overlap_iterations_a, overlap_iterations_b,
2607                            last_conflicts, loop_nest);
2608
2609   if (dump_file && (dump_flags & TDF_DETAILS))
2610     {
2611       fprintf (dump_file, "  (overlap_iterations_a = ");
2612       dump_conflict_function (dump_file, *overlap_iterations_a);
2613       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2614       dump_conflict_function (dump_file, *overlap_iterations_b);
2615       fprintf (dump_file, ")\n");
2616       fprintf (dump_file, ")\n");
2617     }
2618 }
2619
2620 /* Helper function for uniquely inserting distance vectors.  */
2621
2622 static void
2623 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2624 {
2625   unsigned i;
2626   lambda_vector v;
2627
2628   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2629     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2630       return;
2631
2632   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2633 }
2634
2635 /* Helper function for uniquely inserting direction vectors.  */
2636
2637 static void
2638 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2639 {
2640   unsigned i;
2641   lambda_vector v;
2642
2643   for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2644     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2645       return;
2646
2647   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2648 }
2649
2650 /* Add a distance of 1 on all the loops outer than INDEX.  If we
2651    haven't yet determined a distance for this outer loop, push a new
2652    distance vector composed of the previous distance, and a distance
2653    of 1 for this outer loop.  Example:
2654
2655    | loop_1
2656    |   loop_2
2657    |     A[10]
2658    |   endloop_2
2659    | endloop_1
2660
2661    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
2662    save (0, 1), then we have to save (1, 0).  */
2663
2664 static void
2665 add_outer_distances (struct data_dependence_relation *ddr,
2666                      lambda_vector dist_v, int index)
2667 {
2668   /* For each outer loop where init_v is not set, the accesses are
2669      in dependence of distance 1 in the loop.  */
2670   while (--index >= 0)
2671     {
2672       lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2673       lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2674       save_v[index] = 1;
2675       save_dist_v (ddr, save_v);
2676     }
2677 }
2678
2679 /* Return false when fail to represent the data dependence as a
2680    distance vector.  INIT_B is set to true when a component has been
2681    added to the distance vector DIST_V.  INDEX_CARRY is then set to
2682    the index in DIST_V that carries the dependence.  */
2683
2684 static bool
2685 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2686                              struct data_reference *ddr_a,
2687                              struct data_reference *ddr_b,
2688                              lambda_vector dist_v, bool *init_b,
2689                              int *index_carry)
2690 {
2691   unsigned i;
2692   lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2693
2694   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2695     {
2696       tree access_fn_a, access_fn_b;
2697       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2698
2699       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2700         {
2701           non_affine_dependence_relation (ddr);
2702           return false;
2703         }
2704
2705       access_fn_a = DR_ACCESS_FN (ddr_a, i);
2706       access_fn_b = DR_ACCESS_FN (ddr_b, i);
2707
2708       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2709           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2710         {
2711           int dist, index;
2712           int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2713                                             DDR_LOOP_NEST (ddr));
2714           int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2715                                             DDR_LOOP_NEST (ddr));
2716
2717           /* The dependence is carried by the outermost loop.  Example:
2718              | loop_1
2719              |   A[{4, +, 1}_1]
2720              |   loop_2
2721              |     A[{5, +, 1}_2]
2722              |   endloop_2
2723              | endloop_1
2724              In this case, the dependence is carried by loop_1.  */
2725           index = index_a < index_b ? index_a : index_b;
2726           *index_carry = MIN (index, *index_carry);
2727
2728           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2729             {
2730               non_affine_dependence_relation (ddr);
2731               return false;
2732             }
2733
2734           dist = int_cst_value (SUB_DISTANCE (subscript));
2735
2736           /* This is the subscript coupling test.  If we have already
2737              recorded a distance for this loop (a distance coming from
2738              another subscript), it should be the same.  For example,
2739              in the following code, there is no dependence:
2740
2741              | loop i = 0, N, 1
2742              |   T[i+1][i] = ...
2743              |   ... = T[i][i]
2744              | endloop
2745           */
2746           if (init_v[index] != 0 && dist_v[index] != dist)
2747             {
2748               finalize_ddr_dependent (ddr, chrec_known);
2749               return false;
2750             }
2751
2752           dist_v[index] = dist;
2753           init_v[index] = 1;
2754           *init_b = true;
2755         }
2756       else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2757         {
2758           /* This can be for example an affine vs. constant dependence
2759              (T[i] vs. T[3]) that is not an affine dependence and is
2760              not representable as a distance vector.  */
2761           non_affine_dependence_relation (ddr);
2762           return false;
2763         }
2764     }
2765
2766   return true;
2767 }
2768
2769 /* Return true when the DDR contains two data references that have the
2770    same access functions.  */
2771
2772 static bool
2773 same_access_functions (struct data_dependence_relation *ddr)
2774 {
2775   unsigned i;
2776
2777   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2778     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
2779                           DR_ACCESS_FN (DDR_B (ddr), i)))
2780       return false;
2781
2782   return true;
2783 }
2784
2785 /* Return true when the DDR contains only constant access functions.  */
2786
2787 static bool
2788 constant_access_functions (struct data_dependence_relation *ddr)
2789 {
2790   unsigned i;
2791
2792   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2793     if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2794         || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2795       return false;
2796
2797   return true;
2798 }
2799
2800
2801 /* Helper function for the case where DDR_A and DDR_B are the same
2802    multivariate access function.  */
2803
2804 static void
2805 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2806 {
2807   int x_1, x_2;
2808   tree c_1 = CHREC_LEFT (c_2);
2809   tree c_0 = CHREC_LEFT (c_1);
2810   lambda_vector dist_v;
2811   int v1, v2, cd;
2812
2813   /* Polynomials with more than 2 variables are not handled yet.  */
2814   if (TREE_CODE (c_0) != INTEGER_CST)
2815     {
2816       DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2817       return;
2818     }
2819
2820   x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2821   x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2822
2823   /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
2824   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2825   v1 = int_cst_value (CHREC_RIGHT (c_1));
2826   v2 = int_cst_value (CHREC_RIGHT (c_2));
2827   cd = gcd (v1, v2);
2828   v1 /= cd;
2829   v2 /= cd;
2830
2831   if (v2 < 0)
2832     {
2833       v2 = -v2;
2834       v1 = -v1;
2835     }
2836
2837   dist_v[x_1] = v2;
2838   dist_v[x_2] = -v1;
2839   save_dist_v (ddr, dist_v);
2840
2841   add_outer_distances (ddr, dist_v, x_1);
2842 }
2843
2844 /* Helper function for the case where DDR_A and DDR_B are the same
2845    access functions.  */
2846
2847 static void
2848 add_other_self_distances (struct data_dependence_relation *ddr)
2849 {
2850   lambda_vector dist_v;
2851   unsigned i;
2852   int index_carry = DDR_NB_LOOPS (ddr);
2853
2854   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2855     {
2856       tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2857
2858       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2859         {
2860           if (!evolution_function_is_univariate_p (access_fun))
2861             {
2862               if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2863                 {
2864                   DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2865                   return;
2866                 }
2867
2868               add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
2869               return;
2870             }
2871
2872           index_carry = MIN (index_carry,
2873                              index_in_loop_nest (CHREC_VARIABLE (access_fun),
2874                                                  DDR_LOOP_NEST (ddr)));
2875         }
2876     }
2877
2878   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2879   add_outer_distances (ddr, dist_v, index_carry);
2880 }
2881
2882 static void
2883 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2884 {
2885   lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2886
2887   dist_v[DDR_INNER_LOOP (ddr)] = 1;
2888   save_dist_v (ddr, dist_v);
2889 }
2890
2891 /* Adds a unit distance vector to DDR when there is a 0 overlap.  This
2892    is the case for example when access functions are the same and
2893    equal to a constant, as in:
2894
2895    | loop_1
2896    |   A[3] = ...
2897    |   ... = A[3]
2898    | endloop_1
2899
2900    in which case the distance vectors are (0) and (1).  */
2901
2902 static void
2903 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2904 {
2905   unsigned i, j;
2906
2907   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2908     {
2909       subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2910       conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2911       conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2912
2913       for (j = 0; j < ca->n; j++)
2914         if (affine_function_zero_p (ca->fns[j]))
2915           {
2916             insert_innermost_unit_dist_vector (ddr);
2917             return;
2918           }
2919
2920       for (j = 0; j < cb->n; j++)
2921         if (affine_function_zero_p (cb->fns[j]))
2922           {
2923             insert_innermost_unit_dist_vector (ddr);
2924             return;
2925           }
2926     }
2927 }
2928
2929 /* Compute the classic per loop distance vector.  DDR is the data
2930    dependence relation to build a vector from.  Return false when fail
2931    to represent the data dependence as a distance vector.  */
2932
2933 static bool
2934 build_classic_dist_vector (struct data_dependence_relation *ddr,
2935                            struct loop *loop_nest)
2936 {
2937   bool init_b = false;
2938   int index_carry = DDR_NB_LOOPS (ddr);
2939   lambda_vector dist_v;
2940
2941   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
2942     return true;
2943
2944   if (same_access_functions (ddr))
2945     {
2946       /* Save the 0 vector.  */
2947       dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2948       save_dist_v (ddr, dist_v);
2949
2950       if (constant_access_functions (ddr))
2951         add_distance_for_zero_overlaps (ddr);
2952
2953       if (DDR_NB_LOOPS (ddr) > 1)
2954         add_other_self_distances (ddr);
2955
2956       return true;
2957     }
2958
2959   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2960   if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
2961                                     dist_v, &init_b, &index_carry))
2962     return false;
2963
2964   /* Save the distance vector if we initialized one.  */
2965   if (init_b)
2966     {
2967       /* Verify a basic constraint: classic distance vectors should
2968          always be lexicographically positive.
2969
2970          Data references are collected in the order of execution of
2971          the program, thus for the following loop
2972
2973          | for (i = 1; i < 100; i++)
2974          |   for (j = 1; j < 100; j++)
2975          |     {
2976          |       t = T[j+1][i-1];  // A
2977          |       T[j][i] = t + 2;  // B
2978          |     }
2979
2980          references are collected following the direction of the wind:
2981          A then B.  The data dependence tests are performed also
2982          following this order, such that we're looking at the distance
2983          separating the elements accessed by A from the elements later
2984          accessed by B.  But in this example, the distance returned by
2985          test_dep (A, B) is lexicographically negative (-1, 1), that
2986          means that the access A occurs later than B with respect to
2987          the outer loop, ie. we're actually looking upwind.  In this
2988          case we solve test_dep (B, A) looking downwind to the
2989          lexicographically positive solution, that returns the
2990          distance vector (1, -1).  */
2991       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
2992         {
2993           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2994           subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2995                                          loop_nest);
2996           compute_subscript_distance (ddr);
2997           build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
2998                                        save_v, &init_b, &index_carry);
2999           save_dist_v (ddr, save_v);
3000           DDR_REVERSED_P (ddr) = true;
3001
3002           /* In this case there is a dependence forward for all the
3003              outer loops:
3004
3005              | for (k = 1; k < 100; k++)
3006              |  for (i = 1; i < 100; i++)
3007              |   for (j = 1; j < 100; j++)
3008              |     {
3009              |       t = T[j+1][i-1];  // A
3010              |       T[j][i] = t + 2;  // B
3011              |     }
3012
3013              the vectors are:
3014              (0,  1, -1)
3015              (1,  1, -1)
3016              (1, -1,  1)
3017           */
3018           if (DDR_NB_LOOPS (ddr) > 1)
3019             {
3020               add_outer_distances (ddr, save_v, index_carry);
3021               add_outer_distances (ddr, dist_v, index_carry);
3022             }
3023         }
3024       else
3025         {
3026           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3027           lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3028           save_dist_v (ddr, save_v);
3029
3030           if (DDR_NB_LOOPS (ddr) > 1)
3031             {
3032               lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3033
3034               subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3035                                              loop_nest);
3036               compute_subscript_distance (ddr);
3037               build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3038                                            opposite_v, &init_b, &index_carry);
3039
3040               add_outer_distances (ddr, dist_v, index_carry);
3041               add_outer_distances (ddr, opposite_v, index_carry);
3042             }
3043         }
3044     }
3045   else
3046     {
3047       /* There is a distance of 1 on all the outer loops: Example:
3048          there is a dependence of distance 1 on loop_1 for the array A.
3049
3050          | loop_1
3051          |   A[5] = ...
3052          | endloop
3053       */
3054       add_outer_distances (ddr, dist_v,
3055                            lambda_vector_first_nz (dist_v,
3056                                                    DDR_NB_LOOPS (ddr), 0));
3057     }
3058
3059   if (dump_file && (dump_flags & TDF_DETAILS))
3060     {
3061       unsigned i;
3062
3063       fprintf (dump_file, "(build_classic_dist_vector\n");
3064       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3065         {
3066           fprintf (dump_file, "  dist_vector = (");
3067           print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3068                                DDR_NB_LOOPS (ddr));
3069           fprintf (dump_file, "  )\n");
3070         }
3071       fprintf (dump_file, ")\n");
3072     }
3073
3074   return true;
3075 }
3076
3077 /* Return the direction for a given distance.
3078    FIXME: Computing dir this way is suboptimal, since dir can catch
3079    cases that dist is unable to represent.  */
3080
3081 static inline enum data_dependence_direction
3082 dir_from_dist (int dist)
3083 {
3084   if (dist > 0)
3085     return dir_positive;
3086   else if (dist < 0)
3087     return dir_negative;
3088   else
3089     return dir_equal;
3090 }
3091
3092 /* Compute the classic per loop direction vector.  DDR is the data
3093    dependence relation to build a vector from.  */
3094
3095 static void
3096 build_classic_dir_vector (struct data_dependence_relation *ddr)
3097 {
3098   unsigned i, j;
3099   lambda_vector dist_v;
3100
3101   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3102     {
3103       lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3104
3105       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3106         dir_v[j] = dir_from_dist (dist_v[j]);
3107
3108       save_dir_v (ddr, dir_v);
3109     }
3110 }
3111
3112 /* Helper function.  Returns true when there is a dependence between
3113    data references DRA and DRB.  */
3114
3115 static bool
3116 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3117                                struct data_reference *dra,
3118                                struct data_reference *drb,
3119                                struct loop *loop_nest)
3120 {
3121   unsigned int i;
3122   tree last_conflicts;
3123   struct subscript *subscript;
3124
3125   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3126        i++)
3127     {
3128       conflict_function *overlaps_a, *overlaps_b;
3129
3130       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3131                                       DR_ACCESS_FN (drb, i),
3132                                       &overlaps_a, &overlaps_b,
3133                                       &last_conflicts, loop_nest);
3134
3135       if (CF_NOT_KNOWN_P (overlaps_a)
3136           || CF_NOT_KNOWN_P (overlaps_b))
3137         {
3138           finalize_ddr_dependent (ddr, chrec_dont_know);
3139           dependence_stats.num_dependence_undetermined++;
3140           free_conflict_function (overlaps_a);
3141           free_conflict_function (overlaps_b);
3142           return false;
3143         }
3144
3145       else if (CF_NO_DEPENDENCE_P (overlaps_a)
3146                || CF_NO_DEPENDENCE_P (overlaps_b))
3147         {
3148           finalize_ddr_dependent (ddr, chrec_known);
3149           dependence_stats.num_dependence_independent++;
3150           free_conflict_function (overlaps_a);
3151           free_conflict_function (overlaps_b);
3152           return false;
3153         }
3154
3155       else
3156         {
3157           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3158           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3159           SUB_LAST_CONFLICT (subscript) = last_conflicts;
3160         }
3161     }
3162
3163   return true;
3164 }
3165
3166 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR.  */
3167
3168 static void
3169 subscript_dependence_tester (struct data_dependence_relation *ddr,
3170                              struct loop *loop_nest)
3171 {
3172
3173   if (dump_file && (dump_flags & TDF_DETAILS))
3174     fprintf (dump_file, "(subscript_dependence_tester \n");
3175
3176   if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3177     dependence_stats.num_dependence_dependent++;
3178
3179   compute_subscript_distance (ddr);
3180   if (build_classic_dist_vector (ddr, loop_nest))
3181     build_classic_dir_vector (ddr);
3182
3183   if (dump_file && (dump_flags & TDF_DETAILS))
3184     fprintf (dump_file, ")\n");
3185 }
3186
3187 /* Returns true when all the access functions of A are affine or
3188    constant with respect to LOOP_NEST.  */
3189
3190 static bool
3191 access_functions_are_affine_or_constant_p (struct data_reference *a,
3192                                            struct loop *loop_nest)
3193 {
3194   unsigned int i;
3195   VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3196   tree t;
3197
3198   for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3199     if (!evolution_function_is_invariant_p (t, loop_nest->num)
3200         && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3201       return false;
3202
3203   return true;
3204 }
3205
3206 /* Initializes an equation for an OMEGA problem using the information
3207    contained in the ACCESS_FUN.  Returns true when the operation
3208    succeeded.
3209
3210    PB is the omega constraint system.
3211    EQ is the number of the equation to be initialized.
3212    OFFSET is used for shifting the variables names in the constraints:
3213    a constrain is composed of 2 * the number of variables surrounding
3214    dependence accesses.  OFFSET is set either to 0 for the first n variables,
3215    then it is set to n.
3216    ACCESS_FUN is expected to be an affine chrec.  */
3217
3218 static bool
3219 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3220                        unsigned int offset, tree access_fun,
3221                        struct data_dependence_relation *ddr)
3222 {
3223   switch (TREE_CODE (access_fun))
3224     {
3225     case POLYNOMIAL_CHREC:
3226       {
3227         tree left = CHREC_LEFT (access_fun);
3228         tree right = CHREC_RIGHT (access_fun);
3229         int var = CHREC_VARIABLE (access_fun);
3230         unsigned var_idx;
3231
3232         if (TREE_CODE (right) != INTEGER_CST)
3233           return false;
3234
3235         var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3236         pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3237
3238         /* Compute the innermost loop index.  */
3239         DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3240
3241         if (offset == 0)
3242           pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3243             += int_cst_value (right);
3244
3245         switch (TREE_CODE (left))
3246           {
3247           case POLYNOMIAL_CHREC:
3248             return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3249
3250           case INTEGER_CST:
3251             pb->eqs[eq].coef[0] += int_cst_value (left);
3252             return true;
3253
3254           default:
3255             return false;
3256           }
3257       }
3258
3259     case INTEGER_CST:
3260       pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3261       return true;
3262
3263     default:
3264       return false;
3265     }
3266 }
3267
3268 /* As explained in the comments preceding init_omega_for_ddr, we have
3269    to set up a system for each loop level, setting outer loops
3270    variation to zero, and current loop variation to positive or zero.
3271    Save each lexico positive distance vector.  */
3272
3273 static void
3274 omega_extract_distance_vectors (omega_pb pb,
3275                                 struct data_dependence_relation *ddr)
3276 {
3277   int eq, geq;
3278   unsigned i, j;
3279   struct loop *loopi, *loopj;
3280   enum omega_result res;
3281
3282   /* Set a new problem for each loop in the nest.  The basis is the
3283      problem that we have initialized until now.  On top of this we
3284      add new constraints.  */
3285   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3286          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3287     {
3288       int dist = 0;
3289       omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3290                                            DDR_NB_LOOPS (ddr));
3291
3292       omega_copy_problem (copy, pb);
3293
3294       /* For all the outer loops "loop_j", add "dj = 0".  */
3295       for (j = 0;
3296            j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3297         {
3298           eq = omega_add_zero_eq (copy, omega_black);
3299           copy->eqs[eq].coef[j + 1] = 1;
3300         }
3301
3302       /* For "loop_i", add "0 <= di".  */
3303       geq = omega_add_zero_geq (copy, omega_black);
3304       copy->geqs[geq].coef[i + 1] = 1;
3305
3306       /* Reduce the constraint system, and test that the current
3307          problem is feasible.  */
3308       res = omega_simplify_problem (copy);
3309       if (res == omega_false
3310           || res == omega_unknown
3311           || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3312         goto next_problem;
3313
3314       for (eq = 0; eq < copy->num_subs; eq++)
3315         if (copy->subs[eq].key == (int) i + 1)
3316           {
3317             dist = copy->subs[eq].coef[0];
3318             goto found_dist;
3319           }
3320
3321       if (dist == 0)
3322         {
3323           /* Reinitialize problem...  */
3324           omega_copy_problem (copy, pb);
3325           for (j = 0;
3326                j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3327             {
3328               eq = omega_add_zero_eq (copy, omega_black);
3329               copy->eqs[eq].coef[j + 1] = 1;
3330             }
3331
3332           /* ..., but this time "di = 1".  */
3333           eq = omega_add_zero_eq (copy, omega_black);
3334           copy->eqs[eq].coef[i + 1] = 1;
3335           copy->eqs[eq].coef[0] = -1;
3336
3337           res = omega_simplify_problem (copy);
3338           if (res == omega_false
3339               || res == omega_unknown
3340               || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3341             goto next_problem;
3342
3343           for (eq = 0; eq < copy->num_subs; eq++)
3344             if (copy->subs[eq].key == (int) i + 1)
3345               {
3346                 dist = copy->subs[eq].coef[0];
3347                 goto found_dist;
3348               }
3349         }
3350
3351     found_dist:;
3352       /* Save the lexicographically positive distance vector.  */
3353       if (dist >= 0)
3354         {
3355           lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3356           lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3357
3358           dist_v[i] = dist;
3359
3360           for (eq = 0; eq < copy->num_subs; eq++)
3361             if (copy->subs[eq].key > 0)
3362               {
3363                 dist = copy->subs[eq].coef[0];
3364                 dist_v[copy->subs[eq].key - 1] = dist;
3365               }
3366
3367           for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3368             dir_v[j] = dir_from_dist (dist_v[j]);
3369
3370           save_dist_v (ddr, dist_v);
3371           save_dir_v (ddr, dir_v);
3372         }
3373
3374     next_problem:;
3375       omega_free_problem (copy);
3376     }
3377 }
3378
3379 /* This is called for each subscript of a tuple of data references:
3380    insert an equality for representing the conflicts.  */
3381
3382 static bool
3383 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3384                        struct data_dependence_relation *ddr,
3385                        omega_pb pb, bool *maybe_dependent)
3386 {
3387   int eq;
3388   tree fun_a = chrec_convert (integer_type_node, access_fun_a, NULL_TREE);
3389   tree fun_b = chrec_convert (integer_type_node, access_fun_b, NULL_TREE);
3390   tree difference = chrec_fold_minus (integer_type_node, fun_a, fun_b);
3391
3392   /* When the fun_a - fun_b is not constant, the dependence is not
3393      captured by the classic distance vector representation.  */
3394   if (TREE_CODE (difference) != INTEGER_CST)
3395     return false;
3396
3397   /* ZIV test.  */
3398   if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3399     {
3400       /* There is no dependence.  */
3401       *maybe_dependent = false;
3402       return true;
3403     }
3404
3405   fun_b = chrec_fold_multiply (integer_type_node, fun_b,
3406                                integer_minus_one_node);
3407
3408   eq = omega_add_zero_eq (pb, omega_black);
3409   if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3410       || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3411     /* There is probably a dependence, but the system of
3412        constraints cannot be built: answer "don't know".  */
3413     return false;
3414
3415   /* GCD test.  */
3416   if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3417       && !int_divides_p (lambda_vector_gcd
3418                          ((lambda_vector) &(pb->eqs[eq].coef[1]),
3419                           2 * DDR_NB_LOOPS (ddr)),
3420                          pb->eqs[eq].coef[0]))
3421     {
3422       /* There is no dependence.  */
3423       *maybe_dependent = false;
3424       return true;
3425     }
3426
3427   return true;
3428 }
3429
3430 /* Helper function, same as init_omega_for_ddr but specialized for
3431    data references A and B.  */
3432
3433 static bool
3434 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3435                       struct data_dependence_relation *ddr,
3436                       omega_pb pb, bool *maybe_dependent)
3437 {
3438   unsigned i;
3439   int ineq;
3440   struct loop *loopi;
3441   unsigned nb_loops = DDR_NB_LOOPS (ddr);
3442
3443   /* Insert an equality per subscript.  */
3444   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3445     {
3446       if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3447                                   ddr, pb, maybe_dependent))
3448         return false;
3449       else if (*maybe_dependent == false)
3450         {
3451           /* There is no dependence.  */
3452           DDR_ARE_DEPENDENT (ddr) = chrec_known;
3453           return true;
3454         }
3455     }
3456
3457   /* Insert inequalities: constraints corresponding to the iteration
3458      domain, i.e. the loops surrounding the references "loop_x" and
3459      the distance variables "dx".  The layout of the OMEGA
3460      representation is as follows:
3461      - coef[0] is the constant
3462      - coef[1..nb_loops] are the protected variables that will not be
3463      removed by the solver: the "dx"
3464      - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3465   */
3466   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3467          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3468     {
3469       HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3470
3471       /* 0 <= loop_x */
3472       ineq = omega_add_zero_geq (pb, omega_black);
3473       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3474
3475       /* 0 <= loop_x + dx */
3476       ineq = omega_add_zero_geq (pb, omega_black);
3477       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3478       pb->geqs[ineq].coef[i + 1] = 1;
3479
3480       if (nbi != -1)
3481         {
3482           /* loop_x <= nb_iters */
3483           ineq = omega_add_zero_geq (pb, omega_black);
3484           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3485           pb->geqs[ineq].coef[0] = nbi;
3486
3487           /* loop_x + dx <= nb_iters */
3488           ineq = omega_add_zero_geq (pb, omega_black);
3489           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3490           pb->geqs[ineq].coef[i + 1] = -1;
3491           pb->geqs[ineq].coef[0] = nbi;
3492
3493           /* A step "dx" bigger than nb_iters is not feasible, so
3494              add "0 <= nb_iters + dx",  */
3495           ineq = omega_add_zero_geq (pb, omega_black);
3496           pb->geqs[ineq].coef[i + 1] = 1;
3497           pb->geqs[ineq].coef[0] = nbi;
3498           /* and "dx <= nb_iters".  */
3499           ineq = omega_add_zero_geq (pb, omega_black);
3500           pb->geqs[ineq].coef[i + 1] = -1;
3501           pb->geqs[ineq].coef[0] = nbi;
3502         }
3503     }
3504
3505   omega_extract_distance_vectors (pb, ddr);
3506
3507   return true;
3508 }
3509
3510 /* Sets up the Omega dependence problem for the data dependence
3511    relation DDR.  Returns false when the constraint system cannot be
3512    built, ie. when the test answers "don't know".  Returns true
3513    otherwise, and when independence has been proved (using one of the
3514    trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3515    set MAYBE_DEPENDENT to true.
3516
3517    Example: for setting up the dependence system corresponding to the
3518    conflicting accesses
3519
3520    | loop_i
3521    |   loop_j
3522    |     A[i, i+1] = ...
3523    |     ... A[2*j, 2*(i + j)]
3524    |   endloop_j
3525    | endloop_i
3526
3527    the following constraints come from the iteration domain:
3528
3529    0 <= i <= Ni
3530    0 <= i + di <= Ni
3531    0 <= j <= Nj
3532    0 <= j + dj <= Nj
3533
3534    where di, dj are the distance variables.  The constraints
3535    representing the conflicting elements are:
3536
3537    i = 2 * (j + dj)
3538    i + 1 = 2 * (i + di + j + dj)
3539
3540    For asking that the resulting distance vector (di, dj) be
3541    lexicographically positive, we insert the constraint "di >= 0".  If
3542    "di = 0" in the solution, we fix that component to zero, and we
3543    look at the inner loops: we set a new problem where all the outer
3544    loop distances are zero, and fix this inner component to be
3545    positive.  When one of the components is positive, we save that
3546    distance, and set a new problem where the distance on this loop is
3547    zero, searching for other distances in the inner loops.  Here is
3548    the classic example that illustrates that we have to set for each
3549    inner loop a new problem:
3550
3551    | loop_1
3552    |   loop_2
3553    |     A[10]
3554    |   endloop_2
3555    | endloop_1
3556
3557    we have to save two distances (1, 0) and (0, 1).
3558
3559    Given two array references, refA and refB, we have to set the
3560    dependence problem twice, refA vs. refB and refB vs. refA, and we
3561    cannot do a single test, as refB might occur before refA in the
3562    inner loops, and the contrary when considering outer loops: ex.
3563
3564    | loop_0
3565    |   loop_1
3566    |     loop_2
3567    |       T[{1,+,1}_2][{1,+,1}_1]  // refA
3568    |       T[{2,+,1}_2][{0,+,1}_1]  // refB
3569    |     endloop_2
3570    |   endloop_1
3571    | endloop_0
3572
3573    refB touches the elements in T before refA, and thus for the same
3574    loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3575    but for successive loop_0 iterations, we have (1, -1, 1)
3576
3577    The Omega solver expects the distance variables ("di" in the
3578    previous example) to come first in the constraint system (as
3579    variables to be protected, or "safe" variables), the constraint
3580    system is built using the following layout:
3581
3582    "cst | distance vars | index vars".
3583 */
3584
3585 static bool
3586 init_omega_for_ddr (struct data_dependence_relation *ddr,
3587                     bool *maybe_dependent)
3588 {
3589   omega_pb pb;
3590   bool res = false;
3591
3592   *maybe_dependent = true;
3593
3594   if (same_access_functions (ddr))
3595     {
3596       unsigned j;
3597       lambda_vector dir_v;
3598
3599       /* Save the 0 vector.  */
3600       save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3601       dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3602       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3603         dir_v[j] = dir_equal;
3604       save_dir_v (ddr, dir_v);
3605
3606       /* Save the dependences carried by outer loops.  */
3607       pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3608       res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3609                                   maybe_dependent);
3610       omega_free_problem (pb);
3611       return res;
3612     }
3613
3614   /* Omega expects the protected variables (those that have to be kept
3615      after elimination) to appear first in the constraint system.
3616      These variables are the distance variables.  In the following
3617      initialization we declare NB_LOOPS safe variables, and the total
3618      number of variables for the constraint system is 2*NB_LOOPS.  */
3619   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3620   res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3621                               maybe_dependent);
3622   omega_free_problem (pb);
3623
3624   /* Stop computation if not decidable, or no dependence.  */
3625   if (res == false || *maybe_dependent == false)
3626     return res;
3627
3628   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3629   res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3630                               maybe_dependent);
3631   omega_free_problem (pb);
3632
3633   return res;
3634 }
3635
3636 /* Return true when DDR contains the same information as that stored
3637    in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
3638
3639 static bool
3640 ddr_consistent_p (FILE *file,
3641                   struct data_dependence_relation *ddr,
3642                   VEC (lambda_vector, heap) *dist_vects,
3643                   VEC (lambda_vector, heap) *dir_vects)
3644 {
3645   unsigned int i, j;
3646
3647   /* If dump_file is set, output there.  */
3648   if (dump_file && (dump_flags & TDF_DETAILS))
3649     file = dump_file;
3650
3651   if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3652     {
3653       lambda_vector b_dist_v;
3654       fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3655                VEC_length (lambda_vector, dist_vects),
3656                DDR_NUM_DIST_VECTS (ddr));
3657
3658       fprintf (file, "Banerjee dist vectors:\n");
3659       for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3660         print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3661
3662       fprintf (file, "Omega dist vectors:\n");
3663       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3664         print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3665
3666       fprintf (file, "data dependence relation:\n");
3667       dump_data_dependence_relation (file, ddr);
3668
3669       fprintf (file, ")\n");
3670       return false;
3671     }
3672
3673   if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3674     {
3675       fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3676                VEC_length (lambda_vector, dir_vects),
3677                DDR_NUM_DIR_VECTS (ddr));
3678       return false;
3679     }
3680
3681   for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3682     {
3683       lambda_vector a_dist_v;
3684       lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3685
3686       /* Distance vectors are not ordered in the same way in the DDR
3687          and in the DIST_VECTS: search for a matching vector.  */
3688       for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3689         if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3690           break;
3691
3692       if (j == VEC_length (lambda_vector, dist_vects))
3693         {
3694           fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3695           print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3696           fprintf (file, "not found in Omega dist vectors:\n");
3697           print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3698           fprintf (file, "data dependence relation:\n");
3699           dump_data_dependence_relation (file, ddr);
3700           fprintf (file, ")\n");
3701         }
3702     }
3703
3704   for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3705     {
3706       lambda_vector a_dir_v;
3707       lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3708
3709       /* Direction vectors are not ordered in the same way in the DDR
3710          and in the DIR_VECTS: search for a matching vector.  */
3711       for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3712         if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3713           break;
3714
3715       if (j == VEC_length (lambda_vector, dist_vects))
3716         {
3717           fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3718           print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3719           fprintf (file, "not found in Omega dir vectors:\n");
3720           print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3721           fprintf (file, "data dependence relation:\n");
3722           dump_data_dependence_relation (file, ddr);
3723           fprintf (file, ")\n");
3724         }
3725     }
3726
3727   return true;
3728 }
3729
3730 /* This computes the affine dependence relation between A and B with
3731    respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
3732    independence between two accesses, while CHREC_DONT_KNOW is used
3733    for representing the unknown relation.
3734
3735    Note that it is possible to stop the computation of the dependence
3736    relation the first time we detect a CHREC_KNOWN element for a given
3737    subscript.  */
3738
3739 static void
3740 compute_affine_dependence (struct data_dependence_relation *ddr,
3741                            struct loop *loop_nest)
3742 {
3743   struct data_reference *dra = DDR_A (ddr);
3744   struct data_reference *drb = DDR_B (ddr);
3745
3746   if (dump_file && (dump_flags & TDF_DETAILS))
3747     {
3748       fprintf (dump_file, "(compute_affine_dependence\n");
3749       fprintf (dump_file, "  (stmt_a = \n");
3750       print_generic_expr (dump_file, DR_STMT (dra), 0);
3751       fprintf (dump_file, ")\n  (stmt_b = \n");
3752       print_generic_expr (dump_file, DR_STMT (drb), 0);
3753       fprintf (dump_file, ")\n");
3754     }
3755
3756   /* Analyze only when the dependence relation is not yet known.  */
3757   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3758     {
3759       dependence_stats.num_dependence_tests++;
3760
3761       if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3762           && access_functions_are_affine_or_constant_p (drb, loop_nest))
3763         {
3764           if (flag_check_data_deps)
3765             {
3766               /* Compute the dependences using the first algorithm.  */
3767               subscript_dependence_tester (ddr, loop_nest);
3768
3769               if (dump_file && (dump_flags & TDF_DETAILS))
3770                 {
3771                   fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3772                   dump_data_dependence_relation (dump_file, ddr);
3773                 }
3774
3775               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3776                 {
3777                   bool maybe_dependent;
3778                   VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3779
3780                   /* Save the result of the first DD analyzer.  */
3781                   dist_vects = DDR_DIST_VECTS (ddr);
3782                   dir_vects = DDR_DIR_VECTS (ddr);
3783
3784                   /* Reset the information.  */
3785                   DDR_DIST_VECTS (ddr) = NULL;
3786                   DDR_DIR_VECTS (ddr) = NULL;
3787
3788                   /* Compute the same information using Omega.  */
3789                   if (!init_omega_for_ddr (ddr, &maybe_dependent))
3790                     goto csys_dont_know;
3791
3792                   if (dump_file && (dump_flags & TDF_DETAILS))
3793                     {
3794                       fprintf (dump_file, "Omega Analyzer\n");
3795                       dump_data_dependence_relation (dump_file, ddr);
3796                     }
3797
3798                   /* Check that we get the same information.  */
3799                   if (maybe_dependent)
3800                     gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3801                                                   dir_vects));
3802                 }
3803             }
3804           else
3805             subscript_dependence_tester (ddr, loop_nest);
3806         }
3807
3808       /* As a last case, if the dependence cannot be determined, or if
3809          the dependence is considered too difficult to determine, answer
3810          "don't know".  */
3811       else
3812         {
3813         csys_dont_know:;
3814           dependence_stats.num_dependence_undetermined++;
3815
3816           if (dump_file && (dump_flags & TDF_DETAILS))
3817             {
3818               fprintf (dump_file, "Data ref a:\n");
3819               dump_data_reference (dump_file, dra);
3820               fprintf (dump_file, "Data ref b:\n");
3821               dump_data_reference (dump_file, drb);
3822               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3823             }
3824           finalize_ddr_dependent (ddr, chrec_dont_know);
3825         }
3826     }
3827
3828   if (dump_file && (dump_flags & TDF_DETAILS))
3829     fprintf (dump_file, ")\n");
3830 }
3831
3832 /* This computes the dependence relation for the same data
3833    reference into DDR.  */
3834
3835 static void
3836 compute_self_dependence (struct data_dependence_relation *ddr)
3837 {
3838   unsigned int i;
3839   struct subscript *subscript;
3840
3841   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3842     return;
3843
3844   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3845        i++)
3846     {
3847       /* The accessed index overlaps for each iteration.  */
3848       SUB_CONFLICTS_IN_A (subscript)
3849               = conflict_fn (1, affine_fn_cst (integer_zero_node));
3850       SUB_CONFLICTS_IN_B (subscript)
3851               = conflict_fn (1, affine_fn_cst (integer_zero_node));
3852       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3853     }
3854
3855   /* The distance vector is the zero vector.  */
3856   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3857   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3858 }
3859
3860 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3861    the data references in DATAREFS, in the LOOP_NEST.  When
3862    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3863    relations.  */
3864
3865 void
3866 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3867                          VEC (ddr_p, heap) **dependence_relations,
3868                          VEC (loop_p, heap) *loop_nest,
3869                          bool compute_self_and_rr)
3870 {
3871   struct data_dependence_relation *ddr;
3872   struct data_reference *a, *b;
3873   unsigned int i, j;
3874
3875   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3876     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3877       if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3878         {
3879           ddr = initialize_data_dependence_relation (a, b, loop_nest);
3880           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3881           compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3882         }
3883
3884   if (compute_self_and_rr)
3885     for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3886       {
3887         ddr = initialize_data_dependence_relation (a, a, loop_nest);
3888         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3889         compute_self_dependence (ddr);
3890       }
3891 }
3892
3893 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
3894    true if STMT clobbers memory, false otherwise.  */
3895
3896 bool
3897 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3898 {
3899   bool clobbers_memory = false;
3900   data_ref_loc *ref;
3901   tree *op0, *op1, call;
3902
3903   *references = NULL;
3904
3905   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3906      Calls have side-effects, except those to const or pure
3907      functions.  */
3908   call = get_call_expr_in (stmt);
3909   if ((call
3910        && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
3911       || (TREE_CODE (stmt) == ASM_EXPR
3912           && ASM_VOLATILE_P (stmt)))
3913     clobbers_memory = true;
3914
3915   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3916     return clobbers_memory;
3917
3918   if (TREE_CODE (stmt) ==  GIMPLE_MODIFY_STMT)
3919     {
3920       op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
3921       op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
3922
3923       if (DECL_P (*op1)
3924           || REFERENCE_CLASS_P (*op1))
3925         {
3926           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3927           ref->pos = op1;
3928           ref->is_read = true;
3929         }
3930
3931       if (DECL_P (*op0)
3932           || REFERENCE_CLASS_P (*op0))
3933         {
3934           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3935           ref->pos = op0;
3936           ref->is_read = false;
3937         }
3938     }
3939
3940   if (call)
3941     {
3942       unsigned i, n = call_expr_nargs (call);
3943
3944       for (i = 0; i < n; i++)
3945         {
3946           op0 = &CALL_EXPR_ARG (call, i);
3947
3948           if (DECL_P (*op0)
3949               || REFERENCE_CLASS_P (*op0))
3950             {
3951               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3952               ref->pos = op0;
3953               ref->is_read = true;
3954             }
3955         }
3956     }
3957
3958   return clobbers_memory;
3959 }
3960
3961 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
3962    reference, returns false, otherwise returns true.  NEST is the outermost
3963    loop of the loop nest in that the references should be analyzed.  */
3964
3965 static bool
3966 find_data_references_in_stmt (struct loop *nest, tree stmt,
3967                               VEC (data_reference_p, heap) **datarefs)
3968 {
3969   unsigned i;
3970   VEC (data_ref_loc, heap) *references;
3971   data_ref_loc *ref;
3972   bool ret = true;
3973   data_reference_p dr;
3974
3975   if (get_references_in_stmt (stmt, &references))
3976     {
3977       VEC_free (data_ref_loc, heap, references);
3978       return false;
3979     }
3980
3981   for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
3982     {
3983       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
3984       gcc_assert (dr != NULL);
3985
3986       /* FIXME -- data dependence analysis does not work correctly for objects with
3987          invariant addresses.  Let us fail here until the problem is fixed.  */
3988       if (dr_address_invariant_p (dr))
3989         {
3990           free_data_ref (dr);
3991           if (dump_file && (dump_flags & TDF_DETAILS))
3992             fprintf (dump_file, "\tFAILED as dr address is invariant\n");
3993           ret = false;
3994           break;
3995         }
3996
3997       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
3998     }
3999   VEC_free (data_ref_loc, heap, references);
4000   return ret;
4001 }
4002
4003 /* Search the data references in LOOP, and record the information into
4004    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4005    difficult case, returns NULL_TREE otherwise.
4006
4007    TODO: This function should be made smarter so that it can handle address
4008    arithmetic as if they were array accesses, etc.  */
4009
4010 static tree
4011 find_data_references_in_loop (struct loop *loop,
4012                               VEC (data_reference_p, heap) **datarefs)
4013 {
4014   basic_block bb, *bbs;
4015   unsigned int i;
4016   block_stmt_iterator bsi;
4017
4018   bbs = get_loop_body_in_dom_order (loop);
4019
4020   for (i = 0; i < loop->num_nodes; i++)
4021     {
4022       bb = bbs[i];
4023
4024       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4025         {
4026           tree stmt = bsi_stmt (bsi);
4027
4028           if (!find_data_references_in_stmt (loop, stmt, datarefs))
4029             {
4030               struct data_reference *res;
4031               res = XCNEW (struct data_reference);
4032               VEC_safe_push (data_reference_p, heap, *datarefs, res);
4033
4034               free (bbs);
4035               return chrec_dont_know;
4036             }
4037         }
4038     }
4039   free (bbs);
4040
4041   return NULL_TREE;
4042 }
4043
4044 /* Recursive helper function.  */
4045
4046 static bool
4047 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4048 {
4049   /* Inner loops of the nest should not contain siblings.  Example:
4050      when there are two consecutive loops,
4051
4052      | loop_0
4053      |   loop_1
4054      |     A[{0, +, 1}_1]
4055      |   endloop_1
4056      |   loop_2
4057      |     A[{0, +, 1}_2]
4058      |   endloop_2
4059      | endloop_0
4060
4061      the dependence relation cannot be captured by the distance
4062      abstraction.  */
4063   if (loop->next)
4064     return false;
4065
4066   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4067   if (loop->inner)
4068     return find_loop_nest_1 (loop->inner, loop_nest);
4069   return true;
4070 }
4071
4072 /* Return false when the LOOP is not well nested.  Otherwise return
4073    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4074    contain the loops from the outermost to the innermost, as they will
4075    appear in the classic distance vector.  */
4076
4077 bool
4078 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4079 {
4080   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4081   if (loop->inner)
4082     return find_loop_nest_1 (loop->inner, loop_nest);
4083   return true;
4084 }
4085
4086 /* Given a loop nest LOOP, the following vectors are returned:
4087    DATAREFS is initialized to all the array elements contained in this loop,
4088    DEPENDENCE_RELATIONS contains the relations between the data references.
4089    Compute read-read and self relations if
4090    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4091
4092 void
4093 compute_data_dependences_for_loop (struct loop *loop,
4094                                    bool compute_self_and_read_read_dependences,
4095                                    VEC (data_reference_p, heap) **datarefs,
4096                                    VEC (ddr_p, heap) **dependence_relations)
4097 {
4098   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4099
4100   memset (&dependence_stats, 0, sizeof (dependence_stats));
4101
4102   /* If the loop nest is not well formed, or one of the data references
4103      is not computable, give up without spending time to compute other
4104      dependences.  */
4105   if (!loop
4106       || !find_loop_nest (loop, &vloops)
4107       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4108     {
4109       struct data_dependence_relation *ddr;
4110
4111       /* Insert a single relation into dependence_relations:
4112          chrec_dont_know.  */
4113       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4114       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4115     }
4116   else
4117     compute_all_dependences (*datarefs, dependence_relations, vloops,
4118                              compute_self_and_read_read_dependences);
4119
4120   if (dump_file && (dump_flags & TDF_STATS))
4121     {
4122       fprintf (dump_file, "Dependence tester statistics:\n");
4123
4124       fprintf (dump_file, "Number of dependence tests: %d\n",
4125                dependence_stats.num_dependence_tests);
4126       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4127                dependence_stats.num_dependence_dependent);
4128       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4129                dependence_stats.num_dependence_independent);
4130       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4131                dependence_stats.num_dependence_undetermined);
4132
4133       fprintf (dump_file, "Number of subscript tests: %d\n",
4134                dependence_stats.num_subscript_tests);
4135       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4136                dependence_stats.num_subscript_undetermined);
4137       fprintf (dump_file, "Number of same subscript function: %d\n",
4138                dependence_stats.num_same_subscript_function);
4139
4140       fprintf (dump_file, "Number of ziv tests: %d\n",
4141                dependence_stats.num_ziv);
4142       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4143                dependence_stats.num_ziv_dependent);
4144       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4145                dependence_stats.num_ziv_independent);
4146       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4147                dependence_stats.num_ziv_unimplemented);
4148
4149       fprintf (dump_file, "Number of siv tests: %d\n",
4150                dependence_stats.num_siv);
4151       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4152                dependence_stats.num_siv_dependent);
4153       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4154                dependence_stats.num_siv_independent);
4155       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4156                dependence_stats.num_siv_unimplemented);
4157
4158       fprintf (dump_file, "Number of miv tests: %d\n",
4159                dependence_stats.num_miv);
4160       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4161                dependence_stats.num_miv_dependent);
4162       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4163                dependence_stats.num_miv_independent);
4164       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4165                dependence_stats.num_miv_unimplemented);
4166     }
4167 }
4168
4169 /* Entry point (for testing only).  Analyze all the data references
4170    and the dependence relations in LOOP.
4171
4172    The data references are computed first.
4173
4174    A relation on these nodes is represented by a complete graph.  Some
4175    of the relations could be of no interest, thus the relations can be
4176    computed on demand.
4177
4178    In the following function we compute all the relations.  This is
4179    just a first implementation that is here for:
4180    - for showing how to ask for the dependence relations,
4181    - for the debugging the whole dependence graph,
4182    - for the dejagnu testcases and maintenance.
4183
4184    It is possible to ask only for a part of the graph, avoiding to
4185    compute the whole dependence graph.  The computed dependences are
4186    stored in a knowledge base (KB) such that later queries don't
4187    recompute the same information.  The implementation of this KB is
4188    transparent to the optimizer, and thus the KB can be changed with a
4189    more efficient implementation, or the KB could be disabled.  */
4190 static void
4191 analyze_all_data_dependences (struct loop *loop)
4192 {
4193   unsigned int i;
4194   int nb_data_refs = 10;
4195   VEC (data_reference_p, heap) *datarefs =
4196     VEC_alloc (data_reference_p, heap, nb_data_refs);
4197   VEC (ddr_p, heap) *dependence_relations =
4198     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4199
4200   /* Compute DDs on the whole function.  */
4201   compute_data_dependences_for_loop (loop, false, &datarefs,
4202                                      &dependence_relations);
4203
4204   if (dump_file)
4205     {
4206       dump_data_dependence_relations (dump_file, dependence_relations);
4207       fprintf (dump_file, "\n\n");
4208
4209       if (dump_flags & TDF_DETAILS)
4210         dump_dist_dir_vectors (dump_file, dependence_relations);
4211
4212       if (dump_flags & TDF_STATS)
4213         {
4214           unsigned nb_top_relations = 0;
4215           unsigned nb_bot_relations = 0;
4216           unsigned nb_basename_differ = 0;
4217           unsigned nb_chrec_relations = 0;
4218           struct data_dependence_relation *ddr;
4219
4220           for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4221             {
4222               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4223                 nb_top_relations++;
4224
4225               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4226                 {
4227                   struct data_reference *a = DDR_A (ddr);
4228                   struct data_reference *b = DDR_B (ddr);
4229
4230                   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4231                     nb_basename_differ++;
4232                   else
4233                     nb_bot_relations++;
4234                 }
4235
4236               else
4237                 nb_chrec_relations++;
4238             }
4239
4240           gather_stats_on_scev_database ();
4241         }
4242     }
4243
4244   free_dependence_relations (dependence_relations);
4245   free_data_refs (datarefs);
4246 }
4247
4248 /* Computes all the data dependences and check that the results of
4249    several analyzers are the same.  */
4250
4251 void
4252 tree_check_data_deps (void)
4253 {
4254   loop_iterator li;
4255   struct loop *loop_nest;
4256
4257   FOR_EACH_LOOP (li, loop_nest, 0)
4258     analyze_all_data_dependences (loop_nest);
4259 }
4260
4261 /* Free the memory used by a data dependence relation DDR.  */
4262
4263 void
4264 free_dependence_relation (struct data_dependence_relation *ddr)
4265 {
4266   if (ddr == NULL)
4267     return;
4268
4269   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4270     free_subscripts (DDR_SUBSCRIPTS (ddr));
4271
4272   free (ddr);
4273 }
4274
4275 /* Free the memory used by the data dependence relations from
4276    DEPENDENCE_RELATIONS.  */
4277
4278 void
4279 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4280 {
4281   unsigned int i;
4282   struct data_dependence_relation *ddr;
4283   VEC (loop_p, heap) *loop_nest = NULL;
4284
4285   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4286     {
4287       if (ddr == NULL)
4288         continue;
4289       if (loop_nest == NULL)
4290         loop_nest = DDR_LOOP_NEST (ddr);
4291       else
4292         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4293                     || DDR_LOOP_NEST (ddr) == loop_nest);
4294       free_dependence_relation (ddr);
4295     }
4296
4297   if (loop_nest)
4298     VEC_free (loop_p, heap, loop_nest);
4299   VEC_free (ddr_p, heap, dependence_relations);
4300 }
4301
4302 /* Free the memory used by the data references from DATAREFS.  */
4303
4304 void
4305 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4306 {
4307   unsigned int i;
4308   struct data_reference *dr;
4309
4310   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4311     free_data_ref (dr);
4312   VEC_free (data_reference_p, heap, datarefs);
4313 }
4314