Coverage Report

Created: 2017-04-29 12:21

/Users/buildslave/jenkins/sharedspace/clang-stage2-coverage-R@2/llvm/tools/polly/lib/External/isl/isl_local_space.c
Line
Count
Source (jump to first uncovered line)
1
/*
2
 * Copyright 2011      INRIA Saclay
3
 * Copyright 2012-2014 Ecole Normale Superieure
4
 *
5
 * Use of this software is governed by the MIT license
6
 *
7
 * Written by Sven Verdoolaege, INRIA Saclay - Ile-de-France,
8
 * Parc Club Orsay Universite, ZAC des vignes, 4 rue Jacques Monod,
9
 * 91893 Orsay, France
10
 * and Ecole Normale Superieure, 45 rue d’Ulm, 75230 Paris, France
11
 */
12
13
#include <isl_ctx_private.h>
14
#include <isl_map_private.h>
15
#include <isl_local_space_private.h>
16
#include <isl_space_private.h>
17
#include <isl_mat_private.h>
18
#include <isl_aff_private.h>
19
#include <isl_vec_private.h>
20
#include <isl_seq.h>
21
#include <isl_local.h>
22
23
isl_ctx *isl_local_space_get_ctx(__isl_keep isl_local_space *ls)
24
940k
{
25
940k
  return ls ? ls->dim->ctx : NULL;
26
940k
}
27
28
/* Return a hash value that digests "ls".
29
 */
30
uint32_t isl_local_space_get_hash(__isl_keep isl_local_space *ls)
31
0
{
32
0
  uint32_t hash, space_hash, div_hash;
33
0
34
0
  if (!ls)
35
0
    return 0;
36
0
37
0
  
hash = 0
isl_hash_init0
();
38
0
  space_hash = isl_space_get_hash(ls->dim);
39
0
  isl_hash_hash(hash, space_hash);
40
0
  div_hash = isl_mat_get_hash(ls->div);
41
0
  isl_hash_hash(hash, div_hash);
42
0
43
0
  return hash;
44
0
}
45
46
__isl_give isl_local_space *isl_local_space_alloc_div(__isl_take isl_space *dim,
47
  __isl_take isl_mat *div)
48
200k
{
49
200k
  isl_ctx *ctx;
50
200k
  isl_local_space *ls = NULL;
51
200k
52
200k
  if (
!dim || 200k
!div200k
)
53
0
    goto error;
54
200k
55
200k
  ctx = isl_space_get_ctx(dim);
56
200k
  ls = isl_calloc_type(ctx, struct isl_local_space);
57
200k
  if (!ls)
58
0
    goto error;
59
200k
60
200k
  ls->ref = 1;
61
200k
  ls->dim = dim;
62
200k
  ls->div = div;
63
200k
64
200k
  return ls;
65
0
error:
66
0
  isl_mat_free(div);
67
0
  isl_space_free(dim);
68
0
  isl_local_space_free(ls);
69
0
  return NULL;
70
200k
}
71
72
__isl_give isl_local_space *isl_local_space_alloc(__isl_take isl_space *dim,
73
  unsigned n_div)
74
87.4k
{
75
87.4k
  isl_ctx *ctx;
76
87.4k
  isl_mat *div;
77
87.4k
  unsigned total;
78
87.4k
79
87.4k
  if (!dim)
80
0
    return NULL;
81
87.4k
82
87.4k
  total = isl_space_dim(dim, isl_dim_all);
83
87.4k
84
87.4k
  ctx = isl_space_get_ctx(dim);
85
87.4k
  div = isl_mat_alloc(ctx, n_div, 1 + 1 + total + n_div);
86
87.4k
  return isl_local_space_alloc_div(dim, div);
87
87.4k
}
88
89
__isl_give isl_local_space *isl_local_space_from_space(__isl_take isl_space *dim)
90
78.2k
{
91
78.2k
  return isl_local_space_alloc(dim, 0);
92
78.2k
}
93
94
__isl_give isl_local_space *isl_local_space_copy(__isl_keep isl_local_space *ls)
95
291k
{
96
291k
  if (!ls)
97
0
    return NULL;
98
291k
99
291k
  ls->ref++;
100
291k
  return ls;
101
291k
}
102
103
__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
104
88.9k
{
105
88.9k
  if (!ls)
106
0
    return NULL;
107
88.9k
108
88.9k
  return isl_local_space_alloc_div(isl_space_copy(ls->dim),
109
88.9k
           isl_mat_copy(ls->div));
110
88.9k
111
88.9k
}
112
113
__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
114
193k
{
115
193k
  if (!ls)
116
0
    return NULL;
117
193k
118
193k
  
if (193k
ls->ref == 1193k
)
119
104k
    return ls;
120
88.9k
  ls->ref--;
121
88.9k
  return isl_local_space_dup(ls);
122
193k
}
123
124
__isl_null isl_local_space *isl_local_space_free(
125
  __isl_take isl_local_space *ls)
126
403k
{
127
403k
  if (!ls)
128
0
    return NULL;
129
403k
130
403k
  
if (403k
--ls->ref > 0403k
)
131
202k
    return NULL;
132
403k
133
200k
  isl_space_free(ls->dim);
134
200k
  isl_mat_free(ls->div);
135
200k
136
200k
  free(ls);
137
200k
138
200k
  return NULL;
139
403k
}
140
141
/* Is the local space that of a parameter domain?
142
 */
143
isl_bool isl_local_space_is_params(__isl_keep isl_local_space *ls)
144
0
{
145
0
  if (!ls)
146
0
    return isl_bool_error;
147
0
  return isl_space_is_params(ls->dim);
148
0
}
149
150
/* Is the local space that of a set?
151
 */
152
isl_bool isl_local_space_is_set(__isl_keep isl_local_space *ls)
153
108k
{
154
108k
  return ls ? 
isl_space_is_set(ls->dim)108k
:
isl_bool_error0
;
155
108k
}
156
157
/* Do "ls1" and "ls2" have the same space?
158
 */
159
isl_bool isl_local_space_has_equal_space(__isl_keep isl_local_space *ls1,
160
  __isl_keep isl_local_space *ls2)
161
625k
{
162
625k
  if (
!ls1 || 625k
!ls2625k
)
163
0
    return isl_bool_error;
164
625k
165
625k
  return isl_space_is_equal(ls1->dim, ls2->dim);
166
625k
}
167
168
/* Return true if the two local spaces are identical, with identical
169
 * expressions for the integer divisions.
170
 */
171
isl_bool isl_local_space_is_equal(__isl_keep isl_local_space *ls1,
172
  __isl_keep isl_local_space *ls2)
173
5.45k
{
174
5.45k
  isl_bool equal;
175
5.45k
176
5.45k
  equal = isl_local_space_has_equal_space(ls1, ls2);
177
5.45k
  if (
equal < 0 || 5.45k
!equal5.45k
)
178
0
    return equal;
179
5.45k
180
5.45k
  
if (5.45k
!isl_local_space_divs_known(ls1)5.45k
)
181
0
    return isl_bool_false;
182
5.45k
  
if (5.45k
!isl_local_space_divs_known(ls2)5.45k
)
183
0
    return isl_bool_false;
184
5.45k
185
5.45k
  return isl_mat_is_equal(ls1->div, ls2->div);
186
5.45k
}
187
188
/* Compare two isl_local_spaces.
189
 *
190
 * Return -1 if "ls1" is "smaller" than "ls2", 1 if "ls1" is "greater"
191
 * than "ls2" and 0 if they are equal.
192
 */
