Coverage Report

Created: 2018-09-25 00:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/polly/lib/External/isl/isl_aff_map.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2012-2013 Ecole Normale Superieure
4
 * Copyright 2016      Sven Verdoolaege
5
 *
6
 * Use of this software is governed by the MIT license
7
 *
8
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
9
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
10
 * 91893 Orsay, France
11
 * and Ecole Normale Superieure, 45 rue d'Ulm, 75230 Paris, France
12
 */
13
14
#include <isl/ctx.h>
15
#include <isl/space.h>
16
#include <isl/local_space.h>
17
#include <isl/union_map.h>
18
#include <isl_map_private.h>
19
#include <isl_aff_private.h>
20
#include <isl_vec_private.h>
21
#include <isl_seq.h>
22
23
#include <bset_from_bmap.c>
24
#include <set_from_map.c>
25
26
/* Check that the input living in "space" lives in a map space.
27
 * That is, check that "space" is a map space.
28
 */
29
static isl_stat check_input_is_map(__isl_keep isl_space *space)
30
27.2k
{
31
27.2k
  isl_bool is_set;
32
27.2k
33
27.2k
  is_set = isl_space_is_set(space);
34
27.2k
  if (is_set < 0)
35
0
    return isl_stat_error;
36
27.2k
  if (is_set)
37
27.2k
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
38
27.2k
      "space of input is not a map", return isl_stat_error);
39
27.2k
  return isl_stat_ok;
40
27.2k
}
41
42
/* Check that the input living in "space" lives in a set space.
43
 * That is, check that "space" is a set space.
44
 */
45
static isl_stat check_input_is_set(__isl_keep isl_space *space)
46
14
{
47
14
  isl_bool is_set;
48
14
49
14
  is_set = isl_space_is_set(space);
50
14
  if (is_set < 0)
51
0
    return isl_stat_error;
52
14
  if (!is_set)
53
14
    
isl_die0
(isl_space_get_ctx(space), isl_error_invalid,
54
14
      "space of input is not a set", return isl_stat_error);
55
14
  return isl_stat_ok;
56
14
}
57
58
/* Construct a basic map mapping the domain of the affine expression
59
 * to a one-dimensional range prescribed by the affine expression.
60
 * If "rational" is set, then construct a rational basic map.
61
 *
62
 * A NaN affine expression cannot be converted to a basic map.
63
 */
64
static __isl_give isl_basic_map *isl_basic_map_from_aff2(
65
  __isl_take isl_aff *aff, int rational)
66
76.0k
{
67
76.0k
  int k;
68
76.0k
  int pos;
69
76.0k
  isl_bool is_nan;
70
76.0k
  isl_local_space *ls;
71
76.0k
  isl_basic_map *bmap = NULL;
72
76.0k
73
76.0k
  if (!aff)
74
0
    return NULL;
75
76.0k
  is_nan = isl_aff_is_nan(aff);
76
76.0k
  if (is_nan < 0)
77
0
    goto error;
78
76.0k
  if (is_nan)
79
76.0k
    
isl_die0
(isl_aff_get_ctx(aff), isl_error_invalid,
80
76.0k
      "cannot convert NaN", goto error);
81
76.0k
82
76.0k
  ls = isl_aff_get_local_space(aff);
83
76.0k
  bmap = isl_basic_map_from_local_space(ls);
84
76.0k
  bmap = isl_basic_map_extend_constraints(bmap, 1, 0);
85
76.0k
  k = isl_basic_map_alloc_equality(bmap);
86
76.0k
  if (k < 0)
87
0
    goto error;
88
76.0k
89
76.0k
  pos = isl_basic_map_offset(bmap, isl_dim_out);
90
76.0k
  isl_seq_cpy(bmap->eq[k], aff->v->el + 1, pos);
91
76.0k
  isl_int_neg(bmap->eq[k][pos], aff->v->el[0]);
92
76.0k
  isl_seq_cpy(bmap->eq[k] + pos + 1, aff->v->el + 1 + pos,
93
76.0k
        aff->v->size - (pos + 1));
94
76.0k
95
76.0k
  isl_aff_free(aff);
96
76.0k
  if (rational)
97
2
    bmap = isl_basic_map_set_rational(bmap);
98
76.0k
  bmap = isl_basic_map_gauss(bmap, NULL);
99
76.0k
  bmap = isl_basic_map_finalize(bmap);
100
76.0k
  return bmap;
101
0
error:
102
0
  isl_aff_free(aff);
103
0
  isl_basic_map_free(bmap);
104
0
  return NULL;
105
76.0k
}
106
107
/* Construct a basic map mapping the domain of the affine expression
108
 * to a one-dimensional range prescribed by the affine expression.
109
 */
