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

Subversion Repositories openrisc

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

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
 
22
#ifndef GCC_GRAPHITE_POLY_H
23
#define GCC_GRAPHITE_POLY_H
24
 
25
typedef struct poly_dr *poly_dr_p;
26
DEF_VEC_P(poly_dr_p);
27
DEF_VEC_ALLOC_P (poly_dr_p, heap);
28
 
29
typedef struct poly_bb *poly_bb_p;
30
DEF_VEC_P(poly_bb_p);
31
DEF_VEC_ALLOC_P (poly_bb_p, heap);
32
 
33
typedef struct scop *scop_p;
34
DEF_VEC_P(scop_p);
35
DEF_VEC_ALLOC_P (scop_p, heap);
36
 
37
typedef ppl_dimension_type graphite_dim_t;
38
 
39
static inline graphite_dim_t pbb_dim_iter_domain (const struct poly_bb *);
40
static inline graphite_dim_t pbb_nb_params (const struct poly_bb *);
41
static inline graphite_dim_t scop_nb_params (scop_p);
42
 
43
/* A data reference can write or read some memory or we
44
   just know it may write some memory.  */
45
enum poly_dr_type
46
{
47
  PDR_READ,
48
  /* PDR_MAY_READs are represented using PDR_READS.  This does not
49
     limit the expressiveness.  */
50
  PDR_WRITE,
51
  PDR_MAY_WRITE
52
};
53
 
54
struct poly_dr
55
{
56
  /* An identifier for this PDR.  */
57
  int id;
58
 
59
  /* The number of data refs identical to this one in the PBB.  */
60
  int nb_refs;
61
 
62
  /* A pointer to compiler's data reference description.  */
63
  void *compiler_dr;
64
 
65
  /* A pointer to the PBB that contains this data reference.  */
66
  poly_bb_p pbb;
67
 
68
  enum poly_dr_type type;
69
 
70
  /* The access polyhedron contains the polyhedral space this data
71
     reference will access.
72
 
73
     The polyhedron contains these dimensions:
74
 
75
     - The alias set (a):
76
     Every memory access is classified in at least one alias set.
77
 
78
     - The subscripts (s_0, ..., s_n):
79
     The memory is accessed using zero or more subscript dimensions.
80
 
81
     - The iteration domain (variables and parameters)
82
 
83
     Do not hardcode the dimensions.  Use the following accessor functions:
84
     - pdr_alias_set_dim
85
     - pdr_subscript_dim
86
     - pdr_iterator_dim
87
     - pdr_parameter_dim
88
 
89
     Example:
90
 
91
     | int A[1335][123];
92
     | int *p = malloc ();
93
     |
94
     | k = ...
95
     | for i
96
     |   {
97
     |     if (unknown_function ())
98
     |       p = A;
99
     |       ... = p[?][?];
100
     |     for j
101
     |       A[i][j+k] = m;
102
     |   }
103
 
104
     The data access A[i][j+k] in alias set "5" is described like this:
105
 
106
     | i   j   k   a  s0  s1   1
107
     | 0   0   0   1   0   0  -5     =  0
108
     |-1   0   0   0   1   0   0     =  0
109
     | 0  -1  -1   0   0   1   0     =  0
110
     | 0   0   0   0   1   0   0     >= 0  # The last four lines describe the
111
     | 0   0   0   0   0   1   0     >= 0  # array size.
112
     | 0   0   0   0  -1   0 1335    >= 0
113
     | 0   0   0   0   0  -1 123     >= 0
114
 
115
     The pointer "*p" in alias set "5" and "7" is described as a union of
116
     polyhedron:
117
 
118
 
119
     | i   k   a  s0   1
120
     | 0   0   1   0  -5   =  0
121
     | 0   0   0   1   0   >= 0
122
 
123
     "or"
124
 
125
     | i   k   a  s0   1
126
     | 0   0   1   0  -7   =  0
127
     | 0   0   0   1   0   >= 0
128
 
129
     "*p" accesses all of the object allocated with 'malloc'.
130
 
131
     The scalar data access "m" is represented as an array with zero subscript
132
     dimensions.
133
 
134
     | i   j   k   a   1
135
     | 0   0   0  -1   15  = 0 */
136
  ppl_Pointset_Powerset_C_Polyhedron_t accesses;
137
 
138
  /* Data reference's base object set number, we must assure 2 pdrs are in the
139
     same base object set before dependency checking.  */
140
  int dr_base_object_set;
141
 
142
  /* The number of subscripts.  */
143
  graphite_dim_t nb_subscripts;
144
};
145
 
146
#define PDR_ID(PDR) (PDR->id)
147
#define PDR_NB_REFS(PDR) (PDR->nb_refs)
148
#define PDR_CDR(PDR) (PDR->compiler_dr)
149
#define PDR_PBB(PDR) (PDR->pbb)
150
#define PDR_TYPE(PDR) (PDR->type)
151
#define PDR_ACCESSES(PDR) (PDR->accesses)
152
#define PDR_BASE_OBJECT_SET(PDR) (PDR->dr_base_object_set)
153
#define PDR_NB_SUBSCRIPTS(PDR) (PDR->nb_subscripts)
154
 
155
void new_poly_dr (poly_bb_p, int, ppl_Pointset_Powerset_C_Polyhedron_t,
156
                  enum poly_dr_type, void *, graphite_dim_t);
157
void free_poly_dr (poly_dr_p);
158
void debug_pdr (poly_dr_p, int);
159
void print_pdr (FILE *, poly_dr_p, int);
160
static inline scop_p pdr_scop (poly_dr_p pdr);
161
 
162
/* The dimension of the PDR_ACCESSES polyhedron of PDR.  */
163
 
164
static inline ppl_dimension_type
165
pdr_dim (poly_dr_p pdr)
166
{
167
  ppl_dimension_type dim;
168
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PDR_ACCESSES (pdr),
169
                                                      &dim);
170
  return dim;
171
}
172
 
173
/* The dimension of the iteration domain of the scop of PDR.  */
174
 
175
static inline ppl_dimension_type
176
pdr_dim_iter_domain (poly_dr_p pdr)
177
{
178
  return pbb_dim_iter_domain (PDR_PBB (pdr));
179
}
180
 
181
/* The number of parameters of the scop of PDR.  */
182
 
183
static inline ppl_dimension_type
184
pdr_nb_params (poly_dr_p pdr)
185
{
186
  return scop_nb_params (pdr_scop (pdr));
187
}
188
 
189
/* The dimension of the alias set in PDR.  */
190
 
191
static inline ppl_dimension_type
192
pdr_alias_set_dim (poly_dr_p pdr)
193
{
194
  poly_bb_p pbb = PDR_PBB (pdr);
195
 
196
  return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb);
197
}
198
 
199
/* The dimension in PDR containing subscript S.  */
200
 
