gcc/tree-data-ref.c

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