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

Subversion Repositories openrisc

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

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

Line No. Rev Author Line
1 280 jeremybenn
/* Graphite polyhedral representation.
2
   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <sebastian.pop@amd.com> and
4
   Tobias Grosser <grosser@fim.uni-passau.de>.
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
#include "config.h"
22
#include "system.h"
23
#include "coretypes.h"
24
#include "tm.h"
25
#include "ggc.h"
26
#include "tree.h"
27
#include "rtl.h"
28
#include "output.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 "value-prof.h"
42
#include "pointer-set.h"
43
#include "gimple.h"
44
#include "params.h"
45
 
46
#ifdef HAVE_cloog
47
#include "cloog/cloog.h"
48
#include "ppl_c.h"
49
#include "sese.h"
50
#include "graphite-ppl.h"
51
#include "graphite.h"
52
#include "graphite-poly.h"
53
#include "graphite-dependences.h"
54
 
55
/* Return the maximal loop depth in SCOP.  */
56
 
57
int
58
scop_max_loop_depth (scop_p scop)
59
{
60
  int i;
61
  poly_bb_p pbb;
62
  int max_nb_loops = 0;
63
 
64
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
65
    {
66
      int nb_loops = pbb_dim_iter_domain (pbb);
67
      if (max_nb_loops < nb_loops)
68
        max_nb_loops = nb_loops;
69
    }
70
 
71
  return max_nb_loops;
72
}
73
 
74
/* Extend the scattering matrix of PBB to MAX_SCATTERING scattering
75
   dimensions.  */
76
 
77
static void
78
extend_scattering (poly_bb_p pbb, int max_scattering)
79
{
80
  ppl_dimension_type nb_old_dims, nb_new_dims;
81
  int nb_added_dims, i;
82
  ppl_Coefficient_t coef;
83
  Value one;
84
 
85
  nb_added_dims = max_scattering - pbb_nb_scattering_transform (pbb);
86
  value_init (one);
87
  value_set_si (one, 1);
88
  ppl_new_Coefficient (&coef);
89
  ppl_assign_Coefficient_from_mpz_t (coef, one);
90
 
91
  gcc_assert (nb_added_dims >= 0);
92
 
93
  nb_old_dims = pbb_nb_scattering_transform (pbb) + pbb_dim_iter_domain (pbb)
94
    + scop_nb_params (PBB_SCOP (pbb));
95
  nb_new_dims = nb_old_dims + nb_added_dims;
96
 
97
  ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb),
98
                         pbb_nb_scattering_transform (pbb), nb_added_dims);
99
  PBB_NB_SCATTERING_TRANSFORM (pbb) += nb_added_dims;
100
 
101
  /* Add identity matrix for the added dimensions.  */
102
  for (i = max_scattering - nb_added_dims; i < max_scattering; i++)
103
    {
104
      ppl_Constraint_t cstr;
105
      ppl_Linear_Expression_t expr;
106
 
107
      ppl_new_Linear_Expression_with_dimension (&expr, nb_new_dims);
108
      ppl_Linear_Expression_add_to_coefficient (expr, i, coef);
109
      ppl_new_Constraint (&cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
110
      ppl_Polyhedron_add_constraint (PBB_TRANSFORMED_SCATTERING (pbb), cstr);
111
      ppl_delete_Constraint (cstr);
112
      ppl_delete_Linear_Expression (expr);
113
    }
114
 
115
  ppl_delete_Coefficient (coef);
116
  value_clear (one);
117
}
118
 
119
/* All scattering matrices in SCOP will have the same number of scattering
120
   dimensions.  */
121
 
122
int
123
unify_scattering_dimensions (scop_p scop)
124
{
125
  int i;
126
  poly_bb_p pbb;
127
  graphite_dim_t max_scattering = 0;
128
 
129
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
130
    max_scattering = MAX (pbb_nb_scattering_transform (pbb), max_scattering);
131
 
132
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
133
    extend_scattering (pbb, max_scattering);
134
 
135
  return max_scattering;
136
}
137
 
138
/* Prints to FILE the scattering function of PBB, at some VERBOSITY
139
   level.  */
140
 
141
static void
142
print_scattering_function_1 (FILE *file, poly_bb_p pbb, int verbosity)
143
{
144
  graphite_dim_t i;
145
 
146
  if (verbosity > 0)
147
    {
148
      fprintf (file, "# scattering bb_%d (\n", pbb_index (pbb));
149
      fprintf (file, "#  eq");
150
 
151
      for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
152
        fprintf (file, "     s%d", (int) i);
153
 
154
      for (i = 0; i < pbb_nb_local_vars (pbb); i++)
155
        fprintf (file, "    lv%d", (int) i);
156
 
157
      for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
158
        fprintf (file, "     i%d", (int) i);
159
 
160
      for (i = 0; i < pbb_nb_params (pbb); i++)
161
        fprintf (file, "     p%d", (int) i);
162
 
163
      fprintf (file, "    cst\n");
164
    }
165
 
166
  /* Number of disjunct components.  Remove this when
167
     PBB_TRANSFORMED_SCATTERING will be a pointset_powerset.  */
168
  fprintf (file, "1\n");
169
  ppl_print_polyhedron_matrix (file, PBB_TRANSFORMED_SCATTERING (pbb)
170
                               ? PBB_TRANSFORMED_SCATTERING (pbb)
171
                               : PBB_ORIGINAL_SCATTERING (pbb));
172
 
173
  if (verbosity > 0)
174
    fprintf (file, "#)\n");
175
}
176
 
177
/* Prints to FILE the scattering function of PBB, at some VERBOSITY
178
   level.  */
179
 