201
static inline ppl_dimension_type
202
pdr_subscript_dim (poly_dr_p pdr, graphite_dim_t s)
203
{
204
  poly_bb_p pbb = PDR_PBB (pdr);
205
 
206
  return pbb_dim_iter_domain (pbb) + pbb_nb_params (pbb) + 1 + s;
207
}
208
 
209
/* The dimension in PDR containing the loop iterator ITER.  */
210
 
211
static inline ppl_dimension_type
212
pdr_iterator_dim (poly_dr_p pdr ATTRIBUTE_UNUSED, graphite_dim_t iter)
213
{
214
  return iter;
215
}
216
 
217
/* The dimension in PDR containing parameter PARAM.  */
218
 
219
static inline ppl_dimension_type
220
pdr_parameter_dim (poly_dr_p pdr, graphite_dim_t param)
221
{
222
  poly_bb_p pbb = PDR_PBB (pdr);
223
 
224
  return pbb_dim_iter_domain (pbb) + param;
225
}
226
 
227
/* Returns true when PDR is a "read".  */
228
 
229
static inline bool
230
pdr_read_p (poly_dr_p pdr)
231
{
232
  return PDR_TYPE (pdr) == PDR_READ;
233
}
234
 
235
/* Returns true when PDR is a "write".  */
236
 
237
static inline bool
238
pdr_write_p (poly_dr_p pdr)
239
{
240
  return PDR_TYPE (pdr) == PDR_WRITE;
241
}
242
 
243
/* Returns true when PDR is a "may write".  */
244
 
245
static inline bool
246
pdr_may_write_p (poly_dr_p pdr)
247
{
248
  return PDR_TYPE (pdr) == PDR_MAY_WRITE;
249
}
250
 
251
/* Return true when PDR1 and PDR2 are similar data accesses: they have
252
   the same base array, and the same access functions.  */
253
 
254
static inline bool
255
same_pdr_p (poly_dr_p pdr1, poly_dr_p pdr2)
256
{
257
  return PDR_TYPE (pdr1) == PDR_TYPE (pdr2)
258
    && PDR_NB_SUBSCRIPTS (pdr1) == PDR_NB_SUBSCRIPTS (pdr2)
259
    && PDR_BASE_OBJECT_SET (pdr1) == PDR_BASE_OBJECT_SET (pdr2);
260
}
261
 
262
typedef struct poly_scattering *poly_scattering_p;
263
 
264
struct poly_scattering
265
{
266
  /* The scattering function containing the transformations: the
267
     layout of this polyhedron is: T|I|G with T the transform
268
     scattering, I the iteration domain, G the context parameters.  */
269
  ppl_Polyhedron_t scattering;
270
 
271
  /* The number of local variables.  */
272
  int nb_local_variables;
273
 
274
  /* The number of scattering dimensions.  */
275
  int nb_scattering;
276
};
277
 
278
/* POLY_BB represents a blackbox in the polyhedral model.  */
279
 
280
struct poly_bb
281
{
282
  /* Pointer to a basic block or a statement in the compiler.  */
283
  void *black_box;
284
 
285
  /* Pointer to the SCOP containing this PBB.  */
286
  scop_p scop;
287
 
288
  /* The iteration domain of this bb.  The layout of this polyhedron
289
     is I|G with I the iteration domain, G the context parameters.
290
 
291
     Example:
292
 
293
     for (i = a - 7*b + 8; i <= 3*a + 13*b + 20; i++)
294
       for (j = 2; j <= 2*i + 5; j++)
295
         for (k = 0; k <= 5; k++)
296
           S (i,j,k)
297
 
298
     Loop iterators: i, j, k
299
     Parameters: a, b
300
 
301
     | i >=  a -  7b +  8
302
     | i <= 3a + 13b + 20
303
     | j >= 2
304
     | j <= 2i + 5
305
     | k >= 0
306
     | k <= 5
307
 
308
     The number of variables in the DOMAIN may change and is not
309
     related to the number of loops in the original code.  */
310
  ppl_Pointset_Powerset_C_Polyhedron_t domain;
311
 
312
  /* The data references we access.  */
313
  VEC (poly_dr_p, heap) *drs;
314
 
315
  /* The original scattering.  */
316
  poly_scattering_p original;
317
 
318
  /* The transformed scattering.  */
319
  poly_scattering_p transformed;
320
 
321
  /* A copy of the transformed scattering.  */
322
  poly_scattering_p saved;
323
 
324
  /* True when the PDR duplicates have already been removed.  */
325
  bool pdr_duplicates_removed;
326
 
327
  /* True when this PBB contains only a reduction statement.  */
328
  bool is_reduction;
329
};
330
 
331
#define PBB_BLACK_BOX(PBB) ((gimple_bb_p) PBB->black_box)
332
#define PBB_SCOP(PBB) (PBB->scop)
333
#define PBB_DOMAIN(PBB) (PBB->domain)
334
#define PBB_DRS(PBB) (PBB->drs)
335
#define PBB_ORIGINAL(PBB) (PBB->original)
336
#define PBB_ORIGINAL_SCATTERING(PBB) (PBB->original->scattering)
337
#define PBB_TRANSFORMED(PBB) (PBB->transformed)
338
#define PBB_TRANSFORMED_SCATTERING(PBB) (PBB->transformed->scattering)
339
#define PBB_SAVED(PBB) (PBB->saved)
340
#define PBB_NB_LOCAL_VARIABLES(PBB) (PBB->transformed->nb_local_variables)
341
#define PBB_NB_SCATTERING_TRANSFORM(PBB) (PBB->transformed->nb_scattering)
342
#define PBB_PDR_DUPLICATES_REMOVED(PBB) (PBB->pdr_duplicates_removed)
343
#define PBB_IS_REDUCTION(PBB) (PBB->is_reduction)
344
 
345
extern void new_poly_bb (scop_p, void *, bool);
346
extern void free_poly_bb (poly_bb_p);
347
extern void debug_loop_vec (poly_bb_p);
348
extern void schedule_to_scattering (poly_bb_p, int);
349
extern void print_pbb_domain (FILE *, poly_bb_p, int);
350
extern void print_pbb (FILE *, poly_bb_p, int);
351
extern void print_scop_context (FILE *, scop_p, int);
352
extern void print_scop (FILE *, scop_p, int);
353
extern void print_cloog (FILE *, scop_p, int);
354
extern void debug_pbb_domain (poly_bb_p, int);
355
extern void debug_pbb (poly_bb_p, int);
356
extern void print_pdrs (FILE *, poly_bb_p, int);
357
extern void debug_pdrs (poly_bb_p, int);
358
extern void debug_scop_context (scop_p, int);
359
extern void debug_scop (scop_p, int);
360
extern void debug_cloog (scop_p, int);
361
extern void print_scop_params (FILE *, scop_p, int);
362
extern void debug_scop_params (scop_p, int);
363
extern void print_iteration_domain (FILE *, poly_bb_p, int);
364
extern void print_iteration_domains (FILE *, scop_p, int);
365
extern void debug_iteration_domain (poly_bb_p, int);
366
extern void debug_iteration_domains (scop_p, int);
367
extern bool scop_do_interchange (scop_p);
368
extern bool scop_do_strip_mine (scop_p);
369
extern bool scop_do_block (scop_p);
370
extern void pbb_number_of_iterations (poly_bb_p, graphite_dim_t, Value);
371
extern void pbb_number_of_iterations_at_time (poly_bb_p, graphite_dim_t, Value);
372
extern void pbb_remove_duplicate_pdrs (poly_bb_p);
373
 
