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