gcc/tree-data-ref.c

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