374
/* Return the number of write data references in PBB.  */
375
 
376
static inline int
377
number_of_write_pdrs (poly_bb_p pbb)
378
{
379
  int res = 0;
380
  int i;
381
  poly_dr_p pdr;
382
 
383
  for (i = 0; VEC_iterate (poly_dr_p, PBB_DRS (pbb), i, pdr); i++)
384
    if (PDR_TYPE (pdr) == PDR_WRITE)
385
      res++;
386
 
387
  return res;
388
}
389
 
390
/* The basic block of the PBB.  */
391
static inline basic_block
392
pbb_bb (poly_bb_p pbb)
393
{
394
  return GBB_BB (PBB_BLACK_BOX (pbb));
395
}
396
 
397
/* The index of the PBB.  */
398
 
399
static inline int
400
pbb_index (poly_bb_p pbb)
401
{
402
  return pbb_bb (pbb)->index;
403
}
404
 
405
/* The loop of the PBB.  */
406
 
407
static inline loop_p
408
pbb_loop (poly_bb_p pbb)
409
{
410
  return gbb_loop (PBB_BLACK_BOX (pbb));
411
}
412
 
413
/* The scop that contains the PDR.  */
414
 
415
static inline scop_p
416
pdr_scop (poly_dr_p pdr)
417
{
418
  return PBB_SCOP (PDR_PBB (pdr));
419
}
420
 
421
/* Set black box of PBB to BLACKBOX.  */
422
 
423
static inline void
424
pbb_set_black_box (poly_bb_p pbb, void *black_box)
425
{
426
  pbb->black_box = black_box;
427
}
428
 
429
/* The number of loops around PBB: the dimension of the iteration
430
   domain.  */
431
 
432
static inline graphite_dim_t
433
pbb_dim_iter_domain (const struct poly_bb *pbb)
434
{
435
  scop_p scop = PBB_SCOP (pbb);
436
  ppl_dimension_type dim;
437
 
438
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (PBB_DOMAIN (pbb), &dim);
439
  return dim - scop_nb_params (scop);
440
}
441
 
442
/* The number of params defined in PBB.  */
443
 
444
static inline graphite_dim_t
445
pbb_nb_params (const struct poly_bb *pbb)
446
{
447
  scop_p scop = PBB_SCOP (pbb);
448
 
449
  return scop_nb_params (scop);
450
}
451
 
452
/* The number of scattering dimensions in the SCATTERING polyhedron
453
   of a PBB for a given SCOP.  */
454
 
455
static inline graphite_dim_t
456
pbb_nb_scattering_orig (const struct poly_bb *pbb)
457
{
458
  return 2 * pbb_dim_iter_domain (pbb) + 1;
459
}
460
 
461
/* The number of scattering dimensions in PBB.  */
462
 
463
static inline graphite_dim_t
464
pbb_nb_scattering_transform (const struct poly_bb *pbb)
465
{
466
  return PBB_NB_SCATTERING_TRANSFORM (pbb);
467
}
468
 
469
/* The number of dynamic scattering dimensions in PBB.  */
470
 
471
static inline graphite_dim_t
472
pbb_nb_dynamic_scattering_transform (const struct poly_bb *pbb)
473
{
474
  /* This function requires the 2d + 1 scattering format to be
475
     invariant during all transformations.  */
476
  gcc_assert (PBB_NB_SCATTERING_TRANSFORM (pbb) % 2);
477
  return PBB_NB_SCATTERING_TRANSFORM (pbb) / 2;
478
}
479
 
480
/* Returns the number of local variables used in the transformed
481
   scattering polyhedron of PBB.  */
482
 
483
static inline graphite_dim_t
484
pbb_nb_local_vars (const struct poly_bb *pbb)
485
{
486
  /* For now we do not have any local variables, as we do not do strip
487
     mining for example.  */
488
  return PBB_NB_LOCAL_VARIABLES (pbb);
489
}
490
 
491
/* The dimension in the domain of PBB containing the iterator ITER.  */
492
 
493
static inline ppl_dimension_type
494
pbb_iterator_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t iter)
495
{
496
  return iter;
497
}
498
 
499
/* The dimension in the domain of PBB containing the iterator ITER.  */
500
 
501
static inline ppl_dimension_type
502
pbb_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
503
{
504
  return param
505
    + pbb_dim_iter_domain (pbb);
506
}
507
 
508
/* The dimension in the original scattering polyhedron of PBB
509
   containing the scattering iterator SCATTER.  */
510
 
511
static inline ppl_dimension_type
512
psco_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
513
{
514
  gcc_assert (scatter < pbb_nb_scattering_orig (pbb));
515
  return scatter;
516
}
517
 
518
/* The dimension in the transformed scattering polyhedron of PBB
519
   containing the scattering iterator SCATTER.  */
520
 
521
static inline ppl_dimension_type
522
psct_scattering_dim (poly_bb_p pbb ATTRIBUTE_UNUSED, graphite_dim_t scatter)
523
{
524
  gcc_assert (scatter <= pbb_nb_scattering_transform (pbb));
525
  return scatter;
526
}
527
 
528
ppl_dimension_type psct_scattering_dim_for_loop_depth (poly_bb_p,
529
                                                       graphite_dim_t);
530
 
531
/* The dimension in the transformed scattering polyhedron of PBB of
532
   the local variable LV.  */
533
 
534
static inline ppl_dimension_type
535
psct_local_var_dim (poly_bb_p pbb, graphite_dim_t lv)
536
{
537
  gcc_assert (lv <= pbb_nb_local_vars (pbb));
538
  return lv + pbb_nb_scattering_transform (pbb);
539
}
540
 
541
/* The dimension in the original scattering polyhedron of PBB
542
   containing the loop iterator ITER.  */
543
 
544
static inline ppl_dimension_type
545
psco_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
546
{
547
  gcc_assert (iter < pbb_dim_iter_domain (pbb));
548
  return iter + pbb_nb_scattering_orig (pbb);
549
}
550
 
551
/* The dimension in the transformed scattering polyhedron of PBB
552
   containing the loop iterator ITER.  */
553
 
