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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-stable/] [gcc-4.5.1/] [gcc/] [graphite-dependences.c] - Blame information for rev 280

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

Line No. Rev Author Line
1 280 jeremybenn
/* Data dependence analysis for Graphite.
2
   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4
   Konrad Trifunovic <konrad.trifunovic@inria.fr>.
5
 
6
This file is part of GCC.
7
 
8
GCC is free software; you can redistribute it and/or modify
9
it under the terms of the GNU General Public License as published by
10
the Free Software Foundation; either version 3, or (at your option)
11
any later version.
12
 
13
GCC is distributed in the hope that it will be useful,
14
but WITHOUT ANY WARRANTY; without even the implied warranty of
15
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
16
GNU General Public License 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
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
#include "tm.h"
26
#include "ggc.h"
27
#include "tree.h"
28
#include "rtl.h"
29
#include "basic-block.h"
30
#include "diagnostic.h"
31
#include "tree-flow.h"
32
#include "toplev.h"
33
#include "tree-dump.h"
34
#include "timevar.h"
35
#include "cfgloop.h"
36
#include "tree-chrec.h"
37
#include "tree-data-ref.h"
38
#include "tree-scalar-evolution.h"
39
#include "tree-pass.h"
40
#include "domwalk.h"
41
#include "pointer-set.h"
42
#include "gimple.h"
43
 
44
#ifdef HAVE_cloog
45
#include "cloog/cloog.h"
46
#include "ppl_c.h"
47
#include "sese.h"
48
#include "graphite-ppl.h"
49
#include "graphite.h"
50
#include "graphite-poly.h"
51
#include "graphite-dependences.h"
52
 
53
/* Returns a new polyhedral Data Dependence Relation (DDR).  SOURCE is
54
   the source data reference, SINK is the sink data reference.  When
55
   the Data Dependence Polyhedron DDP is not NULL or not empty, SOURCE
56
   and SINK are in dependence as described by DDP.  */
57
 
58
static poly_ddr_p
59
new_poly_ddr (poly_dr_p source, poly_dr_p sink,
60
              ppl_Pointset_Powerset_C_Polyhedron_t ddp,
61
              bool original_scattering_p)
62
{
63
  poly_ddr_p pddr = XNEW (struct poly_ddr);
64
 
65
  PDDR_SOURCE (pddr) = source;
66
  PDDR_SINK (pddr) = sink;
67
  PDDR_DDP (pddr) = ddp;
68
  PDDR_ORIGINAL_SCATTERING_P (pddr) = original_scattering_p;
69
 
70
  if (!ddp || ppl_Pointset_Powerset_C_Polyhedron_is_empty (ddp))
71
    PDDR_KIND (pddr) = no_dependence;
72
  else
73
    PDDR_KIND (pddr) = has_dependence;
74
 
75
  return pddr;
76
}
77
 
78
/* Free the poly_ddr_p P.  */
79
 
80
void
81
free_poly_ddr (void *p)
82
{
83
  poly_ddr_p pddr = (poly_ddr_p) p;
84
  ppl_delete_Pointset_Powerset_C_Polyhedron (PDDR_DDP (pddr));
85
  free (pddr);
86
}
87
 
88
/* Comparison function for poly_ddr hash table.  */
89
 
90
int
91
eq_poly_ddr_p (const void *pddr1, const void *pddr2)
92
{
93
  const struct poly_ddr *p1 = (const struct poly_ddr *) pddr1;
94
  const struct poly_ddr *p2 = (const struct poly_ddr *) pddr2;
95
 
96
  return (PDDR_SOURCE (p1) == PDDR_SOURCE (p2)
97
          && PDDR_SINK (p1) == PDDR_SINK (p2));
98
}
99
 
100
/* Hash function for poly_ddr hashtable.  */
101
 
102
hashval_t
103
hash_poly_ddr_p (const void *pddr)
104
{
105
  const struct poly_ddr *p = (const struct poly_ddr *) pddr;
106
 
107
  return (hashval_t) ((long) PDDR_SOURCE (p) + (long) PDDR_SINK (p));
108
}
109
 
110
/* Returns true when PDDR has no dependence.  */
111
 
112
static bool
113
pddr_is_empty (poly_ddr_p pddr)
114
{
115
  if (!pddr)
116
    return true;
117
 
118
  gcc_assert (PDDR_KIND (pddr) != unknown_dependence);
119
 
120
  return PDDR_KIND (pddr) == no_dependence ? true : false;
121
}
122
 
123
/* Prints to FILE the layout of the dependence polyhedron of PDDR:
124
 
125
   T1|I1|T2|I2|S1|S2|G
126
 
127
   with
128
   | T1 and T2 the scattering dimensions for PDDR_SOURCE and PDDR_SINK
129
   | I1 and I2 the iteration domains
130
   | S1 and S2 the subscripts
131
   | G the global parameters.  */
132
 
