Coverage Report

Created: 2018-06-19 22:08

/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
336k
{
51
336k
  isl_ctx *ctx;
52
336k
  isl_local_space *ls = NULL;
53
336k
54
336k
  if (!dim || !div)
55
0
    goto error;
56
336k
57
336k
  ctx = isl_space_get_ctx(dim);
58
336k
  ls = isl_calloc_type(ctx, struct isl_local_space);
59
336k
  if (!ls)
60
0
    goto error;
61
336k
62
336k
  ls->ref = 1;
63
336k
  ls->dim = dim;
64
336k
  ls->div = div;
65
336k
66
336k
  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
336k
}
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
3
    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
471k
{
98
471k
  if (!ls)
99
0
    return NULL;
100
471k
101
471k
  ls->ref++;
102
471k
  return ls;
103
471k
}
104
105
__isl_give isl_local_space *isl_local_space_dup(__isl_keep isl_local_space *ls)
106
149k
{
107
149k
  if (!ls)
108
0
    return NULL;
109
149k
110
149k
  return isl_local_space_alloc_div(isl_space_copy(ls->dim),
111
149k
           isl_mat_copy(ls->div));
112
149k
113
149k
}
114
115
__isl_give isl_local_space *isl_local_space_cow(__isl_take isl_local_space *ls)
116
346k
{
117
346k
  if (!ls)
118
0
    return NULL;
119
346k
120
346k
  if (ls->ref == 1)
121
196k
    return ls;
122
149k
  ls->ref--;
123
149k
  return isl_local_space_dup(ls);
124
149k
}
125
126
__isl_null isl_local_space *isl_local_space_free(
127
  __isl_take isl_local_space *ls)
128
658k
{
129
658k
  if (!ls)
130
0
    return NULL;
131
658k
132
658k
  if (--ls->ref > 0)
133
322k
    return NULL;
134
335k
135
335k
  isl_space_free(ls->dim);
136
335k
  isl_mat_free(ls->div);
137
335k
138
335k
  free(ls);
139
335k
140
335k
  return NULL;
141
335k
}
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
176k
{
156
176k
  return ls ? isl_space_is_set(ls->dim) : 
isl_bool_error0
;
157
176k
}
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.48M
{
164
1.48M
  if (!ls1 || !ls2)
165
0
    return isl_bool_error;
166
1.48M
167
1.48M
  return isl_space_is_equal(ls1->dim, ls2->dim);
168
1.48M
}
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
48.4k
{
200
48.4k
  isl_bool equal;
201
48.4k
202
48.4k
  equal = isl_local_space_has_equal_space(ls1, ls2);
203
48.4k
  if (equal < 0 || !equal)
204
0
    return equal;
205
48.4k
206
48.4k
  if (!isl_local_space_divs_known(ls1))
207
0
    return isl_bool_false;
208
48.4k
  if (!isl_local_space_divs_known(ls2))
209
0
    return isl_bool_false;
210
48.4k
211
48.4k
  return isl_mat_is_equal(ls1->div, ls2->div);
212
48.4k
}
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
18.3k
{
222
18.3k
  int cmp;
223
18.3k
224
18.3k
  if (ls1 == ls2)
225
26
    return 0;
226
18.3k
  if (!ls1)
227
0
    return -1;
228
18.3k
  if (!ls2)
229
0
    return 1;
230
18.3k
231
18.3k
  cmp = isl_space_cmp(ls1->dim, ls2->dim);
232
18.3k
  if (cmp != 0)
233
0
    return cmp;
234
18.3k
235
18.3k
  return isl_local_cmp(ls1->div, ls2->div);
236
18.3k
}
237
238
int isl_local_space_dim(__isl_keep isl_local_space *ls,
239
  enum isl_dim_type type)
240
2.97M
{
241
2.97M
  if (!ls)
242
0
    return 0;
243
2.97M
  if (type == isl_dim_div)
244
2.24M
    return ls->div->n_row;
245
733k
  if (type == isl_dim_all)
246
279k
    return isl_space_dim(ls->dim, isl_dim_all) + ls->div->n_row;
247
454k
  return isl_space_dim(ls->dim, type);
248
454k
}
249
250
unsigned isl_local_space_offset(__isl_keep isl_local_space *ls,
251
  enum isl_dim_type type)
252
510k
{
253
510k
  isl_space *dim;
254
510k
255
510k
  if (!ls)
256
0
    return 0;
257
510k
258
510k
  dim = ls->dim;
259
510k
  switch (type) {
260
510k
  
case isl_dim_cst: return 00
;
261
510k
  
case isl_dim_param: return 115.2k
;
262
510k
  
case isl_dim_in: return 1 + dim->nparam26.5k
;
263
510k
  
case isl_dim_out: return 1 + dim->nparam + dim->n_in271k
;
264
510k
  
case isl_dim_div: return 1 + dim->nparam + dim->n_in + dim->n_out197k
;
265
510k
  
default: return 00
;
266
510k
  }
267
510k
}
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.11k
{
300
1.11k
  return ls ? isl_space_has_dim_id(ls->dim, type, pos) : 
isl_bool_error0
;
301
1.11k
}
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.11k
{
306
1.11k
  return ls ? isl_space_get_dim_id(ls->dim, type, pos) : NULL;
307
1.11k
}
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
626
{
315
626
  isl_aff *aff;
316
626
317
626
  aff = isl_aff_alloc(isl_local_space_copy(ls));
318
626
  if (!aff)
319
0
    return NULL;
320
626
  isl_seq_cpy(aff->v->el, ls->div->row[pos], aff->v->size);
321
626
  return aff;
322
626
}
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
626
{
364
626
  isl_bool known;
365
626
366
626
  if (!ls)
367
0
    return NULL;
368
626
369
626
  if (pos < 0 || pos >= ls->div->n_row)
370
626
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
371
626
      "index out of bounds", return NULL);
372
626
373
626
  known = isl_local_space_div_is_known(ls, pos);
374
626
  if (known < 0)
375
0
    return NULL;
376
626
  if (!known)
377
626
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
378
626
      "expression of div unknown", return NULL);
379
626
  if (!isl_local_space_is_set(ls))
380
626
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
381
626
      "cannot represent divs of map spaces", return NULL);
382
626
383
626
  known = isl_local_space_divs_known(ls);
384
626
  if (known < 0)
385
0
    return NULL;
386
626
  if (known)
387
626
    return extract_div(ls, pos);
388
0
  else
389
0
    return drop_unknown_divs_and_extract_div(ls, pos);
