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

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-dev/] [or1k-gcc/] [gcc/] [graphite-ppl.c] - Blame information for rev 745

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

Line No. Rev Author Line
1 684 jeremybenn
/* Gimple Represented as Polyhedra.
2
   Copyright (C) 2009, 2010 Free Software Foundation, Inc.
3
   Contributed by Sebastian Pop <sebastian.pop@amd.com>
4
   and 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
#include "config.h"
23
#include "system.h"
24
#include "coretypes.h"
25
 
26
#ifdef HAVE_cloog
27
 
28
#include "ppl_c.h"
29
#include "graphite-cloog-util.h"
30
#include "graphite-ppl.h"
31
 
32
/* Set the inhomogeneous term of E to X.  */
33
 
34
void
35
ppl_set_inhomogeneous_gmp (ppl_Linear_Expression_t e, mpz_t x)
36
{
37
  mpz_t v0, v1;
38
  ppl_Coefficient_t c;
39
 
40
  mpz_init (v0);
41
  mpz_init (v1);
42
  ppl_new_Coefficient (&c);
43
 
44
  ppl_Linear_Expression_inhomogeneous_term (e, c);
45
  ppl_Coefficient_to_mpz_t (c, v1);
46
  mpz_neg (v1, v1);
47
  mpz_set (v0, x);
48
  mpz_add (v0, v0, v1);
49
  ppl_assign_Coefficient_from_mpz_t (c, v0);
50
  ppl_Linear_Expression_add_to_inhomogeneous (e, c);
51
 
52
  mpz_clear (v0);
53
  mpz_clear (v1);
54
  ppl_delete_Coefficient (c);
55
}
56
 
57
/* Set E[I] to X.  */
58
 
59
void
60
ppl_set_coef_gmp (ppl_Linear_Expression_t e, ppl_dimension_type i, mpz_t x)
61
{
62
  mpz_t v0, v1;
63
  ppl_Coefficient_t c;
64
 
65
  mpz_init (v0);
66
  mpz_init (v1);
67
  ppl_new_Coefficient (&c);
68
 
69
  ppl_Linear_Expression_coefficient (e, i, c);
70
  ppl_Coefficient_to_mpz_t (c, v1);
71
  mpz_neg (v1, v1);
72
  mpz_set (v0, x);
73
  mpz_add (v0, v0, v1);
74
  ppl_assign_Coefficient_from_mpz_t (c, v0);
75
  ppl_Linear_Expression_add_to_coefficient (e, i, c);
76
 
77
  mpz_clear (v0);
78
  mpz_clear (v1);
79
  ppl_delete_Coefficient (c);
80
}
81
 
82
/* Insert after X NB_NEW_DIMS empty dimensions into PH.
83
 
84
   With x = 3 and nb_new_dims = 4
85
 
86
   |  d0 d1 d2 d3 d4
87
 
88
   is transformed to
89
 
90
   |  d0 d1 d2 x0 x1 x2 x3 d3 d4
91
 
92
   | map = {0, 1, 2, 7, 8, 3, 4, 5, 6}
93
*/
94
 
95
void
96
ppl_insert_dimensions_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ph, int x,
97
                                int nb_new_dims)
98
{
99
  ppl_dimension_type i, dim;
100
  ppl_dimension_type *map;
101
  ppl_dimension_type x_ppl, nb_new_dims_ppl;
102
 
103
  x_ppl = (ppl_dimension_type) x;
104
  nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims;
105
 
106
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ph, &dim);
107
  ppl_Pointset_Powerset_C_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims);
108
 
109
  map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims);
110
 
111
  for (i = 0; i < x_ppl; i++)
112
    map[i] = i;
113
 
114
  for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++)
115
    map[dim + i - x_ppl] = i;
116
 
117
  for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++)
118
    map[i - nb_new_dims_ppl] = i;
119
 
120
  ppl_Pointset_Powerset_C_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims);
121
  free (map);
122
}
123
 
124
/* Insert after X NB_NEW_DIMS empty dimensions into PH.
125
 
126
   With x = 3 and nb_new_dims = 4
127
 
128
   |  d0 d1 d2 d3 d4
129
 
130
   is transformed to
131
 
132
   |  d0 d1 d2 x0 x1 x2 x3 d3 d4
133
 
134
   | map = {0, 1, 2, 7, 8, 3, 4, 5, 6}
135
*/
136
 
137
void
138
ppl_insert_dimensions (ppl_Polyhedron_t ph, int x,
139
                       int nb_new_dims)