180
void
181
print_scattering_function (FILE *file, poly_bb_p pbb, int verbosity)
182
{
183
  if (!PBB_TRANSFORMED (pbb))
184
    return;
185
 
186
  if (PBB_TRANSFORMED_SCATTERING (pbb)
187
      || PBB_ORIGINAL_SCATTERING (pbb))
188
    {
189
      if (verbosity > 0)
190
        fprintf (file, "# Scattering function is provided\n");
191
 
192
      fprintf (file, "1\n");
193
    }
194
  else
195
    {
196
      if (verbosity > 0)
197
        fprintf (file, "# Scattering function is not provided\n");
198
 
199
      fprintf (file, "0\n");
200
      return;
201
    }
202
 
203
  print_scattering_function_1 (file, pbb, verbosity);
204
}
205
 
206
/* Prints to FILE the iteration domain of PBB, at some VERBOSITY
207
   level.  */
208
 
209
void
210
print_iteration_domain (FILE *file, poly_bb_p pbb, int verbosity)
211
{
212
  print_pbb_domain (file, pbb, verbosity);
213
}
214
 
215
/* Prints to FILE the scattering functions of every PBB of SCOP.  */
216
 
217
void
218
print_scattering_functions (FILE *file, scop_p scop, int verbosity)
219
{
220
  int i;
221
  poly_bb_p pbb;
222
 
223
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
224
    print_scattering_function (file, pbb, verbosity);
225
}
226
 
227
/* Prints to FILE the iteration domains of every PBB of SCOP, at some
228
   VERBOSITY level.  */
229
 
230
void
231
print_iteration_domains (FILE *file, scop_p scop, int verbosity)
232
{
233
  int i;
234
  poly_bb_p pbb;
235
 
236
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
237
    print_iteration_domain (file, pbb, verbosity);
238
}
239
 
240
/* Prints to STDERR the scattering function of PBB, at some VERBOSITY
241
   level.  */
242
 
243
void
244
debug_scattering_function (poly_bb_p pbb, int verbosity)
245
{
246
  print_scattering_function (stderr, pbb, verbosity);
247
}
248
 
249
/* Prints to STDERR the iteration domain of PBB, at some VERBOSITY
250
   level.  */
251
 
252
void
253
debug_iteration_domain (poly_bb_p pbb, int verbosity)
254
{
255
  print_iteration_domain (stderr, pbb, verbosity);
256
}
257
 
258
/* Prints to STDERR the scattering functions of every PBB of SCOP, at
259
   some VERBOSITY level.  */
260
 
261
void
262
debug_scattering_functions (scop_p scop, int verbosity)
263
{
264
  print_scattering_functions (stderr, scop, verbosity);
265
}
266
 
267
/* Prints to STDERR the iteration domains of every PBB of SCOP, at
268
   some VERBOSITY level.  */
269
 
270
void
271
debug_iteration_domains (scop_p scop, int verbosity)
272
{
273
  print_iteration_domains (stderr, scop, verbosity);
274
}
275
 
276
 
277
/* Apply graphite transformations to all the basic blocks of SCOP.  */
278
 
279
bool
280
apply_poly_transforms (scop_p scop)
281
{
282
  bool transform_done = false;
283
 
284
  /* Generate code even if we did not apply any real transformation.
285
     This also allows to check the performance for the identity
286
     transformation: GIMPLE -> GRAPHITE -> GIMPLE
287
     Keep in mind that CLooG optimizes in control, so the loop structure
288
     may change, even if we only use -fgraphite-identity.  */
289
  if (flag_graphite_identity)
290
    transform_done = true;
291
 
292
  if (flag_loop_parallelize_all)
293
    transform_done = true;
294
 
295
  if (flag_loop_block)
296
    transform_done |= scop_do_block (scop);
297
  else
298
    {
299
      if (flag_loop_strip_mine)
300
        transform_done |= scop_do_strip_mine (scop);
301
 
302
      if (flag_loop_interchange)
303
        transform_done |= scop_do_interchange (scop);
304
    }
305
 
306
  return transform_done;
307
}
308
 
309
/* Returns true when it PDR1 is a duplicate of PDR2: same PBB, and
310
   their ACCESSES, TYPE, and NB_SUBSCRIPTS are the same.  */
311
 
312
static inline bool
313
can_collapse_pdrs (poly_dr_p pdr1, poly_dr_p pdr2)
314
{
315
  bool res;
316
  ppl_Pointset_Powerset_C_Polyhedron_t af1, af2, diff;
317
 
318
  if (PDR_PBB (pdr1) != PDR_PBB (pdr2)
319
      || PDR_NB_SUBSCRIPTS (pdr1) != PDR_NB_SUBSCRIPTS (pdr2)
320
      || PDR_TYPE (pdr1) != PDR_TYPE (pdr2))
321
    return false;
322
 
323
  af1 = PDR_ACCESSES (pdr1);
324
  af2 = PDR_ACCESSES (pdr2);
325
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
326
    (&diff, af1);
327
  ppl_Pointset_Powerset_C_Polyhedron_difference_assign (diff, af2);
328
 
329
  res = ppl_Pointset_Powerset_C_Polyhedron_is_empty (diff);
330
  ppl_delete_Pointset_Powerset_C_Polyhedron (diff);
331
  return res;
332
}
333
 
334
/* Removes duplicated data references in PBB.  */
335
 
336
void
337
pbb_remove_duplicate_pdrs (poly_bb_p pbb)
338
{
339
  int i, j;
340
  poly_dr_p pdr1, pdr2;
341
  unsigned n = VEC_length (poly_dr_p, PBB_DRS (pbb));
342
  VEC (poly_dr_p, heap) *collapsed = VEC_alloc (poly_dr_p, heap, n);
343
 
344
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr1); i++)
345
    for (j = 0; VEC_iterate (poly_dr_p, collapsed, j, pdr2); j++)
