gcc/tree-data-ref.c

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