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