346
      if (!can_collapse_pdrs (pdr1, pdr2))
347
        VEC_quick_push (poly_dr_p, collapsed, pdr1);
348
 
349
  VEC_free (poly_dr_p, heap, collapsed);
350
  PBB_PDR_DUPLICATES_REMOVED (pbb) = true;
351
}
352
 
353
/* Create a new polyhedral data reference and add it to PBB.  It is
354
   defined by its ACCESSES, its TYPE, and the number of subscripts
355
   NB_SUBSCRIPTS.  */
356
 
357
void
358
new_poly_dr (poly_bb_p pbb, int dr_base_object_set,
359
             ppl_Pointset_Powerset_C_Polyhedron_t accesses,
360
             enum poly_dr_type type, void *cdr, graphite_dim_t nb_subscripts)
361
{
362
  static int id = 0;
363
  poly_dr_p pdr = XNEW (struct poly_dr);
364
 
365
  PDR_ID (pdr) = id++;
366
  PDR_BASE_OBJECT_SET (pdr) = dr_base_object_set;
367
  PDR_NB_REFS (pdr) = 1;
368
  PDR_PBB (pdr) = pbb;
369
  PDR_ACCESSES (pdr) = accesses;
370
  PDR_TYPE (pdr) = type;
371
  PDR_CDR (pdr) = cdr;
372
  PDR_NB_SUBSCRIPTS (pdr) = nb_subscripts;
373
  VEC_safe_push (poly_dr_p, heap, PBB_DRS (pbb), pdr);
374
}
375
 
376
/* Free polyhedral data reference PDR.  */
377
 
378
void
379
free_poly_dr (poly_dr_p pdr)
380
{
381
  ppl_delete_Pointset_Powerset_C_Polyhedron (PDR_ACCESSES (pdr));
382
  XDELETE (pdr);
383
}
384
 
385
/* Create a new polyhedral black box.  */
386
 
387
void
388
new_poly_bb (scop_p scop, void *black_box, bool reduction)
389
{
390
  poly_bb_p pbb = XNEW (struct poly_bb);
391
 
392
  PBB_DOMAIN (pbb) = NULL;
393
  PBB_SCOP (pbb) = scop;
394
  pbb_set_black_box (pbb, black_box);
395
  PBB_TRANSFORMED (pbb) = NULL;
396
  PBB_SAVED (pbb) = NULL;
397
  PBB_ORIGINAL (pbb) = NULL;
398
  PBB_DRS (pbb) = VEC_alloc (poly_dr_p, heap, 3);
399
  PBB_IS_REDUCTION (pbb) = reduction;
400
  PBB_PDR_DUPLICATES_REMOVED (pbb) = false;
401
  VEC_safe_push (poly_bb_p, heap, SCOP_BBS (scop), pbb);
402
}
403
 
404
/* Free polyhedral black box.  */
405
 
406
void
407
free_poly_bb (poly_bb_p pbb)
408
{
409
  int i;
410
  poly_dr_p pdr;
411
 
412
  ppl_delete_Pointset_Powerset_C_Polyhedron (PBB_DOMAIN (pbb));
413
 
414
  if (PBB_TRANSFORMED (pbb))
415
    poly_scattering_free (PBB_TRANSFORMED (pbb));
416
 
417
  if (PBB_SAVED (pbb))
418
    poly_scattering_free (PBB_SAVED (pbb));
419
 
420
  if (PBB_ORIGINAL (pbb))
421
    poly_scattering_free (PBB_ORIGINAL (pbb));
422
 
423
  if (PBB_DRS (pbb))
424
    for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
425
      free_poly_dr (pdr);
426
 
427
  VEC_free (poly_dr_p, heap, PBB_DRS (pbb));
428
  XDELETE (pbb);
429
}
430
 
431
static void
432
print_pdr_access_layout (FILE *file, poly_dr_p pdr)
433
{
434
  graphite_dim_t i;
435
 
436
  fprintf (file, "#  eq");
437
 
438
  for (i = 0; i < pdr_dim_iter_domain (pdr); i++)
439
    fprintf (file, "     i%d", (int) i);
440
 
441
  for (i = 0; i < pdr_nb_params (pdr); i++)
442
    fprintf (file, "     p%d", (int) i);
443
 
444
  fprintf (file, "  alias");
445
 
446
  for (i = 0; i < PDR_NB_SUBSCRIPTS (pdr); i++)
447
    fprintf (file, "   sub%d", (int) i);
448
 
449
  fprintf (file, "    cst\n");
450
}
451
 
452
/* Prints to FILE the polyhedral data reference PDR, at some VERBOSITY
453
   level.  */
454
 
455
void
456
print_pdr (FILE *file, poly_dr_p pdr, int verbosity)
457
{
458
  if (verbosity > 1)
459
    {
460
      fprintf (file, "# pdr_%d (", PDR_ID (pdr));
461
 
462
      switch (PDR_TYPE (pdr))
463
        {
464
        case PDR_READ:
465
          fprintf (file, "read \n");
466
          break;
467
 
468
        case PDR_WRITE:
469
          fprintf (file, "write \n");
470
          break;
471
 
472
        case PDR_MAY_WRITE:
473
          fprintf (file, "may_write \n");
474
          break;
475
 
476
        default:
477
          gcc_unreachable ();
478
        }
479
 
480
      dump_data_reference (file, (data_reference_p) PDR_CDR (pdr));
481
    }
482
 
483
  if (verbosity > 0)
484
    {
485
      fprintf (file, "# data accesses (\n");
486
      print_pdr_access_layout (file, pdr);
487
    }
488
 
489
  ppl_print_powerset_matrix (file, PDR_ACCESSES (pdr));
490
 
491
  if (verbosity > 0)
492
    fprintf (file, "#)\n");
493
 
494
  if (verbosity > 1)
495
    fprintf (file, "#)\n");
496
}
497
 
