gcc/tree-data-ref.c

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