gcc/tree-data-ref.c

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