193
int isl_local_space_cmp(__isl_keep isl_local_space *ls1,
194
  __isl_keep isl_local_space *ls2)
195
3.54k
{
196
3.54k
  int cmp;
197
3.54k
198
3.54k
  if (ls1 == ls2)
199
1
    return 0;
200
3.53k
  
if (3.53k
!ls13.53k
)
201
0
    return -1;
202
3.53k
  
if (3.53k
!ls23.53k
)
203
0
    return 1;
204
3.53k
205
3.53k
  cmp = isl_space_cmp(ls1->dim, ls2->dim);
206
3.53k
  if (cmp != 0)
207
0
    return cmp;
208
3.53k
209
3.53k
  return isl_local_cmp(ls1->div, ls2->div);
210
3.53k
}
211
212
int isl_local_space_dim(__isl_keep isl_local_space *ls,
213
  enum isl_dim_type type)
214
1.50M
{
215
1.50M
  if (!ls)
216
0
    return 0;
217
1.50M
  
if (1.50M
type == isl_dim_div1.50M
)
218
1.13M
    return ls->div->n_row;
219
369k
  
if (369k
type == isl_dim_all369k
)
220
143k
    return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
221
225k
  return isl_space_dim(ls->dim, type);
222
369k
}
223
224
unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
225
  enum isl_dim_type type)
226
250k
{
227
250k
  isl_space *dim;
228
250k
229
250k
  if (!ls)
230
0
    return 0;
231
250k
232
250k
  dim = ls->dim;
233
250k
  switch (type) {
234
0
  case isl_dim_cst: return 0;
235
7.86k
  case isl_dim_param: return 1;
236
10.8k
  case isl_dim_in:  return 1 + dim->nparam;
237
127k
  case isl_dim_out: return 1 + dim->nparam + dim->n_in;
238
103k
  case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out;
239
0
  default:    return 0;
240
250k
  }
241
250k
}
242
243
/* Return the position of the dimension of the given type and name
244
 * in "ls".
245
 * Return -1 if no such dimension can be found.
246
 */
247
int isl_local_space_find_dim_by_name(__isl_keep isl_local_space *ls,
248
  enum isl_dim_type type, const char *name)
249
0
{
250
0
  if (!ls)
251
0
    return -1;
252
0
  
if (0
type == isl_dim_div0
)
253
0
    return -1;
254
0
  return isl_space_find_dim_by_name(ls->dim, type, name);
255
0
}
256
257
/* Does the given dimension have a name?
258
 */
259
isl_bool isl_local_space_has_dim_name(__isl_keep isl_local_space *ls,
260
  enum isl_dim_type type, unsigned pos)
261
0
{
262
0
  return ls ? 
isl_space_has_dim_name(ls->dim, type, pos)0
:
isl_bool_error0
;
263
0
}
264
265
const char *isl_local_space_get_dim_name(__isl_keep isl_local_space *ls,
266
  enum isl_dim_type type, unsigned pos)
267
0
{
268
0
  return ls ? isl_space_get_dim_name(ls->dim, type, pos) : NULL;
269
0
}
270
271
isl_bool isl_local_space_has_dim_id(__isl_keep isl_local_space *ls,
272
  enum isl_dim_type type, unsigned pos)
273
932
{
274
932
  return ls ? 
isl_space_has_dim_id(ls->dim, type, pos)932
:
isl_bool_error0
;
275
932
}
276
277
__isl_give isl_id *isl_local_space_get_dim_id(__isl_keep isl_local_space *ls,
278
  enum isl_dim_type type, unsigned pos)
279
932
{
280
932
  return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
281
932
}
282
283
/* Return the argument of the integer division at position "pos" in "ls".
284
 * All local variables in "ls" are known to have a (complete) explicit
285
 * representation.
286
 */
287
static __isl_give isl_aff *extract_div(__isl_keep isl_local_space *ls, int pos)
288
166
{
289
166
  isl_aff *aff;
290
166
291
166
  aff = isl_aff_alloc(isl_local_space_copy(ls));
292
166
  if (!aff)
293
0
    return NULL;
294
166
  isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
295
166
  return aff;
296
166
}
297
298
/* Return the argument of the integer division at position "pos" in "ls".
299
 * The integer division at that position is known to have a complete
300
 * explicit representation, but some of the others do not.
301
 * Remove them first because the domain of an isl_aff
302
 * is not allowed to have unknown local variables.
303
 */
304
static __isl_give isl_aff *drop_unknown_divs_and_extract_div(
305
  __isl_keep isl_local_space *ls, int pos)
306
0
{
307
0
  int i, n;
308
0
  isl_bool unknown;
309
0
  isl_aff *aff;
310
0
311
0
  ls = isl_local_space_copy(ls);
312
0
  n = isl_local_space_dim(ls, isl_dim_div);
313
0
  for (i = n - 1; 
i >= 00
;
--i0
)
{0
314
0
    unknown = isl_local_space_div_is_marked_unknown(ls, i);
315
0
    if (unknown < 0)
316
0
      ls = isl_local_space_free(ls);
317
0
    else 
if (0
!unknown0
)
318
0
      continue;
319
0
    ls = isl_local_space_drop_dims(ls, isl_dim_div, i, 1);
320
0
    if (pos > i)
321
0
      --pos;
322
0
  }
323
0
  aff = extract_div(ls, pos);
324
0
  isl_local_space_free(ls);
325
0
  return aff;
326
0
}
327
328
/* Return the argument of the integer division at position "pos" in "ls".
329
 * The integer division is assumed to have a complete explicit
330
 * representation.  If some of the other integer divisions
331
 * do not have an explicit representation, then they need
332
 * to be removed first because the domain of an isl_aff
333
 * is not allowed to have unknown local variables.
334
 */
335
__isl_give isl_aff *isl_local_space_get_div(__isl_keep isl_local_space *ls,
336
  int pos)
337
166
{
338
166
  isl_bool known;
339
166
340
166
  if (!ls)
341
0
    return NULL;
342
166
343
166
  
if (166
pos < 0 || 166
pos >= ls->div->n_row166
)
344
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
345
166
      "index out of bounds", return NULL);
346
166
347
166
  known = isl_local_space_div_is_known(ls, pos);
348
166
  if (known < 0)
349
0
    return NULL;
350
166
  
if (166
!known166
)
351
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
352
166
      "expression of div unknown", return NULL);
353
166
  
if (166
!isl_local_space_is_set(ls)166
)
354
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
355
166
      "cannot represent divs of map spaces", return NULL);
356
166
357
166
  known = isl_local_space_divs_known(ls);
358
166
  if (known < 0)
359
0
    return NULL;
360
166
  
if (166
known166
)
361
166
    return extract_div(ls, pos);
362
166
  else
363
0
    return drop_unknown_divs_and_extract_div(ls, pos);
