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