390
626
}
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.54M
{
396
2.54M
  if (!ls)
397
0
    return NULL;
398
2.54M
399
2.54M
  return ls->dim;
400
2.54M
}
401
402
__isl_give isl_space *isl_local_space_get_space(__isl_keep isl_local_space *ls)
403
590k
{
404
590k
  return isl_space_copy(isl_local_space_peek_space(ls));
405
590k
}
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
1
{
471
1
  ls = isl_local_space_cow(ls);
472
1
  if (!ls)
473
0
    goto error;
474
1
  ls->dim = isl_space_set_tuple_id(ls->dim, type, id);
475
1
  if (!ls->dim)
476
0
    return isl_local_space_free(ls);
477
1
  return ls;
478
0
error:
479
0
  isl_id_free(id);
480
0
  return NULL;
481
1
}
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.7k
{
531
94.7k
  ls = isl_local_space_cow(ls);
532
94.7k
  if (!ls || !dim)
533
0
    goto error;
534
94.7k
535
94.7k
  isl_space_free(ls->dim);
536
94.7k
  ls->dim = dim;
537
94.7k
538
94.7k
  return ls;
539
0
error:
540
0
  isl_local_space_free(ls);
541
0
  isl_space_free(dim);
542
0
  return NULL;
543
94.7k
}
544
545
/* Reorder the dimensions of "ls" according to the given reordering.
546
 * The reordering r is assumed to have been extended with the local
547
 * variables, leaving them in the same order.
548
 */
549
__isl_give isl_local_space *isl_local_space_realign(
550
  __isl_take isl_local_space *ls, __isl_take isl_reordering *r)
551
10.1k
{
552
10.1k
  ls = isl_local_space_cow(ls);
553
10.1k
  if (!ls || !r)
554
0
    goto error;
555
10.1k
556
10.1k
  ls->div = isl_local_reorder(ls->div, isl_reordering_copy(r));
557
10.1k
  if (!ls->div)
558
0
    goto error;
559
10.1k
560
10.1k
  ls = isl_local_space_reset_space(ls, isl_reordering_get_space(r));
561
10.1k
562
10.1k
  isl_reordering_free(r);
563
10.1k
  return ls;
564
0
error:
565
0
  isl_local_space_free(ls);
566
0
  isl_reordering_free(r);
567
0
  return NULL;
568
10.1k
}
569
570
__isl_give isl_local_space *isl_local_space_add_div(
571
  __isl_take isl_local_space *ls, __isl_take isl_vec *div)
572
4.28k
{
573
4.28k
  ls = isl_local_space_cow(ls);
574
4.28k
  if (!ls || !div)
575
0
    goto error;
576
4.28k
577
4.28k
  if (ls->div->n_col != div->size)
578
4.28k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
579
4.28k
      "incompatible dimensions", goto error);
580
4.28k
581
4.28k
  ls->div = isl_mat_add_zero_cols(ls->div, 1);
582
4.28k
  ls->div = isl_mat_add_rows(ls->div, 1);
583
4.28k
  if (!ls->div)
584
0
    goto error;
585
4.28k
586
4.28k
  isl_seq_cpy(ls->div->row[ls->div->n_row - 1], div->el, div->size);
587
4.28k
  isl_int_set_si(ls->div->row[ls->div->n_row - 1][div->size], 0);
588
4.28k
589
4.28k
  isl_vec_free(div);
590
4.28k
  return ls;
591
0
error:
592
0
  isl_local_space_free(ls);
593
0
  isl_vec_free(div);
594
0
  return NULL;
595
4.28k
}
596
597
__isl_give isl_local_space *isl_local_space_replace_divs(
598
  __isl_take isl_local_space *ls, __isl_take isl_mat *div)
599
48.3k
{
600
48.3k
  ls = isl_local_space_cow(ls);
601
48.3k
602
48.3k
  if (!ls || !div)
603
0
    goto error;
604
48.3k
605
48.3k
  isl_mat_free(ls->div);
606
48.3k
  ls->div = div;
607
48.3k
  return ls;
608
0
error:
609
0
  isl_mat_free(div);
610
0
  isl_local_space_free(ls);
611
0
  return NULL;
612
48.3k
}
613
614
/* Copy row "s" of "src" to row "d" of "dst", applying the expansion
615
 * defined by "exp".
616
 */
617
static void expand_row(__isl_keep isl_mat *dst, int d,
618
  __isl_keep isl_mat *src, int s, int *exp)
619
39.7k
{
620
39.7k
  int i;
621
39.7k
  unsigned c = src->n_col - src->n_row;
622
39.7k
623
39.7k
  isl_seq_cpy(dst->row[d], src->row[s], c);
624
39.7k
  isl_seq_clr(dst->row[d] + c, dst->n_col - c);
625
39.7k
626
42.5k
  for (i = 0; i < s; 
++i2.84k
)
627
39.7k
    
isl_int_set2.84k
(dst->row[d][c + exp[i]], src->row[s][c + i]);
628
39.7k
}
629
630
/* Compare (known) divs.
631
 * Return non-zero if at least one of the two divs is unknown.
632
 * In particular, if both divs are unknown, we respect their
633
 * current order.  Otherwise, we sort the known div after the unknown
634
 * div only if the known div depends on the unknown div.
635
 */
636
static int cmp_row(isl_int *row_i, isl_int *row_j, int i, int j,
637
  unsigned n_row, unsigned n_col)
638
12.8k
{
639
12.8k
  int li, lj;
640
12.8k
  int unknown_i, unknown_j;
641
12.8k
642
12.8k
  unknown_i = isl_int_is_zero(row_i[0]);
643
12.8k
  unknown_j = isl_int_is_zero(row_j[0]);
644
12.8k
645
12.8k
  if (unknown_i && 
unknown_j5.41k
)
646
1.34k
    return i - j;
647
11.5k
648
11.5k
  if (unknown_i)
649
4.07k
    li = n_col - n_row + i;
650
7.46k
  else
651
7.46k
    li = isl_seq_last_non_zero(row_i, n_col);
652
11.5k
  if (unknown_j)
653
790
    lj = n_col - n_row + j;
654
10.7k
  else
655
10.7k
    lj = isl_seq_last_non_zero(row_j, n_col);
656
11.5k
657
11.5k
  if (li != lj)
658
5.96k
    return li - lj;
659
5.58k
660
5.58k
  return isl_seq_cmp(row_i, row_j, n_col);
661
5.58k
}
662
663
/* Call cmp_row for divs in a matrix.
664
 */
665
int isl_mat_cmp_div(__isl_keep isl_mat *div, int i, int j)
666
4.30k
{
667
4.30k
  return cmp_row(div->row[i], div->row[j], i, j, div->n_row, div->n_col);
668
4.30k
}
669
670
/* Call cmp_row for divs in a basic map.
671
 */
672
static int bmap_cmp_row(__isl_keep isl_basic_map *bmap, int i, int j,
673
  unsigned total)
674
8.57k
{
675
8.57k
  return cmp_row(bmap->div[i], bmap->div[j], i, j, bmap->n_div, total);
676
8.57k
}
677
678
/* Sort the divs in "bmap".
679
 *
680
 * We first make sure divs are placed after divs on which they depend.
681
 * Then we perform a simple insertion sort based on the same ordering
682
 * that is used in isl_merge_divs.
683
 */
