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