110
__isl_give isl_basic_map *isl_basic_map_from_aff(__isl_take isl_aff *aff)
111
23.3k
{
112
23.3k
  return isl_basic_map_from_aff2(aff, 0);
113
23.3k
}
114
115
/* Construct a map mapping the domain of the affine expression
116
 * to a one-dimensional range prescribed by the affine expression.
117
 */
118
__isl_give isl_map *isl_map_from_aff(__isl_take isl_aff *aff)
119
4
{
120
4
  isl_basic_map *bmap;
121
4
122
4
  bmap = isl_basic_map_from_aff(aff);
123
4
  return isl_map_from_basic_map(bmap);
124
4
}
125
126
/* Construct a basic map mapping the domain of the multi-affine expression
127
 * to its range, with each dimension in the range equated to the
128
 * corresponding affine expression.
129
 * If "rational" is set, then construct a rational basic map.
130
 */
131
__isl_give isl_basic_map *isl_basic_map_from_multi_aff2(
132
  __isl_take isl_multi_aff *maff, int rational)
133
18.7k
{
134
18.7k
  int i;
135
18.7k
  isl_space *space;
136
18.7k
  isl_basic_map *bmap;
137
18.7k
138
18.7k
  if (!maff)
139
0
    return NULL;
140
18.7k
141
18.7k
  if (isl_space_dim(maff->space, isl_dim_out) != maff->n)
142
18.7k
    
isl_die0
(isl_multi_aff_get_ctx(maff), isl_error_internal,
143
18.7k
      "invalid space", goto error);
144
18.7k
145
18.7k
  space = isl_space_domain(isl_multi_aff_get_space(maff));
146
18.7k
  bmap = isl_basic_map_universe(isl_space_from_domain(space));
147
18.7k
  if (rational)
148
2
    bmap = isl_basic_map_set_rational(bmap);
149
18.7k
150
71.3k
  for (i = 0; i < maff->n; 
++i52.6k
) {
151
52.6k
    isl_aff *aff;
152
52.6k
    isl_basic_map *bmap_i;
153
52.6k
154
52.6k
    aff = isl_aff_copy(maff->u.p[i]);
155
52.6k
    bmap_i = isl_basic_map_from_aff2(aff, rational);
156
52.6k
157
52.6k
    bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
158
52.6k
  }
159
18.7k
160
18.7k
  bmap = isl_basic_map_reset_space(bmap, isl_multi_aff_get_space(maff));
161
18.7k
162
18.7k
  isl_multi_aff_free(maff);
163
18.7k
  return bmap;
164
0
error:
165
0
  isl_multi_aff_free(maff);
166
0
  return NULL;
167
18.7k
}
168
169
/* Construct a basic map mapping the domain of the multi-affine expression
170
 * to its range, with each dimension in the range equated to the
171
 * corresponding affine expression.
172
 * If "ma" lives in a set space, then the result is actually a set.
173
 */
174
static __isl_give isl_basic_map *basic_map_from_multi_aff(
175
  __isl_take isl_multi_aff *ma)
176
6.58k
{
177
6.58k
  return isl_basic_map_from_multi_aff2(ma, 0);
178
6.58k
}
179
180
/* Construct a basic map mapping the domain of the multi-affine expression
181
 * to its range, with each dimension in the range equated to the
182
 * corresponding affine expression.
183
 */
184
__isl_give isl_basic_map *isl_basic_map_from_multi_aff(
185
  __isl_take isl_multi_aff *ma)
186
2.31k
{
187
2.31k
  if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
188
0
    ma = isl_multi_aff_free(ma);
189
2.31k
  return basic_map_from_multi_aff(ma);
190
2.31k
}
191
192
/* Construct a basic set mapping the parameter domain
193
 * of the multi-affine expression to its space, with each dimension
194
 * in the space equated to the corresponding affine expression.
195
 */
196
__isl_give isl_basic_set *isl_basic_set_from_multi_aff(
197
  __isl_take isl_multi_aff *ma)
198
0
{
199
0
  if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0)
200
0
    ma = isl_multi_aff_free(ma);
201
0
  return bset_from_bmap(isl_basic_map_from_multi_aff(ma));
202
0
}
203
204
/* Construct a map mapping the domain of the multi-affine expression
205
 * to its range, with each dimension in the range equated to the
206
 * corresponding affine expression.
207
 * If "maff" lives in a set space, then the result is actually a set.
208
 */