684
__isl_give isl_basic_map *isl_basic_map_sort_divs(
685
  __isl_take isl_basic_map *bmap)
686
64.1k
{
687
64.1k
  int i, j;
688
64.1k
  unsigned total;
689
64.1k
690
64.1k
  bmap = isl_basic_map_order_divs(bmap);
691
64.1k
  if (!bmap)
692
0
    return NULL;
693
64.1k
  if (bmap->n_div <= 1)
694
60.5k
    return bmap;
695
3.64k
696
3.64k
  total = 2 + isl_basic_map_total_dim(bmap);
697
10.5k
  for (i = 1; i < bmap->n_div; 
++i6.86k
) {
698
9.55k
    for (j = i - 1; j >= 0; 
--j2.68k
) {
699
8.57k
      if (bmap_cmp_row(bmap, j, j + 1, total) <= 0)
700
5.89k
        break;
701
2.68k
      isl_basic_map_swap_div(bmap, j, j + 1);
702
2.68k
    }
703
6.86k
  }
704
3.64k
705
3.64k
  return bmap;
706
3.64k
}
707
708
/* Sort the divs in the basic maps of "map".
709
 */
710
__isl_give isl_map *isl_map_sort_divs(__isl_take isl_map *map)
711
24.4k
{
712
24.4k
  return isl_map_inline_foreach_basic_map(map, &isl_basic_map_sort_divs);
713
24.4k
}
714
715
/* Combine the two lists of divs into a single list.
716
 * For each row i in div1, exp1[i] is set to the position of the corresponding
717
 * row in the result.  Similarly for div2 and exp2.
718
 * This function guarantees
719
 *  exp1[i] >= i
720
 *  exp1[i+1] > exp1[i]
721
 * For optimal merging, the two input list should have been sorted.
722
 */
723
__isl_give isl_mat *isl_merge_divs(__isl_keep isl_mat *div1,
724
  __isl_keep isl_mat *div2, int *exp1, int *exp2)
725
36.3k
{
726
36.3k
  int i, j, k;
727
36.3k
  isl_mat *div = NULL;
728
36.3k
  unsigned d;
729
36.3k
730
36.3k
  if (!div1 || !div2)
731
0
    return NULL;
732
36.3k
733
36.3k
  d = div1->n_col - div1->n_row;
734
36.3k
  div = isl_mat_alloc(div1->ctx, 1 + div1->n_row + div2->n_row,
735
36.3k
        d + div1->n_row + div2->n_row);
736
36.3k
  if (!div)
737
0
    return NULL;
738
36.3k
739
38.0k
  
for (i = 0, j = 0, k = 0; 36.3k
i < div1->n_row &&
j < div2->n_row21.6k
;
++k1.70k
) {
740
1.70k
    int cmp;
741
1.70k
742
1.70k
    expand_row(div, k, div1, i, exp1);
743
1.70k
    expand_row(div, k + 1, div2, j, exp2);
744
1.70k
745
1.70k
    cmp = isl_mat_cmp_div(div, k, k + 1);
746
1.70k
    if (cmp == 0) {
747
1.09k
      exp1[i++] = k;
748
1.09k
      exp2[j++] = k;
749
1.09k
    } else 
if (603
cmp < 0603
) {
750
130
      exp1[i++] = k;
751
473
    } else {
752
473
      exp2[j++] = k;
753
473
      isl_seq_cpy(div->row[k], div->row[k + 1], div->n_col);
754
473
    }
755
1.70k
  }
756
56.6k
  for (; i < div1->n_row; 
++i, ++k20.3k
) {
757
20.3k
    expand_row(div, k, div1, i, exp1);
758
20.3k
    exp1[i] = k;
759
20.3k
  }
760
52.2k
  for (; j < div2->n_row; 
++j, ++k15.9k
) {
761
15.9k
    expand_row(div, k, div2, j, exp2);
762
15.9k
    exp2[j] = k;
763
15.9k
  }
764
36.3k
765
36.3k
  div->n_row = k;
766
36.3k
  div->n_col = d + k;
767
36.3k
768
36.3k
  return div;
769
36.3k
}
770
771
/* Swap divs "a" and "b" in "ls".
772
 */
773
__isl_give isl_local_space *isl_local_space_swap_div(
774
  __isl_take isl_local_space *ls, int a, int b)
775
1.13k
{
776
1.13k
  int offset;
777
1.13k
778
1.13k
  ls = isl_local_space_cow(ls);
779
1.13k
  if (!ls)
780
0
    return NULL;
781
1.13k
  if (a < 0 || a >= ls->div->n_row || b < 0 || b >= ls->div->n_row)
782
1.13k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
783
1.13k
      "index out of bounds", return isl_local_space_free(ls));
784
1.13k
  offset = ls->div->n_col - ls->div->n_row;
785
1.13k
  ls->div = isl_mat_swap_cols(ls->div, offset + a, offset + b);
786
1.13k
  ls->div = isl_mat_swap_rows(ls->div, a, b);
787
1.13k
  if (!ls->div)
788
0
    return isl_local_space_free(ls);
789
1.13k
  return ls;
790
1.13k
}
791
792
/* Construct a local space that contains all the divs in either
793
 * "ls1" or "ls2".
794
 */
795
__isl_give isl_local_space *isl_local_space_intersect(
796
  __isl_take isl_local_space *ls1, __isl_take isl_local_space *ls2)
797
0
{
798
0
  isl_ctx *ctx;
799
0
  int *exp1 = NULL;
800
0
  int *exp2 = NULL;
801
0
  isl_mat *div = NULL;
802
0
  isl_bool equal;
803
0
804
0
  if (!ls1 || !ls2)
805
0
    goto error;
806
0
807
0
  ctx = isl_local_space_get_ctx(ls1);
808
0
  if (!isl_space_is_equal(ls1->dim, ls2->dim))
809
0
    isl_die(ctx, isl_error_invalid,
810
0
      "spaces should be identical", goto error);
811
0
812
0
  if (ls2->div->n_row == 0) {
813
0
    isl_local_space_free(ls2);
814
0
    return ls1;
815
0
  }
816
0
817
0
  if (ls1->div->n_row == 0) {
818
0
    isl_local_space_free(ls1);
819
0
    return ls2;
820
0
  }
821
0
822
0
  exp1 = isl_alloc_array(ctx, int, ls1->div->n_row);
823
0
  exp2 = isl_alloc_array(ctx, int, ls2->div->n_row);
824
0
  if (!exp1 || !exp2)
825
0
    goto error;
826
0
827
0
  div = isl_merge_divs(ls1->div, ls2->div, exp1, exp2);
828
0
  if (!div)
829
0
    goto error;
830
0
831
0
  equal = isl_mat_is_equal(ls1->div, div);
832
0
  if (equal < 0)
833
0
    goto error;
834
0
  if (!equal)
835
0
    ls1 = isl_local_space_cow(ls1);
836
0
  if (!ls1)
837
0
    goto error;
838
0
839
0
  free(exp1);
840
0
  free(exp2);
841
0
  isl_local_space_free(ls2);
842
0
  isl_mat_free(ls1->div);
843
0
  ls1->div = div;
844
0
845
0
  return ls1;
846
0
error:
847
0
  free(exp1);
848
0
  free(exp2);
849
0
  isl_mat_free(div);
850
0
  isl_local_space_free(ls1);
851
0
  isl_local_space_free(ls2);
852
0
  return NULL;
853
0
}
854
855
/* Is the local variable "div" of "ls" marked as not having
856
 * an explicit representation?
857
 * Note that even if this variable is not marked in this way and therefore
858
 * does have an explicit representation, this representation may still
859
 * depend (indirectly) on other local variables that do not
860
 * have an explicit representation.
861
 */