498
/* Prints to STDERR the polyhedral data reference PDR, at some
499
   VERBOSITY level.  */
500
 
501
void
502
debug_pdr (poly_dr_p pdr, int verbosity)
503
{
504
  print_pdr (stderr, pdr, verbosity);
505
}
506
 
507
/* Creates a new SCOP containing REGION.  */
508
 
509
scop_p
510
new_scop (void *region)
511
{
512
  scop_p scop = XNEW (struct scop);
513
 
514
  SCOP_CONTEXT (scop) = NULL;
515
  scop_set_region (scop, region);
516
  SCOP_BBS (scop) = VEC_alloc (poly_bb_p, heap, 3);
517
  SCOP_ORIGINAL_PDDRS (scop) = htab_create (10, hash_poly_ddr_p,
518
                                            eq_poly_ddr_p, free_poly_ddr);
519
  SCOP_ORIGINAL_SCHEDULE (scop) = NULL;
520
  SCOP_TRANSFORMED_SCHEDULE (scop) = NULL;
521
  SCOP_SAVED_SCHEDULE (scop) = NULL;
522
  POLY_SCOP_P (scop) = false;
523
 
524
  return scop;
525
}
526
 
527
/* Deletes SCOP.  */
528
 
529
void
530
free_scop (scop_p scop)
531
{
532
  int i;
533
  poly_bb_p pbb;
534
 
535
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
536
    free_poly_bb (pbb);
537
 
538
  VEC_free (poly_bb_p, heap, SCOP_BBS (scop));
539
 
540
  if (SCOP_CONTEXT (scop))
541
    ppl_delete_Pointset_Powerset_C_Polyhedron (SCOP_CONTEXT (scop));
542
 
543
  htab_delete (SCOP_ORIGINAL_PDDRS (scop));
544
  free_lst (SCOP_ORIGINAL_SCHEDULE (scop));
545
  free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
546
  free_lst (SCOP_SAVED_SCHEDULE (scop));
547
  XDELETE (scop);
548
}
549
 
550
/* Print to FILE the domain of PBB, at some VERBOSITY level.  */
551
 
552
void
553
print_pbb_domain (FILE *file, poly_bb_p pbb, int verbosity)
554
{
555
  graphite_dim_t i;
556
  gimple_bb_p gbb = PBB_BLACK_BOX (pbb);
557
 
558
  if (!PBB_DOMAIN (pbb))
559
    return;
560
 
561
  if (verbosity > 0)
562
    {
563
      fprintf (file, "# Iteration domain of bb_%d (\n", GBB_BB (gbb)->index);
564
      fprintf (file, "#  eq");
565
 
566
      for (i = 0; i < pbb_dim_iter_domain (pbb); i++)
567
        fprintf (file, "     i%d", (int) i);
568
 
569
      for (i = 0; i < pbb_nb_params (pbb); i++)
570
        fprintf (file, "     p%d", (int) i);
571
 
572
      fprintf (file, "    cst\n");
573
    }
574
 
575
  if (PBB_DOMAIN (pbb))
576
    ppl_print_powerset_matrix (file, PBB_DOMAIN (pbb));
577
  else
578
    fprintf (file, "0\n");
579
 
580
  if (verbosity > 0)
581
    fprintf (file, "#)\n");
582
}
583
 
584
/* Dump the cases of a graphite basic block GBB on FILE.  */
585
 
586
static void
587
dump_gbb_cases (FILE *file, gimple_bb_p gbb)
588
{
589
  int i;
590
  gimple stmt;
591
  VEC (gimple, heap) *cases;
592
 
593
  if (!gbb)
594
    return;
595
 
596
  cases = GBB_CONDITION_CASES (gbb);
597
  if (VEC_empty (gimple, cases))
598
    return;
599
 
600
  fprintf (file, "# cases bb_%d (\n", GBB_BB (gbb)->index);
601
 
602
  for (i = 0; VEC_iterate (gimple, cases, i, stmt); i++)
603
    {
604
      fprintf (file, "# ");
605
      print_gimple_stmt (file, stmt, 0, 0);
606
    }
607
 
608
  fprintf (file, "#)\n");
609
}
610
 
611
/* Dump conditions of a graphite basic block GBB on FILE.  */
612
 
613
static void
614
dump_gbb_conditions (FILE *file, gimple_bb_p gbb)
615
{
616
  int i;
617
  gimple stmt;
618
  VEC (gimple, heap) *conditions;
619
 
620
  if (!gbb)
621
    return;
622
 
623
  conditions = GBB_CONDITIONS (gbb);
624
  if (VEC_empty (gimple, conditions))
625
    return;
626
 
627
  fprintf (file, "# conditions bb_%d (\n", GBB_BB (gbb)->index);
628
 
629
  for (i = 0; VEC_iterate (gimple, conditions, i, stmt); i++)
630
    {
631
      fprintf (file, "# ");
632
      print_gimple_stmt (file, stmt, 0, 0);
633
    }
634
 
635
  fprintf (file, "#)\n");
636
}
637
 
638
/* Print to FILE all the data references of PBB, at some VERBOSITY
639
   level.  */
640
 