133
static void
134
print_dependence_polyhedron_layout (FILE *file, poly_ddr_p pddr)
135
{
136
  poly_dr_p pdr1 = PDDR_SOURCE (pddr);
137
  poly_dr_p pdr2 = PDDR_SINK (pddr);
138
  poly_bb_p pbb1 = PDR_PBB (pdr1);
139
  poly_bb_p pbb2 = PDR_PBB (pdr2);
140
 
141
  graphite_dim_t i;
142
  graphite_dim_t tdim1 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
143
    pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
144
  graphite_dim_t tdim2 = PDDR_ORIGINAL_SCATTERING_P (pddr) ?
145
    pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
146
  graphite_dim_t idim1 = pbb_dim_iter_domain (pbb1);
147
  graphite_dim_t idim2 = pbb_dim_iter_domain (pbb2);
148
  graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
149
  graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
150
  graphite_dim_t gdim = scop_nb_params (PBB_SCOP (pbb1));
151
 
152
  fprintf (file, "#  eq");
153
 
154
  for (i = 0; i < tdim1; i++)
155
    fprintf (file, "   t1_%d", (int) i);
156
  for (i = 0; i < idim1; i++)
157
    fprintf (file, "   i1_%d", (int) i);
158
  for (i = 0; i < tdim2; i++)
159
    fprintf (file, "   t2_%d", (int) i);
160
  for (i = 0; i < idim2; i++)
161
    fprintf (file, "   i2_%d", (int) i);
162
  for (i = 0; i < sdim1; i++)
163
    fprintf (file, "   s1_%d", (int) i);
164
  for (i = 0; i < sdim2; i++)
165
    fprintf (file, "   s2_%d", (int) i);
166
  for (i = 0; i < gdim; i++)
167
    fprintf (file, "    g_%d", (int) i);
168
 
169
  fprintf (file, "    cst\n");
170
}
171
 
172
/* Prints to FILE the poly_ddr_p PDDR.  */
173
 
174
void
175
print_pddr (FILE *file, poly_ddr_p pddr)
176
{
177
  fprintf (file, "pddr (kind: ");
178
 
179
  if (PDDR_KIND (pddr) == unknown_dependence)
180
    fprintf (file, "unknown_dependence");
181
  else if (PDDR_KIND (pddr) == no_dependence)
182
    fprintf (file, "no_dependence");
183
  else if (PDDR_KIND (pddr) == has_dependence)
184
    fprintf (file, "has_dependence");
185
 
186
  fprintf (file, "\n  source ");
187
  print_pdr (file, PDDR_SOURCE (pddr), 2);
188
 
189
  fprintf (file, "\n  sink ");
190
  print_pdr (file, PDDR_SINK (pddr), 2);
191
 
192
  if (PDDR_KIND (pddr) == has_dependence)
193
    {
194
      fprintf (file, "\n  dependence polyhedron (\n");
195
      print_dependence_polyhedron_layout (file, pddr);
196
      ppl_print_powerset_matrix (file, PDDR_DDP (pddr));
197
      fprintf (file, ")\n");
198
    }
199
 
200
  fprintf (file, ")\n");
201
}
202
 
203
/* Prints to STDERR the poly_ddr_p PDDR.  */
204
 
205
void
206
debug_pddr (poly_ddr_p pddr)
207
{
208
  print_pddr (stderr, pddr);
209
}
210
 
211
 
212
/* Remove all the dimensions except alias information at dimension
213
   ALIAS_DIM.  */
214
 
215
static void
216
build_alias_set_powerset (ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset,
217
                          ppl_dimension_type alias_dim)
218
{
219
  ppl_dimension_type *ds;
220
  ppl_dimension_type access_dim;
221
  unsigned i, pos = 0;
222
 
223
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (alias_powerset,
224
                                                      &access_dim);
225
  ds = XNEWVEC (ppl_dimension_type, access_dim-1);
226
  for (i = 0; i < access_dim; i++)
227
    {
228
      if (i == alias_dim)
229
        continue;
230
 
231
      ds[pos] = i;
232
      pos++;
233
    }
234
 
235
  ppl_Pointset_Powerset_C_Polyhedron_remove_space_dimensions (alias_powerset,
236
                                                              ds,
237
                                                              access_dim - 1);
238
  free (ds);
239
}
240
 
241
/* Return true when PDR1 and PDR2 may alias.  */
242
 
243
static bool
244
poly_drs_may_alias_p (poly_dr_p pdr1, poly_dr_p pdr2)
245
{
246
  ppl_Pointset_Powerset_C_Polyhedron_t alias_powerset1, alias_powerset2;
247
  ppl_Pointset_Powerset_C_Polyhedron_t accesses1 = PDR_ACCESSES (pdr1);
248
  ppl_Pointset_Powerset_C_Polyhedron_t accesses2 = PDR_ACCESSES (pdr2);
249
  ppl_dimension_type alias_dim1 = pdr_alias_set_dim (pdr1);
250
  ppl_dimension_type alias_dim2 = pdr_alias_set_dim (pdr2);
251
  int empty_p;
252
 
253
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
254
    (&alias_powerset1, accesses1);
255
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
256
    (&alias_powerset2, accesses2);
257
 
258
  build_alias_set_powerset (alias_powerset1, alias_dim1);
259
  build_alias_set_powerset (alias_powerset2, alias_dim2);
260
 
261
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign
262
    (alias_powerset1, alias_powerset2);
263
 
264
  empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (alias_powerset1);
265
 
266
  ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset1);
