gcc/tree-data-ref.c

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