641
void
642
print_pdrs (FILE *file, poly_bb_p pbb, int verbosity)
643
{
644
  int i;
645
  poly_dr_p pdr;
646
  int nb_reads = 0;
647
  int nb_writes = 0;
648
 
649
  if (VEC_length (poly_dr_p, PBB_DRS (pbb)) == 0)
650
    {
651
      if (verbosity > 0)
652
        fprintf (file, "# Access informations are not provided\n");\
653
      fprintf (file, "0\n");
654
      return;
655
    }
656
 
657
  if (verbosity > 1)
658
    fprintf (file, "# Data references (\n");
659
 
660
  if (verbosity > 0)
661
    fprintf (file, "# Access informations are provided\n");
662
  fprintf (file, "1\n");
663
 
664
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
665
    if (PDR_TYPE (pdr) == PDR_READ)
666
      nb_reads++;
667
    else
668
      nb_writes++;
669
 
670
  if (verbosity > 1)
671
    fprintf (file, "# Read data references (\n");
672
 
673
  if (verbosity > 0)
674
    fprintf (file, "# Read access informations\n");
675
  fprintf (file, "%d\n", nb_reads);
676
 
677
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
678
    if (PDR_TYPE (pdr) == PDR_READ)
679
      print_pdr (file, pdr, verbosity);
680
 
681
  if (verbosity > 1)
682
    fprintf (file, "#)\n");
683
 
684
  if (verbosity > 1)
685
    fprintf (file, "# Write data references (\n");
686
 
687
  if (verbosity > 0)
688
    fprintf (file, "# Write access informations\n");
689
  fprintf (file, "%d\n", nb_writes);
690
 
691
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
692
    if (PDR_TYPE (pdr) != PDR_READ)
693
      print_pdr (file, pdr, verbosity);
694
 
695
  if (verbosity > 1)
696
    fprintf (file, "#)\n");
697
 
698
  if (verbosity > 1)
699
    fprintf (file, "#)\n");
700
}
701
 
702
/* Print to STDERR all the data references of PBB.  */
703
 
704
void
705
debug_pdrs (poly_bb_p pbb, int verbosity)
706
{
707
  print_pdrs (stderr, pbb, verbosity);
708
}
709
 
710
/* Print to FILE the body of PBB, at some VERBOSITY level.  */
711
 
712
static void
713
print_pbb_body (FILE *file, poly_bb_p pbb, int verbosity)
714
{
715
  if (verbosity > 1)
716
    fprintf (file, "# Body (\n");
717
 
718
  if (verbosity > 0)
719
    fprintf (file, "# Statement body is provided\n");
720
  fprintf (file, "1\n");
721
 
722
  if (verbosity > 0)
723
    fprintf (file, "# Original iterator names\n# Iterator names are not provided yet.\n");
724
 
725
  if (verbosity > 0)
726
    fprintf (file, "# Statement body\n");
727
 
728
  fprintf (file, "{\n");
729
  dump_bb (pbb_bb (pbb), file, 0);
730
  fprintf (file, "}\n");
731
 
732
  if (verbosity > 1)
733
    fprintf (file, "#)\n");
734
}
735
 
736
/* Print to FILE the domain and scattering function of PBB, at some
737
   VERBOSITY level.  */
738
 
739
void
740
print_pbb (FILE *file, poly_bb_p pbb, int verbosity)
741
{
742
  if (verbosity > 1)
743
    {
744
      fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
745
      dump_gbb_conditions (file, PBB_BLACK_BOX (pbb));
746
      dump_gbb_cases (file, PBB_BLACK_BOX (pbb));
747
    }
748
 
749
  print_pbb_domain (file, pbb, verbosity);
750
  print_scattering_function (file, pbb, verbosity);
751
  print_pdrs (file, pbb, verbosity);
752
  print_pbb_body (file, pbb, verbosity);
753
 
754
  if (verbosity > 1)
755
    fprintf (file, "#)\n");
756
}
757
 
758
/* Print to FILE the parameters of SCOP, at some VERBOSITY level.  */
759
 
760
void
761
print_scop_params (FILE *file, scop_p scop, int verbosity)
762
{
763
  int i;
764
  tree t;
765
 
766
  if (verbosity > 1)
767
    fprintf (file, "# parameters (\n");
768
 
769
  if (VEC_length (tree, SESE_PARAMS (SCOP_REGION (scop))))
770
    {
771
      if (verbosity > 0)
772
        fprintf (file, "# Parameter names are provided\n");
773
 
774
      fprintf (file, "1\n");
775
 
776
      if (verbosity > 0)
777
        fprintf (file, "# Parameter names\n");
778
    }
779
  else
780
    {
781
      if (verbosity > 0)
782
        fprintf (file, "# Parameter names are not provided\n");
783
      fprintf (file, "0\n");
784
    }
785
 
786
  for (i = 0; VEC_iterate (tree, SESE_PARAMS (SCOP_REGION (scop)), i, t); i++)
787
    {
788
      print_generic_expr (file, t, 0);
789
      fprintf (file, " ");
790
    }
791
 
792
  fprintf (file, "\n");
793
 
794
  if (verbosity > 1)
795
    fprintf (file, "#)\n");
796
}
797
 
798
/* Print to FILE the context of SCoP, at some VERBOSITY level.  */
799
 
800
void
801
print_scop_context (FILE *file, scop_p scop, int verbosity)
802
{
803
  graphite_dim_t i;
804
 
805
  if (verbosity > 0)
806
    {
807
      fprintf (file, "# Context (\n");
808
      fprintf (file, "#  eq");
809
 
810
      for (i = 0; i < scop_nb_params (scop); i++)
811
        fprintf (file, "     p%d", (int) i);
812
 
813
      fprintf (file, "    cst\n");
814
    }
815
 
816
  if (SCOP_CONTEXT (scop))
817
    ppl_print_powerset_matrix (file, SCOP_CONTEXT (scop));
818
  else
819
    fprintf (file, "0 %d\n", (int) scop_nb_params (scop) + 2);
820
 
821
  if (verbosity > 0)
822
    fprintf (file, "# )\n");
823
}
824
 
825
/* Print to FILE the SCOP, at some VERBOSITY level.  */
826
 
