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