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       access_fn = chrec_replace_initial_condition (access_fn, init_cond);
1961       access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
1962
1963       VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
1964     }
1965
1966   if (dump_file && (dump_flags & TDF_DETAILS))
1967     {
1968       struct ptr_info_def *pi = DR_PTR_INFO (dr);
1969
1970       fprintf (dump_file, "\nCreated dr for ");
1971       print_generic_expr (dump_file, memref, TDF_SLIM);
1972       fprintf (dump_file, "\n\tbase_address: ");
1973       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
1974       fprintf (dump_file, "\n\toffset from base address: ");
1975       print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
1976       fprintf (dump_file, "\n\tconstant offset from base address: ");
1977       print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
1978       fprintf (dump_file, "\n\tbase_object: ");
1979       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
1980       fprintf (dump_file, "\n\tstep: ");
1981       print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
1982       fprintf (dump_file, "B\n\tmisalignment from base: ");
1983       print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
1984       if (DR_OFFSET_MISALIGNMENT (dr))
1985         fprintf (dump_file, "B");
1986       if (DR_ALIGNED_TO (dr))
1987         {
1988           fprintf (dump_file, "\n\taligned to: ");
1989           print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
1990         }
1991       fprintf (dump_file, "\n\tmemtag: ");
1992       print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
1993       fprintf (dump_file, "\n");
1994       if (pi && pi->name_mem_tag)
1995         {
1996           fprintf (dump_file, "\n\tnametag: ");
1997           print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
1998           fprintf (dump_file, "\n");
1999         }
2000     }
2001   return dr;
2002 }
2003
2004
2005 /* Returns true when all the functions of a tree_vec CHREC are the
2006    same.  */
2007
2008 static bool
2009 all_chrecs_equal_p (tree chrec)
2010 {
2011   int j;
2012
2013   for (j = 0; j < TREE_VEC_LENGTH (chrec) - 1; j++)
2014     {
2015       tree chrec_j = TREE_VEC_ELT (chrec, j);
2016       tree chrec_j_1 = TREE_VEC_ELT (chrec, j + 1);
2017       if (!integer_zerop
2018           (chrec_fold_minus
2019            (integer_type_node, chrec_j, chrec_j_1)))
2020         return false;
2021     }
2022   return true;
2023 }
2024
2025 /* Determine for each subscript in the data dependence relation DDR
2026    the distance.  */
2027
2028 static void
2029 compute_subscript_distance (struct data_dependence_relation *ddr)
2030 {
2031   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2032     {
2033       unsigned int i;
2034
2035       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2036         {
2037           tree conflicts_a, conflicts_b, difference;
2038           struct subscript *subscript;
2039
2040           subscript = DDR_SUBSCRIPT (ddr, i);
2041           conflicts_a = SUB_CONFLICTS_IN_A (subscript);
2042           conflicts_b = SUB_CONFLICTS_IN_B (subscript);
2043
2044           if (TREE_CODE (conflicts_a) == TREE_VEC)
2045             {
2046               if (!all_chrecs_equal_p (conflicts_a))
2047                 {
2048                   SUB_DISTANCE (subscript) = chrec_dont_know;
2049                   return;
2050                 }
2051               else
2052                 conflicts_a = TREE_VEC_ELT (conflicts_a, 0);
2053             }
2054
2055           if (TREE_CODE (conflicts_b) == TREE_VEC)
2056             {
2057               if (!all_chrecs_equal_p (conflicts_b))
2058                 {
2059                   SUB_DISTANCE (subscript) = chrec_dont_know;
2060                   return;
2061                 }
2062               else
2063                 conflicts_b = TREE_VEC_ELT (conflicts_b, 0);
2064             }
2065
2066           difference = chrec_fold_minus
2067             (integer_type_node, conflicts_b, conflicts_a);
2068
2069           if (evolution_function_is_constant_p (difference))
2070             SUB_DISTANCE (subscript) = difference;
2071
2072           else
2073             SUB_DISTANCE (subscript) = chrec_dont_know;
2074         }
2075     }
2076 }
2077
2078 /* Initialize a data dependence relation between data accesses A and
2079    B.  NB_LOOPS is the number of loops surrounding the references: the
2080    size of the classic distance/direction vectors.  */
2081
2082 static struct data_dependence_relation *
2083 initialize_data_dependence_relation (struct data_reference *a,
2084                                      struct data_reference *b,
2085                                      VEC (loop_p, heap) *loop_nest)
2086 {
2087   struct data_dependence_relation *res;
2088   bool differ_p, known_dependence;
2089   unsigned int i;
2090
2091   res = XNEW (struct data_dependence_relation);
2092   DDR_A (res) = a;
2093   DDR_B (res) = b;
2094
2095   if (a == NULL || b == NULL)
2096     {
2097       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2098       return res;
2099     }
2100
2101   /* When A and B are arrays and their dimensions differ, we directly
2102      initialize the relation to "there is no dependence": chrec_known.  */
2103   if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2104       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2105     {
2106       DDR_ARE_DEPENDENT (res) = chrec_known;
2107       return res;
2108     }
2109
2110   if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2111     known_dependence = base_addr_differ_p (a, b, &differ_p);
2112   else
2113     known_dependence = base_object_differ_p (a, b, &differ_p);
2114
2115   if (!known_dependence)
2116     {
2117       /* Can't determine whether the data-refs access the same memory
2118          region.  */
2119       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2120       return res;
2121     }
2122
2123   if (differ_p)
2124     {
2125       DDR_ARE_DEPENDENT (res) = chrec_known;
2126       return res;
2127     }
2128
2129   DDR_AFFINE_P (res) = true;
2130   DDR_ARE_DEPENDENT (res) = NULL_TREE;
2131   DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2132   DDR_LOOP_NEST (res) = loop_nest;
2133   DDR_DIR_VECTS (res) = NULL;
2134   DDR_DIST_VECTS (res) = NULL;
2135
2136   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2137     {
2138       struct subscript *subscript;
2139
2140       subscript = XNEW (struct subscript);
2141       SUB_CONFLICTS_IN_A (subscript) = chrec_dont_know;
2142       SUB_CONFLICTS_IN_B (subscript) = chrec_dont_know;
2143       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2144       SUB_DISTANCE (subscript) = chrec_dont_know;
2145       VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2146     }
2147
2148   return res;
2149 }
2150
2151 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2152    description.  */
2153
2154 static inline void
2155 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2156                         tree chrec)
2157 {
2158   if (dump_file && (dump_flags & TDF_DETAILS))
2159     {
2160       fprintf (dump_file, "(dependence classified: ");
2161       print_generic_expr (dump_file, chrec, 0);
2162       fprintf (dump_file, ")\n");
2163     }
2164
2165   DDR_ARE_DEPENDENT (ddr) = chrec;
2166   VEC_free (subscript_p, heap, DDR_SUBSCRIPTS (ddr));
2167 }
2168
2169 /* The dependence relation DDR cannot be represented by a distance
2170    vector.  */
2171
2172 static inline void
2173 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2174 {
2175   if (dump_file && (dump_flags & TDF_DETAILS))
2176     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2177
2178   DDR_AFFINE_P (ddr) = false;
2179 }
2180
2181 \f
2182
2183 /* This section contains the classic Banerjee tests.  */
2184
2185 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2186    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
2187
2188 static inline bool
2189 ziv_subscript_p (tree chrec_a,
2190                  tree chrec_b)
2191 {
2192   return (evolution_function_is_constant_p (chrec_a)
2193           && evolution_function_is_constant_p (chrec_b));
2194 }
2195
2196 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2197    variable, i.e., if the SIV (Single Index Variable) test is true.  */
2198
2199 static bool
2200 siv_subscript_p (tree chrec_a,
2201                  tree chrec_b)
2202 {
2203   if ((evolution_function_is_constant_p (chrec_a)
2204        && evolution_function_is_univariate_p (chrec_b))
2205       || (evolution_function_is_constant_p (chrec_b)
2206           && evolution_function_is_univariate_p (chrec_a)))
2207     return true;
2208
2209   if (evolution_function_is_univariate_p (chrec_a)
2210       && evolution_function_is_univariate_p (chrec_b))
2211     {
2212       switch (TREE_CODE (chrec_a))
2213         {
2214         case POLYNOMIAL_CHREC:
2215           switch (TREE_CODE (chrec_b))
2216             {
2217             case POLYNOMIAL_CHREC:
2218               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2219                 return false;
2220
2221             default:
2222               return true;
2223             }
2224
2225         default:
2226           return true;
2227         }
2228     }
2229
2230   return false;
2231 }
2232
2233 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
2234    *OVERLAPS_B are initialized to the functions that describe the
2235    relation between the elements accessed twice by CHREC_A and
2236    CHREC_B.  For k >= 0, the following property is verified:
2237
2238    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2239
2240 static void
2241 analyze_ziv_subscript (tree chrec_a,
2242                        tree chrec_b,
2243                        tree *overlaps_a,
2244                        tree *overlaps_b,
2245                        tree *last_conflicts)
2246 {
2247   tree difference;
2248   dependence_stats.num_ziv++;
2249
2250   if (dump_file && (dump_flags & TDF_DETAILS))
2251     fprintf (dump_file, "(analyze_ziv_subscript \n");
2252
2253   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2254
2255   switch (TREE_CODE (difference))
2256     {
2257     case INTEGER_CST:
2258       if (integer_zerop (difference))
2259         {
2260           /* The difference is equal to zero: the accessed index
2261              overlaps for each iteration in the loop.  */
2262           *overlaps_a = integer_zero_node;
2263           *overlaps_b = integer_zero_node;
2264           *last_conflicts = chrec_dont_know;
2265           dependence_stats.num_ziv_dependent++;
2266         }
2267       else
2268         {
2269           /* The accesses do not overlap.  */
2270           *overlaps_a = chrec_known;
2271           *overlaps_b = chrec_known;
2272           *last_conflicts = integer_zero_node;
2273           dependence_stats.num_ziv_independent++;
2274         }
2275       break;
2276
2277     default:
2278       /* We're not sure whether the indexes overlap.  For the moment,
2279          conservatively answer "don't know".  */
2280       if (dump_file && (dump_flags & TDF_DETAILS))
2281         fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2282
2283       *overlaps_a = chrec_dont_know;
2284       *overlaps_b = chrec_dont_know;
2285       *last_conflicts = chrec_dont_know;
2286       dependence_stats.num_ziv_unimplemented++;
2287       break;
2288     }
2289
2290   if (dump_file && (dump_flags & TDF_DETAILS))
2291     fprintf (dump_file, ")\n");
2292 }
2293
2294 /* Get the real or estimated number of iterations for LOOPNUM, whichever is
2295    available. Return the number of iterations as a tree, or NULL_TREE if
2296    we don't know.  */
2297
2298 static tree
2299 get_number_of_iters_for_loop (int loopnum)
2300 {
2301   tree numiter = number_of_iterations_in_loop (current_loops->parray[loopnum]);
2302
2303   if (TREE_CODE (numiter) != INTEGER_CST)
2304     numiter = current_loops->parray[loopnum]->estimated_nb_iterations;
2305   if (chrec_contains_undetermined (numiter))
2306     return NULL_TREE;
2307   return numiter;
2308 }
2309
2310 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2311    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
2312    *OVERLAPS_B are initialized to the functions that describe the
2313    relation between the elements accessed twice by CHREC_A and
2314    CHREC_B.  For k >= 0, the following property is verified:
2315
2316    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2317
2318 static void
2319 analyze_siv_subscript_cst_affine (tree chrec_a,
2320                                   tree chrec_b,
2321                                   tree *overlaps_a,
2322                                   tree *overlaps_b,
2323                                   tree *last_conflicts)
2324 {
2325   bool value0, value1, value2;
2326   tree difference = chrec_fold_minus
2327     (integer_type_node, CHREC_LEFT (chrec_b), chrec_a);
2328
2329   if (!chrec_is_positive (initial_condition (difference), &value0))
2330     {
2331       if (dump_file && (dump_flags & TDF_DETAILS))
2332         fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2333
2334       dependence_stats.num_siv_unimplemented++;
2335       *overlaps_a = chrec_dont_know;
2336       *overlaps_b = chrec_dont_know;
2337       *last_conflicts = chrec_dont_know;
2338       return;
2339     }
2340   else
2341     {
2342       if (value0 == false)
2343         {
2344           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2345             {
2346               if (dump_file && (dump_flags & TDF_DETAILS))
2347                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2348
2349               *overlaps_a = chrec_dont_know;
2350               *overlaps_b = chrec_dont_know;
2351               *last_conflicts = chrec_dont_know;
2352               dependence_stats.num_siv_unimplemented++;
2353               return;
2354             }
2355           else
2356             {
2357               if (value1 == true)
2358                 {
2359                   /* Example:
2360                      chrec_a = 12
2361                      chrec_b = {10, +, 1}
2362                   */
2363
2364                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2365                     {
2366                       tree numiter;
2367                       int loopnum = CHREC_VARIABLE (chrec_b);
2368
2369                       *overlaps_a = integer_zero_node;
2370                       *overlaps_b = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2371                                                  fold_build1 (ABS_EXPR,
2372                                                               integer_type_node,
2373                                                               difference),
2374                                                  CHREC_RIGHT (chrec_b));
2375                       *last_conflicts = integer_one_node;
2376
2377
2378                       /* Perform weak-zero siv test to see if overlap is
2379                          outside the loop bounds.  */
2380                       numiter = get_number_of_iters_for_loop (loopnum);
2381
2382                       if (numiter != NULL_TREE
2383                           && TREE_CODE (*overlaps_b) == INTEGER_CST
2384                           && tree_int_cst_lt (numiter, *overlaps_b))
2385                         {
2386                           *overlaps_a = chrec_known;
2387                           *overlaps_b = chrec_known;
2388                           *last_conflicts = integer_zero_node;
2389                           dependence_stats.num_siv_independent++;
2390                           return;
2391                         }
2392                       dependence_stats.num_siv_dependent++;
2393                       return;
2394                     }
2395
2396                   /* When the step does not divide the difference, there are
2397                      no overlaps.  */
2398                   else
2399                     {
2400                       *overlaps_a = chrec_known;
2401                       *overlaps_b = chrec_known;
2402                       *last_conflicts = integer_zero_node;
2403                       dependence_stats.num_siv_independent++;
2404                       return;
2405                     }
2406                 }
2407
2408               else
2409                 {
2410                   /* Example:
2411                      chrec_a = 12
2412                      chrec_b = {10, +, -1}
2413
2414                      In this case, chrec_a will not overlap with chrec_b.  */
2415                   *overlaps_a = chrec_known;
2416                   *overlaps_b = chrec_known;
2417                   *last_conflicts = integer_zero_node;
2418                   dependence_stats.num_siv_independent++;
2419                   return;
2420                 }
2421             }
2422         }
2423       else
2424         {
2425           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2426             {
2427               if (dump_file && (dump_flags & TDF_DETAILS))
2428                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2429
2430               *overlaps_a = chrec_dont_know;
2431               *overlaps_b = chrec_dont_know;
2432               *last_conflicts = chrec_dont_know;
2433               dependence_stats.num_siv_unimplemented++;
2434               return;
2435             }
2436           else
2437             {
2438               if (value2 == false)
2439                 {
2440                   /* Example:
2441                      chrec_a = 3
2442                      chrec_b = {10, +, -1}
2443                   */
2444                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2445                     {
2446                       tree numiter;
2447                       int loopnum = CHREC_VARIABLE (chrec_b);
2448
2449                       *overlaps_a = integer_zero_node;
2450                       *overlaps_b = fold_build2 (EXACT_DIV_EXPR,
2451                                                  integer_type_node, difference,
2452                                                  CHREC_RIGHT (chrec_b));
2453                       *last_conflicts = integer_one_node;
2454
2455                       /* Perform weak-zero siv test to see if overlap is
2456                          outside the loop bounds.  */
2457                       numiter = get_number_of_iters_for_loop (loopnum);
2458
2459                       if (numiter != NULL_TREE
2460                           && TREE_CODE (*overlaps_b) == INTEGER_CST
2461                           && tree_int_cst_lt (numiter, *overlaps_b))
2462                         {
2463                           *overlaps_a = chrec_known;
2464                           *overlaps_b = chrec_known;
2465                           *last_conflicts = integer_zero_node;
2466                           dependence_stats.num_siv_independent++;
2467                           return;
2468                         }
2469                       dependence_stats.num_siv_dependent++;
2470                       return;
2471                     }
2472
2473                   /* When the step does not divide the difference, there
2474                      are no overlaps.  */
2475                   else
2476                     {
2477                       *overlaps_a = chrec_known;
2478                       *overlaps_b = chrec_known;
2479                       *last_conflicts = integer_zero_node;
2480                       dependence_stats.num_siv_independent++;
2481                       return;
2482                     }
2483                 }
2484               else
2485                 {
2486                   /* Example:
2487                      chrec_a = 3
2488                      chrec_b = {4, +, 1}
2489
2490                      In this case, chrec_a will not overlap with chrec_b.  */
2491                   *overlaps_a = chrec_known;
2492                   *overlaps_b = chrec_known;
2493                   *last_conflicts = integer_zero_node;
2494                   dependence_stats.num_siv_independent++;
2495                   return;
2496                 }
2497             }
2498         }
2499     }
2500 }
2501
2502 /* Helper recursive function for initializing the matrix A.  Returns
2503    the initial value of CHREC.  */
2504
2505 static int
2506 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2507 {
2508   gcc_assert (chrec);
2509
2510   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2511     return int_cst_value (chrec);
2512
2513   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2514   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2515 }
2516
2517 #define FLOOR_DIV(x,y) ((x) / (y))
2518
2519 /* Solves the special case of the Diophantine equation:
2520    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2521
2522    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
2523    number of iterations that loops X and Y run.  The overlaps will be
2524    constructed as evolutions in dimension DIM.  */
2525
2526 static void
2527 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2528                                          tree *overlaps_a, tree *overlaps_b,
2529                                          tree *last_conflicts, int dim)
2530 {
2531   if (((step_a > 0 && step_b > 0)
2532        || (step_a < 0 && step_b < 0)))
2533     {
2534       int step_overlaps_a, step_overlaps_b;
2535       int gcd_steps_a_b, last_conflict, tau2;
2536
2537       gcd_steps_a_b = gcd (step_a, step_b);
2538       step_overlaps_a = step_b / gcd_steps_a_b;
2539       step_overlaps_b = step_a / gcd_steps_a_b;
2540
2541       tau2 = FLOOR_DIV (niter, step_overlaps_a);
2542       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2543       last_conflict = tau2;
2544
2545       *overlaps_a = build_polynomial_chrec
2546         (dim, integer_zero_node,
2547          build_int_cst (NULL_TREE, step_overlaps_a));
2548       *overlaps_b = build_polynomial_chrec
2549         (dim, integer_zero_node,
2550          build_int_cst (NULL_TREE, step_overlaps_b));
2551       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2552     }
2553
2554   else
2555     {
2556       *overlaps_a = integer_zero_node;
2557       *overlaps_b = integer_zero_node;
2558       *last_conflicts = integer_zero_node;
2559     }
2560 }
2561
2562
2563 /* Solves the special case of a Diophantine equation where CHREC_A is
2564    an affine bivariate function, and CHREC_B is an affine univariate
2565    function.  For example,
2566
2567    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2568
2569    has the following overlapping functions:
2570
2571    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2572    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2573    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2574
2575    FORNOW: This is a specialized implementation for a case occurring in
2576    a common benchmark.  Implement the general algorithm.  */
2577
2578 static void
2579 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2580                                       tree *overlaps_a, tree *overlaps_b,
2581                                       tree *last_conflicts)
2582 {
2583   bool xz_p, yz_p, xyz_p;
2584   int step_x, step_y, step_z;
2585   int niter_x, niter_y, niter_z, niter;
2586   tree numiter_x, numiter_y, numiter_z;
2587   tree overlaps_a_xz, overlaps_b_xz, last_conflicts_xz;
2588   tree overlaps_a_yz, overlaps_b_yz, last_conflicts_yz;
2589   tree overlaps_a_xyz, overlaps_b_xyz, last_conflicts_xyz;
2590
2591   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2592   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2593   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2594
2595   numiter_x = get_number_of_iters_for_loop (CHREC_VARIABLE (CHREC_LEFT (chrec_a)));
2596   numiter_y = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2597   numiter_z = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2598
2599   if (numiter_x == NULL_TREE || numiter_y == NULL_TREE
2600       || numiter_z == NULL_TREE)
2601     {
2602       if (dump_file && (dump_flags & TDF_DETAILS))
2603         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2604
2605       *overlaps_a = chrec_dont_know;
2606       *overlaps_b = chrec_dont_know;
2607       *last_conflicts = chrec_dont_know;
2608       return;
2609     }
2610
2611   niter_x = int_cst_value (numiter_x);
2612   niter_y = int_cst_value (numiter_y);
2613   niter_z = int_cst_value (numiter_z);
2614
2615   niter = MIN (niter_x, niter_z);
2616   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2617                                            &overlaps_a_xz,
2618                                            &overlaps_b_xz,
2619                                            &last_conflicts_xz, 1);
2620   niter = MIN (niter_y, niter_z);
2621   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2622                                            &overlaps_a_yz,
2623                                            &overlaps_b_yz,
2624                                            &last_conflicts_yz, 2);
2625   niter = MIN (niter_x, niter_z);
2626   niter = MIN (niter_y, niter);
2627   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2628                                            &overlaps_a_xyz,
2629                                            &overlaps_b_xyz,
2630                                            &last_conflicts_xyz, 3);
2631
2632   xz_p = !integer_zerop (last_conflicts_xz);
2633   yz_p = !integer_zerop (last_conflicts_yz);
2634   xyz_p = !integer_zerop (last_conflicts_xyz);
2635
2636   if (xz_p || yz_p || xyz_p)
2637     {
2638       *overlaps_a = make_tree_vec (2);
2639       TREE_VEC_ELT (*overlaps_a, 0) = integer_zero_node;
2640       TREE_VEC_ELT (*overlaps_a, 1) = integer_zero_node;
2641       *overlaps_b = integer_zero_node;
2642       if (xz_p)
2643         {
2644           TREE_VEC_ELT (*overlaps_a, 0) =
2645             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2646                              overlaps_a_xz);
2647           *overlaps_b =
2648             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xz);
2649           *last_conflicts = last_conflicts_xz;
2650         }
2651       if (yz_p)
2652         {
2653           TREE_VEC_ELT (*overlaps_a, 1) =
2654             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2655                              overlaps_a_yz);
2656           *overlaps_b =
2657             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_yz);
2658           *last_conflicts = last_conflicts_yz;
2659         }
2660       if (xyz_p)
2661         {
2662           TREE_VEC_ELT (*overlaps_a, 0) =
2663             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 0),
2664                              overlaps_a_xyz);
2665           TREE_VEC_ELT (*overlaps_a, 1) =
2666             chrec_fold_plus (integer_type_node, TREE_VEC_ELT (*overlaps_a, 1),
2667                              overlaps_a_xyz);
2668           *overlaps_b =
2669             chrec_fold_plus (integer_type_node, *overlaps_b, overlaps_b_xyz);
2670           *last_conflicts = last_conflicts_xyz;
2671         }
2672     }
2673   else
2674     {
2675       *overlaps_a = integer_zero_node;
2676       *overlaps_b = integer_zero_node;
2677       *last_conflicts = integer_zero_node;
2678     }
2679 }
2680
2681 /* Determines the overlapping elements due to accesses CHREC_A and
2682    CHREC_B, that are affine functions.  This function cannot handle
2683    symbolic evolution functions, ie. when initial conditions are
2684    parameters, because it uses lambda matrices of integers.  */
2685
2686 static void
2687 analyze_subscript_affine_affine (tree chrec_a,
2688                                  tree chrec_b,
2689                                  tree *overlaps_a,
2690                                  tree *overlaps_b,
2691                                  tree *last_conflicts)
2692 {
2693   unsigned nb_vars_a, nb_vars_b, dim;
2694   int init_a, init_b, gamma, gcd_alpha_beta;
2695   int tau1, tau2;
2696   lambda_matrix A, U, S;
2697   tree difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2698
2699   if (integer_zerop (difference))
2700     {
2701       /* The difference is equal to zero: the accessed index
2702          overlaps for each iteration in the loop.  */
2703       *overlaps_a = integer_zero_node;
2704       *overlaps_b = integer_zero_node;
2705       *last_conflicts = chrec_dont_know;
2706       return;
2707     }
2708   if (dump_file && (dump_flags & TDF_DETAILS))
2709     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
2710
2711   /* For determining the initial intersection, we have to solve a
2712      Diophantine equation.  This is the most time consuming part.
2713
2714      For answering to the question: "Is there a dependence?" we have
2715      to prove that there exists a solution to the Diophantine
2716      equation, and that the solution is in the iteration domain,
2717      i.e. the solution is positive or zero, and that the solution
2718      happens before the upper bound loop.nb_iterations.  Otherwise
2719      there is no dependence.  This function outputs a description of
2720      the iterations that hold the intersections.  */
2721
2722
2723   nb_vars_a = nb_vars_in_chrec (chrec_a);
2724   nb_vars_b = nb_vars_in_chrec (chrec_b);
2725
2726   dim = nb_vars_a + nb_vars_b;
2727   U = lambda_matrix_new (dim, dim);
2728   A = lambda_matrix_new (dim, 1);
2729   S = lambda_matrix_new (dim, 1);
2730
2731   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
2732   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
2733   gamma = init_b - init_a;
2734
2735   /* Don't do all the hard work of solving the Diophantine equation
2736      when we already know the solution: for example,
2737      | {3, +, 1}_1
2738      | {3, +, 4}_2
2739      | gamma = 3 - 3 = 0.
2740      Then the first overlap occurs during the first iterations:
2741      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
2742   */
2743   if (gamma == 0)
2744     {
2745       if (nb_vars_a == 1 && nb_vars_b == 1)
2746         {
2747           int step_a, step_b;
2748           int niter, niter_a, niter_b;
2749           tree numiter_a, numiter_b;
2750
2751           numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2752           numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2753           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2754             {
2755               if (dump_file && (dump_flags & TDF_DETAILS))
2756                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2757               *overlaps_a = chrec_dont_know;
2758               *overlaps_b = chrec_dont_know;
2759               *last_conflicts = chrec_dont_know;
2760               goto end_analyze_subs_aa;
2761             }
2762
2763           niter_a = int_cst_value (numiter_a);
2764           niter_b = int_cst_value (numiter_b);
2765           niter = MIN (niter_a, niter_b);
2766
2767           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
2768           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
2769
2770           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
2771                                                    overlaps_a, overlaps_b,
2772                                                    last_conflicts, 1);
2773         }
2774
2775       else if (nb_vars_a == 2 && nb_vars_b == 1)
2776         compute_overlap_steps_for_affine_1_2
2777           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
2778
2779       else if (nb_vars_a == 1 && nb_vars_b == 2)
2780         compute_overlap_steps_for_affine_1_2
2781           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
2782
2783       else
2784         {
2785           if (dump_file && (dump_flags & TDF_DETAILS))
2786             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
2787           *overlaps_a = chrec_dont_know;
2788           *overlaps_b = chrec_dont_know;
2789           *last_conflicts = chrec_dont_know;
2790         }
2791       goto end_analyze_subs_aa;
2792     }
2793
2794   /* U.A = S */
2795   lambda_matrix_right_hermite (A, dim, 1, S, U);
2796
2797   if (S[0][0] < 0)
2798     {
2799       S[0][0] *= -1;
2800       lambda_matrix_row_negate (U, dim, 0);
2801     }
2802   gcd_alpha_beta = S[0][0];
2803
2804   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
2805      but that is a quite strange case.  Instead of ICEing, answer
2806      don't know.  */
2807   if (gcd_alpha_beta == 0)
2808     {
2809       *overlaps_a = chrec_dont_know;
2810       *overlaps_b = chrec_dont_know;
2811       *last_conflicts = chrec_dont_know;
2812       goto end_analyze_subs_aa;
2813     }
2814
2815   /* The classic "gcd-test".  */
2816   if (!int_divides_p (gcd_alpha_beta, gamma))
2817     {
2818       /* The "gcd-test" has determined that there is no integer
2819          solution, i.e. there is no dependence.  */
2820       *overlaps_a = chrec_known;
2821       *overlaps_b = chrec_known;
2822       *last_conflicts = integer_zero_node;
2823     }
2824
2825   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
2826   else if (nb_vars_a == 1 && nb_vars_b == 1)
2827     {
2828       /* Both functions should have the same evolution sign.  */
2829       if (((A[0][0] > 0 && -A[1][0] > 0)
2830            || (A[0][0] < 0 && -A[1][0] < 0)))
2831         {
2832           /* The solutions are given by:
2833              |
2834              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
2835              |                           [u21 u22]    [y0]
2836
2837              For a given integer t.  Using the following variables,
2838
2839              | i0 = u11 * gamma / gcd_alpha_beta
2840              | j0 = u12 * gamma / gcd_alpha_beta
2841              | i1 = u21
2842              | j1 = u22
2843
2844              the solutions are:
2845
2846              | x0 = i0 + i1 * t,
2847              | y0 = j0 + j1 * t.  */
2848
2849           int i0, j0, i1, j1;
2850
2851           /* X0 and Y0 are the first iterations for which there is a
2852              dependence.  X0, Y0 are two solutions of the Diophantine
2853              equation: chrec_a (X0) = chrec_b (Y0).  */
2854           int x0, y0;
2855           int niter, niter_a, niter_b;
2856           tree numiter_a, numiter_b;
2857
2858           numiter_a = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
2859           numiter_b = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_b));
2860
2861           if (numiter_a == NULL_TREE || numiter_b == NULL_TREE)
2862             {
2863               if (dump_file && (dump_flags & TDF_DETAILS))
2864                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
2865               *overlaps_a = chrec_dont_know;
2866               *overlaps_b = chrec_dont_know;
2867               *last_conflicts = chrec_dont_know;
2868               goto end_analyze_subs_aa;
2869             }
2870
2871           niter_a = int_cst_value (numiter_a);
2872           niter_b = int_cst_value (numiter_b);
2873           niter = MIN (niter_a, niter_b);
2874
2875           i0 = U[0][0] * gamma / gcd_alpha_beta;
2876           j0 = U[0][1] * gamma / gcd_alpha_beta;
2877           i1 = U[1][0];
2878           j1 = U[1][1];
2879
2880           if ((i1 == 0 && i0 < 0)
2881               || (j1 == 0 && j0 < 0))
2882             {
2883               /* There is no solution.
2884                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
2885                  falls in here, but for the moment we don't look at the
2886                  upper bound of the iteration domain.  */
2887               *overlaps_a = chrec_known;
2888               *overlaps_b = chrec_known;
2889               *last_conflicts = integer_zero_node;
2890             }
2891
2892           else
2893             {
2894               if (i1 > 0)
2895                 {
2896                   tau1 = CEIL (-i0, i1);
2897                   tau2 = FLOOR_DIV (niter - i0, i1);
2898
2899                   if (j1 > 0)
2900                     {
2901                       int last_conflict, min_multiple;
2902                       tau1 = MAX (tau1, CEIL (-j0, j1));
2903                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
2904
2905                       x0 = i1 * tau1 + i0;
2906                       y0 = j1 * tau1 + j0;
2907
2908                       /* At this point (x0, y0) is one of the
2909                          solutions to the Diophantine equation.  The
2910                          next step has to compute the smallest
2911                          positive solution: the first conflicts.  */
2912                       min_multiple = MIN (x0 / i1, y0 / j1);
2913                       x0 -= i1 * min_multiple;
2914                       y0 -= j1 * min_multiple;
2915
2916                       tau1 = (x0 - i0)/i1;
2917                       last_conflict = tau2 - tau1;
2918
2919                       /* If the overlap occurs outside of the bounds of the
2920                          loop, there is no dependence.  */
2921                       if (x0 > niter || y0  > niter)
2922                         {
2923                           *overlaps_a = chrec_known;
2924                           *overlaps_b = chrec_known;
2925                           *last_conflicts = integer_zero_node;
2926                         }
2927                       else
2928                         {
2929                           *overlaps_a = build_polynomial_chrec
2930                             (1,
2931                              build_int_cst (NULL_TREE, x0),
2932                              build_int_cst (NULL_TREE, i1));
2933                           *overlaps_b = build_polynomial_chrec
2934                             (1,
2935                              build_int_cst (NULL_TREE, y0),
2936                              build_int_cst (NULL_TREE, j1));
2937                           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2938                         }
2939                     }
2940                   else
2941                     {
2942                       /* FIXME: For the moment, the upper bound of the
2943                          iteration domain for j is not checked.  */
2944                       if (dump_file && (dump_flags & TDF_DETAILS))
2945                         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2946                       *overlaps_a = chrec_dont_know;
2947                       *overlaps_b = chrec_dont_know;
2948                       *last_conflicts = chrec_dont_know;
2949                     }
2950                 }
2951
2952               else
2953                 {
2954                   /* FIXME: For the moment, the upper bound of the
2955                      iteration domain for i is not checked.  */
2956                   if (dump_file && (dump_flags & TDF_DETAILS))
2957                     fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2958                   *overlaps_a = chrec_dont_know;
2959                   *overlaps_b = chrec_dont_know;
2960                   *last_conflicts = chrec_dont_know;
2961                 }
2962             }
2963         }
2964       else
2965         {
2966           if (dump_file && (dump_flags & TDF_DETAILS))
2967             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2968           *overlaps_a = chrec_dont_know;
2969           *overlaps_b = chrec_dont_know;
2970           *last_conflicts = chrec_dont_know;
2971         }
2972     }
2973
2974   else
2975     {
2976       if (dump_file && (dump_flags & TDF_DETAILS))
2977         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
2978       *overlaps_a = chrec_dont_know;
2979       *overlaps_b = chrec_dont_know;
2980       *last_conflicts = chrec_dont_know;
2981     }
2982
2983 end_analyze_subs_aa:
2984   if (dump_file && (dump_flags & TDF_DETAILS))
2985     {
2986       fprintf (dump_file, "  (overlaps_a = ");
2987       print_generic_expr (dump_file, *overlaps_a, 0);
2988       fprintf (dump_file, ")\n  (overlaps_b = ");
2989       print_generic_expr (dump_file, *overlaps_b, 0);
2990       fprintf (dump_file, ")\n");
2991       fprintf (dump_file, ")\n");
2992     }
2993 }
2994
2995 /* Returns true when analyze_subscript_affine_affine can be used for
2996    determining the dependence relation between chrec_a and chrec_b,
2997    that contain symbols.  This function modifies chrec_a and chrec_b
2998    such that the analysis result is the same, and such that they don't
2999    contain symbols, and then can safely be passed to the analyzer.
3000
3001    Example: The analysis of the following tuples of evolutions produce
3002    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3003    vs. {0, +, 1}_1
3004
3005    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3006    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3007 */
3008
3009 static bool
3010 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3011 {
3012   tree diff;
3013
3014   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3015       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3016     /* FIXME: For the moment not handled.  Might be refined later.  */
3017     return false;
3018
3019   diff = chrec_fold_minus (chrec_type (*chrec_a), CHREC_LEFT (*chrec_a),
3020                            CHREC_LEFT (*chrec_b));
3021   if (!evolution_function_is_constant_p (diff))
3022     return false;
3023
3024   if (dump_file && (dump_flags & TDF_DETAILS))
3025     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3026
3027   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3028                                      diff, CHREC_RIGHT (*chrec_a));
3029   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3030                                      integer_zero_node,
3031                                      CHREC_RIGHT (*chrec_b));
3032   return true;
3033 }
3034
3035 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
3036    *OVERLAPS_B are initialized to the functions that describe the
3037    relation between the elements accessed twice by CHREC_A and
3038    CHREC_B.  For k >= 0, the following property is verified:
3039
3040    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
3041
3042 static void
3043 analyze_siv_subscript (tree chrec_a,
3044                        tree chrec_b,
3045                        tree *overlaps_a,
3046                        tree *overlaps_b,
3047                        tree *last_conflicts)
3048 {
3049   dependence_stats.num_siv++;
3050
3051   if (dump_file && (dump_flags & TDF_DETAILS))
3052     fprintf (dump_file, "(analyze_siv_subscript \n");
3053
3054   if (evolution_function_is_constant_p (chrec_a)
3055       && evolution_function_is_affine_p (chrec_b))
3056     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3057                                       overlaps_a, overlaps_b, last_conflicts);
3058
3059   else if (evolution_function_is_affine_p (chrec_a)
3060            && evolution_function_is_constant_p (chrec_b))
3061     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3062                                       overlaps_b, overlaps_a, last_conflicts);
3063
3064   else if (evolution_function_is_affine_p (chrec_a)
3065            && evolution_function_is_affine_p (chrec_b))
3066     {
3067       if (!chrec_contains_symbols (chrec_a)
3068           && !chrec_contains_symbols (chrec_b))
3069         {
3070           analyze_subscript_affine_affine (chrec_a, chrec_b,
3071                                            overlaps_a, overlaps_b,
3072                                            last_conflicts);
3073
3074           if (*overlaps_a == chrec_dont_know
3075               || *overlaps_b == chrec_dont_know)
3076             dependence_stats.num_siv_unimplemented++;
3077           else if (*overlaps_a == chrec_known
3078                    || *overlaps_b == chrec_known)
3079             dependence_stats.num_siv_independent++;
3080           else
3081             dependence_stats.num_siv_dependent++;
3082         }
3083       else if (can_use_analyze_subscript_affine_affine (&chrec_a,
3084                                                         &chrec_b))
3085         {
3086           analyze_subscript_affine_affine (chrec_a, chrec_b,
3087                                            overlaps_a, overlaps_b,
3088                                            last_conflicts);
3089           /* FIXME: The number of iterations is a symbolic expression.
3090              Compute it properly.  */
3091           *last_conflicts = chrec_dont_know;
3092
3093           if (*overlaps_a == chrec_dont_know
3094               || *overlaps_b == chrec_dont_know)
3095             dependence_stats.num_siv_unimplemented++;
3096           else if (*overlaps_a == chrec_known
3097                    || *overlaps_b == chrec_known)
3098             dependence_stats.num_siv_independent++;
3099           else
3100             dependence_stats.num_siv_dependent++;
3101         }
3102       else
3103         goto siv_subscript_dontknow;
3104     }
3105
3106   else
3107     {
3108     siv_subscript_dontknow:;
3109       if (dump_file && (dump_flags & TDF_DETAILS))
3110         fprintf (dump_file, "siv test failed: unimplemented.\n");
3111       *overlaps_a = chrec_dont_know;
3112       *overlaps_b = chrec_dont_know;
3113       *last_conflicts = chrec_dont_know;
3114       dependence_stats.num_siv_unimplemented++;
3115     }
3116
3117   if (dump_file && (dump_flags & TDF_DETAILS))
3118     fprintf (dump_file, ")\n");
3119 }
3120
3121 /* Return true when the property can be computed.  RES should contain
3122    true when calling the first time this function, then it is set to
3123    false when one of the evolution steps of an affine CHREC does not
3124    divide the constant CST.  */
3125
3126 static bool
3127 chrec_steps_divide_constant_p (tree chrec,
3128                                tree cst,
3129                                bool *res)
3130 {
3131   switch (TREE_CODE (chrec))
3132     {
3133     case POLYNOMIAL_CHREC:
3134       if (evolution_function_is_constant_p (CHREC_RIGHT (chrec)))
3135         {
3136           if (tree_fold_divides_p (CHREC_RIGHT (chrec), cst))
3137             /* Keep RES to true, and iterate on other dimensions.  */
3138             return chrec_steps_divide_constant_p (CHREC_LEFT (chrec), cst, res);
3139
3140           *res = false;
3141           return true;
3142         }
3143       else
3144         /* When the step is a parameter the result is undetermined.  */
3145         return false;
3146
3147     default:
3148       /* On the initial condition, return true.  */
3149       return true;
3150     }
3151 }
3152
3153 /* Analyze a MIV (Multiple Index Variable) subscript.  *OVERLAPS_A and
3154    *OVERLAPS_B are initialized to the functions that describe the
3155    relation between the elements accessed twice by CHREC_A and
3156    CHREC_B.  For k >= 0, the following property is verified:
3157
3158    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
3159
3160 static void
3161 analyze_miv_subscript (tree chrec_a,
3162                        tree chrec_b,
3163                        tree *overlaps_a,
3164                        tree *overlaps_b,
3165                        tree *last_conflicts)
3166 {
3167   /* FIXME:  This is a MIV subscript, not yet handled.
3168      Example: (A[{1, +, 1}_1] vs. A[{1, +, 1}_2]) that comes from
3169      (A[i] vs. A[j]).
3170
3171      In the SIV test we had to solve a Diophantine equation with two
3172      variables.  In the MIV case we have to solve a Diophantine
3173      equation with 2*n variables (if the subscript uses n IVs).
3174   */
3175   bool divide_p = true;
3176   tree difference;
3177   dependence_stats.num_miv++;
3178   if (dump_file && (dump_flags & TDF_DETAILS))
3179     fprintf (dump_file, "(analyze_miv_subscript \n");
3180
3181   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
3182
3183   if (chrec_zerop (difference))
3184     {
3185       /* Access functions are the same: all the elements are accessed
3186          in the same order.  */
3187       *overlaps_a = integer_zero_node;
3188       *overlaps_b = integer_zero_node;
3189       *last_conflicts = get_number_of_iters_for_loop (CHREC_VARIABLE (chrec_a));
3190       dependence_stats.num_miv_dependent++;
3191     }
3192
3193   else if (evolution_function_is_constant_p (difference)
3194            /* For the moment, the following is verified:
3195               evolution_function_is_affine_multivariate_p (chrec_a) */
3196            && chrec_steps_divide_constant_p (chrec_a, difference, &divide_p)
3197            && !divide_p)
3198     {
3199       /* testsuite/.../ssa-chrec-33.c
3200          {{21, +, 2}_1, +, -2}_2  vs.  {{20, +, 2}_1, +, -2}_2
3201
3202          The difference is 1, and the evolution steps are equal to 2,
3203          consequently there are no overlapping elements.  */
3204       *overlaps_a = chrec_known;
3205       *overlaps_b = chrec_known;
3206       *last_conflicts = integer_zero_node;
3207       dependence_stats.num_miv_independent++;
3208     }
3209
3210   else if (evolution_function_is_affine_multivariate_p (chrec_a)
3211            && !chrec_contains_symbols (chrec_a)
3212            && evolution_function_is_affine_multivariate_p (chrec_b)
3213            && !chrec_contains_symbols (chrec_b))
3214     {
3215       /* testsuite/.../ssa-chrec-35.c
3216          {0, +, 1}_2  vs.  {0, +, 1}_3
3217          the overlapping elements are respectively located at iterations:
3218          {0, +, 1}_x and {0, +, 1}_x,
3219          in other words, we have the equality:
3220          {0, +, 1}_2 ({0, +, 1}_x) = {0, +, 1}_3 ({0, +, 1}_x)
3221
3222          Other examples:
3223          {{0, +, 1}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y) =
3224          {0, +, 1}_1 ({{0, +, 1}_x, +, 2}_y)
3225
3226          {{0, +, 2}_1, +, 3}_2 ({0, +, 1}_y, {0, +, 1}_x) =
3227          {{0, +, 3}_1, +, 2}_2 ({0, +, 1}_x, {0, +, 1}_y)
3228       */
3229       analyze_subscript_affine_affine (chrec_a, chrec_b,
3230                                        overlaps_a, overlaps_b, last_conflicts);
3231
3232       if (*overlaps_a == chrec_dont_know
3233           || *overlaps_b == chrec_dont_know)
3234         dependence_stats.num_miv_unimplemented++;
3235       else if (*overlaps_a == chrec_known
3236                || *overlaps_b == chrec_known)
3237         dependence_stats.num_miv_independent++;
3238       else
3239         dependence_stats.num_miv_dependent++;
3240     }
3241
3242   else
3243     {
3244       /* When the analysis is too difficult, answer "don't know".  */
3245       if (dump_file && (dump_flags & TDF_DETAILS))
3246         fprintf (dump_file, "analyze_miv_subscript test failed: unimplemented.\n");
3247
3248       *overlaps_a = chrec_dont_know;
3249       *overlaps_b = chrec_dont_know;
3250       *last_conflicts = chrec_dont_know;
3251       dependence_stats.num_miv_unimplemented++;
3252     }
3253
3254   if (dump_file && (dump_flags & TDF_DETAILS))
3255     fprintf (dump_file, ")\n");
3256 }
3257
3258 /* Determines the iterations for which CHREC_A is equal to CHREC_B.
3259    OVERLAP_ITERATIONS_A and OVERLAP_ITERATIONS_B are initialized with
3260    two functions that describe the iterations that contain conflicting
3261    elements.
3262
3263    Remark: For an integer k >= 0, the following equality is true:
3264
3265    CHREC_A (OVERLAP_ITERATIONS_A (k)) == CHREC_B (OVERLAP_ITERATIONS_B (k)).
3266 */
3267
3268 static void
3269 analyze_overlapping_iterations (tree chrec_a,
3270                                 tree chrec_b,
3271                                 tree *overlap_iterations_a,
3272                                 tree *overlap_iterations_b,
3273                                 tree *last_conflicts)
3274 {
3275   dependence_stats.num_subscript_tests++;
3276
3277   if (dump_file && (dump_flags & TDF_DETAILS))
3278     {
3279       fprintf (dump_file, "(analyze_overlapping_iterations \n");
3280       fprintf (dump_file, "  (chrec_a = ");
3281       print_generic_expr (dump_file, chrec_a, 0);
3282       fprintf (dump_file, ")\n  (chrec_b = ");
3283       print_generic_expr (dump_file, chrec_b, 0);
3284       fprintf (dump_file, ")\n");
3285     }
3286
3287   if (chrec_a == NULL_TREE
3288       || chrec_b == NULL_TREE
3289       || chrec_contains_undetermined (chrec_a)
3290       || chrec_contains_undetermined (chrec_b))
3291     {
3292       dependence_stats.num_subscript_undetermined++;
3293
3294       *overlap_iterations_a = chrec_dont_know;
3295       *overlap_iterations_b = chrec_dont_know;
3296     }
3297
3298   /* If they are the same chrec, and are affine, they overlap
3299      on every iteration.  */
3300   else if (eq_evolutions_p (chrec_a, chrec_b)
3301            && evolution_function_is_affine_multivariate_p (chrec_a))
3302     {
3303       dependence_stats.num_same_subscript_function++;
3304       *overlap_iterations_a = integer_zero_node;
3305       *overlap_iterations_b = integer_zero_node;
3306       *last_conflicts = chrec_dont_know;
3307     }
3308
3309   /* If they aren't the same, and aren't affine, we can't do anything
3310      yet. */
3311   else if ((chrec_contains_symbols (chrec_a)
3312             || chrec_contains_symbols (chrec_b))
3313            && (!evolution_function_is_affine_multivariate_p (chrec_a)
3314                || !evolution_function_is_affine_multivariate_p (chrec_b)))
3315     {
3316       dependence_stats.num_subscript_undetermined++;
3317       *overlap_iterations_a = chrec_dont_know;
3318       *overlap_iterations_b = chrec_dont_know;
3319     }
3320
3321   else if (ziv_subscript_p (chrec_a, chrec_b))
3322     analyze_ziv_subscript (chrec_a, chrec_b,
3323                            overlap_iterations_a, overlap_iterations_b,
3324                            last_conflicts);
3325
3326   else if (siv_subscript_p (chrec_a, chrec_b))
3327     analyze_siv_subscript (chrec_a, chrec_b,
3328                            overlap_iterations_a, overlap_iterations_b,
3329                            last_conflicts);
3330
3331   else
3332     analyze_miv_subscript (chrec_a, chrec_b,
3333                            overlap_iterations_a, overlap_iterations_b,
3334                            last_conflicts);
3335
3336   if (dump_file && (dump_flags & TDF_DETAILS))
3337     {
3338       fprintf (dump_file, "  (overlap_iterations_a = ");
3339       print_generic_expr (dump_file, *overlap_iterations_a, 0);
3340       fprintf (dump_file, ")\n  (overlap_iterations_b = ");
3341       print_generic_expr (dump_file, *overlap_iterations_b, 0);
3342       fprintf (dump_file, ")\n");
3343       fprintf (dump_file, ")\n");
3344     }
3345 }
3346
3347 /* Helper function for uniquely inserting distance vectors.  */
3348
3349 static void
3350 save_dist_v (struct data_dependence_relation *ddr, lambda_vector dist_v)
3351 {
3352   unsigned i;
3353   lambda_vector v;
3354
3355   for (i = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), i, v); i++)
3356     if (lambda_vector_equal (v, dist_v, DDR_NB_LOOPS (ddr)))
3357       return;
3358
3359   VEC_safe_push (lambda_vector, heap, DDR_DIST_VECTS (ddr), dist_v);
3360 }
3361
3362 /* Helper function for uniquely inserting direction vectors.  */
3363
3364 static void
3365 save_dir_v (struct data_dependence_relation *ddr, lambda_vector dir_v)
3366 {
3367   unsigned i;
3368   lambda_vector v;
3369
3370   for (i = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), i, v); i++)
3371     if (lambda_vector_equal (v, dir_v, DDR_NB_LOOPS (ddr)))
3372       return;
3373
3374   VEC_safe_push (lambda_vector, heap, DDR_DIR_VECTS (ddr), dir_v);
3375 }
3376
3377 /* Add a distance of 1 on all the loops outer than INDEX.  If we
3378    haven't yet determined a distance for this outer loop, push a new
3379    distance vector composed of the previous distance, and a distance
3380    of 1 for this outer loop.  Example:
3381
3382    | loop_1
3383    |   loop_2
3384    |     A[10]
3385    |   endloop_2
3386    | endloop_1
3387
3388    Saved vectors are of the form (dist_in_1, dist_in_2).  First, we
3389    save (0, 1), then we have to save (1, 0).  */
3390
3391 static void