827
void
828
print_scop (FILE *file, scop_p scop, int verbosity)
829
{
830
  int i;
831
  poly_bb_p pbb;
832
 
833
  fprintf (file, "SCoP #(\n");
834
  fprintf (file, "# Language\nGimple\n");
835
  print_scop_context (file, scop, verbosity);
836
  print_scop_params (file, scop, verbosity);
837
 
838
  if (verbosity > 0)
839
    fprintf (file, "# Number of statements\n");
840
 
841
  fprintf (file, "%d\n",VEC_length (poly_bb_p, SCOP_BBS (scop)));
842
 
843
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
844
    print_pbb (file, pbb, verbosity);
845
 
846
  if (verbosity > 1)
847
    {
848
      fprintf (file, "# original_lst (\n");
849
      print_lst (file, SCOP_ORIGINAL_SCHEDULE (scop), 0);
850
      fprintf (file, "\n#)\n");
851
 
852
      fprintf (file, "# transformed_lst (\n");
853
      print_lst (file, SCOP_TRANSFORMED_SCHEDULE (scop), 0);
854
      fprintf (file, "\n#)\n");
855
    }
856
 
857
  fprintf (file, "#)\n");
858
}
859
 
860
/* Print to FILE the input file that CLooG would expect as input, at
861
   some VERBOSITY level.  */
862
 
863
void
864
print_cloog (FILE *file, scop_p scop, int verbosity)
865
{
866
  int i;
867
  poly_bb_p pbb;
868
 
869
  fprintf (file, "# SCoP (generated by GCC/Graphite\n");
870
  if (verbosity > 0)
871
    fprintf (file, "# CLooG output language\n");
872
  fprintf (file, "c\n");
873
 
874
  print_scop_context (file, scop, verbosity);
875
  print_scop_params (file, scop, verbosity);
876
 
877
  if (verbosity > 0)
878
    fprintf (file, "# Number of statements\n");
879
 
880
  fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
881
 
882
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
883
    {
884
      if (verbosity > 1)
885
        fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
886
 
887
      print_pbb_domain (file, pbb, verbosity);
888
      fprintf (file, "0 0 0");
889
 
890
      if (verbosity > 0)
891
        fprintf (file, "# For future CLooG options.\n");
892
      else
893
        fprintf (file, "\n");
894
 
895
      if (verbosity > 1)
896
        fprintf (file, "#)\n");
897
    }
898
 
899
  fprintf (file, "0");
900
  if (verbosity > 0)
901
    fprintf (file, "# Don't set the iterator names.\n");
902
  else
903
    fprintf (file, "\n");
904
 
905
  if (verbosity > 0)
906
    fprintf (file, "# Number of scattering functions\n");
907
 
908
  fprintf (file, "%d\n", VEC_length (poly_bb_p, SCOP_BBS (scop)));
909
  unify_scattering_dimensions (scop);
910
 
911
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
912
    {
913
      if (!PBB_TRANSFORMED (pbb)
914
          || !(PBB_TRANSFORMED_SCATTERING (pbb)
915
               || PBB_ORIGINAL_SCATTERING (pbb)))
916
        continue;
917
 
918
      if (verbosity > 1)
919
        fprintf (file, "# pbb_%d (\n", pbb_index (pbb));
920
 
921
      print_scattering_function_1 (file, pbb, verbosity);
922
 
923
      if (verbosity > 1)
924
        fprintf (file, "#)\n");
925
    }
926
 
927
  fprintf (file, "0");
928
  if (verbosity > 0)
929
    fprintf (file, "# Don't set the scattering dimension names.\n");
930
  else
931
    fprintf (file, "\n");
932
 
933
  fprintf (file, "#)\n");
934
}
935
 
936
/* Print to STDERR the domain of PBB, at some VERBOSITY level.  */
937
 
938
void
939
debug_pbb_domain (poly_bb_p pbb, int verbosity)
940
{
941
  print_pbb_domain (stderr, pbb, verbosity);
942
}
943
 
944
/* Print to FILE the domain and scattering function of PBB, at some
945
   VERBOSITY level.  */
946
 
947
void
948
debug_pbb (poly_bb_p pbb, int verbosity)
949
{
950
  print_pbb (stderr, pbb, verbosity);
951
}
952
 
953
/* Print to STDERR the context of SCOP, at some VERBOSITY level.  */
954
 
955
void
956
debug_scop_context (scop_p scop, int verbosity)
957
{
958
  print_scop_context (stderr, scop, verbosity);
959
}
960
 
961
/* Print to STDERR the SCOP, at some VERBOSITY level.  */
962
 
963
void
964
debug_scop (scop_p scop, int verbosity)
965
{
966
  print_scop (stderr, scop, verbosity);
967
}
968
 
969
/* Print to STDERR the SCOP under CLooG format, at some VERBOSITY
970
   level.  */
971
 
972
void
973
debug_cloog (scop_p scop, int verbosity)
974
{
975
  print_cloog (stderr, scop, verbosity);
976
}
977
 
978
/* Print to STDERR the parameters of SCOP, at some VERBOSITY
979
   level.  */
980
 
981
void
982
debug_scop_params (scop_p scop, int verbosity)
983
{
984
  print_scop_params (stderr, scop, verbosity);
985
}
986
 
987
 
988
/* The dimension in the transformed scattering polyhedron of PBB
989
   containing the scattering iterator for the loop at depth LOOP_DEPTH.  */
990
 