364
166
}
365
366
__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
367
1.24M
{
368
1.24M
  if (!ls)
369
0
    return NULL;
370
1.24M
371
1.24M
  return isl_space_copy(ls->dim);
372
1.24M
}
373
374
/* Replace the identifier of the tuple of type "type" by "id".
375
 */
376
__isl_give isl_local_space *isl_local_space_set_tuple_id(
377
  __isl_take isl_local_space *ls,
378
  enum isl_dim_type type, __isl_take isl_id *id)
379
0
{
380
0
  ls = isl_local_space_cow(ls);
381
0
  if (!ls)
382
0
    goto error;
383
0
  ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
384
0
  if (!ls->dim)
385
0
    return isl_local_space_free(ls);
386
0
  return ls;
387
0
error:
388
0
  isl_id_free(id);
389
0
  return NULL;
390
0
}
391
392
__isl_give isl_local_space *isl_local_space_set_dim_name(
393
  __isl_take isl_local_space *ls,
394
  enum isl_dim_type type, unsigned pos, const char *s)
395
0
{
396
0
  ls = isl_local_space_cow(ls);
397
0
  if (!ls)
398
0
    return NULL;
399
0
  ls->dim = isl_space_set_dim_name(ls->dim, type, pos, s);
400
0
  if (!ls->dim)
401
0
    return isl_local_space_free(ls);
402
0
403
0
  return ls;
404
0
}
405
406
__isl_give isl_local_space *isl_local_space_set_dim_id(
407
  __isl_take isl_local_space *ls,
408
  enum isl_dim_type type, unsigned pos, __isl_take isl_id *id)
409
0
{
410
0
  ls = isl_local_space_cow(ls);
411
0
  if (!ls)
412
0
    goto error;
413
0
  ls->dim = isl_space_set_dim_id(ls->dim, type, pos, id);
414
0
  if (!ls->dim)
415
0
    return isl_local_space_free(ls);
416
0
417
0
  return ls;
418
0
error:
419
0
  isl_id_free(id);
420
0
  return NULL;
421
0
}
422
423
__isl_give isl_local_space *isl_local_space_reset_space(
424
  __isl_take isl_local_space *ls, __isl_take isl_space *dim)
425
52.4k
{
426
52.4k
  ls = isl_local_space_cow(ls);
427
52.4k
  if (
!ls || 52.4k
!dim52.4k
)
428
0
    goto error;
429
52.4k
430
52.4k
  isl_space_free(ls->dim);
431
52.4k
  ls->dim = dim;
432
52.4k
433
52.4k
  return ls;
434
0
error:
435
0
  isl_local_space_free(ls);
436
0
  isl_space_free(dim);
437
0
  return NULL;
438
52.4k
}
439
440
/* Reorder the columns of the given div definitions according to the
441
 * given reordering.
442
 * The order of the divs themselves is assumed not to change.
443
 */
444
static __isl_give isl_mat *reorder_divs(__isl_take isl_mat *div,
445
  __isl_take isl_reordering *r)
446
7.63k
{
447
7.63k
  int i, j;
448
7.63k
  isl_mat *mat;
449
7.63k
  int extra;
450
7.63k
451
7.63k
  if (
!div || 7.63k
!r7.63k
)
452
0
    goto error;
453
7.63k
454
7.63k
  extra = isl_space_dim(r->dim, isl_dim_all) + div->n_row - r->len;
455
7.63k
  mat = isl_mat_alloc(div->ctx, div->n_row, div->n_col + extra);
456
7.63k
  if (!mat)
457
0
    goto error;
458
7.63k
459
7.79k
  
for (i = 0; 7.63k
i < div->n_row7.79k
;
++i166
)
{166
460
166
    isl_seq_cpy(mat->row[i], div->row[i], 2);
461
166
    isl_seq_clr(mat->row[i] + 2, mat->n_col - 2);
462
791
    for (j = 0; 
j < r->len791
;
++j625
)
463
625
      isl_int_set(mat->row[i][2 + r->pos[j]],
464
166
            div->row[i][2 + j]);
465
166
  }
466
7.63k
467
7.63k
  isl_reordering_free(r);
468
7.63k
  isl_mat_free(div);
469
7.63k
  return mat;
470
0
error:
471
0
  isl_reordering_free(r);
472
0
  isl_mat_free(div);
473
0
  return NULL;
474
7.63k
}
475
476
/* Reorder the dimensions of "ls" according to the given reordering.
477
 * The reordering r is assumed to have been extended with the local
478
 * variables, leaving them in the same order.
479
 */
480
__isl_give isl_local_space *isl_local_space_realign(
481
  __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
482
7.63k
{
483
7.63k
  ls = isl_local_space_cow(ls);
484
7.63k
  if (
!ls || 7.63k
!r7.63k
)
485
0
    goto error;
486
7.63k
487
7.63k
  ls->div = reorder_divs(ls->div, isl_reordering_copy(r));
488
7.63k
  if (!ls->div)
489
0
    goto error;
490
7.63k
491
7.63k
  ls = isl_local_space_reset_space(ls, isl_space_copy(r->dim));
492
7.63k
493
7.63k
  isl_reordering_free(r);
494
7.63k
  return ls;
495
0
error:
496
0
  isl_local_space_free(ls);
497
0
  isl_reordering_free(r);
498
0
  return NULL;
499
7.63k
}
500
501
__isl_give isl_local_space *isl_local_space_add_div(
502
  __isl_take isl_local_space *ls, __isl_take isl_vec *div)
503
3.62k
{
504
3.62k
  ls = isl_local_space_cow(ls);
505
3.62k
  if (
!ls || 3.62k
!div3.62k
)
506
0
    goto error;
507
3.62k
508
3.62k
  
if (3.62k
ls->div->n_col != div->size3.62k
)
509
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
510
3.62k
      "incompatible dimensions", goto error);
511
3.62k
512
3.62k
  ls->div = isl_mat_add_zero_cols(ls->div, 1);
513
3.62k
  ls->div = isl_mat_add_rows(ls->div, 1);
514
3.62k
  if (!ls->div)
515
0
    goto error;
516
3.62k
517
3.62k
  isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
518
3.62k
  isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
519
3.62k
520
3.62k
  isl_vec_free(div);
521
3.62k
  return ls;
522
0
error:
523
0
  isl_local_space_free(ls);
524
0
  isl_vec_free(div);
525
0
  return NULL;
526
3.62k
}
527
528
__isl_give isl_local_space *isl_local_space_replace_divs(
529
  __isl_take isl_local_space *ls, __isl_take isl_mat *div)
530
36.9k
{
531
36.9k
  ls = isl_local_space_cow(ls);
532
36.9k
533
36.9k
  if (
!ls || 36.9k
!div36.9k
)
534
0
    goto error;
535
36.9k
536
36.9k
  isl_mat_free(ls->div);
537
36.9k
  ls->div = div;
538
36.9k
  return ls;
539
0
error:
540
0
  isl_mat_free(div);
541
0
  isl_local_space_free(ls);
542
0
  return NULL;
543
36.9k
}
544
545
/* Copy row "s" of "src" to row "d" of "dst", applying the expansion
546
 * defined by "exp".
547
 */
548
static void expand_row(__isl_keep isl_mat *dst, int d,
549
  __isl_keep isl_mat *src, int s, int *exp)