862
isl_bool isl_local_space_div_is_marked_unknown(__isl_keep isl_local_space *ls,
863
  int div)
864
230
{
865
230
  if (!ls)
866
0
    return isl_bool_error;
867
230
  return isl_local_div_is_marked_unknown(ls->div, div);
868
230
}
869
870
/* Does "ls" have a complete explicit representation for div "div"?
871
 */
872
isl_bool isl_local_space_div_is_known(__isl_keep isl_local_space *ls, int div)
873
1.17k
{
874
1.17k
  if (!ls)
875
0
    return isl_bool_error;
876
1.17k
  return isl_local_div_is_known(ls->div, div);
877
1.17k
}
878
879
/* Does "ls" have an explicit representation for all local variables?
880
 */
881
isl_bool isl_local_space_divs_known(__isl_keep isl_local_space *ls)
882
273k
{
883
273k
  if (!ls)
884
0
    return isl_bool_error;
885
273k
  return isl_local_divs_known(ls->div);
886
273k
}
887
888
__isl_give isl_local_space *isl_local_space_domain(
889
  __isl_take isl_local_space *ls)
890
9.96k
{
891
9.96k
  ls = isl_local_space_drop_dims(ls, isl_dim_out,
892
9.96k
          0, isl_local_space_dim(ls, isl_dim_out));
893
9.96k
  ls = isl_local_space_cow(ls);
894
9.96k
  if (!ls)
895
0
    return NULL;
896
9.96k
  ls->dim = isl_space_domain(ls->dim);
897
9.96k
  if (!ls->dim)
898
0
    return isl_local_space_free(ls);
899
9.96k
  return ls;
900
9.96k
}
901
902
__isl_give isl_local_space *isl_local_space_range(
903
  __isl_take isl_local_space *ls)
904
0
{
905
0
  ls = isl_local_space_drop_dims(ls, isl_dim_in,
906
0
          0, isl_local_space_dim(ls, isl_dim_in));
907
0
  ls = isl_local_space_cow(ls);
908
0
  if (!ls)
909
0
    return NULL;
910
0
911
0
  ls->dim = isl_space_range(ls->dim);
912
0
  if (!ls->dim)
913
0
    return isl_local_space_free(ls);
914
0
  return ls;
915
0
}
916
917
/* Construct a local space for a map that has the given local
918
 * space as domain and that has a zero-dimensional range.
919
 */
920
__isl_give isl_local_space *isl_local_space_from_domain(
921
  __isl_take isl_local_space *ls)
922
77.0k
{
923
77.0k
  ls = isl_local_space_cow(ls);
924
77.0k
  if (!ls)
925
0
    return NULL;
926
77.0k
  ls->dim = isl_space_from_domain(ls->dim);
927
77.0k
  if (!ls->dim)
928
0
    return isl_local_space_free(ls);
929
77.0k
  return ls;
930
77.0k
}
931
932
__isl_give isl_local_space *isl_local_space_add_dims(
933
  __isl_take isl_local_space *ls, enum isl_dim_type type, unsigned n)
934
77.0k
{
935
77.0k
  int pos;
936
77.0k
937
77.0k
  if (!ls)
938
0
    return NULL;
939
77.0k
  pos = isl_local_space_dim(ls, type);
940
77.0k
  return isl_local_space_insert_dims(ls, type, pos, n);
941
77.0k
}
942
943
/* Remove common factor of non-constant terms and denominator.
944
 */
945
static void normalize_div(__isl_keep isl_local_space *ls, int div)
946
1.00k
{
947
1.00k
  isl_ctx *ctx = ls->div->ctx;
948
1.00k
  unsigned total = ls->div->n_col - 2;
949
1.00k
950
1.00k
  isl_seq_gcd(ls->div->row[div] + 2, total, &ctx->normalize_gcd);
951
1.00k
  isl_int_gcd(ctx->normalize_gcd,
952
1.00k
        ctx->normalize_gcd, ls->div->row[div][0]);
953
1.00k
  if (isl_int_is_one(ctx->normalize_gcd))
954
1.00k
    
return498
;
955
503
956
503
  isl_seq_scale_down(ls->div->row[div] + 2, ls->div->row[div] + 2,
957
503
          ctx->normalize_gcd, total);
958
503
  isl_int_divexact(ls->div->row[div][0], ls->div->row[div][0],
959
503
          ctx->normalize_gcd);
960
503
  isl_int_fdiv_q(ls->div->row[div][1], ls->div->row[div][1],
961
503
          ctx->normalize_gcd);
962
503
}
963
964
/* Exploit the equalities in "eq" to simplify the expressions of
965
 * the integer divisions in "ls".
966
 * The integer divisions in "ls" are assumed to appear as regular
967
 * dimensions in "eq".
968
 */
969
__isl_give isl_local_space *isl_local_space_substitute_equalities(
970
  __isl_take isl_local_space *ls, __isl_take isl_basic_set *eq)
971
4.66k
{
972
4.66k
  int i, j, k;
973
4.66k
  unsigned total;
974
4.66k
  unsigned n_div;
975
4.66k
976
4.66k
  if (!ls || !eq)
977
0
    goto error;
978
4.66k
979
4.66k
  total = isl_space_dim(eq->dim, isl_dim_all);
980
4.66k
  if (isl_local_space_dim(ls, isl_dim_all) != total)
981
4.66k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
982
4.66k
      "spaces don't match", goto error);
983
4.66k
  total++;
984
4.66k
  n_div = eq->n_div;