991
ppl_dimension_type
992
psct_scattering_dim_for_loop_depth (poly_bb_p pbb, graphite_dim_t loop_depth)
993
{
994
  ppl_const_Constraint_System_t pcs;
995
  ppl_Constraint_System_const_iterator_t cit, cend;
996
  ppl_const_Constraint_t cstr;
997
  ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
998
  ppl_dimension_type iter = psct_iterator_dim (pbb, loop_depth);
999
  ppl_Linear_Expression_t expr;
1000
  ppl_Coefficient_t coef;
1001
  Value val;
1002
  graphite_dim_t i;
1003
 
1004
  value_init (val);
1005
  ppl_new_Coefficient (&coef);
1006
  ppl_Polyhedron_get_constraints (ph, &pcs);
1007
  ppl_new_Constraint_System_const_iterator (&cit);
1008
  ppl_new_Constraint_System_const_iterator (&cend);
1009
 
1010
  for (ppl_Constraint_System_begin (pcs, cit),
1011
         ppl_Constraint_System_end (pcs, cend);
1012
       !ppl_Constraint_System_const_iterator_equal_test (cit, cend);
1013
       ppl_Constraint_System_const_iterator_increment (cit))
1014
    {
1015
      ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
1016
      ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
1017
      ppl_Linear_Expression_coefficient (expr, iter, coef);
1018
      ppl_Coefficient_to_mpz_t (coef, val);
1019
 
1020
      if (value_zero_p (val))
1021
        {
1022
          ppl_delete_Linear_Expression (expr);
1023
          continue;
1024
        }
1025
 
1026
      for (i = 0; i < pbb_nb_scattering_transform (pbb); i++)
1027
        {
1028
          ppl_dimension_type scatter = psct_scattering_dim (pbb, i);
1029
 
1030
          ppl_Linear_Expression_coefficient (expr, scatter, coef);
1031
          ppl_Coefficient_to_mpz_t (coef, val);
1032
 
1033
          if (value_notzero_p (val))
1034
            {
1035
              value_clear (val);
1036
              ppl_delete_Linear_Expression (expr);
1037
              ppl_delete_Coefficient (coef);
1038
              ppl_delete_Constraint_System_const_iterator (cit);
1039
              ppl_delete_Constraint_System_const_iterator (cend);
1040
 
1041
              return scatter;
1042
            }
1043
        }
1044
    }
1045
 
1046
  gcc_unreachable ();
1047
}
1048
 
1049
/* Returns the number of iterations NITER of the loop around PBB at
1050
   depth LOOP_DEPTH.  */
1051
 
1052
void
1053
pbb_number_of_iterations (poly_bb_p pbb,
1054
                          graphite_dim_t loop_depth,
1055
                          Value niter)
1056
{
1057
  ppl_Linear_Expression_t le;
1058
  ppl_dimension_type dim;
1059
 
1060
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
1061
  ppl_new_Linear_Expression_with_dimension (&le, dim);
1062
  ppl_set_coef (le, pbb_iterator_dim (pbb, loop_depth), 1);
1063
  value_set_si (niter, -1);
1064
  ppl_max_for_le_pointset (PBB_DOMAIN (pbb), le, niter);
1065
  ppl_delete_Linear_Expression (le);
1066
}
1067
 
1068
/* Returns the number of iterations NITER of the loop around PBB at
1069
   time(scattering) dimension TIME_DEPTH.  */
1070
 
1071
void
1072
pbb_number_of_iterations_at_time (poly_bb_p pbb,
1073
                                  graphite_dim_t time_depth,
1074
                                  Value niter)
1075
{
1076
  ppl_Pointset_Powerset_C_Polyhedron_t ext_domain, sctr;
1077
  ppl_Linear_Expression_t le;
1078
  ppl_dimension_type dim;
1079
 
1080
  /* Takes together domain and scattering polyhedrons, and composes
1081
     them into the bigger polyhedron that has the following format:
1082
 
1083
     t0..t_{n-1} | l0..l_{nlcl-1} | i0..i_{niter-1} | g0..g_{nparm-1}
1084
 
1085
     where
1086
     | t0..t_{n-1} are time dimensions (scattering dimensions)
1087
     | l0..l_{nclc-1} are local variables in scattering function
1088
     | i0..i_{niter-1} are original iteration variables
1089
     | g0..g_{nparam-1} are global parameters.  */
1090
 
1091
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron (&sctr,
1092
      PBB_TRANSFORMED_SCATTERING (pbb));
1093
 
1094
  /* Extend the iteration domain with the scattering dimensions:
1095
     0..0 | 0..0 | i0..i_{niter-1} | g0..g_{nparm-1}.   */
1096
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1097
    (&ext_domain, PBB_DOMAIN (pbb));
1098
  ppl_insert_dimensions_pointset (ext_domain, 0,
1099
                                  pbb_nb_scattering_transform (pbb)
1100
                                  + pbb_nb_local_vars (pbb));
1101
 
1102
  /* Add to sctr the extended domain.  */
1103
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (sctr, ext_domain);
1104
 
1105
  /* Extract the number of iterations.  */
1106
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (sctr, &dim);
1107
  ppl_new_Linear_Expression_with_dimension (&le, dim);
1108
  ppl_set_coef (le, time_depth, 1);
1109
  value_set_si (niter, -1);
1110
  ppl_max_for_le_pointset (sctr, le, niter);
1111
 
1112
  ppl_delete_Linear_Expression (le);
1113
  ppl_delete_Pointset_Powerset_C_Polyhedron (sctr);
1114
  ppl_delete_Pointset_Powerset_C_Polyhedron (ext_domain);
1115
}
1116
 
1117
/* Translates LOOP to LST.  */
1118
 