550
27.0k
{
551
27.0k
  int i;
552
27.0k
  unsigned c = src->n_col - src->n_row;
553
27.0k
554
27.0k
  isl_seq_cpy(dst->row[d], src->row[s], c);
555
27.0k
  isl_seq_clr(dst->row[d] + c, dst->n_col - c);
556
27.0k
557
28.3k
  for (i = 0; 
i < s28.3k
;
++i1.33k
)
558
1.33k
    isl_int_set(dst->row[d][c + exp[i]], src->row[s][c + i]);
559
27.0k
}
560
561
/* Compare (known) divs.
562
 * Return non-zero if at least one of the two divs is unknown.
563
 * In particular, if both divs are unknown, we respect their
564
 * current order.  Otherwise, we sort the known div after the unknown
565
 * div only if the known div depends on the unknown div.
566
 */
567
static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
568
  unsigned n_row, unsigned n_col)
569
6.91k
{
570
6.91k
  int li, lj;
571
6.91k
  int unknown_i, unknown_j;
572
6.91k
573
6.91k
  unknown_i = isl_int_is_zero(row_i[0]);
574
6.91k
  unknown_j = isl_int_is_zero(row_j[0]);
575
6.91k
576
6.91k
  if (
unknown_i && 6.91k
unknown_j2.54k
)
577
535
    return i - j;
578
6.91k
579
6.38k
  
if (6.38k
unknown_i6.38k
)
580
2.00k
    li = n_col - n_row + i;
581
6.38k
  else
582
4.37k
    li = isl_seq_last_non_zero(row_i, n_col);
583
6.38k
  if (unknown_j)
584
251
    lj = n_col - n_row + j;
585
6.38k
  else
586
6.12k
    lj = isl_seq_last_non_zero(row_j, n_col);
587
6.38k
588
6.38k
  if (li != lj)
589
2.90k
    return li - lj;
590
6.38k
591
3.47k
  return isl_seq_cmp(row_i, row_j, n_col);
592
6.38k
}
593
594
/* Call cmp_row for divs in a matrix.
595
 */
596
int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
597
3.00k
{
598
3.00k
  return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
599
3.00k
}
600
601
/* Call cmp_row for divs in a basic map.
602
 */
603
static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
604
  unsigned total)
605
3.90k
{
606
3.90k
  return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
607
3.90k
}
608
609
/* Sort the divs in "bmap".
610
 *
611
 * We first make sure divs are placed after divs on which they depend.
612
 * Then we perform a simple insertion sort based on the same ordering
613
 * that is used in isl_merge_divs.
614
 */
615
__isl_give isl_basic_map *isl_basic_map_sort_divs(
616
  __isl_take isl_basic_map *bmap)
617
55.9k
{
618
55.9k
  int i, j;
619
55.9k
  unsigned total;
620
55.9k
621
55.9k
  bmap = isl_basic_map_order_divs(bmap);
622
55.9k
  if (!bmap)
623
0
    return NULL;
624
55.9k
  
if (55.9k
bmap->n_div <= 155.9k
)
625
54.1k
    return bmap;
626
55.9k
627
1.78k
  total = 2 + isl_basic_map_total_dim(bmap);
628
4.76k
  for (i = 1; 
i < bmap->n_div4.76k
;
++i2.97k
)
{2.97k
629
4.36k
    for (j = i - 1; 
j >= 04.36k
;
--j1.38k
)
{3.90k
630
3.90k
      if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
631
2.51k
        break;
632
1.38k
      isl_basic_map_swap_div(bmap, j, j + 1);
633
1.38k
    }
634
2.97k
  }
635
1.78k
636
1.78k
  return bmap;
637
55.9k
}
638
639
/* Sort the divs in the basic maps of "map".
640
 */
641
__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
642
22.6k
{
643
22.6k
  return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
644
22.6k
}
645
646
/* Combine the two lists of divs into a single list.
647
 * For each row i in div1, exp1[i] is set to the position of the corresponding
648
 * row in the result.  Similarly for div2 and exp2.
649
 * This function guarantees
650
 *  exp1[i] >= i
651
 *  exp1[i+1] > exp1[i]
652
 * For optimal merging, the two input list should have been sorted.
653
 */
654
__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
655
  __isl_keep isl_mat *div2, int *exp1, int *exp2)
656
25.3k
{
657
25.3k
  int i, j, k;
658
25.3k
  isl_mat *div = NULL;
659
25.3k
  unsigned d;
660
25.3k
661
25.3k
  if (
!div1 || 25.3k
!div225.3k
)
662
0
    return NULL;
663
25.3k
664
25.3k
  d = div1->n_col - div1->n_row;
665
25.3k
  div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
666
25.3k
        d + div1->n_row + div2->n_row);
667
25.3k
  if (!div)
668
0
    return NULL;
669
25.3k
670
26.1k
  
for (i = 0, j = 0, k = 0; 25.3k
i < div1->n_row && 26.1k
j < div2->n_row13.0k
;
++k785
)
{785
671
785
    int cmp;
672
785
673
785
    expand_row(div, k, div1, i, exp1);
674
785
    expand_row(div, k + 1, div2, j, exp2);
675
785
676
785
    cmp = isl_mat_cmp_div(div, k, k + 1);
677
785
    if (
cmp == 0785
)
{496
678
496
      exp1[i++] = k;
679
496
      exp2[j++] = k;
680
289
    } else 
if (289
cmp < 0289
)
{51
681
51
      exp1[i++] = k;
682
238
    } else {
683
238
      exp2[j++] = k;
684
238
      isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
685
238
    }
686
785
  }
687
37.8k
  for (; 
i < div1->n_row37.8k
;
++i, ++k12.4k
)
{12.4k
688
12.4k
    expand_row(div, k, div1, i, exp1);
689
12.4k
    exp1[i] = k;
690
12.4k
  }
691
38.3k
  for (; 
j < div2->n_row38.3k
;
++j, ++k12.9k
)
{12.9k
692
12.9k
    expand_row(div, k, div2, j, exp2);
693
12.9k
    exp2[j] = k;
694
12.9k
  }
695
25.3k
696
25.3k
  div->n_row = k;
697
25.3k
  div->n_col = d + k;
698
25.3k
699
25.3k
  return div;
700
25.3k
}
701
702
/* Swap divs "a" and "b" in "ls".
703
 */
704
__isl_give isl_local_space *isl_local_space_swap_div(
705
  __isl_take isl_local_space *ls, int a, int b)
706
1.23k
{
707
1.23k
  int offset;
708
1.23k
709
1.23k
  ls = isl_local_space_cow(ls);
710
1.23k
  if (!ls)
711
0
    return NULL;
712
1.23k
  
if (1.23k
a < 0 || 1.23k
a >= ls->div->n_row1.23k
||
b < 01.23k
||
b >= ls->div->n_row1.23k
)
713
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
714
1.23k
      "index out of bounds", return isl_local_space_free(ls));
715
1.23k
  offset = ls->div->n_col - ls->div->n_row;
716
1.23k
  ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
717
1.23k
  ls->div = isl_mat_swap_rows(ls->div, a, b);
718
1.23k
  if (!ls->div)
719
0
    return isl_local_space_free(ls);
720
1.23k
  return ls;