209
__isl_give isl_map *isl_map_from_multi_aff_internal(
210
  __isl_take isl_multi_aff *maff)
211
4.27k
{
212
4.27k
  isl_basic_map *bmap;
213
4.27k
214
4.27k
  bmap = basic_map_from_multi_aff(maff);
215
4.27k
  return isl_map_from_basic_map(bmap);
216
4.27k
}
217
218
/* Construct a map mapping the domain the multi-affine expression
219
 * to its range, with each dimension in the range equated to the
220
 * corresponding affine expression.
221
 */
222
__isl_give isl_map *isl_map_from_multi_aff(__isl_take isl_multi_aff *ma)
223
1.71k
{
224
1.71k
  if (check_input_is_map(isl_multi_aff_peek_space(ma)) < 0)
225
0
    ma = isl_multi_aff_free(ma);
226
1.71k
  return isl_map_from_multi_aff_internal(ma);
227
1.71k
}
228
229
/* Construct a set mapping the parameter domain the multi-affine expression
230
 * to its space, with each dimension in the space equated to the
231
 * corresponding affine expression.
232
 */
233
__isl_give isl_set *isl_set_from_multi_aff(__isl_take isl_multi_aff *ma)
234
0
{
235
0
  if (check_input_is_set(isl_multi_aff_peek_space(ma)) < 0)
236
0
    ma = isl_multi_aff_free(ma);
237
0
  return isl_map_from_multi_aff_internal(ma);
238
0
}
239
240
/* Construct a basic map mapping a domain in the given space to
241
 * to an n-dimensional range, with n the number of elements in the list,
242
 * where each coordinate in the range is prescribed by the
243
 * corresponding affine expression.
244
 * The domains of all affine expressions in the list are assumed to match
245
 * domain_space.
246
 */
247
__isl_give isl_basic_map *isl_basic_map_from_aff_list(
248
  __isl_take isl_space *domain_space, __isl_take isl_aff_list *list)
249
0
{
250
0
  int i;
251
0
  isl_space *space;
252
0
  isl_basic_map *bmap;
253
0
254
0
  if (!list)
255
0
    return NULL;
256
0
257
0
  space = isl_space_from_domain(domain_space);
258
0
  bmap = isl_basic_map_universe(space);
259
0
260
0
  for (i = 0; i < list->n; ++i) {
261
0
    isl_aff *aff;
262
0
    isl_basic_map *bmap_i;
263
0
264
0
    aff = isl_aff_copy(list->p[i]);
265
0
    bmap_i = isl_basic_map_from_aff(aff);
266
0
267
0
    bmap = isl_basic_map_flat_range_product(bmap, bmap_i);
268
0
  }
269
0
270
0
  isl_aff_list_free(list);
271
0
  return bmap;
272
0
}
273
274
/* Construct a map with as domain the domain of pwaff and
275
 * one-dimensional range corresponding to the affine expressions.
276
 * If "pwaff" lives in a set space, then the result is actually a set.
277
 */
278
__isl_give isl_map *isl_map_from_pw_aff_internal(__isl_take isl_pw_aff *pwaff)
279
23.1k
{
280
23.1k
  int i;
281
23.1k
  isl_space *space;
282
23.1k
  isl_map *map;
283
23.1k
284
23.1k
  if (!pwaff)
285
0
    return NULL;
286
23.1k
287
23.1k
  space = isl_pw_aff_get_space(pwaff);
288
23.1k
  map = isl_map_empty(space);
289
23.1k
290
46.5k
  for (i = 0; i < pwaff->n; 
++i23.3k
) {
291
23.3k
    isl_basic_map *bmap;
292
23.3k
    isl_map *map_i;
293
23.3k
294
23.3k
    bmap = isl_basic_map_from_aff(isl_aff_copy(pwaff->p[i].aff));
295
23.3k
    map_i = isl_map_from_basic_map(bmap);
296
23.3k
    map_i = isl_map_intersect_domain(map_i,
297
23.3k
            isl_set_copy(pwaff->p[i].set));
298
23.3k
    map = isl_map_union_disjoint(map, map_i);
299
23.3k
  }
300
23.1k
301
23.1k
  isl_pw_aff_free(pwaff);
302
23.1k
303
23.1k
  return map;
304
23.1k
}
305
306
/* Construct a map with as domain the domain of pwaff and
307
 * one-dimensional range corresponding to the affine expressions.
308
 */