985
10.9k
  for (i = 0; i < eq->n_eq; 
++i6.25k
) {
986
6.25k
    j = isl_seq_last_non_zero(eq->eq[i], total + n_div);
987
6.25k
    if (j < 0 || j == 0 || j >= total)
988
800
      continue;
989
5.45k
990
8.15k
    
for (k = 0; 5.45k
k < ls->div->n_row;
++k2.70k
) {
991
2.70k
      if (isl_int_is_zero(ls->div->row[k][1 + j]))
992
2.70k
        
continue2.18k
;
993
526
      ls = isl_local_space_cow(ls);
994
526
      if (!ls)
995
0
        goto error;
996
526
      ls->div = isl_mat_cow(ls->div);
997
526
      if (!ls->div)
998
0
        goto error;
999
526
      isl_seq_elim(ls->div->row[k] + 1, eq->eq[i], j, total,
1000
526
          &ls->div->row[k][0]);
1001
526
      normalize_div(ls, k);
1002
526
    }
1003
5.45k
  }
1004
4.66k
1005
4.66k
  isl_basic_set_free(eq);
1006
4.66k
  return ls;
1007
0
error:
1008
0
  isl_basic_set_free(eq);
1009
0
  isl_local_space_free(ls);
1010
0
  return NULL;
1011
4.66k
}
1012
1013
/* Plug in the affine expressions "subs" of length "subs_len" (including
1014
 * the denominator and the constant term) into the variable at position "pos"
1015
 * of the "n" div expressions starting at "first".
1016
 *
1017
 * Let i be the dimension to replace and let "subs" be of the form
1018
 *
1019
 *  f/d
1020
 *
1021
 * Any integer division starting at "first" with a non-zero coefficient for i,
1022
 *
1023
 *  floor((a i + g)/m)
1024
 *
1025
 * is replaced by
1026
 *
1027
 *  floor((a f + d g)/(m d))
1028
 */
1029
__isl_give isl_local_space *isl_local_space_substitute_seq(
1030
  __isl_take isl_local_space *ls,
1031
  enum isl_dim_type type, unsigned pos, isl_int *subs, int subs_len,
1032
  int first, int n)
1033
2.20k
{
1034
2.20k
  int i;
1035
2.20k
  isl_int v;
1036
2.20k
1037
2.20k
  if (n == 0)
1038
1.57k
    return ls;
1039
626
  ls = isl_local_space_cow(ls);
1040
626
  if (!ls)
1041
0
    return NULL;
1042
626
  ls->div = isl_mat_cow(ls->div);
1043
626
  if (!ls->div)
1044
0
    return isl_local_space_free(ls);
1045
626
1046
626
  if (first + n > ls->div->n_row)
1047
626
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1048
626
      "index out of bounds", return isl_local_space_free(ls));
1049
626
1050
626
  pos += isl_local_space_offset(ls, type);
1051
626
1052
626
  isl_int_init(v);
1053
1.56k
  for (i = first; i < first + n; 
++i940
) {
1054
940
    if (isl_int_is_zero(ls->div->row[i][1 + pos]))
1055
940
      
continue732
;
1056
208
    isl_seq_substitute(ls->div->row[i], pos, subs,
1057
208
      ls->div->n_col, subs_len, v);
1058
208
    normalize_div(ls, i);
1059
208
  }
1060
626
  isl_int_clear(v);
1061
626
1062
626
  return ls;
1063
626
}
1064
1065
/* Plug in "subs" for dimension "type", "pos" in the integer divisions
1066
 * of "ls".
1067
 *
1068
 * Let i be the dimension to replace and let "subs" be of the form
1069
 *
1070
 *  f/d
1071
 *
1072
 * Any integer division with a non-zero coefficient for i,
1073
 *
1074
 *  floor((a i + g)/m)
1075
 *
1076
 * is replaced by
1077
 *
1078
 *  floor((a f + d g)/(m d))
1079
 */
1080
__isl_give isl_local_space *isl_local_space_substitute(
1081
  __isl_take isl_local_space *ls,
1082
  enum isl_dim_type type, unsigned pos, __isl_keep isl_aff *subs)
1083
1.19k
{
1084
1.19k
  ls = isl_local_space_cow(ls);
1085
1.19k
  if (!ls || !subs)
1086
0
    return isl_local_space_free(ls);
1087
1.19k
1088
1.19k
  if (!isl_space_is_equal(ls->dim, subs->ls->dim))
1089
1.19k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1090
1.19k
      "spaces don't match", return isl_local_space_free(ls));
1091
1.19k
  if (isl_local_space_dim(subs->ls, isl_dim_div) != 0)
1092
1.19k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_unsupported,
1093
1.19k
      "cannot handle divs yet",
1094
1.19k
      return isl_local_space_free(ls));
1095
1.19k
1096
1.19k
  return isl_local_space_substitute_seq(ls, type, pos, subs->v->el,
1097
1.19k
              subs->v->size, 0, ls->div->n_row);
1098
1.19k
}
1099
1100
isl_bool isl_local_space_is_named_or_nested(__isl_keep isl_local_space *ls,
1101
  enum isl_dim_type type)
1102
9.05k
{
1103
9.05k
  if (!ls)
1104
0
    return isl_bool_error;
1105
9.05k
  return isl_space_is_named_or_nested(ls->dim, type);
1106
9.05k
}
1107
1108
__isl_give isl_local_space *isl_local_space_drop_dims(
1109
  __isl_take isl_local_space *ls,
1110
  enum isl_dim_type type, unsigned first, unsigned n)
1111
21.3k
{
1112
21.3k
  isl_ctx *ctx;
1113
21.3k
1114
21.3k
  if (!ls)
1115
0
    return NULL;
1116
21.3k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(ls, type)7.31k
)
1117
7.29k
    return ls;
1118
14.1k
1119
14.1k
  ctx = isl_local_space_get_ctx(ls);
1120
14.1k
  if (first + n > isl_local_space_dim(ls, type))
1121
14.1k
    
isl_die0
(ctx, isl_error_invalid, "range out of bounds",
1122
14.1k
      return isl_local_space_free(ls));
1123
14.1k
1124
14.1k
  ls = isl_local_space_cow(ls);
1125
14.1k
  if (!ls)
1126
0
    return NULL;
1127
14.1k
1128
14.1k
  if (type == isl_dim_div) {
1129
2.48k
    ls->div = isl_mat_drop_rows(ls->div, first, n);
1130
11.6k
  } else {
1131
11.6k
    ls->dim = isl_space_drop_dims(ls->dim, type, first, n);
1132
11.6k
    if (!ls->dim)
1133
0
      return isl_local_space_free(ls);
1134
14.1k
  }
1135
14.1k
1136
14.1k
  first += 1 + isl_local_space_offset(ls, type);
1137
14.1k
  ls->div = isl_mat_drop_cols(ls->div, first, n);
1138
14.1k
  if (!ls->div)
1139
0
    return isl_local_space_free(ls);
1140
14.1k
1141
14.1k
  return ls;
1142
14.1k
}
1143
1144
__isl_give isl_local_space *isl_local_space_insert_dims(
1145
  __isl_take isl_local_space *ls,
1146
  enum isl_dim_type type, unsigned first, unsigned n)