721
1.23k
}
722
723
/* Construct a local space that contains all the divs in either
724
 * "ls1" or "ls2".
725
 */
726
__isl_give isl_local_space *isl_local_space_intersect(
727
  __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
728
0
{
729
0
  isl_ctx *ctx;
730
0
  int *exp1 = NULL;
731
0
  int *exp2 = NULL;
732
0
  isl_mat *div = NULL;
733
0
  isl_bool equal;
734
0
735
0
  if (
!ls1 || 0
!ls20
)
736
0
    goto error;
737
0
738
0
  ctx = isl_local_space_get_ctx(ls1);
739
0
  if (!isl_space_is_equal(ls1->dim, ls2->dim))
740
0
    isl_die(ctx, isl_error_invalid,
741
0
      "spaces should be identical", goto error);
742
0
743
0
  
if (0
ls2->div->n_row == 00
)
{0
744
0
    isl_local_space_free(ls2);
745
0
    return ls1;
746
0
  }
747
0
748
0
  
if (0
ls1->div->n_row == 00
)
{0
749
0
    isl_local_space_free(ls1);
750
0
    return ls2;
751
0
  }
752
0
753
0
  
exp1 = 0
isl_alloc_array0
(ctx, int, ls1->div->n_row);
754
0
  exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
755
0
  if (
!exp1 || 0
!exp20
)
756
0
    goto error;
757
0
758
0
  div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
759
0
  if (!div)
760
0
    goto error;
761
0
762
0
  equal = isl_mat_is_equal(ls1->div, div);
763
0
  if (equal < 0)
764
0
    goto error;
765
0
  
if (0
!equal0
)
766
0
    ls1 = isl_local_space_cow(ls1);
767
0
  if (!ls1)
768
0
    goto error;
769
0
770
0
  free(exp1);
771
0
  free(exp2);
772
0
  isl_local_space_free(ls2);
773
0
  isl_mat_free(ls1->div);
774
0
  ls1->div = div;
775
0
776
0
  return ls1;
777
0
error:
778
0
  free(exp1);
779
0
  free(exp2);
780
0
  isl_mat_free(div);
781
0
  isl_local_space_free(ls1);
782
0
  isl_local_space_free(ls2);
783
0
  return NULL;
784
0
}
785
786
/* Is the local variable "div" of "ls" marked as not having
787
 * an explicit representation?
788
 * Note that even if this variable is not marked in this way and therefore
789
 * does have an explicit representation, this representation may still
790
 * depend (indirectly) on other local variables that do not
791
 * have an explicit representation.
792
 */
793
isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
794
  int div)
795
13.3k
{
796
13.3k
  if (!ls)
797
0
    return isl_bool_error;
798
13.3k
  return isl_local_div_is_marked_unknown(ls->div, div);
799
13.3k
}
800
801
/* Does "ls" have a complete explicit representation for div "div"?
802
 */
803
isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
804
539
{
805
539
  if (!ls)
806
0
    return isl_bool_error;
807
539
  return isl_local_div_is_known(ls->div, div);
808
539
}
809
810
/* Does "ls" have an explicit representation for all local variables?
811
 */
812
isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
813
119k
{
814
119k
  int i;
815
119k
816
119k
  if (!ls)
817
0
    return isl_bool_error;
818
119k
819
132k
  
for (i = 0; 119k
i < ls->div->n_row132k
;
++i13.3k
)
{13.3k
820
13.3k
    isl_bool unknown = isl_local_space_div_is_marked_unknown(ls, i);
821
13.3k
    if (
unknown < 0 || 13.3k
unknown13.3k
)
822
0
      return isl_bool_not(unknown);
823
13.3k
  }
824
119k
825
119k
  return isl_bool_true;
826
119k
}
827
828
__isl_give isl_local_space *isl_local_space_domain(
829
  __isl_take isl_local_space *ls)
830
4.91k
{
831
4.91k
  ls = isl_local_space_drop_dims(ls, isl_dim_out,
832
4.91k
          0, isl_local_space_dim(ls, isl_dim_out));
833
4.91k
  ls = isl_local_space_cow(ls);
834
4.91k
  if (!ls)
835
0
    return NULL;
836
4.91k
  ls->dim = isl_space_domain(ls->dim);
837
4.91k
  if (!ls->dim)
838
0
    return isl_local_space_free(ls);
839
4.91k
  return ls;
840
4.91k
}
841
842
__isl_give isl_local_space *isl_local_space_range(
843
  __isl_take isl_local_space *ls)
844
0
{
845
0
  ls = isl_local_space_drop_dims(ls, isl_dim_in,
846
0
          0, isl_local_space_dim(ls, isl_dim_in));
847
0
  ls = isl_local_space_cow(ls);
848
0
  if (!ls)
849
0
    return NULL;
850
0
851
0
  ls->dim = isl_space_range(ls->dim);
852
0
  if (!ls->dim)
853
0
    return isl_local_space_free(ls);
854
0
  return ls;
855
0
}
856
857
/* Construct a local space for a map that has the given local
858
 * space as domain and that has a zero-dimensional range.
859
 */
860
__isl_give isl_local_space *isl_local_space_from_domain(
861
  __isl_take isl_local_space *ls)
862
37.2k
{
863
37.2k
  ls = isl_local_space_cow(ls);
864
37.2k
  if (!ls)
865
0
    return NULL;
866
37.2k
  ls->dim = isl_space_from_domain(ls->dim);
867
37.2k
  if (!ls->dim)
868
0
    return isl_local_space_free(ls);
869
37.2k
  return ls;
870
37.2k
}
871
872
__isl_give isl_local_space *isl_local_space_add_dims(
873
  __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
874
37.2k
{
875
37.2k
  int pos;
876
37.2k
877
37.2k
  if (!ls)
878
0
    return NULL;
879
37.2k
  pos = isl_local_space_dim(ls, type);
880
37.2k
  return isl_local_space_insert_dims(ls, type, pos, n);
881
37.2k
}
882
883
/* Remove common factor of non-constant terms and denominator.
884
 */
885
static void normalize_div(__isl_keep isl_local_space *ls, int div)
886
286
{
887
286
  isl_ctx *ctx = ls->div->ctx;
888
286
  unsigned total = ls->div->n_col - 2;
889
286
890
286
  isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
891
286
  isl_int_gcd(ctx->normalize_gcd,
892
286
        ctx->normalize_gcd, ls->div->row[div][0]);
893
286
  if (isl_int_is_one(ctx->normalize_gcd))
894
219
    return;
895
286
896
67
  isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
897
67
          ctx->normalize_gcd, total);
898
67
  isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
899
67
          ctx->normalize_gcd);
900
67
  isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
901
67
          ctx->normalize_gcd);
902
67
}
903
904
/* Exploit the equalities in "eq" to simplify the expressions of
905
 * the integer divisions in "ls".
906
 * The integer divisions in "ls" are assumed to appear as regular
907
 * dimensions in "eq".
908
 */