267
  ppl_delete_Pointset_Powerset_C_Polyhedron (alias_powerset2);
268
 
269
  return !empty_p;
270
}
271
 
272
/* Swap [cut0, ..., cut1] to the end of DR: "a CUT0 b CUT1 c" is
273
   transformed into "a CUT0 c CUT1' b"
274
 
275
   Add NB0 zeros before "a":  "00...0 a CUT0 c CUT1' b"
276
   Add NB1 zeros between "a" and "c":  "00...0 a 00...0 c CUT1' b"
277
   Add DIM - NB0 - NB1 - PDIM zeros between "c" and "b":
278
   "00...0 a 00...0 c 00...0 b".  */
279
 
280
static ppl_Pointset_Powerset_C_Polyhedron_t
281
map_dr_into_dep_poly (graphite_dim_t dim,
282
                      ppl_Pointset_Powerset_C_Polyhedron_t dr,
283
                      graphite_dim_t cut0, graphite_dim_t cut1,
284
                      graphite_dim_t nb0, graphite_dim_t nb1)
285
{
286
  ppl_dimension_type pdim;
287
  ppl_dimension_type *map;
288
  ppl_Pointset_Powerset_C_Polyhedron_t res;
289
  ppl_dimension_type i;
290
 
291
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
292
    (&res, dr);
293
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (res, &pdim);
294
 
295
  map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, pdim);
296
 
297
  /* First mapping: move 'g' vector to right position.  */
298
  for (i = 0; i < cut0; i++)
299
    map[i] = i;
300
 
301
  for (i = cut0; i < cut1; i++)
302
    map[i] = pdim - cut1 + i;
303
 
304
  for (i = cut1; i < pdim; i++)
305
    map[i] = cut0 + i - cut1;
306
 
307
  ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (res, map, pdim);
308
  free (map);
309
 
310
  /* After swapping 's' and 'g' vectors, we have to update a new cut.  */
311
  cut1 = pdim - cut1 + cut0;
312
 
313
  ppl_insert_dimensions_pointset (res, 0, nb0);
314
  ppl_insert_dimensions_pointset (res, nb0 + cut0, nb1);
315
  ppl_insert_dimensions_pointset (res, nb0 + nb1 + cut1,
316
                                  dim - nb0 - nb1 - pdim);
317
 
318
  return res;
319
}
320
 
321
/* Builds subscript equality constraints.  */
322
 
323
static ppl_Pointset_Powerset_C_Polyhedron_t
324
dr_equality_constraints (graphite_dim_t dim,
325
                         graphite_dim_t pos, graphite_dim_t nb_subscripts)
326
{
327
  ppl_Polyhedron_t eqs;
328
  ppl_Pointset_Powerset_C_Polyhedron_t res;
329
  graphite_dim_t i;
330
 
331
  ppl_new_C_Polyhedron_from_space_dimension (&eqs, dim, 0);
332
 
333
  for (i = 0; i < nb_subscripts; i++)
334
    {
335
      ppl_Constraint_t cstr
336
        = ppl_build_relation (dim, pos + i, pos + i + nb_subscripts,
337
                              0, PPL_CONSTRAINT_TYPE_EQUAL);
338
      ppl_Polyhedron_add_constraint (eqs, cstr);
339
      ppl_delete_Constraint (cstr);
340
    }
341
 
342
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, eqs);
343
  ppl_delete_Polyhedron (eqs);
344
  return res;
345
}
346
 
347
/* Builds scheduling inequality constraints: when DIRECTION is
348
   1 builds a GE constraint,
349
 
350
   -1 builds a LE constraint.  */
351
 
352
static ppl_Pointset_Powerset_C_Polyhedron_t
353
build_pairwise_scheduling (graphite_dim_t dim,
354
                           graphite_dim_t pos,
355
                           graphite_dim_t offset,
356
                           int direction)
357
{
358
  ppl_Pointset_Powerset_C_Polyhedron_t res;
359
  ppl_Polyhedron_t equalities;
360
  ppl_Constraint_t cstr;
361
 
362
  ppl_new_C_Polyhedron_from_space_dimension (&equalities, dim, 0);
363
 
364
  switch (direction)
365
    {
366
    case -1:
367
      cstr = ppl_build_relation (dim, pos, pos + offset, 1,
368
                                 PPL_CONSTRAINT_TYPE_LESS_OR_EQUAL);
369
      break;
370
 
371
    case 0:
372
      cstr = ppl_build_relation (dim, pos, pos + offset, 0,
373
                                 PPL_CONSTRAINT_TYPE_EQUAL);
374
      break;
375
 
376
    case 1:
377
      cstr = ppl_build_relation (dim, pos, pos + offset, -1,
378
                                 PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
379
      break;
380
 
381
    default:
382
      gcc_unreachable ();
383
    }
384
 
385
  ppl_Polyhedron_add_constraint (equalities, cstr);
386
  ppl_delete_Constraint (cstr);
387
 
388
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&res, equalities);
389
  ppl_delete_Polyhedron (equalities);
390
  return res;
391
}
392
 