554
static inline ppl_dimension_type
555
psct_iterator_dim (poly_bb_p pbb, graphite_dim_t iter)
556
{
557
  gcc_assert (iter < pbb_dim_iter_domain (pbb));
558
  return iter
559
    + pbb_nb_scattering_transform (pbb)
560
    + pbb_nb_local_vars (pbb);
561
}
562
 
563
/* The dimension in the original scattering polyhedron of PBB
564
   containing parameter PARAM.  */
565
 
566
static inline ppl_dimension_type
567
psco_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
568
{
569
  gcc_assert (param < pbb_nb_params (pbb));
570
  return param
571
    + pbb_nb_scattering_orig (pbb)
572
    + pbb_dim_iter_domain (pbb);
573
}
574
 
575
/* The dimension in the transformed scattering polyhedron of PBB
576
   containing parameter PARAM.  */
577
 
578
static inline ppl_dimension_type
579
psct_parameter_dim (poly_bb_p pbb, graphite_dim_t param)
580
{
581
  gcc_assert (param < pbb_nb_params (pbb));
582
  return param
583
    + pbb_nb_scattering_transform (pbb)
584
    + pbb_nb_local_vars (pbb)
585
    + pbb_dim_iter_domain (pbb);
586
}
587
 
588
/* The scattering dimension of PBB corresponding to the dynamic level
589
   LEVEL.  */
590
 
591
static inline ppl_dimension_type
592
psct_dynamic_dim (poly_bb_p pbb, graphite_dim_t level)
593
{
594
  graphite_dim_t result = 1 + 2 * level;
595
 
596
  gcc_assert (result < pbb_nb_scattering_transform (pbb));
597
  return result;
598
}
599
 
600
/* The scattering dimension of PBB corresponding to the static
601
   sequence of the loop level LEVEL.  */
602
 
603
static inline ppl_dimension_type
604
psct_static_dim (poly_bb_p pbb, graphite_dim_t level)
605
{
606
  graphite_dim_t result = 2 * level;
607
 
608
  gcc_assert (result < pbb_nb_scattering_transform (pbb));
609
  return result;
610
}
611
 
612
/* Adds to the transformed scattering polyhedron of PBB a new local
613
   variable and returns its index.  */
614
 
615
static inline graphite_dim_t
616
psct_add_local_variable (poly_bb_p pbb)
617
{
618
  graphite_dim_t nlv = pbb_nb_local_vars (pbb);
619
  ppl_dimension_type lv_column = psct_local_var_dim (pbb, nlv);
620
  ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), lv_column, 1);
621
  PBB_NB_LOCAL_VARIABLES (pbb) += 1;
622
  return nlv;
623
}
624
 
625
/* Adds a dimension to the transformed scattering polyhedron of PBB at
626
   INDEX.  */
627
 
628
static inline void
629
psct_add_scattering_dimension (poly_bb_p pbb, ppl_dimension_type index)
630
{
631
  gcc_assert (index < pbb_nb_scattering_transform (pbb));
632
 
633
  ppl_insert_dimensions (PBB_TRANSFORMED_SCATTERING (pbb), index, 1);
634
  PBB_NB_SCATTERING_TRANSFORM (pbb) += 1;
635
}
636
 
637
typedef struct lst *lst_p;
638
DEF_VEC_P(lst_p);
639
DEF_VEC_ALLOC_P (lst_p, heap);
640
 
641
/* Loops and Statements Tree.  */
642
struct lst {
643
 
644
  /* LOOP_P is true when an LST node is a loop.  */
645
  bool loop_p;
646
 
647
  /* A pointer to the loop that contains this node.  */
648
  lst_p loop_father;
649
 
650
  /* The sum of all the memory strides for an LST loop.  */
651
  Value memory_strides;
652
 
653
  /* Loop nodes contain a sequence SEQ of LST nodes, statements
654
     contain a pointer to their polyhedral representation PBB.  */
655
  union {
656
    poly_bb_p pbb;
657
    VEC (lst_p, heap) *seq;
658
  } node;
659
};
660
 
661
#define LST_LOOP_P(LST) ((LST)->loop_p)
662
#define LST_LOOP_FATHER(LST) ((LST)->loop_father)
663
#define LST_PBB(LST) ((LST)->node.pbb)
664
#define LST_SEQ(LST) ((LST)->node.seq)
665
#define LST_LOOP_MEMORY_STRIDES(LST) ((LST)->memory_strides)
666
 
667
void scop_to_lst (scop_p);
668
void print_lst (FILE *, lst_p, int);
669
void debug_lst (lst_p);
670
void dot_lst (lst_p);
671
 
672
/* Creates a new LST loop with SEQ.  */
673
 
674
static inline lst_p
675
new_lst_loop (VEC (lst_p, heap) *seq)
676
{
677
  lst_p lst = XNEW (struct lst);
678
  int i;
679
  lst_p l;
680
 
681
  LST_LOOP_P (lst) = true;
682
  LST_SEQ (lst) = seq;
683
  LST_LOOP_FATHER (lst) = NULL;
684
  value_init (LST_LOOP_MEMORY_STRIDES (lst));
685
  value_set_si (LST_LOOP_MEMORY_STRIDES (lst), -1);
686
 
687
  for (i = 0; VEC_iterate (lst_p, seq, i, l); i++)
688
    LST_LOOP_FATHER (l) = lst;
689
 
690
  return lst;
691
}
692
 
693
/* Creates a new LST statement with PBB.  */
694
 
695
static inline lst_p
696
new_lst_stmt (poly_bb_p pbb)
697
{
698
  lst_p lst = XNEW (struct lst);
699
 
700
  LST_LOOP_P (lst) = false;
701
  LST_PBB (lst) = pbb;
702
  LST_LOOP_FATHER (lst) = NULL;
703
  return lst;
704
}
705
 
706
/* Frees the memory used by LST.  */
707
 
708
static inline void
709
free_lst (lst_p lst)
710
{
711
  if (!lst)
712
    return;
713
 
714
  if (LST_LOOP_P (lst))
715
    {
716
      int i;
717
      lst_p l;
718
 
719
      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
720
        free_lst (l);
721
 
722
      value_clear (LST_LOOP_MEMORY_STRIDES (lst));
723
      VEC_free (lst_p, heap, LST_SEQ (lst));
724
    }
725
 
726
  free (lst);
727
}
728
 
729
/* Returns a copy of LST.  */
730
 
731
static inline lst_p
732
copy_lst (lst_p lst)
733
{
734
  if (!lst)
735
    return NULL;
736
 
737
  if (LST_LOOP_P (lst))
738
    {
739
      int i;
740
      lst_p l;
741
      VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 5);
742
 
743
      for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
744
        VEC_safe_push (lst_p, heap, seq, copy_lst (l));
745
 
746
      return new_lst_loop (seq);
747
    }
748
 
749
  return new_lst_stmt (LST_PBB (lst));
750
}
751
 
752
/* Adds a new loop under the loop LST.  */
753
 
