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