gcc/tree-data-ref.c

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