309
__isl_give isl_map *isl_map_from_pw_aff(__isl_take isl_pw_aff *pwaff)
310
23.1k
{
311
23.1k
  if (check_input_is_map(isl_pw_aff_peek_space(pwaff)) < 0)
312
0
    pwaff = isl_pw_aff_free(pwaff);
313
23.1k
  return isl_map_from_pw_aff_internal(pwaff);
314
23.1k
}
315
316
/* Construct a one-dimensional set with as parameter domain
317
 * the domain of pwaff and the single set dimension
318
 * corresponding to the affine expressions.
319
 */
320
__isl_give isl_set *isl_set_from_pw_aff(__isl_take isl_pw_aff *pwaff)
321
7
{
322
7
  if (check_input_is_set(isl_pw_aff_peek_space(pwaff)) < 0)
323
0
    pwaff = isl_pw_aff_free(pwaff);
324
7
  return set_from_map(isl_map_from_pw_aff_internal(pwaff));
325
7
}
326
327
/* Construct a map mapping the domain of the piecewise multi-affine expression
328
 * to its range, with each dimension in the range equated to the
329
 * corresponding affine expression on its cell.
330
 *
331
 * If the domain of "pma" is rational, then so is the constructed "map".
332
 */
333
__isl_give isl_map *isl_map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
334
8.25k
{
335
8.25k
  int i;
336
8.25k
  isl_map *map;
337
8.25k
338
8.25k
  if (!pma)
339
0
    return NULL;
340
8.25k
341
8.25k
  map = isl_map_empty(isl_pw_multi_aff_get_space(pma));
342
8.25k
343
17.0k
  for (i = 0; i < pma->n; 
++i8.77k
) {
344
8.77k
    isl_bool rational;
345
8.77k
    isl_multi_aff *maff;
346
8.77k
    isl_basic_map *bmap;
347
8.77k
    isl_map *map_i;
348
8.77k
349
8.77k
    rational = isl_set_is_rational(pma->p[i].set);
350
8.77k
    if (rational < 0)
351
0
      map = isl_map_free(map);
352
8.77k
    maff = isl_multi_aff_copy(pma->p[i].maff);
353
8.77k
    bmap = isl_basic_map_from_multi_aff2(maff, rational);
354
8.77k
    map_i = isl_map_from_basic_map(bmap);
355
8.77k
    map_i = isl_map_intersect_domain(map_i,
356
8.77k
            isl_set_copy(pma->p[i].set));
357
8.77k
    map = isl_map_union_disjoint(map, map_i);
358
8.77k
  }
359
8.25k
360
8.25k
  isl_pw_multi_aff_free(pma);
361
8.25k
  return map;
362
8.25k
}
363
364
__isl_give isl_set *isl_set_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma)
365
7
{
366
7
  if (check_input_is_set(isl_pw_multi_aff_peek_space(pma)) < 0)
367
0
    pma = isl_pw_multi_aff_free(pma);
368
7
  return set_from_map(isl_map_from_pw_multi_aff(pma));
369
7
}
370
371
/* Construct a set or map mapping the shared (parameter) domain
372
 * of the piecewise affine expressions to the range of "mpa"
373
 * with each dimension in the range equated to the
374
 * corresponding piecewise affine expression.
375
 */
376
static __isl_give isl_map *map_from_multi_pw_aff(
377
  __isl_take isl_multi_pw_aff *mpa)
378
0
{
379
0
  int i;
380
0
  isl_space *space;
381
0
  isl_map *map;
382
0
383
0
  if (!mpa)
384
0
    return NULL;
385
0
386
0
  if (isl_space_dim(mpa->space, isl_dim_out) != mpa->n)
387
0
    isl_die(isl_multi_pw_aff_get_ctx(mpa), isl_error_internal,
388
0
      "invalid space", goto error);
389
0
390
0
  space = isl_multi_pw_aff_get_domain_space(mpa);
391
0
  map = isl_map_universe(isl_space_from_domain(space));
392
0
393
0
  for (i = 0; i < mpa->n; ++i) {
394
0
    isl_pw_aff *pa;
395
0
    isl_map *map_i;
396
0
397
0
    pa = isl_pw_aff_copy(mpa->u.p[i]);
398
0
    map_i = isl_map_from_pw_aff_internal(pa);
399
0
400
0
    map = isl_map_flat_range_product(map, map_i);
401
0
  }
402
0
403
0
  map = isl_map_reset_space(map, isl_multi_pw_aff_get_space(mpa));
404
0
405
0
  isl_multi_pw_aff_free(mpa);
406
0
  return map;
407
0
error:
408
0
  isl_multi_pw_aff_free(mpa);
409
0
  return NULL;
410
0
}
411
412
/* Construct a map mapping the shared domain
413
 * of the piecewise affine expressions to the range of "mpa"
414
 * with each dimension in the range equated to the
415
 * corresponding piecewise affine expression.
416
 */