393
/* Add to a non empty polyhedron BAG the precedence constraints for
394
   the lexicographical comparison of time vectors in BAG following the
395
   lexicographical order.  DIM is the dimension of the polyhedron BAG.
396
   TDIM is the number of loops common to the two statements that are
397
   compared lexicographically, i.e. the number of loops containing
398
   both statements.  OFFSET is the number of dimensions needed to
399
   represent the first statement, i.e. dimT1 + dimI1 in the layout of
400
   the BAG polyhedron: T1|I1|T2|I2|S1|S2|G.  When DIRECTION is set to
401
   1, compute the direct dependence from PDR1 to PDR2, and when
402
   DIRECTION is -1, compute the reversed dependence relation, from
403
   PDR2 to PDR1.  */
404
 
405
static ppl_Pointset_Powerset_C_Polyhedron_t
406
build_lexicographical_constraint (ppl_Pointset_Powerset_C_Polyhedron_t bag,
407
                                  graphite_dim_t dim,
408
                                  graphite_dim_t tdim,
409
                                  graphite_dim_t offset,
410
                                  int direction)
411
{
412
  graphite_dim_t i;
413
  ppl_Pointset_Powerset_C_Polyhedron_t res, lex;
414
 
415
  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 1);
416
 
417
  lex = build_pairwise_scheduling (dim, 0, offset, direction);
418
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
419
 
420
  if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
421
    ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
422
 
423
  ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
424
 
425
  for (i = 0; i < tdim - 1; i++)
426
    {
427
      ppl_Pointset_Powerset_C_Polyhedron_t sceq;
428
 
429
      sceq = build_pairwise_scheduling (dim, i, offset, 0);
430
      ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (bag, sceq);
431
      ppl_delete_Pointset_Powerset_C_Polyhedron (sceq);
432
 
433
      lex = build_pairwise_scheduling (dim, i + 1, offset, direction);
434
      ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (lex, bag);
435
 
436
      if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (lex))
437
        ppl_Pointset_Powerset_C_Polyhedron_upper_bound_assign (res, lex);
438
 
439
      ppl_delete_Pointset_Powerset_C_Polyhedron (lex);
440
    }
441
 
442
  return res;
443
}
444
 
445
/* Build the dependence polyhedron for data references PDR1 and PDR2.
446
   The layout of the dependence polyhedron is:
447
 
448
   T1|I1|T2|I2|S1|S2|G
449
 
450
   with
451
   | T1 and T2 the scattering dimensions for PDR1 and PDR2
452
   | I1 and I2 the iteration domains
453
   | S1 and S2 the subscripts
454
   | G the global parameters.
455
 
456
   When DIRECTION is set to 1, compute the direct dependence from PDR1
457
   to PDR2, and when DIRECTION is -1, compute the reversed dependence
458
   relation, from PDR2 to PDR1.  */
459
 
460
static ppl_Pointset_Powerset_C_Polyhedron_t
461
dependence_polyhedron_1 (poly_dr_p pdr1, poly_dr_p pdr2,
462
                         int direction, bool original_scattering_p)
463
{
464
  poly_bb_p pbb1 = PDR_PBB (pdr1);
465
  poly_bb_p pbb2 = PDR_PBB (pdr2);
466
  scop_p scop = PBB_SCOP (pbb1);
467
  graphite_dim_t tdim1 = original_scattering_p ?
468
    pbb_nb_scattering_orig (pbb1) : pbb_nb_scattering_transform (pbb1);
469
  graphite_dim_t tdim2 = original_scattering_p ?
470
    pbb_nb_scattering_orig (pbb2) : pbb_nb_scattering_transform (pbb2);
471
  graphite_dim_t ddim1 = pbb_dim_iter_domain (pbb1);
472
  graphite_dim_t ddim2 = pbb_dim_iter_domain (pbb2);
473
  graphite_dim_t sdim1 = PDR_NB_SUBSCRIPTS (pdr1) + 1;
474
  graphite_dim_t sdim2 = PDR_NB_SUBSCRIPTS (pdr2) + 1;
475
  graphite_dim_t gdim = scop_nb_params (scop);
476
  graphite_dim_t dim1 = pdr_dim (pdr1);
477
  graphite_dim_t dim2 = pdr_dim (pdr2);
478
  graphite_dim_t dim = tdim1 + tdim2 + dim1 + dim2 - gdim;
479
  ppl_Pointset_Powerset_C_Polyhedron_t res;
480
  ppl_Pointset_Powerset_C_Polyhedron_t idr1, idr2;
481
  ppl_Pointset_Powerset_C_Polyhedron_t sc1, sc2, dreq;
482
 
483
  gcc_assert (PBB_SCOP (pbb1) == PBB_SCOP (pbb2));
484
 
485
  combine_context_id_scat (&sc1, pbb1, original_scattering_p);
486
  combine_context_id_scat (&sc2, pbb2, original_scattering_p);
487
 
488
  ppl_insert_dimensions_pointset (sc1, tdim1 + ddim1,
489
                                  tdim2 + ddim2 + sdim1 + sdim2);
490
 
491
  ppl_insert_dimensions_pointset (sc2, 0, tdim1 + ddim1);
492
  ppl_insert_dimensions_pointset (sc2, tdim1 + ddim1 + tdim2 + ddim2,
493
                                  sdim1 + sdim2);
494
 
495
  idr1 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr1), ddim1, ddim1 + gdim,
