OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gcc-4.2.2/] [gcc/] [tree-data-ref.c] - Blame information for rev 832

Go to most recent revision | Details | Compare with Previous | View Log

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

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.