gcc/tree-data-ref.c

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