496
                               tdim1, tdim2 + ddim2);
497
  idr2 = map_dr_into_dep_poly (dim, PDR_ACCESSES (pdr2), ddim2, ddim2 + gdim,
498
                               tdim1 + ddim1 + tdim2, sdim1);
499
 
500
  /* Now add the subscript equalities.  */
501
  dreq = dr_equality_constraints (dim, tdim1 + ddim1 + tdim2 + ddim2, sdim1);
502
 
503
  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&res, dim, 0);
504
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc1);
505
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, sc2);
506
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr1);
507
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, idr2);
508
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (res, dreq);
509
  ppl_delete_Pointset_Powerset_C_Polyhedron (sc1);
510
  ppl_delete_Pointset_Powerset_C_Polyhedron (sc2);
511
  ppl_delete_Pointset_Powerset_C_Polyhedron (idr1);
512
  ppl_delete_Pointset_Powerset_C_Polyhedron (idr2);
513
  ppl_delete_Pointset_Powerset_C_Polyhedron (dreq);
514
 
515
  if (!ppl_Pointset_Powerset_C_Polyhedron_is_empty (res))
516
    {
517
      ppl_Pointset_Powerset_C_Polyhedron_t lex =
518
        build_lexicographical_constraint (res, dim, MIN (tdim1, tdim2),
519
                                          tdim1 + ddim1, direction);
520
      ppl_delete_Pointset_Powerset_C_Polyhedron (res);
521
      res = lex;
522
    }
523
 
524
  return res;
525
}
526
 
527
/* Build the dependence polyhedron for data references PDR1 and PDR2.
528
   If possible use already cached information.
529
 
530
   When DIRECTION is set to 1, compute the direct dependence from PDR1
531
   to PDR2, and when DIRECTION is -1, compute the reversed dependence
532
   relation, from PDR2 to PDR1.  */
533
 
534
static poly_ddr_p
535
dependence_polyhedron (poly_dr_p pdr1, poly_dr_p pdr2,
536
                       int direction, bool original_scattering_p)
537
{
538
  PTR *x = NULL;
539
  poly_ddr_p res;
540
  ppl_Pointset_Powerset_C_Polyhedron_t ddp;
541
 
542
  /* Return the PDDR from the cache if it already has been computed.  */
543
  if (original_scattering_p)
544
    {
545
      struct poly_ddr tmp;
546
      scop_p scop = PBB_SCOP (PDR_PBB (pdr1));
547
 
548
      tmp.source = pdr1;
549
      tmp.sink = pdr2;
550
      x = htab_find_slot (SCOP_ORIGINAL_PDDRS (scop),
551
                          &tmp, INSERT);
552
 
553
      if (x && *x)
554
        return (poly_ddr_p) *x;
555
    }
556
 
557
  if ((pdr_read_p (pdr1) && pdr_read_p (pdr2))
558
      || PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
559
      || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
560
      || !poly_drs_may_alias_p (pdr1, pdr2))
561
    ddp = NULL;
562
  else
563
    ddp = dependence_polyhedron_1 (pdr1, pdr2, direction,
564
                                   original_scattering_p);
565
 
566
  res = new_poly_ddr (pdr1, pdr2, ddp, original_scattering_p);
567
 
568
  if (!(pdr_read_p (pdr1) && pdr_read_p (pdr2))
569
      && PDR_BASE_OBJECT_SET (pdr1) != PDR_BASE_OBJECT_SET (pdr2)
570
      && poly_drs_may_alias_p (pdr1, pdr2))
571
    PDDR_KIND (res) = unknown_dependence;
572
 
573
  if (original_scattering_p)
574
    *x = res;
575
 
576
  return res;
577
}
578
 
579
/* Return true when the data dependence relation between the data
580
   references PDR1 belonging to PBB1 and PDR2 is part of a
581
   reduction.  */
582
 
