gcc/tree-data-ref.c

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