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 = resolve_mixers (nest, 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 HOST_WIDE_INT
1853 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
1854 {
1855   gcc_assert (chrec);
1856
1857   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
1858     return int_cst_value (chrec);
1859
1860   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
1861   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
1862 }
1863
1864 #define FLOOR_DIV(x,y) ((x) / (y))
1865
1866 /* Solves the special case of the Diophantine equation:
1867    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
1868
1869    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
1870    number of iterations that loops X and Y run.  The overlaps will be
1871    constructed as evolutions in dimension DIM.  */
1872
1873 static void
1874 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
1875                                          affine_fn *overlaps_a,
1876                                          affine_fn *overlaps_b,
1877                                          tree *last_conflicts, int dim)
1878 {
1879   if (((step_a > 0 && step_b > 0)
1880        || (step_a < 0 && step_b < 0)))
1881     {
1882       int step_overlaps_a, step_overlaps_b;
1883       int gcd_steps_a_b, last_conflict, tau2;
1884
1885       gcd_steps_a_b = gcd (step_a, step_b);
1886       step_overlaps_a = step_b / gcd_steps_a_b;
1887       step_overlaps_b = step_a / gcd_steps_a_b;
1888
1889       if (niter > 0)
1890         {
1891           tau2 = FLOOR_DIV (niter, step_overlaps_a);
1892           tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
1893           last_conflict = tau2;
1894           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
1895         }
1896       else
1897         *last_conflicts = chrec_dont_know;
1898
1899       *overlaps_a = affine_fn_univar (integer_zero_node, dim,
1900                                       build_int_cst (NULL_TREE,
1901                                                      step_overlaps_a));
1902       *overlaps_b = affine_fn_univar (integer_zero_node, dim,
1903                                       build_int_cst (NULL_TREE,
1904                                                      step_overlaps_b));
1905     }
1906
1907   else
1908     {
1909       *overlaps_a = affine_fn_cst (integer_zero_node);
1910       *overlaps_b = affine_fn_cst (integer_zero_node);
1911       *last_conflicts = integer_zero_node;
1912     }
1913 }
1914
1915 /* Solves the special case of a Diophantine equation where CHREC_A is
1916    an affine bivariate function, and CHREC_B is an affine univariate
1917    function.  For example,
1918
1919    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
1920
1921    has the following overlapping functions:
1922
1923    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
1924    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
1925    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
1926
1927    FORNOW: This is a specialized implementation for a case occurring in
1928    a common benchmark.  Implement the general algorithm.  */
1929
1930 static void
1931 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
1932                                       conflict_function **overlaps_a,
1933                                       conflict_function **overlaps_b,
1934                                       tree *last_conflicts)
1935 {
1936   bool xz_p, yz_p, xyz_p;
1937   int step_x, step_y, step_z;
1938   HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
1939   affine_fn overlaps_a_xz, overlaps_b_xz;
1940   affine_fn overlaps_a_yz, overlaps_b_yz;
1941   affine_fn overlaps_a_xyz, overlaps_b_xyz;
1942   affine_fn ova1, ova2, ovb;
1943   tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
1944
1945   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
1946   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
1947   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
1948
1949   niter_x =
1950     estimated_loop_iterations_int (get_chrec_loop (CHREC_LEFT (chrec_a)),
1951                                    false);
1952   niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), false);
1953   niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), false);
1954
1955   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
1956     {
1957       if (dump_file && (dump_flags & TDF_DETAILS))
1958         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
1959
1960       *overlaps_a = conflict_fn_not_known ();
1961       *overlaps_b = conflict_fn_not_known ();
1962       *last_conflicts = chrec_dont_know;
1963       return;
1964     }
1965
1966   niter = MIN (niter_x, niter_z);
1967   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
1968                                            &overlaps_a_xz,
1969                                            &overlaps_b_xz,
1970                                            &last_conflicts_xz, 1);
1971   niter = MIN (niter_y, niter_z);
1972   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
1973                                            &overlaps_a_yz,
1974                                            &overlaps_b_yz,
1975                                            &last_conflicts_yz, 2);
1976   niter = MIN (niter_x, niter_z);
1977   niter = MIN (niter_y, niter);
1978   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
1979                                            &overlaps_a_xyz,
1980                                            &overlaps_b_xyz,
1981                                            &last_conflicts_xyz, 3);
1982
1983   xz_p = !integer_zerop (last_conflicts_xz);
1984   yz_p = !integer_zerop (last_conflicts_yz);
1985   xyz_p = !integer_zerop (last_conflicts_xyz);
1986
1987   if (xz_p || yz_p || xyz_p)
1988     {
1989       ova1 = affine_fn_cst (integer_zero_node);
1990       ova2 = affine_fn_cst (integer_zero_node);
1991       ovb = affine_fn_cst (integer_zero_node);
1992       if (xz_p)
1993         {
1994           affine_fn t0 = ova1;
1995           affine_fn t2 = ovb;
1996
1997           ova1 = affine_fn_plus (ova1, overlaps_a_xz);
1998           ovb = affine_fn_plus (ovb, overlaps_b_xz);
1999           affine_fn_free (t0);
2000           affine_fn_free (t2);
2001           *last_conflicts = last_conflicts_xz;
2002         }
2003       if (yz_p)
2004         {
2005           affine_fn t0 = ova2;
2006           affine_fn t2 = ovb;
2007
2008           ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2009           ovb = affine_fn_plus (ovb, overlaps_b_yz);
2010           affine_fn_free (t0);
2011           affine_fn_free (t2);
2012           *last_conflicts = last_conflicts_yz;
2013         }
2014       if (xyz_p)
2015         {
2016           affine_fn t0 = ova1;
2017           affine_fn t2 = ova2;
2018           affine_fn t4 = ovb;
2019
2020           ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2021           ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2022           ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2023           affine_fn_free (t0);
2024           affine_fn_free (t2);
2025           affine_fn_free (t4);
2026           *last_conflicts = last_conflicts_xyz;
2027         }
2028       *overlaps_a = conflict_fn (2, ova1, ova2);
2029       *overlaps_b = conflict_fn (1, ovb);
2030     }
2031   else
2032     {
2033       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2034       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2035       *last_conflicts = integer_zero_node;
2036     }
2037
2038   affine_fn_free (overlaps_a_xz);
2039   affine_fn_free (overlaps_b_xz);
2040   affine_fn_free (overlaps_a_yz);
2041   affine_fn_free (overlaps_b_yz);
2042   affine_fn_free (overlaps_a_xyz);
2043   affine_fn_free (overlaps_b_xyz);
2044 }
2045
2046 /* Determines the overlapping elements due to accesses CHREC_A and
2047    CHREC_B, that are affine functions.  This function cannot handle
2048    symbolic evolution functions, ie. when initial conditions are
2049    parameters, because it uses lambda matrices of integers.  */
2050
2051 static void
2052 analyze_subscript_affine_affine (tree chrec_a,
2053                                  tree chrec_b,
2054                                  conflict_function **overlaps_a,
2055                                  conflict_function **overlaps_b,
2056                                  tree *last_conflicts)
2057 {
2058   unsigned nb_vars_a, nb_vars_b, dim;
2059   HOST_WIDE_INT init_a, init_b, gamma, gcd_alpha_beta;
2060   lambda_matrix A, U, S;
2061
2062   if (eq_evolutions_p (chrec_a, chrec_b))
2063     {
2064       /* The accessed index overlaps for each iteration in the
2065          loop.  */
2066       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2067       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2068       *last_conflicts = chrec_dont_know;
2069       return;
2070     }
2071   if (dump_file && (dump_flags & TDF_DETAILS))
2072     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2073
2074   /* For determining the initial intersection, we have to solve a
2075      Diophantine equation.  This is the most time consuming part.
2076
2077      For answering to the question: "Is there a dependence?" we have
2078      to prove that there exists a solution to the Diophantine
2079      equation, and that the solution is in the iteration domain,
2080      i.e. the solution is positive or zero, and that the solution
2081      happens before the upper bound loop.nb_iterations.  Otherwise
2082      there is no dependence.  This function outputs a description of
2083      the iterations that hold the intersections.  */
2084
2085   nb_vars_a = nb_vars_in_chrec (chrec_a);
2086   nb_vars_b = nb_vars_in_chrec (chrec_b);
2087
2088   dim = nb_vars_a + nb_vars_b;
2089   U = lambda_matrix_new (dim, dim);
2090   A = lambda_matrix_new (dim, 1);
2091   S = lambda_matrix_new (dim, 1);
2092
2093   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2094   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2095   gamma = init_b - init_a;
2096
2097   /* Don't do all the hard work of solving the Diophantine equation
2098      when we already know the solution: for example,
2099      | {3, +, 1}_1
2100      | {3, +, 4}_2
2101      | gamma = 3 - 3 = 0.
2102      Then the first overlap occurs during the first iterations:
2103      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2104   */
2105   if (gamma == 0)
2106     {
2107       if (nb_vars_a == 1 && nb_vars_b == 1)
2108         {
2109           HOST_WIDE_INT step_a, step_b;
2110           HOST_WIDE_INT niter, niter_a, niter_b;
2111           affine_fn ova, ovb;
2112
2113           niter_a = estimated_loop_iterations_int (get_chrec_loop (chrec_a),
2114                                                    false);
2115           niter_b = estimated_loop_iterations_int (get_chrec_loop (chrec_b),
2116                                                    false);
2117           niter = MIN (niter_a, niter_b);
2118           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2119           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2120
2121           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2122                                                    &ova, &ovb,
2123                                                    last_conflicts, 1);
2124           *overlaps_a = conflict_fn (1, ova);
2125           *overlaps_b = conflict_fn (1, ovb);
2126         }
2127
2128       else if (nb_vars_a == 2 && nb_vars_b == 1)
2129         compute_overlap_steps_for_affine_1_2
2130           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2131
2132       else if (nb_vars_a == 1 && nb_vars_b == 2)
2133         compute_overlap_steps_for_affine_1_2
2134           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2135
2136       else
2137         {
2138           if (dump_file && (dump_flags & TDF_DETAILS))
2139             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2140           *overlaps_a = conflict_fn_not_known ();
2141           *overlaps_b = conflict_fn_not_known ();
2142           *last_conflicts = chrec_dont_know;
2143         }
2144       goto end_analyze_subs_aa;
2145     }
2146
2147   /* U.A = S */
2148   lambda_matrix_right_hermite (A, dim, 1, S, U);
2149
2150   if (S[0][0] < 0)
2151     {
2152       S[0][0] *= -1;
2153       lambda_matrix_row_negate (U, dim, 0);
2154     }
2155   gcd_alpha_beta = S[0][0];
2156
2157   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2158      but that is a quite strange case.  Instead of ICEing, answer
2159      don't know.  */
2160   if (gcd_alpha_beta == 0)
2161     {
2162       *overlaps_a = conflict_fn_not_known ();
2163       *overlaps_b = conflict_fn_not_known ();
2164       *last_conflicts = chrec_dont_know;
2165       goto end_analyze_subs_aa;
2166     }
2167
2168   /* The classic "gcd-test".  */
2169   if (!int_divides_p (gcd_alpha_beta, gamma))
2170     {
2171       /* The "gcd-test" has determined that there is no integer
2172          solution, i.e. there is no dependence.  */
2173       *overlaps_a = conflict_fn_no_dependence ();
2174       *overlaps_b = conflict_fn_no_dependence ();
2175       *last_conflicts = integer_zero_node;
2176     }
2177
2178   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2179   else if (nb_vars_a == 1 && nb_vars_b == 1)
2180     {
2181       /* Both functions should have the same evolution sign.  */
2182       if (((A[0][0] > 0 && -A[1][0] > 0)
2183            || (A[0][0] < 0 && -A[1][0] < 0)))
2184         {
2185           /* The solutions are given by:
2186              |
2187              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2188              |                           [u21 u22]    [y0]
2189
2190              For a given integer t.  Using the following variables,
2191
2192              | i0 = u11 * gamma / gcd_alpha_beta
2193              | j0 = u12 * gamma / gcd_alpha_beta
2194              | i1 = u21
2195              | j1 = u22
2196
2197              the solutions are:
2198
2199              | x0 = i0 + i1 * t,
2200              | y0 = j0 + j1 * t.  */
2201           HOST_WIDE_INT i0, j0, i1, j1;
2202
2203           i0 = U[0][0] * gamma / gcd_alpha_beta;
2204           j0 = U[0][1] * gamma / gcd_alpha_beta;
2205           i1 = U[1][0];
2206           j1 = U[1][1];
2207
2208           if ((i1 == 0 && i0 < 0)
2209               || (j1 == 0 && j0 < 0))
2210             {
2211               /* There is no solution.
2212                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2213                  falls in here, but for the moment we don't look at the
2214                  upper bound of the iteration domain.  */
2215               *overlaps_a = conflict_fn_no_dependence ();
2216               *overlaps_b = conflict_fn_no_dependence ();
2217               *last_conflicts = integer_zero_node;
2218               goto end_analyze_subs_aa;
2219             }
2220
2221           if (i1 > 0 && j1 > 0)
2222             {
2223               HOST_WIDE_INT niter_a = estimated_loop_iterations_int
2224                 (get_chrec_loop (chrec_a), false);
2225               HOST_WIDE_INT niter_b = estimated_loop_iterations_int
2226                 (get_chrec_loop (chrec_b), false);
2227               HOST_WIDE_INT niter = MIN (niter_a, niter_b);
2228
2229               /* (X0, Y0) is a solution of the Diophantine equation:
2230                  "chrec_a (X0) = chrec_b (Y0)".  */
2231               HOST_WIDE_INT tau1 = MAX (CEIL (-i0, i1),
2232                                         CEIL (-j0, j1));
2233               HOST_WIDE_INT x0 = i1 * tau1 + i0;
2234               HOST_WIDE_INT y0 = j1 * tau1 + j0;
2235
2236               /* (X1, Y1) is the smallest positive solution of the eq
2237                  "chrec_a (X1) = chrec_b (Y1)", i.e. this is where the
2238                  first conflict occurs.  */
2239               HOST_WIDE_INT min_multiple = MIN (x0 / i1, y0 / j1);
2240               HOST_WIDE_INT x1 = x0 - i1 * min_multiple;
2241               HOST_WIDE_INT y1 = y0 - j1 * min_multiple;
2242
2243               if (niter > 0)
2244                 {
2245                   HOST_WIDE_INT tau2 = MIN (FLOOR_DIV (niter - i0, i1),
2246                                             FLOOR_DIV (niter - j0, j1));
2247                   HOST_WIDE_INT last_conflict = tau2 - (x1 - i0)/i1;
2248
2249                   /* If the overlap occurs outside of the bounds of the
2250                      loop, there is no dependence.  */
2251                   if (x1 > niter || y1 > niter)
2252                     {
2253                       *overlaps_a = conflict_fn_no_dependence ();
2254                       *overlaps_b = conflict_fn_no_dependence ();
2255                       *last_conflicts = integer_zero_node;
2256                       goto end_analyze_subs_aa;
2257                     }
2258                   else
2259                     *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2260                 }
2261               else
2262                 *last_conflicts = chrec_dont_know;
2263
2264               *overlaps_a
2265                 = conflict_fn (1,
2266                                affine_fn_univar (build_int_cst (NULL_TREE, x1),
2267                                                  1,
2268                                                  build_int_cst (NULL_TREE, i1)));
2269               *overlaps_b
2270                 = conflict_fn (1,
2271                                affine_fn_univar (build_int_cst (NULL_TREE, y1),
2272                                                  1,
2273                                                  build_int_cst (NULL_TREE, j1)));
2274             }
2275           else
2276             {
2277               /* FIXME: For the moment, the upper bound of the
2278                  iteration domain for i and j is not checked.  */
2279               if (dump_file && (dump_flags & TDF_DETAILS))
2280                 fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2281               *overlaps_a = conflict_fn_not_known ();
2282               *overlaps_b = conflict_fn_not_known ();
2283               *last_conflicts = chrec_dont_know;
2284             }
2285         }
2286       else
2287         {
2288           if (dump_file && (dump_flags & TDF_DETAILS))
2289             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2290           *overlaps_a = conflict_fn_not_known ();
2291           *overlaps_b = conflict_fn_not_known ();
2292           *last_conflicts = chrec_dont_know;
2293         }
2294     }
2295   else
2296     {
2297       if (dump_file && (dump_flags & TDF_DETAILS))
2298         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2299       *overlaps_a = conflict_fn_not_known ();
2300       *overlaps_b = conflict_fn_not_known ();
2301       *last_conflicts = chrec_dont_know;
2302     }
2303
2304 end_analyze_subs_aa:
2305   if (dump_file && (dump_flags & TDF_DETAILS))
2306     {
2307       fprintf (dump_file, "  (overlaps_a = ");
2308       dump_conflict_function (dump_file, *overlaps_a);
2309       fprintf (dump_file, ")\n  (overlaps_b = ");
2310       dump_conflict_function (dump_file, *overlaps_b);
2311       fprintf (dump_file, ")\n");
2312       fprintf (dump_file, ")\n");
2313     }
2314 }
2315
2316 /* Returns true when analyze_subscript_affine_affine can be used for
2317    determining the dependence relation between chrec_a and chrec_b,
2318    that contain symbols.  This function modifies chrec_a and chrec_b
2319    such that the analysis result is the same, and such that they don't
2320    contain symbols, and then can safely be passed to the analyzer.
2321
2322    Example: The analysis of the following tuples of evolutions produce
2323    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
2324    vs. {0, +, 1}_1
2325
2326    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
2327    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
2328 */
2329
2330 static bool
2331 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
2332 {
2333   tree diff, type, left_a, left_b, right_b;
2334
2335   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
2336       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
2337     /* FIXME: For the moment not handled.  Might be refined later.  */
2338     return false;
2339
2340   type = chrec_type (*chrec_a);
2341   left_a = CHREC_LEFT (*chrec_a);
2342   left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
2343   diff = chrec_fold_minus (type, left_a, left_b);
2344
2345   if (!evolution_function_is_constant_p (diff))
2346     return false;
2347
2348   if (dump_file && (dump_flags & TDF_DETAILS))
2349     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
2350
2351   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
2352                                      diff, CHREC_RIGHT (*chrec_a));
2353   right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
2354   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
2355                                      build_int_cst (type, 0),
2356                                      right_b);
2357   return true;
2358 }
2359
2360 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
2361    *OVERLAPS_B are initialized to the functions that describe the
2362    relation between the elements accessed twice by CHREC_A and
2363    CHREC_B.  For k >= 0, the following property is verified:
2364
2365    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2366
2367 static void
2368 analyze_siv_subscript (tree chrec_a,
2369                        tree chrec_b,
2370                        conflict_function **overlaps_a,
2371                        conflict_function **overlaps_b,
2372                        tree *last_conflicts)
2373 {
2374   dependence_stats.num_siv++;
2375
2376   if (dump_file && (dump_flags & TDF_DETAILS))
2377     fprintf (dump_file, "(analyze_siv_subscript \n");
2378
2379   if (evolution_function_is_constant_p (chrec_a)
2380       && evolution_function_is_affine_p (chrec_b))
2381     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
2382                                       overlaps_a, overlaps_b, last_conflicts);
2383
2384   else if (evolution_function_is_affine_p (chrec_a)
2385            && evolution_function_is_constant_p (chrec_b))
2386     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
2387                                       overlaps_b, overlaps_a, last_conflicts);
2388
2389   else if (evolution_function_is_affine_p (chrec_a)
2390            && evolution_function_is_affine_p (chrec_b))
2391     {
2392       if (!chrec_contains_symbols (chrec_a)
2393           && !chrec_contains_symbols (chrec_b))
2394         {
2395           analyze_subscript_affine_affine (chrec_a, chrec_b,
2396                                            overlaps_a, overlaps_b,
2397                                            last_conflicts);
2398
2399           if (CF_NOT_KNOWN_P (*overlaps_a)
2400               || CF_NOT_KNOWN_P (*overlaps_b))
2401             dependence_stats.num_siv_unimplemented++;
2402           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2403                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2404             dependence_stats.num_siv_independent++;
2405           else
2406             dependence_stats.num_siv_dependent++;
2407         }
2408       else if (can_use_analyze_subscript_affine_affine (&chrec_a,
2409                                                         &chrec_b))
2410         {
2411           analyze_subscript_affine_affine (chrec_a, chrec_b,
2412                                            overlaps_a, overlaps_b,
2413                                            last_conflicts);
2414
2415           if (CF_NOT_KNOWN_P (*overlaps_a)
2416               || CF_NOT_KNOWN_P (*overlaps_b))
2417             dependence_stats.num_siv_unimplemented++;
2418           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2419                    || CF_NO_DEPENDENCE_P (*overlaps_b))
2420             dependence_stats.num_siv_independent++;
2421           else
2422             dependence_stats.num_siv_dependent++;
2423         }
2424       else
2425         goto siv_subscript_dontknow;
2426     }
2427
2428   else
2429     {
2430     siv_subscript_dontknow:;
2431       if (dump_file && (dump_flags & TDF_DETAILS))
2432         fprintf (dump_file, "siv test failed: unimplemented.\n");
2433       *overlaps_a = conflict_fn_not_known ();
2434       *overlaps_b = conflict_fn_not_known ();
2435       *last_conflicts = chrec_dont_know;
2436       dependence_stats.num_siv_unimplemented++;
2437     }
2438
2439   if (dump_file && (dump_flags & TDF_DETAILS))
2440     fprintf (dump_file, ")\n");
2441 }
2442
2443 /* Returns false if we can prove that the greatest common divisor of the steps
2444    of CHREC does not divide CST, false otherwise.  */
2445
2446 static bool
2447 gcd_of_steps_may_divide_p (const_tree chrec, const_tree cst)
2448 {
2449   HOST_WIDE_INT cd = 0, val;
2450   tree step;
2451
2452   if (!host_integerp (cst, 0))
2453     return true;
2454   val = tree_low_cst (cst, 0);
2455
2456   while (TREE_CODE (chrec) == POLYNOMIAL_CHREC)
2457     {
2458       step = CHREC_RIGHT (chrec);
2459       if (!host_integerp (step, 0))
2460         return true;
2461       cd = gcd (cd, tree_low_cst (step, 0));
2462       chrec = CHREC_LEFT (chrec);
2463     }
2464
2465   return val % cd == 0;
2466 }
2467
2468 /* Analyze a MIV (Multiple Index Variable) subscript with respect to
2469    LOOP_NEST.  *OVERLAPS_A and *OVERLAPS_B are initialized to the
2470    functions that describe the relation between the elements accessed
2471    twice by CHREC_A and CHREC_B.  For k >= 0, the following property
2472    is verified:
2473
2474    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2475
2476 static void
2477 analyze_miv_subscript (tree chrec_a,
2478                        tree chrec_b,
2479                        conflict_function **overlaps_a,
2480                        conflict_function **overlaps_b,
2481                        tree *last_conflicts,
2482                        struct loop *loop_nest)
2483 {
2484   /* FIXME:  This is a MIV subscript, not yet handled.
2485      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
2486      (A[i] vs. A[j]).
2487
2488      In the SIV test we had to solve a Diophantine equation with two
2489      variables.  In the MIV case we have to solve a Diophantine
2490      equation with 2*n variables (if the subscript uses n IVs).
2491   */
2492   tree type, difference;
2493
2494   dependence_stats.num_miv++;
2495   if (dump_file && (dump_flags & TDF_DETAILS))
2496     fprintf (dump_file, "(analyze_miv_subscript \n");
2497
2498   type = signed_type_for_types (TREE_TYPE (chrec_a), TREE_TYPE (chrec_b));
2499   chrec_a = chrec_convert (type, chrec_a, NULL_TREE);
2500   chrec_b = chrec_convert (type, chrec_b, NULL_TREE);
2501   difference = chrec_fold_minus (type, chrec_a, chrec_b);
2502
2503   if (eq_evolutions_p (chrec_a, chrec_b))
2504     {
2505       /* Access functions are the same: all the elements are accessed
2506          in the same order.  */
2507       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2508       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2509       *last_conflicts = estimated_loop_iterations_tree
2510                                 (get_chrec_loop (chrec_a), true);
2511       dependence_stats.num_miv_dependent++;
2512     }
2513
2514   else if (evolution_function_is_constant_p (difference)
2515            /* For the moment, the following is verified:
2516               evolution_function_is_affine_multivariate_p (chrec_a,
2517               loop_nest->num) */
2518            && !gcd_of_steps_may_divide_p (chrec_a, difference))
2519     {
2520       /* testsuite/.../ssa-chrec-33.c
2521          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
2522
2523          The difference is 1, and all the evolution steps are multiples
2524          of 2, consequently there are no overlapping elements.  */
2525       *overlaps_a = conflict_fn_no_dependence ();
2526       *overlaps_b = conflict_fn_no_dependence ();
2527       *last_conflicts = integer_zero_node;
2528       dependence_stats.num_miv_independent++;
2529     }
2530
2531   else if (evolution_function_is_affine_multivariate_p (chrec_a, loop_nest->num)
2532            && !chrec_contains_symbols (chrec_a)
2533            && evolution_function_is_affine_multivariate_p (chrec_b, loop_nest->num)
2534            && !chrec_contains_symbols (chrec_b))
2535     {
2536       /* testsuite/.../ssa-chrec-35.c
2537          {0, +, 1}_2  vs.  {0, +, 1}_3
2538          the overlapping elements are respectively located at iterations:
2539          {0, +, 1}_x and {0, +, 1}_x,
2540          in other words, we have the equality:
2541          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
2542
2543          Other examples:
2544          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
2545          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
2546
2547          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
2548          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
2549       */
2550       analyze_subscript_affine_affine (chrec_a, chrec_b,
2551                                        overlaps_a, overlaps_b, last_conflicts);
2552
2553       if (CF_NOT_KNOWN_P (*overlaps_a)
2554           || CF_NOT_KNOWN_P (*overlaps_b))
2555         dependence_stats.num_miv_unimplemented++;
2556       else if (CF_NO_DEPENDENCE_P (*overlaps_a)
2557                || CF_NO_DEPENDENCE_P (*overlaps_b))
2558         dependence_stats.num_miv_independent++;
2559       else
2560         dependence_stats.num_miv_dependent++;
2561     }
2562
2563   else
2564     {
2565       /* When the analysis is too difficult, answer "don't know".  */
2566       if (dump_file && (dump_flags & TDF_DETAILS))
2567         fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
2568
2569       *overlaps_a = conflict_fn_not_known ();
2570       *overlaps_b = conflict_fn_not_known ();
2571       *last_conflicts = chrec_dont_know;
2572       dependence_stats.num_miv_unimplemented++;
2573     }
2574
2575   if (dump_file && (dump_flags & TDF_DETAILS))
2576     fprintf (dump_file, ")\n");
2577 }
2578
2579 /* Determines the iterations for which CHREC_A is equal to CHREC_B in
2580    with respect to LOOP_NEST.  OVERLAP_ITERATIONS_A and
2581    OVERLAP_ITERATIONS_B are initialized with two functions that
2582    describe the iterations that contain conflicting elements.
2583
2584    Remark: For an integer k >= 0, the following equality is true:
2585
2586    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
2587 */
2588
2589 static void
2590 analyze_overlapping_iterations (tree chrec_a,
2591                                 tree chrec_b,
2592                                 conflict_function **overlap_iterations_a,
2593                                 conflict_function **overlap_iterations_b,
2594                                 tree *last_conflicts, struct loop *loop_nest)
2595 {
2596   unsigned int lnn = loop_nest->num;
2597
2598   dependence_stats.num_subscript_tests++;
2599
2600   if (dump_file && (dump_flags & TDF_DETAILS))
2601     {
2602       fprintf (dump_file, "(analyze_overlapping_iterations \n");
2603       fprintf (dump_file, "  (chrec_a = ");
2604       print_generic_expr (dump_file, chrec_a, 0);
2605       fprintf (dump_file, ")\n  (chrec_b = ");
2606       print_generic_expr (dump_file, chrec_b, 0);
2607       fprintf (dump_file, ")\n");
2608     }
2609
2610   if (chrec_a == NULL_TREE
2611       || chrec_b == NULL_TREE
2612       || chrec_contains_undetermined (chrec_a)
2613       || chrec_contains_undetermined (chrec_b))
2614     {
2615       dependence_stats.num_subscript_undetermined++;
2616
2617       *overlap_iterations_a = conflict_fn_not_known ();
2618       *overlap_iterations_b = conflict_fn_not_known ();
2619     }
2620
2621   /* If they are the same chrec, and are affine, they overlap
2622      on every iteration.  */
2623   else if (eq_evolutions_p (chrec_a, chrec_b)
2624            && evolution_function_is_affine_multivariate_p (chrec_a, lnn))
2625     {
2626       dependence_stats.num_same_subscript_function++;
2627       *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2628       *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2629       *last_conflicts = chrec_dont_know;
2630     }
2631
2632   /* If they aren't the same, and aren't affine, we can't do anything
2633      yet. */
2634   else if ((chrec_contains_symbols (chrec_a)
2635             || chrec_contains_symbols (chrec_b))
2636            && (!evolution_function_is_affine_multivariate_p (chrec_a, lnn)
2637                || !evolution_function_is_affine_multivariate_p (chrec_b, lnn)))
2638     {
2639       dependence_stats.num_subscript_undetermined++;
2640       *overlap_iterations_a = conflict_fn_not_known ();
2641       *overlap_iterations_b = conflict_fn_not_known ();
2642     }
2643
2644   else if (ziv_subscript_p (chrec_a, chrec_b))
2645     analyze_ziv_subscript (chrec_a, chrec_b,
2646                            overlap_iterations_a, overlap_iterations_b,
2647                            last_conflicts);
2648
2649   else if (siv_subscript_p (chrec_a, chrec_b))
2650     analyze_siv_subscript (chrec_a, chrec_b,
2651                            overlap_iterations_a, overlap_iterations_b,
2652                            last_conflicts);
2653
2654   else
2655     analyze_miv_subscript (chrec_a, chrec_b,
2656                            overlap_iterations_a, overlap_iterations_b,
2657                            last_conflicts, loop_nest);
2658
2659   if (dump_file && (dump_flags & TDF_DETAILS))
2660     {
2661       fprintf (dump_file, "  (overlap_iterations_a = ");
2662       dump_conflict_function (dump_file, *overlap_iterations_a);
2663       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
2664       dump_conflict_function (dump_file, *overlap_iterations_b);
2665       fprintf (dump_file, ")\n");
2666       fprintf (dump_file, ")\n");
2667     }
2668 }
2669
2670 /* Helper function for uniquely inserting distance vectors.  */
2671
2672 static void
2673 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
2674 {
2675   unsigned i;
2676   lambda_vector v;
2677
2678   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
2679     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
2680       return;
2681
2682   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
2683 }
2684
2685 /* Helper function for uniquely inserting direction vectors.  */
2686
2687 static void
2688 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
2689 {
2690   unsigned i;
2691   lambda_vector v;
2692
2693   for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
2694     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
2695       return;
2696
2697   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
2698 }
2699
2700 /* Add a distance of 1 on all the loops outer than INDEX.  If we
2701    haven't yet determined a distance for this outer loop, push a new
2702    distance vector composed of the previous distance, and a distance
2703    of 1 for this outer loop.  Example:
2704
2705    | loop_1
2706    |   loop_2
2707    |     A[10]
2708    |   endloop_2
2709    | endloop_1
2710
2711    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
2712    save (0, 1), then we have to save (1, 0).  */
2713
2714 static void
2715 add_outer_distances (struct data_dependence_relation *ddr,
2716                      lambda_vector dist_v, int index)
2717 {
2718   /* For each outer loop where init_v is not set, the accesses are
2719      in dependence of distance 1 in the loop.  */
2720   while (--index >= 0)
2721     {
2722       lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2723       lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
2724       save_v[index] = 1;
2725       save_dist_v (ddr, save_v);
2726     }
2727 }
2728
2729 /* Return false when fail to represent the data dependence as a
2730    distance vector.  INIT_B is set to true when a component has been
2731    added to the distance vector DIST_V.  INDEX_CARRY is then set to
2732    the index in DIST_V that carries the dependence.  */
2733
2734 static bool
2735 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
2736                              struct data_reference *ddr_a,
2737                              struct data_reference *ddr_b,
2738                              lambda_vector dist_v, bool *init_b,
2739                              int *index_carry)
2740 {
2741   unsigned i;
2742   lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2743
2744   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2745     {
2746       tree access_fn_a, access_fn_b;
2747       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
2748
2749       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2750         {
2751           non_affine_dependence_relation (ddr);
2752           return false;
2753         }
2754
2755       access_fn_a = DR_ACCESS_FN (ddr_a, i);
2756       access_fn_b = DR_ACCESS_FN (ddr_b, i);
2757
2758       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
2759           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
2760         {
2761           int dist, index;
2762           int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
2763                                             DDR_LOOP_NEST (ddr));
2764           int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
2765                                             DDR_LOOP_NEST (ddr));
2766
2767           /* The dependence is carried by the outermost loop.  Example:
2768              | loop_1
2769              |   A[{4, +, 1}_1]
2770              |   loop_2
2771              |     A[{5, +, 1}_2]
2772              |   endloop_2
2773              | endloop_1
2774              In this case, the dependence is carried by loop_1.  */
2775           index = index_a < index_b ? index_a : index_b;
2776           *index_carry = MIN (index, *index_carry);
2777
2778           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
2779             {
2780               non_affine_dependence_relation (ddr);
2781               return false;
2782             }
2783
2784           dist = int_cst_value (SUB_DISTANCE (subscript));
2785
2786           /* This is the subscript coupling test.  If we have already
2787              recorded a distance for this loop (a distance coming from
2788              another subscript), it should be the same.  For example,
2789              in the following code, there is no dependence:
2790
2791              | loop i = 0, N, 1
2792              |   T[i+1][i] = ...
2793              |   ... = T[i][i]
2794              | endloop
2795           */
2796           if (init_v[index] != 0 && dist_v[index] != dist)
2797             {
2798               finalize_ddr_dependent (ddr, chrec_known);
2799               return false;
2800             }
2801
2802           dist_v[index] = dist;
2803           init_v[index] = 1;
2804           *init_b = true;
2805         }
2806       else if (!operand_equal_p (access_fn_a, access_fn_b, 0))
2807         {
2808           /* This can be for example an affine vs. constant dependence
2809              (T[i] vs. T[3]) that is not an affine dependence and is
2810              not representable as a distance vector.  */
2811           non_affine_dependence_relation (ddr);
2812           return false;
2813         }
2814     }
2815
2816   return true;
2817 }
2818
2819 /* Return true when the DDR contains only constant access functions.  */
2820
2821 static bool
2822 constant_access_functions (const struct data_dependence_relation *ddr)
2823 {
2824   unsigned i;
2825
2826   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2827     if (!evolution_function_is_constant_p (DR_ACCESS_FN (DDR_A (ddr), i))
2828         || !evolution_function_is_constant_p (DR_ACCESS_FN (DDR_B (ddr), i)))
2829       return false;
2830
2831   return true;
2832 }
2833
2834 /* Helper function for the case where DDR_A and DDR_B are the same
2835    multivariate access function with a constant step.  For an example
2836    see pr34635-1.c.  */
2837
2838 static void
2839 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
2840 {
2841   int x_1, x_2;
2842   tree c_1 = CHREC_LEFT (c_2);
2843   tree c_0 = CHREC_LEFT (c_1);
2844   lambda_vector dist_v;
2845   int v1, v2, cd;
2846
2847   /* Polynomials with more than 2 variables are not handled yet.  When
2848      the evolution steps are parameters, it is not possible to
2849      represent the dependence using classical distance vectors.  */
2850   if (TREE_CODE (c_0) != INTEGER_CST
2851       || TREE_CODE (CHREC_RIGHT (c_1)) != INTEGER_CST
2852       || TREE_CODE (CHREC_RIGHT (c_2)) != INTEGER_CST)
2853     {
2854       DDR_AFFINE_P (ddr) = false;
2855       return;
2856     }
2857
2858   x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
2859   x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
2860
2861   /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
2862   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2863   v1 = int_cst_value (CHREC_RIGHT (c_1));
2864   v2 = int_cst_value (CHREC_RIGHT (c_2));
2865   cd = gcd (v1, v2);
2866   v1 /= cd;
2867   v2 /= cd;
2868
2869   if (v2 < 0)
2870     {
2871       v2 = -v2;
2872       v1 = -v1;
2873     }
2874
2875   dist_v[x_1] = v2;
2876   dist_v[x_2] = -v1;
2877   save_dist_v (ddr, dist_v);
2878
2879   add_outer_distances (ddr, dist_v, x_1);
2880 }
2881
2882 /* Helper function for the case where DDR_A and DDR_B are the same
2883    access functions.  */
2884
2885 static void
2886 add_other_self_distances (struct data_dependence_relation *ddr)
2887 {
2888   lambda_vector dist_v;
2889   unsigned i;
2890   int index_carry = DDR_NB_LOOPS (ddr);
2891
2892   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2893     {
2894       tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
2895
2896       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
2897         {
2898           if (!evolution_function_is_univariate_p (access_fun))
2899             {
2900               if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
2901                 {
2902                   DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
2903                   return;
2904                 }
2905
2906               access_fun = DR_ACCESS_FN (DDR_A (ddr), 0);
2907
2908               if (TREE_CODE (CHREC_LEFT (access_fun)) == POLYNOMIAL_CHREC)
2909                 add_multivariate_self_dist (ddr, access_fun);
2910               else
2911                 /* The evolution step is not constant: it varies in
2912                    the outer loop, so this cannot be represented by a
2913                    distance vector.  For example in pr34635.c the
2914                    evolution is {0, +, {0, +, 4}_1}_2.  */
2915                 DDR_AFFINE_P (ddr) = false;
2916
2917               return;
2918             }
2919
2920           index_carry = MIN (index_carry,
2921                              index_in_loop_nest (CHREC_VARIABLE (access_fun),
2922                                                  DDR_LOOP_NEST (ddr)));
2923         }
2924     }
2925
2926   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2927   add_outer_distances (ddr, dist_v, index_carry);
2928 }
2929
2930 static void
2931 insert_innermost_unit_dist_vector (struct data_dependence_relation *ddr)
2932 {
2933   lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2934
2935   dist_v[DDR_INNER_LOOP (ddr)] = 1;
2936   save_dist_v (ddr, dist_v);
2937 }
2938
2939 /* Adds a unit distance vector to DDR when there is a 0 overlap.  This
2940    is the case for example when access functions are the same and
2941    equal to a constant, as in:
2942
2943    | loop_1
2944    |   A[3] = ...
2945    |   ... = A[3]
2946    | endloop_1
2947
2948    in which case the distance vectors are (0) and (1).  */
2949
2950 static void
2951 add_distance_for_zero_overlaps (struct data_dependence_relation *ddr)
2952 {
2953   unsigned i, j;
2954
2955   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2956     {
2957       subscript_p sub = DDR_SUBSCRIPT (ddr, i);
2958       conflict_function *ca = SUB_CONFLICTS_IN_A (sub);
2959       conflict_function *cb = SUB_CONFLICTS_IN_B (sub);
2960
2961       for (j = 0; j < ca->n; j++)
2962         if (affine_function_zero_p (ca->fns[j]))
2963           {
2964             insert_innermost_unit_dist_vector (ddr);
2965             return;
2966           }
2967
2968       for (j = 0; j < cb->n; j++)
2969         if (affine_function_zero_p (cb->fns[j]))
2970           {
2971             insert_innermost_unit_dist_vector (ddr);
2972             return;
2973           }
2974     }
2975 }
2976
2977 /* Compute the classic per loop distance vector.  DDR is the data
2978    dependence relation to build a vector from.  Return false when fail
2979    to represent the data dependence as a distance vector.  */
2980
2981 static bool
2982 build_classic_dist_vector (struct data_dependence_relation *ddr,
2983                            struct loop *loop_nest)
2984 {
2985   bool init_b = false;
2986   int index_carry = DDR_NB_LOOPS (ddr);
2987   lambda_vector dist_v;
2988
2989   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
2990     return false;
2991
2992   if (same_access_functions (ddr))
2993     {
2994       /* Save the 0 vector.  */
2995       dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
2996       save_dist_v (ddr, dist_v);
2997
2998       if (constant_access_functions (ddr))
2999         add_distance_for_zero_overlaps (ddr);
3000
3001       if (DDR_NB_LOOPS (ddr) > 1)
3002         add_other_self_distances (ddr);
3003
3004       return true;
3005     }
3006
3007   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3008   if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3009                                     dist_v, &init_b, &index_carry))
3010     return false;
3011
3012   /* Save the distance vector if we initialized one.  */
3013   if (init_b)
3014     {
3015       /* Verify a basic constraint: classic distance vectors should
3016          always be lexicographically positive.
3017
3018          Data references are collected in the order of execution of
3019          the program, thus for the following loop
3020
3021          | for (i = 1; i < 100; i++)
3022          |   for (j = 1; j < 100; j++)
3023          |     {
3024          |       t = T[j+1][i-1];  // A
3025          |       T[j][i] = t + 2;  // B
3026          |     }
3027
3028          references are collected following the direction of the wind:
3029          A then B.  The data dependence tests are performed also
3030          following this order, such that we're looking at the distance
3031          separating the elements accessed by A from the elements later
3032          accessed by B.  But in this example, the distance returned by
3033          test_dep (A, B) is lexicographically negative (-1, 1), that
3034          means that the access A occurs later than B with respect to
3035          the outer loop, ie. we're actually looking upwind.  In this
3036          case we solve test_dep (B, A) looking downwind to the
3037          lexicographically positive solution, that returns the
3038          distance vector (1, -1).  */
3039       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3040         {
3041           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3042           if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3043                                               loop_nest))
3044             return false;
3045           compute_subscript_distance (ddr);
3046           if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3047                                             save_v, &init_b, &index_carry))
3048             return false;
3049           save_dist_v (ddr, save_v);
3050           DDR_REVERSED_P (ddr) = true;
3051
3052           /* In this case there is a dependence forward for all the
3053              outer loops:
3054
3055              | for (k = 1; k < 100; k++)
3056              |  for (i = 1; i < 100; i++)
3057              |   for (j = 1; j < 100; j++)
3058              |     {
3059              |       t = T[j+1][i-1];  // A
3060              |       T[j][i] = t + 2;  // B
3061              |     }
3062
3063              the vectors are:
3064              (0,  1, -1)
3065              (1,  1, -1)
3066              (1, -1,  1)
3067           */
3068           if (DDR_NB_LOOPS (ddr) > 1)
3069             {
3070               add_outer_distances (ddr, save_v, index_carry);
3071               add_outer_distances (ddr, dist_v, index_carry);
3072             }
3073         }
3074       else
3075         {
3076           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3077           lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3078
3079           if (DDR_NB_LOOPS (ddr) > 1)
3080             {
3081               lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3082
3083               if (!subscript_dependence_tester_1 (ddr, DDR_B (ddr),
3084                                                   DDR_A (ddr), loop_nest))
3085                 return false;
3086               compute_subscript_distance (ddr);
3087               if (!build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3088                                                 opposite_v, &init_b,
3089                                                 &index_carry))
3090                 return false;
3091
3092               save_dist_v (ddr, save_v);
3093               add_outer_distances (ddr, dist_v, index_carry);
3094               add_outer_distances (ddr, opposite_v, index_carry);
3095             }
3096           else
3097             save_dist_v (ddr, save_v);
3098         }
3099     }
3100   else
3101     {
3102       /* There is a distance of 1 on all the outer loops: Example:
3103          there is a dependence of distance 1 on loop_1 for the array A.
3104
3105          | loop_1
3106          |   A[5] = ...
3107          | endloop
3108       */
3109       add_outer_distances (ddr, dist_v,
3110                            lambda_vector_first_nz (dist_v,
3111                                                    DDR_NB_LOOPS (ddr), 0));
3112     }
3113
3114   if (dump_file && (dump_flags & TDF_DETAILS))
3115     {
3116       unsigned i;
3117
3118       fprintf (dump_file, "(build_classic_dist_vector\n");
3119       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3120         {
3121           fprintf (dump_file, "  dist_vector = (");
3122           print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3123                                DDR_NB_LOOPS (ddr));
3124           fprintf (dump_file, "  )\n");
3125         }
3126       fprintf (dump_file, ")\n");
3127     }
3128
3129   return true;
3130 }
3131
3132 /* Return the direction for a given distance.
3133    FIXME: Computing dir this way is suboptimal, since dir can catch
3134    cases that dist is unable to represent.  */
3135
3136 static inline enum data_dependence_direction
3137 dir_from_dist (int dist)
3138 {
3139   if (dist > 0)
3140     return dir_positive;
3141   else if (dist < 0)
3142     return dir_negative;
3143   else
3144     return dir_equal;
3145 }
3146
3147 /* Compute the classic per loop direction vector.  DDR is the data
3148    dependence relation to build a vector from.  */
3149
3150 static void
3151 build_classic_dir_vector (struct data_dependence_relation *ddr)
3152 {
3153   unsigned i, j;
3154   lambda_vector dist_v;
3155
3156   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
3157     {
3158       lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3159
3160       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3161         dir_v[j] = dir_from_dist (dist_v[j]);
3162
3163       save_dir_v (ddr, dir_v);
3164     }
3165 }
3166
3167 /* Helper function.  Returns true when there is a dependence between
3168    data references DRA and DRB.  */
3169
3170 static bool
3171 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
3172                                struct data_reference *dra,
3173                                struct data_reference *drb,
3174                                struct loop *loop_nest)
3175 {
3176   unsigned int i;
3177   tree last_conflicts;
3178   struct subscript *subscript;
3179
3180   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3181        i++)
3182     {
3183       conflict_function *overlaps_a, *overlaps_b;
3184
3185       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
3186                                       DR_ACCESS_FN (drb, i),
3187                                       &overlaps_a, &overlaps_b,
3188                                       &last_conflicts, loop_nest);
3189
3190       if (CF_NOT_KNOWN_P (overlaps_a)
3191           || CF_NOT_KNOWN_P (overlaps_b))
3192         {
3193           finalize_ddr_dependent (ddr, chrec_dont_know);
3194           dependence_stats.num_dependence_undetermined++;
3195           free_conflict_function (overlaps_a);
3196           free_conflict_function (overlaps_b);
3197           return false;
3198         }
3199
3200       else if (CF_NO_DEPENDENCE_P (overlaps_a)
3201                || CF_NO_DEPENDENCE_P (overlaps_b))
3202         {
3203           finalize_ddr_dependent (ddr, chrec_known);
3204           dependence_stats.num_dependence_independent++;
3205           free_conflict_function (overlaps_a);
3206           free_conflict_function (overlaps_b);
3207           return false;
3208         }
3209
3210       else
3211         {
3212           if (SUB_CONFLICTS_IN_A (subscript))
3213             free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3214           if (SUB_CONFLICTS_IN_B (subscript))
3215             free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3216
3217           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
3218           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
3219           SUB_LAST_CONFLICT (subscript) = last_conflicts;
3220         }
3221     }
3222
3223   return true;
3224 }
3225
3226 /* Computes the conflicting iterations in LOOP_NEST, and initialize DDR.  */
3227
3228 static void
3229 subscript_dependence_tester (struct data_dependence_relation *ddr,
3230                              struct loop *loop_nest)
3231 {
3232
3233   if (dump_file && (dump_flags & TDF_DETAILS))
3234     fprintf (dump_file, "(subscript_dependence_tester \n");
3235
3236   if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr), loop_nest))
3237     dependence_stats.num_dependence_dependent++;
3238
3239   compute_subscript_distance (ddr);
3240   if (build_classic_dist_vector (ddr, loop_nest))
3241     build_classic_dir_vector (ddr);
3242
3243   if (dump_file && (dump_flags & TDF_DETAILS))
3244     fprintf (dump_file, ")\n");
3245 }
3246
3247 /* Returns true when all the access functions of A are affine or
3248    constant with respect to LOOP_NEST.  */
3249
3250 static bool
3251 access_functions_are_affine_or_constant_p (const struct data_reference *a,
3252                                            const struct loop *loop_nest)
3253 {
3254   unsigned int i;
3255   VEC(tree,heap) *fns = DR_ACCESS_FNS (a);
3256   tree t;
3257
3258   for (i = 0; VEC_iterate (tree, fns, i, t); i++)
3259     if (!evolution_function_is_invariant_p (t, loop_nest->num)
3260         && !evolution_function_is_affine_multivariate_p (t, loop_nest->num))
3261       return false;
3262
3263   return true;
3264 }
3265
3266 /* Initializes an equation for an OMEGA problem using the information
3267    contained in the ACCESS_FUN.  Returns true when the operation
3268    succeeded.
3269
3270    PB is the omega constraint system.
3271    EQ is the number of the equation to be initialized.
3272    OFFSET is used for shifting the variables names in the constraints:
3273    a constrain is composed of 2 * the number of variables surrounding
3274    dependence accesses.  OFFSET is set either to 0 for the first n variables,
3275    then it is set to n.
3276    ACCESS_FUN is expected to be an affine chrec.  */
3277
3278 static bool
3279 init_omega_eq_with_af (omega_pb pb, unsigned eq,
3280                        unsigned int offset, tree access_fun,
3281                        struct data_dependence_relation *ddr)
3282 {
3283   switch (TREE_CODE (access_fun))
3284     {
3285     case POLYNOMIAL_CHREC:
3286       {
3287         tree left = CHREC_LEFT (access_fun);
3288         tree right = CHREC_RIGHT (access_fun);
3289         int var = CHREC_VARIABLE (access_fun);
3290         unsigned var_idx;
3291
3292         if (TREE_CODE (right) != INTEGER_CST)
3293           return false;
3294
3295         var_idx = index_in_loop_nest (var, DDR_LOOP_NEST (ddr));
3296         pb->eqs[eq].coef[offset + var_idx + 1] = int_cst_value (right);
3297
3298         /* Compute the innermost loop index.  */
3299         DDR_INNER_LOOP (ddr) = MAX (DDR_INNER_LOOP (ddr), var_idx);
3300
3301         if (offset == 0)
3302           pb->eqs[eq].coef[var_idx + DDR_NB_LOOPS (ddr) + 1]
3303             += int_cst_value (right);
3304
3305         switch (TREE_CODE (left))
3306           {
3307           case POLYNOMIAL_CHREC:
3308             return init_omega_eq_with_af (pb, eq, offset, left, ddr);
3309
3310           case INTEGER_CST:
3311             pb->eqs[eq].coef[0] += int_cst_value (left);
3312             return true;
3313
3314           default:
3315             return false;
3316           }
3317       }
3318
3319     case INTEGER_CST:
3320       pb->eqs[eq].coef[0] += int_cst_value (access_fun);
3321       return true;
3322
3323     default:
3324       return false;
3325     }
3326 }
3327
3328 /* As explained in the comments preceding init_omega_for_ddr, we have
3329    to set up a system for each loop level, setting outer loops
3330    variation to zero, and current loop variation to positive or zero.
3331    Save each lexico positive distance vector.  */
3332
3333 static void
3334 omega_extract_distance_vectors (omega_pb pb,
3335                                 struct data_dependence_relation *ddr)
3336 {
3337   int eq, geq;
3338   unsigned i, j;
3339   struct loop *loopi, *loopj;
3340   enum omega_result res;
3341
3342   /* Set a new problem for each loop in the nest.  The basis is the
3343      problem that we have initialized until now.  On top of this we
3344      add new constraints.  */
3345   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3346          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3347     {
3348       int dist = 0;
3349       omega_pb copy = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr),
3350                                            DDR_NB_LOOPS (ddr));
3351
3352       omega_copy_problem (copy, pb);
3353
3354       /* For all the outer loops "loop_j", add "dj = 0".  */
3355       for (j = 0;
3356            j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3357         {
3358           eq = omega_add_zero_eq (copy, omega_black);
3359           copy->eqs[eq].coef[j + 1] = 1;
3360         }
3361
3362       /* For "loop_i", add "0 <= di".  */
3363       geq = omega_add_zero_geq (copy, omega_black);
3364       copy->geqs[geq].coef[i + 1] = 1;
3365
3366       /* Reduce the constraint system, and test that the current
3367          problem is feasible.  */
3368       res = omega_simplify_problem (copy);
3369       if (res == omega_false
3370           || res == omega_unknown
3371           || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3372         goto next_problem;
3373
3374       for (eq = 0; eq < copy->num_subs; eq++)
3375         if (copy->subs[eq].key == (int) i + 1)
3376           {
3377             dist = copy->subs[eq].coef[0];
3378             goto found_dist;
3379           }
3380
3381       if (dist == 0)
3382         {
3383           /* Reinitialize problem...  */
3384           omega_copy_problem (copy, pb);
3385           for (j = 0;
3386                j < i && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), j, loopj); j++)
3387             {
3388               eq = omega_add_zero_eq (copy, omega_black);
3389               copy->eqs[eq].coef[j + 1] = 1;
3390             }
3391
3392           /* ..., but this time "di = 1".  */
3393           eq = omega_add_zero_eq (copy, omega_black);
3394           copy->eqs[eq].coef[i + 1] = 1;
3395           copy->eqs[eq].coef[0] = -1;
3396
3397           res = omega_simplify_problem (copy);
3398           if (res == omega_false
3399               || res == omega_unknown
3400               || copy->num_geqs > (int) DDR_NB_LOOPS (ddr))
3401             goto next_problem;
3402
3403           for (eq = 0; eq < copy->num_subs; eq++)
3404             if (copy->subs[eq].key == (int) i + 1)
3405               {
3406                 dist = copy->subs[eq].coef[0];
3407                 goto found_dist;
3408               }
3409         }
3410
3411     found_dist:;
3412       /* Save the lexicographically positive distance vector.  */
3413       if (dist >= 0)
3414         {
3415           lambda_vector dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3416           lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3417
3418           dist_v[i] = dist;
3419
3420           for (eq = 0; eq < copy->num_subs; eq++)
3421             if (copy->subs[eq].key > 0)
3422               {
3423                 dist = copy->subs[eq].coef[0];
3424                 dist_v[copy->subs[eq].key - 1] = dist;
3425               }
3426
3427           for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3428             dir_v[j] = dir_from_dist (dist_v[j]);
3429
3430           save_dist_v (ddr, dist_v);
3431           save_dir_v (ddr, dir_v);
3432         }
3433
3434     next_problem:;
3435       omega_free_problem (copy);
3436     }
3437 }
3438
3439 /* This is called for each subscript of a tuple of data references:
3440    insert an equality for representing the conflicts.  */
3441
3442 static bool
3443 omega_setup_subscript (tree access_fun_a, tree access_fun_b,
3444                        struct data_dependence_relation *ddr,
3445                        omega_pb pb, bool *maybe_dependent)
3446 {
3447   int eq;
3448   tree type = signed_type_for_types (TREE_TYPE (access_fun_a),
3449                                      TREE_TYPE (access_fun_b));
3450   tree fun_a = chrec_convert (type, access_fun_a, NULL_TREE);
3451   tree fun_b = chrec_convert (type, access_fun_b, NULL_TREE);
3452   tree difference = chrec_fold_minus (type, fun_a, fun_b);
3453
3454   /* When the fun_a - fun_b is not constant, the dependence is not
3455      captured by the classic distance vector representation.  */
3456   if (TREE_CODE (difference) != INTEGER_CST)
3457     return false;
3458
3459   /* ZIV test.  */
3460   if (ziv_subscript_p (fun_a, fun_b) && !integer_zerop (difference))
3461     {
3462       /* There is no dependence.  */
3463       *maybe_dependent = false;
3464       return true;
3465     }
3466
3467   fun_b = chrec_fold_multiply (type, fun_b, integer_minus_one_node);
3468
3469   eq = omega_add_zero_eq (pb, omega_black);
3470   if (!init_omega_eq_with_af (pb, eq, DDR_NB_LOOPS (ddr), fun_a, ddr)
3471       || !init_omega_eq_with_af (pb, eq, 0, fun_b, ddr))
3472     /* There is probably a dependence, but the system of
3473        constraints cannot be built: answer "don't know".  */
3474     return false;
3475
3476   /* GCD test.  */
3477   if (DDR_NB_LOOPS (ddr) != 0 && pb->eqs[eq].coef[0]
3478       && !int_divides_p (lambda_vector_gcd
3479                          ((lambda_vector) &(pb->eqs[eq].coef[1]),
3480                           2 * DDR_NB_LOOPS (ddr)),
3481                          pb->eqs[eq].coef[0]))
3482     {
3483       /* There is no dependence.  */
3484       *maybe_dependent = false;
3485       return true;
3486     }
3487
3488   return true;
3489 }
3490
3491 /* Helper function, same as init_omega_for_ddr but specialized for
3492    data references A and B.  */
3493
3494 static bool
3495 init_omega_for_ddr_1 (struct data_reference *dra, struct data_reference *drb,
3496                       struct data_dependence_relation *ddr,
3497                       omega_pb pb, bool *maybe_dependent)
3498 {
3499   unsigned i;
3500   int ineq;
3501   struct loop *loopi;
3502   unsigned nb_loops = DDR_NB_LOOPS (ddr);
3503
3504   /* Insert an equality per subscript.  */
3505   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3506     {
3507       if (!omega_setup_subscript (DR_ACCESS_FN (dra, i), DR_ACCESS_FN (drb, i),
3508                                   ddr, pb, maybe_dependent))
3509         return false;
3510       else if (*maybe_dependent == false)
3511         {
3512           /* There is no dependence.  */
3513           DDR_ARE_DEPENDENT (ddr) = chrec_known;
3514           return true;
3515         }
3516     }
3517
3518   /* Insert inequalities: constraints corresponding to the iteration
3519      domain, i.e. the loops surrounding the references "loop_x" and
3520      the distance variables "dx".  The layout of the OMEGA
3521      representation is as follows:
3522      - coef[0] is the constant
3523      - coef[1..nb_loops] are the protected variables that will not be
3524      removed by the solver: the "dx"
3525      - coef[nb_loops + 1, 2*nb_loops] are the loop variables: "loop_x".
3526   */
3527   for (i = 0; i <= DDR_INNER_LOOP (ddr)
3528          && VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
3529     {
3530       HOST_WIDE_INT nbi = estimated_loop_iterations_int (loopi, false);
3531
3532       /* 0 <= loop_x */
3533       ineq = omega_add_zero_geq (pb, omega_black);
3534       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3535
3536       /* 0 <= loop_x + dx */
3537       ineq = omega_add_zero_geq (pb, omega_black);
3538       pb->geqs[ineq].coef[i + nb_loops + 1] = 1;
3539       pb->geqs[ineq].coef[i + 1] = 1;
3540
3541       if (nbi != -1)
3542         {
3543           /* loop_x <= nb_iters */
3544           ineq = omega_add_zero_geq (pb, omega_black);
3545           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3546           pb->geqs[ineq].coef[0] = nbi;
3547
3548           /* loop_x + dx <= nb_iters */
3549           ineq = omega_add_zero_geq (pb, omega_black);
3550           pb->geqs[ineq].coef[i + nb_loops + 1] = -1;
3551           pb->geqs[ineq].coef[i + 1] = -1;
3552           pb->geqs[ineq].coef[0] = nbi;
3553
3554           /* A step "dx" bigger than nb_iters is not feasible, so
3555              add "0 <= nb_iters + dx",  */
3556           ineq = omega_add_zero_geq (pb, omega_black);
3557           pb->geqs[ineq].coef[i + 1] = 1;
3558           pb->geqs[ineq].coef[0] = nbi;
3559           /* and "dx <= nb_iters".  */
3560           ineq = omega_add_zero_geq (pb, omega_black);
3561           pb->geqs[ineq].coef[i + 1] = -1;
3562           pb->geqs[ineq].coef[0] = nbi;
3563         }
3564     }
3565
3566   omega_extract_distance_vectors (pb, ddr);
3567
3568   return true;
3569 }
3570
3571 /* Sets up the Omega dependence problem for the data dependence
3572    relation DDR.  Returns false when the constraint system cannot be
3573    built, ie. when the test answers "don't know".  Returns true
3574    otherwise, and when independence has been proved (using one of the
3575    trivial dependence test), set MAYBE_DEPENDENT to false, otherwise
3576    set MAYBE_DEPENDENT to true.
3577
3578    Example: for setting up the dependence system corresponding to the
3579    conflicting accesses
3580
3581    | loop_i
3582    |   loop_j
3583    |     A[i, i+1] = ...
3584    |     ... A[2*j, 2*(i + j)]
3585    |   endloop_j
3586    | endloop_i
3587
3588    the following constraints come from the iteration domain:
3589
3590    0 <= i <= Ni
3591    0 <= i + di <= Ni
3592    0 <= j <= Nj
3593    0 <= j + dj <= Nj
3594
3595    where di, dj are the distance variables.  The constraints
3596    representing the conflicting elements are:
3597
3598    i = 2 * (j + dj)
3599    i + 1 = 2 * (i + di + j + dj)
3600
3601    For asking that the resulting distance vector (di, dj) be
3602    lexicographically positive, we insert the constraint "di >= 0".  If
3603    "di = 0" in the solution, we fix that component to zero, and we
3604    look at the inner loops: we set a new problem where all the outer
3605    loop distances are zero, and fix this inner component to be
3606    positive.  When one of the components is positive, we save that
3607    distance, and set a new problem where the distance on this loop is
3608    zero, searching for other distances in the inner loops.  Here is
3609    the classic example that illustrates that we have to set for each
3610    inner loop a new problem:
3611
3612    | loop_1
3613    |   loop_2
3614    |     A[10]
3615    |   endloop_2
3616    | endloop_1
3617
3618    we have to save two distances (1, 0) and (0, 1).
3619
3620    Given two array references, refA and refB, we have to set the
3621    dependence problem twice, refA vs. refB and refB vs. refA, and we
3622    cannot do a single test, as refB might occur before refA in the
3623    inner loops, and the contrary when considering outer loops: ex.
3624
3625    | loop_0
3626    |   loop_1
3627    |     loop_2
3628    |       T[{1,+,1}_2][{1,+,1}_1]  // refA
3629    |       T[{2,+,1}_2][{0,+,1}_1]  // refB
3630    |     endloop_2
3631    |   endloop_1
3632    | endloop_0
3633
3634    refB touches the elements in T before refA, and thus for the same
3635    loop_0 refB precedes refA: ie. the distance vector (0, 1, -1)
3636    but for successive loop_0 iterations, we have (1, -1, 1)
3637
3638    The Omega solver expects the distance variables ("di" in the
3639    previous example) to come first in the constraint system (as
3640    variables to be protected, or "safe" variables), the constraint
3641    system is built using the following layout:
3642
3643    "cst | distance vars | index vars".
3644 */
3645
3646 static bool
3647 init_omega_for_ddr (struct data_dependence_relation *ddr,
3648                     bool *maybe_dependent)
3649 {
3650   omega_pb pb;
3651   bool res = false;
3652
3653   *maybe_dependent = true;
3654
3655   if (same_access_functions (ddr))
3656     {
3657       unsigned j;
3658       lambda_vector dir_v;
3659
3660       /* Save the 0 vector.  */
3661       save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3662       dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3663       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
3664         dir_v[j] = dir_equal;
3665       save_dir_v (ddr, dir_v);
3666
3667       /* Save the dependences carried by outer loops.  */
3668       pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3669       res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3670                                   maybe_dependent);
3671       omega_free_problem (pb);
3672       return res;
3673     }
3674
3675   /* Omega expects the protected variables (those that have to be kept
3676      after elimination) to appear first in the constraint system.
3677      These variables are the distance variables.  In the following
3678      initialization we declare NB_LOOPS safe variables, and the total
3679      number of variables for the constraint system is 2*NB_LOOPS.  */
3680   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3681   res = init_omega_for_ddr_1 (DDR_A (ddr), DDR_B (ddr), ddr, pb,
3682                               maybe_dependent);
3683   omega_free_problem (pb);
3684
3685   /* Stop computation if not decidable, or no dependence.  */
3686   if (res == false || *maybe_dependent == false)
3687     return res;
3688
3689   pb = omega_alloc_problem (2 * DDR_NB_LOOPS (ddr), DDR_NB_LOOPS (ddr));
3690   res = init_omega_for_ddr_1 (DDR_B (ddr), DDR_A (ddr), ddr, pb,
3691                               maybe_dependent);
3692   omega_free_problem (pb);
3693
3694   return res;
3695 }
3696
3697 /* Return true when DDR contains the same information as that stored
3698    in DIR_VECTS and in DIST_VECTS, return false otherwise.   */
3699
3700 static bool
3701 ddr_consistent_p (FILE *file,
3702                   struct data_dependence_relation *ddr,
3703                   VEC (lambda_vector, heap) *dist_vects,
3704                   VEC (lambda_vector, heap) *dir_vects)
3705 {
3706   unsigned int i, j;
3707
3708   /* If dump_file is set, output there.  */
3709   if (dump_file && (dump_flags & TDF_DETAILS))
3710     file = dump_file;
3711
3712   if (VEC_length (lambda_vector, dist_vects) != DDR_NUM_DIST_VECTS (ddr))
3713     {
3714       lambda_vector b_dist_v;
3715       fprintf (file, "\n(Number of distance vectors differ: Banerjee has %d, Omega has %d.\n",
3716                VEC_length (lambda_vector, dist_vects),
3717                DDR_NUM_DIST_VECTS (ddr));
3718
3719       fprintf (file, "Banerjee dist vectors:\n");
3720       for (i = 0; VEC_iterate (lambda_vector, dist_vects, i, b_dist_v); i++)
3721         print_lambda_vector (file, b_dist_v, DDR_NB_LOOPS (ddr));
3722
3723       fprintf (file, "Omega dist vectors:\n");
3724       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3725         print_lambda_vector (file, DDR_DIST_VECT (ddr, i), DDR_NB_LOOPS (ddr));
3726
3727       fprintf (file, "data dependence relation:\n");
3728       dump_data_dependence_relation (file, ddr);
3729
3730       fprintf (file, ")\n");
3731       return false;
3732     }
3733
3734   if (VEC_length (lambda_vector, dir_vects) != DDR_NUM_DIR_VECTS (ddr))
3735     {
3736       fprintf (file, "\n(Number of direction vectors differ: Banerjee has %d, Omega has %d.)\n",
3737                VEC_length (lambda_vector, dir_vects),
3738                DDR_NUM_DIR_VECTS (ddr));
3739       return false;
3740     }
3741
3742   for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3743     {
3744       lambda_vector a_dist_v;
3745       lambda_vector b_dist_v = DDR_DIST_VECT (ddr, i);
3746
3747       /* Distance vectors are not ordered in the same way in the DDR
3748          and in the DIST_VECTS: search for a matching vector.  */
3749       for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, a_dist_v); j++)
3750         if (lambda_vector_equal (a_dist_v, b_dist_v, DDR_NB_LOOPS (ddr)))
3751           break;
3752
3753       if (j == VEC_length (lambda_vector, dist_vects))
3754         {
3755           fprintf (file, "\n(Dist vectors from the first dependence analyzer:\n");
3756           print_dist_vectors (file, dist_vects, DDR_NB_LOOPS (ddr));
3757           fprintf (file, "not found in Omega dist vectors:\n");
3758           print_dist_vectors (file, DDR_DIST_VECTS (ddr), DDR_NB_LOOPS (ddr));
3759           fprintf (file, "data dependence relation:\n");
3760           dump_data_dependence_relation (file, ddr);
3761           fprintf (file, ")\n");
3762         }
3763     }
3764
3765   for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
3766     {
3767       lambda_vector a_dir_v;
3768       lambda_vector b_dir_v = DDR_DIR_VECT (ddr, i);
3769
3770       /* Direction vectors are not ordered in the same way in the DDR
3771          and in the DIR_VECTS: search for a matching vector.  */
3772       for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, a_dir_v); j++)
3773         if (lambda_vector_equal (a_dir_v, b_dir_v, DDR_NB_LOOPS (ddr)))
3774           break;
3775
3776       if (j == VEC_length (lambda_vector, dist_vects))
3777         {
3778           fprintf (file, "\n(Dir vectors from the first dependence analyzer:\n");
3779           print_dir_vectors (file, dir_vects, DDR_NB_LOOPS (ddr));
3780           fprintf (file, "not found in Omega dir vectors:\n");
3781           print_dir_vectors (file, DDR_DIR_VECTS (ddr), DDR_NB_LOOPS (ddr));
3782           fprintf (file, "data dependence relation:\n");
3783           dump_data_dependence_relation (file, ddr);
3784           fprintf (file, ")\n");
3785         }
3786     }
3787
3788   return true;
3789 }
3790
3791 /* This computes the affine dependence relation between A and B with
3792    respect to LOOP_NEST.  CHREC_KNOWN is used for representing the
3793    independence between two accesses, while CHREC_DONT_KNOW is used
3794    for representing the unknown relation.
3795
3796    Note that it is possible to stop the computation of the dependence
3797    relation the first time we detect a CHREC_KNOWN element for a given
3798    subscript.  */
3799
3800 static void
3801 compute_affine_dependence (struct data_dependence_relation *ddr,
3802                            struct loop *loop_nest)
3803 {
3804   struct data_reference *dra = DDR_A (ddr);
3805   struct data_reference *drb = DDR_B (ddr);
3806
3807   if (dump_file && (dump_flags & TDF_DETAILS))
3808     {
3809       fprintf (dump_file, "(compute_affine_dependence\n");
3810       fprintf (dump_file, "  (stmt_a = \n");
3811       print_generic_expr (dump_file, DR_STMT (dra), 0);
3812       fprintf (dump_file, ")\n  (stmt_b = \n");
3813       print_generic_expr (dump_file, DR_STMT (drb), 0);
3814       fprintf (dump_file, ")\n");
3815     }
3816
3817   /* Analyze only when the dependence relation is not yet known.  */
3818   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE
3819       && !DDR_SELF_REFERENCE (ddr))
3820     {
3821       dependence_stats.num_dependence_tests++;
3822
3823       if (access_functions_are_affine_or_constant_p (dra, loop_nest)
3824           && access_functions_are_affine_or_constant_p (drb, loop_nest))
3825         {
3826           if (flag_check_data_deps)
3827             {
3828               /* Compute the dependences using the first algorithm.  */
3829               subscript_dependence_tester (ddr, loop_nest);
3830
3831               if (dump_file && (dump_flags & TDF_DETAILS))
3832                 {
3833                   fprintf (dump_file, "\n\nBanerjee Analyzer\n");
3834                   dump_data_dependence_relation (dump_file, ddr);
3835                 }
3836
3837               if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
3838                 {
3839                   bool maybe_dependent;
3840                   VEC (lambda_vector, heap) *dir_vects, *dist_vects;
3841
3842                   /* Save the result of the first DD analyzer.  */
3843                   dist_vects = DDR_DIST_VECTS (ddr);
3844                   dir_vects = DDR_DIR_VECTS (ddr);
3845
3846                   /* Reset the information.  */
3847                   DDR_DIST_VECTS (ddr) = NULL;
3848                   DDR_DIR_VECTS (ddr) = NULL;
3849
3850                   /* Compute the same information using Omega.  */
3851                   if (!init_omega_for_ddr (ddr, &maybe_dependent))
3852                     goto csys_dont_know;
3853
3854                   if (dump_file && (dump_flags & TDF_DETAILS))
3855                     {
3856                       fprintf (dump_file, "Omega Analyzer\n");
3857                       dump_data_dependence_relation (dump_file, ddr);
3858                     }
3859
3860                   /* Check that we get the same information.  */
3861                   if (maybe_dependent)
3862                     gcc_assert (ddr_consistent_p (stderr, ddr, dist_vects,
3863                                                   dir_vects));
3864                 }
3865             }
3866           else
3867             subscript_dependence_tester (ddr, loop_nest);
3868         }
3869
3870       /* As a last case, if the dependence cannot be determined, or if
3871          the dependence is considered too difficult to determine, answer
3872          "don't know".  */
3873       else
3874         {
3875         csys_dont_know:;
3876           dependence_stats.num_dependence_undetermined++;
3877
3878           if (dump_file && (dump_flags & TDF_DETAILS))
3879             {
3880               fprintf (dump_file, "Data ref a:\n");
3881               dump_data_reference (dump_file, dra);
3882               fprintf (dump_file, "Data ref b:\n");
3883               dump_data_reference (dump_file, drb);
3884               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
3885             }
3886           finalize_ddr_dependent (ddr, chrec_dont_know);
3887         }
3888     }
3889
3890   if (dump_file && (dump_flags & TDF_DETAILS))
3891     fprintf (dump_file, ")\n");
3892 }
3893
3894 /* This computes the dependence relation for the same data
3895    reference into DDR.  */
3896
3897 static void
3898 compute_self_dependence (struct data_dependence_relation *ddr)
3899 {
3900   unsigned int i;
3901   struct subscript *subscript;
3902
3903   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3904     return;
3905
3906   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
3907        i++)
3908     {
3909       if (SUB_CONFLICTS_IN_A (subscript))
3910         free_conflict_function (SUB_CONFLICTS_IN_A (subscript));
3911       if (SUB_CONFLICTS_IN_B (subscript))
3912         free_conflict_function (SUB_CONFLICTS_IN_B (subscript));
3913
3914       /* The accessed index overlaps for each iteration.  */
3915       SUB_CONFLICTS_IN_A (subscript)
3916         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3917       SUB_CONFLICTS_IN_B (subscript)
3918         = conflict_fn (1, affine_fn_cst (integer_zero_node));
3919       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
3920     }
3921
3922   /* The distance vector is the zero vector.  */
3923   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3924   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
3925 }
3926
3927 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
3928    the data references in DATAREFS, in the LOOP_NEST.  When
3929    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
3930    relations.  */
3931
3932 void
3933 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
3934                          VEC (ddr_p, heap) **dependence_relations,
3935                          VEC (loop_p, heap) *loop_nest,
3936                          bool compute_self_and_rr)
3937 {
3938   struct data_dependence_relation *ddr;
3939   struct data_reference *a, *b;
3940   unsigned int i, j;
3941
3942   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3943     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
3944       if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
3945         {
3946           ddr = initialize_data_dependence_relation (a, b, loop_nest);
3947           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3948           compute_affine_dependence (ddr, VEC_index (loop_p, loop_nest, 0));
3949         }
3950
3951   if (compute_self_and_rr)
3952     for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
3953       {
3954         ddr = initialize_data_dependence_relation (a, a, loop_nest);
3955         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
3956         compute_self_dependence (ddr);
3957       }
3958 }
3959
3960 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
3961    true if STMT clobbers memory, false otherwise.  */
3962
3963 bool
3964 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
3965 {
3966   bool clobbers_memory = false;
3967   data_ref_loc *ref;
3968   tree *op0, *op1, call;
3969
3970   *references = NULL;
3971
3972   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
3973      Calls have side-effects, except those to const or pure
3974      functions.  */
3975   call = get_call_expr_in (stmt);
3976   if ((call
3977        && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
3978       || (TREE_CODE (stmt) == ASM_EXPR
3979           && ASM_VOLATILE_P (stmt)))
3980     clobbers_memory = true;
3981
3982   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
3983     return clobbers_memory;
3984
3985   if (TREE_CODE (stmt) ==  GIMPLE_MODIFY_STMT)
3986     {
3987       tree base;
3988       op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
3989       op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
3990
3991       if (DECL_P (*op1)
3992           || (REFERENCE_CLASS_P (*op1)
3993               && (base = get_base_address (*op1))
3994               && TREE_CODE (base) != SSA_NAME))
3995         {
3996           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
3997           ref->pos = op1;
3998           ref->is_read = true;
3999         }
4000
4001       if (DECL_P (*op0)
4002           || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4003         {
4004           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4005           ref->pos = op0;
4006           ref->is_read = false;
4007         }
4008     }
4009
4010   if (call)
4011     {
4012       unsigned i, n = call_expr_nargs (call);
4013
4014       for (i = 0; i < n; i++)
4015         {
4016           op0 = &CALL_EXPR_ARG (call, i);
4017
4018           if (DECL_P (*op0)
4019               || (REFERENCE_CLASS_P (*op0) && get_base_address (*op0)))
4020             {
4021               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4022               ref->pos = op0;
4023               ref->is_read = true;
4024             }
4025         }
4026     }
4027
4028   return clobbers_memory;
4029 }
4030
4031 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
4032    reference, returns false, otherwise returns true.  NEST is the outermost
4033    loop of the loop nest in that the references should be analyzed.  */
4034
4035 static bool
4036 find_data_references_in_stmt (struct loop *nest, tree stmt,
4037                               VEC (data_reference_p, heap) **datarefs)
4038 {
4039   unsigned i;
4040   VEC (data_ref_loc, heap) *references;
4041   data_ref_loc *ref;
4042   bool ret = true;
4043   data_reference_p dr;
4044
4045   if (get_references_in_stmt (stmt, &references))
4046     {
4047       VEC_free (data_ref_loc, heap, references);
4048       return false;
4049     }
4050
4051   for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4052     {
4053       dr = create_data_ref (nest, *ref->pos, stmt, ref->is_read);
4054       gcc_assert (dr != NULL);
4055
4056       /* FIXME -- data dependence analysis does not work correctly for objects with
4057          invariant addresses.  Let us fail here until the problem is fixed.  */
4058       if (dr_address_invariant_p (dr))
4059         {
4060           free_data_ref (dr);
4061           if (dump_file && (dump_flags & TDF_DETAILS))
4062             fprintf (dump_file, "\tFAILED as dr address is invariant\n");
4063           ret = false;
4064           break;
4065         }
4066
4067       VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4068     }
4069   VEC_free (data_ref_loc, heap, references);
4070   return ret;
4071 }
4072
4073 /* Search the data references in LOOP, and record the information into
4074    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4075    difficult case, returns NULL_TREE otherwise.
4076
4077    TODO: This function should be made smarter so that it can handle address
4078    arithmetic as if they were array accesses, etc.  */
4079
4080 static tree
4081 find_data_references_in_loop (struct loop *loop,
4082                               VEC (data_reference_p, heap) **datarefs)
4083 {
4084   basic_block bb, *bbs;
4085   unsigned int i;
4086   block_stmt_iterator bsi;
4087
4088   bbs = get_loop_body_in_dom_order (loop);
4089
4090   for (i = 0; i < loop->num_nodes; i++)
4091     {
4092       bb = bbs[i];
4093
4094       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4095         {
4096           tree stmt = bsi_stmt (bsi);
4097
4098           if (!find_data_references_in_stmt (loop, stmt, datarefs))
4099             {
4100               struct data_reference *res;
4101               res = XCNEW (struct data_reference);
4102               VEC_safe_push (data_reference_p, heap, *datarefs, res);
4103
4104               free (bbs);
4105               return chrec_dont_know;
4106             }
4107         }
4108     }
4109   free (bbs);
4110
4111   return NULL_TREE;
4112 }
4113
4114 /* Recursive helper function.  */
4115
4116 static bool
4117 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4118 {
4119   /* Inner loops of the nest should not contain siblings.  Example:
4120      when there are two consecutive loops,
4121
4122      | loop_0
4123      |   loop_1
4124      |     A[{0, +, 1}_1]
4125      |   endloop_1
4126      |   loop_2
4127      |     A[{0, +, 1}_2]
4128      |   endloop_2
4129      | endloop_0
4130
4131      the dependence relation cannot be captured by the distance
4132      abstraction.  */
4133   if (loop->next)
4134     return false;
4135
4136   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4137   if (loop->inner)
4138     return find_loop_nest_1 (loop->inner, loop_nest);
4139   return true;
4140 }
4141
4142 /* Return false when the LOOP is not well nested.  Otherwise return
4143    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4144    contain the loops from the outermost to the innermost, as they will
4145    appear in the classic distance vector.  */
4146
4147 bool
4148 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4149 {
4150   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4151   if (loop->inner)
4152     return find_loop_nest_1 (loop->inner, loop_nest);
4153   return true;
4154 }
4155
4156 /* Given a loop nest LOOP, the following vectors are returned:
4157    DATAREFS is initialized to all the array elements contained in this loop,
4158    DEPENDENCE_RELATIONS contains the relations between the data references.
4159    Compute read-read and self relations if
4160    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4161
4162 void
4163 compute_data_dependences_for_loop (struct loop *loop,
4164                                    bool compute_self_and_read_read_dependences,
4165                                    VEC (data_reference_p, heap) **datarefs,
4166                                    VEC (ddr_p, heap) **dependence_relations)
4167 {
4168   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4169
4170   memset (&dependence_stats, 0, sizeof (dependence_stats));
4171
4172   /* If the loop nest is not well formed, or one of the data references
4173      is not computable, give up without spending time to compute other
4174      dependences.  */
4175   if (!loop
4176       || !find_loop_nest (loop, &vloops)
4177       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4178     {
4179       struct data_dependence_relation *ddr;
4180
4181       /* Insert a single relation into dependence_relations:
4182          chrec_dont_know.  */
4183       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4184       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4185     }
4186   else
4187     compute_all_dependences (*datarefs, dependence_relations, vloops,
4188                              compute_self_and_read_read_dependences);
4189
4190   if (dump_file && (dump_flags & TDF_STATS))
4191     {
4192       fprintf (dump_file, "Dependence tester statistics:\n");
4193
4194       fprintf (dump_file, "Number of dependence tests: %d\n",
4195                dependence_stats.num_dependence_tests);
4196       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4197                dependence_stats.num_dependence_dependent);
4198       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4199                dependence_stats.num_dependence_independent);
4200       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4201                dependence_stats.num_dependence_undetermined);
4202
4203       fprintf (dump_file, "Number of subscript tests: %d\n",
4204                dependence_stats.num_subscript_tests);
4205       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4206                dependence_stats.num_subscript_undetermined);
4207       fprintf (dump_file, "Number of same subscript function: %d\n",
4208                dependence_stats.num_same_subscript_function);
4209
4210       fprintf (dump_file, "Number of ziv tests: %d\n",
4211                dependence_stats.num_ziv);
4212       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4213                dependence_stats.num_ziv_dependent);
4214       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4215                dependence_stats.num_ziv_independent);
4216       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4217                dependence_stats.num_ziv_unimplemented);
4218
4219       fprintf (dump_file, "Number of siv tests: %d\n",
4220                dependence_stats.num_siv);
4221       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4222                dependence_stats.num_siv_dependent);
4223       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4224                dependence_stats.num_siv_independent);
4225       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4226                dependence_stats.num_siv_unimplemented);
4227
4228       fprintf (dump_file, "Number of miv tests: %d\n",
4229                dependence_stats.num_miv);
4230       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4231                dependence_stats.num_miv_dependent);
4232       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4233                dependence_stats.num_miv_independent);
4234       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4235                dependence_stats.num_miv_unimplemented);
4236     }
4237 }
4238
4239 /* Entry point (for testing only).  Analyze all the data references
4240    and the dependence relations in LOOP.
4241
4242    The data references are computed first.
4243
4244    A relation on these nodes is represented by a complete graph.  Some
4245    of the relations could be of no interest, thus the relations can be
4246    computed on demand.
4247
4248    In the following function we compute all the relations.  This is
4249    just a first implementation that is here for:
4250    - for showing how to ask for the dependence relations,
4251    - for the debugging the whole dependence graph,
4252    - for the dejagnu testcases and maintenance.
4253
4254    It is possible to ask only for a part of the graph, avoiding to
4255    compute the whole dependence graph.  The computed dependences are
4256    stored in a knowledge base (KB) such that later queries don't
4257    recompute the same information.  The implementation of this KB is
4258    transparent to the optimizer, and thus the KB can be changed with a
4259    more efficient implementation, or the KB could be disabled.  */
4260 static void
4261 analyze_all_data_dependences (struct loop *loop)
4262 {
4263   unsigned int i;
4264   int nb_data_refs = 10;
4265   VEC (data_reference_p, heap) *datarefs =
4266     VEC_alloc (data_reference_p, heap, nb_data_refs);
4267   VEC (ddr_p, heap) *dependence_relations =
4268     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4269
4270   /* Compute DDs on the whole function.  */
4271   compute_data_dependences_for_loop (loop, false, &datarefs,
4272                                      &dependence_relations);
4273
4274   if (dump_file)
4275     {
4276       dump_data_dependence_relations (dump_file, dependence_relations);
4277       fprintf (dump_file, "\n\n");
4278
4279       if (dump_flags & TDF_DETAILS)
4280         dump_dist_dir_vectors (dump_file, dependence_relations);
4281
4282       if (dump_flags & TDF_STATS)
4283         {
4284           unsigned nb_top_relations = 0;
4285           unsigned nb_bot_relations = 0;
4286           unsigned nb_basename_differ = 0;
4287           unsigned nb_chrec_relations = 0;
4288           struct data_dependence_relation *ddr;
4289
4290           for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4291             {
4292               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4293                 nb_top_relations++;
4294
4295               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4296                 {
4297                   struct data_reference *a = DDR_A (ddr);
4298                   struct data_reference *b = DDR_B (ddr);
4299
4300                   if (!bitmap_intersect_p (DR_VOPS (a), DR_VOPS (b)))
4301                     nb_basename_differ++;
4302                   else
4303                     nb_bot_relations++;
4304                 }
4305
4306               else
4307                 nb_chrec_relations++;
4308             }
4309
4310           gather_stats_on_scev_database ();
4311         }
4312     }
4313
4314   free_dependence_relations (dependence_relations);
4315   free_data_refs (datarefs);
4316 }
4317
4318 /* Computes all the data dependences and check that the results of
4319    several analyzers are the same.  */
4320
4321 void
4322 tree_check_data_deps (void)
4323 {
4324   loop_iterator li;
4325   struct loop *loop_nest;
4326
4327   FOR_EACH_LOOP (li, loop_nest, 0)
4328     analyze_all_data_dependences (loop_nest);
4329 }
4330
4331 /* Free the memory used by a data dependence relation DDR.  */
4332
4333 void
4334 free_dependence_relation (struct data_dependence_relation *ddr)
4335 {
4336   if (ddr == NULL)
4337     return;
4338
4339   if (DDR_SUBSCRIPTS (ddr))
4340     free_subscripts (DDR_SUBSCRIPTS (ddr));
4341   if (DDR_DIST_VECTS (ddr))
4342     VEC_free (lambda_vector, heap, DDR_DIST_VECTS (ddr));
4343   if (DDR_DIR_VECTS (ddr))
4344     VEC_free (lambda_vector, heap, DDR_DIR_VECTS (ddr));
4345
4346   free (ddr);
4347 }
4348
4349 /* Free the memory used by the data dependence relations from
4350    DEPENDENCE_RELATIONS.  */
4351
4352 void
4353 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4354 {
4355   unsigned int i;
4356   struct data_dependence_relation *ddr;
4357   VEC (loop_p, heap) *loop_nest = NULL;
4358
4359   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4360     {
4361       if (ddr == NULL)
4362         continue;
4363       if (loop_nest == NULL)
4364         loop_nest = DDR_LOOP_NEST (ddr);
4365       else
4366         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4367                     || DDR_LOOP_NEST (ddr) == loop_nest);
4368       free_dependence_relation (ddr);
4369     }
4370
4371   if (loop_nest)
4372     VEC_free (loop_p, heap, loop_nest);
4373   VEC_free (ddr_p, heap, dependence_relations);
4374 }
4375
4376 /* Free the memory used by the data references from DATAREFS.  */
4377
4378 void
4379 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4380 {
4381   unsigned int i;
4382   struct data_reference *dr;
4383
4384   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4385     free_data_ref (dr);
4386   VEC_free (data_reference_p, heap, datarefs);
4387 }
4388
4389 \f
4390
4391 /* Dump vertex I in RDG to FILE.  */
4392
4393 void
4394 dump_rdg_vertex (FILE *file, struct graph *rdg, int i)
4395 {
4396   struct vertex *v = &(rdg->vertices[i]);
4397   struct graph_edge *e;
4398
4399   fprintf (file, "(vertex %d: (%s%s) (in:", i,
4400            RDG_MEM_WRITE_STMT (rdg, i) ? "w" : "",
4401            RDG_MEM_READS_STMT (rdg, i) ? "r" : "");
4402
4403   if (v->pred)
4404     for (e = v->pred; e; e = e->pred_next)
4405       fprintf (file, " %d", e->src);
4406
4407   fprintf (file, ") (out:");
4408
4409   if (v->succ)
4410     for (e = v->succ; e; e = e->succ_next)
4411       fprintf (file, " %d", e->dest);
4412
4413   fprintf (file, ") \n");
4414   print_generic_stmt (file, RDGV_STMT (v), TDF_VOPS|TDF_MEMSYMS);
4415   fprintf (file, ")\n");
4416 }
4417
4418 /* Call dump_rdg_vertex on stderr.  */
4419
4420 void
4421 debug_rdg_vertex (struct graph *rdg, int i)
4422 {
4423   dump_rdg_vertex (stderr, rdg, i);
4424 }
4425
4426 /* Dump component C of RDG to FILE.  If DUMPED is non-null, set the
4427    dumped vertices to that bitmap.  */
4428
4429 void dump_rdg_component (FILE *file, struct graph *rdg, int c, bitmap dumped)
4430 {
4431   int i;
4432
4433   fprintf (file, "(%d\n", c);
4434
4435   for (i = 0; i < rdg->n_vertices; i++)
4436     if (rdg->vertices[i].component == c)
4437       {
4438         if (dumped)
4439           bitmap_set_bit (dumped, i);
4440
4441         dump_rdg_vertex (file, rdg, i);
4442       }
4443
4444   fprintf (file, ")\n");
4445 }
4446
4447 /* Call dump_rdg_vertex on stderr.  */
4448
4449 void
4450 debug_rdg_component (struct graph *rdg, int c)
4451 {
4452   dump_rdg_component (stderr, rdg, c, NULL);
4453 }
4454
4455 /* Dump the reduced dependence graph RDG to FILE.  */
4456
4457 void
4458 dump_rdg (FILE *file, struct graph *rdg)
4459 {
4460   int i;
4461   bitmap dumped = BITMAP_ALLOC (NULL);
4462
4463   fprintf (file, "(rdg\n");
4464
4465   for (i = 0; i < rdg->n_vertices; i++)
4466     if (!bitmap_bit_p (dumped, i))
4467       dump_rdg_component (file, rdg, rdg->vertices[i].component, dumped);
4468
4469   fprintf (file, ")\n");
4470   BITMAP_FREE (dumped);
4471 }
4472
4473 /* Call dump_rdg on stderr.  */
4474
4475 void
4476 debug_rdg (struct graph *rdg)
4477 {
4478   dump_rdg (stderr, rdg);
4479 }
4480
4481 static void
4482 dot_rdg_1 (FILE *file, struct graph *rdg)
4483 {
4484   int i;
4485
4486   fprintf (file, "digraph RDG {\n");
4487
4488   for (i = 0; i < rdg->n_vertices; i++)
4489     {
4490       struct vertex *v = &(rdg->vertices[i]);
4491       struct graph_edge *e;
4492
4493       /* Highlight reads from memory.  */
4494       if (RDG_MEM_READS_STMT (rdg, i))
4495         fprintf (file, "%d [style=filled, fillcolor=green]\n", i);
4496
4497       /* Highlight stores to memory.  */
4498       if (RDG_MEM_WRITE_STMT (rdg, i))
4499         fprintf (file, "%d [style=filled, fillcolor=red]\n", i);
4500
4501       if (v->succ)
4502         for (e = v->succ; e; e = e->succ_next)
4503           switch (RDGE_TYPE (e))
4504             {
4505             case input_dd:
4506               fprintf (file, "%d -> %d [label=input] \n", i, e->dest);
4507               break;
4508
4509             case output_dd:
4510               fprintf (file, "%d -> %d [label=output] \n", i, e->dest);
4511               break;
4512
4513             case flow_dd:
4514               /* These are the most common dependences: don't print these. */
4515               fprintf (file, "%d -> %d \n", i, e->dest);
4516               break;
4517
4518             case anti_dd:
4519               fprintf (file, "%d -> %d [label=anti] \n", i, e->dest);
4520               break;
4521
4522             default:
4523               gcc_unreachable ();
4524             }
4525     }
4526
4527   fprintf (file, "}\n\n");
4528 }
4529
4530 /* Display SCOP using dotty.  */
4531
4532 void
4533 dot_rdg (struct graph *rdg)
4534 {
4535   FILE *file = fopen ("/tmp/rdg.dot", "w");
4536   gcc_assert (file != NULL);
4537
4538   dot_rdg_1 (file, rdg);
4539   fclose (file);
4540
4541   system ("dotty /tmp/rdg.dot");
4542 }
4543
4544
4545 /* This structure is used for recording the mapping statement index in
4546    the RDG.  */
4547
4548 struct rdg_vertex_info GTY(())
4549 {
4550   tree stmt;
4551   int index;
4552 };
4553
4554 /* Returns the index of STMT in RDG.  */
4555
4556 int
4557 rdg_vertex_for_stmt (struct graph *rdg, tree stmt)
4558 {
4559   struct rdg_vertex_info rvi, *slot;
4560
4561   rvi.stmt = stmt;
4562   slot = (struct rdg_vertex_info *) htab_find (rdg->indices, &rvi);
4563
4564   if (!slot)
4565     return -1;
4566
4567   return slot->index;
4568 }
4569
4570 /* Creates an edge in RDG for each distance vector from DDR.  The
4571    order that we keep track of in the RDG is the order in which
4572    statements have to be executed.  */
4573
4574 static void
4575 create_rdg_edge_for_ddr (struct graph *rdg, ddr_p ddr)
4576 {
4577   struct graph_edge *e;
4578   int va, vb;
4579   data_reference_p dra = DDR_A (ddr);
4580   data_reference_p drb = DDR_B (ddr);
4581   unsigned level = ddr_dependence_level (ddr);
4582
4583   /* For non scalar dependences, when the dependence is REVERSED,
4584      statement B has to be executed before statement A.  */
4585   if (level > 0
4586       && !DDR_REVERSED_P (ddr))
4587     {
4588       data_reference_p tmp = dra;
4589       dra = drb;
4590       drb = tmp;
4591     }
4592
4593   va = rdg_vertex_for_stmt (rdg, DR_STMT (dra));
4594   vb = rdg_vertex_for_stmt (rdg, DR_STMT (drb));
4595
4596   if (va < 0 || vb < 0)
4597     return;
4598
4599   e = add_edge (rdg, va, vb);
4600   e->data = XNEW (struct rdg_edge);
4601
4602   RDGE_LEVEL (e) = level;
4603
4604   /* Determines the type of the data dependence.  */
4605   if (DR_IS_READ (dra) && DR_IS_READ (drb))
4606     RDGE_TYPE (e) = input_dd;
4607   else if (!DR_IS_READ (dra) && !DR_IS_READ (drb))
4608     RDGE_TYPE (e) = output_dd;
4609   else if (!DR_IS_READ (dra) && DR_IS_READ (drb))
4610     RDGE_TYPE (e) = flow_dd;
4611   else if (DR_IS_READ (dra) && !DR_IS_READ (drb))
4612     RDGE_TYPE (e) = anti_dd;
4613 }
4614
4615 /* Creates dependence edges in RDG for all the uses of DEF.  IDEF is
4616    the index of DEF in RDG.  */
4617
4618 static void
4619 create_rdg_edges_for_scalar (struct graph *rdg, tree def, int idef)
4620 {
4621   use_operand_p imm_use_p;
4622   imm_use_iterator iterator;
4623
4624   FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, def)
4625     {
4626       struct graph_edge *e;
4627       int use = rdg_vertex_for_stmt (rdg, USE_STMT (imm_use_p));
4628
4629       if (use < 0)
4630         continue;
4631
4632       e = add_edge (rdg, idef, use);
4633       e->data = XNEW (struct rdg_edge);
4634       RDGE_TYPE (e) = flow_dd;
4635     }
4636 }
4637
4638 /* Creates the edges of the reduced dependence graph RDG.  */
4639
4640 static void
4641 create_rdg_edges (struct graph *rdg, VEC (ddr_p, heap) *ddrs)
4642 {
4643   int i;
4644   struct data_dependence_relation *ddr;
4645   def_operand_p def_p;
4646   ssa_op_iter iter;
4647
4648   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
4649     if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4650       create_rdg_edge_for_ddr (rdg, ddr);
4651
4652   for (i = 0; i < rdg->n_vertices; i++)
4653     FOR_EACH_PHI_OR_STMT_DEF (def_p, RDG_STMT (rdg, i),
4654                               iter, SSA_OP_DEF)
4655       create_rdg_edges_for_scalar (rdg, DEF_FROM_PTR (def_p), i);
4656 }
4657
4658 /* Build the vertices of the reduced dependence graph RDG.  */
4659
4660 static void
4661 create_rdg_vertices (struct graph *rdg, VEC (tree, heap) *stmts)
4662 {
4663   int i, j;
4664   tree stmt;
4665
4666   for (i = 0; VEC_iterate (tree, stmts, i, stmt); i++)
4667     {
4668       VEC (data_ref_loc, heap) *references;
4669       data_ref_loc *ref;
4670       struct vertex *v = &(rdg->vertices[i]);
4671       struct rdg_vertex_info *rvi = XNEW (struct rdg_vertex_info);
4672       struct rdg_vertex_info **slot;
4673
4674       rvi->stmt = stmt;
4675       rvi->index = i;
4676       slot = (struct rdg_vertex_info **) htab_find_slot (rdg->indices, rvi, INSERT);
4677
4678       if (!*slot)
4679         *slot = rvi;
4680       else
4681         free (rvi);
4682
4683       v->data = XNEW (struct rdg_vertex);
4684       RDG_STMT (rdg, i) = stmt;
4685
4686       RDG_MEM_WRITE_STMT (rdg, i) = false;
4687       RDG_MEM_READS_STMT (rdg, i) = false;
4688       if (TREE_CODE (stmt) == PHI_NODE)
4689         continue;
4690
4691       get_references_in_stmt (stmt, &references);
4692       for (j = 0; VEC_iterate (data_ref_loc, references, j, ref); j++)
4693         if (!ref->is_read)
4694           RDG_MEM_WRITE_STMT (rdg, i) = true;
4695         else
4696           RDG_MEM_READS_STMT (rdg, i) = true;
4697
4698       VEC_free (data_ref_loc, heap, references);
4699     }
4700 }
4701
4702 /* Initialize STMTS with all the statements of LOOP.  When
4703    INCLUDE_PHIS is true, include also the PHI nodes.  The order in
4704    which we discover statements is important as
4705    generate_loops_for_partition is using the same traversal for
4706    identifying statements. */
4707
4708 static void
4709 stmts_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
4710 {
4711   unsigned int i;
4712   basic_block *bbs = get_loop_body_in_dom_order (loop);
4713
4714   for (i = 0; i < loop->num_nodes; i++)
4715     {
4716       tree phi, stmt;
4717       basic_block bb = bbs[i];
4718       block_stmt_iterator bsi;
4719
4720       for (phi = phi_nodes (bb); phi; phi = PHI_CHAIN (phi))
4721         VEC_safe_push (tree, heap, *stmts, phi);
4722
4723       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4724         if (TREE_CODE (stmt = bsi_stmt (bsi)) != LABEL_EXPR)
4725           VEC_safe_push (tree, heap, *stmts, stmt);
4726     }
4727
4728   free (bbs);
4729 }
4730
4731 /* Returns true when all the dependences are computable.  */
4732
4733 static bool
4734 known_dependences_p (VEC (ddr_p, heap) *dependence_relations)
4735 {
4736   ddr_p ddr;
4737   unsigned int i;
4738
4739   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4740     if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
4741       return false;
4742
4743   return true;
4744 }
4745
4746 /* Computes a hash function for element ELT.  */
4747
4748 static hashval_t
4749 hash_stmt_vertex_info (const void *elt)
4750 {
4751   struct rdg_vertex_info *rvi = (struct rdg_vertex_info *) elt;
4752   tree stmt = rvi->stmt;
4753
4754   return htab_hash_pointer (stmt);
4755 }
4756
4757 /* Compares database elements E1 and E2.  */
4758
4759 static int
4760 eq_stmt_vertex_info (const void *e1, const void *e2)
4761 {
4762   const struct rdg_vertex_info *elt1 = (const struct rdg_vertex_info *) e1;
4763   const struct rdg_vertex_info *elt2 = (const struct rdg_vertex_info *) e2;
4764
4765   return elt1->stmt == elt2->stmt;
4766 }
4767
4768 /* Free the element E.  */
4769
4770 static void
4771 hash_stmt_vertex_del (void *e)
4772 {
4773   free (e);
4774 }
4775
4776 /* Build the Reduced Dependence Graph (RDG) with one vertex per
4777    statement of the loop nest, and one edge per data dependence or
4778    scalar dependence.  */
4779
4780 struct graph *
4781 build_rdg (struct loop *loop)
4782 {
4783   int nb_data_refs = 10;
4784   struct graph *rdg = NULL;
4785   VEC (ddr_p, heap) *dependence_relations;
4786   VEC (data_reference_p, heap) *datarefs;
4787   VEC (tree, heap) *stmts = VEC_alloc (tree, heap, nb_data_refs);
4788
4789   dependence_relations = VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs) ;
4790   datarefs = VEC_alloc (data_reference_p, heap, nb_data_refs);
4791   compute_data_dependences_for_loop (loop,
4792                                      false,
4793                                      &datarefs,
4794                                      &dependence_relations);
4795
4796   if (!known_dependences_p (dependence_relations))
4797     goto end_rdg;
4798
4799   stmts_from_loop (loop, &stmts);
4800   rdg = new_graph (VEC_length (tree, stmts));
4801
4802   rdg->indices = htab_create (nb_data_refs, hash_stmt_vertex_info,
4803                               eq_stmt_vertex_info, hash_stmt_vertex_del);
4804   create_rdg_vertices (rdg, stmts);
4805   create_rdg_edges (rdg, dependence_relations);
4806
4807  end_rdg:
4808   free_dependence_relations (dependence_relations);
4809   free_data_refs (datarefs);
4810   VEC_free (tree, heap, stmts);
4811
4812   return rdg;
4813 }
4814
4815 /* Free the reduced dependence graph RDG.  */
4816
4817 void
4818 free_rdg (struct graph *rdg)
4819 {
4820   int i;
4821
4822   for (i = 0; i < rdg->n_vertices; i++)
4823     free (rdg->vertices[i].data);
4824
4825   htab_delete (rdg->indices);
4826   free_graph (rdg);
4827 }
4828
4829 /* Initialize STMTS with all the statements of LOOP that contain a
4830    store to memory.  */
4831
4832 void
4833 stores_from_loop (struct loop *loop, VEC (tree, heap) **stmts)
4834 {
4835   unsigned int i;
4836   basic_block *bbs = get_loop_body_in_dom_order (loop);
4837
4838   for (i = 0; i < loop->num_nodes; i++)
4839     {
4840       basic_block bb = bbs[i];
4841       block_stmt_iterator bsi;
4842
4843       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4844         if (!ZERO_SSA_OPERANDS (bsi_stmt (bsi), SSA_OP_VDEF))
4845           VEC_safe_push (tree, heap, *stmts, bsi_stmt (bsi));
4846     }
4847
4848   free (bbs);
4849 }
4850
4851 /* For a data reference REF, return the declaration of its base
4852    address or NULL_TREE if the base is not determined.  */
4853
4854 static inline tree
4855 ref_base_address (tree stmt, data_ref_loc *ref)
4856 {
4857   tree base = NULL_TREE;
4858   tree base_address;
4859   struct data_reference *dr = XCNEW (struct data_reference);
4860
4861   DR_STMT (dr) = stmt;
4862   DR_REF (dr) = *ref->pos;
4863   dr_analyze_innermost (dr);
4864   base_address = DR_BASE_ADDRESS (dr);
4865
4866   if (!base_address)
4867     goto end;
4868
4869   switch (TREE_CODE (base_address))
4870     {
4871     case ADDR_EXPR:
4872       base = TREE_OPERAND (base_address, 0);
4873       break;
4874
4875     default:
4876       base = base_address;
4877       break;
4878     }
4879
4880  end:
4881   free_data_ref (dr);
4882   return base;
4883 }
4884
4885 /* Determines whether the statement from vertex V of the RDG has a
4886    definition used outside the loop that contains this statement.  */
4887
4888 bool
4889 rdg_defs_used_in_other_loops_p (struct graph *rdg, int v)
4890 {
4891   tree stmt = RDG_STMT (rdg, v);
4892   struct loop *loop = loop_containing_stmt (stmt);
4893   use_operand_p imm_use_p;
4894   imm_use_iterator iterator;
4895   ssa_op_iter it;
4896   def_operand_p def_p;
4897
4898   if (!loop)
4899     return true;
4900
4901   FOR_EACH_PHI_OR_STMT_DEF (def_p, stmt, it, SSA_OP_DEF)
4902     {
4903       FOR_EACH_IMM_USE_FAST (imm_use_p, iterator, DEF_FROM_PTR (def_p))
4904         {
4905           if (loop_containing_stmt (USE_STMT (imm_use_p)) != loop)
4906             return true;
4907         }
4908     }
4909
4910   return false;
4911 }
4912
4913 /* Determines whether statements S1 and S2 access to similar memory
4914    locations.  Two memory accesses are considered similar when they
4915    have the same base address declaration, i.e. when their
4916    ref_base_address is the same.  */
4917
4918 bool
4919 have_similar_memory_accesses (tree s1, tree s2)
4920 {
4921   bool res = false;
4922   unsigned i, j;
4923   VEC (data_ref_loc, heap) *refs1, *refs2;
4924   data_ref_loc *ref1, *ref2;
4925
4926   get_references_in_stmt (s1, &refs1);
4927   get_references_in_stmt (s2, &refs2);
4928
4929   for (i = 0; VEC_iterate (data_ref_loc, refs1, i, ref1); i++)
4930     {
4931       tree base1 = ref_base_address (s1, ref1);
4932
4933       if (base1)
4934         for (j = 0; VEC_iterate (data_ref_loc, refs2, j, ref2); j++)
4935           if (base1 == ref_base_address (s2, ref2))
4936             {
4937               res = true;
4938               goto end;
4939             }
4940     }
4941
4942  end:
4943   VEC_free (data_ref_loc, heap, refs1);
4944   VEC_free (data_ref_loc, heap, refs2);
4945   return res;
4946 }
4947
4948 /* Helper function for the hashtab.  */
4949
4950 static int
4951 have_similar_memory_accesses_1 (const void *s1, const void *s2)
4952 {
4953   return have_similar_memory_accesses ((tree) s1, (tree) s2);
4954 }
4955
4956 /* Helper function for the hashtab.  */
4957
4958 static hashval_t
4959 ref_base_address_1 (const void *s)
4960 {
4961   tree stmt = (tree) s;
4962   unsigned i;
4963   VEC (data_ref_loc, heap) *refs;
4964   data_ref_loc *ref;
4965   hashval_t res = 0;
4966
4967   get_references_in_stmt (stmt, &refs);
4968
4969   for (i = 0; VEC_iterate (data_ref_loc, refs, i, ref); i++)
4970     if (!ref->is_read)
4971       {
4972         res = htab_hash_pointer (ref_base_address (stmt, ref));
4973         break;
4974       }
4975
4976   VEC_free (data_ref_loc, heap, refs);
4977   return res;
4978 }
4979
4980 /* Try to remove duplicated write data references from STMTS.  */
4981
4982 void
4983 remove_similar_memory_refs (VEC (tree, heap) **stmts)
4984 {
4985   unsigned i;
4986   tree stmt;
4987   htab_t seen = htab_create (VEC_length (tree, *stmts), ref_base_address_1,
4988                              have_similar_memory_accesses_1, NULL);
4989
4990   for (i = 0; VEC_iterate (tree, *stmts, i, stmt); )
4991     {
4992       void **slot;
4993
4994       slot = htab_find_slot (seen, stmt, INSERT);
4995
4996       if (*slot)
4997         VEC_ordered_remove (tree, *stmts, i);
4998       else
4999         {
5000           *slot = (void *) stmt;
5001           i++;
5002         }
5003     }
5004
5005   htab_delete (seen);
5006 }
5007