909
__isl_give isl_local_space *isl_local_space_substitute_equalities(
910
  __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
911
901
{
912
901
  int i, j, k;
913
901
  unsigned total;
914
901
  unsigned n_div;
915
901
916
901
  if (
!ls || 901
!eq901
)
917
0
    goto error;
918
901
919
901
  total = isl_space_dim(eq->dim, isl_dim_all);
920
901
  if (isl_local_space_dim(ls, isl_dim_all) != total)
921
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
922
901
      "spaces don't match", goto error);
923
901
  total++;
924
901
  n_div = eq->n_div;
925
1.95k
  for (i = 0; 
i < eq->n_eq1.95k
;
++i1.05k
)
{1.05k
926
1.05k
    j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
927
1.05k
    if (
j < 0 || 1.05k
j == 01.05k
||
j >= total1.05k
)
928
323
      continue;
929
1.05k
930
1.23k
    
for (k = 0; 732
k < ls->div->n_row1.23k
;
++k499
)
{499
931
499
      if (isl_int_is_zero(ls->div->row[k][1 + j]))
932
425
        continue;
933
74
      ls = isl_local_space_cow(ls);
934
74
      if (!ls)
935
0
        goto error;
936
74
      ls->div = isl_mat_cow(ls->div);
937
74
      if (!ls->div)
938
0
        goto error;
939
74
      isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
940
74
          &ls->div->row[k][0]);
941
74
      normalize_div(ls, k);
942
74
    }
943
732
  }
944
901
945
901
  isl_basic_set_free(eq);
946
901
  return ls;
947
0
error:
948
0
  isl_basic_set_free(eq);
949
0
  isl_local_space_free(ls);
950
0
  return NULL;
951
901
}
952
953
/* Plug in the affine expressions "subs" of length "subs_len" (including
954
 * the denominator and the constant term) into the variable at position "pos"
955
 * of the "n" div expressions starting at "first".
956
 *
957
 * Let i be the dimension to replace and let "subs" be of the form
958
 *
959
 *  f/d
960
 *
961
 * Any integer division starting at "first" with a non-zero coefficient for i,
962
 *
963
 *  floor((a i + g)/m)
964
 *
965
 * is replaced by
966
 *
967
 *  floor((a f + d g)/(m d))
968
 */
969
__isl_give isl_local_space *isl_local_space_substitute_seq(
970
  __isl_take isl_local_space *ls,
971
  enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
972
  int first, int n)
973
428
{
974
428
  int i;
975
428
  isl_int v;
976
428
977
428
  if (n == 0)
978
192
    return ls;
979
236
  ls = isl_local_space_cow(ls);
980
236
  if (!ls)
981
0
    return NULL;
982
236
  ls->div = isl_mat_cow(ls->div);
983
236
  if (!ls->div)
984
0
    return isl_local_space_free(ls);
985
236
986
236
  
if (236
first + n > ls->div->n_row236
)
987
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
988
236
      "index out of bounds", return isl_local_space_free(ls));
989
236
990
236
  pos += isl_local_space_offset(ls, type);
991
236
992
236
  isl_int_init(v);
993
737
  for (i = first; 
i < first + n737
;
++i501
)
{501
994
501
    if (isl_int_is_zero(ls->div->row[i][1 + pos]))
995
400
      continue;
996
101
    isl_seq_substitute(ls->div->row[i], pos, subs,
997
101
      ls->div->n_col, subs_len, v);
998
101
    normalize_div(ls, i);
999
101
  }
1000
236
  isl_int_clear(v);
1001
236
1002
236
  return ls;
1003
236
}
1004
1005
/* Plug in "subs" for dimension "type", "pos" in the integer divisions
1006
 * of "ls".
1007
 *
1008
 * Let i be the dimension to replace and let "subs" be of the form
1009
 *
1010
 *  f/d
1011
 *
1012
 * Any integer division with a non-zero coefficient for i,
1013
 *
1014
 *  floor((a i + g)/m)
1015
 *
1016
 * is replaced by
1017
 *
1018
 *  floor((a f + d g)/(m d))
1019
 */
1020
__isl_give isl_local_space *isl_local_space_substitute(
1021
  __isl_take isl_local_space *ls,
1022
  enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
1023
144
{
1024
144
  ls = isl_local_space_cow(ls);
1025
144
  if (
!ls || 144
!subs144
)
1026
0
    return isl_local_space_free(ls);
1027
144
1028
144
  
if (144
!isl_space_is_equal(ls->dim, subs->ls->dim)144
)
1029
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1030
144
      "spaces don't match", return isl_local_space_free(ls));
1031
144
  
if (144
isl_local_space_dim(subs->ls, isl_dim_div) != 0144
)
1032
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1033
144
      "cannot handle divs yet",
1034
144
      return isl_local_space_free(ls));
1035
144
1036
144
  return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
1037
144
              subs->v->size, 0, ls->div->n_row);
1038
144
}
1039
1040
isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
1041
  enum isl_dim_type type)
1042
5.48k
{
1043
5.48k
  if (!ls)
1044
0
    return isl_bool_error;
1045
5.48k
  return isl_space_is_named_or_nested(ls->dim, type);
1046
5.48k
}
1047
1048
__isl_give isl_local_space *isl_local_space_drop_dims(
1049
  __isl_take isl_local_space *ls,
1050
  enum isl_dim_type type, unsigned first, unsigned n)
1051
10.0k
{
1052
10.0k
  isl_ctx *ctx;
1053
10.0k
1054
10.0k
  if (!ls)
1055
0
    return NULL;
1056
10.0k
  
if (10.0k
n == 0 && 10.0k
!isl_local_space_is_named_or_nested(ls, type)3.96k
)
1057
3.96k
    return ls;
1058
10.0k
1059
6.04k
  ctx = isl_local_space_get_ctx(ls);
1060
6.04k
  if (first + n > isl_local_space_dim(ls, type))
1061
0
    isl_die(ctx, isl_error_invalid, "range out of bounds",
1062
6.04k
      return isl_local_space_free(ls));
1063
6.04k
1064
6.04k
  ls = isl_local_space_cow(ls);
1065
6.04k
  if (!ls)
1066
0
    return NULL;
1067
6.04k
1068
6.04k
  
if (6.04k
type == isl_dim_div6.04k
)
{772
1069
772
    ls->div = isl_mat_drop_rows(ls->div, first, n);
1070
5.27k
  } else {
1071
5.27k
    ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
1072
5.27k
    if (!ls->dim)
1073
0
      return isl_local_space_free(ls);
1074
5.27k
  }
1075
6.04k
1076
6.04k
  first += 1 + isl_local_space_offset(ls, type);
1077
6.04k
  ls->div = isl_mat_drop_cols(ls->div, first, n);
1078
6.04k
  if (!ls->div)
1079
0
    return isl_local_space_free(ls);
1080
6.04k
1081
6.04k
  return ls;
1082
6.04k
}
1083
1084
__isl_give isl_local_space *isl_local_space_insert_dims(
1085
  __isl_take isl_local_space *ls,
1086
  enum isl_dim_type type, unsigned first, unsigned n)
