contrib/gcc/tree-data-ref.c

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