140
{
141
  ppl_dimension_type i, dim;
142
  ppl_dimension_type *map;
143
  ppl_dimension_type x_ppl, nb_new_dims_ppl;
144
 
145
  x_ppl = (ppl_dimension_type) x;
146
  nb_new_dims_ppl = (ppl_dimension_type) nb_new_dims;
147
 
148
  ppl_Polyhedron_space_dimension (ph, &dim);
149
  ppl_Polyhedron_add_space_dimensions_and_embed (ph, nb_new_dims);
150
 
151
  map = (ppl_dimension_type *) XNEWVEC (ppl_dimension_type, dim + nb_new_dims);
152
 
153
  for (i = 0; i < x_ppl; i++)
154
    map[i] = i;
155
 
156
  for (i = x_ppl; i < x_ppl + nb_new_dims_ppl; i++)
157
    map[dim + i - x_ppl] = i;
158
 
159
  for (i = x_ppl + nb_new_dims_ppl; i < dim + nb_new_dims_ppl; i++)
160
    map[i - nb_new_dims_ppl] = i;
161
 
162
  ppl_Polyhedron_map_space_dimensions (ph, map, dim + nb_new_dims);
163
  free (map);
164
}
165
 
166
/* Based on the original polyhedron PH, returns a new polyhedron with
167
   an extra dimension placed at position LOOP + 1 that slices the
168
   dimension LOOP into strips of size STRIDE.  */
169
 
170
ppl_Polyhedron_t
171
ppl_strip_loop (ppl_Polyhedron_t ph, ppl_dimension_type loop, int stride)
172
{
173
  ppl_const_Constraint_System_t pcs;
174
  ppl_Constraint_System_const_iterator_t cit, end;
175
  ppl_const_Constraint_t cstr;
176
  ppl_Linear_Expression_t expr;
177
  int v;
178
  ppl_dimension_type dim;
179
  ppl_Polyhedron_t res;
180
  ppl_Coefficient_t c;
181
  mpz_t val;
182
 
183
  mpz_init (val);
184
  ppl_new_Coefficient (&c);
185
 
186
  ppl_Polyhedron_space_dimension (ph, &dim);
187
  ppl_Polyhedron_get_constraints (ph, &pcs);
188
 
189
  /* Start from a copy of the constraints.  */
190
  ppl_new_C_Polyhedron_from_space_dimension (&res, dim + 1, 0);
191
  ppl_Polyhedron_add_constraints (res, pcs);
192
 
193
  /* Add an empty dimension for the strip loop.  */
194
  ppl_insert_dimensions (res, loop, 1);
195
 
196
  /* Identify the constraints that define the lower and upper bounds
197
     of the strip-mined loop, and add them to the strip loop.  */
198
  {
199
    ppl_Polyhedron_t tmp;
200
 
201
    ppl_new_C_Polyhedron_from_space_dimension (&tmp, dim + 1, 0);
202
    ppl_new_Constraint_System_const_iterator (&cit);
203
    ppl_new_Constraint_System_const_iterator (&end);
204
 
205
    for (ppl_Constraint_System_begin (pcs, cit),
206
           ppl_Constraint_System_end (pcs, end);
207
         !ppl_Constraint_System_const_iterator_equal_test (cit, end);
208
         ppl_Constraint_System_const_iterator_increment (cit))
209
      {
210
        ppl_Constraint_System_const_iterator_dereference (cit, &cstr);
211
        ppl_new_Linear_Expression_from_Constraint (&expr, cstr);
212
        ppl_Linear_Expression_coefficient (expr, loop, c);
213
        ppl_delete_Linear_Expression (expr);
214
        ppl_Coefficient_to_mpz_t (c, val);
215
        v = mpz_get_si (val);
216
 
217
        if (0 < v || v < 0)
218
          ppl_Polyhedron_add_constraint (tmp, cstr);
219
      }
220
    ppl_delete_Constraint_System_const_iterator (cit);
221
    ppl_delete_Constraint_System_const_iterator (end);
222
 
223
    ppl_insert_dimensions (tmp, loop + 1, 1);
224
    ppl_Polyhedron_get_constraints (tmp, &pcs);
225
    ppl_Polyhedron_add_constraints (res, pcs);
226
    ppl_delete_Polyhedron (tmp);
227
  }
228
 
229
  /* Lower bound of a tile starts at "stride * outer_iv".  */
230
  {
231
    ppl_Constraint_t new_cstr;
232
    ppl_new_Linear_Expression_with_dimension (&expr, dim + 1);
233
 
234
    ppl_set_coef (expr, loop + 1, 1);
235
    ppl_set_coef (expr, loop, -1 * stride);
236
 
237
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
238
    ppl_delete_Linear_Expression (expr);
239
    ppl_Polyhedron_add_constraint (res, new_cstr);
240
    ppl_delete_Constraint (new_cstr);
241
  }
242
 
243
  /* Upper bound of a tile stops at "stride * outer_iv + stride - 1",
244
     or at the old upper bound that is not modified.  */
245
  {
246
    ppl_Constraint_t new_cstr;
247
    ppl_new_Linear_Expression_with_dimension (&expr, dim + 1);
248
 
249
    ppl_set_coef (expr, loop + 1, -1);
250
    ppl_set_coef (expr, loop, stride);
251
    ppl_set_inhomogeneous (expr, stride - 1);
252
 
253
    ppl_new_Constraint (&new_cstr, expr, PPL_CONSTRAINT_TYPE_GREATER_OR_EQUAL);
254
    ppl_delete_Linear_Expression (expr);
255
    ppl_Polyhedron_add_constraint (res, new_cstr);
256
    ppl_delete_Constraint (new_cstr);
257
  }
258
 
259
  mpz_clear (val);
260
  ppl_delete_Coefficient (c);
261
  return res;
262
}
263
 
