gcc/tree-data-ref.c

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