gcc/tree-data-ref.c

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