264
/* Lexicographically compares two linear expressions A and B and
265
   returns negative when A < B, 0 when A == B and positive when A > B.  */
266
 
267
int
268
ppl_lexico_compare_linear_expressions (ppl_Linear_Expression_t a,
269
                                       ppl_Linear_Expression_t b)
270
{
271
  ppl_dimension_type min_length, length1, length2;
272
  ppl_dimension_type i;
273
  ppl_Coefficient_t c;
274
  int res;
275
  mpz_t va, vb;
276
 
277
  ppl_Linear_Expression_space_dimension (a, &length1);
278
  ppl_Linear_Expression_space_dimension (b, &length2);
279
  ppl_new_Coefficient (&c);
280
  mpz_init (va);
281
  mpz_init (vb);
282
 
283
  if (length1 < length2)
284
    min_length = length1;
285
  else
286
    min_length = length2;
287
 
288
  for (i = 0; i < min_length; i++)
289
    {
290
      ppl_Linear_Expression_coefficient (a, i, c);
291
      ppl_Coefficient_to_mpz_t (c, va);
292
      ppl_Linear_Expression_coefficient (b, i, c);
293
      ppl_Coefficient_to_mpz_t (c, vb);
294
      res = mpz_cmp (va, vb);
295
 
296
      if (res == 0)
297
        continue;
298
 
299
      mpz_clear (va);
300
      mpz_clear (vb);
301
      ppl_delete_Coefficient (c);
302
      return res;
303
    }
304
 
305
  mpz_clear (va);
306
  mpz_clear (vb);
307
  ppl_delete_Coefficient (c);
308
  return length1 - length2;
309
}
310
 
311
/* Print to FILE the polyhedron PH under its PolyLib matrix form.  */
312
 
313
void
314
ppl_print_polyhedron_matrix (FILE *file, ppl_const_Polyhedron_t ph)
315
{
316
  CloogMatrix *mat = new_Cloog_Matrix_from_ppl_Polyhedron (ph);
317
  cloog_matrix_print (file, mat);
318
  cloog_matrix_free (mat);
319
}
320
 
321
/* Print to FILE the linear expression LE.  */
322
 
323
void
324
ppl_print_linear_expr (FILE *file, ppl_Linear_Expression_t le)
325
{
326
  ppl_Constraint_t c;
327
  ppl_Polyhedron_t pol;
328
  ppl_dimension_type dim;
329
 
330
  ppl_Linear_Expression_space_dimension (le, &dim);
331
  ppl_new_C_Polyhedron_from_space_dimension (&pol, dim, 0);
332
  ppl_new_Constraint (&c, le, PPL_CONSTRAINT_TYPE_EQUAL);
333
  ppl_Polyhedron_add_constraint (pol, c);
334
  ppl_print_polyhedron_matrix (file, pol);
335
}
336
 
337
/* Print to STDERR the linear expression LE.  */
338
 
339
DEBUG_FUNCTION void
340
debug_ppl_linear_expr (ppl_Linear_Expression_t le)
341
{
342
  ppl_print_linear_expr (stderr, le);
343
}
344
 
345
/* Print to FILE the powerset PS in its PolyLib matrix form.  */
346
 
