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