754
static inline void
755
lst_add_loop_under_loop (lst_p lst)
756
{
757
  VEC (lst_p, heap) *seq = VEC_alloc (lst_p, heap, 1);
758
  lst_p l = new_lst_loop (LST_SEQ (lst));
759
 
760
  gcc_assert (LST_LOOP_P (lst));
761
 
762
  LST_LOOP_FATHER (l) = lst;
763
  VEC_quick_push (lst_p, seq, l);
764
  LST_SEQ (lst) = seq;
765
}
766
 
767
/* Returns the loop depth of LST.  */
768
 
769
static inline int
770
lst_depth (lst_p lst)
771
{
772
  if (!lst)
773
    return -2;
774
 
775
  /* The depth of the outermost "fake" loop is -1.  This outermost
776
     loop does not have a loop father and it is just a container, as
777
     in the loop representation of GCC.  */
778
  if (!LST_LOOP_FATHER (lst))
779
    return -1;
780
 
781
  return lst_depth (LST_LOOP_FATHER (lst)) + 1;
782
}
783
 
784
/* Returns the Dewey number for LST.  */
785
 
786
static inline int
787
lst_dewey_number (lst_p lst)
788
{
789
  int i;
790
  lst_p l;
791
 
792
  if (!lst)
793
    return -1;
794
 
795
  if (!LST_LOOP_FATHER (lst))
796
    return 0;
797
 
798
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (LST_LOOP_FATHER (lst)), i, l); i++)
799
    if (l == lst)
800
      return i;
801
 
802
  return -1;
803
}
804
 
805
/* Returns the Dewey number of LST at depth DEPTH.  */
806
 
807
static inline int
808
lst_dewey_number_at_depth (lst_p lst, int depth)
809
{
810
  gcc_assert (lst && depth >= 0 && lst_depth (lst) <= depth);
811
 
812
  if (lst_depth (lst) == depth)
813
    return lst_dewey_number (lst);
814
 
815
  return lst_dewey_number_at_depth (LST_LOOP_FATHER (lst), depth);
816
}
817
 
818
/* Returns the predecessor of LST in the sequence of its loop father.
819
   Returns NULL if LST is the first statement in the sequence.  */
820
 
821
static inline lst_p
822
lst_pred (lst_p lst)
823
{
824
  int dewey;
825
  lst_p father;
826
 
827
  if (!lst || !LST_LOOP_FATHER (lst))
828
    return NULL;
829
 
830
  dewey = lst_dewey_number (lst);
831
  if (dewey == 0)
832
    return NULL;
833
 
834
  father = LST_LOOP_FATHER (lst);
835
  return VEC_index (lst_p, LST_SEQ (father), dewey - 1);
836
}
837
 
838
/* Returns the successor of LST in the sequence of its loop father.
839
   Returns NULL if there is none.  */
840
 
841
static inline lst_p
842
lst_succ (lst_p lst)
843
{
844
  int dewey;
845
  lst_p father;
846
 
847
  if (!lst || !LST_LOOP_FATHER (lst))
848
    return NULL;
849
 
850
  dewey = lst_dewey_number (lst);
851
  father = LST_LOOP_FATHER (lst);
852
 
853
  if (VEC_length (lst_p, LST_SEQ (father)) == (unsigned) dewey + 1)
854
    return NULL;
855
 
856
  return VEC_index (lst_p, LST_SEQ (father), dewey + 1);
857
}
858
 
859
 
860
/* Return the LST node corresponding to PBB.  */
861
 
862
static inline lst_p
863
lst_find_pbb (lst_p lst, poly_bb_p pbb)
864
{
865
  int i;
866
  lst_p l;
867
 
868
  if (!lst)
869
    return NULL;
870
 
871
  if (!LST_LOOP_P (lst))
872
    return (pbb == LST_PBB (lst)) ? lst : NULL;
873
 
874
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
875
    {
876
      lst_p res = lst_find_pbb (l, pbb);
877
      if (res)
878
        return res;
879
    }
880
 
881
  return NULL;
882
}
883
 
884
/* Return the LST node corresponding to the loop around STMT at depth
885
   LOOP_DEPTH.  */
886
 
887
static inline lst_p
888
find_lst_loop (lst_p stmt, int loop_depth)
889
{
890
  lst_p loop = LST_LOOP_FATHER (stmt);
891
 
892
  gcc_assert (loop_depth >= 0);
893
 
894
  while (loop_depth < lst_depth (loop))
895
    loop = LST_LOOP_FATHER (loop);
896
 
897
  return loop;
898
}
899
 
900
/* Return the first lst representing a PBB statement in LST.  */
901
 
902
static inline lst_p
903
lst_find_first_pbb (lst_p lst)
904
{
905
  int i;
906
  lst_p l;
907
 
908
  if (!lst)
909
    return NULL;
910
 
911
  if (!LST_LOOP_P (lst))
912
    return lst;
913
 
914
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
915
    {
916
      lst_p res = lst_find_first_pbb (l);
917
      if (res)
918
        return res;
919
    }
920
 
921
  return NULL;
922
}
923
 
924
/* Returns true when LST is a loop that does not contains
925
   statements.  */
926
 
927
static inline bool
928
lst_empty_p (lst_p lst)
929
{
930
  return !lst_find_first_pbb (lst);
931
}
932
 
933
/* Return the last lst representing a PBB statement in LST.  */
934
 
935
static inline lst_p
936
lst_find_last_pbb (lst_p lst)
937
{
938
  int i;
939
  lst_p l, res = NULL;
940
 
941
  if (!lst)
942
    return NULL;
943
 
944
  if (!LST_LOOP_P (lst))
945
    return lst;
946
 
947
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
948
    {
949
      lst_p last = lst_find_last_pbb (l);
950
 
951
      if (last)
952
        res = last;
953
    }
954
 
955
  gcc_assert (res);
956
  return res;
957
}
958
 
959
/* Returns true if LOOP contains LST, in other words, if LST is nested
960
   in LOOP.  */
961
 
962
static inline bool
963
lst_contains_p (lst_p loop, lst_p lst)
964
{
965
  if (!loop || !lst || !LST_LOOP_P (loop))
966
    return false;
967
 
968
  if (loop == lst)
969
    return true;
970
 
971
  return lst_contains_p (loop, LST_LOOP_FATHER (lst));
972
}
973
 
974
/* Returns true if LOOP contains PBB, in other words, if PBB is nested
975
   in LOOP.  */
976
 
977
static inline bool
978
lst_contains_pbb (lst_p loop, poly_bb_p pbb)
979
{
980
  return lst_find_pbb (loop, pbb) ? true : false;
981
}
982
 
983
/* Creates a loop nest of depth NB_LOOPS containing LST.  */
984
 
