gcc/tree-data-ref.c

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