583
static inline bool
584
reduction_dr_1 (poly_bb_p pbb1, poly_dr_p pdr1, poly_dr_p pdr2)
585
{
586
  int i;
587
  poly_dr_p pdr;
588
 
589
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr); i++)
590
    if (PDR_TYPE (pdr) == PDR_WRITE)
591
      break;
592
 
593
  return same_pdr_p (pdr, pdr1) && same_pdr_p (pdr, pdr2);
594
}
595
 
596
/* Return true when the data dependence relation between the data
597
   references PDR1 belonging to PBB1 and PDR2 belonging to PBB2 is
598
   part of a reduction.  */
599
 
600
static inline bool
601
reduction_dr_p (poly_dr_p pdr1, poly_dr_p pdr2)
602
{
603
  poly_bb_p pbb1 = PDR_PBB (pdr1);
604
  poly_bb_p pbb2 = PDR_PBB (pdr2);
605
 
606
  if (PBB_IS_REDUCTION (pbb1))
607
    return reduction_dr_1 (pbb1, pdr1, pdr2);
608
 
609
  if (PBB_IS_REDUCTION (pbb2))
610
    return reduction_dr_1 (pbb2, pdr2, pdr1);
611
 
612
  return false;
613
}
614
 
615
/* Returns true when the PBB_TRANSFORMED_SCATTERING functions of PBB1
616
   and PBB2 respect the data dependences of PBB_ORIGINAL_SCATTERING
617
   functions.  */
618
 
619
static bool
620
graphite_legal_transform_dr (poly_dr_p pdr1, poly_dr_p pdr2)
621
{
622
  ppl_Pointset_Powerset_C_Polyhedron_t po, pt;
623
  graphite_dim_t ddim1, otdim1, otdim2, ttdim1, ttdim2;
624
  ppl_Pointset_Powerset_C_Polyhedron_t po_temp;
625
  ppl_dimension_type pdim;
626
  bool is_empty_p;
627
  poly_ddr_p opddr, tpddr;
628
  poly_bb_p pbb1, pbb2;
629
 
630
  if (reduction_dr_p (pdr1, pdr2))
631
    return true;
632
 
633
  /* We build the reverse dependence relation for the transformed
634
     scattering, such that when we intersect it with the original PO,
635
     we get an empty intersection when the transform is legal:
636
     i.e. the transform should reverse no dependences, and so PT, the
637
     reversed transformed PDDR, should have no constraint from PO.  */
638
  opddr = dependence_polyhedron (pdr1, pdr2, 1, true);
639
 
640
  if (PDDR_KIND (opddr) == unknown_dependence)
641
    return false;
642
 
643
    /* There are no dependences between PDR1 and PDR2 in the original
644
       version of the program, or after the transform, so the
645
       transform is legal.  */
646
  if (pddr_is_empty (opddr))
647
    return true;
648
 
649
  tpddr = dependence_polyhedron (pdr1, pdr2, -1, false);
650
 
651
  if (PDDR_KIND (tpddr) == unknown_dependence)
652
    {
653
      free_poly_ddr (tpddr);
654
      return false;
655
    }
656
 
657
  if (pddr_is_empty (tpddr))
658
    {
659
      free_poly_ddr (tpddr);
660
      return true;
661
    }
662
 
663
  po = PDDR_DDP (opddr);
664
  pt = PDDR_DDP (tpddr);
665
 
666
  /* Copy PO into PO_TEMP, such that PO is not destroyed.  PO is
667
     stored in a cache and should not be modified or freed.  */
668
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &pdim);
669
  ppl_new_Pointset_Powerset_C_Polyhedron_from_space_dimension (&po_temp,
670
                                                               pdim, 0);
671
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, po);
672
 
673
  /* Extend PO and PT to have the same dimensions.  */
674
  pbb1 = PDR_PBB (pdr1);
675
  pbb2 = PDR_PBB (pdr2);
676
  ddim1 = pbb_dim_iter_domain (pbb1);
677
  otdim1 = pbb_nb_scattering_orig (pbb1);
678
  otdim2 = pbb_nb_scattering_orig (pbb2);
679
  ttdim1 = pbb_nb_scattering_transform (pbb1);
680
  ttdim2 = pbb_nb_scattering_transform (pbb2);
681
  ppl_insert_dimensions_pointset (po_temp, otdim1, ttdim1);
682
  ppl_insert_dimensions_pointset (po_temp, otdim1 + ttdim1 + ddim1 + otdim2,
683
                                  ttdim2);
684
  ppl_insert_dimensions_pointset (pt, 0, otdim1);
685
  ppl_insert_dimensions_pointset (pt, otdim1 + ttdim1 + ddim1, otdim2);
686
 
687
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (po_temp, pt);
688
  is_empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (po_temp);
689
 
690
  ppl_delete_Pointset_Powerset_C_Polyhedron (po_temp);
691
  free_poly_ddr (tpddr);
692
 
693
  if (dump_file && (dump_flags & TDF_DETAILS))
694
    fprintf (dump_file, "\nloop carries dependency.\n");
695
 