1147
83.3k
{
1148
83.3k
  isl_ctx *ctx;
1149
83.3k
1150
83.3k
  if (!ls)
1151
0
    return NULL;
1152
83.3k
  if (n == 0 && 
!isl_local_space_is_named_or_nested(ls, type)4
)
1153
0
    return ls;
1154
83.3k
1155
83.3k
  ctx = isl_local_space_get_ctx(ls);
1156
83.3k
  if (first > isl_local_space_dim(ls, type))
1157
83.3k
    
isl_die0
(ctx, isl_error_invalid, "position out of bounds",
1158
83.3k
      return isl_local_space_free(ls));
1159
83.3k
1160
83.3k
  ls = isl_local_space_cow(ls);
1161
83.3k
  if (!ls)
1162
0
    return NULL;
1163
83.3k
1164
83.3k
  if (type == isl_dim_div) {
1165
0
    ls->div = isl_mat_insert_zero_rows(ls->div, first, n);
1166
83.3k
  } else {
1167
83.3k
    ls->dim = isl_space_insert_dims(ls->dim, type, first, n);
1168
83.3k
    if (!ls->dim)
1169
0
      return isl_local_space_free(ls);
1170
83.3k
  }
1171
83.3k
1172
83.3k
  first += 1 + isl_local_space_offset(ls, type);
1173
83.3k
  ls->div = isl_mat_insert_zero_cols(ls->div, first, n);
1174
83.3k
  if (!ls->div)
1175
0
    return isl_local_space_free(ls);
1176
83.3k
1177
83.3k
  return ls;
1178
83.3k
}
1179
1180
/* Does the linear part of "constraint" correspond to
1181
 * integer division "div" in "ls"?
1182
 *
1183
 * That is, given div = floor((c + f)/m), is the constraint of the form
1184
 *
1185
 *    f - m d + c' >= 0   [sign = 1]
1186
 * or
1187
 *    -f + m d + c'' >= 0   [sign = -1]
1188
 * ?
1189
 * If so, set *sign to the corresponding value.
1190
 */
1191
static isl_bool is_linear_div_constraint(__isl_keep isl_local_space *ls,
1192
  isl_int *constraint, unsigned div, int *sign)
1193
230
{
1194
230
  isl_bool unknown;
1195
230
  unsigned pos;
1196
230
1197
230
  unknown = isl_local_space_div_is_marked_unknown(ls, div);
1198
230
  if (unknown < 0)
1199
0
    return isl_bool_error;
1200
230
  if (unknown)
1201
0
    return isl_bool_false;
1202
230
1203
230
  pos = isl_local_space_offset(ls, isl_dim_div) + div;
1204
230
1205
230
  if (isl_int_eq(constraint[pos], ls->div->row[div][0])) {
1206
185
    *sign = -1;
1207
185
    if (!isl_seq_is_neg(constraint + 1,
1208
185
            ls->div->row[div] + 2, pos - 1))
1209
2
      return isl_bool_false;
1210
45
  } else if (isl_int_abs_eq(constraint[pos], ls->div->row[div][0])) {
1211
32
    *sign = 1;
1212
32
    if (!isl_seq_eq(constraint + 1, ls->div->row[div] + 2, pos - 1))
1213
1
      return isl_bool_false;
1214
13
  } else {
1215
13
    return isl_bool_false;
1216
13
  }
1217
214
  if (isl_seq_first_non_zero(constraint + pos + 1,
1218
214
            ls->div->n_row - div - 1) != -1)
1219
0
    return isl_bool_false;
1220
214
  return isl_bool_true;
1221
214
}
1222
1223
/* Check if the constraints pointed to by "constraint" is a div
1224
 * constraint corresponding to div "div" in "ls".
1225
 *
1226
 * That is, if div = floor(f/m), then check if the constraint is
1227
 *
1228
 *    f - m d >= 0
1229
 * or
1230
 *    -(f-(m-1)) + m d >= 0
1231
 *
1232
 * First check if the linear part is of the right form and
1233
 * then check the constant term.
1234
 */
1235
isl_bool isl_local_space_is_div_constraint(__isl_keep isl_local_space *ls,
1236
  isl_int *constraint, unsigned div)
1237
76
{
1238
76
  int sign;
1239
76
  isl_bool linear;
1240
76
1241
76
  linear = is_linear_div_constraint(ls, constraint, div, &sign);
1242
76
  if (linear < 0 || !linear)
1243
14
    return linear;
1244
62
1245
62
  if (sign < 0) {
1246
31
    int neg;
1247
31
    isl_int_sub(ls->div->row[div][1],
1248
31
        ls->div->row[div][1], ls->div->row[div][0]);
1249
31
    isl_int_add_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1250
31
    neg = isl_seq_is_neg(constraint, ls->div->row[div] + 1, 1);
1251
31
    isl_int_sub_ui(ls->div->row[div][1], ls->div->row[div][1], 1);
1252
31
    isl_int_add(ls->div->row[div][1],
1253
31
        ls->div->row[div][1], ls->div->row[div][0]);
1254
31
    if (!neg)
1255
1
      return isl_bool_false;
1256
31
  } else {
1257
31
    if (!isl_int_eq(constraint[0], ls->div->row[div][1]))
1258
31
      
return isl_bool_false29
;
1259
32
  }
1260
32
1261
32
  return isl_bool_true;
1262
32
}
1263
1264
/* Is the constraint pointed to by "constraint" one
1265
 * of an equality that corresponds to integer division "div" in "ls"?
1266
 *
1267
 * That is, given an integer division of the form
1268
 *
1269
 *  a = floor((f + c)/m)
1270
 *
1271
 * is the equality of the form
1272
 *
1273
 *    -f + m d + c' = 0
1274
 * ?
1275
 * Note that the constant term is not checked explicitly, but given
1276
 * that this is a valid equality constraint, the constant c' necessarily
1277
 * has a value close to -c.
1278
 */
1279
isl_bool isl_local_space_is_div_equality(__isl_keep isl_local_space *ls,
1280
  isl_int *constraint, unsigned div)
1281
154
{
1282
154
  int sign;
1283
154
  isl_bool linear;
1284
154
1285
154
  linear = is_linear_div_constraint(ls, constraint, div, &sign);
1286
154
  if (linear < 0 || !linear)
1287
2
    return linear;
1288
152
1289
152
  return sign < 0;
1290
152
}
1291
1292
/*
1293
 * Set active[i] to 1 if the dimension at position i is involved
1294
 * in the linear expression l.
1295
 */
