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                || operand_equal_p (chrec_a, chrec_b, 0)))
2658     {
2659       dependence_stats.num_same_subscript_function++;
2660       *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2661       *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2662       *last_conflicts = chrec_dont_know;
2663     }
2664
2665   /* If they aren't the same, and aren't affine, we can't do anything
2666      yet.  */
2667   else if ((chrec_contains_symbols (chrec_a)
2668             || chrec_contains_symbols (chrec_b))
2669            && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2670                || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2671     {
2672       dependence_stats.num_subscript_undetermined++;
2673       *overlap_iterations_a = conflict_fn_not_known ();
2674       *overlap_iterations_b = conflict_fn_not_known ();
2675     }
2676
2677   else if (ziv_subscript_p (chrec_a, chrec_b))
2678     analyze_ziv_subscript (chrec_a, chrec_b,
2679                            overlap_iterations_a, overlap_iterations_b,
2680                            last_conflicts);
2681
2682   else if (siv_subscript_p (chrec_a, chrec_b))
2683     analyze_siv_subscript (chrec_a, chrec_b,
2684                            overlap_iterations_a, overlap_iterations_b,
2685                            last_conflicts, lnn);
2686
2687   else
2688     analyze_miv_subscript (chrec_a, chrec_b,
2689                            overlap_iterations_a, overlap_iterations_b,
2690                            last_conflicts, loop_nest);
2691
2692   if (dump_file && (dump_flags & TDF_DETAILS))
2693     {
2694       fprintf (dump_file, "  (overlap_iterations_a = ");
2695       dump_conflict_function (dump_file, *overlap_iterations_a);
2696       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2697       dump_conflict_function (dump_file, *overlap_iterations_b);
2698       fprintf (dump_file, ")\n");
2699       fprintf (dump_file, ")\n");
2700     }
2701 }
2702
2703 /* Helper function for uniquely inserting distance vectors.  */
2704
2705 static void
2706 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2707 {
2708   unsigned i;
2709   lambda_vector v;
2710
2711   FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, v)
2712     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2713       return;
2714
2715   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2716 }
2717
2718 /* Helper function for uniquely inserting direction vectors.  */
2719
2720 static void
2721 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2722 {
2723   unsigned i;
2724   lambda_vector v;
2725
2726   FOR_EACH_VEC_ELT (lambda_vector, DDR_DIR_VECTS (ddr), i, v)
2727     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2728       return;
2729
2730   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2731 }
2732
2733 /* Add a distance of 1 on all the loops outer than INDEX.  If we
2734    haven't yet determined a distance for this outer loop, push a new
2735    distance vector composed of the previous distance, and a distance
2736    of 1 for this outer loop.  Example:
2737
2738    | loop_1
2739    |   loop_2
2740    |     A[10]
2741    |   endloop_2
2742    | endloop_1
2743
2744    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
2745    save (0, 1), then we have to save (1, 0).  */
2746
2747 static void
2748 add_outer_distances (struct data_dependence_relation *ddr,
2749                      lambda_vector dist_v, int index)
2750 {
2751   /* For each outer loop where init_v is not set, the accesses are
2752      in dependence of distance 1 in the loop.  */
2753   while (--index >= 0)
2754     {
2755       lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2756       lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2757       save_v[index] = 1;
2758       save_dist_v (ddr, save_v);
2759     }
2760 }
2761
2762 /* Return false when fail to represent the data dependence as a
2763    distance vector.  INIT_B is set to true when a component has been
2764    added to the distance vector DIST_V.  INDEX_CARRY is then set to
2765    the index in DIST_V that carries the dependence.  */
2766
2767 static bool
2768 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2769                              struct data_reference *ddr_a,
2770                              struct data_reference *ddr_b,
2771                              lambda_vector dist_v, bool *init_b,
2772                              int *index_carry)
2773 {
2774   unsigned i;
2775   lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2776
2777   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2778     {
2779       tree access_fn_a, access_fn_b;
2780       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2781
2782       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2783         {
2784           non_affine_dependence_relation (ddr);
2785           return false;
2786         }
2787
2788       access_fn_a = DR_ACCESS_FN (ddr_a, i);
2789       access_fn_b = DR_ACCESS_FN (ddr_b, i);
2790
2791       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2792           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2793         {
2794           int dist, index;
2795           int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2796                                             DDR_LOOP_NEST (ddr));
2797           int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2798                                             DDR_LOOP_NEST (ddr));
2799
2800           /* The dependence is carried by the outermost loop.  Example:
2801              | loop_1
2802              |   A[{4, +, 1}_1]
2803              |   loop_2
2804              |     A[{5, +, 1}_2]
2805              |   endloop_2
2806              | endloop_1
2807              In this case, the dependence is carried by loop_1.  */
2808           index = index_a < index_b ? index_a : index_b;
2809           *index_carry = MIN (index, *index_carry);
2810
2811           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2812             {
2813               non_affine_dependence_relation (ddr);
2814               return false;
2815             }
2816
2817           dist = int_cst_value (SUB_DISTANCE (subscript));
2818
2819           /* This is the subscript coupling test.  If we have already
2820              recorded a distance for this loop (a distance coming from
2821              another subscript), it should be the same.  For example,
2822              in the following code, there is no dependence:
2823
2824              | loop i = 0, N, 1
2825              |   T[i+1][i] = ...
2826              |   ... = T[i][i]
2827              | endloop
2828           */
2829           if (init_v[index] != 0 && dist_v[index] != dist)
2830             {
2831               finalize_ddr_dependent (ddr, chrec_known);
2832               return false;
2833             }
2834
2835           dist_v[index] = dist;
2836           init_v[index] = 1;
2837           *init_b = true;
2838         }
2839       else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2840         {
2841           /* This can be for example an affine vs. constant dependence
2842              (T[i] vs. T[3]) that is not an affine dependence and is
2843              not representable as a distance vector.  */
2844           non_affine_dependence_relation (ddr);
2845           return false;
2846         }
2847     }
2848
2849   return true;
2850 }
2851
2852 /* Return true when the DDR contains only constant access functions.  */
2853
2854 static bool
2855 constant_access_functions (const struct data_dependence_relation *ddr)
2856 {
2857   unsigned i;
2858
2859   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2860     if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2861         || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2862       return false;
2863
2864   return true;
2865 }
2866
2867 /* Helper function for the case where DDR_A and DDR_B are the same
2868    multivariate access function with a constant step.  For an example
2869    see pr34635-1.c.  */
2870
2871 static void
2872 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2873 {
2874   int x_1, x_2;
2875   tree c_1 = CHREC_LEFT (c_2);
2876   tree c_0 = CHREC_LEFT (c_1);
2877   lambda_vector dist_v;
2878   int v1, v2, cd;
2879
2880   /* Polynomials with more than 2 variables are not handled yet.  When
2881      the evolution steps are parameters, it is not possible to
2882      represent the dependence using classical distance vectors.  */
2883   if (TREE_CODE (c_0) != INTEGER_CST
2884       || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
2885       || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
2886     {
2887       DDR_AFFINE_P (ddr) = false;
2888       return;
2889     }
2890
2891   x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2892   x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2893
2894   /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
2895   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2896   v1 = int_cst_value (CHREC_RIGHT (c_1));
2897   v2 = int_cst_value (CHREC_RIGHT (c_2));
2898   cd = gcd (v1, v2);
2899   v1 /= cd;
2900   v2 /= cd;
2901
2902   if (v2 < 0)
2903     {
2904       v2 = -v2;
2905       v1 = -v1;
2906     }
2907
2908   dist_v[x_1] = v2;
2909   dist_v[x_2] = -v1;
2910   save_dist_v (ddr, dist_v);
2911
2912   add_outer_distances (ddr, dist_v, x_1);
2913 }
2914
2915 /* Helper function for the case where DDR_A and DDR_B are the same
2916    access functions.  */
2917
2918 static void
2919 add_other_self_distances (struct data_dependence_relation *ddr)
2920 {
2921   lambda_vector dist_v;
2922   unsigned i;
2923   int index_carry = DDR_NB_LOOPS (ddr);
2924
2925   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2926     {
2927       tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2928
2929       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2930         {
2931           if (!evolution_function_is_univariate_p (access_fun))
2932             {
2933               if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2934                 {
2935                   DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2936                   return;
2937                 }
2938
2939               access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
2940
2941               if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
2942                 add_multivariate_self_dist (ddr, access_fun);
2943               else
2944                 /* The evolution step is not constant: it varies in
2945                    the outer loop, so this cannot be represented by a
2946                    distance vector.  For example in pr34635.c the
2947                    evolution is {0, +, {0, +, 4}_1}_2.  */
2948                 DDR_AFFINE_P (ddr) = false;
2949
2950               return;
2951             }
2952
2953           index_carry = MIN (index_carry,
2954                              index_in_loop_nest (CHREC_VARIABLE (access_fun),
2955                                                  DDR_LOOP_NEST (ddr)));
2956         }
2957     }
2958
2959   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2960   add_outer_distances (ddr, dist_v, index_carry);
2961 }
2962
2963 static void
2964 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2965 {
2966   lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2967
2968   dist_v[DDR_INNER_LOOP (ddr)] = 1;
2969   save_dist_v (ddr, dist_v);
2970 }
2971
2972 /* Adds a unit distance vector to DDR when there is a 0 overlap.  This
2973    is the case for example when access functions are the same and
2974    equal to a constant, as in:
2975
2976    | loop_1
2977    |   A[3] = ...
2978    |   ... = A[3]
2979    | endloop_1
2980
2981    in which case the distance vectors are (0) and (1).  */
2982
2983 static void
2984 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2985 {
2986   unsigned i, j;
2987
2988   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2989     {
2990       subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2991       conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2992       conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2993
2994       for (j = 0; j < ca->n; j++)
2995         if (affine_function_zero_p (ca->fns[j]))
2996           {
2997             insert_innermost_unit_dist_vector (ddr);
2998             return;
2999           }
3000
3001       for (j = 0; j < cb->n; j++)
3002         if (affine_function_zero_p (cb->fns[j]))
3003           {
3004             insert_innermost_unit_dist_vector (ddr);
3005             return;
3006           }
3007     }
3008 }
3009
3010 /* Compute the classic per loop distance vector.  DDR is the data
3011    dependence relation to build a vector from.  Return false when fail
3012    to represent the data dependence as a distance vector.  */
3013
3014 static bool
3015 build_classic_dist_vector (struct data_dependence_relation *ddr,
3016                            struct loop *loop_nest)
3017 {
3018   bool init_b = false;
3019   int index_carry = DDR_NB_LOOPS (ddr);
3020   lambda_vector dist_v;
3021
3022   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3023     return false;
3024
3025   if (same_access_functions (ddr))
3026     {
3027       /* Save the 0 vector.  */
3028       dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3029       save_dist_v (ddr, dist_v);
3030
3031       if (constant_access_functions (ddr))
3032         add_distance_for_zero_overlaps (ddr);
3033
3034       if (DDR_NB_LOOPS (ddr) > 1)
3035         add_other_self_distances (ddr);
3036
3037       return true;
3038     }
3039
3040   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3041   if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3042                                     dist_v, &init_b, &index_carry))
3043     return false;
3044
3045   /* Save the distance vector if we initialized one.  */
3046   if (init_b)
3047     {
3048       /* Verify a basic constraint: classic distance vectors should
3049          always be lexicographically positive.
3050
3051          Data references are collected in the order of execution of
3052          the program, thus for the following loop
3053
3054          | for (i = 1; i < 100; i++)
3055          |   for (j = 1; j < 100; j++)
3056          |     {
3057          |       t = T[j+1][i-1];  // A
3058          |       T[j][i] = t + 2;  // B
3059          |     }
3060
3061          references are collected following the direction of the wind:
3062          A then B.  The data dependence tests are performed also
3063          following this order, such that we're looking at the distance
3064          separating the elements accessed by A from the elements later
3065          accessed by B.  But in this example, the distance returned by
3066          test_dep (A, B) is lexicographically negative (-1, 1), that
3067          means that the access A occurs later than B with respect to
3068          the outer loop, ie. we're actually looking upwind.  In this
3069          case we solve test_dep (B, A) looking downwind to the
3070          lexicographically positive solution, that returns the
3071          distance vector (1, -1).  */
3072       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3073         {
3074           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3075           if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3076                                               loop_nest))
3077             return false;
3078           compute_subscript_distance (ddr);
3079           if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3080                                             save_v, &init_b, &index_carry))
3081             return false;
3082           save_dist_v (ddr, save_v);
3083           DDR_REVERSED_P (ddr) = true;
3084
3085           /* In this case there is a dependence forward for all the
3086              outer loops:
3087
3088              | for (k = 1; k < 100; k++)
3089              |  for (i = 1; i < 100; i++)
3090              |   for (j = 1; j < 100; j++)
3091              |     {
3092              |       t = T[j+1][i-1];  // A
3093              |       T[j][i] = t + 2;  // B
3094              |     }
3095
3096              the vectors are:
3097              (0,  1, -1)
3098              (1,  1, -1)
3099              (1, -1,  1)
3100           */
3101           if (DDR_NB_LOOPS (ddr) > 1)
3102             {
3103               add_outer_distances (ddr, save_v, index_carry);
3104               add_outer_distances (ddr, dist_v, index_carry);
3105             }
3106         }
3107       else
3108         {
3109           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3110           lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3111
3112           if (DDR_NB_LOOPS (ddr) > 1)
3113             {
3114               lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3115
3116               if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3117                                                   DDR_A (ddr), loop_nest))
3118                 return false;
3119               compute_subscript_distance (ddr);
3120               if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3121                                                 opposite_v, &init_b,
3122                                                 &index_carry))
3123                 return false;
3124
3125               save_dist_v (ddr, save_v);
3126               add_outer_distances (ddr, dist_v, index_carry);
3127               add_outer_distances (ddr, opposite_v, index_carry);
3128             }
3129           else
3130             save_dist_v (ddr, save_v);
3131         }
3132     }
3133   else
3134     {
3135       /* There is a distance of 1 on all the outer loops: Example:
3136          there is a dependence of distance 1 on loop_1 for the array A.
3137
3138          | loop_1
3139          |   A[5] = ...
3140          | endloop
3141       */
3142       add_outer_distances (ddr, dist_v,
3143                            lambda_vector_first_nz (dist_v,
3144                                                    DDR_NB_LOOPS (ddr), 0));
3145     }
3146
3147   if (dump_file && (dump_flags & TDF_DETAILS))
3148     {
3149       unsigned i;
3150
3151       fprintf (dump_file, "(build_classic_dist_vector\n");
3152       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3153         {
3154           fprintf (dump_file, "  dist_vector = (");
3155           print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3156                                DDR_NB_LOOPS (ddr));
3157           fprintf (dump_file, "  )\n");
3158         }
3159       fprintf (dump_file, ")\n");
3160     }
3161
3162   return true;
3163 }
3164
3165 /* Return the direction for a given distance.
3166    FIXME: Computing dir this way is suboptimal, since dir can catch
3167    cases that dist is unable to represent.  */
3168
3169 static inline enum data_dependence_direction
3170 dir_from_dist (int dist)
3171 {
3172   if (dist > 0)
3173     return dir_positive;
3174   else if (dist < 0)
3175     return dir_negative;
3176   else
3177     return dir_equal;
3178 }
3179
3180 /* Compute the classic per loop direction vector.  DDR is the data
3181    dependence relation to build a vector from.  */
3182
3183 static void
3184 build_classic_dir_vector (struct data_dependence_relation *ddr)
3185 {
3186   unsigned i, j;
3187   lambda_vector dist_v;
3188
3189   FOR_EACH_VEC_ELT (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v)
3190     {
3191       lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3192
3193       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3194         dir_v[j] = dir_from_dist (dist_v[j]);
3195
3196       save_dir_v (ddr, dir_v);
3197     }
3198 }
3199
3200 /* Helper function.  Returns true when there is a dependence between
3201    data references DRA and DRB.  */
3202
3203 static bool
3204 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3205                                struct data_reference *dra,
3206                                struct data_reference *drb,
3207                                struct loop *loop_nest)
3208 {
3209   unsigned int i;
3210   tree last_conflicts;
3211   struct subscript *subscript;
3212
3213   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3214        i++)
3215     {
3216       conflict_function *overlaps_a, *overlaps_b;
3217
3218       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3219                                       DR_ACCESS_FN (drb, i),
3220                                       &overlaps_a, &overlaps_b,
3221                                       &last_conflicts, loop_nest);
3222
3223       if (CF_NOT_KNOWN_P (overlaps_a)
3224           || CF_NOT_KNOWN_P (overlaps_b))
3225         {
3226           finalize_ddr_dependent (ddr, chrec_dont_know);
3227           dependence_stats.num_dependence_undetermined++;
3228           free_conflict_function (overlaps_a);
3229           free_conflict_function (overlaps_b);
3230           return false;
3231         }
3232
3233       else if (CF_NO_DEPENDENCE_P (overlaps_a)
3234                || CF_NO_DEPENDENCE_P (overlaps_b))
3235         {
3236           finalize_ddr_dependent (ddr, chrec_known);
3237           dependence_stats.num_dependence_independent++;
3238           free_conflict_function (overlaps_a);
3239           free_conflict_function (overlaps_b);
3240           return false;
3241         }
3242
3243       else
3244         {
3245           if (SUB_CONFLICTS_IN_A (subscript))
3246             free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3247           if (SUB_CONFLICTS_IN_B (subscript))
3248             free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3249
3250           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3251           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3252           SUB_LAST_CONFLICT (subscript) = last_conflicts;
3253         }
3254     }
3255
3256   return true;
3257 }
3258
3259 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR.  */
3260
3261 static void
3262 subscript_dependence_tester (struct data_dependence_relation *ddr,
3263                              struct loop *loop_nest)
3264 {
3265
3266   if (dump_file && (dump_flags & TDF_DETAILS))
3267     fprintf (dump_file, "(subscript_dependence_tester \n");
3268
3269   if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3270     dependence_stats.num_dependence_dependent++;
3271
3272   compute_subscript_distance (ddr);
3273   if (build_classic_dist_vector (ddr, loop_nest))
3274     build_classic_dir_vector (ddr);
3275
3276   if (dump_file && (dump_flags & TDF_DETAILS))
3277     fprintf (dump_file, ")\n");
3278 }
3279
3280 /* Returns true when all the access functions of A are affine or
3281    constant with respect to LOOP_NEST.  */
3282
3283 static bool
3284 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3285                                            const struct loop *loop_nest)
3286 {
3287   unsigned int i;
3288   VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3289   tree t;
3290
3291   FOR_EACH_VEC_ELT (tree, fns, i, t)
3292     if (!evolution_function_is_invariant_p (t, loop_nest->num)
3293         && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3294       return false;
3295
3296   return true;
3297 }
3298
3299 /* Initializes an equation for an OMEGA problem using the information
3300    contained in the ACCESS_FUN.  Returns true when the operation
3301    succeeded.
3302
3303    PB is the omega constraint system.
3304    EQ is the number of the equation to be initialized.
3305    OFFSET is used for shifting the variables names in the constraints:
3306    a constrain is composed of 2 * the number of variables surrounding
3307    dependence accesses.  OFFSET is set either to 0 for the first n variables,
3308    then it is set to n.
3309    ACCESS_FUN is expected to be an affine chrec.  */
3310
3311 static bool
3312 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3313                        unsigned int offset, tree access_fun,
3314                        struct data_dependence_relation *ddr)
3315 {
3316   switch (TREE_CODE (access_fun))
3317     {
3318     case POLYNOMIAL_CHREC:
3319       {
3320         tree left = CHREC_LEFT (access_fun);
3321         tree right = CHREC_RIGHT (access_fun);
3322         int var = CHREC_VARIABLE (access_fun);
3323         unsigned var_idx;
3324
3325         if (TREE_CODE (right) != INTEGER_CST)
3326           return false;
3327
3328         var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3329         pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3330
3331         /* Compute the innermost loop index.  */
3332         DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3333
3334         if (offset == 0)
3335           pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3336             += int_cst_value (right);
3337
3338         switch (TREE_CODE (left))
3339           {
3340           case POLYNOMIAL_CHREC:
3341             return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3342
3343           case INTEGER_CST:
3344             pb->eqs[eq].coef[0] += int_cst_value (left);
3345             return true;
3346
3347           default:
3348             return false;
3349           }
3350       }
3351
3352     case INTEGER_CST:
3353       pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3354       return true;
3355
3356     default:
3357       return false;
3358     }
3359 }
3360
3361 /* As explained in the comments preceding init_omega_for_ddr, we have
3362    to set up a system for each loop level, setting outer loops
3363    variation to zero, and current loop variation to positive or zero.
3364    Save each lexico positive distance vector.  */
3365
3366 static void
3367 omega_extract_distance_vectors (omega_pb pb,
3368                                 struct data_dependence_relation *ddr)
3369 {
3370   int eq, geq;
3371   unsigned i, j;
3372   struct loop *loopi, *loopj;
3373   enum omega_result res;
3374
3375   /* Set a new problem for each loop in the nest.  The basis is the
3376      problem that we have initialized until now.  On top of this we
3377      add new constraints.  */
3378   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3379          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3380     {
3381       int dist = 0;
3382       omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3383                                            DDR_NB_LOOPS (ddr));
3384
3385       omega_copy_problem (copy, pb);
3386
3387       /* For all the outer loops "loop_j", add "dj = 0".  */
3388       for (j = 0;
3389            j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3390         {
3391           eq = omega_add_zero_eq (copy, omega_black);
3392           copy->eqs[eq].coef[j + 1] = 1;
3393         }
3394
3395       /* For "loop_i", add "0 <= di".  */
3396       geq = omega_add_zero_geq (copy, omega_black);
3397       copy->geqs[geq].coef[i + 1] = 1;
3398
3399       /* Reduce the constraint system, and test that the current
3400          problem is feasible.  */
3401       res = omega_simplify_problem (copy);
3402       if (res == omega_false
3403           || res == omega_unknown
3404           || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3405         goto next_problem;
3406
3407       for (eq = 0; eq < copy->num_subs; eq++)
3408         if (copy->subs[eq].key == (int) i + 1)
3409           {
3410             dist = copy->subs[eq].coef[0];
3411             goto found_dist;
3412           }
3413
3414       if (dist == 0)
3415         {
3416           /* Reinitialize problem...  */
3417           omega_copy_problem (copy, pb);
3418           for (j = 0;
3419                j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3420             {
3421               eq = omega_add_zero_eq (copy, omega_black);
3422               copy->eqs[eq].coef[j + 1] = 1;
3423             }
3424
3425           /* ..., but this time "di = 1".  */
3426           eq = omega_add_zero_eq (copy, omega_black);
3427           copy->eqs[eq].coef[i + 1] = 1;
3428           copy->eqs[eq].coef[0] = -1;
3429
3430           res = omega_simplify_problem (copy);
3431           if (res == omega_false
3432               || res == omega_unknown
3433               || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3434             goto next_problem;
3435
3436           for (eq = 0; eq < copy->num_subs; eq++)
3437             if (copy->subs[eq].key == (int) i + 1)
3438               {
3439                 dist = copy->subs[eq].coef[0];
3440                 goto found_dist;
3441               }
3442         }
3443
3444     found_dist:;
3445       /* Save the lexicographically positive distance vector.  */
3446       if (dist >= 0)
3447         {
3448           lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3449           lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3450
3451           dist_v[i] = dist;
3452
3453           for (eq = 0; eq < copy->num_subs; eq++)
3454             if (copy->subs[eq].key > 0)
3455               {
3456                 dist = copy->subs[eq].coef[0];
3457                 dist_v[copy->subs[eq].key - 1] = dist;
3458               }
3459
3460           for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3461             dir_v[j] = dir_from_dist (dist_v[j]);
3462
3463           save_dist_v (ddr, dist_v);
3464           save_dir_v (ddr, dir_v);
3465         }
3466
3467     next_problem:;
3468       omega_free_problem (copy);
3469     }
3470 }
3471
3472 /* This is called for each subscript of a tuple of data references:
3473    insert an equality for representing the conflicts.  */
3474
3475 static bool
3476 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3477                        struct data_dependence_relation *ddr,
3478                        omega_pb pb, bool *maybe_dependent)
3479 {
3480   int eq;
3481   tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3482                                      TREE_TYPE (access_fun_b));
3483   tree fun_a = chrec_convert (type, access_fun_a, NULL);
3484   tree fun_b = chrec_convert (type, access_fun_b, NULL);
3485   tree difference = chrec_fold_minus (type, fun_a, fun_b);
3486   tree minus_one;
3487
3488   /* When the fun_a - fun_b is not constant, the dependence is not
3489      captured by the classic distance vector representation.  */
3490   if (TREE_CODE (difference) != INTEGER_CST)
3491     return false;
3492
3493   /* ZIV test.  */
3494   if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3495     {
3496       /* There is no dependence.  */
3497       *maybe_dependent = false;
3498       return true;
3499     }
3500
3501   minus_one = build_int_cst (type, -1);
3502   fun_b = chrec_fold_multiply (type, fun_b, minus_one);
3503
3504   eq = omega_add_zero_eq (pb, omega_black);
3505   if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3506       || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3507     /* There is probably a dependence, but the system of
3508        constraints cannot be built: answer "don't know".  */
3509     return false;
3510
3511   /* GCD test.  */
3512   if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3513       && !int_divides_p (lambda_vector_gcd
3514                          ((lambda_vector) &(pb->eqs[eq].coef[1]),
3515                           2 * DDR_NB_LOOPS (ddr)),
3516                          pb->eqs[eq].coef[0]))
3517     {
3518       /* There is no dependence.  */
3519       *maybe_dependent = false;
3520       return true;
3521     }
3522
3523   return true;
3524 }
3525
3526 /* Helper function, same as init_omega_for_ddr but specialized for
3527    data references A and B.  */
3528
3529 static bool
3530 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3531                       struct data_dependence_relation *ddr,
3532                       omega_pb pb, bool *maybe_dependent)
3533 {
3534   unsigned i;
3535   int ineq;
3536   struct loop *loopi;
3537   unsigned nb_loops = DDR_NB_LOOPS (ddr);
3538
3539   /* Insert an equality per subscript.  */
3540   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3541     {
3542       if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3543                                   ddr, pb, maybe_dependent))
3544         return false;
3545       else if (*maybe_dependent == false)
3546         {
3547           /* There is no dependence.  */
3548           DDR_ARE_DEPENDENT (ddr) = chrec_known;
3549           return true;
3550         }
3551     }
3552
3553   /* Insert inequalities: constraints corresponding to the iteration
3554      domain, i.e. the loops surrounding the references "loop_x" and
3555      the distance variables "dx".  The layout of the OMEGA
3556      representation is as follows:
3557      - coef[0] is the constant
3558      - coef[1..nb_loops] are the protected variables that will not be
3559      removed by the solver: the "dx"
3560      - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3561   */
3562   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3563          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3564     {
3565       HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3566
3567       /* 0 <= loop_x */
3568       ineq = omega_add_zero_geq (pb, omega_black);
3569       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3570
3571       /* 0 <= loop_x + dx */
3572       ineq = omega_add_zero_geq (pb, omega_black);
3573       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3574       pb->geqs[ineq].coef[i + 1] = 1;
3575
3576       if (nbi != -1)
3577         {
3578           /* loop_x <= nb_iters */
3579           ineq = omega_add_zero_geq (pb, omega_black);
3580           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3581           pb->geqs[ineq].coef[0] = nbi;
3582
3583           /* loop_x + dx <= nb_iters */
3584           ineq = omega_add_zero_geq (pb, omega_black);
3585           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3586           pb->geqs[ineq].coef[i + 1] = -1;
3587           pb->geqs[ineq].coef[0] = nbi;
3588
3589           /* A step "dx" bigger than nb_iters is not feasible, so
3590              add "0 <= nb_iters + dx",  */
3591           ineq = omega_add_zero_geq (pb, omega_black);
3592           pb->geqs[ineq].coef[i + 1] = 1;
3593           pb->geqs[ineq].coef[0] = nbi;
3594           /* and "dx <= nb_iters".  */
3595           ineq = omega_add_zero_geq (pb, omega_black);
3596           pb->geqs[ineq].coef[i + 1] = -1;
3597           pb->geqs[ineq].coef[0] = nbi;
3598         }
3599     }
3600
3601   omega_extract_distance_vectors (pb, ddr);
3602
3603   return true;
3604 }
3605
3606 /* Sets up the Omega dependence problem for the data dependence
3607    relation DDR.  Returns false when the constraint system cannot be
3608    built, ie. when the test answers "don't know".  Returns true
3609    otherwise, and when independence has been proved (using one of the
3610    trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3611    set MAYBE_DEPENDENT to true.
3612
3613    Example: for setting up the dependence system corresponding to the
3614    conflicting accesses
3615
3616    | loop_i
3617    |   loop_j
3618    |     A[i, i+1] = ...
3619    |     ... A[2*j, 2*(i + j)]
3620    |   endloop_j
3621    | endloop_i
3622
3623    the following constraints come from the iteration domain:
3624
3625    0 <= i <= Ni
3626    0 <= i + di <= Ni
3627    0 <= j <= Nj
3628    0 <= j + dj <= Nj
3629
3630    where di, dj are the distance variables.  The constraints
3631    representing the conflicting elements are:
3632
3633    i = 2 * (j + dj)
3634    i + 1 = 2 * (i + di + j + dj)
3635
3636    For asking that the resulting distance vector (di, dj) be
3637    lexicographically positive, we insert the constraint "di >= 0".  If
3638    "di = 0" in the solution, we fix that component to zero, and we
3639    look at the inner loops: we set a new problem where all the outer
3640    loop distances are zero, and fix this inner component to be
3641    positive.  When one of the components is positive, we save that
3642    distance, and set a new problem where the distance on this loop is
3643    zero, searching for other distances in the inner loops.  Here is
3644    the classic example that illustrates that we have to set for each
3645    inner loop a new problem:
3646
3647    | loop_1
3648    |   loop_2
3649    |     A[10]
3650    |   endloop_2
3651    | endloop_1
3652
3653    we have to save two distances (1, 0) and (0, 1).
3654
3655    Given two array references, refA and refB, we have to set the
3656    dependence problem twice, refA vs. refB and refB vs. refA, and we
3657    cannot do a single test, as refB might occur before refA in the
3658    inner loops, and the contrary when considering outer loops: ex.
3659
3660    | loop_0
3661    |   loop_1
3662    |     loop_2
3663    |       T[{1,+,1}_2][{1,+,1}_1]  // refA
3664    |       T[{2,+,1}_2][{0,+,1}_1]  // refB
3665    |     endloop_2
3666    |   endloop_1
3667    | endloop_0
3668
3669    refB touches the elements in T before refA, and thus for the same
3670    loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3671    but for successive loop_0 iterations, we have (1, -1, 1)
3672
3673    The Omega solver expects the distance variables ("di" in the
3674    previous example) to come first in the constraint system (as
3675    variables to be protected, or "safe" variables), the constraint
3676    system is built using the following layout:
3677
3678    "cst | distance vars | index vars".
3679 */
3680
3681 static bool
3682 init_omega_for_ddr (struct data_dependence_relation *ddr,
3683                     bool *maybe_dependent)
3684 {
3685   omega_pb pb;
3686   bool res = false;
3687
3688   *maybe_dependent = true;
3689
3690   if (same_access_functions (ddr))
3691     {
3692       unsigned j;
3693       lambda_vector dir_v;
3694
3695       /* Save the 0 vector.  */
3696       save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3697       dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3698       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3699         dir_v[j] = dir_equal;
3700       save_dir_v (ddr, dir_v);
3701
3702       /* Save the dependences carried by outer loops.  */
3703       pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3704       res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3705                                   maybe_dependent);
3706       omega_free_problem (pb);
3707       return res;
3708     }
3709
3710   /* Omega expects the protected variables (those that have to be kept
3711      after elimination) to appear first in the constraint system.
3712      These variables are the distance variables.  In the following
3713      initialization we declare NB_LOOPS safe variables, and the total
3714      number of variables for the constraint system is 2*NB_LOOPS.  */
3715   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3716   res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3717                               maybe_dependent);
3718   omega_free_problem (pb);
3719
3720   /* Stop computation if not decidable, or no dependence.  */
3721   if (res == false || *maybe_dependent == false)
3722     return res;
3723
3724   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3725   res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3726                               maybe_dependent);
3727   omega_free_problem (pb);
3728
3729   return res;
3730 }
3731
3732 /* Return true when DDR contains the same information as that stored
3733    in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
3734
3735 static bool
3736 ddr_consistent_p (FILE *file,
3737                   struct data_dependence_relation *ddr,
3738                   VEC (lambda_vector, heap) *dist_vects,
3739                   VEC (lambda_vector, heap) *dir_vects)
3740 {
3741   unsigned int i, j;
3742
3743   /* If dump_file is set, output there.  */
3744   if (dump_file && (dump_flags & TDF_DETAILS))
3745     file = dump_file;
3746
3747   if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3748     {
3749       lambda_vector b_dist_v;
3750       fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3751                VEC_length (lambda_vector, dist_vects),
3752                DDR_NUM_DIST_VECTS (ddr));
3753
3754       fprintf (file, "Banerjee dist vectors:\n");
3755       FOR_EACH_VEC_ELT (lambda_vector, dist_vects, i, b_dist_v)
3756         print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3757
3758       fprintf (file, "Omega dist vectors:\n");
3759       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3760         print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3761
3762       fprintf (file, "data dependence relation:\n");
3763       dump_data_dependence_relation (file, ddr);
3764
3765       fprintf (file, ")\n");
3766       return false;
3767     }
3768
3769   if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3770     {
3771       fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3772                VEC_length (lambda_vector, dir_vects),
3773                DDR_NUM_DIR_VECTS (ddr));
3774       return false;
3775     }
3776
3777   for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3778     {
3779       lambda_vector a_dist_v;
3780       lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3781
3782       /* Distance vectors are not ordered in the same way in the DDR
3783          and in the DIST_VECTS: search for a matching vector.  */
3784       FOR_EACH_VEC_ELT (lambda_vector, dist_vects, j, a_dist_v)
3785         if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3786           break;
3787
3788       if (j == VEC_length (lambda_vector, dist_vects))
3789         {
3790           fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3791           print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3792           fprintf (file, "not found in Omega dist vectors:\n");
3793           print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3794           fprintf (file, "data dependence relation:\n");
3795           dump_data_dependence_relation (file, ddr);
3796           fprintf (file, ")\n");
3797         }
3798     }
3799
3800   for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3801     {
3802       lambda_vector a_dir_v;
3803       lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3804
3805       /* Direction vectors are not ordered in the same way in the DDR
3806          and in the DIR_VECTS: search for a matching vector.  */
3807       FOR_EACH_VEC_ELT (lambda_vector, dir_vects, j, a_dir_v)
3808         if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3809           break;
3810
3811       if (j == VEC_length (lambda_vector, dist_vects))
3812         {
3813           fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3814           print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3815           fprintf (file, "not found in Omega dir vectors:\n");
3816           print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3817           fprintf (file, "data dependence relation:\n");
3818           dump_data_dependence_relation (file, ddr);
3819           fprintf (file, ")\n");
3820         }
3821     }
3822
3823   return true;
3824 }
3825
3826 /* This computes the affine dependence relation between A and B with
3827    respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
3828    independence between two accesses, while CHREC_DONT_KNOW is used
3829    for representing the unknown relation.
3830
3831    Note that it is possible to stop the computation of the dependence
3832    relation the first time we detect a CHREC_KNOWN element for a given
3833    subscript.  */
3834
3835 static void
3836 compute_affine_dependence (struct data_dependence_relation *ddr,
3837                            struct loop *loop_nest)
3838 {
3839   struct data_reference *dra = DDR_A (ddr);
3840   struct data_reference *drb = DDR_B (ddr);
3841
3842   if (dump_file && (dump_flags & TDF_DETAILS))
3843     {
3844       fprintf (dump_file, "(compute_affine_dependence\n");
3845       fprintf (dump_file, "  (stmt_a = \n");
3846       print_gimple_stmt (dump_file, DR_STMT (dra), 0, 0);
3847       fprintf (dump_file, ")\n  (stmt_b = \n");
3848       print_gimple_stmt (dump_file, DR_STMT (drb), 0, 0);
3849       fprintf (dump_file, ")\n");
3850     }
3851
3852   /* Analyze only when the dependence relation is not yet known.  */
3853   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3854       && !DDR_SELF_REFERENCE (ddr))
3855     {
3856       dependence_stats.num_dependence_tests++;
3857
3858       if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3859           && access_functions_are_affine_or_constant_p (drb, loop_nest))
3860         {
3861           if (flag_check_data_deps)
3862             {
3863               /* Compute the dependences using the first algorithm.  */
3864               subscript_dependence_tester (ddr, loop_nest);
3865
3866               if (dump_file && (dump_flags & TDF_DETAILS))
3867                 {
3868                   fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3869                   dump_data_dependence_relation (dump_file, ddr);
3870                 }
3871
3872               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3873                 {
3874                   bool maybe_dependent;
3875                   VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3876
3877                   /* Save the result of the first DD analyzer.  */
3878                   dist_vects = DDR_DIST_VECTS (ddr);
3879                   dir_vects = DDR_DIR_VECTS (ddr);
3880
3881                   /* Reset the information.  */
3882                   DDR_DIST_VECTS (ddr) = NULL;
3883                   DDR_DIR_VECTS (ddr) = NULL;
3884
3885                   /* Compute the same information using Omega.  */
3886                   if (!init_omega_for_ddr (ddr, &maybe_dependent))
3887                     goto csys_dont_know;
3888
3889                   if (dump_file && (dump_flags & TDF_DETAILS))
3890                     {
3891                       fprintf (dump_file, "Omega Analyzer\n");
3892                       dump_data_dependence_relation (dump_file, ddr);
3893                     }
3894
3895                   /* Check that we get the same information.  */
3896                   if (maybe_dependent)
3897                     gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3898                                                   dir_vects));
3899                 }
3900             }
3901           else
3902             subscript_dependence_tester (ddr, loop_nest);
3903         }
3904
3905       /* As a last case, if the dependence cannot be determined, or if
3906          the dependence is considered too difficult to determine, answer
3907          "don't know".  */
3908       else
3909         {
3910         csys_dont_know:;
3911           dependence_stats.num_dependence_undetermined++;
3912
3913           if (dump_file && (dump_flags & TDF_DETAILS))
3914             {
3915               fprintf (dump_file, "Data ref a:\n");
3916               dump_data_reference (dump_file, dra);
3917               fprintf (dump_file, "Data ref b:\n");
3918               dump_data_reference (dump_file, drb);
3919               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3920             }
3921           finalize_ddr_dependent (ddr, chrec_dont_know);
3922         }
3923     }
3924
3925   if (dump_file && (dump_flags & TDF_DETAILS))
3926     fprintf (dump_file, ")\n");
3927 }
3928
3929 /* This computes the dependence relation for the same data
3930    reference into DDR.  */
3931
3932 static void
3933 compute_self_dependence (struct data_dependence_relation *ddr)
3934 {
3935   unsigned int i;
3936   struct subscript *subscript;
3937
3938   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3939     return;
3940
3941   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3942        i++)
3943     {
3944       if (SUB_CONFLICTS_IN_A (subscript))
3945         free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3946       if (SUB_CONFLICTS_IN_B (subscript))
3947         free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3948
3949       /* The accessed index overlaps for each iteration.  */
3950       SUB_CONFLICTS_IN_A (subscript)
3951         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3952       SUB_CONFLICTS_IN_B (subscript)
3953         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3954       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3955     }
3956
3957   /* The distance vector is the zero vector.  */
3958   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3959   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3960 }
3961
3962 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3963    the data references in DATAREFS, in the LOOP_NEST.  When
3964    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3965    relations.  */
3966
3967 void
3968 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3969                          VEC (ddr_p, heap) **dependence_relations,
3970                          VEC (loop_p, heap) *loop_nest,
3971                          bool compute_self_and_rr)
3972 {
3973   struct data_dependence_relation *ddr;
3974   struct data_reference *a, *b;
3975   unsigned int i, j;
3976
3977   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
3978     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3979       if (DR_IS_WRITE (a) || DR_IS_WRITE (b) || compute_self_and_rr)
3980         {
3981           ddr = initialize_data_dependence_relation (a, b, loop_nest);
3982           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3983           if (loop_nest)
3984             compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3985         }
3986
3987   if (compute_self_and_rr)
3988     FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, a)
3989       {
3990         ddr = initialize_data_dependence_relation (a, a, loop_nest);
3991         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3992         compute_self_dependence (ddr);
3993       }
3994 }
3995
3996 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
3997    true if STMT clobbers memory, false otherwise.  */
3998
3999 bool
4000 get_references_in_stmt (gimple stmt, VEC (data_ref_loc, heap) **references)
4001 {
4002   bool clobbers_memory = false;
4003   data_ref_loc *ref;
4004   tree *op0, *op1;
4005   enum gimple_code stmt_code = gimple_code (stmt);
4006
4007   *references = NULL;
4008
4009   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4010      Calls have side-effects, except those to const or pure
4011      functions.  */
4012   if ((stmt_code == GIMPLE_CALL
4013        && !(gimple_call_flags (stmt) & (ECF_CONST | ECF_PURE)))
4014       || (stmt_code == GIMPLE_ASM
4015           && gimple_asm_volatile_p (stmt)))
4016     clobbers_memory = true;
4017
4018   if (!gimple_vuse (stmt))
4019     return clobbers_memory;
4020
4021   if (stmt_code == GIMPLE_ASSIGN)
4022     {
4023       tree base;
4024       op0 = gimple_assign_lhs_ptr (stmt);
4025       op1 = gimple_assign_rhs1_ptr (stmt);
4026
4027       if (DECL_P (*op1)
4028           || (REFERENCE_CLASS_P (*op1)
4029               && (base = get_base_address (*op1))
4030               && TREE_CODE (base) != SSA_NAME))
4031         {
4032           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4033           ref->pos = op1;
4034           ref->is_read = true;
4035         }
4036
4037       if (DECL_P (*op0)
4038           || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4039         {
4040           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4041           ref->pos = op0;
4042           ref->is_read = false;
4043         }
4044     }
4045   else if (stmt_code == GIMPLE_CALL)
4046     {
4047       unsigned i, n = gimple_call_num_args (stmt);
4048
4049       for (i = 0; i < n; i++)
4050         {
4051           op0 = gimple_call_arg_ptr (stmt, i);
4052
4053           if (DECL_P (*op0)
4054               || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4055             {
4056               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4057               ref->pos = op0;
4058               ref->is_read = true;
4059             }
4060         }
4061     }
4062
4063   return clobbers_memory;
4064 }
4065
4066 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
4067    reference, returns false, otherwise returns true.  NEST is the outermost
4068    loop of the loop nest in which the references should be analyzed.  */
4069
4070 bool
4071 find_data_references_in_stmt (struct loop *nest, gimple stmt,
4072                               VEC (data_reference_p, heap) **datarefs)
4073 {
4074   unsigned i;
4075   VEC (data_ref_loc, heap) *references;
4076   data_ref_loc *ref;
4077   bool ret = true;
4078   data_reference_p dr;
4079
4080   if (get_references_in_stmt (stmt, &references))
4081     {
4082       VEC_free (data_ref_loc, heap, references);
4083       return false;
4084     }
4085
4086   FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4087     {
4088       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4089       gcc_assert (dr != NULL);
4090
4091       /* FIXME -- data dependence analysis does not work correctly for objects
4092          with invariant addresses in loop nests.  Let us fail here until the
4093          problem is fixed.  */
4094       if (dr_address_invariant_p (dr) && nest)
4095         {
4096           free_data_ref (dr);
4097           if (dump_file && (dump_flags & TDF_DETAILS))
4098             fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4099           ret = false;
4100           break;
4101         }
4102
4103       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4104     }
4105   VEC_free (data_ref_loc, heap, references);
4106   return ret;
4107 }
4108
4109 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
4110    reference, returns false, otherwise returns true.  NEST is the outermost
4111    loop of the loop nest in which the references should be analyzed.  */
4112
4113 bool
4114 graphite_find_data_references_in_stmt (struct loop *nest, gimple stmt,
4115                                        VEC (data_reference_p, heap) **datarefs)
4116 {
4117   unsigned i;
4118   VEC (data_ref_loc, heap) *references;
4119   data_ref_loc *ref;
4120   bool ret = true;
4121   data_reference_p dr;
4122
4123   if (get_references_in_stmt (stmt, &references))
4124     {
4125       VEC_free (data_ref_loc, heap, references);
4126       return false;
4127     }
4128
4129   FOR_EACH_VEC_ELT (data_ref_loc, references, i, ref)
4130     {
4131       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4132       gcc_assert (dr != NULL);
4133       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4134     }
4135
4136   VEC_free (data_ref_loc, heap, references);
4137   return ret;
4138 }
4139
4140 /* Search the data references in LOOP, and record the information into
4141    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4142    difficult case, returns NULL_TREE otherwise.  */
4143
4144 static tree
4145 find_data_references_in_bb (struct loop *loop, basic_block bb,
4146                             VEC (data_reference_p, heap) **datarefs)
4147 {
4148   gimple_stmt_iterator bsi;
4149
4150   for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4151     {
4152       gimple stmt = gsi_stmt (bsi);
4153
4154       if (!find_data_references_in_stmt (loop, stmt, datarefs))
4155         {
4156           struct data_reference *res;
4157           res = XCNEW (struct data_reference);
4158           VEC_safe_push (data_reference_p, heap, *datarefs, res);
4159
4160           return chrec_dont_know;
4161         }
4162     }
4163
4164   return NULL_TREE;
4165 }
4166
4167 /* Search the data references in LOOP, and record the information into
4168    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4169    difficult case, returns NULL_TREE otherwise.
4170
4171    TODO: This function should be made smarter so that it can handle address
4172    arithmetic as if they were array accesses, etc.  */
4173
4174 tree
4175 find_data_references_in_loop (struct loop *loop,
4176                               VEC (data_reference_p, heap) **datarefs)
4177 {
4178   basic_block bb, *bbs;
4179   unsigned int i;
4180
4181   bbs = get_loop_body_in_dom_order (loop);
4182
4183   for (i = 0; i < loop->num_nodes; i++)
4184     {
4185       bb = bbs[i];
4186
4187       if (find_data_references_in_bb (loop, bb, datarefs) == chrec_dont_know)
4188         {
4189           free (bbs);
4190           return chrec_dont_know;
4191         }
4192     }
4193   free (bbs);
4194
4195   return NULL_TREE;
4196 }
4197
4198 /* Recursive helper function.  */
4199
4200 static bool
4201 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4202 {
4203   /* Inner loops of the nest should not contain siblings.  Example:
4204      when there are two consecutive loops,
4205
4206      | loop_0
4207      |   loop_1
4208      |     A[{0, +, 1}_1]
4209      |   endloop_1
4210      |   loop_2
4211      |     A[{0, +, 1}_2]
4212      |   endloop_2
4213      | endloop_0
4214
4215      the dependence relation cannot be captured by the distance
4216      abstraction.  */
4217   if (loop->next)
4218     return false;
4219
4220   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4221   if (loop->inner)
4222     return find_loop_nest_1 (loop->inner, loop_nest);
4223   return true;
4224 }
4225
4226 /* Return false when the LOOP is not well nested.  Otherwise return
4227    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4228    contain the loops from the outermost to the innermost, as they will
4229    appear in the classic distance vector.  */
4230
4231 bool
4232 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4233 {
4234   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4235   if (loop->inner)
4236     return find_loop_nest_1 (loop->inner, loop_nest);
4237   return true;
4238 }
4239
4240 /* Returns true when the data dependences have been computed, false otherwise.
4241    Given a loop nest LOOP, the following vectors are returned:
4242    DATAREFS is initialized to all the array elements contained in this loop,
4243    DEPENDENCE_RELATIONS contains the relations between the data references.
4244    Compute read-read and self relations if
4245    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4246
4247 bool
4248 compute_data_dependences_for_loop (struct loop *loop,
4249                                    bool compute_self_and_read_read_dependences,
4250                                    VEC (data_reference_p, heap) **datarefs,
4251                                    VEC (ddr_p, heap) **dependence_relations)
4252 {
4253   bool res = true;
4254   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4255
4256   memset (&dependence_stats, 0, sizeof (dependence_stats));
4257
4258   /* If the loop nest is not well formed, or one of the data references
4259      is not computable, give up without spending time to compute other
4260      dependences.  */
4261   if (!loop
4262       || !find_loop_nest (loop, &vloops)
4263       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4264     {
4265       struct data_dependence_relation *ddr;
4266
4267       /* Insert a single relation into dependence_relations:
4268          chrec_dont_know.  */
4269       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4270       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4271       res = false;
4272     }
4273   else
4274     compute_all_dependences (*datarefs, dependence_relations, vloops,
4275                              compute_self_and_read_read_dependences);
4276
4277   if (dump_file && (dump_flags & TDF_STATS))
4278     {
4279       fprintf (dump_file, "Dependence tester statistics:\n");
4280
4281       fprintf (dump_file, "Number of dependence tests: %d\n",
4282                dependence_stats.num_dependence_tests);
4283       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4284                dependence_stats.num_dependence_dependent);
4285       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4286                dependence_stats.num_dependence_independent);
4287       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4288                dependence_stats.num_dependence_undetermined);
4289
4290       fprintf (dump_file, "Number of subscript tests: %d\n",
4291                dependence_stats.num_subscript_tests);
4292       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4293                dependence_stats.num_subscript_undetermined);
4294       fprintf (dump_file, "Number of same subscript function: %d\n",
4295                dependence_stats.num_same_subscript_function);
4296
4297       fprintf (dump_file, "Number of ziv tests: %d\n",
4298                dependence_stats.num_ziv);
4299       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4300                dependence_stats.num_ziv_dependent);
4301       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4302                dependence_stats.num_ziv_independent);
4303       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4304                dependence_stats.num_ziv_unimplemented);
4305
4306       fprintf (dump_file, "Number of siv tests: %d\n",
4307                dependence_stats.num_siv);
4308       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4309                dependence_stats.num_siv_dependent);
4310       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4311                dependence_stats.num_siv_independent);
4312       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4313                dependence_stats.num_siv_unimplemented);
4314
4315       fprintf (dump_file, "Number of miv tests: %d\n",
4316                dependence_stats.num_miv);
4317       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4318                dependence_stats.num_miv_dependent);
4319       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4320                dependence_stats.num_miv_independent);
4321       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4322                dependence_stats.num_miv_unimplemented);
4323     }
4324
4325   return res;
4326 }
4327
4328 /* Returns true when the data dependences for the basic block BB have been
4329    computed, false otherwise.
4330    DATAREFS is initialized to all the array elements contained in this basic
4331    block, DEPENDENCE_RELATIONS contains the relations between the data
4332    references. Compute read-read and self relations if
4333    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4334 bool
4335 compute_data_dependences_for_bb (basic_block bb,
4336                                  bool compute_self_and_read_read_dependences,
4337                                  VEC (data_reference_p, heap) **datarefs,
4338                                  VEC (ddr_p, heap) **dependence_relations)
4339 {
4340   if (find_data_references_in_bb (NULL, bb, datarefs) == chrec_dont_know)
4341     return false;
4342
4343   compute_all_dependences (*datarefs, dependence_relations, NULL,
4344                            compute_self_and_read_read_dependences);
4345   return true;
4346 }
4347
4348 /* Entry point (for testing only).  Analyze all the data references
4349    and the dependence relations in LOOP.
4350
4351    The data references are computed first.
4352
4353    A relation on these nodes is represented by a complete graph.  Some
4354    of the relations could be of no interest, thus the relations can be
4355    computed on demand.
4356
4357    In the following function we compute all the relations.  This is
4358    just a first implementation that is here for:
4359    - for showing how to ask for the dependence relations,
4360    - for the debugging the whole dependence graph,
4361    - for the dejagnu testcases and maintenance.
4362
4363    It is possible to ask only for a part of the graph, avoiding to
4364    compute the whole dependence graph.  The computed dependences are
4365    stored in a knowledge base (KB) such that later queries don't
4366    recompute the same information.  The implementation of this KB is
4367    transparent to the optimizer, and thus the KB can be changed with a
4368    more efficient implementation, or the KB could be disabled.  */
4369 static void
4370 analyze_all_data_dependences (struct loop *loop)
4371 {
4372   unsigned int i;
4373   int nb_data_refs = 10;
4374   VEC (data_reference_p, heap) *datarefs =
4375     VEC_alloc (data_reference_p, heap, nb_data_refs);
4376   VEC (ddr_p, heap) *dependence_relations =
4377     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4378
4379   /* Compute DDs on the whole function.  */
4380   compute_data_dependences_for_loop (loop, false, &datarefs,
4381                                      &dependence_relations);
4382
4383   if (dump_file)
4384     {
4385       dump_data_dependence_relations (dump_file, dependence_relations);
4386       fprintf (dump_file, "\n\n");
4387
4388       if (dump_flags & TDF_DETAILS)
4389         dump_dist_dir_vectors (dump_file, dependence_relations);
4390
4391       if (dump_flags & TDF_STATS)
4392         {
4393           unsigned nb_top_relations = 0;
4394           unsigned nb_bot_relations = 0;
4395           unsigned nb_chrec_relations = 0;
4396           struct data_dependence_relation *ddr;
4397
4398           FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4399             {
4400               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4401                 nb_top_relations++;
4402
4403               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4404                 nb_bot_relations++;
4405
4406               else
4407                 nb_chrec_relations++;
4408             }
4409
4410           gather_stats_on_scev_database ();
4411         }
4412     }
4413
4414   free_dependence_relations (dependence_relations);
4415   free_data_refs (datarefs);
4416 }
4417
4418 /* Computes all the data dependences and check that the results of
4419    several analyzers are the same.  */
4420
4421 void
4422 tree_check_data_deps (void)
4423 {
4424   loop_iterator li;
4425   struct loop *loop_nest;
4426
4427   FOR_EACH_LOOP (li, loop_nest, 0)
4428     analyze_all_data_dependences (loop_nest);
4429 }
4430
4431 /* Free the memory used by a data dependence relation DDR.  */
4432
4433 void
4434 free_dependence_relation (struct data_dependence_relation *ddr)
4435 {
4436   if (ddr == NULL)
4437     return;
4438
4439   if (DDR_SUBSCRIPTS (ddr))
4440     free_subscripts (DDR_SUBSCRIPTS (ddr));
4441   if (DDR_DIST_VECTS (ddr))
4442     VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4443   if (DDR_DIR_VECTS (ddr))
4444     VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4445
4446   free (ddr);
4447 }
4448
4449 /* Free the memory used by the data dependence relations from
4450    DEPENDENCE_RELATIONS.  */
4451
4452 void
4453 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4454 {
4455   unsigned int i;
4456   struct data_dependence_relation *ddr;
4457   VEC (loop_p, heap) *loop_nest = NULL;
4458
4459   FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4460     {
4461       if (ddr == NULL)
4462         continue;
4463       if (loop_nest == NULL)
4464         loop_nest = DDR_LOOP_NEST (ddr);
4465       else
4466         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4467                     || DDR_LOOP_NEST (ddr) == loop_nest);
4468       free_dependence_relation (ddr);
4469     }
4470
4471   if (loop_nest)
4472     VEC_free (loop_p, heap, loop_nest);
4473   VEC_free (ddr_p, heap, dependence_relations);
4474 }
4475
4476 /* Free the memory used by the data references from DATAREFS.  */
4477
4478 void
4479 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4480 {
4481   unsigned int i;
4482   struct data_reference *dr;
4483
4484   FOR_EACH_VEC_ELT (data_reference_p, datarefs, i, dr)
4485     free_data_ref (dr);
4486   VEC_free (data_reference_p, heap, datarefs);
4487 }
4488
4489 \f
4490
4491 /* Dump vertex I in RDG to FILE.  */
4492
4493 void
4494 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4495 {
4496   struct vertex *v = &(rdg->vertices[i]);
4497   struct graph_edge *e;
4498
4499   fprintf (file, "(vertex %d: (%s%s) (in:", i,
4500            RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4501            RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4502
4503   if (v->pred)
4504     for (e = v->pred; e; e = e->pred_next)
4505       fprintf (file, " %d", e->src);
4506
4507   fprintf (file, ") (out:");
4508
4509   if (v->succ)
4510     for (e = v->succ; e; e = e->succ_next)
4511       fprintf (file, " %d", e->dest);
4512
4513   fprintf (file, ")\n");
4514   print_gimple_stmt (file, RDGV_STMT (v), 0, TDF_VOPS|TDF_MEMSYMS);
4515   fprintf (file, ")\n");
4516 }
4517
4518 /* Call dump_rdg_vertex on stderr.  */
4519
4520 DEBUG_FUNCTION void
4521 debug_rdg_vertex (struct graph *rdg, int i)
4522 {
4523   dump_rdg_vertex (stderr, rdg, i);
4524 }
4525
4526 /* Dump component C of RDG to FILE.  If DUMPED is non-null, set the
4527    dumped vertices to that bitmap.  */
4528
4529 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4530 {
4531   int i;
4532
4533   fprintf (file, "(%d\n", c);
4534
4535   for (i = 0; i < rdg->n_vertices; i++)
4536     if (rdg->vertices[i].component == c)
4537       {
4538         if (dumped)
4539           bitmap_set_bit (dumped, i);
4540
4541         dump_rdg_vertex (file, rdg, i);
4542       }
4543
4544   fprintf (file, ")\n");
4545 }
4546
4547 /* Call dump_rdg_vertex on stderr.  */
4548
4549 DEBUG_FUNCTION void
4550 debug_rdg_component (struct graph *rdg, int c)
4551 {
4552   dump_rdg_component (stderr, rdg, c, NULL);
4553 }
4554
4555 /* Dump the reduced dependence graph RDG to FILE.  */
4556
4557 void
4558 dump_rdg (FILE *file, struct graph *rdg)
4559 {
4560   int i;
4561   bitmap dumped = BITMAP_ALLOC (NULL);
4562
4563   fprintf (file, "(rdg\n");
4564
4565   for (i = 0; i < rdg->n_vertices; i++)
4566     if (!bitmap_bit_p (dumped, i))
4567       dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4568
4569   fprintf (file, ")\n");
4570   BITMAP_FREE (dumped);
4571 }
4572
4573 /* Call dump_rdg on stderr.  */
4574
4575 DEBUG_FUNCTION void
4576 debug_rdg (struct graph *rdg)
4577 {
4578   dump_rdg (stderr, rdg);
4579 }
4580
4581 static void
4582 dot_rdg_1 (FILE *file, struct graph *rdg)
4583 {
4584   int i;
4585
4586   fprintf (file, "digraph RDG {\n");
4587
4588   for (i = 0; i < rdg->n_vertices; i++)
4589     {
4590       struct vertex *v = &(rdg->vertices[i]);
4591       struct graph_edge *e;
4592
4593       /* Highlight reads from memory.  */
4594       if (RDG_MEM_READS_STMT (rdg, i))
4595        fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4596
4597       /* Highlight stores to memory.  */
4598       if (RDG_MEM_WRITE_STMT (rdg, i))
4599        fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4600
4601       if (v->succ)
4602        for (e = v->succ; e; e = e->succ_next)
4603          switch (RDGE_TYPE (e))
4604            {
4605            case input_dd:
4606              fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4607              break;
4608
4609            case output_dd:
4610              fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4611              break;
4612
4613            case flow_dd:
4614              /* These are the most common dependences: don't print these. */
4615              fprintf (file, "%d -> %d \n", i, e->dest);
4616              break;
4617
4618            case anti_dd:
4619              fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4620              break;
4621
4622            default:
4623              gcc_unreachable ();
4624            }
4625     }
4626
4627   fprintf (file, "}\n\n");
4628 }
4629
4630 /* Display the Reduced Dependence Graph using dotty.  */
4631 extern void dot_rdg (struct graph *);
4632
4633 DEBUG_FUNCTION void
4634 dot_rdg (struct graph *rdg)
4635 {
4636   /* When debugging, enable the following code.  This cannot be used
4637      in production compilers because it calls "system".  */
4638 #if 0
4639   FILE *file = fopen ("/tmp/rdg.dot", "w");
4640   gcc_assert (file != NULL);
4641
4642   dot_rdg_1 (file, rdg);
4643   fclose (file);
4644
4645   system ("dotty /tmp/rdg.dot &");
4646 #else
4647   dot_rdg_1 (stderr, rdg);
4648 #endif
4649 }
4650
4651 /* This structure is used for recording the mapping statement index in
4652    the RDG.  */
4653
4654 struct GTY(()) rdg_vertex_info
4655 {
4656   gimple stmt;
4657   int index;
4658 };
4659
4660 /* Returns the index of STMT in RDG.  */
4661
4662 int
4663 rdg_vertex_for_stmt (struct graph *rdg, gimple stmt)
4664 {
4665   struct rdg_vertex_info rvi, *slot;
4666
4667   rvi.stmt = stmt;
4668   slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4669
4670   if (!slot)
4671     return -1;
4672
4673   return slot->index;
4674 }
4675
4676 /* Creates an edge in RDG for each distance vector from DDR.  The
4677    order that we keep track of in the RDG is the order in which
4678    statements have to be executed.  */
4679
4680 static void
4681 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4682 {
4683   struct graph_edge *e;
4684   int va, vb;
4685   data_reference_p dra = DDR_A (ddr);
4686   data_reference_p drb = DDR_B (ddr);
4687   unsigned level = ddr_dependence_level (ddr);
4688
4689   /* For non scalar dependences, when the dependence is REVERSED,
4690      statement B has to be executed before statement A.  */
4691   if (level > 0
4692       && !DDR_REVERSED_P (ddr))
4693     {
4694       data_reference_p tmp = dra;
4695       dra = drb;
4696       drb = tmp;
4697     }
4698
4699   va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4700   vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4701
4702   if (va < 0 || vb < 0)
4703     return;
4704
4705   e = add_edge (rdg, va, vb);
4706   e->data = XNEW (struct rdg_edge);
4707
4708   RDGE_LEVEL (e) = level;
4709   RDGE_RELATION (e) = ddr;
4710
4711   /* Determines the type of the data dependence.  */
4712   if (DR_IS_READ (dra) && DR_IS_READ (drb))
4713     RDGE_TYPE (e) = input_dd;
4714   else if (DR_IS_WRITE (dra) && DR_IS_WRITE (drb))
4715     RDGE_TYPE (e) = output_dd;
4716   else if (DR_IS_WRITE (dra) && DR_IS_READ (drb))
4717     RDGE_TYPE (e) = flow_dd;
4718   else if (DR_IS_READ (dra) && DR_IS_WRITE (drb))
4719     RDGE_TYPE (e) = anti_dd;
4720 }
4721
4722 /* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
4723    the index of DEF in RDG.  */
4724
4725 static void
4726 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4727 {
4728   use_operand_p imm_use_p;
4729   imm_use_iterator iterator;
4730
4731   FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4732     {
4733       struct graph_edge *e;
4734       int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4735
4736       if (use < 0)
4737         continue;
4738
4739       e = add_edge (rdg, idef, use);
4740       e->data = XNEW (struct rdg_edge);
4741       RDGE_TYPE (e) = flow_dd;
4742       RDGE_RELATION (e) = NULL;
4743     }
4744 }
4745
4746 /* Creates the edges of the reduced dependence graph RDG.  */
4747
4748 static void
4749 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4750 {
4751   int i;
4752   struct data_dependence_relation *ddr;
4753   def_operand_p def_p;
4754   ssa_op_iter iter;
4755
4756   FOR_EACH_VEC_ELT (ddr_p, ddrs, i, ddr)
4757     if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4758       create_rdg_edge_for_ddr (rdg, ddr);
4759
4760   for (i = 0; i < rdg->n_vertices; i++)
4761     FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4762                               iter, SSA_OP_DEF)
4763       create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4764 }
4765
4766 /* Build the vertices of the reduced dependence graph RDG.  */
4767
4768 void
4769 create_rdg_vertices (struct graph *rdg, VEC (gimple, heap) *stmts)
4770 {
4771   int i, j;
4772   gimple stmt;
4773
4774   FOR_EACH_VEC_ELT (gimple, stmts, i, stmt)
4775     {
4776       VEC (data_ref_loc, heap) *references;
4777       data_ref_loc *ref;
4778       struct vertex *v = &(rdg->vertices[i]);
4779       struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4780       struct rdg_vertex_info **slot;
4781
4782       rvi->stmt = stmt;
4783       rvi->index = i;
4784       slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4785
4786       if (!*slot)
4787         *slot = rvi;
4788       else
4789         free (rvi);
4790
4791       v->data = XNEW (struct rdg_vertex);
4792       RDG_STMT (rdg, i) = stmt;
4793
4794       RDG_MEM_WRITE_STMT (rdg, i) = false;
4795       RDG_MEM_READS_STMT (rdg, i) = false;
4796       if (gimple_code (stmt) == GIMPLE_PHI)
4797         continue;
4798
4799       get_references_in_stmt (stmt, &references);
4800       FOR_EACH_VEC_ELT (data_ref_loc, references, j, ref)
4801         if (!ref->is_read)
4802           RDG_MEM_WRITE_STMT (rdg, i) = true;
4803         else
4804           RDG_MEM_READS_STMT (rdg, i) = true;
4805
4806       VEC_free (data_ref_loc, heap, references);
4807     }
4808 }
4809
4810 /* Initialize STMTS with all the statements of LOOP.  When
4811    INCLUDE_PHIS is true, include also the PHI nodes.  The order in
4812    which we discover statements is important as
4813    generate_loops_for_partition is using the same traversal for
4814    identifying statements. */
4815
4816 static void
4817 stmts_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4818 {
4819   unsigned int i;
4820   basic_block *bbs = get_loop_body_in_dom_order (loop);
4821
4822   for (i = 0; i < loop->num_nodes; i++)
4823     {
4824       basic_block bb = bbs[i];
4825       gimple_stmt_iterator bsi;
4826       gimple stmt;
4827
4828       for (bsi = gsi_start_phis (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4829         VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4830
4831       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4832         {
4833           stmt = gsi_stmt (bsi);
4834           if (gimple_code (stmt) != GIMPLE_LABEL)
4835             VEC_safe_push (gimple, heap, *stmts, stmt);
4836         }
4837     }
4838
4839   free (bbs);
4840 }
4841
4842 /* Returns true when all the dependences are computable.  */
4843
4844 static bool
4845 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4846 {
4847   ddr_p ddr;
4848   unsigned int i;
4849
4850   FOR_EACH_VEC_ELT (ddr_p, dependence_relations, i, ddr)
4851     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4852       return false;
4853
4854   return true;
4855 }
4856
4857 /* Computes a hash function for element ELT.  */
4858
4859 static hashval_t
4860 hash_stmt_vertex_info (const void *elt)
4861 {
4862   const struct rdg_vertex_info *const rvi =
4863     (const struct rdg_vertex_info *) elt;
4864   gimple stmt = rvi->stmt;
4865
4866   return htab_hash_pointer (stmt);
4867 }
4868
4869 /* Compares database elements E1 and E2.  */
4870
4871 static int
4872 eq_stmt_vertex_info (const void *e1, const void *e2)
4873 {
4874   const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4875   const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4876
4877   return elt1->stmt == elt2->stmt;
4878 }
4879
4880 /* Free the element E.  */
4881
4882 static void
4883 hash_stmt_vertex_del (void *e)
4884 {
4885   free (e);
4886 }
4887
4888 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4889    statement of the loop nest, and one edge per data dependence or
4890    scalar dependence.  */
4891
4892 struct graph *
4893 build_empty_rdg (int n_stmts)
4894 {
4895   int nb_data_refs = 10;
4896   struct graph *rdg = new_graph (n_stmts);
4897
4898   rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4899                               eq_stmt_vertex_info, hash_stmt_vertex_del);
4900   return rdg;
4901 }
4902
4903 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4904    statement of the loop nest, and one edge per data dependence or
4905    scalar dependence.  */
4906
4907 struct graph *
4908 build_rdg (struct loop *loop)
4909 {
4910   int nb_data_refs = 10;
4911   struct graph *rdg = NULL;
4912   VEC (ddr_p, heap) *dependence_relations;
4913   VEC (data_reference_p, heap) *datarefs;
4914   VEC (gimple, heap) *stmts = VEC_alloc (gimple, heap, nb_data_refs);
4915
4916   dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4917   datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4918   compute_data_dependences_for_loop (loop,
4919                                      false,
4920                                      &datarefs,
4921                                      &dependence_relations);
4922
4923   if (!known_dependences_p (dependence_relations))
4924     {
4925       free_dependence_relations (dependence_relations);
4926       free_data_refs (datarefs);
4927       VEC_free (gimple, heap, stmts);
4928
4929       return rdg;
4930     }
4931
4932   stmts_from_loop (loop, &stmts);
4933   rdg = build_empty_rdg (VEC_length (gimple, stmts));
4934
4935   rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4936                               eq_stmt_vertex_info, hash_stmt_vertex_del);
4937   create_rdg_vertices (rdg, stmts);
4938   create_rdg_edges (rdg, dependence_relations);
4939
4940   VEC_free (gimple, heap, stmts);
4941   return rdg;
4942 }
4943
4944 /* Free the reduced dependence graph RDG.  */
4945
4946 void
4947 free_rdg (struct graph *rdg)
4948 {
4949   int i;
4950
4951   for (i = 0; i < rdg->n_vertices; i++)
4952     free (rdg->vertices[i].data);
4953
4954   htab_delete (rdg->indices);
4955   free_graph (rdg);
4956 }
4957
4958 /* Initialize STMTS with all the statements of LOOP that contain a
4959    store to memory.  */
4960
4961 void
4962 stores_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
4963 {
4964   unsigned int i;
4965   basic_block *bbs = get_loop_body_in_dom_order (loop);
4966
4967   for (i = 0; i < loop->num_nodes; i++)
4968     {
4969       basic_block bb = bbs[i];
4970       gimple_stmt_iterator bsi;
4971
4972       for (bsi = gsi_start_bb (bb); !gsi_end_p (bsi); gsi_next (&bsi))
4973         if (gimple_vdef (gsi_stmt (bsi)))
4974           VEC_safe_push (gimple, heap, *stmts, gsi_stmt (bsi));
4975     }
4976
4977   free (bbs);
4978 }
4979
4980 /* Returns true when the statement at STMT is of the form "A[i] = 0"
4981    that contains a data reference on its LHS with a stride of the same
4982    size as its unit type.  */
4983
4984 bool
4985 stmt_with_adjacent_zero_store_dr_p (gimple stmt)
4986 {
4987   tree op0, op1;
4988   bool res;
4989   struct data_reference *dr;
4990
4991   if (!stmt
4992       || !gimple_vdef (stmt)
4993       || !is_gimple_assign (stmt)
4994       || !gimple_assign_single_p (stmt)
4995       || !(op1 = gimple_assign_rhs1 (stmt))
4996       || !(integer_zerop (op1) || real_zerop (op1)))
4997     return false;
4998
4999   dr = XCNEW (struct data_reference);
5000   op0 = gimple_assign_lhs (stmt);
5001
5002   DR_STMT (dr) = stmt;
5003   DR_REF (dr) = op0;
5004
5005   res = dr_analyze_innermost (dr)
5006     && stride_of_unit_type_p (DR_STEP (dr), TREE_TYPE (op0));
5007
5008   free_data_ref (dr);
5009   return res;
5010 }
5011
5012 /* Initialize STMTS with all the statements of LOOP that contain a
5013    store to memory of the form "A[i] = 0".  */
5014
5015 void
5016 stores_zero_from_loop (struct loop *loop, VEC (gimple, heap) **stmts)
5017 {
5018   unsigned int i;
5019   basic_block bb;
5020   gimple_stmt_iterator si;
5021   gimple stmt;
5022   basic_block *bbs = get_loop_body_in_dom_order (loop);
5023
5024   for (i = 0; i < loop->num_nodes; i++)
5025     for (bb = bbs[i], si = gsi_start_bb (bb); !gsi_end_p (si); gsi_next (&si))
5026       if ((stmt = gsi_stmt (si))
5027           && stmt_with_adjacent_zero_store_dr_p (stmt))
5028         VEC_safe_push (gimple, heap, *stmts, gsi_stmt (si));
5029
5030   free (bbs);
5031 }
5032
5033 /* For a data reference REF, return the declaration of its base
5034    address or NULL_TREE if the base is not determined.  */
5035
5036 static inline tree
5037 ref_base_address (gimple stmt, data_ref_loc *ref)
5038 {
5039   tree base = NULL_TREE;
5040   tree base_address;
5041   struct data_reference *dr = XCNEW (struct data_reference);
5042
5043   DR_STMT (dr) = stmt;
5044   DR_REF (dr) = *ref->pos;
5045   dr_analyze_innermost (dr);
5046   base_address = DR_BASE_ADDRESS (dr);
5047
5048   if (!base_address)
5049     goto end;
5050
5051   switch (TREE_CODE (base_address))
5052     {
5053     case ADDR_EXPR:
5054       base = TREE_OPERAND (base_address, 0);
5055       break;
5056
5057     default:
5058       base = base_address;
5059       break;
5060     }
5061
5062  end:
5063   free_data_ref (dr);
5064   return base;
5065 }
5066
5067 /* Determines whether the statement from vertex V of the RDG has a
5068    definition used outside the loop that contains this statement.  */
5069
5070 bool
5071 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
5072 {
5073   gimple stmt = RDG_STMT (rdg, v);
5074   struct loop *loop = loop_containing_stmt (stmt);
5075   use_operand_p imm_use_p;
5076   imm_use_iterator iterator;
5077   ssa_op_iter it;
5078   def_operand_p def_p;
5079
5080   if (!loop)
5081     return true;
5082
5083   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
5084     {
5085       FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
5086         {
5087           if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
5088             return true;
5089         }
5090     }
5091
5092   return false;
5093 }
5094
5095 /* Determines whether statements S1 and S2 access to similar memory
5096    locations.  Two memory accesses are considered similar when they
5097    have the same base address declaration, i.e. when their
5098    ref_base_address is the same.  */
5099
5100 bool
5101 have_similar_memory_accesses (gimple s1, gimple s2)
5102 {
5103   bool res = false;
5104   unsigned i, j;
5105   VEC (data_ref_loc, heap) *refs1, *refs2;
5106   data_ref_loc *ref1, *ref2;
5107
5108   get_references_in_stmt (s1, &refs1);
5109   get_references_in_stmt (s2, &refs2);
5110
5111   FOR_EACH_VEC_ELT (data_ref_loc, refs1, i, ref1)
5112     {
5113       tree base1 = ref_base_address (s1, ref1);
5114
5115       if (base1)
5116         FOR_EACH_VEC_ELT (data_ref_loc, refs2, j, ref2)
5117           if (base1 == ref_base_address (s2, ref2))
5118             {
5119               res = true;
5120               goto end;
5121             }
5122     }
5123
5124  end:
5125   VEC_free (data_ref_loc, heap, refs1);
5126   VEC_free (data_ref_loc, heap, refs2);
5127   return res;
5128 }
5129
5130 /* Helper function for the hashtab.  */
5131
5132 static int
5133 have_similar_memory_accesses_1 (const void *s1, const void *s2)
5134 {
5135   return have_similar_memory_accesses (CONST_CAST_GIMPLE ((const_gimple) s1),
5136                                        CONST_CAST_GIMPLE ((const_gimple) s2));
5137 }
5138
5139 /* Helper function for the hashtab.  */
5140
5141 static hashval_t
5142 ref_base_address_1 (const void *s)
5143 {
5144   gimple stmt = CONST_CAST_GIMPLE ((const_gimple) s);
5145   unsigned i;
5146   VEC (data_ref_loc, heap) *refs;
5147   data_ref_loc *ref;
5148   hashval_t res = 0;
5149
5150   get_references_in_stmt (stmt, &refs);
5151
5152   FOR_EACH_VEC_ELT (data_ref_loc, refs, i, ref)
5153     if (!ref->is_read)
5154       {
5155         res = htab_hash_pointer (ref_base_address (stmt, ref));
5156         break;
5157       }
5158
5159   VEC_free (data_ref_loc, heap, refs);
5160   return res;
5161 }
5162
5163 /* Try to remove duplicated write data references from STMTS.  */
5164
5165 void
5166 remove_similar_memory_refs (VEC (gimple, heap) **stmts)
5167 {
5168   unsigned i;
5169   gimple stmt;
5170   htab_t seen = htab_create (VEC_length (gimple, *stmts), ref_base_address_1,
5171                              have_similar_memory_accesses_1, NULL);
5172
5173   for (i = 0; VEC_iterate (gimple, *stmts, i, stmt); )
5174     {
5175       void **slot;
5176
5177       slot = htab_find_slot (seen, stmt, INSERT);
5178
5179       if (*slot)
5180         VEC_ordered_remove (gimple, *stmts, i);
5181       else
5182         {
5183           *slot = (void *) stmt;
5184           i++;
5185         }
5186     }
5187
5188   htab_delete (seen);
5189 }
5190
5191 /* Returns the index of PARAMETER in the parameters vector of the
5192    ACCESS_MATRIX.  If PARAMETER does not exist return -1.  */
5193
5194 int
5195 access_matrix_get_index_for_parameter (tree parameter,
5196                                        struct access_matrix *access_matrix)
5197 {
5198   int i;
5199   VEC (tree,heap) *lambda_parameters = AM_PARAMETERS (access_matrix);
5200   tree lambda_parameter;
5201
5202   FOR_EACH_VEC_ELT (tree, lambda_parameters, i, lambda_parameter)
5203     if (lambda_parameter == parameter)
5204       return i + AM_NB_INDUCTION_VARS (access_matrix);
5205
5206   return -1;
5207 }