1087
42.3k
{
1088
42.3k
  isl_ctx *ctx;
1089
42.3k
1090
42.3k
  if (!ls)
1091
0
    return NULL;
1092
42.3k
  
if (42.3k
n == 0 && 42.3k
!isl_local_space_is_named_or_nested(ls, type)2
)
1093
0
    return ls;
1094
42.3k
1095
42.3k
  ctx = isl_local_space_get_ctx(ls);
1096
42.3k
  if (first > isl_local_space_dim(ls, type))
1097
0
    isl_die(ctx, isl_error_invalid, "position out of bounds",
1098
42.3k
      return isl_local_space_free(ls));
1099
42.3k
1100
42.3k
  ls = isl_local_space_cow(ls);
1101
42.3k
  if (!ls)
1102
0
    return NULL;
1103
42.3k
1104
42.3k
  
if (42.3k
type == isl_dim_div42.3k
)
{0
1105
0
    ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1106
42.3k
  } else {
1107
42.3k
    ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1108
42.3k
    if (!ls->dim)
1109
0
      return isl_local_space_free(ls);
1110
42.3k
  }
1111
42.3k
1112
42.3k
  first += 1 + isl_local_space_offset(ls, type);
1113
42.3k
  ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1114
42.3k
  if (!ls->div)
1115
0
    return isl_local_space_free(ls);
1116
42.3k
1117
42.3k
  return ls;
1118
42.3k
}
1119
1120
/* Check if the constraints pointed to by "constraint" is a div
1121
 * constraint corresponding to div "div" in "ls".
1122
 *
1123
 * That is, if div = floor(f/m), then check if the constraint is
1124
 *
1125
 *    f - m d >= 0
1126
 * or
1127
 *    -(f-(m-1)) + m d >= 0
1128
 */
1129
isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1130
  isl_int *constraint, unsigned div)
1131
35
{
1132
35
  unsigned pos;
1133
35
1134
35
  if (!ls)
1135
0
    return isl_bool_error;
1136
35
1137
35
  
if (35
isl_int_is_zero35
(ls->div->row[div][0]))
1138
0
    return isl_bool_false;
1139
35
1140
35
  pos = isl_local_space_offset(ls, isl_dim_div) + div;
1141
35
1142
35
  if (
isl_int_eq35
(constraint[pos], ls->div->row[div][0]))
{10
1143
10
    int neg;
1144
10
    isl_int_sub(ls->div->row[div][1],
1145
10
        ls->div->row[div][1], ls->div->row[div][0]);
1146
10
    isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1147
10
    neg = isl_seq_is_neg(constraint, ls->div->row[div]+1, pos);
1148
10
    isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1149
10
    isl_int_add(ls->div->row[div][1],
1150
10
        ls->div->row[div][1], ls->div->row[div][0]);
1151
10
    if (!neg)
1152
1
      return isl_bool_false;
1153
9
    
if (9
isl_seq_first_non_zero(constraint+pos+1,9
1154
9
              ls->div->n_row-div-1) != -1)
1155
0
      return isl_bool_false;
1156
25
  } else 
if (25
isl_int_abs_eq25
(constraint[pos], ls->div->row[div][0]))
{12
1157
12
    if (!isl_seq_eq(constraint, ls->div->row[div]+1, pos))
1158
9
      return isl_bool_false;
1159
3
    
if (3
isl_seq_first_non_zero(constraint+pos+1,3
1160
3
              ls->div->n_row-div-1) != -1)
1161
0
      return isl_bool_false;
1162
3
  } else
1163
13
    return isl_bool_false;
1164
35
1165
12
  return isl_bool_true;
1166
35
}
1167
1168
/*
1169
 * Set active[i] to 1 if the dimension at position i is involved
1170
 * in the linear expression l.
1171
 */
1172
int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1173
12.4k
{
1174
12.4k
  int i, j;
1175
12.4k
  isl_ctx *ctx;
1176
12.4k
  int *active = NULL;
1177
12.4k
  unsigned total;
1178
12.4k
  unsigned offset;
1179
12.4k
1180
12.4k
  ctx = isl_local_space_get_ctx(ls);
1181
12.4k
  total = isl_local_space_dim(ls, isl_dim_all);
1182
12.4k
  active = isl_calloc_array(ctx, int, total);
1183
12.4k
  if (
total && 12.4k
!active12.4k
)
1184
0
    return NULL;
1185
12.4k
1186
101k
  
for (i = 0; 12.4k
i < total101k
;
++i88.8k
)
1187
88.8k
    
active[i] = !88.8k
isl_int_is_zero88.8k
(l[i]);
1188
12.4k
1189
12.4k
  offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1190
13.7k
  for (i = ls->div->n_row - 1; 
i >= 013.7k
;
--i1.38k
)
{1.38k
1191
1.38k
    if (!active[offset + i])
1192
1.27k
      continue;
1193
756
    
for (j = 0; 118
j < total756
;
++j638
)
1194
638
      
active[j] |= !638
isl_int_is_zero638
(ls->div->row[i][2 + j]);
1195
118
  }
1196
12.4k
1197
12.4k
  return active;
1198
12.4k
}
1199
1200
/* Given a local space "ls" of a set, create a local space
1201
 * for the lift of the set.  In particular, the result
1202
 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1203
 * range of the wrapped map.
1204
 */
1205
__isl_give isl_local_space *isl_local_space_lift(
1206
  __isl_take isl_local_space *ls)
1207
0
{
1208
0
  ls = isl_local_space_cow(ls);
1209
0
  if (!ls)
1210
0
    return NULL;
1211
0
1212
0
  ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1213
0
  ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1214
0
  if (
!ls->dim || 0
!ls->div0
)
1215
0
    return isl_local_space_free(ls);
1216
0
1217
0
  return ls;
1218
0
}
1219
1220
/* Construct a basic map that maps a set living in local space "ls"
1221
 * to the corresponding lifted local space.
1222
 */
1223
__isl_give isl_basic_map *isl_local_space_lifting(
1224
  __isl_take isl_local_space *ls)
1225
0
{
1226
0
  isl_basic_map *lifting;
1227
0
  isl_basic_set *bset;
1228
0
1229
0
  if (!ls)
1230
0
    return NULL;
1231
0
  
if (0
!isl_local_space_is_set(ls)0
)
1232
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1233
0
      "lifting only defined on set spaces", goto error);
1234
0
1235
0
  bset = isl_basic_set_from_local_space(ls);
1236
0
  lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1237
0
  lifting = isl_basic_map_domain_map(lifting);
1238
0
  lifting = isl_basic_map_reverse(lifting);
1239
0
1240
0
  return lifting;
1241
0
error:
1242
0
  isl_local_space_free(ls);
1243
0
  return NULL;
1244
0
}
1245
1246
/* Compute the preimage of "ls" under the function represented by "ma".
1247
 * In other words, plug in "ma" in "ls".  The result is a local space
1248
 * that is part of the domain space of "ma".
1249
 *
1250
 * If the divs in "ls" are represented as
1251
 *
1252
 *  floor((a_i(p) + b_i x + c_i(divs))/n_i)
1253
 *
1254
 * and ma is represented by
1255
 *
1256
 *  x = D(p) + F(y) + G(divs')
1257
 *
1258
 * then the resulting divs are
1259
 *
1260
 *  floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1261
 *
1262
 * We first copy over the divs from "ma" and then
1263
 * we add the modified divs from "ls".
1264
 */
1265
__isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1266
  __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1267