1296
int *isl_local_space_get_active(__isl_keep isl_local_space *ls, isl_int *l)
1297
45.1k
{
1298
45.1k
  int i, j;
1299
45.1k
  isl_ctx *ctx;
1300
45.1k
  int *active = NULL;
1301
45.1k
  unsigned total;
1302
45.1k
  unsigned offset;
1303
45.1k
1304
45.1k
  ctx = isl_local_space_get_ctx(ls);
1305
45.1k
  total = isl_local_space_dim(ls, isl_dim_all);
1306
45.1k
  active = isl_calloc_array(ctx, int, total);
1307
45.1k
  if (total && !active)
1308
0
    return NULL;
1309
45.1k
1310
501k
  
for (i = 0; 45.1k
i < total;
++i456k
)
1311
456k
    active[i] = !isl_int_is_zero(l[i]);
1312
45.1k
1313
45.1k
  offset = isl_local_space_offset(ls, isl_dim_div) - 1;
1314
63.9k
  for (i = ls->div->n_row - 1; i >= 0; 
--i18.7k
) {
1315
18.7k
    if (!active[offset + i])
1316
18.6k
      continue;
1317
1.45k
    
for (j = 0; 173
j < total;
++j1.27k
)
1318
1.27k
      active[j] |= !isl_int_is_zero(ls->div->row[i][2 + j]);
1319
173
  }
1320
45.1k
1321
45.1k
  return active;
1322
45.1k
}
1323
1324
/* Given a local space "ls" of a set, create a local space
1325
 * for the lift of the set.  In particular, the result
1326
 * is of the form [dim -> local[..]], with ls->div->n_row variables in the
1327
 * range of the wrapped map.
1328
 */
1329
__isl_give isl_local_space *isl_local_space_lift(
1330
  __isl_take isl_local_space *ls)
1331
0
{
1332
0
  ls = isl_local_space_cow(ls);
1333
0
  if (!ls)
1334
0
    return NULL;
1335
0
1336
0
  ls->dim = isl_space_lift(ls->dim, ls->div->n_row);
1337
0
  ls->div = isl_mat_drop_rows(ls->div, 0, ls->div->n_row);
1338
0
  if (!ls->dim || !ls->div)
1339
0
    return isl_local_space_free(ls);
1340
0
1341
0
  return ls;
1342
0
}
1343
1344
/* Construct a basic map that maps a set living in local space "ls"
1345
 * to the corresponding lifted local space.
1346
 */
1347
__isl_give isl_basic_map *isl_local_space_lifting(
1348
  __isl_take isl_local_space *ls)
1349
0
{
1350
0
  isl_basic_map *lifting;
1351
0
  isl_basic_set *bset;
1352
0
1353
0
  if (!ls)
1354
0
    return NULL;
1355
0
  if (!isl_local_space_is_set(ls))
1356
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1357
0
      "lifting only defined on set spaces", goto error);
1358
0
1359
0
  bset = isl_basic_set_from_local_space(ls);
1360
0
  lifting = isl_basic_set_unwrap(isl_basic_set_lift(bset));
1361
0
  lifting = isl_basic_map_domain_map(lifting);
1362
0
  lifting = isl_basic_map_reverse(lifting);
1363
0
1364
0
  return lifting;
1365
0
error:
1366
0
  isl_local_space_free(ls);
1367
0
  return NULL;
1368
0
}
1369
1370
/* Compute the preimage of "ls" under the function represented by "ma".
1371
 * In other words, plug in "ma" in "ls".  The result is a local space
1372
 * that is part of the domain space of "ma".
1373
 *
1374
 * If the divs in "ls" are represented as
1375
 *
1376
 *  floor((a_i(p) + b_i x + c_i(divs))/n_i)
1377
 *
1378
 * and ma is represented by
1379
 *
1380
 *  x = D(p) + F(y) + G(divs')
1381
 *
1382
 * then the resulting divs are
1383
 *
1384
 *  floor((a_i(p) + b_i D(p) + b_i F(y) + B_i G(divs') + c_i(divs))/n_i)
1385
 *
1386
 * We first copy over the divs from "ma" and then
1387
 * we add the modified divs from "ls".
1388
 */
1389
__isl_give isl_local_space *isl_local_space_preimage_multi_aff(
1390
  __isl_take isl_local_space *ls, __isl_take isl_multi_aff *ma)
1391
17.3k
{
1392
17.3k
  int i;
1393
17.3k
  isl_space *space;
1394
17.3k
  isl_local_space *res = NULL;
1395
17.3k
  int n_div_ls, n_div_ma;
1396
17.3k
  isl_int f, c1, c2, g;
1397
17.3k
1398
17.3k
  ma = isl_multi_aff_align_divs(ma);
1399
17.3k
  if (!ls || !ma)
1400
0
    goto error;
1401
17.3k
  if (!isl_space_is_range_internal(ls->dim, ma->space))
1402
17.3k
    
isl_die0
(isl_local_space_get_ctx(ls), isl_error_invalid,
1403
17.3k
      "spaces don't match", goto error);
1404
17.3k
1405
17.3k
  n_div_ls = isl_local_space_dim(ls, isl_dim_div);
1406
17.3k
  n_div_ma = ma->n ? 
isl_aff_dim(ma->u.p[0], isl_dim_div)16.6k
:
0704
;
1407
17.3k
1408
17.3k
  space = isl_space_domain(isl_multi_aff_get_space(ma));
1409
17.3k
  res = isl_local_space_alloc(space, n_div_ma + n_div_ls);
1410
17.3k
  if (!res)
1411
0
    goto error;
1412
17.3k
1413
17.3k
  if (n_div_ma) {
1414
543
    isl_mat_free(res->div);
1415
543
    res->div = isl_mat_copy(ma->u.p[0]->ls->div);
1416
543
    res->div = isl_mat_add_zero_cols(res->div, n_div_ls);
1417
543
    res->div = isl_mat_add_rows(res->div, n_div_ls);
1418
543
    if (!res->div)
1419
0
      goto error;
1420
17.3k
  }
1421
17.3k
1422
17.3k
  isl_int_init(f);
1423
17.3k
  isl_int_init(c1);
1424
17.3k
  isl_int_init(c2);
1425
17.3k
  isl_int_init(g);
1426
17.3k
1427
17.6k
  for (i = 0; i < ls->div->n_row; 
++i267
) {
1428
267
    if (isl_int_is_zero(ls->div->row[i][0])) {
1429
0
      isl_int_set_si(res->div->row[n_div_ma + i][0], 0);
1430
0
      continue;
1431
0
    }
1432
267
    isl_seq_preimage(res->div->row[n_div_ma + i], ls->div->row[i],
1433
267
        ma, 0, 0, n_div_ma, n_div_ls, f, c1, c2, g, 1);
1434
267
    normalize_div(res, n_div_ma + i);
1435
267
  }
1436
17.3k
1437
17.3k
  isl_int_clear(f);
1438
17.3k
  isl_int_clear(c1);
1439
17.3k
  isl_int_clear(c2);
1440
17.3k
  isl_int_clear(g);
1441
17.3k
1442
17.3k
  isl_local_space_free(ls);
1443
17.3k
  isl_multi_aff_free(ma);
1444
17.3k
  return res;
1445
0
error:
1446
0
  isl_local_space_free(ls);
1447
0
  isl_multi_aff_free(ma);
1448
0
  isl_local_space_free(res);
1449
0
  return NULL;
1450
17.3k
}
1451
1452
/* Move the "n" dimensions of "src_type" starting at "src_pos" of "ls"
1453
 * to dimensions of "dst_type" at "dst_pos".
1454
 *
1455
 * Moving to/from local dimensions is not allowed.
1456
 * We currently assume that the dimension type changes.
1457
 */