417
__isl_give isl_map *isl_map_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
418
0
{
419
0
  if (check_input_is_map(isl_multi_pw_aff_peek_space(mpa)) < 0)
420
0
    mpa = isl_multi_pw_aff_free(mpa);
421
0
  return map_from_multi_pw_aff(mpa);
422
0
}
423
424
/* Construct a set mapping the shared parameter domain
425
 * of the piecewise affine expressions to the space of "mpa"
426
 * with each dimension in the range equated to the
427
 * corresponding piecewise affine expression.
428
 */
429
__isl_give isl_set *isl_set_from_multi_pw_aff(__isl_take isl_multi_pw_aff *mpa)
430
0
{
431
0
  if (check_input_is_set(isl_multi_pw_aff_peek_space(mpa)) < 0)
432
0
    mpa = isl_multi_pw_aff_free(mpa);
433
0
  return set_from_map(map_from_multi_pw_aff(mpa));
434
0
}
435
436
/* Convert "pa" to an isl_map and add it to *umap.
437
 */
438
static isl_stat map_from_pw_aff_entry(__isl_take isl_pw_aff *pa, void *user)
439
19.1k
{
440
19.1k
  isl_union_map **umap = user;
441
19.1k
  isl_map *map;
442
19.1k
443
19.1k
  map = isl_map_from_pw_aff(pa);
444
19.1k
  *umap = isl_union_map_add_map(*umap, map);
445
19.1k
446
19.1k
  return *umap ? isl_stat_ok : 
isl_stat_error0
;
447
19.1k
}
448
449
/* Construct a union map mapping the domain of the union
450
 * piecewise affine expression to its range, with the single output dimension
451
 * equated to the corresponding affine expressions on their cells.
452
 */
453
__isl_give isl_union_map *isl_union_map_from_union_pw_aff(
454
  __isl_take isl_union_pw_aff *upa)
455
9.02k
{
456
9.02k
  isl_space *space;
457
9.02k
  isl_union_map *umap;
458
9.02k
459
9.02k
  if (!upa)
460
0
    return NULL;
461
9.02k
462
9.02k
  space = isl_union_pw_aff_get_space(upa);
463
9.02k
  umap = isl_union_map_empty(space);
464
9.02k
465
9.02k
  if (isl_union_pw_aff_foreach_pw_aff(upa, &map_from_pw_aff_entry,
466
9.02k
            &umap) < 0)
467
0
    umap = isl_union_map_free(umap);
468
9.02k
469
9.02k
  isl_union_pw_aff_free(upa);
470
9.02k
  return umap;
471
9.02k
}
472
473
/* Convert "pma" to an isl_map and add it to *umap.
474
 */
475
static isl_stat map_from_pw_multi_aff(__isl_take isl_pw_multi_aff *pma,
476
  void *user)
477
7.20k
{
478
7.20k
  isl_union_map **umap = user;
479
7.20k
  isl_map *map;
480
7.20k
481
7.20k
  map = isl_map_from_pw_multi_aff(pma);
482
7.20k
  *umap = isl_union_map_add_map(*umap, map);
483
7.20k
484
7.20k
  return isl_stat_ok;
485
7.20k
}
486
487
/* Construct a union map mapping the domain of the union
488
 * piecewise multi-affine expression to its range, with each dimension
489
 * in the range equated to the corresponding affine expression on its cell.
490
 */
491
__isl_give isl_union_map *isl_union_map_from_union_pw_multi_aff(
492
  __isl_take isl_union_pw_multi_aff *upma)
493
7.39k
{
494
7.39k
  isl_space *space;
495
7.39k
  isl_union_map *umap;
496
7.39k
497
7.39k
  if (!upma)
498
0
    return NULL;
499
7.39k
500
7.39k
  space = isl_union_pw_multi_aff_get_space(upma);
501
7.39k
  umap = isl_union_map_empty(space);
502
7.39k
503
7.39k
  if (isl_union_pw_multi_aff_foreach_pw_multi_aff(upma,
504
7.39k
          &map_from_pw_multi_aff, &umap) < 0)
505
0
    goto error;
506
7.39k
507
7.39k
  isl_union_pw_multi_aff_free(upma);
508
7.39k
  return umap;
509
0
error:
510
0
  isl_union_pw_multi_aff_free(upma);
511
0
  isl_union_map_free(umap);
512
0
  return NULL;
513
7.39k
}