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