1458
__isl_give isl_local_space *isl_local_space_move_dims(
1459
  __isl_take isl_local_space *ls,
1460
  enum isl_dim_type dst_type, unsigned dst_pos,
1461
  enum isl_dim_type src_type, unsigned src_pos, unsigned n)
1462
0
{
1463
0
  unsigned g_dst_pos;
1464
0
  unsigned g_src_pos;
1465
0
1466
0
  if (!ls)
1467
0
    return NULL;
1468
0
  if (n == 0 &&
1469
0
      !isl_local_space_is_named_or_nested(ls, src_type) &&
1470
0
      !isl_local_space_is_named_or_nested(ls, dst_type))
1471
0
    return ls;
1472
0
1473
0
  if (src_pos + n > isl_local_space_dim(ls, src_type))
1474
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1475
0
      "range out of bounds", return isl_local_space_free(ls));
1476
0
  if (dst_pos > isl_local_space_dim(ls, dst_type))
1477
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1478
0
      "position out of bounds",
1479
0
      return isl_local_space_free(ls));
1480
0
  if (src_type == isl_dim_div)
1481
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1482
0
      "cannot move divs", return isl_local_space_free(ls));
1483
0
  if (dst_type == isl_dim_div)
1484
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_invalid,
1485
0
      "cannot move to divs", return isl_local_space_free(ls));
1486
0
  if (dst_type == src_type && dst_pos == src_pos)
1487
0
    return ls;
1488
0
  if (dst_type == src_type)
1489
0
    isl_die(isl_local_space_get_ctx(ls), isl_error_unsupported,
1490
0
      "moving dims within the same type not supported",
1491
0
      return isl_local_space_free(ls));
1492
0
1493
0
  ls = isl_local_space_cow(ls);
1494
0
  if (!ls)
1495
0
    return NULL;
1496
0
1497
0
  g_src_pos = 1 + isl_local_space_offset(ls, src_type) + src_pos;
1498
0
  g_dst_pos = 1 + isl_local_space_offset(ls, dst_type) + dst_pos;
1499
0
  if (dst_type > src_type)
1500
0
    g_dst_pos -= n;
1501
0
  ls->div = isl_mat_move_cols(ls->div, g_dst_pos, g_src_pos, n);
1502
0
  if (!ls->div)
1503
0
    return isl_local_space_free(ls);
1504
0
  ls->dim = isl_space_move_dims(ls->dim, dst_type, dst_pos,
1505
0
          src_type, src_pos, n);
1506
0
  if (!ls->dim)
1507
0
    return isl_local_space_free(ls);
1508
0
1509
0
  return ls;
1510
0
}
1511
1512
/* Remove any internal structure of the domain of "ls".
1513
 * If there is any such internal structure in the input,
1514
 * then the name of the corresponding space is also removed.
1515
 */
1516
__isl_give isl_local_space *isl_local_space_flatten_domain(
1517
  __isl_take isl_local_space *ls)
1518
0
{
1519
0
  if (!ls)
1520
0
    return NULL;
1521
0
1522
0
  if (!ls->dim->nested[0])
1523
0
    return ls;
1524
0
1525
0
  ls = isl_local_space_cow(ls);
1526
0
  if (!ls)
1527
0
    return NULL;
1528
0
1529
0
  ls->dim = isl_space_flatten_domain(ls->dim);
1530
0
  if (!ls->dim)
1531
0
    return isl_local_space_free(ls);
1532
0
1533
0
  return ls;
1534
0
}
1535
1536
/* Remove any internal structure of the range of "ls".
1537
 * If there is any such internal structure in the input,
1538
 * then the name of the corresponding space is also removed.
1539
 */
1540
__isl_give isl_local_space *isl_local_space_flatten_range(
1541
  __isl_take isl_local_space *ls)
1542
0
{
1543
0
  if (!ls)
1544
0
    return NULL;
1545
0
1546
0
  if (!ls->dim->nested[1])
1547
0
    return ls;
1548
0
1549
0
  ls = isl_local_space_cow(ls);
1550
0
  if (!ls)
1551
0
    return NULL;
1552
0
1553
0
  ls->dim = isl_space_flatten_range(ls->dim);
1554
0
  if (!ls->dim)
1555
0
    return isl_local_space_free(ls);
1556
0
1557
0
  return ls;
1558
0
}
1559
1560
/* Given the local space "ls" of a map, return the local space of a set
1561
 * that lives in a space that wraps the space of "ls" and that has
1562
 * the same divs.
1563
 */
1564
__isl_give isl_local_space *isl_local_space_wrap(__isl_take isl_local_space *ls)
1565
817
{
1566
817
  ls = isl_local_space_cow(ls);
1567
817
  if (!ls)
1568
0
    return NULL;
1569
817
1570
817
  ls->dim = isl_space_wrap(ls->dim);
1571
817
  if (!ls->dim)
1572
0
    return isl_local_space_free(ls);
1573
817
1574
817
  return ls;
1575
817
}
1576
1577
/* Lift the point "pnt", living in the space of "ls"
1578
 * to live in a space with extra coordinates corresponding
1579
 * to the local variables of "ls".
1580
 */
1581
__isl_give isl_point *isl_local_space_lift_point(__isl_take isl_local_space *ls,
1582
  __isl_take isl_point *pnt)
1583
19
{
1584
19
  unsigned n_local;
1585
19
  isl_space *space;
1586
19
  isl_local *local;
1587
19
  isl_vec *vec;
1588
19
1589
19
  if (isl_local_space_check_has_space(ls, isl_point_peek_space(pnt)) < 0)
1590
0
    goto error;
1591
19
1592
19
  local = isl_local_space_peek_local(ls);
1593
19
  n_local = isl_local_space_dim(ls, isl_dim_div);
1594
19
1595
19
  space = isl_point_take_space(pnt);
1596
19
  vec = isl_point_take_vec(pnt);
1597
19
1598
19
  space = isl_space_lift(space, n_local);
1599
19
  vec = isl_local_extend_point_vec(local, vec);
1600
19
1601
19
  pnt = isl_point_restore_vec(pnt, vec);
1602
19
  pnt = isl_point_restore_space(pnt, space);
1603
19
1604
19
  isl_local_space_free(ls);
1605
19
1606
19
  return pnt;
1607
0
error:
1608
0
  isl_local_space_free(ls);
1609
0
  isl_point_free(pnt);
1610
0
  return NULL;
1611
19
}