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