1119
static lst_p
1120
loop_to_lst (loop_p loop, VEC (poly_bb_p, heap) *bbs, int *i)
1121
{
1122
  poly_bb_p pbb;
1123
  VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1124
 
1125
  for (; VEC_iterate (poly_bb_p, bbs, *i, pbb); (*i)++)
1126
    {
1127
      lst_p stmt;
1128
      basic_block bb = GBB_BB (PBB_BLACK_BOX (pbb));
1129
 
1130
      if (bb->loop_father == loop)
1131
        stmt = new_lst_stmt (pbb);
1132
      else if (flow_bb_inside_loop_p (loop, bb))
1133
        {
1134
          loop_p next = loop->inner;
1135
 
1136
          while (next && !flow_bb_inside_loop_p (next, bb))
1137
            next = next->next;
1138
 
1139
          stmt = loop_to_lst (next, bbs, i);
1140
        }
1141
      else
1142
        {
1143
          (*i)--;
1144
          return new_lst_loop (seq);
1145
        }
1146
 
1147
      VEC_safe_push (lst_p, heap, seq, stmt);
1148
    }
1149
 
1150
  return new_lst_loop (seq);
1151
}
1152
 
1153
/* Reads the original scattering of the SCOP and returns an LST
1154
   representing it.  */
1155
 
1156
void
1157
scop_to_lst (scop_p scop)
1158
{
1159
  lst_p res;
1160
  int i, n = VEC_length (poly_bb_p, SCOP_BBS (scop));
1161
  VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
1162
  sese region = SCOP_REGION (scop);
1163
 
1164
  for (i = 0; i < n; i++)
1165
    {
1166
      poly_bb_p pbb = VEC_index (poly_bb_p, SCOP_BBS (scop), i);
1167
      loop_p loop = outermost_loop_in_sese (region, GBB_BB (PBB_BLACK_BOX (pbb)));
1168
 
1169
      if (loop_in_sese_p (loop, region))
1170
        res = loop_to_lst (loop, SCOP_BBS (scop), &i);
1171
      else
1172
        res = new_lst_stmt (pbb);
1173
 
1174
      VEC_safe_push (lst_p, heap, seq, res);
1175
    }
1176
 
1177
  res = new_lst_loop (seq);
1178
  SCOP_ORIGINAL_SCHEDULE (scop) = res;
1179
  SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (res);
1180
}
1181
 
1182
/* Print to FILE on a new line COLUMN white spaces.  */
1183
 
1184
static void
1185
lst_indent_to (FILE *file, int column)
1186
{
1187
  int i;
1188
 
1189
  if (column > 0)
1190
    fprintf (file, "\n#");
1191
 
1192
  for (i = 0; i < column; i++)
1193
    fprintf (file, " ");
1194
}
1195
 
1196
/* Print LST to FILE with INDENT spaces of indentation.  */
1197
 
1198
void
1199
print_lst (FILE *file, lst_p lst, int indent)
1200
{
1201
  if (!lst)
1202
    return;
1203
 
1204
  lst_indent_to (file, indent);
1205
 
1206
  if (LST_LOOP_P (lst))
1207
    {
1208
      int i;
1209
      lst_p l;
1210
 
1211
      if (LST_LOOP_FATHER (lst))
1212
        fprintf (file, "%d (loop", lst_dewey_number (lst));
1213
      else
1214
        fprintf (file, "#(root");
1215
 
1216
      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1217
        print_lst (file, l, indent + 2);
1218
 
1219
      fprintf (file, ")");
1220
    }
1221
  else
1222
    fprintf (file, "%d stmt_%d", lst_dewey_number (lst), pbb_index (LST_PBB (lst)));
1223
}
1224
 
1225
/* Print LST to STDERR.  */
1226
 
1227
void
1228
debug_lst (lst_p lst)
1229
{
1230
  print_lst (stderr, lst, 0);
1231
}
1232
 
1233
/* Pretty print to FILE the loop statement tree LST in DOT format.  */
1234
 
1235
static void
1236
dot_lst_1 (FILE *file, lst_p lst)
1237
{
1238
  if (!lst)
1239
    return;
1240
 
1241
  if (LST_LOOP_P (lst))
1242
    {
1243
      int i;
1244
      lst_p l;
1245
 
1246
      if (!LST_LOOP_FATHER (lst))
1247
        fprintf (file, "L -> L_%d_%d\n",
1248
                 lst_depth (lst),
1249
                 lst_dewey_number (lst));
1250
      else
1251
        fprintf (file, "L_%d_%d -> L_%d_%d\n",
1252
                 lst_depth (LST_LOOP_FATHER (lst)),
1253
                 lst_dewey_number (LST_LOOP_FATHER (lst)),
1254
                 lst_depth (lst),
1255
                 lst_dewey_number (lst));
1256
 
1257
      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1258
        dot_lst_1 (file, l);
1259
    }
1260
 
1261
  else
1262
    fprintf (file, "L_%d_%d -> S_%d\n",
1263
             lst_depth (LST_LOOP_FATHER (lst)),
1264
             lst_dewey_number (LST_LOOP_FATHER (lst)),
1265
             pbb_index (LST_PBB (lst)));
1266
 
1267
}
1268
 
1269
/* Display the LST using dotty.  */
1270
 
1271
void
1272
dot_lst (lst_p lst)
1273
{
1274
  /* When debugging, enable the following code.  This cannot be used
1275
     in production compilers because it calls "system".  */
1276
#if 0
1277
  int x;
1278
  FILE *stream = fopen ("/tmp/lst.dot", "w");
1279
  gcc_assert (stream);
1280
 
1281
  fputs ("digraph all {\n", stream);
1282
  dot_lst_1 (stream, lst);
1283
  fputs ("}\n\n", stream);
1284
  fclose (stream);
1285
 
1286
  x = system ("dotty /tmp/lst.dot");
1287
#else
1288
  fputs ("digraph all {\n", stderr);
1289
  dot_lst_1 (stderr, lst);
1290
  fputs ("}\n\n", stderr);
1291
 
1292
#endif
1293
}
1294
 
1295
#endif
1296
 

powered by: WebSVN 2.1.0

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