985
static inline lst_p
986
lst_create_nest (int nb_loops, lst_p lst)
987
{
988
  lst_p res, loop;
989
  VEC (lst_p, heap) *seq;
990
 
991
  if (nb_loops == 0)
992
    return lst;
993
 
994
  seq = VEC_alloc (lst_p, heap, 1);
995
  loop = lst_create_nest (nb_loops - 1, lst);
996
  VEC_quick_push (lst_p, seq, loop);
997
  res = new_lst_loop (seq);
998
  LST_LOOP_FATHER (loop) = res;
999
 
1000
  return res;
1001
}
1002
 
1003
/* Removes LST from the sequence of statements of its loop father.  */
1004
 
1005
static inline void
1006
lst_remove_from_sequence (lst_p lst)
1007
{
1008
  lst_p father = LST_LOOP_FATHER (lst);
1009
  int dewey = lst_dewey_number (lst);
1010
 
1011
  gcc_assert (lst && father && dewey >= 0);
1012
 
1013
  VEC_ordered_remove (lst_p, LST_SEQ (father), dewey);
1014
  LST_LOOP_FATHER (lst) = NULL;
1015
}
1016
 
1017
/* Updates the scattering of PBB to be at the DEWEY number in the loop
1018
   at depth LEVEL.  */
1019
 
1020
static inline void
1021
pbb_update_scattering (poly_bb_p pbb, graphite_dim_t level, int dewey)
1022
{
1023
  ppl_Polyhedron_t ph = PBB_TRANSFORMED_SCATTERING (pbb);
1024
  ppl_dimension_type sched = psct_static_dim (pbb, level);
1025
  ppl_dimension_type ds[1];
1026
  ppl_Constraint_t new_cstr;
1027
  ppl_Linear_Expression_t expr;
1028
  ppl_dimension_type dim;
1029
 
1030
  ppl_Polyhedron_space_dimension (ph, &dim);
1031
  ds[0] = sched;
1032
  ppl_Polyhedron_remove_space_dimensions (ph, ds, 1);
1033
  ppl_insert_dimensions (ph, sched, 1);
1034
 
1035
  ppl_new_Linear_Expression_with_dimension (&expr, dim);
1036
  ppl_set_coef (expr, sched, -1);
1037
  ppl_set_inhomogeneous (expr, dewey);
1038
  ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_EQUAL);
1039
  ppl_delete_Linear_Expression (expr);
1040
  ppl_Polyhedron_add_constraint (ph, new_cstr);
1041
  ppl_delete_Constraint (new_cstr);
1042
}
1043
 
1044
/* Updates the scattering of all the PBBs under LST to be at the DEWEY
1045
   number in the loop at depth LEVEL.  */
1046
 
1047
static inline void
1048
lst_update_scattering_under (lst_p lst, int level, int dewey)
1049
{
1050
  int i;
1051
  lst_p l;
1052
 
1053
  gcc_assert (lst && level >= 0 && dewey >= 0);
1054
 
1055
  if (LST_LOOP_P (lst))
1056
    for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1057
      lst_update_scattering_under (l, level, dewey);
1058
  else
1059
    pbb_update_scattering (LST_PBB (lst), level, dewey);
1060
}
1061
 
1062
/* Updates the scattering of all the PBBs under LST and in sequence
1063
   with LST.  */
1064
 
1065
static inline void
1066
lst_update_scattering_seq (lst_p lst)
1067
{
1068
  int i;
1069
  lst_p l;
1070
  lst_p father = LST_LOOP_FATHER (lst);
1071
  int dewey = lst_dewey_number (lst);
1072
  int level = lst_depth (lst);
1073
 
1074
  gcc_assert (lst && father && dewey >= 0 && level >= 0);
1075
 
1076
  for (i = dewey; VEC_iterate (lst_p, LST_SEQ (father), i, l); i++)
1077
    lst_update_scattering_under (l, level, i);
1078
}
1079
 
1080
/* Updates the all the scattering levels of all the PBBs under
1081
   LST.  */
1082
 
1083
static inline void
1084
lst_update_scattering (lst_p lst)
1085
{
1086
  int i;
1087
  lst_p l;
1088
 
1089
  if (!lst || !LST_LOOP_P (lst))
1090
    return;
1091
 
1092
  if (LST_LOOP_FATHER (lst))
1093
    lst_update_scattering_seq (lst);
1094
 
1095
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (lst), i, l); i++)
1096
    lst_update_scattering (l);
1097
}
1098
 
1099
/* Inserts LST1 before LST2 if BEFORE is true; inserts LST1 after LST2
1100
   if BEFORE is false.  */
1101
 
1102
static inline void
1103
lst_insert_in_sequence (lst_p lst1, lst_p lst2, bool before)
1104
{
1105
  lst_p father;
1106
  int dewey;
1107
 
1108
  /* Do not insert empty loops.  */
1109
  if (!lst1 || lst_empty_p (lst1))
1110
    return;
1111
 
1112
  father = LST_LOOP_FATHER (lst2);
1113
  dewey = lst_dewey_number (lst2);
1114
 
1115
  gcc_assert (lst2 && father && dewey >= 0);
1116
 
1117
  VEC_safe_insert (lst_p, heap, LST_SEQ (father), before ? dewey : dewey + 1,
1118
                   lst1);
1119
  LST_LOOP_FATHER (lst1) = father;
1120
}
1121
 
1122
/* Replaces LST1 with LST2.  */
1123
 
1124
static inline void
1125
lst_replace (lst_p lst1, lst_p lst2)
1126
{
1127
  lst_p father;
1128
  int dewey;
1129
 
1130
  if (!lst2 || lst_empty_p (lst2))
1131
    return;
1132
 
1133
  father = LST_LOOP_FATHER (lst1);
1134
  dewey = lst_dewey_number (lst1);
1135
  LST_LOOP_FATHER (lst2) = father;
1136
  VEC_replace (lst_p, LST_SEQ (father), dewey, lst2);
1137
}
1138
 
1139
/* Returns a copy of ROOT where LST has been replaced by a copy of the
1140
   LSTs A B C in this sequence.  */
1141
 
1142
static inline lst_p
1143
lst_substitute_3 (lst_p root, lst_p lst, lst_p a, lst_p b, lst_p c)
1144
{
1145
  int i;
1146
  lst_p l;
1147
  VEC (lst_p, heap) *seq;
1148
 
1149
  if (!root)
1150
    return NULL;
1151
 
1152
  gcc_assert (lst && root != lst);
1153
 
1154
  if (!LST_LOOP_P (root))
1155
    return new_lst_stmt (LST_PBB (root));
1156
 
1157
  seq = VEC_alloc (lst_p, heap, 5);
1158
 
1159
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (root), i, l); i++)
1160
    if (l != lst)
1161
      VEC_safe_push (lst_p, heap, seq, lst_substitute_3 (l, lst, a, b, c));
1162
    else