696
  return is_empty_p;
697
}
698
 
699
/* Return true when the data dependence relation for PBB1 and PBB2 is
700
   part of a reduction.  */
701
 
702
static inline bool
703
reduction_ddr_p (poly_bb_p pbb1, poly_bb_p pbb2)
704
{
705
  return pbb1 == pbb2 && PBB_IS_REDUCTION (pbb1);
706
}
707
 
708
/* Iterates over the data references of PBB1 and PBB2 and detect
709
   whether the transformed schedule is correct.  */
710
 
711
static bool
712
graphite_legal_transform_bb (poly_bb_p pbb1, poly_bb_p pbb2)
713
{
714
  int i, j;
715
  poly_dr_p pdr1, pdr2;
716
 
717
  if (!PBB_PDR_DUPLICATES_REMOVED (pbb1))
718
    pbb_remove_duplicate_pdrs (pbb1);
719
 
720
  if (!PBB_PDR_DUPLICATES_REMOVED (pbb2))
721
    pbb_remove_duplicate_pdrs (pbb2);
722
 
723
  if (reduction_ddr_p (pbb1, pbb2))
724
    return true;
725
 
726
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
727
    for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
728
      if (!graphite_legal_transform_dr (pdr1, pdr2))
729
        return false;
730
 
731
  return true;
732
}
733
 
734
/* Iterates over the SCOP and detect whether the transformed schedule
735
   is correct.  */
736
 
737
bool
738
graphite_legal_transform (scop_p scop)
739
{
740
  int i, j;
741
  poly_bb_p pbb1, pbb2;
742
 
743
  timevar_push (TV_GRAPHITE_DATA_DEPS);
744
 
745
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
746
    for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
747
      if (!graphite_legal_transform_bb (pbb1, pbb2))
748
        {
749
          timevar_pop (TV_GRAPHITE_DATA_DEPS);
750
          return false;
751
        }
752
 
753
  timevar_pop (TV_GRAPHITE_DATA_DEPS);
754
  return true;
755
}
756
 
757
/* Returns TRUE when the dependence polyhedron between PDR1 and
758
   PDR2 represents a loop carried dependence at level LEVEL.  */
759
 
760
static bool
761
graphite_carried_dependence_level_k (poly_dr_p pdr1, poly_dr_p pdr2,
762
                                     int level)
763
{
764
  ppl_Pointset_Powerset_C_Polyhedron_t po;
765
  ppl_Pointset_Powerset_C_Polyhedron_t eqpp;
766
  graphite_dim_t tdim1 = pbb_nb_scattering_transform (PDR_PBB (pdr1));
767
  graphite_dim_t ddim1 = pbb_dim_iter_domain (PDR_PBB (pdr1));
768
  ppl_dimension_type dim;
769
  bool empty_p;
770
  poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
771
 
772
  if (PDDR_KIND (pddr) == unknown_dependence)
773
    {
774
      free_poly_ddr (pddr);
775
      return true;
776
    }
777
 
778
  if (pddr_is_empty (pddr))
779
    {
780
      free_poly_ddr (pddr);
781
      return false;
782
    }
783
 
784
  po = PDDR_DDP (pddr);
785
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (po, &dim);
786
  eqpp = build_pairwise_scheduling (dim, level, tdim1 + ddim1, 1);
787
 
788
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (eqpp, po);
789
  empty_p = ppl_Pointset_Powerset_C_Polyhedron_is_empty (eqpp);
790
 
791
  ppl_delete_Pointset_Powerset_C_Polyhedron (eqpp);
792
  free_poly_ddr (pddr);
793
 
794
  return !empty_p;
795
}
796
 
797
/* Check data dependency between PBB1 and PBB2 at level LEVEL.  */
798
 
799
bool
800
dependency_between_pbbs_p (poly_bb_p pbb1, poly_bb_p pbb2, int level)
801
{
802
  int i, j;
803
  poly_dr_p pdr1, pdr2;
804
 
805
  timevar_push (TV_GRAPHITE_DATA_DEPS);
806
 
807
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), i, pdr1); i++)
808
    for (j = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), j, pdr2); j++)
809
      if (graphite_carried_dependence_level_k (pdr1, pdr2, level))
810
        {
811
          timevar_pop (TV_GRAPHITE_DATA_DEPS);
812
          return true;
813
        }
814
 
815
  timevar_pop (TV_GRAPHITE_DATA_DEPS);
816
  return false;
817
}
818
 
819
/* Pretty print to FILE all the original data dependences of SCoP in
820
   DOT format.  */
821
 
822
static void
823
dot_original_deps_stmt_1 (FILE *file, scop_p scop)
824
{
825
  int i, j, k, l;
826
  poly_bb_p pbb1, pbb2;
827
  poly_dr_p pdr1, pdr2;
828
 
829
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
830
    for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
831
      {
832
        for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
833
          for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
834
            if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
835
              {
836
                fprintf (file, "OS%d -> OS%d\n",
837
                         pbb_index (pbb1), pbb_index (pbb2));
838
                goto done;
839
              }
840
      done:;
841
      }
842
}
843
 
