gcc/tree-data-ref.c

   1 /* Data references and dependences detectors.
   2    Copyright (C) 2003, 2004, 2005, 2006, 2007 Free Software Foundation, Inc.
   3    Contributed by Sebastian Pop <pop@cri.ensmp.fr>
   4
   5 This file is part of GCC.
   6
   7 GCC is free software; you can redistribute it and/or modify it under
   8 the terms of the GNU General Public License as published by the Free
   9 Software Foundation; either version 2, or (at your option) any later
  10 version.
  11
  12 GCC is distributed in the hope that it will be useful, but WITHOUT ANY
  13 WARRANTY; without even the implied warranty of MERCHANTABILITY or
  14 FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
  15 for more details.
  16
  17 You should have received a copy of the GNU General Public License
  18 along with GCC; see the file COPYING.  If not, write to the Free
  19 Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA
  20 02110-1301, USA.  */
  21
  22 /* This pass walks a given loop structure searching for array
  23    references.  The information about the array accesses is recorded
  24    in DATA_REFERENCE structures.
  25
  26    The basic test for determining the dependences is:
  27    given two access functions chrec1 and chrec2 to a same array, and
  28    x and y two vectors from the iteration domain, the same element of
  29    the array is accessed twice at iterations x and y if and only if:
  30    |             chrec1 (x) == chrec2 (y).
  31
  32    The goals of this analysis are:
  33
  34    - to determine the independence: the relation between two
  35      independent accesses is qualified with the chrec_known (this
  36      information allows a loop parallelization),
  37
  38    - when two data references access the same data, to qualify the
  39      dependence relation with classic dependence representations:
  40
  41        - distance vectors
  42        - direction vectors
  43        - loop carried level dependence
  44        - polyhedron dependence
  45      or with the chains of recurrences based representation,
  46
  47    - to define a knowledge base for storing the data dependence
  48      information,
  49
  50    - to define an interface to access this data.
  51
  52
  53    Definitions:
  54
  55    - subscript: given two array accesses a subscript is the tuple
  56    composed of the access functions for a given dimension.  Example:
  57    Given A[f1][f2][f3] and B[g1][g2][g3], there are three subscripts:
  58    (f1, g1), (f2, g2), (f3, g3).
  59
  60    - Diophantine equation: an equation whose coefficients and
  61    solutions are integer constants, for example the equation
  62    |   3*x + 2*y = 1
  63    has an integer solution x = 1 and y = -1.
  64
  65    References:
  66
  67    - "Advanced Compilation for High Performance Computing" by Randy
  68    Allen and Ken Kennedy.
  69    http://citeseer.ist.psu.edu/goff91practical.html
  70
  71    - "Loop Transformations for Restructuring Compilers - The Foundations"
  72    by Utpal Banerjee.
  73
  74
  75 */
  76
  77 #include "config.h"
  78 #include "system.h"
  79 #include "coretypes.h"
  80 #include "tm.h"
  81 #include "ggc.h"
  82 #include "tree.h"
  83
  84 /* These RTL headers are needed for basic-block.h.  */
  85 #include "rtl.h"
  86 #include "basic-block.h"
  87 #include "diagnostic.h"
  88 #include "tree-flow.h"
  89 #include "tree-dump.h"
  90 #include "timevar.h"
  91 #include "cfgloop.h"
  92 #include "tree-chrec.h"
  93 #include "tree-data-ref.h"
  94 #include "tree-scalar-evolution.h"
  95 #include "tree-pass.h"
  96 #include "langhooks.h"
  97
  98 static struct datadep_stats
  99 {
 100   int num_dependence_tests;
 101   int num_dependence_dependent;
 102   int num_dependence_independent;
 103   int num_dependence_undetermined;
 104
 105   int num_subscript_tests;
 106   int num_subscript_undetermined;
 107   int num_same_subscript_function;
 108
 109   int num_ziv;
 110   int num_ziv_independent;
 111   int num_ziv_dependent;
 112   int num_ziv_unimplemented;
 113
 114   int num_siv;
 115   int num_siv_independent;
 116   int num_siv_dependent;
 117   int num_siv_unimplemented;
 118
 119   int num_miv;
 120   int num_miv_independent;
 121   int num_miv_dependent;
 122   int num_miv_unimplemented;
 123 } dependence_stats;
 124
 125 static tree object_analysis (tree, tree, bool, struct data_reference **,
 126                              tree *, tree *, tree *, tree *, tree *,
 127                              struct ptr_info_def **, subvar_t *);
 128 static bool subscript_dependence_tester_1 (struct data_dependence_relation *,
 129                                            struct data_reference *,
 130                                            struct data_reference *);
 131
 132 /* Determine if PTR and DECL may alias, the result is put in ALIASED.
 133    Return FALSE if there is no symbol memory tag for PTR.  */
 134
 135 static bool
 136 ptr_decl_may_alias_p (tree ptr, tree decl,
 137                       struct data_reference *ptr_dr,
 138                       bool *aliased)
 139 {
 140   tree tag = NULL_TREE;
 141   struct ptr_info_def *pi = DR_PTR_INFO (ptr_dr);
 142
 143   gcc_assert (TREE_CODE (ptr) == SSA_NAME && DECL_P (decl));
 144
 145   if (pi)
 146     tag = pi->name_mem_tag;
 147   if (!tag)
 148     tag = symbol_mem_tag (SSA_NAME_VAR (ptr));
 149   if (!tag)
 150     tag = DR_MEMTAG (ptr_dr);
 151   if (!tag)
 152     return false;
 153
 154   *aliased = is_aliased_with (tag, decl);
 155   return true;
 156 }
 157
 158
 159 /* Determine if two pointers may alias, the result is put in ALIASED.
 160    Return FALSE if there is no symbol memory tag for one of the pointers.  */
 161
 162 static bool
 163 ptr_ptr_may_alias_p (tree ptr_a, tree ptr_b,
 164                      struct data_reference *dra,
 165                      struct data_reference *drb,
 166                      bool *aliased)
 167 {
 168   tree tag_a = NULL_TREE, tag_b = NULL_TREE;
 169   struct ptr_info_def *pi_a = DR_PTR_INFO (dra);
 170   struct ptr_info_def *pi_b = DR_PTR_INFO (drb);
 171   bitmap bal1, bal2;
 172
 173   if (pi_a && pi_a->name_mem_tag && pi_b && pi_b->name_mem_tag)
 174     {
 175       tag_a = pi_a->name_mem_tag;
 176       tag_b = pi_b->name_mem_tag;
 177     }
 178   else
 179     {
 180       tag_a = symbol_mem_tag (SSA_NAME_VAR (ptr_a));
 181       if (!tag_a)
 182         tag_a = DR_MEMTAG (dra);
 183       if (!tag_a)
 184         return false;
 185
 186       tag_b = symbol_mem_tag (SSA_NAME_VAR (ptr_b));
 187       if (!tag_b)
 188         tag_b = DR_MEMTAG (drb);
 189       if (!tag_b)
 190         return false;
 191     }
 192   bal1 = BITMAP_ALLOC (NULL);
 193   bitmap_set_bit (bal1, DECL_UID (tag_a));
 194   if (MTAG_P (tag_a) && MTAG_ALIASES (tag_a))
 195     bitmap_ior_into (bal1, MTAG_ALIASES (tag_a));
 196
 197   bal2 = BITMAP_ALLOC (NULL);
 198   bitmap_set_bit (bal2, DECL_UID (tag_b));
 199   if (MTAG_P (tag_b) && MTAG_ALIASES (tag_b))
 200     bitmap_ior_into (bal2, MTAG_ALIASES (tag_b));
 201   *aliased = bitmap_intersect_p (bal1, bal2);
 202
 203   BITMAP_FREE (bal1);
 204   BITMAP_FREE (bal2);
 205   return true;
 206 }
 207
 208
 209 /* Determine if BASE_A and BASE_B may alias, the result is put in ALIASED.
 210    Return FALSE if there is no symbol memory tag for one of the symbols.  */
 211
 212 static bool
 213 may_alias_p (tree base_a, tree base_b,
 214              struct data_reference *dra,
 215              struct data_reference *drb,
 216              bool *aliased)
 217 {
 218   if (TREE_CODE (base_a) == ADDR_EXPR || TREE_CODE (base_b) == ADDR_EXPR)
 219     {
 220       if (TREE_CODE (base_a) == ADDR_EXPR && TREE_CODE (base_b) == ADDR_EXPR)
 221         {
 222          *aliased = (TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0));
 223          return true;
 224         }
 225       if (TREE_CODE (base_a) == ADDR_EXPR)
 226         return ptr_decl_may_alias_p (base_b, TREE_OPERAND (base_a, 0), drb,
 227                                      aliased);
 228       else
 229         return ptr_decl_may_alias_p (base_a, TREE_OPERAND (base_b, 0), dra,
 230                                      aliased);
 231     }
 232
 233   return ptr_ptr_may_alias_p (base_a, base_b, dra, drb, aliased);
 234 }
 235
 236
 237 /* Determine if a pointer (BASE_A) and a record/union access (BASE_B)
 238    are not aliased. Return TRUE if they differ.  */
 239 static bool
 240 record_ptr_differ_p (struct data_reference *dra,
 241                      struct data_reference *drb)
 242 {
 243   bool aliased;
 244   tree base_a = DR_BASE_OBJECT (dra);
 245   tree base_b = DR_BASE_OBJECT (drb);
 246
 247   if (TREE_CODE (base_b) != COMPONENT_REF)
 248     return false;
 249
 250   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
 251      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
 252      Probably will be unnecessary with struct alias analysis.  */
 253   while (TREE_CODE (base_b) == COMPONENT_REF)
 254      base_b = TREE_OPERAND (base_b, 0);
 255   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
 256      ((*q)[i]).  */
 257   if (TREE_CODE (base_a) == INDIRECT_REF
 258       && ((TREE_CODE (base_b) == VAR_DECL
 259            && (ptr_decl_may_alias_p (TREE_OPERAND (base_a, 0), base_b, dra,
 260                                      &aliased)
 261                && !aliased))
 262           || (TREE_CODE (base_b) == INDIRECT_REF
 263               && (ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
 264                                        TREE_OPERAND (base_b, 0), dra, drb,
 265                                        &aliased)
 266                   && !aliased))))
 267     return true;
 268   else
 269     return false;
 270 }
 271
 272 /* Determine if two record/union accesses are aliased. Return TRUE if they
 273    differ.  */
 274 static bool
 275 record_record_differ_p (struct data_reference *dra,
 276                         struct data_reference *drb)
 277 {
 278   bool aliased;
 279   tree base_a = DR_BASE_OBJECT (dra);
 280   tree base_b = DR_BASE_OBJECT (drb);
 281
 282   if (TREE_CODE (base_b) != COMPONENT_REF
 283       || TREE_CODE (base_a) != COMPONENT_REF)
 284     return false;
 285
 286   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
 287      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
 288      Probably will be unnecessary with struct alias analysis.  */
 289   while (TREE_CODE (base_b) == COMPONENT_REF)
 290     base_b = TREE_OPERAND (base_b, 0);
 291   while (TREE_CODE (base_a) == COMPONENT_REF)
 292     base_a = TREE_OPERAND (base_a, 0);
 293
 294   if (TREE_CODE (base_a) == INDIRECT_REF
 295       && TREE_CODE (base_b) == INDIRECT_REF
 296       && ptr_ptr_may_alias_p (TREE_OPERAND (base_a, 0),
 297                               TREE_OPERAND (base_b, 0),
 298                               dra, drb, &aliased)
 299       && !aliased)
 300     return true;
 301   else
 302     return false;
 303 }
 304
 305 /* Determine if an array access (BASE_A) and a record/union access (BASE_B)
 306    are not aliased. Return TRUE if they differ.  */
 307 static bool
 308 record_array_differ_p (struct data_reference *dra,
 309                        struct data_reference *drb)
 310 {
 311   bool aliased;
 312   tree base_a = DR_BASE_OBJECT (dra);
 313   tree base_b = DR_BASE_OBJECT (drb);
 314
 315   if (TREE_CODE (base_b) != COMPONENT_REF)
 316     return false;
 317
 318   /* Peel COMPONENT_REFs to get to the base. Do not peel INDIRECT_REFs.
 319      For a.b.c.d[i] we will get a, and for a.b->c.d[i] we will get a.b.
 320      Probably will be unnecessary with struct alias analysis.  */
 321   while (TREE_CODE (base_b) == COMPONENT_REF)
 322      base_b = TREE_OPERAND (base_b, 0);
 323
 324   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
 325      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
 326      pointing to a.  */
 327   if (TREE_CODE (base_a) == VAR_DECL
 328       && (TREE_CODE (base_b) == VAR_DECL
 329           || (TREE_CODE (base_b) == INDIRECT_REF
 330               && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb,
 331                                         &aliased)
 332                   && !aliased))))
 333     return true;
 334   else
 335     return false;
 336 }
 337
 338
 339 /* Determine if an array access (BASE_A) and a pointer (BASE_B)
 340    are not aliased. Return TRUE if they differ.  */
 341 static bool
 342 array_ptr_differ_p (tree base_a, tree base_b,
 343                     struct data_reference *drb)
 344 {
 345   bool aliased;
 346
 347   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
 348      help of alias analysis that p is not pointing to a.  */
 349   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == INDIRECT_REF
 350       && (ptr_decl_may_alias_p (TREE_OPERAND (base_b, 0), base_a, drb, &aliased)
 351           && !aliased))
 352     return true;
 353   else
 354     return false;
 355 }
 356
 357
 358 /* This is the simplest data dependence test: determines whether the
 359    data references A and B access the same array/region.  Returns
 360    false when the property is not computable at compile time.
 361    Otherwise return true, and DIFFER_P will record the result. This
 362    utility will not be necessary when alias_sets_conflict_p will be
 363    less conservative.  */
 364
 365 static bool
 366 base_object_differ_p (struct data_reference *a,
 367                       struct data_reference *b,
 368                       bool *differ_p)
 369 {
 370   tree base_a = DR_BASE_OBJECT (a);
 371   tree base_b = DR_BASE_OBJECT (b);
 372   bool aliased;
 373
 374   if (!base_a || !base_b)
 375     return false;
 376
 377   /* Determine if same base.  Example: for the array accesses
 378      a[i], b[i] or pointer accesses *a, *b, bases are a, b.  */
 379   if (base_a == base_b)
 380     {
 381       *differ_p = false;
 382       return true;
 383     }
 384
 385   /* For pointer based accesses, (*p)[i], (*q)[j], the bases are (*p)
 386      and (*q)  */
 387   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
 388       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0))
 389     {
 390       *differ_p = false;
 391       return true;
 392     }
 393
 394   /* Record/union based accesses - s.a[i], t.b[j]. bases are s.a,t.b.  */
 395   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
 396       && TREE_OPERAND (base_a, 0) == TREE_OPERAND (base_b, 0)
 397       && TREE_OPERAND (base_a, 1) == TREE_OPERAND (base_b, 1))
 398     {
 399       *differ_p = false;
 400       return true;
 401     }
 402
 403
 404   /* Determine if different bases.  */
 405
 406   /* At this point we know that base_a != base_b.  However, pointer
 407      accesses of the form x=(*p) and y=(*q), whose bases are p and q,
 408      may still be pointing to the same base. In SSAed GIMPLE p and q will
 409      be SSA_NAMES in this case.  Therefore, here we check if they are
 410      really two different declarations.  */
 411   if (TREE_CODE (base_a) == VAR_DECL && TREE_CODE (base_b) == VAR_DECL)
 412     {
 413       *differ_p = true;
 414       return true;
 415     }
 416
 417   /* In case one of the bases is a pointer (a[i] and (*p)[i]), we check with the
 418      help of alias analysis that p is not pointing to a.  */
 419   if (array_ptr_differ_p (base_a, base_b, b)
 420       || array_ptr_differ_p (base_b, base_a, a))
 421     {
 422       *differ_p = true;
 423       return true;
 424     }
 425
 426   /* If the bases are pointers ((*q)[i] and (*p)[i]), we check with the
 427      help of alias analysis they don't point to the same bases.  */
 428   if (TREE_CODE (base_a) == INDIRECT_REF && TREE_CODE (base_b) == INDIRECT_REF
 429       && (may_alias_p (TREE_OPERAND (base_a, 0), TREE_OPERAND (base_b, 0), a, b,
 430                        &aliased)
 431           && !aliased))
 432     {
 433       *differ_p = true;
 434       return true;
 435     }
 436
 437   /* Compare two record/union bases s.a and t.b: s != t or (a != b and
 438      s and t are not unions).  */
 439   if (TREE_CODE (base_a) == COMPONENT_REF && TREE_CODE (base_b) == COMPONENT_REF
 440       && ((TREE_CODE (TREE_OPERAND (base_a, 0)) == VAR_DECL
 441            && TREE_CODE (TREE_OPERAND (base_b, 0)) == VAR_DECL
 442            && TREE_OPERAND (base_a, 0) != TREE_OPERAND (base_b, 0))
 443           || (TREE_CODE (TREE_TYPE (TREE_OPERAND (base_a, 0))) == RECORD_TYPE
 444               && TREE_CODE (TREE_TYPE (TREE_OPERAND (base_b, 0))) == RECORD_TYPE
 445               && TREE_OPERAND (base_a, 1) != TREE_OPERAND (base_b, 1))))
 446     {
 447       *differ_p = true;
 448       return true;
 449     }
 450
 451   /* Compare a record/union access (b.c[i] or p->c[i]) and a pointer
 452      ((*q)[i]).  */
 453   if (record_ptr_differ_p (a, b) || record_ptr_differ_p (b, a))
 454     {
 455       *differ_p = true;
 456       return true;
 457     }
 458
 459   /* Compare a record/union access (b.c[i] or p->c[i]) and an array access
 460      (a[i]). In case of p->c[i] use alias analysis to verify that p is not
 461      pointing to a.  */
 462   if (record_array_differ_p (a, b) || record_array_differ_p (b, a))
 463     {
 464       *differ_p = true;
 465       return true;
 466     }
 467
 468   /* Compare two record/union accesses (b.c[i] or p->c[i]).  */
 469   if (record_record_differ_p (a, b))
 470     {
 471       *differ_p = true;
 472       return true;
 473     }
 474
 475   return false;
 476 }
 477
 478 /* Function base_addr_differ_p.
 479
 480    This is the simplest data dependence test: determines whether the
 481    data references DRA and DRB access the same array/region.  Returns
 482    false when the property is not computable at compile time.
 483    Otherwise return true, and DIFFER_P will record the result.
 484
 485    The algorithm:
 486    1. if (both DRA and DRB are represented as arrays)
 487           compare DRA.BASE_OBJECT and DRB.BASE_OBJECT
 488    2. else if (both DRA and DRB are represented as pointers)
 489           try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION
 490    3. else if (DRA and DRB are represented differently or 2. fails)
 491           only try to prove that the bases are surely different
 492 */
 493
 494 static bool
 495 base_addr_differ_p (struct data_reference *dra,
 496                     struct data_reference *drb,
 497                     bool *differ_p)
 498 {
 499   tree addr_a = DR_BASE_ADDRESS (dra);
 500   tree addr_b = DR_BASE_ADDRESS (drb);
 501   tree type_a, type_b;
 502   tree decl_a, decl_b;
 503   bool aliased;
 504
 505   if (!addr_a || !addr_b)
 506     return false;
 507
 508   type_a = TREE_TYPE (addr_a);
 509   type_b = TREE_TYPE (addr_b);
 510
 511   gcc_assert (POINTER_TYPE_P (type_a) &&  POINTER_TYPE_P (type_b));
 512
 513   /* 1. if (both DRA and DRB are represented as arrays)
 514             compare DRA.BASE_OBJECT and DRB.BASE_OBJECT.  */
 515   if (DR_TYPE (dra) == ARRAY_REF_TYPE && DR_TYPE (drb) == ARRAY_REF_TYPE)
 516     return base_object_differ_p (dra, drb, differ_p);
 517
 518   /* 2. else if (both DRA and DRB are represented as pointers)
 519             try to prove that DRA.FIRST_LOCATION == DRB.FIRST_LOCATION.  */
 520   /* If base addresses are the same, we check the offsets, since the access of
 521      the data-ref is described by {base addr + offset} and its access function,
 522      i.e., in order to decide whether the bases of data-refs are the same we
 523      compare both base addresses and offsets.  */
 524   if (DR_TYPE (dra) == POINTER_REF_TYPE && DR_TYPE (drb) == POINTER_REF_TYPE
 525       && (addr_a == addr_b
 526           || (TREE_CODE (addr_a) == ADDR_EXPR && TREE_CODE (addr_b) == ADDR_EXPR
 527               && TREE_OPERAND (addr_a, 0) == TREE_OPERAND (addr_b, 0))))
 528     {
 529       /* Compare offsets.  */
 530       tree offset_a = DR_OFFSET (dra);
 531       tree offset_b = DR_OFFSET (drb);
 532
 533       STRIP_NOPS (offset_a);
 534       STRIP_NOPS (offset_b);
 535
 536       /* FORNOW: we only compare offsets that are MULT_EXPR, i.e., we don't handle
 537          PLUS_EXPR.  */
 538       if (offset_a == offset_b
 539           || (TREE_CODE (offset_a) == MULT_EXPR
 540               && TREE_CODE (offset_b) == MULT_EXPR
 541               && TREE_OPERAND (offset_a, 0) == TREE_OPERAND (offset_b, 0)
 542               && TREE_OPERAND (offset_a, 1) == TREE_OPERAND (offset_b, 1)))
 543         {
 544           *differ_p = false;
 545           return true;
 546         }
 547     }
 548
 549   /*  3. else if (DRA and DRB are represented differently or 2. fails)
 550               only try to prove that the bases are surely different.  */
 551
 552   /* Apply alias analysis.  */
 553   if (may_alias_p (addr_a, addr_b, dra, drb, &aliased) && !aliased)
 554     {
 555       *differ_p = true;
 556       return true;
 557     }
 558
 559   /* An instruction writing through a restricted pointer is "independent" of any
 560      instruction reading or writing through a different restricted pointer,
 561      in the same block/scope.  */
 562   else if (TYPE_RESTRICT (type_a)
 563            &&  TYPE_RESTRICT (type_b)
 564            && (!DR_IS_READ (drb) || !DR_IS_READ (dra))
 565            && TREE_CODE (DR_BASE_ADDRESS (dra)) == SSA_NAME
 566            && (decl_a = SSA_NAME_VAR (DR_BASE_ADDRESS (dra)))
 567            && TREE_CODE (decl_a) == PARM_DECL
 568            && TREE_CODE (DECL_CONTEXT (decl_a)) == FUNCTION_DECL
 569            && TREE_CODE (DR_BASE_ADDRESS (drb)) == SSA_NAME
 570            && (decl_b = SSA_NAME_VAR (DR_BASE_ADDRESS (drb)))
 571            && TREE_CODE (decl_b) == PARM_DECL
 572            && TREE_CODE (DECL_CONTEXT (decl_b)) == FUNCTION_DECL
 573            && DECL_CONTEXT (decl_a) == DECL_CONTEXT (decl_b))
 574     {
 575       *differ_p = true;
 576       return true;
 577     }
 578
 579   return false;
 580 }
 581
 582 /* Returns true iff A divides B.  */
 583
 584 static inline bool
 585 tree_fold_divides_p (tree a, tree b)
 586 {
 587   gcc_assert (TREE_CODE (a) == INTEGER_CST);
 588   gcc_assert (TREE_CODE (b) == INTEGER_CST);
 589   return integer_zerop (int_const_binop (TRUNC_MOD_EXPR, b, a, 0));
 590 }
 591
 592 /* Returns true iff A divides B.  */
 593
 594 static inline bool
 595 int_divides_p (int a, int b)
 596 {
 597   return ((b % a) == 0);
 598 }
 599
 600 \f
 601
 602 /* Dump into FILE all the data references from DATAREFS.  */
 603
 604 void
 605 dump_data_references (FILE *file, VEC (data_reference_p, heap) *datarefs)
 606 {
 607   unsigned int i;
 608   struct data_reference *dr;
 609
 610   for (i = 0; VEC_iterate (data_reference_p, datarefs, i, dr); i++)
 611     dump_data_reference (file, dr);
 612 }
 613
 614 /* Dump into FILE all the dependence relations from DDRS.  */
 615
 616 void
 617 dump_data_dependence_relations (FILE *file,
 618                                 VEC (ddr_p, heap) *ddrs)
 619 {
 620   unsigned int i;
 621   struct data_dependence_relation *ddr;
 622
 623   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 624     dump_data_dependence_relation (file, ddr);
 625 }
 626
 627 /* Dump function for a DATA_REFERENCE structure.  */
 628
 629 void
 630 dump_data_reference (FILE *outf,
 631                      struct data_reference *dr)
 632 {
 633   unsigned int i;
 634
 635   fprintf (outf, "(Data Ref: \n  stmt: ");
 636   print_generic_stmt (outf, DR_STMT (dr), 0);
 637   fprintf (outf, "  ref: ");
 638   print_generic_stmt (outf, DR_REF (dr), 0);
 639   fprintf (outf, "  base_object: ");
 640   print_generic_stmt (outf, DR_BASE_OBJECT (dr), 0);
 641
 642   for (i = 0; i < DR_NUM_DIMENSIONS (dr); i++)
 643     {
 644       fprintf (outf, "  Access function %d: ", i);
 645       print_generic_stmt (outf, DR_ACCESS_FN (dr, i), 0);
 646     }
 647   fprintf (outf, ")\n");
 648 }
 649
 650 /* Dumps the affine function described by FN to the file OUTF.  */
 651
 652 static void
 653 dump_affine_function (FILE *outf, affine_fn fn)
 654 {
 655   unsigned i;
 656   tree coef;
 657
 658   print_generic_expr (outf, VEC_index (tree, fn, 0), TDF_SLIM);
 659   for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
 660     {
 661       fprintf (outf, " + ");
 662       print_generic_expr (outf, coef, TDF_SLIM);
 663       fprintf (outf, " * x_%u", i);
 664     }
 665 }
 666
 667 /* Dumps the conflict function CF to the file OUTF.  */
 668
 669 static void
 670 dump_conflict_function (FILE *outf, conflict_function *cf)
 671 {
 672   unsigned i;
 673
 674   if (cf->n == NO_DEPENDENCE)
 675     fprintf (outf, "no dependence\n");
 676   else if (cf->n == NOT_KNOWN)
 677     fprintf (outf, "not known\n");
 678   else
 679     {
 680       for (i = 0; i < cf->n; i++)
 681         {
 682           fprintf (outf, "[");
 683           dump_affine_function (outf, cf->fns[i]);
 684           fprintf (outf, "]\n");
 685         }
 686     }
 687 }
 688
 689 /* Dump function for a SUBSCRIPT structure.  */
 690
 691 void
 692 dump_subscript (FILE *outf, struct subscript *subscript)
 693 {
 694   conflict_function *cf = SUB_CONFLICTS_IN_A (subscript);
 695
 696   fprintf (outf, "\n (subscript \n");
 697   fprintf (outf, "  iterations_that_access_an_element_twice_in_A: ");
 698   dump_conflict_function (outf, cf);
 699   if (CF_NONTRIVIAL_P (cf))
 700     {
 701       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 702       fprintf (outf, "  last_conflict: ");
 703       print_generic_stmt (outf, last_iteration, 0);
 704     }
 705
 706   cf = SUB_CONFLICTS_IN_B (subscript);
 707   fprintf (outf, "  iterations_that_access_an_element_twice_in_B: ");
 708   dump_conflict_function (outf, cf);
 709   if (CF_NONTRIVIAL_P (cf))
 710     {
 711       tree last_iteration = SUB_LAST_CONFLICT (subscript);
 712       fprintf (outf, "  last_conflict: ");
 713       print_generic_stmt (outf, last_iteration, 0);
 714     }
 715
 716   fprintf (outf, "  (Subscript distance: ");
 717   print_generic_stmt (outf, SUB_DISTANCE (subscript), 0);
 718   fprintf (outf, "  )\n");
 719   fprintf (outf, " )\n");
 720 }
 721
 722 /* Print the classic direction vector DIRV to OUTF.  */
 723
 724 void
 725 print_direction_vector (FILE *outf,
 726                         lambda_vector dirv,
 727                         int length)
 728 {
 729   int eq;
 730
 731   for (eq = 0; eq < length; eq++)
 732     {
 733       enum data_dependence_direction dir = dirv[eq];
 734
 735       switch (dir)
 736         {
 737         case dir_positive:
 738           fprintf (outf, "    +");
 739           break;
 740         case dir_negative:
 741           fprintf (outf, "    -");
 742           break;
 743         case dir_equal:
 744           fprintf (outf, "    =");
 745           break;
 746         case dir_positive_or_equal:
 747           fprintf (outf, "   +=");
 748           break;
 749         case dir_positive_or_negative:
 750           fprintf (outf, "   +-");
 751           break;
 752         case dir_negative_or_equal:
 753           fprintf (outf, "   -=");
 754           break;
 755         case dir_star:
 756           fprintf (outf, "    *");
 757           break;
 758         default:
 759           fprintf (outf, "indep");
 760           break;
 761         }
 762     }
 763   fprintf (outf, "\n");
 764 }
 765
 766 /* Print a vector of direction vectors.  */
 767
 768 void
 769 print_dir_vectors (FILE *outf, VEC (lambda_vector, heap) *dir_vects,
 770                    int length)
 771 {
 772   unsigned j;
 773   lambda_vector v;
 774
 775   for (j = 0; VEC_iterate (lambda_vector, dir_vects, j, v); j++)
 776     print_direction_vector (outf, v, length);
 777 }
 778
 779 /* Print a vector of distance vectors.  */
 780
 781 void
 782 print_dist_vectors  (FILE *outf, VEC (lambda_vector, heap) *dist_vects,
 783                      int length)
 784 {
 785   unsigned j;
 786   lambda_vector v;
 787
 788   for (j = 0; VEC_iterate (lambda_vector, dist_vects, j, v); j++)
 789     print_lambda_vector (outf, v, length);
 790 }
 791
 792 /* Debug version.  */
 793
 794 void
 795 debug_data_dependence_relation (struct data_dependence_relation *ddr)
 796 {
 797   dump_data_dependence_relation (stderr, ddr);
 798 }
 799
 800 /* Dump function for a DATA_DEPENDENCE_RELATION structure.  */
 801
 802 void
 803 dump_data_dependence_relation (FILE *outf,
 804                                struct data_dependence_relation *ddr)
 805 {
 806   struct data_reference *dra, *drb;
 807
 808   dra = DDR_A (ddr);
 809   drb = DDR_B (ddr);
 810   fprintf (outf, "(Data Dep: \n");
 811   if (DDR_ARE_DEPENDENT (ddr) == chrec_dont_know)
 812     fprintf (outf, "    (don't know)\n");
 813
 814   else if (DDR_ARE_DEPENDENT (ddr) == chrec_known)
 815     fprintf (outf, "    (no dependence)\n");
 816
 817   else if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
 818     {
 819       unsigned int i;
 820       struct loop *loopi;
 821
 822       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
 823         {
 824           fprintf (outf, "  access_fn_A: ");
 825           print_generic_stmt (outf, DR_ACCESS_FN (dra, i), 0);
 826           fprintf (outf, "  access_fn_B: ");
 827           print_generic_stmt (outf, DR_ACCESS_FN (drb, i), 0);
 828           dump_subscript (outf, DDR_SUBSCRIPT (ddr, i));
 829         }
 830
 831       fprintf (outf, "  inner loop index: %d\n", DDR_INNER_LOOP (ddr));
 832       fprintf (outf, "  loop nest: (");
 833       for (i = 0; VEC_iterate (loop_p, DDR_LOOP_NEST (ddr), i, loopi); i++)
 834         fprintf (outf, "%d ", loopi->num);
 835       fprintf (outf, ")\n");
 836
 837       for (i = 0; i < DDR_NUM_DIST_VECTS (ddr); i++)
 838         {
 839           fprintf (outf, "  distance_vector: ");
 840           print_lambda_vector (outf, DDR_DIST_VECT (ddr, i),
 841                                DDR_NB_LOOPS (ddr));
 842         }
 843
 844       for (i = 0; i < DDR_NUM_DIR_VECTS (ddr); i++)
 845         {
 846           fprintf (outf, "  direction_vector: ");
 847           print_direction_vector (outf, DDR_DIR_VECT (ddr, i),
 848                                   DDR_NB_LOOPS (ddr));
 849         }
 850     }
 851
 852   fprintf (outf, ")\n");
 853 }
 854
 855 /* Dump function for a DATA_DEPENDENCE_DIRECTION structure.  */
 856
 857 void
 858 dump_data_dependence_direction (FILE *file,
 859                                 enum data_dependence_direction dir)
 860 {
 861   switch (dir)
 862     {
 863     case dir_positive:
 864       fprintf (file, "+");
 865       break;
 866
 867     case dir_negative:
 868       fprintf (file, "-");
 869       break;
 870
 871     case dir_equal:
 872       fprintf (file, "=");
 873       break;
 874
 875     case dir_positive_or_negative:
 876       fprintf (file, "+-");
 877       break;
 878
 879     case dir_positive_or_equal:
 880       fprintf (file, "+=");
 881       break;
 882
 883     case dir_negative_or_equal:
 884       fprintf (file, "-=");
 885       break;
 886
 887     case dir_star:
 888       fprintf (file, "*");
 889       break;
 890
 891     default:
 892       break;
 893     }
 894 }
 895
 896 /* Dumps the distance and direction vectors in FILE.  DDRS contains
 897    the dependence relations, and VECT_SIZE is the size of the
 898    dependence vectors, or in other words the number of loops in the
 899    considered nest.  */
 900
 901 void
 902 dump_dist_dir_vectors (FILE *file, VEC (ddr_p, heap) *ddrs)
 903 {
 904   unsigned int i, j;
 905   struct data_dependence_relation *ddr;
 906   lambda_vector v;
 907
 908   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 909     if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE && DDR_AFFINE_P (ddr))
 910       {
 911         for (j = 0; VEC_iterate (lambda_vector, DDR_DIST_VECTS (ddr), j, v); j++)
 912           {
 913             fprintf (file, "DISTANCE_V (");
 914             print_lambda_vector (file, v, DDR_NB_LOOPS (ddr));
 915             fprintf (file, ")\n");
 916           }
 917
 918         for (j = 0; VEC_iterate (lambda_vector, DDR_DIR_VECTS (ddr), j, v); j++)
 919           {
 920             fprintf (file, "DIRECTION_V (");
 921             print_direction_vector (file, v, DDR_NB_LOOPS (ddr));
 922             fprintf (file, ")\n");
 923           }
 924       }
 925
 926   fprintf (file, "\n\n");
 927 }
 928
 929 /* Dumps the data dependence relations DDRS in FILE.  */
 930
 931 void
 932 dump_ddrs (FILE *file, VEC (ddr_p, heap) *ddrs)
 933 {
 934   unsigned int i;
 935   struct data_dependence_relation *ddr;
 936
 937   for (i = 0; VEC_iterate (ddr_p, ddrs, i, ddr); i++)
 938     dump_data_dependence_relation (file, ddr);
 939
 940   fprintf (file, "\n\n");
 941 }
 942
 943 \f
 944
 945 /* Given an ARRAY_REF node REF, records its access functions.
 946    Example: given A[i][3], record in ACCESS_FNS the opnd1 function,
 947    i.e. the constant "3", then recursively call the function on opnd0,
 948    i.e. the ARRAY_REF "A[i]".
 949    The function returns the base name: "A".  */
 950
 951 static tree
 952 analyze_array_indexes (struct loop *loop,
 953                        VEC(tree,heap) **access_fns,
 954                        tree ref, tree stmt)
 955 {
 956   tree opnd0, opnd1;
 957   tree access_fn;
 958
 959   opnd0 = TREE_OPERAND (ref, 0);
 960   opnd1 = TREE_OPERAND (ref, 1);
 961
 962   /* The detection of the evolution function for this data access is
 963      postponed until the dependence test.  This lazy strategy avoids
 964      the computation of access functions that are of no interest for
 965      the optimizers.  */
 966   access_fn = instantiate_parameters
 967     (loop, analyze_scalar_evolution (loop, opnd1));
 968
 969   VEC_safe_push (tree, heap, *access_fns, access_fn);
 970
 971   /* Recursively record other array access functions.  */
 972   if (TREE_CODE (opnd0) == ARRAY_REF)
 973     return analyze_array_indexes (loop, access_fns, opnd0, stmt);
 974
 975   /* Return the base name of the data access.  */
 976   else
 977     return opnd0;
 978 }
 979
 980 /* For a data reference REF contained in the statement STMT, initialize
 981    a DATA_REFERENCE structure, and return it.  IS_READ flag has to be
 982    set to true when REF is in the right hand side of an
 983    assignment.  */
 984
 985 static struct data_reference *
 986 init_array_ref (tree stmt, tree ref, bool is_read)
 987 {
 988   struct loop *loop = loop_containing_stmt (stmt);
 989   VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
 990   struct data_reference *res = XNEW (struct data_reference);;
 991
 992   if (dump_file && (dump_flags & TDF_DETAILS))
 993     {
 994       fprintf (dump_file, "(init_array_ref \n");
 995       fprintf (dump_file, "  (ref = ");
 996       print_generic_stmt (dump_file, ref, 0);
 997       fprintf (dump_file, ")\n");
 998     }
 999
1000   DR_STMT (res) = stmt;
1001   DR_REF (res) = ref;
1002   DR_BASE_OBJECT (res) = analyze_array_indexes (loop, &acc_fns, ref, stmt);
1003   DR_TYPE (res) = ARRAY_REF_TYPE;
1004   DR_SET_ACCESS_FNS (res, acc_fns);
1005   DR_IS_READ (res) = is_read;
1006   DR_BASE_ADDRESS (res) = NULL_TREE;
1007   DR_OFFSET (res) = NULL_TREE;
1008   DR_INIT (res) = NULL_TREE;
1009   DR_STEP (res) = NULL_TREE;
1010   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
1011   DR_MEMTAG (res) = NULL_TREE;
1012   DR_PTR_INFO (res) = NULL;
1013
1014   if (dump_file && (dump_flags & TDF_DETAILS))
1015     fprintf (dump_file, ")\n");
1016
1017   return res;
1018 }
1019
1020 /* For a data reference REF contained in the statement STMT, initialize
1021    a DATA_REFERENCE structure, and return it.  */
1022
1023 static struct data_reference *
1024 init_pointer_ref (tree stmt, tree ref, tree access_fn, bool is_read,
1025                   tree base_address, tree step, struct ptr_info_def *ptr_info)
1026 {
1027   struct data_reference *res = XNEW (struct data_reference);
1028   VEC(tree,heap) *acc_fns = VEC_alloc (tree, heap, 3);
1029
1030   if (dump_file && (dump_flags & TDF_DETAILS))
1031     {
1032       fprintf (dump_file, "(init_pointer_ref \n");
1033       fprintf (dump_file, "  (ref = ");
1034       print_generic_stmt (dump_file, ref, 0);
1035       fprintf (dump_file, ")\n");
1036     }
1037
1038   DR_STMT (res) = stmt;
1039   DR_REF (res) = ref;
1040   DR_BASE_OBJECT (res) = NULL_TREE;
1041   DR_TYPE (res) = POINTER_REF_TYPE;
1042   DR_SET_ACCESS_FNS (res, acc_fns);
1043   VEC_quick_push (tree, DR_ACCESS_FNS (res), access_fn);
1044   DR_IS_READ (res) = is_read;
1045   DR_BASE_ADDRESS (res) = base_address;
1046   DR_OFFSET (res) = NULL_TREE;
1047   DR_INIT (res) = NULL_TREE;
1048   DR_STEP (res) = step;
1049   DR_OFFSET_MISALIGNMENT (res) = NULL_TREE;
1050   DR_MEMTAG (res) = NULL_TREE;
1051   DR_PTR_INFO (res) = ptr_info;
1052
1053   if (dump_file && (dump_flags & TDF_DETAILS))
1054     fprintf (dump_file, ")\n");
1055
1056   return res;
1057 }
1058
1059 /* Analyze an indirect memory reference, REF, that comes from STMT.
1060    IS_READ is true if this is an indirect load, and false if it is
1061    an indirect store.
1062    Return a new data reference structure representing the indirect_ref, or
1063    NULL if we cannot describe the access function.  */
1064
1065 static struct data_reference *
1066 analyze_indirect_ref (tree stmt, tree ref, bool is_read)
1067 {
1068   struct loop *loop = loop_containing_stmt (stmt);
1069   tree ptr_ref = TREE_OPERAND (ref, 0);
1070   tree access_fn = analyze_scalar_evolution (loop, ptr_ref);
1071   tree init = initial_condition_in_loop_num (access_fn, loop->num);
1072   tree base_address = NULL_TREE, evolution, step = NULL_TREE;
1073   struct ptr_info_def *ptr_info = NULL;
1074
1075   if (TREE_CODE (ptr_ref) == SSA_NAME)
1076     ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1077
1078   STRIP_NOPS (init);
1079   if (access_fn == chrec_dont_know || !init || init == chrec_dont_know)
1080     {
1081       if (dump_file && (dump_flags & TDF_DETAILS))
1082         {
1083           fprintf (dump_file, "\nBad access function of ptr: ");
1084           print_generic_expr (dump_file, ref, TDF_SLIM);
1085           fprintf (dump_file, "\n");
1086         }
1087       return NULL;
1088     }
1089
1090   if (dump_file && (dump_flags & TDF_DETAILS))
1091     {
1092       fprintf (dump_file, "\nAccess function of ptr: ");
1093       print_generic_expr (dump_file, access_fn, TDF_SLIM);
1094       fprintf (dump_file, "\n");
1095     }
1096
1097   if (!expr_invariant_in_loop_p (loop, init))
1098     {
1099       if (dump_file && (dump_flags & TDF_DETAILS))
1100         fprintf (dump_file, "\ninitial condition is not loop invariant.\n");
1101     }
1102   else
1103     {
1104       base_address = init;
1105       evolution = evolution_part_in_loop_num (access_fn, loop->num);
1106       if (evolution != chrec_dont_know)
1107         {
1108           if (!evolution)
1109             step = ssize_int (0);
1110           else
1111             {
1112               if (TREE_CODE (evolution) == INTEGER_CST)
1113                 step = fold_convert (ssizetype, evolution);
1114               else
1115                 if (dump_file && (dump_flags & TDF_DETAILS))
1116                   fprintf (dump_file, "\nnon constant step for ptr access.\n");
1117             }
1118         }
1119       else
1120         if (dump_file && (dump_flags & TDF_DETAILS))
1121           fprintf (dump_file, "\nunknown evolution of ptr.\n");
1122     }
1123   return init_pointer_ref (stmt, ref, access_fn, is_read, base_address,
1124                            step, ptr_info);
1125 }
1126
1127 /* Function strip_conversions
1128
1129    Strip conversions that don't narrow the mode.  */
1130
1131 static tree
1132 strip_conversion (tree expr)
1133 {
1134   tree to, ti, oprnd0;
1135
1136   while (TREE_CODE (expr) == NOP_EXPR || TREE_CODE (expr) == CONVERT_EXPR)
1137     {
1138       to = TREE_TYPE (expr);
1139       oprnd0 = TREE_OPERAND (expr, 0);
1140       ti = TREE_TYPE (oprnd0);
1141
1142       if (!INTEGRAL_TYPE_P (to) || !INTEGRAL_TYPE_P (ti))
1143         return NULL_TREE;
1144       if (GET_MODE_SIZE (TYPE_MODE (to)) < GET_MODE_SIZE (TYPE_MODE (ti)))
1145         return NULL_TREE;
1146
1147       expr = oprnd0;
1148     }
1149   return expr;
1150 }
1151 \f
1152
1153 /* Function analyze_offset_expr
1154
1155    Given an offset expression EXPR received from get_inner_reference, analyze
1156    it and create an expression for INITIAL_OFFSET by substituting the variables
1157    of EXPR with initial_condition of the corresponding access_fn in the loop.
1158    E.g.,
1159       for i
1160          for (j = 3; j < N; j++)
1161             a[j].b[i][j] = 0;
1162
1163    For a[j].b[i][j], EXPR will be 'i * C_i + j * C_j + C'. 'i' cannot be
1164    substituted, since its access_fn in the inner loop is i. 'j' will be
1165    substituted with 3. An INITIAL_OFFSET will be 'i * C_i + C`', where
1166    C` =  3 * C_j + C.
1167
1168    Compute MISALIGN (the misalignment of the data reference initial access from
1169    its base). Misalignment can be calculated only if all the variables can be
1170    substituted with constants, otherwise, we record maximum possible alignment
1171    in ALIGNED_TO. In the above example, since 'i' cannot be substituted, MISALIGN
1172    will be NULL_TREE, and the biggest divider of C_i (a power of 2) will be
1173    recorded in ALIGNED_TO.
1174
1175    STEP is an evolution of the data reference in this loop in bytes.
1176    In the above example, STEP is C_j.
1177
1178    Return FALSE, if the analysis fails, e.g., there is no access_fn for a
1179    variable. In this case, all the outputs (INITIAL_OFFSET, MISALIGN, ALIGNED_TO
1180    and STEP) are NULL_TREEs. Otherwise, return TRUE.
1181
1182 */
1183
1184 static bool
1185 analyze_offset_expr (tree expr,
1186                      struct loop *loop,
1187                      tree *initial_offset,
1188                      tree *misalign,
1189                      tree *aligned_to,
1190                      tree *step)
1191 {
1192   tree oprnd0;
1193   tree oprnd1;
1194   tree left_offset = ssize_int (0);
1195   tree right_offset = ssize_int (0);
1196   tree left_misalign = ssize_int (0);
1197   tree right_misalign = ssize_int (0);
1198   tree left_step = ssize_int (0);
1199   tree right_step = ssize_int (0);
1200   enum tree_code code;
1201   tree init, evolution;
1202   tree left_aligned_to = NULL_TREE, right_aligned_to = NULL_TREE;
1203
1204   *step = NULL_TREE;
1205   *misalign = NULL_TREE;
1206   *aligned_to = NULL_TREE;
1207   *initial_offset = NULL_TREE;
1208
1209   /* Strip conversions that don't narrow the mode.  */
1210   expr = strip_conversion (expr);
1211   if (!expr)
1212     return false;
1213
1214   /* Stop conditions:
1215      1. Constant.  */
1216   if (TREE_CODE (expr) == INTEGER_CST)
1217     {
1218       *initial_offset = fold_convert (ssizetype, expr);
1219       *misalign = fold_convert (ssizetype, expr);
1220       *step = ssize_int (0);
1221       return true;
1222     }
1223
1224   /* 2. Variable. Try to substitute with initial_condition of the corresponding
1225      access_fn in the current loop.  */
1226   if (SSA_VAR_P (expr))
1227     {
1228       tree access_fn = analyze_scalar_evolution (loop, expr);
1229
1230       if (access_fn == chrec_dont_know)
1231         /* No access_fn.  */
1232         return false;
1233
1234       init = initial_condition_in_loop_num (access_fn, loop->num);
1235       if (!expr_invariant_in_loop_p (loop, init))
1236         /* Not enough information: may be not loop invariant.
1237            E.g., for a[b[i]], we get a[D], where D=b[i]. EXPR is D, its
1238            initial_condition is D, but it depends on i - loop's induction
1239            variable.  */
1240         return false;
1241
1242       evolution = evolution_part_in_loop_num (access_fn, loop->num);
1243       if (evolution && TREE_CODE (evolution) != INTEGER_CST)
1244         /* Evolution is not constant.  */
1245         return false;
1246
1247       if (TREE_CODE (init) == INTEGER_CST)
1248         *misalign = fold_convert (ssizetype, init);
1249       else
1250         /* Not constant, misalignment cannot be calculated.  */
1251         *misalign = NULL_TREE;
1252
1253       *initial_offset = fold_convert (ssizetype, init);
1254
1255       *step = evolution ? fold_convert (ssizetype, evolution) : ssize_int (0);
1256       return true;
1257     }
1258
1259   /* Recursive computation.  */
1260   if (!BINARY_CLASS_P (expr))
1261     {
1262       /* We expect to get binary expressions (PLUS/MINUS and MULT).  */
1263       if (dump_file && (dump_flags & TDF_DETAILS))
1264         {
1265           fprintf (dump_file, "\nNot binary expression ");
1266           print_generic_expr (dump_file, expr, TDF_SLIM);
1267           fprintf (dump_file, "\n");
1268         }
1269       return false;
1270     }
1271   oprnd0 = TREE_OPERAND (expr, 0);
1272   oprnd1 = TREE_OPERAND (expr, 1);
1273
1274   if (!analyze_offset_expr (oprnd0, loop, &left_offset, &left_misalign,
1275                             &left_aligned_to, &left_step)
1276       || !analyze_offset_expr (oprnd1, loop, &right_offset, &right_misalign,
1277                                &right_aligned_to, &right_step))
1278     return false;
1279
1280   /* The type of the operation: plus, minus or mult.  */
1281   code = TREE_CODE (expr);
1282   switch (code)
1283     {
1284     case MULT_EXPR:
1285       if (TREE_CODE (right_offset) != INTEGER_CST)
1286         /* RIGHT_OFFSET can be not constant. For example, for arrays of variable
1287            sized types.
1288            FORNOW: We don't support such cases.  */
1289         return false;
1290
1291       /* Strip conversions that don't narrow the mode.  */
1292       left_offset = strip_conversion (left_offset);
1293       if (!left_offset)
1294         return false;
1295       /* Misalignment computation.  */
1296       if (SSA_VAR_P (left_offset))
1297         {
1298           /* If the left side contains variables that can't be substituted with
1299              constants, the misalignment is unknown. However, if the right side
1300              is a multiple of some alignment, we know that the expression is
1301              aligned to it. Therefore, we record such maximum possible value.
1302            */
1303           *misalign = NULL_TREE;
1304           *aligned_to = ssize_int (highest_pow2_factor (right_offset));
1305         }
1306       else
1307         {
1308           /* The left operand was successfully substituted with constant.  */
1309           if (left_misalign)
1310             {
1311               /* In case of EXPR '(i * C1 + j) * C2', LEFT_MISALIGN is
1312                  NULL_TREE.  */
1313               *misalign  = size_binop (code, left_misalign, right_misalign);
1314               if (left_aligned_to && right_aligned_to)
1315                 *aligned_to = size_binop (MIN_EXPR, left_aligned_to,
1316                                           right_aligned_to);
1317               else
1318                 *aligned_to = left_aligned_to ?
1319                   left_aligned_to : right_aligned_to;
1320             }
1321           else
1322             *misalign = NULL_TREE;
1323         }
1324
1325       /* Step calculation.  */
1326       /* Multiply the step by the right operand.  */
1327       *step  = size_binop (MULT_EXPR, left_step, right_offset);
1328       break;
1329
1330     case PLUS_EXPR:
1331     case MINUS_EXPR:
1332       /* Combine the recursive calculations for step and misalignment.  */
1333       *step = size_binop (code, left_step, right_step);
1334
1335       /* Unknown alignment.  */
1336       if ((!left_misalign && !left_aligned_to)
1337           || (!right_misalign && !right_aligned_to))
1338         {
1339           *misalign = NULL_TREE;
1340           *aligned_to = NULL_TREE;
1341           break;
1342         }
1343
1344       if (left_misalign && right_misalign)
1345         *misalign = size_binop (code, left_misalign, right_misalign);
1346       else
1347         *misalign = left_misalign ? left_misalign : right_misalign;
1348
1349       if (left_aligned_to && right_aligned_to)
1350         *aligned_to = size_binop (MIN_EXPR, left_aligned_to, right_aligned_to);
1351       else
1352         *aligned_to = left_aligned_to ? left_aligned_to : right_aligned_to;
1353
1354       break;
1355
1356     default:
1357       gcc_unreachable ();
1358     }
1359
1360   /* Compute offset.  */
1361   *initial_offset = fold_convert (ssizetype,
1362                                   fold_build2 (code, TREE_TYPE (left_offset),
1363                                                left_offset,
1364                                                right_offset));
1365   return true;
1366 }
1367
1368 /* Function address_analysis
1369
1370    Return the BASE of the address expression EXPR.
1371    Also compute the OFFSET from BASE, MISALIGN and STEP.
1372
1373    Input:
1374    EXPR - the address expression that is being analyzed
1375    STMT - the statement that contains EXPR or its original memory reference
1376    IS_READ - TRUE if STMT reads from EXPR, FALSE if writes to EXPR
1377    DR - data_reference struct for the original memory reference
1378
1379    Output:
1380    BASE (returned value) - the base of the data reference EXPR.
1381    INITIAL_OFFSET - initial offset of EXPR from BASE (an expression)
1382    MISALIGN - offset of EXPR from BASE in bytes (a constant) or NULL_TREE if the
1383               computation is impossible
1384    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1385                 calculated (doesn't depend on variables)
1386    STEP - evolution of EXPR in the loop
1387
1388    If something unexpected is encountered (an unsupported form of data-ref),
1389    then NULL_TREE is returned.
1390  */
1391
1392 static tree
1393 address_analysis (tree expr, tree stmt, bool is_read, struct data_reference *dr,
1394                   tree *offset, tree *misalign, tree *aligned_to, tree *step)
1395 {
1396   tree oprnd0, oprnd1, base_address, offset_expr, base_addr0, base_addr1;
1397   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1398   tree dummy, address_aligned_to = NULL_TREE;
1399   struct ptr_info_def *dummy1;
1400   subvar_t dummy2;
1401
1402   switch (TREE_CODE (expr))
1403     {
1404     case PLUS_EXPR:
1405     case MINUS_EXPR:
1406       /* EXPR is of form {base +/- offset} (or {offset +/- base}).  */
1407       oprnd0 = TREE_OPERAND (expr, 0);
1408       oprnd1 = TREE_OPERAND (expr, 1);
1409
1410       STRIP_NOPS (oprnd0);
1411       STRIP_NOPS (oprnd1);
1412
1413       /* Recursively try to find the base of the address contained in EXPR.
1414          For offset, the returned base will be NULL.  */
1415       base_addr0 = address_analysis (oprnd0, stmt, is_read, dr, &address_offset,
1416                                      &address_misalign, &address_aligned_to,
1417                                      step);
1418
1419       base_addr1 = address_analysis (oprnd1, stmt, is_read,  dr, &address_offset,
1420                                      &address_misalign, &address_aligned_to,
1421                                      step);
1422
1423       /* We support cases where only one of the operands contains an
1424          address.  */
1425       if ((base_addr0 && base_addr1) || (!base_addr0 && !base_addr1))
1426         {
1427           if (dump_file && (dump_flags & TDF_DETAILS))
1428             {
1429               fprintf (dump_file,
1430                     "\neither more than one address or no addresses in expr ");
1431               print_generic_expr (dump_file, expr, TDF_SLIM);
1432               fprintf (dump_file, "\n");
1433             }
1434           return NULL_TREE;
1435         }
1436
1437       /* To revert STRIP_NOPS.  */
1438       oprnd0 = TREE_OPERAND (expr, 0);
1439       oprnd1 = TREE_OPERAND (expr, 1);
1440
1441       offset_expr = base_addr0 ?
1442         fold_convert (ssizetype, oprnd1) : fold_convert (ssizetype, oprnd0);
1443
1444       /* EXPR is of form {base +/- offset} (or {offset +/- base}). If offset is
1445          a number, we can add it to the misalignment value calculated for base,
1446          otherwise, misalignment is NULL.  */
1447       if (TREE_CODE (offset_expr) == INTEGER_CST && address_misalign)
1448         {
1449           *misalign = size_binop (TREE_CODE (expr), address_misalign,
1450                                   offset_expr);
1451           *aligned_to = address_aligned_to;
1452         }
1453       else
1454         {
1455           *misalign = NULL_TREE;
1456           *aligned_to = NULL_TREE;
1457         }
1458
1459       /* Combine offset (from EXPR {base + offset}) with the offset calculated
1460          for base.  */
1461       *offset = size_binop (TREE_CODE (expr), address_offset, offset_expr);
1462       return base_addr0 ? base_addr0 : base_addr1;
1463
1464     case ADDR_EXPR:
1465       base_address = object_analysis (TREE_OPERAND (expr, 0), stmt, is_read,
1466                                       &dr, offset, misalign, aligned_to, step,
1467                                       &dummy, &dummy1, &dummy2);
1468       return base_address;
1469
1470     case SSA_NAME:
1471       if (!POINTER_TYPE_P (TREE_TYPE (expr)))
1472         {
1473           if (dump_file && (dump_flags & TDF_DETAILS))
1474             {
1475               fprintf (dump_file, "\nnot pointer SSA_NAME ");
1476               print_generic_expr (dump_file, expr, TDF_SLIM);
1477               fprintf (dump_file, "\n");
1478             }
1479           return NULL_TREE;
1480         }
1481       *aligned_to = ssize_int (TYPE_ALIGN_UNIT (TREE_TYPE (TREE_TYPE (expr))));
1482       *misalign = ssize_int (0);
1483       *offset = ssize_int (0);
1484       *step = ssize_int (0);
1485       return expr;
1486
1487     default:
1488       return NULL_TREE;
1489     }
1490 }
1491
1492
1493 /* Function object_analysis
1494
1495    Create a data-reference structure DR for MEMREF.
1496    Return the BASE of the data reference MEMREF if the analysis is possible.
1497    Also compute the INITIAL_OFFSET from BASE, MISALIGN and STEP.
1498    E.g., for EXPR a.b[i] + 4B, BASE is a, and OFFSET is the overall offset
1499    'a.b[i] + 4B' from a (can be an expression), MISALIGN is an OFFSET
1500    instantiated with initial_conditions of access_functions of variables,
1501    and STEP is the evolution of the DR_REF in this loop.
1502
1503    Function get_inner_reference is used for the above in case of ARRAY_REF and
1504    COMPONENT_REF.
1505
1506    The structure of the function is as follows:
1507    Part 1:
1508    Case 1. For handled_component_p refs
1509           1.1 build data-reference structure for MEMREF
1510           1.2 call get_inner_reference
1511             1.2.1 analyze offset expr received from get_inner_reference
1512           (fall through with BASE)
1513    Case 2. For declarations
1514           2.1 set MEMTAG
1515    Case 3. For INDIRECT_REFs
1516           3.1 build data-reference structure for MEMREF
1517           3.2 analyze evolution and initial condition of MEMREF
1518           3.3 set data-reference structure for MEMREF
1519           3.4 call address_analysis to analyze INIT of the access function
1520           3.5 extract memory tag
1521
1522    Part 2:
1523    Combine the results of object and address analysis to calculate
1524    INITIAL_OFFSET, STEP and misalignment info.
1525
1526    Input:
1527    MEMREF - the memory reference that is being analyzed
1528    STMT - the statement that contains MEMREF
1529    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1530
1531    Output:
1532    BASE_ADDRESS (returned value) - the base address of the data reference MEMREF
1533                                    E.g, if MEMREF is a.b[k].c[i][j] the returned
1534                                    base is &a.
1535    DR - data_reference struct for MEMREF
1536    INITIAL_OFFSET - initial offset of MEMREF from BASE (an expression)
1537    MISALIGN - offset of MEMREF from BASE in bytes (a constant) modulo alignment of
1538               ALIGNMENT or NULL_TREE if the computation is impossible
1539    ALIGNED_TO - maximum alignment of EXPR or NULL_TREE if MISALIGN can be
1540                 calculated (doesn't depend on variables)
1541    STEP - evolution of the DR_REF in the loop
1542    MEMTAG - memory tag for aliasing purposes
1543    PTR_INFO - NULL or points-to aliasing info from a pointer SSA_NAME
1544    SUBVARS - Sub-variables of the variable
1545
1546    If the analysis of MEMREF evolution in the loop fails, NULL_TREE is returned,
1547    but DR can be created anyway.
1548
1549 */
1550
1551 static tree
1552 object_analysis (tree memref, tree stmt, bool is_read,
1553                  struct data_reference **dr, tree *offset, tree *misalign,
1554                  tree *aligned_to, tree *step, tree *memtag,
1555                  struct ptr_info_def **ptr_info, subvar_t *subvars)
1556 {
1557   tree base = NULL_TREE, base_address = NULL_TREE;
1558   tree object_offset = ssize_int (0), object_misalign = ssize_int (0);
1559   tree object_step = ssize_int (0), address_step = ssize_int (0);
1560   tree address_offset = ssize_int (0), address_misalign = ssize_int (0);
1561   HOST_WIDE_INT pbitsize, pbitpos;
1562   tree poffset, bit_pos_in_bytes;
1563   enum machine_mode pmode;
1564   int punsignedp, pvolatilep;
1565   tree ptr_step = ssize_int (0), ptr_init = NULL_TREE;
1566   struct loop *loop = loop_containing_stmt (stmt);
1567   struct data_reference *ptr_dr = NULL;
1568   tree object_aligned_to = NULL_TREE, address_aligned_to = NULL_TREE;
1569   tree comp_ref = NULL_TREE;
1570
1571  *ptr_info = NULL;
1572
1573   /* Part 1:  */
1574   /* Case 1. handled_component_p refs.  */
1575   if (handled_component_p (memref))
1576     {
1577       /* 1.1 build data-reference structure for MEMREF.  */
1578       if (!(*dr))
1579         {
1580           if (TREE_CODE (memref) == ARRAY_REF)
1581             *dr = init_array_ref (stmt, memref, is_read);
1582           else if (TREE_CODE (memref) == COMPONENT_REF)
1583             comp_ref = memref;
1584           else
1585             {
1586               if (dump_file && (dump_flags & TDF_DETAILS))
1587                 {
1588                   fprintf (dump_file, "\ndata-ref of unsupported type ");
1589                   print_generic_expr (dump_file, memref, TDF_SLIM);
1590                   fprintf (dump_file, "\n");
1591                 }
1592               return NULL_TREE;
1593             }
1594         }
1595
1596       /* 1.2 call get_inner_reference.  */
1597       /* Find the base and the offset from it.  */
1598       base = get_inner_reference (memref, &pbitsize, &pbitpos, &poffset,
1599                                   &pmode, &punsignedp, &pvolatilep, false);
1600       if (!base)
1601         {
1602           if (dump_file && (dump_flags & TDF_DETAILS))
1603             {
1604               fprintf (dump_file, "\nfailed to get inner ref for ");
1605               print_generic_expr (dump_file, memref, TDF_SLIM);
1606               fprintf (dump_file, "\n");
1607             }
1608           return NULL_TREE;
1609         }
1610
1611       /* 1.2.1 analyze offset expr received from get_inner_reference.  */
1612       if (poffset
1613           && !analyze_offset_expr (poffset, loop, &object_offset,
1614                                    &object_misalign, &object_aligned_to,
1615                                    &object_step))
1616         {
1617           if (dump_file && (dump_flags & TDF_DETAILS))
1618             {
1619               fprintf (dump_file, "\nfailed to compute offset or step for ");
1620               print_generic_expr (dump_file, memref, TDF_SLIM);
1621               fprintf (dump_file, "\n");
1622             }
1623           return NULL_TREE;
1624         }
1625
1626       /* Add bit position to OFFSET and MISALIGN.  */
1627
1628       bit_pos_in_bytes = ssize_int (pbitpos/BITS_PER_UNIT);
1629       /* Check that there is no remainder in bits.  */
1630       if (pbitpos%BITS_PER_UNIT)
1631         {
1632           if (dump_file && (dump_flags & TDF_DETAILS))
1633             fprintf (dump_file, "\nbit offset alignment.\n");
1634           return NULL_TREE;
1635         }
1636       object_offset = size_binop (PLUS_EXPR, bit_pos_in_bytes, object_offset);
1637       if (object_misalign)
1638         object_misalign = size_binop (PLUS_EXPR, object_misalign,
1639                                       bit_pos_in_bytes);
1640
1641       memref = base; /* To continue analysis of BASE.  */
1642       /* fall through  */
1643     }
1644
1645   /*  Part 1: Case 2. Declarations.  */
1646   if (DECL_P (memref))
1647     {
1648       /* We expect to get a decl only if we already have a DR, or with
1649          COMPONENT_REFs of type 'a[i].b'.  */
1650       if (!(*dr))
1651         {
1652           if (comp_ref && TREE_CODE (TREE_OPERAND (comp_ref, 0)) == ARRAY_REF)
1653             {
1654               *dr = init_array_ref (stmt, TREE_OPERAND (comp_ref, 0), is_read);
1655               if (DR_NUM_DIMENSIONS (*dr) != 1)
1656                 {
1657                   if (dump_file && (dump_flags & TDF_DETAILS))
1658                     {
1659                       fprintf (dump_file, "\n multidimensional component ref ");
1660                       print_generic_expr (dump_file, comp_ref, TDF_SLIM);
1661                       fprintf (dump_file, "\n");
1662                     }
1663                   return NULL_TREE;
1664                 }
1665             }
1666           else
1667             {
1668               if (dump_file && (dump_flags & TDF_DETAILS))
1669                 {
1670                   fprintf (dump_file, "\nunhandled decl ");
1671                   print_generic_expr (dump_file, memref, TDF_SLIM);
1672                   fprintf (dump_file, "\n");
1673                 }
1674               return NULL_TREE;
1675             }
1676         }
1677
1678       /* TODO: if during the analysis of INDIRECT_REF we get to an object, put
1679          the object in BASE_OBJECT field if we can prove that this is O.K.,
1680          i.e., the data-ref access is bounded by the bounds of the BASE_OBJECT.
1681          (e.g., if the object is an array base 'a', where 'a[N]', we must prove
1682          that every access with 'p' (the original INDIRECT_REF based on '&a')
1683          in the loop is within the array boundaries - from a[0] to a[N-1]).
1684          Otherwise, our alias analysis can be incorrect.
1685          Even if an access function based on BASE_OBJECT can't be build, update
1686          BASE_OBJECT field to enable us to prove that two data-refs are
1687          different (without access function, distance analysis is impossible).
1688       */
1689      if (SSA_VAR_P (memref) && var_can_have_subvars (memref))
1690         *subvars = get_subvars_for_var (memref);
1691       base_address = build_fold_addr_expr (memref);
1692       /* 2.1 set MEMTAG.  */
1693       *memtag = memref;
1694     }
1695
1696   /* Part 1:  Case 3. INDIRECT_REFs.  */
1697   else if (TREE_CODE (memref) == INDIRECT_REF)
1698     {
1699       tree ptr_ref = TREE_OPERAND (memref, 0);
1700       if (TREE_CODE (ptr_ref) == SSA_NAME)
1701         *ptr_info = SSA_NAME_PTR_INFO (ptr_ref);
1702
1703       /* 3.1 build data-reference structure for MEMREF.  */
1704       ptr_dr = analyze_indirect_ref (stmt, memref, is_read);
1705       if (!ptr_dr)
1706         {
1707           if (dump_file && (dump_flags & TDF_DETAILS))
1708             {
1709               fprintf (dump_file, "\nfailed to create dr for ");
1710               print_generic_expr (dump_file, memref, TDF_SLIM);
1711               fprintf (dump_file, "\n");
1712             }
1713           return NULL_TREE;
1714         }
1715
1716       /* 3.2 analyze evolution and initial condition of MEMREF.  */
1717       ptr_step = DR_STEP (ptr_dr);
1718       ptr_init = DR_BASE_ADDRESS (ptr_dr);
1719       if (!ptr_init || !ptr_step || !POINTER_TYPE_P (TREE_TYPE (ptr_init)))
1720         {
1721           *dr = (*dr) ? *dr : ptr_dr;
1722           if (dump_file && (dump_flags & TDF_DETAILS))
1723             {
1724               fprintf (dump_file, "\nbad pointer access ");
1725               print_generic_expr (dump_file, memref, TDF_SLIM);
1726               fprintf (dump_file, "\n");
1727             }
1728           return NULL_TREE;
1729         }
1730
1731       if (integer_zerop (ptr_step) && !(*dr))
1732         {
1733           if (dump_file && (dump_flags & TDF_DETAILS))
1734             fprintf (dump_file, "\nptr is loop invariant.\n");
1735           *dr = ptr_dr;
1736           return NULL_TREE;
1737
1738           /* If there exists DR for MEMREF, we are analyzing the base of
1739              handled component (PTR_INIT), which not necessary has evolution in
1740              the loop.  */
1741         }
1742       object_step = size_binop (PLUS_EXPR, object_step, ptr_step);
1743
1744       /* 3.3 set data-reference structure for MEMREF.  */
1745       if (!*dr)
1746         *dr = ptr_dr;
1747
1748       /* 3.4 call address_analysis to analyze INIT of the access
1749          function.  */
1750       base_address = address_analysis (ptr_init, stmt, is_read, *dr,
1751                                        &address_offset, &address_misalign,
1752                                        &address_aligned_to, &address_step);
1753       if (!base_address)
1754         {
1755           if (dump_file && (dump_flags & TDF_DETAILS))
1756             {
1757               fprintf (dump_file, "\nfailed to analyze address ");
1758               print_generic_expr (dump_file, ptr_init, TDF_SLIM);
1759               fprintf (dump_file, "\n");
1760             }
1761           return NULL_TREE;
1762         }
1763
1764       /* 3.5 extract memory tag.  */
1765       switch (TREE_CODE (base_address))
1766         {
1767         case SSA_NAME:
1768           *memtag = symbol_mem_tag (SSA_NAME_VAR (base_address));
1769           if (!(*memtag) && TREE_CODE (TREE_OPERAND (memref, 0)) == SSA_NAME)
1770             *memtag = symbol_mem_tag (SSA_NAME_VAR (TREE_OPERAND (memref, 0)));
1771           break;
1772         case ADDR_EXPR:
1773           *memtag = TREE_OPERAND (base_address, 0);
1774           break;
1775         default:
1776           if (dump_file && (dump_flags & TDF_DETAILS))
1777             {
1778               fprintf (dump_file, "\nno memtag for ");
1779               print_generic_expr (dump_file, memref, TDF_SLIM);
1780               fprintf (dump_file, "\n");
1781             }
1782           *memtag = NULL_TREE;
1783           break;
1784         }
1785     }
1786
1787   if (!base_address)
1788     {
1789       /* MEMREF cannot be analyzed.  */
1790       if (dump_file && (dump_flags & TDF_DETAILS))
1791         {
1792           fprintf (dump_file, "\ndata-ref of unsupported type ");
1793           print_generic_expr (dump_file, memref, TDF_SLIM);
1794           fprintf (dump_file, "\n");
1795         }
1796       return NULL_TREE;
1797     }
1798
1799   if (comp_ref)
1800     DR_REF (*dr) = comp_ref;
1801
1802   if (SSA_VAR_P (*memtag) && var_can_have_subvars (*memtag))
1803     *subvars = get_subvars_for_var (*memtag);
1804
1805   /* Part 2: Combine the results of object and address analysis to calculate
1806      INITIAL_OFFSET, STEP and misalignment info.  */
1807   *offset = size_binop (PLUS_EXPR, object_offset, address_offset);
1808
1809   if ((!object_misalign && !object_aligned_to)
1810       || (!address_misalign && !address_aligned_to))
1811     {
1812       *misalign = NULL_TREE;
1813       *aligned_to = NULL_TREE;
1814     }
1815   else
1816     {
1817       if (object_misalign && address_misalign)
1818         *misalign = size_binop (PLUS_EXPR, object_misalign, address_misalign);
1819       else
1820         *misalign = object_misalign ? object_misalign : address_misalign;
1821       if (object_aligned_to && address_aligned_to)
1822         *aligned_to = size_binop (MIN_EXPR, object_aligned_to,
1823                                   address_aligned_to);
1824       else
1825         *aligned_to = object_aligned_to ?
1826           object_aligned_to : address_aligned_to;
1827     }
1828   *step = size_binop (PLUS_EXPR, object_step, address_step);
1829
1830   return base_address;
1831 }
1832
1833 /* Function analyze_offset.
1834
1835    Extract INVARIANT and CONSTANT parts from OFFSET.
1836
1837 */
1838 static bool
1839 analyze_offset (tree offset, tree *invariant, tree *constant)
1840 {
1841   tree op0, op1, constant_0, constant_1, invariant_0, invariant_1;
1842   enum tree_code code = TREE_CODE (offset);
1843
1844   *invariant = NULL_TREE;
1845   *constant = NULL_TREE;
1846
1847   /* Not PLUS/MINUS expression - recursion stop condition.  */
1848   if (code != PLUS_EXPR && code != MINUS_EXPR)
1849     {
1850       if (TREE_CODE (offset) == INTEGER_CST)
1851         *constant = offset;
1852       else
1853         *invariant = offset;
1854       return true;
1855     }
1856
1857   op0 = TREE_OPERAND (offset, 0);
1858   op1 = TREE_OPERAND (offset, 1);
1859
1860   /* Recursive call with the operands.  */
1861   if (!analyze_offset (op0, &invariant_0, &constant_0)
1862       || !analyze_offset (op1, &invariant_1, &constant_1))
1863     return false;
1864
1865   /* Combine the results. Add negation to the subtrahend in case of
1866      subtraction.  */
1867   if (constant_0 && constant_1)
1868     return false;
1869   *constant = constant_0 ? constant_0 : constant_1;
1870   if (code == MINUS_EXPR && constant_1)
1871     *constant = fold_build1 (NEGATE_EXPR, TREE_TYPE (*constant), *constant);
1872
1873   if (invariant_0 && invariant_1)
1874     *invariant =
1875       fold_build2 (code, TREE_TYPE (invariant_0), invariant_0, invariant_1);
1876   else
1877     {
1878       *invariant = invariant_0 ? invariant_0 : invariant_1;
1879       if (code == MINUS_EXPR && invariant_1)
1880         *invariant =
1881            fold_build1 (NEGATE_EXPR, TREE_TYPE (*invariant), *invariant);
1882     }
1883   return true;
1884 }
1885
1886 /* Free the memory used by the data reference DR.  */
1887
1888 static void
1889 free_data_ref (data_reference_p dr)
1890 {
1891   DR_FREE_ACCESS_FNS (dr);
1892   free (dr);
1893 }
1894
1895 /* Function create_data_ref.
1896
1897    Create a data-reference structure for MEMREF. Set its DR_BASE_ADDRESS,
1898    DR_OFFSET, DR_INIT, DR_STEP, DR_OFFSET_MISALIGNMENT, DR_ALIGNED_TO,
1899    DR_MEMTAG, and DR_POINTSTO_INFO fields.
1900
1901    Input:
1902    MEMREF - the memory reference that is being analyzed
1903    STMT - the statement that contains MEMREF
1904    IS_READ - TRUE if STMT reads from MEMREF, FALSE if writes to MEMREF
1905
1906    Output:
1907    DR (returned value) - data_reference struct for MEMREF
1908 */
1909
1910 static struct data_reference *
1911 create_data_ref (tree memref, tree stmt, bool is_read)
1912 {
1913   struct data_reference *dr = NULL;
1914   tree base_address, offset, step, misalign, memtag;
1915   struct loop *loop = loop_containing_stmt (stmt);
1916   tree invariant = NULL_TREE, constant = NULL_TREE;
1917   tree type_size, init_cond;
1918   struct ptr_info_def *ptr_info;
1919   subvar_t subvars = NULL;
1920   tree aligned_to, type = NULL_TREE, orig_offset;
1921
1922   if (!memref)
1923     return NULL;
1924
1925   base_address = object_analysis (memref, stmt, is_read, &dr, &offset,
1926                                   &misalign, &aligned_to, &step, &memtag,
1927                                   &ptr_info, &subvars);
1928   if (!dr || !base_address)
1929     {
1930       if (dump_file && (dump_flags & TDF_DETAILS))
1931         {
1932           fprintf (dump_file, "\ncreate_data_ref: failed to create a dr for ");
1933           print_generic_expr (dump_file, memref, TDF_SLIM);
1934           fprintf (dump_file, "\n");
1935         }
1936       return NULL;
1937     }
1938
1939   DR_BASE_ADDRESS (dr) = base_address;
1940   DR_OFFSET (dr) = offset;
1941   DR_INIT (dr) = ssize_int (0);
1942   DR_STEP (dr) = step;
1943   DR_OFFSET_MISALIGNMENT (dr) = misalign;
1944   DR_ALIGNED_TO (dr) = aligned_to;
1945   DR_MEMTAG (dr) = memtag;
1946   DR_PTR_INFO (dr) = ptr_info;
1947   DR_SUBVARS (dr) = subvars;
1948
1949   type_size = fold_convert (ssizetype, TYPE_SIZE_UNIT (TREE_TYPE (DR_REF (dr))));
1950
1951   /* Extract CONSTANT and INVARIANT from OFFSET.  */
1952   /* Remove cast from OFFSET and restore it for INVARIANT part.  */
1953   orig_offset = offset;
1954   STRIP_NOPS (offset);
1955   if (offset != orig_offset)
1956     type = TREE_TYPE (orig_offset);
1957   if (!analyze_offset (offset, &invariant, &constant))
1958     {
1959       if (dump_file && (dump_flags & TDF_DETAILS))
1960         {
1961           fprintf (dump_file, "\ncreate_data_ref: failed to analyze dr's");
1962           fprintf (dump_file, " offset for ");
1963           print_generic_expr (dump_file, memref, TDF_SLIM);
1964           fprintf (dump_file, "\n");
1965         }
1966       return NULL;
1967     }
1968   if (type && invariant)
1969     invariant = fold_convert (type, invariant);
1970
1971   /* Put CONSTANT part of OFFSET in DR_INIT and INVARIANT in DR_OFFSET field
1972      of DR.  */
1973   if (constant)
1974     {
1975       DR_INIT (dr) = fold_convert (ssizetype, constant);
1976       init_cond = fold_build2 (TRUNC_DIV_EXPR, TREE_TYPE (constant),
1977                                constant, type_size);
1978     }
1979   else
1980     DR_INIT (dr) = init_cond = ssize_int (0);
1981
1982   if (invariant)
1983     DR_OFFSET (dr) = invariant;
1984   else
1985     DR_OFFSET (dr) = ssize_int (0);
1986
1987   /* Change the access function for INIDIRECT_REFs, according to
1988      DR_BASE_ADDRESS.  Analyze OFFSET calculated in object_analysis. OFFSET is
1989      an expression that can contain loop invariant expressions and constants.
1990      We put the constant part in the initial condition of the access function
1991      (for data dependence tests), and in DR_INIT of the data-ref. The loop
1992      invariant part is put in DR_OFFSET.
1993      The evolution part of the access function is STEP calculated in
1994      object_analysis divided by the size of data type.
1995   */
1996   if (!DR_BASE_OBJECT (dr)
1997       || (TREE_CODE (memref) == COMPONENT_REF && DR_NUM_DIMENSIONS (dr) == 1))
1998     {
1999       tree access_fn;
2000       tree new_step;
2001
2002       /* Update access function.  */
2003       access_fn = DR_ACCESS_FN (dr, 0);
2004       if (automatically_generated_chrec_p (access_fn))
2005         {
2006           free_data_ref (dr);
2007           return NULL;
2008         }
2009
2010       new_step = size_binop (TRUNC_DIV_EXPR,
2011                              fold_convert (ssizetype, step), type_size);
2012
2013       init_cond = chrec_convert (chrec_type (access_fn), init_cond, stmt);
2014       new_step = chrec_convert (chrec_type (access_fn), new_step, stmt);
2015       if (automatically_generated_chrec_p (init_cond)
2016           || automatically_generated_chrec_p (new_step))
2017         {
2018           free_data_ref (dr);
2019           return NULL;
2020         }
2021       access_fn = chrec_replace_initial_condition (access_fn, init_cond);
2022       access_fn = reset_evolution_in_loop (loop->num, access_fn, new_step);
2023
2024       VEC_replace (tree, DR_ACCESS_FNS (dr), 0, access_fn);
2025     }
2026
2027   if (dump_file && (dump_flags & TDF_DETAILS))
2028     {
2029       struct ptr_info_def *pi = DR_PTR_INFO (dr);
2030
2031       fprintf (dump_file, "\nCreated dr for ");
2032       print_generic_expr (dump_file, memref, TDF_SLIM);
2033       fprintf (dump_file, "\n\tbase_address: ");
2034       print_generic_expr (dump_file, DR_BASE_ADDRESS (dr), TDF_SLIM);
2035       fprintf (dump_file, "\n\toffset from base address: ");
2036       print_generic_expr (dump_file, DR_OFFSET (dr), TDF_SLIM);
2037       fprintf (dump_file, "\n\tconstant offset from base address: ");
2038       print_generic_expr (dump_file, DR_INIT (dr), TDF_SLIM);
2039       fprintf (dump_file, "\n\tbase_object: ");
2040       print_generic_expr (dump_file, DR_BASE_OBJECT (dr), TDF_SLIM);
2041       fprintf (dump_file, "\n\tstep: ");
2042       print_generic_expr (dump_file, DR_STEP (dr), TDF_SLIM);
2043       fprintf (dump_file, "B\n\tmisalignment from base: ");
2044       print_generic_expr (dump_file, DR_OFFSET_MISALIGNMENT (dr), TDF_SLIM);
2045       if (DR_OFFSET_MISALIGNMENT (dr))
2046         fprintf (dump_file, "B");
2047       if (DR_ALIGNED_TO (dr))
2048         {
2049           fprintf (dump_file, "\n\taligned to: ");
2050           print_generic_expr (dump_file, DR_ALIGNED_TO (dr), TDF_SLIM);
2051         }
2052       fprintf (dump_file, "\n\tmemtag: ");
2053       print_generic_expr (dump_file, DR_MEMTAG (dr), TDF_SLIM);
2054       fprintf (dump_file, "\n");
2055       if (pi && pi->name_mem_tag)
2056         {
2057           fprintf (dump_file, "\n\tnametag: ");
2058           print_generic_expr (dump_file, pi->name_mem_tag, TDF_SLIM);
2059           fprintf (dump_file, "\n");
2060         }
2061     }
2062   return dr;
2063 }
2064
2065 /* Returns true if FNA == FNB.  */
2066
2067 static bool
2068 affine_function_equal_p (affine_fn fna, affine_fn fnb)
2069 {
2070   unsigned i, n = VEC_length (tree, fna);
2071
2072   gcc_assert (n == VEC_length (tree, fnb));
2073
2074   for (i = 0; i < n; i++)
2075     if (!operand_equal_p (VEC_index (tree, fna, i),
2076                           VEC_index (tree, fnb, i), 0))
2077       return false;
2078
2079   return true;
2080 }
2081
2082 /* If all the functions in CF are the same, returns one of them,
2083    otherwise returns NULL.  */
2084
2085 static affine_fn
2086 common_affine_function (conflict_function *cf)
2087 {
2088   unsigned i;
2089   affine_fn comm;
2090
2091   if (!CF_NONTRIVIAL_P (cf))
2092     return NULL;
2093
2094   comm = cf->fns[0];
2095
2096   for (i = 1; i < cf->n; i++)
2097     if (!affine_function_equal_p (comm, cf->fns[i]))
2098       return NULL;
2099
2100   return comm;
2101 }
2102
2103 /* Returns the base of the affine function FN.  */
2104
2105 static tree
2106 affine_function_base (affine_fn fn)
2107 {
2108   return VEC_index (tree, fn, 0);
2109 }
2110
2111 /* Returns true if FN is a constant.  */
2112
2113 static bool
2114 affine_function_constant_p (affine_fn fn)
2115 {
2116   unsigned i;
2117   tree coef;
2118
2119   for (i = 1; VEC_iterate (tree, fn, i, coef); i++)
2120     if (!integer_zerop (coef))
2121       return false;
2122
2123   return true;
2124 }
2125
2126 /* Applies operation OP on affine functions FNA and FNB, and returns the
2127    result.  */
2128
2129 static affine_fn
2130 affine_fn_op (enum tree_code op, affine_fn fna, affine_fn fnb)
2131 {
2132   unsigned i, n, m;
2133   affine_fn ret;
2134   tree coef;
2135
2136   if (VEC_length (tree, fnb) > VEC_length (tree, fna))
2137     {
2138       n = VEC_length (tree, fna);
2139       m = VEC_length (tree, fnb);
2140     }
2141   else
2142     {
2143       n = VEC_length (tree, fnb);
2144       m = VEC_length (tree, fna);
2145     }
2146
2147   ret = VEC_alloc (tree, heap, m);
2148   for (i = 0; i < n; i++)
2149     VEC_quick_push (tree, ret,
2150                     fold_build2 (op, integer_type_node,
2151                                  VEC_index (tree, fna, i),
2152                                  VEC_index (tree, fnb, i)));
2153
2154   for (; VEC_iterate (tree, fna, i, coef); i++)
2155     VEC_quick_push (tree, ret,
2156                     fold_build2 (op, integer_type_node,
2157                                  coef, integer_zero_node));
2158   for (; VEC_iterate (tree, fnb, i, coef); i++)
2159     VEC_quick_push (tree, ret,
2160                     fold_build2 (op, integer_type_node,
2161                                  integer_zero_node, coef));
2162
2163   return ret;
2164 }
2165
2166 /* Returns the sum of affine functions FNA and FNB.  */
2167
2168 static affine_fn
2169 affine_fn_plus (affine_fn fna, affine_fn fnb)
2170 {
2171   return affine_fn_op (PLUS_EXPR, fna, fnb);
2172 }
2173
2174 /* Returns the difference of affine functions FNA and FNB.  */
2175
2176 static affine_fn
2177 affine_fn_minus (affine_fn fna, affine_fn fnb)
2178 {
2179   return affine_fn_op (MINUS_EXPR, fna, fnb);
2180 }
2181
2182 /* Frees affine function FN.  */
2183
2184 static void
2185 affine_fn_free (affine_fn fn)
2186 {
2187   VEC_free (tree, heap, fn);
2188 }
2189
2190 /* Determine for each subscript in the data dependence relation DDR
2191    the distance.  */
2192
2193 static void
2194 compute_subscript_distance (struct data_dependence_relation *ddr)
2195 {
2196   conflict_function *cf_a, *cf_b;
2197   affine_fn fn_a, fn_b, diff;
2198
2199   if (DDR_ARE_DEPENDENT (ddr) == NULL_TREE)
2200     {
2201       unsigned int i;
2202
2203       for (i = 0; i < DDR_NUM_SUBSCRIPTS (ddr); i++)
2204         {
2205           struct subscript *subscript;
2206
2207           subscript = DDR_SUBSCRIPT (ddr, i);
2208           cf_a = SUB_CONFLICTS_IN_A (subscript);
2209           cf_b = SUB_CONFLICTS_IN_B (subscript);
2210
2211           fn_a = common_affine_function (cf_a);
2212           fn_b = common_affine_function (cf_b);
2213           if (!fn_a || !fn_b)
2214             {
2215               SUB_DISTANCE (subscript) = chrec_dont_know;
2216               return;
2217             }
2218           diff = affine_fn_minus (fn_a, fn_b);
2219
2220           if (affine_function_constant_p (diff))
2221             SUB_DISTANCE (subscript) = affine_function_base (diff);
2222           else
2223             SUB_DISTANCE (subscript) = chrec_dont_know;
2224
2225           affine_fn_free (diff);
2226         }
2227     }
2228 }
2229
2230 /* Returns the conflict function for "unknown".  */
2231
2232 static conflict_function *
2233 conflict_fn_not_known (void)
2234 {
2235   conflict_function *fn = XCNEW (conflict_function);
2236   fn->n = NOT_KNOWN;
2237
2238   return fn;
2239 }
2240
2241 /* Returns the conflict function for "independent".  */
2242
2243 static conflict_function *
2244 conflict_fn_no_dependence (void)
2245 {
2246   conflict_function *fn = XCNEW (conflict_function);
2247   fn->n = NO_DEPENDENCE;
2248
2249   return fn;
2250 }
2251
2252 /* Initialize a data dependence relation between data accesses A and
2253    B.  NB_LOOPS is the number of loops surrounding the references: the
2254    size of the classic distance/direction vectors.  */
2255
2256 static struct data_dependence_relation *
2257 initialize_data_dependence_relation (struct data_reference *a,
2258                                      struct data_reference *b,
2259                                      VEC (loop_p, heap) *loop_nest)
2260 {
2261   struct data_dependence_relation *res;
2262   bool differ_p, known_dependence;
2263   unsigned int i;
2264
2265   res = XNEW (struct data_dependence_relation);
2266   DDR_A (res) = a;
2267   DDR_B (res) = b;
2268   DDR_LOOP_NEST (res) = NULL;
2269
2270   if (a == NULL || b == NULL)
2271     {
2272       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2273       return res;
2274     }
2275
2276   /* When A and B are arrays and their dimensions differ, we directly
2277      initialize the relation to "there is no dependence": chrec_known.  */
2278   if (DR_BASE_OBJECT (a) && DR_BASE_OBJECT (b)
2279       && DR_NUM_DIMENSIONS (a) != DR_NUM_DIMENSIONS (b))
2280     {
2281       DDR_ARE_DEPENDENT (res) = chrec_known;
2282       return res;
2283     }
2284
2285   if (DR_BASE_ADDRESS (a) && DR_BASE_ADDRESS (b))
2286     known_dependence = base_addr_differ_p (a, b, &differ_p);
2287   else
2288     known_dependence = base_object_differ_p (a, b, &differ_p);
2289
2290   if (!known_dependence)
2291     {
2292       /* Can't determine whether the data-refs access the same memory
2293          region.  */
2294       DDR_ARE_DEPENDENT (res) = chrec_dont_know;
2295       return res;
2296     }
2297
2298   if (differ_p)
2299     {
2300       DDR_ARE_DEPENDENT (res) = chrec_known;
2301       return res;
2302     }
2303
2304   DDR_AFFINE_P (res) = true;
2305   DDR_ARE_DEPENDENT (res) = NULL_TREE;
2306   DDR_SUBSCRIPTS (res) = VEC_alloc (subscript_p, heap, DR_NUM_DIMENSIONS (a));
2307   DDR_LOOP_NEST (res) = loop_nest;
2308   DDR_INNER_LOOP (res) = 0;
2309   DDR_DIR_VECTS (res) = NULL;
2310   DDR_DIST_VECTS (res) = NULL;
2311
2312   for (i = 0; i < DR_NUM_DIMENSIONS (a); i++)
2313     {
2314       struct subscript *subscript;
2315
2316       subscript = XNEW (struct subscript);
2317       SUB_CONFLICTS_IN_A (subscript) = conflict_fn_not_known ();
2318       SUB_CONFLICTS_IN_B (subscript) = conflict_fn_not_known ();
2319       SUB_LAST_CONFLICT (subscript) = chrec_dont_know;
2320       SUB_DISTANCE (subscript) = chrec_dont_know;
2321       VEC_safe_push (subscript_p, heap, DDR_SUBSCRIPTS (res), subscript);
2322     }
2323
2324   return res;
2325 }
2326
2327 /* Frees memory used by the conflict function F.  */
2328
2329 static void
2330 free_conflict_function (conflict_function *f)
2331 {
2332   unsigned i;
2333
2334   if (CF_NONTRIVIAL_P (f))
2335     {
2336       for (i = 0; i < f->n; i++)
2337         affine_fn_free (f->fns[i]);
2338     }
2339   free (f);
2340 }
2341
2342 /* Frees memory used by SUBSCRIPTS.  */
2343
2344 static void
2345 free_subscripts (VEC (subscript_p, heap) *subscripts)
2346 {
2347   unsigned i;
2348   subscript_p s;
2349
2350   for (i = 0; VEC_iterate (subscript_p, subscripts, i, s); i++)
2351     {
2352       free_conflict_function (s->conflicting_iterations_in_a);
2353       free_conflict_function (s->conflicting_iterations_in_b);
2354     }
2355   VEC_free (subscript_p, heap, subscripts);
2356 }
2357
2358 /* Set DDR_ARE_DEPENDENT to CHREC and finalize the subscript overlap
2359    description.  */
2360
2361 static inline void
2362 finalize_ddr_dependent (struct data_dependence_relation *ddr,
2363                         tree chrec)
2364 {
2365   if (dump_file && (dump_flags & TDF_DETAILS))
2366     {
2367       fprintf (dump_file, "(dependence classified: ");
2368       print_generic_expr (dump_file, chrec, 0);
2369       fprintf (dump_file, ")\n");
2370     }
2371
2372   DDR_ARE_DEPENDENT (ddr) = chrec;
2373   free_subscripts (DDR_SUBSCRIPTS (ddr));
2374 }
2375
2376 /* The dependence relation DDR cannot be represented by a distance
2377    vector.  */
2378
2379 static inline void
2380 non_affine_dependence_relation (struct data_dependence_relation *ddr)
2381 {
2382   if (dump_file && (dump_flags & TDF_DETAILS))
2383     fprintf (dump_file, "(Dependence relation cannot be represented by distance vector.) \n");
2384
2385   DDR_AFFINE_P (ddr) = false;
2386 }
2387
2388 \f
2389
2390 /* This section contains the classic Banerjee tests.  */
2391
2392 /* Returns true iff CHREC_A and CHREC_B are not dependent on any index
2393    variables, i.e., if the ZIV (Zero Index Variable) test is true.  */
2394
2395 static inline bool
2396 ziv_subscript_p (tree chrec_a,
2397                  tree chrec_b)
2398 {
2399   return (evolution_function_is_constant_p (chrec_a)
2400           && evolution_function_is_constant_p (chrec_b));
2401 }
2402
2403 /* Returns true iff CHREC_A and CHREC_B are dependent on an index
2404    variable, i.e., if the SIV (Single Index Variable) test is true.  */
2405
2406 static bool
2407 siv_subscript_p (tree chrec_a,
2408                  tree chrec_b)
2409 {
2410   if ((evolution_function_is_constant_p (chrec_a)
2411        && evolution_function_is_univariate_p (chrec_b))
2412       || (evolution_function_is_constant_p (chrec_b)
2413           && evolution_function_is_univariate_p (chrec_a)))
2414     return true;
2415
2416   if (evolution_function_is_univariate_p (chrec_a)
2417       && evolution_function_is_univariate_p (chrec_b))
2418     {
2419       switch (TREE_CODE (chrec_a))
2420         {
2421         case POLYNOMIAL_CHREC:
2422           switch (TREE_CODE (chrec_b))
2423             {
2424             case POLYNOMIAL_CHREC:
2425               if (CHREC_VARIABLE (chrec_a) != CHREC_VARIABLE (chrec_b))
2426                 return false;
2427
2428             default:
2429               return true;
2430             }
2431
2432         default:
2433           return true;
2434         }
2435     }
2436
2437   return false;
2438 }
2439
2440 /* Creates a conflict function with N dimensions.  The affine functions
2441    in each dimension follow.  */
2442
2443 static conflict_function *
2444 conflict_fn (unsigned n, ...)
2445 {
2446   unsigned i;
2447   conflict_function *ret = XCNEW (conflict_function);
2448   va_list ap;
2449
2450   gcc_assert (0 < n && n <= MAX_DIM);
2451   va_start(ap, n);
2452
2453   ret->n = n;
2454   for (i = 0; i < n; i++)
2455     ret->fns[i] = va_arg (ap, affine_fn);
2456   va_end(ap);
2457
2458   return ret;
2459 }
2460
2461 /* Returns constant affine function with value CST.  */
2462
2463 static affine_fn
2464 affine_fn_cst (tree cst)
2465 {
2466   affine_fn fn = VEC_alloc (tree, heap, 1);
2467   VEC_quick_push (tree, fn, cst);
2468   return fn;
2469 }
2470
2471 /* Returns affine function with single variable, CST + COEF * x_DIM.  */
2472
2473 static affine_fn
2474 affine_fn_univar (tree cst, unsigned dim, tree coef)
2475 {
2476   affine_fn fn = VEC_alloc (tree, heap, dim + 1);
2477   unsigned i;
2478
2479   gcc_assert (dim > 0);
2480   VEC_quick_push (tree, fn, cst);
2481   for (i = 1; i < dim; i++)
2482     VEC_quick_push (tree, fn, integer_zero_node);
2483   VEC_quick_push (tree, fn, coef);
2484   return fn;
2485 }
2486
2487 /* Analyze a ZIV (Zero Index Variable) subscript.  *OVERLAPS_A and
2488    *OVERLAPS_B are initialized to the functions that describe the
2489    relation between the elements accessed twice by CHREC_A and
2490    CHREC_B.  For k >= 0, the following property is verified:
2491
2492    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2493
2494 static void
2495 analyze_ziv_subscript (tree chrec_a,
2496                        tree chrec_b,
2497                        conflict_function **overlaps_a,
2498                        conflict_function **overlaps_b,
2499                        tree *last_conflicts)
2500 {
2501   tree difference;
2502   dependence_stats.num_ziv++;
2503
2504   if (dump_file && (dump_flags & TDF_DETAILS))
2505     fprintf (dump_file, "(analyze_ziv_subscript \n");
2506
2507   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2508   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2509   difference = chrec_fold_minus (integer_type_node, chrec_a, chrec_b);
2510
2511   switch (TREE_CODE (difference))
2512     {
2513     case INTEGER_CST:
2514       if (integer_zerop (difference))
2515         {
2516           /* The difference is equal to zero: the accessed index
2517              overlaps for each iteration in the loop.  */
2518           *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2519           *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
2520           *last_conflicts = chrec_dont_know;
2521           dependence_stats.num_ziv_dependent++;
2522         }
2523       else
2524         {
2525           /* The accesses do not overlap.  */
2526           *overlaps_a = conflict_fn_no_dependence ();
2527           *overlaps_b = conflict_fn_no_dependence ();
2528           *last_conflicts = integer_zero_node;
2529           dependence_stats.num_ziv_independent++;
2530         }
2531       break;
2532
2533     default:
2534       /* We're not sure whether the indexes overlap.  For the moment,
2535          conservatively answer "don't know".  */
2536       if (dump_file && (dump_flags & TDF_DETAILS))
2537         fprintf (dump_file, "ziv test failed: difference is non-integer.\n");
2538
2539       *overlaps_a = conflict_fn_not_known ();
2540       *overlaps_b = conflict_fn_not_known ();
2541       *last_conflicts = chrec_dont_know;
2542       dependence_stats.num_ziv_unimplemented++;
2543       break;
2544     }
2545
2546   if (dump_file && (dump_flags & TDF_DETAILS))
2547     fprintf (dump_file, ")\n");
2548 }
2549
2550 /* Sets NIT to the estimated number of executions of the statements in
2551    LOOP.  If CONSERVATIVE is true, we must be sure that NIT is at least as
2552    large as the number of iterations.  If we have no reliable estimate,
2553    the function returns false, otherwise returns true.  */
2554
2555 static bool
2556 estimated_loop_iterations (struct loop *loop, bool conservative,
2557                            double_int *nit)
2558 {
2559   tree numiter = number_of_exit_cond_executions (loop);
2560
2561   /* If we have an exact value, use it.  */
2562   if (TREE_CODE (numiter) == INTEGER_CST)
2563     {
2564       *nit = tree_to_double_int (numiter);
2565       return true;
2566     }
2567
2568   /* If we have a measured profile and we do not ask for a conservative bound,
2569      use it.  */
2570   if (!conservative && loop->header->count != 0)
2571     {
2572       *nit = uhwi_to_double_int (expected_loop_iterations (loop) + 1);
2573       return true;
2574     }
2575
2576   /* Finally, try using a reliable estimate on number of iterations according
2577      to the size of the accessed data, if available.  */
2578   estimate_numbers_of_iterations_loop (loop);
2579   if (loop->estimate_state == EST_AVAILABLE)
2580     {
2581       *nit = loop->estimated_nb_iterations;
2582       return true;
2583     }
2584
2585   return false;
2586 }
2587
2588 /* Similar to estimated_loop_iterations, but returns the estimate only
2589    if it fits to HOST_WIDE_INT.  If this is not the case, or the estimate
2590    on the number of iterations of LOOP could not be derived, returns -1.  */
2591
2592 HOST_WIDE_INT
2593 estimated_loop_iterations_int (struct loop *loop, bool conservative)
2594 {
2595   double_int nit;
2596   HOST_WIDE_INT hwi_nit;
2597
2598   if (!estimated_loop_iterations (loop, conservative, &nit))
2599     return -1;
2600
2601   if (!double_int_fits_in_shwi_p (nit))
2602     return -1;
2603   hwi_nit = double_int_to_shwi (nit);
2604
2605   return hwi_nit < 0 ? -1 : hwi_nit;
2606 }
2607
2608 /* Similar to estimated_loop_iterations, but returns the estimate as a tree,
2609    and only if it fits to the int type.  If this is not the case, or the
2610    estimate on the number of iterations of LOOP could not be derived, returns
2611    chrec_dont_know.  */
2612
2613 static tree
2614 estimated_loop_iterations_tree (struct loop *loop, bool conservative)
2615 {
2616   double_int nit;
2617   tree type;
2618
2619   if (!estimated_loop_iterations (loop, conservative, &nit))
2620     return chrec_dont_know;
2621
2622   type = lang_hooks.types.type_for_size (INT_TYPE_SIZE, true);
2623   if (!double_int_fits_to_tree_p (type, nit))
2624     return chrec_dont_know;
2625
2626   return double_int_to_tree (type, nit);
2627 }
2628
2629 /* Analyze a SIV (Single Index Variable) subscript where CHREC_A is a
2630    constant, and CHREC_B is an affine function.  *OVERLAPS_A and
2631    *OVERLAPS_B are initialized to the functions that describe the
2632    relation between the elements accessed twice by CHREC_A and
2633    CHREC_B.  For k >= 0, the following property is verified:
2634
2635    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
2636
2637 static void
2638 analyze_siv_subscript_cst_affine (tree chrec_a,
2639                                   tree chrec_b,
2640                                   conflict_function **overlaps_a,
2641                                   conflict_function **overlaps_b,
2642                                   tree *last_conflicts)
2643 {
2644   bool value0, value1, value2;
2645   tree difference, tmp;
2646
2647   chrec_a = chrec_convert (integer_type_node, chrec_a, NULL_TREE);
2648   chrec_b = chrec_convert (integer_type_node, chrec_b, NULL_TREE);
2649   difference = chrec_fold_minus
2650     (integer_type_node, initial_condition (chrec_b), chrec_a);
2651
2652   if (!chrec_is_positive (initial_condition (difference), &value0))
2653     {
2654       if (dump_file && (dump_flags & TDF_DETAILS))
2655         fprintf (dump_file, "siv test failed: chrec is not positive.\n");
2656
2657       dependence_stats.num_siv_unimplemented++;
2658       *overlaps_a = conflict_fn_not_known ();
2659       *overlaps_b = conflict_fn_not_known ();
2660       *last_conflicts = chrec_dont_know;
2661       return;
2662     }
2663   else
2664     {
2665       if (value0 == false)
2666         {
2667           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value1))
2668             {
2669               if (dump_file && (dump_flags & TDF_DETAILS))
2670                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2671
2672               *overlaps_a = conflict_fn_not_known ();
2673               *overlaps_b = conflict_fn_not_known ();
2674               *last_conflicts = chrec_dont_know;
2675               dependence_stats.num_siv_unimplemented++;
2676               return;
2677             }
2678           else
2679             {
2680               if (value1 == true)
2681                 {
2682                   /* Example:
2683                      chrec_a = 12
2684                      chrec_b = {10, +, 1}
2685                   */
2686
2687                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2688                     {
2689                       HOST_WIDE_INT numiter;
2690                       struct loop *loop = get_chrec_loop (chrec_b);
2691
2692                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2693                       tmp = fold_build2 (EXACT_DIV_EXPR, integer_type_node,
2694                                          fold_build1 (ABS_EXPR,
2695                                                       integer_type_node,
2696                                                       difference),
2697                                          CHREC_RIGHT (chrec_b));
2698                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2699                       *last_conflicts = integer_one_node;
2700
2701
2702                       /* Perform weak-zero siv test to see if overlap is
2703                          outside the loop bounds.  */
2704                       numiter = estimated_loop_iterations_int (loop, true);
2705
2706                       if (numiter >= 0
2707                           && compare_tree_int (tmp, numiter) > 0)
2708                         {
2709                           free_conflict_function (*overlaps_a);
2710                           free_conflict_function (*overlaps_b);
2711                           *overlaps_a = conflict_fn_no_dependence ();
2712                           *overlaps_b = conflict_fn_no_dependence ();
2713                           *last_conflicts = integer_zero_node;
2714                           dependence_stats.num_siv_independent++;
2715                           return;
2716                         }
2717                       dependence_stats.num_siv_dependent++;
2718                       return;
2719                     }
2720
2721                   /* When the step does not divide the difference, there are
2722                      no overlaps.  */
2723                   else
2724                     {
2725                       *overlaps_a = conflict_fn_no_dependence ();
2726                       *overlaps_b = conflict_fn_no_dependence ();
2727                       *last_conflicts = integer_zero_node;
2728                       dependence_stats.num_siv_independent++;
2729                       return;
2730                     }
2731                 }
2732
2733               else
2734                 {
2735                   /* Example:
2736                      chrec_a = 12
2737                      chrec_b = {10, +, -1}
2738
2739                      In this case, chrec_a will not overlap with chrec_b.  */
2740                   *overlaps_a = conflict_fn_no_dependence ();
2741                   *overlaps_b = conflict_fn_no_dependence ();
2742                   *last_conflicts = integer_zero_node;
2743                   dependence_stats.num_siv_independent++;
2744                   return;
2745                 }
2746             }
2747         }
2748       else
2749         {
2750           if (!chrec_is_positive (CHREC_RIGHT (chrec_b), &value2))
2751             {
2752               if (dump_file && (dump_flags & TDF_DETAILS))
2753                 fprintf (dump_file, "siv test failed: chrec not positive.\n");
2754
2755               *overlaps_a = conflict_fn_not_known ();
2756               *overlaps_b = conflict_fn_not_known ();
2757               *last_conflicts = chrec_dont_know;
2758               dependence_stats.num_siv_unimplemented++;
2759               return;
2760             }
2761           else
2762             {
2763               if (value2 == false)
2764                 {
2765                   /* Example:
2766                      chrec_a = 3
2767                      chrec_b = {10, +, -1}
2768                   */
2769                   if (tree_fold_divides_p (CHREC_RIGHT (chrec_b), difference))
2770                     {
2771                       HOST_WIDE_INT numiter;
2772                       struct loop *loop = get_chrec_loop (chrec_b);
2773
2774                       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
2775                       tmp = fold_build2 (EXACT_DIV_EXPR,
2776                                          integer_type_node, difference,
2777                                          CHREC_RIGHT (chrec_b));
2778                       *overlaps_b = conflict_fn (1, affine_fn_cst (tmp));
2779                       *last_conflicts = integer_one_node;
2780
2781                       /* Perform weak-zero siv test to see if overlap is
2782                          outside the loop bounds.  */
2783                       numiter = estimated_loop_iterations_int (loop, true);
2784
2785                       if (numiter >= 0
2786                           && compare_tree_int (tmp, numiter) > 0)
2787                         {
2788                           free_conflict_function (*overlaps_a);
2789                           free_conflict_function (*overlaps_b);
2790                           *overlaps_a = conflict_fn_no_dependence ();
2791                           *overlaps_b = conflict_fn_no_dependence ();
2792                           *last_conflicts = integer_zero_node;
2793                           dependence_stats.num_siv_independent++;
2794                           return;
2795                         }
2796                       dependence_stats.num_siv_dependent++;
2797                       return;
2798                     }
2799
2800                   /* When the step does not divide the difference, there
2801                      are no overlaps.  */
2802                   else
2803                     {
2804                       *overlaps_a = conflict_fn_no_dependence ();
2805                       *overlaps_b = conflict_fn_no_dependence ();
2806                       *last_conflicts = integer_zero_node;
2807                       dependence_stats.num_siv_independent++;
2808                       return;
2809                     }
2810                 }
2811               else
2812                 {
2813                   /* Example:
2814                      chrec_a = 3
2815                      chrec_b = {4, +, 1}
2816
2817                      In this case, chrec_a will not overlap with chrec_b.  */
2818                   *overlaps_a = conflict_fn_no_dependence ();
2819                   *overlaps_b = conflict_fn_no_dependence ();
2820                   *last_conflicts = integer_zero_node;
2821                   dependence_stats.num_siv_independent++;
2822                   return;
2823                 }
2824             }
2825         }
2826     }
2827 }
2828
2829 /* Helper recursive function for initializing the matrix A.  Returns
2830    the initial value of CHREC.  */
2831
2832 static int
2833 initialize_matrix_A (lambda_matrix A, tree chrec, unsigned index, int mult)
2834 {
2835   gcc_assert (chrec);
2836
2837   if (TREE_CODE (chrec) != POLYNOMIAL_CHREC)
2838     return int_cst_value (chrec);
2839
2840   A[index][0] = mult * int_cst_value (CHREC_RIGHT (chrec));
2841   return initialize_matrix_A (A, CHREC_LEFT (chrec), index + 1, mult);
2842 }
2843
2844 #define FLOOR_DIV(x,y) ((x) / (y))
2845
2846 /* Solves the special case of the Diophantine equation:
2847    | {0, +, STEP_A}_x (OVERLAPS_A) = {0, +, STEP_B}_y (OVERLAPS_B)
2848
2849    Computes the descriptions OVERLAPS_A and OVERLAPS_B.  NITER is the
2850    number of iterations that loops X and Y run.  The overlaps will be
2851    constructed as evolutions in dimension DIM.  */
2852
2853 static void
2854 compute_overlap_steps_for_affine_univar (int niter, int step_a, int step_b,
2855                                          affine_fn *overlaps_a,
2856                                          affine_fn *overlaps_b,
2857                                          tree *last_conflicts, int dim)
2858 {
2859   if (((step_a > 0 && step_b > 0)
2860        || (step_a < 0 && step_b < 0)))
2861     {
2862       int step_overlaps_a, step_overlaps_b;
2863       int gcd_steps_a_b, last_conflict, tau2;
2864
2865       gcd_steps_a_b = gcd (step_a, step_b);
2866       step_overlaps_a = step_b / gcd_steps_a_b;
2867       step_overlaps_b = step_a / gcd_steps_a_b;
2868
2869       tau2 = FLOOR_DIV (niter, step_overlaps_a);
2870       tau2 = MIN (tau2, FLOOR_DIV (niter, step_overlaps_b));
2871       last_conflict = tau2;
2872
2873       *overlaps_a = affine_fn_univar (integer_zero_node, dim,
2874                                       build_int_cst (NULL_TREE,
2875                                                      step_overlaps_a));
2876       *overlaps_b = affine_fn_univar (integer_zero_node, dim,
2877                                       build_int_cst (NULL_TREE,
2878                                                      step_overlaps_b));
2879       *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
2880     }
2881
2882   else
2883     {
2884       *overlaps_a = affine_fn_cst (integer_zero_node);
2885       *overlaps_b = affine_fn_cst (integer_zero_node);
2886       *last_conflicts = integer_zero_node;
2887     }
2888 }
2889
2890 /* Solves the special case of a Diophantine equation where CHREC_A is
2891    an affine bivariate function, and CHREC_B is an affine univariate
2892    function.  For example,
2893
2894    | {{0, +, 1}_x, +, 1335}_y = {0, +, 1336}_z
2895
2896    has the following overlapping functions:
2897
2898    | x (t, u, v) = {{0, +, 1336}_t, +, 1}_v
2899    | y (t, u, v) = {{0, +, 1336}_u, +, 1}_v
2900    | z (t, u, v) = {{{0, +, 1}_t, +, 1335}_u, +, 1}_v
2901
2902    FORNOW: This is a specialized implementation for a case occurring in
2903    a common benchmark.  Implement the general algorithm.  */
2904
2905 static void
2906 compute_overlap_steps_for_affine_1_2 (tree chrec_a, tree chrec_b,
2907                                       conflict_function **overlaps_a,
2908                                       conflict_function **overlaps_b,
2909                                       tree *last_conflicts)
2910 {
2911   bool xz_p, yz_p, xyz_p;
2912   int step_x, step_y, step_z;
2913   HOST_WIDE_INT niter_x, niter_y, niter_z, niter;
2914   affine_fn overlaps_a_xz, overlaps_b_xz;
2915   affine_fn overlaps_a_yz, overlaps_b_yz;
2916   affine_fn overlaps_a_xyz, overlaps_b_xyz;
2917   affine_fn ova1, ova2, ovb;
2918   tree last_conflicts_xz, last_conflicts_yz, last_conflicts_xyz;
2919
2920   step_x = int_cst_value (CHREC_RIGHT (CHREC_LEFT (chrec_a)));
2921   step_y = int_cst_value (CHREC_RIGHT (chrec_a));
2922   step_z = int_cst_value (CHREC_RIGHT (chrec_b));
2923
2924   niter_x = estimated_loop_iterations_int
2925                 (get_chrec_loop (CHREC_LEFT (chrec_a)), true);
2926   niter_y = estimated_loop_iterations_int (get_chrec_loop (chrec_a), true);
2927   niter_z = estimated_loop_iterations_int (get_chrec_loop (chrec_b), true);
2928
2929   if (niter_x < 0 || niter_y < 0 || niter_z < 0)
2930     {
2931       if (dump_file && (dump_flags & TDF_DETAILS))
2932         fprintf (dump_file, "overlap steps test failed: no iteration counts.\n");
2933
2934       *overlaps_a = conflict_fn_not_known ();
2935       *overlaps_b = conflict_fn_not_known ();
2936       *last_conflicts = chrec_dont_know;
2937       return;
2938     }
2939
2940   niter = MIN (niter_x, niter_z);
2941   compute_overlap_steps_for_affine_univar (niter, step_x, step_z,
2942                                            &overlaps_a_xz,
2943                                            &overlaps_b_xz,
2944                                            &last_conflicts_xz, 1);
2945   niter = MIN (niter_y, niter_z);
2946   compute_overlap_steps_for_affine_univar (niter, step_y, step_z,
2947                                            &overlaps_a_yz,
2948                                            &overlaps_b_yz,
2949                                            &last_conflicts_yz, 2);
2950   niter = MIN (niter_x, niter_z);
2951   niter = MIN (niter_y, niter);
2952   compute_overlap_steps_for_affine_univar (niter, step_x + step_y, step_z,
2953                                            &overlaps_a_xyz,
2954                                            &overlaps_b_xyz,
2955                                            &last_conflicts_xyz, 3);
2956
2957   xz_p = !integer_zerop (last_conflicts_xz);
2958   yz_p = !integer_zerop (last_conflicts_yz);
2959   xyz_p = !integer_zerop (last_conflicts_xyz);
2960
2961   if (xz_p || yz_p || xyz_p)
2962     {
2963       ova1 = affine_fn_cst (integer_zero_node);
2964       ova2 = affine_fn_cst (integer_zero_node);
2965       ovb = affine_fn_cst (integer_zero_node);
2966       if (xz_p)
2967         {
2968           affine_fn t0 = ova1;
2969           affine_fn t2 = ovb;
2970
2971           ova1 = affine_fn_plus (ova1, overlaps_a_xz);
2972           ovb = affine_fn_plus (ovb, overlaps_b_xz);
2973           affine_fn_free (t0);
2974           affine_fn_free (t2);
2975           *last_conflicts = last_conflicts_xz;
2976         }
2977       if (yz_p)
2978         {
2979           affine_fn t0 = ova2;
2980           affine_fn t2 = ovb;
2981
2982           ova2 = affine_fn_plus (ova2, overlaps_a_yz);
2983           ovb = affine_fn_plus (ovb, overlaps_b_yz);
2984           affine_fn_free (t0);
2985           affine_fn_free (t2);
2986           *last_conflicts = last_conflicts_yz;
2987         }
2988       if (xyz_p)
2989         {
2990           affine_fn t0 = ova1;
2991           affine_fn t2 = ova2;
2992           affine_fn t4 = ovb;
2993
2994           ova1 = affine_fn_plus (ova1, overlaps_a_xyz);
2995           ova2 = affine_fn_plus (ova2, overlaps_a_xyz);
2996           ovb = affine_fn_plus (ovb, overlaps_b_xyz);
2997           affine_fn_free (t0);
2998           affine_fn_free (t2);
2999           affine_fn_free (t4);
3000           *last_conflicts = last_conflicts_xyz;
3001         }
3002       *overlaps_a = conflict_fn (2, ova1, ova2);
3003       *overlaps_b = conflict_fn (1, ovb);
3004     }
3005   else
3006     {
3007       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3008       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3009       *last_conflicts = integer_zero_node;
3010     }
3011
3012   affine_fn_free (overlaps_a_xz);
3013   affine_fn_free (overlaps_b_xz);
3014   affine_fn_free (overlaps_a_yz);
3015   affine_fn_free (overlaps_b_yz);
3016   affine_fn_free (overlaps_a_xyz);
3017   affine_fn_free (overlaps_b_xyz);
3018 }
3019
3020 /* Determines the overlapping elements due to accesses CHREC_A and
3021    CHREC_B, that are affine functions.  This function cannot handle
3022    symbolic evolution functions, ie. when initial conditions are
3023    parameters, because it uses lambda matrices of integers.  */
3024
3025 static void
3026 analyze_subscript_affine_affine (tree chrec_a,
3027                                  tree chrec_b,
3028                                  conflict_function **overlaps_a,
3029                                  conflict_function **overlaps_b,
3030                                  tree *last_conflicts)
3031 {
3032   unsigned nb_vars_a, nb_vars_b, dim;
3033   int init_a, init_b, gamma, gcd_alpha_beta;
3034   int tau1, tau2;
3035   lambda_matrix A, U, S;
3036
3037   if (eq_evolutions_p (chrec_a, chrec_b))
3038     {
3039       /* The accessed index overlaps for each iteration in the
3040          loop.  */
3041       *overlaps_a = conflict_fn (1, affine_fn_cst (integer_zero_node));
3042       *overlaps_b = conflict_fn (1, affine_fn_cst (integer_zero_node));
3043       *last_conflicts = chrec_dont_know;
3044       return;
3045     }
3046   if (dump_file && (dump_flags & TDF_DETAILS))
3047     fprintf (dump_file, "(analyze_subscript_affine_affine \n");
3048
3049   /* For determining the initial intersection, we have to solve a
3050      Diophantine equation.  This is the most time consuming part.
3051
3052      For answering to the question: "Is there a dependence?" we have
3053      to prove that there exists a solution to the Diophantine
3054      equation, and that the solution is in the iteration domain,
3055      i.e. the solution is positive or zero, and that the solution
3056      happens before the upper bound loop.nb_iterations.  Otherwise
3057      there is no dependence.  This function outputs a description of
3058      the iterations that hold the intersections.  */
3059
3060   nb_vars_a = nb_vars_in_chrec (chrec_a);
3061   nb_vars_b = nb_vars_in_chrec (chrec_b);
3062
3063   dim = nb_vars_a + nb_vars_b;
3064   U = lambda_matrix_new (dim, dim);
3065   A = lambda_matrix_new (dim, 1);
3066   S = lambda_matrix_new (dim, 1);
3067
3068   init_a = initialize_matrix_A (A, chrec_a, 0, 1);
3069   init_b = initialize_matrix_A (A, chrec_b, nb_vars_a, -1);
3070   gamma = init_b - init_a;
3071
3072   /* Don't do all the hard work of solving the Diophantine equation
3073      when we already know the solution: for example,
3074      | {3, +, 1}_1
3075      | {3, +, 4}_2
3076      | gamma = 3 - 3 = 0.
3077      Then the first overlap occurs during the first iterations:
3078      | {3, +, 1}_1 ({0, +, 4}_x) = {3, +, 4}_2 ({0, +, 1}_x)
3079   */
3080   if (gamma == 0)
3081     {
3082       if (nb_vars_a == 1 && nb_vars_b == 1)
3083         {
3084           int step_a, step_b;
3085           HOST_WIDE_INT niter, niter_a, niter_b;
3086           affine_fn ova, ovb;
3087
3088           niter_a = estimated_loop_iterations_int
3089                         (get_chrec_loop (chrec_a), true);
3090           niter_b = estimated_loop_iterations_int
3091                         (get_chrec_loop (chrec_b), true);
3092           if (niter_a < 0 || niter_b < 0)
3093             {
3094               if (dump_file && (dump_flags & TDF_DETAILS))
3095                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3096               *overlaps_a = conflict_fn_not_known ();
3097               *overlaps_b = conflict_fn_not_known ();
3098               *last_conflicts = chrec_dont_know;
3099               goto end_analyze_subs_aa;
3100             }
3101
3102           niter = MIN (niter_a, niter_b);
3103
3104           step_a = int_cst_value (CHREC_RIGHT (chrec_a));
3105           step_b = int_cst_value (CHREC_RIGHT (chrec_b));
3106
3107           compute_overlap_steps_for_affine_univar (niter, step_a, step_b,
3108                                                    &ova, &ovb,
3109                                                    last_conflicts, 1);
3110           *overlaps_a = conflict_fn (1, ova);
3111           *overlaps_b = conflict_fn (1, ovb);
3112         }
3113
3114       else if (nb_vars_a == 2 && nb_vars_b == 1)
3115         compute_overlap_steps_for_affine_1_2
3116           (chrec_a, chrec_b, overlaps_a, overlaps_b, last_conflicts);
3117
3118       else if (nb_vars_a == 1 && nb_vars_b == 2)
3119         compute_overlap_steps_for_affine_1_2
3120           (chrec_b, chrec_a, overlaps_b, overlaps_a, last_conflicts);
3121
3122       else
3123         {
3124           if (dump_file && (dump_flags & TDF_DETAILS))
3125             fprintf (dump_file, "affine-affine test failed: too many variables.\n");
3126           *overlaps_a = conflict_fn_not_known ();
3127           *overlaps_b = conflict_fn_not_known ();
3128           *last_conflicts = chrec_dont_know;
3129         }
3130       goto end_analyze_subs_aa;
3131     }
3132
3133   /* U.A = S */
3134   lambda_matrix_right_hermite (A, dim, 1, S, U);
3135
3136   if (S[0][0] < 0)
3137     {
3138       S[0][0] *= -1;
3139       lambda_matrix_row_negate (U, dim, 0);
3140     }
3141   gcd_alpha_beta = S[0][0];
3142
3143   /* Something went wrong: for example in {1, +, 0}_5 vs. {0, +, 0}_5,
3144      but that is a quite strange case.  Instead of ICEing, answer
3145      don't know.  */
3146   if (gcd_alpha_beta == 0)
3147     {
3148       *overlaps_a = conflict_fn_not_known ();
3149       *overlaps_b = conflict_fn_not_known ();
3150       *last_conflicts = chrec_dont_know;
3151       goto end_analyze_subs_aa;
3152     }
3153
3154   /* The classic "gcd-test".  */
3155   if (!int_divides_p (gcd_alpha_beta, gamma))
3156     {
3157       /* The "gcd-test" has determined that there is no integer
3158          solution, i.e. there is no dependence.  */
3159       *overlaps_a = conflict_fn_no_dependence ();
3160       *overlaps_b = conflict_fn_no_dependence ();
3161       *last_conflicts = integer_zero_node;
3162     }
3163
3164   /* Both access functions are univariate.  This includes SIV and MIV cases.  */
3165   else if (nb_vars_a == 1 && nb_vars_b == 1)
3166     {
3167       /* Both functions should have the same evolution sign.  */
3168       if (((A[0][0] > 0 && -A[1][0] > 0)
3169            || (A[0][0] < 0 && -A[1][0] < 0)))
3170         {
3171           /* The solutions are given by:
3172              |
3173              | [GAMMA/GCD_ALPHA_BETA  t].[u11 u12]  = [x0]
3174              |                           [u21 u22]    [y0]
3175
3176              For a given integer t.  Using the following variables,
3177
3178              | i0 = u11 * gamma / gcd_alpha_beta
3179              | j0 = u12 * gamma / gcd_alpha_beta
3180              | i1 = u21
3181              | j1 = u22
3182
3183              the solutions are:
3184
3185              | x0 = i0 + i1 * t,
3186              | y0 = j0 + j1 * t.  */
3187
3188           int i0, j0, i1, j1;
3189
3190           /* X0 and Y0 are the first iterations for which there is a
3191              dependence.  X0, Y0 are two solutions of the Diophantine
3192              equation: chrec_a (X0) = chrec_b (Y0).  */
3193           int x0, y0;
3194           int niter, niter_a, niter_b;
3195
3196           niter_a = estimated_loop_iterations_int
3197                         (get_chrec_loop (chrec_a), true);
3198           niter_b = estimated_loop_iterations_int
3199                         (get_chrec_loop (chrec_b), true);
3200
3201           if (niter_a < 0 || niter_b < 0)
3202             {
3203               if (dump_file && (dump_flags & TDF_DETAILS))
3204                 fprintf (dump_file, "affine-affine test failed: missing iteration counts.\n");
3205               *overlaps_a = conflict_fn_not_known ();
3206               *overlaps_b = conflict_fn_not_known ();
3207               *last_conflicts = chrec_dont_know;
3208               goto end_analyze_subs_aa;
3209             }
3210
3211           niter = MIN (niter_a, niter_b);
3212
3213           i0 = U[0][0] * gamma / gcd_alpha_beta;
3214           j0 = U[0][1] * gamma / gcd_alpha_beta;
3215           i1 = U[1][0];
3216           j1 = U[1][1];
3217
3218           if ((i1 == 0 && i0 < 0)
3219               || (j1 == 0 && j0 < 0))
3220             {
3221               /* There is no solution.
3222                  FIXME: The case "i0 > nb_iterations, j0 > nb_iterations"
3223                  falls in here, but for the moment we don't look at the
3224                  upper bound of the iteration domain.  */
3225               *overlaps_a = conflict_fn_no_dependence ();
3226               *overlaps_b = conflict_fn_no_dependence ();
3227               *last_conflicts = integer_zero_node;
3228             }
3229
3230           else
3231             {
3232               if (i1 > 0)
3233                 {
3234                   tau1 = CEIL (-i0, i1);
3235                   tau2 = FLOOR_DIV (niter - i0, i1);
3236
3237                   if (j1 > 0)
3238                     {
3239                       int last_conflict, min_multiple;
3240                       tau1 = MAX (tau1, CEIL (-j0, j1));
3241                       tau2 = MIN (tau2, FLOOR_DIV (niter - j0, j1));
3242
3243                       x0 = i1 * tau1 + i0;
3244                       y0 = j1 * tau1 + j0;
3245
3246                       /* At this point (x0, y0) is one of the
3247                          solutions to the Diophantine equation.  The
3248                          next step has to compute the smallest
3249                          positive solution: the first conflicts.  */
3250                       min_multiple = MIN (x0 / i1, y0 / j1);
3251                       x0 -= i1 * min_multiple;
3252                       y0 -= j1 * min_multiple;
3253
3254                       tau1 = (x0 - i0)/i1;
3255                       last_conflict = tau2 - tau1;
3256
3257                       /* If the overlap occurs outside of the bounds of the
3258                          loop, there is no dependence.  */
3259                       if (x0 > niter || y0  > niter)
3260                         {
3261                           *overlaps_a = conflict_fn_no_dependence ();
3262                           *overlaps_b = conflict_fn_no_dependence ();
3263                           *last_conflicts = integer_zero_node;
3264                         }
3265                       else
3266                         {
3267                           *overlaps_a
3268                             = conflict_fn (1,
3269                                 affine_fn_univar (build_int_cst (NULL_TREE, x0),
3270                                                   1,
3271                                                   build_int_cst (NULL_TREE, i1)));
3272                           *overlaps_b
3273                             = conflict_fn (1,
3274                                 affine_fn_univar (build_int_cst (NULL_TREE, y0),
3275                                                   1,
3276                                                   build_int_cst (NULL_TREE, j1)));
3277                           *last_conflicts = build_int_cst (NULL_TREE, last_conflict);
3278                         }
3279                     }
3280                   else
3281                     {
3282                       /* FIXME: For the moment, the upper bound of the
3283                          iteration domain for j is not checked.  */
3284                       if (dump_file && (dump_flags & TDF_DETAILS))
3285                         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3286                       *overlaps_a = conflict_fn_not_known ();
3287                       *overlaps_b = conflict_fn_not_known ();
3288                       *last_conflicts = chrec_dont_know;
3289                     }
3290                 }
3291
3292               else
3293                 {
3294                   /* FIXME: For the moment, the upper bound of the
3295                      iteration domain for i is not checked.  */
3296                   if (dump_file && (dump_flags & TDF_DETAILS))
3297                     fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3298                   *overlaps_a = conflict_fn_not_known ();
3299                   *overlaps_b = conflict_fn_not_known ();
3300                   *last_conflicts = chrec_dont_know;
3301                 }
3302             }
3303         }
3304       else
3305         {
3306           if (dump_file && (dump_flags & TDF_DETAILS))
3307             fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3308           *overlaps_a = conflict_fn_not_known ();
3309           *overlaps_b = conflict_fn_not_known ();
3310           *last_conflicts = chrec_dont_know;
3311         }
3312     }
3313
3314   else
3315     {
3316       if (dump_file && (dump_flags & TDF_DETAILS))
3317         fprintf (dump_file, "affine-affine test failed: unimplemented.\n");
3318       *overlaps_a = conflict_fn_not_known ();
3319       *overlaps_b = conflict_fn_not_known ();
3320       *last_conflicts = chrec_dont_know;
3321     }
3322
3323 end_analyze_subs_aa:
3324   if (dump_file && (dump_flags & TDF_DETAILS))
3325     {
3326       fprintf (dump_file, "  (overlaps_a = ");
3327       dump_conflict_function (dump_file, *overlaps_a);
3328       fprintf (dump_file, ")\n  (overlaps_b = ");
3329       dump_conflict_function (dump_file, *overlaps_b);
3330       fprintf (dump_file, ")\n");
3331       fprintf (dump_file, ")\n");
3332     }
3333 }
3334
3335 /* Returns true when analyze_subscript_affine_affine can be used for
3336    determining the dependence relation between chrec_a and chrec_b,
3337    that contain symbols.  This function modifies chrec_a and chrec_b
3338    such that the analysis result is the same, and such that they don't
3339    contain symbols, and then can safely be passed to the analyzer.
3340
3341    Example: The analysis of the following tuples of evolutions produce
3342    the same results: {x+1, +, 1}_1 vs. {x+3, +, 1}_1, and {-2, +, 1}_1
3343    vs. {0, +, 1}_1
3344
3345    {x+1, +, 1}_1 ({2, +, 1}_1) = {x+3, +, 1}_1 ({0, +, 1}_1)
3346    {-2, +, 1}_1 ({2, +, 1}_1) = {0, +, 1}_1 ({0, +, 1}_1)
3347 */
3348
3349 static bool
3350 can_use_analyze_subscript_affine_affine (tree *chrec_a, tree *chrec_b)
3351 {
3352   tree diff, type, left_a, left_b, right_b;
3353
3354   if (chrec_contains_symbols (CHREC_RIGHT (*chrec_a))
3355       || chrec_contains_symbols (CHREC_RIGHT (*chrec_b)))
3356     /* FIXME: For the moment not handled.  Might be refined later.  */
3357     return false;
3358
3359   type = chrec_type (*chrec_a);
3360   left_a = CHREC_LEFT (*chrec_a);
3361   left_b = chrec_convert (type, CHREC_LEFT (*chrec_b), NULL_TREE);
3362   diff = chrec_fold_minus (type, left_a, left_b);
3363
3364   if (!evolution_function_is_constant_p (diff))
3365     return false;
3366
3367   if (dump_file && (dump_flags & TDF_DETAILS))
3368     fprintf (dump_file, "can_use_subscript_aff_aff_for_symbolic \n");
3369
3370   *chrec_a = build_polynomial_chrec (CHREC_VARIABLE (*chrec_a),
3371                                      diff, CHREC_RIGHT (*chrec_a));
3372   right_b = chrec_convert (type, CHREC_RIGHT (*chrec_b), NULL_TREE);
3373   *chrec_b = build_polynomial_chrec (CHREC_VARIABLE (*chrec_b),
3374                                      build_int_cst (type, 0),
3375                                      right_b);
3376   return true;
3377 }
3378
3379 /* Analyze a SIV (Single Index Variable) subscript.  *OVERLAPS_A and
3380    *OVERLAPS_B are initialized to the functions that describe the
3381    relation between the elements accessed twice by CHREC_A and
3382    CHREC_B.  For k >= 0, the following property is verified:
3383
3384    CHREC_A (*OVERLAPS_A (k)) = CHREC_B (*OVERLAPS_B (k)).  */
3385
3386 static void
3387 analyze_siv_subscript (tree chrec_a,
3388                        tree chrec_b,
3389                        conflict_function **overlaps_a,
3390                        conflict_function **overlaps_b,
3391                        tree *last_conflicts)
3392 {
3393   dependence_stats.num_siv++;
3394
3395   if (dump_file && (dump_flags & TDF_DETAILS))
3396     fprintf (dump_file, "(analyze_siv_subscript \n");
3397
3398   if (evolution_function_is_constant_p (chrec_a)
3399       && evolution_function_is_affine_p (chrec_b))
3400     analyze_siv_subscript_cst_affine (chrec_a, chrec_b,
3401                                       overlaps_a, overlaps_b, last_conflicts);
3402
3403   else if (evolution_function_is_affine_p (chrec_a)
3404            && evolution_function_is_constant_p (chrec_b))
3405     analyze_siv_subscript_cst_affine (chrec_b, chrec_a,
3406                                       overlaps_b, overlaps_a, last_conflicts);
3407
3408   else if (evolution_function_is_affine_p (chrec_a)
3409            && evolution_function_is_affine_p (chrec_b))
3410     {
3411       if (!chrec_contains_symbols (chrec_a)
3412           && !chrec_contains_symbols (chrec_b))
3413         {
3414           analyze_subscript_affine_affine (chrec_a, chrec_b,
3415                                            overlaps_a, overlaps_b,
3416                                            last_conflicts);
3417
3418           if (CF_NOT_KNOWN_P (*overlaps_a)
3419               || CF_NOT_KNOWN_P (*overlaps_b))
3420             dependence_stats.num_siv_unimplemented++;
3421           else if (CF_NO_DEPENDENCE_P (*overlaps_a)
3422                    || CF_NO_DEPENDENCE_P (*overlaps_b))
3423             dependence_stats.num_siv_independent++;
3424           else
3425             dependence_stats.num_siv_dependent++;
3426         }