347
void
348
ppl_print_powerset_matrix (FILE *file,
349
                           ppl_Pointset_Powerset_C_Polyhedron_t ps)
350
{
351
  size_t nb_disjuncts;
352
  ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
353
 
354
  ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
355
  ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
356
 
357
  ppl_Pointset_Powerset_C_Polyhedron_size (ps, &nb_disjuncts);
358
  fprintf (file, "%d\n", (int) nb_disjuncts);
359
 
360
  for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
361
       ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
362
       !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
363
       ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
364
    {
365
      ppl_const_Polyhedron_t ph;
366
 
367
      ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
368
      ppl_print_polyhedron_matrix (file, ph);
369
    }
370
 
371
  ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
372
  ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
373
}
374
 
375
/* Print to STDERR the polyhedron PH under its PolyLib matrix form.  */
376
 
377
DEBUG_FUNCTION void
378
debug_ppl_polyhedron_matrix (ppl_Polyhedron_t ph)
379
{
380
  ppl_print_polyhedron_matrix (stderr, ph);
381
}
382
 
383
/* Print to STDERR the powerset PS in its PolyLib matrix form.  */
384
 
385
DEBUG_FUNCTION void
386
debug_ppl_powerset_matrix (ppl_Pointset_Powerset_C_Polyhedron_t ps)
387
{
388
  ppl_print_powerset_matrix (stderr, ps);
389
}
390
 
391
/* Read from FILE a polyhedron under PolyLib matrix form and return a
392
   PPL polyhedron object.  */
393
 
394
void
395
ppl_read_polyhedron_matrix (ppl_Polyhedron_t *ph, FILE *file)
396
{
397
  CloogMatrix *mat = cloog_matrix_read (file);
398
  new_C_Polyhedron_from_Cloog_Matrix (ph, mat);
399
  cloog_matrix_free (mat);
400
}
401
 
402
/* Return in RES the maximum of the linear expression LE on the
403
   pointset powerset of polyhedra PS.  */
404
 
405
void
406
ppl_max_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps,
407
                         ppl_Linear_Expression_t le, mpz_t res)
408
{
409
  ppl_Coefficient_t num, denom;
410
  mpz_t dv, nv;
411
  int maximum, err;
412
 
413
  mpz_init (nv);
414
  mpz_init (dv);
415
  ppl_new_Coefficient (&num);
416
  ppl_new_Coefficient (&denom);
417
  err = ppl_Pointset_Powerset_C_Polyhedron_maximize (ps, le, num, denom, &maximum);
418
 
419
  if (err > 0)
420
    {
421
      ppl_Coefficient_to_mpz_t (num, nv);
422
      ppl_Coefficient_to_mpz_t (denom, dv);
423
      gcc_assert (mpz_sgn (dv) != 0);
424
      mpz_tdiv_q (res, nv, dv);
425
    }
426
 
427
  mpz_clear (nv);
428
  mpz_clear (dv);
429
  ppl_delete_Coefficient (num);
430
  ppl_delete_Coefficient (denom);
431
}
432
 
433
/* Return in RES the maximum of the linear expression LE on the
434
   polyhedron POL.  */
435
 
436
void
437
ppl_min_for_le_pointset (ppl_Pointset_Powerset_C_Polyhedron_t ps,
438
                         ppl_Linear_Expression_t le, mpz_t res)
439
{
440
  ppl_Coefficient_t num, denom;
441
  mpz_t dv, nv;
442
  int minimum, err;
443
 
444
  mpz_init (nv);
445
  mpz_init (dv);
446
  ppl_new_Coefficient (&num);
447
  ppl_new_Coefficient (&denom);
448
  err = ppl_Pointset_Powerset_C_Polyhedron_minimize (ps, le, num, denom, &minimum);
449
 
450
  if (err > 0)
451
    {
452
      ppl_Coefficient_to_mpz_t (num, nv);
453
      ppl_Coefficient_to_mpz_t (denom, dv);
454
      gcc_assert (mpz_sgn (dv) != 0);
455
      mpz_tdiv_q (res, nv, dv);
456
    }
457
 
458
  mpz_clear (nv);
459
  mpz_clear (dv);
460
  ppl_delete_Coefficient (num);
461
  ppl_delete_Coefficient (denom);
462
}
463
 
464
/* Builds a constraint in dimension DIM relating dimensions POS1 to
465
   POS2 as "POS1 - POS2 + C CSTR_TYPE 0" */
466
 
467
ppl_Constraint_t
468
ppl_build_relation (int dim, int pos1, int pos2, int c,
469
                    enum ppl_enum_Constraint_Type cstr_type)
