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   bool res = true;
3315
3316   dr = create_data_ref (loop, op, stmt, true);
3317   if (!access_functions_are_affine_or_constant_p (dr, loop))
3318     res = false;
3319
3320   free_data_ref (dr);
3321   return res;
3322 }
3323
3324 /* Initializes an equation for an OMEGA problem using the information
3325    contained in the ACCESS_FUN.  Returns true when the operation
3326    succeeded.
3327
3328    PB is the omega constraint system.
3329    EQ is the number of the equation to be initialized.
3330    OFFSET is used for shifting the variables names in the constraints:
3331    a constrain is composed of 2 * the number of variables surrounding
3332    dependence accesses.  OFFSET is set either to 0 for the first n variables,
3333    then it is set to n.
3334    ACCESS_FUN is expected to be an affine chrec.  */
3335
3336 static bool
3337 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3338                        unsigned int offset, tree access_fun,
3339                        struct data_dependence_relation *ddr)
3340 {
3341   switch (TREE_CODE (access_fun))
3342     {
3343     case POLYNOMIAL_CHREC:
3344       {
3345         tree left = CHREC_LEFT (access_fun);
3346         tree right = CHREC_RIGHT (access_fun);
3347         int var = CHREC_VARIABLE (access_fun);
3348         unsigned var_idx;
3349
3350         if (TREE_CODE (right) != INTEGER_CST)
3351           return false;
3352
3353         var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3354         pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3355
3356         /* Compute the innermost loop index.  */
3357         DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3358
3359         if (offset == 0)
3360           pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3361             += int_cst_value (right);
3362
3363         switch (TREE_CODE (left))
3364           {
3365           case POLYNOMIAL_CHREC:
3366             return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3367
3368           case INTEGER_CST:
3369             pb->eqs[eq].coef[0] += int_cst_value (left);
3370             return true;
3371
3372           default:
3373             return false;
3374           }
3375       }
3376
3377     case INTEGER_CST:
3378       pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3379       return true;
3380
3381     default:
3382       return false;
3383     }
3384 }
3385
3386 /* As explained in the comments preceding init_omega_for_ddr, we have
3387    to set up a system for each loop level, setting outer loops
3388    variation to zero, and current loop variation to positive or zero.
3389    Save each lexico positive distance vector.  */
3390
3391 static void
3392 omega_extract_distance_vectors (omega_pb pb,
3393                                 struct data_dependence_relation *ddr)
3394 {
3395   int eq, geq;
3396   unsigned i, j;
3397   struct loop *loopi, *loopj;
3398   enum omega_result res;
3399
3400   /* Set a new problem for each loop in the nest.  The basis is the
3401      problem that we have initialized until now.  On top of this we
3402      add new constraints.  */
3403   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3404          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3405     {
3406       int dist = 0;
3407       omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3408                                            DDR_NB_LOOPS (ddr));
3409
3410       omega_copy_problem (copy, pb);
3411
3412       /* For all the outer loops "loop_j", add "dj = 0".  */
3413       for (j = 0;
3414            j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3415         {
3416           eq = omega_add_zero_eq (copy, omega_black);
3417           copy->eqs[eq].coef[j + 1] = 1;
3418         }
3419
3420       /* For "loop_i", add "0 <= di".  */
3421       geq = omega_add_zero_geq (copy, omega_black);
3422       copy->geqs[geq].coef[i + 1] = 1;
3423
3424       /* Reduce the constraint system, and test that the current
3425          problem is feasible.  */
3426       res = omega_simplify_problem (copy);
3427       if (res == omega_false
3428           || res == omega_unknown
3429           || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3430         goto next_problem;
3431
3432       for (eq = 0; eq < copy->num_subs; eq++)
3433         if (copy->subs[eq].key == (int) i + 1)
3434           {
3435             dist = copy->subs[eq].coef[0];
3436             goto found_dist;
3437           }
3438
3439       if (dist == 0)
3440         {
3441           /* Reinitialize problem...  */
3442           omega_copy_problem (copy, pb);
3443           for (j = 0;
3444                j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3445             {
3446               eq = omega_add_zero_eq (copy, omega_black);
3447               copy->eqs[eq].coef[j + 1] = 1;
3448             }
3449
3450           /* ..., but this time "di = 1".  */
3451           eq = omega_add_zero_eq (copy, omega_black);
3452           copy->eqs[eq].coef[i + 1] = 1;
3453           copy->eqs[eq].coef[0] = -1;
3454
3455           res = omega_simplify_problem (copy);
3456           if (res == omega_false
3457               || res == omega_unknown
3458               || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3459             goto next_problem;
3460
3461           for (eq = 0; eq < copy->num_subs; eq++)
3462             if (copy->subs[eq].key == (int) i + 1)
3463               {
3464                 dist = copy->subs[eq].coef[0];
3465                 goto found_dist;
3466               }
3467         }
3468
3469     found_dist:;
3470       /* Save the lexicographically positive distance vector.  */
3471       if (dist >= 0)
3472         {
3473           lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3474           lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3475
3476           dist_v[i] = dist;
3477
3478           for (eq = 0; eq < copy->num_subs; eq++)
3479             if (copy->subs[eq].key > 0)
3480               {
3481                 dist = copy->subs[eq].coef[0];
3482                 dist_v[copy->subs[eq].key - 1] = dist;
3483               }
3484
3485           for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3486             dir_v[j] = dir_from_dist (dist_v[j]);
3487
3488           save_dist_v (ddr, dist_v);
3489           save_dir_v (ddr, dir_v);
3490         }
3491
3492     next_problem:;
3493       omega_free_problem (copy);
3494     }
3495 }
3496
3497 /* This is called for each subscript of a tuple of data references:
3498    insert an equality for representing the conflicts.  */
3499
3500 static bool
3501 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3502                        struct data_dependence_relation *ddr,
3503                        omega_pb pb, bool *maybe_dependent)
3504 {
3505   int eq;
3506   tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3507                                      TREE_TYPE (access_fun_b));
3508   tree fun_a = chrec_convert (type, access_fun_a, NULL);
3509   tree fun_b = chrec_convert (type, access_fun_b, NULL);
3510   tree difference = chrec_fold_minus (type, fun_a, fun_b);
3511
3512   /* When the fun_a - fun_b is not constant, the dependence is not
3513      captured by the classic distance vector representation.  */
3514   if (TREE_CODE (difference) != INTEGER_CST)
3515     return false;
3516
3517   /* ZIV test.  */
3518   if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3519     {
3520       /* There is no dependence.  */
3521       *maybe_dependent = false;
3522       return true;
3523     }
3524
3525   fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
3526
3527   eq = omega_add_zero_eq (pb, omega_black);
3528   if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3529       || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3530     /* There is probably a dependence, but the system of
3531        constraints cannot be built: answer "don't know".  */
3532     return false;
3533
3534   /* GCD test.  */
3535   if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3536       && !int_divides_p (lambda_vector_gcd
3537                          ((lambda_vector) &(pb->eqs[eq].coef[1]),
3538                           2 * DDR_NB_LOOPS (ddr)),
3539                          pb->eqs[eq].coef[0]))
3540     {
3541       /* There is no dependence.  */
3542       *maybe_dependent = false;
3543       return true;
3544     }
3545
3546   return true;
3547 }
3548
3549 /* Helper function, same as init_omega_for_ddr but specialized for
3550    data references A and B.  */
3551
3552 static bool
3553 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3554                       struct data_dependence_relation *ddr,
3555                       omega_pb pb, bool *maybe_dependent)
3556 {
3557   unsigned i;
3558   int ineq;
3559   struct loop *loopi;
3560   unsigned nb_loops = DDR_NB_LOOPS (ddr);
3561
3562   /* Insert an equality per subscript.  */
3563   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3564     {
3565       if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3566                                   ddr, pb, maybe_dependent))
3567         return false;
3568       else if (*maybe_dependent == false)
3569         {
3570           /* There is no dependence.  */
3571           DDR_ARE_DEPENDENT (ddr) = chrec_known;
3572           return true;
3573         }
3574     }
3575
3576   /* Insert inequalities: constraints corresponding to the iteration
3577      domain, i.e. the loops surrounding the references "loop_x" and
3578      the distance variables "dx".  The layout of the OMEGA
3579      representation is as follows:
3580      - coef[0] is the constant
3581      - coef[1..nb_loops] are the protected variables that will not be
3582      removed by the solver: the "dx"
3583      - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3584   */
3585   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3586          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3587     {
3588       HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3589
3590       /* 0 <= loop_x */
3591       ineq = omega_add_zero_geq (pb, omega_black);
3592       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3593
3594       /* 0 <= loop_x + dx */
3595       ineq = omega_add_zero_geq (pb, omega_black);
3596       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3597       pb->geqs[ineq].coef[i + 1] = 1;
3598
3599       if (nbi != -1)
3600         {
3601           /* loop_x <= nb_iters */
3602           ineq = omega_add_zero_geq (pb, omega_black);
3603           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3604           pb->geqs[ineq].coef[0] = nbi;
3605
3606           /* loop_x + dx <= nb_iters */
3607           ineq = omega_add_zero_geq (pb, omega_black);
3608           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3609           pb->geqs[ineq].coef[i + 1] = -1;
3610           pb->geqs[ineq].coef[0] = nbi;
3611
3612           /* A step "dx" bigger than nb_iters is not feasible, so
3613              add "0 <= nb_iters + dx",  */
3614           ineq = omega_add_zero_geq (pb, omega_black);
3615           pb->geqs[ineq].coef[i + 1] = 1;
3616           pb->geqs[ineq].coef[0] = nbi;
3617           /* and "dx <= nb_iters".  */
3618           ineq = omega_add_zero_geq (pb, omega_black);
3619           pb->geqs[ineq].coef[i + 1] = -1;
3620           pb->geqs[ineq].coef[0] = nbi;
3621         }
3622     }
3623
3624   omega_extract_distance_vectors (pb, ddr);
3625
3626   return true;
3627 }
3628
3629 /* Sets up the Omega dependence problem for the data dependence
3630    relation DDR.  Returns false when the constraint system cannot be
3631    built, ie. when the test answers "don't know".  Returns true
3632    otherwise, and when independence has been proved (using one of the
3633    trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3634    set MAYBE_DEPENDENT to true.
3635
3636    Example: for setting up the dependence system corresponding to the
3637    conflicting accesses
3638
3639    | loop_i
3640    |   loop_j
3641    |     A[i, i+1] = ...
3642    |     ... A[2*j, 2*(i + j)]
3643    |   endloop_j
3644    | endloop_i
3645
3646    the following constraints come from the iteration domain:
3647
3648    0 <= i <= Ni
3649    0 <= i + di <= Ni
3650    0 <= j <= Nj
3651    0 <= j + dj <= Nj
3652
3653    where di, dj are the distance variables.  The constraints
3654    representing the conflicting elements are:
3655
3656    i = 2 * (j + dj)
3657    i + 1 = 2 * (i + di + j + dj)
3658
3659    For asking that the resulting distance vector (di, dj) be
3660    lexicographically positive, we insert the constraint "di >= 0".  If
3661    "di = 0" in the solution, we fix that component to zero, and we
3662    look at the inner loops: we set a new problem where all the outer
3663    loop distances are zero, and fix this inner component to be
3664    positive.  When one of the components is positive, we save that
3665    distance, and set a new problem where the distance on this loop is
3666    zero, searching for other distances in the inner loops.  Here is
3667    the classic example that illustrates that we have to set for each
3668    inner loop a new problem:
3669
3670    | loop_1
3671    |   loop_2
3672    |     A[10]
3673    |   endloop_2
3674    | endloop_1
3675
3676    we have to save two distances (1, 0) and (0, 1).
3677
3678    Given two array references, refA and refB, we have to set the
3679    dependence problem twice, refA vs. refB and refB vs. refA, and we
3680    cannot do a single test, as refB might occur before refA in the
3681    inner loops, and the contrary when considering outer loops: ex.
3682
3683    | loop_0
3684    |   loop_1
3685    |     loop_2
3686    |       T[{1,+,1}_2][{1,+,1}_1]  // refA
3687    |       T[{2,+,1}_2][{0,+,1}_1]  // refB
3688    |     endloop_2
3689    |   endloop_1
3690    | endloop_0
3691
3692    refB touches the elements in T before refA, and thus for the same
3693    loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3694    but for successive loop_0 iterations, we have (1, -1, 1)
3695
3696    The Omega solver expects the distance variables ("di" in the
3697    previous example) to come first in the constraint system (as
3698    variables to be protected, or "safe" variables), the constraint
3699    system is built using the following layout:
3700
3701    "cst | distance vars | index vars".
3702 */
3703
3704 static bool
3705 init_omega_for_ddr (struct data_dependence_relation *ddr,
3706                     bool *maybe_dependent)
3707 {
3708   omega_pb pb;
3709   bool res = false;
3710
3711   *maybe_dependent = true;
3712
3713   if (same_access_functions (ddr))
3714     {
3715       unsigned j;
3716       lambda_vector dir_v;
3717
3718       /* Save the 0 vector.  */
3719       save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3720       dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3721       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3722         dir_v[j] = dir_equal;
3723       save_dir_v (ddr, dir_v);
3724
3725       /* Save the dependences carried by outer loops.  */
3726       pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3727       res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3728                                   maybe_dependent);
3729       omega_free_problem (pb);
3730       return res;
3731     }
3732
3733   /* Omega expects the protected variables (those that have to be kept
3734      after elimination) to appear first in the constraint system.
3735      These variables are the distance variables.  In the following
3736      initialization we declare NB_LOOPS safe variables, and the total
3737      number of variables for the constraint system is 2*NB_LOOPS.  */
3738   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3739   res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3740                               maybe_dependent);
3741   omega_free_problem (pb);
3742
3743   /* Stop computation if not decidable, or no dependence.  */
3744   if (res == false || *maybe_dependent == false)
3745     return res;
3746
3747   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3748   res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3749                               maybe_dependent);
3750   omega_free_problem (pb);
3751
3752   return res;
3753 }
3754
3755 /* Return true when DDR contains the same information as that stored
3756    in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
3757
3758 static bool
3759 ddr_consistent_p (FILE *file,
3760                   struct data_dependence_relation *ddr,
3761                   VEC (lambda_vector, heap) *dist_vects,
3762                   VEC (lambda_vector, heap) *dir_vects)
3763 {
3764   unsigned int i, j;
3765
3766   /* If dump_file is set, output there.  */
3767   if (dump_file && (dump_flags & TDF_DETAILS))
3768     file = dump_file;
3769
3770   if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3771     {
3772       lambda_vector b_dist_v;
3773       fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3774                VEC_length (lambda_vector, dist_vects),
3775                DDR_NUM_DIST_VECTS (ddr));
3776
3777       fprintf (file, "Banerjee dist vectors:\n");
3778       for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3779         print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3780
3781       fprintf (file, "Omega dist vectors:\n");
3782       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3783         print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3784
3785       fprintf (file, "data dependence relation:\n");
3786       dump_data_dependence_relation (file, ddr);
3787
3788       fprintf (file, ")\n");
3789       return false;
3790     }
3791
3792   if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3793     {
3794       fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3795                VEC_length (lambda_vector, dir_vects),
3796                DDR_NUM_DIR_VECTS (ddr));
3797       return false;
3798     }
3799
3800   for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3801     {
3802       lambda_vector a_dist_v;
3803       lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3804
3805       /* Distance vectors are not ordered in the same way in the DDR
3806          and in the DIST_VECTS: search for a matching vector.  */
3807       for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3808         if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3809           break;
3810
3811       if (j == VEC_length (lambda_vector, dist_vects))
3812         {
3813           fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3814           print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3815           fprintf (file, "not found in Omega dist vectors:\n");
3816           print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3817           fprintf (file, "data dependence relation:\n");
3818           dump_data_dependence_relation (file, ddr);
3819           fprintf (file, ")\n");
3820         }
3821     }
3822
3823   for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3824     {
3825       lambda_vector a_dir_v;
3826       lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3827
3828       /* Direction vectors are not ordered in the same way in the DDR
3829          and in the DIR_VECTS: search for a matching vector.  */
3830       for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3831         if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3832           break;
3833
3834       if (j == VEC_length (lambda_vector, dist_vects))
3835         {
3836           fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3837           print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3838           fprintf (file, "not found in Omega dir vectors:\n");
3839           print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3840           fprintf (file, "data dependence relation:\n");
3841           dump_data_dependence_relation (file, ddr);
3842           fprintf (file, ")\n");
3843         }
3844     }
3845
3846   return true;
3847 }
3848
3849 /* This computes the affine dependence relation between A and B with
3850    respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
3851    independence between two accesses, while CHREC_DONT_KNOW is used
3852    for representing the unknown relation.
3853
3854    Note that it is possible to stop the computation of the dependence
3855    relation the first time we detect a CHREC_KNOWN element for a given
3856    subscript.  */
3857
3858 static void
3859 compute_affine_dependence (struct data_dependence_relation *ddr,
3860                            struct loop *loop_nest)
3861 {
3862   struct data_reference *dra = DDR_A (ddr);
3863   struct data_reference *drb = DDR_B (ddr);
3864
3865   if (dump_file && (dump_flags & TDF_DETAILS))
3866     {
3867       fprintf (dump_file, "(compute_affine_dependence\n");
3868       fprintf (dump_file, "  (stmt_a = \n");
3869       print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
3870       fprintf (dump_file, ")\n  (stmt_b = \n");
3871       print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
3872       fprintf (dump_file, ")\n");
3873     }
3874
3875   /* Analyze only when the dependence relation is not yet known.  */
3876   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3877       && !DDR_SELF_REFERENCE (ddr))
3878     {
3879       dependence_stats.num_dependence_tests++;
3880
3881       if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3882           && access_functions_are_affine_or_constant_p (drb, loop_nest))
3883         {
3884           if (flag_check_data_deps)
3885             {
3886               /* Compute the dependences using the first algorithm.  */
3887               subscript_dependence_tester (ddr, loop_nest);
3888
3889               if (dump_file && (dump_flags & TDF_DETAILS))
3890                 {
3891                   fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3892                   dump_data_dependence_relation (dump_file, ddr);
3893                 }
3894
3895               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3896                 {
3897                   bool maybe_dependent;
3898                   VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3899
3900                   /* Save the result of the first DD analyzer.  */
3901                   dist_vects = DDR_DIST_VECTS (ddr);
3902                   dir_vects = DDR_DIR_VECTS (ddr);
3903
3904                   /* Reset the information.  */
3905                   DDR_DIST_VECTS (ddr) = NULL;
3906                   DDR_DIR_VECTS (ddr) = NULL;
3907
3908                   /* Compute the same information using Omega.  */
3909                   if (!init_omega_for_ddr (ddr, &maybe_dependent))
3910                     goto csys_dont_know;
3911
3912                   if (dump_file && (dump_flags & TDF_DETAILS))
3913                     {
3914                       fprintf (dump_file, "Omega Analyzer\n");
3915                       dump_data_dependence_relation (dump_file, ddr);
3916                     }
3917
3918                   /* Check that we get the same information.  */
3919                   if (maybe_dependent)
3920                     gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3921                                                   dir_vects));
3922                 }
3923             }
3924           else
3925             subscript_dependence_tester (ddr, loop_nest);
3926         }
3927
3928       /* As a last case, if the dependence cannot be determined, or if
3929          the dependence is considered too difficult to determine, answer
3930          "don't know".  */
3931       else
3932         {
3933         csys_dont_know:;
3934           dependence_stats.num_dependence_undetermined++;
3935
3936           if (dump_file && (dump_flags & TDF_DETAILS))
3937             {
3938               fprintf (dump_file, "Data ref a:\n");
3939               dump_data_reference (dump_file, dra);
3940               fprintf (dump_file, "Data ref b:\n");
3941               dump_data_reference (dump_file, drb);
3942               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3943             }
3944           finalize_ddr_dependent (ddr, chrec_dont_know);
3945         }
3946     }
3947
3948   if (dump_file && (dump_flags & TDF_DETAILS))
3949     fprintf (dump_file, ")\n");
3950 }
3951
3952 /* This computes the dependence relation for the same data
3953    reference into DDR.  */
3954
3955 static void
3956 compute_self_dependence (struct data_dependence_relation *ddr)
3957 {
3958   unsigned int i;
3959   struct subscript *subscript;
3960
3961   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3962     return;
3963
3964   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3965        i++)
3966     {
3967       if (SUB_CONFLICTS_IN_A (subscript))
3968         free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3969       if (SUB_CONFLICTS_IN_B (subscript))
3970         free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3971
3972       /* The accessed index overlaps for each iteration.  */
3973       SUB_CONFLICTS_IN_A (subscript)
3974         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3975       SUB_CONFLICTS_IN_B (subscript)
3976         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3977       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3978     }
3979
3980   /* The distance vector is the zero vector.  */
3981   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3982   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3983 }
3984
3985 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3986    the data references in DATAREFS, in the LOOP_NEST.  When
3987    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3988    relations.  */
3989
3990 void
3991 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3992                          VEC (ddr_p, heap) **dependence_relations,
3993                          VEC (loop_p, heap) *loop_nest,
3994                          bool compute_self_and_rr)
3995 {
3996   struct data_dependence_relation *ddr;
3997   struct data_reference *a, *b;
3998   unsigned int i, j;
3999
4000   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4001     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4002       if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4003         {
4004           ddr = initialize_data_dependence_relation (a, b, loop_nest);
4005           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4006           compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
4007         }
4008
4009   if (compute_self_and_rr)
4010     for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4011       {
4012         ddr = initialize_data_dependence_relation (a, a, loop_nest);
4013         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4014         compute_self_dependence (ddr);
4015       }
4016 }
4017
4018 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
4019    true if STMT clobbers memory, false otherwise.  */
4020
4021 bool
4022 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4023 {
4024   bool clobbers_memory = false;
4025   data_ref_loc *ref;
4026   tree *op0, *op1;
4027   enum gimple_code stmt_code = gimple_code (stmt);
4028
4029   *references = NULL;
4030
4031   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4032      Calls have side-effects, except those to const or pure
4033      functions.  */
4034   if ((stmt_code == GIMPLE_CALL
4035        && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4036       || (stmt_code == GIMPLE_ASM
4037           && gimple_asm_volatile_p (stmt)))
4038     clobbers_memory = true;
4039
4040   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4041     return clobbers_memory;
4042
4043   if (stmt_code == GIMPLE_ASSIGN)
4044     {
4045       tree base;
4046       op0 = gimple_assign_lhs_ptr (stmt);
4047       op1 = gimple_assign_rhs1_ptr (stmt);
4048
4049       if (DECL_P (*op1)
4050           || (REFERENCE_CLASS_P (*op1)
4051               && (base = get_base_address (*op1))
4052               && TREE_CODE (base) != SSA_NAME))
4053         {
4054           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4055           ref->pos = op1;
4056           ref->is_read = true;
4057         }
4058
4059       if (DECL_P (*op0)
4060           || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4061         {
4062           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4063           ref->pos = op0;
4064           ref->is_read = false;
4065         }
4066     }
4067   else if (stmt_code == GIMPLE_CALL)
4068     {
4069       unsigned i, n = gimple_call_num_args (stmt);
4070
4071       for (i = 0; i < n; i++)
4072         {
4073           op0 = gimple_call_arg_ptr (stmt, i);
4074
4075           if (DECL_P (*op0)
4076               || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4077             {
4078               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4079               ref->pos = op0;
4080               ref->is_read = true;
4081             }
4082         }
4083     }
4084
4085   return clobbers_memory;
4086 }
4087
4088 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
4089    reference, returns false, otherwise returns true.  NEST is the outermost
4090    loop of the loop nest in which the references should be analyzed.  */
4091
4092 bool
4093 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4094                               VEC (data_reference_p, heap) **datarefs)
4095 {
4096   unsigned i;
4097   VEC (data_ref_loc, heap) *references;
4098   data_ref_loc *ref;
4099   bool ret = true;
4100   data_reference_p dr;
4101
4102   if (get_references_in_stmt (stmt, &references))
4103     {
4104       VEC_free (data_ref_loc, heap, references);
4105       return false;
4106     }
4107
4108   for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4109     {
4110       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4111       gcc_assert (dr != NULL);
4112
4113       /* FIXME -- data dependence analysis does not work correctly for objects with
4114          invariant addresses.  Let us fail here until the problem is fixed.  */
4115       if (dr_address_invariant_p (dr))
4116         {
4117           free_data_ref (dr);
4118           if (dump_file && (dump_flags & TDF_DETAILS))
4119             fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4120           ret = false;
4121           break;
4122         }
4123
4124       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4125     }
4126   VEC_free (data_ref_loc, heap, references);
4127   return ret;
4128 }
4129
4130 /* Search the data references in LOOP, and record the information into
4131    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4132    difficult case, returns NULL_TREE otherwise.
4133
4134    TODO: This function should be made smarter so that it can handle address
4135    arithmetic as if they were array accesses, etc.  */
4136
4137 tree
4138 find_data_references_in_loop (struct loop *loop,
4139                               VEC (data_reference_p, heap) **datarefs)
4140 {
4141   basic_block bb, *bbs;
4142   unsigned int i;
4143   gimple_stmt_iterator bsi;
4144
4145   bbs = get_loop_body_in_dom_order (loop);
4146
4147   for (i = 0; i < loop->num_nodes; i++)
4148     {
4149       bb = bbs[i];
4150
4151       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4152         {
4153           gimple stmt = gsi_stmt (bsi);
4154
4155           if (!find_data_references_in_stmt (loop, stmt, datarefs))
4156             {
4157               struct data_reference *res;
4158               res = XCNEW (struct data_reference);
4159               VEC_safe_push (data_reference_p, heap, *datarefs, res);
4160
4161               free (bbs);
4162               return chrec_dont_know;
4163             }
4164         }
4165     }
4166   free (bbs);
4167
4168   return NULL_TREE;
4169 }
4170
4171 /* Recursive helper function.  */
4172
4173 static bool
4174 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4175 {
4176   /* Inner loops of the nest should not contain siblings.  Example:
4177      when there are two consecutive loops,
4178
4179      | loop_0
4180      |   loop_1
4181      |     A[{0, +, 1}_1]
4182      |   endloop_1
4183      |   loop_2
4184      |     A[{0, +, 1}_2]
4185      |   endloop_2
4186      | endloop_0
4187
4188      the dependence relation cannot be captured by the distance
4189      abstraction.  */
4190   if (loop->next)
4191     return false;
4192
4193   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4194   if (loop->inner)
4195     return find_loop_nest_1 (loop->inner, loop_nest);
4196   return true;
4197 }
4198
4199 /* Return false when the LOOP is not well nested.  Otherwise return
4200    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4201    contain the loops from the outermost to the innermost, as they will
4202    appear in the classic distance vector.  */
4203
4204 bool
4205 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4206 {
4207   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4208   if (loop->inner)
4209     return find_loop_nest_1 (loop->inner, loop_nest);
4210   return true;
4211 }
4212
4213 /* Returns true when the data dependences have been computed, false otherwise.
4214    Given a loop nest LOOP, the following vectors are returned:
4215    DATAREFS is initialized to all the array elements contained in this loop,
4216    DEPENDENCE_RELATIONS contains the relations between the data references.
4217    Compute read-read and self relations if
4218    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4219
4220 bool
4221 compute_data_dependences_for_loop (struct loop *loop,
4222                                    bool compute_self_and_read_read_dependences,
4223                                    VEC (data_reference_p, heap) **datarefs,
4224                                    VEC (ddr_p, heap) **dependence_relations)
4225 {
4226   bool res = true;
4227   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4228
4229   memset (&dependence_stats, 0, sizeof (dependence_stats));
4230
4231   /* If the loop nest is not well formed, or one of the data references
4232      is not computable, give up without spending time to compute other
4233      dependences.  */
4234   if (!loop
4235       || !find_loop_nest (loop, &vloops)
4236       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4237     {
4238       struct data_dependence_relation *ddr;
4239
4240       /* Insert a single relation into dependence_relations:
4241          chrec_dont_know.  */
4242       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4243       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4244       res = false;
4245     }
4246   else
4247     compute_all_dependences (*datarefs, dependence_relations, vloops,
4248                              compute_self_and_read_read_dependences);
4249
4250   if (dump_file && (dump_flags & TDF_STATS))
4251     {
4252       fprintf (dump_file, "Dependence tester statistics:\n");
4253
4254       fprintf (dump_file, "Number of dependence tests: %d\n",
4255                dependence_stats.num_dependence_tests);
4256       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4257                dependence_stats.num_dependence_dependent);
4258       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4259                dependence_stats.num_dependence_independent);
4260       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4261                dependence_stats.num_dependence_undetermined);
4262
4263       fprintf (dump_file, "Number of subscript tests: %d\n",
4264                dependence_stats.num_subscript_tests);
4265       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4266                dependence_stats.num_subscript_undetermined);
4267       fprintf (dump_file, "Number of same subscript function: %d\n",
4268                dependence_stats.num_same_subscript_function);
4269
4270       fprintf (dump_file, "Number of ziv tests: %d\n",
4271                dependence_stats.num_ziv);
4272       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4273                dependence_stats.num_ziv_dependent);
4274       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4275                dependence_stats.num_ziv_independent);
4276       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4277                dependence_stats.num_ziv_unimplemented);
4278
4279       fprintf (dump_file, "Number of siv tests: %d\n",
4280                dependence_stats.num_siv);
4281       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4282                dependence_stats.num_siv_dependent);
4283       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4284                dependence_stats.num_siv_independent);
4285       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4286                dependence_stats.num_siv_unimplemented);
4287
4288       fprintf (dump_file, "Number of miv tests: %d\n",
4289                dependence_stats.num_miv);
4290       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4291                dependence_stats.num_miv_dependent);
4292       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4293                dependence_stats.num_miv_independent);
4294       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4295                dependence_stats.num_miv_unimplemented);
4296     }
4297
4298   return res;
4299 }
4300
4301 /* Entry point (for testing only).  Analyze all the data references
4302    and the dependence relations in LOOP.
4303
4304    The data references are computed first.
4305
4306    A relation on these nodes is represented by a complete graph.  Some
4307    of the relations could be of no interest, thus the relations can be
4308    computed on demand.
4309
4310    In the following function we compute all the relations.  This is
4311    just a first implementation that is here for:
4312    - for showing how to ask for the dependence relations,
4313    - for the debugging the whole dependence graph,
4314    - for the dejagnu testcases and maintenance.
4315
4316    It is possible to ask only for a part of the graph, avoiding to
4317    compute the whole dependence graph.  The computed dependences are
4318    stored in a knowledge base (KB) such that later queries don't
4319    recompute the same information.  The implementation of this KB is
4320    transparent to the optimizer, and thus the KB can be changed with a
4321    more efficient implementation, or the KB could be disabled.  */
4322 static void
4323 analyze_all_data_dependences (struct loop *loop)
4324 {
4325   unsigned int i;
4326   int nb_data_refs = 10;
4327   VEC (data_reference_p, heap) *datarefs =
4328     VEC_alloc (data_reference_p, heap, nb_data_refs);
4329   VEC (ddr_p, heap) *dependence_relations =
4330     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4331
4332   /* Compute DDs on the whole function.  */
4333   compute_data_dependences_for_loop (loop, false, &datarefs,
4334                                      &dependence_relations);
4335
4336   if (dump_file)
4337     {
4338       dump_data_dependence_relations (dump_file, dependence_relations);
4339       fprintf (dump_file, "\n\n");
4340
4341       if (dump_flags & TDF_DETAILS)
4342         dump_dist_dir_vectors (dump_file, dependence_relations);
4343
4344       if (dump_flags & TDF_STATS)
4345         {
4346           unsigned nb_top_relations = 0;
4347           unsigned nb_bot_relations = 0;
4348           unsigned nb_basename_differ = 0;
4349           unsigned nb_chrec_relations = 0;
4350           struct data_dependence_relation *ddr;
4351
4352           for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4353             {
4354               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4355                 nb_top_relations++;
4356
4357               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4358                 {
4359                   struct data_reference *a = DDR_A (ddr);
4360                   struct data_reference *b = DDR_B (ddr);
4361
4362                   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4363                     nb_basename_differ++;
4364                   else
4365                     nb_bot_relations++;
4366                 }
4367
4368               else
4369                 nb_chrec_relations++;
4370             }
4371
4372           gather_stats_on_scev_database ();
4373         }
4374     }
4375
4376   free_dependence_relations (dependence_relations);
4377   free_data_refs (datarefs);
4378 }
4379
4380 /* Computes all the data dependences and check that the results of
4381    several analyzers are the same.  */
4382
4383 void
4384 tree_check_data_deps (void)
4385 {
4386   loop_iterator li;
4387   struct loop *loop_nest;
4388
4389   FOR_EACH_LOOP (li, loop_nest, 0)
4390     analyze_all_data_dependences (loop_nest);
4391 }
4392
4393 /* Free the memory used by a data dependence relation DDR.  */
4394
4395 void
4396 free_dependence_relation (struct data_dependence_relation *ddr)
4397 {
4398   if (ddr == NULL)
4399     return;
4400
4401   if (DDR_SUBSCRIPTS (ddr))
4402     free_subscripts (DDR_SUBSCRIPTS (ddr));
4403   if (DDR_DIST_VECTS (ddr))
4404     VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4405   if (DDR_DIR_VECTS (ddr))
4406     VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4407
4408   free (ddr);
4409 }
4410
4411 /* Free the memory used by the data dependence relations from
4412    DEPENDENCE_RELATIONS.  */
4413
4414 void
4415 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4416 {
4417   unsigned int i;
4418   struct data_dependence_relation *ddr;
4419   VEC (loop_p, heap) *loop_nest = NULL;
4420
4421   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4422     {
4423       if (ddr == NULL)
4424         continue;
4425       if (loop_nest == NULL)
4426         loop_nest = DDR_LOOP_NEST (ddr);
4427       else
4428         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4429                     || DDR_LOOP_NEST (ddr) == loop_nest);
4430       free_dependence_relation (ddr);
4431     }
4432
4433   if (loop_nest)
4434     VEC_free (loop_p, heap, loop_nest);
4435   VEC_free (ddr_p, heap, dependence_relations);
4436 }
4437
4438 /* Free the memory used by the data references from DATAREFS.  */
4439
4440 void
4441 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4442 {
4443   unsigned int i;
4444   struct data_reference *dr;
4445
4446   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4447     free_data_ref (dr);
4448   VEC_free (data_reference_p, heap, datarefs);
4449 }
4450
4451 \f
4452
4453 /* Dump vertex I in RDG to FILE.  */
4454
4455 void
4456 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4457 {
4458   struct vertex *v = &(rdg->vertices[i]);
4459   struct graph_edge *e;
4460
4461   fprintf (file, "(vertex %d: (%s%s) (in:", i,
4462            RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4463            RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4464
4465   if (v->pred)
4466     for (e = v->pred; e; e = e->pred_next)
4467       fprintf (file, " %d", e->src);
4468
4469   fprintf (file, ") (out:");
4470
4471   if (v->succ)
4472     for (e = v->succ; e; e = e->succ_next)
4473       fprintf (file, " %d", e->dest);
4474
4475   fprintf (file, ") \n");
4476   print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4477   fprintf (file, ")\n");
4478 }
4479
4480 /* Call dump_rdg_vertex on stderr.  */
4481
4482 void
4483 debug_rdg_vertex (struct graph *rdg, int i)
4484 {
4485   dump_rdg_vertex (stderr, rdg, i);
4486 }
4487
4488 /* Dump component C of RDG to FILE.  If DUMPED is non-null, set the
4489    dumped vertices to that bitmap.  */
4490
4491 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4492 {
4493   int i;
4494
4495   fprintf (file, "(%d\n", c);
4496
4497   for (i = 0; i < rdg->n_vertices; i++)
4498     if (rdg->vertices[i].component == c)
4499       {
4500         if (dumped)
4501           bitmap_set_bit (dumped, i);
4502
4503         dump_rdg_vertex (file, rdg, i);
4504       }
4505
4506   fprintf (file, ")\n");
4507 }
4508
4509 /* Call dump_rdg_vertex on stderr.  */
4510
4511 void
4512 debug_rdg_component (struct graph *rdg, int c)
4513 {
4514   dump_rdg_component (stderr, rdg, c, NULL);
4515 }
4516
4517 /* Dump the reduced dependence graph RDG to FILE.  */
4518
4519 void
4520 dump_rdg (FILE *file, struct graph *rdg)
4521 {
4522   int i;
4523   bitmap dumped = BITMAP_ALLOC (NULL);
4524
4525   fprintf (file, "(rdg\n");
4526
4527   for (i = 0; i < rdg->n_vertices; i++)
4528     if (!bitmap_bit_p (dumped, i))
4529       dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4530
4531   fprintf (file, ")\n");
4532   BITMAP_FREE (dumped);
4533 }
4534
4535 /* Call dump_rdg on stderr.  */
4536
4537 void
4538 debug_rdg (struct graph *rdg)
4539 {
4540   dump_rdg (stderr, rdg);
4541 }
4542
4543 static void
4544 dot_rdg_1 (FILE *file, struct graph *rdg)
4545 {
4546   int i;
4547
4548   fprintf (file, "digraph RDG {\n");
4549
4550   for (i = 0; i < rdg->n_vertices; i++)
4551     {
4552       struct vertex *v = &(rdg->vertices[i]);
4553       struct graph_edge *e;
4554
4555       /* Highlight reads from memory.  */
4556       if (RDG_MEM_READS_STMT (rdg, i))
4557         fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4558
4559       /* Highlight stores to memory.  */
4560       if (RDG_MEM_WRITE_STMT (rdg, i))
4561         fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4562
4563       if (v->succ)
4564         for (e = v->succ; e; e = e->succ_next)
4565           switch (RDGE_TYPE (e))
4566             {
4567             case input_dd:
4568               fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4569               break;
4570
4571             case output_dd:
4572               fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4573               break;
4574
4575             case flow_dd:
4576               /* These are the most common dependences: don't print these. */
4577               fprintf (file, "%d -> %d \n", i, e->dest);
4578               break;
4579
4580             case anti_dd:
4581               fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4582               break;
4583
4584             default:
4585               gcc_unreachable ();
4586             }
4587     }
4588
4589   fprintf (file, "}\n\n");
4590 }
4591
4592 /* Display SCOP using dotty.  */
4593
4594 void
4595 dot_rdg (struct graph *rdg)
4596 {
4597   FILE *file = fopen ("/tmp/rdg.dot", "w");
4598   gcc_assert (file != NULL);
4599
4600   dot_rdg_1 (file, rdg);
4601   fclose (file);
4602
4603   system ("dotty /tmp/rdg.dot");
4604 }
4605
4606
4607 /* This structure is used for recording the mapping statement index in
4608    the RDG.  */
4609
4610 struct rdg_vertex_info GTY(())
4611 {
4612   gimple stmt;
4613   int index;
4614 };
4615
4616 /* Returns the index of STMT in RDG.  */
4617
4618 int
4619 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4620 {
4621   struct rdg_vertex_info rvi, *slot;
4622
4623   rvi.stmt = stmt;
4624   slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4625
4626   if (!slot)
4627     return -1;
4628
4629   return slot->index;
4630 }
4631
4632 /* Creates an edge in RDG for each distance vector from DDR.  The
4633    order that we keep track of in the RDG is the order in which
4634    statements have to be executed.  */
4635
4636 static void
4637 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4638 {
4639   struct graph_edge *e;
4640   int va, vb;
4641   data_reference_p dra = DDR_A (ddr);
4642   data_reference_p drb = DDR_B (ddr);
4643   unsigned level = ddr_dependence_level (ddr);
4644
4645   /* For non scalar dependences, when the dependence is REVERSED,
4646      statement B has to be executed before statement A.  */
4647   if (level > 0
4648       && !DDR_REVERSED_P (ddr))
4649     {
4650       data_reference_p tmp = dra;
4651       dra = drb;
4652       drb = tmp;
4653     }
4654
4655   va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4656   vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4657
4658   if (va < 0 || vb < 0)
4659     return;
4660
4661   e = add_edge (rdg, va, vb);
4662   e->data = XNEW (struct rdg_edge);
4663
4664   RDGE_LEVEL (e) = level;
4665   RDGE_RELATION (e) = ddr;
4666
4667   /* Determines the type of the data dependence.  */
4668   if (DR_IS_READ (dra) && DR_IS_READ (drb))
4669     RDGE_TYPE (e) = input_dd;
4670   else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
4671     RDGE_TYPE (e) = output_dd;
4672   else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
4673     RDGE_TYPE (e) = flow_dd;
4674   else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
4675     RDGE_TYPE (e) = anti_dd;
4676 }
4677
4678 /* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
4679    the index of DEF in RDG.  */
4680
4681 static void
4682 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4683 {
4684   use_operand_p imm_use_p;
4685   imm_use_iterator iterator;
4686
4687   FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4688     {
4689       struct graph_edge *e;
4690       int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4691
4692       if (use < 0)
4693         continue;
4694
4695       e = add_edge (rdg, idef, use);
4696       e->data = XNEW (struct rdg_edge);
4697       RDGE_TYPE (e) = flow_dd;
4698       RDGE_RELATION (e) = NULL;
4699     }
4700 }
4701
4702 /* Creates the edges of the reduced dependence graph RDG.  */
4703
4704 static void
4705 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4706 {
4707   int i;
4708   struct data_dependence_relation *ddr;
4709   def_operand_p def_p;
4710   ssa_op_iter iter;
4711
4712   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
4713     if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4714       create_rdg_edge_for_ddr (rdg, ddr);
4715
4716   for (i = 0; i < rdg->n_vertices; i++)
4717     FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4718                               iter, SSA_OP_DEF)
4719       create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4720 }
4721
4722 /* Build the vertices of the reduced dependence graph RDG.  */
4723
4724 void
4725 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
4726 {
4727   int i, j;
4728   gimple stmt;
4729
4730   for (i = 0; VEC_iterate (gimple, stmts, i, stmt); i++)
4731     {
4732       VEC (data_ref_loc, heap) *references;
4733       data_ref_loc *ref;
4734       struct vertex *v = &(rdg->vertices[i]);
4735       struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4736       struct rdg_vertex_info **slot;
4737
4738       rvi->stmt = stmt;
4739       rvi->index = i;
4740       slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4741
4742       if (!*slot)
4743         *slot = rvi;
4744       else
4745         free (rvi);
4746
4747       v->data = XNEW (struct rdg_vertex);
4748       RDG_STMT (rdg, i) = stmt;
4749
4750       RDG_MEM_WRITE_STMT (rdg, i) = false;
4751       RDG_MEM_READS_STMT (rdg, i) = false;
4752       if (gimple_code (stmt) == GIMPLE_PHI)
4753         continue;
4754
4755       get_references_in_stmt (stmt, &references);
4756       for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
4757         if (!ref->is_read)
4758           RDG_MEM_WRITE_STMT (rdg, i) = true;
4759         else
4760           RDG_MEM_READS_STMT (rdg, i) = true;
4761
4762       VEC_free (data_ref_loc, heap, references);
4763     }
4764 }
4765
4766 /* Initialize STMTS with all the statements of LOOP.  When
4767    INCLUDE_PHIS is true, include also the PHI nodes.  The order in
4768    which we discover statements is important as
4769    generate_loops_for_partition is using the same traversal for
4770    identifying statements. */
4771
4772 static void
4773 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4774 {
4775   unsigned int i;
4776   basic_block *bbs = get_loop_body_in_dom_order (loop);
4777
4778   for (i = 0; i < loop->num_nodes; i++)
4779     {
4780       basic_block bb = bbs[i];
4781       gimple_stmt_iterator bsi;
4782       gimple stmt;
4783
4784       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4785         VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4786
4787       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4788         {
4789           stmt = gsi_stmt (bsi);
4790           if (gimple_code (stmt) != GIMPLE_LABEL)
4791             VEC_safe_push (gimple, heap, *stmts, stmt);
4792         }
4793     }
4794
4795   free (bbs);
4796 }
4797
4798 /* Returns true when all the dependences are computable.  */
4799
4800 static bool
4801 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4802 {
4803   ddr_p ddr;
4804   unsigned int i;
4805
4806   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4807     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4808       return false;
4809
4810   return true;
4811 }
4812
4813 /* Computes a hash function for element ELT.  */
4814
4815 static hashval_t
4816 hash_stmt_vertex_info (const void *elt)
4817 {
4818   const struct rdg_vertex_info *const rvi =
4819     (const struct rdg_vertex_info *) elt;
4820   gimple stmt = rvi->stmt;
4821
4822   return htab_hash_pointer (stmt);
4823 }
4824
4825 /* Compares database elements E1 and E2.  */
4826
4827 static int
4828 eq_stmt_vertex_info (const void *e1, const void *e2)
4829 {
4830   const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4831   const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4832
4833   return elt1->stmt == elt2->stmt;
4834 }
4835
4836 /* Free the element E.  */
4837
4838 static void
4839 hash_stmt_vertex_del (void *e)
4840 {
4841   free (e);
4842 }
4843
4844 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4845    statement of the loop nest, and one edge per data dependence or
4846    scalar dependence.  */
4847
4848 struct graph *
4849 build_empty_rdg (int n_stmts)
4850 {
4851   int nb_data_refs = 10;
4852   struct graph *rdg = new_graph (n_stmts);
4853
4854   rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4855                               eq_stmt_vertex_info, hash_stmt_vertex_del);
4856   return rdg;
4857 }
4858
4859 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4860    statement of the loop nest, and one edge per data dependence or
4861    scalar dependence.  */
4862
4863 struct graph *
4864 build_rdg (struct loop *loop)
4865 {
4866   int nb_data_refs = 10;
4867   struct graph *rdg = NULL;
4868   VEC (ddr_p, heap) *dependence_relations;
4869   VEC (data_reference_p, heap) *datarefs;
4870   VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
4871
4872   dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4873   datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4874   compute_data_dependences_for_loop (loop,
4875                                      false,
4876                                      &datarefs,
4877                                      &dependence_relations);
4878
4879   if (!known_dependences_p (dependence_relations))
4880     {
4881       free_dependence_relations (dependence_relations);
4882       free_data_refs (datarefs);
4883       VEC_free (gimple, heap, stmts);
4884
4885       return rdg;
4886     }
4887
4888   stmts_from_loop (loop, &stmts);
4889   rdg = build_empty_rdg (VEC_length (gimple, stmts));
4890
4891   rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4892                               eq_stmt_vertex_info, hash_stmt_vertex_del);
4893   create_rdg_vertices (rdg, stmts);
4894   create_rdg_edges (rdg, dependence_relations);
4895
4896   VEC_free (gimple, heap, stmts);
4897   return rdg;
4898 }
4899
4900 /* Free the reduced dependence graph RDG.  */
4901
4902 void
4903 free_rdg (struct graph *rdg)
4904 {
4905   int i;
4906
4907   for (i = 0; i < rdg->n_vertices; i++)
4908     free (rdg->vertices[i].data);
4909
4910   htab_delete (rdg->indices);
4911   free_graph (rdg);
4912 }
4913
4914 /* Initialize STMTS with all the statements of LOOP that contain a
4915    store to memory.  */
4916
4917 void
4918 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4919 {
4920   unsigned int i;
4921   basic_block *bbs = get_loop_body_in_dom_order (loop);
4922
4923   for (i = 0; i < loop->num_nodes; i++)
4924     {
4925       basic_block bb = bbs[i];
4926       gimple_stmt_iterator bsi;
4927
4928       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4929         if (!ZERO_SSA_OPERANDS (gsi_stmt (bsi), SSA_OP_VDEF))
4930           VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4931     }
4932
4933   free (bbs);
4934 }
4935
4936 /* For a data reference REF, return the declaration of its base
4937    address or NULL_TREE if the base is not determined.  */
4938
4939 static inline tree
4940 ref_base_address (gimple stmt, data_ref_loc *ref)
4941 {
4942   tree base = NULL_TREE;
4943   tree base_address;
4944   struct data_reference *dr = XCNEW (struct data_reference);
4945
4946   DR_STMT (dr) = stmt;
4947   DR_REF (dr) = *ref->pos;
4948   dr_analyze_innermost (dr);
4949   base_address = DR_BASE_ADDRESS (dr);
4950
4951   if (!base_address)
4952     goto end;
4953
4954   switch (TREE_CODE (base_address))
4955     {
4956     case ADDR_EXPR:
4957       base = TREE_OPERAND (base_address, 0);
4958       break;
4959
4960     default:
4961       base = base_address;
4962       break;
4963     }
4964
4965  end:
4966   free_data_ref (dr);
4967   return base;
4968 }
4969
4970 /* Determines whether the statement from vertex V of the RDG has a
4971    definition used outside the loop that contains this statement.  */
4972
4973 bool
4974 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
4975 {
4976   gimple stmt = RDG_STMT (rdg, v);
4977   struct loop *loop = loop_containing_stmt (stmt);
4978   use_operand_p imm_use_p;
4979   imm_use_iterator iterator;
4980   ssa_op_iter it;
4981   def_operand_p def_p;
4982
4983   if (!loop)
4984     return true;
4985
4986   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
4987     {
4988       FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
4989         {
4990           if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
4991             return true;
4992         }
4993     }
4994
4995   return false;
4996 }
4997
4998 /* Determines whether statements S1 and S2 access to similar memory
4999    locations.  Two memory accesses are considered similar when they
5000    have the same base address declaration, i.e. when their
5001    ref_base_address is the same.  */
5002
5003 bool
5004 have_similar_memory_accesses (gimple s1, gimple s2)
5005 {
5006   bool res = false;
5007   unsigned i, j;
5008   VEC (data_ref_loc, heap) *refs1, *refs2;
5009   data_ref_loc *ref1, *ref2;
5010
5011   get_references_in_stmt (s1, &refs1);
5012   get_references_in_stmt (s2, &refs2);
5013
5014   for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
5015     {
5016       tree base1 = ref_base_address (s1, ref1);
5017
5018       if (base1)
5019         for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
5020           if (base1 == ref_base_address (s2, ref2))
5021             {
5022               res = true;
5023               goto end;
5024             }
5025     }
5026
5027  end:
5028   VEC_free (data_ref_loc, heap, refs1);
5029   VEC_free (data_ref_loc, heap, refs2);
5030   return res;
5031 }
5032
5033 /* Helper function for the hashtab.  */
5034
5035 static int
5036 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5037 {
5038   return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5039                                        CONST_CAST_GIMPLE ((const_gimple) s2));
5040 }
5041
5042 /* Helper function for the hashtab.  */
5043
5044 static hashval_t
5045 ref_base_address_1 (const void *s)
5046 {
5047   gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5048   unsigned i;
5049   VEC (data_ref_loc, heap) *refs;
5050   data_ref_loc *ref;
5051   hashval_t res = 0;
5052
5053   get_references_in_stmt (stmt, &refs);
5054
5055   for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
5056     if (!ref->is_read)
5057       {
5058         res = htab_hash_pointer (ref_base_address (stmt, ref));
5059         break;
5060       }
5061
5062   VEC_free (data_ref_loc, heap, refs);
5063   return res;
5064 }
5065
5066 /* Try to remove duplicated write data references from STMTS.  */
5067
5068 void
5069 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5070 {
5071   unsigned i;
5072   gimple stmt;
5073   htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5074                              have_similar_memory_accesses_1, NULL);
5075
5076   for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5077     {
5078       void **slot;
5079
5080       slot = htab_find_slot (seen, stmt, INSERT);
5081
5082       if (*slot)
5083         VEC_ordered_remove (gimple, *stmts, i);
5084       else
5085         {
5086           *slot = (void *) stmt;
5087           i++;
5088         }
5089     }
5090
5091   htab_delete (seen);
5092 }
5093
5094 /* Returns the index of PARAMETER in the parameters vector of the
5095    ACCESS_MATRIX.  If PARAMETER does not exist return -1.  */
5096
5097 int
5098 access_matrix_get_index_for_parameter (tree parameter,
5099                                        struct access_matrix *access_matrix)
5100 {
5101   int i;
5102   VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5103   tree lambda_parameter;
5104
5105   for (i = 0; VEC_iterate (tree, lambda_parameters, i, lambda_parameter); i++)
5106     if (lambda_parameter == parameter)
5107       return i + AM_NB_INDUCTION_VARS (access_matrix);
5108
5109   return -1;
5110 }