844
/* Pretty print to FILE all the transformed data dependences of SCoP in
845
   DOT format.  */
846
 
847
static void
848
dot_transformed_deps_stmt_1 (FILE *file, scop_p scop)
849
{
850
  int i, j, k, l;
851
  poly_bb_p pbb1, pbb2;
852
  poly_dr_p pdr1, pdr2;
853
 
854
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
855
    for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
856
      {
857
        for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
858
          for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
859
            {
860
              poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
861
 
862
              if (!pddr_is_empty (pddr))
863
                {
864
                  fprintf (file, "TS%d -> TS%d\n",
865
                           pbb_index (pbb1), pbb_index (pbb2));
866
 
867
                  free_poly_ddr (pddr);
868
                  goto done;
869
                }
870
 
871
              free_poly_ddr (pddr);
872
            }
873
      done:;
874
      }
875
}
876
 
877
 
878
/* Pretty print to FILE all the data dependences of SCoP in DOT
879
   format.  */
880
 
881
static void
882
dot_deps_stmt_1 (FILE *file, scop_p scop)
883
{
884
  fputs ("digraph all {\n", file);
885
 
886
  dot_original_deps_stmt_1 (file, scop);
887
  dot_transformed_deps_stmt_1 (file, scop);
888
 
889
  fputs ("}\n\n", file);
890
}
891
 
892
/* Pretty print to FILE all the original data dependences of SCoP in
893
   DOT format.  */
894
 
895
static void
896
dot_original_deps (FILE *file, scop_p scop)
897
{
898
  int i, j, k, l;
899
  poly_bb_p pbb1, pbb2;
900
  poly_dr_p pdr1, pdr2;
901
 
902
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
903
    for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
904
      for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
905
        for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
906
          if (!pddr_is_empty (dependence_polyhedron (pdr1, pdr2, 1, true)))
907
            fprintf (file, "OS%d_D%d -> OS%d_D%d\n",
908
                     pbb_index (pbb1), PDR_ID (pdr1),
909
                     pbb_index (pbb2), PDR_ID (pdr2));
910
}
911
 
912
/* Pretty print to FILE all the transformed data dependences of SCoP in
913
   DOT format.  */
914
 
915
static void
916
dot_transformed_deps (FILE *file, scop_p scop)
917
{
918
  int i, j, k, l;
919
  poly_bb_p pbb1, pbb2;
920
  poly_dr_p pdr1, pdr2;
921
 
922
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb1); i++)
923
    for (j = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), j, pbb2); j++)
924
      for (k = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb1), k, pdr1); k++)
925
        for (l = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb2), l, pdr2); l++)
926
          {
927
            poly_ddr_p pddr = dependence_polyhedron (pdr1, pdr2, 1, false);
928
 
929
            if (!pddr_is_empty (pddr))
930
              fprintf (file, "TS%d_D%d -> TS%d_D%d\n",
931
                       pbb_index (pbb1), PDR_ID (pdr1),
932
                       pbb_index (pbb2), PDR_ID (pdr2));
933
 
934
            free_poly_ddr (pddr);
935
          }
936
}
937
 
938
/* Pretty print to FILE all the data dependences of SCoP in DOT
939
   format.  */
940
 
941
static void
942
dot_deps_1 (FILE *file, scop_p scop)
943
{
944
  fputs ("digraph all {\n", file);
945
 
946
  dot_original_deps (file, scop);
947
  dot_transformed_deps (file, scop);
948
 
949
  fputs ("}\n\n", file);
950
}
951
 
952
/* Display all the data dependences in SCoP using dotty.  */
953
 
954
void
955
dot_deps (scop_p scop)
956
{
957
  /* When debugging, enable the following code.  This cannot be used
958
     in production compilers because it calls "system".  */
959
#if 0
960
  int x;
961
  FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
962
  gcc_assert (stream);
963
 
964
  dot_deps_1 (stream, scop);
965
  fclose (stream);
966
 
967
  x = system ("dotty /tmp/scopdeps.dot");
968
#else
969
  dot_deps_1 (stderr, scop);
970
#endif
971
}
972
 
973
/* Display all the statement dependences in SCoP using dotty.  */
974
 
975
void
976
dot_deps_stmt (scop_p scop)
977
{
978
  /* When debugging, enable the following code.  This cannot be used
979
     in production compilers because it calls "system".  */
980
#if 0
981
  int x;
982
  FILE *stream = fopen ("/tmp/scopdeps.dot", "w");
983
  gcc_assert (stream);
984
 
985
  dot_deps_stmt_1 (stream, scop);
986
  fclose (stream);
987
 
988
  x = system ("dotty /tmp/scopdeps.dot");
989
#else
990
  dot_deps_stmt_1 (stderr, scop);
991
#endif
992
}
993
 
994
#endif

powered by: WebSVN 2.1.0

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