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