9.22k
{
1268
9.22k
  int i;
1269
9.22k
  isl_space *space;
1270
9.22k
  isl_local_space *res = NULL;
1271
9.22k
  int n_div_ls, n_div_ma;
1272
9.22k
  isl_int f, c1, c2, g;
1273
9.22k
1274
9.22k
  ma = isl_multi_aff_align_divs(ma);
1275
9.22k
  if (
!ls || 9.22k
!ma9.22k
)
1276
0
    goto error;
1277
9.22k
  
if (9.22k
!isl_space_is_range_internal(ls->dim, ma->space)9.22k
)
1278
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1279
9.22k
      "spaces don't match", goto error);
1280
9.22k
1281
9.22k
  n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1282
9.05k
  n_div_ma = ma->n ? 
isl_aff_dim(ma->p[0], isl_dim_div)9.05k
:
0175
;
1283
9.22k
1284
9.22k
  space = isl_space_domain(isl_multi_aff_get_space(ma));
1285
9.22k
  res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1286
9.22k
  if (!res)
1287
0
    goto error;
1288
9.22k
1289
9.22k
  
if (9.22k
n_div_ma9.22k
)
{106
1290
106
    isl_mat_free(res->div);
1291
106
    res->div = isl_mat_copy(ma->p[0]->ls->div);
1292
106
    res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1293
106
    res->div = isl_mat_add_rows(res->div, n_div_ls);
1294
106
    if (!res->div)
1295
0
      goto error;
1296
106
  }
1297
9.22k
1298
9.22k
  
isl_int_init9.22k
(f);9.22k
1299
9.22k
  isl_int_init(c1);
1300
9.22k
  isl_int_init(c2);
1301
9.22k
  isl_int_init(g);
1302
9.22k
1303
9.33k
  for (i = 0; 
i < ls->div->n_row9.33k
;
++i111
)
{111
1304
111
    if (
isl_int_is_zero111
(ls->div->row[i][0]))
{0
1305
0
      isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1306
0
      continue;
1307
0
    }
1308
111
    isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1309
111
        ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1310
111
    normalize_div(res, n_div_ma + i);
1311
111
  }
1312
9.22k
1313
9.22k
  isl_int_clear(f);
1314
9.22k
  isl_int_clear(c1);
1315
9.22k
  isl_int_clear(c2);
1316
9.22k
  isl_int_clear(g);
1317
9.22k
1318
9.22k
  isl_local_space_free(ls);
1319
9.22k
  isl_multi_aff_free(ma);
1320
9.22k
  return res;
1321
0
error:
1322
0
  isl_local_space_free(ls);
1323
0
  isl_multi_aff_free(ma);
1324
0
  isl_local_space_free(res);
1325
0
  return NULL;
1326
9.22k
}
1327
1328
/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1329
 * to dimensions of "dst_type" at "dst_pos".
1330
 *
1331
 * Moving to/from local dimensions is not allowed.
1332
 * We currently assume that the dimension type changes.
1333
 */
1334
__isl_give isl_local_space *isl_local_space_move_dims(
1335
  __isl_take isl_local_space *ls,
1336
  enum isl_dim_type dst_type, unsigned dst_pos,
1337
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1338
0
{
1339
0
  unsigned g_dst_pos;
1340
0
  unsigned g_src_pos;
1341
0
1342
0
  if (!ls)
1343
0
    return NULL;
1344
0
  
if (0
n == 0 &&0
1345
0
      !isl_local_space_is_named_or_nested(ls, src_type) &&
1346
0
      !isl_local_space_is_named_or_nested(ls, dst_type))
1347
0
    return ls;
1348
0
1349
0
  
if (0
src_pos + n > isl_local_space_dim(ls, src_type)0
)
1350
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1351
0
      "range out of bounds", return isl_local_space_free(ls));
1352
0
  
if (0
dst_pos > isl_local_space_dim(ls, dst_type)0
)
1353
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1354
0
      "position out of bounds",
1355
0
      return isl_local_space_free(ls));
1356
0
  
if (0
src_type == isl_dim_div0
)
1357
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1358
0
      "cannot move divs", return isl_local_space_free(ls));
1359
0
  
if (0
dst_type == isl_dim_div0
)
1360
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1361
0
      "cannot move to divs", return isl_local_space_free(ls));
1362
0
  
if (0
dst_type == src_type && 0
dst_pos == src_pos0
)
1363
0
    return ls;
1364
0
  
if (0
dst_type == src_type0
)
1365
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1366
0
      "moving dims within the same type not supported",
1367
0
      return isl_local_space_free(ls));
1368
0
1369
0
  ls = isl_local_space_cow(ls);
1370
0
  if (!ls)
1371
0
    return NULL;
1372
0
1373
0
  g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1374
0
  g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1375
0
  if (dst_type > src_type)
1376
0
    g_dst_pos -= n;
1377
0
  ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1378
0
  if (!ls->div)
1379
0
    return isl_local_space_free(ls);
1380
0
  ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1381
0
          src_type, src_pos, n);
1382
0
  if (!ls->dim)
1383
0
    return isl_local_space_free(ls);
1384
0
1385
0
  return ls;
1386
0
}
1387
1388
/* Remove any internal structure of the domain of "ls".
1389
 * If there is any such internal structure in the input,
1390
 * then the name of the corresponding space is also removed.
1391
 */
1392
__isl_give isl_local_space *isl_local_space_flatten_domain(
1393
  __isl_take isl_local_space *ls)
1394
0
{
1395
0
  if (!ls)
1396
0
    return NULL;
1397
0
1398
0
  
if (0
!ls->dim->nested[0]0
)
1399
0
    return ls;
1400
0
1401
0
  ls = isl_local_space_cow(ls);
1402
0
  if (!ls)
1403
0
    return NULL;
1404
0
1405
0
  ls->dim = isl_space_flatten_domain(ls->dim);
1406
0
  if (!ls->dim)
1407
0
    return isl_local_space_free(ls);
1408
0
1409
0
  return ls;
1410
0
}
1411
1412
/* Remove any internal structure of the range of "ls".
1413
 * If there is any such internal structure in the input,
1414
 * then the name of the corresponding space is also removed.
1415
 */
1416
__isl_give isl_local_space *isl_local_space_flatten_range(
1417
  __isl_take isl_local_space *ls)
1418
0
{
1419
0
  if (!ls)
1420
0
    return NULL;
1421
0
1422
0
  
if (0
!ls->dim->nested[1]0
)
1423
0
    return ls;
1424
0
1425
0
  ls = isl_local_space_cow(ls);
1426
0
  if (!ls)
1427
0
    return NULL;
1428
0
1429
0
  ls->dim = isl_space_flatten_range(ls->dim);
1430
0
  if (!ls->dim)
1431
0
    return isl_local_space_free(ls);
1432
0
1433
0
  return ls;
1434
0
}
1435
1436
/* Given the local space "ls" of a map, return the local space of a set
1437
 * that lives in a space that wraps the space of "ls" and that has
1438
 * the same divs.
1439
 */
1440
__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1441
389
{
1442
389
  ls = isl_local_space_cow(ls);
1443
389
  if (!ls)
1444
0
    return NULL;
1445
389
1446
389
  ls->dim = isl_space_wrap(ls->dim);
1447
389
  if (!ls->dim)
1448
0
    return isl_local_space_free(ls);
1449
389
1450
389
  return ls;
1451
389
}