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, tree b)
 565 {
 566   gcc_assert (TREE_CODE (a) == INTEGER_CST);
 567   gcc_assert (TREE_CODE (b) == INTEGER_CST);
 568   return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
 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   gcc_assert (0 < n && n <= MAX_DIM);
2422   va_start(ap, n);
2423
2424   ret->n = n;
2425   for (i = 0; i < n; i++)
2426     ret->fns[i] = va_arg (ap, affine_fn);
2427   va_end(ap);
2428
2429   return ret;
2430 }
2431
2432 /* Returns constant affine function with value CST.  */
2433
2434 static affine_fn
2435 affine_fn_cst (tree cst)
2436 {
2437   affine_fn fn = VEC_alloc (tree, heap, 1);
2438   VEC_quick_push (tree, fn, cst);
2439   return fn;
2440 }
2441
2442 /* Returns affine function with single variable, CST + COEF * x_DIM.  */
2443
2444 static affine_fn
2445 affine_fn_univar (tree cst, unsigned dim, tree coef)
2446 {
2447   affine_fn fn = VEC_alloc (tree, heap, dim + 1);
2448   unsigned i;
2449
2450   gcc_assert (dim > 0);
2451   VEC_quick_push (tree, fn, cst);
2452   for (i = 1; i < dim; i++)
2453     VEC_quick_push (tree, fn, integer_zero_node);
2454   VEC_quick_push (tree, fn, coef);
2455   return fn;
2456 }
2457
2458 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
2459    *OVERLAPS_B are initialized to the functions that describe the
2460    relation between the elements accessed twice by CHREC_A and
2461    CHREC_B.  For k >= 0, the following property is verified:
2462
2463    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2464
2465 static void
2466 analyze_ziv_subscript (tree chrec_a,
2467                        tree chrec_b,
2468                        conflict_function **overlaps_a,
2469                        conflict_function **overlaps_b,
2470                        tree *last_conflicts)
2471 {
2472   tree difference;
2473   dependence_stats.num_ziv++;
2474
2475   if (dump_file && (dump_flags & TDF_DETAILS))
2476     fprintf (dump_file, "(analyze_ziv_subscript \n");
2477
2478   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2479   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2480   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2481
2482   switch (TREE_CODE (difference))
2483     {
2484     case INTEGER_CST:
2485       if (integer_zerop (difference))
2486         {
2487           /* The difference is equal to zero: the accessed index
2488              overlaps for each iteration in the loop.  */
2489           *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2490           *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2491           *last_conflicts = chrec_dont_know;
2492           dependence_stats.num_ziv_dependent++;
2493         }
2494       else
2495         {
2496           /* The accesses do not overlap.  */
2497           *overlaps_a = conflict_fn_no_dependence ();
2498           *overlaps_b = conflict_fn_no_dependence ();
2499           *last_conflicts = integer_zero_node;
2500           dependence_stats.num_ziv_independent++;
2501         }
2502       break;
2503
2504     default:
2505       /* We're not sure whether the indexes overlap.  For the moment,
2506          conservatively answer "don't know".  */
2507       if (dump_file && (dump_flags & TDF_DETAILS))
2508         fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2509
2510       *overlaps_a = conflict_fn_not_known ();
2511       *overlaps_b = conflict_fn_not_known ();
2512       *last_conflicts = chrec_dont_know;
2513       dependence_stats.num_ziv_unimplemented++;
2514       break;
2515     }
2516
2517   if (dump_file && (dump_flags & TDF_DETAILS))
2518     fprintf (dump_file, ")\n");
2519 }
2520
2521 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2522    available. Return the number of iterations as a tree, or NULL_TREE if
2523    we don't know.  */
2524
2525 static tree
2526 get_number_of_iters_for_loop (int loopnum)
2527 {
2528   struct loop *loop = get_loop (loopnum);
2529   tree numiter = number_of_exit_cond_executions (loop);
2530
2531   if (TREE_CODE (numiter) == INTEGER_CST)
2532     return numiter;
2533
2534   if (loop->estimate_state == EST_AVAILABLE)
2535     {
2536       tree type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2537       if (double_int_fits_to_tree_p (type, loop->estimated_nb_iterations))
2538         return double_int_to_tree (type, loop->estimated_nb_iterations);
2539     }
2540
2541   return NULL_TREE;
2542 }
2543
2544 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2545    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
2546    *OVERLAPS_B are initialized to the functions that describe the
2547    relation between the elements accessed twice by CHREC_A and
2548    CHREC_B.  For k >= 0, the following property is verified:
2549
2550    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2551
2552 static void
2553 analyze_siv_subscript_cst_affine (tree chrec_a,
2554                                   tree chrec_b,
2555                                   conflict_function **overlaps_a,
2556                                   conflict_function **overlaps_b,
2557                                   tree *last_conflicts)
2558 {
2559   bool value0, value1, value2;
2560   tree difference, tmp;
2561
2562   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2563   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2564   difference = chrec_fold_minus
2565     (integer_type_node, initial_condition (chrec_b), chrec_a);
2566
2567   if (!chrec_is_positive (initial_condition (difference), &value0))
2568     {
2569       if (dump_file && (dump_flags & TDF_DETAILS))
2570         fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2571
2572       dependence_stats.num_siv_unimplemented++;
2573       *overlaps_a = conflict_fn_not_known ();
2574       *overlaps_b = conflict_fn_not_known ();
2575       *last_conflicts = chrec_dont_know;
2576       return;
2577     }
2578   else
2579     {
2580       if (value0 == false)
2581         {
2582           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2583             {
2584               if (dump_file && (dump_flags & TDF_DETAILS))
2585                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2586
2587               *overlaps_a = conflict_fn_not_known ();
2588               *overlaps_b = conflict_fn_not_known ();
2589               *last_conflicts = chrec_dont_know;
2590               dependence_stats.num_siv_unimplemented++;
2591               return;
2592             }
2593           else
2594             {
2595               if (value1 == true)
2596                 {
2597                   /* Example:
2598                      chrec_a = 12
2599                      chrec_b = {10, +, 1}
2600                   */
2601
2602                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2603                     {
2604                       tree numiter;
2605                       int loopnum = CHREC_VARIABLE (chrec_b);
2606
2607                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2608                       tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2609                                          fold_build1 (ABS_EXPR,
2610                                                       integer_type_node,
2611                                                       difference),
2612                                          CHREC_RIGHT (chrec_b));
2613                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2614                       *last_conflicts = integer_one_node;
2615
2616
2617                       /* Perform weak-zero siv test to see if overlap is
2618                          outside the loop bounds.  */
2619                       numiter = get_number_of_iters_for_loop (loopnum);
2620
2621                       if (numiter != NULL_TREE
2622                           && TREE_CODE (tmp) == INTEGER_CST
2623                           && tree_int_cst_lt (numiter, tmp))
2624                         {
2625                           free_conflict_function (*overlaps_a);
2626                           free_conflict_function (*overlaps_b);
2627                           *overlaps_a = conflict_fn_no_dependence ();
2628                           *overlaps_b = conflict_fn_no_dependence ();
2629                           *last_conflicts = integer_zero_node;
2630                           dependence_stats.num_siv_independent++;
2631                           return;
2632                         }
2633                       dependence_stats.num_siv_dependent++;
2634                       return;
2635                     }
2636
2637                   /* When the step does not divide the difference, there are
2638                      no overlaps.  */
2639                   else
2640                     {
2641                       *overlaps_a = conflict_fn_no_dependence ();
2642                       *overlaps_b = conflict_fn_no_dependence ();
2643                       *last_conflicts = integer_zero_node;
2644                       dependence_stats.num_siv_independent++;
2645                       return;
2646                     }
2647                 }
2648
2649               else
2650                 {
2651                   /* Example:
2652                      chrec_a = 12
2653                      chrec_b = {10, +, -1}
2654
2655                      In this case, chrec_a will not overlap with chrec_b.  */
2656                   *overlaps_a = conflict_fn_no_dependence ();
2657                   *overlaps_b = conflict_fn_no_dependence ();
2658                   *last_conflicts = integer_zero_node;
2659                   dependence_stats.num_siv_independent++;
2660                   return;
2661                 }
2662             }
2663         }
2664       else
2665         {
2666           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2667             {
2668               if (dump_file && (dump_flags & TDF_DETAILS))
2669                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2670
2671               *overlaps_a = conflict_fn_not_known ();
2672               *overlaps_b = conflict_fn_not_known ();
2673               *last_conflicts = chrec_dont_know;
2674               dependence_stats.num_siv_unimplemented++;
2675               return;
2676             }
2677           else
2678             {
2679               if (value2 == false)
2680                 {
2681                   /* Example:
2682                      chrec_a = 3
2683                      chrec_b = {10, +, -1}
2684                   */
2685                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2686                     {
2687                       tree numiter;
2688                       int loopnum = CHREC_VARIABLE (chrec_b);
2689
2690                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2691                       tmp = fold_build2 (EXACT_DIV_EXPR,
2692                                          integer_type_node, difference,
2693                                          CHREC_RIGHT (chrec_b));
2694                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2695                       *last_conflicts = integer_one_node;
2696
2697                       /* Perform weak-zero siv test to see if overlap is
2698                          outside the loop bounds.  */
2699                       numiter = get_number_of_iters_for_loop (loopnum);
2700
2701                       if (numiter != NULL_TREE
2702                           && TREE_CODE (tmp) == INTEGER_CST
2703                           && tree_int_cst_lt (numiter, tmp))
2704                         {
2705                           free_conflict_function (*overlaps_a);
2706                           free_conflict_function (*overlaps_b);
2707                           *overlaps_a = conflict_fn_no_dependence ();
2708                           *overlaps_b = conflict_fn_no_dependence ();
2709                           *last_conflicts = integer_zero_node;
2710                           dependence_stats.num_siv_independent++;
2711                           return;
2712                         }
2713                       dependence_stats.num_siv_dependent++;
2714                       return;
2715                     }
2716
2717                   /* When the step does not divide the difference, there
2718                      are no overlaps.  */
2719                   else
2720                     {
2721                       *overlaps_a = conflict_fn_no_dependence ();
2722                       *overlaps_b = conflict_fn_no_dependence ();
2723                       *last_conflicts = integer_zero_node;
2724                       dependence_stats.num_siv_independent++;
2725                       return;
2726                     }
2727                 }
2728               else
2729                 {
2730                   /* Example:
2731                      chrec_a = 3
2732                      chrec_b = {4, +, 1}
2733
2734                      In this case, chrec_a will not overlap with chrec_b.  */
2735                   *overlaps_a = conflict_fn_no_dependence ();
2736                   *overlaps_b = conflict_fn_no_dependence ();
2737                   *last_conflicts = integer_zero_node;
2738                   dependence_stats.num_siv_independent++;
2739                   return;
2740                 }
2741             }
2742         }
2743     }
2744 }
2745
2746 /* Helper recursive function for initializing the matrix A.  Returns
2747    the initial value of CHREC.  */
2748
2749 static int
2750 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2751 {
2752   gcc_assert (chrec);
2753
2754   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2755     return int_cst_value (chrec);
2756
2757   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2758   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2759 }
2760
2761 #define FLOOR_DIV(x,y) ((x) / (y))
2762
2763 /* Solves the special case of the Diophantine equation:
2764    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2765
2766    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
2767    number of iterations that loops X and Y run.  The overlaps will be
2768    constructed as evolutions in dimension DIM.  */
2769
2770 static void
2771 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2772                                          affine_fn *overlaps_a,
2773                                          affine_fn *overlaps_b,
2774                                          tree *last_conflicts, int dim)
2775 {
2776   if (((step_a > 0 && step_b > 0)
2777        || (step_a < 0 && step_b < 0)))
2778     {
2779       int step_overlaps_a, step_overlaps_b;
2780       int gcd_steps_a_b, last_conflict, tau2;
2781
2782       gcd_steps_a_b = gcd (step_a, step_b);
2783       step_overlaps_a = step_b / gcd_steps_a_b;
2784       step_overlaps_b = step_a / gcd_steps_a_b;
2785
2786       tau2 = FLOOR_DIV (niter, step_overlaps_a);
2787       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2788       last_conflict = tau2;
2789
2790       *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2791                                       build_int_cst (NULL_TREE,
2792                                                      step_overlaps_a));
2793       *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2794                                       build_int_cst (NULL_TREE,
2795                                                      step_overlaps_b));
2796       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2797     }
2798
2799   else
2800     {
2801       *overlaps_a = affine_fn_cst (integer_zero_node);
2802       *overlaps_b = affine_fn_cst (integer_zero_node);
2803       *last_conflicts = integer_zero_node;
2804     }
2805 }
2806
2807 /* Solves the special case of a Diophantine equation where CHREC_A is
2808    an affine bivariate function, and CHREC_B is an affine univariate
2809    function.  For example,
2810
2811    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2812
2813    has the following overlapping functions:
2814
2815    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2816    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2817    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2818
2819    FORNOW: This is a specialized implementation for a case occurring in
2820    a common benchmark.  Implement the general algorithm.  */
2821
2822 static void
2823 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2824                                       conflict_function **overlaps_a,
2825                                       conflict_function **overlaps_b,
2826                                       tree *last_conflicts)
2827 {
2828   bool xz_p, yz_p, xyz_p;
2829   int step_x, step_y, step_z;
2830   int niter_x, niter_y, niter_z, niter;
2831   tree numiter_x, numiter_y, numiter_z;
2832   affine_fn overlaps_a_xz, overlaps_b_xz;
2833   affine_fn overlaps_a_yz, overlaps_b_yz;
2834   affine_fn overlaps_a_xyz, overlaps_b_xyz;
2835   affine_fn ova1, ova2, ovb;
2836   tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2837
2838   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2839   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2840   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2841
2842   numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
2843   numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2844   numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2845
2846   if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
2847       || numiter_z == NULL_TREE)
2848     {
2849       if (dump_file && (dump_flags & TDF_DETAILS))
2850         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2851
2852       *overlaps_a = conflict_fn_not_known ();
2853       *overlaps_b = conflict_fn_not_known ();
2854       *last_conflicts = chrec_dont_know;
2855       return;
2856     }
2857
2858   niter_x = int_cst_value (numiter_x);
2859   niter_y = int_cst_value (numiter_y);
2860   niter_z = int_cst_value (numiter_z);
2861
2862   niter = MIN (niter_x, niter_z);
2863   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2864                                            &overlaps_a_xz,
2865                                            &overlaps_b_xz,
2866                                            &last_conflicts_xz, 1);
2867   niter = MIN (niter_y, niter_z);
2868   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2869                                            &overlaps_a_yz,
2870                                            &overlaps_b_yz,
2871                                            &last_conflicts_yz, 2);
2872   niter = MIN (niter_x, niter_z);
2873   niter = MIN (niter_y, niter);
2874   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2875                                            &overlaps_a_xyz,
2876                                            &overlaps_b_xyz,
2877                                            &last_conflicts_xyz, 3);
2878
2879   xz_p = !integer_zerop (last_conflicts_xz);
2880   yz_p = !integer_zerop (last_conflicts_yz);
2881   xyz_p = !integer_zerop (last_conflicts_xyz);
2882
2883   if (xz_p || yz_p || xyz_p)
2884     {
2885       ova1 = affine_fn_cst (integer_zero_node);
2886       ova2 = affine_fn_cst (integer_zero_node);
2887       ovb = affine_fn_cst (integer_zero_node);
2888       if (xz_p)
2889         {
2890           affine_fn t0 = ova1;
2891           affine_fn t2 = ovb;
2892
2893           ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2894           ovb = affine_fn_plus (ovb, overlaps_b_xz);
2895           affine_fn_free (t0);
2896           affine_fn_free (t2);
2897           *last_conflicts = last_conflicts_xz;
2898         }
2899       if (yz_p)
2900         {
2901           affine_fn t0 = ova2;
2902           affine_fn t2 = ovb;
2903
2904           ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2905           ovb = affine_fn_plus (ovb, overlaps_b_yz);
2906           affine_fn_free (t0);
2907           affine_fn_free (t2);
2908           *last_conflicts = last_conflicts_yz;
2909         }
2910       if (xyz_p)
2911         {
2912           affine_fn t0 = ova1;
2913           affine_fn t2 = ova2;
2914           affine_fn t4 = ovb;
2915
2916           ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2917           ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2918           ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2919           affine_fn_free (t0);
2920           affine_fn_free (t2);
2921           affine_fn_free (t4);
2922           *last_conflicts = last_conflicts_xyz;
2923         }
2924       *overlaps_a = conflict_fn (2, ova1, ova2);
2925       *overlaps_b = conflict_fn (1, ovb);
2926     }
2927   else
2928     {
2929       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2930       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2931       *last_conflicts = integer_zero_node;
2932     }
2933
2934   affine_fn_free (overlaps_a_xz);
2935   affine_fn_free (overlaps_b_xz);
2936   affine_fn_free (overlaps_a_yz);
2937   affine_fn_free (overlaps_b_yz);
2938   affine_fn_free (overlaps_a_xyz);
2939   affine_fn_free (overlaps_b_xyz);
2940 }
2941
2942 /* Determines the overlapping elements due to accesses CHREC_A and
2943    CHREC_B, that are affine functions.  This function cannot handle
2944    symbolic evolution functions, ie. when initial conditions are
2945    parameters, because it uses lambda matrices of integers.  */
2946
2947 static void
2948 analyze_subscript_affine_affine (tree chrec_a,
2949                                  tree chrec_b,
2950                                  conflict_function **overlaps_a,
2951                                  conflict_function **overlaps_b,
2952                                  tree *last_conflicts)
2953 {
2954   unsigned nb_vars_a, nb_vars_b, dim;
2955   int init_a, init_b, gamma, gcd_alpha_beta;
2956   int tau1, tau2;
2957   lambda_matrix A, U, S;
2958
2959   if (eq_evolutions_p (chrec_a, chrec_b))
2960     {
2961       /* The accessed index overlaps for each iteration in the
2962          loop.  */
2963       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2964       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2965       *last_conflicts = chrec_dont_know;
2966       return;
2967     }
2968   if (dump_file && (dump_flags & TDF_DETAILS))
2969     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2970
2971   /* For determining the initial intersection, we have to solve a
2972      Diophantine equation.  This is the most time consuming part.
2973
2974      For answering to the question: "Is there a dependence?" we have
2975      to prove that there exists a solution to the Diophantine
2976      equation, and that the solution is in the iteration domain,
2977      i.e. the solution is positive or zero, and that the solution
2978      happens before the upper bound loop.nb_iterations.  Otherwise
2979      there is no dependence.  This function outputs a description of
2980      the iterations that hold the intersections.  */
2981
2982   nb_vars_a = nb_vars_in_chrec (chrec_a);
2983   nb_vars_b = nb_vars_in_chrec (chrec_b);
2984
2985   dim = nb_vars_a + nb_vars_b;
2986   U = lambda_matrix_new (dim, dim);
2987   A = lambda_matrix_new (dim, 1);
2988   S = lambda_matrix_new (dim, 1);
2989
2990   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2991   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2992   gamma = init_b - init_a;
2993
2994   /* Don't do all the hard work of solving the Diophantine equation
2995      when we already know the solution: for example,
2996      | {3, +, 1}_1
2997      | {3, +, 4}_2
2998      | gamma = 3 - 3 = 0.
2999      Then the first overlap occurs during the first iterations:
3000      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3001   */
3002   if (gamma == 0)
3003     {
3004       if (nb_vars_a == 1 && nb_vars_b == 1)
3005         {
3006           int step_a, step_b;
3007           int niter, niter_a, niter_b;
3008           tree numiter_a, numiter_b;
3009           affine_fn ova, ovb;
3010
3011           numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3012           numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
3013           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
3014             {
3015               if (dump_file && (dump_flags & TDF_DETAILS))
3016                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3017               *overlaps_a = conflict_fn_not_known ();
3018               *overlaps_b = conflict_fn_not_known ();
3019               *last_conflicts = chrec_dont_know;
3020               goto end_analyze_subs_aa;
3021             }
3022
3023           niter_a = int_cst_value (numiter_a);
3024           niter_b = int_cst_value (numiter_b);
3025           niter = MIN (niter_a, niter_b);
3026
3027           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
3028           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
3029
3030           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
3031                                                    &ova, &ovb,
3032                                                    last_conflicts, 1);
3033           *overlaps_a = conflict_fn (1, ova);
3034           *overlaps_b = conflict_fn (1, ovb);
3035         }
3036
3037       else if (nb_vars_a == 2 && nb_vars_b == 1)
3038         compute_overlap_steps_for_affine_1_2
3039           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
3040
3041       else if (nb_vars_a == 1 && nb_vars_b == 2)
3042         compute_overlap_steps_for_affine_1_2
3043           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
3044
3045       else
3046         {
3047           if (dump_file && (dump_flags & TDF_DETAILS))
3048             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
3049           *overlaps_a = conflict_fn_not_known ();
3050           *overlaps_b = conflict_fn_not_known ();
3051           *last_conflicts = chrec_dont_know;
3052         }
3053       goto end_analyze_subs_aa;
3054     }
3055
3056   /* U.A = S */
3057   lambda_matrix_right_hermite (A, dim, 1, S, U);
3058
3059   if (S[0][0] < 0)
3060     {
3061       S[0][0] *= -1;
3062       lambda_matrix_row_negate (U, dim, 0);
3063     }
3064   gcd_alpha_beta = S[0][0];
3065
3066   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3067      but that is a quite strange case.  Instead of ICEing, answer
3068      don't know.  */
3069   if (gcd_alpha_beta == 0)
3070     {
3071       *overlaps_a = conflict_fn_not_known ();
3072       *overlaps_b = conflict_fn_not_known ();
3073       *last_conflicts = chrec_dont_know;
3074       goto end_analyze_subs_aa;
3075     }
3076
3077   /* The classic "gcd-test".  */
3078   if (!int_divides_p (gcd_alpha_beta, gamma))
3079     {
3080       /* The "gcd-test" has determined that there is no integer
3081          solution, i.e. there is no dependence.  */
3082       *overlaps_a = conflict_fn_no_dependence ();
3083       *overlaps_b = conflict_fn_no_dependence ();
3084       *last_conflicts = integer_zero_node;
3085     }
3086
3087   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
3088   else if (nb_vars_a == 1 && nb_vars_b == 1)
3089     {
3090       /* Both functions should have the same evolution sign.  */
3091       if (((A[0][0] > 0 && -A[1][0] > 0)
3092            || (A[0][0] < 0 && -A[1][0] < 0)))
3093         {
3094           /* The solutions are given by:
3095              |
3096              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
3097              |                           [u21 u22]    [y0]
3098
3099              For a given integer t.  Using the following variables,
3100
3101              | i0 = u11 * gamma / gcd_alpha_beta
3102              | j0 = u12 * gamma / gcd_alpha_beta
3103              | i1 = u21
3104              | j1 = u22
3105
3106              the solutions are:
3107
3108              | x0 = i0 + i1 * t,
3109              | y0 = j0 + j1 * t.  */
3110
3111           int i0, j0, i1, j1;
3112
3113           /* X0 and Y0 are the first iterations for which there is a
3114              dependence.  X0, Y0 are two solutions of the Diophantine
3115              equation: chrec_a (X0) = chrec_b (Y0).  */
3116           int x0, y0;
3117           int niter, niter_a, niter_b;
3118           tree numiter_a, numiter_b;
3119
3120           numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3121           numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
3122
3123           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
3124             {
3125               if (dump_file && (dump_flags & TDF_DETAILS))
3126                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3127               *overlaps_a = conflict_fn_not_known ();
3128               *overlaps_b = conflict_fn_not_known ();
3129               *last_conflicts = chrec_dont_know;
3130               goto end_analyze_subs_aa;
3131             }
3132
3133           niter_a = int_cst_value (numiter_a);
3134           niter_b = int_cst_value (numiter_b);
3135           niter = MIN (niter_a, niter_b);
3136
3137           i0 = U[0][0] * gamma / gcd_alpha_beta;
3138           j0 = U[0][1] * gamma / gcd_alpha_beta;
3139           i1 = U[1][0];
3140           j1 = U[1][1];
3141
3142           if ((i1 == 0 && i0 < 0)
3143               || (j1 == 0 && j0 < 0))
3144             {
3145               /* There is no solution.
3146                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3147                  falls in here, but for the moment we don't look at the
3148                  upper bound of the iteration domain.  */
3149               *overlaps_a = conflict_fn_no_dependence ();
3150               *overlaps_b = conflict_fn_no_dependence ();
3151               *last_conflicts = integer_zero_node;
3152             }
3153
3154           else
3155             {
3156               if (i1 > 0)
3157                 {
3158                   tau1 = CEIL (-i0, i1);
3159                   tau2 = FLOOR_DIV (niter - i0, i1);
3160
3161                   if (j1 > 0)
3162                     {
3163                       int last_conflict, min_multiple;
3164                       tau1 = MAX (tau1, CEIL (-j0, j1));
3165                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
3166
3167                       x0 = i1 * tau1 + i0;
3168                       y0 = j1 * tau1 + j0;
3169
3170                       /* At this point (x0, y0) is one of the
3171                          solutions to the Diophantine equation.  The
3172                          next step has to compute the smallest
3173                          positive solution: the first conflicts.  */
3174                       min_multiple = MIN (x0 / i1, y0 / j1);
3175                       x0 -= i1 * min_multiple;
3176                       y0 -= j1 * min_multiple;
3177
3178                       tau1 = (x0 - i0)/i1;
3179                       last_conflict = tau2 - tau1;
3180
3181                       /* If the overlap occurs outside of the bounds of the
3182                          loop, there is no dependence.  */
3183                       if (x0 > niter || y0  > niter)
3184                         {
3185                           *overlaps_a = conflict_fn_no_dependence ();
3186                           *overlaps_b = conflict_fn_no_dependence ();
3187                           *last_conflicts = integer_zero_node;
3188                         }
3189                       else
3190                         {
3191                           *overlaps_a
3192                             = conflict_fn (1,
3193                                 affine_fn_univar (build_int_cst (NULL_TREE, x0),
3194                                                   1,
3195                                                   build_int_cst (NULL_TREE, i1)));
3196                           *overlaps_b
3197                             = conflict_fn (1,
3198                                 affine_fn_univar (build_int_cst (NULL_TREE, y0),
3199                                                   1,
3200                                                   build_int_cst (NULL_TREE, j1)));
3201                           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
3202                         }
3203                     }
3204                   else
3205                     {
3206                       /* FIXME: For the moment, the upper bound of the
3207                          iteration domain for j is not checked.  */
3208                       if (dump_file && (dump_flags & TDF_DETAILS))
3209                         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3210                       *overlaps_a = conflict_fn_not_known ();
3211                       *overlaps_b = conflict_fn_not_known ();
3212                       *last_conflicts = chrec_dont_know;
3213                     }
3214                 }
3215
3216               else
3217                 {
3218                   /* FIXME: For the moment, the upper bound of the
3219                      iteration domain for i is not checked.  */
3220                   if (dump_file && (dump_flags & TDF_DETAILS))
3221                     fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3222                   *overlaps_a = conflict_fn_not_known ();
3223                   *overlaps_b = conflict_fn_not_known ();
3224                   *last_conflicts = chrec_dont_know;
3225                 }
3226             }
3227         }
3228       else
3229         {
3230           if (dump_file && (dump_flags & TDF_DETAILS))
3231             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3232           *overlaps_a = conflict_fn_not_known ();
3233           *overlaps_b = conflict_fn_not_known ();
3234           *last_conflicts = chrec_dont_know;
3235         }
3236     }
3237
3238   else
3239     {
3240       if (dump_file && (dump_flags & TDF_DETAILS))
3241         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3242       *overlaps_a = conflict_fn_not_known ();
3243       *overlaps_b = conflict_fn_not_known ();
3244       *last_conflicts = chrec_dont_know;
3245     }
3246
3247 end_analyze_subs_aa:
3248   if (dump_file && (dump_flags & TDF_DETAILS))
3249     {
3250       fprintf (dump_file, "  (overlaps_a = ");
3251       dump_conflict_function (dump_file, *overlaps_a);
3252       fprintf (dump_file, ")\n  (overlaps_b = ");
3253       dump_conflict_function (dump_file, *overlaps_b);
3254       fprintf (dump_file, ")\n");
3255       fprintf (dump_file, ")\n");
3256     }
3257 }
3258
3259 /* Returns true when analyze_subscript_affine_affine can be used for
3260    determining the dependence relation between chrec_a and chrec_b,
3261    that contain symbols.  This function modifies chrec_a and chrec_b
3262    such that the analysis result is the same, and such that they don't
3263    contain symbols, and then can safely be passed to the analyzer.
3264
3265    Example: The analysis of the following tuples of evolutions produce
3266    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3267    vs. {0, +, 1}_1
3268
3269    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3270    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3271 */
3272
3273 static bool
3274 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3275 {
3276   tree diff, type, left_a, left_b, right_b;
3277
3278   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3279       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3280     /* FIXME: For the moment not handled.  Might be refined later.  */
3281     return false;
3282
3283   type = chrec_type (*chrec_a);
3284   left_a = CHREC_LEFT (*chrec_a);
3285   left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3286   diff = chrec_fold_minus (type, left_a, left_b);
3287
3288   if (!evolution_function_is_constant_p (diff))
3289     return false;
3290
3291   if (dump_file && (dump_flags & TDF_DETAILS))
3292     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3293
3294   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3295                                      diff, CHREC_RIGHT (*chrec_a));
3296   right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3297   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3298                                      build_int_cst (type, 0),
3299                                      right_b);
3300   return true;
3301 }
3302
3303 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
3304    *OVERLAPS_B are initialized to the functions that describe the
3305    relation between the elements accessed twice by CHREC_A and
3306    CHREC_B.  For k >= 0, the following property is verified:
3307
3308    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
3309
3310 static void
3311 analyze_siv_subscript (tree chrec_a,
3312                        tree chrec_b,
3313                        conflict_function **overlaps_a,
3314                        conflict_function **overlaps_b,
3315                        tree *last_conflicts)
3316 {
3317   dependence_stats.num_siv++;
3318
3319   if (dump_file && (dump_flags & TDF_DETAILS))
3320     fprintf (dump_file, "(analyze_siv_subscript \n");
3321
3322   if (evolution_function_is_constant_p (chrec_a)
3323       && evolution_function_is_affine_p (chrec_b))
3324     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3325                                       overlaps_a, overlaps_b, last_conflicts);
3326
3327   else if (evolution_function_is_affine_p (chrec_a)
3328            && evolution_function_is_constant_p (chrec_b))
3329     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3330                                       overlaps_b, overlaps_a, last_conflicts);
3331
3332   else if (evolution_function_is_affine_p (chrec_a)
3333            && evolution_function_is_affine_p (chrec_b))
3334     {
3335       if (!chrec_contains_symbols (chrec_a)
3336           && !chrec_contains_symbols (chrec_b))
3337         {
3338           analyze_subscript_affine_affine (chrec_a, chrec_b,
3339                                            overlaps_a, overlaps_b,
3340                                            last_conflicts);
3341
3342           if (CF_NOT_KNOWN_P (*overlaps_a)
3343               || CF_NOT_KNOWN_P (*overlaps_b))
3344             dependence_stats.num_siv_unimplemented++;
3345           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3346                    || CF_NO_DEPENDENCE_P (*overlaps_b))
3347             dependence_stats.num_siv_independent++;
3348           else
3349             dependence_stats.num_siv_dependent++;
3350         }
3351       else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3352                                                         &chrec_b))
3353         {
3354           analyze_subscript_affine_affine (chrec_a, chrec_b,
3355                                            overlaps_a, overlaps_b,
3356                                            last_conflicts);
3357           /* FIXME: The number of iterations is a symbolic expression.
3358              Compute it properly.  */
3359           *last_conflicts = chrec_dont_know;
3360
3361           if (CF_NOT_KNOWN_P (*overlaps_a)
3362               || CF_NOT_KNOWN_P (*overlaps_b))
3363             dependence_stats.num_siv_unimplemented++;
3364           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3365                    || CF_NO_DEPENDENCE_P (*overlaps_b))
3366             dependence_stats.num_siv_independent++;
3367           else
3368             dependence_stats.num_siv_dependent++;
3369         }
3370       else
3371         goto siv_subscript_dontknow;
3372     }
3373
3374   else
3375     {
3376     siv_subscript_dontknow:;
3377       if (dump_file && (dump_flags & TDF_DETAILS))
3378         fprintf (dump_file, "siv test failed: unimplemented.\n");
3379       *overlaps_a = conflict_fn_not_known ();
3380       *overlaps_b = conflict_fn_not_known ();
3381       *last_conflicts = chrec_dont_know;
3382       dependence_stats.num_siv_unimplemented++;
3383     }
3384
3385   if (dump_file && (dump_flags & TDF_DETAILS))
3386     fprintf (dump_file, ")\n");
3387 }
3388
3389 /* Return true when the property can be computed.  RES should contain
3390    true when calling the first time this function, then it is set to
3391    false when one of the evolution steps of an affine CHREC does not
3392    divide the constant CST.  */
3393
3394 static bool
3395 chrec_steps_divide_constant_p (tree chrec,
3396                                tree cst,
3397                                bool *res)
3398 {
3399   switch (TREE_CODE (chrec))
3400     {
3401     case POLYNOMIAL_CHREC:
3402       if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3403         {
3404           if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3405             /* Keep RES to true, and iterate on other dimensions.  */
3406             return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3407
3408           *res = false;
3409           return true;
3410         }
3411       else
3412         /* When the step is a parameter the result is undetermined.  */
3413         return false;
3414
3415     default:
3416       /* On the initial condition, return true.  */
3417       return true;
3418     }
3419 }
3420
3421 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
3422    *OVERLAPS_B are initialized to the functions that describe the
3423    relation between the elements accessed twice by CHREC_A and
3424    CHREC_B.  For k >= 0, the following property is verified:
3425
3426    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
3427
3428 static void
3429 analyze_miv_subscript (tree chrec_a,
3430                        tree chrec_b,
3431                        conflict_function **overlaps_a,
3432                        conflict_function **overlaps_b,
3433                        tree *last_conflicts)
3434 {
3435   /* FIXME:  This is a MIV subscript, not yet handled.
3436      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3437      (A[i] vs. A[j]).
3438
3439      In the SIV test we had to solve a Diophantine equation with two
3440      variables.  In the MIV case we have to solve a Diophantine
3441      equation with 2*n variables (if the subscript uses n IVs).
3442   */
3443   bool divide_p = true;
3444   tree difference;
3445   dependence_stats.num_miv++;
3446   if (dump_file && (dump_flags & TDF_DETAILS))
3447     fprintf (dump_file, "(analyze_miv_subscript \n");
3448
3449   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
3450   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
3451   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3452
3453   if (eq_evolutions_p (chrec_a, chrec_b))
3454     {
3455       /* Access functions are the same: all the elements are accessed
3456          in the same order.  */
3457       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3458       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3459       *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3460       dependence_stats.num_miv_dependent++;
3461     }
3462
3463   else if (evolution_function_is_constant_p (difference)
3464            /* For the moment, the following is verified:
3465               evolution_function_is_affine_multivariate_p (chrec_a) */
3466            && chrec_steps_divide_constant_p (chrec_a, difference, &divide_p)
3467            && !divide_p)
3468     {
3469       /* testsuite/.../ssa-chrec-33.c
3470          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
3471
3472          The difference is 1, and the evolution steps are equal to 2,
3473          consequently there are no overlapping elements.  */
3474       *overlaps_a = conflict_fn_no_dependence ();
3475       *overlaps_b = conflict_fn_no_dependence ();
3476       *last_conflicts = integer_zero_node;
3477       dependence_stats.num_miv_independent++;
3478     }
3479
3480   else if (evolution_function_is_affine_multivariate_p (chrec_a)
3481            && !chrec_contains_symbols (chrec_a)
3482            && evolution_function_is_affine_multivariate_p (chrec_b)
3483            && !chrec_contains_symbols (chrec_b))
3484     {
3485       /* testsuite/.../ssa-chrec-35.c
3486          {0, +, 1}_2  vs.  {0, +, 1}_3
3487          the overlapping elements are respectively located at iterations:
3488          {0, +, 1}_x and {0, +, 1}_x,
3489          in other words, we have the equality:
3490          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3491
3492          Other examples:
3493          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3494          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3495
3496          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3497          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3498       */
3499       analyze_subscript_affine_affine (chrec_a, chrec_b,
3500                                        overlaps_a, overlaps_b, last_conflicts);
3501
3502       if (CF_NOT_KNOWN_P (*overlaps_a)
3503           || CF_NOT_KNOWN_P (*overlaps_b))
3504         dependence_stats.num_miv_unimplemented++;
3505       else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3506                || CF_NO_DEPENDENCE_P (*overlaps_b))
3507         dependence_stats.num_miv_independent++;
3508       else
3509         dependence_stats.num_miv_dependent++;
3510     }
3511
3512   else
3513     {
3514       /* When the analysis is too difficult, answer "don't know".  */
3515       if (dump_file && (dump_flags & TDF_DETAILS))
3516         fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3517
3518       *overlaps_a = conflict_fn_not_known ();
3519       *overlaps_b = conflict_fn_not_known ();
3520       *last_conflicts = chrec_dont_know;
3521       dependence_stats.num_miv_unimplemented++;
3522     }
3523
3524   if (dump_file && (dump_flags & TDF_DETAILS))
3525     fprintf (dump_file, ")\n");
3526 }
3527
3528 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3529    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3530    two functions that describe the iterations that contain conflicting
3531    elements.
3532
3533    Remark: For an integer k >= 0, the following equality is true:
3534
3535    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3536 */
3537
3538 static void
3539 analyze_overlapping_iterations (tree chrec_a,
3540                                 tree chrec_b,
3541                                 conflict_function **overlap_iterations_a,
3542                                 conflict_function **overlap_iterations_b,
3543                                 tree *last_conflicts)
3544 {
3545   dependence_stats.num_subscript_tests++;
3546
3547   if (dump_file && (dump_flags & TDF_DETAILS))
3548     {
3549       fprintf (dump_file, "(analyze_overlapping_iterations \n");
3550       fprintf (dump_file, "  (chrec_a = ");
3551       print_generic_expr (dump_file, chrec_a, 0);
3552       fprintf (dump_file, ")\n  (chrec_b = ");
3553       print_generic_expr (dump_file, chrec_b, 0);
3554       fprintf (dump_file, ")\n");
3555     }
3556
3557   if (chrec_a == NULL_TREE
3558       || chrec_b == NULL_TREE
3559       || chrec_contains_undetermined (chrec_a)
3560       || chrec_contains_undetermined (chrec_b))
3561     {
3562       dependence_stats.num_subscript_undetermined++;
3563
3564       *overlap_iterations_a = conflict_fn_not_known ();
3565       *overlap_iterations_b = conflict_fn_not_known ();
3566     }
3567
3568   /* If they are the same chrec, and are affine, they overlap
3569      on every iteration.  */
3570   else if (eq_evolutions_p (chrec_a, chrec_b)
3571            && evolution_function_is_affine_multivariate_p (chrec_a))
3572     {
3573       dependence_stats.num_same_subscript_function++;
3574       *overlap_iterations_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3575       *overlap_iterations_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3576       *last_conflicts = chrec_dont_know;
3577     }
3578
3579   /* If they aren't the same, and aren't affine, we can't do anything
3580      yet. */
3581   else if ((chrec_contains_symbols (chrec_a)
3582             || chrec_contains_symbols (chrec_b))
3583            && (!evolution_function_is_affine_multivariate_p (chrec_a)
3584                || !evolution_function_is_affine_multivariate_p (chrec_b)))
3585     {
3586       dependence_stats.num_subscript_undetermined++;
3587       *overlap_iterations_a = conflict_fn_not_known ();
3588       *overlap_iterations_b = conflict_fn_not_known ();
3589     }
3590
3591   else if (ziv_subscript_p (chrec_a, chrec_b))
3592     analyze_ziv_subscript (chrec_a, chrec_b,
3593                            overlap_iterations_a, overlap_iterations_b,
3594                            last_conflicts);
3595
3596   else if (siv_subscript_p (chrec_a, chrec_b))
3597     analyze_siv_subscript (chrec_a, chrec_b,
3598                            overlap_iterations_a, overlap_iterations_b,
3599                            last_conflicts);
3600
3601   else
3602     analyze_miv_subscript (chrec_a, chrec_b,
3603                            overlap_iterations_a, overlap_iterations_b,
3604                            last_conflicts);
3605
3606   if (dump_file && (dump_flags & TDF_DETAILS))
3607     {
3608       fprintf (dump_file, "  (overlap_iterations_a = ");
3609       dump_conflict_function (dump_file, *overlap_iterations_a);
3610       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
3611       dump_conflict_function (dump_file, *overlap_iterations_b);
3612       fprintf (dump_file, ")\n");
3613       fprintf (dump_file, ")\n");
3614     }
3615 }
3616
3617 /* Helper function for uniquely inserting distance vectors.  */
3618
3619 static void
3620 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3621 {
3622   unsigned i;
3623   lambda_vector v;
3624
3625   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3626     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3627       return;
3628
3629   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3630 }
3631
3632 /* Helper function for uniquely inserting direction vectors.  */
3633
3634 static void
3635 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3636 {
3637   unsigned i;
3638   lambda_vector v;
3639
3640   for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3641     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3642       return;
3643
3644   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3645 }
3646
3647 /* Add a distance of 1 on all the loops outer than INDEX.  If we
3648    haven't yet determined a distance for this outer loop, push a new
3649    distance vector composed of the previous distance, and a distance
3650    of 1 for this outer loop.  Example:
3651
3652    | loop_1
3653    |   loop_2
3654    |     A[10]
3655    |   endloop_2
3656    | endloop_1
3657
3658    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
3659    save (0, 1), then we have to save (1, 0).  */
3660
3661 static void
3662 add_outer_distances (struct data_dependence_relation *ddr,
3663                      lambda_vector dist_v, int index)
3664 {
3665   /* For each outer loop where init_v is not set, the accesses are
3666      in dependence of distance 1 in the loop.  */
3667   while (--index >= 0)
3668     {
3669       lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3670       lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3671       save_v[index] = 1;
3672       save_dist_v (ddr, save_v);
3673     }
3674 }
3675
3676 /* Return false when fail to represent the data dependence as a
3677    distance vector.  INIT_B is set to true when a component has been
3678    added to the distance vector DIST_V.  INDEX_CARRY is then set to
3679    the index in DIST_V that carries the dependence.  */
3680
3681 static bool
3682 build_classic_dist_vector_1 (struct data_dependence_relation *ddr,
3683                              struct data_reference *ddr_a,
3684                              struct data_reference *ddr_b,
3685                              lambda_vector dist_v, bool *init_b,
3686                              int *index_carry)
3687 {
3688   unsigned i;
3689   lambda_vector init_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3690
3691   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3692     {
3693       tree access_fn_a, access_fn_b;
3694       struct subscript *subscript = DDR_SUBSCRIPT (ddr, i);
3695
3696       if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3697         {
3698           non_affine_dependence_relation (ddr);
3699           return false;
3700         }
3701
3702       access_fn_a = DR_ACCESS_FN (ddr_a, i);
3703       access_fn_b = DR_ACCESS_FN (ddr_b, i);
3704
3705       if (TREE_CODE (access_fn_a) == POLYNOMIAL_CHREC
3706           && TREE_CODE (access_fn_b) == POLYNOMIAL_CHREC)
3707         {
3708           int dist, index;
3709           int index_a = index_in_loop_nest (CHREC_VARIABLE (access_fn_a),
3710                                             DDR_LOOP_NEST (ddr));
3711           int index_b = index_in_loop_nest (CHREC_VARIABLE (access_fn_b),
3712                                             DDR_LOOP_NEST (ddr));
3713
3714           /* The dependence is carried by the outermost loop.  Example:
3715              | loop_1
3716              |   A[{4, +, 1}_1]
3717              |   loop_2
3718              |     A[{5, +, 1}_2]
3719              |   endloop_2
3720              | endloop_1
3721              In this case, the dependence is carried by loop_1.  */
3722           index = index_a < index_b ? index_a : index_b;
3723           *index_carry = MIN (index, *index_carry);
3724
3725           if (chrec_contains_undetermined (SUB_DISTANCE (subscript)))
3726             {
3727               non_affine_dependence_relation (ddr);
3728               return false;
3729             }
3730
3731           dist = int_cst_value (SUB_DISTANCE (subscript));
3732
3733           /* This is the subscript coupling test.  If we have already
3734              recorded a distance for this loop (a distance coming from
3735              another subscript), it should be the same.  For example,
3736              in the following code, there is no dependence:
3737
3738              | loop i = 0, N, 1
3739              |   T[i+1][i] = ...
3740              |   ... = T[i][i]
3741              | endloop
3742           */
3743           if (init_v[index] != 0 && dist_v[index] != dist)
3744             {
3745               finalize_ddr_dependent (ddr, chrec_known);
3746               return false;
3747             }
3748
3749           dist_v[index] = dist;
3750           init_v[index] = 1;
3751           *init_b = true;
3752         }
3753       else
3754         {
3755           /* This can be for example an affine vs. constant dependence
3756              (T[i] vs. T[3]) that is not an affine dependence and is
3757              not representable as a distance vector.  */
3758           non_affine_dependence_relation (ddr);
3759           return false;
3760         }
3761     }
3762
3763   return true;
3764 }
3765
3766 /* Return true when the DDR contains two data references that have the
3767    same access functions.  */
3768
3769 static bool
3770 same_access_functions (struct data_dependence_relation *ddr)
3771 {
3772   unsigned i;
3773
3774   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3775     if (!eq_evolutions_p (DR_ACCESS_FN (DDR_A (ddr), i),
3776                           DR_ACCESS_FN (DDR_B (ddr), i)))
3777       return false;
3778
3779   return true;
3780 }
3781
3782 /* Helper function for the case where DDR_A and DDR_B are the same
3783    multivariate access function.  */
3784
3785 static void
3786 add_multivariate_self_dist (struct data_dependence_relation *ddr, tree c_2)
3787 {
3788   int x_1, x_2;
3789   tree c_1 = CHREC_LEFT (c_2);
3790   tree c_0 = CHREC_LEFT (c_1);
3791   lambda_vector dist_v;
3792
3793   /* Polynomials with more than 2 variables are not handled yet.  */
3794   if (TREE_CODE (c_0) != INTEGER_CST)
3795     {
3796       DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3797       return;
3798     }
3799
3800   x_2 = index_in_loop_nest (CHREC_VARIABLE (c_2), DDR_LOOP_NEST (ddr));
3801   x_1 = index_in_loop_nest (CHREC_VARIABLE (c_1), DDR_LOOP_NEST (ddr));
3802
3803   /* For "{{0, +, 2}_1, +, 3}_2" the distance vector is (3, -2).  */
3804   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3805   dist_v[x_1] = int_cst_value (CHREC_RIGHT (c_2));
3806   dist_v[x_2] = -int_cst_value (CHREC_RIGHT (c_1));
3807   save_dist_v (ddr, dist_v);
3808
3809   add_outer_distances (ddr, dist_v, x_1);
3810 }
3811
3812 /* Helper function for the case where DDR_A and DDR_B are the same
3813    access functions.  */
3814
3815 static void
3816 add_other_self_distances (struct data_dependence_relation *ddr)
3817 {
3818   lambda_vector dist_v;
3819   unsigned i;
3820   int index_carry = DDR_NB_LOOPS (ddr);
3821
3822   for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
3823     {
3824       tree access_fun = DR_ACCESS_FN (DDR_A (ddr), i);
3825
3826       if (TREE_CODE (access_fun) == POLYNOMIAL_CHREC)
3827         {
3828           if (!evolution_function_is_univariate_p (access_fun))
3829             {
3830               if (DDR_NUM_SUBSCRIPTS (ddr) != 1)
3831                 {
3832                   DDR_ARE_DEPENDENT (ddr) = chrec_dont_know;
3833                   return;
3834                 }
3835
3836               add_multivariate_self_dist (ddr, DR_ACCESS_FN (DDR_A (ddr), 0));
3837               return;
3838             }
3839
3840           index_carry = MIN (index_carry,
3841                              index_in_loop_nest (CHREC_VARIABLE (access_fun),
3842                                                  DDR_LOOP_NEST (ddr)));
3843         }
3844     }
3845
3846   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3847   add_outer_distances (ddr, dist_v, index_carry);
3848 }
3849
3850 /* Compute the classic per loop distance vector.  DDR is the data
3851    dependence relation to build a vector from.  Return false when fail
3852    to represent the data dependence as a distance vector.  */
3853
3854 static bool
3855 build_classic_dist_vector (struct data_dependence_relation *ddr)
3856 {
3857   bool init_b = false;
3858   int index_carry = DDR_NB_LOOPS (ddr);
3859   lambda_vector dist_v;
3860
3861   if (DDR_ARE_DEPENDENT (ddr) != NULL_TREE)
3862     return true;
3863
3864   if (same_access_functions (ddr))
3865     {
3866       /* Save the 0 vector.  */
3867       dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3868       save_dist_v (ddr, dist_v);
3869
3870       if (DDR_NB_LOOPS (ddr) > 1)
3871         add_other_self_distances (ddr);
3872
3873       return true;
3874     }
3875
3876   dist_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3877   if (!build_classic_dist_vector_1 (ddr, DDR_A (ddr), DDR_B (ddr),
3878                                     dist_v, &init_b, &index_carry))
3879     return false;
3880
3881   /* Save the distance vector if we initialized one.  */
3882   if (init_b)
3883     {
3884       /* Verify a basic constraint: classic distance vectors should
3885          always be lexicographically positive.
3886
3887          Data references are collected in the order of execution of
3888          the program, thus for the following loop
3889
3890          | for (i = 1; i < 100; i++)
3891          |   for (j = 1; j < 100; j++)
3892          |     {
3893          |       t = T[j+1][i-1];  // A
3894          |       T[j][i] = t + 2;  // B
3895          |     }
3896
3897          references are collected following the direction of the wind:
3898          A then B.  The data dependence tests are performed also
3899          following this order, such that we're looking at the distance
3900          separating the elements accessed by A from the elements later
3901          accessed by B.  But in this example, the distance returned by
3902          test_dep (A, B) is lexicographically negative (-1, 1), that
3903          means that the access A occurs later than B with respect to
3904          the outer loop, ie. we're actually looking upwind.  In this
3905          case we solve test_dep (B, A) looking downwind to the
3906          lexicographically positive solution, that returns the
3907          distance vector (1, -1).  */
3908       if (!lambda_vector_lexico_pos (dist_v, DDR_NB_LOOPS (ddr)))
3909         {
3910           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3911           subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3912           compute_subscript_distance (ddr);
3913           build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3914                                        save_v, &init_b, &index_carry);
3915           save_dist_v (ddr, save_v);
3916
3917           /* In this case there is a dependence forward for all the
3918              outer loops:
3919
3920              | for (k = 1; k < 100; k++)
3921              |  for (i = 1; i < 100; i++)
3922              |   for (j = 1; j < 100; j++)
3923              |     {
3924              |       t = T[j+1][i-1];  // A
3925              |       T[j][i] = t + 2;  // B
3926              |     }
3927
3928              the vectors are:
3929              (0,  1, -1)
3930              (1,  1, -1)
3931              (1, -1,  1)
3932           */
3933           if (DDR_NB_LOOPS (ddr) > 1)
3934             {
3935               add_outer_distances (ddr, save_v, index_carry);
3936               add_outer_distances (ddr, dist_v, index_carry);
3937             }
3938         }
3939       else
3940         {
3941           lambda_vector save_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3942           lambda_vector_copy (dist_v, save_v, DDR_NB_LOOPS (ddr));
3943           save_dist_v (ddr, save_v);
3944
3945           if (DDR_NB_LOOPS (ddr) > 1)
3946             {
3947               lambda_vector opposite_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
3948
3949               subscript_dependence_tester_1 (ddr, DDR_B (ddr), DDR_A (ddr));
3950               compute_subscript_distance (ddr);
3951               build_classic_dist_vector_1 (ddr, DDR_B (ddr), DDR_A (ddr),
3952                                            opposite_v, &init_b, &index_carry);
3953
3954               add_outer_distances (ddr, dist_v, index_carry);
3955               add_outer_distances (ddr, opposite_v, index_carry);
3956             }
3957         }
3958     }
3959   else
3960     {
3961       /* There is a distance of 1 on all the outer loops: Example:
3962          there is a dependence of distance 1 on loop_1 for the array A.
3963
3964          | loop_1
3965          |   A[5] = ...
3966          | endloop
3967       */
3968       add_outer_distances (ddr, dist_v,
3969                            lambda_vector_first_nz (dist_v,
3970                                                    DDR_NB_LOOPS (ddr), 0));
3971     }
3972
3973   if (dump_file && (dump_flags & TDF_DETAILS))
3974     {
3975       unsigned i;
3976
3977       fprintf (dump_file, "(build_classic_dist_vector\n");
3978       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
3979         {
3980           fprintf (dump_file, "  dist_vector = (");
3981           print_lambda_vector (dump_file, DDR_DIST_VECT (ddr, i),
3982                                DDR_NB_LOOPS (ddr));
3983           fprintf (dump_file, "  )\n");
3984         }
3985       fprintf (dump_file, ")\n");
3986     }
3987
3988   return true;
3989 }
3990
3991 /* Return the direction for a given distance.
3992    FIXME: Computing dir this way is suboptimal, since dir can catch
3993    cases that dist is unable to represent.  */
3994
3995 static inline enum data_dependence_direction
3996 dir_from_dist (int dist)
3997 {
3998   if (dist > 0)
3999     return dir_positive;
4000   else if (dist < 0)
4001     return dir_negative;
4002   else
4003     return dir_equal;
4004 }
4005
4006 /* Compute the classic per loop direction vector.  DDR is the data
4007    dependence relation to build a vector from.  */
4008
4009 static void
4010 build_classic_dir_vector (struct data_dependence_relation *ddr)
4011 {
4012   unsigned i, j;
4013   lambda_vector dist_v;
4014
4015   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, dist_v); i++)
4016     {
4017       lambda_vector dir_v = lambda_vector_new (DDR_NB_LOOPS (ddr));
4018
4019       for (j = 0; j < DDR_NB_LOOPS (ddr); j++)
4020         dir_v[j] = dir_from_dist (dist_v[j]);
4021
4022       save_dir_v (ddr, dir_v);
4023     }
4024 }
4025
4026 /* Helper function.  Returns true when there is a dependence between
4027    data references DRA and DRB.  */
4028
4029 static bool
4030 subscript_dependence_tester_1 (struct data_dependence_relation *ddr,
4031                                struct data_reference *dra,
4032                                struct data_reference *drb)
4033 {
4034   unsigned int i;
4035   tree last_conflicts;
4036   struct subscript *subscript;
4037
4038   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4039        i++)
4040     {
4041       conflict_function *overlaps_a, *overlaps_b;
4042
4043       analyze_overlapping_iterations (DR_ACCESS_FN (dra, i),
4044                                       DR_ACCESS_FN (drb, i),
4045                                       &overlaps_a, &overlaps_b,
4046                                       &last_conflicts);
4047
4048       if (CF_NOT_KNOWN_P (overlaps_a)
4049           || CF_NOT_KNOWN_P (overlaps_b))
4050         {
4051           finalize_ddr_dependent (ddr, chrec_dont_know);
4052           dependence_stats.num_dependence_undetermined++;
4053           free_conflict_function (overlaps_a);
4054           free_conflict_function (overlaps_b);
4055           return false;
4056         }
4057
4058       else if (CF_NO_DEPENDENCE_P (overlaps_a)
4059                || CF_NO_DEPENDENCE_P (overlaps_b))
4060         {
4061           finalize_ddr_dependent (ddr, chrec_known);
4062           dependence_stats.num_dependence_independent++;
4063           free_conflict_function (overlaps_a);
4064           free_conflict_function (overlaps_b);
4065           return false;
4066         }
4067
4068       else
4069         {
4070           SUB_CONFLICTS_IN_A (subscript) = overlaps_a;
4071           SUB_CONFLICTS_IN_B (subscript) = overlaps_b;
4072           SUB_LAST_CONFLICT (subscript) = last_conflicts;
4073         }
4074     }
4075
4076   return true;
4077 }
4078
4079 /* Computes the conflicting iterations, and initialize DDR.  */
4080
4081 static void
4082 subscript_dependence_tester (struct data_dependence_relation *ddr)
4083 {
4084
4085   if (dump_file && (dump_flags & TDF_DETAILS))
4086     fprintf (dump_file, "(subscript_dependence_tester \n");
4087
4088   if (subscript_dependence_tester_1 (ddr, DDR_A (ddr), DDR_B (ddr)))
4089     dependence_stats.num_dependence_dependent++;
4090
4091   compute_subscript_distance (ddr);
4092   if (build_classic_dist_vector (ddr))
4093     build_classic_dir_vector (ddr);
4094
4095   if (dump_file && (dump_flags & TDF_DETAILS))
4096     fprintf (dump_file, ")\n");
4097 }
4098
4099 /* Returns true when all the access functions of A are affine or
4100    constant.  */
4101
4102 static bool
4103 access_functions_are_affine_or_constant_p (struct data_reference *a)
4104 {
4105   unsigned int i;
4106   VEC(tree,heap) **fns = DR_ACCESS_FNS_ADDR (a);
4107   tree t;
4108
4109   for (i = 0; VEC_iterate (tree, *fns, i, t); i++)
4110     if (!evolution_function_is_constant_p (t)
4111         && !evolution_function_is_affine_multivariate_p (t))
4112       return false;
4113
4114   return true;
4115 }
4116
4117 /* This computes the affine dependence relation between A and B.
4118    CHREC_KNOWN is used for representing the independence between two
4119    accesses, while CHREC_DONT_KNOW is used for representing the unknown
4120    relation.
4121
4122    Note that it is possible to stop the computation of the dependence
4123    relation the first time we detect a CHREC_KNOWN element for a given
4124    subscript.  */
4125
4126 static void
4127 compute_affine_dependence (struct data_dependence_relation *ddr)
4128 {
4129   struct data_reference *dra = DDR_A (ddr);
4130   struct data_reference *drb = DDR_B (ddr);
4131
4132   if (dump_file && (dump_flags & TDF_DETAILS))
4133     {
4134       fprintf (dump_file, "(compute_affine_dependence\n");
4135       fprintf (dump_file, "  (stmt_a = \n");
4136       print_generic_expr (dump_file, DR_STMT (dra), 0);
4137       fprintf (dump_file, ")\n  (stmt_b = \n");
4138       print_generic_expr (dump_file, DR_STMT (drb), 0);
4139       fprintf (dump_file, ")\n");
4140     }
4141
4142   /* Analyze only when the dependence relation is not yet known.  */
4143   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
4144     {
4145       dependence_stats.num_dependence_tests++;
4146
4147       if (access_functions_are_affine_or_constant_p (dra)
4148           && access_functions_are_affine_or_constant_p (drb))
4149         subscript_dependence_tester (ddr);
4150
4151       /* As a last case, if the dependence cannot be determined, or if
4152          the dependence is considered too difficult to determine, answer
4153          "don't know".  */
4154       else
4155         {
4156           dependence_stats.num_dependence_undetermined++;
4157
4158           if (dump_file && (dump_flags & TDF_DETAILS))
4159             {
4160               fprintf (dump_file, "Data ref a:\n");
4161               dump_data_reference (dump_file, dra);
4162               fprintf (dump_file, "Data ref b:\n");
4163               dump_data_reference (dump_file, drb);
4164               fprintf (dump_file, "affine dependence test not usable: access function not affine or constant.\n");
4165             }
4166           finalize_ddr_dependent (ddr, chrec_dont_know);
4167         }
4168     }
4169
4170   if (dump_file && (dump_flags & TDF_DETAILS))
4171     fprintf (dump_file, ")\n");
4172 }
4173
4174 /* This computes the dependence relation for the same data
4175    reference into DDR.  */
4176
4177 static void
4178 compute_self_dependence (struct data_dependence_relation *ddr)
4179 {
4180   unsigned int i;
4181   struct subscript *subscript;
4182
4183   for (i = 0; VEC_iterate (subscript_p, DDR_SUBSCRIPTS (ddr), i, subscript);
4184        i++)
4185     {
4186       /* The accessed index overlaps for each iteration.  */
4187       SUB_CONFLICTS_IN_A (subscript)
4188               = conflict_fn (1, affine_fn_cst (integer_zero_node));
4189       SUB_CONFLICTS_IN_B (subscript)
4190               = conflict_fn (1, affine_fn_cst (integer_zero_node));
4191       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
4192     }
4193
4194   /* The distance vector is the zero vector.  */
4195   save_dist_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4196   save_dir_v (ddr, lambda_vector_new (DDR_NB_LOOPS (ddr)));
4197 }
4198
4199 /* Compute in DEPENDENCE_RELATIONS the data dependence graph for all
4200    the data references in DATAREFS, in the LOOP_NEST.  When
4201    COMPUTE_SELF_AND_RR is FALSE, don't compute read-read and self
4202    relations.  */
4203
4204 static void
4205 compute_all_dependences (VEC (data_reference_p, heap) *datarefs,
4206                          VEC (ddr_p, heap) **dependence_relations,
4207                          VEC (loop_p, heap) *loop_nest,
4208                          bool compute_self_and_rr)
4209 {
4210   struct data_dependence_relation *ddr;
4211   struct data_reference *a, *b;
4212   unsigned int i, j;
4213
4214   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4215     for (j = i + 1; VEC_iterate (data_reference_p, datarefs, j, b); j++)
4216       if (!DR_IS_READ (a) || !DR_IS_READ (b) || compute_self_and_rr)
4217         {
4218           ddr = initialize_data_dependence_relation (a, b, loop_nest);
4219           VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4220           compute_affine_dependence (ddr);
4221         }
4222
4223   if (compute_self_and_rr)
4224     for (i = 0; VEC_iterate (data_reference_p, datarefs, i, a); i++)
4225       {
4226         ddr = initialize_data_dependence_relation (a, a, loop_nest);
4227         VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4228         compute_self_dependence (ddr);
4229       }
4230 }
4231
4232 /* Stores the locations of memory references in STMT to REFERENCES.  Returns
4233    true if STMT clobbers memory, false otherwise.  */
4234
4235 bool
4236 get_references_in_stmt (tree stmt, VEC (data_ref_loc, heap) **references)
4237 {
4238   bool clobbers_memory = false;
4239   data_ref_loc *ref;
4240   tree *op0, *op1, args, call;
4241
4242   *references = NULL;
4243
4244   /* ASM_EXPR and CALL_EXPR may embed arbitrary side effects.
4245      Calls have side-effects, except those to const or pure
4246      functions.  */
4247   call = get_call_expr_in (stmt);
4248   if ((call
4249        && !(call_expr_flags (call) & (ECF_CONST | ECF_PURE)))
4250       || (TREE_CODE (stmt) == ASM_EXPR
4251           && ASM_VOLATILE_P (stmt)))
4252     clobbers_memory = true;
4253
4254   if (ZERO_SSA_OPERANDS (stmt, SSA_OP_ALL_VIRTUALS))
4255     return clobbers_memory;
4256
4257   if (TREE_CODE (stmt) ==  GIMPLE_MODIFY_STMT)
4258     {
4259       op0 = &GIMPLE_STMT_OPERAND (stmt, 0);
4260       op1 = &GIMPLE_STMT_OPERAND (stmt, 1);
4261
4262       if (DECL_P (*op1)
4263           || REFERENCE_CLASS_P (*op1))
4264         {
4265           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4266           ref->pos = op1;
4267           ref->is_read = true;
4268         }
4269
4270       if (DECL_P (*op0)
4271           || REFERENCE_CLASS_P (*op0))
4272         {
4273           ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4274           ref->pos = op0;
4275           ref->is_read = false;
4276         }
4277     }
4278
4279   if (call)
4280     {
4281       for (args = TREE_OPERAND (call, 1); args; args = TREE_CHAIN (args))
4282         {
4283           op0 = &TREE_VALUE (args);
4284           if (DECL_P (*op0)
4285               || REFERENCE_CLASS_P (*op0))
4286             {
4287               ref = VEC_safe_push (data_ref_loc, heap, *references, NULL);
4288               ref->pos = op0;
4289               ref->is_read = true;
4290             }
4291         }
4292     }
4293
4294   return clobbers_memory;
4295 }
4296
4297 /* Stores the data references in STMT to DATAREFS.  If there is an unanalyzable
4298    reference, returns false, otherwise returns true.  */
4299
4300 static bool
4301 find_data_references_in_stmt (tree stmt,
4302                               VEC (data_reference_p, heap) **datarefs)
4303 {
4304   unsigned i;
4305   VEC (data_ref_loc, heap) *references;
4306   data_ref_loc *ref;
4307   bool ret = true;
4308   data_reference_p dr;
4309
4310   if (get_references_in_stmt (stmt, &references))
4311     {
4312       VEC_free (data_ref_loc, heap, references);
4313       return false;
4314     }
4315
4316   for (i = 0; VEC_iterate (data_ref_loc, references, i, ref); i++)
4317     {
4318       dr = create_data_ref (*ref->pos, stmt, ref->is_read);
4319       if (dr)
4320         VEC_safe_push (data_reference_p, heap, *datarefs, dr);
4321       else
4322         {
4323           ret = false;
4324           break;
4325         }
4326     }
4327   VEC_free (data_ref_loc, heap, references);
4328   return ret;
4329 }
4330
4331 /* Search the data references in LOOP, and record the information into
4332    DATAREFS.  Returns chrec_dont_know when failing to analyze a
4333    difficult case, returns NULL_TREE otherwise.
4334
4335    TODO: This function should be made smarter so that it can handle address
4336    arithmetic as if they were array accesses, etc.  */
4337
4338 tree
4339 find_data_references_in_loop (struct loop *loop,
4340                               VEC (data_reference_p, heap) **datarefs)
4341 {
4342   basic_block bb, *bbs;
4343   unsigned int i;
4344   block_stmt_iterator bsi;
4345
4346   bbs = get_loop_body (loop);
4347
4348   for (i = 0; i < loop->num_nodes; i++)
4349     {
4350       bb = bbs[i];
4351
4352       for (bsi = bsi_start (bb); !bsi_end_p (bsi); bsi_next (&bsi))
4353         {
4354           tree stmt = bsi_stmt (bsi);
4355
4356           if (!find_data_references_in_stmt (stmt, datarefs))
4357             {
4358               struct data_reference *res;
4359               res = XNEW (struct data_reference);
4360               DR_STMT (res) = NULL_TREE;
4361               DR_REF (res) = NULL_TREE;
4362               DR_BASE_OBJECT (res) = NULL;
4363               DR_TYPE (res) = ARRAY_REF_TYPE;
4364               DR_SET_ACCESS_FNS (res, NULL);
4365               DR_BASE_OBJECT (res) = NULL;
4366               DR_IS_READ (res) = false;
4367               DR_BASE_ADDRESS (res) = NULL_TREE;
4368               DR_OFFSET (res) = NULL_TREE;
4369               DR_INIT (res) = NULL_TREE;
4370               DR_STEP (res) = NULL_TREE;
4371               DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
4372               DR_MEMTAG (res) = NULL_TREE;
4373               DR_PTR_INFO (res) = NULL;
4374               VEC_safe_push (data_reference_p, heap, *datarefs, res);
4375
4376               free (bbs);
4377               return chrec_dont_know;
4378             }
4379         }
4380     }
4381   free (bbs);
4382
4383   return NULL_TREE;
4384 }
4385
4386 /* Recursive helper function.  */
4387
4388 static bool
4389 find_loop_nest_1 (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4390 {
4391   /* Inner loops of the nest should not contain siblings.  Example:
4392      when there are two consecutive loops,
4393
4394      | loop_0
4395      |   loop_1
4396      |     A[{0, +, 1}_1]
4397      |   endloop_1
4398      |   loop_2
4399      |     A[{0, +, 1}_2]
4400      |   endloop_2
4401      | endloop_0
4402
4403      the dependence relation cannot be captured by the distance
4404      abstraction.  */
4405   if (loop->next)
4406     return false;
4407
4408   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4409   if (loop->inner)
4410     return find_loop_nest_1 (loop->inner, loop_nest);
4411   return true;
4412 }
4413
4414 /* Return false when the LOOP is not well nested.  Otherwise return
4415    true and insert in LOOP_NEST the loops of the nest.  LOOP_NEST will
4416    contain the loops from the outermost to the innermost, as they will
4417    appear in the classic distance vector.  */
4418
4419 static bool
4420 find_loop_nest (struct loop *loop, VEC (loop_p, heap) **loop_nest)
4421 {
4422   VEC_safe_push (loop_p, heap, *loop_nest, loop);
4423   if (loop->inner)
4424     return find_loop_nest_1 (loop->inner, loop_nest);
4425   return true;
4426 }
4427
4428 /* Given a loop nest LOOP, the following vectors are returned:
4429    DATAREFS is initialized to all the array elements contained in this loop,
4430    DEPENDENCE_RELATIONS contains the relations between the data references.
4431    Compute read-read and self relations if
4432    COMPUTE_SELF_AND_READ_READ_DEPENDENCES is TRUE.  */
4433
4434 void
4435 compute_data_dependences_for_loop (struct loop *loop,
4436                                    bool compute_self_and_read_read_dependences,
4437                                    VEC (data_reference_p, heap) **datarefs,
4438                                    VEC (ddr_p, heap) **dependence_relations)
4439 {
4440   struct loop *loop_nest = loop;
4441   VEC (loop_p, heap) *vloops = VEC_alloc (loop_p, heap, 3);
4442
4443   memset (&dependence_stats, 0, sizeof (dependence_stats));
4444
4445   /* If the loop nest is not well formed, or one of the data references
4446      is not computable, give up without spending time to compute other
4447      dependences.  */
4448   if (!loop_nest
4449       || !find_loop_nest (loop_nest, &vloops)
4450       || find_data_references_in_loop (loop, datarefs) == chrec_dont_know)
4451     {
4452       struct data_dependence_relation *ddr;
4453
4454       /* Insert a single relation into dependence_relations:
4455          chrec_dont_know.  */
4456       ddr = initialize_data_dependence_relation (NULL, NULL, vloops);
4457       VEC_safe_push (ddr_p, heap, *dependence_relations, ddr);
4458     }
4459   else
4460     compute_all_dependences (*datarefs, dependence_relations, vloops,
4461                              compute_self_and_read_read_dependences);
4462
4463   if (dump_file && (dump_flags & TDF_STATS))
4464     {
4465       fprintf (dump_file, "Dependence tester statistics:\n");
4466
4467       fprintf (dump_file, "Number of dependence tests: %d\n",
4468                dependence_stats.num_dependence_tests);
4469       fprintf (dump_file, "Number of dependence tests classified dependent: %d\n",
4470                dependence_stats.num_dependence_dependent);
4471       fprintf (dump_file, "Number of dependence tests classified independent: %d\n",
4472                dependence_stats.num_dependence_independent);
4473       fprintf (dump_file, "Number of undetermined dependence tests: %d\n",
4474                dependence_stats.num_dependence_undetermined);
4475
4476       fprintf (dump_file, "Number of subscript tests: %d\n",
4477                dependence_stats.num_subscript_tests);
4478       fprintf (dump_file, "Number of undetermined subscript tests: %d\n",
4479                dependence_stats.num_subscript_undetermined);
4480       fprintf (dump_file, "Number of same subscript function: %d\n",
4481                dependence_stats.num_same_subscript_function);
4482
4483       fprintf (dump_file, "Number of ziv tests: %d\n",
4484                dependence_stats.num_ziv);
4485       fprintf (dump_file, "Number of ziv tests returning dependent: %d\n",
4486                dependence_stats.num_ziv_dependent);
4487       fprintf (dump_file, "Number of ziv tests returning independent: %d\n",
4488                dependence_stats.num_ziv_independent);
4489       fprintf (dump_file, "Number of ziv tests unimplemented: %d\n",
4490                dependence_stats.num_ziv_unimplemented);
4491
4492       fprintf (dump_file, "Number of siv tests: %d\n",
4493                dependence_stats.num_siv);
4494       fprintf (dump_file, "Number of siv tests returning dependent: %d\n",
4495                dependence_stats.num_siv_dependent);
4496       fprintf (dump_file, "Number of siv tests returning independent: %d\n",
4497                dependence_stats.num_siv_independent);
4498       fprintf (dump_file, "Number of siv tests unimplemented: %d\n",
4499                dependence_stats.num_siv_unimplemented);
4500
4501       fprintf (dump_file, "Number of miv tests: %d\n",
4502                dependence_stats.num_miv);
4503       fprintf (dump_file, "Number of miv tests returning dependent: %d\n",
4504                dependence_stats.num_miv_dependent);
4505       fprintf (dump_file, "Number of miv tests returning independent: %d\n",
4506                dependence_stats.num_miv_independent);
4507       fprintf (dump_file, "Number of miv tests unimplemented: %d\n",
4508                dependence_stats.num_miv_unimplemented);
4509     }
4510 }
4511
4512 /* Entry point (for testing only).  Analyze all the data references
4513    and the dependence relations.
4514
4515    The data references are computed first.
4516
4517    A relation on these nodes is represented by a complete graph.  Some
4518    of the relations could be of no interest, thus the relations can be
4519    computed on demand.
4520
4521    In the following function we compute all the relations.  This is
4522    just a first implementation that is here for:
4523    - for showing how to ask for the dependence relations,
4524    - for the debugging the whole dependence graph,
4525    - for the dejagnu testcases and maintenance.
4526
4527    It is possible to ask only for a part of the graph, avoiding to
4528    compute the whole dependence graph.  The computed dependences are
4529    stored in a knowledge base (KB) such that later queries don't
4530    recompute the same information.  The implementation of this KB is
4531    transparent to the optimizer, and thus the KB can be changed with a
4532    more efficient implementation, or the KB could be disabled.  */
4533 #if 0
4534 static void
4535 analyze_all_data_dependences (struct loops *loops)
4536 {
4537   unsigned int i;
4538   int nb_data_refs = 10;
4539   VEC (data_reference_p, heap) *datarefs =
4540     VEC_alloc (data_reference_p, heap, nb_data_refs);
4541   VEC (ddr_p, heap) *dependence_relations =
4542     VEC_alloc (ddr_p, heap, nb_data_refs * nb_data_refs);
4543
4544   /* Compute DDs on the whole function.  */
4545   compute_data_dependences_for_loop (loops->parray[0], false,
4546                                      &datarefs, &dependence_relations);
4547
4548   if (dump_file)
4549     {
4550       dump_data_dependence_relations (dump_file, dependence_relations);
4551       fprintf (dump_file, "\n\n");
4552
4553       if (dump_flags & TDF_DETAILS)
4554         dump_dist_dir_vectors (dump_file, dependence_relations);
4555
4556       if (dump_flags & TDF_STATS)
4557         {
4558           unsigned nb_top_relations = 0;
4559           unsigned nb_bot_relations = 0;
4560           unsigned nb_basename_differ = 0;
4561           unsigned nb_chrec_relations = 0;
4562           struct data_dependence_relation *ddr;
4563
4564           for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4565             {
4566               if (chrec_contains_undetermined (DDR_ARE_DEPENDENT (ddr)))
4567                 nb_top_relations++;
4568
4569               else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
4570                 {
4571                   struct data_reference *a = DDR_A (ddr);
4572                   struct data_reference *b = DDR_B (ddr);
4573                   bool differ_p;
4574
4575                   if ((DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
4576                        && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
4577                       || (base_object_differ_p (a, b, &differ_p)
4578                           && differ_p))
4579                     nb_basename_differ++;
4580                   else
4581                     nb_bot_relations++;
4582                 }
4583
4584               else
4585                 nb_chrec_relations++;
4586             }
4587
4588           gather_stats_on_scev_database ();
4589         }
4590     }
4591
4592   free_dependence_relations (dependence_relations);
4593   free_data_refs (datarefs);
4594 }
4595 #endif
4596
4597 /* Free the memory used by a data dependence relation DDR.  */
4598
4599 void
4600 free_dependence_relation (struct data_dependence_relation *ddr)
4601 {
4602   if (ddr == NULL)
4603     return;
4604
4605   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_SUBSCRIPTS (ddr))
4606     free_subscripts (DDR_SUBSCRIPTS (ddr));
4607
4608   free (ddr);
4609 }
4610
4611 /* Free the memory used by the data dependence relations from
4612    DEPENDENCE_RELATIONS.  */
4613
4614 void
4615 free_dependence_relations (VEC (ddr_p, heap) *dependence_relations)
4616 {
4617   unsigned int i;
4618   struct data_dependence_relation *ddr;
4619   VEC (loop_p, heap) *loop_nest = NULL;
4620
4621   for (i = 0; VEC_iterate (ddr_p, dependence_relations, i, ddr); i++)
4622     {
4623       if (ddr == NULL)
4624         continue;
4625       if (loop_nest == NULL)
4626         loop_nest = DDR_LOOP_NEST (ddr);
4627       else
4628         gcc_assert (DDR_LOOP_NEST (ddr) == NULL
4629                     || DDR_LOOP_NEST (ddr) == loop_nest);
4630       free_dependence_relation (ddr);
4631     }
4632
4633   if (loop_nest)
4634     VEC_free (loop_p, heap, loop_nest);
4635   VEC_free (ddr_p, heap, dependence_relations);
4636 }
4637
4638 /* Free the memory used by the data references from DATAREFS.  */
4639
4640 void
4641 free_data_refs (VEC (data_reference_p, heap) *datarefs)
4642 {
4643   unsigned int i;
4644   struct data_reference *dr;
4645
4646   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
4647     free_data_ref (dr);
4648   VEC_free (data_reference_p, heap, datarefs);
4649 }
4650