1163
      {
1164
        if (!lst_empty_p (a))
1165
          VEC_safe_push (lst_p, heap, seq, copy_lst (a));
1166
        if (!lst_empty_p (b))
1167
          VEC_safe_push (lst_p, heap, seq, copy_lst (b));
1168
        if (!lst_empty_p (c))
1169
          VEC_safe_push (lst_p, heap, seq, copy_lst (c));
1170
      }
1171
 
1172
  return new_lst_loop (seq);
1173
}
1174
 
1175
/* Moves LST before LOOP if BEFORE is true, and after the LOOP if
1176
   BEFORE is false.  */
1177
 
1178
static inline void
1179
lst_distribute_lst (lst_p loop, lst_p lst, bool before)
1180
{
1181
  int loop_depth = lst_depth (loop);
1182
  int depth = lst_depth (lst);
1183
  int nb_loops = depth - loop_depth;
1184
 
1185
  gcc_assert (lst && loop && LST_LOOP_P (loop) && nb_loops > 0);
1186
 
1187
  lst_remove_from_sequence (lst);
1188
  lst_insert_in_sequence (lst_create_nest (nb_loops, lst), loop, before);
1189
}
1190
 
1191
/* Removes from LOOP all the statements before/after and including PBB
1192
   if BEFORE is true/false.  Returns the negation of BEFORE when the
1193
   statement PBB has been found.  */
1194
 
1195
static inline bool
1196
lst_remove_all_before_including_pbb (lst_p loop, poly_bb_p pbb, bool before)
1197
{
1198
  int i;
1199
  lst_p l;
1200
 
1201
  if (!loop || !LST_LOOP_P (loop))
1202
    return before;
1203
 
1204
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1205
    if (LST_LOOP_P (l))
1206
      {
1207
        before = lst_remove_all_before_including_pbb (l, pbb, before);
1208
 
1209
        if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1210
          {
1211
            VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1212
            free_lst (l);
1213
          }
1214
        else
1215
          i++;
1216
      }
1217
    else
1218
      {
1219
        if (before)
1220
          {
1221
            if (LST_PBB (l) == pbb)
1222
              before = false;
1223
 
1224
            VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1225
            free_lst (l);
1226
          }
1227
        else if (LST_PBB (l) == pbb)
1228
          {
1229
            before = true;
1230
            VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1231
            free_lst (l);
1232
          }
1233
        else
1234
          i++;
1235
      }
1236
 
1237
  return before;
1238
}
1239
 
1240
/* Removes from LOOP all the statements before/after and excluding PBB
1241
   if BEFORE is true/false; Returns the negation of BEFORE when the
1242
   statement PBB has been found.  */
1243
 
1244
static inline bool
1245
lst_remove_all_before_excluding_pbb (lst_p loop, poly_bb_p pbb, bool before)
1246
{
1247
  int i;
1248
  lst_p l;
1249
 
1250
  if (!loop || !LST_LOOP_P (loop))
1251
    return before;
1252
 
1253
  for (i = 0; VEC_iterate (lst_p, LST_SEQ (loop), i, l);)
1254
    if (LST_LOOP_P (l))
1255
      {
1256
        before = lst_remove_all_before_excluding_pbb (l, pbb, before);
1257
 
1258
        if (VEC_length (lst_p, LST_SEQ (l)) == 0)
1259
          {
1260
            VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1261
            free_lst (l);
1262
            continue;
1263
          }
1264
 
1265
        i++;
1266
      }
1267
    else
1268
      {
1269
        if (before && LST_PBB (l) != pbb)
1270
          {
1271
            VEC_ordered_remove (lst_p, LST_SEQ (loop), i);
1272
            free_lst (l);
1273
            continue;
1274
          }
1275
 
1276
        i++;
1277
 
1278
        if (LST_PBB (l) == pbb)
1279
          before = before ? false : true;
1280
      }
1281
 
1282
  return before;
1283
}
1284
 
1285
/* A SCOP is a Static Control Part of the program, simple enough to be
1286
   represented in polyhedral form.  */
1287
struct scop
1288
{
1289
  /* A SCOP is defined as a SESE region.  */
1290
  void *region;
1291
 
1292
  /* Number of parameters in SCoP.  */
1293
  graphite_dim_t nb_params;
1294
 
1295
  /* All the basic blocks in this scop that contain memory references
1296
     and that will be represented as statements in the polyhedral
1297
     representation.  */
1298
  VEC (poly_bb_p, heap) *bbs;
1299
 
1300
  /* Original, transformed and saved schedules.  */
1301
  lst_p original_schedule, transformed_schedule, saved_schedule;
1302
 
1303
  /* The context describes known restrictions concerning the parameters
1304
     and relations in between the parameters.
1305
 
1306
  void f (int8_t a, uint_16_t b) {
1307
    c = 2 a + b;
1308
    ...
1309
  }
1310
 
1311
  Here we can add these restrictions to the context:
1312
 
1313
  -128 >= a >= 127
1314
 
1315
     c = 2a + b  */
1316
  ppl_Pointset_Powerset_C_Polyhedron_t context;
1317
 
1318
  /* A hashtable of the data dependence relations for the original
1319
     scattering.  */
1320
  htab_t original_pddrs;
1321
 
1322
  /* True when the scop has been converted to its polyhedral
1323
     representation.  */
1324
  bool poly_scop_p;
1325
};
1326
 
1327
#define SCOP_BBS(S) (S->bbs)
1328
#define SCOP_REGION(S) ((sese) S->region)
1329
#define SCOP_CONTEXT(S) (S->context)
1330
#define SCOP_ORIGINAL_PDDRS(S) (S->original_pddrs)
1331
#define SCOP_ORIGINAL_SCHEDULE(S) (S->original_schedule)
1332
#define SCOP_TRANSFORMED_SCHEDULE(S) (S->transformed_schedule)
1333
#define SCOP_SAVED_SCHEDULE(S) (S->saved_schedule)
1334
#define POLY_SCOP_P(S) (S->poly_scop_p)
1335
 
1336
extern scop_p new_scop (void *);
1337
extern void free_scop (scop_p);
1338
extern void free_scops (VEC (scop_p, heap) *);
1339
extern void print_generated_program (FILE *, scop_p);
1340
extern void debug_generated_program (scop_p);
1341
extern void print_scattering_function (FILE *, poly_bb_p, int);
1342
extern void print_scattering_functions (FILE *, scop_p, int);
1343
extern void debug_scattering_function (poly_bb_p, int);
1344
extern void debug_scattering_functions (scop_p, int);
1345
extern int scop_max_loop_depth (scop_p);
1346
extern int unify_scattering_dimensions (scop_p);
1347
extern bool apply_poly_transforms (scop_p);
1348
extern bool graphite_legal_transform (scop_p);
1349
 
1350
/* Set the region of SCOP to REGION.  */
1351
 
1352
static inline void
1353
scop_set_region (scop_p scop, void *region)
1354
{
1355
  scop->region = region;
1356
}
1357
 
1358
/* Returns the number of parameters for SCOP.  */
1359
 