470
{
471
  ppl_Linear_Expression_t expr;
472
  ppl_Constraint_t cstr;
473
  ppl_Coefficient_t coef;
474
  mpz_t v, v_op, v_c;
475
 
476
  mpz_init (v);
477
  mpz_init (v_op);
478
  mpz_init (v_c);
479
 
480
  mpz_set_si (v, 1);
481
  mpz_set_si (v_op, -1);
482
  mpz_set_si (v_c, c);
483
 
484
  ppl_new_Coefficient (&coef);
485
  ppl_new_Linear_Expression_with_dimension (&expr, dim);
486
 
487
  ppl_assign_Coefficient_from_mpz_t (coef, v);
488
  ppl_Linear_Expression_add_to_coefficient (expr, pos1, coef);
489
  ppl_assign_Coefficient_from_mpz_t (coef, v_op);
490
  ppl_Linear_Expression_add_to_coefficient (expr, pos2, coef);
491
  ppl_assign_Coefficient_from_mpz_t (coef, v_c);
492
  ppl_Linear_Expression_add_to_inhomogeneous (expr, coef);
493
 
494
  ppl_new_Constraint (&cstr, expr, cstr_type);
495
 
496
  ppl_delete_Linear_Expression (expr);
497
  ppl_delete_Coefficient (coef);
498
  mpz_clear (v);
499
  mpz_clear (v_op);
500
  mpz_clear (v_c);
501
 
502
  return cstr;
503
}
504
 
505
/* Print to STDERR the GMP value VAL.  */
506
 
507
DEBUG_FUNCTION void
508
debug_gmp_value (mpz_t val)
509
{
510
  char *str = mpz_get_str (0, 10, val);
511
  void (*gmp_free) (void *, size_t);
512
 
513
  fprintf (stderr, "%s", str);
514
  mp_get_memory_functions (NULL, NULL, &gmp_free);
515
  (*gmp_free) (str, strlen (str) + 1);
516
}
517
 
518
/* Checks for integer feasibility: returns true when the powerset
519
   polyhedron PS has no integer solutions.  */
520
 
521
bool
522
ppl_powerset_is_empty (ppl_Pointset_Powerset_C_Polyhedron_t ps)
523
{
524
  ppl_PIP_Problem_t pip;
525
  ppl_dimension_type d;
526
  ppl_const_Constraint_System_t pcs;
527
  ppl_Constraint_System_const_iterator_t first, last;
528
  ppl_Pointset_Powerset_C_Polyhedron_iterator_t it, end;
529
  bool has_integer_solutions = false;
530
 
531
  if (ppl_Pointset_Powerset_C_Polyhedron_is_empty (ps))
532
    return true;
533
 
534
  ppl_Pointset_Powerset_C_Polyhedron_space_dimension (ps, &d);
535
  ppl_new_Constraint_System_const_iterator (&first);
536
  ppl_new_Constraint_System_const_iterator (&last);
537
  ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&it);
538
  ppl_new_Pointset_Powerset_C_Polyhedron_iterator (&end);
539
 
540
  for (ppl_Pointset_Powerset_C_Polyhedron_iterator_begin (ps, it),
541
       ppl_Pointset_Powerset_C_Polyhedron_iterator_end (ps, end);
542
       !ppl_Pointset_Powerset_C_Polyhedron_iterator_equal_test (it, end);
543
       ppl_Pointset_Powerset_C_Polyhedron_iterator_increment (it))
544
    {
545
      ppl_const_Polyhedron_t ph;
546
      ppl_Pointset_Powerset_C_Polyhedron_iterator_dereference (it, &ph);
547
 
548
      ppl_Polyhedron_get_constraints (ph, &pcs);
549
      ppl_Constraint_System_begin (pcs, first);
550
      ppl_Constraint_System_end (pcs, last);
551
 
552
      ppl_new_PIP_Problem_from_constraints (&pip, d, first, last, 0, NULL);
553
      has_integer_solutions |= ppl_PIP_Problem_is_satisfiable (pip);
554
 
555
      ppl_delete_PIP_Problem (pip);
556
    }
557
 
558
  ppl_delete_Constraint_System_const_iterator (first);
559
  ppl_delete_Constraint_System_const_iterator (last);
560
  ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (it);
561
  ppl_delete_Pointset_Powerset_C_Polyhedron_iterator (end);
562
 
563
  return !has_integer_solutions;
564
}
565
 
566
#endif

powered by: WebSVN 2.1.0

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