gcc/tree-data-ref.c

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