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