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