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