1360
static inline graphite_dim_t
1361
scop_nb_params (scop_p scop)
1362
{
1363
  return scop->nb_params;
1364
}
1365
 
1366
/* Set the number of params of SCOP to NB_PARAMS.  */
1367
 
1368
static inline void
1369
scop_set_nb_params (scop_p scop, graphite_dim_t nb_params)
1370
{
1371
  scop->nb_params = nb_params;
1372
}
1373
 
1374
/* Allocates a new empty poly_scattering structure.  */
1375
 
1376
static inline poly_scattering_p
1377
poly_scattering_new (void)
1378
{
1379
  poly_scattering_p res = XNEW (struct poly_scattering);
1380
 
1381
  res->scattering = NULL;
1382
  res->nb_local_variables = 0;
1383
  res->nb_scattering = 0;
1384
  return res;
1385
}
1386
 
1387
/* Free a poly_scattering structure.  */
1388
 
1389
static inline void
1390
poly_scattering_free (poly_scattering_p s)
1391
{
1392
  ppl_delete_Polyhedron (s->scattering);
1393
  free (s);
1394
}
1395
 
1396
/* Copies S and return a new scattering.  */
1397
 
1398
static inline poly_scattering_p
1399
poly_scattering_copy (poly_scattering_p s)
1400
{
1401
  poly_scattering_p res = poly_scattering_new ();
1402
 
1403
  ppl_new_C_Polyhedron_from_C_Polyhedron (&(res->scattering), s->scattering);
1404
  res->nb_local_variables = s->nb_local_variables;
1405
  res->nb_scattering = s->nb_scattering;
1406
  return res;
1407
}
1408
 
1409
/* Saves the transformed scattering of PBB.  */
1410
 
1411
static inline void
1412
store_scattering_pbb (poly_bb_p pbb)
1413
{
1414
  gcc_assert (PBB_TRANSFORMED (pbb));
1415
 
1416
  if (PBB_SAVED (pbb))
1417
    poly_scattering_free (PBB_SAVED (pbb));
1418
 
1419
  PBB_SAVED (pbb) = poly_scattering_copy (PBB_TRANSFORMED (pbb));
1420
}
1421
 
1422
/* Stores the SCOP_TRANSFORMED_SCHEDULE to SCOP_SAVED_SCHEDULE.  */
1423
 
1424
static inline void
1425
store_lst_schedule (scop_p scop)
1426
{
1427
  if (SCOP_SAVED_SCHEDULE (scop))
1428
    free_lst (SCOP_SAVED_SCHEDULE (scop));
1429
 
1430
  SCOP_SAVED_SCHEDULE (scop) = copy_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1431
}
1432
 
1433
/* Restores the SCOP_TRANSFORMED_SCHEDULE from SCOP_SAVED_SCHEDULE.  */
1434
 
1435
static inline void
1436
restore_lst_schedule (scop_p scop)
1437
{
1438
  if (SCOP_TRANSFORMED_SCHEDULE (scop))
1439
    free_lst (SCOP_TRANSFORMED_SCHEDULE (scop));
1440
 
1441
  SCOP_TRANSFORMED_SCHEDULE (scop) = copy_lst (SCOP_SAVED_SCHEDULE (scop));
1442
}
1443
 
1444
/* Saves the scattering for all the pbbs in the SCOP.  */
1445
 
1446
static inline void
1447
store_scattering (scop_p scop)
1448
{
1449
  int i;
1450
  poly_bb_p pbb;
1451
 
1452
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1453
    store_scattering_pbb (pbb);
1454
 
1455
  store_lst_schedule (scop);
1456
}
1457
 
1458
/* Restores the scattering of PBB.  */
1459
 
1460
static inline void
1461
restore_scattering_pbb (poly_bb_p pbb)
1462
{
1463
  gcc_assert (PBB_SAVED (pbb));
1464
 
1465
  poly_scattering_free (PBB_TRANSFORMED (pbb));
1466
  PBB_TRANSFORMED (pbb) = poly_scattering_copy (PBB_SAVED (pbb));
1467
}
1468
 
1469
/* Restores the scattering for all the pbbs in the SCOP.  */
1470
 
1471
static inline void
1472
restore_scattering (scop_p scop)
1473
{
1474
  int i;
1475
  poly_bb_p pbb;
1476
 
1477
  for (i = 0; VEC_iterate (poly_bb_p, SCOP_BBS (scop), i, pbb); i++)
1478
    restore_scattering_pbb (pbb);
1479
 
1480
  restore_lst_schedule (scop);
1481
}
1482
 
1483
/* For a given PBB, add to RES the scop context, the iteration domain,
1484
   the original scattering when ORIGINAL_P is true, otherwise add the
1485
   transformed scattering.  */
1486
 
1487
static inline void
1488
combine_context_id_scat (ppl_Pointset_Powerset_C_Polyhedron_t *res,
1489
                         poly_bb_p pbb, bool original_p)
1490
{
1491
  ppl_Pointset_Powerset_C_Polyhedron_t context;
1492
  ppl_Pointset_Powerset_C_Polyhedron_t id;
1493
 
1494
  ppl_new_Pointset_Powerset_C_Polyhedron_from_C_Polyhedron
1495
    (res, original_p ?
1496
     PBB_ORIGINAL_SCATTERING (pbb) : PBB_TRANSFORMED_SCATTERING (pbb));
1497
 
1498
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1499
    (&context, SCOP_CONTEXT (PBB_SCOP (pbb)));
1500
 
1501
  ppl_new_Pointset_Powerset_C_Polyhedron_from_Pointset_Powerset_C_Polyhedron
1502
    (&id, PBB_DOMAIN (pbb));
1503
 
1504
  /* Extend the context and the iteration domain to the dimension of
1505
     the scattering: T|I|G.  */
1506
  {
1507
    ppl_dimension_type gdim, tdim, idim;
1508
 
1509
    ppl_Pointset_Powerset_C_Polyhedron_space_dimension (*res, &tdim);
1510
    ppl_Pointset_Powerset_C_Polyhedron_space_dimension (context, &gdim);
1511
    ppl_Pointset_Powerset_C_Polyhedron_space_dimension (id, &idim);
1512
 
1513
    if (tdim > gdim)
1514
      ppl_insert_dimensions_pointset (context, 0, tdim - gdim);
1515
 
1516
    if (tdim > idim)
1517
      ppl_insert_dimensions_pointset (id, 0, tdim - idim);
1518
  }
1519
 
1520
  /* Add the context and the iteration domain to the result.  */
1521
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, context);
1522
  ppl_Pointset_Powerset_C_Polyhedron_intersection_assign (*res, id);
1523
 
1524
  ppl_delete_Pointset_Powerset_C_Polyhedron (context);
1525
  ppl_delete_Pointset_Powerset_C_Polyhedron (id);
1526
}
1527
 
1528
#endif

powered by: WebSVN 2.1.0

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