Coverage Report

Created: 2018-04-24 22:41

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